全网最全的BFT协议项目分析报告

2020年5月13日10:01:17 发表评论

在开始阅读之前,给你们打一个预防针,由于英语能力和语文水平比较薄弱,可能会导致本文阅读起来非常困难。目前本公众号寻求运营伙伴,感兴趣可以和我联系。

简介

在考虑如何将Tari应用在二层时,我们对最有希望的拜占庭共识机制及其应用进行了分析。

需要考虑的重要因素是“可伸缩性难题”。在文中提到的这些考虑了关于分散性,安全性和可伸缩性的潜在权衡:

· 去中心化:建立大多数系统所依据的核心原则,要考虑到抗审查性,并确保每个人都可以不带偏见地参与去中心化系统。

· 可扩展性:包含网络处理事务的能力。因此如果一个公共区块链被认为是高效、有效和可用的,那么它的设计应该能够处理网络上数以百万计的用户。

· 安全性:指账本的不变性,并考虑了51%攻击、Sybil攻击、分布式拒绝服务(DDoS)攻击等威胁。

通过该生态系统的最新发展,大多数区块链都集中在三个因素中的两个,即去中心化和安全性,却以可扩展性为代价。这样做的主要原因是节点必须先达成共识,然后才能处理交易。

报告审查了考虑到拜占庭容错(BFT)共识机制的建议,并考虑了它们在满足可伸缩性、去中心化和安全性特征方面的可行性和效率。在每种情况下,都会评估以下内容:

· 假设协议
· 实施参考;
· 关于该协议是否可用于Tari的一种识别方法,以保持分布式资产状态;

拜占庭容错一致性机制概述

许多端到端都在线实时策略游戏使用修改的锁步协议作为共识协议,以便管理游戏中玩家之间的游戏状态。每个游戏动作都会向所有其他玩家广播一个游戏状态增量,以及整个游戏状态的哈希值。每个玩家通过将增量应用于自己的游戏状态并比较游戏状态哈希值来验证更改。如果哈希值不一致,则进行投票,并且将游戏状态为少数的那些玩家断开连接并从游戏中移除(称为取消同步)。

许可的拜占庭容错协议

拜占庭协议方案被认为非常适合于已知参与者身份的许可区块链。示例包括Hyperledger和Tendermint。在这里,实现了联邦共识算法

共识协议

Hyperledger Fabric

Hyperledger Fabric(HLF)于2016年初开始作为LinX基金会的一个项目。其目的是为分布式账本创建一个开源、跨行业、标准的平台。HLF是分布式分类帐平台的实现,用于运行智能合约和成熟的技术。它有一个模块化的架构,允许各种功能的可插入实现。fabric分布式账本协议是运行在不同节点。fabric将节点区分为:

· 验证节点(他们运行共识算法,从而验证交易);
· 非验证节点(它们充当代理,可帮助将客户端连接到验证节点);

验证节点运行一个BFT共识协议来执行一个复制的状态机,该状态机接受部署、调用和查询事务作为操作。

区块链的哈希链是基于已执行的交易和产生的持久状态来计算的。链码(涉及接受要部署的智能合约的代码的交易)的复制执行用于验证交易。假设在n个验证对等方中,最多f<n/3(其中f是故障节点的数量,n是网络中存在的节点的数量)可以任意运行,而其他节点可以正确执行,从而适应 概念BFT共识。由于HLF建议遵循实用的拜占庭容错(PBFT)共识协议,因此链码事务本质上必须是确定性的,否则不同的节点可能具有不同的持久状态。SIEVE协议用于过滤不确定的事务,从而确保节点之间唯一的持久状态。

在针对v1.0版本进行重新设计时,该格式的目标是实现可扩展性。该版本允许交换成员资格和共识机制等模块。获得许可后,此共识机制主要负责接收来自客户端的交易请求并建立总执行顺序。

Tendermint

