Generating Randomness In Blockchain: Verifiable Random Function

Blockchains such as Bitcoin are facing a key problem. How to fairly spread out the decision-making consensus on what pool will win the competition and have the right to add the new block into the blockchain itself.

Bitcoin protocol, which is made by pseudonym person/group Satoshi Nakamoto, solves this problem by a cryptographical quest. Specifically, the search of the random number, the cryptographic nonce. The pool which finds the lowest possible nonce is the winner of the approx. The 10-minute task, enlist the block into the blockchain and then the process of searching a nonce starts again.

But as cryptographers all around the world work day and night and try to find a better solution, that will enable the block to be mined earlier than in 10 minutes, they came up with different kinds of solutions. One of them I would like to describe now in this article also with examples of what projects use it.

Verifiable Random Function (VRF)

Bitcoin's problem with the long mining process (10 minutes per block on average) is more complex than it may seem. Because of that, fewer transactions can be processed in a specific time, because it takes too much time to mine and finalizes the block. At this moment, the Bitcoin network can handle around 7 TPS (transactions per second).

Modern cryptography goes far ahead of this result. The elegant solution is a random draw, which happens in a decentralized manner. This application of a cryptographic lottery is called Verifiable Random Function.

Verifiable random functions (VRFs) were developed by Silvio Micali, Michael Rabin, and Salil Vadhan in 1999 and then later improved by Yevgeniy Dodis and Aleksandr Yampolskiy in 2005.

A verifiable random function is a cryptographic function that processes inputs and produces verifiable pseudorandom output. By using the proof and the public key as inputs, the outputs can be then verifiable without knowing the private key and even without the possibility to find out it.

Given the input value x, the owner of the secret key SK can calculate the value of the function y = F SK (x) and the proof p SK (x).

Using the proof and the public key, anyone can check that the value of y = F SK (x) was actually calculated correctly, yet this information cannot be used to find the secret key. PK = g SK

VRFs provide deterministic precommitments which can be revealed at a later time using proofs which can only be generated by a private key. This is useful for providing a 1:1 mapping of low entropy inputs (e.g. names, email addresses, phone numbers) to some random values which can be committed to in advance, e.g. through a timestamping service such as a transparency log.

Unlike traditional digital signature algorithms, VRF outputs can be published publicly without being subject to a preimage attack, even if the verifier knows the public key (but not the proof). This is useful to prevent enumeration of the names/identifiers in a directory which is using a transparency system.

Source: https://en.wikipedia.org/wiki/Verifiable_random_function

Application of VRF in the blockchain space

We can find some applications of Verifiable Random Functions in the blockchain space. From the already functional blockchains, it's Algorand, Cardano, Polkadot, and in some way Chainlink. For Algorand, the undeniable advantage of using VRF is, that is almost impossible to fork the network due to the network latency like it’s happening with the Bitcoin blockchain, where orphan blocks arise all the time.

From the upcoming projects, we can name Dfinity, which will be kind of a decentralized "internet computer", that aims to reduce the costs of cloud services in today’s internet world. 

Algorand

Silvio Micali, the founder of Verifiable Random Functions, is a respectable person in the computer science world. He also stands behind blockchain project Algorand, which of course uses his invention to the attainment of consensus.

Algorand includes 2 types of nodes. Relay nodes, which serve as network hubs relaying protocol messages very quickly and efficiently between participation nodes, that serves for the proposing new block and following validation process.

The VRF takes a secret key and a value and produces a pseudorandom output, with a proof that anyone can use to verify the result. The VRF functions similar to a lottery and is used to choose leaders to propose a block and committee members to vote on a block. This VRF output, when executed for an account, is used to sample from a binomial distribution to emulate a call for every algo in a user’s account. The more algos in an account, the greater chance the account has of being selected -- it’s as if every algo in an account participates in its own lottery. This method ensures that a user does not gain any advantage by creating multiple accounts.

Source: https://developer.algorand.org/docs/algorand_consensus/

It’s no surprise then, that Silvio Micali used Verifiable Random Functions also for Algorand blockchain to perform secret cryptographic sortition to select block proposal node and the validation committee to propel the consensus protocol. Using VRF made the consensus process very effective, so a high level of scalability is reached. From that moment, also other blockchain projects started to use VRF for the selection of the block proposal node and the committee.

How VRF works in the Algorand Blockchain

Recall that at the core of the Algorand Blockchain is a fast Byzantine Agreement protocol. However, the agreement is not performed between all users in the network. Instead, it is confined to a small randomly chosen committee of users for each round.

Now, each user in the Algorand network holds a secret key SK, while her verification key VK is publicly known to everyone. Each user participating in the Algorand network wants to decide if she should be in the committee to run Byzantine Agreement for block r, she needs to do the following:

Compute Evaluate(SK, Qr) → (Y, ⍴). Here, Qr is a “magic” seed string that is available to everyone in the system.

Check that Y falls within a certain range [0, P] that depends on the stake the user holds in the system.

If the above check passes, then the user holds a proof consisting of values (Y, ⍴) which validates their committee membership for block r. Given (Y, ⍴) and the user’s verification key VK, anyone can verify that Y is a valid unique output and that it falls within a desired range (hence, validating that the user holding VK was indeed chosen to serve on the committee for block r).

Source: https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61

Source: https://developer.algorand.org/docs/algorand_consensus/

Cardano

Cardano Ouroboros PoS uses Verifiable Random Function (VRF) technology, through which the node determines that it has acquired the right to produce the next block. The inputs of the VRF are slot ID (current clot in the epoch), VRF signing key (a unique input), and Nonce (derived from hash made of 2/3 blocks from the previous epoch).

By using VRF, there can be generated a random number that will answer the question for each node just before the potential right to produce a block: “do I now have the right to produce a new block in this time slot”? There is no chance to find out in advance, which node will have the right to produce the next block.

The creation of the block consists, among other things, of signing with a private key (KES key) and entering a verification number. After signing the block, the private key is discarded and a new one is generated. Another cryptographic tool is used, which is called Key Evolving Signature, which allows you to change the private key and keep the same public key. The practical thing about this solution is that there is no need for a large number of messages to be sent between different nodes when concluding a consensus, as we can see with a traditional BFT solution. The node obtains the right to create the block, does so, and then simply promotes the block. The other nodes verify the right to create the new block and also the transactions in it and then accept the block or not.

Chainlink

Chainlink also uses the advantages of VRF, but in comparison to
Algorand or Cardano, it goes even further. Chainlink offers its solution called Chainlink VRF, which utilizes verifiable random functions to generate randomness on-chain. That way it can be used by smart contracts developers as a source of the tamper-proof random-number generator.

It can be used by smart contracts in many applications such as NFTs, in blockchain games, for selection of a representative sample for consensus mechanism and even for generating some duties and resources, like randomly assigning judges to the cases.

For each request, Chainlink VFR will generate a random number and also the cryptographic proof, how it was determined. By publishing and verifying the proof on-chain, it's guaranteed, that it can’t be tampered with or manipulated by anyone including smart contract developers or oracle operators.

How Chainlink VRF works, source: https://blog.chain.link/verifiable-random-functions-vrf-random-number-generation-rng-feature/

Polkadot

Verifiable random functions used in Polkadot are very similar to those used in Ouroboros PoS. The difference is that Polkadots VRF used in BABE consensus doesn't depend on the central clock, but on its past results, which determine present and future results. They use slot numbers as a clock emulator that estimates time.

Validators participate in a lottery in every slot (currently 6 seconds) which will tell them whether they are a block producer candidate. This lottery is based on VRF (Verifiable Random Function) which validators use to compute a random number. This function is also used to prove that the number validator provided was truly valid and it’s thus eligible for a lottery. The validator wins the lottery if v < T where v is the validators random number and T is generated number by the network. After the lottery, several scenarios actually come into play — one validator wins, multiple validators win, and finally a situation where there is no block producer candidate.

Source: https://polkadotters.medium.com/polkadot-architecture-6d150dd1253e

Other solutions than VRF

Besides VRF, there are some other popular approaches to produce randomness in the blockchain space. One of them is RANDAO with its augment VDF (Verifiable Delay Function). But let’s keep this topic for some other articles to describe it.

At this moment, Ethereum is using RANDAO but wants to implement VDF into the protocol in the future.

Final thoughts on VRFs

Proof of Work blockchains struggles in scalability because it takes much more time to mine the block than in PoS blockchains, where to mine the block in the same size as in PoW can take just a few seconds. Because of that, the number of processed transactions per second is lower.

Proof of Stake blockchains (and types derived therefrom) use a different approach and engage randomness as a fair and unpredictable selection of the block validators. That makes them more efficient/effective and scalable. But the security needs to be secured with fair random selection, otherwise, the scalability solution is on the contrary with the level of decentralization.

A cryptographically prooved lottery can use its advantages and pick up a node with the right to create a new block or the committee to vote for the validity of this block.

A verifiable random function is a valuable tool for blockchain developers as it can help solve the problem with true randomness used by election in several different cases as you can see with the examples with Algorand, Cardano, Polkadot, and soon in Dfinity as well. There are also different solutions like the one described with Chainlink VRF with its own on-chain tamper-proof random number generator.

Note: The author is an Algorand ambassador. If you are interested in Algorand and maybe you want to become the leader of your community, check Algorand ambassador program

Title photo: Pixabay.com

References:

• https://en.wikipedia.org/wiki/Verifiable_random_function
• https://developer.algorand.org/docs/algorand_consensus/
• https://medium.com/algorand/algorand-releases-first-open-source-code-of-verifiable-random-function-93c2960abd61
• https://cardanians-io.medium.com/why-not-use-cryptography-for-consensus-fcf68f6f0fb9
• https://blog.chain.link/verifiable-random-functions-vrf-random-number-generation-rng-feature/
• https://wiki.polkadot.network/docs/en/learn-randomness
• https://polkadotters.medium.com/polkadot-architecture-6d150dd1253e