How does the lottery work on the Cardano network?
In the Cardano network, the lottery determines the winner, who gets the right to mint a new block. A cryptographic primitive called Verifiable Random Function is used to find the winner. Let's explore how this sophisticated mechanism works. Who...
In the Cardano network, the lottery determines the winner, who gets the right to mint a new block. A cryptographic primitive called Verifiable Random Function is used to find the winner. Let's explore how this sophisticated mechanism works.
Who will be the next slot leader
The selection of the node that gets the right to mint the next block must be random. At the same time, the choice of the node must reflect the trust delegated by the other participants in the consensus. In a Cardano network, blocks are minted by pools. ADA holders delegate coins to the chosen pool thereby giving it trust. The higher the stake a given pool has, the more blocks it mints in a given time.
In the Cardano network, time is divided into slots. Each slot lasts 1 second. In each slot, there is a lottery that is performed by each pool autonomously and only needs the information available to the node. The lottery does not require any central control. The protocol is deliberately set to find a winner approximately every 20 seconds. The winner is called the slot leader. Sometimes it can happen that 2 slot leaders win in one round, which doesn't matter because there is a defined rule to decide which block is the right one.
Verifiable Random Function
A cryptographic primitive called Verifiable Random Function (VRF) is used to draw slot leaders. VRF was Introduced by Micali, Rabin, and Vadhan in 1999 and is used in various cryptographic schemes, protocols, and systems.
The owner of the secret key can compute the output value as well as an associated proof for any input value. Everyone else, using the proof and the associated public key (verification key), can check that the output value was indeed calculated correctly. Yet, this information cannot be used to find the secret key.
Let's take a look at how VRF works in general. VRF provides a trio of algorithms:
- Keygen (r) → (VK, SK). In the beginning, it is necessary to generate a verification key (VK) and a secret key (SK) based on random input (r).
- Evaluate (SK, X) → (Y, ⍴). The evaluate algorithm produces a pseudorandom output string (Y) and a proof (⍴) based on two inputs the secret key (SK) and a message (X).
- Verify (VK, X, Y, ⍴) → 0/1. The verification algorithm processes the outputs of the evaluate algorithm, namely outputs string (Y) and a proof (⍴), together with the message (X) and verification key (VK), to produce either 1 or 0. The output is 1 if and only if (Y) is the output produced by the evaluation algorithm with inputs (SK) and (X).
The output Y is pseudorandom and unique. It is impossible to find another output together with a valid proof for a given key pair (VK, SK) and input X. The output Y looks random to any third party that does not see the associated proof ⍴. In other words, to fully verify the output Y and distinguish it from another random output (that might have the same value), it is necessary to have also proof (⍴) that cannot be easily created without knowing the secret key (SK).
Besides other steps, any node that wants to register to produce blocks must initially use the VRF Keygen algorithm to generate VRF keys. This process generates a VRF secret key (which the operator must back up carefully and cannot be revealed) and a verification key (which is used by everyone else to verify that the node has obtained the right to mint the block in a given slot).
During the lottery, nodes (pools) use the VRF Evaluate algorithm every second to see if they have got the right to mint a block. If so, they can create the block and insert the appropriate proof in the block header. It will be described later.
In the Cardano network, only a node that creates the necessary certificate and stores it in the blockchain can produce blocks. Thus, all nodes have all relevant information to validate the blocks. Note that the VRF Verify algorithm does not require a secret key as input. This means that no one other than the owner of the secret key can win the lottery and is able to produce the proof that is necessary to produce a valid block.
Finding the winner
VRF Evaluate algorithm has multiple inputs. Besides others, these include the slot ID for which the lottery is currently running, and ⅔ of all VRF output from the previous epoch, from which a single hash (value) is created. This hash is also called a Nonce. Nonce makes it impossible to compute VRF results too far in advance.
Each node knows its threshold number, derived from the size of stake a given pool has. The bigger the stake, the bigger the threshold. In other words, the threshold number is proportional to the size of the stake, which consists of the operator's stake and the stakes of all delegates. The larger the stake, the more blocks the pool will produce in a given epoch.
The stake of pools can change literally with every block. Ouroboros PoS takes a snapshot of the blockchain every 5 days and takes into account the stake that was active (valid) during the snapshot. The active stake may differ from the current stake (live stake).
Every second, every pool executes the VRF Evaluate algorithm and compares the VRF output (output Y) with the threshold and if output Y is less than the threshold, the pool has got the right to produce a new block.
When the node finds that it has become the slot leader, it produces a new block and inserts VRF proofs in the block header.
Any other node in the network uses the VRF Verify algorithm to verify that the block is valid as far as the block producer is concerned. The VRF proofs contained in the proposed block are used for validation.
In addition to VRF proofs, the block must be signed by a KES key (Key Evolving Signature cryptography). This is the next level of security so that if an attacker were able to somehow break the operation of the VRF, they still don't have the KES keys of operators to sign the blocks.
Advantages of VRF
The advantage of VRF is that blocks can be created more frequently in the network, without the need to consume excessive amounts of energy as in PoW networks. One of the main features of PoW also relates to the lottery. In each round, all pools fight with each other to see who can solve an energy-intensive cryptographic problem faster. In this competition, randomness plays a significant role. Analogous to the Ouroboros PoS, in PoW the larger the hash rate delegated to a given pool, the more likely the pool is to succeed in the lottery. In the Cardano network, the hash rate is replaced by ADA coins.
Another advantage is that the output Y can be used to decide which block is the right one in case a fork occurs (slot battle). Simply take the block whose output Y value is lower. In each round, even in the case of a fork, all nodes know which chain is the correct one. Just apply the longest chain rule and use the block with the lower output Y in the case of a fork.
When a fork occurs in PoW networks, you don't know which block will remain in the blockchain and which will be orphaned until the network manages to add a few more blocks. The longest chain rule is used.
In PoW networks, it is assumed that rewriting historical blocks is very expensive and therefore infeasible. For Ouroboros PoS it is assumed that no one can create the block except the one who owns the necessary private keys. While PoW security depends on the consumption of physical resources, PoS relies more on the honesty of pool operators who do not intentionally back up their keys. At the same time, more emphasis is placed on decentralization, since as decentralization grows, the number of operators holding private keys grows at the same time. If the pool operators, which in aggregate would cover more than half the stakes, honestly delete keys, it is essentially impossible to rewrite the history of the Cardano blockchain.
Conclusion
VRF was created more than 20 years ago so it is a reliable cryptographic tool. In addition to Cardano, it is also used in the Algorand project. At the time of writing, VRF has been running reliably in the Cardano network for 2 years and is involved in the slot leader drawing. In the future, VRF will be used not only for the draw of slot leaders but also for input endorsers. This cannot be achieved with PoW, as the hash rate would have to be split.
Delegate Your Voting Power to FEED DRep in Cardano Governance.
DRep ID: drep12ukt4ctzmtf6l5rj76cddgf3dvuy0lfz7uky08jfvgr9ugaapz4 | We are driven to register as a DRep by our deep dedication to the Cardano ecosystem and our aspiration to take an active role in its development, ensuring that its progress stays true to the principles of decentralization, security, and community empowerment.DELEGATE VOTING POWER!
