匹诺曹虚拟机：接近实用的可验证计算

在 LambdaClass，我们成立了一个小型研究团队，致力于零知识证明和全同态加密。在过去的几周里，他们用 Rust 语言实现了一个虚拟机，实现了 Pinocchio 协议。

你可以在 lambdaclass/pinocchio_lambda_vm 查看该代码仓库。它由 Mauro Toscano、Sergio Chouhy、Agustin Garassino 和 Diego Kingston 构建。

如果你需要一个在分布式系统、机器学习、编译器和密码学等领域合作了十年的工程师和研究人员团队，我们就是你要找的人。想进一步了解吗？通过 calendly 与我们预约会议。

介绍

对于新手来说，zk-SNARKs 协议可能很难理解。其中一个最早的实际实现叫做 Pinocchio，对于任何想要理解它们的人来说，这是一个非常好的起点。Pinocchio 的论文可以在 这里 找到。透彻理解它的主要思想对于理解更新和更复杂的协议非常有价值。

在这篇文章中，我们讨论了其内部工作原理背后的直觉，以及它如何提供电路执行的简洁证明。

我们知道，有时数学看起来比实际情况更复杂和可怕。而且，通常情况下，能够查看一些实际代码可以阐明正在发生的事情。因此，我们为这篇博文创建了一个配套：一个用于学习目的的零依赖 Rust 版 Pinocchio 实现。你可以在 lambdaclass/pinocchio_lambda_vm 找到它。如果你正在寻找此处未涵盖的细节，我们鼓励你去那里看看。

那么，让我们开始吧！

要解决的问题

这里试图解决的问题如下：有人使用一些输入值运行一些代码。她得到了程序的最终结果，并希望说服其他人，这个值实际上是该程序对于给定输入的执行输出。

这个过程的起点是将感兴趣的程序翻译成“算术电路”。在 Pinocchio 的上下文中，这些是有向图，其中节点表示算术运算。我们现在将通过一个例子来看一下。

顺便说一句，我们在这里不讨论如何将程序转换为电路。我们的上下文如下：一个被称为“证明者”的人想要说服其他人，即“验证者”，她执行了一个算术电路并从中得到了一些输出值。让我们看看这究竟意味着什么。

电路执行

在本文中，让我们以论文中的示例电路的一个变体作为一个运行示例。该电路如下：

顶端的小方块代表输入值。选择输入值决定了所有其他门的输出值。执行电路意味着为输入门选择一些值，并填写与乘法门输出相对应的其余值。如果你想知道为什么我们只标记乘法门的输出，这是正常的。答案是：这样做就足够了。我们稍后会回到这一点。

例如，假设我们在 $F_p$ 中工作，其中 $p$ 是某个大素数。以下是电路的两个评估。

这里的输入值是 $2$ 和 $3$。输出是 $30$。唯一的中间值是 $6$。

另一个评估如下：输入值是 $6$ 和 $4$，输出值是 $240$，中间值是 $24$。

满足电路执行实例的等式

让我们将输入值命名为 $c_1, c_2$，输出值命名为 $c_3$，中间值命名为 $c_4$。

这里有一个简单但重要的观察。无论我们选择哪个输入值，得到的值都将满足以下方程组：

$c_1c_2=c_4$

$(c_1+c_2)c_4=c_3$

这里每个乘法门都有一个方程。由于我们没有标记加法门的输出，我们将它们扩展到乘法门的左右操作数中。在本例中，这只发生在第二个方程的左操作数中。

每一组满足这两个等式的 $c_1, c_2, c_3, c_4$ 值都是与程序执行实例对应的值。它们是与输入值为 $c_1$ 和 $c_2$ 的程序执行相对应的唯一值，并且我们得到了 $c_3$ 作为结果。

这些方程测试一组值 $c_1, c_2, c_3, c_4$ 是否对应于一个执行实例。

我们可以将加法门的输出命名为 $c_5$，并得到以下更大的方程组。

$c_1c_2=c_4$

$c_1+c_2=c_5$

$c_5c_4=c_3$

但这是不必要的。这样做的好处是，结果方程组中的每个方程都具有以下形式

$(c_{i1}+\cdots+c{i\alpha})(c{j1}+\cdots+c{j_\beta})=c_k$

请注意，最后一个系统中的第二个方程不是这种形式。拥有所有相同形状的方程对于协议来说非常方便。此外，拥有所有特定形式的方程将非常重要，我们稍后会看到。我们只需为乘法门的输入和输出值赋予变量名，而不是加法门，就可以实现这一点。这种形式的方程组称为 Rank-1 Constraint System (R1CS)。

总结

因此，我们从一个电路开始。通过选择一些输入值并跟踪每个乘法门的输出值，我们获得一个值元组 $(c_1,\dots,c_N)$，这些值满足一个特定形式的方程组，称为 R1CS。此外，该方程组的任何解都对应于电路的某个执行。

执行的朴素证明

在我们的例子中，如果我们想证明我们执行了电路，我们可以展示我们得到的值 $c_1, c_2, c_3, c_4$。然后，验证者可以检查这些方程是否成立，并确保我们使用输入值 $c_1$ 和 $c_2$ 执行了电路，并且我们得到了 $c_3$ 作为结果。这里的问题很明显：验证工作与执行电路的工作相同。这是无用的，因为我们希望将繁重的计算委托给不受信任的服务器，然后获得简洁的执行证明。因此，重做所有工作是不可能的。

QAP 和 Pinocchio 的想法是以更紧凑的形式，即单个多项式恒等式，来表达方程组。这与一些基本的代数结果相结合，将使我们能够给出执行的简洁证明。验证者必须做的工作量始终相同，而与电路的复杂性无关。

Pinocchio 的执行证明思想

