hashGraph共识算法介绍和技术细节

hashGraph共识

1. 前沿和背景

Hashgraph算法最早是由Leemon Baird博士在2016年发表的一篇论文“The Swirlds Hashgraph Consensus Algorithm: Fair, Fast, Byzantine Fault Tolerance”上公开，根据其介绍，Hashgraph 算法实现了异步拜占庭容错（ABFT），因而能容纳非常高的吞吐量并能非常快速的处理交易，官网提供的数据显示，在真实环境下可以达到惊人的250k TPS。

1. 简介

根据原作者发布的白皮书介绍，Hashgraph 仅是一个算法的名字，它既不是区块链项目(比如比特币，以太坊这种完整的可运行的系统)，也不是开源的，它是由发明它的 Leemon Baird博士所创建的Swirlds.Inc公司负责掌控，并运营在 Hedera 项目（https://www.hedera.com）之下。Hashgraph 是一种异步拜占庭容错算法（ABFT），它跟我们目前常见的 PBFT 算法最大的不同就是它是完全异步的。我们知道 PBFT 算法能支撑的网络规模是非常有限的最大原因就 PBFT 模型的通信复杂度是 O(N^2），随着节点数量的增加，需要通信的消息数量呈指数级别的上升。而 Hashgraph 突破性的抛弃 PBFT 中使用的消息同步机制，使用异步 BFT，通过保证最终确定性来确保算法的高效和安全。

Hashgraph 采用的是 DAG 数据结构，Hashgraph 最特别的一点是，它无需中心权威节点，而是依靠独特的 Gossip about Gossip 和 Virtual Vote 两大机制来保证了算法可以在纯异步的环境中高效运行，并且通过绝对多数（超过 2/3 节点）强可见机制来保证了共识结果的正确性和安全性。

1. 算法原理

在介绍算法之前，先了解论文中所提出的一些概念，Event，这个是 Hashgraph 中最基本的元素和概念。在 Hashgraph中，使用一种叫Event的数据结构来代替我们常见的区块链（比如比特币）中的Block概念。Event由每个节点自行创建，它主要包含四类元素：交易集合，时间戳，以及对两个Parent Events 的引用哈希。

在传统的区块链中，新产生的区块只能是只能有一个先导区块的，Hashgraph 中，每个Event必须要链接两个parent Events，其中一个必须是自己，而另一个则可以是任何一个从其他节点发来的Event。我们来对比一下传统区块链的结构和Hashgraph的结构之间的区别，如下：

下面我们一一讨论hashgrap算法的一些重要概念

Gossip About Gossip

