【区块链Go语言实现】Part 2：工作量证明机制POW

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Go›Go教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

0x00 介绍

在上一篇文章中，我们建立了一个非常简单的数据结构，它是区块链数据库的本质。并且，我们实现了以类似链条关系的方式向其中添加区块的功能：每个区块都会链接到前一区块。然而，我们实现的区块链有一个严重的缺陷：向区块链中添加区块太过容易和廉价。区块链和比特币的基本原则之一是，要使添加新区块是一项繁重的工作。本文中我们将解决这个缺陷。

0x01 工作量证明（Proof-of-Work，POW）

区块链的一个关键思想是，为了向区块链中添加新的区块，添加者（或节点）必须执行一些繁重的工作，而正是这种繁重的工作确保了区块链的安全性和一致性。同时，系统也会为该工作支付一定的报酬（这也就是人们能够通过挖矿来获得比特币的原因）。

这种机制与现实生活中的情况非常类似：一个人必须努力工作来获得报酬，以维持他们的生活。在区块链中，网络中的一些参与者（矿工）通过工作来维持整个网络，添加新区块，并为他们的工作获得报酬。由于他们的工作，区块能够以一种安全的方式并入到区块链中，这保证了整个区块链数据库的稳定性。值得注意的是，完成这项工作的人必须证明这一点。

整个“努力工作并证明”的机制称为工作量证明机制。做到这一点很困难，因为它需要大量的计算能力，即使是高性能计算机也无法快速做到这一点。此外，这项工作的难度也会随着时间而增大，以此保持新区块的增长速率约为每小时6块。在比特币网络中，这项工作的目标是找到一个满足一定要求的区块散列值，正是这个散列值来作为工作量的证明。因此，找到一个工作量的证明才是实际的工作。

最后需要注意一点，工作量证明算法必须满足一个要求：虽然做这项工作很困难，但验证证明却很容易。通常情况下，工作量证明生成后，会将证明传递给其他人，所以对他们来说，验证它不应该花费太多时间。

0x02 计算哈希

在这一节中，我们将讨论哈希的计算。如果你熟悉这个概念，那么你可以跳过这一部分。

计算哈希是一个求取指定数据的哈希值的过程。哈希是待计算目标数据的一种独特表示。哈希函数是这样一个函数，它可以接受任意大小的数据，并能够生成一个固定大小的哈希值。下面列举了计算哈希的一些关键特性：

从一个哈希值无法恢复原始数据。因此，计算哈希并不是对数据加密。
固定数据只能有一个哈希值，且该哈希值是独一无二的。
即使改变输入数据的一个字节都将导致一个完全不同的哈希值。

哈希函数广泛用于检查数据的一致性。一些软件提供商在发布软件包时也会附带一个软件包的校验和，这样用户下载软件后，可以通过哈希函数计算软件包的哈希值，然后将该哈希值与软件提供商提供的哈希值进行比较，以此确定所下载软件的完整性和一致性。

在区块链中，哈希用来保证区块的一致性。哈希算法中输入的数据包含前一区块的哈希值，因此使得篡改区块链中的区块变得不可能（或者至少变得十分困难）：篡改者必须重新计算该区块的哈希值，以及该区块之后所有区块的哈希值。

0x03 哈希现金（Hashcash）

比特币使用了哈希现金（Hashcash）算法，它是一种工作量证明算法，最初开发用来防止垃圾邮件。它可以分为以下步骤：

利用一些公开已知的数据（以邮件为例，可以是接收方的邮件地址；在比特币情况下，就是区块头）。
向其中添加一个计数器，计数器从0开始。
计算数据和计数器组合的哈希值。
校验上步中得到的哈希值以确保其满足特定的要求。

如果正常实现，那么到此结束。
否则，增加计数器的值，然后重复第3和第4步。

因此，这是一个暴力算法：你改变计数器的值，计算一个新的哈希，对其进行检查，增加计数器值，计算哈希，等等。这就是为什么需要大量计算的原因了。

现在，让我们深入了解一个哈希必须满足的要求。在最初的哈希现金机制实现中，这种要求类似于“哈希的前20位必须是零”。在比特币中，这种要求会随时调整，因为在设计上，必须保证每10分钟生成一块新的区块，尽管计算能力在随着时间的推移而提升，以及越来越多的矿工加入到网络中。

为了演示该算法，使用上一例子中的数据（“I like donuts”），我们得到一个前3字节为0的哈希：

ca07ca是计数器的十六进制值，对应的十进制值为13240266。

0x04 代码实现

到此，我们完成了理论部分，接下来我们开始编写代码！首先，我们定义挖矿的难度：

const targetBits = 24

在比特币中，“目标比特”是区块头，它存储了该区块被开采时的难度。现在，我们并不去实现一种目标调整算法，而是仅仅将难度定义为一个全局常量。

24可以是任意数，我们的目的是在内存中得到一个少于256位的目标值，并且我们希望差别足够重要，但不要太大，因为差别越大，那么找到一个合适的哈希将会越困难。

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结构体，它包含一个指向某个区块的指针，以及一个指向目标的指针。“目标”是前面段落中描述的要求的另一名字。考虑到我们将哈希与目标进行比较的方式，我们使用了一个大整数（big.Int）：我们将哈希转换为一个大整数，并检查它的值是否小于目标。

在NewProofOfWork函数中，我们初始化一个big.Int的值为1，并将其值左移256-targetBits位，其中256为一个SHA-256哈希的比特长度，我们将会使用SHA-256哈希算法。target（目标）的十六进制表示为：

0x10000000000000000000000000000000000000000000000000000000000

它在内存中占据了29个字节。下面是它与上一例子中哈希的视觉比较：

0fac49161af82ed938add1d8725835cc123a1a87b1b196488360e58d4bfb51e3
0000010000000000000000000000000000000000000000000000000000000000
0000008b0f41ec78bab747864db66bcb9fb89920ee75f43fdaaeb5544f7f76ca

第一个哈希（对“I like donuts”计算得到）比目标大，因此它不是一个有效的工作量证明。第二个哈希（对“I like donutsca07ca”计算得到）则比目标小，因此这是一个有效的证明。

你可以想出一个目标作为一个范围的上限：如果一个数（一个哈希）低于边界，那么说明它是有效的，反之亦然。降低边界将会导致更少的有效数，因此，找到一个有效数将需要更困难的工作。

现在，我们需要待求取哈希的目标数据，下面我们准备该数据：

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是前面描述的哈希现金算法中的计数器，这是一个密码学术语。

Ok，到此所有的准备工作都已完成。下面我们将实现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实现难度太低，以至于不会造成计数器的溢出，但最好还是对其进行验证，以防万一。

在循环中，我们做了以下事情：

准备数据。
使用SHA-256对其求取哈希。
将哈希转换成一个大整数。
将上步中的整数与目标进行比较。

正如我们前面解释的那样简单。现在我们可以删除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
}

OK，现在我们运行程序来检查是否一切工作正常：

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

欧耶！你可以看到，现在每一个哈希都以三个零字节开头，而获取到这些哈希都需要花费一定的时间。

还有一件事需要做：实现验证工作量证明的功能。

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的地方。

让我们再次检查以确保一切都OK：

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