Zusammenfassung

Ein öffentliches Hauptbuch ist eine manipulationssichere Datenfolge, die von jedem gelesen und ergänzt werden kann. Öffentliche Hauptbücher haben unzählige und überzeugende Verwendungsmöglichkeiten. Sie können alle Arten vor aller Augen sichern von Transaktionen – wie Titeln, Verkäufen und Zahlungen – in der genauen Reihenfolge, in der sie stattfinden. Öffentliche Hauptbücher dämmen nicht nur Korruption ein, sondern ermöglichen auch hochentwickelte Anwendungen – wie z Kryptowährungen und smart contracts. Sie werden die Art und Weise einer demokratischen Gesellschaft revolutionieren betreibt. In der derzeit implementierten Form sind sie jedoch schlecht skalierbar und können ihr Potenzial nicht ausschöpfen. Algorand ist eine wirklich demokratische und effiziente Möglichkeit, ein öffentliches Hauptbuch zu implementieren. Im Gegensatz zu früher Implementierungen, die auf Arbeitsnachweisen basieren, erfordern einen vernachlässigbaren Rechenaufwand und generiert einen Transaktionsverlauf, der mit überwältigend hoher Wahrscheinlichkeit nicht „verzweigt“ wird. Algorand basiert auf einer (neuen und superschnellen) byzantinischen Vereinbarung zur Nachrichtenübermittlung. Der Konkretheit halber beschreiben wir Algorand nur als Geldplattform.

Einführung

Geld wird immer virtueller. Es wurde geschätzt, dass etwa 80 % der Vereinigten Staaten Dollar existieren heute nur noch als Hauptbucheinträge [5]. Andere Finanzinstrumente ziehen nach. In einer idealen Welt, in der wir auf eine allgemein vertrauenswürdige zentrale Instanz zählen könnten, wären wir immun Um allen möglichen Cyber-Angriffen standzuhalten, könnten Geld- und andere Finanztransaktionen ausschließlich elektronisch abgewickelt werden. Leider leben wir nicht in einer solchen Welt. Dementsprechend sind dezentrale Kryptowährungen, wie z als Bitcoin [29] und „smart contract“-Systeme wie Ethereum wurden [4] vorgeschlagen. Bei Das Herzstück dieser Systeme ist ein gemeinsames Hauptbuch, das eine Abfolge von Transaktionen zuverlässig aufzeichnet. ∗Dies ist die formellere (und asynchronere) Version des ArXiv-Artikels des zweiten Autors [24], eines Artikels basiert auf dem von Gorbunov und Micali [18]. Die Technologien von Algorand sind Gegenstand des Folgenden Patentanmeldungen: 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.931so vielfältig wie Zahlungen und Verträge, und zwar auf manipulationssichere Weise. Die Technologie der Wahl Die Gewährleistung dieser Manipulationssicherheit ist blockchain. Blockchains stecken hinter Anwendungen wie Kryptowährungen [29], Finanzanwendungen [4] und das Internet der Dinge [3]. Mehrere Techniken Zur Verwaltung blockchain-basierter Ledger wurden vorgeschlagen: Proof of Work [29], Proof of Stake [2], praktische byzantinische Fehlertoleranz [8] oder eine Kombination davon. Derzeit kann die Verwaltung von Hauptbüchern jedoch ineffizient sein. Zum Beispiel proof-of-work von Bitcoin Der Ansatz (basierend auf dem ursprünglichen Konzept von [14]) erfordert einen großen Rechenaufwand und ist verschwenderisch und skaliert schlecht [1]. Darüber hinaus konzentriert es de facto die Macht in sehr wenigen Händen. Wir möchten daher eine neue Methode zur Implementierung eines öffentlichen Hauptbuchs vorschlagen, das Folgendes bietet: Bequemlichkeit und Effizienz eines zentralisierten Systems, das von einer vertrauenswürdigen und unantastbaren Autorität betrieben wird, ohne die Ineffizienzen und Schwächen aktueller dezentraler Implementierungen. Wir nennen unseren Ansatz Algorand, weil wir algorithmische Zufälligkeit verwenden, um basierend auf dem bisher erstellten Hauptbuch auszuwählen, eine Gruppe von Verifizierern, die für die Erstellung des nächsten Blocks gültiger Transaktionen verantwortlich sind. Natürlich, Wir stellen sicher, dass solche Auswahlen nachweislich vor Manipulationen geschützt und bis dahin unvorhersehbar sind in letzter Minute, sondern auch, dass sie letztendlich allgemein klar sind. Der Ansatz von Algorand ist durchaus demokratisch, weder im Prinzip noch de facto erstellt verschiedene Klassen von Benutzern (als „Miner“ und „normale Benutzer“ in Bitcoin). In Algorand „alle Die Macht liegt bei der Menge aller Benutzer.“ Eine bemerkenswerte Eigenschaft von Algorand ist, dass sein Transaktionsverlauf nur mit sehr kleinen Teilen möglich ist Wahrscheinlichkeit (z. B. eins zu einer Billion oder sogar 10−18). Algorand kann auch einige rechtliche Aspekte ansprechen und politische Bedenken. Der Algorand-Ansatz gilt für blockchains und allgemeiner für jede Generierungsmethode eine manipulationssichere Folge von Blöcken. Wir haben tatsächlich eine neue Methode vorgeschlagen – eine Alternative zu und effizienter als blockchains – das kann von unabhängigem Interesse sein. 1.1 Annahme und technische Probleme von Bitcoin Bitcoin ist ein sehr ausgeklügeltes System und hat viele weitere Forschungen inspiriert. Doch es ist auch problematisch. Fassen wir die zugrunde liegende Annahme und die technischen Probleme zusammen – welche werden tatsächlich von praktisch allen Kryptowährungen geteilt, die, wie Bitcoin, auf proof-of-work basieren. Für diese Zusammenfassung genügt es, sich daran zu erinnern, dass ein Benutzer in Bitcoin mehrere öffentliche Schlüssel besitzen kann eines digitalen Signatursystems, dass Geld mit öffentlichen Schlüsseln verknüpft ist und dass eine Zahlung eine ist Digitale Signatur, die einen Geldbetrag von einem öffentlichen Schlüssel auf einen anderen überträgt. Im Wesentlichen, Bitcoin organisiert alle verarbeiteten Zahlungen in einer Kette von Blöcken, B1, B2, . . ., jeweils bestehend aus mehreren Zahlungen, so dass alle Zahlungen von B1, in beliebiger Reihenfolge, gefolgt von denen von B2, in beliebiger Reihenfolge, usw. stellen eine Folge gültiger Zahlungen dar. Jeder Block wird im Durchschnitt alle 10 Minuten generiert. Bei dieser Abfolge von Blöcken handelt es sich um eine Kette, da sie so strukturiert ist, dass jede Änderung auch möglich ist in einem einzelnen Block, dringt in alle nachfolgenden Blöcke ein und erleichtert so das Erkennen von Änderungen die Zahlungshistorie. (Wie wir sehen werden, wird dies dadurch erreicht, dass in jeden Block ein kryptografischer Code eingefügt wird hash des vorherigen.) Eine solche Blockstruktur wird als blockchain bezeichnet. Annahme: Ehrliche Mehrheit der Rechenleistung Bitcoin geht davon aus, dass keine böswillige Absicht vorliegt Eine Entität (noch eine Koalition koordinierter böswilliger Entitäten) kontrolliert den Großteil der Rechenleistung Macht, die der Blockgenerierung gewidmet ist. Eine solche Entität wäre tatsächlich in der Lage, blockchain zu ändern,und so die Zahlungshistorie nach Belieben umschreiben. Es könnte insbesondere eine Zahlung \(\wp\) leisten, Erhalten Sie die bezahlten Leistungen und „löschen“ Sie dann jede Spur von \(\wp\). Technisches Problem 1: Rechenverschwendung Bitcoins proof-of-work-Ansatz zum Blockieren Die Generierung erfordert einen außerordentlichen Rechenaufwand. Derzeit sind es nur ein paar Hundert Tausende öffentliche Schlüssel im System können die 500 leistungsstärksten Supercomputer nur aufbringen lediglich 12,8 % der gesamten Rechenleistung, die von den Bitcoin-Spielern benötigt wird. Dies Der Rechenaufwand würde erheblich zunehmen, wenn deutlich mehr Benutzer dem System beitreten würden. Technisches Problem 2: Machtkonzentration Heute aufgrund der exorbitanten Menge an Berechnung erforderlich, ein Benutzer, der versucht, einen neuen Block mithilfe eines normalen Desktops zu generieren (geschweige denn a Handy), rechnet damit, Geld zu verlieren. Um einen neuen Block mit einem gewöhnlichen Computer zu berechnen, Die erwarteten Kosten für den für die Berechnung erforderlichen Strom übersteigen die erwartete Belohnung. Nur die Verwendung von Pools speziell gebauter Computer (die nichts anderes tun als „neue Blöcke abbauen“), einer könnte erwarten, durch die Generierung neuer Blöcke einen Gewinn zu erzielen. Dementsprechend sind es heute de facto zwei disjunkte Benutzerklassen: normale Benutzer, die nur Zahlungen leisten, und spezialisierte Mining-Pools, die nur nach neuen Blöcken suchen. Es sollte daher nicht überraschen, dass seit kurzem die gesamte Rechenleistung für Block Generation liegt in nur fünf Pools. Unter solchen Bedingungen ist die Annahme, dass eine Mehrheit der Rechenleistung ist ehrlich, wird weniger glaubwürdig. Technisches Problem 3: Mehrdeutigkeit In Bitcoin ist blockchain nicht unbedingt eindeutig. Tatsächlich sein letzter Teil verzweigt sich oft: Der blockchain kann – sagen wir – B1 sein, . . . , Bk, B′ k+1, B′ k+2, gem ein Benutzer und B1, . . . , Bk, B'' k+1, B'' k+2, B'' k+3 laut einem anderen Benutzer. Erst nach mehreren Blöcken Kann man einigermaßen sicher sein, dass die ersten k + 3 Blöcke gleich sind, wenn sie zur Kette hinzugefügt wurden? für alle Benutzer. Daher kann man sich nicht sofort auf die im letzten Block enthaltenen Zahlungen verlassen die Kette. Es ist sinnvoller abzuwarten und zu sehen, ob der Block ausreichend tief im Inneren sitzt blockchain und somit ausreichend stabil. Unabhängig davon wurden auch Bedenken hinsichtlich der Strafverfolgung und der Geldpolitik in Bezug auf Bitcoin.1 geäußert 1.2 Algorand, kurz und bündig Einstellung Algorand arbeitet in einer sehr schwierigen Umgebung. Kurz gesagt, (a) Erlaubnisfreie und erlaubte Umgebungen. Algorand funktioniert effizient und sicher in einer völlig erlaubnisfreien Umgebung, in der beliebig viele Benutzer dem beitreten dürfen System jederzeit und ohne jegliche Überprüfung oder Erlaubnis jeglicher Art zu öffnen. Natürlich funktioniert Algorand noch besser in einer zugelassenen Umgebung. 1Die durch Bitcoin-Zahlungen gebotene (Pseudo-)Anonymität kann zur Geldwäsche und/oder Finanzierung missbraucht werden von kriminellen Personen oder terroristischen Organisationen. Traditionelle Banknoten oder Goldbarren, die im Prinzip perfekt sind Anonymität sollte die gleiche Herausforderung darstellen, aber die Physizität dieser Währungen verlangsamt das Geld erheblich Übermittlungen, um ein gewisses Maß an Überwachung durch Strafverfolgungsbehörden zu ermöglichen. Die Fähigkeit, „Geld zu drucken“, ist eine der grundlegendsten Befugnisse eines Nationalstaats. Im Prinzip also das Massive Die Einführung einer unabhängig schwankenden Währung könnte diese Macht einschränken. Derzeit ist Bitcoin jedoch noch lange nicht da Es stellt eine Bedrohung für die staatliche Geldpolitik dar und wird es aufgrund seiner Skalierbarkeitsprobleme möglicherweise nie sein.(b) Sehr kontroverse Umgebungen. Algorand widersteht einem sehr mächtigen Gegner, der es kann (1) jeden Benutzer, den er möchte, zu jeder Zeit, die er möchte, sofort korrumpieren, vorausgesetzt, dass in a In einer erlaubnisfreien Umgebung gehören zwei Drittel des Geldes im System ehrlichen Benutzern. (In einem (In einer genehmigten Umgebung, unabhängig vom Geld, reicht es aus, dass 2/3 der Benutzer ehrlich sind.) (2) vollständige Kontrolle und perfekte Koordinierung aller beschädigten Benutzer; und (3) Planen Sie die Zustellung aller Nachrichten, vorausgesetzt, dass jede Nachricht von einem ehrlichen Benutzer gesendet wird erreicht 95 % der ehrlichen Nutzer innerhalb einer Zeit \(\lambda\)m, die allein von der Größe von m abhängt. Haupteigenschaften Trotz der Anwesenheit unseres mächtigen Gegners in Algorand • Der Rechenaufwand ist minimal. Im Wesentlichen egal, wie viele Benutzer es gibt Im System vorhanden, muss jeder der fünfzehnhundert Benutzer höchstens einige Sekunden ausführen Berechnung. • Ein neuer Block wird in weniger als 10 Minuten generiert und verlässt de facto nie den blockchain. Beispielsweise ist zu erwarten, dass die Zeit zum Generieren eines Blocks in der ersten Ausführungsform kürzer ist als Λ + 12,4\(\lambda\), wobei Λ die Zeit ist, die erforderlich ist, um einen Block in einem Peer-to-Peer-Klatsch zu verbreiten Mode, egal welche Blockgröße man wählt, und \(\lambda\) ist die Zeit, um 1.500 200B lange Nachrichten zu verbreiten. (Da in einem wirklich dezentralisierten System Λ im Wesentlichen eine intrinsische Latenz ist, in Algorand Der begrenzende Faktor bei der Blockgenerierung ist die Netzwerkgeschwindigkeit.) Die zweite Ausführungsform hat tatsächlich experimentell getestet (von?), was darauf hindeutet, dass ein Block in weniger als 40 generiert wird Sekunden. Darüber hinaus darf blockchain von Algorand nur mit vernachlässigbarer Wahrscheinlichkeit (d. h. weniger als eins) gegabelt werden in einer Billion), und so können Benutzer die in einem neuen Block enthaltenen Zahlungen weiterleiten, sobald die Block erscheint. • Die gesamte Macht liegt bei den Benutzern selbst. Algorand ist ein wirklich verteiltes System. Insbesondere Es gibt keine exogenen Einheiten (wie die „Miner“ in Bitcoin), die welche Transaktionen kontrollieren können werden anerkannt. Algorands Techniken. 1. Ein neues und schnelles Byzantinisches Abkommensprotokoll. Algorand generiert einen neuen Block über ein neues kryptografisches, nachrichtenweitergebendes, binäres Byzantine Agreement (BA)-Protokoll, BA⋆. Protokoll BA⋆erfüllt nicht nur einige zusätzliche Eigenschaften (auf die wir gleich noch eingehen werden), sondern ist auch sehr schnell. Grob gesagt besteht die Version mit Binäreingabe aus einer dreistufigen Schleife, in der ein Spieler eine Single sendet Nachricht mi an alle anderen Spieler. Ausgeführt in einem vollständigen und synchronen Netzwerk, mit mehr Wenn mehr als 2/3 der Spieler ehrlich sind, mit einer Wahrscheinlichkeit von > 1/3, endet das Protokoll nach jeder Schleife Vereinbarung. (Wir betonen, dass das Protokoll BA⋆der ursprünglichen Definition der byzantinischen Vereinbarung entspricht von Pease, Shostak und Lamport [31], ohne Abschwächungen.) Algorand nutzt dieses binäre BA-Protokoll, um in unserer unterschiedlichen Kommunikation eine Einigung zu erzielen Modell, auf jedem neuen Block. Der vereinbarte Block wird dann über eine vorgeschriebene Anzahl zertifiziert Digitale Signatur der entsprechenden Prüfer erstellt und über das Netzwerk verbreitet. 2. Kryptografische Sortierung. Obwohl es sehr schnell ist, würde das Protokoll BA⋆ von weiteren Vorteilen profitieren Geschwindigkeit, wenn sie von Millionen von Benutzern gespielt wird. Dementsprechend wählt Algorand die künftigen Spieler von BA⋆ auseine viel kleinere Teilmenge der Menge aller Benutzer. Um eine andere Art von Machtkonzentration zu vermeiden Problem, jeder neue Block Br wird durch eine neue Ausführung von BA⋆ konstruiert und vereinbart, durch einen separaten Satz ausgewählter Prüfer, SV r. Im Prinzip kann die Auswahl eines solchen Sets genauso schwierig sein wie Br direkt auswählen. Wir begegnen diesem potenziellen Problem mit einem Ansatz, den wir „umfassend“ nennen der aufschlussreiche Vorschlag von Maurice Herlihy, kryptografische Sortierung. Sortierung ist die Praxis von Auswahl von Beamten nach dem Zufallsprinzip aus einer großen Gruppe berechtigter Personen [6]. (Sortierung wurde geübt über Jahrhunderte hinweg: zum Beispiel durch die Republiken Athen, Florenz und Venedig. In der modernen Justiz Systeme werden bei der Auswahl der Jurys häufig Zufallsauswahlverfahren eingesetzt. In letzter Zeit gibt es auch Zufallsstichproben für Wahlen befürwortet von David Chaum [9].) In einem dezentralen System natürlich die Wahl der Es ist problematisch, zufällige Münzen zu verwenden, um die Mitglieder jedes Verifizierersatzes SV r zufällig auszuwählen. Wir greifen daher auf Kryptographie zurück, um jeden Verifizierersatz aus der Population aller Benutzer auszuwählen. auf eine Weise, die garantiert automatisch (d. h. ohne Nachrichtenaustausch) und zufällig erfolgt. Im Wesentlichen verwenden wir eine kryptografische Funktion, um den vorherigen Block automatisch zu ermitteln Br−1, ein Benutzer, der Leiter, der dafür verantwortlich ist, den neuen Block Br vorzuschlagen, und der Verifizierer SV r, in Aufgabe ist es, eine Einigung über den vom Vorsitzenden vorgeschlagenen Block zu erzielen. Da böswillige Benutzer Einfluss nehmen können Die Zusammensetzung von Br−1 (z. B. durch Auswahl einiger seiner Zahlungen) konstruieren und verwenden wir speziell Zusätzliche Eingaben, um zu beweisen, dass der Anführer für den r-ten Block und der Verifizierersatz SV r tatsächlich vorhanden sind zufällig ausgewählt. 3. Die Menge (Samen) Qr. Wir verwenden dazu den letzten Block Br−1 im blockchain Bestimmen Sie automatisch den nächsten Verifizierersatz und den Leiter, der für den Aufbau des neuen Blocks verantwortlich ist Br. Die Herausforderung bei diesem Ansatz besteht darin, dass durch die einfache Auswahl einer etwas anderen Zahlung im In der letzten Runde erlangt unser mächtiger Gegner eine enorme Kontrolle über den nächsten Anführer. Auch wenn er Obwohl er nur 1/1000 der Spieler/Gelder im System kontrollierte, konnte er sicherstellen, dass alle Anführer dies tun bösartig. (Siehe Abschnitt 4.1 zur Intuition.) Diese Herausforderung ist für alle proof-of-stake-Ansätze von zentraler Bedeutung. und nach unserem besten Wissen wurde es bis jetzt noch nicht zufriedenstellend gelöst. Um dieser Herausforderung gerecht zu werden, bauen wir gezielt und sorgfältig ein separates und kontinuierlich aktualisiertes System auf definierte Größe Qr, die nachweislich nicht nur unvorhersehbar, sondern auch nicht beeinflussbar ist mächtiger Gegner. Wir können Qr als den r-ten Samen bezeichnen, da Algorand von Qr auswählt, Über eine geheime kryptografische Sortierung werden alle Benutzer, die bei der Generierung eine besondere Rolle spielen, ermittelt rter Block. 4. Geheime krytografische Sortierung und geheime Anmeldeinformationen. Zufällige und eindeutige Verwendung des aktuellen letzten Blocks, Br−1, um den Verifizierersatz und den verantwortlichen Leiter auszuwählen Der Bau des neuen Blocks Br reicht nicht aus. Da Br−1 bekannt sein muss, bevor Br erzeugt wird, Auch die letzte in Br−1 enthaltene, nicht beeinflussbare Größe Qr−1 muss bekannt sein. Dementsprechend also sind die Verifizierer und der Leiter, der für die Berechnung des Blocks Br verantwortlich ist. Also unser mächtiger Gegner könnte sie alle sofort korrumpieren, bevor sie sich auf eine Diskussion über Br einlassen, um zu bekommen volle Kontrolle über den von ihnen zertifizierten Block. Um diesem Problem vorzubeugen, erfahren Führungskräfte (und eigentlich auch Prüfer) heimlich von ihrer Rolle, können es aber Berechnen Sie einen ordnungsgemäßen Berechtigungsnachweis, der in der Lage ist, jedem nachzuweisen, der diese Rolle tatsächlich innehat. Wann Ein Benutzer erkennt privat, dass er der Anführer für den nächsten Block ist, und baut zunächst heimlich seinen Block zusammen Er erstellt einen eigenen vorgeschlagenen neuen Block und verbreitet ihn dann zusammen mit seinem eigenen (damit er zertifiziert werden kann). Berechtigung. Auf diese Weise erkennt der Gegner jedoch sofort, wer der Anführer des nächsten ist Block ist, und obwohl er ihn sofort korrumpieren kann, wird es für den Gegner zu spät sein Einfluss auf die Wahl eines neuen Blocks haben. Tatsächlich kann er die Botschaft des Anführers nicht mehr „zurückrufen“.als eine mächtige Regierung eine von WikiLeaks viral verbreitete Botschaft zurück in die Flasche stecken kann. Wie wir sehen werden, können wir weder die Einzigartigkeit eines Anführers garantieren, noch dafür, dass jeder sicher ist, wer der Anführer ist ist, einschließlich des Anführers selbst! Aber in Algorand ist ein eindeutiger Fortschritt garantiert. 5. Spieleraustauschbarkeit. Nachdem er einen neuen Block vorgeschlagen hat, könnte der Anführer genauso gut „sterben“ (oder sterben). vom Gegner korrumpiert), weil seine Arbeit erledigt ist. Für die Verifizierer in SV r sind die Dinge jedoch weniger einfach. Da ich für die Beglaubigung des neuen Blocks Br mit ausreichend vielen Unterschriften verantwortlich bin, Sie müssen zunächst eine byzantinische Einigung über den vom Führer vorgeschlagenen Block herbeiführen. Das Problem ist, dass Egal wie effizient es ist, BA⋆erfordert mehrere Schritte und die Ehrlichkeit von > 2/3 seiner Spieler. Dies stellt ein Problem dar, da die Spielermenge von BA⋆aus Effizienzgründen aus der kleinen Menge SV r besteht wird zufällig aus der Menge aller Benutzer ausgewählt. So ist unser mächtiger Gegner zwar unfähig korrupt 1/3 aller Benutzer, kann sicherlich alle Mitglieder von SV r korrumpieren! Glücklicherweise werden wir beweisen, dass das Protokoll BA⋆, das durch die Verbreitung von Nachrichten auf Peer-to-Peer-Art ausgeführt wird, vom Spieler austauschbar ist. Diese neuartige Anforderung bedeutet, dass das Protokoll korrekt und korrekt ist erreicht effizient einen Konsens, auch wenn jeder seiner Schritte völlig neu und zufällig ausgeführt wird und unabhängig ausgewählter Satz von Spielern. Somit gibt es bei Millionen von Benutzern jeweils eine kleine Gruppe von Spielern einem Schritt von BA⋆ zugeordnet, hat höchstwahrscheinlich einen leeren Schnittpunkt mit der nächsten Menge. Darüber hinaus werden die Spielermengen verschiedener Schritte von BA⋆ wahrscheinlich völlig unterschiedlich sein Kardinalitäten. Darüber hinaus wissen die Mitglieder jeder Gruppe nicht, wer die nächste Spielergruppe sein wird sein und keinen inneren Zustand heimlich passieren. Die Eigenschaft des austauschbaren Spielers ist tatsächlich entscheidend, um den dynamischen und sehr mächtigen Spieler zu besiegen Gegner, den wir uns vorstellen. Wir glauben, dass sich Protokolle mit austauschbaren Playern in vielen Fällen als entscheidend erweisen werden Kontexte und Anwendungen. Sie werden insbesondere für die sichere Ausführung kleiner Unterprotokolle von entscheidender Bedeutung sein Eingebettet in ein größeres Spieleruniversum mit einem dynamischen Gegner, der selbst korrumpieren kann Ein kleiner Bruchteil der Gesamtzahl der Spieler hat keine Schwierigkeiten, alle Spieler in den kleineren zu korrumpieren Unterprotokoll. Eine zusätzliche Eigenschaft/Technik: Faule Ehrlichkeit Ein ehrlicher Benutzer befolgt seine Vorschriften Anweisungen, zu denen auch gehört, online zu sein und das Protokoll auszuführen. Seitdem ist Algorand nur bescheiden Rechen- und Kommunikationsanforderungen, Online-Sein und Ausführung des Protokolls „im Hintergrund“ ist kein großes Opfer. Natürlich gibt es auch ein paar „Abwesenheiten“ unter ehrlichen Spielern, wie z aufgrund eines plötzlichen Verbindungsverlusts oder der Notwendigkeit eines Neustarts werden automatisch toleriert (weil Wir können so wenige Spieler immer als vorübergehend böswillig betrachten. Wir weisen jedoch darauf hin, dass Algorand einfach angepasst werden kann, um in einem neuen Modell zu funktionieren, in dem ehrliche Benutzer vorhanden sind Die meiste Zeit offline. Unser neues Modell kann wie folgt informell vorgestellt werden. Faule Ehrlichkeit. Grob gesagt ist ein Benutzer faul, aber ehrlich, wenn er (1) alle seine Vorschriften befolgt Anweisungen, wenn er zur Teilnahme am Protokoll aufgefordert wird, und (2) er zur Teilnahme aufgefordert wird nur selten und mit entsprechender Vorankündigung auf das Protokoll eingehen. Mit einer so entspannten Vorstellung von Ehrlichkeit sind wir möglicherweise noch zuversichtlicher, dass ehrliche Menschen es sein werden zur Hand, wenn wir sie brauchen, und Algorand garantieren, dass, wenn dies der Fall ist, Das System arbeitet auch dann sicher, wenn zu einem bestimmten Zeitpunkt Die Mehrheit der teilnehmenden Spieler ist böswillig.1.3 Eng verwandte Arbeit Proof-of-Work-Ansätze (wie die zitierten [29] und [4]) sind ziemlich orthogonal zu unserem. So sind die Ansätze, die auf byzantinischer Vereinbarung zur Nachrichtenübermittlung oder praktischer byzantinischer Fehlertoleranz basieren (wie das zitierte [8]). Tatsächlich können diese Protokolle nicht von allen Benutzern ausgeführt werden und können auch nicht in unserem Modell auf eine entsprechend kleine Gruppe von Benutzern beschränkt sein. Tatsächlich ist unser mächtiger Gegner mein beschädigt sofort alle beteiligten Benutzer einer kleinen Gruppe, die tatsächlich ein BA-Protokoll ausführen soll. Unser Ansatz könnte als mit dem Proof of Stake [2] verknüpft betrachtet werden, in dem Sinne, dass die „Macht“ der Benutzer beim Blockaufbau ist proportional zu dem Geld, das sie im System besitzen (im Gegensatz zu – sagen wir – zu das Geld, das sie in ein „Treuhandkonto“ eingezahlt haben). Das Papier, das unserem am nächsten kommt, ist das Sleepy Consensus Model von Pass und Shi [30]. Um das zu vermeiden Der proof-of-work-Ansatz erfordert umfangreiche Berechnungen, auf die sich ihr Artikel (und freundlicherweise) stützt Credits) Algorands geheime kryptografische Sortierung. Mit diesem entscheidenden Aspekt haben mehrere gemeinsam Es bestehen erhebliche Unterschiede zwischen unseren Papieren. Insbesondere (1) Ihre Einstellung ist nur erlaubt. Im Gegensatz dazu ist Algorand auch ein erlaubnisloses System. (2) Sie verwenden ein Protokoll im Nakamoto-Stil, weshalb ihre blockchain häufig gegabelt werden. Obwohl Unter Verzicht auf proof-of-work wird in ihrem Protokoll ein heimlich ausgewählter Anführer gebeten, das zu verlängern längste gültige (in einem umfassenderen Sinne) blockchain. Gabelungen sind daher unvermeidlich und man muss darauf warten Der Block ist ausreichend „tief“ in der Kette. Tatsächlich, um ihre Ziele mit einem Gegner zu erreichen Da sie zu adaptiven Verfälschungen fähig sind, erfordern sie, dass ein Block poly(N) tief ist, wobei N das darstellt Gesamtzahl der Benutzer im System. Beachten Sie das, selbst wenn man davon ausgeht, dass ein Block erzeugt werden könnte Wenn es in einer Minute N = 1 Mio. Benutzer gäbe, müsste man etwa 2 Mio. Jahre darauf warten dass ein Block N-tief wird, und etwa zwei Jahre lang, bis ein Block N-tief wird. Im Gegensatz dazu Algorands blockchain gabelt sich nur mit vernachlässigbarer Wahrscheinlichkeit, auch wenn der Gegner korrupt ist Benutzer können sich sofort und anpassungsfähig an die neuen Blöcke wenden, auf die man sich sofort verlassen kann. (3) Sie behandeln keine einzelnen byzantinischen Verträge. In gewissem Sinne garantieren sie nur „letzterer Konsens über eine wachsende Reihe von Werten“. Es handelt sich vielmehr um ein Zustandsreplikationsprotokoll als ein BA-Wert und kann nicht verwendet werden, um eine byzantinische Einigung über einen individuellen Interessenwert zu erzielen. Im Gegensatz dazu kann Algorand bei Bedarf auch nur einmal verwendet werden, um Millionen von Benutzern schnell zu ermöglichen byzantinische Einigung über einen bestimmten Zinswert erzielen. (4) Sie erfordern schwach synchronisierte Uhren. Das heißt, die Uhren aller Benutzer sind um eine kleine Zeit verschoben δ. Im Gegensatz dazu müssen Uhren in Algorand nur (im Wesentlichen) die gleiche „Geschwindigkeit“ haben. (5) Ihr Protokoll funktioniert mit faulen, aber ehrlichen Benutzern oder mit der ehrlichen Mehrheit der Online-Benutzer. Sie danken Algorand dafür, dass er das Problem angesprochen hat, dass ehrliche Benutzer massenhaft offline gehen, und zwar dafür Als Antwort darauf wurde das Modell der faulen Ehrlichkeit vorgeschlagen. Ihr Protokoll funktioniert nicht nur bei Faulenzern Ehrlichkeitsmodell, aber auch in ihrem kontradiktorischen Sleepy-Modell, bei dem ein Gegner auswählt, welche Benutzer online sind und die offline sind, vorausgesetzt, dass die Mehrheit der Online-Nutzer jederzeit ehrlich ist.2 2Die ursprüngliche Version ihres Artikels betrachtete in ihrem kontradiktorischen, schläfrigen Modell tatsächlich nur Sicherheit. Die Die ursprüngliche Version von Algorand, die ihrer Vorgängerversion vorausgeht, sah auch ausdrücklich die Annahme vor, dass eine bestimmte Mehrheit der Online-Spieler sind immer ehrlich, haben dies jedoch zugunsten des Modells der faulen Ehrlichkeit ausdrücklich von der Betrachtung ausgeschlossen. (Wenn sich zum Beispiel irgendwann die Hälfte der ehrlichen Benutzer dafür entscheidet, offline zu gehen, dann die Mehrheit der Benutzer online kann sehr wohl bösartig sein. Um dies zu verhindern, sollte der Gegner die meisten seiner Kräfte erzwingen (Er hat auch korrupte Spieler dazu gebracht, offline zu gehen, was eindeutig seinem eigenen Interesse zuwiderläuft.) Beachten Sie, dass es sich um ein Protokoll mit einer Mehrheit handelt von faulen, aber ehrlichen Spielern funktioniert gut, wenn die Mehrheit der Online-Benutzer immer böswillig ist. Das ist so, weil Eine ausreichende Anzahl ehrlicher Spieler, die wissen, dass sie zu einem seltenen Zeitpunkt von entscheidender Bedeutung sein werden, werden wählen In diesen Momenten nicht offline zu gehen, noch kann der Gegner sie dazu zwingen, offline zu gehen, da er nicht weiß, wer das ist Entscheidend könnten ehrliche Spieler sein.(6) Sie erfordern eine einfache ehrliche Mehrheit. Im Gegensatz dazu erfordert die aktuelle Version von Algorand eine 2/3 ehrliche Mehrheit. Ein weiteres Papier in unserer Nähe ist Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol, von Kiayias, Russell, David und Oliynykov [20]. Auch ihr System erschien nach unserem. Es auch nutzt kryptografische Sortierung, um auf nachweisbare Weise auf einen Arbeitsnachweis zu verzichten. Allerdings sind ihre Das System ist wiederum ein Protokoll im Nakamoto-Stil, bei dem Gabelungen sowohl unvermeidbar als auch häufig sind. (In ihrem Modell müssen die Blöcke jedoch nicht so tief sein wie im Sleepy-Consensus-Modell.) Darüber hinaus Ihr System basiert auf den folgenden Annahmen: In den Worten der Autoren selbst: „(1) die Das Netzwerk ist hochgradig synchron, (2) die Mehrheit der ausgewählten Stakeholder ist bei Bedarf verfügbar an jeder Epoche teilzunehmen, (3) die Stakeholder bleiben nicht für längere Zeit offline, (4) Die Adaptivität von Verfälschungen unterliegt einer kleinen Verzögerung, die in Runden linear gemessen wird der Sicherheitsparameter.“ Im Gegensatz dazu ist Algorand mit überwältigender Wahrscheinlichkeit forkfrei und stützt sich auf keine dieser vier Annahmen. Insbesondere in Algorand ist der Gegner dazu in der Lage die Benutzer, die er kontrollieren möchte, sofort korrumpieren.

Grundlagen

2.1 Kryptografische Primitive Ideales Hashing. Wir werden uns auf eine effizient berechenbare kryptografische hash-Funktion H verlassen, die ordnet beliebig lange Strings binären Strings fester Länge zu. Wir modeln einer langen Tradition folgend H als zufälliges oracle, im Wesentlichen eine Funktion, die jede mögliche Zeichenfolge s einem zufälligen und zuordnet unabhängig ausgewählte (und dann festgelegte) Binärzeichenfolge H(s) der gewählten Länge. In diesem Artikel hat H 256 Bit lange Ausgänge. Tatsächlich ist diese Länge kurz genug, um dies zu ermöglichen systemeffizient und lang genug, um das System sicher zu machen. Wir wollen zum Beispiel, dass H kollisionsresistent ist. Das heißt, es sollte schwierig sein, zwei verschiedene Zeichenfolgen x und y zu finden, sodass H(x) = H(y). Wenn H ein zufälliger oracle mit 256 Bit langen Ausgaben ist, ist das Finden eines solchen Zeichenfolgenpaars tatsächlich möglich schwierig. (Bei einem zufälligen Versuch und unter Berufung auf das Geburtstagsparadoxon wäre 2256/2 = 2128 erforderlich Versuche.) Digitales Signieren. Mithilfe digitaler Signaturen können Benutzer Informationen untereinander authentifizieren ohne irgendwelche geheimen Schlüssel weiterzugeben. Ein digitales Signaturschema besteht aus drei schnellen Algorithmen: ein probabilistischer Schlüsselgenerator G, ein Signierungsalgorithmus S und ein Verifizierungsalgorithmus V. Bei einem Sicherheitsparameter k, einer ausreichend hohen Ganzzahl, verwendet ein Benutzer i G, um ein Paar zu erzeugen k-Bit-Schlüssel (d. h. Zeichenfolgen): ein „öffentlicher“ Schlüssel PKI und ein passender „geheimer“ Signaturschlüssel Ski. Entscheidend ist, a Der öffentliche Schlüssel „verrät“ seinen entsprechenden geheimen Schlüssel nicht. Das heißt, selbst wenn man Kenntnisse über PKI hat, nein Jemand anderes als ich ist in der Lage, Ski in weniger als astronomischer Zeit zu berechnen. Benutzer i nutzt Ski, um Nachrichten digital zu signieren. Für jede mögliche Nachricht (Binärzeichenfolge) m, i zuerst hashes m und führt dann den Algorithmus S auf den Eingängen H(m) und Ski aus, um die k-Bit-Zeichenfolge zu erzeugen sigpki(m) \(\triangleq\)S(H(m), ski) .3 3Da H kollisionsresistent ist, ist es praktisch unmöglich, dass man durch das Signieren von m versehentlich etwas anderes „signiert“. Nachricht m′.Die Binärzeichenfolge sigpki(m) wird als digitale Signatur von m (relativ zu pki) von i bezeichnet und kann es sein einfacher mit sigi(m) bezeichnet, wenn der öffentliche Schlüssel pki aus dem Kontext klar hervorgeht. Jeder, der pki kennt, kann damit die von i erstellten digitalen Signaturen überprüfen. Konkret: auf gibt (a) den öffentlichen Schlüssel pki eines Spielers i, (b) eine Nachricht m und (c) eine Zeichenfolge s ein, d. h. i ist angeblich Wenn die digitale Signatur der Nachricht m vorliegt, gibt der Verifizierungsalgorithmus V entweder JA oder NEIN aus. Die Eigenschaften, die wir von einem digitalen Signaturschema benötigen, sind: 1. Legitime Signaturen werden immer verifiziert: Wenn s = sigi(m), dann V (pki, m, s) = Y ES; und 2. Digitale Signaturen sind schwer zu fälschen: Ohne Wissen über die Zeit, um eine solche Zeichenfolge zu finden dass V (pki, m, s) = Y ES für eine Nachricht m, die nie von i signiert wurde, astronomisch lang ist. (Aufgrund der strengen Sicherheitsanforderungen von Goldwasser, Micali und Rivest [17] ist dies wahr selbst wenn man die Signatur einer anderen Nachricht erhalten kann.) Um zu verhindern, dass jemand anderes Nachrichten in seinem Namen signiert, muss ein Spieler seinen behalten Der Signaturschlüssel ist geheim (daher der Begriff „geheimer Schlüssel“) und ermöglicht es jedem, die Nachrichten zu überprüfen Er unterschreibt, ich habe ein Interesse daran, seinen Schlüssel-PKI zu veröffentlichen (daher der Begriff „öffentlicher Schlüssel“). Im Allgemeinen ist eine Nachricht m nicht aus ihrer Signatur sigi(m) abrufbar. Um virtuell zu handeln mit digitalen Signaturen, die die konzeptionell praktische Eigenschaft „Abrufbarkeit“ erfüllen (d. h. zu garantieren, dass der Unterzeichner und die Nachricht aus einer Signatur leicht errechenbar sind, definieren wir SIGpki(m) = (i, m, sigpki(m)) und SIGi(m) = (i, m, sigi(m)), wenn pki klar ist. Einzigartiges digitales Signieren. Wir berücksichtigen auch digitale Signaturschemata (G, S, V), die die Anforderungen erfüllen folgende zusätzliche Eigenschaft. 3. Einzigartigkeit. Es ist schwierig, solche Zeichenfolgen pk′, m, s und s′ zu finden s ̸= s′ und V (pk′, m, s) = V (pk′, m, s′) = 1. (Beachten Sie, dass die Eindeutigkeitseigenschaft auch für Zeichenfolgen pk′ gilt, die nicht legitim generiert wurden öffentliche Schlüssel. Insbesondere impliziert die Einzigartigkeitseigenschaft jedoch, dass, wenn man die verwendet spezifizierter Schlüsselgenerator G, um einen öffentlichen Schlüssel pk zusammen mit einem passenden geheimen Schlüssel sk zu berechnen, Und so wusste Sk, dass es auch für ihn im Grunde unmöglich sein würde, zwei verschiedene digitale zu finden Signaturen derselben Nachricht relativ zu pk.) Bemerkungen • Von eindeutigen Signaturen bis hin zu überprüfbaren Zufallsfunktionen. Relativ zu einem digitalen Signaturschema mit der Eindeutigkeitseigenschaft, dem die Zuordnung m \(\to\) H(sigi(m)) zugeordnet ist jede mögliche Zeichenfolge m, eine eindeutige, zufällig ausgewählte 256-Bit-Zeichenfolge, und deren Richtigkeit Die Zuordnung kann anhand der Signatur sigi(m) nachgewiesen werden. Das heißt, ein ideales hashing- und digitales Signaturschema, das die Eindeutigkeitseigenschaft im Wesentlichen erfüllt stellen eine elementare Implementierung einer überprüfbaren Zufallsfunktion bereit, wie sie eingeführt wurde und von Micali, Rabin und Vadhan [27]. (Ihre ursprüngliche Implementierung war zwangsläufig komplexer, da sie sich nicht auf ideale hashing verlassen haben.)• Drei unterschiedliche Anforderungen an digitale Signaturen. In Algorand verlässt sich ein Benutzer auf digital Unterschriften für (1) Authentifizierung meiner eigenen Zahlungen. In dieser Anwendung können Schlüssel „langfristig“ (d. h. gewohnt) sein signieren viele Nachrichten über einen langen Zeitraum) und stammen aus einem gewöhnlichen Signaturschema. (2) Generieren von Anmeldeinformationen, die beweisen, dass i berechtigt ist, bei einigen Schritten einer Runde r zu handeln. Hier, Schlüssel können langfristig sein, müssen aber aus einem Schema stammen, das die Eindeutigkeitseigenschaft erfüllt. (3) Authentifizieren der Nachricht, die ich in jedem Schritt sendet, in dem er handelt. Hier müssen Schlüssel sein ephemer (d. h. nach der ersten Verwendung zerstört), können aber aus einem gewöhnlichen Signaturschema stammen. • Eine Vereinfachung mit geringem Aufwand. Der Einfachheit halber stellen wir uns vor, dass jeder Benutzer einen einzigen Langzeitschlüssel hat. Dementsprechend muss ein solcher Schlüssel aus einem Signaturschema mit Eindeutigkeit stammen Eigentum. Eine solche Einfachheit hat einen geringen Rechenaufwand. Normalerweise tatsächlich einzigartig digital Die Erstellung und Überprüfung von Signaturen ist etwas teurer als bei gewöhnlichen Signaturen. 2.2 Das idealisierte öffentliche Hauptbuch Algorand versucht, das folgende Zahlungssystem nachzuahmen, basierend auf einem idealisierten öffentlichen Hauptbuch. 1. Der Anfangsstatus. Geld ist mit einzelnen öffentlichen Schlüsseln verknüpft (privat generierte und Eigentum der Benutzer). Lassen Sie pk1, . . . , pkj seien die anfänglichen öffentlichen Schlüssel und a1, . . . , aj ihre jeweiligen Anfangsbeträge an Geldeinheiten, dann ist der Anfangsstatus S0 = (pk1, a1), . . . , (pkj, aj) , von dem angenommen wird, dass es im System allgemein bekannt ist. 2. Zahlungen. Sei pk ein öffentlicher Schlüssel, der derzeit \(\geq\)0 Geldeinheiten hat, und pk′ ein anderer öffentlicher Schlüssel Schlüssel und a′ eine nicht negative Zahl, die nicht größer als a ist. Dann ist eine (gültige) Zahlung \(\wp\)eine digitale Unterschrift, bezogen auf PK, die zusammen die Übertragung von a′-Geldeinheiten von PK auf PK′ angibt mit einigen Zusatzinformationen. In Symbolen, \(\wp\)= SIGpk(pk, pk′, a′, I, H(I)), Dabei steht „I“ für alle zusätzlichen Informationen, die als nützlich, aber nicht sensibel erachtet werden (z. B. Zeit). Informationen und eine Zahlungskennung) und ich alle zusätzlichen Informationen, die als vertraulich gelten (z. B. der Grund der Zahlung, möglicherweise die Identität der Eigentümer von pk und pk′ usw.). Wir bezeichnen pk (oder seinen Besitzer) als Zahler, jeden pk′ (oder seinen Besitzer) als Zahlungsempfänger und a′ als die Höhe der Zahlung \(\wp\). Kostenloser Beitritt über Zahlungen. Beachten Sie, dass Benutzer jederzeit dem System beitreten können Generieren ihrer eigenen öffentlichen/geheimen Schlüsselpaare. Dementsprechend ist der öffentliche Schlüssel pk′, der in erscheint Bei der oben genannten Zahlung kann es sich um einen neu generierten öffentlichen Schlüssel handeln, der noch nie Geld „besessen“ hat vor. 3. Das magische Hauptbuch. Im Idealized System sind alle Zahlungen gültig und manipulationssicher Liste L der Zahlungssätze, die „am Himmel veröffentlicht“ sind, damit jeder sie sehen kann: L = 1 ZAHLEN, 2 ZAHLEN, . . . ,Jeder Block PAY r+1 besteht aus der Menge aller Zahlungen, die seit dem Erscheinen des Blocks getätigt wurden ZAHLEN r. Im idealen System erscheint ein neuer Block nach einer festen (oder endlichen) Zeitspanne. Diskussion. • Allgemeinere Zahlungen und nicht ausgegebene Transaktionsausgabe. Allgemeiner gesagt, wenn es sich um einen öffentlichen Schlüssel handelt Besitzt pk einen Betrag a, so darf eine gültige Zahlung \(\wp\)von pk die Beträge a′ übertragen 1, ein‘ 2, . . ., jeweils zu den Tasten pk′ 1, Pk′ 2, . . ., solange P j a′ j \(\leq\)a. In Bitcoin und ähnlichen Systemen wird das Geld, das einem öffentlichen Schlüssel gehört, getrennt aufgeteilt Beträge und eine Zahlung \(\wp\)der pk müssen einen solchen abgesonderten Betrag in voller Höhe überweisen. Wenn pk nur einen Bruchteil a′ < a von a auf einen anderen Schlüssel übertragen möchte, muss er auch den übertragen Balance, die nicht ausgegebene Transaktionsausgabe, an einen anderen Schlüssel, möglicherweise pk selbst. Algorand funktioniert auch mit Schlüsseln mit getrennten Beträgen. Um sich jedoch auf die zu konzentrieren Aufgrund der neuen Aspekte von Algorand ist es konzeptionell einfacher, bei unseren einfacheren Zahlungsformen zu bleiben und Schlüssel, denen ein einzelner Betrag zugeordnet ist. • Aktueller Status. Das Idealisierte Schema liefert keine direkten Informationen über den Strom Status des Systems (d. h. ungefähr, wie viele Geldeinheiten jeder öffentliche Schlüssel hat). Diese Informationen ist aus dem Magic Ledger ableitbar. Im idealen System speichert und aktualisiert ein aktiver Benutzer kontinuierlich die neuesten Statusinformationen. oder er müsste es sonst rekonstruieren, entweder von Grund auf oder vom letzten Mal an habe es berechnet. (In der nächsten Version dieses Dokuments werden wir Algorand erweitern, um es zu ermöglichen Benutzer können den aktuellen Status effizient rekonstruieren.) • Sicherheit und „Privatsphäre“. Digitale Signaturen garantieren, dass niemand eine Zahlung fälschen kann ein anderer Benutzer. Bei einer Zahlung \(\wp\) sind nicht die öffentlichen Schlüssel und der Betrag verborgen, sondern die Sensiblen Informationen, die ich habe. Tatsächlich erscheint nur H(I) in \(\wp\), und da H eine ideale hash-Funktion ist, ist H(I) ist ein zufälliger 256-Bit-Wert, und daher gibt es keine Möglichkeit herauszufinden, um was ich besser war als um einfach nur erraten. Doch um zu beweisen, was ich getan habe (z. B. um den Grund für die Zahlung zu beweisen), war der Der Zahler kann nur I offenbaren. Die Richtigkeit des offenbarten I kann durch Berechnen von H(I) überprüft werden. und Vergleichen des resultierenden Werts mit dem letzten Element von \(\wp\). Da H tatsächlich stoßfest ist, Es ist schwierig, einen zweiten Wert I′ zu finden, so dass H(I) = H(I′). 2.3 Grundbegriffe und Notationen Schlüssel, Benutzer und Besitzer Sofern nicht anders angegeben, ist jeder öffentliche Schlüssel (kurz „Schlüssel“) langfristig und relativ zu einem digitalen Signaturschema mit der Eindeutigkeitseigenschaft. Ein öffentlicher Schlüssel, den ich hinzufüge das System, wenn ein anderer öffentlicher Schlüssel j, der sich bereits im System befindet, eine Zahlung an i vornimmt. Für die Farbe personifizieren wir Schlüssel. Wir bezeichnen einen Schlüssel i als „er“, sagen, dass ich ehrlich ist, dass ich sende und empfängt Nachrichten usw. Benutzer ist ein Synonym für Schlüssel. Wenn wir einen Schlüssel unterscheiden wollen von die Person, der es gehört, wir verwenden jeweils die Begriffe „digitaler Schlüssel“ und „Eigentümer“. Erlaubnislose und erlaubte Systeme. Ein System ist erlaubnislos, wenn ein digitaler Schlüssel frei ist jederzeit beitreten und ein Eigentümer kann mehrere digitale Schlüssel besitzen; und es ist erlaubt, sonst.Einzigartige Darstellung Jedes Objekt in Algorand hat eine eindeutige Darstellung. Insbesondere jede Menge {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . . .} wird auf eine vorab festgelegte Weise geordnet: z. B. zuerst lexikografisch in x, dann in y usw. Uhren mit gleicher Geschwindigkeit Es gibt keine globale Uhr, sondern jeder Benutzer hat seine eigene Uhr. Benutzeruhren müssen in keiner Weise synchronisiert werden. Wir gehen jedoch davon aus, dass sie alle die gleiche Geschwindigkeit haben. Wenn es beispielsweise laut der Uhr eines Benutzers i 12:00 Uhr ist, kann es entsprechend 14:30 Uhr sein die Uhr eines anderen Benutzers j, aber wenn es laut der Uhr von i 12:01 ist, ist es laut i 2:31 zu js Uhr. Das heißt: „Eine Minute ist für jeden Benutzer gleich (ausreichend, im Wesentlichen gleich).“ Runden Algorand ist in logischen Einheiten organisiert, r = 0, 1, . . ., sogenannte Runden. Wir verwenden konsequent hochgestellte Zeichen, um Runden anzuzeigen. Um anzuzeigen, dass eine nicht numerische Größe Q (z. B. eine Zeichenfolge, ein öffentlicher Schlüssel, ein Satz, eine digitale Signatur usw.) auf ein rundes r bezieht, schreiben wir einfach Qr. Nur wenn Q eine echte Zahl ist (im Gegensatz zu einer als Zahl interpretierbaren Binärzeichenfolge), tun Sie dies wir schreiben Q(r), sodass das Symbol r nicht als Exponent von Q interpretiert werden kann. Zu Beginn einer Runde r > 0 ist die Menge aller öffentlichen Schlüssel PKr und der Systemstatus ist Sr = n ich, ein(r) ich , . . .  : i \(\in\)PKro , wo a(r) ich ist der Geldbetrag, der dem öffentlichen Schlüssel i zur Verfügung steht. Beachten Sie, dass PKr daraus abgeleitet werden kann Sr, und dass Sr auch andere Komponenten für jeden öffentlichen Schlüssel i angeben kann. Für Runde 0 ist PK0 der Satz der anfänglichen öffentlichen Schlüssel und S0 der Anfangsstatus. Sowohl PK0 als auch Es wird davon ausgegangen, dass S0 im System allgemein bekannt sind. Der Einfachheit halber zu Beginn der Runde r, also sind PK1, . . . , PKr und S1, . . . , Sr. In einer Runde r geht der Systemstatus von Sr zu Sr+1 über: symbolisch, Runde r: Sr −→Sr+1. Zahlungen In Algorand führen die Benutzer kontinuierlich Zahlungen durch (und verbreiten diese auf diese Weise). beschrieben in Abschnitt 2.7). Eine Zahlung \(\wp\)eines Benutzers i \(\in\)PKr hat das gleiche Format und die gleiche Semantik wie im Idealen System. Nämlich, \(\wp\)= SIGi(i, i′, a, I, H(I)) . Die Zahlung \(\wp\)ist bei einer Runde r einzeln gültig (ist kurz eine Runde-R-Zahlung), wenn (1) ihr Betrag a ist kleiner oder gleich a(r) i , und (2) es erscheint in keinem offiziellen Gehaltssatz PAY r′ für r′ < r. (Wie unten erläutert, bedeutet die zweite Bedingung, dass \(\wp\) noch nicht wirksam geworden ist. Eine Menge von Rund-r-Zahlungen von i ist insgesamt gültig, wenn die Summe ihrer Beträge höchstens a(r) ist. ich . Gehaltssätze Ein Round-r-Zahlungssatz P ist ein Satz von Round-r-Zahlungen, sodass für jeden Benutzer i die Zahlungen erfolgen von i in P (möglicherweise keine) sind kollektiv gültig. Die Menge aller Round-r-Gehaltssätze ist PAY(r). Ein Rund-r Die Auszahlungsmenge P ist maximal, wenn keine Obermenge von P eine Round-R-Auszahlungsmenge ist. Wir schlagen tatsächlich vor, dass eine Zahlung \(\wp\)auch eine Runde \(\rho\) angibt, \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) , und kann in keiner Runde außerhalb von [\(\rho\), \(\rho\) + k] für eine feste nichtnegative ganze Zahl k gültig sein.4 4Dies vereinfacht die Überprüfung, ob \(\wp\) „wirksam“ geworden ist (d. h. es vereinfacht die Bestimmung, ob ein Gehaltssatz vorliegt). PAY r enthält \(\wp\). Wenn k = 0, wenn \(\wp\)= SIGi(r, i, i′, a, I, H(I)) und \(\wp\)/\(\in\)PAY r, dann muss ich \(\wp\) erneut einreichen.Offizielle Gehaltssätze Für jede Runde r wählt Algorand öffentlich aus (auf eine später beschriebene Weise). ein einzelner (möglicherweise leerer) Payset, PAY r, der offizielle Payset der Runde. (Im Wesentlichen stellt PAY r dar die Round-R-Zahlungen, die „tatsächlich“ stattgefunden haben.) Wie im Idealen System (und Bitcoin) ist (1) die einzige Möglichkeit für einen neuen Benutzer, j das System zu betreten soll der Empfänger einer Zahlung sein, die zum offiziellen Gehaltssatz PAY r einer bestimmten Runde r gehört; und (2) PAY r bestimmt den Status der nächsten Runde, Sr+1, aus dem der aktuellen Runde, Sr. Symbolisch, PAY r : Sr −→Sr+1. Konkret: 1. Die Menge der öffentlichen Schlüssel der Runde r + 1, PKr+1, besteht aus der Vereinigung von PKr und der Menge aller Zahlungsempfängerschlüssel, die erstmals in den Zahlungen von PAY r auftauchen; und 2. der Geldbetrag a(r+1) ich dass ein Benutzer i in Runde r + 1 besitzt, ist die Summe von ai(r) – d. h. die Geldbetrag, den ich in der vorherigen Runde besaß (0, wenn i ̸\(\in\)PKr) – und die Summe der Beträge an i entsprechend den Zahlungen von PAY r gezahlt. Zusammenfassend ist, wie im Idealsystem, jeder Status Sr+1 aus der vorherigen Zahlungshistorie ableitbar: ZAHLEN 0, . . . , ZAHLEN r. 2.4 Blöcke und bewährte Blöcke In Algorand0 gibt der Block Br, der einem runden r entspricht, Folgendes an: r selbst; die Menge der Zahlungen von runde r, ZAHLE r; eine zu erklärende Größe Qr und der hash des vorherigen Blocks, H(Br−1). Ausgehend von einem festen Block B0 haben wir also ein traditionelles blockchain: B1 = (1, PAY 1, Q0, H(B0)), B2 = (2, PAY 2, Q1, H(B1)), B3 = (3, PAY 3, Q2, H(B2)), . . . In Algorand wird die Authentizität eines Blocks tatsächlich durch eine separate Information bestätigt, ein „Blockzertifikat“ CERT r, das Br in einen bewährten Block, Br, verwandelt. Das Magic Ledger ist daher wird durch die Reihenfolge der bewährten Blöcke umgesetzt, B1, B2, . . . Diskussion Wie wir sehen werden, besteht CERT r aus einem Satz digitaler Signaturen für H(Br), denen von a Mehrheit der Mitglieder des SV r, zusammen mit einem Nachweis, dass jedes dieser Mitglieder tatsächlich dazugehört zu SV r. Wir könnten natürlich die Zertifikate CERT r in die Blöcke selbst einbauen, aber wir werden es finden konzeptionell sauberer, um es getrennt zu halten.) In Bitcoin muss jeder Block eine spezielle Eigenschaft erfüllen, das heißt, er muss „eine Lösung von a enthalten Krypto-Puzzle“, was die Blockgenerierung rechenintensiv macht und beides unvermeidlich verzweigt und nicht selten. Im Gegensatz dazu hat blockchain von Algorand zwei Hauptvorteile: Es wird mit generiert minimaler Rechenaufwand, und es wird nicht mit überwältigend hoher Wahrscheinlichkeit gegabelt. Jeder Block Bi ist sicher endgültig, sobald es den blockchain betritt.2.5 Akzeptable Ausfallwahrscheinlichkeit Um die Sicherheit von Algorand zu analysieren, geben wir die Wahrscheinlichkeit F an, mit der wir dazu bereit sind Akzeptieren Sie, dass etwas schief geht (z. B. dass ein Verifizierersatz SV r keine ehrliche Mehrheit hat). Wie bei der Ausgabelänge der kryptografischen Funktion hash H ist auch F ein Parameter. Aber wie in diesem Fall finden wir es nützlich, F auf einen konkreten Wert zu setzen, um eine intuitivere Darstellung zu erhalten begreifen, dass es in Algorand tatsächlich möglich ist, gleichzeitig ausreichende Sicherheit zu genießen und ausreichende Effizienz. Zunächst möchte ich betonen, dass F ein Parameter ist, der beliebig eingestellt werden kann und zweite Ausführungsformen haben wir jeweils festgelegt F = 10−12 und F = 10−18 . Diskussion Beachten Sie, dass 10−12 tatsächlich weniger als eine von einer Billion ist, und wir glauben, dass dies der Fall ist Die Wahl von F ist für unsere Anwendung ausreichend. Wir möchten betonen, dass 10−12 nicht die Wahrscheinlichkeit ist mit dem der Gegner die Zahlungen eines ehrlichen Benutzers fälschen kann. Alle Zahlungen erfolgen digital signiert, und wenn die richtigen digitalen Signaturen verwendet werden, besteht daher eine hohe Wahrscheinlichkeit, dass eine Zahlung gefälscht wird weit niedriger als 10−12 und tatsächlich im Wesentlichen 0. Das schlimme Ereignis, das wir bereit sind zu tolerieren mit der Wahrscheinlichkeit F ist, dass sich blockchain von Algorand verzweigt. Beachten Sie, dass mit unserer Einstellung von F und Bei einminütigen Runden wird erwartet, dass eine Gabelung in blockchain von Algorand so selten wie möglich auftritt (ungefähr) einmal in 1,9 Millionen Jahren. Im Gegensatz dazu kommt es in Bitcoin recht häufig zu einer Verzweigung. Eine anspruchsvollere Person kann F auf einen niedrigeren Wert einstellen. Zu diesem Zweck in unserer zweiten Ausführungsform Wir überlegen, F auf 10−18 zu setzen. Beachten Sie, dass unter der Annahme, dass jede Sekunde ein Block generiert wird, 1018 ist die geschätzte Anzahl an Sekunden, die das Universum bisher benötigt hat: vom Urknall bis heute Zeit. Wenn also mit F = 10−18 ein Block in einer Sekunde erzeugt wird, sollte man mit dem Alter von rechnen Das Universum sieht eine Gabelung. 2.6 Das kontradiktorische Modell Algorand ist so konzipiert, dass es in einem sehr kontroversen Modell sicher ist. Lassen Sie es uns erklären. Ehrliche und böswillige Benutzer Ein Benutzer ist ehrlich, wenn er alle seine Protokollanweisungen befolgt und ist durchaus in der Lage, Nachrichten zu senden und zu empfangen. Ein Benutzer ist böswillig (d. h. byzantinisch). (Sprache des verteilten Rechnens), wenn er willkürlich von seinen vorgeschriebenen Anweisungen abweichen kann. Der Gegner Der Gegner ist ein effizienter (technisch gesehen polynomialer) Algorithmus, personifiziert durch Farbe, der jeden Benutzer, den er möchte, jederzeit und jederzeit böswillig machen kann (Subjekt nur bis zu einer Obergrenze der Anzahl der Benutzer, die er korrumpieren kann). Der Gegner kontrolliert und koordiniert alle böswilligen Benutzer vollständig. Er ergreift alle Maßnahmen in ihrem Namen, einschließlich des Empfangens und Versendens aller ihrer Nachrichten, und kann zulassen, dass sie davon abweichen ihre vorgeschriebenen Anweisungen auf willkürliche Weise. Oder er kann einfach einen beschädigten Benutzerversand isolieren und Empfangen von Nachrichten. Lassen Sie uns klarstellen, dass niemand sonst automatisch erfährt, dass ein Benutzer böswillig ist. Allerdings kann sich meine Böswilligkeit durch die Handlungen bemerkbar machen, die der Gegner von ihm verlangt. Dieser mächtige Gegner jedoch, • Verfügt über keine unbegrenzte Rechenleistung und kann das Digitale nicht erfolgreich fälschen Unterschrift eines ehrlichen Benutzers, außer mit vernachlässigbarer Wahrscheinlichkeit; Und• Darf in keiner Weise den Nachrichtenaustausch zwischen ehrlichen Benutzern beeinträchtigen. Darüber hinaus wird seine Fähigkeit, ehrliche Benutzer anzugreifen, durch eine der folgenden Annahmen eingeschränkt. Ehrlichkeit, Mehrheit des Geldes Wir betrachten ein Kontinuum der ehrlichen Mehrheit des Geldes (HMM). Annahmen: nämlich für jede nicht negative ganze Zahl k und reelles h > 1/2, HHMk > h: Die ehrlichen Benutzer in jeder Runde r besaßen einen Bruchteil größer als h des gesamten Geldes in das System bei Runde r −k. Diskussion. Vorausgesetzt, dass alle böswilligen Benutzer ihre Aktionen perfekt koordinieren (als ob sie kontrolliert würden). durch eine einzelne Entität, den Gegner) ist eine eher pessimistische Hypothese. Perfekte Koordination auch untereinander Für viele Menschen ist es schwierig, dies zu erreichen. Vielleicht findet die Koordination nur innerhalb separater Gruppen statt von böswilligen Spielern. Da man jedoch nicht sicher sein kann, wie gut die Koordination böswilliger Benutzer ist Vielleicht genießen Sie es, wir gehen besser auf Nummer sicher. Auch die Annahme, dass der Gegner Benutzer heimlich, dynamisch und sofort korrumpieren kann, ist möglich pessimistisch. Schließlich dürfte es realistisch gesehen einige Zeit dauern, bis man die vollständige Kontrolle über die Vorgänge eines Benutzers erlangt. Die Annahme HMMk > h impliziert beispielsweise, dass eine Runde (im Durchschnitt) durchgeführt wird In einer Minute bleibt dann der Großteil des Geldes einer bestimmten Runde in ehrlichen Händen mindestens zwei Stunden, wenn k = 120, und mindestens eine Woche, wenn k = 10.000. Beachten Sie die HMM-Annahmen und die vorherige ehrliche Mehrheit der Rechenleistung Annahmen hängen in dem Sinne zusammen, dass Rechenleistung mit Geld gekauft werden kann, Wenn böswillige Benutzer das meiste Geld besitzen, können sie auch den Großteil der Rechenleistung erhalten. 2.7 Das Kommunikationsmodell Wir gehen davon aus, dass die Verbreitung von Nachrichten – d. h. „Peer-to-Peer-Klatsch“5 – das einzige Mittel dafür ist Kommunikation. Vorübergehende Annahme: Rechtzeitige Zustellung von Nachrichten im gesamten Netzwerk. Für In den meisten Teilen dieses Artikels gehen wir davon aus, dass jede verbreitete Nachricht fast alle ehrlichen Benutzer erreicht rechtzeitig. Wir werden diese Annahme in Abschnitt 10 entfernen, wo wir uns mit Netzwerken befassen Partitionen, die entweder natürlich vorkommen oder durch Angriffe herbeigeführt werden. (Wie wir sehen werden, nehmen wir nur an rechtzeitige Zustellung von Nachrichten innerhalb jeder verbundenen Komponente des Netzwerks.) Eine konkrete Möglichkeit, die rechtzeitige Zustellung verbreiteter Nachrichten (im gesamten Netzwerk) zu erfassen, ist Folgendes: Für alle Erreichbarkeiten \(\rho\) > 95 % und Nachrichtengröße \(\mu\) \(\in\)Z+ gibt es \(\lambda\) \(\rho\),\(\mu\), so dass Wenn ein ehrlicher Benutzer zum Zeitpunkt t eine \(\mu\)-Byte-Nachricht m weiterleitet, dann erreicht m zum Zeitpunkt t + \(\lambda\) \(\rho\),\(\mu\) mindestens einen Bruchteil \(\rho\) der ehrlichen Benutzer. 5Im Wesentlichen, wie in Bitcoin, wenn ein Benutzer eine Nachricht m verbreitet, empfängt jeder aktive Benutzer m zum ersten Mal, wählt zufällig und unabhängig eine entsprechend kleine Anzahl aktiver Benutzer, seine „Nachbarn“, aus, an die er m weiterleitet, möglicherweise bis er eine Bestätigung von ihnen erhält. Die Weitergabe von m endet, wenn kein Benutzer empfängt Ich bin zum ersten Mal dabei.Die obige Eigenschaft kann jedoch unser Algorand-Protokoll nicht unterstützen, ohne explizit und separat einen Mechanismus vorzusehen, um die neueste blockchain zu erhalten – von einem anderen Benutzer/Depot usw. Um einen neuen Block Br zu konstruieren, muss nicht nur ein geeigneter Satz von Verifizierern die Runde r rechtzeitig erhalten Nachrichten, sondern auch die Nachrichten früherer Runden, um Br−1 und alle anderen vorherigen zu kennen Blöcke, die notwendig sind, um festzustellen, ob die Zahlungen in Br gültig sind. Folgendes Stattdessen reicht die Annahme aus. Annahme der Nachrichtenweitergabe (MP): Für alle \(\rho\) > 95 % und \(\mu\) \(\in\)Z+ gibt es \(\lambda\) \(\rho\),\(\mu\) so dass für alle Zeiten t und alle \(\mu\)-Byte-Nachrichten m, die von einem ehrlichen Benutzer vor t verbreitet wurden −\(\lambda\) \(\rho\),\(\mu\), m wird zum Zeitpunkt t von mindestens einem Bruchteil \(\rho\) der ehrlichen Benutzer empfangen. Das Protokoll Algorand weist tatsächlich jeden einer kleinen Anzahl von Benutzern (d. h. die Prüfer eines) an gegebener Schritt einer Runde in Algorand ′, um eine separate Nachricht einer (kleinen) vorgeschriebenen Größe zu verbreiten, und wir müssen die Zeit begrenzen, die zur Erfüllung dieser Anweisungen erforderlich ist. Wir tun dies, indem wir den MP bereichern Annahme wie folgt. Für alle n, \(\rho\) > 95 % und \(\mu\) \(\in\)Z+ gibt es \(\lambda\)n,\(\rho\),\(\mu\), so dass für alle Zeiten t und alle \(\mu\)-Byte gilt Nachrichten m1, . . . , mn, jeweils von einem ehrlichen Benutzer vor t −\(\lambda\)n,\(\rho\),\(\mu\), m1, . propagiert. . . , mn werden empfangen, bis zur Zeit t um mindestens einen Bruchteil \(\rho\) der ehrlichen Benutzer. Hinweis • Die obige Annahme ist bewusst einfach, aber auch stärker als in unserer Arbeit erforderlich.6 • Der Einfachheit halber gehen wir von \(\rho\) = 1 aus und verzichten daher auf die Erwähnung von \(\rho\). • Wir gehen pessimistisch davon aus, dass er, sofern er nicht gegen die MP-Annahme verstößt, der Gegner ist kontrolliert vollständig die Zustellung aller Nachrichten. Insbesondere ohne dass es von den Ehrlichen bemerkt wird Benutzer können den Gegner willkürlich entscheiden, welcher ehrliche Spieler wann welche Nachricht erhält, und die Zustellung jeder gewünschten Nachricht willkürlich beschleunigen.7

