Du flocon de neige à l'avalanche (Snowflake to Avalanche): une nouvelle famille de protocoles de consensus métastables pour crypto monnaies

Traduction de l'article Murat Demirbas
Niveau : confirmé
Lecture : 10-15 minutes

Voici le synopsis de l'article. "Cet article introduit une toute nouvelle famille de protocoles de consensus adaptés aux crypto monnaies, basée sur un échantillonnage aléatoire et une décision métastable.Les protocoles offrent une garantie de sécurité probabiliste forte, et une garantie de vivacité pour les clients corrects."

Ci-dessous, je résume d'abord les protocoles et à la fin je fournirai mes commentaires / évaluations. L'analyse de l'article est très poussée et couvre 8 pages, mais je passe cette section dans ma critique.

Introduction

Les protocoles de consensus traditionnels entraînent des frais généraux de communication élevés et une connaissance précise des membres. Ainsi, bien qu'ils fonctionnent bien pour moins de 20 participants, ils ne fonctionnent pas pour un grand nombre de participants et d'environnements ouverts / sans permission. Les protocoles de la famille consensus de Nakamoto traitent ce problème, mais ils sont coûteux et énergivore. Bitcoin consomme actuellement environ 63,49 TWh / an, environ deux fois plus que tout le Danemark.

Cet article introduit une nouvelle famille de protocoles de consensus, inspirés par les algorithmes de ragots (gossip algorithms): Le système fonctionne en échantillonnant de manière répétée dans lequel chaque participant est soumis au hasard, et se doit de diriger les bons nœuds vers le même résultat consensuel. Les protocoles n'utilisent pas de preuves de travail (PoW) mais assurent la sécurité grâce à un mécanisme métastable efficace. Donc, cette famille évite les pires parties des protocoles de consensus traditionnels et de Nakamoto.

Semblable au consensus de Nakamoto, les protocoles offrent une garantie de sécurité probabiliste, utilisant des paramètres de sécurité accordables pour rendre la possibilité d'un échec consensuel arbitrairement faible.

Les protocoles garantissent la vivacité uniquement pour les transactions vertueuses. La vivacité des transactions conflictuelles émises par les clients byzantins n'est pas garantie. Ce point est important, voici l'explication:
"Dans un contexte de crypto monnaie, les signatures cryptographiques imposent que seul un propriétaire de clé puisse créer une transaction qui dépense une pièce particulière. Comme les clients corrects suivent le protocole comme prescrit, ils sont garantis à la fois de la sécurité et de la vivacité. Garantir la vivacité pour les transactions indésirables, soumises par des clients byzantins, qui sont en conflit les uns avec les autres. Ces décisions peuvent bloquer dans le réseau, mais n'ont aucun impact sur la sécurité des transactions vertueuses. C'est un compromis très judicieux pour la construction de systèmes de crypto monnaie. (bien que ce soit bon pour les systèmes de crypto monnaie, ce serait un problème de consensus général où les demandes contradictoires des clients seront présentes.)

Ces transactions non conflictuelles rendent-elles le consensus trivial dans les systèmes de crypto monnaie? Les transactions non conflictuelles réduiraient-elles le consensus à des commérages simples? Avec de simples potins, le client byzantin peut d'abord introduire une transaction, puis introduire une autre transaction. Avec les potins plain la dernière écriture gagne et une double dépense s'ensuivrait. Donc, les commérages simples ne se feront pas; le protocole doit échantillonner et établir / maintenir une sorte de mémoire commune des transactions de sorte qu'une transaction établie devrait être impossible à changer. Nakamoto utilise la superposition de chaînes / amberification (fossilisation) basée sur PoW pour y parvenir. Cet article montre comment cette amberification peut être réalisée via des potins d'échantillonnage et une superposition de DAG sans PoW! Avalanche est un joli nom pour désigner ce processus irréversible.

Le modèle

L'article se base sur le modèle de sortie de transaction non dépensée (UTXO) de Bitcoin: les clients émettent des transactions cryptographiquement signées qui consomment entièrement un UTXO existant et émettent de nouveaux UTXO. Deux transactions sont en conflit si elles consomment le même UTXO et produisent des résultats différents. Les clients corrects n'émettent jamais de transactions en conflit. Il est également impossible pour les clients byzantins de forger des conflits avec des transactions émises par des clients corrects.

