zkSNARKs（零知识证明）简述

zkSNARKs 的成功实现让我们印象深刻，因为你可以在不执行，甚至不知道执行的具体内容是什么的情况下确定某个计算的结果是否正确 -- 而你唯一知道的信息就是它正确的完成了。但是不幸的是，大多数关于 zkSNARKs 的解释都浮于表面，而且他们往往会遗留下一些『魔法』，并暗示只有最聪明的人才能懂得 zkSNARKs 是如何工作的。实际上，zkSNARKs 可以总结为 4 个简单的技术，本篇博客将会逐一解释这些技术。任何懂得 RSA 加密系统工作原理的人都会对当前使用的 zkSNARKs 有一个更好的理解和认识。让我们拭目以待！

先做一个简单的摘要，我们当前使用的 zkSNARKs 包含 4 个主要的部分（在接下来的文章里我们会详细解释每个部分）：

A) 编码成一个多项式问题

把需要验证的程序编写成一个二次的多项式方程：t(x) h(x) = w(x) v(x)，当且仅当程序的计算结果正确时这个等式才成立。证明者需要说服验证者这个等式成立。

B) 简单随机抽样

验证者会选择一个私密评估点 s 来将多项式乘法和验证多项式函数相等的问题简化成简单乘法和验证等式 t(s)h(s) = w(s)v(s) 的问题。

这样做不但可以减小证明的大小，还可以大量的减小验证所需的时间。

C) 同态（Homomorphic）编码 / 加密

译者注：在1978年，Ron Rivest，Leonard Adleman，以及 Michael L. Dertouzos 就以银行为应用背景提出了同态加密的概念，当时使用的单词是 homomorphism，也就是和抽象代数的同态是一个单词。现在一般都使用 homomorphic encryption，国内密码学圈子基本也都称作同态加密。Ron Rivest 和 Leonard Adleman 分别就是著名的RSA算法中的 R 和 A（还有一位是 Adi Shamir）。
补充（来自白老师）：同胚和同态在数学上不是一个意思。同胚指连续变形下的不变性，同态指映射下代数运算关系的保持性。

我们使用一个拥有一些同态属性的（并不是完全同态的，至少在实际使用中有一些不是同态的）编码 / 加密函数 E。这个函数允许证明者在不知道 s 的情况下计算 E(t(s)), E(h(s)), E(w(s)), E(v(s))，她只知道 E(s) 和一些其他有用的加密信息。

D) 零知识

证明者通过乘以一个数来替换 E(t(s)), E(h(s)), E(w(s)), E(v(s)) 的值，这样验证者就可以在不知道真实的编码值的情况下验证他们正确的结构了。

困难的问题在于对一个随机的私密数 k（k 不等于 0）来说，校验 t(s)h(s) = w(s)v(s) 和校验 t(s)h(s) k = w(s)v(s) 几乎是完全一样的，而不同点则是如果你只接收到了 (t(s)h(s) k) 和 w(s)v(s) 那么从中获取到 t(s)h(s) 或者 w(s)v(s) 的值就几乎不可能了。

当然了，这些都只是表面的部分，是为了让你更好的理解 zkSNARKs 的本质，现在让我们开始详细的讲解这些知识点。

RSA 和零知识证明

现在让我们快速的回想一下 RSA 是如何工作的，先不管那些琐碎的细节。想想看，我们经常用一个数字对一些数字取模，而并不是所有的整数。这里的等式 “a + b ≡ c (mod n)” 等价于 “(a + b) % n = c % n”。注意，“(mod n)” 这个部分并不是应用在 “c” 上面的，而是应用在 “≡” 以及相同等式所以其他的 “≡” 上面。虽然这样非常难以阅读，但是我保证尽量少用他们。接着让我们回到 RSA：

证明者提供了下面的数字：

p，q：两个随机的私密素数
n := p q
d：1 < d < n – 1 的随机数
e：d e ≡ 1 (mod (p-1)(q-1))

公钥是 (e, n)，私钥是 d。素数 p 和 q 可以丢弃，但是不能暴露。

消息 m 通过下面的公式加密：

$E(m) := m^{e} \,\%\,n$

c = E(m) 通过下面的公式解密：

$D(c) := c^{d}\,\%\,n$

因为 $c^{d} ≡ (m^{e} \% n)^{d} ≡ m^{ed} (mod\,\,n)$ ，并且 m 的指数就是对 (p-1)(q-1) 这一组数取模，这样我们就得到了 $m^{ed} equiv m (mod\,\,n)$ （译者注可以由费马小定理和中国剩余定理推出）。而且 RSA 的安全性是基于假设：n 不能被轻易有效的因式分解，d 不能通过 e 计算得到（如果我们知道 p 和 q 的话，就可以轻易得到我们想要的值）。

RSA 的一个牛逼的特性是同态乘法。通常来讲，如果你可以交换两个操作的顺序而不影响计算结果，那么我们就说这两个操作是同态的。在同态加密中，这就是你可以对加密数据进行计算的一个属性。完全同态加密是存在的，但是现在还没有应用到实际中，它能够对任何基于加密数据的程序完成计算。在这里对于 RSA 来说，我们只谈论 group multiplication。更准确的说就是： $E(x) E(y) ≡ x^ey^e ≡ (xy)^e ≡ E(x y) (mod \,n)$ ，用文字描述就是：两个加密信息的乘积等于两个信息乘积的加密。

