在EVM上对Mina区块链的完全验证

u_2Ygx8XS5Ss1aObgOFjkA
发布于 2024-11-21 13:35
阅读 51

以太坊基金会和Mina基金会发布提案征集（RfP），旨在设计并实现一种在以太坊上验证Pickles SNARK的机制。目标是实现Mina区块链在以太坊上的完全验证，从而实现两个链之间的互操作，并使应用程序更广泛地在以太坊上使用递归SNARK。该提案详细介绍了验证过程中的关键步骤，包括哈希计算、算术方程检查和多标量乘法（MSM），并提出了使用辅助证明系统来验证计算密集型步骤的方案。

# 在 EVM 上完全验证 Mina 区块链

## 介绍

\[以太坊基金会](https://ethereum.foundation/) (EF) 和 \[Mina 基金会](https://minaprotocol.com/) (MF) 宣布了一项提案征集 (RfP)，旨在设计和实现一种在以太坊上验证 Pickles SNARK 的机制。

在 EVM 上直接验证这个 SNARK 似乎成本太高。因此，我们接受对 Pickles SNARK 执行一些预处理的系统的提案（例如，通过计算一个 STARK 来验证 Pickles SNARK，而它本身可以在 EVM 上有效地验证）。

此举的目标是 (1) 在以太坊上实现 Mina 区块链的完全验证，以实现两个链之间的互操作，以及 (2) 使应用程序更普遍地在以太坊上使用递归 SNARK。

## 目录

\[toc]

## 定义

设

\\begin{align\*}
p &= 2^{254} + 45560315531419706090280762371685220353 \\\
q &= 2^{254} + 45560315531506369815346746415080538113 \\\
\\mathbb{G}\_1 &= \\left\\{ (x, y) \\in \\mathbb{F}\_p \\mid y^2 = x^3 + 5 \\right\\} \\\
\\mathbb{G}\_2 &= \\left\\{ (x, y) \\in \\mathbb{F}\_q \\mid y^2 = x^3 + 5 \\right\\} \\\
n\_1 = 17 \\\
n\_2 = 16
\\end{align\*}

注意 $\|\\mathbb{G}\_1\| = q$ 且 $\|\\mathbb{G}\_2\| = p$。

Mina 中使用的 Pickles SNARK 验证器有几个组成部分

1.  从证明数据中计算多个哈希值。这涉及使用 Poseidon 哈希函数，在 $\\mathbb{F}\_p$ 和 $\\mathbb{F}\_q$ 上都进行 63 轮完整运算，其舍入常数和 MDS 矩阵在 \[此处针对 $\\mathbb{F}\_p$]（https://github.com/o1-labs/marlin/blob/master/oracle/src/pasta/fp.rs）和 \[此处针对 $\\mathbb{F}\_q$]（https://github.com/o1-labs/marlin/blob/master/oracle/src/pasta/fq.rs）中指定。这一步相当便宜，并且很可能以合理的 gas 成本在 EVM 上实现。
2.  检查几个算术等式。同样，这一步相当便宜，可以直接在 EVM 上实现。
3.  执行一次大小为 $2 n\_2 + 4 + (2 + 25) = 63$ 的多标量乘法 (MSM)，其中一些基是固定的，而另一些是可变的。这一步很可能可以直接在 EVM 上以合理的效率实现，尽管它可能比步骤 1 和 2 更昂贵。
4.  对于每个 $i$，在 $\\mathbb{G}\_i$ 上执行一次大小为 $2^{n\_i}$ 的多标量乘法，使用一个固定的基数组，以及可以从证明中非常有效地计算出的标量。

除非计算被分成几个区块，否则步骤 4 很难直接在 EVM 上有效地计算。作为替代方案，我们建议资助接受者生成一个额外的证明（例如，一个基于 AIR 的 STARK 或一个基于 BN128 的 SNARK），以验证该步骤的计算。

## 参考实现

Pickles 验证器的 Rust 实现可以在 \[此处](https://github.com/o1-labs/marlin/blob/master/dlog/plonk/src/verifier.rs#L207) 找到。它调用一个过程来验证底层的多项式承诺打开，其代码位于 \[此处](https://github.com/o1-labs/marlin/blob/master/dlog/commitment/src/commitment.rs#L612)。

## 扩展讨论

如上所述，验证器中最昂贵的部分，以及可能必须在 EVM 之外的辅助证明系统中验证的部分，是两个 MSM。在本节中，我们将更详细地描述这些 MSM。设 $\\mathbb{G}\_k$ 是上面定义的两个曲线之一，设 $\\mathbb{F}$ 是它的标量域。设 $\\phi \\colon \\{ 0, 1 \\}^{128} \\to \\mathbb{F}$ 是由 \`to\_field\` 定义的算法 \[此处](https://github.com/o1-labs/marlin/blob/49f81edc9c86e5907d26ea791fa083640ad0ef3e/oracle/src/sponge.rs#L33)。

给定一个整数 $i < 2^{n\_k}$，定义 $\\mathsf{bits}(i)$ 为长度为 $n$ 的小端位数组，表示 $i$ 的二进制展开。

从给定的 Pickles SNARK 中，将导出一个挑战序列 $c\_0, \\dots, c\_{n\_k - 1} \\in \\{ 0, 1 \\}^{128}$。相关的 MSM 是

$$
\\sum\_{i = 0}^{2^{n\_k} - 1} s\_i G\_i = H
$$
其中
$$
s\_i := \\prod\_{\\substack{0 \\leq j < n\_k \\\ \\mathsf{bits}(i)\[j\] = 1}} \\phi(c\_j)
$$
其中 $G\_0, \\dots, G\_{2^{n\_k} - 1} \\in \\mathbb{G}$ 是由 \[此算法](https://github.com/o1-labs/marlin/blob/master/dlog/commitment/src/srs.rs#L70) 生成的固定群元素序列。

### 观察

标量序列 $\\left\\{ s\_i \\right\\}\_{0 \\leq i < 2^{n - 1}}$ 可以以这样一种方式重新排序，即每个项都可以通过前一个项最多通过一次乘法和一次除法获得。如果也相应地重新排序基的固定序列 $\\left\\{ {G}\_i \\right\\}\_{0 \\leq i < 2^{n - 1}}$，这使得 MSM $\\sum\_i s\_i {G}\_i$ 非常适合用于使用基于 AIR 的 STARK 进行验证，因为计算可以表示为一个循环，其中每次迭代都可以非常有效地表示为算术计算（模固定查找表中的查找）。

## 代码版本

将作为规范的代码的 github commit 将在项目开始时确定。该代码在 https://github.com/o1-labs/marlin 和 https://github.com/minaprotocol/mina/ 上公开开发。

## 流程总结

整个流程可以总结如下：

1.  **请求：** 发布 RfP（此帖子）
2.  **收集：** 供应商提交提案
3.  **审议：** EF 和 MF 决定接受哪个提案，并根据接受提案的资源和需求制定计划。
4.  **提议：** EF 和 MF 向供应商提议该计划，并根据供应商的反馈进行调整
5.  **开始：** 供应商接受并开始工作

## 参与时间表

拟议的参与时间表约为 6 个月。

EF 和 MF 的成员将随时解答规划和实施过程中的问题和评论，以便尽可能方便供应商。

## 交付成果

交付成果将采用以下形式

\- 一个程序 \`aux-proof-gen\`，它将 Mina 区块链状态和关联的 Pickles SNARK 作为输入，并生成一个辅助证明。必须能够在具有最多 16 个核心和 32 GB 内存的云实例上在 15 分钟内运行此程序。
\- 一个以太坊智能合约 \`aux-proof-verify\`，它具有与 Mina 区块链状态相对应的内部状态，并且只有在提供验证的辅助证明时才能设置为新状态。该合约应最多使用 5M gas。
\- 对于给定的 Mina 区块链状态 $s$，如果且仅当拥有与状态 $s$ 关联的 Pickles SNARK，才可以使用 \`aux-proof-gen\` 生成一个辅助证明，该证明在具有状态 $s$ 的 \`aux-proof-verify\` 上验证。
\- 已实现的辅助证明系统的高级描述。
\- 两篇博客文章，描述工作的进展情况；一篇在参与过程中进行到一半时发布，另一篇在结束时发布。
\- 在此 RfP 下交付的所有代码将根据 Apache License, Version 2.0 发布。

## 费用结构

### 发票

根据本 RfP 的时间表，选定的供应商预计将提交 2 份发票：

\- 在参与开始时，第一份发票为参与总费用的 50%
\- 在交付所有交付成果（包括代码和最终博客文章）以及 5 天审核期后，第二份发票为参与总费用的 50%。

### 付款方式

供应商可以选择以法定货币（通过银行转账）、ETH 或 MINA 支付。

如果供应商选择以 ETH 支付，则协议下描述的 ETH 的价值将是在到期日前一天（美国东部时间下午 4 点）纽约证券交易所收盘时（如 https://www.coingecko.com 所述）的美元价值。

如果供应商选择以 MINA 支付，则协议下描述的 MINA 的价值将是：
\- 如果存在具有公开访问的 MINA 代币市场的信誉良好的交易所，则为到期日前一天（美国东部时间下午 4 点）纽约证券交易所收盘时（如 https://www.coingecko.com 所述）的美元价值；
\- 或者，如果不存在具有公开访问的 MINA 代币市场的信誉良好的交易所，则为 Mina 代币最新私人融资轮的隐含美元价值。

## 筛选标准

选定的供应商应在满足本 RfP 中规定的需求和要求所需的领域拥有丰富的专业知识。特别是：

\- 应用密码学和密码系统的专业知识，特别是 STARK 和 SNARK
\- 底层优化代码的专业知识
\- EVM 的经验

## 投标说明

收到此请求后，有兴趣的供应商应确认收到并打算对参与进行投标。

在此确认中，他们应解释为了开始工作，他们需要我们提供什么。以及提请注意他们认为自己没有丰富专业知识的领域。我们将使用此信息来尝试为参与提供适当的入门材料。

提案必须在 \*2021 年 3 月 31 日太平洋标准时间下午 5 点\* 之前提交。我们预计需要 1 周的时间来进行审议和回复。

请将初始确认函和提案（PDF 格式）发送至以下地址：rfp@ethereum.org

**请随时向我们发送你可能有的任何问题：rfp@ethereum.org**

>- 原文链接： [hackmd.io/u_2Ygx8XS5Ss1a...](https://hackmd.io/u_2Ygx8XS5Ss1aObgOFjkA)
>- 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～

在 EVM 上完全验证 Mina 区块链

介绍

[以太坊基金会](https://ethereum.foundation/) (EF) 和 [Mina 基金会](https://minaprotocol.com/) (MF) 宣布了一项提案征集 (RfP)，旨在设计和实现一种在以太坊上验证 Pickles SNARK 的机制。

此举的目标是 (1) 在以太坊上实现 Mina 区块链的完全验证，以实现两个链之间的互操作，以及 (2) 使应用程序更普遍地在以太坊上使用递归 SNARK。

定义

设

\begin{align*} p &= 2^{254} + 45560315531419706090280762371685220353 \\ q &= 2^{254} + 45560315531506369815346746415080538113 \\ \mathbb{G}_1 &= \left\{ (x, y) \in \mathbb{F}_p \mid y^2 = x^3 + 5 \right\} \\ \mathbb{G}_2 &= \left\{ (x, y) \in \mathbb{F}_q \mid y^2 = x^3 + 5 \right\} \\ n_1 = 17 \\ n_2 = 16 \end{align*}

注意 $|\mathbb{G}_1| = q$ 且 $|\mathbb{G}_2| = p$。

Mina 中使用的 Pickles SNARK 验证器有几个组成部分

从证明数据中计算多个哈希值。这涉及使用 Poseidon 哈希函数，在 $\mathbb{F}_p$ 和 $\mathbb{F}_q$ 上都进行 63 轮完整运算，其舍入常数和 MDS 矩阵在 [此处针对 $\mathbb{F}_p$]（https://github.com/o1-labs/marlin/blob/master/oracle/src/pasta/fp.rs）和 [此处针对 $\mathbb{F}_q$]（https://github.com/o1-labs/marlin/blob/master/oracle/src/pasta/fq.rs）中指定。这一步相当便宜，并且很可能以合理的 gas 成本在 EVM 上实现。
检查几个算术等式。同样，这一步相当便宜，可以直接在 EVM 上实现。
执行一次大小为 $2 n_2 + 4 + (2 + 25) = 63$ 的多标量乘法 (MSM)，其中一些基是固定的，而另一些是可变的。这一步很可能可以直接在 EVM 上以合理的效率实现，尽管它可能比步骤 1 和 2 更昂贵。
对于每个 $i$，在 $\mathbb{G}_i$ 上执行一次大小为 $2^{n_i}$ 的多标量乘法，使用一个固定的基数组，以及可以从证明中非常有效地计算出的标量。

参考实现

Pickles 验证器的 Rust 实现可以在 [此处](https://github.com/o1-labs/marlin/blob/master/dlog/plonk/src/verifier.rs#L207) 找到。它调用一个过程来验证底层的多项式承诺打开，其代码位于 [此处](https://github.com/o1-labs/marlin/blob/master/dlog/commitment/src/commitment.rs#L612)。

扩展讨论

如上所述，验证器中最昂贵的部分，以及可能必须在 EVM 之外的辅助证明系统中验证的部分，是两个 MSM。在本节中，我们将更详细地描述这些 MSM。设 $\mathbb{G}_k$ 是上面定义的两个曲线之一，设 $\mathbb{F}$ 是它的标量域。设 $\phi \colon \{ 0, 1 \}^{128} \to \mathbb{F}$ 是由 `to_field` 定义的算法 [此处](https://github.com/o1-labs/marlin/blob/49f81edc9c86e5907d26ea791fa083640ad0ef3e/oracle/src/sponge.rs#L33)。

给定一个整数 $i < 2^{n_k}$，定义 $\mathsf{bits}(i)$ 为长度为 $n$ 的小端位数组，表示 $i$ 的二进制展开。

从给定的 Pickles SNARK 中，将导出一个挑战序列 $c_0, \dots, c_{n_k - 1} \in \{ 0, 1 \}^{128}$。相关的 MSM 是

$$ \sum_{i = 0}^{2^{n_k} - 1} s_i G_i = H $$ 其中 $$ s_i := \prod_{\substack{0 \leq j < n_k \\ \mathsf{bits}(i)[j] = 1}} \phi(c_j) $$ 其中 $G_0, \dots, G_{2^{n_k} - 1} \in \mathbb{G}$ 是由 [此算法](https://github.com/o1-labs/marlin/blob/master/dlog/commitment/src/srs.rs#L70) 生成的固定群元素序列。

观察

标量序列 $\left\{ s_i \right\}_{0 \leq i < 2^{n - 1}}$ 可以以这样一种方式重新排序，即每个项都可以通过前一个项最多通过一次乘法和一次除法获得。如果也相应地重新排序基的固定序列 $\left\{ {G}_i \right\}_{0 \leq i < 2^{n - 1}}$，这使得 MSM $\sum_i s_i {G}_i$ 非常适合用于使用基于 AIR 的 STARK 进行验证，因为计算可以表示为一个循环，其中每次迭代都可以非常有效地表示为算术计算（模固定查找表中的查找）。

代码版本

将作为规范的代码的 github commit 将在项目开始时确定。该代码在 https://github.com/o1-labs/marlin 和 https://github.com/minaprotocol/mina/ 上公开开发。

流程总结

整个流程可以总结如下：

请求： 发布 RfP（此帖子）
收集： 供应商提交提案
审议： EF 和 MF 决定接受哪个提案，并根据接受提案的资源和需求制定计划。
提议： EF 和 MF 向供应商提议该计划，并根据供应商的反馈进行调整
开始： 供应商接受并开始工作

参与时间表

拟议的参与时间表约为 6 个月。

EF 和 MF 的成员将随时解答规划和实施过程中的问题和评论，以便尽可能方便供应商。

交付成果

交付成果将采用以下形式

- 一个程序 `aux-proof-gen`，它将 Mina 区块链状态和关联的 Pickles SNARK 作为输入，并生成一个辅助证明。必须能够在具有最多 16 个核心和 32 GB 内存的云实例上在 15 分钟内运行此程序。 - 一个以太坊智能合约 `aux-proof-verify`，它具有与 Mina 区块链状态相对应的内部状态，并且只有在提供验证的辅助证明时才能设置为新状态。该合约应最多使用 5M gas。 - 对于给定的 Mina 区块链状态 $s$，如果且仅当拥有与状态 $s$ 关联的 Pickles SNARK，才可以使用 `aux-proof-gen` 生成一个辅助证明，该证明在具有状态 $s$ 的 `aux-proof-verify` 上验证。 - 已实现的辅助证明系统的高级描述。 - 两篇博客文章，描述工作的进展情况；一篇在参与过程中进行到一半时发布，另一篇在结束时发布。 - 在此 RfP 下交付的所有代码将根据 Apache License, Version 2.0 发布。

费用结构

发票

根据本 RfP 的时间表，选定的供应商预计将提交 2 份发票：

- 在参与开始时，第一份发票为参与总费用的 50% - 在交付所有交付成果（包括代码和最终博客文章）以及 5 天审核期后，第二份发票为参与总费用的 50%。

付款方式

供应商可以选择以法定货币（通过银行转账）、ETH 或 MINA 支付。

如果供应商选择以 MINA 支付，则协议下描述的 MINA 的价值将是： - 如果存在具有公开访问的 MINA 代币市场的信誉良好的交易所，则为到期日前一天（美国东部时间下午 4 点）纽约证券交易所收盘时（如 https://www.coingecko.com 所述）的美元价值； - 或者，如果不存在具有公开访问的 MINA 代币市场的信誉良好的交易所，则为 Mina 代币最新私人融资轮的隐含美元价值。

筛选标准

选定的供应商应在满足本 RfP 中规定的需求和要求所需的领域拥有丰富的专业知识。特别是：

- 应用密码学和密码系统的专业知识，特别是 STARK 和 SNARK - 底层优化代码的专业知识 - EVM 的经验

投标说明