聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

零知识证明 – PLONK 学习笔记

2022-04-28 12:03 浏览: 2362579 次 我要评论(0 条) 字号:

之前学习 PLONK 的笔记,主要来自公众号 blocksight

3 - 多项式承诺

有限域 mathbb{F}_{p} triangleq {0, 1, 2, ... p-1}

mathbb{G} triangleq {g^0, g^1, g^2, ... g^{(p-1)}},其中 g 为 生成元

在有限域 mathbb{F}_{p} 上的 d 阶多项式 f(x) = a_0 + a_1x + a_2x^2 + ... + a_dx^d

其中,d 远远小于 p,比如 d2^{20}p2^{512}

--

P 拥有多项式,即他知道系数 {a_0, a_1, a_2, ... a_d}

V 做验证

多项式承诺

P 需要向 V 承诺他知道这个多项式,承诺过程:V 给出 在 mathbb{F}_{p} 域内的随机值 r,P 给出多项式在这个点的取值 f(r)

但是,为了避免 P 作弊,V 不能直接给他 r 明文;而是在加密空间中交互,推导如下:

关键 对多项式 f(x) = a_0 + a_1x + a_2x^2 + ... + a_dx^d 左右求指数,即:

begin{aligned}
g^{f(r)} =& g^{a_0 + a_1r + a_2r^2 + ... + a_dr^d} \
=& g^{a_0} cdot (g^r)^{a_1} cdot (g^{r^2})^{a_2} cdot ... cdot (g^{r^d})^{a_d}
end{aligned}

即:

V 给出的不是 r,而是加密空间的 {g, g^r, g^{r^2}, ... g^{r^d}},称为公共参数

P 回复的承诺不是 f(r),而是根据系数 {a_0, a_1, a_2, ..., a_d} 计算出的 g^{f(r)}

分析:

  • 承诺拥有 binding 的性质,这是对 V 的保护
    • 因为 离散对数 不可解 (准确说法:没有 多项式时间 解法),所以
    • P 无法通过 {g, g^r, g^{r^2}, ... g^{r^d}} 解出 r
    • g^{f(r)} 固定了 f(r), 而 f(r) 进一步固定了 f
    • 换句话说,随机数 r 对 P 不可见
    • 所以 P 无法伪造承诺
    • V 可以事后要求 P 打开承诺,然后自行根据参数 {g, g^r, g^{r^2}, ... g^{r^d}},计算 g'^{f(r)} 并与 g^{f(r)} 比较

补充:

离散对数 不可解:给出 g^a, 无法反解 a

-

  • 承诺拥有 hiding 的性质,这是对 P 的保护
    • 因为 P 回复的承诺为 g^{f(r)}, 所以 V 无法通过它反推 {a_0, a_1, a_2, ..., a_d}
    • 换句话说,V 无法从 承诺 反推多项式

--

部分打开

V 给出随机数 z, P 返回多项式计算结果 s, V 表示怀疑

问题:P 如何向 V 证明 f(z) = s

转换:

证明 f(z) = s, 等于证明 f(z) - s = 0, 即 z 是多项式 f'(x) 的一个根,其中 f'(x) = f(x) - s

根据 因式定理 可知:x -z 是 多项式 f'(x) 的因子

将第二因子记为 t(x), 则 f'(x) = t(x) cdot (x - z), 又因为 f'(x) = f(x) - s, 所以:

f(x) - s = t(x) cdot (x - z)

P 可以 多项式长除法 (long division),计算出 t(x)

我们将 t(x)x - z 分别看作新的多项式,则公式右边为 两个多项式的乘法,即 二次方程组

显然,P 不能直接将 二次方程组 给 V,否则 V 可以推导出左边的原始多项式

利用:Schwartz–Zippel lemma

转换:给出一个随机点 r, 只要能承诺这个随机点 rt(x) cdot (x - z) 的取值,我们就承诺了整个 二次式

