Eventually content please refer to the original: https://wangwei.one/posts/7890ab7e.html

The introduction

In the last article, we implemented the most basic data structure model of blockchain, adding blocks and connecting them to previous blocks. However, our implementation method is very simple, whereas in the real Bitcoin blockchain, the addition of each block requires a lot of calculation, which is known as mining.

Proof of work mechanism

One of the key ideas of blockchain is that a lot of difficult computing must be done to store transaction data on the blockchain. Only this working mechanism can ensure the security and consistency of the entire blockchain data. At the same time, the miners who complete the calculation will be rewarded with tokens.

This mechanism is very similar to our real life: we have to work hard to get paid to support our life. In blockchain, miners in the network work hard to maintain the blockchain network, add blocks to it, and receive certain Token rewards. As a result of their work, a block is incorporated into the blockchain in a secure manner, thus ensuring the stability of the entire blockchain database. It is also important to note that the result of a calculation done by one miner must be approved (proved correct) by all the other miners in order to be considered complete.

This whole system of calculation and Proof is called proof-of Work. Computing is very, very difficult because it consumes a lot of computer power resources, and even very high performance computers cannot compute the correct results very quickly. In addition, this calculation becomes more difficult over time in order to ensure a rate of 6 new blocks per hour. In Bitcoin, the goal is to find a block Hash that satisfies a particular requirement. This block hash is a proof of the result of the work. Therefore, the purpose of computation is to find this proof value.

Finally, note that it is very difficult to compute this particular Hash, but it is very easy for someone else to verify that the Hash value is correct.

Hashing

Hash: Hash | Hash

Let’s talk about Hashing, and those of you who are familiar with this can skip over that.

A hash is a computer algorithm that can compute a hash of any size of data, and the length of the hash is fixed at 256 bits. This computed hash can be used as a unique representation of this data. The hashing algorithm has several key properties:

  • Irreversibility. Raw data cannot be derived from a hash value. So, hash is not encryption.
  • Uniqueness. Each data has one and only one unique hash value.
  • Different sex. Any slight change in the original data will result in a completely different hash value.

Such as:

SHA256("wangwei1") - > 1 e898b7c9adaad86c20139a302ccd5277f81040cab68dc2aecfc684773532652 SHA256 ("wangwei2") ——> c9cc7417c17318c8aab448cc8ace24c53b6dcf350f5c5fd8e91cbc3b011a179d
Copy the code

Hashing algorithm is widely used to verify file consistency. Such as software provider usually attach a check code on the installation package (checksums), when we after downloading a software installation package, you can use hash function to calculate the hash value of the software installation package, then make a contrast and software installation package check code, can know whether the installation package download is complete, if there is a loss of data.

In blockchains, hashes are used to guarantee the consistency of blocks. Each block used for hashing contains the hash value of the previous block, so it is almost impossible for anyone to modify the block’s data. He would have to recalculate all the hashes in the whole block chain from genesis block to the latest block.

You can imagine how much work that would be, but with the power of computers today, it’s almost impossible

Hashcash

Bitcoin’s proof of work uses Hashcash, an algorithm originally developed for anti-spam, which can be broken down into the following steps:

  1. Get some publicly known data (in the mail case, the email address of the recipient; In the case of Bitcoin, the block head.)
  2. Add a counter counter with an initial value of 0;
  3. Calculates the hash value of the data and counter concatenation string;
  4. Check if the hash value of the previous step satisfies a condition, stop the calculation if it does, increment counter if it does not, and repeat steps 3 and 4 until this particular condition is satisfied.

It’s a brutal algorithm: you change the counter, compute a new hash, check it, increase the counter, compute a new hash, and repeat, which is why it takes a lot of computing power.

Let’s take a closer look at what this particular condition refers to. In the original Hashcash algorithm, this particular requirement meant that the first 20 bits of the computed hash value had to be all zeros,

In bitcoins, the requirement for the number of zeros in front of a hash value is adjusted over time by design, despite the need to produce a block every 10 minutes as computing power improves and more miners join the network.

So let’s demonstrate this algorithm,

