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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2414 天前的主题，其中的信息可能已经有所发展或是发生改变。

背景

在深入探索 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 是一种数据结构和共识算法。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 白皮书中描述的相关术语，不然真的会看得云里雾里，我将尽可能地说人话:sweat_smile:

事件（ 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 ）:thumbsup:

$> java -jar swirlds.jar

结论

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