CryptoDB
Alice in Randomland: How to Build and Use Distributed Randomness Beacons
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Distributed randomness beacons allow a number of parties to periodically obtain fresh random outputs in such a way that they can verify these outputs are correctly generated while being able to prove to any third party that a given random output was previously obtained at a certain period. These schemes find a number of real world applications towards achieving anonymity and privacy in many scenarios as well as being central building blocks of consensus protocols. The emergence of provably secure Proof-of-Stake blockchains and other decentralized applications has sparked a renewed interest in constructing more efficient and robust randomness beacons, yielding a multitude of constructions based on different techniques, ranging from traditional secret sharing to timing based primitives such as verifiable delay functions. In this talk, we survey recent results on randomness beacons, focusing on our results covering a wide range of building blocks and their respective assumptions: Publicly Verifiable Secret Sharing (e.g. ALBATROSS), Verifiable Random Functions (e.g. Ouroboros Praos) and Time-lock Puzzles (e.g. CRAFT). We classify distributed randomness beacon protocols in terms of their security guarantees, their bias (or lack of thereof) and their complexity. We cover randomness beacons based on traditional techniques such as threshold schemes (i.e. secret sharing and threshold signatures) and verifiable random functions, as well as protocols based on timed primitives such as verifiable delay functions (e.g. Boneh et al.) and time-lock puzzles. We present basic constructions of randomness beacons based on each of these primitives, pointing out the scenarios where each has a (dis)advantage. Moreover, we discuss the communication channel synchronicity assumptions (and consensus guarantees) under which these beacons can be proven secure. We aim at informing the real world cryptography community of the scenarios where each beacon may perform better, as well as potential pitfalls in employing each of them. Towards this goal, we also discuss the necessary setup assumptions and procedures needed for each construction and how these fit into threat models considered in practical applications such as different flavors of Proof-of-Stake blockchain protocols, which crucially rely on randomness beacons for their security. We also strive to describe the optimistic randomness beacon constructions in our recent works (ALBATROSS and CRAFT), which achieve much better concrete performance than current approaches in case parties behave honestly, only falling back to more expensive procedures/techniques in case it is necessary to recover from cheating. Finally, we identify directions for future work on real world randomness beacons aiming at improving their efficiency and/or providing novel useful features. |
| Video: | https://youtu.be/3JeYu2xoVtE?t=2144 |
BibTeX
@misc{rwc-2021-35547,
title={Alice in Randomland: How to Build and Use Distributed Randomness Beacons},
note={Video at \url{https://youtu.be/3JeYu2xoVtE?t=2144}},
howpublished={Talk given at RWC 2021},
author={Ignacio Cascudo and Bernardo David},
year=2021
}