Kimchi：Mina 证明系统的最新更新

我们最近发布了 Mina 证明系统的更新，名为 Kimchi。在这篇文章中，我们将介绍 Kimchi 是什么以及它的不同之处。

简介

作者：David Wong，o1Labs 加密工程师，Mina 协议贡献者

我们最近发布了 Mina 证明系统的更新，名为 Kimchi。 Kimchi 是我们用来生成递归证明的主要机制，它允许 Mina 区块链保持约 22KB 的固定大小。它还将很快通过我们的 zkApps 更新实现隐私和智能合约的本地执行。在这篇文章中，我们将介绍 Kimchi 是什么以及它的不同之处。

首先，很高兴看到我们在堆栈中的位置。观察网络的边缘，我们可以看到一个大黑匣子：Mina。

如果你足够好奇，你可以打开它看看里面有什么。在某些时候，你最终会得到 Kimchi 。 Pickles 是递归层，它是我们用来创建……的证明的证明的协议，并将区块链减少到 22KB 以下的固定大小。

不过 Kimchi 需要一些东西来创建证明，这就是 Kimchi ：

在这篇文章中，我们将尝试创建一些抽象和简化来教授关于 Kimchi 是什么的直觉。我们将尽力将解释保持在相对较高的水平，因此将由您来打开我们将摆在您面前的黑匣子。

例如，这些黑盒子之一就是意大利面曲线。

这里显然有一个主题。剩下的就是把米娜的名字改成另一种腌制调味品了。

一些背景 

Kimchi 基于 PLONK，这是 Ariel Gabizon、Zachary J. Williamson 和 Oana Ciobotaru 于 2019 年发布的证明系统。 从那时起，许多改进和扩展被提出。有 fflonk、turbo PLONK、ultra PLONK、plonkup 以及最近的 plonky2。这很难理解，但本质上所有这些协议都实现了 PLONK 的变体。因此，我们称它们为笨拙的协议。 Kimchi 就是这样一个笨拙的协议。

如今，PLONK 被认为是最雄心勃勃的通用零知识证明结构之一。 许多项目，如 Zcash、Polygon Zero（以前称为 Mir Protocol）、Aztec 网络、Dusk、MatterLabs（zksync）、Astar 和 anoma，都有自己的证明系统实现。

但首先，什么是证明系统？

让我们看一个场景，该场景应该可以阐明构造的界面。如果您理解本节，那么您就成功了一半，因为您将能够自己思考如何使用通用零知识证明，而不必弄清楚其中发生了什么。

假设爱丽丝有一个数独谜题。她将其发送给鲍勃，鲍勃找到了谜题的解决方案。为了向她证明这一点，他向她发送了解决方案。

然后，Alice 可以使用数独在程序中运行该解决方案，如果解决方案正确，该程序将返回 true。

问题是鲍勃并不想分享他的解决方案......因此，他自己在笔记本电脑上运行该程序，并告诉爱丽丝“我知道一个解决方案，相信我，我刚刚运行了 在我的笔记本电脑上运行程序，它返回true”。

显然，爱丽丝没有理由相信鲍勃。我们有点进退两难。这就是像 PLONK 这样的协议可以发挥作用的地方。第一步是以特殊格式获取我们的 verify solution 程序（我稍后会讨论）并将其编译为两个不同的数据块：

• 证明者索引（有时称为证明者密钥，尽管它不是真正的密钥）
• 验证者索引（有时称为验证者密钥，也不是密钥）

然后证明者 (Bob) 可以使用带有证明者索引、数独谜题及其解决方案的算法来执行程序并生成正确执行的证明（程序返回的证明< b1> 在本例中）。

我们将数独称为公共输入，因为其他人（例如爱丽丝）都知道它，而将解决方案称为私人输入，因为鲍勃希望它保持秘密。

注意：这里我们并不真正关心输出（我们只是希望程序正确运行完成，这相当于返回 true ）。但有时，我们确实关心是否有一个公共输出（也许是 Alice 可以使用的执行结果）。在这些情况下，公共输出是公共输入的一部分。 （这个细节在实践中并不重要。）

现在，Bob 可以简单地将证明提供给 Alice，而 Alice 可以使用另一种名为 verify 的算法来验证它。如果verify函数返回true，她就知道Bob正确地运行了程序verify solution来完成（使用她的数独谜题和他的解决方案）。

以数独为例，零知识证明如何工作。

zkApps 怎么样？ 

在 Mina 中，zkApps（零知识智能合约）可以使用 snarkyjs 库以打字稿编写，然后使用 snarky 编译为某种中间表示。然后可以使用 Kimchi 编译器将程序编译为证明者和验证者索引，双方都可以使用 Kimchi 提供的功能来生成证明并验证它们。

验证者索引上传到链上，这允许任何人验证交易中包含的证明，声称他们正确执行了 zkApp。

算术电路 

现在让我们解决房间里的大象：密码学是关于数学和数字的，但像我们的数独解决方案验证器这样的程序是关于指令和位的。那是行不通的。我们能做些什么呢？解决方案是使用算术电路！

算术电路是由算术门组成的电路：

我认为，通过加法门（将两个数字相加）和乘法门（将两个数字相乘），我们可以重写大多数程序。

让我们看一个简单的例子。假设我想在计算中使用一点x。为此，我首先需要确保 x 确实是一个位（0 或 1）。

看一下下面的等式：x(x-1) = 0。仅当 x 为 0 或 1 时，这才应该成立。我们称之为约束（我们将 x 限制为某些值）。为我们的证明系统编写电路就是编写这样的约束。事实上其中有很多。

让我们看看它如何与我们的算术门一起工作。

首先，我们将 1 添加到 -x （稍后我将解释如何从 x 获取 -x）。然后我们使用乘法门和输出：

乘法门的输出必须为 0（这是我们要写的约束）。

就是这样，我们的电路现在只有两个门。在 PLONK 中，您可以将其写为作用于寄存器的门列表（两个输入 L 和 R 以及输出 O ）：

现在，我们实际上并没有对 L 和 R 进行加法，而是在 -R 中加 1。我们该怎么做？也许我们可以有一个“常量加法”门和一个“减法门”？相反，我们“调整”我们的加法门：

现在让我们将乘法门添加到列表中。但请记住，输出寄存器未被使用，因为它必须为 0。因此我们也调整该门：

稍后将详细介绍如何调整这些门。

我们还缺少最后一件事：第一个门的输出寄存器是第二个门的左侧寄存器。我们可以简单地连接两个寄存器来编码这种对应关系：

这就是我们在 PLONK 中表示电路的方式！我们只是列出所有门（及其参数）以及它们所作用的寄存器之间的接线。

现在，当证明者想要生成证明时，他们将运行该程序并将每个寄存器的值记录在执行跟踪中。例如，下面是一个采用 x = 0 的例子。

注意：第一个门的左侧寄存器和第二个门的输出寄存器中的值可以是任何值，因为它们不被门使用。

我所做的一个简化是，我们不知道 x 从这里来。在实际电路中，此执行跟踪的正确寄存器连接到另一个包含值 x 的寄存器（或者它可能作为电路的私有或公共输入给出，但我将避免解释其工作原理这里）。

我所做的另一个简化是，实际上加法和乘法门是作为单个可调整门实现的，我们在 Kimchi 中称之为通用门：

调整通用门的参数本质上是将其变成不同的门（加法、乘法、常数加法、减法等）

从 PLONK 到 Kimchi

Kimchi 是在 PLONK 基础上进行的改进、优化和更改的集合。例如，它通过在协议内部使用防弹式多项式承诺来克服 PLONK 的可信设置限制。这样，就不需要相信可信设置的参与者是诚实的（如果他们不诚实，他们可能会破坏协议）。说到电路，既然我们在这里讨论电路，Kimchi 在 PLONK 已有的 3 个寄存器上添加了 12 个寄存器：

这些寄存器分为两种类型的寄存器：IO 寄存器，可以相互连接，以及只能由相关门使用的临时寄存器（有时称为建议线）。 更多寄存器意味着我们现在可以拥有接受多个输入而不是仅一个输入的门：

这开启了新的可能性。例如，标量乘法门将需要至少三个输入（一个标量和两个曲线点坐标）。由于某些操作比其他操作发生得更频繁，因此可以更有效地将它们重写为新门。在撰写本文时，Kimchi 提供 9 个新门：

Kimchi 中的另一个概念是一个门可以直接将其输出写入下一个门使用的寄存器。这对于像“poseidon”这样的门很有用，它需要连续使用几次（具体来说是 11 次）来表示poseidon 哈希函数：

Kimchi 中实现的另一个性能改进是查找。有时，一些操作可以写成表格。例如，异或表：

4 位值的 XOR 表的大小为 28 。使用通用门实现这一点将是困难和冗长的，因此 Kimchi 构建表并允许门（到目前为止只有 Chacha 使用它）简单地对表执行查找以获取操作结果。

Kimchi 还有更多内容，但这是另一次了。您可以查看 Kimchi 实现，如果您好奇打开其他黑盒，您可以查看我们的深入解释。

总结一下 

Pickles 现在使用升级的证明系统：Kimchi。 Kimchi 为电路制造商带来了多项优化和生活质量改进。这应该允许更快的证明器、更大的电路以及可能更短的证明尺寸！

关于 Mina 协议 

Mina 是世界上最轻的区块链，由参与者提供支持。 Mina 没有使用强力计算力，而是使用先进的密码学和递归 zk-SNARK 来设计整个区块链，大小约为 22kb，相当于几条推文的大小。它是第一个能够实现零知识智能合约（zkApps）的高效实施和轻松编程的第一层。凭借其独特的隐私功能和连接到任何网站的能力，Mina 正在现实世界和加密货币之间建立一个私人网关，以及我们所有人都应得的安全、民主的未来。