Preuve de travail
Ă quoi sert la preuve de travail ?
La preuve de travail permet de synchroniser un réseau pair à pair (p2p) de machines devant partager une base de données commune.
Dans duniter, cette base de données commune est notre grand livre de comptes commun qui consigne toutes les transactions de la monnaie ainsi que les actes de la toile de confiance (certifications, adhésions, renouvellements, révocations, etc). Elle est inscrite dans une « blockchain ».
Comment fait-on lorsque plusieurs machines souhaitent ajouter en mĂȘme temps une nouvelle donnĂ©e (une nouvelle transaction par exemple) ?
De plus, comment fait-on pour nous mettre d'accord sur le temps qui s'est écoulé ? Ce qui est essentiel pour savoir s'il est temps de créer le dividende universel ainsi que pour gérer les délais d'expiration des adhésions et certifications.
Eh bien la preuve de travail permet de rĂ©soudre ces deux problĂšmes en mĂȘme temps.
Voici comment :
- N'importe quelle machine peut Ă©crire une nouvelle donnĂ©e (= un nouveau bloc), mais pour avoir le droit de l'Ă©crire il faut rĂ©soudre un dĂ©fi qui demande du travail Ă la machine, ce dĂ©fi doit ĂȘtre suffisamment difficile pour qu'il n'y ait pas deux machines qui le rĂ©solvent en mĂȘme temps. Il n'y a donc qu'une seule machine qui peut Ă©crire en mĂȘme temps, celle qui rĂ©sout le dĂ©fi demandĂ©, bien.
- La résolution de ce défi demande un certain temps de calcul qui est fonction de la puissance de calcul du réseau, nous avons donc là un moyen de définir l'écoulement du temps selon un référentiel commun. Il suffit ensuite de choisir une convention, par exemple
1 bloc = 5 min
puis d'adapter la difficulté du défi pour que le réseau trouve bien en moyenne un bloc toutes les 5 min.
Seuls les membres peuvent calculer
Duniter a une différence fondamentale avec toutes les autres crypto-monnaies basées sur la preuve de travail : seuls les membres de la toile de confiance ont le droit d'ajouter des blocs à la blockchain (le grand livre de comptes commun).
Chaque bloc est signĂ© avec la clĂ© privĂ©e du membre qui l'a ajoutĂ©, cela permet d'affecter une difficultĂ© personnalisĂ©e a chaque membre ce qui change absolument tout, sans ce mĂ©canisme la Ä1 serait tout aussi asymĂ©trique et non-libre que le bitcoin !
La difficultĂ© personnalisĂ©e est en effet indispensable pour empĂȘcher la course au calcul, ainsi que pour empĂȘcher un supercalculateur de prendre le contrĂŽle de toute la blockchain et donc de la monnaie.
De plus, la difficultĂ© personnalisĂ©e impose une rotation dans l'Ă©criture des blocs qui permet a tous d'avoir la possibilitĂ© d'Ă©crire dans la blockchain, mĂȘme avec une brique internet ou un raspberry pi, ce qui rend les monnaies duniter considĂ©rablement plus Ă©conomes en Ă©nergie !
Comment marche la preuve de travail ?
L'empreinte (le hash)
Exemple d'empreinte valide :
00000276902793AA44601A9D43099E7B63DBF9EBB55BCCFD6AE20C729B54C653
On peut voir que cette empreinte dĂ©marre par 5 zĂ©ros : rĂ©aliser une telle empreinte demande beaucoup de travail de la part d'un ordinateur, d'oĂč le fait qu'on appelle l'opĂ©ration consistant Ă rĂ©aliser une telle empreinte « preuve de travail ».
La difficulté commune
Afin de nous donner une mesure commune du temps, nous avons besoin d'une difficulté commune qui assure que la blockchain avance à un rythme régulier (1 bloc toutes les avgGenTime
secondes, avgGenTime
étant l'un des 20 paramÚtres qui décrivent une monnaie duniter).
Cette difficulté peut commencer à une valeur arbitraire (70
dans le code v1.5.x
) puis agit comme un ressort, si l'intervalle entre deux blocs est inférieur à avgGenTime
la difficulté commune augmente et inversement si l'intervalle entre deux blocs est supérieur à avgGenTime
, la difficulté commune diminue.
Comment s'applique la difficulté
La valeur numérique de la difficulté correspond directement à une plage d'empreintes possibles parmi toutes les empreintes possibles. Dans duniter v1.5.x
l'empreinte d'un bloc c'est le hash hexadécimal sha256 du bloc. Ce qui veut dire que chaque caractÚre de l'empreinte n'a que 16 valeurs possibles : les chiffres de 0 à 9 et les lettres de A à F.
Pour interpréter une difficulté il faut effectuer la division euclidienne de cette difficulté par 16. Exemple avec 70
:
70 // 16 = 4 reste 6. Donc les empreintes valides sont celles qui commencent par 4 zéros et dont le 5Úme caractÚre est inférieur ou égal à 9 (car on commence à F
(index 0), puis on descend ... E(1), D(2), C(3), B(4), A(5), 9(6)
). On écrit alors que les empreintes valides commencent par : 0000[0-9]
Oui mais l'empreinte d'un bloc sera toujours la mĂȘme pour un bloc donnĂ© et n'a aucune raison de commencer par une suite particuliĂšre, donc comment fait-on pour trouver un bloc qui a comme par hasard une empreinte qui respecte la difficultĂ© ?
Bien vu, il faut effectivement faire varier le contenu du bloc pour obtenir une empreinte différente, c'est le rÎle du Nonce. Lorsque qu'un membre veut ajouter un nouveau bloc à la blockchain, il fixe le contenu de ce bloc, puis rajoute un champ Nonce qu'il fait varier jusqu'à tomber par hasard sur une empreinte qui respecte la difficulté.
Le Nonce
Il s'agit du champ du document Block
permettant de faire varier l'empreinte finale du bloc, empreinte qui définit le niveau de la preuve de travail.
Exemples de valeurs de Nonce :
- 10100000112275
- 10300000288743
- 10400000008538
- 10700000079653
- 10300000070919
En réalité ces valeurs de Nonce
suivent toutes un mĂȘme schĂ©ma XYY00000000000
. Le Nonce ne correspond pas aux nombres d'essais, mais plutÎt à un espace de Nonce possible. La décomposition est la suivante :
- X correspond au numĂ©ro de pair. Par exemple celui qui a plusieurs nĆuds avec la mĂȘme clĂ© personnelle et qui sont donc tous capables de calculer, chacun de ces nĆuds va rĂ©aliser sa preuve avec un X diffĂ©rent, afin de ne pas calculer la mĂȘme preuve justement. Car potentiellement, ils rĂ©alisent exactement le mĂȘme prochain bloc (puisque l'Ă©metteur est le mĂȘme, le contenu possiblement identique, seul le Nonce peut varier), donc il faut avoir un Nonce qui les diffĂ©rencie pour qu'ils ne fassent pas exactement les mĂȘmes calculs.
- Y correspond au numĂ©ro de cĆur du processeur. On peut voir par exemple que quelqu'un possĂšde au moins 7 cores dans son CPU ici, car on lit le Nonce
107[...]
. Un serveur avec 99 cores pourrait réaliser une preuve199[...]
par exemple.
Le reste du Nonce, la partie derriĂšre XYY, est l'espace de Nonce du nĆud pour chaque core du CPU. Ce qui fait donc un espace de 11 chiffres (00000000000
) pour trouver un Nonce correct pour chaque core du CPU de la machine (CPU au sens large, ce peut-ĂȘtre un bi-CPU, on considĂšre le nombre de cores rĂ©sultants pour la PoW).
La difficulté personnalisée
Nous avons expliqué plus haut que la difficulté personnalisée est le nouveau concept fondamental qui différencie les monnaies duniter des autres crypto-monnaies basées sur la « preuve de travail », comme le bitcoin par exemple.
Voici donc comment est calculée la difficulté personnalisée d'un membre :
La difficulté personnalisée d'un membre résulte de l'assemblage de deux contraintes distinctes qui ont des rÎles complémentaires : le facteur d'exclusion et le handicap.
Soient powMin
la difficulté commune, exFact
le facteur d'exclusion d'un membre et handicap
son handicap. La difficulté personnalité diff
de ce membre est :
diff = powMin*exFact + handicap
Le facteur d'exclusion exFact
d'un membre
Les membres qui n'ont jamais écrit de bloc ou qui n'ont pas écrit de bloc depuis longtemps ont un facteur d'exclusion de 1
. Leur difficulté personnalisée sera donc égale à la somme powMin + handicap
.
Avant de lire la formule donnĂ©e plus bas vous devez comprendre le rĂŽle de ce facteur d'exclusion : lorsqu'un membre ajoute un bloc Ă la blockchain, son facteur d'exclusion saute subitement de 1 vers une valeur trĂšs Ă©levĂ©e afin de faire grimper exponentiellement sa difficultĂ© et l'exclure ainsi du calcul des prochains blocs et donc l'empĂȘcher de prendre le contrĂŽle de la blockchain.
Le facteur d'exclusion du membre va ensuite chuter rapidement Ă chaque nouveau bloc dont il n'est pas l'auteur puis retomber Ă 1 au bout d'un nombre de blocs qui est en fait une proportion du nombre de membres calculant (un tiers dans le cas de la Ä1, ce qui signifie que s'il y a 15 membres calculant vous ĂȘtes exclus pendant 5 blocs).
heu attend c'est quoi le nombre de membres calculant ?
TrÚs bonne question, il s'agit du nombre de membres que l'on considÚre comme étant actuellement en train de calculer le prochain bloc. En réalité il n'y a aucun moyen de savoir combien de membres sont réellement en train de calculer le prochain bloc car d'une part il est impossible d'avoir une vue complÚte du réseau et d'autre part il existe des moyens de se rendre invisible du réseau. Il nous faut pourtant bien choisir une méthode, car sans considérer le nombre de membres calculant, il est impossible de calibrer la difficulté personnalisée.
La méthode actuellement utilisée par Duniter est de regarder l'historique des X derniers blocs et considérer que le nombre de membres calculant c'est le nombre de membres ayant écrit au moins 1 bloc sur les X derniers blocs sans compter le tout dernier bloc.
Et comment on choisit X ?
GrĂ ce au concept de fenĂȘtre courante, X correspond alors Ă la taille de la fenĂȘtre courante, voici comment cela fonctionne :
On nomme issuersFrame
la taille de la fenĂȘtre courante et issuersCount
le nombre de membres ayant calculĂ© au moins 1 bloc dans la fenĂȘtre courante.
Au commencement d'une blockchain, le tout premier bloc que l'on nomme le bloc #0 décrÚte que issuersFrame=1
et issuersCount=0
. HĂ© oui le tout dernier bloc Ă©tant exclu, il n'y a pour l'instant aucun membre dans la fenĂȘtre courante.
Ensuite, Ă chaque nouveau bloc, on mesure la variation de issuersCount
, dĂšs le second bloc (le bloc #1), l'auteur du bloc #0 entre dans la fenĂȘtre courante, on Ă©crira donc dans le bloc #1 issuersCount=1
.
issuersFrame
varie alors de la façon suivante : si issuersCount
augmente de X (et X = 1 au maximum), alors issuersFrame
augmentera de 1 unité pendant 5X blocs. Et inversement : si issuersCount
diminue de Y (et Y = 2 au maximum : dĂ©calage de fenĂȘtre + perte dâun auteur), alors issuersFrame diminuera de 1 unitĂ© pendant 5Y blocs. Les effets Ă©tant cumulatifs dans le temps. Ce qui fait que si un nouvel auteur apparaĂźt au bloc T
et un autre disparaĂźt Ă T+1
, issuersFrame
augmentera de 1 unité à T+1
puis diminuera de 1 unité à T+2
, pour se stabiliser.
Techniquement ce calcul est formalisé par les rÚgles BR_G05 et BR_G06 du protocole DUP.
Revenons à notre difficulté personnalisée !
Nous avons dit que le facteur d'exclusion exFact
augmente brutalement dÚs que le membre considéré trouve un bloc puis qu'il diminue rapidement pour retomber à 1
au bout d'un nombre de blocs égal au tiers des calculateurs. Et bien, c'est parti voici comment est calculé exFact
 :
Soient nbPreviousIssuers
la valeur du champ issuersCount
du dernier bloc trouvé par le membre et nbBlocksSince
le nombre de blocs trouvés par le reste du réseau depuis que le membre considéré a trouvé son dernier bloc.
exFact = MAX [ 1 ; FLOOR (0.67 * nbPreviousIssuers / (1 + nbBlocksSince)) ]
La fonction FLOOR est une simple troncature, ainsi pour que exFact
soit excluant il faut que le rapport (0.67 * nbPreviousIssuers / (1 + nbBlocksSince))
soit supérieur ou égal à 2. On voit bien que si nbBlocksSince
est supérieur au tiers des calculateurs = 0.33*nbPreviousIssuers
alors le rapport sera inférieur à 2 et donc le membre ne sera pas exclu du calcul du prochain bloc.
à l'inverse, si le membre considéré est l'auteur du dernier bloc alors nbBlocksSince=0
et le facteur d'exclusion vaut donc 0.67 * nbPreviousIssuers
, c'est d'autant plus grand que le nombre de calculateurs est élevé. Je vous laisse imaginer la difficulté vertigineuse que vous atteindrez en trouvant un bloc s'il y a des centaines de membres calculant !
Vous atteindrez une difficultĂ© telle que mĂȘme le plus grand des supercalcuteurs serait bloquĂ©, et c'est bien le but du facteur d'exclusion : empecher les supercalculateurs et fermes de calcul de prendre le contrĂŽle de la blockchain et donc de la monnaie.
En revanche, a tout instant t les deux tiers des membres calculant non exclus ont tous un facteur d'exclusion égal à 1
, mais tous n'ont pas la mĂȘme puissance de calcul, et donc si la difficultĂ© personnalisĂ©e se limitait au facteur d'exclusion c'est toujours le tiers des membres calculant les plus puissants qui Ă©criraient des blocs et deux tiers restants seraient presque toujours exclus, en particulier les machines trĂšs modestes type raspberry n'auraient aucune chance.
Le handicap
Le handicap est le second paramÚtre de la difficulté personnalisée. Plus subtil, il permet néanmoins d'améliorer considérablement le mécanisme de rotation en donnant un handicap aux membres ayant une machine puissante afin de donner leur chance aux machines les plus modestes et de diminuer le coût écologique de la monnaie.
Le calcul du handicap se base sur le nombre mĂ©dian de blocs Ă©crits par chaque membre au sein de la fenĂȘtre courante. En gros, l'idĂ©e est de donner un handicap Ă la moitiĂ© haute de la fenĂȘtre courante pour donner plus de chance Ă la moitiĂ© basse.
Soient nbPersonalBlocksInFrame
le nombre de blocs Ă©crits par le membre considĂ©rĂ© dans la fenĂȘtre courante et medianOfBlocksInFrame
le nombre mĂ©dian de blocs Ă©crits par les membres au sein de la fenĂȘtre courante.
Voici la formule :
handicap = FLOOR(LN(MAX(1;(nbPersonalBlocksInFrame + 1) / medianOfBlocksInFrame)) / LN(1.189))
Démystifions cette formule, (nbPersonalBlocksInFrame + 1) / medianOfBlocksInFrame)
est simplement le rapport entre le nombre de blocs calculés par le membre et la médiane. Par exemple si le membre a calculé 9
blocs dans la fenĂȘtre courante alors que la mĂ©diane vaut 5
, ce rapport vaudra (9+1)/5 = 2
.
On s'assure via la fonction MAX que ce rapport vaut au moins 1
.
Ensuite on prend le logarithme nĂ©pĂ©rien de ce rapport pour Ă©viter que le handicap devienne excluant lorsque la fenĂȘtre courante devient trĂšs grande, c'est ce qui fait la subtilitĂ© du handicap, son rĂŽle n'est pas d'exclure mais de niveler la difficultĂ© de chacun en fonction de sa puissance pour que tout le monde ait a peu prĂšs les mĂȘmes chances de calculer.
Si l'on veut que le handicap s'applique dés la médiane il faudrait ensuite diviser par LN(1)
, le problÚme c'est qu'on a déjà nivellé la rapport à 1
avec la fonction MAX, donc si l'on divisait par LN(1)
tous les membres calculant auraient un handicap >= 1
, qui plus est, est-il bien juste de donner un handicap à un membre qui est tout juste à la médiane ?
C'est pourquoi, au lieu de prendre 1
, on prend 1.189
, ce qui veut dire qu'il faut ĂȘtre 18,9 %
 au-dessus de la médiane pour subir un handicap (si l'on néglige le +1 dans la formule qui devient effectivement négligeable pour un grand nombre de calculateurs).
Mais pourquoi 18,9%
me direz-vous ?
C'est 16^(1/16), le facteur de difficulté entre 2 niveaux de la preuve de travail dont le hash est en hexadécimal.
En conclusion, ce qu'il faut retenir c'est l'idée d'indexer le handicap sur le logarithme du rapport à la médiane, et de ne l'appliquer que pour les membres dont le rapport à la médiane dépasse le rapport entre 2 niveaux de difficulté de la preuve de travail.