On-Chain Randomness Fulfillment via Verifiable Random Functions

April 15, 2024 - 9 min read

Introduction

On-chain verifiable randomness is a crucial resource in Web3 applications. This is especially the case with online lotteries, blockchain gaming, NFT crafting and minting, leader selection, resource allocation, and much more.

In our Supra dVRF blog, we stated that verifiable randomness, which leads to the generation of a truly random number, is:

Unpredictable: No one can compute the number ahead of time.
Unbiasable: The random number cannot be biased to make specific numbers more likely to appear than others (e.g., the number is always even or always odd).
Publicly Verifiable: Anyone can verify that the random number is correctly generated.

In this blog we discuss how to capture the above three properties with regards to on-chain verifiable randomness. Then we’ll dive deep into the Verifiable Random Function (VRF)-based randomness services and discuss the randomness services of Supra distributed VRF (dVRF) and Chainlink VRF.

On-Chain Verifiable Randomness

Cryptographic techniques – like publicly verifiable coin-tossing, verifiable random functions, or randomness beacons that provide publicly verifiable output – can be used to generate randomness that is unpredictable and can be publicly verified by anyone. If the underlying randomness source is verifiable, then public verifiability can be easily realized on blockchains by leveraging the capabilities of smart contracts. However, the property of unbiasability is hard to achieve in blockchain settings.

In a previous blog, we demonstrated that existing randomness generation services like Pyth-VRF fail to ensure unbiasable randomness. This stems from the fact that a malicious user is able to preemptively obtain the output and can opt to discontinue the request fulfillment if the output is unfavorable, thus effectively biasing the output as the output would not ultimately be posted on-chain resulting from the malicious user’s preemptive knowledge.

Thus, the liveness property of VRF services is necessary to ensure the unbiasability of the output. We also desire that each randomness request is fulfilled with a unique random output, regardless of input, otherwise an adversarial user can replay an already fulfilled request to generate the same randomness. To formalize this idea of on-chain unbiasability we require:

Availability/Liveness: Once a randomness request gets added on-chain it will always be fulfilled, i.e. the output will be generated, even if the client chooses to discontinue the process.
Unbiasable Random Output: The output of a fulfilled request is random and fixed/immutable once it is added on-chain. Two different requests with the same input will also yield random and independent outputs.

To meet all of the above requirements, most randomness services require two on-chain transactions: a randomness request transaction and a randomness fulfillment transaction.

What is an on-chain transaction?

Blockchains execute code via programs called smart contracts. When a smart contract is executed, on-chain transactions are recorded on the blockchain and are visible to all participants in the network, providing both transparency and immutability.

Architecture of Randomness Service

Smart contract execution is deterministic in nature, and blockchains are likewise inherently deterministic. So, we require that there is a randomness provider, like Supra or Chainlink, that uses cryptographic techniques to generate randomness off-chain which is publicly verifiable on-chain. This randomness is used to fulfill randomness requests for on-chain consumption. At Supra, we have analyzed the existing services and performed an extensive analysis here.

First, users invoke randomness on-chain via a request transaction. Next, the output randomness is generated by the provider. Then the fulfillment transaction verifies the output randomness and records it on-chain corresponding to the request. Anyone can view the randomness request and verifiable output on-chain and verify the proof personally, exemplifying that the randomness was generated by the provider with fidelity. We describe the architecture of a randomness service in Fig. 1 and define each stage as follows.

Setup: The randomness provider runs a setup phase with the randomness service smart contract (SC). For randomness services, such as Supra and Chainlink, it can be assumed that the smart contract is hardcoded with the public key of the provider.

Request: Next, the user requests randomness by submitting its input x to the user smart contract (SC). The randomness request is registered with the service SC and a unique request-id, denoted reqid, is assigned to this user request. We assume that the request transaction stores the necessary user details that are required for computing the randomness off-chain along with the necessary details required for the protocol. Note that, for the sake of simplicity, we do not delve into the details of the user smart contract and consider it as part of the user protocol.

Fulfill: To fulfill a user request (indexed by reqid) that has been registered on-chain, the provider reads the request details corresponding to reqid from the request transaction. Employing an adequate incentive mechanism ensures that it will be read within a reasonable time frame. The providers then use the request details, along with their secret keys, to generate the random output and a proof of correctness (rand, proof). The provider forwards (rand, proof) to the service SC. The service SC verifies the proof with respect to reqid and then stores it on-chain and forwards (reqid, rand, proof) to the user SC. The user SC verifies proof and uses the randomness for Web3 applications.

The unbiasability of the output is guaranteed by the off-chain randomness provider. The output is unpredictable to the user since the secret key of the provider is kept hidden. Finally, the output rand is also publicly verifiable (with respect to the input) due to the associated proof. The liveness of the protocol is ensured from the two transactions as we discuss next.

Why Two On-Chain Transactions?

The fulfillment transaction is necessary to ensure that the output is available on-chain. Removing this transaction (and replacing it with a direct message from the randomness provider to the user) enables a malicious user to selectively reject the output if it is unfavorable. In such a case, an external entity cannot determine whether the user behaved maliciously (by rejecting the output) or the fulfillment is still being processed. To prevent such a “denial of output attack” we need the fulfillment transaction to ensure the liveness of the randomness service, irrespective of the user’s behavior. Recall that, liveness of the output is one of the two requirements for on-chain unbiasability.

The request transaction verifies that the randomness request is generated by a user that is registered with the blockchain. Removing the request randomness transaction would allow a malicious user to launch an impersonation attack by making multiple requests that are unlinkable. Subsequently, it may just select one output over others according to the preference diminishing unbiasability. The first transaction also prevents a malicious user from impersonating another user and requesting randomness on their behalf.

