工具 区块链上的零常识证明技术及其典型算法

零常识证明（ZKP）是由Goldwasser等人[1]首先提出的，在明码学畛域有着关键的运行。它能够保障证明者在不提供任何有用的相关消息的状况下，使验证者置信一个语句是实在的。零常识证明准许证明者发生一个冗长的证明π，可以压服任何验证者置信证明者的公共输入x和秘密输入w上的公共函数f的结果是y = f（x,w）。w通常被称为见证输入或辅佐输入。零常识证明保障了假设证明者在计算结果时舞弊，验证者以压倒性的概率拒绝，而证明环节不会泄漏关于秘密w的额外消息，包括证明者的数据、证明者的身份和验证者的身份等。在区块链运行中，验证者可以经常使用ZKP来验证证明者在区块链环境中能否有足够的买卖量，而不会暴露任何私有买卖数据。

零常识证明作为一项关键的明码学技术，在许多畛域有着宽泛运行，例如隐衷包全、区块链默认合约的验证等。为了更深化地理解零常识证明的多样性和适用性，接上去本文将进一步讨论零常识证明的不同类型，包括Snark（Succinct Non-Interactive Arguments of Knowledge）、Stark（Scalable Transparent ARguments of Knowledge）以及Bulletproof等。每种类型都在特定情境下具备共同的优势和运行。

2. 零常识证明分类

在的明码学钻研和通常中，零常识证明（ZKP）技术已成为确保数据隐衷和完整性的关键工具。零常识证明准许一方（证明者）向另一方（验证者）证明某个陈说的正确性，而无需泄漏除该陈说正确性之外的任何消息。由于零常识证明底层的结构冗杂，本文更强调零常识证明在区块链上的运行，故本节将深化讨论区块链上三种代表性以及经常使用范围最广的零常识证明结构：ZK-Snark、ZK-Stark和Bulletproof。这三种结构方法表现了零常识证明技术在安保性、效率和适用性方面的不同技术特点及开展趋向。ZK-Snark是一种高度紧缩且非交互式的零常识证明，适用于区块链和隐衷包全运行。其关键优势是极高的验证效率和低通讯开支，但这种优势的代价是须要一个可信的设置阶段，这或者引入了中心化的危险和潜在的安保破绽。相比之下，ZK-Stark提供了一种无需可信设置的零常识证明方法，能够在不就义透明度和安保性的前提下提供可裁减性。它应用了明码学中的哈希函数和其余非对称技术，因此通常上在反抗量子计算攻打方面具备更强的韧性。但是，这种方法通常会带来更大的证明尺寸和计算开支。最后，Bulletproof是一种新型的非交互式零常识证明技术，不须要可信的设置环节，适用于范围证明。

2.1 ZK-Snark

ZK-Snark：一个非交互式论证系统R的ZK-Snark是指满足以下条件的（G, P, Ver, Sim）：

完备性：关于相关 R 的一个实在陈说，一个老实的证明者 P 领有一个能够压服验证者V有效的证据。

常识牢靠性：存在一个提取器，每当P生成一个有效的论证时，就能计算出一个证据。提取器可以齐全访问P的形态，包括任何随机的硬币，以确保对手不能经过舞弊或不实在的证明诈骗系统。

繁复性：一个非交互式论证，其中验证者在 λ + |u| 的多项式期间内运转，并且证明大小是 λ 的多项式，称为预处置 Snark。假设公共参考字符串是 λ 的多项式，则非交互式论证是一个齐全繁复的 Snark。

统计零常识：统计零常识是一种强零常识证明，在这种证明中，关于任何或者的输入，验证者从证明者那里取得的消息与他在不启动任何交互时可以模拟的消息在统计上是无法区分的。详细来说，这象征着存在一个模拟器，该模拟器在不与证明者交互的状况下，能够生成一个与实践交互记载在统计上无法区分的记载。

2.2 ZK-Stark

