Transparent 且 Post-quantum zkSNARKs

1. 引言

前序博客有：

• SNARK原理示例
• SNARK性能及安全——Prover篇
• SNARK性能及安全——Verifier篇

上图摘自STARKs and STARK VM: Proofs of Computational Integrity。

上图选自：Dan Boneh 斯坦福大学 CS251 Fall 2023 Building a SNARK 课件。

SNARK方案由 Polynomial IOP（信息理论对象） ➕ 多项式承诺方案（密码学对象） 组成。

当前的Polynomial IOP主要分为三大类：

• 1）基于interactive proofs（IPs）的Polynomial IOP：如Hyrax、vSQL、Libra、Virgo等。【$P$
• 2）基于multi-prover interactive proofs（MIPs）的Polynomial IOP：如Spartan、Brakedown、Xiphos等。【$P$
• 3）基于constant-round的Polynomial IOP：如Marlin、PlonK、StarkWare的SNARKs等。【$P$

以上方案都是通过增加

P

P

P开销，来减少proof长度以及降低

V

V

V开销。
以上1）2）类，只要其结合的多项式承诺方案也不需要FFT，则

P

P

P无需做FFT运算。

当前的多项式承诺方案主要分为四大类：

• 1）基于pairing的多项式承诺方案（既不transparent，也不post-quantum）
  • 如KZG10、PST13、ZGKPP18等。
  • 独特属性有：具有constant sized evaluation proofs。
• 2）基于discrete logarithm的多项式承诺方案（transparent，但不post-quantum）
  • 如BCCGP16、Bulletproofs、Hyrax、Dory等。【其中Dory即需要discret-log hardness，还需要pairing。】
• 3）基于IOPs+hashing（transparent 且 post-quantum）
  • 如Ligero、FRI、Brakedown等。
• 4）基于Groups of unknown order的多项式承诺方案（若使用class groups具有transparent属性，但不是post-quantum的）
  • 如DARK、Dew等。
  • 由于使用class groups，$P$

现有的多项式承诺方案有：

• KZG多项式承诺：PlonK和Marlin采用KZG多项式承诺。其既不是transparent的，也不是post-quantum secure的。2020年。
• Bulletproofs多项式承诺：为transparent的，但不是post-quantum secure的。2017年。
• Hyrax多项式承诺：为transparent的，但不是post-quantum secure的。2017年。
• Dory多项式承诺：为transparent的，但不是post-quantum secure的。2020年。
• FRI多项式承诺：为post-quantum secure的。2017年。基于纠错码。
• Ligero多项式承诺：为post-quantum secure的。2017年。基于纠错码。
• Ligero++多项式承诺：为post-quantum secure的。2020年。基于纠错码。
• Brakedown多项式承诺：为post-quantum secure的。2021年。基于纠错码。
• Orion多项式承诺：为post-quantum secure的。2022年。基于纠错码。

上面的5种post-quantum secure多项式承诺方案均是基于纠错码，使用的唯一密码学原语为哈希。同时具有如下属性：

• 验证开销随着bits of security的位数增加而增加。（所谓验证开销，是由 哈希evaluation数量以及field operation数量 来衡量的。）

粗略来说，这些post-quantum多项式承诺方案的单次“迭代”仅可实现小数量的bits of security（如2-4）。因此，需重复该协议多次来“放大”安全等级，而随着每次重复，验证开销也会随之增加。因此，控制PQ-SNARKs的验证开销（对应为区块链应用中的gas开销），协议设计者通常有动力将security level设置为较低值。

除极少数例外情况（见2018年论文 Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains）外，Non-PQ-SNARK（透明和不透明）中不会出现具体安全和验证成本之间的紧张关系。Non-PQ-SNARK使用椭圆曲线群，其中离散对数被认为很难计算，其安全级别由所使用的群确定。椭圆曲线群的合适大小，以及每个群操作的成本，随着所需的安全级别而增长。然而，proof 中群元素的数量与群的选择无关。

而在PQ-SNARKs中，不仅hash evaluation的size会随着所需的安全等级增加而增加，proof中所需的evaluation数以及Verifier计算的 evaluation数也将随着所需安全等级增加而增加。

本文重点关注Transparent 且 Post-quantum zkSNARKs，在：

• libiop: a C++ library for IOP-based zkSNARKs（C++）【2021年5月后未更新】

中实现了几种仅依赖于lightweight symmetric cryptography（任意Cryptographic hash function）的 Transparent 且 Post-quantum zkSNARKs 方案：

• 1）Ligero协议：argument size为

  O

  (

  N

  )

  O(\sqrt{N})

  O(N

  ​)，见2017年论文Ligero: Lightweight Sublinear Arguments Without a Trusted Setup。

• 2）Aurora协议：argument size为

  O

  (

  log

  ⁡

  2

  N

  )

  O(\log ^2 N)

  O(log2N)，见2018年论文Aurora: Transparent Succinct Arguments for R1CS。

• 3）Fractal协议：argument size为

  O

  (

  log

  ⁡

  2

  N

  )

  O(\log ^2 N)

  O(log2N)，见2019年论文FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography。

以上这3种Transparent 且 Post-quantum zkSNARKs 方案，均支持基于smooth prime fields和binary extension fields的R1CS。所谓R1CS，为一种NP-complete relation that generalizes arithmetic circuit satisfiability。

不同于Ligero，其中Aurora和Fractal中有额外有趣的点在于：

• FRI low-degree test：详情见Fast Reed-Solomon Interactive Oracle Proofs of Proximity。

2. 由IOPs 到 zkSNARKs

Interactive Oracle Proofs（IOPs）：

• 为Probabilistically checkable proof 的multi-round generalization
• IOPs的性能，优于，PCPs
• libiop: a C++ library for IOP-based zkSNARKs库，通过Interactive Oracle Proofs（IOPs）（本文接下来按作者名，称为BCS transformation），实现了由IOPs构建的zkSNARKs。

BCS transformation：

• 使用cryptographic hash function（模型化为random oracle）
• 来将，任意public-coin IOP
• 编译为某SNARG

该SNARG具有如下属性：

• transparent：生成/验证proof strings所需的全局参数，仅为，该哈希函数
• post-quantum：在quantum random oracle模型内，其是安全的
• lightweight：除该哈希函数之外，无需其它密码学依赖

BCS transformation的描述见：

• Eli Ben-Sasson、Alessandro Chiesa 和 Nicholas Spooner 2016年论文 Interactive Oracle Proofs

BCS transformation的post-quantum安全性论证见：

• Alessandro Chiesa、Peter Manohar 和 Nicholas Spooner 2020年论文 Succinct Arguments in the Quantum Random Oracle Model

BCS transformation保持了proof of knowledge：

• 若底层的IOP是proof of knowledge，则所生成的SNARG为an argument of knowledge（即 a SNARK）

同理，BCS transformation保持了zero knowledge：

• 若底层IOP是（honest-verifier）zero knowledge，则所生成的SNARK是zero knowledge的（即 a zkSNARG）

同时，BCS transformation可扩展为：

• 向holographic IOPs，编译为，preprocessing SNARGs
  • 详情见：Alessandro Chiesa、Dev Ojha 和 Nicholas Spooner 2019年论文 FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography
  • 该特性，使得SNARGs可为，任意计算（而不仅仅是结构化计算），提供fast verification。

3. IOP协议

• http://github.com/scipr-lab/libiop/tree/master/libiop/iop：该目录下包含了编写IOP协议的基础设施。
• http://github.com/scipr-lab/libiop/tree/master/libiop/protocols：该目录下包含了几个使用该基础设施实现的协议，具体为：

其中：

• 1）Ligero-IOP：见2017年论文Ligero: Lightweight Sublinear Arguments Without a Trusted Setup。
  • 更准确来说，Ligero论文中仅描述了arithmetic circuits构建。而Aurora论文附录中解释了如何将，该arithmetic circuits构建，扩展为，支持R1CS。因此，实际在libiop: a C++ library for IOP-based zkSNARKs代码库中所实现的Ligero协议，借助了Aurora论文中的该扩展技术。
• 2）Aurora-IOP：见2018年论文Aurora: Transparent Succinct Arguments for R1CS。
• 3）Fractal-IOP：见2019年论文FRACTAL: Post-Quantum and Transparent Recursive Proofs from Holography。

其中比Ligero-IOP更高效，的，Aurora-IOP和Fractal-IOP，结合了2大元素：【详情见 2018年论文Aurora: Transparent Succinct Arguments for R1CS 】

• 1）RS-encoded IOP，即基于纠错码
  • http://github.com/scipr-lab/libiop/tree/master/libiop/protocols/encoded：该目录下包含了RS-encoded IOPs，覆盖了Ligero、Aurora和Fractal协议核心的RS-encoded IOPs。
• 2）对RS code的proximity test
  • http://github.com/scipr-lab/libiop/tree/master/libiop/protocols/ldt：该目录下包含了对RS code的proximity tests。其包含了：
    • direct test：用于Ligero
    • FRI protocol：用于Aurora和Fractal。

4. BCS transformation

• http://github.com/scipr-lab/libiop/tree/master/libiop/bcs：该目录下将BCS transformation作为独立组件。
• http://github.com/scipr-lab/libiop/tree/master/libiop/snark：该目录下，包含，将BCS transformation用于以上IOP协议，所获得的zkSNARKs。具体有：

其中：

• κ 用于表示上表中的asymptotics还依赖于该安全参数。
• make_zk：设置该标签，表示该BCS transformation应保留zero knowledge属性；而不设置，则表示该所转换的IOP是非zero knowledge的，因此也无需保留zero knowledge属性。

5. libiop库安装及测试

编译运行前，需安装：

• 依赖项Installation instructions

测试文件见：

• http://github.com/scipr-lab/libiop/blob/master/libiop/tests

若运行所有测试用例，则运行：

make check

若仅运行Aurora协议所有测试用例，则运行：

	$ ./test_aurora_snark
	$ ./test_aurora_protocol

6. libiop库性能分析

• http://github.com/scipr-lab/libiop/tree/master/libiop/profiling：该目录下包含生成，具有timing和argument size信息的，协议执行traces。
  • 这些traces均对应为单线程环境

如，可基于181 bit prime field（其中RS-extra-dimensions=3），采用如下命令，为Ligero、Aurora和Fractal创建traces：

  $ ./instrument_aurora_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --optimize_localization=1
  $ ./instrument_fractal_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --optimize_localization=1
  $ ./instrument_ligero_snark --make_zk 1 --is_multiplicative 1 --field_size=181 --RS_extra_dimensions=3

根据以上命令所生成的traces，绘制了如下性能分析图表：

参考资料

[1] libiop: a C++ library for IOP-based zkSNARKs