Résumé

Un grand livre public est une séquence de données infalsifiables qui peuvent être lues et complétées par tout le monde. Les grands livres publics ont des utilisations innombrables et convaincantes. Ils peuvent sécuriser, à la vue de tous, toutes sortes des transactions — telles que les titres, les ventes et les paiements — dans l'ordre exact dans lequel elles se produisent. Les registres publics non seulement freinent la corruption, mais permettent également des applications très sophistiquées, telles que crypto-monnaies et smart contracts. Ils sont en passe de révolutionner la façon dont une société démocratique fonctionne. Toutefois, tels qu’ils sont actuellement mis en œuvre, ils évoluent mal et ne peuvent pas réaliser leur potentiel. Algorand est un moyen véritablement démocratique et efficace de mettre en œuvre un grand livre public. Contrairement aux précédents implémentations basées sur une preuve de travail, cela nécessite une quantité négligeable de calculs, et génère un historique de transactions qui ne « bifurquera » pas avec une probabilité extrêmement élevée. Algorand est basé sur un accord byzantin (un nouveau et ultra rapide) de transmission de messages. Par souci de concrétisation, nous décrirons Algorand uniquement comme une plateforme monétaire.

Introduction

L'argent devient de plus en plus virtuel. On estime qu'environ 80 % de la population américaine les dollars n’existent aujourd’hui que sous forme d’écritures comptables [5]. D’autres instruments financiers emboîtent le pas. Dans un monde idéal, dans lequel nous pourrions compter sur une entité centrale universellement fiable, immunisée Face à toutes les cyberattaques possibles, l’argent et les autres transactions financières pourraient être uniquement électroniques. Malheureusement, nous ne vivons pas dans un tel monde. En conséquence, les crypto-monnaies décentralisées, telles que comme Bitcoin [29], et des systèmes « smart contract », tels que Ethereum, ont été proposés [4]. À le cœur de ces systèmes est un registre partagé qui enregistre de manière fiable une séquence de transactions, ∗Il s'agit de la version la plus formelle (et asynchrone) de l'article ArXiv du deuxième auteur [24], un article lui-même basé sur celui de Gorbounov et Micali [18]. Les technologies de Algorand font l’objet des éléments suivants demandes de brevet : US62/117 138 US62/120 916 US62/142 318 US62/218 817 US62/314 601 PCT/US2016/018300 US62/326 865 62/331 654 US62/333 340 US62/343 369 US62/344 667 US62/346 775 US62/351 011 US62/653 482 US62/352 195 US62/363 970 US62/369 447 US62/378 753 US62/383 299 US62/394 091 US62/400 361 US62/403 403 US62/410 721 US62/416 959 US62/422 883 US62/455 444 US62/458 746 US62/459 652 US62/460 928 US62/465 931aussi variés que les paiements et les contrats, de manière inviolable. La technologie de choix pour garantir cette inviolabilité est le blockchain. Les blockchains sont à l'origine d'applications telles que les crypto-monnaies [29], les applications financières [4] et l'Internet des objets [3]. Plusieurs techniques pour gérer les grands livres basés sur blockchain ont été proposés : preuve de travail [29], preuve de mise [2], tolérance aux pannes byzantine pratique [8], ou une combinaison. Cependant, à l’heure actuelle, la gestion des grands livres peut s’avérer inefficace. Par exemple, proof-of-work de Bitcoin L'approche (basée sur le concept original de [14]) nécessite une grande quantité de calculs et est un gaspillage et évolue mal [1]. De plus, il concentre de facto le pouvoir entre très peu de mains. Nous souhaitons donc proposer une nouvelle méthode pour mettre en place un grand livre public offrant la la commodité et l’efficacité d’un système centralisé géré par une autorité de confiance et inviolable, sans les inefficacités et les faiblesses des mises en œuvre décentralisées actuelles. Nous appelons notre approche Algorand, car nous utilisons le hasard algorithmique pour sélectionner, sur la base du grand livre construit jusqu'à présent, un ensemble de vérificateurs chargés de construire le prochain bloc de transactions valides. Naturellement, nous veillons à ce que ces sélections soient prouvées à l'abri de toute manipulation et imprévisibles jusqu'à ce que la dernière minute, mais aussi qu'ils sont finalement universellement clairs. L’approche de Algorand est assez démocratique, dans le sens où ni en principe ni de facto elle crée différentes classes d'utilisateurs (comme « mineurs » et « utilisateurs ordinaires » dans Bitcoin). Dans Algorand « tout le pouvoir appartient à l’ensemble de tous les utilisateurs ». Une propriété notable de Algorand est que son historique de transactions ne peut bifurquer qu'avec de très petites probabilité (par exemple, un sur un billion, c'est-à-dire, ou même 10−18). Algorand peut également répondre à certaines questions juridiques et les préoccupations politiques. L'approche Algorand s'applique aux blockchain et, plus généralement, à toute méthode de génération une séquence de blocs inviolables. Nous avons en fait proposé une nouvelle méthode, alternative et plus efficace que les blockchains — qui peuvent présenter un intérêt indépendant. 1.1 Hypothèse de Bitcoin et problèmes techniques Bitcoin est un système très ingénieux et a inspiré de nombreuses recherches ultérieures. Pourtant, il est également problématique. Résumons son hypothèse sous-jacente et ses problèmes techniques - qui sont en fait partagés par pratiquement toutes les crypto-monnaies qui, comme Bitcoin, sont basées sur proof-of-work. Pour ce résumé, il suffit de rappeler que, dans Bitcoin, un utilisateur peut posséder plusieurs clés publiques d'un système de signature numérique, que l'argent est associé à des clés publiques et qu'un paiement est un signature numérique qui transfère une certaine somme d'argent d'une clé publique à une autre. Essentiellement, Bitcoin organise tous les paiements traités dans une chaîne de blocs, B1, B2, . . ., chacun étant composé de plusieurs paiements, tels que tous les paiements de B1, pris dans n'importe quel ordre, suivis de ceux de B2, dans n'importe quel ordre, etc., constituent une séquence de paiements valides. Chaque bloc est généré en moyenne toutes les 10 minutes. Cette séquence de blocs est une chaîne, car elle est structurée de manière à garantir que tout changement, même dans un seul bloc, s'infiltre dans tous les blocs suivants, ce qui facilite la détection de toute altération de l'historique des paiements. (Comme nous le verrons, ceci est réalisé en incluant dans chaque bloc un code cryptographique. hash de la précédente.) Une telle structure de bloc est appelée blockchain. Hypothèse : majorité honnête de la puissance de calcul Bitcoin suppose qu'aucun malware entité (ni une coalition d'entités malveillantes coordonnées) contrôle la majorité des ressources informatiques. puissance consacrée à la génération de blocs. Une telle entité serait en effet en mesure de modifier le blockchain,et ainsi réécrire l'historique des paiements, à sa guise. Il pourrait notamment effectuer un paiement \(\wp\), obtenir les prestations versées, puis « effacer » toute trace de \(\wp\). Problème technique 1 : Déchets informatiques L'approche proof-of-work de Bitcoin pour bloquer la génération nécessite une quantité extraordinaire de calculs. Actuellement, avec seulement quelques centaines des milliers de clés publiques dans le système, les 500 superordinateurs les plus puissants ne peuvent que rassembler seulement 12,8 % de la puissance de calcul totale requise des joueurs Bitcoin. Ceci la quantité de calcul augmenterait considérablement si davantage d’utilisateurs rejoignaient le système. Problème technique 2 : Concentration du pouvoir Aujourd'hui, en raison de la quantité exorbitante de calcul requis, un utilisateur essayant de générer un nouveau bloc en utilisant un bureau ordinaire (sans parler d'un téléphone portable), s'attend à perdre de l'argent. En effet, pour calculer un nouveau bloc avec un ordinateur ordinaire, le coût attendu de l’électricité nécessaire pour alimenter le calcul dépasse la récompense attendue. En utilisant uniquement des pools d'ordinateurs spécialement construits (qui ne font rien d'autre que « extraire de nouveaux blocs »), un pourrait espérer réaliser un profit en générant de nouveaux blocs. Ainsi, il existe aujourd’hui de facto deux classes d'utilisateurs disjointes : utilisateurs ordinaires, qui effectuent uniquement des paiements, et pools miniers spécialisés, qui recherche uniquement de nouveaux blocs. Il ne faut donc pas s'étonner que, depuis peu, la puissance de calcul totale des blocs La génération se situe dans seulement cinq pools. Dans de telles conditions, l’hypothèse selon laquelle une majorité des la puissance de calcul est honnête et devient moins crédible. Problème technique 3 : Ambiguïté Dans Bitcoin, le blockchain n'est pas nécessairement unique. En effet sa dernière partie se divise souvent : le blockchain peut être —disons— B1, . . . , Bk, B′ k+1, B′ k+2, selon un utilisateur, et B1, . . . , Bk, B' k+1,B' k+2, B'' k+3 selon un autre utilisateur. Ce n'est qu'après plusieurs blocs été ajouté à la chaîne, peut-on être raisonnablement sûr que les k + 3 premiers blocs seront les mêmes pour tous les utilisateurs. Ainsi, on ne peut pas compter d'emblée sur les paiements contenus dans le dernier bloc de la chaîne. Il est plus prudent d'attendre et de voir si le bloc s'enfonce suffisamment profondément dans le blockchain et donc suffisamment stable. Par ailleurs, des préoccupations en matière d’application de la loi et de politique monétaire ont également été soulevées à propos de Bitcoin.1 1.2 Algorand, en bref Paramètre Algorand travaille dans un environnement très difficile. En bref, (a) Environnements sans autorisation et autorisés. Algorand fonctionne efficacement et en toute sécurité, même dans un environnement totalement sans autorisation, où de nombreux utilisateurs arbitrairement sont autorisés à rejoindre le système à tout moment, sans aucun contrôle ni autorisation d’aucune sorte. Bien sûr, Algorand fonctionne encore mieux dans un environnement autorisé. 1Le (pseudo) anonymat offert par les paiements Bitcoin peut être utilisé à mauvais escient à des fins de blanchiment d'argent et/ou de financement. d’individus criminels ou d’organisations terroristes. Les billets de banque traditionnels ou les lingots d'or, qui offrent en principe une parfaite l'anonymat, devrait poser le même défi, mais le caractère physique de ces monnaies ralentit considérablement l'argent transferts, afin de permettre un certain degré de surveillance par les organismes chargés de l'application de la loi. La capacité « d’imprimer de l’argent » est l’un des pouvoirs fondamentaux d’un État-nation. En principe donc, le massif l’adoption d’une monnaie flottante de manière indépendante pourrait restreindre ce pouvoir. Cependant, à l'heure actuelle, Bitcoin est loin d'être une menace pour les politiques monétaires gouvernementales et, en raison de ses problèmes d’évolutivité, elle ne le sera peut-être jamais.(b) Environnements très conflictuels. Algorand résiste à un Adversaire très puissant, qui peut (1) corrompre instantanément tout utilisateur de son choix, à tout moment, à condition que, de manière environnement sans autorisation, les 2/3 de l’argent du système appartiennent à un utilisateur honnête. (Dans un environnement autorisé, quel que soit l'argent, il suffit que les 2/3 des utilisateurs soient honnêtes.) (2) contrôler totalement et coordonner parfaitement tous les utilisateurs corrompus ; et (3) planifier la livraison de tous les messages, à condition que chaque message soit envoyé par un utilisateur honnête atteint 95% des utilisateurs honnêtes dans un temps \(\lambda\)m, qui dépend uniquement de la taille de m. Propriétés principales Malgré la présence de notre puissant adversaire, en Algorand • La quantité de calcul requise est minime. Essentiellement, quel que soit le nombre d'utilisateurs présent dans le système, chacun des mille cinq cents utilisateurs doit effectuer au maximum quelques secondes de calcul. • Un nouveau bloc est généré en moins de 10 minutes, et ne quittera de facto jamais le blockchain. Par exemple, en prévision, le temps nécessaire pour générer un bloc dans le premier mode de réalisation est inférieur que Λ + 12,4\(\lambda\), où Λ est le temps nécessaire à la propagation d'un bloc, dans un potin peer-to-peer mode, quelle que soit la taille de bloc que l'on choisit, et \(\lambda\) est le temps nécessaire pour propager 1 500 messages de 200 Blongs. (Puisque dans un système véritablement décentralisé, Λ est essentiellement une latence intrinsèque, Algorand le facteur limitant dans la génération de blocs est la vitesse du réseau.) Le deuxième mode de réalisation a en fait été testé expérimentalement (par ?), indiquant qu'un bloc est généré en moins de 40 secondes. De plus, le blockchain de Algorand ne peut se diviser qu'avec une probabilité négligeable (c'est-à-dire moins d'un en billions), et ainsi les utilisateurs peuvent s'appuyer sur les paiements contenus dans un nouveau bloc dès que le Le bloc apparaît. • Tout le pouvoir appartient aux utilisateurs eux-mêmes. Algorand est un véritable système distribué. En particulier, il n'y a pas d'entités exogènes (comme les « mineurs » dans Bitcoin), qui peuvent contrôler quelles transactions sont reconnus. Techniques de Algorand. 1. Un nouveau et rapide protocole d’accord byzantin. Algorand génère un nouveau bloc via un nouveau protocole d'accord byzantin (BA) binaire cryptographique, de transmission de messages, BA⋆. Protocole BA⋆ non seulement satisfait quelques propriétés supplémentaires (dont nous parlerons bientôt), mais est également très rapide. En gros, sa version à entrée binaire consiste en une boucle en 3 étapes, dans laquelle un joueur envoie un seul message mi à tous les autres joueurs. Exécuté dans un réseau complet et synchrone, avec plus que 2/3 des joueurs sont honnêtes, avec une probabilité > 1/3, après chaque boucle le protocole se termine par accord. (Nous soulignons que le protocole BA⋆ satisfait à la définition originale de l'accord byzantin de Pease, Shostak et Lamport [31], sans aucun affaiblissement.) Algorand exploite ce protocole BA binaire pour parvenir à un accord, dans nos différentes communications modèle, sur chaque nouveau bloc. Le bloc convenu est ensuite certifié, via un nombre prescrit de signature numérique des vérificateurs appropriés et propagée à travers le réseau. 2. Tri cryptographique. Bien que très rapide, le protocole BA⋆ gagnerait à être développé davantage. vitesse lorsqu'il est joué par des millions d'utilisateurs. En conséquence, Algorand choisit les joueurs de BA⋆pour êtreun sous-ensemble beaucoup plus petit de l’ensemble de tous les utilisateurs. Pour éviter un autre type de concentration du pouvoir problème, chaque nouveau bloc Br sera construit et convenu, via une nouvelle exécution de BA⋆, par un ensemble distinct de vérificateurs sélectionnés, SV r. En principe, sélectionner un tel ensemble pourrait être aussi difficile que en sélectionnant Br directement. Nous résolvons ce problème potentiel par une approche que nous appelons, englobant la suggestion perspicace de Maurice Herlihy, le tri cryptographique. Le tri est la pratique de sélectionner des responsables au hasard parmi un large ensemble de personnes éligibles [6]. (Le tri était pratiqué à travers les siècles : par exemple par les républiques d’Athènes, de Florence et de Venise. Dans la justice moderne systèmes, la sélection aléatoire est souvent utilisée pour choisir les jurys. Un échantillonnage aléatoire a également été récemment préconisé pour les élections par David Chaum [9].) Dans un système décentralisé, bien sûr, choisir le les pièces aléatoires nécessaires pour sélectionner aléatoirement les membres de chaque ensemble de vérificateurs SV r sont problématiques. Nous recourons donc à la cryptographie afin de sélectionner chaque ensemble de vérificateurs, parmi la population de tous les utilisateurs, d'une manière garantie automatique (c'est-à-dire ne nécessitant aucun échange de message) et aléatoire. Essentiellement, nous utilisons une fonction cryptographique pour déterminer automatiquement, à partir du bloc précédent Br−1, un utilisateur, le leader, chargé de proposer le nouveau bloc Br, et l'ensemble vérificateur SV r, dans chargé de parvenir à un accord sur le bloc proposé par le leader. Étant donné que des utilisateurs malveillants peuvent affecter la composition de Br−1 (par exemple, en choisissant certains de ses paiements), nous construisons et utilisons spécialement entrées supplémentaires afin de prouver que le leader du rème bloc et l'ensemble de vérificateurs SV r sont bien choisi au hasard. 3. La quantité (graines) Qr. On utilise le dernier bloc Br−1 du blockchain afin de déterminer automatiquement le prochain ensemble de vérificateurs et le leader en charge de la construction du nouveau bloc Frère. Le défi de cette approche est que, en choisissant simplement un paiement légèrement différent dans le Au tour précédent, notre puissant adversaire acquiert un énorme contrôle sur le prochain leader. Même s'il ne contrôlant que 1/1000 des joueurs/argent dans le système, il pouvait s'assurer que tous les dirigeants sont malveillant. (Voir la section 4.1 sur l'intuition.) Ce défi est au cœur de toutes les approches proof-of-stake, et, à notre connaissance, ce problème n’a pas encore été résolu de manière satisfaisante. Pour relever ce défi, nous construisons délibérément et mettons continuellement à jour un système distinct et soigneusement quantité définie, Qr, qui est prouvablement, non seulement imprévisible, mais aussi non influentable, par notre puissant Adversaire. Nous pouvons faire référence à Qr comme à la rème graine, car c'est à partir de Qr que Algorand sélectionne, via un tri cryptographique secret, tous les utilisateurs qui joueront un rôle particulier dans la génération du rème bloc. 4. Tri cryptographique secret et informations d'identification secrètes. Utiliser de manière aléatoire et sans ambiguïté le dernier bloc actuel, Br−1, afin de choisir l'ensemble des vérificateurs et le leader en charge la construction du nouveau bloc Br ne suffit pas. Puisque Br−1 doit être connu avant de générer Br, la dernière quantité non influençable Qr−1 contenue dans Br−1 doit également être connue. En conséquence, donc sont les vérificateurs et le leader en charge du calcul du bloc Br. Ainsi, notre puissant Adversaire pourrait immédiatement tous les corrompre, avant qu'ils s'engagent dans une discussion sur Br, afin d'obtenir contrôle total sur le bloc qu'ils certifient. Pour éviter ce problème, les dirigeants (et en fait les vérificateurs aussi) apprennent secrètement leur rôle, mais peuvent calculer un titre approprié, capable de prouver à tous ceux qui jouent effectivement ce rôle. Quand un utilisateur se rend compte en privé qu'il est le leader du bloc suivant, il assemble d'abord secrètement son propre nouveau bloc proposé, puis le diffuse (afin qu'il puisse être certifié) avec son propre bloc accréditation. De cette façon, même si l’Adversaire comprendra immédiatement qui est le chef du prochain le bloc est, et bien qu'il puisse le corrompre immédiatement, il sera trop tard pour que l'Adversaire puisse le corrompre. influencer le choix d’un nouveau bloc. En effet, il ne peut plus « rappeler » le message du leaderqu’un gouvernement puissant ne peut remettre dans la bouteille un message diffusé de manière virale par WikiLeaks. Comme nous le verrons, nous ne pouvons pas garantir l'unicité du leader, ni que chacun sache avec certitude qui est le leader. c'est, y compris le leader lui-même ! Mais, en Algorand, des progrès sans ambiguïté seront garantis. 5. Remplaçabilité du joueur. Après avoir proposé un nouveau bloc, le leader pourrait tout aussi bien « mourir » (ou être corrompu par l'Adversaire), car son travail est accompli. Mais, pour les vérificateurs de SV r, les choses sont moins simple. En effet, étant en charge de certifier le nouveau bloc Br avec suffisamment de signatures, ils doivent d'abord obtenir un accord byzantin sur le bloc proposé par le leader. Le problème est que, Quelle que soit son efficacité, BA⋆ nécessite plusieurs étapes et l'honnêteté de > 2/3 de ses joueurs. C’est un problème car, pour des raisons d’efficacité, l’ensemble des joueurs de BA⋆est constitué du petit ensemble SV r sélectionné au hasard parmi l’ensemble de tous les utilisateurs. Ainsi, notre puissant Adversaire, bien qu'incapable corrompre 1/3 de tous les utilisateurs, peut certainement corrompre tous les membres de SV r ! Heureusement, nous prouverons que le protocole BA⋆, exécuté en propageant des messages de manière peer-to-peer, est remplaçable par le joueur. Cette nouvelle exigence signifie que le protocole correctement et parvient efficacement à un consensus même si chacune de ses étapes est exécutée par une personne totalement nouvelle et aléatoire. et un ensemble de joueurs sélectionnés indépendamment. Ainsi, avec des millions d'utilisateurs, chaque petit groupe d'acteurs associé à une étape de BA⋆ a très probablement une intersection vide avec l’ensemble suivant. De plus, les ensembles d’acteurs des différents niveaux de BA⋆auront probablement des valeurs totalement différentes. cardinalités. De plus, les membres de chaque groupe ne savent pas qui sera le prochain groupe de joueurs. être, et ne passer secrètement aucun état interne. La propriété du joueur remplaçable est en fait cruciale pour vaincre le dynamique et très puissant Adversaire que nous envisageons. Nous pensons que les protocoles de joueurs remplaçables s'avéreront cruciaux dans de nombreux contextes et applications. En particulier, ils seront cruciaux pour exécuter de manière sécurisée de petits sous-protocoles intégré dans un univers plus vaste de joueurs avec un adversaire dynamique, qui, étant capable de corrompre même une petite fraction du total des joueurs, n'a aucune difficulté à corrompre tous les joueurs du plus petit sous-protocole. Une propriété/technique supplémentaire : l’honnêteté paresseuse Un utilisateur honnête suit ses prescriptions instructions, qui incluent être en ligne et exécuter le protocole. Depuis, Algorand n’a que modestement exigence de calcul et de communication, être en ligne et exécuter le protocole « dans le contexte » n’est pas un sacrifice majeur. Bien sûr, quelques « absences » parmi les joueurs honnêtes, comme ceux en raison d'une perte soudaine de connectivité ou de la nécessité d'un redémarrage, sont automatiquement tolérés (car nous pouvons toujours considérer que si peu de joueurs sont temporairement malveillants). Signalons cependant que Algorand peut être simplement adapté pour fonctionner dans un nouveau modèle, dans lequel des utilisateurs honnêtes doivent être hors ligne la plupart du temps. Notre nouveau modèle peut être présenté de manière informelle comme suit. Honnêteté paresseuse. En gros, un utilisateur i est paresseux mais honnête si (1) il suit toutes les instructions prescrites instructions, lorsqu'il lui est demandé de participer au protocole, et (2) il lui est demandé de participer au protocole que rarement et avec un préavis approprié. Avec une notion d’honnêteté aussi détendue, nous pouvons être encore plus confiants dans le fait que les gens honnêtes seront à portée de main lorsque nous en avons besoin, et Algorand garantissent que, lorsque tel est le cas, Le système fonctionne en toute sécurité même si, à un moment donné, la majorité des joueurs participants sont malveillants.1.3 Travail étroitement lié Les approches de preuve de travail (comme les [29] et [4] cités) sont assez orthogonales aux nôtres. Ainsi sont les approches basées sur un accord byzantin de transmission de messages ou sur une tolérance aux pannes byzantine pratique (comme le [8] cité). En effet, ces protocoles ne peuvent pas être exécutés parmi l'ensemble des utilisateurs et ne peuvent pas, dans notre modèle, être limité à un nombre suffisamment restreint d’utilisateurs. En fait, notre puissant adversaire, mon corrompt immédiatement tous les utilisateurs impliqués dans un petit ensemble chargé d’exécuter réellement un protocole BA. Notre approche pourrait être considérée comme liée à la preuve d’enjeu [2], dans le sens où le « pouvoir » des utilisateurs dans la construction de blocs est proportionnel à l’argent qu’ils possèdent dans le système (par opposition à – disons – à l’argent qu’ils ont mis en « séquestre »). L'article le plus proche du nôtre est le Sleepy Consensus Model de Pass et Shi [30]. Pour éviter le calculs lourds requis dans l'approche proof-of-work, leur article s'appuie sur (et aimablement crédits) Le tri cryptographique secret de Algorand. Avec cet aspect crucial en commun, plusieurs des différences significatives existent entre nos articles. En particulier, (1) Leur paramétrage est uniquement autorisé. En revanche, Algorand est également un système sans autorisation. (2) Ils utilisent un protocole de style Nakamoto, et donc leurs forks blockchain fréquemment. Bien que en se dispensant de proof-of-work, dans leur protocole, il est demandé à un leader secrètement sélectionné d'allonger le valide le plus longtemps (dans un sens plus riche) blockchain. Ainsi, les fourchettes sont inévitables et il faut attendre que le bloc est suffisamment « profond » dans la chaîne. En effet, pour atteindre ses objectifs face à un adversaire capables de corruptions adaptatives, ils nécessitent qu'un bloc soit profond en poly(N), où N représente le nombre total d'utilisateurs dans le système. Notez que, même en supposant qu'un bloc puisse être produit en une minute, s'il y avait N = 1 million d'utilisateurs, il faudrait alors attendre environ 2 millions d'années pour un bloc pour devenir N 2 de profondeur, et pendant environ 2 ans pour qu'un bloc devienne N de profondeur. En revanche, Les fourches blockchain de Algorand n'ont qu'une probabilité négligeable, même si l'Adversaire corrompt utilisateurs immédiatement et de manière adaptative, et ses nouveaux blocs peuvent être immédiatement fiables. (3) Ils ne traitent pas les accords byzantins individuels. En un sens, ils garantissent seulement « un éventuel consensus sur une séquence croissante de valeurs ». Il s'agit plutôt d'un protocole de réplication d'état. qu'un BA, et ne peut pas être utilisé pour parvenir à un accord byzantin sur une valeur individuelle d'intérêt. En revanche, Algorand peut également être utilisé une seule fois, si vous le souhaitez, pour permettre à des millions d'utilisateurs de rapidement parvenir à un accord byzantin sur une valeur d’intérêt spécifique. (4) Ils nécessitent des horloges faiblement synchronisées. Autrement dit, les horloges de tous les utilisateurs sont légèrement décalées. δ. En revanche, dans Algorand, les horloges doivent seulement avoir (essentiellement) la même « vitesse ». (5) Leur protocole fonctionne avec des utilisateurs paresseux mais honnêtes ou avec une majorité honnête d'utilisateurs en ligne. Ils remercient gentiment Algorand d'avoir soulevé la question des utilisateurs honnêtes qui se déconnectent en masse, et d'avoir soulevé la question de la déconnexion massive des utilisateurs honnêtes. en mettant en avant le modèle de l’honnêteté paresseuse en réponse. Leur protocole ne fonctionne pas seulement chez les paresseux modèle d'honnêteté, mais aussi dans leur modèle contradictoire endormi, où un adversaire choisit quels utilisateurs sont en ligne et qui sont hors ligne, à condition que, à tout moment, la majorité des utilisateurs en ligne soient honnêtes.2 2La version originale de leur article ne considérait en fait que la sécurité dans leur modèle endormi et contradictoire. Le version originale de Algorand, qui précède la leur, envisageait également explicitement de supposer qu'une majorité donnée des les joueurs en ligne sont toujours honnêtes, mais l’ont explicitement exclu de toute considération, en faveur du modèle d’honnêteté paresseuse. (Par exemple, si à un moment donné la moitié des utilisateurs honnêtes choisissent de se déconnecter, alors la majorité des utilisateurs en ligne peut très bien être malveillant. Ainsi, pour éviter que cela ne se produise, l'Adversaire devrait forcer la plupart de ses joueurs corrompus se déconnectent également, ce qui est clairement contraire à son propre intérêt.) Notez qu'un protocole avec une majorité La méthode des joueurs paresseux mais honnêtes fonctionne très bien si la majorité des utilisateurs en ligne sont toujours malveillants. Il en est ainsi, parce que un nombre suffisant d’acteurs honnêtes, sachant qu’ils vont jouer un rôle crucial à un moment donné, éliront ils ne peuvent pas se déconnecter dans ces moments-là, et ils ne peuvent pas non plus être forcés hors ligne par l'Adversaire, puisqu'il ne sait pas qui est le des joueurs honnêtes cruciaux pourraient l’être.(6) Ils nécessitent une majorité simple et honnête. En revanche, la version actuelle de Algorand nécessite une majorité honnête des 2/3. Un autre article proche de nous est Ouroboros : A Provably Secure Proof-of-Stake Blockchain Protocol, par Kiayias, Russell, David et Oliynykov [20]. Leur système est également apparu après le nôtre. C'est aussi utilise le tri cryptographique pour se passer de preuve de travail de manière prouvable. Cependant, leur Le système est, encore une fois, un protocole de style Nakamoto, dans lequel les forks sont à la fois inévitables et fréquents. (Cependant, dans leur modèle, les blocages n’ont pas besoin d’être aussi profonds que dans le modèle du consensus endormi.) De plus, leur système repose sur les hypothèses suivantes : selon les mots des auteurs eux-mêmes, « (1) le le réseau est hautement synchrone, (2) la majorité des parties prenantes sélectionnées sont disponibles selon les besoins pour participer à chaque époque, (3) les parties prenantes ne restent pas hors ligne pendant de longues périodes, (4) l'adaptabilité des corruptions est soumise à un petit retard qui se mesure en tours linéaires en le paramètre de sécurité. En revanche, Algorand est, avec une écrasante probabilité, sans fourchette, et ne repose sur aucune de ces 4 hypothèses. En particulier, dans Algorand, l'Adversaire est capable de corrompt instantanément les utilisateurs qu'il veut contrôler.

Préliminaires

2.1 Primitives cryptographiques Hachage idéal. Nous nous appuierons sur une fonction cryptographique hash efficacement calculable, H, qui mappe des chaînes arbitrairement longues en chaînes binaires de longueur fixe. Suivant une longue tradition, nous modélisons H comme un oracle aléatoire, essentiellement une fonction mappant chaque chaîne possible s à un oracle aléatoire et chaîne binaire sélectionnée indépendamment (puis fixée), H(s), de la longueur choisie. Dans cet article, H a des sorties de 256 bits. En effet, cette longueur est suffisamment courte pour que le système efficace et suffisamment long pour sécuriser le système. Par exemple, nous voulons que H soit résistant aux collisions. Autrement dit, il devrait être difficile de trouver deux chaînes différentes x et y telles que H(x) = H(y). Lorsque H est un oracle aléatoire avec des sorties de 256 bits, trouver une telle paire de chaînes est en effet difficile. (Essayer au hasard et s'appuyer sur le paradoxe de l'anniversaire nécessiterait 2256/2 = 2128 essais.) Signature numérique. Les signatures numériques permettent aux utilisateurs d'authentifier les informations les uns auprès des autres sans partager aucun partage de clés secrètes. Un schéma de signature numérique se compose de trois étapes rapides algorithmes : un générateur de clé probabiliste G, un algorithme de signature S et un algorithme de vérification V . Étant donné un paramètre de sécurité k, un entier suffisamment élevé, un utilisateur i utilise G pour produire une paire de Clés de k bits (c'est-à-dire chaînes) : une clé pki "publique" et une clé de signature "secrète" correspondante ski. Surtout, un la clé publique ne « trahit » pas la clé secrète correspondante. Autrement dit, même avec la connaissance de pki, non un autre que moi est capable de calculer le ski en moins d'un temps astronomique. L'utilisateur i utilise ski pour signer numériquement les messages. Pour chaque message possible (chaîne binaire) m, je commence par hashes m puis exécute l'algorithme S sur les entrées H(m) et skie de manière à produire la chaîne de k bits sigpki(m) \(\triangleq\)S(H(m), ski) .3 3Puisque H est résistant aux collisions, il est pratiquement impossible qu’en signant m, quelqu’un « signe accidentellement » un autre message m'.La chaîne binaire sigpki(m) est appelée la signature numérique de m de i (par rapport à pki) et peut être plus simplement désigné par sigi(m), lorsque la clé publique pki ressort clairement du contexte. Toute personne connaissant pki peut l'utiliser pour vérifier les signatures numériques produites par i. Plus précisément, sur entre (a) la clé publique pki d'un joueur i, (b) un message m et (c) une chaîne s, c'est-à-dire que i est allégué signature numérique du message m, l'algorithme de vérification V renvoie soit OUI, soit NON. Les propriétés que nous exigeons d'un système de signature numérique sont : 1. Les signatures légitimes sont toujours vérifiées : Si s = sigi(m), alors V (pki, m, s) = Y ES ; et 2. Les signatures numériques sont difficiles à falsifier : sans connaissance du ski, il est temps de trouver une telle chaîne. que V (pki, m, s) = Y ES, pour un message m jamais signé par i, est astronomiquement long. (Suite aux fortes exigences de sécurité de Goldwasser, Micali et Rivest [17], c'est vrai même si l'on peut obtenir la signature de tout autre message.) En conséquence, pour empêcher quiconque de signer des messages en son nom, un joueur doit conserver son signer la clé ski secrète (d'où le terme « clé secrète »), et permettre à quiconque de vérifier les messages s'il signe, j'ai intérêt à faire connaître sa clé pki (d'où le terme « clé publique »). En général, un message m n'est pas récupérable à partir de sa signature sigi(m). Afin de traiter virtuellement avec des signatures numériques qui satisfont à la propriété de « récupérabilité » conceptuellement pratique (c'est-à-dire, pour garantir que le signataire et le message sont facilement calculables à partir d'une signature, nous définissons SIGpki(m) = (je, m, sigpki(m)) et SIGi(m) = (i, m, sigi(m)), si pki est clair. Signature numérique unique. Nous considérons également des schémas de signature numérique (G, S, V ) satisfaisant les propriété supplémentaire suivante. 3. Unicité. Il est difficile de trouver des chaînes pk′, m, s et s′ telles que s ̸= s′ et V (pk′, m, s) = V (pk′, m, s′) = 1. (Notez que la propriété d'unicité s'applique également aux chaînes pk′ qui ne sont pas légitimement générées. clés publiques. Mais en particulier, la propriété d'unicité implique que, si l'on utilisait la générateur de clé spécifié G pour calculer une clé publique pk avec une clé secrète correspondante sk, et connaissant donc sk, il lui serait également essentiellement impossible de trouver deux éléments numériques différents. signatures d'un même message relatif à pk.) Remarques • Des signatures uniques aux fonctions aléatoires vérifiables. Par rapport à un numérique schéma de signature avec la propriété d'unicité, l'application m \(\to\) H (sigi (m)) associe à chaque chaîne possible m, une chaîne unique de 256 bits sélectionnée au hasard, et l'exactitude de cette information la cartographie peut être prouvée étant donné la signature sigi(m). Autrement dit, un schéma idéal de hashing et de signature numérique satisfaisant essentiellement la propriété d'unicité fournir une implémentation élémentaire d'une fonction aléatoire vérifiable, telle qu'introduit et par Micali, Rabin et Vadhan [27]. (Leur mise en œuvre initiale était forcément plus complexe, puisqu'ils ne s'appuyaient pas sur un hashing idéal.)• Trois besoins différents en matière de signatures numériques. Dans Algorand, un utilisateur s'appuie sur le numérique signatures pour (1) Authentifier mes propres paiements. Dans cette application, les clés peuvent être « à long terme » (c'est-à-dire utilisées pour signer de nombreux messages sur une longue période) et proviennent d'un schéma de signature ordinaire. (2) Générer des informations d'identification prouvant que j'ai le droit d'agir à certaines étapes d'un tour r. Ici, les clés peuvent être à long terme, mais doivent provenir d'un schéma satisfaisant la propriété d'unicité. (3) Authentifier le message que j'envoie à chaque étape dans laquelle il agit. Ici, les clés doivent être éphémères (c'est-à-dire détruits après leur première utilisation), mais peuvent provenir d'un schéma de signature ordinaire. • Une simplification à faible coût. Pour plus de simplicité, nous envisageons que chaque utilisateur dispose d'une seule clé à long terme. En conséquence, une telle clé doit provenir d’un schéma de signature ayant l’unicité propriété. Une telle simplicité a un faible coût de calcul. Généralement, en fait, des données numériques uniques les signatures sont légèrement plus coûteuses à produire et à vérifier que les signatures ordinaires. 2.2 Le grand livre public idéalisé Algorand tente d'imiter le système de paiement suivant, basé sur un grand livre public idéalisé. 1. Le statut initial. L'argent est associé à des clés publiques individuelles (générées de manière privée et appartenant aux utilisateurs). Laisser pk1, . . . , pkj les clés publiques initiales et a1, . . . , aj leurs respectifs montants initiaux d'unités monétaires, alors le statut initial est S0 = (pk1, a1), . . . , (pkj, aj) , qui est supposé être de notoriété publique dans le système. 2. Paiements. Soit pk une clé publique ayant actuellement une unité monétaire \(\geq\)0, pk′ une autre clé publique clé, et a′ un nombre non négatif pas supérieur à a. Ensuite, un paiement (valide) \(\wp\)est un paiement numérique signature, relative à pk, spécifiant le transfert d'unités monétaires a′ de pk à pk′, ensemble avec quelques informations complémentaires. En symboles, \(\wp\)= SIGpk(pk, pk′, une′, I, H(I)), où I représente toute information supplémentaire jugée utile mais non sensible (par exemple, l'heure informations et un identifiant de paiement), ainsi que toute information supplémentaire jugée sensible (par exemple, le motif du paiement, éventuellement l'identité des propriétaires du pk et du pk′, etc.). On appelle pk (ou son propriétaire) le payeur, chaque pk′ (ou son propriétaire) le bénéficiaire et a′ le le montant du paiement \(\wp\). Adhésion gratuite via les paiements. Notez que les utilisateurs peuvent rejoindre le système quand ils le souhaitent en générer leurs propres paires de clés publiques/secrètes. En conséquence, la clé publique pk′ qui apparaît dans le paiement \(\wp\)ci-dessus peut être une clé publique nouvellement générée qui n'a jamais « possédé » d'argent avant. 3. Le grand livre magique. Dans le système idéalisé, tous les paiements sont valides et apparaissent dans un format infalsifiable. liste L de séries de paiements « affichées dans le ciel » à la vue de tous : L = PAYER 1, PAYER 2, . . . ,Chaque bloc PAY r+1 est constitué de l'ensemble de tous les paiements effectués depuis l'apparition du bloc PAYER r. Dans le système idéal, un nouveau bloc apparaît après un laps de temps fixe (ou fini). Discussion. • Paiements plus généraux et résultats de transactions non dépensés. Plus généralement, si une clé publique pk possède un montant a, alors un paiement valide \(\wp\)de pk peut transférer les montants a′ 1, un' 2, . . ., respectivement aux touches pk′ 1, pk' 2, . . ., tant que P j'ai j \(\leq\)a. Dans Bitcoin et les systèmes similaires, l'argent détenu par une clé publique pk est séparé en montants, et un paiement \(\wp\)effectué par pk doit transférer un tel montant séparé a dans son intégralité. Si pk souhaite transférer seulement une fraction a′ < a de a vers une autre clé, alors il doit également transférer la solde, le résultat de la transaction non dépensé, vers une autre clé, éventuellement pk lui-même. Algorand fonctionne également avec des clés ayant des montants séparés. Cependant, afin de se concentrer sur nouveaux aspects de Algorand, il est conceptuellement plus simple de s'en tenir à nos formes de paiement les plus simples et des clés auxquelles est associé un montant unique. • Statut actuel. Le schéma idéalisé ne fournit pas directement d’informations sur la situation actuelle. statut du système (c’est-à-dire le nombre d’unités monétaires de chaque clé publique). Ces informations est déductible du Magic Ledger. Dans le système idéal, un utilisateur actif stocke et met à jour en permanence les dernières informations d'état, sinon il devrait le reconstruire, soit à partir de zéro, soit à partir de la dernière fois qu'il l'a fait. l'a calculé. (Dans la prochaine version de cet article, nous augmenterons Algorand afin de permettre son utilisateurs de reconstruire l'état actuel de manière efficace.) • Sécurité et « Confidentialité ». Les signatures numériques garantissent que personne ne peut falsifier un paiement en un autre utilisateur. Dans un paiement \(\wp\), les clés publiques et le montant ne sont pas cachés, mais les clés sensibles informations que je suis. En effet, seul H(I) apparaît dans \(\wp\), et comme H est une fonction hash idéale, H(I) est une valeur aléatoire de 256 bits, et il n'y a donc aucun moyen de savoir ce que j'étais meilleur qu'en simplement le deviner. Pourtant, pour prouver ce que j'étais (par exemple, pour prouver la raison du paiement), le le payeur peut simplement révéler I. L'exactitude du I révélé peut être vérifiée en calculant H(I) et comparer la valeur résultante avec le dernier élément de \(\wp\). En fait, puisque H est résilient aux collisions, il est difficile de trouver une deuxième valeur I′ telle que H(I) = H(I′). 2.3 Notions et notations de base Clés, utilisateurs et propriétaires Sauf indication contraire, chaque clé publique (« clé » en abrégé) est à long terme et relative à un schéma de signature numérique avec la propriété d'unicité. Une clé publique que je rejoint le système lorsqu'une autre clé publique j déjà présente dans le système effectue un paiement à i. Pour la couleur, nous personnifions les clés. Nous appelons une clé i un «il», disons que je suis honnête, que j'envoie et reçoit des messages, etc. L'utilisateur est un synonyme de clé. Quand on veut distinguer une clé de la personne à qui elle appartient, nous utilisons respectivement les termes « clé numérique » et « propriétaire ». Systèmes sans autorisation et avec autorisation. Un système est sans autorisation, si une clé numérique est gratuite pour adhérer à tout moment et un propriétaire peut posséder plusieurs clés numériques ; et c'est autorisé, sinon.Représentation unique Chaque objet dans Algorand a une représentation unique. En particulier, chaque ensemble {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . . .} est ordonné d'une manière prédéfinie : par exemple, en premier lexicographiquement en x, puis en y, etc. Horloges à même vitesse Il n’y a pas d’horloge globale : chaque utilisateur a sa propre horloge. Horloges utilisateur Il n’est en aucun cas nécessaire de les synchroniser. Nous supposons cependant qu’ils ont tous la même vitesse. Par exemple, lorsqu'il est 12h selon l'horloge d'un utilisateur i, il peut être 14h30 selon l'horloge d'un autre utilisateur j, mais quand il sera 12h01 selon l'horloge de i, il sera 2h31 selon à l'horloge de j. Autrement dit, « une minute est la même (suffisamment, essentiellement la même) pour chaque utilisateur ». Tours Algorand est organisé en unités logiques, r = 0, 1, . . ., appelés rondes. Nous utilisons systématiquement des exposants pour indiquer les tours. Pour indiquer qu'une quantité non numérique Q (par exemple, une chaîne, une clé publique, un ensemble, une signature numérique, etc.) fait référence à un tour r, on écrit simplement Qr. Ce n'est que lorsque Q est un véritable nombre (par opposition à une chaîne binaire interprétable comme un nombre) que on écrit Q(r), de sorte que le symbole r ne puisse pas être interprété comme l'exposant de Q. Au (début d'un) tour r > 0, l'ensemble de toutes les clés publiques est PKr et l'état du système est Sr = n je, un(r) je , . . .  : je \(\in\)PKro , où un(r) je est le montant d’argent disponible pour la clé publique i. Notez que PKr est déductible de Sr, et que Sr peut également spécifier d'autres composants pour chaque clé publique i. Pour le tour 0, PK0 est l'ensemble des clés publiques initiales et S0 est l'état initial. PK0 et S0 sont supposés être de notoriété publique dans le système. Pour simplifier, au début du tour r, donc sont PK1, . . . , PKr et S1, . . . , Sr. Dans un tour r, l'état du système passe de Sr à Sr+1 : symboliquement, Tour r : Sr −→Sr+1. Paiements Dans Algorand, les utilisateurs effectuent continuellement des paiements (et les diffusent de la manière décrit à la sous-section 2.7). Un paiement \(\wp\)d'un utilisateur i \(\in\)PKr a le même format et la même sémantique comme dans le Système Idéal. A savoir, \(\wp\)= SIGi(je, je′, une, je, H(I)) . Le paiement \(\wp\)est individuellement valable à un tour r (est un paiement rond-r, en abrégé) si (1) son montant a est inférieur ou égal à a(r) i , et (2) il n’apparaît dans aucun ensemble de paie officiel PAY r′ pour r′ < r. (Comme expliqué ci-dessous, la deuxième condition signifie que \(\wp\)n’est pas encore entré en vigueur. Un ensemble de paiements ronds de i est collectivement valable si la somme de leurs montants est au plus a(r) je. Ensembles de paie Un ensemble de paiements rond-r P est un ensemble de paiements ronds-r tel que, pour chaque utilisateur i, les paiements de je dans P (peut-être aucun) sont collectivement valides. L’ensemble de tous les ensembles de paiements du tour r est PAY(r). Un rond-r le ensemble de pays P est maximal si aucun sur-ensemble de P n'est un ensemble de pays rond-r. Nous suggérons en effet qu'un paiement \(\wp\) spécifie également un tour \(\rho\), \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) , et ne peut être valide à aucun tour en dehors de [\(\rho\), \(\rho\) + k], pour un entier fixe non négatif k.4 4Cela simplifie la vérification si \(\wp\)est devenu « efficace » (c’est-à-dire que cela simplifie la détermination si certains éléments de rémunération PAY r contient \(\wp\). Lorsque k = 0, si \(\wp\)= SIGi(r, i, i′, a, I, H(I)) et \(\wp\)/\(\in\)PAY r, alors je dois soumettre à nouveau \(\wp\).Ensembles de pays officiels Pour chaque tour r, Algorand sélectionne publiquement (de la manière décrite plus loin) un seul ensemble de paiements (éventuellement vide), PAY r, l'ensemble de paiements officiel du tour. (Essentiellement, PAY r représente les paiements ronds qui ont « réellement » eu lieu.) Comme dans le système idéal (et Bitcoin), (1) le seul moyen pour un nouvel utilisateur j d'entrer dans le système doit être destinataire d'un paiement appartenant au système de paie officiel PAY r d'un tour r donné ; et (2) PAY r détermine le statut du tour suivant, Sr+1, à partir de celui du tour en cours, Sr. Symboliquement, PAYER r : Sr −→Sr+1. Plus précisément, 1. l'ensemble des clés publiques du tour r + 1, PKr+1, est constitué de l'union de PKr et de l'ensemble de tous les clés du bénéficiaire qui apparaissent, pour la première fois, dans les paiements de PAY r ; et 2. la somme d'argent a(r+1) je qu'un utilisateur que je possède au tour r + 1 est la somme de ai(r) — c'est-à-dire le montant d'argent que je possédais lors du tour précédent (0 si i ̸\(\in\)PKr) - et la somme des montants payé à moi selon les paiements de PAY r. En somme, comme dans le Système Idéal, chaque statut Sr+1 est déductible de l'historique de paiement précédent : PAYER 0, . . . , PAYER r. 2.4 Blocs et blocs éprouvés Dans Algorand0, le bloc Br correspondant à un tour r précise : r lui-même ; l'ensemble des paiements de tour r, PAYER r; une quantité Qr, à expliquer, et le hash du bloc précédent, H(Br−1). Ainsi, à partir d'un bloc fixe B0, nous avons un blockchain traditionnel : B1 = (1, PAYER 1, Q0, H(B0)), B2 = (2, PAYER 2, Q1, H(B1)), B3 = (3, PAYER 3, Q2, H(B2)), . . . Dans Algorand, l'authenticité d'un bloc est en fait garantie par une information distincte, un « certificat de bloc » CERT r, qui transforme Br en un bloc éprouvé, Br. Le Magic Ledger, donc, est mis en œuvre par la séquence des blocs éprouvés, B1, B2, . . . Discussion Comme nous le verrons, CERT r est constitué d'un ensemble de signatures numériques pour H(Br), celles d'un majorité des membres de SV r, accompagnée d'une preuve que chacun de ces membres appartient effectivement à SV r. Nous pourrions bien sûr inclure les certificats CERT r dans les blocs eux-mêmes, mais nous conceptuellement plus propre pour le garder séparé.) Dans Bitcoin, chaque bloc doit satisfaire une propriété spéciale, c'est-à-dire doit « contenir une solution d'un crypto puzzle », ce qui rend la génération de blocs gourmande en calcul et les deux fourches sont inévitables et pas rare. En revanche, le blockchain de Algorand présente deux avantages principaux : il est généré avec calcul minimal, et il ne se produira pas avec une probabilité extrêmement élevée. Chaque bloc Bi est final en toute sécurité dès qu'il entre dans le blockchain.2.5 Probabilité de défaillance acceptable Pour analyser la sécurité de Algorand, nous spécifions la probabilité, F, avec laquelle nous sommes prêts à accepter que quelque chose ne va pas (par exemple, qu’un ensemble de vérificateurs SV r n’a pas de majorité honnête). Comme dans le cas de la longueur de sortie de la fonction cryptographique hash H, F est également un paramètre. Mais, comme dans ce cas, nous trouvons utile de fixer F à une valeur concrète, afin d’obtenir une approche plus intuitive. comprendre qu'il est effectivement possible, en Algorand, de jouir simultanément d'une sécurité suffisante et une efficacité suffisante. Pour souligner que F est un paramètre qui peut être réglé à volonté, dans le premier et des deuxièmes modes de réalisation que nous définissons respectivement F = 10−12 et F = 10−18 . Discussion Notez que 10−12 est en réalité inférieur à un sur mille milliards, et nous pensons qu'un tel le choix de F est adéquat dans notre application. Soulignons que 10−12 n'est pas la probabilité avec lequel l'Adversaire peut falsifier les paiements d'un utilisateur honnête. Tous les paiements sont numériques signé, et donc, si les signatures numériques appropriées sont utilisées, la probabilité de falsifier un paiement est bien inférieur à 10−12, et est, en fait, essentiellement égal à 0. Le mauvais événement que nous sommes prêts à tolérer avec probabilité F est que les fourches blockchain de Algorand. Notez que, avec notre réglage de F et d'une minute, un fork devrait se produire dans le blockchain de Algorand aussi rarement que (environ) une fois tous les 1,9 millions d’années. En revanche, dans Bitcoin, une fourchette se produit assez souvent. Une personne plus exigeante pourra régler F à une valeur inférieure. A cette fin, dans notre deuxième mode de réalisation nous envisageons de régler F à 10−18. Notez que, en supposant qu'un bloc soit généré chaque seconde, 1018 est le nombre estimé de secondes nécessaires à l'Univers jusqu'à présent : du Big Bang à aujourd'hui le temps. Ainsi, avec F = 10−18, si un bloc est généré en une seconde, il faut s'attendre pour l'âge de l'Univers pour voir une fourchette. 2.6 Le modèle contradictoire Algorand est conçu pour être sécurisé dans un modèle très conflictuel. Expliquons-nous. Utilisateurs honnêtes et malveillants Un utilisateur est honnête s'il suit toutes les instructions de son protocole, et est parfaitement capable d’envoyer et de recevoir des messages. Un utilisateur est malveillant (c'est-à-dire byzantin, dans le sens langage de l'informatique distribuée) s'il peut s'écarter arbitrairement des instructions qui lui sont prescrites. L'adversaire L'Adversaire est un algorithme efficace (techniquement en temps polynomial), personnifié par la couleur, qui peut immédiatement rendre malveillant n'importe quel utilisateur de son choix, à tout moment (sous réserve de uniquement jusqu'à une limite supérieure au nombre d'utilisateurs qu'il peut corrompre). L’Adversaire contrôle totalement et coordonne parfaitement tous les utilisateurs malveillants. Il prend toutes les mesures en leur nom, y compris la réception et l'envoi de tous leurs messages, et peut les laisser s'écarter de leurs instructions prescrites de manière arbitraire. Ou il peut simplement isoler un utilisateur corrompu envoyant et recevoir des messages. Précisons que personne d'autre n'apprend automatiquement qu'un utilisateur i est malveillant, bien que ma méchanceté puisse transparaître dans les actions que l’Adversaire lui fait entreprendre. Cependant, ce puissant adversaire, • Ne dispose pas d'une puissance de calcul illimitée et ne peut pas réussir à forger le numérique signature d'un utilisateur honnête, sauf avec une probabilité négligeable ; et• Ne peut en aucun cas interférer avec les échanges de messages entre utilisateurs honnêtes. De plus, sa capacité à attaquer des utilisateurs honnêtes est limitée par l’une des hypothèses suivantes. Honnêteté, majorité de l'argent Nous considérons un continuum de majorité honnête de l'argent (HMM) hypothèses : à savoir, pour chaque entier non négatif k et réel h > 1/2, HHMk > h : les utilisateurs honnêtes à chaque tour r possédaient une fraction supérieure à h de tout l'argent du jeu le système au tour r −k. Discussion. En supposant que tous les utilisateurs malveillants coordonnent parfaitement leurs actions (comme s'ils étaient contrôlés par une seule entité, l'Adversaire) est une hypothèse plutôt pessimiste. Coordination parfaite entre eux aussi de nombreux individus est difficile à réaliser. Peut-être que la coordination n'a lieu qu'au sein de groupes distincts de joueurs malveillants. Mais comme on ne peut pas être sûr du niveau de coordination des utilisateurs malveillants peut en profiter, mieux vaut prévenir que guérir. Supposer que l’Adversaire puisse corrompre secrètement, dynamiquement et immédiatement les utilisateurs est également pessimiste. Après tout, en réalité, prendre le contrôle total des opérations d’un utilisateur devrait prendre un certain temps. L'hypothèse HMMk > h implique, par exemple, que si un cycle (en moyenne) est mis en œuvre en une minute, la majorité de l'argent d'un tour donné restera entre des mains honnêtes pendant au moins deux heures, si k = 120, et au moins une semaine, si k = 10 000. Notez que les hypothèses HMM et la précédente majorité honnête de la puissance de calcul les hypothèses sont liées dans le sens où, puisque la puissance de calcul peut être achetée avec de l'argent, si les utilisateurs malveillants possèdent la plus grande partie de l’argent, ils peuvent alors obtenir l’essentiel de la puissance de calcul. 2.7 Le modèle de communication Nous envisageons la propagation des messages – c’est-à-dire les « potins entre pairs »5 – comme le seul moyen de communications. Hypothèse temporaire : livraison en temps opportun des messages sur l'ensemble du réseau. Pour Dans la majeure partie de cet article, nous supposons que chaque message propagé atteint presque tous les utilisateurs honnêtes. en temps opportun. Nous supprimerons cette hypothèse dans la section 10, où nous traiterons des réseaux cloisons, qu’elles soient naturelles ou provoquées par des adversaires. (Comme nous le verrons, nous supposons seulement livraison en temps opportun des messages au sein de chaque composant connecté du réseau.) Un moyen concret de capturer la livraison en temps opportun des messages propagés (dans l'ensemble du réseau) est ce qui suit : Pour toute accessibilité \(\rho\) > 95% et taille de message \(\mu\) \(\in\)Z+, il existe \(\lambda\) \(\rho\),\(\mu\) tel que, si un utilisateur honnête propage un message m de \(\mu\)-octets au temps t, alors m atteint, au temps t + \(\lambda\) \(\rho\),\(\mu\), au moins une fraction \(\rho\) des utilisateurs honnêtes. 5Essentiellement, comme dans Bitcoin, lorsqu'un utilisateur propage un message m, chaque utilisateur actif i reçoit m pour la première fois, sélectionne de manière aléatoire et indépendante un nombre suffisamment restreint d'utilisateurs actifs, ses «voisins», auxquels il transmet m, peut-être jusqu'à ce qu'il reçoive un accusé de réception de leur part. La propagation de m se termine lorsqu'aucun utilisateur ne reçoit m pour la première fois.La propriété ci-dessus ne peut cependant pas prendre en charge notre protocole Algorand, sans envisager explicitement et séparément un mécanisme permettant d'obtenir le dernier blockchain — par un autre utilisateur/dépôt/etc. En fait, pour construire un nouveau bloc Br, non seulement un ensemble approprié de vérificateurs doit recevoir en temps opportun le round-r. messages, mais aussi les messages des tours précédents, afin de connaître Br−1 et tous les autres blocs, ce qui est nécessaire pour déterminer si les paiements en Br sont valides. Ce qui suit l’hypothèse suffit. Hypothèse de propagation des messages (MP) : Pour tout \(\rho\) > 95% et \(\mu\) \(\in\)Z+, il existe \(\lambda\) \(\rho\),\(\mu\) tel que, pour tout instant t et tous les messages de \(\mu\)-octets m propagés par un utilisateur honnête avant t −\(\lambda\) \(\rho\),\(\mu\), m est reçu, à l’instant t, par au moins une fraction \(\rho\) des utilisateurs honnêtes. Le protocole Algorand ′ demande en fait à chacun d'un petit nombre d'utilisateurs (c'est-à-dire les vérificateurs d'un étape donnée d'un tour dans Algorand ′, pour propager un message distinct d'une (petite) taille prescrite, et nous devons limiter le temps requis pour accomplir ces instructions. Nous le faisons en enrichissant le député hypothèse comme suit. Pour tout n, \(\rho\) > 95%, et \(\mu\) \(\in\)Z+, il existe \(\lambda\)n,\(\rho\),\(\mu\) tel que, pour tout instant t et tout \(\mu\)-octet messages m1, . . . , mn, chacun propagé par un utilisateur honnête avant t −\(\lambda\)n,\(\rho\),\(\mu\), m1, . . . , mn sont reçus, au temps t, par au moins une fraction \(\rho\) des utilisateurs honnêtes. Remarque • L'hypothèse ci-dessus est délibérément simple, mais également plus solide que ce qui est nécessaire dans notre article.6 • Par souci de simplicité, nous supposons \(\rho\) = 1, et nous ne mentionnons donc pas \(\rho\). • Nous supposons avec pessimisme que, à condition qu'il ne viole pas l'hypothèse MP, l'Adversaire contrôle totalement la livraison de tous les messages. Surtout, sans se faire remarquer des honnêtes gens utilisateurs, l'Adversaire peut décider arbitrairement quel joueur honnête reçoit quel message quand, et accélérer arbitrairement la livraison de n’importe quel message qu’il souhaite.7

Le protocole BA BA⋆dans un cadre traditionnel

Comme nous l'avons déjà souligné, l'accord byzantin est un ingrédient clé de Algorand. En effet, c'est par l'utilisation d'un protocole BA tel que Algorand n'est pas affecté par les forks. Cependant, pour être en sécurité contre notre Adversaire puissant, Algorand doit s'appuyer sur un protocole BA qui satisfait à la remplaçabilité du nouveau joueur contrainte. De plus, pour que Algorand soit efficace, un tel protocole BA doit être très efficace. Les protocoles BA ont d'abord été définis pour un modèle de communication idéalisé, synchrone complet réseaux (réseaux SC). Un tel modèle permet une conception et une analyse plus simples des protocoles BA. 6Étant donné le pourcentage honnête h et la probabilité de défaillance acceptable F, Algorand calcule une limite supérieure, N, au nombre maximum de membres de vérificateurs dans une étape. Ainsi, l’hypothèse MP ne doit être valable que pour n \(\leq\)N. De plus, comme indiqué, l'hypothèse MP est valable quel que soit le nombre d'autres messages pouvant être propagés parallèlement à les MJ. Cependant, comme nous le verrons, dans Algorand, les messages à sont propagés dans un temps essentiellement sans chevauchement. intervalles, pendant lesquels soit un seul bloc est propagé, soit au plus N vérificateurs propagent un petit (par exemple, 200B) message. Ainsi, nous pourrions reformuler l’hypothèse MP d’une manière plus faible, mais aussi plus complexe. 7Par exemple, il peut immédiatement apprendre les messages envoyés par des joueurs honnêtes. Ainsi, un utilisateur malveillant i′, qui est invité à propager un message simultanément avec un utilisateur honnête i, peut toujours choisir son propre message m′ en fonction de le message m réellement propagé par i. Cette capacité est liée à la précipitation, dans le langage du calcul distribué. littérature.En conséquence, dans cette section, nous introduisons un nouveau protocole BA, BA⋆, pour les réseaux SC et en ignorant la question de la remplaçabilité des joueurs. Le protocole BA⋆est une contribution de valeur distincte. En effet, il s’agit du protocole BA cryptographique le plus efficace pour les réseaux SC connu à ce jour. Pour l'utiliser au sein de notre protocole Algorand, nous modifions un peu BA⋆, afi n de tenir compte de nos différents modèle et contexte de communication, mais assurez-vous, dans la section X, de souligner comment BA⋆est utilisé dans le cadre de notre protocole actuel Algorand ′. Nous commençons par rappeler le modèle dans lequel opère BA⋆ et la notion d’accord byzantin. 3.1 Réseaux complets synchrones et adversaires correspondants Dans un réseau SC, il existe une horloge commune, tournant à chaque instant intégral r = 1, 2, . . . A chaque clic pair sur r, chaque joueur i envoie instantanément et simultanément un seul message monsieur i,j (éventuellement le message vide) à chaque joueur j, y compris lui-même. Chaque monsieur i,j est reçu au moment cliquez sur r + 1 par le joueur j, ainsi que l'identité de l'expéditeur i. Encore une fois, dans un protocole de communication, un joueur est honnête s'il suit toutes les instructions qui lui sont prescrites. instructions, et malveillant autrement. Tous les joueurs malveillants sont totalement contrôlés et parfaitement coordonné par l'Adversaire, qui reçoit notamment immédiatement tous les messages adressés à joueurs malveillants, et choisit les messages qu'ils envoient. L'Adversaire peut immédiatement rendre malveillant tout utilisateur honnête qu'il souhaite cliquer à tout moment il le souhaite, sous réserve uniquement d'une éventuelle limite supérieure au nombre de joueurs malveillants. C'est-à-dire l’Adversaire « ne peut pas interférer avec les messages déjà envoyés par un utilisateur honnête i », ce qui sera livré comme d'habitude. L'Adversaire a également la capacité supplémentaire de voir instantanément, à chaque round pair, le messages que les joueurs actuellement honnêtes envoient et utilisent instantanément ces informations pour choisir les messages que les joueurs malveillants envoient en même temps cochent. Remarques • Puissance adverse. Le cadre ci-dessus est très conflictuel. En effet, dans l'accord byzantin Dans la littérature, de nombreux contextes sont moins conflictuels. Cependant, certains contextes plus conflictuels ont a également été envisagé, où l'Adversaire, après avoir vu les messages envoyés par un joueur honnête, je à un instant donné cliquez sur r, a la possibilité d'effacer tous ces messages du réseau, immédiatement je suis corrompu, choisissez le message que le i désormais malveillant envoie au moment où vous cliquez sur r, et demandez-lui livré comme d'habitude. La puissance envisagée des matchs Adversaires qu’il a dans notre cadre. • Abstraction physique. Le modèle de communication envisagé fait abstraction d'un modèle plus physique, dans lequel chaque paire de joueurs (i, j) est reliée par une ligne de communication distincte et privée li,j. Autrement dit, personne d'autre ne peut injecter, interférer ou obtenir des informations sur les messages envoyés. li,j. La seule façon pour l’Adversaire d’avoir accès à li,j est de corrompre i ou j. • Confidentialité et authentification. Dans les réseaux SC, la confidentialité et l'authentification des messages sont garanties par hypothèse. En revanche, dans notre réseau de communication, où les messages se propagent de pair à pair, l'authentification est garantie par des signatures numériques et la confidentialité est inexistante. Ainsi, pour adopter le protocole BA⋆dans notre contexte, chaque message échangé doit être signé numériquement (identifiant en outre l'État dans lequel il a été envoyé). Heureusement, les protocoles BA que nous envisagez d'utiliser dans Algorand ne nécessite pas de confidentialité des messages.3.2 La notion d'accord byzantin La notion d'accord byzantin a été introduite par Pease Shostak et Lamport [31] pour la cas binaire, c'est-à-dire lorsque chaque valeur initiale est constituée d'un bit. Cependant, il a été rapidement prolongé à des valeurs initiales arbitraires. (Voir les enquêtes de Fischer [16] et Chor et Dwork [10].) Par un BA protocole, nous entendons un protocole à valeur arbitraire. Définition 3.1. Dans un réseau synchrone, soit P un protocole à n joueurs, dont l'ensemble de joueurs est commun connaissance entre les joueurs, t un entier positif tel que n \(\geq\)2t + 1. On dit que P est un valeur arbitraire (respectivement binaire) (n, t) -protocole d'accord byzantin avec solidité \(\sigma\) \(\in\)(0, 1) si, pour tout ensemble de valeurs V ne contenant pas le symbole spécial \(\bot\) (respectivement pour V = {0, 1}), dans un exécution dans laquelle au plus t joueurs sont malveillants et dans laquelle chaque joueur i commence avec un valeur initiale vi \(\in\)V , tout joueur honnête j s'arrête avec une probabilité 1, produisant une valeur outi \(\in\)V \(\cup\){\(\bot\)} de manière à satisfaire, avec probabilité au moins \(\sigma\), les deux conditions suivantes : 1. Accord : Il existe out \(\in\)V \(\cup\){\(\bot\)} tel que outi = out pour tous les joueurs honnêtes i. 2. Cohérence : si, pour une valeur v \(\in\)V , vi = v pour tous les joueurs honnêtes, alors out = v. Nous appelons out la sortie de P et chaque outi la sortie du joueur i. 3.3 La notation BA # Dans nos protocoles BA, un joueur doit compter combien de joueurs lui ont envoyé un message donné dans une étape donnée. En conséquence, pour chaque valeur possible v qui pourrait être envoyée,

s

je(v) (ou simplement #i(v) lorsque s est clair) est le nombre de joueurs j dont j'ai reçu v à l'étape s. Rappelons qu'un joueur i reçoit exactement un message de chaque joueur j, si le nombre de joueurs est n, alors, pour tout i et s, P v#s je(v) = n. 3.4 Le protocole binaire BA BBA⋆ Dans cette section, nous présentons un nouveau protocole BA binaire, BBA⋆, qui repose sur l'honnêteté de plus plus des deux tiers des joueurs et est très rapide : peu importe ce que font les joueurs malveillants, chaque exécution de sa boucle principale met les joueurs en accord avec une probabilité 1/3. Chaque joueur possède sa propre clé publique d'un schéma de signature numérique satisfaisant la signature unique propriété. Puisque ce protocole est destiné à être exécuté sur un réseau complet synchrone, il n'y a pas de besoin d'un joueur pour signer chacun de ses messages. Les signatures numériques sont utilisées pour générer un bit aléatoire suffisamment commun à l'étape 3. (Dans Algorand, les signatures numériques sont également utilisées pour authentifier tous les autres messages.) Le protocole nécessite une configuration minimale : une chaîne aléatoire commune r, indépendante des préférences des joueurs. clés. (Dans Algorand, r est en fait remplacé par la quantité Qr.) Le protocole BBA⋆est une boucle en 3 étapes, dans laquelle les joueurs échangent à plusieurs reprises des valeurs booléennes, et différents joueurs peuvent quitter cette boucle à des moments différents. Un joueur qui sort de cette boucle en se propageant, à un moment donné, soit une valeur spéciale 0∗, soit une valeur spéciale 1∗, demandant ainsi à tous les joueurs de «faire semblant» qu'ils reçoivent respectivement 0 et 1 de i dans toutes les étapes futures. (Autrement dit : supposezque le dernier message reçu par un joueur j d'un autre joueur i était un bit b. Puis, à n'importe quelle étape dans lequel il ne reçoit aucun message de i, j fait comme si je lui envoyais le bit b.) Le protocole utilise un compteur \(\gamma\), représentant le nombre de fois que sa boucle en 3 étapes a été exécutée. Au début de BBA⋆, \(\gamma\) = 0. (On peut considérer \(\gamma\) comme un compteur global, mais il est en réalité augmenté par chaque joueur individuel à chaque fois que la boucle est exécutée.) Il y a n \(\geq\)3t + 1, où t est le nombre maximum possible de joueurs malveillants. Un binaire la chaîne x est identifiée avec l'entier dont la représentation binaire (avec des 0 possibles en tête) est x ; et lsb(x) désigne le bit le moins significatif de x. Protocole BBA⋆ (Communication) Étape 1. [Étape Coin-Fixed-To-0] Chaque joueur envoie bi. 1.1 Si #1 i (0) \(\geq\)2t + 1, alors i définit bi = 0, envoie 0∗, sort outi = 0, et ARRÊTS. 1.2 Si #1 i (1) \(\geq\)2t + 1, alors, alors i définit bi = 1. 1.3 Sinon, je définit bi = 0. (Communication) Étape 2. [Étape Coin-Fixed-To-1] Chaque joueur envoie bi. 2.1 Si #2 je (1) \(\geq\)2t + 1, alors je fixe bi = 1, envoie 1∗, sorties outi = 1, et ARRÊTS. 2.2 Si #2 je (0) \(\geq\)2t + 1, alors je mets bi = 0. 2.3 Sinon, je définit bi = 1. (Communication) Étape 3. [Étape Coin-Genuinely-Flipped] Chaque joueur i envoie bi et SIGi(r, \(\gamma\)). 3.1 Si #3 i (0) \(\geq\)2t + 1, alors i définit bi = 0. 3.2 Si #3 i (1) \(\geq\)2t + 1, alors i définit bi = 1. 3.3 Sinon, soit Si = {j \(\in\)N qui a envoyé i un message propre à cette étape 3 }, je définit bi = c \(\triangleq\)lsb(minj\(\in\)Si H(SIGi(r, \(\gamma\)))); augmente \(\gamma\)i de 1 ; et revient à l'étape 1. Théorème 3.1. Chaque fois que n \(\geq\)3t + 1, BBA⋆est un protocole binaire (n, t)-BA de solidité 1. Une preuve du théorème 3.1 est donnée dans [26]. Son adaptation à notre contexte et sa remplaçabilité des joueurs la propriété est nouvelle. Remarque historique Les protocoles BA binaires probabilistes ont été proposés pour la première fois par Ben-Or dans paramètres asynchrones [7]. Le protocole BBA⋆est une nouvelle adaptation, à notre environnement à clé publique, du protocole BA binaire de Feldman et Micali [15]. Leur protocole a été le premier à fonctionner de la manière attendue. nombre constant de pas. Cela a fonctionné en demandant aux joueurs eux-mêmes de mettre en œuvre une pièce commune, une notion proposée par Rabin, qui l'a mise en œuvre via une partie de confiance externe [32].3.5 Consensus gradué et protocole GC Rappelons, pour les valeurs arbitraires, une notion de consensus bien plus faible que l'accord byzantin. Définition 3.2. Soit P un protocole dans lequel l’ensemble de tous les acteurs est de notoriété publique, et chacun joueur, je connais en privé une valeur initiale arbitraire v′ je. Nous disons que P est un protocole de consensus gradué (n, t) si, dans toute exécution avec n joueurs, à dont la plupart sont malveillants, chaque joueur honnête i arrête de produire une paire valeur-grade (vi, gi), où gi \(\in\){0, 1, 2}, de manière à satisfaire les trois conditions suivantes : 1. Pour tous les joueurs honnêtes i et j, |gi −gj| \(\leq\)1. 2. Pour tous les joueurs honnêtes i et j, gi, gj > 0 ⇒vi = vj. 3. Si v′ 1 = \(\cdots\) = v′ n = v pour une valeur v, alors vi = v et gi = 2 pour tous les joueurs honnêtes i. Note historique La notion de consensus gradué dérive simplement de celle de consensus gradué. diffusée, mise en avant par Feldman et Micali dans [15], en renforçant la notion de croisé accord, tel qu’introduit par Dolev [12], et affiné par Turpin et Coan [33].8 Dans [15], les auteurs ont également fourni un protocole de diffusion gradué en 3 étapes (n, t), gradecast, pour n \(\geq\)3t+1. Un protocole de diffusion plus complexe (n, t) pour n > 2t+1 a été découvert plus tard. par Katz et Koo [19]. Le protocole GC en deux étapes suivant comprend les deux dernières étapes du gradecast, exprimées dans notre notation. Pour souligner ce fait, et pour correspondre aux étapes du protocole Algorand ′ de la section 4.1, nous nommer respectivement 2 et 3 les étapes de GC. Protocole GC Étape 2. Chaque joueur envoie v′ je à tous les joueurs. Étape 3. Chaque joueur i envoie à tous les joueurs la chaîne x si et seulement si #2 je (x) \(\geq\)2t + 1. Détermination du résultat. Chaque joueur i produit la paire (vi, gi) calculée comme suit : • Si, pour certains x, #3 je (x) \(\geq\)2t + 1, alors vi = x et gi = 2. • Si, pour certains x, #3 je (x) \(\geq\)t + 1, alors vi = x et gi = 1. • Sinon, vi = \(\bot\)et gi = 0. Théorème 3.2. Si n \(\geq\)3t + 1, alors GC est un protocole de diffusion gradué (n, t). La preuve découle immédiatement de celle du protocole gradecast dans [15], et est donc omise.9 8Essentiellement, dans un protocole de diffusion graduée, (a) l’entrée de chaque acteur est l’identité d’un personnage distingué. joueur, l'expéditeur, qui a une valeur arbitraire v comme entrée privée supplémentaire, et (b) les sorties doivent satisfaire la mêmes propriétés 1 et 2 du consensus gradué, plus la propriété suivante 3′ : si l'expéditeur est honnête, alors vi = v et gi = 2 pour tout joueur honnête i. 9En effet, dans leur protocole, à l’étape 1, l’expéditeur envoie sa propre valeur privée v à tous les joueurs, et chaque joueur i laisse v′ je comprends la valeur qu'il a réellement reçue de l'expéditeur à l'étape 1.3.6 Le Protocole BA⋆ Nous décrivons maintenant le protocole BA à valeurs arbitraires BA⋆via le protocole BA binaire BBA⋆et le protocole de consensus gradué GC. Ci-dessous, la valeur initiale de chaque joueur i est v′ je. Protocole BA⋆ Étapes 1 et 2. Chaque joueur i exécute GC, sur l'entrée v′ i, de manière à calculer un couple (vi, gi). Étape 3, . . . Chaque joueur i exécute BBA⋆ — avec l'entrée initiale 0, si gi = 2, et 1 sinon — donc quant à calculer le bit outi. Détermination du résultat. Chaque joueur i produit vi, si outi = 0, et \(\bot\)sinon. Théorème 3.3. Chaque fois que n \(\geq\)3t + 1, BA⋆est un protocole (n, t)-BA de solidité 1. Preuve. Nous prouvons d’abord la cohérence, puis l’accord. Preuve de cohérence. Supposons que, pour une valeur v \(\in\)V , v′ i = v. Alors, par la propriété 3 de consensus noté, après l'exécution de GC, tous les joueurs honnêtes sortent (v, 2). En conséquence, 0 est le premier élément de tous les joueurs honnêtes à la fin de l'exécution de BBA⋆. Ainsi, par l'accord propriété de l'accord byzantin binaire, à la fin de l'exécution de BA⋆, outi = 0 pour tout honnête joueurs. Cela implique que la sortie de chaque joueur honnête i dans BA⋆est vi = v. ✷ Preuve d'accord. Puisque BBA⋆est un protocole BA binaire, soit (A) outi = 1 pour tout joueur honnête i, ou (B) outi = 0 pour tout joueur honnête i. Dans le cas A, tous les joueurs honnêtes produisent \(\bot\)dans BA⋆, et donc l'accord est valable. Considérons maintenant le cas B. Dans dans ce cas, dans l’exécution de BBA⋆, le bit initial d’au moins un joueur honnête i est 0. (En effet, si Le bit initial de tous les joueurs honnêtes était 1, alors, par la propriété de cohérence de BBA⋆, nous aurions outj = 1 pour tout j honnête.) En conséquence, après l'exécution de GC, i génère la paire (v, 2) pour certains valeur v. Ainsi, par propriété 1 de consensus gradué, gj > 0 pour tous les joueurs honnêtes j. En conséquence, par propriété 2 du consensus gradué, vj = v pour tous les joueurs honnêtes j. Cela implique qu'à la fin de BA⋆, tout joueur honnête j produit v. Ainsi, l'accord est également valable dans le cas B. ✷ Puisque la cohérence et l'accord sont valables, BA⋆est un protocole BA à valeur arbitraire. Note historique Turpin et Coan ont été les premiers à montrer que, pour n \(\geq\)3t+1, tout binaire (n, t)-BA Le protocole peut être converti en un protocole (n, t)-BA à valeur arbitraire. La réduction à valeur arbitraire L’accord byzantin à l’accord binaire byzantin via un consensus gradué est plus modulaire et plus propre, et simplifie l’analyse de notre protocole Algorand Algorand ′. Généralisation de BA⋆à utiliser dans Algorand Algorand fonctionne même lorsque toutes les communications se font via bavarder. Cependant, bien que présenté dans un réseau de communication traditionnel et familier, pour permettre une meilleure comparaison avec l'art antérieur et une compréhension plus aisée, le protocole BA⋆fonctionne également dans les réseaux de commérages. En fait, dans nos modes de réalisation détaillés de Algorand, nous le présenterons directement pour les réseaux de potins. Nous soulignerons également qu'elle satisfait le joueur en termes de remplaçabilité. propriété qui est cruciale pour que Algorand soit sécurisée dans le modèle très contradictoire envisagé.

Tout protocole remplaçable par un lecteur BA fonctionnant dans un réseau de communication bavarde peut être utilisé en toute sécurité dans le système inventif Algorand. En particulier, Micali et Vaikunthanatan ont étendu BA⋆pour travailler très efficacement également avec une simple majorité de joueurs honnêtes. Cela Le protocole pourrait également être utilisé dans Algorand.

Deux modes de réalisation de Algorand

Comme indiqué, à un niveau très élevé, un cycle de Algorand se déroule idéalement comme suit. D'abord, au hasard l'utilisateur sélectionné, le leader, propose et fait circuler un nouveau bloc. (Ce processus comprend initialement sélectionner quelques dirigeants potentiels, puis veiller à ce que, au moins une bonne partie du temps, un un seul leader commun émerge.) Deuxièmement, un comité d'utilisateurs sélectionné au hasard est sélectionné, et parvient à un accord byzantin sur le bloc proposé par le leader. (Ce processus inclut cela chaque étape du protocole BA est gérée par un comité sélectionné séparément.) Le bloc convenu est ensuite signé numériquement par un seuil (TH) donné de membres du comité. Ces signatures numériques sont diffusés afin que chacun sache quel est le nouveau bloc. (Cela inclut la diffusion du informations d'identification des signataires et authentifiant uniquement le hash du nouveau bloc, garantissant que tout le monde est assuré d'apprendre le bloc, une fois que son hash est clarifié.) Dans les deux sections suivantes, nous présentons deux modes de réalisation de Algorand, Algorand ′ 1 et Algorand′ 2, qui fonctionnent selon l’hypothèse d’une majorité d’utilisateurs honnêtes. Dans la section 8, nous montrons comment adopter ces les modes de réalisation fonctionnent dans le cadre d’une hypothèse de majorité honnête en termes d’argent. Algorand ′ 1 envisage seulement que > 2/3 des membres du comité soient honnêtes. De plus, dans Algorand' 1, le nombre d'étapes pour parvenir à un accord byzantin est plafonné à un niveau suffisamment élevé nombre, de sorte qu'un accord est garanti avec une probabilité écrasante d'être atteint dans un délai raisonnable. nombre d'étapes fixe (mais nécessitant potentiellement un temps plus long que les étapes de Algorand ′ 2). Dans le Dans le cas rare où un accord n'est pas encore atteint à la dernière étape, la commission se met d'accord sur la bloc vide, qui est toujours valide. Algorand' 2 prévoit que le nombre de membres honnêtes dans un comité est toujours supérieur à ou égal à un seuil fixe tH (qui garantit que, avec une écrasante probabilité, au moins 2/3 des membres du comité sont honnêtes). De plus, Algorand ′ 2 permet à l'accord byzantin de être atteint en un nombre arbitraire d'étapes (mais potentiellement en un temps plus court que Algorand ′ 1). Il est facile de dériver de nombreuses variantes de ces modes de réalisation de base. En particulier, c'est facile, étant donné Algorand' 2, pour modifier Algorand′ 1 afin de permettre de parvenir à un accord byzantin de manière arbitraire nombre d'étapes. Les deux modes de réalisation partagent le noyau commun, les notations, les notions et les paramètres suivants. 4.1 Un tronc commun Objectifs Idéalement, pour chaque tour r, Algorand satisferait les propriétés suivantes : 1. Exactitude parfaite. Tous les utilisateurs honnêtes sont d'accord sur le même bloc Br. 2. Complétude 1. Avec une probabilité de 1, l’ensemble de rémunération de Br, PAY r, est maximal.10 10Parce que les ensembles de paiements sont définis pour contenir des paiements valides et que les utilisateurs honnêtes n’effectuent que des paiements valides, une limite maximale PAY r contient les paiements « actuellement impayés » de tous les utilisateurs honnêtes.Bien entendu, garantir à lui seul une exactitude parfaite est trivial : chacun choisit toujours le modèle officiel. payet PAY r doit être vide. Mais dans ce cas, le système aurait la complétude 0. Malheureusement, garantir à la fois l'exactitude et l'exhaustivité parfaites 1 n'est pas chose aisée en présence d'informations malveillantes utilisateurs. Algorand adopte ainsi un objectif plus réaliste. De manière informelle, en laissant h désigner le pourcentage des utilisateurs honnêtes, h > 2/3, l'objectif de Algorand est Garantissant, avec une probabilité écrasante, une parfaite exactitude et une exhaustivité proche de h. Privilégier l'exactitude à l'exhaustivité semble un choix raisonnable : les paiements non traités un tour peut être traité le suivant, mais il faut éviter les fourchettes, si possible. Accord byzantin dirigé L'exactitude parfaite pourrait être garantie comme suit. Au début du tour r, chaque utilisateur i construit son propre bloc candidat Br i , puis tous les utilisateurs atteignent Byzantine accord sur un bloc candidat. Conformément à notre introduction, le protocole BA utilisé nécessite une majorité honnête des 2/3 et est remplaçable par le joueur. Chacune de ses étapes peut être exécutée par un petit et ensemble de vérificateurs sélectionnés au hasard, qui ne partagent aucune variable interne. Malheureusement, cette approche n'a aucune garantie d'exhaustivité. Il en est ainsi parce que le candidat les blocs d’utilisateurs honnêtes sont très probablement totalement différents les uns des autres. Ainsi, en fin de compte le bloc convenu peut toujours être un bloc avec un ensemble de paiements non maximal. En fait, il se peut toujours que ce soit le bloc vide, B\(\varepsilon\), c'est-à-dire le bloc dont le payet est vide. eh bien, ce sera celui par défaut, vide. Algorand ′ évite ce problème d'exhaustivité comme suit. Tout d’abord, un leader pour le tour r, \(\ell\)r, est sélectionné. Ensuite, \(\ell\)r propage son propre bloc candidat, Br \(\ell\)r. Finalement, les utilisateurs parviennent à un accord sur le blocage ils reçoivent en fait de \(\ell\)r. Parce que, chaque fois que \(\ell\)r est honnête, l'exactitude et l'exhaustivité sont parfaites. 1 sont tous deux valables, Algorand ′ garantit que \(\ell\)r est honnête avec une probabilité proche de h. (Quand le leader est malveillant, nous ne nous soucions pas de savoir si le bloc convenu est un bloc avec un ensemble de paiements vide. Après tout, un un leader malveillant \(\ell\)r pourrait toujours choisir par malveillance Br \(\ell\)r être le bloc vide, et puis honnêtement le propager, obligeant ainsi les utilisateurs honnêtes à se mettre d'accord sur le bloc vide.) Sélection des dirigeants Dans Algorand, le rème bloc est de la forme Br = (r, PAY r, Qr, H(Br−1). Comme déjà mentionné en introduction, la quantité Qr−1 est soigneusement construite de manière à être essentiellement non manipulable par notre très puissant adversaire. (Plus loin dans cette section, nous verrons donnent une idée de la raison pour laquelle c'est le cas.) Au début d'un tour r, tous les utilisateurs connaissent le blockchain jusqu'à présent, B0, . . . , Br−1, dont ils déduisent l’ensemble des utilisateurs de chaque tour précédent : que est, PK1, . . . , PKr−1. Un leader potentiel du tour r est un utilisateur i tel que .H SIGI r, 1, Qr−1 \(\leq\)p. Expliquons-nous. Notez que, puisque la quantité Qr−1 fait partie du bloc Br−1, et que la quantité sous-jacente le schéma de signature satisfait à la propriété d'unicité, SIGi r, 1, Qr−1 est une chaîne binaire uniquement associé à i et r. Ainsi, puisque H est un oracle aléatoire, H SIGI r, 1, Qr−1 est un 256 bits aléatoire longue chaîne associée de manière unique à i et r. Le symbole « ». devant H SIGI r, 1, Qr−1 est le point décimal (dans notre cas, binaire), de sorte que ri \(\triangleq\).H SIGI r, 1, Qr−1 est le développement binaire d'un nombre aléatoire de 256 bits compris entre 0 et 1 associé de manière unique à i et r. Ainsi la probabilité que ri est inférieur ou égal à p est essentiellement p. (Notre mécanisme de sélection des leaders potentiels a été inspiré du système de micro-paiement de Micali et Rivest [28].) La probabilité p est choisie de telle sorte que, avec une probabilité écrasante (c'est-à-dire 1 − F), au moins un le vérificateur potentiel est honnête. (Si tel est le cas, p est choisi comme étant la plus petite probabilité de ce type.)Notons que, puisque i est le seul capable de calculer ses propres signatures, lui seul peut déterminer s'il est un vérificateur potentiel du premier tour. Cependant, en révélant son propre titre, \(\sigma\)r je \(\triangleq\)SIGi r, 1, Qr−1 , je peux prouver à n’importe qui que je suis un vérificateur potentiel du tour r. Le leader \(\ell\)r est défini comme étant le leader potentiel dont le titre hashed est plus petit que le leader potentiel. hashed accréditation de tous les autres leaders potentiels j : c'est-à-dire H(\(\sigma\)r,s \(\ell\)r ) \(\leq\)H(\(\sigma\)r,s j). Notez que, puisqu'un \(\ell\)r malveillant ne peut pas révéler ses informations d'identification, le bon leader du tour r peut ne sera jamais connu, et que, sauf liens improbables, \(\ell\)r est bien le seul leader du tour r. Abordons enfin un dernier détail important : un utilisateur i peut être un leader potentiel (et donc le leader) d'un tour r seulement s'il a appartenu au système pendant au moins k tours. Cela garantit la non-manipulabilité de Qr et de toutes les futures quantités Q. En fait, l'un des dirigeants potentiels déterminera en fait Qr. Sélection du vérificateur Chaque étape s > 1 du tour r est exécutée par un petit ensemble de vérificateurs, SV r,s. Encore une fois, chaque vérificateur i \(\in\)SV r,s est sélectionné aléatoirement parmi les utilisateurs déjà présents dans le système k tours avant r, et encore via la quantité spéciale Qr−1. Plus précisément, i \(\in\)PKr−k est un vérificateur dans SV r,s, si .H SIGI r, s, Qr−1 \(\leq\)p′. Encore une fois, moi seul sais s'il appartient au SV r,s, mais, si tel est le cas, il pourrait le prouver en exhibant son titre \(\sigma\)r,s je \(\triangleq\)H(SIGi r, s, Qr−1 ). Un vérificateur i \(\in\)SV r,s envoie un message, mr,s moi, dans étape s du tour r, et ce message inclut son identifiant \(\sigma\)r,s i , afin de permettre aux vérificateurs du étape de nidification pour reconnaître que mr,s je est un message d'étape légitime. La probabilité p′ est choisie de manière à assurer que, dans SV r,s, soit #good le nombre de utilisateurs honnêtes et #bad le nombre d'utilisateurs malveillants, avec une probabilité écrasante ce qui suit deux conditions sont remplies. Pour le mode de réalisation Algorand ′ 1 : (1) #bon > 2 \(\cdot\) #mauvais et (2) #bon + 4 \(\cdot\) #mauvais < 2n, où n est la cardinalité attendue de SV r,s. Pour le mode de réalisation Algorand ′ 2 : (1) #bon > th et (2) #bon + 2#mauvais < 2tH, où tH est un seuil spécifié. Ces conditions impliquent que, avec une probabilité suffisamment élevée, (a) dans la dernière étape du BA protocole, il y aura au moins un nombre donné de joueurs honnêtes pour signer numériquement le nouveau bloc Br, (b) un seul bloc par tour peut avoir le nombre de signatures nécessaire, et (c) le BA utilisé le protocole a (à chaque étape) la majorité honnête requise des 2/3. Clarification de la génération de blocs Si le leader du tour \(\ell\)r est honnête, alors le bloc correspondant est de la forme Br = r, PAYer r, SIG\(\ell\)r Qr−1 , H Br−1 , où le payset PAY r est maximal. (rappelons que tous les ensembles de paie sont, par définition, collectivement valables.) Sinon (c'est-à-dire si \(\ell\)r est malveillant), Br a l'une des deux formes possibles suivantes : Br = r, PAYER r, SIGi Qr−1 , H Br−1 et Br = Br \(\varepsilon\) \(\triangleq\) r, \(\emptyset\), Qr−1, H Br−1 .Dans la première forme, PAY r est un ensemble de salaires (non nécessairement maximal) et il peut s'agir de PAY r = \(\emptyset\) ; et je suis un leader potentiel du tour r. (Cependant, je ne suis peut-être pas le leader \(\ell\)r. Cela peut effectivement arriver si si \(\ell\)r garde secret ses informations d'identification et ne se révèle pas.) La deuxième forme apparaît lorsque, lors de l'exécution du protocole BA, tous les joueurs honnêtes afficher la valeur par défaut, qui est le bloc vide Br \(\varepsilon\) dans notre application. (Par définition, le possible les sorties d'un protocole BA incluent une valeur par défaut, notée génériquement par \(\bot\). Voir la section 3.2.) Notez que, bien que les ensembles de payes soient vides dans les deux cas, Br = r, \(\emptyset\), SIGi Qr−1 , H Br−1 et Br \(\varepsilon\) sont des blocs syntaxiquement différents et apparaissent dans deux situations différentes : respectivement, « tous s’est déroulé sans problème dans l’exécution du protocole BA », et « quelque chose s’est mal passé dans l’exécution du protocole BA ». Protocole BA, et la valeur par défaut a été sortie ». Décrivons maintenant intuitivement comment se déroule la génération du bloc Br au tour r de Algorand ′. Dans un premier temps, chaque joueur éligible, c’est-à-dire chaque joueur i \(\in\)PKr−k, vérifie s’il est un potentiel chef. Si tel est le cas, on me demande alors, en utilisant tous les paiements qu'il a vus jusqu'à présent, et le actuel blockchain, B0, . . . , Br−1, pour préparer secrètement un ensemble de paiements maximal, PAY r moi, et secrètement assemble son bloc candidat, Br = r, PAYER r je, SIGi Qr−1 , H Br−1 . Autrement dit, non seulement il inclure dans Br i , comme deuxième composant le payset qui vient d'être préparé, mais aussi, comme troisième composant, sa propre signature de Qr−1, la troisième composante du dernier bloc, Br−1. Finalement, il propage son message round-r-step-1, mr,1 i , qui comprend (a) son bloc candidat Br i , (b) sa signature officielle de son bloc candidat (c'est-à-dire sa signature du hash du Br i , et (c) son propre titre \(\sigma\)r,1 je, prouvant qu'il est bien un vérificateur potentiel du tour r. (Notez que, jusqu'à ce qu'un honnête je produise son message mr,1 moi, l'Adversaire n'a aucune idée que je suis un vérificateur potentiel. S’il souhaite corrompre des dirigeants potentiels honnêtes, l’Adversaire pourrait tout aussi bien joueurs honnêtes aléatoires corrompus. Cependant, une fois qu'il voit M.,1 i , puisqu'il contient les informations d'identification de i, le L'adversaire sait et pourrait corrompre moi, mais ne peut pas empêcher mr,1 i , qui se propage viralement, à partir de atteignant tous les utilisateurs du système.) Dans un deuxième temps, chaque vérificateur sélectionné j \(\in\)SV r,2 tente d'identifier le leader du tour. Plus précisément, j prend les informations d'identification de l'étape 1, \(\sigma\)r,1 je1 , . . . , \(\sigma\)r,1 dans , contenu dans le message approprié de l'étape 1 mr,1 je il a reçu; hashes tous, c'est-à-dire calcule H  \(\sigma\)r,1 i1  , . . . , H  \(\sigma\)r,1 dans  ; trouve l'identifiant, \(\sigma\)r,1 \(\ell\)j , dont hash est lexicographiquement minimum ; et considère \(\ell\)r j être le leader du tour r. Rappelons que chaque identifiant considéré est une signature numérique de Qr−1, que SIGi r, 1, Qr−1 est déterminé de manière unique par i et Qr−1, que H est aléatoire oracle, et donc que chaque H(SIGi r, 1, Qr−1 est une chaîne aléatoire de 256 bits unique à chaque leader potentiel i du tour r. De là, nous pouvons conclure que, si la chaîne de 256 bits Qr−1 était elle-même aléatoire et indépendante sélectionnés, alors ce seraient les informations d'identification hashed de tous les dirigeants potentiels du tour r. En fait, tout les dirigeants potentiels sont bien définis, tout comme leurs références (qu’elles soient réellement calculées ou non). De plus, l’ensemble des leaders potentiels du tour r est un sous-ensemble aléatoire des utilisateurs du tour r −k, et un leader potentiel honnête, je construit et propage toujours correctement son message mr je, qui contient mes informations d'identification. Ainsi, puisque le pourcentage d'utilisateurs honnêtes est h, quel que soit le que des dirigeants potentiels malveillants pourraient faire (par exemple, révéler ou dissimuler leurs propres informations d'identification), le minimum Le titre de leader potentiel hashed appartient à un utilisateur honnête, nécessairement identifié par tous être le leader \(\ell\)r du tour r. En conséquence, si la chaîne de 256 bits Qr−1 était elle-même aléatoire et sélectionné indépendamment, avec probabilité exactement h (a) le leader \(\ell\)r est honnête et (b) \(\ell\)j = \(\ell\)r pour tous vérificateurs honnêtes de l'étape 2 j. En réalité, les identifiants hashed sont, oui, sélectionnés au hasard, mais dépendent de Qr−1, qui estpas choisis au hasard et indépendamment. Nous prouverons cependant dans notre analyse que Qr−1 est suffisamment non manipulable pour garantir que le leader d'un tour est honnête avec probabilité h′ suffisamment proche de h : à savoir h′ > h2(1 + h −h2). Par exemple, si h = 80 %, alors h′ > 0,7424. Après avoir identifié le leader du tour (ce qu'ils font correctement lorsque le leader \(\ell\)r est honnête), la tâche des vérificateurs de l'étape 2 est de commencer à exécuter le BA en utilisant comme valeurs initiales ce qu'ils croient être le bloc du leader. En fait, afin de minimiser la quantité de communication requise, un vérificateur j \(\in\)SV r,2 n’utilise pas comme valeur d’entrée v′ j au protocole byzantin, le bloc Bj qui il a effectivement reçu de \(\ell\)j (l'utilisateur j croit être le leader), mais le leader, mais le hash de ce bloc, c'est-à-dire v′ j = H(Bi). Ainsi, à la fin du protocole BA, les vérificateurs de la dernière étape ne calcule pas le bloc round-r souhaité Br, mais calcule (authentifier et se propager) H(Br). En conséquence, puisque H(Br) est signé numériquement par suffisamment de vérificateurs du dernière étape du protocole BA, les utilisateurs du système se rendront compte que H(Br) est le hash du nouveau bloquer. Cependant, ils doivent également récupérer (ou attendre, puisque l'exécution est assez asynchrone) le bloquer Br lui-même, dont le protocole garantit qu'il est effectivement disponible, quel que soit l'adversaire pourrait faire. Asynchronie et timing Algorand ′ 1 et Algorand′ 2 ont un degré d’asynchronie important. Il en est ainsi parce que l'Adversaire dispose d'une grande latitude pour planifier la livraison des messages en cours de transmission. propagé. De plus, que le nombre total d'étapes d'un tour soit plafonné ou non, il y a la variance contribue au nombre de pas réellement effectués. Dès qu'il prend connaissance des certificats de B0, . . . , Br−1, un utilisateur i calcule Qr−1 et commence à travailler au tour r, vérifier s'il est un leader potentiel, ou un vérificateur à certaines étapes du tour r. En supposant que je doive agir à l'étape s, à la lumière de l'asynchronie discutée, je m'appuie sur diverses des stratégies pour s’assurer qu’il dispose d’informations suffisantes avant d’agir. Par exemple, il pourrait attendre de recevoir au moins un nombre donné de messages des vérificateurs de l'étape précédente, ou attendre un temps suffisant pour être sûr qu'il reçoive les messages de suffisamment de nombreux vérificateurs de l’étape précédente. Le Seed Qr et le paramètre Look-Back k Rappelons que, idéalement, les quantités Qr devraient aléatoires et indépendants, même s’il suffira qu’ils soient suffisamment non manipulables par l'Adversaire. À première vue, on pourrait choisir Qr−1 pour coïncider avec H PAYER r−1 , et ainsi éviter de spécifier explicitement Qr−1 dans Br−1. Une analyse élémentaire révèle cependant que des utilisateurs malveillants peuvent tirer parti de ce mécanisme de sélection.11 Des efforts supplémentaires montrent que des myriades d’autres 11Nous sommes au début du tour r −1. Ainsi, Qr−2 = PAY r−2 est publiquement connu, et l'Adversaire en privé sait qui sont les dirigeants potentiels qu’il contrôle. Supposons que l'Adversaire contrôle 10 % des utilisateurs, et que, avec une très forte probabilité, un utilisateur malveillant w est le leader potentiel du tour r −1. Autrement dit, supposons que H SIGw r −2, 1, Qr−2 est si petit qu'il est hautement improbable qu'un leader potentiel honnête soit réellement le leader du tour r −1. (Rappelons que, puisque nous choisissons les dirigeants potentiels via un mécanisme de tri cryptographique secret, l’Adversaire ne sait pas qui sont les dirigeants potentiels honnêtes.) L’Adversaire se trouve donc dans une situation enviable. position de choisir le ensemble de paie PAY ′ qu'il souhaite, et qu'il devienne l'ensemble de paie officiel du tour r −1. Cependant, il peut faire plus. Il peut également s'assurer que, avec une forte probabilité, () l'un de ses utilisateurs malveillants sera le leader également du tour r, afin qu'il puisse choisir librement quel sera PAY r. (Et ainsi de suite. Au moins pendant longtemps, c'est-à-dire tant que ces événements à forte probabilité se produisent réellement.) Pour garantir (), l'Adversaire agit comme suit. Laissez PAYER ' être le ensemble de paiements que l'Adversaire préfère pour le tour r −1. Ensuite, il calcule H(PAY ′) et vérifie si, pour certains joueur déjà malveillant z, SIGz(r, 1, H(PAY ′)) est particulièrement petit, c'est-à-dire suffisamment petit pour qu'avec des valeurs très élevées la probabilité z sera le leader du tour r. Si tel est le cas, alors il demande à w de choisir son bloc candidat àles alternatives, basées sur les quantités de blocs traditionnelles, sont facilement exploitables par l'Adversaire pour garantir que les dirigeants malveillants sont très fréquents. Nous définissons plutôt notre marque de manière spécifique et inductive. nouvelle quantité Qr afin de pouvoir prouver qu'elle est non manipulable par l'Adversaire. A savoir, Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), si Br n'est pas le bloc vide, et Qr \(\triangleq\)H(Qr−1, r) sinon. L’intuition de la raison pour laquelle cette construction de Qr fonctionne est la suivante. Supposons un instant que Qr−1 est véritablement sélectionné de manière aléatoire et indépendante. Alors, Qr en sera-t-il aussi ? Quand \(\ell\)r est honnête, le la réponse est (en gros) oui. Il en est ainsi parce que H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→{0, 1}256 est une fonction aléatoire. Cependant, lorsque \(\ell\)r est malveillant, Qr n’est plus défini de manière univoque à partir de Qr−1 et \(\ell\)r. Il existe au moins deux valeurs distinctes pour Qr. On continue d'être Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), et l'autre est H(Qr−1, r). Disons d’abord que, même si le deuxième choix est quelque peu arbitraire, un deuxième choix est absolument obligatoire. La raison en est qu'un \(\ell\)r malveillant peut toujours provoquer des blocs candidats totalement différents doivent être reçus par les vérificateurs honnêtes de la deuxième étape.12 Une fois Dans ce cas, il est facile de s'assurer que le blocage finalement convenu via le protocole BA de round r sera celui par défaut et ne contiendra donc la signature numérique de personne de Qr−1. Mais le système doit continuer, et pour cela, il a besoin d'un leader pour le tour r. Si ce leader est automatiquement et ouvertement sélectionné, alors l'Adversaire le corrompra trivialement. S'il est sélectionné par le précédent Qr−1 via le même processus, alors \(\ell\)r sera à nouveau leader au tour r+1. Nous proposons spécifiquement de utiliser le même mécanisme de tri cryptographique secret, mais appliqué à une nouvelle quantité Q : à savoir, H(Qr−1, r). En faisant de cette quantité la sortie de H garantit que la sortie est aléatoire, et en incluant r comme deuxième entrée de H, alors que toutes les autres utilisations de H ont une ou 3+ entrées, « garantit » qu’un tel Qr est sélectionné indépendamment. Encore une fois, notre choix spécifique d’alternative Qr n'a pas d'importance, ce qui compte c'est que \(\ell\)r ait deux choix pour Qr, et ainsi il peut doubler ses chances avoir un autre utilisateur malveillant comme prochain leader. Les options pour Qr pourraient même être plus nombreuses pour l’Adversaire qui contrôle un \(\ell\)r malveillant. Par exemple, soit x, y et z trois leaders potentiels malveillants du tour r tels que H \(\sigma\)r,1 x
<H \(\sigma\)r,1 oui
1. Notez que n1 << n, puisque nous avons besoin d'au moins un membre honnête et honnête dans SV r,1, mais au moins une majorité de membres honnêtes dans chaque SV r,s pour s > 1. • h \(\in\)(0, 1) : une constante supérieure à 2/3. h est le ratio d'honnêteté dans le système. Autrement dit, le La fraction d'utilisateurs honnêtes ou d'argent honnête, selon l'hypothèse utilisée, dans chaque PKr est au moins h. • H : une fonction cryptographique hash, modélisée comme un oracle aléatoire. • \(\bot\) : Une chaîne spéciale de la même longueur que la sortie de H. • F \(\in\)(0, 1) : le paramètre spécifiant la probabilité d'erreur autorisée. Une probabilité \(\leq\)F est est considérée comme « négligeable » et une probabilité \(\geq\)1 −F est considérée comme « écrasante ». • ph \(\in\)(0, 1) : la probabilité que le leader d'un tour r, \(\ell\)r, soit honnête. Idéalement ph = h. Avec l’existence de l’Adversaire, la valeur du ph sera déterminée lors de l’analyse. • k \(\in\)Z+ : le paramètre de rétrospection. Autrement dit, le tour r −k est l'endroit où les vérificateurs du tour r sont choisi parmi —à savoir, SV r \(\subseteq\)PKr−k.15 – p1 \(\in\)(0, 1) : pour la première étape du tour r, un utilisateur du tour r −k est choisi pour être dans SV r,1 avec probabilité p1 \(\triangleq\) n1 |P Kr−k|. • p \(\in\)(0, 1) : pour chaque étape s > 1 du tour r, un utilisateur du tour r −k est choisi pour être dans SV r,s avec probabilité p \(\triangleq\) n |P Kr−k|. • CERT r : le certificat du Br. Il s’agit d’un ensemble de signatures de H(Br) provenant de vérificateurs appropriés dans rond r. • Br \(\triangleq\)(Br, CERT r) est un bloc éprouvé. Un utilisateur i connaît Br s'il possède (et vérifie avec succès) les deux parties du bloc éprouvé. Notez que le CERT vu par différents utilisateurs peut être différent. • τr i : l'heure (locale) à laquelle un utilisateur i connaît Br. Dans le protocole Algorand chaque utilisateur a son propre horloge. Les horloges des différents utilisateurs n’ont pas besoin d’être synchronisées, mais doivent avoir la même vitesse. Uniquement aux fins de l’analyse, nous considérons une horloge de référence et mesurons les performances des joueurs. moments liés à celui-ci. • \(\alpha\)r,s je et \(\beta\)r,s i : respectivement l'heure (locale) à laquelle un utilisateur i commence et termine son exécution de l'étape s de rond r. • Λ et \(\lambda\) : essentiellement, les limites supérieures, respectivement, du temps nécessaire pour exécuter l'étape 1 et le temps nécessaire à toute autre étape du protocole Algorand. Le paramètre Λ limite supérieurement le temps de propagation d'un seul bloc de 1 Mo. (Dans notre notation, Λ = \(\lambda\) \(\rho\),1Mo. En rappelant notre notation, que nous fixons \(\rho\) = 1 pour plus de simplicité, et que les blocs sont choisi pour avoir une longueur maximale de 1 Mo, nous avons Λ = \(\lambda\)1,1,1 Mo.) 15À proprement parler, « r −k » devrait être « max{0, r −k} ».Le paramètre \(\lambda\) limite le temps nécessaire pour propager un petit message par vérificateur dans une étape s > 1. (En utilisant, comme dans Bitcoin, des signatures de courbe elliptique avec des clés de 32 B, un message de vérification fait 200 B de long. Ainsi, dans notre notation, \(\lambda\) = \(\lambda\)n,\(\rho\),200B.) Nous supposons que Λ = O(\(\lambda\)). Notions • Sélection du vérificateur. Pour chaque tour r et étape s > 1, SV r,s \(\triangleq\){i \(\in\)PKr−k : .H(SIGi(r, s, Qr−1)) \(\leq\)p}. Chacun l'utilisateur i \(\in\)PKr−k calcule en privé sa signature en utilisant sa clé à long terme et décide si i \(\in\)SV r,s ou non. Si i \(\in\)SV r,s, alors SIGi(r, s, Qr−1) est l’identifiant (r, s) de i, noté de manière compacte par \(\sigma\)r,s je. Pour la première étape du tour r, SV r,1 et \(\sigma\)r,1 je sont définis de la même manière, avec p remplacé par p1. Le les vérificateurs dans SV r,1 sont des leaders potentiels. • Sélection des dirigeants. L'utilisateur i \(\in\)SV r,1 est le leader du tour r, noté \(\ell\)r, si H(\(\sigma\)r,1 je ) \(\leq\)H(\(\sigma\)r,1 j ) pour tout potentiel dirigeants j \(\in\)SV r,1. Chaque fois que les hashes des informations d’identification de deux joueurs sont comparées, dans le cas improbable En cas d'égalité, le protocole rompt toujours les égalités lexicographiquement en fonction de l'ordre (public à long terme) clés des) leaders potentiels. Par définition, la valeur hash de l’identifiant du joueur \(\ell\)r est également la plus petite parmi tous les utilisateurs de PKr−k. Notez qu'un leader potentiel ne peut pas décider en privé s'il est le leader ou non, sans voir les références des autres dirigeants potentiels. Puisque les valeurs hash sont uniformes au hasard, lorsque SV r,1 est non vide, \(\ell\)r existe toujours et est honnête avec probabilité au moins h. Le paramètre n1 est suffisamment grand pour garantir que chaque SV r,1 est non vide avec une probabilité écrasante. • Structure des blocs. Un bloc non vide est de la forme Br = (r, PAY r, SIG\(\ell\)r(Qr−1), H(Br−1)), et un bloc vide est de la forme Br ǫ = (r, \(\emptyset\), Qr−1, H(Br−1)). Notez qu'un bloc non vide peut toujours contenir un ensemble de paie PAY r vide, si aucun paiement n'a lieu dans ce tour ou si le leader est malveillant. Cependant, un bloc non vide implique que l'identité de \(\ell\)r, son titre \(\sigma\)r,1 \(\ell\)r et SIG\(\ell\)r(Qr−1) ont tous été révélés en temps opportun. Le protocole garantit que si le leader est honnête, alors le bloc ne sera pas vide avec une écrasante probabilité. • Semences Qr. Si Br est non vide, alors Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), sinon Qr \(\triangleq\)H(Qr−1, r). Paramètres • Relations entre divers paramètres. — Les vérificateurs et leaders potentiels du tour r sont sélectionnés parmi les utilisateurs de PKr−k, où k est choisi de telle sorte que l'Adversaire ne puisse pas prédire Qr−1 au tour r −k −1 avec une probabilité meilleure que F : sinon, il pourra introduire des utilisateurs malveillants pour le tour r −k, qui seront tous des leaders/vérificateurs potentiels au tour r, réussissant à

avoir un leader malveillant ou une majorité malveillante dans SV r,s pour certaines étapes souhaitées par lui. — Pour l'étape 1 de chaque tour r, n1 est choisi de telle sorte que, avec une très forte probabilité, SV r,1 ̸= \(\emptyset\). • Exemples de choix de paramètres importants. — Les sorties de H ont une longueur de 256 bits. — h = 80 %, n1 = 35. — Λ = 1 minute et \(\lambda\) = 10 secondes. • Initialisation du protocole. Le protocole démarre au temps 0 avec r = 0. Puisqu'il n'existe pas de « B−1 » ou de « CERT −1 », syntaxiquement, B−1 est un paramètre public avec son troisième composant spécifiant Q−1, et tous les utilisateurs connaître B−1 au temps 0.

Algorand ′

1 Dans cette section, nous construisons une version de Algorand ′ fonctionnant sous l'hypothèse suivante. Hypothèse de la majorité honnête des utilisateurs : plus des 2/3 des utilisateurs de chaque PKr sont honnêtes. Dans la section 8, nous montrons comment remplacer l'hypothèse ci-dessus par la majorité honnête souhaitée des Hypothèse monétaire. 5.1 Notations et paramètres supplémentaires Notations • m \(\in\)Z+ : le nombre maximum d'étapes dans le protocole binaire BA, un multiple de 3. • Lr \(\leq\)m/3 : une variable aléatoire représentant le nombre d'essais de Bernoulli nécessaires pour voir un 1, lorsque chaque essai vaut 1 avec probabilité ph 2 et il y a au plus des essais m/3. Si tous les essais échouent alors Lr\(\triangleq\)m/3. Lr sera utilisé pour limiter le temps nécessaire à la génération du bloc Br. • tH = 2n 3 + 1 : le nombre de signatures nécessaires dans les conditions finales du protocole. • CERT r : le certificat du Br. Il s’agit d’un ensemble de signatures de H(Br) provenant de vérificateurs appropriés dans rond r. Paramètres • Relations entre divers paramètres. — Pour chaque étape s > 1 du tour r, n est choisi de telle sorte que, avec une écrasante probabilité, |HSVr,s| > 2|MSVr,s| et |HSVr,s| + 4|MSVr,s| <2n. Plus la valeur de h est proche de 1, plus n doit être petit. En particulier, nous utilisons (variantes de) Tchernofflimite pour garantir que les conditions souhaitées soient maintenues avec une écrasante probabilité. — m est choisi tel que Lr < m/3 avec une probabilité écrasante. • Exemples de choix de paramètres importants. — F = 10−12. — n \(\approx\)1500, k = 40 et m = 180.5.2 Implémentation de clés éphémères dans Algorand ′ 1 Comme déjà mentionné, nous souhaitons qu'un vérificateur i \(\in\)SV r,s signe numériquement son message mr,s je de pas s dans le tour r, par rapport à une clé publique éphémère pkr,s i , en utilisant une clé secrète éphémère skr,s je que il détruit rapidement après utilisation. Nous avons donc besoin d'une méthode efficace pour garantir que chaque utilisateur puisse vérifier que pkr,s je est bien la clé à utiliser pour vérifier la signature de mr,s je. Nous le faisons par un (au mieux de nos connaissances) nouvelle utilisation de schémas de signature basés sur l'identité. A un niveau élevé, dans un tel schéma, une autorité centrale A génère une clé principale publique, PMK, et une clé principale secrète correspondante, SMK. Étant donné l’identité U d’un joueur U, A calcule : via SMK, une clé de signature secrète skU relative à la clé publique U, et donne en privé la skU à U. (En effet, dans un schéma de signature numérique basé sur l'identité, la clé publique d'un utilisateur U est U lui-même !) De cette façon, si A détruit SMK après avoir calculé les clés secrètes des utilisateurs qu'il souhaite permettre à produit des signatures numériques, et ne conserve aucune clé secrète calculée, alors U est le seul à pouvoir peut signer numériquement des messages relatifs à la clé publique U. Ainsi, toute personne connaissant le « nom de U », connaît automatiquement la clé publique de U et peut ainsi vérifier les signatures de U (éventuellement en utilisant également le clé principale publique PMK). Dans notre application, l’autorité A est l’utilisateur i, et l’ensemble de tous les utilisateurs possibles U coïncide avec la paire de pas ronds (r, s) dans —disons— S = {i}\(\times\){r′, . . . , r′ +106}\(\times\){1, . . . , m+3}, où r′ est une donnée tour, et m + 3 la limite supérieure du nombre d'étapes pouvant se produire au cours d'un tour. Ceci façon, pkr,s je \(\triangleq\)(i, r, s), pour que tout le monde voie la signature de i SIGr,s pkr,s je (madame, s je ) peux, avec écrasante probabilité, vérifiez-la immédiatement pour le premier million de tours r suivant r′. En d’autres termes, je génère d’abord PMK et SMK. Ensuite, il annonce que PMK est mon maître. clé publique pour n'importe quel tour r \(\in\)[r′, r′ + 106], et utilise SMK pour produire et stocker le secret en privé clé skr,s je pour chaque triplet (i, r, s) \(\in\)S. Ceci fait, il détruit SMK. S'il détermine qu'il n'est pas une partie de SV r,s, alors je peux quitter skr,s je seul (car le protocole n'exige pas qu'il authentifie n'importe quel message dans les étapes s du tour r). Sinon, j'utilise d'abord skr,s je signer numériquement son message mr,s moi, et puis détruit skr,s je. Notez que je peux publier sa première clé principale publique lors de sa première entrée dans le système. C'est-à-dire le même paiement \(\wp\)qui amène i dans le système (à un tour r′ ou à un tour proche de r′), peut aussi spécifier, à la demande de i, que la clé principale publique de i pour tout tour r \(\in\)[r′, r′ + 106] est PMK — par exemple, par incluant une paire de la forme (PMK, [r′, r′ + 106]). Notez également que, puisque m + 3 est le nombre maximum de pas dans un tour, en supposant qu'un tour Cela prend une minute, la réserve de clés éphémères ainsi produite durera près de deux ans. En même temps Avec le temps, ces clés secrètes éphémères ne prendront pas trop de temps à produire. Utilisation d'une courbe elliptique basée système avec 32B clés, chaque clé secrète est calculée en quelques microsecondes. Ainsi, si m + 3 = 180, alors toutes les 180 millions de clés secrètes peuvent être calculées en moins d’une heure. Lorsque le tour en cours se rapproche de r′ + 106, pour gérer le prochain million de tours, je génère une nouvelle paire (PMK′, SMK′) et informe quelle est sa prochaine réserve de clés éphémères en -par exemple- demander à SIGi(PMK′, [r′ + 106 + 1, r′ + 2 \(\cdot\) 106 + 1]) d'entrer un nouveau bloc, soit en tant que une « transaction » distincte ou des informations supplémentaires faisant partie d’un paiement. Ce faisant, J'informe tout le monde qu'il doit utiliser PMK′ pour vérifier mes signatures éphémères dans le prochain millions de tours. Et ainsi de suite. (Notez que, en suivant cette approche de base, d'autres moyens d'implémenter des clés éphémères sans l’utilisation de signatures basées sur l’identité est certainement possible. Par exemple, via Merkle trees.16) 16Dans cette méthode, je génère une paire de clés secrètes publiques (pkr,s je, skr,s je ) pour chaque paire d'étapes rondes (r, s) dans —disons—D'autres moyens d'implémenter des clés éphémères sont certainement possibles, par exemple via Merkle trees. 5.3 Correspondant aux étapes de Algorand ′ 1 avec ceux de BA⋆ Comme nous l'avons dit, un tour dans Algorand ′ 1 comporte au plus m + 3 marches. Étape 1. Dans cette étape, chaque leader potentiel i calcule et propage son bloc candidat Br je, avec son propre identifiant, \(\sigma\)r,1 je. Rappelons que ce titre identifie explicitement i. Il en est ainsi, car \(\sigma\)r,1 je \(\triangleq\)SIGi(r, 1, Qr−1). Le vérificateur potentiel i propage également, dans le cadre de son message, sa propre signature numérique de H(Br je ). Ne s'agissant ni d'un paiement ni d'un accréditif, cette signature de i est relative à son public éphémère clé pkr,1 i : c'est-à-dire qu'il propage sigpkr,1 je (H(Br je )). Compte tenu de nos conventions, plutôt que de propager Br je et sigpkr,1 je (H(Br i )), il aurait pu SIGpkr propagé,1 je (H(Br je )). Cependant, dans notre analyse, nous devons avoir un accès explicite à sigpkr,1 je (H(Br je )). Étapes 2. Dans cette étape, chaque vérificateur i définit \(\ell\)r je dois être le leader potentiel dont le titre hashed est le plus petit, et Br je suis le bloc proposé par \(\ell\)r je. Puisque, dans un souci d'efficacité, nous souhaite s'entendre sur H(Br), plutôt que directement sur Br, je propage le message qu'il aurait propagé dans la première étape de BA⋆avec la valeur initiale v′ je = H(Br je ). Autrement dit, il propage v′ moi, après l’avoir signé éphémèrement, bien entendu. (A savoir, après l'avoir signé par rapport au droit éphémère clé publique, qui dans ce cas est pkr,2 i .) Bien sûr aussi, je transmets également son propre identifiant. Puisque la première étape de BA⋆ consiste en la première étape du protocole de consensus gradué GC, l’étape 2 de Algorand ′ correspond à la première étape de GC. Étapes 3. Dans cette étape, chaque vérificateur i \(\in\)SV r,2 exécute la deuxième étape de BA⋆. Autrement dit, il envoie le même message qu’il aurait envoyé lors de la deuxième étape de GC. Encore une fois, mon message est éphémère signé et accompagné de mes identifiants. (Nous omettons désormais de dire qu'un vérificateur signe éphémèrement son message et propage également ses informations d'identification.) Étape 4. Dans cette étape, chaque vérificateur i \(\in\)SV r,4 calcule la sortie de GC, (vi, gi), et éphémèrement signe et envoie le même message qu'il aurait envoyé à la troisième étape de BA⋆, c'est-à-dire dans le première étape de BBA⋆, avec le bit initial 0 si gi = 2, et 1 sinon. Étape s = 5, . . . , m + 2. Un tel pas, si jamais atteint, correspond au pas s −1 de BA⋆, et donc à étape s −3 de BBA⋆. Puisque notre modèle de propagation est suffisamment asynchrone, nous devons tenir compte de la possibilité qu'au milieu d'une telle étape s, un vérificateur i \(\in\)SV r,s est atteint par une information lui prouvant ce bloc Br a déjà été choisi. Dans ce cas, j'arrête sa propre exécution du tour r de Algorand ′, et commence à exécuter ses instructions round-(r + 1). {r', . . . , r′ + 106} \(\times\) {1, . . . , m + 3}. Puis il ordonne ces clés publiques de manière canonique, stocke la jème clé publique saisissez la jème feuille d'un Merkle tree et calcule la valeur racine Ri, qu'il publie. Quand il veut signer un message relatif à la clé pkr,s je , je fournis non seulement la signature réelle, mais également le chemin d'authentification pour pkr,s je par rapport à Ri. Notez que ce chemin d'authentification prouve également que pkr,s je est stocké dans la jème feuille. Le reste du les détails peuvent être facilement remplis.En conséquence, les instructions d’un vérificateur i \(\in\)SV r,s, en plus des instructions correspondant à l'étape s −3 de BBA⋆, inclure la vérification si l'exécution de BBA⋆ s'est arrêtée dans un précédent Étapes s′. Puisque BBA⋆ne peut s'arrêter que dans une étape Coin-Fixed-to-0 ou dans une étape Coin-Fixed-to-1, le les instructions distinguent si A (Condition de fin 0) : s′ −2 ≡0 mod 3, ou B (Condition de fin 1) : s′ −2 ≡1 mod 3. En fait, dans le cas A, le bloc Br n'est pas vide, et donc des instructions supplémentaires sont nécessaires pour m'assurer que i reconstruit correctement Br, avec son certificat approprié CERT r. Dans le cas B, le bloc Br est vide, et donc je dois définir Br = Br \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), et pour calculer CERT r. Si, lors de l'exécution de l'étape s, je ne vois aucune preuve que le bloc Br a déjà été généré, alors il envoie le même message qu’il aurait envoyé à l’étape s −3 de BBA⋆. Étape m + 3. Si, lors de l'étape m + 3, i \(\in\)SV r,m+3 voit que le bloc Br a déjà été généré dans une étape préalable s', puis il procède comme expliqué ci-dessus. Sinon, plutôt que d'envoyer le même message qu'il aurait envoyé à l'étape m de BBA⋆, i est chargé, sur la base des informations en sa possession, de calculer Br et son correspondant certificat CERT r. Rappelons en effet que nous majorons de m + 3 le nombre total d'étapes d'un tour. 5.4 Le protocole actuel Rappelons qu'à chaque étape s d'un tour r, un vérificateur i \(\in\)SV r,s utilise sa paire de clés secrètes publiques à long terme pour produire son titre, \(\sigma\)r,s je \(\triangleq\)SIGi(r, s, Qr−1), ainsi que SIGi Qr−1 dans le cas s = 1. Vérificateur i utilise sa clé secrète éphémère skr,s je signer son (r, s)-message mr,s je. Par souci de simplicité, lorsque r et s sont clair, on écrit esigi(x) plutôt que sigpkr,s i (x) pour désigner la signature éphémère propre d'une valeur x à l'étape s du tour r, et écrivez ESIGi(x) au lieu de SIGpkr,s i (x) pour désigner (i, x, esigi(x)). Étape 1 : Bloquer la proposition Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 1 du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,1 ou non. • Si i /\(\in\)SV r,1, alors i arrête immédiatement sa propre exécution de l'étape 1. • Si i \(\in\)SV r,1, c'est-à-dire si i est un leader potentiel, alors il perçoit les paiements ronds r qui ont lui a été propagé jusqu'à présent et calcule un ensemble de paie maximal PAY r je d'eux. Ensuite, il calcule son « bloc candidat » Br je = (r, PAYER r je , SIGi(Qr−1), H(Br−1)). Finalement, il calcule le message monsieur,1 je = (Br je , esigi(H(Br je )), \(\sigma\)r,1 i ), détruit sa clé secrète éphémère skr,1 moi, et puis propage mr,1 je.Remarque. En pratique, pour raccourcir l’exécution globale de l’étape 1, il est important que le (r, 1)- les messages sont propagés de manière sélective. Autrement dit, pour chaque utilisateur i dans le système, pour le premier (r, 1)- message qu'il reçoit et vérifie avec succès17, le joueur i le propage comme d'habitude. Pour tous les autres (r, 1)-messages que le joueur i reçoit et vérifie avec succès, il ne les propage que si le hash la valeur des informations d'identification qu'il contient est la plus petite parmi les valeurs hash des informations d'identification contenues dans tous les messages (r, 1) qu'il a reçus et vérifiés avec succès jusqu'à présent. De plus, comme suggéré par Georgios Vlachos, il est utile que chaque leader potentiel i propage également son accréditation \(\sigma\)r,1 je séparément : ces petits messages voyagent plus rapidement que les blocs, assurent une propagation rapide du mr,1 j's où les informations d'identification contenues ont de petites valeurs hash, tandis que celles avec de grandes valeurs hash disparaître rapidement. Étape 2 : La première étape du protocole de consensus gradué GC Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 2 du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,2 ou non. • Si i /\(\in\)SV r,2 alors i arrête immédiatement sa propre exécution de l'étape 2. • Si i \(\in\)SV r,2, alors après avoir attendu un temps t2 \(\triangleq\) \(\lambda\) + Λ, i agit comme suit. 1. Il trouve l’utilisateur \(\ell\)tel que H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) pour tous les pouvoirs \(\sigma\)r,1 j qui font partie de les messages (r, 1) vérifiés avec succès qu'il a reçus jusqu'à présent.a 2. S'il a reçu de \(\ell\)un message valide mr,1 \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),b alors je définis v′ je \(\triangleq\)H(Br \(\ell\)); sinon je mets v′ je \(\triangleq\) \(\bot\). 3. je calcule le message mr,2 je \(\triangleq\)(ESIGi(v′ je), \(\sigma\)r,2 i ),c détruit sa clé secrète éphémère skr,2 i , puis propage mr,2 je. aEssentiellement, l'utilisateur i décide en privé que le leader du tour r est l'utilisateur \(\ell\). bEncore une fois, les signatures du joueur \(\ell\) et les hashes sont tous vérifiés avec succès, et PAY r \(\ell\)en Br \(\ell\)est un ensemble de paie valide pour round r — bien que je ne vérifie pas si PAY r \(\ell\)est maximal pour \(\ell\)ou non. cLe message monsieur,2 je signale que le joueur que je considère comme v′ je suis le hash du bloc suivant, ou considère le prochain le bloc doit être vide. 17C'est-à-dire que toutes les signatures sont correctes et que le bloc et son hash sont valides - même si je ne vérifie pas si le salaire inclus est maximal pour son proposant ou non.

