Hallo, Habr!
In In diesem Artikel haben wir besprochen, warum es notwendig sein kann, Zufallszahlen für Teilnehmer zu generieren, die sich gegenseitig nicht vertrauen, welche Anforderungen an solche Zufallszahlengeneratoren gestellt werden und haben zwei Ansätze für deren Implementierung betrachtet.
In diesem Abschnitt des Artikels werden wir einen weiteren Ansatz ausführlich behandeln, der Schwellenwertsignaturen verwendet.
Ein wenig Kryptographie
Um zu verstehen, wie Schwellenwertsignaturen funktionieren, muss man ein wenig Grundkenntnisse in Kryptographie haben. Wir verwenden zwei Konzepte: Skalare, oder einfach Zahlen, die wir mit Kleinbuchstaben kennzeichnen (x, y) und Punkte auf einer elliptischen Kurve, die wir mit Großbuchstaben kennzeichnen.
Um die Grundlagen der Schwellenwertsignaturen zu verstehen, muss man nicht wissen, wie elliptische Kurven funktionieren, außer ein paar grundlegenden Dingen:
Punkte auf einer elliptischen Kurve können addiert und mit einem Skalar multipliziert werden (die Multiplikation mit einem Skalar kennzeichnen wir als xG, obwohl die Notation Gx in der Literatur auch häufig verwendet wird). Das Ergebnis der Addition und Multiplikation mit einem Skalar ist ein Punkt auf der elliptischen Kurve.
Nur aus dem Punkt G und dessen Produkt mit dem Skalar xG kann man nicht berechnen x.
Wir werden auch das Konzept von Polynomen verwenden p(x) Grad k-1. Insbesondere werden wir die folgende Eigenschaft von Polynomen nutzen: Wenn wir den Wert kennen p(x) für beliebige k verschiedene x (und keine weiteren Informationen über p(x)), können wir berechnen p(x) für eine andere x.
Es ist interessant, dass für jedes Polynom p(x) und einen bestimmten Punkt auf der Kurve G, wenn wir den Wert kennen p(x)G für beliebige k verschiedene Werte x, können wir auch berechnen p(x)G für jede x.
Diese Informationen reichen aus, um in die Details zu gehen, wie Schwellenwertsignaturen funktionieren und wie man sie zur Generierung von Zufallszahlen verwendet.
Zufallszahlengenerator auf Basis von Schwellenwertsignaturen
Angenommen, dass n Teilnehmer ein zufälliges Zahl generieren möchten, und wir wollen, dass die Teilnahme von beliebigen k von ihnen ausreicht, um eine Zahl zu generieren, aber dass Angreifer, die kontrollieren k-1 oder weniger Teilnehmer, die generierte Zahl nicht vorhersagen oder beeinflussen können.
Angenommen, es gibt ein solches Polynom p(x) Grad k-1, dass der erste Teilnehmer weiß p(1), der zweite weiß p(2), und so weiter (n-ter weiß p(n)). Angenommen, es gibt einen bestimmten Punkt, an dem alle wissen G für alle Werte p(x)G für alle Werte x. Wir nennen p(i) die „private Komponente“ ides -ten Teilnehmers (weil nur i-ter Teilnehmer sie kennt), und p(i)G die „öffentliche Komponente“ ides -ten Teilnehmers (weil alle Teilnehmer sie kennen). Wie Sie sich erinnern, reicht das Wissen p(i)G nicht aus, um p(i) wiederherzustellen.
Die Erstellung eines solchen Polynoms, sodass nur der i-teTeilnehmer und niemand sonst seine private Komponente kennt – das ist der schwierigste und interessanteste Teil des Protokolls, den wir im Folgenden behandeln werden. Nehmen wir vorläufig an, wir haben ein solches Polynom, und alle Teilnehmer kennen ihre privaten Komponenten.
Wie können wir ein solches Polynom verwenden, um eine Zufallszahl zu generieren? Zunächst benötigen wir eine Zeichenkette, die zuvor nicht als Eingabe für den Generator verwendet wurde. Im Fall der Blockchain ist der Hash des letzten Blocks h ein guter Kandidat für eine solche Zeichenkette. Angenommen, die Teilnehmer möchten eine Zufallszahl erstellen, indem sie h als Seed verwenden. Zunächst konvertieren die Teilnehmer h in einen Punkt auf der Kurve mithilfe einer vorher definierten Funktion:
H = scalarToPoint(h)
Dann berechnet jeder Teilnehmer i und veröffentlicht Hi = p(i)H, was sie tun können, weil sie wissen p(i) und H. Offenlegung Hund erlaubt es anderen Teilnehmern nicht, die private Komponente wiederherzustellen i-en Teilnehmer, weshalb ein Set privater Komponenten von Block zu Block verwendet werden kann. Auf diese Weise muss der teure Algorithmus zur Erstellung des Polynoms, der unten beschrieben ist, nur einmal ausgeführt werden.
Wenn k Teilnehmer geöffnet Hi = p(i)H, alle können berechnen Hx = p(x)H für alle x dank der Eigenschaft von Polynomen, die wir im vorherigen Abschnitt besprochen haben. An diesem Punkt berechnen alle Teilnehmer H0 = p(0)H, und das ist die resultierende Zufallszahl. Es sei darauf hingewiesen, dass niemand weiß p(0), und somit ist die einzige Möglichkeit, p(0)H zu berechnen – das Interpolieren p(x)H, was nur möglich ist, wenn k die Werte p(i)H bekannt sind. Das Öffnen von weniger p(i)H gibt keine Informationen über p(0)H.
Der obige Generator hat alle Eigenschaften, die wir wünschen: Angreifer, die nur über k-1 Teilnehmer oder weniger kontrollieren, haben keine Informationen und keinen Einfluss auf die Ausgabe, während alle k Teilnehmer die resultierende Zahl berechnen können und jede Teilmenge von k Teilnehmern immer das gleiche Ergebnis für denselben Seed erhält.
Es gibt ein Problem, das wir oben sorgfältig umgangen sind. Damit die Interpolation funktioniert, ist es wichtig, dass der Wert Hi, den jeder Teilnehmer veröffentlicht hat, i tatsächlich gleich p(i)H. Da niemand außer dem i-ten Teilnehmer weiß, p(i), kann niemand außer i-tedem Teilnehmer überprüfen, ob Hallo tatsächlich korrekt berechnet wurde, und ohne einen kryptografischen Beweis der Korrektheit Hkann ein Angreifer jeden beliebigen Wert als Hallo, veröffentlichen und willkürlich Einfluss auf die Ausgabe des Zufallszahlengenerators nehmen.:
Verschiedene Werte H_1, die vom ersten Teilnehmer gesendet werden, führen zu unterschiedlichen resultierenden H_0.
Es gibt mindestens zwei Möglichkeiten, die Korrektheit Hi zu beweisen, die wir betrachten werden, nachdem wir die Polynomialerzeugung behandelt haben.
Polynomialerzeugung
Im vorherigen Abschnitt haben wir vorausgesetzt, dass wir ein solches Polynom p(x) Grad k-1 haben, dass der Teilnehmer i weiß p(i), und niemand sonst Informationen über diesen Wert hat. Im nächsten Abschnitt wird es auch notwendig sein, dass für einen bestimmten vordefinierten Punkt G alle wissen, p(x)G für alle x.
In diesem Abschnitt werden wir annehmen, dass jeder Teilnehmer lokal einen privaten Schlüssel hat, xi, bekannt ist der entsprechende öffentliche Schlüssel Xi.
Ein möglicher Protokoll zur Generierung von Polynomen ist wie folgt:
Jeder Teilnehmer i erstellt lokal ein beliebiges Polynom pi(x) der Ordnung k-1. Diese senden dann an jeden Teilnehmer j den Wert pi(j), verschlüsselt mit dem öffentlichen Schlüssel Xj. Somit weiß nur i-tej- und teilnehmer werj- i(j). Der Teilnehmer pankündigt ebenfalls öffentlich i pi(j)G einschließlich. für alle j ab 1 bis zu k Alle Teilnehmer verwenden einen Konsens, um auszuwählen
Teilnehmer, deren Polynome verwendet werden. Da einige Teilnehmer offline sein können, können wir nicht warten, bis alle k Teilnehmer ihre Polynome veröffentlicht haben. Das Ergebnis dieses Schrittes ist eine Menge n bestehend aus mindestens Z Polynomen, die im Schritt (1) erstellt wurden. k Die Teilnehmer stellen sicher, dass die ihnen bekannten Werte.
i(j) den öffentlich angekündigten ppi(j)G entsprechen. Nach diesem Schritt sollten nur noch Polynome übrig bleiben, für die privat übertragene berechnet seinen privaten Anteil Z p(j) ppi(j)G entsprechen. Nach diesem Schritt sollten nur noch Polynome übrig bleiben, für die privat übertragene
Jeder Teilnehmer j als Summe i(j) für alle . Jeder Teilnehmer berechnet auch alle Werte ppi(x)G für alle i i in Zp(x) – p(x)G . Jeder Teilnehmer berechnet auch alle Werte es ist tatsächlich ein Polynom der Ordnung in Z.
nicht mit einem Bindestrich beginnt. In YAML bedeutet dies, dass k-1, weil es die Summe der einzelnen i(x), von denen jede ein Polynom der Ordnung ist. weil es die Summe der einzelnen pi(x), wobei jeder ein Polynom vom Grad k-1. Dann beachten Sie, dass während jeder Teilnehmer j weiß p(j), sie keine Informationen über p(x) für x ≠ j. Tatsächlich müssen sie, um diesen Wert zu berechnen, alle pi(x), und solange ein Teilnehmer j nicht mindestens einen der gewählten Polynome kennt, haben sie keine ausreichenden Informationen über p(x).
Das ist der gesamte Prozess der Polynomgenerierung, der im vorherigen Abschnitt erforderlich war. Die Schritte 1, 2 und 4 oben haben eine recht offensichtliche Umsetzung. Schritt 3 ist jedoch nicht trivial.
Konkret müssen wir beweisen können, dass die verschlüsselten pi(j) tatsächlich mit den veröffentlichten Nach diesem Schritt sollten nur noch Polynome übrig bleiben, für die privat übertragene Wenn wir das nicht beweisen können, kann ein Angreifer i statt pi(j) an den Teilnehmer senden, jund der Teilnehmer j wird den echten Wert nicht erhalten pi(j), und kann seine private Komponente nicht berechnen..
Es gibt ein kryptografisches Protokoll, das es ermöglicht, eine zusätzliche Nachricht zu erstellen proofi(j), sodass jeder Teilnehmer, der einen Wert hat e, und auch proofi(j) und pi(j)G, kann lokal überprüfen, dass e es tatsächlich pi(j), mit dem Schlüssel des Teilnehmers j verschlüsselt ist. Leider ist die Größe eines solchen Beweises unglaublich groß, und da es notwendig ist, diese zu veröffentlichen, O(nk) wird es nicht möglich sein, sie für diesen Zweck zu verwenden.
Anstatt zu beweisen, dass pi(j) entspricht pi(j)G, können wir im Protokoll zur Erzeugung des Polynoms einen sehr großen Zeitraum einplanen, während dessen alle Teilnehmer die erhaltenen verschlüsselten Nachrichten überprüfen, pi(j), und wenn die entschlüsselte Nachricht nicht mit dem öffentlichen pi(j)G übereinstimmt, veröffentlichen sie den kryptografischen Beweis dafür, dass die erhaltene verschlüsselte Nachricht falsch ist. Es ist viel einfacher zu beweisen, dass die Nachricht nicht entspricht pi(G) ist als zu beweisen, dass sie übereinstimmt. Es ist anzumerken, dass dies erfordert, dass jeder Teilnehmer mindestens einmal im Netzwerk erscheint innerhalb der für die Erstellung solcher Beweise vorgesehenen Zeit und beruht auf der Annahme, dass, wenn sie einen solchen Beweis veröffentlicht haben, dieser alle anderen Teilnehmer innerhalb derselben festgelegten Zeit erreicht.
Wenn ein Teilnehmer in diesem Zeitraum nicht online ist und tatsächlich mindestens eine fehlerhafte Komponente hatte, kann dieser spezifische Teilnehmer nicht an der weiteren Generierung von Zahlen teilnehmen. Das Protokoll wird jedoch weiterhin funktionieren, sofern es mindestens k Teilnehmer gibt, die entweder nur korrekte Komponenten erhalten haben oder rechtzeitig einen Nachweis für die Fehlerhaftigkeit abgegeben haben.
Nachweise über die Korrektheit von H_i
Der letzte Punkt, den wir besprechen müssen, ist, wie man die Korrektheit der veröffentlichten Hi beweist, nämlich dass Hi = p(i)H, ohne Offenlegung p(i) wiederherzustellen.
Erinnern wir uns daran, dass die Werte H, G, p(i)G öffentlich sind und allen bekannt sind. Der Vorgang der Bestimmung von p(i) bekannt p(i)G und G wird als diskreter Logarithmus oder dlog, und wir möchten beweisen, dass:
dlog(p(i)G, G) = dlog(Hi, H)
ohne Offenlegung p(i). Es existieren Konstruktionen für solche Nachweise, wie zum Beispiel.
Mit einer solchen Konstruktion sendet jeder Teilnehmer zusammen mit Hallo einen Nachweis über die Korrektheit gemäß der Konstruktion.
Wenn eine Zufallszahl generiert wird, muss sie häufig von den Teilnehmern verwendet werden, die sie nicht erzeugt haben. Daher müssen diese Teilnehmer zusammen mit der Zahl alle Hallo und begleitenden Beweise erhalten.
Ein neugieriger Leser könnte fragen: Da die endgültige Zufallszahl – das ist H0, und p(0)G – ist öffentliche Information, warum ist ein Beweis für jedes einzelne erforderlich? HWarum nicht stattdessen den Beweis schicken, dass
dlog(p(0)G, G) = dlog(H0, H)
Das Problem ist, dass mit dem Schnorr-Protokoll ein solcher Beweis nicht erstellt werden kann, weil niemand den Wert p(0), der zur Erstellung des Beweises erforderlich ist, kennt, und darüber hinaus basiert der gesamte Zufallszahlengenerator darauf, dass niemand diesen Wert kennt. Darum müssen alle Werte Hallo und ihre individuellen Beweise vorliegen, um die Korrektheit zu belegen. H0.
Wäre jedoch eine Operation an den Punkten auf elliptischen Kurven vorhanden, die semantisch dem Multiplikationsprozess ähnlich ist, wäre der Korrektheitsbeweis H0 trivial, wir müssten nur sicherstellen, dass
H0 × G = p(0)G × H
Wenn die gewählte Kurve elliptische Kurvenpaarungen unterstützt. , dieser Nachweis funktioniert. In diesem Fall H0 – das ist nicht nur die Ausgabe des Zufallszahlengenerators, die jeder Teilnehmer, der es weiß, überprüfen kann G, H und p(0)G. H0 – es ist auch die Signatur der Nachricht, die als Seed verwendet wurde und bestätigt, dass k und n die Teilnehmer diese Nachricht signiert haben. Somit, wenn Seed – der Hash des Blocks im Blockchain-Protokoll ist, dann H0 ist das gleichzeitig eine Multi-Signatur für den Block und eine sehr gute Zufallszahl.
Zusammenfassung
Dieser Artikel ist Teil einer Serie technischer Blogartikel . NEAR ist ein Blockchain-Protokoll und eine Plattform zur Entwicklung von dezentralen Anwendungen mit 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
