=nil; Foundation 在 EVM 中的完整 Mina 状态验证
由 Mikhail Komarov 撰写于 2021 年 9 月 30 日
本文翻译自 https://blog.nil.foundation/2021/09/30/mina-ethereum-bridge.html
早在 2021 年 4 月，Mina 基金会与以太坊基金会一起宣布招募设计和实现在以太坊上通过 Pickles SNARK 进行验证机制的。最后，经过严格的筛选，=nil; Foundation 的 =nil; Crypto3 团队的提案获得了官方的资助。
本文为此系列博文的第一篇文章，涵盖桥接实现的一些内容。
在 EVM 中完整地验证 Mina 协议状态意味着有可能将 Mina 主网内部发生的一切都同步到以太坊上，包括金融应用、可证明的计算等等。
Mina 中使用的 Pickles SNARK 验证器有几个组件：
计算验证证明数据的多组哈希值。这涉及使用波塞冬散列函数在 和 上进行 63 轮完整轮次计算，轮次常数和为 和 指定的 MDS 矩阵。这一步的成本相当低，并且很可能在 EVM 上以合理的 gas 成本完成计算。
检查几个算术方程。同样，这一步成本相当低，可以直接在 EVM 上实现。
执行一次 的多标量乘法 (MSM)，其中一些基数是固定值，一些基数是变量。该步骤可能会以合理的效率直接在 EVM 上计算，但它可能比步骤 1 和 2 成本更高。
对于每个 i，执行一次 的 多标量乘法，使用固定的基数组，以及可以从证明中非常有效地计算出的标量。
事实证明，第 4 步不可能直接在 EVM 上进行有效计算，除非将计算拆分为多个块。
这正是我们所采取的方法。
Mina 状态验证的给定值成本设置为 5,000,000 gas。直接的 Pickles 证明验证会花费更多成本。以太坊基金会和 Mina 基金会的 RFP 提出了一种，该方法的结果是向 EVM 提交成功 Pickles SNARK 证明验证的额外 STARK 证明，可以看作是 EVM 对 Mina 内部发生的一切的有效确认。这种方法（提交已成功验证的证明），这似乎可以将成本控制在 5,000,000 gas 范围内。前途一片光明。
我们甚至为基于 STARK 的辅助证明建议了以下基本电路。
这种证明应该在以下基本约束下生成（代表验证算法的第 4 步）。
Let:
, 为 MSM 结果。
, 为 MSM 大小。
为固定点的集合。
其中 从前一个标量计算新标量 并将其乘以
这些基本约束可以进一步优化（使用其他链、类似 Pipepnger 的方法和 STARK 友好的数学）以为证明者提供更好的证明性能并为验证者提供更低的 gas 成本。进一步的研究将确定验证算法的第 3 步是需要辅助证明还是直接在以太坊智能合约上进行验证计算。
R1CS 系统的使用成本大约是多少？让我们计算一下。
我们需要在不同的曲线中执行大小为 和大小为 的 multiexp。R1CS 系统中标量乘法每一个 bit 可能的最佳约束成本是 6 个约束。
标量乘法 × (每个标量乘法 位 × ( 个约束 / 位)) = 个约束鉴于此，如果我们使用基于 sqrt(N)-cost DLOG 的多项式承诺方案来实例化多项式承诺方案，则验证者将不得不进行大小为 的 multiexp。上述测算是使用简单的 multiexp 算法进行的。如果使用 Pippenger's > 算法，它执行大约 组操作，其中 是 > multiexp 的大小（即 ）， 是标量的大小（即， ）。使用雅可比坐标，每个组操作大约有 个字段乘法，在 EVM 上，每个字段操作使用大约 gas。所以总的来说，EVM 成本是（非常乐观地）：
gas然后还需要做一个大小为 的 multiexp，它产生 个约束，这将是： gas所以总共大约有 101,101,661 gas。约束成本是乐观的，因为在电路内部必须发生更多的事情，而 gas 成本是乐观的，因为 Pippinger 除了在 EVM 上可能昂贵的组操作外，还有其他成本，还因为链上验证器必须执行额外的操作。没有基于 R1CS 的系统可用于此任务。
现在主要验证者的成本是 Merkle 证明验证 和低度测试 ，其中 是提交多项式的级数。根据 ， 。为简单起见，在有限域（~ gas）上进行两次反演的低级数测试仅考虑主要成本。Keccak256 花费 30 gas。
标量乘法仍然是这两个组件中消耗最大的部分，因此需要完成正确的 PLONK 门构造。
根据此处 Daira 的：似乎可以在 3 个 PLONK 门中执行单个标量乘法轮（导致多项式约束为度 3) 每个标量位（3 列，每次乘法 3 行）。行数： 行低度测试：
Merkle 树操作：
总 gas 成本：
由于还需要做一个大小为 的 multiexp，对不同的大小重复相同的步骤会导致 行，这导致低度测试数 。默克尔操作数：
总 gas 成本：
gas。主要的验证成本是由这两个 MSM 带来的，因此它们总共大约消耗： gas。由于限制是 gas 并且肯定存在一些低估，因此这种标量乘法门结构方法看上去可行（即使这是一个非常粗略的估计）。Poseidon 哈希计算和线性大小的 MSM 计算将带来更多的验证成本。
将会有更多的文章来介绍这样一个特殊的设计。我们会保持更新！
关于 Mina Protocol
About Mina Protocol
Mina 是全球最轻量区块链，由参与者参与治理。
Mina 使用先进的密码学和递归 zk-SNARK 取代大量密集计算，设计一个约为 22kb 的完整区块链，相当于几条推文的大小，开创了区块链移动端可访问性的新时代。
凭借其独特的隐私功能以及和任何网站链接的能力，Mina 正在现实世界和加密货币之间建立一个私人网关，构建一个我们所有人都应享有安全民主的未来。Mina 由总部位于美国的非营利组织 Mina 基金会管理。
全球最轻量区块链 人人皆可参与
公众号｜Mina Protocol Official
微 博｜Mina_Protocol