Roll with Move: Secure, Instant Randomness on Aptos

Author: Alin Tomescu respond in singing Zhuolun Xiang

Short Abstract: This is the first on-chain, secure, on-the-fly randomness API for PoS blockchains, available only for Aptos.If you need a random number, just call aptos_framework::randomness::u64_integer(). If you need bytes, call aptos_framework::randomness::bytes().

summarize
In this blog post, we introduce Aptos Roll, a secure on-the-fly randomness API and its underlying cryptographic implementation that will power the next generation of randomized dapps.

At the heart of Aptos Roll are two novel cryptographic constructs: the Weighted Publicly Verifiable Secret Sharing (wPVSS) scheme and the Weighted Verifiable Random Function (wVRF), which have been carefully designed and integrated with the Aptos blockchain protocol.

Let's dive into the core technical details of Aptos Roll!

How to use Aptos Roll
The need for on-chain randomness arises in many applications, such as decentralized games, lotteries, random NFTs, random airdrops, and so on. In addition, many blockchain applications will benefit from randomness to improve fairness, security, and functionality.

Aptos Roll provides these applications with a simple Move API Interfaceto provide unpredictable and unbiased random values on the fly:

• randomness::u64_integer() function: Immediately returns a uniformly sampled 64-bit unsigned integer.
• randomness::bytes(n: u64) function: Immediately return a vector of uniformly sampled bytes of length n.
• randomness::permutation(n: u64) function: immediately returns a uniformly sampled [0, 1, 2, ..., n-1] vector.

A notable feature of this API is the instant delivery: Move smart contracts simply call the API and get randomness immediately. This is more convenient for developers than obtaining randomness from external randomness beacons, which require smart contracts to submit and wait for future random numbers to be generated.

For more details, see our Aptos Improvement Proposal (AIP) 41, which describes this API in depth.

Why it's cool.
Easy-to-Use APIs: Aptos Roll provides easy-to-use APIs that immediately provide randomness to the caller. These on-the-fly APIs are easier to use than solutions based on a commit-and-reveal process (a commit transaction followed by a use transaction).

As secure as the blockchain: Aptos Roll requires no additional trust assumptions and relies solely on the security and availability of the blockchain's Proof-of-Stake (PoS) verifier set. Specifically, randomness on Aptos is neither predictable nor biased against adversaries who do not control interests in 50%.

Novel cryptographic techniques: designing a scalable randomness beacon in a PoS environment requires solving a number of challenges.

• First, Aptos Roll has a novel Weighted Publicly Verifiable Secret Sharing (wPVSS) algorithm that can be run efficiently by each verifier and is aggregatable to help reduce communication overhead.
• Second, Aptos Roll has a communication-efficient aggregatable weighted distributed key generation (wDKG) generation protocol.
• Third, Aptos Roll has a novel weighted verifiable random function (wVRF) that the verifier evaluates each round, and the amount of communication for each verifier is constant rather than linearly related to the shares of the verifier.

contexts
Aptos is a Proof of Stake (PoS) blockchain with a consensus algorithm that runs in two-hour intervals called "epochs". Validators and their equity allocations remain constant within each epoch and change between epoch boundaries. Validators for the next epoch do not come online until the start of the new epoch.

The blockchain also decouples consensus (i.e., the current BFT consensus protocol called Jolteon) from execution (i.e., an optimistic concurrency-controlled execution engine called BlockSTM), where each block is first determined by consensus and then executed to update the blockchain state.

This decoupling is particularly important for on-chain randomness on the network, as it allows the network to first commit to the order of transactions, and then compute and reveal the randomness later.

devise
This approach enables authenticators to jointly generate a shared secret key at the beginning of each epoch via the Weighted Distributed Key Generation (wDKG) protocol.

This shared secret key can only be reconstructed by shares of 50% or more, and can therefore be securely used to compute the randomness seed for each block in the epoch.

The seed is computed by evaluating block-specific unbiased messages (e.g., epoch number and round number) against a weighted verifiable random function (wVRF) under a shared secret key. Finally, this block seed is used to pseudo-randomly derive the randomness of each API call in the block.

At a high level, this summarizes everything you need to know about this randomness method. At a lower level, things are more interesting. Co-generating a shared secret key in a Proof-of-Stake (PoS) setup while evaluating wVRFs under this key frequently and efficiently proved to be an intractable open problem.