Tendermint Core是一种BFT权益证明(PoS)协议,它由两个协议合而为一:共识算法和对等网络协议。受Raft背后的设计目标启发,作者将Tendermint指定为一种易于理解,对开发人员友好的算法,可以进行算法复杂的系统工程。

Tendermint被建模为确定性协议,在部分同步下运行,从而在网络和各个进程自身的延迟范围内实现吞吐量。

Tendermint以加权轮询方式循环通过验证程序集。验证人所拥有的抵押(即投票权)越高,其权重就越大;并按比例分配更多的时间作为领导人。因此如果一个验证者具有与另一个验证者相同的投票权,则两者将由协议选举相等的次数。

批评人士认为,Tendermint并没有分散化,人们可以区分和瞄准领导层,对他们发动DDoS攻击,嗅到这条链的进展。虽然Tendermint已经实现了哨兵体系结构(包含哨兵节点,称为哨兵节点),但是关于分散程度的争论仍然是有疑问的。

哨兵节点

哨兵节点是验证者节点的守护者,并向验证者节点提供对网络其余部分的访问。它们与网络上的其他完整节点连接。哨兵节点可能是动态的,但应保持与彼此不断发展的随机子集的持久连接。他们应该总是期望有来自验证节点及其备份的直接传入连接。它们不会在对等交换反应器(Peer Exchange Reactor,PEX)中报告验证器节点的地址,并且可能对它们保留的对等节点的质量更严格。

属于彼此信任的验证者的哨兵节点可能希望通过虚拟专用网(VPN)彼此保持持久连接,但仅在PEX中互相告知。

无许可的拜占庭容错协议

当在无许可的区块链中使用时,BFT协议面临一些限制。它们无法随着参与者的数量很好地扩展,导致目标网络规模的性能下降。此外它们在这种情况下还不能很好地建立起来,因此容易出现安全问题,例如Sybil攻击。当前有一些方法试图规避或解决此问题。

协议和算法

Paxos

Paxos算法解决的问题正是分布式一致性问题,即一个分布式系统中的各个进程如何就某个值(决议)达成一致。

Paxos算法运行在允许宕机故障的异步系统中,不要求可靠的消息传递,可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了2F+1的容错能力,即2F+1个节点的系统最多允许F个节点同时出现故障。

一个或多个提议进程 (Proposer) 可以发起提案 (Proposal),Paxos算法使所有提案中的某一个提案,在所有进程中达成一致。系统中的多数派同时认可该提案,即达成了一致。最多只针对一个确定的提案达成一致。

Chandra-Toueg

Chandra–Toueg共识算法,于1996年发布,依赖于充当故障检测器的特殊节点。本质上,它将对其他节点执行ping操作,以确保它们仍在响应。这意味着检测器保持在线状态,并且当新节点加入网络时必须不断使检测器知道。

该算法本身类似于Paxos算法,该算法也依赖于故障检测器,并且要求f<n/2,其中n是进程总数。

Raft

Raft是一种共识算法,旨在替代Paxos。通过逻辑分离,它比Paxos更加易于理解,但是它也被正式证明是安全的,并提供了一些附加功能。

Raft通过民选领导者达成共识。每个跟随者都有一个超时,在这个超时中它期望来自领导者的心跳。因此它是一个同步协议。如果领导者掉线,则举行选举以寻找新的领导者。这需要节点以先到先得的方式提名自己。挂票要求取消选举并重新开始选举。这表明节点需要高度的协作,并且恶意节点可能容易串通以破坏领导者,然后阻止选举新的领导者。Raft是一种简单的算法,但显然不适合在加密货币应用程序中达成共识。

Paxos,Raft和许多其他知名协议可以容忍崩溃错误,而从PBFT开始的BFT协议甚至可以容忍任意损坏的节点。许多后续协议通常通过乐观执行来提高性能,而乐观执行可以在没有故障时提供出色的性能。当客户竞争不激烈时;当网络运行良好时,至少会有一些进展。

