Ist es möglich, Zufallszahlen zu generieren, wenn wir einander nicht vertrauen? Teil 1

Hey Habr!

In diesem Artikel werde ich über die Generierung von Pseudozufallszahlen durch Teilnehmer sprechen, die sich gegenseitig nicht vertrauen. Wie wir weiter unten sehen werden, ist die Implementierung eines „fast“ guten Generators recht einfach, die Implementierung eines sehr guten Generators jedoch schwierig.

Warum sollte es notwendig sein, Zufallszahlen unter Teilnehmern zu generieren, die einander nicht vertrauen? Ein Anwendungsgebiet sind dezentrale Anwendungen. Beispielsweise funktioniert eine Anwendung, die eine Wette eines Teilnehmers annimmt und entweder mit einer Wahrscheinlichkeit von 49 % den Betrag verdoppelt oder mit einer Wahrscheinlichkeit von 51 % abnimmt, nur, wenn sie unvoreingenommen eine Zufallszahl erhalten kann. Wenn ein Angreifer das Ergebnis des Zufallszahlengenerators beeinflussen und seine Chancen auf eine Auszahlung in der Anwendung sogar geringfügig erhöhen kann, wird er diese leicht zerstören.

Wenn wir ein Protokoll zur Erzeugung verteilter Zufallszahlen entwerfen, möchten wir, dass es drei Eigenschaften hat:

1. Er muss unvoreingenommen sein. Mit anderen Worten: Kein Teilnehmer sollte das Ergebnis des Zufallszahlengenerators in irgendeiner Weise beeinflussen.

2. Er muss unberechenbar sein. Mit anderen Worten: Kein Teilnehmer sollte in der Lage sein, vorherzusagen, welche Zahl generiert wird (oder auf ihre Eigenschaften zu schließen), bevor sie generiert wird.

3. Das Protokoll muss tragfähig sein, also resistent gegen die Tatsache sein, dass sich ein bestimmter Prozentsatz der Teilnehmer vom Netzwerk trennt oder absichtlich versucht, das Protokoll zu stoppen.

In diesem Artikel werden wir uns zwei Ansätze ansehen: RANDAO + VDF und den Löschcode-Ansatz. Im nächsten Teil werden wir den auf Schwellenwertsignaturen basierenden Ansatz im Detail untersuchen.

Aber schauen wir uns zunächst einen einfachen und häufig verwendeten Algorithmus an, der realisierbar, unvorhersehbar, aber voreingenommen ist.

RANDAO

RANDAO ist ein sehr einfacher und daher recht häufig verwendeter Ansatz zur Generierung von Zufälligkeiten. Alle Netzwerkteilnehmer wählen zunächst lokal eine Pseudozufallszahl aus, dann sendet jeder Teilnehmer einen Hash der ausgewählten Zahl. Als nächstes geben die Teilnehmer abwechselnd ihre gewählten Zahlen preis und führen eine XOR-Operation an den offenbarten Zahlen durch, und das Ergebnis dieser Operation wird zum Ergebnis des Protokolls.

Der Schritt der Veröffentlichung der Hashes vor der Offenlegung der Nummern ist notwendig, damit der Angreifer seine Nummer nicht auswählen kann, nachdem er die Nummern der anderen Teilnehmer gesehen hat. Dies würde es ihm ermöglichen, die Ausgabe des Zufallszahlengenerators praktisch im Alleingang zu bestimmen.

Im Verlauf des Protokolls müssen die Teilnehmer zweimal zu einer gemeinsamen Entscheidung (sogenanntem Konsens) kommen: wann mit der Offenlegung der ausgewählten Zahlen begonnen werden soll und damit die Annahme von Hashes beendet wird, und wann mit der Annahme der ausgewählten Zahlen und der Berechnung des resultierenden Zufalls aufgehört wird Nummer. Solche Entscheidungen zwischen Teilnehmern zu treffen, die sich gegenseitig nicht vertrauen, ist an sich keine leichte 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 und hat die gleiche Vitalität wie das zugrunde liegende Konsensprotokoll, ist jedoch voreingenommen. Konkret kann ein Angreifer das Netzwerk beobachten und nachdem andere Teilnehmer ihre Nummern preisgegeben haben, kann er deren XOR berechnen und entscheiden, ob er seine Nummer preisgibt oder nicht, um das Ergebnis zu beeinflussen. Dies verhindert zwar, dass der Angreifer die Ausgabe des Zufallszahlengenerators im Alleingang bestimmen kann, verschafft ihm aber dennoch 1 Bit Einfluss. Und wenn Angreifer mehrere Teilnehmer kontrollieren, entspricht die Anzahl der von ihnen kontrollierten Bits der Anzahl der von ihnen kontrollierten Teilnehmer.

Der Einfluss von Angreifern kann erheblich verringert werden, indem von den Teilnehmern verlangt wird, die Zahlen der Reihe nach preiszugeben. Dann kann der Angreifer das Ergebnis nur dann beeinflussen, wenn es zuletzt geöffnet wird. Obwohl der Einfluss deutlich geringer ist, ist der Algorithmus immer noch voreingenommen.

RANDAO+VDF

Eine Möglichkeit, RANDAO unvoreingenommen zu machen, ist folgende: Nachdem alle Zahlen aufgedeckt und das XOR berechnet wurde, wird sein Ergebnis in die Eingabe einer Funktion eingespeist, deren Berechnung sehr lange dauert, es Ihnen aber ermöglicht, die Richtigkeit des zu überprüfen Berechnung sehr schnell.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Diese Funktion wird Verifiable Delay Function oder VDF genannt. Wenn die Berechnung des Endergebnisses länger dauert als die Phase der Offenlegung der Nummer, kann der Angreifer die Auswirkungen des Ein- oder Ausblendens seiner Nummer nicht vorhersagen und verliert daher die Möglichkeit, das Ergebnis zu beeinflussen.

Die Entwicklung guter VDFs ist äußerst schwierig. In letzter Zeit gab es mehrere Durchbrüche, z.B. diese и dieser hier Dadurch wurde VDF in der Praxis praktischer, und Ethereum 2.0 plant, RANDAO mit VDF langfristig als Zufallszahlenquelle zu verwenden. Abgesehen von der Tatsache, dass dieser Ansatz unvorhersehbar und unvoreingenommen ist, hat er den zusätzlichen Vorteil, dass er realisierbar ist, wenn mindestens zwei Teilnehmer im Netzwerk verfügbar sind (vorausgesetzt, das verwendete Konsensprotokoll ist bei einer so kleinen Anzahl von Teilnehmern realisierbar).

Die größte Herausforderung dieses Ansatzes besteht darin, die VDF so einzurichten, dass selbst ein Teilnehmer mit sehr teurer Spezialhardware nicht in der Lage sein wird, die VDF vor dem Ende der Entdeckungsphase zu berechnen. Im Idealfall sollte der Algorithmus sogar eine erhebliche Sicherheitsmarge haben, beispielsweise 10x. Die folgende Abbildung zeigt einen Angriff eines Akteurs, der über einen speziellen ASIC verfügt, der es ihm ermöglicht, eine VDF schneller auszuführen, als für die Offenlegung der RANDAO-Bestätigung vorgesehen ist. Ein solcher Teilnehmer kann immer noch das Endergebnis anhand seiner Zahl berechnen oder nicht und dann auf der Grundlage der Berechnung entscheiden, ob er es anzeigen möchte oder nicht.

Bei der oben erwähnten VDF-Familie kann die Leistung eines dedizierten ASIC über 100-mal höher sein als bei herkömmlicher Hardware. Wenn die Bereitstellungsphase also 10 Sekunden dauert, muss die auf einem solchen ASIC berechnete VDF mehr als 100 Sekunden dauern, um eine 10-fache Sicherheitsmarge zu haben, und daher muss die gleiche VDF, die auf Standardhardware berechnet wird, 100 x 100 Sekunden = ~3 Stunden dauern.

Die Ethereum Foundation plant, dieses Problem durch die Entwicklung eigener öffentlich verfügbarer, kostenloser ASICs zu lösen. Sobald dies geschieht, können alle anderen Protokolle ebenfalls 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 so praktikabel sein.

Viele Artikel, Videos und andere Informationen über VDF wurden auf gesammelt this site.

Wir verwenden Löschcodes

In diesem Abschnitt betrachten wir ein Protokoll zur Zufallszahlengenerierung, das verwendet wird Codes löschen. Es kann bis zu ⅓ Angreifer tolerieren, bleibt aber lebensfähig und lässt bis zu ⅔ Angreifer existieren, bevor sie das Ergebnis vorhersagen oder beeinflussen können.

