SWIRLDS HASHGRAPH 共识协议: 公平，快速，拜占庭容错

LEEMON BAIRD MAY 31, 2016 SWIRLDS TECH REPORT SWIRLDS-TR-2016-01

摘要

一个新的系统，Swirlds散列图共识算法，被提议用于保证拜占庭容错的复制状态机。它实现了公平性，因为攻击者很难操纵两个交易中的哪一个将被选为第一个这样的的共识顺序。它具有完全的异步性，没有领导者，没有轮询，没有工作证明，最终以同样的概率达成一致，并且在没有缺陷的情况下高速运转。它基于gossip协议，其中参与者不只是传播交易。他们传播gossip。他们共同构建一个反映所有gossip事件的散列图。这使得拜占庭协议可以通过虚拟投票来实现。Alice不会通过互联网向Bob投票。相反，Bob根据他对Alice的了解，计算Alice将投什么票。这对所有交易的总订单产生了公平的拜占庭协议，除了交易本身之外，通信开销很少。

关键词：拜占庭，拜占庭协议，拜占庭容错，复制状态机，公平，公平，哈希图，关于传播gossip，虚拟投票，Swirlds

内容

List of Figures

Introduction 介绍
Core concepts 核心概念
Gossip about gossip: the hashgraph 传播gossip: 哈希图
Consensus algorithm 共识算法
Proof of Byzantine fault tolerance 拜占庭容错证明
Fairness 公平性
Generalizations and enhancements 概括和增强
Conclusions 结论

References 参考

Appendix A: Consensus algorithm in functional form

List of Figures 图表列表

Gossip history as a directed graph
The hashgraph data structure
Illustration of strongly seeing.
Pseudocode: the Swirlds hashgraph consensus algorithm
Pseudocode: the divideRounds procedure
Pseudocode: the decideFame procedure
Pseudocode: the finalOrder procedure

1. 介绍

分布式数据库通常需要具有拜占庭容错的复制状态机。一些作者用“拜占庭”这个术语来表示软弱，例如假设攻击者不会串通，或者沟通是弱的异步。在本文中，“拜占庭”将以使用其原始定义的强烈意义：成员中只有不到1/3的成员可以成为攻击者，他们可以勾结，并且在没有消息延迟的限制下，可以删除或延迟诚实成员之间的信息。攻击者可以控制网络来延迟和删除任何消息，尽管在任何时候，如果一个诚实的成员多次向另一个成员发送消息，攻击者最终必须允许其中一个通过。假设存在安全的数字签名，那攻击者不能无法不留痕迹地修改消息。假定存在安全的散列函数，那这些散列函数永远不会冲突。本文提出并描述了Swirlds散列图的共识算法，并在强烈的定义下证明了拜占庭容错性。 FLP定理说明：没有一个完全确定性的拜占庭系统是完全异步的，无限的消息延迟，并且仍然保证达成共识。但是非确定性系统有可能以同样的概率达成共识。哈希图共识算法是完全异步的，是非确定性的，并且以相同的概率实现拜占庭协议。一些系统，如Paxos或Raft使用领导者，如果攻击者对当前领导者发起拒绝服务攻击，他们可能会使他们容易遭受大量延迟。很多系统甚至可能被一个坏客户推迟。事实上，后面的文章表明，具有这种漏洞的系统可能更好地被描述为“拜占庭故障可存活”而不是“拜占庭容错”。哈希图共识不使用领导者，并且能够适应对小型的成员子集进行攻击。其他系统（比如比特币）则基于工作的区块链验证。这避免了所有上述问题。然而，这样的系统不是拜占庭式的，因为一个成员从来不知道何时达成共识，他们只能随着时间的推移, 从而信任某个结果。如果两个区块同时开采，那么该链就会分叉，直到社区都同意延伸哪个分支。如果块缓慢添加，社区总是选择更长的分支，其他分支将停止增长，并且可以修剪和丢弃，因为它是“陈旧”的。这会导致效率低下，虽然某些区块开采得当，但无论如何都会被丢弃。这也意味着有必要放慢块开采的速度，以便社区能够共同选择分叉，而不是一直创建新分叉。这是工作证明的目的。通过要求矿工解决一个困难的计算问题来挖掘一个区块，它可以确保整个网络在采矿之间平均具有足够长的延迟。哈希图共识算法相当于一个块链，其中“链”不断地分支，没有任何修剪，没有任何块过时，并且允许每个矿工每秒钟挖掘许多新块，而没有工作证明和100％的效率。工作量证明的区块链还要求额外计算，浪费电力，并且可能需要购买昂贵的采矿设备。通过使用长时间延迟的可信硬件芯片，一个过期时间证明系统可以避免浪费的电力（尽管可能不是开采工具的成本），就好像他们正在进行工作证明的计算一样。但是，这要求所有参与者相信创建该芯片的公司。这种对芯片厂商的信任在某些情况下存在，但在其他情况下则不存在，例如当FreeBSD被更改为不仅仅依靠硬件RDRAND指令获取安全随机数时，因为“我们不能再相信它们了”。拜占庭协议系统为避免上述问题，制定了该拜占庭协议。这些系统通常交换许多信息供会员投票。对于n个成员来决定单个YES/NO问题，有些系统可能需要 O（n）个消息需要通过网络发送。其他系统可能需要O（n^2），或者甚至O（n^3）个消息，每个二进制决策通过网络。然后可以扩展单个YES/NO决策的算法来决定一组交易的总订单，这可能进一步增加投票流量。哈希图在整个网络上都没有投票，因为所有投票都是虚拟的。

