ersten Teils<\/a><\/noindex> In den Artikeln haben wir besprochen, warum es notwendig sein kann, Zufallszahlen f\u00fcr Teilnehmer zu generieren, die sich nicht gegenseitig vertrauen, welche Anforderungen an solche Zufallszahlengeneratoren gestellt werden und haben zwei Ans\u00e4tze zu ihrer Implementierung betrachtet.<\/p>\nIn diesem Teil des Artikels werden wir einen weiteren Ansatz im Detail untersuchen, der Schwellenunterschriften verwendet.<\/p>\n
Ein wenig Krypto<\/h3>\n 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<\/em>) und Punkte auf einer elliptischen Kurve, die wir mit Gro\u00dfbuchstaben bezeichnen werden.<\/p>\nUm die Grundlagen der Schwellenunterschriften zu verstehen, muss man nicht wissen, wie elliptische Kurven funktionieren, au\u00dfer einige grundlegende Dinge:<\/p>\n
\n\nMan kann Punkte auf einer elliptischen Kurve addieren und mit einem Skalar multiplizieren (die Multiplikation mit einem Skalar werden wir als xG<\/em>bezeichnen, obwohl die Notation Gx<\/em> wird ebenfalls h\u00e4ufig in der Literatur verwendet). Das Ergebnis der Addition und der Multiplikation mit einem Skalar \u2014 ist ein Punkt auf der elliptischen Kurve.<\/p>\n<\/li>\n\nNur mit dem Punkt G<\/em> und seinem Produkt mit dem Skalar xG<\/em> kann man nicht berechnen x<\/em>.<\/p>\n<\/li>\n<\/ol>\nWir werden auch das Konzept eines Polynoms verwenden p(x)<\/em> der Ordnung k<\/em>-1. Insbesondere werden wir die folgende Eigenschaft von Polynomen verwenden: Wenn wir den Wert p(x) <\/em>f\u00fcr beliebige k <\/em>unterschiedliche x <\/em>(und keine weiteren Informationen \u00fcber p(x)<\/em>) haben, k\u00f6nnen wir p(x) <\/em>f\u00fcr jeden anderen berechnen x<\/em>.<\/p>\nEs ist interessant, dass man f\u00fcr jedes Polynom p(x)<\/em> und einen bestimmten Punkt auf der Kurve G<\/em>, wobei man den Wert p(x)G<\/em> f\u00fcr beliebige k<\/em> verschiedener Werte x<\/em>, auch berechnen kann p(x)G<\/em> f\u00fcr jedes x<\/em>.<\/p>\nDiese Informationen sind ausreichend, um in die Details zu gehen, wie Schwellenunterschriften funktionieren und wie sie zur Generierung von Zufallszahlen verwendet werden k\u00f6nnen.<\/p>\n
Zufallszahlengenerator auf Schwellenunterschriften<\/h3>\n Nehmen wir an, dass n<\/em> Teilnehmer ein Zufallszahl generieren wollen, und wir m\u00f6chten, dass die Teilnahme von beliebigen k<\/em> von ihnen ausreicht, um die Zahl zu generieren, aber dass Angreifer, die kontrollieren k<\/em>-1 oder weniger Teilnehmer, die generierte Zahl nicht vorhersagen oder beeinflussen k\u00f6nnen.<\/p>\n
Nehmen wir an, es gibt ein solches Polynom p(x)<\/em> der Ordnung k<\/em>-1, dass der erste Teilnehmer wei\u00df p(1)<\/em>, der zweite wei\u00df p(2), <\/em>und so weiter (n<\/em>-ter wei\u00df p(n)<\/em>). Angenommen, dass f\u00fcr einen bestimmten vorab definierten Punkt G<\/em> alle wissen p(x)G <\/em>f\u00fcr alle Werte x<\/em>. Wir werden es nennen p(i)<\/em> \u201eprivate Komponente\u201c i<\/em>-es Teilnehmers (weil nur i<\/em>-er Teilnehmer sie kennt), und p(i)G<\/em> \u201e\u00f6ffentliche Komponente\u201c i<\/em>-es Teilnehmers (weil alle Teilnehmer sie kennen). Wie Sie sich erinnern, reicht das Wissen p(i)G <\/em>nicht aus, um zu rekonstruieren p(i).<\/em><\/p>\nDie Erstellung eines solchen Polynoms, sodass nur i-<\/em>-er Teilnehmer und niemand sonst seine private Komponente kennt \u2013 ist der schwierigste und interessanteste Teil des Protokolls, das wir unten erl\u00e4utern werden. Angenommen, wir haben ein solches Polynom, und alle Teilnehmer kennen ihre privaten Komponenten.<\/p>\nWie k\u00f6nnen wir ein solches Polynom nutzen, um eine Zufallszahl zu generieren? Zun\u00e4chst ben\u00f6tigen wir eine bestimmte Zeichenkette, die zuvor nicht als Eingabe f\u00fcr den Generator verwendet wurde. Im Fall von Blockchain ist der Hash des letzten Blocks h<\/em> \u2014 ein guter Kandidat f\u00fcr eine solche Zeichenfolge. Lassen Sie die Teilnehmer eine Zufallszahl erzeugen mit h <\/em>als Seed verwenden. Zuerst konvertieren die Teilnehmer h<\/em> in einen Punkt auf der Kurve unter Verwendung einer beliebigen vordefinierten Funktion:<\/p>\nH = scalarToPoint(h)<\/em><\/p>\nDann berechnet jeder Teilnehmer i<\/em> und ver\u00f6ffentlicht Hi = p(i)H, <\/em>was sie tun k\u00f6nnen, weil sie wissen, p(i) und H. <\/em>Die Offenlegung H<\/em>i erlaubt es den anderen Teilnehmern nicht, die private Komponente i<\/em>-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\u00fchrt werden.<\/p>\nWenn k<\/em> Nach der Offenlegung Hi = p(i)H, <\/em>k\u00f6nnen alle berechnen H<\/em>x = p(x)H<\/em> f\u00fcr alle x<\/em> aufgrund der Eigenschaften von Polynomen, die wir im vorherigen Abschnitt besprochen haben. In diesem Moment berechnen alle Teilnehmer H0 = p(0)H, <\/em>und das ist die resultierende Zufallszahl. Beachten Sie, dass niemand wei\u00df p(0), <\/em>und daher ist der einzige Weg, p(0)H zu berechnen \u2013 <\/em>die Interpolation p(x)H, <\/em>was nur m\u00f6glich ist, wenn k <\/em>die Werte p(i)H <\/em>bekannt sind. Die Offenlegung einer geringeren Anzahl verursacht p(i)H <\/em>keine Informationen \u00fcber p(0)H.<\/em><\/p>\n
Der obige Generator hat alle Eigenschaften, die wir wollen: Angreifer, die nur k-<\/em>-1 Teilnehmer oder weniger kontrollieren, haben keine Informationen und keinen Einfluss auf die Ausgabe, w\u00e4hrend beliebige k<\/em> Teilnehmer die resultierende Zahl berechnen k\u00f6nnen, und jede Teilmenge aus k<\/em> Teilnehmern kommt immer zu demselben Ergebnis f\u00fcr denselben Seed.<\/p>\nEs gibt ein Problem, das wir oben umgangen haben. Damit die Interpolation funktioniert, ist es wichtig, dass der Wert H<\/em>i, den jeder Teilnehmer ver\u00f6ffentlicht hat, i<\/em> tats\u00e4chlich gleich ist p(i)H.<\/em> Da niemand au\u00dfer dem i<\/em>-ten Teilnehmer wei\u00df, p(i), <\/em>kann niemand au\u00dfer i-<\/em>dem -ten Teilnehmer \u00fcberpr\u00fcfen, ob Hi <\/em>tats\u00e4chlich korrekt berechnet wurde und ohne einen kryptografischen Nachweis der Korrektheit H<\/em>kann ein Angreifer jeden Wert als Hallo, <\/em>ver\u00f6ffentlichen und willk\u00fcrlich die Ausgabe des Zufallszahlengenerators beeinflussen.:<\/em><\/p>\n
Es gibt mindestens zwei M\u00f6glichkeiten, die Korrektheit von H<\/em>i zu beweisen. Wir werden diese betrachten, nachdem wir die Polynom-Generierung behandelt haben.<\/p>\nPolynom-Generierung<\/h3>\n Im vorherigen Abschnitt haben wir angenommen, dass wir ein solches Polynom haben, p(x)<\/em> der Ordnung k<\/em>-1, sodass der Teilnehmer i<\/em> wei\u00df p(i)<\/em>, und niemand sonst hat irgendwelche Informationen \u00fcber diesen Wert. Im n\u00e4chsten Abschnitt m\u00fcssen wir auch sicherstellen, dass f\u00fcr einen bestimmten vordefinierten Punkt G<\/em> alle wissen, p(x)G <\/em>f\u00fcr alle x<\/em>.<\/p>\nIn diesem Abschnitt gehen wir davon aus, dass jeder Teilnehmer lokal einen privaten Schl\u00fcssel xi, <\/em>hat, sodass der entsprechende \u00f6ffentliche Schl\u00fcssel X<\/em>i f\u00fcr alle bekannt ist.<\/p>\nEin m\u00f6glicher Protokoll zur Generierung des Polynoms ist folgender:<\/p>\n
\n\nJeder Teilnehmer i<\/em> erzeugt lokal ein beliebiges Polynom pi(x) der Ordnung k-1. <\/em>Sie senden dann an jeden Teilnehmer j <\/em>system-id D p<\/em>i(j), verschl\u00fcsselt mit dem \u00f6ffentlichen Schl\u00fcssel Xj. <\/em>So wei\u00df nur der i-<\/em>-te <\/em>und j-te<\/em>-te <\/em>Teilnehmer, p<\/em>i(j). Der Teilnehmer i<\/em> k\u00fcndigt auch \u00f6ffentlich an pi(j)G <\/em>f\u00fcr alle j <\/em>ab 1 <\/em>bis k <\/em>einschlie\u00dflich.<\/p>\n<\/li>\n\nAlle Teilnehmer nutzen einen Konsens, um die k <\/em>Teilnehmer auszuw\u00e4hlen, deren Polynome verwendet werden. Da einige Teilnehmer offline sein k\u00f6nnten, k\u00f6nnen wir nicht warten, bis alle n <\/em>Teilnehmer ihre Polynome ver\u00f6ffentlicht haben. Das Ergebnis dieses Schrittes ist eine Menge <\/em>Z<\/em><\/strong> <\/em>die aus mindestens k <\/em>Polynomen besteht, die in Schritt (1) erstellt wurden..<\/em><\/p>\n<\/li>\n\nDie Teilnehmer stellen sicher, dass die ihnen bekannten Werte p<\/em>i(j) den \u00f6ffentlich angek\u00fcndigten pi(j)G entsprechen. <\/em>Nach diesem Schritt sollten nur noch die Polynome \u00fcbrig bleiben, f\u00fcr die privat \u00fcbermittelte <\/em>Z <\/em><\/strong>ihre private Komponente p<\/em>i(j) den \u00f6ffentlich angek\u00fcndigten pi(j)G entsprechen.<\/em><\/p>\n<\/li>\n\nJeder Teilnehmer j <\/em>p(j) als Summe <\/em>i(j) f\u00fcr alle p<\/em>. Jeder Teilnehmer berechnet auch alle Werte i<\/em> in Z<\/em><\/strong>pi(x)G f\u00fcr alle i. p(x)G <\/em>i(j) f\u00fcr alle p(x) \u2013 <\/em>in <\/em>Z<\/em><\/strong>.<\/em><\/p>\n<\/li>\n<\/ol>\n
Beachten Sie, dass ist tats\u00e4chlich ein Polynom der Ordnung <\/em>k-1, da es sich um die Summe einzelner <\/em>i(x) handelt, von denen jede ein Polynom der Ordnung p<\/em>ist. k<\/em>-1. Dann beachten Sie, dass w\u00e4hrend jeder Teilnehmer j<\/em> wei\u00df p(j), <\/em>sie keine Informationen \u00fcber p(x)<\/em> f\u00fcr x \u2260 j<\/em>. Tats\u00e4chlich m\u00fcssen sie, um diesen Wert zu berechnen, alle pi(x), <\/em>und solange der Teilnehmer j <\/em>nicht mindestens eines der gew\u00e4hlten Polynome kennt, haben sie keine ausreichenden Informationen \u00fcber p(x).<\/em><\/p>\nDas 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.<\/p>\n
Insbesondere m\u00fcssen wir in der Lage sein zu beweisen, dass die verschl\u00fcsselten p<\/em>i(j) tats\u00e4chlich den ver\u00f6ffentlichten entsprechen. pi(j)G entsprechen. <\/em>Wenn wir das nicht beweisen k\u00f6nnen, k\u00f6nnte ein Angreifer i <\/em>m\u00fcll anstelle von p<\/em>i(j) an den Teilnehmer senden, j<\/em>und der Teilnehmer j <\/em>wird den tats\u00e4chlichen Wert nicht erhalten pi(j), <\/em>und wird seine private Komponente nicht berechnen k\u00f6nnen..<\/em><\/p>\nEs gibt ein kryptografisches Protokoll, das es erm\u00f6glicht, eine zus\u00e4tzliche Nachricht zu erstellen, proof<\/em>i(j), so dass jeder Teilnehmer, der einen bestimmten Wert hat, e, <\/em>und auch proofi(j) <\/em>und p<\/em>i(j)G, kann lokal \u00fcberpr\u00fcfen, dass e<\/em> \u2013 es tats\u00e4chlich pi(j), <\/em>mit dem Schl\u00fcssel des Teilnehmers j verschl\u00fcsselt ist. <\/em>Leider ist die Gr\u00f6\u00dfe eines solchen Beweises unglaublich gro\u00df, und angesichts der Tatsache, dass es notwendig ist, O(nk) <\/em>solcher Beweise zu ver\u00f6ffentlichen, k\u00f6nnen sie nicht zu diesem Zweck verwendet werden.<\/p>\nAnstatt zu beweisen, dass pi(j) <\/em>entspricht p<\/em>i(j)G, k\u00f6nnen wir im Protokoll zur Erzeugung des Polynoms einen sehr langen Zeitraum einplanen, w\u00e4hrenddessen alle Teilnehmer die erhaltenen verschl\u00fcsselten \u00fcberpr\u00fcfen, pi(j), <\/em>und wenn die entschl\u00fcsselte Nachricht nicht mit der \u00f6ffentlichen p<\/em>i(j)G \u00fcbereinstimmt, ver\u00f6ffentlichen sie einen kryptografischen Beweis daf\u00fcr, dass die erhaltene verschl\u00fcsselte Nachricht falsch ist. Zu beweisen, dass die Nachricht nicht <\/em>entspricht pi(G)<\/em> ist viel einfacher, als zu beweisen, dass sie \u00fcbereinstimmt. Es sollte angemerkt werden, dass dies erfordert, dass jeder Teilnehmer mindestens einmal im Netzwerk erscheint, w\u00e4hrend der Zeit, die f\u00fcr die Erstellung solcher Beweise vorgesehen ist, und beruht auf der Annahme, dass, wenn sie einen solchen Beweis ver\u00f6ffentlicht haben, er alle anderen Teilnehmer in dieser Zeit erreicht.<\/p>\n
Wenn ein Teilnehmer in diesem Zeitraum nicht im Netzwerk erscheint und er tats\u00e4chlich 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<\/em> Teilnehmer, die entweder gerade korrekte Komponenten erhalten haben oder rechtzeitig einen Nachweis \u00fcber die Unkorrektheit hinterlassen haben.<\/p>\nNachweise der Korrektheit H_i<\/h3>\n Der letzte Punkt, den es zu besprechen gilt, ist, wie man die Korrektheit der ver\u00f6ffentlichten H<\/em>i, n\u00e4mlich dass Hi = p(i)H, <\/em>ohne Offenlegung p(i).<\/em><\/p>\nErinnern wir uns daran, dass die Werte H, G, p(i)G <\/em>\u00f6ffentlich und allen bekannt sind. <\/em>Der Vorgang der Erhaltung p(i) <\/em>w\u00e4hrend man wei\u00df, p(i)G <\/em>und G <\/em>wird diskreter Logarithmus oder dlog genannt, <\/em>und wir wollen beweisen, dass:<\/p>\ndlog(p(i)G, G) = dlog(H<\/em>i, H<\/em>)<\/p>\nohne Preisgabe p(i)<\/em>. Konstruktionen f\u00fcr solche Nachweise existieren, wie zum Beispiel das Schnorr-Protokoll.<\/u><\/a><\/noindex>.<\/p>\n Mit dieser Konstruktion sendet jeder Teilnehmer zusammen mit Hi <\/em>einen Nachweis der Korrektheit gem\u00e4\u00df der Konstruktion.<\/p>\nWenn eine Zufallszahl generiert wird, muss sie oft von anderen Teilnehmern verwendet werden, als denen, die sie generiert haben. Solchen Teilnehmern m\u00fcssen zusammen mit der Zahl alle Hi<\/em> und zugeh\u00f6rige Nachweise gesendet werden.<\/p>\nDer neugierige Leser k\u00f6nnte fragen: Da die endg\u00fcltige Zufallszahl \u2013 das H<\/em>0 ist, und p(0)G \u2013 <\/em>\u00f6ffentliche Informationen sind, warum braucht man dann einen Nachweis f\u00fcr jedes einzelne H<\/em>i, warum nicht einfach den Nachweis schicken, dass<\/p>\ndlog(p(0)G, G) = dlog(H.<\/em>0, H<\/em>)<\/p>\nDas Problem besteht darin, dass mit dem Schnorr-Protokoll solch ein Nachweis nicht erstellt werden kann, weil niemand den Wert kennt, p(0),<\/em>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 <\/em>und deren individuelle Nachweise zu haben, um die Korrektheit zu beweisen. H<\/em>0.<\/p>\nWenn es jedoch eine Operation an Punkten auf elliptischen Kurven g\u00e4be, die semantisch mit der Multiplikation vergleichbar ist, w\u00e4re der Nachweis der Korrektheit H0 <\/em>trivial, wir m\u00fcssten nur sicherstellen, dass<\/p>\nH<\/em>0 \u00d7 G<\/em> = p(0)G \u00d7 H<\/em><\/p>\nWenn die ausgew\u00e4hlte Kurve elliptische Kurvenpaarungen unterst\u00fctzt,<\/u><\/a><\/noindex>funktioniert solch ein Nachweis. In diesem Fall ist H<\/em>0 nicht nur die Ausgabe des Zufallszahlengenerators, die jeder Teilnehmer \u00fcberpr\u00fcfen kann, der wei\u00df, G, H<\/em> und p(0)G. H<\/em>0 ist auch eine Unterschrift auf der Nachricht, die als Seed verwendet wurde, was best\u00e4tigt, dass k<\/em> und n <\/em>die Teilnehmer diese Nachricht unterzeichnet haben. Somit, wenn seed \u2013 <\/em>es der Hash des Blocks im Blockchain-Protokoll ist, dann H0<\/em> ist es gleichzeitig eine Multi-Unterschrift auf dem Block und eine sehr gute Zufallszahl.<\/p>\nAbschlie\u00dfend<\/h4>\n Dieser Artikel ist Teil einer Serie technischer Artikel im Blog. NEAR<\/a><\/noindex>. NEAR \u2013 ist ein Blockchain-Protokoll und eine Plattform zur Entwicklung dezentraler Anwendungen mit dem Fokus auf einfache Entwicklung und Benutzerfreundlichkeit f\u00fcr Endanwender.<\/p>\nDer Protokollcode ist offen, unsere Implementierung ist in Rust geschrieben, und sie kann gefunden werden
![\"Kann](\"\/wp-content\/uploads\/2020\/10\/fc42fe5e99ce4412a0ce99eb63629a42.png\")
<\/p>\n