Blockchain (Part 2) - Mining

I have discussed minutely about mining and Proof-of-Work in Part 1 of the article. I'll try to explain the technical details of mining and its benefits in Blockchain and how it is used in Bitcoin.

To reiterate what I discussed in first part about mining, there are special nodes on the blockchain network which are dedicatedly running an algorithm to validate the transactions being generated on the network. Miners validate the transactions in a batch (for Bitcoin blockchain, each block is ~1MB in size). This Batch is called a Block and it has a specific format containing the Block ID, Transactions contained in that Block, Hash of the previous approved block on the chain, and hash of the whole Block. Since every block is connected to its predecessor by linking to the Hash of its previous block, all the blocks are tied together like a chain, starting from the very first Block called the Genesis Block.

The Miners are always looking for new transactions and when they find new pending transactions, they start validating the transactions to form a Block. Validation process is a multi step process and goes through different set of rules called Transactional consensus (For Bitcoin this is a collection of almost 20 rules which can contain verification that the same coins are not already spent or that the sender actually had the coins that he sent to the recipient or as minor validation as checking the syntax and size of the transaction and so on).

Once a miner validates the transactions, he forms a Block. However, he is not yet ready to broadcast this Block to the network. The miner who has validated the block is required by the BlockChain to provide a Proof-of-Work. Proof-of-Work is a computation-intensive task that a Miner needs to attach to every Block that he has validated. Once he comes up with the solution to the computation problem, he broadcasts the block along with the solution so that other miners in the race can validate his block and his block can be accepted by the network. Once more than 50% of the network accepts this Block, only then the Block is said to be finally mined and the other miners will leave the race for the current block and start mining for the child of the newly created block.

For the Bitcoin Network, the computational difficulty of this computation problem is adjusted dynamically, so that the problem can not be solved easily and it takes ~10 minutes to mine a single block.

This Proof-of-work is the most important aspect of Blockchain that helps in making the whole Blockchain immutable. Since the Proof-of-Work is a resource intensive task, it becomes impossible for any fraudulent Miner to go back and change any transaction and mine that Block again. Changing any minute detail in the Block's data means that the Hash of that Block is changed and since it is linked to each Next Block in the chain, the Hash of every following Block changes. this means that the Miner has to Mine each Block again and propagate all the blocks collectively to the network. However, he has to do that in the same time that the other miners are racing to mine the latest single block. So for example there are 10,000 Blocks on the Blockchain, and a miner changes a transaction in the 9,997th Block. So the hashes of 9,997th , 9,998th, 9,999th and 10,000th blocks all change and he has to mine all these Blocks to validate them all and propagate them to the network, however he has to do that in only 10 minutes where other miners are racing to Mine a single Block 10,001st. So unless the fraudulent Mines owns more than 51% of the total network computational resources, he wont be able to do so and other honest miners will keep winning this race and thus keep the whole BlockChain validated.

To summarize again:

1. The transactions are happening between different nodes on the network, all the time. These transactions are not accepted until validated in a Block.

2. Special nodes, called Miners, pick up a number of transactions (total of ~1MB in size for Bitcoin network).

3. They first validate all the transactions to see that all the transactions are fair and valid and does not contain any fraudulent transaction with problems like double-spend etc. (there are actually 20 rules specifically for Bitcoin network that this step undergoes. These validation rules are called transactional consensus).

4. Once the transactions are validated, the miners create a Block of the transactions he picked. This Block contains a sequential ID, the Transactions picked by the miner , SHA256 Hash of all the values and Hash of the Previous Block.

5. The BlockChain Consensus requires the miners to resolve a computational-intense hard mathematical problem to sign the generated block before broadcasting it to the network.

6. The other miners validate the solution of the problem and if validated accepts the block and starts the race for the next block.

So, why is this process called Mining (in Bitcoin or CryptoCurrencies)?

Since this process is highly resource (as well as energy) intensive, it requires special Hardware and a supply of real cheap electricity to solve the computational problem. To incentivize each miner, the winning miners win a number of Bitcoins once their Block gets accepted in the Blockchain. This actually solves another purpose. The coins that Miners are gifted for mining a successful Block are actually NEW COINS in the Bitcoin network. The Proof-Of-Work not only validates the transactions and blockchain but also generate the new coins.

The Mining Algorithm for Bitcoin

So, everyone must be wondering what is this computational intensive problem that I have discussed throughout this article and in Part 1. So, Take a deep breath and read along.

To understand the mining algorithm used in Bitcoin, lets do some maths (and computer science) first. As I mentioned earlier, each Block creates a SHA256 Hash and uses this Hash to Link to the next block in the chain. SHA256 hash is a function where you can input a text of any length (20 Bytes or 2 GB), it generates a random string of 256 bits (32 bytes). For example, SHA256 of string "Amrit" is

0BC745BCD04E807CBA0F38D7086FC5A3F774CBFD596F5BE7D796EC01C9B908EC

however, if I change just a single character in the string, the Hash changes totally, which make it almost impossible to predict the input from the output. For example, the SHA256 of the string "Amrit1" is

7C91A443EE568C9D29CEE938D463035D6256DDE3CE830926D31EB326A4F949EF

However, SHA256 always generate the same hash for the same input (deterministic), so, if someone else knows the string "Amrit" he can generate the same Hash and can validate that this was indeed the correct hash and can validate it.

 Now, Since the hash generated by SHA256 is totally random and deterministic, the bitcoin Proof-of-Work uses these two properties to create a hard computational problem which can still be validated.

The Bitcoin Consensus algorithm states that the Hash created from the Block Data should contain 0 as the first X bits of the Hash. Consider that a miner after validating a Block, generates following Hash :

D1F2C5659647378AE5B3C452150ECF47F5527AE15240721F9DE4FADC7C63DA45

however, to provide a proof of work, he will have to find a Text which when added to this Hash will generate a Hash containing first, say, 64 Bits of data 0. Something like:

00000000EBB479FD3E4AA8A65303C7628743FEEF846040E10DB6542B9CE2749F

To understand why this is difficult to calculate, consider the following mathematical problem.

Lets say, I have a Coin and I flip that coin, what is the probability that coin will yield Head (0). 50% . Since there are only two possibilities head (0) and a tail (1), probability of head(0) is 50% or 1/2 .

Consider I have two coins and I flip them together, what is the probability that both the coins yield heads together. 25%. Since there is 1 out of 4 possibilities (HH, HT, TH and TT), the probability is 25% or 1/4. 

Consider I have three coins and I flip them together, what is the probability that all the three coins yield heads together. 12.5%. Since there is 1 out of 8 possibilities (HHH, HHT, HTH, HTT, THH, THT, TTH and TTT), the probability is 12.5% or 1/8.

Similarly, if I have 64 coins and I flip them together, the probability of all the coins yielding heads together is meager 1/2??. 

Similarly, I need to do 2?? calculations before I can probably find a number that yields first 64 bits of a Hash as 0. To understand the complexity of this astronomical number 

232 is 4 billion

2?? is 4 billion X 4 billion 

and the miners have to do these many calculations in under 10 minutes to find the right number (called nonce) that generates the Hash according to the Blockchain consensus and broadcast this before any other miner does that in 10 minutes.

So this is what Mining and Proof-Of-Concept does and makes the whole BlockChain immutable by design.