Das BA-Protokoll BA⋆in einer traditionellen Umgebung

Wie bereits betont, ist das byzantinische Abkommen ein wesentlicher Bestandteil von Algorand. Tatsächlich ist es durch die Verwendung eines solchen BA-Protokolls, dass Algorand von Forks nicht beeinflusst wird. Um jedoch sicher vor unserem zu sein Der mächtige Gegner Algorand muss sich auf ein BA-Protokoll verlassen, das die Ersetzbarkeit neuer Spieler erfüllt Einschränkung. Damit Algorand effizient ist, muss ein solches BA-Protokoll außerdem sehr effizient sein. BA-Protokolle wurden zunächst für ein idealisiertes Kommunikationsmodell, synchrone Vollständigkeit, definiert Netzwerke (SC-Netzwerke). Ein solches Modell ermöglicht einen einfacheren Entwurf und eine einfachere Analyse von BA-Protokollen. 6Anhand des ehrlichen Prozentsatzes h und der akzeptablen Ausfallwahrscheinlichkeit F berechnet Algorand eine Obergrenze N, auf die maximale Anzahl von Prüfern in einem Schritt. Daher muss die MP-Annahme nur für n \(\leq\) N gelten. Darüber hinaus gilt die MP-Annahme, wie bereits erwähnt, unabhängig davon, wie viele andere Nachrichten gleichzeitig verbreitet werden die mjs. Wie wir jedoch sehen werden, werden Nachrichten in Algorand in im Wesentlichen nicht überlappender Zeit verbreitet Intervalle, in denen entweder ein einzelner Block propagiert wird oder höchstens N Verifizierer einen kleinen (z. B. 200B) propagieren Nachricht. Somit könnten wir die MP-Annahme auf eine schwächere, aber auch komplexere Weise umformulieren. 7Zum Beispiel kann er die Nachrichten, die ehrliche Spieler senden, sofort erfahren. Somit ist ein böswilliger Benutzer i′, wer ist Wenn ein ehrlicher Benutzer i aufgefordert wird, gleichzeitig eine Nachricht zu verbreiten, kann er immer seine eigene Nachricht m′ basierend darauf auswählen die Nachricht, die m tatsächlich von i verbreitet wurde. Diese Fähigkeit steht im Zusammenhang mit Rushing, im Sprachgebrauch verteilter Berechnungen Literatur.Dementsprechend stellen wir in diesem Abschnitt ein neues BA-Protokoll, BA⋆, für SC-Netzwerke und Ignorieren vor die Frage der Spielerersetzbarkeit insgesamt. Das Protokoll BA⋆ist ein Beitrag von gesondertem Wert. Tatsächlich ist es das bisher effizienteste kryptografische BA-Protokoll für SC-Netzwerke. Um es in unserem Algorand-Protokoll zu verwenden, modifizieren wir BA⋆ein wenig, um unseren Unterschieden Rechnung zu tragen Kommunikationsmodell und -kontext, aber achten Sie darauf, in Abschnitt X hervorzuheben, wie BA⋆ verwendet wird innerhalb unseres aktuellen Protokolls Algorand ′. Wir erinnern uns zunächst an das Modell, nach dem BA⋆ operiert, und an die Vorstellung einer byzantinischen Vereinbarung. 3.1 Synchrone vollständige Netzwerke und passende Gegner In einem SC-Netzwerk gibt es eine gemeinsame Uhr, die jeweils zu ganzzahligen Zeiten r = 1, 2, . tickt. . . Bei jedem geraden Klick auf r sendet jeder Spieler sofort und gleichzeitig eine Single Nachricht an Herrn i,j (möglicherweise die leere Nachricht) an jeden Spieler j, einschließlich sich selbst. Jeder Herr i,j wird empfangen Zu diesem Zeitpunkt klicken Sie auf r + 1 von Spieler j, zusammen mit der Identität des Absenders i. Auch in einem Kommunikationsprotokoll ist ein Spieler ehrlich, wenn er alle seine Anweisungen befolgt Anweisungen und sonst böswillig. Alle böswilligen Spieler werden vollständig und perfekt kontrolliert koordiniert durch den Gegner, der insbesondere alle an ihn gerichteten Nachrichten sofort erhält böswillige Spieler und wählt die Nachrichten aus, die sie senden. Der Angreifer kann jeden ehrlichen Benutzer, den er möchte, jederzeit bösartig machen Er will, vorbehaltlich nur einer möglichen Obergrenze t für die Anzahl böswilliger Spieler. Das heißt, Der Gegner „kann nicht in die Nachrichten eingreifen, die bereits von einem ehrlichen Benutzer i gesendet wurden“, was der Fall sein wird wie gewohnt geliefert. Der Gegner hat außerdem die zusätzliche Fähigkeit, in jeder geraden Runde sofort zu sehen, was Nachrichten, die die derzeit ehrlichen Spieler senden, und verwenden diese Informationen sofort zur Auswahl Die Nachrichten, die die böswilligen Spieler gleichzeitig senden, ticken. Bemerkungen • Gegnerische Macht. Die obige Einstellung ist sehr kontrovers. Tatsächlich im byzantinischen Abkommen In der Literatur sind viele Situationen weniger kontrovers. Es gibt jedoch einige kontroversere Einstellungen Es wurde auch in Betracht gezogen, dass der Gegner, nachdem er die von einem ehrlichen Spieler gesendeten Nachrichten gesehen hat, i Wenn Sie zu einem bestimmten Zeitpunkt auf r klicken, können Sie alle diese Nachrichten sofort aus dem Netzwerk löschen korruptes i, wählen Sie die Nachricht aus, die das jetzt böswillige i sendet, klicken Sie auf r und lassen Sie sie wie gewohnt geliefert. Die erwartete Macht des Gegners entspricht der, die er in unserer Umgebung hat. • Physikalische Abstraktion. Das geplante Kommunikationsmodell abstrahiert ein eher physisches Modell, bei dem jedes Spielerpaar (i, j) durch eine separate und private Kommunikationsleitung li,j verbunden ist. Das heißt, niemand sonst kann die übermittelten Nachrichten einschleusen, stören oder Informationen über sie erhalten li,j. Die einzige Möglichkeit für den Gegner, Zugriff auf li,j zu erhalten, besteht darin, entweder i oder j zu beschädigen. • Datenschutz und Authentifizierung. In SC-Netzwerken sind Nachrichtenvertraulichkeit und Authentifizierung gewährleistet durch Annahme. Im Gegensatz dazu in unserem Kommunikationsnetzwerk, wo Nachrichten verbreitet werden Von Peer zu Peer wird die Authentifizierung durch digitale Signaturen garantiert und es gibt keinen Datenschutz. Um das Protokoll BA⋆an unsere Umgebung anzupassen, sollte daher jede ausgetauschte Nachricht digital signiert sein (zur weiteren Identifizierung des Staates, in dem es gesendet wurde). Glücklicherweise sind die BA-Protokolle, die wir haben Erwägen Sie die Verwendung in Algorand erfordern keinen Datenschutz für Nachrichten.3.2 Die Idee eines byzantinischen Abkommens Der Begriff der byzantinischen Vereinbarung wurde von Pease Shostak und Lamport [31] für die eingeführt binärer Fall, das heißt, wenn jeder Anfangswert aus einem Bit besteht. Es wurde jedoch schnell erweitert auf beliebige Anfangswerte. (Siehe die Umfragen von Fischer [16] und Chor and Dwork [10].) Von einem BA Protokoll, wir meinen ein Protokoll mit beliebigem Wert. Definition 3.1. In einem synchronen Netzwerk sei P ein N-Spieler-Protokoll, dessen Spielersatz gemeinsam ist Wissen unter den Spielern, t eine positive ganze Zahl, so dass n \(\geq\)2t + 1. Wir sagen, dass P ein ist beliebiger Wert (bzw. binär) (n, t)-Byzantinisches Vereinbarungsprotokoll mit Solidität \(\sigma\) \(\in\)(0, 1) wenn für jede Menge von Werten V, die nicht das Sonderzeichen \(\bot\) enthält (bzw. für V = {0, 1}), in an Ausführung, bei der höchstens t der Spieler böswillig sind und bei der jeder Spieler mit einem beginnt Anfangswert vi \(\in\)V , jeder ehrliche Spieler j hält mit Wahrscheinlichkeit 1 an und gibt einen Wert outi \(\in\)V \(\cup\){\(\bot\)} aus um mit einer Wahrscheinlichkeit von mindestens \(\sigma\) die folgenden zwei Bedingungen zu erfüllen: 1. Übereinstimmung: Es existiert out \(\in\)V \(\cup\){\(\bot\)} mit outi = out für alle ehrlichen Spieler i. 2. Konsistenz: Wenn für einen Wert v \(\in\)V vi = v für alle ehrlichen Spieler ist, dann gilt out = v. Wir bezeichnen out als P-Output und jedes Outi als Player-i-Output. 3.3 Die BA-Notation # In unseren BA-Protokollen muss ein Spieler zählen, wie viele Spieler ihm eine bestimmte Nachricht gesendet haben einen bestimmten Schritt. Dementsprechend gilt für jeden möglichen Wert v, der gesendet werden könnte:

