• 1. 程序逻辑转换成数学运算
• 2. 数学运算转换成多项式
  • 2.1 一个运算
  • 2.2. 多个运算
• 3. 新的证明过程
• 4. 总结

在前面的文章里，我们拥有了一个很健壮的零知识证明过程（也叫做证明协议（procotol））。这个证明过程是建立在我们已经拥有一个多项式的基础上，但我们之前从未涉及到如何拥有一个多项式，我们只是假设我们已经有了。现在我们要开始学习如何将计算问题转换成多项式，从而可以正常使用我们的证明过程。

现在我们已经知道，要想用零知识证明去证明某个东西，我们首先要拥有一个多项式；而这个多项式就是我们要证明的东西的等价转换。那么如何等价转换呢？其实主要分两步：

1. 将要证明的计算过程用数学的方式表示
2. 将这种「数学的表示方式」等价转换成多项式

理论上是有第 1 步的，但现实中已经存在一些零知识证明的框架，并不需要我们特意的去做第 1 步。第 2 步就更不需要我们自己做了，只要用框架提供的方式去写约束代码，框架自己会将约束转换成多项式。（所谓约束代码，是类似「 a * b 必须等于 c 这种」表达方式，我们以后的文章会详细介绍，这里可以先不用过多关注）

这篇文章里，我们只关注第 2 步，即如何用多项式表达问题的「数学的表示方式」。但有可能在不是很理解第 1 步到底是个什么的情况下，我们直接进入到第 2 步，会有一些不踏实，所以这里我们就通过一个简单的例子了解一下。

1. 程序逻辑转换成数学运算

比如我们有以下一个 rust 函数：

fn foo(w: bool, a: i32, b: i32) -> i32 {
	if w {
		return a * b
	} else {
		return a + b
	}
}

我们现在要做的是将 foo 的逻辑等价转换成一组数学运算，确切的话是转换成一组类似 $a\times b = c$ 这样的等式。

首先我们先用数学运算的方式把 foo 表示出来。很简单，就像这样：

这里数学函数 f 就是和 foo 等价的，但它是一个数学上的表示方式，即一个数学函数。然后我们要想办法把它转换成我们刚才说的一组类似于 $a\times b = c$ 这样的等式。

foo 就相当于我们要证明的「业务逻辑」。再强调一下，在现实中我们想要证明我们的一段业务逻辑时，并不需要先写出这样一个等价的数学函数；我们甚至不需要去自己生成多项式。我们要做的，只是把我们要证明的逻辑，用「约束」表示出来就行了。但这里为了学习理论，我们要知道如何从业务逻辑转换成多项式。

我们先直接给出结果，然后再作解释：

其实有了结果就很好理解了，我们通过引入多个中间变量 $m_i$ ，将原来的 $f(w,a,b)$ 转换成了一组乘法等式（其实把这组乘法等式中的中间变量消去，就可以原来出原来的 $f(w, a, b)$）。

有了这个小例子，相信你对于程序逻辑如果转换成数学运算等式会有一个非常直观的了解了。但现实中我们不会这么笨拙的去做这件事，而是直接用一些框架提供的语言或规范，直接通过这种乘法等式实现我们想要实现的逻辑，这个就叫做「写电路」。感兴趣的读者可以去看看 circom ，可以有更准确且直观的了解。

接下来是本篇文章的重点，即如何将这一组乘法等式等价转换成多项式。

2. 数学运算转换成多项式

2.1 一个运算

我们先简单点，看看一个运算的的情况。所谓的运算，无非就是这样的表达方式：

即一个操作符（可能是 $+$ $-$ $\times$ $\div$ ）操作左右两个操作数，得出最终的结果 output 。那这个跟多项式有什么关系呢？有关系的，比如左右两个操作数可以是数，是不是也可以是多项式呢？

比如我有一个运算 $2 \times 3 = 6$ ，如果我有三个多项式 $l(x)$ 、$r(x)$ 和 $o(x)$ ，当 $x=1$ 时，分别令：

那这个运算我也可以用 $l(1) \times r(1) = o(1)$ 来表示，等式同样是成立的。那如果我不仅限于 $x=1$ 这个点，而是在多项式上所有的点都用这个等式来表示呢：

如果把上面这个式子当成一个等式来看待的话，我们只能确定它在 $x=1$ 时是成立的，但当 $x$ 取其它值时，我们不确定等式还是否成立；但我们完全可以不把它当成一个等式看待，而是一个新的多项式：

在 $f(x)$ 这个多项式中，我们可以确定的是 $f(1) = 0$ 。

如此一来，我们就得到了一个多项式 $f(x)$ ，它在某个点 $x=1$ 和原始的运算（我们例子中的 $2 \times 3 = 6$ ）是等价的，在其它点则未必，但我们只要知道它肯定在 $x=1$ 这个点是等价的就足够了。

让我们再用一个稍微抽象一点的例子来总结一下 1 个运算时多项式的转换。比如我们有一个运算 $a \times b = c$ ，那么我们可以找到三个多项式 $l(x)$ 、$r(x)$ 和 $o(x)$ ，当 $x=1$ 时，令：

那么我们就可以得到一个多项式 $f(x)=l(x)\times r(x) - o(x)$ ，其中当 $x=1$ 时 $f(1) = 0$ 。

另外你可能注意到我们刚开始提到操作符有 $+ - \times \div$ 四种运算，但我们一直在用乘法举例子。这不是巧合，而是因为乘法正好被双线性配对很好的支持（比如后面 verifier 会验证类似 $e(g^l,g^r)=e(g^t,g^h) \cdot e(g^o,g)$ 这样的等式，而 $e(g^l,g^r)$ 正好等于 $e(g,g)^{l{\times}r}$ ），所以后面我们的零知识证明的过程中，正是要使用类似 $l(x) \times r(x) = o(x)$ 这种形式。而 $+ - \div$ 可以很好的转换成乘法（我们后面会介绍到）。

2.2. 多个运算

上面我们展示的是一个运算的转换过程，那多个运算怎么办呢？比如我们有三个运算等式：

在将 1 个运算转换成多项式的时候，我们使用的方法是让多项式在某 1 个点与运算等价；那么当我们有多个运算的时候，我们就可以让多项式在多个点分别与不同的运算等式等价，这样我们可以用同样的多项式 $l(x)$ 、 $r(x)$ 和 $o(x)$ 代表多个运算了。

比如对于上面的三个运算，我们可以令：

那么在 $x={1, 2, 3}$ 这三个点，$l(x) \times r(x) = o(x)$ 这个多项式，依然分别三前面的三个运算等式相等。所以这里我们要求：

• $l(x)$ 必须经过点 $(1, a_1)$ 、$(2, a_2)$ 和 $(3, a_3)$
• $r(x)$ 必须经过点 $(1, b_1)$ 、$(2, b_2)$ 和 $(3, b_3)$
• $o(x)$ 必须经过点 $(1, c_1)$ 、$(2, c_2)$ 和 $(3, c_3)$

所以我们可以得到一个多项式 $f(x)=l(x)\times r(x)-o(x)$ 代表上面的一组（3个）运算，其中 $(1, 2, 3)$ 是 $f(x)$ 的三个根。注意很神奇的是，我们依然只用 1 个多项式，代表了整组的 3 个运算，那么扩展一下，我们可以用 1 个多项式，代表非常多的类似 $a\times b = c$ 这样的运算（而非常多的 $a\times b= c$ 这样的运算，可以代表你想表达的程序逻辑，例如上面的 foo 函数）。

另外一个问题是，如何找到符合上面要求的多项式呢？数学上有很多方法，比如解方程组法；但最常用的还是拉格朗日插值法（Lagrange polynomials）和快速傅利叶变换（Fast Fourier transform），其中快速傅利叶变换在程序实现后应该是性能最好的。这里我们不详细介绍这些方法，只要知道给定 $n$ 个点的坐标，就肯定能求得一个 $n-1$ 阶多项式经过这 $n$ 个点。

3. 新的证明过程