在最近的工作中,提倡改善最坏情况下的性能,即使在系统受到攻击时也能提供服务质量保证,即使这在乐观情况下也会牺牲性能。但是尽管“严格意义上的鲁棒BFT协议可以容忍所组成的节点,但它们仍然依赖于有关底层网络的时序假设” 。因此,焦点转移到了异步网络上。

Hashgraph

Hashgraph 是一种异步拜占庭容错算法(ABFT),它跟我们目前常见的 PBFT 算法最大的不同就是它是完全异步的。我们知道 PBFT 算法能支撑的网络规模是非常有限的最大原因就 PBFT 模型的通信复杂度是 O(N^2),随着节点数量的增加,需要通信的消息数量呈指数级别的上升。而 Hashgraph 突破性的抛弃 PBFT 中使用的消息同步机制,使用异步 BFT,通过保证最终确定性来确保算法的高效和安全。

Hashgraph 采用的是 DAG 数据结构,这跟当前的很多开源链(比如 Iota,byteball, nano 等)是类似的,因为它们都采用 DAG 作为底层数据结构模型。但是 Hashgraph 最特别的一点是,它无需中心权威节点,而是依靠独特的 Gossip about Gossip 和 Virtual Vote 两大机制来保证了算法可以在纯异步的环境中高效运行,并且通过绝对多数(超过 2/3 节点)强可见(强引用)机制来保证了共识结果的正确性(安全)。

Hashgraph 算法是一种拜占庭容错算法,它要求节点数量是相对固定的(总量为 N 需要预先设定),这样的话,它就可以通过大于 2/3 忠诚节点的比例原则来达到拜占庭容错。这跟当前公链模型下(比如 DAG 主链,POW,POS 等)这些算法在达到共识的条件上有一些区别,所以更适用于私链(或联盟链)。但是,由于其独特的性质(在保证去中心化的同时不需要繁重的工作量证明),Hashgraph 在未来的公链也有相当潜在的使用价值。

Gossip Protocol

Gossip是一个带冗余的容错算法,更进一步,Gossip是一个最终一致性算法。虽然无法保证在某个时刻所有节点状态一致,但可以保证在”最终“所有节点一致,”最终“是一个现实中存在,但理论上无法证明的时间点。

因为Gossip不要求节点知道所有其他节点,因此又具有去中心化的特点,节点之间完全对等,不需要任何的中心节点。实际上Gossip可以用于众多能接受“最终一致性”的领域:失败检测、路由同步、Pub/Sub、动态负载均衡。

但Gossip的缺点也很明显,冗余通信会对网路带宽、CUP资源造成很大的负载,而这些负载又受限于通信频率,该频率又影响着算法收敛的速度,后面我们会讲在各种场合下的优化方法。

八卦历史可以表示为有向图,如图1所示。

全网最全的BFT协议项目分析报告

Hashgraph引入了一些重要概念,这些重要概念在后来的BFT共识算法中被重复使用:famous witnesses和strongly seeing.

Ancestors(祖先)

如果一个事件(x1)在另一个事件(x2)之前,并且它们通过一条线连接,则较旧的事件是该事件的祖先。如果两个事件都是由同一节点创建的,则x1是x2的自祖。

Seeing(见证)

如果事件x1是x2的祖先,那么我们说x1看到x2,只要该节点不知道来自x2的任何派生。因此在没有分叉的情况下,所有事件都将看到其所有祖先。

 +-----> y
     |
x +--+
     |
     +-----> z

在前面的示例中,x是y和z的祖先。但是,由于y和z之间没有祖先关系,因此可见条件失败,因此y无法看到x,而z无法看到x。

在协议中的节点检测到分叉之前,可能需要花费一些时间。例如Bob可以创建z和y,但与Alice共享z,与Charlie共享y。Alice和Charlie最终都会知道这个骗局,但在那之前,Alice会相信y看到x,Charlie会相信z看到x,这就是strongly seeing的概念。

