1. 首页
  2. 基本原理

ByteBall主链更新算法解析

节点的所有交易数据存储在两个位置:一个是内存中(为了减少数据库查询);另一个是数据库中。也就是说,当对一个新的交易单元校验完后,在存储时可能会对已经存储的交易数据以及本地DAG产生影响,影响包括两个方面:一方面是需要更新DAG及主链信息;另一方面是检查是否出现双花或者不连续的交易单元。

这里我们主要关注新交易单元对DAG及主链的影响,在将新交易单元加入本地DAG中时,基本步骤如下:

  1. 从所有的自由结点(顶端结点)中选择一个最优结点的作为当前主链的起点,选择标准与最优父结点一样;
  2. 如果新加入的结点不影响候选主链,那么只需要更新一下新结点的LIMCI即可;
  3. 如果新加入的结点使当前主链发生变化,则应该在某个位置与原主链会合(最差的情况是在稳定点会合,最好的情况是新结点延长了原主链),那么从会合结点开始向后更新MCILIMCI
  4. 检查稳定结点是否可以沿当前主链前进。

下面将分两种情况对稳定结点是否可以沿当前主链前进展开详细讨论:一种是稳定结点仅有一个子结点;另一种是稳定结点具有多个子结点。

首先,我们将定义结点的“见证人支持度”:给定起始结点S和见证人列表W,从结点S出发沿着最优路径回溯,当路径中出现见证人列表W中大部分见证人(7个)时停止回溯;在起始结点到停止结点的这段路径里,定义见证人发出的交易单元中最小的见证级别为结点S在见证人列表W下的“见证人支持度”。

假设DAG中最近的稳定结点为X,其见证人列表为W,当前主链的顶端结点S在见证人列表W下的“见证人支持度”为SL。

稳定结点具有一个分支

稳定结点X仅具有一个子结点C,它位于当前主链上,假设结点C的级别为L。

ByteBall主链更新算法解析

如果当前主链的顶端结点的“见证人支持度”SL大于等于结点C的级别L时,则结点C达到稳定,即稳定结点可以从结点X前进到结点C。由于见证人列表不能发生突变而且大部分见证人已经支持当前主链,这些见证人后续发送的交易单元与其之前发送的交易单元保持连续,即它们将继续支持当前主链。因此,这将保证当前主链包含稳定结点X与结点C之间的路径,也就是说稳定结点可以从X前进至C。

稳定结点具有多个分支

稳定结点X具有多个子结点,其中一个子结点C位于当前主链上,其它子结点位于其它竞争分支上,假设结点C的级别为L。

ByteBall主链更新算法解析

由于见证人可能在当前主链之外的其它分支上也存在交易单元,为了防止当前主链切换到其它竞争分支上,稳定点从结点X前进到C的判定条件要更加严格。在关于ByteBall中见证级别(witnessed level)的深入讨论中,我们知道那些使得子结点见证级别大于父结点的最优路径是十分重要的,它代表了见证人对该路径的支持。因此,在稳定点前进的判定中,我们要充分考虑竞争分支中这些特殊的最优路径。

选取除当前主链外的竞争分支中见证级别大于其父结点的那些结点,将这些结点中的最大级别记作ML。极限情况下,如果竞争分支中不存在符合条件的结点,则ML等于结点C的级别L。如果当前主链的顶端结点的“见证人支持度”SL大于等于ML时,则结点C达到稳定,即稳定结点可以从结点X前进到结点C。

在构造以及检验新交易单元N时,要求该交易单元的last_ball_unit在其视角下达到稳定。此时,last_ball_unit的最优父结点作为稳定结点X,last_ball_unit作为子结点C,从新交易单元N到达稳定结点X的最优路径作为当前主链,新交易单元N作为顶端结点。根据上述算法,我们可以判断last_ball_unit在新交易单元N的视角下是否达到稳定。

P.S. 目前ByteBall在主链更新这部分的实现是比较混乱的,后续我们将对这块代码进行优化并向byteballcore提交相应的更新。

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

发表评论

登录后才能评论

联系我们

加入ByteBall技术群请添加

QR code