区块链从 2009 年发展至今,已经演变出多种共识。共识机制之争的就像区块链领域内竞争「王座」的「权力的游戏」。本文通过类比美剧《权力的游戏》来梳理和介绍目前区块链的主流共识协议。

目前,大部分的区块链共识都来自「BFT 家族」、「Proof of X 家族」,又或者是两大家族之间的结合。BFT 共识发展较早但应用场景有限。在区块链诞生后,BFT 类共识也随之复兴,主要应用于许可链内,也可在修改后应用于公链。Proof of X 是目前公链领域内应用较多的一类共识。其中 PoW 最早被应用,但存在资源浪费、算力集中、缺少终局性以及性能低下等。PoS 是目前有力竞争者,可避免资源浪费、弱化了中心矿池需求、降低 51% 攻击可能性,但也同时存在确定记账节点数量困难、存在非预期的中心化问题、Nothing at Stake 等问题。

为了解决以上弊端,当前也诞生了许多混合类共识,希望既融合两者的优势,又能规避某些弊端,包括 PoW+PoS、DPoS+BFT 等。

此外,还有一些思路是应用密码学技术来改进共识,包括门限签名、聚合签名、可验证随机函数等等,但使用效果还有待实践检验。

可以看到,共识算法的「权力的游戏」还在继续,区块链及分布式计算的演化不会停歇。

原文标题:《共识机制的「权力的游戏」》
文章来源:火币研究院
作者:袁煜明、胡智威

报告正文

随着《权力的游戏》第 8 季的到来,这个陪伴我们近 10 年的剧集也将迎来终结。豆瓣评分 9.7 分,朋友圈各种剧透刷屏,随着大 boss 夜王的「冤死」,故事真正的情节高潮还是围绕在几大家族对王座的角逐。

区块链从 2009 年发展至今,已经演变出多种共识,不同共识以不同方法解决了运行中出现的攻击、作弊、延时、一致性、最终确定性等等问题。目前主流的共识算法包括 PoW、PoS、BFT 等,混合共识更如雨后春笋。还有一些在主流基础上演变而来的共识算法,诸如 PoA、PoI、DPoS、PBFT 称得上百家争鸣,不明觉厉。

不夸张地说,共识机制就是区块链技术中的「王座」,而你方唱罢我登场的共识机制之争,就好像一场区块链的「权力的游戏」。

1 两大家族的纷争

何为共识 ? 共识(Consensus)是在分布式的系统中获得一致性数据的计算机科学过程。共识机制非常必要地假设一些流程和系统有较高延迟、无法有时效地沟通甚至于一些节点作恶,因此共识机制需要有一定的容错性。

权利游戏视角看区块链协议竞争:谁能成为 Proof of Thrones?

区块链共识机制让我们看得眼花缭乱,但我们可认为基本都是由 Paxos、BFT 类和 Proof of X 三种基础的共识衍生而成。大部分的区块链共识都来自「BFT 家族」「Proof of X 家族」,又或者是两大家族之间的结合。「BFT 家族」是共识世界中古老的王者,一如古老的龙族 House Targaryen,虽然一度落寞但是能力依旧,并且历经磨难卷土重来。而随着 2008 年比特币白皮书的问世,「Proof of X 家族」开始了风光无限的快速发展,好像是自带主角光环的 House Stark。Stark 家族虽然年轻,但家族成员个个能力超强,每个都是王座的有力争夺者。

webp (1).png

2 BFT 类共识

现在家喻户晓的「拜占庭将军问题」(Byzantine failures),早在 1982 年便出现了,是由美国计算机科学家莱斯利·兰伯特在论文《ACM Transactions on Programming Languages and Systems》2 中提出的分布式系统通信中的一种问题。

兰伯特在提出了拜占庭将军问题之后,也在论文中提出了解决该问题的两种解法,包括口头协议和书面协议等。为了在工程上更加实际可用,学术界后来又不断进行探索研究,诞生了 PBFT (Practical Byzantine Fault Tolerance)[3] 等更为实用的共识协议。这类共识均可归为 BFT 类共识。单从历史来看,BFT 类共识资历最深,是共识机制传统的王者。

拜占庭问题是非常严重且极难处理的。但是除了在飞机发动机系统、核电站等需要大量传感器并对采集结果极端敏感的一些系统环境中适用外,通常的分布式系统,例如 zookeeper 等并不需要拜占庭容错,只需要 Paxos、Raft 等支持 CFT (CrashFaultTolerance)的共识协议即可。 就像 Targaryen 家族被 Baratheon 家族取代一样,可认为 BFT 的王座一度让位于这些 CFT 共识。

