Hashgraph —— 或许是目前最为优秀的共识协议

摘要：同时因为所有节点都是对等节点，避免了潜在的攻击风险。创建轮次一个事件的创建轮次是或者，其中是该事件父节点的最大轮次。

在深入探索Hashgraph之前，我们先聊聊关于共识协议的背景，众所周知比特币和以太坊目前都采用POW共识机制，如果暂不考虑大矿场联合做些小动作，工作量证明机制确实是个非常安全的协议，简单粗暴的算法设计从经济收益层面杜绝了几乎99%的潜在攻击，比特币网络从2009年运行至今几乎没出过什么严重的BUG，即使从软件代码上来看也称得上是一个相当可靠的系统。然而随着整个网络资源规模飞速增长，POW机制带来的资源消耗问题越来越难以忽视。摩根士丹利在2018年1月发布的一份研究报告中指出，2017年比特币挖矿业务共消耗了36太瓦时的能源，相当于卡塔尔一年的能源消耗量，预计2018年的电力需求将增至三倍以上，与阿根廷全国一年能源消耗量相当。POW机制引起的计算力消耗是否真的是毫无价值的能源浪费，对于这个问题社区存在不同的声音（V神在不同场合都发表过对资源浪费问题的重视，以太坊也正在准备向POS机制切换），小编对此保留意见，毕竟我不是专业的经济学家，但是对了达成全网共识是否真的需要消耗大量资源，我认为将来一定会出现更有效率的解决方案。

​ 再来看另一个应用颇多的POS系，包括BM在多个项目里采用的DPOS机制，诚然在资源消耗方面有了相当多的改进，但DPOS机制在去中心化方面远远不如POW，虽然牛逼如BM的大神多次提到一定数量的出块节点足以保证全网去中心化同时大大提高交易处理能力，但是我相信有权力与利益集中的地方一定不会那么风平浪静，并且存在了相对中心化的节点后，相当于是给攻击者框定了攻击目标，DPOS能否抵御各种系统性风险需要打个大大的问号。

​ 要从根本上提高去中心化系统效率，共识协议一定是个绕不开的话题，很多团队对此提出了很多不同的方案，Hashgraph就是其中之一，相比于其他还只有天马行空的想法，Hashgraph已经发布了可用的SDK。

​ 根据白皮书定义，Hashgraph是一种数据结构和共识算法。Hashgraph不是数字货币，也不是区块链（因为它其实是DAG图，并非是链式结构），严格说也不单单是协议。Hashgraph更像是一个底层的出块层而非一个完整的系统。Hashgraph的SDK中包含一个数字货币的Demo，但那仅仅用于演示证明Hashgraph可以用于构建数字货币。Hashgraph能为分布式APP提供高效、公平、安全的基础设施。高吞吐量和异步拜占庭容错（ABFT）的特点，使得Hashgraph在公链和私有链领域都有潜在的使用价值，并且，在保证去中心化的同时不需要繁重的工作量证明。

公平

采用一致的时间戳，每一个区块（实际上是事件，下文会谈到）以及区块里的每一笔交易都有顺序

安全

Hashgraph是一个ABFT系统，没有一个节点可以阻止网络达成共识或者在达成共识之后修改数据，号称能达到银行级别的安全性

速度

根据官网的测试数据，可以达到惊人的 250000 TPS

这里我们简单讲一下BFT算法，中文名拜占庭算法，不了解拜占庭将军问题的可以上网搜索下。我们知道因为FLP不可能定理（在网络可靠且存在节点失效的异步分布式系统中，不存在一个可以解决一致性问题的确定性算法），BFT算法中的节点通信基本都是同步的，并且虽然PBFT（实用拜占庭容错）大大优化了消息传播的复杂度，但是实际使用中差不多也就支持到100个节点就是极限了，因此BFT算法只适用于非公链场景，其次它本身对动态节点场景的处理也非常麻烦，而节点随意加入或者退出在公链环境下是非常常见的。那么Hashgraph究竟是如何实现异步BFT的呢，白皮书中hashgraph对共识定义做了一些放宽（还是得要适当的妥协啊~），在极小概率下共识算法可能会无限执行，但是这一概率几乎为0。Hashgraph的共识算法是非确定性的，但是能保证最终确定性，也就是说我虽然无法保证在某个时间点下所有节点状态保持一致，但我能保证在最终某个时刻下所有节点对某个时间点之前的网络历史达成一致。同时因为所有节点都是对等节点，避免了潜在的DDOS攻击风险。

