In traditional PoS systems, block production participation is dependent on token holdings as opposedto computational power. While PoS developers usually have a proponent for equitable participation ina decentralized manner, most projects propose some level of centralized operation, where the numberof validators with full participation rights is limited. These validators are often seen to be themost wealthy and, as a result, influence the PoS network as they are the most staked. Usually, thenumber of candidates to maintain the network with the necessary knowledge (and equipment) islimited; this can also increase operational costs. Systems with a large number of validators tend toform pools to decrease the variance of their revenue and profit from economies of scale. These poolsare often off-chain.
A way to alleviate this is to implement pool formation on-chain and allow token holders to vote withtheir stake for validators to represent them.
Nominated Proof of Stake
Polkadot uses NPoS (Nominated Proof-of-Stake)as its mechanism for selecting the validator set. It is designed with the roles ofvalidators and nominators, to maximize chainsecurity. Actors who are interested in maintaining the network can run a validator node.
Validators assume the role of producing new blocks, validating parachain blocks, and guaranteeingfinality. Nominators can choose to backselect validators with their stake. Nominators can approvecandidates that they trust and back them with their tokens.
Hybrid Consensus
Polkadot uses what is known as hybridconsensus. Hybrid consensus splits up the finality gadget (GRANDPA)from the block production mechanism (BABE).
This is a way of getting the benefits of probabilistic finality (the ability always to producenew blocks) and provable finality (having a universal agreement on the canonical chain with nochance for reversion) in Polkadot. It alsoavoids the corresponding drawbacks of each mechanism (the chance of unknowingly following the wrongfork in probabilistic finality, and a chance for "stalling" - not being able to produce new blocks -in provable finality). By combining these two mechanisms,Polkadot allows for blocks to be rapidlyproduced, and the slower finality mechanism to run in a separate process to finalize blocks withoutrisking slower transaction processing or stalling.
Hybrid consensus has been proposed in the past. Notably, it was proposed (now defunct) as a step inEthereum's transition to proof of stake in EIP 1011, whichspecified Casper FFG.
Block Production: BABE
BABE (Blind Assignment for Blockchain Extension) is the block production mechanism that runs betweenthe validator nodes and determines the authors of new blocks. BABE is comparable as an algorithm toOuroboros Praos, with some key differences in chainselection rule and slot time adjustments. BABE assigns block production slots to validatorsaccording to stake and using the Polkadotrandomness cycle. The chain’s runtime is required to providethe BABE authority list and randomness to the host via a consensus message in the header of thefirst block of each epoch.
BABE execution happens in sequential non-overlapping phases known as epochs. Each epoch is dividedinto a predefined number of slots. All slots in each epoch are sequentially indexed starting from 0(slot number). At the beginning of each epoch, the BABE node needs to run theBlock-Production-Lottery algorithmto find out in which slots it should produce a block and gossip to the other block producers.
Validators participate in a lottery for every slot, which will inform whether or not they are theblock producer candidate for that slot. Slots are discrete units of time of approximately 6 secondsin length. Because the mechanism of allocating slots to validators is based on a randomized design,multiple validators could be candidates for the same slot. Other times, a slot could be empty,resulting in inconsistent block time.
Multiple Validators per Slot
When multiple validators are block producer candidates in a given slot, all will produce a block andbroadcast it to the network. At that point, it's a race. The validator whose block reaches most ofthe network first wins. Depending on network topology and latency, both chains will continue tobuild in some capacity until finalization kicks in and amputates a fork. SeeFork Choice below for how that works.
No Validators in Slot
When no validators have rolled low enough in the randomness lottery to qualify for block production,a slot can remain seemingly blockless. We avoid this by running a secondary, round-robin stylevalidator selection algorithm in the background. The validators selected to produce blocks throughthis algorithm always produce blocks. Still, these secondary blocks are ignored if the same slotalso produces a primary block from a VRF-selected validator.Thus, a slot can have either a primary or a secondary block, and no slots are ever skipped.
For more details on BABE, please see theBABE paper.
Finality Gadget: GRANDPA
GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement) is the finality gadget that isimplemented for the Polkadot Relay Chain.
The Polkadot Host uses the GRANDPA Finalityprotocol to finalize blocks. Finality is obtained by consecutive rounds of voting by the validatornodes. Validators execute the GRANDPA finality process in parallel to Block Production as anindependent service.
It works in a partially synchronous network model as long as 2/3 of nodes are honest and can copewith 1/5 Byzantine nodes in an asynchronous setting.
A notable distinction is that GRANDPA reaches agreements on chains rather than blocks, greatlyspeeding up the finalization process, even after long-term network partitioning or other networkingfailures.
In other words, as soon as more than 2/3 of validators attest to a chain containing a particularblock, all blocks leading up to that one are finalized at once.
GRANDPA description and implementation
Please refer to the GRANDPA paperfor a full description of the protocol. GRANDPA is implemented as amodule of the Substrate Frame System.
Probabilistic vs. Provable Finality
A pure Nakamoto consensus blockchain that runs PoW is only able to achieve the notion ofprobabilistic finality and reach eventual consensus. Probabilistic finality means that undersome assumptions about the network and participants, if we see a few blocks building on a givenblock, we can estimate the probability that it is final. Eventual consensus means that at some pointin the future, all nodes will agree on the truthfulness of one set of data. This eventual consensusmay take a long time, and will not be able to determine how long it will take ahead of time.However, finality gadgets such as GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement)or Ethereum's Casper FFG (the Friendly Finality Gadget) are designed to give stronger and quickerguarantees on the finality of blocks - specifically, that they can never be reverted after someprocess of Byzantine agreements has taken place. The notion of irreversible consensus is known asprovable finality.
In the GRANDPA paper, it is phrasedin this way:
note
We say an Oracle A in a protocol is eventually consistent if it returns the same value to allparticipants after some unspecified time.
Fork Choice
Bringing BABE and GRANDPA together, the fork choice ofPolkadot becomes clear. BABE must always buildon the chain that GRANDPA has finalized. BABE provides probabilistic finality when there are forksafter the finalized head by building on the chain with the most primary blocks.
In the above image, the black blocks are finalized, and the yellow blocks are not. Blocks markedwith a "1" are primary blocks; those marked with a "2" are secondary blocks. Even though the topmostchain is the longest chain on the latest finalized block, it does not qualify because it has fewerprimaries at the time of evaluation than the one below it.
Comparisons
Nakamoto consensus
Nakamoto consensus consists of the longest chain rule using proof of work as its Sybil resistancemechanism and leader election.
Nakamoto consensus only gives us probabilistic finality. Probabilistic finality states that a blockin the past is only as safe as the number of confirmations it has, or the number of blocks that havebeen built on top of it. As more blocks are built on top of a specific block in a Proof of Workchain, more computational work has been expended behind this particular chain. However, it does notguarantee that the chain containing the block will always remain the agreed-upon chain since anactor with unlimited resources could potentially build a competing chain and expend enoughcomputational resources to create a chain that did not contain a specific block. In such asituation, the longest chain rule employed in Bitcoin and other proof of work chains would move tothis new chain as the canonical one.
PBFT / Tendermint
Please see the relevant section in the Cosmos comparisonarticle.
Casper FFG
The two main differences between GRANDPA and Casper FFG are:
- in GRANDPA, different voters can cast votes simultaneously for blocks at different heights
- GRANDPA only depends on finalized blocks to affect the fork-choice rule of the underlying blockproduction mechanism
Bridging: BEEFY
The BEEFY (Bridge Efficiency Enabling Finality Yielder) is a secondary protocol to GRANDPA tosupport efficient bridging between relay chains (Polkadot and Kusama) and remote, segregatedblockchains, such as Ethereum, which were not built with the Polkadot native interoperability inmind. The protocol allows participants of the remote network to efficiently verify finality proofscreated by validators on the relay chain, i.e. clients in the Ethereum network can verify that thePolkadot network is at a specific state.
Storing all the information necessary to verify the state of the remote chain, such as the blockheaders, is too expensive. In BEEFY, all honest validators sign on a GRANDPA finalized block. Thisreduces the efforts on the light client side, as tracking forks, GRANDPA justifications, etc., is nolonger necessary. Moreover, BEEFY utilizes Merkle Mountain Ranges (MMR) as an efficient datastructure for storing and transmitting block headers and signatures to light clients and the ECDSAsignature schemes (more efficiently verifiable on EVM). Light clients now only have to check if theblock has a super-majority of BEEFY votes by validators.
Overall, BEEFY addresses the limitations of GRANDPA finality for bridges to chains like Ethereum byproviding a more lightweight and efficient finality solution.
For additional implementation details about BEEFY, seethe Polkadot Specification.
Resources
- BABE paper - Theacademic description of the BABE protocol.
- GRANDPA paper - The academicdescription of the GRANDPA finality gadget. Contains formal proofs of the algorithm.
- Rust implementation - The referenceimplementation and the accompanyingSubstrate pallet.
- Block Production and Finalization in Polkadot -An explanation of how BABE and GRANDPA work together to produce and finalize blocks on Kusama withBill Laboon.
- Block Production and Finalization in Polkadot: Understanding the BABE and GRANDPA Protocols -An academic talk by Bill Laboon, given at MIT Cryptoeconomic Systems 2020, describing Polkadot'shybrid consensus model in-depth.
