Zufallszahlen und dezentrale Netzwerke: praktische Anwendungen

Einführung

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

Dieser Artikel widmet sich der praktischen Anwendung von Lösungen, die kollektive Zufallszahlengenerierung in einer nicht vertrauenswürdigen Umgebung nutzen. Kurz gesagt: Wie und warum wird Zufall in Blockchains verwendet, und ein bisschen darüber, wie man „guten“ Zufall von „schlechtem“ unterscheidet. Die Generierung einer tatsächlich zufälligen Zahl ist ein äußerst komplexes Problem, selbst auf einem einzelnen Computer, das schon lange von Kryptographen untersucht wird. In dezentralen Netzwerken ist die Generierung von Zufallszahlen jedoch noch schwieriger und wichtiger.

In Netzwerken, in denen die Teilnehmer einander nicht vertrauen, ermöglicht die Fähigkeit, eine unwiderlegbare Zufallszahl zu generieren, die effektive Lösung zahlreicher wichtiger Aufgaben und verbessert erheblich bereits bestehende Systeme. Dabei sind Glücksspiel und Lotterien keineswegs das Hauptziel, wie es ungeübten Lesern zunächst erscheinen mag.

Zufallszahlengenerierung

Computer sind nicht in der Lage, selbst zufällige Zahlen zu erzeugen; dafür benötigen sie externe Hilfe. Ein Computer kann beispielsweise einige zufällige Werte erhalten, indem er die Bewegungen der Maus, die Menge des verwendeten Speichers, parasitäre Ströme an den Kontakten des Prozessors und viele andere Quellen nutzt, die als Entropiequellen bezeichnet werden. Diese Werte sind nicht ganz zufällig, da sie innerhalb eines bestimmten Bereichs liegen oder vorhersehbare Veränderungsmuster haben. Um solche Zahlen in tatsächlich zufällige Werte innerhalb eines definierten Bereichs umzuwandeln, werden kryptographische Transformationen angewendet, um aus den ungleichmäßig verteilten Werten der Entropiequellen gleichmäßig verteilte pseudorandomisierte Werte zu gewinnen. Diese Werte werden als pseudorandomisiert bezeichnet, da sie nicht wirklich zufällig sind, sondern deterministisch aus der Entropie erzeugt werden. Ein guter KryptAlgorithmus erzeugt beim Verschlüsseln von Daten Chiffretexte, die statistisch von echten Zufallsfolgen nicht zu unterscheiden sind. Daher kann eine Entropiequelle verwendet werden, die lediglich eine gute Wiederholbarkeit und Unvorhersehbarkeit der Werte in kleinen Bereichen bietet, während der Rest der Arbeit zur Verteilung und Mischen der Bits im Resultat vom Verschlüsselungsalgorithmus übernommen wird.

Um den kurzen Überblick abzuschließen, möchte ich hinzufügen, dass die Generierung von Zufallszahlen, selbst auf einem einzigen Gerät, eine der Säulen für die Sicherheit unserer Daten ist. Die erzeugten pseudorandomisierten Zahlen werden zur Einrichtung sicherer Verbindungen in verschiedenen Netzwerken, zur Generierung kryptografischer Schlüssel, zum Lastenausgleich, zur Integritätskontrolle und für viele weitere Anwendungen verwendet. Die Sicherheit vieler Protokolle hängt davon ab, zuverlässige, von außen unvorhersehbare Zufallszahlen zu generieren, sie zu speichern und sie bis zum nächsten Schritt des Protokolls nicht offenzulegen, da ansonsten die Sicherheit gefährdet wäre. Ein Angriff auf den Generator pseudorandomisierter Werte ist äußerst gefährlich und gefährdet sofort alle Software, die auf die Generierung von Zufallszahlen angewiesen ist.

All dies müssen Sie wissen, wenn Sie einen Grundkurs in Kryptografie absolviert haben, also fahren wir fort mit dezentralisierten Netzwerken.

Zufallszahlen in Blockchains

