ZKP的起源和发展历程:自1980年代至今

fffmCQ.jpg

作者:Preethi Kasireddy,DappCamp创始人;翻译:金色财经cryptonaitive

ZKP(零知识证明)在加密货币大爆发后受到欢迎,但它们的悠久历史可以追溯到 1980 年代。本文探讨 ZKP 这些年来的起源和发展。

ZKP的基本前提是,一方(prover)可以向另一方(verifier)证明他们了解特定信息,而无需实际透露该信息是什么。通过这样做,Prover可以证明他们对特定事实或数据的了解,而无需透露任何其他信息。

现在,让我们开始探索ZKP的历史和发展。

1980年代:ZKP起源

ZKP 在加密货币爆发后获得了关注,因为它们允许在两方之间进行无需信任和匿名的交换,但这个概念本身并不新鲜。ZKP 的历史其实可以追溯到 20 世纪 80 年代后期,当时 Shafi Goldwasser、Silvio Micali 和 Charles Rackoff 在一篇题为“The Knowledge Complexity of Interactive Proof-Systems”(交互式证明系统的知识复杂性)的论文中引入这个概念。

作者描述的初始概念涉及称为“交互式协议”的东西,其中prover和verifier将来回通信(反复交互)以使verifier相信prover知道正确的信息。这种方法虽然有其自身突破,但被证明是耗时且资源密集型的,尤其是在涉及大量数据时。为了使ZKP具有可扩展性,它们需要是非交互式的。

s9MA8RtoEXfzxn6ICILYPa3MAD8KCVrMOqehiTPc.png

Peggy(证明者)和 Victor(验证者)

1986 年,Fiat 和 Shamir 发明了 Fiat-Shamir heuristic(Fiat-Shamir 启发式,一种采用交互式知识证明并据此创建数字签名的技术),成功地将交互式零知识证明转变为非交互式零知识证明。现在,这使得 ZKP 成为非交互式的,并为 ZKP 的广泛、可扩展使用奠定了基础。

FovzAhH68lMILxcih3DeM0c6oFkDIFub94SiZKrd.png

交互式与非交互式ZKP

2011-2015:zkSNARKs

ZKP 的下一次重大推动发生在 2011 年,Nir Bitansky、Ran Canetti和Alessandro Chiesa在密码学理论国际研讨会上发表了一篇名为“From Extractable Collision Resistance to SNARKs and Back Again" (从可提取的抗碰撞性到 SNARKs,然后再反向操作 )的论文。

6dfioud49xs00wSolNizdEZD1p7q1oD82BS4EfTz.png

zkSNARK如何工作?

这篇论文表明,我们可以使用一种称为可提取抗碰撞 (ECR) 哈希函数的东西来创建 SNARKS(简洁的非交互式知识论证)。SNARKS 基本上是“简洁”的 ZKP,这意味着它们体积小,可以在几秒钟内得到验证。

这篇论文表明,我们可以使用一种称为可提取抗碰撞 (ECR) 哈希函数的东西来创建 SNARKS(简洁的非交互式知识论证)。SNARKS 基本上是“简洁”的 ZKP,这意味着它们体积小,可以在几秒钟内得到验证。

67OEGdawnLdQfi1ktEizi2jo1uWJAoJFS5oMwd8g.png

ZKP、NIZKP 和 zkSNARK 的比较

从这里开始,ZKP 的进程加快了,并促成了 2013 年Pinocchio的诞生。

Pinocchio是零知识简洁非交互式知识论证 (zk-SNARK) 证明系统的第一个概念验证实现之一,被认为是该领域的突破。它在几年前一直被使用,但随后被更新、更高效版本的zk-SNARKs所取代。

当时 zkSNARKS 的两个主要缺点是:

● 可信设置的要求

zkSNARKs 需要prover和verifier之间的“可信设置”。此设置阶段用于创建一组初始参数,然后用于生成和验证 zk 证明。

生成这些参数需要一些秘密信息。一群人通常生成这些秘密,然后使用这些秘密来生成参数。一旦生成参数,秘密就被丢弃。然而,由于秘密输入需要由一组人生成,因此需要我们“信任”这些人。

在区块链中,我们希望最小化信任,这就是为什么“可信设置”通常不受青睐的原因。

zk-SNARK 证明依赖于prover和verifier之间的初始“可信设置”,这意味着需要一组公共参数来构建零知识证明,从而构建隐私交易。这些参数几乎就像游戏规则一样,它们被编码到协议中,是证明交易有效的必要因素之一。这会产生潜在的中心化问题,因为参数通常由非常小的团队制定。

l4OqzI0h9p8bp9CPtIxElRcOzTraKWO7X4FhKOPt.png

多参与者可信设置的工作流程 来源

● 非后量子安全

zkSNARKS 不是后量子安全的,因为它们依赖于公钥加密。公钥密码学依赖于解决特定数组的离散对数问题的难度。但随着量子计算机的诞生,公钥密码学面临风险,因为计算机可以将大数分解为素数,这意味着解决离散对数问题不再困难。

ZK行业正在努力构建解决这两个问题的协议。

2016-2018:让SNARKs变得实用

接下来是Groth。Groth 于 2016 年推出,是使 zkSnarks 高效且极其实用的首批协议之一。这是一个巨大的突破,并立即得到采用。事实上,由于它的性能和简单性,它今天仍在许多协议中使用,并且围绕它构建了许多工具。

ZKP的下一个重要里程碑是 2017 年 Bulletproofs 的推出。我记得 Bulletproofs 在 2017 年大肆宣传。Bulletproofs 是简短的非交互式零知识证明,可以证明某个加密值在给定的“范围内”不透露任何有关数据的信息(例如,我可以在不透露金额的情况下向你证明交易价值在一定范围内)。这些“范围证明”可以聚合成一个简短的证明。Bulletproof协议变得如此流行的原因是因为它们使比特币的机密交易不仅成为可能,而且变得高效。Bulletproof技术最大的区别在于它不需要可信设置。这在区块链行业非常重要,因为我们专注于构建无需信任的网络,正如你可以想象的那样,行业很快就采用了Bulletproof技术。

