本文主要介绍零知识证明的一些重要概念和思想，可以对零知识证明有直观的理解，然后讲解一个经典简洁的零知识证明安全协议Schnorr协议。本文首先来总体介绍一下零知识证明，然后分析交互式Schnorr协议和非交互式Schnorr协议。零知识证明(Zero-Knowledge Proof)，是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的。证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。零知识证明实质上是一种涉及两方或更多方的协议，即两方或多方完成任务所需采取的一系列步骤。
“P”表示 “证明者(Proofer)”：作为零知识证明的参与方，他在证明命题真实性的同时，不会泄漏任何相关信息。
“V”表示 “验证者(Verifier)”：作为零知识证明的另一参与方，验证证明者提出的命题以及对应的证明是不是正确。
“承诺阶段(Commit)”：证明者针对命题做出承诺，并等待验证者提出挑战并进行验证。
“挑战阶段(Challenge)”：验证者选择随机数，对提出的承诺进行挑战。
“回应挑战阶段(Response)”：证明者将收到的随机数并结合给出的承诺，返回挑战的回应。
“验证阶段(Verify)”：验证者验证，挑战的回应是否正确，错误的话那就证明失败，如果成功就可进行下一次挑战，直到可以相信的概率达到验证者接受的条件，这样就证明成功。
正确性。没有人能够假冒P使这个证明成功。如果不满足这条性质，也就是P不知道“知识”，再怎么证明，V也很难相信P拥有正确的知识。完备性。如果P和V都是诚实的，并证明过程的每一步都进行正确的计算，那么这个证明一定是成功的。也就是说如果P知道“知识”，那么V会有极大的概率相信P。零知识性。证明执行完之后，V只获得了“P拥有这个知识”这条信息，而没有获得关于这个知识本身的任何信息。数据的隐私保护：在隐私场景中，根据零知识性，不泄漏交易的接收方，发送方，交易余额等细节的前提下，证明区块链上的资产转移是有效的。再比如买保险的时候，保险公司需要了解是否患有某种疾病，但是我不想让保险公司知道我的全部病历信息，那我可以证明给保险公司看，我没相关疾病就足够了。计算压缩与区块链扩容：在当前的区块链架构中，同样的计算会被重复多次，比如签名的校验，交易合法性校验，智能合约的执行等等。这些计算过程都可以被零知识证明技术进行压缩。比如以太坊采用 zkSNARK，带来几十倍的性能提升。端到端的通讯加密：用户可以互相通信，但是消息记录不会完全暴露在服务器上，同时消息也可以按照服务器的要求，出示相应的零知识证明，比如消息的来源、与发送的目的地。身份认证：用户可以向网站证明，他拥有私钥，网站并不需要知道私钥的内容，可以通过验证这个零知识证明， 确认用户的身份。去中心化存储：服务器可以向用户证明他们的数据被妥善保存，并且不泄露数据的内容。Schnorr机制是一种基于离散对数难题的零知识证明机制。证明者声称知道一个密钥x的值，通过使用Schnorr加密技术，可以在不揭露x的情况下，向验证者证明对x的知情权。可用于证明你有一个私钥但是不披露私钥的内容。
原始的Schnorr机制是一个交互式的机制。Schnorr中涉及到的技术有哈希函数的性质、椭圆曲线的离散对数难题。（椭圆曲线的离散对数难题是指，已知椭圆曲线E和点G，随机选择一个整数d，容易计算椭圆曲线上另一点Q=d*G，但是给定的Q和G来计算d就非常困难。）假设Alice 拥有一个秘密数字，a，我们可以把这个数字当成「私钥: sk」，然后把它「映射」到椭圆曲线群上的一个点 a*G，简写为 aG。这个点我们把它当做「公钥: PK」。 Schnorr 协议充分利用了有限域和循环群之间单向映射，实现了简洁的零知识证明安全协议：Alice 向 Bob 证明她拥有 PK 对应的私钥 sk，那么如何证明呢。交互式Schnorr协议的流程分为三步：
第一步：为了保证零知识，Alice 需要先产生一个随机数r，这个随机数是用来保护私钥无法被 Bob 抽取出来，会映射到椭圆曲线群上的点rG上，记为R发送给Bob。
第二步：Bob 要提供一个随机数进行挑战，把它称为 c。
第三步：Alice 根据挑战数计算 z = r + a * c，然后把 z 发给 Bob，Bob通过式子进行检验：z*G ?= R + c*PK
由于z=r+c*sk，等式两边添加相同的生成元可得：z*G= rG + c*(aG)=c*PK+R。就可以验证Alice确实拥有私钥sk，但是验证者Bob并不能得到私钥sk的值，因此这个过程是零知识的，并且是交互式的。
由于椭圆曲线上的离散对数问题，知道R和G的情况下通过R=r*G解出r是不可能的，所以保证了r的私密性。
但是，整个过程是在证明者和验证者在私有安全通道中执行的。这是由于协议存在交互过程，只对参与交互的验证者有效，其他不参与交互的验证者，无法判断整个过程是否存在串通的舞弊行为，一旦两个验证者相互串通，交换自己得到的值，便可以推出私钥。因此，是无法公开验证的。进一步分析，为什么需要验证者回复一个随机数c呢？这是为了防止Alice造假。如果Bob不回复一个c，就变成一次性交互。由于椭圆曲线上的离散对数问题，知道PK和G的情况下通过PK = a * G接触a是不可能的，所以保证了a的私密性。但是这种方案是存在问题的，a和r都是Alice自己生成的，她知道Bob会用PK和R相加然后再与z * G进行比较。所以她完全可以在不知道a的情况下构造：R = r * G - PK 和 z = r。这样Bob的验证过程就变成：z * G ?== PK + R ==> r * G ?== PK + r * G - PK。这是永远成立的，所以这种方案并不正确。所以在交互式Schnorr协议中存在的私钥泄露问题，使得算法无法在公开的环境下使用。可以将原始的交互式协议转变为非交互式协议来解决这个问题！下面来看，如何把一个三步的 Schnorr 协议变成一步。 回顾一下交互式Schnorr 协议的第二步，Bob 需要给出一个随机的挑战数 c，这里我们可以让 Alice 用下面这个式子来计算这个挑战数，从而达到去除协议第二步的目的，c = Hash(PK, R)，其中 R 是 Alice 发给 Bob 的椭圆曲线点，PK 是公钥。第一个，Alice 在产生承诺 R 之前，没有办法预测 c，即使 c 最终是 Alice 生成的。第二个，c 通过 Hash 函数计算，会均匀分布在一个整数域内，可以作为一个随机数。
Hash 函数是「单向」的，这样一来，虽然 c 是 Alice 计算的，但是 Alice 并没有能力实现通过挑选 c 来作弊。因为只要 Alice 一产生 R， c 就相当于固定下来了。这样，就把三步Schnorr协议合并为一步。Alice可直接发送（R，z），因为Bob拥有Alice的公钥PK，于是Bob可自行计算出c。然后验证z*G?=R+c*PK。如图，利用 Hash 函数，把三步 Schnorr 协议合并为了一步。Alice 可以直接发送：(R, c, z)。又因为 Bob 拥有 PK，于是 Bob 可以自行计算出 c，于是 Alice 可以只发送 (R, z) 即可。·Alice：均匀随机选择r，并依次计算 R=r*G c=Hash(R,PK) z=r+c*sk·Bob(或者任意一个验证者)：计算e=Hash(PK,R)·Bob(或者任意一个验证者)：验证z*G?==R+c*PK本周五下午14:00，来自北京航空航天大学网络空间安全学院的张宗洋教授将在上海市计算机学会信息安全专委会主办，华东师范大学承办的以【区块链与隐私计算】主题的ySec空中学术论坛上，带来题为《简洁非交互零知识证明及其在区块链中的应用》的分享。简洁非交互零知识证明 (zk-SNARK) 以其信任建立和隐私保护等功能，不仅在经典密码学中应用广泛，也与区块链、隐私计算等新技术领域对信任与隐私的需求高度契合。
这次分享首先会介绍简洁非交互零知识证明的基本概念、通用构造方法和主要分类，其次介绍典型协议及其构造原理，最后介绍zk-SNARK在区块链扩容中的应用。