零知识证明：基础原理简介

简介

零知识证明是密码学家设计出的最强大工具之一。遗憾的是，大多数人并不了解它。本文将从基本原理出发，全面介绍零知识证明，以解决这一问题。我们将讲解零知识证明背后的理论、数学和密码学，让每个人都能理解 Solana 上的最新进展，即 ZK Compression 以及互操作性的未来。

本文假设你已经了解 Solana 的编程模型，以及区块链系统固有的密码学原语（即哈希函数、哈希指针、Merkle 树和并发 Merkle 树）。如果你还不熟悉这些概念，建议先阅读以下往期博客文章：

• 密码学工具 101——详解哈希函数和 Merkle 树
• Solana 编程模型：Solana 开发简介

请注意，本文采用模块化设计。如果你刚接触这些主题，建议按顺序阅读每个章节和小节；如果你已经熟悉某些主题，或者只想了解某个特定主题，也可以直接跳转到相应章节。

本文也是零知识证明系列两篇文章中的第一篇。强烈建议先阅读本文，再继续阅读零知识证明：在 Solana 上的应用。

零知识证明背后的理论

1989 年，MIT 研究人员 Shafi Goldwasser、Silvio Micali（Algorand 创始人）和 Charles Rackoff 发表了交互式证明系统的知识复杂度。他们当时正在研究这样一种系统：一方（即证明者）与另一方（即验证者）交换消息，以使对方相信某个数学命题为真。他们率先提出了一个问题：“如果证明者和验证者互不信任，会怎样？”这里关注的是，在这些消息交换过程中，除了命题为真这一事实之外，验证者还能了解到多少信息。例如，证明者可能希望让验证者相信自己知道一道复杂谜题的解法，但不透露解法本身。

我们究竟要解决哪类问题？

图的三着色

图的三着色是计算机科学和图论中的经典问题。它要求使用三种颜色为图的顶点着色，使任何相邻顶点都不具有相同颜色。对于只有三个顶点的图，这很简单。但随着顶点数量增加，难度也会越来越高。

大学排课就是一个现实应用。在大型大学中，课程表必须确保任何学生的课程都不会出现时间冲突。每门课程都可以表示为图中的一个顶点，边则表示两门课程之间存在共同的学生。这样可以确保任何有共同学生的两门课程都不会安排在同一时间。此外，约束条件还包括教室容量、教授偏好的时间，以及将课程均匀分散到一周之中。因此，必须为课程分配时间段和教室，使任何两门相邻课程都不使用同一时间段。图的三着色可以解决这个问题。

现在，假设最终课表必须由外部审计公司验证。由于特定的隐私法规，大学不能与审计人员分享详细的学生选课信息。大学必须证明最终课表满足所需约束，同时不透露哪些学生选修了哪些课程。 

为此，大学必须创建一张图，其中每个顶点代表一门课程。如果两门对应课程至少有一名共同学生，就在两个顶点之间连一条边。大学会为每门课程分配时间段，确保任何两门相邻课程都不会同时进行。大学会使用密码学承诺方案对完成的课表作出承诺。具体做法是为每门课程分配的时间段创建密码学哈希，并将哈希分享给验证者，但不公开时间段。随后，外部审计公司会随机选择相邻课程对，对其分配的时间段发起质询。大学会公开所选相邻课程对已承诺的时间段，并提供原始承诺（即哈希），使外部审计公司能够验证公开的值。质询、公开和验证这几个步骤会反复进行，直到外部审计公司确信不存在课程冲突。强烈推荐使用 MIT 的交互式零知识三着色演示，实时查看这些步骤的执行过程。

大学希望向外部审计公司证明自己知道一个正确的排课方案。也就是说，它希望向另一方证明自己知道某件事。这个问题的优势在于，它是 NP 完全问题。

NP 完全

在计算复杂性理论中，如果一个问题满足以下条件，它就是 NP 完全问题：

• 对该问题的任何输入，输出要么是“是”，要么是“否”
• 当答案为“是”时，可以用一个简短的解来证明
• 每个解的正确性都必须能够快速验证，而且暴力算法可以通过尝试所有可能的解来找到答案

NP 完全问题非常重要，因为它们代表了 NP 类中最困难的问题（即一组非常困难的谜题：在多项式时间内验证猜测的解很容易，但找到解却很困难）。这些问题的一大特点是具备通用可模拟性。也就是说，如果我们能快速解决一个 NP 完全问题，就能将任何 NP 问题归约或转换成 NP 完全问题，并在多项式时间内找到解。验证 NP 完全问题的解也很容易。 

因此，我们拥有一整类可以用零知识证明高效证明的问题。例如：

• 旅行商问题——给定一组城市以及每对城市之间的距离，找出一条访问每座城市一次并返回起点城市的最短路线。这个问题广泛应用于物流、路线规划、制造和供应链管理
• 背包问题——给定一组物品，确定集合中每种物品的数量，使总重量小于或等于给定上限，同时让总价值尽可能大。这是金融和资源分配领域的常见问题
• 作业调度——给定一组具有特定持续时间和截止期限的作业，在一台机器上安排它们，以尽量降低作业逾期的总惩罚。该问题广泛应用于计算、制造和项目管理

此外，Cook-Levin 定理指出，布尔可满足性问题是 NP 完全问题。也就是说，任何变量可以替换为真值或假值，并最终求值为真的问题，都可以转换为 NP 完全问题。这意味着，任何可以归约成一系列真假问题的问题，都可以通过零知识证明高效证明。

零知识证明的性质

鉴于 NP 完全问题的复杂性和重要性，高效、安全地证明这类问题的解至关重要。零知识证明提供了一种不会损害相关信息隐私的方法。Goldwasser、Micali 和 Rackoff 提出，所有零知识证明都必须满足以下性质：

• 完备性——如果证明者诚实，最终一定能说服验证者
• 可靠性——作弊的证明者永远无法让验证者相信一个虚假命题
• 零知识性——证明者与验证者之间的交互只会揭示命题是否为真，不会透露任何其他信息

