1. 字节雪球爱好者社区首页
  2. 基本原理

关于ByteBall中见证级别(witnessed level)的深入讨论

如果只保留结点与其最优父结点的连接,那么整个DAG将退化为一棵最优路径树。最优路径树的树干为主链,不在主链之上的结点形成分支,并通过最优路径连接到主链上。只要获得足够多的见证人的支持,还未达到稳定状态的分支可以通过竞争成为主链。

最优路径树

在主链的竞争中,最为重要的是见证级别。计算结点的见证级别时,从结点的最优父结点出发沿着最优路径回溯,当收集到7个不同见证人(都属于结点的见证人列表)发出的交易单元时停止,停止处结点的级别作为该结点的见证级别。

见证级别

根据见证级别定义,见证级别是由结点所使用的见证人列表决定的,且沿着最优路径回溯停止的终点必定是由见证人发出的。假设结点的见证人列表为$W$,见证级别为$WL$,计算见证级别时最优路径上出现的见证人集合为$X \subset W$,最优路径终点的见证人为$w_e$,定义$X'=X-{w_e}$ 。

在最优路径树中,所有与最优父结点的连接里,那些使得结点的见证级别增大的连接是值得关注,因为这意味着有新的见证人支持了该连接所在的分支。因此,我们感兴趣的是在什么情况下,结点的见证级别比其最优父结点的大。

假设结点为$C$,其见证人列表为$W_c$,见证级别为$WL_c$;结点$C$的最优父结点为$P$,其见证人列表为$W_p$,见证级别为$WL_p$,最优路径上出现的见证人集合分别为$X_p$及$X'_p$。关于$WL_c$和$WL_p$的关系,我们分以下两种情况讨论:

结点的见证人列表与最优父结点的相同

由于见证人列表保持一致,即$W_c=W_p$,在计算结点$C$的见证级别$WL_c$时,最差情况下也将在$WL_p$这里遇见7个见证人,也就是说$WL_c \ge WL_p$。当且仅当最优父结点$P$的发送者$S$同时满足$S \in W_c$与$S \notin X'_p$时,即$S$为$W_c$中除了$X'_p$之外的见证人时,有$WL_c > WL_p$,否则$WL_c = WL_p$。

结点的见证人列表与最优父结点不同

根据见证人列表不能突变的原则,两者的差别数为1,即$|W_c \cap W_p|=11$。假设$N \in W_p$且$N \notin W_c$,即见证人$N$在结点$P$的见证人列表中而不在结点$C$的见证人列表中;$M \in W_c$且$M \notin W_p$,即见证人$M$在结点$C$的见证人列表中而不在结点$P$的见证人列表中。

根据$N$是否出现在计算见证级别$WL_p$的最优路径中可以分为以下三种情况:

  1. 若$N$不出现在计算$WL_p$的路径中,即$N \notin X_p$,那么满足$X_p \subset W_c$。在计算结点$C$的见证级别$WL_c$时,最差情况下也将在$WL_p$这里遇见7个见证人,也就是说$WL_c \ge WL_p$。当且仅当最优父结点$P$的发送者$S$同时满足$S \in W_c$与$S \notin X'_p$时,有$WL_c > WL_p$,否则$WL_c = WL_p$;
  2. 若$N$出现在计算$WL_p$的路径中,且为路径停止的终点,即$N \in X_p$且$N \notin X'_p$。在计算结点$C$的见证级别$WL_c$时,当最优父结点$P$的发送者$S$同时满足$S \in W_c$与$S \notin X'_p$时,或者$M$出现在结点$P$的最优路径上时,有$WL_c > WL_p$。在其它情况下,有$WL_c < WL_p$。
  3. 若$N$出现在计算$WL_p$的路径中,且不为路径停止的终点,即$N \in X'_p$。在计算结点$C$的见证级别$WL_c$时,当最优父结点$P$的发送者$S$同时满足$S \in W_c$与$S \notin X_p$时,或者$M$出现在结点$P$的最优路径上时,有$WL_c = WL_p$。在其它情况下,有$WL_c < WL_p$。

综上所述,当结点的见证级别大于它的最优父结点时,则必然在原来的最优路径上出现了新的见证人支持该路径。这个条件是将稳定点向前推进的重要基础。

版权所有。发布者:Alan During,转载请注明出处:https://bbfans.org/2018/11/09/byteball-witnessed-level/

发表评论

登录后才能评论

评论列表(1条)

联系我们

加入ByteBall技术群请添加

QR code