作者：BlockPunk 社区：果壳宇宙（ID:DfinityFun） 前言 4000年前的东方大陆，萨满缓慢的从篝火的灰烬中扒出龟甲，龟甲上随机的裂纹会决定部落下一次狩猎的时机；3000年前的地中海，尊贵的雅典神官主持着抽签仪式，他们要随机选出五百位优秀公民，来参与城邦政务的讨论；2000年前的中东，行商围坐在一张赌桌旁，紧张的注视着桌面上转动的四面骰子，它的最终结果会决定一大笔财富的归属。 在上千年的人类历史里，我们一直不断地探寻着可靠的随机数，并将随机数用在生活的各个方面，民主与共和的抽签制度，战争时期的军情传递、生产上的模型计算，以及赌博娱乐时的可信参照。 对可靠随机数的追求，更是人类对公平的追求，对随机数的承认，可以说是人类最早的关于公正的共识。而在2000多年后的现代，人类发明了计算机，开始了崭新的数字纪元，随机数成为了整个虚拟世界的基础。 真随机数 我们祖先朴实的技术而言，人类创造了很多生成随机数的方法，但这些随机数的随机强度与不可预测程度，并不比烧龟甲来的更高。 这里就要讲到真随机数与伪随机数了。古代的人类观察物理世界时，会发现到处都存在着随机的波动，这种随机性在他们看来，是上天的旨意，你完全没法预测未来会怎么样。真正的随机性，只存在于物理世界，大气噪声、宇宙背景辐射、放射物的衰变期、量子塌缩现象，通过观测这些现象，得到的随机数是完全无规律可循的。 《百万乱数表》图片来自网络 上世纪40年代，兰德公司利用模拟电路制成的电脉冲发生器生成了100万个随机数，并将其出版为《百万乱数表》，一直销售到今天。现在看来这似乎是一个异想天开的行为艺术，但在当时却是非常重大的突破。 熔岩灯 有趣的是，在互联网时代的今天，仍有人在使用这种方法。一家名叫Cloudflare的云服务商，通过图像识别实时处理熔岩灯中蜡的形状，计算量化来获取真随机数，从而对数据进行高强度的加密。这听起来好像有些愚蠢，但其实它的随机强度，却远强于现在主流的随机数。 假随机数 我们可以从物理现象中得到神秘而无穷的随机性，但有些现象并不能精确量化。但同时我们需要巨量的随机数来加密数据、训练模型、公平仲裁，仅依靠自然界的随机数是远远不够的。 这也是计算机之父，冯诺依曼思考过的。在1946年， 冯诺依曼参与了美军氢弹的设计，他在一台名为ENIAC的计算机上，模拟计算核聚变的过程。而这个模型的训练，需要对随机数进行快速的存取，但ENIAC的内存不够大，无法保存长真随机数，因此冯诺依曼设计了一个算法，来模拟一个随机性的混乱状态。 ENIAC计算机 | 图片来自网络 这个算法是这样的：首先获得一个很短的随机值，比如操作时刻的毫秒数，作为这个算法的“种子”，然后将“种子”平方，输出平方结果的中间部分数字，再作为“种子”重复上述操作。重复足够的次数后，就获得了一个“随机数”。 这被称为平方取中法，这也只是无数假随机数算法中的一种，这个算法输出的序列，只取决于最初种子的随机性。由于机器的确定性，同样的种子，就可以计算出同样的随机数。 种子的位数决定了随机数的随机度，当你设定一个两位的种子生成一个10位随机数，在函数产生重复循环之前，最多只能得到100个可用的随机数；而在自然界中，10位随机数应该存在一百亿种可能。这两者之间巨大的数量级差别，就是随机数真与假的区别。 只要你使用基于“种子”的假随机数，必然会出现重复循环的过程，也就是说，只要知晓了你的随机数算法，另一台计算机迟早能暴力尝试出相同的随机数。这就是区块链钱包的密钥生成随机函数被攻破后，暴力盗取密钥的手段。 假随机数存在规律的周期，点集中表现为脉络 图片来自网络 当然这种随机数是足够使用的，我们必须引入计算机科学中非常重要的一个概念，时间边界，也就是在多长的时间里，这个随机数是安全不重复的。和我们使用密码车锁一样，我们知道正确的密码必在一万种的组合方式之中，但一个个尝试需要花费好几天时间，这个时间边界内都算是安全，假随机数也是如此。 我们闭眼敲键盘的随机字符串，其实也有规律可循，这就是QWER的键盘布局，通过分析后破解随机数的可能性就会很大 这依然无法满足区块链的使用要求，因为我们需要一个能在固定时间内，分布式的获取随机数的方法，而不能依赖于任何一个中心主体。 区块链为什么需要随机数 在传统互联网中，随机数是作为密码学与隐私安全的基础，通过共享随机的密钥，两个节点间就可以进行加密的私人通讯，而在区块链中，就是使用私钥密钥传输财产；同时随机数还广泛应用于有限带宽下的多节点通讯，可以利用随机数来决定数据发送的合理顺序，来协调多方节点，在区块链上，就是利用基于随机数的共识算法，协调交易确认者，保证一段时间内大家只对部分节点的消息进行反馈更新，从而在网络消息数有限的情况下获得一致。 而在区块链与加密的世界里，随机数上再次投射出了人类对公平的追求。我们的世界是随机的，过去无法更改，但未来不可预测，这是对生命最大的公平。区块链上一样，我们通过随机数的可信，脱离人性的干扰，获得链上的公正性，保证整个系统的去中心化程度与可信性。特别是权益证明PoS越来越火的现在，我们比以往任何时候都需要一个安全、稳定、可信的随机数，来保证密钥对的生成、链上数据的加密、出块权力的裁定、智能合约的运行。 总结 公平的决定出块权力，维持一致性共识。部分PoW与PoS机制下，依靠随机数选定出块者或者出块组的，包括DPoS机制下的循环出块的顺序，也是依靠随机数决定。 私钥的生成。目前私钥只要由各钱包自定随机数方法生成，存在较大安全隐患。 链上应用的随机数源。保证博彩、游戏、抽奖、分发、调查等应用的公平公正，此类容易被黑客攻击。 数据加密。链上数据因为是公开审查的，需要强度较高的加密，通过足够强的随机数确保链上数据的隐私与安全。 链上随机数的难点 虽然区块链还是基于过去的互联网技术，但是在随机数生成部分却有着非常大区别。 传统的随机数产生方式是中心化的，产出的随机数，与特定机器的状态值、物理状态相关，而同一个随机数算法，在不同的节点上得到的随机数是不同的，并且也没法针对每一个随机数进行验证，因此传统的方式无法产生一致性的随机性，这和区块链不兼容。 因此区块链上的随机数，需要重头开始设计机制，从而来获得满足分布式特点的结果。因此到目前为止，没有真正意义上完美的方案，区块链上的真随机数是缺失的，连假随机数都很难获得。 链上随机数的原则 1.不可预测 因为随机数决定着整个协议层包括所有以上层级的公正性，如果这个随机数是能提前预见的，那么就可以伺机发动攻击。当然这个不可预测性是存在时间边界的，一般以区块链时间为边界，通过控制计算难度，或设置等待，来增加预测的难度。简而言之，有两种方案： 保证随机数从区块时间上看是串行的（VRF/VDF） 保证随机数产生的难度，并按情况调节难度（哈希碰撞） 2.不可干扰 随机数决定着区块（非拜占庭容错系统中）的共识确认，因此如果能干扰到随机数的发生，无需掌握超越上限的节点/算力，就可以间接的控制区块链未来的走向，虽然干扰可能很微小，但多次干扰积累下来就会出现较严重的问题（“放大攻击”）。有两种解决方案： 保证随机数生成是非交互的（阀值签名方案），或完全根据节点本身状态计算（哈希碰撞） 设置随机数生成时延，需要等待长时间的复杂计算才能得出随机数，让干扰者无法预估自己施加的影响 3.可验证 应该详细表述为，可被简单验证，这表示随机数必须能够被任何节点快速进行验证其合法性，这样分布式的节点才能通过检验随机数，确认某一节点的出块资格，从而达成一致性。如果验证效率很低，需要很长时间，那么节点间共识的达成就会遥遥无期，区块链无法使用。 不符合上述原则的一些解决方案 为了解决区块链上的随机数难点，自发的产生了许多解决方案，以下简述以下不符合上述三个原则的方案，虽然他们各自都有自洽的逻辑与一定的安全性，但在现阶段还是存在问题的，在对安全需求不是那么高的地方仍可以使用。这不不针对某个项目，而是指出相似范式的问题 1.使用链下真随机数 不在链上计算随机数，而是使用从物理现象中获得的真随机数，比如大气噪声、电子脉冲，以及依赖包含热噪声电路的芯片组。但是对区块链来说，链下部分是不可见的，默认就是不可信的，链下获得随机数一定需要一个第三方上传至链上，这不仅违背了区块链的去中心化精神，完全无法验证，且存在篡改与提前预知的风险。就算使用预言机来去中心化的获取链下的真随机数，但仍存在物理上的人为干扰。因此这种方案非常不可取。 2.将当前块的数据作为随机源 很多的链上博彩类Dapp，都习惯直接引用最近区块的哈希根值等作为合约的随机种子，再来产生随机数。虽说简介的借助了链上算力的保证，如此产生的随机数看似足够有公信力，但需要考虑到多维度的安全性。首先，区块上的数据是透明的，所有节点都能获取，攻击者同样能用来攻击合约，唯一的障碍就是不开源的随机数算法。第二点，出块人获得出块资格后，可以尝试变更打包交易顺序、尝试打包不同交易，来产生最有利于他的哈希根值，从而扩大自己中奖的概率，这对其他参与者是不公平的。 3.借助分布式组织产生随机数 因为随机数的强度来源于种子的随机性，因此就有人提出由一个分布式组织来产生足够随机的种子，依赖与本地节点的特殊状态或控制者的“自由意志”，向链上上传秘密与验证，以特殊算法组合种子，再在链上产生随机数。先不论链下的合谋可能（有经济设计制约），这种方案还是存在“最后参与者攻击”的可能，也就是最后一个上传秘密的参与者，可以知道此前的全部秘密，他可以控制自己的秘密来干扰最终随机数的产生。且在掌握了函数算法后，可以预测影响的规律，如此可以多次施加干扰，进而不断扩大自己的影响，这就是“放大攻击”。 三类方案 虽然区块链上的随机数并不完美，但随这越来越多的项目认识到了随机数对效率和冗余度的巨大优化，随机数的可信与高效显得越来越重要。因此这里总结了三类相对成熟方案，并指出了相关项目与方案优缺点。 哈希碰撞 在PoW系统中，矿工的客户端有一个基于本节点状态的随机数发生器，可以输出随机数序列，然后再计算其哈希值，一但生成的哈希值在规定的大小范围内，就是为获得了出块资格，其他节点获取这个随机数值，计算一次哈希值即可进行验证，因此它的验证是十分简洁的。 因此这个随机数得经历数百兆亿次随机数发生后，才有机会获得一个符合要求的随机数，因此它的随机程度非常的高；同时由于得出随机数消耗的资源非常大，想要提前几个区块预测这个随机数几乎是不可能的；由于随机数完全根据节点本身状态输出随机数，因此这个随机数不会其他攻击者干扰；即时的难度调整（调整哈希值的大小范围），在安全时间边界内不会出现被攻破的情况。 PoW的共识特点，使得其天然具备随机性的（randomness for free）。 优点： 随机性最强，安全性号，非常适合驱动共识层； 产生随机数时不需要使用网络带宽。 缺点： 计算冗余度，计算消耗大，资源浪费； 难以在应用层使用； 不具备唯一性，可以同时存在多个满足要求的随机数，可能导致区块分叉； 无法抵抗并行加速破解，计算机持有多的人可以连续预测多个随机数。 可验证随机函数（VRF） VRF（Verifiable Random Function）算法于1999年由莫卡利教授提出，由于其较好的安全性与效率，被越来越多区块链项目拿来优化共识过程，让共识的随机数部分占用计算资源变少，让资源更多地被交易的确认与合约的运行所占用。 集合上图简述生成步骤： 0.生成随机数签名专用公私钥对； 1.获得一个足够随机的种子，可以直接使用上一轮结果，与区块高度、时间的变量等进行组合； 2.用随机数私钥对之进行签名（共同参与随机数生成），或是先签名再组合； 3.对签名后的值做哈希摘要，得出最新的随机数； 4.检查随机数是否在合法范围中，判断是否抽签成功进入出块组（部分项目不需要这个过程） 5.根据公钥与轮次等输入，计算证明，接受随机数后验证者使用函数进行验证。 因此这样产生的随机数，节点可以轻松验证其是否合乎算法，"Verifiable"就这样做到了；而经过足够复杂的算法，加上哈希摘要过程，获得足够随机分布的结果，“Random”得到了保证。 VRF主要结合PoS机制一起使用，来进行出块人（群）的随机选择，个别项目中直接决定区块的一致性选择。这个随机数的生成过程可以完全在一个节点的链下运行，同时也可以整个运行在链上。 需要注意的是签名随机的部分，VRF的这个签名随机算法应当具备唯一性，也就是说用同一把密钥，对同一个数据签名随机多次，只有唯一的一个随机数能被公钥验证，这就能防止产生随机数时，多次运行签名随机部分，来获得最有利于自己的随机数。 优点： 算力要求低，产出随机数效率高； 产生唯一性、确定性的随机数，不易出现分叉； 验证可滞后于随机数产生，适合进行秘密选举； 可设置为（输入为上轮结果）抗并行加速破解，矿机多者也无法连续预测随机数。 缺点： 验证步骤较多，秘密选举下需要多次验证； 随机数分布均匀性不好，因为是根据特点密钥计算的； 带宽占用高，延时长，是为让秘密选举的节点互相确认，BLS项目问题不大； Algorand 每一个节点都获取前一轮确认区块上的随机种子，集合轮次时间等，在链下单独运行VRF函数，然后对结果进行哈希摘要，节点将结果与网络中哈希值范围进行比较（比较类似于PoW哈希比对），范围内的成员便有资格参与验证与出块。…