s

ich(v) (oder einfach #i(v), wenn s klar ist) ist die Anzahl der Spieler j, von denen i v in Schritt s erhalten hat. Denken Sie daran, dass ein Spieler i von jedem Spieler j genau eine Nachricht erhält, wenn die Anzahl der Spieler ist n, dann ist für alle i und s P v #s i(v) = n. 3.4 Das binäre BA-Protokoll BBA⋆ In diesem Abschnitt stellen wir ein neues binäres BA-Protokoll vor, BBA⋆, das auf der Ehrlichkeit von mehr basiert als zwei Drittel der Spieler und ist sehr schnell: Egal, was die böswilligen Spieler tun, Jede Ausführung der Hauptschleife bringt die Spieler mit einer Wahrscheinlichkeit von 1/3 zur Übereinstimmung. Jeder Spieler verfügt über seinen eigenen öffentlichen Schlüssel eines digitalen Signaturschemas, das der eindeutigen Signatur entspricht Eigentum. Da dieses Protokoll für die Ausführung in einem synchronen Gesamtnetzwerk vorgesehen ist, ist dies nicht der Fall Ich brauche einen Spieler, der jede seiner Nachrichten signiert. Digitale Signaturen werden verwendet, um in Schritt 3 ein ausreichend häufiges Zufallsbit zu generieren. (In Algorand, Digitale Signaturen werden auch zur Authentifizierung aller anderen Nachrichten verwendet.) Das Protokoll erfordert eine minimale Einrichtung: eine gemeinsame Zufallszeichenfolge r, unabhängig von den Spielern. Schlüssel. (In Algorand wird r tatsächlich durch die Größe Qr ersetzt.) Das Protokoll BBA⋆ist eine dreistufige Schleife, in der die Spieler wiederholt boolesche Werte austauschen Verschiedene Spieler können diese Schleife zu unterschiedlichen Zeiten verlassen. Ein Spieler verlässt diese Schleife durch Weitergabe, irgendwann entweder einen Sonderwert 0∗ oder einen Sonderwert 1∗ und weist damit alle Spieler an „Stellen Sie sich vor“, dass sie in allen zukünftigen Schritten jeweils 0 und 1 von i erhalten. (Alternativ gesagt: annehmendass die letzte Nachricht, die ein Spieler j von einem anderen Spieler i erhalten hat, ein bisschen b war. Dann, in jedem Schritt in dem er keine Nachricht von i erhält, verhält sich j so, als ob ich ihm das Bit b geschickt hätte.) Das Protokoll verwendet einen Zähler \(\gamma\), der angibt, wie oft seine dreistufige Schleife ausgeführt wurde. Zu Beginn von BBA⋆ ist \(\gamma\) = 0. (Man könnte sich \(\gamma\) als einen globalen Zähler vorstellen, aber er wird tatsächlich erhöht von jedem einzelnen Spieler jedes Mal, wenn die Schleife ausgeführt wird.) Es gibt n \(\geq\)3t + 1, wobei t die maximal mögliche Anzahl böswilliger Spieler ist. Eine Binärdatei Zeichenfolge x wird mit der Ganzzahl identifiziert, deren binäre Darstellung (mit möglichen führenden Nullen) x ist; und lsb(x) bezeichnet das niedrigstwertige Bit von x. Protokoll BBA⋆ (Kommunikation) Schritt 1. [Coin-Fixed-To-0-Schritt] Jeder Spieler sendet bi. 1.1 Wenn #1 i (0) \(\geq\)2t + 1, dann setzt i bi = 0, sendet 0∗, gibt outi = 0 aus, und HALTS. 1.2 Wenn #1 i (1) \(\geq\)2t + 1, dann setzt i bi = 1. 1.3 Ansonsten setzt i bi = 0. (Kommunikation) Schritt 2. [Coin-Fixed-To-1-Schritt] Jeder Spieler sendet Bi. 2.1 Wenn #2 i (1) \(\geq\)2t + 1, dann setzt i bi = 1, sendet 1∗, Ausgänge outi = 1, und HALTS. 2.2 Wenn #2 i (0) \(\geq\)2t + 1, dann setze ich bi = 0. 2.3 Ansonsten setzt i bi = 1. (Kommunikation) Schritt 3. [Münzen-echt umgedrehter Schritt] Jeder Spieler i sendet bi und SIGi(r, \(\gamma\)). 3.1 Wenn #3 i (0) \(\geq\)2t + 1, dann setzt i bi = 0. 3.2 Wenn #3 i (1) \(\geq\)2t + 1, dann setzt i bi = 1. 3.3 Ansonsten sei Si = {j \(\in\)N, die i in diesem Schritt 3 eine richtige Nachricht gesendet haben }, i setzt bi = c \(\triangleq\)lsb(minj\(\in\)Si H(SIGi(r, \(\gamma\)))); erhöht \(\gamma\)i um 1; und kehrt zu Schritt 1 zurück. Satz 3.1. Immer wenn n \(\geq\)3t + 1, ist BBA⋆ein binäres (n, t)-BA-Protokoll mit der Solidität 1. Ein Beweis von Satz 3.1 ist in [26] gegeben. Seine Anpassung an unsere Umgebung und seine Austauschbarkeit durch Spieler Eigentum sind neu. Historische Bemerkung Probabilistische binäre BA-Protokolle wurden erstmals von Ben-Or vorgeschlagen asynchrone Einstellungen [7]. Das Protokoll BBA⋆ist eine neuartige Anpassung des binäres BA-Protokoll von Feldman und Micali [15]. Ihr Protokoll war das erste, das wie erwartet funktionierte konstante Anzahl von Schritten. Es funktionierte dadurch, dass die Spieler selbst eine gemeinsame Münze einführten, eine von Rabin vorgeschlagene Idee, die sie über eine externe vertrauenswürdige Partei [32] implementierte.3.5 Abgestufter Konsens und das Protokoll GC Erinnern wir uns für willkürliche Werte an einen Konsensbegriff, der viel schwächer ist als die byzantinische Vereinbarung. Definition 3.2. Sei P ein Protokoll, in dem die Menge aller Spieler allgemein bekannt ist, und zwar jeder Spieler i kennt privat einen beliebigen Anfangswert v′ ich. Wir sagen, dass P ein (n, t)-gestuftes Konsensprotokoll ist, wenn bei jeder Ausführung mit n Spielern at Die meisten davon sind böswillig. Jeder ehrliche Spieler hört auf, ein Wert-Grade-Paar (vi, gi) auszugeben. wobei gi \(\in\){0, 1, 2}, um die folgenden drei Bedingungen zu erfüllen: 1. Für alle ehrlichen Spieler i und j gilt |gi −gj| \(\leq\)1. 2. Für alle ehrlichen Spieler i und j, gi, gj > 0 ⇒vi = vj. 3. Wenn v′ 1 = \(\cdots\) = v′ n = v für einen Wert v, dann ist vi = v und gi = 2 für alle ehrlichen Spieler i. Historische Anmerkung Der Begriff eines abgestuften Konsenses leitet sich einfach von dem eines abgestuften Konsenses ab Sendung, vorgebracht von Feldman und Micali in [15], indem sie die Vorstellung eines Kreuzfahrers stärkt Vereinbarung, eingeführt von Dolev [12] und verfeinert von Turpin und Coan [33].8 In [15] stellten die Autoren auch ein dreistufiges (n, t)-bewertetes Rundfunkprotokoll bereit, Gradecast, für n \(\geq\)3t+1. Später wurde ein komplexeres (n, t)-Graded-Broadcasting-Protokoll für n > 2t+1 gefunden von Katz und Koo [19]. Das folgende zweistufige Protokoll GC besteht aus den letzten beiden Schritten des Gradecasts, ausgedrückt in unserem Notation. Um diese Tatsache hervorzuheben und die Schritte des Protokolls Algorand ′ in Abschnitt 4.1 anzupassen, haben wir Nennen Sie jeweils 2 und 3 die Schritte von GC. Protokoll GC Schritt 2. Jeder Spieler i sendet v′ Ich an alle Spieler. Schritt 3. Jeder Spieler i sendet genau dann an alle Spieler die Zeichenfolge x, wenn #2 i (x) \(\geq\)2t + 1. Ausgabeermittlung. Jeder Spieler i gibt das wie folgt berechnete Paar (vi, gi) aus: • Wenn für ein x, #3 i (x) \(\geq\)2t + 1, dann gilt vi = x und gi = 2. • Wenn für ein x, #3 i (x) \(\geq\)t + 1, dann gilt vi = x und gi = 1. • Sonst gilt vi = \(\bot\)und gi = 0. Satz 3.2. Wenn n \(\geq\)3t + 1, dann ist GC ein (n, t)-abgestuftes Broadcast-Protokoll. Der Beweis folgt unmittelbar aus dem des Protokoll-Gradecasts in [15] und wird daher weggelassen.9 8Im Wesentlichen ist in einem abgestuften Rundfunkprotokoll (a) die Eingabe jedes Spielers die Identität eines Distinguished Spieler, der Absender, der einen beliebigen Wert v als zusätzliche private Eingabe hat, und (b) die Ausgaben müssen die erfüllen gleiche Eigenschaften 1 und 2 des abgestuften Konsenses, plus die folgende Eigenschaft 3′: Wenn der Absender ehrlich ist, dann gilt vi = v und gi = 2 für alle ehrlichen Spieler i. 9Tatsächlich sendet der Absender in seinem Protokoll in Schritt 1 seinen eigenen privaten Wert v an alle Spieler, und jeder Spieler i lässt zu v′ i besteht aus dem Wert, den er in Schritt 1 tatsächlich vom Absender erhalten hat.3.6 Das Protokoll BA⋆ Wir beschreiben nun das Arbiträrwert-BA-Protokoll BA⋆über das binäre BA-Protokoll BBA⋆und das Protokoll mit abgestuftem Konsens GC. Unten ist der Anfangswert jedes Spielers i v′ ich. Protokoll BA⋆ Schritte 1 und 2. Jeder Spieler i führt GC bei der Eingabe v′ aus i, um ein Paar (vi, gi) zu berechnen. Schritt 3, . . . Jeder Spieler i führt BBA⋆ aus – mit der anfänglichen Eingabe 0, wenn gi = 2, und 1 andernfalls – also um das Bit outi zu berechnen. Ausgabeermittlung. Jeder Spieler i gibt vi aus, wenn outi = 0, andernfalls \(\bot\). Satz 3.3. Immer wenn n \(\geq\)3t + 1, ist BA⋆ein (n, t)-BA-Protokoll mit der Solidität 1. Beweis. Wir beweisen zunächst die Konsistenz und dann die Übereinstimmung. Konsistenznachweis. Nehmen Sie an, dass für einen Wert v \(\in\)V v′ i = v. Dann, nach Eigenschaft 3 von Abgestufter Konsens, nach der GC-Ausführung geben alle ehrlichen Spieler aus (v, 2). Dementsprechend ist 0 das erste Stück aller ehrlichen Spieler am Ende der Ausführung von BBA⋆. Also durch die Vereinbarung Eigenschaft der binären byzantinischen Vereinbarung, am Ende der Ausführung von BA⋆, outi = 0 für alle ehrlich Spieler. Dies impliziert, dass die Ausgabe jedes ehrlichen Spielers i in BA⋆vi = v ist. ✷ Nachweis der Vereinbarung. Da BBA⋆ auch ein binäres BA-Protokoll ist (A) outi = 1 für alle ehrlichen Spieler i, oder (B) outi = 0 für alle ehrlichen Spieler i. Im Fall A geben alle ehrlichen Spieler \(\bot\)in BA⋆ aus, und somit gilt die Vereinbarung. Betrachten Sie nun Fall B. In In diesem Fall ist bei der Ausführung von BBA⋆ das Anfangsbit von mindestens einem ehrlichen Spieler i 0. (In der Tat, wenn Das anfängliche Bit aller ehrlichen Spieler war 1, dann hätten wir es aufgrund der Konsistenzeigenschaft von BBA⋆ outj = 1 für alle ehrlichen j.) Dementsprechend gibt i nach der Ausführung von GC das Paar (v, 2) für einige aus Wert v. Somit ist nach Eigenschaft 1 des abgestuften Konsenses gj > 0 für alle ehrlichen Spieler j. Dementsprechend von Eigenschaft 2 des abgestuften Konsenses, vj = v für alle ehrlichen Spieler j. Dies impliziert, dass am Ende BA⋆, jeder ehrliche Spieler j gibt v aus. Somit gilt Übereinstimmung auch im Fall B. ✷ Da sowohl Konsistenz als auch Übereinstimmung gelten, ist BA⋆ein BA-Protokoll mit beliebigem Wert. Historische Anmerkung Turpin und Coan waren die ersten, die zeigten, dass für n \(\geq\)3t+1 jedes binäre (n, t)-BA gilt Das Protokoll kann in ein (n, t)-BA-Protokoll mit beliebigem Wert umgewandelt werden. Die Reduzierung auf einen beliebigen Wert Die byzantinische Vereinbarung zur binären byzantinischen Vereinbarung über einen abgestuften Konsens ist modularer und sauberer und vereinfacht die Analyse unseres Algorand-Protokolls Algorand ′. Verallgemeinerung von BA⋆zur Verwendung in Algorand Algorand funktioniert auch dann, wenn die gesamte Kommunikation über erfolgt Klatschen. Allerdings, obwohl in einem traditionellen und vertrauten Kommunikationsnetzwerk präsentiert, so Um einen besseren Vergleich mit dem Stand der Technik und ein leichteres Verständnis zu ermöglichen, funktioniert das Protokoll BA⋆works auch in Klatschnetzwerken. Tatsächlich werden wir es in unseren detaillierten Ausführungsformen von Algorand vorstellen direkt für Klatschnetzwerke. Wir weisen auch darauf hin, dass es der Austauschbarkeit des Spielers gerecht wird Eigentum, das für die Sicherheit von Algorand im geplanten sehr kontradiktorischen Modell von entscheidender Bedeutung ist.

Jedes durch einen BA-Spieler austauschbare Protokoll, das in einem klatschenden Kommunikationsnetzwerk funktioniert, kann sein sicher im erfinderischen Algorand-System eingesetzt. Insbesondere Micali und Vaikunthanatan haben BA⋆ erweitert, um auch mit einer einfachen Mehrheit ehrlicher Spieler sehr effizient zu arbeiten. Das Auch das Protokoll könnte in Algorand verwendet werden.

Zwei Ausführungsformen von Algorand

Wie bereits erwähnt, läuft eine Runde Algorand auf sehr hohem Niveau idealerweise wie folgt ab. Zuerst ein Zufall Der ausgewählte Benutzer, der Leiter, schlägt einen neuen Block vor und verteilt ihn. (Dieser Prozess umfasst zunächst Wählen Sie einige potenzielle Führungskräfte aus und stellen Sie dann sicher, dass zumindest in einem guten Teil der Zeit a es entsteht ein einziger gemeinsamer Anführer.) Zweitens wird ein zufällig ausgewähltes Komitee von Benutzern ausgewählt, und erreicht eine byzantinische Einigung über den vom Führer vorgeschlagenen Block. (Dieser Prozess beinhaltet das Jeder Schritt des BA-Protokolls wird von einem separat ausgewählten Ausschuss geleitet.) Der vereinbarte Block wird dann von einer bestimmten Schwelle (TH) an Ausschussmitgliedern digital signiert. Diese digitalen Signaturen werden verteilt, so dass jeder sicher ist, welcher der neue Block ist. (Dazu gehört auch die Weitergabe der Anmeldeinformationen der Unterzeichner und Authentifizierung nur des hash des neuen Blocks, um sicherzustellen, dass jeder wird den Block garantiert lernen, sobald sein hash klargestellt ist.) In den nächsten beiden Abschnitten stellen wir zwei Ausführungsformen von Algorand, Algorand vor. 1 und Algorand ′ 2, die unter der Annahme der Mehrheit der ehrlichen Benutzer funktionieren. In Abschnitt 8 zeigen wir, wie man diese übernimmt Verkörperungen funktionieren unter der Annahme einer ehrlichen Mehrheit des Geldes. Algorand ′ 1 sieht lediglich vor, dass > 2/3 der Ausschussmitglieder ehrlich sind. Darüber hinaus in Algorand ′ 1 ist die Anzahl der Schritte zur Erzielung einer byzantinischen Einigung auf einen angemessen hohen Betrag begrenzt Zahl, so dass eine Einigung mit überwältigender Wahrscheinlichkeit innerhalb von a gewährleistet ist Feste Anzahl von Schritten (aber möglicherweise länger dauernd als die Schritte von Algorand ′ 2). Im In einem entfernten Fall, in dem bis zum letzten Schritt noch keine Einigung erzielt wurde, stimmt der Ausschuss dem zu leerer Block, der immer gültig ist. Algorand ′ 2 sieht vor, dass die Zahl der ehrlichen Mitglieder in einem Ausschuss immer größer ist als oder gleich einem festen Schwellenwert tH (was dies zumindest mit überwältigender Wahrscheinlichkeit garantiert). 2/3 der Ausschussmitglieder sind ehrlich). Darüber hinaus Algorand ′ 2 ermöglicht eine byzantinische Vereinbarung in einer beliebigen Anzahl von Schritten erreicht werden (aber möglicherweise in kürzerer Zeit als Algorand ′ 1). Viele Varianten dieser Grundausführungen lassen sich leicht ableiten. Insbesondere ist es einfach, gegeben Algorand ′ 2, um Algorand ′ zu ändern 1, um eine willkürliche byzantinische Einigung zu ermöglichen Anzahl der Schritte. Beide Ausführungsformen teilen den folgenden gemeinsamen Kern, die folgenden Notationen, Begriffe und Parameter. 4.1 Ein gemeinsamer Kern Ziele Idealerweise würde Algorand für jede Runde r die folgenden Eigenschaften erfüllen: 1. Perfekte Korrektheit. Alle ehrlichen Benutzer sind sich im selben Block einig, Br. 2. Vollständigkeit 1. Mit Wahrscheinlichkeit 1 ist die Lohnmenge von Br, PAY r, maximal.10 10Weil Gehaltssätze so definiert sind, dass sie gültige Zahlungen enthalten und ehrliche Benutzer nur gültige Zahlungen leisten dürfen, ein Maximum PAY r enthält die „aktuell ausstehenden“ Zahlungen aller ehrlichen Nutzer.Natürlich ist die Gewährleistung vollkommener Korrektheit allein trivial: Jeder wählt immer den Beamten Payset PAY r muss leer sein. Aber in diesem Fall hätte das System die Vollständigkeit 0. Leider Die Gewährleistung sowohl vollkommener Richtigkeit als auch Vollständigkeit 1 ist angesichts böswilliger Angriffe nicht einfach Benutzer. Algorand verfolgt somit eine realistischere Zielsetzung. Informell bezeichnet h den Prozentsatz der ehrlichen Benutzer, h > 2/3, ist das Ziel von Algorand Garantiert mit überwältigender Wahrscheinlichkeit vollkommene Korrektheit und Vollständigkeit nahe h. Der Richtigkeit Vorrang vor der Vollständigkeit zu geben, scheint eine vernünftige Entscheidung zu sein: Zahlungen werden nicht verarbeitet Eine Runde kann in der nächsten abgearbeitet werden, man sollte aber nach Möglichkeit auf Gabelungen verzichten. Geführtes byzantinisches Abkommen Perfekte Korrektheit kann wie folgt garantiert werden. Am Anfang In Runde r erstellt jeder Benutzer i seinen eigenen Kandidatenblock Br i , und dann erreichen alle Benutzer Byzantine Einigung über einen Kandidatenblock. Gemäß unserer Einführung erfordert das verwendete BA-Protokoll eine ehrliche 2/3-Mehrheit und ist durch Spieler austauschbar. Jeder seiner Schritte kann von einem kleinen und ausgeführt werden zufällig ausgewählte Gruppe von Verifizierern, die keine inneren Variablen gemeinsam haben. Leider gibt es für diesen Ansatz keine Vollständigkeitsgarantie. Das ist so, weil der Kandidat Die Blöcke der ehrlichen Benutzer unterscheiden sich höchstwahrscheinlich völlig voneinander. Somit ist das letztendlich Der vereinbarte Block kann immer einer mit einem nicht maximalen Gehaltssatz sein. Tatsächlich kann es immer so sein leerer Block, B\(\varepsilon\), d. h. der Block, dessen Payset leer ist. Nun, es wird die Standardeinstellung sein, leer. Algorand ′ vermeidet dieses Vollständigkeitsproblem wie folgt. Zunächst wird ein Anführer für die Runde r, \(\ell\)r, ausgewählt. Dann propagiert \(\ell\)r seinen eigenen Kandidatenblock, Br \(\ell\)r. Schließlich einigen sich die Nutzer auf die Sperre sie erhalten tatsächlich von \(\ell\)r. Denn wann immer \(\ell\)r ehrlich ist, vollkommene Korrektheit und Vollständigkeit 1 gilt beides, Algorand ′ stellt sicher, dass \(\ell\)r ehrlich ist mit einer Wahrscheinlichkeit nahe h. (Wenn der Anführer ist Böswillig ist es uns egal, ob der vereinbarte Block einer mit einem leeren Payset ist. Immerhin a böswilliger Anführer \(\ell\)r könnte sich immer böswillig für Br entscheiden \(\ell\)r der leere Block sein, und dann ehrlich verbreiten Sie es und zwingen Sie so die ehrlichen Benutzer, sich auf den leeren Block zu einigen.) Auswahl des Leiters In Algorand hat der r-te Block die Form Br = (r, PAY r, Qr, H(Br−1). Wie bereits in der Einleitung erwähnt, wird die Größe Qr−1 sorgfältig so konstruiert, dass sie ist im Wesentlichen nicht manipulierbar durch unseren sehr mächtigen Gegner. (Später in diesem Abschnitt werden wir Geben Sie eine Vorstellung davon, warum dies der Fall ist.) Zu Beginn einer Runde r kennen alle Benutzer das blockchain bisher, B0, . . . , Br−1, woraus sie die Menge der Benutzer jeder vorherigen Runde ableiten: das ist, PK1, . . . , PKr−1. Ein potenzieller Anführer der Runde r ist ein Benutzer, der so ist .H SIGi r, 1, Qr−1 \(\leq\)p . Lassen Sie es uns erklären. Beachten Sie, dass die Größe Qr−1 Teil des Blocks Br−1 und des zugrundeliegenden ist Das Signaturschema erfüllt die Eindeutigkeitseigenschaft SIGi r, 1, Qr−1 ist eindeutig eine Binärzeichenfolge verbunden mit i und r. Da H also ein zufälliger oracle ist, ist H SIGi r, 1, Qr−1 ist ein zufälliges 256-Bit lange Zeichenfolge, die eindeutig i und r zugeordnet ist. Das Symbol „.“ vor H SIGi r, 1, Qr−1 ist das Dezimalpunkt (in unserem Fall binär), so dass ri \(\triangleq\).H SIGi r, 1, Qr−1 ist die binäre Entwicklung von a Zufällige 256-Bit-Zahl zwischen 0 und 1, die eindeutig i und r zugeordnet ist. Somit ist die Wahrscheinlichkeit, dass ri kleiner oder gleich p ist im Wesentlichen p. (Unser Auswahlmechanismus für potenzielle Führungskräfte war inspiriert vom Mikrozahlungssystem von Micali und Rivest [28].) Die Wahrscheinlichkeit p wird so gewählt, dass mit überwältigender Wahrscheinlichkeit (d. h. 1 − F) mindestens eins vorliegt Der potenzielle Prüfer ist ehrlich. (Tatsächlich wird p so gewählt, dass es die kleinste derartige Wahrscheinlichkeit ist.)Beachten Sie, dass er allein dazu in der Lage ist, da ich der Einzige ist, der in der Lage ist, seine eigenen Signaturen zu berechnen Stellen Sie fest, ob er ein potenzieller Prüfer der ersten Runde ist. Indem Sie jedoch seine eigenen Qualifikationen offenlegen, \(\sigma\)r i \(\triangleq\)SIGi r, 1, Qr−1 , ich kann jedem beweisen, dass ich ein potenzieller Prüfer der Runde r bin. Der Anführer ist der potenzielle Anführer, dessen hashed-Berechtigung kleiner ist als der hashed-Berechtigungsnachweis aller anderen potenziellen Anführer j: das heißt, H(\(\sigma\)r,s \(\ell\)r ) \(\leq\)H(\(\sigma\)r,s j). Beachten Sie, dass, da ein böswilliger \(\ell\)r seinen Berechtigungsnachweis nicht preisgeben darf, der richtige Anführer der Runde r dies tun darf nie bekannt werden, und dass \(\ell\)r, sofern es keine unwahrscheinlichen Bindungen gibt, tatsächlich der einzige Anführer der Runde r ist. Lassen Sie uns abschließend noch ein letztes, aber wichtiges Detail ansprechen: Ein Benutzer kann ein potenzieller Anführer sein (und somit der Anführer) einer Runde r nur dann, wenn er mindestens k Runden dem System angehörte. Das garantiert die Nichtmanipulierbarkeit von Qr und allen zukünftigen Q-Größen. Tatsächlich einer der potenziellen Anführer wird tatsächlich Qr bestimmen. Auswahl des Verifizierers Jeder Schritt s > 1 der Runde r wird von einer kleinen Gruppe von Prüfern, SV r,s, ausgeführt. Auch hier wird jeder Verifizierer i \(\in\)SV r,s zufällig unter den Benutzern ausgewählt, die sich bereits in den k Runden des Systems befinden vor r und wiederum über die Sondergröße Qr−1. Konkret ist i \(\in\)PKr−k ein Verifizierer in SV r,s, wenn .H SIGi r, s, Qr−1 \(\leq\)p′ . Auch hier weiß nur ich, ob er zum SV r,s gehört, aber wenn das der Fall ist, könnte er es durch beweisen stellt seinen Berechtigungsnachweis \(\sigma\)r,s vor ich \(\triangleq\)H(SIGi r, s, Qr−1 ). Ein Prüfer i \(\in\)SV r,s sendet eine Nachricht, mr,s ich, in Schritte s der Runde r, und diese Nachricht enthält seine Anmeldeinformationen \(\sigma\)r,s i , um die Verifizierer für die zu aktivieren Nestschritt, um zu erkennen, dass Herr, S ich ist eine legitime Step-S-Nachricht. Die Wahrscheinlichkeit p′ wird so gewählt, dass sichergestellt ist, dass in SV r,s #good die Zahl von ist ehrliche Benutzer und #bad die Anzahl böswilliger Benutzer, mit überwältigender Wahrscheinlichkeit das Folgende Es gelten zwei Bedingungen. Zur Verkörperung Algorand ′ 1: (1) #gut > 2 \(\cdot\) #schlecht und (2) #gut + 4 \(\cdot\) #schlecht < 2n, wobei n die erwartete Kardinalität von SV r,s ist. Zur Verkörperung Algorand ′ 2: (1) #gut > tH und (2) #gut + 2#schlecht < 2tH, wobei tH ein festgelegter Schwellenwert ist. Diese Bedingungen implizieren, dass mit ausreichend hoher Wahrscheinlichkeit (a) im letzten Schritt des BA Protokoll wird es mindestens eine bestimmte Anzahl ehrlicher Spieler geben, die den neuen Block Br digital signieren, (b) nur ein Block pro Runde darf die erforderliche Anzahl an Signaturen haben und (c) die verwendete BA Das Protokoll verfügt (bei jedem Schritt) über die erforderliche ehrliche Zweidrittelmehrheit. Klärung der Blockgenerierung Wenn der Rund-R-Anführer \(\ell\)r ehrlich ist, dann der entsprechende Block ist von der Form Br = r, PAY r, SIG\(\ell\)r Qr−1 , H Br−1 , wobei der Payset PAY r maximal ist. (Denken Sie daran, dass alle Gehaltssätze per Definition kollektiv gültig sind.) Andernfalls (d. h. wenn \(\ell\)r böswillig ist) hat Br eine der folgenden zwei möglichen Formen: Br = r, ZAHLEN r, SIGi Qr−1 , H Br−1 und Br = Br \(\varepsilon\) \(\triangleq\) r, \(\emptyset\), Qr−1, H Br−1 .In der ersten Form ist PAY r eine (nicht unbedingt maximale) Gehaltsmenge und kann PAY r = \(\emptyset\) sein; und ich bin ein potenzieller Anführer der Runde r. (Allerdings bin ich möglicherweise nicht der Anführer. Dies kann tatsächlich passieren, wenn \(\ell\)r hält seinen Ausweis geheim und gibt sich nicht zu erkennen.) Die zweite Form entsteht, wenn bei der Round-R-Ausführung des BA-Protokolls alle ehrlichen Spieler auftreten Geben Sie den Standardwert aus, der der leere Block Br ist \(\varepsilon\) in unserer Anwendung. (Per Definition das Mögliche Ausgaben eines BA-Protokolls enthalten einen Standardwert, der allgemein mit \(\bot\) bezeichnet wird. Siehe Abschnitt 3.2.) Beachten Sie, dass Br =, obwohl die Gehaltssätze in beiden Fällen leer sind r, \(\emptyset\), SIGi Qr−1 , H Br−1 und Br \(\varepsilon\) sind syntaktisch unterschiedliche Blöcke und treten in zwei verschiedenen Situationen auf: bzw. „alle verlief reibungslos genug bei der Ausführung des BA-Protokolls“, und „etwas ist schief gelaufen BA-Protokoll und der Standardwert wurde ausgegeben“. Beschreiben wir nun intuitiv, wie die Generierung des Blocks Br in Runde r von Algorand ′ abläuft. Im ersten Schritt prüft jeder teilnahmeberechtigte Spieler, also jeder Spieler i \(\in\)PKr−k, ob er ein Potential ist Anführer. Wenn dies der Fall ist, dann wird ich gefragt, unter Verwendung aller Zahlungen, die er bisher gesehen hat, und die aktuell blockchain, B0, . . . , Br−1, um heimlich einen maximalen Zahlungssatz, PAY r, vorzubereiten ich, und zwar heimlich stellt seinen Kandidatenblock zusammen, Br = r, ZAHLEN r Ich, SIGi Qr−1 , H Br−1 . Das heißt, nicht nur er in Br einschließen i als zweite Komponente der soeben vorbereitete Lohnsatz, aber auch als dritte Komponente seine eigene Signatur von Qr−1, der dritten Komponente des letzten Blocks, Br−1. Schließlich propagiert er seine Runde-r-Schritt-1-Nachricht, mr,1 i , zu dem (a) sein Kandidatenblock Br gehört i, (b) seine ordnungsgemäße Unterschrift seines Kandidatenblocks (d. h. seine Unterschrift des hash von Br i und (c) sein eigener Ausweis \(\sigma\)r,1 ich, beweisen dass er tatsächlich ein potenzieller Verifizierer der Runde r ist. (Beachten Sie, dass, bis ein ehrlicher Herr seine Botschaft hervorbringt, 1 Ich, der Widersacher hat keine Ahnung, dass ich ein bin potenzieller Prüfer. Sollte er ehrliche potenzielle Anführer korrumpieren wollen, könnte der Widersacher dies auch tun korrupte zufällige ehrliche Spieler. Sobald er jedoch Herrn 1 sieht i , da es die Anmeldeinformationen von i enthält, die Der Gegner weiß es und könnte i korrumpieren, kann mr,1 aber nicht verhindern i , das viral verbreitet wird, von alle Benutzer im System erreichen.) Im zweiten Schritt versucht jeder ausgewählte Verifizierer j \(\in\)SV r,2, den Anführer der Runde zu identifizieren. Insbesondere nimmt j die Anmeldeinformationen für Schritt 1 an, \(\sigma\)r,1 i1 , . . . , \(\sigma\)r,1 in , enthalten in der richtigen Schritt-1-Nachricht mr,1 ich er hat empfangen; hashes alle, das heißt, berechnet H  \(\sigma\)r,1 i1  , . . . , H  \(\sigma\)r,1 in  ; findet den Ausweis, \(\sigma\)r,1 \(\ell\)j , dessen hash lexikographisch minimal ist; und überlegt \(\ell\)r j soll der Anführer der Runde r sein. Denken Sie daran, dass jeder betrachtete Berechtigungsnachweis eine digitale Signatur von Qr−1, also SIGi, ist r, 1, Qr−1 ist eindeutig durch i und Qr−1 bestimmt, dass H zufällig oracle ist und somit jedes H(SIGi r, 1, Qr−1 ist eine zufällige 256-Bit-lange Zeichenfolge, die für jeden potenziellen Anführer i der Runde r eindeutig ist. Daraus können wir schließen, dass die 256-Bit-Zeichenfolge Qr−1 selbst zufällig und unabhängig wäre ausgewählt, dann wären dies die hashed-Anmeldeinformationen aller potenziellen Anführer der Runde r. Tatsächlich alle Potenzielle Führungskräfte sind genau definiert, ebenso wie ihre Qualifikationen (ob tatsächlich berechnet oder nicht). nicht). Darüber hinaus ist die Menge potenzieller Anführer der Runde r eine zufällige Teilmenge der Benutzer der Runde r −k, und ein ehrlicher potenzieller Anführer, der seine Botschaft immer richtig formuliert und verbreitet, Herr ich, welches den Berechtigungsnachweis von i enthält. Da also der Prozentsatz der ehrlichen Benutzer h ist, egal was böswillige potenzielle Führungskräfte könnten das Mindeste tun (z. B. ihre eigenen Referenzen preisgeben oder verbergen). hashed Die Qualifikation als potenzieller Leiter gehört einem ehrlichen Benutzer, der unbedingt von jedem identifiziert werden kann der Anführer \(\ell\)r der Runde r sein. Wenn dementsprechend die 256-Bit-Zeichenfolge Qr−1 selbst zufällig wäre und unabhängig ausgewählt, mit Wahrscheinlichkeit genau h (a) der Anführer \(\ell\)r ist ehrlich und (b) \(\ell\)j = \(\ell\)r für alle Ehrliche Schritt-2-Prüfer j. In Wirklichkeit werden die hashed-Berechtigungsnachweise zwar zufällig ausgewählt, hängen aber von Qr-1 ab, was der Fall istnicht zufällig und unabhängig ausgewählt. Wir werden in unserer Analyse jedoch beweisen, dass Qr−1 gilt ausreichend nicht manipulierbar, um sicherzustellen, dass der Anführer einer Runde ehrlich mit der Wahrscheinlichkeit ist h′ hinreichend nahe bei h liegt: nämlich h′ > h2(1 + h − h2). Wenn beispielsweise h = 80 %, dann ist h′ > 0,7424. Nachdem sie den Anführer der Runde identifiziert haben (was sie richtig machen, wenn der Anführer ehrlich ist), Die Aufgabe der Schritt-2-Verifizierer besteht darin, mit der Ausführung des BA zu beginnen und dabei als Anfangswerte das zu verwenden, woran sie glauben der Block des Anführers sein. Um den Umfang der erforderlichen Kommunikation zu minimieren, Ein Verifizierer j \(\in\)SV r,2 verwendet nicht als seinen Eingabewert v′ j zum byzantinischen Protokoll, der Block Bj das Er hat tatsächlich von \(\ell\)j empfangen (der Benutzer j glaubt, der Anführer zu sein), aber der der Anführer, aber der hash dieses Blocks, also v′ j = H(Bi). Daher werden nach Beendigung des BA-Protokolls die Verifizierer des letzten Schritts nicht den gewünschten Round-r-Block Br berechnen, sondern berechnen (authentifizieren und propagieren) H(Br). Da H(Br) dementsprechend von ausreichend vielen Verifizierern digital signiert ist Im letzten Schritt des BA-Protokolls werden die Benutzer im System erkennen, dass H(Br) der hash des neuen ist blockieren. Sie müssen jedoch auch die Datei abrufen (oder darauf warten, da die Ausführung ziemlich asynchron ist). Blockieren Sie Br selbst, wodurch das Protokoll sicherstellt, dass es tatsächlich verfügbar ist, unabhängig vom Gegner könnte reichen. Asynchronität und Timing Algorand ′ 1 und Algorand ′ 2 weisen einen erheblichen Grad an Asynchronität auf. Dies liegt daran, dass der Gegner einen großen Spielraum bei der Planung der Zustellung der Nachrichten hat propagiert. Darüber hinaus gibt es eine Obergrenze dafür, ob die Gesamtzahl der Schritte in einer Runde begrenzt ist oder nicht Der Varianzbeitrag ergibt sich aus der Anzahl der tatsächlich unternommenen Schritte. Sobald er die Zertifikate B0 erlernt hat, . . . , Br−1, ein Benutzer i berechnet Qr−1 und beginnt zu arbeiten In Runde r prüft er, ob er ein potenzieller Anführer oder ein Prüfer in einigen Schritten von Runde r ist. Unter der Annahme, dass ich angesichts der besprochenen Asynchronität bei Schritt s handeln muss, verlasse ich mich auf verschiedene Strategien, um sicherzustellen, dass er über ausreichende Informationen verfügt, bevor er handelt. Beispielsweise könnte er warten, bis er mindestens eine bestimmte Anzahl von Nachrichten von den Prüfern von erhält Gehen Sie zum vorherigen Schritt über oder warten Sie ausreichend Zeit, um sicherzustellen, dass er die Nachrichten ausreichend erhält viele Verifizierer des vorherigen Schritts. Der Seed Qr und der Look-Back-Parameter k Denken Sie daran, dass im Idealfall die Größen Qr sein sollten zufällig und unabhängig, obwohl es ausreicht, dass sie ausreichend nicht manipulierbar sind der Gegner. Auf den ersten Blick könnten wir Qr−1 so wählen, dass es mit H übereinstimmt ZAHLEN Sie r−1 , und vermeiden Sie es daher spezifizieren Sie Qr−1 explizit in Br−1. Eine elementare Analyse zeigt jedoch, dass böswillige Benutzer möglicherweise Nutzen Sie diesen Auswahlmechanismus.11 Einige zusätzliche Anstrengungen zeigen, dass unzählige andere 11Wir stehen am Anfang der Runde r −1. Somit ist Qr−2 = PAY r−2 öffentlich bekannt und der Gegner privat weiß, wer die potenziellen Führungskräfte sind, die er kontrolliert. Gehen Sie davon aus, dass der Gegner 10 % der Benutzer kontrolliert dass mit sehr hoher Wahrscheinlichkeit ein böswilliger Benutzer w der potenzielle Anführer der Runde r −1 ist. Das heißt, nehmen Sie das an H SIGw r −2, 1, Qr−2 ist so gering, dass es höchst unwahrscheinlich ist, dass ein ehrlicher potenzieller Anführer dies tatsächlich tun wird Anführer der Runde r −1. (Da wir uns daran erinnern, dass wir potenzielle Anführer über einen geheimen kryptografischen Sortiermechanismus auswählen, Der Widersacher weiß nicht, wer die ehrlichen potenziellen Anführer sind.) Der Widersacher ist daher beneidenswert Position der Wahl des von ihm gewünschten Gehaltssatzes PAY′ und dass dieser zum offiziellen Gehaltssatz der Runde r −1 geworden ist. Allerdings er kann mehr. Er kann auch sicherstellen, dass mit hoher Wahrscheinlichkeit () einer seiner böswilligen Benutzer der Anführer sein wird auch der Runde r, so dass er frei wählen kann, wie hoch PAY r sein soll. (Und so weiter. Zumindest für eine lange Zeit, solange diese Ereignisse mit hoher Wahrscheinlichkeit tatsächlich eintreten.) Um () zu garantieren, verhält sich der Gegner wie folgt. Lass ZAHLEN‘ sei der vom Gegner bevorzugte Auszahlungssatz für Runde r −1. Dann berechnet er H(PAY ′) und prüft, ob für einige Der bereits böswillige Spieler z, SIGz(r, 1, H(PAY ′)) ist besonders klein, also klein genug, um sehr hoch zu sein Wahrscheinlichkeit z wird der Anführer der Runde r sein. Wenn dies der Fall ist, weist er w an, seinen Kandidatenblock auszuwählenAlternativen, die auf traditionellen Blockmengen basieren, können vom Gegner leicht ausgenutzt werden, um sicherzustellen dass böswillige Anführer sehr häufig sind. Vielmehr definieren wir unsere Marke gezielt und induktiv neue Größe Qr, um nachweisen zu können, dass sie vom Gegner nicht manipulierbar ist. Nämlich, Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), wenn Br nicht der leere Block ist, andernfalls Qr \(\triangleq\)H(Qr−1, r). Die Intuition, warum diese Konstruktion von Qr funktioniert, ist wie folgt. Nehmen Sie das für einen Moment an Qr−1 wird wirklich zufällig und unabhängig ausgewählt. Wird Qr dann auch so sein? Wenn \(\ell\)r ehrlich ist, dann Die Antwort lautet (grob gesagt) ja. Das liegt daran H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→{0, 1}256 ist eine Zufallsfunktion. Wenn \(\ell\)r jedoch böswillig ist, ist Qr nicht mehr eindeutig aus Qr−1 definiert und \(\ell\)r. Es gibt mindestens zwei separate Werte für Qr. Man bleibt weiterhin Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), und der andere ist H(Qr−1, r). Lassen Sie uns zunächst argumentieren, dass die zweite Wahl zwar etwas willkürlich ist, eine zweite Wahl ist unbedingt erforderlich. Der Grund dafür ist, dass ein böswilliger Fehler immer verursacht werden kann völlig unterschiedliche Kandidatenblöcke, die von den ehrlichen Prüfern des zweiten Schritts empfangen werden müssen.12 Einmal Ist dies der Fall, lässt sich leicht sicherstellen, dass der Block letztendlich über das BA-Protokoll vereinbart wird Runde r ist die Standardrunde und enthält daher keine digitale Signatur von Qr−1. Aber Das System muss weitermachen und dafür braucht es einen Anführer für Runde r. Wenn dieser Anführer automatisch ist und offen ausgewählt, dann wird ihn der Widersacher trivial korrumpieren. Wenn es vom vorherigen ausgewählt wird Qr−1 über den gleichen Prozess, dann wird \(\ell\)r in Runde r+1 wieder der Anführer sein. Wir schlagen dies ausdrücklich vor Verwenden Sie denselben geheimen kryptografischen Sortiermechanismus, der jedoch auf eine neue Q-Menge angewendet wird: nämlich H(Qr−1, r). Dadurch, dass diese Menge die Ausgabe von H ist, wird garantiert, dass die Ausgabe zufällig ist. und indem r als zweite Eingabe von H einbezogen wird, während alle anderen Verwendungen von H eine oder mehr als drei Eingaben haben, „garantiert“, dass ein solcher Qr unabhängig ausgewählt wird. Auch hier ist unsere spezifische Wahl des alternativen Qr spielt keine Rolle, wichtig ist, dass \(\ell\)r zwei Möglichkeiten für Qr hat und somit seine Chancen verdoppeln kann einen anderen böswilligen Benutzer als nächsten Anführer zu haben. Die Optionen für Qr könnten für den Gegner, der einen böswilligen \(\ell\)r kontrolliert, sogar noch zahlreicher sein. Nehmen wir zum Beispiel an, x, y und z seien drei böswillige potenzielle Anführer der Runde r, so dass H \(\sigma\)r,1 x
< H \(\sigma\)r,1 j
< H \(\sigma\)r,1 z
und H  \(\sigma\)r,1 z  ist besonders klein. Das heißt, so klein, dass eine gute Chance besteht, dass H  \(\sigma\)r,1 z  ist kleiner als die hashed-Referenz eines jeden ehrlichen potenziellen Anführers. Dann, indem Sie x bitten, seine zu verstecken Aufgrund seiner Qualifikation hat der Gegner gute Chancen, dass er der Anführer der Runde r −1 wird. Dies impliziert, dass er eine andere Option für Qr hat: nämlich SIGy Qr−1 . Ebenso kann der Gegner Bitten Sie sowohl x als auch y, ihre Anmeldeinformationen zurückzuhalten, damit z der Anführer der Runde r −1 wird und eine weitere Option für Qr zu gewinnen: nämlich SIGz Qr−1 . Natürlich ist die Wahrscheinlichkeit, dass diese und andere Optionen scheitern, ungleich Null, denn die Der Gegner kann den hash der digitalen Signaturen der ehrlichen potenziellen Benutzer nicht vorhersagen. Br−1 ich = (r −1, PAY ′, H(Br−2). Ansonsten hat er zwei weitere böswillige Benutzer x und y, die immer wieder eine neue Zahlung generieren \(\wp\)′, von einem zum anderen, bis für einen böswilligen Benutzer z (oder sogar für einen festen Benutzer z) H (SIGz (PAY ′ \(\cup\){\(\wp\)})) ist auch besonders klein. Dieses Experiment wird ziemlich schnell enden. Und wenn das der Fall ist, bittet uns der Gegner, einen Vorschlag zu machen der Kandidatenblock Br−1 ich = (r −1, PAY ′ \(\cup\){\(\wp\)}, H(Br−2). 12Um es beispielsweise einfach (aber extrem) zu halten: „Wenn die Zeit des zweiten Schritts bald abläuft“, könnte \(\ell\)r Senden Sie jedem Benutzer i direkt einen anderen Kandidatenblock Bi per E-Mail. Auf diese Weise können sie, wer auch immer die Schritt-2-Prüfer sein mögen wird völlig unterschiedliche Blöcke erhalten haben.Eine sorgfältige, Markov-Ketten-ähnliche Analyse zeigt dies, egal welche Optionen der Gegner wählt Solange er in Runde r −1 keine neuen Benutzer in das System aufnehmen kann, kann er die nicht verringern Wahrscheinlichkeit, dass ein ehrlicher Benutzer der Anführer der Runde r + 40 ist, liegt deutlich unter h. Dies ist der Grund dafür Wir fordern, dass die potenziellen Anführer der Runde r Benutzer sind, die bereits in Runde r − k existieren. Auf diese Weise kann sichergestellt werden, dass der Gegner in der Runde r − k die Wahrscheinlichkeit nicht wesentlich ändern kann Ein ehrlicher Benutzer wird zum Anführer von Round R. Tatsächlich spielt es keine Rolle, welche Benutzer er dem hinzufügt System in den Runden r −k bis r, sind sie nicht berechtigt, potenzielle Anführer zu werden (und erst recht die Anführer) der Runde r. Somit ist der Lookback-Parameter k letztlich ein Sicherheitsparameter. (Obwohl, Wie wir in Abschnitt 7 sehen werden, kann es sich auch um eine Art „Bequemlichkeitsparameter“ handeln.) Vergängliche Schlüssel Obwohl die Ausführung unseres Protokolls keinen Fork generieren kann, außer mit Mit vernachlässigbarer Wahrscheinlichkeit könnte der Gegner am r-ten Block nach dem legitimen eine Abzweigung erzeugen Block r wurde generiert. Sobald Br generiert wurde, hat der Gegner ungefähr erfahren, wer die Prüfer für jeden Schritt ist der Runde r sind. Somit könnte er sie alle korrumpieren und sie dazu zwingen, einen neuen Block zu zertifizieren f Br. Da dieser gefälschte Block möglicherweise erst nach dem legitimen Block weitergegeben wird, haben Benutzer dies getan Aufmerksamkeit würde sich nicht täuschen lassen.13 Nichtsdestotrotz, f Br wäre syntaktisch korrekt und wir verhindern wollen, dass sie hergestellt werden. Dies tun wir mittels einer neuen Regelung. Im Wesentlichen legen die Mitglieder des Verifizierers SV r,s eines Schritts s fest der Runde r verwenden kurzlebige öffentliche Schlüssel pkr,s ich um ihre Nachrichten digital zu signieren. Diese Schlüssel sind nur für den einmaligen Gebrauch bestimmt und ihre entsprechenden geheimen Schlüssel sind skr,s ich werden nach Gebrauch zerstört. Auf diese Weise, wenn ein Verifizierer vorhanden ist Da er später korrumpiert wird, kann der Gegner ihn nicht zwingen, etwas anderes zu unterzeichnen, als er ursprünglich unterzeichnet hat. Natürlich müssen wir sicherstellen, dass es für den Gegner unmöglich ist, einen neuen Schlüssel g zu berechnen PR,S ich und einen ehrlichen Benutzer davon überzeugen, dass es der richtige ephemere Schlüssel des Verifizierers i \(\in\)SV r,s ist, der in Schritt s verwendet werden soll. 4.2 Allgemeine Zusammenfassung von Notationen, Begriffen und Parametern Notationen • r \(\geq\)0: die aktuelle Rundenzahl. • s \(\geq\)1: die aktuelle Schrittnummer in Runde r. • Br: der in Runde r erzeugte Block. • PKr: die Menge der öffentlichen Schlüssel am Ende der Runde r −1 und am Anfang der Runde r. • Sr: der Systemstatus am Ende der Runde r −1 und am Anfang der Runde r.14 • PAY r: der in Br enthaltene Payset. • \(\ell\)r: Rund-R-Anführer. \(\ell\)r wählt den Payset PAY r der Runde r (und bestimmt den nächsten Qr). • Qr: der Startwert der Runde r, eine Menge (d. h. eine binäre Zeichenfolge), die am Ende der Runde r generiert wird und wird verwendet, um Verifizierer für Runde r + 1 auszuwählen. Qr ist unabhängig von den Gehaltssätzen in den Blöcken und kann nicht von \(\ell\)r manipuliert werden. 13Denken Sie daran, den Nachrichtensprecher eines großen Fernsehsenders zu korrumpieren und heute eine Wochenschau zu produzieren und auszustrahlen zeigt, wie Außenministerin Clinton die letzten Präsidentschaftswahlen gewann. Die meisten von uns würden es als Scherz erkennen. Aber Jemand, der aus dem Koma erwacht, könnte getäuscht werden. 14In einem System, das nicht synchron ist, ist der Begriff „das Ende der Runde r −1“ und „der Anfang der Runde r“ müssen sorgfältig definiert werden. Mathematisch werden PKr und Sr aus dem Ausgangszustand S0 und den Blöcken berechnet B1, . . . , Br−1.• SV r,s: die Menge der Verifizierer, die für die Schritte s der Runde r ausgewählt wurden. • SV r: die Menge der für Runde r gewählten Verifizierer, SV r = \(\cup\)s\(\geq\)1SV r,s. • MSV r,s und HSV r,s: die Menge der böswilligen Verifizierer bzw. die Menge der ehrlichen Verifizierer in SV r,s. MSV r,s \(\cup\)HSV r,s = SV r,s und MSV r,s ∩HSV r,s = \(\emptyset\). • n1 \(\in\)Z+ und n \(\in\)Z+: jeweils die erwartete Anzahl potenzieller Anführer in jedem SV r,1, und die erwartete Anzahl von Verifizierern in jedem SV r,s, für s > 1. Beachten Sie, dass n1 << n, da wir mindestens ein ehrliches ehrliches Mitglied in SV r,1 benötigen, aber zumindest eine Mehrheit ehrlicher Mitglieder in jedem SV r,s für s > 1. • h \(\in\)(0, 1): eine Konstante größer als 2/3. h ist das Ehrlichkeitsverhältnis im System. Das heißt, die Der Bruchteil der ehrlichen Benutzer oder des ehrlichen Geldes, abhängig von der verwendeten Annahme, in jedem PKr zumindest h. • H: eine kryptografische hash-Funktion, modelliert als zufällige oracle. • \(\bot\): Eine spezielle Zeichenfolge mit der gleichen Länge wie die Ausgabe von H. • F \(\in\)(0, 1): der Parameter, der die zulässige Fehlerwahrscheinlichkeit angibt. Eine Wahrscheinlichkeit \(\leq\)F ist als „vernachlässigbar“ und eine Wahrscheinlichkeit \(\geq\)1 −F gilt als „überwältigend“. • ph \(\in\)(0, 1): die Wahrscheinlichkeit, dass der Anführer einer Runde r, \(\ell\)r, ehrlich ist. Idealerweise ist pH = h. Mit Sobald der Gegner existiert, wird der pH-Wert in der Analyse ermittelt. • k \(\in\)Z+: der Lookback-Parameter. Das heißt, in Runde r − k befinden sich die Verifizierer für Runde r ausgewählt aus – nämlich SV r \(\subseteq\)PKr−k.15 • p1 \(\in\)(0, 1): Für den ersten Schritt der Runde r wird ein Benutzer in Runde r −k ausgewählt, der im SV r,1 mit ist Wahrscheinlichkeit p1 \(\triangleq\) n1 |P Kr−k|. • p \(\in\)(0, 1): Für jeden Schritt s > 1 der Runde r wird ein Benutzer in Runde r −k ausgewählt, der im SV r,s mit ist Wahrscheinlichkeit p \(\triangleq\) n |P Kr−k|. • CERT r: das Zertifikat für Br. Es handelt sich um eine Reihe von Signaturen von H(Br) von geeigneten Prüfern in rund r. • Br \(\triangleq\)(Br, CERT r) ist ein bewährter Block. Ein Benutzer kennt Br, wenn er beide Teile des bewährten Blocks besitzt (und erfolgreich verifiziert). Beachten Sie, dass die von verschiedenen Benutzern angezeigten CERT-Werte unterschiedlich sein können. • τ r i: die (lokale) Zeit, zu der ein Benutzer Br kennt. Im Algorand-Protokoll hat jeder Benutzer sein eigenes eigene Uhr. Die Uhren verschiedener Benutzer müssen nicht synchronisiert sein, sondern müssen die gleiche Geschwindigkeit haben. Lediglich zum Zweck der Analyse betrachten wir eine Referenzuhr und messen die verwandte Zeiten in Bezug darauf. • \(\alpha\)r,s ich und \(\beta\)r,s i: jeweils die (lokale) Zeit, zu der ein Benutzer i seine Ausführung von Schritten beginnt und beendet rund r. • Λ und \(\lambda\): im Wesentlichen die Obergrenzen für die Zeit, die zum Ausführen von Schritt 1 bzw. benötigt wird die Zeit, die für jeden anderen Schritt des Algorand-Protokolls benötigt wird. Der Parameter Λ begrenzt die Zeit, die für die Ausbreitung eines einzelnen 1-MB-Blocks benötigt wird, nach oben. (In unserer Notation, Λ = \(\lambda\) \(\rho\),1MB. Erinnern wir uns an unsere Notation, dass wir der Einfachheit halber \(\rho\) = 1 setzen und dass Blöcke dies sind so gewählt, dass es höchstens 1 MB lang ist, gilt Λ = \(\lambda\)1,1,1 MB.) 15Genau genommen sollte „r −k“ „max{0, r −k}“ sein.Der Parameter \(\lambda\) begrenzt die Zeit zur Verbreitung einer kleinen Nachricht pro Verifizierer in einem Schritt s > 1. (Bei Verwendung von elliptischen Kurvensignaturen mit 32B Schlüsseln, wie in Bitcoin, ist eine Verifizierernachricht 200B lang. Somit ist in unserer Notation \(\lambda\) = \(\lambda\)n,\(\rho\),200B.) Wir gehen davon aus, dass Λ = O(\(\lambda\)). Vorstellungen • Prüferauswahl. Für jede Runde r und Schritt s > 1 gilt SV r,s \(\triangleq\){i \(\in\)PKr−k : .H(SIGi(r, s, Qr−1)) \(\leq\)p}. Jeder Benutzer i \(\in\)PKr−k berechnet privat seine Signatur unter Verwendung seines Langzeitschlüssels und entscheidet, ob i \(\in\)SV r,s oder nicht. Wenn i \(\in\)SV r,s, dann ist SIGi(r, s, Qr−1) der (r, s)-Berechtigungsnachweis von i, kompakt bezeichnet von \(\sigma\)r,s ich . Für den ersten Schritt der Runde r, SV r,1 und \(\sigma\)r,1 ich sind ähnlich definiert, wobei p durch p1 ersetzt wird. Die Verifizierer in SV r,1 sind potenzielle Führungskräfte. • Auswahl des Leiters. Benutzer i \(\in\)SV r,1 ist der Anführer der Runde r, bezeichnet mit \(\ell\)r, wenn H(\(\sigma\)r,1 i ) \(\leq\)H(\(\sigma\)r,1 j ) für alle Potentiale Leiter j \(\in\)SV r,1. Immer wenn die hashes der Referenzen zweier Spieler verglichen werden, ist das unwahrscheinlich Im Falle von Bindungen bricht das Protokoll Bindungen immer lexikographisch entsprechend der (langfristigen Öffentlichkeit) auf Schlüssel der potenziellen Führungskräfte. Per Definition ist der hash-Wert der Anmeldeinformationen des Spielers auch der kleinste unter allen Benutzern in PKr−k. Beachten Sie, dass ein potenzieller Anführer nicht privat entscheiden kann, ob er der Anführer ist oder nicht. ohne die Referenzen der anderen potenziellen Führungskräfte zu sehen. Da die hash-Werte zufällig einheitlich sind, existiert und ist \(\ell\)r immer, wenn SV r,1 nicht leer ist ehrlich mit Wahrscheinlichkeit mindestens h. Der Parameter n1 ist groß genug, um sicherzustellen, dass jeder SV r,1 ist mit überwältigender Wahrscheinlichkeit nicht leer. • Blockstruktur. Ein nicht leerer Block hat die Form Br = (r, PAY r, SIG\(\ell\)r(Qr−1), H(Br−1)) und ist ein leerer Block hat die Form Br ǫ = (r, \(\emptyset\), Qr−1, H(Br−1)). Beachten Sie, dass ein nicht leerer Block immer noch einen leeren Payset PAY r enthalten kann, wenn keine Zahlung erfolgt in dieser Runde oder wenn der Anführer böswillig ist. Ein nicht leerer Block impliziert jedoch, dass die Identität von \(\ell\)r, sein Ausweis \(\sigma\)r,1 \(\ell\)r und SIG\(\ell\)r(Qr−1) wurden alle rechtzeitig enthüllt. Das Protokoll garantiert Wenn der Anführer ehrlich ist, wird der Block mit überwältigender Wahrscheinlichkeit nicht leer sein. • Seed Qr. Wenn Br nicht leer ist, dann ist Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), andernfalls ist Qr \(\triangleq\)H(Qr−1, r). Parameter • Beziehungen zwischen verschiedenen Parametern. — Die Verifizierer und potenziellen Leiter der Runde r werden aus den Benutzern in PKr−k ausgewählt, wobei k so gewählt ist, dass der Gegner Qr−1 nicht in der Runde r −k −1 vorhersagen kann mit einer Wahrscheinlichkeit besser als F: Andernfalls kann er böswillige Benutzer einführen für Runde r − k, die alle potenzielle Anführer/Verifizierer in Runde r sein werden und erfolgreich sind

Einen böswilligen Anführer oder eine böswillige Mehrheit in SV r,s für einige Schritte zu haben, ist erwünscht von ihn. — Für Schritt 1 jeder Runde r wird n1 so gewählt, dass mit überwältigender Wahrscheinlichkeit SV r,1 ̸= \(\emptyset\). • Beispielhafte Auswahl wichtiger Parameter. — Die Ausgänge von H sind 256 Bit lang. — h = 80 %, n1 = 35. — Λ = 1 Minute und \(\lambda\) = 10 Sekunden. • Initialisierung des Protokolls. Das Protokoll beginnt zum Zeitpunkt 0 mit r = 0. Da es weder „B−1“ noch „CERT −1“ gibt, Syntaktisch ist B−1 ein öffentlicher Parameter, dessen dritte Komponente Q−1 und alle Benutzer angibt kenne B−1 zum Zeitpunkt 0.

Algorand ′

1 In diesem Abschnitt erstellen wir eine Version von Algorand ′, die unter der folgenden Annahme arbeitet. Annahme: Ehrliche Mehrheit der Benutzer: Mehr als 2/3 der Benutzer in jedem PKr sind ehrlich. In Abschnitt 8 zeigen wir, wie man die obige Annahme durch die gewünschte ehrliche Mehrheit ersetzt Geldannahme. 5.1 Zusätzliche Notationen und Parameter Notationen • m \(\in\)Z+: die maximale Anzahl von Schritten im binären BA-Protokoll, ein Vielfaches von 3. • Lr \(\leq\)m/3: eine Zufallsvariable, die die Anzahl der Bernoulli-Versuche darstellt, die erforderlich sind, um eine 1 zu sehen, wenn jeder Versuch 1 mit der Wahrscheinlichkeit ph ist 2 und es gibt höchstens m/3-Versuche. Wenn alle Versuche scheitern, dann Lr \(\triangleq\)m/3. Lr wird verwendet, um die Zeit, die zum Generieren des Blocks Br benötigt wird, nach oben zu begrenzen. • tH = 2n 3 + 1: die Anzahl der Signaturen, die in den Endbedingungen des Protokolls erforderlich sind. • CERT r: das Zertifikat für Br. Es handelt sich um eine Reihe von Signaturen von H(Br) von geeigneten Prüfern in rund r. Parameter • Beziehungen zwischen verschiedenen Parametern. — Für jeden Schritt s > 1 der Runde r wird n so gewählt, dass mit überwältigender Wahrscheinlichkeit |HSV r,s| > 2|MSV r,s| und |HSV r,s| + 4|MSV r,s| < 2n. Je näher der Wert von h an 1 liegt, desto kleiner muss n sein. Insbesondere verwenden wir (Varianten von) Chernoff-Grenzen, um sicherzustellen, dass die gewünschten Bedingungen mit überwältigender Wahrscheinlichkeit eintreten. — m wird so gewählt, dass mit überwältigender Wahrscheinlichkeit Lr < m/3 ist. • Beispielhafte Auswahl wichtiger Parameter. — F = 10−12. — n \(\approx\)1500, k = 40 und m = 180.5.2 Implementierung kurzlebiger Schlüssel in Algorand ′ 1 Wie bereits erwähnt, wünschen wir uns, dass ein Verifizierer i \(\in\)SV r,s seine Nachricht mr,s digital signiert ich Schritt s in Runde r, relativ zu einem kurzlebigen öffentlichen Schlüssel pkr,s i , unter Verwendung eines kurzlebigen geheimen Schlüssels skr,s ich das Er zerstört sofort nach dem Gebrauch. Wir brauchen daher eine effiziente Methode, um sicherzustellen, dass jeder Benutzer dies tun kann Überprüfen Sie, ob pkr,s ich ist in der Tat der Schlüssel, mit dem ich die Unterschrift von Herrn, S. überprüfen kann ich . Wir tun dies nach bestem Wissen und Gewissen unseres Wissens) neue Verwendung identitätsbasierter Signaturverfahren. Auf hoher Ebene generiert in einem solchen Schema eine zentrale Behörde A einen öffentlichen Hauptschlüssel, PMK, und einen entsprechenden geheimen Hauptschlüssel, SMK. Angesichts der Identität U eines Spielers U berechnet A: Über SMK wird ein geheimer Signaturschlüssel skU relativ zum öffentlichen Schlüssel U bereitgestellt und skU privat an ihn weitergegeben U. (Tatsächlich ist in einem identitätsbasierten digitalen Signaturschema der öffentliche Schlüssel eines Benutzers U U selbst!) Auf diese Weise zerstört A SMK, nachdem er die geheimen Schlüssel der Benutzer berechnet hat, die er aktivieren möchte Digitale Signaturen erstellen und keinen berechneten geheimen Schlüssel aufbewahren, dann ist U der Einzige, der dies tut kann Nachrichten relativ zum öffentlichen Schlüssel U digital signieren. Somit kann jeder, der „Us Namen“ kennt, kennt automatisch den öffentlichen Schlüssel von U und kann daher die Signaturen von U überprüfen (möglicherweise auch unter Verwendung des öffentlicher Hauptschlüssel PMK). In unserer Anwendung ist die Autorität A der Benutzer i, und die Menge aller möglichen Benutzer U stimmt mit überein das Rundschrittpaar (r, s) in — sagen wir — S = {i}\(\times\){r′, . . . , r′ +106}\(\times\){1, . . . , m+3}, wobei r′ gegeben ist Runde und m + 3 die Obergrenze für die Anzahl der Schritte, die innerhalb einer Runde auftreten dürfen. Dies Weg, pkr,s ich \(\triangleq\)(i, r, s), sodass jeder die Signatur von i sieht, SIGr,s pkr,s ich (Herr, S ich ) kann, mit Überwältigung Wahrscheinlichkeit, überprüfen Sie es sofort für die ersten Millionen Runden r nach r′. Mit anderen Worten: Ich erzeuge zunächst PMK und SMK. Dann macht er bekannt, dass PMK mein Meister ist öffentlichen Schlüssel für jede Runde r \(\in\)[r′, r′ + 106] und verwendet SMK, um das Geheimnis privat zu erzeugen und zu speichern Schlüssel skr,s ich für jedes Tripel (i, r, s) \(\in\)S. Wenn das erledigt ist, zerstört er SMK. Wenn er feststellt, dass dies nicht der Fall ist Teil von SV r,s, dann kann ich skr,s verlassen ich allein (da das Protokoll nicht verlangt, dass er sich authentifiziert jede Nachricht in Schritt s der Runde r). Ansonsten verwende ich zuerst skr,s ich seine Nachricht digital signieren mr,s ich , und zerstört dann skr,s ich . Beachten Sie, dass ich seinen ersten öffentlichen Hauptschlüssel veröffentlichen kann, wenn er das System zum ersten Mal betritt. Das heißt, Die gleiche Zahlung \(\wp\), die i in das System bringt (in einer Runde r′ oder in einer Runde nahe r′), kann auch Geben Sie auf Wunsch von i an, dass der öffentliche Hauptschlüssel von i für jede Runde r \(\in\)[r′, r′ + 106] PMK ist – z. B. by einschließlich eines Paares der Form (PMK, [r′, r′ + 106]). Beachten Sie auch, dass m + 3 die maximale Anzahl von Schritten in einer Runde ist, vorausgesetzt, dass eine Runde erfolgt dauert eine Minute, der so hergestellte Vorrat an kurzlebigen Schlüsseln reicht für fast zwei Jahre. Gleichzeitig Mit der Zeit wird die Herstellung dieser kurzlebigen Geheimschlüssel nicht allzu lange dauern. Unter Verwendung einer elliptischen Kurve Bei einem System mit 32B Schlüsseln wird jeder geheime Schlüssel in wenigen Mikrosekunden berechnet. Wenn also m + 3 = 180, Dann können alle 180 Millionen geheimen Schlüssel in weniger als einer Stunde berechnet werden. Wenn sich die aktuelle Runde r′ + 106 nähert, um die nächsten Millionen Runden zu bewältigen, d generiert ein neues (PMK′, SMK′)-Paar und informiert über seinen nächsten Vorrat an kurzlebigen Schlüsseln – zum Beispiel – mit SIGi(PMK′, [r′ + 106 + 1, r′ + 2 \(\cdot\) 106 + 1]) geben Sie einen neuen Block ein, entweder als separate „Transaktion“ oder als zusätzliche Information, die Teil einer Zahlung ist. Dadurch Ich informiere jeden darüber, dass er/sie im nächsten Schritt PMK′ verwenden soll, um die ephemeren Signaturen von i zu überprüfen Millionen Schuss. Und so weiter. (Beachten Sie, dass es nach diesem grundlegenden Ansatz auch andere Möglichkeiten gibt, ephemere Schlüssel ohne zu implementieren Der Einsatz identitätsbasierter Signaturen ist durchaus möglich. Zum Beispiel über Merkle trees.16) 16Bei dieser Methode generiert i ein öffentlich-geheimes Schlüsselpaar (pkr,s ich, skr,s ich ) für jedes Rundenschrittpaar (r, s) in — sagen wir —Andere Möglichkeiten zur Implementierung ephemerer Schlüssel sind sicherlich möglich – z. B. über Merkle trees. 5.3 Passend zu den Schritten von Algorand ′ 1 mit denen von BA⋆ Wie gesagt, eine Runde in Algorand ′ 1 hat höchstens m + 3 Schritte. Schritt 1. In diesem Schritt berechnet und propagiert jeder potenzielle Anführer i seinen Kandidatenblock Br ich, zusammen mit seinem eigenen Ausweis, \(\sigma\)r,1 ich . Denken Sie daran, dass dieser Berechtigungsnachweis i explizit identifiziert. Das ist so, weil \(\sigma\)r,1 ich \(\triangleq\)SIGi(r, 1, Qr−1). Der potenzielle Verifizierer verbreitet als Teil seiner Nachricht auch seine ordnungsgemäße digitale Signatur von H(Br.) ich). Da es sich bei dieser Signatur nicht um eine Zahlung oder einen Ausweis handelt, bezieht sie sich auf seine flüchtige Öffentlichkeit Schlüssel VE,1 i: das heißt, er propagiert sigpkr,1 ich (H(Br ich )). Angesichts unserer Konventionen, anstatt Br. zu propagieren ich und sigpkr,1 ich (H(Br i)), er hätte es tun können propagierte SIGpkr,1 ich (H(Br ich )). In unserer Analyse benötigen wir jedoch expliziten Zugriff darauf sigpkr,1 ich (H(Br ich )). Schritte 2. In diesem Schritt legt jeder Verifizierer \(\ell\)r fest Ich möchte der potenzielle Anführer sein, dessen Qualifikation hash ist ist der kleinste und Br i soll der von \(\ell\)r vorgeschlagene Block sein ich . Da wir aus Gründen der Effizienz Wenn er sich auf H(Br) und nicht direkt auf Br einigen möchte, propagiert er die Botschaft, die er haben möchte propagiert im ersten Schritt von BA⋆mit Anfangswert v′ i = H(Br ich). Das heißt, er propagiert v′ ich, natürlich erst nach kurzer Unterzeichnung. (Nämlich nach der Unterzeichnung relativ zum rechten Ephemeren Öffentlicher Schlüssel, in diesem Fall pkr,2 i .) Selbstverständlich übermittelt auch ich seinen eigenen Ausweis. Da der erste Schritt von BA⋆aus dem ersten Schritt des abgestuften Konsensprotokolls GC besteht, Schritt 2 von Algorand ′ entspricht dem ersten Schritt von GC. Schritte 3. In diesem Schritt führt jeder Prüfer i \(\in\)SV r,2 den zweiten Schritt von BA⋆ aus. Das heißt, er sendet die Dieselbe Nachricht, die er im zweiten Schritt von GC gesendet hätte. Auch hier ist meine Botschaft vergänglich unterschrieben und mit meinem Ausweis versehen. (Von nun an werden wir es unterlassen, zu sagen, dass es sich um einen Verifizierer handelt unterzeichnet flüchtig seine Nachricht und verbreitet auch seine Beglaubigung.) Schritt 4. In diesem Schritt berechnet jeder Verifizierer i \(\in\)SV r,4 die Ausgabe von GC (vi, gi) und ephemer signiert und sendet die gleiche Nachricht, die er im dritten Schritt von BA⋆ gesendet hätte, also im erster Schritt von BBA⋆, mit Anfangsbit 0, wenn gi = 2, andernfalls 1. Schritt s = 5, . . . , m + 2. Ein solcher Schritt, falls jemals erreicht, entspricht dem Schritt s −1 von BA⋆ und damit Schritt s −3 von BBA⋆. Da unser Ausbreitungsmodell ausreichend asynchron ist, müssen wir die Möglichkeit berücksichtigen dass mitten in einem solchen Schritt s ein Verifizierer i \(\in\)SV r,s durch Informationen erreicht wird, die ihn beweisen dieser Block Br wurde bereits ausgewählt. In diesem Fall stoppt i seine eigene Ausführung von Runde r Algorand ′ und beginnt mit der Ausführung seiner Round-(r + 1)-Anweisungen. {R', . . . , r′ + 106} \(\times\) {1, . . . , m + 3}. Dann ordnet er diese öffentlichen Schlüssel auf kanonische Weise an und speichert den J-ten öffentlich Geben Sie das j-te Blatt eines Merkle tree ein und berechnen Sie den Wurzelwert Ri, den er veröffentlicht. Wenn er unterschreiben will eine Nachricht relativ zum Schlüssel pkr,s ich , i stellt nicht nur die eigentliche Signatur bereit, sondern auch den Authentifizierungspfad für pkr,s ich relativ zu Ri. Beachten Sie, dass dieser Authentifizierungspfad auch beweist, dass pkr,s ich wird im j-ten Blatt gespeichert. Der Rest Details können einfach ausgefüllt werden.Dementsprechend sind die Anweisungen eines Verifizierers i \(\in\)SV r,s, zusätzlich zu den entsprechenden Anweisungen Zu Schritt s −3 von BBA⋆ gehört auch die Prüfung, ob die Ausführung von BBA⋆ in einem früheren Zustand angehalten wurde Schritt s′. Da BBA⋆nur anhalten kann, ist ein Coin-Fixed-to-0-Schritt oder ein Coin-Fixed-to-1-Schritt Anweisungen unterscheiden, ob A (Endbedingung 0): s′ −2 ≡0 mod 3, oder B (Endbedingung 1): s′ −2 ≡1 mod 3. Tatsächlich ist im Fall A der Block Br nicht leer und daher sind zusätzliche Anweisungen erforderlich Stellen Sie sicher, dass ich Br zusammen mit dem richtigen Zertifikat CERT r ordnungsgemäß rekonstruiere. Im Fall B, Der Block Br ist leer und daher wird i angewiesen, Br = Br zu setzen \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), und um CERT r zu berechnen. Wenn i während seiner Ausführung von Schritt s keine Hinweise darauf sieht, dass der Block Br bereits vorhanden ist generiert wurde, sendet er dieselbe Nachricht, die er in Schritt s −3 von BBA⋆ gesendet hätte. Schritt m + 3. Wenn i \(\in\)SV r,m+3 während Schritt m + 3 erkennt, dass der Block Br bereits in generiert wurde einen vorherigen Schritt s′, dann geht er genauso vor wie oben erklärt. Anstatt die gleiche Nachricht zu senden, die er in Schritt m von BBA⋆ gesendet hätte, ist i angewiesen, auf der Grundlage der in seinem Besitz befindlichen Informationen Br und dessen entsprechende Werte zu berechnen Zertifikat CERT r. Denken Sie daran, dass wir die Gesamtzahl der Schritte einer Runde um m + 3 nach oben begrenzen. 5.4 Das eigentliche Protokoll Denken Sie daran, dass in jedem Schritt s einer Runde r ein Verifizierer i \(\in\)SV r,s sein langfristiges öffentlich-geheimes Schlüsselpaar verwendet seinen Ausweis vorlegen, \(\sigma\)r,s ich \(\triangleq\)SIGi(r, s, Qr−1) sowie SIGi Qr−1 im Fall s = 1. Verifier i verwendet seinen kurzlebigen geheimen Schlüssel skr,s ich seine (r,s)-Nachricht unterschreiben mr,s ich . Der Einfachheit halber, wenn r und s sind klar, wir schreiben esigi(x) statt sigpkr,s i (x), um die eigentliche ephemere Signatur eines Wertes zu bezeichnen x in Schritt s der Runde r und schreibe ESIGi(x) anstelle von SIGpkr,s i (x) zur Bezeichnung von (i, x, esigi(x)). Schritt 1: Vorschlag blockieren Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seinen eigenen Schritt 1 der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,1 oder nicht. • Wenn i /\(\in\)SV r,1, stoppt i sofort seine eigene Ausführung von Schritt 1. • Wenn i \(\in\)SV r,1, das heißt, wenn i ein potenzieller Anführer ist, dann kassiert er die runden Zahlungen, die er hat wurde ihm bisher propagiert und berechnet einen maximalen Payset PAY r ich von ihnen. Als nächstes er berechnet seinen „Kandidatenblock“ Br i = (r, PAY r i , SIGi(Qr−1), H(Br−1)). Schließlich rechnet er die Nachricht Herr,1 ich = (Br ich, esigi(H(Br i )), \(\sigma\)r,1 i ), zerstört seinen ephemeren geheimen Schlüssel skr,1 ich, und dann propagiert mr,1 ich .Bemerkung. Um die globale Ausführung von Schritt 1 zu verkürzen, ist es in der Praxis wichtig, dass (r, 1)- Nachrichten werden selektiv verbreitet. Das heißt, für jeden Benutzer i im System gilt für den ersten (r, 1)- Die Nachricht, die er jemals erhält und erfolgreich verifiziert,17 verbreitet der Spieler wie gewohnt. Für alle Andere (r, 1)-Nachrichten, die Spieler i empfängt und erfolgreich verifiziert, er verbreitet sie nur, wenn die hash Der Wert der darin enthaltenen Anmeldeinformationen ist der kleinste unter den hash Werten der enthaltenen Anmeldeinformationen in allen (r, 1)-Nachrichten, die er bisher erhalten und erfolgreich verifiziert hat. Darüber hinaus, wie vorgeschlagen von Georgios Vlachos ist es nützlich, dass jeder potenzielle Anführer i auch seine Qualifikation \(\sigma\)r,1 propagiert ich separat: Diese kleinen Nachrichten verbreiten sich schneller als Blöcke und stellen eine rechtzeitige Ausbreitung des mr,1 sicher j’s wobei die enthaltenen Anmeldeinformationen kleine hash-Werte haben, während solche mit großen hash-Werten erstellt werden verschwinden schnell. Schritt 2: Der erste Schritt des Graded Consensus Protocol GC Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seinen eigenen Schritt 2 der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,2 oder nicht. • Wenn i /\(\in\)SV r,2, stoppt i sofort seine eigene Ausführung von Schritt 2. • Wenn i \(\in\)SV r,2, verhält sich i nach einer Wartezeit von t2 \(\triangleq\) \(\lambda\) + Λ wie folgt. 1. Er findet den Benutzer \(\ell\)so dass H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) für alle Referenzen \(\sigma\)r,1 j die Teil davon sind die erfolgreich verifizierten (r, 1)-Nachrichten, die er bisher erhalten hat.a 2. Wenn er von \(\ell\)eine gültige Nachricht erhalten hat, mr,1 \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),b dann setzt i v′ i \(\triangleq\)H(Br \(\ell\)); sonst setze ich v′ ich \(\triangleq\) \(\bot\). 3. i berechnet die Nachricht mr,2 ich \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),c zerstört seinen ephemeren Geheimschlüssel skr,2 i und propagiert dann mr,2 ich . aIm Wesentlichen entscheidet Benutzer i privat, dass der Anführer der Runde r Benutzer \(\ell\) ist. bAuch hier wurden die Unterschriften von Spieler \(\ell\) und die hashes alle erfolgreich verifiziert und ZAHLEN r \(\ell\)in Br \(\ell\)ist ein gültiger Gehaltssatz für rundes r – obwohl ich nicht prüfe, ob PAY r \(\ell\)ist maximal für \(\ell\)oder nicht. cDie Nachricht mr,2 ich signalisiert, dass der Spieler v′ betrachtet i sei der hash des nächsten Blocks oder betrachte den nächsten Block soll leer sein. 17Das heißt, alle Signaturen sind korrekt und sowohl der Block als auch sein hash sind gültig – obwohl ich das nicht prüfe ob der enthaltene Gehaltssatz für seinen Antragsteller maximal ist oder nicht.

Schritt 3: Der zweite Schritt der GC Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seinen eigenen Schritt 3 der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,3 oder nicht. • Wenn i /\(\in\)SV r,3, stoppt i sofort seine eigene Ausführung von Schritt 3. • Wenn i \(\in\)SV r,3, verhält sich i nach einer Wartezeit von t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ wie folgt. 1. Wenn es einen Wert v′ ̸= \(\bot\) gibt, so dass unter allen gültigen Nachrichten mr,2 j er hat erhalten, mehr als 2/3 davon haben die Form (ESIGj(v′), \(\sigma\)r,2 j ), ohne jeden Widerspruch,a dann berechnet er die Nachricht mr,3 ich \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 ich). Andernfalls berechnet er mr,3 ich \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 ich). 2. Ich zerstöre seinen kurzlebigen geheimen Schlüssel skr,3 i und propagiert dann mr,3 ich . aDas heißt, er hat keine zwei gültigen Nachrichten erhalten, die ESIGj(v′′) bzw. ein anderes ESIGj(v′′) enthalten. von einem Spieler j. Hier und von nun an, außer in den später definierten Endbedingungen, wann immer ein ehrlicher Spieler Will Nachrichten einer bestimmten Form, werden widersprüchliche Nachrichten niemals gezählt oder als gültig angesehen.Schritt 4: Ausgabe von GC und der erste Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seinen eigenen Schritt 4 der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,4 oder nicht. • Wenn i /\(\in\)SV r,4, dann stoppt i seine eigene Ausführung von Schritt 4 sofort. • Wenn i \(\in\)SV r,4, verhält sich i nach einer Wartezeit von t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ wie folgt. 1. Er berechnet vi und gi, die Ausgabe von GC, wie folgt. (a) Wenn es einen Wert v′ ̸= \(\bot\) gibt, so dass unter allen gültigen Nachrichten mr,3 j er hat empfangen, mehr als 2/3 davon haben die Form (ESIGj(v′), \(\sigma\)r,3 j ), dann setzt er vi \(\triangleq\)v′ und gi \(\triangleq\)2. (b) Andernfalls, wenn unter allen gültigen Nachrichten ein Wert v′ ̸= \(\bot\)existiert Herr,3 j er erhalten hat, haben mehr als 1/3 davon die Form (ESIGj(v′), \(\sigma\)r,3 j), dann er setzt vi \(\triangleq\)v′ und gi \(\triangleq\)1.a (c) Ansonsten setzt er vi \(\triangleq\)H(Br ǫ ) und gi \(\triangleq\)0. 2. Er berechnet bi, die Eingabe von BBA⋆, wie folgt: bi \(\triangleq\)0, wenn gi = 2, andernfalls bi \(\triangleq\)1. 3. Er berechnet die Nachricht mr,4 ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), zerstört sein Vergängliches geheimer Schlüssel skr,4 i und propagiert dann mr,4 ich . aEs kann bewiesen werden, dass das v′ im Fall (b), falls vorhanden, eindeutig sein muss.

Schritt s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: Ein Coin-Fixed-To-0-Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seine eigenen Schritte s der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,s. • Wenn i /\(\in\)SV r,s, stoppt i sofort seine eigene Ausführung von Schritt s. • Wenn i \(\in\)SV r,s, dann verhält er sich wie folgt. – Er wartet, bis eine Zeitspanne ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ verstrichen ist. – Endbedingung 0: Wenn während dieses Wartens und zu irgendeinem Zeitpunkt ein string v ̸= \(\bot\)und ein Schritt s′ so dass (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 – das heißt, Schritt s′ ist ein Coin-Fixed-To-0-Schritt, (b) Ich habe mindestens tH erhalten = 2n 3 + 1 gültige Nachrichten mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),a und (c) Ich habe eine gültige Nachricht mr,1 erhalten j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) mit v = H(Br j), dann stoppt i seine eigene Ausführung von Schritt s (und tatsächlich von Runde r) sofort ohne irgendetwas verbreiten; setzt Br = Br j ; und legt sein eigenes CERT r als Nachrichtenmenge fest mr,s′−1 j des Unterschritts (b).b – Endbedingung 1: Wenn während des Wartens und zu irgendeinem Zeitpunkt ein Schritt s′ so dass (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 – das heißt, Schritt s′ ist ein Coin-Fixed-To-1-Schritt, und (b’) i hat mindestens die gültigen Nachrichten mr,s′−1 erhalten j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),c dann stoppt i seine eigene Ausführung von Schritt s (und tatsächlich von Runde r) sofort ohne irgendetwas verbreiten; setzt Br = Br ǫ ; und legt sein eigenes CERT r als Nachrichtenmenge fest mr,s′−1 j des Teilschritts (b‘). – Andernfalls führt Benutzer i am Ende der Wartezeit Folgendes aus. Er setzt vi als Mehrheitsvotum der vjs in den zweiten Komponenten aller gültigen Stimmen mr,s−1 j ’s hat er erhalten. Er berechnet bi wie folgt. Wenn mehr als 2/3 aller gültigen mr,s−1 j ’s, die er erhalten hat, sind von der Form (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), dann setzt er bi \(\triangleq\)0. Andernfalls, wenn mehr als 2/3 aller gültigen mr,s−1 j ’s, die er erhalten hat, sind von der Form (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), dann setzt er bi \(\triangleq\)1. Andernfalls setzt er bi \(\triangleq\)0. Er berechnet die Nachricht mr,s ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), zerstört sein Vergängliches geheimer Schlüssel skr,s i , und dann propagiert mr,s ich . aEine solche Nachricht von Spieler j wird auch dann gezählt, wenn Spieler i auch eine Nachricht von j erhalten hat, der für 1 signiert. Ähnliches gilt für Endbedingung 1. Wie in der Analyse gezeigt, geschieht dies, um sicherzustellen, dass alle ehrlichen Benutzer Bescheid wissen Br innerhalb der Zeit \(\lambda\) voneinander. bUser i kennt jetzt Br und seine eigenen Rundenabschlüsse. Als allgemeiner Benutzer hilft er immer noch bei der Verbreitung von Nachrichten, aber initiiert keine Ausbreitung als (r, s)-Verifizierer. Insbesondere hat er dazu beigetragen, alle in ihm enthaltenen Botschaften zu verbreiten CERT r, was für unser Protokoll ausreicht. Beachten Sie, dass er auch für das binäre BA-Protokoll bi \(\triangleq\)0 festlegen sollte, aber bi wird in diesem Fall ohnehin nicht benötigt. Ähnliches gilt für alle zukünftigen Anweisungen. cIn diesem Fall spielt es keine Rolle, um welche VJs es sich handelt.Schritt s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: Ein Coin-Fixed-To-1-Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seine eigenen Schritte s der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,s oder nicht. • Wenn i /\(\in\)SV r,s, stoppt i sofort seine eigene Ausführung von Schritt s. • Wenn i \(\in\)SV r,s, dann macht er Folgendes. – Er wartet, bis eine Zeitspanne ts \(\triangleq\)(2s −3)\(\lambda\) + Λ verstrichen ist. – Endbedingung 0: Die gleichen Anweisungen wie bei den Schritten „Coin-Fixed-To-0“. – Endbedingung 1: Die gleichen Anweisungen wie bei den Schritten „Coin-Fixed-To-0“. – Andernfalls führt Benutzer i am Ende der Wartezeit Folgendes aus. Er setzt vi als Mehrheitsvotum der vjs in den zweiten Komponenten aller gültigen Stimmen mr,s−1 j ’s hat er erhalten. Er berechnet bi wie folgt. Wenn mehr als 2/3 aller gültigen mr,s−1 j ’s, die er erhalten hat, sind von der Form (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), dann setzt er bi \(\triangleq\)0. Andernfalls, wenn mehr als 2/3 aller gültigen mr,s−1 j ’s, die er erhalten hat, sind von der Form (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), dann setzt er bi \(\triangleq\)1. Andernfalls setzt er bi \(\triangleq\)1. Er berechnet die Nachricht mr,s ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), zerstört sein Vergängliches geheimer Schlüssel skr,s i , und dann propagiert mr,s ich .

