...

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

dag accumulator

...

构建流程

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

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

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

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

...

节点的增加

例子一

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

...

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

同步的三大任务

...

例子二

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

...

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

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

额外存储

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

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

2、accumulator 叶子节点和广度优先搜索每次循环使用的队列信息的映射关系。（是否可以复用 dag 的 relationship store 待考察）

同步的三大任务

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

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

为什么要确认和验证

主要原因有两个：

1、握手；同步两个节点之间的状态；同步1、握手；谁同步谁，确定从哪里开始同步。

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

确认和验证流程

...

对应代码

待补充

同步新的节点

流程

...

对应代码

...

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

...

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

冒充诚实节点

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

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

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

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

...

其它

使用startup info存储同步快照

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

...

info（包含 accumulator info）