English source address
Introduction
In the previous article, we built a very simple data structure, which is the essence of the blockchain database. And we can add blocks through the chain relationship between them: each block is linked to the previous A block. Alas, our blockchain implementation has a major flaw: adding blocks to the chain is easy and fast. One of the keys to blockchains and Bitcoin is that adding new blocks is a difficult task . Today we will fix this bug.
Proof of Work
A key idea of a blockchain is that people have to perform some hard work to put data into it. It is this hard work that makes a blockchain secure and consistent. Also, this hard work gets Rewards (this is how people miner earn bitcoins).
This mechanism is very similar to the mechanism in real life: people have to work hard to get rewards and maintain their lives. In the blockchain, some participants in the network (miners) work to maintain the network, adding new miners to it. blocks and receive rewards for their work. Thanks to their work, a block is merged into the blockchain in a secure manner, thereby maintaining the stability of the entire blockchain database. It is worth noting that, The person who gets the job done has to prove it.
This whole ‘work hard and prove’ mechanism is called proof-of-work. It’s hard, because it requires a lot of computing power: even a high-powered computer can’t do it quickly. Furthermore, the difficulty of the work will keep increasing to Maintain a new block output of 6 blocks per hour. In Bitcoin, the goal of this kind of work is to find a hash value for a block that satisfies some requirements. This hash value can be used as a proof. is real work.
As a final note, the proof-of-work algorithm must meet one requirement: doing the work is hard, but verifying the proof-of-work is easy. The proof is usually given to someone else, so it shouldn’t take too much time for them to verify it.
Hash function
In this section, we will discuss hash (hash) functions. If you are familiar with this concept, you can skip this part.
A hash function is the process of obtaining a hash for specified data. A hash value is a unique representation of the calculated data. A hash function is a function that accepts data of any size as input and generates a fixed-size hash value. The following is hash Some key properties of Chi functions:
- The original data cannot be recovered from the hash value. Therefore, the hash operation is not an encryption operation
- The same data will only have one hash value, and the hash value is unique
- Changing even one byte in the input data results in a completely different hash
Hash functions are widely used to check data consistency. Some software providers publish checksums in addition to software packages. Once you download a file, you can feed it to a hash function and the resulting hash value Compare with the hash value provided by the software developer.
In blockchains, hash operations are used to ensure block consistency. The input data to the hash algorithm contains the hash value of the previous block, so it is impossible (or at least quite difficult) to modify the blocks in the chain : Has to recalculate its hash and the hashes of all subsequent blocks.
Hashcash
Bitcoin uses Hashcash, a proof-of-work algorithm originally developed to prevent spam. It can be broken down into the following steps:
- With some public data (if it’s an email, it’s the recipient’s email address; in the case of Bitcoin, it’s the block header)
- Add a counter to it. The counter starts counting from 0.
- Get the hash value of the data + counter combination
- Check if the hash value meets certain requirements:
1. If satisfied, it is done
2. If not satisfied, increase the counter and repeat steps 3 and 4
So, it’s a brute force algorithm: you change the counter, compute a new hash, check it, increment the counter, compute a hash, etc. That’s why it’s expensive on the computer.
Now let’s take a closer look at the conditions that a hash value must satisfy. In the original Hashcash implementation, this requirement sounded like ‘the first 20 bits of the hash must be zero’. In Bitcoin, this requirement has evolved over time Adjusted, because by design, a block must be produced every 10 minutes despite computing power increasing over time as more and more miners join the network.
To demonstrate the algorithm, I take the data from the signed example (‘i like donuts’) and find a hash value starting with 3 zero bytes. 
ca07ca is the hexadecimal value of the counter, which corresponds to 13240266 in decimal.
Implementation
Ok, now that we’ve finished the theory, let’s start writing the code! First, let’s define the difficulty of the miner:
const targetBits = 24
In Bitcoin. ‘Target bit’ is the block header that stores the block mining difficulty. We won’t implement the target adjustment algorithm right now, so we can define the difficulty as a global constant.
24 is an arbitrary number, our goal is to occupy less than 256 bits of target value in memory. We hope that the difference is obvious enough, but not too large, because the larger the difference, the harder it is to find a suitable Greek value.
type ProofOfWork struct {<!-- -->
block *Block
target *big.Int
}
func NewProofOfWork(b *Block) *ProofOfWork {<!-- -->
target := big. NewInt(1)
target.Lsh(target, uint(256-trgetBits))
\t
pow := &ProofOfWork{<!-- -->b, target}
return pow
}
Create a ProofOfWork structure here that holds a pointer to the block and a pointer to the target. ‘target’ is another name for the requirement described in the previous paragraph. We use a large integer because we are combining the hash with the target target value: we convert the hash value to a large integer and check if it is less than the target value.
In the NewProofOfWork function, initialize a big.Int, assign a value of 1 and shift (256-targetBits) bits to the left. 256 is the length of the SHA-256 hash value, in bits, and what we want to use is the SHA-256 hash The hexadecimal representation of algorithm.target is
0x10000000000000000000000000000000000000000000000000000000000
It occupies 29 bytes of memory. Here is a visual comparison of it with the hash value in the previous example
0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3 00000100000000000000000000000000000000000000000000000000000000000 0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca
The first hash (calculated from ‘I like donuts’) is larger than the target, so it is not a valid proof-of-work. The second hash (‘ calculated from ‘I like donutsca07ca’) is smaller than the target , so it is a valid proof.
You can think of the target value as an upper boundary on a range: if a number (hash) is below that boundary, it is valid, and vice versa. Lowering the boundary will result in fewer valid numbers, so look for valid numbers The work required will be more difficult.
Now, we need to hash the data, so let’s prepare it:
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{<!-- -->})
\t
return data
}
This part is easy: we just merge the block field with the target and the nonce. The nonce is the counter in the Hashcash algorithm description above, which is a cryptographic term.
Ok, all the preparations are done, let’s implement the core of the PoW algorithm:
func (pow *ProofOfWork) Run() (int, []byte) {<!-- -->
var hashInt big.Int
var hash [32]byte
nonce := 0
maxNonce := math.MaxInt64
fmt.Printf("Mining the block containing "%s"\\
", pow.block.Data)
for nonce < maxNonce {<!-- -->
data := pow. prepareData(nonce)
hash = sha256. Sum256(data)
fmt.Printf("\r%x", hash)
hashInt. SetBytes(hash[:])
\t\t
if hashInt.Cmp(pow.target) == -1 {<!-- -->
break
} else {<!-- -->
nonce++
}
}
fmt.Print("\\
\\
")
return nonce, hash[:]
}
First, the variable is initialized: hashInt is the integer form of the hash value. The nonce is the counter value. Next, we run an ‘infinite’ loop: it is limited by maxNonce, which is equal to math.MaxInt64; this is done to avoid the nonce possible Overflow. Even though the difficulty of our PoW implementation is too low for the counter to overflow, it would be nice to have a check just in case.
In the loop, we:
- prepare data
- Calculate the hash value with the SHA-256 algorithm
- Convert hash value to big integer
- compares the integer value to the target value
It’s as simple as explained before. Now we can delete the Block’s SetHash method and modify the NewBlock function:
func NewBlock(data string, prevBlockHash []byte) *Block {<!-- -->
block := & amp;Block{<!-- -->time.Now().Unix(), []byte(data), prevBlockHash, []byte{<!-- -->}, 0}
pow := NewProofOfWork(block)
nonce, hash := pow. Run()
block.Hash = hash[:]
block.Nonce = nonce
\t
return block
}
Here we see that the nonce is saved as a property of the Block. This is necessary because the nonce is needed to verify the proof. The Block structure now looks like this:
type Block struct {<!-- -->
Timestamp int64
Data[]byte
PrevBlockHash []byte
Hash[]byte
Nonce int
}
That’s it! Let’s run the program to see if everything works:
Prev. hash: Data: Genesis Block Hash: 0000005d42343f4f2aef73a27ed617c7b61768b87fdf9705b588db99477c4fb9 Prev. hash: 0000005d42343f4f2aef73a27ed617c7b61768b87fdf9705b588db99477c4fb9 Data: Send 1 BTC to Ivan Hash: 000000fbcdefd2389096e73d2c3af7ad11d6c17d59756dd848bfaddfe3c3ac1b Prev. hash: 000000fbcdefd2389096e73d2c3af7ad11d6c17d59756dd848bfaddfe3c3ac1b Data: Send 2 more BTC to Ivan Hash: 000000d01d9fa49f97f5abd759d1ae59cee4f36044117754a9347f7414ec4980
Yay! As you can see, each hash now starts with three zero bytes, and it takes some time to get those hashes.
One more thing to do: let’s make it possible to verify proof-of-work.
func (pow *ProofOfWork) Validate() bool {<!-- -->
var hashInt big.Int
\t
data := pow. prepareData(pow. block. Nonce)
hash := sha256.Sum256(data)
hashInt. SetBytes(hash[:])
\t
isValid := hashInt. Cmp(pow. target) == -1
\t
return isValid
}
That’s why we need to save the nonce.
Let’s check again to make sure everything works.
func main() {<!-- -->
bc := NewBlockchain()
bc.AddBlock("Send 1 BTC to Ivan")
bc.AddBlock("Send 2 more BTC to Ivan")
for _, block := range bc.blocks {<!-- -->
fmt.Printf("Prev. hash: %x\\
", block. PrevBlockHash)
fmt.Printf("Data: %s\\
", block.Data)
fmt.Printf("Hash: %x\\
", block.Hash)
fmt. Println()
pow := NewProofOfWork(block)
fmt.Printf("Pow: %s\\
", strconv.FormatBool(pow.Validate()))
fmt. Println()
}
}
output result
Prev. hash: Data: Genesis Block Hash: 00000074c46066dc882a455694f6457f18ce4552153c58d4c7c94c97b420c405 Pow: true Prev. hash: 00000074c46066dc882a455694f6457f18ce4552153c58d4c7c94c97b420c405 Data: Send 1 BTC to Ivan Hash: 000000bb4739f0563ef910e16afd8b6f1fe3d1837e355b22714c388b2b73506e Pow: true Prev. hash: 000000bb4739f0563ef910e16afd8b6f1fe3d1837e355b22714c388b2b73506e Data: Send 2 more BTC to Ivan Hash: 000000d7ae7d8736aa04542d09c58fc6bbc6437a21e4ad23bafe4d6ef140c8d2 Pow: true
Summary
Our blockchain is one step closer to an actual framework: adding blocks is now hard work, so miners are viable. But it still lacks some key features: no persistent storage for the blockchain database, no wallets, Addresses, transactions, and no consensus mechanism. We will implement all of these functions in a later article, and for now, happy miner!
links:
https://github.com/Jeiwan/blockchain_go/tree/part_2
https://en.bitcoin.it/wiki/Block_hashing_algorithm
https://en.bitcoin.it/wiki/Proof_of_work
https://en.bitcoin.it/wiki/Hashcash