STROBE: Stake-based Threshold Random Beacons

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

Paper 2021/1643

STROBE: Stake-based Threshold Random Beacons

Donald Beaver, Konstantinos Chalkias, Mahimna Kelkar, Lefteris Kokoris Kogias, Kevin Lewi, Ladi de Naurois, Valeria Nicolaenko, 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.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint. MINOR revision.
Keywords: decentralized randomness beacons consensus blockchain lottery
Contact author(s): don beaver @ gmail com
dbeaver @ fb com
arnabr @ fb com
kostascrypto @ fb com
valerini @ fb com
mahimna @ cs cornell edu
asonnino @ fb com
ladi @ fb com
klewi @ fb com
History: 2021-12-17: received
Short URL: https://ia.cr/2021/1643
License: CC BY

BibTeX

@misc{cryptoeprint:2021/1643,
      author = {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},
      title = {{STROBE}: Stake-based Threshold Random Beacons},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1643},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1643}
}