analysis

# how do the bitcoin mining algorithms work?

cryptocurrencies (2018-04-17)

Bitcoin mining involves computers competing with each other to solve a random puzzle. The answer found by the winner is shared and verified by all participants. The winner receives bitcoins as a reward.

In this article I will delve into what exactly this random puzzle is, and how the solution found by the winner is verified. I have made the article interactive so that you can simulate the mining algorithms for yourself and get a feel for how mining really works. While the concepts here are not simple, they are presented so as to be easily understood by someone with no knowledge of programming, cryptography or Bitcoin. And I hope the interactivity will make the whole process fun.

The article has 3 parts:

Bitcoin mining uses cryptographic hashing, so to understand Bitcoin mining it is first necessary to understand what cryptographic hashing is and how it works. Rather than bore you with definitions at the start, let's just dive in and give it a go. Click the SHA256 button a few times and look carefully at what this does each time, then try typing different things in the pre-image field and clicking the SHA256 button to see what that does:

SHA256 stands for Secure Hash Algorithm (256 bits). Algorithm sounds complicated but it just means a series of operations done by a computer. There are many different hashing algorithms - SHA128, SHA512, MD5, RIPEMD128, RIPEMD160, etc. The differences between these hashing algorithms are not important for the sake of this article. All that is important is to recognise that SHA256 is merely one of many hashing algorithms - the one that is used in Bitcoin mining.

Cryptographic hashing involves taking a string of characters and transforming them into another string of characters. We call the input characters the pre-image and we call the output the hash:

The output of a cryptographic hash is actually a number; however, that may not have been obvious when you ran the SHA256 hash above, since that number is written in hexadecimal format - i.e. base 16. To explain what that means, here are some hexadecimal values side by side with their decimal equivalent values:

 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 a 11 b 12 c 13 d 14 e 15 f 16 10 17 11 18 12
click for more

Don't worry, you won't need to do any hexadecimal conversions while following this article. All you need to remember here is that hexadecimal digits go from `0` to `9` to `a` to `f`.

OK, so now that you have tried cryptographic hashing, and you know about hexadecimal format, let's have a look at a more formal definition of cryptographic hashing. Some parts of the definition may not make sense at first, but I will be explaining them in detail in the paragraphs that follow.

A cryptographic hashing algorithm has the following properties relevant to Bitcoin mining:

1. it is deterministic - the same pre-image always results in the same hash
2. it is quick to compute the hash value for any given pre-image
3. it is impossible to reverse a cryptographic hash and recover a pre-image from its hash value, except by trying all possible pre-images
4. a small change to a pre-image changes the hash value so extensively that the new hash value appears uncorrelated with the old hash value

Lets investigate these properties:

Properties 1 and 2 are quite obvious - earlier when we hashed `hello world!` with SHA256 it always gave `7509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9` and took less than 4 milliseconds (depending on the speed of your device), which is fairly quick. However, it must be noted that performing the hash always takes at least some time, even if it is a very small amount of time. This fact will be important when we discuss hashing in relation to Bitcoin mining later on.

Property 3 explains that hashing is a one-way process. We can easily get from a pre-image to its hash, but it is impossible to programmatically get from a cryptographic hash back to its pre-image. The process of trying to get from a hash back to its pre-image is called inverting the hash.

easy: pre-image -> SHA256 -> hash impossible: pre-image <- SHA256 <- hash

If we start with a pre-image and then hash it, then of course we already know what the pre-image for the resulting hash is. For example, if I give you the hash `7509e5bda0c762d2bac7f90d758b5b2263fa01ccbc542ab5e3df163be08e6ca9` then you already know that a corresponding SHA256 pre-image is `hello world!`, since we already hashed `hello world!` with SHA256 earlier and it gave this result. But if I give you `32bd2fb75ea9fdd49c0a9b97b015b47a9cf41f6fc2f773dde97c67bcfc9830c7` then you will not be able to find the pre-image which results in this hash - i.e. you will not be able to invert this hash. Seriously - give it a go:

? -> SHA256 -> 32bd2fb75ea9fdd49c0a9b97b015b47a9cf41f6fc2f773dde97c67bcfc9830c7