D'un autre côté, les clients byzantins peuvent émettre plusieurs transactions qui sont en conflit les uns avec les autres, et les clients corrects ne devraient consommer au maximum qu'une de ces transactions. Le but de la famille des protocoles de consensus Avalanche est d'accepter un ensemble de transactions non conflictuelles en présence du comportement byzantin.

La famille de protocoles Avalanche offre les garanties suivantes avec une probabilité élevée (whp):

• Sécurité. Deux noeuds corrects n'acceptent pas les transactions en conflit.
• Vivacité. Toute transaction émise par un client correct sera finalement acceptée par tous les noeuds corrects.

Slush (neige fondante): Présentation de la métastabilité

L'article commence avec un protocole non-byzantin, Slush, puis construit Snowflake, Snowball et Avalanche, avec de meilleures propriétés de tolérance aux fautes (BFT) et d'irréversibilité byzantines.

Slush est présenté en utilisant une décision entre deux couleurs contradictoires, rouge et bleu. Un noeud commence initialement dans un état incolore. Lors de la réception d'une transaction d'un client, un nœud non coloré met à jour sa propre couleur à celle transportée dans la transaction et initie une requête.

Pour effectuer une requête, un nœud choisit un petit échantillon de taille constante (k) du réseau de manière aléatoire et envoie un message de requête. Lors de la réception d'une requête, un nœud non coloré adopte la couleur de la requête, répond avec cette couleur et initie sa propre requête, alors qu'un nœud coloré répond simplement avec sa couleur actuelle.

Une fois que le nœud interrogateur recueille k réponses, il vérifie si une fraction a * k est de la même couleur, où a> 0.5 est un paramètre de protocole. Si le seuil a * k est atteint et que la couleur échantillonnée diffère de la couleur du nœud, le nœud retourne à cette couleur. Il revient ensuite à l'étape de la requête et lance un cycle de requête ultérieur, pour un total de m tours. Finalement, le nœud décide de la couleur avec laquelle il a fini à l'instant m. Le papier montre dans l'analyse que m croît logarithmiquement avec n.

Ce protocole simple illustre l'idée de base, mais il présente de nombreuses lacunes. Il suppose que les rounds synchronisés sont disponibles pour tous. Dans la ligne 15, la "couleur d'acceptation" vient à la fin de m tours; il n'y a pas d'acceptation précoce. Enfin, Slush ne fournit pas de garantie de sécurité forte en présence de nœuds byzantins, car les nœuds manquent d'état: les nœuds byzantins peuvent essayer de retourner les nœuds sans mémoire aux couleurs opposées.

Snowflake: BFT

Snowflake augmente Slush avec un seul compteur qui mesure la force de conviction d'un nœud dans sa couleur actuelle. Dans le protocole Snowflake de la figure 2:

1. Chaque noeud maintient un compteur cnt;
2. A chaque changement de couleur, le nœud réinitialise cnt à 0;
3. À chaque requête réussie qui donne des réponses =a * k pour la même couleur que le nœud, le nœud incrémente cnt.

Ici, les nœuds peuvent accepter des couleurs de manière asynchrone, pas tous à la fin de m rounds. Chacun peut accepter quand son propre compteur dépasse β. Lorsque le protocole est correctement paramétré pour un seuil donné de nœuds byzantins et une garantie ε souhaitée, il peut assurer à la fois la sécurité et la vivacité.

L'analyse montre qu'il existe un point de déphasage après lequel les nœuds corrects sont plus susceptibles de tendre vers une décision qu'un état bivalent. De plus, il existe un point de non-retour après lequel une décision est inévitable. Les nœuds byzantins perdent le contrôle après le déphasage, et les nœuds corrects commencent à entrer au point de non-retour, pour adopter la même couleur, whp.

Snowball: Ajouter de la confiance

