Scalable Bias-Resistant Distributed Randomness
- Speaker : Ewa Syta
- Location : ITE 125
- Date : March 6th, 2018
- Time : 11:00 AM - 12:00 PM
Bias-resistant public randomness is a critical component in many (distributed) protocols. Generating public randomness is hard, however, because active adversaries may behave dishonestly to bias public random choices toward their advantage. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We proposed two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability, and it depends on the pigeonhole principle to ensure output integrity, even for non-random, adversarial group choices. RandHerd implements an efficient, decentralized randomness beacon by using RandHound in a one-time setup to arrange participants into verifiably unbiased random secret-sharing groups, which then repeatedly produce random output at predefined intervals. Our prototype demonstrates that RandHound and RandHerd achieve good performance across hundreds of participants while retaining a low failure probability by properly selecting protocol parameters, such as a group size and secret-sharing threshold. RandHound (512 nodes sharded into groups of 32) produces fresh random output after 240 seconds while RandHerd after approximately 6 seconds, following one-time RandHound setup. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.
Ewa Syta is an Assistant Professor of Computer Science at Trinity College. Previously, she was a Lecturer and Associate Research Scientist in the Computer Science Department at Yale University.