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.

Note: More important content is left (about half of the full text). #

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

amazon.png

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

BSV Donate:
1Djc4TdVBi8urzmSXKHwg8cpEAYKcRQxgY

©2019 - Recreating.org all rights reserved

 
1
Kudos
 
1
Kudos

Now read this

比特币经济学 12 : 族群矛盾

比特币经济学:基于BitcoinSV的全新视角来重新构想世界经济格局 # Recreating Economics based on Bitcoin : Reimagining the world economic landscape based on a new perspective of BitcoinSV # CONTENTS (目录) # 比特币经济学 : 首页 比特币经济学 1 : 开讲 比特币经济学 2 : 法律 比特币经济学 3 : CSW 比特币经济学... Continue →