Roll with Move: Secure, instant randomness on Aptos
By Alin Tomescu and Zhuolun Xiang
tl;dr: The very first secure and instant on-chain randomness API for PoS blockchains, only on Aptos. If you need a random number in Move, just call aptos_framework::randomness::u64_integer(). If you need bytes, call aptos_framework::randomness::bytes().
Overview
In this blog post, we present Aptos Roll, a secure instant randomness API and its underlying cryptographic implementation which will power the next generation of randomized dapps.
At the core of Aptos Roll lie two novel cryptographic constructions, a weighted publicly-verifiable secret sharing (wPVSS) scheme and a weighted verifiable random function (wVRF), carefully co-designed with and integrated into the Aptos blockchain protocol.
Let’s dive into the technical details that lie at the heart of Aptos Roll!
How to use Aptos Roll
The need for on-chain randomness arises in many applications, such as decentralized games, raffles, randomized NFTs, randomized airdrops, and more. Plus, many blockchain applications will benefit from randomness in terms of fairness, security, and functionality.
Aptos Roll provides a simple Move API interface for such applications to access instantly-delivered unpredictable and unbiasable random values:
fun randomness::u64_integer(): u64instantly returns a uniformly-sampled 64-bit unsigned integerfun randomness::bytes(n: u64): vector<u8>instantly returns a uniformly-sampled vector ofnbytes.fun randomness::permutation(n: u64): vector<u64>instantly returns a uniformly-sampled shuffle of the vector[0, 1, 2, ..., n-1].
A distinguishing feature of this API is instant delivery: A Move smart contract simply calls the API and immediately obtains the randomness. This is much more convenient for developers compared to fetching randomness from external randomness beacons, which burden smart contracts with committing to (and waiting for) a future-generated piece of randomness.
For more details, see our Aptos Improvement Proposal (AIP) 41, which describes this API in depth.
Why is it cool
Easy-to-use APIs: Aptos Roll offers an easy-to-use API that instantly delivers randomness to the caller. These instant APIs are much more convenient to use than solutions based on a commit-and-reveal process (a commitment transaction followed by a usage transaction).
As secure as the blockchain: Aptos Roll requires no additional trust assumptions, relying solely on the security and availability of the blockchain’s proof-of-stake (PoS) validator set. Specifically, randomness on Aptos is both unpredictable and unbiasable for adversaries who control less than 50% of the stake.
Novel cryptography: Designing a scalable randomness beacon in the PoS setting requires tackling some hard cryptographic problems.
- First, Aptos Roll has a novel weighted publicly-verifiable secret sharing (wPVSS) algorithm that can be efficiently run by each validator and is aggregatable, which helps reduce communication overheads.
- Second, Aptos Roll has a communication-efficient aggregatable weighted distributed key generation (wDKG) generation protocol on top of it.
- Third, Aptos Roll has a novel weighted verifiable random function (wVRF), which the validators evaluate every round, and has constant communication per validator as opposed to linear in the validator’s stake.
Background
Aptos is a proof-of-stake (PoS) blockchain with a consensus algorithm that operates in periodic two-hour intervals known as epochs. The set of validators and their stake distribution remain fixed within each epoch, and can change across epoch boundaries. The validators of the next epoch do not come online until the new epoch starts.
The blockchain also decouples consensus (i.e., currently a BFT consensus protocol named Jolteon) from execution (i.e., an optimistic concurrency control execution engine named BlockSTM), where each block is first finalized by consensus and then executed to update the blockchain state.
This decoupling is especially important for the network’s on-chain randomness because it allows the network to first commit to an ordering of transactions before computing and revealing randomness later on.
Design
This approach enables validators to jointly generate a shared secret at the beginning of every epoch via a weighted distributed key generation (wDKG) protocol.
This shared secret can only be reconstructed by 50% or more [1] of the stake and therefore can be safely used to compute a randomness seed for every block in that epoch.
The seed is computed by evaluating a weighted verifiable random function (wVRF) under this shared secret over a block-specific unbiasable message (e.g., epoch number and round number). Finally, this block seed is used to pseudo-randomly derive the randomness for every API call in that block.
At a high level, this summarizes everything you need to know about this approach to randomness. At a low-level, things are much more interesting. It turns out, jointly-generating a shared secret in the proof-of-stake (PoS) setting while frequently-and-efficiently evaluating a wVRF under this secret is an open problem that is difficult to solve.
Let’s dig into some of the cool details below.
Weighted distributed key generation (wDKG) from weighted publicly-verifiable secret sharing (wPVSS)
Before a new epoch begins, the old epoch’s validators will collaborate to deal a shared secret to the new epoch’s validators.
Specifically, each old validator acts as a dealer: he picks a random value and secret-shares it with all of the new validators by sending them a weighted publicly-verifiable secret sharing (wPVSS) transcript via a reliable multicast. This transcript will contain, for each validator, an encryption of that validator’s secret share of the random value that was dealt. Importantly, every old validator can deal to the new validators despite new validators not even being online yet, since their epoch hasn’t started yet.
Once each old validator receives a secure-subset of valid transcripts from 66% or more [2] of the stake, it aggregates the valid transcript into a single final aggregated transcript and passes it on to consensus. This aggregated transcript will encrypt, for each new validator, their share of the final shared secret, which will be a sum of random values from 66% or more of the stake. Upon agreeing on the first valid aggregated transcript, validators finish the wDKG and start the new epoch.
Finally, when the new epoch begins and the new validators are online, they can decrypt their shares of the secret from the aggregated transcript. At this point, the new validators will be ready to produce randomness for every block by evaluating a wVRF in a secret-shared manner, as we explain below.
One of the key innovations is designing an aggregatable wPVSS with fast dealing time, fast verification time and small transcript sizes. This is very difficult since we are in the weighted setting where the shared secret can only be reconstructed by 50% or more of the stake. To ensure this, the simplest approach is to issue each validator secret shares proportional to their stake, but this can become rather inefficient. This challenge has been resolved by carefully rounding stakes to smaller weights and devising a novel wPVSS that remains efficient even when dealing thousands of shares. The nitty-gritty details will be publicly-available soon in an academic paper [3].
Weighted verifiable random functions (wVRFs)
Once the shared secret is established among the new validators, they can collaborate to evaluate a weighted verifiable random function (wVRF) under this secret. This is done once per block to produce the block’s randomness seed mentioned above.
When a block achieves consensus finalization, each validator will use its decrypted share from the aggregated wPVSS transcript, produce its wVRF share for that block and reliably-multicast this share. Once wVRF shares from 50% or more of the stake are available, every validator will combine them into (and agree on) a final wVRF evaluation, which becomes the block seed. Lastly, this seed is attached to the block and the block is sent for execution.
Importantly, only 50% or more of the stake can compute the wVRF evaluation, which ensures unpredictability. Furthermore, the uniqueness property of wVRFs together with the secrecy of the wPVSS scheme ensure unbiasability against adversaries controlling less than 50% of the stake.
A key innovation to make this approach practical is the novel wVRF scheme which must be efficient for the weighted setting where the number of shares of each validator is proportional to its weight. Once again this is challenging.
For example, a naive solution based on the state-of-the art BLS-based VRF would have a wVRF share size linear in the weight of a validator. This would lead to excessive communication overheads on a per-block basis and slow down consensus.
In contrast, the wVRF scheme reduces the share size from linear to constant, which keeps the communication overhead optimal when computing the block seed.
Comparison
The table below summarizes the differences between Aptos Roll and other blockchains’ on-chain randomness, with the Aptos model standing out as the only secure solution for PoS blockchains with an instant-delivery randomness API.
DFINITY relies on a threshold DKG (tDKG) and a threshold VRF (tVRF), rather than weighted ones. This is because DFINITY assumes a non-PoS security model where the chain remains secure as long as no more than one third of the validators (rather than the stake) is compromised. This threshold setting is much easier than Aptos’s weighted setting because the total number of shares can be set to the number of validators (e.g., hundreds). In contrast, in Aptos’s weighted setting, the total number of shares is proportional to the total stake which, even if rounded down, will be larger (e.g., thousands).
External beacons like Drand also rely on implementing a tDKG and a tVRF among a committee of servers. As a result, they are easier to implement in the threshold setting. Unfortunately, when a dapp consumes the generated randomness, it must now place external trust in the randomness beacon’s security and availabilty. Furthermore, the randomness cannot be consumed instantly, but via a commit-and-reveal process, which makes development more cumbersome and access to randomness more delayed. The same problems apply to Algorand’s randomness beacon design, which relies on consuming randomness from a separate external randomness beacon.
A very promising approach for producing randomness is via verifiable delay functions (VDFs). This approach, adopted by Chia, the advantage that unpredictability holds even if all validators are corrupted, under the assumption that nobody can evaluate the VDF faster than the delay it was originally set up with. Unfortunately, this approach cannot produce randomness quickly since it is inherently based on delaying the computation of the randomness. Furthermore, VDF-based approaches cannot easily provide instantly-delivered randomness since that would require producing one VDF per block, which is difficult for low-latency blockchains since VDFs are inherently slow. In other words, if blocks are produced more often than VDFs, then those blocks will not have access to instant randomness.
Lastly, some randomness designs do not assume a realistic threat model and are biasable or predictable by a single malicious validator.
In Flow’s design, validators cast votes and attach their VRF evaluations for a proposed block A, allowing the proposer of the next block B to aggregate votes and reveal the randomness of A. This enables bias by strategically not proposing block B, rendering block A an orphan block.
Celo lets the proposer of a block pick the randomness, commit to it and reveal it in a subsequent block. This opens avenues for refusing to reveal the randomness or making informed predictions to maximize profit based on expected transactions in the subsequent block.
In Ethereum, each block proposer evaluates a VRF over the current epoch number. Then, the epoch’s randomness is defined as a best-effort combination of the proposers’ VRF evaluations. Unfortunately, this approach is prone to bias, as one or more colluding block proposers can choose not to mix their contributions in if they do not like the outcome. Furthermore, this approach is very slow, as epochs only happen every 6.4 minutes.
Acknowledgment
We wish to thank Dan Boneh, Valeria Nikolaenko, and the whole a16z crypto research team for reviewing and helping verify our design.
Footnotes and references
[1] Aptos Roll relies on rounding the stakes of each validator into a smaller weight. This is very good for achieving practical performance but has implications on secrecy and availability. Specifically, any rounding scheme will lead to rounding errors: i.e., some players might receive more secret shares than they deserve and other players might receive less. As a result, this effectively turns the threshold secret sharing scheme into a ramp secret sharing scheme, which has a different secrecy threshold and a different reconstruction threshold. Typically, the reconstruction threshold is higher. As a consequence, for liveness, the mechanism needs to ensure any 66% or more of the stake can reconstruct while secrecy holds against any 33% or less of the stake. To minimize the impact of MEV attacks, we chose to make the secrecy threshold even higher, setting it to 50% while still keeping the reconstruction threshold below 66%, to handle a 33% adversary.
[2] Validators could settle for 33% of the stake here, since there are no rounding issues as in [1], but they conservatively wait for additional stake to be more resilient against MEV attacks where validators collude to pre-determine the shared secret.
[3] Distributed Randomness using Weighted VRFs, by Sourav Das, Benny Pinkas, Alin Tomescu, Zhuolun Xiang; 2024
