Scalable Bias-Resistant Distributed Randomness

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.


Publié dans:
2017 Ieee Symposium On Security And Privacy (Sp), 444-460
Présenté à:
38th IEEE Symposium on Security and Privacy, San Jose, California, USA, May 22-24, 2017
Année
2017
Publisher:
New York, Ieee
ISSN:
1081-6011
ISBN:
978-1-5090-5533-3
Mots-clefs:
Laboratoires:




 Notice créée le 2017-08-29, modifiée le 2018-09-13

IEEE S&P'17 Slides:
Télécharger le documentPDF
Publisher's version:
Télécharger le documentPDF
Évaluer ce document:

Rate this document:
1
2
3
 
(Pas encore évalué)