自2008年中本聪发明比特币以来，比特币作为加密数字货币，迅速得到热捧。特别是在“丝绸之路”等黑市交易网站，比特币更是成为了“法定货币”。FBI花了近2年的时间潜伏在“丝绸之路”网站，最终成功抓捕了网站头目，并捣毁了网站。

“丝绸之路”事件后，比特币的匿名性和安全性问题，引起了广泛关注。学术界开始探寻进一步加强加密数据货币隐匿性的新方法。约翰•霍普金斯大学、麻省理工学院、以色列理工学院以及特拉维夫大学的科学家们研究提出了Zerocoin、Zerocash等加密货币。2016年，Zcash正式发布，代表着新一代强加密货币的诞生。

不论是Zerocash，还是Zcash，其强加密特性的关键来自于其内部实现的“非交互性零知识证明机制”（简称零知识证明）。这里我们来简单探讨一下这个机制的基本原理。

一、什么是零知识证明机制

零知识证明机制早在20世纪80年代就被提出，真正进入大众视野则是在2016年Zcash诞生后。简单地讲，零知识证明机制就是：在没有交互或者交互极少的条件下，证明者和验证者开展证明和验证活动，其中，证明者向验证者出示证据，但不需要告诉验证者具体的执行内容；验证者能够直接验证计算的正确性，而不必执行计算过程，甚至不用知道证明者到底执行了什么。

Bob捡到了Alice丢失的钱包，Bob在不让Alice看到钱包的前提下，要求Alice“证明”钱包归Alice所有。这个“证明”过程就类似于“零知识证明机制”。Bob可能会向Alice提出一系列问题，比如钱包里有多少钱、有什么卡、有没有身份证件或其他物件等等。Bob根据Alice给出的回答（证据），来验证这个钱包是不是Alice的。

再比如，Zcash要对隐秘交易过程进行证明。假如有一笔交易A将5ZEC转给B，一方面要证明A原来拥有5ZEC，另一方面要证明交易完成后，A支出5ZEC，B获得5ZEC，总量保持平衡。这一证明过程可抽象为表达式F(σ1,σ2,s,r,v,ps,pr,v)=1。其中，σ1和σ2是“前”“后”状态的Merkle树的根散列值；s和r是发送者和接收者账户；ps是个证据，用于证明“前状态”时v在σ1上；pr是个证据，用于证明前后状态变化后，v从σ1移到σ2，s和r两个账户保持平衡。如果所有输入已知，验证表达式F的计算相对容易。但zkSNARK的证明过程则是：从证明者看来，只有σ1和σ2已知，通过证据（Pour）证明表达式F(σ1,σ2,s,r,v,ps,pr,v)=1是正确的。

零知识证明机制的英文全称为zero-knowledge Succinct Non-interactiveARguments of Knowledge，缩写为zkSNARKs。zkSNARKs的首字母准确地描述了其关键含义：

• zero-knowledge：零知识证明，证明者向验证者给出证据，但不向验证者透露陈述细节。

• Succinct：简洁，与实际的陈述长度相比，证据的大小很小。

• Non-interactive：没有交互，整个证明过程没有或只有很少的交互。任何证明者均只通过证据便可直接证明。

• ARguments：证据，证明过程基于计算能力保障，也就是说是基于“计算健全性”，而不是“完美的健全性”。假如证明者拥有足够大的计算能力，则可以伪造证据。

• of Knowledge：知识，证明者不可能在不知道陈述具体细节的情况下构造证据。

二、零知识证明机制的核心概念

零知识证明机制早的基本思想是，综合运用NP-complete归约、QAP构建等方法，将待证明问题编码成为一个多项式问题；运用QSP证明、α-pairing验证等方法，进行多项式的简洁、高效验证；运用同态加密、T-shift保护等方法，加强验证过程的隐匿性保护。

NP-complete归约

NP-complete归约是将各类待证明问题转化为布尔判定式的基本方法，是开展zkSNARK证明验证的基础。运算问题大体可归为P、NP两类：P问题的计算复杂度为输入参数个数的多项式级别，一般是多项式运算问题；NP问题的计算复杂度为输入参数个数的指数级别，一般是搜索问题。任意NP问题都可以通过一个NP完全问题（NP-complete）进行表示。NP完全问题L都可以通过降维函数（reductionfunction）f和布尔判定式SAT，表示为：L(x) = SAT(f(x))。

其中，f的定义为：

• F(a1,…,ak)为真当且仅当r(f)(a1,…,ak)为0；

• r(xi):=(1-xi)

• r(¬f):=(1-r(f))

• r((f∧g)):=(1-(1-r(f))(1-r(g)))

• r((f∨g)):=r(f)r(g)

SAT的定义为：

• 任意变量x1,x2,x3,...都是布尔方程式；

• 如果f是布尔方程式，那么¬f也是布尔方程式；

• 如果f和g是布尔方程式，那么(f∧g)和(f∨g)都是布尔方程式。

QAP构建

zkSNARK通过环路算术化方法构建规则二次算术程序（QAP，QuadraticArithmetic Programs）把各类运算问题表示为NP完全问题，为后续验证计算做好准备。一个数字环路由多个数字计算门组成，其功能类似于加法和乘法，通过使用线路链接门。在底部的线路是输入线路，在顶部的线路是输出线路，它将输出线路通过计算输入得到的计算结果。