2. 核心概念

哈希图共识算法包括下面这些核心概念:

交易: 任何人都可以在任何时刻创建新的签名交易。所有人都会有此交易的完整拷贝，社区将会对这些交易的排序达成共识。
公平性：少数攻击者难以不公平地影响被选为共识的交易顺序。
Gossip：信息会由每位成员随机选择另一名成员，并告诉他们所有的自己知道的信息。
哈希图：一种记录了每个人传播的gossip记录和顺序的数据结构。
关于gossip的gossip：哈希图是通过gossip协议传播的。被传播的是gossip本身的历史，所以这是gossip about gossip。这仅仅使用非常少的带宽开销，而且不仅仅是在单纯地传播gossip事件。
虚拟投票：每个成员都有一个散列图的副本，所以如果Alice运行着正常的拜占庭协议协议（包括发送投票），Alice可以计算Bob将给她发送了什么投票。所以鲍勃不需要真正的投票。每个成员都可以就任何的决定达成拜占庭协议，而无需发送任何一次投票。散列图本身就足够了。因此，零带宽使用，不仅仅是在简单地传播hashgraph。
著名的证人：社区可以通过收集 O（n log n）个关于 “是/否事件x在事件y之前出现” 的是/否问题，进行运行单独的拜占庭协议协议，将n个事务列表排序。更快的方法是只挑选几个事件（散列图中的顶点），称为证人，并且如果散列图显示大多数成员在创建后很短时间内收到它，则定义一个有名的证人。仅仅为证人运行拜占庭协议协议就足够了，为每个证人决定单个问题“这个证人是否出名？”。一旦拜占庭就一组固定的证人达成协议，就很容易从哈希图中得出所有事件的公平的总订单。
强连接：给定散列图中的任何两个顶点x和y，可以立即计算出x是否强连接y，如果它们通过经过足够多成员的多个有向路径连接，则将其定义为真。这个概念可以证明关键定理：如果Alice和Bob都能够计算Carol在给定问题上的虚拟投票，那么Alice和Bob会得到相同的答案。这个定理形成了拜占庭与概率一致的数学证明的基础。

图1. Gossip历史是一个有向图。任何Gossip历史都可以用一个图来表示，每一个成员都是一个顶点。当Alice收到Bob的gossip时，告诉她他所知道的一切，这个gossip事件由Alice列中的一个顶点表示，其中两条边向下延伸到Alice和Bob的紧接着的前面的gossip事件。

3. 关于gossip的gossip：哈希图

