March 28, 2020

Recreating Bitcoin 19:Proof of Work (Part II)

Epilogue #

Now let’s design a problem that requires Proof of Work to solve (POW).

Looking for the Random Number

Many times, in sleep you get the answer you would not get while awake. Satoshi was lucky to have experienced that. But it was not time for him to wake up yet.

“So what kind of problem can prove the work done by the node?” asked Tauren.

“I have precisely the problem in mind: finding a random number. You know, like guessing someone’s birthday, as long as you keep guessing, you can eventually guess it right with some effort,” Little Boy gave out his idea.
Tauren said, “I see. The nature of the problem is logic-less random collision. Such randomness is the fairest.”

“Yes! But it’d not be birthday we’d be guessing, but a random number, a number added to the message at the end of the message. And the Hash Value is asked for such that there are many zeros at the start of the value,” Little Boy continued to finish his thought.

“And we can make it five zeros at the start of the value. Anyone who wants the ledger-writing task must find this lucky number such that the Hash Value of ‘block message plus the random number’ starts with five zeros.”

“Five” here represented difficulty. Hash with more zeros meant higher difficulty.

After a pause, Little boy thought that the Tauren might not have understood him, so he started the actual demonstration:

Because the block message is longer, we use a short message instead: happy go lucky, and its Hash Value is:

7511cedf823f0757d66c26769c8d15f8597e4384420e6cbebb0acbec5e73344a.

We can see that usually the Hash does not start with 0.

The following task would be to find a lucky number such that the first five characters in the Hash are all 0.

We try adding something to the end of the message such as: Happy go lucky0 and get its Hash: 0b3844eec6204d01……

Because this Hash Value does not start with five zeros, it is not the answer.

Then we continue to try different numbers following such formular:

MESSAGE + NUM = HASH VALUE
Happy go lucky0 0b3844eec6204
Happy go lucky1 ebf1bbf0e1d2bc
Happy go lucky2 45963e7cbe226
Happy go lucky3 6b9e76dd1ca27
Happy go lucky4 ebf1bbf0e1d2bc
Happy go lucky5 6ec12dcfee54ffe
Happy go lucky6 53bde13314663
Happy go lucky7 d348d2eee3e8d
Happy go lucky8 276cfcd1386ffbd
Happy go lucky9 f78628f2b0e4e
Happy go lucky10 fe2e8cd0e0f3
Happy go lucky11 5cc0bc8d34f5fb
Happy go lucky12 764154ddd623
Happy go lucky13 e6c3bcb245fd
Happy go lucky14 7c18fb827e48
Happy go lucky15 283f7de03f01
Happy go lucky16 bce71436c4e
Happy go lucky17 4f76be60fb2b
Happy go lucky18 182530c711d1
Happy go lucky1e 6d5ec71c30c1
Happy go lucky20 b0161336bbbe
Happy go lucky21 d1f35d0522b3d
Happy go lucky22 e118e2ce041d
Happy go lucky23 052083fffd51d

We managed to find one that started with 0 but didn’t find one that started with five 0s. We didn’t even find one that started with two 0s. Keep looking…

Happy go lucky520 e1f34d0t22b3
Happy go lucky521 g11ee2cg04sd
Happy go lucky522 0092e10ae10a

Finally, in the 523th try, we find a prefix with a hash value of two consecutive 0’s. Keep looking…

Still looking….

After a long, long time, we finally found it!

Happy go lucky832290344 00000d4955bc5445e97

We see that this Hash starts with five zeros, so 832290344 is the lucky number we’re looking for. Note that this is after more than 800 million guesses. We know that Hash values can’t be derived backwards, so they can only be randomly produced, and these 800 million random tries are proof of the work that I have done.

The node that got that right gets the ledger-writing task and broadcasts the message to other nodes. Tauren receives it and calculates its Hash. He got five zeros.

Since Tauren can then determine that Little Boy has done the necessary work, the transactions in the block that he produced can also be trusted with a reasonable level of validity. Then Tauren synchronized the update to his ledger while broadcasting it to other nodes.

Other nodes do the same until ledger is synchronized across the network and the block becomes the latest page in the ledger.

Structural Change in Block #

Now we take a look at how to add the Proof of Work mechanism into the block structure.

We can put the random number in the Header of the block and add another text in the Header as computing difficulty, a difficulty of five being a Hash Value that begins with five zeros for example. The difficulty changes based on the most recent 2016 blocks in order to keep the difficulty at around ten minutes (see graph below).

(Note: in the actual Bitcoin, Difficulty is be replaced by nBits. For simplicity purposes Difficulty is used here.)

Block structure after the addition of random number and difficulty

Block Header Chain #

Tauren said, “I discovered a problem: for every search for random number, while running the Hash function, the block data are read into the memory and sent over to the Hash function for computing, right?”

Little Boy replied, “Yes, of course. Memory is needed.”

“How much memory do you have?” Tauren asked.

“512MB is what I have for now,” Little Boy answered back. “Okay, I see what you are saying. As the network scales, the number of transactions increases too, which means the block size only gets bigger. When the block size supersedes the memory limit, the Hash function could not run.”

“Exactly,” echoed Tauren. “My memory is even smaller. Going like this, we’d be competing over the size of our server’s memory.”

“That sounds about right. It’d be not just who does more work, but who’s fatter. We need a solution,” Little Boy said.

“I have an improvement plan, and although it doesn’t solve the memory problem completely, but the burden for the system could be greatly alleviated,” said Tauren.

Overall, Tauren’s plan is to break the random number into two parts:

The first part is to replace transaction data with a digital signature. That is, the Hash Value of the block’s Transactions would be a part of the digital signature of the Transactions. The purpose of the digital signature is to make it possible to unidirectionally verify if the data in the Transactions part have been falsified, since one unwanted change in a given transaction would not produce the same digital signature.

The second part is to use the Hash Value of the Header to replace the Hash Value of the Block. That is, the digital signature obtained in the previous step would serve as the newly added script - Transactions Hash – into the Header. As digital signature can authenticate the data, Transactions Hash could represent Transactions, which means that Header could represent the whole block. Therefore, looking for the random number has got from looking for the Hash Value of the block to computing for the Hash Value of the Block Header.

The first part needs to only be run once, while the second part needs to be run several times, which would still restrict the memory issue to one part and hence reduce the network’s throughput burden. As the operation system possesses virtual memory capabilities, disk space could act as memory virtually. Although the processing speed would be slow, as the part one only runs once, it is still acceptable (see graph below).

The Transactions script added to the Header

Header could represent the whole block, and Header’s Hash Value could represent the Hash Value of the previous block. Basically, the Block Chain has become Block Header Chain.

Block Header Chain essentially solves the scalability issue that as the system scales, Transactions become larger, but Header stays the same, never exceeding 1KB, even if Transactions get above 2TB. The benefit is that for some nodes, even if certain Transactions data are shortened, as long as the Header is whole, block data can still be verified.

In other words, the cost of maintaining Bitcoin’s integrity is very low (see graph below).

Block Header Chain

Merkle Tree #

Next, we focus on the memory crisis of the first part.

Since we can’t eat an elephant in one single bite, we have to buy space with time. like ants finish up a large chunk of food, we do it piece by piece, many, many times. combination of Hash values together.

For example, we assume that the current Transactions include: TxA, TxB, TxC, TxD.

By multiple times, we compute the Hash Value individually: HA = Hash (TxA), HB = Hash (TxB), HC = Hash (TxC), HD = Hash (TxD).

In addition, we compute the aggregate Hash Value of the transactions two at a time: HAB = Hash(TA+HB), HCD = Hash(HC+HD).

So on and so forth, we have the last Hash Value: HABCD = Hash (HAB+HCD).

This sorting method that organizes all transactions is called Merkle Tree, and the last root in the final round is Merkle Root (see graph below).

Merkle Tree

Merkle Tree not only solves the memory crisis, but also the storage problem.

This means that by adopting the first Transaction Hash plan, when a SPV with small a memory and storage verifies if the block data have been modified, the block could have been too large to be completed, as the storage might not be big enough for the Transactions.

Merkle Tree solves the problem by providing a highly efficient if a transaction has been modified.

For the following Merkle Tree (see graph below):

Merkle Tree’s verification process

To verify that Transaction K is in the block, we can use the Hash Values - HLHL, HIJHIJ, HMNOPHMNOP and HABCDEFGHHABCDEFGH – to construct a Merkle path that only requires 128 bytes. Any SPV only needs to send a verification request to a full node to receive a 128-byte Merkle path from it, rather than the block’s Transactions. SPV can then verify the previously stored Merkle Root in the Block Header Chain to verify.

The last step would simply be to replace Transaction Hash with Merkle Root in the Block Header. (see graph below).

SPV Node only needs to store Block Header Chain

Version 0.1.0 #

Suddenly, Satoshi woke up. With a fresh memory, he started to change the code with his new ideas.

After two weeks of work, the Bitcoin system was upgraded, and POW has replaced the Timestamp Server solution. So far, Bitcoin had eliminated all single points to become a swarm system.

From another perspective, the Bitcoin system was also the first distributed Timestamp Server.

Since the upgrade was a monumental milestone, Satoshi named this upgrade v0.1.0.

The following graph shows the new features in the new system.

Full node functionalities of v0.1.0

Full node included the following components:

Network connection: enables the autonomous governance of the Bitcoin network
Transaction processing: enables the processing of Bitcoin transactions in the present mode
Block processing: enables the backup of Bitcoin transactions in the past mode
Transaction memory pool: stores present transaction data
Block chain: stores past transaction data

The new component is block processing:

Random number calculation obtains a random number as explained in the POW concept
Block production: updates the ledger with the random number calculated and broadcasts the block to other nodes to receive the block reward. If the random number is not yet obtained, the node gives up its block to chooses the block passed on by other nodes
Block synchronization: synchronizes block information from other nodes to its local block chain
Block verification: verifies the synchronized block is valid through verification processes

Since block production and computing the random number is for the purposes of earning block rewards and transaction fees, we can liken it to mining gold under the ground. We call this act in the block chain network “mining” and the full nodes doing the mining “miners” (see graph below).

