We first design a new Byzantine fault-tolerant state machine replication protocol with $O(\kappa n^2)$ 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(\kappa n^2)$ always (best and worst cases), 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(\kappa fn^2)$, 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.
Category / Keywords: cryptographic protocols / Random Beacons Date: received 19 Dec 2020 Contact author: bhat24 at purdue edu, nxs4564@rit edu, aniket@purdue edu, kartik@cs duke edu Available format(s): PDF | BibTeX Citation Version: 20201221:074909 (All versions of this report) Short URL: ia.cr/2020/1590