谣言算法（Gossip about Gossip）

虚拟投票（Virtual Voting）

谣言算法

谣言算法也叫八卦算法，在分布式系统中式非常常见的概念，这里的谣言或者八卦之的是一段我知道但是另一个人不知道的信息，顾名思义，算法运行原理和实际生活中办公室八卦传播类似，当一个人知道一个八卦后，经过有限时间传播后，最后整个办公室都会知道这一八卦。

在Hashgraph中，每一个节点都在传播经过签名的新交易已经从临近节点接收到的交易信息。当某个节点收到包含新交易信息的数据后，会组合并可能添加自己所知道的交易成为一个新的事件（event，类似于比特币中的区块Block，为了便于理解，下文中的事件和区块都是指同一个东西）传播出去，并且这个事件包含两个哈希，一个指向该节点上次最新的事件，另一个指向该节点所收到的另一个节点的最新事件，然后对整个事件加上时间戳并签名，整个循环不断进行直到所有节点都获得相同的信息。

假设网络中有4个对等节点，P、Q、R、S，初始状态下各自都有一个新的事件

Q节点随机选择S节点传播消息，意思就是Q节点发送所有他自己知道而S不知道的信息给S，S确认消息后创建一个新事件，同时指向S和Q的最新事件。

S节点随机选择Q传播消息，这个消息包含三个事件

现在，Q节点收到了包含三个事件的消息，随着消息在节点间不断传播，整个Hashgraph结构可能会是以下样子，这是一个通过加密哈希值连接的图，因此叫做哈希图（Hashgraph）

虚拟投票

上面我们看到了Hashgraph如何在节点之间通信，但这仅仅只是通信步骤，节点之间达成共识还需要虚拟投票机制，为什么说是虚拟投票，因为通过执行谣言算法后所有节点都是全节点，都存储了完整的网络历史，在需要对某一提案达成共识时并不需要大规模的消息通信，每个节点独立执行投票算法，并且所有节点一定会得出相同的共识结果。在讨论具体的投票步骤前，有必要列下Hashgraph白皮书中描述的相关术语，不然真的会看得云里雾里，我将尽可能地说人话

事件（event）

在上面的谣言算法中我们已经接触到了这个概念，类似于比特币中的区块，事件是一个包含有两个哈希指针的数据结构，并且可以包括0个或若干交易信息，节点在创建事件的同时会加上时间戳并且对整个事件数字签名

绝对多数（supermajority）

超过2/3以上节点的数量，在很多DPOS系算法上也有这个概念

可见（seeing）

当事件B可以沿着哈希指针找到事件A，那么事件B就可见事件A

强可见（ strongly seeing）

当事件B能找到事件A的所有路径中跨越了绝对多数的节点，那么事件B强可见事件A。白皮书中提到经过数学论证可以保证两个强可见的节点在虚拟投票时能获得一致的结果

见证人（witness）

每个节点在每个轮次中创建的第一个事件就是见证人事件，即该轮次的祖先事件，节点可能在某个轮次中没有见证人事件

知名见证人（famous witness）

如果R轮的见证人能被绝对多数的R+1轮见证人可见，则它就是知名见证人。具体的计算方法详见后文。

创建轮次（round created）

一个事件的创建轮次是R或者R+1，其中R是该事件父节点的最大轮次。当且仅当事件能强可见绝对多数的R轮见证人，则该事件的创建轮次为R+1。

接受轮次（round received）

如果R轮（创建轮次）中的所有知名见证人可见某一普通事件，则该事件的接受轮次就是R轮，如果某普通事件没有被R轮所有知名见证人可见，则它的接受轮次一定晚于R轮

一个投票过程的例子

下图已经划分好了各个创建轮次，图中的DAG图自下而上增长，关于如何划分创建轮次后面会详细谈到，每个节点在同步到新事件后，可以立刻开始计算创建轮次

然后，我们按照见证人的定义标记每轮次的见证人事件，如下：

对于每一个见证人，我们需要判断它是否是知名见证人，我们以判断B2事件是否是知名见证人为例，根据知名见证人的定义我们需要判断A3、B3、C3和D3事件能够可见B2，这其实就是一个选举过程，每一个见证人都会对B2进行投票来决定B2是否知名。

A3事件可见B2，可见路径如下黄线，我们可以说B2是A3的祖先事件，A3是B2的儿子事件或派生事件，A3可见B2，因此A3投票YES

