————————————————————
作者：
Node Capital研究中心 林婕茵 郎瀚威
鲸准研究院 谭莹 王帆 陈泓伊
（本报告由Node Capital X 鲸准研究院联合发布）
. 01 .概述
1.1 区块链的概念
传统意义的区块链是由一根链以线性方式链接一系列的区块，这些区块中记录着一个时间段内发生的交易。矿工通过各种机制竞争这个时间段内交易的记账权，对于一笔交易来说，需要足够幸运或付出足够多的手续费才能被矿工选中。如在比特币网络中每10分钟才出一个块，平均每秒进行7次交易，以太坊虽然大大加快了出块时间，但也需要十几秒才能确认出一个块。由于一笔交易的确认需要等待十几秒甚至十分钟，效率很低，因此区块链1.0和2.0的项目对于大规模商用还有很长一段距离。
1.2 DAG的概念
如果一个有向图从任意顶点出发无法经过若干条边回到该点，那么这个图就是一个有向无环图（简称DAG）。有向无环图打破了“区块”的概念，其中的每一笔交易跳过了等待打包入块的步骤，直接以单笔交易为单位计入链中。
然而，DAG网络面临着控制网络宽度的问题，如果每一笔新的交易都链接到网络中比较老的某个交易节点上，那么DAG网络就会从这一老节点突然变宽，效率变低。因此，最理想的状态是，每一笔新交易都均匀的连接在链的新老节点上，将网络控制在一定的宽度内，包括IOTA在内的DAG网络都是这样解决宽度问题的。
现有DAG项目的问题：
IOTA：
1. MIT报告指出，IOTA使用了自己开发的哈希算法curl，但是curl算法的哈希值极易发生碰撞，于是就能伪造数字签名。
2.因为共识是由全网交易确定的，那么理论上来说，如果有人能够产生1/3的交易量，他就可以将无效交易变成有效交易。另一方面，由于IOTA无手续费，所以没有矿工激励，IOTA面临着拒绝服务攻击和垃圾信息攻击可能，就像不收物业费的小区，靠业主自治很难扫清不法份子。
3. IOTA引入闭源的中心化组件Coordinator来对全网交易进行检查（例如双花），如何有效移除Coordinator并建立一个具有良性激励机制的去中心化「Coordinator群体」，IOTA还没有给出解决方案。
Byteball：
由于主链算法和见证人发布频率有关系，交易确认的时间是不确定的；由于Byteball基于关系数据库来存储数据，SQL语言过于紧耦合算法逻辑，在一定程度上限制了Byteball目前的扩展能力和速度。
NANO：
没有被充分测试、缺乏同行评议，共识算法可能有严重缺陷的风险。例如，如果没有足够的法定人数投票来解决网络冲突会发生什么？如果NANO网络的某些部分长时间分离，当分离的网络重新加入时会发生什么？重新加入的网络是否会在不可避免发生的投票过程中瘫痪？这些问题都有待测试验证。
1.3 Hashgraph的概念
Hashgraph是以基于DAG网络来搭建的一种数据结构和共识算法，但Hashgraph有着自己的控制宽度的方式，而且每个点可以有两个父节点。在Hashgraph网络中，只有获得准入的节点才有发起事件（Event）的权利，事件即为交易数据的容器，所有发起新事件的工作都需由这些节点完成，通过非链式结构无需竞争即可同步出块，实现大规模低成本共识，大大提高了工作效率，控制了带宽的同时，做到了真正的“Blockless”。据称能够实现超过25万TPS，是低交易费、去中心化、无需挖矿的互联网底层信任网络。Hashgraph的数据结构示意图如下，其中，Alice、Bob、Carol、Dave、Ed分别是五个有发起事件权力的节点，每个圆圈是一个事件，由节点在接收到八卦时创建，越靠近下方的越早发起的事件，越靠近上方是越新的事件。
Hashgraph开创性地在公链环境下做异步BFT共识，传统BFT的一大问题是消息复杂度太高，大量消耗系统的网络带宽，无法很好的应对动态网络。这里Hashgraph引入了传统Gossip Protocol，并加以独特的创新，另外再加上虚拟投票机制，这样在需要共识的时候不会引起突发大规模消息传递风暴。
区块链与Hashgraph的对比：
区块链技术vs Hashgraph
. 02 .Hashgraph技术
Hashgrapgh的共识机制包括两个部分，Gossip about Gossip和Virtual Voting，以下将分别解释二者的工作流程与总体共识机制的工作流程，并说明Hashgraph的优点和存在的问题。
2.1 Gossip about Gossip
Hashgrapgh的核心通信协议是“八卦八卦协议”（Gossip about Gossip），灵感来自办公室八卦，这里的八卦指的是一段我知道但是另一个人不知道的信息，只要两个人之间八卦一下，在有限的时间内，所有的人都会知道该八卦的信息。
在Hashgraph中，每一个节点都在传播经过签名的新交易以及从临近节点接收到的交易信息。当某个节点收到包含新交易信息的数据后，会组合并可能添加自己所知道的交易成为一个新的事件（Event，类似于区块的概念，是一个包含有两个哈希指针的数据结构，并且可以包括0个或若干交易信息）传播出去，并且这个事件包含两个哈希，一个指向该节点上次最新的事件，另一个指向该节点所收到的另一个节点的最新事件，然后对整个事件加上时间戳并签名，整个循环不断进行直到所有节点都获得相同的信息。
如下图所示，当 Bob 随机找到了 Alice 八卦的时候，就会把自己当前所知道的一切都原原本本地告诉 Alice。然后 Alice 这里会出一个新事件（红点），这个新事件里除了加入新的交易事务的同时，还会加上两个指向父事件的 hash 值，一个指向自己的最新事件（深蓝），一个指向 Bob 和自己聊天时候最新的事件（天蓝）。
本质上八卦算法是一个带冗余的容错算法，更进一步，八卦是一个最终一致性算法或提供一致性算法的手段。虽然无法保证在某个时刻所有节点状态一致，但可以保证在最终某个时刻，所有节点一致对某个时间点前的所有历史达成一致。
Hashgraph的节点之间进行八卦的内容还包括节点间互相八卦的历史记录，于是每个节点都可以通过八卦维护一个哈希图，这样在节点计算共识投票的时候就可以发起虚拟投票，也就是计算其他节点在给定的哈希图中会怎么投票，从而不需要在网络上再做大量双向同步通信去进行真实的投票。用Hashgraph发明者的话来说就是：“Hashgraph具备投票算法的一切优点，然而避开了它的最大缺陷。”
由于Gossip协议迅速的收敛性(convergence propperty)，每条新的信息能够以更快的方式到达每个节点，让每个节点都维护着所有节点跟其他节点的通信历史。
2.2 Virtual Voting
上面我们看到了Hashgraph如何在节点之间通信，在通过执行八卦算法后，所有节点都是全节点，存储了完整的网络历史，在需要对某一提案达成共识时并不需要大规模的消息通信，每个节点可以独立执行虚拟投票机制（VirtualVoting），并且所有节点一定会得出相同的共识结果。下面我们可以看到虚拟投票机制的详细名词定义与虚拟投票过程的演示范例，引用自《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的投票结果），则将延续到下一轮，根据数学定理只要我们在每十轮增加一个随机轮次（coinround），则选举过程最终一定会结束（以概率1收敛，通俗点说就是几乎必然收敛，这是概率论中的概念）。在随机轮中，收集到绝对多数结果的见证人仅投票而不做决定，而其他见证人则根据数字签名的中间位进行随机投票。我们继续进行知名见证人的选举，结果如下：
一旦某个轮次确定了所有的知名见证人，就可以为这一轮次中的其他普通事件确定接受轮次和共识时间戳（consensus timestamp）。我们可以看到黑色事件可以被第二轮的所有知名见证人可见，因此它的接受轮次就是2。
现在我们开始确定黑色事件的共识时间戳用于后续确定共识顺序，寻找A节点最早的事件X，它既是A2的祖先也是黑色事件的儿子，同理寻找B节点的Y和D节点的Z。然后将XYZ事件的时间戳依次排序并取中位数作为黑色节点的共识时间戳。然后我们继续确定其他节点的接受轮次。
现在我们确定了10个接受轮次为2的事件，我们将为其排序得到全网公认的顺序，即共识顺序，按照以下优先级进行排序：
接受轮次
共识时间戳
按事件签名和某随机数异或的结果排序，这个随机数通过该轮所有知名见证人的数字签名进行异或运算得到
2.3 共识机制总结
Hashgraph由八卦协议和虚拟投票机制构成的共识机制，总体来说可以概括如以下步骤：
1. 每个节点都在试图随机找到其他节点，把自己所知的信息通过八卦协议传递给对方；
2. 每个节点同时也在接受其他节点通过八卦协议传递过来的信息，接受信息时节点需要进行一系列的运算，包括：
a. 接受和处理接收的八卦信息
b. 创建一个新的事件，同时指向自己的最后一个事件和八卦来源节点的最后一个事件
c. 对所有已知的事件计算其创建轮次，确定事件是否是该轮次内的见证人事件
d. 对所有已知的见证人事件进行选举投票，计算出是否为知名见证人
e. 通过知名见证人，确定所有事件的接受轮次
f. 通过事件的接受轮次和共识时间戳，进行虚拟投票决定共识顺序
整个共识算法，单个节点需要保存全网数据。
2.4 Hashgraph的优势
公平：维护交易的实际顺序
采用一致的时间戳，每一个事件以及事件里的每一笔交易都有顺序。
没有矿工这种角色的存在。
安全：异步拜占庭容错
Hashgraph是一个异步拜占庭容错（ABFT）系统，没有一个节点可以阻止网络达成共识或者在达成共识之后修改数据，号称能达到银行级别的安全性。而且共识算法中没有引入任何领导的角色，从而规避了领导节点被DoS攻击导致系统问题的风险。目前Hashgraph作为一个私有链，所有节点的身份已知，这种准入控制使得现阶段的Hashgraph无需考虑使用假身份攻击的危险。
快速
根据官网的测试数据，可以达到惊人的 250000 TPS。
2.5 Hashgraph目前的问题
目前为私有链，吞吐量参考价值存疑
目前Hashgraph是一个私有链，它的“运行速度快”只能跟其他私有链做比较，比如Hyperledger（700个交易/秒）和RedBelly（400,000个交易/秒），如果拿它的速度跟比特币和以太坊等公链来比较的话，是非常不公平的，因为现在的Hashgraph不需要设置防范恶意节点攻击的机制。此外，八卦算法是否适用于大规模公链环境也仍值得探讨。
能否经受恶意攻击
女巫攻击（Sybilattack），即攻击者通过创建大量假身份来破坏对等网络的信誉系统，并利用它们获得不成比例的巨大影响力。目前Hashgraph作为一个私有链，所有节点的身份已知，这种准入控制使得现阶段的Hashgraph无需考虑女巫攻击的危险。但如果未来Hashgraph打算往公有链方向发展的话，能否抵御女巫攻击将是Hashgraph必须思考的一个问题。
投票验证可能花费较多时间
Hashgraph的算法虽然很容易建立事件，但是在每个Round之后的投票验证过程却有可能很长。如果一直无法达到超过2/3的绝对多数，有可能要进行很多轮投票来决定谁记录的交易有效。
外部条件不同时的公平性问题：交易顺序如何决定？
Hashgraph白皮书中对公平性（Fairness）的解释如下：
假定存在A、B两个节点，A在B之前发出交易请求，如果最终在共识机制的判断下，A的交易的时间戳早于B的交易，我们就说该系统是有公平性的。如果A和B同时发生交易，并且两笔交易几乎是同时上传到网络并传播，此时就可能产生分叉，但是我们也说该系统是公平的。大多数共识机制都能够在以上两种情况下达到公平。
但是此解释是建立在A、B节点面临着同样的外部网络情况的假设前提下的。但我们考虑这样一个情况：
如果A的带宽是5M/s，而B的带宽是10M/s，A确实是比B早一点在网络中上传自己的交易信息，但是由于带宽限制，A的消息的传播速度会慢于B，这样就有可能导致最终投票时大多数人都更先接收到B的消息。这就像是在学校里，B的朋友更多，影响力大于A，因此在讨论八卦的时候，B可以把自己想传播的八卦信息更快地告诉更多人。即使可能是由A先开始传播八卦的，但因为影响力限制，大多数人都先听到B口中的版本。
在节点的外部条件不同时，投票是否也能反应真实地交易顺序，目前没有明确说明，因此仍然存在公平性的疑虑。
代码不开源
Hashgraph的代码不开源，且有专利保护，开发者需要申请SDK来进行开发，这是Hashgraph变成公链需要面临的一个很大障碍，这种闭源性本身与加密数字货币开源的理念是相违背的，所声称的公平、安全也无法提供确切的证据证明，可能无法得到信任。
. 03 .总结
Hashgraph是一个创新的共识协议，已被证明在私链的环境中产生高吞吐量，在当前运行的许可设置内是快速、公平和安全的，但如果想在公共环境中使用，将可能无法维持其安全性和性能，并且由于当前其代码不开源，所声称的安全性、公平性也不易得到信任，这些问题都尚待更进一步地完善和测试。
. 04 .参考与引用
Hedera Hashgraph 白皮书；
20180326 共识梳理 及 Hashgraph简评 作者 谢骏毅 码农学习区块链；
20180403 神级项目Hashgraph真的能成为区块链终结者吗？ 作者 Casey 猫眼财经聚焦；
20180413 Hashgraph —— 或许是目前最为优秀的共识协议 作者 Eric Sun BlockGeeks；
20180417 Hashgraph —— 可能超越区块链的优秀共识协议 作者 XC 带头币姐；
20180424 一文看懂DAG技术的现状与趋势 |链捕手 作者 李强 链捕手；
20180507 如何十分钟读懂Hashgraph 作者 互联价值 InterValue。
