零知识证明流派简介

一句话介绍 ZK(Zero Knowledge Proof):证明者(Prover)说服验证者(Verifier)相信某些声明是真的,但除了声明是真的之外,验证者没有获得其他信息。

ZK 是为匿名而设计的。试想我们可以证明我们的身份证号码是有效的,但是验证者并不能获得我们的身份证号码。这在信息过渡索取的今天,具有重大意义。

让我们来看一个更加生动的例子。小明和小红在玩数独。小红想向小明证明她找到了数独的答案,但同时又不透露这个答案,因为小明还没解出这个数独。你将如何设计这个证明?

我们把数独写到卡片上。每张卡片上有一个数字。将他们按照答案排列好,正面朝下。小明可以随机选择一列,一行或者一块。小红将拿出小明所选择的那些卡片,随机打乱后,将这些卡牌翻过来,正面朝上。如果这些卡牌是不重复的 1-9,那么小明知道小红解出了数独的某一部分,但也或许是运气。重复以上步骤,如果每次都是正确的。那么就几乎不可能是小红运气好,而是小红真的知道答案。虽然小明得知小红解出了数独,但是小明仍旧不知道数独的答案。

如果你还是有点疑惑,欢迎观看这个视频。UCLA 的计算机教授将以 5 种难度形式,解释什么是 ZK。

1. 常见零知识证明流派

在介绍零知识证明流派之前,大家要注意我们常说的 ZK-SNARK 不是一种算法,而是一种流派。ZK-STARK 是一种具体零知识算法的名字。

我们最常见的可能是 ZK-SNARK。SNARK 的缩写是 succinct non-interactive arguments of knowledge。SNARK 最特殊的点在于他的 N,非交互性。

  • 简洁性(Succinct):验证所需要的计算资源远远小于重新跑一遍需要证明的程序
  • 非交互性(Non-interactive):证明者和验证者不需要每一轮都沟通。他们只需要在一开始完成可信初始化(Trust Setup)。其他验证者也可以在可信初始化之后加入验证
  • Argument:如果证明者有着无比强大的算力,那么他可以生成假证明。如果这种情况发生,主流的公私钥加密模式也不再安全
  • 知识(Knowledge):证明者需要知道一些其他人不知道的秘密,才能生成证明

ZK-SNARK 最大的问题在于它需要可信初始化。可信初始化会生成参考字符串(Reference String)。如果 RS 被泄露,那么任何人都可以生成虚假证明。此外,如何设计多人参与的可信初始化也很具有挑战性。RS 还只能被用于置顶的程序。对于其他的程序,我们需要另外的可信初始化。因此 ZK-SNARK 不可能用于通用计算。另外一点,RS 不能升级。如果我们升级了程序,可信初始化要重新运行。

ZK-SNARK 的问题是信任建立阶段。信任建立阶段会产生参考字符串。如果参考字符串被泄露,任何人都可以做一个假证明。此外,如何在多方之间协调这种信任设置阶段也很复杂。参考字符串只能在一个程序(电路)中使用。因此,在一般的计算中,不可能有 ZK-SNARK 的单一信任设置。另一个问题是,参考字符串是不可升级的。如果我们升级程序,我们需要重新运行信任设置阶段

为了解决这一系列的问题,科学家们找到了两个方向

Transparent Setup:可信初始化生成公共参考字符串(Common Reference String)。CRS 是公开的,不需要保密。Fractal,Halo,ZK-STARK,SuperSonic 都是采取了这一条路线。这一条路线的问题是生成的证明占用太多的存储,来到了 kB 的量级。对于区块链来说,存储是非常昂贵的。

Universal Setup:可信初始化生成了结构化参考字符串(Structure Reference String),但它需要保密。SRS 让可信初始化可以用于不同的程序,这让通用计算的证明可能实现。Marlink,SuperSonic-RSA 和 Plonk 都采用了这条路线。

2. 业界广泛采用以下几种算法

Groth16:Zcash 一开始使用了这种算法。它是零知识证明中的跑分对照组,因为它具有证明快,生成的证明小的特点。它的缺点是需要可信初始化,并且一次可信初始化只能针对一个程序

Sonic:支持 universal setup. SRS 的大小和程序大小成线性关系。生成的证明是固定大小,但是验证需要消耗很多的计算资源。Sonic 让通用计算的零知识证明变为可能

Fractal:支持递归(Recursion)。生成的证明占用较多空间

Halo: 支持递归,但并不满足简洁性(Succinct)因为证明时间是非线性的

SuperSonic:第一个实际的,可以应用的 Transparent ZK-SNARK

Marlin:程序可以升级。性能处于 Sonic 和 Groth16 之间

Plonk:程序可以升级;参与者按照顺序加入可信初始化。这让举行有很多人参与的可信初始化不那么复杂;Plonk 使用 Kate commitments 而不是多项式承诺。 (ZK-SNARK 的第一步是将计算问题转化为多项式问题)

下图是零知识证明算法的 Benchmark,基于这个实验。

Here is the benchmark based on this research. CRS 是 Transparent Setup 路线中生成的公共参考字符串。SRS 是 Universal Setup 路线中生成的结构参考字符串。证明的大小将决定要占用 Layer1 多少的存储空间。证明和验证的时间决定了计算资源的消耗。

以下有更多的 Benchmark 和算法对比:

  • Benchmarking Zero-Knowledge proofs with isekai | by Guillaume Drevon | Sikoba Network | Medium
  • Zero-Knowledge Proofs: STARKs vs SNARKs | ConsenSys
  • Community Proposal: A Benchmarking Framework for (Zero-Knowledge) Proof Systems (zkproof.org)
  • Comparison of Different zk-SNARKs

总结以下,当我们看到一个新的 ZK 算法时候,以下指标是我们需要在意的:

  • 证明时间
  • 验证时间
  • 一笔交易和十笔交易打包后的证明大小
  • 可信初始化
  • 参考字符串长度
  • CRS 支持
  • SRS 支持
  • 递归证明支持
  • 能否抵抗量子计算机
  • 安全性基于任何密码学假设

ZK 在最近几年走出实验室,逐渐步入应用。ZK 两个主要应用方向是 Rollup 和隐私。ZK 对于隐私产品的变革是显而易见的,得益于 ZK 可以让验证者不获得任何额外信息。Rollup 依赖于 ZK 的两大特性:简洁(Succinct)和递归(Recursion)。简明的特性有助于验证者节省大量的计算资源。验证者不需要重新运行整个程序。递归特性有助于节省存储空间。通过递归,区块链可以保持一个固定的大小。这也有利于去中心化,因为这样的区块链节点在什么样的硬件上都可以跑起来。

下图展示了目前主流 ZK 应用的方向。之后我们将介绍 ZK 的应用方向。

全部评论(0)