正如我们很快将看到的，存在一个非常特殊且依赖于电路的方式，从值 $c_1, c_2, c_3, c_4$ 中构造一个多项式 $p$，该多项式编码了正确的执行。这意味着 $c_1, c_2, c_3, c_4$ 是有效的执行实例值，当且仅当它们关联的多项式 $p$ 满足一个特殊的属性。对于示例电路，此属性是 $p$ 等于 $X(X-1)h$，其中 $h$ 是某个多项式。我们很快就会看到这个属性来自哪里。因此，该协议的思想是，证明者构造多项式 $p$ 并说服验证者存在 $h$ 使得 $p=X(X-1)h$。

该协议将如下所示。

1. 在设置阶段，选择 $F_p$ 中的一个随机点 $s$，并预先计算值 $s(s-1)$。
2. 证明者使用公共输入值 $c_1$ 和 $c_2$ 执行电路并获得 $c_3, c_4$。她从这些值构造多项式 $p$ 并计算 $h$ 使得 $p=X(X-1)h$。她评估 $a=p(s)$ 和 $b=h(s)$ 并将 $a$ 和 $b$ 发送给验证者。
3. 验证者检查 $a=s(s-1)b$。

我们需要解决许多令人不安的事情才能使之起作用。例如：

1. 如何构造 $p$?
2. 为什么只检查 $a=s(s-1)b$ 就足以确信 $p=X(X-1)h$?
3. 验证者如何知道证明者遵循了正确的步骤从电路的执行值构造 $p$?
4. 验证者如何知道 $a$ 和 $b$ 是来自在 $s$ 处评估多项式 $p$ 和 $h$ 的值?
5. 验证者如何知道使用哪些公共输入值来执行电路?
6. 是什么阻止证明者简单地选择 $b=1$ 和 $a=s(s-1)$?
7. 这怎么可能奏效?

为了解决所有这些问题，该协议变得更加复杂。但其本质是上述步骤。其余的部分是为了保证没有人作弊。我们将涵盖所有这些问题，最后，我们将获得实际的 Pinocchio 协议。

对于更复杂的电路，涉及到更复杂的多项式 $p$，条件 $p=X(X-1)h$ 被替换为 $p=X(X-1)(X-2)\cdots(X-k)h$，其中数字 $k$ 取决于电路的乘法门数量。这个想法仍然是一样的。更重要的是，验证者必须执行的检查次数与电路无关！

1. 用于表示正确电路执行的多项式

让我们从展示如何构造多项式 $p$ 开始。

从多项式族到方程组

让我们忘记我们的例子和电路，从玩随机多项式开始。我们取 $v_1$ 为

$v_1=X, v_2=X+1, v_3=X+2$

$w_1$ 为

$w_1=2X+1, w_2=2X+2, w_3=2X+3$

和 $y_1$ 为

$y_1=X, y_2=-X+1, y_3=0$

设 $c_1, c_2, c_3$ 是 $F_p$ 的三个元素。从中，构造以下多项式

$p=(c_1v_1+c_2v_2+c_3v_3)(c_1w_1+c_2w_2+c_3w_3)-(c_1y_1+c_2y_2+c_3y_3)$

我们可以问自己以下问题（似乎与任何事情无关）：哪些值 $c_1, c_2, c_3$ 使得 $p$ 在 $0$ 和 $1$ 处有根？为了弄清楚，我们可以在 $0$ 和 $1$ 处进行评估。更精确地说，$p(0)=0$ 和 $p(1)=0$ 意味着

$0=p(0)=(c_2+2c_3)(c_1+2c_2+3c_3)-c_2$

$0=p(1)=(c_1+2c_2+3c_3)(3c_1+4c_2+5c_3)-c_3$

$c_1, c_2$ 和 $c_3$ 使得多项式 $p$ 满足 $p(0)=0$ 和 $p(1)=0$，当且仅当它们求解以下方程组

$(c_2+2c_3)(c_1+2c_2+3c_3)=c_2$

$(c_1+2c_2+3c_3)(3c_1+4c_2+5c_3)=c_3$

另一方面，多项式的基本理论表明，$0$ 和 $1$ 是多项式 $p$ 的根，当且仅当 $X(X-1)$ 除 $p$。也就是说，当且仅当存在一个多项式 $h$ 使得

$p=X(X-1)h$

总结

总结一下，我们从多项式集合 $v_i, w_i, y_i$ 开始。这些提供了一种从任何元组 $c_1, c_2, c_3$ 构造多项式 $p$ 的方法。多项式 $p$ 可被 $X(X-1)$ 整除，当且仅当值 $c_1, c_2, c_3$ 满足方程组。

这种将方程组编码为单个多项式恒等式的方法是构建简洁证明的基本技巧。

回到我们的电路

在上一节中，我们选择了随机多项式。因此，我们得到了与它们相关联的方程组，该方程组与我们的电路无关。我们现在要做的是仔细选择多项式 $v_i, w_i, y_i$，使得与它们相关联的方程组是我们电路的 R1CS：

$c_1c_2=c_4$

$(c_1+c_2)c_4=c_3$

由于我们有四个变量 $c_1, c_2, c_3$ 和 $c_4$，我们需要每个系列中有四个多项式。在其他博客文章中，我们将解释如何使用多项式插值来构造它们，但现在，这里是我们想要的多项式：

$v_1=1, v_2=X, v_3=0, v_4=0$

$w_1=0, w_2=-X+1, w_3=0, w_4=X$

$y_1=0, y_2=0, y_3=X$ $y_4=-X+1$

对于每个 $(c_1, c_2, c_3, c_4)$，我们遵循以下配方构造 $p$：

$p=(c_1v_1+c_2v_2+c_3v_3+c_4v_4)(c_1w_1+c_2w_2+c_3w_3+c_4w_4)-(c_1y_1+c_2y_2+c_3y_3+c_4y_4)$

