新型零知识证明，背后的“隐身”大法是什么？

希望现在很多人都听说过ZK-SNARKs协议，这是零知识证明技术的通用性说法，使用它的案例从可验证的计算到私人保护的数字货币。也许你不知道，ZK-SNARKs协议有更新的版本，ZK-STARKs。其中改变的字母T代表的是“透明”，ZK-STARKs解决ZK-SNARKs的其中一个弱势，它依赖于一种“可信任的配置”。而且ZK-STARKs也有更加简单的加密假设，从而避免椭圆曲线，配对以及指数假设的知识，而是仅仅依赖于哈希和信息的理论；这也就意味着他们对于量子计算机的攻击来说，是安全的。

但是，这也会有代价：证明的存储大小也从288字节增加到几百千兆字节。有时候这个代价并不值得，但是有时候，特别是在讨论公链应用的时候，需要的最小信任非常高，事情就很可能这样。并且如果椭圆曲线打破或者量子计算机真地出现，这事情就肯定会发生。

所以这种零知识证明是如何工作呢？首先，让我们来看看通用的ZKP协议是做什么的。假设你现在有一个公开函数f，一个私密的输入x以及一个公开的输出y。你想要证明你知道一个x，从而得到f(x) = y，而不用泄露x是什么。并且，为了保证这个协议足够简单，你想要它的验证比计算f本身还要快。

让我们来举个例子：

f 是一个需要在普通计算机上运行2周的计算，但是在数据中心只需要2小时。你给数据中心发送了这个计算（也就是说，运行f的代码），然后数据中心就会运行，并且通过证明反馈了答案y。你在几毫秒之内，就验证了这个证明，并且相信y其实就是答案。

你有一个加密的交易，表格中的X1是我之前的余额。X2是你之前的余额。X3是我新的余额。X4是你新的余额。你想要创建一个证明，其中这个交易是有效的（特别指出，之前和现在的余额都是正的，而且我余额的减少抵消了你余额的增加）。x可以是秘钥对，并且f可以是一个函数，其中包含了内置公开输入的交易，而且作为输入秘钥，解密了交易，完成了检验，如果通过就返回1，如果失败就返回0。y 当然会是1。

你有个类似以太坊的区块链，而且你下载了最近的区块。你想要一个证明，表示这个区块是有效的，而且这个区块是在链的顶端，其中链上任何区块都是有效的。你想让一个现存的全节点来提供这样的验证。x是整个区块链，f是区块处理的函数，验证有效性并且输出最后区块的哈希，而且y就是你之前下载区块的哈希。

所以这些问题的困难点在哪呢？就像它表现出来的，需要很容易为零知识证明（也就是，隐私性）提出保证；现在有很多种方法来将任何计算转换为例如三色图表问题的情况，其中图表的三种颜色都对应原始问题的解决方案，然后使用传统的零知识证明协议来证明，你即使不揭露它的信息，也可以获得有效的图表颜色。

更困难的地方在于提供简洁性。直观地来说，证明关于计算简洁性是困难的，因为计算是难以置信地脆弱。如果你有个很长很复杂的计算，那么你需要有能力在计算过程中的任何地方，从0跳到1，然后再很多情况下，甚至很小的失误都会导致计算结果完全不同。因此，很难知道你如何才能做出例如对计算过程地随机取样，才能保证正确性。因为，很容易就会错过“很小部分的计算”。但是，通过一些厉害的数学方法，你就可以做到。

整体的感觉是，和这些联合在一起的协议，都在使用纠偏编码的数学方式，这种方式通常用来让数据可以容错。如果你有项目数据，那么你可以将这些数据作为行代码，然后你可以在这行中选出四个点。其中任何两个点都足够来重新构造这条线，因此也给你另外两个点。并且，如果你甚至对数据进行了很小的改变，那么它至少保证了你四个点中的三个。你也可以将数据编码成1,000,000维度的多项式，并且从中选出2,000,000个点；这些点中的任意1,000,001个都会获得初始数据，因此其他点，以及数据的任何偏离都会至少改变1,000,000个点。这里的算法将会这样利用多项式，从而使得误差放大。

