January 17, 2020

重新创造比特币19:工作量证明（下）

作者：何岩，由 recreating.org发行。

0.前言 #

本篇我们就来讨论上一篇引出的核心问题：设计出一个可以证明工作量的题目。

1.寻找随机数 #

很多时候，现实中冥思苦想的问题，在梦中确可以很轻松的得到答案。

中本聪在梦境中尝到了好处，现在还不是醒来的时候。

牛头人问：“什么样的题目可以证明节点付出的工作量呢？”

小男孩说：“我想到的是：寻找随机数。这就好比去猜测一个人的生日，你只要趴在桌子上一直写呀写，总有一次可以猜中，只不过会花些体力，你付出的简单劳作就是工作量。”

牛头人说：“我懂了，题目的本质就是不含任何逻辑的随机碰撞，随机碰撞最公平。”

小男孩说：“对！我想到的工作量证明题目，猜的不是某人的生日，而是猜一个普通数字，这个数字添加到原来的消息后面，再对其求Hash，使得Hash值前面有很多个0。

大家约定，想要拥有记账权，必须先要找到一个幸运数字，使得“区块消息＋幸运数字”的Hash值以5个0开头。

这里的“5”就代表难度，Hash前缀的0越多寻找的难度越大。”

停顿了一下，小男孩觉得牛头人可能没有听明白，于是动手开始实际演示。
因为区块消息比较长，我们用一句简短的消息来代替："安心即乐土"。
先对这句话求Hash，"安心即乐土"的Hash值为7511cedf823f0757d66c26769c8d15f8597e4384420e6cbebb0acbec5e73344a。

我们看到，一般的Hash值都不会以0开头。

接下来的任务，是找到一个幸运数字，使得‘安心即乐土＋幸运数字‘的Hash值的前5位都是0，这个幸运数字就是我们要找的随机数。

我们从0开始，将0添加到"安心即乐土"后面，变成："安心即乐土0"，求得Hash值：0b3844eec6204d01……

因为，这个Hash值不以5个0开头，所以0不是符合规则的幸运数字。
继续寻找，开始体力劳动：

消息＋幸运数字 Hash值前N位

安心即乐土0 0b3844eec6204
安心即乐土1 ebf1bbf0e1d2bc
安心即乐土2 45963e7cbe226
安心即乐土3 6b9e76dd1ca27
安心即乐土4 ebf1bbf0e1d2bc
安心即乐土5 6ec12dcfee54ffe
安心即乐土6 53bde13314663
安心即乐土7 d348d2eee3e8d
安心即乐土8 276cfcd1386ffbd
安心即乐土9 f78628f2b0e4e
安心即乐土10 fe2e8cd0e0f3
安心即乐土11 5cc0bc8d34f5fb
安心即乐土12 764154ddd623
安心即乐土13 e6c3bcb245fd
安心即乐土14 7c18fb827e48
安心即乐土15 283f7de03f01
安心即乐土16 bce71436c4e
安心即乐土17 4f76be60fb2b
安心即乐土18 182530c711d1
安心即乐土1e 6d5ec71c30c1
安心即乐土20 b0161336bbbe
安心即乐土21 d1f35d0522b3d
安心即乐土22 e118e2ce041d
安心即乐土23 052083fffd51d

终于找到一个以0开头的，但是没有发现以5个0开头的，甚至没有以2个0开头的，继续寻找…

安心即乐土520 e1f34d0t22b3
安心即乐土521 g11ee2cg04sd
安心即乐土523 0092e10ae10a

终于在第523轮，发现了一个前缀是连续2个0的Hash值，继续寻找…

一直找…

百折不挠…

过了很久很久，终于找到了！

“安心即乐土832290344"的Hash值为：00000d4955bc5445e97…

我们看到这个Hash值以5个0开头，所以，832290344就是我们要找的幸运数字。

我们知道Hash值不可以倒推，所以只能随机碰撞，这8亿多次的随机碰撞，就是我的工作量证明。

得到幸运数字之后，我就等于获得了记账权。接下来我就可以将这个区块消息广播出去，提供给其它节点同步。

牛头人收到这条区块消息："安心即乐土832290344”

对其进行Hash计算，得出的Hash值满足我们的约定，即以5个0开头。

牛头人就可以判定小男孩是付出了很大的工作量，付出了成本的人，大概率不会造假，所以将其同步到自己的账本中。

同时，牛头人再将这条区块消息路由广播给其它邻居。

其它节点也会像牛头人一样，进行验证和路由广播，小男孩的区块就会迅速被整个网络确认，成为最终账本中的一页。

2.区块结构的改造 #

小男孩继续补充到：“当然，‘安心即乐土832290344’只是在映射已经计算出随机数的区块消息，真实的区块结构会比较复杂，但是原理是一样的，因为寻找随机数的难度与区块消息的内容和长度无关。

下面我们来看一下区块结构如何改造，可以承载工作量证明的新机制。

我们可以将随机数放在区块的Header中，而不用一定是放在区块的尾部。

另外Header中还需要加一个字段，来表示计算难度，例如5个0的Hash值前缀就表示难度值为5，9个0的Hash值前缀就表示难度值为9，难度值可以根据最近2016个区块的平均计算时间来进行动态调整，目的是让区块产生的间隔始终保持在10分钟左右。（改造后的区块结构见下图。备注：在真实世界中Difficulty应该为nBits，现在为了保持简单性，做了简化。）

加入随机数和难度值字段的区块结构

2.1.Block Header Chain #

牛头人说：“我发现一个问题，每次寻找随机数，运行Hash函数的时候，得把区块数据读取到内存里，再塞给Hash函数去计算吧？”

小男孩说：“对啊，函数运算当然要用内存啊”

牛头人问：“你的内存多大？”

小男孩答：“512MB啊！呀呀呀！我明白你要说什么了，如果随着系统发展，交易量会越来越大，意味着区块也会越来越大，那么总有一天区块大小会超过我的内存上限，到那时候我就运行不动Hash函数了！”

牛头人说：“我的内存更小，咱们的初衷是拼工作量，别到了最后变成拼内存了。”

小男孩问：“对呀！本来是比谁干得多，现在这是要比谁长的胖啊！这可如何是好？”

牛头人说：“我想到一个改进方案，虽然不能完全解决内存问题，但是能大大减轻系统压力。“

牛头人解释起来：总的思路是拆解，将寻找随机数拆成两个部分，

第一个部分是用数字指纹来代替交易数据，即，计算出区块Transactions部分的Hash值，这个Hash值就等于是Transactions部分的数字指纹，数字指纹的作用是可以单向验证Transactions中的交易数据是否篡改。因为如果改动任何一笔交易，再无法得到相同的数字指纹(或称之为摘要）。

第二个部分是用区块Header的Hash值代替区块的Hash值，即，将上个步骤得到的数字指纹作为新字段：Transactions Hash，加到Header中。因为数字指纹可以验证原始数据，那么，Transaciions Hash就可以代表Transactions部分，所以Header就可以代表整个区块。所以，寻找随机数就由之前的计算区块Hash值，就变成计算区块Header的Hash值了。

第一部分只需要运行一次，第二部分要运行上很多很多次。这样一来我们就把内存不够的问题就缩小到了只运行一次的第一部分中。从而，大大减轻了系统的吞吐负担。又因为操作系统具有虚拟内存能力，可以将硬盘虚拟成内存来欺骗cpu，虽然运行速度会变慢，但也就运行一次，也还可以接受。（见下图）

Header中加入Transactions的摘要

Header可以代表整个区块，Header的Hash值就可以代替之前的区块Hash值，这样一来Block Chain本质上就变成了Block Header Chain。

Block Header Chain的意义在于，随着系统发展，Transactions部分越来越大，假设达到了区块平均2TB，但是Header不会增长，永远不会超过1KB。这时候某些记账节点为了节省存储空间，哪怕裁剪了某些区块的

Transactions数据，只要还完整保留Header部分，就还是可以独立验证任意一个区块的数据是否被篡改。

换句话说，Bitcoin系统用来保障诚实的存储成本可以很小。（见下图）

Block Header Chain

2.2.Merkle Tree #

接下来，我们将焦点放在第一部分的内存危机问题。

既然一口吃不下大象，我们就采取蚂蚁吃大象的方式，即，时间换空间：多次、组合的进行Hash计算。

具体怎么做呢？

我们假设当前区块的Transactions部分包含4笔交易分别是：TxA、TxB、TxC、TxD。

所谓一口一口吃，就是从最小粒度交易入手，第一轮分别计算每笔交易的Hash值：HA=Hash(TxA)、HB=Hash(TxB)、HC=Hash(TxC)、HD=Hash(TxD)
第二轮继续一口一口吃，将上一轮的产出物两两组合后继续计算Hash值：HAB=Hash(HA+HB)、HCD=Hash(HC+HD)

如此类推，直到最后剩下一个Hash值，我们这个例子只要到第三轮就到头了：HABCD=Hash(HAB+HCD)

这种归纳所有交易的结构就称之为Merkle Tree，最后一轮得到的树根就是Merkle Root（如下图）

Merkle Tree

Merkle Tree不仅仅解决了内存危机，也解决了存储危机。

什么意思呢？

如果采用第一个Transactions Hash的方案，一个内存和存储都很小的SPV轻节点，已经存储了所有的Block Header Chain（也就几十MB），这时候SPV想要根据自己的Block Header Chain来独立验证某个区块数据是否被篡改，就很可能因为区块过大而无法完成，因为存储空间装不下这个区块中的Transactions部分。这就是所谓的存储危机。

Merkle Tree则能完美的解决这个问题，它提供了一种极其高效途径来验证区块中的某笔交易是否被篡改。

对于下面这颗Merkle Tree（见下图）

Merkle Tree的验证路径

为了证明交易 K 在区块中，可以用 HLHL、HIJHIJ、HMNOPHMNOP 和 HABCDEFGHHABCDEFGH 这四个Hash值构造一条“Merkle 路径”，只需 128 字节。任何SPV轻节点只需要向记账节点发起交易K的验证请求，记账节点只需要返回128个字节的Merkle路径，而不是区块的所有Transactions，SPV轻节点就可以根据自己之前已经存储的Block Header Chain中的Merkle Root来验证这笔交易的真伪。

这样一来，记账节点不再担心内存、SPV轻节点不再担心存储。

最后，还需要改造一下Block Header，将Merkle Root替换掉之前的Transaction Hash字段（如下图）

SPV只需要存储Block Header Chain

3.里程碑V0.1.0版本 #

中本聪猛然醒过来，趁着记忆还算清晰，赶紧打开笔记本，按照小男孩的启发修改起代码来。

中本聪专注的写了整整2周，Bitcoin系统升级好了，工作量证明方案替代了之前的临时方案（单点timestamp server）。

所有节点更新至最新版本，重启运行，Bitcoin系统去掉了所有单点，第一次成为了真正意义上的群系统。

从另一个视角，可以将Bitcoin系统看成是一个真正分布式的时间服务器（去中心化的timestamp server）

因为这次系统升级实现了质的飞跃，所以中本聪将版本号定为了v0.1.0。
我们来看看，v0.1.0版本的系统功能有哪些（见下图）

v0.1.0版本的服务端功能

服务端包括这么几个部分：
1.网络连接：负责Bitcoin网络的自治。
2.交易处理：负责Bitcoin系统的交易处理，属于系统的现在时。
3.区块处理：负责Bitcoin系统的交易备份，属于系统的过去时。
4.交易内存池：存储实时的交易数据。
5.Block Chain：存储过去的交易数据。

其中新添加的是区块处理部分：
1.计算随机数：就是上面提到的工作量证明，获得随机数。
2.生成区块：就是在记账，如果计算出了随机数，就可以将自己生成的区块广播出去，获得区块奖励。如果没有顺利计算出随机数，则放弃自己生成的区块，而选择同步网络中传递过来的区块。
3.区块同步：同步其它节点的区块消息到自己的本地账本（Block Chain）。
4.区块验证：通过一系列验证，来确保同步过来的区块是正确的。

由于生成区块和计算随机数的目的是赚取区块奖励和交易手续费，其行为很像在地下随机的挖掘金矿，所以可以将这种行为称为挖矿，记账节点也就可以称之为矿工。（见下图）

set in stone：一旦0.1版本发布，核心设计在其整个生命周期中都是一成不变的

4.竞争 #

系统刚升级完，咖啡馆里的3台机器一下子变得嗡嗡作响。它们在争分夺秒的挖矿。

每台矿机都想成为第一个找到那个随机数的幸运者。

竞争是一轮接着一轮，每轮竞争大概的时间是10分钟。

我们将视角聚焦到小男孩、牛头人和黄鼠狼之间的竞争。

小男孩正在计算着自己的随机数，忽然邻居节点广播了一个新出炉的区块消息，小男孩一看，这个区块是三爷（节点3）生成的，心想三爷的机器性能不错啊，这一轮输给你了，我得赶紧把三爷的这个区块加入到自己的账本中，然后马上开始下一轮竞争。

于此同时，牛头人和黄鼠狼也收到了三爷的新区块，处理过程和小男孩一样，也马上同步完区块，开始了下一轮的竞争。

所以说，一个新的区块消息在网络中的广播，可以看成是一个以节点为中心的水波在网络的世界扩散，宣布着本轮的竞争结束，新的一轮开始啦！

节点在广播区块消息

区块构建 #

新的一轮竞争开始了！

小男孩首先要构建自己的区块数据，区块的交易数据来自于自己的内存池，选择几条交易数据放入本轮的区块之中是节点的自由，你可以选择几百条记录，也可以选择几万条记录。

所以，每个矿工构建的区块中的交易记录都可能不同。

当然，选择的交易记录越多，你会收获的手续费就越多，但是你的处理逻辑和广播速度就会变慢。

这需要矿工根据自己的情况来进行平衡。

甚至有的矿工追求极限的速度，构建的区块中不加入任何交易记录，只有一条区块奖励记录。这就是传说中的空区块。当然，这也算符合规则，可以被系统接受。

小男孩根据自己的情况，按照交易费用由高到底的排序，从内存池中选择了前100条交易记录，将它们加入了新构建的区块的Transactions部分。

然后将区块的Header部分的字段一一填写好，只剩下了随机数这个字段没有填写。

接下来，小男孩开足马力，开始寻找那个唯一的随机数。

与此同时，竞争者黄鼠狼和牛头人也在做着同样的挖矿行为。

只不过黄鼠狼死心不改，还想再次将区块奖励的数字由50改为500。

黄鼠狼为了追求区块的构建和传播速度的极限，竟然构建了一个空区块，区块的Transations中只有一条区块奖励的交易记录，奖励的数字是500Bitcoin。

然后同样开始开足马力的计算随机数。

黄鼠狼曾经想过，能不能在上一轮区块广播之前就提前开始计算随机数，后来发现不行，因为新的一轮的区块中要在Header中填写上一轮区块的Hash值，所以必须得等到上一轮的区块消息传递到自己手里，才能开始。

区块广播 #

小男孩，牛头人和黄鼠狼就像是在同一条跑道上赛跑。先发出区块广播者就是冠军。

经过了10分钟左右的激烈竞争，黄鼠狼在10分11秒第一个找到了随机数，小

男孩稍微慢了一点在10分13秒找到了随机数，牛头人最慢在10分14秒找到了随机数。

黄鼠狼开心坏了，急忙将找到的随机数填写到区块中，并将区块消息广播了出去。

小男孩和牛头人也同样将自己的区块消息广播到网络中。

接下来就看网络中的其它节点来投票了。因为它们三个广播的时间几乎是同时发出，所以还可以彼此竞争一下，这就好像水面上同时有3个水波在扩散。（见下图）

三个节点三个水波

区块验证 #

因为Bitcoin的点对点网络的特性很像水面，所以大概率，最先发出的水波会最先传遍整个水面。

果然，黄鼠狼的区块消息被其它节点首先收到，但是大家不会盲目的将这个区块加入到自己的账本中。

而是首先要进行区块验证：区块的语法是否正确，区块中的交易是否合法。
当大家验证发现黄鼠狼的区块奖励不符合约定，大家都皱起眉头，果断将黄
鼠狼的区块消息放弃。

紧接着大家又收到了小男孩和牛头人的区块消息。因为小男孩发起广播的时间比牛头人快了1秒，所以整个网络中，大多数的节点都是先收到了小男孩的区块消息。

大家同样对小男孩的区块进行验证，发现没有问题，就马上将其同步到自己的账本中。然后马上进入下一轮的挖矿竞争中。

网络的弹性 #

这时候你会问，还有一小部分节点，由于离牛头人的距离更近，先接受到了牛头人的区块消息，那么如果它们也以先收到的区块为准，进行同步，那岂不是选错了区块。

其实不会，节点在收到牛头人的区块消息之后，不会马上认同，而会看看身边的邻居是否也同样在广播牛头人的区块消息，如果发现身边的邻居广播的区块消息和自己一样，则可以认同牛头人的区块是最先发出。如果发现身边的邻居广播的区块不同，有的邻居广播的竟然是小男孩的区块消息，节点就会怀疑自己收到的牛头人的区块没准不是最先发出。这时候就要统计一下邻居的广播，发现10个邻居中有7个人都在向外广播小男孩的区块消息，只有3个人在广播牛头人的区块消息，所以就得出结论，小男孩才是正确的选择。
当然，也会存在特殊情况，如果身边的邻居也错了，那么这一小部分节点就会错误的选择了将牛头人的区块同步到了自己的账本中。这种时候系统中就存在两套账本，这就是暂时性的区块链的分叉。(见下图)

分叉

关于分叉的问题我们下一篇在来详细讨论。

竞争守护正义 #

我们回过头再来看看可怜的黄鼠狼，由于自己的区块被大多数节点的放弃，自己感觉赔了一个亿。

自己付出那么多劳动成本，全都作废了。

黄鼠狼在思考，要不以后就好好做人，不再偷鸡摸狗了，就正常挖矿赚Bitcoin得了。

经过这次教训，黄鼠狼老实了一点。

投票 #

讲过上面一轮的竞争，我们可以看出，节点选择同步哪个区块，就等于在给自己认同的区块投票。

投给自己认为正确，并且最早的区块。

基于竞争机制的民主投票才可能朝着正确的方向前行。

5.后记 #

Bitcoin本身是车轮，全球账本（Metanet）才是车，比特币是这个全球账本上的通用货币，其目的是提供这辆车的燃料，维护这个不可篡改账本的安全以及提供经济激励。在有了使用价值之后，才延伸出“通用货币”，或者说“钱”的属性。只是在造车的时候，需要先造轮子，再有了轮子之后，才上车架。

下一篇我们将讨论分叉的概念。

参考： #

公众号：汤强《鸡一嘴鸭一嘴，应该听谁？》- https://mp.weixin.qq.com/s/DgKUftTAgdpKnox6ZpLq8Q

下一篇：重新创造比特币20:分叉之重组与分裂