Simplex for Crash Faults #

It is easy to adapt Simplex to a setting with crash faults instead of byzantine faults. We interpret it as a natural extension of the original protocol. In the crash fault version of Simplex, we can eliminate an entire round of communication.

Crash Faults vs Byzantine Faults #

The main version of Simplex is designed for a setting with byzantine faults, where faulty players may be malicious and deviate arbitrarily from the protocol. Here, we describe a version of Simplex for crash faults, where faulty players cannot deviate from the protocol, and can at most crash or go offline. In particular, we assume that \(f\) out of the \(n\) players may crash at any point in time, and moreover that \(f < n/2\) (like in Paxos).

The key insight is that a faulty leader will never send different block proposals to different players in an given iteration, even if they are faulty and crash. Thus, it is no longer necessary to require a quorum of votes for a block proposal to be notarized.

Protocol Description #

The only substantial logical change is to redefine the meaning of a notarized block:

Notarized blocks (proposed by the leader). A notarization for a block \(b_h\) is simply any valid block proposal message of the form \(\langle \textsf{propose}, h, b_0, b_1, \ldots, b_h \rangle_{L_h}\).
Notarized dummy blocks. A notarization for the dummy block \(\bot_h = (h, \bot, \bot)\) is a set of messages of the form \(\langle \textsf{vote}, h, \bot_h \rangle_i\) from \(> n/2\) unique players \(i \in \{1, \ldots, n\}\).

Of course, we now no longer need digital signatures, since faulty players can no longer forge messages. Whereas before \(\langle m \rangle_i\) used to denote the message \(m\) signed by player \(i\), now it just denotes the tuple \((m, i)\).

The threshold of finalization also changes from \(\geq 2n/3\) to \(> n/2\):

Finalizing transactions. At any point, if player \(i\) sees \(> n/2 \) \(\langle\textsf{finalize}, h\rangle_j\) messages for some iteration number \(h\), each for a different player \(j\), player \(i\) deems that iteration to be finalized.

Correctness #

Let’s briefly sketch the consistency argument, which is even easier than before.

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 a single observation:

Claim. 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. Thus there are \(< n\) messages combined of either type. If someone sees both \(> n/2\) finalize messages and \(> n/2\) votes for the dummy block of height \(h\), that would require \(> n\) votes to be cast in sum, which is a contradiction. (This is your traditional quorum intersection argument.)

Recall that, when a player finalizes a chain \(b_0, \ldots, b_h\), the player saw that iteration \(h\) is finalized, and also saw that each block in \(b_0, \ldots, b_h\) is notarized. By the above claim, no player can have seen a notarized dummy block at height \(h\), so \(b_h \neq \bot_h\). Next, note that any notarized block that is not the dummy block must have been proposed by the leader. Thus \(b_h\) must be proposed by the leader of iteration \(h\). Observing that the leader proposes at most one block, then if any player sees a notarized block at height \(h\), it must be \(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.

Notes #

The protocol described here is similar to Paxos or Log Paxos. We can interpret Simplex for crash faults as a pipelined recharacterization (or simplification) of Paxos for rotating leaders, with easier view changes. It is then surprisingly easy to extend the protocol to the Byzantine setting (see the main Simplex protocol).