Étape 3 : la deuxième étape du GC Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 3 du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,3 ou non. • Si i /\(\in\)SV r,3, alors i arrête immédiatement sa propre exécution de l'étape 3. • Si i \(\in\)SV r,3, alors après avoir attendu un temps t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ, i agit comme suit. 1. S’il existe une valeur v′ ̸= \(\bot\)telle que, parmi tous les messages valides mr,2 j il a reçu, plus des 2/3 d’entre eux sont de la forme (ESIGj(v′), \(\sigma\)r,2 j ), sans aucune contradiction,a puis il calcule le message mr,3 je \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 je ). Sinon, il calcule mr,3 je \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 je ). 2. je détruit sa clé secrète éphémère skr,3 i , puis propage mr,3 je. aC'est-à-dire qu'il n'a pas reçu deux messages valides contenant respectivement ESIGj(v′) et un ESIGj(v′′) différent, d'un joueur j. Ici et à partir de là, sauf dans les Conditions de Fin définies plus loin, chaque fois qu'un joueur honnête veut des messages d'une forme donnée, les messages se contredisant ne sont jamais comptés ni considérés comme valides.Étape 4 : Résultat de GC et première étape de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 4 du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,4 ou non. • Si i /\(\in\)SV r,4, alors i his arrête immédiatement sa propre exécution de l'étape 4. • Si i \(\in\)SV r,4, alors après avoir attendu un temps t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ, i agit comme suit. 1. Il calcule vi et gi, la sortie de GC, comme suit. (a) S’il existe une valeur v′ ̸= \(\bot\)telle que, parmi tous les messages valides mr,3 j il a reçus, plus des 2/3 d’entre eux sont de la forme (ESIGj(v′), \(\sigma\)r,3 j ), puis il pose vi \(\triangleq\)v′ et gi \(\triangleq\)2. (b) Sinon, s'il existe une valeur v′ ̸= \(\bot\)telle que, parmi tous les messages valides monsieur,3 j qu'il a reçu, plus de 1/3 d'entre eux sont de la forme (ESIGj(v′), \(\sigma\)r,3 j), alors il pose vi \(\triangleq\)v′ et gi \(\triangleq\)1.a (c) Sinon, il pose vi \(\triangleq\)H(Br ǫ ) et gi \(\triangleq\)0. 2. Il calcule bi, l’entrée de BBA⋆, comme suit : bi \(\triangleq\)0 si gi = 2, et bi \(\triangleq\)1 sinon. 3. Il calcule le message mr,4 je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), détruit son éphémère clé secrète skr,4 i , puis propage mr,4 je. aOn peut prouver que le v′ dans le cas (b), s’il existe, doit être unique.