分布式系统 万法皆空，因果不空。 随着摩尔定律碰到瓶颈，越来越多的系统要依靠分布式集群架构来实现海量数据处理和可扩展计算能力。 区块链首先是一个分布式系统。 中央式结构改成分布式系统，碰到的第一个问题就是一致性的保障。 很显然，如果一个分布式集群无法保证处理结果一致的话，那任何建立于其上的业务系统都无法正常工作。 本文将介绍分布式系统中一些核心问题的来源以及相关的工作。 一致性问题 在分布式系统中，一致性(Consistency，早期也叫 Agreement)是指对于系统中的多个服务节点，给定一系列操作，在协议（往往通过某种共识算法）保障下，试图使得它们对处理结果达成某种程度的一致。 如果分布式系统能实现“一致”，对外就可以呈现为一个功能正常的，且性能和稳定性都要好很多的“虚处理节点”。 举个例子，某影视公司旗下有西单和中关村的两个电影院，都出售某电影票，票一共就一万张。那么，顾客到达某个电影院买票的时候，售票员该怎么决策是否该卖这张票，才能避免超售呢？当电影院个数更多的时候呢？ 这个问题在人类世界中，看起来似乎没那么难，你看，英国人不是刚靠 投票 达成了“某种一致”吗？ 注意：一致性并不代表结果正确与否，而是系统对外呈现的状态一致与否，例如，所有节点都达成失败状态也是一种一致。 挑战 在实际的计算机集群系统（看似强大的计算机系统，很多地方都比人类世界要脆弱的多）中，存在如下的问题： 节点之间的网络通讯是不可靠的，包括任意延迟和内容故障； 节点的处理可能是错误的，甚至节点自身随时可能宕机； 同步调用会让系统变得不具备可扩展性。 要解决这些挑战，愿意动脑筋的读者可能会很快想出一些不错的思路。 为了简化理解，仍然以两个电影院一起卖票的例子。可能有如下的解决思路： 每次要卖一张票前打电话给另外一家电影院，确认下当前票数并没超售； 两家电影院提前约好，奇数小时内一家可以卖票，偶数小时内另外一家可以卖； 成立一个第三方的存票机构，票都放到他那里，每次卖票找他询问； 更多…… 这些思路大致都是可行的。实际上，这些方法背后的思想，将可能引发不一致的并行操作进行串行化，就是现在计算机系统里处理分布式一致性问题的基础思路和唯一秘诀。只是因为计算机系统比较傻，需要考虑得更全面一些；而人们又希望计算机系统能工作的更快更稳定，所以算法需要设计得再精巧一些。 要求 规范的说，理想的分布式系统一致性应该满足： 可终止性（Termination）：一致的结果在有限时间内能完成； 共识性（Consensus）：不同节点最终完成决策的结果应该相同； 合法性（Validity）：决策的结果必须是其它进程提出的提案。 第一点很容易理解，这是计算机系统可以被使用的前提。需要注意，在现实生活中这点并不是总能得到保障的，例如取款机有时候会是“服务中断”状态，电话有时候是“无法连通”的。 第二点看似容易，但是隐藏了一些潜在信息。算法考虑的是任意的情形，凡事一旦推广到任意情形，就往往有一些惊人的结果。例如现在就剩一张票了，中关村和西单的电影院也分别刚确认过这张票的存在，然后两个电影院同时来了一个顾客要买票，从各自“观察”看来，自己的顾客都是第一个到的……怎么能达成结果的共识呢？记住我们的唯一秘诀：核心在于需要把两件事情进行排序，而且这个顺序还得是大家都认可的。 第三点看似绕口，但是其实比较容易理解，即达成的结果必须是节点执行操作的结果。仍以卖票为例，如果两个影院各自卖出去一千张，那么达成的结果就是还剩八千张，决不能认为票售光了。 带约束的一致性 做过分布式系统的读者应该能意识到，绝对理想的强一致性（Strong Consistency）代价很大。除非不发生任何故障，所有节点之间的通信无需任何时间，这个时候其实就等价于一台机器了。实际上，越强的一致性要求往往意味着越弱的性能。 一般的，强一致性（Strong Consistency）主要包括下面两类： 顺序一致性（Sequential Consistency）：Leslie Lamport 1979 年经典论文《How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs》中提出，是一种比较强的约束，保证所有进程看到的 全局执行顺序（total order）一致，并且每个进程看自身的执行（local order）跟实际发生顺序一致。例如，某进程先执行 A，后执行 B，则实际得到的全局结果中就应该为 A 在 B 前面，而不能反过来。同时所有其它进程在全局上也应该看到这个顺序。顺序一致性实际上限制了各进程内指令的偏序关系，但不在进程间按照物理时间进行全局排序。 线性一致性（Linearizability Consistency）：Maurice P. Herlihy 与 Jeannette M. Wing 在 1990 年经典论文《Linearizability: A Correctness Condition for Concurrent Objects》中共同提出，在顺序一致性前提下加强了进程间的操作排序，形成唯一的全局顺序（系统等价于是顺序执行，所有进程看到的所有操作的序列顺序都一致，并且跟实际发生顺序一致），是很强的原子性保证。但是比较难实现，目前基本上要么依赖于全局的时钟或锁，要么通过一些复杂算法实现，性能往往不高。 目前，高精度的石英钟的漂移率为，人类目前最准确的原子震荡时钟的漂移率为。Google 曾在其分布式数据库 Spanner 中采用基于原子时钟和 GPS 的“TrueTime”方案，能够将不同数据中心的时间偏差控制在 10ms 以内。方案简单粗暴而有效，但存在成本较高的问题。 强一致的系统往往比较难实现。很多时候，人们发现实际需求并没有那么强，可以适当放宽一致性要求，降低系统实现的难度。例如在一定约束下实现所谓最终一致性（Eventual Consistency），即总会存在一个时刻（而不是立刻），系统达到一致的状态，这对于大部分的 Web 系统来说已经足够了。这一类弱化的一致性，被笼统称为弱一致性（Weak Consistency）。 莫非分布式领域也有一个测不准原理？这个世界为何会有这么多的约束呢？ 共识算法 实际上，要保障系统满足不同程度的一致性，往往需要通过共识算法来达成。 共识算法解决的是对某个提案（Proposal），大家达成一致意见的过程。提案的含义在分布式系统中十分宽泛，如多个事件发生的顺序、某个键对应的值、谁是领导……等等，可以认为任何需要达成一致的信息都是一个提案。 注：实践中，一致性的结果往往还需要客户端的特殊支持，典型地通过访问足够多个服务节点来验证确保获取共识后结果。…

区块链的基础是P2P分布式网络、加密算法和共识机制。 在这些基础技术中，共识机制是至关重要的。可以说共识机制是区块链技术的核心，共识机制对于一个区块链系统来说就是它的灵魂。 共识机制很大程度上决定了整个区块链系统节点间的相互信任程度，也决定了其他使用者对于区块链上数据的信任程度。 区块链与普通分布式系统，尤其是分布式数据库最大的区别就是“去中心化”，而正是共识机制决定了一个区块链系统“去中心化”的程度。 通常，我们把区块链分为两大类：一种是公有链，一种是非公有链。 这两种区块链的核心区别在于：参与共识的节点是否是受控的。 对于公有链来说，互联网上的任何计算机都可以通过运行相应的区块链程序，参与整个区块链的共识； 而对于非公有链来说，通常需要获得之前区块链节点中大部分节点的同意，或者通过其他某种机制，获得参与共识的权力。 目前主要几类共识算法如下：PoW、PoS、DPos、Ripple Consensus、PBFT、dBFT、POOL验证池 1.PoW（工作量证明） 通过与或运算，计算出一个满足规则的随机数，即获得本次记账权，发出本轮需要记录的数据，全网其它节点验证后一起存储； 优点：易实现，节点间无需交换额外的信息即可达成共识，破坏系统需要投入极大的成本。 缺点：浪费能源，区块的确认时间难以缩短；共识达成的周期较长，不适合商业应用 2.PoS（权益证明） PoW的一种升级共识机制，本质上是采用权益证明来代替PoW的算力证明，记账权由最高权益的节点获得，而不是最高算力的节点。根据每个节点所占代币的比例和时间；等比例的降低挖矿难度，从而加快找随机数的速度。 优点：解决了PoW 消耗算力的问题，在一定程度上缩短了共识达成的时间 缺点：拥有权益 的参与者未必希望参与记账，还是需要挖矿。 3.DPoS（股份授权证明机制） 类似于董事会投票，持币者投出一定数量的节点，代理他们进行验证和记账。 优点：大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。 缺点：整个共识机制还是依赖于代币，很多商业应用是不需要代币存在的。 4.Ripple Consensus（瑞波共识算法） 使一组节点能够基于特殊节点列表达成共识。初始特殊节点列表就像一个俱乐部，要接纳一个新成员，必须由51%的该俱乐部会员投票通过。共识遵循这核心成员的51%权力，外部人员则没有影响力。由于该俱乐部由“中心化”开始，它将一直是“中心化的”，而如果它开始腐化，股东们什么也做不了。 5.PBFT：Practical Byzantine Fault Tolerance（实用拜占庭容错算法） 在保证活性和安全性（liveness & safety）的前提下提供了(n-1)/3的容错性。 在分布式计算上，不同的计算机透过讯息交换，尝试达成共识；但有时候，系统上协调计算机（Coordinator / Commander）或成员计算机 （Member /Lieutanent）可能因系统错误并交换错的讯息，导致影响最终的系统一致性。 拜占庭将军问题就根据错误计算机的数量，寻找可能的解决办法，这无法找到一个绝对的答案，但只可以用来验证一个机制的有效程度。 而拜占庭问题的可能解决方法为： 在 N ≥ 3F + 1 的情况下一致性是可能解决。其中，N为计算机总数，F为有问题计算机总数。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。 优点： 1）系统运转可以脱离币的存在，pbft算法共识各节点由业务的参与方或者监管方组成，安全性与稳定性由业务相关方保证。 2）共识的时延大约在2~5秒钟，基本达到商用实时处理的要求。 3）共识效率高，可满足高频交易量的需求。 缺点： 1)当有1/3或以上记账人停止工作后，系统将无法提供服务； 2)当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据； 6.dBFT： delegated BFT 授权拜占庭容错算法 小蚁（NEO）采用的dBFT机制，是由权益来选出记账人，然后记账人之间通过拜占庭容错算法来达成共识。 此算法在PBFT基础上进行了以下改进： 将C/S架构的请求响应模式，改进为适合P2P网络的对等节点模式； 将静态的共识参与节点改进为可动态进入、退出的动态共识参与节点； 为共识参与节点的产生设计了一套基于持有权益比例的投票机制，通过投票决定共识参与节点（记账节点）； 在区块链中引入数字证书，解决了投票中对记账节点真实身份的认证问题。 优点： 1)专业化的记账人； 2)可以容忍任何类型的错误； 3)记账由多人协同完成，每一个区块都有最终性，不会分叉； 4)算法的可靠性有严格的数学证明； 缺点： 1)当有1/3或以上记账人停止工作后，系统将无法提供服务； 2)当有1/3或以上记账人联合作恶，且其它所有的记账人被恰好分割为两个网络孤岛时，恶意记账人可以使系统出现分叉，但是会留下密码学证据； 以上总结来说，dBFT机制最核心的一点，就是最大限度地确保系统的最终性，使区块链能够适用于真正的金融应用场景。 7.POOL验证池 基于传统的分布式一致性技术，加上数据验证机制。 优点：不需要代币也可以工作，在成熟的分布式一致性算法（Pasox、Raft）基础上，实现秒级共识验证。 缺点：去中心化程度不如bictoin；更适合多方参与的多中心商业模式。   Source: bitcointalk.org

区块链的根本属性是去中心化，而去中心化的依托是共识机制。 在了解共识机制之前，先来看两个古老的引入问题：类两军问题、拜占庭将军问题。 类两军问题： 古代有两个相距很远的军队要传递信息， 蓝军派遣一个信使去跟红军说：有本事把意大利炮拿过来！ 红军收到后回复蓝军说：收到指令。 蓝军要给出确认答复：知道你收到指令了！ 红军继续给出答复：知道你知道我知道指令了！ …. 拜占庭将军问题： 拜占庭罗马帝国在军事行动中，采取将军投票策略来决定进攻还是撤退，即如果多数人决定进攻，就整体确定进攻策略。但是军队中如果有奸细（将军可能反水、传令官可能误传），如何保证最后投票真实反映忠诚将军的决策？ 拜占庭帝国周围有10个小国，它们饱受拜占庭欺压，却只有同一时间有6个以上国家进攻才有可能打败拜占庭帝国，非则一定战败。 难点在于：古时候军队之间的通信完全依赖于人，如果军队中有奸细，无论是将军反水还是传令官误传，都会是另外9个国家收到假消息，从而造成作战失败。如果你是国王，该如何判断一定会有另外5个以上国家与你并肩作战？毕竟一不小心，就亡国了。 由于类似于以上这样的问题存在，共识的必要性浮现出来。 九种共识机制比较 区块链上的共识机制有多种，但任何一种都不是完美无缺，或者说适用于所有应用场景的。 1. 工作量证明(POW) 工作量证明（Proof of Work，简称PoW）通常只能从结果证明，因为监测工作过程通常是繁琐且低效的。 比特币在区块的生成过程种使用了PoW机制，一个符合要求的区块哈希值由N个前导零构成，零的个数取决于网络的难度值。要得到合理的区块哈希值需要经过大量的尝试计算，计算时间取决于机器的哈希运算速度。当某个节点提供出一个合理的区块哈希值，说明该节点确实经过了大量的尝试计算，但是并不能得出计算次数，因为寻找合理的哈希值是一个概率事件。当节点拥有占全网n%的算力时，该节点既有n%的概率找到区块哈希值。 PoW依赖机器进行数学运算来获取记账权，资源消耗大、共识机制高、可监管性弱，同时每次达成共识需要全网共同参与运算，性能效率比较低，容错性方便允许全网50%节点出错。 PoW的优点：完全去中心化，节点自由进出。 PoW的缺点：目前比特币已经吸引全球大部分的算力，其他再使用PoW共识机制的区块链应用很难获得相同的算力来保障自身安全；挖矿造成大量的资源浪费；共识达成的周期较长。 使用PoW的项目有：比特币、以太坊的前三个阶段（Frontier前沿、Homestead家园、Metropolis大都会）。以太坊的第四个阶段 Serenity宁静 将采用权益证明机制（POS）。 2. 权益证明（P0S） 权益证明（Proof of Stake，简称PoS）由Quantum Mechanic 2011年在比特币论坛讲座上首先提出，后经Peercoin（点点币）和NXT（未来币）以不同思路实现。 PoS的主要理念是节点记账权的获得难度与节点持有的权益成反比，相比PoW，其在一定程度上减少了数学运算带来的资源消耗，性能也得到了相应的提升，但依然是基于哈希运算，竞争获取记账权的方式，可监管性弱。该共识机制的容错性和PoW相同。它是PoW的一种升级，根据每个节点所占代币的比例和时间，等比例地降低挖矿难度，从而加快找到随机数的速度。 在PoW中，一个用户可能拿1000美元来购买计算机，并加入网络来挖矿以此产生新区块，从而得到奖励。而在PoS中，用户可以拿1000美元购买等价的代币，并把这些代币当作押金放入PoS机制中，这样用户就有机会产生新区块而得到奖励。 总体而言，这个系统中存在一个持币人的集合，他们把手中的代币放入PoS机制中，这样他们就变成验证者。比如对区块链最前面的一个区块而言，PoS算法在验证者中随机选择一个（选择验证者的权重依据他们投入的代币量，比如一个投入押金为1W代币的验证者被选择的概率是一个投入1K代币验证者的10倍），给他权利产生下一个区块。如果在一定时间内，这个验证者没有产生一个区块，则选出第二个验证者代替产生新区块。与PoW一样，PoS以最长的链为准。 随着规模经济（指扩大生产规模引起经济效益增加的现象）的消失，中心化所带来的风险减小了。价值1000万美元的代币带来的回报不多不少，是价值100万美元代币的10倍，不会有人因为负担得起大规模生产工具而得不到成比例的额外回报。 PoS的优点：在一定程度上缩短了共识达成的时间；不再需要大量消耗能源去挖矿。 PoS的缺点：还是需要挖矿，本质上没有解决商业应用的痛点；所有的确认都只是一个概率上的表达，而不是一个确定性的事情，理论上有可能存在其他攻击影响，例如以太坊的DAO攻击事件造成以太坊硬分叉，而ETC随之出现，事实上证明了此次硬分叉的失败。 3. 股份授权证明（DPOS） BitShares（比特股）社区首先提出了股份授权证明（简称DPoS）机制，它与PoS的主要区别在于节点选举若干代理人，由代理人验证和记账，但其合规监管、性能、资源消耗和容错性与PoS相似。类似于董事会投票，持币者投出一定数量的节点，进行代理验证和记账。 DPoS的工作原理如下：每个股东按其持股比例拥有相应的影响力，51%股东投票的结果将是不可逆且有约束力的，其挑战是通过及时而高效的方法达到“51%批准”； 为了达到这个目标，每个股东可以将其投票授予一名代表。获票数最多的前100位代表按既定时间表轮流产生区块。每位代表分配到一个时间段来生产区块。 所有的代表将收到等同于一个平均水平的区块所含交易费的10%作为报酬。如果一个平均水平的区块用100股作为交易费，一位代表将获得一股作为报酬。 网络延迟有可能使某些代表没能及时广播他们的区块，而这将导致区块链分叉。然而，这不太可能发生，因为制造该区块的代表可以与制造该区块前后的区块的代表建立直接连接。建立这种与你之后的代表（也许也包括其后的那名代表）的直接连接是为了确保你能得到报酬。 DPoS的投票模式可以每30秒产生一个新区块，并且在正常的网络条件下，区块链分叉的可能性极其小，即使发生也可以在几分钟内得到解决。执行该模式的基本步骤如下： 成为代表。成为一位代表，你必须在网络上注册你的公钥，并获得一个32位的特有标识符。该标识符会被每笔交易数据的“头部”引用。 授权投票。每个钱包有一个参数设置窗口，在该窗口里用户可以选择一位或更多的代表，并将其分级。一经设定，用户所做的每笔交易将把选票从“输入代表”转移至“输出代表”。一般情况下，用户不会创建专门以投票为目的的交易，因为那将耗费他们一笔交易费。但是在紧急情况下，某些用户可能觉得通过支付费用这一更积极的方式来改变他们的投票是值得的。 保持代表忠诚。每个钱包将显示一个状态指示器，让用户知道他们的代表表现如何。如果他们错过了太多的区块，那么系统将会推荐用户更换一位新的代表。如果任何代表被发现签发了一个无效的区块，那么所有标准钱包将在每个钱包进行更多交易前要求选出一位新代表。 抵抗攻击。在抵抗攻击上，前100位代表所获得的权利是相同的，即每位代表都有一项平等的投票权，因此，无法通过获得超过1%的选票而将权利集中到单一代表上。由于只有100位代表，不难想象一个攻击者可以对每位轮到其生产区块的代表依次进行拒绝服务攻击。幸运的是，由于每位代表的标识是其公钥而非IP地址，这种特定攻击的威胁很容易被减轻。这将使确定DDoS（分布式拒绝服务）攻击目标更为困难。而代表之间的潜在连接将使妨碍他们生产区块变得更为困难。 DPoS的优点：大幅缩小参与验证和记账节点的数量，可以达到秒级的共识验证。 DPoS的缺点：整个共识机制还是依赖于代币，而很多商业应用是不需要代币的。 4. 投注共识 投注共识是以太坊下一代的共识机制Casper（鬼马小精灵）引入的一个全新概念，属于PoS。Casper的共识是按区块达成的，而不像PoS那样按链达成。 为了防止验证人在不同的世界中提供不同的投注，我们还有一个简单严格的条款：如果你两次的投注序号一样，或者说你提交了一个无法让Casper依照合约处理的投注，你将失去所有保证金。从这一点我们可以看出，Casper与传统的PoS不同的是，Casper有惩罚机制，这样非法节点通过恶意攻击网络不仅得不到交易费，而且还面临着保证金被没收的风险。 Casper协议下的验证人需要完成出块和投注两个活动。具体如下： 出块是一个独立于其他所有时间而发生的过程，验证人收集交易，当轮到他们的出块时间时，他们就制造一个区块，并签名，然后发送到网络上。投注的过程更为复杂一些，目前Casper默认的验证人策略被设计为模仿传统的拜占庭容错共识：观察其他的验证人如何投注，取33%处的值，向0或1进一步移动。 而客户端确认当前状态的过程是这样的：一开始先下载所有的区块和投注，然后用上面的算法来形成自己的意见，但是不公布意见；它只是简单地按顺序在每个高度进行观察，如果一个区块的概率高于0.5就处理它，否则就跳过它。在处理所有的区块之后，所得到的状态就可以显示为区块链的“当前状态”。客户端还可以给出对于“最终确定”的主观看法：如果高度k之前的每个区块形成的意见高于99.999%或者低于0.001%，那么客户端可以认为前k个区块已经最终确定。 5. 瑞波共识机制（Ripple Consensus） 瑞波共识算法使一组节点能够基于特殊节点列表形成共识。初始特殊节点列表就像一个俱乐部，要接纳一个新成员，必须由该俱乐部51%的会员投票通过。共识遵循这些核心成员的“51%权利”，外部人员则没有影响力。由于该俱乐部由中心化开始，它将一直是中心化的，而如果它开始腐化，股东们什么也做不了。与比特币及Peercoin一样，瑞波系统将股东们与其投票权隔开，因此，它比其他系统更中心化。 6. Pool验证池 基于传统的分布式一致性技术以及数据验证机制，Pool（联营）验证池是目前行业内大范围使用的共识机制。它的优缺点如下： 优点：不需要代币也可以工作，在成熟的分布式一致性算法（Paxos、Raft）的基础上，实现秒级共识验证。 缺点：去中心化程度不如比特币，更适合多方参与的多中心商业模式。 7. 实用拜占庭容错 在分布式计算上，不同的计算机通过信息交换尝试达成共识，但有时候，系统中的协调计算机或者成员计算机可能因系统错误，而交换错误信息，以致影响最终的系统一致性。对于拜占庭将军问题，若根据错误计算机的数量，寻找可能的解决办法，这其实无法找到一个绝对的答案，只可以用来验证一个机制的有效程度。 而拜占庭将军问题的可能解决方法为：在N≥3F+1的情况下，一致性是可能实现的（N为计算机总数，F为有问题的计算机总数）。信息在计算机间互相交换后，各计算机列出所有得到的信息，以大多数的结果作为解决办法。 最早由卡斯特罗和利斯科夫在1999年提出的使用拜占庭容错（PBFT）是第一个得到广泛应用的拜占庭算法。只要系统中有2/3的节点是正常工作的，就可以保证一致性。 使用拜占庭容错算法的总体过程如下：客户端向主节点发送请求调用服务操作，如“<REQUEST,o,t,c>”，这里客户端c请求执行操作o，时间戳t用来保证客户端请求只会执行一次。每个由副本节点发给客户端的消息都包含了当前的视图编号，使得客户端能够追踪视图编号，从而进一步推算出当前主节点的编号。客户端通过点对点消息向它自己认为的主节点发送请求，然后主节点自动将该请求向所有备份节点进行广播。 视图编号是连续编号的整数，主节点由公式p=v mod |R|计算得到，这里v是视图编号，p是副本编号，|R|是副本集合的个数。 副本发给客户单的响应为“<REPLY,v,t,c,i,r>”，v是视图编号，t是时间戳，i是副本的编号，r是请求执行的结果。 主节点通过广播将请求发送给其他副本，然后就开始执行三个阶段的任务。 预准备阶段。主节点分配一个序列号n给收到的请求，然后向所有备份节点群发预准备消息，预准备消息格式为“<<PRE-PREPARE, v, n, d>, m>”，这里v是视图编号，m是客户端发送的请求消息，d是请求消息m的摘要。 准备阶段。如果备份节点i接受了预准备消息，则进入准备阶段。在准备的同时，该节点向所有副本节点发送准备消息“<PREPARE, v, n, d, i>”，并且将预准备消息和准备消息写入自己的消息日志。 确认阶段。当“(m, v, n, i)”条件为真的时候，副本i将“<COMMIT, v, n, D(m), i>”向其他副本节点广播，于是就进入了确认阶段。所有副本都执行请求并将结果发回客户端。客户端需要等待不同副本节点发回相同的结果，作为整个操作的最终结果。…

区块链技术是近几年逐渐变得非常热门的技术，以比特币为首的密码货币其实已经被无数人所知晓，但是却很少有人会去研究它们的底层技术，也就是作为一个分布式网络比特币等加密货币是如何工作的。 无论是 Bitcoin、Ethereum 还是 EOS，作为一个分布式网络，首先需要解决分布式一致性的问题，也就是所有的节点如何对同一个提案或者值达成共识，这一问题在一个所有节点都是可以被信任的分布式集群中都是一个比较难以解决的问题，更不用说在复杂的区块链网络中了。 分布式一致性 在一个分布式系统中，如何保证集群中所有节点中的数据完全相同并且能够对某个提案（Proposal）达成一致是分布式系统正常工作的核心问题，而共识算法就是用来保证分布式系统一致性的方法。 然而分布式系统由于引入了多个节点，所以系统中会出现各种非常复杂的情况；随着节点数量的增加，节点失效、故障或者宕机就变成了一件非常常见的事情，解决分布式系统中的各种边界条件和意外情况也增加了解决分布式一致性问题的难度。 在一个分布式系统中，除了节点的失效是会导致一致性不容易达成的主要原因之外，节点之间的网络通信收到干扰甚至阻断以及分布式系统的运行速度的差异都是解决分布式系统一致性所面临的难题。 CAP 在 1998 年的秋天，加州伯克利大学的教授 Eric Brewer 第一次发布了 CAP 理论，在 1999 年论文 Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services 正式发布，其中总结了 Eric Brewer 提出的 CAP 理论。 这篇论文证明了两个非常有意思的理论，首先是在异步的网络模型中，所有的节点由于没有时钟仅仅能根据接收到的消息作出判断，这时完全不能同时保证一致性、可用性和分区容错性，每一个系统只能在这三种特性中选择两种。 不过这里讨论的一致性其实都是强一致性，也就是所有节点接收到同样的操作时会按照完全相同的顺序执行，被一个节点提交的更新操作会立刻反映在其他通过异步或部分同步网络连接的节点上，如果想要同时满足一致性和分区容错性，在异步的网络中，我们只能中心化存储所有数据，通过其他节点将请求路由给中心节点达到这两个目的。 但是在现实世界中其实并不存在绝对异步的网络环境，如果我们允许每一个节点拥有自己的时钟，这些时钟虽然有着完全不同的时间，但是它们的更新频率是完全相同的，所以我们可以通过时钟得知接收消息的间隔时间，在这种更宽松的前提下，我们能够得到更强大的服务。 然而在部分同步的网络环境中，我们仍然没有办法同时保证一致性、可用性和分区容错性，证明的过程其实非常简单，可以直接阅读 论文 的 4.2 节，然而时钟的出现能够让我们知道当前消息有多久没有得到回应，通过超时时间就能在一定程度上解决信息丢失的问题。 由于网络一定会存在延时，所以没有办法在分布式系统中做到强一致性的同时保证可用性，不过我们可以通过降低对一致性的要求，在一致性和可用性之间做出权衡，而这其实也是设计分布式系统首先需要考虑的问题，由于强一致性的系统会导致系统的可用性降低，仅仅将接受请求的工作交给其他节点对于高并发的服务并不能解决问题，所以在目前主流的分布式系统中都选择最终一致性。 最终一致性允许多个节点的状态出现冲突，但是所有能够沟通的节点都能够在有限的时间内解决冲突，从不一致的状态恢复到一致，这里列出的两个条件比较重要，一是节点直接可以正常通信，二是冲突需要在有限的时间内解决，只有在这两个条件成立时才能达到最终一致性。 拜占庭将军问题 拜占庭将军问题是 Leslie Lamport 在 The Byzantine Generals Problem 论文中提出的分布式领域的容错问题，它是分布式领域中最复杂、最严格的容错模型。 在该模型下，系统不会对集群中的节点做任何的限制，它们可以向其他节点发送随机数据、错误数据，也可以选择不响应其他节点的请求，这些无法预测的行为使得容错这一问题变得更加复杂。 拜占庭将军问题描述了一个如下的场景，有一组将军分别指挥一部分军队，每一个将军都不知道其它将军是否是可靠的，也不知道其他将军传递的信息是否可靠，但是它们需要通过投票选择是否要进攻或者撤退： 在这一节中，黄色代表状态未知，绿色代表进攻，蓝色代表撤退，最后红色代表当前将军的信息不可靠。 在这时，无论将军是否可靠，只要所有的将军达成了统一的方案，选择进攻或者撤退其实就是没有任何问题的： 上述的情况不会对当前的战局有太多的影响，也不会造成损失，但是如果其中的一个将军告诉其中一部分将军选择进攻、另一部分选择撤退，就会出现非常严重的问题了。 由于将军的队伍中出了一个叛徒或者信息在传递的过程中被拦截，会导致一部分将军会选择进攻，剩下的一部分会选择撤退，它们都认为自己的选择是大多数人的选择，这时就出现了严重的不一致问题。 拜占庭将军问题是对分布式系统容错的最高要求，然而这不是日常工作中使用的大多数分布式系统中会面对的问题，我们遇到更多的还是节点故障宕机或者不响应等情况，这就大大简化了系统对容错的要求；不过类似 Bitcoin、Ethereum 等分布式系统确实需要考虑拜占庭容错的问题，我们会在下面介绍它们是如何解决的。 FLP FLP 不可能定理是分布式系统领域最重要的定理之一，它给出了一个非常重要的结论：在网络可靠并且存在节点失效的异步模型系统中，不存在一个可以解决一致性问题的确定性算法。 In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume…