浅谈零知识证明

零知识证明是实现隐私保护的密码学方案。曾被称为密码学领域的一颗皇冠，用于在不泄露具体秘密情况下对问题一种正确证明方法。尤其是在金融领域实现数据隐私保护方面的创新业务场景里实现落地应用。

我们整理了相关领域的知识后，站在伟人的肩上，今天就从零知识证明的基本概念、研究进展、实现原理方面做一些简单阐述。

一、零知识证明概述
零知识证明（Zero-Knowledge Proof, ZKP）是现代密码学中的一类经典协议，用于在不泄露关于某个命题任何信息的情况下证明该命题的正确性。近年来，随着区块链等新兴技术的发展以及隐私计算需求的兴起，零知识证明技术再次成为包括金融科技、大数据等相关行业关注的焦点。

零知识证明的概念最早在20世纪80年代由美国麻省理工学院的Shafi Goldwasser、Silvio Micali和Charles Rackoff在论文《The Knowledge Complexity of Interactive Proof Systems（交互式证明系统中的知识复杂性）》这篇论文仅能证明某一类特定的问题，且需要证明者和验证者进行多轮交互才能完成，其功能和实际应用效果难以满足现实应用场景的要求。为了能够实现针对任意问题的通用证明协议，同时避免多次交互给实际应用带来的局限性，非交互式通用证明协议的研究成为了零知识证明自概念诞生以来的重要发展方向。

目前，数据安全与隐私保护成为了区块链等应用中的重要需求，零知识证明这一经典的密码学算法有了新的应用前景。在区块链应用场景中，实现多参与方的频繁交互是不现实的，且复杂多样的业务模式催生了通用证明协议的应用需求。因此，非交互式通用零知识证明协议得到了广泛的应用。

二、零知识证明技术原理
现在对零知识证明的技术原理进行进一步分析，包括零知识证明在密码学上需要满足的基本属性，以及以经典的Schnorr协议为例说明交互式零知识证明协议到非交互零知识证明协议的转化。

1、基本属性
零知识证明涉及的密码学与数学理论较多，包括计算/统计不可区分性（Computationally/Statistically Indistinguishiable）、模拟器（Simulator）、随机预言机（Random Oracle）模型（简单期间，预言机我们用SHA-256算法代替）等计算复杂性理论内容。为了便于理解，我们将零知识证明协议的三个基本属性用较为通俗的语言描述如下：

• 完备性（Completeness）：只要证明者P拥有相应正确知识，就能够通过验证者V的验证，即P有足够大的概率使V确信。
• 可靠性（Soundness）：如果证明者P没有相应正确知识，则无法通过验证者V的验证，即P成功欺骗V的概率可忽略。
• 零知识性（Zero-Knowledge）：证明者P在交互的过程中仅向验证者V揭露其是否拥有相应正确知识，而不会泄露任何关于知识的额外信息。

2、交互式零知识证明
零知识证明起源于交互式证明协议，本小节以Schnorr协议为例分析交互式零知识证明的原理和特点。Schnorr协议是一种身份认证协议，也是如今许多PKI数字签名方案。

PKI是Public Key Infrastructure的首字母缩写，翻译过来就是公钥基础设施；PKI是一种遵循标准的利用公钥加密技术为电子商务的开展提供一套安全基础平台的技术和规范。

在Schnorr协议中，证明者A通过和验证者B进行三次交互的方式证明了其拥有公钥pk对应的私钥sk，而验证者B无法在整个过程中获取私钥sk的信息。
3、非交互式零知识证明
交互式零知识证明协议依赖于验证者的随机尝试，需要证明者和验证者进行多次交互才能完成。非交互式零知识证明（Non-Interactive Zero-Knowledge, NIZK）将交互次数减少到一次，可实现离线证明和公开验证。例如，在区块链等零知识证明应用场景中，通常需要将证明进行直接发布，而非依赖于交互实现，且需要支持多方的公开离线验证。因此，在实际应用中需要考虑如何实现交互式零知识证明协议的非交互化。

对于Schnorr这一具体协议而言，可通过基于随机预言机模型的Fiat-Shamir变换将其转化为非交互式零知识证明，即Schnorr签名。Fiat-Shamir变换将交互式协议中验证者的每次随机数挑战行为用证明者执行随机预言机代替，随机预言机的输入应包含之前的所有上下文信息。随机预言机可以看作是一个理想化的哈希函数，能够将输入转化为具有真随机性（满足一致性分布）的结果。在实际应用中，由于不存在理想化的随机预言机，可以使用SHA-256等常用的密码学哈希算法进行实现。

