View profile

Issues 2 - ZK 流派

Glaze
Glaze
0️⃣ 零知识证明流派简介
一句话介绍 ZK(Zero Knowledge Proof):证明者(Prover)说服验证者(Verifier)相信某些声明是真的,但除了声明是真的之外,验证者没有获得其他信息。
ZK 是为匿名而设计的。试想我们可以证明我们的身份证号码是有效的,但是验证者并不能获得我们的身份证号码。这在信息过渡索取的今天,具有重大意义。
让我们来看一个更加生动的例子。小明和小红在玩数独。小红想向小明证明她找到了数独的答案,但同时又不透露这个答案,因为小明还没解出这个数独。你将如何设计这个证明?
我们把数独写到卡片上。每张卡片上有一个数字。将他们按照答案排列好,正面朝下。小明可以随机选择一列,一行或者一块。小红将拿出小明所选择的那些卡片,随机打乱后,将这些卡牌翻过来,正面朝上。如果这些卡牌是不重复的 1-9,那么小明知道小红解出了数独的某一部分,但也或许是运气。重复以上步骤,如果每次都是正确的。那么就几乎不可能是小红运气好,而是小红真的知道答案。虽然小明得知小红解出了数独,但是小明仍旧不知道数独的答案。
如果你还是有点疑惑,欢迎观看这个视频。UCLA 的计算机教授将以 5 种难度形式,解释什么是 ZK。
🗡️ 常见零知识证明流派
在介绍零知识证明流派之前,大家要注意我们常说的 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 不能升级。如果我们升级了程序,可信初始化要重新运行。
为了解决这一系列的问题,科学家们找到了两个方向
  • Transparent Setup:可信初始化生成公共参考字符串(Common Reference String)。CRS 是公开的,不需要保密。Fractal,Halo,ZK-STARK,SuperSonic 都是采取了这一条路线。这一条路线的问题是生成的证明占用太多的存储,来到了 kB 的量级。对于区块链来说,存储是非常昂贵的。
  • Universal Setup:可信初始化生成了结构化参考字符串(Structure Reference String),但它需要保密。SRS 让可信初始化可以用于不同的程序,这让通用计算的证明可能实现。Marlink,SuperSonic-RSA 和 Plonk 都采用了这条路线。
业界广泛采用以下几种算法:
  • 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 和算法对比:
总结以下,当我们看到一个新的 ZK 算法时候,以下指标是我们需要在意的:
  • 证明时间
  • 验证时间
  • 一笔交易和十笔交易打包后的证明大小
  • 可信初始化
  • 参考字符串长度
  • CRS 支持
  • SRS 支持
  • 递归证明支持
  • 能否抵抗量子计算机
  • 安全性基于任何密码学假设
ZK 在最近几年走出实验室,逐渐步入应用。ZK 两个主要应用方向是 Rollup 和隐私ZK 对于隐私产品的变革是显而易见的,得益于 ZK 可以让验证者不获得任何额外信息。Rollup 依赖于 ZK 的两大特性:简洁(Succinct)和递归(Recursion)。简明的特性有助于验证者节省大量的计算资源。验证者不需要重新运行整个程序。递归特性有助于节省存储空间。通过递归,区块链可以保持一个固定的大小。这也有利于去中心化,因为这样的区块链节点在什么样的硬件上都可以跑起来。
下图展示了目前主流 ZK 应用的方向。之后我们将介绍 ZK 的应用方向。
Did you enjoy this issue? Yes No
Glaze
Glaze @glazecl

Issues:💡 寻找具有创新的项目,No Alpha,100x or 止损

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.