A Better Solution to the Byzantine Generals Problem

Bitcoin is often described as a solution to the Byzantine Generals Problem. But it actually solves a more general problem, which we could call the Anonymous Byzantine Generals Problem, where the generals are not known—i.e., they are anonymous—and can come and go at will. It is not necessary to solve the anonymous version, and we can solve the original version instead, where the generals are known. This eliminates the possibility of a 51% attack and allows instant finality of blocks and transactions. These critical user-experience qualities are worth the tradeoff because miners can never be truly anonymous anyway.

The Byzantine Generals Problem

The original formulation is as follows: The Byzantine Generals are a set of generals, none of whom is the leader. They need a process to make a decision about when to attack their target. They choose to use proof-of-work. Whoever finds the first valid block determines the attack time.

Thus, in this manner, we see that the proof-of-work solution to this problem is a type of consensus algorithm (not a security algorithm): the generals, who presumably know each other (wouldn’t generals in an army know each other?), can agree on a time to attack by using proof-of-work, with no one general being the leader.

Proof-of-work as a solution to the Byzantine Generals Problem is a consensus mechanism.

The Anonymous Byzantine Generals Problem

Bitcoin actually solves a more general problem, which we can call the Anonymous Byzantine Generals Problem. Each general does not know who the other generals are or even how many there are. They do not care about the opinions of “generals” but instead decide to allow anybody who can produce proof-of-work to determine the attack time. If the proof-of-work is unsigned—i.e., you have no idea who produced each proof-of-work—then you have no idea who the generals are. This is the problem solved by Bitcoin: anybody can be a general simply by providing proof-of-work.

Solving the anonymous formulation of the Byzantine Generals Problem is not necessary to create a type of electronic cash, and in fact, it introduces a new problem: What if the enemy pretends to be a general and produces proof-of-work, changing the attack time—presumably to a time when the target is ready to be attacked?

This problem can be solved, of course, if the generals are identified. If you know who the generals are, simply require that each general sign their unit of proof-of-work. In this manner, you prevent the attacker from pretending to be a general.

Two Different Problems

We see that there are actually two distinct problems:

• The Byzantine Generals Problem (or The Classic Byzantine Generals Problem, or The Original Byzantine Generals Problem), where the generals are known to each other.
• The Anonymous Byzantine Generals Problem, where the generals do not know who each other are, do not know how many other generals there are, and are willing to allow anybody to become a general simply by doing proof-of-work.

Bitcoin solves the latter of these. But the anonymous version is not necessary to create a type of electronic cash. In fact, it introduces the possibility that a malicious general (the enemy) performs a 51% attack on the blockchain. It also makes it impossible to have true finality because you never know when someone else will come along and create a bigger proof-of-work block. Furthermore, the mining pools and hashers on Bitcoin are not really anonymous anyway, making Bitcoin’s solution—and the subsequent attack scenarios and user-experience deficiencies—pointless.

Advantages of De-Anonymizing the Generals

The original formulation of the Byzantine Generals Problem assumes the generals are identified because, well, of course they are. In what army would the generals not know who the other generals are? Obviously, every general knows every other general because they all have to go through a rigorous training process for competence and loyalty, and there are only a small number of them. Becoming a general would never, in any army, be some open, anonymous process based only on who has the biggest data center. That would obviously allow an attacker to become a general, which is a huge and eventually fatal vulnerability.

A “general” would be what Bitcoin calls a mining pool. Mining pools are never anonymous in practice because, since they accept connections over the internet at a known domain name, their physical location can be triangulated and identified. The same is true for all big miners who operate large data centers full of hashers. They are so big that you can find them via their energy usage, by locating them on a satellite map, or simply by their registered business address. Miners are never actually anonymous. The internet, and the world, are not designed like that. Bitcoin merely pretends they are anonymous.

If the generals are known, as would be the case in any real army, then we gain significant advantages:

• All generals are known to have gone through a rigorous competency and loyalty process, making it exceptionally unlikely that a general would be a traitor, so that 51% attacks never occur.
• When a new block is found, you can simply ask the other generals if they all agree that the block is valid, and thus you have instant finality: there is no chance that another block will be found to replace it. In Bitcoin, this means reorgs are impossible.
• You also have instant finality of transactions because simply monitoring who produces each block gives you the amount of hash power of each general by counting their number of blocks. You can use that count to vote on valid transactions or on anything else.

De-anonymizing the generals is a huge advantage. It eliminates the 51% attack and creates instant finality of blocks and transactions. In fact, it frankly seems crazy to keep generals anonymous when expressed in this manner: Why would you want to delude yourself into thinking you could have true anonymity for critical pieces of infrastructure that could attack the system and make it impossible to ever have real finality, meaning you never really know if your transaction is valid or not, increasing wait times indefinitely?

Conclusion

The Byzantine Generals Problem is a classic problem in computer science and cryptography. Bitcoin is often described as a solution to this problem, but it actually solves a more general problem, which we could call the Anonymous Byzantine Generals Problem. This problem is not necessary to solve in order to create a type of electronic cash. In fact, it introduces new problems, such as the possibility of a 51% attack and the inability to have true finality of blocks and transactions. By de-anonymizing the generals, we can eliminate these problems and create a more robust and secure system. This is a critical user-experience attribute that is worth the tradeoff because miners can never be truly anonymous anyway. The advantages of de-anonymizing the generals include instant finality of blocks and transactions.

EarthBucks solves the classic Byzantine Generals Problem, which is what gives it the superior qualities of no 51% attack and instant finality of blocks and transactions.