即在基于Fiat-Shamir变换的非交互式Schnorr协议证明过程中，随机挑战数c不再由B生成并发送给A，而是由A自己通过c=H(x||M)计算挑战数c，其中H(∙)是哈希函数（随机预言机），M是任意消息串。最后A将(c, y)作为证明值进行发布，同时发布消息M。任何获知证明值(c, y)、消息M和公钥pk的验证者均可在与交互式协议相同的验证方式基础上进一步验证c=H(x||M)是否成立。

证明者A在没有交互的情况下得到了随机挑战数c，因此省去了交互式协议中验证者B随机选择c并发送给证明者A的交互过程。这一非交互式的Schnorr协议也被称为Schnorr签名机制，即证明者A使用自己的私钥sk=a对消息M进行了签名，其他人可通过A的公钥pk验证这一签名。

三、零知识证明典型算法分析
为了能够使零知识证明在更多业务场景中应用，可实现通用功能的非交互式零知识证明算法具有更强的应用普适性。因此，我们选取zk-SNARK等在区块链等场景中应用较多的通用非交互式零知识证明算法进行分析。

1、zk-SNARK
zk-SNARK（Zero-Knowledge Succinct Non-interactive Arguments of Knowledge，零知识简明非交互式知识论证）是一类应用广泛的通用零知识证明方案，通过将任意的计算过程转化为若干门电路的形式，并利用多项式的一系列数学性质将门电路转化为多项式，进而生成非交互式的证明，可实现各类复杂的业务场景的应用。目前，zk-SNARK已在数字货币、区块链金融等区块链领域实际落地，是目前最为成熟的通用零知识证明方案之一。

1.1、基本框架
1.1.1、将计算转化为电路
首先，为了将待证明的计算式进行统一处理，需要将其转化为若干个门电路的组合形式。例如，证明者A希望向验证者B证明其知道使得计算式(A1×A2)×(A1+A3)=18成立的A1、A2、A3值，而不泄露A1、A2、A3的具体值。根据zk-SNARK协议，首先需要将计算式(A1×A2)×(A1+A3)=18转化成如下图：

在进行程序表达时，还需要引入一些中间变量。如下

A1 X A2 = SYM_1
(A1+A3)*1 = SYM_2
SYM_1+SYM_2 = OUT

其中，SYM_1和SYM_2是中间变量，OUT 为输出值，即18。
1.1.2、将电路转化为R1CS
第二步是将表示计算式的电路转化为向量点积（内积）的形式，即一阶约束系统（Rank-1 Constraint System, R1CS）。对于每个门电路，需要定义一组向量(l, r, o)，通过向量内积运算使得s∙l×s∙r-s∙o=0，其中s代表全部输入组成的向量，即s=[one, A1, A2, A3, SYM_1, SYM_2, OUT]（元素排列没有固定顺序），one表示值为1的虚拟变量，用于将加法门电路A1+A3=SYM_2统一表达为(A1+A3)×1-SYM_2=0的形式。向量s在zk-SNARK中又被成为证据（Witness），作为证明者生成证明的输入参数。

对于乘法门电路A1×A2=SYM_1，对应的三个向量(l, r, o)分别为：

l=[0,1,0,0,0,0,0]
r=[0,0,1,0,0,0,0]
o=[0,0,0,0,1,0,0]

将s、l、r、o代入s∙l×s∙r-s∙o=0即得A1×A2-SYM_1=0，与门电路A1×A2=SYM_1等价。同理可得加法门电路A1+A3=SYM_2对应的向量为：

l=[1,0,0,0,0,0,0]
r=[0,1,0,1,0,0,0]
o=[0,0,0,0,0,1,0]

即1×(A1+A3)-SYM_1=0。最后一个乘法门SYM_1×SYM_2=OUT对应的向量为：

l=[0,0,0,0,1,0,0]
r=[0,0,0,0,0,1,0]
o=[0,0,0,0,0,0,1]

即SYM_1×SYM_2-OUT =0。通过以上过程，就将待证明计算式对应的电路编码成了R1CS向量的形式。

1.1.3、QAP
第三步是将R1CS向量表达式转化为多项式的形式，即QAP（Quadratic Arithmetic Programs）。通过这一重要步骤，即可实现待证明计算式验证和多项式验证之间的等价转换。