利用零知识证明的强大性质，我们可以在各种场景中证明事实或掌握某些信息，同时保护隐私并确保结果准确。在后续章节中，我们将探讨为什么这对区块链等要求高安全性和高效率的应用如此重要。

交互式与非交互式

零知识证明通常采用相同的三步结构：

• 证明者生成计算的解（即见证），然后发送对该见证答案的承诺
• 验证者使用随机生成的质询值作出响应
• 证明者根据承诺和质询计算最终证明

这种结构本质上是交互式的——证明者声称自己知道某件事，而验证者持续发起质询，直到证明者成功欺骗验证者的概率可以忽略不计。这对大多数应用来说并不理想，因为证明者在生成完整证明之前，需要获得一次或多次响应。这种设置天然存在以下问题：

• 验证者可能与证明者串通，允许其伪造证明
• 验证者可能创建虚假证明
• 验证者必须将其秘密值存储在某处，而这些值可能遭到泄露或攻击

Fiat-Shamir 启发式方法是一种将交互式知识证明转换为数字签名的技术。通过这种方式，可以公开证明某个事实，而不透露底层信息。其思路是，不再由验证者向证明者发送随机质询值，而是由证明者使用随机函数自行计算该数字签名，例如使用一个良好的密码学哈希函数。因此，验证者不再检查计算中的 500 个不同位置来确认它们全部正确，而是由证明者计算该计算的 Merkle 根，使用 Merkle 根伪随机选择 500 个索引，并提供对应的 500 个数据 Merkle 分支。关键在于，在数据完成承诺之前，证明者并不知道自己必须公开哪些分支。

敏锐的读者可能会发现，使用随机抽样来抽查计算存在一个致命缺陷——计算本质上非常脆弱。恶意证明者可以翻转计算中间的某一个比特，而验证者可能永远无法发现。验证者如何在不逐一查看计算中每个部分的情况下，检查计算的每个部分？答案是：多项式。

不过，在讨论多项式之前，我们还需要理解不少数学知识。

零知识证明背后的数学

以下内容并非对这些数学领域的全面介绍——每个章节本身都足以写成一篇完整文章。这里仅作简要介绍，帮助你开始理解零知识证明背后的数学基础，以及它们在宏观层面究竟如何运作。

本文还会向你介绍规范的数学符号。例如，在接下来关于集合论的小节中，我们会介绍符号 ∈、∉ 和 ⊆。归根结底，这些符号都只是其他概念的占位符。零知识证明并不是一个适合初学者的主题；因此，绝大多数相关文章对初学者并不友好。它们不会深入解释这些符号的含义，并且会假设读者已经理解这些符号。现在介绍这些符号非常重要，可以让有兴趣深入学习零知识证明的人不再对它们感到畏惧。尽量不要迷失在符号中。坚持下去，终有一天，当你看到这些符号时，想到的会是背后的概念，而不只是某个希腊字母。

集合论

集合论是研究对象集合的数学分支。集合是由互不相同的对象组成的汇集。这些不同的对象称为集合的元素或成员。例如，考虑一个水果集合：

在集合表示法中，花括号用于括住一组元素，以表示一个集合。这样，我们就知道 apple、orange、pear 和 banana 属于这个集合，而“potato”之类的对象不属于它。符号 ∈ 用于表示集合的隶属关系，读作“是……的元素”。同样，∉ 表示某个元素不属于给定集合。因此，我们可以写成：

我们会将其读作：“apple 是集合 Fruit 的元素，而 potato 不是集合 Fruit 的元素。”

子集

我们还可以创建由其他集合组成的集合。子集是仅包含另一个集合中元素的集合。例如，假设有：

我们可以说，集合 Citrus 是更大集合 AllFruits 的子集。我们也可以使用之前的 Fruit 集合，说明 Fruit 是更大集合 AllFruit 的子集。用集合表示法可以写成：

为什么这很重要？

集合论对于理解范围和约束的概念至关重要。在接下来关于数论和模算术的章节中，我们将探讨数字位于特定范围内的概念。例如，我们可能有一个密码学密钥的可能取值集合：

这里，K 定义了所有可能密钥的范围。我们可以构建零知识证明，对该集合应用某些约束，从而仅允许特定值有效。例如，可以规定密钥必须是 1 到 5 之间的数字。 

因此，集合论为定义和分析密码学协议中可能的输入、输出和状态集合提供了基础语言、工具和表示法。在零知识证明中，我们经常需要证明某个元素属于特定集合或范围，但不公开该元素本身。

建议访问 Khan Academy，完成一些关于基础集合表示法的优质练习题。

数论

数论是研究整数和算术函数的数学分支。我们可以将整数定义为完整数字（即不是分数的数字）的集合，包括正数、负数和零。更正式地说，整数集合可以定义为：

这里，ℤ 用于表示整数集合，省略号表示整数从负无穷延伸到正无穷。例如，数字 12 是整数，-1978649832794275 也是整数。

有理数

有理数是可以表示为分数的数，其中分母（即普通分数中横线下方的数字，也就是除数）不能为零。例如，$(\frac{1}{2}), 74, (\frac{2}{3})$ 都是有理数。更正式地说，我们可以将有理数定义为能够表示为分数 pq 的整数集合，其中 p 是分子，q 是分母，且 q 不为 0。符号 ℚ 用于表示有理数。使用集合表示法，可以写成：‍

‍乍看之下可能有些吓人，但它表达的内容与上一句话完全相同。我们会将这段看起来奇怪的数学术语读作：“Q 是所有 p 除以 q 的分数组成的集合，其中 p 和 q 都是整数，且 q 不等于零。” 

实数

实数包括有理数和无理数。无理数是无法表示为简单分数，并且小数部分无限不循环的数。例如，圆周率（即 π）和 $\sqrt{2}$（即 1.4.1421…）都是无理数。我们暂且跳过它的集合表示法，只需注意实数使用符号 ℝ 表示。

为什么这很重要？

