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

Hey Habr!

В der erste Teil In diesem Artikel haben wir diskutiert, warum es notwendig sein kann, Zufallszahlen für Teilnehmer zu generieren, die sich gegenseitig nicht vertrauen, welche Anforderungen an solche Zufallszahlengeneratoren gestellt werden und zwei Ansätze für deren Implementierung betrachtet.

In diesem Teil des Artikels werfen wir einen genaueren Blick auf einen anderen Ansatz, der Schwellenwertsignaturen verwendet.

Ein bisschen Kryptographie

Um zu verstehen, wie Schwellenwertsignaturen funktionieren, müssen Sie ein wenig Grundkenntnisse in der Kryptographie haben. Wir werden zwei Konzepte verwenden: Skalare oder einfach Zahlen, die wir mit Kleinbuchstaben bezeichnen (x, y) und Punkte auf der elliptischen Kurve, die wir mit Großbuchstaben bezeichnen.

Um die Grundlagen von Schwellenwertsignaturen zu verstehen, müssen Sie außer ein paar grundlegenden Dingen nicht verstehen, wie elliptische Kurven funktionieren:

1. Punkte auf einer elliptischen Kurve können addiert und mit einem Skalar multipliziert werden (wir bezeichnen die Multiplikation mit einem Skalar als). xG, obwohl die Notation Gx wird auch häufig in der Literatur verwendet). Das Ergebnis der Addition und Multiplikation mit einem Skalar ist ein Punkt auf einer elliptischen Kurve.

2. Nur den Punkt kennen G und sein Produkt mit einem Skalar xG kann nicht berechnet werden x.

Wir werden auch den Begriff eines Polynoms verwenden p (x) Grad k-1. Insbesondere werden wir die folgende Eigenschaft von Polynomen verwenden: wenn wir den Wert kennen p (x) für jeden k unterschiedlich x (Und wir haben keine weiteren Informationen darüber p (x)), können wir berechnen p (x) für alle anderen x.

Das ist für jedes Polynom interessant p (x) und irgendein Punkt auf der Kurve Gdie Bedeutung kennen p(x)G für jeden k unterschiedliche Bedeutungen x, können wir auch berechnen p(x)G für jeden x.

Dies sind genügend Informationen, um sich mit den Einzelheiten der Funktionsweise von Schwellenwertsignaturen und ihrer Verwendung zur Generierung von Zufallszahlen zu befassen.

Zufallszahlengenerator für Schwellenwertsignaturen

Sagen wir das so n Die Teilnehmer möchten eine Zufallszahl generieren, und wir möchten, dass jeder teilnimmt k Es gab genug davon, um eine Nummer zu generieren, aber damit die Angreifer die Kontrolle hatten k-1 oder weniger Teilnehmer konnten die generierte Zahl nicht vorhersagen oder beeinflussen.

Angenommen, es gibt ein solches Polynom p (x) Grad k-1 was der erste Teilnehmer weiß p (1), der zweite weiß es p(2), usw (n-th weiß p(n)). Wir gehen auch davon aus, dass es sich um einen vorher festgelegten Punkt handelt G jeder weiß es p(x)G für alle Werte x. Wir werden anrufen p (i) „private Komponente“ iTeilnehmer (weil nur ider te Teilnehmer kennt sie), und Schwein „öffentliche Komponente“ i-te Teilnehmerin (weil alle Teilnehmer sie kennen). Wie Sie sich erinnern, Wissen Schwein nicht genug, um es wiederherzustellen Pi).

Erstellen Sie ein solches Polynom nur damit i-Der erste Teilnehmer und niemand sonst kannte seine private Komponente – dies ist der komplexeste und interessanteste Teil des Protokolls, den wir im Folgenden analysieren werden. Nehmen wir zunächst an, dass wir ein solches Polynom haben und alle Teilnehmer ihre privaten Komponenten kennen.

Wie können wir ein solches Polynom verwenden, um eine Zufallszahl zu erzeugen? Zunächst benötigen wir eine Zeichenfolge, die zuvor noch nicht als Eingabe für den Generator verwendet wurde. Im Falle einer Blockchain der Hash des letzten Blocks h ist ein guter Kandidat für eine solche Linie. Lassen Sie die Teilnehmer eine Zufallszahl erstellen h wie Samen. Die Teilnehmer konvertieren zuerst h zu einem Punkt auf der Kurve mit einer beliebigen vordefinierten Funktion:

H = scalarToPoint(h)

Dann jeder Teilnehmer i berechnet und veröffentlicht Hi = p(i)H, Was können sie tun, weil sie es wissen? p(i) und H. Offenlegung HIch erlaube anderen Teilnehmern nicht, die private Komponente wiederherzustellen iTeilnehmer, und daher kann von Block zu Block ein Satz privater Komponenten verwendet werden. Somit muss der unten beschriebene teure Polynomgenerierungsalgorithmus nur einmal ausgeführt werden.

Wenn k Die Teilnehmer wurden obduziert Hi = p(i)H, Rechnen kann jeder Hx = p(x)H für alle x dank der Eigenschaft von Polynomen, die wir im letzten Abschnitt besprochen haben. In diesem Moment rechnen alle Teilnehmer H0 = p(0)H, und das ist die resultierende Zufallszahl. Bitte beachten Sie, dass es niemand weiß p(0), und daher die einzige Möglichkeit zur Berechnung p(0)H – das ist Interpolation p(x)H, was nur möglich ist, wenn k Werte p(i)H bekannt. Öffnen Sie jede kleinere Menge p(i)H macht keine Angaben dazu p(0)H.

Der obige Generator hat alle Eigenschaften, die wir wollen: Nur Angreifer kontrollieren k-1 Teilnehmer oder weniger haben keine Informationen oder Einfluss auf die Schlussfolgerung, während alle k Die Teilnehmer können die resultierende Zahl und jede Teilmenge davon berechnen k Die Teilnehmer werden für denselben Samen immer zum gleichen Ergebnis kommen.

Es gibt ein Problem, das wir oben sorgfältig vermieden haben. Damit die Interpolation funktioniert, ist es wichtig, dass der Wert Hi, das von jedem Teilnehmer veröffentlicht wurde i es war wirklich dasselbe p(i)H. Da niemand außer iDer -te Teilnehmer weiß es nicht Pi), niemand außer i-Der Teilnehmer kann das nicht überprüfen Hi tatsächlich korrekt berechnet, und zwar ohne jeglichen kryptografischen Nachweis der Korrektheit HIch kann als Angreifer jeden Wert veröffentlichen Hallo, und die Ausgabe des Zufallszahlengenerators willkürlich beeinflussen:

Unterschiedliche Werte von H_1, die vom ersten Teilnehmer gesendet wurden, führen zu unterschiedlichen resultierenden H_0

Es gibt mindestens zwei Möglichkeiten, die Richtigkeit nachzuweisen Hi, wir werden sie betrachten, nachdem wir die Erzeugung des Polynoms analysiert haben.

Polynomgenerierung

Im letzten Abschnitt haben wir angenommen, dass wir ein solches Polynom haben p (x) Grad k-1 dass der Teilnehmer i weiß p (i), und niemand sonst hat irgendwelche Informationen über diesen Wert. Im nächsten Abschnitt werden wir das auch für einen vorher festgelegten Punkt benötigen G jeder wusste es p(x)G für alle x.

In diesem Abschnitt gehen wir davon aus, dass jeder Teilnehmer lokal über einen privaten Schlüssel verfügt xi, sodass jeder den entsprechenden öffentlichen Schlüssel kennt Xi.

Ein mögliches Protokoll zur Polynomgenerierung lautet wie folgt:

1. Jeder Teilnehmer i Erstellt lokal ein beliebiges Polynom pi(x) Grad k-1. Anschließend schicken sie jeden Teilnehmer j Wert pi(j), verschlüsselt mit öffentlichem Schlüssel Xj. Also nur i-th и j-th Teilnehmer wissen pi(j). Teilnehmer i kündigt auch öffentlich an pi(j)G für alle j aus 1 auf k inklusive.

2. Alle Teilnehmer nutzen bei der Auswahl einen gewissen Konsens k Teilnehmer, deren Polynome verwendet werden. Da einige Teilnehmer möglicherweise offline sind, können wir nicht warten, bis alle Teilnehmer anwesend sind n Die Teilnehmer veröffentlichen Polynome. Das Ergebnis dieses Schritts ist eine Menge Z bestehend aus mindestens k In Schritt (1) erstellte Polynome.

3. Die Teilnehmer stellen sicher, dass die Werte, die sie kennen pi(j) entsprechen öffentlich bekannt gegeben pi(j)G. Nach diesem Schritt einsteigen Z nur Polynome, für die privat übertragen wird pi(j) entsprechen öffentlich bekannt gegeben pi(j)G.

4. Jeder Teilnehmer j berechnet seine private Komponente p(j) als Summe pi(j) für alle i в Z. Jeder Teilnehmer berechnet auch alle Werte p(x)G als Summe pi(x)G für alle i в Z.

Bitte beachten Sie, dass p(x) – es ist wirklich ein Polynom k-1, denn es ist die Summe des Einzelnen pi(x), von denen jedes ein Gradpolynom ist k-1. Beachten Sie dann, dass jeder Teilnehmer j weiß p(j), sie haben keine Informationen darüber p (x) für x ≠ j. Um diesen Wert zu berechnen, müssen sie tatsächlich alles wissen pi(x), und solange der Teilnehmer j Kennt mindestens eines der ausgewählten Polynome nicht und verfügt über keine ausreichenden Informationen darüber p(x).

Dies ist der gesamte Polynomgenerierungsprozess, der im letzten Abschnitt benötigt wurde. Die obigen Schritte 1, 2 und 4 haben eine ziemlich offensichtliche Implementierung. Aber Schritt 3 ist nicht so trivial.

Konkret müssen wir die Verschlüsselung nachweisen können pi(j) entsprechen wirklich den veröffentlichten pi(j)G. Wenn wir es nicht beweisen können, der Angreifer i kann stattdessen Müll senden pi(j) zum Teilnehmer j, und Teilnehmer j wird nicht in der Lage sein, den tatsächlichen Wert zu erhalten pi(j), und kann seine private Komponente nicht berechnen.

Es gibt ein kryptografisches Protokoll, mit dem Sie eine zusätzliche Nachricht erstellen können Beweisi(j), so dass jeder Teilnehmer einen gewissen Wert hat e, sowie Beweisi(j) и pi(j)G, kann das lokal überprüfen e - es ist wirklich pi(j), mit dem Schlüssel des Teilnehmers verschlüsselt j. Leider ist der Umfang solcher Beweise unglaublich umfangreich und daher notwendig, sie zu veröffentlichen O (nk) Solche Beweise können für diesen Zweck nicht verwendet werden.

Anstatt das zu beweisen pi(j) Streichhölzer pi(j)G können wir im Polynomgenerierungsprotokoll einen sehr langen Zeitraum vorsehen, in dem alle Teilnehmer die empfangene Verschlüsselung prüfen pi(j), und wenn die entschlüsselte Nachricht nicht der Öffentlichkeit entspricht pi(j)G, sie veröffentlichen einen kryptografischen Beweis dafür, dass die verschlüsselte Nachricht, die sie erhalten haben, falsch ist. Beweisen Sie, dass die Nachricht nicht Streichhölzer Schwein) viel einfacher, als zu beweisen, dass es passt. Es ist zu beachten, dass dies erfordert, dass jeder Teilnehmer während der für die Erstellung eines solchen Nachweises vorgesehenen Zeit mindestens einmal online erscheint, und dass davon ausgegangen wird, dass ein solcher Beweis, wenn er ihn veröffentlicht, in derselben vorgegebenen Zeit bei allen anderen Teilnehmern eintrifft.

