当前同步算法

区块同步代码分析

dag 同步

名词解释

accumulator

merkle tree，叶子节点即我们的数据的hash值节点，可以快速验证和遍历叶子节点。更多详见https://cookbook.starcoin.org/zh/docs/concepts/accumulator

dag accumulator 构建流程（待修改，原算法有问题）

1）Genesis 是 accumulator 的最左叶子节点；是 accumulator 的起始节点。

2）每次对 dag 节点的子节点做 hash 运算，hash 值作为 accumulator 中的节点下一个叶子节点。简单来说即广度优先搜索，将每次搜索的临时队列（存放父子节点对）做一次哈希运算，作为本次 accumulator的叶子节点。

3）若所有节点都没有子节点，则构建 accumulator 完成。

如下图，从 Genesis 开始，accumulator 的叶子节点都是上一层父子节点对的 hash，从而构建出一个 accumulator（只画出叶子节点，省略没有画出 accumulator 的根节点和非叶子节点）：

节点的增加

增加节点时，如上图，分别增加了 P 和 V，它的 dag 结构和 accumulator 如下：

可以看到，新增的节点，造成了 accumulator 中的3，4节点更新，多了一些关系对，且新增了 accumulator 5 节点。此时，需要从 2 节点开始更新，更新节点对的时候可以采取增量更新的方式。例如，拿节点 3 来说，当发现3需要更新时，读出老的节点对，对比新的节点对，对于新增的节点对，插入db，然后计算新的 节点 3 hash。

同步的三大任务

确认边缘节点和验证历史节点

为什么要确认和验证

主要原因有两个：

1、握手；同步两个节点之间的状态；同步

2、防止恶意 peer 假冒诚实节点，必须通过历史区块的验证才能识别出节点是否为诚实节点。

确认和验证流程

对应代码

待补充

同步新的节点

流程

对应代码

待补充

拉取区块数据

流程

对应代码

待补充

攻击和异常

accumulator 的稳定性

前面说了，如果继续插入新的节点，那么 accumulator 尾部会出现不稳定的节点，这主要是因为并发的原因，如果我们设置 ghostdag 的 k = 1，那么就跟单链一样了不稳定的问题会大大降低，但也失去了并发的特性。因此，稳定性和并发需要有一个平衡，必须保证大部分稳定（越老越稳定），也需要有一定的并发能力。

控制稳定性和并发的平衡，这里需要引入时间窗口的概念，即只能在特定的时间窗口内去加入新节点，过了窗口期，就只能在其它满足时间窗口内的节点加入新节点了。

以下是一个例子：

若不控制节点的插入，那么 accumulator 会变得很不稳定，例如下图中，突然插入一个 X 节点，导致几乎整个 accumulator 都变了：

因此必须防止 X 这样的节点插入进来，dag 的插入应该对区块的时间戳进行校验，若父子区块的时间戳差值超过窗口时间，则子区块应该被拒绝，从而减少 accumulator 的不稳定。

冒充诚实节点

所谓冒充诚实节点，即在同步 accumulator 的时候，返回垃圾 hash 值。例如，第一步，诚实节点向恶意节点请求 accumulator info 开始握手。恶意节点返回信息告知诚实节点自己有大量节点可以同步给诚实节点，此时，若诚实节点直接同步恶意节点的信息，就会被污染，实际恶意节点根本没有真实数据，或者数据都是自己创建的伪造数据。

因此，每次同步前，都必须对历史数据进行验证，直到 Genesis，也即对历史的 accmulator 叶子节点进行验证，都通过，才能同步后续节点。当然，后续节点也需要验证，保证链上的区块交易和状态都是可靠的。

网络延迟高导致矿工被孤立

若某个矿工因为网络延迟的原因，造成挖了很多矿但实际跟外面的大部队已经相差很远，此时，若网络延迟恢复到正常，矿工的链就需要和大部队同步，此时就需要：

1）找到和大部队链一致的叶子节点，验证叶子节点的前序节点一致，然后同步后续节点。

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 个区块同时打包同步，相比原来是一块块同步，相当于用了空间换取了时间。

对比单个节点对应一个accumulator叶子节点方案

其它

使用startup info存储同步快照

节点握手的时候需要同步 chain info