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$ 无需做FFT运算】
2）基于multi-prover interactive proofs（MIPs）的Polynomial IOP：如Spartan、Brakedown、Xiphos等。【 $P$ 无需做FFT运算】
3）基于constant-round的Polynomial IOP：如Marlin、PlonK、StarkWare的SNARKs等。【 $P$ 需要做FFT运算】

以上方案都是通过增加 $P$ 开销，来减少proof长度以及降低 $V$ 开销。
以上1）2）类，只要其结合的多项式承诺方案也不需要FFT，则 $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(\sqrt{N})$ ，见2017年论文Ligero: Lightweight Sublinear Arguments Without a Trusted Setup。
2）Aurora协议：argument size为 $O(\log ^2 N)$ ，见2018年论文Aurora: Transparent Succinct Arguments for R1CS。
3）Fractal协议：argument size为 $O(\log ^2 N)$ ，见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协议

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

	language	round complexity	oracle length (field elts)	query complexity	indexer time (field ops)	prover time (field ops)	verifier time (field ops)
Ligero-IOP	R1CS	2	O(N)	O(N^0.5)	N/A	O(N logN)	O(N)
Aurora-IOP	R1CS	O(log N)	O(N)	O(log N)	N/A	O(N logN)	O(N)
Fractal-IOP	R1CS	O(log N)	O(N)	O(log N)	O(N logN)	O(N logN)	O(log N)

其中：

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

4. BCS transformation

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

	language	indexer time	prover time	argument size	verifier time
Ligero-SNARK	R1CS	N/A	O_κ(N logN)	O_κ(N^0.5)	O_κ(N)
Aurora-SNARK	R1CS	N/A	O_κ(N logN)	O_κ(log² N)	O_κ(N)
Fractal-SNARK	R1CS	O_κ(N logN)	O_κ(N logN)	O_κ(log² N)	O_κ(log² N)

其中：

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

5. libiop库安装及测试

编译运行前，需安装：

依赖项Installation instructions

测试文件见：

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

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

make check

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

	$ ./test_aurora_snark
	$ ./test_aurora_protocol

6. libiop库性能分析

https://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，绘制了如下性能分析图表：
在这里插入图片描述