Zuerst werde ich über Blockchains sprechen, die Smart Contracts unterstützen, denn diese können die Möglichkeiten voll ausschöpfen, die durch qualitativ hochwertigen, unbestreitbaren Zufall bereitgestellt werden. Im Folgenden werde ich diese Technologie kurz als “Öffentlich Überprüfbare Zufallsbeacons” oder PVRB bezeichnen. Da Blockchains Netzwerke sind, in denen die Informationen von jedem Teilnehmer überprüft werden können, ist ein zentraler Bestandteil des Namens “Öffentlich Überprüfbar”, d.h. jeder Interessierte kann durch Berechnungen den Nachweis erbringen, dass die im Blockchain gespeicherte Zahl folgende Eigenschaften hat:

• Das Ergebnis muss nachweislich gleichmäßig verteilt sein, d.h. es basiert auf nachweislich sicherer Kryptografie.
• Keiner der Bits des Ergebnisses kann kontrolliert werden. Folglich kann das Ergebnis nicht im Voraus vorhergesagt werden.
• Der Protokoll zur Generierung kann nicht durch Nicht-Teilnahme oder durch Überlastung des Netzwerks mit Angriffsnachrichten sabotiert werden.
• All das oben Genannte muss widerstandsfähig gegen Kollusionen einer zulässigen Anzahl unehrlicher Teilnehmer im Protokoll sein (z. B. 1/3 der Teilnehmer).

Jede Möglichkeit einer kooperierenden Minderheit von Teilnehmern, sogar kontrollierte gerade / ungerade Zufallszahlen zu erzeugen, stellt ein Sicherheitsrisiko dar. Jede Möglichkeit dieser Gruppe, die Zufallszahlenvergabe zu stoppen, ist ebenfalls ein Sicherheitsproblem. Insgesamt gibt es viele Herausforderungen, und diese Aufgabe ist nicht einfach…

Es scheint, dass die wichtigste Anwendung für PVRB in verschiedenen Spielen, Lotterien und im Allgemeinen in allen Arten von Gambling auf der Blockchain zu finden ist. Tatsächlich ist das ein wichtiger Bereich, aber Zufallsgeneratoren in Blockchains haben auch bedeutendere Anwendungen. Lassen Sie uns diese näher betrachten.

Konsensalgorithmen

Die PVRB für die Organisation des Netzwerk-Konsenses spielt eine enorme Rolle. Transaktionen in Blockchains sind durch digitale Signaturen geschützt, weshalb eine "Transaktionsattacke" stets das Einfügen oder Entfernen einer Transaktion in einem Block (oder in mehreren Blöcken) bedeutet. Die Hauptaufgabe des Konsensalgorithmus besteht darin, sich über die Reihenfolge dieser Transaktionen und die Reihenfolge der Blöcke, die diese Transaktionen enthalten, zu einigen. Ein notwendiges Merkmal für echte 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 durch das Auftauchen eines neuen Forks ausgeschlossen wird. Um sich darauf zu einigen, dass ein Block gültig und vor allem final ist, ist es erforderlich, die Signaturen von der Mehrheit der Blockproduzenten (BP – Blockproduzenten) zu sammeln, was mindestens die Zustellung der Blockkette an alle BPs erfordert und die Verbreitung der Signaturen zwischen allen BPs. Mit zunehmender Anzahl von BPs wächst die Anzahl der erforderlichen Nachrichten im Netzwerk exponentiell, wodurch Konsensalgorithmen, die Finalität erfordern, wie zum Beispiel der pBFT-Konsens von Hyperledger, nicht mit der notwendigen Geschwindigkeit arbeiten können, bereits ab einigen Dutzend BPs und dabei eine riesige Anzahl von Verbindungen benötigen.

Wenn es ein unbestreitbares und faires PVRB im Netzwerk gibt, kann man selbst in der einfachsten Annäherung auf dessen Grundlage einen der Blockproduzenten auswählen und ihn während einer Runde des Protokolls als „Leiter“ einsetzen. Wenn wir N Blockproduzenten haben, von denen M: M > 1/2 N ehrlich sind, Transaktionen nicht zensieren und keine Forks der Kette bauen, um einen „Double Spend“-Angriff durchzuführen, ermöglicht die Nutzung eines gleichmäßig verteilten unbestreitbaren PVRB die Auswahl eines ehrlichen Leiters mit einer Wahrscheinlichkeit von M / N (M / N > 1/2). Wenn jedem Blockproduzenten ein spezifisches Zeitfenster zugewiesen wird, innerhalb dessen er einen Block erstellen und die Kette validieren kann, und diese Zeitfenster gleichmäßig verteilt sind, dann wird die Kette von ehrlichen Blockproduzenten länger sein als die von bösartigen Blockproduzenten. Ein Konsensalgorithmus, der auf der Kettenlänge basiert, wird einfach die „schlechte“ Kette verwerfen. Dieses Prinzip, jedem Blockproduzenten gleiche Zeitintervalle zuzuteilen, wurde erstmals in Graphene (dem Vorläufer von EOS) angewendet und ermöglicht es, die Mehrheit der Blöcke mit einer einzigen Signatur abzuschließen. Dies verringert die Netzwerkbelastung erheblich und ermöglicht einen extrem schnellen und stabilen Konsens. Dennoch muss das EOS-Netzwerk derzeit spezielle Blöcke (Last Irreversible Block) verwenden, die durch die Signaturen von 2/3 der Blockproduzenten bestätigt werden. Diese Blöcke dienen dazu, die Endgültigkeit zu gewährleisten (d.h. die Unmöglichkeit, dass ein Fork vorkommt, der vor dem letzten Last Irreversible Block beginnt).

In der Praxis ist das Protokollschema komplexer – Abstimmungen über die vorgeschlagenen Blöcke erfolgen in mehreren Phasen, um den Netzwerkbetrieb bei Blockausfällen und Netzwerkproblemen aufrechtzuerhalten. Selbst unter Berücksichtigung dieser Aspekte erfordern Konsensalgorithmen mit PVRB wesentlich weniger Nachrichten zwischen den BP, was sie schneller macht als das traditionelle PВFT oder dessen verschiedene Modifikationen.

Ein herausragendes Beispiel für solche Algorithmen ist: Ouroboros vom Team von Cardano, das, wie angekündigt, mathematisch bewiesene Widerstandsfähigkeit gegenüber Absprachen unter BP aufweist.

Im Ouroboros PVRB wird das sogenannte "BP-Schedule" verwendet – ein Zeitplan, der jedem BP einen eigenen Zeitfenster für die Veröffentlichung eines Blocks zuweist. Ein großer Vorteil der Verwendung von PVRB ist die vollständige "Gleichheit" der BPs (basierend auf der Größe ihrer Salden). Die Fairness von PVRB gewährleistet, dass böswillige BPs nicht das Zeitfenster kontrollieren können und somit nicht in der Lage sind, die Blockchain zu manipulieren, indem sie Forks im Voraus vorbereiten und analysieren. Um einen Fork auszuwählen, reicht es aus, sich einfach auf die Länge der Kette zu stützen, anstatt ausgeklügelte Methoden zur Berechnung der "Nützlichkeit" der BPs und des "Gewichts" ihrer Blöcke zu verwenden.

In allen Fällen, in denen ein zufälliger Teilnehmer in einem dezentralen Netzwerk ausgewählt werden muss, ist fast immer PVRB die beste Wahl, nicht eine deterministische Option, wie etwa ein Block-Hash. Ohne PVRB besteht die Möglichkeit, die Auswahl des Teilnehmers zu beeinflussen, was zu Angriffen führen kann, bei denen der Angreifer aus mehreren zukünftigen Optionen wählt, um den nächsten korrumpierten Teilnehmer oder sogar mehrere auszuwählen, um eine größere Stimme im Entscheidungsprozess zu sichern. Der Einsatz von PVRB entwertet diese Arten von Angriffen.

Skalierung und Lastverteilung

PVRB kann auch erhebliche Vorteile bei Aufgaben zur Lastverringerung und Skalierung von Zahlungen bieten. Zunächst ist es sinnvoll, sich mit Artikel. Der RIVESTA „Elektronische Lotterietickets als Mikropayments“. Die grundlegende Idee ist, dass anstelle von 100 Zahlungen von 1 Cent vom Zahler an den Empfänger, man an einer fairen Lotterie teilnehmen kann mit einem Preis von 1 $ = 100 Cent, wobei der Zahler bei jeder Zahlung von 1 Cent der Bank eines von 100 seiner „Lotterietickets“ überträgt. Eines dieser Tickets gewinnt der Bank 1 $, und genau dieses Ticket kann der Empfänger in der Blockchain festhalten. Das Wichtigste ist, dass die restlichen 99 Tickets zwischen dem Empfänger und dem Zahler ohne jegliche externe Beteiligung, über einen privaten Kanal und in beliebiger Geschwindigkeit übertragen werden. Eine gute Beschreibung des Protokolls auf Basis dieses Schemas im Emercoin-Netzwerk kann gelesen werden. hier.

