多项式的零知识乘法

使用上一章中的多项式承诺方案，证明者可以展示他们拥有三个多项式 $l(x)$、$r(x)$ 和 $t(x)$，并证明 $t(x) = l(x)r(x)$。

为了使该算法起作用，验证者必须相信多项式求值是正确的——但这是我们在上一章中已经展示过的。这里的大多数步骤只是重复我们之前执行过的多项式承诺算法。

从高层次来看，证明者对 $l(x)$、$r(x)$ 和 $t(x)$ 做出承诺，并将这些承诺发送给验证者。然后，验证者为 $x$ 选择一个随机值 $u$，并要求证明者在 $u$ 处对多项式进行求值。验证者接着检查求值是否被正确执行，并且 $l(x)$ 的求值结果乘以 $r(x)$ 的求值结果是否等于 $t(x)$ 的求值结果。

例如，假设第一个多项式是 $l(x)=2x$，第二个多项式是 $r(x) = x + 1$。那么 $t(x)=2x(x+1) = 2x^2+2$。验证者可以采样任意随机的 $x$ 值，乘积 $l(x)r(x)$ 的结果将是 $t(x)$。下图展示了验证者选择 $x=2$ 的示例：

然后验证者将检查 $3 \times 4 = 12$ 并接受证明者的声明。

Schwartz-Zippel lemma（施瓦茨-齐佩尔引理）指出，如果 $f(x) \neq g(x)$，那么对于某个随机值 $u$，$f(u) = g(u)$ 的概率小于 $d/p$，其中 $d$ 是两个多项式的最大度数，$p$ 是 finite field（有限域）的阶。如果 $d \ll p$（$d$ 远小于 $p$），那么 $u$ 成为两个不相等多项式交点的概率可以忽略不计。

具体来说，假设证明者在撒谎，并且 $l(x)r(x) \neq t(x)$。在这种情况下，对于随机选择的 $u$，$l(u)r(u) \neq t(u)$ 的概率极高。如果 $l(x)r(x) \neq t(x)$，那么 $l(x)r(x)$ 和 $t(x)$ 最多仅在 $d$ 个点（即 $l(x)r(x)$ 或 $t(x)$ 的最大度数）相交，并且验证者随机挑到一个属于这 $d$ 个交点之一的 $u$ 的可能性微乎其微。

为了感受一下这个比例，在我们的例子中 $d$ 是 2，但我们椭圆曲线的阶（因此也是有限域的阶）大约是 $2^{254}$。因此，如果 $t(x) \neq l(x)r(x)$，那么 $t(u) = l(u)r(u)$ 的概率是 $1/2^{253}$，这小到可以忽略不计。

我们现在详细描述该算法，然后展示一种优化方案。

证明多项式乘法知识的步骤

证明者对两个线性（1次）多项式 $l(x)$、$r(x)$ 和一个二次（2次）多项式 $t(x)$ 做出承诺，并将这些承诺发送给验证者。验证者以随机值 $u$ 作为响应，证明者计算求值 $l_u = l(u)$、$r_u = r(u)$ 和 $t_u = t(u)$ 以及求值证明 $\pi_l, \pi_r, \pi_t$。验证者断言所有多项式都被正确求值，并且 $t_u = l_ur_u$。

设置

证明者和验证者就椭圆曲线点 $G$ 和 $B$ 达成一致，这两个点之间具有未知的离散对数关系（即这些点是随机选择的）。

证明者对 $l(x)$、$r(x)$ 和 $t(x)$ 做出承诺

证明者创建三个多项式：

因此，他们需要为每个系数产生总共7个 Pedersen 承诺，这将需要七个盲化项 $\alpha_0, \alpha_1, \beta_0, \beta_1, \tau_0, \tau_1, \tau_2$：

证明者将 $(L_0, L_1, R_0, R_1, T_0, T_1, T_2)$ 发送给验证者。

验证者生成随机标量 $u$

… 并将该域元素 $u$ 发送给证明者。

证明者对三个多项式求值并生成三个证明

证明者将 $u$ 代入多项式中，并计算代入 $u$ 时多项式系数承诺的盲化项之和。

证明者将值 $(l_u, r_u, t_u, \pi_l, \pi_r, \pi_t)$ 发送给验证者。请注意，这些都是域元素，而不是椭圆曲线点。

最终验证步骤

验证者检查每个多项式是否都被正确求值，并且 $t(u)$ 的求值结果是 $l(u)$ 和 $r(u)$ 求值结果的乘积。前三个检查是证明多项式的求值相对于系数承诺是正确的，最后一个检查用于验证多项式的输出是否具有所声明的乘积关系。

当我们展开这些项时，我们可以看到如果证明者是诚实的，等式两边是平衡的：

优化：发送更少的承诺

在第一步中，证明者发送了 7 个椭圆曲线点，在最后一步中，验证者检查了 4 个等式。我们可以改进该算法，使其仅需发送 5 个椭圆曲线点并进行 3 次等式检查。

这是通过将 $l(x)$ 和 $r(x)$ 的常数项系数放入同一个承诺中，并将这些多项式的一次项系数放入另一个单独的承诺中来实现的。作为提醒，我们将 $l(x)$ 和 $r(x)$ 定义为：

因此 $a$ 和 $b$ 是常数项系数，$s_L$ 和 $s_R$ 是一次项系数。

这类似于我们对向量做出承诺的方式。在某种意义上，我们是将常数项系数作为一个向量进行承诺，并将一次项系数作为另一个向量进行承诺。

设置

在设置过程中，我们现在需要 3 个椭圆曲线点：$G$、$H$ 和 $B$。

多项式承诺

请注意，$l(x)$ 的系数应用于 $G$，$r(x)$ 的系数应用于 $H$。证明者将 $(A, S, T_0, T_1, T_2)$ 发送给验证者，验证者以 $u$ 响应。

多项式求值

$l_u$、$r_u$、$t_u$、$\pi_{lr}$ 和 $\pi_t$ 的计算同前，但 $l(x)$ 和 $r(x)$ 的求值证明（以前分别是 $\pi_l$ 和 $\pi_r$）现在被合并为了单一的一个证明：$\pi_{lr}$。

最终验证

检查项 $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ 可展开为：

对等式左边进行一些重排，我们可以看到该等式检查同时验证了 $l(x)$ 和 $r(x)$ 是否被正确求值。

作为看待检查项 $A + Su \stackrel{?}= l_uG + r_uH+\pi_{lr}B$ 的另一种方式，请考虑以下可视化展示：

标量的零知识乘法

证明我们正确地将两个多项式相乘获得第三个多项式的证明，也可以用来证明我们将两个标量相乘获得第三个标量。算法无需进行任何更改，只需在语义（我们如何解释承诺）上进行微小的改动。

假设我们想证明我们执行了乘法 $ab = v$。

问题描述

$A$ 是对 $a$ 和 $b$ 的承诺，$V$ 是对 $v$ 的承诺，其中 $v = ab$。我们希望证明 $A$ 和 $V$ 的承诺如我们所声明的那样，而又不泄露 $a$、$b$ 或 $v$。

解决方案

总体思路是，通过添加一个任意选择的一次项，可以将标量转化为多项式。例如，$a$ 变成 $a + s_Lx$，$b$ 变成 $b + s_Rx$。$s_L$ 和 $s_R$ 由证明者随机选择。

当多项式 $a + s_Lx$ 和 $b + s_Rx$ 相乘时，$ab$ 的乘法就发生在多项式乘法的“内部”。

回想一下，证明者通过发送承诺来开始该算法：

我们只需将 $A$ 的“解释”从多项式的常数项更改为我们正在相乘的常数 $a$ 和 $b$。我们将 $T_0$ 更改为 $V$，以反映作为乘积 $V$（即我们要证明已正确执行了乘法 $v = ab$）承诺的解释变化。

练习： 填写缺失的 Python 代码，以实现上述描述的算法。

Copy
from py_ecc.bn128 import G1, multiply, add, FQ, eq
from py_ecc.bn128 import curve_order as p
import random

def random_element():
    return random.randint(0, p)

# these EC points have unknown discrete logs:
G = (FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138))

H = (FQ(13728162449721098615672844430261112538072166300311022796820929618959450231493), FQ(12153831869428634344429877091952509453770659237731690203490954547715195222919))

B = (FQ(12848606535045587128788889317230751518392478691112375569775390095112330602489), FQ(18818936887558347291494629972517132071247847502517774285883500818572856935411))

# utility function
def addd(A, B, C):
    return add(A, add(B, C))

# scalar multiplication example: multiply(G, 42)
# EC addition example: add(multiply(G, 42), multiply(G, 100))

# remember to do all arithmetic modulo p
def commit(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2):
    pass
    # return (A, S, V, T1, T2)


def evaluate(f_0, f_1, f_2, u):
    return (f_0 + f_1 * u + f_2 * u**2) % p

def prove(blinding_0, blinding_1, blinding_2, u):
    # fill this in
    # return pi
    pass

## step 0: Prover and verifier agree on G and B

## step 1: Prover creates the commitments
a = ...
b = ...
sL = ...
sR = ...
t1 = ...
t2 = ...

### blinding terms
alpha = ...
beta = ...
gamma = ...
tau_1 = ...
tau_2 = ...

A, S, V, T1, T2 = commit(a, sL, b, sR, alpha, beta, gamma, tau_1, tau_2)

## step 2: Verifier picks u
u = ...

## step 3: Prover evaluates l(u), r(u), t(u) and creates evaluation proofs
l_u = evaluate(a, sL, 0, u)
r_u = evaluate(b, sR, 0, u)
t_u = evaluate(a*b, t1, t2, u)

pi_lr = prove(alpha, beta, 0, u)
pi_t = prove(gamma, tau_1, tau_2, u)

## step 4: Verifier accepts or rejects
assert t_u == (l_u * r_u) % p, "tu != lu*ru"
assert eq(add(A, multiply(S, u)), addd(multiply(G, l_u), multiply(H, r_u), multiply(B, pi_lr))), "l_u or r_u not evaluated correctly"
assert eq(add(multiply(G, t_u), multiply(B, pi_t)), addd(V, multiply(T1, u), multiply(T2, u**2 % p))), "t_u not evaluated correctly"

了解更多

本文是关于 Bulletproof ZKPs 系列文章的一部分。