ALEO采用的是哪种算法？

最新版的算法核心称为 Synthesis Puzzle，其核心是针对每个 epoch 固定产生一个共同的 EpochProgram，通过为输入和 EpochProgram 构建 R1CS 证明电路，产生对应 R1CS assignment （即大家提到的 witness）并作为 Merkle tree 的叶子节点，计算出所有叶子节点后生成 Merkle root 并转换为 solution 的 proof_target。构建 Synthesis Puzzle 的详细流程和规范如下：

1/ 每一次 puzzle 计算称为 nonce，它是由接收挖矿奖励的地址、epoch_hash 和 一个随机数 counter 构建，每次需要计算新的 solution 时可以通过更新 counter 获得新的 nonce

2/ 每一个 epoch 中，网络中所有 prover 需要计算的 EpochProgram 是同一个，它由当前的 epoch_hash 产生的随机数从指令集中抽样出来，抽样逻辑是：

· 指令集是固定的，每一个指令（instruction）包含一个或多个计算操作，每一个指令有一个预设的权重和操作计数

· 抽样时根据当前 epoch_hash 生成随机数，根据该随机数从指令集中结合权重获取指令并顺序排列，累积操作计数到 97 之后停止抽样

· 将所有指令组成 EpochProgram

3/ 使用 nonce 作为随机数种子生成 EpochProgram 的输入

4/ 聚合 EpochProgram 对应的 R1CS 和 input，进行 witness （R1CS assignment） 计算

5/ 计算出所有 witness 后，这些 witness 将被转换为对应的 merkle tree 的叶子节点序列，merkle tree 是一个深度为 8 的 8 元 K-ary Merkle tree

6/ 计算 merkle root 并将其转换为 solution 的 proof_target，判断其是否满足当前 epoch 的 latest_proof_target，若满足则计算成功，提交上文中构建输入需要的 reward address、epoch_hash 和 counter 作为 solution 并广播

7/ 同一个 epoch 中可通过迭代 counter 的方式更新 EpochProgram 的输入进行多次 solution 计算

挖矿的变化和影响

经过此次更新后，puzzle 由生成 proof 转变为生成 witness，每一个 epoch 内的所有 solution 计算逻辑一致但是不同 epoch 计算逻辑有较大区别。

从之前的测试网中我们可以发现很多优化手段着重于使用 GPU 对生成 proof 阶段的 MSM 和 NTT 计算进行优化从而提高挖矿效率，此次更新完全摒弃了这部分计算；同时由于生成 witness 的过程产生于执行一个跟随 epoch 变化的 program，其中的指令将存在部分串行执行的依赖关系，所以实现并行化具有不小的挑战。