本文介绍经典零只是证明协议——zk-SNARKs

zk-SNARK 算法简介

zk-SNARK 是 zero-knowledge succint non-interactive arguments of knowledge 的简称，其中：

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

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

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

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

zk-SNARKs的构建方式

zk-SNARKs 先将需要证明的内容转化为一系列代数方程的解的形式，具体而言是先将计算转化为算术电路，再到 R1CS，QAP，最后到 zk-SNARKs

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

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