学术向 | 深入浅出zkSNARKs

zkSNARKs的成功性令人印象深刻，因为你可以在不执行，甚至不知道执行的具体内容是什么的情况下确定某个计算的结果是否正确 -- 而你唯一知道的信息就是它正确的完成了。不幸的是，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）同态编码/加密
使用具有一些同态属性的编码/加密函数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）），以便验证者再不知道实际的编码值仍然可以检查它们的正确性结构。
有一个粗糙的想法是这样的，因为校验 t(s)h(s) = w(s)v(s) 和校验 t(s)h(s) k =w(s)v(s) k（对于一个不等于 0 的私密的随机数 k 来说）几乎是完全一样的，而不同的地方在于如果你只接收到了 (t(s)h(s) k) 和 (w(s)v(s) k) 那么从中获取到 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 qd：1 lt; d lt; 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。 因为cd≡（me％N）d≡med（mod n），m的指数就是对（P-1）（Q-1）这组数取模，我们得到med ≡m（mod n）。此外，RSA的安全性依赖于这样的假设：n不能轻易被因式分解，因此d不能从e计算（如果我们知道p和q，这将是容易的）。
RSA 的一个牛逼的特性是同态乘法。通常来讲，如果你可以交换两个操作的顺序而不影响计算结果，那么我们就说这两个操作是同态的。在同态加密中，这就是你可以对加密数据进行计算的一个属性。完全同态加密是存在的，但是现在还没有应用到实际中，它能够对任何基于加密数据的程序完成计算。在这里对于 RSA 来说，我们只讨论组乘法。更正式地：E（x）E（y）≡xe y e ≡（xy）e≡E（xy）（mod n），文字描述就是：两个加密消息的的乘积等于两个信息乘机的加密。
这种同态性已经允许某种零知识的乘法证明：证明者知道一些秘密数字x和y并计算它们的乘积，但只发送加密版本a= E（x），b = E（y）和c = E（xy）到验证者。验证者现在检查（ab）％n≡c％n 是否成立，此时验证者只知道加密版的乘积以及乘积是否被正确的计算，但是她不知道两个乘数和真正的乘积。如果你用加法来替代乘法，那就是一个主要操作为添加余额的区块链方向了。
交互验证

我们已经对零知识这个概念有了一定的了解了，让我们现在关注zkSNARKs的另一个主要特征，即简洁性。正如您稍后将看到的，简洁性是zkSNARKs中更为显着的部分，因为由于某种编码允许有限形式的同态编码，零知识部分将“免费”给出。
SNARKs 是 succinct non-interactive arguments of knowledge 的缩写。一般都通用设置之所以叫做交互式协议，是因为这里有一个证明者和一个验证者，证明者想要通过交换信息的方式让验证者相信一个表达式（比如 f(x) = y）。一般来说，没有证明者可以让验证者相信一个错误的表达式（可靠性），而且对于证明者来说一定存在一个确定的策略让验证者相信任何真实的表达式（完整性）。SNARKs 各个部分的的意义如下：
简洁：与实际计算的长度相比，消息的大小很小 非交互式：没有或者只有很少很少的交互。对于 zkSNARKs 来说就是在证明者向验证者发送一条信息之后的过程。此外，SNARKs 还常常拥有叫做『公共验证者』的属性，它的意思是在没有再次交互的情况下任何人都可以验证，这对于区块链来说是至关重要的。 参数：验证者仅受到计算限制的证明者的保护。具有足够计算能力的证明器可以创建关于错误语句的证明/参数（注意，如果具有足够的计算能力，则可以破坏任何公钥加密）。这也称为“计算可靠性”，而不是“完美可靠性”。 知识：对于证明者来说在不知道一个叫做证据（witness）（比如一个哈希函数的原象或者一个确定 Merkle-tree 节点的路径）的情况下，构造出一组参数和证明是不可能的。
如果你添加了零知识的前缀，那么在交互中你就需要一个性质，即验证者除了知道表达式的正确与否之外其他一无所知。尤其是验证者不能知道 见证字符串 稍后我们会详细解释这是什么。
举个例子，让我们考虑下面的交易验证计算：当且仅当 σ 1 和σ2 是账户默克树s（pre 和 post 状态）的根哈希，s 和 r 是发送者和接收者账户， PS和PR 是默克树 的证明（当 v 从 s 的余额中转移到 r 的余额的过程中，能够证明在 中 s 的余额至少是 v 并且他们的哈希结果是 而不是 ），这些条件都成立时，f（σ1，σ2，s ,r,v,ps,pr,v) 成立。
如果所有输入都已知，则验证f的计算相对容易。正因为如此，我们可以将F转换成一个zkSNARK，其中只有σ 1和σ 2是公开的和（s ,r,v,ps,pr,v）是witmess-string。零知识属性现在会使得验证者能够检查证明方是否知道一些见证，它可以将根哈希从σ 1转换至σ 2，而这样的转换又不影响正常的交易，但是验证者却不知道到底是谁发送了多少钱给谁。
关于零知识的部分相对正式的定义（仍然缺乏一些细节）就是：存在一个模拟器，它可以生成一些设置字段，但是却不知道私密的证人，它还可以和验证者交互 -- 但是外部的观察者却不能分辨出哪个与验证者进行的交互，哪个是与证明者进行的交互。
为了了解zkSNARKs可以用于哪些问题和计算，我们必须从复杂性理论中定义一些概念。如果你不关心“见证”是什么，那么即使在“阅读”零知识证明之后你也不会知道他是什么，并且你也不会了解到为什么 zkSNARKs 只适用于特定的多项式问题，如果真是这样的话，那么你就可以跳过本节了。
p和NP

首先，我们限制函数只能输出 0 和 1，并称这样的函数为问题。因为您可以单独查询较长结果的每个位，所以这不是一个真正的限制，但它可以使理论更容易。现在我们要测量解决给定问题（计算函数）的“复杂程度”。对于数学函数f的特定机器实现M，我们总是可以计算在特定输入x上计算f所需的步数 - 这称为x在M上的运行时间。究竟什么是“步骤”，在这种情况下并不太重要。由于程序对于更大的输入旺旺需要更多的步数，而运行时间以输入的大小或长度（位数）来衡量的。这就是例如”n2 算法”的来源 -- 这就是一个当输入值大小为 n 时，至多需要n2 个步数的算法。这里的”程序”和”算法”广义上是相同的。
对于某些k，其运行时间最多为n k的程序也称为“多项式时间程序”。
复杂性理论中的两个主要问题类型是P和NP：
P是具有多项式时间程序的一类问题类 虽然 k 的指数对于一些问题来说确实非常大，但是实际上对于那些非人造的，k 不大于 4 的 P 问题仍然被认为是可以“解决的”的问题。要确认一笔比特币的交易就是一个 P 问题，因为经过评估它需要一个多项式时间（并且只能输出 0 和 1）。简单的说就是，如果你只是计算一些值而不去“搜索”，那么这个问题就是 P 问题。但是如果你不得不搜索一些东西，那么你就会进入到另一个叫做 NP 问题的类别中。
NP类问题

对于NP类中的所有问题都是zkSNARK，实际上，现在存在的实际使用的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）”也是一个布尔函数。
如果有一种方法可以将真值赋给变量，那么布尔函数是可以满足的，这样公式的计算结果为真（其中σ为真，¬false为真，true∧false为假，依此类推）。可满足性问题SAT是所有可满足的布尔函数的集合。
当且仅当 f 是一个可满足函数且不是 0 时，SAT(f) := 1 成立 上面的例子中，“（（X 1 ∧X 2）∧¬x 2）”，是不符合要求的，因此它不属于SAT。证明一个给定公式满足定义并且同时确保它赋值的变量也是可满足的就是一个可以在多项式时间内被解决的问题。
P=NP?

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

让我们回到SAT。这个看似简单的问题的有趣特性是它不仅存在于NP中，而且还是NP完全问题。这里的“完整”一词与“图灵完整”中的完整相同。这意味着它是NP中最难的问题之一，但更重要的是这就是NP完全的定义 - NP中任何问题的输入都可以转换为SAT的等效输入，具体如下： 所有 NP 问题 L 都有一个在多项式时间可计算的”还原函数”f： L（x）= SAT（f（x）） 这样的一个还原函数不能被看成一个编译器：编译器是可以将一些编程语言写的源代码等价的转换成另一种编程语言的机器，也就是拥有语义行为的机器语言。因为 SAT 是 NP 完全的，所以这样一个还原对于任何可能的 NP 问题都是存在的，比如给定一个合适的块哈希，验证一笔比特币交易是否合法。这里还可以将一笔交易转换成一个布尔函数的还原函数，因此当且仅当这个交易是合法的时候这个布尔函数就是可满足的。
还原示例

为了弄明白这样一个还原的方法，让我们先考虑评估多项式的问题。首先，让我们定义一个由整数常量，变量，加法，减法，乘法和（正确匹配的）括号构成的多项式（类似于布尔函数）。现在让我们考虑下面的问题： 如果 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对应于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 的信息。（未完待续）