Zufallszahlen und dezentralisierte Netzwerke: praktische Anwendungen

Einführung

„Die Erzeugung von Zufallszahlen ist zu wichtig, um sie dem Zufall zu überlassen“
Robert Cavyu, 1970

Dieser Artikel widmet sich der praktischen Anwendung von Lösungen, die kollektive Zufallszahlengenerierung in unzuverlässigen Umgebungen nutzen. Kurz gesagt – wie und wozu Zufallszahlen in Blockchains verwendet werden, und ein wenig darüber, wie man „gute“ Zufallszahlen von „schlechten“ unterscheidet. Die Erzeugung einer wirklich zufälligen Zahl ist selbst auf einem einzelnen Computer ein äußerst komplexes Problem und wird bereits seit langem von Kryptographen erforscht. In dezentralen Netzwerken ist die Generierung von Zufallszahlen noch komplexer und wichtiger.

Gerade in Netzwerken, in denen die Teilnehmer einander nicht vertrauen, ermöglicht die Fähigkeit, eine unwiderlegbare Zufallszahl zu generieren, die effektive Lösung vieler wichtiger Aufgaben und verbessert bereits bestehende Systeme erheblich. Dabei sind Glücksspiele und Lotterien keineswegs das Hauptziel, wie es anfänglichen Lesern erscheinen mag.

Generierung von Zufallszahlen

Computer können keine Zufallszahlen selbst erzeugen; dazu benötigen sie externe Hilfe. Ein Computer kann einen gewissen Zufallswert erhalten, indem er beispielsweise die Bewegung der Maus, den verwendeten Speicher, parasitäre Ströme an den Kontakten des Prozessors und viele andere Quellen, die als Entropiequellen bezeichnet werden, nutzt. Diese Werte sind nicht völlig zufällig, da sie sich in einem bestimmten Bereich befinden oder vorhersehbare Änderungen aufweisen. Um solche Zahlen in tatsächliche Zufallszahlen innerhalb eines bestimmten Bereichs umzuwandeln, werden kryptographische Transformationen angewendet, um aus ungleichmäßig verteilten Werten der Entropiequelle gleichmäßig verteilte pseudorandomisierte Werte zu erhalten. Die erhaltenen Werte werden als pseudorandomisiert bezeichnet, da sie nicht wirklich zufällig sind, sondern deterministisch aus Entropie erzeugt wurden. Jeder gute Kryptoschlüsselalgorithmen erzeugt beim Verschlüsseln von Daten Chiffretexte, die statistisch nicht von einer zufälligen Sequenz zu unterscheiden sein sollten, sodass zur Erzeugung von Zufallszahlen eine Entropiequelle herangezogen werden kann, die nur eine gute Unvorhersehbarkeit und Wiederholbarkeit der Werte gewährleistet, während der Rest der Arbeit zum Mischen und Verteilen von Bits im Ergebnis vom Verschlüsselungsalgorithmus übernommen wird.

Um das kurze Grundlagenwissen abzuschließen, füge ich hinzu, dass die Generierung von Zufallszahlen, selbst auf einem einzigen Gerät, einer der Grundpfeiler der Sicherheit unserer Daten ist. Die erzeugten pseudorandomisierten Zahlen werden zur Etablierung von sicheren Verbindungen in verschiedenen Netzwerken, zur Generierung von kryptografischen Schlüsseln, zur Lastenverteilung, zur Integritätskontrolle und für viele weitere Anwendungen verwendet. Die Sicherheit vieler Protokolle hängt von der Fähigkeit ab, ein zuverlässiges, von außen unvorhersehbares Zufallswert zu erzeugen, es zu speichern und es bis zum nächsten Schritt des Protokolls nicht offenzulegen, da sonst die Sicherheit gefährdet ist. Ein Angriff auf den Generator von pseudorandomisierten Werten ist äußerst gefährlich und gefährdet sofort alle Software, die die Generierung von Zufallswerten nutzt.

All dies sollten Sie wissen, wenn Sie einen basischen Kurs in Kryptographie besucht haben. Daher machen wir mit dezentralen Netzwerken weiter.

Zufälligkeit in Blockchains

