ALEO采用的是哪种算法?

19次阅读
没有评论

最新版的算法核心称为 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,其中的指令将存在部分串行执行的依赖关系,所以实现并行化具有不小的挑战。

正文完
 0
aleocn
版权声明:本站原创文章,由 aleocn 于2024-06-28发表,共计1156字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)