Zufallszahlen und dezentrale Netzwerke: Praktische Anwendungen

Einführung

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

Dieser Artikel widmet sich der praktischen Anwendung von Lösungen mit kollektiver Zufallszahlengenerierung in einer nicht vertrauenswürdigen Umgebung. Kurz gesagt, wie und warum Zufall in Blockchains verwendet wird und ein wenig darüber, wie man „guten“ Zufall von „schlecht“ unterscheiden kann. Das Generieren einer echten Zufallszahl ist selbst auf einem einzelnen Computer ein äußerst schwieriges Problem und wird von Kryptographen seit langem untersucht. Nun, in dezentralen Netzwerken ist die Generierung von Zufallszahlen noch komplexer und wichtiger.

Gerade in Netzwerken, in denen die Teilnehmer einander nicht vertrauen, ermöglicht uns die Fähigkeit, eine unbestreitbare Zufallszahl zu generieren, viele kritische Probleme effektiv zu lösen und bestehende Systeme erheblich zu verbessern. Zudem sind Glücksspiele und Lotterien hier nicht das oberste Ziel, wie es dem unerfahrenen Leser zunächst erscheinen mag.

Zufallszahlengenerierung

Computer können keine Zufallszahlen selbst erzeugen, sie benötigen dazu die Hilfe von außen. Der Computer kann einen Zufallswert beispielsweise aus Mausbewegungen, der verwendeten Speichermenge, Streuströmen an den Prozessorpins und vielen anderen Quellen, sogenannten Entropiequellen, ermitteln. Diese Werte selbst sind nicht völlig zufällig, da sie in einem bestimmten Bereich liegen oder ein vorhersehbares Änderungsmuster aufweisen. Um solche Zahlen innerhalb eines bestimmten Bereichs in eine echte Zufallszahl umzuwandeln, werden Kryptotransformationen auf sie angewendet, um aus den ungleichmäßig verteilten Werten der Entropiequelle gleichmäßig verteilte Pseudozufallswerte zu erzeugen. Die resultierenden Werte werden pseudozufällig genannt, da sie nicht wirklich zufällig sind, sondern deterministisch aus der Entropie abgeleitet werden. Jeder gute kryptografische Algorithmus erzeugt beim Verschlüsseln von Daten Chiffretexte, die statistisch nicht von einer Zufallssequenz zu unterscheiden sein sollten. Um Zufälligkeit zu erzeugen, können Sie also eine Entropiequelle verwenden, die nur eine gute Wiederholbarkeit und Unvorhersehbarkeit von Werten selbst in kleinen Bereichen bietet Der Rest der Arbeit besteht darin, die Bits zu verteilen und zu mischen. Der resultierende Wert wird vom Verschlüsselungsalgorithmus übernommen.

Um ein kurzes Bildungsprogramm zu vervollständigen, möchte ich hinzufügen, dass die Generierung von Zufallszahlen selbst auf einem Gerät eine der Säulen zur Gewährleistung der Sicherheit unserer Daten ist. Die generierten Pseudozufallszahlen werden beim Aufbau sicherer Verbindungen in verschiedenen Netzwerken zur Generierung verwendet kryptografische Schlüssel, zum Lastausgleich, zur Integritätsüberwachung und für viele weitere Anwendungen. Die Sicherheit vieler Protokolle hängt von der Fähigkeit ab, einen zuverlässigen, von außen unvorhersehbaren Zufall zu erzeugen, ihn zu speichern und erst im nächsten Schritt des Protokolls preiszugeben, da sonst die Sicherheit gefährdet wird. Ein Angriff auf einen Pseudozufallswertgenerator ist äußerst gefährlich und bedroht unmittelbar jede Software, die Zufallsgenerierung nutzt.

Das alles sollten Sie wissen, wenn Sie einen Grundkurs in Kryptographie belegt haben. Fahren wir also mit dezentralen Netzwerken fort.

Zufällig in Blockchains

Zunächst werde ich über Blockchains mit Unterstützung für Smart Contracts sprechen; sie sind diejenigen, die die Chancen, die eine qualitativ hochwertige, unbestreitbare Zufälligkeit bietet, voll ausnutzen können. Der Kürze halber werde ich diese Technologie außerdem „Öffentlich überprüfbare Zufallsbeacons” oder PVRB. Da es sich bei Blockchains um Netzwerke handelt, in denen Informationen von jedem Teilnehmer verifiziert werden können, lautet der zentrale Namensbestandteil „Publicly Verifiable“, d. h. Jeder kann mithilfe von Berechnungen den Nachweis erbringen, dass die resultierende Zahl, die auf der Blockchain veröffentlicht wird, die folgenden Eigenschaften aufweist:

• Das Ergebnis muss nachweislich gleichmäßig verteilt sein, also auf einer nachweislich starken Kryptographie basieren.
• Es ist nicht möglich, eines der Bits des Ergebnisses zu steuern. Daher kann der Ausgang nicht im Voraus vorhergesagt werden.
• Sie können das Generierungsprotokoll nicht sabotieren, indem Sie nicht am Protokoll teilnehmen oder das Netzwerk mit Angriffsnachrichten überlasten
• Alle oben genannten Punkte müssen einer Absprache mit einer zulässigen Anzahl unehrlicher Protokollteilnehmer (z. B. 1/3 der Teilnehmer) standhalten.

Jede Möglichkeit, dass eine kleine Gruppe von Teilnehmern zusammenarbeitet, um auch nur ein kontrolliertes gerades/ungerades Zufallsergebnis zu erzeugen, stellt eine Sicherheitslücke dar. Jede Fähigkeit der Gruppe, die Ausgabe von Zufallszahlen zu stoppen, stellt eine Sicherheitslücke dar. Im Allgemeinen gibt es viele Probleme und diese Aufgabe ist nicht einfach ...

Es scheint, dass die wichtigste Anwendung für PVRB verschiedene Spiele, Lotterien und allgemein jede Art von Glücksspiel auf der Blockchain sind. Dies ist in der Tat eine wichtige Richtung, aber der Zufall in Blockchains hat noch wichtigere Anwendungen. Schauen wir sie uns an.

Konsensalgorithmen

PVRB spielt eine große Rolle bei der Organisation des Netzwerkkonsenses. Transaktionen in Blockchains sind durch eine elektronische Signatur geschützt, ein „Angriff auf eine Transaktion“ ist also immer die Aufnahme/Ausschluss einer Transaktion in einen Block (oder mehrere Blöcke). Und die Hauptaufgabe des Konsensalgorithmus besteht darin, sich auf die Reihenfolge dieser Transaktionen und die Reihenfolge der Blöcke zu einigen, die diese Transaktionen enthalten. Eine notwendige Eigenschaft für echte Blockchains ist außerdem die Endgültigkeit – die Fähigkeit des Netzwerks, sich darauf zu einigen, dass die Kette bis zum endgültigen Block endgültig ist und niemals aufgrund des Erscheinens einer neuen Abzweigung ausgeschlossen wird. Um zuzustimmen, dass ein Block gültig und vor allem endgültig ist, ist es normalerweise notwendig, Unterschriften von der Mehrheit der Blockproduzenten (im Folgenden BP – Blockproduzenten) zu sammeln, was zumindest die Lieferung der Blockkette erfordert an alle BPs und die Verteilung von Signaturen zwischen allen BPs. Wenn die Anzahl der BPs wächst, wächst die Anzahl der erforderlichen Nachrichten im Netzwerk exponentiell. Daher funktionieren Konsensalgorithmen, die Endgültigkeit erfordern, wie sie beispielsweise im Hyperledger-pBFT-Konsens verwendet werden, nicht mit der erforderlichen Geschwindigkeit, die ab mehreren Dutzend BPs erforderlich ist eine große Anzahl von Verbindungen.

Wenn es im Netzwerk einen unbestreitbaren und ehrlichen PVRB gibt, dann kann man selbst in der einfachsten Näherung einen der darauf basierenden Blockproduzenten auswählen und ihn während einer Runde des Protokolls zum „Anführer“ ernennen. Wenn wir haben N Blockproduzenten, davon M: M > 1/2 N Wenn Sie ehrlich sind, Transaktionen nicht zensieren und die Kette nicht aufspalten, um einen „Double-Spend“-Angriff durchzuführen, dann wird die Verwendung eines gleichmäßig verteilten, unangefochtenen PVRB die Auswahl eines ehrlichen Anführers mit Wahrscheinlichkeit ermöglichen M / N (M / N > 1/2). Wenn jedem Anführer sein eigenes Zeitintervall zugewiesen wird, in dem er einen Block erzeugen und die Kette validieren kann, und diese Intervalle zeitlich gleich sind, dann ist die Blockkette ehrlicher BPs länger als die Kette böswilliger BPs und des Konsenses Der Algorithmus basiert auf der Länge der Kette. Er verwirft einfach die „schlechte“ Kette. Dieses Prinzip, jedem BP gleiche Zeitabschnitte zuzuweisen, wurde erstmals in Graphene (dem Vorgänger von EOS) angewendet und ermöglicht das Schließen der meisten Blöcke mit einer einzigen Signatur, was die Netzwerklast erheblich reduziert und es ermöglicht, dass dieser Konsens extrem schnell und funktioniert ständig. Allerdings muss das EOS-Netzwerk nun spezielle Blöcke (Last Irreversible Block) verwenden, die durch die Signaturen von 2/3 BP bestätigt werden. Diese Blöcke dienen dazu, die Endgültigkeit sicherzustellen (die Unmöglichkeit, dass eine Kettenverzweigung vor dem letzten letzten irreversiblen Block beginnt).

Außerdem ist das Protokollschema in realen Implementierungen komplizierter – die Abstimmung über vorgeschlagene Blöcke erfolgt in mehreren Stufen, um das Netzwerk bei fehlenden Blöcken und Problemen mit dem Netzwerk aufrechtzuerhalten, aber selbst unter Berücksichtigung dieser Tatsache erfordern Konsensalgorithmen, die PVRB verwenden deutlich weniger Nachrichten zwischen BPs, was es ermöglicht, sie schneller als herkömmliches PVFT oder seine verschiedenen Modifikationen zu machen.

Der prominenteste Vertreter solcher Algorithmen: Ouroboros vom Cardano-Team, das mathematisch gegen BP-Absprachen beweisbar sein soll.

In Ouroboros wird PVRB verwendet, um den sogenannten „BP-Zeitplan“ zu definieren – einen Zeitplan, nach dem jedem BP ein eigenes Zeitfenster für die Veröffentlichung eines Blocks zugewiesen wird. Der große Vorteil der Nutzung von PVRB ist die völlige „Gleichheit“ der BPs (entsprechend der Größe ihrer Bilanzen). Die Integrität des PVRB stellt sicher, dass böswillige BPs die Planung von Zeitfenstern nicht kontrollieren und daher die Kette nicht manipulieren können, indem sie Zweige der Kette im Voraus vorbereiten und analysieren. Um einen Zweig auszuwählen, reicht es aus, sich einfach auf die Länge des Zweigs zu verlassen Kette, ohne knifflige Methoden zur Berechnung des „Nutzens“ von BP und des „Gewichts“ seiner Blöcke zu verwenden.

Im Allgemeinen ist PVRB in allen Fällen, in denen ein zufälliger Teilnehmer in einem dezentralen Netzwerk ausgewählt werden muss, fast immer die beste Wahl und nicht eine deterministische Option, die beispielsweise auf einem Block-Hash basiert. Ohne PVRB führt die Möglichkeit, die Wahl eines Teilnehmers zu beeinflussen, zu Angriffen, bei denen der Angreifer aus mehreren Zukünften wählen kann, um den nächsten korrupten Teilnehmer auszuwählen, oder mehrere gleichzeitig, um sich einen größeren Anteil an der Entscheidung zu sichern. Der Einsatz von PVRB diskreditiert diese Art von Angriffen.

Skalierung und Lastausgleich

PVRB kann auch bei Aufgaben wie Lastreduzierung und Zahlungsskalierung von großem Nutzen sein. Zunächst ist es sinnvoll, sich damit vertraut zu machen Artikel Rivesta „Elektronische Lottoscheine als Mikrozahlungen“. Die allgemeine Idee besteht darin, dass Sie, anstatt 100 1-Cent-Zahlungen vom Zahler an den Empfänger zu leisten, eine ehrliche Lotterie mit einem Gewinn von 1 $ = 100 Cent spielen können, bei der der Zahler der Bank für jeden einen von 1 seiner „Lottoscheine“ gibt 100c Zahlung. Mit einem dieser Tickets gewinnt man ein Glas mit 1 US-Dollar, und dieses Ticket kann der Empfänger in der Blockchain erfassen. Das Wichtigste ist, dass die restlichen 99 Tickets ohne externe Beteiligung, über einen privaten Kanal und in jeder gewünschten Geschwindigkeit zwischen Empfänger und Zahler übertragen werden. Eine gute Beschreibung des auf diesem Schema basierenden Protokolls im Emercoin-Netzwerk finden Sie hier hier.

