Randomness for blockchains : generating publicly-verifiable and bias-resistant randomness in decentralized systems

Abstract

S. Nakamoto präsentierte 2008 eine Peer-to-Peer Version von elektronischem Geld: Bitcoin. Dieses System ermöglicht den direkten Zahlungsverkehr zwischen verschiedenen Personen und Organisationen, ohne Finanzdienstleister oder andere zu-vertrauende Dritte als Intermediäre einsetzen zu müssen. Im Zuge dessen entwickelte er die erste praktische Lösung für das Problem der Konsensfindung innerhalb eines dynamischen Netzwerks von potentiell anonymen Knoten, ohne die Notwendigkeit diese zuvor festzulegen. Dieses Ergebnis wird auf Basis des Konzepts von Proof-of-Work erzielt, das auf Grund der hohen Anforderungen für die benötigten Berechnungen zu einem enormen Energieverbrauch führt. Unter Verwendung des alternativen Prinzips von Proof-of-Stake versuchen neue Protokolle Nakamoto's Ansatz weiterzuentwickeln. Eine grundlegende Voraussetzung für die Sicherheit dieser Protokolle ist eine vertrauenswürdige (d. h. öffentlich-verifizierbare und manipulationssichere) Quelle von Zufallszahlen. Deren Erzeugung stellt ein komplexes Problem dar, da diese in einem dezentralen Netzwerk unter dem potentiellen Einfluss von Angreifern durchgeführt wird. Kürzlich veröffentlichte Forschungsergebnisse und Projekte aus der Wirtschaft beschäftigen sich mit diesem Problem und stellen sogenannte Random Beacon Protokolle vor, welche die erforderlichen Zufallszahlen in regelmäßigen Intervallen generieren. Diese Diplomarbeit beschäftigt sich intensiv mit den Herausforderungen der Entwicklung von Random Beacon Protokollen und liefert den ersten detaillierten Vergleich. Es wird gezeigt, dass Publicly-Verfiable Secret Sharing (PVSS) in vielen dieser Ansätze als gemeinsame Komponente dient. Weiters präsentiert diese Arbeit ein neu entwickeltes Protokoll, das ebenfalls PVSS verwendet und die Skalierbarkeit im Vergleich zu den bereits existierenden deutlich verbessert. Da dieser neue Ansatz nur eine PVSS-Instanz pro Runde benötigt, verringert sich der Kommunikationsaufwand von O(n³) auf O(n²). Diese Verbesserung wird erzielt, ohne auf wichtige Protokolleigenschaften, wie öffentliche Verifizierbarkeit, Manipulationssicherheit oder Nichtvorhersagbarkeit, verzichten zu müssen. Darüber hinaus erfolgt eine Optimierung der erarbeiteten Lösung durch die Entwicklung einer Protokollerweiterung, die die Interaktion zwischen den Knoten weiter reduziert und einen nahezu optimalen Kommunikationsaufwand von O(n c) erreicht. Dennoch stellt das erweiterte Protokoll mit sehr großer Wahrscheinlichkeit sicher, dass Zufallszahlen kontinuierlich erzeugt werden können und diese weder manipulierbar noch vorhersagbar sind.