Algorand: une alternative au PoW

 

Le professeur Silvio Micali du MIT, l’un des meilleurs cryptographes au monde, a récemment publié un document très intéressant intitulé ALGORAND The Efficient and Democratic Ledger où il expose une nouvelle manière de sécuriser une blockchain. Il s’agit d’une solution élégante au problème des généraux byzantins qui permet de se passer de la proof-of-work. Silvio Micali a reçu le Prix Turing (en informatique), le Prix Goedel (en science informatique théorique) et le prix RSA (en cryptographie). Il est notamment co-inventeur du protocole zero-knowledge-proof (ZKP) utilisé par exemple dans Z-Cash.

Si cette innovation devait être appliquée au bitcoin (pour l’instant elle est plutôt applicable dans des réseaux synchrones) elle changerait complètement son visage.

Le professeur Micali a profité de l’exposition de sa nouvelle méthode pour affirmer que les ledger blockchain sont une des technologies de pointe de l’histoire de l’humanité et qu’il est urgent de s’y intéresser de très près. Sans crainte d’exagérer, il a affirmé:

“I believe the public ledger is going to be as beautiful and as useful as any physical infrastructure we have created and I really urge you to devote all of your attention to it.”

C’est pas beau ça ?

***

Le bitcoin présente aujourd’hui trois points majeurs d’amélioration, tous liés à son consensus proof-of-work:

  • la quantité d’énergie indispensable pour sécuriser le réseau, nécessairement redondante mais non optimisée
  • la concentration du mining parmi quelques gros mining-pool dans le monde (conséquence directe de la quantité d’énergie demandée)
  • les forks passagers qui allongent les temps de confirmation

Dans le bitcoin, les forks surviennent chaque fois qu’il y a une ambiguïté sur le gagnant de la course proof-of-work et il faut démêler en suivant la chaîne la plus longue. C’est la raison principale pour laquelle les scrupuleux attendent les fameux 3-6 blocs (surtout pour les sommes importantes) afin d’avoir une certitude absolue que la transaction va bien faire partie de l’historique final.

Ces forks sont artificiellement rares parce que le protocole veut (et doit) espacer d’au moins 10 minutes la création de blocs. Réduire ce temps signifierait augmenter sensiblement le nombre de forks. Une réduction est pourtant nécessaire pour que le BTC devienne pleinement un système de paiement (et non seulement de placement). Voilà pourquoi une approche fork-free est très intéressante pour la communauté.

***

Avant d’entrer dans les détails, tâchons de répondre à une question. Puisque tout est pour l’instant sur papier, comment être sûr que Algorand  va être résistant à toutes sortes d’attaques?

Avec ironie, le professeur (d’origine sicilienne) dit avoir appliqué une méthode pragmatique, le Sicilian Cryptographic Realism: prévoir le pire parce que de toute façon ça va bien finir par arriver. Il a donc imaginé un adversaire parfait auquel il confère virtuellement tout pouvoir:

  • l’adversaire parfait peut instantanément corrompre tout noeud, jusqu’à 1/3 du total (accord byzantin oblige)
  • il a le pouvoir de coordonner comme/quand il veut les noeuds malicieux
  • il peut notamment corrompre instantanément la totalité des validateurs SVr (voir plus bas) dès qu’il est connu par le réseau.

Le white paper, long et assez costaud d’un point de vue mathématique, procède en démontrant pourquoi sa méthode est solide face à un tel adversaire.

***

D’une façon informelle, un accord Byzantin (BA) est un protocole de communication permettant à un ensemble de joueurs de convenir d’une valeur de sortie unique. Un tel accord est atteint par tous les joueurs honnêtes (ceux qui suivent scrupuleusement le protocole) malgré le fait qu’une minorité de joueurs soit malveillante et puisse dévier du protocole de façon arbitraire, éventuellement coordonnée. Algorand propose sa propre version d’Accord Byzantin, une variante beaucoup plus rapide que les précédentes et basée sur une nouvelle propriété, la player replaceability. Nous verrons que cette propriété est le coeur de la fiabilité du système, celle qui le sécurise parfaitement, même dans un environnement hypothétique très adverse.

***

Comment AlgoRand fonctionne-t-il? Commençons par une analogie.

Travailler pour une société comme Google est le rêve de nombreux informaticiens. Il va de soi que les candidatures affluent du monde entier et Google a besoin de filtrer efficacement les CV à la base. Comment s’y prendre?

