Bitcoin Explained (II)

This is part II in my “Bitcoin Explained” series.

The problem we left at the end of part I was that the construction of a valid chain of payload-storing blocks is trivial (for a computer) to create. For a financial system we want it to not be trivial, we want it to be incredibly hard to recreate a chain, so hard in fact that there can be only one chain.

The solution that Bitcoin uses is a proof of work system. Here “work” means computational work. It’s worth noting that the work we choose must have two very important properties:

1. It must be very hard to do (this is the “work” part)
2. It must be very easy to verify (this is the “proof” part)

There is no point in a proof of work system that requires as much work to check that it is valid as it did to create the work. This is what renders suggestions that Bitcoin should use folding@home or SETI@home as its computational work, invalid. While the work done by those two systems is indeed hard to do (meeting criteria #1), there is no way to verify the correctness of that work other than by repeating it (failing criteria #2).

The proof of work system used by Bitcoin is one that combines nicely with the block chain system it already has. An additional piece of data is stored in each block. This data has no purpose other than to alter the final cryptographic hash of the block (any change of input alters a hash significantly). It’s called the nonce; it’s not (for UK readers) a paedophile, its use comes from the noun “nonce”, meaning “The one or single occasion; the present reason or purpose (now only in for the nonce)”. Strangely, given the purpose of a cryptographic hash, the nonce’s job in a block is to be a use-once number that effectively brute-forces the block hash to a particular value.

That brute forcing of block hash is hard work, but, (drumroll) is easily verified. Exactly what we want for our proof of work system.

The “particular value” of hash being searched for is any hash less than a pre-determined target; we’ll come to how that target is determined later, but for now simply accept that there is a hash-target, and that target is itself listed in the block (i.e. changing it would also change the hash). Finding a nonce is hard because there is no way to know without recalculating what effect any value of nonce will have on the final hash (if there were then the cryptographic hash would be a failure). If we’re looking for a nonce that results in the hash being numerically less than some defined target value, there is only one way to find it: we have to try many different values of nonce, one by one. However, once we have found one, it’s easy for someone else to do the same calculation using that found nonce to see that it really does result in a hash less than the claimed target.

I, as a Bitcoin node, get sent a block by my peer. I do not trust that peer, since it is just some computer on the Internet, it could be feeding me bogus data. I perform two initial checks on that received block:

• I calculate this new block’s hash, that calculation uses both the nonce and the target values. If the hash that I calculate is less than the target value the block claims, then I can believe that its creation was “hard” to the level described by target.
• Is it part of my previously accepted and “trusted” chain? I do this by positioning it in my ever-increasing block chain. Provided the new block claims as its parent a block I have previously accepted as trustworthy, then that new block is part of the chain.

Our node can now reconstruct a chain, and estimate how hard it was to create that chain. It can do that without needing to trust the nodes that fed it those blocks. If bogus blocks are fed then they can be rejected because they aren’t really part of the true chain, or because they weren’t as hard to create as they claim to be. (“Bogus” here is going to mean “not agreed on by a majority of nodes”)

We’re left with a similar problem to the one we started with. Constructing an arbitrary chain is trivially easy, so we required that it is not trivially easy by use of the verified target value. What is to stop us creating a valid chain that honestly claims to be easy, and is? Provided no block has a target that doesn’t verify, isn’t that chain valid; and couldn’t I include a “pay lots of money to me” entry in my easily-created, but valid looking chain? Well yes. Our defence against that is going to be that we don’t allow easy chains. To do that we have yet to talk about how target is determined.

We’ll come to that in part III, when we discuss mining.