多项式承诺通过 Pedersen 承诺实现

一个多项式承诺是一种机制，证明者可以通过它说服验证者多项式 p(x) 在点 x 的评估 y=p(x)，而不披露任何关于 p(x) 的信息。过程如下：

1. 证明者向验证者发送一个承诺 C，"锁定"他们的多项式。
2. 验证者回复一个他们希望对多项式进行评估的值 u。
3. 证明者回复 y 和 π，其中 y 是 p(u) 的评估，而 π 是评估正确的证明。
4. 验证者检查 C, u, y, π 并接受或拒绝该多项式的评估是否有效。

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

对多项式进行承诺

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

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

$$p(x) = c_0+c_1x+c_2x^2$$

我们可以为每个系数创建一个 Pedersen commitment。我们将需要三个混淆项 γ0, γ1, γ2。为了方便，任何用于混淆的标量将使用小写希腊字母。我们始终使用椭圆曲线点 B 作为混淆项。我们的承诺的生成方式如下： $$ \begin{align} C_0=c_0G+\gamma_0B \ C_1=c_1G+\gamma_1B \ C_2=c_2G+\gamma_2B \ \end{align} $$

证明者将元组 (C0, C1, C2) 发送给验证者。

验证者选择 u

验证者选择他们的 x 值并将其发送给证明者。我们称该值为 u。

证明者计算证明

证明者评估多项式

证明者计算原始多项式为：

$$ y = p(u) = c_0 + c_1u + c_2u^2 $$

证明者评估混淆项

评估正确的证明由以下多项式给出，该多项式使用混淆项乘以 u 的相应幂。原因将在后面解释。

$$ \pi = \gamma_0 + \gamma_1u+\gamma_2u^2 $$

证明者将 (y, π) 发送给验证者。请注意，证明者仅发送域元素（标量），而不是椭圆曲线点。

验证步骤

验证者进行以下检查：

$$ C_0+C_1u+C_2u^2\stackrel{?}{=}yG+\pi B $$

为什么验证步骤有效

如果我们将椭圆曲线点扩展到其底层值，我们看到这个方程是平衡的：

$$ \begin{align} C_0 + C_1u + C_2u^2 &= yG + \pi B \ (c_0G + \gamma_0B) + (c_1G + \gamma_1B)u + (c_2G + \gamma_2B)u^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ c_0G + \gamma_0B + c_1Gu + \gamma_1Bu + c_2Gu^2 + \gamma_2Bu^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ c_0G + c_1Gu + c_2Gu^2 + \gamma_0B + \gamma_1Bu + \gamma_2Bu^2 &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B &= (c_0 + c_1u + c_2u^2)G + (\gamma_0 + \gamma_1u + \gamma_2u^2)B \ \end{align} $$

在某种意义上，证明者使用多项式的系数和他们选择的 u 评估多项式。这将产生原始多项式的评估以及多项式的混淆项。

正确评估的证明是，证明者可以将混淆项与多项式评估分开——即使证明者不知道 yG 和 πB 的离散对数。

证明有效性的替代说明

回顾一下 p(x)=c0+c1x+c2x^2。因此，对系数的承诺计算如下：

$$ \begin{matrix} &\space\space\space c_0G&\space\space\space c_1G&\space\space\space c_2G\ &+\gamma_0B&+\gamma_1B&+\gamma_2B\ &\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\ &C_0&C_1&C_2 \end{matrix} $$

当验证者发送 u 时，证明者计算：

$$ \begin{matrix} y=& c_0& +c_1\color{red}{u}& +c_2\color{red}{u^2}\ \pi=&\gamma_0&+\gamma_1\color{red}{u}&+\gamma_2\color{red}{u^2}\ \end{matrix} $$

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

$$ yG + \pi B\stackrel{?}=C_0 + C_1 {\color{red} u} + C_2 {\color{red} u^2} $$

如果我们纵向扩展条目，我们看到方程是平衡的，如果证明者是诚实的：