Die Hauptidee des Protokolls ist wie folgt. Nehmen wir der Einfachheit halber an, dass es genau 100 Teilnehmer gibt. Nehmen wir außerdem an, dass alle Teilnehmer vor Ort über einen privaten Schlüssel verfügen und die öffentlichen Schlüssel aller Teilnehmer allen Teilnehmern bekannt sind:

1. Jeder Teilnehmer erstellt lokal eine lange Zeichenfolge, zerlegt sie in 67 Teile, erstellt Löschcodes, um 100 Anteile zu erhalten, sodass alle 67 ausreichen, um die Zeichenfolge wiederherzustellen, weist jede der 100 Anteile einem der Teilnehmer zu und verschlüsselt sie mit der öffentliche Schlüssel desselben Teilnehmers. Anschließend werden alle verschlüsselten Freigaben veröffentlicht.

2. Die Teilnehmer nutzen eine Art Konsens, um eine Einigung über codierte Sätze bestimmter 67 Teilnehmer zu erzielen.

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

4. Sobald 67 Teilnehmer Schritt (3) abgeschlossen haben, können alle vereinbarten Sätze aufgrund der Eigenschaften von Löschcodes vollständig dekodiert und rekonstruiert werden, und die endgültige Zahl kann als XOR der Anfangszeilen erhalten werden, mit denen die Teilnehmer in (1) begonnen haben. .

Es kann gezeigt werden, dass dieses Protokoll unvoreingenommen und unvorhersehbar ist. Die resultierende Zufallszahl wird nach Erreichen eines Konsenses ermittelt, ist jedoch niemandem bekannt, bis ⅔ der Teilnehmer die mit ihrem öffentlichen Schlüssel verschlüsselten Teile entschlüsseln. Somit wird die Zufallszahl bestimmt, bevor Informationen veröffentlicht werden, die zu ihrer Rekonstruktion ausreichen.

