Blockchain on Go. Part 2: Proof-of-Work

Hi, Habr! I present to your attention the translation of the article " Building Blockchain in Go. Part 2: Proof-of-Work ".

Content

1. Blockchain on Go. Part 1: Prototype
2. Blockchain on Go. Part 2: Proof-of-Work
3. Blockchain on Go. Part 3: Permanent Memory and Command Line Interface
4. Blockchain on Go. Part 4: Transactions, Part 1
5. Blockchain on Go. Part 5: Addresses
6. Blockchain on Go. Part 6: Transactions, Part 2
7. Blockchain on Go. Part 7: Network

Introduction

In the previous article, we built a very simple data structure, which is the basis for the blockchain database. We also added blocks with a chain link between them: each block is connected with the previous one. Alas, our implementation of the blockchain has one major drawback: adding blocks to the chain is too simple and cheap.
')
One of the cornerstones of Bitcoin and the blockchain is that adding new blocks should be a rather complicated job. And now we are going to fix this flaw.

Proof-of-Work (PoW)

The key idea behind the blockchain is that in order to add a new block it is necessary to do some complicated work. It is this hard work that makes the blockchain reliable and complete. In addition, remuneration is paid for this difficult job (that's how people get coins for mining).

This mechanism is like a real life: you have to work hard to get rewards and ensure your life. In the blockchain, some participants (miners) of the network are working on maintaining the network, adding new blocks to the blockchain, and are rewarded for their work. As a result of their work, the block is built in to the blockchain in a reliable way, which ensures the stability of the entire blockchain database. It should be noted that the one who performed the work must also prove that it was done.

This whole "do the hard work and prove it" -the mechanism is called Proof-of-Work (proof of work). It is complicated because it requires large computing power: even high-performance computers cannot quickly complete it. Moreover, the complexity of this work is gradually increasing in order to create on average about 6 blocks per hour. In Bitcoin, the goal of such work is to find a hash of a block that satisfies certain requirements. This hash is evidence. Thus, the search for evidence is the actual work.

One thing to be noted: Proof-of-Work algorithms must meet the following requirement: the work must be complex, but the proof must be simple. Testing the evidence is usually passed to someone else, so this check should not take a lot of time from them.

Hashing

This part is dedicated to hashing. Those who are familiar with this concept may skip this part.

Hashing is the process of getting a hash for some data. A hash is a unique representation for the data for which it was calculated. A hash function is a function that, for data of arbitrary size, receives a hash of a specific size. Some key features of hashing are:

1. Initial data cannot be recovered from the hash. Thus, hashing is not encryption.
2. A hash for specific data is always unambiguous and unique.
3. Changing one byte in the data results in a completely different hash.

Hash functions are widely used to verify data integrity. Many software providers publish together with the software its checksums. After downloading the file, it is necessary to feed the hash function, and then compare the resulting hash with that published by the software developer.

In the blockchain, the hash is used to ensure the integrity of the block. The input data for the hashing algorithm contains the hash of the previous block, which makes it impossible (or at least very complicated) to change the block in the chain: you have to recalculate the hash of the block itself, as well as the hashes of all the blocks following it.

Hashcash

Bitcoin uses Hashcash , a Proof-of-Work algorithm that was designed to protect against spam email. The algorithm can be divided into the following steps:

1. Take publicly known data (for email, this is the recipient’s address; for Bitcoin, this is the block header
2. Add a counter to them. The counter starts from zero
3. Get hash from combination +
4. Check if the hash meets certain requirements.
   1. If yes, then everything is ready
   2. If not, increase the counter and repeat steps 3 and 4

Thus, this is a brute force algorithm: change the counter, calculate the hash, check it, increment the counter, calculate the hash again, and so on. That is why the algorithm is computationally expensive.

Now consider the requirements that the hash must satisfy. In the original Hashcash implementation, the requirement sounds like "the first 20 bits of the hash should be zero." In Bitcoin, the requirement is corrected from time to time, because according to the plan, the block should be generated every 10 minutes, despite the fact that the computing power grows with time and more and more miners join the network.

To demonstrate the algorithm, take the previous example (“I like donuts”) and find a hash that starts with three zero bytes.



ca07ca is a hexadecimal representation of the counter, which corresponds to the number 13240266 in the decimal number system.

Implementation

So, the theory is finished, let's proceed to the code. First, let's define the complexity of mining:

 const targetBits = 24 

In Bitcoin, “target bits” is a block header field that stores the complexity on which the block was extracted. We will not build a corrective algorithm, so we define complexity as a global constant.

24 is an arbitrary number, our goal is to have complexity that takes less than 256 bits in memory. And we want the difference to be significant enough, but not too big, because the bigger the difference, the harder it is to find the right hash.

 type ProofOfWork struct { block *Block target *big.Int } func NewProofOfWork(b *Block) *ProofOfWork { target := big.NewInt(1) target.Lsh(target, uint(256-targetBits)) pow := &ProofOfWork{b, target} return pow } 

Here we create create ProofOfWork , which contains a pointer to a pointer to a block and a pointer to a target. “Target” is another name for the requirements described in the previous section. We use big integer because of the way the hash is compared to the target: we distribute the hash into the big integer and check if it is smaller than the target.
In the NewProofOfWork function NewProofOfWork we will initialize big.Int value 1, and then shift by 256-targetBits bits. 256 is the length of the SHA-256 hash in bits, and we will use this hashing algorithm. Hex target view:

  0x10000000000000000000000000000000000000000000000000000000000 

And it takes 29 bytes in memory. And here is a visual comparison with the hashes from the previous examples:

 0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3 0000010000000000000000000000000000000000000000000000000000000000 0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca 

The first hash (calculated for “I like donuts”) is larger than the goal, so this is incorrect proof of work. The second hash (calculated for "I like donutsca07ca") is smaller than the target, so this is a sure proof.

You can consider the target as the upper limit of the range: if the number (hash) is smaller than the limit, then it is suitable, and vice versa. Lowering the border will reduce the number of suitable numbers, thereby increasing the difficulty of finding the right one.

Now we need data for hashing. Let's prepare them:

 func (pow *ProofOfWork) prepareData(nonce int) []byte { data := bytes.Join( [][]byte{ pow.block.PrevBlockHash, pow.block.Data, IntToHex(pow.block.Timestamp), IntToHex(int64(targetBits)), IntToHex(int64(nonce)), }, []byte{}, ) return data } 

This piece of code is quite simple. We simply combine the fields of the block with the goal and "nonce". nonce is a counter from the Hashcash description; this is such a cryptographic term.

So, all the preparations are made. Now we implement the core of the Proof-of-Work algorithm:

 func (pow *ProofOfWork) Run() (int, []byte) { var hashInt big.Int var hash [32]byte nonce := 0 fmt.Printf("Mining the block containing \"%s\"\n", pow.block.Data) for nonce < maxNonce { data := pow.prepareData(nonce) hash = sha256.Sum256(data) fmt.Printf("\r%x", hash) hashInt.SetBytes(hash[:]) if hashInt.Cmp(pow.target) == -1 { break } else { nonce++ } } fmt.Print("\n\n") return nonce, hash[:] } 

First we initialize the variables. hashInt is an integer representation for hash . nonce is a counter. Then we start the “infinite” loop: it is bounded by the maxNonce constant, the value of which is math.MaxInt64 . This is done to avoid possible nonce overflow. Although the complexity of our PoW implementation is too small to overflow the counter, it is better to have such a check just in case.

In the loop, we do the following:

1. Prepare data
2. Hash them Hash256
3. Convert hash to big integer
4. Compare the resulting integer with the goal

As easy as previously explained. Now you can delete the SetHash method from Block and change the NewBlock function:

 func NewBlock(data string, prevBlockHash []byte) *Block { block := &Block{time.Now().Unix(), []byte(data), prevBlockHash, []byte{}, 0} pow := NewProofOfWork(block) nonce, hash := pow.Run() block.Hash = hash[:] block.Nonce = nonce return block } 

You may notice that nonce saved as a Block property. This is necessary because nonce is required to verify the evidence. The Block structure now looks like this:

 type Block struct { Timestamp int64 Data []byte PrevBlockHash []byte Hash []byte Nonce int } 

And now we will launch our program and check that everything works well:

 Mining the block containing "Genesis Block" 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1 Mining the block containing "Send 1 BTC to Ivan" 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804 Mining the block containing "Send 2 more BTC to Ivan" 000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe Prev. hash: Data: Genesis Block Hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1 Prev. hash: 00000041662c5fc2883535dc19ba8a33ac993b535da9899e593ff98e1eda56a1 Data: Send 1 BTC to Ivan Hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804 Prev. hash: 00000077a856e697c69833d9effb6bdad54c730a98d674f73c0b30020cc82804 Data: Send 2 more BTC to Ivan Hash: 000000b33185e927c9a989cc7d5aaaed739c56dad9fd9361dea558b9bfaf5fbe 

Hooray! Now you can see that each hash begins with three zero bytes and the search for hashes takes some time.

There is still something to be done: let's make it possible to check the evidence of the work:

 func (pow *ProofOfWork) Validate() bool { var hashInt big.Int data := pow.prepareData(pow.block.Nonce) hash := sha256.Sum256(data) hashInt.SetBytes(hash[:]) isValid := hashInt.Cmp(pow.target) == -1 return isValid } 

This is where we need the saved nonce .

Check that everything is in order:

 func main() { ... for _, block := range bc.blocks { ... pow := NewProofOfWork(block) fmt.Printf("PoW: %s\n", strconv.FormatBool(pow.Validate())) fmt.Println() } } 

Output:

 ... Prev. hash: Data: Genesis Block Hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038 PoW: true Prev. hash: 00000093253acb814afb942e652a84a8f245069a67b5eaa709df8ac612075038 Data: Send 1 BTC to Ivan Hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b PoW: true Prev. hash: 0000003eeb3743ee42020e4a15262fd110a72823d804ce8e49643b5fd9d1062b Data: Send 2 more BTC to Ivan Hash: 000000e42afddf57a3daa11b43b2e0923f23e894f96d1f24bfd9b8d2d494c57a PoW: true 

Conclusion

Our blockchain is still a step closer to the current architecture: adding blocks requires computational work, so mining is possible. But it still lacks some important functions: the blockchain database is not permanent, there are no wallets, addresses, transactions, and there is no concess mechanism. All these things we will consider in the following articles.

Links

First part
Original article
Source codes for the article
Blockchain hashing algorithm
Proof of work
Hashcash