Why Isn’t the GRANDPA Protocol Secure?

Sperax
Sperax
Mar 26 · 4 min read

In previous articles, we’ve discussed other solutions the blockchain ecosystem has proposed to solve the Byzantine Fault Tolerance (BFT) problem: see our articles [Tendermint BFT], [Casper FFG]. In this article, we’ll discuss Polkadot’s GRANDPA. Here we’ll assume knowledge of the Byzantine Fault Tolerance (BFT) problem in distributed computing, and we’ll dive into a description of GRANDPA as a solution to the BFT problem. After a quick discussion of GRANDPA, we’ll discuss possible attacks where GRANDPA might fail, and end with proposals on how those could be solved.

Probabilistic vs. Provable Finality

GRANDPA was a new BFT finality gadget protocol inspired by the Casper FFG protocol. Recall that FFG stands for Friendly Finality Gadget. A Finality Gadget is a protocol to finalize a unique chain after some proposal mechanism.

As you can read on the Polkadot Wiki: “A pure Nakamoto consensus blockchain which runs PoW is only able to achieve the notion of probabilistic finality and reach eventual consensus.” Finality gadgets, such as GRANDPA or Ethereum’s Casper FFG, then give us a stronger guarantee known as provable finality. That’s what gives us the much stronger conclusion that blocks can never be reverted after some consensus protocol agreements have taken place.

Polkadot’s GRANDPA

Polkadot implements BABE as its block production mechanism, via a nominated proof-of-stake (NPoS) system. That means that the system elects a group of validators, through a nomination process. In order to be a nominator, participants stake their tokens as collateral, and that stake gets slashed anytime the nominated validators deviate from the protocol. Nominators are incentivized to participate since they also get paid when their nominated validators play by the rules. Validators that get elected then get equal voting power in the consensus protocol.

With GHOST-based Recursive ANcestor Deriving Prefix Agreement (GRANDPA) as its BFT finality gadget, Polkadot’s relay chain contains two protocols that should handle two different network types. The one we’re interested in is the first protocol, that works in partially synchronous networks, and tolerates ⅓ malicious Byzantine participants. One note here is that GRANDPA 1) depends only on finalized blocks to affect their block production mechanism, and 2) can cast votes simultaneously for blocks at different heights, unlike Casper FFG.

Protocol 1 is designed for Type I asynchronous networks, and will not tolerate network partition or DoS attacks. It is also worth noting that this protocol assumes that after an unknown time GST, the network becomes synchronous.

Each participant stores a block tree produced by BABE, with the genesis block as the root. A participant can vote for a block on the tree, and a block B gets some X number of votes, where X summarizes both B and B’s descendents’ votes. The ⅔-GHOST function g(S) then returns the block B with maximal height such that a set S of votes has a supermajority for B.

The authors then set out to define the possibility of a vote set having a supermajority fro a block: “We say that it is impossible for a set S to have a supermajority for a block B if at least 2t+1 voters either equivocate or vote for blocks who are not descendents of B. Otherwise, it is possible for S to have a supermajority for B”. Furthermore, they claim “a vote set S is possible to have a supermajority for a block B if and only if there exists a tolerate vote set T \subset S, such that T has a supermajority for B”. Several problems arise in practice here:

If we assume that blocks B and C are inconsistent, and yet t malicious voters + 1 honest voter votes for B, and 2t honest voters vote for C, then it is fully possible to have a supermajority for B. Since honest voters will not equivocate, there may not always exist a subset of the vote set S that contains a supermajority, and as a result, GRANDPA cannot achieve the liveness guarantee. We’ll walk through such a scenario next in more detail.

Suppose we maintain the same scenario with blocks B and C as two child blocks produced during some round r — that is, BABE undergoes a fork for this round E_{r-1, 0}, and two child blocks B and C result.

At round r, t + 1 voters (all malicious voters + 1 honest) prevote for B, and the remaining honest 2t voters prevote for C. Thus, for each voter, our g() function outputs one of the ancestor blocks to B, C from a previous round (E_{r-1, i}). Correspondingly, each participant then precommits to that ancestor block. It’s worth noting that even honest nodes on a network could find themselves in this split scenario due to network delay or asynchrony. An honest node could receive block B first, so it votes for B. The other honest nodes receive C first, so they vote for C.

Now, each voter then estimates what the r-1’th round’s ancestor (E_{r-1, i}) might be. Since it is possible for C_{r, i} to result in a voting supermajority for any child of E_{r, i}, the round r is left incomplete, and the process fails.

Even if one could repair the semantic definitions in GRANDPA to resolve the issues discussed here, we could similarly cite the attacks from our discussion of the Tendermint protocol against GRANDPA as well. As a result, we can only conclude that the GRANDPA protocol could not be secure in Type II networks.

To keep up with our latest stories, join us on Telegram, or any of these social channels: TwitterFacebook, and Linkedin.

Sperax

Trusted Infrastructure for Decentralised Economy.

Sperax

Written by

Sperax

Sperax

Sperax

Trusted Infrastructure for Decentralised Economy. Visit us at http://sperax.io/

More From Medium

More on Crypto from Sperax

More on Crypto from Sperax

Sperax Monthly News | March

Apr 3 · 3 min read

More on Crypto from Sperax

More on Crypto from Sperax

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade