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.)

图片 1.png

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).

图片 1.png

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).

图片 1.png

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).

图片 1.png

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):

图片 1.png

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).

图片 1.png

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.

图片 1.png

Full node functionalities of v0.1.0

Full node included the following components:

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

The new component is block processing:

  1. Random number calculation obtains a random number as explained in the POW concept
  2. 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
  3. Block synchronization: synchronizes block information from other nodes to its local block chain
  4. 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).

图片 1.png

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.

图片 1.png

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.

图片 1.png

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

CONTENTS #

Recreating Bitcoin:A Fictional Story of Why Bitcoin was Designed This Way

Part one : Transactions
Recreating Bitcoin 1:Start over with a Simple Web Transaction System
Recreating Bitcoin 2:First Version is Online!
Recreating Bitcoin 3:Getting Rid of the Account Model
Recreating Bitcoin 4:Digital Signature
Recreating Bitcoin 5:Public Key and Private Key
Recreating Bitcoin 6:Version 0.0.2 is Online!
Recreating Bitcoin 7:UTXO
Recreating Bitcoin 8:System Refactoring Based on UTXO
Recreating Bitcoin 9:Everything is Transaction
Recreating Bitcoin 10:Transaction Script

Part Two : Swarm System
Recreating Bitcoin 11:Swarm System (Part I)
Recreating Bitcoin 12:Swarm System (Part II)
Recreating Bitcoin 13:P2P Network
Recreating Bitcoin 14:Synchronizing Transactions
Recreating Bitcoin 15:Synchronizing Ledger
Recreating Bitcoin 16:Block chain
Recreating Bitcoin 17:Network Flexibility
Recreating Bitcoin 18:Proof of Work (Part I)
Recreating Bitcoin 19:Proof of Work (Part II)
Recreating Bitcoin 20:The Reorganization and Division of
Forking

Complete book selling at Amazon( > US > UK > CA > JP > DE > FR > ES > IT) #

amazon.png

BSV Donate:
1Djc4TdVBi8urzmSXKHwg8cpEAYKcRQxgY

©2019 - Recreating.org all rights reserved

 
1
Kudos
 
1
Kudos

Now read this

重新创造比特币18:工作量证明(上)

作者:何岩,由 recreating.org发行。 0.前言 # 上一篇,Bitcoin的点对点网络演进成了一个可以自治的群系统。 这一篇,我们将解决最后一个遗留的难题,那就是分配记账权的单点:Timestamp Server 1.最后的单点Timestamp Server # 一大早,中本聪和Gilfoyle就来到了咖啡馆,Bitcoin的记账网络演进成了真正意义上的群系统,这让他俩很兴奋,他俩想乘胜追击,一口气拿下最有一个难题,系统中最后的单点:... Continue →