当前同步算法

https://starcoin.atlassian.net/wiki/spaces/CHAIN/pages/168034312

dag 同步

名词解释

accumulator

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

dag accumulator 构建流程

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

2）从 Genesis 开始循环，每次取上一次节点的子节点，直到没有子节点为止。这里可以理解为， accumulator 的叶子是每次广度优先遍历图的时候的临时队列hash值。另外，构建子节点到 accumulator 叶子节点的映射关系，如果子节点出现在多个叶子节中，则映射到最小 index 那个叶子节点。

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

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

Open

节点的增加

例子一

增加节点时，如上图，分别增加了 P ，其父节点为 J 和 M，它的 dag 结构和 accumulator 如下，可以看到 P 挂在 J 和 M 下，而 J 和 M 映射到 accumulator 叶子 3 这个节点，因此，需要对 3 所对应的叶子节点重新生成后续节点：

Open

例子二

增加 P 和 V 节点，V 节点挂在 K，L 和 D 下，D 对应了 1 节点，而 K 和 L 对应了 accumulator 的 叶子节点 2，因此从 1 开始，需要重新生成后续的 3， 4， 5：

这里可以看到保存广度优先搜索的队列好处就是某个节点新加入了子节点，那么对其拓扑顺序是会有影响的，如果不保存搜索使用的队列，那么就需要回溯父节点，uncle 节点（例如 V 的加入，导致第二层的拓扑顺序变化，因此需要去找 D 的父节点和兄弟节点，需要回溯到 Genesis 节点，再重新广度优先遍历），逻辑比较复杂，因此这里选择了保存广度优先搜索使用的队列。

此外，使用 accumulator 模型保存，有助于两个网络 peer 节点相互核对信息，只需要核对 accumulator 信息就可以保证对应的 dag 图是相同的。accumulator 对于验证和遍历有比较简单的接口。

额外存储

从上面看出，这个方案还需要额外保存以下信息：

1、区块节点和 accumulator 的叶子节点的映射关系。因为我们需要马上找到某个区块在哪个叶子节点中，由于 accumulator 叶子节点是 dag 的 各层子节点 hash，因此需要额外存储这个映射关系；

2、accumulator 叶子节点和广度优先搜索每次循环使用的队列信息的映射关系。此处可以复用 relationship store，只需要存储子节点队列即可。

同步的三大任务

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

所谓确认和验证，即先确认两个网络 peer 节点的 accumulator 是对应同一个 dag 图的，哪怕两者 accumulator 其中一个相对另一个不那么完整。

为什么要确认和验证

主要原因有两个：

1、握手；谁同步谁，确定从哪里开始同步。

2、防止恶意 peer 假冒诚实节点，必须通过历史区块的验证才能识别出节点是否为诚实节点。（否者恶意节点可以说自己完全符合状态，让诚实节点拉取垃圾数据，直到开始验证 pow 环节才能发现问题）

确认和验证流程

对应代码

待补充

同步新的节点

流程

对应代码

待补充

拉取区块数据

流程

对应代码

待补充

攻击和异常

accumulator 的稳定性

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

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

以下是一个例子：

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

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

冒充诚实节点

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

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

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

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

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

其它

使用startup info存储同步快照

节点握手的时候需要同步 chain info（包含 accumulator info）