零知识编年史：群

为了获得更具互动性的体验，请在我的个人博客 Arkana 上阅读。

上次，我们介绍了一个关键工具——哈希。

一个全新的密码学原语竟能为我们解锁如此巨大的潜力，这真是令人难以置信。但要继续前进，仅仅依靠哈希是远远不够的！

我们还需要更多的工具，它们将最终（几乎）完全扫清前进的道路，使我们能够应对最复杂的 ZK 技术。

那么，今天的主题将是数学群。这是一个抽象的概念，但不要因此而却步：我们很快就会将其引入熟悉的领域。

我们将不得不涉及一些更复杂的内容，但同样，不必过于担心。我们不会深入探究更精细的细节，目前只需要了解最重要的概念即可。此外，还有大量材料可以帮助你理解今天所构建内容的细微之处。

当然，我也写了很多关于它们的内容，所以我会随时链接相关的博客文章！

今天的介绍就到这里！是时候言归正传了。

群

我们今天需要讨论的第一个概念是群。

这里的名称可能有点误导。谈到群，我们可能会想象一堆元素聚集在一起。虽然这种说法有一定道理，但远非全貌。

事实上，上述定义更适合描述一个数学集合。

这正是它的本质：一堆元素构成一个单一实体！

不过公平地说，集合论 是一个非常重要的数学领域，具有丰富的表达能力和非常深刻的定理（如良序定理）。但这将是另一个话题了！

一个群 实际上由两部分组成：一个集合，以及一个二元运算：一个函数，它接受该集合中的两个输入，并输出同样属于该集合的另一个元素。

是的，我知道。这听起来像抽象数学，而且很快就会变得令人望而生畏。

不过好消息是，我们不需要关注所有可能存在的奇异群。我们只需要了解几个感兴趣的群（或群族），这应该足以涵盖本系列剩余的内容！

我不知道我是否还能信任你

所以在我们了解实际使群对密码学有用的良好性质之前，让我们聚焦于我们的两个主角，它们是现代技术的主力军。

整数，再次回顾

等等，整数？我们不是已经讲过那些了吗？

不，你的记忆并没有背叛你。正整数（模 $p$）是有限域（一个我们系列一开始就定义的结构）的典型例子（双关语）。

你可能还记得，有限域是一个集合加上四种运算，而不是单一的运算。只要我们只考虑一种运算，有限域就可以“像”一个群一样工作，但那是在作弊：群的大多数有趣的性质都 heavily focused on the guarantee that there’s a single valid way to combine two group elements，有效地排除了其他捷径。

这使得我们的问题变得更重：为什么整数会是有效的候选呢？嗯，考虑一下当我们从原始集合中移除零时会发生什么：

这看起来像是一个无关紧要的改变，当然。但关键是：

我们能将这个集合中的任意两个元素相加吗？

花点时间考虑一下选项。将两个随机元素相加似乎是可行的。$2 + 3$ 仍然是 $5$。如果超出范围，我们应用模运算，并且仍然没问题。

但是当我们加 $1$ 和 $p - 1$ 时会发生什么呢？结果当然是零。但是……零已经不在集合中了！正因为如此，加法现在不构成有效的运算。或者，更正式地说，我们称该集合对加法不封闭。

乘法则是另一回事。你看，集合中的所有元素都小于 $p$。如果 $p$ 是一个素数，那么你永远不能将两个集合元素相乘得到 $p$，因为那将意味着 $p$ 一开始就不是素数！

也许花点时间消化一下这些信息！

事实上，你甚至不能将两个集合元素相乘得到任何 $p$ 的倍数（$k \cdot p$ 形式的数）。这些是唯一在应用模运算后会得到 $0$ 的数字：

换句话说，我们将两个集合元素相乘永远得不到零！这意味着模 $p$ 的整数，当剥离掉零元素时，只对乘法封闭——它们构成一个乘法群！

我说哦-哦

另外值得一提的是，如果我们再次包含零（$\mathbb{Z}_p$），乘法就会出现问题。零将没有定义明确的乘法逆元。也就是说，你不能撤销乘以 $0$ 的操作，因为 $0 \times \text{任何数} = 0$！

