一起了解最热门的zkSNARK方案——零知识证明引论（三）

21-01-25 17:34

阅读本文需 11 分钟

AI 总结

看总结

原文标题：《一起了解最热门的 zkSNARK 方案——零知识证明引论（三）》

原文来源：Nervos 中文社区

在之前的文章中，我们介绍了零知识证明的基础概念以及构造 zkSNARK 的基本思想和方法。从本文开始，我们将逐一介绍目前最热门的 zkSNARK 方案。文章旨在让读者理解这些方案的基本原理。为了方便叙述并容易理解，在叙述方案时，我们会做一些简化处理，重在传达方案的核心思想。

本文介绍的是 Groth16 方案。Groth16 方案，顾名思义，就是 Groth 在 2016 年发表的一篇论文 [Gro16] 中提出的方案。目前为止，Groth16 是在实践中使用最广泛的 zkSNARK (没有之一)。特别一提的，Zcash 目前使用的 zkSNARK 方案就是 Groth16。从性能上，Groth16 的 Verifier 性能是所有 zkSNARK 中最快的，其证明字符串也是最短的。

而 Groth16 的最大缺点就是它需要对每个电路都执行一次可信初始化。

在介绍 Groth16 之前，简单回顾一下 zkSNARK 所要解决的问题。我们称这个问题为「计算验证问题」。

计算验证问题

任何计算都可以描述为一个算术电路。一个算术电路可以对数字进行算术运算。电路由加法门、乘法门以及一些常数门组成，如下图所示：

一句话概括计算验证问题：Verifier 能否在不知道秘密输入的情况下，高效地验证计算结果？

从电路到 R1CS 问题

从 R1CS 问题到 QAP 问题

多项式插值

QAP 问题

现在，我们直接把 R1CS 矩阵中的列向量换成它们的多项式插值，得到的结果如下图所示。

小结

本文中，我们解释了 Groth16 这个 zkSNARK 方案的构造原理。我们从算术电路开始，介绍了怎样将计算验证问题转化为 R1CS 问题以及 QAP 问题。然后我们解释了怎样使用 Groth16 方案来证明知道一个 QAP 问题的解。Groth16 方案使用了 KoE 假设以及双线性配对。它的缺点是需要可信第三方进行初始化，而且初始化过程需要对每个电路进行一次。与此同时，Groth16 享有最高效的 Verifier 算法以及最短的证明字符串，使得 Groth16 成为至今仍然应用最广的 zkSNARK 方案。