La notion d'état de Snowflake est éphémère: le compteur est réinitialisé à chaque changement de couleur. C'est trop d'histoire à oublier en fonction d'un résultat d'échantillonnage. Snowball augmente Snowflake avec l'élan en ajoutant des compteurs de confiance qui mesure le nombre de requêtes qui ont donné un résultat de seuil pour la couleur correspondante (Figure 3):

1. À chaque requête réussie, le nœud incrémente son compteur de confiance pour cette couleur.
2. Un noeud change de couleur lorsque la confiance dans sa couleur actuelle devient inférieure à la valeur de confiance de la nouvelle couleur.
   

Avalanche: Ajout d'un DAG

L'ajout d'un DAG améliore l'efficacité, car un seul vote sur un sommet DAG vote implicitement pour toutes les transactions sur le chemin vers le sommet de la genèse. Deuxièmement, il améliore également la sécurité, car le DAG entremêle le sort des transactions, similaire à la blockchain Bitcoin. Cela rend les décisions passées (qui sont enterrées sous une avalanche) beaucoup plus difficiles à annuler.

When a client creates a transaction, it names one or more parents in the DAG. This may not correspond to application-specific dependencies: e.g., a child transaction need not spend or have any relationship with the funds received in the parent transaction. The paper includes a detailed discussion of parent selection in the implementation section.

In the cryptocurrency application, transactions that spend the same funds (double-spends) conflict, and form a conflict set, out of which only a single one can be accepted. As we mentioned above, a conflict set is disparate from how the DAG is constructed, yet the protocol needs to maintain and check for conflict sets for the safety of consensus.

Avalanche incarne une instance Snowball pour chaque ensemble de conflits. Alors que Snowball utilisait des requêtes répétées et plusieurs compteurs pour mesurer la quantité de confiance construite dans les transactions conflictuelles (couleurs), Avalanche tire parti de la structure DAG et utilise la progéniture / descendance d'une transaction. Lorsqu'une transaction T est interrogée, toutes les transactions accessibles à partir de T en suivant les bords DAG font implicitement partie de la requête. Un nœud ne répondra positivement à la requête que si T et toute son ascendance sont actuellement l'option préférée dans leurs ensembles de conflits respectifs. Si plus d'un seuil de répondeurs vote positivement, la transaction est censée recueillir un chit, cT = 1, sinon, cT = 0. Les nœuds calculent ensuite leur confiance en tant que somme des valeurs de chit dans la descendance de cette transaction. Les nœuds interrogent une transaction une seule fois et s'appuient sur de nouveaux sommets et chits, ajoutés à la progéniture, pour renforcer leur confiance.

Comme le montre la figure 5, lorsque le nœud u découvre une transaction T à travers une requête, il lance un processus de requête unique en échantillonnant k pairs aléatoires. Une requête commence par l'ajout de T à l'ensemble Transaction, en initialisant cT = 0, puis en envoyant un message aux homologues sélectionnés. Chaque nœud correct u garde trace de toutes les transactions qu'il a apprises dans l'ensemble Tu, partitionné en ensembles de conflits mutuellement exclusifs PT, T∈Tu. Puisque les conflits sont transitifs, si Ti et Tj sont en conflit, alors PTi = PTj.

La figure 6 montre ce qui se passe lorsqu'un noeud reçoit une requête pour la transaction T du pair j. Le nœud détermine si T est actuellement fortement préféré et renvoie une réponse positive au pair j. La transaction T est fortement préférée, si chaque ancêtre de T est préféré parmi ses transactions concurrentes (listées dans son ensemble de conflit correspondant).

Notez que l'ensemble de conflits d'une transaction vertueuse est toujours un singleton. La Figure 7 illustre un exemple de DAG construit par Avalanche, où les régions ombrées indiquent des ensembles de conflits. L'échantillonnage dans Avalanche créera un retour positif pour la préférence d'une transaction unique dans son ensemble de conflits. Par exemple, parce que T2 a une plus grande confiance que T3, ses descendants sont plus susceptibles de collecter des jetons à l'avenir par rapport à T3. Donc, T9 aurait un avantage sur T6 et T7 dans son ensemble de conflits.

