密码学基础：算术电路

这是一系列关于加密技术的文章中的一部分。如果这是你遇到的第一篇文章，我强烈建议你从系列的开始阅读。

上次，我们深入探讨了一个 零知识证明 协议的特定示例。尽管优化和性能问题不谈，它涵盖了所需的用例：证明一个数字在 某个范围 内。然而，该协议是 极其具体 的，为了另一个声明而制作另一种协议需要专门的研究，可能会导致一整个不同的步骤序列。

我们总结时提到，零知识证明 的 通用框架 可能是一个有趣的追求目标。

而我们将会到达那个目标——只是现在还不是时候！

今天的计划是展示一些 基础，我们将在下篇文章中 立即 以此为基础进行构建。

既然我们在上次讨论中提到了 比特，那么我们就稍微绕一下，简要复习一下它们的用途。可以吗？

二进制电路

如果你正在阅读这篇文章，很可能你对计算机至少是 有点 兴趣，所以我们来谈谈这个话题。

比特作为计算机科学中的数据表示基本单位的事实，与计算机的工作原理密切相关。简单地说，流过电路的 电流 可以被视为 一 (1)，而在同一电路中 没有电流 流动的状态可能表示为 零 (0)。确实，这些电流就是 比特 在物理世界中的表现方式。

但是，如果我们不能对这些数据执行某些 操作，计算机就不会如此酷炫。

我们可以做的第一件事情就是以各种方式 组合 两个比特（记住，它们只是 电信号）。例如，我们可以创建一个 盒子，只有在两个信号输入也都是 1 时才输出 1，否则输出 0：

AND 门的运作

这些类型的盒子称为 逻辑门，它们使计算机能够进行魔法。其他 简单 门的存在，例如 NOT、OR、XOR、NAND、NOR 和 XNOR——它们都是电路的巧妙排列。

一个 AND 门的实际电路大致看起来是这样的

两个信号仍然太少——我们可以做得更好。所以，我们可以通过排列一些门来处理多个输入，在这个过程中获得一系列输出。门的排列方式称为 电路，它本质上是一个 计算模型。

例如，我们可以用这个相对简单的电路来加两个 两比特数字 A =(a ₀, a₁) 和 B =(b ₀, b₁)：

结果可能是 3 比特长——这对应于第三个输出，溢出

可以通过使用多个门和处理多个输入来创建各种用途的电路。

改变视角

让我们通过另一种视角来看待这些二进制电路。比特 只是一个属于集合 {0,1} 的数字。这个集合也双重成为一个 有限域：加法、乘法、减法和除法（除了 0 以外的一切）都被定义。我们使用 模 运算来保持在范围内——例如， 1 + 1 mod 2 = 0。

在这个意义上，我们可以将门视为对该有限域上进行的 数学运算。XOR 门正确地表示 模 2 加法，而 AND 门表示 模 2 乘法：

好吧，酷……接下来呢？

假设我们将输入标记为 x 和 y。我们再加一个 1 作为输入，以作补充。如果我们设置一些门，会发生什么？

输出是什么？是……一个 多项式？不错！

基本上，我们可以用一堆加法和乘法门来表示一个 二进制多项式。事实上，这就是对 如何计算 多项式本身的逐步说明。

我们已经知道，多项式在加密学中有很多应用。那么这里有一个想法：为什么要限制我们在 模 2 的范围内？有什么阻止我们将这个 计算食谱 扩展到任何任意有限域？

超级大脑启动

算术电路

对于具有 q 个元素的有限域（例如，模 q 的整数），我们可以使用同类型的电路来规定 多项式计算。与前面的电路唯一不同的是，所有操作都在 模 q 下进行，而不是 模 2，但仅此而已！

如果我没搞错（欢迎验证！），这应该得到多项式 x⁴y² + 3x³y² + x³y + 2x²y² + 4x²y + 4xy。

正式来说，这被称为 算术电路。它只是一个 图，将输入映射到节点（称为 门），这些节点表示 二元操作（这里的二元是指每个门接受两个输入）。

在它们的最简单版本中，使用的唯一门是 加法 和 乘法。这些简单操作的执行成本非常低——这使其成为资源受限环境（例如 区块链）中的良好计算模型。

顺便说一下，重要的是电路是一个 有向无环图(DAG)，这样只会向前进行计算，从而获得唯一结果。

为什么要这样麻烦？

此时，你可能在想：“为什么要定义图之类的东西，如果你可以直接计算多项式？”就是说，如果你有公式和系数……为什么不直接进行计算，而不去考虑电路？

尽管这有一点道理，但仍然存在一些需要考虑的问题——关于 可分解性、并行化、通用性 等等。我们将在下面看到这点。

例如，在同态协议中，可能希望执行已知能保持代数结构的操作。这些操作通常是“简单”的加法和乘法——将多项式分解为简单步骤可能有助于保持代数性质，因此使同态协议能够支持复杂计算。

呃……好的，当然。

应用

算术电路是我们手中的又一工具。但是，像往常一样，如果没有 应用，工具就毫无意义。

接下来，我想重点关注一个在零知识证明中特别感兴趣的方面。为此，让我们来玩一些 数独。

是的，数独。你听得没错！

解决一个传统的数独通常并不难（尽管有时确实会变得非常具有挑战性！）。我们可以肯定的是，检查一个给定的解决方案 是否有效 更容易——只要确保每行、每列和每个方框中没有重复的数字，我们就可以了。

但你们所想的是“标准”数独，这是一个 9 × 9 格子的棋盘。游戏可以通过使用 更大的棋盘 来扩展，比如 16 × 16、25 × 25、100 × 100，等等。随着棋盘尺寸扩大，问题变得非常、非常困难。然而，检查有效解决方案仍然很简单：你仍然检查每行、每列和每个方框中没有重复的数字。

这一切暗示着，有时 验证 一个问题的解决方案比 找到 它要容易得多——这点我们可以利用。

如果你对这个主题很感兴趣，你可能已经听说过，它被引用为 P vs NP 问题的一个例子。实际上，还没有证明存在那些难以解决但容易验证的问题——换句话说，还没有数学证明证明解决一个大型数独比验证它更困难。

这对计算机科学而言至关重要，以至于对证明 P = NP 与否的人提供了 一百万美元的挣赏。

是的，这很重要。

检查解决方案

如前所述，验证通过检查数字是否未重复来进行。我们来尝试将其写成方程形式？

坚持住，我的朋友

如果数字不应重复，则意味着每一行、每一列和每个方框的和都应相等，S：

我想没有人会反对我将数独的值表示为矩阵——我的意思是，这甚至是个正方形！就像为我们准备好的盘子一样。

当然其中一些值是被规定的，因为难题需要一个 初始状态 ，使其只有一个解决方案。

稍微关注一下第一列。如果我们将所有元素相加，一个有效的解决方案应给出预期值 S：

当然，我们必须对每行、每列和每个方框执行相同类型的检查——这样总共会产生 3n 个方程。即使其中 任何一个 检查失败，我们也立即知道解决方案是无效的。

这些方程可以表示为一个非常简单的 算术电路！只是，或许会有很多加法门。

这是 4x4 数独的一列电路。输出应为 S = 10

我们现在拥有一个验证 问题解决方案 的通用计算模型。换句话说，知识 解决方案的知识。因此，在进行 知识证明 时，我们可以 构建一个电路，表示对所选问题解决方案的验证。

这个问题可以帮助我们证明大量的声明：某个数字位于给定范围内，我们知道某个离散对数，我们知道某个值的哈希——确实，有很多声明。这就是算术电路的灵活性所在！

好的，或许你没这么兴奋。

关于零知识的说明

太好了！我们现在知道，给定某个声明，我们可以制作一个 算术电路 来表示其验证。只是验证需要电路的输入！

在 零知识证明 中，我们希望避免披露这些输入（或至少是那些应该保密的输入）。那么我们该怎么办？难道我们引入算术电路是没有意义的吗？

*痛苦加剧*

别担心，亲爱的朋友——这一切不是毫无意义。

因为算术电路可以 分解 成简单元素（它们的 门），我们可以进行一些魔法，这将允许验证者在 不知道 所选输入的情况下检查有效计算。我们很快就会讨论这个！

总结

这篇文章介绍了 算术电路 的概念，以及它们作为通用计算模型的作用。在这个意义上，我们讨论了它们如何用于 验证 解决方案——前提是问题被 正确表示 为算术电路。

算术电路是通用的计算模型，可以方便地分解为它们的构建块：门。

我们提到了这些算术电路如何 容易分解，以及这将帮助优化 零知识证明 中的 “零” 部分。然而，这还涉及一些新的 数学成就。

解释这些成就将最终使我们构建一个零知识证明协议，这是下篇文章的核心主题。在那之前再见！

• 原文链接： medium.com/@francomangon...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，在这里修改，还请包涵～