现在我们有必要更新一下我们的证明过程了，因为我们在将运算等式转换成多项式后，得到了三个多项式：$l(x)$ 、$r(x)$ 和 $o(x)$ ，而不是之前文章里的一个多项式 $f(x)$。我们当然也可以像以前那样，令 $f(x) = l(x) \times r(x) - o(x)$ ，就仍然得到一个多项 $f(x)$ ，但这样给了 prover 更多「灵活处理」的机会，比如虽然 prover 得到的 $l(x)$ 、$r(x)$ 、$o(x)$ 是正确的，但计算 $f(x)$ 时 prover 未必使用 $f(x) = l(x) \times r(x) - o(x)$ 这个等式，ta 可能直接令 $f(x) = l(x)$ 甚至自己造一个 $f(x)$ 出来，而 verifier 是发现不了了（只要 $t(x)$ 和 $h(x)$ 都是用假的 $f(x)$ 算出来的）。所以我们需要直接使用 $l(x)$ 、$r(x)$ 和 $o(x)$ 这三个多项式，不给 prover 自己处理的机会。

还记得之前的过程中，prover 要计算得到 $t(x)$ 和 $h(x)$ 吗？那直接使用 $l(x)$ 、$r(x)$ 和 $o(x)$ 后，$h(x)$ 和 $t(x)$ 怎么来呢？我们在求解 $l(x)$ 、$r(x)$ 和 $o(x)$ 过程中，规定必须经过一些点（比如上面例子中的 $x={1, 2, 3}$），所以这些点必定是 $l(x)$ 、$r(x)$ 和 o$(x)$ 的根，而前面我们讲过，多项式必定是能被根整除的，所以令 $t(x)=(x-x_1)(x-x_2)…(x-x_k)$ ，其中 ${x_1, x_2, …, x_k}$ 都是 $l(x)$ 、$r(x)$ 和 $o(x)$ 的根（但不必是全部的根）。比如上面的例子里，我们就可以令 $t(x)=(x-1)(x-2)(x-3)$ 。

有了 $t(x)$ ，我们可以令 $h(x) = \frac{l(x)r(x)-o(x)}{t(x)}$ ，就可以计算得出 $h(x)$ 。所以 verifier 要验证的等式变成了 $l(x)r(x) - o(x) = h(x)t(x)$ 。但由于减法在双线性配对里是一个比较耗时的运算（想想 $g^{lr-o}$，需要计算 $g^{-o}$ 或 $g^{lr} \div g^o$ ，求逆和除法都是比较复杂的运算 ），所以我们 $o(x)$ 移到右边，把验证的等式改成 $l(x)r(x)=o(x)+h(x)t(x)$ 。

所以修改后的证明过程如下：

setup:

1. prover 知道多项式 $l(x)$ ，$r(x)$，$o(x)$ ；计算得出 $h(x)$, $t(x)$ ，令： $l(x)r(x) = o(x) + h(x)t(x)$
2. verifier 知道多项式 $t(x)$
3. 多方参与 trusted setup ，得到 $(g^{\alpha}, g^{s^i}, g^{ {\alpha}s^i})$ ，其中 $i\in{0,…,d}$
4. 由于 $(g^{s^i}, g^{ {\alpha}s^i})$ 由 prover 用到，所以我们可以把它们称为 proving key.
5. 使用 $g^{s^i}$ 计算 $g^t$ ，所以得到 verification key: $(g^{\alpha},g^t)$

prover:

1. 使用 proving key 中的 $g^{s^i}$ 计算：
   \(\begin{align} E_l&=(g^{s^n})^{a_n}(g^{s^{n-1}})^{a_{n-1}}...(g^{s^1})^{a_1}g^{a_0}=g^l\\ E_r&=g^r\\ E_o&=g^o\\ E_h&=g^h \end{align}\)
2. 同样使用 proving key 中的 $g^{ {\alpha}s^i}$ 计算 ：
   \(\begin{align} E_{l'}&={(g^{ {\alpha}s^n})}^{a_n}{(g^{ {\alpha}s^{n-1}})}^{a_{n-1}}...{(g^{ {\alpha}s^1})}^{a_1}{(g^{\alpha})}^{a_0}={({(g^{s^n})}^{a_n}{(g^{s^{n-1}})}^{a_{n-1}}...{(g^{s^1})}^{a_1}g^{a_0})}^{\alpha}={g^f}^\alpha=g^{ {\alpha}l}\\ E_{r'}&=g^{ {\alpha}r}\\ E_{o'}&=g^{ {\alpha}o}\\ E_{h'}&=g^{ {\alpha}h} \end{align}\)
