13. The Byzantine General's Problem

13

The Byzantine General’s Problem

IN WHAT IS POSSIBLY the most interesting post made by Satoshi, he explains how the block chain solves a problem in computer science known as the “Byzantine fault tolerance”, a more generalized version of the “Two Generals’ Problem”. In this problem, two (or more) persons need to share information in an unreliable communication environment, where messages sent can be lost or tampered with. The statement of the problem first appeared in the 1970s in network computing literature, and at that time the problem was considered unsolvable. In this post, Satoshi claims that Bitcoin solves it.

To illustrate the problem, imagine that two generals are required to attack a city at the same time. If either one attacks and the other does not, the forces of the attacking general will be annihilated by the city’s defenses. Communication between the generals is unreliable; the courier sending the message regarding when to attack must go through the city and so could be intercepted. The first general can, by 9 am, dispatch the messenger with the message communicating that the attack will commence on that same day. However, once dispatched, the first general will have no idea as to whether or not the messenger got through. This uncertainty may lead the first general to hesitate to attack since he might be attacking alone if the second general never received his message.

Knowing all this, the second general may send a confirmation back to the first to indicate that he received the message to attack. But that message, too, could be intercepted, leading the second general to hesitate as well. The first general could be sending a confirmation of the confirmation, but that too could have been intercepted. Hence, again, the first general could hesitate unless he gets back a confirmation of this confirmation of the first confirmation. This process could be carried out ad infinitum with no way for either general to know whether messages were dispatched or whether they were but were intercepted by the enemy.

To learn more, read the section “Illustrating the problem” in the following Wikipedia article:

http://en.wikipedia.org/wiki/Two_Generals%27_Problem

See also this article on the Byzantine fault tolerance:

http://en.wikipedia.org/wiki/Byzantine_fault_tolerance

Re: Bitcoin P2P e-cash paper

Satoshi Nakamoto Thu, 13 Nov 2008 19:34:250800

James A. Donald wrote:

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.

The proof-of-work chain is a solution to the Byzantine Generals’ Problem. I’ll try to rephrase it in that context.

A number of Byzantine Generals each have a computer and want to attack the King’s wi-fi by brute forcing the password, which they’ve learned is a certain number of characters in length. Once they stimulate the network to generate a packet, they must crack the password within a limited time to break in and erase the logs, otherwise they will be discovered and get in trouble. They only have enough CPU power to crack it fast enough if a majority of them attack at the same time.

They don’t particularly care when the attack will be, just that they all agree. It has been decided that anyone who feels likeit will announce a time, and whatever time is heard first will be the official attack time. The problem is that the network is not instantaneous, and if two generals announce different attack times at close to the same time, some may hear one first and others hear the other first.

They use a proof-of-work chain to solve the problem. Once each general receives whatever attack time he hears first, he sets his computer to solve an extremely difficult proof-of-work problem that includes the attack time in its hash. The proof-of-work isso difficult, it’s expected to take 10 minutes of them all working at once before one of them finds a solution. Once one of the generals finds a proof-of-work, he broadcasts it to the network, and everyone changes their current proof-of-work computation to include that proof-of-work in the hash they’re working on. Ifanyone was working on a different attack time, they switch to thisone, because its proof-of-work chain is now longer.

After two hours, one attack time should be hashed by a chain of 12 proofs-of-work. Every general, just by verifying the difficulty of the proof-of-work chain, can estimate how much parallel CPU power per hour was expended on it and see that it must have requiredthe majority of the computers to produce that much proof-of-work in the allotted time. They had to all have seen it because the proofof-work is proof that they worked on it. If the CPU power exhibited by the proof-of-work chain is sufficient to crack the password, they can safely attack at the agreed time.

The proof-of-work chain is how all the synchronisation, distributed database and global view problems you’ve asked about are solved.

The Cryptography Mailing List