Paper 2016/1067

Scalable Bias-Resistant Distributed Randomness

Ewa Syta, Philipp Jovanovic, Eleftherios Kokoris Kogias, Nicolas Gailly, Linus Gasser, Ismail Khoffi, 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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
distributed randomnessverifiable randomnessrandomness beaconsecret sharingcollective authority
Contact author(s)
philipp jovanovic @ epfl ch
History
2017-03-22: last of 2 revisions
2016-11-15: received
See all versions
Short URL
https://ia.cr/2016/1067
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1067,
      author = {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},
      title = {Scalable Bias-Resistant Distributed Randomness},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1067},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1067}},
      url = {https://eprint.iacr.org/2016/1067}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.