Polkadot — An Early In-Depth Analysis — Part Two — How Consensus Works
I would like to thank Alistair Stewart, lead researcher of Polkadot, for verifying the accuracy of the article and answering any questions I had. There are lots of excellent research papers, articles and videos explaining Polkadot, which were extremely helpful in researching the project, and always great to see so much interaction with the community. As with other articles I will provide links that reference to sections, as well as include a list of sources at the bottom of the article for you to look into specific areas in more detail if required.
Part One — Polkadot Overview and Benefits
Part Two — In-Depth look at the Consensus (This article)
Part Three — Limitations and Issues
With the overview covered in part one, (which I recommend reading first if you haven’t already), we will have an in-depth look at the consensus mechanism used in Polkadot. Before that however, we need to explain some of the various roles performed.
Collators
Collators maintain a “full-node” for a particular parachain; meaning they retain all necessary information to be able to author new blocks and execute transactions. Under normal circumstances, they will collate and execute transactions to create an unsealed block and provide it, together with a proof of state transition, to one or more validators responsible for proposing a parachain block. Collators will also watch the progress of block-producing and consensus protocols in BABE (explained later) and build on what they think is the latest relay chain block that will be finalised. Collators do not directly participate in the consensus for the relay chain and therefore never stake DOT. Each parachain will likely have their own token with incentives provided to collators to run on their parachain.
https://wiki.polkadot.network/docs/en/learn-collator
Validators
Validators secure the Relay Chain by staking DOT, validating proofs from collators and participating in consensus with other validators.
These participants will play a crucial role in adding new blocks to the Relay Chain and, by extension, to all parachains. This allows parties to complete cross-chain transactions via the Relay Chain.
A small number of validators are randomly assigned to each parachain and rotate within a given time interval. Validators perform two functions. First, verifying that the information contained in an assigned set of parachain blocks is valid (such as the identities of the transacting parties and the subject matter of the contract). Their second role is to participate in the consensus mechanism to produce the Relay Chain blocks based on validity statements from other validators. Any instances of non-compliance with the consensus algorithms result in punishment by removal of some or all of the validator’s staked DOT, thereby discouraging bad actors. Good performance, however, will be rewarded, with validators receiving block rewards (including transaction fees) in the form of DOT in exchange for their activities.
https://wiki.polkadot.network/docs/en/learn-validator
Nominators
A nominator is a stake-holding party who contributes to the security bond of a validator. They have no additional role except to place risk capital and as such to signal that they trust a particular validator (or set thereof) to act responsibly in their maintenance of the network. They receive a pro-rata increase or reduction in their deposit according to the bond’s growth to which they contribute.
While your DOT are staked by nominating a validator, they are ‘locked’ (bonded). There is an unbonding period of 7 days on Kusama and 28 days on Polkadot before bonded funds can be transferred.
If a validator does not behave properly, they will get slashed and nominators will also lose DOT as well. For attacks this can result in 100% of the stake being slashed, meaning you could lose all of your DOT, so choose wisely.
https://wiki.polkadot.network/docs/en/learn-nominator
Fishermen
fishermen are not directly related to the block authoring process. Rather they are independent “bounty hunters” motivated by a large one-off reward. Fishermen are checking proposed blocks in every part of the network. Ideally, some fishermen focus on one parachain, another group tackles another parachain and a group of fishermen checks relay chain validators. If they find a compromised block, then the creator of the block gets slashed and the fisherman receives a portion of this slashed stake as reward. Fishermen are particularly important when there is a group of validators colluding and proposing a compromised parachain block. Fishermen are required to stake a small amount of DOT to prevent sybil attacks from wasting validators’ time and compute resources.
How Consensus works
Collators are selected by each parachain to produce the next block for the parachain. The collator will watch the progress of block-producing and consensus protocols in BABE and build on what they think is the latest relay chain block that will be finalised. They will collate and execute transactions for the parachain to create an unsealed block and provide it, together with a proof of state transition, to one or more validators responsible for proposing a parachain block.
The number of validators in the relay chain is determined by governance, currently it is 197 validators with the hope to extend this to 1,000. After a certain period of time, referred to as an era, which is currently every 24 hours, an election is held to determine who gets to be a validator using Nominated Proof of Stake (NPoS). Nominators stake their funds against validators they trust and the reward scheme and selection method is designed to have each validator backed by a similar amount of stake.
As the total number of validators is limited that can participate in consensus for performance reasons, a small amount are randomly assigned to validate each parachain.
When the validator receives the unsealed block and proof of validity from the collator, it will check the block follows state transition rules of the parachain. A parachain’s state is stored in a Merkle tree. If some value changes, one can verify the change by only looking at the new values and the paths in the tree that it affects. Based on this property, a validator can verify a state transition without having access to the entire state. It only needs:
- The block (list of state transitions),
- The values in the parachain’s database that the block modifies, and
- The hashes of the unaffected points in the Merkle tree.
This set of information constitutes a proof of validity. Polkadot does not guarantee a valid state; it guarantees a valid state transition. Polkadot validators do not inspect every value in a parachain’s state, only those that are modified, where it ensures that the modification is valid.
If it passes, then it will sign and gossip the proof of validity to the other validators assigned to this parachain.
Once more than half of the assigned validators agree that the block represents a valid transition, they will construct a “candidate recipient”.
A validator constructs a candidate receipt for a parachain block by signing:
- The parachain ID
- The collator’s ID and signature
- A hash of the parent block’s candidate receipt
- A Merkle root of the block’s erasure coding
- A Merkle root of any outgoing messages
- A hash of the block
- The state root of the parachain before executing the block
- The state root of the parachain after executing the block
At this point there are no guarantees that anyone other than the collator and parachain validators have seen the proof of validity block. If these collude then the rest of the parachain network need not have the parachain block and then most collators cannot build a new block and this block’s invalidity may not be discovered. Rather than send the proof of validity block to every validator in the relay chain (hoping to achieve 1000 validators) instead erasure coding is used for performance reasons.
Erasure coding takes the parachain block and proof of validity and creates a set of smaller messages which can be reconstructed to the original message. The number of smaller messages is equal to the total number of validators and the fraction required to reconstruct the message is one-third. As an example, if Polkadot has 1,000 validators and they each get a chunk, then they could reconstruct a block with any 334 of them. In addition, it also sends the candidate recipient to every validator so that it will be included in the Relay Chain transaction queue. This process happens for each parachain simultaneously.
Relay chain blocks are produced using the Blind Assignment for Blockchain Extension (BABE) protocol. BABE assigns validators randomly to block production slots using the randomness generated with blocks. The validator will prove that it assigned to the slot and create a relay chain block which includes the candidate recipients from the various parachains.
The block author will only include candidate recipients that have a parent candidate recipient in an earlier relay chain block to ensure the parachain follows a valid chain. It will also only include those which the validator has an erasure coding chunk, ensuring availability and validity checks can be performed next round
Additional checks are performed by randomly assigned validators. The minimum number of validators to validate a parachain is 14 to ensure sufficient security. So, if 10 validators were assigned to each parachain for the initial check, then a minimum of an additional 4 hidden randomly assigned validators would need to perform additional checks on all the candidate recipients included in the relay chain block that was produced. For parachains which have received reports from fisherman and collators then additional validators will be assigned to verify.
Each of the selected validators will request the erasure coding chunks for each parachain (if 1000 validators, a request would be made for chunks from 334 validators) included in the block and reconstruct the parachain block and proof of validity.
The validator will verify the candidate receipt and the parachain block, and if these checks pass it will sign the candidate receipt for each parachain and announces its signature via gossip to other validators.
Only once relay chain blocks containing candidate receipts that have performed enough checks is it available to be voted on to finalise the chain. Meanwhile this entire process is continuously repeating, and additional relay blocks are added to the relay chain but not finalised yet. As multiple proposers can be chosen to produce blocks for a slot through the randomness of BABE, there may be multiple forks of the relay chain, and transactions could be reverted back at this point if not on the longest chain. As explained in this video
GRANDPA is the finality gadget that is implemented for the Polkadot Relay Chain and works to agree on a chain, out of many possible forks, by following some simpler fork choice rule. Rather than voting on every block, instead it reaches agreements on chains. As soon as more than 2/3 of validators attest to a chain containing a certain block, all blocks leading up to that one are finalized at once.
All parachains in Polkadot follow the finality of the Relay Chain. Future parachain blocks must always build off the candidate receipts that are in the finalized Relay Chain. All of the availability and validity checks should take place in less than one minute from the time a block is authored to the time it is finalized.
Once final, the block benefits from the shared security environment that allows chains to interact with each other in a trustless manner. If an invalid block is detected after it has been finalised then the relay chain would need to be reverted along with every parachain. This is particularly important when connecting to external blockchains as those don’t share the state of the relay chain and thus can’t be rolled back. As explained in this video
Hopefully now with a better understanding of how the consensus mechanism works in Polkadot and the various roles performed, I will cover the limitations and potential issues in part three.
For additional reading please see a list of articles / research papers I found particularly useful whilst researching.
Whitepaper, Overview of Polkadot and its Design Considerations, BABE Research Paper, GRANDPA: a Byzantine Finality Gadget, Video with NEAR explaining Polkadot consensus, Polkadot Wiki, Path of a Parachain block, Block Production and Finalization in Polkadot, Availability and Validity Research Paper, Polkadot’s Data Availability and Validity Scheme, Consensus Part 2 — Grandpa, Consensus Part 3 — BABE, Consensus Part 4 — Security, Slashing Mechanisms, Check Validators / Stake, Censorship, Polkadot Bridges, Polkadot, Substrate and Ethereum, Polkadot — shared security or single point of failure?, Projects building on Polkadot, Polkascan Block Explorer, Polkadot, The Ethereum 2.0 or The Mighty Race
The Network of Networks, Scalable Interoperability to Unleash the True Potential of Blockchain
How the Overledger Network Community Treasury is powering the Network of Networks