Eli Ben-Sasson于2018年提出了一种称为ZK-Stark的新型零常识证明[2]。ZK-Stark是ZK-Snark协定的改良版本。“Stark” 这个缩写代表 “Scalable Transparent Argument of Knowledge”－即可裁减透明常识论证。“可裁减” 指的是证明者的运转期间最多是计算大小的准线性级别、验证期间是计算大小的对数级别。也就是说，ZK-Stark是一种针对可用对数空间，经常使用可计算电路示意陈说的非交互零常识论证。“透明”指的是一切验证者消息只是地下抽样的随机硬币。ZK-Stark不须要可信设置程序来实例化证明系统，而是依赖于基于哈希抵触的对称加密算法，这种个性使其愈加高效，并且齐全解脱了ZK-Snark中可信阶段发生的参数，能够有效抗击量子计算机对算法的要挟。ZK-Stark经过AIR（algebraic intermediate representation，代数两边示意）启动解放的示意，Stark证明系统将在任何期间计算的形态都蕴含在从有限域取值的寄存器元组中，在每个周期降级形态。而代数口头轨迹（AET）则是按期间顺序陈列的一切形态元组的列表。ZK-Stark可以有一个十分快的证明期间和验证期间，但证明大小过大。因此，它在投票系统、在线系统和其余一些须要识别步骤才干访问的服务中有着黑暗的前景。

2.3 Bulletproof

Bulletproof的结构思绪如下：首先将电路中的乘法门解放和乘法门之间的线性解放应用 Schwartz-Zippel 引理[3]归约为一个多项式的某一特定项系数为零的疑问，而后将该疑问转化为内积论证（IPA）[4]的陈说示意方式，最后调用内积论证明现零常识证明。

Bulletproof提供了一种更有效的秘密买卖（CT）范围证明，关键运行于在加密货币畛域如Zcash中。防弹技术建设在成功通讯高效的零常识证明的技术之上，它们可以用来裁减多方协定，如多重签名或零常识紧急支付等，理想上，Bulletproof可以以为是基于IPA的Snark结构的一种。

表1 经典零常识证明协定对比

3. 零常识证明的运行

关于区块链的扩容疑问，已成为增强区块链网络可裁减性的关键打算。Rollups经过在二层协定上处置买卖并将结果传回主链，能够在提高性能和降落买卖费用的同时，坚持去中心化和安保性。在这一环节中，零常识证明尤为关键，由于它们准许在主链上对多笔买卖的实在性启动一次性性验证，而无需一一验证每笔买卖的细节。而在跨链技术方面，ZK Bridge展现了零常识证明技术在成功不同区块链之间资产与消息传递的后劲。与传统的跨链桥相比，ZK Bridge的优势在于它不须要引入额外的信任假定，并且可以成功高效率的买卖验证，从而降落了计算和存储老本。

3.1 扩容

随着以太坊生态的日渐兴盛，以太坊主链无法接受宏大的生态，造成整个以太坊网络拥挤。Rollup 是为了缓解 Layer1 扩容疑问所提出的可裁减性的打算，通常被称为链下处置打算。它裁减了以太坊并承袭了以太坊的安保保障。它的关键目标是在提高以太坊的性能并且降落 Gas费用的同时，保管散布式协定的去中心化和安保性特点。Rollup经过将Layer1的局部数据转移到二层协定上启动处置，而后将处置结果返送到Layer1上，从而增强区块链网络的可裁减性。Rollups 会在其上的网络中将买卖打包在一同并启动紧缩，而后将打包后的买卖发送到Layer1主网启动验证，经过一次性性验证多笔买卖，使得网络效率获取提高，同时参与了可被口头的买卖数量，成功了网络扩容。但在这个环节中，须要保障L1的节点没有舞弊上行虚伪买卖。

