Cryptology ePrint Archive: Report 2021/1643

STROBE: Stake-based Threshold Random Beacons

Donald Beaver and Konstantinos Chalkias and Mahimna Kelkar and Lefteris Kokoris Kogias and Kevin Lewi and Ladi de Naurois and Valeria Nicolaenko and Arnab Roy and Alberto Sonnino

Abstract: We revisit decentralized random beacons with a focus on practical distributed applications. Decentralized random beacons (Beaver and So, Eurocrypt 1993) provide the functionality for $n$ parties to generate an unpredictable sequence of bits in a way that cannot be biased, which is useful for any decentralized protocol requiring trusted randomness.

Existing beacon constructions are highly inefficient in practical settings where protocol parties need to rejoin after crashes or disconnections, and more significantly where smart contracts may rely on arbitrary index points in high-volume streams. For this, we introduce a new notion of history-generating decentralized random beacons (HGDRBs).

Roughly, the history-generation property of HGDRBs allows for previous beacon outputs to be efficiently generated knowing only the current value and the public key. At application layers, history-generation supports registering a sparser set of on-chain values if desired, so that apps like lotteries can utilize on-chain values without incurring high-frequency costs, enjoying all the benefits of DRBs implemented off-chain or with decoupled, special-purpose chains. Unlike rollups, HG is tailored specifically to recovering and verifying pseudorandom bit sequences and thus enjoys unique optimizations investigated in this work.

We introduce STROBE: an efficient HGDRB construction which generalizes the original squaring-based RSA approach of Beaver and So. STROBE enjoys several useful properties that make it suited for practical applications that use beacons:

- history-generating: it can regenerate and verify high-throughput beacon streams, supporting sparse (thus cost-effective) ledger entries;

- concisely self-verifying: NIZK-free, with state and validation employing a single ring element;

- eco-friendly: stake-based rather than work based;

- unbounded: refresh-free, addressing limitations of Beaver and So;

- delay-free: results are immediately available.

Category / Keywords: cryptographic protocols / decentralized randomness, beacons, consensus, blockchain, lottery

Date: received 16 Dec 2021

Contact author: don beaver at gmail com, dbeaver at fb com, arnabr at fb com, kostascrypto at fb com, valerini at fb com, mahimna at cs cornell edu, asonnino at fb com, ladi at fb com, klewi at fb com

Available format(s): PDF | BibTeX Citation

Version: 20211217:142755 (All versions of this report)

Short URL: ia.cr/2021/1643


[ Cryptology ePrint archive ]