Gossip简单来说就是，节点随机选择一个可以连接的邻节点，向其发送一条信息(Event）。而Gossip about Gossip则是，收到 gossip信息的节点，对该 gossip信息进行签名，并且再把该签名打包进一个新的信息中，并随机发送给网络中的任一节点。这样，每个节点发出的Gossip信息都包含了对其收到的前一个Gossip信息的签名验证，实际上就是做了一个见证工作（Witnessing）。注意这里的Gossip过程是非常简单的，收到Event信息的节点可以向任意一个或多个节点继续Gossip新的 Event。每一次Gossip都是对前一次信息的背书和见证。

Local hashgraph copy

参与共识的每个节点都会保存一份完整的hashgraph副本图，初始时每个节点上的这个副本图都是空的，当开始有节点产生Event之后，就会在自己的hashgraph副本图上进行记录。比如，每个节点都创建第一个Event时，他们各自的副本图如下:

当A收到C发来的Event时，A就会更新本地的hashgraph副本，如下:

同时，A还会基于Event a1和Event c1创建一个新的Event，并Gossip 出去，如下：

假设刚才在A收到C的Event时，C也收到了D的Event，那么各个节点的hashgraph副本图则会显示如下：

某个时间点之后，大家都收到了彼此发给对方的消息：

可见，在节点相互Gossip通信的过程中，它们各自hashgraph副本的内容都不尽相同，但是有一点非常重要的就是，每个节点都会忠实的记录自己所创建的所有Events。比如上图中的节点A和B，A记录了自己所创建的所有Events，即a1和a2，而B 同样记录了自己所有的b1和b2。但是A缺少B的所有Events，而B则缺少A的最新Eventa2。并且，A准备更新自己副本上B这部分的数据时，发现自己缺少B这部分前序的数据，因此，B会把它的历史数据同步给 A。而B的副本上由于已经有a1了，因此在收到a2之后无需再同步。最终，hashgraph就会更新成如下状态:

可见

由于hashgraph中，所有events都会引用两个parent events，因此，如果一个child event y可以回溯到某个ancestor event x，那么就说y可见x。

强可见

当事件Y能找到事件X的所有路径中跨越了绝对多数的节点，那么事件Y强可见事件X。比如下图，想要判断 b5 是否强可见 c1:

我们需要做的就是，把所有从b5能可见c1的路径都找出来，如果这些路径集合中，能够包含超过 2/3 的节点（也就是要包含至少4个节点），那么就说b5强可见c1。如下：

可以看到，b5 有3条路径都能可见 c1，这3条路径经过的节点分别是path1: (B, C)，path2:(B, D, C), path3(B, E, C)，这三条路径一共经过了 B, C, D, E 4 个节点，满足超过 2/3 节点的要求，因此，可以确认事件 b5 强可见事件 c1。

轮次Round

在Hashgraph中，根据事件所处的可见状态，把他们分为不同的轮次（Round）。当一个事件强可见绝对多数节点上的第一个事件时，我们就说该事件在一个新的轮次上，记为R。（比如初始状态时，所有节点均一致，就可以把它定义为是一个新的轮次，标记为 R。）我们通过一个示意图来更好地理解轮次的概念：

上图中，事件a5和d3强可见了R轮的 a1, b1, c1, d1 共4个事件，也就是说强可见了绝对多数节点的第R轮的第一个事件，因此，a5和d3就在一个新的轮次 R + 1 上。

创建轮次

所谓的创建轮（Creation Round），就是当一个事件被创建时，它所在的轮次。通常，一个事件被创建时，它会被立即赋予一个轮次号，它跟其父事件是在同一个轮次。也就是说，如果该事件的父事件是 R 轮，那么该事件的创建轮就是 R 。比如，上图中，初始情况下，所有节点的状态都是相同的，把它定义为第R轮（R = 1），后续创建的事件都是在第R轮的。

接收轮（Receive Round）很好理解，就是当某个事件强可见超过 2/3 节点的本轮或者上一轮的事件时，这个事件就达到了一个新的轮次，这个轮次就是他的接收轮。如下图：

从上图中，我们可以看到，当a5和d5被创建时，它们的创建轮是第R轮，而当它们能够强可见绝对多数节点的第R轮的见证人事件（即 a1, b1, c1, d1）时，它的接收轮就变为R + 1轮，也就是说，a5和d5 都变成R + 1轮的事件了，并且，在它们之后创建的子孙事件都在R + 1轮。

这里需要注意的是：如果事件a5只能强可见 R 轮某节点的见证人时，a5的轮次是不会增加的，依然为此在R轮。只有当其强可见绝对多数节点的第R轮的见证人，它的轮次才变为R + 1轮。

见证人和知名见证人

见证人（Witness），就是第 R 轮所创建的第一个事件。比如上图的 a1，b1，c1, d1 和 e1，它们都是各自节点的见证人事件。

知名见证人（Famous Witness），当 R 轮的见证人事件被 R + 1 轮的多数（超过 2/3）见证人强可见时，它就是知名见证人事件。

由上图我们可以看到，c1被R +1轮的大部分见证人事件强可见，因此c1就是知名见证人。我们注意到这里暗含了一个强约束条件，就是R + 1轮的见证人事件，这意味着[a5, b5, c5, d5]这几个事件必然是强可见大部分节点的第R轮见证人事件的，但不必然强可见c1（比如他们都强可见 [a1, b1, d1, e1]这4个见证人事件。所以，要判断c1是否是知名见证人，就必须要求R + 1轮的大部分事件都强可见c1，一旦满足，说明c1就是知名见证人了，知名见证人意味着不可更改，这时候系统就可以对该事件进行commit。

虚拟投票（Virtual Vote）

上述 Event 状态变迁和系统状态变迁的过程其实也包含了投票的过程，投票是在上述状态变迁过程中完成的。根据上述的算法介绍，我们知道一个 Event 的状态变迁过程是这样的：

可见 -> 强可见某祖先 Event -> 强可见绝对多数节点的祖先 Events -> 轮次增加（即 Round + 1） -> 大多数 R+1 轮 Witness 强可见 R 轮某个 witness -> R 轮该 Witness 成为 famous witness -> commit。

虚拟投票实际上就是指上述两个黄色部分。可以看到，它主要是分为两个步骤来进行的：① 处相当于 Pre-Vote 过程，这里其实是确定投票委员会成员，如果一个事件强可见大多数 witness，那么它对某 witness 的票就有效。

② 处则是 Pre-Commit 过程，收集投票委员会对某个祖先 Event 所投的票，如果票数超过 2/3，那么就可以把该 Event 标记为 Famous，也就是不可更改了。接下来只需要 commit 就行了。

注：R + 1轮的Witness只会对R轮的Witness 投票，R轮Witness后续的Events不会收到投票。Witness是指R轮创建的第一个Event，如下：

现在，我们来看一下想要把R轮的c1标记为知名见证人需要经过哪些步骤：

1）判断每个节点满足 R + 1轮的Event

这是一个对当前节点的各 Event 进行不断回溯验证的过程。

2）判断每个节点中，R + 1的Event是否强可见c1，如果强可见，那就相当于Vote Yes。

3）计算Vote数量，如果超过 2/3 的Event都投票 Yes。就把c1标记为 Famous。

计票

计票过程是在 R + 2轮进行的。因为即使R + 1轮所有Event都强可见c1，它们彼此之间也互相不知道对方的投票情况。因此，必须由下一轮的Event来收集大家的投票结果。

由上图可见，R + 1轮的[a5, b5, c5, d5]以绝对多数的比例对c1形成了强可见状态，使得c1满足知名见证人人条件。R+2轮上的每个见证人则对R+1轮的见证人收集投票。如图，R + 2轮的见证人a9，它强可见了R + 1轮的那四个强可见c1的事件，因为数量已经达到绝对多数的要求，因此a9可以立即确认c1事件，也就是说，c1已经达到全网共识而且不可更改。

注：Hashgraph根据数学理论证明，任何一个R + 2轮见证人如果对投票结果做出了决定，那么这个结果就是全网的结论，如果这轮见证人无法做出决定，就由下一轮见证人计票决定，直到得出确切结论。

事实上，R + 2轮这个收集投票的过程只是一个学习共识结果并进行提交（commit）的过程，因为一旦知名见证人被确定，剩下的过程就只是各个节点把这个结果进行提交而已了。