Verifiable Random Functions (VRF) are random number generators whose output can be cryptographically verified. A special algorithm provides the proof for VRF’s at a later time then when the random function was executed.
Normally, the output of random number generators isn’t cryptographically checked. The numbers are consumed somehow, perhaps stored, but other users have no way to verify that a certain number was chosen at a certain time, by a certain user, unless they’re informed about the number beforehand.
What happens, then, when you wish to keep the random number secret until a later time, when it can be independently verified by a network of users? You guessed it – a VRF is used.
In a typical VRF, users have a private and a public key pair. They generate the random numbers and sign them using the private key. The rest of the network receives the signatures but not the numbers. Later on, when the secret number is revealed, everyone can verify the signature, thus proving that the number was indeed produced by the holder of the secret key. The number could also be concatenated with a timestamp, to prove it was generated at a certain point in time.
How is this used in Cardano staking?
In our previous article, we introduced how Ouroboros works.
Here we’ll continue our discussion of the Cardano protocol and how its Verifiable Random Function – VRF– is used to choose a random validator every epoch.
When a new staking pool or validating node joins the Cardano network, they must broadcast two public keys along with its registration certificate: a VRF and a KES key. For now we’ll focus on the VRF key. (You may have guessed by now that VRF stands for Verifiable Random Function.)
Keep in mind that everyone on a Cardano network has access to every other staking pool’s VRF public key.
When a Ouroboros epoch is under way, each validating node (staking pool or solo validator) must generate a random hash using the private part of the VRF key.
Each node then keeps this generated number secret until the epoch finishes. Once the epoch is through, everyone exchanges their generated numbers with each other. This forms a list of random numbers.
This random list is then zipped with the ID’s of staking pools. Each random number is associated with a validator ID. The numbers will be the slot numbers for the next epoch and the ID’s are the staking pool ID’s.
During the next epoch each staking pool checks the random number against their own secret key.
If the number matches its own, the node then generates and broadcasts a block.
As you can see, nobody else is able to verify a number, except the holder of the VRF private key which generated the random slot number! This way, competitors don’t know who’s the next node chosen to produce a block. This protects staking pools against DDoS attacks, where they could be taken offline during their slot, so the competitor would inherit the slot and earn the block reward.
Remember the rest of the network has the staking pool’s public VRF key? When a node broadcasts their block, all other nodes can verify that it was that node’s turn to mint the block because they used their private VRF key to sign the random number. All other nodes then verify the signature using the public component of the VRF key.
The Algorand cryptocurrency also uses VRF’s in its protocol.
There is a Java implememtation of Verifiable Random Functions in Algorand’s Github repo which you can check out and study.
There’s a more general and less strict version of Verifiable Random Functions called Weak VRF’s. According to Brakerski et al, Weak Verifiable Random Functions are defined as VRF’s “where pseudorandomness is required to hold only for randomly selected inputs. We conduct a study of weak VRFs, focusing on applications, constructions, and their relationship to other cryptographic primitives”
Verifiable Random Functions Wikipedia Entry
Verifiable Random Function RFC [IETF]
Verifiable Random Functions (VRFs) RFC [IETF]