#2: 在EVM内验证Mina的完整状态

介绍

所以是什么？

具体是什么？

特别的是。Mina 中使用的 Pickles SNARK 验证器有如下几步：

1. 从证明的数据中计算几个哈希值。这涉及在有限域Fp 和有限域Fq上都进行 63 次完整轮次的 Poseidon 哈希函数，和特定的 MDS 矩阵 。这一步相当便宜，可以在 EVM 上以合理的 gas 成本实现。

2. 检查几个算术方程。该步骤同样相当便宜，可以直接在 EVM 上实现。

3. 执行一次规模为 的多标量乘法 (MSM)，其中一些基数是固定的，一些是可变的。该步骤也可以在合理的效率下直接在 EVM 上实现，尽管它可能比步骤 1 和 2 更昂贵。

4. 对于每个 i，在群 上执行规模为 的固定向量基数的多标量乘法，以及可以从证明中非常有效地计算出的标量。

事实证明，第 4 步无法直接在 EVM 上进行有效地计算，除非计算被拆分到几个区块中。

基于Placeholder证明系统的证明

应该为如下基本约束生成证明（代表验证算法的第 4 步）。 令：

1. 是 MSM 的结果。

2. 是 MSM 的规模。

3. 是固定点的集合。

对于 :

3. 其中 通过将前一个标量在点 上相乘，得到新的标量

基本的约束（使用加法链、类似流水线的方法和对占位符友好的数学），以便为证明者提供更好的性能，为验证者提供更低的 gas 成本。进一步的研究将确定验证算法的第 3 步是否需要包含在辅助证明中，或者是直接在以太坊智能合约上进行验证。

让证明更便宜

R1CS 系统的使用费用大概是多少？好吧，让我们计算一下。

我们需要在不同的曲线中，执行一个大小为 和一个大小为 的 multiexp 运算。

R1CS 系统中约束的最低成本是，在 1 比特的标量中实现 6 个约束。

个标量乘法 × ( 每个标量乘法 255 比特 × ( 6个约束 / 1个比特 )) = 401,080,320个约束

因此，鉴于此，如果我们使用基于 sqrt(N)-cost DLOG 的多项式承诺方案来实例化多项式承诺方案，则验证者将必须执行大小为 的 multiexp 运算。

如上的估计是使用简单的多重表达式算法进行的。如果改为使用流水线的 > 算法，该算法大致执行 ，其中 是 multiexp 的大小（即 ） 和  是标量的大小（即 )。 使用雅可比坐标，每个群运算中大约是16个场乘法，在 EVM 上每个场乘法操作大约需要 8 gas。

所以总的来说，（非常乐观的估计下）EVM 成本是：

然后还需要做一个大小为 $$2^{17}$$ 的 multiexp 运算，结果需要14161个约束：

所以总共大约是 101,101,661 gas。这是在非常乐观的估计下的约束成本，因为在电路内部有更多的计算也在进行，gas 成本也是乐观情况下的估计，因为流水线算法除了群运算外，还有其他可能在 EVM 昂贵的计算，同时因为链上验证者必须执行额外的运算操作

没有基于 R1CS 的系统可用于此类任务。

那么如何在保持跨链桥费用便宜的同时，保证跨链桥无需信任呢？

具体来说。现在验证者的主要成本是 Merkle 证明验证()和低度测试 ()， 其中 是多项式承诺的次数。根据https://eprint.iacr.org/2019/1400.pdf，  。为简单起见，对于低度测试只考虑最主要的成本，两次有限域上的反演大约需要 30000 gas。Keccak256 消耗 30 gas。

标量乘法仍然是这两个组件中消耗最多的部分，因此需要完成正确的 PLONK 门构造。

根据 Daira 的结果： https://github.com/zcash/zcash/issues/4254#issuecomment-565761663  ，似乎可以在每个标量比特下，在 3 个 PLONK Gate（多项式约束为3) 中执行 1 次标量乘法（3 列，每次乘法 3 行）。

行数：

低度测试：

Merkle验证：

整体Gas成本：

因为它也同样需要做一个大小为 的 multiexp 运算，对不同的规模重复上述相同的步骤需要 行，这需要 个低度测试

增加merkle运算：

整体Gas成本：

主要的验证成本是这两个 MSM ，因此它们总共大约消耗： 。

因为上限是5M gas，存在一些低估，这种标量乘法的证明系统看上去是可行的（即使这是一个非常粗略的估计）。Poseidon 哈希计算和线性大小的 MSM 计算将带来更多的验证成本。

什么时候上线？