[137555] in cryptography@c2.net mail archive
Re: Bitcoin P2P e-cash paper
daemon@ATHENA.MIT.EDU (Satoshi Nakamoto)
Thu Nov 13 22:34:16 2008
Date: Fri, 14 Nov 2008 06:56:55 +0800
From: "Satoshi Nakamoto" <satoshi@vistomail.com>
Reply-To: satoshi@vistomail.com
To: jamesd@echeque.com
Cc: cryptography@metzdowd.com
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=
=2E I'll try to rephrase it in that context.
A number of Byzantine Generals each have a computer and want to attack t=
he 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 netwo=
rk to generate a packet, they must crack the password within a limited t=
ime to break in and erase the logs, otherwise they will be discovered an=
d get in trouble. They only have enough CPU power to crack it fast enou=
gh 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 like it will announce=
a time, and whatever time is heard first will be the official attack ti=
me. The problem is that the network is not instantaneous, and if two ge=
nerals announce different attack times at close to the same time, some m=
ay 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 so=
lve an extremely difficult proof-of-work problem that includes the attac=
k time in its hash. The proof-of-work is so 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 com=
putation to include that proof-of-work in the hash they're working on. =
If anyone was working on a different attack time, they switch to this on=
e, because its proof-of-work chain is now longer.
After two hours, one attack time should be hashed by a chain of 12 proof=
s-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 ex=
pended on it and see that it must have required the majority of the comp=
uters to produce that much proof-of-work in the allotted time. They had=
to all have seen it because the proof-of-work is proof that they worked=
on it. If the CPU power exhibited by the proof-of-work chain is suffic=
ient to crack the password, they can safely attack at the agreed time.
The proof-of-work chain is how all the synchronisation, distributed data=
base and global view problems you've asked about are solved.
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
