原文标题：一文了解最抢手zkSNARK计划：零常识证明引论（三）
在之前的文章中，咱们介绍了零常识证明的 基础概念 以及结构 zkSNARK 的 根本思维和办法。从本文开始，咱们将逐一介绍目前最抢手的 zkSNARK 计划。文章旨在让读者理解这些计划的根本原理。为了方便叙说并简略理解，在叙说计划时，咱们会做一些简化处理，重在传达计划的核心思维。
本文介绍的是 Groth16 计划。Groth16 计划，顾名思义，便是 Groth 在 2016 年宣布的一篇论文 [Gro16] 中提出的计划。目前为止，Groth16 是在实践中运用最广泛的 zkSNARK (没有之一)。特别一提的，Zcash 目前运用的 zkSNARK 计划便是 Groth16。从功能上，Groth16 的 Verifier 功能是一切 zkSNARK 中最快的，其证明字符串也是最短的。
而 Groth16 的最大缺陷便是它需求对每个电路都履行一次可信初始化。
在介绍 Groth16 之前，简略回忆一下 zkSNARK 所要处理的问题。咱们称这个问题为「核算验证问题」。
核算验证问题
任何核算都能够描述为一个算术电路。一个算术电路能够对数字进行算术运算。电路由加法门、乘法门以及一些常数门组成，如下图所示：
这个比如中的电路包含了 15 个门。这个电路所描述的核算进程需求输入五个数字 x1 到 x5，输出四个数字。
给定一组输入的数字，需求把这个电路中的每个门都核算一遍，才干核算出这个电路的输出。在这个比如中，假如输入是 (1,2,3,4,5) ，则电路的输出为 (-27,14,80,171)，如下图所示：
核算验证问题是指，假如一个验证者——不妨叫做 Verifier——只拿到了电路的一组输入和输出，如这个比如中的 (1,2,3,4,5) 和 (-27,14,80,171) ，它该如何验证这是一对合法的输入和输出呢？最简略粗犷的办法便是把这个输入从头扔进电路算一遍。假如电路很大的话，这个验证办法最大的缺陷便是功率问题。
有些场景下，功率还不是仅有的问题。例如，输入可能包含 Verifier 不能知道的隐秘信息。假定上例中的 (3,4,5) 是隐秘输入，Verifier 只能看到 (1,2) ，如下图所示。此刻 Verifier 要验证的问题就变成了「是否存在 (?,?,?) 使得电路在输入 (1,2,?,?,?) 的时候的输出是 (-27,14,80,171) 」。这个场景下，即使是简略粗犷的从头核算也不再可行。
一句话归纳核算验证问题：Verifier 能否在不知道隐秘输入的情况下，高效地验证核算成果？
从电路到 R1CS 问题
一个 zkSNARK 便是对上述问题的一个处理计划。运用 zkSNARK，一个证明者，叫做 Prover，可认为核算进程生成一个简短的证明字符串。Verifier 读取这个字符串，就能够判别给定的公开输入和输出是否合法。
Groth16 是很多 zkSNARK 结构计划中的一种。接下来，咱们介绍 Groth16 是怎样处理核算验证问题的。
首要，咱们从头审视一下 Verifier 的使命：咱们只知道电路的前两个输入是 (1,2)，咱们的方针是要判别是否存在一组合法的隐秘输入，使得电路的输出是 (-27,14,80,171)。假如咱们换个视点看这个问题，它其实能够描述为：给一个电路，上面有些空格能够填数字，有些空格现已填上了数字，请问是否存在一种填法，能够一起满意每个门的逻辑？
从这个新的视点，核算验证问题被转换成了一个类似于数独那样的填数字游戏：有一些空格，一部分现已填上，请你填上另外一些空格，满意一些约束条件。
然后，咱们为每一个要满意的条件列一个方程。这儿，每个要满意的条件其实便是一个门的逻辑：加法门的输出等于两个输入之和，乘法门的输出等于两个输入之积。所以，原来的填空游戏就变成了一个多元方程组。上述比如转化得到的方程组如下：
最后，咱们对这个方程做一些整理，使得它能够写成矩阵和向量的形式，愈加规整和简洁。咱们把每个方程都写成 * = * x * 的形式。虽然并不是一切方程中都有乘法，但咱们能够给没有乘法的式子乘上一个 。所以方程组变成了下面这个姿态：
把一切方程合到一起，就得到了原方程组的矩阵表明
咱们把终究得到的这个矩阵向量方程叫做一个 Rank-1 Constraint System (R1CS)。
总结一下，这一节中咱们把核算验证问题转化成了数学问题 R1CS。
在核算验证问题中，Verifier 知道一个电路，拿到公开部分的输入，以及电路的输出，判别它们是否合法。
从 R1CS 问题到 QAP 问题
在零常识证明范畴，R1CS 根本上便是电路的代名词。许多 zkSNARK 把 R1CS 问题作为方针问题。不过，大部分 zkSNARK 不会直接对 R1CS 下手，而是把 R1CS 问题继续转化，得到一个等价的多项式问题，再对这个多项式问题设计证明计划。Groth16 也不破例。不同的 zkSNARK 挑选的多项式问题各不相同，Groth16 挑选的是一个叫做 Quadratic Arithmetic Programming (QAP)的问题。
这一节中介绍一下怎样把 R1CS 问题转化为等价的 QAP 问题。
然后，咱们把这些列向量换成多项式，使得多项式方程和原先的向量方程等价。
把向量转化成多项式的一种方法是运用多项式插值。
多项式插值
QAP 问题
现在，咱们直接把 R1CS 矩阵中的列向量换成它们的多项式插值，得到的成果如下图所示。
咱们用一个表格总结一下上文中提到的一切问题。
为什么要越搞越复杂，把电路问题转化为 QAP 问题呢？一个简略的答复：便是为了引进多项式！多项式是一个强壮的东西。多项式的作用，能够理解为一个「杠杆」，或许叫「误差放大器」。假如咱们要查看两个长度为 10000 的向量是否持平，一定需求查看 10000 次，哪怕查看过了 9999 个点都是一样的，也不能保证最后一点是相同的。而两个 10000 次的多项式，哪怕十分挨近，比如说它们的系数有 9999 个都相同，或许它们在 这些点上的取值都持平，但只要有一个点不同，这两个多项式就天壤之别。这意味着，假如在一个很大的范围内，例如 到 傍边均匀随机选一个点，两个不同的多项式在这个点上持平的时机只有 。查看两个多项式是否持平，比查看相同规划的向量要快得多，这几乎是一切 zkSNARK 进步 Verifier 功率的底子原理。
为 QAP 问题结构 zkSNARK
QAP 问题便是 Groth16 要用来结构 zkSNARK 的终究问题了。不过，在解说 Groth16 的结构细节之前，咱们先预备一些东西。
预备东西
咱们假定读者对椭圆曲线群的根本特性和运用有所了解，并选用加法群的记号来描述椭圆曲线群中的点和运算。椭圆曲线群中的元素能够用来表明多项式，并约束 Prover 有必要运用给定的多项式来进行线性组合。这正是 QAP 所需求用到的特性。
咱们看一下椭圆曲线是怎样用来表明多项式的。
KoE 假定
然而，上述直觉并不能从离散对数假定严格地证明而来。所以，只能把它作为一个新的安全性假定来用。这个假定就叫做 Knowledge-of-Exponent (KoE) 假定。
KoE 假定怎样运用到 QAP 问题上呢？那便是，KoE 答应咱们运用椭圆曲线点来表明多项式，并且迫使 Prover 只能从已知的多项式线性组合产生新的多项式。
不过，到目前为止，咱们疏忽了两个关键问题：
关于第二个问题，一个处理办法便是双线性配对。
双线性配对
现在，咱们现已预备好了东西：KoE 假定和双线性配对。接下来，咱们就介绍 Groth16 是如何为 QAP 问题结构 zkSNARK 的。
Groth16 计划
Setup
Prove
Verify
解析
咱们简略解说一下上述结构为什么能够工作。至于它为什么是安全的，请感兴趣的读者参看 [Gro16] 原文。
当然，Verifier 的验证式中还包含了许多其他项，但在 Groth 的精心设计下，它们都消掉了。感兴趣的能够自行验证。
小结
本文中，咱们解说了 Groth16 这个 zkSNARK 计划的结构原理。咱们从算术电路开始，介绍了怎样将核算验证问题转化为 R1CS 问题以及 QAP 问题。然后咱们解说了怎样运用 Groth16 计划来证明知道一个 QAP 问题的解。Groth16 计划运用了 KoE 假定以及双线性配对。它的缺陷是需求可信第三方进行初始化，而且初始化进程需求对每个电路进行一次。与此一起，Groth16 享有最高效的 Verifier 算法以及最短的证明字符串，使得 Groth16 成为至今仍然运用最广的 zkSNARK 计划。
参考资料
[Gro16] Jen Groth. On the Size of Pairing-based Non-interactive Argument. 2016.
撰文：Cyte
视野开拓
短缺与缺乏不同，缺乏是指某物品的需求使价格或代价高于零。-《经济解释（二〇一四合订本）》
