【区块链基本技术】共识算法（2）

数字增币

  

微信、浏览器扫描下载杏吧APP

　　11. 权益流通证明（PoSV，Proof of Stake Velocity）

　　采用者：Reddcoin

　　解释：PoSV 是作为 PoW 和 PoS 的一种替代方法而提出的，其目的是提高 P2P 网络的安全性，进而用于确认 Reddcoin 交易。Reddcoin 是一种加密货币，专为加速数字化时代的社交交互而提出的。PoSV 在设计上鼓励所有者（权益）和活动（流通），直接对应于 Reddcoin 作为真实货币的两个主要功能，即存储价值和交换中介。Reddcoin 也可在异构社交场景中作为计量单位使用。

　　12. 重要性证明（PoImportance，Proof of Importance）

　　优点：在权益计算方面要优于 PoS。

　　使用者：NEM

　　解释：NEM 共识网络不仅依赖于代币的数量，而且依赖于生成系统行动得到回报的可能性。区块收益机率是各种因素之一，此外还包括不好的名声（受控于不同的框架设计目的）、差额，以及从该处做出和得到的交易数量。它也被称为“重要性计算”（Importance Calculation），因为它可为“有用的”系统成员提供更全面的图像。

　　一名用户要具有资格执行重要性计算，其账户余额至少需要为 10000 枚 XEM。考虑到只有不到 90 亿枚 XEM 在流通，实现这一目标并非过于昂贵。在未来 10000 枚 XEM 的阈值有可能会发生变化，但就目前而言，它仍然没有变化。重要性计算是使用特定算法完成的，而不仅仅考虑用户份额的概率和规模。

　　需要指出的是，NEM 的 PoImportance 对任何操控都具有抵制力。该共识的底层机制可缓解女巫攻击（Sybil Attack）和循环攻击问题。谨记，“PoImportance 并非 PoS”，尽管两者很容易被同等看待。

　　13. 烧毁证明（PoBurn，Proof of Burn）

　　采用者：Slimcoin、TGCoin（第三代代币）。

　　解释：PoBurn 并非在昂贵的计算设备上一掷千金，而通过发送代币到一个不可检索地址实现“烧钱”（Burn）。将代币发送到一个并不存在的地址，用户将根据某个随机选择过程，获得整个生命时间内对系统挖矿的特权。

　　PoBurn 有多种实现方式，矿工可以烧毁原生的货币，或者烧毁一些其它区块链的货币，例如比特币等。烧毁的代币越多，用户就越有机会被选中去挖掘下一个区块。

　　随时间的流逝，用户在系统的权益会得到弱化。因此，最终用户为增加在这个博彩中被选中的机会，会考虑烧掉更多的代币（这可类比于比特币的挖矿过程，用户必须不断投资更现代的计算设备以维持哈希能力）。

　　尽管 PoBurn 是一种有意思的 PoW 替代者，但是该协议依然会毫无必要地浪费资源。另一个批评是，挖矿能力只会偏向于那些愿意烧掉更多钱的人。

　　14. 身份证明（PoI，Proof of Identity）

　　解释：PoI 是一块表示了加密事实的数据。它支持用户指定一个私钥，并对应到一个经认证的身份，加密将附着到一个指定的交易。来自于某些组中的每个个体都可以创建 PoF(因为它只是一块数据)，并将该数据展示给其它任何处理节点的人。

　　15. 活动证明（PoActivity，Proof Of Activity）

　　使用者：Decred

　　解释：为避免出现恶性通货膨胀（当大量货币充斥系统时就会发生），比特币将只生成两千一百万枚。这意味着，在某些时候，比特币区块奖励补贴将终止，比特币矿工将只能收取交易费用。

　　一些人猜测这可能会导致由“公地悲剧（Tragedy of the commons）”所引发的安全问题，人们出于自身利益考虑行事并破坏系统。因此，人们提出了PoActivity作为一种替代 Bitcoin 的激励结构。PoActivity 是一种结合了 PoW 和 PoS 的混合方法。

　　在 PoActivity 中，挖矿一开始使用的是传统的 PoW，矿工们争相解决加密难题。根据实现，挖掘的区块不包含任何交易，它们更像模板。因此，胜出的区块将只包含头部信息，以及矿工的奖励地址。

