1. 概述

• 1.1 应用场景
• 1.2 简介

2. 引入问题

• 2.1 NP问题和NPC问题
• 2.2 电路
• 2.3 数值化
• 2.4 问题转换

3. 证明

• 3.1 同态加密
• 3.2 零知识
• 3.3 非交互式
  • 3.3.1 CRS

4. 其它方案
5. 结尾

概述

应用场景

零知识证明在隐私保护、区块链扩容等领域都有非常重要的作用，在之前的文章中提到过零知识证明的有: 真正理解 Layer2 中我们介绍zk-rollup是Layer2一种较好的扩容方式,不需要较长的提款周期 Immutable X白皮书(译) 中介绍Immutable X这一Layer2扩容方案也是使用的零知识证明。 去中心化存储的那些事(上) 中的filecoin需要存储者证明自己确实进行了存储并且未被损坏(复制证明和时空证明)，这个证明过程也是使用零知识证明。 Flow白皮书1-共识和计算分离(译) flow采用了将共识和计算分离的方案，有专门的执行节点和验证节点，验证节点进行验证的时候也是使用知识证明减少计算量。 可见零知识证明在区块链中有着广泛应用，本文重点是介绍零知识证明的实现原理，所以这部分不过多赘述。

简介

在学习零知识证明的时候，常常面临一堆较为复杂的词汇，ZK-SNARK、ZK-STARK、椭圆曲线、同态加密、CRS、QAP、QSP、groth16、Zcash等等，每一块知识都相当复杂并可以延展出其他的知识。此时我们看到的零知识证明就是一个巨无霸，包含了许多子概念。

我们首先需要把握零知识证明的完整主线，然后各种协议方案在这条主线上进行迭代更替就变换为不同的零知识证明的解决方案。

引入问题

零知识证明是为了达成证明者希望能够证明自己知道某一问题的答案但又不希望透露答案的目标。在这里我们首先引入问题。即如下图，零知识证明需要有1个问题才能够围绕这个问题进行证明。

如果零知识证明需要对接无数种问题，那么方案是不具备通用性的，所以我们希望能够有一种问题可以将其他问题都转化为该问题，这样零知识证明就只针对该问题进行研究即可。

接下来我们就来寻找这类问题。

NP问题和NPC问题

1个问题如果可以多项式时间内求解，我们可以称之为P问题。1个问题如果可以在多项式时间内通过解进行验证那么称之为NP问题。由此可见P问题是属于NP问题的，因为1个问题多项式时间内可以找到解，那么一定可以在多项式时间内验证。

这里简单介绍介绍下多项式时间求解是什么意思，学过数据结构和算法都了解时间复杂度O(n),如果1个算法时间复杂度是O(n) or O(n^2)n在底数位置那么称之为可以多项式时间内求解，如果1个算法时间复杂度O(n!) or O(2^n)等n在指数位置那么称之为不能在多项式时间内求解。

我们需要证明的问题一定是NP问题，否则无法在多项式时间内进行验证，而零知识证明非常重要的一个点计算验证要简单。那么有没有一种问题可以将所有的NP问题都转化为该问题呢？ NPC问题就是这样的一类问题，如果其他NP问题都可以约化为该问题，那么该问题称为NPC问题。

问题描述-电路

如何描述1个NPC问题，电路是1个经常被采用的方案。而且逻辑电路本身就是1个NPC问题。其他的描述方式我们将在后面进行介绍。

电路问题即给定输出和电路，然后需要求得输入，如下图所示

我们一般使用算术电路，输入为数字(简单理解)，逻辑运算为乘法门和加法门。 目前为止我们找到了1个通用的问题-逻辑电路，其他特定问题或任意一段程序都可以转化为逻辑电路。 此时理解的零知识证明变成了。

注意:这里的画电路不是真正的用绘图方式表达，而是用电路语言进行编写。

数值化-r1cs

接下来，我们的逻辑电路因为是要给计算机进行计算，所以我们希望将其数值化描述。这个数值化的过程通常会采用约束系统。比如常见的r1cs就是一种约束，其要求的约束是 $A·s B·s - C·s = 0$ 这个约束如何理解呢？我们看个简单的例子: $ 25=kk $ 这个语句可以用来描述这样一个非常简单的电路

将电路中涉及到的变量组成1个向量s[k,25] 要有一组ABC使得$ A·[k,25] B·[k, 25] - C ·[k,25] = 0 $等价于$ 25=k k $ 此时我们给出1组符合 A=[1,0] B=[1,0] C=[0,1] 代入$ A·s B·s - C·s = 0 $后即可求得$ 25=k k $

这里我们使用了最简单的例子，更复杂一点的例子可以参考V神较为知名的文章 https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

这里需要重点理解的就是电路是由很多个逻辑门操作组成的，而每个逻辑门操作总是可以转换成为2个输入1个输出。使用 $ A·s * B·s - C·s = 0 $可以较好得通过数值描述每个逻辑门是针对输入做了什么样的变化从而转变成输出的。

