Hashgraph哈希图是什么？与区块链有什么不同？

Hashgraph是一种全新的分布式账本共识机制技术和数据结构，与以区块为核心的区块链技术相比，其更快、更公平和更安全。Hashgraph更像一个底层的出块层而非一个完整的系统。

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

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如何在节点之间通信，在通过执行八卦算法后，所有节点都是全节点，存储了完整的网络历史，在需要对某一提案达成共识时并不需要大规模的消息通信，每个节点可以独立执行虚拟投票机制(Virtual Voting)，并且所有节点一定会得出相同的共识结果。接下来我们可以看到虚拟投票机制的详细名词定义与虚拟投票过程的演示范例，引用自《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的事件，我们将为其排序得到全网公认的顺序，即共识顺序，按照以下优先级进行排序：

接受轮次

共识时间戳

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

2.3 共识机制总结

Hashgraph由八卦协议和虚拟投票机制构成的共识机制，总体来说可以概括如以下步骤：

1. 每个节点都在试图随机找到其他节点，把自己所知的信息通过八卦协议传递给对方;

2. 每个节点同时也在接受其他节点通过八卦协议传递过来的信息，接受信息时节点需要进行一系列的运算，包括：

a. 接受和处理接收的八卦信息

b. 创建一个新的事件，同时指向自己的最后一个事件和八卦来源节点的最后一个事件

c. 对所有已知的事件计算其创建轮次，确定事件是否是该轮次内的见证人事件

d. 对所有已知的见证人事件进行选举投票，计算出是否为知名见证人

e. 通过知名见证人，确定所有事件的接受轮次

f. 通过事件的接受轮次和共识时间戳，进行虚拟投票决定共识顺序

整个共识算法，单个节点需要保存全网数据。

 1/5    1 2 3 4 5 下一页 尾页