La figure 4 illustre la boucle principale du protocole Avalanche, exécutée par chaque nœud. A chaque itération, le nœud tente de sélectionner une transaction T qui n'a pas encore été interrogée. Si aucune transaction de ce type n'existe, la boucle stagnera jusqu'à ce qu'une nouvelle transaction soit ajoutée. Il sélectionne ensuite k pairs et interroge ces pairs. Si plus de α * k de ces pairs renvoient une réponse positive, la valeur du chit est définie sur 1. Après cela, il met à jour la transaction préférée de chaque ensemble de conflits des transactions de son ascendance. Ensuite, T est ajouté à l'ensemble Q afin qu'il ne soit plus jamais interrogé par le noeud.

Similaire à Bitcoin, Avalanche laisse déterminer le point d'acceptation d'une transaction à l'application. Une transaction peut être effectué grâce à un engagement précoce et sécurisé. Pour les transactions vertueuses, T est accepté lorsqu'il est la seule transaction dans son ensemble de conflits et a une confiance supérieure au seuil β1. En variante, T peut également être accepté après un nombre β2 de requêtes consécutives réussies. Si une transaction vertueuse ne parvient pas à être acceptée en raison d'un problème de vivacité avec les parents, elle pourrait être acceptée si elle est réédité avec des parents différents.

La mise en oeuvre

Le Team Rocket a mis en place un système de paiement sans complication en transférant les transactions Bitcoin vers Avalanche. Ils disent: "Déployer une crypto-monnaie complète implique le bootstrap, le monnayage, le jalonnement, le démantèlement et le contrôle de l'inflation.Tandis que nous avons des solutions à ces problèmes, leur discussion complète dépasse la portée de cet article."

Comme je l'ai déjà mentionné, cette section parle en profondeur de la sélection des parents:

L'objectif de l'algorithme de sélection des parents est de produire un DAG bien structuré qui maximise la probabilité que les transactions vertueuses soient rapidement acceptées par le réseau. Bien que cet algorithme n'affecte pas la sécurité du protocole, il affecte la vivacité et joue un rôle crucial dans la détermination de la forme du DAG. Un bon algorithme de sélection des parents fait croître le DAG en profondeur avec une "largeur" ​​approximativement constante. Le DAG ne devrait pas diverger comme un arbre ou converger vers une chaîne, mais plutôt fournir une simultanéité afin que les nœuds puissent fonctionner sur plusieurs fronts.

L'idée la plus simple est peut-être de réaliser une nouvelle transaction avec des parents choisis au hasard parmi les transactions qui sont actuellement fortement préférées. Mais cette stratégie donnera de grands ensembles de parents éligibles, composés principalement d'anciennes transactions historiques. Lorsqu'un nœud échantillonne les transactions uniformément de cette façon, le DAG qui en résulte aura une grande diffusion, qui ne cesse de croître. Parce que les nouvelles transactions auront des progénitures rares, le processus de vote prendra beaucoup de temps pour établir la confiance requise sur une nouvelle transaction donnée.

Non seulement les ancêtres sont importants, mais la progéniture est également importante pour l'acceptation des transactions à faible latence. Les meilleures transactions à choisir se situent quelque part près de la frontière, mais pas trop loin dans l'histoire. L'algorithme de sélection parentale adaptative choisit les parents en commençant à la frontière DAG et en reculant vers le sommet de la genèse jusqu'à trouver un parent éligible.

Évaluation

Le système de paiement de base est implémenté dans des lignes 5K de code C ++. Les tests sont exécutés sur Amazon EC2 en exécutant des centaines à des milliers d'instances de machines virtuelles à l'aide des instances c5.large.

Pour le débit, la gestion d'un ordre partiel (DAG) qui capture simplement les relations de dépenses permet une plus grande simultanéité dans le traitement qu'un système de réplication de journal BFT classique où toutes les transactions doivent être linéarisées. En outre, l'absence d'un leader dans Avalanche permet d'éviter les goulots d'étranglement.

La figure 21 montre que toutes les transactions sont confirmées en environ 1 seconde. La figure 22 montre les latences de transaction pour différents nombres de nœuds et la latence médiane est plus ou moins indépendante de la taille du réseau.

La latence d'Avalanche n'est que légèrement affectée par les clients qui se comportent mal, comme le montre la figure 23.

