密码学证明方案寒武纪大爆发——扩容、透明性和隐私的变革潜力

1. 引言

前序博客有：

ZKP大爆炸

本文主要参考：

StarkWare 2023年6月博客 Cambrian Explosion of Cryptographic Proofs----The transformative potential for scalability, transparency, and privacy
2023年3月Eli Ben-Sasson在The 13th BIU Winter School on Cryptography - Blockchain Technologies的分享视频 A Cambrian Explosion of Cryptographic Proofs - Eli Ben-Sasson

要点：

密码学证明（Cryptographic Proofs）可验证计算，并提高区块链网络的交易完整性。
L2链采用密码学证明来扩容——为聚合的交易生成可验证的证明。
ZKPs（Zero-Knowledge Proofs）在不泄露额外信息的情况下可用于验证真相，但它们对隐私的使用各不相同。
密码学证明包含的技术层面有：算术化以及低阶强化（low-degreeness enforcement）。
随着区块链技术的成熟，某种类型的密码证明可能会占主导地位，促进扩容、透明性和隐私。

C.S. Lewis对完整性的定义为：

即使在无人监管的情况下，也做正确的事。

在区块链上下文中，密码学证明用于保证完整性——即使无人监管，仍确保某些计算处理正确。

本文重点关注：

何为密码学证明？
如何将密码学证明用于区块链？
不同密码学证明方案实现的差异性。（从算术化、低阶、密码学假设这三个维度来区分）

2. 何为密码学证明？

密码学证明为：

一组数学和密码学协议，用于断言计算的完整性。

一个密码学证明的很美示例见L. Babai等人1991年论文Checking Computations in Polylogarithmic Time，在该论文中提出了一种协议：

一台个人电脑可以用强大但不可靠的软件和未经测试的硬件监控一群超级计算机的运行。

这意味着，即使控制超级计算机的一方是恶意的，或者被激励误报计算结果，一台计算能力有限的机器可断言一组计算能力高得多的超级计算机所做计算的完整性。

3. 如何将密码学证明用于区块链？

过去十年来，见证了半实用和实用证明系统的寒武纪大爆发，以及大量确保隐私、安全和计算完整性的应用。而且，尽管web2和web3一样需要完整性，但由于区块链的开放和透明性质，以及它们更喜欢数学完整性而不是基于人的完整性，所有使用通用密码学证明系统的产品都可以在web3中的区块链上找到。为理解密码学证明如何帮助区块链扩容，需首先回顾区块链是如何工作的。

如今，当在Solana、以太坊或Cosmos等区块链上发送交易时，网络中的每个validator都会接收并执行交易。这很快就会变得效率低下。随着去中心化的发展，用于将每个交易包括在网络历史中的计算资源随着活跃validators的数量线性增加。

多个项目（如Aztec、Starknet）旨在使用密码学证明来解决扩容问题——称为L2 Validity Rollup，因为这些项目位于L1区块链（如以太坊）之上。这些L2 rollups背后的思想为：

依赖于密码学证明来确认链外计算的完整性，以及状态和交易集更新的有效性。

对长计算完整执行的验证能力代表了分布式网络吞吐量的基本范式转变。一个由许多机器组成的网络可以简单地验证它们，而不是天真地重新执行每个计算步骤。不需要超级计算机——这些计算机可以是普通的弱计算机。

这种大规模计算完整性的验证是由L1（如以太坊）的可靠节点执行的。在这种情况下，使用上面提到的1991年论文中的预言，L1网络中的Validators扮演着“单个可靠的PC”的角色，而L2 Prover是一台超级计算机，尽管在未经测试的硬件和可能不可靠的软件上执行，但它还是实现了完全的完整性和可靠性。

密码学证明寒武纪大爆发是关于这些系统在区块链中应用的日益增加，以及实现这些证明的不同密码学协议的激增。目前在web3中使用的许多项目有：
在这里插入图片描述
现有的知名密码学证明系统有：【主要用于区块链领域的以黄色框表示，其它以白色框表示】

