ZK编年史：内积论证

上次，我们构建了第一个完整的 polynomial commitment scheme。

它属于那种机制，至少对我来说，极其优雅，几乎有一种魔法般的感觉。我的意思是，天哪，你只需要一个 单个 group element 来 commit，一个 单个 group element 来证明 opening，然后用一个简洁的 pairing 等式把一切串联起来。

它展示了 pairings 的力量，利用代数变换的能力，让所有部分都完美契合。

我们会继续在这些能力之上构建——但现在，我想先说明一点：KZG 并不是实现 polynomial commitments 的唯一方式。

到目前为止，我们都是通过“在一个隐藏点上做 evaluation”的视角来处理这个问题的。但如果我告诉你，我们可以采用一种完全不同的视角呢？

如果我告诉你……

今天，我们将处理的是 vectors，而不是 polynomials。虽然这听起来令人困惑，但事后看来也不至于太离谱：毕竟我们已经用 Pedersen commitments 讲过 vector commitments。只不过这次我们会看另一种策略——可以说是一种更有针对性的策略——而且一旦我们开始深入，它就会更容易解释为什么我们一开始就会对探索其他选项感兴趣。

我们将进入一种新的机制，名为 inner product arguments。它的组成要素，至少在原则上，是相当不同的，但结果同样强大。

所以，为了开始，让我们先看看这些组成要素！

The Inner Product

如果我的记忆没错的话，这应该是本系列中我第一次提到 inner products，所以唯一合理的起点就是它们的定义。

给定两个 vectors a 和 b（我们会用粗体表示 vectors），它们的 inner product 或 dot product 定义为 a 和 b 的按分量乘积之和。如果这听起来有点绕，那么把它写清楚或许会更有帮助——因此，对于长度为 n 的 vectors，我们得到：

尽管表面上很简单，inner products 在很多方面都极其有用。

例如，它们提供了一种衡量 vectors 之间共线性的方式。inner product 为 0 意味着这些 vectors 完全正交。

不过在我们的场景里，我们关心的是 verifiable computing 这一面，所以 inner products 必须承担某种与 证明语句 相关的作用。事实上，我们可以围绕它们构建一种非常不错的机制。

Inner Product Arguments

核心思想最好通过一个简单例子来展示。假设我们有一个秘密 vector a 和一个公开 vector b，并且我们已经使用类似 Pedersen commitment 的 vector commitment scheme 对 a 做了 commit。

在此基础上，我们声称：

作为 prover，我们如何在不透露 a 的情况下，让 verifier 相信这个主张是真的？

这就是 inner product argument（或 IPA）的本质：它允许 prover 说服 verifier，一个已 commit 的 vector 满足某个特定的 线性关系，同时 保持该 vector 隐藏。由于 a 从未被揭示，IPA 必须把对 a 的 commitment 纳入其中，这样 prover 就会受到 a 的值的约束。

在上面的陈述里，我偷偷带入了两个很重要的点：IPA 应该既是 hiding 的（vector 保持隐藏），又是 binding 的（proof 应该只对 a 有效）。而我们现在很清楚，这些都是 commitment schemes 的特征……那问题出在哪里？

嗯，准确来说，IPA 实际上更像是一种 proving 或 argument system，而不是 commitment scheme，正如我们很快会看到的那样。不过，我们可以与 polynomial commitment schemes 建立一个很漂亮而简单的联系——这种联系如此紧密，以至于 IPA 实际上可以被用作 PCS（以及其他用途！）。

秘密就藏在一个有点意想不到的联系中：inner products 与 polynomial evaluations 密切相关。

啥？

你可能会想，这是怎么回事？好吧，当我们有一个次数为 n 的 polynomial Q(X) 时，我们可以把它的 coefficients 写成一个 vector q = (q₀, q₁, q₂, …, qₙ)。我们还可以取某个值 z，并把它的所有幂写成一个 vector，于是得到 z = (1, z, z², …, zⁿ)。现在……如果我们对这些 vectors 取 inner product，会发生什么？

啊哈！我们刚刚发现了一种将 polynomial evaluation 写成 inner product 的替代方式——这意味着我们可以用 IPA 来证明 polynomial evaluations 的正确性！

好了！说完这些，现在我们更清楚自己在处理什么了，是时候动手看看这类 arguments 是如何实际工作的了。

准备好——会有点乱！

Bulletproofs

也许最著名的 inner product argument 的实现出现在 Bulletproofs 中。

不对！

它推广了一种 特别优雅 的 IPA，能把一个 inner product 主张压缩成一个对数大小的 proof，这真的很棒。而且它是以一种 透明的 方式做到这一点的，不需要 trusted setup。

