雷锋网：原标题为《zkSNARKs in a nutshell》，作者是Christian Reitwiessner，以太坊智能契约语言Solidity的发明者。译者杨文涛，授权转载自作者之虎专栏。
ZKSARKS(Zero-Knowledge Succint Non-Interactive Arguments of Knowledge)的成功实现让我们印象深刻，因为你可以在不执行计算，甚至不知道执行的具体内容的情况下，确定一个计算的结果是否正确。你知道的唯一信息就是正确完成。不幸的是，大多数关于zkSNARKs的解释都很肤浅，并且暗示只有最聪明的人才能理解它是如何工作的。事实上，zkSNARKs可以总结为四种简单的技术，本博客将对这些技术逐一进行解释。了解RSA加密系统工作原理的人对目前使用的zkSNARKs会有更好的了解。
我们目前使用的zkSNARKs包含4个主要部分：
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是否为真。此时验证者只知道加密的乘积和乘积是否计算正确，但她不知道两个乘数和真实乘积。如果你用加法而不是乘法，这是一个区块链方向，其主要操作是添加平衡。
互动验证我们对零知识的概念有了一定的了解。现在让我们来关注zkSNARKs的另一个主要特点：简洁。之后你会看到这种简单性是zkSNARKs更强大的部分，因为零知识部分的实现是由于这个特定的代码，它是一个有限形式的同态代码。
SNARKs是简洁的非交互式知识论证的缩写。常见的设置被称为交互式协议，因为有一个证明者和一个验证者。证明者想通过交换信息让验证者相信一个表达式(比如f(x)=y)。一般来说，没有证明者能让验证者相信一个虚假的表达式(可靠性)，证明者必须有一个确定的策略才能让验证者相信任何一个真实的表达式(完整性)。SNARKs各部分的意义如下：
简洁：与真正需要计算的长度相比，我们发送的信息的大小是非常小的。
非交互：没有或很少交互。对于zkSNARKs来说，是证明者向验证者发送消息后的过程。此外，SNARKs通常有一个名为“公共验证者”的属性，这意味着任何人都可以验证而无需再次交互，这对区块链来说至关重要。
论据：Verifier只对计算能力有限的证明者有效。有足够计算能力的证明者可以创建关于错误表达式的证明和参数(注意，只要他有足够的计算能力，任何公钥加密系统都可以被破解)。这也叫“计算可靠性”，是相对于“完美可靠性”而言的。
知识的：证明者不可能在不知道见证人的情况下构造一组参数和证明(例如哈希函数的原始图像或确定Merkle-tree节点的路径)。
如果加上零知识的前缀，那么在交互中就需要一个属性，即验证者除了表达式是否正确之外什么都不知道。特别是验证者不能知道见证字符串——。我们稍后会解释它是什么。
零知识相对正式的定义(还缺少一些细节)是有一个模拟器，可以生成一些设置字段，但是不知道私有见证人，也可以和验证者交互——但是外部观察者分不清哪个和验证者交互，哪个和证明者交互。
NP与简化复杂性理论。为了理解zkSNARKs可以用于哪些问题和计算，我们必须定义一些基于复杂理论的陈述。如果你不知道“见证”是什么，那么你就算“看”过零知识证明也不会知道它是什么，更不会知道为什么zkSNARKs只适用于特定的多项式问题。如果是这样，那么你可以跳过这一节。
P NP首先，我们把函数限制为只能输出0和1，把这样的函数叫做问题。因为您可以单独查询长结果的每一位，所以这不是真正的限制，但它可以使定理稍微简单一点。现在我们要衡量解决一个给定的问题(计算函数)有多“难”。给定一个输入x，我们可以计算出特定机器实现一个数学函数f需要的步骤数——这叫做x在m上的执行时间，这里的步骤数其实并不是很重要。因为程序对于较大的输入往往需要更多的步骤，而这个执行时间是用输入值的大小或长度(位数)来衡量的。这是如“
“算法”的来源——这是输入值为n时最多需要的一个。
步骤的算法。这里的“程序”和“算法”大致相同。
执行时间最多。
该程序也被称为“多项式时间程序”(多项式时间问题)。
复杂性理论中有两大类，它们是P问题和NP问题：
p问题是一类多项式时间的问题。
虽然对于某些问题来说k的指数确实很大，但实际上对于那些非人工的，k不大于4的P问题仍然被认为是“可解”的问题。确认一个比特币交易是一个P问题，因为评估后需要一个多项式时间(并且只能输出0和1)。简单来说，如果只是计算一些值而没有“搜索”，那么这个问题就是P问题。但是如果你非要搜索某个东西，那么你就进入了另一个范畴，叫做NP问题。
NP类问题
几乎所有的NP类问题都是zksark，今天实践中用到的zksark都是一般意义上的NP类问题。我们还不知道的是，是否存在不属于NP问题的zkSNARKs。
的所有NP问题都有一个特定的结构，这个结构来自于NP问题的定义：
NP问题是L(多项式时间的程序V)的一类问题。给定一个称为因子的多项式尺度的见证，这个程序V可以验证这个因子。更正式地说，L(x)=1成立当且仅当一些多项式标度串w(称为见证)满足V(x，w)=1。
P=NP？
如果你把NP问题定义为长度为0的见证字符串，那么你会发现这是P问题。所以每个P问题其实都是NP问题。复杂性理论研究的一个主要任务就是发现这两类问题的区别——也就是一个不属于p的NP问题，这里看似显而易见，但如果你能笼统地证明，那么你就能得到100万美元。对了，如果你能反过来证明P和NP是等价的，你也能得到那个加成。而且有很大概率有一天数字货币会证明这一点。我之所以这么说，是因为找到一个工作问题的解的证明，显然比哈希函数的碰撞或者根据地址找到私钥更容易。这些都是NP问题，因为你刚刚证明了P=NP，那么这些NP问题一定有多项式时间的程序。但我不会在本文中讨论，虽然大多数研究者认为P问题和NP问题是不等价的。
非确定性多项式完全问题
让我们回到SAT。这个看似简单的问题的一个有趣的特点是，它不仅是NP完全的，而且是NP完全的。“完全”这个词在这里和“图灵完全”的意思一样。这意味着它是NP中最难的问题，但更重要的是NP的完整定义。3354任何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))(1-(1-x))。
注意，对于R，每一个替换规则都满足前面所述的目的，所以R也正确地实现了恢复：
而sat (f)=polyzero (r(f))或f只有在r(f)包含集合{0，1}中的一个0时才能满足。
见证保存从这个例子可以看出，restore函数只定义了如何转换输入，但是当你仔细看的时候(或者看完如何完成一个可用的restore证据之后)，你就会知道如何用输入转换一个可用的见证。在我们的例子中，我们只定义了如何将函数转换为多项式，但不知道如何将我们解释的证据转换为满足赋值的见证。同时这种见证转换对于事务来说不是必需的，但通常是包含在内的。这对zkSNARKs来说非常重要，因为他给证明者的唯一任务就是让验证者相信有这样一个证人，他不会透露任何关于证人的信息。
二次跨度程序上一部分我们看到了NP问题的计算是如何简化的，尤其是那些NP完全问题，基本上又形成了其他NP问题，包括交易验证问题3354。那么我们就很容易找到一个所有NP问题共有的zkSNARKs:我们只需要选择合适的NP完全问题。所以如果我们想展示如何使用zkSNARKs来验证事务，那么展示如何处理这个确定的NP-完全问题是一个有效的方法，而且比理论解释更容易被接受。
接下来是基于论文GGPR12(本文链接的技术报告比原干货多)。本文作者发现了一个叫二次跨度规划(QSP)的问题，完全是为zkSNARKs准备的。二次跨度程序由一组多项式和寻找给定多项式倍数的线性组合任务组成。此外，输入字符串的每一位都限制了您可以使用的多项式。详细来说(一般来说GSPs限制没那么严格，但我们就是需要这个强限制版本，因为后面会用到):
输入长度为n的域f上的QSP问题由以下部分组成：
这里的任务比较粗略，就是将多项式乘以一个因子，然后相加(也叫“线性组合”)，使它们的和是t的倍数，对于每一个二进制输入字符串U，函数F限定了可以使用的多项式，或者更严格地说，必须是线性组合因子。官方的表述是：
注意，这里，当2n小于m时，仍然有很大的自由度来选择元组A和b。这意味着QSP仅对于特定大小的输入有价值。这个问题可以通过使用非均匀复杂度来解决。今天就不深入讲解非一致复杂度这个话题了。我们只需要知道，当输入值很小时，我们的密码学可以很好地工作。
这里不讨论如何把一般的计算和线问题简化成QSP问题，因为这对我们理解基本概念没有帮助。我们只需要知道QSP是NP完全的(或者比一些非均匀分布的问题如NP/poly更完全)。事实上，这种简化是一个“工程”部分3354，必须使用一种巧妙的方法使QSP问题尽可能小，并具有一些其他优秀的特征。
zkSNARK详解现在我们来详细描述一下QSP上的zkSNARK。它在初始设置阶段执行每个单独的QSP。在zCash中，交易验证符的行是固定的，所以QSP的多项式也是固定的。该QSP仅允许在设置阶段执行一次，然后在具有不同输入u的所有交易中重复使用。该初始设置将生成公共参考字符串(CRS)。验证者选择一个随机的私有域元素，并在此时加密多项式值。验证者使用一些特定的加密方法e并在CRS中使用它们
如何利用零知识简单估计一个多项式？首先，我们来看一个简单的情况，即一个多项式在一个私有点的加密估计，而不是完全的QSP问题。
这里的这个例子告诉我们，验证者不需要要求一个完整的多项式来证明这一点，只需要使用配对函数即可。下一步，我们将添加零知识的部分，这样验证者就无法构造任何关于f(s)的值，甚至是E(f(s))这样的加密信息。
好了，现在我们终于知道了一点，当验证者不知道加密私有点上的多项式加密值时，证明者是如何计算这个值的。接下来，让我们将这些应用于QSP问题。
用QSP问题的SNARK的最后一个方程来检验是否使用了正确的多项式(这部分还没有提到，其他例子会讲到)。注意，我们所有的加密值都可以由只知道CRS的证明者来计算。
现在验证者必须这样做：
假设证明者提供了正确的证明，让我们检查方程是否满足。左右两部分是：
添加零知识
在输入和见证大小之间取一个折衷值。正如你在上面的小节中看到的，我们的证明由一组(即一条椭圆曲线)的7个元素组成。而且验证者的工作就是检查某些配对函数的方程是否成立，并进行计算。
这样一个遵循输入大小的线性任务。最重要的是，在这个验证过程中，既不需要证明串的大小，也不需要计算量来验证QSP(没有SNARKs)。这意味着对SNARKs的验证是一个非常复杂的问题，而简单的问题往往也是如此。造成这个结果的主要原因是我们只检查多项式在单点的一致性，而不是所有的点。多项式可以非常非常复杂，但是一个点始终是一个点。唯一能够影响验证结果的参数是安全级别(如聚类的大小)和输入值的最大大小。
减少第二个参数并将输入值的一部分移入witness是可行的：不是验证函数f(u，w)，其中u是输入，w是witness，我们做一次散列，然后验证：
这意味着我们可以用一个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的一些不足，那么我们会把它加入到新的预编译契约中。
