首页 > 品牌导购 > 查看内容
  • 分享到

Hashgraph技术解析

2018-06-22 18:38

来源:鲸准研究院

作者:陈泓伊



下图已经划分好了各个创建轮次,图中的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的事件,我们将为其排序得到全网公认的顺序,即共识顺序,按照以下优先级进行排序:


接受轮次


共识时间戳


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

发表评论
回顶部