根据上述定义，NP 语言由它的标准验证过程决定，而它的验证过程就是一段计算逻辑。编码 NP 语言，本质上是在寻找一种方式来描述「计算」。图灵机是一种描述计算的方式，还有一种方式是电路。当然，还可以用更高级的编程语言。
如果用高级的编程语言，好处是写程序相对容易，但是在构造 ZKP 时处理起来非常复杂。图灵机的执行过程很简单，为一个图灵机构造 ZKP 就比高级语言容易，但是用图灵机编程的体验就不太友好了。所以，我们要在「容易写程序」和「容易构造 ZKP」之间选择一个平衡点。
一个选择是电路。在用电路写程序方面，已经算是比较成熟了，例如 CPU 以及各种芯片、嵌入式设备、ASIC 矿机等都是电路设计。同时，电路的结构又足够简单，不至于给构造 ZKP 带来太多麻烦。
另一个选项是一个比图灵机稍微复杂一点的模型，叫做随机访问机 (Random Access Machine, RAM)模型，也是一个不错的平衡点。RAM 模型可以看做一个简单的现代计算机，包括一个 CPU 和一个内存。CPU 支持一些简单的指令集，内存可随机访问。
在表达性方面，RAM 其实比电路更有优势，因为它更接近现代计算机。用 RAM 模型描述计算过程就像用汇编写程序。把高级语言编译成汇编程序，要比编译成电路更方便一些。不过，可能是因为 RAM 模型处理起来比电路要复杂，目前大多数的 zkSNARK 是基于电路模型的，基于 RAM 模型的极少，STARK 是其中的代表，而 STARK 的构造极其复杂。
构造 zkSNARK 时，常用的是算术电路 (Arithmetic Circuit)，而不是硬件中常见的布尔电路。它们的主要区别是：
布尔电路处理的是布尔值，算术电路处理的是有限域 F 中的元素；
布尔电路的门是逻辑门，算术电路中的门是加法门和乘法门；
算术电路对涉及到代数运算的计算逻辑更友好
算术电路可以进一步转化为数学模型。这个过程叫做算术化 (Arithmetization)。下面介绍一些常见的从电路转化成的数学模型。
通过取不同的矩阵，R1CS 问题可以表示所有 NP 问题。要把一个 NP 问题编码为 R1CS，首先将它的验证过程用算术电路 C 表示，再进一步转化为 R1CS 问题 (A,B,C) 。
设多项式
下面总结一下现有的 zkSNARK 使用的计算模型：
QAP：主要是以 Groth16 方案为代表的一系列基于双线性对的 zkSNARK 在用
Hadamard 关系：使用它的方案包括 BulletProof、Sonic
R1CS：几乎所有基于电路的 zkSNARK 都用到了 R1CS，如 Groth16、Marlin、Spartan、Fractal、Aurora
分层电路：GKR、Libra 是基于分层电路的
RAM：STARK 是基于 RAM 做的，其实也进行了算术化，构造了一个叫做 AIR 的数学问题，然后经过非常复杂的转换得到一个叫 ACSP 的问题
其他：例如 PLONK 等一些 zkSNARK 都是自己搞了一个算术化方案。我们在后续文章中讲对应的 zkSNARK 方案时再做介绍。
我们刚刚讲到，NP 问题有一个标准的验证过程。相比于这个标准验证，zkSNARK 有两点优势：
零知识性 (ZK)：标准验证需要用到证据，而 zkSNARK 验证不需要，而且 zkSNARK 证明不泄露任何信息
简洁性 (Succinct)：有两点要求 a) zkSNARK 证明比证据更小 b) 且 / 或 Verifier 验证 zkSNAKR 证明比标准验证更快
这两个优势单独拿出来都是很有意义的。ZK 的意义就不用说了。即使只有简洁性，也就是 SNARK (而非 zkSNARK)，也有一些很重要的应用场景，比如说代理计算。例如，一台手机可以借助云服务器进行大量计算，而只需在本地进行少量的计算就可以验证计算结果。这个场景中云服务器并不需要隐私，也就不需要 ZK，但是需要简洁性。
注意到，简洁性的两个要求中，在「验证更快」这一点上，存在一个天然的障碍：上文提到，通用的 zkSNARK 系统中没有包含任何 NP 语言的信息，Verifier 要验证一个 NP 语言，就要把这个 NP 语言的编码输入进来，不妨记为 C。 C 需要包含完整的计算过程，那么 C 的规模其实和计算量是相当的。那么，Verifier 光是把 C 读完，就已经比这个 NP 语言的标准验证更慢了。
这个问题有两种解决方式：
假设 NP 语言的标准验证可以用很短的信息来描述。一般的电路是做不到的，因为电路大小和计算量相当。而用图灵机、RAM 或高级语言，则有可能用很少的信息描述很大的计算量，关键原因是代码可以复用。例如，高级语言代码中一个简单的循环，写下来可能不超过 100 字节，代表的计算量可能要大得多。这样的计算过程叫做「均匀 (Uniform)」计算，因为大部分计算是在执行相似的逻辑。但是，如果有均匀计算的限制，就会把一大部分 NP 语言排除在外。
对 C 进行预处理。把 C 压缩成一个很小的字符串，不妨记为 c 。Verifier 只输入 c 。当然，这样一来 Verifier 没有直接接触到需要验证的计算过程，需要一些密码学工具来防止 Prover 作恶。例如，c 可以是 C 的密码学承诺。
本质上，这两个解决方式是相通的，也就是对 C 进行压缩。如果 C 代表的是均匀计算，就可以无损压缩，否则就只能用密码学工具来压缩。
我们的目标是构造 zkSNARK。在我们的目标场景中，Prover 只需要发送一个简短的证明字符串给 Verifier，而 Verifier 不需要给 Prover 发送任何消息。
直接构造一个满足这个场景的 zkSNARK 可能会很困难。一个更灵活的方式是在先在理想模型下构造证明系统，然后用一个通用的转换，把这个只能在理想场景下的系统转化成现实场景中可以工作的 zkSNARK。
理想模型中，就是指这个模型用到了场景中并不存在的功能，叫做理想功能。理想功能的存在使得构造证明更加方便。构造好之后，使用密码学工具模拟这个不存在的功能，以实现这个理想模型。
下图是 ZKP 常用的理想模型，以及它们之间的转换关系。接下来我们会一一介绍这些模型以及它们之间的转换的具体实现。
我们在上一篇文章中介绍了交互式证明系统。站在 zkSNARK 的场景看，交互系统就是一个理想模型，因为它提供了一个场景中不存在的理想功能，即 Verifier 可以向 Prover 发送消息。
上述方法就叫做 Fiat-Shamir 变换。Fiat-Shamir 变换只能将公开随机数的交互证明转化为非交互证明，所以，接下来的理想模型中，只能考虑构造公开随机数的 ZKP。
Babai 等人在 1991 年提出了随机可查证明 (Probabilistically Checkable Proof, PCP)。在 PCP 模型中，Prover 构造一个证明字符串，叫做 PCP 证明。PCP 证明的长度可以非常长，远远超过 Verifier 的计算能力。所以，Prover 不会直接把 PCP 证明发送给 Verifier，而是向 Verifier 发送一个预言机 (Oracle)，叫做 PCP 预言机。Verifier 可以随意查询 PCP 预言机，获取 PCP 字符串任意位置的比特。
为了理解 IP 和 PCP 的关系，我们举一个现实中的例子。我们请上我们熟悉的主人公 Alice 和 Bob。假设 Alice 是一名即将毕业的研究生，Bob 的任务是评审 Alice 的课题是否合格。IP 模型就是答辩，Alice 和 Bob 直接对话，如果 Alice 能成功回答 Bob 的所有提问，Alice 就成功毕业了。而在 PCP 模型中，没有答辩，Alice 只是把毕业论文发给 Bob，而毕业论文超级长，Bob 不可能看完论文，只能在论文中随机挑选几段来读，如果挑的这些段落都没有问题，相互之间逻辑通顺，Bob 就相信 Alice 的课题是合格的。
PCP 预言机提供了这样的功能：它本身很短，传递它只需要很小的通信量；它传递的信息量却很大，通过它可以随机访问一个很长的字符串。显然，真正的 PCP 预言机是不存在的，PCP 是一个理想化的模型。
上述过程中的 Merkle-Tree 可以用更一般的密码学组件向量承诺 (Vector Commitment, VC)来代替。VC 使得 Prover 可以向 Verifier 发送一个短的字符串 ，代表对一个向量的承诺，而 Verifier 可以令 Prover 展示出这个向量中的任意位置的值，并提供合法性证明，证明的长度远小于向量的长度。实际上，Merkle-Tree 就是一个简单的 VC 实现。
IPCP (Interactive PCP) 模型可以看做 IP 模型和 PCP 模型的相加。在 IPCP 模型中，Prover 向 Verifier 发送了 PCP 预言机后，Prover 和 Verifier 继续进行交互。交互过程中，Verifier 可以不时地访问 PCP 预言机。
继续使用上一节中 Alice 和 Bob 的例子。如果说 IP 模型是只有答辩，PCP 模型是只有毕业论文，那么 IPCP 模型就是在 Alice 答辩之前把毕业论文发给 Bob。在答辩过程中，Bob 可以一边看毕业论文一边向 Alice 提问。
基于 IPCP 模型构造的证明系统也可以通过 Merkle-Tree 或一般的 VC 方案转化成 IP 模型下的证明系统，过程和 PCP 模型的转换完全一样，区别仅在于，Verifier 在查询 PCP 证明的请求中可能夹杂着普通的交互。
IP 模型和 PCP 模型都可以看做是特殊的 IPCP 模型。其中，IP 模型相当于在 IPCP 模型中 Prover 发送一个空预言机给 Verifier。PCP 模型相当于在 IPCP 中省略掉 Prover 和 Verifier 的对话环节。
如果说 IPCP 模型是把 IP 和 PCP 模型做加法，那么 IOP (Interactive Oracle Proof) 模型就是把 IP 和 PCP 做乘法。在 IOP 模型中，Verifier 向 Prover 发送消息，而 Prover 则向 Verifier 发送 PCP 预言机。Verifier 可以随意查询 Prover 发过的任何 PCP 预言机。
继续使用前面 Alice 和 Bob 的例子来解释 IOP 模型。Alice 把毕业论文发给 Bob，Bob 给 Alice 回复一个简短的评论意见，然后 Alice 再写一篇论文发给 Bob，Bob 再回复，这样来回进行多次。这个过程中，Bob 可以随时阅读 Alice 发给过他的任何一篇论文，当然 Bob 的时间仍然不够，Bob 仍然只能随机选取一小部分阅读。最后，Bob 判断 Alice 的课题是否合格。
和 PCP、IPCP 一样，在 IOP 模型下构造的证明系统也可以类似转化成 IP 模型下的证明系统。
IPCP 模型可以看做特殊的 IOP 模型。在 IPCP 模型中，把对话环节的 Prover 消息都看做一个 PCP 预言机，那么一个 IPCP 模型下的协议就可以看做 IOP 模型下的协议。
多项式 IOP (Polynomial IOP, PIOP) 模型是对 IOP 模型的进一步一般化。和 IOP 模型类似，在 PIOP 模型中，Verifier 向 Prover 发送消息，而 Prover 向 Verifier 发送预言机，不过这次不同的是，Prover 发送的是多项式预言机。
因为多项式预言机可以实现 PCP 预言机的功能，IOP 模型可以看做特殊的 PIOP 模型。
把 PIOP 模型下构造的证明系统转化为 IP 模型下的系统，基本思想是和 PCP、IPCP 以及 IOP 的情况一致的，即让 Prover 代替多项式预言机的角色，但是需要的密码学工具就不一样了。简单的 Merkle-Tree 或 VC 是不能模拟多项式预言机的。我们要用到一个更强大的密码工具，叫做多项式承诺 (Polynomial Commitment, PC)。
接下来我们介绍另外两个模型，LIP 和 LPCP。目前已有的 Verifier 复杂度和证明大小为常数级别的 zkSNARK 都是基于这两个模型构造的。
在线性 IP (Linear IP, LIP) 模型中，Prover 和 Verifier 进行对话。但是，相比于 IP 模型，增加了一些限制条件：Prover 只能是线性的。
这样一来，不仅 Prover，连 Verifier 也只能够进行线性运算了。这么一来，这个系统就没多大意义。为了能让 Verifier 做至少一次非线性运算，一个方法就是引入双线性对。双线性对允许对密文做乘法，但是乘法的计算结果是在另外一个密文空间中的，所以不影响安全性。
本文介绍了构造通用简洁零知识证明 (zkSNARK) 的基本原理和常用工具。首先讨论了 NP 的刻画方式，包括图灵机、电路以及 R1CS 等数学问题。然后讨论了实现简洁性的必要方式：要么假设计算是均匀的，要么使用预处理。最后，理想模型中构造零知识证明比直接在非交互场景中构造更加方便，本文介绍了若干理想模型，以及怎样将理想模型中的零知识证明转化为 zkSNARK。
声明：本文为转发软文，观点仅代表作者本人，绝不代表赞同其观点或证实其描述。
提示：投资有风险，入市须谨慎。本资讯不作为投资理财建议。