具体而言，首先在有限域上选择三个不同的值，假设为1、2、3（在实际应用中需要随机选择），然后通过拉格朗日插值公式，构造三组多项式l(x)、r(x)、o(x)，使得在x的取值分别为之前选择的1、2、3时，多项式向量组(l(x), r(x), o(x))的三种取值分别对应第二步中三个门电路的向量组(l, r, o)的三种不同取值。取多项式P(x)=s∙l(x)×s∙r(x)-s∙o(x)，当x取值为1、2、3时，P(x)=0，即1、2、3为多项式P(x)的三个根，因此多项式P(x)能够被T(x)=(x-1)(x-2)(x-3)整除，即存在多项式H(x)使得P(x)=T(x)×H(x)。

上述QAP过程将证明原计算式转化成了证明存在多项式H(x)使得P(x)=T(x)×H(x)。通过拉格朗日插值公式引入了大量与原计算式无关的值将向量取值转化为多项式约束，因此多项式与原计算式在本质上并不完全等价，但根据多项式的Schwatz-Zippel定理，验证了转化后的多项式即相当于验证了原计算式。

1.1.4、引入约束
以上步骤完成了计算式证明到多项式证明的转化。为了构造完整的零知识证明方案，需要再引入一系列约束方法构造完备的零知识证明协议。具体包括：

引入椭圆曲线密码体系下的系数知识假设（Knowledge-of-Coefficient Assumption, KCA）约束证明者在生成证明过程中的参数使用，防止证明者通过选择不符合限制条件的多项式进行欺骗。
防止暴力破解：为了保证证明的零知识性，防止验证者在有限范围的多项式系数组合中对证明结果进行穷举破解，进而反推出证明者的原始多项式，需要生成一个秘密的随机数来对证明结果进一步的加密。
使用双线性配对实现验证过程中需要使用到的乘法同态。
为了实现非交互式零知识证明，需要事先由第三方生成一些秘密随机数，并进一步生成证明密钥（Proving Key）pk和验证密钥（Verification Key）vk，pk和vk将作为公共参考串CRS分别赋予证明者和验证者，而原始的随机数则作为“有害废料”（Toxic Waste）进行销毁。

2、功能实现

除上述的(A1×A2)×(A1+A3)=18这类简单的计算式证明外，还可通过不同的电路构造方法，将更为复杂的证明需求转化为门电路的组合形式。libsnark算法库中的gadget工具库包含布尔值、位组合、析取关系（或）、合取关系（与）、大小关系、向量内积、线性组合等基本约束的实现，通过包括但不限于以上基本功能的组合，可实现更为复杂计算式的证明。除基本功能外，zk-SNARK还可实现Merkle树、SHA256哈希、模指数运算、双线性配对等复杂计算的验证。在实际场景中，只要存在对隐私数据计算的可验证性需求，理论上都可考虑尝试采用零知识证明技术解决的可行性，但在应用的必要性方面还需考虑实际可操作性和引入的效率问题。

3、开发工具
目前，为了解决零知识证明技术的广泛应用需求，产生了多个用于实现zk-SNARK零知识证明协议工程化的开源算法库，包括libsnark、bellman、ZoKrates等等。
3.1、libsnark
ibsnark是一个基于C++语言的zk-SNARK工程开发算法库，由SCIPR Lab开发和维护，开发者中包含参与多篇zk-SNARK学术论文的共同作者。libsnark实现了近年来多个主流的zk-SNARK论文方案，其中最为常用的包括BCTV14a和Groth16方案。

下图是 libsnark 的模块总览图，摘自 libsnark 代码贡献量第一作者 Madars Virza 在 MIT 的博士论文。

libsnark实现了zk-SNARK算法的黑盒化，提供高度抽象的编程接口，使开发者无需掌握算法细节即可直接进行工程开发。此外，libsnark还提供了实际应用中的常见基础功能库，可辅助开发者进行复杂证明的组合实现。以在匿名数字货币Zcash中的应用为开端，libsnark奠定了零知识证明技术从理论研究到大规模工程应用的基础。
github上有实现的源码。
地址：https://github.com/scipr-lab/libsnark

查看 libsnark/libsnark/zk_proof_systems 路径，就能发现 libsnark 对各种证明系统的具体实现，并且均按不同类别进行了分类，还附上了实现依照的具体论文。

其中：

• zk_proof_systems/ppzksnark/r1cs_ppzksnark 对应的是 BCTV14a
• zk_proof_systems/ppzksnark/r1cs_gg_ppzksnark 对应的是 Groth16

如果想研究这两个协议的实现细节可直接从这两个目录入手。ppzksnark 是指 preprocessing zkSNARK。这里的 pp/preprocessing 其实就是指我们常说的 trusted setup，即在证明生成和验证之前，需要通过一个生成算法来创建相关的公共参数（proving key 和 verification key）。我们也把这个提前生成的参数称为 「公共参考串」（Common Reference String），或简称为 CRS。

