TL; DR：zkMIPS 通过五个步骤证明了 MIPS 程序的正确执行：它（1）将程序分成几个段，（2）将每个段的指令分成四个模块表，（3）独立证明来自每个模块表的指令，（4）证明每个段的指令包含在其一个表中，以及（5）递归地证明段序列与程序执行相匹配。第 3 步以 STARK 形式编写，步骤 4 是以 STARK 编写的 LogUp 证明，步骤 5 以 PLONK 证明的形式编写。所有证明步骤均使用 Plonky2 库实现。或者，可以生成最终的 Groth16 证明来验证程序在链上的执行。
零知识（ZK）证明的概念在区块链中越来越受到重视，因为它们能够对关键属性进行透明和可验证的验证，例如证明储备或验证新的汇总状态。在过去的几年中，ZK证明的两个具体案例变得特别流行：zkVM（ZK虚拟机）和zkEVM（ZK以太坊虚拟机）。这些概念非常相似，因为它们都验证了程序的正确执行；它们之间的主要区别在于该程序是要在（zkEVM）上还是链下（zkVM）上运行，即它是否使用智能合约语言编写。
ZKM开发了一种名为zkMips的zkVM，它能够在链上验证MIPS程序是否在链下正确执行。由于大多数链下和链上编程语言都可以轻松编译为 MIPS，因此 zkMIPS 支持多种程序，包括验证区块链交易、智能合约函数调用和汇总正确性的程序。
这篇文章解释了所有这些在技术上意味着什么，以及实现该系统所需的步骤。为此，我们必须回过头来解释如何在 ZK 证明中解释程序及其执行。
对于 任何 计算问题有一种验证算法可以检查给定解决方案是否有效。ZK 将模型验证算法证明为安全的多方协议，以保证：
这三个属性由两种相关的算法实现，即prover和verifier（不要与验证混淆——验证算法验证解决方案，验证器算法验证证据）。我们需要证明者 要知道 目标问题的解决方案，而验证者不是（尽管证明者和验证者是算法，但我们也可以使用这些术语来指代运行它们的各方）。换句话说，如果证明者是诚实的，他们将帮助验证者检查解决方案的有效性。根据这个术语，只有当证明者诚实（完整性）时，ZK证明才有望成功，只有在作弊（正确性）时才会失败。
如今，ZK 证明最终是为了使验证器算法比验证算法更快地运行。尽管此属性通常被称为零知识，但从技术上讲确实如此 叫 简洁。提高简洁性的一种方法是将验证复杂性从验证器转移到证明者，这意味着要有一个复杂的证明器和一个简单的验证器。
zkMips 由用于执行 MIPS 程序的复杂验证器、简单的验证器算法和等效的验证器智能合约组成。这里的计算问题是验证某些 MIPS 程序执行的正确性。解决方案，即正确性证明，是代表程序执行的整体 CPU 状态顺序。天真的验证算法是简单地重新运行程序，但是这种方法并不简洁，因为状态序列对于智能合约来说太大了。
使用最先进的简洁证明，可以更快、更便宜地完成对MIPS程序执行的验证。快得多、便宜多少取决于不断发展的复杂技术。直到最近，这些技术主要依赖于多项式和概率属性：多项式属性涉及高级数学和基本（有时是高级）加密；而概率属性涉及基本的数学和哈希函数。
其基本思想是将验证算法的步骤以及这些步骤中涉及的值编码为多项式。我们称多项式编码验证步骤为 “约束多项式”，将其中涉及的多项式编码值称为 “见证多项式”。如果约束和见证多项式定义得当，我们可以通过周到的多项式组合将整个算法执行表示为单个多项式。
在此步骤结束时，通过对组合多项式进行某些多项式评估来验证解（这就是概率的用武之地）。定义要执行哪些评估的最常用方法之一是 FRI 协议，该协议用于验证组合多项式的度数是否正确。如果正在评估的多项式构图正确，则足以验证见证多项式和约束多项式是否匹配。
尽管 FRI 协议是 zkMips 证明的核心，但它还不够简洁，无法进行链上验证。原因之一是多项式表示形式通常与多项式次数一样大，对于 FRI 的多项式输入，多项式次数与 MIPS 程序一样大。为了提高 FRI 的简洁性，我们要做的第一件事是将程序分成几个段，使用 FRI 协议并行证明每个片段，然后递归地合并后续段的证明。我们称此方法为延续，因为每个新证明都表明其第一个输入段由第二个输入段延续，即第二个输入证明的初始状态与第一个输入证明的最终状态相匹配。
为了优化验证时间，我们将分段数设置为 2 的次方，并使所有分段的大小相同（大小等于 2 的分段对于 FRI 最佳，因此我们也考虑到了这一点）。最终的延续证明大致相当于一个段落证明的大小，但证明了整个程序的正确执行，从而保证了对数简洁因子。
另一种简洁的 zkMIPS 验证技术是查找。由于某些运算不容易表示为多项式（例如逻辑运算），因此一些项目会为其创建固定的评估表，并需要 查找 每当这些操作出现时，就会进入这些表中。这里的诀窍是将这些表的条目编码为多项式，并将这些表作为另一种类型的多项式进行查找，从而允许像协议的其余部分一样进行构图。这个解决方案在实践中是有效的，因为查询的表格是固定的，任何人都可以检查。
去年，Jolt and Lasso（J&L）提议查找 所有 操作。这个想法似乎需要巨大的表来实现某些运算（例如 32 位算术运算）的所有可能的输入和输出组合。但是，J&L 并没有真正创建这些表，他们只是使用奇特的多项式技术对其进行模拟。zkMIPS 使用查找的方式与 J&L 类似：它将运算分为四组（算术、逻辑、内存和控制），单独证明每组运算（使用 FRI），并使用查找来显示原始内部 CPU 状态集中的每个条目都出现在其中一个组的表中操作组。
为了创建约束条件和见证多项式，将它们组合成将进行FRI测试的多项式，并编写延续和查找证明，我们使用了众所周知的 Plonky2 图书馆。该库是一个最先进的框架，用于设计两种类型的 ZK 证明，即 STARK 和 PLONK 证明。出于技术原因，我们选择在 FRI 和查找阶段使用 STARK 范例，在延续阶段使用 PLONK 范例。Plonky2 库中两种范式的实现都使用 FRI 协议，这使得它们的证明非常相似，并保证了它们可以通过相同的算法进行验证。
此属性允许我们将一个额外的证明层合并到 zkMIPS 架构中，从而使最终证明更易于在第 1 层上进行验证。我们选择了广泛使用的 Groth16 证明范例作为最后一层，因为它使用双线性函数，而不是以太坊 EVM 中原生实现的椭圆曲线。由于将转换为这种 EVM 友好格式的证明是延续性证明，实际上是 FRI 证明，因此我们需要为 FRI 验证算法编写 Groth16 证明。
关于zkMips架构的最后一个细节是经过验证的优化，它利用了FRI协议的特殊功能。该协议使用多项式承诺（我不会在此介绍的高级密码学主题）来评估其每次迭代中的某些属性。Plonky2在STARK和PLONK实现中采用的多项式承诺方案的最独特特性之一是其大小可变。
这些承诺的大小与证明者计算承诺所需的时间成反比。为了缩短验证时间，我们选择在基于 Plonky2 的每个验证阶段都进行快速和大额的承诺，但最后一个阶段除外，我们选择使用缓慢和小额承诺来提高证明规模。这保证了尽可能缩短证明时间，并且最终证明将大大小于中间证据。由此产生的验证架构如下所示。
在本博客系列的下一部分中，我将把我们的 zkVM 解决方案与其他公司的解决方案进行比较。
卢卡斯·弗拉加是ZKM Research的高级研究员。
TL; DR：zkMIPS 通过五个步骤证明了 MIPS 程序的正确执行：它（1）将程序分成几个段，（2）将每个段的指令分成四个模块表，（3）独立证明来自每个模块表的指令，（4）证明每个段的指令包含在其一个表中，以及（5）递归地证明段序列与程序执行相匹配。第 3 步以 STARK 形式编写，步骤 4 是以 STARK 编写的 LogUp 证明，步骤 5 以 PLONK 证明的形式编写。所有证明步骤均使用 Plonky2 库实现。或者，可以生成最终的 Groth16 证明来验证程序在链上的执行。
零知识（ZK）证明的概念在区块链中越来越受到重视，因为它们能够对关键属性进行透明和可验证的验证，例如证明储备或验证新的汇总状态。在过去的几年中，ZK证明的两个具体案例变得特别流行：zkVM（ZK虚拟机）和zkEVM（ZK以太坊虚拟机）。这些概念非常相似，因为它们都验证了程序的正确执行；它们之间的主要区别在于该程序是要在（zkEVM）上还是链下（zkVM）上运行，即它是否使用智能合约语言编写。
ZKM开发了一种名为zkMips的zkVM，它能够在链上验证MIPS程序是否在链下正确执行。由于大多数链下和链上编程语言都可以轻松编译为 MIPS，因此 zkMIPS 支持多种程序，包括验证区块链交易、智能合约函数调用和汇总正确性的程序。
这篇文章解释了所有这些在技术上意味着什么，以及实现该系统所需的步骤。为此，我们必须回过头来解释如何在 ZK 证明中解释程序及其执行。
对于 任何 计算问题有一种验证算法可以检查给定解决方案是否有效。ZK 将模型验证算法证明为安全的多方协议，以保证：
这三个属性由两种相关的算法实现，即prover和verifier（不要与验证混淆——验证算法验证解决方案，验证器算法验证证据）。我们需要证明者 要知道 目标问题的解决方案，而验证者不是（尽管证明者和验证者是算法，但我们也可以使用这些术语来指代运行它们的各方）。换句话说，如果证明者是诚实的，他们将帮助验证者检查解决方案的有效性。根据这个术语，只有当证明者诚实（完整性）时，ZK证明才有望成功，只有在作弊（正确性）时才会失败。
如今，ZK 证明最终是为了使验证器算法比验证算法更快地运行。尽管此属性通常被称为零知识，但从技术上讲确实如此 叫 简洁。提高简洁性的一种方法是将验证复杂性从验证器转移到证明者，这意味着要有一个复杂的证明器和一个简单的验证器。
zkMips 由用于执行 MIPS 程序的复杂验证器、简单的验证器算法和等效的验证器智能合约组成。这里的计算问题是验证某些 MIPS 程序执行的正确性。解决方案，即正确性证明，是代表程序执行的整体 CPU 状态顺序。天真的验证算法是简单地重新运行程序，但是这种方法并不简洁，因为状态序列对于智能合约来说太大了。
使用最先进的简洁证明，可以更快、更便宜地完成对MIPS程序执行的验证。快得多、便宜多少取决于不断发展的复杂技术。直到最近，这些技术主要依赖于多项式和概率属性：多项式属性涉及高级数学和基本（有时是高级）加密；而概率属性涉及基本的数学和哈希函数。
其基本思想是将验证算法的步骤以及这些步骤中涉及的值编码为多项式。我们称多项式编码验证步骤为 “约束多项式”，将其中涉及的多项式编码值称为 “见证多项式”。如果约束和见证多项式定义得当，我们可以通过周到的多项式组合将整个算法执行表示为单个多项式。
在此步骤结束时，通过对组合多项式进行某些多项式评估来验证解（这就是概率的用武之地）。定义要执行哪些评估的最常用方法之一是 FRI 协议，该协议用于验证组合多项式的度数是否正确。如果正在评估的多项式构图正确，则足以验证见证多项式和约束多项式是否匹配。
尽管 FRI 协议是 zkMips 证明的核心，但它还不够简洁，无法进行链上验证。原因之一是多项式表示形式通常与多项式次数一样大，对于 FRI 的多项式输入，多项式次数与 MIPS 程序一样大。为了提高 FRI 的简洁性，我们要做的第一件事是将程序分成几个段，使用 FRI 协议并行证明每个片段，然后递归地合并后续段的证明。我们称此方法为延续，因为每个新证明都表明其第一个输入段由第二个输入段延续，即第二个输入证明的初始状态与第一个输入证明的最终状态相匹配。
为了优化验证时间，我们将分段数设置为 2 的次方，并使所有分段的大小相同（大小等于 2 的分段对于 FRI 最佳，因此我们也考虑到了这一点）。最终的延续证明大致相当于一个段落证明的大小，但证明了整个程序的正确执行，从而保证了对数简洁因子。
另一种简洁的 zkMIPS 验证技术是查找。由于某些运算不容易表示为多项式（例如逻辑运算），因此一些项目会为其创建固定的评估表，并需要 查找 每当这些操作出现时，就会进入这些表中。这里的诀窍是将这些表的条目编码为多项式，并将这些表作为另一种类型的多项式进行查找，从而允许像协议的其余部分一样进行构图。这个解决方案在实践中是有效的，因为查询的表格是固定的，任何人都可以检查。
去年，Jolt and Lasso（J&L）提议查找 所有 操作。这个想法似乎需要巨大的表来实现某些运算（例如 32 位算术运算）的所有可能的输入和输出组合。但是，J&L 并没有真正创建这些表，他们只是使用奇特的多项式技术对其进行模拟。zkMIPS 使用查找的方式与 J&L 类似：它将运算分为四组（算术、逻辑、内存和控制），单独证明每组运算（使用 FRI），并使用查找来显示原始内部 CPU 状态集中的每个条目都出现在其中一个组的表中操作组。
为了创建约束条件和见证多项式，将它们组合成将进行FRI测试的多项式，并编写延续和查找证明，我们使用了众所周知的 Plonky2 图书馆。该库是一个最先进的框架，用于设计两种类型的 ZK 证明，即 STARK 和 PLONK 证明。出于技术原因，我们选择在 FRI 和查找阶段使用 STARK 范例，在延续阶段使用 PLONK 范例。Plonky2 库中两种范式的实现都使用 FRI 协议，这使得它们的证明非常相似，并保证了它们可以通过相同的算法进行验证。
此属性允许我们将一个额外的证明层合并到 zkMIPS 架构中，从而使最终证明更易于在第 1 层上进行验证。我们选择了广泛使用的 Groth16 证明范例作为最后一层，因为它使用双线性函数，而不是以太坊 EVM 中原生实现的椭圆曲线。由于将转换为这种 EVM 友好格式的证明是延续性证明，实际上是 FRI 证明，因此我们需要为 FRI 验证算法编写 Groth16 证明。
关于zkMips架构的最后一个细节是经过验证的优化，它利用了FRI协议的特殊功能。该协议使用多项式承诺（我不会在此介绍的高级密码学主题）来评估其每次迭代中的某些属性。Plonky2在STARK和PLONK实现中采用的多项式承诺方案的最独特特性之一是其大小可变。
这些承诺的大小与证明者计算承诺所需的时间成反比。为了缩短验证时间，我们选择在基于 Plonky2 的每个验证阶段都进行快速和大额的承诺，但最后一个阶段除外，我们选择使用缓慢和小额承诺来提高证明规模。这保证了尽可能缩短证明时间，并且最终证明将大大小于中间证据。由此产生的验证架构如下所示。
在本博客系列的下一部分中，我将把我们的 zkVM 解决方案与其他公司的解决方案进行比较。
卢卡斯·弗拉加是ZKM Research的高级研究员。