依据证明方法，Rollup 可以大抵分为两类：失望（optimistic）—Rollup 和ZK（零常识）-Rollup。Optimistic-Rollup的前提是一切买卖均有效，除非另有证明。假设买卖的有效性遭到质疑，验证者须要提供欺诈证明，而后将其发送到主网络启动验证。假设发现有效，买卖将被复原。这种方法依赖于网络介入者彼此坚持老实，从而建设信任和警觉的平衡。但是当用户提供欺诈证据时，主网上的处置打算不会立刻获取处置。这或者会造成从Optimistic-Rollup链中提取资产时发生提前，期待期间从几天到甚至几周不等。而零常识证明可以很好地成功上述需求，在L1打包多笔买卖后同时为这个环节生成零常识证明，验证者在Layer1上经过验证该证明后打包生成共识，成功扩容配置。ZK-Rollup则确保一切买卖都经过验证，同时坚持买卖详细消息齐全私密。这不只增强了安保性，而且提供了一切用户都十分赞叹的更高水平的隐衷。ZK-rollups的落地运行包括基于Snark的Scroll[551]，基于Starknet的Starknet[6]，混合Snark与Stark证明机制的Taiko[7]等名目。

3.2 跨链

跨链技术是一种使得加密资产在不同的区块链之间移动和贮存的技术。市场上存在泛滥独立运作的区块链，例如比特币和以太坊，但它们之间不足间接的互通机制。若无跨链技术，资产将无法在不同链间转移。

ZK Bridge作为经常使用零常识证明技术的跨链桥梁，其最大特点是不须要引入额外的信任假定就可以顺应多种不同类型的区块链。在这个处置打算当中，零常识证明是在区块链之外生成的，实践的验证则是在区块链上启动的。这样的做法大幅降落了区块链上的计算和存储老本，是当今市场上一种相沿且有后劲的跨链技术。目前，有几个名目正在开展 ZK Bridge 的生态系统，也就是开发基于零常识证明技术的跨链桥处置打算，但皆处于开发阶段。例如，Succinct Labs[8]、Electron Labs[9]、zkIBC[10]、Polyhedra Network[11]的 zkBridge[12] 等。Succinct Labs推出了Tendermint X，这是第一个开源的、高性能的Tendermint ZK轻客户端，它为Cosmos和Ethereum之间提供了一个无需信任的ZK桥接，标记着将Cosmos衔接到Ethereum的成功。Polyhedra Network的zkBridge应用其首创的deVirgo协定，一种高效的散布式零常识证明协定，成功了令人印象深入的性能优化和线性可裁减性。deVirgo协定的外围优势在于它简直完美的线性可裁减性—在一个散布式计算网络中，随着计算资源的线性参与，证明的生成期间将成倍缩小。deVirgo协定的这一个性特意适宜处置少量数据或高频买卖，使得zkBridge在处置跨链买卖时，不只坚持了零常识证明的隐衷和安保性优势，同时也确保了极高的吞吐量和低提前，这关于金融买卖和复杂的去中心化运行（dApps）来说至关关键。

4. 应战与未来展望

零常识证明技术依然面临许多应战，同时也衍生出泛滥钻研方向。

较弱假定的应战。ZKP的一个应战是，能否可以在一些较弱假定下有效实施。例如，Zerocash中经常使用了ZK-Snark，但它须要一个受信任的第三方来启动设置和系统初始化。ZKP可以在没有受信任第三方的状况下实施，但这会影响ZKP的效率。因此，钻研在没有受信任第三方的状况下有效实施ZKP是值得的。Spartan是一个有目共睹的成绩[13]，它提供了一种无需可信设置的ZK-Snark，特意适用于处置算术电路满足性疑问（R1CS）。它的特点在于，它能够在验证证明时发生低于线性的老本，而且不要求NP陈说的结构具备分歧性。此外，Spartan成功了期间最优化的证明者，这在先前的ZK-Snark文献中简直未被成功。Spartan运行了新技术，如计算承诺和一个加密编译器Spark，用于将现有的可提取多项式承诺打算转换为有效处置稠密多项式的打算，这关于成功期间最优化的证明者至关关键。Spartan作为Rust库成功，并与最新ZK-Snark启动了试验比拟，表现出多方面的优势，包括在无可信设置打算中具备较快的证明者速度，生成更短的证明，验证期间低，综合效率低劣。

零常识证明的配件减速。零常识证明技术虽然被宽泛以为是处置区块链关键疑问的关键打算，但常年受制于其自身的高计算密集性造成的计算效率疑问。正是基于这种背景，ZKP配件减速成为处置 ZKP 效率疑问的一个关键翻新方向。ZKP 配件减速触及在公用配件（如 GPU、 FPGA 和 ASIC）上成功 ZKP 算法的优化，使其能够更快地处置复杂计算，从而大幅提高 ZKP 的生成和验证速度。在 ZKP 的不同证明系统及其相关成功中，计算需求与资源开支各不相反。在泛滥证明系统中，有两种计算操作尤为耗时与低廉，区分是多标量乘法（Multiscalar Multiplication-MSM）和极速傅里叶变换（Fast Fourier Transform-FFT）。CUZK[14]中提出MSM 算法占据了证明生成总运转期间的70%以上。随着新的 ZKP 框架 STARK 的开展，也有更多的证明是基于 FTT 算法为主。

多标量乘法（MSM）优化。MSM是一种在椭圆曲线明码学中经常出现的操作，它触及对多个标量和椭圆曲线点的乘法与求和运算。虽然MSM 可以经过并行处置来减速，但即使在多外围的系统上，关于复杂的运行MSM 的运算依然须要消耗少量的资源与期间。MSM 算法须要处置少量的元素与重复口头相反的操作。

极速傅里叶变换（FFT）优化。以STARK为代表的零常识证明系统少量用到了极速傅里叶变换（FFT）。这个算法用于高效计算序列的团圆傅里叶变换（DFT）及其逆变换。FFT 的运转环节严重依赖于数据的频繁替换，数据替换环节中须要从大数据集中“随机”地传输元素，这在配件内存有限的状况下尤为艰巨。虽然配件操作自身十分快，但传输数据的期间却清楚降落了全体操作速度。除此之外，FFT 算法通常须要将输入数据从新陈列成特定顺序以口头变换，这或者须要少量的数据移动，关于大型FFT算法规模来说，这或者成为性能瓶颈。FFT 虽然是一种弱小且宽泛运行的算法，但在大型数据处置和散布式计算环境中，其性能和效率遭到数据替换、带宽限度的清楚影响。

基于 SNARK 的证明系统关键依赖于 MSM 算法，而 STARK 类证明则关键经常使用 FFT 算法。因此，目前的配件减速关键是面向这两种加密算法的需求启动优化。MSM 对配件的需求包括弱小的并行处置才干、较大的内存容量。相比之下，FFT 对配件的需求则包括高带宽、大内存容量、高效的数据访问形式。

参考文献

[1] Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof-systems[M]//Providing sound foundations for cryptography: On the work of shafi goldwasser and silvio micali. 2019: 203-225.

[2] Ben-Sasson E, Bentov I, Horesh Y, et al. Scalable zero knowledge with no trusted setup[C]//Advances in Cryptology–CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18–22, 2019, Proceedings, Part III 39. Springer International Publishing, 2019: 701-732

[3] Schwartz J T. Fast probabilistic algorithms for verification of polynomial identities[J]. Journal of the ACM (JACM), 1980, 27(4): 701-717.

[4] Bootle J, Cerulli A, Chaidos P, et al. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C]//Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer Berlin Heidelberg, 2016: 327-357.

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13] Setty S. Spartan: Efficient and general-purpose zkSNARKs without trusted setup[C]//Annual International Cryptology Conference. Cham: Springer International Publishing, 2020: 704-737.

[14] [63]Lu T, Wei C, Yu R, et al. Cuzk: Accelerating zero-knowledge proof with a faster parallel multi-scalar multiplication algorithm on gpus[J]. Cryptology ePrint Archive, 2022.