零知识乘法

零知识多项式乘法

使用前一章的多项式承诺方案，证明者可以展示他们拥有三个多项式 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。验证者可以随机抽取任何 x 值，l(x)r(x) 的结果将是 t(x)。下面的图展示了验证者选择 x = 2 的一个示例：

验证者接下来会检查 3×4 = 12，并接受证明者的声明。

Schwartz-Zippel 引理 表明，如果 f(x) ≠ g(x)，那么对于某个随机值 u，f(u) = g(u) 的概率小于 d/p，其中 d 是这两个多项式的最大度数，p 是有限域的阶数。如果 d ≪ p（d 远小于 p），那么 u 成为两个不相等多项式的交点的概率可以忽略不计。

具体来说，假设证明者在撒谎，l(x)r(x) ≠ t(x)。在这种情况下，考虑到极高的概率，对于随机的 u，l(u)r(u) ≠ t(u)。如果 l(x)r(x) ≠ t(x)，那么 l(x)r(x) 和 t(x) 仅在最多 d 个点相交（即 l(x)r(x) 或 t(x) 的最大度数），并且验证者随机选择的 u 是这 d 个交点之一的概率极小。

为了感受规模，d 在我们的情况下是 2，但我们的椭圆曲线（从而定义的域）的阶数约为 2^254。因此，如果 t(x) ≠ l(x)r(x)，那么 t(u) = l(u)r(u) 的概率是 1/2253，这可以忽略不计。

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

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

证明者提交两个线性（1 次）多项式 l(x)、r(x) 和一个二次（2 次）多项式 t(x)，并将承诺发送给验证者。验证者回应一个随机值 u，而证明者评估 lu = l(u)、ru = r(u) 和 tu = t(u)，以及评估证明 πl、πr、πt。验证者确认所有多项式的评估都是正确的，并且 tu = l(u)r(u)。

设置

证明者和验证者就椭圆曲线点 G 和 B 达成一致，且存在一个未知的离散对数关系（即点是随机选择的）。

证明者承诺 l(x)、r(x) 和 t(x)

证明者创建三个多项式：

$$ \begin{align} l(x) &= a + s_Lx \ r(x) &= b + s_Rx \ t(x) &= l(x)r(x) = (a + s_Lx)(b + s_Rx) = ab+(as_R+bs_L)x+s_Ls_Rx^2\ \end{align} $$

因此，他们需要为每个系数生成总共 7 个 Pedersen 承诺，这将需要七个盲项 α0, α1, β0, β1, τ0, τ1, τ2