Diese Lösung hat mehrere Probleme, zum Beispiel könnte der Empfänger den Zahler sofort nach Erhalt des Gewinnertickets nicht mehr bedienen. Für viele spezielle Anwendungen, wie minutengenaue Abrechnung oder elektronische Abonnements für Dienste, können diese jedoch ignoriert werden. Das Hauptkriterium ist natürlich die Fairness der durchgeführten Lotterie, und dafür ist ein PVRB unbedingt notwendig.

Die Auswahl eines zufälligen Teilnehmers ist auch für Sharding-Protokolle von entscheidender Bedeutung, deren Ziel es ist, die Blockchain horizontal zu skalieren. Dabei kann jeder BP nur seinen bestimmten Transaktionsbereich verarbeiten. Dies ist eine äußerst komplexe Aufgabe, insbesondere in Bezug auf die Sicherheit bei der Zusammenführung von Shards. Eine faire Auswahl eines zufälligen BP, um ihn für einen bestimmten Shard verantwortlich zu machen, ist ebenso eine Herausforderung wie bei Konsensalgorithmen – auch dies ist eine PVRB-Aufgabe. In zentralisierten Systemen werden Shards von einem Lastenausgleichsmechanismus zugewiesen, der einfach einen Hash vom Anfrage berechnet und an den entsprechenden Ausführer sendet. In Blockchains kann die Möglichkeit, auf diese Zuweisung Einfluss zu nehmen, zu einem Angriff auf den Konsens führen. Beispielsweise kann der Angreifer den Inhalt der Transaktionen kontrollieren und bestimmen, welche Transaktionen in den von ihm kontrollierten Shard gelangt und die Blockchain darin manipuliert werden. Die Diskussion über die Problematik der Verwendung von Zufallszahlen für Sharding-Aufgaben in Ethereum kann man weiterlesen. hier
Sharding ist eine der ambitioniertesten und anspruchsvollsten Herausforderungen im Bereich Blockchain. Ihre Lösung ermöglicht den Aufbau von dezentralen Netzwerken mit fantastischer Leistung und Kapazität. PVRB ist nur ein wichtiger Baustein für diese Lösung.

Spiele, wirtschaftliche Protokolle, Arbitrage

Die Rolle von Zufallszahlen in der Spieleindustrie ist enorm. Ihr offensichtlicher Einsatz in Online-Casinos sowie ihr impliziter Einfluss auf die Berechnung der Auswirkungen bestimmter Spielaktionen stellen komplexe Herausforderungen für dezentralisierte Netzwerke dar, in denen es keinen zentralen Zufallsquelle gibt. Zufällige Auswahlen können jedoch auch viele wirtschaftliche Probleme lösen und dabei helfen, einfachere und effektivere Protokolle zu erstellen. Angenommen, unser Protokoll sieht Streitigkeiten über die Bezahlung von kostengünstigen Dienstleistungen vor, und diese Streitigkeiten treten recht selten auf. In diesem Fall, wenn es einen unwiderlegbaren PVRB gibt, können Kunden und Verkäufer eine zufällige Lösung der Streitigkeiten vereinbaren, jedoch mit einer bestimmten Wahrscheinlichkeit. Zum Beispiel hat der Kunde eine 60%ige Gewinnchance, der Verkäufer 40%. Dieser auf den ersten Blick absurde Ansatz ermöglicht es, Streitigkeiten automatisch mit einer genau vorhersagbaren Gewinn- und Verlustquote zu lösen, die beide Parteien zufriedenstellt, ohne dass eine dritte Partei eingreifen muss und ohne Zeitverschwendung. Darüber hinaus kann das Verhältnis der Wahrscheinlichkeiten dynamisch sein und von bestimmten globalen Variablen abhängen. Wenn ein Unternehmen beispielsweise gut läuft, wenige Streitigkeiten und hohe Einnahmen verzeichnet, kann es die Wahrscheinlichkeit der streitigen Lösung zugunsten der Kunden erhöhen, zum Beispiel auf 70/30 oder 80/20. Umgekehrt, wenn Streitigkeiten erhebliche Kosten verursachen und betrügerisch oder unangemessen sind, kann die Wahrscheinlichkeit in die andere Richtung verschoben werden.

Eine Vielzahl interessanter dezentraler Protokolle, wie tokenkuratierte Register, Prognosemärkte, Bonding-Kurven und viele andere, stellen wirtschaftliche Spiele dar, in denen gutes Verhalten belohnt und schlechtes bestraft wird. Häufig treten Sicherheitsprobleme auf, deren Abwehr sich gegenseitig widerspricht. Was vor Angriffen von „Walen“ mit Milliarden von Tokens („big stake“) geschützt ist, ist anfällig für Angriffe von Tausenden von Konten mit kleinen Salden („sybil stake“). Die Maßnahmen gegen eine Art von Angriff, wie zum Beispiel nichtlineare Gebühren, die darauf abzielen, es unattraktiv zu machen, einen großen Stake zu haben, werden in der Regel von einem anderen Angriff unterlaufen. Da es sich um ein wirtschaftliches Spiel handelt, können die entsprechenden statistischen Gewichte im Voraus berechnet werden, und die Gebühren können einfach durch randomisierte Alternativen mit entsprechender Verteilung ersetzt werden. Solche probabilistischen Gebühren lassen sich äußerst einfach implementieren, wenn die Blockchain eine zuverlässige Quelle für Zufälligkeit bietet und keine komplexen Berechnungen erforderlich sind, was sowohl Walen als auch Sybils das Leben erschwert.
Es ist wichtig, sich bewusst zu sein, dass die Kontrolle über ein einzelnes Bit in diesem Zufallsprozess die Möglichkeit bietet, zu manipulieren, indem Wahrscheinlichkeiten verdoppelt oder halbiert werden. Daher ist ein ehrlicher PVRB eine entscheidende Komponente solcher Protokolle.

Wo findet man den richtigen Zufall?

Theoretisch ermöglicht eine ehrliche Zufallsauswahl in dezentralen Netzwerken, nahezu jede Protokollvereinbarung gegen Kollusion nachnachweislich abzusichern. Die Begründung ist recht einfach: Wenn das Netzwerk sich auf ein Bit von 0 oder 1 einigt und weniger als die Hälfte der Teilnehmer unehrlich sind, wird das Netzwerk bei ausreichender Anzahl von Iterationen mit fester Wahrscheinlichkeit zu einem Konsens bezüglich dieses Bits gelangen. Einfach weil der ehrliche Zufallsprozess in 51% der Fälle 51 von 100 Teilnehmern auswählen wird. Aber das ist theoretisch, denn in realen Netzwerken erfordert das Erreichen eines solchen Sicherheitsniveaus, wie in den Artikeln beschrieben, viele Nachrichten zwischen Hosts, komplexe mehrstufige Kryptografie, und jede Erschwerung des Protokolls fügt sofort neue Angriffsvektoren hinzu.
Deshalb ist bisher kein PVRB in Blockchain-Systemen nachweislich robust, der lange genug verwendet wurde, um die Tests durch echte Anwendungen, mehrere Audits, Belastungstests und selbstverständlich echten Angriffen zu bestehen. Ohne diese ist es schwierig, ein Produkt tatsächlich als sicher zu betrachten.

Dennoch gibt es mehrere vielversprechende Ansätze, die sich in zahlreichen Details unterscheiden, und einer von ihnen wird sicherlich das Problem lösen. Mit den heutigen Rechenressourcen kann theoretische Kryptografie recht geschickt in praktische Anwendungen umgesetzt werden. In Zukunft werden wir gerne über die Implementierungen von PVRB berichten: es gibt derzeit mehrere davon, jede mit einem eigenen Satz wichtiger Eigenschaften und Besonderheiten in der Umsetzung, und hinter jeder steht eine interessante Idee. Nur wenige Teams beschäftigen sich mit Randomisierung, und die Erfahrungen jedes einzelnen sind für alle anderen äußerst wertvoll. Wir hoffen, dass unsere Informationen es anderen Teams ermöglichen, schneller voranzukommen, unter Berücksichtigung der Erfahrungen der Vorgänger.

Quelle: habr.com