We would like to note that the requirement for the first transaction can be obviated by deploying a separate public key infrastructure (PKI) where each user has to be registered (e.g. via KYC) and the user’s unique public verification key must be available to the provider. This prevents impersonation attacks and prevents users from launching multiple unlinkable requests. However, this would severely affect the scalability of the provider’s protocol since each user would have to be registered and their public keys made accessible by the provider during output evaluation.

Verifiable Random Function-Based Providers

Next, we will demonstrate how to instantiate the randomness provider algorithm in Figure 1 based on the primitive of VRF. First, we’ll outline the verifiable random function primitive before distinguishing between Supra dVRF and Chainlink VRF services.

Verifiable Random Function

VRFs are cryptographic objects that, provided a given input and a randomly chosen secret key, produce outputs that are “as good as random’’ (technically, called pseudorandom). This means that as long as the secret key is kept hidden, the output is unpredictable, pseudorandom (or unbiasable) and is publicly verifiable given the VRF public key.

It is important to emphasize that even a short secret key (i.e. a 128-bit key) can produce many pseudorandom strings, one for each input. Therefore, the challenge boils down to keeping the secret key secure. In Web3, computing randomness on-chain while maintaining a secret key becomes rather challenging and costly. Therefore, the best approach is to compute the VRF off-chain and subsequently verify its legitimacy on-chain via cryptographic proof.

So, in Figure 1 the randomness provider generates the public key in the Setup phase and posts it to the service smart contract. In the off-chain randomness generation phase, the provider evaluates the VRF on the request input to obtain the output rand and proof. The cryptographic proof verifies the legitimacy of the output with reference to the VRF evaluation on the input. This is uploaded and verified on-chain as part of the fulfillment.

Analysis of Existing VRF-Based Providers

Next, we discuss the similarities and differences between two VRF-based providers – Supra dVRF and Chainlink VRF.

Chainlink VRF

First of all, the Chainlink server generates the public key and secret key for the VRF. The Chainlink server then posts the public key on the different blockchains on which users can request randomness to Chainlink. The secret key is stored by the Chainlink server.

A user requests randomness by submitting a request transaction. Once the request is confirmed on-chain, the Chainlink VRF server reads the randomness requests from the source blockchain and verifies the request. Once the verification succeeds, the VRF server evaluates the output by running the elliptic-curve based VRF on it and then initiates the fulfillment transaction on the output.

The fulfillment transaction verifies the well-formedness of the VRF input using on-chain commitments, verifies the VRF output and then appends the output to the destination blockchain. The Chainlink VRF server also has to keep track of different blockchains to read the requests and initiate the fulfillment requests.

Moreover, to the best of our knowledge, Chainlink VRF is not distributed, and ultimately cannot be distributed efficiently. The cryptographic proof (over elliptic-curves) in the distributed version of Chainlink cannot be made compact and grows with the number of servers. Meanwhile, the cryptographic proof (relying on BLS) in Supra’s dVRF is constant and independent of the number of VRF servers.

Supra dVRF

Decentralization is one of the core ethos in the Web3 world. It avoids a single point of failure and distributes the centralized trust assumption among a bunch of parties. The Supra dVRF follows this same principle to distribute the VRF process among a clan of VRF server nodes.

First, VRF servers generate the VRF public key using a distributed key generation that leverages a secure secret-sharing mechanism. In this case, the secret key remains hidden from the Supra servers, and each server only possesses a secret, partial share of the secret key. The aggregated public key is posted on the different blockchains on which users can request randomness from the Supra dVRF.

A user requests randomness by submitting a request transaction. Once the request gets confirmed on-chain, a committee of relay nodes reads the randomness requests from the source blockchain, verifies the request, and sends it to the Supra VRF clan. Supra servers evaluate the output by running the distributed GLOW-DVRF (based on BLS signatures) on it, and then send the output to relay nodes. The relay nodes verify the output and then initiate the fulfillment transaction on it.

The fulfillment transaction verifies the output and then appends it to the destination blockchain. The transaction assumes the VRF input is correct since it is already vetted by relay nodes and Supra servers and, unlike Chainlink, Supra removes the additional cost of verifying the VRF input as part of the fulfillment transaction. So, the transaction only verifies the VRF output and then appends it to the destination blockchain.

With Supra’s architecture, different relay nodes are assigned to keep track of randomness requests that are generated on different blockchains. This removes the requirement of Supra servers to be blockchain-aware, unlike Chainlink servers. Hence, onboarding a new Supra server is significantly easier. A more detailed comparison between Chainlink VRF and Supra dVRF can be found here.

Conclusion

In this blog, we discussed the requirements for deploying verifiable randomness services over different blockchains. We argued why a single on-chain transaction fails – either it allows impersonation or it breaks liveness and hence unbiasability.

We introduced the two-transaction system – one for initiating requests and the other one for fulfilling the request. Then, we showed that the existing randomness services of Chainlink VRF and Supra dVRF work according to this two-transaction architecture. Moreover, Supra dVRF supports randomness generation in a distributed/decentralized fashion, which aligns with the core ethos of decentralization in the Web3 world.

The Chainlink protocol requires the trusted VRF server to be blockchain-aware. In the case of Supra, the dVRF requires a committee of relay nodes that are blockchain-aware. These incur certain costs in terms of either requiring expensive network usage (Chainlink) or relying on a committee of trusted free nodes (Supra). In the next blog, we will discuss how to remove these assumptions by relying on randomness beacons.