K6VXDXTE2F9Idkf3G67rmgu5RmO7n7kQYyJ25vRV.png

SNARKs、STARKs 和 Bulletproofs 的Runtime比较

2018:STARK

2018 年,STARKS(Zero-Knowledge Scalable Transparent ARguments of Knowledge——零知识可扩展透明知识论证——的缩写)通过缓解 zkSNARKS 的两个缺点在业界引起了轰动:

● STARKS 是“后量子安全”的,这意味着它们依赖于哈希函数而不是椭圆曲线作为证明机制。

● STARKS 不需要可信设置。相反,zk-STARKS 使用可公开验证的随机源作为初始参数。

zkSTARKS 的最大缺点是它们的证明很大。这使得它不适合区块链,因为链上存储需要花钱。然而,STARKS 超过 SNARKS 脱颖而出,并让行业摆脱可信设置。

P23fHMbIHa7qjZcBddWdKf8RUgXQXJjSZ39lPNfd.png

zkSNARKs 和 zkSTARKs 在各种参数上的比较

2019:SNARKS年

2019 年对 zkSNARKS 来说是重要的一年,该领域有 3 项重大创新:

● SONIC

Sonic 做出的最大贡献是支持“通用”且可不断升级的参考字符串。这意味着你不需要进行可信设置来为每个程序生成初始参数。相反,你只需执行一次可信设置,然后对所有程序使用相同的参数。虽然这并不能完全减轻可信设置的缺点,但它确实使它变得更好了。

Sonic 还具有恒定的证明大小(这很好,因为证明大小不会随着程序的复杂性而增加)并引入了批量验证,从而减少了验证时间。但是,当你不进行批处理时,验证时间非常长。

● MARLIN

Marlin 是 Sonic 的显著改进版本,证明时间减少了 10 倍。它还提供了更快的验证而无需批处理,并将验证时间缩短了 3 倍。

● PLONK

PLONK 是“Permutations over Lagrange-bases for Oecumenical Non Interactive Arguments of Knowledge ”(普遍用途的非交互式知识论证的拉格朗日基排列)的缩写,是 SONIC 的另一个改进版本,它的一个特性是,它的证明时间减少了 5 倍。这里的重大创新是 PLONK 允许自定义门(gate)而不是通常的加法/乘法,这意味着你可以为更复杂的程序构建 zk 证明。

PlonK 和 Marlin 都用通用设置替换了 Groth16 中电路特定的可信设置。随着 PLONK 的推出,加密社区也意识到他们甚至可以构建“zkEVM”,这将使我们能够在以太坊上获取任何智能合约代码并将其转换为零知识证明。Vitalik 曾经写过一篇精彩文章,解释了它背后的数学原理。

这标志着ZKP乱战的结束,但也仅仅只是个开始!

pcnfXz3vOnaC2flLUZeFML3aZPh25cIeAAMaGdvy.png

各协议证明大小和安全假设图,来源

2020年至今

HALO2

2020 年,Zcash 团队推出了 HALO 2(HALO 的继后继者),它结合了 PLONK 和 Bulletproofs 的优点,然后允许在没有可信设置的情况下进行快速验证。

FgnoXJu2Beri9vTxrzruBaBWx6SYOuU8RfDbitfe.png

HALO vs HALO 2,来源

快进到 2022 年,我们开始再次看到新协议开发的加速。

HYPERPLONK 

HYPERPLONK 于 2022 年推出,是一种 zkp系统,证明是完全线性时间的并支持高度和查找自定义门。它试图提高 PLONK 的灵活性,提高其速度并提供更多好处。

虽然 PLONK 本身非常强大,但它有一定的局限性,尤其是在证明大型声明或尝试使用高度并行的硬件时。在证明诸如rollup和 zkEVM 等大型复杂命令时,这些限制尤为重要。HyperPlonk 旨在解决这个问题。

PLONKY2

最近,Polygon 于 2022 年 1 月发布的 Plonky2 是 ZKP 世界中最新的。它是一种递归 SNARK,比现有其他方案快 100 倍。它结合了 PLONK 和 FRI,以获得最好的 STARK(即快速证明和无可信设置)和最好的 SNARK(即支持递归和以太坊上的低验证成本)。

这将我们带到了今天。这就是 ZKP生态今天的样子:

sDZsf6H6neTvr91PHWQNdC2EWsYNDLoyp3wDCDLZ.png

ZKP生态

虽然没有哪个“协议”被认为是最好的,但了解所有这些协议、它们的优点和局限性有助于我们为特定用例和设置选择最好的一个。我的团队收集了我今天介绍的所有协议的信息,并在此处为你总结:

vICxlPgSJxbfFTzGL2fns88KBcWRm3sgFO3UUSQp.png

各ZKP特性全汇总

ZKP 有着悠久而丰富的历史,每个协议都在突破极限,提高速度并扩展这项技术的限制。从需要prover和verifier来回交换信息的第一次迭代,我们已经走了很长一段路。

在我看来,我们才刚刚开始。你认为 ZKP 领域的下一个重大创新是什么?

声明:该文观点仅代表作者本人,与炒币网无关。炒币网系信息发布平台,仅提供信息存储空间服务。对所包含内容的准确性、可靠性或者完整性不提供任何明示或暗示的保证,并不对文章观点负责。 提示:投资有风险,入市须谨慎。本资讯仅供参阅,不作为投资理财建议。

发表评论

登录后才能评论