3. 取随机数 $\delta$ ，分别加密 $(E_l, E_{l’}, E_r, E_{r’}, E_o, E_{o’}, E_h, E_{h’})$ ，得到：
   \(\begin{align} E'_l&={(E_l)}^\delta\\ E'_{l'}&={(E_{l'})}^\delta\\ E'_r&={(E_r)}^\delta\\ E'_{r'}&={(E_{r'})}^\delta\\ E'_o&={(E_o)}^{ {\delta}^2}\\ E'_{o'}&={(E_{o'})}^{ {\delta}^2}\\ E'_h&={(E_h)}^{ {\delta}^2}\\ E'_{h'}&={(E_{h'})}^{ {\delta}^2}\\ \end{align}\)
4. 将计算得出的值 \(({E'_l}, E'_{l'}, E'_r, E'_{r'}, E'_o, E'_{o'}, E'_h, E'_{h'})\) 传回给 verifier.

verifier: 使用 verification key $(g^{\alpha}, g^t)$ 进行如下验证：

1. 验证 \(e(E'_l, g^{\alpha})=e(E'_{l'}, g)\), 即 $e({(g^l)}^{\delta}, g^{\alpha})=e({(g^{ {\alpha}l})^{\delta}}, g)$ （它们都等于 $e(g,g)^{ {\alpha}l{\delta}}$）
2. 验证 \(e(E'_r, g^{\alpha})=e(E'_{r'}, g)\), 即 $e({(g^r)}^{\delta}, g^{\alpha})=e({(g^{ {\alpha}r})^{\delta}}, g)$ （它们都等于 $e(g,g)^{ {\alpha}r{\delta}}$）
3. 验证 \(e(E'_o, g^{\alpha})=e(E'_{o'}, g)\), 即 $e({(g^o)}^{ {\delta}^2}, g^{\alpha})=e({(g^{ {\alpha}o})^{ {\delta}^2}}, g)$ （它们都等于 $e(g,g)^{ {\alpha}o{ {\delta}^2}}$）
4. 验证 \(e(E'_h, g^{\alpha})=e(E'_{h'},g)\)，即 $e({(g^h)}^{ {\delta}^2}, g^{\alpha})=e({(g^{ {\alpha}h})}^{ {\delta}^2}, g)$，（它们都等于 $e(g,g)^{ {\alpha}h{ {\delta}^2}}$）
5. 验证 \(e(E'_l,E'_r)=e(E'_o,g){\cdot}e(E'_h,g^t)\)，即 $e({(g^l)}^{\delta},{(g^r)}^{\delta})=e({(g^o)}^{ {\delta}^2},g){\cdot}e({(g^h)}^{ {\delta}^2}, g^t)$ ，即 $e(g,g)^{lr{\delta}{\delta}}=e(g,g)^{o{ {\delta}^2}}{\cdot}e(g,g)^{ht{ {\delta}^2}}=e(g,g)^{(o+ht){ {\delta}^2}}$

上面的过程与之前的相比，有两点变化。一是多项式变多了；二 verifier 验证多项式成立时，不再验证 $f(x)=h(x)t(x)$ ，而是变成了验证 $l(x)r(x)=o(x)+h(x)t(x)$ ，因此与之对应的，prover 使用 $\delta$ 对结果进行加密的时候，有些需要使用 ${\delta}^2$ 进行加密而不是 $\delta$ ，这样才能让 verifier 的第 5 步验证成立（但使用 $\delta^2$ 只是我们目前的权宜之计，真正的零知道证明（具体来说是 groth16 算法）不会使用 $\delta^2$ 的）。

4. 总结

这篇文章里，我们初步介绍了如何将普通的运算转换成多项式，方法很简单，我们将程序逻辑等价转换成很多个 $a\times b = c$ 这样的等式，然后让 $l(x)$ 、$r(x)$ 和 $o(x)$ 在某些点恰好等价于这些运算等式就可以了，有多少个等式，就有多少个点。这就是转换的核心。

但是这个核心仍需要完善，比如如何约束变量的值（上面的例子中，如果 $a_1$ 和 $a_2$ 是同一个值，我们如何在多项式中约束这个事实？），再比如我们只解决了乘法，那其它运算呢？这些问题我们在后面的文章里会一一解决。