这个同态的特性已经有一些乘法的零知识证明了：证明者知道一些私密的数字 x 和 y，并计算出了它们的乘积，但是只给验证者发送加密的版本：a = E(x), b = E(y) 以及 c = E(x y)。验证者检验等式 (a b) % n ≡ c % n 是否成立，此时验证者只知道加密版的乘积以及乘积是否被正确的计算，但是她不知道两个乘数和真正的乘积。如果你用加法来替代乘法，那就是一个主要操作为添加余额的区块链方向了。

交互式验证

我们已经对零知识这个概念有了一定的了解了，现在让我们着重看一下 zkSNARKs 的另一个主要的特性：简明性（succinctness）。之后你会看到这个简明性是 zkSNARKs 更牛逼的部分，因为零知识部分的实现就是因为这一特定编码，而这个特定的编码是一个有限形式的同态编码。

SNARKs 是 ** *succinct non-interactive arguments of knowledge * 的缩写。一般都通用设置之所以叫做交互式协议，是因为这里有一个证明者和一个验证者，证明者想要通过交换信息的方式让验证者相信一个表达式（比如 f(x) = y）。一般来说，没有证明者可以让验证者相信一个错误的表达式（可靠性），而且对于证明者来说一定存在一个确定的策略让验证者相信任何真实的表达式（完整性）**。SNARKs 各个部分的的意义如下：

Succinct：比起真正需要计算的长度来说，我们发送的信息大小是很小的
Non-interactive：没有或者只有很少很少的交互。对于 zkSNARKs 来说就是在证明者向验证者发送一条信息之后的过程。此外，SNARKs 还常常拥有叫做『公共验证者』的属性，它的意思是在没有再次交互的情况下任何人都可以验证，这对于区块链来说是至关重要的。
Arguments：验证者只对计算能力有限的证明者有效。拥有足够计算能力的证明者可以创造出关于错误表达式的（注意，只要拥有足够的计算能力，任何公钥加密系统都可以被破解）证明和参数。这也叫做『计算可靠性』，相对的还有『完美可靠性』。
of Knowledge：对于证明者来说在不知道一个叫做证据（witness）（比如一个哈希函数的原象或者一个确定 Merkle-tree 节点的路径）的情况下，构造出一组参数和证明是不可能的。

如果你添加了零知识的前缀，那么在交互中你就需要一个性质，即验证者除了知道表达式的正确与否之外其他一无所知。尤其是验证者不能知道 *witness string *-- 稍后我们会详细解释这是什么。

先举个例子，让我们考虑下面的交易验证计算：当且仅当 $σ_1$ 和 $σ_2$ 是账户 Merkle-trees（pre 和 post 状态）的根哈希，s 和 r 是发送者和接收者账户， $p_s$ 和 $p_r$ 是 Merkle-tree 的证明（当 v 从 s 的余额中转移到 r 的余额的过程中，能够证明在 $σ_1$ 中 s 的余额至少是 v 并且他们的哈希结果是 $σ_2$ 而不是 $σ_1$ ），这些条件都成立时， $f(σ_1, σ_2, s, r, v, p_s, p_r, v) = 1$ 成立。

如果我们知道所有输入的话，验证 f 的计算相对来说是比较容易的。因为我们可以将 f 转换成一个 zkSNARK，这时只有 $sigma_1$ 和 $sigma_2$ 是公开的， $(s, r, v, p_s, p_r, v)$ 就是 witness string。零知识的性质现在使得验证者能够检查证明者是否知道一些 witness，这些 witness 可以通过一个方式将根哈希从 $sigma_1$ 转成 $sigma_2$ ，而这样的转换又不影响正常的交易，但是验证者却不知道到底是谁发送了多少钱给谁。

关于零知识的部分相对正式的定义（仍然缺乏一些细节）就是：存在一个模拟器，它可以生成一些设置字段，但是却不知道私密的 witness，它还可以和验证者交互 -- 但是外部的观察者却不能分辨出哪个与验证者进行的交互，哪个是与证明者进行的交互。

NP 和简化的复杂性理论

为了了解 zkSNARKs 能用于哪些问题和计算，我们不得不基于复杂的理论定义一些说法。如果你不知道什么是 “witness” 的话，那么即使『读』完零知识证明你也不会知道它是什么，并且你也不会了解到为什么 zkSNARKs 只适用于特定的多项式问题，如果真是这样的话，那么你就可以跳过本节了。

P 和 NP

首先，我们限制函数只能输出 0 和 1，并称这样的函数为问题（problems）。因为你可以单独的查询一个长长的结果的每一位（bit），所以这不是一个真正的限制，但是这样可以让定理变的简单一点。现在我们想衡量解决一个给定的问题（计算函数）到底有多『难』。对于一个数学函数 f 的特定机器的实现 M，给定一个输入 x，我们可以计算出这个函数 f 需要的步数 -- 这就叫做 x 在 M 上的执行时间，这里的『步数』其实不太重要。因为程序对于更大的输入往往会需要更多的步数，而这个执行时间则是用输入值的大小或者说长度（bit 的数量）来衡量。这就是例如『 $n^{2}$ 算法』的来源 -- 这就是一个当输入值大小为 n 时，至多需要 $n^{2}$ 个步数的算法。这里的『程序』和『算法』广义上是相同的。