Wenn ein Teilnehmer in diesem Zeitraum nicht online erschienen ist und mindestens eine fehlerhafte Komponente hatte, kann dieser Teilnehmer nicht an der weiteren Nummerngenerierung teilnehmen. Das Protokoll funktioniert jedoch weiterhin, wenn es zumindest vorhanden ist k Teilnehmer, die entweder gerade erst die richtigen Komponenten erhalten haben oder es geschafft haben, innerhalb der vorgegebenen Zeit einen Nachweis über die Unrichtigkeit zu hinterlassen.

Beweise für die Korrektheit von H_i

Der letzte Teil, der noch diskutiert werden muss, ist die Frage, wie die Richtigkeit der veröffentlichten Informationen nachgewiesen werden kann Hich, nämlich das Hi = p(i)H, ohne zu öffnen Pi).

Erinnern wir uns an die Werte H, G, p(i)G öffentlich und jedem bekannt. Operation empfangen p (i) wissend Schwein и G namens diskreter Logarithmus, oder dlog, und das wollen wir beweisen:

dlog(p(i)G, G) = dlog(Hi, H)

ohne Offenlegung p (i). Es gibt beispielsweise Konstruktionen für solche Beweise Schnorr-Protokoll.

Mit diesem Design kann jeder Teilnehmer mitmachen Hi sendet einen Nachweis der Korrektheit entsprechend dem Design.

Sobald eine Zufallszahl generiert wurde, muss sie häufig von anderen Teilnehmern als denjenigen verwendet werden, die sie generiert haben. Diese Teilnehmer müssen zusammen mit der Nummer alle senden Hi und entsprechende Beweise.

Ein neugieriger Leser könnte fragen: Da ist die endgültige Zufallszahl H0, und p(0)G – Das sind öffentliche Informationen, warum brauchen wir Beweise für jeden Einzelnen? HWarum schickst du mir stattdessen nicht einen Beweis dafür?

dlog(p(0)G, G) = dlog(H0, H)

Das Problem besteht darin, dass ein solcher Beweis nicht mit dem Schnorr-Protokoll erstellt werden kann, da niemand den Wert kennt p (0), notwendig, um den Beweis zu erstellen, und darüber hinaus basiert der gesamte Zufallszahlengenerator auf der Tatsache, dass niemand diesen Wert kennt. Daher ist es notwendig, alle Werte zu haben Hi und ihre individuellen Beweise zum Nachweis der Richtigkeit H0.

Wenn es jedoch eine Operation an Punkten auf elliptischen Kurven gäbe, die semantisch der Multiplikation ähnelt, wäre der Beweis der Korrektheit H0 wäre trivial, das würden wir einfach sicherstellen

H0 × G = p(0)G × H

Wenn die ausgewählte Kurve dies unterstützt Elliptische Kurvenpaare, dieser Beweis funktioniert. In diesem Fall H0 ist nicht nur die Ausgabe eines Zufallszahlengenerators, die von jedem Teilnehmer überprüft werden kann, der es weiß G, H и p(0)G. H0 ist auch eine Signatur der Nachricht, die als Startwert verwendet wurde und dies bestätigt k и n Teilnehmer haben diese Nachricht unterzeichnet. Also, wenn Samen - ist dann der Hash des Blocks im Blockchain-Protokoll H0 ist sowohl eine Mehrfachsignatur auf einem Block als auch eine sehr gute Zufallszahl.

Abschließend

Dieser Artikel ist Teil einer technischen Blogserie 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