$=(c_1+c_2X)(c_2(-X+1)+c_4X)-(c_3X+c_4(-X+1))$

$=(c_1+c_2X)(c_2+X(c_4-c_2))-(X(c_3-c_4)+c_4)$

我们有 $p(0)=c_1c_2-c_4$ 和 $p(1)=(c_1+c_2)c_4-c_3$。因此，$p$ 可被 $X(X-1)$ 整除当且仅当

$c_1c_2=c_4$

$(c_1+c_2)c_4=c_3$

让我们插入一些实际值，看看 $p$ 是什么样子。让我们从我们的执行示例元组开始。对于我们的第一个例子，我们有 $(c_1, c_2, c_3, c_4)=(2, 3, 30, 6)$。我们得到

$p=(2+3X)(3(-X+1)+6X)-(30X+6(-X+1))$

$=(2+3X)(3X+3)-(24X+6)$

$=6X+6+9X^2+9X-24X-6$

$=9X^2-9X$

$=9X(X-1)$

对于我们的第二个例子，$(c_1, c_2, c_3, c_4)=(6, 4, 240, 24)$。我们得到

$p=(6+4X)(4(-X+1)+24X)-(240X+24(-X+1))$

$=(6+4X)(20X+4)-(216X+24)$

$=120X+24+80X^2+16X-216X-24$

$=80X^2-80X$

$=80X(X-1)$

因此，在这两种情况下，$p(0)=0, p(1)=0$，因此 $p$ 可被 $X(X-1)$ 整除。

让我们看看当我们选择不对应于执行实例的 $(c_1, c_2, c_3, c_4)$ 时会发生什么。例如，考虑与 $c_1=1, c_2=1, c_3=0, c_4=0$ 相关联的多项式 $p$。这些值不符合电路的执行实例。我们得到

$p=(1+X)((-X+1)+0X)-(0X+0(-X+1))$

$=(1+X)(-X+1)$

该多项式满足 $p(0)=1$，因此它不能被 $X(X-1)$ 整除。

像这样编码电路执行实例的多项式族 $v_i, w_i, y_i$ 存在于任何电路中。

总结

主要目标是证明电路的正确执行。显示我们得到的值 $c_1,\dots,c_N$ 并不是很好，因为验证者必须做很多工作来验证它们。多项式在这里提供了一种显示该信息的替代方法。我们可以从值 $c_1,\dots,c_N$ 构造一个多项式 $p$。当值 $c_i$ 对应于电路的有效执行时，该多项式具有特殊属性。在我们的例子中，该属性是 $p$ 可被 $X(X-1)$ 整除。因此，这提供了另一种证明正确执行的方法：

1. 表明我们按照有问题的电路的配方正确地构造了 $p$。
2. 表明对于某个多项式 $h$，$p=X(X-1)h$。

2. Schwartz-Zippel 引理

展示 $p=X(X-1)h$ 的一种简单方法是将 $p$ 的系数提供给验证者，并让他将其除以 $X(X-1)$ 以找到存在这样的多项式 $h$。这不是很好，因为执行该除法所需的工作量随着电路的复杂性而扩展。在每个 SNARK 中都出现了一种非常便宜的替代方法：证明对于 $F_p$ 中的某个随机元素 $s$，等式 $p(s)=s(s-1)h(s)$ 成立。Schwarz-Zippel 引理指出，这足以确信 $p=X(X-1)h$，我们来看看为什么。

这里的关键概念是多项式的 根。多项式 $f$ 的根是一个元素 $r \in F_p$，使得 $f(r)=0$。一个基本的代数定理指出，一个 $d$ 次的非零多项式最多可以有 $d$ 个根。例如，多项式 $f=X^5-3X+8$ 最多有 $5$ 个根。因此，如果 $F_p$ 具有大量的元素，并且我们在其中选择一个随机的 $s$，那么它成为该多项式 $5$ 个根之一的机会非常小。另一方面，多项式 $f=0$ 是唯一满足所有 $s$ 的 $f(s)=0$ 的多项式。

将所有这些放在一起，如果 $f$ 是一个多项式且对于一个随机的 $s$，有 $f(s)=0$，那么我们很有可能可以确定 $f=0$。

在我们的例子中，我们有 $p$ 和 $h$，并希望说服验证者 $p=X(X-1)h$。换句话说，我们有多项式 $f=p-X(X-1)h$，我们想说服验证者 $f=0$。因此，使用这种方法，只要表明对于一个随机的 $s$，$0=f(s)=p(s)-s(s-1)h(s)$ 就足够了。这与表明对于一个随机的 $s$，$p(s)=s(s-1)h(s)$ 相同。

3. 隐藏

到目前为止，事情看起来有点傻，因为我们正在使用 $F_p$ 中的原始元素。如果证明者向验证者发送 $p(s)$ 和 $h(s)$，她会发送 $F_p$ 的两个元素。因此，验证者收到 $F_p$ 中的两个元素 $a, b$，并且不知道它们是如何产生的。它们是随机的吗？它们实际上是 $p(s)$ 和 $h(s)$ 吗？没有办法知道。

解决方案是使用混淆的数据，允许各方执行最少的操作集。混淆的方法非常简单。我们将有一个群 $G$ 和一种将 $F_p$ 的每个元素与其在 $G$ 中的元素相关联的方法，并且这种关联方式是难以反转的。

$F_p \longrightarrow G$

例子

让我们举一个例子。数字 $113$ 是素数，这是一个我们将使用的事实：在 $Z_{454}$ 中，元素 $3$ 具有以下属性：$3^x \equiv 1$ 模 $454$ 当且仅当 $n \equiv 0$ 模 $113$。这意味着 $3^i \equiv 3^j$ 模 $454$ 当且仅当 $i \equiv j$ 模 $113$。

因此，我们有一个域 $F{113}$，一个群 $G=Z{454}$ 和元素 $3 \in Z{454}$。我们可以使用所有这些来 隐藏 $Z{454}$ 中 $F{113}$ 的元素，如下所示：元素 $x \in F{113}$ 的隐藏是 $3^x$ 模 $454$。

$F{113} \longrightarrow Z{454}$

$x \mapsto 3^x$

以下是一些例子：

$1 \mapsto 3$

$9 \mapsto 161$

$10 \mapsto 29$

$90 \mapsto 65$

假设有人选择一个随机的 $s \in F_{113}$，计算 $3^s$ 模 $454$，并发布结果。假设结果是 $225$。所以我们知道 $3^s \equiv 225$ 模 $454$。在没有遍历所有可能性的情况下，很难找出 $s$ 是什么。暴力攻击在这里起作用，因为数字很小。对于较大的域和群，这变得不可行。假设对于这个玩具例子也是如此。假设我们无法获得 $s$ 的值。

现在，即使我们不知道 $s$，我们也可以根据隐藏 $3^s$ 计算其他隐藏。例如，我们知道 $3^s=225$，所以

$3^{10s}=225^{10}=343$

所以，即使我们只知道 $s$ 的隐藏，我们也可以计算 $10s$ 的隐藏。此外，我们可以计算 $as+b$ 对于 $F_{113}$ 中的任何 $a, b$ 的隐藏：$3^{as+b}=3^{sa} \cdot 3^b=225^a \cdot 3^b$。例如

$s \mapsto 225$

$10s \mapsto 343$

$3s+2 \mapsto 155$

一般来说

现在隐藏所在的实际群 $G$ 并不那么重要。上面的例子应该能让你感受到它们的样子。但是，从现在开始，我们将假设我们有一种计算隐藏的方法。我们将用 $E(x)$ 表示 $F_p$ 中元素 $x$ 的隐藏。在示例中，$E(s)=225$, $E(10s)=343$。

检查隐藏上的等式

我们刚才看到，如果我们有一个未知元素 $s$ 的隐藏 $E(s)$，我们可以计算 $as+b$ 对于任何 $a$ 和 $b$ 的隐藏。更一般地，如果我们有隐藏 $E(s)$ 和 $E(t)$，那么我们可以计算 $as+bt$ 的隐藏，如下所示

$E(as+bt)=E(s)^aE(t)^b$。

这是因为我们有 $E(s)$，$E(t)$，其余的涉及与这两个元素的群运算。我们不能做的是计算 $E(st)$，即 $st$ 的隐藏，而不知道原始值 $s$ 和 $t$。

这很糟糕，但还不是世界末日。我们可以在没有它的情况下摆脱困境。我们需要一种算法，帮助我们在只有原始值的隐藏时检查原始值之间的关系。精确地说，我们需要一种算法 $A$，它接受 $5$ 个隐藏 $E(a), E(b), E(c), E(t), E(d)$，如果 $ab-c=td$，则输出 $1$，否则输出 $0$。它的美妙之处在于它不会泄露原始值 $a, b, c, t, d$ 是什么。

实际的算法 $A$ 是我们需要掩盖的东西。最重要的是，对于某些群 $G$，特别是对于椭圆曲线，存在这样的算法。我们建议暂时将其保留为黑盒。

请注意，$A(E(a), E(b), E(c), E(0), E(0))$ 在且仅在 $ab=c$ 时输出 $1$。这也将很有用！由于我们将大量使用此版本，因此我们将其称为算法 $B$。因此，$B$ 接受 $3$ 个隐藏 $E(a)$，$E(b)$ 和 $E(c)$，并且仅当 $c=ab$ 时才输出 $1$。

例如，使用上一节中的隐藏，

$B(161, 29, 65)=1$。

好吧，但是为什么？

回想一下，从值 $c_1, c_2, c_3, c_4$ 构造 $p$ 的公式是

$p=vw-y$,

其中 $v=c_1v_1+c_2v_2+c_3v_3+c_4v_4$, $w=c_1w_1+c_2w_2+c_3w_3+c_4w_4$ 和 $y=c_1y_1+c_2y_2+c_3y_3+c_4y_4$。如果证明者做对了所有事情，她将能够找到一个多项式 $h$ 使得 $p=X(X-1)h$。

因此，想法是证明者发送 $E(v(s))$, $E(w(s))$, $E(y(s))$ 和 $E(h(s))$ 对于某个未知值 $s$。然后，将具有 $E(s(s-1))$ 的验证者可以使用算法 $A$ 来检查 $v(s)w(s)-y(s)=s(s-1)h(s)$。这恰好是我们想要的 $p(s)=s(s-1)h(s)$。

发送 $v(s)$, $w(s)$ 和 $y(s)$ 的隐藏而不是 $p(s)$ 的隐藏的优点是，构造 $v, w$ 和 $y$ 的方法比构造 $p$ 的方法容易得多。它们是基本多项式 $v_i, w_i, y_i$ 的线性组合。而且，正如我们现在将看到的，有一种方法可以证明我们在隐藏领域中正确构造了这些多项式。

总结

证明者和验证者必须使用隐藏而不是原始值。设置阶段将产生足够的隐藏，以便证明者可以计算它需要向验证者显示的值。这足以让他确信证明者正确地执行了电路。通过一些技巧，我们可以保证证明者不能作弊。

4. 关于如何证明多项式的正确构造的直觉

让我们首先解决第三个问题：验证者如何知道证明者遵循了正确的配方来构造多项式？

以下是关于协议如何解决此问题的直觉。我们为什么要说这是一种直觉？好吧，它有漏洞。我们将在其他博客文章中讨论实际的安全性证明。

看看你自己是否能发现这些漏洞！

证明 $v$ 的正确构造

让我们从 $v$ 开始。我们想要的是以某种方式将 $E(v(s))$ 发送给验证者，以及一些冗余信息，证明 $v(s)=c_1v_1(s)+c_2v_2(s)+c_3v_3(s)+c_4v_4(s)$。但是不泄露值 $c_1,c_2,c_3,c_4$。

让我们回到我们的例子。我们有 $v_1,v_2,v_3,v_4$。并假设有一个设置阶段，其中从 $F_p$ 中抽样了随机的 $s$ 和 $\alpha$，并且公开了以下评估和验证密钥

评估密钥：

$E(v_1(s)),E(v_2(s)),E(v_3(s)),E(v_4(s)),E(\alpha v_1(s)),E(\alpha v_2(s)),E(\alpha v_3(s)),E(\alpha v_4(s)).$

验证密钥：

$E(\alpha)$

$s$ 和 $\alpha$ 的值不为任何人所知，并且已被丢弃。假设证明者已经执行了电路，获得了 $c_1,c_2,c_3,c_4$，并构造了 $v$。她想将 $v(s)$ 发送给验证者，但她不知道 $s$。然后她可以使用评估密钥来发送其隐藏：$E(v(s))$。因此，证明者构造以下元素并将它们发送给验证者：

$E(v(s))=E(v_1(s))^{c_1}E(v_2(s))^{c_2}E(v_3(s))^{c_3}E(v_4(s))^{c_4},$

$E(\alpha v(s))=E(\alpha v_1(s))^{c_1}E(\alpha v_2(s))^{c_2}E(\alpha v_3(s))^{c_3}E(\alpha v_4(s))^{c_4}.$ 请注意，右侧取决于证明者已知的元素。

验证者接收到这两个元素。我们称它们为 $V=E(v(s))$ 和 $V'=E(\alpha v(s))$。但是验证者不信任证明者，所以目前，他知道他收到了某些元素 $x$ 和 $y$ 的两个隐藏值 $V=E(x)$ 和 $V'=E(y)$。他想要确信 $x=c_1v_1(s)+c_2v_2(s)+c_3v_3(s)+c_4v_4(s)$，其中 $c_1,c_2,c_3,c_4$ 是某些值。这些值是否对应于电路的正确求值，这不是我们现在所担心的，另一个检查将涵盖这一点。我们现在所做的只是检查 $x$ 是否是在 $s$ 处对以非常特殊的方式构造的多项式的求值。

验证者使用验证密钥执行以下检查

检查 $B(V,E(\alpha),V')$ 是否等于 1

如果证明者做的一切都正确，检查应该通过。从验证者的角度来看，如果检查通过，由于 $V=E(x)$ 且 $V'=E(y)$，他知道 $y=\alpha x$。查看求值密钥，他看到证明者不知道 $\alpha$ 的原始值。证明者唯一知道的与 $\alpha$ 相关的是求值密钥中的隐藏值 $E(\alpha v_i(s))$。所以证明者构造 $\alpha$ 的倍数的隐藏值的唯一方式是从值 $E(\alpha v_i(s))$。并且可以使用它们和群操作构造的唯一东西是

$E(\alpha v_1(s))^{c_1}E(\alpha v_2(s))^{c_2}E(\alpha v_3(s))^{c_3}E(\alpha v_4(s))^{c_4}=E(c_1\alpha v_1(s)+c_2\alpha v_2(s)+c_3\alpha v_3(s)+c_4\alpha v_4(s)))$

$=E(\alpha(c_1v_1(s)+c_2v_2(s)+c_3v_3(s)+c_4v_4(s)))$

对于某些 $c_1,c_2,c_3,c_4$。所以 $V'=E(\alpha x)$ 必须是上述形式。这意味着 $\alpha x=\alpha(c_1v_1(s)+c_2v_2(s)+c_3v_3(s)+c_4v_4(s))$，因此验证者拥有

$V=E(x)=E(c_1v_1(s)+c_2v_2(s)+c_3v_3(s)+c_4v_4(s))$.

这就是验证者如何确信证明者发送给他 $V=E(v(s))$，其中 $v$ 是使用正确的配方构造的多项式！

一个漏洞

你发现了吗？问题在于“证明者唯一知道的与 $\alpha$ 相关的是求值密钥中的隐藏值 $E(\alpha v_i(s))$。” 这是错误的，因为验证密钥也是公开的，并且可能被证明者知道。证明者也有 $E(\alpha)$。她可以使用它。例如，她可以选择任何 $z$ 并将 $V=E(z)$ 和 $V'=E(\alpha)z=E(\alpha z)$ 发送给验证者。这会通过验证者的检查，而不需要 $z=v(s)$，其中 $v$ 是多项式 $v_i$ 的任何线性组合。

至此，这就是我们拥有的，如果她想，证明者可能会偷偷地把那个 $z$ 放进去。目前还不清楚证明者如何利用这种灵活性来构造假证明。而且实际上，如果不首先破坏一些密码学假设，她是做不到的。但是那个证明需要另一条路。现在，让我们继续我们的直觉，忽略这个事实。

直觉继续

尽管我们刚刚讨论了这个问题，但这个想法给出了隐藏的一个明显的用例，以说服验证者以一种非常特殊的方式生成一个值。

由于证明者还需要发送 $E(w(s))$ 和 $E(y(s))$，因此必须有一个可信设置来发布足够的隐藏值来构造它们。它看起来像这样。

所以为了发送所有 $E(v(s))$、$E(w(s))$ 和 $E(y(s))$，我们需要一个可信设置，该设置采样随机 $s$、$\alpha_v$、$\alpha_w$、$\alpha_y$ 并发布

