揭秘比特币和区块链（二）：什么是工作量证明？

1. 来源

工作量证明（POW），简单理解，就是确认你做了一定量工作的证明。监控工作的整个过程往往效率极低，证明工作结果以证明已经完成了相应的工作量是一种非常有效的方式。比如现实生活中的毕业证、驾照等，也是通过检验结果（通过相关测试）获得的证明。

工作量证明系统（或协议、功能）是针对拒绝服务攻击和其他服务滥用的经济对策。它需要发起者执行一定数量的操作，这意味着它需要消耗一定的计算机时间。这个概念是在 1993 年 Cynthia Dwork 和 Moni Naor 的学术论文中首次提出的。工作量证明 (POW) 一词是在 1999 年 Markus Jakobsson 和 Ari Juels 的一篇文章中才真正提出的。

HashCash 是一种工作量证明机制，由 Adam Back 在 1997 年发明，用于抵御电子邮件拒绝服务攻击和垃圾邮件网关滥用。在比特币之前，HashCash 被用于垃圾邮件过滤，微软也将其用于 hotmail/exchange/outlook 等产品中（微软使用了一种与 HashCash 不兼容的格式，并将其命名为电子邮戳）。

Hal Finney 还以可重用工作证明 (RPOW) 的形式在比特币前的加密货币实验中使用了 Hash Cash。此外，比特币的先驱戴维的B-money和Nick Sabo的Bit-Gold都是在Hash Cash的框架下挖矿的。

2. 哈希函数

散列函数，也称为散列函数，给定一个输入x，它会计算出对应的输出H(x)。哈希函数的主要特点是：

输入 x 可以是任意长度的字符串。输出结果是H(x)的长度是固定的。计算H(x)的过程是高效的（对于长度为n的字符串x，计算H(x)的时间很复杂。度数应该是O(n)）

对于像比特币这样的加密系统使用的哈希函数，它需要具有以下属性：

Collision-free，即不会有输入x≠y，但是H(x)=H(y)其实这个特性在理论上是不成立的。例如，比特币使用的 SHA256 算法将有 2^256 个输出。如果我们有 2^256+1 个输入，必然会发生碰撞；即使从概率的角度来看，有 2^130 个输入，也有 99% 的机会发生碰撞。不过我们可以算一下，假设一台计算机每秒散列 10,000 次，则需要 10^27 年才能完成 2^128 次散列！甚至可以说，即使人类制造的所有计算机从宇宙诞生到今天都在运行，但发现碰撞的概率极小。隐身，即对于给定的输出 H(x)，在计算上不可能反转输入 x。

上述特征是比特币工作量证明系统正常运行的基石。

3. 工作量证明的基本原理

工作量证明系统的主要特点是客户端需要做一些困难的工作才能得到结果，但验证者可以很容易地通过结果检查客户端是否完成了相应的工作。该方案的一个核心特征是不对称：对请求者来说工作量适中，对验证者来说易于验证。它与验证码不同，验证码的设计目的是人类容易破解，但计算机不易破解。

下图展示了工作量证明的流程：

例如，给定一个基本字符串“Hello, world!”，我们给出的工作量要求是可以在字符串后面加上一个叫做nonce的整数值，并对改变后的（添加的nonce）字符串进行SHA256哈希运算。如果得到的哈希结果（十六进制形式）以“0000”开头，则验证通过。实现这一工作量证明目标。我们需要不断增加 nonce 值并对生成的新字符串执行 SHA256 哈希运算。根据这条规则，我们需要经过 4251 次计算才能找到前 4 位正好为 0 的哈希。

复制代码

 
"Hello, world!0" => 1312af178c253f84028d480a6adc1e25e81caa44c749ec81976192e2ec934c64
"Hello, world!1" => e9afc424b79e4f6ab42d99c81156d3a17228d6e1eef4139be78e948a9332a7d8
"Hello, world!2" => ae37343a357a8297591625e7134cbea22f5928be8ca2a32aa475cf05fd4266b7
...
"Hello, world!4248" => 6e110d98b388e77e9c6f042ac6b497cec46660deef75a55ebc7cfdf65cc0b965
"Hello, world!4249" => c004190b822f1669cac8dc37e761cb73652e7832fb814565702245cf26ebb9e6
"Hello, world!4250" => 0000c3af42fc31103f1fdc0151fa747ff87349a4714df7cc52ea464e12dcd4e9

通过这个例子，我们对工作量证明机制有了一个初步的了解。有人会认为，如果工作量证明只是这样一个过程，是不是只需要记住nonce是4521，计算就能通过验证？当然不是，这只是一个例子。

下面，我们简单将输入改为“Hello, world + 整数值”，整数值范围为1到1000，即把输入变成1000个值的数组：“Hello, world!1、@ >你好，世界！2...你好，世界！1000”。然后依次为数组中的每个输入执行上述示例中所需的工作量证明 - 找到具有前 4 个零的散列。

很容易计算出，预计需要大约 2^16 次尝试（散列值的伪随机性质允许我们进行概率估计）才能得到一个前导 4 个 0 的散列。并且统计一下刚刚执行的 1000 次计算的实际计算结果，我们会发现平均执行的计算次数是 66958 次，非常接近 2^16 (65536）。在这个例子中，数学所期望的计算是比特币技术指标，是我们需要的“工作量”，重复多次的工作量将证明是符合统计规律的概率事件。

统计的输入字符串列表和用于获取目标结果的实际计算次数如下：

复制代码

 
Hello, world!1 => 42153
Hello, world!2 => 2643
Hello, world!3 => 32825
Hello, world!4 => 250
Hello, world!5 => 7300
...
Hello, world!995 => 164819
Hello, world!996 => 178486
Hello, world!997 => 22798
Hello, world!998 => 68868
Hello, world!999 => 46821

比特币系统中的工作量证明机制与上面的例子类似，但稍微复杂一些。

4. 比特币工作量证明

如果比特币网络中的任何一个节点想要生成一个新的区块并将其写入区块链，就必须解决比特币网络的工作量证明难题。这个问题的三个关键要素是工作量证明函数、块和难度值。工作量证明函数是这个问题的计算方式，区块决定了这个问题的输入数据，难度值决定了这个问题需要的计算量。

4.1 工作证明函数

与上一节示例中使用的哈希函数一样，比特币系统中使用的工作量证明函数是 SHA256。

SHA 是 Secure Hash Algorithm 的缩写，是一系列加密哈希函数。这组函数由美国国家安全局 (NSA) 设计并由美国国家标准与技术研究院 (NIST) 发布，主要针对数字签名标准。SHA256 是该系列函数之一，是一种哈希算法，输出值为 256 位。到目前为止，还没有针对 SHA256 算法的有效攻击。

4.2 块

比特币区块由区块头和区块中包含的交易列表组成。区块头大小为80字节，由4字节的版本号、32字节的前一个区块的哈希值、32字节的Merkle Root Hash、4字节的时间后缀（当前时间）、4它由以字节为单位的当前难度值和一个 4 字节的随机数组成。块中包含的交易列表附加到块头中。第一个交易是coinbase交易，是矿工获得奖励和费用的特殊交易。

块的一般结构如图所示：

固定长度为 80 字节的块头是用于比特币工作量证明的输入字符串。因此，为了让区块头反映区块中包含的所有交易，在区块的构建过程中，需要通过 Merkle Tree 算法生成 Merkle Root Hash，并将其作为交易列表。摘要存储在块头中。Merkle Tree的算法说明如下：

4.3 难度值

难度是矿工在挖矿时的一个重要参考指标，它决定了矿工需要经过多少哈希运算才能产生一个合法的区块。比特币区块大约每 10 分钟生成一次。如果要在全网不同的算力条件下以相同的速率产生新的块，则必须根据全网算力的变化来调整难度值。简单地说，难度值的设置使得新块生成率保持在每 10 分钟一个，而不管挖矿能力如何。

难度调整在每个完整节点中独立且自动发生。每 2016 个区块，所有节点都会根据统一的公式自动调整难度。这个公式是根据最近 2016 个区块的成本和预期时间（预期时间为 20160 分钟或两周，即每 10 分钟一个区块）计算的。根据实际时长与预期时长的比例，进行相应的调整（或变得更难或更容易）。也就是说，如果出块快于 10 分钟，则增加难度，如果出块慢于 10 分钟，则降低难度。

这个公式可以总结如下：

复制代码

 
新难度值 = 旧难度值 * ( 过去 2016 个区块花费时长 / 20160 分钟 )

工作量证明需要有一个目标值。比特币工作量证明的目标值（Target）计算公式如下：

复制代码

 
目标值 = 最大目标值 / 难度值
其中最大目标值为一个恒定值：
0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

目标值的大小与难度值成反比。比特币工作量证明的实现是矿工计算的区块哈希值必须小于目标值。

对比第 3 节的例子，我们也可以简单理解比特币工作量证明的过程，就是通过不断改变区块头（即尝试不同的 nouce 值）作为输入，进行 SHA256 哈希运算，寻找哈希的过程特定格式的值（即需要一定数量的前导0）。需要的前导零越多，难度越大。

4.4 工作证明流程

我们可以大致总结比特币矿工解决这个工作量证明难题的步骤如下：

生成 Coinbase 交易，与所有其他交易形成交易列表，打包成区块，通过 Merkle Tree 算法生成 Merkle Root Hash，将 Merkle Root Hash 等相关字段组装成区块头，将区块头的 80 字节数据组合起来区块头（Block Header）作为工作量证明的输入，不断改变区块头中的随机数，即nonce的值，每次改变后对区块头进行双SHA256运算（即SHA256（ SHA256(Block_Header)))，将结果值与当前网络的目标值进行比较。如果小于目标值，则问题成功解决，工作量证明完成。

该过程可以用下图表示：

5. 结论

比特币的工作量证明是我们通常所说的“挖矿”的主要工作。了解工作量证明机制将为我们进一步了解比特币区块链的共识机制奠定基础。在后续文章中，我们将详细介绍比特币交易和区块的结构和同步过程，最长链机制，以及达成共识的原则。

感谢郭磊对本文的策划和审阅。

为InfoQ中文站投稿或参与内容翻译，请发邮件至editors@cn.infoq.com。也欢迎您关注我们的新浪微博（@InfoQ比特币技术指标，@丁晓云）和微信（微信：InfoQChina）。