当前同步算法
dag 同步
名词解释
tips 节点
即 dag 的尖端节点。也就是如果我们把 dag 看成单链，那么就是当前高度最高的节点，放到 dag 图中，则是在当前某个时间领域内的无子区块的节点。
确认的 tips 节点表示需要从这些节点开始同步后续的子节点。
accumulator
merkle tree，叶子节点即我们的数据的hash值节点，可以快速验证和遍历叶子节点。更多详见https://cookbook.starcoin.org/zh/docs/concepts/accumulator
dag accumulator 构建流程
1）Genesis 是 accumulator 的最左叶子节点；是 accumulator 的起始节点。
2）每次对 dag 节点的子节点做 hash 运算，hash 值作为 accumulator 中的节点下一个叶子节点。若 dag 的节点没有子节点，则保留下来，继续参与 hash 运算。
3）若所有节点都没有子节点，则构建 accumulator 完成，tips节点也找到了。
如下图，从 Genesis 开始，accumulator 的叶子节点都是上一个节点的子节点的 hash，从而构建出一个 accumulator（只画出叶子节点，省略没有画出 accumulator 的根节点和非叶子节点）：
使用 accumulator 确认 tips 节点
构建好 accumulator 后，accumulator 的叶子节点中最右一个节点就是 tips 节点。
例如前面的例子中，JML 就是当前 dag 的 tips 节点。
tips节点后续节点的增加
tips 增加节点时，如上图，分别增加了 P 和 V，它的 dag 结构和 accumulator 如下（新增黄色节点）：
可以看到，另一个节点的 accumulator 和 本节点的 accumulator 从 JMKL 开始就不一致，因此确认的 tips应该是 JMKL 而不是 JML。
另一种情况是如下图：
这种情况下，由于 V 的父节点包含了 K，那么导致 ac
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 的不稳定。
冒充诚实节点
所谓冒充诚实节点，即在同步 accumulator 的时候，返回垃圾 hash 值。例如，第一步，诚实节点向恶意节点请求 accumulator info 开始握手。恶意节点返回信息告知诚实节点自己有大量节点可以同步给诚实节点，此时，若诚实节点直接同步恶意节点的信息，就会被污染，实际恶意节点根本没有真实数据，或者数据都是自己创建的伪造数据。
因此，每次同步前，都必须对历史数据进行验证，直到 Genesis，也即对历史的 accmulator 叶子节点进行验证，都通过，才能同步 tips 后续节点。当然，后续节点也需要验证，保证链上的区块交易和状态都是可靠的。
网络延迟高导致矿工被孤立
若某个矿工因为网络延迟的原因，造成挖了很多矿但实际跟外面的大部队已经相差很远，此时，若网络延迟恢复到正常，矿工的链就需要和大部队同步，此时就需要：
1）找到和大部队链一致的 tips 节点，验证 tips 节点的前序节点一致，然后同步后续节点。
2）回退交易状态，删除被回退的交易记录；
第一个在同步流程中已经解决，但交易状态的回退可能需要想想怎么设计才好。相比之前的回滚， dag 引入了并发挖矿，交易的冲突或重复交易的问题会更多，还得想想有没有更好的设计。
父节点还未同步子节点就被广播过来了
由于引入并发挖矿，会出现子节点的父节点还未同步，子节点就被广播或者通过过来，因此需要增加一个节点池，若一个节点的父节点至少有一个不在 db 中，那么这个节点就只能先放在节点池，直到父节点都同步过来为止。
在节点池的节点不能执行交易，也不参加同步。
时间复杂度
最差情况
若有 n 个节点，dag 的 链接参数为 k，那么，最差的情况下，每次只有一个矿工成功挖矿，此时就相当于单链的情况， accumulator 的内容和单链的 accumulator 完全一样，即都有一个字节点。那么同步 accumulator 的时间复杂度为 O(n)，空间复杂度也为O(n)，和原来的复杂度一样。
最优情况
相比只有一个矿工成功挖矿，最优的情况下，一共有 k 个矿工（或者一个矿工同时挖中 k 个区块）产生 k 个区块，此时， accumulator 的叶子节点有 n / k 个，时间复杂度为 O(n / k)，可见 k 越大，accmulator 同步越快。空间复杂度没有变化，因为依然需要同步 n 个区块 hash 值。
平均情况
时间复杂度，即每次只有 k / 2 个区块被挖出，即O(2n / k)，因此依然还是 O(n / k)，取决于我们设置的 k 值或者实际并发时的挖矿数量。空间复杂度依然是O(n)。
另外，由于每次同步区块数据时，是批量同步，即最大的情况下，有 k 个区块同时打包同步，相比原来是一块块同步，相当于用了空间换取了时间。