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.

In 2008, S. Nakamoto presented Bitcoin as a peer-to-peer version of electronic cash -- a system allowing direct payments between participants without the need for a financial institution or trusted third party. Thereby, he proposed the first practical solution for the problem of reaching consensus in a dynamic set of potentially anonymous participants without a prior agreement on this set. Bitcoin achieves this advancement at the cost of high computational requirements for Proof-of-Work, leading to vast amounts of electricity being consumed. Recently, new protocols, using Proof-of-Stake as a fundamental principle, have tried to improve upon Nakamoto's solution. These protocols require a trustworthy source of randomness, i.e. publicly-verifiable and bias-resistant randomness, to maintain desirable security guarantees. However, obtaining trustworthy randomness, in a highly decentralized network and under potentially adversarial conditions, is by itself a challenging task. Recent academic research as well as projects from the industry try to address this problem by designing random beacon protocols, which produce the required random values in regular intervals. In this thesis, we highlight the design challenges of random beacon protocols as well as provide the first in-depth review and comparison of state-of-the-art protocols. We identify public-verifiable secret sharing (PVSS) as a common building block and develop a new protocol using this cryptographic primitive. Our PVSS-based random beacon protocol greatly improves upon the scalability of existing approaches. Communication complexity is reduced from O(n³) to O(n²), as our solution only requires a single PVSS instance per round. Our protocol achieves this advancement while ensuring important protocol characteristics such as public-verifiability, bias-resistance and unpredictability. Additionally, we present an optimized solution as a protocol extension, which further reduces the interaction between network nodes and achieves a near optimal communication complexity of O(n c). This improvement is accomplished while still retaining liveness, bias-resistance and unpredictability of the random beacon values with very high probability.