Bei diesem System gibt es einige Probleme, z. B. kann es sein, dass der Empfänger die Zustellung an den Zahler unmittelbar nach Erhalt eines Gewinnloses einstellt. Bei vielen Sonderanwendungen, wie z. B. der Minutenabrechnung oder elektronischen Abonnements von Diensten, können diese jedoch vernachlässigt werden. Die wichtigste Voraussetzung ist natürlich die Fairness der Lotterie, und für ihre Umsetzung ist ein PVRB unbedingt erforderlich.

Die Wahl eines zufälligen Teilnehmers ist auch für Sharding-Protokolle äußerst wichtig, deren Zweck darin besteht, die Blockchain horizontal zu skalieren, sodass verschiedene BPs nur ihren Transaktionsbereich verarbeiten können. Dies ist eine äußerst schwierige Aufgabe, insbesondere im Hinblick auf die Sicherheit beim Zusammenführen von Shards. Die faire Auswahl eines zufälligen BP zum Zweck der Zuordnung der Verantwortlichen für einen bestimmten Shard, wie bei Konsensalgorithmen, ist ebenfalls Aufgabe des PVRB. In zentralisierten Systemen werden Shards von einem Balancer zugewiesen; er berechnet einfach den Hash aus der Anfrage und sendet ihn an den erforderlichen Executor. In Blockchains kann die Möglichkeit, diese Zuordnung zu beeinflussen, zu einem Angriff auf den Konsens führen. Beispielsweise kann ein Angreifer den Inhalt von Transaktionen kontrollieren, er kann steuern, welche Transaktionen an den von ihm kontrollierten Shard gehen, und die Blockkette darin manipulieren. Sie können eine Diskussion über das Problem der Verwendung von Zufallszahlen für Sharding-Aufgaben in Ethereum lesen hier
Sharding ist eines der ehrgeizigsten und schwerwiegendsten Probleme im Bereich der Blockchain; seine Lösung wird den Aufbau dezentraler Netzwerke mit fantastischer Leistung und Volumen ermöglichen. PVRB ist nur einer der wichtigen Blöcke zur Lösung.

Spiele, Wirtschaftsprotokolle, Schiedsverfahren

Die Rolle von Zufallszahlen in der Spielebranche kann kaum überschätzt werden. Die explizite Verwendung in Online-Casinos und die implizite Verwendung bei der Berechnung der Auswirkungen der Aktion eines Spielers sind äußerst schwierige Probleme für dezentrale Netzwerke, in denen es keine Möglichkeit gibt, sich auf eine zentrale Zufallsquelle zu verlassen. Aber auch eine zufällige Auswahl kann viele wirtschaftliche Probleme lösen und dabei helfen, einfachere und effizientere Protokolle zu erstellen. Angenommen, in unserem Protokoll gibt es Streitigkeiten über die Bezahlung einiger kostengünstiger Dienste, und diese Streitigkeiten kommen recht selten vor. In diesem Fall, wenn ein unbestrittener PVRB vorliegt, können Kunden und Verkäufer vereinbaren, Streitigkeiten nach dem Zufallsprinzip, jedoch mit einer bestimmten Wahrscheinlichkeit, beizulegen. Beispielsweise gewinnt der Kunde mit einer Wahrscheinlichkeit von 60 %, und mit einer Wahrscheinlichkeit von 40 % gewinnt der Verkäufer. Dieser auf den ersten Blick absurde Ansatz ermöglicht es, Streitigkeiten automatisch mit einem genau vorhersehbaren Anteil an Gewinnen/Verlusten zu lösen, was für beide Parteien ohne Beteiligung Dritter und unnötiger Zeitverschwendung sinnvoll ist. Darüber hinaus kann das Wahrscheinlichkeitsverhältnis dynamisch sein und von einigen globalen Variablen abhängen. Wenn es einem Unternehmen beispielsweise gut geht, es nur wenige Streitigkeiten gibt und es eine hohe Rentabilität hat, kann das Unternehmen die Wahrscheinlichkeit, einen Streit beizulegen, automatisch in Richtung Kundenorientierung verschieben, beispielsweise 70/30 oder 80/20, und umgekehrt. Wenn Streitigkeiten viel Geld kosten und betrügerisch oder unzureichend sind, können Sie die Wahrscheinlichkeit in die andere Richtung verschieben.

