零知识纪事：Sigma协议

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

当我们首次介绍我们的承诺方案时，我们不得不指出，即使它们潜力巨大，它们也不是证明系统。尽管如此，它们之间确实感觉有着密切的联系。

我们很快就会发现，它们的算术特性是开发一套新证明机制的关键，这些机制再次通过证明者和验证者之间巧妙的交互精心制作而成。

交互式证明的概念应该已经很熟悉了。我们甚至在第一次接触时就提到过。

因此，在花费了大量文章进行准备之后，我们将再次把注意力转向构建证明系统。在此过程中，我们将揭示一些新的核心概念，这将使我们更接近我们所追求的零知识。

这将是一篇很长的文章。请坐稳，泡杯咖啡，让我们深入探讨！

Sigma 协议

不，不是那种 Sigma

今天我们不会只看一个协议，而是要看一系列协议，被称为 Sigma 协议。

或者简称 Σ-协议！

从概念上讲，它们非常简单，因为它们由三个主要阶段定义：

• 承诺：证明者发送一个初始消息。
• 挑战：验证者发送一个随机挑战，证明者必须无法预测该挑战。
• 响应：证明者以某种方式响应挑战，从而能够证明关于某个声明的一些事情。

承诺-挑战-响应与“sigma”这个名字的词源密切相关。不过，我听过至少两种说法。

一种说法是，这种来回的模式类似于希腊字母 sigma (Σ)。确实如此！简单明了。

另一种说法则稍微复杂一些，即“sig”部分来自消息的之字形运动，而“ma”来自 Merlin-Arthur，这是指定证明者 (Merlin) 和验证者 (Arthur) 的通用约定。

我让你决定你更喜欢哪个故事！

这种模式听起来应该非常熟悉：它与我们定义 sum-check协议 和更复杂的 GKR协议 时使用的交互类型相同。

那些协议本身非常有趣，当然，在合适的语境下也是如此。同样，Sigma协议也有其专业领域：它们用于证明对秘密值的了解。

这听起来有点零知识的味道，不是吗？

我们马上就会通过最著名的例子看到它的实际应用。

Schnorr 协议

我们最初的目标将尽可能简单：我们将尝试证明对单个秘密整数 $x$ 的了解。

不多不少！我们稍后再考虑为什么。

那么，我们该如何着手呢？我们已经有了一套相当大的基本工具，所以也许我们可以从检查我们拥有的东西开始！

回顾我们对群的简要介绍，我们知道一种隐藏值的简单方法是将其埋藏在离散对数之下。换句话说，当我们计算：

$$g^x = y$$

我们知道从 $y$ 恢复 $x$ 是不可行的（请记住，这是对 $g$ 应用群操作 $x$ 次的符号表示）。

所以，想法是这样的：如果我们能以某种方式说服验证者我们知道群元素 $y$ 的离散对数，那么我们就证明了对 $x$ 的了解！

这正是 Schnorr协议 背后的概念。为了不拖延太久，它的过程如下：

• 首先，双方（证明者和验证者）就一个大小为 $n$ 的群 $\mathbb{G}$ 和一个生成元 $g$ 达成一致。值 $y$ 实际上可以公开。
• 然后，在第一轮中，证明者通过计算并发送：

$$t = g^r$$

来**承诺**某个随机性 $r$。

• 收到此值后，验证者抽取一个随机挑战 $e$，并将其发送回给证明者。

$$e \leftarrow \mathbb{Z}_n$$

• 证明者然后计算 $z$，并将其发送给验证者：

$$z = r + xe \pmod{n}$$

• 最后，验证者执行以下小检查：

$$g^z = t \cdot y^e$$

注意这与 Pedersen承诺!是多么相似。

如果检查通过，验证者就接受证明。直观地看：

很简单，对吧？

我想提供一个直观的例子来说明这在实践中是如何进行的。想象一下，你，验证者，是色盲。在你面前，有两颗球。一个证明者声称这两颗球颜色不同，但你就是看不出来！

于是，你们同意玩这个游戏：你首先选择一颗球，并指向它让证明者看到。然后，证明者转过身去，你可以选择交换球的位置，或者保持它们不动。这就是你的挑战。

最后，证明者转过身来，指向你最初选择的那颗球。更重要的是，你可以一直玩这个游戏，如果证明者每次都猜对，那么他们很可能真的能看到不同的颜色！

我们首先要证明这个协议是完备的，也就是说，当验证者是诚实的时候它能正常工作。这很容易证明：

$$g^z = g^{r+xe} = g^r \cdot g^{xe} = g^r \cdot (g^x)^e = t \cdot y^e$$