Let's dive into some of the interesting details below.

Weighted Distributed Key Generation (wDKG) from Weighted Publicly Verifiable Secret Sharing (wPVSS)
Before the new epoch begins, the validators of the old epoch will cooperate in processing a shared secret key to the validators of the new epoch.

Specifically, each old verifier acts as a dealer: he chooses a random value and shares it secretly with all new verifiers, sending a weighted publicly verifiable secret share (wPVSS) record via reliable multicast. This record will contain encrypted information for each validator that is a secret share of the random value processed by that validator. Importantly, each old validator can issue licenses to the new validator, even though the new validator is not even online yet, since their epoch has not yet begun.

Once each old validator receives a valid record from the secure subset of 66% or more shares, it will aggregate the valid records into a single final aggregated record that will be passed to the consensus. This aggregated record will encrypt the final shared secret key share for each new authenticator, which will be the sum of the random values from 66% or more shares. After agreeing on the first valid aggregation record, the validator completes the wDKG and begins a new epoch.

Finally, when the new epoch begins and the new validator comes online, they can decrypt the share of the shared secret key they have from the aggregation record. At this point, the new validator will be ready to evaluate the wVRF as a secret share by generating randomness for each block in the following way.

One of the key innovations was to design an aggregatable wPVSS with fast transaction times and fast authentication times as well as small record sizes. This is very difficult because we are in a weighted setup where the shared secret key can only be rebuilt by 50% or more shares. To ensure this, the simplest thing to do would be to issue each validator a proportional share of the secret associated with their shares, but this can become quite inefficient. This challenge has been addressed by carefully rounding shares to smaller weights and designing a novel wPVSS that remains efficient while handling thousands of shares. These details will be publicly available in an academic paper in the near future [3].

Weighted Verifiable Random Functions (wVRFs)
Once a shared secret key has been established between the new verifiers, they can cooperate to evaluate the weighted verifiable random function (wVRF) under the secret key. This is an operation that each block performs in order to generate the randomness seed for the blocks mentioned above.

When a block reaches final consensus, each validator will use its decrypted shares from the aggregated wPVSS records to generate its wVRF shares for that block and broadcast them via reliable multicast. Once the wVRF shares have been obtained from 50% or more shares, each validator combines them into (and agrees on) the final wVRF evaluation, which becomes the block seed. Finally, this seed is attached to the block and the block is sent to execution.

Importantly, only 50% or more shares can be used to calculate wVRF assessments, which ensures unpredictability. In addition, the uniqueness of the wVRFs and the confidentiality of the wPVSS program ensures nonprejudice against counterparties that control less than 50% shares.

The key innovation that makes this approach practically feasible is the novel wVRF scheme, which has to be efficiently evaluated for a weighted setup in which the number of shares of each validator is proportional to their weights. Once again, this is a challenging problem.

For example, a simple idea is to assign a fixed weight to each validator and use these weights to evaluate the wVRF. However, this approach leads to a mismatch between the ratio between the validator's shares and its wVRF shares with respect to the share weights, which increases the computational cost and reduces the efficiency. Therefore, an innovative scheme is needed to solve this problem.

To address this problem, we design a novel weighted verifiable random function (wVRF) that uses an innovative approach to the proportionality between weights and shares. This approach optimizes computational efficiency and accuracy by carefully designing the mathematical structure of the wVRF, resulting in an efficient evaluation in the weighted setting.

The details of this wVRF will be made public in an academic paper [4], but here we can summarize the core idea. The scheme uses a method called "segmented weighted sampling" to handle the proportionality between weights and shares. By subdividing each validator's share into smaller shares and weighting these smaller shares according to their weights, we can precisely match the proportionality between share weights and wVRF shares. This approach not only improves computational efficiency, but also reduces computational cost and improves security.

By using this novel wVRF scheme, we can ensure secure and efficient randomness seeding of blocks in a Proof-of-Stake (PoS) setup, thus providing a practical solution to generate unpredictable and unbiased randomness for blockchains.

For example, a simple solution based on state-of-the-art BLS-based VRFs would make the wVRF share size linearly related to the weight of the validator. This would lead to excessive communication overhead per block and slow down consensus.

In contrast, the wVRF scheme reduces the share size from linear to constant, keeping the communication overhead optimal when computing block seeds.

The table below summarizes the differences between Aptos Roll and other blockchains in terms of on-chain randomness, where the Aptos model is the only security solution available for PoS blockchains with instant delivery randomness APIs.

DFINITY relies on the threshold DKG (tDKG) and the threshold VRF (tVRF), rather than a weighted setting. This is because DFINITY assumes a non-proof-of-stake (PoS) security model in which the chain remains secure as long as no more than one-third of the verifiers (and not the stakes) are compromised. This threshold setting is much simpler than the weighted setting of Aptos because the total number of shares can be set to the number of verifiers (e.g., hundreds). In contrast, in Aptos' weighted setting, the total number of shares is proportional to the total equity, and is larger even after rounding (e.g., thousands).

look as if Drand Such external beacons also rely on the implementation of tDKG and tVRF in the server committee. and is therefore easier to implement in a threshold setting. Unfortunately, when a dapp consumes generated random numbers, it must now externally trust the availability and security of the random number beacons. Additionally, random numbers cannot be consumed immediately, but rather through the commit and reveal process, making development more cumbersome and access to random numbers more delayed. The same problem applies to Random Number Beacon Design for AlgorandThe design relies on consuming random numbers from separate external random number beacons.

A very promising approach to random number generation is the use of verifiable delay functions (VDFs).ChiaWith this approach, the advantage is that the unpredictability still holds even if all verifiers are compromised, provided that no one is able to delay more than the initial setupFaster evaluation of VDFs. Unfortunately, this approach cannot generate random numbers quickly because it calculates random numbers based on latency. In addition, the VDF-based approach does not easily provide instant delivery of random numbers because it would require generating a VDF for each block, which is difficult for low-latency blockchains because VDFs are inherently slow. In other words, if blocks are produced more frequently than VDFs, then those blocks will not be able to obtain immediate randomness.

Finally, some randomized designs do not assume realistic threat models and may be subject to the biases or predictions of a single malicious verifier.

existFlowof the design, the verifier votes on the proposed block A and attaches their VRF evaluation, allowing the proposer of the next block B to aggregate the votes and reveal the randomness of block A. This allows bias to be created by strategically not proposing block B, making block A an isolated block.

CeloAllow the proposer of a block to choose randomness, commit to it and reveal it in subsequent blocks. This provides a way to refuse to reveal randomness or to make informed predictions based on expected trades to maximize profits.

existEtherlandsin which each block proposer performs a VRF (Verifiable Random Function) evaluation for the current epoch number. The randomness of that epoch is then defined as the best combination of efforts for the proposer's VRF evaluation. Unfortunately, this method is prone to bias because one or more colluding block proposers can choose not to mix their contributions if they do not like the results. In addition, this method is very slow, as epochs only occur every 6.4 minutes.

a thank-you note
We wish to thank Dan Boneh, Valeria Nikolaenko, and the entire a16z cryptographic research team for reviewing our design and helping to validate it.

Footnotes and references
[1] Aptos Roll relies on rounding each authenticator's entitlement to a smaller weight. This is great for achieving real-world performance, but has implications for confidentiality and availability. Specifically, any rounding scheme leads to rounding errors: i.e., some players may get more secret shares than they deserve, while others may get less. Thus, this effectively transforms a threshold secret-sharing scheme into a ramp secret-sharing scheme, with different secrecy thresholds and different reconstruction thresholds. Typically, the reconstruction threshold is higher. Thus, in order to maintain continuity of activity, the mechanism needs to ensure that any interest of 661 TP3T or more can be reconstructed, while secrecy can withstand any interest of 331 TP3T or less. To minimize the impact of the MEV attack, we chose to raise the confidentiality threshold and set it to 50% while still keeping the reconstruction threshold lower than 66% against 33% adversaries.

[2] Here, verifiers may choose to hold 33% interests because there is no rounding problem as described in [1], but they conservatively wait for more interests to be more resistant to MEV attacks in which verifiers collude to predetermine shared secrets.

[3] Distributed randomness using weighted VRFs, Sourav Das, Benny Pinkas, Alin Tomescu, Zhuolun Xiang; 2024