原始数据更改1个点，对于多项式都会有很大的改变

简单举例

假设你想要证明，你有个多项目P，从而对于x从1到100万，P(x)是0 <= P(x) <= 9之间的整数。这就是“范围检查”的简单举例；也许你会假设这类检查可以用来进行验证，例如在进行转账后，账户余额仍然是正数。如果1 <= P(x) <= 9成立，那么这可能是检查这些值形成正确的数独解决方案的一部分。

“传统”的方式是证明这会显示所有1,000,000个点，并且通过检查这些数值来验证。但是，我们想要看到是否我们能够做出证据，可以在少于1,000,000个步骤的时候就被验证。简单随机检查P的估值不会这样做；总会有欺诈者出现，来证明P是满足999,999个位置，但是不能满足最后一个，而且随机取样就几个数字，通常总是会错过那个。那么我们可以怎么做呢？

让我们从数学方式来转化这个问题。假设C(x)是多项式检验；如果0 <= x <= 9，那么C(x) = 0，否则，C(x)就是非零数字。有一种很简单的方法，就可以构建C(x)：x * (x-1) * (x-2) * ... * (x-9)（我们会假设，所有我们的多项式和其他数字都会使用常数，所有我们不需要担心之间的数字）。

现在，问题变成了：证明你知道P，然后对于所有的x从1到1,000,000，C(P(x)) = 0。让Z(x) = (x-1) * (x-2) * ... (x-1000000)。很基本的数学事实是，对于x从1到1,000,000，任何等于零的多项式都是Z(x)的乘积。因此，问题再次转变成了：证明你知道P和D，然后对于所有的x，C(P(x)) = Z(x) * D(x)（需要注意到，如果你知道一个合适的C(P(x))，那么用Z（x）除以计算D（x）不是太困难；你可以使用长多项式除法或者基于FFT算法来进行更快地运算）。现在，我们将最初的问题转换成了数学问题，并且看起来可以顺利解决。

那么如何证明这个问题呢？我们可以假设，证明过程是证明者和验证者之间的三步沟通：证明者发出了一些信息，然后验证者发出一些需求，之后证明者发出更多的信息。首先，证明者承认（也就是说，创建一个Merkle树，并且给验证者发去根哈希）对于1到10亿之间x的所有P(x) 和 D(x)的估值。这就包含了0 <= P(x) <= 9之间的100万个点，以及剩下的9.99亿个点。

假设验证者已经知道Z(x)在这些点的估值;那么Z(x)就像一个“公共的验证秘钥”，从而每个人都必须提前知道（没有地方存储Z(x)的客户端，可以简单地将它存储在Z(x)的Merkle树根部，而且需要证明者也为每个Z(x)的数值提供验证者需要的分支；或者，有些数字字段，对于x和Z(x)都很容易计算）。在获得这个认可（也就是说，Merkle树的根部），验证者然后会在1和10亿之间选择随机的16x数值，而且让证明者来提供P(x)和D(x)的Merkle树分支。证明者提供了这些数值，而且验证者会检查(i)这些分支和之前提供的Merkle树根部符合（ii）C(P(x))其实等于Z(x) * D(x)。

我们知道这个证明有很好的完整性，如果你其实知道一个合适的P(x)，那么你可以计算D(x)并且构建正确的证明，来通过16个检查点。但是稳定性又如何呢？也就是说，如果欺诈的证明者提供了个错误的P(x)，他们被抓的最小可能性是多少？我们可以进行如下分析。因为C(P(x))是由1,000,000维度多项式组成的10维度多项式。整体来说，我们知道这两个不同的多项式最多在N个点符合；因此，10,000,000维度的多项式和任何等于Z(x) * D(x)的多项式都不会相等。对于x来说，至少在990,000,000个点都不会同意。因此，对于不好的P(x)，在一轮被抓住的概率已经是99%；通过16轮检查，被抓住的概率是1 - 10-32，也就是说，这个机制不可能存在欺诈。

那么，我们刚刚做了什么？我们使用多项式来推动任何不良解决方案的错误，以至于对于初始问题的任何错误解决方案，都需要100万个检查才能发现，最终导致验证协议的解决方案，可以99%的概率发现错误。

我们可以将这三步的机制转换成一个非交互式的证明，这可以通过单个的证明者来广播，然后被任何人使用菲亚特-夏米尔启发式算法来进行验证，证明者首先构建P(x) 和 D(x)数值的Merkle树，然后计算树的根哈希。这个根部本身被用于作为熵的来源，用来决定证明者需要提高这个树的哪些分支。证明者然后就会广播Merkle树的根部，分支还有证明。计算全部会在提供方完成；从数据计算Merkle树根部的过程，然后是使用这些来选择经过审计的分支，有消息地完成了交互性验证者的需求。

欺诈者在不需要有效的P(x)前提下，唯一能做的事情，就是尝试进行有效验证，直到最终他们特别幸运，选择到了正确的Merkle树分支，但是概率只有1 - 10-32（也就是说，至少有1 - 10-32的概率，虚假的证明不会通过检查），欺诈者需要花费几十亿年，才能得到可以通过的证明。

前景展望

为了说明这项技术的能力，我们来做些看起来不是很重要的事情：证明你知道第100万个斐波纳契数。为了完成这个，我们会证明你对多项式有了解，P(x)代表第x个斐波纳契数。多项式检验就会从3个维度进行：C(x1, x2, x3) = x3-x2-x1（需要注意，如果对所有x来说，C(P(x), P(x+1), P(x+2)) = 0，那么P(x)久代表斐波纳契数）。

所以问题就变成了：证明你知道有个P和D，然后C(P(x), P(x+1), P(x+2)) = Z(x) * D(x)。对于其中的16个因子，证明者需要为P(x), P(x+1), P(x+2) and D(x)提供Merkle树的分支。证明者而且还需要保证所提供的Merkle树的分支可以保证，P(0) = P(1) = 1。否则，整个流程就是一样的。

现在，为了完成这个，还需要解决2个问题。第一个是，如果我们尝试进行列举数字的方法来解决这个问题，效率就会很低，因为这些数字通常都会很大。例如，第100万个斐波纳契数有208988个数字。如果我们其实想要获得简单性，与其使用常规数字进行列举，我们需要使用有限的数字系统，始终符合我们了解的规则，例如a * (b+c) = (a*b) + (a*c) and (a^2 - b^2) = (a-b) * (a+b)，但是每个数字都会占据一定空间的数据。证明关于斐波纳契数数字的问题，需要更加复杂的设计。最简单的模式，就是将每个a + b用a + b的N进制数来代替，对减法和乘法也是同样地方法，对于除法，使用模块逆转（例如，如果N=7，那么3 + 4 = 0, 2 + 6 = 1, 3 * 4 = 5, 4 / 2 = 2而且5 / 2 = 6）。

其次，你也许注意到了，在上面的证明中，我忽略了一种攻击：如果攻击者不是通过看似真实的P(x)，而是使用了并不在这些多项式的数据？那么，无效的C(P(x))必须要和有效的C(P(x))在至少9.9亿个点上相同，就不会应用了，而且会非常不同，而且更有效的攻击是有可能发生的。例如 ，一个攻击者会保证任何x都有一个随机数p，那么计算d = C(p) / Z(x)，并且将这些数字都放入P(x)和D(x)。这些数字不会在任何低维度的多项式，但是它们会通过检测。

这就证明了这种可能性会很有效地抵抗攻击，虽然做这些的工具相对复杂，而且你可以说它们组成了STARKs协议中的数学创新。同时，这个解决方案有个限制：你可以清除这些数据，但是你不能清除和你的多项式存在一个或两个变量差别的多项式。因此，这些工具会提供接近性证明，证明大多数在P和D的点上，都会代表正确的多项式。

所以最终证明，这已经足够来打造证明，尽管会有两个小问题。首先，验证者需要检查更多的指数来弥补错误占据的有限空间。其次，如果我们正在打造边界检测，那么我们需要将接近性证明扩大到不止是证明大多数点是在同个多项式，而且证明这两个特别的点是在那个多项式上。