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
的。
计算结点的级别和见证级别
在已知结点的父结点集合的基础上,结点的级别level
等于所有父结点中最大的级别max_level+1
。
给定结点的见证人列表和父结点集合时,计算结点的见证级别witnessed_level
的步骤为:
- 找到最优父结点;
- 开始从最优父结点沿主链开始回溯;
- 当路径上出现多于7个不同见证人发出的结点时,回溯停止;
- 以回溯停止处的结点的级别
level
作为见证级别witnessed_level
。
寻找主链上最近的稳定结点
给定见证人列表,在主链上找到已达到稳定的结点中主链序号最大的那个结点,并记录其对应的ball
、unit
及main_chain_index
。特别地,如果从父结点集合的角度来看该结点还没有达到稳定,则需要沿主链继续回溯,选择该结点的最优父结点作为新的稳定结点。
版权所有。发布者:Alan During,转载请注明出处:https://bbfans.org/2018/08/31/byteball-core-algorithm-unit-generation/