Étape s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3 : Une étape fixée à 0 de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape s du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,s. • Si i /\(\in\)SV r,s, alors i arrête immédiatement sa propre exécution du Step s. • Si i \(\in\)SV r,s alors il agit comme suit. – Il attend qu’un laps de temps ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ se soit écoulé. – Condition de fin 0 : si, pendant cette attente et à tout moment, il existe un chaîne v ̸= \(\bot\)et une étape s′ telle que (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 — c'est-à-dire que l'étape s′ est une étape Coin-Fixed-To-0, (b) j'ai reçu au moins le = 2n 3 + 1 messages valides mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),a et (c) j'ai reçu un message valide mr,1 j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) avec v = H(Br j), puis, j'arrête immédiatement sa propre exécution du Step s (et en fait du tour r) sans propager quoi que ce soit ; ensembles Br = Br j ; et définit son propre CERT r comme l'ensemble des messages monsieur,s′−1 j de la sous-étape (b).b – Condition finale 1 : Si, pendant cette attente et à tout moment, il existe un étape telle que (a') 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 — c'est-à-dire que l'étape s′ est une étape Coin-Fixed-To-1, et (b’) j’ai reçu au moins les messages valides mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),c puis, j'arrête immédiatement sa propre exécution du Step s (et en fait du tour r) sans propager quoi que ce soit ; ensembles Br = Br ǫ ; et définit son propre CERT r comme l'ensemble des messages monsieur,s′−1 j de la sous-étape (b’). – Sinon, à la fin de l’attente, l’utilisateur i effectue la procédure suivante. Il définit vi comme étant le vote majoritaire des vj dans les secondes composantes de tous les votes valides. monsieur,s−1 j c’est ce qu’il a reçu. Il calcule bi comme suit. Si plus des 2/3 de tous les mr,s−1 valides j 's qu'il a reçu sont de la forme (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il pose bi \(\triangleq\)0. Sinon, si plus des 2/3 de tous les mr,s−1 valides j 's qu'il a reçu sont de la forme (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il pose bi \(\triangleq\)1. Sinon, il définit bi \(\triangleq\)0. Il calcule le message mr,s je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), détruit son éphémère clé secrète skr,s i , puis propage mr,s je. aUn tel message du joueur j est compté même si le joueur i a également reçu un message de j signant pour 1. Des choses similaires pour la condition finale 1. Comme le montre l'analyse, cela est fait pour garantir que tous les utilisateurs honnêtes savent Br dans le temps \(\lambda\) les uns des autres. bUtilisateur i connaît maintenant Br et ses propres finitions de tour r. Il aide toujours à propager des messages en tant qu'utilisateur générique, mais n’initie aucune propagation en tant que vérificateur (r, s). Il a notamment contribué à propager tous les messages dans son CERT r, ce qui est suffisant pour notre protocole. Notez qu'il doit également définir bi \(\triangleq\)0 pour le protocole binaire BA, mais bi n'est de toute façon pas nécessaire dans ce cas. Des choses similaires pour toutes les instructions futures. cDans ce cas, peu importe les vj.Étape s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3 : Une étape Coin-Fixed-To-1 de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape s du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,s ou non. • Si i /\(\in\)SV r,s, alors i arrête immédiatement sa propre exécution du Step s. • Si i \(\in\)SV r,s alors il fait ce qui suit. – Il attend qu’un laps de temps ts \(\triangleq\)(2s −3)\(\lambda\) + Λ se soit écoulé. – Condition de fin 0 : les mêmes instructions que les étapes Coin-Fixed-To-0. – Condition de fin 1 : les mêmes instructions que les étapes Coin-Fixed-To-0. – Sinon, à la fin de l’attente, l’utilisateur i effectue la procédure suivante. Il définit vi comme étant le vote majoritaire des vj dans les secondes composantes de tous les votes valides. monsieur,s−1 j c’est ce qu’il a reçu. Il calcule bi comme suit. Si plus des 2/3 de tous les mr,s−1 valides j 's qu'il a reçu sont de la forme (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il pose bi \(\triangleq\)0. Sinon, si plus des 2/3 de tous les mr,s−1 valides j 's qu'il a reçu sont de la forme (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il pose bi \(\triangleq\)1. Sinon, il définit bi \(\triangleq\)1. Il calcule le message mr,s je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), détruit son éphémère clé secrète skr,s i , puis propage mr,s je.

Étape s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3 : Une étape véritablement inversée de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape s du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,s ou non. • Si i /\(\in\)SV r,s, alors i arrête immédiatement sa propre exécution du Step s. • Si i \(\in\)SV r,s alors il fait ce qui suit. – Il attend qu’un laps de temps ts \(\triangleq\)(2s −3)\(\lambda\) + Λ se soit écoulé. – Condition de fin 0 : les mêmes instructions que les étapes Coin-Fixed-To-0. – Condition de fin 1 : les mêmes instructions que les étapes Coin-Fixed-To-0. – Sinon, à la fin de l’attente, l’utilisateur i effectue la procédure suivante. Il définit vi comme étant le vote majoritaire des vj dans les secondes composantes de tous les votes valides. monsieur,s−1 j c’est ce qu’il a reçu. Il calcule bi comme suit. Si plus des 2/3 de tous les mr,s−1 valides j 's qu'il a reçu sont de la forme (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il pose bi \(\triangleq\)0. Sinon, si plus des 2/3 de tous les mr,s−1 valides j 's qu'il a reçu sont de la forme (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il pose bi \(\triangleq\)1. Sinon, soit SV r,s−1 je être l’ensemble des (r, s −1)-vérificateurs dont il a reçu un message mr,s−1 j . Il pose bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 je H(\(\sigma\)r,s−1 j )). Il calcule le message mr,s je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), détruit son éphémère clé secrète skr,s i , puis propage mr,s je.

Étape m + 3 : La dernière étape de BBA⋆a Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape m + 3 du tour r dès qu'il connaît Br−1. • L'utilisateur i calcule Qr−1 à partir de la troisième composante de Br−1 et vérifie si i \(\in\)SV r,m+3 ou non. • Si i /\(\in\)SV r,m+3, alors i arrête immédiatement sa propre exécution de l'étape m + 3. • Si i \(\in\)SV r,m+3 alors il fait ce qui suit. – Il attend qu’un laps de temps tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ se soit écoulé. – Condition de fin 0 : les mêmes instructions que les étapes Coin-Fixed-To-0. – Condition de fin 1 : les mêmes instructions que les étapes Coin-Fixed-To-0. – Sinon, à la fin de l’attente, l’utilisateur i effectue la procédure suivante. Il énonce outi \(\triangleq\)1 et Br \(\triangleq\)Br ǫ. Il calcule le message mr,m+3 je = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 je ), détruit son clé secrète éphémère skr,m+3 je , puis propage mr,m+3 je certifier Br.b aIl est très probable que BBA⋆ se soit terminé avant cette étape, et nous spécifions cette étape par souci d’exhaustivité. bUn certificat de l'étape m + 3 ne doit pas nécessairement inclure ESIGi(outi). Nous l'incluons uniquement par souci d'uniformité : le les certificats ont désormais un format uniforme quelle que soit l'étape à laquelle ils sont générés.Reconstruction du bloc Round-r par des non-vérificateurs Instructions pour chaque utilisateur i dans le système : L'utilisateur i démarre son propre tour r dès qu'il le sait Br−1, et attend les informations de bloc comme suit. – Si, pendant cette attente et à tout instant, il existe une chaîne v et une étape s′ telle que (a) 5 \(\leq\)s′ \(\leq\)m + 3 avec s′ −2 ≡0 mod 3, (b) j’ai reçu au moins les messages valides mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ), et (c) j'ai reçu un message valide mr,1 j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) avec v = H(Br j), puis, j'arrête immédiatement sa propre exécution du tour r ; ensembles Br = Br j; et définit son propre CERT r être l’ensemble des messages mr,s′−1 j de la sous-étape (b). – Si, au cours de cette attente et à tout instant, il existe une étape s′ telle que (a’) 6 \(\leq\)s′ \(\leq\)m + 3 avec s′ −2 ≡1 mod 3, et (b’) j’ai reçu au moins les messages valides mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ), puis, j'arrête immédiatement sa propre exécution du tour r ; ensembles Br = Br ǫ; et définit son propre CERT r être l’ensemble des messages mr,s′−1 j de la sous-étape (b’). – Si, pendant cette attente et à tout moment, j’ai reçu au moins les messages valides monsieur, m+3 j = (ESIGj(1), ESIGj(H(Br ǫ )), \(\sigma\)r,m+3 j ), puis j'arrête sa propre exécution du tour r tout de suite, définit Br = Br ǫ , et définit son propre CERT r comme étant l'ensemble des messages mr,m+3 j pour 1 et H(Br ǫ ). 5.5 Analyse de Algorand′ 1 Nous introduisons les notations suivantes pour chaque tour r \(\geq\)0, utilisées dans l'analyse. • Soit T r l'instant où le premier utilisateur honnête connaît Br−1. • Soit Ir+1 l'intervalle [T r+1, T r+1 + \(\lambda\)]. Notons que T 0 = 0 par l'initialisation du protocole. Pour chaque s \(\geq\)1 et i \(\in\)SV r,s, rappelons que \(\alpha\)r,s je et \(\beta\)r,s je sont respectivement l’heure de début et l’heure de fin de l’étape s du joueur i. De plus, rappelons que ts = (2s −3)\(\lambda\) + Λ pour chaque 2 \(\leq\)s \(\leq\)m + 3. De plus, soit I0 \(\triangleq\){0} et t1 \(\triangleq\)0. Rappelons enfin que Lr \(\leq\)m/3 est une variable aléatoire représentant le nombre d'essais de Bernoulli nécessaire pour voir un 1, lorsque chaque essai est 1 avec une probabilité ph 2 et il y a au plus des essais m/3. Si tout les essais échouent alors Lr \(\triangleq\)m/3. Dans l’analyse, nous ignorons le temps de calcul, car il est en fait négligeable par rapport au temps nécessaire pour propager des messages. Dans tous les cas, en utilisant \(\lambda\) et Λ légèrement plus grands, le temps de calcul peut être directement intégré à l’analyse. La plupart des déclarations ci-dessous sont valables « avec une écrasante majorité » probabilité », et nous ne pouvons pas insister à plusieurs reprises sur ce fait dans l’analyse.5.6 Théorème principal Théorème 5.1. Les propriétés suivantes sont vérifiées avec une écrasante probabilité pour chaque tour r \(\geq\)0 : 1. Tous les utilisateurs honnêtes sont d'accord sur le même bloc Br. 2. Lorsque le leader \(\ell\)r est honnête, le bloc Br est généré par \(\ell\)r, Br contient un ensemble de gains maximal reçu par \(\ell\)r à l'heure \(\alpha\)r,1 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ et tous les utilisateurs honnêtes connaissent Br à l'époque intervalle Ir+1. 3. Lorsque le leader \(\ell\)r est malveillant, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ et tous les utilisateurs honnêtes savent Br dans l'intervalle de temps Ir+1. 4. ph = h2(1 + h −h2) pour Lr, et le leader \(\ell\)r est honnête avec une probabilité d'au moins ph. Avant de démontrer notre théorème principal, faisons deux remarques. Remarques. • Génération de blocs et latence réelle. Le temps pour générer le bloc Br est défini comme étant T r+1 −T r. Autrement dit, il s'agit de la différence entre la première fois qu'un utilisateur honnête apprend Br et c'est la première fois qu'un utilisateur honnête apprend Br−1. Lorsque le leader du round-r est honnête, Property 2 notre le théorème principal garantit que le temps exact pour générer Br est le temps 8\(\lambda\) + Λ, quoi qu'il arrive la valeur précise de h > 2/3 peut l'être. Lorsque le leader est malveillant, la propriété 3 implique que le le temps prévu pour générer Br est limité par ( 12 ph + 10)\(\lambda\) + Λ, encore une fois, quelle que soit la précision valeur de h.18 Cependant, le temps attendu pour générer Br dépend de la valeur précise de h. En effet, par la Propriété 4, ph = h2(1 + h −h2) et le leader est honnête avec probabilité au moins ph, donc E[T r+1 −T r] \(\leq\)h2(1 + h −h2) \(\cdot\) (8\(\lambda\) + Λ) + (1 −h2(1 + h −h2))(( 12 h2(1 + h −h2) + 10)\(\lambda\) + Λ). Par exemple, si h = 80 %, alors E[T r+1 −T r] \(\leq\)12,7\(\lambda\) + Λ. • \(\lambda\) contre Λ. A noter que la taille des messages envoyés par les vérificateurs dans une étape Algorand ′ est dominée par la longueur des clés de signature numérique, qui peut rester fixe, même lorsque le nombre de les utilisateurs sont énormes. Notez également que, à toute étape s > 1, le même nombre attendu n de vérificateurs peut être utilisé que le nombre d'utilisateurs soit de 100 000, 100 M ou 100 M. Il en est ainsi parce que n uniquement dépend de h et F. En résumé, donc, à moins d'un besoin soudain d'augmenter la longueur de la clé secrète, la valeur de \(\lambda\) doit rester la même, quel que soit le nombre d'utilisateurs dans le avenir prévisible. En revanche, quel que soit le taux de transaction, le nombre de transactions augmente avec le nombre de transactions. utilisateurs. Par conséquent, pour traiter toutes les nouvelles transactions en temps opportun, la taille d'un bloc doit augmente également avec le nombre d'utilisateurs, ce qui entraîne une croissance de Λ également. Ainsi, à long terme, nous aurions dû \(\lambda\) << Λ. En conséquence, il convient d’avoir un coefficient plus grand pour \(\lambda\), et en réalité un coefficient de 1 pour Λ. Preuve du théorème 5.1. Nous prouvons les propriétés 1 à 3 par récurrence : en supposant qu'elles soient valables pour le tour r −1 (sans perte de généralité, ils sont automatiquement valables pour le « tour -1 » lorsque r = 0), on les prouve pour rond r. 18En effet, E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ.Puisque Br−1 est défini de manière unique par l’hypothèse inductive, l’ensemble SV r,s est défini de manière unique pour chaque étape s du tour r. Par le choix de n1, SV r,1 ̸= \(\emptyset\)avec une écrasante probabilité. Nous maintenant énoncer les deux lemmes suivants, prouvés dans les sections 5.7 et 5.8. Tout au long de l'intégration et dans les preuves des deux lemmes, l'analyse pour le tour 0 est presque la même que l'étape inductive, et nous mettrons en évidence les différences lorsqu'elles se produiront. Lemme 5.2. [Lemme d'exhaustivité] En supposant que les propriétés 1 à 3 soient valables pour le tour r−1, lorsque le leader \(\ell\)r est honnête, avec une écrasante probabilité, • Tous les utilisateurs honnêtes s'accordent sur le même bloc Br, qui est généré par \(\ell\)r et contient un maximum ensemble de paie reçu par \(\ell\)r à l'heure \(\alpha\)r,1 \(\ell\)r \(\in\)Ir ; et • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ et tous les utilisateurs honnêtes connaissent Br dans l'intervalle de temps Ir+1. Lemme 5.3. [Lemme de solidité] En supposant que les propriétés 1 à 3 soient valables pour le tour r −1, lorsque le leader \(\ell\)r est malveillant, avec une probabilité écrasante, tous les utilisateurs honnêtes sont d'accord sur le même bloc Br, T r+1 \(\leq\) T r + (6Lr + 10)\(\lambda\) + Λ et tous les utilisateurs honnêtes connaissent Br dans l'intervalle de temps Ir+1. Les propriétés 1 à 3 sont vérifiées en appliquant les lemmes 5.2 et 5.3 à r = 0 et à l'étape inductive. Enfin, nous reformulons la propriété 4 comme le lemme suivant, prouvé dans la section 5.9. Lemme 5.4. Étant donné les propriétés 1 à 3 pour chaque tour avant r, ph = h2(1 + h −h2) pour Lr, et le le leader \(\ell\)r est honnête avec une probabilité d'au moins ph. En combinant les trois lemmes ci-dessus, le théorème 5.1 est valable. ■ Le lemme ci-dessous énonce plusieurs propriétés importantes concernant le tour r étant donné le caractère inductif hypothèse, et sera utilisé dans les preuves des trois lemmes ci-dessus. Lemme 5.5. Supposons que les propriétés 1 à 3 soient valables pour le tour r −1. Pour chaque étape s \(\geq\)1 du tour r et chaque vérificateur honnête i \(\in\)HSV r,s, nous avons cela (a) ar,s je \(\in\)Ir ; (b) si le joueur i a attendu un temps ts, alors \(\beta\)r,s je \(\in\)[T r + ts, T r + \(\lambda\) + ts] pour r > 0 et \(\beta\)r,s je = ts pour r = 0 ; et (c) si le joueur i a attendu un temps ts, alors au temps \(\beta\)r,s moi, il a reçu tous les messages envoyé par tous les vérificateurs honnêtes j \(\in\)HSV r,s′ pour toutes les étapes s′ < s. De plus, pour chaque pas s \(\geq\)3, on a que (d) il n’existe pas deux joueurs différents i, i′ \(\in\)SV r,s et deux valeurs différentes v, v′ du même durée, de telle sorte que les deux joueurs ont attendu un temps ts, soit plus des 2/3 de tout le temps. messages valides mr,s−1 j joueur que je reçois a signé pour v, et plus des 2/3 de tous les joueurs valides messages mr,s−1 j le joueur que je reçois a signé pour v. Preuve. La propriété (a) découle directement de l’hypothèse inductive, puisque le joueur i connaît Br−1 dans le intervalle de temps Ir et démarre immédiatement son propre pas s. La propriété (b) découle directement de (a) : puisque joueur j'ai attendu un certain temps ts avant d'agir, \(\beta\)r,s je = \(\alpha\)r,s je + c.t. Notez que \(\alpha\)r,s je = 0 pour r = 0. Nous prouvons maintenant la propriété (c). Si s = 2, alors par la propriété (b), pour tous les vérificateurs j \(\in\)HSV r,1 nous avons \(\beta\)r,s je = \(\alpha\)r,s je + ts \(\geq\)T r + ts = T r + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 j + Λ.Puisque chaque vérificateur j \(\in\)HSV r,1 envoie son message à l’instant \(\beta\)r,1 j et le message atteint tous les honnêtes utilisateurs dans un temps Λ maximum, par temps \(\beta\)r,s je joueur, j'ai reçu les messages envoyés par tous les vérificateurs en HSV r,1 au choix. Si s > 2, alors ts = ts−1 + 2\(\lambda\). Par propriété (b), pour toutes les étapes s′ < s et tous les vérificateurs j \(\in\)HSV r,s′, \(\beta\)r,s je = \(\alpha\)r,s je + ts \(\geq\)T r + ts = T r + ts−1 + 2\(\lambda\) \(\geq\)T r + ts′ + 2\(\lambda\) = T r + \(\lambda\) + ts′ + \(\lambda\) \(\geq\) \(\beta\)r,s′ j + \(\lambda\). Puisque chaque vérificateur j \(\in\)HSV r,s′ envoie son message à l’instant \(\beta\)r,s′ j et le message atteint tous les honnêtes utilisateurs dans un temps \(\lambda\) maximum, par temps \(\beta\)r,s je joueur, j'ai reçu tous les messages envoyés par tous les vérificateurs honnêtes dans HSV r,s′ pour tout s′ < s. Ainsi la propriété (c) est vraie. Enfin, nous prouvons la propriété (d). Notons que les vérificateurs j \(\in\)SV r,s−1 signent au plus deux choses dans Étape s −1 utilisant leurs clés secrètes éphémères : une valeur vj de même longueur que la sortie du Fonction hash, et aussi un peu bj \(\in\){0, 1} si s −1 \(\geq\)4. C'est pourquoi dans l'énoncé du lemme nous exigeons que v et v′ aient la même longueur : de nombreux vérificateurs peuvent avoir signé tous les deux une valeur hash v et un bit b, passent donc tous les deux le seuil des 2/3. Supposons, par souci de contradiction, qu'il existe les vérificateurs i, i' et les valeurs v, v' souhaités. Notez que certains vérificateurs malveillants dans MSV r,s−1 peuvent avoir signé à la fois v et v′, mais chaque vérificateur honnête le vérificateur en HSV r,s−1 en a signé au plus un. Par la propriété (c), i et i′ ont tous deux reçu tous les messages envoyés par tous les vérificateurs honnêtes dans HSV r,s−1. Soit HSV r,s−1(v) l'ensemble des vérificateurs honnêtes de (r, s −1) qui ont signé v, MSV r,s−1 je l'ensemble de vérificateurs (r, s −1) malveillants de qui i a reçu un message valide, et MSV r,s−1 je (v) le sous-ensemble de MSV r,s−1 je de qui j'ai reçu un message valide signant v. Par les exigences pour i et v, nous avons rapport \(\triangleq\)|HSV r,s−1(v)| + |MSV r,s−1 je (v)| |HSVr,s−1| + |MSV r,s−1 je |

