Scalable Bias-Resistant Distributed Randomness

[Philipp Jovanovic]

Dear all,

We are happy to announce the release of RandHound and RandHerd, two protocols
that enable generation of verifiable, unbiasable, distributed randomness.
The prototype implementation of both protocols is available through the
cothority project. Currently, the protocols only support execution in testbed
environments, i.e. you can run them locally via 'go test' or distributed on
Deterlab. However, we are working hard to fully integrate both protocols into
the cothority framework to make them accessible as a service in every conode.

- Research paper: https://eprint.iacr.org/2016/1067
- Implementations:
+ RandHound: https://github.com/dedis/cothority/tree/randherd/protocols/randhound
+ RandHerd: https://github.com/dedis/cothority/tree/randherd/protocols/randherd

Note: To run RandHerd, make sure to checkout the “randherd" branch of the crypto
library: https://github.com/dedis/crypto/tree/randherd

For your convenience please find the abstract of the research paper below.

-----
Abstract. Bias-resistant public randomness is a critical component required
in many (distributed) protocols. Generating public randomness is hard, however,
because active adversaries behave dishonestly in order to bias public random
choices toward their advantage. Existing solutions do not scale to hundreds
or thou- sands of participants, as is needed in many decentralized systems.
In response, 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 are then repeatedly used
to 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, whereas RandHerd,
after a setup phase of 260 seconds, is able to generate fresh random output
in intervals of approximately 6 seconds. For this configuration, our analysis
indicates that both protocols operate at a failure probability of at most 0.08%
against a Byzantine adversary.
-----

If you have questions or feedback, feel free to reach out to us at any time.

All the best,
Philipp