同理其他3个见证人，经过投票后所有见证人都投YES，因此我们预判B2事件将是知名见证人，但需要注意的是选举过程并没有结束哦，还有一步计票阶段，计票必须由下一轮见证人完成，因此B4和D4将进行计票，虽然这幅图中没有A4和C4，但是随着时间推移它们一定会出现并且也将参与计票

在计票阶段，R+2轮见证人会从自己强可见的R+1见证人处收集投票结果，一旦某个投票结果的计票数量超过绝对多数即认为该结果有效，也就是达成共识。根据数学理论证明，任何一个R+2轮见证人如果对投票结果做出了决定，那么这个结果就是全网的结论，如果这轮见证人无法做出决定，就由下一轮见证人计票决定，直到得出确切结论。具体来看个例子，B4到A3有三条可见路径且跨越了3个节点，因此B4强可见A3事件，即B4从A3处收集到的投票结果是YES

同理可得，B4强可见B3、C3和D3事件

通过合计，B4事件收集到了4个YES投票，显然我们可以得出结论：B2是知名见证人！我们将在图中用绿色标记出这些知名见证人。然后我们继续对C2事件进行知名性判断，由于C2下一轮的见证人投票结果为1YES，3NO，B4在计票后显然会判定不是知名见证人，我们将C2标记为蓝色，同时白皮书有数学验证可以保证所有其他见证人也做出同样的决定。

值得一提的是，假如在下一轮无法做出决定（例如2:2的投票结果），则将延续到下一轮，根据数学定理只要我们在每十轮增加一个随机轮次（coin round），则选举过程最终一定会结束（以概率1收敛，通俗点说就是几乎必然收敛，这是概率论中的概念）。在随机轮中，收集到绝对多数结果的见证人仅投票而不做决定，而其他见证人则根据数字签名的中间位进行随机投票。我们继续进行知名见证人的选举，结果如下

一旦某个轮次确定了所有的知名见证人，就可以为这一轮次中的其他普通事件确定接受轮次和共识时间戳（consensus timestamp）。我们可以看到黑色事件可以被第二轮的所有知名见证人可见，因此它的接受轮次就是2

现在我们开始确定黑色事件的共识时间戳用于后续确定共识顺序，寻找A节点最早的事件X，它既是A2的祖先也是黑色事件的儿子，同理寻找B节点的Y和D节点的Z。然后将XYZ事件的时间戳依次排序并取中位数作为黑色节点的共识时间戳。然后我们继续确定其他节点的接受轮次

现在我们确定了10个接受轮次为2的事件，我们将为其排序得到全网公认的顺序，即共识顺序。我们按照以下优先级进行排序：

接受轮次

共识时间戳

按事件签名和某随机数异或的结果排序，这个随机数通过该轮所有知名见证人的数字签名进行异或运算得到

下面我们看一张共识算法的可视化图，来自HashgraphDemo 应用的运行结果，有兴趣的同学可以下载官方的SDK包运行查看，SDK中包含若干个有趣的Demo（通过修改配置文件运行不同的demo）

$> java -jar swirlds.jar

​ 前段时间我曾看到一篇文章说目前公链项目已经扎堆得人满为患了，是时候将目光聚焦到协议层上，至少这里还不是那么拥挤，那么Hashgraph绝对是一个值得考虑的项目。需要注意的是，Hashrgaph目前并没有开源，整个共识系统由一家商业软件公司所有（Swirlds）。通过上文的分析，Hashgraph的共识过程相比于其他算法有很大的创新，有相当的安全理论证明，并且验证简单，同时其高并发低延迟的特性目前正在进行测试中。不过谣言算法真的适用于大规模公链环境依然值得商榷，而在私有链场景，Hashgraph已经成功应用于不少2B系统中。其次，在Hashgraph协议中所有节点必须保存全网数据，不知如何解决数据压缩问题。不过总体来说，Hashgraph项目非常值得期待，在目前的测试数据来看，在许多场景下效果吊打大部分共识协议，技术细节论证严谨，团队组建2年多，团队老大Leemon Baird关于Hashgraph有多次精彩的公开演讲，可以网上搜索。

最近的商业信息：

在2017年9月团队获得了来自NEA的300万美元的种子投资

2017年10月有偿授权美国信用联盟使用hashgraph技术

社区热度：

Twitter: 2.1 W

电报：2.7 W

Medium: 1.1 K

YouTube: 7.2 K

最后说一句，目前官方只允许合格投资者参与预售，这意味门槛非常高哦。开发人员和用户可以参与到社区建设获得代币，具体信息关注官方渠道。