换句话说,要承诺

f(x) - s = t(x) cdot (x - z)

只需承诺

f(r) - s = t(r) cdot (r - z)

问题:如何做 r 在 多项式乘法 的承诺

解决:

利用椭圆曲线 pairing 的两个性质,来验证乘法关系:

(1) e(g_1, g_2) = g_T

(2) e({g_1}^a, {g_2^b}) = {g_T}^{a cdot b}

其中,

e 是 椭圆曲线 的 pairing,是个 双线性映射公式,且这个公式公开 (参考 blocksight: 区块链中的数学(六十二)双线性映射)

G_1G_2G_T 是乘法循环群,g_1g_2g_T 分别是它们的 生成元

过程:

二次方程组 进入加密空间,应用性质 (1) 和 (2),得到:

begin{aligned}
&  f(r) - s = t(r) cdot (r - z) & \
Rightarrow &  {g_T}^{f(r) - s} = {g_T}^{t(r) cdot (r - z)} & \
Rightarrow &  {e(g_1, g_2)}^{f(r) - s} = {e(g_1, g_2)}^{t(r) cdot (r - z)} & 应用 (1)\
Rightarrow &  {e(frac{{g_1}^{f(r)}}{{g_1}^s}, g2)} = {e({g_1}^{t(r)}, frac{{g_2}^r}{{g_2}^z})} & 应用 (2)
end{aligned}

其中,g_1g_2 是公共参数,P 和 V 都知道

V 必须有 5 个参数 {g_1}^{f(r)}{g_1}^s{g_1}^{t(r)}{g_2}^r{g_2}^z, 才能验证参数

接下来,逐个看这 5 个 参数

  • {g_1}^{f(r)}{g_1}^{t(r)}
    • r 是 setup 阶段随机数,对 P 和 V 保密
    • P 计算出来给 V
  • {g_1}^s
    • P 将 s 明文发给 V,V 再计算 {g_1}^s
  • {g_2}^r
    • {g_2}^r 是公共参数,对 P 和 V 都已知
    • 由于 离散对数 不可解,任何人无法知道秘密 r
  • {g_2}^z
    • g_2 是公共参数,而 z 是 V 选取的随机数,所以 V 可以计算 {g_2}^z

经过上面的处理,V 最终有了这 5 个参数,所以它可以验证整个式子

其中,关键参数有:

  • {g_1}^{f(r)}
    • 承诺
    • commitment
  • s
    • 声明
    • f(x)z 上的取值
  • {g_1}^{t(r)}
    • 证明
    • witness

--

以上就是 P 如何向 V 证明:f(z) = s 的过程,

setup

概括的说,多项式承诺分为两个阶段:承诺 和 打开

在 承诺 阶段,P 向 V 返回 g^{f(r)}

在 打开 阶段,P 向 V 返回 g^{t(r)}

注意:承诺 阶段的随机数 r, 与 打开 阶段的随机数 r, 是同一个

这就引出了 setup 的概念

--

在多项式承诺系统开始前,需要 可信的第三方 通过 setup 构建任何人都不知道的随机数 r, 并通过它计算参数:

begin{cases}
{g_1, {g_1}^r, {g_1}^{r^2}, ... {g_1}^{r^d}} \
{g_2, {g_2}^r}
end{cases}

这两组参数称为 公开参数 public params,对 P 和 V 都公开

其中,

P 需要 {g_1, {g_1}^r, {g_1}^{r^2}, ... {g_1}^{r^d}} 来计算 承诺 和 witness

V 需要的是 {g_2, {g_2}^r}

--

引入 可信第三方 来 setup 这些参数,而不由 V 直接选择这些参数,是因为在区块链的应用场景中,P 和 V 的角色可以是动态的,而非一成不变的;比如一个角色今天可能是 V,明天可能是 P

所以,我们要求任何人都不能知道 r, 否则可以作弊

更进一步,在 setup 构建公共参数后,第三方必须销毁随机数 r