Strongly Seeing(强见证)

如果节点检查其哈希图并注意到事件z看到了事件x,不仅如此,它还可以通过大量的对等节点(通常是通过多条路线)绘制祖先关系,并且事件与 每个节点也看到x,那么说根据该节点,z强烈看到x。如下图

全网最全的BFT协议项目分析报告

Gossiping的架构

主要共识算法循环包括每个节点(Alice),选择随机对等节点(Bob)并共享其图历史记录。现在Alice和Bob具有相同的图形历史记录。

Alice和Bob都利用刚刚从邻居那里学到的新知识创建了一个新活动。Alice不断重复此过程。

内部共识

同步后,节点将使用三个过程来确定尽可能多的事件的顺序。该算法使用常数n(节点数)和较小的常数c>2。

首先我们有Swirlds Hashgraph共识算法,每个成员并行运行。每次同步都会带来新的事件,然后将其添加到哈希图中。然后将所有已知事件分成几轮。然后确定每个回合中的第一个事件是否著名(通过纯本地拜占庭协议和虚拟投票达成)。然后在具有足够信息的那些事件中找到总订单。如果两个成员分别为事件分配历史位置,则即使有更多信息进入,他们也可以保证分配相同的位置,并且永远不会改变。此外每个事件最终都有可能被分配为此类位置。

in parallel:
    loop
      sync all known events to a random member
    end loop

    loop
      receive a sync
      create a new event
      call divideRounds
      call decideFame
      call findOrder
    end loop

其次,我们有dividRounds过程。一旦知道事件x,便为其分配一个轮数x.round,并计算布尔值x.witness,以指示这是否是该轮成员创建的第一个事件。

  for each event x
        r ← max round of parents of x ( or 1 if none exist )
        if x can strongly see more than 2/3*n round r witnesses
          x.round ← r + 1
        else
          x.round ← r
        x.witness ← ( x has no self parent ) || ( x.round > x.selfParent.round )

第三,我们有DecisionFame程序。对于每个见证事件(即x.witness为true的事件x),请确定该事件是否著名(即为x.famous分配一个布尔值)。该决定由基于虚拟投票的拜占庭协议协议完成。每个成员都在自己的Hashgraph副本上本地运行它,而无需其他通信。该协议将哈希图中的事件视为彼此发送选票,尽管计算纯粹是针对成员计算机而言。该成员将投票分配给每个回合的见证人,连续数回合,直到三分之二以上的成员同意为止。

 for each event x in order from earlier rounds to later
        x.famous ← UNDECIDED
        for each event y in order from earlier rounds to later
          if x.witness and y.witness and y.round > x.round
            d ← y.round - x.round
            s ← the set of witness events in round y.round-1 that y can strongly see
            v ← majority vote in s ( is TRUE for a tie )
            t ← number of events in s with a vote of v
            if d = 1 // first round of the election
              y.vote ← can y see x ?
            else if d mod c > 0 // this is a normal round
                if t > 2* n /3 // if supermajority, then decide
                  x.famous ← v
                  y.vote ← v
                  break // y loop
                else // else, just vote
                  y.vote ← v
            else if t > 2* n /3 // this is a coin round
              y.vote ← v
            else // else flip a coin
              y.vote ← middle bit of y.signature

Criticisms(评判)

提出了解决以下一些评判的尝试:

1. Hashgraph协议已获得专利并且不是开源的。
2. 此外,哈希图白皮书假设网络中的节点数n是恒定的。实际上n可以增加,但是当n变大时,性能可能会严重下降。
3. Hashgraph不像他们的论文中所说的那样“公平”,建议至少进行一次攻击。

SINTRA

