Bitcoin white paper explained (PART 2/3)
proof of work explained
The article states we need proof-of-work if we are implementing the timestamp server in a peer-to-peer basis. Let’s first see what it is and we will get again to the question in hand.
4. Proof of work
In Part 1 we saw that a SHA-256 function produces a fixed-length (256 bits) string (in Hexadecimal) from a certain data input. Let’s have a look on how such a hash looks for some inputs (“Alice”, “alice” and “ALICE”). Output is represented in Hexadecimal and Binary (only the beginning for brevity):
As you can see, the output drastically changes for small changes on the input but will remain the same when it isn’t changing.
This asymmetry of I/O has been exploited in Hashcash to ensure a certain operation has a cost associated with it.
An example could be reducing email SPAM: I give you a challenge to be resolved before sending the email which will cost you some computing power (i.e. electricity hence money). It will be small enough so that sending one email is cheap but costly enough to avoid a spammer send many. What could the challenge be?
Let’s say the content of the e-mail you are sending is “Alice”. We know the output of a SHA-256 applied to the content starts with 3 (0011 in binary) from the table above. A challenge I could give you is to find a number which when appended to the content (i.e. “Alice24”) will produce a binary output with certain amount of 0’s in the beginning. Why would I do that? Well, it’s just math. You can picture the binary output as a sequence of flipping coins (we don’t know what output we get from certain input so the sequence of 0’s and 1’s is random, just like the chance of flipping a coin). What is the chance to get one 0 from a certain number appended to Alice? Well, 50% (it’s flipping one coin). To have two consecutive 0's? 25%. And so on… The more 0’s I ask you for, the more difficult the challenge gets.
So let’s say k is the number of 0’s we are asking for. Given the input “Alice” and a challenge k=2:
We have found a solution by calculating the hash 3 times. Everyone can calculate the hash just once and verify that what we solved the challenge correctly. We could make the challenge much more difficult by requiring more 0’s to appear on the output (k=20 requires on average 1 million tries).
How does Bitcoin leverage this?
We need to find a way to give incentives to distributed machines to find consensus (vote) on what is the current state and order of the transactions within the blocks that form the blockchain. If there was no cost associated in generating each block it would be costless for anyone to manipulate it (such as in the SPAM prevention example) and hence the system would be hackable by definition.
By applying a variation of Hashcash PoW we can accomplish this:
Instead of using “Alice” as we did in the last example, what bitcoin does is applying the hash function on the headers of the block (which include the previous block hash, the timestamp and the nonce among others). The nonce is the number we have to increment until we satisfy the 0s challenge we are solving just as in our example. An immediate question arises: The nonce is a number defined by 32bits (allows ~4 billion tries), isn’t that a quite easy challenge to solve for a miner with current technology? It is! That’s why there is an extraNonce in every block (in the coinbase transaction — check section 6) which has to be modified by the miner whenever the 4 billion hashes have been calculated with no success. A modification on the extraNonce changes the Merkle tree root so we can start calculating hashes from 0 again. And repeat. What’s a Merkle tree? That’s covered in Part 3. For now just think that the transactions change and so does the headers hash hence the space of hashes we can generate through the nonce.
This is how a block is mined. As there are multiple nodes within the network they have to do decision making through consensus. What a miner considers truth is validated by the PoW it has performed rather than something like an IP address, which could be tricked by a single entity getting many IPs (remember PoW depends on CPU cycles which has a cost associated with it).
Decision making is achieved by the longest chain:
Two nodes (one in Amsterdam, one in Barcelona) mine a block at the same time so there is a race condition (called fork). Surrounding nodes to each location will receive one of the two chains first and start working immediately on top of it. Nodes close to Amsterdam will keep working on chain A (they received quicker the new block) while Barcelona ones will work on top of another chain B. Both chains latest block hash will differ (due to different headers — as transactions might not be the same, in the same order or the tiemstamp slightly differs). As soon as another block is mined on a chain (i.e. A) the node will propagate it to the whole network and nodes that believed the other chain (B) was the correct one will see they aren’t on the longest chain to date anymore (their latest blocks become orphan as they are out of the main chain) so will have to start working on chain A.
If the majority of CPU is held by honest nodes, their chain will outpace attackers: the probability of changing a past block and catching up diminishes exponentially by every block that is added as the attacker would have to redo the work of that block, all blocks after it and surpass the current nodes work.
The difficulty of the PoW challenge is automatically updated (by software — it’s part of the consensus rules which any node runs and validates) so it keeps it hard enough taking into account increasing hardware speed and changing financial interests (transaction rewards/fees). The difficulty depends on the target which is the 256 bit number with leading 0’s we are trying to find while producing hashes. In bitcoin it’s represented by a floating number to enable more flexibility while doing adjustments (so we can adjust to “2 zeros and a half” whereas in Hashcash it’s integers).
There is a desired average mining speed of one block each 10 minutes (an estimate of a good balance between orphan blocks / network speed) which is automatically adjusted every 2016 blocks. At this speed that should have taken two weeks, if it took more difficulty is reduced for next 2016 blocks and the process repeats.
All that is described in the original paper we have discussed in section 4 in order to understand PoW properly. The network behaves as follows:
- New transactions are broadcasted to all (doesn’t have to be 100%) nodes
- Each node collects transactions into a block
- Once enough transactions are found they are validated
- Once valid, PoW is executed on them to form the block
- By performing PoW of a new block the node has accepted the chain at that moment
Longest chain is considered the correct one but other branches are kept in case they become larger (as we saw in section 4)
There is a block called genesis block which is the first block within the blockchain and it’s hardcoded within bitcoin core by Satoshi Nakamoto.
Every mined block has a first transaction called coinbase transaction. It’s the one that gives the reward to the miner for doing it’s PoW. That’s how bitcoins are initially put into circulation and the amount of reward gets capped every 210000 blocks (~4 years) by half. Other incentive is the transaction fee, which we saw is defined by unspent transaction inputs. There will be a moment where incentive will be just based on that as rewards keep halving.
Playing by the rules ensures profit while not doing so can easily get an attacker into trouble. Even if someone get’s more CPU than honest nodes he will find it more profitable to play by the rules (he would get more coins than anyone else combined) than undermining the hole system.
So now that we know what PoW is, do we actually need it? It’s one way of overcoming byzantine failures which basically means that all participants (nodes) must agree on the same thing (the blockchain contents at certain point of time). With no PoW any node could manipulate the chain and pretend its version is correct, but by having a CPU limitation it would be too expensive to go that way.
Are we safe? Well, theoretically if the top 3 miner providers decided to join forces they could alter the blockchain at their will. Thing is, game theory tells us that it won’t happen as it’s far more profitable to follow the rules instead of discrediting the hole system.
In next part we will see some optimizations on the bitcoin implementation.
Clap if this helped and follow me on Twitter @sgerov!