DAGX中DAG交易数据同步算法详解

引言
相比于传统单链结构的区块同步过程，DAG结构的交易数据同步过程要更加复杂。其复杂性主要体现在以下两个方面：
从同步数量上来看：单链结构中区块打包了一批交易数据，只需要对区块进行同步及其正确性的检查，这样就完成了一批交易数据的检查；而DAG结构需要对每一笔交易数据单独进行同步和检查，时间和计算复杂度成倍增加。
从连接关系上来看：单链结构的区块只有一个父区块，整个结构中只有单一路径，连接关系的同步和检查比较简单；而DAG结构中交易数据可能有多个父交易，连接关系的同步和检查更为复杂。
DAGX采用的是“分而治之”的思想，通过将整个DAG分割成多棵哈希树（hash_tree），以哈希树作为基本单元来进行同步。为方便理解，哈希树在一定程度上可以跟单链结构中的区块进行类比，只不过哈希树的分割方式具有更大的灵活性。在DAGX中，哈希树的分割方式以同步链（catchup_chain）的形式实现。同步链和哈希树构成了DAGX的DAG同步的基本数据结构。
基本流程
当全节点A需要与全节点B进行同步时（以下讨论中，我们称全节点A为本地节点，全节点B为对方节点），其同步的基本流程如下图所示：

DAGX中DAG交易数据同步算法详解
同步过程主要包括以下几个基本步骤：
本地节点向对方节点发送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中最近达到稳定的交易单元。
依照上述同步过程，我们可以大体的描绘出本地DAG的变化图如下所示：

DAGX中DAG交易数据同步算法详解
同步链（catchup_chain）的生成及处理
首先，我们给出DAGX中与DAG数据同步有关的几张数据表：
balls：用于保存已同步且经过验证的稳定交易单元；
hash_tree_balls：用于保存已同步的哈希树；
catchup_chain_balls：用于保存已获取的同步链。
同步链的生成
当对方节点接收到本地节点的catchup请求后，它将根据请求参数及其DAG数据生成同步链。在生成同步链之前，首先需要生成见证人证明witness_proof，它主要是用来处理见证人的定义变化，以及获取相应见证人列表条件下主链上的交易单元。
在给定catchup请求参数见证人列表arrWitnesses及已知最近稳定单元的主链序号last_stable_mci的条件下，见证人证明包括以下两部分数据：
主链上未达到稳定的交易单元arrUnstableMcJoints：在min_retrievable_mci之后出现的主链上的交易单元，min_retrievable_mci指的是当前DAG中最近稳定单元的last_ball的mci。
见证人定义发生变化的交易单元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在本地未出现或者未达到稳定状态，则对方的主链也已经跟本地达到同步状态，不再需要进行同步过程。
生成的同步链由以下几部分数据组成：
主链上未达到稳定的交易单元集合
unstable_mc_joints：在min_retrievable_mci之后出现在主链上的交易单元，即见证证据中的arrUnstableMcJoints。
主链上已稳定的交易单元集合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通过见证证据获得。
见证人定义发生变化的交易单元集合witness_change_and_definition_joints：在last_stable_mci之后出现的见证人地址定义新增或修改的交易单元，即见证证据中的arrWitnessChangeAndDefinitionJoints。
同步链的处理
与同步链的生成相对应的是同步链的处理过程，当本地节点接收到对方节点返回的同步链时，它将首先对见证人证明进行处理。返回的同步链中
unstable_mc_joints及witness_change_and_definition_joints对应见证人证明中的两部分数据arrUnstableMcJoints及arrWitnessChangeAndDefinitionJoints，其处理过程如下：
从arrUnstableMcJoints的顶端结点开始回溯，当遇见大多数见证人后，选取剩余交易单元的last_ball_unit形成集合arrLastBallUnits，并以last_ball_unit为索引存储相应的last_ball构成集合assocLastBallByLastBallUnit。
对于见证人定义发生变化的交易单元arrWitnessChangeAndDefinitionJoints，检查这些交易单元是否达到稳定，并检查是否由本地见证人列表arrWitnesses中的见证人发出。然后，获取本地见证人列表arrWitnesses中见证人的定义，检查交易单元的签名并更新见证人的定义。
给定同步链的数据unstable_mc_joints、stable_last_ball_joints以及witness_change_and_definition_joints，同步链的处理过程如下：
首先需要处理由unstable_mc_joints及witness_change_and_definition_joints组成的见证人证明，从而获得arrLastBallUnits及assocLastBallByLastBallUnit，其处理过程已在上面讨论了。
检查stable_last_ball_joints中第一个交易单元是否在arrLastBallUnits中，并以其作为同步链的处理起点last_ball_unit。
依次检查stable_last_ball_joints中的交易单元，检验前一个交易单元的last_ball_unit是否指向后一个交易单元。
检查stable_last_ball_joints中的最后一个交易单元是否为本地节点DAG已知的并且达到稳定状态，并将其替换为本地DAG的最近稳定交易单元。
检查stable_last_ball_joints中的倒数第二个交易单元是否不是本地DAG并且没有达到稳定状态，即stable_last_ball_joints中只有最后一个交易单元满足本地DAG已知且达到稳定状态。
将stable_last_ball_joints作为同步链数据插入本地数据库表catchup_chain_balls中，按照mci从小到大的顺序插入。
同步链处理后，本地节点DAG形成了一种哈希树的分割方式，并存储在数据表catchup_chain_balls中，为之后逐步进行哈希树同步提供了依据。
哈希树（hash_tree）的同步
对于主链上已经达到稳定状态的两个交易单元，主链序号在二者之间的所有交易单元构成一棵哈希树，哈希树的树根为主链序号较大的那个交易单元。

本地数据库表catchup_chain_balls按照mci从小到大的顺序存储了一条以last_ball_unit作为连接的主链路径，路径的起点是本地DAG中最近达到稳定的单元，路径的终点是对方DAG中最近达到稳定的单元。catchup_chain_balls中相邻的两个交易单元可以构造一棵哈希树，我们将以此为基础进行同步。假设相邻两个交易单元中mci较小的称为from_ball，mci较大的称为to_ball。
在进行同步时，本地节点向对方节点请求哈希树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数据同步这样较为复杂的问题，该方法十分值得研究和借鉴。

浏览过的版块