之前学习 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，比如 d 为 2^{20} 而 p 为 2^{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， 只要能承诺这个随机点 r 上 t(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_1，G_2， G_T 是乘法循环群，g_1，g_2，g_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_1 和 g_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

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

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

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

例子：

现有加法电路 a_1 + b_1 = c_1， 假设 a_1 和 c_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_0 和 b_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 电路有输入和输出，问给定 x 和 y， 问是否存在 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 个符号：输入输出 a，b，c 加上 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 选择系数

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

• a 和 b 和 c

  • 代表每个门的 输入和输出
  • 是否已知，取决于 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_1， Z_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 阶子群 H：H = \{\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}) = 1 和 V(\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 都知道 R，x， 这是公开信息；

只有 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 个选择系数 和 a，b，c)

得到多项式：

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) 满足上面的等式