Consensus Series: Preliminaries

_kitchen
_kitchen
Oct 30 · 11 min read

This series of articles was written by myself and Gengmo QI with advice from fcamel and many others. I hope you all enjoy!

Introduction

Earlier we introduced the technology behind our public blockchain in ThunderCore Consensus 101 at a high level. This series of articles is intended for those who are interested in learning more about consensus protocols. The current landscape of blockchain resources has a plethora of competing resources with no clear metric for gauging their quality. This document collates what we believe are the most important facts to understanding blockchain consensus in an accessible way.

This series will culminate in a description of the Thunderella and PaLa consensus algorithms. In particular, we believe PaLa to be the simplest and most performant consensus algorithm of its class and thus treat it as a first class citizen in understanding distributed consensus.

What is a consensus protocol?

Consensus is an abstraction for distributed systems where a set of nodes seek to agree on an ever-growing linearly-ordered log, such that two important properties are satisfied:

  • Consistency: all honest nodes’ logs agree with each other
  • Liveness: all honest nodes are able to make progress on their logs

In context of blockchain, consistency (sometimes called “safety”) means that there is a single canonical chain (no forks) that all honest nodes will agree on. Liveness means that honest nodes on the network are always able to add new blocks to the blockchain. When all nodes agree on a block, we say the block is finalized.

Major types of consensus protocols

We are interested in the following two broad classes of consensus protocols:

(1) Nakamoto Consensus

Nakamoto consensus, sometimes also called “chain” consensus, use Nakamoto’s elegant “longest-chain” fork choice rule for reaching consensus with high probability and is a breakthrough in distributed consensus. These protocols are conceptually simple and tolerate minority corruptions(½). Further, not only has blockchains’ robustness been empirically proven in real world public blockchain networks holding billions in assets, earlier works have also shown mathematically that Nakamoto consensus indeed achieves certain robustness properties in the presence of sporadic participation and node churn that none of the classical style protocols can attain. Unfortunately, known Nakamoto consensus protocols suffer from slow transaction confirmation and low throughput. For example, Bitcoin has a 10-minute block interval and requires several blocks to confirm a transaction with sufficient confidence. Earlier works that mathematically analyze Nakamoto consensus have pointed out that such slowness is inherent for Nakamoto protocols since the expected block interval must be set to be sufficiently large for the protocol to retain security.

(2) Classical Consensus

Classical consensus protocols reach deterministic consensus through voting. These protocols confirm transactions fast relative to Nakamoto consensus as the consensus network size is fixed and progress can be made as soon as the required votes are seen. These protocols typically use the partially synchronous (or partially asynchronous) network model, and thus can only tolerate at most ⅓ faults.

“DAG”

You may also hear of still a third class of blockchain protocols sometimes called “DAG” protocols (a name that says little about the mechanism for consensus). Such protocols include SPECTRE, The Tangle, Avalanche and PARSEC, and Hashgraph. These protocols achieve consensus on non-linear or eventually linear directed acyclic graph (DAG) of blocks using a variety of means. These protocols — which often claim to be the logical evolution of blockchain — are interesting both in a theoretical and practical setting. We omit discussing them in this article to avoid complexity. This article still provides the fundamentals needed to understand such protocols so if they are of interest to you, please keep reading!

In the next two sections, we’ll get into some background information and build up to a rigorous understanding of how we arrive at the tight ⅓ and ½ fault tolerance bounds mentioned above.

Byzantine Faults and Crash Faults

For the purpose of this article, we distinguish between two types of faults

Crash Faults

A crash fault is just that. Even the best run servers do not have 100% uptime and thus crash faults must be addressed in any robust distributed system. A crashed node will stop responding to messages and may lose data. Thus a crash fault tolerant consensus protocol must handle some nodes dropping offline arbitrarily and must allow them to recover data from non-faulty nodes. Examples of crash fault tolerant consensus protocols include Raft and Zookeeper. Raft is simple and commonly taught in introductory courses to consensus. This interactive tutorial is a great place to learn more about Raft and consensus in general.

Byzantine Faults

A byzantine node may behave arbitrarily in the network including not sending messages and sending deliberately misleading messages selectively to other nodes on the network. A byzantine fault may present different symptoms to different observers. It is difficult to declare it failed and shut it out of the network, because the network must first reach a consensus regarding which component has failed in the first place. The term is derived from the Byzantine Generals’ Problem, where actors must agree on a concerted strategy to avoid catastrophic system failure. Some of these actors may be traitors deliberately attempting to sabotage a coherent strategy.

A crash fault tolerant algorithm can tolerate crash faults up to a certain threshold. A byzantine fault tolerant algorithm is able to tolerate byzantine faults up to a certain threshold. In the case of blockchain consensus, we can imagine byzantine faults as malicious actors on the network trying to pull off a double spend or bring the chain to a halt.

You might notice classical consensus protocols are sometimes also called “BFT consensus” protocols. This usage is prevalent and misleading. Nakamoto consensus protocols are also BFT but it is not a BFT consensus protocol in this sense. Thus we’ll encourage the use of the term “classical consensus” instead.

Synchronous, Partially Synchronous, Asynchronous

These are assumptions a consensus protocol requires from the underlying network.

Synchronous

  • Synchrony assumes that there is a known upper bound on all message delay. That is, all messages must be delivered in some amount of time, and all participants in the network know how long it takes for messages to be delivered.
  • Can tolerate up to ½ byzantine faults
  • It turns out the synchronous network model can be overly restrictive with strict limitations. The more nuanced weakly synchronous model is a more practical option.

Partially Synchronous

  • Sometimes also known as partially asynchronous.
  • Partial synchrony assumes that there is an unknown bound on network latency, we do not know ahead of time what it is. The system behaves like a synchronous one most of the time, but sometimes network delay that exceed the bounds may happen.
  • The partially synchronous model is relatively realistic. Unknown delays do occur in real life systems and we may assume that network infrastructure is reliable enough to always deliver messages eventually.
  • Can tolerate up to ⅓ byzantine faults

Asynchronous

  • Asynchrony assumes that there are no bounds on network latency even between correctly functioning nodes. There is no common global clock thus algorithms cannot make timing assumptions and can’t use timeouts.
  • The FLP impossibility proves it is impossible to create an algorithm which is guaranteed to reach consensus in any specific finite amount of time if even a single faulty node is present.
  • That is to say, it’s impossible to have both liveness and consistency.
  • However, there do exist (randomized) algorithms that can achieve consensus within T seconds with probability exponentially approaching 1 as T grows.
  • In other words, under the asynchronous setting, if you have bad actors around, no deterministic algorithms can even agree on the value of a single bit.
  • Deterministic algorithms can tolerate 0% faults and probabilistic algorithms can tolerate up to ⅓ faults.

Notes

  • In practice, the right choice of consensus algorithm, and thus the right choice of the underlying consensus protocol is very context specific. For example, synchronous network assumptions may be appropriate if ½ fault tolerance is needed and if the assumed maximum network delay is very high or the underlying network is very reliable (e.g. a private network).

You might hear that asynchronous and partially synchronous protocols are more performant than synchronous. Fitting the assumptions of the network, synchronous protocols typically wait for a period of time for all messages to arrive before reaching consensus whereas asynchronous protocols make a decision as soon as some message threshold is reached. This is not a rule. There are, for example, synchronous protocols that have “asynchronous performance”.

Fault tolerance bounds: Why ½ and ⅓?

You must have seen or heard expressions like majority honest, tolerate minority corruptions; tolerate ⅓ corruptions multiple times. In the following, we aim to explain the bounds on fault tolerance under different network assumptions. For the curious reader, please see this paper for a more thorough analysis.

Synchronous

Intuition: Majority rule, we want the correct choice to have more than half the votes.

  • By synchronous network assumptions, we can assume that every node on the network has seen every vote after a fixed amount of time has passed at which point a decision can be made.

Explanation:

  • Assume a total of n nodes, among which f is faulty(behave arbitrarily). Once all messages are received (applying synchrony assumption), we want to have at least f+1 correct messages to outnumber the f faulty messages.
  • n ≥ f+(f+1)
  • f ≤ (n-1)/2
  • f < n/2 — “Up to ½ byzantine-fault tolerance”

Partially Synchronous

Intuition: A single dishonest node can fool 2 other nodes by sending conflicting messages to each node.

  • The conflicting messages may not be detected in time because of the partially synchronous network assumption means there is an unknown bound on the network latency.

Explanation:

  • Assume a total of n nodes, among which f are faulty (may behave arbitrarily).
  • Assume a node received x messages.
  • The f faulty nodes may choose not to send any message, thus in the worst case a node will receive at most n-f messages, and make a decision based upon them.
  • so we get (1) x ≤ n-f — “There is at most n-f messages”
  • Among the n-f messages, it is unclear which ones are from the honest ones, or faulty ones. It is possible that the nodes that did not respond are not faulty, but we didn’t get the message only because of network delay.
  • Therefore, f of those responses might be faulty, which means all faulty nodes may have sent false messages.
  • To make a decision, we have to guarantee there is at least f+1 correct messages to outnumber the f faulty messages.
  • thus (2) x ≥ f+(f+1) — “There must be enough responses from non-faulty nodes to outnumber those from faulty ones”
  • By equations (1) and (2):
  • f+(f+1) ≤ x ≤ n-f
  • f ≤ (n-1)/3
  • f < n/3 — “Up to ⅓ byzantine-fault tolerance”

Note on fault tolerance bounds

  • So far we have informally established that it’s possible to achieve consensus with ½ fault tolerance in a synchronous network — messages broadcasted by any honest node are guaranteed to be received by all other honest nodes within some known time period.
  • The maximum achievable fault tolerance drops to ⅓ if we relax to partially synchronous network assumptions — instead of having a known upper bound, the bound of network delay is unknown.
  • It’s unclear if this will be used in practice, but If we add even more assumptions we can increase fault tolerance all the way to 99%.

Takeaway

It doesn’t make sense to talk about a protocol’s fault tolerance without knowing the assumptions it is based upon 🤔. When you are comparing across different protocols in the future, do not be misled by claims such as “Our protocol X is 50% fault tolerant, thus more secure than protocol Y which is 33% fault tolerant 😈”.

Liveness vs Consistency

You may sometimes hear that PoW favors liveness over consistency. Any PoW node has a chance to mine a new block and contribute to the blockchain’s liveness whereas there is no consistency until sufficient time has passed. In Nakamoto consensus, liveness comes for free as any node can make a new block whereas consistency must be carefully reasoned.

In classical consensus, the opposite is true. Consistency is a straightforward argument based on the pigeonhole principle. With a ⅔ voting threshold, it’s clear that at least ⅓ nodes must be byzantine to create a split vote. In the picture below, groups A and B are both ⅔ votes for conflicting proposals. Honest voters do not cast conflicting votes. Thus, group C is byzantine and votes for both groups. Group C must contain at least ⅓ of the nodes in order to create two ⅔ majority votes for conflicting proposals.

With only honest nodes, there might be a split vote (say ½ vote in group A and ½ vote in group B). In this case neither groups A or B will ever reach ⅔ majority since no honest node casts conflicting votes. Without further mechanisms to make progress, liveness comes to a halt. Thus, in classical consensus, consistency is easy and liveness is hard.

Proof-of-Work

So we now know enough to understand the formal properties of the Proof-of-Work (PoW) consensus protocol. PoW is the very original Nakamoto consensus protocol. Using the longest chain fork choice rule, blocks are finalized when they are deep enough into the history. This works because the more blocks that have been mined on top of any given block, the more “work” is required to fork it. The protocol has probabilistic finality meaning consistency is achieved with very high probability.

While the bitcoin paper did not make explicit network assumptions, we can interpret the protocol as functioning in the synchronous network setting. Blocks are required to propagate through the entire network such that each node is likely mining on top of the most recent block. Another way to look at this is to say that PoW is not partition tolerant. A network is partitioned if there are subsets who can speak within their group but not to each other. Since hash power is the only requirement for creating blocks, we can see that each partition in a PoW network is capable of extending and finalizing their own chain.

Finally, as we read earlier, the synchronous network have up to ½ fault tolerance. Indeed PoW achieves this tight bound. This is clear if you understand the “51% attack” where an adversary with majority of the network hash power creates a fork from before a finalized block that becomes the new longest chain thus breaking consistency.

ThunderCore

Real Blockchain. Real Benefits.

_kitchen

Written by

_kitchen

Product and Research Specialist @ ThunderCore and also a lot of other things

ThunderCore

Real Blockchain. Real Benefits.

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