Verifiable random function
A verifiable random function is a pseudo-random function that generates a random value and allows anyone to verify if it was correctly calculated. It combines three functions: a proving function, a verifying function, and an extracting function. A key pair is used to operate these functions.
Prove function: Given a message and a user’s private key as input of the function, a proof is generated.
Verify function: Anyone can verify the proof’s correctness by running this function. The corresponding public key, the proof, and the previous message are taken as input to verify if the proof was correctly computed.
Extract function: The function takes as input the proof and outputs a random value. This random value is the entropy that was extracted from the proof. Thus, the entropy randomly takes a piece of the proof and generates a random value.
VRFs have three security properties:
Pseudorandomness: Despite the output appearing to be random, it is generated with deterministic computation. The same input always results in the same output.
Uniqueness: Only one output is possible for each input and private key.
Public verifiability: Anyone that holds the correspondent public key can verify the correctness of the output.
Albatross implementation of VRF
Elected validators produce random seeds implementing VRFs with the VXEdDSA algorithm. Both micro block producers and macro block proposers generate random seeds. These are stored in the header of every block.
The elected validator selected to produce a random seed takes as input the entropy from the previous random seed as the message of the proof function along with its own private key. This outputs a proof that is the new random seed. Then, any node can run the verify function with the corresponding public key to check the proof’s correctness. Lastly, any node can run the extract function on the random seed to extract its entropy, which is used to generate a random value.
A random value is generated by extracting the entropy from the proof. The random seed can’t be used directly since it’s a controllable value that could be changed by the elected validator. It is essential to extract the entropy from the proof as it ensures security and prevents any node from controlling this value.
The prove and extract functions allow a chain of seeds since generating a new random seed occurs using data from the previous random seed. Every random seed is intrinsically related to the previous one. The following figure demonstrates the chain of seeds within the blockchain.
Random seeds are used in three cases:
Validator slot selection: A new validator slot list is selected at the end of each epoch. The entropy extracted from the random seed is used to select this new list. The block’s proposer takes the active validator set along with the entropy and creates the list.
View slot selection: A new view slot list is created at every block. The block’s producer extracts the entropy from the random seed to shuffle the validator slot list resulting in the view slot list for the block.
Rewards distribution: Elected validators are rewarded at the end of every batch. The rewards are distributed among the elected validators. In every batch, the validator slot list has 512 validator slots. Since we may not be able to divide the reward of a batch by 512 slots evenly, we use the entropy from the random seed to select which elected validator receives the remainder.