[EMS Discuss] The Byzantine Generals' Problem

Wed Nov 13 15:54:13 PST 2013

Hi Gang,

last night I mentioned that the hashing algorithm bitcoin uses is based 
on another well known computer science problem. Well here it is: The 
Byzantine Generals' Problem

On a bitcoin site there is a short write up:


The Byzantine Generals' Problem

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, lest they be discovered. 
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 
agree. It has been decided that anyone who feels like it will announce 
an attack time, which we'll call the "plan", and whatever plan is heard 
first will be the official plan. The problem is that the network is not 
instantaneous, and if two generals announce different plans 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 plan he hears first, he sets his computer to solve a 
difficult hash-based proof-of-work problem that includes the plan in its 
hash. The proof-of-work is difficult enough that with all of them 
working at once, it's expected to take 10 minutes before one of them 
finds a solution and broadcasts it to the network. Once received, 
everyone adjusts the hash in their proof-of-work computation to include 
the first solution, so that when they find the next proof-of-work, it 
chains after the first one. If anyone was working on a different plan, 
they switch to this one, because its proof-of-work chain is now longer.

After about two hours, the plan 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 required the majority of 
the computers to produce in the allotted time. At the least, most of 
them had to have seen the plan, since the proof-of-work is proof that 
they worked on it. If the CPU power exhibited by the proof-of-work is 
sufficient to crack the password, they can safely attack at the agreed time.

I also attached the full paper on it.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://eugenemakerspace.com/pipermail/com.eugenemakerspace.discuss/attachments/20131113/5f7e4aa9/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: lsp82-1.pdf
Type: binary/octet-stream
Size: 1245510 bytes
Desc: not available
URL: <http://eugenemakerspace.com/pipermail/com.eugenemakerspace.discuss/attachments/20131113/5f7e4aa9/attachment-0001.bin>

More information about the Discuss mailing list