Schindler, P. (2022). Advances in distributed randomness [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2022.107310
Distributed randomness, the problem of how a network of computers can jointly and securely generate a sequence of verifiably random values, is a long-standing research topic in computer science. Recently, the problem has seen a large amount of renewed interest, mainly due to technical innovations emerging in the field of public distributed ledgers. Whereas Bitcoin was the first to implement a digital currency that does not rely on a central party, we now see thousands of projects building platforms and applications far beyond the functionality of a payment system. Still, a Proof-of-Work consensus algorithm, the core concept used to implement Bitcoin, powers many large real-world systems in this domain. Unfortunately, Proof-of-Work inherently requires a tremendous amount of electrical power to ensure the system's security. This requirement is one of the key reasons why leading projects in this field have already switched to, or are considering, alternative designs, most prominently Proof-of-Stake. And distributed randomness, for example, used to implement leader selection, sharding, or the resolution of ties in the consensus algorithm, turns out to be an essential component of these designs. In order to support the development of these alternatives and several other use cases, this thesis sets out to explore, analyze, and improve upon existing approaches for distributed randomness. Our main results include two novel protocol designs named HydRand and RandRunner. With HydRand, we do not only improve upon the theoretical efficiency compared to other designs with similar guarantees but also demonstrate that these results are translatable into practice by providing our prototype implementation. RandRunner's design, despite being quite minimalistic, furthermore improves communication efficiency by only propagating a single message to produce a new random output. Additionally, it achieves a wide range of desirable security guarantees and properties, for example, automatic recovery from temporary network failures. These improvements are (in part) made possible by leveraging our novel construction of a trapdoor verifiable delay function with strong uniqueness.