有限域：密码学赖以生存的数字系统

来自 Annkkitaaa 的原创研究

为什么“绕回”是 Zcash 的秘密基石

系列： Zcash from First Principles 。文章 1 。有限域 读者对象： 新手。我们只假设你掌握普通的学校算术（加、乘、除）。不需要任何密码学或高等数学基础。 你将收获： 对有限域的直观且正确的理解，明白为什么密码学家使用它们，以及它们在 Zcash 内部出现在哪里。

在文章 0中，我们认识了五个角色：note、commitment、note commitment tree、nullifier，以及零知识证明。我们留下了一个悬而未决的问题：所有这些密钥和秘密配方究竟从哪里来？ 它们来自数字。但不是你从小熟悉的普通数字。它们来自一种特殊的、自成体系的数字系统，叫作有限域，而 Zcash 中几乎所有密码学部件都建立在它之上。

这篇文章会慢慢把这个想法讲清楚。正如承诺的那样，先讲直觉。不到非用公式不可的时候，我们不会引入公式。

1. 为什么你需要关心它？

普通数字对密码学有一个问题：它们是无限多的，而且会泄露信息。

想想当一个数字变得更大时会发生什么。如果我告诉你，一次秘密计算得出了 8,142,067，你其实已经知道了很多：它是一个七位数，它是奇数，它“相当大”。大小本身就是线索。而线索，恰恰是隐私系统绝不能轻易泄露的东西。

密码学想要一种数字系统，在其中：

• 存在有限个取值，因此计算机可以精确存储其中任何一个值，不会有舍入误差，也不会溢出，
• 这些值不会泄露它们的大小，因为这个系统并没有真正意义上的“更大”这一概念，
• 你仍然可以自由且可逆地加、减、乘、除，因为密码学配方需要真正的代数结构才能运作，并且
• 这个空间可以做到大得惊人，让猜测毫无希望。

这份愿望清单有一个名字。它叫作有限域。在我们写下任何符号之前，先来建立它的直觉。

2. 直觉：时钟

其实你每天都在使用一种有限域。就是墙上的时钟。

在一个 12 小时制时钟上，数字会绕回去。从 10 点开始，加上 5 小时，你不会落在“15 点”，而会落在3 点。时钟只有十二个位置，超过顶端继续计数时，就会循环回到起点。

这里刚刚发生了三件事，而这正是本文的核心：

1. 这个世界是有限的。 无论你数多久，都只有恰好十二个位置。
2. 加法仍然成立。 你可以一整天都在加小时数；最终总会落在一个合法的钟面位置上。
3. 大小不再重要。 “3 点”并不能告诉你，你是数了 3 小时、15 小时还是 27 小时。绕回机制抹掉了大小信息。 这种抹除，正是我们想要的、对隐私友好的性质。

这种绕回的算术有一个正式名称：模运算。时钟按“模 12”工作，记作 mod 12。数学家更喜欢从 0 开始计位置，所以“模 12 的时钟”实际上有位置 0, 1, 2, ..., 11。模 7 的时钟则有位置 0 到 6。

唯一规则： 要计算任何“mod p”的结果，先做普通算术，再除以 p，只保留余数。 例子，mod 7：5 + 4 = 9，而 9 除以 7 的余数是 2，所以 5 + 4 = 2 (mod 7)。

3. 从时钟到域

时钟允许我们做加法。而域则是升级版：一种四则运算都正常工作的数字系统，其中包括最棘手的那一个——除法。

非正式地说，域是任何这样一组“数字”：你可以对它们加、减、乘、除（除了不能除以零），并且所有熟悉的规则依然成立：加法和乘法中顺序不重要，括号可以重新分组，存在 0 和 1，每个数字都有一个相反数，以及（除了 0 以外）一个倒数。

有理数是一个域。实数是一个域。我们想要的是一个有限的域。

下面是核心结论，而且它非常优美：

取全部整数 0, 1, ..., p-1，并让所有运算都按 p 取模。如果 p 是一个素数，得到的结果就是一个有限域。 我们记作 F_p（读作“F 下标 p”）。

所以 F_7 = {0, 1, 2, 3, 4, 5, 6}，配上模 7 的时钟式算术，就是一个真正的有限域。让我们看看它如何“呼吸”。

F_7 中的乘法（已验证）

表中每个项都是 (row x column) mod 7：

看看 1 到 6 这些行：每一行都恰好包含每个非零值 1..6 一次。这个“没有重复，也没有缺失”的模式，就是域最直观的指纹。

除法：需要素数的魔法

除法其实就是“乘以倒数”。在 F_7 中，数字 a 的倒数（或逆元）是那个满足 a x a^(-1) = 1 的值 a^(-1)。直接从表中读出来：

验证一个：2 x 4 = 8 = 1 (mod 7)。所以在 F_7 中，“除以 2”就意味着“乘以 4”。每个非零元素都有自己的搭档。这正是 F_7 成为一个域的原因。

4. 为什么模数必须是素数

这是全文最重要的一个思想，所以我们不抽象地讲，而是把它具体化。

看看如果我们天真地尝试构造一个模 6 的“域”会坏在哪里（而 6 不是 素数）：

是否存在某个 x，使得 2 x x = 1 (mod 6)？把它们全都检查一遍：2x0=0, 2x1=2, 2x2=4, 2x3=0, 2x4=2, 2x5=4。答案 1 从未出现。 所以 2 在 mod 6 下没有倒数。更糟的是，2 x 3 = 6 = 0 (mod 6)：两个非零数相乘却得到了零。