这使得该集合不能成为群！

事实上，这种版本的整数被称为模 $p$ 整数的乘法群。它因多种原因而极其有用，并且它也再简单不过了。

下一个，虽然非常有名，却隐藏了更多的复杂性。

椭圆曲线

在密码学中，另一个极其重要的群是椭圆曲线所产生的群。你知道的，就是这些家伙：

噢，你好！

我们上面看到的是一条满足以下表达式的曲线：

$$ y^2 = x^3 + ax + b $$

自然，人们不禁要问，到底该如何用它来构建一个群。对于这个问题，我可以提供两种答案：简短而实用的一个，只包含我们所需的信息；或者全面而冗长的披露。

由你来决定。

如果你选择留在这篇文章中，我们将只涵盖 ZK 所需的：其基本结构和性质。这是我们的重点，仅此而已。

但如果你想吃红药丸，我也可以向你展示兔子洞有多深！

多么美丽的景象

构建群

这个故事的简单版本实际上相当直接：群元素将是曲线上的点。然而，为了构建这个群，我们需要一个将点相加的机制。

因此，我们将给出曲线上的点相加意味着什么的一个相当牵强的定义。

我想强调的是，这可能感觉有点勉强，因为我们不想在这里探索更深层的理论，但实际上，这个运算是完全有道理的！

相加两点过程如下：

1. 首先，画一条穿过我们尝试相加的两个点（比如说 $P$ 和 $Q$）的直线。
2. 这条直线将在另一个点与曲线相交（因为椭圆曲线的度为 3！）。
3. 将这个点沿 $x$ 轴翻转。由于曲线是对称的，镜像也将落在曲线上。
4. 你就得到了 $R = P + Q$。
5. 搞定！

整个过程看起来是这样的：

当然，有一些特殊情况。例如，你如何将 $P$ 与自身相加？或者你如何将 $P$ 和 $-P$（它的镜像）相加，当穿过它们的垂直线不第三次与曲线相交时？

前一种情况通过在第一步中使用曲线上 $P$ 点的切线来解决。然而，后一种情况需要更多一点的创造力。但我们把那个留到下次再说！

最后，我们必须明白这些曲线不连续。我们刚才看到的图像仅仅是说明性的，因为在密码学中，我们总是需要在离散、精确的世界中操作。因此，我们将在所有构造中使用的“真实”椭圆曲线实际上看起来像这样：

放轻松。如果你选择了实用主义的道路，好消息是，我们不需要太担心椭圆曲线点加法工作原理的细枝末节。

不过，如果你好奇，你可以在这里一窥究竟。

我们只需要知道这些点确实有一个群结构，由我们刚刚定义的运算所诱导。

有了这个概念，我们就可以专注于今天对我们而言重要的内容：群的性质。

性质

说实话，我之前不够精确。一个群要成为群，我们需要的不仅仅是一个集合和一个运算：这两个组成部分需要遵循一套规则（或者具有某些特定性质）。

那么，要使一个群成为群，我们要求它具有一些特殊元素，并且我们也需要运算（我们暂时用 $\oplus$ 表示）以某种方式表现。

我们先来谈谈运算，它有两个简单要求，其中一个你已经知道了：

• 封闭性： 对于群中的任意两个元素 $a$ 和 $b$，将它们组合（$a \oplus b$）的结果也必须在群中。
• 结合律： 我们如何组合顺序运算是无关紧要的。也就是说，$(a \oplus b) \oplus c = a \oplus (b \oplus c)$。

就这样！

噢，不错！

请注意，我们不要求交换律（$a \cdot b = b \cdot a$）成立。如果交换律也成立的群被称为 阿贝尔群。

我们还需要讨论的另一件事是群元素的几个要求，它们同样相当简单：

• 单位元： 必须存在一个特殊元素 $e$，使得对于任意元素 $a$，都有 $a \oplus e = e \oplus a = a$。
• 逆元： 对于每个元素 $a$，都存在另一个元素 $b$，使得 $a \oplus b = b \oplus a = e$（单位元）。

在 $\mathbb{Z}_p^*$ 中这些元素是什么，这很明显。但你能猜到它们在椭圆曲线群中是什么吗？

在使用群时，我们自动获得所有这些保证，这带来了一些有趣的后果。

群生成元

现在，有些群有一个特殊性质：通过选择一个单一元素，并重复地对自身应用群运算，你可以恢复整个群，最终循环回到起点**。

一个以 G 为生成元的小型 4 元素循环群

幸运的是，数学家们在为这些概念选择命名约定方面非常直观：这个“种子”元素（在本例中为 $G$）被称为生成元，它产生一个循环群（由 $G$ 生成）。

为了使符号更简洁，我们通常用 $G^k$ 来表示“对 $G$ 应用 $k$ 次群运算”。

然而，并非群中的每个元素都是生成元。

以 $\mathbb{Z}_7^*$（乘法群）为例，让我们从元素 $G_1 = 3$ 开始。如果你进行计算（记住要应用模运算），你会发现它似乎有效，因为我们得到序列 $3 \to 2 \to 6 \to 4 \to 5 \to 1 \to 3$，所以 $G_1 = 3$ 确实是一个生成元。然而，$G_2 = 2$ 则陷入一个更小的循环中：$2 \to 4 \to 1 \to 2$。

虽然我们无法生成整个群，但我们仍然生成了一些东西：一个更小的群，包含在原始群中。这就是我们所说的循环子群**。

我们也说生成元（以及生成的子群）的阶是我们需要应用运算回到单位元所需的次数。

简单，对吗？

我们可能会被原谅地认为循环群只是架子上的一些花哨的数学定义，但它们实际上是构建密码系统的关键！

离散对数问题

想象我们有一个循环群 $\mathbb{G}$，由某个元素 $G$ 生成，通常表示为：

$$ H = G^k $$

现在，想象我们想要计算 $G^k$。在模 $p$ 的整数群中计算这个值非常简单：我们只需使用标准指数规则。

试想一下：如果你想计算 $G^8$，你首先计算 $G^2$，然后将该值平方得到 $G^4$，然后再次平方得到最终结果！三次运算而不是七次！

对于椭圆曲线群也是如此：存在快速算法（平方-加法式）来应用群运算 $k$ 次。

到目前为止没有问题。但另一个方向呢？如果我们被要求找出群运算被应用了多少次才达到给定结果 $H$ 呢？

$$ k = \log_G H $$

自然地，$k$ 被称为 $H$ 的离散对数。与我们从连续设置中计算对数的经验所预期相反，在这种情况下寻找 $k$ 可能极具挑战性。

这种不对称性的原因在于有限群的跳跃性：由于它们的循环行为，我们不会随着重复应用群运算而得到越来越大的值，而是会在过程中多次循环回到起点。

以 $\mathbb{Z}_7^*$ 为例。$3^2$ 的结果不是 $9$——它实际上是 $2$！

这也意味着寻找离散对数**没有标准方法。在正常情况下，你能做的最好就是试错，并且根据生成元的阶，这可能相对容易，也可能（对于较大的群）极其困难**。

这就是所谓的离散对数问题，简称 DLP。从密码学角度来看，这非常有吸引力，因为我们通常对这种不可能逆转的困难问题感兴趣，以保护敏感信息。

以至于，现代密码学的大部分都建立在这个问题的困难性上。几种密钥交换、签名和加密技术都依赖于这一单一假设！

循环子群和 DLP 无疑非常重要，但我们需要关注一种特殊的类型的循环群，因为它对 ZK 系统至关重要。

没有这些特殊元素，许多算法和协议将无法工作。

或者至少，它们不会快，那也会使它们不切实际。

让我们来谈谈它们。

单位根

这是原始定义：一个n 次单位根是这样一个元素 $\omega$，当你应用群运算 n 次时，你会回到单位元：

$$ \omega^n = e $$

为了完全透明，n 次单位根的概念并非群所独有。

以复数为例！它们是一个完备域，然而虚数单位 $i$ 是一个4 次单位根！

单位根的任何整数幂也都是单位根，因为我们可以像这样分解它们：

$$ (\omega^k)^n = (\omega^n)^k = e^k = e $$

有些 n 次单位根很特殊，它们可以生成所有其他 n 次单位根。这些被称为本原 n 次单位根！

有趣的是，单位根也存在于有限域中。你可能已经从我们迄今为止经历的一切中发现了这一点，但是当我们剥离元素 0 时，每个（素数）有限域都成为一个乘法群。这样的群具有生成元，甚至可能具有循环子群——即素数域的单位根！

好吧……然后呢？老兄，这故事很酷，但单位根有什么用呢？

你又来了，那些奇怪的定义……

一个原因：快速傅里叶变换，简称 FFT。

我们现在不会深入细节，但没有 FFT，我们将要探索的技术大部分都将无用。巧合的是，FFT 利用单位根的特殊结构**，为我们提供了一种非常快速的多项式插值方法**！

群等价性

在我们结束之前，我还有一个微小细节想提一下。这只是一个小技巧，我们将来可能需要利用它来让我们的生活更轻松。

正如我们已经说过的，每个群都配备了其二元运算。这种运算的性质可能截然不同：有时，它像加法和乘法一样简单，但也有更复杂的例子，比如我们看到的椭圆曲线的运算。

甚至还有更抽象的例子，比如用来模拟魔方的群的群运算。

使用这种运算可能会使某些证明的数学处理相当繁琐。

然而，你可能已经注意到，我们今天的重点不在于具体细节，而在于群的普遍性质。我甚至建议我们使用指数记法 $G^k$，即使我们处理的不是乘法群。这并非巧合，真的：这里有更深层的原因。

原因在于，即使两个群表面上看完全不同，它们的行为完全相同。

例如，考虑在模 $2$ 加法下的 ${0, 1}$，以及在模 $3$ 乘法下的 ${1, 2}$。它们显然有不同的元素和不同的运算。

但现在，将 $0 \to 1$ 和 $1 \to 2$ 映射。突然间，第一个群中的每个运算在第二个群中都有一个完美匹配：$0 + 0 = 0$ 对应于 $1 \times 1 = 1$， $0 + 1 = 1$ 对应于 $1 \times 2 = 2$， $1 + 1 = 0$ 对应于 $2 \times 2 = 1$。

它们是同一个群，只是标签不同！

事实上，两个群可以共享相同的结构。不深入细节地说，这意味着我们可以找到从第一个群中的元素到第二个群中的元素之间的一一对应（一个双射），并且群运算在两个群上基本表现完全相同。

当这种情况发生时，我们说这些群是同构的。

同构实际上是同态的受限版本，它只要求运算行为相同，而不要求一一对应！

因此，当面对一个具有复杂运算的群时，我们可以做一件非常巧妙的事情来简化其处理：找到一个方便的同构。

在这里，我将简单地提出几个事实，让我们的生活更轻松。首先：

每个 n 阶循环群都与模 $n$ 整数的加法群同构。

从某种意义上说，这只是在说任何循环群的元素都始终存在一个自然排序！

其次，对于任何循环群，我们总能找到一个与它同构的乘法群。然而，这种构造不如加法情况那样简洁：我们需要查看精心选择的域中的乘法群，或者考虑子群。但重点是，这样的群始终存在！

这听起来可能只是一个简单的技术细节，但这确实是我们始终可以使用指数记法的原因：因为我们总是可以利用该同构到一个简单的乘法群。

这多酷啊？

总结

好了，一篇文章的内容可能已经足够多了！

群是现代密码学的数学支柱。

不过，随着后量子密码学的出现，这种情况可能很快就会改变。

它们的结构支撑着大量技术的安全性，我们也提到了它们如何实现一些关键优化，因为它们是 FFT 的先决条件。

至此，我们即将完成所需的基础概念。虽然我们仍然缺少几个概念（说的就是你，配对），但大部分都已涵盖。

剩下的就是开始用我们的新工具构建更复杂的工具和技术，随着我们进入更复杂的协议，并更接近 ZK 领域。

那么，别浪费时间了！下一期，我们将讨论承诺方案，我们将看到如何用群构建有趣的东西。

下次见！

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