从拜占庭容错到工作量证明

前几天那篇文章在其他平台分发、转化的还不错，今天再续前缘补充一下那篇文章里面一个没有填的坑——拜占庭容错。

严正声明，本文仅限对于区块链技术本身的探讨，不涉及对任何数字虚拟货币的推荐。

一、从一个小故事说起

拜占庭将军问题（Byzantine Generals Problem），由莱斯利·兰伯特（Leslie Lamport）在1982年首次提出，成为了困扰了计算机科学家们数十年的难题。

故事模型比较简单，梗概如下：

拜占庭帝国（中世纪时期的土耳其）拥有巨大的财富，周围10个邻邦垂诞拜占庭帝国的财富已久。但拜占庭固若金汤，任何一个单独的邻邦都不能够成功攻占拜占庭。

由于拜占庭帝国国力很强，10个邻邦中，至少要有一半以上的邻邦同时进攻，才有可能攻破。

然而，如果其中的一个或者几个邻邦本身答应好一起进攻，但实际过程出现背叛者（Traitor），那么进攻将会失败。

每一个邻邦在协商总体进攻的时候都小心翼翼，不敢轻易的相信其他邻邦。

这就延伸出，在进攻拜占庭这件事情上，对各邻邦来说最重要的议题是：将军们如何在非信任环境中建立共识，让所有忠诚的将军统一行动计划集体进攻拜占庭帝国。

二、达成共识的解决方案——引入记账成本

在达成共识的过程中，在10个将军里面可能出现背叛者导致任务失败：

（1）背叛者怂恿忠诚者采取不良计划。

（2）忠诚者的数量小于2/3，拜占庭问题不可解。

（3）背叛者可能欺骗其他人自己会采取进攻行动（实际不会进攻）。

（4）10个将军中同时发起进攻信息，造成整个通信系统的混乱，各说各的攻击时间方案，行动无法达到一致。

如果任何人都可以随时发起进攻信息，大家自说自话，整个通讯体系就瘫痪了。那么如何决定某个时间点信息由谁来发出呢？

比特币的创始人中本聪在通讯系统加入了发送信息的成本：一段时间内只有一个节点可以传播信息（记账）。

这个记账的成本就是「工作量」——邻邦国（节点）必须率先做一道很难的数学题（率先完成计算工作）才能向其他邻邦传播消息（获得记账权），这个很难的数学题是绝对公平的，大家一起算，只能一个数一个数穷举试错，完全随机的，看谁先穷举出来。

谁先算出答案（第一个完成计算工作），谁就能先获得传播进攻消息的权利（获得记账权）。只有随机才是真正的公平，实现随机的最好办法是使用数学，所有的将军在寻找共识的过程，借助了大家都认可的数学逻辑。

在分布式网络里，区块链上的共识机制主要解决由谁来构造区块，以及如何维护区块链唯一性的问题。

拜占庭将军容错问题需要解决的也同样是谁来发起信息，如何实现信息的统一同步的问题。

基于区块链技术，通过使用消息加密技术、以及公平的工作量证明机制，创建了所有邻邦都认可协商方案的通讯协议，这套共识协议的出现，使得拜占庭将军问题得到完美的解决。

三、保证信息传输的可信——非对称加密

解决了某一时间由谁发的问题，那么怎么确定发信人的身份不是被伪造呢？

当某个邻邦发出自己认可的进攻信息后，其他邻邦收到发起者的消息必须签名盖章，确认各自的身份。中本聪在这里引用非对称加密技术为这个信息签名。

非对称加密算法的加密和解密使用不同的两个密钥.这两个密钥就是我们经常听到的”公开密钥”(公钥)和”私有密钥”(私钥)。

公钥和私钥一般成对出现, 如果消息使用公钥加密,那么需要该公钥对应的私钥才能解密; 同样，如果消息使用私钥加密,那么需要该私钥对应的公钥才能解密.

