区块链共识算法--PoW

PoW算法是一种概率算法，其共识结果是暂时的。 随着时间的推移或某种强化，共识结果被推翻的概率越来越小比特币区块链的经济机制包括，最终称为事实结果

1 项研究

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

工作量证明系统（或协议、函数）是一种针对拒绝服务攻击和其他服务滥用的经济对策。 它需要发起者进行一定量的计算，这意味着计算机需要消耗一定的时间。 这个概念最早是由 Cynthia Dwork 和 Moni Naor 在 1993 年的一篇学术论文中提出的。工作量证明（Proof of Work，简称 POW）一词实际上是在 Markus Jakobsson 和 Ari Juels 1999 年的文章中提出的。

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

Hal Finney 还以可重用工作量证明 (RPOW) 的形式在前比特币加密货币实验中使用了 Hashcash。 另外，比特币的前身戴维的B-money和Nick Szabo的Bit-Gold都是在hash cash的框架下挖矿。

2 哈希函数

散列函数（Hash Function），又称散列函数，给定一个输入x，它会计算出对应的输出H(x)。 哈希函数的主要特征是：

1.输入x可以是任意长度的字符串

2、输出结果，即H(x)的长度是固定的

3、计算H(x)的过程是高效的（对于长度为n的字符串x，计算H(x)的时间复杂度应该是O(n)

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

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

3 工作量证明的基本原则

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

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

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

"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, Hello, world !2...你好，世界！1000”。 然后，对于数组中的每个输入，依次执行上述示例中所需的工作量证明——找到具有 4 个前导 0 的散列散列。

它很容易计算，预计需要大约 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 bytes 以字节为单位的当前难度值和以 4 字节为单位的随机数。 块中包含的交易列表附加到块头。 第一笔交易是coinbase交易，是矿工获取奖励和手续费的特殊交易。

block的一般结构如图所示：

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

4.3 难度值

难度值（difficulty）是矿工挖矿时的一个重要参考指标。 它决定了矿工需要经过多少次哈希运算才能生成一个合法的区块。 大约每 10 分钟生成一个比特币块。 如果要在不同的网络算力条件下都保持这个速率产生新区块，就必须根据网络算力的变化来调整难度值。 简单地说，难度值设置为每 10 分钟出一个新区块的速率，与挖矿能力无关。

难度调整在每个完整节点内独立且自动发生。 每2016个区块，所有节点都会根据统一的公式自动调整难度。 这个公式是根据最近2016个区块花费的时间和预期时间（预期时间为20160分钟或两周，以每10分钟一个区块为准。根据实际时长与预期时长的比值, 做相应的调整（或做难或易），也就是说出块速度快于10分钟，难度就会增加，慢于10分钟，难度就会降低。

这个公式可以总结如下：

新难度 = 旧难度 *（过去 2016 个区块的持续时间 / 20160 分钟）

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

目标值=最大目标值/难度值

其中最大目标值是一个常数值：

0x00000000FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

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

类似于第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 结论

比特币的工作量证明就是我们俗称的“挖矿”的主要工作。 理解工作量证明机制，将为我们进一步理解比特币区块链的共识机制打下基础。

参考链接：

程序员灯塔