2 3. (1) Nous montrons d'abord |MSVr,s−1 je (v)| \(\leq\)|HSVr,s−1(v)|. (2) En supposant le contraire, d’après les relations entre les paramètres, avec une probabilité écrasante |HSVr,s−1| > 2|MSV r,s−1| \(\geq\)2|MSV r,s−1 je |, donc rapport < |HSV r,s−1(v)| + |MSV r,s−1 je (v)| 3|MSVr,s−1 je | < 2|MSV r,s−1 je (v)| 3|MSVr,s−1 je | \(\leq\)2 3, contredisant l’inégalité 1. Ensuite, par inégalité 1, nous avons 2|HSVr,s−1| + 2|MSVr,s−1 je | < 3|HSVr,s−1(v)| + 3|MSV r,s−1 je (v)| \(\leq\) 3|HSVr,s−1(v)| + 2|MSVr,s−1 je | + |MSV r,s−1 je (v)|. En combinant avec Inégalité 2, 2|HSVr,s−1| < 3|HSVr,s−1(v)| + |MSV r,s−1 je (v)| \(\leq\)4|HSVr,s−1(v)|, ce qui implique |HSVr,s−1(v)| > 1 2|HSVr,s−1|.De même, d’après les exigences pour i′ et v′, nous avons |HSVr,s−1(v′)| > 1 2|HSVr,s−1|. Puisqu’un vérificateur honnête j \(\in\)HSV r,s−1 détruit sa clé secrète éphémère skr,s−1 j avant de se propager son message, l’Adversaire ne peut pas falsifier la signature de j pour une valeur que j n’a pas signée, après apprendre que j est un vérificateur. Ainsi, les deux inégalités ci-dessus impliquent |HSV r,s−1| \(\geq\)|HSVr,s−1(v)| + |HSVr,s−1(v′)| > |HSV r,s−1|, une contradiction. En conséquence, les i, i', v, v' souhaités n'existent pas, et La propriété (d) est détenue. ■ 5.7 Le lemme de complétude Lemme 5.2. [Lemme d'exhaustivité, reformulé] En supposant que les propriétés 1 à 3 soient valables pour le tour r−1, lorsque le leader \(\ell\)r est honnête, avec une probabilité écrasante, • Tous les utilisateurs honnêtes s'accordent sur le même bloc Br, qui est généré par \(\ell\)r et contient un maximum ensemble de paie reçu par \(\ell\)r à l'heure \(\alpha\)r,1 \(\ell\)r \(\in\)Ir ; et • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ et tous les utilisateurs honnêtes connaissent Br dans l'intervalle de temps Ir+1. Preuve. Par l’hypothèse inductive et le lemme 5.5, pour chaque étape s et vérificateur i \(\in\)HSV r,s, \(\alpha\)r,s je \(\in\)Ir. Ci-dessous, nous analysons le protocole étape par étape. Étape 1. Par définition, tout vérificateur honnête i \(\in\)HSV r,1 propage le message souhaité mr,1 je à temps \(\beta\)r,1 je = \(\alpha\)r,1 je, où monsieur,1 je = (Br je , esigi(H(Br je )), \(\sigma\)r,1 je ), Br je = (r, PAYER r je , SIGi(Qr−1), H(Br−1)), et PAYER r i est un ensemble de paiements maximal parmi tous les paiements que j'ai vus au temps \(\alpha\)r,1 je. Étape 2. Fixer arbitrairement un vérificateur honnête i \(\in\)HSV r,2. D'après le lemme 5.5, lorsque le joueur i a terminé attente à l'instant \(\beta\)r,2 je = \(\alpha\)r,2 je + t2, il a reçu tous les messages envoyés par les vérificateurs en HSV r,1, y compris monsieur,1 \(\ell\)r. D’après la définition de \(\ell\)r, il n’existe pas d’autre joueur dans PKr−k dont l’identifiant hash la valeur est inférieure à H(\(\sigma\)r,1 \(\ell\)r ). Bien entendu, l’Adversaire peut corrompre \(\ell\)r après avoir vu que H(\(\sigma\)r,1 \(\ell\)r) est très petit, mais à ce moment-là, le joueur \(\ell\)r a détruit sa clé éphémère et le message mr,1 \(\ell\)r s'est propagée. Ainsi, le vérificateur i définit son propre leader comme étant le joueur \(\ell\)r. En conséquence, au temps \(\beta\)r,2 je, vérificateur je propage mr,2 je = (ESIGi(v′ je), \(\sigma\)r,2 je ), où v′ je = H(Br \(\ell\)r). Lorsque r = 0, la seule différence est-ce \(\beta\)r,2 je = t2 plutôt que d'être dans une plage. Des choses similaires peuvent être dites pour les étapes futures et nous je ne les soulignerai plus. Étape 3. Fixer arbitrairement un vérificateur honnête i \(\in\)HSV r,3. D'après le lemme 5.5, lorsque le joueur i a terminé attente à l'instant \(\beta\)r,3 je = \(\alpha\)r,3 je + t3, il a reçu tous les messages envoyés par les vérificateurs en HSV r,2. Par les relations entre les paramètres, avec une probabilité écrasante |HSV r,2| > 2|MSV r,2|. De plus, aucun vérificateur honnête ne signerait des messages contradictoires, et l’Adversaire ne peut pas falsifier la signature d'un vérificateur honnête après que ce dernier a détruit son clé secrète éphémère. Ainsi, plus des 2/3 de tous les messages (r, 2) valides que j'ai reçus proviennent de vérificateurs honnêtes et de la forme mr,2 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,2 j ), sans contradiction. En conséquence, au temps \(\beta\)r,3 je joueur je propage mr,3 je = (ESIGi(v′), \(\sigma\)r,3 je ), où v′ = H(Br \(\ell\)r).Étape 4. Fixer arbitrairement un vérificateur honnête i \(\in\)HSV r,4. D'après le lemme 5.5, le joueur i a tout reçu messages envoyés par les vérificateurs en HSV r,3 lorsqu'il a fini d'attendre à l'instant \(\beta\)r,4 je = \(\alpha\)r,4 je +t4. Semblable à Étape 3, plus des 2/3 de tous les messages (r, 3) valides que j'ai reçus proviennent de vérificateurs honnêtes et de la forme mr,3 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,3 j). En conséquence, le joueur i définit vi = H(Br \(\ell\)r), gi = 2 et bi = 0. Au temps \(\beta\)r,4 je = \(\alpha\)r,4 je +t4 il se propage monsieur,4 je = (ESIGi(0), ESIGi(H(Br \(\ell\)r)), \(\sigma\)r,4 je ). Étape 5. Fixer arbitrairement un vérificateur honnête i \(\in\)HSV r,5. D'après le lemme 5.5, joueur que j'aurais a reçu tous les messages envoyés par les vérificateurs en HSV r,4 s'il a attendu l'heure \(\alpha\)r,5 je +t5. Notez que |HSVr,4| \(\geq\)tH.19 Notez également que tous les vérificateurs dans HSV r,4 ont signé pour H(Br \(\ell\)r). Comme |MSV r,4| < tH, il n’existe aucun v′ ̸= H(Br \(\ell\)r) qui aurait pu être signé par TH vérificateurs dans SV r,4 (qui seraient forcément malveillants), donc le joueur i ne s'arrête pas avant d'avoir reçu des messages valides mr,4 j = (ESIGj(0), ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,4 j). Soit T le moment où ce dernier événement se produit. Certains de ces messages peuvent provenir de joueurs malveillants, mais comme |MSVr,4| < thH, au moins l'un d'entre eux provient d'un vérificateur honnête en HSV r,4 et est envoyé après un délai T r + t4. Par conséquent, T \(\geq\)T r +t4 > T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ, et au moment T joueur j'ai également reçu le message monsieur,1 \(\ell\)r. Par la construction du protocole, le joueur i s'arrête à l'instant \(\beta\)r,5 je = T sans propager quoi que ce soit ; ensembles Br = Br \(\ell\)r; et définit son propre CERT r comme étant l'ensemble des messages (r, 4) pour 0 et H(Br \(\ell\)r) qu’il a reçu. Étapes > 5. De même, pour toute étape s > 5 et tout vérificateur i \(\in\)HSV r,s, le joueur i aurait a reçu tous les messages envoyés par les vérificateurs en HSV r,4 s'il a attendu l'heure \(\alpha\)r,s je + c.t. Par le même analyse, le joueur i s'arrête sans rien propager, en mettant Br = Br \(\ell\)r (et définissant le sien CERT r correctement). Bien entendu, les vérificateurs malveillants peuvent ne pas s'arrêter et se propager de manière arbitraire. messages, mais parce que |MSV r,s| < th, par induction aucun autre v′ ne pourrait être signé par les th vérificateurs dans n'importe quelle étape 4 \(\leq\)s′ < s, donc les vérificateurs honnêtes ne s'arrêtent que parce qu'ils ont reçu le code valide (r, 4)-messages pour 0 et H(Br \(\ell\)r). Reconstruction du bloc Round-r. L'analyse de l'étape 5 s'applique à un modèle honnête utilisateur, je suis presque sans aucun changement. En effet, le joueur i commence son propre tour r dans l'intervalle Ir et ne s'arrêtera qu'à un instant T lorsqu'il aura reçu les messages (r, 4) valides pour H(Br \(\ell\)r). Encore une fois parce que au moins un de ces messages provient de vérificateurs honnêtes et est envoyé après le temps T r + t4, le joueur i a a également reçu mr,1 \(\ell\)r au temps T. Ainsi il pose Br = Br \(\ell\)r avec le CERT r approprié. Il ne reste plus qu'à montrer que tous les utilisateurs honnêtes terminent leur tour r dans l'intervalle de temps Ir+1. D’après l’analyse de l’étape 5, tout vérificateur honnête i \(\in\)HSV r,5 connaît Br sur ou avant \(\alpha\)r,5 je + t5 \(\leq\) T r + \(\lambda\) + t5 = T r + 8\(\lambda\) + Λ. Puisque T r+1 est le moment où le premier utilisateur honnête ir connaît Br, on a T r+1 \(\leq\)T r + 8\(\lambda\) + Λ comme souhaité. De plus, lorsque le joueur connaît Br, il a déjà contribué à propager les messages dans son CERT r. Notez que tous ces messages seront reçus par tous les utilisateurs honnêtes dans un délai \(\lambda\), même si 19À proprement parler, cela se produit avec une très forte probabilité, mais pas nécessairement de manière écrasante. Cependant, ceci la probabilité affecte légèrement la durée d’exécution du protocole, mais n’affecte pas son exactitude. Lorsque h = 80 %, alors |HSVr,4| \(\geq\)tH avec probabilité 1 −10−8. Si cet événement ne se produit pas, le protocole se poursuivra pendant une autre période. 3 étapes. Comme la probabilité que cela ne se produise pas en deux étapes est négligeable, le protocole se terminera à l'étape 8. Dans ce cas, le nombre d'étapes nécessaires est presque de 5.J'ai été le premier joueur à les propager. De plus, suite à l’analyse ci-dessus, nous avons T r+1 \(\geq\)T r + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ, donc tous les utilisateurs honnêtes ont reçu mr,1 \(\ell\)r au temps T r+1 + \(\lambda\). En conséquence, tous les utilisateurs honnêtes connaissent Br dans l'intervalle de temps Ir+1 = [T r+1, T r+1 + \(\lambda\)]. Enfin, pour r = 0 nous avons en fait T 1 \(\leq\)t4 + \(\lambda\) = 6\(\lambda\) + Λ. En combinant tout ensemble, Le lemme 5.2 est valable. ■ 5.8 Le lemme de solidité Lemme 5.3. [Lemme de solidité, reformulé] En supposant que les propriétés 1 à 3 soient valables pour le tour r −1, lorsque le leader \(\ell\)r est malveillant, avec une écrasante probabilité, tous les utilisateurs honnêtes sont d'accord sur le même bloc Br, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ et tous les utilisateurs honnêtes connaissent Br dans l'intervalle de temps Ir+1. Preuve. Nous considérons les deux parties du protocole, GC et BBA⋆, séparément. CG. Par l’hypothèse inductive et par le lemme 5.5, pour toute étape s \(\in\){2, 3, 4} et toute étape honnête vérificateur i \(\in\)HSV r,s, lorsque le joueur i agit au temps \(\beta\)r,s je = \(\alpha\)r,s je + ts, il a reçu tous les messages envoyés par tous les vérificateurs honnêtes aux étapes s′ < s. Nous distinguons deux cas possibles pour l’étape 4. Cas 1. Aucun vérificateur i \(\in\)HSV r,4 définit gi = 2. Dans ce cas, par définition bi = 1 pour tous les vérificateurs i \(\in\)HSV r,4. Autrement dit, ils commencent par un accord sur 1 dans le protocole binaire BA. Ils n’ont peut-être pas d’accord sur leurs vi’s, mais cela n'a pas d'importance comme nous le verrons dans le BA binaire. Cas 2. Il existe un vérificateur ˆi \(\in\)HSV r,4 tel que gˆi = 2. Dans ce cas, nous montrons que (1) gi \(\geq\)1 pour tout i \(\in\)HSV r,4, (2) il existe une valeur v′ telle que vi = v′ pour tout i \(\in\)HSV r,4, et (3) il existe un message valide mr,1 \(\ell\) d’un vérificateur \(\ell\) \(\in\)SV r,1 tel que v′ = H(Br \(\ell\)). En effet, puisque le joueur ˆi est honnête et fixe gˆi = 2, plus des 2/3 de tous les messages valides mr,3 j il a reçu sont pour la même valeur v′ ̸= \(\bot\), et il a posé vˆi = v′. Par la propriété (d) du lemme 5.5, pour tout autre vérificateur i honnête (r, 4), cela ne peut pas être plus que que 2/3 de tous les messages valides mr,3 j que i′ a reçu sont pour la même valeur v′′ ̸= v′. En conséquence, si je fixe gi = 2, il faut que j'aie également vu une majorité > 2/3 pour v′ et que j'ai défini vi = v′, comme souhaité. Considérons maintenant un vérificateur arbitraire i \(\in\)HSV r,4 avec gi < 2. Semblable à l'analyse de la propriété (d) dans le lemme 5.5, parce que le joueur ˆi a vu une majorité > 2/3 pour v′, plus de 1 2|HSV r,3| honnête (r, 3)-vérificateurs ont signé v′. Parce que j'ai reçu tous les messages de vérificateurs honnêtes (r, 3) par temps \(\beta\)r,4 je = \(\alpha\)r,4 je + t4, il a notamment reçu plus de 1 2|HSV r,3| messages de leur part pour v′. Parce que |HSV r,3| > 2|MSV r,3|, j'ai vu > 1/3 de majorité pour v′. En conséquence, le joueur i définit gi = 1 et la propriété (1) est valable. Est-ce que le joueur i définit nécessairement vi = v′ ? Supposons qu’il existe une valeur différente v′′ ̸= \(\bot\) telle que joueur que j'ai également vu > 1/3 de majorité pour v′′. Certains de ces messages peuvent provenir de logiciels malveillants vérificateurs, mais au moins l’un d’entre eux provient d’un vérificateur honnête j \(\in\)HSV r,3 : en effet, parce que |HSV r,3| > 2|MSV r,3| et j'ai reçu tous les messages de HSV r,3, l'ensemble des logiciels malveillants les vérificateurs de qui j'ai reçu un message (r, 3) valide comptent pour < 1/3 de tous les messages valides. messages qu'il a reçus.Par définition, le joueur j doit avoir vu > 2/3 de majorité pour v′′ parmi tous les (r, 2)-messages valides il a reçu. Cependant, nous savons déjà que d’autres vérificateurs (r, 3) honnêtes ont vu Majorité des 2/3 pour v′ (car ils ont signé v′). Par la propriété (d) du lemme 5.5, cela ne peut pas se produire et une telle valeur v′′ n’existe pas. Ainsi, le joueur doit avoir défini vi = v′ comme souhaité, et la propriété (2) est détenue. Enfin, étant donné que certains vérificateurs (r, 3) honnêtes ont vu une majorité > 2/3 pour v′, certains (en fait, plus de la moitié des) vérificateurs honnêtes (r, 2) ont signé pour v′ et ont propagé leurs messages. Par la construction du protocole, ces vérificateurs (r, 2) honnêtes doivent avoir reçu un message monsieur, 1 \(\ell\) d'un joueur \(\ell\) \(\in\)SV r,1 avec v′ = H(Br \(\ell\)), donc la propriété (3) est vérifiée. BBA⋆. Nous distinguons encore deux cas. Cas 1. Tous les vérificateurs i \(\in\)HSV r,4 ont bi = 1. Cela se produit à la suite du cas 1 de GC. Comme |MSV r,4| < tH, dans ce cas aucun vérificateur dans SV r,5 pourrait collecter ou générer les messages (r, 4) valides pour le bit 0. Ainsi, aucun vérificateur honnête dans HSV r,5 s'arrêterait parce qu'il connaît un bloc non vide Br. De plus, bien qu’il y ait au moins tH messages (r, 4) valides pour le bit 1, s′ = 5 ne satisfait pas s′ −2 ≡1 mod 3, donc aucun vérificateur honnête dans HSV r,5 ne s'arrêterait parce qu'il sait Br = Br ǫ. Au lieu de cela, tout vérificateur i \(\in\)HSV r,5 agit au temps \(\beta\)r,5 je = \(\alpha\)r,5 je + t5, au moment où il a tout reçu messages envoyés par HSV r,4 suivant le lemme 5.5. Ainsi le joueur que j'ai vu > 2/3 de majorité pour 1 et définit bi = 1. À l’étape 6 qui est une étape Coin-Fixed-To-1, bien que s′ = 5 satisfasse s′ −2 ≡0 mod 3, il y a n’existe pas de messages (r, 4) valides pour le bit 0, donc aucun vérificateur dans HSV r,6 ne s’arrêterait car il connaît un bloc non vide Br. Cependant, avec s′ = 6, s′ −2 ≡1 mod 3 et il existe |HSVr,5| \(\geq\)tH messages (r, 5) valides pour le bit 1 de HSV r,5. Pour tout vérificateur i \(\in\)HSV r,6, suivant le lemme 5.5, au plus tard à l’instant \(\alpha\)r,6 je + joueur t6 je a reçu tous les messages de HSV r,5, donc je m'arrête sans rien propager et je règle Br = Br ǫ. Son CERT r est l'ensemble des messages (r, 5) valides mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) reçu par lui quand il s'arrête. Ensuite, laissez le joueur i être soit un vérificateur honnête dans une étape s > 6, soit un utilisateur honnête générique (c'est-à-dire, non-vérificateur). Semblable à la preuve du lemme 5.2, le joueur i définit Br = Br ǫ et définit le sien CERT r est l'ensemble des messages (r, 5) valides mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) il a reçu. Enfin, similaire au lemme 5.2, Tr+1 \(\leq\) min i\(\in\)HSV r,6 \(\alpha\)r,6 je + t6 \(\leq\)T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ, et tous les utilisateurs honnêtes connaissent Br dans l’intervalle de temps Ir+1, car le premier utilisateur honnête i qui sait que Br a aidé à propager les messages (r, 5) dans son CERT r. Cas 2. Il existe un vérificateur ˆi \(\in\)HSV r,4 avec bˆi = 0. Cela se produit après le cas 2 de GC et constitue le cas le plus complexe. Par l'analyse de GC, dans ce cas il existe un message valide mr,1 \(\ell\) tel que vi = H(Br \(\ell\)) pour tout i \(\in\)HSV r,4. Remarque que les vérificateurs dans HSV r,4 peuvent ne pas avoir d'accord sur leurs bi. Pour toute étape s \(\in\){5, . . . , m + 3} et vérificateur i \(\in\)HSV r,s, d'après le joueur du lemme 5.5 j'aurais reçu tous les messages envoyés par tous les vérificateurs honnêtes dans HSV r,4 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1 s'il a attendu pour le temps ts.Considérons maintenant l’événement E suivant : il existe une étape s∗\(\geq\)5 telle que, pour la première temps dans le BA binaire, un joueur i∗\(\in\)SV r,s∗ (qu'il soit malveillant ou honnête) devrait s'arrêter sans rien propager. Nous utilisons « devrait arrêter » pour souligner le fait que, si le joueur i∗ est malveillant, alors il peut prétendre qu'il ne devrait pas s'arrêter conformément au protocole et propager des messages au choix de l’Adversaire. De plus, par la construction du protocole, soit (E.a) i∗est capable de collecter ou de générer au moins les messages valides mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) pour les mêmes v et s′, avec 5 \(\leq\)s′ \(\leq\)s∗ et s′ −2 ≡0 mod 3 ; ou (E.b) i∗est capable de collecter ou de générer au moins les messages valides mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ) pour le même s′, avec 6 \(\leq\)s′ \(\leq\)s∗ et s′ −2 ≡1 mod 3. Parce que les messages (r, s′ −1) honnêtes sont reçus par tous les vérificateurs (r, s′) honnêtes avant d’être envoyés. ont fini d'attendre à l'étape s', et parce que l'Adversaire reçoit tout au plus tard utilisateurs honnêtes, sans perte de généralité on a s′ = s∗ et le joueur i∗ est malveillant. Notez que nous n'avons pas exigé que la valeur v dans E.a soit le hash d'un bloc valide : comme cela deviendra clair dans l'analyse, v = H(Br \(\ell\)) dans ce sous-événement. Ci-dessous, nous analysons d’abord le cas 2 suite à l’événement E, puis montrons que la valeur de s∗ est essentiellement distribué en conséquence à Lr (ainsi l'événement E se produit avant l'étape m + 3 avec une écrasante probabilité compte tenu des relations entre les paramètres). Pour commencer, pour tout pas 5 \(\leq\)s < s∗, tout vérificateur honnête i \(\in\)HSV r,s a attendu un temps ts et a défini vi comme étant le vote majoritaire du messages (r, s−1) valides qu'il a reçus. Depuis que le joueur j'ai reçu tous les messages (r, s−1) honnêtes suivant le lemme 5.5, puisque tous les vérificateurs honnêtes dans HSV r,4 ont signé H(Br \(\ell\)) cas suivant 2 de GC, et puisque |HSV r,s−1| > 2|MSV r,s−1| pour chaque s, par induction nous avons ce joueur i a fixé vi = H(Br \(\ell\)). Il en va de même pour tout vérificateur honnête i \(\in\)HSV r,s∗ qui ne s’arrête pas sans se propager n'importe quoi. Considérons maintenant l’étape s∗ et distinguons quatre sous-cas. Cas 2.1.a. L’événement E.a se produit et il existe un vérificateur honnête i′ \(\in\)HSV r,s∗ qui devrait s'arrêter aussi sans rien propager. Dans ce cas, nous avons s∗−2 ≡0 mod 3 et l'étape s∗ est une étape Coin-Fixed-To-0. Par définition, le joueur i′ a reçu au moins les (r, s∗−1)-messages valides de la forme (ESIGj(0), ESIGj(v), \(\sigma\)r,s∗−1 j ). Puisque tous les vérificateurs dans HSV r,s∗−1 ont signé H(Br \(\ell\)) et |MSVr,s∗−1| < tH, on a v = H(Br \(\ell\)). Puisque au moins tH −|MSV r,s∗−1| \(\geq\)1 des (r, s∗−1)-messages reçus par i′ pour 0 et v sont envoyés par les vérificateurs dans HSV r,s∗−1 après le temps T r +ts∗−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\) +Λ, joueur, j'ai reçu mr,1 \(\ell\) au moment où il reçoit ces (r, s∗−1)-messages. Ainsi joueur je m'arrête sans rien propager ; ensembles Br = Br \(\ell\) ; et définit son propre CERT r comme étant le ensemble de messages (r, s∗−1) valides pour 0 et v qu'il a reçus. Ensuite, nous montrons que tout autre vérificateur i \(\in\)HSV r,s∗ s’est arrêté avec Br = Br \(\ell\), ou a défini bi = 0 et propagé (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s je ). En effet, parce que l’étape s∗ C'est la première fois qu'un vérificateur doit s'arrêter sans rien propager, il n'y a pas existe une étape s′ < s∗ avec s′ −2 ≡1 mod 3 telle que les tH (r, s′ −1)-vérificateurs ont signé 1. Par conséquent, aucun vérificateur dans HSV r,s∗ ne s’arrête avec Br = Br ǫ.De plus, comme tous les vérificateurs honnêtes aux étapes {4, 5, . . . , s∗−1} sont signés H(Br \(\ell\)), il y a il n’existe pas d’étape s′ \(\leq\)s∗avec s′ −2 ≡0 mod 3 telle que les tH (r, s′ −1)-vérificateurs aient signé certains v′′ ̸= H(Br \(\ell\)) — en effet, |MSV r,s′−1| < th. En conséquence, aucun vérificateur dans HSV r,s∗arrête avec Br ̸ = Br ǫ et Br ̸= Br \(\ell\). Autrement dit, si un joueur i \(\in\)HSV r,s∗ s’est arrêté sans propageant quoi que ce soit, il a dû définir Br = Br \(\ell\). Si un joueur i \(\in\)HSV r,s∗ a attendu le temps ts∗ et a propagé un message à l'instant \(\beta\)r,s∗ je = \(\alpha\)r,s∗ je + ts∗, il a reçu tous les messages de HSV r,s∗−1, dont au moins tH −|MSVr,s∗−1| d'entre eux pour 0 et v. Si j'ai vu une majorité > 2/3 pour 1, alors il a vu plus de 2(tH −|MSV r,s∗−1|) messages (r, s∗−1) valides pour 1, avec plus que 2tH −3|MSV r,s∗−1| d’entre eux provenant de vérificateurs (r, s∗−1) honnêtes. Cependant, cela implique |HSVr,s∗−1| \(\geq\)tH−|MSV r,s∗−1|+2tH−3|MSV r,s∗−1| > 2n−4|MSV r,s∗−1|, contredisant le fait que |HSVr,s∗−1| + 4|MSV r,s∗−1| <2n, qui vient des relations pour les paramètres. En conséquence, je ne vois pas > 2/3 majorité pour 1, et il fixe bi = 0 car l'étape s∗ est une étape Coin-Fixed-To-0. Comme nous l'avons vu, vi = H(Br \(\ell\)). Ainsi je propage (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s i ) comme nous le voulions montrer. Pour l’étape s∗+ 1, puisque le joueur i′ a contribué à propager les messages dans son CERT r au plus tard à l’heure \(\alpha\)r,s∗ je + ts∗, tous les vérificateurs honnêtes dans HSV r,s∗+1 ont reçu au moins tH messages (r, s∗−1) valides pour le bit 0 et la valeur H(Br \(\ell\)) au plus tard en attendant. De plus, les vérificateurs dans HSV r,s∗+1 ne s'arrêteront pas avant de recevoir ceux (r, s∗−1)- messages, car il n’existe pas d’autres messages (r, s′ −1) valides pour le bit 1 avec s′ −2 ≡1 mod 3 et 6 \(\leq\)s′ \(\leq\)s∗+ 1, par la définition du Pas s∗. En particulier, l'étape s∗+ 1 lui-même est une étape Coin-Fixed-To-1, mais aucun vérificateur honnête dans HSV r,s∗ ne s'est propagé un message pour 1, et |MSV r,s∗| < th. Ainsi tous les vérificateurs honnêtes dans HSV r,s∗+1 s’arrêtent sans rien propager et posent Br = Br \(\ell\) : comme avant, ils ont reçu mr,1 \(\ell\) avant de recevoir les messages (r, s∗−1) souhaités.20 La même chose peut être dite pour tous les vérificateurs honnêtes dans les étapes futures et pour tous les utilisateurs honnêtes en général. En particulier, ils savent tous Br = Br \(\ell\)dans l'intervalle de temps Ir+1 et T r+1 \(\leq\) \(\alpha\)r,s∗ je + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Cas 2.1.b. L’événement E.b se produit et il existe un vérificateur honnête i′ \(\in\)HSV r,s∗ qui devrait s'arrêter aussi sans rien propager. Dans ce cas, nous avons s∗−2 ≡1 mod 3 et l'étape s∗ est une étape Coin-Fixed-To-1. L'analyse est similaire au cas 2.1.a et de nombreux détails ont été omis. 20 S’il est méchant, il pourra envoyer monsieur,1 \(\ell\) en retard, en espérant que certains utilisateurs/vérificateurs honnêtes n'aient pas reçu mr,1 \(\ell\) encore lorsqu'ils recevront le certificat souhaité. Cependant, puisque le vérificateur ˆi \(\in\)HSV r,4 a posé bˆi = 0 et vˆi = H(Br \(\ell\)), comme avant d’avoir que plus de la moitié des vérificateurs honnêtes i \(\in\)HSV r,3 ont défini vi = H(Br \(\ell\)). Cela implique en outre davantage plus de la moitié des vérificateurs honnêtes i \(\in\)HSV r,2 ont défini vi = H(Br \(\ell\)), et ces (r, 2)-vérificateurs ont tous reçu mr,1 \(\ell\). Comme le L'adversaire ne peut pas distinguer un vérificateur d'un non-vérificateur, il ne peut pas cibler la propagation de mr,1 \(\ell\) aux (r, 2)-vérificateurs sans que les non-vérificateurs ne le voient. En fait, avec une forte probabilité, plus de la moitié (ou une bonne fraction constante) de tous les utilisateurs honnêtes ont vu mr,1 \(\ell\) après avoir attendu t2 depuis le début de son propre tour r. A partir de là, le temps \(\lambda\)′ nécessaire pour mr,1 \(\ell\) pour atteindre les utilisateurs honnêtes restants est beaucoup plus petit que Λ, et par souci de simplicité, nous ne le faisons pas écrivez-le dans l’analyse. Si 4\(\lambda\) \(\geq\) \(\lambda\)′ alors l’analyse se déroule sans aucun changement : à la fin de l’étape 4, tous des utilisateurs honnêtes auraient reçu mr,1 \(\ell\). Si la taille du bloc devient énorme et 4\(\lambda\) < \(\lambda\)′, alors aux étapes 3 et 4, le protocole pourrait demander à chaque vérificateur d'attendre \(\lambda\)′/2 plutôt que 2\(\lambda\), et l'analyse continue de tenir.Comme précédemment, le joueur i′ doit avoir reçu au moins les (r, s∗−1)-messages valides de la forme (ESIGj(1), ESIGj(vj), \(\sigma\)r,s∗−1 j ). Toujours par la définition de s∗, il n’existe pas d’étape 5 \(\leq\)s′ < s∗avec s′ −2 ≡0 mod 3, où au moins les tH (r, s′ −1)-vérificateurs ont signé 0 et le même v. Ainsi le joueur i s'arrête sans rien propager ; ensembles Br = Br ǫ; et des ensembles son propre CERT r est l'ensemble des messages (r, s∗−1) valides pour le bit 1 qu'il a reçu. De plus, tout autre vérificateur i \(\in\)HSV r,s∗ s’est arrêté avec Br = Br ǫ , ou a défini bi = 1 et propagé (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ je ). Depuis que je suis joueur, j'ai aidé à se propager les (r, s∗−1)-messages dans son CERT r au temps \(\alpha\)r,s∗ je + ts∗, encore une fois tous les vérificateurs honnêtes dans HSV r,s∗+1 s'arrête sans rien propager et pose Br = Br ǫ . De même, tous honnêtes les utilisateurs savent que Br = Br ǫ dans l’intervalle de temps Ir+1 et T r+1 \(\leq\) \(\alpha\)r,s∗ je + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Cas 2.2.a. L’événement E.a se produit et il n’existe pas de vérificateur honnête i′ \(\in\)HSV r,s∗qui devrait également s'arrêter sans rien propager. Dans ce cas, notez que le joueur i∗pourrait avoir un CERT r valide i∗constitué du tH souhaité (r, s∗−1)-messages que l'adversaire est capable de collecter ou de générer. Cependant, le malveillant les vérificateurs ne peuvent pas aider à propager ces messages, nous ne pouvons donc pas conclure que les honnêtes les utilisateurs les recevront dans le temps \(\lambda\). En fait, |MSV r,s∗−1| de ces messages peuvent provenir de des vérificateurs (r, s∗−1) malveillants, qui ne propageaient pas du tout leurs messages et envoyaient uniquement aux vérificateurs malveillants à l’étape s∗. Semblable au cas 2.1.a, nous avons ici s∗−2 ≡0 mod 3, l'étape s∗est une étape Coin-Fixed-To-0, et les messages (r, s∗−1) dans CERT r i∗sont pour le bit 0 et v = H(Br \(\ell\)). En effet, tout est honnête (r, s∗−1)-vérificateurs signe v, donc l'Adversaire ne peut pas générer les (r, s∗−1)-messages valides pour un v′ différent. De plus, tous les vérificateurs (r, s∗) honnêtes ont attendu un temps ts∗ et ne voient pas une majorité > 2/3 pour le bit 1, encore une fois parce que |HSV r,s∗−1| + 4|MSV r,s∗−1| <2n. Ainsi, tout vérificateur honnête i \(\in\)HSV r,s∗sets bi = 0, vi = H(Br \(\ell\)) à la majorité des voix, et propage mr,s∗ je = (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s∗ je ) au temps \(\alpha\)r,s∗ je + ts∗. Considérons maintenant les vérificateurs honnêtes de l’étape s∗+1 (qui est une étape Coin-Fixed-To-1). Si le L'adversaire envoie réellement les messages dans CERT r i∗à certains d'entre eux et les amène à stop, alors similaire au cas 2.1.a, tous les utilisateurs honnêtes savent Br = Br \(\ell\)dans l'intervalle de temps Ir+1 et T r+1 \(\leq\)T r + \(\lambda\) + ts∗+1. Sinon, tous les vérificateurs honnêtes de l’étape s∗+1 ont reçu tous les messages (r, s∗) pour 0 et H(Br \(\ell\)) de HSV r,s∗après le temps d'attente ts∗+1, ce qui conduit à une majorité > 2/3, car |HSVr,s∗| > 2|MSV r,s∗|. Ainsi tous les vérificateurs dans HSV r,s∗+1 propagent leurs messages pour 0 et H(Br \(\ell\)) en conséquence. Notons que les vérificateurs dans HSV r,s∗+1 ne s’arrêtent pas à Br = Br \(\ell\), car l'étape s∗ + 1 n'est pas une étape Coin-Fixed-To-0. Considérons maintenant les vérificateurs honnêtes de l’étape s∗+2 (qui est une étape Coin-Genuinely-Flipped). Si l'adversaire envoie les messages dans CERT r i∗à certains d'entre eux et les fait arrêter, là encore, tous les utilisateurs honnêtes savent Br = Br \(\ell\)dans l'intervalle de temps Ir+1 et T r+1 \(\leq\)T r + \(\lambda\) + ts∗+2.Sinon, tous les vérificateurs honnêtes à l’étape s∗+ 2 ont reçu tous les messages (r, s∗+ 1) pour 0 et H(Br \(\ell\)) de HSV r,s∗+1 après le temps d’attente ts∗+2, ce qui conduit à une majorité > 2/3. Ainsi tous propagent leurs messages pour 0 et H(Br \(\ell\)) en conséquence : c'est ce qu'ils font pas de « lancer une pièce » dans ce cas. Encore une fois, notez qu'ils ne s'arrêtent pas sans se propager, car l'étape s∗+ 2 n'est pas une étape Coin-Fixed-To-0. Enfin, pour les vérificateurs honnêtes de l’étape s∗+3 (qui est une autre étape Coin-Fixed-To-0), tous d'entre eux auraient reçu au moins les messages valides pour 0 et H(Br \(\ell\)) de HSV s∗+2, s'ils attendent réellement le temps ts∗+3. Ainsi, que l'Adversaire envoie ou non les messages en CERT r i∗pour n’importe lequel d’entre eux, tous les vérificateurs dans HSV r,s∗+3 s’arrêtent avec Br = Br \(\ell\), sans propager quoi que ce soit. Selon la manière dont l'Adversaire agit, certains d'entre eux peuvent avoir leur propre CERT r composé de ces (r, s∗−1)-messages dans CERT r i∗, et les autres ont leur propre CERT r composé de ces messages (r, s∗+ 2). Quoi qu'il en soit, tous les utilisateurs honnêtes savoir Br = Br \(\ell\)dans l'intervalle de temps Ir+1 et T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3. Cas 2.2.b. L’événement E.b se produit et il n’existe pas de vérificateur honnête i′ \(\in\)HSV r,s∗qui devrait également s'arrêter sans rien propager. L'analyse dans ce cas est similaire à celles des cas 2.1.b et 2.2.a, donc de nombreux détails ont été omis. En particulier, CERT r i∗se compose des tH (r, s∗−1)-messages souhaités pour le bit 1 que l'Adversaire est capable de collecter ou de générer, s∗−2 ≡1 mod 3, l'Etape s∗est un Étape Coin-Fixed-To-1, et aucun vérificateur honnête (r, s∗) n'aurait pu voir une majorité > 2/3 pour 0. Ainsi, tout vérificateur i \(\in\)HSV r,s∗ fixe bi = 1 et propage mr,s∗ je = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ je ) au temps \(\alpha\)r,s∗ je + ts∗. Semblable au cas 2.2.a, en au plus 3 étapes supplémentaires (c'est-à-dire le protocole atteint l'étape s∗+3, qui est une autre étape Coin-Fixed-To-1), tous les utilisateurs honnêtes savent Br = Br ǫ dans l'intervalle de temps Ir+1. De plus, T r+1 peut être \(\leq\)T r+\(\lambda\)+ts∗+1, ou \(\leq\)T r+\(\lambda\)+ts∗+2, ou \(\leq\)T r + \(\lambda\) + ts∗+3, selon la première fois qu'un vérificateur honnête est capable d'arrêter sans se propager. En combinant les quatre sous-cas, nous constatons que tous les utilisateurs honnêtes connaissent Br dans l'intervalle de temps Ir+1, avec T r+1 \(\leq\)T r + \(\lambda\) + ts∗dans les cas 2.1.a et 2.1.b, et T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 dans les cas 2.2.a et 2.2.b. Il reste à majorer s∗ et donc T r+1 pour le cas 2, et nous le faisons en considérant comment plusieurs fois, les étapes Coin-Genuinely-Flipped sont réellement exécutées dans le protocole : c'est-à-dire certains vérificateurs honnêtes ont en fait tiré à pile ou face. En particulier, fixez arbitrairement un pas s′ de Coin-Genuinely-Flipped (c'est-à-dire 7 \(\leq\)s′ \(\leq\)m + 2 et s′ −2 ≡2 mod 3), et soit \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 j ). Pour l’instant supposons s′ < s∗, car autrement, aucun vérificateur honnête ne lance réellement une pièce à l’étape s′, selon la précédente discussions. Par la définition de SV r,s′−1, la valeur hash du titre de \(\ell\)′ est également la plus petite parmi tous les utilisateurs de PKr−k. Puisque la fonction hash est un oracle aléatoire, idéalement le joueur \(\ell\)′ est honnête avec probabilité d'au moins h. Comme nous le montrerons plus tard, même si l'Adversaire fait de son mieux pour prédire le sortie du oracle aléatoire et inclinez la probabilité, le joueur \(\ell\)′ est toujours honnête avec la probabilitéau moins ph = h2(1 + h −h2). Ci-dessous, nous considérons le cas où cela se produit effectivement : c'est-à-dire \(\ell\)′ \(\in\)HSV r, s′−1. Notez que tout vérificateur honnête i \(\in\)HSV r,s′ a reçu tous les messages de HSV r,s′−1 par temps \(\alpha\)r,s′ je + ts′. Si le joueur i doit lancer une pièce de monnaie (c'est-à-dire s'il n'a pas vu une majorité > 2/3 depuis le même bit b \(\in\){0, 1}), puis il pose bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )). S'il existe un autre honnête vérificateur i′ \(\in\)HSV r,s′ qui a vu > 2/3 de majorité pour un bit b \(\in\){0, 1}, puis par Propriété (d) du lemme 5.5, aucun vérificateur honnête dans HSV r,s′ n'aurait vu une majorité > 2/3 pendant un moment b′ ̸= b. Puisque lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) = b avec probabilité 1/2, tous les vérificateurs honnêtes dans HSV r,s′ atteignent un accord sur b avec une probabilité 1/2. Bien sûr, si un tel vérificateur i n’existe pas, alors tout les vérificateurs honnêtes en HSV r,s′ s’accordent sur le bit lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) avec probabilité 1. En combinant la probabilité pour \(\ell\)′ \(\in\)HSV r,s′−1, nous avons que les vérificateurs honnêtes dans HSV r,s′ parvenir à un accord sur un bit b \(\in\){0, 1} avec une probabilité d'au moins ph 2 = h2(1+h−h2) 2 . De plus, par induction au vote majoritaire comme auparavant, tous les vérificateurs honnêtes dans HSV r,s′ ont leur vi défini être H(Br \(\ell\)). Ainsi, une fois qu’un accord sur b est atteint à l’étape s′, T r+1 est soit \(\leq\)T r + \(\lambda\) + ts′+1 soit \(\leq\)T r + \(\lambda\) + ts′+2, selon que b = 0 ou b = 1, suite à l'analyse des cas 2.1.a et 2.1.b. Dans En particulier, aucune autre étape Coin-Genuinely-Flipped ne sera exécutée : c'est-à-dire que les vérificateurs dans de telles démarches vérifient toujours qu'ils sont les vérificateurs et attendent donc, mais ils s'arrêteront tous sans propager quoi que ce soit. En conséquence, avant l'étape s∗, le nombre de fois où les étapes Coin-GenuinelyFlipped sont exécutées est distribué en fonction de la variable aléatoire Lr. Laisser les étapes s' être la dernière étape Coin-Genuinely-Flipped selon Lr, par la construction du protocole nous avons s′ = 4 + 3Lr. Quand l’Adversaire doit-il réaliser l’étape s∗ s’il veut retarder T r+1 d’autant possible ? On peut même supposer que l’Adversaire connaît à l’avance la réalisation de Lr. Si s∗> s′ alors cela ne sert à rien, car les vérificateurs honnêtes sont déjà parvenus à un accord dans Étapes s′. Bien sûr, dans ce cas s∗ serait s′ +1 ou s′ +2, toujours selon que b = 0 ou b = 1. Cependant, il s’agit en fait des cas 2.1.a et 2.1.b, et le T r+1 résultant est exactement le pareil que dans ce cas. Plus précisément, T r+1 \(\leq\)T r + \(\lambda\) + ts∗\(\leq\)T r + \(\lambda\) + ts′+2. Si s∗< s′ −3 — c'est-à-dire s∗ est avant l'avant-dernière étape Coin-Genuinely-Flipped — alors par l'analyse des cas 2.2.a et 2.2.b, T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 < T r + \(\lambda\) + ts′. Autrement dit, l’Adversaire fait en réalité en sorte que l’accord sur Br se réalise plus rapidement. Si s∗= s′ −2 ou s′ −1 — c'est-à-dire l'étape Coin-Fixed-To-0 ou l'étape Coin-Fixed-To-1 immédiatement avant l'étape s' - puis par l'analyse des quatre sous-cas, les vérificateurs honnêtes en Les étapes s ne permettent plus de lancer des pièces, car soit elles se sont arrêtées sans se propager, ou ont vu une majorité > 2/3 pour le même bit b. Nous avons donc T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 \(\leq\)T r + \(\lambda\) + ts′+2.En résumé, peu importe ce que s∗is, nous avons T r+1 \(\leq\)T r + \(\lambda\) + ts′+2 = T r + \(\lambda\) + t3Lr+6 = T r + \(\lambda\) + (2(3Lr + 6) −3)\(\lambda\) + Λ = T r + (6Lr + 10)\(\lambda\) + Λ, comme nous voulions le montrer. Le pire des cas est celui où s∗= s′ −1 et le cas 2.2.b se produit. En combinant les cas 1 et 2 du protocole binaire BA, le lemme 5.3 est valable. ■ 5.9 Sécurité du Qr des semences et probabilité d’un leader honnête Il reste à prouver le lemme 5.4. Rappelons que les vérificateurs du tour r sont tirés de PKr−k et sont choisis en fonction de la quantité Qr−1. La raison de l'introduction du paramètre de rétrospection k est de s'assurer que, au tour r −k, lorsque l'adversaire sera en mesure d'ajouter de nouveaux utilisateurs malveillants à PKr−k, il ne peut prédire la quantité Qr−1 qu’avec une probabilité négligeable. Notez que le La fonction hash est un oracle aléatoire et Qr−1 est l'une de ses entrées lors de la sélection des vérificateurs pour le tour r. Ainsi, quelle que soit la manière dont des utilisateurs malveillants sont ajoutés à PKr−k, du point de vue de l’Adversaire, chacun l'un d'eux est toujours sélectionné pour être vérificateur dans une étape du tour r avec la probabilité requise p (ou p1 pour l'étape 1). Plus précisément, nous avons le lemme suivant. Lemme 5.6. Avec k = O(log1/2 F), pour chaque tour r, avec une écrasante probabilité, l'Adversaire n'a pas interrogé Qr−1 au oracle aléatoire au tour r −k. Preuve. Nous procédons par induction. Supposons que pour chaque round \(\gamma\) < r, l’Adversaire n’a pas interrogé Q\(\gamma\)−1 au oracle aléatoire au tour \(\gamma\) −k.21 Considérons le jeu mental suivant joué par l'Adversaire au tour r −k, essayant de prédire Qr−1. À l'étape 1 de chaque tour \(\gamma\) = r −k, . . . , r −1, étant donné un Q\(\gamma\)−1 spécifique non interrogé au hasard oracle, en ordonnant les joueurs i \(\in\)PK\(\gamma\)−k selon les hash valeurs H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) de plus en plus, nous obtenons une permutation aléatoire sur PK\(\gamma\)−k. Par définition, le leader \(\ell\) \(\gamma\) est le premier utilisateur dans la permutation et est honnête avec la probabilité h. De plus, lorsque PK\(\gamma\)−k est grand assez, pour tout entier x \(\geq\)1, la probabilité que les x premiers utilisateurs de la permutation soient tous malveillant mais le (x + 1)st est honnête est (1 −h)xh. Si \(\ell\) \(\gamma\) est honnête, alors Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\)). Comme l'Adversaire ne peut pas contrefaire la signature de \(\ell\) \(\gamma\), Q\(\gamma\) est distribué uniformément de manière aléatoire du point de vue de l’Adversaire et, sauf avec une probabilité exponentiellement faible,22 n’a pas été interrogé sur H au tour r −k. Puisque chaque Qy+1, Qy+2, . . . , Qr−1 est respectivement la sortie de H avec Q\(\gamma\), Q\(\gamma\)+1, . . . , Qr−2 comme une des entrées, ils semblent tous aléatoires pour l'Adversaire et l'Adversaire n'aurait pas pu interroger Qr−1 à H à arrondir r −k. En conséquence, le seul cas où l’Adversaire peut prédire Qr−1 avec une bonne probabilité au tour r−k est lorsque tous les leaders \(\ell\)r−k, . . . , \(\ell\)r−1 sont malveillants. Considérons à nouveau un tour \(\gamma\) \(\in\){r−k . . . , r−1} et la permutation aléatoire sur PK\(\gamma\)−k induite par les valeurs hash correspondantes. Si pour certains x \(\geq\)2, les x −1 premiers utilisateurs de la permutation sont tous malveillants et le x-ème est honnête, alors le L'adversaire a x choix possibles pour Q\(\gamma\) : soit de la forme H(SIGi(Q\(\gamma\)−1, \(\gamma\))), où i est l'un des 21Comme k est un petit entier, sans perte de généralité on peut supposer que les k premiers tours du protocole sont exécutés dans un environnement sûr et l'hypothèse inductive est valable pour ces tours. 22C’est-à-dire exponentielle dans la longueur de la sortie de H. Notez que cette probabilité est bien inférieure à F.les x−1 premiers utilisateurs malveillants, en faisant du joueur i le véritable leader du tour \(\gamma\) ; ou H(Q\(\gamma\)−1, \(\gamma\)), par forcer B\(\gamma\) = B\(\gamma\) ǫ . Sinon, le leader du tour \(\gamma\) sera le premier utilisateur honnête dans la permutation et Qr−1 devient imprévisible pour l'Adversaire. Laquelle des x options de Q\(\gamma\) ci-dessus l’Adversaire devrait-il poursuivre ? Pour aider l'Adversaire Répondez à cette question, dans le jeu mental, nous le rendons en fait plus puissant qu'il ne l'est réellement. est, comme suit. Tout d’abord, en réalité, l’Adversaire ne peut pas calculer le hash du comportement d’un utilisateur honnête. signature, ne peut donc pas décider, pour chaque Q\(\gamma\), du nombre x(Q\(\gamma\)) d'utilisateurs malveillants au début de la permutation aléatoire en tour \(\gamma\) + 1 induite par Q\(\gamma\). Dans le jeu mental, on lui donne le nombres x(Q\(\gamma\)) gratuitement. Deuxièmement, en réalité, avoir les x premiers utilisateurs dans la permutation être malveillant ne signifie pas nécessairement qu'ils peuvent tous devenir le leader, car le hash les valeurs de leurs signatures doivent également être inférieures à p1. Nous avons ignoré cette contrainte dans le mental jeu, donnant à l'adversaire encore plus d'avantages. Il est facile de voir que dans le jeu mental, l'option optimale pour l'Adversaire, notée ˆQ\(\gamma\), est celui qui produit la plus longue séquence d'utilisateurs malveillants au début du processus aléatoire. permutation en tour \(\gamma\) + 1. En effet, étant donné un Q\(\gamma\) spécifique, le protocole ne dépend pas de Q\(\gamma\)−1 et l’Adversaire peut uniquement se concentrer sur la nouvelle permutation du tour \(\gamma\) + 1, qui a pour même répartition pour le nombre d'utilisateurs malveillants au début. Ainsi, à chaque tour \(\gamma\), le ˆQ\(\gamma\) mentionné ci-dessus lui donne le plus grand nombre d’options pour Q\(\gamma\)+1 et maximise ainsi la probabilité que les leaders consécutifs soient tous malveillants. Par conséquent, dans le jeu mental, l’Adversaire suit une Chaîne de Markov du tour r −k pour arrondir r −1, l'espace d'état étant {0} \(\cup\){x : x \(\geq\)2}. L'état 0 représente le fait que le Le premier utilisateur de la permutation aléatoire du tour en cours \(\gamma\) est honnête, donc l'Adversaire échoue à la jeu de prédiction de Qr−1 ; et chaque état x \(\geq\)2 représente le fait que les x −1 premiers utilisateurs du les permutations sont malveillantes et le x-ième est honnête, donc l'adversaire a x options pour Q\(\gamma\). Le les probabilités de transition P(x, y) sont les suivantes. • P(0, 0) = 1 et P(0, y) = 0 pour tout y \(\geq\)2. C'est-à-dire que l'Adversaire échoue au jeu une fois que le premier l'utilisateur dans la permutation devient honnête. • P(x, 0) = hx pour tout x \(\geq\)2. Autrement dit, avec la probabilité hx, toutes les x permutations aléatoires ont leurs premiers utilisateurs étant honnêtes, l’Adversaire échoue au tour suivant. • Pour tout x \(\geq\)2 et y \(\geq\)2, P(x, y) est la probabilité que, parmi les x permutations aléatoires induite par les options x de Q\(\gamma\), la plus longue séquence d'utilisateurs malveillants au début de certains d'entre eux sont y −1, donc l'Adversaire a y options pour Q\(\gamma\)+1 au tour suivant. C'est-à-dire P(x, y) = y−1 X je = 0 (1 −h)ih !x − y−2 X je = 0 (1 −h)ih !x = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x. Notez que l'état 0 est l'unique état absorbant dans la matrice de transition P, et tous les autres états x a une probabilité positive d’aller vers 0. Nous souhaitons majorer le nombre k de tours nécessaires pour que la chaîne de Markov converge vers 0 avec une probabilité écrasante : c'est-à-dire non peu importe l'état dans lequel la chaîne commence, avec une écrasante probabilité, l'adversaire perd la partie. et ne parvient pas à prédire Qr−1 au tour r −k. Considérons la matrice de transition P (2) \(\triangleq\)P \(\cdot\) P après deux tours. Il est facile de voir que P (2)(0, 0) = 1 et P (2)(0, x) = 0 pour tout x \(\geq\)2. Pour tout x \(\geq\)2 et y \(\geq\)2, comme P(0, y) = 0, on a P (2)(x, y) = P(x, 0)P(0, y) + X z\(\geq\)2 P(x, z)P(z, y) = X z\(\geq\)2 P(x, z)P(z, y).Soit ¯h \(\triangleq\)1 −h, on a P(x, y) = (1 −¯hy)x −(1 −¯hy−1)x et P (2)(x, y) = X z\(\geq\)2 [(1 −¯hz)x −(1 −¯hz−1)x][(1 −¯hy)z −(1 −¯hy−1)z]. Ci-dessous nous calculons la limite de P (2)(x,y) P (x, y) lorsque h tend vers 1, c'est-à-dire que ¯h tend vers 0. Notez que le plus haut l’ordre de ¯h dans P(x, y) est ¯hy−1, de coefficient x. En conséquence, lim h \(\to\) 1 P (2)(x, y) P(x,y) = lim ¯h \(\to\) 0 P (2)(x, y) P(x,y) = lim ¯h \(\to\) 0 P (2)(x, y) x¯hy−1 + O(¯hy) = lim ¯h \(\to\) 0 P. z\(\geq\)2[x¯hz−1 + O(¯hz)][z¯hy−1 + O(¯hy)] x¯hy−1 + O(¯hy) = lim ¯h \(\to\) 0 2x¯hy + O(¯hy+1) x¯hy−1 + O(¯hy) = lim ¯h \(\to\) 0 2x¯hy x¯hy−1 = lim ¯h \(\to\) 0 2¯h = 0. Quand h est suffisamment proche de 1,23 on a P (2)(x, y) P(x,y) \(\leq\)1 2 pour tout x \(\geq\)2 et y \(\geq\)2. Par récurrence, pour tout k > 2, P (k) \(\triangleq\)P k est tel que • P (k)(0, 0) = 1, P (k)(0, x) = 0 pour tout x \(\geq\)2, et • pour tout x \(\geq\)2 et y \(\geq\)2, P (k)(x, y) = P (k−1)(x, 0)P(0, y) + X z\(\geq\)2 P (k−1)(x, z)P(z, y) = X z\(\geq\)2 P (k−1)(x, z)P(z, y) \(\leq\) X z\(\geq\)2 P(x,z) 2k−2 \(\cdot\) P(z, y) = P (2)(x, y) 2k−2 \(\leq\)P(x,y) 2k−1 . Comme P(x, y) \(\leq\)1, après 1−log2 F tours, la probabilité de transition vers n'importe quel état y \(\geq\)2 est négligeable, en commençant par n’importe quel état x \(\geq\)2. Bien qu’il existe de nombreux états y, il est facile de voir que lim y → + ∞ P(x,y) P(x, y + 1) = lim y → + ∞ (1 −¯hy)x −(1 −¯hy−1)x (1 −¯hy+1)x −(1 −¯hy)x = lim y → + ∞ ¯hy−1 −¯hy ¯hy −¯hy+1 = 1 ¯h = 1 1 −h. Par conséquent, chaque ligne x de la matrice de transition P décroît comme une séquence géométrique avec le taux 1 1−h > 2 lorsque y est suffisamment grand, et il en va de même pour P (k). En conséquence, lorsque k est suffisamment grand mais quand même de l'ordre de log1/2 F, P y\(\geq\)2 P (k)(x, y) < F pour tout x \(\geq\)2. Autrement dit, avec une écrasante probabilité l'Adversaire perd la partie et ne parvient pas à prédire Qr−1 au tour r −k. Pour h \(\in\)(2/3, 1], un plus Une analyse complexe montre qu’il existe une constante C légèrement supérieure à 1/2, telle qu’elle suffit prendre k = O(logC F). Ainsi le lemme 5.6 est vérifié. ■ Lemme 5.4. (retraité) Étant donné les propriétés 1 à 3 pour chaque tour avant r, ph = h2(1 + h −h2) pour Lr, et le leader \(\ell\)r est honnête avec une probabilité d'au moins ph. 23Par exemple, h = 80 % comme le suggèrent les choix spécifiques des paramètres.

Preuve. D’après le lemme 5.6, l’Adversaire ne peut pas prédire Qr−1 au tour r −k sauf avec probabilité négligeable. Notez que cela ne signifie pas que la probabilité d’avoir un leader honnête soit h pour chaque tour. En effet, étant donné Qr−1, en fonction du nombre d'utilisateurs malveillants au début de la permutation aléatoire de PKr−k, l'Adversaire peut avoir plus d'une option pour Qr et cela peut donc augmenter la probabilité d'un leader malveillant au tour r + 1 — encore une fois, nous lui donnons quelques avantages irréalistes comme dans le lemme 5.6, afin de simplifier l’analyse. Cependant, pour chaque Qr−1 qui n’a pas été interrogé à H par l’Adversaire au tour r −k, pour tout x \(\geq\)1, avec probabilité (1 −h)x−1h que le premier utilisateur honnête se produise à la position x dans le résultat permutation aléatoire de PKr−k. Lorsque x = 1, la probabilité d’avoir un leader honnête au tour r + 1 est en effet h; tandis que lorsque x = 2, l'Adversaire a deux options pour Qr et la probabilité résultante est h2. En considérant seulement ces deux cas, nous avons que la probabilité d'avoir un leader honnête au tour r + 1 est au moins h \(\cdot\) h + (1 −h)h \(\cdot\) h2 = h2(1 + h −h2) comme souhaité. Notez que la probabilité ci-dessus ne prend en compte que le caractère aléatoire du protocole du tour r −k arrondir r. Lorsque tout le hasard du tour 0 au tour r est pris en compte, Qr−1 est encore moins prévisible pour l’Adversaire et la probabilité d’avoir un leader honnête au tour r+1 est de moins h2(1 + h −h2). En remplaçant r + 1 par r et décale tout en arrière d'un tour, le leader \(\ell\)r est honnête avec une probabilité d'au moins h2(1 + h −h2), comme souhaité. De même, dans chaque étape Coin-Genuinely-Flipped, le « leader » de cette étape – c’est-à-dire le vérificateur dans SV r,s dont le titre a la plus petite valeur hash, est honnête avec une probabilité d'au moins h2(1 + h-h2). Ainsi ph = h2(1 + h −h2) pour Lr et le lemme 5.4 est vérifié. ■

