Kann man Zufallszahlen generieren, wenn wir uns nicht gegenseitig vertrauen? Teil 1

Hallo, Habra!

In diesem Artikel werde ich die Erzeugung von Pseudo-Zufallszahlen durch Teilnehmer erläutern, die einander nicht vertrauen. Wie wir gleich sehen werden, ist es relativ einfach, einen „fast“ guten Generator zu implementieren, aber einen sehr guten zu erstellen, ist kompliziert.

Warum müssen Teilnehmer, die einander nicht vertrauen, überhaupt Zufallszahlen erzeugen? Ein Anwendungsbereich ist die dezentralisierte Anwendung. Zum Beispiel eine Anwendung, die eine Wette von einem Teilnehmer annimmt und entweder den Betrag mit einer Wahrscheinlichkeit von 49 % verdoppelt oder ihn mit einer Wahrscheinlichkeit von 51 % einbehält, wird nur funktionieren, wenn sie zufällig und unvoreingenommen eine Zufallszahl erhalten kann. Wenn ein Angreifer in der Lage ist, das Ergebnis des Zufallszahlengenerators zu beeinflussen und sogar seine Chance auf eine Auszahlung in der Anwendung geringfügig zu erhöhen, wird er sie leicht ausrauben.

Wenn wir ein verteiltes Protokoll zur Generierung von Zufallszahlen entwickeln, wollen wir, dass es drei Eigenschaften hat:

1. Es muss unparteiisch sein. Mit anderen Worten, kein Teilnehmer darf auf irgendeine Weise das Ergebnis des Zufallszahlengenerators beeinflussen.

2. Es muss unvorhersehbar sein. Mit anderen Worten, kein Teilnehmer darf in der Lage sein vorherzusagen, welche Zahl generiert wird (oder irgendwelche ihrer Eigenschaften herauszufinden), bevor sie generiert wird.

3. Das Protokoll muss funktionsfähig sein, das heißt, es muss widerstandsfähig gegen das Ausfallen eines bestimmten Prozentsatzes von Teilnehmern oder gegen absichtliche Versuche sein, das Protokoll zu stoppen.

In diesem Artikel werden wir zwei Ansätze betrachten: RANDAO + VDF und den Ansatz, der auf Löschcodes basiert. Im nächsten Teil werden wir den auf Schwellenwertsignaturen basierenden Ansatz ausführlich erläutern.

Aber zuerst schauen wir uns einen einfachen und häufig verwendeten Algorithmus an, der funktionsfähig, unvorhersehbar, aber voreingenommen ist.

RANDAO

RANDAO ist ein sehr einfacher und deshalb ziemlich häufig verwendeter Ansatz zur Erzeugung von Zufälligkeit. Alle Teilnehmer im Netzwerk wählen zunächst lokal eine pseudorandomisierte Zahl, danach 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, wobei das Ergebnis dieser Operation das Ergebnis des Protokolls wird.

Der Schritt zur Veröffentlichung der Hashes, bevor die Zahlen aufgedeckt werden, ist notwendig, damit ein Angreifer seine Zahl nicht auswählen kann, nachdem er die Zahlen der anderen Teilnehmer gesehen hat. Dies würde es ihm ermöglichen, das Ergebnis des Zufallszahlengenerators faktisch 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 damit aufhören, Hashes zu akzeptieren, und wann sie aufhören, die gewählten Zahlen zu akzeptieren und die resultierende Zufallszahl zu berechnen. Die Entscheidungsfindung zwischen Teilnehmern, die sich gegenseitig nicht vertrauen, ist an sich eine schwierige Aufgabe, und wir werden in zukünftigen Artikeln darauf zurückkommen; in diesem Artikel gehen wir davon aus, dass uns ein solcher Konsensalgorithmus zur Verfügung steht.

Welche der oben beschriebenen Eigenschaften hat RANDAO? Es ist unvorhersehbar, hat die gleiche Lebensfähigkeit wie das zugrunde liegende Konsensprotokoll, ist aber voreingenommen. Insbesondere kann ein Angreifer das Netzwerk beobachten, und nachdem andere Teilnehmer ihre Zahlen aufgedeckt haben, kann er deren XOR berechnen und entscheiden, ob er seine eigene Zahl aufdecken oder nicht aufdecken möchte, um das Ergebnis zu beeinflussen. Während es dem Angreifer nicht erlaubt, das Ergebnis des Zufallszahlengenerators allein zu bestimmen, gibt es ihm dennoch 1 Bit Einfluss. Und wenn Angreifer mehrere Teilnehmer kontrollieren, entspricht die Anzahl der von ihnen kontrollierten Bits der Anzahl der Teilnehmer unter ihrer Kontrolle.

Der Einfluss der Angreifer kann erheblich reduziert werden, wenn gefordert wird, dass die Teilnehmer die Zahlen der Reihe nach aufdecken. Dann kann der Angreifer das Ergebnis nur beeinflussen, wenn er zuletzt aufgedeckt wird. Während der Einfluss deutlich geringer ist, bleibt der Algorithmus dennoch voreingenommen.

RANDAO + VDF

Eine der Möglichkeiten, RANDAO uneingeschränkt zu machen, besteht darin, dass, nachdem alle Zahlen aufgedeckt und das XOR berechnet wurde, das Ergebnis an eine Funktion übergeben wird, die eine sehr lange Zeit benötigt, um berechnet zu werden, es aber ermöglicht, die Richtigkeit der Berechnung sehr schnell zu überprüfen.

(vdf_output, vdf_proof) = VDF_compute(input) // das ist sehr langsam
correct = VDF_verify(input, vdf_output, vdf_proof) // das ist sehr schnell

Diese Funktion wird als Verifiable Delay Function oder VDF bezeichnet. Wenn die Berechnung des endgültigen Ergebnisses länger dauert als die Phase der Offenlegung der Zahlen, kann ein Angreifer den Effekt der Demonstration oder des Versteckens seiner Zahl nicht vorhersagen, und verliert somit die Möglichkeit, das Ergebnis zu beeinflussen.

Die Entwicklung guter VDF ist extrem kompliziert. In letzter Zeit gab es mehrere Durchbrüche, zum Beispiel diesen und dieser, die VDF praktischer anwendbar gemacht haben, und Ethereum 2.0 plant langfristig, RANDAO mit VDF als Quelle für Zufallszahlen zu verwenden. Neben der Tatsache, dass dieser Ansatz unvorhersehbar und unbefangen ist, hat er den zusätzlichen Vorteil der Lebensfähigkeit, solange mindestens zwei Teilnehmer im Netzwerk verfügbar sind (vorausgesetzt, dass das verwendete Konsensprotokoll auch bei so wenigen Teilnehmern funktioniert).

Die größte Herausforderung dieses Ansatzes besteht darin, eine VDF so einzurichten, dass selbst ein Teilnehmer mit sehr teurer spezialisierter Hardware die VDF nicht vor dem Ende der Offenlegungsphase berechnen kann. Idealerweise sollte der Algorithmus sogar einen bedeutenden Sicherheitsabstand haben, sagen wir 10-fach. Die folgende Abbildung zeigt einen Angriff eines Teilnehmers, der über einen spezialisierten ASIC verfügt, der es ihm ermöglicht, die VDF schneller auszuführen als die für die Offenlegung der RANDAO-Bestätigung vorgesehene Zeit. Ein solcher Teilnehmer kann weiterhin das endgültige Ergebnis sowohl mit als auch ohne seine Zahl berechnen und anschließend basierend auf diesen Berechnungen entscheiden, ob er sie zeigt oder nicht.

Für das vorgenannte Familienspektrum an VDF kann die Leistung spezialisierter ASICs mehr als 100-mal höher sein als die von herkömmlicher Hardware. Wenn die Offenlegungsphase also 10 Sekunden dauert, müsste die auf einem solchen ASIC berechnete VDF mehr als 100 Sekunden in Anspruch nehmen, um einen 10-fachen Sicherheitsabstand zu haben. Daher müsste 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 ASIC zu lösen. Sobald dies geschieht, können auch alle anderen Protokolle von dieser Technologie profitieren, aber bis dahin wird der Ansatz RANDAO + VDF für Protokolle, die nicht in die Entwicklung eigener ASIC investieren können, nicht genauso tragfähig sein.

Es gibt viele Artikel, Videos und andere Informationen über VDF, die gesammelt wurden auf dieser Website.

Wir verwenden Löschen-Codes

In diesem Abschnitt betrachten wir das Protokoll zur Generierung von Zufallszahlen, das Löschen-Codes. Es kann bis zu ⅓ der Angreifer überstehen und ermöglicht die Existenz von bis zu ⅔ Angreifern, bevor sie das Ergebnis vorhersagen oder beeinflussen können.

Die Grundidee des Protokolls ist folgende: Zum Einfachheit nehmen wir an, dass es genau 100 Teilnehmer gibt. Angenommen, jeder Teilnehmer hat lokal einen privaten Schlüssel, und die öffentlichen Schlüssel aller Teilnehmer sind allen Teilnehmern bekannt:

1. Jeder Teilnehmer denkt sich lokal eine lange Zeichenkette aus, teilt sie in 67 Teile und erstellt Löschen-Codes, um 100 Anteile zu erhalten, wobei beliebige 67 zur Wiederherstellung der Zeichenkette ausreichen, weist jeder der 100 Anteile einem der Teilnehmer zu und verschlüsselt sie mit dem öffentlichen Schlüssel desselben Teilnehmers. Dann werden alle codierten Anteile veröffentlicht.

2. Die Teilnehmer verwenden einen Konsens, um sich über die codierten Sätze von bestimmten 67 Teilnehmern zu einigen.

3. Sobald Konsens erreicht ist, nimmt jeder Teilnehmer die codierten Anteile in jedem der 67 Sätze, die mit ihrem öffentlichen Schlüssel verschlüsselt sind, entschlüsselt alle derartigen Anteile und veröffentlicht alle dieser entschlüsselten Anteile.

4. Sobald 67 Teilnehmer Schritt (3) ausgeführt haben, können alle vereinbarten Sätze aufgrund der Eigenschaften der Löschen-Codes vollständig decodiert und wiederhergestellt werden, und die endgültige Zahl kann als XOR der ursprünglichen Zeichenketten, mit denen die Teilnehmer in (1) begonnen haben, erhalten werden.

Es kann gezeigt werden, dass dieses Protokoll unparteiisch und unvorhersehbar ist. Die resultierende Zufallszahl wird nach Erreichung eines Konsenses bestimmt, aber niemand weiß davon, bis ⅔ der Teilnehmer die Teile, die mit ihrem öffentlichen Schlüssel verschlüsselt sind, dekodieren. So wird die Zufallszahl vorher bestimmt, bevor die Informationen, die für ihre Wiederherstellung notwendig sind, veröffentlicht werden.

Was passiert, wenn in Schritt (1) einer der Teilnehmer den anderen Teilnehmern kodierte Anteile sendet, die keinen korrekten Löschcode einer bestimmten Zeichenfolge darstellen? Ohne zusätzliche Änderungen werden verschiedene Teilnehmer entweder die Zeichenfolge gar nicht wiederherstellen können oder unterschiedliche Zeichenfolgen wiederherstellen, was dazu führt, dass verschiedene Teilnehmer unterschiedliche Zufallszahlen erhalten. Um dies zu verhindern, kann Folgendes gemacht werden: Jeder Teilnehmer berechnet neben den kodierten Anteilen auch Merkelbaum , und sendet jedem Teilnehmer sowohl den kodierten Anteil als auch die Wurzel des Merkelbaums sowie einen Beweis für die Einbeziehung des Anteils in den Merkelbaum. Im Konsens in Schritt (2) stimmen die Teilnehmer dann nicht nur über eine Reihe von Sätzen zu, sondern auch über eine Reihe konkreter Wurzeln solcher Bäume (wenn ein Teilnehmer vom Protokoll abweicht und unterschiedliche Wurzeln des Merkelbaums an verschiedene Teilnehmer sendet und zwei solcher Wurzeln im Konsens gezeigt werden, wird seine Zeichenfolge nicht in das Ergebnisset aufgenommen). Am Ende des Konsenses haben wir 67 kodierte Zeichenfolgen und die entsprechenden Wurzeln des Merkelbaums, sodass es mindestens 67 Teilnehmer gibt (nicht unbedingt dieselben, die die entsprechenden Zeichenfolgen vorgeschlagen haben), für die für jede der 67 Zeichenfolgen eine Nachricht mit einem Anteil des Löschcodes und ein Beweis der Einbeziehung ihres Anteils in den entsprechenden Merkelbaum vorhanden ist.

Wenn ein Teilnehmer in Schritt (4) 67 Anteile für eine bestimmte Zeichenfolge dekodiert und versucht, die ursprüngliche Zeichenfolge wiederherzustellen, kann Folgendes geschehen:

1. Die Zeichenfolge wird wiederhergestellt, und wenn sie dann erneut mit Löschcodes kodiert und der Merkelbaum für die lokal berechneten Anteile gezählt wird, stimmt die Wurzel mit der überein, bei der der Konsens erreicht wurde.

2. Die Zeichenfolge wird wiederhergestellt, aber die lokal berechnete Wurzel stimmt nicht mit der überein, bei der der Konsens erreicht wurde.

3. Die Zeichenfolge kann nicht wiederhergestellt werden.