在开始之前，我想先立刻澄清一件事。Bulletproofs 的主要用途之一是 range proofs：证明某个数属于从 0 到另一个整数 k 的给定范围内。

事实上，这正是我 第一次写这个主题 时对它们的表述方式！

但实际上，它们使用的核心构造可以应用于 任何 inner product。只是 range proof 的一个主要组成部分恰好是 inner product，所以这个构造天然就适合那个用途！

所以这一次，我更想聚焦于通用技术，而不是某个特定用例。

只要记住，这种类型的 argument system 可能在多种场景下都有用。

说完这些，让我们进入正题！

Notation

我们仍然会处理一个由 field elements 组成的秘密 vector u。不过，这次故事开始的方式稍有不同：让我们假设，我们已经通过一个 Pedersen commitment 对这个 vector 做了 commit：

使用的是某个 group ? 的 generators vector g。

从表面上看，这并不像 inner product。但这里我们可以做一个很好的变换：一个 isomorphism！如果我们把 ? 看作加法群而不是乘法群，并且为了方便省略 blinding factor，我们会得到类似这样的形式：

而这……几乎就像一个 inner product！唯一的问题是，它一边是 field elements，另一边是 group elements。所以在这里，我们会稍微滥用一下 notation，仍然把 Pedersen commitment 写成：

为了简化讨论，我们这里只是省略了 blinding factor，但请记住，在完整构造中它应该被考虑进去！

The Core Construction

好，随着 notation 上这一点小变化，这个 IPA 的目标就非常容易表述了：prover 想要证明自己知道一个 vector u，使得 commitment c ᵤ 的构造是正确的，同时还满足某个特定的 inner product 关系。

为了让事情运作起来，我们需要动用一个在本系列中一次又一次用到的资源：recursion！

核心思想是，prover 会试图说服 verifier：初始主张与一个 更小的主张（这里是 一半大小）相关，并且这种主张与原始主张具有 相同的形式。我们把这叫作 folding。

也就是字面意义上的 把主张折半，并伴随一些 verifier 的参与，以确保这个折叠是诚实的。

我们所做的就是重复这个过程，直到达到一个可以直接检查的条件——基本就是这样！

然而（而且非常重要），我们必须让这个 argument 是 sound 的，也就是说，prover 几乎不可能作弊。为了强制这一点，我们做的是到目前为止在所有 proving systems 中一直在做的事情：请求 verifier challenges。通过在 folding 过程中直接使用这些挑战，我们把 prover 绑定到这种不可预测性上，而这正是防止 proof 伪造的关键。

具体做法如下：首先，prover 将 u 和 g 都整齐地拆成两半：

为了简化起见，我们假设 vectors 的长度是 2 的幂，这样在递归步骤中我们总能把它们对半拆分。

这意味着我们也可以直接通过以下方式把原始 inner product 拆开：

他们还会计算一对 cross-terms，这些项的作用正是今天这个构造的核心：verifier 在验证时需要它们，以便自己重建一些内容。

现在先相信我——没有这些 cross-terms，就不会有 Bulletproofs！

从这一点开始，prover 和 verifier 之间会进行一个小小的 interactive protocol。首先，prover 会发送 cross-term 的值（它们是 group elements）。请记住，verifier 不知道 u，所以他们不可能自己算出这些值。

verifier 会回应一个挑战 α ∈ ?ₚ。接下来有趣的部分来了：prover 会利用这个挑战来更新他们的 vector u，而 verifier 可以同时更新 commitment c ᵤ，使其 匹配更新后的 vector。

我们说他们是以 homomorphically 的方式完成这个更新的。

对……说起来容易做起来难。我的意思是，vector 的更新本身相当直接，尽管一开始并不容易立刻看出 为什么 我们会选择这种特定形式，它看起来像这样：

但 commitment 到底要怎么更新呢？verifier 又不能把它拆成两半之类的……

让我们一步一步来。我们需要的是一种方式，让 verifier 能够把他们对 u 和 g 的 commitment 更新为这对新 vectors u’ 和 g’。所以让我们借助 inner products 的 线性性 来看看这会是什么样子：

我们可以再次利用线性性，把这些 α 移到 inner products 的外面：

咦？那是什么？就像魔法一样，我们之前计算的 cross terms 似乎出现了！经过最后一些重排，我们得到了最终整洁的形式：

Et voilà！借助 cross terms，verifier 就能够自行得到对折叠后 vector 的 commitment！

这里有一个微妙但重要的细节：verifier 也可以自己折叠 g，因为 g 是公开的。这对最终验证至关重要。

而且信不信由你，这基本就是全部内容了！一旦我们能够把一个主张缩减到一半大小，就可以继续用新的挑战递归地这样做，直到把原始 vector u 折叠成一个单独的 field element u *。verifier 的最终检查就是：

