Hallo, Habra!
Im In den Artikeln haben wir besprochen, warum es notwendig sein kann, Zufallszahlen für Teilnehmer zu generieren, die sich nicht gegenseitig vertrauen, welche Anforderungen an solche Zufallszahlengeneratoren gestellt werden und haben zwei Ansätze zu ihrer Implementierung betrachtet.
In diesem Teil des Artikels werden wir einen weiteren Ansatz im Detail untersuchen, der Schwellenunterschriften verwendet.
Ein wenig Krypto
Um zu verstehen, wie Schwellenunterschriften funktionieren, muss man ein wenig grundlegende Krypto verstehen. Wir werden zwei Konzepte verwenden: Skalare, oder einfach Zahlen, die wir mit Kleinbuchstaben bezeichnen werden (x, y) und Punkte auf einer elliptischen Kurve, die wir mit Großbuchstaben bezeichnen werden.
Um die Grundlagen der Schwellenunterschriften zu verstehen, muss man nicht wissen, wie elliptische Kurven funktionieren, außer einige grundlegende Dinge:
Man kann Punkte auf einer elliptischen Kurve addieren und mit einem Skalar multiplizieren (die Multiplikation mit einem Skalar werden wir als xGbezeichnen, obwohl die Notation Gx auch oft in der Literatur verwendet wird). Das Ergebnis der Addition und der Multiplikation mit einem Skalar ist ein Punkt auf der elliptischen Kurve.
Nur mit dem Punkt G und seinem Produkt mit dem Skalar xG kann man nicht berechnen x.
Wir werden auch das Konzept eines Polynoms verwenden p(x) der Ordnung k-1. Insbesondere werden wir die folgende Eigenschaft von Polynomen verwenden: Wenn wir den Wert p(x) für beliebige k unterschiedliche x (und keine weiteren Informationen über p(x)) haben, können wir p(x) für jeden anderen berechnen x.
Es ist interessant, dass man für jedes Polynom p(x) und einen bestimmten Punkt auf der Kurve G, wobei man den Wert p(x)G für beliebige k verschiedener Werte x, auch berechnen kann p(x)G für jedes x.
Diese Informationen sind ausreichend, um in die Details zu gehen, wie Schwellenunterschriften funktionieren und wie sie zur Generierung von Zufallszahlen verwendet werden können.
Zufallszahlengenerator auf Schwellenunterschriften
Nehmen wir an, dass n Teilnehmer ein Zufallszahl generieren wollen, und wir möchten, dass die Teilnahme von beliebigen k von ihnen ausreicht, um die Zahl zu generieren, aber dass Angreifer, die kontrollieren k-1 oder weniger Teilnehmer, die generierte Zahl nicht vorhersagen oder beeinflussen können.
Nehmen wir an, es gibt ein solches Polynom p(x) der Ordnung k-1, dass der erste Teilnehmer weiß p(1), der zweite weiß p(2), und so weiter (n-ter weiß p(n)). Angenommen, dass für einen bestimmten vorab definierten Punkt G alle wissen p(x)G für alle Werte x. Wir werden es nennen p(i) „private Komponente“ i-es Teilnehmers (weil nur i-er Teilnehmer sie kennt), und p(i)G „öffentliche Komponente“ i-es Teilnehmers (weil alle Teilnehmer sie kennen). Wie Sie sich erinnern, reicht das Wissen p(i)G nicht aus, um zu rekonstruieren p(i).
Die Erstellung eines solchen Polynoms, sodass nur i--er Teilnehmer und niemand sonst seine private Komponente kennt – ist der schwierigste und interessanteste Teil des Protokolls, das wir unten erläutern werden. Angenommen, wir haben ein solches Polynom, und alle Teilnehmer kennen ihre privaten Komponenten.
Wie können wir ein solches Polynom nutzen, um eine Zufallszahl zu generieren? Zunächst benötigen wir eine bestimmte Zeichenkette, die zuvor nicht als Eingabe für den Generator verwendet wurde. Im Fall von Blockchain ist der Hash des letzten Blocks h ein guter Kandidat für eine solche Zeichenkette. Nehmen wir an, die Teilnehmer möchten eine Zufallszahl erstellen, wobei sie h als Seed verwenden. Zuerst konvertieren die Teilnehmer h in einen Punkt auf der Kurve unter Verwendung einer beliebigen vordefinierten 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. Die Offenlegung Hi erlaubt es den anderen Teilnehmern nicht, die private Komponente i-es Teilnehmers zu rekonstruieren, und daher kann ein Satz privater Komponenten von Block zu Block verwendet werden. So muss der teure Algorithmus zur Erstellung des Polynoms, der unten beschrieben wird, nur einmal durchgeführt werden.
Wenn k Nach der Offenlegung Hi = p(i)H, können alle berechnen Hx = p(x)H für alle x aufgrund der Eigenschaften von Polynomen, die wir im vorherigen Abschnitt besprochen haben. In diesem Moment berechnen alle Teilnehmer H0 = p(0)H, und das ist die resultierende Zufallszahl. Beachten Sie, dass niemand weiß p(0), und daher ist der einzige Weg, p(0)H zu berechnen – die Interpolation p(x)H, was nur möglich ist, wenn k die Werte p(i)H bekannt sind. Die Offenlegung einer geringeren Anzahl verursacht p(i)H keine Informationen über p(0)H.
Der obige Generator hat alle Eigenschaften, die wir wollen: Angreifer, die nur k--1 Teilnehmer oder weniger kontrollieren, haben keine Informationen und keinen Einfluss auf die Ausgabe, während beliebige k Teilnehmer die resultierende Zahl berechnen können, und jede Teilmenge aus k Teilnehmern kommt immer zu demselben Ergebnis für denselben Seed.
Es gibt ein Problem, das wir oben umgangen haben. Damit die Interpolation funktioniert, ist es wichtig, dass der Wert Hi, den jeder Teilnehmer veröffentlicht hat, i tatsächlich gleich ist p(i)H. Da niemand außer dem i-ten Teilnehmer weiß, p(i), kann niemand außer i-dem -ten Teilnehmer überprüfen, ob Hi tatsächlich korrekt berechnet wurde und ohne einen kryptografischen Nachweis der Korrektheit Hkann ein Angreifer jeden Wert als Hallo, veröffentlichen und willkürlich die Ausgabe des Zufallszahlengenerators beeinflussen.:
Unterschiedliche Werte H_1, die vom ersten Teilnehmer gesendet wurden, führen zu unterschiedlichen resultierenden H_0.
Es gibt mindestens zwei Möglichkeiten, die Korrektheit von Hi zu beweisen. Wir werden diese betrachten, nachdem wir die Polynom-Generierung behandelt haben.
Polynom-Generierung
Im vorherigen Abschnitt haben wir angenommen, dass wir ein solches Polynom haben, p(x) der Ordnung k-1, sodass der Teilnehmer i weiß p(i), und niemand sonst hat irgendwelche Informationen über diesen Wert. Im nächsten Abschnitt müssen wir auch sicherstellen, dass für einen bestimmten vordefinierten Punkt G alle wissen, p(x)G für alle x.
In diesem Abschnitt gehen wir davon aus, dass jeder Teilnehmer lokal einen privaten Schlüssel xi, hat, sodass der entsprechende öffentliche Schlüssel Xi für alle bekannt ist.
Ein möglicher Protokoll zur Generierung des Polynoms ist folgender:
Jeder Teilnehmer i erzeugt lokal ein beliebiges Polynom pi(x) der Ordnung k-1. Sie senden dann an jeden Teilnehmer j system-id D pi(j), verschlüsselt mit dem öffentlichen Schlüssel Xj. So weiß nur der i--te und j-te-te Teilnehmer, pi(j). Der Teilnehmer i kündigt auch öffentlich an pi(j)G für alle j ab 1 bis k einschließlich.
Alle Teilnehmer nutzen einen Konsens, um die k Teilnehmer auszuwählen, deren Polynome verwendet werden. Da einige Teilnehmer offline sein könnten, können wir nicht warten, bis alle n Teilnehmer ihre Polynome veröffentlicht haben. Das Ergebnis dieses Schrittes ist eine Menge Z die aus mindestens k Polynomen besteht, die in Schritt (1) erstellt wurden..
Die Teilnehmer stellen sicher, dass die ihnen bekannten Werte pi(j) den öffentlich angekündigten pi(j)G entsprechen. Nach diesem Schritt sollten nur noch die Polynome übrig bleiben, für die privat übermittelte Z ihre private Komponente pi(j) den öffentlich angekündigten pi(j)G entsprechen.
Jeder Teilnehmer j p(j) als Summe i(j) für alle p. Jeder Teilnehmer berechnet auch alle Werte i in Zpi(x)G für alle i. p(x)G i(j) für alle p(x) – in Z.
Beachten Sie, dass ist tatsächlich ein Polynom der Ordnung k-1, da es sich um die Summe einzelner i(x) handelt, von denen jede ein Polynom der Ordnung pist. 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 der Teilnehmer j nicht mindestens eines der gewählten Polynome kennt, haben sie keine ausreichenden Informationen über p(x).
Das ist der gesamte Prozess der Erzeugung des Polynoms, der im vorherigen Abschnitt erforderlich war. Die Schritte 1, 2 und 4 oben haben eine recht offensichtliche Umsetzung. Schritt 3 ist jedoch nicht trivial.
Insbesondere müssen wir in der Lage sein zu beweisen, dass die verschlüsselten pi(j) tatsächlich den veröffentlichten entsprechen. pi(j)G entsprechen. Wenn wir das nicht beweisen können, könnte ein Angreifer i müll anstelle von pi(j) an den Teilnehmer senden, jund der Teilnehmer j wird den tatsächlichen Wert nicht erhalten pi(j), und wird seine private Komponente nicht berechnen können..
Es gibt ein kryptografisches Protokoll, das es ermöglicht, eine zusätzliche Nachricht zu erstellen, proofi(j), so dass jeder Teilnehmer, der einen bestimmten 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 angesichts der Tatsache, dass es notwendig ist, O(nk) solcher Beweise zu veröffentlichen, können sie nicht zu diesem Zweck verwendet werden.
Anstatt zu beweisen, dass pi(j) entspricht pi(j)G, können wir im Protokoll zur Erzeugung des Polynoms einen sehr langen Zeitraum einplanen, währenddessen alle Teilnehmer die erhaltenen verschlüsselten überprüfen, pi(j), und wenn die entschlüsselte Nachricht nicht mit der öffentlichen pi(j)G übereinstimmt, veröffentlichen sie einen kryptografischen Beweis dafür, dass die erhaltene verschlüsselte Nachricht falsch ist. Zu beweisen, dass die Nachricht nicht entspricht pi(G) ist viel einfacher, als zu beweisen, dass sie übereinstimmt. Es sollte angemerkt werden, dass dies erfordert, dass jeder Teilnehmer mindestens einmal im Netzwerk erscheint, während der Zeit, die für die Erstellung solcher Beweise vorgesehen ist, und beruht auf der Annahme, dass, wenn sie einen solchen Beweis veröffentlicht haben, er alle anderen Teilnehmer in dieser Zeit erreicht.
Wenn ein Teilnehmer in diesem Zeitraum nicht im Netzwerk erscheint und er tatsächlich mindestens eine fehlerhafte Komponente hatte, kann dieser spezielle Teilnehmer nicht an der weiteren Zahlenerzeugung teilnehmen. Das Protokoll wird jedoch weiterhin funktionieren, wenn es mindestens k Teilnehmer, die entweder gerade korrekte Komponenten erhalten haben oder rechtzeitig einen Nachweis über die Unkorrektheit hinterlassen haben.
Nachweise der Korrektheit H_i
Der letzte Punkt, den es zu besprechen gilt, ist, wie man die Korrektheit der veröffentlichten Hi, nämlich dass Hi = p(i)H, ohne Offenlegung p(i).
Erinnern wir uns daran, dass die Werte H, G, p(i)G öffentlich und allen bekannt sind. Der Vorgang der Erhaltung p(i) während man weiß, p(i)G und G wird diskreter Logarithmus oder dlog genannt, und wir wollen beweisen, dass:
dlog(p(i)G, G) = dlog(Hi, H)
ohne Preisgabe p(i). Konstruktionen für solche Nachweise existieren, wie zum Beispiel das.
Mit dieser Konstruktion sendet jeder Teilnehmer zusammen mit Hi einen Nachweis der Korrektheit gemäß der Konstruktion.
Wenn eine Zufallszahl generiert wird, muss sie oft von anderen Teilnehmern verwendet werden, als denen, die sie generiert haben. Solchen Teilnehmern müssen zusammen mit der Zahl alle Hi und zugehörige Nachweise gesendet werden.
Der neugierige Leser könnte fragen: Da die endgültige Zufallszahl – das H0 ist, und p(0)G – öffentliche Informationen sind, warum braucht man dann einen Nachweis für jedes einzelne Hi, warum nicht einfach den Nachweis schicken, dass
dlog(p(0)G, G) = dlog(H.0, H)
Das Problem besteht darin, dass mit dem Schnorr-Protokoll solch ein Nachweis nicht erstellt werden kann, weil niemand den Wert kennt, p(0),der zur Erstellung eines Nachweises erforderlich ist, und noch mehr, der gesamte Zufallszahlengenerator basiert darauf, dass niemand diesen Wert kennt. Daher ist es notwendig, alle Werte Hi und deren individuelle Nachweise zu haben, um die Korrektheit zu beweisen. H0.
Wenn es jedoch eine Operation an Punkten auf elliptischen Kurven gäbe, die semantisch mit der Multiplikation vergleichbar ist, wäre der Nachweis der Korrektheit H0 trivial, wir müssten nur sicherstellen, dass
H0 × G = p(0)G × H
Wenn die ausgewählte Kurve funktioniert solch ein Nachweis. In diesem Fall ist H0 nicht nur die Ausgabe des Zufallszahlengenerators, die jeder Teilnehmer überprüfen kann, der weiß, G, H und p(0)G. H0 ist auch eine Unterschrift auf der Nachricht, die als Seed verwendet wurde, was bestätigt, dass k und n die Teilnehmer diese Nachricht unterzeichnet haben. Somit, wenn seed – es der Hash des Blocks im Blockchain-Protokoll ist, dann H0 ist es gleichzeitig eine Multi-Unterschrift auf dem Block und eine sehr gute Zufallszahl.
Abschließend
Dieser Artikel ist Teil einer Serie technischer Artikel im Blog. . NEAR – ist ein Blockchain-Protokoll und eine Plattform zur Entwicklung dezentraler Anwendungen mit dem Fokus auf einfache Entwicklung und Benutzerfreundlichkeit für Endanwender.
Der Protokollcode ist offen, unsere Implementierung ist in Rust geschrieben, und sie kann gefunden werden .
Sie können sehen, wie die Entwicklung unter NEAR aussieht, und in der Online-IDE experimentieren .
Um alle Nachrichten auf Russisch zu verfolgen, können Sie in der und in , und auf Englisch im offiziellen .
Bis bald!
Quelle: habr.com