哈希图共识算法使用一个gossip协议。这意味着像Alice这样的成员会随机选择另一个成员，比如Bob，然后Alice会告诉Bob她知道的所有信息。 Alice然后重复这样的操作，选择一个随机的成员。Bob反复做这样的事情，同时，其他成员也会这样做。通过这种方式，如果一个成员接到新信息，它就会以指数形式快速传播到整个社区，直到每个成员都意识到这一点。任何gossip协议的历史都可以用像图1这样的有向图来说明。Alice列中的每个顶点表示一个gossip事件。例如，Alice列中的顶级事件表示了Bob向Alice发送了一个gossip同步，Bob在其中告知了他所知道的所有信息。该顶点有两个向下的连线，连接到Alice和Bob的最前面的gossip。时间在图形中流动，所以较低的顶点表示历史中较早的事件。在一个典型的gossip协议中，像这样的图只是用来讨论协议;实质上这个图形并没有存储在任何地方形。在哈希图共识中，图是实际上的数据结构。图2说明了这个数据结构。每个事件（顶点）都以字节序列的形式存储在内存中，由其创建者签名。例如，Alice（红色）的一个事件记录了Bob执行了gossip同步的事实，在该事实中，他向她发送了他所知道的一切。此事件由Alice创建并由她签名，并包含另外两个事件的散列：她的最后一个事件和Bob在该gossip同步之前的最后一个事件。红色事件还可以包含Alice选择在那个时候创建的任何事务的有效载荷，并且可能包含一个时间戳，即Alice声明创建它的时间和日期。该事件的其他祖先（灰色）不包含在其中，而是由一组密码哈希确定。具有散列图的这种数据结构已经被用于其他的地方，例如Git中的顶点是文件树的版本，边表示文件的更改。但Git并没有存储成员是如何沟通的这种记录。哈希表有自己的实现目的，就是记录下成员之间沟通的历史。 gossip协议被广泛用于传输各种类型的信息。他们可能会涉及传播用户身份，传播交易，传播区块链，或传播其他需要分发的信息。但如何定义关于gossip的gossip协议？如果成员们传播传递哈希图本身呢？当Bob向Alice传播时，他会把所有他知道但她不知道的事件都给她。传播哈希图给参与者很多信息。如果一个新事件被放置在事件的有效载荷中，它将很快传播至所有成员那，直到每个成员都知道。Alice在接受这笔交易时。她会知道Bob是何时才知道这笔交易。同时她也会确切地知道Carol是何时知道Bob已经知道这笔交易的事实。当所有成员都有散列图的副本时，这种深层次的链推理就成为可能。随着哈希函数向上增长，不同的成员可能会在顶部附近的关于新事件的子集上略有不同，但它们将迅速收敛到一个在哈希图中具有完全相同的事件的状态。此外，如果Alice和Bob碰巧都有一个特定的事件，那么他们也保证都拥有其所有的祖先。他们也会同意这些祖先的所有子图的所有连线。所有这些都是在本地运行的强大的算法，包括拜占庭容错。这种能力带来的通信开销很小。如果社区只是传播他们创建的签名交易，则需要一定数量的带宽。如果他们只是在传播散列图，并且如果在足够多的事务中，有一个典型事件中至少包含一笔交易，则开销很小。她不会签署她创建的交易，她只会签署她创建的事件来包含该交易。无论哪种方式，她只发送一个签名。换句话说，无论如何，她必须自己发送交易。唯一额外的开销就是她必须发送这两个哈希值。但即使这样也可以压缩处理。在图2中，Alice不会向Carol发送红色事件，直到Carol已经拥有其所有早期祖先（不论是来自Alice还是早先与其他人同步）之后。所以Alice不需要发送两个蓝色父事件的两个哈希值。告诉Carol这个事件是Alice的下一个事件就足够了，并且它的另一个父母是Bob的第三个事件。通过适当的压缩，这可以以很少的字节发送，仅增加发送消息的几个百分比来的大小。

4. 共识算法

确保每个成员都知道每一个事件是不够的，还需要就事件的线性排序以及事件内记录的交易达成一致。大多数没有领导者的拜占庭容错协议取决于每个人成员告知所有人他们的投票结果。因此，对于n个成员就单个YES/NO问题达成一致而言，可能需要通过网络发送O(n^2)个投票消息，因为每个成员都需要告诉其他成员投票结果。其中一些协议要求收到发给每个人的选票，使其成为O(n^3)。他们可能需要多轮投票，这进一步增加了发送的投票消息的数量。