1. 求值密钥：对于所有 $i$

$E(v_i(s)),E(\alpha_v v_i(s)),E(v_i(s)),E(\alpha_v v_i(s)),$

$E(w_i(s)),E(\alpha_w w_i(s)),E(w_i(s)),E(\alpha_w w_i(s)),$

$E(y_i(s)),E(\alpha_y y_i(s)),E(y_i(s)),E(\alpha_y y_i(s)),$

2. 验证密钥：$E(\alpha_v),E(\alpha_w),E(\alpha_y)$.

有了这一切，证明者可以构造所有隐藏值并将其发送给验证者。他遵循所有检查并确信他收到了 $E(v(s)))$、$E(w(s))$ 和 $E(y(s))$，其中 $v,w$ 和 $y$ 是相应的 $v_i,w_i$ 和 $y_i$ 的线性组合。

但那有问题。让我们更详细地重复我们刚才所说的，看看它。

验证者确信他收到了 $E(v(s))$，其中 $v(s)$ 是 $v_i(s)$ 的一些线性组合，例如 $v(s)=av_1(s)+bv_2(s)+cv_3(s)+dv_4(s)$，其中 $a,b,c,d$ 是某些值。

另一方面，他还收到了 $E(w(s))$，其中 $w(s)$ 是元素 $w_i(s)$ 的一些线性组合，例如 $w(s)=a'v_1(s)+b'v_2(s)+c'v_3(s)+d'v_4(s)$，其中 $a',b',c',d'$ 是某些值。这就是问题所在。验证者无法保证 $a=a'$，$b=b'$，$c=c'$，$d=d'$。这很重要！因为 $v,w$ 和 $y$ 需要使用相同的值 $c_1,c_2,c_3,c_4$ 来构造。这是构造 $p$ 的配方的一部分。

所以我们需要一些东西来连接证明者发送的三个隐藏值。因为到目前为止，它们是独立的，验证者的三个检查也是如此。

证明所有 $v,w,y$ 的构造

解决方案是巧妙地再次使用相同的技巧。事情开始变得奇怪。

设置阶段现在将采样随机数 $s,\alpha_v,\alpha_w,\alpha_y,\beta$ 并发布以下密钥

求值密钥：

$E(v_i(s)),E(\alpha_v v_i(s)),E(v_i(s)),E(\alpha_v v_i(s)),$

$E(w_i(s)),E(\alpha_w w_i(s)),E(w_i(s)),E(\alpha_w w_i(s)),$

$E(y_i(s)),E(\alpha_y y_i(s)),E(y_i(s)),E(\alpha_y y_i(s)),$

$E(\beta(v_i(s)+w_i(s)+y_i(s))).$

验证密钥：

$E(\alpha_v),E(\alpha_w),E(\alpha_y),E(\beta)$

和之前一样，证明者获得 $c_1,c_2,c_3,c_4$ 并使用求值密钥来计算 $E(v(s))$、$E(\alpha_v v(s))$、$E(w(s))$、$E(\alpha_w w(s))$、$E(y(s))$、$E(\alpha_y y(s))$。但现在她还可以使用求值密钥的新元素来计算 $E(\beta(v(s)+w(s)+y(s)))$。她将这七个元素发送给验证者。验证者收到七个隐藏值。让我们按证明者发送的顺序将它们表示为 $V,V',W,W',Y,Y',Z$。

验证者执行以下检查：