QAP方法的主要思想是：对于一个固定取值的 (s1,…,s6)，我们使用它作为系数来定义一个多项式的左、右和输出的“相加”。也就是说，我们定义

，

，

；

再定义多项式

，

完成环路算术化构建。

QSP证明

zkSNARK基于二次张成程序（QSP，Quadratic Span Programs）原理构建简明的非交互知识论证系统。QSP的基本思想是：QSP由两个多项式集合V = {v0，v1,…，vn}和W = {w0，w1,…，wn},以及一个目标多项式t组成。当且仅当对任意满足F(x)=1的x=x1,…，xn∈{0，1}n,有

，而且满足当xi=0时,ai=bi=0。

利用QSP验证即证明：

成立，

也就是证明：

。

验证方法是：选择任意随机值s,证明t(s)h(s)=va(s)wb(s)。从计算耗费来看，验证者在输入准备阶段的时间复杂度是线性的，验证时间是常数。

α-pairing验证

zkSNARK通过α-pairing函数、知识系数测试方法（d-KCA）实现盲评价验证。

α-pairing函数定义如下：

验证者利用α-pairing函数来检查

是否成立。其安全性基于q-power Diffie-Hellman假设。利用α-pairing进行验证的方法称为知识系数测试方法（d-KCA），其主要验证步骤如下：

• 预处理阶段：随机选取s，计算并公布

• 为了验证证明方知道多项式P，验证方选择随机的α和s，并且发送给证明方隐藏的

。其中g为一种加密运算，如椭圆曲线加密等。运算完成后，将s进行严格保密或者舍弃。

（对应证明方使用验证方发送的数据计算a=P(s)·g和b=αP(s)·g，并且都发送给验证方。验证方检查b=α·a，如果这个等式成立就会将其接受，验证证明方不知道多项式P的概率几乎可以忽略。

）和同样隐藏的

（对应

）。

同态加密验证

同态加密的概念源于1978年Rivest等人提出的“秘密同态”概念，主要解决在不解密密文的情况下，对加密数据进行复杂操作，获得与相应明文操作相同的结果。同态加密包括加法同态、乘法同态、全同态等。

例如加法同态，定义加密函数E:M->C，其中，M和C分别为明文空间和密文空间。如果E(m1+m2)= E(m1)⊕E(m2) 或者m1+m2=D(E(m1)⊕E(m2))，其中D是解密函数，这意味着对于一个加法同态系统，存在一个有效算法可以计算出两个消息的和，但是不泄露消息本身。

再例如乘法同态，RSA加密算法就是一个标准的乘法同态加密。具体来讲，基于RSA加密具备的特性：

。也就是说，在a=E(x)，b=E(y)，c=E(xy)条件下，(ab)%n ≡ c%n。

T-shift零知识保护

zkSNARK中，证明者通过T-shift方法进一步加强隐私信息保护，基本思想是：

（1）将证明问题转换为L·R−O=t·h。

（2）随机地选择δ1,δ2,δ3∈Fp，定义Lz:=L+δ1·t，Rz:=R+δ2·t，Oz:=O+δ3·t。

（3）Lz·Rz−Oz=(L+δ1·t)(R+δ2·t)−O−δ3·t

=(L·R−O)+L·δ2·t+δ1·t·R+δ1δ2·t 2−δ3·t

= t·(h+L·δ2+δ1·R+δ1δ2·t)

定义hz=h+L·δ2+δ1·R+δ1δ2·t，则将问题转换为证明Lz·Rz−Oz=t·hz。由于δ1,δ2,δ3的随机性，确保了T-shift方法对信息的进一步隐秘保护。

三、对于零知识机制的展望

零知识证明机制的第一个成熟的工程实现是libsnark，由Eli Ben-Sasson、Alessandro Chiesa等人于2012年完成。Zcash正是直接引用libsnark来实现零知识证明的功能。在实际运用中，zksnark的运算效率、通信耗费、初始参数生成安全性等问题也引起了大家的关注。2017年9月，另一种相对高效的零知识证明方法zkstark被提出，号称将大幅提升运算效率、降低成本。但zkstark还处于研发阶段，具体技术细节并未被披露。

关于应用前景，零知识证明机制目前的主要应用是在加密货币领域，但从其技术本质来看，凡是基于数据隐秘保护的证明问题或者计算问题，都可以通过零知识证明机制来寻求解决方案。在信息技术数据密集化、计算密集化、隐私保密化发展背景下，基于“通用零知识证明系统”，开展区块链、大数据、人工智能等深度融合运用是未来的一大发展趋势。

2016年底，图灵奇点就敏锐发觉这一技术趋势，并在理论研究、工程实现、行业应用等方面持续投入，积极布局。目前，已在金融和电动汽车行业的相关应用中取得积极进展。后续，图灵奇点将按照“区块链+私密保护”的思路，进一步加大研究和开发的投入，让人类最伟大的思想服务与我们的日常生活，Better solution，better life。

本文作者：雷木