执行时间至多为 $n^{k}$ 的程序也叫做 “polynomial-time programs”（多项式时间问题）。

在复杂性理论中有两个主要的类别，他们就是 P 问题和 NP 问题：

P 问题是具有多项式时间的一类问题

虽然 k 的指数对于一些问题来说确实非常大，但是实际上对于那些非人造的，k 不大于 4 的 P 问题仍然被认为是可以『解决的』的问题。要确认一笔比特币的交易就是一个 P 问题，因为经过评估它需要一个多项式时间（并且只能输出 0 和 1）。简单的说就是，如果你只是计算一些值而不去『搜索』，那么这个问题就是 P 问题。但是如果你不得不搜索一些东西，那么你就会进入到另一个叫做 NP 问题的类别中。

NP 类问题

几乎所有的 NP 类问题都是 zkSNARKs，今天在实际中使用的 zkSNARKs 在通常意义上讲都属于 NP 问题。而我们目前还不知道的是，有没有不属于 NP 问题的 zkSNARKs 存在。

所有的 NP 问题都有一个特定的结构，这个特定的结构来自于 NP 问题的定义：

NP 问题是 L（含有多项式时间的程序 V）的一类问题，这个程序 V 可以在给定一个多项式尺度的叫做因子的 witness 的情况下验证这个因子。更正式的说就是：当且仅当一些多项式尺度的字符串 w（被称作 witness）满足 V(x, w) = 1 时，L(x) = 1 成立。

让我们来看一个 NP 问题的例子，比如说一个布尔函数可满足性问题（SAT）。首先让我们先来定义一下布尔函数：

任何变量 $x_1, x_2, x_3,...$ 都是一个布尔函数（我们也会使用其他的字母来设变量）
如果 f 是一个布尔函数，那么 ¬f 也是一个布尔函数（否命题）
如果 f 和 g 都是布尔函数，那么 (f ∧ g) 和 (f ∨ g) 也都是布尔函数（∧ 是且， ∨ 是或）

字符串 $“((x_1∧ x_2) ∧ ¬x_2)”$ 也是一个布尔函数。

如果可以给变量赋一个真值，然后布尔函数判断为 true（¬true 就是 false，¬false 就是 true，true ∧ false 是 false 等等一些普通的规则），我们就说这个布尔函数是可满足的，可满足性问题 SAT 就是所有可满足函数的集合。

当且仅当 f 是一个可满足函数且不是 0 时，SAT(f) := 1 成立

上面的例子 $“((x_1∧ x_2) ∧ ¬x_2)”$ 就不是可满足的，因此它不属于 SAT。证明一个给定公式满足定义并且同时确保它赋值的变量也是可满足的就是一个可以在多项式时间内被解决的问题。

P = NP ?

如果你将 NP 问题定义为长度为 0 的 witness strings，那么你会发现这就是 P 问题。因此每个 P 问题其实都是 NP 问题。在复杂性理论研究中有一个主要的任务就是发掘出这两类问题的不同 -- 即一个不属于 P 的 NP 问题。在这里似乎是很显然的，但是如果你可以再一般情况下证明它，那么你可以获得 1 百万美元**。额外说一句，如果你可以反向证明，即 P 和 NP 是等价的，也可以获得那笔奖金。而数字货币领域有朝一日能够证明的概率很大。我这么说的原因是，比起一个哈希函数的碰撞或者根据地址找到私钥来说，找到一个工作难题解决办法的证明显然更容易一点。这些都是 NP 问题，因为你刚已经证明了 P = NP，那么对于这些 NP 问题来说就一定存在一个多项式时间的程序。但是本文就不讨论了，虽然大部分研究者都认为 P 问题和 NP 问题并不是等价的。

NP 完全问题

让我们再回到 SAT。这个看起来简单的问题有个有趣的特性就是它并不仅是 NP 问题，还是 NP 完全问题。『完全』这个词在这里和『图灵完备』是一个意思。这意味着它是 NP 中最难的问题，但是更重要的是 NP 完全的定义——任何 NP 问题的输入都可以用下面的方法转换成一个同样的 SAT 的输入：

所有 NP 问题 L 都有一个在多项式时间可计算的『还原函数（reduction function）』f：

L(x) = SAT(f(x))

这样的一个还原函数不能被看成一个编译器：编译器是可以将一些编程语言写的源代码等价的转换成另一种编程语言的机器，也就是拥有语义行为的机器语言。因为 SAT 是 NP 完全的，所以这样一个还原对于任何可能的 NP 问题都是存在的，比如给定一个合适的 block hash，验证一笔比特币交易是否合法。这里还可以将一笔交易转换成一个布尔函数的还原函数，因此当且仅当这个交易是合法的时候这个布尔函数就是可满足的。

还原示例

为了弄明白这样一个还原的方法，让我们先考虑评估多项式的问题。首先，让我们定义一个由整数常量，变量，加法，减法，乘法和（正确匹配的）括号构成的多项式（类似于布尔函数）。现在让我们考虑下面的问题：

如果 f 是一个变量都来自于集合 {0, 1} 的多项式，并且其中包含一个零项，那么 PolyZero(f) := 1

现在我们就可以构建出一个从 SAT 到 PolyZero 的还原方法了，同时这也说明了 PolyZero 也是一个 NP 完全问题（验证它是否属于 NP 就当是留给你们的小练习啦）。

