Skip to content

Satoshi Nakamoto explains the blockchain

March 30, 2013

One of Bitcoin’s strengths is the brilliant solution to the Byzantine Generals’ Problem as rendered by Satoshi Nakamoto, the art name of whomever it was that originally coded Bitcoin.

The obvious brilliance of the solution rests on one fact: the Bitcoin network has been up for four years. The bad press, the network attacks, the server hacks, the market crashes…all have come and gone but Bitcoin keeps chugging like the lean and strong little engine that it is.

Below is Satoshi’s early description of his solution to the Byzantine Generals’ Problem which we now use as Bitcoin’s blockchain.

Re: Bitcoin P2P e-cash paper
Satoshi Nakamoto
Thu 13 Nov 2008 19:34:25 -0800

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 like it 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 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 computation 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 one, 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 required the majority of the computers 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 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.

From → Uncategorized

  1. Blacksmith permalink

    This is all good until one looks at custom hardware being produced to perform that work in a fraction of the time and thus which could give the impression that many nodes were required to perform the work when it’s actually just one big c1a node blagging the system and telling each general a different time so they can be ambushed separately :(

  2. Zigzag permalink

    So how does bitcoin know how much CPU is coming from Bitcoin supporters vs. subversive Institutions? Supercomputers are easy to come by for Banks and sovereign entities.

    • Bitcoin doesn’t know. Satoshi is assuming what all decent human beings assume: there are more honest people than dishonest people in the world.

      If we’re wrong and there are more dishonest than honest people, then Bitcoin will fail.

  3. Blacksmith permalink

    Rather, if subversive forces control more hashing power the bitcoin system will fail. the number of ppl in the BTC community and honesty of those ppl is irrelevant, only the resources matter. He who can hash fastest generates the block, blocks don’t have to have transactions in, and without transactions there’s is no purpose or value to a BTC :-0

    • True, it is the resources, not the actual people. However, if the solution does indeed follow anywhere near that of the Byzantine General’s problem, then there is some clever algo requiring the “majority” of the CPU power to be dishonest. The standard problem requires that the “vast majority” (> 2/3) of the CPUs are honest. I suspect a better algo can do better than 2/3, but it is not an easy problem to solve, and this brief article glosses over this non-trivial issue.

      Regarding honesty, it’s more accurate, to say “correctness”: it doesn’t matter whether the CPUs are honest or not, just whether they are crunching the numbers properly. They might be messing up on purpose (dishonest) or on accident (hardware failures, etc.). For instance, the Hadoop Data File System (HDFS) default sets up a data redundancy of 3: each chunk of data is replicated on 3 different hard disks on 3 different ranks. This is not to fight against dishonesty, but against hardware failures. I’m still not sure how bitcoin addresses hardware failures at the source. But that’s a totally different issue…

Trackbacks & Pingbacks

  1. Satoshi Nakamoto explains the blockchain | Bitcoin News Bits -

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

%d bloggers like this: