零知识证明定义

以图染色为例子进行说明。证明者可以向验证者证明其知道一个图的有效着色，而不透露它。为了做到这一点，两方执行一个游戏，由证明者用一组随机的颜色给图形上色，然后覆盖它，验证者随机选择一条边。如果证明者的着色是有效的，那么由这条边连接的两个节点必须具有不同的颜色。然后重复，每次换一套不同的颜色，直到验证者相信证明者知道图的有效着色。由于证明者在每一轮之前重新绘制图形，所以验证者不会了解任何有关着色的信息，但验证者可以验证每次都是有效的。 零知识证明比较著名的案例为区块链系统中的数字签名，由证明者产生一个证明来使其他人知道其拥有一个私钥，具体方案是通过私钥对一个消息进行加密，再公开公钥和消息的明文与密文。由于公私钥加密的对应关系，如果通过公钥解密的消息与明文消息一致，则可以证明证明者私钥的正确性。

zk-SNARK

zk-SNARK全称为零知识-简洁非交互知识声明，其核心在于简洁与非交互性。 如果证明很小（证明大小的时间复杂度不高于O(log(n))，那么证明就是简洁的。这意味着，无论原本索要证明的事实有多复杂，zkSNARK都可以保持证明的小而快速。目前在区块链系统中，ZKSNARK对构建EVM-rollup非常有技术前景:在以太坊layer2的构建中，矿工通过生成一个简洁的证明，证明L2链上发生的所有交易都是有效的，足够简洁。生成的证明则在L1的合约中验证它。 至于非交互性，说明证明方和验证放之间在知识证明过程中不需要进行交互，只需要证明方按照协议生成证明之后，让验证放随时可以通过公开信息和证明来验证证明方的知识合理性。

零知识证明的种类

在零知识证明中，除了zk-SNARK，还有STARK（简洁透明知识声明）与Bulletproofs(子弹证明)。它们在生成和验证证明的运行时间、生成的证明大小以及对可信设置的需求方面有所不同，具体可见下图。 在zk-SNARK同样有着多种实例化证明框架。其中Groth16是最受欢迎的，但是其需要可信设置。PLONK系列，包括TurboPLONK和UltraPLONK，优点在于牺牲证明生成和验证时间的情况下消除对特定电路可信设置的需要，或者增加对新类型操作的支持。同时不同的零知识证明系统应用不同的椭圆曲线和多项式承诺框架。

可信设置

部分zk-SNARK系统需要进行可信设置，可信设置是由多个参与者运行的一次性程序，它产生一组随机通用参考字符串CRS，为ZK证明系统提供基础设置。CRS的重要性在于其能够防止所有参与者串通并破坏证明系统。 目前Groth16，需要为每个电路设置一个可信的设置:PLONK只需要一个通用的可信设置，该可信设置可以在基于PLONK知识证明系统中进行复用。STARKs不需要任何可信的设置。

约束

ZKPs在执行期间主要处理的目标为：证明在一个数学约束系统上运行。实际解释就是现有框架的零知识证明“引擎”不会执行z:=xy类似的代码，而是处理类似xy-z=0这类约束。目前Circom只允许在变量上写平方表达式约束，Halo2允许写任何程度的多项式约束。总结，用ZKP语言编译程序的输出之一将是约束的集合。 由此可以发现某些运算比其他运算更易在ZKP中表示:比如加法运算只需要一个约束就可以在零知识证明系统中表示，但是位操作则可能需要数百个约束，因为每一位可能需要作为单独的变量表示。这就是在处理zkp时通常选择特定加密原语的原因。例如，Pedersen哈希是一种哈希函数，它可以比keccak更有效地在算术电路中表示，因此它们经常出现在zkp中。

有限域

约束作用于一个由底层椭圆曲线决定大小的有限域中。在零知识证明的运算中，所有的算术运算都是对某个值取模计算的。在有限域的限制下，如果要为零知识证明中的整数定义特定阈值，则需要为其添加额外的约束。

零知识证明的作用

零知识最近引起了很多关注的原因在于其可以作为一种低成本验证任何计算的手段，有效地成为通用的加密构建块。 零知识证明也被Gubsheep将描述为可编程密码学，可以使用零知识证明为一般性问题编写加密证明。例如，可以使用专门为解决这个问题而构建的环签名来证明集合成员资格，或者只是为它编写一个zkSNARK电路。

零知识证明中的“电路”

电路是基于零知识证明体系或者已有框架（如Halo2）所编写的前期程序，其电路中的变量一般被称为"信号"。以Circom 零知识证明框架为例构建一个证明存在公共变量a,b，c并让这三个变量满足关系c=(a×b)^2电路，则进行如下定义： 在该电路设计中，定义两个输入信号a,b以及一个中间变量ab满足ab=a×b，最后定义公共输出c。在实际的电路定义中，由于Circom不支持二次多项式以上的运算，所以需要中间变量信号ab。

零知识证明的创建和验证

使用ZKP电路的工作流程分别由证明者和验证者执行。同时在证明器中，生成证明也涉及多个步骤，具体如下表示: 1.首先编写并编译电路。这将输出几个“组件”，例如由电路定义的约束集，以及将在接下来的步骤中使用的脚本或二进制文件。 2.如果使用Grouth16零知识证明系统，则需要运行一个可信的设置仪式来生成证明和验证密钥，通过这些密钥是对验证过程中的材料进行加密。 3.当与的zk-app交互时，由用户输入电路的私有和公共输入。第一步是“执行”电路，此时会使用步骤1中生成的脚本或二进制文件。此时计算给定输入的所有中间变量和输出变量的值。在上面的例子中，给定a = 2和b = 3，它将计算出ab = 6和c = 36。把每一个信号赋值给它的具体值称为见证(wintness)或者追踪（trace）。 4.给定步骤3的trace和步骤2的证明密钥，证明者现在可以生成电路中定义的所有约束都保持的零知识证明，并且只显示输出值c。现在可以将该证明发送给验证者。 5.验证者使用提交的证明和验证密钥，现在可以验证其公开输出的证明是正确的。在已有示例中，验证者可以加密检查证明者是否知道三个值 (a, b, ab)使得 a × b = ab， ab × ab = c, c = 36. 因为证明是简洁的，所以验证证明会非常容易，由此在EVM智能合约上验证证明而不是验证计算本身将会大大减少以太坊Gas消耗，所以零知识证明在以太坊网络中具有非常广阔的应用前景。

零知识证明的执行与约束

在上面的工作流中，电路被证明者使用了两次:第一次生成见证，然后导出证明所涵盖的约束。基于上面的实例加强理解，则有： 在上图中，这两个指令是包含对变量的约束与赋值，其可以具体划分为两个步骤，如下图所示： 上图中第一条指令表示在执行期间，将a×b的值分配给ab，此时不考虑值的约束，第二条指令则增加强制约束，使得ab恒等于a×b.

IsZero 电路

IsZero电路的逻辑是如果输入信号为0，则其输出为1。在Circom 中，其实现如下图所示： IsZero电路中的执行和约束是实现了完美的解耦。约束in * out = 0表示当in或out为零。如果in是零，那么out = -in * inv + 1 = 1。如果out为零，那么in * inv = 1，这意味着in不能为零！ 此时使用的运算比二次表达式复杂得多:IsZero中有一个条件运算、一个比较运算和一个除法运算。这是因为执行阶段与约束无关，因此不受生成ZKP的限制的约束。因此在执行阶段工作时，则进行普通的编程，以访问额外的操作符，控制流语句，和辅助函数。

零知识证明的实用语言

能够实现零知识证明的编程语言有Circom、Halo2等。

Circom

Circom语言具体是附带了一个基于rust的编译器CLI，以及一个用于可信设置、证明生成和验证的npm包。使用npm包能够让用户在浏览器中生成证明，由此来构建zk-app。同时还可以自动生成用于验证链上证明的Solidity合约。Circom还允许用户在Groth16和PLONK之间选择验证引擎。 在Circom中，其工作的本质为组装电路，其中每个电路都有一组输入、内部和输出信号。电路被定义为模板，可以用编译时已知的值对其进行参数化，这类似于c++函数模板。Circom在执行阶段也有函数作为可重用构建块的概念。 Circom面临的主要难点在于使用者需要明确约束生成代码的生成时机以及见证生成代码的生成时机，同时需要跟踪哪些值是在编译时已知的，而哪些是在运行时才知道的。许多语言结构只适用于见证生成，比如布尔运算符或比较运算符，或者只能依赖于在编译时已知的值，比如控制流语句。另外，记住约束和见证生成时间之间的差异，可以防止约束不足的计算错误。

Circom的剪刀-石头-布实例

用Circom编写剪刀石头布问题的电路。在Circom环境下，用户不可能在约束中编写条件表达式，因此需要借助基于数学的技巧。举个简单的例子，第一个电路，通过检查输入是0、1或2来验输入，则有: 计算单轮分数的代码使用类似的结构，以及CircomLib的IsEqual电路： 最后，最外层的回路通过一个可参数化的轮数n进行循环，并汇总所有分数。

Halo2

Halo2是一个基于Rust的零知识证明框架，由ZCash团队维护。Halo2基于PLONKish构建算术化证明体系，让使用者能够非常直接地控制电路在算术中的表示方式。这使得Halo2非常较为简单，非常适合编写高度优化的电路。

但是，Halo2的学习曲线是比较陡峭的。首先必须了解PLONKish算术的工作原理来构建电路，其次需要适应Halo2的复杂的API。学习Halo2的资源也很少：我发现最好的是0xparc课程，它提供了一些真正有价值的代码样本，以及主程序库中的例子。你可能还想看看awesome-halo2的最新资源。

Halo2有两种框架：由ZCash维护的vanilla，以及由Ethereum的隐私和扩展探索团队的分叉，它使用不同的多项式承诺（KZG而不是IPA），对Ethereum更友好。

PLONKish算术化

在Halo2中构建电路的关键是开始设计底层的PLONKish矩阵是什么样子的。在PLONKish中，电路被定义在一个你直接定义的矩阵上。这个矩阵由多列组成，其中一列可以代表一个公共输出（称为实例）、一个私人见证值（称为建议）、一个常量值（称为固定值）、一个关于约束是否被启用的标志（称为选择器），或者一个查找值（用于查找表，一个高级功能）。 一旦建立了矩阵，就该使用门定义多项式约束了。Halo2中的门定义了一个或多个约束，这些约束将应用于矩阵中的一组单元。每个门都是通过一个选择器列来控制的:如果选择器在一行上启用，那么将强制执行相对于该行的门所施加的约束。一个gate可以跨多行定义约束 在上面的代码示例中，a0和a1是建议列，s_mul是定义是否强制执行多乘法门的选择器。如果是，那么下一行中a0的值将被约束为等于当前行中a0和a1的乘积。

Halo2中的Chips, gadgets, and regions

Halo2中电路的主要构件是 gadgets和Chips。Chips是最低级别的单元。一个Chips通常会暴露出一种配置其门的方法，以及在合成过程中为其单元分配数值的多种方法，同时使用者也可以建立由其他Chips组成的新Chip。另一方面，gadgets在更高的抽象层次上运作，隐藏了底层Chip的实现细节，Halo2支持直接从Chip中构建电路，也可以通过gadgets构建电路。 由于Chip总是在相对偏移量上操作。这使得多个Chip可以在一个电路中被分组为不同regions。一旦所有的regions和它们的形状都被定义，Halo2中由floor planner来责任在矩阵上安排这些regions，使用者不需要直接定义每个chips的实际放置位置。

Halo2 Rust API

在Halo2中，与Circom类似，零知识证明代码将在不同的情况下被多次调用:无论是配置矩阵、生成约束、创建证明还是计算见证 所以定制电路时需要实现一个特定的电路特性，该特性定义了将在整个生命周期中调用的方法，这些方法可能带有具体的值，也可能带有未知的值，如下图所示： 这里重要的部分是配置和合成。TLDR是由configure建立矩阵的形状及其门，synthesis计算见证并将相应的值填充到矩阵中。但是，在其他阶段也可能使用未知值调用synthesize，因此需要始终使用包装值，同时，Halo2中的多项式约束是在配置期间定义的，而等式约束是在合成时建立的。

Halo2 的剪刀-石头-布实例

Halo2中的RPS，首先，在PLONKish矩阵中设置了以下几列：

两个棋手的advice column，xs和ys，其中第i行的数值代表棋手在第i轮选择了什么棋。 第三个advice column accum来追踪累积的总分，所以第i行包含了到第i轮为止的所有回合的分数之和。 一个公共instance colum，其中最后一个单元格被限制为等于 accum 的值，所以只有总分被揭示，而不是中间分。 一个选择器，用于启用单门，验证输入并计算每轮的分数。

主芯片定义了一个自定义门，该门封装了每个回合的所有约束:验证输入是否在范围内，计算该回合的分数并将其添加到累积总分中。该芯片使用一行中的xs、ys和accum的值作为“输入”，并在下一行accum列中“输出”新的分数。 上面的y_wins和is_draw是IsZero芯片，定义如下。 在合成电路时，对每一轮的输入进行循环，计算累积得分，并将计算出的数值分配给定义好的矩阵。注意，对于 "执行 "模式，则直接使用条件表达式来计算得分。 最后一位是将总分作为电路的公共输出，通过约束实例列以匹配矩阵最后一行中的累加列: