内积参数（IPA）与多项式承诺方案

在这篇博文中，我们将更仔细地研究内部乘积论证（Inner Product Argument）。我们将首先了解这项技术的基础知识，然后将重点转移到 Halo2 证明系统中的变体。具体来说，我们将探讨 Halo2 如何巧妙地将内部乘积论证用作多项式承诺方案。

首先确定一些将在全文中使用的符号。

符号

符号 $\mathbb{F}$ 始终表示阶数为 $p$ 的素数域。给定两个长度相同的 $\mathbb{F}$ 元素向量 $A = (a_1, \dots, a_n)$ 和 $B = (b_1, \dots, b_n)$，则 $A$ 和 $B$ 之间的内积是元素 $a_1b_1 + \dots + a_nb_n \in \mathbb{F}$。它表示为 $\langle A, B \rangle$。

符号 $\mathbb{G}$ 表示阶数为 $p$ 的交换群。我们总是使用加法符号。如果 $A = (a_1, \dots, a_n)$ 是 $\mathbb{F}$ 元素向量，而 $G = (G_1, \dots, G_n)$ 是 $\mathbb{G}$ 元素序列，则 $\langle A, G \rangle$ 表示元素 $a_1G_1 + \dots + a_nG_n \in \mathbb{G}$。

内部乘积论证

为了理解这是怎么回事，让我们直接进入它的描述。这是一种承诺方案，将有一个证明者和一个验证者。该论证有两个部分。

承诺（Commit）：证明者可以通过生成一个用 $P$ 表示的对象来承诺一对向量 $(A, B)$，其中 $A \in \mathbb{F}^n$ 且 $B \in \mathbb{F}^n$。此过程不会揭示 $A$ 或 $B$，但它具有约束力。这意味着任何其他向量都会以高概率产生另一个承诺。通常，证明者将 $P$ 发送给验证者。

打开（Open）：假设验证者已经持有承诺 $P$。“打开”协议是一个交互式协议，其中证明者发送一个值 $c \in \mathbb{F}$，并使验证者确信：

• $P$ 是两个向量 $A$ 和 $B$ 的有效承诺，两者的长度均为 $n$。
• 值 $c$ 是 $A$ 和 $B$ 的内积。

好的，但是为什么？

该方案本身可能看起来没有特别的价值，因为 $A$ 和 $B$ 可以是任何东西。然而，它的重要性在于它作为其他证明系统的构建块。在这些上下文中，会应用额外的检查来对 $A$、$B$ 和 $c$ 强制执行特定的结构，所有这些都取决于公共参数。证明者不是发送 $P$，而是发送其他承诺，以便对 $A$ 和 $B$ 进行结构检查。通过这些承诺，验证者可以有效地重建 $P$。这种方法赋予向量关于所证明语句的某些上下文含义。它们内积等于预定值的要求可以作为证明者了解此事实的证据。

我们接下来将描述的版本是在 Bulletproofs 论文 中提出的。要进一步了解其在算术电路的零知识证明中的应用，请参阅该论文的第 5 节。

设置

“承诺”和“打开”协议都依赖于一些预先计算的值。所需的要素是：

• 一个具有 $p$ 个元素的交换群 $\mathbb{G}$。我们将使用加法符号。
• $\mathbb{G}$ 元素的两个序列 $G = (G_1, \dots, G_n)$ 和 $H = (H_1, \dots, H_n)$。我们可以将这些称为基。

这里的 $n$ 是要承诺的向量的长度。我们始终假设它是 2 的幂。如果不是这种情况，则可以用零填充向量，直到下一个 2 的幂。

承诺

给定向量 $A = (a_1, \dots, a_n)$ 和 $B = (b_1, \dots, b_n)$，则一对 $(A, B)$ 的承诺是：

$$ P := \sum_{i=1}^{n} a_iGi + \sum{i=1}^{n} b_iH_i. $$

打开

“打开”协议有 $\log_2(n)$ 轮。让我们从最简单的例子开始。

情况 $n = 2$。

在这种情况下，$A = (a_1, a_2)$ 且 $B = (b_1, b_2)$。

该协议从验证者在 $\mathbb{G}$ 中选择一个随机元素 $U$ 并将其发送给证明者开始。

证明者计算以下元素并将它们发送给验证者

• $L := a_1G_2 + b_2H_1 + a_1b_2U$ 和
• $R := a_2G_1 + b_1H_2 + a_2b_1U$。

验证者选择一个随机的非零值 $x \in \mathbb{F}$ 并将其发送给证明者，证明者使用它来计算以下元素：

• $a' := a_1x + a_2x^{-1}$
• $b' := b_1x^{-1} + b_2x$

证明者将 $a'$ 和 $b'$ 发送给验证者。最后，验证者检查：

$$ x^2L + P + cU + x^{-2}R = x^{-1}a'G_1 + xa'G_2 + xb'H_1 + x^{-1}b'H_2 + a'b'U $$

当且仅当上述等式成立时，验证者才接受。

完整性思路

为了理解为什么这个等式成立，可以展开两边并检查它们是否具有相同的项。例如，让我们检查一下右侧的第一项：

$$ x^{-1}a'G_1 = x^{-1}(a_1x + a_2x^{-1})G_1 = (a_1 + a_2x^{-2})G_1 = a_1G_1 + x^{-2}a_2G_1 $$

请注意，这如何与 $P = a_1G_1 + a_2G_2 + b_1H_1 + b_2H_2$ 的一部分匹配。另一项出现在 $x^{-2}R = x^{-2}a_2G_1 + x^{-2}b_1H_2 + x^{-2}a_2b_1U$ 中。其余项的行为方式类似。

可靠性思路

在 Bulletproofs 论文中，作者证明，在离散对数假设下，如果证明者可以成功地用 $a'$、$b'$ 响应至少 4 个不同的 $x$ 值，则可以从中提取两个向量 $A$ 和 $B$，使得 $\langle A, B \rangle = c$ 且 $P$ 是一对 $(A, B)$ 的承诺。

因此，如果不存在这样的 $A$ 和 $B$，则最多有 3 个 $x$ 值，证明者知道 $a'$ 和 $b'$，使得验证者的检查通过。但是验证者恰好选择一个随机 $x$，而该 $x$ 是这 3 个选项之一的机会可以忽略不计。

$n = 2^k$ 的一般情况

它是这样一个过程的迭代应用：在每个步骤中，证明者取两个大小为 $2^k$ 的向量 $A$ 和 $B$，并生成两个大小均为 $2^{k-1}$ 的向量 $A'$ 和 $B'$。在后续步骤中，$A'$ 和 $B'$ 取代 $A$ 和 $B$ 的角色并重复，直到 $k = 0$。在每个中间步骤中，基 $G$ 和 $H$ 也会更新以使其长度减半。

在第一次迭代中，$A$ 和 $B$ 是原始向量，最后一步正是已经描述的 $n = 2$ 的基本情况。最后，$A'$ 和 $B'$ 的长度为 1，因此它们只是 $\mathbb{F}$ 的元素。它们是我们上面用 $a'$ 和 $b'$ 表示的元素。

具体来说，第一步如下。

令 $n = 2^k$ 并假设 $k > 1$。否则，我们遵循上面描述的 $n = 2$ 的情况。

写为 $A = (a1, \dots, a{2^k})$，并将 $A$ 的较低部分和较高部分定义为 $A_{lo} := (a1, \dots, a{2^{k-1}})$ 和 $A{hi} := (a{2^{k-1}+1}, \dots, a{2^k})$。对于 $B$、$B{lo}$ 和 $B{hi}$、$G{lo}$、$G{hi}$、$H{lo}$、$H_{hi}$，也是如此。

该协议也从验证者在 $\mathbb{G}$ 中选择一个随机元素 $U$ 并将其发送给证明者开始。这仅发生在第一个回合中。然后，相同的元素 $U$ 将在所有回合中使用。

证明者计算以下向量并将它们发送给验证者

• $L := \langle A{lo}, G{hi} \rangle + \langle B{hi}, H{lo} \rangle + \langle A{lo}, B{hi} \rangle U$，并且
• $R := \langle A{hi}, G{lo} \rangle + \langle B{lo}, H{hi} \rangle + \langle A{hi}, B{lo} \rangle U$。

验证者选择一个随机的非零值 $x \in \mathbb{F}$ 并将其发送给证明者。

此时，下一步开始。证明者计算

• $A' := xA{lo} + x^{-1}A{hi}$，
• $B' := x^{-1}B{lo} + xB{hi}$。

这些将取代 $A$ 和 $B$ 的角色。基的更新方式与 $A$ 和 $B$ 类似。这意味着，在下一步中，将使用以下基来代替 $G$ 和 $H$：

• $G' := x^{-1}G{lo} + xG{hi}$。
• $H' := xH{lo} + x^{-1}H{hi}$。

最后，当且仅当最后一步 ($n = 2$) 的检查成功时，验证者才接受。

多项式承诺方案

有一个受 IPA 协议启发的多项式承诺方案。这在 Halo2 证明系统中使用。

多项式承诺方案有两个部分：

• 承诺：给定一个多项式 $p$，证明者生成一个对于 $p$ 来说是唯一的对象。我们在此用 $[p]$ 表示它，并称其为 $p$ 的承诺。证明者通常将 $[p]$ 发送给验证者。对象 $[p]$ 是一种 $p$ 的哈希。
• 打开：这是证明者和验证者之间的交互式协议。验证者仅持有某个多项式的承诺 $[p]$，并将一个值 $z$ 发送给证明者，他想知道 $p(z)$ 的值。证明者用一个值 $c$ 响应，然后他们参与“打开”协议。结果，验证者确信与承诺 $[p]$ 对应的多项式在 $z$ 处的值为 $c$。

利用 IPA 构建多项式承诺方案的想法主要基于两个观察结果。

• 一个多项式 $p = \sum_{i=0}^{n-1} a_iX^i$ 由其系数向量 $A = (a0, \dots, a{n-1})$ 唯一确定。
• $p$ 在元素 $z$ 处的值恰好是 $p$ 的系数向量 $A$ 和 $z$ 的幂向量 $B$ 之间的内积。更准确地说，如果 $p = \sum_{i=0}^{n-1} a_iX^i$，则

$$ p(z) = \langle A, B \rangle, $$

其中 $A = (a_0, \dots, a_n)$ 且 $B = (1, z, z^2, \dots, z^n)$。

正如我们稍后将看到的，多项式 $p$ 的承诺与 IPA 中 $(A, B)$ 的承诺 $P$ 非常相似。“打开”协议也非常相似。它证明一个值 $c$ 实际上是 $c = \langle A, B \rangle$，顺便说一句，由于 $B$ 的定义，它是 $p(z)$。

与 IPA 的一个主要区别在于，在这种情况下，向量 $B$ 始终为验证者所知。因此，在承诺中与 $B$ 对应的项是不必要的。这使得序列 $H_1, \dots, H_n$ 也是不必要的。证明者没有完全删除那些项，而是添加了一个随机值，但带有另一个目的。它被称为致盲因子，它的作用是为协议添加零知识。

设置

与 IPA 一样，存在一个设置阶段，在其中生成所需的要素：

• 一个具有 $p$ 个元素的交换群 $\mathbb{G}$。与之前一样，我们将使用加法符号。
• $\mathbb{G}$ 的元素序列 $G0, \dots, G{n-1} \in \mathbb{G}$ 和一个元素 $H \in \mathbb{G}$。

承诺

给定一个多项式 $p = \sum_{i=0}^{n-1} a_iX^i$，为了生成它的承诺 $[p]$，证明者选择一个随机值 $r \in \mathbb{F}$ 并计算

$$ [p] := a_0G0 + \dots + a{n-1}G_{n-1} + rH. $$

