原标题为《zkSNARKs in a nutshell》，作者是以太坊智能契约语言Solidity的发明者Christian Reitwiessner。译者杨文涛，授权转载自作者之虎专栏。
ZKSARKS(知识的零知识成功非交互arguments)的成功实现给我们留下了深刻的印象，因为你不需要执行它，甚至不需要知道执行的具体内容，就可以确定一个计算的结果是否正确，你知道的唯一信息就是正确完成。不幸的是，大多数关于zkSNARKs的解释都是肤浅的，并且暗示只有最聪明的人才能理解它是如何工作的。事实上，zkSNARKs可以总结为四种简单的技术，本博客将对这些技术逐一进行解释。任何了解RSA加密系统工作原理的人都会对目前使用的zkSNARKs有更好的了解和认识。
我们目前使用的zkSNARKs包含四个主要部分：
a)编码成多项式问题把要验证的程序写成二次多项式方程：t(x) h(x)=w(x) v(x)，这个方程成立当且仅当程序的计算结果正确。证明者需要说服验证者这个等式成立。
b)简单随机抽样的验证者会选择一个私有评价点S，将多项式乘法和验证多项式函数等式的问题简化为简单乘法和验证方程t(s)h(s)=w(s)v(s)的问题。这样做不仅可以减少证明的大小，还可以大大减少验证所需的时间。
c)同态编码/加密译者注：1978年Ron Rivest、Leonard Adleman和Michael L. Dertouzos在《银行的应用背景》中提出了同态加密的概念，当时使用的词是同态，即与抽象代数的同态是一个词。现在普遍使用同态加密，国内密码学界也称之为同态加密。罗恩里维斯特(Ron Rivest)和伦纳德阿德曼(Leonard Adleman)在著名的RSA算法中分别是R和A(阿迪萨莫尔是另一个)。
补充(来自白老师):同态和同胚在数学上不是一回事。同态是指连续变形下的不变性，同态是指映射下代数运算关系的保持性。
我们使用一个编码/加密函数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)
当然这些只是基础部分，为了让读者更好的理解zkSNARKs的精髓，接下来我们会开始详细讲解这些知识点。
RSA和零知识证明现在让我们快速回忆一下RSA是如何工作的，不考虑琐碎的细节。想想看，我们经常用一个数来模化一些数，而不是所有的整数。这里的等式“a b c (mod n)”等价于“(a b)% n=c% n”。注意，“(mod n)”部分不是应用于“c”，而是应用于同一个等式中的“”和其他“”。虽然很难读，但我保证尽量少用。那么让我们回到RSA:
认证机构提供了以下数据：
p，Q:两个随机秘密素数
n :=p q
d: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，我们只说群乘。更准确地说：
用文字描述就是两个加密消息的乘积等于两个消息乘积的加密。
这种同态已经被零乘法知识所证明：证明者知道一些秘密数X和Y，并计算它们的乘积，但只把加密的版本发送给验证者：a=E(x)，b=E(y)，c=E(x y)。验证者检查等式(a b)% n c% n是否为真。此时验证者只知道加密版本的乘积以及乘积是否计算正确，但她不知道两个乘数的真实乘积。如果你用加法而不是乘法，这是一个区块链方向，其主要操作是添加余额。
互动验证我们对零知识的概念有了一定的了解。现在让我们来关注ZKS Snarks的另一个主要特征：简单。之后你会看到这种简单性才是zkSNARKs更牛逼的地方，因为零知识部分的实现是因为这个特定的代码，而这个特定的代码是同态代码的有限形式。
SNARKs是成功的非交互式知识论证的缩写。常规设置被称为交互式协议，因为有一个证明者和一个验证者。证明者希望通过交换信息来说服验证者一个表达式(比如f(x)=y)。一般来说，没有一个证明者能够说服验证者一个错误的表达式(可靠性)，证明者要说服验证者任何真实的表达式(完整性)都必须有一个确定的策略。SNARKs各部分的含义如下：
简洁：与真正需要计算的长度相比，我们发送的信息的大小是非常小的。
非交互：没有或很少交互。对于zkSNARKs来说，是证明者向验证者发送消息后的过程。此外，SNARKs往往有一个属性叫做“公共验证者”(public verifier)，意思是任何人都可以验证，而无需再次交互，这对区块链来说非常重要。
参数：验证器仅对计算能力有限的认证者有效。计算能力足够的证明者可以创建关于错误表达式的证明和参数(注意任何公钥加密系统都可以用足够的计算能力破解)。这也叫“计算可靠性”，还有“完美可靠性”。
知识的：证明者不可能在不知道见证人的情况下构造一组参数和证明(例如哈希函数的原始图像或确定Merkle-tree节点的路径)。
如果加上一个零知识的前缀，那么在交互中就需要一个属性，即验证者除了表达式是否正确之外，什么都不知道。特别是验证者不能知道见证字符串——，这个我们后面会详细解释。
零知识相对正式的定义(还缺少一些细节)是有一个仿真器，可以生成一些设置字段，但是不知道私有见证，也可以和验证者交互——但是外部观察者分不清哪个和验证者交互，哪个和验证者交互。
NP和简化复杂性理论为了理解zkSNARKs可以用于什么问题和计算，我们必须定义一些基于复杂理论的陈述。如果你不知道“见证”是什么，你就算“看”过零知识证明也不会知道它是什么，更不会明白为什么zkSNARKs只适用于特定的多项式问题。如果是这样，那么你可以跳过这一节。
p和NP首先我们把函数限定为只输出0和1，把这样的函数叫做问题。因为您可以单独查询一个长结果的每一位，这不是一个真正的限制，但它可以使定理稍微简单一点。现在我们想衡量一下解决一个给定问题(计算函数)的难度。对于一个数学函数F的具体机器实现M，给定一个输入X，我们可以计算出这个函数F需要的步数——这叫做X在M上的执行时间，这里的“步数”其实不是很重要。因为程序对于较大的输入往往需要更多的步骤，而这个执行时间是用输入值的大小或长度(位数)来衡量的。这是，举例来说，
算法\”源-这是一个当输入值大小为n时，最多需要。
步数的算法。这里的“程序”和“算法”大致相同。
执行时间最多。
该程序也被称为“多项式时间程序”(多项式时间问题)。
复杂性理论中主要有两大类，即P问题和NP问题：
p问题是一类多项式时间的问题。
虽然对于某些问题，k的指数确实很大，但实际上对于那些k不大于4的非人工P问题，仍然被认为是“可解”问题。确认一笔比特币交易是P问题，因为评估后需要多项式时间(而且只能输出0和1)。简单来说，如果只是计算一些值，不“搜索”，那么这个问题就是一个P问题。但是如果你非要搜索某个东西，那么你就进入了另一个范畴，叫做NP问题。
NP类问题
几乎所有的NP问题都是ZKSARKS，今天实践中用到的ZKSARKS一般都是NP问题。我们目前不知道的是是否有不属于NP问题的zkSNARKs。
所有的NP问题都有一个特定的结构，这个结构来自于NP问题的定义：
NP问题是L(多项式时间的程序V)的一类问题。给定一个称为因子见证的多项式标度，这个程序V可以验证这个因子。更正式地说，当且仅当一些多项式规模的字符串W(称为见证)满足V(x，w)=1时，L(x)=1成立。
P=NP？
如果你把NP问题定义为长度为0的见证字符串，那么你会发现这是P问题。所以每个P问题其实都是NP问题。复杂性理论研究的一个主要任务就是找出这两类问题的区别——也就是一个不属于p的NP问题，这里看似显而易见，但如果你能笼统地证明，那么你就能得到100万美元。对了，如果你能反过来证明P和NP是等价的，你也能得到那个加成。而且有很大概率有一天数字货币可以证明。我之所以这么说，是因为找到一个工作问题的解的证明，显然比哈希函数的碰撞或者根据地址找到私钥更容易。这些都是NP问题，因为你刚刚证明了P=NP，所以这些NP问题一定有多项式时间的程序。但本文不会讨论，虽然大多数研究者认为P问题和NP问题是不等价的。
非确定性多项式完全问题
让我们回到SAT。这个看似简单的问题的一个有趣的特点是，它不仅是一个NP问题，而且是一个NP完全问题。“完成”这个词在这里和“图灵完成”是一个意思。这意味着它是NP中最难的问题，但更重要的是，NP是完全定义的。——任何NP问题的输入都可以通过以下方式转化为同一个SAT的输入：
所有NP问题l都有一个可以在多项式时间内计算的“约化函数”f:
L(x)=SAT(f(x))
这样的恢复功能不能算是编译器：编译器是一种机器，可以把用某些编程语言编写的源代码等价地转换成另一种编程语言，也就是具有语义行为的机器语言。因为SAT是NP完全的，所以对于任何可能的NP问题都存在这样的恢复，比如给出一个合适的块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))。
注意，对于R来说，每个替换规则都满足前面陈述的目的，所以R也正确地实现了恢复：
Sat (f)=polyzero (r(f))或f可满足当且仅当r(f)在集合{0，1}中包含0。
见证保存从这个例子可以看出，restore函数只定义了如何转换输入，但是当你仔细看的时候(或者看完如何完成一个可用的restore证据之后)，你就会知道如何用输入转换一个可用的见证。在我们的例子中，我们只定义了如何将函数转化为多项式，但不知道如何将我们解释的证据转化为满足赋值的见证。同时这种见证转换对于事务来说不是必需的，但通常是包含在内的。这对zkSNARKs来说非常重要，因为他给证明者的唯一任务就是让验证者相信这样一个证人的存在，并且不会透露任何关于它的信息。
在二次跨度程序的最后一部分，我们看到了NP问题的计算是如何相互简化的，尤其是那些NP完全问题，基本上又形成了其他NP问题，包括交易验证问题。那么我们就很容易找到一个所有NP问题共有的zkSNARKs:我们只需要选择合适的NP完全问题。所以如果我们想展示如何使用zkSNARKs来验证交易，那么展示如何处理这种确定的NP完全问题是一种有效的方法，并且比理论解释更容易被接受。
接下来是基于论文GGPR12(里面链接的技术报告比原来的干货还多)。本文作者发现了一个叫二次跨度规划(QSP)的问题，完全是为zkSNARKs准备的。二次跨度程序由一组多项式和一个线性组合任务组成，该任务用于查找给定多项式的倍数。此外，输入字符串的每一位都限制了您可以使用的多项式。详细来说(一般来说gsp没那么严格，但我们就是需要这个强限制版本，因为后面会用到):
输入长度为n的域F上的QSP问题由以下部分组成：
这里的任务比较粗糙，就是将多项式乘以一个因子，然后相加(也叫“线性组合”)，使它们的和是t的倍数，对于每一个二进制输入字符串u，函数f限定了可以使用的多项式，或者更严格地说，必须是线性组合的因子。正式的表述是：
注意，当2n小于m时，在选择元组A和b时仍然有很大的自由度。这意味着QSP仅对特定大小的输入有价值。这个问题可以通过使用非均匀复杂度来解决。我们今天不深入讨论非均匀复杂性这个话题。我们只需要知道，当输入值很小时，我们的密码学可以很好地工作。
在这里，我们将不讨论如何把一般的计算和电路问题简化成QSP问题，因为这无助于我们理解基本概念。我们只需要知道QSP是NP完全的(或者比一些非均匀分布的NP/poly问题更完全)。事实上，这种简化是“工程”的一部分。——必须用一种非常巧妙的方法，使QSP问题尽可能小，并具有一些其他优秀的特性。
zkSNARK详解现在我们来详细描述一下QSP上的zkSNARK。它将在初始设置阶段执行每个单独的QSP。在zCash中，事务验证器的行是固定的，因此QSP的多项式也是固定的。该QSP仅允许在设置阶段执行一次，然后在具有不同输入u的所有交易中重复使用。该初始设置将生成公共参考字符串(CRS)。验证者选择一个随机的私有域元素，并在此时加密多项式的值。验证器使用某种特定的加密方法e，并且在CRS中
如何利用零知识简单估计一个多项式？首先，我们来看一个简单的情况，即一个多项式在一个私有点的加密估计，而不是一个完全的QSP问题。
这里的这个例子告诉我们，验证者不需要要求一个完全多项式来证明这一点，而只需要使用配对函数。接下来，我们将添加零知识部分，使验证者无法构造任何关于f(s)的值的信息，即使是E(f(s))这样的加密信息。
好了，现在我们终于知道了一点关于证明者如何在验证者不知道这个值的情况下计算加密的私有点上的多项式加密值。让我们将这些应用于QSP问题。
SNARK的QSP问题的最后一个方程，用来检查是否使用了正确的多项式(这部分还没提到，其他例子会讲到)。需要注意的是，只有知道CRS，证明者才能计算出我们所有的加密值。
验证者现在要做的是：
假设证明者提供了一个正确的证明，让我们检查一下方程是否满足。左右两部分是：
添加零知识
在输入和见证大小之间进行折衷。正如你在上面几节中看到的，我们的证明由一组(即一条椭圆曲线)的7个元素组成。而且验证者的工作就是检查某些配对函数的方程是否成立，是否计算。
这种线性任务遵循输入大小。最重要的是，在这个验证过程中，既不需要见证字符串的大小，也不需要计算工作量来验证QSP(没有SNARKs)。这意味着SNARKs的验证是一个非常复杂的问题，简单的问题往往也是如此。造成这个结果的主要原因是我们只检验了多项式在单点上的一致性，而不是所有的点。多项式可以非常非常复杂，但是一个点始终是一个点。唯一能够影响验证结果的参数是安全级别(如组的大小)和输入值的最大大小。
减少第二个参数，将部分输入值移入witness是可行的：不是验证函数f(u，w)，u是输入，w是见证，我们做一个hash，然后验证：
这意味着我们可以用一个hash来表示输入h(u)(会更短)。除了验证f(x，w)，我们还需要验证某个值X的hash等于H(u)(这种情况下，X很可能等于U)。这将把原始输入u移动到见证字符串中，这将增加见证的大小，但输入值的大小将减少到一个常数。
这简直太神奇了，因为这意味着我们可以在恒定的时间内测试任何复杂的表达式。
ZkSNARKs和以太坊关系密切。
因为验证计算是以太坊区块链的核心，所以zkSNARKs和以太坊是密切相关的。有了zkSNARKs，我们不仅可以完成任何人都可以验证的私密计算，而且可以高效地完成。
虽然以太坊用的是完全图灵的虚拟机，但是目前还无法在以太坊上实现一个zkSNARK。从概念上来说，验证者的任务看似简单，但配对函数确实很难计算，而且在单块中会消耗更多的气体。椭圆曲线的乘法相对复杂，而配对函数又给这种复杂性增加了一个层次。
现有的zkSNARK系统，如zCash，对每个任务都使用相同的问题，电路计算。在zCash中，它是交易验证。在以太坊上，ZKSARKS不会只做一道计算题，而是让每个人都建立自己的ZKSARKS系统，而不用发布新的区块链。每一个加入以太坊的zkSNARK系统都需要一个新的私有可信的准备阶段(有些可以重用，有些不能)，比如生成一个新的CRS。例如，可以将zkSNARK系统添加到“通用虚拟机”中。这样，当您使用新实例时，您不需要重置它，因为您不需要在以太坊上为新的智能合约发布新的区块链。
如何在以太坊上启用ZKSARKS在以太坊上启用ZKSARKS的方法有很多。所有的方法对于配对函数和椭圆曲线运算(其他必要的运算比较简单)都可以减少实损耗，所以也要减少这些运算所消耗的气体。
提高(确保)EVM的绩效。
仅在确定的配对函数和椭圆曲线乘法上提高EVM的性能。
第一项从长期来看显然会获得不错的回报，但是实现起来比较困难。我们现在给EVM增加了一些新的功能和限制，比如更好地支持及时编译和解释器的实现，只需对现有实现做最小的改动。当然，也不排除直接用eWASM代替EVM。
第二项可以通过强制所有以太坊客户端执行某种配对函数和某种称为预编译契约的椭圆曲线乘法来实现。这样做的好处是实现起来简单快捷。缺点是我们会固定在某个配对函数和某个椭圆曲线上。以太坊上的所有新客户端都必须再次实现这个预编译的契约。所以，如果有什么新的进展，或者有人能找到zkSNARKs的更好的方法，更好的配对函数，更好的椭圆曲线，或者找到椭圆曲线，配对函数和zkSNARK的一些缺点，那么我们会把它添加到新的预编译契约中。