mod n 可以安全地忽略，因为我们处理的是大小为 $n$ 的循环群，所以我们保证每 $n$ 步会得到单位元。

为了更明确，假设 $z \pmod n = h$。那么，我们知道 $z = h + k \cdot n$，对于某个整数 $k$。代入后，我们得到：$g^z = g^h \cdot g^{kn} = g^h$。也就是说，我们可以完全忽略模运算！

太棒了！这两个值将匹配，因此算法是完备的。事实上，它是完美完备的：验证者将总是接受一个有效的记录 $(t, e, z)$。

接下来，我们需要看看健全性。

健全性

正如我们所知，健全性 要求我们证明一个欺骗性证明者不能轻易欺骗验证者。

这里事情变得有趣起来，因为对于这个协议，健全性论证有两种风味。我们有更标准的演示，然后是一个具有一些很酷含义的更强条件。

让我们从直接方法开始：一个欺骗性证明者在不实际知道 $x$ 的情况下说服验证者他们知道 $x$ 会有多难？要回答这个问题，我们注意到要通过验证，他们需要找到一对值 $(t, z)$，使得验证通过。

首先，我们考虑证明者提前知道挑战 $c$ 的情况。在这种情况下，作弊实际上相当容易：你只需选择任何 $z$，然后计算 $t$ 为：

$$t = g^z \cdot y^{-e}$$

再一次，请记住这个指数符号表示群运算。第二个项 $y^{-e}$ 是 $y^e$ 在对应群中的逆元。这意味着，例如，对于椭圆曲线群，这些点是关于 x 轴对称的！

但由于 $e$ 是在承诺随机性 $r$ 之后发送的，他们只有两种选择：事先猜测 $c$，或者在知道 $e$ 后猜测 $x$。

这两个数字几乎可以是 $\mathbb{Z}_n$ 中的任何可能值，并且由于离散对数问题，欺骗性证明者没有比猜测更好的选择了。如果 $n$ 很大，正确猜测 $e$ 或 $x$ 的机会变得极其小（约 $1/n$），因此，作弊的机会实际上可以忽略不计！

这足以满足健全性。但是，我们还有第二种健全性要探索！

特殊健全性

我们之前提到的一件事实际上有一个很好的结果。我们知道一个欺骗性证明者几乎不可能猜到验证者对 $e$ 的选择，对吗？如果猜测单个 $e$ 值很难，那么猜测两个独立的 $e$ 选择（比如说，$e$ 和 $e'$) 的可能性要小得多，非常小！

所以，假设我们对相同的随机性运行这个 Schnorr 协议两次，产生两个接受的记录 $(t, e, z)$ 和 $(t, e', z')$。我们的直觉告诉我们，因为证明者正确地响应了两个挑战，他们一定知道 $x$ —— 因为他们正确预测 $e$ 和 $e'$ 的可能性极小。

我们实际上可以证明这一点：如果我们可以从两个记录中提取（或恢复）$x$，这意味着证明者知道 $x$！

策略如下：由于有两个接受的记录，我们有：

$$\begin{aligned} g^z &= t \cdot y^e \ g^{z'} &= t \cdot y^{e'} \end{aligned}$$

让我们用第一个方程除以第二个。这转化为指数相减，我们知道如何处理：

$$g^z / g^{z'} = (t \cdot y^e) / (t \cdot y^{e'}) \implies g^{z-z'} = y^{e-e'}$$

看看那个！这个方程的第一个和最后一个成员有相同的生成元，这意味着指数必须相等！

或者至少是 模 $n$ 同余！

剩下要做的就是解 $x$：

$$g^{z-z'} = (g^x)^{e-e'} \implies g^{z-z'} = g^{x(e-e')} \implies z-z' = x(e-e') \pmod{n} \implies x = (z-z')(e-e')^{-1} \pmod{n}$$

然后砰！我们成功提取了秘密！

就这么简单！

能够从两个具有相同承诺但不同挑战的接受记录中提取证人的属性有一个名字：它被称为特殊健全性。

这比基本健全性提供了更强的保证，因为它告诉我们，如果证明者能够成功地回答同一承诺的多个不同挑战，他们必须实际知道证人。根本没有办法规避！

对于纯粹主义者来说，有一个小细节：我们要求提取算法在多项式时间内运行。这确保了提取器不仅是理论上的，而且是高效的。

这是零知识吗？

啊，这个价值百万美元的问题！

是的，协议是完备且健全的。但是这个新的特殊健全性可能让我们认为一些信息正在泄露！那是什么呢？

很明显，证明者的响应 $z$ 涉及到秘密 $x$。但是它是否揭示了关于 $x$ 的任何信息呢？

嗯，如果验证者知道随机性 $r$，他们可以简单地计算：

$$x = (z-r)e^{-1} \pmod{n}$$

然而，由于验证者不知道随机性，而我们只是通过巧妙的算术等价来使用它，所以验证者无法这样做！值 $r$ 充当盲化因子，验证者从 $z$ 中学不到任何关于 $x$ 的信息。

至少这是直觉——这应该足以让我们说 Schnorr 协议是零知识的。我们稍后会探讨其形式化，但这确实感觉是一个很好的近似！

重新审视语言

最后，虽然绝对必要，但完备性和健全性只是可验证计算技术工作所需的最低限度要求：它们意味着协议对诚实证明者有效，而 dishonest 证明者将很难尝试作弊。

我们甚至可以把零知识也算进去！

在这里，值得停下来问一个补充问题：一个诚实的证明者拥有什么是一个欺骗者没有的？

答案很明显，至少在这种情况下：他们知道 $x$。但是我们如何让它更精确呢？

当我们谈到计算模型时，我们引入了语言的概念：一组存在有效证人的语句。当时我们没有深入讨论，但 Schnorr 为我们提供了一个完美的借口来演示一个具体例子。

那么，这里的语言是什么？它只是所有存在离散对数的群元素 $y$ 的集合：

$$L = {y \in \mathbb{G} \mid \exists x \in \mathbb{Z}_n \text{ s.t. } g^x = y}$$

在这种情况下，证人简单地就是 $x$ 本身：我们试图证明对其了解而又不泄露的秘密整数。

这可能看起来这只是一个表面上的重构，但实际上它比这强大得多。我们将了解离散对数 $x$ 对于某个值 $y$ 的概念，转化为关于集合成员关系的陈述。也就是说，证明者将说服验证者 $y$ 属于具有离散对数（相对于 $g$）的元素语言，而证人则有点像支持这一主张的凭证。

当然，这样做的全部意义在于验证者永远看不到这样的凭证，但却相信它的存在！

这反过来又让特殊健全性感觉不那么像一个花招，而更像一个形式上的保证：如果一个证明者能够回答同一承诺的两个独立挑战，我们就可以提取他们的证人。而可提取性正是我们说一个证明者知道某事，而不是仅仅走运时的意思。

我们稍后在本系列的更深入探讨中，当讨论另一个密切相关的概念，即知识健全性时，将再次回到这些思想并使其更加精确。它是特殊健全性的一个更普遍的版本，因为它允许证明者和验证者之间进行无限次交互，但其思想是相同的：我们最终能够提取证人，这意味着证明者必须知道它。

目前，牢记这种框架是很好的——当我们想要形式化事物时，语言和证人将不断出现，即使我们不明确谈论它们，它们也存在！

记住我以便更快登录

至此，我们对 Schnorr 协议有了相当全面的介绍。

对于这样一个看似无害的过程来说，这真是一大堆话！

此时，你脑海中可能会浮现一个问题（如果你的大脑还没有被烧坏的话）：我为什么要这么做？证明对单个值的了解到底有什么意义？

我说过我们稍后再担心为什么，我想我不能再拖延了。所以，看：

Schnorr 协议是无数密码协议的基础。

是的！我们可以使用这个小过程作为模板，构建无数其他协议。

为了充分巩固这些证明系统的潜力和多功能性，我想再向你展示几个例子。

另外，我承诺过我们会看到 Pedersen 承诺的实际应用！

Okamoto 协议

在看到 Schnorr 协议的实际应用后，接下来的下一步是证明对 Pedersen 承诺 的打开值的了解。快速回顾一下，它看起来像这样：

$$c = g^v h^r$$

不用说，我们想在不泄露打开值 $(v, r)$ 本身的情况下做到这一点！

这正是 Okamoto 协议所解决的问题。它是 Sigma 协议的另一个经典示例，正如你所料，它与 Schnorr 协议有很多相似之处。

同样，设置并不需要太多精力：我们需要一个群 $\mathbb{G}$，生成元 $g$ 和 $h$，以及承诺 $c$。所有这些都是完全公开的。

证明者的秘密（又称证人）当然是打开值 $(v, r)$。我们按以下步骤进行：

• 证明者选择随机值 $s$ 和 $t$，并计算：

$$t = g^s h^t$$

• 收到此信息后，验证者抽取一个随机挑战 $e$，并将其发送给证明者：

$$e \leftarrow \mathbb{Z}_n$$

• 证明者计算对 $(z, w)$ 并将其发送给验证者：