一种方式:MPC 多方构建

--

PLONK 中 setup 是 可更新 updatable 的

首先,第三方 {P_1} 通过随机数 r_1 生成公共参数:

{P_1} : {g_1, {g_1}^{r_1}, {g_1}^{{r_1}^2}, ... {g_1}^{{r_1}^d}}

然后,第三方 P_2 不信任系统,它可以通过 r_2 更新公共参数:

begin{cases}
{P_1} : {g_1, {g_1}^{r_1}, {g_1}^{{r_1}^2}, ... {g_1}^{{r_1}^d}} \
{P_2} : {g_1, {{g_1}^{r_1}}^{r_2}, {{g_1}^{{r_1}^2}}^{{r_2}^2}, ... {{g_1}^{{r_1}^d}}^{{r_2}^d}} = {g_1, {g_1}^{r_1 cdot r_2}, {g_1}^{{r_1 cdot r_2}^2}, ... {g_1}^{{r_1 cdot r_2}^d}}
end{cases}

注意,{P_1} 不知道 r_2{P_2} 不知道 r_1

因此,任何一方都可以更新公告参数,使得自己和其他人都无法知道随机数 r_1 cdot r_2 cdot ...

4 - SRS 与门电路

Kate 承诺:用多项式在某一个随机点上的值,来决定 f(x)

--

电路可满足问题 Circuit Satisfiability Problem

给定 xy, 问是否存在 w 满足 C(x, w) = y

其中: x 已知输入,y 已知输出,w 未知输入

零知识证明:P 找到了这个解 w。他要向 V 证明自己知道这个解,但不暴露 w

例子:

现有加法电路 a_1 + b_1 = c_1, 假设 a_1c_1 已知,分别为 1 和 3,问是否存在 b_1 满足这个加法电路

表达为约束方程,即:

begin{cases}
a_1 + b_1 = c_1 \
a_1 = 1 \
c_1 = 3 \
end{cases}

可以看到,在上面的例子中,一个门存在 3 个约束

问题:如何实现一个门有且只有一个约束

解答:引入 常数门

这样使得约束方程为

begin{cases}
a_1 + b_1 = c_1 \
a_1 = c_0 \
c_0 = 1 \
end{cases}

其中,c_0 为假想的门,它的约束为 c_0 = 1 (忽略左右输入 a_0b_0 的约束)

因为引入了 常数门,系统中一共存在 5 种情况的约束:

  • a + b = c 加法约束
  • a cdot b = c 乘法约束
  • a = constant 已知输入 x 或 已知输出 y
  • b = constant -
  • c = constant -

这样改造后,一套电路等价于一个约束系统,每个门对应一个约束,且每个约束必然是 5 种约束之一

问题转为:如何用 一个公式 表达 上面 5 个公式

回答:

(Q_L) a+ (Q_R) b + (Q_O) c + (Q_M) ab + Q_C = 0

通过恰当地选择下面 5 个系数,公式就可以表达上面 5 种约束中的一种

  • Q_L 加法门左输入系数
  • Q_R 加法门右输入系数
  • Q_O 输出系数
  • Q_M 乘法门系数
  • Q_C 常数

--

如果有 n 个门,那么存在 3n 个变量

begin{bmatrix}
a_1 & a_2 & a_3 & ... & a_n \
b_1 & b_2 & b_3 & ... & b_n \
c_1 & c_2 & c_3 & ... & c_n \
end{bmatrix}

这些变量中,有一系列的约束方程;这些约束方程,可以分为两大类,一类是 门约束,一类是 复制约束:

门约束 可以归结为 (Q_L) a + (Q_R) b + (Q_O) c + (Q_M) ab + Q_C = 0, 每个门 有且只有 一个 门约束

复制约束 一定是形式 a_3 = c_5;即在 3n 个变量中,某一个变量等于另一个变量

5 - 置换与复制约束

门约束