在一个布尔函数的结构要素上是可以定义一个还原函数 r 的。对于任何布尔函数 f，r(f) 的值拥有相同的变量个数，并且当且仅当 $r(f)(a_1,..,a_k)$ 为 0 时 $f(a_1,..,a_k)$ 为 true，这里 true 是 1，false 是 0，并且 r(f) 只假设了来自集合 {0, 1} 的变量值 0 或者 1：

$r(x_i) := (1 – x_i)$
$r(¬f) := (1 – r(f))$
$r((f ∧ g)) := (1 – (1 – r(f))(1 – r(g)))$
$r((f ∨ g)) := r(f)r(g)$

有些人可能会假设将 r((f ∧ g)) 定义为 r(f) + r(g)，但是那样的话多项式的结果就会超出集合 {0, 1} 了。

使用函数 r，((x ∧ y) ∨¬x) 被转换成了 (1 – (1 – (1 – x))(1 – (1 – y))(1 – (1 – x))。

注意，对于 r 来说，每一个替换规则都满足了之前声明的目的，因此 r 也正确的实现了还原：

当且仅当 r(f) 含有集合 {0, 1} 中的一个 0 时，SAT(f) = PolyZero(r(f)) 或者说 f 是可满足的

Witness preserving

从这个例子中你可以看出还原函数只定义了如何转换输入，但是当你仔细看的时候（或者阅读完如何完成一个可用的还原证据之后）你就会知道如何将一个可用 witness 和输入一起转换。在我们的例子中，我们只定义了如何将函数转换为多项式，但是不知道如何将我们解释的证据转换成满足赋值的 witness。这个 witness 在同一时间转换对于交易来说不是必要的，但是通常都会包含。而这对于 zkSNARKs 来说是至关重要的，因为对于证明者来说他唯一的任务就是让验证者相信有这样一个 witness 存在，并且还不会暴露任何有关 witness 的信息。

Quadratic Span Programs

在上一部分中，我们看到了 NP 问题的计算是如何被相互化简的，尤其是那些 NP 完全问题，那些 NP 完全问题基本上又都再次形成了其他的 NP 问题——包括交易验证问题。那么对我们来说找到一个对所有 NP 问题都通用的 zkSNARKs 就变的很容易了：我们只需要选择适合的 NP 完全问题。所以如果我们想展示如何使用 zkSNARKs 来验证交易的话，那么展示如何处理这个确定的 NP 完全问题就是一个有效的方法，并且比从理论上解释更容易让人接受。

接下来就是基于论文GGPR12**（这里面链接的技术报告比原文的干货更多）来谈了，这篇论文的作者发现了一个叫做 Quadratic Span Programs（QSP）的问题，这个问题完全就是为 zkSNARKs 准备的。一个 Quadratic Span Program 是由一组多项式和寻找给定多项式倍数的线性组合任务构成。此外，输入字符串的每个单独的 bit 都限制了你能够使用的多项式。详细来说（通常来讲 GSPs 限制不是那么严格，但是我们就是需要这种强限制的版本，因为后面我们会用到）就是：

对于输入长度为 n 的在域 F 上的 QSP 问题由下面这些部分构成：

一组域 F 上的多项式 $v_0,…,v_m, w_0,…,w_m$
域 F 上的一个多项式 t（目标多项式）
一个单射函数 f：{(i, j) | 1 ≤ i ≤ n, j ∈ {0, 1}} → {1, …, m}

这里的任务很粗糙，就是给多项式乘以一个因子并把它们加起来（也叫做『线性组合』）使得它们的总和是 t 的倍数。对于每一个二进制输入字符串 u 来说，函数 f 限制了可以被使用的多项式，或者更严格的讲就是它们必须是线性组合的因子。正式的表示就是：

一个输入 u 会被 QSP 接受（或验证）当且仅当来自域 F 的元组 $a = (a_1,…,a_m), b = (b_1,…,b_m)$ 满足：

如果 k = f(i, u[i]) 那么 $a_k,b_k = 1$ （u[i] 是 u 的第 i 位）
如果 k = f(i, 1 - u[i]) 那么 $a_k,b_k = 0$
目标多项式 t 整除 $v_a\,w_b$ ， $v_a = v_0 + a_1 v_0 + … + a_mv_m, w_b = w_0 + b_1 w_0 + … + b_mw_m$

注意，在这里当 2n 小于 m 时，选择元组 a 和 b 仍然是有很大的自由度的。这就意味着 QSP 只对特定大小的输入是有价值的——这个问题可以通过使用非均匀复杂度来解决，非均匀复杂度这个话题今天我们不会深入的讲解，我们只需要知道当输入值很小时，我们的密码学也能良好运转。

做一个和布尔函数可满足性的类比，你可以看到因子 $a_1,…,a_m, b_1,…,b_m$ 作为被赋值的变量，或者说是 NP 问题的 witness。因为 QSP 是属于 NP 的，那么所有的验证者都必须（只要她知道因子）检查多项式 t 是否能够整除 $v_a w_b$ ，这也是一个多项式时间的问题。

这里我们不会讨论如何将通用计算和线路问题简化成 QSP 问题，因为这对于我们了解基本概念没有任何帮助，我们只需要知道 QSP 是 NP 完全（或者说比一些非均匀分布的像 NP/poly 问题更完全）的就好了。实际上，这个简化是一个『工程』部分——必须要使用一种很聪明的方法才能让 QSP 问题尽可能的小并且有一些其他的优良特性。

关于 QSP 我们已知的一件事是如何更有效的验证它们：这个验证任务就是检验一个多项式能否整除另一个多项式。如果证明者可以提供一个满足 $t h = v_a w_b$ 的多项式 h，那么这个任务就被转变成了检验一个多项式恒等式，换句话说就是检验 $t h – v_a w_b = 0$ ，其实就是检验某个特定的多项式是否是零多项式。虽然这看起来似乎很简单，但是我们接下来要使用的多项式相当巨大（阶数大概是原始电路控制级的 100 倍），以至于获得两个多项式的乘积并不是一件容易的事。

所以相比于真正的去计算 $v_a, w_b$ 以及它们的乘积，验证者只需要选择一个私密的随机点（这个点是 zCash 中 “toxic waste” 的一部分），然后对所有的 k 计算 $t(s), v_k(s)$ 和 $w_k(s)$ ，并通过它们以及 $v_a(s)$ 和 $w_b(s)$ 来验证等式： $t(s) h(s) = v_a(s) w_b (s)$ 。所有这一系列的多项式加法，标量乘法和一个多项式乘积都可以被简化成域上的乘法和加法。

只在一个单点而不是在路径的所有点上验证多项式恒等式会降低安全性，但是证明者唯一可以作弊的情况是当 $t h – v_a w_b$ 不是零多项式时，即使证明者成功的获得了多项式的一个零项，但是她也不知道 s，并且比起 s（域中元素的数量）可能的值，0 的数量是很少的，所以实际中只在一个单点验证也是非常安全的。

zkSNARK 详解

现在让我们来详细的描述一下 QSP 上的 zkSNARK。它在开始设置阶段会执行每一个单独的 QSP。在 zCash 中，交易验证者的线路是固定的，因此 QSP 的多项式也是固定的，这个 QSP 在设置阶段只允许被执行一次，然后在所有的只有输入 u 不同的交易上复用。这个开始的设置会生成一个公共参考串（common reference string，CRS），验证者选择一个随机且私密的域元素，并在这个点加密多项式的值。验证者使用一些特定的加密方法 E 并在 CRS 中把 $E(v_k(s))$ 和 $E(w_k(s))$ 公布出来。CRS 同时还包含一些可以让验证更有效率以及添加零知识属性的值。这里使用的加密方法 E 有一个明确的同构属性，这个属性可以让证明者在不知道 $v_k(s)$ 的情况下计算出 $E(v(s))$ 。

如何使用零知识来简单估计一个多项式

首先让我们先来看一种简单的情况，即一个多项式在私密点上的加密估值，而不是完整的 QSP 问题。

为此，我们选择一个群（这里通常会使用椭圆曲线）和一个生成器 g。对于群中的元素 g，如果存在一个数字 n（群的顺序）使得列表 $g_0, g_1, g_2, …, g_{n-1}$ 包含群中的所有元素，那么我们就称 g 为『生成器』。加密方法很简单： $E(x) := g^x$ 。现在验证者选择一个私密域元素 s 并把它作为 CRS 的一部分公布出来

$E(s^0), E(s^1), …, E(s^d)$ —— d 是所有多项式的最高阶

之后，s 就可以（确切的说是一定要）被忘记了。这就是 zCash 中说的『有毒废料（toxic waste）』，因为如果有人恢复了有毒废料和之后挑选的一些私密值，那么通过找到多项式中的零项，他就可以随意的伪造证据了。

在不知道 s 的情况下，证明者可以使用这些值对任意多项式 f 计算 E(f(s))：假设我们的多项式是 $f(x) = 4x^2 + 2x + 4$ 要计算 E(f(s)) 的话，我们可以得到 $E(f(s)) = E(4s^2 + 2s + 4) = g4s^2 + 2s + 4 = E(s^2)^4 E(s^1)^2 E(s^0)^4$ ，这些值我们都可以从公开的 CRS 中获取，而不需要知道确定的 s。

这里唯一的问题是当 s 被销毁之后，验证者无法验证证明者是否正确的计算出了这个多项式。因此我们还需要选择另一个私密的域元素 $alpha$ 并公开下面的『转移』值：

$E(αs^0), E(αs^1), …, E(αs^d)$

设置阶段之后 $alpha$ 会随着 s 一起被销毁掉，验证者和证明者都不知道这个值。但是使用这些加密的值，证明者可以轻易的计算出 E(α f(s))，用上面的例子就是： $E(4αs^2 + 2αs + 4α) = E(αs^2)^4 E(αs^1)^2 E(αs^0)^4$ 。所以证明者只要公布 A := E(f(s)) 和 B := E(α f(s)))，那么验证者就可以验证这些值是否匹配了。要验证是否匹配就要用到我们的另一个主要的手法『配对函数』e 了。椭圆曲线和配对函数一定要一起选择，那么 x 和 y 就会满足下面的式子：

$e(g^x, g^y) = e(g, g)^{xy}$

使用这个配对函数，验证者就可以去检验 $e(A, g^α) = e(B, g)$ 了——注意一点，验证者是知道 $g^alpha$ 的，因为它是 CRS 中 $E(αs^0)$ 的一部分。为了明确这个方法是可用的，且证明者没有作弊，让我们来看下面的等式：

$e(A, g^α) = e(g^{f(s)}, g^α) = e(g, g)^{α f(s)}$

$e(B, g) = e(g^{α f(s)}, g) = e(g, g)^{α f(s)}$

然而，还有一个更重要的问题是证明者能否提供满足 $e(A, g^α) = e(B, g)$ 而不是 $E(f(s))$ 和 $E(α f(s)))$ 的 A 和 B。这个问题的答案是『我们希望他不能』。严格地说，我们称之为『d 次方指数知识假设』，而且我们也不知道一个想作弊的证明者能不能做到这一点。这个假设同时也是其他用来证明公钥加密方案安全性的类似的假设的拓展，而这些假设似乎也不能确认他们到底是不是正确的。

实际上，上面的协议并不是真的要让验证者检验证明者提供的多项式 $f(x) = 4x^2 + 2x + 4$ ，验证者其实只需要在点 s 上验证『几个』多项式就可以了。QSP 问题的 zkSNARK 还包含另外一个值，这个值可以让验证者确认证明者是否真的求出了正确的多项式。

这里的这个示例告诉我们验证者并不需要求出完整的多项式来证明这一点，仅仅使用配对函数就可以了。下一步我们就要添加零知识的部分了，这样验证者就不能构建任何关于 f(s) 值了，甚至连 E(f(s)) 这种加密信息也不行。

为此，证明者会挑选一个随机的 $delta$ 然后发送 $A’ := E(δ + f(s))$ 和 $B := E(α (δ + f(s))))$ ，而不是 $A := E(f(s))$ 和 $B := E(α f(s)))$ 。如果我们假设这个加密算法是不能被破解的，那么零知识的属性就很明显了。现在我们需要验证两个事情：1. 证明者确实可以计算出这些值。2. 验证者的结果依然为 true。

对于第一件事来说，注意： $A’ = E(δ + f(s)) = g^{δ + f(s)} = g^δg^{f(s)} = E(δ) E(f(s)) = E(δ) A$ ，同样的， $B’ = E(α (δ + f(s)))) = E(α δ + α f(s))) = g^{α δ + α f(s)} = g^{α δ} g^{α f(s)} = E(α)δE(α f(s)) = E(α)δ B$ 。

第二件事的话，因为验证者唯一要做的事情就是验证她接收到的 A 和 B 满足基于某个 a 的等式：A = E(a) 以及 B = E(α a)。这里的 a 显然满足 a = δ + f(s)，实际上就是 a = f(s)。

好的，现在我们总算知道了一点关于在验证者不知道那个值的情况下，证明者是如何在一个加密的私密点上面计算出多项式加密值的。接下来让我们把这些应用到 QSP 问题中吧。

QSP 问题的 SNARK

还记得吗，在 QSP 问题中我们有一些多项式 $v_0,…,v_m, w_0,…,w_m$ ，目标多项式 t（最高阶为 d）以及一个二进制的输入字符串 u。证明者会找到 $a_1,…,a_m, b_1,…,b_m$ （这些值都取决于 u）和多项式 h：

$t h = (v_0 + a_1v_1 + … + a_m v_m) (w_0 + b_1w_1 + … + b_m w_m)$

在上一节中我们已经解释了 CRS 是如何生成的。现在我们选择一个私密数字 s 和 $alpha$ 并把它们公布出来：

$E(s^0), E(s^1), …, E(s^d) and E(αs^0), E(αs^1), …, E(αs^d)$

因为我们没有单个的多项式，而对于当前问题来说这一列多项式是固定的，所以我们也需要马上把推出的多项式公布出来：

$E(t(s)), E(α t(s))$
$E(v_0(s)), …, E(v_m(s)), E(α v_0(s)), …, E(α v_m(s))$
$E(w_0(s)), …, E(w_m(s)), E(α w_0(s)), …, E(α w_m(s))$

我们还需要一个之后要用的的私密数字 $βv, βw, γ$ （它们会被用来验那些多项式是推算出来的，而不是任意的多项式），然后把它们公布出来：

$E(γ), E(β_v γ), E(β_w γ)$
$E(β_v v_1(s)), …, E(β_v v_m(s))$
$E(β_w w_1(s)), …, E(β_w w_m(s))$
$E(β_v t(s)), E(β_w t(s))$

这就是完整的 CRS。在实际的实现过程中，CRS 中的一些元素并不是必须的，但是那样会让我们的表达式变得很复杂。

现在证明者还需要做什么呢？她使用上面解释过的还原函数来找到多项式 h 和 $a_1,…,a_m, b_1,…,b_m$ 这些值。这里有一点非常重要，就是要使用一个 witness-preserving reduction（可以看上面的解释），因为只有到那个时候 $a_1,…,a_m, b_1,…,b_m$ 才能和 reduction 一起被计算出来，否则将会非常非常困难。为了描述证明者发送给验证者的证明，我们不得不再看一下 QSP 的定义。

这里有一个限制 $a_1,…,a_m, b_1,…,b_m$ 这些值的单射函数 $f: {(i, j) | 1 ≤ i ≤ n, j ∈ {0, 1}} → {1, …, m}$ 。因为相对来说 m 是比较大的，所以对于任何输入，函数 f 的输出的都不会包含这些数字。而这些下标没有被限制，所以我们就把他们叫 $I_{free}$ ，然后基于 $I_{free}$ 中的所有下标 k 定义 $v_{free}(x) = Σ_k a_kv_k(x)$ 。对于等式 $w(x) = b_1w_1(x) + … + b_mw_m(x)$ 来说，我们的证明将由下面的式子构成：

$V_{free} := E(v_{free}(s)), W := E(w(s)), H := E(h(s))$
$V’_{free} := E(α v_{free}(s)), W’ := E(α w(s)), H’ := E(α h(s))$
$Y := E(β_v v_{free}(s) + β_w w(s)))$

最后一个等式用来检验是否使用了正确的多项式（这一部分还没有讲到，不过其他的例子会说到它）。要注意的是，我们所有的加密值，证明者只需要知道 CRS 就可以全部推算出来。

而验证者现在要做的还有这些：

因为 k 不是一个 "free" 的下标，所以 $a_k$ 的值可以通过输入 u（验证者也知道这个 u 的值，其实这就是要被校验的值）直接计算得出，验证者还可以通过 v 计算出总和：

$E(v_{in}(s)) = E(Σ_k a_kv_k(s))$ 这里的 k 包含所有的『不在』 $I_{free}$ 中的下标

有了上面的式子，验证者就可以通过配对函数 e（别害怕...（译者注：讲道理，还是有点怕...））来确认下面的等式了：

$e(V’_{free}, g) = e(V{free}, g^α), e(W’, E(1)) = e(W, E(α)), e(H’, E(1)) = e(H, E(α))$
$e(E(γ), Y) = e(E(β_v γ), V_{free}) e(E(β_w γ), W)$
$e(E(v_0(s)) E(v_{in}(s)) V_{free}, E(w_0(s)) W) = e(H, E(t(s)))$

要了解这里关键概念的知识，你必须要知道配对函数是允许我们在加密信息上进行一些有限的计算的：首先我们可以使用任意多次的加法，但是不能使用乘法。其次这个加法是来自加密方法本身的加同态，乘法则是通过配对函数的两个参数来实现的。所以 $e(W’, E(1)) = e(W, E(α))$ 基本上就是在加密空间中用 1 乘以 W’，然后和 $alpha$ 乘以 W 做比较。回想一下上面的定义你就会发现 W 和 W’ 应该就是 E(w(s)) 和 E(α w(s))（如果证明者提供的是正确的证明）。

如果你还记得上面关于如何在一个私密点上推算多项式的话，这三个首先要检查的点基本上就可以确认证明者确实知道一些用 CRS 中的部分构造的多项式。第二个条目往往是用来确保证明者使用的是正确的多项式 v 和 w，而不是任意的多项式。而它背后的逻辑则是除了从 $E(v_{free}(s))$ 和 $E(w(s))$ 中获取精确的值之外，证明者没办法计算出加密组合 $E(β_v v_{free}(s) + β_w w(s)))$ 。因为 $β_v$ 在 CRS 中是隔离的，并不是 CRS 中的一部分，只有在和多项式 $w_k(s)$ 组合起来的时候才知道 $β_v$ 的值。而将它们『混合』起来的唯一方法则是通过同样的加密 γ。

假设证明者提供了一个正确的证明，让我们检验一下等式是否满足。左边和右边的部分分别是：

$e(E(γ), Y) = e(E(γ), E(β_v v_{free}(s) + β_w w(s))) = e(g, g)^{γ(β_v v_{free}(s) + β_w w(s))}$
$e(E(β_v γ), V_{free}) e(E(β_w γ), W) = e(E(β_v γ), E(v_{free}(s))) e(E(β_w γ), E(w(s))) = e(g, g)^{(β_v γ) v_{free}(s)} e(g, g)^{(β_w γ) w(s)} = e(g, g)^{γ(β_v v_{free}(s) + β_w w(s))}$

第三个条目本质上就是检验了 $(v_0(s) + a_1v_1(s) + … + a_mv_m(s)) (w_0(s) + b_1w_1(s) + … + b_mw_m(s)) = h(s) t(s)$ ，这也是 QSP 问题主要的条件。有一个需要注意的是，要将加密值的乘法转换成非加密值的加法，因为 $E(x) E(y) = g^x g^y = g^{x+y} = E(x + y)$ 。

添加零知识

就像我在开头说的，零知识证明（zkSNARKS）最牛逼的特性其实不是零知识本身，而是一种简洁性。从现在开始我们将会看到如何添加这个零知识的属性，下面的一节将会着重介绍简洁性。零知识的思路是这样的，就是证明者现在通过一个随机私密的值来进行『移位』，然后再在其他的等式中『移位回来』以取得平衡。证明者会选择 $δ_{free}, δ_w$ ，然后在证明中执行下面的替换：

用 $v_{free}(s) + δ_{free} t(s)$ 来替换 $v_{free}(s)$
用 $w(s) + δ_w t(s)$ 来替换 $w(s)$

通过这两个替换， $V_{free}$ 和 W 这两个包含 witness 因子编码的值基本上就变成了无法区别的随机值，因此要从 witness 中提取出来也不可能。大部分的等式检验对修改都是『免疫』的，而我们要确保正确的值就是 H 或者说是 h(s)。那我们就要确保：

