Protocol in a Nutshell #

What is Consensus? #

Consensus. (Also known as State Machine Replication, or the Permissioned Blockchain problem.¹) We want a protocol that works as follows:

• Setup. There are \(n\) players, \(f\) of whom are faulty. Here, we assume that \(f < n/3\), and that each of these faulty players are malicious (syn: Byzantine), and can deviate arbitrarily from the protocol. (Of course, one may not need to be so pessimistic about faulty behavior — see Simplex for Crash Faults.)
• Transactions. Over time, players receive transactions \(\mathsf{txs}\) from the environment, and want to order them into a single log (an ordered sequence) of transactions. Each player outputs an updated version of their log periodically. If a player outputs a transaction \(\mathsf{tx}\) in its log, we say that the transaction \(\mathsf{tx}\) is finalized, or confirmed, by that player.
• Consistency (i.e. no forks). Suppose two honest players output \(\mathsf{LOG}_1\) and \(\mathsf{LOG}_2\) respectively. Then either \(\mathsf{LOG}_1 = \mathsf{LOG}_2\), or \(\mathsf{LOG}_1\) is a prefix of \(\mathsf{LOG}_2\), or \(\mathsf{LOG}_2\) is a prefix of \(\mathsf{LOG}_1\). This is the key property that ensures that players reach consensus on a single log of transactions, agreeing on their order.
• Confirmation Time. Suppose a transaction \(\mathsf{tx}\) arrives at some time \(t\). How long after time \(t\) does it take for the transaction \(\mathsf{tx}\) to be finalized by every honest player?

For scalability, players typically batch transactions together into “blocks”. The log is then comprised of blocks, instead of individual transactions, hence the name “blockchain”. It is then easy to extract an ordered log of transactions from a blockchain.

The Partially Synchronous network setting. In a real-world network, such as the internet, messages may sometimes be delayed, reordered, or dropped entirely. Entire partitions of the network may lose connectivity due to an implementation bug, or an internet outage. It is essential to prevent a consistency violation (e.g. a double spend) in such a situation. We assume a network that behaves as follows:²

• Good network conditions. Under good network conditions, every message is delivered within \(\Delta\) seconds (e.g. we can pick \(\Delta = 3\) seconds), where \(\Delta\) is known ahead of time.
• Bad network conditions. Occasionally, the network may be faulty. In these bad network conditions, there is no guarantee on message delivery.

We require the protocol to confirm transactions under good network conditions, and to preserve consistency even under bad network conditions.³

Why is this problem hard?

The challenge of faulty players. In our setting, faulty players can deviate arbitrarily from the protocol (i.e. they are “byzantine faults”). Such a fault model has been studied since the 1980s, and is essential for capturing real-world settings such as cryptocurrencies where some fraction of players cannot be trusted. (After all, it seems downright natural that some participants may try to subvert the protocol for their own benefit.) In particular, a faulty player may decide to stay offline, and can also send different (but conflicting) messages to different people, lying about their state. When combined with a unreliable network, this faulty behavior is difficult to detect and challenging to deal with. (Even crash faults are non-trivial to deal with, despite being more benign; see the famous Paxos protocol.)

A toy example. For example, suppose that there are \(n = 99\) players, choosing between two block proposals \(b\) and \(b'\). Suppose that each honest player “votes” for a single block proposal of its choice. Naïvely, one may think that if a player sees 50 votes for \(b\), then no one else will ever see 50 votes for \(b'\). However, this breaks down even if there is only one faulty player. 49 honest players could vote for \(b\), another 49 honest players could vote for \(b'\), and the faulty player could vote for both \(b\) and \(b'\). If the network is unreliable, some player may see 50 votes for \(b\) and no votes at all for \(b'\), and proceed even though some other player saw 50 votes for \(b'\).

As a consequence, we generally require \(\geq 2n/3\) votes on block proposals to make progress (instead of a simple majority), and additionally assume that \(f < n/3\). This is is the same approach taken by most prior work (i.e. see PBFT), and is the best we can do on an unreliable network. And like most solutions to the problem in the literature, we also need basic cryptography (digital signatures) to prevent adversaries from forging honest messages.

Protocol Description #

We start with some preliminaries and data structures that will set the stage for the main body of the protocol.

Digital Signatures #

Our protocol uses digital signatures, which requires a basic setup ahead of time.

• Public key infrastructure. Every player has a public key, and a secret key (which it keeps secret), generated for the digital signature scheme. Each player’s public key is known to every other player at the beginning of the protocol execution.

For any string or message \(m\), we denote \(\langle m \rangle_i\) to be the same message but signed by player \(i\). That is, \(m\) is accompanied by a digital signature on \(m\) that is verifiable using player \(i\)’s public key.

Data Structures #

Simplex uses a number of different data structures, many of which should be familiar to a blockchain enthusiast.

• Blocks and block heights. The protocol operates on “blocks” of transactions. A block is a tuple \((h, \mathsf{parenthash}, \mathsf{txs})\), where \(h\) is the height of the block, \(\mathsf{parenthash}\) is a cryptographic hash of the parent blockchain, and \(\mathsf{txs}\) is a set of transactions included in the block. Thanks to the parent hash, each block essentially “extends” and commits to a parent blockchain, which represents a history of transactions.

• Genesis block. The genesis block is the default starting block \((0, \bot, \bot)\) of height 0. Here, \(\bot\) is the empty string "", representing some empty default value. The genesis block is always the first block in the blockchain.

• Dummy blocks. In Simplex, sometimes we may mine a “dummy block” during periods of time when the network is faulty, or when there is too much malicious activity. A dummy block of height \(h\) is simply the tuple \((h, \bot, \bot)\). Note that the dummy block does not extend a specific parent chain.

• Blockchains. A blockchain of height (or length) \(h\) is a sequence of blocks \(b_0, b_1, \ldots, b_h\) where \(b_0\) is the genesis block, and for each of other blocks, either \(b_i\) is the dummy block of height \(i\), or \(b_i = (i, H(b_0, \ldots, b_{i-1}), \mathsf{txs})\) for some choice of transactions. Here, \(H\) is a publicly known collision-resistant hash function.

• Notarized blocks and blockchains. A “notarization” for a block \(b\) (which may be the dummy block) is a set of signed messages of the form \(\langle\textsf{vote}, h, b\rangle_i\) from \(2n/3\) unique players \(i \in \{1, \ldots, n\}\). A “notarized block” is a block augmented by a notarization for that block. A “notarized blockchain” is a blockchain, where every block has a notarization. Dummy blocks can also be notarized. (Sometimes, notarized dummy blocks are known as “timeout certificates”.)

High Level Structure #

The protocol runs in iterations \(h = 1, 2, 3, \ldots\) where each player only advances to the next iteration \(h+1\) once it has seen a notarized blockchain of length \(h\). Thus, in each iteration \(h\), the protocol must ensure that every honest player eventually sees a new notarized block of height \(h\), and moreover that this block extends some notarized blockchain of length \(h-1\). In order to help shepherd players towards voting for the same block, each iteration \(h\) has a designated “leader player”, denote \(L_h\), chosen randomly ahead of time and known to all of the players. More specifically:

• Random leaders. For each iteration \(h\), its leader \(L_h\) is chosen by hashing the iteration number \(h\) using some public hash function. In other words, \(L_h = H^*(h) \mod n\), where \(H^*\) is a predetermined hash function.⁴

As a preview, in each iteration \(h\), the leader \(L_h\) will propose a new block of height \(h\) extending a notarized blockchain of \(h-1\). Players will then vote for this block, to get it notarized. Of course, we will have to handle the case of a faulty network or faulty leader who sends invalid blocks, or sends different block proposals to different people. A faulty leader may even pretend to be offline, and not send a block proposal at all. We handle this in the full description below.

The Full Protocol Description #

We are now ready to describe the protocol in its entirety.

Starting iteration. At the beginning of the execution, every player immediately enters iteration \(1\). As local state, each player keeps track of which iteration it is currently in, and also stores all of the notarized blocks and messages that it has seen so far.⁵

In each iteration h. Each player \(i\), on entering iteration \(h\) executes the following:

1. Backup step in case of faulty network or faulty leader. Player \(i\) starts a new timer \(T_h\) set to fire locally after \(3\Delta\) seconds if player \(i\) still hasn’t finished iteration \(h\) by then. If the timer fires, and player \(i\) is still in iteration \(h\), player \(i\) sends to everyone a vote for the dummy block \[\langle \textsf{vote}, h, \bot_h \rangle_i\] Here, \(\bot_h = (h, \bot, \bot)\) is just the dummy block.

2. Leader proposal. If player \(i\) is the leader, namely if \(i = L_h\), then player \(i\) sends to everyone a block proposal of the form \[\langle \textsf{propose}, h, b_0, b_1, \ldots, b_h \rangle_i\] where \(b_h = (h, H(b_0, \ldots, b_{h-1}), \textsf{txs})\) is player \(i\)’s choice of a new block extending some blockchain \(b_0, \ldots, b_{h-1}\) that is notarized in player \(i\)’s view. Note that the parent blockchain has length \(h-1\). Player \(i\) should include in \(\mathsf{txs}\) every transaction that it has seen that is not already in the parent blockchain.⁶

3. Voting step. Player \(i\) waits to see the leader’s block proposal. On seeing the first (and only the first) such proposal of the form \(\langle \textsf{propose}, h, b_0, \ldots, b_h \rangle_{L_h}\), player \(i\) first checks that the block is well-formed (i.e. that \(b_h = (h, H(b_0, \ldots, b_{h-1}), \textsf{txs})\) for some set of transactions) and that \(b_0, \ldots, b_{h-1}\) is indeed a notarized blockchain of length \(h-1\) in its view. If these checks succeed, then player \(i\) sends to everyone a vote \[\langle \textsf{vote}, h, b_h \rangle_i\] (Recall that on seeing \(2n/3\) votes for any given block \(b_h\), a player considers that block to be notarized.)

4. Entering the next iteration. At any point during iteration \(h\), if player \(i\) sees a notarized blockchain of length \(h\), it moves on to iteration \(h+1\). At this point, if its timer \(T_h\) has not fired yet: player \(i\) cancels the timer, and sends everyone a message \[\langle \textsf{finalize}, h \rangle_i\] Simultaneously, regardless of whether the player sent a finalize message, \(i\) multicasts its current view of the notarized blockchain to everyone else. (This ensures that other players will also enter iteration \(h+1\) within one message delay.)

Finally, at any point during the protocol execution, no matter the current iteration number:

5. Finalizing transactions. At any point, if player \(i\) sees \(2n/3\) \(\langle\textsf{finalize}, h\rangle_j\) messages for some iteration number \(h\), each signed by a different player \(j\), player \(i\) deems that iteration to be finalized. If an iteration \(h\) is finalized, whenever player \(i\) sees a notarized blockchain of length \(h\), they can finalize all the transactions contained within (and output them to the client).

Some Common Questions #

• Can proposers/voters avoid sending the entire chain? Yes, if we are careful about how nodes forward messages. See Footnote 6 for details.

• Can blocks point to a parent block instead? Yes. \(b_h := (h, h_{parent}, \mathsf{txs})\), where \(h_{parent}\) is the height of the highest non-dummy parent block, works as well. We don’t even need a hash function! [source]

• Why don’t dummy blocks have parents? If dummy blocks pointed to parent chains, then it’s possible that voters vote for different dummy blocks, and split their votes, losing liveness. This occurs when voters disagree on which parent chain the dummy block points to.

• Do proposers and voters need to send the block itself? No. We write it this way for ease of understanding. In practice, block dissemination should be independent, and consensus should be run on hashes of blocks, or something similar.

• How do you do committee reconfiguration? One common way is to split execution into epochs, where each epoch has a different committee, but the committee doesn’t change within an epoch. Players move to the next epoch on confirming \( X\) blocks in the current epoch, which becomes the new parent chain for the next epoch, ignoring extra blocks.

Correctness of the Protocol #

In this section, we argue that the Simplex protocol has all the properties that we desire. Importantly, the protocol is both consistent (that is, two players never finalize two conflicting transactions), and is also fast during periods of network stability. In particular, whenever a new transaction is delivered to some honest player, the protocol finalizes that transaction quickly. Here, our treatment is meant to be informal and intuitive; for a formal analysis, see the full paper.

Consistency Argument #

Consistency requires that if one player outputs a sequence of transactions \(\mathsf{LOG}_1\), and another player outputs a sequence of transactions \(\mathsf{LOG}_2\), then it must be that either the two logs are identical, or that one log is a prefix of the other. This is the key property that ensures agreement on a log of transactions.

For us, it suffices to show that if one player finalizes the contents of a blockchain \(b_0, \ldots, b_h\) of length \(h\), and another player finalizes the contents of \(b_0, b'_1, \ldots, b'_{h'}\) of length \(h'\), then either they are the same chain entirely, or one chain is the prefix of the other. Assume, without loss of generality, that \(h' \geq h\). The argument follows from two simple observations:

1. Claim A. If some honest player sees that a block proposal \(b_h\) is notarized, no honest player will ever see a competing block proposal \(b'_h\) of the same height notarized, unless one of \(b_h\) or \(b'_h\) is the dummy block of height \(h\).

   • Proof. In iteration \(h\), each honest player will only vote for one of \(b_h\) and \(b'_h\). A faulty player can vote for both \(b_h\) and \(b'_h\). There are at least \(\geq 2n/3\) honest players and \(< n/3\) faulty players. Thus there are \(< 4n/3\) votes combined for either \(b_h\) and \(b'_h\). This just isn’t enough votes: if honest players saw that both \(b_h\) and \(b'_h\) are notarized, then there must be \(\geq 4n/3\) votes. (This is also known as a quorum intersection argument.)

2. Claim B. If some honest player sees that iteration \(h\) is finalized, then no honest player will ever see that the dummy block of height \(h\) is notarized.

   • Proof. In iteration \(h\), each honest player will send either a vote for the dummy block, or a finalize message for \(h\), but never both. A faulty player can do both. Thus there are \(< 4n/3\) messages combined of either type. By the exact same argument as for the previous claim, there just aren’t enough votes to make it so that someone sees both \(\geq 2n/3\) finalize messages and \(\geq 2n/3\) votes for the dummy block of height \(h\).

Finishing the consistency argument. Since the first player finalized \(b_0, \ldots, b_h\), then they must see that \(b_h\) is notarized, and moreover \(b_h\) is not the dummy block. We want to rule out the case that the second player sees a different notarized block \(b'_h \neq b_h\) at height \(h\). There are two cases: \(b'_h\) is either a competing block proposal from the leader, or a dummy block.

By Claim A, no player can see any other notarized block proposal \(b'_h \neq b_h\) at height \(h\). By Claim B, no player will ever see a notarized dummy block at height \(h\). Thus, if any player ever sees a notarized block at height \(h\), it must be the same block \(b_h\).

So whenever a player finalizes \(b_0, b'_1, \ldots, b'_{h'}\) of length \(h' \geq h\), their chain must contain \(b_h\). In other words, \(b'_h = b_h\). By the collision resistance of the hash function, recalling that \(b_h\) contains a hash \(H(b_0, b_1, \ldots, b_h)\) of its parent chain, then \(b_0, b'_1, \ldots, b'_{h} = b_0, b_1, \ldots, b_h\) as required.

Liveness Argument #

Simplex has a delightfully simple Liveness proof, in contrast with every single other protocol that we know of in the literature (in this setting).

We show that the protocol makes progress during good network conditions. Assume that every message takes \(\leq \delta\) seconds to be delivered.

First, observe:

0. Observation A. If some honest player has entered iteration \(h\) by time \(t\), then all honest players have entered iteration \(h\) by time \(t+\delta\). (Make sure you see why.)

The liveness argument breaks down into two cases:

1. Claim B (Liveness w/ Honest Leaders). If the leader \(L_h\) of iteration \(h\) is honest, and they entered that iteration by time \(t\), then all honest players will have finished iteration \(h\) and moved on to iteration \(h+1\) (or higher) by time \(t + 2\delta\). Additionally, they all see a finalized block proposed by \(L_h\) by \(t + 3\delta\).

2. Claim C (Liveness despite Faulty Leaders). If every honest player entered an iteration \(h\) by time \(t\), then every honest player enters iteration \(h+1\) by time \(t+ 3\Delta + \delta\). This holds even if \(L_h\) is faulty!

Recall that \(\Delta\) is a protocol parameter that configures the length of the timeout, taken to be a conservative estimate of the true network speed \(\delta\) (so \(\delta < \Delta\)). \(\Delta\) is chosen ahead of time, when the protocol is deployed. (Analyzing the protocol this way gives more granularity for properties like optimistic responsiveness.)

Let’s see why Claim B is true. In the following figure, we visually plot the timeline for an iteration \(h\) with an honest leader, during “good network conditions”, using Observation A:

And likewise, to show Claim C, we plot the timeline of an iteration \(h\) with a missing or malicious leader, again during “good network conditions” and using Observation A:

The full proofs of the claims are in the paper.

Footnotes #