字节雪球ByteBall核心算法之交易单元生成过程

交易单元生成过程

图结构包含结点和边两部分数据，结点数据主要使用数据表units存储，边主要采用数据表parenthoods存储。从数据结构角度来看，与结点数据相关的两个主要数据结构为：

交易单元（unit）：用来存储交易的属性数据，是核心数据结构，相关的数据表为units
连接点（joint）：主体由交易单元unit组成，同时包括一些结点的额外属性，比如ball、skiplist_units、unsigned等，相关的数据表包括joints、unhandled_joints、archived_joints、known_bad_joints。

下面给出一个连接点joint数据的简单示例：

joint = {
  'unit': {
    'unit': unit_hash,
    'version': version,
    'alt': alt,
    'messages': [
      {
        'app': 'payment',
        'payload_location': 'inline',
        'payload_hash': hash,
        'payload': {
          'outputs': arrOutputs
        }
      }, ...
    ],
    'authors': [
      {
        'address': address,
        'authentifiers': {
          'path': signature
        }
      }, ...
    ],
    'earned_headers_commission_recipients': recipients,
    'headers_commission': headers_commission,
    'payload_commission': payload_commission,
    'parent_units': arrParentUnits,
    'last_ball': last_stable_mc_ball,
    'last_ball_unit': last_stable_mc_ball_unit,
    'witnesses': arrWitnesses,
    'witness_list_unit': witness_list_unit, // only allowed witnesses or witness_list_unit
    'timestamp': timestamp,
    'content_hash': content_hash // only allowed in finished ball
  },
  'unsigned': ?,
  'ball': ?,
  'skiplist_units': ?
}

交易单元的生成过程是ByteBall中非常重要的部分，它的作用可以类比Bitcoin出块。在这个过程中，结点有几个关键属性需要构造：

level：结点的级别，代表结点在DAG中所处的位置序号；
witnessed_level：结点的见证级别，代表沿结点当前所在主链回溯获得多数见证人支持的位置序号；
best_parent_unit：结点的最优父结点；
witness_list_unit：结点的见证人列表；
last_ball_unit：主链上距离最近的已稳定的结点。

选择见证人列表

每个结点都具有见证人列表，这是结点看待“历史”所选取的角度，这好比在人类社会中人们是基于自身获取的信息源来得出对事情的看法。在保证见证人列表不能突变的情况下，“历史”只能缓慢地发生变化。

与见证人列表相关的数据库表包括：

my_witnesses：当前钱包所使用的见证人地址列表；
unit_witnesses：记录交易单元unit中包含的见证人witness，每个见证人witness的地址为一条记录，可以用来做结点兼容性的检查；
witness_list_hashes：记录交易单元unit对应的见证人列表hash值，相同的见证人列表对应的hash值相同，相同的见证人列表只记录第一次出现的unit。

如果见证人列表与之前结点的相同时，则采用witness_list_unit来代替就可以，若相应结点不在表中再单独记录。在构造交易单元时，应该优先使用witness_list_unit。对于一个交易单元unit而言，要么就是它本身可以在unit_witnesses中查到，要么就是它的witness_list_unit可以在unit_witnesses中查到。

寻找父结点

如何选择新结点的父结点是新结点构造过程中极为关键的一步。对于新结点$J$，给定其见证人列表$W^*$，在当前DAG中寻找其父结点的规则为：

找到当前图中的自由结点集合${ F_i, i=1,2,\dots,n}$，并计算自由结点$F_i$对应的见证人列表$W_i$与给定的见证人列表$W^*$中相同见证人的个数；
选择与给定见证人列表$W^*$兼容的自由结点集合${ F'_i, i=1,2,\dots,m}$，即相同见证人的个数超过11个；
若自由结点集合${F'_i}$不为空，则找出自由结点集合${ F'_i }$中的最优父结点$M$；
如果新结点$J$的见证级别witnessed_level不小于最优父节点$M$的见证级别witnessed_level，则自由结点集合${F'_i}$作为新结点的父结点集合（最多16个）；
如果新结点$J$的见证级别小于最优父结点$M$的见证级别，则对最优父结点$M$进行替换：选择仅具有$M$作为子结点的结点进行替换，或者直接从集合${F'_i}$中删除$M$，生成新的自由结点集合${F'_i,i=1,2,\dots,k}$，然后重复步骤3；
当找不到与给定见证人列表$W^*$兼容的自由结点时，则选择主链上最后一个结点作为父结点（这是为了防止洪泛攻击来修改见证人列表），如果新结点$J$的见证级别witnessed_level小于父结点的见证级别witnessed_level时，则继续在主链上选择见证级别更低的结点作为父结点。

在得到父结点集合后，还需要对见证人列表是否发生突变进行检查，要求从新结点$J$出发到last_ball_unit的主链上的所有结点对应的见证人列表witnesses差别不超过一个。如果见证人列表发生突变，则无法找到新结点的父结点，也就无法构造新结点。

在上述规则中，选择最优父结点的方法为：

优先级最高：父结点的见证级别witnessed_level越大越好；
优先级次高：父结点的级别与见证级别之差level-witnessed_level越小越好；
优先级最低：父结点的交易单元哈希值unit越小越好。

判断结点之间兼容的判断标准为：

witness_list_unit相同；
见证人列表witnesses最多只有一个不同。

另外值得注意的是，如果子结点的见证人列表和父结点的相同时，子结点的见证级别witnessed_level肯定是不小于父结点的。那么，什么情况下子结点的见证级别witnessed_level什么情况下会小于父结点？答案就是：当子结点和父结点的见证人列表不同时，它们是在不同的视角下计算见证级别witnessed_level的。