概述

前段时间听9th BIU的时候，听不下去了，感觉缺了不少的数学基础，包括Elliptic Curve Cryptography以及zk-SNARKs底层需要的构建组件，于是上周学习了一下R1CS到QAP的转换，论文什么的还没太有时间看

于是打算先从Zcash的官方文档开始看起，讲的比较简单，相较于论文也更好理解，于是翻译了一下Zcash的八篇文章，里面加上了一些自己的理解，部分理解有误或梳理不通顺之处劳烦指出

什么是zk-SNARKs

Zcash是zk-SNARKs的首次广泛应用，zk-SNARKs是一种新的零知识密码学形式，Zcash强大的隐私由这个样一个事实保障：Zcash中的屏蔽交易可以在区块链上完全加密，但仍然可以使用zk-SNARK证明在网络共识规则下验证为有效

zk-SNARK是Zero-Knowledge Succinct Non-Interactive Argument of Knowledge的缩写，意思是简洁零知识非交互式论证

非交互指的是Prover和Verifier之间可以不进行任何的交互（P和V来回发送消息）

零知识允许Prover向Verifier证明一项陈述为真，而不泄露除了该陈述为真以外的任何有效的信息（比如给定一个随机数的散列，Prover可以向Verifier证明其知道这个随机数而不透露这个数）

简洁则意味着证明可以在短时间内完成（比如毫秒级别的时间），即便对于非常大的陈述而言证明也是非常快的，且不需要太多的通信量（仅需要几百字节）

因为以往的交互式证明系统中P和V需要互相发送消息，甚至为了降低合理性错误需要很多的交互轮次，从而导致通信量急剧增加，而非交互的简洁的结构中，P可以仅向V发送一个包含少量自己的消息就可以完成验证，为了做到这种短到足以让其发布到区块链上的非交互式的证明，目前采用的方法是P和V之间生成一个CRS并将其作为公共参数（参见之前的文章），从而完成证明

不过换言之，如果敌手能够获得用于生成这些参数的秘密随机性，则意味着他们将能够创建对Verifier有效的虚假证明，在Zcash上这样的敌手意味着其可以创造假币，为了防止这种情况发生，Zcash精心设计了通过多个参与方共同生成的公共参数，

zk-SNARKs在Zcash中的构建方式

为了在Zcash中拥有零知识隐私，根据网络共识规则确定交易有效性的函数必须返回交易是否有效的答案，而不披露其执行计算的任何信息，这一过程通过在zk-SNARK中编码网络的一些共识规则来实现的，换个角度而言，zk-SNARKs先将需要证明的内容转化为一系列代数方程的解的形式，具体而言是先将计算转化为算术电路，再到R1CS，QAP，最后到zk-SNARKs

在这个过程中，需要将验证交易合法性的函数转化为一个数学表达式，第一步是将逻辑步骤分解为尽可能小的操作，即创建一个算术电路，这和布尔电路类似（程序被编译为离散的单个步骤，如AND、OR、NOT等），转换为算术电路后，函数就分解为加减乘除等基本算术运算（特殊情况下会尽可能避免除法，或直接不使用除法）

举个例子，比如说想要计算表达式$(a+b)*(b*c)$，转化为下面这个算术电路

上述电路中各个输入按照表达式经过对应的门，最终达到输出，接下来是建立一阶约束系统（R1CS），以检查值是否正确的经过了应当经过的门，比如在上述例子中，R1CS会检查Gate2的输出是否是$b*c$

在R1CS中，Verifier必须检查许多约束条件（几乎电路中的每一个路径都有一个约束条件），然后是将所有的约束条件捆绑在一起，这篇论文里面提出了一个好方法，称为二次算术程序（QAP），在QAP下，只需要检查多项式之间的约束即可，而无需检查数字之间的约束，尽管这个多项式会很大（阶数很高），但是检查非常的方便且可以满足正确性，因为当一个恒等式在该多项式上不成立时，意味着其在大多数点上也不成立，因此只需要检查两个多项式在某个随机的点上是否成立，即可在很高的概率下使得证明通过

但如果Verifier事先知道Prover将要选择哪一个点进行检查，则Verifier可以设计一个无效的多项式，但该多项式仍然可以通过检查，在zk-SNARKs中通过引入复杂的数学定理（如同态加密和椭圆曲线对）来完成多项式的隐秘计算，换句话说，就是通过加密之前提到的公共参数来确定要检查的点，使得Prover和Verifier都不知道这个点是什么

