简介

分布式数据库通常要求具有拜占庭容错的状态机复制。一些人定义“Byzantine”这个术语时会加一些假设，例如假设攻击者不会串通，或者通信是弱异步即非完全异步。在本文中，按照严格意义上的“Byzantine“含义来定义：

• 只有不到1/3的成员可以成为攻击者
• 攻击者可以相互勾结
• 攻击者可以删除或无限延迟诚实成员之间的信息转发
• 攻击者可以控制网络来延迟和删除任何消息
• 在任何时候，如果一个诚实的成员多次向另一个成员发送消息，攻击者最终必须允许其中一个通过（注：不是太理解该句的含义）
• 假设存在安全的数字签名，使得攻击者不能篡改消息数据
• 假定存在安全hash函数，对于这些散列函数永远不会发生冲突。

本文提出并描述了Swirlds hashgraph的共识算法，并遵守上面严格的定义下证明了拜占庭容错性。

非确定性的拜占庭系统可以是完全异步的（注：例如比特币以太坊的PoW），消息可以无限时延，达成共识的方式是不断共识出新的数据，对之前的数据进行’确认‘，使得前面的数据被篡改的概率越来越低（注：永远不会最终确定，只是概率无限趋于0）。hashgraph的共识也是完全异步的，非确定性的。

完全异步的系统肯定会产生分叉，不管是攻击者故意分叉，还是正常节点刚好同时产生新数据，因为大家都在独立生成最新的数据，那么选择哪一份数据作为主干留下来，哪一份作为分支修剪掉。因为数据分叉后还是会广播给全网， 假设分叉数据是A、B，一些节点先收到A，就基于A去解一个数学难题，一些节点先收到B，就基于B去解一个数学难题，根据各个节点的计算算力决定谁能解出来的概率大小， 注意是概率， 不是算力越大就一定是它先解出来。而计算机越多，算力越分散，就越不容易被控制计算结果（当然现在矿池的存在导致了算力集中化），这样在一个相对公平的条件下谁先解出难题就决定A还是B作为主干，例如节点N基于A接触来了，得到数据是C，那么C被广播出来后， 任何基于数据B的节点都会抛弃之前的计算，重新根据数据C进行下一轮计算。PoW对应上述描述中的数据即区块， 计算即挖矿。当然这种分叉解决方式也会降低出块速率， 并浪费大量的无效计算。

而传统拜占庭协议没有分叉问题， 因为节点之间对每一轮都要通过交互消息来投票选择哪个是主干，哪个是分支，hashgraph也采用这种思想，但使用了本地虚拟投票的方案解决了节点之间消息交互的问题，节约带宽，提高吞吐量。

核心概念

• 交易。任何节点在任何时候都可以创建一个签名交易，所有节点收到该交易的拷贝，对所有交易生成抗拜占庭的全局排序。
• 公平性。对于小范围内的攻击者，很难影响交易的排序公平性。
• gossip。每个节点随机选择所连的peer，并不断传播他们所知道的所有信息。
• hashgraph。是一个数据结构，记录了谁和谁之间传播了数据，以什么顺序传播的。
• gossip的gossip。hashgraph本身的数据通过gossip传播，也就是gossip本身的历史记录，这样比每次传播一个交易要节省很多带宽。
• 虚拟投票。每个节点根据存储的全局hashgraph数据，可以计算出peer预期的投票信息，这样不用等peer将投票信息发过来， 在本地就可以一步全局共识。
• 知名见证人（famous witnesses）。全网对n个交易进行排序，需要相互询问“事件x是不是在事件y前面？”，得到yes、no的回答，复杂度是O(n log n)。一种更快的方法是选取少数事件（hashgraph中的顶点）称为见证人。知名见证人的定义是该事件被创建后很快被大多数节点收到，那么该事件就是知名的。节点对见证人按照拜占庭协议运行：询问该见证人是否是知名见证人，得到全部明确答复之后，就很容易从hashgraph中派生出所有事件的全局顺序。
• 强看见（strongly seeing）。给定2个顶点：x,y，可以很快计算出x是否可以强看见y： x和y是否通过多条直接路径连接在一起，（注：从x回溯找到所有祖先，它们分布在超过2n/3的节点上，并最终回溯到y， 也可以理解为事件y被传播到了>2n/3的节点上）。这个定义可以证明：如果A，B都可以计算C对给定问题的虚拟投票，那么A，B也会给出相同的投票。

gossip的gossip：hashgraph

hashgraph使用gissip协议：Alice随机选择一个已连接的peer，例如Bob，然后告诉Bob所有Alice知道的信息（注：例如新创建的交易），然后Alice继续随机选择另一个peer， 重复发送她知道的信息。Bob和其他节点也一样传播出去， 知道全网都收到这个新的信息。

gossip协议传播的历史最终生成一个有向图：

image.png

节点Alice上的每个顶点代表一个gossip事件，Alice中最上面的事件代表Bob执行一个gossip同步信息给她，这个顶点有2条向下的边，代表Alice和Bob之间的gossip传播，下面的顶点代表早期事件的gossip。

在hashgraph中， 这个图是一个数据结构。每个事件（顶点）由创建者签名后存储在内存中。例如红色的顶点是Bob执行gossip同步后发过来的，该事件由Alice创建并签名，事件中包含：

• 2个hash：就是2个蓝色节点的hash
• Alice选出来的打包进来的新交易

红色事件的其他祖先（灰色顶点）信息不包含在红色事件中，但是决定了hash值。像这种hash图和Git也很类似：顶点是文件树的一个版本，边代表修改， 只是Git存储及诶单之间的相互通信记录。而hashgraph则会保存。

gossip协议可以传输个各种各样的信息，比如用户标识，交易，区块等等信息。但如果用来传播gossip本身的传播记录呢？用来传播hashgraph数据本身呢？传播hahsgraph可以携带大量的信息，比如在hashgraph中携带新的交易，Alice不仅可以得到新的交易信息，也可以知道Bob是在何时得到该交易的，也可以知道Carol是在何时得到“”Bob在何时得到该交易“”的信息。随着hashgraph不断向上生长，节点可能在短时间内会保持不同的最新的事件，当他们很快会汇集到全部下一级的hashgraph数据。进一步来说，Alice和Bob同时得到一个事件，可以确保拥有完全相同的祖先，保证所有支持拜占庭容错的算法都在本地运行，不需要和其他接待进行交互，解决大量的通信带宽和延时，通信信息也可以少很多：AliceU需要对每个交易进行签名并传播，而只需要把所有交易放在事件中，签一次名传播出去即可，而事件中也还需要携带本身的hash即可， 不用携带祖先的hash。