RandPiper - Reconfiguration-Friendly Random Beacons with Quadratic Communication

A random beacon provides a continuous public source of randomness and its applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (Publicly) Verifiable Secret Sharing (PVSS/VSS). For a system with n nodes in the synchronous communication model and a security parameter κ, we first design an optimally resilient Byzantine fault-tolerant state machine replication protocol with O(κ n2) bits communication per consensus decision without using threshold signatures. Next, we design GRandPiper (Good Pipelined Random beacon), a random beacon protocol with bias-resistance and unpredictability, that uses PVSS and has a communication complexity of O(K n2) always, for a static adversary. However, GRandPiper allows an adaptive adversary to predict beacon values up to t+1 epochs into the future. Therefore, we design BRandPiper (Better RandPiper), that uses VSS and has a communication complexity of O(κ fn2), where f is the actual number of faults, while offering a strong unpredictability with an advantage of only a single round even for an adaptive adversary. We also provide reconfiguration mechanisms to restore the resilience of the beacon protocols while still maintaining quadratic communication complexity per epoch. We implement BRandPiper and compare it against the state-of-the-art practically deployed beacon protocol, Drand, and show that we are always better than or equal to it in performance.