Set in stone: once v0.1.0 is launched, the core design remains perpetually the same throughout Bitcoin’s life cycles

Competition #

The three computers went into a frenzy of buzzing the moment the upgrade was complete, mining for the block reward every second and aiming to become that first lucky miner.

Every competition cycle is ten minutes, reset every cycle.

We focus our attention to the competition between Little Boy, Tauren, and Greedy Wolf.

Little Boy was computing for the random number on his own, when suddenly he sees a new block message sent by Node 3. Node 3 was able to do so most likely because he had superior machine specs. Realizing that he had lost this round of competition, Little Boy added this block to his ledger and started the next round of computing.

At the same time, Tauren and Greedy Wolf had received the new block from Node 3 and synchronized the block for the next cycle.

As we can see, the propagation of the new block in the network is similar to the ripples stirred up by a point in the middle of the ripples. The new cycle is announced where the previous cycle ends.

Nodes propagation block information in the network

Building a block #

The new cycle began.

Little Boy first built his own block data and put transaction data he selected from the memory pool to his block. The amount of data could range from hundreds to thousands of transactions.

This meant that the block was different depending on the miner that built it.

For more transactions in the block, the transaction fees the miner earns also increases, but the tradeoff is that the processing logic and propagation speed would slow down. Therefore, this is a choice left to the miners themselves.

For certain miners even, they would leave zero transaction record in a block just for the sake of speed. The block is what’s called an “empty block.” It does not break and rules and hence must be accepted by the network if that is the case.

Little Boy ranks the transactions based on the transaction fees from high to low and selected the first hundred transactions to add to the Transactions part of the new block.

He finished the Header text except for the random number part. Now his work began.

Meanwhile, Tauren and Greedy Wolf were doing the exact same things. This time, Greedy Wolf went for it again, changing the block reward from 50 to 500.

Moreover, he created an empty block, only including the transaction that gave him the block reward and started working for the random number.

In fact, Greedy Wolf had been thinking before this cycle started if he could start computing for the random number before this cycle. He couldn’t because the Header of the new block must include the Hash Value of the previous block, which meant that the computing had to start after the previous block’s information was received.

Block propagation #

After about ten minutes of mining, Greedy Wolf found the random number at the mark of 10 minutes and 11 seconds, followed by Little Boy at 10 minutes and 13 seconds and Tauren at 10 minutes and 14 seconds.

Greedy Wolf immediately added the number to the block’s header and broadcasted his block to other nodes.

Little Boy and Tauren also sent their blocks to the rest of the network.

From then now it was up to the choosing of other nodes. Since the three blocks were almost sent simultaneously, there was still room for competition. It’s like having three waves on the surface of water at once.

Three nodes are like three waves

Block verification #

Because Bitcoin’s peer-to-peer network is very much like a water surface, there is a high probability that the first wave will propagate across the entire water surface first.

Sure enough, the Greedy Wolf’s block message is received first by other nodes, but the nodes won’t blindly add this block to their own ledger.

The first test is on the syntax of the block and the validity of the transactions.

When the nodes discovered that the Greedy Wolf’s block reward is not consistent with the agreement, they frowned and all decisively gave up the Greedy Wolf’s block message.

Then the nodes received the block from Little Boy, and they broadcasted it to the rest of the network instead of Tauren’s block because Little Boy was ahead of him for one second.

The verification on Little Boy’s block passed with no issue detected, and his block was added by other nodes to their block chain.

And then all the nodes immediately dived into the next round of mining competition.

Network flexibility #

A question at this point is that since there would be some nodes closer to Tauren that added his block first, would they not have to forfeit the block?

The answer is, in fact, a no. After the nodes received the block from Tauren, they would not immediately add the block to their block chains. Instead, they would only do so after checking if their own neighboring nodes had the same block information. Otherwise, they would know that Tauren’s block was not the first block to be produced. When they found out that seven out of ten neighboring nodes were broadcasting Little Boy’s block, they would instead choose that one to add to their block chain.

On the other hand, special cases do exist. If a small group of nodes chose to add Tauren’s block to their block chain, then two ledgers would exist simultaneously in the network. This would be called a temporary fork in the block chain.

Fork

We will talk more about forks in the next chapter.

Competition protects the network #

Let’s go back and look at the poor Greedy Wolf, who feels like he lost a hundred million as his block was abandoned by most nodes.
His work spent on the block was all wasted as well.
Greedy Wolf paid for this lesson dearly.

“Voting” #

From the previous cycle of competition, we can see that the process where nodes choose which block to add to their block chain is equivalent to the process of voting for the block they acknowledge.

They vote for the block they believe to be valid and earliest to be produced.
Democratic voting, based on competition, can move society in the right direction.

Epilogue #

Bitcoin in itself is the wheel, METANET is the car. Bitcoin is the universal currency in its global ledger, providing the fuel for this car and guarding the economic incentive and the security of its immutable ledger. Only with utility value does it become a universal currency or the property of money. When building a car, we first build the wheels and then the chassis.

In the next chapter, we will talk about forking.

Next chapter ：Recreating Bitcoin 20:The Reorganization and Division of
Forking