The difficulty of inverting a SHA256 hash is due its enormous length! SHA256 has approximately 2256 possible different hash values. That's 115792089237316195423570985008687907853269984665640564039457584007913129639936 different possible hash values. There are about that many atoms in the universe! So don't feel bad for not being able to invert `32bd2fb75ea9fdd49c0a9b97b015b47a9cf41f6fc2f773dde97c67bcfc9830c7`. For all intents and purposes, it cannot be inverted. And that is true even when computers do the hashing at their maximum speeds. If you click the Run SHA256 Automatically button below then you can have your device cycle through pre-images and show you the results at its maximum possible speed:

? -> SHA256 -> 32bd2fb75ea9fdd49c0a9b97b015b47a9cf41f6fc2f773dde97c67bcfc9830c7

When it comes to hashing, 30 hashes per second is actually not quick at all by computer standards. Specialized computer chips called ASICs are built to run billions of hashes per second. At the time I'm writing this (March 2018) the total global SHA256 hashpower is 25,000,000,000,000,000,000 hashes per second, i.e. 25 million million million hashes per second, but even at this rate it would take 146 million million million million million million million million years to try enough different pre-images to invert a SHA256 hash. That's about a million million million years quicker than your device, but it doesn't really matter - by the time it comes around, our sun will have long since burned out.

"Ok", you might think to yourself, "but maybe I don't need to try millions and millions of pre-images to produce the hash I'm after - maybe I can just skip ahead ... If the pre-image I start with does not give a hash that is close to what I want, then I will just choose a pre-image further along that gives a hash closer to what I want, and then make minor adjustments until I zero in on the hash." But alas, this is not how cryptographic hashing works - Property 4 tells us that hashes are both deterministic and random. They are deterministic because a pre-image will always hash to the same value, but that value is random, so there can be no process of zeroing in. Trying a pre-image that is "further along" is no better than trying any other different pre-image - they all completely modify the resulting hash.

Now that we have discussed the properties of cryptographic hashing, we can investigate how it is used in a technique known as proof of work, also known as mining. Proof of work, as the name implies, is a way for one computer to prove to another computer that it has completed a certain amount of work. Let's call the computer doing the work the miner, and the other computer the examiner. The examiner sets a test for the miner to pass by giving it 3 things:

• part of a pre-image
• a hash value that must be matched (called the target)
• the difficulty level of the test

The test works like this: the miner takes the part of the pre-image it has been given and appends a bunch of random data (called a nonce) to the end of it. It then hashes the whole thing and checks if it matches the target given by the examiner. However, it does not need to match the entire target hash (that would take millions of years); rather, it just needs to match part of the target hash, as specified by the difficulty level.

That all sounds very complicated, but don't worry, it will be much clearer after you give it a go. Click the Mine with SHA256 button and look carefully at what this does. Once you find the solution, try changing the difficulty:

SHA256 target: 0000000000000000000000000000000000000000000000000000000000000000

In that scenario, your device was the miner. When you passed the test, you would give the nonce back to the examiner and it could verify that you did indeed pass by running the hash for itself. It would have taken your device a lot of attempts at hashing to pass the test (i.e. a lot of work), but it only takes the examiner a single hash to know whether you passed or failed. This means that your device is doing all the work and the examiner barely does any at all.

As you would have noticed, the higher the difficulty, the more attempts it will take on average to pass the test. From the results, you can also see that there is a degree of luck involved in mining - sometimes it takes fewer attempts than expected and sometimes it takes more. This is because hashing is a random process.

Another thing to note is that the examiner can set the target value without having to hash a pre-image to get it. The examiner does not need to know the answer to the test before it sets the test for the miner. In this way, mining is different from a normal school exam. All that matters is that the examiner can verify the test once the miner submits the nonce as a solution.

You may be wondering why the examiner must supply part of the pre-image to the miner. Why not just let the miner determine the entire pre-image itself? The answer is that this is necessary to ensure that the miner always has to do work (i.e. do lots of hashing) to find a solution to the puzzle. If the miner was allowed to determine the entire pre-image itself, then once it had found a solution for a given difficulty, it could simply re-use that solution over and over and thus avoid doing any work. To ensure that the miner always does work every time the examiner gives the miner a test, the examiner generates a new pre-image prefix as part of every test. This way, the miner has to find a new nonce for every test, even if the difficulty does not change.

The final thing to understand from this section, before we move on to Bitcoin mining, is that the test we have done here - matching a specified number of characters at the left-hand side of the target - is just one of many possible types of proof-of-work test. The only criteria for a good proof-of-work test is that the examiner must be able to fine-tune the number of attempts it takes the miner to pass. Here are some examples of other proof-of-work tests:

• matching a specified number of characters at the right-hand side of the target
• matching a specified number of characters anywhere within the target
• treating both the target and the mined hash as (hexadecimal) numbers, setting the target to some large number, and requiring the miner to find a hash lower than the target

That last type of proof-of-work test is the one used in Bitcoin mining and is explained in detail in the following section.

Now that we have explored hashing and mining in general, we can apply this knowledge to Bitcoin mining.

Bitcoin mining involves computers competing to find the nonce part of the pre-image for the hash of the next block in the Bitcoin blockchain. The winner receives bitcoins as a reward.

That explanation contains a couple of new concepts, and once you understand them then the process will make perfect sense:

• a Bitcoin block
• the Bitcoin blockchain

When someone sends some bitcoins to someone else, they begin by opening their Bitcoin wallet (which is a program, app or website running on their device), and then typing in the address of the recipient and the amount of bitcoin they want to send to them. The Bitcoin wallet uses this information to construct a transaction. Here is a real Bitcoin transaction taken from the blockchain:

01000000010000000000000000000000000000000000000000000000000000000000000000ffffffff0704ffff001d0102ffffffff0100f2052a01000000434104d46c4968bde02899d2aa0963367c7a6ce34eec332b32e42e5f3407e052d64ac625da6f0718e7b302140434bd725706957c092db53805b821a85b23a7ac61725bac00000000
example Bitcoin transaction

For the purposes of this article, the details of this transaction are not important, but if you are curious you can view all of its information here. However, the only thing you really need to understand at this point is that a Bitcoin transaction is just a string of characters.

Once the wallet software has created the transaction, it sends it out over the internet to all the other Bitcoin nodes it can find (a Bitcoin node is just a device running the Bitcoin software). You might have expected the transaction to be sent only to the person who is receiving the bitcoins, but that is not the case. In fact, that person does not even have to have their wallet software running for the transaction to be processed.

Some of the Bitcoin nodes which receive the transaction are Bitcoin miners. These miners gather the transactions they receive and put them into a block:

 header transaction 1 transaction 2 transaction 3
a Bitcoin block

A Bitcoin block consists of a header, followed by a list of transactions. The block shown here only has 3 transactions, but blocks containing thousands of transactions are most common.

Just as Bitcoin transactions are a string of characters, so is the block header. The header contains all the data needed to uniquely identify the block:

 version previous block hash merkle root timestamp bits nonce

Lets look at each of these fields within the block header:

The version is just a number indicating the current version of the Bitcoin protocol (i.e. the rules governing Bitcoin behaviour).

The previous block hash is where the blockchain concept comes in - the current block references the previous block so that blocks build upon each other over time, like so:

the Bitcoin blockchain

Looking at that diagram, we can see that the previous block hash value in the current block is found by doing a SHA265 hash twice in succession on all the data in the previous block header. For example, the previous block hash for block 1 would be found by hashing the entire block 0 header twice. As we saw in the hashing section earlier, doing two SHA256 hashes will only take a computer a fraction of a second to complete.

The merkle root is loosely defined as a hash of all transactions contained within the block. The transaction data is the pre-image and the merkle root is the hash. This is another useful feature of cryptographic hashing - a very small amount of data can be used to summarise a large amount of data. The transactions in a block generally take up over 1MB, but the merkle root is only 32 bytes (64 hexadecimal digits).

The timestamp is the current date and time of the block.

Bits is a field which denotes the current mining difficulty. It is a description of how many attempts, on average, a miner will need to make to find a solution to the test. As mentioned at the end of the previous section on hashing, the test in Bitcoin mining involves finding a hash that is lower than a given target. The bits value in the block header specifies what that target value is. The way this works is quite technical and is not necessary to understand Bitcoin mining; however, if you are curious, I have included full details in the annex. The basic principle, however, is simple - increasing the difficulty lowers the target value so that miners will have to do more hashing attempts, and decreasing the difficulty raises the target value so that miners will have to do fewer hashing attempts.

Finally the nonce is something we have already discussed in the section on hashing. The only difference here is that with Bitcoin the nonce is an integer.

OK, lets dive into a practical simulation of Bitcoin mining to see how all this works. Click the Mine manually with SHA256 button a few times and have a look at what this does, both to the results area and to the nonce in the block header:

 version previous block hash merkle root timestamp bits nonce

nonce: 0 target: block hash: status:

The data in the simulation block header is actually that of the very first bitcoin block ever. It was mined by Satoshi Nakamoto, the creator(s) of Bitcoin, on 3 January 2009.

As you can see, each mining attempt increments the nonce by 1. To find the block hash, all of the data in the block header shown here is hashed with SHA256 twice. I.e. it is all put together in one big string of characters and then hashed once with SHA256, and then that result is hashed with SHA256 again. There is a walkthrough of this process in the annex; however, the details are really not important in order to get a high-level understanding of how Bitcoin mining works.

The biggest apparent difference between this mining example and the one in the previous section on hashing is that the test here involves comparing two hexadecimal numbers, whereas previously the test involved matching a certain number of digits from the left-hand side. However, there is actually a lot of similarity between these two types of test. Let's forget about hexadecimal numbers for a moment and just look at some unrelated decimal numbers:

1000000000000 1000000

It is obvious that the first number is bigger than the second number. The first one is longer, so clearly it must be bigger. But how about if we zero-pad them i.e. put zeros before the left-most digit) so that they are the same length? They are still the same numbers, but now they are the same length:

1000000000000 0000001000000

How can we tell which is bigger? The easiest way is to begin at the left-hand side of the number and compare each digit:

1000000000000 0000001000000

Because `1` is greater than `0`, we know that the first number must be a bigger number.

OK, now what if we zero-pad them both to 64 digits? Again they are exactly the same numbers as before, and they are the same length, but now they have lots of leading zeros:

0000000000000000000000000000000000000000000000000001000000000000 0000000000000000000000000000000000000000000000000000000001000000

The way to tell which is larger is again to begin at the left-hand side and keep moving to the right until we find a digit that is different. The digit that is higher belongs to the bigger number:

0000000000000000000000000000000000000000000000000001000000000000 0000000000000000000000000000000000000000000000000000000001000000

That's the technique for decimal numbers, and it is exactly the same for hexadecimal numbers. The only difference is that decimal numbers go from `0` to `9` whereas hexadecimal numbers go from `0` to `f`, as you will recall from the start of this article. If you now go back and mine a few more times in the previous simulation then the results should make a lot more sense.

So finally we arrive at the end of this article on Bitcoin mining. You now know all about hashing and how hashing is used in Bitcoin mining. There is a bit more information in the annex to fill in some small gaps, however, everything already covered above is certainly enough to understand what Bitcoin mining is and to get a feel for the amount of effort that it requires even for the fastest computers on the planet.

All that remains now is to mine a block. We can cheat at this because the above block was already mined by Satoshi Nakomoto. If we inspect the blockchain we can see that the correct nonce is 2,083,236,893. Click here to copy the nonce back into the previous mining simulation and then click the Mine manually with SHA256 button to see what happens.

This section goes into all the detail skipped above. It is really just intended for those (such as myself) who like to leave no stone unturned. One thing that was not previously explained in detail was how the Bitcoin block hashes are derived from the block header. The block header is stored as bytes in the Bitcoin blockchain (1 byte is 2 hexadecimal digits). Previously the values for each field in the block header were shown in formats which are easy for humans to understand; however, conversions must be done to arrive at the storage method used by Bitcoin.

The version is stored in the blockchain as 4 bytes. Try altering the human-readable version value to see how this changes the value stored in the blockchain:

convert to hexadecimal: convert to 4 bytes (big endian): convert to little endian:

Note that converting to little endian format simply means reversing the bytes.

The timestamp is also stored in the blockchain as 4 bytes. This currently imposes some restrictions on the permissible date range. Try altering the human-readable timestamp value to see how this changes the value stored in the blockchain:

timestamp: convert to unixtime (integer): convert to hexadecimal (always 4 bytes - big endian): convert to little endian:

Bits, difficulty and target are three different ways of expressing the same thing - namely the amount of work involved in mining. Bits is a compact format used in the block header. It only uses 4 bytes, which saves a lot of space compared to the 32 byte target. Difficulty is the inverse ratio of a given target to the target in the very first Bitcoin block. Difficulty in the Bitcoin source code is a double precision number, which means that it is accurate to 15 significant digits. The Bitcoin source code has functions for converting between bits, target and difficulty.