Schritt s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Ein münzecht umgedrehter Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seine eigenen Schritte s der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,s oder nicht. • Wenn i /\(\in\)SV r,s, stoppt i sofort seine eigene Ausführung von Schritt s. • Wenn i \(\in\)SV r,s, dann macht er Folgendes. – Er wartet, bis eine Zeitspanne ts \(\triangleq\)(2s −3)\(\lambda\) + Λ verstrichen ist. – Endbedingung 0: Die gleichen Anweisungen wie bei den Schritten „Coin-Fixed-To-0“. – Endbedingung 1: Die gleichen Anweisungen wie bei den Schritten „Coin-Fixed-To-0“. – Andernfalls führt Benutzer i am Ende der Wartezeit Folgendes aus. Er setzt vi als Mehrheitsvotum der vjs in den zweiten Komponenten aller gültigen Stimmen mr,s−1 j ’s hat er erhalten. Er berechnet bi wie folgt. Wenn mehr als 2/3 aller gültigen mr,s−1 j ’s, die er erhalten hat, sind von der Form (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), dann setzt er bi \(\triangleq\)0. Andernfalls, wenn mehr als 2/3 aller gültigen mr,s−1 j ’s, die er erhalten hat, sind von der Form (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), dann setzt er bi \(\triangleq\)1. Ansonsten sei SV r,s−1 ich sei die Menge der (r, s −1)-Verifizierer, von denen er ein gültiges erhalten hat Nachricht mr,s−1 j . Er setzt bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 ich H(\(\sigma\)r,s−1 j )). Er berechnet die Nachricht mr,s ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), zerstört sein Vergängliches geheimer Schlüssel skr,s i , und dann propagiert mr,s ich .

Schritt m + 3: Der letzte Schritt von BBA⋆a Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seinen eigenen Schritt m + 3 der Runde r, sobald er kennt Br−1. • Benutzer i berechnet Qr−1 aus der dritten Komponente von Br−1 und prüft, ob i \(\in\)SV r,m+3 oder nicht. • Wenn i /\(\in\)SV r,m+3, dann stoppt i sofort seine eigene Ausführung von Schritt m + 3. • Wenn i \(\in\)SV r,m+3, dann macht er Folgendes. – Er wartet, bis eine Zeitspanne tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ vergangen ist. – Endbedingung 0: Die gleichen Anweisungen wie bei den Schritten „Coin-Fixed-To-0“. – Endbedingung 1: Die gleichen Anweisungen wie bei den Schritten „Coin-Fixed-To-0“. – Andernfalls führt Benutzer i am Ende der Wartezeit Folgendes aus. Er stellt i \(\triangleq\)1 und Br \(\triangleq\)Br dar ǫ. Er berechnet die Nachricht mr,m+3 ich = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 ich ), zerstört seine Vergänglicher geheimer Schlüssel skr,m+3 ich , und propagiert dann mr,m+3 ich Br.b. zertifizieren aMit überwältigender Wahrscheinlichkeit ist BBA⋆vor diesem Schritt beendet, und wir geben diesen Schritt der Vollständigkeit halber an. Ein BA-Zertifikat aus Schritt m + 3 muss ESIGi(outi) nicht enthalten. Wir schließen es nur aus Gründen der Einheitlichkeit ein: das Zertifikate haben nun ein einheitliches Format, unabhängig davon, in welchem Schritt sie generiert werden.Rekonstruktion des Round-r-Blocks durch Nicht-Verifizierer Anleitung für jeden Benutzer i im System: Benutzer i startet seine eigene Runde, sobald er es weiß Br−1 und wartet wie folgt auf Blockinformationen. – Wenn während dieses Wartens und zu irgendeinem Zeitpunkt eine Zeichenfolge v und ein Schritt s′ wie z das (a) 5 \(\leq\)s′ \(\leq\)m + 3 mit s′ −2 ≡0 mod 3, (b) i hat mindestens die gültigen Nachrichten mr,s′−1 erhalten j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ), und (c) Ich habe eine gültige Nachricht mr,1 erhalten j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) mit v = H(Br j), dann stoppt i sofort seine eigene Ausführung von Runde r; setzt Br = Br j; und legt sein eigenes CERT r fest die Menge der Nachrichten mr,s′−1 sein j des Unterschritts (b). – Wenn während dieses Wartens und zu irgendeinem Zeitpunkt ein Schritt s′ existiert, so dass (a’) 6 \(\leq\)s′ \(\leq\)m + 3 mit s′ −2 ≡1 mod 3, und (b’) i hat mindestens die gültigen Nachrichten mr,s′−1 erhalten j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ), dann stoppt i sofort seine eigene Ausführung von Runde r; setzt Br = Br ǫ; und legt sein eigenes CERT r fest die Menge der Nachrichten mr,s′−1 sein j des Teilschritts (b‘). – Wenn ich während dieser Wartezeit und zu irgendeinem Zeitpunkt mindestens die gültigen Nachrichten erhalten habe Herr,m+3 j = (ESIGj(1), ESIGj(H(Br ǫ )), \(\sigma\)r,m+3 j ), dann stoppt i seine eigene Ausführung der Runde r setzt sofort Br = Br ǫ und setzt sein eigenes CERT r auf die Menge der Nachrichten mr,m+3 j für 1 und H(Br ǫ ). 5.5 Analyse von Algorand ′ 1 Wir führen die folgenden Notationen für jede Runde r \(\geq\)0 ein, die in der Analyse verwendet wird. • Sei T r der Zeitpunkt, zu dem der erste ehrliche Benutzer Br−1 kennt. • Sei Ir+1 das Intervall [T r+1, T r+1 + \(\lambda\)]. Beachten Sie, dass T 0 = 0 durch die Initialisierung des Protokolls. Erinnern Sie sich daran für jedes s \(\geq\)1 und i \(\in\)SV r,s \(\alpha\)r,s ich und \(\beta\)r,s ich sind jeweils die Startzeit und die Endzeit der Schritte s von Spieler i. Darüber hinaus Denken Sie daran, dass ts = (2s −3)\(\lambda\) + Λ für jedes 2 \(\leq\)s \(\leq\)m + 3. Außerdem seien I0 \(\triangleq\){0} und t1 \(\triangleq\)0. Denken Sie abschließend daran, dass Lr \(\leq\)m/3 eine Zufallsvariable ist, die die Anzahl der Bernoulli-Versuche darstellt benötigt, um eine 1 zu sehen, wenn jeder Versuch 1 mit der Wahrscheinlichkeit ph ist 2 und es gibt höchstens m/3-Versuche. Wenn alle Versuche scheitern, dann ist Lr \(\triangleq\)m/3. Bei der Analyse ignorieren wir die Rechenzeit, da sie im Verhältnis zur benötigten Zeit tatsächlich vernachlässigbar ist um Nachrichten zu verbreiten. In jedem Fall kann die Berechnungszeit durch die Verwendung etwas größerer \(\lambda\) und Λ verkürzt werden direkt in die Analyse einfließen. Die meisten der folgenden Aussagen treffen „mit überwältigender Mehrheit“ zu Wahrscheinlichkeit“, und wir betonen diese Tatsache möglicherweise nicht wiederholt in der Analyse.5.6 Hauptsatz Satz 5.1. Die folgenden Eigenschaften gelten mit überwältigender Wahrscheinlichkeit für jede Runde r \(\geq\)0: 1. Alle ehrlichen Benutzer stimmen dem gleichen Block zu, Br. 2. Wenn der Anführer \(\ell\)r ehrlich ist, wird der Block Br von \(\ell\)r erzeugt, Br enthält einen maximalen Payset empfangen von \(\ell\)r bis zur Zeit \(\alpha\)r,1 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ und alle ehrlichen Benutzer kennen Br in der Zeit Intervall Ir+1. 3. Wenn der Anführer \(\ell\)r böswillig ist, gilt T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ und alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1. 4. ph = h2(1 + h −h2) für Lr, und der Anführer \(\ell\)r ist mit einer Wahrscheinlichkeit von mindestens ph ehrlich. Bevor wir unseren Hauptsatz beweisen, machen wir zwei Bemerkungen. Bemerkungen. • Blockgenerierung und echte Latenz. Die Zeit zum Erzeugen des Blocks Br ist als T r+1 − T r definiert. Das heißt, es ist definiert als der Unterschied zwischen dem ersten Mal, wenn ein ehrlicher Benutzer Br lernt, und Das erste Mal lernt ein ehrlicher Benutzer Br−1. Wenn der Round-R-Anführer ehrlich ist, ist Eigentum 2 unser Der Hauptsatz garantiert, dass die genaue Zeit zur Erzeugung von Br 8\(\lambda\) + Λ Zeit beträgt, egal was passiert Der genaue Wert von h > 2/3 kann sein. Wenn der Anführer böswillig ist, impliziert Eigenschaft 3, dass der Die erwartete Zeit zur Erzeugung von Br ist durch ( 12) begrenzt ph + 10)\(\lambda\) + Λ, wiederum unabhängig von der Genauigkeit Wert von h.18 Allerdings hängt die erwartete Zeit zur Erzeugung von Br vom genauen Wert von h ab. Tatsächlich ist nach Eigenschaft 4 ph = h2(1 + h − h2) und der Anführer ist zumindest in Bezug auf die Wahrscheinlichkeit ehrlich ph, also 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\) + Λ). Wenn beispielsweise h = 80 %, dann ist E[T r+1 −T r] \(\leq\)12,7\(\lambda\) + Λ. • \(\lambda\) vs. Λ. Beachten Sie, dass die Größe der von den Verifizierern in einem Schritt gesendeten Nachrichten Algorand ′ dominiert durch die Länge der digitalen Signaturschlüssel, die auch bei der Anzahl der Schlüssel fest bleiben kann Benutzer ist enorm. Beachten Sie außerdem, dass in jedem Schritt s > 1 die gleiche erwartete Anzahl n von Verifizierern erwartet wird kann unabhängig davon verwendet werden, ob die Anzahl der Benutzer 100.000, 100 Millionen oder 100 Millionen beträgt. Das liegt daran, dass n allein hängt von h und F ab. Zusammenfassend lässt sich sagen, dass, sofern nicht plötzlich die Notwendigkeit besteht, die Länge des geheimen Schlüssels zu erhöhen, Der Wert von \(\lambda\) sollte derselbe bleiben, egal wie groß die Anzahl der Benutzer ist absehbare Zukunft. Im Gegensatz dazu wächst bei jeder Transaktionsrate die Anzahl der Transaktionen mit der Anzahl der Transaktionen Benutzer. Um alle neuen Transaktionen zeitnah verarbeiten zu können, sollte daher die Größe eines Blocks erforderlich sein wachsen auch mit der Anzahl der Benutzer, wodurch auch Λ wächst. Auf lange Sicht hätten wir das also tun sollen \(\lambda\) << Λ. Dementsprechend ist es angemessen, einen größeren Koeffizienten für \(\lambda\) zu haben, und zwar tatsächlich einen Koeffizienten von 1 für Λ. Beweis von Satz 5.1. Wir beweisen die Eigenschaften 1–3 durch Induktion: unter der Annahme, dass sie für die Runde r −1 gelten (Ohne Beschränkung der Allgemeinheit gelten sie automatisch für „Runde -1“, wenn r = 0), wir beweisen sie für rund r. 18Tatsächlich ist E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ.Da Br−1 durch die Induktionshypothese eindeutig definiert ist, ist auch die Menge SV r,s eindeutig definiert für jeden Schritt s der Runde r. Durch die Wahl von n1 ist SV r,1 ̸= \(\emptyset\)mit überwältigender Wahrscheinlichkeit. Wir jetzt Geben Sie die folgenden zwei Lemmata an, die in den Abschnitten 5.7 und 5.8 bewiesen wurden. Während der Induktion und in die Beweise der beiden Lemmata, die Analyse für Runde 0 ist fast die gleiche wie der Induktionsschritt, und wir werden die Unterschiede hervorheben, wenn sie auftreten. Lemma 5.2. [Vollständigkeitslemma] Angenommen, die Eigenschaften 1–3 gelten für Runde r−1, wenn der Anführer \(\ell\)r ist ehrlich, mit überwältigender Wahrscheinlichkeit, • Alle ehrlichen Benutzer stimmen dem gleichen Block Br zu, der von \(\ell\)r erzeugt wird und ein Maximum enthält Gehaltssatz, den \(\ell\)r zum Zeitpunkt \(\alpha\)r,1 erhalten hat \(\ell\)r \(\in\)Ir; und • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ und alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1. Lemma 5.3. [Gesundheits-Lemma] Angenommen, die Eigenschaften 1–3 gelten für Runde r −1, wenn der Anführer \(\ell\)r ist bösartig, mit überwältigender Wahrscheinlichkeit sind sich alle ehrlichen Benutzer auf denselben Block Br, T r+1 \(\leq\) einig T r + (6Lr + 10)\(\lambda\) + Λ und alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1. Die Eigenschaften 1–3 gelten durch Anwendung der Lemmata 5.2 und 5.3 auf r = 0 und auf den Induktionsschritt. Schließlich, Wir formulieren Eigenschaft 4 als das folgende Lemma, das in Abschnitt 5.9 bewiesen wurde. Lemma 5.4. Gegeben sind die Eigenschaften 1–3 für jede Runde vor r, ph = h2(1 + h −h2) für Lr und die Anführer \(\ell\)r ist mit Wahrscheinlichkeit mindestens ph ehrlich. Kombiniert man die oben genannten drei Lemmata miteinander, gilt Satz 5.1. ■ Das folgende Lemma gibt mehrere wichtige Eigenschaften der Runde r bei gegebener Induktivität an Hypothese und wird in den Beweisen der oben genannten drei Lemmata verwendet. Lemma 5.5. Gehen Sie davon aus, dass die Eigenschaften 1–3 für Runde r −1 gelten. Für jeden Schritt s \(\geq\)1 der Runde r und Jeder ehrliche Verifizierer i \(\in\)HSV r,s, das haben wir (a) \(\alpha\)r,s ich \(\in\)Ir; (b) wenn Spieler i eine Zeitspanne ts gewartet hat, dann \(\beta\)r,s ich \(\in\)[T r + ts, T r + \(\lambda\) + ts] für r > 0 und \(\beta\)r,s ich = ts für r = 0; und (c) Wenn Spieler i eine Zeitspanne ts gewartet hat, dann nach der Zeit \(\beta\)r,s i , er hat alle Nachrichten erhalten gesendet von allen ehrlichen Verifizierern j \(\in\)HSV r,s′ für alle Schritte s′ < s. Darüber hinaus haben wir das für jeden Schritt s \(\geq\)3 (d) es gibt keine zwei verschiedenen Spieler i, i′ \(\in\)SV r,s und zwei verschiedene Werte v, v′ derselben Länge, so dass beide Spieler eine Zeitspanne ts gewartet haben, mehr als 2/3 aller gültige Nachrichten mr,s−1 j Spieler, den ich erhalte, haben für v unterschrieben, und mehr als 2/3 aller gültigen Nachrichten mr,s−1 j Spieler i′ erhält, hat für v′ unterschrieben. Nachweisen. Eigenschaft (a) folgt direkt aus der Induktionshypothese, da Spieler i Br−1 im kennt Zeitintervall Ir und beginnt sofort mit seinen eigenen Schritten. Eigenschaft (b) folgt direkt aus (a): da Spieler i hat eine gewisse Zeit ts gewartet, bevor er gehandelt hat, \(\beta\)r,s ich = \(\alpha\)r,s ich + ts. Beachten Sie, dass \(\alpha\)r,s ich = 0 für r = 0. Wir beweisen nun Eigenschaft (c). Wenn s = 2, dann gilt nach Eigenschaft (b) für alle Verifizierer j \(\in\)HSV r,1 \(\beta\)r,s ich = \(\alpha\)r,s ich + ts \(\geq\)T r + ts = T r + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 j + Λ.Da jeder Prüfer j \(\in\)HSV r,1 seine Nachricht zum Zeitpunkt \(\beta\)r,1 sendet j und die Botschaft erreicht alle ehrlich Benutzer in höchstens Λ Zeit, nach Zeit \(\beta\)r,s ich Player Ich habe die von allen Verifizierern gesendeten Nachrichten erhalten HSV r,1 nach Wunsch. Wenn s > 2, dann ist ts = ts−1 + 2\(\lambda\). Nach Eigenschaft (b) gilt für alle Schritte s′ < s und alle Verifizierer j \(\in\)HSV r,s′, \(\beta\)r,s ich = \(\alpha\)r,s ich + 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\). Da jeder Prüfer j \(\in\)HSV r,s′ seine Nachricht zum Zeitpunkt \(\beta\)r,s′ sendet j und die Botschaft erreicht alle ehrlich Benutzer in höchstens \(\lambda\) Zeit, nach Zeit \(\beta\)r,s ich Spieler, ich habe alle Nachrichten erhalten, die von allen ehrlichen Prüfern gesendet wurden im HSV r,s′ für alle s′ < s. Somit gilt Eigenschaft (c). Abschließend beweisen wir Eigenschaft (d). Beachten Sie, dass die Verifizierer j \(\in\)SV r,s−1 höchstens zwei Dinge unterschreiben Schritt s −1 unter Verwendung ihrer ephemeren geheimen Schlüssel: ein Wert vj mit der gleichen Länge wie die Ausgabe des hash-Funktion und auch ein Bit bj \(\in\){0, 1}, wenn s −1 \(\geq\)4. Deshalb in der Aussage des Lemmas wir erfordern, dass v und v′ die gleiche Länge haben: Viele Prüfer haben möglicherweise beide einen hash-Wert signiert v und ein Bit b, also überschreiten beide die 2/3-Schwelle. Nehmen Sie aus Gründen der Widersprüchlichkeit an, dass es die gewünschten Verifizierer i, i′ und die Werte v, v′ gibt. Beachten Sie, dass einige böswillige Verifizierer in MSV r,s−1 möglicherweise sowohl v als auch v′ signiert haben, aber alle ehrlich Prüfer im HSV r,s−1 hat höchstens einen davon unterzeichnet. Nach Eigenschaft (c) haben sowohl i als auch i′ erhalten Alle Nachrichten, die von allen ehrlichen Verifizierern im HSV r,s−1 gesendet werden. Sei HSV r,s−1(v) die Menge der ehrlichen (r, s −1)-Verifizierer, die v signiert haben, MSV r,s−1 ich das Set von böswilligen (r, s −1)-Verifizierern, von denen ich eine gültige Nachricht erhalten habe, und MSV r,s−1 ich (v) die Teilmenge von MSV r,s−1 ich Von wem ich eine gültige Nachrichtensignatur erhalten habe v. Durch die Anforderungen für i und v, wir haben Verhältnis \(\triangleq\)|HSV r,s−1(v)| + |MSV r,s−1 ich (v)| |HSV r,s−1| + |MSV r,s−1 ich |

2 3. (1) Wir zeigen zuerst |MSV r,s−1 ich (v)| \(\leq\)|HSV r,s−1(v)|. (2) Wenn man aufgrund der Beziehungen zwischen den Parametern mit überwältigender Wahrscheinlichkeit etwas anderes annimmt |HSV r,s−1| > 2|MSV r,s−1| \(\geq\)2|MSV r,s−1 ich |, also Verhältnis < |HSV r,s−1(v)| + |MSV r,s−1 ich (v)| 3|MSV r,s−1 ich | < 2|MSV r,s−1 ich (v)| 3|MSV r,s−1 ich | \(\leq\)2 3, widersprüchliche Ungleichung 1. Als nächstes haben wir nach Ungleichung 1 2|HSV r,s−1| + 2|MSV r,s−1 ich | < 3|HSV r,s−1(v)| + 3|MSV r,s−1 ich (v)| \(\leq\) 3|HSV r,s−1(v)| + 2|MSV r,s−1 ich | + |MSV r,s−1 ich (v)|. In Kombination mit Ungleichung 2, 2|HSV r,s−1| < 3|HSV r,s−1(v)| + |MSV r,s−1 ich (v)| \(\leq\)4|HSV r,s−1(v)|, was impliziert |HSV r,s−1(v)| > 1 2|HSV r,s−1|.In ähnlicher Weise gilt aufgrund der Anforderungen für i′ und v′ |HSV r,s−1(v′)| > 1 2|HSV r,s−1|. Da ein ehrlicher Verifizierer j \(\in\)HSV r,s−1 seinen ephemeren geheimen Schlüssel skr,s−1 zerstört j vor der Vermehrung In seiner Botschaft kann der Gegner die Signatur von j nicht für einen Wert fälschen, den j nicht signiert hat lernen, dass j ein Verifizierer ist. Somit implizieren die beiden obigen Ungleichungen |HSV r,s−1| \(\geq\)|HSV r,s−1(v)| + |HSV r,s−1(v′)| > |HSV r,s−1|, ein Widerspruch. Dementsprechend existieren die gewünschten i, i′, v, v′ nicht, und Eigenschaft (d) gilt. ■ 5.7 Das Vollständigkeitslemma Lemma 5.2. [Vollständigkeitslemma, angepasst] Unter der Annahme, dass die Eigenschaften 1–3 für Runde r−1 gelten, wenn der Anführer ist mit überwältigender Wahrscheinlichkeit ehrlich, • Alle ehrlichen Benutzer stimmen dem gleichen Block Br zu, der von \(\ell\)r erzeugt wird und ein Maximum enthält Gehaltssatz, den \(\ell\)r zum Zeitpunkt \(\alpha\)r,1 erhalten hat \(\ell\)r \(\in\)Ir; und • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ und alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1. Nachweisen. Nach der Induktionshypothese und Lemma 5.5 gilt für jeden Schritt s und Verifizierer i \(\in\)HSV r,s, \(\alpha\)r,s ich \(\in\)Ir. Nachfolgend analysieren wir das Protokoll Schritt für Schritt. Schritt 1. Per Definition verbreitet jeder ehrliche Verifizierer i \(\in\)HSV r,1 die gewünschte Nachricht mr,1 ich bei Zeit \(\beta\)r,1 ich = \(\alpha\)r,1 ich, wo Herr,1 ich = (Br ich, esigi(H(Br i )), \(\sigma\)r,1 ich), Br i = (r, PAY r i , SIGi(Qr−1), H(Br−1)), und ZAHLEN r i ist eine maximale Auszahlungsmenge aller Zahlungen, die ich bis zum Zeitpunkt \(\alpha\)r,1 gesehen habe ich . Schritt 2. Legen Sie willkürlich einen ehrlichen Verifizierer i \(\in\)HSV r,2 fest. Nach Lemma 5.5, wenn Spieler i fertig ist Warten zum Zeitpunkt \(\beta\)r,2 ich = \(\alpha\)r,2 ich + t2 hat er alle von Verifizierern in HSV r,1 gesendeten Nachrichten erhalten, einschließlich Herr,1 \(\ell\)r . Nach der Definition von \(\ell\)r gibt es in PKr−k keinen anderen Spieler, dessen Anmeldeinformationen hash sind. Wert ist kleiner als H(\(\sigma\)r,1 \(\ell\)r ). Natürlich kann der Gegner \(\ell\)r korrumpieren, nachdem er gesehen hat, dass H(\(\sigma\)r,1 \(\ell\)r ) ist sehr klein, aber zu diesem Zeitpunkt hat Spieler \(\ell\)r seinen kurzlebigen Schlüssel und die Nachricht mr,1 zerstört \(\ell\)r wurde propagiert. Daher setzt der Verifizierer seinen eigenen Anführer als Spieler \(\ell\)r. Dementsprechend zum Zeitpunkt \(\beta\)r,2 ich, Verifizierer propagiert mr,2 ich = (ESIGi(v′ i), \(\sigma\)r,2 i), wobei v′ i = H(Br \(\ell\)r). Wenn r = 0, der einzige Unterschied ist das \(\beta\)r,2 ich = t2 anstatt in einem Bereich zu liegen. Ähnliches lässt sich für zukünftige Schritte und uns sagen Ich werde sie nicht noch einmal betonen. Schritt 3. Legen Sie willkürlich einen ehrlichen Verifizierer i \(\in\)HSV r,3 fest. Nach Lemma 5.5, wenn Spieler i fertig ist Warten zum Zeitpunkt \(\beta\)r,3 ich = \(\alpha\)r,3 ich + t3 hat er alle von Verifizierern in HSV r,2 gesendeten Nachrichten erhalten. Aufgrund der Beziehungen zwischen den Parametern mit überwältigender Wahrscheinlichkeit |HSV r,2| > 2|MSV r,2|. Darüber hinaus würde kein ehrlicher Prüfer widersprüchliche Botschaften unterzeichnen, und zwar den Widersacher Die Unterschrift eines ehrlichen Prüfers kann nicht gefälscht werden, nachdem dieser seine Korrespondenz vernichtet hat vergänglicher geheimer Schlüssel. Somit stammen mehr als 2/3 aller gültigen (r, 2)-Nachrichten, die ich erhalten habe, von ehrliche Prüfer und der Form mr,2 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,2 j ), ohne Widerspruch. Dementsprechend zum Zeitpunkt \(\beta\)r,3 ich Spieler, den ich mr,3 propagiere ich = (ESIGi(v′), \(\sigma\)r,3 i ), wobei v′ = H(Br \(\ell\)r).Schritt 4. Bestimmen Sie willkürlich einen ehrlichen Verifizierer i \(\in\)HSV r,4. Nach Lemma 5.5 hat Spieler i alles erhalten Nachrichten, die von Verifizierern in HSV r,3 gesendet werden, wenn er zum Zeitpunkt \(\beta\)r,4 mit dem Warten fertig ist ich = \(\alpha\)r,4 ich + t4. Ähnlich wie Schritt 3: Mehr als 2/3 aller gültigen (r, 3)-Nachrichten, die ich erhalten habe, stammen von ehrlichen Verifizierern und der Form mr,3 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,3 j). Dementsprechend setzt Spieler i vi = H(Br \(\ell\)r), gi = 2 und bi = 0. Zum Zeitpunkt \(\beta\)r,4 ich = \(\alpha\)r,4 ich +t4 propagiert er Herr,4 ich = (ESIGi(0), ESIGi(H(Br \(\ell\)r)), \(\sigma\)r,4 ich). Schritt 5. Legen Sie willkürlich einen ehrlichen Verifizierer i \(\in\)HSV r,5 fest. Nach Lemma 5.5 hätte Spieler ich hat alle von den Verifizierern in HSV r,4 gesendeten Nachrichten erhalten, wenn er bis zum Zeitpunkt \(\alpha\)r,5 gewartet hat ich + t5. Beachten Sie das |HSV r,4| \(\geq\)tH.19 Beachten Sie außerdem, dass alle Prüfer in HSV r,4 für H(Br.) unterschrieben haben \(\ell\)r). Als |MSV r,4| < tH, es existiert kein v′ ̸= H(Br \(\ell\)r), die von tH hätte unterzeichnet werden können Verifizierer in SV r,4 (die notwendigerweise böswillig wären), sodass Spieler i nicht aufhört, bevor er es getan hat Ich habe die gültigen Nachrichten erhalten, Herr,4 j = (ESIGj(0), ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,4 j). Sei T die Zeit, wann Letzteres geschieht. Einige dieser Nachrichten stammen möglicherweise von böswilligen Spielern, aber weil |MSV r,4| < tH, mindestens einer davon stammt von einem ehrlichen Prüfer im HSV r,4 und wird nach einiger Zeit gesendet T r + t4. Dementsprechend ist T \(\geq\)T r +t4 > T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ, und bis zur Zeit T hat Spieler i auch erhalten die Nachricht Herr,1 \(\ell\)r . Aufgrund der Konstruktion des Protokolls stoppt Spieler i zum Zeitpunkt \(\beta\)r,5 ich = T ohne irgendetwas verbreiten; setzt Br = Br \(\ell\)r; und setzt sein eigenes CERT r auf die Menge der (r, 4)-Nachrichten für 0 und H(Br \(\ell\)r), die er erhalten hat. Schritt s > 5. In ähnlicher Weise hätte ich für jeden Schritt s > 5 und jeden Verifizierer i \(\in\)HSV r,s den Spieler i alle von den Verifizierern in HSV r,4 gesendeten Nachrichten erhalten, wenn er bis zum Zeitpunkt \(\alpha\)r,s gewartet hat ich + ts. Durch die Dieselbe Analyse, Spieler i stoppt, ohne etwas zu verbreiten, und setzt Br = Br \(\ell\)r (und seine eigenen einstellen CERT r ordnungsgemäß). Natürlich dürfen die böswilligen Verifizierer nicht aufhören und sich willkürlich verbreiten Nachrichten, sondern weil |MSV r,s| < tH, durch Induktion konnte kein anderes v′ von den Verifizierern signiert werden in jedem Schritt 4 \(\leq\)s′ < s, die ehrlichen Verifizierer hören also nur auf, weil sie das Gültige erhalten haben (r, 4)-Nachrichten für 0 und H(Br \(\ell\)r). Rekonstruktion des Round-r-Blocks. Die Analyse von Schritt 5 gilt für eine generische Ehrlichkeit Benutzer i fast ohne Änderung. Tatsächlich beginnt Spieler i seine eigene Runde r im Intervall Ir und stoppt erst zu einem Zeitpunkt T, wenn er tH gültige (r, 4)-Nachrichten für H(Br.) erhalten hat \(\ell\)r). Wieder weil Mindestens eine dieser Nachrichten stammt von ehrlichen Prüfern und wird nach der Zeit T r + t4 gesendet, die Spieler i hat erhielt auch mr,1 \(\ell\)r durch die Zeit T. Somit setzt er Br = Br \(\ell\)r mit dem richtigen CERT r. Es bleibt nur noch zu zeigen, dass alle ehrlichen Benutzer ihre Runde r innerhalb des Zeitintervalls Ir+1 beenden. Durch die Analyse von Schritt 5 kennt jeder ehrliche Verifizierer i \(\in\)HSV r,5 Br am oder vor \(\alpha\)r,5 ich + t5 \(\leq\) T r + \(\lambda\) + t5 = T r + 8\(\lambda\) + Λ. Da T r+1 der Zeitpunkt ist, zu dem der erste ehrliche Benutzer ir Br kennt, haben wir T r+1 \(\leq\)T r + 8\(\lambda\) + Λ wie gewünscht. Darüber hinaus hat der Spieler, wenn er Br kennt, bereits dabei geholfen, die Nachrichten zu verbreiten sein CERT r. Beachten Sie, dass alle diese Nachrichten innerhalb der Zeit \(\lambda\) von allen ehrlichen Benutzern empfangen werden, auch wenn 19 Streng genommen geschieht dies mit sehr hoher Wahrscheinlichkeit, aber nicht unbedingt mit überwältigender Wahrscheinlichkeit. Allerdings ist dies Die Wahrscheinlichkeit wirkt sich geringfügig auf die Laufzeit des Protokolls aus, hat jedoch keinen Einfluss auf seine Richtigkeit. Wenn h = 80 %, dann |HSV r,4| \(\geq\)tH mit Wahrscheinlichkeit 1 −10−8. Wenn dieses Ereignis nicht eintritt, wird das Protokoll für ein anderes fortgesetzt 3 Schritte. Da die Wahrscheinlichkeit, dass dies nicht in zwei Schritten geschieht, vernachlässigbar ist, endet das Protokoll bei Schritt 8 Erwartungsgemäß beträgt die Anzahl der erforderlichen Schritte also fast 5.Spieler ir waren der erste Spieler, der sie propagierte. Darüber hinaus haben wir nach der obigen Analyse T r+1 \(\geq\)T r + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ, also haben alle ehrlichen Benutzer mr,1 erhalten \(\ell\)r durch die Zeit T r+1 + \(\lambda\). Dementsprechend Alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1 = [T r+1, T r+1 + \(\lambda\)]. Schließlich gilt für r = 0 tatsächlich T 1 \(\leq\)t4 + \(\lambda\) = 6\(\lambda\) + Λ. Alles zusammen kombinieren, Es gilt Lemma 5.2. ■ 5.8 Das Soliditäts-Lemma Lemma 5.3. [Gesundheits-Lemma, angepasst] Unter der Annahme, dass die Eigenschaften 1–3 für Runde r −1 gelten, wenn Der Anführer \(\ell\) ist böswillig, mit überwältigender Wahrscheinlichkeit stimmen alle ehrlichen Benutzer dem gleichen Block zu Br, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ und alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1. Nachweisen. Wir betrachten die beiden Teile des Protokolls, GC und BBA⋆, getrennt. GC. Nach der induktiven Hypothese und nach Lemma 5.5, für jeden Schritt s \(\in\){2, 3, 4} und jeden ehrlichen Verifizierer i \(\in\)HSV r,s, wenn Spieler i zum Zeitpunkt \(\beta\)r,s agiert ich = \(\alpha\)r,s ich + ts, er hat alle gesendeten Nachrichten erhalten von allen ehrlichen Prüfern in den Schritten s′ < s. Für Schritt 4 unterscheiden wir zwei mögliche Fälle. Fall 1. Kein Verifizierer i \(\in\)HSV r,4 setzt gi = 2. In diesem Fall gilt per Definition bi = 1 für alle Verifizierer i \(\in\)HSV r,4. Das heißt, sie beginnen mit einem Vereinbarung über 1 im binären BA-Protokoll. Sie haben möglicherweise keine Einigung über ihre Vis, aber das spielt keine Rolle, wie wir im binären BA sehen werden. Fall 2. Es gibt einen Verifizierer ˆi \(\in\)HSV r,4 mit gˆi = 2. In diesem Fall zeigen wir das (1) gi \(\geq\)1 für alle i \(\in\)HSV r,4, (2) Es gibt einen Wert v′ mit vi = v′ für alle i \(\in\)HSV r,4 und (3) Es existiert eine gültige Nachricht mr,1 \(\ell\) von einem Verifizierer \(\ell\) \(\in\)SV r,1 mit v′ = H(Br \(\ell\)). Da Spieler ˆi ehrlich ist und gˆi = 2 setzt, sind tatsächlich mehr als 2/3 aller gültigen Nachrichten mr,3 j er hat are für den gleichen Wert v′ ̸= \(\bot\) erhalten, und er hat vˆi = v′ gesetzt. Nach Eigenschaft (d) in Lemma 5.5 kann es für jeden anderen ehrlichen (r, 4)-Verifizierer i nicht mehr sein als 2/3 aller gültigen Nachrichten mr,3 j die i′ erhalten hat, sind für den gleichen Wert v′′ ̸= v′. Wenn i dementsprechend gi = 2 setzt, muss es sein, dass ich auch > 2/3 Mehrheit für v′ gesehen und gesetzt habe vi = v′, wie gewünscht. Betrachten Sie nun einen beliebigen Verifizierer i \(\in\)HSV r,4 mit gi < 2. Ähnlich wie bei der Analyse von Property (d) in Lemma 5.5, weil Spieler ˆi > 2/3 Mehrheit für v′ gesehen hat, mehr als 1 2|HSV r,3| ehrlich (r, 3)-Verifizierer haben v′ signiert. Weil ich alle Nachrichten von ehrlichen (r, 3)-Verifizierern von erhalten habe Zeit \(\beta\)r,4 ich = \(\alpha\)r,4 ich + t4, er hat insbesondere mehr als 1 erhalten 2|HSV r,3| Nachrichten von ihnen für v′. Weil |HSV r,3| > 2|MSV r,3|, i hat > ​​1/3 Mehrheit für v′ gesehen. Dementsprechend, Spieler i setzt gi = 1 und Eigenschaft (1) gilt. Setzt Spieler i unbedingt vi = v′? Angenommen, es gibt einen anderen Wert v′′ ̸= \(\bot\)so dass Spieler i hat auch > 1/3 Mehrheit für v'' gesehen. Einige dieser Nachrichten könnten von böswilligen Absendern stammen Prüfer, aber mindestens einer von ihnen stammt von einem ehrlichen Prüfer j \(\in\)HSV r,3: tatsächlich, weil |HSV r,3| > 2|MSV r,3| und ich habe alle Nachrichten von HSV r,3 erhalten, der Schadsoftware Verifizierer, von denen ich eine gültige (r, 3)-Nachricht erhalten habe, zählen < 1/3 aller gültigen Nachrichten, die er erhalten hat.Per Definition muss Spieler j > 2/3 Mehrheit für v'' unter allen gültigen (r, 2)-Nachrichten gesehen haben er hat erhalten. Wir haben jedoch bereits festgestellt, dass einige andere ehrliche (r, 3)-Verifizierer dies gesehen haben 2/3 Mehrheit für v′ (weil sie v′ unterzeichnet haben). Aufgrund der Eigenschaft (d) von Lemma 5.5 ist dies nicht möglich passieren und ein solcher Wert v'' existiert nicht. Somit muss Spieler i wie gewünscht vi = v′ gesetzt haben, und Eigenschaft (2) gilt. Angesichts der Tatsache, dass einige ehrliche (r, 3)-Prüfer eine Mehrheit von > 2/3 für v′ gesehen haben, sind einige (eigentlich) Mehr als die Hälfte der ehrlichen (r, 2)-Verifizierer haben für v′ unterschrieben und ihre Botschaften verbreitet. Durch die Konstruktion des Protokolls müssen diese ehrlichen (r, 2)-Verifizierer eine gültige Gültigkeit erhalten haben Nachricht an Herrn,1 \(\ell\) von irgendeinem Spieler \(\ell\) \(\in\)SV r,1 mit v′ = H(Br \(\ell\)), daher gilt Eigenschaft (3). BBA⋆. Wir unterscheiden wieder zwei Fälle. Fall 1. Alle Verifizierer i \(\in\)HSV r,4 haben bi = 1. Dies geschieht nach Fall 1 von GC. Als |MSV r,4| < tH, in diesem Fall kein Prüfer im SV r,5 könnte die gültigen (r, 4)-Nachrichten für Bit 0 sammeln oder generieren. Daher kein ehrlicher Verifizierer im HSV r,5 würde aufhören, weil er einen nicht leeren Block Br kennt. Darüber hinaus erfüllt s′ = 5 nicht, obwohl es mindestens tH gültige (r, 4)-Nachrichten für Bit 1 gibt s′ −2 ≡1 mod 3, daher würde kein ehrlicher Verifizierer im HSV r,5 aufhören, weil er Br = Br weiß ǫ. Stattdessen agiert jeder Prüfer i \(\in\)HSV r,5 zum Zeitpunkt \(\beta\)r,5 ich = \(\alpha\)r,5 ich + t5, bis er alles erhalten hat Von HSV r,4 gesendete Nachrichten gemäß Lemma 5.5. Somit hat Spieler, den ich gesehen habe, > 2/3 Mehrheit für 1 und setzt bi = 1. In Schritt 6, der ein Coin-Fixed-To-1-Schritt ist, erfüllt dort s′ −2 ≡0 mod 3, obwohl s′ = 5 Es existieren keine gültigen (r, 4)-Nachrichten für Bit 0, daher würde kein Verifizierer im HSV r,6 anhalten, weil er kennt einen nicht leeren Block Br. Mit s′ = 6 ist jedoch s′ −2 ≡1 mod 3 und es existiert |HSV r,5| \(\geq\)tH gültige (r, 5)-Nachrichten für Bit 1 von HSV r,5. Für jeden Verifizierer i \(\in\)HSV r,6, gemäß Lemma 5.5, zum oder vor dem Zeitpunkt \(\alpha\)r,6 ich + t6 Spieler i hat alle Nachrichten von HSV r,5 erhalten, daher stoppt i, ohne etwas weiterzugeben, und setzt Br = Br ǫ. Sein CERT r ist die Menge der gültigen (r, 5)-Nachrichten mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) von ihm empfangen, wenn er anhält. Lassen Sie den Spieler als Nächstes entweder ein ehrlicher Prüfer in einem Schritt s > 6 oder ein allgemeiner ehrlicher Benutzer sein (d. h. Nichtprüfer). Ähnlich wie beim Beweis von Lemma 5.2 setzt Spieler i Br = Br ǫ und legt sein eigenes fest CERT r soll die Menge der gültigen (r, 5)-Nachrichten mr,5 sein j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j ) er hat erhalten. Schließlich, ähnlich wie in Lemma 5.2, T r+1 \(\leq\) min i\(\in\)HSV r,6 \(\alpha\)r,6 ich + t6 \(\leq\)T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ, und alle ehrlichen Benutzer kennen Br im Zeitintervall Ir+1, denn der erste ehrliche Benutzer ist wer weiß, dass Br dabei geholfen hat, die (r, 5)-Nachrichten in seinem CERT r zu verbreiten. Fall 2. Es existiert ein Verifizierer ˆi \(\in\)HSV r,4 mit bˆi = 0. Dies geschieht im Anschluss an Fall 2 von GC und ist der komplexere Fall. Durch die Analyse von GC, in diesem Fall liegt eine gültige Nachricht mr,1 vor \(\ell\) so dass vi = H(Br \(\ell\)) für alle i \(\in\)HSV r,4. Hinweis dass die Prüfer im HSV r,4 möglicherweise keine Einigung über ihre Bi’s haben. Für jeden Schritt s \(\in\){5, . . . , m + 3} und Verifier i \(\in\)HSV r,s, nach Lemma 5.5 Spieler hätte ich hat alle von allen ehrlichen Verifizierern in HSV r,4 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1 gesendeten Nachrichten erhalten, wenn er gewartet hat für die Zeit ts.Wir betrachten nun das folgende Ereignis E: Es gibt einen Schritt s∗\(\geq\)5, so dass zum ersten Mal Zeit in der binären BA sollte ein Spieler i∗\(\in\)SV r,s∗ (egal ob böswillig oder ehrlich) aufhören ohne etwas zu verbreiten. Wir verwenden „sollte aufhören“, um die Tatsache hervorzuheben, dass, wenn Spieler i∗ böswillig ist, dann darf er so tun, als ob er nicht protokollarisch aufhören dürfe und Botschaften nach Wahl des Gegners verbreiten. Darüber hinaus auch durch die Konstruktion des Protokolls (E.a) i∗ist in der Lage, mindestens die gültigen Nachrichten mr,s′−1 zu sammeln oder zu generieren j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) für dasselbe v und s′, mit 5 \(\leq\)s′ \(\leq\)s∗und s′ −2 ≡0 mod 3; oder (E.b) i∗ist in der Lage, mindestens die gültigen Nachrichten mr,s′−1 zu sammeln oder zu generieren j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ) für dasselbe s′, mit 6 \(\leq\)s′ \(\leq\)s∗und s′ −2 ≡1 mod 3. Denn die ehrlichen (r, s′ −1)-Nachrichten werden von allen ehrlichen (r, s′)-Verifizierern vor ihnen empfangen sind mit dem Warten in Schritt s′ fertig, und weil der Gegner alles spätestens am erhält Ehrliche Benutzer, ohne Beschränkung der Allgemeinheit gilt s′ = s∗und Spieler i∗ ist bösartig. Beachten Sie das wir brauchten nicht, dass der Wert v in E.a der hash eines gültigen Blocks ist: wie noch deutlich wird in der Analyse ist v = H(Br \(\ell\)) in diesem Unterereignis. Im Folgenden analysieren wir zunächst Fall 2 nach Ereignis E und zeigen dann, dass der Wert von s∗ im Wesentlichen ist entsprechend auf Lr verteilt (also geschieht Ereignis E vor Schritt m + 3 mit Überwältigung). Wahrscheinlichkeit angesichts der Beziehungen für Parameter). Zunächst gilt für jeden Schritt 5 \(\leq\)s < s∗: Jeder ehrliche Verifizierer i \(\in\)HSV r,s hat die Zeit ts abgewartet und vi als Mehrheitsvotum der gesetzt gültige (r, s−1)-Nachrichten, die er erhalten hat. Seit Spieler i habe ich alle ehrlichen (r, s−1)-Nachrichten erhalten nach Lemma 5.5, da alle ehrlichen Verifizierer in HSV r,4 H(Br.) unterzeichnet haben \(\ell\)) folgenden Fall 2 von GC, und da |HSV r,s−1| > 2|MSV r,s−1| für jedes s haben wir per Induktion diesen Spieler i eingestellt hat vi = H(Br \(\ell\)). Das Gleiche gilt für jeden ehrlichen Verifizierer i \(\in\)HSV r,s∗, der nicht aufhört, ohne zu propagieren irgendetwas. Nun betrachten wir Schritt s∗ und unterscheiden vier Unterfälle. Fall 2.1.a. Das Ereignis E.a tritt ein und es gibt einen ehrlichen Verifizierer i′ \(\in\)HSV r,s∗, der das tun sollte auch aufhören, ohne etwas zu verbreiten. In diesem Fall gilt s∗−2 ≡0 mod 3 und Schritt s∗ ist ein Coin-Fixed-To-0-Schritt. Von Definition: Spieler i′ hat mindestens tH gültige (r, s∗−1)-Nachrichten der Form erhalten (ESIGj(0), ESIGj(v), \(\sigma\)r,s∗−1 j ). Da alle Verifizierer in HSV r,s∗−1 H(Br.) signiert haben \(\ell\)) und |MSV r,s∗−1| < tH, wir haben v = H(Br \(\ell\)). Da mindestens tH −|MSV r,s∗−1| \(\geq\)1 der von i′ empfangenen (r, s∗−1)-Nachrichten für 0 und v werden von Verifizierern in HSV r,s∗−1 nach der Zeit T r +ts∗−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 gesendet \(\ell\) +Λ, Spieler i′ hat mr,1 erhalten \(\ell\) bis er diese (r, s∗−1)-Nachrichten erhält. Also Spieler i′ bleibt stehen, ohne etwas zu verbreiten; setzt Br = Br \(\ell\); und setzt sein eigenes CERT r auf das Menge gültiger (r, s∗−1)-Nachrichten für 0 und v, die er empfangen hat. Als nächstes zeigen wir, dass jeder andere Verifizierer i \(\in\)HSV r,s∗ entweder mit Br = Br gestoppt hat \(\ell\), oder hat bi = 0 gesetzt und propagiert (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s ich). In der Tat, weil Schritt s∗ Es ist das erste Mal, dass ein Verifizierer anhält, ohne etwas zu verbreiten, aber das ist nicht der Fall Es gibt einen Schritt s′ < s∗mit s′ −2 ≡1 mod 3, sodass tH (r, s′ −1)-Verifizierer das Vorzeichen 1 haben. Dementsprechend stoppt kein Verifizierer im HSV r,s∗mit Br = Br ǫ.Darüber hinaus gilt, dass alle ehrlichen Prüfer in den Schritten {4, 5, . . . , s∗−1} haben das Vorzeichen H(Br \(\ell\)) gibt es Es gibt keinen Schritt s′ \(\leq\)s∗mit s′ −2 ≡0 mod 3, sodass tH (r, s′ −1)-Verifizierer vorzeichenbehaftet sind einige v′′ ̸= H(Br \(\ell\)) – tatsächlich |MSV r,s′−1| < tH. Dementsprechend stoppt kein Verifizierer im HSV r,s∗ mit Br ̸= Br ǫ und Br ̸= Br \(\ell\). Das heißt, wenn ein Spieler i \(\in\)HSV r,s∗ ohne angehalten hat Wenn er etwas propagiert, muss er Br = Br gesetzt haben \(\ell\). Wenn ein Spieler i \(\in\)HSV r,s∗die Zeit ts∗abgewartet und zur Zeit eine Nachricht verbreitet hat \(\beta\)r,s∗ ich = \(\alpha\)r,s∗ ich + ts∗, er hat alle Nachrichten vom HSV r,s∗−1 erhalten, darunter mindestens tH −|MSV r,s∗−1| davon für 0 und v. Wenn ich > 2/3 Mehrheit für 1 gesehen habe, dann er hat mehr als 2(tH −|MSV r,s∗−1|) gültige (r, s∗−1)-Nachrichten für 1 gesehen, mit mehr als 2tH −3|MSV r,s∗−1| davon von ehrlichen (r, s∗−1)-Verifizierern. Dies impliziert jedoch |HSV r,s∗−1| \(\geq\)tH−|MSV r,s∗−1|+2tH−3|MSV r,s∗−1| > 2n−4|MSV r,s∗−1|, widersprüchlich die Tatsache, dass |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n, was sich aus den Beziehungen für die Parameter ergibt. Dementsprechend sehe ich nicht > 2/3 Mehrheit für 1, und er setzt bi = 0, weil Schritt s∗ ein Coin-Fixed-To-0-Schritt ist. So wie wir es getan haben gesehen, vi = H(Br \(\ell\)). Somit propagiert i (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s i ) wie wir es wollten zeigen. Für Schritt s∗+ 1, da Spieler i′ dabei geholfen hat, die Nachrichten in seinem CERT r zu verbreiten am oder vor der Zeit \(\alpha\)r,s∗ ich‘ + ts∗, alle ehrlichen Prüfer im HSV r,s∗+1 haben mindestens erhalten tH gültige (r, s∗−1)-Nachrichten für Bit 0 und Wert H(Br \(\ell\)) am oder bevor sie fertig sind warten. Darüber hinaus werden Verifizierer in HSV r,s∗+1 nicht aufhören, bevor sie diese (r, s∗−1)- erhalten. Nachrichten, da keine anderen gültigen (r, s′ −1)-Nachrichten für Bit 1 mit existieren s′ −2 ≡1 mod 3 und 6 \(\leq\)s′ \(\leq\)s∗+ 1, nach der Definition von Schritt s∗. Insbesondere Step s∗+ 1 selbst ist ein Coin-Fixed-To-1-Schritt, aber kein ehrlicher Verifizierer im HSV r,s∗hat sich verbreitet eine Nachricht für 1 und |MSV r,s∗| < tH. Somit stoppen alle ehrlichen Verifizierer im HSV r,s∗+1, ohne etwas zu propagieren, und setzen Br = Br \(\ell\): wie zuvor haben sie mr,1 erhalten \(\ell\) bevor sie die gewünschten (r, s∗−1)-Nachrichten erhalten.20 Das Gleiche gilt für alle ehrlichen Prüfer in zukünftigen Schritten und alle ehrlichen Benutzer im Allgemeinen. Insbesondere wissen sie alle, dass Br = Br ist \(\ell\)innerhalb des Zeitintervalls Ir+1 und T r+1 \(\leq\) \(\alpha\)r,s∗ ich‘ + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Fall 2.1.b. Das Ereignis E.b tritt ein und es gibt einen ehrlichen Verifizierer i′ \(\in\)HSV r,s∗, der das tun sollte auch aufhören, ohne etwas zu verbreiten. In diesem Fall haben wir s∗−2 ≡1 mod 3 und Schritt s∗ ist ein Coin-Fixed-To-1-Schritt. Die Analyse ähnelt Fall 2.1.a und viele Details wurden weggelassen. 20Wenn er böswillig ist, könnte er Herrn1 aussenden \(\ell\) zu spät, in der Hoffnung, dass einige ehrliche Benutzer/Prüfer mr,1 nicht erhalten haben \(\ell\) noch wenn sie dafür das gewünschte Zertifikat erhalten. Da der Verifizierer ˆi \(\in\)HSV r,4 jedoch bˆi = 0 und vˆi = H(Br \(\ell\)), wie bevor wir wissen, dass mehr als die Hälfte der ehrlichen Verifizierer i \(\in\)HSV r,3 vi = H(Br \(\ell\)). Dies impliziert noch mehr mehr als die Hälfte der ehrlichen Verifizierer i \(\in\)HSV r,2 haben vi = H(Br \(\ell\)), und diese (r, 2)-Verifizierer haben alle mr,1 erhalten \(\ell\). Als die Der Gegner kann einen Verifizierer nicht von einem Nichtverifizierer unterscheiden, er kann die Ausbreitung von mr,1 nicht ins Visier nehmen \(\ell\) zu (r, 2)-Verifizierern ohne dass die Nichtprüfer es sehen. Tatsächlich ist mit hoher Wahrscheinlichkeit mehr als die Hälfte (oder ein guter konstanter Bruchteil) aller ehrlichen Benutzer haben mr,1 gesehen \(\ell\) nachdem sie vom Beginn ihrer eigenen Runde r an auf t2 gewartet haben. Von hier an ist die Zeit \(\lambda\)′, die für mr,1 benötigt wird \(\ell\) um die verbleibenden ehrlichen Benutzer zu erreichen, ist viel kleiner als Λ, und der Einfachheit halber tun wir dies nicht Schreiben Sie es in der Analyse auf. Wenn 4\(\lambda\) \(\geq\) \(\lambda\)′, dann wird die Analyse ohne jegliche Änderung durchgeführt: am Ende von Schritt 4 alle Ehrliche Benutzer hätten mr,1 erhalten \(\ell\). Wenn die Größe des Blocks enorm wird und 4\(\lambda\) < \(\lambda\)′, dann in den Schritten 3 und 4: Das Protokoll könnte jeden Prüfer auffordern, auf \(\lambda\)′/2 statt auf 2\(\lambda\) zu warten, und die Analyse bleibt bestehen.Wie zuvor muss Spieler i′ mindestens tH gültige (r, s∗−1)-Nachrichten der Form erhalten haben (ESIGj(1), ESIGj(vj), \(\sigma\)r,s∗−1 j ). Auch hier gibt es aufgrund der Definition von s∗ keine Stufe 5 \(\leq\)s′ < s∗mit s′ −2 ≡0 mod 3, wobei mindestens tH (r, s′ −1)-Verifizierer 0 vorzeichenbehaftet haben und das gleiche v. Somit stoppt Spieler i′, ohne etwas zu propagieren; setzt Br = Br ǫ; und Sets sein eigenes CERT r sei die Menge der gültigen (r, s∗−1)-Nachrichten für Bit 1, die er empfangen hat. Darüber hinaus hat jeder andere Verifizierer i \(\in\)HSV r,s∗ entweder mit Br = Br aufgehört ǫ , oder hat bi = gesetzt 1 und propagiert (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ ich ). Seit Spieler i′ bei der Verbreitung mitgeholfen hat die (r, s∗−1)-Nachrichten in seinem CERT r nach Zeit \(\alpha\)r,s∗ ich‘ + ts∗, wieder alle ehrlichen Prüfer drin HSV r,s∗+1 stoppt, ohne etwas zu propagieren, und setzt Br = Br ǫ . Ebenso alles ehrlich Benutzer wissen, dass Br = Br ist ǫ innerhalb des Zeitintervalls Ir+1 und T r+1 \(\leq\) \(\alpha\)r,s∗ ich‘ + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Fall 2.2.a. Das Ereignis E.a tritt ein und es gibt keinen ehrlichen Verifizierer i′ \(\in\)HSV r,s∗who sollte auch aufhören, ohne etwas zu verbreiten. Beachten Sie in diesem Fall, dass Spieler i∗ über ein gültiges CERT r verfügen könnte i∗bestehend aus dem gewünschten tH (r, s∗−1)-Nachrichten, die der Gegner sammeln oder generieren kann. Allerdings ist das böswillig Prüfer helfen möglicherweise nicht dabei, diese Botschaften zu verbreiten, daher können wir nicht zu dem Schluss kommen, dass dies ehrlich ist Benutzer erhalten sie rechtzeitig \(\lambda\). Tatsächlich ist |MSV r,s∗−1| dieser Nachrichten stammen möglicherweise von böswillige (r, s∗−1)-Verifizierer, die ihre Nachrichten überhaupt nicht verbreiteten, sondern nur verschickten sie an die böswilligen Verifizierer in Schritt s∗ weiter. Ähnlich wie in Fall 2.1.a gilt hier s∗−2 ≡0 mod 3, Schritt s∗ist ein Coin-Fixed-To-0-Schritt, und die (r, s∗−1)-Nachrichten in CERT r i∗are für Bit 0 und v = H(Br \(\ell\)). In der Tat, alles ehrlich (r, s∗−1)-Verifizierer signieren v, daher kann der Gegner keine gültigen (r, s∗−1)-Nachrichten generieren für ein anderes v′. Darüber hinaus haben alle ehrlichen (r, s∗)-Verifizierer die Zeit ts∗ abgewartet und sehen keine > 2/3 Mehrheit für Bit 1, wiederum weil |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n. Also jeder ehrliche Prüfer i \(\in\)HSV r,s∗sets bi = 0, vi = H(Br \(\ell\)) mit Stimmenmehrheit und propagiert mr,s∗ ich = (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s∗ ich ) zum Zeitpunkt \(\alpha\)r,s∗ ich + ts∗. Betrachten Sie nun die ehrlichen Verifizierer in Schritt s∗+ 1 (was ein Coin-Fixed-To-1-Schritt ist). Wenn die Der Gegner sendet die Nachrichten tatsächlich in CERT r i∗zu einigen von ihnen und veranlasst sie dazu Stopp, dann ähnlich wie in Fall 2.1.a, alle ehrlichen Benutzer wissen Br = Br \(\ell\)innerhalb des Zeitintervalls Ir+1 und T r+1 \(\leq\)T r + \(\lambda\) + ts∗+1. Ansonsten haben alle ehrlichen Verifizierer in Schritt s∗+1 alle (r, s∗)-Nachrichten für 0 und erhalten H(Br \(\ell\)) aus HSV r,s∗nach Wartezeit ts∗+1, was zu > 2/3 Mehrheit führt, weil |HSV r,s∗| > 2|MSV r,s∗|. Somit verbreiten alle Verifizierer im HSV r,s∗+1 ihre Nachrichten für 0 und H(Br \(\ell\)) entsprechend. Beachten Sie, dass die Verifizierer in HSV r,s∗+1 nicht mit Br = Br aufhören \(\ell\), weil Schritt s∗+ 1 kein Coin-Fixed-To-0-Schritt ist. Betrachten Sie nun die ehrlichen Verifizierer in Schritt s∗+2 (bei dem es sich um einen Coin-Echt-Flipped-Schritt handelt). Wenn der Gegner die Nachrichten in CERT r sendet i∗zu einigen von ihnen und bringt sie zum Anhalten, Andererseits wissen alle ehrlichen Benutzer, dass Br = Br ist \(\ell\)innerhalb des Zeitintervalls Ir+1 und T r+1 \(\leq\)T r + \(\lambda\) + ts∗+2.Ansonsten haben alle ehrlichen Prüfer in Schritt s∗+ 2 alle (r, s∗+ 1)-Nachrichten für erhalten 0 und H(Br \(\ell\)) aus HSV r,s∗+1 nach Wartezeit ts∗+2, was zu > 2/3 Mehrheit führt. Somit verbreiten sie alle ihre Botschaften für 0 und H(Br \(\ell\)) dementsprechend: das tun sie in diesem Fall nicht „eine Münze werfen“. Beachten Sie erneut, dass sie nicht aufhören, ohne sich zu verbreiten. weil Schritt s∗+ 2 kein Coin-Fixed-To-0-Schritt ist. Schließlich für die ehrlichen Verifizierer in Schritt s∗+3 (was ein weiterer Coin-Fixed-To-0-Schritt ist): alle von ihnen hätten mindestens die gültigen Nachrichten für 0 und H(Br.) erhalten \(\ell\)) aus HSV s∗+2, wenn sie wirklich die Zeit ts∗+3 warten. Also, ob der Gegner die Nachrichten sendet oder nicht in CERT r i∗zu jedem von ihnen stoppen alle Verifizierer in HSV r,s∗+3 mit Br = Br \(\ell\), ohne irgendetwas verbreiten. Abhängig davon, wie sich der Gegner verhält, kann es sein, dass einige von ihnen dies tun ihr eigenes CERT r bestehend aus diesen (r, s∗−1)-Nachrichten in CERT r i∗, und die anderen haben ihr eigenes CERT r bestehend aus diesen (r, s∗+ 2)-Nachrichten. Auf jeden Fall alle ehrlichen Nutzer weiß Br = Br \(\ell\)innerhalb des Zeitintervalls Ir+1 und T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3. Fall 2.2.b. Ereignis E.b tritt ein und es gibt keinen ehrlichen Verifizierer i′ \(\in\)HSV r,s∗who sollte auch aufhören, ohne etwas zu verbreiten. Die Analyse in diesem Fall ähnelt der in Fall 2.1.b und Fall 2.2.a, daher viele Details wurden weggelassen. Insbesondere CERT r i∗besteht aus den tH gewünschten (r, s∗−1)-Nachrichten für Bit 1, das der Gegner sammeln oder erzeugen kann, s∗−2 ≡1 mod 3, Schritt s∗ist a Coin-Fixed-To-1-Schritt, und kein ehrlicher (r, s∗)-Verifizierer hätte > 2/3 Mehrheit für 0 sehen können. Somit setzt jeder Verifizierer i \(\in\)HSV r,s∗ bi = 1 und propagiert mr,s∗ ich = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ ich ) zum Zeitpunkt \(\alpha\)r,s∗ ich + ts∗. Ähnlich wie in Fall 2.2.a, in höchstens 3 weiteren Schritten (d. h. dem Protokoll erreicht Schritt s∗+3, was ein weiterer Coin-Fixed-To-1-Schritt ist), wissen alle ehrlichen Benutzer, dass Br = Br ist ǫ innerhalb des Zeitintervalls Ir+1. Darüber hinaus kann T r+1 \(\leq\)T r+\(\lambda\)+ts∗+1 oder \(\leq\)T r+\(\lambda\)+ts∗+2 sein, oder \(\leq\)T r + \(\lambda\) + ts∗+3, je nachdem, wann ein ehrlicher Prüfer zum ersten Mal in der Lage ist, aufzuhören ohne sich zu verbreiten. Durch die Kombination der vier Unterfälle haben wir festgestellt, dass alle ehrlichen Benutzer Br innerhalb des Zeitintervalls kennen Ir+1, mit T r+1 \(\leq\)T r + \(\lambda\) + ts∗in den Fällen 2.1.a und 2.1.b, und T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 in den Fällen 2.2.a und 2.2.b. Es bleibt die Obergrenze von s∗ und damit T r+1 für Fall 2, und wir tun dies, indem wir überlegen, wie Oftmals werden die Coin-Genuinely-Flipped-Schritte tatsächlich im Protokoll ausgeführt: das heißt, Einige ehrliche Prüfer haben tatsächlich eine Münze geworfen. Legen Sie insbesondere willkürlich einen Coin-Echt-umgedrehten Schritt s′ fest (d. h. 7 \(\leq\) s′ \(\leq\) m + 2 und s′ −2 ≡2 mod 3) und sei \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 j ). Nehmen wir zunächst an, dass s′ < s∗, denn sonst wirft kein ehrlicher Verifizierer in Schritt s′ tatsächlich eine Münze, heißt es weiter oben Diskussionen. Nach der Definition von SV r,s′−1 ist der hash-Wert des Berechtigungsnachweises von \(\ell\)′ auch der kleinste unter ihnen alle Benutzer in PKr−k. Da es sich bei der Funktion hash um eine zufällige Funktion oracle handelt, ist Spieler \(\ell\)′ im Idealfall ehrlich Wahrscheinlichkeit mindestens h. Wie wir später zeigen werden, auch wenn der Gegner sein Bestes versucht, das vorherzusagen Ausgabe des Zufalls oracle und Neigung der Wahrscheinlichkeit, Spieler \(\ell\)′ ist immer noch ehrlich mit der Wahrscheinlichkeitmindestens ph = h2(1 + h −h2). Im Folgenden betrachten wir den Fall, in dem dies tatsächlich geschieht: Das heißt, \(\ell\)′ \(\in\)HSV r,s′−1. Beachten Sie, dass jeder ehrliche Verifizierer i \(\in\)HSV r,s′ alle Nachrichten von HSV r,s′−1 bis erhalten hat Zeit \(\alpha\)r,s′ ich + ts′. Wenn Spieler i eine Münze werfen muss (d. h. er hat nicht mehr als 2/3 Mehrheit dafür gesehen). das gleiche Bit b \(\in\){0, 1}), dann setzt er bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )). Wenn es einen anderen Ehrlichen gibt Verifizierer i′ \(\in\)HSV r,s′, der > 2/3 Mehrheit für ein Bit b \(\in\){0, 1} gesehen hat, dann durch Eigenschaft (d) von Lemma 5.5 hätte kein ehrlicher Verifizierer im HSV r,s′ eine Zeit lang eine Mehrheit von > 2/3 gesehen b′ ̸= b. Da lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) = b mit Wahrscheinlichkeit 1/2, alle ehrlichen Prüfer im HSV r,s′ erreichen eine Übereinstimmung über b mit Wahrscheinlichkeit 1/2. Wenn ein solcher Verifizierer i′ nicht existiert, dann natürlich alle Ehrliche Verifizierer in HSV r,s′ sind sich über das Bit lsb(H(\(\sigma\)r,s′−1) einig \(\ell\)′ )) mit Wahrscheinlichkeit 1. Wenn wir die Wahrscheinlichkeit für \(\ell\)′ \(\in\)HSV r,s′−1 kombinieren, erhalten wir, dass die ehrlichen Verifizierer in HSV r,s′ eine Einigung über ein Bit b \(\in\){0, 1} mit einer Wahrscheinlichkeit von mindestens ph erzielen 2 = h2(1+h−h2) 2 . Darüber hinaus durch Induktion auf der Mehrheitsabstimmung wie zuvor haben alle ehrlichen Verifizierer im HSV r,s′ ihre vi’s festgelegt sein H(Br \(\ell\)). Sobald also in Schritt s′ eine Einigung über b erzielt wird, ist T r+1 entweder \(\leq\)T r + \(\lambda\) + ts′+1 oder \(\leq\)T r + \(\lambda\) + ts′+2, abhängig davon, ob b = 0 oder b = 1, entsprechend der Analyse der Fälle 2.1.a und 2.1.b. In Insbesondere wird kein weiterer Coin-Genuinely-Flipped-Schritt ausgeführt: das heißt, die Verifizierer in Solche Schritte überprüfen immer noch, ob sie die Verifizierer sind, und warten daher, aber ohne sie werden sie alle aufhören irgendetwas verbreiten. Dementsprechend wird vor Schritt s∗ die Anzahl der Ausführungen der Coin-GenuinelyFlipped-Schritte entsprechend der Zufallsvariablen Lr verteilt. Schritt s′ vermieten laut Lr der letzte Coin-Echt-Flipped-Schritt bei der Konstruktion des Protokolls sein wir haben s′ = 4 + 3Lr. Wann sollte der Gegner den Schritt durchführen, wenn er T r+1 so lange verzögern möchte möglich? Wir können sogar davon ausgehen, dass der Gegner die Verwirklichung von Lr im Voraus kennt. Wenn s∗> s′, dann ist es nutzlos, weil sich die ehrlichen Prüfer bereits geeinigt haben Schritt s′. Natürlich wäre s∗ in diesem Fall s′ +1 oder s′ +2, wiederum abhängig davon, ob b = 0 oder b = 1. Dies trifft jedoch tatsächlich auf die Fälle 2.1.a und 2.1.b zu, und das resultierende T r+1 ist genau das das Gleiche wie in diesem Fall. Genauer gesagt, T r+1 \(\leq\)T r + \(\lambda\) + ts∗\(\leq\)T r + \(\lambda\) + ts′+2. Wenn s∗< s′ −3 – das heißt, s∗ liegt vor dem vorletzten Coin-Echt-Flipped-Schritt – dann durch die Analyse der Fälle 2.2.a und 2.2.b, T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 < T r + \(\lambda\) + ts′. Das heißt, der Gegner sorgt tatsächlich dafür, dass die Vereinbarung über Br schneller zustande kommt. Wenn s∗= s′ −2 oder s′ −1 – also der Coin-Fixed-To-0-Schritt oder der Coin-Fixed-To-1-Schritt unmittelbar vor Schritt s′ – dann durch die Analyse der vier Unterfälle die ehrlichen Prüfer in Schritte s′ können keine Münzen mehr werfen, weil sie entweder angehalten haben, ohne sich fortzupflanzen, oder > 2/3 Mehrheit für das gleiche Bit gesehen haben b. Deshalb haben wir T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 \(\leq\)T r + \(\lambda\) + ts′+2.Zusammenfassend lässt sich sagen, dass wir, egal was s∗ ist, haben 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\) + Λ, wie wir zeigen wollten. Der schlimmste Fall ist, wenn s∗= s′ −1 und Fall 2.2.b eintritt. Durch die Kombination der Fälle 1 und 2 des binären BA-Protokolls gilt Lemma 5.3. ■ 5.9 Sicherheit des Seed Qr und Wahrscheinlichkeit eines ehrlichen Führers Es bleibt Lemma 5.4 zu beweisen. Denken Sie daran, dass die Verifizierer in Runde r aus PKr−k und stammen werden entsprechend der Größe Qr−1 gewählt. Der Grund für die Einführung des Lookback-Parameters k Ziel ist es, sicherzustellen, dass der Gegner in der Runde r −k in der Lage ist, neue böswillige Benutzer hinzuzufügen zu PKr−k kann er die Größe Qr−1 nur mit vernachlässigbarer Wahrscheinlichkeit vorhersagen. Beachten Sie, dass die Die Funktion hash ist eine zufällige Funktion oracle und Qr−1 ist eine ihrer Eingaben bei der Auswahl von Verifizierern für Runde r. Unabhängig davon, wie böswillig Benutzer zu PKr-k hinzugefügt werden, gilt dies aus Sicht des Gegners für jeden Einer von ihnen wird immer noch als Verifizierer in einem Schritt der Runde r mit der erforderlichen Wahrscheinlichkeit p (oder) ausgewählt p1 für Schritt 1). Genauer gesagt haben wir das folgende Lemma. Lemma 5.6. Mit k = O(log1/2 F), für jede Runde r, mit überwältigender Wahrscheinlichkeit der Gegner hat Qr−1 in der Runde r −k nicht an den Zufallsgenerator oracle abgefragt. Nachweisen. Wir gehen per Induktion vor. Nehmen Sie an, dass der Gegner für jede Runde \(\gamma\) < r keine Abfrage durchgeführt hat Q\(\gamma\)−1 zum zufälligen oracle zurück in Runde \(\gamma\) −k.21 Betrachten Sie das folgende mentale Spiel, das von gespielt wird der Gegner in Runde r −k, der versucht, Qr−1 vorherzusagen. In Schritt 1 jeder Runde \(\gamma\) = r −k, . . . , r −1, gegeben ein spezifisches Q\(\gamma\)−1, das nicht an den Zufallsgenerator abgefragt wird oracle, indem die Spieler i \(\in\)PK\(\gamma\)−k gemäß den hash Werten H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) geordnet werden zunehmend erhalten wir eine zufällige Permutation über PK\(\gamma\)−k. Per Definition ist der Anführer \(\ell\) \(\gamma\) der erster Benutzer in der Permutation und ist ehrlich mit der Wahrscheinlichkeit h. Darüber hinaus, wenn PK\(\gamma\)−k groß ist Genug, für jede ganze Zahl x \(\geq\) 1, die Wahrscheinlichkeit, dass die ersten x Benutzer in der Permutation alle sind bösartig, aber der (x + 1)st ist ehrlich, ist (1 −h)xh. Wenn \(\ell\) \(\gamma\) ehrlich ist, dann ist Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\)). Da der Gegner die Signatur nicht fälschen kann von \(\ell\) \(\gamma\) ist Q\(\gamma\) aus der Sicht des Gegners gleichmäßig und zufällig verteilt und, außer mit exponentiell kleiner Wahrscheinlichkeit22 wurde bei Runde r −k nicht nach H abgefragt. Da jeder Q\(\gamma\)+1, Q\(\gamma\)+2, . . . , Qr−1 ist jeweils die Ausgabe von H mit Q\(\gamma\), Q\(\gamma\)+1, . . . , Qr−2 als einer der Eingänge, Für den Gegner sehen sie alle zufällig aus und der Gegner hätte Qr−1 nicht an H abfragen können rund r −k. Dementsprechend ist dies der einzige Fall, in dem der Gegner Qr−1 mit guter Wahrscheinlichkeit in der Runde vorhersagen kann r−k ist, wenn alle Anführer \(\ell\)r−k, . . . , \(\ell\)r−1 sind bösartig. Betrachten Sie erneut eine Runde \(\gamma\) \(\in\){r−k . . . , r−1} und die zufällige Permutation über PK\(\gamma\)−k, die durch die entsprechenden hash-Werte induziert wird. Wenn für einige x \(\geq\)2, die ersten x −1 Benutzer in der Permutation sind alle böswillig und der x-te ist ehrlich, dann ist der Der Gegner hat x mögliche Auswahlmöglichkeiten für Q\(\gamma\): entweder in der Form H(SIGi(Q\(\gamma\)−1, \(\gamma\))), wobei i eine davon ist 21Da k eine kleine ganze Zahl ist, kann man ohne Beschränkung der Allgemeinheit davon ausgehen, dass die ersten k Runden des Protokolls ausgeführt werden in einer sicheren Umgebung und die induktive Hypothese gilt für diese Runden. 22Das heißt, exponentiell in der Länge der Ausgabe von H. Beachten Sie, dass diese Wahrscheinlichkeit viel kleiner als F ist.die ersten x−1 böswilligen Benutzer, indem Spieler i zum eigentlichen Anführer der Runde \(\gamma\) gemacht wird; oder H(Q\(\gamma\)−1, \(\gamma\)), durch erzwingt B\(\gamma\) = B\(\gamma\) ǫ . Andernfalls ist der Anführer der Runde \(\gamma\) der erste ehrliche Benutzer in der Permutation und Qr−1 wird für den Gegner unvorhersehbar. Welche der oben genannten x Optionen von Q\(\gamma\) sollte der Gegner verfolgen? Um dem Gegner zu helfen Um diese Frage zu beantworten, machen wir ihn im mentalen Spiel tatsächlich mächtiger als er tatsächlich ist wie folgt. Erstens kann der Gegner in Wirklichkeit nicht den hash eines ehrlichen Benutzers berechnen Signatur, kann daher nicht für jedes Q\(\gamma\) die Anzahl x(Q\(\gamma\)) der böswilligen Benutzer zu Beginn bestimmen der zufälligen Permutation in Runde \(\gamma\) + 1, die durch Q\(\gamma\) induziert wird. Im mentalen Spiel geben wir ihm das Zahlen x(Q\(\gamma\)) kostenlos. Zweitens: In der Realität sind es alle ersten x Benutzer in der Permutation Böswillig zu sein bedeutet nicht unbedingt, dass sie alle zum Anführer gemacht werden können, denn die hash Werte ihrer Signaturen müssen ebenfalls kleiner als p1 sein. Wir haben diese Einschränkung im Mentalen ignoriert Spiel, was dem Gegner noch mehr Vorteile verschafft. Es ist leicht zu erkennen, dass im mentalen Spiel die optimale Option für den Gegner, bezeichnet mit ˆQ\(\gamma\), ist derjenige, der zu Beginn des Zufalls die längste Folge böswilliger Benutzer erzeugt Permutation in Runde \(\gamma\) + 1. Tatsächlich hängt das Protokoll bei einem bestimmten Q\(\gamma\) nicht von Q\(\gamma\)−1 ab mehr und der Gegner kann sich ausschließlich auf die neue Permutation in Runde \(\gamma\) + 1 konzentrieren, die das hat gleiche Verteilung für die Anzahl böswilliger Benutzer zu Beginn. Dementsprechend in jeder Runde \(\gamma\), das oben erwähnte ˆQ\(\gamma\) gibt ihm die größte Anzahl an Optionen für Q\(\gamma\)+1 und maximiert somit die Wahrscheinlichkeit, dass die aufeinanderfolgenden Anführer alle böswillig sind. Daher folgt der Gegner im mentalen Spiel einer Markov-Kette aus Runde r − k um r −1 zu runden, wobei der Zustandsraum {0} \(\cup\){x : x \(\geq\)2} ist. Zustand 0 stellt die Tatsache dar, dass die Der erste Benutzer in der zufälligen Permutation in der aktuellen Runde \(\gamma\) ist ehrlich, daher scheitert der Gegner Spiel zur Vorhersage von Qr−1; und jeder Zustand x \(\geq\)2 stellt die Tatsache dar, dass die ersten x −1 Benutzer im Permutationen sind bösartig und das x-te ist ehrlich, daher hat der Gegner x Optionen für Q\(\gamma\). Die Übergangswahrscheinlichkeiten P(x, y) sind wie folgt. • P(0, 0) = 1 und P(0, y) = 0 für jedes y \(\geq\)2. Das heißt, der Gegner scheitert beim ersten Mal am Spiel Der Benutzer in der Permutation wird ehrlich. • P(x, 0) = hx für jedes x \(\geq\)2. Das heißt, mit der Wahrscheinlichkeit hx haben alle x zufälligen Permutationen Da ihre ersten Benutzer ehrlich sind, scheitert der Gegner in der nächsten Runde am Spiel. • Für jedes x \(\geq\)2 und y \(\geq\)2 ist P(x, y) die Wahrscheinlichkeit, dass unter den x zufälligen Permutationen Induziert durch die x-Optionen von Q\(\gamma\), der längsten Sequenz böswilliger Benutzer zu Beginn einige davon sind y −1, daher hat der Gegner in der nächsten Runde y Optionen für Q\(\gamma\)+1. Das heißt, P(x, y) = y−1 X i=0 (1 −h)ih !x − y−2 X i=0 (1 −h)ih !x = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x. Beachten Sie, dass Zustand 0 der einzige absorbierende Zustand in der Übergangsmatrix P und in jedem anderen Zustand ist x hat eine positive Wahrscheinlichkeit, gegen 0 zu gehen. Wir sind daran interessiert, die Zahl k von nach oben zu begrenzen Runden, die benötigt werden, damit die Markov-Kette mit überwältigender Wahrscheinlichkeit gegen 0 konvergiert: das heißt, nein Egal in welchem Zustand die Kette beginnt, mit überwältigender Wahrscheinlichkeit verliert der Gegner das Spiel und kann Qr−1 in der Runde r −k nicht vorhersagen. Betrachten Sie die Übergangsmatrix P (2) \(\triangleq\)P \(\cdot\) P nach zwei Runden. Es ist leicht zu erkennen, dass P (2)(0, 0) = 1 und P (2)(0, x) = 0 für jedes x \(\geq\)2. Für jedes x \(\geq\)2 und y \(\geq\)2 gilt, da P(0, y) = 0 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).Wenn ¯h \(\triangleq\)1 −h gilt, gilt P(x, y) = (1 −¯hy)x −(1 −¯hy−1)x und P (2)(x, y) = X z\(\geq\)2 [(1 −¯hz)x −(1 −¯hz−1)x][(1 −¯hy)z −(1 −¯hy−1)z]. Nachfolgend berechnen wir den Grenzwert von P (2)(x,y) P (x,y) wenn h auf 1 geht – das heißt, ¯h geht auf 0. Beachten Sie, dass die höchste Ordnung von ¯h in P(x, y) ist ¯hy−1, mit Koeffizient x. Dementsprechend 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. Wenn h hinreichend nahe bei 1,23 liegt, haben wir P (2)(x, y) P(x, y) \(\leq\)1 2 für jedes x \(\geq\)2 und y \(\geq\)2. Nach Induktion gilt für jedes k > 2 P (k) \(\triangleq\)P k, so dass • P (k)(0, 0) = 1, P (k)(0, x) = 0 für jedes x \(\geq\)2 und • für jedes x \(\geq\)2 und 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 . Da P(x, y) \(\leq\)1 ist, ist die Übergangswahrscheinlichkeit in einen beliebigen Zustand y \(\geq\)2 nach 1−log2 F-Runden vernachlässigbar, beginnend mit einem beliebigen Zustand x \(\geq\)2. Obwohl es viele solcher Zustände gibt, ist das leicht zu erkennen 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 − Std. Daher nimmt jede Zeile x der Übergangsmatrix P als geometrische Folge mit der Rate ab 1 1−h > 2 wenn y groß genug ist, und das Gleiche gilt für P (k). Dementsprechend ist k aber immer noch groß genug in der Größenordnung von log1/2 F, P y\(\geq\)2 P (k)(x, y) < F für jedes x \(\geq\)2. Das heißt, mit überwältigender Wahrscheinlichkeit Der Gegner verliert das Spiel und kann Qr−1 in Runde r −k nicht vorhersagen. Für h \(\in\)(2/3, 1], ein mehr Eine komplexe Analyse zeigt, dass es eine Konstante C gibt, die etwas größer als 1/2 ist, sodass sie ausreicht um k = O(logC F) zu nehmen. Somit gilt Lemma 5.6. ■ Lemma 5.4. (angepasst) Gegebene Eigenschaften 1–3 für jede Runde vor r, ph = h2(1 + h −h2) für Lr, und der Anführer \(\ell\)r ist mit Wahrscheinlichkeit mindestens ph ehrlich. 23Zum Beispiel ist h = 80 %, wie aus der spezifischen Auswahl der Parameter hervorgeht.