Algorand ′

2 Dans cette section, nous construisons une version de Algorand ′ fonctionnant sous l'hypothèse suivante. Hypothèse de la majorité honnête des utilisateurs : plus des 2/3 des utilisateurs de chaque PKr sont honnêtes. Dans la section 8, nous montrons comment remplacer l'hypothèse ci-dessus par la majorité honnête souhaitée des Hypothèse monétaire. 6.1 Notations et paramètres supplémentaires pour Algorand ′ 2 Notations • \(\mu\) \(\in\)Z+ : une limite supérieure pragmatique du nombre d'étapes qui, avec une probabilité écrasante, sera effectivement pris en un seul tour. (Comme nous le verrons, le paramètre \(\mu\) contrôle le nombre clés qu'un utilisateur prépare à l'avance pour chaque tour.) • Lr : une variable aléatoire représentant le nombre d'essais de Bernoulli nécessaires pour obtenir un 1, lorsque chaque l'essai est 1 avec une probabilité ph 2 . Lr sera utilisé pour limiter le temps nécessaire à la génération bloquer Br. • th : une limite inférieure pour le nombre de vérificateurs honnêtes dans une étape s > 1 du tour r, telle que avec Avec une probabilité écrasante (étant donné n et p), il y a > 100 vérificateurs honnêtes dans SV r,s. Paramètres • Relations entre divers paramètres. — Pour chaque étape s > 1 du tour r, n est choisi de telle sorte que, avec une écrasante probabilité,

