Abstract. We formalize the use of Bitcoin as a source of publicly-verifiable randomness. As a side-effect of Bitcoin’s proof-of-work-based consensus system, random values are broadcast every time new blocks are mined. We can derive strong lower bounds on the computational min-entropy in each block: currently, at least 68 bits of min-entropy are produced every 10 minutes, from which one can derive over 32 near-uniform bits using standard extractor techniques. We show that any attack on this beacon would form an attack on Bitcoin itself and hence have a monetary cost that we can bound, unlike any other construc-tion for a public randomness beacon in the literature. In our simplest construction, we show that a lottery producing a single unbiased bit is manipulation-resistant against an attacker with a stake of less than 50 bitcoins in the output, or about US$12,000 today. Finally, we propose making the beacon output available to smart contracts and demonstrate that this simple tool enables a number of interesting applications. 1
Abstract. We formalize the use of Bitcoin as a source of publicly-verifiable randomness. As a side-effect of Bitcoin’s proof-of-work-based consensus system, random values are broadcast every time new blocks are mined. We can derive strong lower bounds on the computational min-entropy in each block: currently, at least 68 bits of min-entropy are produced every 10 minutes, from which one can derive over 32 near-uniform bits using standard extractor techniques. We show that any attack on this beacon would form an attack on Bitcoin itself and hence have a monetary cost that we can bound, unlike any other construc-tion for a public randomness beacon in the literature. In our simplest construction, we show that a lottery producing a single unbiased bit is manipulation-resistant against an attacker with a stake of less than 50 bitcoins in the output, or about US$12,000 today. Finally, we propose making the beacon output available to smart contracts and demonstrate that this simple tool enables a number of interesting applications. 1
A trustworthy source of randomness is a crucial component of many decentralized and crypto-based application systems, especially blockchain consensus. A decentralized random beacon (DRB) periodically outputs a new source of randomness generated using a distributed technique, such as publicly verifiable secret sharing (PVSS) or distributed verifiable random functions (VRFs). These protocols offer a variety of efficiency versus randomness quality tradeoffs, but guarantee security under a variety of configurations, assumptions, and adversarial models. This article aims to provide a future-proof unbiased decentralized randomness (abbreviated as Funder) via a post-quantum threshold VRF for sustainable proof-of-stake blockchain. We also provide a generic compiler for achieving post-quantum VRF from a classical VRF solution, but our approach makes use of symmetric-key primitives Our novel compiler is validated and evaluated using the ZKBoo and ZKB++ quantum-secure zero-knowledge systems, respectively. The implementation of the proof-of-concept demonstrates that the overheads introduced by our solution are acceptable for real-world deployments even in the present day. In addition, we demonstrate the protocol’s possible application in lottery-based proof-of-stake consensus protocols.
We examine a protocol πbeacon that outputs unpredictable and publicly verifiable randomness, meaning that the output is unknown at the time that πbeacon starts, yet everyone can verify that the output is close to uniform after πbeacon terminates. We show that πbeacon can be instantiated via Bitcoin under sensible assumptions; in particular we consider an adversary with an arbitrarily large initial budget who may not operate at a loss indefinitely. In case the adversary has an infinite budget, we provide an impossibility result that stems from the similarity between the Bitcoin model and Santha-Vazirani sources. We also give a hybrid protocol that combines trusted parties and a Bitcoin-based beacon.
The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed.
We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung.
We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.
Chance plays an essential role in many decision procedures such as lotteries, draws etc. As such procedures are moving on-line, several web services offering randomness have appeared over the last few years. NIST’s randomness beacon, which publishes a sequence of 512 random bytes every minute, unfortunately lacks transparency: the beacon does not eliminate the possibility of an insider attack who knows the outcomes beforehand. We propose an improvement of NIST’s beacon which is publicly verifiable and fully transparent: any outsider who did not witness the bit generation in person but has internet access can convince himself that the beacon acted honestly, provided he can be sure that fresh, independent random bits were contributed to the seed value. Our proposal is based on a novel cryptographic assumption: the existence of functions that are slow to compute even on the fastest supercomputers.
Blockchain systems based on the proof-of-work (PoW) consensus introduce entropy to the system in a natural way due to the randomness of mining. However, for non-PoW consensus (e.g., proof-of-stake and delegated proof-of-stake consensus) blockchain systems, a different approach to introducing entropy, such as the distributed random number generation (dRNG) algorithm, must be established. The dRNG algorithm is one of the key challenges in developing the consensus mechanism, as well as one of the relevant parameters for determining the merit of the consensus mechanism. In this paper, we first derive a publicly verifiable quantum random numbers generation protocol based on the certifiable randomness scheme from any untrusted quantum device, which offers features, such as fairness, no trusted third party, and publicly verifiable. Then, based on verifiable quantum random numbers, we propose a new consensus algorithm. The algorithm selects block proposer and block verification committees for each round using verifiable quantum random numbers, resulting in better randomness, fairness, and efficiency of the entire consensus process. In addition, the new consensus algorithm is not only resistant to adaptive adversary models as well as to collusion attacks, but also requires negligible computation for each user to avoid unnecessary consumption of power resources. Finally, we analyze the verifiable randomness, fairness, liveness, and communication complexity of the consensus algorithm.
Random beacons—services that periodically emit public, unpredictable, and unbiasable random values—underpin blockchains, lotteries, sharding, and cryptographic parameter generation. To remove single points of trust, modern beacons are distributed, but they rest on classical hardness assumptions that quantum computers threaten. Quantum random beacons instead draw unpredictability directly from quantum mechanics and are quantum-safe by construction. Existing systems sit at two extremes: single-device protocols based on random circuit sampling trust one quantum server, while device-independent beacons require entangled measurement stations and do not fit the commercial quantum cloud. We present QuoRand, a quantum random beacon that combines m mutually distrusting quantum servers into one publicly verifiable source of certified randomness through a fully distributed classical protocol with no trusted party. QuoRand introduces (1) a Certified-Randomness Oracle (CRO) abstraction that captures RCS-, LWE-, and low-depth-unitary instantiations uniformly, so all guarantees hold independently of the quantum-advantage assumption; (2) a hash-chained challenge derivation that self-bootstraps each round from the previous output, removing the trusted coordinator of prior designs; and (3) a verifiable-delay-function audit lottery, drawn only after all servers commit, that renders any spoofing server accountable while amortizing verification across rounds. We prove QuoRand is unpredictable and bias-resistant under an anytrust assumption—a single honest server suffices—accountable under an honest majority, and live under partial synchrony, and confirm the soundness-cost trade-off with lightweight simulations.