精华内容
下载资源
问答
  • 全球共识——分布式的未来,恒星共识协议白皮书概论。 _ 奇瓦
  • 极简区块链共识协议

    2021-01-11 11:31:08
    如何设计一种简单而高效的共识协议一直是学术界和工业界追求的目标。比特币的设计虽然简单,但性能低下且共识结果具有一定随机性,因此不适用于企业之间业务量巨大的场景。近年来大家非常关注的联盟链中应用的共识...

    导读

    区块链作为典型的分布式系统,其共识核心的设计和实现一直困扰着开发者。如何设计一种简单而高效的共识协议一直是学术界和工业界追求的目标。比特币的设计虽然简单,但性能低下且共识结果具有一定随机性,因此不适用于企业之间业务量巨大的场景。近年来大家非常关注的联盟链中应用的共识算法(PBFT、Tendermint)虽然性能接近传统的共识算法(Paxos、Raft),但协议设计相对比较复杂,实现难度较高。本文着眼于一种针对联盟链设计的极简区块链协议 Streamlet。具有一定区块链知识背景的人只需要不到10分钟就能理解整个共识流程,因此 Streamlet 不仅适用于工程化实现,而且具有非常现实的教学意义。

    背景

    Streamlet[1] 由 Cornell 大学的 Elaine Shi 教授团队在2020年2月的斯坦福区块链大会提出(也许更早),其前身是 Pala[2]。Streamlet 可以算作是近五年来区块链领域与传统拜占庭共识(Byzantine fault-tolerant,BFT)领域的集大成之作,在包括经典 PBFT[3],Cosmos 在用的 Tendermint[4],以太坊 2.0 将要用的Casper[5],以及 Facebook 推出的数字货币 Libra[6] 所基于的 HotStuff[7] 等协议中都能感受到对 Streamlet 的影响。尽管如同一个大杂烩,但 Streamlet 的目标是一种堪比比特币的极简区块链协议。

    Streamlet 遵循传统 BFT 协议的容错规则,即在节点数目为 n 的网络中,可以容忍最多 f 个拜占庭节点,需要满足 n > 3f。Streamlet 依赖于半同步(partially synchronous)网络假设,即网络在大部分情况都是好的,消息可以在一个能够预测的延迟内传播,但在某些情况下网络可能会经历一段波动期(Global Stabilization Time,GST),并最终会恢复。在GST期间,网络延迟无法预测。Streamlet 和大多数协议一样,保证协议在异步网络下的安全性(safety),当网络回归同步时可以进一步保证活性(liveness)。

    Streamlet

    在 Streamlet 中,协议的运行被划分为一个个同步的 epoch(这里的epoch是指生成一个区块的时间周期,例如每个 epoch 持续 1 秒),每个 epoch 都由哈希算法随机分配一个 leader进行“随机选主”。每个 leader 在属于自己的 epoch 中发布(propose)一个区块给其它 replica 节点投票(vote)。投票可以被看作是投票者用自己的私钥对区块哈希值的签名,并将其广播给其它所有节点。如果一个区块收到了来自超过 2/3 不同节点的投票,则被认为是“已证区块(notarized block)”。由已证区块组成的链被称为“已证链(notarized chain)”。接下来介绍整个 propose-vote 的流程中的一些细节。

    • 发布规则(Proposing Rule)。每个 leader 都在本地最长的已证链的基础上发布新的区块,即新区块的 prevHash 指向本地最长的已证链末尾的区块。

    • 投票规则(Voting Rule)。每个 replica 只对来自当前 leader 发布的第一个区块投票,并且该区块必须扩展自本地最长已证链,即该区块的 prevHash 必须指向投票者本地最长的已证链末尾的区块。

    • 确认规则(Commit Rule)。一个区块在区块链中被确认(commit)意味着网络中所有诚实节点对这个区块已经达成了共识,不会再对共识结果修改。已证区块并不一定最终会被确认。在一个已证链中,当存在三个连续的已证区块时,其中前两个区块以及同一链上之前的所有区块都被确认。在这里,连续区块的意思是连续的 epoch。例如,在图 1 中,epoch 5、6、7 连续产生了三个已证区块,因此当区块 7 成为已证区块时,区块 5 和 6 以及之前的区块 2 都被确认。

    图片 

    Streamlet 协议的整个流程到这里就全部介绍完了,是不是堪比比特币中的 PoW 一样简单?其中的发布规则和投票规则类似于比特币中的最长链(The Longest Rule)原则,而确认规则类似于比特币中一般需要末尾 6 个区块确认的规则。两者看起来有很多相似之处,但算法本质却大有径庭。从这点看来,Streamlet 吸收了区块链的设计精髓并将其与传统的 BFT 协议融合在一起,得到了新一代的 BFT 协议。那么有些读者可能想问了,如此简单的协议安全性如何呢?

    安全性

    在区块链中,协议的安全性可以简单表述为不存在两个同样高度的不同区块被确认。在这里我们简单通过图示来展示在异步网络以及拜占庭攻击的情况下 Streamlet 是如何保证安全性的。如上面的图 1 所示,由于 epoch X 的区块与区块 6 在同一高度,那么问题可以转化为:是否存在区块 X 且 X 是已证区块?

    为了证明上面的问题不存在,我们采用反证法。首先,假设存在已证区块 X,那么只存在两种可能性,即 X = 4 或者 X ≥ 8,这是由于同一个 epoch 不可能产生两个已证区块(诚实的 replica 不会在同一 epoch 给不同的区块投票)。下面分情况讨论。

    • X = 4。由于区块 X 是已证区块,意味着有超过 2/3 的节点给区块 X 投票,那么可以进一步推论出超过 2/3 的节点在给 X 投票的时候已经在本地有了已证区块 3。因此,当协议运行到 epoch 5 的时候,不可能有足够多的节点给区块 5 投票。这是由于投票规则的限制,诚实节点只给最长已证链上的区块投票。这与区块 5 是已证区块的假设违背。

    • X ≥ 8。由于区块 7 是已证区块,意味着有超过 2/3 的节点给区块 7 投票,那么进一步可以推测超过 2/3 的节点在给区块 7 投票的时候已经在本地有了已证区块 6。因此,当协议运行到 epoch X 的时候,同样由于投票规则的限制,区块 X 不可能成为已证区块,这与假设违背。

    上面两种情况已经包含了可能出现的所有情况,因此安全性得证。虽然图 1 所示的情况是一个个例,但很容易对结论进行一般化证明。详细证明可以参考原论文。

    活性

    活性的含义是客户端发送的交易最终会在区块链上被确认。在传统 BFT 协议中,活性的保证的其中一个前提是足够多的诚实节点在同一 epoch 的时间足够长。Streamlet 为了使得协议足够简单,采用了同步时钟来保证活性。例如,每个 epoch 被预设成固定的 1 秒钟。在实际的使用中可以将每个 epoch 的时长根据网络最大延迟来设置。由于以上的限制,Streamlet 一般只会被部署在网络条件较好的数据中心网络中,否则很难找到一个合适的 epoch 长度,进而影响协议性能。

    在 Streamlet 中,活性的证明被表述为在 GST 之后如果连续 5 个 epoch 都是诚实的 leader,那么一定会有区块被确认。由于在长时间运行中,总会出现至少一次联系 5 个 leader 都是诚实的情况,因此活性可以得到保证。那么问题是,为什么需要 5 个连续的而不是 3 个?这里可以简单理解为前 2 个 epoch 用来解决由于 GST 所造成的潜在的不一致,之后连续 3 个 epoch 则是确认规则所要求的,为了保证最终能有区块被确认。完整的活性证明可以参考原论文。

    协议对比

    接下来通过对比讨论目前常见的几种 BFT 协议之间的差异。其中,Streamlet 和 HotStuff/LibraBFT 都是新型的链式 BFT,即节点的每次投票不仅是对当前区块的投票,同时也是对这个区块之前所有区块的投票,因此相比于 Tendermint 和 PBFT来说,消息的种类较少,实现起来也更简单,也更容易优化性能。由于链式 BFT 的特性,接收到一轮 2/3 投票的区块并不会被 commit,因此当区块不连续的时候会有分叉产生。

    图片

    在协议同步方面,只有 Streamlet 采用了同步时钟的方式。由于很难保证不同节点之间的时钟严格同步,所以一般情况下每个 epoch 的时间会略长与网络最高延迟,从而提高了协议的延迟。其它三种协议采用传统的超时加倍模式,即每当一段等待时间之后没有收到区块,那么则将下一轮的等待时间加倍。虽然这种方式没有额外的网络开销,但在某些极端情况下会使得协议长时间停滞。LibraBFT 使用了消息传递的模式(Pacemaker)进行同步。虽然这种方式能够快速实现同步,但也使得 view-change 时的消息复杂度提高到 O(n^2)。

    Best-case 延迟是指在最好的情况下协议经过多少轮投票可以确认一个区块。虽然 Streamlet 和 HotStuff/LibraBFT 都要求 3 个连续的区块才触发确认事件。但 Streamlet 可以一次确认两个区块,而 HotStuff/LibraBFT 只能一次确认一个区块。

    从消息复杂度来看,HotStuff/LibraBFT 和 Tendermint 采用聚合签名或者阈值签名的技术由一个节点(比如 leader)将来自 replica 的签名聚合成一个单一签名后再广播给所有 replica,因此消息复杂度可以达到 O(n)。而 Streamlet 和 PBFT 则在投票阶段使用了广播,使得消息复杂度较高。

    另外一个值得被提到的特性是 view-change 时的响应性(Responsiveness)。响应性指的是当 view-change 发生时,下一个 leader 是否能快速推进协议。例如,Tendermint 没有响应性,在发生 view-change 的时候节点需要等待一个 timeout,以确保在 timeout 之内收到所有的有效消息。如果没有 timeout 的假设,则可能会由于节点锁在不同的阶段而导致活性出现问题。HotStuff/LibraBFT 和 PBFT 都有响应性,但代价分别是多一轮的投票以及更高的复杂度。

    从上面的对比可以看出,即使共识算法经过了这么多年的发展,也没有出现哪个协议是全能将军。协议的设计本质就是在取舍,不仅体现在安全性和活性之争,也包括性能、复杂度、容错性、响应性等多种性质。某些协议的特性只有遇到合适的应用场景才能发挥价值。例如,在一些网络环境较好的数据中心当中,选择 Streamlet 可能在工程实现以及延迟上更有优势,而在一些广域网环境中可能选择消息复杂度更低且具有响应性的 HotStuff 更好。

    总结

    Streamlet 作为新一代 BFT 共识协议,很好地将区块链中的链式结构与传统 BFT 相结合,极大简化了协议设计,不仅降低了开发者学习区块链和 BFT 协议的门槛,也为工程师们开发区块链系统提供了很好的模板。

     

    参考文献

    [1] Streamlet: Textbook Streamlined Blockchains

    [2] PaLa: A Simple Partially Synchronous Blockchain

    [3] Practical Byzantine Fault Tolerance

    [4] Tendermint

    [5] Casper the Friendly Finality Gadget

    [6] State Machine Replication in the Libra Blockchain

    [7] HotStuff: BFT Consensus in the Lens of Blockchain

     

    作者简介

    盖方宇

    来自趣链科技基础平台部,区块链共识算法研究小组

    展开全文
  • 该算法基于最大共识技术,并且精确提供了共识迭代的次数。 我们证明该估计器是稳定的,并且均方误差等于集中式估计器获得的均方误差。 此外,我们将此有限时间共识卡尔曼滤波算法扩展到具有不均匀时变通信延迟的...
  • 在区块链中,不同节点为了达成数据一致而按照同一套逻辑处理数据。...拜占庭将军问题被认为是在分布式系统中达成共识的最难解的问题之一,而与之对应的拜占庭容错共识算法是区块链网络的基础设施之一。
  • POS 共识协议.docx

    2018-04-12 23:12:29
    POS的设想是非常好的——采用POS的货币的安全性直接与使用者相关,省去了矿工这个媒介。POS简单说就是,每当发表一条消息的时候,不用证明你付出了什么代价,而要证明你拥有一定数量的钱。而拥有钱代表着,如果你...
  • 摘要 PlatON提出了一种基于部分同步假设情形下的并行拜占庭容错协议CBFT(Concurrent ...本文分析了PBFT,Tendermint,Hotstuff等共识协议,CBFT综合了其优点,通过pipeline的方式完成区块生成和确认的并行,在一个视

    摘要

    PlatON提出了一种基于部分同步假设情形下的并行拜占庭容错协议CBFT(Concurrent Byzantine Fault Tolerance),解决区块链共识效率的问题。
    PlatON提出了一种基于部分同步假设情形下的并行拜占庭容错协议CBFT(Concurrent Byzantine Fault Tolerance),解决区块链共识效率的问题。本文分析了PBFT,Tendermint,Hotstuff等共识协议,CBFT综合了其优点,通过pipeline的方式完成区块生成和确认的并行,在一个视图窗口内可以出多个块,并可以在O(n2)内完成视图窗口切换,从而提高共识效率。

    分布式网络模型

    按照分布式系统理论,分布式系统的网络模型分为三类:

    同步网络模型:节点所发出的消息,在一个确定的时间内,肯定会到达目标节点
    异步网络模型:节点所发出的消息,不能确定一定会到达目标节点
    部分同步网络模型:节点发出的消息,虽然会有延迟,但是最终会到达目标节点

    同步网络模型是十分理想的情况,异步网络模型是更为贴近实际的模型,但据FLP不可能[1]原理,在异步网络模型假定下,共识算法不可能同时满足安全性(safety)和活性(liveness),目前的BFT类共识算法多是基于部分同步网络模型假定。我们也是基于部分同步网络模型假定来进行讨论。

    BFT共识协议

    概述

    一个分布式系统是由多个节点组成,节点之间需要网络发送消息通信,根据它们遵循的协议在某个任务消息达成共识并一致执行。这个过程中会出现很多类型的错误,但它们基本上可以分为两大类。

    · 第一类错误是节点崩溃、网络故障、丢包等,这种错误类型的节点是没有恶意的,属于非拜占庭错误。

    · 第二类错误是节点可能是恶意的,不遵守协议规则。例如验证者节点可以延迟或拒绝网络中的消息、领导者可以提出无效块、或者节点可以向不同的对等体发送不同的消息。在最坏的情况下,恶意节点可能会相互协作。这些被称为拜占庭错误。

    考虑到这两种错误,我们希望系统始终能够保持两个属性:安全性(safety)和活性(liveness)。

    · 安全性:在以上两类错误发生时,共识系统不能产生错误的结果。在区块链的语义下,指的是不会产生双重花费和分叉。

    · 活性:系统一直能持续产生提交,在区块链的语义下,指的是共识会持续进行,不会卡住。假如一个区块链系统的共识卡在了某个高度,那么新的交易是没有回应的,也就是不满足liveness。

    BFT(拜占庭容错协议)是一种即使系统中存在恶意节点也能保证分布式系统的安全性和活性的协议。根据Lamport[2]的经典论文,所有BFT协议都有一个基本假设:节点总数大于3f时,恶意节点最大为f,诚实节点可以达成一致的正确结果。

    PBFT

    实用拜占庭容错算法(PBFT[3])是现实世界里首批能够同时处理第一类和第二类错误的拜占庭容错协议之一,基于部分同步模型,解决了之前BFT类算法效率不高的问题,将算法复杂度由节点数的指数级降低到节点数的平方级,使得拜占庭容错算法在实际系统应用中变得可行。

    目前区块链中使用的BFT类共识协议都可以认为是PBFT的变形,与PBFT一脉相承。

    正常流程

    PBFT正常流程如下所示(图1中C为客户端,系统中有编号分别为0~3的四个节点,且节点3为拜占庭节点):

    在这里插入图片描述
    PBFT正常流程为3阶段协议:

    · pre-prepare:主节点(Primary)广播预准备消息(Preprepare)到各副本节点(Replica)

    · prepare:该阶段是各个节点告诉其他节点我已经知道了这个消息,一旦某个节点收到了包含n-f 个prepare消息(我们将使用QC也就是Quorum Certificate来指代,下同)则进入prepared状态

    · commit:该阶段是各个节点以及知道其他节点知道了这个消息,一旦某个节点收到了n-f 个commit消息(QC)则进入committed状态

    视图切换流程

    视图切换(viewchange)是PBFT最为关键的设计,当主节点挂了(超时无响应)或者副本节点集体认为主节点是问题节点时,就会触发ViewChange事件,开始viewchange阶段。此时,系统中的节点会广播视图切换请求,当某个节点收到足够多的视图切换请求后会发送视图切换确认给新的主节点。当新的主节点收到足够多的视图切换确认后开始下一视图,每个视图切换请求都要包含该节点达到prepared状态序号的消息。

    在视图切换过程中,我们需要确保提交的消息序号在整个视图更改中也是一致的。简单来说,当一个消息定序为n,且收到2f+1个prepare消息之后,在下个视图中,依然会被分配序号为n,并重新开始正常流程。
    在这里插入图片描述
    如图2所示,viewchange会有三个阶段,分别是view-change,view-change-ack和new-view阶段。从节点认为主节点有问题时,会向其它节点发送view-change消息,当前存活的节点编号最小的节点将成为新的主节点。当新的主节点收到2f个其它节点的view-change消息,则证明有足够多人的节点认为主节点有问题,于是就会向其它节点广播。

    通信复杂度问题

    PBFT是基于三阶段投票即可达成共识的协议。prepare和commit阶段中,都需要每个节点广播自己的prepare或commit消息,因此通信复杂度是O(n2)。view change过程中,需要所有的副本节点先time out,然后对于view change这件事达成共识,然后,他们把这个共识(以及已经达成了共识这件事)告诉新的主节点,新的主节点还要把这个消息广播出去宣布view change,因此,view change的通信复杂度是O(n3) 。

    高达O(n3) 的通信复杂度无疑给PBFT的共识效率带来了严重的影响,极大地制约了PBFT的可扩展性。

    BFT协议的优化

    如何把O(n3) 的通信复杂度降到O(n),提高共识效率,是BFT共识协议在区块链场景中面临的挑战。针对BFT共识效率的优化方法,具有以下几类:

    聚合签名

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

    之后一些公链项目,例如Zilliqa[5]等基于这种思想,采用EC-Schnorr多签算法提高PBFT过程中Prepare和Commit阶段的消息传递效率。

    通信机制优化

    PBFT使用多对多(all-to-all)的消息模式,因此需要O(n2)的通信复杂度。

    SBFT(Scale optimized PBFT)[6]提出了一个使用收集器(collector)的线性通信模式。这种模式下不再将消息发给每一个副本节点,而是发给收集器,然后再由收集器广播给所有副本节点,同时通过使用门限签名(threshold signatures)可以将消息长度从线性降低到常数,从而总的开销降低到O(n2)。

    Tendermint[7]使用gossip通信机制,乐观情况下可以将通信复杂度降低到O(nlogn)。

    view-change流程优化

    所有的BFT协议都通过view-change来更换主节点。PBFT,SBFT等协议具有独立的view-change流程,当主节点出问题后才触发。而在Tendermint、HostStuff[8]等协议中没有显式的view-change流程,view-change流程合入正常流程中,因此提高了view-change的效率,将view-change的通信复杂度降低。

    Tendermint将roundchange(和viewchange类似)合入正常流程中,因此roundchange和正常的区块消息commit流程一样,不像PBFT一样有单独的viewchange流程,因此通信复杂度也就降为O(n2)。

    HotStuff参考Tendermint,也将视图切换流程和正常流程进行合并,即不再有单独的视图切换流程。通过引入二阶段投票锁定区块,并采用leader节点集合BLS聚合签名的方式,将视图切换的通信复杂度降低到了O(n)。

    链式BFT

    传统BFT需要对每个区块进行两轮共识,O(n)的通信复杂度可以让区块达到prepareQC,但是必须要O(n2)的通信复杂度才能让区块达到commitQC。

    Hotstuff将传统BFT的两轮的同步BFT改为三轮的链式BFT,没有明确的prepare,commit共识阶段,每个区块只需要进行一轮QC,后一个区块的prepare阶段为前一个区块的pre-commit阶段,后一个区块的pre-commit阶段为前一个区块的commit阶段。每次出块的时候都只需要O(n)的通信复杂度,通过两轮的O(n)通信复杂度,达到了之前O(n2)的效果。

    流水线(Pipelining)和并行处理(Concurrency)

    PBFT、Tendermint等协议具有即时确定(Instant Finality)的特性,几乎不可能出现分叉。在PBFT中,每个区块被确认后才能出下一个区块,Tendermint还提出区块锁定的概念,进一步确保了区块的即时确定性,即在某个round阶段,节点对区块消息投了pre-commit票,则在下一个round中,该节点也只能给该区块消息投pre-commit票,除非收到新proposer的针对某个区块消息的解锁证明。

    这类BFT共识协议本质上是一个同步系统,将区块的生产和确认紧密耦合,一个区块确认后才能生产下一个区块,需要在块与块间等待最大的可能网络延迟,共识效率受到很大限制。

    HotStuff的Pipelining方法将区块的生产和确认分离,每个区块的最终确认需要后两个区块达到QC,也就意味着上一个区块没有完全确认(需要满足Three-Chain)的情况下可以生产下一个区块。这种方式实际上还是一个半同步系统,每个区块的产生还是需要等上一个区块达到QC。

    EOS[9]的BFT-DPoS共识协议可认为是一种完全并行的Pipelining方案:每个区块生产后立即全网广播,区块生产者一边等待 0.5 秒生产下一个区块,一边接收其他见证人对于上一个区块的确认结果,使用BFT协议达成共识,新区块的生产和旧区块确认的接收同时进行,这极大地优化了出块效率。

    CBFT共识协议

    为什么设计CBFT

    前面的内容中,我们分析了BFT共识协议的问题,以及几种主流的优化BFT共识协议,这些BFT共识协议在降低通信复杂度和出块效率方面都取得了不错的研究成果,但仍存在一些改进空间。

    · PBFT较之于之前的BFT算法虽更实用,但因受制于O(n^(3))的视图切换开销,在扩展性方面存在很大的问题。

    · Tendermint将round change和正常流程合并,简化了视图切换逻辑,将视图切换的通信复杂度降低为O(n2),但需要等待一个比较大的网络时延来保证活性。同时Tendermint仍然是串行出块和确认,一个区块的投票需要等上一个区块commit完成才能开始。

    · EOS的BFT-DPOS共识协议中,区块生产者可以连续产生若干区块,同时区块采用并行确认,提高了出块速度。使用BFT协议确认出块,但仅适用于强同步的通信模型。

    · HotStuff创新地提出了基于leader节点的、三阶段提交的BFT 共识协议,吸收了Tendermint的优点,将viewchange和正常流程合并,并将viewchange的通信复杂度降至线性。同时通过简化消息类型,可以pipeline的方式确认区块。但引入了新的投票阶段也会增加通信复杂度,同时一个视图窗口只确认一个区块,这无疑需要耗费较多的通信复杂度在视图切换上。此外,基于Leader节点收集投票的星状拓扑结构,比较适合于Libra这种网络环境良好的联盟链,在弱网环境中比较容易受单点故障影响,造成较大的leader节点切换开销。

    因此,我们提出了CBFT共识协议,在以上共识协议的基础上进行进一步的优化,可以极大地降低通信复杂度 ,并且提高出块效率。

    CBFT概述

    CBFT基于部分同步网状通信模型,提出了一个三阶段共识的并行拜占庭容错协议。网状的通信模型更适合公网的弱网环境,在PlatON上已经使用了该协议作为共识算法。

    CBFT的正常流程和Hotstuff 类似,分为prepare,pre-comit,commit和decide几个阶段。但CBFT还作了关键的改进:在一个视图窗口内可以连续提议多个区块,下一个区块的产生不用等上一个区块达到QC;而各个节点可以在接收上一个区块投票的同时,并行执行下个区块的交易,以pipeline的方式对区块进行投票确认, 从而极大提高出块速度。

    CBFT有自适配的视图切换机制:在一个视图窗口内,节点接收到足够多的区块和赞成票(超过2/3的节点投票,也就是QC)时,会自动进行窗口切换,切换到下一个窗口,无需进行viewchange投票。此外,节点才会启动viewchange流程,并且在viewchange阶段引入了和Hotstuff一样的二阶段锁定投票规则,同时使用BLS聚合签名,在O(n2)的通信复杂度内完成视图窗口切换。

    根据上面的讨论,CBFT只在正常流程之外才会进行viewchange,因此相比HotStuff会有更少的视图切换开销。

    接下来先给出CBFT共识中涉及的相关概念及含义说明,便于之后对 CBFT进行详细介绍。

    CBFT相关术语

    提议人(Proposer):CBFT共识中负责出块的节点
    T: 时间窗口,每个提议人只能在自己的时间窗口进行出块
    N: 共识节点总数
    f: 拜占庭节点最大数量
    足够多赞成票: 表示为至少收到N-f张赞成票
    验证人(Validator): 共识节点中非提议人节点
    视图(View): 当前提议人的时间窗口可以产生区块的时间范围
    ViewNumber: 每个时间窗口的序号,随着时间窗口递增
    HighestQCBlock: 本地最高的N-f PrepareVote区块
    ProposalIndex: 提议人的索引号
    ValidatorIndex: 验证人的索引号
    PrepareBlock: 提议的区块消息,主要包含区块(Block),提议人索引号
    PrepareVote: 验证人对提议区块的Prepare投票,每个验证人需要执行区块后才发送PrepareVote。主要包含ViewNumber,区块hash,区块高度,验证人索引号(ValidatorIndex)
    ViewChange: 当时间窗口超时,提议人的区块没有都收集到N-f PrepareVote,则会向下一个提议人发送ViewChange。ViewChange包含提议人索引号(ValidatorIndex),最高确认区块(HighestQCBlock)
    锁(Lock): 对指定块高进行锁定
    Timeout: 超时(时间窗口到期可以看作提议人的超时时间)
    法定: 最大被允许
    同一个View: 两个View的ViewNumber相等,可以成为同一个View

    BLS签名

    目前业界采用的聚合签名方案主要是BLS聚合签名。BLS聚合签名是在BLS签名方案基础上的扩展方案。Boneh-Lynn-Shacham(BLS)签名方案是Dan Boneh,Ben Lynn, Hovav Shacham[10]于2001年提出的。BLS签名目前在许多区块链项目如Dfifinity、fifilecoin、 Libra中都得到了运用。BLS聚合签名可以把多个签名简化为1个聚合签名,对于提高BFT共识协议中的通信效率至关重要。

    值得注意的是,BLS聚合签名的方法是有漏洞的。一种称为rogue public key的攻击可以使得攻击者有机会在获得其他签名者的公钥和标准BLS签名信息之后,能够操纵聚合签名的输出结果。

    对这个攻击的一种最直接的防御措施是,参与BLS聚合签名的人都需要先证明各自确实掌握了BLS私钥信息,并事先注册。这一过程可以通过使用一种简单高效的零知识证明技术(Schnorr非交互式零知识证明协议)完成。参与者在进行聚合签名之前,需要给出零知识证明,证明其持有公钥信息的同时,确实掌握了该公钥对应的私钥信息。

    CBFT协议流程

    正常流程

    在这里插入图片描述

    1. 提议人在成功进入到新的View后,会连续产生多个区块,将消息PrepareBlock广播给验证人。

    2. 逐个验证区块:验证人校验签名和时间窗口,执行区块,成功后产生PrepareVote<ViewNumber,BlockHash, BlockNumber>。当PrepareVote对应的父区块收集到N-f个PrepareVote时,使用BLS 将N-f 个PrepareVote的个体签名聚合成一个聚合签名,并将当前PrepareVote进行广播。我们将N-f个PrepareVote 简化为prepareQC(quorum certificate) 。

    3. 当节点在当前view内最后一个区块收到prepareQC,则会进入到新的view开始下一轮投票。

    为了更安全的投票,投票必须符合以下规则:

    · 区块执行后才能进行投票
    · 诚实的节点只能对当前View提议的区块进行投票
    · 诚实的节点当View超时后不能再进行投票,也不接收当前View的投票
    · 在同一个View内,相同高度的两个区块只能投其中一个
    · 当对Block(n+1)进行投票时,Block(n)需达到prepareQC

    ViewChange流程

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    假设每个时间窗口最多允许产生n个区块,viewchange流程如下:

    1. 如果在时间窗口内,收到第n块的prepareQC,则更新本地view+1,进入新的正常流程,这种情况下如果是新提议人达成n的QC,则开始广播第一个区块,如图4所示,高度为BlockNumber(n)+1 ,并会携带n 区块的prepareQC。

    2. 如果时间窗口过期,节点首先会拒绝对当前提议人的区块产生新的投票,同时没有收到第n块的prepareQC,则发送ViewChange<ViewNumber, HighestQCBlock>消息,如图5所示。

    3. 下一个时间窗口的提议人收到 N-f 个ViewChange消息(我们将N-f 个ViewChange 消息简称为 viewchangeQC )之后,使用BLS签名聚合成一个QC签名,然后更新本地ViewNumber+1,由于采用两轮投票锁定区块的规则,新提议人可以简单地从收到的N-f个viewchange消息中选择HighestQCBlock,将新的区块序号定为 HighestQCBlock+1,如图6所示,然后广播第一个区块给各验证人节点,并携带HighestQCBlock的QC签名和viewchange的QC签名。

    4. 各验证人节点会根据收到的HighestQCBlock+1序号开始新一轮共识。

    区块确认

    Pipelining流程

    在传统BFT(PBFT, Tendermint)中,每个区块通常都需要经历明确的Pre-Commit 和 Commit阶段才最终确认:

    · Pre-Commit: 当节点收到N-f个Prepare投票时会广播Pre-Commit,Pre-Commit可以看作对Prepare阶段的确认。
    · Commit: 当收到N-f个Pre-Commit投票时,表明所有节点对指定消息达成一致,提交到本地磁盘。

    根据以上介绍,CBFT中有类似Prepare和ViewChange两个阶段,每个区块只有Prepare投票,没有明确的Pre-Commit和Commit阶段,如何达到区块的确认呢?CBFT可看作Pipeline版本的BFT,每个prepareQC都是对前面区块更高阶段的确认。
    在这里插入图片描述
    如图7所示prepareQC(2)作为Block(1)的Pre-Commit阶段,prepareQC(3)作为Block(1)的Commit阶段,Block(2)的Pre-Commit阶段。

    因此在CBFT中,只有两种消息类型:prepare消息和view-change消息,每个消息的QC均采用聚合签名方式验证。

    区块重组

    假设每个view能允许产生n个区块,当前view Vi 时间窗口超时,view切换到Vi+1,此时Vi 产生的区块只有部分得到QC,部分区块进行重组,重组规则如下:

    · Pre-Commit状态的区块被锁定,不能被重组,即如果当前节点在高度h上有Pre-Commit状态的区块,当前节点不能在高度h产生新的区块,也不能在高度h对其他区块投票

    · Prepare状态的区块可以被重组,即如果当前节点在高度h上有Prepare状态的区块,当前节点可以在高度h产生新的区块,或者在高度h对其他区块投票(只允许对更高viewnumber的区块投票)

    验证人替换机制

    · CBFT共识中,每250个区块(称为一个 Epoch)就会更新验证人集合,更新规则如下:
    新验证人可能由于网络连接或区块不同步等原因不能参与共识,因此我们每次替换不超过8个节点,如果候选验证人不足8个,替· 换的数量为候选验证人的总数。
    · 使用VRF从候选验证人中随机选出新的验证人。

    容错恢复(WAL)机制

    CBFT共识提供了容错恢复机制,也就是WAL模块。该模块不属于严格意义上的预写日志系统,但是借鉴了相关思想,在验证人共识过程中将还未落链区块的共识状态和当前View的共识消息从内存分别持久化到本地数据库和本地文件。在系统crash或者机器掉电重启之后通过磁盘日志数据迅速恢复共识状态。

    这里简要介绍一下主要的原理:

    · 区块、viewChange在各验证人间达成共识需要经历验证、投票等阶段,某个区块最终落链前与该区块相关的共识状态、消息都记录在内存中。节点重启也只是需要恢复这部分还未落链区块的内存数据,因此checkpoint恢复点也就是当前blockchain的 currentBlock

    · 链式投票可得,每一区块的投票都是对前一区块的确认,达到第三级即达到区块的Commit阶段,因此3-chain区块的 prepareQC状态在共识中至关重要,必须保证在重启后恢复,这部分数据存储至 db

    · 共识消息只保留最近一轮view相关的,这部分数据存储至文件

    区块同步机制

    由于CBFT共识的异步并行性,导致最新的区块存储在内存中,并且区块高度有3种高度:最高逻辑区块高度、最高确认区块高度和写入磁盘区块高度,并且三种高度依次递减。因此CBFT中的区块同步机制也在已有的PlatON-P2P的基础上作了适配,调整了区块高度的获取方式。这里概要介绍区块同步机制如下:

    · 新加入节点通过PlatON-P2P利用快速同步或全同步更新至主网高度
    · 共识节点利用CBFT-P2P的心跳机制与其它节点保持块高一致
    · 共识节点区块落后时,会主动减少通信量,全力处理区块同步
    · 同步机制使用BLS签名来减少网络同步消息量

    CBFT分析

    基本规则定义

    为方便对CBFT的安全性和活跃进行分析 ,我们定义CBFT的几条基本规则。

    K-Chain 规则

    对于一条链,满足以下条件:

    B(0)<-C(0)<-…<-B(k-1)<-C(k-1)

    我们将其定义为K-Chain,其中B为Block, C为B的prepareQC。我们可以看到当达到3-Chain时如:B0<-C0<-B1<-C1<-B2<-C2,B0达到Commit状态。

    Lock-Block规则

    节点a中, 当区块n收到区块n之后的2次prepareQC,则区块n定义为Lock-Block(a)。可以观察到,当Lock-Block(a) = B0时,B0达到2-Chain, 如B0<-C0<-B1<-C1。

    Unlock-Block规则

    假设Lock-Block(a)为n,当n的子区块n+1达到2次prepareQC,则Lock-Block(a)为n+1。可以观察到,当Lock-Block(a) = B0时,B0达到2-Chain, 如B0<-C0<-B1<-C1-B2,当B0 Unlock-Block时,B0达到3-Chain,如B0<-C0<-B1<-C1<-B2<-C2。

    Previous-Block规则

    形如 Block(B)<-prepareQC(B)<-Block(B’),我们将Block(B)定义为Block(B’)的Previous-Block,则可表示为Previous-Block(B’) = Block(B)。

    由Lock-Block与Previous-Block规则可知:

    在节点a中,形如B<-C<-B’<-C’<-B’’ , Previous-Block(B’’) > Lock-Block(a)

    Commit 规则

    当区块n,收到区块n之后的3次prepareQC,则区块n被Commit。可以观察到,当B0被Commit时,B0达到3-Chain,如B0<-C0<-B1<-C1<-B2<-C2。

    安全性(safety)证明

    1) 不存在同一个View中有两个相同高度区块都能收到足够多投票

    证明: 假设N=3f+1为节点总数,f为拜占庭节点最大数量,那么当收到2f+1投票为足够多投票。因两个区块都收到至少2f+1,投票总量至少为 2(2f+1) = N+f+1,能看到至少有f+1对两个区块投了票,与f个拜占庭节点假设矛盾。

    2) 对于3-Chain来说,B0<-C0<-B1<-C1<-B2<-C2, ViewNumber(B2) >= ViewNumber(B0)。那么存在Block(B),当ViewNumber(B) > ViewNumber(B2),则Previous_Block(B) > B0。

    证明: 对于正常诚实节点(给区块B2,B投过票)来说, 那么节点至少可以看到B0<-C0<-B1<-C1<-B2, 也就是Lock-Block最小为Lock-Block(B0)。因为ViewNumber(B) > ViewNumber(B2),则根据ViewChange确认规则,ViewNumber(B)的第一个区块不小于B1,则Previous_Block(B) > B0

    3) 假设节点n的Lock-Block(n) = B,节点m的Lock-Block(m) = B’,如果Number(B) = Number(B’), 则Hash(B) = Hash(B’)

    证明: 由上面Lock-Block规则可知,存在2种Lock-Block场景,第一种情况两个QC在同一View内,则由1可知不存在B’和B同时收到足够多投票。第二种情况,出现B与B’分属不同View,且都收到prepareQC(B), prepareQC(B’)。假设ViewNumber(B’) > ViewNumber(B),那么根据结论2,Previous_Block(B’) > B,与假设矛盾。

    4) 在Commit阶段不会有两个相同高度不同块Hash被Commit

    证明: 由3可知,如果Number(B) = Number(B’),不存在B,B’‘同时被Lock-Block。则可推不存在Commit(B),Commit(B’)都被提交。

    活性(liveness)证明

    假设节点间网络最大延时为T,执行区块为S

    1)不存在时间窗口永远小于time(prepareQC)*2时间

    证明: 根据实际网络状况,合理调整实际窗口大小,可以保证时间窗口内至少达成2次QC,则时间窗口至少为 2S+4T

    2) ViewNumber可以达成一致,并且递增

    证明:ViewChange达成一致最少需要T,由结论1可以保证ViewChange可以达成一致,为那么ViewNumber可以进行递增切换

    3) Lock-Block高度永远递增

    证明: 假设ViewNumber为n,n+1, 由安全证明(2),可以保证ViewNumber(n+1)的第一个区块Previous-Block至少为Lock-Block(View(n)),又由于活证明(1),至少有两次prepareQC,可以得到两个View锁定高度的关系,Lock-Block(View(n+1)) >= Lock-Block(View(n))+1

    通信复杂度分析

    · PBFT:网状网络拓扑,采用二阶段投票协议,消息达到prepared状态即锁定,有单独的视图切换流程,正常流程通信复杂度为O(n2),视图切换流程通信复杂度为O(n3)。

    · Tendermint:网状网络拓扑,采用二阶段投票协议, 消息达到prepared状态即锁定,视图切换流程和正常流程合并,通信复杂度为O(n2)。

    · Hotstuff:星状网络拓扑,采用三阶段投票协议,消息达到pre-commited状态即锁定,视图切换流程和正常流程合并, 通信复杂度为O(n)。

    · CBFT:网状网络拓扑,采用三阶段投票协议,消息达到pre-commited状态即锁定,自适配视图切换流程,通信复杂度为O(n2)。

    回顾与总结

    本文讨论了目前常见的BFT类共识算法,提出了一种可以更适合公网环境的CBFT协议,可以在满足安全性和活性的前提下,大大提高区块出块确认速度,满足区块链当下越来越高的共识速度需求。

    参考文献

    [1] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,”J. ACM, 1985.

    [2] L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), 1982.

    [3] M. Castro and B. Liskov. Practical byzantine fault tolerance. In OSDI,1999.

    [4] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.

    [5] TEAM T Z. Zilliqa TechnicalWhitepaper[J]. Zilliqa, 2017: 1–8.

    [6] Guy Golan Gueta, Ittai Abraham, Shelly Grossman, Dahlia Malkhi, Benny Pinkas, Michael K. Reiter, Dragos-Adrian Seredinschi, Orr Tamir, Alin Tomescu,“a Scalable and Decentralized Trust Infrastructure”,2018.

    [7] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.

    [8] M. Yin, D. Malkhi, M. K. Reiterand, G. G. Gueta, and I. Abraham, “HotStuff: BFT consensus in the lens of blockchain,” 2019.

    [9] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.

    [10] Dan Boneh, Manu Drijvers, Gregory Neven. “BLS Multi-Signatures With Public-Key Aggregation”, 2018.

    展开全文
  • Thunder 共识协议

    2018-06-28 18:57:29
    本白皮书将介绍 Thunder 共识协议,这是一种新的 可证安全 的共识协议,克服了传统区块链的两个主要瓶颈:吞吐量和确认时间。更确切地说,新 Thunder 共识协议实现了高吞吐量和快速确认(通常情况下在两个网络往返内...
  • 自从基于工作量证明(PoW)的比特币于2008年问世以来,分布式分类帐技术已得到广泛的... 在本文中,我们将回顾分布式分类账技术的不同共识协议及其实现。 我们还将回顾它们的特性,概念和类似工作,然后进行简要分析。
  • BFT类共识协议概览与分析实测

    千次阅读 2019-05-16 18:22:23
    本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览: 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等; 针对拜占庭错误场景优化的,包括Aardvark、Primer等等; 为公链应用而优化的协议,...

    摘要

    本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览:

    • 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等;
    • 针对拜占庭错误场景优化的,包括Aardvark、Primer等等;
    • 为公链应用而优化的协议,包括DPoS+BFT、Zilliqa等等。

    本文还选用PBFT、Zyzzyva、Zilliqa协议,编写程序进行实测,主要得到以下结果及技术指导建议:

    • Zyzzyva和Zilliqa等协议的网络通讯量确实比PBFT降低很多;
    • 调整PBFT检查点周期对性能没有太大影响;而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间,不过同时也会加大消息量对网络造成压力;
    • Zyzzyva在其客户端足够的情况下,增加批量数会对吞吐量和共识时间等性能指标均有较大提升;
    • 虽然增加批量数对Zilliqa等协议都有促进效果,但这也会增加带宽占用。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。

    目录

    1. 引言
    2. 主要结论
    3. 共识问题及BFT协议简介
     3.1 一致性问题及原理
     3.2 BFT共识原理及流程简介
     3.3 技术思路分析换手率
    4. BFT类共识概览
     4.1 针对无拜占庭错误场景进行优化
     4.2 很对拜占庭错误场景进行优化
     4.3 为公链应用优化
    5. 实测对比
     5.1 测试方案介绍
     5.2 场景1:节点均正常的横向比较
     5.3 场景2:节点异常时的横向比较
     5.4 场景3:PBFT测试研究
     5.5 场景4:Zyzzyva测试研究
     5.6 场景5:Zilliqa测试研究
    6. 参考资料


    1. 引言

    共识协议被许多人视为是区块链项目的核心。无论是对区块链平台的交易处理能力、扩展性影响还是对通证经济的激励模型设计,共识协议都会产生很大影响。

    共识协议从大的方面可分为自比特币诞生以来产生的PoW等中本聪共识协议和拜占庭容错(BFT)类共识协议这两大类协议。其中,在计算机科学的分布式系统研究领域已较多研究的BFT类共识协议近年来被越来越多的应用于联盟链平台。与此同时,也有越来越多的研发工作尝试将BFT应用于公链平台。

    我们在本文中对BFT类协议进行了综述性概览分析,并从改进思路上将现有BFT类共识协议分为3大类:针对无拜占庭错误场景优化的协议、针对拜占庭错误场景优化的协议以及为公链应用而优化的协议;另外选用了PBFT、Zyzzyva、Zilliqa协议,编写程序并运行后得到实测对比结果,对共识协议的具体设计提供一些技术性指导建议。

    2. 主要结论

    经过研究与测试分析,我们得到以下主要结论及技术建议:

    • Zyzzyva和Zilliqa等协议的网络通讯量确实比PBFT降低很多;
    • 对PBFT,调整检查点周期对性能没有太大影响;而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间,不过同时也会加大消息量对网络造成压力;
    • Zyzzyva在其客户端足够的情况下,增加批量数会对吞吐量和共识时间等性能指标均有较大提升;
    • 虽然增加批量数对Zilliqa等协议都有促进效果,但网络中消息量也会增加。在设计共识协议时应综合考虑性能目标与网络带宽等实际情况。

    3. 共识问题及BFT协议简介

    3.1. 一致性问题及原理

    计算机世界早已从“单机版”进入了“大型多人在线”的时代,区块链的诞生与发展更是让这一特性得到了充分的体现。这个过程中不可避免的产生了多个计算机之间如何达成一致的问题。常见问题包括:

    表 1 常见网络服务器错误[1]

    在已经大规模投入使用中的分布式数据库系统环境中,有可能存在很多的宕机错误。根据CAP原理[2],Paxos和Raft协议被设计为在牺牲一定可用性的情况下,解决在节点服务器可能宕机问题的协议[3]。

    然而这些协议在区块链领域内还不能直接使用,因为还有其他更多在区块链领域内可能出现的错误。在表1中这种任意类型错误都可能发生的场景中,服务器有可能产生原本不应该输出的内容,系统要做好最坏情况的准备。例如,当一个服务器向不同的服务器发送截然相反的消息时,那么仅可处理宕机错误Paxos协议就无能为力了。

    这种类型错误,也被称为拜占庭错误,最早由Pease和Lamport在上世纪80年代通过拜占庭将军问题进行描述和分析[4][5]。

    因此相较于分布式数据库,区块链的对于一致性问题的设计和实现要更为复杂,这也是为什么区块链不只是一个简单的分布式数据库的原因之一。

    3.2 BFT共识原理及流程简介

    Lamport等人在其经典论文[4]中除了提出拜占庭将军问题外,也提供了两种解决办法[6][7]。

    第一种为“口头消息”的OM(m)协议,即除了链路上可使用加密安全保障外,不允许使用任何的加密算法。该协议需要两两之间递归的传递大量消息,因此消息复杂度很高,为指数级,不太具有可实际操作性。但这一算法仍有其很高的价值,首先是为“实用拜占庭容错”(Practical Byzantine Fault Tolerance)这一多项式级别复杂度协议的诞生做了一个铺垫;另外,其1/3容错节点数量也被证明为是该类算法的理论上限。

    而第二种为“加密消息”的SM(m)协议。该算法与第一种不同之处在于使用签名算法。每个节点都能产生一个不可伪造的签名,并可由其他节点进行验证。当收到消息后,节点会通过签名来判断及验证该消息是否已收到过。最终不再收到消息后,消息共识结束。它同样假设是在一个同步网络内进行;另外,签名身份体系信息需要在网络运行前确定,较难实现扩展。Vitalik近期在其博客上发布了一篇名为《一个99%容错共识的指南》[8]就是根据这一协议在区块链实际场景中所作的适应性改造探索[9]。

    3.3 技术思路分析

    与从比特币系统中衍生出的中本聪共识不同,BFT类协议基于节点间传递消息对网络中提案达成共识。因此一般来说消息复杂度较高,而且节点的加入和退出过程需要进行特别处理,但一旦达成共识则形成确定性结果,而不是中本聪共识的概率上的最终一致。

    因此基于以上特性,BFT类共识目前在金融场景以及联盟链场景中应用的更多。不过随着研究的探索推进,一些可在公有链场景下使用的BFT共识也正在不断研发出来。

    4. BFT类共识概览

    我们在已有BFT类共识分类[10][11]的基础上,继续对目前BFT协议进行了梳理。因为BFT协议中的无论是口头协议还是书面协议都不够“实用”,很难在实际场景中直接运用。因此后来学术界和业界对BFT协议有了大量的改进。按照改进思路的不同,这些协议主要可分为以下3大类方向:

    • 针对无拜占庭错误场景进行优化
    • 针对拜占庭错误场景进行优化
    • 为公链应用而做的优化

    4.1 针对无拜占庭错误场景进行优化

    此场景假设大部分情况下,网络中的节点运行都正常,拜占庭错误并不经常出现,因此可对这种节点均正常情况下的共识机制进行简化或优化。

    下面我们根据不同的优化方法,对这些协议进行分项介绍。

    4.1.1. 基于协约的方法

    对BFT协议最为经典的改进主要是以PBFT为代表的基于节点协约一致(Agreement)的方法。该类协议通常会有一个主节点作为网络中的枢轴。比其他节点相比,主节点在共识过程中会发出最主要的作用,但通常也会成为系统性能的瓶颈。因为主节点需要将客户端发来的请求排序后发送给所有的备节点。所有节点通过互相通信后达成一致,实现安全性(Safety);大多数协议中所有节点也会向客户端回复响应,实现活性(Liveness)。该类协议通常需要3f+1个节点来实现对f个拜占庭节点的容错。

    实用拜占庭容错Practical Byzantine Fault Tolerance. 简称PBFT)[12]是早期对其进行的改进,将BFT的消息复杂度从指数级降低为 级别,即具备了可实际使用的条件。

    图 1 正常情况下的PBFT消息传播过程[12]

    PBFT协议将共识过程分为了5个阶段(如果不算与客户端交互的阶段,则可视为3个阶段):

    • Request阶段是客户端发送信息;
    • 在Pre-prepare阶段,主节点接到消息对其签名并分配一个唯一的序号n并将该消息发送给其他节点;
    • Prepare阶段:所有备份节点收到主节点发来的PRE-PREPARE消息后,将一个包含当前视图号v、消息序号n、消息摘要的PREPARE信息发给所有其他节点。如果节点收到了2f个以上的PREPARE消息后则进入到下一阶段并且该消息处于Prepared状态;
    • Commit阶段:每个节点广播一个保护当前视图号v、消息序号n的COMMIT消息。当节点收到2f个相同的COMMIT消息并且小于序号n的消息都已被执行,那么当前消息会被执行并被标记为Committed状态;
    • Reply阶段:所有节点将执行结果返回给客户端。

    除了以上阶段流程外,协议运行过程中还涉及到几个重要概念:

    • 水位:每个节点在运行协议时会设置一个处理消息的窗口,消息序号在这个区间内的时候才会被处理,例如最小序号设为h、最大序号为H;
    • 检查点(Checkpoint):在运行提交过程中所有已处于已准备好(Prepared)和已提交状态(Committed)的信息会被记录在内存中。节点会定期(每执行k个请求后)记录一个稳定的检查点并截断记录,即每执行k个请求后,会将水位h和H提高k个单位;
    • 视图切换(View Change):但是当节点发现对某个消息的等待超过一定时间后,则认为是主节点失效,会发送视图切换(VIEW-CHANGE)消息并开始视图切换的过程;
    • 批量(Batch):实际执行中会采用的一些优化改进技术,例如批量方式,即实际程序并不是对单个提交来每次运行协议,而是会在以集合形式同时在网络中处理,并通过设置批量大小(Batch Size)的方式来控制处理消息的数量。

    在设置了以上运行机制后,尽管消息复杂度仍然较高,PBFT已具备了实际运行的可行性。之后的许多BFT类协议均在PBFT协议基础上进行改进,并将PBFT作为研究对比的基准对象。

    Chain协议。Chain协议[13]采用了一个和其名称很相似的链条式传播路径[14]。从主节点开始,每一次传播时即加入该节点的摘要信息。当客户端较多时,Chain通常会比PBFT、Zyzzyva等吞吐量更高。

    图 2 Chain消息传播过程[10]

    Ring协议。Ring协议[15]使用环形拓扑方式来传递消息,即每个节点都有消息的上一个发送者和下一个接收者,以此方式来降低对部分节点分配更多工作而形成的性能瓶颈问题。对有无错误的不同场景,Ring分别采用两种运行模式:快速模式(Fast Mode)和弹性模式(Resilient Mode),并采用ABSTRACT框架进行切换[14]。

    图 3 快速模式下Ring消息传播过程[15]

    BFT-SMaRt协议。BFT-SMaRt[16]与PBFT、UpRight[17]类似,但增强了可靠性、模块化程度、同时还提供了灵活的编程接口。

    4.1.2 基于Quorum的方法

    Quorum机制是一种分布式系统中常用的机制,用来保证数据冗余和最终一致性的投票算法。其主要思想来源于抽屉原理,常用于分布式系统的读写访问控制[18]。

    该类共识协议不需要节点间相互通讯,而是由节点直接执行并响应客户端发来的请求。当受到足够数量的响应后,客户端才会将结果最终提交。但是当出现拜占庭错误场景时,通常会花费较大的代价来解决。另外,由于缺少对请求的排序机制,Quorum方法无法处理有竞争(contention)的情况。

    Q/U协议。Q/U协议(Query/Update)[19]是一个典型的基于Quorum的协议。Q/U没有主节点来为请求排序,而是由客户端直接向节点发送请求并由节点反馈结果。它需要5f+1个节点来对f个拜占庭节点容错。

    HQ协议(Hybrid Quorum)[20]是另一个较为早期和著名的共识协议。正如其名称,HQ综合参考并优化了Q/U协议和PBFT协议:只需要3f+1个节点进行容错,并针对没有竞争的情况简化了PBFT节点间通讯。当没有竞争情况下,共识主要分为两个阶段:第一阶段是客户端发送请求并收集节点的状态信息;当收到结果表明2f+1个节点状态相同且可以执行请求后,开始第二阶段信息发送、由节点执行请求。而如果发现有竞争,则采用类似PBFT的解决过程,性能也退化为和PBFT类似。

    图 4 HQ的消息传播模式[20]

    Quorum协议也是基于Quorum机制的一个共识协议[14],主要没有客户端竞争的非异步网络而进行设计,只需要3f+1个节点进行拜占庭容错。当没有错误产生时,Quorum协议的传播路径和Q/U类似,节点独立执行请求并自己维护一个执行历史记录。当客户端数量较少时,其吞吐量和延迟等性能指标均比其他BFT类共识更好。但其缺点也和Q/U类似,无法处理客户端有竞争的情况[10]。

    4.1.3 基于Speculation的方法

    在这类协议中,节点不需要通过需要消耗大量系统代价的3阶段提交过程即可响应客户端的请求。采用了更乐观的策略,节点同意由主节点发出的排序请求并给客户端返回结果。由客户端而不是节点来负责考虑一致性问题。如果发现不一致问题,由客户端负责通知节点回滚至一致状态。

    Zyzzyva协议。Zyzzyva是该类中最典型的一个协议[21]。它需要3f+1个节点进行拜占庭容错。与基于Agreement的协议类似,Zyzzyva中的主节点也是将客户端发来的请求排序后转发其他节点。每个节点根据自身历史记录来执行请求并将结果反馈给客户端。客户端根据节点返回的一致性结果数量分别执行不同的动作。

    在没有错误的场景下,Zyzzyva表现比PBFT和Q/U等协议要好;但是当有错误时,因为要涉及到和PBFT类似的view change过程,其性能也会急剧下降。

    图 5 Zyzzyva的消息传播模式[21]

    Zeno协议。Zeno协议[22]在Zyzzyva基础上进行修改,将原有的强一致性替换为一个较弱的最终一致性保证。它允许客户端偶尔忽略其他更新,但是当网络不稳定时,所有节点的状态需要进行合并以达成一致。

    ZZ协议。ZZ协议[23]同样基于Speculation机制。因其还采用了分离处理的机制,也可将其归为“分离处理一致性与执行请求的阶段”的类别,我们将在后续章节继续介绍。

    4.1.4 基于客户端的方法

    基于客户端的方法通过避免节点间通信的方式,来避免异常节点对正常节点的攻击、误导或延迟。协议完全依赖于这些客户端的正确性,假设客户端都没有异常、是诚实且在宕机时会被外部所感知的。

    OBFT(Obfuscated BFT)协议[24]是这一类协议的典型代表。它需要3f+1个节点进行容错,但与其他很多BFT协议涉及到节点间通讯不同,OBFT协议中的节点完全不需要关注其他节点并只与客户端联系,因此避免了恶意节点干扰其他正常从而影响系统性能的问题,不过这也带来了一个较强的假设:必须完全信任客户端不会作恶。因此该类协议都存在着较难在实际场景中进行应用的问题。

    图 6 OBFT的消息传播模式[24]

    4.1.5 基于可信组件的方法

    因为FLP不可能性原理(即使网络通讯可靠也无法在任何场景下都能达到共识[25]),一些协议并不使用传统的超时等机制而是基于外部的可信组件进行设计。这些组件也需要被认为是无拜占庭错误的,但允许存在宕机等临时性无法提供服务的情况[11]。基于以上条件,该类协议可以将容错节点数量从3f+1将为2f+1。

    例如,CheapBFT协议[26]。需要基于一个叫做CASH的FPGA可信设备,从而降低正常情况下协议对于资源的使用。

    4.1.6 基于拜占庭锁的方法

    拜占庭锁是拜占庭协议的扩展,通过利用IO绝大多数时间里不会出现竞争的特性来达到降低服务器响应时间、提高吞吐量与扩展性的效果。

    这种方法最早由Zzyzx协议[27]提出,包括加锁和解锁两个部分。加解锁过程均基于现有拜占庭协议达成对客户端授权的一致。当授权完成,则获得锁的客户端可直接进行操作,从而去掉了主节点排序、节点间通讯等操作,从而大幅度提高吞吐量。但当有多个客户端需要频繁切换时,其性能也会大幅下降,因此该协议较为适用于客户端不会频繁发生变化的情况下。

    4.1.7 基于分离一致性与执行请求的方法

    还有一类改进方法是将共识与执行提交的过程分开,因为执行客户端请求只需要f+1个(当没有拜占庭节点或者客户端可验证结果正确性时)或2f+1个节点(当有可能存在拜占庭节点且客户端不可验证正确性时),因此可将协议的执行分为2个部分,一部分节点负责一致性共识协议,而另一部分负责执行提交,从而提高吞吐量。

    ZZ协议,通过虚拟化技术[23]把节点均正常场景下的执行所需节点数量从2f+1降为f+1个。在没有错误场景时,只通过f+1个节点来执行请求,其余服务器在休息状态;而当执行请求的节点发生错误时,客户端通过虚拟化技术快速启动更多的节点来执行[11]。

    ODRC协议也是将执行节点数量将为了f+1,但与ZZ协议不同,它并没有采用额外的虚拟化等技术,而是在BFT协议过程中的节点达成一致后、执行请求前增加了一个选择执行节点的阶段。该阶段根据当前系统状态,选择指定数量的节点执行请求[11]。

    4.2 针对拜占庭错误场景进行优化

    上面介绍的一类协议均是针对没有错误的场景对BFT协议进行简化而设计,因此当遇到拜占庭错误时,这类协议的性能一般都会下降比较多,甚至很难保证系统活性。而另一类协议的改进目的是为了有效对拜占庭行为(甚至是一些罕见的行为)进行容错,降低系统在有无拜占庭错误这两种场景下的表现差异。主要有以下几个比较典型的协议。

    Aardvark协议。Aardvark协议[28]的通讯过程与PBFT类似,但对许多可能的错误场景设计了适应性机制以保证系统的安全性和活性。这些适应性机制包括:对客户端采用混合签名等机制来防止客户端作恶;更为积极主动的触发view change过程以避免主节点有拜占庭行为;为每个节点设计3f+1个网络接口(其中1个用于其与客户端通信,其余3f个用于节点间通讯),以此隔离网络通道来防止流量攻击。

    Prime协议。因为PBFT协议中当主节点作恶的view change过程对性能的影响较大,即便主节点不进行任何主动作恶,只要在处理排序过程中刻意增加延迟就可以降低系统整体性能表现。Prime协议[29]针对此情况进行了改进,在PBFT过程前增加了一个预排序的阶段,包括PO Request、PO ACK、PO ARU等阶段。通过这种分析主节点排序时间的方式,使得所有节点来监控网络表现。因此主节点必须及时将消息发送给其他节点以避免被替换掉。因为引入了额外的阶段,Prime在正常场景中的性能要比PBFT等协议要低;但在存在错误场景中其表现要比其他协议要好。

    图 7 Prime消息传播模式[10]

    Spinning协议。Spinning协议[30]在PBFT协议的基础上,设计用来减轻更换主节点的代价。在正常场景中的,Spinning通讯过程与PBFT相同。不过它没有view change过程,而是通过合并操作的方式来收集不同节点信息来决定之前视图中的操作是否应在新视图中执行。

    RBFT协议。Redundant-BFT协议[31]利用目前所流行的多核技术来保障鲁棒性。该协议采用与PBFT类似的通讯过程,但在Pre-prepare阶段前增加了一个Propagate阶段。客户端首先将消息发送给f+1个节点,这些节点在Propagate阶段相互传递消息以此来保证客户端请求会被所有正常节点接收到。RBFT执行f+1个同一个协议的多个实例,其中每个实例都对应一个在不同物理机器上运行的主节点,不过只有被主实例所排序的请求才会被有效执行。备份实例运行的意义主要在于监测运行性能:当发现主实例运行缓慢时,备份实例将触发view change过程选择出一个新的主实例。

    图 8 RBFT的消息传播模式[31]

    4.3 为公链应用优化

    传统PBFT及类似协议,其自身的特性导致应用场景有较多限制,例如消息复杂度随节点数成平方级别上升、主节点容易成为系统性能瓶颈、节点列表需要提前固定且节点间相互已知。所以在分布式账本系统中,更多应用于联盟链或私有链场景中。

    为了适应公有链场景中的大规模扩展需求,有不少项目进行了有益尝试,具体方式可主要包括与公链共识结合以及基于密码学机制等两大类方式。

    4.3.1 与中本聪共识结合

    为了在公有链中利用BFT类共识的结果可快速得到最终确认等优点,一类做法是将BFT类协议与中本聪协议进行结合,以此来取长补短,将BFT类共识引入应用到公有链的业务场景中。

    例如,Elaine Shi等在2017年提出将BFT类共识与中本聪共识结合的办法[32]:通过PoW先选出负责共识的委员会(Commitee);由委员会再进行PBFT过程达成共识并出块[33]。

    DPoS+BFT协议也是类似的思路。该协议是BFT类协议与中本聪协议结合的一个典型代表,被用于BM开发的石墨烯[34]“全家桶”平台,包括BitShares[35]、Steemit[36]、EOS[37]等。通证持有者以投票等方式选出自己支持的“代表”,并由这些代表组成的见证人网络通过BFT的方式进行共识。例如EOS中,用户投票产生21个可出块的“超级节点”,以BFT方式共识后轮流出块,对1/3以下的“超级节点”可以容错。基于该类共识协议的平台性能较高,且不需要竞争挖矿等,但缺点是略微中心化。

    DBFT协议是NEO提出的授权拜占庭容错协议[38],和DPoS+BFT思路有些类似,是一种通过代理投票实现大规模参与的共识协议。通证持有者可通过投票选出他所支持的“代理”,然后代理再通过BFT达成共识。因此它也和DPoS+BFT类似,具有快速、扩展性好等特点,但也同样受到共识节点数量有限、中心化程度太高等质疑。

    Tendermint BFT协议。Cosmos项目提出了名为Tendermint BFT的一种基于BFT的PoS共识协议[39]。它以加权轮询的方式产生验证者集合,由选出的验证者产生共识提议并进行BFT过程。因此它也是一种在半同步网络中使用的确定性算法[40]。

    FBA协议。Stellar使用的恒星共识协议(Stellar Consensus Protocol)的背后是一种联邦拜占庭协议(Federated Byzantine Agreement)。该协议并不是直接把BFT和某一个中本聪共识结合,而是参考了中本聪对比特币的设计理念。该协议实现一个开放式的节点成员列表,任何人都可以加入。网络中的每个节点可自行选择其Quorum,降低对非理性行为的容忍程度,所以其性能和可扩展性都较为突出,但一些拜占庭行为也可能导致分叉等情况发生,因此节点需要花费不少代价去设置其所信任的节点列表。

    还有一些项目在尝试探索把BFT协议引入当前公链平台中,例如Istanbul BFT(IBFT)[41]就是通过引入验证者(validator)并基于Quorum机制运行,并被探索用于当前以太坊平台。

    除了狭义的“区块链”方式外,Hashgraph[42]也可认为是一种BFT类共识与DAG结合的协议。它通过gossip about gossip降低通信量,并且也是异步的BFT协议。

    4.3.2 基于密码学优化

    另一种可运用于公链的思路是利用密码学的方法,包括聚合签名、可验证随机函数、门限签名等,以达到降低BFT类共识的通讯代价、提高共识效率的目的。

    聚合签名

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

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

    Gosig[45]也使用该方法,同时还结合了Algorand以VRF方式选择“Leader”和多轮投票等方法来尽量降低Leader作恶可能性。

    可验证随机函数

    Algorand的BA★协议[46]使用了另一种密码学方法 — — 可验证随机函数(VRF),以加密抽签的形式随机决定“验证者”,并以带有权重的方式来全网共识,可认为是BFT类共识+PoS或PoWeight的架构。投票过程分为两个阶段:第一阶段通过一个分级共识选出“验证者”共识最多的候选区块;第二阶段运行一个二元拜占庭协议(接受出块或产生空块)。执行速度很快,不太容易产生分叉且交易确认时间虽用户数增加变化不大[33]。另外,Algorand通过加密方式隐藏了“领导者”的真实身份,提高了针对Leader攻击的安全性。

    VBFT协议也是使用VRF的一个共识协议[47],由Ontology提出,可认为是PoS+VRF+BFT:在共识协议的各个阶段,分别使用VRF从网络中选出该阶段所需要的节点,例如提案节点、验证节点、确认节点等并完成最终的共识。其中的选择参数是根据PoS来确定。

    门限签名

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

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

    5. 实测对比

    除了进行理论上的归纳总结与分析外,我们选用PBFT、Zyzzyva、Zilliqa协议,编写共识协议的程序进行实测模拟。通过横向与纵向的测试比较,以期得出以上共识协议的技术建议。

    5.1 测试方案介绍

    由于共识协议都需要基于一个实际的应用场景,我们在程序中将节点处理计算的过程设定为一个固定的延时;消息传输采用消息队列方式来实现。程序基于Java 8编写实现。

    因为PBFT、Zilliqa等共识协议在一些实现细节上缺少明确描述,我们在实现程序时进行了以下设定:

    • 节点之间的网络时延在5–10毫秒内;
    • 网络带宽设置为100MB(假设每条请求消息平均100B大小)。

    5.2 场景1:节点均正常的横向比较

    首先在所有节点均为诚实节点的情况下,我们进行多组实测,横向比较PBFT、Zyzzyva、Zilliqa共识协议在不同情况下的协议吞吐量、网络中平均消息量、达成共识总时长等性能指标。

    本场景的第1组测试条件为:

    • 批量大小= 10
    • 水位大小=30
    • 检查点周期=10
    • 客户端数量=1,消息发送间隔=1ms

    横向比较的结果(其中吞吐量和网络平均消息量单位均为消息笔数,下同)如下:

    整体来看,BFT类协议的吞吐量确实均会随着节点数增加而下降(性能降低),当节点数量过多时,很难完成处理。

    对于PBFT协议,可看到其消息量和节点数量确实有平方级的关系(本例中约为 );

    Zyzzyva和Zilliqa的消息量为线性关系,即以上协议的方法确实会降低PBFT消息量大的问题

    由于批量大小会影响网络中处理消息的数量,因此我们在第2组观察批量大小对性能的影响。测试条件为:

    • 节点数=22
    • 水位大小=30
    • 检查点周期=10
    • 客户端数量=1,消息发送间隔=1ms

    从结果可以看出,增加批量大小对吞吐量均有较为明显的提升,但也会增加网络中的消息量。其中,Zilliqa的吞吐量提升最为明显,因为该算法可以在一个单位时间内进行聚合签名并且可以批量验证,即批量大小相当于打包区块的大小。所以当总带宽允许的情况下,Zilliqa算法可以通过增加批量而获取极大的吞吐量。

    PBFT和Zyzzyva提升到一定阶段后在实测中会遇到瓶颈(批量数>30后,吞吐量始终接近1000),原因是本次测试客户端消息间隔导致。如果降低发送间隔或者增加客户端数量均可提高吞吐量。例如,当假设消息可并行处理且没有到达网络带宽瓶颈,增加客户端可得到如下PBFT的性能结果为:

    5.3 场景2:节点异常时的横向比较

    BFT类协议的一个复杂之处在于部分节点存在拜占庭行为情况下的处理,各个协议对不同数量的异常节点,该情况下的效率可能也不一样。

    在本场景中我们设置节点数固定为22个。

    本场景第1组测试设置条件为:

    • 批量大小=10
    • 水位大小=30
    • 检查点周期=10
    • 客户端数量=1

    经过测试PBFT、Zyzzyva、Zilliqa的吞吐量分别为:

    其中,可看到PBFT吞吐量和共识时间都优于Zyzzyva和Zilliqa,是因为本次测试暂忽略了网络消息量增大对消息传播延迟的影响。

    从结果也可看到网络平均消息量会减小,尤其是PBFT的消息量会随着节点增多而降低较快。其原因是当出现拜占庭节点时,作恶节点的消息会被忽略掉;而同时,消息传播和达成共识的时间会相应延长。

    5.4 场景3:PBFT测试研究

    下面的几个场景我们对比PBFT的批量、检查点周期与吞吐量、网络中平均消息量以及达成共识时间等性能表现之间的关系。

    • 节点数=22
    • 水位大小=50

    可以看到,对于PBFT来说,检查点周期调整对性能的影响并没有太大;而调整批量大小则会较大程度上提高吞吐量指标、缩短共识时间,不过同时也会加大消息量对网络造成压力。

    5.5 场景4:Zyzzyva测试研究

    从上述场景已可看到,调整批量大小会对共识性能产生影响;而Zyzzyva的主节点负责接收各客户端发来的请求,因此在客户端数量不同的情况下,表现可能也会不一样。因此我们针对不同的批量大小和客户端数量进行分析研究。

    从结果可以看到,当批量数较小时,增加客户端数量后,Zyzzyva整体性能并没有太大改观。

    当增大批量后,Zyzzyva的吞吐量提高较为明显;在增加客户端数量后,吞吐量和共识时间均有改观,但在增加一定程度后其表现并不会继续提升。

    另外和PBFT类似,增加客户端数量或增大批量后,Zyzzyva的网络消息也会随之增加。

    5.6 场景5:Zilliqa测试研究

    从场景1的测试中可看出,Zilliqa的Batch可以设置的远比PBFT大从而获得极大的吞吐量,因此与前两个纵向对比测试略有不同,本场景测试着眼点在网络带宽消耗上。在不同Batch下,我们测试研究Zilliqa的消耗情况(以PBFT作为一个基准对比)。

    测试条件为:

    • 节点数=22
    • 检查点周期=10
    • 消息大小=100B

    可以看到,尽管可设置较大的批量数来获得更高的吞吐量,但Zilliqa的最大带宽消耗也会随着批量数而线性增长作为对比,PBFT在批量数到达一定数量后,最大消耗带宽会趋于稳定。因此在实际应用共识协议时,应充分考虑好选用的共识协议以及实际网络带宽情况。

    6. 参考资料

    [1] M. van Steen and A. S. Tanenbaum, Distributed Systems, 3.01. 2017.

    [2] S. Gilbert and N. Lynch, “Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services,” ACM SIGACT News, 2002.

    [3] S. Gilbert and N. Lynch, “Perspectives on the CAP Theorem,” Computer (Long. Beach. Calif)., vol. 45, no. 2, pp. 30–36, 2012.

    [4] L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,” ACM Trans. Program. Lang. Syst., 1982.

    [5] LoomNetwork, “了解区块链的基本(第一部分):拜占庭容错(Byzantine Fault Tolerance),” 2018. [Online]. Available: https://segmentfault.com/a/1190000014009235.

    [6] bangerlee, “[上篇] 大话分布式系统理论基础.” [Online]. Available: https://mp.weixin.qq.com/s/p4PEZPjxJyYXKpkCCdShbw.

    [7] 初夏虎, “拜占庭将军问题深入探讨,” 2015. [Online]. Available: https://www.8btc.com/article/70370.

    [8] V. Buterin, “A Guide to 99% Fault Tolerant Consensus,” 2018. [Online]. Available: https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html.

    [9] 袁煜明 and 胡智威, “【火线视点10】Vitalik的‘99%容错共识算法’解析.”

    [10] D. Gupta, L. Perronne, and S. Bouchenak, “BFT-Bench: Towards a practical evaluation of robustness and effectiveness of BFT protocols,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2016.

    [11] J. FAN, L.-T. YI, and J.-W. SHU, “Research on the Technologies of Byzantine System,” J. Softw., vol. 24, no. 6, pp. 1346–1360, 2014.

    [12] M. Castro and B. Liskov, “Practical byzantine fault tolerance and proactive recovery,” ACM Trans. Comput. Syst., 2002.

    [13] R. van Renesse and F. B. Schneider, “Chain Replication for Supporting High Throughput and Availability,” Proc. 6th Conf. Symp. Opearting Syst. Des. Implement. — Vol. 6, 2004.

    [14] P.-L. Aublin, R. Guerraoui, N. Knežević, V. Quéma, and M. Vukolić, “The Next 700 BFT Protocols,” ACM Trans. Comput. Syst., vol. 32, no. 4, pp. 1–45, 2015.

    [15] R. Guerraoui, N. Knezevic, V. Quema, and M. Vukolic, “Stretching BFT,” 2010.

    [16] A. Bessani, J. Sousa, and E. E. P. Alchieri, “State machine replication for the masses with BFT-SMART,” in Proceedings — 44th Annual IEEE/IFIP International Conference on Dependable Systems and Networks, DSN 2014, 2014.

    [17] A. Clement et al., “Upright cluster services,” in Proceedings of the ACM SIGOPS 22nd symposium on Operating systems principles — SOSP ’09, 2009.

    [18] Wikipedia, “Quorum (distributed computing).” [Online]. Available: https://en.wikipedia.org/wiki/Quorum_(distributed_computing).

    [19] M. Abd-El-Malek, G. R. Ganger, G. R. Goodson, M. K. Reiter, and J. J. Wylie, “Fault-scalable Byzantine fault-tolerant services,” in Proceedings of the twentieth ACM symposium on Operating systems principles — SOSP ’05, 2005.

    [20] B. Bershad, D. ACM Digital Library., B. ACM Special Interest Group in Operating Systems., R. Rodrigues, and L. Shrira, “HQ Replication: A Hybrid Quorum Protocol for Byzantine Fault Tolerance,” Proc. 7th Symp. Oper. Syst. Des. Implement., p. 407, 2006.

    [21] R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong, “Zyzzyva: Speculative Byzantine Fault Tolerance,” Proc. Symp. Oper. Syst. Princ., pp. 45–58, 2007.

    [22] A. Singh, P. Fonseca, and P. Kuznetsov, “Zeno: Eventually Consistent Byzantine-Fault Tolerance.,” Nsdi, pp. 169–184, 2009.

    [23] T. Wood, R. Singh, A. Venkataramani, P. Shenoy, and E. Cecchet, “ZZ and the art of practical BFT execution,” in Proceedings of the sixth conference on Computer systems — EuroSys ’11, 2011.

    [24] A. Shoker, J. P. Bahsoun, and M. Yabandeh, “Improving independence of failures in BFT,” in Proceedings — IEEE 12th International Symposium on Network Computing and Applications, NCA 2013, 2013.

    [25] M. J. Fischer, N. A. Lynch, and M. S. Paterson, “Impossibility of distributed consensus with one faulty process,” J. ACM, 1985.

    [26] R. Kapitza et al., “CheapBFT: Resource-efficient Byzantine Fault Tolerance,” Proc. 7th ACM Eur. Conf. Comput. Syst., 2012.

    [27] J. Hendricks, S. Sinnamohideen, G. R. Ganger, and M. K. Reiter, “Zzyzx: Scalable fault tolerance through Byzantine locking,” in Proceedings of the International Conference on Dependable Systems and Networks, 2010.

    [28] A. Clement, E. Wong, L. Alvisi, M. Dahlin, and M. Marchetti, “Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults,” Symp. A Q. J. Mod. Foreign Lit., 2009.

    [29] Y. Amir, B. Coan, J. Kirsch, and J. Lane, “Prime: Byzantine replication under attack,” IEEE Trans. Dependable Secur. Comput., 2011.

    [30] G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung, “Spin one’s wheels? Byzantine fault tolerance with a spinning primary,” in Proceedings of the IEEE Symposium on Reliable Distributed Systems, 2009.

    [31] P. L. Aublin, S. Ben Mokhtar, and V. Quema, “RBFT: Redundant byzantine fault tolerance,” in Proceedings — International Conference on Distributed Computing Systems, 2013.

    [32] R. Pass and E. Shi, “Hybrid consensus: {Efficient} consensus in the permissionless model,” Leibniz {Int}. {Proc}. {Informatics}, {LIPIcs}, 2017.

    [33] 姚前, 数字货币初探. 中国金融出版社, 2018.

    [34] “Graphene Technical Documentation.” [Online]. Available: http://docs.bitshares.org/.

    [35] “BitShares Whitepapers.” [Online]. Available: http://docs.bitshares.org/bitshares/papers/.

    [36] “Steem Whitepaper.” [Online]. Available: https://steem.io/steem-whitepaper.pdf.

    [37] “EOS.IO Technical White Paper v2.” [Online]. Available: https://github.com/EOSIO/Documentation/blob/master/TechnicalWhitePaper.md.

    [38] NEO, “A Byzantine Fault Tolerance Algorithm for Blockchain.” [Online]. Available: http://docs.neo.org/en-us/basic/consensus/whitepaper.html.

    [39] “Cosmos Whitepaper.” [Online]. Available: https://github.com/cosmos/cosmos/blob/master/WHITEPAPER.md.

    [40] C. Unchained, “Tendermint Explained — Bringing BFT-based PoS to the Public Blockchain Domain.” [Online]. Available: https://blog.cosmos.network/tendermint-explained-bringing-bft-based-pos-to-the-public-blockchain-domain-f22e274a0fdb.

    [41] Z.-C. Lin, “Istanbul BFT (IBFT).” [Online]. Available: https://medium.com/getamis/istanbul-bft-ibft-c2758b7fe6ff.

    [42] H. Hashgraph, “Hedera: A Governing Council & Public Hashgraph Network.” [Online]. Available: https://s3.amazonaws.com/hedera-hashgraph/hh-whitepaper-v1.1-180518.pdf.

    [43] E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford, “Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing,” 2016.

    [44] T. Z. Team, “Zilliqa Technical Whitepaper,” Zilliqa, pp. 1–8, 2017.

    [45] P. Li, G. Wang, X. Chen, and W. Xu, “Gosig: Scalable Byzantine Consensus on Adversarial Wide Area Network for Blockchains,” 2018.

    [46] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling byzantine agreements for cryptocurrencies,” Proc. 26th Symp. Oper. Syst. Princ., 2017.

    [47] “VBFT算法介绍.” [Online]. Available: https://github.com/ontio/documentation/blob/master/vbft-intro/vbft-intro-CN.md.

    [48] A. Miller, Y. Xia, K. Croman, E. Shi, and D. Song, “The Honey Badger of BFT Protocols,” in Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security — CCS’16, 2016.

    [49] Juniway, “Honey Badger of BFT 协议详解.” [Online]. Available: https://www.jianshu.com/p/15d5b6f968d9.

    展开全文
  • 此存储库提供了HotStuff共识协议的2链变体的最小实现。 该代码库被设计为小巧,高效,易于基准测试和修改。 它尚未设计成可以在生产环境中运行,而是使用了真正的加密( ),网络( )和存储( )。 快速开始 ...
  • Casper共识协议

    千次阅读 2018-06-05 08:06:58
    Security-deposit based security and authenticationCasper是一种基于保证金的经济激励共识协议(security-deposit based economic consensus protocol)。协议中的节点,作为“锁定保证金的验证人(bonded validators...

    基于保证金的安全和共识鉴别

    Security-deposit based security and authentication

    Casper是一种基于保证金的经济激励共识协议(security-deposit based economic consensus protocol)。协议中的节点,作为“锁定保证金的验证人(bonded validators)”,必须先缴纳保证金(这一步叫做锁定保证金,"bonding")才可以参与出块和共识形成。Casper共识协议通过对这些保证金的直接控制来约束验证人的行为。具体来说就是,如果一个验证人作出了任何Casper认为“无效”的事情,他的保证金将被罚没,出块和参与共识的权利也会被取消。保证金的引入解决了"nothing at stake",也就是经典POS协议中做坏事的代价很低的问题。现在有了代价,而且被客观证明做错事的验证人将会付出这个代价。


    我们容易发现,只有在验证人当前已缴纳保证金的情况下他的签名才有意义(economically meaningful)。这代表客户端只能依赖他们知道的锁定保证金的验证人的签名。因此当客户端接收和鉴別共识数据时,共识认可的链必须起源于出自当前锁定保证金的验证人的块。在POW协议中共识认可的链则是起源于创世块 - 只要你知道创世块的数据你就可以鉴别出共识认可的链。这里,只要你知道当前锁定保证金的验证人,你就可以鉴别出共识认可的链。不知道当前锁定保证金的验证人列表的客户端必须先通过另外的信道获取这个列表。这个限制通过要求所有人用当前信息鉴别共识解决了“远程攻击(long range attack)”问题。


    验证人列表随着验证人保证金不断的锁定,罚没,解锁而变动。如果客户端离线过长时间,它的验证人列表就会由于过时而不能用来鉴别共识。如果客户端经常在线,则能够与最新的验证人列表保持同步,但问题是在第一次同步之前,客户端还是需要从其他信道获取最新锁定保证金的验证人列表。


    这个“需要从其他信道鉴别共识至少一次”的性质。在我们的上下文中,如果信息可以在协议之内被验证,则可称之为“客观的”;如果信息必须依赖协议外的手段才可验证,则称为“主观的”。在弱主观性共识协议中,分叉选择规则是有状态的,因此客户端必须初始化(有些时候是更新)这个状态才能鉴别共识。在这里,这个状态被用来辨认当前锁定保证金的验证人(更精确的说法可能是当前验证人列表的密码学哈希)。



    下注共识

    Gambling on Consensus

    Casper要求验证人将保证金中的大部分对共识结果进行下注。而共识结果又通过验证人的下注情况形成:验证人必须猜测其他人会赌哪个块胜出,同时也下注这个块。如果赌对了,他们就可以拿回保证金外加交易费用,也许还会有一些新发的货币;如果下注没有迅速达成一致,他们只能拿回部分保证金。因此数个回合之后验证人的下注分布就会收敛。


    此外如果验证人过于显著的改变下注,例如先是赌某个块有很高概率胜出,然后又改赌另外一个块有高概率胜出,他将被严惩。这条规则确保了验证人只有在非常确信其他人也认为某个块有高概率胜出时才以高概率下注。我们通过这个机制来确保不会出现下注先收敛于一个结果然后又收敛到另外一个结果的情况,只要验证人足够多。


    POW共识同样可以理解为是一个下注机制:矿工选择一个块基于它进行挖矿,也就是赌这个块会成为主链的一部分;如果赌对了,他可以收到奖励,而如果赌错了,他会损失电费。只要所有的矿工都将他们的算力下注到同一条链上,使这条链拥有最多的工作量(即时算力下注的预测,也是算力下注的结果),共识就是安全的。POW中算力赌注的经济价值随着确认数的增加线性增长,而在Casper中验证人可以通过协调使下注比例指数增长,从而使共识快速达到最大安全。


    高度级共识

    High level consensus

    验证人对每一个高度上的每一个候选块独立下注,给每个块指定一个胜出概率并公布。通过反复下注,对于每个高度验证人会选出唯一一个胜出块,这个过程也决定了交易(transaction)执行的顺序。如果一个验证人在某个高度公布的概率分布总和大于100%,或者公布了小于0%的概率,或者对一个无效块指定了大于0%的概率,Casper将罚没他的保证金。


    交易最终确认

    Transaction Finality

    当锁定保证金的验证人中的绝大多数(满足协议定义阈值的一群验证人:保证金比例达到67%到90%之间某个百分比)以非常高的概率(例如,> 99.9%)下注某个块时,任何不包含这个块的分叉都不可能胜出,此时我们说这个块已最终确认(final)。此外,如果客户端发现所有小于高度H的块都已最终确认,那么此客户端永远不能接受一个在高度H - 1的状态和顺序执行这些完全块得到的状态不一样的分叉。这种情况下我们说这个状态(H - 1高度的状态)已最终确认。


    因此这里有相关的两种交易的最终确认:交易在特定高度被执行的最终确认(也就是对应块的最终确认,早于所有此高度之后的交易执行),以及交易执行后状态的最终确认(需要对应块和所有低于此高度的块被最终确认)。


    防审查

    Censorship Resistance

    共识协议最大的威胁之一是矿工形成以损害非成员利益为代价最大化成员获利的联盟。如果Casper中验证人的收入主要由手续费构成,一个多数联盟就能够通过过滤其它节点的出块来获取更大利益。不仅如此,攻击者还可以贿赂节点来剔除特定地址发出的交易,只要多数节点是理性的,他们就能够联合起来过滤掉没有剔除指定交易的块。


    为了抵御多数派联盟攻击,Casper将共识过程看作一个合作博弈,确保每一个节点只有在由所有节点组成的联盟中才能获得最大利益(至少在当利益主要由协议内奖励构成的情况下如此)。如果p%的验证人参与了共识博弈,那么他们将得到f(p) ≤ p%的收益;如果有100%的验证人参与则能获得更多回报。


    更具体的说,Casper会惩罚那些不按照协议规定顺序出块的验证人。协议会注意到出块顺序的偏离,并且扣下对应验证人的保证金和手续费。此外,通过下注赢得的收益与参与共识博弈的验证人数量成线性(或者超线性)关系。



    吞吐量(每秒可处理的交易数)会增加吗?


    答案很可能是确定的,而原因与其说是Casper的区块链架构不如说是Casper上的经济学。不过Casper的区块链设计确实支持了比POW共识更快的出块间隔。


    验证人的收入很可能只有交易费用,因此他们有增加Gas上限的直接动机,只要他们的服务器负荷的了。但是如果因此造成其它处理能力比较弱的验证人跟不上节奏,他们的收入会变少。所以验证人只会接受大家都能承受的Gas上限上涨。矿工(Miners)投资硬件的方式是购买更多的矿机(算力),而验证人的投资硬件的方式则会是升级服务器以获取更高的吞吐量。矿工也有购买能获得更高吞吐量的硬件的动力,但是这比购买算力的动力弱得多。


    相对于POW, 在基于保证金的POS上实现轻客户端更加方便。具体来说,轻客户端无需下载区块头来获得共识鉴别的安全性,或是交易执行有效性的经济性保证。大部分的共识开销只会影响验证人,不会影响轻客户端。轻客户端也可以在保留鉴别共识能力的前提下实现低延迟。


    网络分区的恢复


    由于未最终确认的区块中的交易可以被撤销,Casper具有在网络分区后恢复的能力。在分区重新连上后,Casper会执行具有更高验证人参与度的分区上获得下注的区块中的交易。这样在重连之后验证人重新下注前,分区双方就对共识状态达成了一致。验证人的下注会收敛并以高概率最终确认具有更高验证人参与度的分区上的某个块。Casper很可能会在产生胜出块之后再处理淘汰块中的交易,不过我们还没有决定到底是由验证人把这些交易纳入新块,还是由Casper按照原来的顺序处理。


    大规模崩溃的恢复


    即使在全网只剩一个节点没有崩溃的极端情况下Casper也有能力恢复。锁定保证金的验证人总是独立的对候选块下注,虽然下注和多数验证人一致的话回报会更高。在任何时候,验证人从出块获得的回报总是比不出块要高。如果锁定保证金的验证人过长时间没有上线,他的保证金会被解锁,新的验证人会接替他的位置。因此Casper的安全程度可以恢复到和大规模崩溃之前一样。


    抛开经济学术语的解释


    Casper是一个基于区块链的最终一致性共识协议。想对于一致性(C)它更倾向于可用性(A)(见CAP理论)。它总是可用,并且尽可能迅速的达成一致。它健壮到足以容忍不可预计的消息传输延迟,因为节点可以在收到延迟的消息之后通过重新组织交易达成共识。由大于50%的正常节点建立的分叉总是比剩下的有潜在问题的节点建立的分叉权重更高,因此它对不超过50%的网络失效有最终容错性(eventual fault tolernace)。需要注意的是客户端无法知道一个有51%的验证人参与的分支会不会被放弃,因为此时不知道这些验证人中是否有恶意节点。一个块只有在绝大多数(supermajority)验证人(或者说保证金)参与共识的情形下才能被认为是最终确认(final)的。


    验证人有什么责任?


    作为一个锁定保证金的验证人,你需要对块进行签名以及在共识过程中下注。如果你缴纳了一大笔保证金,你也许应该部署一个由多台服务器组成的多重签名环境来做验证工作,以减少服务器异常或是被黑导致的风险。这种方案需要反复实验和技术专家的帮助。


    为了最大化收益,验证人需要尽可能的保持在线和服务稳定。DDoS防护服务是非常必要的。你的收益率还取决于其他验证人的处理性能和可用性,也就是说这里存在一个你无法直接化解的风险。如果其他节点表现不行你也会遭受损失!但是此时如果你决定完全不参与共识你会损失更多。然而额外的风险通常意味着更高的回报,尤其是当风险已经被认识到而永远不会发生的时候。


    应用和普通用户有什么好处?


    应用和它们的用户可以从POW转向Casper的变化中获得许多好处。低延迟确认可以极大的改善用户体验。一般情况下交易很快就能最终确认。如果有网络分区发生,交易依然会被执行,而交易有被撤销的可能性这一情况会被清楚的报告给应用和其用户。应用的开发者依然需要处理分叉的情况,和使用POW协议时一样,但这里共识协议会给出一个对交易撤销可能性的清楚估量。


    展开全文
  • 以太坊共识协议

    千次阅读 2021-09-26 17:32:01
    以太坊如何达成共识 1.pow共识机制 2.最长合法链 3.Ghost 协议 前言 我们知道,以太坊出块时间约为15秒,出块时间加快,必然会产生更多的分叉,以太坊采用ghost 协议来解决大量分叉的问题。 与比特币相同,以太坊...
  • 内容整理自 北京大学肖臻老师《区块链技术与应用》公开课04-BTC-协议
  • 针对跨分片共识协议S-BAC通过分片之间互相通信来处理跨分片交易,造成通信开销大和高时延的问题,提出了一种改进的跨分片共识协议S-BAC+。首先,通过分片管理员来处理跨分片交易,有效地减少了通信开销和时延;其次...
  • 本文首先对BFT类共识协议按照改进思路分为3大类进行综述性概览: 针对无拜占庭错误场景优化的协议,包括PBFT、Zyzzyva等等 针对拜占庭错误场景优化的,包括Aardvark、Primer等等 为公链应用而优化的协议,包括...
  • 【区块链】分布式共识协议

    千次阅读 2019-01-09 20:45:39
    分布式共识协议 一、概述 总结: 私有链:封闭生态的存储系统,采用PAXOS、RAFT最佳 联盟链:半公开半开放特性,采用拜占庭容错的PBFT算法比较合适 公有链:POW、POS、DPOS是比较适合的高安全性的协议 ...
  • 是一个Java库,实现了Raft协议[1],在上可以找到Raft论文的扩展版本。 本文介绍了Raft,并用以下几句话陈述了它的动机: Raft是用于管理复制日志的共识算法。 它产生的结果等效于(multi-)Paxos,它的效率与Paxos...
  • Prism共识协议的Rust实现。 纸 棱镜:将比特币扩展10,000倍 (MIT CSAIL), (斯坦福大学), (UIUC) ,(MIT CSAIL),(斯坦福大学),(CMU), (UIUC) 摘要:比特币是第一个完全去中心化的无许可区块链...
  • 区块链共识协议最详细的分析

    千次阅读 2019-04-29 10:03:07
    区块链是一个去中心化的系统,共识机制通过数学的方式,让分散在全球各地成千上万的节点就区块的创建达成一致的意见。共识机制中还包含了促使区块链系统有效运转的激励机制,是区块链建立信任的基础。 区块链公链...
  • 恒星共识协议白皮书概论

    千次阅读 2018-03-12 21:03:13
    我们引入了恒星共识协议(Stellar Consensus Protocol-abbr:SCP),这是一个适用于全球共识的模型。SCP是第一个可证的安全共识机制,同时拥有四大关键属性:分散控制、灵活信任、低延迟、渐进安全。 上图中一些主流...
  • BTC-共识协议

    2020-04-11 14:34:25
    比特币中的共识协议 比特币系统中的共识要考虑到有些结点是有恶意的,假设系统中大部分结点是友好的,有恶意的结点占少数。 一种思路是用投票的方式,将所有交易写入一个候选区块,然后发给所有结点,大家验证这个...
  • 本文研究了在两种不同的共识协议下扩展区块链的经济意义:工作量证明(PoW)和权益证明(PoS)。 我们研究了一种经济模型,代理商可以通过区块链的加密货币存储财富,但由于区块链的有限交易率,清算时可能会面临...
  • 共识协议取得的共识是去中心化的账本里的交易 。 只有获得记账权的结点可以往区块里写交易,而获得记账权的途径就是解那个不等式puzzle,根据第一节课学习的哈希函数 puzzle friendly 的性质,求解这个puzzle的...
  • Hyperledger Fabric在发布1.4.3版本时,增加了新的共识策略Raft,以此来循序渐进地迁移至拜占庭容错算法(PBFT),它是一种基于etcd的崩溃容错(CFT)排序服务。Raft 遵循 “领导者和追随者” 模型,其中每个通道...
  • 一个库实现了筏共识协议核心功能,旨在用作分布式系统的构建块。 支持的功能 领导人选举。 日志复制。 领导转移。 成员资格更改。 开发中的功能 日志压缩。 先决条件 安装 git clone ...
  • 有限时间弹性共识协议的实现。 该存储库包含James Usevitch和密歇根大学航空航天工程系的论文中使用的代码。 跑步说明 克隆仓库,并导航至MATLAB中的仓库文件夹。 使用以下字段创建struct : n :代理总数的整数。 k...
  • 该论文于2018年5月首次披露,提出了一种基于亚稳态机制(metastable)的共识协议族。作者是一个神秘团队Team Rocket(火箭队?)。 所谓亚稳态,是指系统在某段时间内处于稳定状态,但在另外一段时间内可能是不...
  • fantoch :用于评估(行星尺度)共识协议的框架 实施的协议 节奏:( :( :( :( 它有什么作用? 所有协议都实现了特征 该规范可以用于 在给定的地理分布方案中模拟预期的延迟(假定无限的CPU和网络带宽)...
  • TrueChain共识协议 建立源 建造 步骤1 安装和 。 确保$GOBIN路径中有hmake。 使用hmake和docker构建所有内容 该项目使用: 与工具链(包含容器的环境)进行交互并构建跨平台的二进制文件。 gvt管理依赖项。 $ ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,026
精华内容 13,210
关键字:

共识协议