Paper 2020/1033

RandChain: A Scalable and Fair Decentralised Randomness Beacon

Runchao Han, Haoyu Lin, and Jiangshan Yu

Abstract

We propose RANDCHAIN, a Decentralised Randomness Beacon (DRB) that is the first to achieve both scalability (i.e., a large number of participants can join) and fairness (i.e., each participant controls comparable power on deciding random outputs). Unlike existing DRBs where participants are collaborative, i.e., aggregating their local entropy into a single output, participants in RANDCHAIN are competitive, i.e., competing with each other to generate the next output. The competitive design reduces the communication complexity from at least O(n2) to O(n) without trusted party, breaking the scalability limit in existing DRBs. To build RANDCHAIN, we introduce Sequential Proof-of-Work (SeqPoW), a cryptographic puzzle that takes a random and unpredictable number of sequential steps to solve. We implement RANDCHAIN and evaluate its performance on up to 1024 nodes, demonstrating its superiority (1.3 seconds per output with a constant bandwidth of 200KB/s per node) compared to state-of-the-art DRBs RandHerd (S&P’18) and HydRand (S&P’20).

Note: Defined the unbiasibility. Proposed a mechanism for achieving unbiasibility in RandChain. Refined model, comparisons, security proofs and figures.