　　此时，系统将切换到 PoS。PoActivity 根据头部信息选择一组随机验证者对新区块签名。如果一位验证者所拥有的系统中代币越多，那么该验证者被选中的可能性也会越大。一旦所有验证者已签名，那么模板就会变成一个完整的区块。

　　如果在完成区块时，某些选定的验证者是不可用的，那么就选择下一个胜出区块，并选择一组新的验证者，依此类推，直到区块收到到正确数量的签名。费用由矿工和在区块上签名的验证者分摊。

　　对 PoActivity 的批评包括挖掘区块耗能过高（与 PoW 一样），以及无法阻止验证者做双重签名（与 PoS 一样）。

　　16. 时间证明（PoTime，Proof of Time）

　　使用者：Chronologic

　　解释：PoTime 是一种由 Chronologic 提出的共识算法。Chronologic 设计构建一种独立的区块链，其首席开发人员提出：我们的问题在于，Solidity 中一个变量可存储的最大数是 1076 的数量级。这使我们很难处理时间生成和令牌生成。

　　17. 存在证明（PoExistence，Proof of Existence）

　　使用者：Poex.io、HeroNode、DragonChain。

　　解释：PoExistence 是一种在线服务，它通过比特币区块链对交易打时间戳，验证在特定时间是否存在计算机文件。PoExistence 是作为一项开源项目在 2013 年提出的，由 Manuel Araoz 和 Esteban Ordano 开发。

　　用例：

　　不泄露实际内容的数字签署协议（Digital Sign Agreement）。

　　不泄露实际数据，展示数据的属主。

　　记录时间戳。

　　证明属主。

　　检查文档完整性。

　　18. Ouroboros

　　采用者：Cardano

　　解释：Ouroboros 是 Cardano 使用的共识算法。它是 PoS 的一个变种，具有严格的安全性保证。

　　19. 可收回证明（PoR，Proof of Retrievability）

　　采用者：Microsoft

　　解释：PoR 是一种紧凑证明，表示文件系统（证明者）中的目标文件 F 对客户端（验证者）而言是完整的。由于使用 PoR 比传输文件 F 本身而言具有更低的通信复杂性，因此 PoR 对于构建高可靠的远程存储系统是一种颇具吸引力的构建模块。作为一种共识算法，PoR 对于云计算系统非常有用。

　　20. 拜占庭容错（Byzantine Fault Tolerance）

　　优点：高速、可扩展。

　　不足：通常用于私有网络和许可网络。

　　采用者：Hyperledger Fabric、Stellar、Ripple、Dispatch

　　解释：拜占庭将军问题是分布式计算中的一个经典问题。问题描述为，几位拜占庭将军分别率领部队合力包围了一座城市。他们必须一致决定是否发起攻城。如果一些将军在没有其他将军参与的情况下决定发起攻城，那么他们的行动将以失败告终。将军们之间相互隔着一定的距离，必须依靠信息传递进行交流。 一些加密货币协议在达成共识时使用了特定版本的 BFT，每种版本都具有各自的优缺点：

　　实用拜占庭容错（PBFT，Practical Byzantine Fault Tolerance）：首个提出的该问题解决方案称为“实用拜占庭容错”（PBFT），当前已被 Hyperledger Fabric 采用。PBFT 使用了较少（少于 20 个，之后会稍有增加）的预选定将军数，因此运行非常高效。它的优点是高交易通量和吞吐量，但是不足之处在于是中心化的，并用于许可网络。

　　联邦拜占庭协议（FBA，Federated Byzantine Agreement）：另一类拜占庭将军问题的解决方案是 FBA，已被 Stellar 和 Ripple 等代币使用。FBA 的通用理念是每个拜占庭将军负责自身的链、消息一旦到来，通过排序建立事实。在 Ripple 中，将军（验证者）是 Ripple 基金会预先选定的。在 Stellar 中，任何人都可以成为验证者，需要用户选择去相信哪个验证者。

　　由于 FBA 可提供令人难以置信的吞吐量、低交易开销和网络扩展性，我相信 FBA 类公式算法是目前提出的最好的分布式共识发现算法。

　　21. 授权拜占庭容错算法（dBFT，Delegated Byzantine Fault Tolerance）

　　优点：快速、可扩展。

　　不足：每个人都争相成为根链。其中可能存在多个根链。

　　采用者：Neo。

　　解释：授权拜占庭容错算法，简称 dBFT，是一种支持通过代理投票实现大规模参与共识的拜占庭容错共识算法。在 Neo 中，令牌持有者可以通过投票选取其支持的 bookkeeper。之后，选定的 bookkeeper 组采用 BFT 算法达成共识，并生成新区块。Neo 网络中的投票是实时的，而非因人而异的。

　　dBFT 可为具有个共识节点的共识系统提供(f = {{n-1} over 3})容错。这种容错也涵盖了安全性和可用性、不受将军和拜占庭错误影响，并且适合任何网络环境。dBFT 具有很好的最终性（finality），这意味着一旦最终确认，区块将不可分叉，交易将不可再撤销或是回滚。

　　Neo 的 dBFT 机制生成一个区块需 15 到 20 秒钟。交易吞吐量测定约为 1000 TPS。这对于公共区块链而言，这是很好的性能。通过一定优化，dBFT 具有达到一万 TPSS 的潜力，这样就可支持大规模的商业应用。

　　dBFT 中加入了数字身份技术，这意味着 bookkeeper 可以是真实的个人，也可以是某些机构。因此，dBFT 根据存在于其本身之中的司法判决，可以冻结、撤销、继承、检索和拥有代币兑换权。它有利于实现合规金融资产在 Neo 网络中的注册。Neo 网络从设计上，就是在必要时为此提供支持。

　　22. RAFT

　　优点：

　　模型比Paxos更简单，但提供了同等的安全性。

　　有多种语言的实现可用。

　　不足：通常用于私有网络和许可网络。

　　采用者：IPFS Private Cluster、Quorum。

　　解释：Raft 是一种是设计用于替代Paxos的共识算法。它的本意就是通过实现逻辑分离，比 Paxos 更易于理解。但是它也可以通过形式化证明是安全的，并提供了一些额外的特性。Raft 提供一种在计算系统集群中实现分布状态机的通用方式，确保了集群中的每个节点在同一组状态转移上取得一致。它具有一系列的开源参考实现，包括Go、C++、Java、Scala等语言的完全声明实现。

　　Raft 通过选取领导者实现共识。在 Raft 集群中，一个服务器可以是领导者（leader），也可以是追随者（follower），也可以作为一些特定选举情况下（例如缺少领导者）的候选者。领导者负责向追随者发送日志副本。领导者通过发送心跳消息，定期通知追随者自身的存活情况。每位追随者维护一个超时（通常在 150 到 300 毫秒之间），正常情况下应在此时间范围内收到领导者的心跳。一旦收到心跳，超时就会重置。如果没有收到心跳，那么追随者就将自身状态更改为候选者，并开始领导者选举。

　　23. 恒星共识（Stellar Consensus）

　　优点：去中心化控制、低延迟、灵活的信任机制、渐进安全（Asymptotic security）。

　　采用者：Stellar

　　解释：恒星共识基于上文介绍的联邦拜占庭共识（FBA）。

　　恒星共识协议（SCP，Stellar Consensus Protocol）提供了一种不依赖闭合系统实现准确记录金融交易而达成共识的方法。SCP 具有一组可验证的安全属性，这些属性根据如何安全地保持活力而做了优化。一旦出现分区或不当行为节点，它将会终止网络过程，直至达成共识。SCP 同时具备四种属性：去中心控制、低延迟、灵活信任机制和渐进安全。

　　24. 置信度证明（PoB，Proof of Believability）

　　优点：

　　通过使用一种称为“Servi”的理念，PoB 比传统 PoS 更加去中心化（细节在下文给出）。

　　相比于传统的 PoS，具有更快的最终性（Finality）。

　　采用者：IOST

　　解释：传统的 PoS 共识机制面临的主要挑战是趋向于中心化。为了降低这种风险，IOST 引入了“Servi”概念。Servi 不仅衡量了用户对社区的贡献，而且鼓励成员为 IOSChain 的持续发展做出贡献。Servi 具有以下属性：

　　不可交易性（Non-tradable）：由于 Servi 并非设计作为一种交换媒介，因此 Servi 不能以任何方式交易或做交换。

　　自毁性（Self-destructive）：验证区块后，系统将自动清除验证者拥有的 Servi 余额。通过这种方式，具有高可信度分值的节点可轮流验证区块，确保了公平区块的生成。

　　自发行性（Self-issuance）:Servi 在做出某些贡献之后（例如，提供社区服务、估其他实体提供的服务，以及其它一些特殊贡献），将会自动生成并存入用户帐户。

　　传统的区块链系统在安全性和吞吐量间存在着固有的折衷，具体取决于分片（shard）的大小。具有大量小分片的系统可提供更好的性能，但抵抗不良行为者的稳定性低，反之也是如此（这也是 Casper 面临的一个问题）。为了在保持安全和提高吞吐量的情况下打破这种权衡，IOST 创新性地提出了一种用于 IOSChain 的 PoB 共识协议。PoB 确保了节点产生行为不端的可能性微乎其微，同时通过确定分片规模（size-one-shard），显著地提高了交易吞吐量。

　　PoB 共识协议使用一种分片内“可信度优先”的方法。该协议将所有的验证者分为两组，一组是可信的联盟，另一组是正常的联盟。在第一阶段，可信的验证者快速地处理交易。之后在第二阶段，普通验证者对交易做抽样并验证，提供最终结果，确保可验证性。节点被选入可信联盟的机会是由可信度分值确定的。可信度分值由多个因素计算，包括令牌余额、对社区的贡献、评论等。具有较高可信度分值的人，更有可能被选入可信联盟。可信验证者遵循一定的程序，决定已提交的交易及其订单的集合，并按顺序处理它们。可信验证者也会构成一些较小的组，甚至可以每组一名验证者。交易将在这些可信验证者之间随机分配。因此，PoB 会产生具有极低延迟的较小区块。

　　但是，由于只有一个节点在执行验证，因此 PoB 可能会存在安全问题。行为不当的验证者可能会提交一些已损坏的交易。为了解决这个安全问题，PoB 指定了一个采样概率。普通验证者根据概率对交易做采样，并检测交易的不一致性。如果验证者被检测出存在不良行为，那么该验证者将会失去所有系统中的令牌和声誉，而被欺诈的用户将获得所有损失的补偿。“可信度优先”使处理交易非常快，因为只有一个（可信的）验证者执行验证，并且该验证者不太可能存在行为不端。

　　25. 有向无环图（DAG，Directed Acyclic Graphs）

　　优点：

　　由于 DAG 的非线性结构，它是高度可扩展的、快速、节能、立即实现终结性（Finality）。

　　不足：只能通过使用 Oracle 实现智能合约。

　　采用者：Iota、HashGraph、Byteball、RaiBlocks/Nano。

　　解释：DAG 是一种更通用形式的区块链。由于其独特结构，DAG 内在支持高可扩展性，因此也得到了广泛的使用。

　　从根本上说，任何区块链系统都具有线性结构，因为区块是依次添加到链中的。这使得相比于并行向链中添加区块，线性区块链在本质上是非常缓慢的。但是对于 DAG 而言，每个区块和交易只需数个前期区块得到确认，就可以并行地添加到区块和交易中。这意味着，DAG 在本质上是高可扩展的。

　　DAG 存在多种变体，取决于：

　　· 如何选取前期区块验证的算法，也称为“Tip 选择算法”。

　　· 交易完成的顺序。

　　· 如何抵达完成状态。

　　下面列出一些广为使用的 DAG 项目。

　　25.1 Tangle（IOTA）

　　解释：Tangle是一种 DAG 共识算法，由 IOTA 使用。为了发送一个 IOTA 交易，用户需要验证接收到的前两个交易。在更多交易添加到 Tangle 的情况下，这种二对一、前瞻性支付的共识可加强交易的有效性。由于共识是由交易确定的，因此理论上，如果有人可以生成三分之一的交易，那么他就可以说服网络中的其余部分，使得他的无效交易变成有效的。一旦交易量足够大，使得个人难以创建三分之一交易量，这时 IOTA 就会在一个称为“协调器（The Coordinator）”的中心节点上对网络中的所有交易做“复核”（double-checking）。按 ITOA 的说法，协调员的工作类似于辅助轮。一旦 Tangle 达到一定的规模，协调员就会被从中移除。

　　25.2 Hashgraph

　　解释：Hashgraph 是由 Leemon Baird 开发的一种 Gossip 协议共识。节点随机与其它节点共享自身已知的交易，最终所有交易都被以 Gossip 协议传播到（Gossip around）到所有节点。Hashgraph 对于私有网络是一个很好的选择。但我们并不会看到它实现在以太坊这样的公共网络中，或是不通过 Gossip 协议随机传播交易。

　　25.3 Holochain

　　解释：Holochain 十分类似于 HashGraph，但不同于 Hashgraph。它提供了一种可用于构建去中心化应用的数据结构。用户可以具有自己的链，并向其中添加包括金融交易在内的数据。链可以采用复杂的方式合并、拆分和交互。数据以去中心化的方式存储（类似于 Bittorrent）。数据具有一个哈希值，即一个对应于数据的数学指纹。如果有人意图篡改数据，那么我们就会注意到在数据和哈希值之间存在不匹配，这样就可拒绝数据为无效的。数字签名保证了数据的作者身份。Holochain 可看成是“Bittorrent+git+ 数字签名”。

　　25.4 Block-Lattice（Nano）

　　解释：Nano（以前称为 Raiblocks）是以缠绕在区块链上的方式运行，这种方式被称为“块状格子”（Block-lattice）。在 Block-lattice 结构中，每个用户（地址）都有自己的链，只有用户本身可写，每个用户都拥有所有链的副本。

　　每个交易都可分解为发送者链上的发送区块，以及接收者链上的接收区块。Block-lattice 看上似乎太简单，以至于无法工作，但它已经在实际运行了。Block-lattice 的独特结构的确无法抵制一些独特的攻击向量，例如 Penny-spend 攻击。在这种攻击中，攻击者通过向大量空钱包发送数额可忽略不计的金钱，导致必须要追踪的链数量急剧膨胀。

　　25.5 SPECTRE

　　解释：SPECTRE，即“序列化 PoW 事件并通过递归选举确认交易”（Serialization of Proof-of-work Events, Confirming Transactions via Recursive Elections），是提议的一种 Bitcoin 扩展解决方案。它利用 PoW 和 DAG 的组合实现可扩展的共识。在 SPECTER 中，一个挖掘的区块指向多个父节点，而不仅仅是单个节点，这使得网络每秒可以处理多个区块。而挖掘指向某些父区块的区块，这将支持区块的有效性。与 PoW 的“最长链胜出”的原则相比，SPECTER 使用的原则可描述为“拥有最多子节点的区块胜出”。SPECTRE 尚未得到实际运行测试，因此可能会存在一些新的攻击向量。但我认为，SPECTRE 很有可能成为一种修正 Bitcoin 问题的潜在好做法。

　　25.6 ByteBall

　　解释：ByteBall 使用 DAG 建立交易间的偏序关系，此外还在 DAG 中添加了“主链”（MC，Main Chain）。

　　图 DAG 中加粗显示的“主链”

　　MC 允许在交易间定义全序关系，即更早加入（直接或间接）MC 的交易，必定更早出现在全序中。如果存在“双重支付”问题，那么将视较早出现在全序中的交易版本为有效的，而其它所有的交易均被视为是无效的。

　　根据交易在图中的位置，MC 可得到确定性的定义。相关详细信息，请参阅白皮书。作为一般性规则，MC 倾向于采纳由一些总所周知用户所给出的交易，这样的用户被称为“证人”（Witnesses）。证人列表是由用户自己定义的，因为列表中包括了用户发布的每个交易。然后，MC 沿着 DAG 内路径推进。推进原则包括：

　　· MC 上相邻交易的证人列表要么完全相同，要么只存在一个突变。

　　· 与其它链相比，MC 中为经过最多数量的由见证人认证的交易。

　　ByteBall 也是首个在系统中包含 Oracle 的平台。Oracle 是在 DAG 中添加智能合约功能所必需的。