Bits is a form of floating point notation. The first byte of the bits value is the exponent (called the size during the bits -> target and target -> bits conversions, and shift during the bits -> difficulty conversion) and the final 3 bytes of the bits value are the mantissa (called the word during the bits -> target conversion and compact during the target -> bits conversion). There is no reason for the different naming conventions - the Bitcoin source code is just inconsistent. Setting bit `00800000` in the bits value makes the target negative.

As discussed in the previous section on Bitcoin mining, target is used as the threshold during mining. It is a 32 byte (ie. 256 bit) number.

Difficulty is a human-readable indication of the amount of work involved in mining, relative to the work required to mine the very first Bitcoin block. So for example, a difficulty of 2 means that it will take twice as much work, on average, to mine a block as it took to mine the first block. Difficulty is calculated as:

```difficulty = first_block_target / current_target
```

The first block target was `00000000ffff0000000000000000000000000000000000000000000000000000`.

As the difficulty increases, the target decreases. This makes sense, since it takes more hashpower to mine a block hash below a lower target. According to the Bitcoin source code, the difficulty can never be negative, so converting a negative bits value to difficulty and back will give a different result to the original value.

In the following box you can convert between bits, target and difficulty. To perform these calculations I have carefully transcribed the c++ Bitcoin source code into Javascript which runs on this page. The textarea explains exactly what the original Bitcoin source code does to perform the conversions.

The Bitcoin source code has unit tests for the following conversions:

To ensure that the conversions in the previous box are accurate, I have reproduced those unit tests in Javascript here. Note that numbers in Javascript are IEEE 754 double precision, which means that they are accurate to 15 significant digits. Bitcoin also uses double precision for its difficulty values, so the results are compatible. Please click here to run the unit tests.

The human readable nonce is stored in the blockchain as 4 little endian bytes:

convert to hexadecimal: convert to 4 bytes (big endian): convert to little endian:

Now we can put all this together. In the following form, note how each field in the human-readable block header is converted to bytes to be stored in the blockchain, and how these are concatenated together. The block header is always 80 bytes:

 version previous block hash merkle root timestamp bits nonce

block header (hexadecimal): block header -> SHA256 -> convert to little endian: block header -> SHA256 -> SHA256 -> convert to little endian:

If you are very astute, you would have noticed that copying and pasting this block header into the SHA256 hash forms at the start of this article gives a different result to the SHA256 hashes here. This is because these hashes are implemented upon the pre-image as a hexadecimal number, whereas the hashes in the first section were implemented for a pre-image expressed in bytes. You can see the difference in the following form by ticking and unticking the pre-image is hexadecimal checkbox and observing how the resulting hash changes:

pre-image -> SHA256 -> pre-image -> SHA256 (little endian) ->

That covers most of the nitty-gritty detail regarding the process of hashing a Bitcoin block.

The final thing to discuss is the luck involved in mining. As you may have guessed, each Bitcoin block will contain different data to all the blocks that have come before it. No other block will have the same transactions, the same timestamp, the same previous block hash, etc, as the current block. This means that miners will need to try lots of nonce values in order to mine a block - i.e. they cannot simply guess the nonce value straight away. The more digits that must be matched, the more hashing attempts must be made on average. In fact the average number of hashing attempts needed to match a hexadecimal digit with a hash can be calculated using the following expression:

```average attempts = (16number of hexadecimal digits) / 2
```

I have created a difficulty calculator so you can see the average number of hashes that must be made for a given difficulty:

Of course, a miner may be lucky or unlucky. You will have noticed this when you tried mining in the final scenario of the cryptographic hashing section - sometimes you find a valid nonce in many fewer attempts than the average, and sometimes in many more. The process is random, just like trying to shake a 6 with a dice.

Interestingly, if 9 or more digits must be matched, then the nonce alone is not large enough for the average number of attempts that must be made. Matching 9 characters will require on average 34,359,738,368 double-hash attempts; however, the Bitcoin nonce field is only 4 bytes long and so has a maximum value of 4,294,967,295. What is a Bitcoin miner to do if it reaches 4,294,967,295 attempts and a solution has still not been found? One option is to increment the timestamp field in the block by 1 second and begin mining again with a nonce of 0. But what if the miners are so fast that they can hash at more than 4,294,967,295 hashes per second? In that case they can change some redundant data in the first transaction of the block they are currently mining and reset the nonce to 0.