Paper 2020/1033

RandChain: Decentralised Randomness Beacon from Sequential Proof-of-Work

Runchao Han and Jiangshan Yu and Haoyu Lin

Abstract

Decentralised Randomness Beacon (DRB) is a service that generates publicly verifiable randomness. Constructing DRB protocols is challenging. Existing DRB protocols suffer from either strong network synchrony assumptions, high communication complexity or various attacks. In this paper, we propose RandChain, a new family of (permissioned) DRB protocols. To construct RandChain, we first introduce Sequential Proof-of-Work (SeqPoW), a Proof-of-Work (PoW) variant that is sequential, i.e., the work can only be done by a single processor. In RandChain, nodes jointly maintain a blockchain, i.e., a chain of blocks, and each block derives a random output. Each node derives a unique SeqPoW puzzle from the last block and its identity, and keeps mining, i.e., solving the SeqPoW puzzle, to append a block to the blockchain. This makes mining non-parallelisable. RandChain applies Nakamoto consensus so that nodes agree on a unique blockchain. While inheriting simplicity and scalability from Nakamoto consensus, RandChain produces strongly unpredictable randomness and remains energy-efficient and decentralised. RandChain does not require nodes to provide local entropy, thus giving no opportunity to bias randomness. Solutions of SeqPoW puzzles are unpredictable, so nodes cannot predict randomness. As each node can use at most a single processor for mining, RandChain remains energy-efficient. SeqPoW mining can only be accelerated by increasing processors’ clock rate, which is bound by processors’ voltage limit. Therefore, powerful nodes can only achieve limited speedup compared to normal nodes, leading to a high degree of mining power decentralisation.