Eine große Anzahl interessanter dezentraler Protokolle, wie z. B. von Token kuratierte Register, Prognosemärkte, Bindungskurven und viele andere, sind Wirtschaftsspiele, bei denen gutes Verhalten belohnt und schlechtes Verhalten bestraft wird. Sie enthalten häufig Sicherheitsprobleme, bei denen Schutzmaßnahmen miteinander in Konflikt stehen. Was vor einem Angriff von „Walen“ mit Milliarden von Token („Big Stake“) geschützt ist, ist anfällig für Angriffe von Tausenden von Konten mit kleinen Guthaben („Sybil Stake“) und Maßnahmen gegen einen einzelnen Angriff, wie z. Lineare Gebühren, die geschaffen wurden, um das Arbeiten mit einem großen Einsatz unrentabel zu machen, werden in der Regel durch einen weiteren Angriff diskreditiert. Da es sich um ein Wirtschaftsspiel handelt, können die entsprechenden statistischen Gewichte im Voraus berechnet werden und die Provisionen einfach durch zufällige mit der entsprechenden Verteilung ersetzt werden. Solche probabilistischen Kommissionen lassen sich äußerst einfach umsetzen, wenn die Blockchain über eine zuverlässige Zufallsquelle verfügt und keine komplexen Berechnungen erfordern, was sowohl Walen als auch Sybillen das Leben schwer macht.
Gleichzeitig muss man sich weiterhin daran erinnern, dass die Kontrolle über ein einzelnes Bit in dieser Zufälligkeit es ermöglicht, zu schummeln, die Wahrscheinlichkeiten zu reduzieren oder um die Hälfte zu erhöhen, sodass ein ehrlicher PVRB der wichtigste Bestandteil solcher Protokolle ist.

Wo findet man den richtigen Zufall?

Theoretisch macht eine faire Zufallsauswahl in dezentralen Netzwerken fast jedes Protokoll nachweislich sicher gegen Absprachen. Der Grund dafür ist ganz einfach: Wenn sich das Netzwerk auf ein einzelnes 0- oder 1-Bit einigt und weniger als die Hälfte der Teilnehmer unehrlich ist, dann wird das Netzwerk bei genügend Iterationen mit einer festen Wahrscheinlichkeit garantiert einen Konsens über dieses Bit erzielen. Ganz einfach, weil ein ehrlicher Zufall in 51 % der Fälle 100 von 51 Teilnehmern auswählt. Aber das ist nur theoretisch, denn... Um in realen Netzwerken ein solches Sicherheitsniveau wie in den Artikeln zu gewährleisten, sind viele Nachrichten zwischen Hosts und eine komplexe Multi-Pass-Kryptografie erforderlich, und jede Komplikation des Protokolls führt sofort zu neuen Angriffsvektoren.
Aus diesem Grund sehen wir in Blockchains noch kein nachweislich resistentes PVRB, das lange genug verwendet worden wäre, um durch reale Anwendungen, mehrere Audits, Lasten und natürlich echte Angriffe getestet zu werden, ohne die es schwierig ist, als a zu bezeichnen Produkt wirklich sicher.

Allerdings gibt es mehrere vielversprechende Ansätze, die sich in vielen Details unterscheiden und einer davon wird das Problem auf jeden Fall lösen. Mit modernen Rechenressourcen lässt sich die kryptografische Theorie recht geschickt in praktische Anwendungen übertragen. In Zukunft werden wir gerne über PVRB-Implementierungen sprechen: Mittlerweile gibt es mehrere davon, jede hat ihre eigenen wichtigen Eigenschaften und Implementierungsmerkmale und hinter jeder steckt eine gute Idee. Es gibt nicht viele Teams, die an der Randomisierung beteiligt sind, und die Erfahrung jedes einzelnen von ihnen ist für alle anderen äußerst wichtig. Wir hoffen, dass unsere Informationen es anderen Teams ermöglichen, unter Berücksichtigung der Erfahrungen ihrer Vorgänger schneller voranzukommen.

Source: habr.com