到目前为止，主要介绍了zk-SNARKs中的S和N，但还没有介绍zk，zk允许Prover在秘密不泄露的情况下完成验证，zk的部分可以通过让Prover将原始的多项式进行随机移位来完成，使得移位后的多项式仍然可以通过验证，但是加入了零知识的特性

zk-SNARKs如何创建隐蔽交易

比特币中通过链接公链上的发送方地址、接收方地址和输入输出的值来验证交易，但Zcash使用zk-SNARKs证明该交易已满足有效的条件，同时还可以透露相关的地址或值，此时发送方隐藏交易的方式是构造一个证明，其以高概率证明下列三个陈述

  • 每个隐蔽交易的输入和与输出和相等
  • 发送方证明其拥有输入票据的支出私钥，从而有权限验证其支出
  • 输入票据的支出私钥通过加密的方式与整个交易的签名相关联，因此不知道私钥的一方无法修改交易

此外，隐蔽交易还需要满足下列条件

比特币采用UTXO来决定哪些交易是可支出的，在Zcash中，对UTXO的隐蔽等效于承诺，支出一个承诺意味着揭示一个无效的承诺（nullifier）（？）Zcash结点维护一个列表来保存所有已创建的承诺和所有已被揭示的无效的承诺，承诺和无效承诺都以Hash的形式保存，从而避免了任何有关承诺的信息被泄露，或者无效承诺与承诺之间的关联性

对隐蔽支付创建的每个新的票据，都会发布一个承诺，其中包含票据的接收地址、发送的金额、随机的nonce和票据的唯一标识$\rho$（会被用于推导出无效承诺），也即

$$ Commitment=Hash(Recipient Addr,amount,\rho,nonce) $$

当这笔隐蔽交易被支出时，发送方利用其支出私钥和唯一标识$\rho$发布一个无效承诺并提供零知识证明来证明其有权使用这笔支出，也即

$$ Nullifier=Hash(Spending Key,\rho) $$

其中唯一标识$\rho$必须时已被承诺且仍未被支出的值，此外这个Hash值不能存在于区块链中每个结点保存的nullifier中

除了验证上述条件外，零知识证明还需要验证下列三个事实

  1. 每个输入票据都存在一个已公开的承诺
  2. nullifier和票据承诺均计算正确
  3. 输出票据的nullifier和其他票据的nullifier不冲突（不重复）

除了用于控制地址的支出密钥外，Zcash还使用一组密钥来创建和检查证明，这组密钥与之前的公共参数一起生成，并在Zcash中的所有参与者之间共享，对于每个隐蔽交易，发送方使用其证明密钥生成对输入的有效证明，矿工使用验证密钥并通过检查Prover的计算来检查隐蔽交易是否合法，Zcash证明的生成过程较为复杂，要求Prover完成更多的计算，但这样可以极大的简化验证的过程，因此Zcash中的主要计算工作转移到了交易的创建者上（Zcash创建交易可能需要几秒钟，但是验证只需要几毫秒）

Zcash隐蔽交易的隐私依赖于现有的标准、经过试验和测试的密码技术（比如Hash函数和流密码），但其作为zk-SNARKs的添加并应用承诺和nullifier使得隐蔽交易发送方和接收方验证加密交易的有效性，其他为加密货币提供隐私的方法依赖于隐蔽交易之间的联系，但Zcash交易可以存储在完全加密的区块链上，这种方式为加密货币应用开辟了新的可能性

加密交易允许各方享受公共区块链的好处，同时仍然保护其隐私

zk-SNARKs的未来应用

在Zcash中创建隐蔽交易只是zk-SNARKs的一个应用例子，理论上zk-SNARKs可以验证任何关系但不泄露输入或其他信息，尽管为复杂函数生成证明仍然是一个计算上过于密集的手段，对大部分应用来说并不实用，但是仍然可以优化zk-SNARKs使其变得更高效

小结

本文简单介绍了一下zk-SNARKs的大致框架，以及如何用zk-SNARKs构建Zcash，接下来的文章主要围绕zk-SNARKs展开，从同态隐藏开始，一步步的介绍如何构建一个相对完整的zk-SNARKs

本系列文章撰写于研一，受笔者知识面与理解能力的局限，部分概念与定理的表述难免有不准确与不严谨的地方，烦请各位专业人士斧正

参考文章

$[1]$What are zk-SNARKs? - electriccoin-blog