De manière inefficace: Google pourrait proposer une lourde tâche de programmation aux candidats (ex: construire un algo pointu d’AI) et demander de la poster avec leur CV. Puisqu’un seul CV ne sera retenu à la fin, avec cette solution 99.9% des candidats travailleraient dur pour rien. On voit bien ici une analogie (imparfaite) avec la proof-of-work bitcoin.

De manière efficace: Google propose un quiz mathématique complexe mais rapide à effectuer (pour les plus smart) et demande de le résoudre en secret sur son PC. Le candidat poste ensuite une preuve publique de la solution. C’est cette approche que Google utilise concrètement tous les jours.

Algorand marche un peu selon le même principe. Voyons pourquoi.

***

Dans son paper le professeur nous explique que, bien que très rapide, le nouvel algo BFT ne peut pas être joué par tous les noeuds du système. On sait qu’il est possible de sécuriser une blockchain via un algorithme BFT plutôt que par une PoW ou PoS. Toutefois, si les blockchain qui adoptent cette option sont les permissioned avec un nombre reduit de nodes, ce n’est pas par hasard: le BFT demande aux noeuds des échanges qui sont exponentiels au nombre de participants, raison pour laquelle dans le bitcoin cette approche serait impossible.

Il faut donc avant tout pouvoir activer, pour chaque nouveau bloc, un sous-ensemble de mineurs réduit.

Connaissant l’histoire de l’Italie, le professeur nous rappelle l’époque où la plupart des magistrats à Florence et Venise étaient élus par tirage au sort, puis il nous explique que Algorand va lui aussi tirer au sort: il sélectionne un ensemble de vérificateurs chargés de la construction du prochain bloc par une procédure appelée Cryptographic Sortation. Cette sélection se fait soudainement et de manière mathématiquement résistante aux manipulations. Il faut que ce choix soit imprévisible pour éviter que des noeuds malicieux puissent s’accorder entre eux. Seul ce sous-ensemble d’élus (bien plus petit que l’ensemble de tous les noeuds) sera en charge d’écrire le prochain bloc dans la blockchain.

En substance, on utilise une fonction cryptographique pour déterminer automatiquement, à partir du bloc précédent B-1, l’ensemble des vérificateurs SVr qui vont assumer la tâche de choisir le bloc suivant. Et puisque des utilisateurs malveillants peuvent tenter de piloter la composition de B-1 (par exemple, en effectuant certaines de ses transactions) on construit et on met continuellement à jour une quantité de blocs séparés, Qr, afin de prouver que le SVr est en effet choisi aléatoirement et qu’il n’est, de fait, pas influençable par notre redoutable adversaire tout-puissant.

Il faut souligner que chaque noeud décrète SEUL son appartenance (ou pas) au groupe SVr. Chaque noeud aquiert cette connaissance dans le secret de son PC, sans devoir échanger des messages réseau avec l’extérieur: un concept qu’on définit Secret Credentials.

Un leader est maintenant choisi au hasard à l’intérieur de SVr, l’ensemble des noeuds élus. Si ce leader est honnête, l’accord est trouvé très rapidement. En revanche, si le leader est un noeud malicieux il sera impossible de trouver un point commun, ne pouvant se mettre d’accord sur rien. On arrive alors à une situation de Progrès Zero et on demande le remplacement du leader au sein du groupe jusqu’à tomber sur un noeud correct. La règle de base est qu’avec un mauvais chef on ne touchera aucune récompense pour le mining (lorsque celle si est prévue).

Que se passe-t-il maintenant si un des noeuds SVr tombe? Pour un noeud leader, proposer un nouveau bloc aux autres membres SVr puis mourir n’est pas un problème (son boulot est fini parce que la balle est dans le camp des validateurs du BA).

Pour un noeud qui n’est pas un leader les choses sont différentes. Ces noeuds doivent s’accorder de manière byzantine sur le bloc proposé par le leader, ce qui se fait par des itérations multiples. Dans le BFT classique, chaque itération parvient à un accord avec probabilité 1/3, en supposant que > 2/3 des joueurs soient honnêtes. Hélas, cette supposition ne tient pas dans Algorand: l’Adversaire peut certainement corrompre tous les membres de SVr puisqu’il est un tout petit sous-ensemble de noeuds. 

La solution vient du fait que le protocole est player-replaceable: si à chaque step on renouvelle entièrement l’ensemble des noeuds, le protocole continue à fonctionner correctement. En d’autres termes, l’important est que tous puissent voir les messages propagés plus  que savoir qui est celui qui les a propagés.

Ainsi, à chaque étape de l’accord à trouver, on choisit aléatoirement et indépendamment un nouvel ensemble d’acteurs qui a une intersection nulle avec les ensembles des pas précédents. Il n’est pas indispensable que le nombre d’acteurs soit le même dans les ensembles qui se suivent et les membres de chaque ensemble ne connaissent rien de l’ensemble suivant. Ils ne partagent pas non plus avec eux un quelconque état interne.

***

Encore trois points à noter.

L’approche d’Algorand est pleinement démocratique, dans le sens où il n’y a pas de classes de noeuds comme les mineurs d’un côté et les porteurs de wallet de l’autre. Dans Algorand, tous les noeuds ont la même fonction, les miners et payers sont équivalents.

Algorand élimine les goulots d’étranglement qui aujourd’hui introduisent du retard dans le bitcoin. Le résultat des courses est que dans Algorand la latence coïncide avec la latence du réseau. Ce qui signifie que la scalability n’a virtuellement plus de limites.

Le débat qui fait rage sur la taille des blocs n’existerait plus si on passait à AlgoRand.

***

Pour résumer, Algorand apporte donc les avantages suivants:

  1. demande une quantité négligeable de calcul
  2. résout l’interminable question de la taille des blocs
  3. élimine la séparation entre miners et utilisateurs (une seule classe de participants)
  4. assure au réseau la scalability
  5. garantit l’absence statistique de forks: la probabilité d’occasionner un fork est de l’ordre de  P = 10∧-12, ce qui signifie qu’on devrait voir un fork tous les 19 millions d’années !
  6. élimine tous les retards jusqu’à pouvoir affirmer que la latency d’une blockchain AlgoRand coïncide de facto avec la latency du réseau peer-2-peer qui la porte

***

Comme d’habitude, le concept de consensus repose sur le fait que la plupart des noeuds (ou plutôt de l’argent qui circule dans le réseau) est honnête. Souvent on objecte aux blockchain qu’il s’agit là d’une condition faible, voire inacceptable. Et pourtant c’est un concept qui existe déjà dans la vie courante: que se passerait-il si 51% des Français décidaient de ne plus payer d’impôts?  C’est un cas limite qui s’est déjà produit avec le streaming de musique en p2p et la conséquente loi Hadopi. Face à une technologie p2p difficile à cadrer, la loi a du mal à se faire appliquer. C’est une problématique qui est au coeur de la réglementation du bitcoin.

Les technos comme AlgoRand vont pouvoir faire bouger beaucoup de choses. Personne ne pense que le bitcoin sera dans 10 ans le même qu’aujourd’hui, loin s’en faut! Le bitcoin étant pour la première fois dans l’histoire de l’humanité une monnaie technologique, il évoluera sans aucun doute avec la technologie.

BU, SegWit, Algorand… sont en ce sens des exemples très éloquents et on peut légitimement se demander:

Y aura-t-il un jour une loi de Moore du bitcoin? Je parie que oui.

Déjà avec Algorand on pourrait avoir un bitcoin sans ‘gaspillage’ d’énergie et avec des temps de bloc de l’ordre de quelques dizaines secondes. A ce moment-là, le problème majeur serait probablement la taille de la base qui pourrait grossir à vue d’oeil…  Cela dit je pressens quelques obstacles techniques à l’intégration et il ne faut sans doute pas s’attendre à une adoption rapide (il est plus probable de voir d’abord Algorand dans un système pleinement ou partiellement synchrone).

AlgoRand reprend certaines idées déjà présentes dans le Proof-of-Stake et l’on pourrait se demander quelle est son originalité par rapport au PoS. Cela sera l’objet d’un prochain post (je l’espère).

On verra bien si la communauté bitcoin, si difficile à faire converger, accepte de lui donner sa chance. A mon sens, elle le devrait, compte-tenu surtout de l’autorité de ce grand expert du MIT.

 

6 réflexions au sujet de « Algorand: une alternative au PoW »

  1. Superbe billet ! Très intéressant et instructif. À sa lecture, l’envie d’en apprendre davantage sur AlgoRand est manifeste (je compte lire le White paper rédigé par Micali dans les prochaines semaines). Au plaisir de lire la suite de ce billet lorsqu’il sera disponible ! En vous remerciant sincèrement de partager vos réflexions et vos découvertes, c’est toujours apprécié.

  2. Bonjour David,

    Merci beaucoup pour cet avis d’expert…
    Et je rappelle à vos fidèles lecteurs que vous avez apporté votre éclairage sur différents points techniques dans l’ouvrage qui sort jeudi : « Blockchain, la révolution de la confiance ».

    Merci beaucoup

Laisser un commentaire