$$ \begin{matrix} yG&=& c_0G& c_1G\color{red}{u}& c_2G\color{red}{u^2}\ \pi B&=&\gamma_0B&\gamma_1B\color{red}{u}&\gamma_2B\color{red}{u^2}\ \vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\ yG+\pi B&\stackrel{?}=&C_0&+C_1\color{red}{u}&+C_2\color{red}{u^2} \end{matrix} $$

非常重要的是，你必须牢牢把握这种基于混淆系数的多项式正确评估证明的技术，因为 Bulletproofs 在各处使用此技术。

练习: 写出证明者如何说服验证者他们正确评估了一个 1 次多项式的步骤，而不向验证者透露该多项式。

练习: 在下面填入 Python 代码，以实现本章中描述的算法：

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)

## 这些 EC 点具有未知离散对数：
G = (FQ(6286155310766333871795042970372566906087502116590250812133967451320632869759), FQ(2167390362195738854837661032213065766665495464946848931705307210578191331138))

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

## 标量乘法示例： multiply(G, 42)
## EC 加法示例： add(multiply(G, 42), multiply(G, 100))

## 请记住，所有算术都要进行模 p

def commit(f_0, f_1, f_2, gamma_0, gamma_1, gamma_2, G, B):
    # 填写此部分
    # 返回承诺作为元组 (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):
    # 填写此部分
    # 返回 π
    pass

def verify(C0, C1, C2, G, B, f_u, pi):
    # 填写此部分
    # 返回 true 或 false
    pass

### 步骤 0：证明者和验证者就 G 和 B 达成一致

### 步骤 1：证明者创建承诺
#### f(x) = f_0 + f_1x + f_2x^2
f_0 = ...
f_1 = ...
f_2 = ...

#### 混淆项
gamma_0 = ...
gamma_1 = ...
gamma_2 = ...
C0, C1, C2 = commit(f_0, f_1, f_2, gamma_0, gamma_1, gamma_2, G, B)

### 步骤 2：验证者选择 u
u = ...

### 步骤 3：证明者评估 f(u) 和 π

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

### 步骤 4：验证者接受或拒绝
if verify(C0, C1, C2, G, B, f_u, pi):
    print("accept")
else:
    print("reject")

为什么证明者不能作弊

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

不失一般性地说，假设证明者发送了正确的系数承诺 C0, C1, C2。

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

为了做到这一点，证明者发送 y′，其中 $y’ \neq c_0 + c_1u + c_2u^2$。

使用上一节中的最终方程，我们看到证明者必须满足：

$$ (c_0 + c_1u + c_2u^2)G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B=y’G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B $$

方程的 G 项显然不平衡。证明者可以拉动的另一根“杠杆”是调整他们发送的 π。

$$ (c_0 + c_1u + c_2u^2)G+(\gamma_0 + \gamma_1u+\gamma_2u^2)B=y’G + \boxed{\pi’}B $$

由于 y′≠c0+c1u+c2u^2，恶意证明者必须通过选择一个π′来重新平衡方程，以便弥补 G 项中的不匹配。证明者可以尝试通过解决以下方程来求解π′：

$$ π′B=(c0+c1u+c2u^2)G+(γ0+γ1u+γ2u^2)B–y′G $$

但是，解决此方程要求恶意证明者知道 G 和 B 的离散对数。

让我们在上面的方程中求解 π′：

$$ π′=(c0+c1u+c2u^2)G+(γ0+γ1u+γ2u^2)B–y′G $$

然后用 b 和 g 替换 B 和 G，其中 b 和 g 分别是 B 和 G 的离散对数： $$ π′=(c0+c1u+c2u^2)g+(γ0+γ1u+γ2u^2)b–y′g $$

但这同样是不可行的，因为计算 B 和 G 的离散对数是不可行的。

验证者学会什么

验证者了解到承诺 C0, C1, C2 代表对最多为 2 次的多项式的有效承诺，并且 y 是对 u 进行评估得到的多项式的值。

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