Einführung
"Die Generierung von Zufallszahlen ist zu wichtig, um sie dem Zufall zu überlassen."
Robert Cavyu, 1970
Dieser Artikel befasst sich mit der praktischen Anwendung von Lösungen unter Verwendung der kollektiven Erzeugung von Zufallszahlen in einer nicht vertrauenswürdigen Umgebung. Kurz gesagt - wie und warum der Zufall in Blockchains verwendet wird und ein wenig darüber, wie man „guten“ Zufall von „schlechten“ unterscheidet. Das Generieren einer wirklich zufälligen Zahl ist selbst auf einem separaten Computer ein äußerst schwieriges Problem und wurde von Kryptographen seit langem untersucht. In dezentralen Netzwerken ist die Erzeugung von Zufallszahlen noch komplexer und wichtiger.
In Netzwerken, in denen sich die Teilnehmer nicht gegenseitig vertrauen, kann die Fähigkeit, eine unbestreitbare Zufallszahl zu generieren, viele wichtige Probleme effektiv lösen und bestehende Systeme erheblich verbessern. Darüber hinaus sind Glücksspiele und Lotterien hier keineswegs das oberste Ziel, wie ein unerfahrener Leser zunächst scheinen mag.
Zufallszahlengenerierung
Computer wissen nicht, wie sie selbst Zufallszahlen erzeugen sollen, dafür benötigen sie Hilfe von außen. Ein Computer kann einen zufälligen Wert erhalten, indem er beispielsweise Mausbewegungen, die Menge des verwendeten Speichers, Störströme auf den Prozessorkontakten und viele andere Quellen verwendet, die als Entropiequellen bezeichnet werden. Diese Werte selbst sind nicht völlig zufällig, da sie in einem bestimmten Bereich liegen oder vorhersehbare Änderungen aufweisen. Um solche Zahlen in einem bestimmten Bereich in eine wirklich zufällige Zahl umzuwandeln, werden kryptografische Transformationen auf sie angewendet, um gleichmäßig verteilte Pseudozufallswerte aus den ungleichmäßig verteilten Werten der Entropiequelle zu erhalten. Die erhaltenen Werte werden als pseudozufällig bezeichnet, da sie nicht wirklich zufällig sind, sondern deterministisch aus der Entropie abgeleitet werden. Jeder gute kryptografische Algorithmus, der die Daten verschlüsselt, erzeugt Chiffretexte, die statistisch nicht von einer zufälligen Sequenz zu unterscheiden sind. Für die Erzeugung der Randomisierung können Sie eine Entropiequelle verwenden, die selbst in kleinen Bereichen nur eine gute Wiederholbarkeit und Unvorhersehbarkeit von Werten bietet. Der Rest der Arbeit besteht darin, Bits zu streuen und zu mischen Der resultierende Wert wird vom Verschlüsselungsalgorithmus übernommen.
Um das kurze Schulungsprogramm abzuschließen, möchte ich hinzufügen, dass die Generierung von Zufallszahlen auch auf einem Gerät eine der Säulen zur Gewährleistung der Sicherheit unserer Daten darstellt. Die generierten Pseudozufallszahlen werden verwendet, um sichere Verbindungen in verschiedenen Netzwerken herzustellen, kryptografische Schlüssel zu generieren, die Last auszugleichen, die Integrität zu kontrollieren. und für viele weitere Zwecke. Die Sicherheit vieler Protokolle hängt von der Fähigkeit ab, zuverlässige, unvorhersehbare Zufallsdaten von außen zu generieren, zu speichern und erst im nächsten Schritt des Protokolls zu öffnen. Andernfalls wird die Sicherheit beeinträchtigt. Ein Angriff auf einen Pseudozufallswertgenerator ist äußerst gefährlich und bedroht alle Software, die die Zufallsgenerierung gleichzeitig verwendet.
Sie sollten dies alles wissen, wenn Sie einen grundlegenden Kryptografiekurs absolviert haben. Fahren wir also mit dezentralen Netzwerken fort.
Blockchain zufällig
Zunächst werde ich über Blockchains mit Unterstützung für intelligente Verträge sprechen. Sie können die Möglichkeiten eines unbestreitbaren Qualitäts-Zufalls voll ausschöpfen. Der Kürze halber werde ich diese Technologie als " öffentlich überprüfbare Zufallsbaken " oder PVRB bezeichnen. Da Blockchains Netzwerke sind, in denen jeder Teilnehmer Informationen überprüfen kann, ist der Schlüsselteil des Namens "öffentlich überprüfbar", d. H. Jeder, der mithilfe von Berechnungen arbeitet, kann nachweisen, dass die resultierende Zahl in der Blockchain die folgenden Eigenschaften aufweist:
- Das Ergebnis sollte eine nachweislich gleichmäßige Verteilung aufweisen, d. H. Basierend auf einer nachweislich starken Kryptographie.
- Keines der Bits des Ergebnisses kann gesteuert werden. Infolgedessen kann das Ergebnis 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 sollten gegen Absprachen der zulässigen Anzahl unehrlicher Teilnehmer am Protokoll (z. B. 1/3 der Teilnehmer) resistent sein.
Jede Möglichkeit für eine verschwörerische kleine Gruppe von Teilnehmern, sogar einen kontrollierten geraden / ungeraden Zufall zu erzeugen, ist eine Sicherheitslücke. Jede Möglichkeit für die Gruppe, die Ausgabe eines zufälligen Hauses einzustellen, ist eine Sicherheitslücke. 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 im Allgemeinen jede Art von Glücksspiel in der Blockchain sind. Dies ist zwar eine wichtige Richtung, aber das zufällige Haus in Blockchains hat Anwendungen und ist wichtiger. Betrachten Sie sie.
Konsensalgorithmen
PVRB ist entscheidend für den Netzwerkkonsens. Transaktionen in Blockchains sind durch eine elektronische Signatur geschützt. Daher ist „Angriff auf eine Transaktion“ immer das Einschließen / Ausschließen einer Transaktion in einem Block (oder in mehreren Blöcken). Die Hauptaufgabe des Konsensalgorithmus besteht darin, die Reihenfolge dieser Transaktionen und die Reihenfolge der Blöcke, die diese Transaktionen enthalten, zu vereinbaren. Eine notwendige Eigenschaft für echte Blockchains ist auch die Endgültigkeit - die Fähigkeit des Netzwerks, zuzustimmen, dass die Kette zum finalisierten Block endgültig ist, und wird aufgrund des Auftretens einer neuen Gabel niemals ausgeschlossen. Um zuzustimmen, dass ein Block gültig und vor allem endgültig ist, müssen Sie normalerweise Signaturen von den meisten Blockproduzenten (im Folgenden BP - Blockproduzenten) sammeln, was mindestens die Lieferung einer Blockkette an alle BPs und die Verteilung von Signaturen zwischen allen BPs erfordert . Mit zunehmender Anzahl von BPs wächst die Anzahl der erforderlichen Nachrichten im Netzwerk exponentiell. Daher arbeiten Konsensalgorithmen, die Endgültigkeit erfordern, wie sie im pBFT-Konsens von Hyperledger verwendet werden, nicht mit der richtigen Geschwindigkeit, beginnend mit mehreren Dutzend BPs, die eine große Anzahl von Verbindungen erfordern.
Wenn das Netzwerk einen unbestreitbaren und ehrlichen PVRB hat, ist es auch in einfachster Näherung möglich, einen der Blockproduzenten auf dieser Grundlage auszuwählen und ihn zum „Leader“ für eine Runde des Protokolls zu ernennen. Wenn wir N Blockproduzenten haben, von denen M: M > 1/2 N ehrlich sind, zensieren Sie keine Transaktionen und bauen Sie keine Gabelketten, um einen Angriff mit doppelten Ausgaben durchzuführen. Wenn Sie einen gleichmäßig verteilten unbestreitbaren PVRB verwenden, können Sie einen ehrlichen Anführer auswählen mit der Wahrscheinlichkeit M / N (M / N > 1/2) . Wenn jedem Anführer ein eigenes Zeitintervall zugewiesen wird, in dem er einen Block erstellen und die Kette validieren kann, und diese Intervalle zeitlich gleich sind, ist die Kette ehrlicher BP-Blöcke länger als die vom böswilligen BP gebildete Kette, und der Konsensalgorithmus basiert auf der Länge der Kette. verwerfe einfach das "schlechte". Dieses Prinzip, jedem BP gleiche Zeitscheiben zuzuweisen, wurde erstmals in Graphene (dem Vorgänger von EOS) angewendet und ermöglicht das Schließen der meisten Blöcke mit einer Signatur, wodurch die Netzwerklast erheblich reduziert wird und dieser Konsens extrem schnell und stetig funktioniert. EOS-Netzwerke müssen jetzt jedoch spezielle Blöcke (Last Irreversible Block) verwenden, die durch 2/3 BP-Signaturen bestätigt werden. Diese Blöcke werden verwendet, um die Endgültigkeit sicherzustellen (die Unmöglichkeit, dass eine Gabelkette früher als der letzte letzte irreversible Block beginnt).
In realen Implementierungen ist das Protokollschema auch komplizierter - die Abstimmung für die vorgeschlagenen Blöcke erfolgt in mehreren Schritten, um das Netzwerk bei Blockübersprung und Netzwerkproblemen aufrechtzuerhalten, aber selbst in diesem Sinne erfordern PVRB-Konsensalgorithmen erheblich weniger Nachrichten zwischen BPs. Dies ermöglicht es Ihnen, sie schneller als herkömmliche PBFT oder ihre verschiedenen Modifikationen zu machen.
Der auffälligste Vertreter solcher Algorithmen: Ouroboros vom Cardano-Team, das, wie angekündigt, einen mathematisch nachweisbaren Widerstand gegen Kollusionen zwischen BP aufweist.
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 Verwendung von PVRB ist die vollständige „Gleichberechtigung“ von BP (entsprechend der Größe ihrer Guthaben). Honesty PVRB stellt sicher, dass böswillige BPs den Zeitplan für Zeitfenster nicht kontrollieren können und daher die Kette nicht manipulieren können, indem sie die Kettengabeln im Voraus vorbereiten und analysieren. Um eine Gabel auszuwählen, können Sie sich einfach auf die Länge der Kette verlassen, ohne knifflige Methoden zur Berechnung des „Nutzens“ von BP und zu verwenden "Gewichte" seiner Blöcke.
In allen Fällen, in denen ein zufälliger Teilnehmer in einem dezentralen Netzwerk ausgewählt werden muss, ist PVRB im Allgemeinen fast immer die beste Wahl und keine deterministische Option, die beispielsweise auf einem Block-Hash basiert. Ohne PVRB führt die Fähigkeit, die Wahl des Teilnehmers zu beeinflussen, zum Auftreten von Angriffen, bei denen der Angreifer aus mehreren Optionen für die Zukunft den nächsten korrupten Teilnehmer oder mehrere gleichzeitig auswählen kann, um einen größeren Anteil an der Entscheidung zu erhalten. Die Verwendung von PVRB diskreditiert diese Art von Angriffen.
Skalierung und Lastausgleich
PVRB kann auch bei Aufgaben zur Reduzierung der Arbeitsbelastung und zur Skalierung von Zahlungen von großem Nutzen sein. Für den Anfang ist es sinnvoll, Rivests Artikel "Elektronische Lottoscheine als Mikrozahlungen" zu lesen. Die allgemeine Essenz ist, dass Sie anstelle von 100 Zahlungen von 1c vom Zahler an den Empfänger eine ehrliche Lotterie mit einem Preis von 1 $ = 100c spielen können, bei der der Zahler für jede Zahlung in 1c einen seiner 100 „Lottoscheine“ an die Bank überweist. Eines dieser Tickets gewinnt die Bank $ 1, und dieses Ticket kann der Empfänger in der Blockchain reparieren. Am wichtigsten ist, dass die verbleibenden 99 Tickets ohne externe Beteiligung, über einen privaten Kanal und mit jeder gewünschten Geschwindigkeit zwischen dem Empfänger und dem Zahler übertragen werden. Eine gute Beschreibung des auf diesem Schema basierenden Protokolls im Emercoin-Netzwerk finden Sie hier .
Dieses Schema weist mehrere Probleme auf, z. B. kann der Empfänger die Zustellung des Zahlers unmittelbar nach Erhalt eines Gewinnscheins einstellen, aber für viele spezielle Anwendungen, wie die Abrechnung pro Minute oder elektronische Abonnements von Diensten, können diese vernachlässigt werden. Die Hauptanforderung ist natürlich die Ehrlichkeit der Lotterie, und PVRB ist für ihre Durchführung absolut notwendig.
Die Auswahl eines zufälligen Teilnehmers ist auch äußerst wichtig für Sharding-Protokolle, deren Zweck darin besteht, die Blockkette horizontal zu skalieren, sodass verschiedene BPs nur ihren Transaktionsumfang verarbeiten können. Dies ist eine äußerst schwierige Aufgabe, insbesondere wenn es um die Sicherheit beim Zusammenführen von Shards geht. Die ehrliche Wahl eines zufälligen BP, um ihn den Verantwortlichen für einen bestimmten Shard zuzuweisen, wie bei Konsensalgorithmen, ist ebenfalls eine PVRB-Aufgabe. In zentralisierten Systemen werden Shards vom Balancer zugewiesen, er berechnet einfach den Hash aus der Anforderung und sendet ihn an den erforderlichen Executor. Bei Blockchains kann die Fähigkeit, diese Zuordnung zu beeinflussen, zu einem Angriff auf den Konsens führen. Zum Beispiel kann der Inhalt von Transaktionen vom Angreifer gesteuert werden, er kann steuern, welche Transaktionen in den von ihm kontrollierten Shard fallen, und die darin enthaltene Blockkette manipulieren. Eine Diskussion des Problems der Verwendung von Zufallszahlen für Sharding-Probleme in Ethereum finden Sie hier.
Sharding ist eine der ehrgeizigsten und schwerwiegendsten Aufgaben im Bereich der Blockchain. Mit seiner Lösung können Sie dezentrale Netzwerke mit fantastischer Leistung und Volumen aufbauen. PVRB ist nur einer der wichtigen Blöcke, um es zu lösen.
Spiele, Wirtschaftsprotokolle, Schiedsverfahren
Die Rolle von Zufallszahlen in der Spielebranche ist schwer zu überschätzen. Die explizite Verwendung in Online-Casinos und die implizite 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. Eine zufällige Auswahl kann jedoch viele wirtschaftliche Probleme lösen und dazu beitragen, einfachere und effizientere Protokolle zu erstellen. Angenommen, in unserem Protokoll gibt es Streitigkeiten über die Bezahlung einiger kostengünstiger Dienstleistungen, und diese Streitigkeiten sind ziemlich selten. In diesem Fall können Kunden und Verkäufer bei einem unbestreitbaren PVRB eine zufällige Beilegung von Streitigkeiten vereinbaren, jedoch mit einer bestimmten Wahrscheinlichkeit. Mit einer Wahrscheinlichkeit von 60% gewinnt beispielsweise der Kunde und mit einer Wahrscheinlichkeit von 40% gewinnt der Verkäufer. Ein derart absurder Ansatz ermöglicht es aus der ersten Sicht, Streitigkeiten mit einem genau vorhersehbaren Anteil an Gewinnen / Verlusten automatisch zu lösen, was für beide Parteien ohne Beteiligung Dritter und unnötige Zeitverschwendung geeignet 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 eine geringe Anzahl von Streitigkeiten und eine hohe Rentabilität gibt, kann das Unternehmen die Wahrscheinlichkeit einer Streitbeilegung automatisch in Richtung Kundenorientierung verschieben, z. B. 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. Token-Currized-Register, Prognosemärkte, Bindungskurven und viele andere, sind Wirtschaftsspiele, die gutes und gutes schlechtes Verhalten belohnen. Sie stoßen häufig auf Sicherheitsprobleme, deren Schutz sich widerspricht. Was vor einem Angriff von „Walen“ mit Milliarden von Token („großer Einsatz“) geschützt ist, ist anfällig für Angriffe von Tausenden von Konten mit kleinen Guthaben („Sybil-Einsatz“) und Maßnahmen gegen einen Angriff, z. B. nichtlineare Provisionen für Um ein großes Steak nachteilig wirken zu lassen, werden sie normalerweise durch einen anderen Angriff diskreditiert. Da dies ein wirtschaftliches Spiel ist, können die entsprechenden statistischen Gewichte im Voraus berechnet werden und die Provisionen einfach durch zufällige Provisionen mit der entsprechenden Verteilung ersetzt werden. Solche probabilistischen Provisionen werden extrem einfach implementiert, wenn die Blockchain eine zuverlässige Zufallsquelle hat und keine komplexen Berechnungen erfordert, was Walen und Sybil das Leben schwer macht.
Denken Sie weiterhin daran, dass Sie durch die Kontrolle über ein einzelnes Bit in dieser Randomisierung die Wahrscheinlichkeiten betrügen, reduzieren und verdoppeln können. Daher ist ehrlicher PVRB die wichtigste Komponente solcher Protokolle.
Wo finde ich den richtigen Zufall?
Theoretisch bieten ehrliche Zufallsentscheidungen in dezentralen Netzwerken die nachweisbare Sicherheit fast aller Protokolle gegen Absprachen. Die Begründung ist recht einfach: Wenn sich das Netzwerk auf ein Bit 0 oder 1 einigt und weniger als die Hälfte der Teilnehmer unehrlich sind, wird das Netzwerk bei einer ausreichenden Anzahl von Iterationen garantiert mit einer festen Wahrscheinlichkeit zu einem Konsens über dieses Bit kommen. Nur weil ein ehrlicher Zufall in 51% der Fälle 51 von 100 Teilnehmern auswählt. Aber das ist theoretisch so, weil In realen Netzwerken sind viele Nachrichten zwischen Hosts, komplexe Kryptografie mit mehreren Durchgängen und jede Komplikation des Protokolls erforderlich, um ein Sicherheitsniveau wie in Artikeln zu gewährleisten. Sofort werden neue Angriffsmethoden hinzugefügt.
Aus diesem Grund sehen wir in den Blockchains noch keinen bewährten PVRB, der genügend Zeit benötigt hätte, um von realen Anwendungen, mehreren Audits, Lasten und natürlich echten Angriffen getestet zu werden, ohne die es schwierig ist, das Produkt als wirklich sicher zu bezeichnen.
Trotzdem gibt es mehrere vielversprechende Ansätze gleichzeitig, die sich in vielen Details unterscheiden und von denen einige das Problem definitiv lösen werden. Mit modernen Rechenressourcen kann die kryptografische Theorie sehr geschickt in praktische Anwendungen umgewandelt werden. In Zukunft werden wir gerne über die Implementierung von PVRB sprechen: Es gibt jetzt mehrere davon, jeder hat seine eigenen wichtigen Eigenschaften und Merkmale in der Implementierung und jeder hat eine gute Idee. Es sind nicht viele Teams in den Zufall involviert, 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, sich unter Berücksichtigung der Erfahrungen ihrer Vorgänger schneller zu bewegen.