0
| 本文作者： AI金融评论 | 2017-12-29 11:03 |
雷锋网按：原文标题为《zkSNARKs in a nutshell》，作者是以太坊智能合约语言Solidity的发明人Christian Reitwiessner。译者杨文涛，授权转载自作者知乎专栏。
zkSNARKs（zero-knowledge succint non-interactive arguments of knowledge）的成功实现让我们印象深刻，因为你可以在不执行，甚至在不知道执行具体内容的情况下确定某个计算的结果是否正确——而你唯一知道的信息就是它正确地完成了。但是不幸的是，大多数关于 zkSNARKs 的解释都浮于表面，并暗示只有最聪明的人才能懂得它的工作原理。实际上，zkSNARKs 可以总结为 4 个简单的技术，本篇博客将会逐一解释这些技术。任何懂得 RSA 加密系统工作原理的人都会对当前使用的 zkSNARKs 有一个更好的理解和认识。
我们当前使用的 zkSNARKs 包含 4 个主要部分：
把需要验证的程序编写成一个二次的多项式方程：t(x) h(x) = w(x) v(x)，当且仅当程序的计算结果正确时这个等式才成立。证明者需要说服验证者这个等式成立。
验证者会选择一个私密评估点 s 来将多项式乘法和验证多项式函数相等的问题简化成简单乘法和验证等式 t(s)h(s) = w(s)v(s) 的问题。这样做不但可以减小证明的大小，还可以大量地减少验证所需的时间。
译者注：在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) 和一些其他有用的加密信息。
证明者通过乘以一个数来替换 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 是如何工作的，先不管那些琐碎的细节。想想看，我们经常用一个数字对一些数字取模，而并不是所有的整数。这里的等式 “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 通过下面的公式加密：
c = E(m) 通过下面的公式解密：
因为 
，并且 m 的指数就是对 (p-1)(q-1) 这一组数取模，这样我们就得到了
（译者注：可以由费马小定理和中国剩余定理推出）。而且 RSA 的安全性是基于假设：n 不能被轻易有效的因式分解，d 不能通过 e 计算得到（如果我们知道 p 和 q 的话，就可以轻易得到我们想要的值）。
RSA 的一个牛逼的特性是同态乘法。通常来讲，如果你可以交换两个操作的顺序而不影响计算结果，那么我们就说这两个操作是同态的。在同态加密中，这就是你可以对加密数据进行计算的一个属性。完全同态加密是存在的，但是现在还没有应用到实际中，它能够对任何基于加密数据的程序完成计算。在这里对于 RSA 来说，我们只谈论 group multiplication。更准确的说就是：
，用文字描述就是：两个加密信息的乘积等于两个信息乘积的加密。
这个同态的特性已经有一些乘法的零知识证明了：证明者知道一些私密的数字 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 ——稍后我们会详细解释这是什么。
关于零知识的部分相对正式的定义（仍然缺乏一些细节）就是：存在一个模拟器，它可以生成一些设置字段，但是却不知道私密的 witness，它还可以和验证者交互 -- 但是外部的观察者却不能分辨出哪个与验证者进行的交互，哪个是与证明者进行的交互。
为了了解 zkSNARKs 能用于哪些问题和计算，我们不得不基于复杂的理论定义一些说法。如果你不知道什么是 “witness” 的话，那么即使『读』完零知识证明你也不会知道它是什么，并且你也不会了解到为什么 zkSNARKs 只适用于特定的多项式问题，如果真是这样的话，那么你就可以跳过本节了。
首先，我们限制函数只能输出 0 和 1，并称这样的函数为问题（problems）。因为你可以单独的查询一个长长的结果的每一位（bit），所以这不是一个真正的限制，但是这样可以让定理变的简单一点。现在我们想衡量解决一个给定的问题（计算函数）到底有多『难』。对于一个数学函数 f 的特定机器的实现 M，给定一个输入 x，我们可以计算出这个函数 f 需要的步数 -- 这就叫做 x 在 M 上的执行时间，这里的『步数』其实不太重要。因为程序对于更大的输入往往会需要更多的步数，而这个执行时间则是用输入值的大小或者说长度（bit 的数量）来衡量。这就是例如『 
算法』的来源 -- 这就是一个当输入值大小为 n 时，至多需要 
个步数的算法。这里的『程序』和『算法』广义上是相同的。
执行时间至多为 
的程序也叫做 “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 成立。
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 ∧ 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 和 输入一起转换。在我们的例子中，我们只定义了如何将函数转换为多项式，但是不知道如何将我们解释的证据转换成满足赋值的 witness。这个 witness 在同一时间转换对于交易来说不是必要的，但是通常都会包含。而这对于 zkSNARKs 来说是至关重要的，因为对于证明者来说他唯一的任务就是让验证者相信有这样一个 witness 存在，并且还不会暴露任何有关 witness 的信息。
在上一部分中，我们看到了 NP 问题的计算是如何被相互化简的，尤其是那些 NP 完全问题，那些 NP 完全问题基本上又都再次形成了其他的 NP 问题——包括交易验证问题。那么对我们来说找到一个对所有 NP 问题都通用的 zkSNARKs 就变的很容易了：我们只需要选择适合的 NP 完全问题。所以如果我们想展示如何使用 zkSNARKs 来验证交易的话，那么展示如何处理这个确定的 NP 完全问题就是一个有效的方法，并且比从理论上解释更容易让人接受。
接下来就是基于论文GGPR12（这里面链接的技术报告比原文的干货更多）来谈了，这篇论文的作者发现了一个叫做 Quadratic Span Programs（QSP）的问题，这个问题完全就是为 zkSNARKs 准备的。一个 Quadratic Span Program 是由一组多项式和寻找给定多项式倍数的线性组合任务构成。此外，输入字符串的每个单独的 bit 都限制了你能够使用的多项式。详细来说（通常来讲 GSPs 限制不是那么严格，但是我们就是需要这种强限制的版本，因为后面我们会用到）就是：
对于输入长度为 n 的在域 F 上的 QSP 问题由下面这些部分构成：
这里的任务很粗糙，就是给多项式乘以一个因子并把它们加起来（也叫做『线性组合』）使得它们的总和是 t 的倍数。对于每一个二进制输入字符串 u 来说，函数 f 限制了可以被使用的多项式，或者更严格的讲就是它们必须是线性组合的因子。正式的表示就是：
注意，在这里当 2n 小于 m 时，选择元组 a 和 b 仍然是有很大的自由度的。这就意味着 QSP 只对特定大小的输入是有价值的——这个问题可以通过使用非均匀复杂度来解决，非均匀复杂度这个话题今天我们不会深入的讲解，我们只需要知道当输入值很小时，我们的密码学也能良好运转。
这里我们不会讨论如何将通用计算和线路问题简化成 QSP 问题，因为这对于我们了解基本概念没有任何帮助，我们只需要知道 QSP 是 NP 完全（或者说比一些非均匀分布的像 NP/poly 问题更完全）的就好了。实际上，这个简化是一个『工程』部分——必须要使用一种很聪明的方法才能让 QSP 问题尽可能的小并且有一些其他的优良特性。
现在让我们来详细的描述一下 QSP 上的 zkSNARK。它在开始设置阶段会执行每一个单独的 QSP。在 zCash 中，交易验证者的线路是固定的，因此 QSP 的多项式也是固定的，这个 QSP 在设置阶段只允许被执行一次，然后在所有的只有输入 u 不同的交易上复用。这个开始的设置会生成一个公共参考串（common reference string，CRS），验证者选择一个随机且私密的域元素，并在这个点加密多项式的值。验证者使用一些特定的加密方法 E 并在 CRS 中
首先让我们先来看一种简单的情况，即一个多项式在私密点上的加密估值，而不是完整的 QSP 问题。
这里的这个示例告诉我们验证者并不需要求出完整的多项式来证明这一点，仅仅使用配对函数就可以了。下一步我们就要添加零知识的部分了，这样验证者就不能构建任何关于 f(s) 值了，甚至连 E(f(s)) 这种加密信息也不行。
好的，现在我们总算知道了一点关于在验证者不知道那个值的情况下，证明者是如何在一个加密的私密点上面计算出多项式加密值的。接下来让我们把这些应用到 QSP 问题中吧。
最后一个等式用来检验是否使用了正确的多项式（这一部分还没有讲到，不过其他的例子会说到它）。要注意的是，我们所有的加密值，证明者只需要知道 CRS 就可以全部推算出来。
而验证者现在要做的还有这些：
假设证明者提供了一个正确的证明，让我们检验一下等式是否满足。左边和右边的部分分别是：
就像你在上面这些小节中看到的一样，我们的证明由一个群（就是一个椭圆曲线）的 7 个元素组成。而且验证者的工作就是检验一些配对函数的等式是否成立以及计算 
这样一个跟随输入大小的线性任务。最主要的是，在这个验证过程中，既不需要 witness 字符串的大小，又不需要计算工作量来验证 QSP（没有 SNARKs）。这就意味着 SNARKs 的校验是个很复杂的问题，而简单的问题往往都是一样的。造成这个结果的主要原因则是，因为我们只在一个单独的点上面检验了多项式的一致性，而不是全部的点。多项式可以变的非常非常复杂，但是一个点始终是一个点。而唯一能影响到验证结果的参数就是安全性的等级（比如群的大小）和输入值的最大尺寸。
减小第二个参数是可行的，将输入值的一部分移动到 witness 中：我们不验证函数 f(u, w)，u 是输入，w 是 witness，而是做一次 hash，然后验证：
这样就意味着我们可以用一个 hash 来代表输入 h(u) 了（这样就会变的更短），除了验证 f(x, w)，我们还需要验证某个值 x 的 hash 等于 H(u)（这样的话，那 x 极有可能就等于 u 了）。这样就将原始输入 u 移动到 witness 字符串中了，这样虽然会增大 witness 的大小，但是输入值的大小就减小为一个常数了。
这简直太厉害了，因为这意味着我们可以在常数时间内完成对任何复杂表达式的检验。
zkSNARKs 和 Ethereum 关系紧密
因为验证计算是 Ethereum 区块链的核心，所以 zkSNARKs 和 Ethereum 关系紧密相连。有了 zkSNARKs，我们不但可以完成任何人都可证实的私密的计算，而且还可以高效的完成。
虽然 Ethereum 使用了一个图灵完备的虚拟机，但是当前在 Ethereum 上实现一个 zkSNARK 还是不可能的。从概念上讲，验证者的任务似乎很简单，但是配对函数是真的很难计算，而且在单个区块中还会消耗更多的 gas。椭圆曲线的乘法相对来讲已经非常复杂了，而配对函数将这个复杂度又增加了一个级别。
像 zCash 这种现存的 zkSNARK 系统对每一个任务都使用的是同样的问题，circuit 计算。在 zCash 中，就是交易验证。在 Ethereum 上，zkSNARKs 将不会只单单做一个计算问题，而是让所有的人都能够在不发布一个新的区块链的情况下构建他们自己的 zkSNARK 系统。每一个添加到 Ethereum 上的 zkSNARK 系统都需要进行一个新的私密的可信任的准备阶段（一些可以复用，一些不能），比如生成一个新的 CRS。像为一个『通用虚拟机』添加 zkSNARK 系统将会变的可能。这样的话当你使用一个新的实例时，你就不需要重新设置了，因为你将不再需要为 Ethereum 上新的智能合约发布一个新的区块链。
在 Ethereum 上启用 zkSNARKs 有很多种方式。所有的方式都可以为配对函数和椭圆曲线操作（其他必要的操作都很简单）减小真实的损耗，因此我们也要减小这些操作消耗的 gas。
提升（确保）EVM 的性能
只在确定的配对函数和椭圆曲线乘法上提升 EVM 的性能
第一项在长期显然会得到很好的回报，但是实现起来难度比较大。我们现在已经在对 EVM 添加一些新的功能和限制了，例如更好的支持及时编译以及在现存实现下最小改动的解释器的实现。当然也不排除直接用 eWASM 来替换 EVM。
第二项则可以通过强制所有的 Ethereum 客户端执行一个确定的配对函数和确定的椭圆曲线乘法的叫做预编译合约的东西来实现。这样做的好处就是实现起来既简单又快速。而缺点呢则是这样做我们就会固定在一个确定的的配对函数和一个确定的椭圆曲线上。所有 Ethereum 上新的客户端都不得不再实现一遍这个预编译合约。所有，如果有什么新的进展，或者有人可以找到更好的 zkSNARKs 的方法，更好的配对函数，更好的椭圆曲线，又或者发现了椭圆曲线，配对函数和 zkSNARK 的一些缺点，那么我们就会添加到新的预编译合约中。
雷峰网版权文章，未经授权禁止转载。详情见转载须知。
