...
如下图,从 Genesis 开始,accumulator 的叶子节点都是上一个节点的子节点的 hash,从而构建出一个 accumulator(只画出叶子节点,省略没有画出 accumulator 的根节点和非叶子节点):
...
...
确认tips节点和验证历史节点
为什么要确认和验证
主要原因有两个:
1、握手;同步两个节点之间的状态;同步
2、防止恶意 peer 假冒诚实节点,必须通过历史区块的验证才能识别出节点是否为诚实节点。
确认和验证流程
...
对应代码
待补充
同步新的tips节点
获取后续节点
拉取数据内容
对应代码
拉取区块数据
攻击和异常
使用老旧的父节点作为新节点造成大量回滚
冒充诚实节点
时间复杂度
获得 current tips
只有 Genesis 区块
此时 Genesis 区块就是 current tips。 Genesis 是一个特殊的 tips,如果当前 tips 是 Genesis,那么说明 dag 中前面没有 parents 了。
starcoin 的单链在转向 dag 升级时,会指定某一个区块为 dag 的 Genesis 区块,以此区块开始,后续都会走 dag 协议。
普通的 tips 区块
...
例如上图的 J,M 和 L 就是普通的 tips 节点。普通 tips 节点,经过不断的回溯父节点,总是能回到 Genesis 节点,可能有些 tips 节点能提前回到 Genesis 节点,但若两个 node 有相同的 dag,则它们返回到 Genesis 所沿途的 accmulator 节点应该是一致的。
确认 tips 节点以及前序节点
为什么要确认 tisp 节点
相当于两个 node 要先握手,保证两个 node 的tips节点之前的 dag 结构是一致的。
为什么要确认前序节点
因为如果对方是恶意节点,我们用 accumulator info 确认的时候无法验证对方的节点是否完整可靠,因此必须发送前序节点验证。
构建 accumulator
1)Genesis 是 accumulator 的最左叶子节点;
2)每次tips 节点的子节点做 hash 运算,作为本次 tips节点的下一个 accumulator 兄弟节点;
如下图,从 Genesis 开始,accumulator 的叶子节点都是上一个节点的子节点的 hash,从而构建出一个 accumulator(只画出叶子节点,省略没有画出 accumulator 的根节点和非叶子节点):
...
使用 accumulator 确认 tips 节点
构建好 accumulator 后,可以拿出 accumulator 的最后一个节点(存放在 startup info 中,似乎从 accumulator 中读也行)去另一个 node 中同步看大家的 accumulator 是否相同,若相同,开始从 tips 节点拉取后面的子节点。
...
使用 accumulator 确认 tips 节点
构建好 accumulator 后,accumulator 的叶子节点中最右一个节点就是 tips 节点。
例如前面的例子中,JML 就是当前 dag 的 tips 节点。
tips节点后续节点的增加
tips 增加节点时,如上图,分别增加了 P 和 V,它的 dag 结构和 accumulator 如下(新增黄色节点):
...
cumulator 从 JMKL 开始后面也是不一致的,那么此时确认的 tips 节点应该也是 JMKL,即应该从 JMKL 开始同步后续的子节点。
...
由此可见,增加新节点会造成 accumulator 的尾部发生变化,这个是正常的,对比第一张图,其 tips 节点是 JML,和其前一个节点仅少了一个 K,可见 JML 作为 tips 是很不稳定的,被新来的 PMV 替代也是正常。
因此,同步时,需要讲 JMKL 这样的节点找出来。
同步的三大任务
确认tips节点和验证历史节点
为什么要确认和验证
主要原因有两个:
1、握手;同步两个节点之间的状态;同步
2、防止恶意 peer 假冒诚实节点,必须通过历史区块的验证才能识别出节点是否为诚实节点。
确认和验证流程
...
对应代码
待补充
同步新的tips节点
获取后续节点
拉取数据内容
对应代码
拉取区块数据
攻击和异常
accumulator 的稳定性
前面说了,如果 tips 节点继续插入新的节点,那么 accumulator 尾部会出现不稳定的节点,这主要是因为并发的原因,如果我们设置 ghostdag 的 k = 1,那么就跟单链一样了不稳定的问题会大大降低,但也失去了并发的特性。因此,稳定性和并发需要有一个平衡,必须保证大部分稳定(越老越稳定),也需要有一定的并发能力。
控制稳定性和并发的平衡,这里需要引入时间窗口的概念,即 tips 节点只能在特定的时间窗口内去加入新节点,过了窗口期,就只能在下一个 tips 节点加入新节点了。
以下是一个例子:
若不控制节点的插入,那么 accumulator 会变得很不稳定,例如下图中,突然插入一个 X 节点,导致几乎整个 accumulator 都变了:
...
因此必须防止 X 这样的节点插入进来,因此,dag 的插入应该对区块的时间戳进行校验,若父子区块的时间戳差值超过窗口时间,则子区块应该被拒绝,从而减少 accumulator 的不稳定。
冒充诚实节点
时间复杂度
同步流程图
...
其它
使用startup info存储同步快照
节点握手的时候需要同步 chain info
...