Hallo, Habr!
In diesem Artikel werde ich über die Generierung von pseudo-zufälligen Zahlen durch Teilnehmer sprechen, die einander misstrauen. Wie wir weiter unten sehen werden, ist es relativ einfach, einen „fast“ guten Generator zu implementieren, während es sehr schwierig ist, einen wirklich guten zu schaffen.
Warum ist es überhaupt notwendig, dass Teilnehmer, die einander misstrauen, zufällige Zahlen generieren? Ein Anwendungsbereich sind dezentrale Anwendungen. Zum Beispiel ein Programm, das eine Wette von einem Teilnehmer annimmt und entweder den Betrag mit einer Wahrscheinlichkeit von 49 % verdoppelt oder ihn mit 51 % einbehält, funktioniert nur, wenn es auf faire Weise eine zufällige Zahl erhalten kann. Wenn ein Angreifer das Ergebnis des Zufallszahlengenerators beeinflussen kann und sogar seine Chancen auf eine Auszahlung im Programm geringfügig erhöhen kann, wird er leicht dessen Inhalte leeren.
Wenn wir ein verteiltes Protokoll zur Generierung von Zufallszahlen entwickeln, möchten wir, dass es drei Eigenschaften besitzt:
Es muss unparteiisch sein. Mit anderen Worten, kein Teilnehmer darf in irgendeiner Weise das Ergebnis des Zufallszahlengenerators beeinflussen.
Er muss unvorhersehbar sein. Mit anderen Worten, kein Teilnehmer sollte in der Lage sein, vorherzusagen, welche Zahl generiert wird (oder irgendwelche ihrer Eigenschaften) bevor sie generiert wird.
Das Protokoll muss funktionsfähig sein, das heißt, es muss robust gegenüber dem Ausfall eines gewissen Prozentsatzes von Teilnehmern oder dem absichtlichen Versuch, das Protokoll zu stoppen, sein.
In diesem Artikel betrachten wir zwei Ansätze: RANDAO + VDF und einen Ansatz, der auf fehlerkorrigierenden Codes basiert. Im nächsten Teil werden wir den Ansatz, der auf Schwellenwertsignaturen basiert, detaillierter untersuchen.
Aber zunächst wollen wir einen einfachen und oft verwendeten Algorithmus aufschlüsseln, der funktionsfähig, unvorhersehbar, aber voreingenommen ist.
RANDAO
RANDAO ist ein sehr einfacher und daher recht häufig verwendeter Ansatz zur Generierung von Zufälligkeit. Alle Teilnehmer im Netzwerk wählen zunächst lokal eine pseudorandomisierte Zahl aus, dann sendet jeder Teilnehmer den Hash der gewählten Zahl. Anschließend decken die Teilnehmer nacheinander ihre gewählten Zahlen auf und führen eine XOR-Operation über die aufgedeckten Zahlen durch, deren Ergebnis dann das Resultat des Protokolls ist.
Der Schritt zur Veröffentlichung von Hashes, bevor die Zahlen aufgedeckt werden, ist notwendig, damit ein Angreifer nicht seine eigene Zahl wählen kann, nachdem er die Zahlen der anderen Teilnehmer gesehen hat. Dies würde ihm ermöglichen, die Ausgabe des Zufallszahlengenerators tatsächlich allein zu bestimmen.
Im Verlauf des Protokolls müssen die Teilnehmer zweimal zu einer gemeinsamen Entscheidung (dem sogenannten Konsens) kommen: wann sie beginnen, die gewählten Zahlen aufzudecken und somit die Annahme von Hashes einzustellen, und wann die Annahme der gewählten Zahlen abgeschlossen ist und die resultierende Zufallszahl berechnet wird. Solche Entscheidungen zwischen Teilnehmern, die sich gegenseitig nicht vertrauen, sind an sich eine herausfordernde Aufgabe, auf die wir in zukünftigen Artikeln zurückkommen werden; in diesem Artikel nehmen wir an, dass ein solcher Konsensusalgorithmus für uns verfügbar ist.
Welche der oben beschriebenen Eigenschaften besitzt RANDAO? Es ist unvorhersehbar und hat die gleiche Lebensfähigkeit wie das zugrunde liegende Konsensprotokoll, zeigt jedoch eine Voreingenommenheit. Insbesondere kann ein Angreifer das Netzwerk beobachten, und nachdem andere Teilnehmer ihre Zahlen offenbart haben, kann er deren XOR berechnen und entscheiden, ob er seine eigene Zahl offenbaren sollte, um das Ergebnis zu beeinflussen. Auch wenn dies dem Angreifer nicht erlaubt, den Ausgang des Zufallszahlengenerators allein zu bestimmen, gibt es ihm dennoch 1 Bit Einfluss. Wenn Angreifer mehrere Teilnehmer kontrollieren, wird die Anzahl der von ihnen kontrollierten Bits der Anzahl der unter ihrer Kontrolle stehenden Teilnehmer entsprechen.
Der Einfluss von Angreifern kann erheblich verringert werden, wenn Teilnehmer gefordert werden, ihre Zahlen in einer bestimmten Reihenfolge preiszugeben. In diesem Fall kann der Angreifer den Ausgang nur beeinflussen, wenn er als letzter offenbart. Während der Einfluss deutlich geringer ist, bleibt der Algorithmus dennoch voreingenommen.
RANDAO + VDF
Eine Möglichkeit, RANDAO unparteiisch zu gestalten, besteht darin, dass, nachdem alle Zahlen enthüllt sind und das XOR berechnet wurde, das Ergebnis in eine Funktion eingegeben wird, deren Berechnung sehr viel Zeit in Anspruch nimmt, jedoch eine schnelle Überprüfung der Korrektheit ermöglicht.
(vdf_output, vdf_proof) = VDF_compute(input) // das ist sehr langsam
correct = VDF_verify(input, vdf_output, vdf_proof) // das ist sehr schnellEine solche Funktion wird als Verifiable Delay Function oder VDF bezeichnet. Wenn die Berechnung des endgültigen Ergebnisses mehr Zeit in Anspruch nimmt als der Schritt der Zahlenenthüllung, kann ein Angreifer nicht vorhersagen, welchen Einfluss die Offenlegung oder das Zurückhalten seiner Zahl hat, und somit verliert er die Möglichkeit, das Ergebnis zu beeinflussen.
Die Entwicklung guter VDF ist extrem komplex. In letzter Zeit gab es einige Durchbrüche, zum Beispiel und welche VDF praktischer anwendbar machte, und Ethereum 2.0 plant langfristig, RANDAO mit VDF als Zufallszahlengenerator zu nutzen. Abgesehen davon, dass dieser Ansatz unvorhersehbar und unvoreingenommen ist, hat er den zusätzlichen Vorteil der Lebensfähigkeit, solange mindestens zwei Teilnehmer im Netzwerk verfügbar sind (vorausgesetzt, dass das verwendete Konsensprotokoll bei so wenigen Teilnehmern funktionsfähig ist).
Die größte Herausforderung dieses Ansatzes besteht darin, VDF so zu konfigurieren, dass selbst ein Teilnehmer mit sehr teurer spezialisierter Hardware VDF nicht vor dem Ende der Offenlegungsphase berechnen kann. Idealerweise sollte der Algorithmus sogar einen erheblichen Puffer haben, sagen wir 10x. Die untenstehende Abbildung zeigt einen Angriff eines Teilnehmers mit spezialisierter ASIC-Hardware, der es ihm ermöglicht, VDF schneller auszuführen, als die für die Offenlegung der RANDAO-Bestätigung vorgesehene Zeit. Ein solcher Teilnehmer kann das Endergebnis berechnen, indem er seine Zahl sowohl verwendet als auch nicht verwendet, und danach, basierend auf den Berechnungen, entscheiden, ob er sie zeigt oder nicht.
Für die oben erwähnte VDF-Familie kann die Leistung eines spezialisierten ASIC mehr als 100-mal höher sein als bei herkömmlicher Hardware. Wenn die Entdeckungsphase also 10 Sekunden dauert, sollte die auf einem solchen ASIC berechnete VDF mehr als 100 Sekunden in Anspruch nehmen, um einen Sicherheitsvorrat von 10-fach zu gewährleisten. Folglich sollte dieselbe VDF, die auf herkömmlicher Hardware berechnet wird, 100 x 100 Sekunden = ~ 3 Stunden dauern.
Die Ethereum Foundation plant, dieses Problem durch die Schaffung eigener öffentlicher, kostenloser ASICs zu lösen. Sobald dies geschehen ist, können auch alle anderen Protokolle von dieser Technologie profitieren, aber bis dahin wird der RANDAO + VDF-Ansatz für Protokolle, die nicht in die Entwicklung ihrer eigenen ASICs investieren können, nicht ebenso tragfähig sein.
Viele Artikel, Videos und andere Informationen über VDF sind gesammelt auf .
Wir verwenden Fehlerkorrekturcodes
In diesem Abschnitt werden wir das Protokoll zur Generierung von Zufallszahlen betrachten, das . Es kann bis zu ein Drittel der Angreifer aushalten und bleibt dabei funktionsfähig, und es erlaubt die Existenz von bis zu zwei Dritteln der Angreifer, bevor sie das Ergebnis vorhersagen oder beeinflussen können.
Die grundlegende Idee des Protokolls lässt sich wie folgt zusammenfassen. Zur Vereinfachung nehmen wir an, dass es genau 100 Teilnehmer gibt. Nehmen wir auch an, dass jeder Teilnehmer lokal einen bestimmten privaten Schlüssel hat und die öffentlichen Schlüssel aller Teilnehmer allen bekannt sind:
Jeder Teilnehmer erfindet lokal eine lange Zeichenfolge, zerlegt sie in 67 Teile, erstellt Löschcodes, um 100 Anteile zu erzeugen, wobei beliebige 67 zur Wiederherstellung der Zeichenfolge ausreichend sind, weist jeden der 100 Anteile einem der Teilnehmer zu und verschlüsselt sie mit dem öffentlichen Schlüssel desselben Teilnehmers. Danach werden alle codierten Anteile veröffentlicht.
Die Teilnehmer verwenden einen bestimmten Konsens, um Einigkeit über die kodierten Sätze von konkret 67 Teilnehmern zu erzielen.
Sobald der Konsens erreicht ist, nimmt jeder Teilnehmer die kodierten Anteile aus jedem der 67 Sätze, die mit ihrem öffentlichen Schlüssel verschlüsselt sind, entschlüsselt alle solchen Anteile und veröffentlicht alle entschlüsselten Anteile.
Sobald 67 Teilnehmer Schritt (3) abgeschlossen haben, können alle vereinbarten Sätze vollständig dekodiert und wiederhergestellt werden, dank der Eigenschaften von Löschcodes. Die endgültige Zahl kann als XOR der ursprünglichen Zeilen erhalten werden, von denen die Teilnehmer in (1) ausgegangen sind.
Es kann gezeigt werden, dass dieses Protokoll unparteiisch und unvorhersehbar ist. Die resultierende Zufallszahl wird nach Erreichen des Konsenses festgelegt, aber niemand weiß sie, bis ⅔ der Teilnehmer die Teile dekodiert haben, die mit ihrem öffentlichen Schlüssel verschlüsselt sind. Somit wird die Zufallszahl festgelegt, bevor die Informationen, die für ihre Wiederherstellung erforderlich sind, veröffentlicht werden.
Was passiert, wenn in Schritt (1) einer der Teilnehmer den anderen Teilnehmern kodierte Anteile sendet, die keinen gültigen Löschcode einer bestimmten Zeile darstellen? Ohne zusätzliche Änderungen werden unterschiedliche Teilnehmer entweder in der Lage sein, die Zeile überhaupt nicht wiederherzustellen oder unterschiedliche Zeilen wiederherzustellen, was dazu führen wird, dass verschiedene Teilnehmer unterschiedliche Zufallszahlen erhalten. Um dies zu verhindern, kann Folgendes getan werden: Jeder Teilnehmer berechnet zusätzlich zu den kodierten Anteilen auch aller solcher Anteile, und jeder Teilnehmer erhält sowohl den codierten Anteil als auch die Wurzel des Merkel-Baums sowie den Beweis für die Einbeziehung des Anteils in den Merkel-Baum. Bei dem Konsensschritt (2) einigen sich die Teilnehmer nicht nur auf eine Menge von Sätzen, sondern auf eine Menge spezifischer Wurzeln solcher Bäume (wenn ein Teilnehmer vom Protokoll abweicht und verschiedenen Teilnehmern unterschiedliche Wurzeln des Merkel-Baums sendet, wird seine Zeile nicht in die Ergebnismenge aufgenommen). Am Ende des Konsenses werden wir 67 codierte Zeilen und die entsprechenden Wurzeln des Merkel-Baums haben, sodass es mindestens 67 Teilnehmer gibt (nicht unbedingt die gleichen, die die entsprechenden Zeilen vorgeschlagen haben), bei denen für jede der 67 Zeilen eine Nachricht mit dem Anteil des Löschcodes vorliegt und der Nachweis der Einbeziehung ihres Anteils in den entsprechenden Merkel-Baum erbracht wird.
Wenn ein Teilnehmer in Schritt (4) 67 Anteile für eine bestimmte Zeile entschlüsselt und versucht, die ursprüngliche Zeile wiederherzustellen, gibt es eine der folgenden Möglichkeiten:
Die Zeile wird wiederhergestellt, und wenn sie dann erneut mit Löschcodes kodiert wird und der Merkle-Baum für die lokal berechneten Anteile gezählt wird, stimmt die Wurzel mit derjenige überein, bei der Konsens erzielt wurde.
Die Zeile wird wiederhergestellt, jedoch stimmt die lokal berechnete Wurzel nicht mit der überein, bei der Konsens erzielt wurde.
Die Zeile kann nicht wiederhergestellt werden.
Es ist leicht zu zeigen, dass, wenn bei mindestens einem Teilnehmer der Fall (1) eintritt, für alle Teilnehmer der Fall (1) eintreten wird. Umgekehrt, wenn bei mindestens einem Teilnehmer der Fall (2) oder (3) eintritt, dann wird es bei allen Teilnehmern der Fall (2) oder (3) eintreten. Somit wird für jede Zeile im Satz entweder allen Teilnehmern die Wiederherstellung erfolgreich gelingen oder keiner der Teilnehmer kann sie wiederherstellen. Die resultierende Zufallszahl ist dann das XOR nur der Zeilen, die die Teilnehmer wiederherstellen konnten.
Schwellensignaturen
Ein alternativer Ansatz zur Zufälligkeit besteht darin, sogenannte Schwellenwerte für BLS-Signaturen zu verwenden. Ein auf Schwellenwertsignaturen basierender Zufallszahlengenerator bietet die gleichen Garantien wie der oben beschriebene Algorithmus, der auf Löschcodes basiert, weist jedoch eine signifikant niedrigere Asymptotik der Anzahl der Nachrichten auf, die für jede generierte Zahl über das Netzwerk gesendet werden.
BLS-Signaturen sind ein Konstrukt, das es mehreren Teilnehmern ermöglicht, eine gemeinsame Signatur für eine Nachricht zu erstellen. Solche Signaturen werden häufig verwendet, um Platz und Bandbreite zu sparen, da sie keine Verteilung mehrerer Signaturen erfordern.
Eine häufige Anwendung von BLS-Signaturen in Blockchain-Protokollen, neben der Generierung von Zufallszahlen, ist die Signierung von Blöcken in BFT-Protokollen. Nehmen wir an, 100 Teilnehmer erstellen Blöcke, und ein Block wird als endgültig betrachtet, wenn 67 von ihnen ihn signieren. Alle können ihre Teile der BLS-Signatur präsentieren und einen Konsensalgorithmus verwenden, um 67 von ihnen zu bestätigen, bevor sie diese zu einer einzigen BLS-Signatur zusammenführen. Jede beliebige Kombination von 67 (oder mehr) Teilen kann zur Erstellung der endgültigen Signatur verwendet werden, die davon abhängt, welche spezifischen 67 Signaturen zusammengeführt wurden. Daher kann sie variieren, aber unabhängig davon, welche 67 Teilnehmer ausgewählt wurden, wird jede solche Signatur eine gültige Signatur für den Block sein. Den übrigen Teilnehmern genügt es dann, über das Netzwerk nur eine Signatur pro Block zu erhalten und zu überprüfen, anstatt 67, was die Netzwerklast erheblich verringert.
Es stellt sich heraus, dass, wenn die privaten Schlüssel, die von den Teilnehmern verwendet werden, auf bestimmte Weise generiert werden, die resultierende Signatur unabhängig davon, welche 67 Signaturen (oder mehr, aber auf keinen Fall weniger) aggregiert werden, gleich sein wird. Dies kann als Quelle der Zufälligkeit genutzt werden: Die Teilnehmer einigen sich zunächst auf eine bestimmte Nachricht, die sie signieren wollen (dies kann der Ausgabe von RANDAO oder einfach der Hash des letzten Blocks sein; es ist eigentlich unerheblich, solange sie jedes Mal anders ist und einvernehmlich ist) und erstellen dafür eine BLS-Signatur. Das Ergebnis der Generierung bleibt unvorhersehbar, bis 67 Teilnehmer ihre Teile bereitgestellt haben; danach sind die Ausgaben bereits vordefiniert und können nicht von den Aktionen eines beliebigen Teilnehmers abhängen.
Dieser Ansatz zur Zufälligkeit ist tragfähig, wenn mindestens ⅔ der Teilnehmer online sind und das Protokoll befolgen. Zudem bleibt es unparteiisch und unvorhersehbar, solange mindestens ⅓ der Teilnehmer dem Protokoll folgen. Es ist wichtig zu beachten, dass ein Angreifer, der mehr als ⅓, aber weniger als ⅔ der Teilnehmer kontrolliert, das Protokoll stoppen kann, jedoch nicht dessen Ausgang vorhersagen oder beeinflussen kann.
Schwellensignaturen sind an sich ein sehr interessantes Thema. Im zweiten Teil des Artikels werden wir detailliert untersuchen, wie sie funktionieren und wie die Schlüssel der Teilnehmer generiert werden müssen, damit Schwellensignaturen als Zufallszahlengenerator verwendet werden können.
Zusammenfassung
Dieser Artikel ist der erste in einer Reihe von technischen Blog-Artikeln. . NEAR ist ein Blockchain-Protokoll und eine Plattform zur Entwicklung dezentraler Anwendungen mit dem Fokus auf einfache Entwicklung und Benutzerfreundlichkeit.
Der Code des Protokolls ist offen, unsere Implementierung ist in Rust geschrieben und kann gefunden werden .
Schauen Sie sich an, wie die Entwicklung unter NEAR aussieht, und experimentieren Sie in der Online-IDE .
Folgen Sie allen Nachrichten auf Russisch in der auch in , und auf Englisch in der offiziellen .
Bis bald!
Quelle: habr.com