|HSVr,s| > e et |HSVr,s| + 2|MSVr,s| < 2ème. Notez que les deux inégalités ci-dessus impliquent ensemble |HSV r,s| > 2|MSV r,s| : c'est-à-dire qu'il y a Il existe une majorité honnête des 2/3 parmi les vérificateurs sélectionnés. Plus la valeur de h est proche de 1, plus n doit être petit. En particulier, nous utilisons (variantes de) Tchernofflimite pour garantir que les conditions souhaitées soient maintenues avec une écrasante probabilité. • Exemples de choix de paramètres importants. — F = 10−18. — n \(\approx\)4000, tH \(\approx\)0,69n, k = 70. 6.2 Implémentation de clés éphémères dans Algorand ′ 2 Rappelons qu'un vérificateur i \(\in\)SV r,s signe numériquement son message mr,s je de l'étape s du tour r, par rapport à une clé publique éphémère pkr,s i , en utilisant une clé secrète éphémère skr,s je qu'il détruit promptement après utilisation. Lorsque le nombre d'étapes possibles qu'un tour peut effectuer est plafonné par un entier \(\mu\), nous avons déjà vu comment gérer pratiquement les clés éphémères. Par exemple, comme nous ont expliqué dans Algorand ′ 1 (où \(\mu\) = m + 3), pour gérer toutes ses clés éphémères possibles, de d'un tour r' à un tour r' + 106, i génère une paire (PMK, SMK), où PMK public master clé d'un schéma de signature basé sur l'identité, et SMK sa clé principale secrète correspondante. Utilisateur je fait connaître PMK et utilise SMK pour générer la clé secrète de chaque clé publique éphémère possible (et détruit SMK après l'avoir fait). L’ensemble des clés publiques éphémères de i pour le les tours sont S = {i} \(\times\) {r′, . . . , r′ + 106} \(\times\) {1, . . . ,\(\mu\)}. (Comme discuté, à mesure que le tour r′ + 106 approche, je « rafraîchis » sa paire (PMK, SMK).) En pratique, si \(\mu\) est suffisamment grand, un tour de Algorand ′ 2 ne prendra pas plus de \(\mu\) pas. Dans Cependant, il existe une faible possibilité que, pour certains tours, le nombre d'étapes effectivement prélevé dépassera \(\mu\). Lorsque cela se produira, je serais incapable de signer son message mr,s je pour toute étape s > \(\mu\), car il n'a préparé à l'avance que \(\mu\) clés secrètes pour le tour r. De plus, il ne pouvait pas préparer et publier une nouvelle réserve de clés éphémères, comme indiqué précédemment. En fait, faire il lui faudrait donc insérer une nouvelle clé principale publique PMK′ dans un nouveau bloc. Mais il faudrait arrondir r faites de plus en plus de pas, aucun nouveau bloc ne sera généré. Pourtant, des solutions existent. Par exemple, je peux utiliser la dernière clé éphémère du tour r, pkr,\(\mu\) je , comme suit. Il génère une autre réserve de paires de clés pour le tour r — par exemple, en (1) générant une autre paire de clés principales (PMK, SMK) ; (2) utiliser cette paire pour générer, disons, 106 autres clés éphémères, sk r,\(\mu\)+1 je , . . . , sk r,μ+106 je , correspondant aux étapes \(\mu\)+1, ..., \(\mu\)+106 du tour r ; (3) en utilisant skr,\(\mu\) je au numérique signe PMK (et tout message (r, \(\mu\)) si i \(\in\)SV r,\(\mu\)), par rapport à pkr,\(\mu\) je ; et (4) effacer SMK et skr,\(\mu\) je . Dois-je devenir vérificateur dans une étape \(\mu\) + s avec s \(\in\){1, . . . , 106}, alors je signe numériquement son (r, \(\mu\) + s)- message mr,\(\mu\)+s je par rapport à sa nouvelle clé pk r,\(\mu\)+s je = (je, r, \(\mu\) + s). Bien entendu, pour vérifier cette signature de i, d’autres doivent être certains que cette clé publique correspond à la nouvelle clé principale publique PMK de i. Ainsi, en plus de cette signature, i transmet sa signature numérique de PMK relative à pkr,\(\mu\) je . Bien entendu, cette approche peut être répétée autant de fois que nécessaire, si le cycle continue. pour toujours plus d'étapes ! La dernière clé secrète éphémère est utilisée pour authentifier un nouveau maître public clé, et donc une autre réserve de clés éphémères pour le tour r. Et ainsi de suite.6.3 Le protocole actuel Algorand ′ 2 Rappelons à nouveau qu'à chaque étape s d'un tour r, un vérificateur i \(\in\)SV r,s utilise son secret public à long terme paire de clés pour produire son identifiant, \(\sigma\)r,s je \(\triangleq\)SIGi(r, s, Qr−1), ainsi que SIGi Qr−1 dans le cas s = 1. Vérifier que j'utilise sa bi-clé éphémère, (pkr,s je, skr,s i ), pour signer tout autre message m qui pourrait être requis. Pour plus de simplicité, nous écrivons esigi(m), plutôt que sigpkr,s je (m), pour désigner i est proprement éphémère signature de m dans cette étape, et écrivez ESIGi(m) au lieu de SIGpkr,s je (m) \(\triangleq\)(je, m, esigi(m)). Étape 1 : Bloquer la proposition Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 1 du tour r dès qu'il a CERT r−1, qui permet de calculer sans ambiguïté H(Br−1) et Qr−1. • L'utilisateur i utilise Qr−1 pour vérifier si i \(\in\)SV r,1 ou non. Si i /\(\in\)SV r,1, il ne fait rien pour l’étape 1. • Si i \(\in\)SV r,1, c'est-à-dire si i est un leader potentiel, alors il fait ce qui suit. (a) Si j'ai vu B0, . . . , Br−1 lui-même (tout Bj = Bj ǫ peut être facilement dérivé de sa valeur hash dans CERT j et est donc supposé « vu »), puis il collecte les paiements ronds qui ont lui a été propagé jusqu'à présent et calcule un ensemble de paie maximal PAY r je d'eux. (b) Si je n’ai pas vu tous les B0, . . . , Br−1 encore, puis il fixe PAY r je = \(\emptyset\). (c) Ensuite, i calcule son « bloc candidat » Br je = (r, PAYER r je , SIGi(Qr−1), H(Br−1)). (c) Finalement, i calcule le message mr,1 je = (Br je , esigi(H(Br je )), \(\sigma\)r,1 i ), détruit son éphémère clé secrète skr,1 i , puis propage deux messages, mr,1 je et (SIGi(Qr−1), \(\sigma\)r,1 je ), séparément mais simultanément.a aQuand i est le leader, SIGi(Qr−1) permet aux autres de calculer Qr = H(SIGi(Qr−1), r).

Propagation sélective Pour raccourcir l'exécution globale de l'étape 1 et de l'ensemble du tour, il est important que le (r, 1)- les messages sont propagés de manière sélective. Autrement dit, pour chaque utilisateur j du système, • Pour le premier message (r, 1) qu'il reçoit et vérifie avec succès, s'il contient un bloc ou n'est qu'un identifiant et une signature de Qr−1, le joueur j le propage comme d'habitude. • Pour tous les autres (r, 1)-messages que le joueur j reçoit et vérifie avec succès, il propage uniquement si la valeur hash de l'identifiant qu'il contient est la plus petite parmi les valeurs hash des informations d'identification contenues dans tous les messages (r, 1) qu'il a reçus et vérifiés avec succès ainsi loin. • Cependant, si j reçoit deux messages différents de la forme mr,1 je du même joueur je,b il supprime le second, quelle que soit la valeur hash des informations d'identification de i. Notez que, dans le cadre d'une propagation sélective, il est utile que chaque leader potentiel i propage son identifiant \(\sigma\)r,1 je séparément de monsieur,1 i :c ces petits messages voyagent plus vite que les blocs, assurez-vous propagation rapide du mr,1 i est l'endroit où les informations d'identification contenues ont de petites valeurs hash, tandis que faire disparaître rapidement ceux avec de grandes valeurs hash. aC'est-à-dire que toutes les signatures sont correctes et, si elle est de la forme mr,1 i , le bloc et son hash sont valides — bien que j ne vérifie pas si le ensemble de paie inclus est maximal pour i ou non. bCe qui signifie que je suis malveillant. cNous remercions Georgios Vlachos pour cette suggestion.Étape 2 : La première étape du protocole de consensus gradué GC Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 2 du tour r dès qu'il a CERT r−1. • L'utilisateur i attend un temps maximum t2 \(\triangleq\) \(\lambda\) + Λ. En attendant, j'agis comme suit. 1. Après avoir attendu le temps 2\(\lambda\), il trouve l’utilisateur \(\ell\)tel que H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) pour tous informations d'identification \(\sigma\)r,1 j qui font partie des messages (r, 1) vérifiés avec succès qu'il a reçus jusqu'à présent.a 2. Si il a reçu un bloquer Br−1, lequel matchs le hash valeur H(Br−1) contenu dans CERT r−1,b et s'il a reçu de \(\ell\)un message valide mr,1 \(\ell\) = (Fr \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),c alors j'arrête d'attendre et définit v′ je \(\triangleq\)(H(Br \(\ell\)), \(\ell\)). 3. Sinon, lorsque le temps t2 est écoulé, je fixe v′ je \(\triangleq\) \(\bot\). 4. Lorsque la valeur de v′ i a été défini, je calcule Qr−1 à partir de CERT r−1 et vérifie si i \(\in\)SV r,2 ou non. 5. Si i \(\in\)SV r,2, i calcule le message mr,2 je \(\triangleq\)(ESIGi(v′ je), \(\sigma\)r,2 i ),d détruit son éphémère clé secrète skr,2 i , puis propage mr,2 je. Sinon, j'arrête sans propager n'importe quoi. aEssentiellement, l'utilisateur i décide en privé que le leader du tour r est l'utilisateur \(\ell\). bBien sûr, si CERT r−1 indique que Br−1 = Br−1 ǫ , alors j’ai déjà « reçu » Br−1 au moment où il a CERT r−1. cEncore une fois, les signatures du joueur \(\ell\) et les hashes sont tous vérifiés avec succès, et PAY r \(\ell\)en Br \(\ell\)est un ensemble de paie valide pour round r — bien que je ne vérifie pas si PAY r \(\ell\)est maximal pour \(\ell\)ou non. Si Br \(\ell\)contient un ensemble de paie vide, alors il n’est en fait pas nécessaire que je voie Br−1 avant de vérifier si Br \(\ell\)est valide ou non. dLe message monsieur,2 je signale que le joueur i considère la première composante de v′ je suis le hash du bloc suivant, ou considère que le bloc suivant est vide.

Étape 3 : la deuxième étape du GC Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 3 du tour r dès qu'il a CERT r−1. • L'utilisateur i attend un temps maximum t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ. En attendant, j'agis comme suit. 1. S'il existe une valeur v telle qu'il a reçu au moins les messages valides mr,2 j de la forme (ESIGj(v), \(\sigma\)r,2 j ), sans aucune contradiction,a puis il arrête d'attendre et pose v′ = v. 2. Sinon, lorsque le temps t3 est écoulé, il pose v′ = \(\bot\). 3. Lorsque la valeur de v′ a été définie, je calcule Qr−1 à partir de CERT r−1 et vérifie si i \(\in\)SV r,3 ou non. 4. Si i \(\in\)SV r,3, alors i calcule le message mr,3 je \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 je ), détruit son clé secrète éphémère skr,3 i , puis propage mr,3 je. Sinon, j'arrête sans propager quoi que ce soit. aC'est-à-dire qu'il n'a pas reçu deux messages valides contenant respectivement ESIGj(v) et un ESIGj(ˆv) différent, d'un joueur j. Ici et à partir de là, sauf dans les Conditions de Fin définies plus loin, chaque fois qu'un joueur honnête veut des messages d'une forme donnée, les messages se contredisant ne sont jamais comptés ni considérés comme valides.

Étape 4 : Résultat de GC et première étape de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape 4 du tour r dès qu'il termine sa propre étape 3. • L'utilisateur i attend un temps maximum 2\(\lambda\).a Pendant l'attente, i agit comme suit. 1. Il calcule vi et gi, la sortie de GC, comme suit. (a) S'il existe une valeur v′ ̸= \(\bot\)telle qu'il a reçu au moins les messages valides monsieur,3 j = (ESIGj(v′), \(\sigma\)r,3 j ), puis il arrête d'attendre et pose vi \(\triangleq\)v′ et gi \(\triangleq\)2. (b) S'il a reçu au moins les messages valides mr,3 j = (ESIGj(\(\bot\)), \(\sigma\)r,3 j ), puis il s'arrête attend et définit vi \(\triangleq\) \(\bot\)et gi \(\triangleq\)0.b (c) Sinon, lorsque le temps 2\(\lambda\) s'écoule, s'il existe une valeur v′ ̸= \(\bot\) telle qu'il a reçu au moins ⌈tH 2 ⌉messages valides mr,j j = (ESIGj(v′), \(\sigma\)r,3 j ), alors il pose vi \(\triangleq\)v′ et gi \(\triangleq\)1.c (d) Sinon, lorsque le temps 2\(\lambda\) est écoulé, il définit vi \(\triangleq\) \(\bot\) et gi \(\triangleq\)0. 2. Lorsque les valeurs vi et gi ont été définies, i calcule bi, l'entrée de BBA⋆, comme suit : bi \(\triangleq\)0 si gi = 2, et bi \(\triangleq\)1 sinon. 3. i calcule Qr−1 à partir de CERT r−1 et vérifie si i \(\in\)SV r,4 ou non. 4. Si i \(\in\)SV r,4, il calcule le message mr,4 je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 je ), détruit son clé secrète éphémère skr,4 je , et propage mr,4 je. Sinon, j'arrête sans propager n'importe quoi. aAinsi, le temps total maximum écoulé depuis que i commence son étape 1 du tour r pourrait être t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ. bQue l'étape (b) figure ou non dans le protocole n'affecte pas son exactitude. Cependant, la présence de l'étape (b) permet à l’étape 4 de se terminer en moins de 2 \(\lambda\) si suffisamment de vérificateurs de l’étape 3 ont « signé \(\bot\) ». cOn peut prouver que le v′ dans ce cas, s’il existe, doit être unique.Étape s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3 : Une étape fixée à 0 de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape s du tour r dès qu'il termine sa propre étape s −1. • L'utilisateur i attend un temps maximum 2\(\lambda\).a Pendant l'attente, i agit comme suit. – Condition de fin 0 : Si à un moment donné il existe une chaîne v ̸= \(\bot\)et une étape s′ telle que (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 — c'est-à-dire que l'étape s′ est une étape Coin-Fixed-To-0, (b) j’ai reçu au moins les messages valides mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),b et (c) j'ai reçu un message valide (SIGj(Qr−1), \(\sigma\)r,1 j ) avec j étant le deuxième composante de v, puis, j'arrête d'attendre et termine sa propre exécution du Step s (et en fait du tour r) tout de suite sans rien propager en tant que vérificateur (r, s) ; définit H(Br) comme le premier composante de v ; et définit son propre CERT r comme étant l'ensemble des messages mr,s′−1 j de l'étape (b) avec (SIGj(Qr−1), \(\sigma\)r,1 j ).c – Condition de fin 1 : si à un moment donné il existe une étape s′ telle que (a') 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 — c'est-à-dire que l'étape s′ est une étape Coin-Fixed-To-1, et (b’) j’ai reçu au moins les messages valides mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),d puis, j'arrête d'attendre et termine sa propre exécution du Step s (et en fait du tour r) à droite sans propager quoi que ce soit en tant que vérificateur (r, s) ; ensembles Br = Br ǫ ; et définit le sien CERT r est l'ensemble des messages mr,s′−1 j de la sous-étape (b’). – Si à n'importe quel pointe il a reçu à le moins e valide monsieur,s−1 j c'est de le formulaire (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il arrête d'attendre et fixe bi \(\triangleq\)1. – Si à n'importe quel pointe il a reçu à le moins e valide monsieur,s−1 j c'est de le formulaire (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), mais ils ne sont pas d'accord sur le même v, alors il s'arrête en attente et définit bi \(\triangleq\)0. – Sinon, lorsque le temps 2\(\lambda\) est écoulé, i définit bi \(\triangleq\)0. – Lorsque la valeur bi a été définie, i calcule Qr−1 à partir de CERT r−1 et vérifie si je \(\in\)SV r,s. – Si i \(\in\)SV r,s, i calcule le message mr,s je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) avec vi étant la valeur qu'il a calculée à l'étape 4, détruit sa clé secrète éphémère skr,s moi, et puis se propage mr, s je. Sinon, je m'arrête sans rien propager. aAinsi, le temps total maximum depuis que i commence son étape 1 du tour r pourrait être ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ. bUn tel message du joueur j est compté même si le joueur i a également reçu un message de j signant pour 1. Des choses similaires pour la condition finale 1. Comme le montre l'analyse, il s'agit de garantir que tous les utilisateurs honnêtes savent CERT r dans le temps \(\lambda\) les uns des autres. cUser i connaît maintenant H(Br) et son propre tour r se termine. Il lui suffit d'attendre que le bloc Br soit réellement lui est propagé, ce qui peut prendre un certain temps supplémentaire. Il aide toujours à propager des messages en tant qu'utilisateur générique, mais n'initie aucune propagation en tant que vérificateur (r, s). Il a notamment contribué à propager tous les messages dans son CERT r, ce qui est suffisant pour notre protocole. Notez qu'il doit également définir bi \(\triangleq\)0 pour le protocole binaire BA, mais bi n'est de toute façon pas nécessaire dans ce cas. Des choses similaires pour toutes les instructions futures. dDans ce cas, peu importe les vj. 65Étape s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3 : Une étape Coin-Fixed-To-1 de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape s du tour r dès qu'il termine sa propre étape s −1. • L'utilisateur i attend un temps maximum 2\(\lambda\). En attendant, j'agis comme suit. – Condition de fin 0 : les mêmes instructions que dans une étape Coin-Fixed-To-0. – Condition de fin 1 : les mêmes instructions que dans une étape Coin-Fixed-To-0. – Si à n'importe quel pointe il a reçu à le moins e valide monsieur,s−1 j c'est de le formulaire (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il arrête d'attendre et fixe bi \(\triangleq\)0.a – Sinon, lorsque le temps 2\(\lambda\) est écoulé, i définit bi \(\triangleq\)1. – Lorsque la valeur bi a été définie, i calcule Qr−1 à partir de CERT r−1 et vérifie si je \(\in\)SV r,s. – Si i \(\in\)SV r,s, i calcule le message mr,s je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) avec vi étant la valeur qu'il a calculée à l'étape 4, détruit sa clé secrète éphémère skr,s moi, et puis se propage mr, s je. Sinon, je m'arrête sans rien propager. aNotez que recevoir des messages (r, s −1) valides signant pour 1 signifierait la condition de fin 1. Étape s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3 : Une étape véritablement inversée de BBA⋆ Instructions pour chaque utilisateur i \(\in\)PKr−k : L'utilisateur i démarre sa propre étape s du tour r dès qu'il termine son propre pas s −1. • L'utilisateur i attend un temps maximum 2\(\lambda\). En attendant, j'agis comme suit. – Condition de fin 0 : les mêmes instructions que dans une étape Coin-Fixed-To-0. – Condition de fin 1 : les mêmes instructions que dans une étape Coin-Fixed-To-0. – Si à n'importe quel pointe il a reçu à le moins e valide monsieur,s−1 j c'est de le formulaire (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il arrête d'attendre et fixe bi \(\triangleq\)0. – Si à n'importe quel pointe il a reçu à le moins e valide monsieur,s−1 j c'est de le formulaire (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), puis il arrête d'attendre et fixe bi \(\triangleq\)1. – Sinon, lorsque le temps 2\(\lambda\) est écoulé, soit SV r,s−1 je être l’ensemble des (r, s −1)-vérificateurs de pour qui il a reçu un message valide mr,s−1 j , je définit bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 je H(\(\sigma\)r,s−1 j )). – Lorsque la valeur bi a été définie, i calcule Qr−1 à partir de CERT r−1 et vérifie si je \(\in\)SV r,s. – Si i \(\in\)SV r,s, i calcule le message mr,s je \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ) avec vi étant la valeur qu'il a calculée à l'étape 4, détruit sa clé secrète éphémère skr,s moi, et puis se propage mr, s je. Sinon, je m'arrête sans rien propager. Remarque. En principe, comme indiqué à la sous-section 6.2, le protocole peut prendre arbitrairement plusieurs étapes dans un tour. Si cela se produit, comme indiqué, un utilisateur i \(\in\)SV r,s avec s > \(\mu\) a épuisé

sa réserve de clés éphémères pré-générées et doit authentifier son message (r, s) mr,s je par un « cascade » de clés éphémères. Ainsi, le message de mon message devient un peu plus long et sa transmission est plus longue. les messages prendront un peu plus de temps. En conséquence, après tant d'étapes d'un tour donné, la valeur de le paramètre \(\lambda\) augmentera automatiquement légèrement. (Mais il revient au \(\lambda\) original une fois un nouveau un bloc est produit et un nouveau tour commence.) Reconstruction du bloc Round-r par des non-vérificateurs Instructions pour chaque utilisateur i dans le système : L'utilisateur i démarre son propre tour r dès qu'il a CERT r−1. • je suis les instructions de chaque étape du protocole, participe à la propagation de tous messages, mais n'initie aucune propagation dans une étape s'il n'y est pas vérificateur. • i termine son propre tour r en entrant soit la condition de fin 0, soit la condition de fin 1 dans certains étape, avec le CERT r correspondant. • A partir de là, il commence son tour r + 1 en attendant de recevoir le bloc Br proprement dit (sauf si il l'a déjà reçu), dont hash H(Br) a été épinglé par le CERT r. Encore une fois, si CERT r indique que Br = Br ǫ, le je connaît Br dès qu'il a le CERT r. 6.4 Analyse de Algorand′ 2 L’analyse de Algorand′ 2 se déduit facilement de celui de Algorand′ 1. Essentiellement, en Algorand ′ 2, avec probabilité écrasante, (a) tous les utilisateurs honnêtes sont d’accord sur le même bloc Br ; le leader d'un nouveau le bloc est honnête avec une probabilité d'au moins ph = h2(1 + h −h2).

Gestion des utilisateurs honnêtes hors ligne

Comme nous l'avons dit, un utilisateur honnête suit toutes les instructions qui lui sont prescrites, parmi lesquelles celle d'être en ligne et exécuter le protocole. Ceci ne représente pas une charge majeure dans Algorand, puisque le calcul et la bande passante requise par un utilisateur honnête est assez modeste. Précisons cependant que Algorand peut être facilement modifié de manière à fonctionner dans deux modèles, dans lesquels les utilisateurs honnêtes sont autorisés à être déconnectés dans de grands nombres. Avant d'évoquer ces deux modèles, précisons que, si le pourcentage de joueurs honnêtes étaient de 95 %, Algorand pouvait toujours être exécuté en définissant tous les paramètres en supposant à la place que h = 80 %. En conséquence, Algorand continuerait à fonctionner correctement même si au plus la moitié des joueurs honnêtes choisi de se déconnecter (en effet, un cas majeur d'« absentéisme »). En fait, à tout moment, au moins 80% des joueurs en ligne seraient honnêtes. De la participation continue à l’honnêteté paresseuse Comme nous l'avons vu, Algorand ′ 1 et Algorand′ 2 choisir le paramètre de rétrospection k. Montrons maintenant que choisir k proprement grand permet de supprimer l’exigence de participation continue. Cette exigence garantit une propriété cruciale : à savoir, que le protocole BA sous-jacent BBA⋆a une majorité honnête et appropriée. Expliquons maintenant à quel point l'honnêteté offre une manière alternative et attrayante de satisfaire cette propriété.

Rappelons qu'un utilisateur i est paresseux mais honnête si (1) il suit toutes les instructions qui lui sont prescrites, lorsque il lui est demandé de participer au protocole, et (2) il lui est demandé de participer au protocole uniquement très rarement — par exemple, une fois par semaine — avec un préavis approprié et potentiellement recevoir des récompenses lorsqu'il participe. Pour permettre à Algorand de travailler avec de tels acteurs, il suffit de « choisir les vérificateurs des cycle en cours parmi les utilisateurs déjà présents dans le système lors d’un cycle beaucoup plus ancien. Rappelons en effet que les vérificateurs pour un tour r sont choisis parmi les utilisateurs du tour r −k, et les sélections sont faites en fonction sur la quantité Qr−1. Notez qu'une semaine compte environ 10 000 minutes et supposons qu'un le tour prend environ (par exemple, en moyenne) 5 minutes, donc une semaine compte environ 2 000 tours. Supposons qu'à un moment donné, un utilisateur i souhaite planifier son temps et savoir s'il va être un vérificateur dans la semaine à venir. Le protocole choisit désormais les vérificateurs pour un tour r parmi les utilisateurs de autour de r −k −2 000, et les sélections sont basées sur Qr−2 001. Au tour r, joueur que je connais déjà les valeurs Qr−2 000, . . . , Qr−1, puisqu’ils font en réalité partie des blockchain. Alors, pour chaque M entre 1 et 2 000, i est vérificateur dans une étape s du tour r + M si et seulement si .H SIGI r + M, s, Qr+M−2,001 \(\leq\)p. Ainsi, pour vérifier s'il va être appelé à agir comme vérificateur lors des 2 000 prochains tours, je dois calculer \(\sigma\)M,s je = SIGi r + M, s, Qr+M−2,001 pour M = 1 à 2 000 et pour chaque pas s, et vérifier si .H(\(\sigma\)M,s je ) \(\leq\)p pour certains d'entre eux. Si le calcul d'une signature numérique prend une milliseconde, alors toute cette opération lui prendra environ 1 minute de calcul. S'il n'est pas sélectionné comme vérificateur dans n’importe lequel de ces tours, il peut alors se déconnecter avec une « conscience honnête ». Avait-il continuellement participé, il aurait de toute façon fait essentiellement 0 pas dans les 2 000 tours suivants ! Si, au contraire, il est sélectionné pour être vérificateur lors d'un de ces tours, puis il se prépare (par exemple, en obtenant tous les informations nécessaires) pour agir en tant que vérificateur honnête au moment approprié. En agissant ainsi, un vérificateur de potentiel paresseux mais honnête ne manque que de participer à la propagation de messages. Mais la propagation des messages est généralement robuste. De plus, les payeurs et les bénéficiaires de les paiements récemment propagés devraient être en ligne pour surveiller ce qu'il advient de leurs paiements, et ainsi ils participeront à la propagation du message, s'ils sont honnêtes.

Protocole Algorand ′ avec une majorité honnête d'argent

Nous montrons maintenant, enfin, comment remplacer l'hypothèse de la majorité honnête des utilisateurs par l'hypothèse beaucoup plus hypothèse significative de majorité honnête de l’argent. L'idée de base est (dans une saveur proof-of-stake) « pour sélectionner un utilisateur i \(\in\)PKr−k pour appartenir à SV r,s avec un poids (c'est-à-dire un pouvoir de décision) proportionnel à le montant d’argent que je possède. »24 D’après notre hypothèse HMM, nous pouvons choisir si ce montant doit être détenu au tour r −k ou au (début du) tour r. En supposant que cela ne nous dérange pas une participation continue, nous optons pour ce dernier choix. (Pour supprimer la participation continue, nous aurions opté pour le premier choix. Mieux dit, pour le montant d'argent possédé au tour r −k −2 000.) Il existe de nombreuses façons de mettre en œuvre cette idée. Le moyen le plus simple serait de maintenir chaque touche enfoncée au plus 1 unité de monnaie puis sélectionner au hasard n utilisateurs i parmi PKr−k tel que a(r) je = 1. 24Il faudrait dire PKr−k−2 000 pour remplacer une participation continue. Par souci de simplicité, puisqu'on peut souhaiter exiger participation continue de toute façon, on utilise PKr−k comme avant, de manière à porter un paramètre de moins.

La prochaine mise en œuvre la plus simple La prochaine mise en œuvre la plus simple pourrait consister à exiger que chaque clé publique possède un montant maximum d'argent M, pour certains M fixes. La valeur M est suffisamment petite par rapport au montant total de de l'argent dans le système, de telle sorte que la probabilité qu'une clé appartienne à l'ensemble de vérificateurs de plus d'un intervenir dans — disons — k tours est négligeable. Alors, une clé i \(\in\)PKr−k, possédant une somme d’argent a(r) je au tour r, est choisi pour appartenir à SV r,s si .H SIGI r, s, Qr−1 \(\leq\)p \(\cdot\) a(r) je M . Et tout se passe comme avant. Une mise en œuvre plus complexe La dernière implémentation « a forcé un riche participant au système à posséder de nombreuses clés ». Une implémentation alternative, décrite ci-dessous, généralise la notion de statut et considère chaque utilisateur i doit être constitué de K + 1 copies (i, v), dont chacune est sélectionnée indépendamment pour être un vérificateur, et possédera sa propre clé éphémère (pkr,s je,v,skr,s i,v) dans une étape s d'un tour r. La valeur K dépend sur le montant d'argent a(r) je appartenant à moi au tour r. Voyons maintenant plus en détail comment fonctionne un tel système. Nombre d'exemplaires Soit n la cardinalité attendue ciblée de chaque ensemble de vérificateurs, et soit a(r) je être le montant d'argent détenu par un utilisateur i au tour r. Soit Ar le montant total d'argent possédé par les utilisateurs de PKr−k au tour r, c'est-à-dire Ar = X i\(\in\)P Kr−k un(r) je. Si i est un utilisateur dans PKr−k, alors les copies de i sont (i, 1), . . . , (i, K + 1), où K = $ n \(\cdot\) a(r) je Ar % . Exemple. Soit n = 1 000, Ar = 109 et a(r) je = 3,7 millions. Ensuite, K = 103 \(\cdot\) (3,7 \(\cdot\) 106) 109  = ⌊3,7⌋= 3 . Vérificateurs et informations d'identification Soit un utilisateur de PKr−k avec K + 1 copies. Pour chaque v = 1, . . . , K, copie (i, v) appartient automatiquement à SV r,s. Autrement dit, mes informations d'identification sont \(\sigma\)r,s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1), mais la condition correspondante devient .H(\(\sigma\)r,s i,v) \(\leq\)1, ce qui est toujours vrai. Pour la copie (i, K + 1), pour chaque étape s du tour r, je vérifie si .H SIGI (je, K + 1), r, s, Qr−1 \(\leq\)a(r) je n Ar−K.

Si tel est le cas, la copie (i, K + 1) appartient à SV r,s. Pour le prouver, je propage le badge \(\sigma\)r,1 je,K+1 = SIGi (je, K + 1), r, s, Qr−1 . Exemple. Comme dans l’exemple précédent, soit n = 1K, a(r) je = 3,7M, Ar = 1B et j'en ai 4 exemplaires : (i, 1), . . . , (i, 4). Ensuite, les 3 premières copies appartiennent automatiquement à SV r,s. Pour le 4ème, conceptuellement, Algorand ′ lance indépendamment une pièce biaisée, dont la probabilité de face est de 0,7. Copier (i, 4) est sélectionné si et seulement si le tirage au sort est face. (Bien sûr, ce tirage au sort biaisé est mis en œuvre en hashing, en signant et en comparant - comme nous le faisons). l'ai fait tout au long de cet article - afin de me permettre de prouver son résultat.) Affaires comme d'habitude Après avoir expliqué comment les vérificateurs sont sélectionnés et comment leurs informations d'identification sont calculé à chaque étape d'un tour r, l'exécution d'un tour est similaire à celle déjà expliquée.

Gestion des forks

Ayant réduit la probabilité de fourchettes à 10−12 ou 10−18, il est pratiquement inutile de gérer au cas où ils se produiraient. Algorand, cependant, peut également utiliser divers fork procédures de résolution, avec ou sans justificatif de travail. Une manière possible de demander aux utilisateurs de résoudre les forks est la suivante : • Suivez la chaîne la plus longue si un utilisateur voit plusieurs chaînes. • S'il y a plusieurs chaînes les plus longues, suivez celle avec un bloc non vide à la fin. Si ils ont tous des blocs vides à la fin, considérez leurs avant-derniers blocs. • S'il y a plusieurs chaînes les plus longues avec des blocs non vides à la fin, disons que les chaînes sont de longueur r, suivez celui dont le chef du bloc r a le plus petit identifiant. S'il y a des liens, suivez celui dont le bloc r lui-même a la plus petite valeur hash. S'il y a encore des égalités, suivez les celui dont le bloc r est ordonné le premier lexicographiquement.

Gestion des partitions réseau

Comme indiqué, nous supposons que les temps de propagation des messages entre tous les utilisateurs du réseau sont limités par \(\lambda\) et Λ. Ce n’est pas une hypothèse solide, car l’Internet d’aujourd’hui est rapide et robuste, et les valeurs réelles de ces paramètres sont tout à fait raisonnables. Précisons ici que Algorand ′ 2 continue de fonctionner même si Internet est parfois divisé en deux parties. Le cas où Internet est divisé en plus de deux parties, c'est similaire. 10.1 Partitions physiques Tout d’abord, la partition peut être provoquée par des raisons physiques. Par exemple, un énorme tremblement de terre peut finissent par briser complètement la connexion entre l’Europe et l’Amérique. Dans ce cas, le les utilisateurs malveillants sont également partitionnés et il n'y a aucune communication entre les deux parties. Ainsi

il y aura deux Adversaires, un pour la partie 1 et l'autre pour la partie 2. Chaque Adversaire essaie toujours de rompre le protocole dans sa propre partie. Supposons que la partition se produise au milieu du tour r. Ensuite, chaque utilisateur est toujours sélectionné comme vérificateur basé sur PKr−k, avec la même probabilité que précédemment. Soit HSV r,s je et MSV r,s je respectivement être l’ensemble des vérificateurs honnêtes et malveillants dans une étape s de la partie i \(\in\){1, 2}. Nous avons |HSVr,s 1 | + |MSVr,s 1 | + |HSVr,s 2 | + |MSVr,s 2 | = |VHS r,s| + |MSVr,s|. Notez que |HSV r,s| + |MSVr,s| < |HSVr,s| + 2|MSVr,s| < 2th avec une probabilité écrasante. Si une partie j'ai |HSV r,s je | + |MSVr,s je | \(\geq\)tH avec une probabilité non négligeable, par exemple 1 %, alors le probabilité que |HSV r,s 3−i| + |MSVr,s 3−i| \(\geq\)tH est très faible, par exemple 10−16 lorsque F = 10−18. Dans ce cas, autant considérer la plus petite partie comme étant hors ligne, car il n'y aura pas assez de vérificateurs dans cette partie pour générer les signatures pour certifier un bloc. Considérons la plus grande partie, disons la partie 1 sans perte de généralité. Bien que |HSV r,s| < th avec une probabilité négligeable à chaque étape s, lorsque le réseau est partitionné, |HSV r,s 1 | peut-être inférieur à tH avec une probabilité non négligeable. Dans ce cas, l'Adversaire peut, avec quelques autre probabilité non négligeable, forcer le protocole binaire BA dans un fork au tour r, avec un bloc non vide Br et le bloc vide Br ǫ tous deux ayant des signatures valides.25 Par exemple, dans un Coin-Fixed-To-0 step s, tous les vérificateurs en HSV r,s 1 signé pour le bit 0 et H(Br), et propagé leur messages. Tous les vérificateurs dans MSV r,s 1 ont également signé 0 et H(Br), mais ont caché leurs messages. Parce que |HSVr,s 1 | + |MSVr,s 1 | \(\geq\)th, le système dispose de suffisamment de signatures pour certifier Br. Cependant, depuis le les vérificateurs malveillants ont retenu leurs signatures, les utilisateurs entrent dans l'étape s + 1, qui est une étape Coin-Fixed-To1. Parce que |HSV r,s 1 | < tH dû à la partition, les vérificateurs en HSV r,s+1 1 je n'ai pas vu ça signatures pour le bit 0 et ils ont tous signé pour le bit 1. Tous les vérificateurs dans MSV r,s+1 1 a fait de même. Parce que |HSVr,s+1 1 | + |MSVr,s+1 1 | \(\geq\)tH, le système dispose de suffisamment de signatures pour certifier Br ǫ. L'adversaire crée ensuite un fork en libérant les signatures de MSV r,s 1 pour 0 et H(Br). En conséquence, il y aura deux Qr, définis par les blocs correspondants du tour r. Cependant, la fourche ne continuera pas et une seule des deux branches pourra pousser au tour r+1. Instructions supplémentaires pour Algorand ′ 2. En voyant un bloc Br non vide et le bloc vide bloc Br ǫ , suit celui non vide (et le Qr défini par lui). En effet, en demandant aux utilisateurs d'opter pour le bloc non vide dans le protocole, si un grand nombre d'utilisateurs honnêtes dans PKr+1−k se rendent compte qu'il y a un fork au début du tour r +1, alors le le bloc vide n’aura pas assez d’abonnés et ne grandira pas. Supposons que l'Adversaire parvienne à partitionner les utilisateurs honnêtes afin que certains utilisateurs honnêtes voient Br (et peut-être Br ǫ), et certains ne voient que Br ǫ. Parce que l'Adversaire ne peut pas dire lequel d'entre eux sera un vérificateur à la suite de Br et lequel d'entre eux sera un vérificateur après Br et lequel d'entre eux sera un vérificateur après Br et lequel sera un vérificateur suivant Br ǫ , les utilisateurs honnêtes sont partitionnés aléatoirement et chacun d'entre eux reste devient vérificateur (soit par rapport à Br, soit par rapport à Br ǫ) dans une étape s > 1 avec probabilité p. Pour les utilisateurs malveillants, chacun d'entre eux peut avoir deux chances de devenir vérificateur, une avec Br et l'autre avec Br ǫ, chacun avec une probabilité p indépendamment. Soit HSV r+1,s 1;Br être l'ensemble des vérificateurs honnêtes à l'étape s du tour r+1 suivant Br. Autres notations comme HSV r+1,s 1;Brǫ , MSV r+1,s 1;Br et MSV r+1,s 1;Brǫ sont définis de la même manière. En direction de Tchernoff, c'est facile 25Avoir un fork avec deux blocs non vides n'est pas possible avec ou sans partitions, sauf avec des probabilité.voir cela avec une écrasante probabilité, |HSVr+1,s 1;Br | + |HSVr+1,s 1;Br | + |MSV r+1,s 1;Br | + |MSV r+1,s 1;Br | < 2ème. En conséquence, les deux succursales ne peuvent pas toutes deux avoir les signatures appropriées certifiant un bloc pour le tour r + 1 dans la même étape s. De plus, puisque les probabilités de sélection pour deux étapes s et s′ sont les pareil et les sélections sont indépendantes, également avec une probabilité écrasante |HSVr+1,s 1;Br | + |MSV r+1,s 1;Br | + |HSVr+1,s′ 1;Brǫ | + |MSV r+1,s′ 1;Brǫ | < 2eH, pour deux étapes s et s′ quelconques. Lorsque F = 10−18, par l'union liée, tant que l'Adversaire ne peut pas partitionner les utilisateurs honnêtes pendant une longue période (disons 104 étapes, soit plus de 55 heures avec \(\lambda\) = 10 secondes26), avec une forte probabilité (disons 1−10−10) au plus une branche aura les signatures propres pour certifier un bloc au tour r+1. Enfin, si la partition physique a créé deux parties ayant à peu près la même taille, alors la probabilité que |HSV r,s je | + |MSVr,s je | \(\geq\)tH est petit pour chaque partie i. Suite à une analyse similaire, même si l'Adversaire parvient à créer un fork avec une probabilité non négligeable dans chaque partie pour le tour r, au plus une des quatre branches peut pousser au tour r + 1. 10.2 Partition contradictoire Deuxièmement, la partition peut être provoquée par l'Adversaire, de sorte que les messages propagés par les utilisateurs honnêtes d’une part n’atteindra pas directement les utilisateurs honnêtes de l’autre partie, mais l'Adversaire est capable de transmettre des messages entre les deux parties. Pourtant, une fois un message d'un une partie parvient à un utilisateur honnête dans l'autre partie, elle sera propagée dans cette dernière comme d'habitude. Si le L'adversaire est prêt à dépenser beaucoup d'argent, il est concevable qu'il puisse pirater le Internet et partitionnez-le comme ça pendant un moment. L'analyse est similaire à celle de la plus grande partie de la partition physique ci-dessus (la plus petite partie peut être considérée comme ayant une population de 0) : l'Adversaire peut être capable de créer un fork et chaque utilisateur honnête ne voit qu'une seule des branches, mais au plus une branche peut croître. 10.3 Partitions réseau en somme Bien que des partitions réseau puissent se produire et qu'un fork en un seul tour puisse se produire sous les partitions, il Il n'y a pas d'ambiguïté persistante : une fourchette a une durée de vie très éphémère, et ne dure en fait qu'un seul tour au maximum. Dans toutes les parties de la partition sauf une au plus, les utilisateurs ne peuvent pas générer de nouveau bloc et donc (a) se rendre compte qu'il existe une partition dans le réseau et (b) ne jamais s'appuyer sur des blocs qui « disparaîtront ». Remerciements Nous tenons tout d'abord à remercier Sergey Gorbunov, co-auteur du système Democoin cité. Nos plus sincères remerciements vont à Maurice Herlihy, pour ses nombreux échanges éclairants, pour avoir souligné que le pipeline améliorera les performances de débit de Algorand, et pour améliorer considérablement le 26Remarquons qu'un utilisateur termine une étape s sans attendre 2\(\lambda\) temps seulement s'il a vu au moins les signatures de l'étape s. même message. Lorsqu’il n’y a pas assez de signatures, chaque étape durera 2\(\lambda\).

exposition d’une version antérieure de cet article. Un grand merci à Sergio Rajsbaum, pour ses commentaires sur une version antérieure de cet article. Un grand merci à Vinod Vaikuntanathan, pour plusieurs discussions approfondies et des idées. Un grand merci à Yossi Gilad, Rotem Hamo, Georgios Vlachos et Nickolai Zeldovich pour avoir commencé à tester ces idées et pour de nombreux commentaires et discussions utiles. Silvio Micali tient à remercier personnellement Ron Rivest pour ses innombrables discussions et conseils en recherche cryptographique pendant plus de 3 décennies, pour avoir co-écrit le système de micropaiement cité qui a inspiré l’un des mécanismes de sélection des vérificateurs de Algorand. Nous espérons amener cette technologie au niveau supérieur. Pendant ce temps, le voyage et la compagnie sont très amusants, pour lesquels nous sommes très reconnaissants.