Recreating Bitcoin 19:Proof of Work (Part II)
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:
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…
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 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).
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).
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) #
Next chapter ：Recreating Bitcoin 20:The Reorganization and Division of
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
©2019 - Recreating.org all rights reserved