Pour la géoréplication émulée, les mesures montrent un débit moyen de 1312 tps, avec un écart type de 5 tps, et la latence de transaction médiane est de 4,2 secondes, avec une latence maximale de 5,8 secondes.

Le document comprend un paragraphe de comparaison à Algorand et Bitcoin:

Algorand utilise une fonction aléatoire vérifiable pour élire les comités, et maintient un journal totalement ordonné tandis qu'Avalanche établit seulement un ordre partiel. Algorand est dirigé par un chef et fait consensus par comité, tandis qu'Avalanche est sans chef. Les deux évaluations utilisent un réseau de décision de taille 2000 sur EC2. Notre évaluation utilise c5.large avec 2 vCPU, 2 Gbps réseau par VM, tandis que Algorand utilise m4.2xlarge avec 8 vCPU, 1 Gbps réseau par VM. Les processeurs ont à peu près la même vitesse, et notre réseau n'est pas encombré par le réseau, ce qui rend la comparaison possible. Les paramètres de sécurité choisis dans nos expériences garantissent une probabilité de violation de sécurité inférieure à 10-9 en présence de 20% de nœuds byzantins, tandis que l'évaluation d'Algorand garantit une probabilité de violation inférieure à 5 × 10-9 avec 20% de nœuds byzantins.

Le débit est de 3-7 tps pour Bitcoin, de 364 tps pour Algorand (avec des blocs de 10 Mbyte) et de 159 tps (avec des blocs de 2 Mbyte). En revanche, Avalanche réalise plus de 1300 tps de manière cohérente jusqu'à 2000 nœuds. En ce qui concerne la latence, la finalité est de 10-60 minutes pour Bitcoin, environ 50 secondes pour Algorand avec 10 blocs Mbyte et 22 secondes avec 2 blocs Mbyte, et 4,2 secondes pour Avalanche.

1. Est-ce une nouvelle famille de protocoles?

Oui. Le consensus Nakamato a utilisé le programme PoW pour choisir les leaders. D'autres protocoles utilisent PoX (par exemple, preuve de loterie, preuve d'enjeu, PoW) pour choisir des comités qui exécutent ensuite PBFT. Les protocoles de consensus traditionnels nécessitent une adhésion connue.

En revanche, Avalanche est une famille de protocoles sans leader qui fonctionne en mode ouvert / sans autorisation. Il n'utilise aucun schéma PoX, mais utilise l'échantillonnage aléatoire et la métastabilité pour déterminer et maintenir les transactions.

L'analyse des protocoles est très forte et discute du point de déphasage et du point de non-retour pour ces protocoles. C'est une approche très intéressante pour penser au consensus. C'est aussi une approche très novatrice pour penser à l'auto-stabilisation. J'ai une bonne compréhension de la littérature sur l'auto-stabilisation, mais je n'ai pas non plus vu cette approche dans ce domaine. Je dirais que cette approche susciterait également de l'intérêt dans le vaste domaine des systèmes auto-organisés.

L'analyse DAG dans la section implémentation est également intéressante. Je ne connais pas beaucoup les solutions basées sur le hashgraph, donc je ne sais pas comment cette construction DAG se rapporte à celles-ci.

2. Quelle est l'incitation à participer?

Nous avons déjà discuté d'une implémentation de crypto monnaie en utilisant Avalanche. Mais le monnayage, le jalonnement, la distribution de crédit, etc., ont été laissés pour le travail futur. L'incitation à participer viendrait de la monnaie et du jalonnement de la crypto monnaie. L'attribution de crédit serait intéressante et impliquerait probablement plusieurs nouveaux problèmes de recherche.

3. D'où vient la tolérance Sybil d'Avalanche?

Avalanche tolère les nœuds byzantins en utilisant un paramètre réglable pour augmenter / diminuer le facteur de tolérance. L'article rapporte également des résultats avec 20% de nœuds byzantins.

Cependant, si la participation est très peu coûteuse, l'attaque de Sybil est possible, où un grand nombre de nœuds byzantins peuvent être introduits dans le système en violant les ratios BFT. Je suppose qu'une approche fondée sur le proof of stake peut être utilisée dans Avalanche pour empêcher l'introduction d'un nombre énorme de nœuds byzantins sur le réseau.

Rendre des nœuds Sybil coûteux aide, et cela peut être complété en gardant le nombre de noeuds corrects élevé. Si le protocole peut être vraiment léger, les gens ne verraient pas d'inconvénient à avoir cela en arrière-plan dans leurs ordinateurs portables de la même manière que cela ne les dérange pas. Avec une certaine motivation, il est possible d'avoir beaucoup participants qui augmentent également la tolérance contre l'attaque Sybil.

4. Quelles sont les exigences en ressources (calcul et stockage) chez les participants?

Sur le sujet de la légèreté des ressources du protocole, le document mentionne que la validation des transactions est le goulet d'étranglement des performances: "Pour tester le gain de performance du débit, nous avons effectué une expérience où le système de dosage est désactivé. En outre, l'augmentation de la taille du lot n'augmente pas le débit, car la mise en œuvre est goulue par la vérification des transactions. Notre implémentation actuelle utilise un modèle piloté par les événements pour gérer un grand nombre de messages simultanés provenant du réseau. Après avoir commenté la fonction verify () dans notre code, le débit passe à 8K tps, ce qui montre que l'interprétation du contrat ou les opérations cryptographiques impliquées dans la vérification constituent le principal goulot d'étranglement du système. "

En avalanche, chaque nœud participant doit maintenir le DAG. Mais comme le DAG est une structure de données assez flexible dans Avalanche, je pense qu'il ne devrait pas être difficile de répartir le DAG entre des groupes de participants.

Je m'interroge également sur le coût de la maintenance «conflict set» car je n'ai pas bien compris comment les sets de conflits sont maintenus. Le document mentionne une optimisation pour la maintenance des ensembles de conflits dans la section implémentation: «Un ensemble de conflits peut être très important en pratique, car un client non autorisé peut générer un volume important de transactions conflictuelles. Nous créons un mappage de chaque UTXO vers la transaction préférée qui représente le jeu complet de conflits, ce qui permet à un nœud de déterminer rapidement les conflits futurs et la réponse appropriée aux requêtes.

5. Certaines hypothèses peuvent-elles être utilisées pour construire une attaque?

L'article dit: "L'analyse suppose un réseau synchrone, alors que le déploiement et l'évaluation sont effectués dans un cadre partiellement synchrone.Nous conjecturons que les résultats tiennent dans des réseaux partiellement synchrones, mais la preuve est laissée aux travaux futurs."

Je pense que j'achète ça. Les protocoles venant après Slush ont affaibli l'hypothèse de synchronicité. Le mécanisme d'échantillonnage aléatoire épidémique aide à propager les transactions sur le réseau. Donc, avec un nombre suffisant de nœuds corrects, et quelques garanties faibles sur la vitesse de traitement, je pense que cela peut fonctionner. Eh bien, nous devrions voir la preuve.

Le mécanisme d'échantillonnage aléatoire épidémique nécessite un service décentralisé afin que le nœud puisse se connecter avec suffisamment de nœuds corrects pour acquérir une vue statistiquement non biaisée du réseau. Je suppose que les tables de doigté peer-to-peer seraient suffisantes pour y parvenir. Ce service doit également être protégé contre les nœuds byzantins car cela peut être utilisé pour affecter les résultats consensuels en acheminant les nœuds vers les pools byzantins pour l'échantillonnage. Je me demande si l'asynchronicité peut également être utilisée pour introduire / renforcer le partitionnement de réseau.

---

Si tu es nouveau dans la crypto (ou pas), viens faire un tour sur notre communauté Telegram!
Tu y retrouveras tout ce dont tu as besoin pour bien débuter avec la crypto : des articles pour débutants, des articles pour la culture générale, des reviews d'ICO, du trading, les dernières informations et une communauté chaude et chaleureuse!

🙏 | Si tu aimes cet article, n'hésite pas à upvoter / commenter / resteemer

🙌 | Si tu aimes notre travail et que tu veux nous soutenir en nous faisant un don en ETH, c'est par ici : 0x27D31fa37FA5dC2B19134302517e27342b649F2a