zk-SNARK 电路有输入和输出,问给定 xy, 问是否存在 w 满足 C(x, w) = y

这里有个反直觉的地方:为什么输出 y 是已知的,还没计算又怎么知道输出呢?

例子:已知一个图,问是否存在三色染色的解。在这个问题中,图 就是已知输出

在零知识证明中,P 求出了这个数学方程的解 w, 在不暴露 w 的情况下,向 V 证明自己求出了解

--

回忆 #4 - SRS 与门电路,我们引入 常数门 后,一个电路系统有一套约束系统,每个门有且仅有一个约束条件

假设电路有 n 个门,则他有 n 个约束条件;我们以 C 表示一个约束,则它可以表示为 C_i(a_i, b_i, c_i) = 0

每个约束条件为一个方程,共 n 个约束条件,形成方程组:

begin{cases}
C_1(a_1, b_1, c_1) = 0 \
C_2(a_2, b_2, c_2) = 0 \
C_3(a_3, b_3, c_3) = 0 \
... \
C_n(a_n, b_n, c_n) = 0 \
end{cases}

注意:这个 方程组 等价于 原来的问题 C(x, w) = y

每个方程可以表达为 统一格式 (但需要正确的选择系数):

({Q_L}_i) a_i + ({Q_R}_i) b_i + ({Q_O}_i) c_i + ({Q_M}_i) a_i b_i + {Q_C}_i = 0

所以,方程组 可以表达为:

begin{cases}
({Q_L}_0) a_0 + ({Q_R}_0) b_0 + ({Q_O}_0) c_0 + ({Q_M}_0) a_0 b_0 + {Q_C}_0 = 0 \
({Q_L}_1) a_1 + ({Q_R}_1) b_1 + ({Q_O}_1) c_1 + ({Q_M}_1) a_1 b_1 + {Q_C}_1 = 0 \
({Q_L}_2) a_2 + ({Q_R}_2) b_2 + ({Q_O}_2) c_2 + ({Q_M}_2) a_2 b_2 + {Q_C}_2 = 0 \
... \
({Q_L}_n) a_n + ({Q_R}_n) b_n + ({Q_O}_n) c_n + ({Q_M}_n) a_n b_n + {Q_C}_n = 0 \
end{cases}

如果按 每个门有一个方程组 的思路,横向看待方程组,每个方程有 8 个符号:输入输出 abc 加上 5 个选择系数

关键 切换视角,纵向看待 8 个符号,可以得到 8 个多项式

Q_L 为例,它有 n 个点,且在点 i 上的取值为 {Q_L}_i

通过 拉格朗日插值,我们可以得到这些 点 和 取值 表示的 n-1 阶的多项式

更进一步的,我们可以将这 8 个多项式,表达为:

{Q_L}(x) cdot a(x) + {Q_R}(x) cdot b(x) + {Q_O}(x) cdot c(x) + {Q_M}(x) cdot a(x) cdot b(x) + {Q_C}(x) = 0 \
where quad x in {x_1, x_2, ..., x_n}

注意:这个多项式只在 {x_1, x_2, ..., x_n} 这些点上取值为 0

问题:x 取值不是 {1, 2, ..., n} 吗,怎么成了 {x_1, x_2, ..., x_n}

理解:每个门的下标记为 {1, 2, ..., n} 只是为了理解方便,实际上必须是在有限域 mathbb{F}_{p} 上,精心选择的 n 个点 {x_1, x_2, ..., x_n}

参考 复制约束{x_1, x_2, ..., x_n} 需要满足一定的要求,实际取值为 {omega, omega^2, ..., omega^n = 1}

关键 再次转换

转为多项式

F(x) = {Q_L}(x) cdot a(x) + {Q_R}(x) cdot b(x) + {Q_O}(x) cdot c(x) + {Q_M}(x) cdot a(x) cdot b(x) + {Q_C}(x) = 0 \
quad where quad x in {x_1, x_2, ..., x_n}