当然电路除了r1cs外，还有一些其他的约束如:bacs、tbcs等，这里不再介绍。 我们编写的电路，经过r1cs的编译器，会编译成为符合r1cs规范的约束数值。这组数值就可以描述该电路，这样可以更方便地进行计算。 此时所理解的零知识证明变为:

在使用r1cs的时候问题转换为就是找到1个向量s满足A·s * B·s - C·s = 0，即使获得s，在实际问题中的验证过程我们可能需要验证数万个这样的逻辑运算，非常冗余，有没有办法进行一次运算即可验证呢？在这里我们引入多项式的方案。

问题转化

我们这里通过QAP问题介绍多项式的方案，QAP问题简单来说(这里经过简化)是需要找到p(x)能够整除一个已知的t(x),即可以表示为公式: p(x) = H(x) * t(x) 如何将r1cs转换为QAP呢，还是用我们上面的例子: 将r1cs中求得的向量A=[1,0] B=[1,0] C=[0,1]进行拉格朗日插值,插值方式为依次按照[1,A向量第一组第一个值] [2, A向量第二组第1个值]进行插值计算，求得的方程将系数提取作为A~ 向量组的第一个向量。依次类推A~ 向量的第二组方程是由A向量组的第2个值进行插值获得。关于拉格朗日插值大家可以自行搜索。求得: A~ [0,1] [0,0] B~ [0,1] [0,0] C~ [0,0] [0,1]

此时将s[k, 25]向量和A B C相乘可得: A~·s = [0,k] B~·s = [0,k] C~·s = [0,25] $ p(x) = A~·s B~·s - C~·s = 0 x + k^2 -25 = k^2 -25 $ $ t(x) = x-1 $ 因为无论p(x)的方程系数如何，总是满足x=1时 p(x) = 0 这个原因是因为我们在进行拉格朗日插值时使用了x=1作为插值点

证明者由于知道答案，自然也就知道p(x) = 0 验证者需要验证 符合条件的p(x) 满足$ p(x)/t(x) = p(x) /(x-1) $能够整除。

在这里我们举了1个非常简单的例子，为了能够让大家在阅读时不再陷入复杂计算中去，较为复杂的例子还是可以阅读上面推荐的V神的那篇文章

此时的零知识证明又增加了一步

很多算法都有类似QAP转换过程，目的如我们前文所说是为了简化验证。

证明

到了这里我们终于开始进行证明，常用的零知识证明会要求将问题转换为寻找1个满足特定条件多项式的问题(如上述的QAP)。直接将多项式系数给出是最简单的证明，但无法保证零知识。所以我们来讨论如何证明知道1个多项式，以上文中的QAP为例，需要寻找到P(x)能够整除t(x),进行公式化表达即: $ P(x) = H(x) * t(x) $

如上图所示 验证者发起挑战，向证明者发送随机数r，如果证明者可以给出 P(r)和H(r)，验证者进行验证t(r) = P(r)/H(r)，这样进行多次随机挑战降低证明者欺骗的概率从而使得验证者相信证明者的确知道p(x)。

但这里存在1个问题，因为t(x)和r都是公开的，所以此时验证者可以随意构造p(r)和H(r)使得t(r) = p(r) / H(r)。我们需要有一种方式对r进行加密，但因为r要参与计算，所以加密后的r计算结果要能够通过r加密计算求得，这样才可以进行验证，这里就用到了同态加密。

同态加密

同态加密即加密后的运算结果可以和先运算再加密进行转换，比如: $ g^a * g^b = g^(a+b) $ 我们暂且使用S(x) = g^x 作为同态加密函数，来看看上面说的r泄露问题如何解决 举个例子: $ P(x) = 2x^2 -x $ $ t(x) = x $ $ H(x) = 2x-1 $

验证者依旧随机挑选1个数r，但这次不公开r，而是公开g^r。我们使用的是加法同态: $ S(x)S(y) = g^(x+y) $ 也就是说g^(x^2)无法通过g^x运算得到,所以验证者需要将g^(r^2)和g^r都给到证明者。

证明者获取到g^(r^2)和g^r后利用同态性质计算: $ g^(p(r)) = g^(2r^2-r) = (g^(r^2))^2 /g^r $ $ g^(H(r)) = g^(2r-1) = (g^r)^2 /g $ 证明者计算出g^(p(r))、g^(H(r))后发送给验证者

验证者拿到g^(p(r))和g^(H(r))后进行验证 $ g^p(r)= g^(H(r)* t(r)) = (g^H(r))^t(r) $

至此，我们通过同态加密解决了，随机数r泄露的问题。

上面的同态加密解决了证明者利用r泄露欺骗验证者的问题，那么验证者是否会通过多轮随机数挑战将多项式系数获取到呢，如果存在这种可能的话就无法保证零知识了，我们先来看看会不会发生这种情况。

零知识