第二句话对算术来说就是灾难。两个非零的东西相乘得到零（称为零因子），意味着除法坏掉了，而除法失效的系统就不是域。它之所以会发生，恰恰是因为 6 可以分解为 2 x 3。

而素数按定义没有这样的因子。因此，在模一个素数的情况下，不会出现零因子，每个非零元素都能得到一个干净的倒数，于是这个结构才是一个真正的域。

可复用的一句话版本： 输入素数模数，输出干净除法。

5. 唯一值得认识的公式：计算机如何求逆元

对于 F_7，我们可以从表里直接读出逆元，但 Zcash 使用的素数有数百位，不可能制表。这里有一个经典捷径，也是本文唯一要出现的公式。

费马小定理说，对于素数 p 和任意非零 a：

a^(p-1) = 1   (mod p)

把它重新整理一下（剥掉一个 a 因子），你就免费得到了逆元：

a^(-1) = a^(p-2)   (mod p)

在 F_7 中测试一下（p = 7，所以 p - 2 = 5）：2 的逆元应该是 2^5 = 32 = 4 (mod 7)。而我们的表确实给出 2^(-1) = 4。计算机可以非常快地计算大幂，所以这就把“求倒数”变成了一次快速且精确的计算，即使面对极大的素数也是如此。

你不需要背下这个公式。你需要知道的是：有限域中的除法是一种快速且精确的运算，这正是密码学家乐于在其上构建系统的原因。

6. 为什么密码学爱上了有限域

把前面的直觉拼起来，整件事的理由一页就能讲完。

用一句话说，有限域就是：一个对算术而言完全封闭、完全精确、又大得惊人的游乐场。 Zcash 中的其他一切，都是在这个游乐场里搭建出来的。

7. 这在 Zcash 里体现在哪里

你不必仅凭信念接受“Zcash 使用有限域”这句话。下面是具体对应关系（更深的机制会留给后续文章；这里的目的只是说明这些指纹是真实存在的）。

• Sapling（一种较早的屏蔽设计）在一条名为 BLS12-381 的曲线上构建其证明，而这条曲线的基域使用一个长度为 381 bits 的素数。每一个坐标、密钥和证明元素，都是建立在该素数上的某个有限域元素。
• Orchard（当前的屏蔽设计）使用一对名为 Pallas and Vesta 的曲线（即 “Pasta” 曲线），其对应的域使用大约 255 bits 长的素数。
• 来自文章 0 的 note commitment、nullifier，以及零知识证明中的数字，归根到底都是这些有限域中的元素。当协议说“计算这个 commitment”时，它的意思就是“按那个素数做这套模运算”。

所以，对文章 0 中那个悬而未决的问题——“这些秘密配方从哪里来？”——答案就从这里开始：一切都始于有限域中的算术。 在下一篇文章里，我们会从这个域出发，构造真正的对象——椭圆曲线上的点——它们将变成密钥和 commitment。

8. 一个诚实的说明

为了让内容对新手友好，我们简化了一些真实情况。有限域并不只有 F_p 这一种形式；你也可以构造有 p^n 个元素的域（称为扩域），而它们对 Sapling 证明系统所依赖的“配对”很重要。我们也略过了完整的域公理列表，并简化了这种规模的素数是如何被选定和验证的。这些都不会改变你现在已经建立起来的直觉；它们只是对直觉做进一步细化。等到后续文章真正需要这些精度时，我们会再把这些细节补回来，并明确标注。

9. 总结

• 密码学需要一种有限、精确、对大小不敏感、可完全求逆、并且极其庞大的数字系统。这个系统就是有限域。
• 它的直觉模型是时钟：一种会绕回的算术（模运算），而这种机制恰好会抹去数字的“大小”。
• 用数字 0..p-1 并按一个素数 p 取模来做运算，就能得到真正的域 F_p，在其中你还可以做除法，因为每个非零元素都有逆元。
• 模数必须是素数：合数模数会产生零因子（例如 2 x 3 = 0 mod 6），从而破坏除法。
• 计算机通过费马小定理快速求逆（a^(-1) = a^(p-2)）。
• 在 Zcash 中，每个密钥、commitment、nullifier 和证明元素，最终都是某个大型有限域中的元素（Orchard 使用 255 位的 Pasta 域，Sapling 的 BLS12-381 使用 381 位域）。

术语表

FAQ

为什么不直接使用普通整数或小数？ 小数会舍入并产生漂移；整数会无限增长并泄露大小。有限域则是精确的、有界的，并且对大小不敏感，而这正是密码学所需要的。

“绕回”会丢失信息吗？ 会，而且这是有意为之。对隐私来说，抹掉中间值的大小信息是特性，不是缺陷。

素数越大就一定越安全吗？ 粗略来说，更大的域意味着更多可能值，也更难猜测，但安全性取决于整个构造，而不只是域的大小。后续文章会把这个说法讲得更精确。

为什么 Zcash 里要用这些特定的素数（255 位、381 位）？ 因为它们能让建立在其上的曲线具备证明系统所需的正确结构和效率。这个“正确结构”正是接下来两篇文章的主题。

测试一下你的直觉

在 F_7 中，5 - 6 等于多少？（记住：通过绕回，始终留在 {0,...,6} 内。）(答案见下方。)

接下来是什么

文章 2 。椭圆曲线： 我们会把刚刚构建好的有限域拿来画出一种奇特的曲线，这条曲线上的点可以彼此“相加”。这些点会变成 Zcash 的密钥和 commitment，并且它们隐藏着一个单向陷门，使整个隐私系统成为可能。和往常一样，依然先讲直觉。

本文属于 Zcash from First Principles 系列，由 ZecHub 发布。采用 CC BY-SA 4.0 许可协议。