Zunächst werde ich über Blockchains mit Unterstützung für Smart Contracts sprechen, da diese die Möglichkeiten vollständig nutzen können, die durch qualitativ hochwertigen, unumstrittenen Zufall bereitgestellt werden. Um es kurz zu machen, werde ich diese Technologie als “Öffentlich Überprüfbare Zufallsbeacons” oder PVRB bezeichnen. Da Blockchains Netzwerke sind, deren Informationen von jedem Teilnehmer überprüft werden können, ist ein Schlüsselteil des Namens “Öffentlich Überprüfbar”, d.h. jeder, der möchte, kann durch Berechnungen den Beweis erlangen, dass die im Blockchain gespeicherte Zahl solche Eigenschaften hat:

• Das Ergebnis muss eine nachweisbar gleichmäßige Verteilung aufweisen, d.h. es muss auf nachweisbar robuster Kryptografie basieren.
• Es ist unmöglich, irgendein Bit des Ergebnisses zu kontrollieren. Folglich kann das Ergebnis nicht im Voraus vorhergesagt werden.
• Der Protokollgenerator darf nicht durch Nicht-Teilnahme am Protokoll oder durch Überlastung des Netzwerks mit Angreifer-Nachrichten sabotiert werden.
• Alles oben Genannte muss gegenüber Absprachen einer zulässigen Anzahl unredlicher Teilnehmer des Protokolls robust sein (zum Beispiel 1/3 der Teilnehmer).

Jede Möglichkeit einer verschworen Gruppe von Teilnehmern, sogar kontrolliert zufällig gerade/ungerade Zufälle zu erzeugen, ist ein Sicherheitsrisiko. Jede Möglichkeit einer Gruppe, die Ausgabe von Zufall zu stoppen, ist ein Sicherheitsrisiko. Insgesamt gibt es viele Probleme, und diese Aufgabe ist nicht einfach…

Es scheint, dass die wichtigste Anwendung für PVRB verschiedene Spiele, Lotterien und generell jede Form von Glücksspiel auf der Blockchain ist. Tatsächlich ist dies ein wichtiges Gebiet, aber der Zufall in Blockchains hat auch wichtigere Anwendungen. Lassen Sie uns diese betrachten.

Konsens-Algorithmen

PVRB spielt eine enorme Rolle bei der Organisation des Netzwerk-Konsenses. Transaktionen in Blockchains sind durch digitale Signaturen geschützt, daher bedeutet eine "Angriff auf die Transaktion" immer, eine Transaktion in einen Block (oder mehrere Blöcke) einzufügen oder herauszunehmen. Die Hauptaufgabe des Konsens-Algorithmus besteht darin, sich über die Reihenfolge dieser Transaktionen und die Reihenfolge der Blöcke, die diese Transaktionen enthalten, zu verständigen. Ein weiteres notwendiges Merkmal realer Blockchains ist die Finalität – die Fähigkeit des Netzwerks, sich darauf zu einigen, dass die Kette bis zum finalisierten Block endgültig ist und niemals aufgrund eines neuen Forks ausgeschlossen wird. Um zu vereinbaren, dass ein Block gültig und vor allem final ist, müssen Signaturen von der Mehrheit der Blockproduzenten gesammelt werden (im Folgenden BP – Blockproduzenten), was erfordert, dass die Blockkette an alle BPs geliefert und die Signaturen unter allen BPs verbreitet werden. Mit dem Wachstum der Anzahl der BPs wächst die Anzahl der notwendigen Nachrichten im Netzwerk exponentiell, daher funktionieren Konsensalgorithmen, die Finalität erfordern und beispielsweise im pBFT-Konsens von Hyperledger verwendet werden, nicht mit der erforderlichen Geschwindigkeit, beginnend mit nur einigen Dutzend BPs, und erfordern eine enorme Anzahl von Verbindungen.

Wenn im Netzwerk ein unumstrittenes und ehrliches PVRB vorhanden ist, kann man selbst in der einfachsten Annäherung auf dessen Basis einen der Blockproduzenten auswählen und ihn während einer Protokollrunde zum "Leader" ernennen. Wenn wir N Blockproduzenten haben, von denen M: M > 1/2 N ehrlich sind, Transaktionen nicht zensieren und keine Forks der Kette mit dem Ziel eines "Double Spend"-Angriffs erstellen, wird die Nutzung eines gleichmäßig verteilten unumstrittenen PVRB es ermöglichen, einen ehrlichen Leader mit einer Wahrscheinlichkeit von M / N (M / N > 1/2). Wenn jedem einzelnen Validator ein eigener Zeitraum zugewiesen wird, in dem er einen Block erstellen und die Kette validieren kann, und diese Zeiträume gleich sind, wird die Kette von ehrlichen Valideuren länger sein als die von bösartigen Valideuren. Der Konsensalgorithmus, der auf der Kettenlänge basiert, wird einfach die „schlechte“ Kette verwerfen. Dieses Prinzip der gleichmäßigen Zeitverteilung für jeden Validator wurde erstmals in Graphene (dem Vorgänger von EOS) angewendet und ermöglicht es, die meisten Blöcke mit einer einzigen Unterschrift zu schließen, was die Netzwerklast erheblich verringert und es diesem Konsens ermöglicht, extrem schnell und stabil zu arbeiten. Dennoch muss das EOS-Netzwerk derzeit spezielle Blöcke (Last Irreversible Block) verwenden, die mit den Unterschriften von 2/3 der Validierer bestätigt werden. Diese Blöcke dienen der Sicherstellung der Finalität (der Unmöglichkeit, einen Fork der Kette zu erzeugen, der vor dem letzten Last Irreversible Block beginnt).

Außerdem ist das Protokoll in echten Implementierungen komplexer — die Abstimmung über vorgeschlagene Blöcke erfolgt in mehreren Phasen, um den Betrieb des Netzwerks im Falle von versäumten Blöcken und Netzwerkproblemen aufrechtzuerhalten. Selbst unter Berücksichtigung dessen benötigen Konsensalgorithmen, die PVRB verwenden, erheblich weniger Nachrichten zwischen den Validierern, was sie schneller macht als das traditionelle PВFT oder verschiedene seiner Modifikationen.

Das auffälligste Beispiel für solche Algorithmen ist: Ouroboros vom Cardano-Team, das, wie angekündigt, mathematisch nachweisbare Robustheit gegen das Vorhandensein von Absprachen unter den Validierern aufweist.

In Ouroboros wird PVRB verwendet, um den sogenannten „BP-Hochlaufplan“ – einen Zeitplan, der jedem Validator ein Zeitfenster zur Veröffentlichung eines Blocks zuweist – zu bestimmen. Ein großer Vorteil der Verwendung von PVRB ist die vollständige „Gleichheit“ der Validierer (entsprechend der Größen ihrer Konten). Die Integrität von PVRB garantiert, dass bösartige Valideure den Zeitplan der Zeitfenster nicht kontrollieren können und daher die Kette nicht manipulieren können, indem sie Forks im Voraus vorbereiten und analysieren. Es reicht aus, sich einfach auf die Kettenlänge zu verlassen, ohne ausgeklügelte Methoden zur Berechnung des „Nutzens“ der Validierer und des „Gewichts“ ihrer Blöcke anzuwenden.

Insgesamt ist PVRB in fast allen Fällen, in denen in einem dezentralen Netzwerk ein zufälliger Teilnehmer ausgewählt werden muss, die beste Wahl, und nicht eine deterministische Variante, die beispielsweise auf dem Hash eines Blocks basiert. Ohne PVRB führt die Möglichkeit, Einfluss auf die Auswahl des Teilnehmers zu nehmen, zu Angriffen, bei denen der Angreifer, indem er aus mehreren zukünftigen Optionen wählt, den nächsten korrupten Teilnehmer oder mehrere gleichzeitig auswählen kann, um ein größeres Gewicht im Entscheidungsprozess zu gewährleisten. Der Einsatz von PVRB diskreditiert solche Angriffe.

Skalierung und Lastverteilung

PVRB kann auch bei der Reduzierung von Lasten und der Skalierung von Zahlungen erhebliche Vorteile bringen. Zunächst lohnt es sich, sich mit der einem Artikel Rivista “Electronic Lottery Tickets as Micropayments” vertraut zu machen. Die grundlegende Idee ist, dass anstelle von 100 Zahlungen von 1 Cent vom Zahler an den Empfänger eine ehrliche Lotterie mit einem Preis von 1 $ = 100 Cent gespielt werden kann, wobei der Zahler bei jeder Zahlung von 1 Cent der Bank eines von 100 „Lottoscheinen“ überträgt. Einer dieser Scheine gewinnt der Bank 1 $, und genau diesen Schein kann der Empfänger in der Blockchain festhalten. Das Wichtigste ist, dass die anderen 99 Scheine zwischen Empfänger und Zahler ohne äußere Beteiligung über einen privaten Kanal und in beliebiger Geschwindigkeit übertragen werden. Eine gute Beschreibung des Protokolls auf dieser Basis im Emercoin-Netzwerk kann gelesen werden. hier.

