上次文章中提到Bitcoin网络中各个节点是“黑暗森林”中的“猎人”，它们除了要“隐藏”自己，更重要的是要保证自己存的交易记录和其他节点的是一致的，要不然就有可能出现双重支付或者伪造支付的情况，如上海地区的节点中有交易记录A，但北京地区的节点中没有交易记录A，如果汇款方在上海，他说我已经支付过了，但收款方在北京，他说我没有收到过你的转账记录，你没有支付，得继续支付。这就是网络中节点状态不一致导致交易无法完成的情况。所以说，Bitcoin网络中最关键的问题是如何保证各节点在有限时间内达到状态一致。
这个问题先放一放，我先讲几个小故事。
《囚徒》
南纬15°56'， 西经5°42'，圣赫勒拿岛，发生一起抢劫案，警察迅速找到并逮捕了两名嫌疑人A和I。
警察将A和I关在两个封闭的审讯室里分开审讯，并对他们承诺：如果告发另一个人，可以无罪释放，另一个人构成抢劫罪会判10年；同时也明白告知他们：如果两人都招供，可以按自首处理，他们会一起判5年。A和I听到后，不以为然，因为他们知道，他们还有一个选择：只要两人都死扛，谁都不招供，只要警方找不到有力证据，他们最多被拘48小时。在行动之前，A和I就商量好了，一旦事发，两人必须咬死不招，这样对大家都有好处。
A和I在审讯室里沉默了几个小时，警察着急了，开始对他们攻心: 如果你们中一方选择告发另一个人，那么被告发的那个人要么被判5年，要么被判10年，而告发的那个人要么被释放，要么被判5年，其中利害你们自己想一想。然后故意向A和I分别透露已经掌握的一些证据，让他们以为是对方向警方提供的。A和I一开始都咬定准备死杠了，因为很显然，这对双方都有好处。但时间一分一分地煎熬，加上警方的分化，他们内心都出现了动摇。他们知道他们的关系并非是牢不可破，从对自己有利的角度来想，选择告发对方可以肯定地减少自己的刑期，最差也是5年，肯定不会是10年；但如果自己死杠，一旦对方选择告发，那自己就是10年，而对方在外逍遥了。思来想去，A和I都觉得不能牺牲自己的利益来换取可能的最大化的共同利益，所以不约而同地选择了告发对方。。。
《议员》
北纬37°58'，东经23°43'，古希腊雅典城，男人们在大声讨论着。令人讨厌的波斯不停地侵扰着半岛，为了加强防御、一致对外，各城邦需要强化联系，就一些事务共同决策。于是在雅典城和斯巴达城的共同提议下，各城邦派出代表齐集雅典市集，商讨各城邦如何有效地共同商讨决策问题。为了方便叙述，我们暂且称这些代表为议员，虽然直到罗马才有。
斯巴达方的议员们比较冷静和强势，他们直接指出：各城邦之间只能通过送信的方式联络，但城邦之间有的有山脉和海湾阻隔，送信可能有很长时间的延迟，或者送信人在中途出意外导致信根本就送不到对方；而且，城邦收到议事的信后，还要就所议事情在内部召集人们讨论，可能需要较长时间回复，或者有些东部城邦由于在和波斯交战，暂时根本没有精力来参与议事，要等战争结束后才能参与进来。此言一出，各大小城邦议员纷纷点头称是。在长期的民主政体熏陶下，雅典议员们较为平和与沉着，其中有一长者，略一沉吟说到：大家的初衷都是一致的，就是要在通信不畅或者议事不及时的情况下，就共同的提案商议以达成一致决议，所以我们各城邦要真实表达自己的投票意见，不能故意扰乱协商过程，大家的目标都是尽快地达到一致决议。众议员纷纷点头称是。随后，大家便开始商讨各种达成决议的办法。
其中，米利都城的议员提议到：让有提案的城邦派信使将其提案送给其余各城邦，等各城邦投票后再由信使送还，收集各城邦投票结果后再根据多数城邦的意见形成决议，再由提案城邦派信使将决议通告各城邦即可。小亚细亚沿岸各城邦纷纷点赞，认为此举应该能让大家达成决议。
但哈尔基斯城的议员立即反问到：如果信使没能送到，或者城邦当时无法回复，导致收集到的投票始终无法过半数，怎么办？或者，在一个提案投票未完成时，又有一个相同问题的不同提案被另一个城邦提出来，如果两个提案都收集到了过半的投票，那到底应该执行哪一个决议呢？
话音一落，众议员纷纷窃窃私语，有的点头表示赞同，有的摇头表示问题好难，有的一言不发，似乎在思索答案。。。
当日，众议员没有商议出一个好办法，于是各回旅店休息。
是日，又议，未果；如此数日，未果。
眼看此次集会预定的时间将截止，还没有商量出好办法，大家都比较着急。这时，雅典议员代表中一个年轻人犹豫着举起了手，然后站起来说道：如果各城邦能保证一定投票，真实投票，而且大家目标是为了尽快达成一致决议，而不是为了实现自己的提案而抬杠的话，我有一个办法。之前那个雅典长者对他投来了赞许和信任的目光，并说：帕克索斯，请讲。
帕克索斯得到了支持，自信地说到：我们可以把投票过程分为两个阶段。第一个阶段，由有提案的城邦 A 写好提案编号和要提案的内容，由信使发送出去，然后等待其他城邦的回复。第一阶段其他城邦不需要投票，所以他们的回复不是支持或者赞成，而是告诉城邦 A 能不能正式向其他城邦发起投票请求，或者现在是不是有针对相同问题的其他提案正在协商。等到城邦 A 收到了过半数城邦的回复，该城邦就可以发起第二阶段的投票了。在第二阶段中，城邦 A 根据收到的回复，如果过半数的其他城邦的回复中都表示可以继续发起投票，而且回复中没有说明有正在协商的其他提案，那城邦 A 就可以向其余城邦写信发送提案投票的请求，如果有半数人支持就可以达成决议，由城邦 A 将决议告知其他城邦执行；或者第一阶段中有城邦回复说要停止提案，因为有其他城邦更紧急地提出了提案，那城邦 A 就不再发起投票请求，以免造成投票混乱，而是等待给那个更紧急的提案投票；又或者第一阶段中有城邦回复表示可以继续发起投票但是他们有的已经同意了另外一个相同问题的其他提案，那么城邦 A 就要放弃自己的提案，将其改成回复中表明的已经被同意了的另一个提案，然后向其余城邦发起投票请求，由于这个时候各城邦收到的投票提案是一样的，所以能很快得到多数同意并形成一致决议。
帕克索斯说完后，整个集市沉默了下来。有的人微蹙眉头，似乎在默默推理和反诘他的方法；有的人则是一脸茫然，表示完全没有听懂。这时底比斯城的一个中年议员问了一个问题： 你的方法中第一阶段是不是为了保证第二阶段只有一个提案值？ 帕克索斯说是的。底比斯城的另一个年轻议员又问道：第一阶段中，如果有城邦回复说他已经接受了另一个提案，那城邦 A 就把自己的提案改成那个提案了，是不是因为那个提案肯定已经有多数城邦不反对或者说同意了。帕克索斯说非常正确。这时，底比斯城的议员们一致表示他们赞成帕克索斯的方法，认为他的办法可以保证各城邦较快达成一致。
随后，由雅典、斯巴达和底比斯等城的议员给其他城邦的议员反复解释后，大家明白了这个方法，并一致决定采用这个方法来协商事务。后来，根据这套协商机制，希腊各城邦共进共退，终于取得了波希战争的最后胜利。虽然后来雅典独自做大，引起斯巴达不满，进而演化成各城邦相互厮杀的局面，但帕克索斯的提案若干年后还是被各城邦的有识之士津津乐道。
《将军》
北纬41°01'，东经28°58'，君士坦丁堡。城外一片萧杀，奥斯曼海军已经兵临金角湾，随时有可能突入帝国首都后方。
君士坦丁十一世焦急地召集部署在金角湾和首都东面临海的将军们，心急地要求他们：务必协同作战，保证防线万无一失。因为帝国战力已经告急，各将军必须组织共同进攻或者共同撤退，单方面的冒进或者后退都会导致防线失守，彻底战败。然而，将军们却各怀心思: 谁能保证步调一致呢，谁知道其中有没有叛徒，万一准备进攻的时候，叛徒将军故意传达撤退命令怎么办？年轻的皇帝看出了大家的心思，心里满是悲怆，尽管帝国仅存孤城，他还是想最后一博，无论如何不能投降。于是他开诚布公地说道: 我知道诸位的顾虑，战事至此，只希望诸公与我奋力保卫新罗马，战场态势变化不定，无法由我来协调，所以需要诸将军即时协调攻守，如果大家担心其中有叛徒或者传令兵被调包，也请大家想出办法来，在可能有叛徒的情况下仍然保证共进共退，只有共进共退，我们才有死守成功的可能。诸将军听完后，头皮发麻，觉得此问题无解，应该先找出叛徒正法为妥。
皇宫内安静得可怕，将军们粗重的呼吸清晰可辨。然而只有皇帝心急如焚，将军们却是平静而放松。时间一点一点流失，皇帝反复追讨办法无果。这时，旁边的主教兰波特说：陛下，我有办法可以让将军们保证进退一致。将军们诧异地将目光集中到兰波特身上：这个长袍秃头的家伙这回居然和皇帝站在了一边。皇帝欣喜地说道：主教大人，请讲。
兰波特清了清嗓子，说道：我们这里有10位将军，虽然我们现在无法弄清谁是叛徒，但我们有办法知道将军中的叛徒个数，而且我有信心，即使有叛徒，也不会超过3位。假如你们在战场上的联络是没有问题的，就是说，传令兵会把命令传到另一位将军那里，无论传令兵有没有被调包。那么当你们收到将军A的传令兵的消息后，先不要相信他传达的命令，而是派出自己的亲兵去问一下其他将军：将军A给他们传的命令是什么？ 如果叛徒不止一个的话，收到其他将军回复后也不要选择相信，因为他们中间可能还有叛徒。假如回复的8个将军分别是将军 1 - 8，为了确认他们回复的是否可相，应该再分别问除了回复的将军外其他将军。比如，如果要确认将军 1 回复的是否可信，要问一下将军 2 - 8，将军 1 给他们传达的是什么命令。确认将军 2 - 8 的回复也采用类似的方法，直到根据叛徒数量确定剩下的将军中可能没有叛徒为止。最后，收集各将军的回复，选择多数的结果作为对应将军的命令，分别确定将军 2 - 8的命令，然后与自己收到的命令一起选一个多数意见执行进攻或者撤退。每个将军都用相同的方法决定最后的执行结果，可以保证大家共进共退。
听完后，各将军一脸茫然，直观感觉要传好多道令。而且他们都知道主教作了一个假设，说最多只有3个叛徒，所以有将军提出来说：万一咱们中的叛徒不止3个，有5个甚至7个怎么办？
兰波特微微一笑，说这个也好办：如果叛徒超过3个人，你们就要对传令的文书签名了，而且除非是两个叛徒共谋篡改签名，正常的签名是很容易被识别的。如果将军A传令，那他签好名后由传令兵向其他 9 个将军传达命令。这9个将军收到 A 的命令后，也不会立即选择相信并执行，而是先把他的传令记下来，并在传令文书上加上自己的签名后，再由传令兵传递给其他 8 位将军；剩下的将军收到传令文书后，检查一下签名，看还没有谁的签名，如果还有人没有签名，就把自己的签名加上去，给他发一份。这样一段时间后，各将军手上都有收到不止一份签过名的传令文书。每个将军把他收到的所有传令文书上的命令都记下来。如果一段时间内没有收到某个将军签名的文书的话，就默认这个将军对应的命令是撤退。这个方法可以保证，一段时间当将军们不再收到新的传令后，所有将军记下来的命令集合是一致的，将军们最后都通过选择命令集合中最多数的命令执行就可以实现共进共退了。
将军们已经昏昏欲睡，皇帝则满脸狐疑地问道：主教大人，你确定在我们知道叛徒人数的情况下，这两种方法都能让将军们行动一致？
兰波特用力地点了点头，给皇帝信心。皇帝将信将疑：你的办法要求反复传令，我担心战场上不好实施啊。兰波特默然，但建议皇帝事情紧急，没有更好的办法了。皇帝于是要求将军们按主教大人的办法执行，等叛徒人数确定后，再选择执行方案一或者方案二。
不久，奥斯曼海陆军并进。主教确认，有3个将军是叛徒，拜占庭的将军们选择方案一进行协商，但兰波特的方法实在太过繁复，传令兵还没有跑完，奥斯曼海军已经突入金角湾，切断了西边的补给和救援通道。没过多久，君士坦丁堡被攻陷。
好了，故事已经讲完了。有同学可能会问：这些故事与Bitcoin网络的共识有什么关系？关系蛮大的。相信不少同学对上面的故事已经会心一笑了，我只不过把几个有名的故事重新讲了一遍。第一个故事便是博弈中的囚徒困境问题，它是说在单次或者有限次博弈中，理性个人总是选择对自己有利的方案，而不顾全局最优选择。第二个故事是Lamport提出的Paxos算法，讨论的是无欺骗的故障容错算法。第三个故事讲的是拜占庭将军问题，讲的是分布式系统中有恶意节点存在时如何达到一致的问题，解决的理论办法是Lamport提出的口头协议和书面协议算法。Bitcoin网络是一个分布式系统，也需要解决有恶意节点和有故障节点时如何让各节点达成一致的问题。
从上面的故事中可以看到，Lamport提出的理论算法复杂度比较高，虽然已经有算法提出来，实现了多项式级别复杂度，但针对大规模网络，节点数量很多，从达成一致的时间要求和成本要求来看，无法高效实用。上述算法要达到的是确定共识状态，即最后能确定达到一致状态。大家已经知道，Bitcoin网络采用的是PoW共识算法，它是一种概率共识算法，即最后全网是以一定概率逐步达成共识的。
PoW算法不再赘述，这里只以笔者有限的理解，来简要说明一下Bitcoin网络中的共识机制与上述三个故事的关系。PoW算法中，要求节点必须完成工作量证明后，才能向其他节点广播被“挖”出来的区块，这实际上是变相完成了议员故事中讲的第一阶段，即提高了提案的成本，让一段时间内只有一个提案供网络投票。另一方面，为了防止区块或其中的交易被篡改，区块中的交易会通过Hash形成Markle树，区块头中包含了上一区块的Hash然后再计算自己的Hash，会使得中间节点篡改会很快被发现，从而无法在网络中传播被修改的提案。然而，如何防止“矿工”自己篡改区块呢，“矿工”可以有意排除一些交易或者虚构工作量证明？这个问题就是通过其他节点收到该区块后的决策来解决的。具体来说，其他节点收到这个被篡改的区块后，会验证工作量证明是否正确，一方面是区块目标难度是不是预定的值，另一方面就是给出的随机值能不能满足区块头Hash小于目标难度。对于有意排除一些交易或者虚构工作量证明的矿工，其他节点无法在验证工作量证明环节识别，因而将这一“假区块”根据区块高度暂时添加到自己的区块链上，但他们会通过类似将军故事中第二个方案中的其他将军那样，等其他节点或者矿工发过来的区块。一段时间后，相同高度的正确的区块会被其他矿工“挖”出来并传播出来，节点于是有了相同高度的真假区块在自己的区块链上，也就是发生了分叉，这时节点会选择工作量最大或者最长的区块为正确的区块，对应的分叉为主链，另一个分叉和其上的区块被丢弃。如果要伪造工作量证明，只可能往工作难度小的方向篡改，因为能更快地“挖”出区块，所以工作量最大的肯定是正常的区块。
那么，这里还有一个可能性: 如果其他节点不是选择工作量最大或者最长链为主链，而是与恶意“矿工”合作，选择虚假区块，那不就可以了么。这里节点就面临囚徒困境了，因为被系统承认的区块会给相应的矿工奖励若干比特币，而没被系统接受的“矿工”所付出的算力及背后对应的电力、设备折旧带来的经济成本就成为了沉没成本，由“矿工”自己承担。那么，就会有不少“矿工”开始琢磨，要不要和恶意“矿工”合伙作假了，因为作假的成本确实有点高，除非拉拢了超过全网1/3甚于1/2的节点，才有可能得成。想一想，还是老老实实“挖”吧。。。
