The problem of the Byzantine Generals

“It is not sufficient that everyone knows X. We also need everyone to know that everyone knows X, and that everyone knows that everyone knows that everyone knows X — which, as in the Byzantine Generals’ problem, is the classic hard problem of distributed data processing.”

A fundamental problem in distributed networks is finding consensus in the presence of faulty or defective processes. A dependable system must manage the failure of one or more of its components when it either permanently crashes, repeatedly boots-up and shuts-down, or behaves byzantine, meaning damaging in the worst possible way. For example, nodes may deliberately and maliciously misrepresent or contradict information or disseminate information to make it impossible to unify the network. This problem is described in the literature as the “problem of the Byzantine Generals”. It occurs specifically in the case of Bitcoin when the entire network needs to agree on the secure and irreversible validity of transactions, i.e. when it needs to decide which blocks are the generally accepted ones.

The problem of the Byzantine Generals can be described as follows: A number of generals position their armies outside a besieged city they want to conquer, and they need to choose the time of their attack. They know that they can only be victorious if at least half of them attack at the same time. But if they don’t coordinate the time of the attack well, they are outnumbered and will lose the fight. They also suspect that some of the generals are disloyal and will send out fake messages regarding the time of the attack. And since the generals can only communicate with each other via messengers on horseback, they have no way of verifying the authenticity of a message. So we ask ourselves, how can consensus regarding the timing of the attack be reached in these circumstances, despite the lack of trust and without a central governance entity.

Prior to Bitcoin, this problem was considered perhaps impossible to solve. Computer scientists declared in 1982 that the generals’ problem can at most be reduced to a “commander and lieutenant” problem, in which all lieutenants must act in accordance with the commander’s orders, as long as they are loyal. They have shown that the problem can only have a solution if more than two-thirds of the generals are loyal.[1]

Bitcoin seeks to provide a universal solution to the problem, through which the loyalty of more than 50% of the computing capacity is enough to reach consensus. In this case, disagreement is temporarily accepted and the solution to conflicting opinions is determined by majority vote. In other words, consensus is reached because computing resources are scarce and because one’s own performance is used as a vote. This makes it possible to build applications in a decentralised way, which would not have been possible earlier without a central controller. For this reason, the technology behind the Bitcoin protocol — the blockchain and distributed consensus — is increasingly used in other areas too, not only in transaction verification.

Going back to our example, if we regard the generals as an analogy to the individual mining nodes of the Bitcoin network, then the solution offered by Bitcoin looks like this: At any time, any general may announce an attack time. The attack time that is first heard is considered the official plan. However, the transmission of a message is not immediate, which is why different generals can hear different plans first. Therefore, once a general receives a plan, he must solve a difficult mathematical problem based on that plan — a task which preferably lasts multiple minutes on average. As soon as one of them finds a solution, he adds it to the plan, thus generating a new plan. He sends the new plan to the other generals. After that, everyone who hears it begins to expand on this new official plan, which should again take multiple minutes.

Every general is working on the most frequently expanded plan known to him, in order to extend the longest living solution that he has heard until then. After a solution has been expanded multiple times, the attack time contained in the longest chain of calculations (e.g. in the longest plan) is considered to be the true attack time, because it necessarily required more than half of the calculation capacity of all the generals to create it. Put differently, the mere existence of this longest block-chain is proof that the majority of generals (over 50%) were involved in its creation. No attacker with less than half the computing power could have produced another chain of similar length during the same time. This scheme is called “proof-of-work” and the resulting hash-tree structure of the blockchain is shown schematically below.

One aspect of Bitcoin complicates the problem described above. In the problem of the Byzantine Generals a final decision exists with which all nodes agree. For Bitcoin, this requirement does not exist, so no deterministic solution is provided. The Bitcoin protocol is highly probabilistic and random. It guarantees that the decisions will eventually converge, but without setting a final date. This self-stabilising solution adopted by Bitcoin was described by Dijkstra in 1974 and published in 2006 by Angluin and others, and applied to consensus finding in distributed systems. Eventually an agreement on the validity of each block takes place with absolute certainty. At the same time, it cannot be ruled out that at any point in time a longer chain will appear, which supersedes the previous chain. As a result, all transactions in the shorter chain lose their validity from the time the branch out — the so-called “fork” — takes place. Only those transactions remain valid, which have the same inputs and outputs in the long chain as in the short chain. The discrepancy between the two chains may allow, in certain circumstances, the double spending of the same amounts. This is an issue we’ll discuss in the next sub-chapter.

From a technological point of view, such a fork (or branching out) can be expected at certain intervals. A major such fork took place in March 2013. A new version of a Bitcoin software client, due to a lack of backward compatibility, caused older versions of the same client to fail to recognise the generated blocks. This led to old clients working on their own blockchain. The fork existed for 24 blocks — about 6 hours — and disbanded after most of the network switched back to the old version.

This article is an excerpt from my book, A brief introduction to Bitcoin.