Was passiert, wenn in Schritt (1) einer der Teilnehmer verschlüsselte Anteile an die anderen Teilnehmer sendet, die nicht den richtigen Löschcode für eine Zeichenfolge enthalten? Ohne zusätzliche Änderungen werden verschiedene Teilnehmer entweder überhaupt nicht in der Lage sein, die Zeichenfolge wiederherzustellen, oder sie werden unterschiedliche Zeichenfolgen wiederherstellen, was dazu führt, dass verschiedene Teilnehmer eine unterschiedliche Zufallszahl erhalten. Um dies zu verhindern, können Sie Folgendes tun: Jeder Teilnehmer berechnet zusätzlich zu den verschlüsselten Anteilen auch Merkla-Baum alle derartigen Anteile und sendet jedem Teilnehmer sowohl den verschlüsselten Anteil selbst als auch die Wurzel des Merkle-Baums sowie einen Nachweis über die Aufnahme des Anteils in den Merkle-Baum. Im Konsens in Schritt (2) einigen sich die Teilnehmer dann nicht nur auf eine Reihe von Sätzen, sondern auf eine Reihe spezifischer Wurzeln solcher Bäume (wenn ein Teilnehmer vom Protokoll abgewichen ist und unterschiedliche Merkle-Baum-Wurzeln an verschiedene Teilnehmer gesendet hat, und zwei solcher Wurzeln während des Konsenses angezeigt werden, ist die Zeile nicht im Ergebnissatz enthalten. Als Ergebnis des Konsenses werden wir 67 codierte Zeilen und die entsprechenden Wurzeln des Merkle-Baums haben, sodass es mindestens 67 Teilnehmer gibt (nicht unbedingt dieselben, die die entsprechenden Zeilen vorgeschlagen haben), die für jede der 67 Zeilen zuständig sind eine Nachricht mit einem Anteil des Löschcodes und ein Nachweis des Vorkommens ihres Anteils im entsprechenden Baum.

Wenn der Teilnehmer in Schritt (4) 67 Schläge für eine bestimmte Saite entschlüsselt und versucht, daraus die ursprüngliche Saite zu rekonstruieren, ist eine der Optionen möglich:

1. Die Zeichenfolge wird wiederhergestellt, und wenn sie dann erneut löschcodiert wird und der Merkle-Baum für die lokal berechneten Anteile berechnet wird, stimmt die Wurzel mit derjenigen überein, über die ein Konsens erzielt wurde.

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

3. Die Zeile wird nicht wiederhergestellt.

Es lässt sich leicht zeigen, dass Option (1) für alle Teilnehmer gilt, wenn Option (1) für mindestens einen der oben genannten Teilnehmer zutrifft, und umgekehrt, wenn Option (2) oder (3) für mindestens einen Teilnehmer zutrifft Für alle Teilnehmer gilt Option (2) oder (3). Somit wird jede Zeile im Satz entweder von allen Teilnehmern erfolgreich wiederhergestellt, oder es gelingt allen Teilnehmern nicht, sie wiederherzustellen. Die resultierende Zufallszahl ist dann ein XOR nur der Zeilen, die die Teilnehmer wiederherstellen konnten.

Schwellensignaturen

Ein weiterer Ansatz zur Zufälligkeit besteht darin, sogenannte BLS-Schwellenwertsignaturen zu verwenden. Ein auf Schwellenwertsignaturen basierender Zufallszahlengenerator bietet genau die gleichen Garantien wie der oben beschriebene auf Löschcode basierende Algorithmus, weist jedoch eine deutlich geringere asymptotische Anzahl von Nachrichten auf, die für jede generierte Zahl über das Netzwerk gesendet werden.

Bei BLS-Signaturen handelt es sich um ein Design, das es mehreren Teilnehmern ermöglicht, eine gemeinsame Signatur für eine Nachricht zu erstellen. Diese Signaturen werden häufig verwendet, um Platz und Bandbreite zu sparen, da nicht mehrere Signaturen gesendet werden müssen. 

Eine häufige Anwendung für BLS-Signaturen in Blockchain-Protokollen ist neben der Generierung von Zufallszahlen auch die Blocksignierung in BFT-Protokollen. Nehmen wir an, 100 Teilnehmer erstellen Blöcke und ein Block gilt als endgültig, wenn 67 von ihnen ihn unterschreiben. Sie können alle ihre Teile der BLS-Signatur einreichen und sich mithilfe eines Konsensalgorithmus auf 67 davon einigen und diese dann zu einer BLS-Signatur zusammenführen. Zur Erstellung der endgültigen Signatur können beliebige 67 (oder mehr) Teile verwendet werden. Dies hängt davon ab, welche 67 Signaturen kombiniert wurden und kann daher variieren. Auch wenn unterschiedliche Entscheidungen der 67 Teilnehmer eine unterschiedliche Signatur erzeugen, ist jede dieser Signaturen gültig Unterschrift für den Block. Die verbleibenden Teilnehmer müssen dann statt 67 nur noch eine Signatur pro Block über das Netzwerk empfangen und verifizieren, was die Belastung des Netzwerks deutlich reduziert.

Es stellt sich heraus, dass, wenn die von den Teilnehmern verwendeten privaten Schlüssel auf eine bestimmte Weise generiert werden, die resultierende Signatur unabhängig davon, welche 67 Signaturen (oder mehr, aber nicht weniger) aggregiert werden, dieselbe ist. Dies kann als Zufallsquelle genutzt werden: Die Teilnehmer einigen sich zunächst auf eine Nachricht, die sie signieren (dies könnte die Ausgabe von RANDAO oder nur der Hash des letzten Blocks sein; das spielt keine Rolle, solange er sich jedes Mal ändert). und ist konsistent) und erstellen Sie eine BLS-Signatur dafür. Das Ergebnis der Generierung wird unvorhersehbar sein, bis 67 Teilnehmer ihre Teile liefern, und danach ist das Ergebnis bereits vorbestimmt und kann nicht von den Aktionen eines Teilnehmers abhängen.

Dieser Ansatz zur Zufälligkeit ist praktikabel, solange mindestens ⅔ der Online-Teilnehmer das Protokoll befolgen, und er ist unvoreingenommen und unvorhersehbar, solange mindestens ⅓ der Teilnehmer das Protokoll befolgen. Es ist wichtig zu beachten, dass ein Angreifer, der mehr als ⅓, aber weniger als ⅔ der Teilnehmer kontrolliert, das Protokoll stoppen kann, seine Ausgabe jedoch nicht vorhersagen oder beeinflussen kann.

Schwellenwertsignaturen selbst sind ein sehr interessantes Thema. Im zweiten Teil des Artikels analysieren wir im Detail, wie sie funktionieren und wie genau es notwendig ist, Teilnehmerschlüssel zu generieren, damit Schwellenwertsignaturen als Zufallszahlengenerator verwendet werden können.

Abschließend

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

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

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

Alle Neuigkeiten auf Russisch können Sie unter verfolgen Telegrammgruppe und Gruppe auf VKontakte, und auf Englisch im offiziellen zwitschern.

Bis bald!

Source: habr.com