图2. 哈希图数据结构。Alice创建一个事件（红色），记录Bob对她做的传播同步的事件，并告诉她他知道的一切。该事件包含两个父事件（蓝色）的散列：由同一个创建者Alice创建的父母（深蓝色），以及Bob创建的另一个父母（浅蓝色）。它还包含Alice当时选择创建的任何新交易的有效载荷，以及Alice的数字签名。其他祖先事件（灰色）不存储在红色事件中，但它们由所有哈希确定。其他自我祖先（深灰色）可以通过自我亲缘关系序列到达，其他祖先（浅灰色）则不是。

哈希图共识不需要发送任何投票。每个成员都有散列图的副本。如果Alice和Bob都具有相同的散列图，那么他们可以根据该散列图，通过函数计算并确定下所有事件的顺序，并且它们都会得到相同的答案。因此，即使不发送投票信息，也能达成共识。当然，在某个特定时刻，Alice和Bob可能没有完全相同的哈希图。他们通常会在较早的事件中达成一致，但对于最近的事件，互相可能还没有完全同步。此外，有时可能会向社区发布一个新事件，该事件被放置在散列图中较低（较早）的位置。哈希图形共识算法使用被认为最好的虚拟投票系统来处理这些问题。假设Alice具有散列图A和Bob散列图B。这些哈希图在任何给定的时刻都可能稍有不同，但它们将始终保持一致。一致意味着如果A和B都包含事件x，那么它们都将包含与x完全相同的一组祖先，并且都包含这些祖先之间完全相同的一组边。如果Alice知道x而Bob不知道，并且他们都诚实并积极参与，那么我们相信Bob会通过gossip协议很快地接收到x。共识算法假设最终会发生，但不会对其发生速度做出任何假设。该协议是完全异步的，并没有对超时时间，传播速度或进度进行假设。 Alice将通过一系列的选举计算来确定A中事件的总顺序。在每次选举中，A中的一些事件将被视为投票，同时A中的一些事件将被视为接受该投票。Alice将多次计算选举，因为某一事件可能参加一些选举而不参与其他选举，并可能在不同的选举中投不同的选票。如果这个事件是由Bob创建的，我们将会讨论Bob在特定选举中以某种方式进行了投票。但实际的鲍勃不参与。这完全是Alice在本地执行的计算，她计算出Bob发送出去的投票数。当然这建立在真的是Bob通过互联网向她投票的基础上。

图3. 强烈看到的插图。在每个哈希图中，顶部的黄色事件可以强烈地看到底部行中的一个橙色事件。有n = 5个成员，所以大于2n / 3的最小整数是4。在（d）中，一个事件（橙色）是不同创建者（红色）的4个中间事件中的每一个的祖先，每个事件都是黄色事件的祖先。因此，黄色事件可以强烈地看到橙色事件。其他每个哈希图都被着色，以显示底行不同的橙色事件，黄色事件至少会看到4个红色事件。如果所有4个橙色事件和黄色事件的父母都创建了一轮r，则在r + 1轮创建黄色，因为它可以强烈地看到r轮中由不同成员创建的超过2n / 3个证人。请注意，每个事件都被定义为自己的祖先和自我祖先。