$(v_0(s) + a_1v_1(s) + … + a_mv_m(s)) (w_0(s) + b_1w_1(s) + … + b_mw_m(s)) = h(s) t(s)$ ，或者说是
$(v_0(s) + v_{in}(s) + v_{free}(s)) (w_0(s) + w(s)) = h(s) t(s)$

这两个等式成立。修改之后，我们得到：

$(v_0(s) + v_{in}(s) + v_{free}(s) + δ_{free} t(s)) (w_0(s) + w(s) + δ_w t(s))$

然后将结果展开，我们就可以用 h(s) 来替换了：

$h(s) + δ_{free} (w_0(s) + w(s)) + δ_w (v_0(s) + v_{in}(s) + v_{free}(s)) + (δ_{free} δ_w) t(s)$

在输入和 Witness 大小之间取一个折中的值

就像你在上面这些小节中看到的一样，我们的证明由一个群（就是一个椭圆曲线）的 7 个元素组成。而且验证者的工作就是检验一些配对函数的等式是否成立以及计算
$E(v_{in}(s))$ 这样一个跟随输入大小的线性任务。最主要的是，在这个验证过程中，既不需要 witness 字符串的大小，又不需要计算工作量来验证 QSP（没有 SNARKs）。这就意味着 SNARKs 的校验是个很复杂的问题，而简单的问题往往都是一样的。造成这个结果的主要原因则是，因为我们只在一个单独的点上面检验了多项式的一致性，而不是全部的点。多项式可以变的非常非常复杂，但是一个点始终是一个点。而唯一能影响到验证结果的参数就是安全性的等级（比如群的大小）和输入值的最大尺寸。

减小第二个参数是可行的，将输入值的一部分移动到 witness 中：我们不验证函数 f(u, w)，u 是输入，w 是 witness，而是做一次 hash，然后验证：

$f'(H, (u, w)) := f(u, w) ∧ h(u) = H$

这样就意味着我们可以用一个 hash 来代表输入 h(u) 了（这样就会变的更短），除了验证 f(x, w)，我们还需要验证某个值 x 的 hash 等于 H(u)（这样的话，那 x 极有可能就等于 u 了）。这样就将原始输入 u 移动到 witness 字符串中了，这样虽然会增大 witness 的大小，但是输入值的大小就减小为一个常数了。

这简直太厉害了，因为这意味着我们可以在常数时间内完成对任何复杂表达式的检验。

和 Ethereum 的关系

因为验证计算是 Ethereum 区块链的核心，所以 zkSNARKs 和 Ethereum 关系紧密相连。有了 zkSNARKs，我们不但可以完成任何人都可证实的私密的计算，而且还可以高效的完成。

虽然 Ethereum 使用了一个图灵完备的虚拟机，但是当前在 Ethereum 上实现一个 zkSNARK 还是不可能的。从概念上讲，验证者的任务似乎很简单，但是配对函数是真的很难计算，而且在单个区块中还会消耗更多的 gas。椭圆曲线的乘法相对来讲已经非常复杂了，而配对函数将这个复杂度又增加了一个级别。

像 zCash 这种现存的 zkSNARK 系统对每一个任务都使用的是同样的问题，circuit 计算。在 zCash 中，就是交易验证。在 Ethereum 上，zkSNARKs 将不会只单单做一个计算问题，而是让所有的人都能够在不发布一个新的区块链的情况下构建他们自己的 zkSNARK 系统。每一个添加到 Ethereum 上的 zkSNARK 系统都需要进行一个新的私密的可信任的准备阶段（一些可以复用，一些不能），比如生成一个新的 CRS。像为一个『通用虚拟机』添加 zkSNARK 系统将会变的可能。这样的话当你使用一个新的实例时，你就不需要重新设置了，因为你将不再需要为 Ethereum 上新的智能合约发布一个新的区块链。

将 zkSNARKs 结合到 Ethereum 上

在 Ethereum 上启用 zkSNARKs 有很多种方式。所有的方式都可以为配对函数和椭圆曲线操作（其他必要的操作都很简单）减小真实的损耗，因此我们也要减小这些操作消耗的 gas。

提升（确保）EVM 的性能
只在确定的配对函数和椭圆曲线乘法上提升 EVM 的性能

第一项在长期显然会得到很好的回报，但是实现起来难度比较大。我们现在已经在对 EVM 添加一些新的功能和限制了，例如更好的支持及时编译以及在现存实现下最小改动的解释器的实现。当然也不排除直接用 eWASM 来替换 EVM。

第二项则可以通过强制所有的 Ethereum 客户端执行一个确定的配对函数和确定的椭圆曲线乘法的叫做预编译合约的东西来实现。这样做的好处就是实现起来既简单又快速。而缺点呢则是这样做我们就会固定在一个确定的的配对函数和一个确定的椭圆曲线上。所有 Ethereum 上新的客户端都不得不再实现一遍这个预编译合约。所有，如果有什么新的进展，或者有人可以找到更好的 zkSNARKs 的方法，更好的配对函数，更好的椭圆曲线，又或者发现了椭圆曲线，配对函数和 zkSNARK 的一些缺点，那么我们就会添加到新的预编译合约中。

原文链接: https://blog.ethereum.org/2016/12/05/zksnarks-in-a-nutshell/
作者: Christian Reitwiessner