# Kimchi：Mina 最新版本的证明系统

By [minacash](https://paragraph.com/@minacash) · 2022-02-23

---

![](https://storage.googleapis.com/papyrus_images/52a559b2b3b72acb3e08af0864f1868684fee19a3abba74c410faca1aa21744a.png)

**作者：**[**David Wong**](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2)**,** [**O(1) Labs**](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2) **加密工程师，Mina 协议贡献者**

我们最近为 Mina 发布了名为 **Kimchi** 的最新证明系统。Kimchi 是我们用来生成递归证明的主要系统，它让 Mina 区块链保持在约为[22KB](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2) 的固定大小。Kimchi 很快将通过我们对 [Snapp](http://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247485607&idx=2&sn=e24f32b0fb9c07a341e71231d77e9893&chksm=c35a29bdf42da0aba6e4e58a21fa3f71d63b54a41036a1b16769b866e7a17028ff1a09f3023d&scene=21#wechat_redirect) 的更新实现智能合约的隐私功能和本地执行。在本文中，我们将介绍 Kimchi 是什么，以及它的独特之处。

首先，一起来看看我们在栈中的位置。查看网络边缘，我们可以看到一个黑盒子：Mina。

![](https://storage.googleapis.com/papyrus_images/c5e46d83c4ef1b5ae53386300487aa886f854d8bda2c46943c9eacef71518a68.jpg)

如果你很好奇，你可以打开它看看里面有什么。某些时候，你会在里面找到[pickles](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2)。Pickles 是递归层，它是我们用来创建证明的证明的证明……的证明的协议，并将区块链压缩到低于 22KB 的固定大小。

![](https://storage.googleapis.com/papyrus_images/581032c25d9cdfd2c92dd4833e76913ffad99cfba61e868fca4b636bf780fab6.jpg)

Pickles 需要一些东西来生成证明，这就是 Kimchi：

![](https://storage.googleapis.com/papyrus_images/6a3c873601b078752df4192568c03af626f8293ea416305dfca816bafda2eb83.jpg)

在本文中，我们将尝试用一些抽象和简化的概念来告诉你什么是 Kimchi。我们将尽量相对比较精简地解释，从而帮助你打开我们摆在你面前的黑盒子。

例如，这些黑盒子的其中之一，[pasta 曲线](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2)。

![](https://storage.googleapis.com/papyrus_images/2cbbcca3c4a50a55307b3160be50ae2a6d33eea319fa6495dffefcb1ce68a6d3.jpg)

显而易见的主题。剩下要做的就是把 Mina 的名字改成另一种腌制品。

Mina SAUERKRAUT（酸菜）

![](https://storage.googleapis.com/papyrus_images/f800e4413876a3944e70f1d59e391f89cce2b0dbe5f7ce75902a8fe89c485208.jpg)

**一些背景介绍**

Kimchi 基于 PLONK 系统，这是一个由 Ariel Gabizon、Zachary J. Williamson 和 Oana Ciobotaru 于[2019 年发布](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2)的证明系统。从那时起，有许多改进和扩展不断被提出。比如有 fflonk、turbo PLONK、ultra PLONK、plonkup 以及最近的 plonky2。在这里很难一一介绍，但基本上所有这些协议都是 PLONK 的变体。因此，我们称它们为 plonkish 协议。Kimchi 就是这样一个 plonkish 协议。

今天，PLONK 被认为是最具野心的通用零知识证明结构之一。Zcash、Polygon Zero（前称 Mir 协议）、Aztec Network、Dusk、MatterLabs (zksync)、Astar 和 anoma 等许多项目都是基于 PLONK 协议实现了各自的证明系统。

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

本节构造了一个零知识证明的场景。如果你理解了本节的场景，那么你就成功了一半，这是由于你将能够自己思考如何使用通用零知识证明，而无需弄清楚其中发生了什么。

我们假设 Alice 在玩数独游戏。Alice 将它发给了 Bob，Bob 找到了这个谜题的解。Bob 为了向 Alice 证明这一点，需要他将解发送给 Alice。

![](https://storage.googleapis.com/papyrus_images/06e5217420ed5c363888b65ccd827357012dca7a99cecde031a989936b9c75ef.jpg)

Alice 可以通过运行程序验证数独的解，如果解正确，该程序将返回结果 true。

![](https://storage.googleapis.com/papyrus_images/bffbb9bdd2bd5a4d2600e4625ecf80252020d7a0da20406af4b12d22ce2053f5.jpg)

问题是，Bob 并不想分享他的解……因此，他自己在笔记本电脑上运行程序，并告诉 Alice：“我知道一个解，相信我，我在笔记本电脑上运行了验证这个解的程序，它返回了 true 的结果”。

![](https://storage.googleapis.com/papyrus_images/4f1b51016749e0659e0df340c5484cfdbd66bc437e81e990e85431a4c217b705.jpg)

显然， Alice 没有理由相信 Bob。这里我们就会遇到麻烦。而这就是像 PLONK 这样的协议的用武之地。第一步是以一种特殊的方式获取我们验证解的程序（稍后会对此进行解释）并将其编译为两个不同的数据块：

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

证明者（Bob）可以使用证明者索引的证明算法、数独谜题以及问题的解来执行程序，并生成正确执行的证明（一个由程序返回 true 的证明）。

我们将数独称为公共输入/public input，因为它为其他人（如 Alice）所知，而将解称为秘密输入 / private input，因为 Bob 希望它是保密的。

![](https://storage.googleapis.com/papyrus_images/76652c54388ce3a3b13d8be2b49d215802c03db03c34f4046d16f4356be135d2.jpg)

备注：此处我们并不真正关注输出结果（我们只希望程序正确运行并完成，在这里即为返回 true 结果）。但有时，我们确实需要一个公共输出（比如执行的结果，可以为 Alice 所利用）。在这些情况下，公共输出是公共输入的一部分。（这个细节在演示中并不重要。）

现在，Bob 可以非常方便地将证明交给 Alice，Alice 可以使用另一种验证算法对其进行验证。如果验证函数返回结果为 true ，Alice 就知道 Bob 正确地运行了验证程序（使用 Alice 的数独谜题和 Bob 的解）。

![](https://storage.googleapis.com/papyrus_images/4f90d4de7aa8017774cedd9ffd5b12a0ff568ac1fd124ed6edac301d4a4a40cb.jpg)

**那么 Snapp 呢？**

在 Mina 中，可以使用 typescript 调用[snarkyjs](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2) 库来编写 Snapp（零知识智能合约），然后使用[snarky](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2) 编译成一种中间语言。Kimchi 编译器将程序编译为证明者索引和验证者索引，并且双方都可以使用 Kimchi 提供的功能来生成证明并进行验证。

验证者索引是上传到链上的，这使得任何人都可以核查交易中包含的证明，以此来验证他们正确地执行了一个 Snapp。

![](https://storage.googleapis.com/papyrus_images/9376d5623b96112090a74409a88416dd0efbbf0600d49c4e28ecd6dc02e8e335.jpg)

**算术电路**

现在让我们来谈谈房间里的大象：密码学是关于数学和数字的，但是像验证数独解这样的程序是关于指令和 bit 的。这是行不通的。 我们可以怎么做？ 解决方案是使用**算术电路 / arithmetic circuit**！

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

![](https://storage.googleapis.com/papyrus_images/4e9b9c88b139787729e43eb42bb94d5682aa7535c7d0fa39a9867b8fde453668.png)

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

![](https://storage.googleapis.com/papyrus_images/5b3fcb0129da0abdd7f2c76d2713e18c88b0ac74f4ef3f98da2cca0db3fdca97.jpg)

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

请看以下等式：x(x-1) = 0。只有当 x 是 0 或 1 时，该等式才成立。我们将该等式称之为约束（我们将 x 约束在某些值）。为我们的证明系统编写电路就是编写这样的约束。事实上，许多电路都是这样编写的。

让我们看看这个等式是如何通过算术门运作的。

首先我们在 -x 上加 1（稍后我会解释如何从 x 中得到 -x）。然后我们同时使用乘法门与输出：

![](https://storage.googleapis.com/papyrus_images/953631985ea9101dab60e560a0b734be856d53aec749559c07cbd85955acf8a6.jpg)

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

如图所示，我们的电路现在只有两个门。在 PLONK 中，你可以将其写成变现为计数器（两个输入：左输入和右输入 L 和 R，以及输出：O）的门列表：

![](https://storage.googleapis.com/papyrus_images/265affdbf06d1962ab60d1ffd63d935f7cef1f13c622f4a198282d3539a29138.png)

现在，我们实际上并没有在 L 和 R 做加法，而是在 -R 中加 1。如何做到这一点？也许我们可以设定一个“加常数”门和一个“减法门”。我们对加法门进行“调整”：

left register is not used：左计数器未使用 negate right register：右计数器取反

constant：常数

接着我们将乘法门添加到列表中。但请注意，输出计数器没有被使用，因为它必须为 0。所以我们也对乘法门进行了调整：

![](https://storage.googleapis.com/papyrus_images/fcd50dff893a0382d76bc66144560eeefad3bbbf700b3e126b4c3efb3b04dc70.jpg)

稍后将对门的调整进行详细介绍。

现在还剩最后一件事：第一个门的输出计数器是第二个门的左输入计数器。我们可以简单地连接两个计数器来编译这种对应关系：

![](https://storage.googleapis.com/papyrus_images/e1cc75306a618dae3e11e5b8bcc899b1a0eeac5b09e1f68867e81db9c9bc1c9c.jpg)

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

当证明者想要生成证明，他们将运行程序，并在**执行跟踪 / execution trace** 中记录每个计数器的值。例如，以下是当 x = 0 时的结果。

![](https://storage.googleapis.com/papyrus_images/c410da1a87a0068b86159706bd5ae3dc03b89eabf13a5e54edaa1fc79a2d6fd0.jpg)

备注：第一个门的左输入计数器，以及第二个门的输出计数器的中的值可以是任何值，因为它们不被门使用。

此处我做了一个简化，即我们不知道 x 来自哪里。在实际电路中，右输入计数器的执行跟踪会连接到另一个包含 x 值的计数器（它可能作为电路的秘密输入或公共输入给出，但我将不在这里进行详细解释）。

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

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

**从 PLONK 到 Kimchi**

Kimchi 是在 PLONK 之上进行的改进、优化调整的集合。例如，它通过在协议内部使用 bulletproof 类的多项式承诺来克服 PLONK 的可信设置限制。这样，就无需相信可信设置的参与者是诚实的（如果他们不诚实，他们可能会破坏协议）。说到电路，既然我们在这里谈论电路，Kimchi 在 PLONK 已经拥有的 3 个计数器中添加了 12 个计数器：

这些计数器分为两种类型：IO 计数器，可以相互连接；临时计数器（有时称为 advice wires）只能由相关门进行使用。

更多的计数器意味着我们现在可以拥有多个输入而不是只有一个输入的门：

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

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

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

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

Kimchi 还有很多特点，未来将有更多介绍。你可以在[此处](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2)查看实现，如果你想打开其他黑盒子，可以在[此处](https://mp.weixin.qq.com/s?__biz=Mzk0OTIzNzg3Nw==&mid=2247489522&idx=1&sn=c153b630078f3dcd364313836b534f8d&key=4af29f4fad9279b73e8b9d05a571ba7c136971dc6d1c55736e9a7f6d0c64041113e991e63acb320dc21ab7f074ab78b993a7f6d9a02f41e723a8c292a5ca500a665f2afb6849bb55e5876e7edfecbd46a532dbd131f63fec4f8f1bafb1177cdff9b7827d474e056d501ef8160c5cae331bb567f1143fd15d591c0afba591177b&ascene=1&uin=MTY5MjI5MzMyMA%3D%3D&devicetype=Windows+10+x64&version=6305002e&lang=zh_CN&exportkey=A1h2852YDoriMej%2B20dpQh4%3D&acctmode=0&pass_ticket=6gS%2F8W1iGaeX4x2cqonv4KVVgpud8tKs39aG375u0oCin%2FwMpaN%2Berqla8bB9pYN&wx_header=0&fontgear=2)查看我们的深入解释。

**总结**

Pickles 现在使用升级的证明系统：Kimchi。Kimchi 为电路构建者带来了多项优化和改进。它支持更快的验证、更庞大的电路和可能更短的证明尺寸！

---

*Originally published on [minacash](https://paragraph.com/@minacash/kimchi-mina)*