这个虚拟投票有几个好处。除了节省带宽之外，它还确保成员总能够按照规则计算他们的投票。如果Alice是诚实的，她会真实地计算出Bob所做出的虚拟投票。即使真正的Bob是个骗子，他也不能通过虚假的虚拟投票来攻击Alice。 Bob可以尝试以不同的方式作弊。假设Bob创建一个事件x，其中自身父事件指向他以前的事件z。然后Bob创建一个新的事件y，也将自身父事件指向了z，而不是指向x。这意味着Bob在哈希图中的事件将不再是一个链。他们现在将成为一棵树，因为他创造了一个分叉。如果Bob将x传给Alice，然后y传给Carol，那么一段时间后，Alice和Carol可能还没有意识到这个分叉。这个时候，爱丽丝计算出来的关于x的虚拟投票，与Carol对y的虚拟投票计算结果不同。哈希图的一致性算法通过使用一种状态观念来看一个状态这种方式来防止这种攻击，并且一个状态的观念是可以强烈地看到另一个状态的。这些基于对祖先和自我祖先的定义，以致每个事件都被认为是自己的祖先和自我祖先。##译者注如果Bob创建两个事件x和y，这两个事件都不是另一个的自我祖先，那么Bob就会被分叉作弊。如果某个事件w有x作为祖先，但没有y作为祖先，那么事件w可以看到事件x。然而，如果x和y都是w的祖先，那么w被定义为不会看到它们中的任何一个，也不会被同一个创建者看到任何其他事件。换句话说，如果x能够看到w的话，w可以看到x，而且不知道是谁创建了分叉。如果有n个成员，那么事件w可以强烈地看到事件x，如果w可以看到不同成员的超过2n/3个事件，其中每个成员都可以看到x。这个概念如图3所示。该图显示了相同哈希图的四个副本，每个在底部行上以不同的事件着橙色。在（d）中，顶部的黄色事件可以由不同的成员看到4个红色事件，每个事件都可以在底部看到橙色事件。（a），（b）和（c）中也是如此，其中（a）实际上有5个红色事件。但只有4个人需要强烈观察，因为这个例子有n = 5个成员，大于2n / 3的最小整数是4。这个概念允许一个协议通过本地虚拟投票而无需任何实际投票就能实现拜占庭容错。在虚拟投票中，在事件x中，对某个YES/NO问题进行了投票（例如，不管事件是否有名），投票计算纯粹是作为x的祖先的函数。如果w可以强烈地看到x，则该投票仅被认为是从x可以连接到它的后代事件w。在第5节中证明，如果x和y在不同的分叉上，那么w可以强烈地看到x和y中的一个，但不能同时看到这两个分支。此外，如果哈希图A和B一致，则同一个事件不可能既可以强烈地看到A中的x，而另一个事件可以强烈地看到B中的y。这个引理是拜占庭证明的基石。它确保即使攻击者试图通过分叉作弊，他们仍然无法让不同的成员根据不同的顺序做出决定。从历史上看，一些拜占庭协议算法要求成员向每个人发送他们收到的每一张投票的“收据”，以防止Alice向Bob和Carol发送不一致的投票。这种攻击在哈希图分叉攻击上，以及使用收据和使用强烈看到之间有一些相似之处。鉴于这些定义，完整的哈希图共识协议可以由图4,5,6和7中的算法给出。图4中的主要算法表明通信非常简单：Alice随机挑选另一名成员Bob，并向他传达她所知道的所有事件。Bob然后创建一个新的事件来记录这个gossip的事实。这个简单的gossip协议足以支持拜占庭容错和正确性。同时它也可以以各种方式扩展, 以提高效率。例如, Alice和Bob可能会告诉对方, 他们已经知道的事件, 然后Alice只需要发送给Bob所有她知道而他不知道的事件。该协议可能要求Alice以拓扑顺序发送这些事件, 因此Bob在接收事件之前总是会有一个事件的父级。协议甚至可能要求, 在Alice 同步到Bob之后, Bob将立即同步回Alice。多个同步可能会立即发生, 因此Alice可能会同步到多个成员, 同时几个成员也正在同步到她。这些以及其他优化都可以使用, 但这一简单的要求实现就已经足够了。在每次同步之后, 该成员调用三个过程来确定尽可能多的事件的协商一致顺序。这些不涉及交流，只是纯粹地在本地计算就足够了。在这些过程中，每个for循环都以拓扑顺序访问事件，在这种情况下，事件总是在其父级之后访问。在算法的第一个for循环中，如果x是所有历史记录中的第一个事件，那么它将不会有父级或前几轮，因此应该将其设置为 x.round = 1 和 x.witness = TRUE。该算法还使用常量n，代表所有成员数目，c是大于2的常数, 如 c = 10。在下面的算法中, 拜占庭协议是达成相同概率的保证。将每个事件的循环数定义为其祖先的函数是有用的。在divideRounds（图5）中，每个已知事件都被赋予一个回合整数（定义5.2），作为其祖先的整数的函数。图3中的哈希图显示了如何完成。如果最下面的所有事件都是回合制的，那么这些数字中的所有其他事件也将是回合的，除了黄色事件，它将是r + 1。黄色事件前进到下一回r + 1，因为它能够强烈地看到来自r回的超过2n / 3个事件。历史上的第一个事件被定义为第一回合，所以未来的所有回合都由此决定。每个事件最终都会有一回合创建和一回合接收的数字。所创建的回合也被称为回合或回合数。对于任何给定的成员，他们在每轮中创建的第一个事件称为证人。只有证人事件发送和接收虚拟投票。这发生在图6所示的decisionFame过程中。此过程是拜占庭协议发生的地方。对于每个证人，决定它是否出名的是：如果许多证人在下一轮能够看到它，该证人就很有名，如果许多证人无法看到，它就不会出名。拜占庭协议协议为每个证人进行选举，以确定它是否有名。对于第r轮中的证人x，第r + 1轮中的每个证人都会投票表明是否能够看到x，如果看到它就是有名的。如果超过2n/3就是否知名达成一致，那么可以宣告选举结束。如果表决达到一个平衡，那么它会根据需要继续进行多轮，每个证人在正常轮次投票中根据其在上一轮中可以看到的大多数证人进行投票。为了防御可以控制互联网的攻击者，有定期的硬币轮，证人可以伪随机地投票。这意味着，即使攻击者可以控制所有通过互联网传递的信息，以保持投票的谨慎分裂，社区仍然有可能随机跨越2n/3的阈值。最终达成协议的一致概率。在图6中，如果将行“if d = 1”更改为“if d = 2”，算法将继续工作。在该修订算法中，每次选举将在一轮后开始。如果两者在以下混合算法中组合，它甚至会继续工作。在每轮中，首先用“d = 1”检查运行其所有选举。如果这一轮中每个证人的名气都已经确定，并且在那一轮中有2n/3或更少的成员创造了有名的证人，那么这一轮的选举就全部重新开始，使用a，d = 2来验证。对于这种混合算法，本文中的所有定理都将继续保持真实，包括拜占庭容错的证明。对于引发新选举的轮次来说，达成共识的时间会稍微增加（大概增加20％）。但在实践中这种情况很少发生，如果发生这种情况，可能会增加著名证人的数量，以确保公平。一旦就特定回合中的每个证人是否出名达成共识，那么使用它可以很容易地确定一个一致的时间戳，并且对较早事件的顺序达成共识。这由findOrder过程完成，见图7。

图4 Swirlds哈希图共识算法。每个成员反复呼叫随机选择的其他成员，并与其同步。向外同步的同时，每个成员也在接收传入的同步信息。当Alice与Bob同步时，她发送她知道Bob不知道的所有事件。Bob将这些事件添加到哈希图中，并且只接受包含他拥有的有效父哈希的有效签名的事件。所有已知的事件然后被分成几轮。然后，每一轮每个成员（“证人”）的都会对这轮的第一个事件，执行本地拜占庭式协议，通过虚拟投票来决定是否著名。然后对拥有足够可用信息的事件，进行排序。如果两位成员单独给某个事件分配一个位置，他们将保证分配的是相同的职位，并保证永远不会改变职位，即使后面有更多的事件进入。最终，每个事件都会以一个相同的概率被分配到这样一个位置上。

首先，计算收到的回合。如果这是所有独特的著名证人都是其后代的第一轮，并且每个证人的名气都被确定为小于或等于r的回合，则事件x已经接收到一轮r。（一轮中独特的着名证人的定义与一组着名证人的定义相同，只是如果该成员在该回合中有一个以上着名证人的话，那么来自给定成员的所有着名证人都将被删除。）然后，计算接收到的时间。假设事件x有一个r的接收轮，Alice在r轮创建了一个独特的着名见证y。该算法找到z，它是学习了x的y的最早的自我祖先。假设t是Alice创建z时放入z的时间戳。那么t可以被认为是Alice声称第一次学习x的时间。x的接收时间是所有这些时间戳的中位数，对于r轮中唯一著名证人的所有创建者。然后计算一致性顺序。所有的事件都按他们收到的一轮排序。如果两个事件有相同的接收轮次，则按接收时间排序。如果仍然存在关系，那么在签名被与接收回合中所有独特的着名证人签名异或之后，通过简单的签名排序就可以打破关系。

图5 divideRounds程序。只要事件x已知，就会分配一个回合数字x.round，并计算布尔值x.witness，指出它是否是“见证事件”，即该成员是否是该轮中创建的第一个事件。

5. 拜占庭容错证明

本节提供了许多有用的定义，其次是几个证明，从强烈看见引理（引理5.12）到拜占庭容错定理（定理5.19）。在证明中，假设有n个成员（n>1），其中超过 2n/3 个是诚实的，并且其中不到 n/3 是不诚实的。还假定数字签名和密码哈希是安全的，所以签名不能被伪造，签名的消息不能被检测而改变，并且哈希碰撞永远不会发生。同步gossip协议被假定为确保当Alice向Bob发送她知道的所有事件时，Bob只接受那些具有有效签名并包含与他拥有的事件相对应的有效哈希。该系统完全异步。假定对于任何诚实的成员Alice和Bob，Alice最终将尝试与Bob同步，并且如果Alice反复尝试向Bob发送消息，她最终将成功。对网络可靠性或网络速度或超时时间没有其他假设。具体来说，允许攻击者完全控制网络，任意删除和延迟消息，但要受限于反复发送的诚实成员之间的消息必须最终具有其通过的副本。

定义5.1：如果x是y，则事件x被定义为事件y的祖先，或者是y的父亲，或者是父亲的父亲，等等。如果x是y，或者是y的自身父母，或者是y的自身父母的自身父母等，那么它也是y的自身祖先。 An event x is defined to be an ancestor of event y if x is y , or a parent of y , or a parent of a parent of y , and so on. It is also a self-ancestor of y if x is y , or a self-parent of y , or a self-parent of a self-parent of y and so on.

定义5.2: 一个事件x的回合创建数（或轮）被定义为r + i，其中r是x的父辈的最大轮数（如果没有父代，则为1），如果x可以强烈地看到r轮中超过2n / 3个证人（如果不能，则为0），那么i就是1， The round created number (or round) of an event x is defined to be r + i, where r is the maximum round number of the parents of x (or 1 if it has no parents), and i is defined to be 1 if x can strongly see more than 2n/3 witnesses in round r (or 0 if it can’t).

定义5.3: 如果所有独特的著名证人都是x的后代，那么事件x的回合数(或者轮)就是1。 The round received number (or round received) of an event x is defined to be the first round where all unique famous witnesses are descendants of x.

图6.DecideFame程序。对于每个见证事件（即，其中x.witness为真的事件x），决定它是否是有名的（即，将布尔分配给x.famous）。这个决定是通过基于虚拟投票的拜占庭协议协议完成的。每个成员在本地运行它，在他们自己的哈希图副本上，没有额外的通信。它将哈希图中的事件看作是彼此发送的投票，尽管纯粹是成员在本地计算的的。该成员为每轮回合的证人分配选票数次，直到超过2/3的人口同意。为了判断x是否有名，在持续增长的哈希图上反复重复这个操作，直到x.famous被判定。

定义5.4: 一组事件 (x, y), 如果x和y拥有相同的祖先，而且他们互相都不是对方的自我祖先, 那么这是一个分叉(fork)。 The pair of events(x, y) is a fork if x and y have the same creator, but neither is a self-ancestor of the other.

图7。findOrder程序。一旦r轮中的所有证人都有了名气，那么在那一轮中找到一组着名的证人，然后从该组中删除与该组中任何其他著名证人相同的创造者（去除重复的创建者）。其余的著名证人是独特的著名证人。他们担任评委，接受一轮事件和达成共识时间戳。所有独特的着名证人收到它的第一轮“接收”事件，如果所有先前的轮次都有所有决定的证人的名气。它的时间戳是每个成员第一次收到它的事件时间戳的中间值。一旦计算出来后，这些事件就按照收到的一轮进行排序。任何关系都按照一致的时间戳进行分类。任何剩余的关系都是由白色签名来划分的。白色签名是与接收回合中所有唯一着名证人签名异或的签名。

定义5.5: 一个诚实的成员会一直尝试着与其他成员进行同步，并在每次同步后创建一个有效事件（使用最新的自身父母和其他父母的哈希），并且永远不会创建两个彼此分叉的事件。 An honest member tries to sync infinitely often with every other member, creates a valid event after each sync (with hashes of the latest self-parent and other-parent), and never creates two events that are forks with each other.

定义5.6: 如果y是x的祖先，则事件x可以看到事件y，并且x的祖先不包括y的创建者的分叉。 An event x can see event y if y is an ancestor of x, and the ancestors of x do not include a fork by the creator of y.

定义5.7: 如果x能够看到y，并且在超过2/3的成员中有一组事件S，x可以看到S中的每个事件，并且S中的每个事件都可以看到y，那么事件x可以强烈地看到事件y。 An event x can strongly see event y if x can see y and there is a set S of events by more than 2/3 of the members such that x can see every event in S, and every event in S can see y.

定义5.8：见证是指某一轮中一个成员创建的第一个事件。 A witness is the first event created by a member in a round.

定义5.9: 一个著名的证人是由社区来决定的，使用这里描述的算法。非正式地，如果许多成员在下一轮开始时看到证人，社区往往会认定证人是有名的。一个唯一的著名的见证的创建者在这一轮中所有著名见证中应该只会出现一次。在没有分叉的情况下，每个著名的证人都是一个唯一的著名证人。 A famous witness is a witness that has been decided to be famous by the community, using the algorithms described here. Informally, the community tends to decide that a witness is famous if many members see it by the start of the next round. A unique famous witness is a famous witness that does not have the same creator as any other famous witness created in the same round. In the absence of forking, each famous witness is also a unique famous witness.

定义5.10: 如果两个哈希图中包含的任何事件x都包含相同的x祖先，并且在这些祖先之间具有相同的父亲和自身父亲边缘，则哈希图A和B是一致的。 Hashgraphs A and B are consistent if for any event x contained in both hashgraphs, both contain the same set of ancestors for x, with the same parent and self-parent edges between those ancestors.

引理5.11: 所有成员都有一致的哈希图。 All members have consistent hashgraphs.

引理5.12: （强烈的看见引理）如果一组事件(x, y)是分叉，而且在哈希图A中，x能够被事件z强烈的看到，因此，在和A相同的哈希图B中，y将不能被任何事件强烈的看到。 if the pair of events (x, y) is a fork, and x is strongly seen by event z in hashgraph A , then y will not be strongly seen by any event in any hashgraph B that is consistent with A.

引理5.13: 如果哈希图A和B一致，而且都包含x事件，那么两者都会对x得到相同的回合数。 If hashgraphs A and B are consistent and both contain event x, then both will assign the same round created number to x.

引理5.14: 如果A和B一样，在A中的算法显示，在r轮中，成员m(0)投了v(A)票，给在r+1轮的成员m(1)，而且在B中的算法显示，m(0)在r轮的时候，投了v(B)给r+1轮中的m(1)的事件，则可以得出 v(A) = v(B)。 if hashgraphs A and B are consistent, and the algorithm running on A shows that a round r event by member m(0) sends a vote v(A) to member m(1) in round r + 1, and the algorithm running on B shows that a round r event by member m(0) sends a vote v(B) to an event by member m(1) in round r + 1, then v(A) = v(B).

引理5.15: 如果哈希图A和B是一致的，并且A决定好了在r回合中结果为v的拜占庭协议选举，并且B在r之前还没有决定，那么B将在r + 2回合或之前决定v。 if hashgraphs A and B are consistent, and A decides a Byzantine agreement election with result v in round r and B has not decided prior to r , then B will decide v in round r + 2 or before.

定理5.16: 对于任何单一的是/否问题，最终以相同的概率达成共识。 For any single YES/NO question, consensus is achieved eventually with probability 1.

定理5.17: 对于任何轮r，在r + 3轮中至少有一个事件的哈希图，那么在r轮中至少有一个证人会被共识算法著名，这个决定将由每个 r+3 轮中的或更早轮中的见证人决定。 For any round number r, for any hashgraph that has at least one event in round r + 3, there will be at least one witness in round r that will be decided to be famous by the consensus algorithm, and this decision will be made by every witness in round r + 3 , or earlier.

定理5.18: 如果哈希图A不包含事件x，但确实包含x的所有父项，并且哈希图B是加了x的结果，并且x是在r轮创建的证人，并且A在r轮中至少有一个证人其名气已经决定（无论是着名的还是不知名的），那么在B中x将被定为“不出名”。 If hashgraph A does not contain event x, but does contain all the parents of x, and hashgraph B is the result of adding x to A, and x is a witness created in round r , and A has at least one witness in round r whose fame has been decided (as either famous or as not famous), then x will be decided as “not famous” in B.

定理5.19: （拜占庭容错定理）。由诚实成员创建的每个事件x最终将以相同的概率按被纳入到所有事件的总顺序中。 (Byzantine Fault Tolerance Theorem). Each event x created by an honest member will eventually be assigned a consensus position in the total order of events, with probability 1.

Hashgraph-DAG共识算法