SINTRA是一种安全入侵容忍复制体系结构,用于在受到拜占庭式错误影响的异步网络中进行协调。它由一组协议组成,并用Java实现,可在由广域网(例如Internet)连接的一组服务器之间提供安全的复制和协调。对于由n台服务器组成的组,它最多可以容忍t<n/3台以任意恶意方式发生故障的服务器,这对于给定模型而言是最佳的。服务器仅通过异步点对点通信链接进行连接。因此SINTRA自动容忍定时失败以及利用定时的攻击。SINTRA组模型是静态的。这意味着必须通过SINTRA之外的机制来恢复发生故障的服务器,并且必须通过受信任的进程来初始化组。

该协议利用随机化,这是解决此类异步分布式系统中拜占庭协议所必需的。阈值密码伪随机生成器提供了随机化,该伪随机生成器是基于Diffie-Hellman问题的抛硬币协议。阈值密码学是SINTRA中的基本概念,因为它允许该组执行公共密码操作,为此在服务器之间共享密钥,这样一来,单个服务器或少量损坏的服务器联盟都无法获得有关该密钥的有用信息。SINTRA提供了用于数字签名,公共密钥加密和不可预测的伪随机数生成(投币)的阈值加密方案。它包含用于可靠且一致的广播的广播原语,该广播原语就杰出的发件人发送的各个消息达成协议。但是,这些原语不能保证系统传递的多条消息流的总顺序,这是使用状态机复制范例构建容错服务所必需的。这是原子广播的问题,需要基于拜占庭协议的更昂贵的协议。SINTRA为二进制和多值协议提供了多个随机的拜占庭协议协议,并在协议之上实现了原子广播频道。安全因果原子广播频道提供了在拜占庭式故障存在时也能维持因果顺序的原子广播。

图3说明了SINTRA的模块化设计。模块化极大地简化了容忍拜占庭式故障所需的复杂协议的构建和分析。

全网最全的BFT协议项目分析报告

HoneyBadgerBFT

HoneyBadgerBFT于2016年11月发布,被视为第一个实用的异步BFT共识算法。它在设计时考虑了在这种情况下带宽被认为是稀缺的,但是可以使用大量的CPU功能。因此该协议实现了公私密钥加密,以提高共识建立的效率。该协议与一组固定的服务器一起运行以运行共识。但是这导致集中化并让攻击者有专门针对这些服务器的可能性。

在其阈值加密方案中,任何一方都可以使用主公用密钥对消息进行加密,并且在恢复明文之前,它需要f + 1个正确的节点来计算和显示密文的解密份额。

HoneyBadgerBFT的工作与SINTRA密切相关,如前所述,SINTRA是基于中的异步原子广播协议的系统实现。该协议包括从原子广播信道(ABC)减少到异步通用子集(ACS),以及从ACS减少到多值验证协议(MVBA)。

HoneyBadger提供了一种从ABC到ACS的新颖方法,可通过批处理提供更高的效率(通过O(N)因子),同时使用阈值加密来保留审查制度的弹性。通过选择改进的子组件实例化也可以获得更好的效率。例如通过使用替代ACS以及高效可靠的广播(RBC)避免了昂贵的MVBA。

Stellar共识协议

Stellar共识协议(SCP)是一种异步协议。它被认为是由提名协议和投票协议组成的全球共识协议。据说SCP是BFT,因为它带来了仲裁分片的概念并击败了BFT。

每个参与者形成其他用户的法定人数,从而创建一个信任层次结构,这需要复杂的信任决策。最初提名督导员开始运作。在此期间,提出了称为候选值的新值以供协商。接收这些值的每个节点将在其中投票一个值。最终该插槽的一致选择值。

成功执行提名协议后,节点将部署投票协议。这涉及联合投票以提交或中止提名协议产生的值。这将导致外部化当前时段的选票。被否决的选票现在被宣布为无关紧要。但是在某些状态下,节点无法得出关于中止还是提交值的结论。通过将其移至更高价值的选票并在新的选票协议执行中考虑它,可以避免这种情况。如果节点认为此卡住的选票已落实,则有帮助。因此SCP确保避免和管理卡住状态并提供生动的生活。

