原文：Building Blockchain in Go. Part 2: Proof-of-Work

简介

在上一篇文章中，我们构建了一个非常简单的数据结构，这正是区块链数据库的本质所在。同时，我们也实现了通过链式关系去添加区块，每一个区块都连接着上一个区块。然而，我们的区块链实现有一个很明显的瑕疵：添加区块到链上实在是太容易，太廉价了。区块链和比特币其中一个主旨是，添加区块应该是一件困难的工作。今天我们就来修复这个瑕疵吧。

工作量证明

区块链其中一个关键的想法就是，要把数据成功添加进去必须执行一些困难的工作才能通过。也正是这些困难的工作才能让区块链变得更加安全和保持一致性。同样，执行这些困难的工作也是可以获取到特定的报酬的（这就是人们为什么能够通过挖矿来获取货币）。

这个机制跟我们现实生活是很相似的：人们需要通过工作才能获取报酬并且维持他们的生活。在区块链中，网络节点上的一些参与者（矿工）负责维持网络，并且通过添加新的区块去获取相应的报酬。正是有了他们的工作，一个区块才能以安全的方式编入区块链中，从而维持了整个区块链数据库的稳定性。值得注意的是，完成这项工作的人必须证明这一点。

整个"执行困难工作并且证明"的机制也成为工作量证明。这项工作的困难是在于其需要大量的算力：即使是高性能的计算机也不能迅速的完成。此外，随着每次1小时6个区块的增长，这项工作的困难程度将会越来越大。在比特币中，这项工作的目标就是为一个区块找出一个符合特定要求的hash值，而这个hash值则可以作为一个证明。因此，找到一个证明就是实际的工作。

哈希算法

在这一段中我们将会讨论hash算法。如果你已经对这个概念比较熟悉了，那么可以跳过这部分。

hash算法是为特别数据获取对应hash值的一个过程。hash值是它计算的数据的唯一表示。一个哈希函数可以接收任意大小的数据，并且输出固定大小的hash值。下面是哈希算法的关键特性：
1.原始数据不能从一个hash值中反推出来。因此，hash算法并不是加密算法。
2.固定的数据有且仅有一个唯一的hash值。
3.改变输入数据中的任何一个字节都会输出一个完全不同的hash值。

hashing-example.png

哈希函数广泛用于检查数据的一致性。某些软件厂商会把对应的摘要添加到软件包中。当你下载完一个文件之后，你就可以将其输入到哈希函数中，并将输出的hash值与软件开发人员提供的hash值进行比较。

在区块链中，hash通常用于保证一个区块的一致性。每一个区块输入到哈希函数的数据中都会包含着上一个区块的hash值，因此它使得在链上修改一个区块变得完全不可能（至少是非常困难）：因为修改一个区块必须重新计算后面所有区块的hash值。

Hashcash

比特币使用Hashcash，Hashcash最初是用于防止邮件轰炸的一个工作量证明的算法。以下是它的一些算法步骤：
1.提供公开的数据（在邮件中指的是收件人的邮箱地址；在比特币中指的是区块头）。
2.往其添加一个计数器。计数器从0开始。
3.把数据和计数器组合并计算hash值
4.检查这个hash值是否符合特定要求。
（1）如果符合则完成。
（2）如果不符合，增加计数器并重复第三步和第四步。

因此，这是一个非常暴力的算法：修改一个计数器，计算一个新的hash值并检查，继续增加计数器并检查，以此类推。这就是计算费用很昂贵的原因了。

现在我们来仔细看看hash值如何才能满足要求。在最初的Hashcash实现中，听起来要求是"hash值的前20位必须是0"。在比特币中，这个要求还是一次次地被调整，因为从设计上来考虑，尽管计算力随着越来越多的矿工加入到网络中变得越来越高，但还是必须隔十分钟才能产生一个区块。

为了证明这个算法，我从上一个例子中的(“I like donuts”)拿过来了，发现其hash值是已3个0字节开头的：

hashcash-example.png

ca07ca是计数器的十六进制值，也是13240266的十进制值。

实现

好了，我们终于完成了理论部分，让我们开始写代码吧！让我们先定义一个挖矿的难度系数：

const targetBits = 24

在比特币中，“目标比特”是存储块开采难度的区块头。我们目前不会实现目标难度的调整算法，因此我们只需要定义一个全局常量即可。

24是一个任意数字，我们的目标是在内存中拥有少于256位的目标。我们需要有一定象征意义的难度，但也不能太庞大，因为难度越大就越难找出一个合适的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
}

这里创建了一个名为ProofOfWork的结构体，其包含了一个区块指针和目标指针。“目标”也就是上一段中提到的“要求”的别名。我们使用golang的big包主要是因为我们要比较hash值和目标值：我们会把hash转为一个大整数并且检查其是否小于目标值。

在NewProofOfWork函数里面，我们初始化了一个类型为big.Int值为1的变量，并且把它左移了256 - targetBits位。256位是SHA-256哈希算法的长度，我们也即将使用SHA-256算法。target的十六进制表示为：

0x10000000000000000000000000000000000000000000000000000000000

它在内存中占用了29个字节，这是它与前面例子中的hash值进行的可视化比较：

0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3
0000010000000000000000000000000000000000000000000000000000000000
0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca

第一个hash（由“ I like donuts”计算得来）比目标值要更大，因此它不是一个合法的工作量证明。第二个hash值（由“I like donutsca07ca”计算得来）则比目标值更小，因此这才是合法的工作量证明。

你可以把目标值视为范围的上限：如果一个数字（hash值）比边界小，那么它就是合法的。越小的范围会导致合法数字越小，因此也需要更困难的工作才能找到合法的数字。

现在，我们需要对数据进行hash，让我们先来准备数据：

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
}

这里做的事情很简单：我们只是把区块字段和目标以及nonce值进行了合并。nonce在这里则作为上面Hashcash描述中的计数器，这是一个加密术语。

好了，一切准备就绪，我们来实现PoW算法的核心部分吧：

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[:]
}

首先，我们先初始化一些变量：hashInt是hash的整型标识；nonce是一个计数器。接下来，我们开始一个“无限”循环：它限制于maxNonce，这个变量等于math.MaxInt64；主要是用于防止nonce的溢出。尽管难度对于我们实现的PoW算法来说，溢出的可能性很低，但我们最好还是检查一下，以防万一。

在这个循环我们主要做了：
1.准备数据。
2.使用SHA-256函数进行哈希。
3.把hash值转换为大整数。
4.把这个整数跟目标值比较。

我们的解释尽可能的简单。现在我们可以去掉Block中的SetHash方法了，并修改NewBlock函数：

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
}

这里你能看到nonce已经被作为Block的属性保存起来了。这是有必要的，因为nonce是检查证明的必要属性。现在Block结构体看起来是这样的：

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

好的！接下来我们开始运行程序看看是否一切如常：

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

Yay！你可以看到每个hash值都是由3个0字节开头的，并且需要一定时间才能获取到这些hash值。

但这里还有一件事情没完成：让我们可以验证这个工作的证明。

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
}

这就解释了我们为什么需要保存nonce值了。

让我们再检查一次是否运行正常：

func main() {
    ...

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

输出：

...

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

总结

现在添加区块需要进行一系列困难的工作，因此需要进行挖掘，可以看到，我们的区块链又向真实的架构迈向了一步。但这依然缺少一些重要的特性：这个区块链数据库不可以持久化，没有钱包、地址、交易，也没有一致性机制。这些特性我们将会在后面的文章中实现，现在我们就先快乐的挖矿吧！