Polkadot Proof-of-Concept 3: A Better Consensus Algorithm
The third Polkadot proof-of-concept is live. It powers a new testnet, “Alexander,” that implements the brand-new GRANDPA consensus algorithm. GRANDPA (GHOST-based Recursive Ancestor Deriving Prefix Agreement) gives asynchronously, accountably safe finality in a hybrid consensus blockchain.
Here’s three reasons why GRANDPA is the granddaddy of all consensus algorithms:
- Under good network conditions, GRANDPA can finalize blocks nearly instantly.
- Under bad network conditions, like a network partition, GRANDPA can finalize millions of blocks at once when the partitions resolve.
- GRANDPA can finalize a new block regardless of how many blocks have passed since the last one was finalized.
GRANDPA’s secret? It figures out which blocks are in at least ⅔ of nodes’ chains and finalizes them. It can also give different validators different weights, e.g., by the amount staked in the protocol.
In the above diagram, notice how node 1, node 2, and node 3 all have blocks A, B, and C in them. Because nodes 1, 2, and 3 have more than ⅔ of the total stake, blocks A, B, and C are finalized. However, the rest of blocks aren’t finalized because they don’t have enough nodes including them.
GRANDPA was invented by Web3 Foundation research scientist Alistair Stewart and implemented by Thiel Fellow and Polkadot cofounder Robert Habermeier. Alistair is well-respected in the community for having found vulnerabilities in major blockchain consensus algorithms. We sat down with Alistair to discuss how he came up with GRANDPA, and how the algorithm makes Polkadot a stronger platform.
How did you come up with GRANDPA?
Alistair: I spent a few months staring at Byzantine agreement protocols! The key idea was that GHOST on votes, used in Casper The Friendly Ghost, could be used instead of voting on a single block in these protocols to get something where we can formally agree on as many blocks as we already agree on.
Why did Polkadot decide to use GRANDPA?
Alistair: Compared to Byzantine agreement on every block, like Tendermint or BBQ-Birch’s Rhododendron, we can be more decentralized by having more validators, since they can take longer than one block to come to agreement without slowing down block production.
Also block production can survive most of our network going offline, while still normally getting the benefits of Byzantine agreement. One of the design goals of Ethereum 2.0 was to survive WW3 and now Polkadot may also do that!
What does GRANDPA improve?
Alistair: Compared to Casper FFG, the previous solution to a similar problem, GRANDPA has two benefits. Firstly, rather than agreeing only on checkpoints every 64 or 128 blocks as in Casper FFG, we try to agree on the chain everybody already agrees on, regardless of however many blocks that is. Secondly, we have tried to formalize the problem and can prove better theoretical guarantees, especially for liveness.
What’s your background and what are you working on now?
Alistair: I’m a theoretical computer scientist who has recently moved from academia to blockchain. I’m working on formalizing the guarantees we get for problems about the design of Polkadot and other blockchain protocols.
—
For more on how GRANDPA works, read Robert Habermeier’s introduction to GRANDPA and Alistair’s paper on the mechanism, and check out Parity’s first implementation.
A draft of GRANDPA’s formal specification can be found here.
Polkadot is on track for a launch in late 2019. Stay tuned! The next Proof-of-Concept will include the hotly anticipated interchain communication. Polkadot research and design is nearing completion and development is scheduled for the early part of 2019. Simultaneously, Parity Technologies will be finalising the “nominated proof-of-stake” scheme and building in parachain consensus into Substrate, allowing Substrate blockchains to plug in to the global blockchain network that is Polkadot.
Stay informed of Polkadot developments: follow Polkadot on Twitter and join the newsletter.
Want to come up with the next innovation in decentralized systems? Web3 Foundation is hiring research scientists.
