基于 Java 语言构建区块链（二）—— 工作量证明

文章的主要思想和内容均来自 https://jeiwan.cc/posts/building-blockchain-in-go-part-2/

引言

在 上一篇 文章中，我们实现了区块链最基本的数据结构模型，添加区块以及和前一个区块连接在一起。但是，我们的实现方式非常简单，而真实的比特币区块链中，每一个区块的添加都是需要经过大量的计算才可以完成，这个过程就是我们熟知的挖矿。

工作量证明机制

区块链最关键的一个思想就是，必须进行大量且困难的计算工作才能将交易数据存放到区块链上。这种工作机制才能保证整个区块链数据的安全性和一致性。同时，完成这个计算工作的矿工会得到相应的 Token 奖励。

这套机制和我们的现实生活非常相似：我们必须努力工作来赚取报酬用以维持我们的生活。在区块链中，网络中的矿工们努力工作来维持区块链网络，为其添加区块，并且获得一定的 Token 奖励。作为他们工作的成果，一个区块以安全的方式被组合进了区块链中，这样就保证了整个区块链数据库的稳定性。还有一个必须要注意的是，某个矿工完成了计算工作的结果，还必须得到其他所有矿工的认同（证明是正确的），这样才算完成。

这一整套的计算和证明机制，就称为 Proof-of-Work（工作量证明）。计算工作是非常非常困难的，因为它需要消耗大量的计算机算力资源，即使是性能非常高的计算机都不能非常快地计算出正确的结果。此外，随着时间的推移，这项计算工作的难度也会随之增加，目的是为了保证每小时 6 个新区块的出块率。在比特币中，这种工作的目标是找到满足某个特定要求的区块 Hash（哈希值）。这个区块哈希值就是工作结果的一个证明。因此，计算工作的目的就是为了寻找到这个证明值。

最后要注意的是，计算出这个特定的 Hash（哈希值）是非常困难的，但是别人来验证这个 Hash 值是否正确的时候，是非常简单的，一下子就能完成。

Hashing

Hash：哈希 | 散列

我们来讨论一下 Hashing（哈希），对这一块非常熟悉的朋友可以直接跳过这一段内容。

哈希是一种计算机算法，该算法能够计算出任意大小数据的哈希值，并且这个哈希值的长度是固定的，256bit。这个被计算出来的哈希值能够作为这个数据的唯一代表。哈希算法有几个关键的特性：

• 不可逆性。不能根据一个哈希值推导出原始数据。所以，哈希不是加密。
• 唯一性。每个数据有且仅有一个唯一的哈希值。
• 迥异性。原始数据一丁点的变化都将得到完全不一样的哈希值。

例如：

SHA256("wangwei1") ——> 1e898b7c9adaad86c20139a302ccd5277f81040cab68dc2aecfc684773532652
SHA256("wangwei2") ——> c9cc7417c17318c8aab448cc8ace24c53b6dcf350f5c5fd8e91cbc3b011a179d

哈希算法被广泛用于验证文件的一致性上。比如软件提供商通常会在安装包上附加一个检验码（checksums），当我们下载完一个软件安装包后，可以用哈希函数计算一下这个软件安装包的哈希值，然后再和软件安装包的检验码做个对比，就可以知道下载的安装包是否完整、是否有数据丢失。

在区块链中，哈希值用于保证区块的一致性。每一个区块被用于进行哈希计算的数据，都包含前一个区块链的哈希值，因此任何人想要修改区块的数据几乎是不可能的，他必须要把整个区块链中从创世区块到最新的区块的所有哈希值全部重新计算一遍。

你可以脑补一下这个工作量有多大，按照目前计算机的算力来看，几乎不可能

Hashcash

比特币的工作量证明是使用的是 Hashcash 算法，一种最初被用于反垃圾邮件的算法，它可以被拆解为以下几步：

1. 获取某种公开可知的数据 data（在邮件案例中，指的是收件人邮件地址；比特币案例中，指的是区块头）
2. 添加一个计数器 counter，初始值设置为 0；
3. 计算 data 与 counter 拼接字符串的哈希值；
4. 检查上一步的哈希值是否满足某个条件，满足则停止计算，不满足则 counter 加 1，然后重复第 3 步和第 4 步，直到满足这个特定的条件为止。

这是一种粗暴的算法：你改变计数器，计算一个新的哈希值，检查它，增加计数器，计算一个新的哈希值，循环往复，这就是为什么它需要花费大量计算机算力资源的原因所在。

让我们来近距离看一下这个特定的条件指的是什么。在原始的 Hashcash 算法中，这个特殊的要求指的是计算出来的哈希值的前 20bit 必须全是零，

在比特币种，这种要求哈希值前面有多少个零打头的要求是随着时间的推移而不断调整的，这是出于设计的目的，尽管在计算机的算力会不断的提升和越来越多的矿工加入这个网络中的情况下，都要保证每 10min 生产一个区块。

我们演示一下这个算法，

# 计算字符串'I like donuts'的哈希值
SHA256("I like donuts") 
——> f80867f6efd4484c23b0e7184e53fe4af6ab49b97f5293fcd50d5b2bfa73a4d0

# 拼接一个计数器值(ca07ca)，再次进行Hash计算
SHA256("I like donutsca07ca") 
——> 0000002f7c1fe31cb82acdc082cfec47620b7e4ab94f2bf9e096c436fc8cee06

这里的 ca07ca 是计数器值的十六进制，他表示的十进制值为 13240266

即，从 0 开始，总共计算了 13240266 次，才计算出 I like donuts 这个数据的 Hash 值，满足前 6 位 (3 字节) 全是零。

代码实现

思路：

1）每次区块被添加到区块链之前，先要进行挖矿（Pow）

2）挖矿过程中，产生的 Hash 值，如果小于难度目标值则添加进区块，否则继续挖矿，直到找到正确的 Hash 为止

3）最后，验证区块 Hash 是否有效

定义 Pow 类

/**
 * 工作量证明
 *
 * @author wangwei
 * @date 2018/02/04
 */
@Data
public class ProofOfWork {

    /**
     * 难度目标位
     */
    public static final int TARGET_BITS = 20;

    /**
     * 区块
     */
    private Block block;
    /**
     * 难度目标值
     */
    private BigInteger target;

    private ProofOfWork(Block block, BigInteger target) {
        this.block = block;
        this.target = target;
    }
  
    /**
     * 创建新的工作量证明，设定难度目标值
     * <p>
     * 对1进行移位运算，将1向左移动 (256 - TARGET_BITS) 位，得到我们的难度目标值
     * 
     * @param block
     * @return 
     */
    public static ProofOfWork newProofOfWork(Block block) {
        BigInteger targetValue = BigInteger.valueOf(1).shiftLeft((256 - TARGET_BITS));
        return new ProofOfWork(block, targetValue);
    }
}

• 设定一个难度目标位 TARGET_BITS，表示最终挖矿挖出来 Hash 值，转化为二进制后，与 256 相比，长度少了多少 bit，也即二进制前面有多少 bit 是零.

  • TARGET_BITS 越大，最终 targetValue 就越小，要求计算出来的 Hash 越来越小，也就是挖矿的难度越来越大。
  • 我们这里的 TARGET_BITS 是固定的，但是在真实的比特币中，难度目标是随着时间的推推，会动态调整的。详见：《精通比特币 （第二版）》第 10 章

• 由于数值比较大，这里要使用 BitInteger 类型。

准备数据

/**
 * 准备数据
 * <p>
 * 注意：在准备区块数据时，一定要从原始数据类型转化为byte[]，不能直接从字符串进行转换
 * @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)
    );
}

• 参与 Hash 运算的如下几个信息：
  • 前一个区块（父区块）的 Hash 值；
  • 区块中的交易数据；
  • 区块生成的时间；
  • 难度目标；
  • 用于工作量证明算法的计数器

详见：《精通比特币 （第二版）》第 09 章

Pow 算法

/**
 * 运行工作量证明，开始挖矿，找到小于难度目标值的Hash
 *
 * @return
 */
public PowResult run() {
    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);
}

• 循环体里面主要以下四步：
  • 准备数据
  • 进行 sha256 运算
  • 转化为 BigInter 类型
  • 与 target 进行比较
• 最后，返回正确的 Hash 值以及运算计数器 nonce

验证区块 Hash 有效性

/**
 * 验证区块是否有效
 *
 * @return
 */
public boolean validate() {
    String data = this.prepareData(this.getBlock().getNonce());
    return new BigInteger(DigestUtils.sha256Hex(data), 16).compareTo(this.target) == -1;
}

修改区块添加逻辑

/**
 * <p> 创建新区块 </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;
}

• 创建区块
• 创建 Pow 算法对象
• 执行 Pow 算法
• 保存返回的 Hash 以及运算计数器

测试运行

/**
 * 测试
 *
 * @author wangwei
 * @date 2018/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");
        }
    }
}

/**
 * 设定TARGET_BITS = 20，得到如下结果：
 */
Mining the block containing：Genesis Block 
Elapsed Time: 2.118 seconds 
correct hash Hex: 00000828ee8289ef6381f297585ef8c952fde93fc2b673ff7cc655f699bb2442 

Mining the block containing：Send 1 BTC to Ivan 
Elapsed Time: 1.069 seconds 
correct hash Hex: 00000a38c0d7f2ebbd20773e93770298aa8bc0cc6d85fca8756fe0646ae7fea5 

Mining the block containing：Send 2 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

总结

我们正在一步一步接近真实的区块链架构，本篇我们实现了挖矿机制，但是我们还有很多关键性的功能没有实现：区块链数据库的持久性、钱包、地址、交易、共识机制，这些我们后面一步一步来实现

资料

• 源代码：https://github.com/wangweiX/blockchain-java/tree/part2-pow

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

• 《精通比特币（第二版）》