Dieses Schema hat einige Probleme, zum Beispiel kann der Empfänger sofort nach Erhalt des Gewinnscheins aufhören, den Zahler zu bedienen, aber für viele spezielle Anwendungen, wie minutenspezifische Abrechnung oder elektronische Abonnements für Dienstleistungen, kann darüber hinweg gesehen werden. Die Hauptanforderung besteht natürlich darin, dass die durchgeführte Lotterie ehrlich ist, und für ihre Durchführung ist PVRB unbedingt erforderlich.

Die Auswahl eines zufälligen Teilnehmers ist auch für die Sharding-Protokolle von entscheidender Bedeutung, deren Ziel es ist, die Blockchain horizontal zu skalieren, sodass verschiedene BPs nur ihren eigenen Anwendungsbereich von Transaktionen verarbeiten können. Dies ist eine äußerst komplexe Aufgabe, insbesondere hinsichtlich der Sicherheit bei der Zusammenführung von Shards. Eine ehrliche Auswahl eines zufälligen BPs, um ihn für einen bestimmten Shard verantwortlich zu machen, ist wie bei den Konsensalgorithmen ebenfalls eine Aufgabe von PVRB. In zentralisierten Systemen werden Shards durch einen Lastverteiler zugewiesen, der einfach den Hash der Anfrage berechnet und ihn an den entsprechenden Ausführer sendet. In Blockchains kann die Möglichkeit, diese Zuweisung zu beeinflussen, zu Angriffen auf den Konsens führen. Zum Beispiel kann der Inhalt der Transaktionen vom Angreifer kontrolliert werden, der steuern kann, welche Transaktionen in den von ihm kontrollierten Shard gelangen, und die Blockchain darin manipulieren kann. Weitere Informationen zu den Problemen der Verwendung von Zufallszahlen für Sharding-Aufgaben in Ethereum können gelesen werden. hier
Sharding ist eine der ambitioniertesten und herausforderndsten Aufgaben im Bereich Blockchain, deren Lösung es ermöglicht, dezentrale Netzwerke mit fantastischer Leistung und Kapazität aufzubauen. PVRB ist lediglich einer der wichtigen Bausteine für ihre Lösung.

Spiele, wirtschaftliche Protokolle, Arbitrage

Die Rolle von Zufallszahlen in der Spieleindustrie ist schwer zu überschätzen. Ihre explizite Nutzung in Online-Casinos und die implizite Berücksichtigung bei der Berechnung der Effekte bestimmter Aktionen eines Spielers sind äußerst komplexe Probleme für dezentralisierte Netzwerke, in denen man sich nicht auf eine zentrale Zufallsquelle verlassen kann. Doch die Zufallsauswahl kann auch viele wirtschaftliche Probleme lösen und dabei helfen, einfachere und effektivere Protokolle zu erstellen. Angenommen, in unserem Protokoll gibt es Streitigkeiten über die Bezahlung einiger günstiger Dienstleistungen, und diese Streitigkeiten treten relativ selten auf. In diesem Fall können Kunden und Verkäufer, wenn ein unbestrittener PVRB vorliegt, eine zufällige Beilegung der Streitigkeiten mit einer vorgegebenen Wahrscheinlichkeit vereinbaren. Zum Beispiel hat der Kunde eine Gewinnchance von 60 % und der Verkäufer von 40 %. Dieser auf den ersten Blick absurde Ansatz ermöglicht eine automatische Lösung von Streitigkeiten mit genau vorhersehbaren Gewinn-/Verlustquoten, die beide Seiten zufriedenstellt, ohne dass eine dritte Partei einbezogen wird und ohne unnötige Zeitverschwendung. Darüber hinaus kann das Verhältnis der Wahrscheinlichkeiten dynamisch sein und von einigen globalen Variablen abhängen. Wenn das Unternehmen beispielsweise gut läuft, eine geringe Anzahl von Streitigkeiten und eine hohe Rentabilität verzeichnet, kann es die Wahrscheinlichkeit der Streitbeilegung zugunsten der Kunden erhöhen, etwa auf 70/30 oder 80/20, und umgekehrt, wenn Streitigkeiten große Mittel kosten und betrügerisch oder unangemessen sind, kann die Wahrscheinlichkeit in die andere Richtung verschoben werden.

Eine Vielzahl interessanter dezentraler Protokolle, wie zum Beispiel token curated registries, Predictive Markets, Bonding Curves und viele andere, stellen ökonomische Spiele dar, die gutes Verhalten belohnen und schlechtes bestrafen. Häufig treten in diesen Protokollen Sicherheitsprobleme auf, deren Schutz sich gegenseitig widerspricht. Was gegen Angriffe von „Walen“ mit Milliarden von Tokens („big stake“) geschützt ist, ist anfällig für Angriffe von Tausenden von Konten mit kleinen Guthaben („sybil stake“). Die Maßnahmen, die gegen einen Angriffsvektor ergriffen werden, wie beispielsweise nichtlineare Gebühren, die dazu entwickelt wurden, das Arbeiten mit großen Stakes unrentabel zu machen, werden in der Regel durch einen anderen Angriff diskreditiert. Da es sich um ein ökonomisches Spiel handelt, können die entsprechenden statistischen Gewichte im Voraus berechnet und die Gebühren einfach durch randomisierte mit dem entsprechenden Verteilung ersetzt werden. Solche probabilistischen Gebühren lassen sich extrem einfach umsetzen, wenn die Blockchain eine zuverlässige Zufallsquelle hat, und erfordern keine komplexen Berechnungen, die sowohl Walen als auch Sybils das Leben erschweren.
Dabei muss man sich weiterhin bewusst sein, dass die Kontrolle über ein einzelnes Bit in diesem Zufallswert betrügerisch beeinflusst werden kann, indem die Wahrscheinlichkeiten verdoppelt oder halbiert werden, sodass ein ehrlicher PVRB eine entscheidende Komponente solcher Protokolle ist.

Wo findet man den richtigen Zufall?

In der Theorie ermöglicht eine ehrliche Zufallsauswahl in dezentralen Netzwerken einen nachweisbaren Schutz fast jedes Protokolls vor Kollusion. Die Begründung ist recht einfach: Wenn das Netzwerk sich auf ein einzelnes Bit von 0 oder 1 einigt und weniger als die Hälfte der Teilnehmer unehrlich ist, dann wird das Netzwerk mit ausreichenden Iterationen mit fester Wahrscheinlichkeit zu einem Konsens über dieses Bit gelangen. Einfach weil der ehrliche Zufall in 51 % der Fälle 51 von 100 Teilnehmern auswählen wird. Aber das ist nur theoretisch, da in realen Netzwerken für ein solches Sicherheitsniveau, wie in den Veröffentlichungen beschrieben, zahlreiche Nachrichten zwischen Hosts, komplexe kryptographische Prozesse und jede Komplikation des Protokolls neue Angriffsvektoren einführt.
Deshalb sehen wir bisher in Blockchains kein nachweislich robustes PVRB, das bereits lange genug genutzt wurde, um sich echten Anwendungen, mehreren Audits, Belastungstests und natürlich realen Angriffen zu bewähren, ohne die es schwerfällt, ein Produkt als wirklich sicher zu bezeichnen.

Dennoch gibt es mehrere vielversprechende Ansätze, die sich in vielen Details unterscheiden, und einer von ihnen wird sicherlich das Problem lösen. Mit heutigen Rechenressourcen kann die kryptographische Theorie recht geschickt in praktische Anwendungen umgesetzt werden. In Zukunft werden wir gerne über die Implementierungen von PVRB berichten: Es gibt derzeit mehrere, jede mit ihrem eigenen Satz wichtiger Eigenschaften und Umsetzungen, und hinter jeder steht eine gute Idee. Nur wenige Teams beschäftigen sich mit Zufallszahlen, und die Erfahrungen jedes einzelnen sind für alle anderen von größter Bedeutung. Wir hoffen, dass unsere Informationen es anderen Teams ermöglichen, schneller voranzukommen, unter Berücksichtigung der Erfahrungen der Vorgänger.

Quelle: habr.com