注意 F(x) 只在 {x_1, x_2, ..., x_n} 取值为 0,所以这些点是 F(x) 的根

我们定义 Z_S(X) = (x - x_1)(x - x_2)...(x - x_n), 那么 Z_S(x) 一定可以被 F(x) 整除,即:Z_S(x) mid F(x)

因此,我们一定可以求得 t_g(x), 使其满足:F(x) = t_g(x) cdot {Z_S}(x)

注意:使用长除法的前提:知道 8 个符号的信息

反思 零知识证明 和 电路

首先,一套电路系统有 已知输入 x, 已知输出 y 和 未知输入 w;问题为:是否存在 w, 满足 C(x, w) = y

我们再看多项式:

{Q_L}(x) cdot a(x) + {Q_R}(x) cdot b(x) + {Q_O}(x) cdot c(x) + {Q_M}(x) cdot a(x) cdot b(x) + {Q_C}(x) = 0 \
where quad x in {x_1, x_2, ..., x_n}

其中,

关键

  • 5 个 Q_x 选择系数

    • 代表一套已经构建的电路中,每个门的元信息 (每个门是加法门,还是乘法门,还是常数门,或布尔门)
    • 是已知信息
  • abc

    • 代表每个门的 输入和输出
    • 是否已知,取决于 P 是否已经求出 C(x, w) = y 的解
    • 如果 P 解出 w, 它就结合 已知输入 x 运算电路,得到每个门的输入和输出

复制约束

首先,把 3n 个变量看成一个集合,则 复制约束 可以看成对这个集合的 partition 划分:把一个集合拆分成若干个子集的并,且子集之间不相交;即:F = F_1 cup F_2 cup ... cup F_k

然后,对每个子集 F_i 进行置换,得到 {sigma_1, sigma_2, ..., sigma_k};然后把所有子集的置换连乘,得到整体置换 sigma;即:sigma = sigma_1 cdot sigma_2 cdot ... cdot sigma_k

所以:

sigma begin{bmatrix}
a_1 & a_2 & a_3 & ... & a_n \
b_1 & b_2 & b_3 & ... & b_n \
c_1 & c_2 & c_3 & ... & c_n \
end{bmatrix}
= begin{bmatrix}
a_x & a_x & a_x & ... & a_x \
b_x & b_x & b_x & ... & b_x \
c_x & c_x & c_x & ... & c_x \
end{bmatrix}

这个置换方程,也就覆盖了所有的 复制约束 copy constraint

TODO 没懂

prod_{i = 1}^{N} U_i = 1

问题:怎样把 U_1 cdot U_2 cdot ... cdot U_N = 1 变成 U(x) (注意不是 U(x_i)) 的方程

解答:PLONK 用 递归 来处理

定义 Z_1Z_2, ...,Z_{N+1}, 递归如下

begin{cases}
Z_1 = 1 \
Z_2 = U_1 \
Z_3 = U_1 cdot U_2 \
... \
Z_N = U_1 cdot U_2 cdot ... cdot U_{N-1} \
Z_{N+1} = 1 = Z_1 \
end{cases}

统一表述为 Z_{i+1} = Z_i cdot U_i

进一步,我们发现 Z(x_{i+1}) = Z(x_i) cdot U(x_i)

这样,我们几乎得到了想要的 U(x) 的方程,除了 问号 部分:Z(?) = Z(x) cdot U(x)

解决:在 有限域 mathbb{F}_{p} 的 乘法群 mathbb{F}^*_{p} 中找到带 单位根 的 n 阶子群 HH = {omega, omega^2, ..., omega^n = 1}

TODO '单位根'

TODO 没懂

参考 门约束,我们对门的标记不是 {1, 2, ..., n}, 而是 H ({omega, omega^2, ..., omega^n = 1})

这样我们得到 问号 部分:Z(omega cdot x) = Z(x) cdot U(x)