非对称加密的作用是:保护消息内容, 并并且让消息接收方确定发送方的身份。

比如，将军A想给将军B发送消息，为防止消息泄露，将军A只需要使用B的公钥对信息加密，而B的公钥是公开的，B只需要用只有他自己只的私钥解密即可。

将军B想要在信件上声明自己的身份，他可以自己写一段”签名文本“，并用私钥签名，并广播出去，所有人可以根据B的公钥来验证该签名，确定的B的身份。

通过这种方式，一个不可信的分布式网络变成了一个可信的网络，所有的参与者可以在某件事在达成一致并提供了以下几点保证：

（1）信息传送的私密性 ；

（2）能够确认签名的真实性；

（3）签名不可伪造、篡改 。

（4）PoW验证者可以快速检验工作量是否达标。

四、工作量证明PoW

建立信任是有成本的，我们也就能明白比特币通过区块链这个技术进行工作量证明PoW（Proof of Work）的意义。

在1999年，Markus Jakobsson和Ari Juels两人将PoW概念引入用以抵挡DDOS攻击和反垃圾邮件。PoW设计原理是一个正常用户写一封邮件是需要一定的时间，工作量证明能够使垃圾邮件发送者需要更多的时间来发送邮件（相当于计算机每算完成一道题，才能发送邮件），就可以通过增大大量发送垃圾数据的成本，来提高发送垃圾邮件者的机会成本，从而抵挡攻击。

在数字货币中的PoW工作量证明过程，就是「挖矿」的过程。「挖矿」表面上来看浪费了社会资源，但是「挖矿」是维护比特币网络可靠性和达成共识的非常高效且靠谱的办法。通过竞争记账方式解决去中心化的账本一致性，用工作量证明PoW的机制来实现竞争结果判定。工作量证明完成后，产生新的区块。当新区块在网络中传播时，每个节点广播到其他节点。

工作量证明步骤如下:

1.构建区块，把将要写入区块交易信息组成交易列表，通过Merkle树算法把交易列表信息生成Merkle根哈希。

2.组装成区块头，把区块头80字节数据作为数据输入。

3.穷举区块头的随机数：nonce的数值，变更nonce后把区块头不断采用两次SHA256运算。与目标值做对比，如果小于目标值（结果前面有更多的0），则找到我们所需的随机数，工作量被证明是有效的。

在分布式网络中的任何一个节点，如果想生成新的区块并写入区块链，必须解出特定要求的PoW题目。解出题目关键3个要素是：工作证明函数、区块和难度值。

五、工作量函数，区块和难度值

比特币使用SHA256作为工作量证明函数。SHA256是安全散列算法SHA（Secure Hash Algorithm）系列算法之一，其摘要长度为256bits，故称SHA256，比特币挖矿算法中使用的哈希算法是SHA2-256。

区块决定输入数据，因为使用区块头作为工作量证明输入数据。在挖矿过程中，矿机把比特币的80个字节长度的区块头数据做两次SHA256运算。哈希运算结果要满足前n位均为0要求，区块头的详细情况请见下图。

在构造区块过程中，需要将该区块要含有的交易信息列表，通过Merkle树诉算法生成哈希值，把它作为区块头Merkle根的值。

Merkle树是完全二叉树，通过哈希值的计算，将这棵二叉树转化为Merkle树。

上图示例中四个交易分别计算各自哈希值进行运算，得出Merkle树根。

现在区块头能有确定值的字段分别是：版本、父区块哈希值、Merkle根、时间戳。Nonce是用于工作量证明计数器，需要不断运算，是变量。

难度值决定大约需要经过多少次哈希运算产生一个合法区块。在全网算力不断变化，维持平均10分钟出一个区块，难度值必须根据全网算力的变化进行调整。

难度调整是每个完整节点中独立自动发生。每2016个区块，所有节点都会按统一公式自动调整难度，调整公式：

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

工作量计算有一个目标值：

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

目标值的大小与难度值成反比，比特币工作量证明要求矿工计算出来哈希值必须小于目标值，也即：哈希运算结果中前n位数为0的数目n要大于等于目标值的前几位为0的数目，这样运算结果才比目标结果要小。

所需的为0的n值位数越多，需要运算量就越大。运算结果就是一个256位（32字节）长度的字符串，通过比较与当前难度值的大小判断当前区块是否合法。

六、解决冲突，免得扯皮——时间戳，最长链原则和奖励

在拜占庭进攻的例子中，如果不同的邻邦分别先后解出了题算出了答案，各自先后向分布式网络发布自己算出来的消息，造成消息混乱，怎么办？

只有时间最早的发起者才是有效的。比特币中，通过时间戳，为每个邻邦在解题完成的时间（出块时间）盖上时间印章。

就算两个挖矿的人同时挖出区块的可能（由于随机数的影响和网络的延时），这种情况也是时有发生的，如果他们一起记账就会造成区块链的分叉。

此时，系统就会根据最长链原则进行取舍，即哪个新产生的区块能使其所在的区块链变得更长，则哪个区块得以被记录。在这个博弈中，所有矿工的最优选择是：在最长链上挖矿，维护区块链账本的唯一性。

各个邻邦凭什么要一起耗时耗力的做工作量证明呢？中本聪设置了一个奖励机制，比特币的奖励机制是每解锁一个新块，目前是奖励12.5个比特币。正因为因为有比特币的奖励，所以矿工们都会争夺每十分钟一次的记账权。

在拜占庭将军问题中，奖励的就可以是瓜分拜占庭帝国的财富。

根据每产出21万个区块新比特币奖励就会减半的规则，下一次减半预计将发生在2020年5月。

七、出现背叛者怎么办

如果出现背叛者怎么办？

区块链中的节点，其中包括诚实节点和恶意的节点，就如何写入一个区块达成共识。PoW的容错性是50%，也就是说只要超过一半的节点是诚实的，就可以保证区块链数据的有效性。

历史上其他种类数字货币（BTG，骗得将近2000万美金）已经出现过通过51%攻击进行双花交易。“双花攻击”（double spend attack）就是一笔资金，通过某种方式被花费了两次。

怎么实现的呢？

根据前面说到的最长链原则，节点会认可并在此基础上继续延长当前最长链。

如果当攻击者拥有超过全网50%算力（实际操盘中甚至不需要严格超过50%），就可以选择先把自己手中囤积的大量数字货币售出并提现，这时候这笔交易已经写入区块链的“主链A”中。

攻击者在确认售出的数字货币提现成功后，马上在交易前的起始节点重新开一个分叉，分叉的交易信息是自己转给自己同伙张三（不转给原来的打款人）。由于自身算力超过全网算力的50%，假以时日，总能够将自己分叉的链变为最长的链进而成为“主链B”（最长链原则）。成功把虚假的交易写“主链B”中。

通过这种方式，“主链B”成为大家认可的“最长链”，不仅2000万美金现金到手，原来的数字货币也回到了自己账户中。这种双花攻击，越小算力的盘，越容易实施。

虽说如此，对比特币来说，先不说掌控超过比特币50%算力的有多难，及时掌握了这么大的算力。你会发现，用这个算力挖矿赚取收益，比双花的收益还高很多。

八、说在最后

这篇文章步子迈的有点大，像一口气吃个胖子。自己都感觉的出来很多东西也没有讲的特别清楚，而且写出来自己看着都觉得枯燥无聊。只能尽量的把相关的技术和原理通俗的形成文字讲出来。

比如说，比特币这个概念本身其实是UTXO，指未花费的交易输出，和币这个词本身其实没啥关系。比特币的记账系统，也不是记录谁谁的比特币余额和余额变动是多少，而是记录交易行为本身，每个人的最终余额是通过扫描交易数据计算出来的。