$$\begin{aligned} z &= s + ve \pmod{n} \ w &= t + re \pmod{n} \end{aligned}$$

• 最后，验证者检查：

$$g^z h^w = t \cdot c^e$$

我邀请你亲自检查完备性和健全性（甚至特殊健全性）！

当你检查完备性时，你实际上会使用 Pedersen 承诺的加法同态特性：对值 $(z, w)$ 的承诺可以通过对单个值的承诺同态地推导出来！

这很酷，因为 Okamoto 协议可以在密码协议中任何时候我们有一个 Pedersen 承诺，并且需要证明我们知道它的打开值而不泄露它时使用。

我们可以对此发挥很大的创意。然而，我希望我们看一个特别的例子，它在我们的探索中会特别有趣。

还有，因为我对此做了一些承诺！

乘法门

没错！上次我们遇到了死胡同，因为与加法门不同，乘法门对 Pedersen 承诺的表现不佳。

我们很快注意到承诺本身不是证明系统。但是现在，有了 Sigma 协议的概念，也许这确实是我们能做到的事情！

不过，这个问题需要稍微不同的框架，所以让我们从那里开始。想象我们有三个值，它们对应于一个乘法门的两个输入和输出。我们的目标是证明这些值满足所述关系，但又不泄露它们。

为了隐藏这些值，我们首先对它们进行承诺，当然，使用我们值得信赖的 Pedersen 承诺方案：

$$\begin{aligned} c_a &= g^a h^{r_a} \ c_b &= g^b h^{r_b} \ c_c &= g^c h^{r_c} \end{aligned}$$

承诺的乘法不再有效，但请记住：我们只需要证明这些值满足关系！所以，我们将使用 Okamoto 协议，再加一点额外的东西。

过程如下：

• 证明者选择五个随机值 $s_1$ 到 $s_5$。对于前四个，他们正常承诺：

$$\begin{aligned} t_1 &= g^{s_1} h^{s_2} \ t_2 &= g^{s_3} h^{s_4} \end{aligned}$$

• 最后一个承诺略有不同：我们不使用生成元 $g$，而是将其替换为对 $a$ 的承诺（请暂时相信我，我保证稍后事情会很好地抵消）：

$$t_3 = c_a^{s_5} h^{s_1}$$

• 然后，验证者发送通常的挑战 $e$。
• 证明者计算总共五个响应。前四个非常简单：

$$\begin{aligned} z_1 &= s_1 + a e \pmod{n} \ z_2 &= s_2 + r_a e \pmod{n} \ z_3 &= s_3 + b e \pmod{n} \ z_4 &= s_4 + r_b e \pmod{n} \end{aligned}$$

• 但最后一个有点不同：

$$z_5 = s_5 + (c - ab)e \pmod{n}$$

• 有了这些信息，验证者就可以执行他们的检查了。

那么他们应该执行哪些检查呢？显然，他们可以使用 Okamoto 协议中的完全相同的方法来验证对 $a$ 和 $b$ 的知识：

$$\begin{aligned} g^{z_1} h^{z_2} &= t_1 c_a^e \ g^{z_3} h^{z_4} &= t_2 c_b^e \end{aligned}$$

这里没有什么惊喜。那么我们对 $c$ 能做什么呢？

是这个：

$$c_c^e = t_3 c_a^{z_3} h^{z_4}$$

什么？

深呼吸，冷静。让我们一步一步来。

我们必须通过展开表达式来检查它。从左侧开始，并假设 $c = a \cdot b$：

$$\begin{aligned} c_c^e &= (g^c h^{r_c})^e \ &= g^{ce} h^{r_c e} \ &= g^{abe} h^{r_c e} \end{aligned}$$

现在我们开始把东西组合起来：

$$g^{as_5 + as_3 + abe} h^{r_a s_5 + s_1 + r_a s_3 + r_a be + s_4 + r_b e}$$

就像魔法一样，我们得到了预期的表达式！这到底是什么巫术？

巫术！

这个问题的关键在于一次巧妙的抵消，这得益于我们定义 $z_5$ 的方式。这并非偶然：它与这样一个事实有关，即当 $c = a \cdot b$ 时，我们可以通过一个百年老技巧来处理对 $c$ 的承诺：乘以 $1$，并以一种方便的方式表达这个 $1$。在这里：

$$\begin{aligned} c_c &= g^c h^{r_c} \ &= g^{ab} h^{r_c} \ &= g^{ab} h^{r_c} (g^a h^{r_a})^{-b} (g^a h^{r_a})^b \ &= g^{ab} h^{r_c} c_a^{-b} c_a^b \end{aligned}$$

啊哈！看看最后一个指数！它看起来确实和 $z_5$ 相似。

发生的情况是，我们可以用另一种方式解释对 $c$ 的承诺：将其视为对 $b$ 的承诺，使用生成元 $c_a$ 和 $h$，以及一个非常特定的随机性作为校正项。结合承诺 γ，并通过适当的承诺操作，一切都完美地对齐了。

因此，该方法是完备的。

我将再次跳过健全性演示以保持简洁，但如果你愿意，你可以自己尝试！

简而言之：通过巧妙地重新解释承诺和使用 Sigma 协议，我们可以证明三个隐藏值满足 $c = a \cdot b$ 而不泄露它们。太棒了！

电路

到目前为止，我们已经积累了相当多的工具。我们有一种方法来证明对乘法门打开值的了解，如果你仔细想想，Okamoto 协议的基本形式也可以用于加法门。

尽管 Pedersen 承诺的同态特性应该足以处理这些情况！

嗯……但是如果我们可以处理两种门类型，难道我们不能处理完整的算术电路吗？我们不能同时证明所有门都是正确的吗？

哇

是的！如果我们对每条导线进行承诺，验证者可以轻松地通过加法门（事实上，我们不需要对加法门的输出进行承诺），并且我们可以为每个乘法门使用一个独立的 Sigma 协议。

这是一个崇高的想法……但它有一个明显的问题。随着乘法门数量的增加，这种策略的扩展性很差，这意味着所需的通信步骤也会增加。

或者在应用 Fiat-Shamir 变换 时，证明大小会更大。

然而，并非一切都失去了，因为我们可以通过一个很酷的技巧来缓解这个问题：组合！

组合

将声明组合在一起意味着我们可以同时检查两个或多个打开值。这有两种风味：我们证明对两个语句的知识（AND 组合）或我们证明对任一语句的知识（OR 组合）。

当然，在 OR 组合中，其思想是不揭示我们知道哪个语句！

特别是对于电路，我们需要证明对所有乘法门的所有承诺的知识，所有这些都是一次性的。这正是 AND 组合的想法。那么我们该怎么做呢？

这个技巧出奇地简单：我们不为每个门使用不同的挑战运行独立的协议，而是为所有门使用单个共享挑战 $e$！

具体来说，证明者会发送所有的承诺（每个乘法门的 $\alpha$、$\beta$ 和 $\gamma$），验证者会发送一个挑战 $e$ 作为响应。证明者使用相同的 $e$ 响应所有门，并且验证也在此相同假设下进行。

这样做是完全安全的：一个作弊的证明者仍然必须猜测这个值，所以这和以前一样困难！

因此，我们可以在一个单一的承诺-挑战-响应周期中处理整个电路！

另一方面，OR 组合对我们的目的来说不是很有用。然而，它可能成为 环签名 和匿名凭证等的基础。

一切都很好，直到我们意识到电路可以有非常多的乘法门。

这是一个小细节导致的问题，我之前没有提到：承诺的数量与乘法门的数量呈线性关系。而线性扩展并不是最好的：一个拥有数百万门的电路将需要发送数百万个承诺和域元素。

所以，是的……我们又撞上了一堵墙。

尽管技术上可行，但对于大型电路来说，这种替代方案并不实用。为了生成更易于管理的证明，更高级的系统会应用一些优化。

总结

哦，天哪。内容真多。

写完这些，我的大脑感觉像一团浆糊，所以我想你也很累。但是嘿！我们今天涵盖了很多内容。

Sigma 协议非常有用。它们甚至可以作为更复杂构造的子协议。我承认我以一种有些悲观的方式描述了组合，但它确实是一个很好的工具，特别是当我们处理少量承诺时。

重要的是，我们成功地应用了我们对群的新知识来构建一种新型协议。

你可能会原谅地认为，考虑到群的简单性，我们能用群做的事情不多。但那离真相甚远。

尤其是因为我之前提到的那些优化。我不想剧透，但给你一个小提示，这与我们如何编码电路有关。

与其将电路视为单个门的集合，不如将其重新解释为我们一段时间以来没有谈论过的东西：多项式！

你以为我们已经讲完了吗？哈！

与其检查数百万个单独的约束，验证者可以检查几个多项式恒等式，然后完成整个事情！

高效地处理多项式依赖于一个单一的算法——而这个算法与群息息相关。

因此，在我们继续学习更高级的证明系统之前，我们需要战略性地停下来理解这个机制，它简直是人类有史以来开发的最重要、最优雅的算法之一。

在下一篇文章中加入我，了解它到底是什么！

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