A 10-Minute Guide to Consensus Protocols, by Analogy to an Imaginary Senate

Or, how to explain consensus to my dad.

With the launch of Avalanche, it seems like work has only amplified. Projects after projects, integrations after integrations. Still, among the craziness, I wanted to take a bit of time to do something I haven’t done in a very long time: write concisely about topics that I happen to know a thing or two about.

Today’s topic is consensus. There’s been at this point probably hundreds if not thousands of blog posts written about this topic. I’ve read a bunch myself, and wasn’t impressed.

“Everything should be as simple as possible, but not simpler”. The blog posts, tweet-storms, etc., I’ve read have been jumbles of ideas, trying to juggle multiple designs without a cohesive — or “unifying” theory — of consensus. There’s far too much complexity, likely due to a lack of subject mastery. To that end, I shall create a “unifying” theory of consensus through a simple, yet arguably pretty accurate, metaphor: that of a bunch of senators trying to pass a bill in a parliament. And I shall choose the clearly superior method of publishing to academic papers: a blog post on Medium. In this guide I’ll cover PoW, PoS, sharding, and whatever comes along. If my dad can understand this post, while remaining scientifically accurate, I will have achieved my goal.

1. Setting the Stage

Because we want to keep it really simple, we’re going to learn about consensus by now never saying the word consensus ever again. We can’t define a word by using the word itself in the definition.

Instead, we’re going to focus on the following task at hand: getting a bunch of senators to pass a bill. First, we need a few ground rules, which are artificially imposed on the senators a) for simplicity and b) out of a need to make them “behave” like computers.

1. Rule #1: Each senator must vote yay or nay to a bill. Also, each senator has exactly 1 vote.
2. Rule #2. A senator must be present on the senate building in order to vote. If they aren’t there, they can’t vote for or against the bill. It’s show up or gtfo.
3. Rule #3: There’s at most 100 senators. This is random, but I chose it because it makes the math simple.
4. Rule #4: Whenever a bill is proposed, there’s at least 1 senator on the floor available to vote on the bill, AND that senator is willing to vote yay or nay on it.

Now, through this setup, we’re going to do the following: get a bill through the floor. That’s the goal. How we get there will be subject to the specific design of each algorithm. Naturally, there are three outcomes:

1. The bill is approved.
2. The bill is rejected.
3. There’s no decision, and we just filibuster. At that point, we pack our bags and try again tomorrow.

In my words above there is a few subtle, but deeply consequential, implications:

1. I never said anything about what either “approved”, “rejected”, or “no decision” means. Why? because it is subject to interpretation. Said in nerd lingo, it is subject to the specific definition that the target algorithm uses. This is quite important to understand right now. Those that aren’t experts in this area typically understand each of those as having unique and universal definitions (typically those subsumed by Satoshi). However, this is clearly not the case, as there are other definitions. For example, the algorithm that the U.S. government chooses to pass bills (very roughly [1]) says that if 2/3 of the senate (in this case 67 of the 100 senators) votes for a bill, they can overwrite the President even if he or she vetoes it. In that sense, “approve” means that 2/3 of the senate wants to pass the bill. Furthermore, unlike in Bitcoin, it is also perfectly normal and acceptable for the bill to be filibustered. Weird, right?
2. The framework above is universal. This means that the simple process I’ve outlined above is sufficient to describe every single consensus protocol, including L1’s and L2’s. Pretty neat.

Ok, so let’s get started.

2. Synchronous protocols, proof-of-work, Bitcoin, Ethereum, and much ado about nothing.

Here’s how Bitcoin works:

1. Step 1: A bill is proposed.
2. Step 2: Senators have 10 minutes to vote on the bill.
3. Step 3: At the end of the 10 minutes, there’s 3 outcomes:

• Approve: pass the bill as long as 51% of whoever is on the senate floor at the time of the bill being proposed votes “yay”.
• Reject: reject the bill as long as 51% of whoever is on the senate floor at the time of the bill being proposed votes “nay”.
• Filibuster: not possible. Why is filibuster not possible in Bitcoin’s senate? Because of one key part: “51% of whoever is on the senate floor at the time of the bill being proposed votes”. So, as long as at least 1 senator is on the floor to vote, which is something that we assumed per the rules above, we will have a vote.

4. Step 4: Go back to step 2, and consider the bill irrevocable once you go through steps 2 and 3 for a minimum of 6 times.

That’s literally Bitcoin. Don’t @ me on Twitter, this is how it works. For Ethereum, change the 10 minutes to 15 seconds, and the 6 to like 35. Something like that.

A few observations:

Observation #1. So where does the proof-of-work come into play? Irrelevant for any of this. Truly, it is. Proof-of-work becomes relevant in the pre-processing step, in the part where we define on who a senator is. In PoW-case, it’s someone with a bunch of hashpower. The more hashpower, the more the voting power.

Observation #2. This one’s a doozy, but it’s one of the most interesting outcomes from distributed systems. Synchronous protocols, such as Bitcoin and Ethereum, always make progress. But, they do so at a massive tradeoff: safety. Remember that when I said there’s really 100 senators, but Bitcoin could make progress with a single one being present every 10 minutes?

That’s pretty bad. Here’s how: only one senator is on the floor; bill arrives; senator keeps voting “yay” every 10 minutes; an hour goes by, bill passes; next day 99 other senators come in, they can easily overwrite the 1 senator.

Pretty bad. This is what’s know in literature as a partitioning attack, which is what happens when synchronicity is violated. Bitcoin is only safe if it is guarantee that all miners in the network are connected by at worse a 10 minute delay.

3. Asynchronous protocols, PoS, and why a filibuster is good.

I’m going to disappoint a whole lot of you. There’s nothing special about this class of protocols besides the fact that instead of there being any majority of senators to there being the majority of senators. In particular, in these protocols, we will ONLY make progress if some large majority of the 100 senators are actually voting on the bill. That’s it. The PoS component doesn’t matter.

Here’s how, for example, PBFT works:

1. Step 1: A bill is proposed.
2. Step 2: Senators can vote as soon as they want to.
3. Step 3: As soon as a supermajority of the votes come in, there’s three outcomes:

• Approve: pass the bill as long as a supermajority of the 100 senators vote “yay”.
• Reject: reject the bill as long as a supermajority of the 100 senators vote “nay”.
• Filibuster: possible. Why? We could be waiting for quite a while until the supermajority of senators vote. But here’s the important part: eventually, the senators will vote. Eventually.

4. Step 4: Nothing to do. Get an espresso and hang out. Just keep waiting until senators vote. Trust me, dude, it’s better for everyone. We need assurance here.

Please vote this November

Most important observation: asynchronous protocols typically value safety over liveness. These protocols make no assumptions about how long it will take for communication to happen, and so it is required that a supermajority of senators must vote.

Is this supermajority property a requirement? Can we make PoS protocols work in the synchronous case? Absolutely. And there’s a bunch of them out there.

What about Avalanche? Avalanche is an elegant protocol, but it’s not so special that it won’t fit within this universal framework. It’s — in fact — squarely in this domain. Avalanche is a (probabilistically) safe asynchronous protocol.

4. L2s on Ethereum

Simple:

1. Step 1: A bunch of bills are proposed all at once in a building next to the senate, and are approved or rejected by a “pseudo senate”.
2. Step 2: At some point, the pseudo senate sends the set of bills to the actual real senators, who have 10 minutes to vote on the set of bills.
3. Step 3: At the end of the 10 minutes, there’s 3 outcomes:

• Approve: pass the bills as long as 51% of whoever is on the senate floor at the time of the bills being proposed votes “yay”.
• Reject: reject the bills as long as 51% of whoever is on the senate floor at the time of the bills being proposed votes “nay”.
• Filibuster: not possible.

4. Step 4: Go back to step 2, and consider the set of bills irrevocable once you go through steps 2 and 3 for a minimum of 6 times.

Basically, L2s “process” a bunch of bills offline first, then show them all at once in a “condensed” form to the senate. Senate must still vote on these bills, so L2s are as slow as the underlying L1. Also, it’s possible the senators are going to reject all those bills, even though the pseudo-senate approved them. The pseudo-senate is irrelevant. Only the real senate can set the law. L2s are trusted off-chain accumulators.

5. Sharding (the asynchronous version)

Gets a bit more complicated. I’ve seen two major classes of sharded blockchains.

Class 1: The basic principle is that instead of having a single big senate, we divide the senate into multiple mini-senates, where each mini-senate votes on bills in parallel, and then sends them out to the larger senate to vote in batches. I’m grossly oversimplifying, but ultimately that’s the gist. The astute reader will notice that the latencies here — in theory and in practice — will be as high as the slowest mini-senate.

Class 2: The basic principle is that we divide senators into mini-senates and then each of those acts as a single unit of vote. It’s basically just a way to reduce the raw number of senators voting on a bill down linearly by the number of shards. Again, latencies here could be huge.

6. Concluding remarks.

If you are now thinking to yourself: “is this it, is this all the fuss is about?”, the answer is a resounding “yes”. This is really it. It’s not that much more complicated. I got kind of lazy towards the latter parts of the article, especially with L2s and sharding because frankly the article started getting kind of long, but there isn’t much more to this space.