# Evaluate the hash of the string 'I like donuts'
SHA256("I like donuts") 
——> f80867f6efd4484c23b0e7184e53fe4af6ab49b97f5293fcd50d5b2bfa73a4d0

# concatenate a counter value (ca07CA) to Hash again
SHA256("I like donutsca07ca") 
——> 0000002f7c1fe31cb82acdc082cfec47620b7e4ab94f2bf9e096c436fc8cee06
Copy the code

Here ca07ca is the hexadecimal value of the counter, which represents a decimal value of 13240266

That is, the Hash value of “I like Donuts” was calculated for 1,240,266 times starting from 0, and the first 6 bits (3 bytes) were all zero.

Code implementation

Ideas:

1) Every time a block is added to the blockchain, it is mined (Pow)

2) During mining, if the Hash value generated is less than the difficulty target value, it will be added to the block; otherwise, mining will continue until the correct Hash is found

3) Finally, verify that the block Hash is valid

Classes define the Pow

/** ** work proof **@author wangwei
 * @date2018/02/04 * /
@Data
public class ProofOfWork {

    /** * Difficulty target */
    public static final int TARGET_BITS = 20;

    /** * block */
    private Block block;
    /** * Difficulty target value */
    private BigInteger target;

    private ProofOfWork(Block block, BigInteger target) {
        this.block = block;
        this.target = target;
    }
  
    /** * Create a new proof of work, set the difficulty target value * <p> * and shift 1 to the left by (256-target_bits) bits to get our difficulty target value **@param block
     * @return* /
    public static ProofOfWork newProofOfWork(Block block) {
        BigInteger targetValue = BigInteger.valueOf(1).shiftLeft((256 - TARGET_BITS));
        return newProofOfWork(block, targetValue); }}Copy the code

  • Set a difficulty target bit TARGET_BITS, which indicates the Hash value extracted from the final mining. After converting to binary, how many bits are shorter than 256, that is, how many bits are zero before the binary.

    • TARGET_BITSThe bigger, eventuallytargetValueThe smaller it gets, the smaller the Hash it needs to compute, the harder it gets to mine.
    • What we have hereTARGET_BITSIt’s fixed, but in real Bitcoin, the difficulty goal is dynamically adjusted over time. See:Chapter 10 in Mastering Bitcoin (second edition)

  • Because of the large value, the type BitInteger is used.

To prepare data

/** * prepare data * <p> * Note: When preparing block data, it must be converted from the raw data type to byte[], not directly from string *@param nonce
 * @return* /
private String prepareData(long nonce) {
   byte[] prevBlockHashBytes = {};
   if (StringUtils.isNoneBlank(this.getBlock().getPrevBlockHash())) {
       prevBlockHashBytes = new BigInteger(this.getBlock().getPrevBlockHash(), 16).toByteArray();
   }

   return ByteUtils.merge(
           prevBlockHashBytes,
           this.getBlock().getData().getBytes(),
           ByteUtils.toBytes(this.getBlock().getTimeStamp()),
           ByteUtils.toBytes(TARGET_BITS),
           ByteUtils.toBytes(nonce)
    );
}
Copy the code
  • The following information participates in the Hash operation:
    • The Hash value of the previous block (parent block);
    • Transaction data in the block;
    • Block generation time;
    • Difficulty target;
    • Counters for proof-of-work algorithms

See chapter 09 in Mastering Bitcoin (Second Edition)

Pow algorithm

/** * Run the proof of work, start mining and find Hash ** that is less than the target difficulty value@return* /
public PowResult run(a) {
    long nonce = 0;
    String shaHex = "";
    System.out.printf("Mining the block containing: %s \n".this.getBlock().getData());

    long startTime = System.currentTimeMillis();
    while (nonce < Long.MAX_VALUE) {
        String data = this.prepareData(nonce);
        shaHex = DigestUtils.sha256Hex(data);
        if (new BigInteger(shaHex, 16).compareTo(this.target) == -1) {
            System.out.printf("Elapsed Time: %s seconds \n", (float) (System.currentTimeMillis() - startTime) / 1000);
            System.out.printf("correct hash Hex: %s \n\n", shaHex);
            break;
         } else{ nonce++; }}return new PowResult(nonce, shaHex);
}
Copy the code
  • There are four main steps in the circulation body:
    • To prepare data
    • Perform sha256 operation
    • Convert to BigInter type
    • Compare with Target
  • Finally, the correct Hash value is returned along with the operation counternonce

Verify the block Hash validity

/** * Verify that the block is valid **@return* /
public boolean validate(a) {
    String data = this.prepareData(this.getBlock().getNonce());
    return new BigInteger(DigestUtils.sha256Hex(data), 16).compareTo(this.target) == -1;
}
Copy the code

Modify block add logic

/** * <p> Create a new block </p> **@param previousHash
 * @param data
 * @return* /
public static Block newBlock(String previousHash, String data) {
    Block block = new Block("", previousHash, data, Instant.now().getEpochSecond(), 0);
    ProofOfWork pow = ProofOfWork.newProofOfWork(block);
    PowResult powResult = pow.run();
    block.setHash(powResult.getHash());
    block.setNonce(powResult.getNonce());
    return block;
}
Copy the code
  • Create a block
  • Create a Pow algorithm object
  • Execute Pow algorithm
  • Save the returned Hash and the arithmetic counter

A test run

/** * test **@author wangwei
 * @date2018/02/05 * /
public class BlockchainTest {

    public static void main(String[] args) {

        Blockchain blockchain = Blockchain.newBlockchain();

        blockchain.addBlock("Send 1 BTC to Ivan");
        blockchain.addBlock("Send 2 more BTC to Ivan");

        for (Block block : blockchain.getBlockList()) {
            System.out.println("Prev.hash: " + block.getPrevBlockHash());
            System.out.println("Data: " + block.getData());
            System.out.println("Hash: " + block.getHash());
            System.out.println("Nonce: " + block.getNonce());

            ProofOfWork pow = ProofOfWork.newProofOfWork(block);
            System.out.println("Pow valid: " +  pow.validate() + "\n"); }}}/** ** set TARGET_BITS = 20 and get the following result: */Mining the block containing: Genesis block Elapsed Time:2.118 seconds 
