DAGX中DAG交易数据同步算法详解
棋丝集日授
发表于 2022-12-13 00:42:27
175
0
0
相比于传统单链结构的区块同步过程,DAG结构的交易数据同步过程要更加复杂。其复杂性主要体现在以下两个方面:
从同步数量上来看:单链结构中区块打包了一批交易数据,只需要对区块进行同步及其正确性的检查,这样就完成了一批交易数据的检查;而DAG结构需要对每一笔交易数据单独进行同步和检查,时间和计算复杂度成倍增加。1 N9 k1 h4 Q2 @& Z
从连接关系上来看:单链结构的区块只有一个父区块,整个结构中只有单一路径,连接关系的同步和检查比较简单;而DAG结构中交易数据可能有多个父交易,连接关系的同步和检查更为复杂。8 R$ ]3 w8 y7 y3 V; k
DAGX采用的是“分而治之”的思想,通过将整个DAG分割成多棵哈希树(hash_tree),以哈希树作为基本单元来进行同步。为方便理解,哈希树在一定程度上可以跟单链结构中的区块进行类比,只不过哈希树的分割方式具有更大的灵活性。在DAGX中,哈希树的分割方式以同步链(catchup_chain)的形式实现。同步链和哈希树构成了DAGX的DAG同步的基本数据结构。7 O6 h. d0 `1 M" J/ g
基本流程. U* ~8 V; S8 ^; m% _( T
当全节点A需要与全节点B进行同步时(以下讨论中,我们称全节点A为本地节点,全节点B为对方节点),其同步的基本流程如下图所示: @5 Q& Z) j8 A& v1 X) X8 f& A
# M" N4 I# H& E, Q. \
DAGX中DAG交易数据同步算法详解% o) [" D0 y# R. v5 a
同步过程主要包括以下几个基本步骤:
本地节点向对方节点发送catchup请求,参数为本地DAG的属性,包括节点A的见证人列表arrWitnesses、已知的稳定单元主链序号last_stable_mci、已知的最近的主链序号last_known_mci;
对方节点根据本地节点的请求,按照其所具有的DAG构造同步链catchup_chain返回给本地节点;
本地节点根据同步链catchup_chain的信息,逐步请求哈希树hash_tree,从而同步本地DAG。
同步链catchup_chain是当前主链的一种分割方式,本质上它是一条以last_ball_unit作为连接的主链路径,路径的起点是本地节点DAG中最近达到稳定的交易单元,路径的终点是对方节点DAG中最近达到稳定的交易单元。2 @3 b+ u: A+ k5 w3 Z& y+ C+ O5 ]
依照上述同步过程,我们可以大体的描绘出本地DAG的变化图如下所示:
DAGX中DAG交易数据同步算法详解
同步链(catchup_chain)的生成及处理
首先,我们给出DAGX中与DAG数据同步有关的几张数据表:
balls:用于保存已同步且经过验证的稳定交易单元;
hash_tree_balls:用于保存已同步的哈希树;3 s# V% }' o w' o4 p' _' P
catchup_chain_balls:用于保存已获取的同步链。; M/ r0 H2 ~4 a3 k2 V5 ?
同步链的生成
当对方节点接收到本地节点的catchup请求后,它将根据请求参数及其DAG数据生成同步链。在生成同步链之前,首先需要生成见证人证明witness_proof,它主要是用来处理见证人的定义变化,以及获取相应见证人列表条件下主链上的交易单元。0 U& z# C- U9 c' V
在给定catchup请求参数见证人列表arrWitnesses及已知最近稳定单元的主链序号last_stable_mci的条件下,见证人证明包括以下两部分数据:
主链上未达到稳定的交易单元arrUnstableMcJoints:在min_retrievable_mci之后出现的主链上的交易单元,min_retrievable_mci指的是当前DAG中最近稳定单元的last_ball的mci。% U- T8 X7 Q4 S$ T3 s
见证人定义发生变化的交易单元arrWitnessChangeAndDefinitionJoints:在last_stable_mci之后出现的见证人地址定义新增或修改的交易单元。
在生成见证人证明的过程中,同时检查当前DAG中最近稳定的交易单元last_ball_unit及其主链序号last_ball_mci。从arrUnstableMcJoints的顶端结点开始回溯,当遇见大多数见证人后,选取其剩余交易单元的last_ball,以其中mci最大的那个last_ball对应的交易单元作为last_ball_unit,其mci作为last_ball_mci。如果last_stable_mci >= last_ball_mci,那么说明对方的主链已经跟本地达到同步状态,不需要再进行数据同步过程。
此外,如果对方节点的last_known_mci在本地未出现或者未达到稳定状态,则对方的主链也已经跟本地达到同步状态,不再需要进行同步过程。8 m0 K& G( n T+ k, T7 I
生成的同步链由以下几部分数据组成:; Q0 t8 Q/ g+ E4 u" E5 _
主链上未达到稳定的交易单元集合
unstable_mc_joints:在min_retrievable_mci之后出现在主链上的交易单元,即见证证据中的arrUnstableMcJoints。# U! H- o+ b$ H; p3 j
主链上已稳定的交易单元集合stable_last_ball_joints:从last_ball_mci位置开始沿last_ball_unit路径开始回溯,直到小于等于last_stable_mci停止,获取相应的last_ball_unit的集合,在这个集合中,最后一个last_ball_unit是请求同步的节点已知的。其中,last_ball_unit及last_ball_mci通过见证证据获得。7 T1 h5 t6 G2 T6 ~. T/ E
见证人定义发生变化的交易单元集合witness_change_and_definition_joints:在last_stable_mci之后出现的见证人地址定义新增或修改的交易单元,即见证证据中的arrWitnessChangeAndDefinitionJoints。( [9 ^ c: i! |
同步链的处理
与同步链的生成相对应的是同步链的处理过程,当本地节点接收到对方节点返回的同步链时,它将首先对见证人证明进行处理。返回的同步链中
unstable_mc_joints及witness_change_and_definition_joints对应见证人证明中的两部分数据arrUnstableMcJoints及arrWitnessChangeAndDefinitionJoints,其处理过程如下:2 D# \/ d( o( F% `5 X% e
从arrUnstableMcJoints的顶端结点开始回溯,当遇见大多数见证人后,选取剩余交易单元的last_ball_unit形成集合arrLastBallUnits,并以last_ball_unit为索引存储相应的last_ball构成集合assocLastBallByLastBallUnit。' x$ S- K3 }) o6 l& h b
对于见证人定义发生变化的交易单元arrWitnessChangeAndDefinitionJoints,检查这些交易单元是否达到稳定,并检查是否由本地见证人列表arrWitnesses中的见证人发出。然后,获取本地见证人列表arrWitnesses中见证人的定义,检查交易单元的签名并更新见证人的定义。
给定同步链的数据unstable_mc_joints、stable_last_ball_joints以及witness_change_and_definition_joints,同步链的处理过程如下:! O" n7 I' b Z
首先需要处理由unstable_mc_joints及witness_change_and_definition_joints组成的见证人证明,从而获得arrLastBallUnits及assocLastBallByLastBallUnit,其处理过程已在上面讨论了。: Y7 Z: `- D; A" d1 e3 ?
检查stable_last_ball_joints中第一个交易单元是否在arrLastBallUnits中,并以其作为同步链的处理起点last_ball_unit。
依次检查stable_last_ball_joints中的交易单元,检验前一个交易单元的last_ball_unit是否指向后一个交易单元。
检查stable_last_ball_joints中的最后一个交易单元是否为本地节点DAG已知的并且达到稳定状态,并将其替换为本地DAG的最近稳定交易单元。- {: s6 L! h# w
检查stable_last_ball_joints中的倒数第二个交易单元是否不是本地DAG并且没有达到稳定状态,即stable_last_ball_joints中只有最后一个交易单元满足本地DAG已知且达到稳定状态。& y1 Z) w8 c9 ?4 {! E
将stable_last_ball_joints作为同步链数据插入本地数据库表catchup_chain_balls中,按照mci从小到大的顺序插入。
同步链处理后,本地节点DAG形成了一种哈希树的分割方式,并存储在数据表catchup_chain_balls中,为之后逐步进行哈希树同步提供了依据。
哈希树(hash_tree)的同步! K2 _9 t0 I2 t+ x- a- H
对于主链上已经达到稳定状态的两个交易单元,主链序号在二者之间的所有交易单元构成一棵哈希树,哈希树的树根为主链序号较大的那个交易单元。
本地数据库表catchup_chain_balls按照mci从小到大的顺序存储了一条以last_ball_unit作为连接的主链路径,路径的起点是本地DAG中最近达到稳定的单元,路径的终点是对方DAG中最近达到稳定的单元。catchup_chain_balls中相邻的两个交易单元可以构造一棵哈希树,我们将以此为基础进行同步。假设相邻两个交易单元中mci较小的称为from_ball,mci较大的称为to_ball。9 v, J7 G1 G" g. x# j0 `+ O
在进行同步时,本地节点向对方节点请求哈希树get_hash_tree,请求参数为from_ball和to_ball。对方节点将mci位于from_ball和to_ball之间的所有交易单元构成哈希树返回给本地节点。
本地节点接收到哈希树后,对于哈希树中的每个交易单元,检查其父单元以及跳跃列表是否是本地节点DAG已知的,然后将其添加至本地数据库表hash_tree_balls中,按照mci和level从小到大顺序插入。处理完成后,向对方节点请求哈希树中每个交易单元的详细数据,并处理这些交易单元。
结语
本文详细讨论了ByteBall的DAG数据同步过程,分析了ByteBall处理同步问题的基本思想,并针对同步过程中使用的同步链(catchup_chain)和哈希树(hash_tree)两个基本数据结构的处理过程进行了详细分析。ByteBall采用了比较巧妙的方法来处理DAG数据同步这样较为复杂的问题,该方法十分值得研究和借鉴。
成为第一个吐槽的人