多项式承诺（polynomial commitment）是一种机制，通过该机制，证明者可以说服验证者多项式 $p(x)$ 在点 $x$ 处的求值为 $y = p(x)$，而无需透露关于 $p(x)$ 的任何信息。其流程如下：

1. 证明者向验证者发送一个承诺 $C$，“锁定”其多项式。
2. 验证者回复一个他们希望用于多项式求值的值 $u$。
3. 证明者回复 $y$ 和 $\pi$，其中 $y$ 是 $p(u)$ 的求值结果，$\pi$ 是证明该求值正确的证明。
4. 验证者检查 $C$、$u$、$y$、$\pi$，并接受或拒绝多项式的求值是否有效。

该承诺方案不需要可信设置（trusted setup）。然而，由于证明者必须为其多项式中的每个系数发送一个承诺，因此通信开销为 $O(n)$。

对多项式进行承诺

证明者可以通过为每个系数创建一个 Pedersen Commitment 来对多项式进行承诺。对于 Pedersen Commitment，证明者和验证者需要就两个具有未知离散对数的椭圆曲线点达成一致。我们将使用 $G$ 和 $B$。

例如，如果我们有一个多项式

我们可以为每个系数创建一个 Pedersen Commitment。我们将需要三个盲化项 $\gamma_0$、$\gamma_1$、$\gamma_2$。为方便起见，任何用于盲化的标量都将使用小写希腊字母。我们始终使用椭圆曲线点 $B$ 作为盲化项。我们的承诺生成如下：

证明者将元组 $(C_0, C_1, C_2)$ 发送给验证者。

验证者选择 $u$

验证者选择他们想要用于 $x$ 的值，并将其发送给证明者。我们称该值为 $u$。

证明者计算证明

证明者对多项式求值

证明者计算原始多项式如下：

证明者对盲化项求值

下面的多项式给出了求值正确的证明，该多项式使用了盲化项乘以 $u$ 的相应次幂。具体原因将在后文解释。

证明者将 $(y, \pi)$ 发送给验证者。请注意，证明者发送的仅为域元素（标量），而非椭圆曲线点。

验证步骤

验证者运行以下检查：

为什么验证步骤有效

如果我们将椭圆曲线点展开为其底层值，我们可以看到等式是平衡的：

从某种意义上说，证明者正在使用多项式的系数以及他们选择的 $u$ 对多项式进行求值。这将产生原始多项式的求值结果加上多项式的盲化项。

证明求值正确的核心在于，证明者能够将盲化项与多项式的求值分离——尽管证明者并不知道 $yG$ 和 $\pi B$ 的离散对数。

关于验证为何有效的另一种图示说明

回想一下 $p(x) = c_0 + c_1x + c_2x^2$。因此，对系数的承诺计算如下：

当验证者发送 $\color{red}{u}$ 时，证明者计算：

在最后一步，验证者检查：

如果我们垂直展开各项，我们可以看到，如果证明者是诚实的，等式就是平衡的：

牢固掌握在给出系数盲化承诺的情况下，证明多项式正确求值的这项技术是如何工作的，这是 非常重要的，因为 Bulletproofs 在其协议中 处处 都在使用这项技术。

练习： 写出一个证明者将如何说服验证者他们正确求值了一个一阶多项式，同时又不向验证者透露该多项式的具体步骤。

练习： 填写下面的 Python 代码以实现本章描述的算法：

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

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

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

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

# 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(f_0, f_1, f_2, gamma_0, gamma_1, gamma_2, G, B):
    # fill this in
    # return the commitments as a tuple (C0, C1, C2)
    pass

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

def prove(gamma_0, gamma_1, gamma_2, u):
    # fill this in
    # return pi
    pass

def verify(C0, C1, C2, G, B, f_u, pi):
    # fill this in
    # Return true or false
    pass

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

## step 1: Prover creates the commitments
### f(x) = f_0 + f_1x + f_2x^2
f_0 = ...
f_1 = ...
f_2 = ...

### blinding terms
gamma_0 = ...
gamma_1 = ...
gamma_2 = ...
C0, C1, C2 = commit(f_0, f_1, f_2, gamma_0, gamma_1, gamma_2, G, B)

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

## step 3: Prover evaluates f(u) and pi

f_u = evaluate(f_0, f_1, f_2, u)
pi = prove(gamma_0, gamma_1, gamma_2, u)

## step 4: Verifier accepts or rejects
if verify(C0, C1, C2, G, B, f_u, pi):
    print("accept")
else:
    print("reject")

为什么证明者无法作弊

证明者作弊意味着他们没有诚实地求值 $y = p(u)$，但仍试图通过最终的验证步骤。

不失一般性，假设证明者为系数发送了正确的承诺 $C_0, C_1, C_2$。

我们说不失一般性，是因为在承诺中发送的系数与用于评估多项式的系数之间存在不匹配。

为此，证明者发送 $y'$，其中 $y' \neq c_0 + c_1u + c_2u^2$。

使用上一节的最终等式，我们可以看到证明者必须满足：

等式中的 $G$ 项显然不平衡。证明者可以拉动的另一个“杠杆”是调整他们发送的 $\pi$。

由于 $y' \neq c_0 + c_1u + c_2u^2$，恶意的证明者必须通过选择一个项 $\pi'$ 来重新平衡等式，以弥补 $G$ 项中的不匹配。证明者可以尝试用以下等式求解 $\pi'$：

但是求解这个等式需要恶意的证明者知道 $G$ 和 $B$ 的离散对数。

让我们求解上面等式中的 $\pi'$：

然后将 $B$ 替换为 $b$ 并将 $G$ 替换为 $g$，其中 $b$ 和 $g$ 分别是 $B$ 和 $G$ 的离散对数：

但再次强调，这是不可能的，因为计算 $B$ 和 $G$ 的离散对数在计算上是不可行的。

验证者了解到了什么

验证者了解到，承诺 $C_0, C_1, C_2$ 代表了对一个最高为 2 阶的多项式的有效承诺，并且 $y$ 是该多项式在 $u$ 处的求值结果。