Mina到以太坊ZK桥

介绍

在过去的几个月里，我们一直在开发一个Mina 和以太坊之间的桥梁。Mina 是一个 layer-1 区块链，它使用零知识证明 (zk-SNARKs) 来将其大小保持在 22 kB。该桥梁有两个目的：

1. 允许无缝的跨链交易。
2. 允许应用程序利用 Mina 的零知识功能，并跨多个链扩展其功能。

由于 22，用户可以简单地在链下证明事情，并在以太坊上验证它们。

Mina 的核心是使用一种称为 Kimchi 的证明系统，它是 Plonk 的一个变体，具有许多优化，并使用内积参数 (IPA) 多项式承诺方案。它的关键优化是用于有限域加法和乘法、Keccak、Poseidon 和查找参数的自定义 gates。最重要的是，我们有 Pickles，它是 Mina 的归纳 SNARK 组合，能够以灵活的方式进行增量可验证计算。这种构造允许我们生成一个证明，证明从状态 $Sn$ 到状态 $S{n+1}$ 的转换的有效性，同时检查上一步的证明是否正确。虽然这有助于 Mina 实现其简洁性，但在以太坊中验证这些证明的成本非常高。

目前，基于配对的 SNARK（例如那些使用 KZG 的 SNARK）在以太坊中具有更便宜的验证成本，这使得这个选项很有吸引力。为了“包装” Mina 状态证明，我们可以生成一个 SNARK，以使用带有 KZG 承诺方案的 Kimchi 变体来验证使用 IPA 获得的 Mina 证明。为此，我们必须首先将 Kimchi-IPA 证明的所有验证逻辑表达为一个电路，然后使用这个电路、证明和其他公共输入，并使用 Kimchi-KZG 生成一个证明。说起来容易做起来难。首先，我们必须将所有验证操作表达为算术电路。好消息是，我们可以使用椭圆曲线 gates 和查找参数来表达即使是像 MSM 这样的复杂操作。坏消息是，这些等式是在以太坊的 BN-254 标量域上表达的，这与 Pasta 域不同。这意味着我们将不得不进行许多有限域操作，这使得 SNARK 的成本非常高。

这篇文章将提供桥梁、Kimchi 和 KZG 验证器的概述。有关某些主题的介绍，请参阅 Plonk、IPA 和 lookups。

桥梁

该桥梁有以下组件：

1. 后端服务定期包装 Mina 的状态证明，并将其发布到 EVM 链。
2. 用于 Mina 证明的“包装”模块，使其易于在 EVM 上验证。
3. 用于在 EVM 中验证包装后的 Mina 状态证明的 solidity 逻辑。
4. 用于智能合约的浏览器实用程序。
5. 一个 solidity 合约实用程序，智能合约开发者或用户可以在 EVM 链上执行该实用工具，以输入 Mina 状态查找证明，该证明将根据最新发布的 Mina 状态证明检查状态查找，以验证此 Mina 状态是否有效。

流程如下图所示。有关与架构相关的更多详细信息，请参阅桥梁的 readme。

SNARKs

如前所述，Mina 的证明系统是 Kimchi，它是 Plonk 的修改版本，使用 IPA 并在 Pallas 和 Vesta（缩短为 Pasta 曲线）的一对椭圆曲线上工作。IPA 和 Pasta 曲线可以轻松实现递归，但代价是证明比基于 KZG 的 SNARK 更长。在以太坊中验证和存储这些证明的成本很高，因此我们需要获得一种新型的证明，可以在以太坊中以较低的成本进行检查。让我们深入了解 Kimchi、Pickes 和 KZG 承诺。

Kimchi

这是 Plonk 的修改版本。有三种类型的参数：

• 自定义 gates。
• 排列。
• 查找。

这些参数被转换为几个多项式，这些多项式必须在某个集合上求值为零。幸运的是，我们可以通过执行随机线性组合来检查所有多项式是否在集合上求值为零。例如，假设 $p_1, p_2 \dots p_n$ 都在集合 $S = {1, 2, \dots, m}$ 上求值为零。我们可以让验证者采样 $\alpha$ 并获得

$$ p(x) = \alpha p_1(x) + \alpha^2 p_2(x) + \cdots + \alpha^n p_n(x) $$

它也应该求值为零。为了看到该多项式具有该属性，我们可以证明 $p(x)$ 可被 $S$ 上的消失多项式 $Z_S(x)$ 整除。另一种表述是存在一些多项式 $q(x)$ 使得 $p(x) = Z_S(x) q(x)$。此外，如果我们决定仅从一个非常大的集合中的一个随机点 $\zeta$ 处执行此检查，那么以很高的概率，我们有之前的等式对于所有集合都成立。

成分是电路规范（gates 和连接/布线）和执行跟踪。Kimchi 中的执行跟踪具有输入/输出寄存器 (7) 加上建议寄存器 (8)。该电路是预先知道的，表示给定的程序/计算。执行跟踪取决于程序的特定执行（例如，我们可以使用不同的输入运行相同的程序）。

下表描述了电路：

• Gates：通用、Poseidon、椭圆曲线加法、Endo 标量、Endo 标量乘法、标量乘法、范围检查、有限域加法、有限域乘法、旋转和 XOR。
• 系数。这些仅在 Poseidon 和通用 gates 中使用。
• 布线（也称为排列或 Sigmas)
• 查找表
• 查找选择器

pub struct CircuitGate<F: PrimeField> {
    /// gate 的类型
    pub typ: GateType,

    /// gate 布线（对于每个单元格，它连接到哪个单元格）
    pub wires: GateWires,

    /// 公共选择器多项式，可以用作 gates 中方便的系数
    #[serde_as(as = "Vec<o1_utils::serialization::SerdeAs>")]
    pub coeffs: Vec<F>,
}

Kimchi 包含三个主要算法：

1. 设置：获取电路并生成证明者和验证者索引。
2. 证明创建：获取电路和证明者索引并输出证明。
3. 证明验证：获取证明和验证者索引并检查证明。

证明者为了获得证明而执行的步骤在此处列出。验证遵循此处所示的步骤。

Pickles

Pickles 使用 Pasta 曲线来高效地传递增量可验证计算。Pasta 曲线也称为：

• Tick/Step (Vesta)，处理区块和交易的证明。
• Tock/Wrap (Pallas)，处理签名并执行递归验证。

Tock 用于证明 Tick 证明的验证并输出 Tick 证明。Tick 用于证明 Tock 证明的验证并输出 Tock 证明。

• Provetock(Verify(Tick))=Tickproof
• Provetick(Verify(Tock))=Tockproof

Tick 和 Tock 最多可以验证两种相反的证明。Pickles 包含两个组件：快速 (1 - 30 ms) 和慢速 (100 ms - 1 s) 验证器。给定一个证明 $\pi_1$，我们首先执行快速验证器，并且更新算法采用先前的证明状态 $S_0$ 和 $\pi_1$ 并生成下一个证明状态 $S_1$。如果我们有一个传入的 $\pi_2$，我们不会执行慢速验证器，而是开始一个新的累积阶段。我们在 $\pi_2$ 上运行快速验证器，并将证明状态从 $S_1$ 更新到 $S_2$。如果没有更多传入的证明，我们使用慢速验证器来检查最后一个状态证明 $S_n$。

KZG 验证器 solidity

solidity 中验证器的代码在这里。验证器可以分为两个大的部分：

• 部分验证。
• 最终验证。

第一个处理诸如评估和承诺的正确长度之类的检查，使用 Fiat-Shamir 重新生成随机挑战，并使用声明的评估来查看 gate 和排列约束是否有效。第二部分通过调用配对检查函数来检查承诺。在朴素的 KZG 验证中，我们必须为我们要检查的每个评估计算一个配对。但是，我们可以随机组合承诺和评估以仅执行一个配对检查。

KZG 评估证明验证背后的工作原理如下：我们有一个对多项式的承诺 $p(x)$，一个评估点 $\zeta$，一个声明的评估 $v = p(\zeta)$，以及评估证明 $\pi = cm(q)$，它是对商多项式 $q(x)$ 的承诺。如果评估正确，则 $p(x) - v$ 应该可以被 $x - \zeta$ 整除，即

$$ p(x) - v = (x - \zeta) q(x) $$

我们无法直接进行此检查，因为我们只能访问承诺，而不能访问整个多项式。我们有 $cm(p) = p(s)g_1$ 和 $cm(q) = q(s)g_1$，它们是椭圆曲线上的点。我们可以尝试仅在一个点 $s$ 处检查所有内容，并且如果两边都匹配，那么以极大的概率，多项式被正确评估。配对是一个函数 $e(x, y)$，具有两个属性：

1. 双线性：$e(x_1 + x_2, y_1 + y_2) = e(x_1, y_1) e(x_2, y_2) e(x_1, y_2) e(x_2, y_1)$
2. 非退化：如果 $e(x, y) = 1$，则 $x$ 或 $y$ 是无穷远点（椭圆曲线加法的 нейтральный элемент）。

从双线性性质可以得出

$$ e(p(s)g_1 - vg_1, g_2) = e(g_1, g_2)^{p(s) - v} $$

类似地，

$$ e(q(s)g_1, sg_2 - \zeta g_2) = e(g_1, g_2)^{q(s)(s - \zeta)} $$

由于 $g_1$ 和 $g_2$ 都不是无穷远点（因为它们是整个群的生成器），因此 $e(g_1, g_2) \neq 1$，因此，如果两个配对都相等，则可以得出结论

$$ p(s) - v = q(s)(s - \zeta) $$

EVM 有一个函数，配对检查，它计算两个配对的乘积并验证它是否等于 1。由于此条件，我们重写第二个配对，对商的承诺取反，

$$ e(-q(s)g_1, sg_2 - \zeta g_2) = e(g_1, g_2)^{-q(s)(s - \zeta)} $$

在点 $\zeta$ 处批量评估多个多项式

如果我们有几个多项式 $p_1, p_2, \dots p_n$，并且我们想检查在同一点 $\zeta$ 处的评估，我们只需要对每个元素执行随机线性组合：

• 对 $p_k$ 的承诺：$cm(p) = \sum \alpha^k cm(p_k)$
• 对商 $q_k$ 的承诺：$cm(q) = \sum \alpha^k cm(q_k)$
• 评估：$v = \sum \alpha^k v_k$

在一个多项式的多个点 $\zeta_k$ 处批量评估

如果我们需要检查一个多项式在 $\zeta_1$ 处的值为 $v_1$，在 $\zeta_2$ 处的值为 $v_2$，... 在 $\zeta_n$ 处的值为 $v_n$，我们可以将所有这些检查合并为一个。步骤如下：

• 计算 n-1 次多项式 $I(x)$，该多项式内插点 $(\zeta_k, v_k)$. 这意味着对于 $k = 1, 2, \dots n$，有 $I(\zeta_k) = v_k$。如果我们只有两个点，则 $I(x) = (v_2 - v_1)(\zeta_2 - \zeta_1)^{-1}(x - \zeta_1) + v_1$，这是通过这两个点的直线。
• 多项式 $p(x) - I(x)$ 在 $\zeta_k$ 处的值为 $0$，这意味着 $p(x) - I(x)$ 可被多项式 $D(x) = \prod (x - \zeta_k)$ 整除（在我们的二维情况下，这是 $(x - \zeta_1)(x - \zeta_2)$）。计算 $p(x) - I(x)$ 除以 $D(x)$ 的商 $q(x)$ 并对其进行承诺。

我们可以将此想法与多个多项式的批量验证相结合，并且只需支付一次配对检查的费用！

结论

这篇文章介绍了简洁区块链 Mina 和以太坊之间的桥梁，允许无缝的跨链交易和 dApps 利用 Mina 的 zk 功能。主要挑战之一与以太坊中 Mina 证明的验证有关，因为它们依赖于 IPA，它比基于 KZG 的证明更昂贵。为了解决这个问题，我们必须创建一个包装器（一个证明 Mina 证明验证的程序）以获得可以在以太坊中以更具成本效益的方式验证的新证明。我们介绍了 Kimchi（Mina 的证明系统）和 Pickles（Mina 可以提供增量可验证计算的关键组件，这是简洁性的关键组件）的基础知识以及 KZG 承诺如何工作。我们还讨论了一些与有限域操作相关的挑战。在接下来的文章中，我们将更深入地讨论桥梁的一些组件以及项目的里程碑和进展。

• 原文链接： blog.lambdaclass.com/min...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～