=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