Paper 2018/319

HydRand: Practical Continuous Distributed Randomness

Philipp Schindler and Nicholas Stifter and Aljosha Judmayer and Edgar Weippl

Abstract

A reliable source of randomness is not only an essential building block in various cryptographic, security, and distributed systems protocols, but also plays an integral part in the design of many new blockchain proposals. Consequently, the topic of publicly-verifiable, bias-resistant and unpredictable randomness has recently enjoyed increased attention in a variety of scientific contributions, as well as projects from the industry. In particular random beacon protocols, which are aimed at continuous operation, can be a vital component for many current Proof-of-Stake based distributed ledger proposals. We improve upon existing random beacon approaches by introducing HydRand, a novel distributed protocol based on publicly-verifiable secret sharing (PVSS) to ensure unpredictability, bias-resistance, and public-verifiability of a continuous sequence of random beacon values. Furthermore, HydRand is able to provide guaranteed output delivery of randomness at regular and predictable intervals in the presence of adversarial behavior and does not rely on a trusted dealer for the initial setup. In comparison to existing PVSS based approaches which achieve similar properties, our solution improves scalability by lowering the communication complexity from $ \mathcal{O}(n^3) $ to $ \mathcal{O}(n^2) $. Furthermore, we are the first to present a detailed comparison of recently described schemes and protocols that can be used for implementing random beacons.