Es ist leicht zu zeigen, dass, wenn für mindestens einen Teilnehmer die Variante (1) aufgetreten ist, für alle Teilnehmer die Variante (1) auftritt, und umgekehrt, wenn für mindestens einen Teilnehmer die Variante (2) oder (3) aufgetreten ist, dann tritt für alle Teilnehmer die Variante (2) oder (3) auf. Somit wird für jede Zeile in der Menge entweder allen Teilnehmern gelingen, sie erfolgreich wiederherzustellen, oder es wird allen Teilnehmern nicht gelingen, sie wiederherzustellen. Die resultierende Zufallszahl ist dann das XOR nur jener Zeilen, die die Teilnehmer wiederherstellen konnten.

Schwellensignaturen

Ein anderer Ansatz zur Zufälligkeit besteht in der Verwendung von sogenannten BLS-Schwellensignaturen. Ein auf Schwellensignaturen basierender Zufallszahlengenerator hat die gleichen Garantien wie der oben beschriebene Algorithmus, der auf Löschcodes basiert, hat aber eine erheblich geringere asymptotische Anzahl an Nachrichten, die für jede generierte Zahl über das Netzwerk gesendet werden.

BLS-Signaturen sind eine Konstruktion, die 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 die Verbreitung mehrerer Signaturen nicht erfordern. 

Eine häufige Anwendung von BLS-Signaturen in Blockchain-Protokollen, neben der Generierung von Zufallszahlen, besteht darin, Blöcke in BFT-Protokollen zu signieren. Angenommen, 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 vorlegen und einen Konsens-Algorithmus verwenden, um 67 davon zu vereinbaren und sie dann zu einer einzigen BLS-Signatur zusammenzuführen. Jedes 67 (oder mehr) Teile können zur Erstellung der finalen Signatur verwendet werden, die davon abhängt, welche spezifischen 67 Signaturen kombiniert wurden, und daher variieren kann, aber obwohl die Auswahl von 67 Teilnehmern unterschiedliche Signaturen erzeugt, ist jede dieser Signaturen eine gültige Signatur für den Block. Den anderen Teilnehmern reicht es dann aus, über das Netzwerk nur eine Signatur für jeden Block zu erhalten und zu überprüfen, anstatt 67, was die Netzlast erheblich reduziert.

Es stellt sich heraus, dass, wenn die privaten Schlüssel, die von den Teilnehmern verwendet werden, auf eine bestimmte Weise generiert werden, unabhängig davon, welche 67 Signaturen (oder mehr, aber keinesfalls weniger) aggregiert werden, die resultierende Signatur identisch sein wird. Dies kann als Quelle der Zufälligkeit verwendet werden: Die Teilnehmer einigen sich zunächst auf eine bestimmte Nachricht, die sie signieren werden (das kann entweder der Ausgang von RANDAO oder einfach der Hash des letzten Blocks sein, tatsächlich spielt es keine Rolle, solange es sich jedes Mal ändert und vereinbart ist), und erstellen dafür eine BLS-Signatur. Das Ergebnis der Generierung wird unvorhersehbar sein, bis 67 Teilnehmer ihre Teile bereitstellen, und danach sind die Ausgaben bereits vorbestimmt und können nicht von den Handlungen eines einzelnen Teilnehmers abhängen.

Dieser Ansatz zur Zufälligkeit ist tragfähig, wenn mindestens ⅔ der Teilnehmer online sind und dem Protokoll folgen, und 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, aber seine Ausgabe nicht vorhersagen oder beeinflussen kann.

Schwellensignaturen sind an sich ein sehr interessantes Thema. Im zweiten Teil des Artikels werden wir im Detail untersuchen, wie sie funktionieren und wie genau die Schlüssel der Teilnehmer generiert werden müssen, damit Schwellensignaturen als Zufallszahlengenerator verwendet werden können.

Abschließend

Dieser Artikel ist der erste in einer Reihe technischer Artikel im Blog NEAR. NEAR ist ein Blockchain-Protokoll und eine Plattform zur Entwicklung dezentralisierter Anwendungen mit Schwerpunkt auf einfacher Entwicklung und Benutzerfreundlichkeit für Endbenutzer.

Der Protokollcode ist offen, unsere Implementierung ist in Rust geschrieben, und sie kann gefunden werden hier.

Sie können sehen, wie die Entwicklung unter NEAR aussieht, und in der Online-IDE experimentieren hier.

Um alle Nachrichten auf Russisch zu verfolgen, können Sie in der Gruppe im Telegram und in Gruppe auf VKontakte, und auf Englisch im offiziellen Twitter-Account.

Bis bald!

Quelle: habr.com