$$ \begin{align} L_0&=aG + \alpha_0B &&\text{// l(x) 的常数项 }\ L_1&=s_LG + \alpha_1B &&\text{// l(x) 线性项 }\ \ R_0&=bG + \beta_0B &&\text{// constant coefficient of }r(x)\ R_1&=s_RG + \beta_1B &&\text{// linear coefficient of }r(x)\ \ T_0 &= abG + \tau_0 B &&\text{// constant coefficient of }t(x)\ T_1 &=(as_R + bs_L)G + \tau_1B &&\text{// linear coefficient of }t(x)\ T_2 &= s_Ls_RG + \tau_2B &&\text{// quadratic coefficient of }t(x) \end{align} $$

证明者将 $(L0, L1, R0, R1, T0, T1, T2)$ 发送给验证者。

验证者生成随机标量 u

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

证明者评估三个多项式并创建三个证明

证明者将 u 代入多项式，并计算在应用 u 时多项式系数承诺盲项的和。

$$ \begin{align} l_u &= a + s_Lu\ r_u &= b + s_Ru\ t_u &= ab + (as_R + bs_l)u + s_Ls_Ru^2\ \ \pi_l &= \alpha_0 + \alpha_1u \ \pi_r &= \beta_0 + \beta_1u \ \pi_t &= \tau_0 + \tau_1u + \tau_2u^2 \end{align} $$

证明者将值 $(lu, ru, tu, πl, πr, πt) $ 发送给验证者。注意这些都是域元素，而不是椭圆曲线点。

最终验证步骤

验证者检查每个多项式是否被正确评估，以及 t(u) 的评估是否是 l(u) 和 r(u) 评估的乘积。前三个检查是证明多项式相对于系数承诺被正确评估，最后一个检查验证多项式的输出是否如所声称的那样具有乘积关系。

$$ \begin{align} l_uG + \pi_l B &\stackrel{?}= L_0+L_1u &&\text{// Check that }l(u) \text{ was evaluated correctly}\ r_uG + \pi_r B &\stackrel{?}= R_0+R_1u &&\text{// Check that }r(u) \text{ was evaluated correctly}\ t_uG + \pi_t B &\stackrel{?}= T_0+T_1u+T_2u^2&&\text{// Check that }t(u) \text{ was evaluated correctly}\ t_u &\stackrel{?}= l_ur_u &&\text{// Check that }t(u)=l(u)r(u) \end{align} $$

当我们展开项时，可以看到如果证明者诚实，这些项就会平衡：

$$ \begin{align} \underbrace{(a + sLu)}{l_u}G + \underbrace{(\alpha_0 + \alpha1u)}{\pi_l} B &\stackrel{?}= \underbrace{(aG + \alpha0B)}{L_0}+\underbrace{(s_LG + \alpha1B)}{L_1}u \ \underbrace{(b + sRu)}{r_u}G + \underbrace{(\beta_0 + \beta1u)}{\pi_r} B &\stackrel{?}= \underbrace{(bG + \beta0B)}{R_0}+\underbrace{(s_RG + \beta1B)}{R_1}u \ \underbrace{(ab + (as_R + bs_l)u + s_LsRu^2)}{t_u}G + \underbrace{(\tau_0 + \tau_1u + \tau2u^2)}{\pi_t} B &\stackrel{?}= \underbrace{(abG + \tau0 B)}{T_0}+\underbrace{(as_R + bs_L+ \tau1B)}{T_1}u+\underbrace{(s_Ls_R+ \tau2B)}{T_2}u^2 \ t_u &\stackrel{?}= l_ur_u \end{align} $$

优化：发送更少的承诺

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

这是通过将 l(x) 和 r(x) 的常数系数放入一个承诺中，而将这两个多项式的线性系数放入一个单独的承诺中来实现的。此时的定义如下：

$$ \begin{align} l(x) &= a + s_Lx \ r(x) &= b + s_Rx \ \end{align} $$

所以 a 和 b 是常数系数，sL 和 sR 是线性系数。

这类似于我们如何承诺一个向量。从某种意义上讲，我们将常数系数作为一个向量进行承诺，而将线性系数作为另一个向量进行承诺。

设置

在设置期间，我们现在需要 3 个椭圆曲线点：G、H 和 B。

多项式承诺

$$ \begin{align} A &= aG + bH + \alpha B &&\text{// 承诺常数项 }\ S &= s_LG + s_RH + \beta B &&\text{// 承诺线性项 }\ T_0 &= abG + \tau_0 B &&\text{// t(x) 的常数系数承诺 } \ T_1 &=(as_R + bs_L)G + \tau_1B &&\text{// t(x) 的线性系数承诺 }\ T_2 &= s_Ls_RG + \tau_2B &&\text{// t(x) 二次系数承诺 } \end{align} $$

注意 l(x) 的系数应用于 G，r(x) 的系数应用于 H。证明者将 (A, S, T0, T1, T2) 发送给验证者，验证者对此进行响应，发送 u。

多项式评估

$$ \begin{align} l_u &= l(u) = a + s_Lu\ r_u &= r(u) = b + s_Ru\ t_u &= t(u) = l(u)r(u) = ab + (as_R + bs_L)u + s_LsRu^2\ \pi{lr} &= \alpha + \beta u \ \pi_t &= \tau_0 + \tau_1u + \tau_2u^2 \end{align} $$

$lu、ru、tu、πlr 和 πt$ 的计算与之前相同，但 $l(x)$ 和 $r(x)$ 的评估证明，之前是 $πl$ 和 $πr$，现在合并为一个单一的证明：πlr。

最终验证

$$ \begin{align} A + Su &\stackrel{?}= l_uG + ruH+\pi{lr}B \ t_uG + \pi_tB &\stackrel{?}= T_0 + T_1u + T_2u^2 \ t_u &\stackrel{?}= l_ur_u \end{align} $$

检查$A + Su \stackrel{?}= l_uG + ruH+\pi{lr}B$展开为

$$ \underbrace{(aG + bH + \alpha B)}_A + \underbrace{(s_LG + sRH + \beta B)u}{Su} = \underbrace{(a + sLu)}{l_u}G + \underbrace{(b + sRu)}{ru}H + \underbrace{(\alpha + \beta u)}{\pi_{lr}}B $$

在左侧进行一些重组后，我们可以看到等式的检查同时检查了 l(x) 和 r(x) 的评估是否正确。

$$ (a + s_Lu)G + (b + s_Ru)H + (\alpha + \beta u)B=\underbrace{(a + sLu)}{l_u}G + \underbrace{(b + sRu)}{ru}H + \underbrace{(\alpha + \beta u)}{\pi_{lr}}B $$

另一种查看检查 A + Su = ? luG + ruH + πlrB 的方法是考虑以下可视化：

$$ \begin{align} A &= &aG& + &bH &+ &\alpha B\ Su &= &s_LuG& + &sRuH &+ &\beta u B\ &&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}&&\vcenter{\hbox{|}} \vcenter{\hbox{|}}\ &&l(u)G&&r(u)H&&\pi{lr}B \end{align} $$

零知识标量(Scalars)乘法

我们证明两项多项式乘法以获得第三项的方式，也可以证明我们将两个 标量(scalars) 相乘以获得第三项。算法不需要任何更改，只需在语义上稍做调整（即我们如何解释承诺）。

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

问题描述

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

解决方案

高层次的想法是标量可以通过添加任意选择的线性项变成一个多项式，例如 a 变为 a + sLx，b 变为 b + sRx。sL 和 sR 是由证明者随机选择的。

当多项式 a + sLx 和 b + sRx 相乘时，ab 的乘法在“内部”发生。

$$ (a + s_Lx)(b + s_Rx) = \boxed{ab} + (as_R + bs_L)x + s_Ls_rx^2 $$

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

$$ \begin{align} A &= aG + bH + \alpha B &&\text{// 对 a 和 b 的承诺 } \ S &= s_LG + s_RH + \beta B &&\text{// 承诺线性项 }\ V &= abG + \tau_0 B &&\text{// 对乘积 V 的承诺 } \ T_1 &=(as_R + bS_L)G + \tau_1B &&\text{// t(x) 的线性系数承诺 }\ T_2 &= s_Ls_RG + \tau_2B &&\text{// t(x) 二次系数承诺 } \end{align} $$

我们只是更改 A 的“解释”——从多项式的常数项，更改为我们要相乘的常数 a 和 b。我们将 T0 更改为 V，以反映在乘法中我们试图证明的 V 的承诺，即 v = ab。

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

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)

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

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

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

## 工具函数
def addd(A, B, C):
    return add(A, add(B, C))

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

## 记得所有算术运算要根据 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):
    # 填写此部分
    # return pi
    pass

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

### 步骤 1: 证明者创建承诺
a = ...
b = ...
sL = ...
sR = ...
t1 = ...
t2 = ...

#### 盲项
alpha = ...
beta = ...
gamma = ...
tau_1 = ...
tau_2 = ...

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

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

### 步骤 3: 证明者评估 l(u)、r(u)、t(u) 并创建评估证明
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)

### 步骤 4: 验证者接受或拒绝
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 或 r_u 评估不正确"
assert eq(add(multiply(G, t_u), multiply(B, pi_t)), addd(V, multiply(T1, u), multiply(T2, u**2 % p))), "t_u 评估不正确"

了解更多

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

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