Mining – Solving the puzzle

In an earlier article, I discussed why the process of mining is essential for Bitcoin and other cryptocurrencies and I gave a very generic overview of how it works. In this post, I will attempt to explain in more detail what the mining process entails.


But first, hash functions!

An important concept in understanding Bitcoin mining (and mining of most altcoins) is the concept of a hash function. A hash function is a mathematical function that takes any input data and returns a number of fixed maximum size. A very simple example of a hash function would be the function that takes any number and adds up its digits, repeating the process until a single digit number remains. The number 5618 would give 2 as result, for example.

A special subset of hash functions are the cryptographic hash functions. These have the property that a small change in the input data completely changes the output. In addition, given an output value, it should be impossible to find input data that would produce this specific output. My previous example is not a good cryptographic hash function, since a simple change like swapping the order of two digits doesn’t change the output at all. In addition, given an output value, say 6, it is easy to find not just one, but many inputs that would result in this output, for example 6, 15, 24, 123, etc…

Cryptographic hash functions have many applications. One such application is to verify that some piece of data was not tampered with. If I post a file online, I can compute it’s hash using a cryptographic hash function. Anyone downloading the file can do the same and compare the results. If they are the same, then they can be assured that the file was not altered by a third party. In a similar way, I can make a prediction about a future event, say a sports match, type it out, compute the hash of the text and share that with others. After the event, I can reveal the original text and the others can verify that I did not change my written prediction by computing the hash of the revealed text and comparing it with the hash I provided at the start.

A recipe for a block

Back to Bitcoin. As you know, transactions are bundled in blocks. The set of transactions in a block is described by a data structure called a ‘Merkle tree’. The details of this are not important, but the main aspect is that from this data structure a single value can be computed, the so-called ‘Merkle root’, which is computed from the set of transactions using a cryptographic hash function. So any change in one of the transactions causes the Merkle root to change.

While the transactions form the main body of a block, each block has a header which contains important metadata. The Merkle root discussed above is one element of the header, but the header also includes a timestamp, a reference to the previous block and some other variables. One particular element of the block header is interesting though. A 4 byte area that can have any value.

The puzzle: How low can you go?

If we put the block header into a cryptographic hash function, we get a number out. The computational problem that drives Bitcoin mining is to make sure that this number is below a certain target-value. So if the hash function would have a possible range of values between 0 and 100, we could demand that in order for a block to be valid, the hash of its header must be smaller than 20, for example.

The 4 byte area that can have any value mentioned above plays an important role here. In the process of mining, the miner will change the value of this variable, the so-called ‘nonce’, compute the hash of the block header and check if it’s below the target value. If not, change the nonce and try again. If the hash does fall below the target value, the miner broadcasts the block to the network.

Difficulties

It should be clear from the previous section that the speed at which we can find a valid block header depends on how fast we can compute the hash function. The amount of computing power used for mining today is much higher than it was in 2009, when Bitcoin was first launched. If the target value below which a hash should fall would be fixed, this would mean that blocks would be produced many times faster today than a few years ago.

To overcome this problem, the target value is updated regularly. This update aims to set the target in such a way that on average it takes the entire network 10 minutes to find a valid block. This update occurs after every 2016 blocks, which corresponds with a period of 2 weeks at a rate of 10 minutes per block. At this point, the total amount of time spent mining the last 2016 blocks is computed and from that, the target value is adjust.

Instead of the target value, miners talk about the difficulty value, which is inversely proportional to the target value. A higher difficulty means that the target value is lower and that is more difficulty to find a valid hash of the block header. Since the difficulty is proportional to the amount of computing power in the network, the change in difficulty can be seen as a measure for the growth of the network.

Extra nonce – for when just the nonce isn’t enough

Very attentive readers may have noticed an issue with the description of the block header I gave earlier. The issue relating to the nonce, the 4 byte field that can be filled with arbitrary values to in the mining process in order to find the right hash value. 4 byte is 32 bits and that means there are 232 possible values for the nonce. This is roughly 4 billion. Nowadays, there are plenty of mining devices on the market that compute a multiple of that per second, because 4 billion computations per second corresponds with a hashing rate of 4 GHash/s.

While there is a timestamp field in the block header, this field only has a granularity of a second. So if more than 4 billion values for the nonce are computed within a second, the miner runs out of new possibilities to try. And these days the mining difficulty is high enough that there’s a very large chance that more than 4 billion attempts are needed to find a valid block.

To overcome this problem, some additional space was added where miners can add random data in order to try additional possibilities. This additional space is located in the special transaction that rewards the miner with the reward for finding the block (this transaction is called the coinbase-transaction). Recall that a change in any of the transactions in a block changes the Merkle root in the block header. So after all 4 billion nonce values have been tried, a miner can change the value of the extra nonce field in the coinbase-transaction, which causes the Merkle root to change, after which the miner can restart trying changing the regular nonce values again.

Conclusions and a note on the specific functions used

The calculations done by miners don’t serve a particular purpose. The only point is that they take time and computational effort to do. By changing the nonce and extra nonce values until the resulting hash of the block header falls below the target value, mining essentially becomes a lottery, where a miner with more computing power has better odds.

In this article, I have not given any details about the hash function used, because they don’t matter. As long as it is a proper cryptographic hash function, it can be used. In fact, many applications of these cryptographic hash functions have more stringent demands than Bitcoin mining, so even functions that are no longer suitable for other tasks because weaknesses were found, would still make for a perfectly safe function for mining.

Many alternative cryptocurrencies use different hash functions than Bitcoin. This is not for security reasons (although some altcoin creators do claim just that), but rather to prevent the dedicated hardware created specifically for Bitcoin mining (the so-called ASIC hardware) from being used to mine the alternative currency, thereby giving users that haven’t made an investment in mining hardware a chance to provide a non-trivial contribution.

In a followup article, I will discuss the mechanics of pooled mining, where many users can work together to find a block and share the rewards.

Leave a Reply

Your email address will not be published. Required fields are marked *