4. 不同密码学证明方案实现的差异性

密码学证明方案众多，理解每种方案的优势劣势很重要。

4.1 ZKP：扩容 VS. 隐私

尽管很多项目都会提到“零知识”证明（或ZKP）一词，而且零知识证明在保护隐私的区块链中具有潜力，但大多数web3 L2 Validity Rollup 并不使用具有“零知识”密码学属性的证明，而是依赖于密码学证明的扩容属性。

ZKP是允许一方验证特定计算是否正确执行的证明，而不会透露该计算所消耗的输入（如，密码、交易的财务细节、医疗数据等）。因此，除了显著降低验证成本（继承自密码学证明的属性）外，还获得了隐私。

当项目声称其使用ZKP时，准确理解项目的含义是很重要的。虽然大多数基于区块链的项目都声称他们的技术“基于ZKP”，但事实上，其解决方案没有隐私考虑。

大多数项目更关注扩容而不是隐私：
在这里插入图片描述

4.2 何为算术化？

当看到一个系统需要证明的一组计算时，将这些计算问题转化为代数问题是有意义的。密码学证明中的算术化是指在有限域上使用算术运算来表示数学概念和运算的过程。

在高层，这意味着将任何语句表示为代数方程，即多项式。将计算问题转化为此类代数问题的过程在计算机科学的行话中被称为“归约（reduction）”，详细示例见下图：
在这里插入图片描述
算术化有助于提高扩容性的原因是，一旦用代数和多项式表达事物，就可提高发现破坏完整性的可能性。要了解多项式的魔力及其在证明中的有用性，最好学习STARK 101课程或阅读博客Arithmetization II。

考察不同的证明系统，一个区别因素是执行算术运算的方式。一些可以使用整数环（RSA环）上的模运算，另一些可以使用椭圆曲线和/或更复杂的方法（基于格的密码学、基于码的密码学和多变量多项式）。

4.3 低阶

所有的密码学证明系统都有某种形式的低阶强化，这是它们之间的一个关键区别因素。

低阶强化是指确保多项式（作为算术过程的一部分所生成的代数方程）的阶数小于某个阈值的过程。（只是提醒一下，多项式中的阶等于其中出现的项的最大幂。）

低阶强化对于完整性和安全性是必要的。错误地接受错误证明的概率与所选择的多项式的阶有关。此外，因为低阶多项式具有一些良好的数学特性，在这些系统使用低阶多项式，效率更高。

在这里插入图片描述
多项式承诺方案（polynomial commitment scheme，PCS）是一种允许对多项式进行有效和可验证计算的密码学协议。它使一方，即Committer，能够在不透露其全部细节的情况下对多项式进行承诺，而另一方，称为Verifier，可以稍后验证多项式承诺的属性。

在这里插入图片描述

不同的证明系统使用不同的PCS来创建和验证证明。STARKs和Risc0使用Fast Reed-Solomon Interactive Oracle Proof（“FRI”）承诺方案，而Groth16和PLONK使用KZG承诺方案。通常，这些承诺方案之间的区别因素在于：

创建证明的成本
验证证明的成本
证明的大小

在这里插入图片描述
见上图，可了解不同系统的优缺点。STARK证明系统使用FRI协议来强化低阶多项式。在STARK证明系统中，Prover与Verifier迭代交互，并对新的多项式进行承诺，使得每个新多项式的阶是前一个多项式的一半。PLONK系统使用基于椭圆曲线数学的多项式承诺（例如，KZG）。

此外，一些系统可能需要可信设置。可信设置中将生成特定的秘密参数。需要可信设置的证明系统中，挑战在于这些参数的pre-image必须保持私有。如果没有，那么整个证明系统就很脆弱，产生虚假证明就成为可能。
通常，组织特殊的可信设置“仪式”——多方私下创建随机元素组合以获得最终参数。只要其中的一方成功地销毁了其提交的随机元素，则可以认为该可信设置是安全的。