correct hash Hex: 00000828Ee8289ef6381f297585ef8c952fde93fc2b673ff7cc655f699bb2442 Mining, the block containing: Send1 BTC to Ivan 
Elapsed Time: 1.069 seconds 
correct hash Hex: 00000A38c0d7f2ebbd20773e93770298aa8bc0cc6d85fca8756fe0646ae7fea5 Mining, the block containing: Send2 more BTC to Ivan 
Elapsed Time: 4.258 seconds 
correct hash Hex: 00000777f93efe91d9aabcba14ab3d8ab8e0255b89818cdb9b93cfa844ad0c7f 

Prev.hash: 
Data: Genesis Block
Hash: 00000828ee8289ef6381f297585ef8c952fde93fc2b673ff7cc655f699bb2442
Nonce: 522163
Pow valid: true

Prev.hash: 00000828ee8289ef6381f297585ef8c952fde93fc2b673ff7cc655f699bb2442
Data: Send 1 BTC to Ivan
Hash: 00000a38c0d7f2ebbd20773e93770298aa8bc0cc6d85fca8756fe0646ae7fea5
Nonce: 474758
Pow valid: true

Prev.hash: 00000a38c0d7f2ebbd20773e93770298aa8bc0cc6d85fca8756fe0646ae7fea5
Data: Send 2 more BTC to Ivan
Hash: 00000777f93efe91d9aabcba14ab3d8ab8e0255b89818cdb9b93cfa844ad0c7f
Nonce: 1853839
Pow valid: true
Copy the code

conclusion

We are getting closer and closer to the real blockchain architecture. We have implemented the mining mechanism, but we have not implemented many key features: persistence of the blockchain database, wallet, address, transaction, consensus mechanism, which we will implement step by step

data

  • Source: https://github.com/wangweiX/blockchain-java/tree/part2-pow

  • https://jeiwan.cc/posts/building-blockchain-in-go-part-2/

  • Mastering Bitcoin (2nd Edition)