数论与集合论密切相关，因为它研究特定的数字集合（例如有理数）。这些集合通常是定义数学和密码学问题中范围与约束的基础。 

我们也能看出数论与集合论之间的联系。例如，可以说所有整数的集合 ℤ 是有理数 ℚ 的子集。这一点可以从上面使用集合表示法给出的实数定义中看出，其中我们规定分子和分母都是整数。

模算术

模算术也称为时钟算术，是一种针对整数的数值运算系统。数字达到某个称为模数的特定值后会“绕回”。这里的思路是，不再处理无限的数字集合，而是使用前 n 个正数。

时钟

考虑一个数字从 1 到 12 的模拟时钟（我讨厌在这个年代还必须说明它有指针而且不是数字时钟）。如果现在是 11 点，我们想知道两小时后的时间，答案不会是 13 点，而是绕回到 1 点。这可以表示为 $11 + 2 \equiv 1 \pmod{12}$。这里正确的数学表达式是 $13 \bmod 12 = 1$。程序员应该熟悉按 $13 \% 12 = 1$ 的形式使用取模运算。

取模运算

当我们写 n mod k 时，表示我们想求 n 除以 k 的余数。这称为取模运算。例如：

• 25 mod 3 表示用 25 除以 3，余数为 1，因为 $25 = 8 \times 3 + 1$
• 15 mod 4 表示用 15 除以 4，余数为 3，因为 $15 = 3 \times 4 + 3$

在模算术中，余数始终为非负数。

为什么这很重要？

理解模算术至关重要，因为它能帮助我们理解数字在约束条件下的行为，而这对密码学非常有价值。模算术是许多密码学算法的基础，广泛应用于计算机科学、工程学以及任何需要安全处理和加密数据的领域。

考虑计算 x + y = z。如果我们使用由素数 p = 17 定义的有限域（很快就会讲到。现在可以把它理解为从 0 到 16 的所有整数构成的集合，并在 17 处绕回），那么该域中的计算将是 (x + y) mod *p = z。如果 x = 12 且 y = 15，计算如下：‍

**这里使用模算术，让我们能够在由素数 p 定义的可管理取值范围内执行计算。**这一点尤其重要，因为计算机和处理器的空间有限，所以我们通常使用固定大小的整数，例如 u32 或 u64。模算术可以确保值始终处于这些边界内。此外，使用素数还会增加一层复杂性。从密码学角度看，这至关重要，因为它可以增强安全性，并使某些数学性质更可预测、更可靠。

例如，zk-SNARKs 使用模算术来确保计算值处于特定且可管理的边界内。模算术还用于在给定数字集合上创建算术电路。这样，我们就能表达计算，同时确保它们可以得到高效验证。在这里，证明者必须证明自己执行了该计算，但不能公开 x、y 和 z 的值。

如果想获得更多解决模算术问题的实践经验，强烈建议查看 Art of Problem Solving 的习题集和 Joseph Zoller 的模算术练习。 

群论

群论是研究群这种代数结构的数学分支。群是一个元素集合，其中定义了一种满足以下条件的运算，这些条件称为群公理：

• 封闭性——任何算术计算的结果仍是该集合中的元素
• 结合律——对三个或更多元素执行同一种运算时，元素的分组方式不会影响结果
• 单位元——存在一个元素，将其与任何其他元素执行运算，都不会改变另一个元素的值
• 逆元——对于任何元素，都存在另一个元素，使两者执行运算后得到单位元

它们的正式定义如下：

• 封闭性——如果 a 和 b 是群的成员，那么运算结果（通常表示为 $a \times b$、$ab$、$a \circ b$, 或 $ab$）也是该群的成员。正式写法是 $\forall a, b \in G \mid a \circ b \in G$。可以读作：“对于集合 G 中元素 a 和 b 的所有值，a 与 b 的运算结果都属于 G”
• 结合律——如果 a、b 和 c 是群的成员，那么 (ab)c = a(cb)。正式写法是 $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$。可以读作：“对于集合 G 中元素 a、b 和 c 的所有值，先对 a 和 b 运算再与 c 运算，等于先对 b 和 c 运算再与 a 运算”
• 单位元——群中存在一个元素 e，使群中的每个元素 a 都满足 $e \circ a = a \circ e = a$。正式写法是 $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$。可以读作：“集合 G 中存在元素 e，对于集合 G 中的每个元素 a，先以 e 与 a 运算，等于先以 a 与 e 运算，并且都等于 a”
• 逆元——对于群中的每个元素 a，群中都存在一个元素 b，使 $a \circ b = b \circ a = e$，其中 e 是单位元。正式写法是 $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$。可以读作：“对于集合 G 中元素 a 的所有值，集合 G 中都存在元素 b，使先以 a 与 b 运算等于先以 b 与 a 运算，并且都等于单位元”

我们可以通过一个例子，将这些数学术语拆解成更容易理解的内容。考虑加法运算下的整数集合。我们可以说这个集合构成一个群，因为它满足全部四条群公理：

• 封闭性——两个整数相加，结果仍是整数
• 结合律——$(5 + 4) + 3 = 5 + (4 + 3)$
• 单位元——数字零是单位元，因为任何整数加零都不会改变其值。例如，$7 + 0 = 0 + 7 = 7$
• 逆元——任何整数的逆元都是它的相反数，因为两者相加会得到单位元。例如，$5 + (-5) = 0$。可以将其推广为 $n + (-n) = 0$

我们还可以扩展到一个更难的例子，例如在乘法运算下的非零有理数集合 $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$。它同样构成一个集合：

• 封闭性——两个非零有理数相乘，结果仍是非零有理数
• 结合律——$ab \times cd \times ef = ab \times (cd \times ef)$
• 单位元——数字 1 是单位元，因为任何非零有理数乘以 1 都不会改变其值。例如，$\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• 逆元——任何非零有理数的逆元都是其倒数（即交换分子与分母），因为结果等于单位元 1。例如，$\frac{3}{5} \times \frac{5}{3} = 1$

子群

子群是群中的群。如果说群 G 的子群 H 是 G 的子集，则必须满足以下群公理：

• 封闭性——如果 a 和 b 属于 H，那么两者的运算结果也必须属于 H
• 结合律——该公理继承自更大的群 G 
• 单位元——G 的单位元也必须属于 H 
• 逆元——对于 H 中的每个元素 a，H 中都必须存在某个元素 b，使 ab 和 ba 都等于单位元

一个经典示例是：加法运算下的偶数集合是加法运算下的整数集合的子群：

• 封闭性——两个偶数相加，结果仍是偶数
• 结合律——该公理继承自整数。例如，$2 + (4 + 6) = (2 + 4) + 6$
• 单位元——数字零是单位元，因为任何偶数加零都不会改变其值。零也属于整数集合
• 逆元——任何偶数的逆元也是偶数。例如，4 的逆元是 -4，因为 $4 + (-4) = 0$，结果为单位元

我们可以将其应用到更难的例子中。考虑乘法运算下所有非零有理数的集合（即 ℚ*）。我们可以证明，ℚ* 是乘法运算下非零实数集合（即 ℝ*）的子群：

• 封闭性——如果 a 和 b 是非零有理数，其乘积 ab 也是非零有理数。例如，$\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$，结果是非零有理数
• 结合律——有理数乘法满足结合律。例如，$(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• 单位元——数字 1 是单位元，因为任何非零有理数乘以 1 后保持不变。例如，$\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• 逆元——每个非零有理数 $a = \frac{p}{q}$ 都有一个乘法逆元 $a^{-1} = \frac{q}{p}$，它也是非零有理数，与原数相乘等于单位元。例如，令 a = $\frac{2}{3}$。其逆元是 $\frac{3}{2}$，因为 $\frac{2}{3} \times \frac{3}{2} = 1$

由于 ℚ* 满足所有群公理，因此它构成一个群。此外，因为 ℚ* 是 ℝ* 的子集并继承其性质，所以可以说 ℚ* 是 ℝ* 的子群。

为什么这很重要？

群是各种数学和密码学概念与结构的基础。例如，RSA 和椭圆曲线密码学等密码系统高度依赖群及其运算的性质。通过研究规模更小、更易处理的子集，理解子群有助于我们理解更大群的结构。群为理解对称性、运算和变换提供了基本框架，而这些知识对接下来学习域至关重要。

域

域是一个元素集合，它满足加法和乘法的域公理，并且是一个可交换除法代数（即除了除以零之外，除法始终可行）。域公理通常按加法和乘法成对列出：

• 加法
  • 结合律： $(a + b) + c = a + (b + c)$
  • 交换律： $a + b = b + a$
  • 分配律： $a(b + c) = ab + ac$
  • 单位元： $a + 0 = 0 + a = a$
  • 逆元： $a + (-a) = 0$
• 乘法
  • 结合律： $(ab)c = a(bc)$
  • 交换律： $ab = ba$
  • 分配律：$(a + b)c = ac + bc$
  • 单位元： $(a + b)c = ac + bc$
  • 逆元： $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

有限域与生成元

有限域是元素数量有限的域。有限域也称为伽罗瓦域。元素数量称为域的阶或基数。元素数量始终是素数的幂。有限域的优势在于，对域内元素执行的任何算术运算，其结果都仍然位于该域中。这是因为所有运算都以域的阶为模执行，使值能够绕回。

每个有限域都有一个生成元。生成元可以通过幂运算生成域中的所有元素。这意味着，我们可以取生成元并逐次将其指数加一，直到得到域中的所有元素。因此，生成元是域中的一个元素，它的各次幂能够产生域中的每个非零元素。

例如，假设我们取模 p = 7 的整数集合，并得到域 $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$。如果想找到 $\mathbb{Z}_7^*$ 的生成元 g（即 $\mathbb{Z}_7$ 中非零元素的乘法群），就需要确保 g1、g2、g3 等可以生成域中的所有非零元素。

让我们检查 3 是否为生成元：

3 的各次幂生成了 $\mathbb{Z}_7$ 中的所有非零元素。因此，3 是乘法群 $\mathbb{Z}_7^*$ 的生成元。

为什么这很重要？

密码学是一门处理有限集合的科学。有限集合构成了一项基础知识，对理解离散对数问题、加密、Diffie-Hellman 交换和椭圆曲线等主题至关重要。生成元允许我们在不解密加密多项式的情况下对其进行算术运算（即同态加密）。也就是说，我们可以在保护底层值隐私的同时，对加密数据进行计算。理解本节对于掌握零知识证明中的“零知识”部分至关重要。

建议访问 Bill’s Security Site，其中提供了一个交互式示例，展示如何使用特定参数生成有限域，并介绍 Python 中的底层理论。 

函数

函数是一种表达式、规则或定律，用于定义两个变量之间的关系，即自变量与因变量。这两个变量通常分别描述为原因和结果。这种关系通常表示为 y = f(x)，读作“x 的 f”。每个 x 值都有唯一的 y 值，这意味着对于同一个 x，f(x) 不能有多个值。

函数可以是一对一或多对一的，这通常称为基数关系。这意味着一个 x 值可以映射到唯一的 y 值，或者多个 x 值可以映射到同一个 y 值

假设有一条由 $y = 3x + 4$ 定义的直线。这是一个线性函数，代入 x 的值会得到对应的 y 值。这两个值共同构成直线上的一个点。例如，可以将方程改写为 $f(x) = 3x + 4$，然后计算 x = 1 时的值，得到 $f(1) = 7$。函数也可以包含多个变量。例如，考虑三角形面积公式：$A = \frac{bh}{2}$。这里，A（即面积）被定义为 b（即底）和 h（即高）的函数。

定义域和值域

函数的定义域是函数能够接受的所有可能输入值（即自变量）的集合。函数的值域是函数能够产生的所有可能输出值（即因变量）的集合。

对于函数 $y = 2x + 2$：

• 定义域是所有实数，因为从负无穷到正无穷的任何数都适用。例如：
  • 如果 x = 2.5，则 $y = 2(2.5) + 2 = 7$ 
  • 如果 x = -9234525，则 $y = 2(-9234525) + 2 = -18469048$
• 值域也是所有实数，因为可以产生从负无穷到正无穷的任何数。例如：
  • 要得到 y = -50，可以求解 -50 = 2x + 2，得到 x = -26。 
  • 要得到 y = 0，可以求解 0 = 2x + 2，得到 x = 0

为什么这很重要？

函数是理解多项式的关键。多项式是一种特殊函数，其中包含变量的不同次幂及其系数。多项式是基础代数结构，为构建密码学协议提供了基础。在下一节中，我们将详细探讨多项式，了解其性质及其在零知识证明中的重要性。

建议查看 Paul’s Online Notes 并完成其中的练习题，以便更好地理解函数。

多项式

多项式是一种由多个变量和系数组成的函数，其中仅涉及加法、减法、乘法以及变量的非负整数次幂运算。多项式通常写成以下形式：‍

其中 $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ 是系数，x 是变量。变量 x 的非零系数项中的最高幂称为多项式的次数。

多项式可以分为一元多项式和多元多项式。一元多项式只包含一个变量（即上面写出的形式），多元多项式则包含多个变量（例如 $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$。Sum-Check 是使用多元多项式的协议示例。不过，大多数情况下，零知识证明只需要一个变量。

根据次数，多项式的常见名称包括：

• 0 次——非零常数（例如 $P(x) = 6$）
• 1 次——线性（例如 $P(x) = 2x - 7$）
• 2 次——二次（例如 $P(x) = 8x^2 - 3x + 1$）
• 3 次——三次（例如 $P(x) = 3x^3 - 4x$）

如果有两个次数至多为 $d$ 且不相等的多项式，它们最多只能相交于 $d$ 个点（例如，将线性函数与三次函数设为相等时，它们最多可以相交三次）。这一性质源于寻找公共点的方法。要找出两个多项式的交点，我们需要将它们设为相等。在下一小节中，我们将练习求多项式的根，也就是寻找给定多项式与 x 轴的交点。代数基本定理指出，$d$ 次多项式最多可以有 $d$ 个解，因此最多有 $d$ 个公共点。

多项式的根 

多项式的根或零点，是使多项式等于零的 x 值。换句话说，如果 $P(x)$ 是一个多项式，那么根 $r$ 就是方程 $P(r) = 0$ 的解。要找到根，我们必须熟悉多项式因式分解。因式分解就是找出哪些数相乘可以得到给定的量。例如，12 有多种因式分解方式：

一种常见的因式分解方法是将一个数完全分解为正质因数。进行因式分解时，最好始终先找出所有项共有的最大公因数（GCF）。例如：

在上面的例子中，两项（即 6x 和 3）都能被 3 整除，因此它们的最大公因数是 3。所以，其因式为 3 和 $2x + 1$。这是对分配律的逆向运用：$3 \times 2x$ 和 $3 \times 1$。求根就是在 $P(x) = 0$ 时求解 x。

对于二项多项式，因式分解很直观。如果给出了图像，则更为直观，因为根就是多项式与 x 轴的交点。然而，次数达到三次或更高时，问题会更复杂。建议阅读文章多项式因式分解详解，了解更深入的说明。 

要继续阅读本文，并不需要精通不同多项式因式分解的所有细节。就我们的目的而言，我们关注的是多项式等于另一个值的情况。这里，我们关注多项式等于零的情况。稍后，我们会关注一个多项式等于另一个多项式，或两个多项式之差恒等于零（即所有系数均为零）的情况，这需要检查给定多项式是否具有特定的根。

Schwartz-Zippel 引理 

Schwartz-Zippel 引理是一种用于检查多项式方程是否恒成立的概率工具。它在随机点上计算多项式，并检查结果是否为零。

设想一个包含变量 $x_1, x_2, \ldots, x_n$ 的复杂方程。如果该方程是一个多项式，而不是若干项的随意组合，那么 Schwartz_Zippel 引理可以帮助我们验证它是否对这些变量的所有可能取值都成立。

其工作方式如下：

• 设 $P(x_1, x_2, \ldots, x_n)$ 是总次数为 d 的多项式（即任意项中指数之和的最大值）
• 从该域中选择一个有限集合 S（类似于选择一组数字）
• 从集合 S 中为每个变量 $x_1, x_2, \ldots, x_n$ 随机选择值

该引理指出，P 在这些随机选择的点上为零的概率至多为 $\frac{d}{S}$。这意味着，如果多项式不为零，它因随机巧合而看起来为零的概率非常低。这对零知识证明尤其有用，因为我们需要高效验证多项式恒等式。

拉格朗日插值

拉格朗日插值是一种构造经过给定点集的多项式的方法。拉格朗日多项式是经过每个给定点的最低次数多项式。对于 n 个点，可以构造一个经过所有这些点的 n-1 次多项式。例如，如果平面上有两个点，我们可以定义一条经过这两个点的直线。如果平面上有三个点，我们可以定义一个经过所有这些点的二次多项式（即 $y = ax^2 + bx + c$）。以此类推。

为什么这很重要？

多项式是一个可以包含无限量信息的单一数学对象——把多项式看作一个整数列表，这一点就不言自明了。因此，一个多项式等式可以表示无限多个数值等式。如果有人能够验证给定的多项式等式，也就隐式地同时验证了所有可能的等式。这正是我们保护非交互式证明，使其免受恶意证明者危害，同时避免依赖对给定计算进行随机抽查的方式。 

多项式还具有多种适合构造证明的性质：

• 如果给定多项式有足够多的点，就可以重建整个多项式
• 多项式输入的微小变化可能导致输出发生显著变化，从而更容易检测错误
• 多项式可以检测并纠正计算错误，类似于纠删码让数据具备容错能力（这对 Turbine 的工作方式至关重要）

零知识证明用于证明特定计算。多项式在这方面价值巨大，因为我们可以根据所需特性来构造它们。假设你有一项计算或一组想要证明的数据点。最简单的方法是将其编码为多项式，并利用多项式的性质构造证明：

• 将数据编码为多项式 $P(x)$，使得在特定点计算 $P(x)$ 时可得到原始数据或给定计算的结果
• 为确保多项式符合给定条件（例如所有值都位于某个范围内），创建约束多项式 $C(x)$。例如，$C(x) = (P(x) - 0)(P(x) - 1)$ 可确保 $P(x)$ 为 0 或 1
• 将问题转化为证明 $P(x)$ 对你的数据集或计算满足特定条件
• 创建一个已知多项式 $H(x)$，它是编码了这些条件的 $P(x)$ 的倍数
• 证明者通过为 $P(x)$ 及任何相关多项式的计算值创建 Merkle 树来提交这些值，并将根哈希发送给验证者
• 验证者随机选择若干点，并要求证明者提供 $P(x)$ 和 $C(x)$ 在这些点上的值
• 验证者根据已提交的根哈希和预期的多项式关系检查所提供的值

无论多项式有多大都没有关系；由于使用了多项式承诺，我们可以在很短的时间内验证多项式之间的等式。这是一种高度简洁且高效的证明构造方式。任何错误都会被放大，而借助 Fiat-Shamir 启发式方法等技术，这些证明可以变为非交互式，让任何人无需进一步交互即可验证。 

为了进一步加深理解，建议完成以下练习题：

• 多项式练习题
• 求多项式零点练习题
• 多项式因式分解：附答案的高难度题目

Khan Academy 也提供了关于多项式表达式、方程和函数的完整单元。

现在，为了更好地理解多项式承诺，有必要探索零知识证明背后的密码学。

零知识证明背后的密码学

下面介绍对称加密和非对称加密。

对称加密

对称加密是一种使用同一密钥加密明文和解密密文的加密技术。该密钥通常称为秘密密钥或私钥，因为使用单一密钥意味着必须对其保密。但这也意味着双方必须先共享秘密密钥，之后才能安全通信。因此，安全管理和分发秘密密钥可能很有挑战；如果处理不当，还可能发生泄露。尽管存在这一缺点，对称加密仍然快速、高效，并且比其他加密方案需要更少的计算能力和内存。

常见的对称加密算法包括：

高级加密标准（AES）

高级加密标准（AES）是 Rijndael 分组密码的一种变体，在全球广泛用于保护数据安全。它支持 128、192 和 256 位密钥。

ChaCha20

ChaCha20 是由 Daniel J. Bernstein 开发的一种现代高效流密码。它是 Salsa20 流密码的变体，利用了加法—旋转—异或（ARX）运算。它将一个 256 位密钥、一个 64 位 nonce 和一个 64 位计数器映射为一个 512 位密钥流块，这意味着用户可以在常数时间内高效定位密钥流中的任意位置。

虽然对称加密稳健且高效，但它需要安全的密钥交换方式。Diffie-Hellman 密钥交换就是这样一种方法，它允许双方通过不安全的信道安全地共享秘密密钥。不过，这种方法基于非对称加密原理，我们将在下一节中介绍。

非对称加密

非对称加密也称公钥加密，是一种使用一对相关密钥（即公钥和私钥）加密及解密信息的方法。公钥可以公开共享，而私钥必须保密。发送方要加密消息时，会使用接收方的公钥。接收方收到消息后，使用对应的私钥解密。用公钥加密的数据只能用私钥解密。因此，非对称加密可以在不安全的信道上实现安全通信，因为解密密钥从不共享。

非对称加密的优势在于私钥从不共享，因此能够提供很高的安全性。它还简化了密钥分发，因为公钥可以公开共享，并且支持数字签名。不过，非对称加密比对称加密需要更多计算资源，速度也更慢。密钥对管理也可能变得复杂，尤其是在用户数量庞大或密钥对不够直观的系统中。 

常见的非对称加密算法包括：

• Rivest-Shamir-Adleman（RSA） — 最早且使用最广泛的安全数据传输公钥密码系统之一。它开发于 20 世纪 70 年代，依赖于分解两个大质数乘积在实践中的困难性
• 椭圆曲线密码学（ECC） — 一种基于有限域上椭圆曲线代数结构的公钥密码学方法。它能提供与 RSA 类似的安全性，但密钥更小，因此计算更快，存储需求也更低。Solana 使用 Ed25519 椭圆曲线生成密钥对

数字签名

数字签名是公钥密码学的关键组成部分，提供了一种验证消息、软件或数字文档真实性与完整性的方法。数字签名使用发送方的私钥创建，任何能够访问对应公钥的人都可以验证。这可以确保消息由合法发送方发送，并且未被篡改。

数字签名常用的算法包括：

• 数字签名算法（DSA） — 一种基于模幂运算（即以某个数为模进行的幂运算）和离散对数问题的方法
• 椭圆曲线数字签名算法（ECDSA） — DSA 的一种变体，使用椭圆曲线密码学，以更小的密钥提供更高的安全性

离散对数问题

离散对数问题是求方程 $g^k \equiv h \pmod{p}$ 中指数 k 的问题，其中：

• g 是已知的底数（即生成元）
• h 是已知的结果（即群中的一个元素）
• p 是质数（即群的阶）
• k 是未知指数（即以 g 为底的 h 的离散对数）

简单来说，如果已知 g、h 和 p 的值，离散对数问题就是求 k。例如，给定方程 $2^k \equiv 9 \pmod{23}$，目标是求出 k。

离散对数问题被认为难以高效求解，尤其是在数字很大时。正因如此，它构成了多种密码系统的安全基础，包括 Solana、ElGamal 加密、数字签名算法（即 DSA 和 ECDSA）以及 Diffie-Hellman 密钥交换

Diffie-Hellman 密钥交换

Diffie-Hellman 密钥交换是一种通过公共信道安全交换加密密钥的方法。 其最简单且最初的实现（即有限域 Diffie-Hellman）如下：

• Alice 和 Bob 公开商定两个数字——一个大质数 p（即模数）和一个底数 g（即生成元），其中 g 是模 p 的原根 
• Alice 选择一个秘密整数 a，然后向 Bob 发送 $A \equiv g^a \pmod{p}$
• Bob 选择一个秘密整数 b，然后向 Alice 发送 $B \equiv g^b \pmod{p}$
• Alice 计算 $s \equiv B^a \pmod{p}$ 
• Bob 计算 $s = A^b \pmod{p}$ 

现在，Alice 和 Bob 拥有相同的秘密值。这是因为两个计算都会得到同一个秘密 s：

随后，这个共享秘密 s 可以作为对称加密的密钥，让 Alice 和 Bob 能够安全通信。Diffie-Hellman 密钥交换的安全性依赖于离散对数问题的求解难度。在不知道秘密值 a 和 b 的情况下，窃听者在计算上无法推导出共享秘密。这称为单向函数——计算它相对容易，但进行逆运算极其困难。

虽然有限域 Diffie-Helman 密钥交换安全且应用广泛，但它需要很大的密钥才能确保安全。例如，如果 Alice 和 Bob 公开选择的模数都是 23，那么破解就容易得多，因为 n mod 23 只有 23 种可能的结果。因此，这种方法可能消耗大量计算资源，效率也较低。为解决这些问题，椭圆曲线密码学（ECC）提供了更高效的替代方案，因为它能以小得多的密钥和更快的计算提供相同级别的安全性。

椭圆曲线

椭圆曲线由方程 $y^2 = x^3 + ax + b$ 定义，其中 a 和 b 是常数。椭圆曲线密码学就是对给定椭圆曲线上的点进行运算。这些曲线具有多种独特性质，因此适用于密码学。例如：

• 点的加法 — 给定某条椭圆曲线上的两个点 P 和 Q，它们的和 R = P + Q 也会是曲线上的一个点。Preethi Kasireddy 的文章《零知识证明密码学无痛指南》很好地解释了如何在椭圆曲线上进行点加法
• 标量乘法 — 给定某条椭圆曲线上的点 P 和整数 k，标量乘法就是将点 P 与自身相加 k 次。这样会在曲线上产生另一个点（即 kP）。该运算用于从私钥生成公钥
• 离散对数问题 — 椭圆曲线上的离散对数问题比对应的整数问题难解得多。给定点 P 和 q = kP，如果正确选择曲线参数，在计算上就无法确定 k。这意味着椭圆曲线可以用小得多的密钥提供与传统系统相同的安全性，因此效率更高

根据刚刚了解的群论知识，我们可以说，某些椭圆曲线方程满足一组公理：

• 任意两个点相加都能得到第三个点
• 两个点相加的顺序不影响结果
• 如果要将两个以上的点相加，相加顺序不影响结果
• 存在单位元（即零与曲线上的任意点相加，结果仍是该点）

强烈建议阅读 Georgie Bumpus 的椭圆曲线密码学，更深入地了解这种群结构。 

椭圆曲线能提供与 RSA 等其他传统密码系统相同级别的安全性，但密钥小得多。例如，ECC 中的 256 位密钥可提供与 RSA 中 3072 位密钥相当的安全性。这带来了以下优势：

• 更小的密钥可实现更快的加密和解密
• 密钥和证书所需的空间更少
• 更小的密钥可以减少传输的数据量，这对区块链等带宽有限的环境很有帮助

Montgomery 曲线

Montgomery 曲线是一种定义在有限域上的椭圆曲线，其方程为 $By^2 = x^3 + Ax^2 + x$，其中 A 和 B 是常数，B 不等于零，且 A 不是 -2 或 2。这类曲线的特殊之处在于，可以使用 Montgomery 阶梯更高效地实现椭圆曲线乘法。 

Montgomery 阶梯本质上会接收 Montgomery 曲线上的一个点 P 和一个标量 k，初始化从无穷远点到 P 的两个点，并从最高有效位到最低有效位依次更新标量 k 的每一位。核心思想是维护两个点，并且无论标量 k 的各个位为何值，都以恒定的操作序列更新它们。

这很重要，原因如下：

• 它可以抵抗侧信道攻击。侧信道攻击是指利用特定协议或算法在实现或设计过程中产生的额外信息实施的任何攻击。这是一个非常、非常硬核的研究方向，值得深入探索。此类攻击包括利用硬件在计算期间不断变化的功耗，以及利用泄漏的电磁辐射
• 不需要 y 坐标，因为仅使用 x 坐标即可执行标量乘法
• 它在常数时间内运行，也就是说，给定计算所需的时间与输入值无关

Montgomery 曲线广泛用于密码协议，例如用于密钥交换的 X25519 算法，该算法使用 Curve25519 曲线的 Montgomery 形式。该算法是现代安全通信的基础，热门协议中的实现包括 TLS。 

Edwards 曲线

Edwards 曲线是一类由方程 $x^2 + y^2 = 1 + d x^2 y^2$ 定义的椭圆曲线，其中 d 是一个不为零且不等于 1 的常数。  

这类曲线之所以重要，是因为：

• 点运算效率 — 与其他形式的椭圆曲线相比，在 Edwards 曲线上进行两点相加更高效。点加法和倍点运算的公式更简单，涉及的域运算更少，因此计算速度更快
• 统一加法公式 — Edwards 曲线使用统一加法公式，这意味着点加法和倍点运算可以使用同一公式。这样可减少实现错误的可能性并增强安全性
• 完备性 — 对于 d 的某些取值，Edwards 曲线是完备的。这意味着加法法则可以无例外地涵盖所有可能的输入。
• 抵抗侧信道攻击 — 与 Montgomery 曲线一样，Edwards 曲线凭借统一且可预测的运算模式，能够抵抗侧信道攻击。

一种广泛使用的 Edwards 曲线是 Edwards25519，其定义方程为 $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$。该曲线以高效算术运算和 256 位密钥而闻名。它的签名方案已在多种安全协议和系统中实现，包括 Solana、OpenSSH 和 Tor。Monero 使用 Edwards25519 作为生成密钥对的基础。

为什么这很重要？

椭圆曲线凭借其高效且能够增强安全性的特征，在零知识证明中至关重要。请注意：使用椭圆曲线可以创建更小、更快的证明，这对任何实际实现都不可或缺。在讨论零知识相关发展时，我们会进一步分析这一点。但在存在多种账户和交易限制的高计算负载环境中，对小型、快速证明的需求至关重要。正因如此，零知识证明很适合用于构建 rollup：可以生成简洁证明，证明 L2 上的所有操作均有效，然后在 L1 上进行验证。

归根结底，可以将椭圆曲线视为模运算的替代方案。使用椭圆曲线时，求得特定点要困难得多。如果使用传统模运算 $g^a \bmod n$，其中 g 是生成元，n 是一个大质数，a 是秘密密钥。正如前面讨论离散对数问题时所述，需要非常大的质数才能保护秘密密钥。椭圆曲线提供了使用更小密钥的高效替代方案，能在大幅提升性能的同时提供相同级别的安全性。

随机性

如果没有随机性这一密码学的基本要素，本文的其他内容都将失去意义。如果系统中的值可以预测且存在偏差，又如何期待它是安全的？真正的随机性很难实现，但基于以下几个原因，它至关重要：

• 密钥生成 — 必须随机生成加密密钥，以确保其不可预测且安全
• Nonce 和盐值 — Nonce（即只使用一次的数字）和盐值（即在哈希前添加到数据中的随机值）分别用于防止重放攻击和抵御预计算攻击
• 安全协议 — 随机性用于确保公平性和安全性，避免出现可预测性以及攻击者可以利用的模式

大多数随机数生成器都无法生成可通过密码学方式验证的随机数。这使它们容易受到操纵，并限制了其使用场景。不过，可验证随机函数解决了这个问题。

可验证随机函数

可验证随机函数（VRF）是一种密码学原语，可以生成随机输出，以及证明该输出由给定输入正确生成的证明。VRF 必须不可预测，也就是说，对于任何不知道秘密输入的人，其输出都无法与随机值区分。它的安全性依赖于 RSA 假设，即在不知道秘密指数 d 的情况下很难计算 $y = h^d \bmod n$，同时也依赖于哈希函数 H 的安全性。 

给定 VRF 的主要步骤如下：

• 密钥生成 — 用户生成一对 RSA 密钥，以 (e, n) 作为公钥，以 (d, n) 作为私钥。公钥中的 e 是指数，n 是模数。私钥中的 d 是秘密指数
• 计算 — 给定输入 x，用户计算 VRF 输出 y 和证明 π。首先计算哈希 h = H(x)，其中 H 是密码哈希函数。然后计算 $y = h^d \bmod n$，即该哈希的 RSA 签名。最后计算证明 π = (h, y)
• 验证 — 给定公钥 (e, n)、输入 x、输出 y 和证明 π = (h, y)，任何人都可以通过检查哈希 h 是否等于 $H(x)$，并检查 $y^e \equiv h \pmod{n}$ 以验证 RSA 方程，从而验证 VRF 输出的正确性‍

VRF 常用于共识协议，因为这类协议中的随机性需要不可预测，同时又可验证。包括 Algorand、Cardano、Internet Computer 和 Polkadot 在内的 L1 都在其共识机制中使用 VRF 随机选择区块生产者。Chainlink 提供 Chainlink VRF，作为用户与区块链之间的抽象层，用于生成可证明公平且可验证的值。Pyth Entropy 也提供可靠且安全的随机性来源。

仪式与可信设置

密码学仪式是在安全、受控的环境中执行关键密码计算的协议或活动。密码学仪式有多种类型，主要包括：

• 密钥生成仪式 — 生成加密密钥，确保没有任何单一实体能够控制密钥生成过程
• 参数生成仪式 — 创建供多方使用的密码参数
• 多方计算（MPC）仪式 — 由多方共同执行密码计算，确保任何单一参与方都无法破坏该过程

可信设置仪式是一种特殊活动或流程，用于生成运行密码协议所需的一组密码参数。在关于交互式和非交互式零知识证明的章节中，我们指出证明的第一步是让证明者和验证者就要使用的某个值达成一致。在可信设置仪式中，多名参与者为设置过程贡献随机性，以确保没有任何单一参与者能够控制该过程。每名参与者都会生成一个随机值，并与其他参与者提供的值组合。组合后的输出会成为一组所有人都能信任的参数。 

这一过程至关重要，因为如果所有参与者串通，他们就可以为无效声明生成证明，从而破坏系统。不过，只要有一名诚实参与者，就能确保这些参数的安全性。 

Zcash 曾使用可信仪式来引导启动该链的隐私功能，这一做法广为人知。Ethereum 也举行过 KZG 仪式，这是一场协调开展的公共仪式，旨在为其扩容工作（例如 EIP-4844 / proto-danksharding）奠定密码学基础。 

请注意，某些零知识证明系统（例如 zk-STARK）不需要可信设置。我们将在第二篇文章中进一步探讨这一点。

总结

本文探讨了零知识证明背后的理论、数学原理和密码学知识。这些内容足以帮助你开始理解什么是零知识证明。接下来，我们可以将这些知识应用于 Solana 等网络，推动零知识证明领域的整体讨论与发展。

我们将在零知识证明系列的第二篇，也是最后一篇文章中继续分析，文章名为 零知识证明：在 Solana 上的应用。 

如果你读到了这里，感谢你，匿名朋友！请务必在下方输入你的电子邮件地址，以免错过 Solana 的任何最新动态。准备好深入探索了吗？立即阅读 Helius 博客上的最新文章，继续你的 Solana 之旅。

其他资源

• 真正的随机性存在吗？
• 椭圆曲线 — Computerphile
• NP 完全复杂度类简介
• 密钥交换问题 — Computerphile
• 可汗学院密码学单元
• 公钥密码学 — Computerphile
• 交互式证明系统的知识复杂度