Want to see the most important line in the Bitcoin source code? Here it is:
return (CBigNum(1)<<256) / (bnTarget+1);
What this line does and why it matters is the topic of this installment.
...
Did you ever watch "Who Wants to Be a Millionaire"? They ask a sequence of questions, and as soon as you get one wrong, you lose. Along the way you get a few "lifelines", the most interesting of which is "Ask the Audience". The audience is almost always right.
Imagine you had an audience available to you in daily life, but with a few differences. First, you can ask all the questions you want. Second, every member of the audience knows absolutely everything. (They are all computer geeks or MIT grads or something.) Third, a few of them will deliberately lie to you because they are like that.
Oh, one more thing: You can only communicate with them over the Internet. You have no idea who any of them really are.
One problem with the Internet -- or feature, depending on your point of view -- is that one person can appear to be more than one person. Can you take a "majority vote" when a lying minority can pretend to be legion?
Yes! Well, sort of. You need a cryptographic hash function. And I need better notation. (If you are reading this via RSS, now would be a good time to click through to the post.)
Let \(H\) denote a cryptographic hash function. This just means you can give it any message \(\mathcal{M}\) as input, and it will compute a random number \(H(\mathcal{M})\) as output. For example, we can let \(H\) be SHA-256, which will produce random numbers from \(0\) to \(2^{256}-1\).
"Now wait a minute, Nemo", you say. "Earlier you told me that a cryptographic hash is just a collision resistant one-way function. Now you say it's a random function. Is that supposed to be the same thing? And what do you mean by 'random', anyway? A deterministic process specified by a U.S. Government standard is kind of the opposite of random."
Yes, you're very smart. Shut up.
Seriously, though, the notion of "cryptographic hash" firmly straddles the fault line between cryptography as practiced by academics and cryptography as practiced by... well, practitioners. This is actually an interesting topic of its own, and I will take a stab at writing about it some day. But not today. For now, just accept that \(H\) has the property that when anyone inputs a message \(\mathcal{M}\), it generates an output \(H(\mathcal{M})\) that is completely random, from their point of view, unless they have computed \(H\) for that exact same message before.
When you ask your audience a question, they will send you answers in the form of messages. But here is the twist: You will ignore any message \(\mathcal{M}\) whose hash \(H(\mathcal{M})\) is greater than some threshold. (Bitcoin calls this threshold a target.) For example, suppose your target is \(2^{224}-1\), and you receive two messages in response to your first question:
\(\mathcal{M}_1\) = "The answer to question 1 is Peru [xyzzy]"
\(\mathcal{M}_1^\prime\) = "The answer to question 1 is Iceland [plugh]"
If you calculate \(H(\mathcal{M}_1^\prime)\) and find it is greater than \(2^{224}-1\), you reject it immediately as invalid.
Next, you simply publish your target to your audience. Each message you receive has a nonsense word at the end called a nonce. You ignore the nonce, as it only exists to affect the hash. To create a valid message, a member of your audience must find one with \(H(\mathcal{M})\leq2^{224}-1\). Because \(H\) is a cryptographic hash function, anyone who sends you a valid message must have worked reasonably hard trying different nonces.
Or rather, their computer must have worked reasonably hard. As long as the honest audience members control most of the computing power, most of the valid messages you see will originate from them. And they do not even need to coordinate with each other. Each one can try different nonces at random, and as a group, they will generate valid messages at a faster rate than all of the dishonest people combined.
Now, if you imagine receiving a series of valid messages that look like this:
\(\mathcal{M}_1\) = "The answer to question 1 is Peru [xyzzy]"
\(\mathcal{M}_2\) = "I agree with \(H(\mathcal{M}_1)\), and the answer to question 2 is 42 [foobar]"
\(\mathcal{M}_3\) = "I agree with \(H(\mathcal{M}_2)\), and the answer to question 3 is Lucius Æmilius Paullus and Gaius Terentius Varro [quux]"
\(\mathcal{M}_4\) = "I agree with \(H(\mathcal{M}_3)\), and the answer to question 4 is Miss Scarlet in the Bedroom with the Rope [SqueamishOssifrage]"
...and so on, you get a pretty good idea what Bitcoin's block chain looks like. By mentioning the hash of another message, each of these messages asserts its position in the chain. Each message not only conveys an answer of its own but also attests to the accuracy of all previous messages in the chain.
If your target is \(T\), how many nonces does someone have to try, on average, to generate a message whose SHA-256 hash does not exceed \(T\)? Answer:
return (CBigNum(1)<<256) / (bnTarget+1);
...which is how you write \(\frac{2^{256}}{T+1}\) in C++.(1)
In Bitcoin, the "audience" is the miners, the "messages" are the blocks, and this line of code computes the work associated with each block. The Bitcoin software's Prime Directive is: When faced with conflicting versions of the block chain, the one with the greatest total sum of work is the Truth.
That last sentence is, to my knowledge, the sole original idea in Bitcoin's design.
More next time.
(1) Assuming you have a CBignum class with properly overloaded operator<< and operator/. Did I ever mention that by day I am a mild-mannered software engineer? Well, not that mild-mannered. But I digress.
Another great article, thank you. I recently talked to a cryptographer and I asked him whether he deems it to be possible for Bitcoin to be designed by one person. He said yes sure that’s possible. What do you think? Is “Nakamoto” a single smart ass or a group of developers? Like you said here, the only “new” thing Bitcoin has is your last sentence. Besides that, it is the combination of existing techniques that is unique to Bitcoin.
I need to study the specifics of the implementation better, but everything suddenly clicked about how network difficulty is increased (I think) when I read “You will ignore any message M whose hash H(M) is greater than some threshold.”
Thanks.