如果这一步通过，那么我们就可以非常有信心地说，prover 知道原始 vector u！

Public Coins

到这里，我们需要形式化一个我们一直在使用、但还没有明确说出名字的概念：public randomness。

注意，折叠后 commitment 的推导包含了 α。这个值是公开的，但它是在 恰到好处 的时间点被选择出来的，以防止 prover 作弊。也就是说，除非 prover 事先知道 α，否则他们没有办法影响这个推导结果。

如果你还记得我们在 sum-check protocol 中的 soundness analysis 里提到的内容，这一点极不可能发生。实际上，这是一种在进入下一步之前，先把上一步结果 锁定 住的方法。

这种随机挑战的使用对于 interactive protocols 的 soundness analysis 如此核心，以至于它们得到了一个特殊名字：public coins.-,Public%20coin%20protocol%20versus%20private%20coin%20protocol,-%5Bedit%5D)。当然，我们把使用这种策略的 protocols 称为 public-coin protocols。

与 private-coin protocols 相对，在后者中，随机选择不会公开。

Public-coin protocols 提供了很强的 soundness 保证，而且在此基础上，它们在概念上也非常清晰：protocol 的 整个 transcript 由 prover 发送的消息和公开的 verifier challenges 共同决定。没有任何隐藏的把戏。

更进一步，因为所有随机性都是公开的，我们可以使用 Fiat-Shamir transform 来完全去掉交互！

所以这就是 Bulletproofs 的本质！folding 的想法给了我们一种简洁的 argument system，它不需要 trusted setup，并且运行在 log₂(n) 轮中。

请记住，我们为了更简单的数学处理省略了 blinding factor，但完整构造中应该把它包含进去，这样 commitment 才是 hiding 的！

我们本可以就此结束这个故事。然而，我不希望你们读完这篇文章后留下这样的印象：Bulletproofs 是唯一可用的 IPA，而且我们要么用这种 IPA，要么用 KZG 来处理 polynomial evaluations。

外面还有很多其他方案。所以为了让你们稍微窥见一点，我想简要谈谈另一种技术，它在某种程度上位于我们到目前为止讨论过的这些技术之间。

Dory

我们将看 Dory，一种稍微现代一些的 PCS，它也依赖 pairings，但用途与 KZG 不同。因为 Dory 从本质上说就是一个 inner product argument！

不过，它的性质与 Bulletproofs 非常不同，因为它处理 inner products 的方式完全不同。

Inner Pairing Products

它使用 pairings！

没错！Dory 并不使用类似 Pedersen 的 commitments，而是依赖于基于 pairing 的 commitments。它通过利用所谓的 inner pairing product（或 IPP）来做到这一点，我们接下来就会看到。

这个设定与 KZG 类似：我们需要三个 prime order 为 p 的 groups ?₁、?₂ 和 ?ₜ，一个它们之间的 pairing e，以及一个 field ?ₚ。

有了这些，我们可以定义：

为什么这样定义？嗯，注意这里 a 和 b 是 group elements 的 vectors，而不是 field elements。因此，我们不能使用标准的 inner product（也不能用我们在 Bulletproofs 中用过的稍作修改的那个），因为没有办法把 两个不同群中的元素乘在一起。

但我们可以借助 pairing 实现类似的效果！

这样做的好处是，它的行为 完全像 inner product：它具有相同的线性性质，这都要归功于 pairings 的 bilinearity！

在同构意义下，我们甚至可以把 IPP 表示成一个和，而不是乘积！只是我们这里假设 ?ₜ 是一个乘法群。

所以接下来，我们还是会稍微滥用一下 notation，直接写表达式 ⟨ a, b⟩ 来表示 IPP( a, b)。

现在，Dory 并不是给 Bulletproofs 简单加上 pairing 的强化版而已。它确实建立在 inner product 范式之上，也确实依赖 recursion，但在 压缩的是什么 以及 如何压缩 方面，有一个根本性的变化。

说到这里就更清楚了：对某个 vector u 的 commitment，现在是用一个 commitment key g 来计算，而这个 g 不再是公开的：

这才是真正的关键区别。由于 g 不是公开的，verifier 不能自己折叠它，因此 Bulletproofs 风格的 folding 过程就无法应用。换句话说，在 Bulletproofs 中定义 commitment 的那个对象是 公开的 且 可折叠的。而在这里，它是 commitment 结构本身的一部分！

注意，在 Bulletproofs 中，commitment 的 hiding 属性是通过显式的 blinding factor r 赋予的。这里，我们不需要这样的因子。

相反，hiding 源自 commitment key g 的结构以及 pairing group 上的底层困难性假设。不过这里我们不必纠结细节。重要的是要知道，这仍然是 hiding 的，只是原因不同！

“但是 Frank”——你可能会想——“如果 g 不是公开的，我们怎么证明任何关于这个 commitment 的东西呢？”这正是正确的问题！这也是 Dory 的关键结构差异：我们必须执行一个 transparent setup step，才能让这一切运转起来！

The Transparent Setup

为了理解这会如何工作，让我们一起走过几轮 folding。

这一轮会与 Bulletproofs 类似地进行：prover 将 vector u 和 commitment key g 分开，把 cross terms 发送给 verifier，而 verifier 回复一个挑战 α₁。然后 prover 按常规把 u 和 g 都折叠成 u’ 和 g’，verifier 则折叠 commitment c ᵤ。

到目前为止，这看起来很熟悉。然而，有个问题：verifier 无法折叠 g，因为他们根本 不知道它！

不过别慌：隧道尽头是有光的。我们只需要一些 pre-processing！

解决这个问题的方法是，同样走一遍 IPA，但对象是 commitment key。我知道这听起来很有挑战性，但实际上非常简单。

为此，prover 选择一个由随机 group elements 组成的 vector，我们称之为 Γ，它的长度需要是 g 的一半。然后，prover 将 g 分成左半部分和右半部分，并分别计算一对对应每一半的 IPP commitments：

为什么？因为这些现在可以 与 verifier 共享，而 verifier 可以用它们来计算对 g’ 的 commitment：

让我们花一点时间欣赏一下刚才发生了什么：verifier 这一轮开始时只有一个 commitment，形式上是一个 inner product equality，最后却得到了 两个 inner products：

这里有一个小细节：g 最初是 ?₂ 元素的 vector，但在这里，它被当作 ?₁ 元素的 vector 来处理。

严格来说，这一步假设存在一个 symmetric pairing。否则，我们必须跟踪每个 vector 分别属于哪个群！

那么接下来怎么办？好吧，我们证明这两个 commitments 的 openings 都是已知的！也就是说，我们可以完全沿用刚才的 folding 策略，对 两个 commitments 并行 进行同样的处理！

为了简洁起见，我们只概述一下接下来如何继续。如果再进行一轮，prover 就需要发送与一个新的 commitment key Γ’ 相关的新预计算 Δ’ 值，而这个 commitment key 的长度是 Γ 的一半。反过来，这会为 prover 需要检查的内容再增加 另一个 inner product。

目标很简单，尽管路径并不简单：通过在每一轮都对 commitment key 本身进行 commit，verifier 就可以与 prover 的 folding 保持同步。他们只需一路跟踪对 commitments 的 commitments，直到最后！

这个过程会一直继续，直到 u 被折叠成一个 单独的值 u*，此时 prover 可以发送 g*、u*，以及 所有折叠过的中间 commitment keys Γ。

最后，verifier 检查 log₂(n) 个乘积等式，如果它们都通过，那么就接受 proof！

那么 pre-processing 在哪里呢？就在于选择所有的 Γ vectors，以及计算所有的 Δ values！这些都可以 提前 算好，所以 prover 可以针对每个 inner product 做一次，并在发送任何 challenge 之前把它们发给 verifier！

把这一点转换成 polynomial commitment scheme 还需要多做一点工作，但我们现在不必担心这个。

再说，Dory 还有更多细节要讲，那会让我们分心很多。仅仅这些核心思想，就足够让我们继续深入 ZK 领域了！

Summary

哦天哪。这次确实够硬核。

不是吗？你真这么觉得？

这些事情根本没法粉饰。数学很复杂，而且还会继续复杂下去。

抱歉！

对我来说，更重要的是关注更大的图景，并围绕构成 verifiable computing 的核心思想建立直觉。

在这方面，今天非常有启发性，因为我们在一个非常重要的技术家族——IPAs——的背景下探索了 folding 的概念。我们也看到了，它们远不只是思考 polynomial commitments 的另一种方式：它们更像是 proving systems 的一种 设计模式。

有一个微妙而关键的方面，我们只是隐含地提到过：这些 arguments 是 zero knowledge 吗？

在 Bulletproofs 中，prover 说服 verifier，相信一个 inner product 关系成立，同时似乎没有泄露任何关于隐藏 vector 的信息。

这不是偶然，但也并不是自动显而易见的。所以，我们该如何量化这一点？

因此，在下一篇文章中，我们会从具体构造中暂时抽离出来，最终聚焦于我们整个探索的核心属性：zero knowledge。

因为高效地证明某件事，只是故事的一半！

希望你已经对下一篇充满期待了！到时候见！

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