通过这个结论,我们就把一个很复杂的乘积,转成了多项式

总结

我们把一个电路的问题,完完全全翻译成一些多项式组成的方程组

准确的说,是这两种方程的形式:

begin{cases}
begin{aligned}
& {Q_L}(x) cdot a(x) + {Q_R}(x) cdot b(x) + {Q_O}(x) cdot c(x) + {Q_M}(x) cdot a(x) cdot b(x) + {Q_C}(x) = 0 & where quad x in {x_1, x_2, ..., x_n} \
& Z(omega cdot x) - Z(x) cdot U(x) = 0 & where quad x in {omega, omega^2, ..., omega^n = 1} \
end{aligned}
end{cases}

分别对应 门约束 和 复制约束

6 - 递归证明

命题:R(x, w) = 1

P:向 V 出示 pi, 证明自己解出 w

V:验证 V(x, pi) = 1

递归:

V 向 V1 出示 pi', 证明 自己已经拿到了 P 的一个证明,即:V(x, pi) = 1

V1:验证 V_1(x, pi') = 1

--

问题:为什么要递归,而不是由 V 直接将 pi 给 V1

原因:区块链 scalability

命题:存在交易 t_n, 满足状态转移方程:

exist tn: U(sigma_{n-1}, t_n) = sigma_n

P 向 V 出示 pi_n

begin{cases}
pi_1 equiv exist t_1: U(sigma_0, t_1) = sigma_1 \
pi_2 equiv exist t_2: U(sigma_1, t_2) = sigma_2 \
dots \
pi_n equiv exist tn: U(sigma_{n-1}, t_n) = sigma_n \
end{cases}

V 进行验证

begin{cases}
V(sigma_0, sigma_1, pi_1) = 1 \
V(sigma_1, sigma_2, pi_2) = 1 \
V(sigma_2, sigma_3, pi_3) = 1 \
V(sigma_3, sigma_4, pi_4) = 1 \
dots \
V(sigma_{n-1}, sigma_n, pi_n) = 1 \
end{cases}

接下来,两两合并:

命题:存在 sigma_{n-1}pi_{n-1}pi_n, 使得 V(sigma_{n-2}, sigma_{n-1}, pi_{n-1}) = 1V(sigma_{n-1}, sigma_n, pi_n) = 1 同时成立:

exist sigma_{n-1}, pi_{n-1}, pi_{n}: V(sigma_{n-2}, sigma_{n-1}, pi_{n-1}) = 1 wedge V(sigma_{n-1}, sigma_n, pi_n) = 1

V 需要出示声明 pi'_1, 证明上面式子成立;

V‘ 进行验证 V(sigma_0, sigma_2, pi'_1) = 1

--

20 层递归,可以证明 2^{20} 笔交易

最后只需要一个 pi, 就能证明 整个 状态转换 链条 合法

7 - 整体过程分析与总结

原始问题:零知识证明 R(x, w) = 1

其中,R 是个数学算法,可以检查 w 是否是 x 的解;x 是其个问题,w 是问题的解

P 和 V 都知道 Rx, 这是公开信息;

只有 P 解出 w, 这是私密信息,他向 V 证明

把 零知识证明 转为 电路问题:C(x, w) = y

其中,C 表示公开的电一套路结构,x 表示 公开的输入,y 表示 公开的输出,P 和 V 都知道

w 表示 未知输入,P 解出后要向 V 证明

把 电路问题 转为 约束系统

原来的电路系统就被表示成了约束系统,存在两种约束

(1) 门约束

i 表示门的下标,每个门有一个门约束

({Q_L}_i) a_i + ({Q_R}_i) b_i + ({Q_O}_i) c_i + ({Q_M}_i) a_i b_i + {Q_C}_i = 0

(2) 复制约束

另一个门的输出,是另一个门的输入;因此要约束 输入 等于 输出

通过置换,把整套电路系统的所有 复制约束,一起表达为方程:

sigma begin{bmatrix}
a_1 & a_2 & a_3 & ... & a_n \
b_1 & b_2 & b_3 & ... & b_n \
c_1 & c_2 & c_3 & ... & c_n \
end{bmatrix}
= begin{bmatrix}
a_x & a_x & a_x & ... & a_x \
b_x & b_x & b_x & ... & b_x \
c_x & c_x & c_x & ... & c_x \
end{bmatrix}

把 门约束系统 转为 多项式

对门约束系统,把带 i 的参数,转为 i 的函数 (纵向看待 5 个选择系数 和 abc)

得到多项式:

F(x) = {Q_L}(x) cdot a(x) + {Q_R}(x) cdot b(x) + {Q_O}(x) cdot c(x) + {Q_M}(x) cdot a(x) cdot b(x) + {Q_C}(x) = 0 \
where quad x in {x_1, x_2, ..., x_n}

再次强调:F(x) 只在 {x_1, x_2, ..., x_n} 取值为 0,所以这些点是 F(x) 的根

我们定义 Z_S(X) = (x - x_1)(x - x_2)...(x - x_n), 那么 Z_S(x) 一定可以被 F(x) 整除,即:Z_S(x) mid F(x)

因此,我们一定可以求得 t_g(x), 使其满足:F(x) = t_g(x) cdot {Z_S}(x)

把 复制约束系统 转为 多项式

TODO 没懂

第一步,把 置换方程 变成 代数方程

第二步,把 代数方程 换成 多项式 (把 U(x_i) 变成 U(x))

Z(omega cdot x) - Z(x) cdot U(x) = 0 \
where quad x in {omega, omega^2, ..., omega^n = 1}

因为多项式 {Z(omega cdot x) - Z(x) cdot U(x)}{omega, omega^2, ..., omega^n = 1} 这些点上取值为 0,所以这些点是它的根

我们定义 Z_H(X) = (x - omega)(x - omega^2)...(x - omega^n), 那么 Z_H(x) 一定可以被 {Z(omega cdot x) - Z(x) cdot U(x)} 整除,即:Z_H(x) mid Z(omega cdot x) - Z(x) cdot U(x)

因此,我们一定可以求得 t_c(x), 使其满足:Z(omega cdot x) - Z(x) cdot U(x) = t_c(x) cdot {Z_H}(x)

结合 门约束 和 复制约束

我们用 复制约束系统 中的 {omega, omega^2, ..., omega^n = 1}, 作为 门约束系统中 {x_1, x_2, ..., x_n} 的取值,即:Z_S(x) equiv Z_H(x)

那么,原始的 零知识证明 问题 可以转为:

exist a(x), b(x), c(x), Z(x), t_g(x), t_c(x) \
such  that \
begin{cases}
{Q_L}(x) cdot a(x) + {Q_R}(x) cdot b(x) + {Q_O}(x) cdot c(x) + {Q_M}(x) cdot a(x) cdot b(x) + {Q_C}(x) = t_g(x) cdot {Z_H}(x)\
Z(omega cdot x) - U(x) cdot Z(x) = t_c(x) cdot {Z_H}(x)\
end{cases}

P 和 V 都知道的公共信息:{Q_L}(x){Q_R}(x){Q_O}(x){Q_M}(x){Q_C}(x)Z_H(x)

P 知道的 但 V 不知道:a(x)b(x)c(x)Z(omega cdot x)t_g(x)t_c(x)

--

为了简洁,用 G 代表公共信息 {Q_L}(x){Q_R}(x){Q_O}(x){Q_M}(x){Q_C}(x)Z_H(x)

我们可以进一步将上面两个多项式写为:

G(x, a(x), b(x), c(x), Z(omega cdot x), t_g(x), t_c(x)) = 0

P 需要向 V 证明,自己知道 a(x)b(x)c(x)Z(omega cdot x)t_g(x)t_c(x) 满足上面的等式



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复