1. 首页
  2. 基本原理

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

引言

相比于传统单链结构的区块同步过程,DAG结构的交易数据同步过程要更加复杂。其复杂性主要体现在以下两个方面:

  • 从同步数量上来看:单链结构中区块打包了一批交易数据,只需要对区块进行同步及其正确性的检查,这样就完成了一批交易数据的检查;而DAG结构需要对每一笔交易数据单独进行同步和检查,时间和计算复杂度成倍增加。
  • 从连接关系上来看:单链结构的区块只有一个父区块,整个结构中只有单一路径,连接关系的同步和检查比较简单;而DAG结构中交易数据可能有多个父交易,连接关系的同步和检查更为复杂。

ByteBall采用的是“分而治之”的思想,通过将整个DAG分割成多棵哈希树(hash_tree),以哈希树作为基本单元来进行同步。为方便理解,哈希树在一定程度上可以跟单链结构中的区块进行类比,只不过哈希树的分割方式具有更大的灵活性。在ByteBall中,哈希树的分割方式以同步链(catchup_chain)的形式实现。同步链和哈希树构成了ByteBall的DAG同步的基本数据结构。

基本流程

当全节点A需要与全节点B进行同步时(以下讨论中,我们称全节点A为本地节点,全节点B为对方节点),其同步的基本流程如下图所示:

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

同步过程主要包括以下几个基本步骤:

  1. 本地节点向对方节点发送catchup请求,参数为本地DAG的属性,包括节点A的见证人列表arrWitnesses、已知的稳定单元主链序号last_stable_mci、已知的最近的主链序号last_known_mci
  2. 对方节点根据本地节点的请求,按照其所具有的DAG构造同步链catchup_chain返回给本地节点;
  3. 本地节点根据同步链catchup_chain的信息,逐步请求哈希树hash_tree,从而同步本地DAG。

同步链catchup_chain是当前主链的一种分割方式,本质上它是一条以last_ball_unit作为连接的主链路径,路径的起点是本地节点DAG中最近达到稳定的交易单元,路径的终点是对方节点DAG中最近达到稳定的交易单元。

依照上述同步过程,我们可以大体的描绘出本地DAG的变化图如下所示:

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

同步链(catchup_chain)的生成及处理

首先,我们给出ByteBall中与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_ballmci
  • 见证人定义发生变化的交易单元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_unitlast_ball_mci通过见证证据获得。
  • 见证人定义发生变化的交易单元集合witness_change_and_definition_joints:在last_stable_mci之后出现的见证人地址定义新增或修改的交易单元,即见证证据中的arrWitnessChangeAndDefinitionJoints

同步链的处理

与同步链的生成相对应的是同步链的处理过程,当本地节点接收到对方节点返回的同步链时,它将首先对见证人证明进行处理。返回的同步链中unstable_mc_jointswitness_change_and_definition_joints对应见证人证明中的两部分数据arrUnstableMcJointsarrWitnessChangeAndDefinitionJoints,其处理过程如下:

  • arrUnstableMcJoints的顶端结点开始回溯,当遇见大多数见证人后,选取剩余交易单元的last_ball_unit形成集合arrLastBallUnits,并以last_ball_unit为索引存储相应的last_ball构成集合assocLastBallByLastBallUnit

  • 对于见证人定义发生变化的交易单元arrWitnessChangeAndDefinitionJoints,检查这些交易单元是否达到稳定,并检查是否由本地见证人列表arrWitnesses中的见证人发出。然后,获取本地见证人列表arrWitnesses中见证人的定义,检查交易单元的签名并更新见证人的定义。

给定同步链的数据unstable_mc_jointsstable_last_ball_joints以及witness_change_and_definition_joints,同步链的处理过程如下:

  • 首先需要处理由unstable_mc_jointswitness_change_and_definition_joints组成的见证人证明,从而获得arrLastBallUnitsassocLastBallByLastBallUnit,其处理过程已在上面讨论了。
  • 检查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)的同步

对于主链上已经达到稳定状态的两个交易单元,主链序号在二者之间的所有交易单元构成一棵哈希树,哈希树的树根为主链序号较大的那个交易单元。

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

本地数据库表catchup_chain_balls按照mci从小到大的顺序存储了一条以last_ball_unit作为连接的主链路径,路径的起点是本地DAG中最近达到稳定的单元,路径的终点是对方DAG中最近达到稳定的单元。catchup_chain_balls中相邻的两个交易单元可以构造一棵哈希树,我们将以此为基础进行同步。假设相邻两个交易单元中mci较小的称为from_ballmci较大的称为to_ball

在进行同步时,本地节点向对方节点请求哈希树get_hash_tree,请求参数为from_ballto_ball。对方节点将mci位于from_ballto_ball之间的所有交易单元构成哈希树返回给本地节点。

本地节点接收到哈希树后,对于哈希树中的每个交易单元,检查其父单元以及跳跃列表是否是本地节点DAG已知的,然后将其添加至本地数据库表hash_tree_balls中,按照mcilevel从小到大顺序插入。处理完成后,向对方节点请求哈希树中每个交易单元的详细数据,并处理这些交易单元。

结语

本文详细讨论了ByteBall的DAG数据同步过程,分析了ByteBall处理同步问题的基本思想,并针对同步过程中使用的同步链(catchup_chain)和哈希树(hash_tree)两个基本数据结构的处理过程进行了详细分析。ByteBall采用了比较巧妙的方法来处理DAG数据同步这样较为复杂的问题,该方法十分值得研究和借鉴。

版权所有。发布者:Alan During,转载请注明出处:https://bbfans.org/2018/12/09/byteball-dag-catchup/

发表评论

登录后才能评论

联系我们

加入ByteBall技术群请添加

QR code