3.2、bellman
bellman是Zcash团队基于Rust语言实现的zk-SNARK算法库，支持Groth16论文方案，目前主要在主流项目中得到应用。
github上有实现的源码
地址：https://github.com/zkcrypto/bellman

3.3、ZoKrates
ZoKrates是一个部分基于libsnark、部分采用Rust语言重写的zk-SNARK实现工具，默认支持Groth16方案，开发者需要使用一种自建的脚本语言进行代码编写，目前在实际工程中仅用于在以太坊智能合约上部署支持零知识证明的应用。
github上有实现的源码。
地址：https://github.com/Zokrates/ZoKrates

3.4、其他算法
3.4.1、zk-STARK
zk-STARK（Zero-Knowledge Scalable Transparent Arguments of Knowledge，零知识可扩展透明知识论证）[13]是2018年提出的一种通用非交互式零知识证明算法，通过多项式插值等方法将证明计算式转化为证明多项式小于某个度的问题，实现对问题的零知识证明。

zk-SNARK算法主要可分为算术化（Arithmetization）和低度测试（Low Degree Testing, LDT）两部分。算术化过程将待证明问题转化为多项式的形式，具体内容包括生成与R1CS类似的执行轨迹（Execute Trace）并构造多项式约束，然后对执行轨迹进行多项式插值，并与多项式约束进行组合变换，得到确定性的验证多项式；而LDT过程则通过二分法验证证明组合多项式和轨迹多项式小于某个固定的度，确保证明者给出的满足多项式的值是基于有效的多项式计算的，用于防止证明者伪造证明，具体基于FRI（Fast Reed-Solomen Interactive Oracle Proofs of Proximity）协议实现。

zk-STARK与zk-SNARK相比主要有以下异同点：

相同点

zk-STARK和zk-SNARK均实现了对隐私输入的隐藏；
zk-STARK和zk-SNARK均为基于知识的论证，即在不知道隐私输入的情况下无法生成有效证明；
zk-STARK和zk-SNARK均可实现非交互式协议；
zk-STARK和zk-SNARK均通过将计算式转化为多项式实现零知识证明。

不同点

zk-STARK具有透明性，即不需要通过由可信第三方完成的可信设置过程生成CRS；
zk-STARK具有可扩展性，即证明过程的耗时与输入大小呈线性关系，但验证过程的耗时仅与输入大小呈对数关系；
zk-STARK生成的证明大小比zk-SNARK大很多。

总的来说，与zk-SNARK相比，zk-STARK不需要通过可信第三方生成CRS，且验证耗时仅与输入大小呈对数关系，但其生成的证明更大。面对区块链等应用场景宝贵的存储资源，zk-SNARK在证明的简洁性方面更胜一筹。

四、总结

得益于近年来隐私计算等新兴技术应用的发展，零知识证明这一具有30多年历史的经典密码学技术在最近5到10年又产生了极为丰富的理论与应用成果。在实际金融领域的应用中，对于不同参与方的数据交互验证可采用零知识证明技术实现，避免敏感信息的相互泄露；在安全多方计算应用中，参与双方可在通过同态加密等方法保护的隐私计算完成后要求互相提供计算过程的零知识证明结果进行验证，防止虚假计算，同时又不会泄露计算过程中的敏感信息。

总的来说，零知识证明这一“新瓶装旧酒”的密码技术，在目前安全多方计算、金融领域、共性连金融领域等场景中都有着一定的应用潜力。

名词解释

1.Schnorr
Schnorr：Schnorr机制由德国数学家和密码学家Claus-Peter Schnorr在1990年提出，是一种基于离散对数难题的知识证明机制。
2.PKI
PKI：PKI是Public Key Infrastructure的首字母缩写，翻译过来就是公钥基础设施；PKI是一种遵循标准的利用公钥加密技术为电子商务的开展提供一套安全基础平台的技术和规范。
3.The Knowledge Complexity of Interactive Proof Systems
交互式证明系统。
4.NIZK
NIZK:Non-Interactive Zero-Knowledge 非交互式零知识证明。
5.zk-SNARK
zk-SNARK（Zero-Knowledge Succinct Non-interactive Arguments of Knowledge，零知识简明非交互式知识论证）
6.R1CS
R1CS：Rank-1 Constraint System, R1CS 即一阶约束系统。
7.QAP
QAP：Quadratic Arithmetic Programs 多项式。

2021年11月6日整理于深圳。