不过随着比特币等一系列区块链应用的诞生,区块链的应用场景需求激增,BFT 类共识也得到了很好的发展。目前,BFT 类共识在区块链应用中一般适合于对强一致性有要求的私有链和联盟链场景,但是其变种也适用于公链的共识。

3 Proof of X

直到比特币和区块链的出现,共识机制迎来了由古典时期到现代时期的快速发展。区块链主要的细分领域——公链,是一种去中心化的分布式账本系统,也是未来一切区块链商业应用的基础设施。由于点对点网络下存在较高的网络延迟,各个节点所观察到的交易事务先后顺序不可能完全一致。因此,公链系统需要共识机制来对在一定时间内发生的事务的先后顺序进行共识。共识机制可以解决节点间互相信任的难题,使得区块链在信息传输的过程中同时完成价值转移。共识机制决定了公链的性能,公链则催生了共识机制的繁荣。

3.1 PoW 主角的危机

PoW(Proof of Work 工作量证明),是一种按劳分配模式,即矿工凭借工作量的大小来争取记账的权利。工作量越大对应矿工的算力越大,其获得记账权的概率也越大。

PoW 共识在比特币的应用中具有重要意义,也是最早和迄今为止在实践中最安全可靠的公有链共识算法,支撑了比特币系统超过 10 年无重大故障的平稳运行。

除了 PoW 最早的「中本聪共识」以外,PoW 在后来的发展中还有了更多的一些演化,主要包括分叉选择策略方面和哈希算法方面等。

分叉策略选择

比特币采用的最长链机制,呈现出赢者通吃的一种情况。一些区块链系统对此有不同看法,因而采用了其他的策略。例如,以太坊认为在挖矿竞争中失败的矿工也为整个网络提供了服务,应当予以一定的奖励,因此带来了叔块(Ommer)的概念。在这种情况下的确定主链方式,以太坊用了另一种策略:GHOST (Greedy Heaviest-Observed Sub-Tree Protocol)由简单的最长链策略改为了包含叔块在内、区块最多的一条链。

webp (2).png

调整哈希算法

哈希算法主要用来 PoW 时的工作量证明,即矿工是否找到了一个数值可以满足当前区块的哈希值要求的。在比特币之后,更多的算法被引入或发明出来用于工作量的证明 [4],在单纯哈希的基础上,还加入了更多的计算内容,形成了更为复杂的计算流程。其中一些是因为密码学上已被证明存在安全隐患因此需要以比如增加位数等方式来改进;一些通过内存密集型的算法设计来提升 CPU、GPU 的相对计算优势,以此对抗 ASIC 矿机;还有一些设计用来配合隐私保护。

webp (3).png

当然,也像在《权力的游戏》中一样,危机会随时降临到每个人头上,即使能力最强的主角也是一样。PoW 共识也存在一些明显问题:

资源浪费:PoW 共识过程高度依赖区块链网络节点贡献的算力。同时,加密数字货币生态圈已经在资本和设备方面呈现出明显的「军备竞赛」态势,逐渐成为高能耗的资本密集型行业,进一步凸显了资源消耗问题。

算力集中:根据 btc.com 数据显示,过去一年矿池算力份额排名前五位的矿池占据了比特币总算力份额的 65%,马太效应逐渐显现。同时算力过度集中还存在着 51% 攻击的风险。

性能低:由于需要通过设置一定的工作量来达成共识,PoW 的区块链通常处理交易业务的性能非常低,比如比特币 TPS 理论上最多只有 7 笔 / 秒。

3.2 PoS,王位最有力的冲击者

正因为 PoW 的势微,主流算法里面,PoS (Proof of Stake 权益证明)顺利成章成为了王位最有力的冲击者。PoS 在 PoW 的基础上发展而来,并受到当今区块链共识世界的推崇。在 2014-2017 年期间,基于 PoS 共识打造的区块链逐渐增多,就连市值长期保持第二的以太坊也计划从 PoW 转到 PoS。

PoS 共识机制的提出最早源于人们对挖矿中「公地悲剧」问题的辩论。2010 年 11 月,挖矿公地悲剧 (Disturbingly low future difficulty equilibrium) 由 Vandroiy 指出并引发广泛讨论。2011 年 7 月,数字货币爱好者 Quantum Mechanic 在比特币论坛首次提出 PoS 权益证明共识机制的概念 (Proof of stake instead of proof of work)。客观来说,PoS 机制的诞生确实解决了 PoW 的部分弊端:1. 以 PoS 机制开发新区块在一定程度上避免了资源浪费,同时系统区块的自动产出缓解了由于数字资源有限性而产生的通货紧缩。PoW 机制下,矿池通过规模经济效应来提高产量,降低了长期平均成本;2.PoS 共识机制弱化了中心矿池规模经济的需求,算力集中垄断的情形也得到了缓解,个体竞争力差别相对减小;3. 就 51% 攻击而言,PoS 共识机制发起一小时攻击的成本远大于 PoW 共识机制。

然而 PoS 也存在一些问题需要解决:

无权益问题(Nothing at Stake):用户在 PoS 中可以同时在两个分叉上面下注;无论哪一个分叉后面被公认为主链,该用户都可以获得奖励而没有机会成本的损失。这样也在事实上会干扰共识的形成。

被动形成中心化:PoS 主网上线伊始,创世块中分配的 Token 绝大多数属于数量有限的项目方和早期投资人。因此 PoS 的区块链很容易被早期用户垄断和支配。

记账节点选择问题:很多 PoS 依赖于 BFT 类算法,但是许多 BFT 类共识需要确定节点后才能进行下去。记账节点的不确定还会增大网络分区的概率。

4 天下大乱,混合共识如雨后春笋

几乎所有的共识机制都有其独特的优势,也有其弊端,没有一种共识机制可以完美解决区块链「不可能三角」问题。因此,人们开始思考是否可以将两种共识混合,从而做到既融合两者的优势,又能规避某些弊端。于是就有了混合类共识。

4.1.PoW + PoS

在「混合共识」中,PoW+PoS 混合机制是其中最热门也应用得较为成功的一种共识算法。

2014 年 4 月,拉里·雷恩 (Larry Ren) 在《Reddcoin 白皮书》中提出了权益 - 速度证明(Proof of Stake Velocity,PoSV)共识机制。PoSV 算法前期使用 PoW 实现代币分配,后期使用 PoSV 维护网络长期安全。PoSV 将 PoS 中币龄和时间的线性函数修改为指数式衰减函数,即币龄的增长率随时间减少最后趋于零。因此新币的币龄比老币增长地更快,直到达到上限阈值,这在一定程度上缓和了持币者的屯币现象。

以太坊 Casper 是另一个比较知名的结合方案。为了解决挖矿耗能、网络中心化、性能扩展等多个问题,以太坊目前在通过 Casper 试着从 PoW 转向 PoS。Casper 可视为是以太坊版本的 PoS,但 Casper 目前并不是一个协议,而是包含了 2 个由以太坊团队发起的设计实现,包括了 Casper FFG 和 CasperCBC。其中,CasperFFG[5](Casperthe Friendly Finality Gadget)是一种 PoW+PoS 混合的机制,希望将 PoS 机制逐步引入到以太坊区块链网络中。在这种共识协议下,区块生成的主要过程将仍然通过 PoW 挖矿来进行;不过每间隔 50 或 100 个 PoW 生成的区块,则会设置一个 PoS 的检查点,由验证人对这个检查点上的数据内容进行验证和投票。

此外,这些结合的共识还有:2014 年 5 月发行的 Slimcoin 基于 PoW 和 PoS 提出了燃烧证明 (Proof of Burn, PoB) 共识机制 ; 2014 年 12 月提出了行动证明 (Proofof Activity,PoA) 等等。

4.2 DPoS+BFT

PoS 会导致首富账户的权力更大,有能力支配记账权。2014 年 4 月由 Dan Larimer (BM)提出 DPoS (Delegate Proof of Stake)机制,期望通过引入技术民主层来减少中心化的负面影响。

在 DPoS 共识机制中,存在两种角色,公证人和见证者。公证人是指权益持有者,可以投票选举区块生产者,见证者指被选举出来进行区块生产、验证交易的节点。在 DPoS 中,不是每个节点都具有生产区块的权利,但是每个节点都具有投票权,这一点和议会制度很像:不是每个公民都可以做议员,但是每个公民都具有选举自己信任的议员的权利。DPoS 中的投票是根据投票者权益进行加权的,在投票中使用的权益越多,选举的影响力越大。DPoS 系统中仍然存在中心化现象,但它是受约束的。DPoS 体系里每个客户端都可以决定谁能够被信任,而不用必须像 PoS 一样信任拥有最多资源的人。

不过 DPoS 也存在一些问题:

投票的积极性并不高。绝大多数持股人(90%+)从未参与投票。这是因为投票需要时间、精力以及技能,而这恰恰是大多数投资者所缺乏的。

对于坏节点的处理存在诸多困难。社区选举不能及时有效地阻止一些破坏节点的出现,给网络造成安全隐患。

依赖增发代币。整个共识机制还是依赖于代币的增发来维持代理节点的稳定性。

5 基于密码学的改进,通向王位的龙与魔法?

可以说,以区块链技术为代表特征的加密世界是构建于密码学的基础之上的。目前很多区块链系统也开始回归到这种技术本源,利用各类密码学技术来降低共识的通讯代价、提高共识效率,获得了不错的效果。这些密码学技术包括门限签名、聚合签名、可验证随机函数等。

5.1 门限签名

以上介绍的协议大部分都需要假设基于一个同步或半同步的网络环境,而 HoneyBadger BFT 是第一个知名的异步 BFT 类协议 [6],可在消息延迟没有明确上限的异步网络中运行。它首先将交易拆分为多份,各个节点间相互,减轻发起节点的消息发送瓶颈问题。而因为其异步网络环境,节点间收到交易是非同步的、随机顺序的。节点以二元拜占庭协议剔除无效交易和重复交易等后,得到一个异步公共交易子集(Asynchronous Common Subset)[7]。

而门限加密使得只有 f+1 个诚实节点共同合作才能解密出消息原文,防止恶意节点对于最终交易集的攻击。HoneyBadger BFT 协议的主要限制是其在异步网络下为一个非确定性共识算法。

5.2 聚合签名

E.Kokoris-Kogias 等在其论文中提出了在共识机制中使用聚合签名的方法。论文中提到的 ByzCoin[8] 以数字签名方式替代原有 PBFT 使用的 MAC 将通讯延迟从 [if !msEquation] [endif] 降低至 [if !msEquation][endif];使用聚合签名方式将通讯复杂度进一步降低至 [if !msEquation][endif]。但 ByzCoin 在主节点作恶或 33% 容错等方面仍有局限。

之后一些公链项目,例如 Zilliqa[9] 等基于这种思想,采用 EC-Schnorr 多签算法提高 PBFT 过程中 Prepare 和 Commit 阶段的消息传递效率,并结合分片等优化技术以希望突出改进公有链平台 TPS。

Gosig[10] 也使用该方法,同时还结合了 Algorand 以可验证随机函数的方式选择「Leade」和多轮投票等方法来尽量降低 Leader 作恶可能性。

5.3. 可验证随机函数

可验证随机函数(Verifiable Random Function,简称 VRF)是另一个经常会使用到的密码学技术。在区块链共识里,经常会被用来以一种公平公开的方式选出某些节点,作为出块者或者验证者。因此在公链平台中与中本聪共识进行结合,既可容纳众多参与者,又能尽量避免 PoW 的算力集中等问题。Algorand、VBFT、Dfinity,都是通过引入可验证随机函数的共识机制改进节点中心化的问题。

Algorand 和 Dfinity 的「套路」大体上可从可验证随机函数包含的四个函数来看:1、生成密钥,生成一个公钥私钥对;2、生成随机数输出;3、计算零知识证明;4、验证随机数输出。具体过程是先将前一个随机数(最初的随机数却是协议给定的)和某种代表高度、轮次的变量进行组合,用某种私钥对之进行签名(或者是先签名再组合),最后哈希一下得出最新的随机数。这样产生的随机数旁人很容易验证其合乎算法,「V」就这样得到了;而哈希返回值又是随机分布的,「R」也因此得到保证。正如 VRF 的文字表述,目的就是要生成一个真正随机而且无法被预测的值。

在区块链选出块节点的过程中,为了保证安全,随机是一个基本要求。不过,区块链选节点不单纯是随机就有保证了,还要考虑到攻击成本、治理的公平性等问题。如果单纯使用随机算法,就很容易受到「女巫攻击」:攻击者可以廉价地以大量的傀儡机来增加自己抽中的概率。所以共识机制往往还需要加入算力和持币权益等影响因素来综合设计,以增加攻击者的攻击成本。

但密码学的技术应用也并不是没有代价的。门限签名、聚合签名通常要比普通签名技术需要更大的计算量。在具体技术实现上,有些会需要一些特殊的信息交互过程或中心化的密码基础设施。另外,Algorand 和 Dfinity 这些大量使用 VRF 的区块链系统还没有上线,VRF 在共识中的具体使用效果还有待实践评估检验。

6 结语

共识算法的「权力的游戏」还在继续,区块链及分布式计算的演化不会停歇。回顾共识算法过去 40 年的发展历程,由古典时期 BFT 对一致性的关注,到近代时期中本聪共识对容错和去中心化的追求,再到现在 PoS、VRF 等对性能平衡的聚焦,可以看到:游戏还在继续,未来浪成于微澜之间。

来源链接:www.jianshu.com