在SCP情况下,定额分片的概念提供了渐近安全性和灵活的信任,使其比其他早期使用联合BFT的共识算法(例如Ripple协议共识算法)更易接受。在此为用户提供了更多的独立性来决定信任谁。

SCP协议声称没有阻塞状态,并提供分散控制,渐近安全性,灵活信任和低延迟。但是它不能始终保证安全。如果用户节点选择无效的仲裁分片,则无法保证安全性。如果出现分区或节点行为不正常的情况,它将停止网络的进程,直到可以达成共识为止。

LinBFT

LinBFT是用于区块链系统的BFT协议。它在合理的条件下(其中n是参与者的数量)允许每块O(n)的摊销通信量,同时满足安全性和活动性的确定性保证。它满足了部分同步网络中的活动。

LinBFT通过实现O(n)的更改来降低其O(n4)复杂度:线性视图更改,阈值签名和可验证的随机函数。这显然是最佳的,因为散布一个区块已经进行了O(n)次传输。

LinBFT旨在为无许可的公共区块链系统实施,并考虑了没有公共密钥基础设施,PoS,轮换领导者和动态参与者集的匿名参与者。例如参与者可以是匿名的,而彼此之间没有集中式公共密钥基础结构(PKI)的公共密钥,并且可以参与创建阈值签名所需的分布式密钥生成(DKG)协议,这两者都是繁重的通信过程。

LinBFT与PoS兼容,后者可通过削减来抵御Sybil攻击并阻止不诚实的行为。

Algorand

Algorand白皮书于2017年5月发布。Algorand是同步BFT共识机制,其中以最小速率添加块。它允许参与者私下检查是否选择他们参加共识参与,并且每个用户仅需要一条消息,从而限制了可能的攻击。

通过采用可验证的随机函数,Alogrand可以扩展至500,000个用户,这些函数是伪随机函数,能够提供可验证的证明,该函数的输出正确。这些BFT算法中的大多数都需要某种类型的随机性预言,但是如果使用该预言,则所有节点都需要看到相同的值。这是通过_comon _coin想法实现的。具体硬币使用了一种简单得多的方法,但仅返回二进制值。

Thunderella

Thunderella实现了一种异步策略,其中在发生故障时将同步策略用作后备方法,因此它既实现了鲁棒性又提高了速度。可以使用PoW将其应用于无许可的网络中。网络的健壮性和“即时确认”要求75%的网络是诚实的,并且需要存在领导者节点。

Snowflake to Avalanche

由Team Rocket发布,是建立在一个亚稳态机制上的。它们被称为Slush,Snowflake,Snowball和Avalanche。

这些协议与传统共识协议和Nakamoto共识协议的不同之处在于,它们不需要选举产生的领导者。相反该协议只是引导所有节点达成共识。

由于这种亚稳定性的概念,这四个协议被描述为一个新的协议家族:一种通过引导所有节点朝着一个新的共识而建立共识的方法,而不需要领导者,同时仍然保持相同的安全级别,并产生超过当前协议的速度。

这是通过形成“子群体”来实现的,“子群体”是来自网络节点的小型随机样本。这样可以提高吞吐量,并在并行共识达成合并以形成总体共识之前便开始运行并行共识,这在本质上可以被视为类似于八卦协议。

在安全性,吞吐量(每秒事务数)和可伸缩性(网络支持的人数)方面,Slush,Snowflake,Snowball和Avalanche似乎能够实现这三个目标。它们在拜占庭式对手在场的情况下提供了概率安全保证,并由于其并发性而实现了高吞吐量和可伸缩性。

BFT协议设计当前面临的问题是,当活动的节点数量较少时,系统可以非常快地执行,因为需要做出的决策较少。但是当用户众多且交易增加时,无法维护该系统。

尽管传统的共识协议需要O(n2)通信,但对于某些安全参数k << n,其通信复杂度从O(kn log n)到O(kn)。从某种意义上说,Team Rocket强调指出,其协议的通信复杂性比O(n2)通信的强度低,因此使这些协议更快,更具可伸缩性。

为了回溯一下,计算机科学中使用了Big O表示法来描述算法的性能或复杂性。它描述了最坏的情况,可用于描述算法所需的执行时间。在共识算法的情况下,O描述了一个有限的预期步骤或操作数。例如,O(1)描述了一种算法,无论输入数据集的大小如何,该算法将始终在同一时间执行。O(n)描述了一种算法,其性能将线性增长,并且与输入数据集的大小成正比。O(n2)表示一种算法,其性能与输入数据集大小的平方成正比。

原因是O(n2)表示功能的增长速度由n2决定,其中n是网络上的人数。因此增加一个人成倍地增加了在网络上传播信息所花费的时间,而传统的共识协议则要求每个人都互相通信,这是一个费力的过程。

尽管假定了一个容易受到DoS攻击的同步网络,但是这个新的协议系列“达到了足以满足其他要求的安全级别”。

PARSEC

PARSEC是一种BFT共识算法,具有弱同步假设(高度异步,假设随机延迟具有有限的期望值)。与Hashgraph相似,它没有领导者,没有轮询,没有PoW,并且最终以概率1达成共识。它与Hashgraph的不同之处在于,在不存在和存在故障的情况下,它都可以提供高速。因此它避免了委托PoS(DPoS)的结构,该结构要求一组受信任的领导者,并且没有轮循机制(其中允许的一组矿工在每个块上签名)。

PARSEC是完全开放的,与Hashgraph不同,Hashgraph拥有专利并且是开源的。

在任何值上达成拜占庭协议的一般问题都简化为在参与每个决策的节点上达成二进制拜占庭协议的简单问题。这使PARSEC在适应八卦协议后可以重用二进制拜占庭协议协议(无签名的异步拜占庭共识)。

与HoneybadgerBFT相似,该协议是通过添加文献中提出的有趣观点而构成的。类似于Hashgraph和Avalanche,八卦协议用于允许节点之间的有效通信。

最后通过将关键思想移植到异步设置中,消除了中暗示的对可信任领导者或可信任设置阶段的需求。

网络设置为通过随机同步连接进行通信的N个算法实例的N个。由于随机同步,所有用户都可以就发生的事情达成协议。无法保证节点应按时接收消息,并且最多允许t拜占庭式(任意)故障,其中3t <N。没有发生故障的实例被认为是正确的或诚实的,而发生故障的实例被称为故障或恶意的。由于拜占庭式故障模型允许恶意行为,因此包含超过2/3N个实例的任何实例集都称为“绝大多数”。

当节点收到八卦请求时,它会创建一个新事件并向后发送响应(在Hashgraph中,响应是可选的)。每个八卦事件包含:

1. 正在传输的数据。
2. 自父self-parent (同一节点创建的另一个八卦事件的哈希)。
3. 另一个父节点other-parent(由另一个节点创建的另一个八卦事件的哈希)。
4. 创建原因,可以是信息请求,对另一个节点的请求的响应或观察。观察是节点创建八卦事件以记录该节点自己进行的观察的时间。
5. 创建者ID(公钥)。
6. 签名–签名上述信息。

自父和其他父节点阻止篡改,因为它们已签名并且与其他八卦事件相关。

与Hashgraph一样,对手很难干预共识算法,因为所有投票都是虚拟的,并且不共享投票细节。每个节点根据其八卦图的副本找出其他节点将投票的内容。

PARSEC还使用了来自Algorand的具体硬币的概念。这用于打破关系,尤其是在敌方仔细管理节点之间的通信以维持投票僵局的情况下。

在步骤1中,节点尝试为一组结果收敛于“true”结果。如果未实现,则他们继续执行步骤2,尝试收敛于“false”结果。如果仍然无法达成共识,则进行一次硬币翻转,然后返回到另一轮投票中的步骤1。

Democratic BFT

这是一种确定性的拜占庭共识算法,它依赖于新的弱协调器。该协议在Red Belly区块链中实现,据说在Amazon Cloud Trials上每秒可实现30,000个事务。通过结合中将多阀还原为二进制共识的优化变体,生成了民主BFT(DBFT)共识算法。在好的情况下,当所有非故障进程都提出相同的值时,它在四个消息延迟中终止。

弱协调器一词用来描述算法在存在错误或缓慢协调器的情况下终止的能力,不同于以前没有终止能力的算法。这里的基本思想是允许进程在接收到消息阈值时立即完成异步循环,而不必等待来自协调器的消息,该消息可能很慢。结果算法假设部分同步;是弹性和时间最优的;并且不需要签名。

摆脱了异步消息系统中无法解决共识的可能性,在异步消息系统中,进程可能有故障或拜占庭,因此采用了随机化或附加同步技术。

尽管t<n/3拜占庭式过程,随机算法仍可以使用每个过程的“本地”硬币或共享的通用硬币来概率性地解决n个过程之间的共识。当基于本地硬币时,现有算法会收敛O(n2.5)预期时间。

最近的不包含签名的随机算法在公平调度程序下解决O(1)预期时间的共识,其中O是二进制。

为了确定性地解决共识问题并防止使用通用硬币,研究人员假定了部分或最终同步。在这里,这些解决方案需要唯一的协调程序(称为领导者),以保持无故障。

此技术有优点也有缺点:

好处是,如果协调器无故障,并且消息在异步回合中及时传递,则协调器会将其提议广播到所有进程,并且在恒定数目的消息延迟之后确定该值。

 缺点是有缺陷的协调器可以通过全面利用其功能并将其价值强加给所有人,从而极大地影响算法性能。因此非故障过程别无选择,只能在这一轮中什么都不做。

该协议使用弱协调器,允许引入一种新的确定的拜占庭共识算法,该算法是时间最优的,弹性最优的,不需要使用签名。与经典的强协调器不同,弱协调器不施加其价值。它允许无故障流程快速确定值,而无需协调器,同时如果无故障流程知道它们提出了可以决定的独特值,则可以帮助算法终止。另外弱协调器的存在允许在不等待特定消息的情况下乐观地执行回合。这与经典的BFT算法不同,经典的BFT算法必须等待其协调器发出的特定消息,并且有时不得不从慢速的网络或故障的协调器中恢复。

关于拜占庭协调器的速度较慢的问题,弱协调器通过贡献一个值来帮助达成协议,同时仍允许终止一定数量的消息延迟。因此,它不同于经典的协调器或最终的领导者,后者无法在二进制拜占庭共识算法BAMPn,t[t<n/3]中实现。

协议的验证类似于HoneyBadger区块链的验证,其中使用了中的随机算法“ Coin”。使用位于不同大陆的五个数据中心中的100个Amazon虚拟机,结果表明DBFT算法的性能优于“硬币”算法,该算法预期会在O(1)轮中终止。此外由于已发现拜占庭行为严重影响了基于协调员的共识的性能,因此在验证中测试了四种不同的拜占庭攻击。

总结摘要

表1突出了上述BFT协议的特点。渐进安全、无许可区块链、时间假设、分散控制、低延迟和灵活信任构成价值体系的一部分。

1. 渐进安全性-这仅依赖于数字签名(和散列函数)的安全性。
2. 无许可协议-这允许任何人创建地址并开始与协议交互。
3. 时间假设-指时间假设的形式-同步程度。
4. 分散控制-一致性是通过保护该节点的身份,直到其工作完成,通过一个无领导的节点来实现和维护的。
5. 低延迟-这描述了一个计算机网络,它经过优化,能够以最小的延迟处理大量数据消息。
6. 灵活的信任-用户可以自由地信任他们认为合适的任何组合。

全网最全的BFT协议项目分析报告

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: