Cet article est un examen superficiel des principales approches pour parvenir à un consensus dans un environnement décentralisé. Le matériel vous permettra de comprendre les tâches qui résolvent les protocoles considérés, la portée de leur application, les fonctionnalités de conception et d'utilisation, et évaluera également les perspectives de leur développement et de leur mise en œuvre dans des systèmes comptables décentralisés.
Notez que dans un réseau décentralisé, le principe de redondance est appliqué, qui est basé sur le fait que les nœuds peuvent faire le même travail. Pour un réseau centralisé, cela est naturellement inefficace et pour un réseau décentralisé, c'est une condition préalable. Passons aux exigences de base.
Exigences du protocole de consensus
Les protocoles doivent garantir un fonctionnement fiable des utilisateurs dans des conditions assez difficiles et en même temps satisfaire aux exigences minimales. Les principaux sont énumérés ci-dessous.
Absence d'une partie centrale de confiance . Un réseau est composé de pairs. Si un attaquant ou un tiers tente de désactiver un certain nombre de nœuds, le réseau continuera de fonctionner normalement jusqu'à ce que des participants honnêtes contrôlent la grande majorité des nœuds du réseau.
Les membres honnêtes ne savent pas quels sites sont contrôlés par des cybercriminels . Il est supposé que d'autres nœuds peuvent échouer ou fonctionner arbitrairement à des moments arbitraires, notamment en étant coordonnés par des attaquants pour mener une attaque sur le réseau. Encore une fois, les participants honnêtes ne savent pas lesquels des nœuds sont honnêtes et lesquels sont mauvais ou peu fiables.
On suppose que le
réseau est sciemment peu fiable . Certains messages peuvent être remis avec un retard important, tandis que d'autres peuvent être perdus sur le réseau et ne pas être remis du tout. C'est dans de telles circonstances que le consensus décentralisé devrait continuer à fonctionner normalement: tous les nœuds honnêtes devraient arriver au même état de la base de données des transactions confirmées.
Les protocoles doivent être complètement formels . Aucune implication humaine supplémentaire ne devrait être et aucune donnée supplémentaire n'est requise. Tous les nœuds honnêtes doivent arriver à la même solution, en suivant entièrement l'algorithme que l'ordinateur exécute.
De plus,
il existe certaines hypothèses selon lesquelles le protocole garantit un fonctionnement correct . Les nœuds honnêtes devraient constituer la majorité de tous les participants: plus de la moitié ou les ⅔ de leur nombre total. Cependant, le temps de prise de décision n'est pas limité. La restriction peut concerner le nombre d'étapes pour prendre une décision, mais pas le temps.
Domaines des protocoles de consensus
Monnaies numériques
Tout d'abord, cela s'applique aux crypto-monnaies: Bitcoin utilise l'algorithme Nakamoto, Ethereum utilise une version simplifiée de GHOST, Bitshares implémente le PoS délégué, etc.
Il convient de noter qu'une communauté qui prend en charge une certaine monnaie numérique n'est pas toujours grande et décentralisée. Il existe un certain nombre d'autres monnaies numériques qui sont centralisées. Toutefois, cela ne signifie pas qu'un mécanisme de consensus n'est pas nécessaire. Par exemple, Ripple utilise le protocole BFT dans un environnement centralisé.
Systèmes hautement fiables et critiques
Les protocoles de consensus sont utilisés dans les systèmes informatiques hautement fiables. Ils peuvent être utilisés pour accéder à des bases de données distribuées lors de la construction de clusters, et ils sont également nécessairement utilisés dans des systèmes techniques critiques: il peut s'agir de systèmes de contrôle d'équipements aéronautiques, de systèmes de contrôle de réacteurs nucléaires, ainsi que dans les technologies spatiales.
Le 6 février 2018, le lancement du Falcon Heavy a eu lieu. C'était intéressant de le regarder et de lire les revues techniques. Mais il n'était pas moins intéressant de savoir quels algorithmes de consensus l'équipe utilise. Les ingénieurs ont été contraints d'utiliser des appareils électroniques simples, qui sont vendus dans des magasins ordinaires et ne fonctionnent pas de manière très fiable dans des conditions spatiales difficiles. Par conséquent, ils utilisent plusieurs redondances dans leur travail et parvenir à un consensus dans ce cas est nécessaire.
Crypto-monnaies
Les crypto-monnaies fonctionnent dans les réseaux peer-to-peer. Dans ce cas, des messages ou des transactions sont transmis entre les participants du réseau à des moments arbitraires. Supposons qu'il existe des membres situés aux États-Unis et des membres situés en Australie sur le réseau. Les paiements envoyés depuis les États-Unis seront vus par les participants d'Amérique plus tôt que les paiements envoyés depuis l'Australie. Cela est dû au sérieux retard, selon les normes informatiques, dans la livraison d'un message d'un continent à l'autre. La situation sera similaire pour les Australiens, car ils verront les paiements de l'Australie plus tôt que les paiements des États-Unis.
La situation décrite ci-dessus signifie que différents participants au réseau verront à un moment donné qu'ils verront un état final différent de la base de données avec les transactions. Étant donné que les transactions proviennent d'utilisateurs à des valideurs à des moments différents, un protocole est nécessaire qui permettra à chaque nœud, quel que soit son emplacement, de recevoir toutes les transactions dans le même ordre.
Fondamentalement, deux approches sont utilisées pour le fonctionnement des systèmes comptables de crypto-monnaie: PoW, qui est le plus courant, et PoS, qui s'est développé activement récemment.
Dans PoW, un travail supplémentaire est en cours, qui consiste désormais à trouver le prototype de la fonction de hachage. En fait, il y a un ralentissement artificiel du réseau pour assurer la sécurité. Pour effectuer une action malveillante, un attaquant devra effectuer la quantité de travail nécessaire. Cela nécessite une énorme quantité d'énergie et rend la mise en œuvre d'attaques peu efficace. Cette approche garantit la fiabilité du réseau. Cependant, la nécessité d'effectuer une telle tâche exigeante en ressources limite la bande passante du réseau qui s'exécute sur ce protocole. Mais les scientifiques continuent de travailler sur l'approche PoW et proposent des schémas alternatifs, ainsi que d'autres tâches gourmandes en ressources, en plus de rechercher l'image inverse de la fonction de hachage. Récemment, un algorithme basé sur la
preuve de l'espace et du temps a été proposé.
PoS vous permet de fournir une bande passante réseau plus élevée et ne nécessite pas de coûts énergétiques excessifs, comme PoW. Cependant, PoS nécessite une analyse plus sérieuse dans le développement et la mise en œuvre des crypto-monnaies.
Dans les systèmes de comptabilité basés sur PoS, il est supposé que les utilisateurs qui possèdent un grand nombre de pièces ne sont pas rentables à attaquer. Si dans des systèmes comptables basés sur un système PoW, un entrepreneur investit de l'argent dans des équipements et paie de l'électricité, puis attaque avec succès le système, alors il perdra son investissement dans l'exploitation minière. Dans PoS, une approche différente est adoptée: s'il est supposé que l'attaquant a investi dans des pièces spécifiques dans les valeurs dont il est intéressé, alors en cas d'attaque réussie sur le système, il perdra ses investissements, car les pièces se déprécieront. Par conséquent, la stratégie la plus rentable est considérée comme une adhésion honnête au protocole.
Glossaire court
Sécurité - la capacité du système comptable à maintenir les principes de base du fonctionnement et les intérêts des participants honnêtes en cas d'influences malveillantes.
Finalité - une propriété qui indique l'irrévocabilité d'une décision ou de données confirmées.
Liveness est une propriété qui garantit que si tous les membres honnêtes veulent ajouter une entrée à une base de données commune, elle y sera ajoutée.
Persistance - la capacité du système comptable à maintenir l'invariabilité de l'état final de sa base de données même après l'échec de tous ses valideurs.
Autorisé - indique une restriction, c'est-à-dire la nécessité d'obtenir l'autorisation de participer à un certain processus.
Sans autorisation - signifie un accès gratuit pour participer à un certain processus.
Protocole de consensus d'Ouroboros
Ouroboros est un protocole basé sur PoS qui fournit un consensus parmi les validateurs de transactions de monnaie numérique Cardano. De plus, l'algorithme lui-même est le premier à être stable parmi toutes les alternatives PoS.
Tout d'abord, considérons une option plus simple basée sur la mise statique, quand on suppose que la distribution existante des pièces ne change pas.
Il y a un bloc de genèse et les utilisateurs forment de nouvelles transactions, mais elles n'affectent pas de manière significative la distribution.
Le bloc Genesis contient des données avec une valeur aléatoire, à l'aide de laquelle la sélection des validateurs a lieu. Ils vous permettent de libérer le bloc à un certain moment. Le validateur qui a reçu ce droit collecte les transactions, les reçoit d'un autre validateur, vérifie l'exactitude et libère le bloc dans le réseau. S'il voit plusieurs chaînes, il en sélectionne la plus longue et y attache le bloc.
Dans le contexte de la situation liée à la mise statique, nous pouvons utiliser cette approche pendant une certaine période de temps, mais alors la répartition de la mise (distribution de la mise) entre les différents utilisateurs peut changer. En d'autres termes, une partie de l'argent va d'un utilisateur à un autre et vous devez ajuster la probabilité d'obtenir le droit de choisir un bloc.
Remarque : la mise statique implique qu'une certaine période de mise validateur est considérée comme inchangée. Le validateur peut à ce moment participer à la décision et effectuer les paiements, mais le nombre de pièces en jeu, et donc le poids de son vote, restera inchangé jusqu'à la prochaine période.
Dans le cas d'un enjeu dynamique, le temps est divisé en créneaux et les créneaux sont divisés en époques. La durée d'une ère est approximativement égale à la durée d'une journée. Ce ratio est déterminé par le fait que pendant cette période, la distribution des pièces ne peut pas changer de manière significative.
A la fin de l'ère, la répartition actuelle des pièces pour chaque utilisateur est enregistrée. De plus, une nouvelle valeur aléatoire est générée pour garantir que dans la prochaine ère, les utilisateurs éligibles pour générer des blocs seront effectivement sélectionnés au hasard en fonction du nombre de pièces dont ils disposent.
De même, il existe une protection contre les soi-disant attaques de meulage, lorsqu'un utilisateur particulier peut trier diverses options de blocs, diverses options d'aléatoire pour former la chaîne dans laquelle il peut maximiser son profit. Les crypto-monnaies basées sur des protocoles PoS de première génération tels que Peercoin et NXT sont potentiellement vulnérables à de telles attaques.
Les créateurs de cet algorithme ont résolu les problèmes ci-dessus. Les validateurs démarrent un protocole spécial entre eux, qui s'appelle MPC (calcul multipartite) et permet de générer ensemble des aléas. Ce protocole est également prouvé robuste, basé sur des approches établies de longue date.
Le protocole d'Ouroboros assure la persistance, à condition que la majorité des validateurs honnêtes soient dans le système. Si des participants honnêtes qui travaillent sur la question des blocs contrôlent plus de 50% des pièces du système, le protocole peut être considéré comme protégé.
Un mécanisme d'incitation (motivation) à un comportement honnête a été développé. En utilisant la théorie des jeux, il est prouvé que le validateur obtient le maximum d'avantages lorsqu'il suit les règles du protocole. Toute participation à la commission d'attaques non seulement n'augmente pas le profit du participant, mais dans certains cas peut le réduire. Par conséquent, la stratégie la plus rentable pour le validateur est de suivre honnêtement les règles du protocole.
La capacité du système comptable ne sera limitée que par des retards lors de la synchronisation du réseau. Ce protocole offre une efficacité énergétique élevée par rapport à la preuve de travail, car les exploitations minières ne sont pas nécessaires ici. Maintenant pour la collecte des transactions et la libération des blocs, un ordinateur personnel normal suffit. À l'avenir, ces calculs pourront être effectués même sur un smartphone classique.
Les limites du protocole Ouroboros incluent le fait que la première version du protocole est synchrone. Cela signifie que les messages entre les participants doivent être livrés dans un délai limité. Si le réseau présente des retards plus longs que ceux prévus par les règles, cela peut réduire la sécurité. Néanmoins, il est déjà prévu d'utiliser la prochaine version du protocole - Ouroboros Praos. En cela, même avec une augmentation des retards réseau, une sécurité complète est garantie.
Problèmes avec PoW dans Bitcoin
Considérez le consensus qui sous-tend le Bitcoin. Une partie des blocs qui sont générés par des utilisateurs honnêtes sont toujours jetés - ce sont les soi-disant blocs orphelins. Ces blocs sont générés en parallèle avec la chaîne principale, mais la plupart du réseau a décidé que cette chaîne ne devait pas être poursuivie et les blocs sont supprimés.
Lorsqu'il y a peu de tels blocs, il n'y a rien à craindre. Cependant, s'il y en a beaucoup, le réseau n'a pas le temps de se synchroniser et il s'avère qu'une partie de la puissance de calcul des utilisateurs honnêtes du réseau est gaspillée. Cela signifie que l'attaquant doit désormais se battre non pas pour 51% de la puissance de calcul du réseau, mais en fait pour un pourcentage inférieur. Si cette valeur est de 20%, un attaquant disposant de 20% de la puissance de calcul et d'un retard important dans la livraison des messages réseau peut implémenter une attaque à double dépense.
Par conséquent, dans Bitcoin, un intervalle de temps est défini entre les blocs extraits d'une durée de 10 minutes. Grâce à cela, le réseau parvient à se synchroniser clairement et la probabilité d'apparition de tels blocs est réduite. Si vous devez augmenter le débit du réseau en augmentant la fréquence de formation de blocs, vous avez besoin d'une solution différente.
Fantôme
La première solution de ce type a été le protocole GWOST PoW. Sa version simplifiée est utilisée sur la plateforme Ethereum.
Dans ce cas, l'attaquant peut tirer sa chaîne (marquée en rouge sur la figure) et la faire la plus longue, mais elle ne gagnera pas. Les utilisateurs honnêtes suivront la chaîne qu'ils ont construite auparavant.
Les utilisateurs honnêtes dans ce cas peuvent avoir deux chaînes. Le plus long (1B-2D-3F-4C-5B), mais il sera plus court que la chaîne de l'attaquant. La particularité de GHOST est que l'algorithme ne se concentre pas sur la chaîne la plus longue, mais sur le nombre de blocs dans l'arbre formé par la chaîne actuelle. Il prend en compte non seulement la longueur de la chaîne elle-même, mais également les blocs à différentes hauteurs. Ainsi, le résultat n'est pas une chaîne linéaire, mais un arbre. Le nombre de blocs qui s'y trouvent est pris en compte.
Si vous regardez la chaîne 1B-2C-3D-4B, les blocs d'accompagnement 3E et 3C sont visibles. Par le nombre de blocs et le travail dépensé, cette chaîne a la plus grande complexité et elle sera considérée comme la principale. Les utilisateurs honnêtes continueront de le considérer comme le principal, malgré les tentatives de l'attaquant pour attaquer le réseau. Dans le consensus traditionnel de Nakamoto, une telle attaque aurait réussi, mais elle ne représente aucune menace pour GHOST.
Néanmoins, l'inconvénient de GHOST est le fait qu'une partie des blocs est toujours perdue. Dans ce cas, la chaîne 2D-3F-4C-5B sera toujours supprimée. Par conséquent, la question de la suppression de blocs d'utilisateurs honnêtes reste ouverte.
SPECTRE et FANTÔME
Afin d'augmenter la fréquence de formation de blocs et de résoudre le problème de la suppression de blocs d'utilisateurs honnêtes, deux autres protocoles PoW ont été proposés: SPECTRE et PHANTOM.
Ils n'utilisent même plus une structure arborescente, mais le soi-disant graphe acyclique dirigé (DAG). Dans ce cas, le validateur inclut des pointeurs vers des blocs qui ne sont pas encore référencés par d'autres validateurs dans l'en-tête de son bloc, au moins dans l'état de réseau qu'il voit à l'heure actuelle, et envoie le bloc plus loin.
Par conséquent, une structure est obtenue dans laquelle tous les blocs que les validateurs voient au moment actuel sont inclus. Ici, la puissance minière des utilisateurs honnêtes n'est pas du tout perdue. De plus, il offre une bande passante réseau élevée et un haut niveau de sécurité. L'avantage de cette approche est le fait que le système est vraiment décentralisé.
Comparons les fonctionnalités du réseau Bitcoin et du réseau qui fonctionne en utilisant les protocoles SPECTRE et PHANTOM. Si nous parlons de la situation actuelle du réseau Bitcoin, il vaut la peine d'accorder une grande importance aux pools de minage. Dans le Bitcoin moderne, 144 blocs sont libérés par jour. C'est ce chiffre qui peut être obtenu si le nombre de minutes en jours est divisé par 10. Il est tout à fait possible que le valideur ait acheté l'équipement, payé l'électricité pendant longtemps, mais cela n'a pas fonctionné pour générer l'unité, et pendant ce temps l'équipement était obsolète et utilisé plus aucun sens. Pour éviter cette situation, les validateurs entrepreneuriaux sont combinés dans des pools de minage. La plupart des pools de minage ont une avance (entreprise / organisation), ce qui incline le Bitcoin moderne à centraliser le processus de validation de nouvelles transactions.
Dans le cas de SPECTRE et PHANTOM, les pools de minage ne sont pas du tout nécessaires. Si nous établissons un parallèle avec le réseau Bitcoin moderne, chaque utilisateur du réseau qui utilise les protocoles SPECTRE et PHANTOM a une chance de libérer un bloc par jour. Ainsi, le besoin de pools de minage disparaît généralement et nous arrivons à un réseau vraiment décentralisé.
, SPECTRE PHANTOM , .
BFT-
, – BFT- (Byzantine Fault Tolerance).
, 80- XX . , - . , . , . , , , , . - , . . , .
BFT- . , , . . , , . , . : .
, ⅔ . BFT- , . BFT- , .
BFT-. , , , , , , Genesis . , . BFT- .
BFT-
Practical BFT
, , Practical BFT. 1999 . . , . . , . , ⅔ .
⅔ , .
, , , , . , , , , . , , , . .
, , DoS- .
HoneyBadger BFT
HoneyBadger BFT . , , . . HoneyBadger : RBC (Reliable broadcast) BA (Byzantine Agreement).
RBC- . , , ⅔ . BA- , .
. , , . . : - , . , , .
Algorand Hashgraph.
Algorand
Algorand 2017 . BFT-, , , . , .
, , , ⅔ , ⅔ . , « » (DoS-). , , adaptive corruption.
, , . , ( , ⅔). .
BFT-, safety persistence. .
, liveness, , . , , ( ) . . , .
Hashgraph
Hashgraph . , , , , .
, : «», , , .
Hashgraph , , , . . , Algorand, . Hashgraph safety liveness, . , .
, , , , . ⅔ , .
BFT
BFT-. . . , ⅔ . , Algorand Hashgraph, .
: permissioned . , . , . , .
permissionless , . . .
Distributed Lab , .– ?, , . : Algorand Hashgraph BFT-, PoS- Ouroboros. 2018 PHANTOM. .
– Ouroboros , , , ?grinding-, . Ouroboros persistence liveness: , , . , , , .
persistence . , , MPC . , . , MPC , , , . . - , , . . «» ( ), .
– , ?, . . PHANTOM, SPECTRE Ouroboros.
, .
– PHANTOM SPECTRE, ? .PHANTOM SPECTRE . , . PHANTOM SPECTRE , . , . , . , , , .
– BFT -?. PBFT, -, . Algorand Hashgraph, .
– PBFT ?( ) . , , , .
– , Algorand – DPoS (Delegated Proof-of-stake), . Delegated Proof-of-stake , . . Algorand, , .
– , ?SPECTRE PHANTOM – . SPECTRE , .