Beweis. Nach Lemma 5.6 kann der Gegner Qr−1 nicht zurück zur Runde r −k vorhersagen, außer mit vernachlässigbare Wahrscheinlichkeit. Beachten Sie, dass dies nicht bedeutet, dass die Wahrscheinlichkeit eines ehrlichen Anführers h ist jede Runde. In der Tat, angesichts von Qr-1, abhängig davon, wie viele böswillige Benutzer zu Beginn vorhanden sind Durch die zufällige Permutation von PKr−k kann der Gegner mehr als eine Option für Qr und haben Dadurch kann die Wahrscheinlichkeit eines böswilligen Anführers in Runde r + 1 erhöht werden – wir geben ihn wiederum an einige unrealistische Vorteile wie in Lemma 5.6, um die Analyse zu vereinfachen. Allerdings gilt für jedes Qr−1, das vom Gegner in der Runde r −k nicht an H abgefragt wurde, für Jedes x \(\geq\)1, mit der Wahrscheinlichkeit (1 −h)x−1h, tritt der erste ehrliche Benutzer an Position x im Ergebnis auf zufällige Permutation von PKr−k. Wenn x = 1, beträgt die Wahrscheinlichkeit eines ehrlichen Anführers in Runde r + 1 tatsächlich h; Wenn hingegen x = 2, hat der Gegner zwei Optionen für Qr und die resultierende Wahrscheinlichkeit ist h2. Nur wenn wir diese beiden Fälle berücksichtigen, haben wir die Wahrscheinlichkeit eines ehrlichen Anführers in der Runde r + 1 ist mindestens h \(\cdot\) h + (1 − h)h \(\cdot\) h2 = h2(1 + h − h2) wie gewünscht. Beachten Sie, dass die obige Wahrscheinlichkeit nur die Zufälligkeit im Protokoll ab Runde r − k berücksichtigt r runden. Wenn die gesamte Zufälligkeit von Runde 0 bis Runde r berücksichtigt wird, ist Qr−1 noch weniger vorhersehbar für den Gegner und die Wahrscheinlichkeit eines ehrlichen Anführers in Runde r + 1 liegt bei mindestens h2(1 + h −h2). Ersetzt man r + 1 durch r und verschiebt alles um eine Runde zurück, den Anführer \(\ell\)r ist ehrlich mit einer Wahrscheinlichkeit von mindestens h2(1 + h − h2), wie gewünscht. In ähnlicher Weise ist in jedem Coin-Echt-Flipped-Schritt s der „Anführer“ dieses Schritts – das ist der Verifizierer in SV r,s, dessen Credential den kleinsten hash-Wert hat, ist mit einer Wahrscheinlichkeit von mindestens h2(1 +) ehrlich h − h2). Somit ist ph = h2(1 + h −h2) für Lr und es gilt Lemma 5.4. ■

Algorand ′

2 In diesem Abschnitt erstellen wir eine Version von Algorand ′, die unter der folgenden Annahme arbeitet. Annahme: Ehrliche Mehrheit der Benutzer: Mehr als 2/3 der Benutzer in jedem PKr sind ehrlich. In Abschnitt 8 zeigen wir, wie man die obige Annahme durch die gewünschte ehrliche Mehrheit ersetzt Geldannahme. 6.1 Zusätzliche Notationen und Parameter für Algorand ′ 2 Notationen • \(\mu\) \(\in\)Z+: eine pragmatische Obergrenze für die Anzahl der Schritte, die mit überwältigender Wahrscheinlichkeit wird tatsächlich in einer Runde genommen. (Wie wir sehen werden, steuert der Parameter \(\mu\), wie viele ephemere Schlüssel, die ein Benutzer im Voraus für jede Runde vorbereitet.) • Lr: eine Zufallsvariable, die die Anzahl der Bernoulli-Versuche darstellt, die erforderlich sind, um jeweils eine 1 zu sehen Versuch ist 1 mit Wahrscheinlichkeit ph 2 . Lr wird verwendet, um die für die Generierung benötigte Zeit nach oben zu begrenzen Block Br. • tH: eine Untergrenze für die Anzahl ehrlicher Verifizierer in einem Schritt s > 1 der Runde r, so dass mit Überwältigende Wahrscheinlichkeit (vorausgesetzt n und p), es gibt > tH ehrliche Verifizierer in SV r,s. Parameter • Beziehungen zwischen verschiedenen Parametern. — Für jeden Schritt s > 1 der Runde r wird n so gewählt, dass mit überwältigender Wahrscheinlichkeit

|HSV r,s| > tH und |HSV r,s| + 2|MSV r,s| < 2tH. Beachten Sie, dass die beiden obigen Ungleichungen zusammen |HSV r,s| implizieren > 2|MSV r,s|: das heißt, dort ist eine 2/3 ehrliche Mehrheit unter den ausgewählten Prüfern. Je näher der Wert von h an 1 liegt, desto kleiner muss n sein. Insbesondere verwenden wir (Varianten von) Chernoff-Grenzen, um sicherzustellen, dass die gewünschten Bedingungen mit überwältigender Wahrscheinlichkeit eintreten. • Beispielhafte Auswahl wichtiger Parameter. — F = 10−18. — n \(\approx\)4000, tH \(\approx\)0,69n, k = 70. 6.2 Implementierung kurzlebiger Schlüssel in Algorand ′ 2 Denken Sie daran, dass ein Verifizierer i \(\in\)SV r,s seine Nachricht mr,s digital signiert ich der Schritte s in Runde r, relativ zu ein kurzlebiger öffentlicher Schlüssel pkr,s i , unter Verwendung eines kurzlebigen geheimen Schlüssels skr,s ich dass er sofort zerstört nach der Verwendung. Wenn die Anzahl der möglichen Schritte, die eine Runde machen darf, durch eine bestimmte Grenze begrenzt ist Ganzzahl \(\mu\) haben wir bereits gesehen, wie man ephemere Schlüssel praktisch handhabt. Zum Beispiel, wie wir habe erklärt in Algorand ′ 1 (wobei \(\mu\) = m + 3), um alle seine möglichen kurzlebigen Schlüssel zu verarbeiten Eine Runde r′ zu einer Runde r′ + 106, i erzeugt ein Paar (PMK, SMK), wobei PMK öffentlicher Master ist Schlüssel eines identitätsbasierten Signaturschemas und SMK sein entsprechender geheimer Hauptschlüssel. Benutzer i veröffentlicht PMK und verwendet SMK, um den geheimen Schlüssel jedes möglichen kurzlebigen öffentlichen Schlüssels zu generieren (und zerstört danach SMK). Der Satz der kurzlebigen öffentlichen Schlüssel von i für das relevante Runden ist S = {i} \(\times\) {r′, . . . , r′ + 106} \(\times\) {1, . . . , \(\mu\)}. (Wie besprochen, wenn sich die Runde r′ + 106 nähert, Ich „aktualisiere“ sein Paar (PMK, SMK).) In der Praxis ergibt sich, wenn \(\mu\) groß genug ist, eine Runde von Algorand ′ 2 dauert nicht mehr als \(\mu\)-Schritte. In Prinzipiell besteht jedoch die entfernte Möglichkeit, dass für einige Runden die Anzahl der Schritte r ist tatsächlich eingenommen wird \(\mu\) überschreiten. Wenn das passiert, könnte ich seine Nachricht nicht unterschreiben, Herr ich für jeder Schritt s > \(\mu\), da er im Voraus nur \(\mu\) geheime Schlüssel für Runde r vorbereitet hat. Außerdem, er konnte, wie bereits besprochen, keinen neuen Vorrat an kurzlebigen Schlüsseln vorbereiten und veröffentlichen. Tatsächlich zu tun Daher müsste er einen neuen öffentlichen Hauptschlüssel PMK′ in einen neuen Block einfügen. Aber sollte r runden Wenn Sie immer mehr Schritte ausführen, werden keine neuen Blöcke generiert. Es gibt jedoch Lösungen. Zum Beispiel kann ich den letzten kurzlebigen Schlüssel der Runde r, pkr,\(\mu\) verwenden ich , wie folgt. Er generiert einen weiteren Vorrat an Schlüsselpaaren für Runde r – z. B. indem er (1) ein weiteres generiert Hauptschlüsselpaar (PMK, SMK); (2) Verwenden dieses Paares, um weitere, sagen wir, 106 kurzlebige Schlüssel zu generieren, sk r,\(\mu\)+1 ich , . . . , sk r,\(\mu\)+106 ich , entsprechend den Schritten \(\mu\)+1, ..., \(\mu\)+106 der Runde r; (3) mit skr,\(\mu\) ich zu digital Vorzeichen PMK (und jede (r, \(\mu\))-Nachricht, wenn i \(\in\)SV r,\(\mu\)), relativ zu pkr,\(\mu\) ich ; und (4) Löschen von SMK und skr,\(\mu\) ich . Soll ich in einem Schritt \(\mu\) + s mit s \(\in\){1, . . . , 106}, dann unterschreibe ich digital seine (r, \(\mu\) + s)- Nachricht mr,\(\mu\)+s ich relativ zu seinem neuen Schlüssel pk r,\(\mu\)+s ich = (i, r, \(\mu\) + s). Natürlich, um diese Signatur zu überprüfen Von i müssen andere sicher sein, dass dieser öffentliche Schlüssel dem neuen öffentlichen Hauptschlüssel PMK von i entspricht. Somit übermittelt i zusätzlich zu dieser Signatur seine digitale Signatur von PMK relativ zu pkr,\(\mu\) ich . Natürlich kann dieser Ansatz so oft wie nötig wiederholt werden, falls die Runde fortgesetzt wird für immer mehr Schritte! Der letzte ephemere geheime Schlüssel wird zur Authentifizierung einer neuen Master-Öffentlichkeit verwendet Schlüssel und damit ein weiterer Vorrat an kurzlebigen Schlüsseln für Runde r. Und so weiter.6.3 Das eigentliche Protokoll Algorand ′ 2 Erinnern Sie sich noch einmal daran, dass in jedem Schritt s einer Runde r ein Verifizierer i \(\in\)SV r,s sein langfristiges öffentliches Geheimnis verwendet Schlüsselpaar, um seinen Ausweis zu erzeugen, \(\sigma\)r,s ich \(\triangleq\)SIGi(r, s, Qr−1) sowie SIGi Qr−1 im Fall s = 1. Verifier i verwendet sein kurzlebiges Schlüsselpaar (pkr,s ich, skr,s i ), um jede andere Nachricht zu signieren erforderlich. Der Einfachheit halber schreiben wir esigi(m) statt sigpkr,s i (m), um die eigentliche Vergänglichkeit von i zu bezeichnen Signatur von m in diesem Schritt und schreiben Sie ESIGi(m) anstelle von SIGpkr,s i (m) \(\triangleq\)(i, m, esigi(m)). Schritt 1: Vorschlag blockieren Anweisungen für jeden Benutzer i \(\in\)PKr−k: Benutzer i beginnt seinen eigenen Schritt 1 der Runde r, sobald er dies getan hat CERT r−1, was es i ermöglicht, H(Br−1) und Qr−1 eindeutig zu berechnen. • Benutzer i verwendet Qr−1, um zu prüfen, ob i \(\in\)SV r,1 oder nicht. Wenn i /\(\in\)SV r,1, tut er für Schritt 1 nichts. • Wenn i \(\in\)SV r,1, das heißt, wenn i ein potenzieller Anführer ist, dann tut er Folgendes. (a) Wenn ich B0 gesehen habe, . . . , Br−1 selbst (jedes Bj = Bj ǫ kann leicht aus seinem hash-Wert abgeleitet werden in CERT j und wird daher als „gesehen“ angenommen), dann sammelt er die Round-R-Zahlungen ein, die er erhalten hat wurde ihm bisher propagiert und berechnet einen maximalen Payset PAY r ich von ihnen. (b) Wenn ich nicht alle B0 gesehen habe, . . . , Br−1 noch, dann setzt er PAY r ich = \(\emptyset\). (c) Als nächstes berechne ich seinen „Kandidatenblock“ Br i = (r, PAY r i , SIGi(Qr−1), H(Br−1)). (c) Schließlich berechnet i die Nachricht mr,1 ich = (Br ich, esigi(H(Br i )), \(\sigma\)r,1 i ), zerstört sein Vergängliches geheimer Schlüssel skr,1 i und verbreitet dann zwei Nachrichten, mr,1 ich und (SIGi(Qr−1), \(\sigma\)r,1 ich), getrennt, aber gleichzeitig.a aWenn i der Anführer ist, ermöglicht SIGi(Qr−1) anderen die Berechnung von Qr = H(SIGi(Qr−1), r).

Selektive Vermehrung Um die globale Ausführung von Schritt 1 und der gesamten Runde zu verkürzen, ist es wichtig, dass die (r, 1)- Nachrichten werden selektiv verbreitet. Das heißt, für jeden Benutzer j im System • Für die erste (r, 1)-Nachricht, die er jemals empfängt und erfolgreich überprüft, ob sie Folgendes enthält ein Block oder nur ein Berechtigungsnachweis und eine Signatur von Qr−1 ist, propagiert Spieler j ihn wie gewohnt. • Für alle anderen (r, 1)-Nachrichten, die Spieler j empfängt und erfolgreich verifiziert, propagiert er Dies gilt nur, wenn der hash-Wert der darin enthaltenen Anmeldeinformationen der kleinste unter den hash-Werten ist der in allen (r, 1)-Nachrichten enthaltenen Anmeldeinformationen, die er erhalten hat, und hat dies erfolgreich überprüft weit. • Empfängt j jedoch zwei verschiedene Nachrichten der Form mr,1 ich vom selben Spieler i,b er verwirft den zweiten, unabhängig vom hash-Wert der Anmeldeinformationen von i. Beachten Sie, dass es bei der selektiven Propagierung nützlich ist, dass jeder potenzielle Anführer seinen eigenen propagiert Ausweis \(\sigma\)r,1 ich getrennt von Herrn,1 i :c Diese kleinen Nachrichten verbreiten sich schneller als Blöcke, stellen Sie sicher rechtzeitige Ausbreitung des Herrn,1 i ist dort, wo die enthaltenen Anmeldeinformationen kleine hash-Werte haben, während Lassen Sie solche mit großen hash-Werten schnell verschwinden. aDas heißt, alle Signaturen sind korrekt und wenn es sich um die Form mr,1 handelt i , sowohl der Block als auch sein hash sind gültig – obwohl j nicht prüft, ob der enthaltene Gehaltssatz für i maximal ist oder nicht. bWas bedeutet, dass ich böswillig bin. cWir danken Georgios Vlachos für diesen Vorschlag.Schritt 2: Der erste Schritt des Graded Consensus Protocol GC Anweisungen für jeden Benutzer i \(\in\)PKr−k: Benutzer i beginnt seinen eigenen Schritt 2 der Runde r, sobald er dies getan hat CERT r−1. • Benutzer i wartet maximal t2 \(\triangleq\) \(\lambda\) + Λ. Während ich warte, verhalte ich mich wie folgt. 1. Nachdem er die Zeit 2\(\lambda\) abgewartet hat, findet er den Benutzer \(\ell\)so dass H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j) für alle Referenzen \(\sigma\)r,1 j die Teil der erfolgreich verifizierten (r, 1)-Nachrichten sind, die er erhalten hat bisher.a 2. Wenn er hat erhalten a blockieren Br−1, welche Streichhölzer die hash Wert H(Br−1) im CERT r−1,b enthalten ist und ob er von \(\ell\)eine gültige Nachricht mr,1 erhalten hat \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),c dann hört i auf zu warten und setzt v′ i \(\triangleq\)(H(Br \(\ell\)), \(\ell\)). 3. Andernfalls, wenn die Zeit t2 abläuft, setzt i v′ ich \(\triangleq\) \(\bot\). 4. Wenn der Wert von v′ i wurde gesetzt, i berechnet Qr−1 aus CERT r−1 und prüft, ob i \(\in\)SV r,2 oder nicht. 5. Wenn i \(\in\)SV r,2, berechnet i die Nachricht mr,2 ich \(\triangleq\)(ESIGi(v′ i), \(\sigma\)r,2 i ),d zerstört sein Vergängliches geheimer Schlüssel skr,2 i und propagiert dann mr,2 ich . Ansonsten höre ich auf, ohne mich weiterzuverbreiten irgendetwas. aIm Wesentlichen entscheidet Benutzer i privat, dass der Anführer der Runde r Benutzer \(\ell\) ist. bNatürlich, wenn CERT r−1 anzeigt, dass Br−1 = Br−1 ǫ , dann habe ich Br−1 in dem Moment, in dem er es hat, bereits „erhalten“. CERT r−1. cAuch hier sind die Unterschriften von Spieler \(\ell\) und die hashes alle erfolgreich verifiziert und ZAHLEN r \(\ell\)in Br \(\ell\)ist ein gültiger Gehaltssatz für rundes r – obwohl ich nicht prüfe, ob PAY r \(\ell\)ist maximal für \(\ell\)oder nicht. Wenn Br \(\ell\)enthält dann einen leeren Gehaltssatz Eigentlich ist es nicht nötig, dass ich Br−1 sehe, bevor ich verifiziere, ob Br \(\ell\)ist gültig oder nicht. dDie Nachricht mr,2 ich signalisiert, dass Spieler i die erste Komponente von v′ betrachtet i soll der hash des nächsten Blocks sein, oder betrachtet den nächsten Block als leer.

Schritt 3: Der zweite Schritt der GC Anweisungen für jeden Benutzer i \(\in\)PKr−k: Benutzer i beginnt seinen eigenen Schritt 3 der Runde r, sobald er dies getan hat CERT r−1. • Benutzer i wartet maximal t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ. Während ich warte, verhalte ich mich wie folgt. 1. Wenn ein Wert v existiert, so dass er mindestens die gültigen Nachrichten mr,2 erhalten hat j von die Form (ESIGj(v), \(\sigma\)r,2 j ), ohne jeden Widerspruch,a dann hört er auf zu warten und setzt v′ = v. 2. Ansonsten setzt er nach Ablauf der Zeit t3 v′ = \(\bot\). 3. Wenn der Wert von v′ festgelegt wurde, berechnet i Qr−1 aus CERT r−1 und prüft, ob i \(\in\)SV r,3 oder nicht. 4. Wenn i \(\in\)SV r,3, dann berechnet i die Nachricht mr,3 ich \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 i ), zerstört seine Vergänglicher geheimer Schlüssel skr,3 i und propagiert dann mr,3 ich . Ansonsten höre ich ohne auf irgendetwas verbreiten. aDas heißt, er hat keine zwei gültigen Nachrichten erhalten, die ESIGj(v) bzw. ein anderes ESIGj(ˆv) enthalten. von einem Spieler j. Hier und von nun an, außer in den später definierten Endbedingungen, wann immer ein ehrlicher Spieler Will Nachrichten einer bestimmten Form, werden widersprüchliche Nachrichten niemals gezählt oder als gültig angesehen.

Schritt 4: Ausgabe von GC und der erste Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seinen eigenen Schritt 4 der Runde r, sobald er beendet seinen eigenen Schritt 3. • Benutzer i wartet maximal 2\(\lambda\).a Während des Wartens verhält sich i wie folgt. 1. Er berechnet vi und gi, die Ausgabe von GC, wie folgt. (a) Wenn es einen Wert v′ ̸= \(\bot\) gibt, so dass er mindestens die gültigen Nachrichten erhalten hat Herr,3 j = (ESIGj(v′), \(\sigma\)r,3 j ), dann hört er auf zu warten und setzt vi \(\triangleq\)v′ und gi \(\triangleq\)2. (b) Wenn er mindestens die gültigen Nachrichten mr,3 erhalten hat j = (ESIGj(\(\bot\)), \(\sigma\)r,3 j ), dann bleibt er stehen wartet und setzt vi \(\triangleq\) \(\bot\)und gi \(\triangleq\)0.b (c) Ansonsten, wenn die Zeit 2\(\lambda\) abläuft, wenn es einen Wert v′ ̸= \(\bot\) gibt, den er hat mindestens ⌈tH erhalten 2 ⌉gültige Nachrichten mr,j j = (ESIGj(v′), \(\sigma\)r,3 j ), dann setzt er vi \(\triangleq\)v′ und gi \(\triangleq\)1.c (d) Andernfalls, wenn die Zeit 2\(\lambda\) abläuft, setzt er vi \(\triangleq\) \(\bot\)und gi \(\triangleq\)0. 2. Wenn die Werte vi und gi festgelegt wurden, berechnet i bi, die Eingabe von BBA⋆, wie folgt: bi \(\triangleq\)0, wenn gi = 2, andernfalls bi \(\triangleq\)1. 3. i berechnet Qr−1 aus CERT r−1 und prüft, ob i \(\in\)SV r,4 oder nicht. 4. Wenn i \(\in\)SV r,4, berechnet er die Nachricht mr,4 ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), zerstört seine Vergänglicher geheimer Schlüssel skr,4 i , und propagiert mr,4 ich . Ansonsten höre ich auf, ohne mich weiterzuverbreiten irgendetwas. aSomit könnte die maximale Gesamtzeit seit Beginn von Schritt 1 der Runde r t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ betragen. bOb Schritt (b) im Protokoll enthalten ist oder nicht, hat keinen Einfluss auf dessen Richtigkeit. Das Vorhandensein von Schritt (b) ermöglicht, dass Schritt 4 in weniger als 2\(\lambda\) Zeit endet, wenn ausreichend viele Prüfer von Schritt 3 „\(\bot\) signiert“ haben. cEs kann bewiesen werden, dass das v′ in diesem Fall, falls vorhanden, eindeutig sein muss.Schritt s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: Ein Coin-Fixed-To-0-Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seine eigenen Schritte s der Runde r, sobald er beendet seinen eigenen Schritt s −1. • Benutzer i wartet maximal 2\(\lambda\).a Während des Wartens verhält sich i wie folgt. – Endbedingung 0: Wenn an irgendeinem Punkt eine Zeichenfolge v ̸= \(\bot\)und ein Schritt s′ existiert, so dass (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 – das heißt, Schritt s′ ist ein Coin-Fixed-To-0-Schritt, (b) i hat mindestens die gültigen Nachrichten mr,s′−1 erhalten j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),b und (c) i hat eine gültige Nachricht erhalten (SIGj(Qr−1), \(\sigma\)r,1 j ), wobei j der zweite ist Komponente von v, dann hört i auf zu warten und beendet seine eigene Ausführung von Schritt s (und tatsächlich auch von Runde r) sofort, ohne etwas als (r, s)-Verifizierer zu propagieren; setzt H(Br) als erstes Komponente von v; und setzt sein eigenes CERT r auf die Menge der Nachrichten mr,s′−1 j von Schritt (b) zusammen mit (SIGj(Qr−1), \(\sigma\)r,1 j ).c – Endbedingung 1: Wenn es an irgendeinem Punkt einen Schritt s′ gibt, so dass (a’) 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 – das heißt, Schritt s′ ist ein Coin-Fixed-To-1-Schritt, und (b’) i hat mindestens die gültigen Nachrichten mr,s′−1 erhalten j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),d dann hört i auf zu warten und beendet seine eigene Ausführung von Schritt s (und tatsächlich auch von Runde r) richtig weg, ohne etwas als (r, s)-Verifizierer zu propagieren; setzt Br = Br ǫ ; und legt sein eigenes fest CERT r soll die Menge der Nachrichten mr,s′−1 sein j des Teilschritts (b‘). – Wenn bei irgendein Punkt er hat erhalten bei am wenigsten tH gültig mr,s−1 j ’s von die Formular (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), dann hört er auf zu warten und setzt bi \(\triangleq\)1. – Wenn bei irgendein Punkt er hat erhalten bei am wenigsten tH gültig mr,s−1 j ’s von die Formular (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), aber sie sind sich nicht auf dasselbe v einig, dann hört er auf wartet und setzt bi \(\triangleq\)0. – Ansonsten setzt i nach Ablauf der Zeit 2\(\lambda\) bi \(\triangleq\)0. – Wenn der Wert bi gesetzt wurde, berechnet i Qr−1 aus CERT r−1 und prüft, ob i \(\in\)SV r,s. – Wenn i \(\in\)SV r,s, berechnet i die Nachricht mr,s ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) mit vi Der Wert, den er in Schritt 4 berechnet hat, zerstört seinen kurzlebigen Geheimschlüssel skr,s ich, und dann propagiert mr,s ich . Andernfalls höre ich auf, ohne etwas zu verbreiten. aSomit könnte die maximale Gesamtzeit seit Beginn von Schritt 1 der Runde r ts \(\triangleq\)ts−1 + 2\(\lambda\) = sein (2s −3)\(\lambda\) + Λ. bEine solche Nachricht von Spieler j wird auch dann gezählt, wenn Spieler i auch eine Nachricht von j erhalten hat, der für 1 signiert. Ähnliches gilt für Endbedingung 1. Wie in der Analyse gezeigt, soll damit sichergestellt werden, dass alle ehrlichen Benutzer Bescheid wissen CERT r innerhalb der Zeit \(\lambda\) voneinander entfernt. cUser i kennt jetzt H(Br) und seine eigenen Rundenenden. Er muss nur warten, bis der eigentliche Block Br ist an ihn weitergeleitet, was einige Zeit in Anspruch nehmen kann. Als allgemeiner Benutzer hilft er immer noch bei der Verbreitung von Nachrichten. löst aber keine Ausbreitung als (r, s)-Verifizierer aus. Insbesondere hat er dabei geholfen, alle Botschaften zu verbreiten sein CERT r, was für unser Protokoll ausreicht. Beachten Sie, dass er auch für das binäre BA-Protokoll bi \(\triangleq\)0 festlegen sollte, aber bi wird in diesem Fall sowieso nicht benötigt. Ähnliches gilt für alle zukünftigen Anweisungen. dIn diesem Fall spielt es keine Rolle, um welche VJs es sich handelt. 65Schritt s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: Ein Coin-Fixed-To-1-Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seine eigenen Schritte s der Runde r, sobald er beendet seinen eigenen Schritt s −1. • Benutzer i wartet maximal 2\(\lambda\). Während ich warte, verhalte ich mich wie folgt. – Endbedingung 0: Dieselben Anweisungen wie in einem Coin-Fixed-To-0-Schritt. – Endbedingung 1: Die gleichen Anweisungen wie in einem Coin-Fixed-To-0-Schritt. – Wenn bei irgendein Punkt er hat erhalten bei am wenigsten tH gültig mr,s−1 j ’s von die Formular (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), dann hört er auf zu warten und setzt bi \(\triangleq\)0.a – Andernfalls, wenn die Zeit 2\(\lambda\) abläuft, setzt i bi \(\triangleq\)1. – Wenn der Wert bi gesetzt wurde, berechnet i Qr−1 aus CERT r−1 und prüft, ob i \(\in\)SV r,s. – Wenn i \(\in\)SV r,s, berechnet i die Nachricht mr,s ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) mit vi Der Wert, den er in Schritt 4 berechnet hat, zerstört seinen kurzlebigen Geheimschlüssel skr,s ich, und dann propagiert mr,s ich . Andernfalls höre ich auf, ohne etwas zu verbreiten. aBeachten Sie, dass der Empfang gültiger (r, s −1)-Nachrichten mit der Signatur 1 die Endbedingung 1 bedeuten würde. Schritt s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Ein münzecht umgedrehter Schritt von BBA⋆ Anleitung für jeden Benutzer i \(\in\)PKr−k: Benutzer i startet seine eigenen Schritte s der Runde r, sobald er beendet seinen eigenen Schritt s −1. • Benutzer i wartet maximal 2\(\lambda\). Während ich warte, verhalte ich mich wie folgt. – Endbedingung 0: Dieselben Anweisungen wie in einem Coin-Fixed-To-0-Schritt. – Endbedingung 1: Die gleichen Anweisungen wie in einem Coin-Fixed-To-0-Schritt. – Wenn bei irgendein Punkt er hat erhalten bei am wenigsten tH gültig mr,s−1 j ’s von die Formular (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), dann hört er auf zu warten und setzt bi \(\triangleq\)0. – Wenn bei irgendein Punkt er hat erhalten bei am wenigsten tH gültig mr,s−1 j ’s von die Formular (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), dann hört er auf zu warten und setzt bi \(\triangleq\)1. – Andernfalls, wenn die Zeit 2\(\lambda\) abläuft, gilt SV r,s−1 ich sei die Menge der (r, s −1)-Verifizierer aus wem er eine gültige Nachricht erhalten hat mr,s−1 j , i setzt bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 ich H(\(\sigma\)r,s−1 j )). – Wenn der Wert bi gesetzt wurde, berechnet i Qr−1 aus CERT r−1 und prüft, ob i \(\in\)SV r,s. – Wenn i \(\in\)SV r,s, berechnet i die Nachricht mr,s ich \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) mit vi Der Wert, den er in Schritt 4 berechnet hat, zerstört seinen kurzlebigen Geheimschlüssel skr,s ich, und dann propagiert mr,s ich . Andernfalls höre ich auf, ohne etwas zu verbreiten. Bemerkung. Im Prinzip kann das Protokoll, wie in Unterabschnitt 6.2 dargelegt, beliebig viele annehmen Schritte in einer Runde. Sollte dies passieren, wie besprochen, ist ein Benutzer i \(\in\)SV r,s mit s > \(\mu\) erschöpft

seinen Vorrat an vorgenerierten kurzlebigen Schlüsseln und muss seine (r, s)-Nachricht mr,s authentifizieren ich von a „Kaskade“ vergänglicher Schlüssel. Dadurch wird meine Nachricht etwas länger und die Übermittlung dieser Daten länger Nachrichten werden etwas länger dauern. Dementsprechend ist nach so vielen Schritten einer bestimmten Runde der Wert von Der Parameter \(\lambda\) erhöht sich automatisch leicht. (Aber es kehrt erneut zum ursprünglichen \(\lambda\) zurück Block wird produziert und eine neue Runde beginnt.) Rekonstruktion des Round-r-Blocks durch Nicht-Verifizierer Anleitung für jeden Benutzer i im System: Benutzer i startet seine eigene Runde r, sobald er sie hat CERT r−1. • Ich befolge die Anweisungen jedes Schritts des Protokolls und beteilige mich an der Verbreitung aller Nachrichten, initiiert jedoch keine Weitergabe in einem Schritt, wenn er darin kein Verifizierer ist. • i beendet seine eigene Runde r, indem er in einigen Fällen entweder die Endbedingung 0 oder die Endbedingung 1 eingibt Schritt, mit dem entsprechenden CERT r. • Von da an beginnt er seine Runde r + 1, während er darauf wartet, den eigentlichen Block Br zu erhalten (es sei denn er hat es bereits erhalten), dessen hash H(Br) von CERT r festgelegt wurde. Nochmals, wenn CERT r gibt an, dass Br = Br ǫ, das i weiß Br, sobald er CERT r hat. 6.4 Analyse von Algorand ′ 2 Die Analyse von Algorand ′ 2 lässt sich leicht aus dem von Algorand ′ ableiten 1. Im Wesentlichen in Algorand ′ 2, mit überwältigende Wahrscheinlichkeit, (a) alle ehrlichen Benutzer stimmen dem gleichen Block Br zu; der Anführer eines neuen Block ist mit einer Wahrscheinlichkeit von mindestens ph = h2(1 + h − h2) ehrlich.

Umgang mit ehrlichen Offline-Benutzern

Wie bereits erwähnt, befolgt ein ehrlicher Benutzer alle ihm vorgeschriebenen Anweisungen, einschließlich der Anweisungen, online zu sein und Ausführen des Protokolls. Dies stellt in Algorand keine große Belastung dar, da die Berechnung und Die von einem ehrlichen Benutzer benötigte Bandbreite ist recht bescheiden. Dennoch möchten wir darauf hinweisen, dass Algorand dies kann lässt sich leicht modifizieren, um in zwei Modellen zu funktionieren, in denen ehrliche Benutzer offline sein können tolle Zahlen. Bevor wir diese beiden Modelle diskutieren, möchten wir darauf hinweisen, dass der Prozentsatz ehrlicher Spieler groß ist 95 % betrugen, konnte Algorand immer noch ausgeführt werden, indem alle Parameter eingestellt wurden, wobei stattdessen davon ausgegangen wurde, dass h = 80 % ist. Demnach würde Algorand auch bei höchstens der Hälfte der ehrlichen Spieler weiterhin einwandfrei funktionieren entschied sich dafür, offline zu gehen (in der Tat ein schwerwiegender Fall von „Abwesenheit“). Zumindest zu jedem Zeitpunkt 80 % der Online-Spieler wären ehrlich. Von der kontinuierlichen Teilnahme zur faulen Ehrlichkeit Wie wir gesehen haben, Algorand ′ 1 und Algorand ′ 2 wählen der Lookback-Parameter k. Lassen Sie uns nun zeigen, dass die richtige Wahl von k das Entfernen ermöglicht die Anforderung der kontinuierlichen Teilnahme. Diese Anforderung gewährleistet eine entscheidende Eigenschaft: nämlich dass das zugrunde liegende BA-Protokoll BBA⋆eine angemessene ehrliche Mehrheit hat. Lassen Sie uns nun erklären, wie faul Ehrlichkeit bietet eine alternative und attraktive Möglichkeit, diese Immobilie zufriedenzustellen.

Denken Sie daran, dass ein Benutzer faul, aber ehrlich ist, wenn (1) er alle ihm vorgeschriebenen Anweisungen befolgt er wird gebeten, am Protokoll teilzunehmen, und (2) er wird gebeten, nur am Protokoll teilzunehmen sehr selten – z. B. einmal pro Woche – mit angemessener Vorankündigung und möglicherweise erheblichem Empfang Belohnungen, wenn er mitmacht. Damit Algorand mit solchen Playern arbeiten kann, reicht es lediglich aus, „die Verifizierer der auszuwählen.“ aktuelle Runde unter den Benutzern, die bereits in einer viel früheren Runde im System waren.“ Denken Sie daran Die Verifizierer für eine Runde r werden aus den Benutzern in Runde r − k ausgewählt und die Auswahl erfolgt basierend auf der Größe Qr−1. Beachten Sie, dass eine Woche aus etwa 10.000 Minuten besteht, und gehen Sie davon aus, dass a Eine Runde dauert etwa (z. B. im Durchschnitt) 5 Minuten, eine Woche hat also etwa 2.000 Runden. Angenommen dass ein Benutzer irgendwann seine Zeit planen und wissen möchte, ob er es sein wird ein Gutachter in der kommenden Woche. Das Protokoll wählt nun die Verifizierer für eine Runde aus den Benutzern aus runden r −k −2.000 ab, und die Auswahlen basieren auf Qr−2.001. In Runde R, Spieler, den ich bereits kenne die Werte Qr−2.000, . . . , Qr−1, da sie tatsächlich Teil von blockchain sind. Dann gilt für jedes M zwischen 1 und 2.000 ist i genau dann ein Verifizierer in einem Schritt s der Runde r + M, wenn .H SIGi r + M, s, Qr+M−2.001 \(\leq\)p . Ich muss also prüfen, ob er in den nächsten 2.000 Runden als Prüfer berufen wird Berechnen Sie \(\sigma\)M,s ich = SIGi r + M, s, Qr+M−2.001 für M = 1 bis 2.000 und für jeden Schritt s und überprüfen ob .H(\(\sigma\)M,s ich ) \(\leq\)p für einige von ihnen. Wenn die Berechnung einer digitalen Signatur eine Millisekunde dauert, dann Dieser gesamte Vorgang wird etwa 1 Minute Rechenzeit in Anspruch nehmen. Wenn er nicht als Prüfer ausgewählt wird In jeder dieser Runden kann er mit „ehrlichem Gewissen“ offline gehen. Hatte er ununterbrochen teilgenommen hätte, hätte er in den nächsten 2.000 Runden ohnehin im Wesentlichen 0 Schritte gemacht! Wenn stattdessen Er wird in einer dieser Runden als Prüfer ausgewählt und bereitet sich dann darauf vor (z. B. indem er alle Informationen erhält die erforderlichen Informationen), um bei der richtigen Runde als ehrlicher Prüfer zu fungieren. Durch dieses Verhalten entgeht mir als fauler, aber ehrlicher potenzieller Prüfer nur die Beteiligung an der Verbreitung von Nachrichten. Aber die Nachrichtenweitergabe ist normalerweise robust. Darüber hinaus sind die Zahler und Zahlungsempfänger von Von kürzlich propagierten Zahlungen wird erwartet, dass sie online sind, um zu beobachten, was mit ihren Zahlungen passiert. und somit werden sie sich an der Nachrichtenverbreitung beteiligen, wenn sie ehrlich sind.

Protokoll Algorand ′ mit ehrlicher Mehrheit des Geldes

Wir zeigen nun endlich, wie man die Annahme „Ehrliche Mehrheit der Benutzer“ durch viel mehr ersetzen kann sinnvolle Annahme der ehrlichen Mehrheit des Geldes. Die Grundidee ist (in einer proof-of-stake-Variante) „um einen Benutzer i \(\in\)PKr−k auszuwählen, der zu SV r,s gehört, mit einem Gewicht (d. h. Entscheidungskraft) proportional zu der Geldbetrag, der mir gehört.“24 Durch unsere HMM-Annahme können wir entscheiden, ob dieser Betrag in der Runde r − k gehalten werden soll oder zu Beginn der Runde r. Vorausgesetzt, dass uns eine kontinuierliche Teilnahme nichts ausmacht, entscheiden wir uns dafür die letztere Wahl. (Um die kontinuierliche Teilnahme zu eliminieren, hätten wir uns für die erstere Option entschieden. Besser gesagt, für den Geldbetrag, der bei rund r −k −2.000 liegt.) Es gibt viele Möglichkeiten, diese Idee umzusetzen. Der einfachste Weg wäre, jede Taste gedrückt zu halten höchstens 1 Geldeinheit und wähle dann zufällig n Benutzer i aus PKr−k aus, so dass a(r) ich = 1. 24Wir sollten PKr−k−2.000 sagen, um die kontinuierliche Teilnahme zu ersetzen. Der Einfachheit halber, da man es vielleicht verlangen möchte Bei kontinuierlicher Teilnahme verwenden wir wie zuvor PKr−k, um einen Parameter weniger zu tragen.

Die nächsteinfachste Implementierung Die nächsteinfachere Implementierung könnte darin bestehen, zu verlangen, dass jeder öffentliche Schlüssel einen Höchstbetrag besitzt Geldmenge M für ein bestimmtes festes M. Der Wert M ist klein genug im Vergleich zum Gesamtbetrag von Geld im System, so dass die Wahrscheinlichkeit, dass ein Schlüssel zur Verifizierermenge gehört, größer als eins ist Schritt in – sagen wir – k Runden ist vernachlässigbar. Dann ist ein Schlüssel i \(\in\)PKr−k, der einen Geldbetrag a(r) besitzt ich in Runde r, wird ausgewählt, um zu SV r,s zu gehören, wenn .H SIGi r, s, Qr−1 \(\leq\)p \(\cdot\) a(r) ich M . Und alles läuft wie bisher ab. Eine komplexere Implementierung Die letzte Implementierung „zwingte einen reichen Teilnehmer des Systems, viele Schlüssel zu besitzen“. Eine alternative Implementierung, die unten beschrieben wird, verallgemeinert den Begriff Status und Überlegung Jeder Benutzer i soll aus K + 1 Kopien (i, v) bestehen, von denen jede unabhängig als Verifizierer ausgewählt wird. und wird seinen eigenen vergänglichen Schlüssel besitzen (pkr,s i,v, skr,s i,v) in einem Schritt s einer Runde r. Der Wert K hängt davon ab über den Geldbetrag a(r) ich im besitz von i in rund r. Sehen wir uns nun genauer an, wie ein solches System funktioniert. Anzahl der Exemplare Sei n die angestrebte erwartete Kardinalität jedes Verifizierersatzes und sei a(r) ich sei der Geldbetrag, der einem Benutzer i in Runde r gehört. Sei Ar der Gesamtbetrag des Geldes, das man besitzt von den Benutzern in PKr−k in Runde r, d. h. Ar = X i\(\in\)P Kr−k a(r) ich . Wenn i ein Benutzer in PKr−k ist, dann sind die Kopien von i (i, 1), . . . , (i, K + 1), wo K = $ n \(\cdot\) a(r) ich Ar % . Beispiel. Sei n = 1.000, Ar = 109 und a(r) ich = 3,7 Millionen. Dann, K = 103 \(\cdot\) (3,7 \(\cdot\) 106) 109  = ⌊3,7⌋= 3 . Prüfer und Anmeldeinformationen Sei ich ein Benutzer in PKr−k mit K + 1 Kopien. Für jedes v = 1, . . . , K, copy (i, v) gehört automatisch zu SV r,s. Das heißt, meine Qualifikation ist \(\sigma\)r,s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1), aber die entsprechende Bedingung wird .H(\(\sigma\)r,s i,v) \(\leq\)1, also immer wahr. Für copy (i, K + 1) prüft i für jeden Schritt s der Runde r, ob .H SIGi (i, K + 1), r, s, Qr−1 \(\leq\)a(r) ich n Ar −K .

Wenn ja, gehört Kopie (i, K + 1) zu SV r,s. Um es zu beweisen, gebe ich den Berechtigungsnachweis weiter \(\sigma\)r,1 i,K+1 = SIGi (i, K + 1), r, s, Qr−1 . Beispiel. Wie im vorherigen Beispiel sei n = 1K, a(r) ich = 3,7M, Ar = 1B und i hat 4 Kopien: (i, 1), . . . , (i, 4). Dann gehören die ersten 3 Kopien automatisch zu SV r,s. Für den 4. Konzeptionell wirft Algorand ′ unabhängig eine voreingenommene Münze, deren Kopfwahrscheinlichkeit 0,7 beträgt. Kopieren (i, 4) wird genau dann ausgewählt, wenn der Münzwurf „Kopf“ ist. (Natürlich wird dieser voreingenommene Münzwurf durch hashdurch hashing, signieren und vergleichen umgesetzt – wie wir Dies habe ich in dieser Arbeit die ganze Zeit über getan – um es mir zu ermöglichen, sein Ergebnis zu beweisen.) Alles wie gewohnt Nachdem erklärt wurde, wie Prüfer ausgewählt werden und welche Qualifikationen sie haben Bei jedem Schritt einer Runde r berechnet, ähnelt die Ausführung einer Runde der bereits erläuterten.

Umgang mit Forks

Da die Wahrscheinlichkeit von Forks auf 10−12 oder 10−18 reduziert wurde, ist die Handhabung praktisch unnötig sie in der entfernten Chance, dass sie auftreten. Algorand kann jedoch auch verschiedene Forks verwenden Abwicklungsverfahren, mit oder ohne Arbeitsnachweis. Eine Möglichkeit, die Benutzer anzuweisen, Forks aufzulösen, ist wie folgt: • Folgen Sie der längsten Kette, wenn ein Benutzer mehrere Ketten sieht. • Wenn es mehr als eine längste Kette gibt, folgen Sie der Kette mit einem nicht leeren Block am Ende. Wenn Alle von ihnen haben am Ende leere Blöcke, betrachten Sie die vorletzten Blöcke. • Wenn es mehr als eine längste Kette mit nicht leeren Blöcken am Ende gibt, sagen wir, dass es sich um Ketten handelt der Länge r, folgen Sie demjenigen, dessen Anführer von Block r den kleinsten Berechtigungsnachweis hat. Wenn es Unentschieden gibt, Folgen Sie demjenigen, dessen Block r selbst den kleinsten hash-Wert hat. Wenn es immer noch Unentschieden gibt, befolgen Sie die Anweisungen einer, dessen Block r lexikographisch der erste ist.

Umgang mit Netzwerkpartitionen

Wie gesagt gehen wir davon aus, dass die Ausbreitungszeiten von Nachrichten zwischen allen Benutzern im Netzwerk durch \(\lambda\) und Λ begrenzt sind. Dies ist keine starke Annahme, da das heutige Internet schnell und robust ist Die tatsächlichen Werte dieser Parameter sind durchaus angemessen. Lassen Sie uns hier darauf hinweisen, dass Algorand ′ 2 funktioniert weiterhin, auch wenn das Internet gelegentlich in zwei Teile geteilt wurde. Der Fall, wenn Das Internet ist in mehr als zwei Teile unterteilt. 10.1 Physische Partitionen Erstens kann die Teilung physikalische Ursachen haben. Zum Beispiel kann es zu einem großen Erdbeben kommen Am Ende wird die Verbindung zwischen Europa und Amerika völlig zerstört. In diesem Fall ist die böswillige Benutzer werden ebenfalls aufgeteilt und es findet keine Kommunikation zwischen den beiden Teilen statt. Also

Es wird zwei Gegner geben, einen für Teil 1 und einen für Teil 2. Jeder Gegner versucht es immer noch Brechen Sie das Protokoll in seinem eigenen Teil. Nehmen Sie an, dass die Teilung in der Mitte der Runde r erfolgt. Dann wird jeder Benutzer noch als ausgewählt Verifizierer basierend auf PKr−k, mit der gleichen Wahrscheinlichkeit wie zuvor. Lass den HSV r,s ich und MSV r,s ich bzw sei die Menge der ehrlichen und böswilligen Verifizierer in einem Schritt s in Teil i \(\in\){1, 2}. Wir haben |HSV r,s 1 | + |MSV r,s 1 | + |HSV r,s 2 | + |MSV r,s 2 | = |HSV r,s| + |MSV r,s|. Beachten Sie, dass |HSV r,s| + |MSV r,s| < |HSV r,s| + 2|MSV r,s| < 2tH mit überwältigender Wahrscheinlichkeit. Wenn ein Teil i |HSV r,s hat ich | + |MSV r,s ich | \(\geq\)tH mit nicht vernachlässigbarer Wahrscheinlichkeit, z. B. 1 %, dann ist die Wahrscheinlichkeit, dass |HSV r,s 3−i| + |MSV r,s 3−i| \(\geq\)tH ist sehr niedrig, z. B. 10−16, wenn F = 10−18. In diesem Fall, Wir können den kleineren Teil genauso gut als offline betrachten, da nicht genügend Verifizierer vorhanden sein werden Dieser Teil dient zum Generieren der Signaturen zur Zertifizierung eines Blocks. Betrachten wir den größeren Teil, sagen wir Teil 1, ohne die Allgemeingültigkeit zu verlieren. Obwohl |HSV r,s| < tH mit vernachlässigbarer Wahrscheinlichkeit in jedem Schritt s, wenn das Netzwerk partitioniert ist, |HSV r,s 1 | kann sein kleiner als tH mit einer nicht zu vernachlässigenden Wahrscheinlichkeit. In diesem Fall kann der Gegner mit einigen Andere nicht vernachlässigbare Wahrscheinlichkeiten zwingen das binäre BA-Protokoll in Runde r zu einer Verzweigung mit einem nicht leeren Block Br und dem leeren Block Br ǫ beide haben die gültigen Unterschriften.25 Beispielsweise in a Coin-Fixed-To-0-Schritte s, alle Verifizierer in HSV r,s 1 für Bit 0 und H(Br) signiert und weitergegeben Nachrichten. Alle Prüfer in MSV r,s 1 unterzeichneten ebenfalls 0 und H(Br), hielten ihre Nachrichten jedoch zurück. Weil |HSV r,s 1 | + |MSV r,s 1 | \(\geq\)tH, das System verfügt über genügend Unterschriften, um Br zu zertifizieren. Da jedoch die böswillige Verifizierer haben ihre Signaturen zurückgehalten, die Benutzer geben Schritt s + 1 ein, bei dem es sich um einen Coin-Fixed-To1-Schritt handelt. Weil |HSV r,s 1 | < tH aufgrund der Partition, die Prüfer im HSV r,s+1 1 habe das nicht gesehen Signaturen für Bit 0 und alle signierten für Bit 1. Alle Prüfer in MSV r,s+1 1 habe das Gleiche getan. Weil |HSV r,s+1 1 | + |MSV r,s+1 1 | \(\geq\)tH, das System verfügt über genügend Unterschriften, um Br zu zertifizieren ǫ. Der Gegner erstellt dann einen Fork, indem er die Signaturen von MSV r,s freigibt 1 für 0 und H(Br). Dementsprechend gibt es zwei Qr, die durch die entsprechenden Blöcke der Runde r definiert werden. Allerdings die Gabelung wird nicht fortgesetzt und nur einer der beiden Zweige darf in Runde r + 1 wachsen. Zusätzliche Anweisungen für Algorand ′ 2. Wenn man einen nicht leeren Block sieht, ist Br und der leere Block Br ǫ , folgen Sie dem nicht leeren (und dem dadurch definierten Qr). In der Tat, indem die Benutzer angewiesen werden, den nicht leeren Block im Protokoll zu verwenden, wenn dieser groß ist Anzahl der ehrlichen Benutzer in PKr+1−k erkennen, dass es zu Beginn der Runde r +1 eine Abzweigung gibt, dann Ein leerer Block hat nicht genügend Follower und wächst nicht. Angenommen, der Gegner schafft es Partitionieren Sie die ehrlichen Benutzer so, dass einige ehrliche Benutzer Br (und möglicherweise Br) sehen ǫ), und manche sehen nur Br ǫ. Weil der Gegner nicht sagen kann, welcher von ihnen als Verifizierer nach Br fungieren wird und welcher wird nach Br. ein Prüfer sein ǫ , die ehrlichen Benutzer werden zufällig aufgeteilt und jeder von ihnen bleibt stehen wird zum Verifizierer (entweder in Bezug auf Br oder in Bezug auf Br ǫ) in einem Schritt s > 1 mit Wahrscheinlichkeit p. Für die böswilligen Benutzer hat jeder von ihnen möglicherweise zwei Chancen, Prüfer zu werden, eine mit Br und der andere mit Br ǫ, jeweils mit Wahrscheinlichkeit p unabhängig. Sei HSV r+1,s 1;Br sei die Menge der ehrlichen Verifizierer in den Schritten s der Runde r+1 nach Br. Andere Notationen wie HSV r+1,s 1;Brǫ , MSV r+1,s 1;Br und MSV r+1,s 1;Brǫ sind ähnlich definiert. Bei Chernoffbound ist es einfach 25Eine Abzweigung mit zwei nicht leeren Blöcken ist weder mit noch ohne Partitionen möglich, außer mit vernachlässigbaren Wahrscheinlichkeit.das mit überwältigender Wahrscheinlichkeit zu sehen, |HSV r+1,s 1;Br | + |HSV r+1,s 1;Brǫ | + |MSV r+1,s 1;Br | + |MSV r+1,s 1;Brǫ | < 2tH. Dementsprechend können die beiden Zweige nicht beide über die richtigen Signaturen verfügen, die einen Block für eine Runde bescheinigen r + 1 im gleichen Schritt s. Da außerdem die Auswahlwahrscheinlichkeiten für zwei Schritte s und s′ sind gleich und die Auswahlen sind unabhängig, auch mit überwältigender Wahrscheinlichkeit |HSV r+1,s 1;Br | + |MSV r+1,s 1;Br | + |HSV r+1,s′ 1;Brǫ | + |MSV r+1,s′ 1;Brǫ | < 2tH, für zwei beliebige Schritte s und s′. Wenn F = 10−18, durch die Vereinigung gebunden, solange der Gegner dies nicht kann Partitionieren Sie die ehrlichen Benutzer über einen langen Zeitraum (z. B. 104 Schritte, was mehr als 55 Stunden mit \(\lambda\) = 10 entspricht). Sekunden26), mit hoher Wahrscheinlichkeit (sagen wir 1−10−10) wird höchstens ein Zweig die richtigen Signaturen haben um einen Block in Runde r + 1 zu zertifizieren. Wenn die physische Partition schließlich zwei Teile mit ungefähr der gleichen Größe erstellt hat, dann ist die Wahrscheinlichkeit, dass |HSV r,s ich | + |MSV r,s ich | \(\geq\)tH ist für jeden Teil i klein. Nach einer ähnlichen Analyse, selbst wenn es dem Gegner gelingt, in jedem Teil eine Abzweigung mit einer nicht zu vernachlässigenden Wahrscheinlichkeit zu schaffen für Runde r darf höchstens einer der vier Zweige in Runde r + 1 wachsen. 10.2 Gegnerische Teilung Zweitens kann die Partitionierung durch den Angreifer verursacht werden, sodass sich die Nachrichten verbreiten durch die ehrlichen Benutzer in einem Teil erreichen die ehrlichen Benutzer im anderen Teil nicht direkt, sondern Der Gegner ist in der Lage, Nachrichten zwischen den beiden Teilen weiterzuleiten. Dennoch einmal eine Nachricht von einem Wenn ein Teil einen ehrlichen Benutzer im anderen Teil erreicht, wird er dort wie üblich weitergegeben. Wenn die Ist der Gegner bereit, viel Geld auszugeben, ist es denkbar, dass er in der Lage ist, das zu hacken Internet und Partitionierung für eine Weile so. Die Analyse ähnelt der für den größeren Teil in der physischen Partition oben (der kleinere). Teil kann als Population 0 betrachtet werden): Der Gegner kann möglicherweise eine Abzweigung erstellen und Jeder ehrliche Benutzer sieht nur einen der Zweige, es darf aber höchstens ein Zweig wachsen. 10.3 Netzwerkpartitionen im Überblick Obwohl es zu Netzwerkpartitionen kommen kann und eine Verzweigung in einer Runde unter Partitionen stattfinden kann, gibt es sie Es besteht keine bleibende Unklarheit: Eine Gabelung ist sehr kurzlebig und dauert tatsächlich höchstens eine einzige Runde. In Alle Teile der Partition außer höchstens einem, können die Benutzer keinen neuen Block generieren und somit (a) erkennen, dass es eine Partition im Netzwerk gibt und (b) sich niemals auf Blöcke verlassen, die „verschwinden“. Danksagungen Wir möchten zunächst Sergey Gorbunov danken, Mitautor des zitierten Democoin-Systems. Der aufrichtigste Dank geht an Maurice Herlihy für die vielen aufschlussreichen Diskussionen und die Hinweise heraus, dass Pipelining die Durchsatzleistung von Algorand verbessern wird, und für eine erhebliche Verbesserung der 26Beachten Sie, dass ein Benutzer einen Schritt s nur beendet, ohne 2\(\lambda\) Zeit zu warten, wenn er mindestens die Signaturen dafür gesehen hat gleiche Nachricht. Wenn nicht genügend Signaturen vorhanden sind, dauert jeder Schritt 2\(\lambda\).

Darstellung einer früheren Version dieser Arbeit. Vielen Dank an Sergio Rajsbaum für seine Kommentare zu eine frühere Version dieses Artikels. Vielen Dank an Vinod Vaikuntanathan für die zahlreichen intensiven Diskussionen und Erkenntnisse. Vielen Dank an Yossi Gilad, Rotem Hamo, Georgios Vlachos und Nickolai Zeldovich für den Beginn, diese Ideen zu testen, und für viele hilfreiche Kommentare und Diskussionen. Silvio Micali möchte sich persönlich bei Ron Rivest für die unzähligen Gespräche und Anleitungen bedanken in der kryptografischen Forschung über mehr als drei Jahrzehnte, für die Mitautoren des genannten Mikrozahlungssystems Dies hat einen der Verifizierer-Auswahlmechanismen von Algorand inspiriert. Wir hoffen, diese Technologie auf die nächste Stufe zu bringen. Inzwischen das Reisen und die Kameradschaft machen großen Spaß, wofür wir sehr dankbar sind.