Polkadot Proof-of-Concept 3: A Better Consensus Algorithm

Jan 21, 2019 · 4 min read

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:

  1. Under good network conditions, GRANDPA can finalize blocks nearly instantly.
  2. Under bad network conditions, like a network partition, GRANDPA can finalize millions of blocks at once when the partitions resolve.
  3. 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.

Polkadot Network

Medium account/ publication of the Polkadot Network

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store