Bitcoin Mining Algorithm Explained

With the current mining craze, A very frequent question I ask about mining is: "What is my PC actually doing?"
So for those people, I have decided to make this post.
It is my first post here on Steemit :)

This post does assume that you already know what mining does in the global lines.
If not, then go watch this video first:
[embed]

[/embed]

It also assumes that you know what hashing is and what it does.
If not, then go watch this video:
[embed]

[/embed]

I have written the protocol in Python for this demonstration.
The core principle will remain the same across all the programming languages, however, the exact way it is done will differ.
This post also only takes into account the SHA256D hashing algorithm used by Bitcoin.
While other coins like Litecoin (Scrypt) and Ethereum (Ethash) still use this general principle, the specifics (eg. outputs) might be different.
Now that we have that out of the way, let's get into it!

Proof-of-Work and Difficulty

First of all, why does Bitcoin require so much hashing power in the first place?
Bitcoin uses an algorithm that is called proof-of-work (PoW).
This function basically requires you to be able to show that you've put a certain amount of effort in a hash.
You can compare it to a school project.
You don't just have to make the project, but also put some effort in it (which can be proven both by the way it looks, the way it functions and whether it satisfies the evaluator's requirements).
In Bitcoin, this is exactly what the PoW algorithm is for!
Take block #505259 for example:
it has the following hash:

0000000000000000006b7c05a0f698a1e2f848f283ecc3cd0c8b8763a152ca00

You see all those 0's in front?
That is the requirement for the PoW algorithm!
The more 0's a hash needs, the more difficult it is to find a working hash!
As you know, a hash changes dramatically when changing even the slightest amount of data.
And you have to change a specific value a lot in order to find a suitable hash.
This is also what is called the mining difficulty, as it requires exponentially more effort to find more 0's in your hash.
One 0 can be found quickly by any CPU.
Two 0's takes a bit longer, but still doesn't take a lot of time either.
Three 0's can be noticeable depending on the CPU.
Four 0's can take a bit of time depending on the CPU.
Five 0's might take you a while depending on the CPU.
Six 0's can take ages depending on the CPU.
Seven 0's can take you a long time.

This difficulty (the amount of 0's it takes to find a satisfying hash) is adjusted to become more or less as the total network hash rate decreases or increases.
This is done to make the amount of time in between blocks somewhat stable.
Remember, the higher the hash rate, the sooner you will find a satisfying hash, thus find a block.

Not only that, but even with the same amount of 0's, you also need to get your hash below a certain target.
For example, you and your friend throw two stones each.
The target is at 10 meters, but here are some rules:
You can't go over 10 meters (the target).
You can't go below 9 meters (can be compared to the amount of 0's needed in a hash).
Your friend throws his first stone and it lands at 10.5 meters.
Then it's your turn.
You throw your stone and land at 10.2 meters.
You are still too far away in order to win.
Your friend then throws his other stone.
It lands at 10.1 meters.
Still not close enough.
You then throw your other stone.
It lands at 9.9 meters.
Your stone is landed farther than 9 meters (thus has enough 0's) and closer than 10 meters (the target).
Therefore, you win!

So what are we hashing exactly

Second, we need to know what we are hashing exactly.
The In Bitcoin, we hash a so-called "block header".
This header contains all the information we need in order to both satisfy the PoW algorithm and validate a block (and making transactions permanent).
This is the data that we need to hash in order to create our block:

Field	Purpose	Updates when...	Size (bytes)
Version	The Block version	You upgrade the software and it specifies a new version	4
hashPrevBlock	The hash of the previous block	A new block is mined	32
MerkleRoot	a MerkleRoot hash of all transactions in the block	A transaction is accepted by the miner	32
Timestamp	The current timestamp in seconds since the epoch	Every few seconds	4
Bits	Current target in compart format	The difficulty is adjusted	4
Nonce	32-bit integer starting from 0	A hash is tried (incremental)	4

So now that we have the data we need, how do we create our block header?
Well, this is where my Python code comes in :)

First of all, we gather all of our variables.

In this example, I'm using the data of block #286818

We then take our block version and pack it into a 4-byte Little-Endian.
If you don't know what that is, go read that up here.

Next up, we take the hash of the previous block and reverse it (so the 0's are now in the rear, this is the internal format for the hashes).

We do the same with our merkle root.

We then pack our timestamp into a 4-byte Little-Endian aswell.

Now comes something interesting: We are gonna extract the target hash from our bits.
As I've already explained earlier, the target makes it slightly more difficult to find a suiting hash.
We get our target by doing a right bitshift in order to get the exponent of the bits.
A bitshift literally just moves binary bits of a value to the right.

So, for example:

The 4-bit binary value of 10 is 1010.
We move those bits to the right one time and end up with 0101.
The decimal value of 0101 is 5.

In our script, however, we do this 24 times.
This is a somewhat dirty way to accomplish this, but it works.
This gives up the value of 25

We then get the mantissa of our bits.
Basically what we do is mask our bits with 0xffffff.
This way, we end up with only the last 8-bits of our bits.
This leaves us with our mantissa.
Which in this case is 89939 (mathematically speaking it is 0.89939 but we strip off the 0. automatically)

Now that we have our exponent and mantissa, we can calculate our actual target using some dark voodoo magick!...
I mean math.
Our formula is as follows:

1. We take our exponent and subtract 3 (=22).
2. we multiply that by 8 (=176).
3. we bitshift the binary value of 1 176 times to the left (=95780971304118053647396689196894323976171195136475136).
4. We take the modulus of %064x and 95780971304118053647396689196894323976171195136475136 (= our target)

Now that we have that, we can continue preparing our block header.
Next up, we pack our bits and our nonce into a 4-byte Little-Endian.

We then slap all of our values together into out block header!

We then hash our block header using SHA256 twice ("creating" the SHA256D algorithm).

We then reverse our output hash and compare it against our target (again, the hash value has to be lower than our target!)

If we have a valid block, we can then broadcast it to the network together with all the data we used to get this block (so that they can verify wether you didn't cheat).

Now that we're on the topic of cheating, with Mining, it is very difficult to cheat.
Everything can be re-checked on validity.
Remember, if you change even the slightest value, the entire hash will change :

And with that said, you should now know how the bitcoin mining algoritm works!
At least, I hope you do.
If you don't understand it yet, please don't hesitate to ask me a question down in the comments.

I'll see you on the blockchain!