Hi 游客

更多精彩,请登录!

比特池塘 区块链技术 正文

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

棋丝集日授
193 0 0
引言
8 m' R2 w( k6 S相比于传统单链结构的区块同步过程,DAG结构的交易数据同步过程要更加复杂。其复杂性主要体现在以下两个方面:
- U# z7 S) X: r7 S/ t从同步数量上来看:单链结构中区块打包了一批交易数据,只需要对区块进行同步及其正确性的检查,这样就完成了一批交易数据的检查;而DAG结构需要对每一笔交易数据单独进行同步和检查,时间和计算复杂度成倍增加。
! z% c0 O0 ]% R4 E8 y, I& I从连接关系上来看:单链结构的区块只有一个父区块,整个结构中只有单一路径,连接关系的同步和检查比较简单;而DAG结构中交易数据可能有多个父交易,连接关系的同步和检查更为复杂。6 L+ b6 A& J5 L- L- t" u7 {# D: H
DAGX采用的是“分而治之”的思想,通过将整个DAG分割成多棵哈希树(hash_tree),以哈希树作为基本单元来进行同步。为方便理解,哈希树在一定程度上可以跟单链结构中的区块进行类比,只不过哈希树的分割方式具有更大的灵活性。在DAGX中,哈希树的分割方式以同步链(catchup_chain)的形式实现。同步链和哈希树构成了DAGX的DAG同步的基本数据结构。2 Q7 X& G- z1 k- ^5 P
基本流程
2 m: _# w' e: m( @# k$ A当全节点A需要与全节点B进行同步时(以下讨论中,我们称全节点A为本地节点,全节点B为对方节点),其同步的基本流程如下图所示:
7 R' z, s8 X* d4 D$ E  e& J) C3 a
# d' ?, t$ \/ |) H. l, RDAGX中DAG交易数据同步算法详解
0 n$ F$ s9 {. x6 r: s同步过程主要包括以下几个基本步骤:% d( r8 E, c8 ~. J9 J( c8 L0 r
本地节点向对方节点发送catchup请求,参数为本地DAG的属性,包括节点A的见证人列表arrWitnesses、已知的稳定单元主链序号last_stable_mci、已知的最近的主链序号last_known_mci;6 c! L5 X; {' z$ s0 y  ^
对方节点根据本地节点的请求,按照其所具有的DAG构造同步链catchup_chain返回给本地节点;6 l% N- v# V* C4 l+ W" ~
本地节点根据同步链catchup_chain的信息,逐步请求哈希树hash_tree,从而同步本地DAG。
: Z2 x  E; V% Z同步链catchup_chain是当前主链的一种分割方式,本质上它是一条以last_ball_unit作为连接的主链路径,路径的起点是本地节点DAG中最近达到稳定的交易单元,路径的终点是对方节点DAG中最近达到稳定的交易单元。
! l. m$ M$ `4 ^1 c! f" U3 t. U依照上述同步过程,我们可以大体的描绘出本地DAG的变化图如下所示:
- ?9 Q0 K$ A  ^+ \. v9 W' z! V( n8 n. p# @
DAGX中DAG交易数据同步算法详解
) E+ J+ ?- w& x% o同步链(catchup_chain)的生成及处理' X% H# R+ t. b% i! o
首先,我们给出DAGX中与DAG数据同步有关的几张数据表:
4 T& ]0 v% Y/ m2 e* S0 vballs:用于保存已同步且经过验证的稳定交易单元;
5 ^" W4 I0 d, M- c: dhash_tree_balls:用于保存已同步的哈希树;
% t+ V* G5 I% T# A# Rcatchup_chain_balls:用于保存已获取的同步链。
, o  a& {9 d2 s3 G1 X同步链的生成
; @4 m/ F) ~; p9 Y6 G6 o3 L. w当对方节点接收到本地节点的catchup请求后,它将根据请求参数及其DAG数据生成同步链。在生成同步链之前,首先需要生成见证人证明witness_proof,它主要是用来处理见证人的定义变化,以及获取相应见证人列表条件下主链上的交易单元。
* [) b  x7 ^, f* k& v在给定catchup请求参数见证人列表arrWitnesses及已知最近稳定单元的主链序号last_stable_mci的条件下,见证人证明包括以下两部分数据:7 G0 }7 h, @9 @7 m- }
主链上未达到稳定的交易单元arrUnstableMcJoints:在min_retrievable_mci之后出现的主链上的交易单元,min_retrievable_mci指的是当前DAG中最近稳定单元的last_ball的mci。
3 Z/ }9 m8 d: w( ?5 ?( w/ Q见证人定义发生变化的交易单元arrWitnessChangeAndDefinitionJoints:在last_stable_mci之后出现的见证人地址定义新增或修改的交易单元。
3 t; @, M! A( ?5 s3 b* h1 [' c2 k8 F在生成见证人证明的过程中,同时检查当前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,那么说明对方的主链已经跟本地达到同步状态,不需要再进行数据同步过程。
2 w/ Q- b# ~/ l此外,如果对方节点的last_known_mci在本地未出现或者未达到稳定状态,则对方的主链也已经跟本地达到同步状态,不再需要进行同步过程。* |( ]; u, M9 f- d+ U
生成的同步链由以下几部分数据组成:
6 O$ N0 f' q0 ^/ @% t1 O0 M主链上未达到稳定的交易单元集合
2 S2 n) i. @4 M6 a* H. ^( a* ^unstable_mc_joints:在min_retrievable_mci之后出现在主链上的交易单元,即见证证据中的arrUnstableMcJoints。
6 |2 s6 n4 I1 Q1 E3 B$ t: O主链上已稳定的交易单元集合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通过见证证据获得。% l7 y( S. A! A% l, y; j# F" @
见证人定义发生变化的交易单元集合witness_change_and_definition_joints:在last_stable_mci之后出现的见证人地址定义新增或修改的交易单元,即见证证据中的arrWitnessChangeAndDefinitionJoints。
* l4 G6 U* h( G同步链的处理
  w- F% f) L& v& r2 e- L0 E与同步链的生成相对应的是同步链的处理过程,当本地节点接收到对方节点返回的同步链时,它将首先对见证人证明进行处理。返回的同步链中
3 Z9 s/ G  v+ c$ Y5 y5 Wunstable_mc_joints及witness_change_and_definition_joints对应见证人证明中的两部分数据arrUnstableMcJoints及arrWitnessChangeAndDefinitionJoints,其处理过程如下:
2 A+ u2 x. j1 @+ X) o  r8 }从arrUnstableMcJoints的顶端结点开始回溯,当遇见大多数见证人后,选取剩余交易单元的last_ball_unit形成集合arrLastBallUnits,并以last_ball_unit为索引存储相应的last_ball构成集合assocLastBallByLastBallUnit。6 i5 [" y4 G3 ~8 G5 V
对于见证人定义发生变化的交易单元arrWitnessChangeAndDefinitionJoints,检查这些交易单元是否达到稳定,并检查是否由本地见证人列表arrWitnesses中的见证人发出。然后,获取本地见证人列表arrWitnesses中见证人的定义,检查交易单元的签名并更新见证人的定义。
7 L1 ^2 p" V5 X给定同步链的数据unstable_mc_joints、stable_last_ball_joints以及witness_change_and_definition_joints,同步链的处理过程如下:
- u+ R3 D* l- U& ~& `- P首先需要处理由unstable_mc_joints及witness_change_and_definition_joints组成的见证人证明,从而获得arrLastBallUnits及assocLastBallByLastBallUnit,其处理过程已在上面讨论了。
6 |; A0 v; ^0 t6 b, B9 C3 k" ^检查stable_last_ball_joints中第一个交易单元是否在arrLastBallUnits中,并以其作为同步链的处理起点last_ball_unit。
% Q7 Z9 c: m# _1 E2 C+ Z依次检查stable_last_ball_joints中的交易单元,检验前一个交易单元的last_ball_unit是否指向后一个交易单元。" M- f7 l$ `, ?3 q  {
检查stable_last_ball_joints中的最后一个交易单元是否为本地节点DAG已知的并且达到稳定状态,并将其替换为本地DAG的最近稳定交易单元。+ q/ r" V8 t2 E4 H8 e; b; y
检查stable_last_ball_joints中的倒数第二个交易单元是否不是本地DAG并且没有达到稳定状态,即stable_last_ball_joints中只有最后一个交易单元满足本地DAG已知且达到稳定状态。
$ Q4 g. l3 a3 V/ F0 w7 m* f将stable_last_ball_joints作为同步链数据插入本地数据库表catchup_chain_balls中,按照mci从小到大的顺序插入。
! p! F) T$ |' p5 S- `/ N) @同步链处理后,本地节点DAG形成了一种哈希树的分割方式,并存储在数据表catchup_chain_balls中,为之后逐步进行哈希树同步提供了依据。
: c2 E& c, U! i5 U哈希树(hash_tree)的同步2 b3 t- @7 y# U$ L
对于主链上已经达到稳定状态的两个交易单元,主链序号在二者之间的所有交易单元构成一棵哈希树,哈希树的树根为主链序号较大的那个交易单元。
; I5 H' b. e4 F2 {
$ D; f( i2 b4 d! d( n) f$ u本地数据库表catchup_chain_balls按照mci从小到大的顺序存储了一条以last_ball_unit作为连接的主链路径,路径的起点是本地DAG中最近达到稳定的单元,路径的终点是对方DAG中最近达到稳定的单元。catchup_chain_balls中相邻的两个交易单元可以构造一棵哈希树,我们将以此为基础进行同步。假设相邻两个交易单元中mci较小的称为from_ball,mci较大的称为to_ball。% L+ D* G; z' A! z7 v- F4 R
在进行同步时,本地节点向对方节点请求哈希树get_hash_tree,请求参数为from_ball和to_ball。对方节点将mci位于from_ball和to_ball之间的所有交易单元构成哈希树返回给本地节点。3 `8 s- B3 Y' a! {% f) R# n
本地节点接收到哈希树后,对于哈希树中的每个交易单元,检查其父单元以及跳跃列表是否是本地节点DAG已知的,然后将其添加至本地数据库表hash_tree_balls中,按照mci和level从小到大顺序插入。处理完成后,向对方节点请求哈希树中每个交易单元的详细数据,并处理这些交易单元。
' v6 T6 C# x" r8 G5 |7 q9 A# f6 [/ H- K结语
; J) l, g. a/ z8 ~- x/ W本文详细讨论了ByteBall的DAG数据同步过程,分析了ByteBall处理同步问题的基本思想,并针对同步过程中使用的同步链(catchup_chain)和哈希树(hash_tree)两个基本数据结构的处理过程进行了详细分析。ByteBall采用了比较巧妙的方法来处理DAG数据同步这样较为复杂的问题,该方法十分值得研究和借鉴。
BitMere.com 比特池塘系信息发布平台,比特池塘仅提供信息存储空间服务。
声明:该文观点仅代表作者本人,本文不代表比特池塘立场,且不构成建议,请谨慎对待。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

成为第一个吐槽的人

棋丝集日授 小学生
  • 粉丝

    0

  • 关注

    0

  • 主题

    1