我们假设验证者进行3次挑战给出的随机数是r1，r2, r3那么验证者将会知道 (r1,P(r1)) (r2,P(r2)) (r3,P(r3)),对于2次方程通过3个点可以求得原方程，所以说验证者是可以通过多轮随机挑战来窃取答案的。 那么如何避免这种情况呢？我们这里让证明者生成随机数l，在每次结果中增加随机偏移值。整个过程变为证明者生成随机数L，验证者生成随机数r，证明者计算出结果P(r) H(r)使用l进行变换。注意，这里l依旧需要进行同态加密发送给验证者或者进行计算的时候消除掉这个l。

按照上面例子 我们进行变换，证明者返回$ (g^p(r))^l和(g^H(r))^l $ 那么验证者验证$ (g^p(r))^l= (g^(H(r)* t(r))^l = ((g^H(r))^l)^t(r) $即可

现在我们保障了证明者不会欺骗验证者，验证者也不会从证明者获取到原问题有关的知识。但刚刚有没有发现，我们的示例都是基于验证者使用随机数去挑战证明者，这样他们2者之间是有交互的。如果网络中存在大量的验证者，那么证明者需要和每个验证者进行通信，通信成本很大。有没有办法，使得证明者直接给出证明，所有的验证者拿着这个证明就可以对结果进行验证了呢？

非交互式

使用非交互式，这里意味着没有验证者会持有随机数r，因为证明者的这份证明是针对所有验证者的，除非所有验证者都持有r，那这样证明者也大概率会知道r。所以我们不能直接公开r，需要使用避免泄露的方式同态加密R=g^r来进行公开，但需要注意的是上面介绍同态加密的时候我们进行验证的方式是: $ g^p(r)= (g^H(r))^t(r) $ 但此时验证者并不知道t(r),我们只知道加密后的结果g^t(r)。我们需要一个函数能够满足乘法同态，即: $ S(a)S(b) = S(a b) $ 这样我们验证就可以通过: $ S(p(r)) = S(H(r) t(r)) = S(H(r)) * S(t(r)) $ 来进行验证。

椭圆曲线pairing具备这样乘法同态的性质，具体可以自行查阅资料。

此时我们了解的零知识证明就变成了这样:

CRS

在上文中，我们介绍非交互式实现的方式是通过将随机数r加密生成R，这一过程需要有可信的第三方完成，并且生成完成需要立马删除原始r。这一过程使用的就是CRS，CRS是指通过一种受信任的方式生成一组可以被公开访问的字符串(一系列值)。这也就是SNARK中经常提到的初始化可信设置，由上面的推导，我们可以思考得出如果原始值r泄露，那么证明者可以随意欺骗验证者。

其它方案

上述我们大部分都是使用zk-SNARK的过程，但这只是1个流程，其中每个阶段都会有其他方案，比如我们会提出以下一些问题

1. 上文我们介绍证明时是通过验证者向证明者发起挑战的方式，为了避免随机挑战数被泄露使用了同态加密，那么有没有其他方式证明呢？
2. NP问题描述方式只有电路这一种？
3. 为什么STARK是抗量子攻击的特性呢？

我们简要回答下这几个问题

1. Q: 上文我们介绍证明时是通过验证者向证明者发起挑战的方式，为了避免随机挑战数被泄露使用了同态加密，那么有没有其他方式证明呢？ A: 除了隐藏询问参数，另外一种方式是多项式承诺，plonk就使用了该方案，很多STARK应进行采用。多项式承诺可以做到不需要设置可信参数，这也是STARK的优势之一。
2. Q:NP问题的描述方式只有电路吗？ A: 描述NP问题的方式一般有这几种 1.电路 2.RAM 3.高级编程语言 RAM描述方式和汇编语言可以认为是类似的表达形式。这几种方式在表达上是越来越好，但底层处理上是越来复杂了。RAM也需要进行数值化，RAM经过数值化后称之为AIR。 一般而言STARK不再使用电路来描述问题(自然也就不会使用r1cs约束)，而是使用RAM(数值化会变为AIR)。
3. Q:为什么STARK是抗量子攻击的特性呢？ A: 因为SNARK大多数采用非对称加密而STARK大部分采用对称加密，对称加密是具备抗量子性的，非对称加密是不具备抗量子性的。

结尾

本文对零知识证明的过程进行分析，希望读者可以对零知识证明的整体流程有所了解，后续讨论零知识证明原理的时候我们都是在放大讨论这篇文章中的某一部分，再去接触一些令人眼花缭乱的技术时，我们能够很清晰的知道，这项技术是解决了零知识证明的哪部分问题，针对哪部分进行了优化，就像文末介绍的较新的STARK中的AIR其实是用来替换r1cs作为另外一种描述NP问题的方式。

参考 https://eprint.iacr.org/2012/215.pdf (介绍QAP问题的论文） https://github.com/scipr-lab/libsnark (实现SNARK的库) https://github.com/iden3/snarkjs (使用js实现SNARK，支持groth16和plonk) https://nakamoto.com/cambrian-explosion-of-crypto-proofs/ (各种证明之间不同维度的对比) https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649 (V神针对ZK-SNARK的介绍)