The difference between Ordering and Consensus protocols (and why PoW is not quite a consensus protocol)

TLDR - if the validity of all messages in a distributed system is known in advance, an ordering protocol is equivalent to a consensus protocol. However, ordering protocols do not allow to reach consensus on messages whose validity is not known in advance.

Definition of Consensus

The consensus problem, which is fundamental for distributed computing, has been a subject of research since the late 1970s / early 1980s. It can be defined as follows:

“In the consensus problem, each process p start with a local binary value (..) and the processes have to decide on a common value. A consensus protocol that solves the consensus problem terminates when each correct process makes an irreversible decision on some value.” (Gabriel Bracha. Asynchronous byzantine agreement protocols. 1987)

In his 1987 paper, Bracha was the first to present an asynchronous protocol tolerating up to a third of Byzantine nodes, which is optimal. The asynchronous setting, in which arbitrary message delays are possible, is the most difficult one to achieve consensus. The number of communication rounds required by Bracha’s protocol is around 3 * 2**(2n/3), where n is the number of nodes. This is obviously not practical: in a network of 10 nodes, in which up to 3 can by Byzantine, the average number of communication rounds would be almost 400, while 20 nodes would require almost 50,000 communication rounds.

Modern asynchronous binary consensus protocols, which use threshold cryptography, require only a small and constant expected number of all-to-all communication rounds.

There are two important points to note:

1. Consensus is required when the nodes do not know initially if a message is valid or not;
2. Based on a binary consensus primitive, all other consensus protocols can be constructed: multivalued consensus, message ordering etc.

Ordering Protocols

As its name implies, an ordering protocol orders arbitrary messages in a way that all nodes agree on.

In the case where it is known in advance by everyone if a message is correct or not, ordering is actually equivalent to consensus.

In blockchains like Bitcoin, Ethereum etc it is always known, at the moment of adding a transaction to a block, if that transaction is valid or not. A block containing even one incorrect transaction (whatever the reason: wrong format, nonce already used, not enough funds, ….) will simply not be accepted by the network. In fact, incorrect messages will not even be accepted into the mempool of a correct node. That said there there can be transactions in the mempool which initially looks valid, but may be invalidated by a later transaction. Such a transaction will simply never make it into a block, so that’s not a problem.

But when actual consensus is required, for example about a protocol upgrade, it is clear that in Bitcoin and similar PoW chains this decision must be made off-chain. This is because PoW (and by that I mean PoW-with-longest-chain) is not a full consensus protocol - and luckily it does not need to be.

Cases where consensus is necessary

The hardest problem in consensus is identifying muteness failures. One could say that solving consensus is tantamout to agreeing on the answer to the simple question “Has node X sent a message?”

Two typical situations where consensus is necessary (i.e. just ordering will not help):

1. in a leader-based protocol, the leader appears to be slow. The other nodes need to agree whether to remove the leader.
2. In a consortium network, one of the nodes appears inactive. The other nodes need to decide whether to remove that node from the network.

In both of these cases, because of network delays, it may well be that roughly half the nodes initially vote “remove”, while the other half initially vote “keep”. In other words, the outcome is not evident, and some Byzantine nodes may collude to delay a decision as much as possible.

That is why the process of changing a leader is typically a weak point of leader-based protocols.

Achieving consensus when only ordering is available

For decisions which are not time-critical, for example adding/removing validators in a permissioned chain, one solution is to make such decisions off-protocol. By collecting a sufficient number of signatures, the transaction to add or remove a node then becomes “deterministic”, ie it is known in advance that it will be accepted by all nodes.