值 $r$ 称为致盲因子。证明者始终跟踪每个已生成的承诺 $[p]$ 使用了哪些值 $r$。这是因为他稍后将在“打开”协议中使用它们。形式上，我们所描述的是对 $(p, r)$ 对的承诺，我们应该将其写为 $[(p, r)]$。但是为了简化符号，我们省略了对致盲因子 $r$ 的显式提及。

打开

回想一下，我们假设验证者已经持有一个对多项式 $p$ 的承诺 $[p]$，证明者知道该多项式 $p$。证明者也知道他用来生成承诺 $[p]$ 的值 $r$。此外，验证者已经发送了 $\mathbb{F}$ 中的一个元素 $z$，他想知道 $p(z)$ 的值。证明者用一个声称的值 $c$ 响应。接下来是“打开”协议，他们参与该协议来使验证者确信 $c = p(z)$。

情况 $n = 2$

让我们从基本情况开始。与 IPA 一样，这将是所有其他情况都将归结为的基本情况。

当 $n = 2$ 时，多项式 $p$ 的次数最多为 1，即 $p = a_0 + a_1X$。令 $A = (a_0, a_1)$ 和 $B = (1, z)$。定义 $b_0 = 1$ 且 $b_1 = z$。

该交互从验证者在 $\mathbb{G}$ 中选择一个随机元素 $U$ 并将其发送给证明者开始。

证明者选择随机值 $s, s' \in \mathbb{F}$，并使用以下元素响应验证者

• $L := a_0G_1 + sH + a_0b_1U$ 和
• $R := a_1G_0 + s'H + a_1b_0U$。

验证者选择一个随机的非零值 $x \in \mathbb{F}$ 并将其发送给证明者，证明者使用它来计算以下元素。

• $a' := a_0x + a_1x^{-1}$
• $b' := b_0x^{-1} + b_1x$

证明者将 $a'$ 和 $b'$ 连同元素 $r' := sx^2 + r + s'x^{-2}$ 一起发送给验证者。最后，验证者检查：

$$ x^2L + [p] + x^{-2}R + cU = x^{-1}a'G_0 + xa'G_1 + r'H + a'b'U $$

当且仅当上述等式成立时，验证者才接受。

一般情况 $n = 2^k$

这个想法与 IPA 中的相同。这是一个递归参数。

令 $n = 2^k$ 并假设 $k > 1$。如果 $k = 1$，我们遵循上面描述的 $n = 2$ 的情况。

写为 $p = \sum_{i=0}^{n-1} a_iX^i$。与之前一样，定义 $A = (a0, \dots, a{2^{k-1}})$ 和 $B = (1, z, \dots, z^{n-1})$。令 $A$ 的较低部分和较高部分为其第一半和第二半。对于涉及的其余向量也是如此。

该协议也从验证者在 $\mathbb{G}$ 中选择一个随机元素 $U$ 并将其发送给证明者开始。

证明者选择 $\mathbb{F}$ 中的随机元素 $s, s'$。他计算以下向量并将它们发送给验证者

• $L := \langle A{lo}, G{hi} \rangle + sH + \langle A{lo}, B{hi} \rangle U$，并且
• $R := \langle A{hi}, G{lo} \rangle + s'H + \langle A{hi}, B{lo} \rangle U$。

验证者选择一个随机的非零值 $x \in \mathbb{F}$ 并将其发送给证明者。

此时，下一步开始。证明者计算

• $A' := xA{lo} + x^{-1}A{hi}$，
• $B' := x^{-1}B{lo} + xB{hi}$。

这些将取代 $A$ 和 $B$ 的角色。在下一轮中，将使用以下基础来代替 $G$：

• $G' := x^{-1}G{lo} + xG{hi}$。

当且仅当最后一步 ($n = 2$) 的检查成功时，验证者才接受。

未完待续

在后续的博文中，我们将讨论这些协议的复杂性，并且我们将看到如何对它们进行优化并在知识的递归论证中使用它们。

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