Cryptology ePrint Archive: Report 2016/1067

Scalable Bias-Resistant Distributed Randomness

Ewa Syta and Philipp Jovanovic and Eleftherios Kokoris Kogias and Nicolas Gailly and Linus Gasser and Ismail Khoffi and Michael J. Fischer and Bryan Ford

Abstract: Bias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose 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. RandHerd is structurally similar to a BFT protocol, but uses 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. For example, when sharding 512 nodes into groups of 32, our experiments show that RandHound can produce fresh random output after 240 seconds. RandHerd, after a setup phase of 260 seconds, is able to generate fresh random output in intervals of approximately 6 seconds. For this configuration, both protocols operate at a failure probability of at most 0.08% against a Byzantine adversary.

Category / Keywords: distributed randomness, verifiable randomness, randomness beacon, secret sharing, collective authority

Date: received 15 Nov 2016, last revised 22 Mar 2017

Contact author: philipp jovanovic at epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20170322:091634 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]