1. 检查 $B(V,E(\alpha_v),V')$、$B(W,E(\alpha_w),W')$ 和 $B(Y,E(\alpha_y),Y')$ 是否都等于 1。
2. 他使用群运算计算 $VWY$ 并检查 $B(VWY,E(\beta),Z)$ 是否等于 1

如果所有这些测试都通过，证明者将说服验证者

$V=E(av_1(s)+bv_1(s)+cv_3(s)+dv_4(s)),$

$W=E(aw_1(s)+bw_2(s)+cw_3(s)+dw_4(s))$

$Y=E(ay_1(s)+by_2(s)+cy_3(s)+dy_4(s))$

对于某些元素 $a,b,c,d$。原因与前一种情况非常相似。第二个检查保证 $Z$ 是 $\beta$ 的某个倍数的隐藏值。产生它的唯一方法是使用新的隐藏值 $E(\beta(v_i(s)+w_i(s)+y_i(s)))$。有了这样的隐藏值，证明者只能计算 $E(\beta(v(s)+w(s)+y(s)))$，其中 $v,w$ 和 $y$ 分别是 $v_i$、$y_i$ 和 $w_i$ 的线性组合，具有相同的系数。同样，由于第二个检查通过了，这意味着 $V,W$ 和 $Y$ 的原始值中的系数是相同的。

$h$ 怎么样？

正如我们之前所说，证明者正在发送 $E(v(s))$、$E(w(s))$ 和 $E(y(s))$，因为验证者可以使用它们来检查 $A(E(v),E(w),E(y),E(s(s-1)),E(h(s)))$ 是否等于 1。为此，验证者需要 $E(s(s-1))$ 和 $E(h(s))$。值 $E(s(s-1))$ 与电路的特定执行无关，可以添加到验证密钥中。关于 $E(h(s))$，证明者需要提供它。所以她需要能够构造它。由于 $h$ 通常不会是多项式 $v_i,w_i,y_i$ 的任何线性组合，因此评估密钥上的隐藏值现在是不够的。解决方案是将 $E(s^i)$ 添加到评估密钥，对于构造 $h$ 在最坏情况下所需的尽可能多的值 $i$。

为了保持简短，我们将等待将其添加到协议中。我们将涵盖剩余的问题，然后写下最终协议。

回顾

有了这一切，证明者可以构造 $v(s)$、$w(s)$、$y(s),h(s)$ 的隐藏值，并说服验证者她遵循了正确的配方来构建多项式 $v,w,y$。而且 $p=vw-y=X(X-1)h$。这回答了开始时的第三个和第四个问题！

5. 输入和输出

让我们回答问题 5。验证者如何知道证明者使用了输入值 $c_1$ 和 $c_2$？这很简单。回想一下，验证者期望关于输入 $c_1,c_2$ 的电路执行的证明。因此，证明者执行电路，获得输出 $c_3$，并将 $c_3$ 传达给验证者。所以验证者知道 $c_1,c_2$ 和 $c_3$。通常，验证者知道所有公共输入和输出值。因此，我们可以稍微修改协议，以允许验证者检查输入和输出。

多项式 $p$ 等于 $vw-y$，其中 $v=c_1v_1+c_2v_2+c_3v_3+c_4v_4$，对于 $w$ 和 $y$ 也是如此。并且验证者期望收到，例如，隐藏值 $E(v(s))$ 作为证明的一部分。但是 $E(v(s))$ 的输入/输出部分是验证者可以自己计算的。更准确地说，他知道 $c_1,c_2,c_3$ 和 $E(v_1(s))$、$E(v_2(s))$ 和 $E(v_3(s))$，因为到目前为止它们是公共求值密钥的一部分。所以他可以计算

$E(c_1v_1(s)+c_1v_2(s)+c_3v_3(s))=E(v_1(s))^{c_1}E(v_2(s))^{c_2}E(v_3(s))^{c_3}$

这意味着如果证明者只向他发送 $V=E(c_4v_4(s))$，那么验证者可以用上面的内容完成它以获得 $E(v(s))$：

$E(v(s))=E(c_1v_1(s)+c_1v_2(s)+c_3v_3(s))V$

这样做，他得到了保证，$v(s)$ 中对应于输入/输出的项是他所期望的。

请注意，如果我们这样做，证明者将不再需要隐藏值 $E(v_1(s))$、$E(v_2)$ 和 $E(v_3(s))$。所以我们将它们移动到验证密钥。

让我们写下我们目前所拥有的！

6. 最终协议

几乎是示例的最终协议

回想一下，我们假设存在一个隐藏函数 $E:F_p\rightarrow G$，对于某个群 $G$，并且存在一个算法 $A$，使得当且仅当 $ab-c=th$ 时，$A(E(a),E(b),E(c),E(t),E(h))=1$。我们定义 $B(E(a),E(b),E(c)):=A(E(a),E(b),E(c),E(0),E(0))$，当且仅当 $ab=c$ 时，它输出 1。另请回想一下，$E(a)E(b)=E(a+b)$。

1. 设置

从 $F_p$ 中采样五个随机元素 $s,\alpha_v,\alpha_w,\alpha_y,\beta$。从它们生成两个公共密钥：评估密钥和验证密钥

3.1 评估密钥：

$E(v_4(s)),E(w_4(s)),E(y_4(s)),E(v_4(s)),E(w_4(s)),E(y_4(s)),$

$E(\alpha_v v_4(s)),E(\alpha_w w_4(s)),E(\alpha_y y_4(s)),E(\alpha_v v_4(s)),E(\alpha_w w_4(s)),E(\alpha_y y_4(s)),$

$E(\beta(v_4(s)+w_4(s)+y_4(s))),E(\beta(v_4(s)+w_4(s)+y_4(s))),$

$E(1)$

3.2 评估密钥：

$E(\alpha_v),E(\alpha_w),E(\alpha_y),E(\beta),E(\alpha_v),E(\alpha_w),E(\alpha_y),E(\beta),$

$E(v_1(s)),E(v_2(s)),E(v_3(s)),E(v_1(s)),E(v_2(s)),E(v_3(s)),$

$E(w_1(s)),E(w_2(s)),E(w_3(s)),E(w_1(s)),E(w_2(s)),E(w_3(s)),$

$E(y_1(s)),E(y_2(s)),E(y_3(s)),E(y_1(s)),E(y_2(s)),E(y_3(s)),$

$E(s(s-1))$

2. 证明生成

证明者使用公共输入值 $c_1,c_2$ 执行电路，获得输出值 $c_3$ 和中间值 $c_4$。 她计算

$v=c_1v_1+c_2v_2+c_3v_3+c_4v_4$

$w=c_1w_1+c_2w_2+c_3w_3+c_4w_4$

$y=c_1y_1+c_2y_2+c_3y_3+c_4y_4$

$p=vw-y$

她还计算 $h$，使得 $p=X(X-1)h$。 对于此特定电路，多项式 $h$ 必须为 0 度，因此它是 $F_p$ 中的一个常数值。

证明者从评估密钥计算以下隐藏值。

$\pi=(E(c_4v_4(s)),E(\alpha_v c_4v_4(s)),$

$E(c_4w_4(s)),E(\alpha_w c_4w_4(s)),$

$E(c_4y_4(s)),E(\alpha_y c_4y_4(s)),$

$E(\beta c_4(v_4(s)+w_4(s)+y_4(s)),$

$E(h))$

证明者将输出值 $c_3$ 和证明 $\pi$ 发送给验证者。

3. 验证

验证者接收输出值 $c_3$ 和证明 $\pi=(V,V',W,W',Y,Y',Z,H)$。 他从验证密钥计算输入/输出部分。

$V_{IO}=E(c_1v_1(s)+c_2v_2(s)+c_3v_3(s))$

$W_{IO}=E(c_1w_1(s)+c_2w_2(s)+c_3w_3(s))$

$Y_{IO}=E(c_1y_1(s)+c_2y_2(s)+c_3y_3(s))$

他执行以下检查

1. $B(V',V,E(\alpha_v))=1$，$B(W',W,E(\alpha_w))=1$，$B(Y',Y,E(\alpha_y))=1$，
2. $B(VWY,E(\beta),Z)=1$，
3. $A(V{IO}V,W{IO}W,Y_{IO}Y,E(s(s-1)),H)=1$。

如果所有检查都通过，验证者确信证明者使用输入值 $c_1,c_2$ 执行了电路，并获得了输出值 $c_3$。

Pinocchio 协议

现在我们给出一般电路的实际协议。 假设电路有 $n_I$ 个输入值和 $n_O$ 个输出值。

和以前一样，令 $E$ 为隐藏函数，而 $A$ 和 $B$ 为检查隐藏方程的算法。

令 $N=n_I+n_O$。 使用输入值 $(c1,\dots,c{nI})$ 执行电路会输出值 $(c{n_I+1},\dots,cN)$ 和所有中间值 $(c{N+1},\dots,c_m)$。 将这些元组放在一起，我们说 $(c_1,\dots,c_m)$ 是电路执行的值。

在示例中，我们有 $n_I=2,n_O=1$，$N=3$，因此使用输入值 $(c_1,c_2)$ 执行电路会产生输出值 $c_3$ 和中间值 $c_4$。

令 $d$ 为电路中乘法门的数量。 令 $t=X(X-1)(X-2)\cdots(X-d)$。 存在多项式族 $v_i,w_i,y_i$，其中 $i=1,\dots,m$，使得 $(c_1,\dots,c_m)$ 是电路执行的值，当且仅当 $p=vw-y$ 可被 $t$ 整除，其中 $v=\sum_i c_i v_i$，$w=\sum_i c_i w_i$ 且 $y=\sum_i c_i y_i$。

在我们的例子中，$t=X(X-1)$。

1. 设置

从 $F_p$ 中采样八个随机元素 $s,r_v,r_w,\alpha_v,\alpha_w,\alpha_y,\beta,\gamma$。 令 $r_y=r_v r_w$。 从它们生成两个公共密钥：评估密钥和验证密钥

3.1 评估密钥：对于所有 $i=N+1,\dots,m$，以及对于所有 $j=1,\dots,d-2$

$E(r_v v_i(s)),E(r_w w_i(s)),E(r_y y_i(s)),E(r_v v_i(s)),E(r_w w_i(s)),E(r_y y_i(s)),$

$E(\alpha_v r_v v_i(s)),E(\alpha_w r_w w_i(s)),E(\alpha_y r_y y_i(s)),E(\alpha_v r_v v_i(s)),E(\alpha_w r_w w_i(s)),E(\alpha_y r_y y_i(s)),$

$E(\beta(r_v v_i(s)+r_w w_i(s)+r_y y_i(s))),E(\beta(r_v v_i(s)+r_w w_i(s)+r_y y_i(s))),$

$E(s^j)$

3.2 评估密钥：对于所有 $i=1,\dots,N$

$E(\alpha_v),E(\alpha_w),E(\alpha_y),E(\beta\gamma),E(\gamma)$

$E(r_v v_i(s)),$

$E(r_w w_i(s)),$

$E(r_y y_i(s)),$

$E(t(s))$

2. 证明生成

证明者使用输入值 $(c1,\dots,c{n_I})$ 执行电路，并获得值 $(c_1,\dots,c_m)$。 她计算：

$v=\sum_{i=1}^m c_i v_i$

$w=\sum_{i=1}^m c_i w_i$

$y=\sum_{i=1}^m c_i y_i$

$p=vw-y$

她还计算 $h$，使得 $p=th$。 多项式 $h$ 的度数最多为 $d$。

证明者从评估密钥计算以下隐藏值。 请注意，此处所有总和的 $i$ 范围为 $N+1$ 到 $m$。 这对应于中间值的索引。

$\pi=(E(\sum_{i=N+1}^m c_i r_v v_i(s)),E(\alphav \sum{i=N+1}^m r_v c_i v_i(s)),$

$E(\sum_{i=N+1}^m c_i r_w w_i(s)),E(\alphaw \sum{i=N+1}^m r_w c_i w_i(s)),$

$E(\sum_{i=N+1}^m c_i r_y y_i(s)),E(\alphay \sum{i=N+1}^m r_y c_i y_i(s)),$

$E(\beta\sum_{i=N+1}^m r_v c_i v_i(s)+r_w c_i w_i(s)+r_i c_i y_i(s)),$

$E(h))$

证明者将输出值 $(c_{n_O+1},\dots,c_N)$ 和证明 $\pi$ 发送给验证者。

3. 验证

验证者接收输出值 $(c_{n_O},\dots,c_N)$ 和证明 $\pi=(V,V',W,W',Y,Y',Z,H)$。 他从验证密钥计算输入/输出部分。 请注意，此处所有总和的 $i$ 范围为 1 到 $N$。 这对应于输入/输出索引。

$V{IO}=E(\sum{i=1}^N c_i r_v v_i(s))$

$W{IO}=E(\sum{i=1}^N c_i r_w w_i(s))$

$Y{IO}=E(\sum{i=1}^N c_i r_y y_i(s))$

他执行以下检查

1. $B(V', V, E(\alpha_v)) = 1$，$B(W', W, E(\alpha_w)) = 1$，$B(Y', Y, E(\alpha_y)) = 1$，
2. $A(Z, E(\gamma), E(0), VWY, E(\beta\gamma)) = 1$，
3. $A(VIOV, WIOW, YIOY, E(t(s)), H) = 1$。

• 如果所有检查都通过，验证者确信证明者使用输入值 $(c1, \dots, c{nI})$ 执行了电路，并获得了输出值 $(c{n_O+1}, \dots, c_N)$。

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