Unpredictable Randomness Thanks to Verifiable Random Functions
Overview
Hello and welcome back to our latest comparison article on VRFs and Unpredictable Randomness. This will be a technical deep dive into what VRFs are and why they make the best tool yet to produce randomness in a decentralized system.
Blockchains can be thought of as a global; open and transparent; verifiable and interactive computer. As such, it’s not immediately possible to store a secret within it.
This is bad news because most classic Pseudo Random Number Generators (PRNGs) rely on one party keeping some piece of information secret (often called seed). What’s more is that if this seed is not chosen carefully, the statistical performance of the algorithm can suffer making it more predictable than expected.
In 1999, Micali, Rabin, and Vadhan introduced the concept of Verifiable Random Functions which can be thought of as cryptographic commitments to randomness. Let’s break down what that means.
Table of Content - Unpredictable Randomness
- Verifiable Random Functions
- VRFs in Algorand Consensus Protocol
- Unpredictable Randomness
- Conclusions
Verifiable Random Functions
(non-Verifiable) Random Functions in this context are a family of functions, each characterized by a particular seed, that will return a constant-sized string for any arbitrary input data.
This computation is deterministic which means that a given input will always compute down to the same output.
The goal is that this output string looks sufficiently random and unpredictable to an observer who doesn’t know the seed. This can be used for a coin toss, a lottery, an unbiased random selection…
How would one convince a third party interacting with this Random Function that is being computed honestly?
One trivial way to convince an observer that we always used the same seed, is to reveal it. This is not ideal because then any adversary will be able to predict the output of our function.
In their work Micali, Rabin, and Vadhan, formulated a Verifiable variation of a Random Function. With Elliptic Curve Cryptography, it is today possible to own a secret seed and use it conjunctively with arbitrary data to spit out randomness and a cryptographic proof of computation.
Neither the randomness nor the proof will leak any information about the secret seed and a verifier will be able to use those two pieces of information to be convinced that the process was carried out correctly and honestly.
The verifier can use this zero-knowledge proof to be sure that the seed wasn’t secretly changed to skew the result toward a more favorable outcome for the party executing the function.
By the way, if this Random Function sounds to you like a hash function it’s because, for most intents and purposes, it is! One of the applications of VRFs is to prevent enumeration attacks on hash-based data structures.
A rather handwavy and complementary explanation of this cryptographic tool is that it’s similar to a Digital Signature Scheme. The secret seed is the secret key of the keypair and the public key is what a verifier uses to validate that the expected seed was used.
When you participate in the consensus protocol, one of the things that happen is generating an ephemeral VRF keypair that will be used if your stake is selected in a committee.
A lot more also happens when participating in the consensus protocol to make sure that this process is carried out securely. You can read more about it here.
Going into the security proof of VRFs is far beyond the scope of this article but we leave a couple of resources for the more curious readers.
VRFs in Algorand Consensus Protocol
So far we know about the existence of a function that, thanks to EC Cryptography and a secret seed, can transform arbitrary data into a random string and prove to anyone that this string was generated honestly without revealing anything about the secret seed used in the computation.
We also know that the Algorand consensus protocol uses this function to select the members of a voting committee based on the amount of stake each participant owns.
From the source code we can see that the input of a VRF includes the amount of stake of a participant. This is what each node uses to self-select.
This, yet to-be-verified proof, is then checked against the public component of the VRF key and total amount of money online in the protocol.
Essentially, a user is selected proportionally to their stake and deterministically with the output of the VRF (otherwise, only the highest staker would be selected into the committee).
More details on Chapter 5 of this paper.
This is how Algorand implements a Proof of Stake protocol with a self-selection process, fast verification, and bounded-size committees.
Unpredictable Randomness
The AVM v7 release introduced new instructions in the TEAL language that make it possible to verify VRF directly within a Smart Contract. This means that the use of VRF is not relegated exclusively to protocol-level messages but it’s now a tool that can be used in our decentralized Layer-1.
There are already two very good articles on this topic:
- Randomness on Algorand
- Usage and Best Practices for Randomness Beacon
The TL;DR is that randomness on Algorand needs to be a cryptographic commitment to ensure that whoever holds the secret key does not collude with block-producing committees. It’s not a process that can be started as soon as there’s a need for randomness.
It also needs to be a process where a key holder securely provides the service to an application (or, in the case of the Beacon, to the entire network).
Previous systems that only rely on the “randomness” of a future block should not be considered secure because the hash of a future block, while it is largely chaotic, can be predicted in advance at the protocol level before it ever makes it into the ledger.
Fortunately, VRFs are becoming the primary tool to generate randomness in ecosystems outside of Algorand. That’s great news because it means that more blockchains are using safe randomness for their users.
While this is great, these systems are often much more costly (both algorithmically and monetarily) requiring randomness be generated from scratch specifically for each call.
Also, starting from the output string generating random numbers is expensive because it relies on a sequence of hash functions instead of relying on much statistically sound PRNG algorithms.
Algorand solves this by uploading a single truly random and verifiable seed which is hashed only once based on the use case of that request.
A safer and lighter PRNG algorithm such as PCG can be applied afterward.
Conclusions
VRFs are slowly but surely conquering their place in the blockchain ecosystem. Be that at the protocol level for Algorand or for generating randomness in many technologies, VRFs are truly a game changer.
Algorand shows that it is the best (and cheapest) place to generate randomness because it pairs efficient algorithms with inexpensive on-chain computation.