STARKs with small finite field：小域带来的迷人性能-CSDN博客

1. 引言

前序博客有

• 2023年 ZK Hack以及ZK Summit 亮点记
• 为何需关注各ZKP方案的benchmarks

很久以前有大量研究和开发致力于改进ZKP性能。研究人员通过采用多种不同的技术包括但不限于

• 不同的IOPs
• 不同的多项式承诺方案
• 不同的哈希函数
• 不同的硬件加速等

来不断优化

• Prover time
• Verifier time
• 以及Proof size。

其中一项广受关注的技术就是

• 使用更小的域smaller field。
• 前提是使用更小的域有助于在消费级硬件上更高效地运行如GPU采用32位数据类型CPU采用32位或64位数据类型。这样可降低类似zkRollups这类应用的延迟。

当前STARKs项目中所使用的small finite field小有限域有

• StarkNet中的STARK证明系统所使用的有限域为$p=3\ast 2^{30}+1$。
• RISC Zero zkVM的STARK证明系统所使用的有限域为BabyBear域 $p=2^{31}-2^{27}+1$也即$p=15\ast 2^{27}+1$。
• Polygon Zero Plonky2项目、Polygon zkEVM以及Polygon Miden等项目使用的有限域为Goldilocks域 $p=2^{64}-2^{32}+1$。
• Polygon Zero Plonky3项目使用有限域为Mersenne31域 $p=2^{31}-1$。

2. 实际生产用的小域类型

关于在ZKP系统中使用小域的许多神秘传说仍然相当不透明。虽然有一些博客文章和一些视频可用但真正宝藏的主要来源往往是代码库中的内置评论详细说明了这些字段及其用途。例如在Risc0代码库中从第41行开始有一条注释解释了使用BabyBear的两个好处

• 1其值小于$2^{31}$因此可用一个32位word来表示。适用于CPU
• 2对于$p-1$进行因式分解其具有尽可能大的power of 2。【即适用于FFT运算很多ZKP系统中需要FFT运算。本文不展开这块内容。】

出发点很合乎逻辑

• 为使证明系统发挥最佳功能基础数据类型必须与硬件高度兼容。

Polygon的“Plonky2”提供了精心制作的文档对这个主题进行了更深入的研究。“Plonky2”使用FRI来代替KZG是因为KZG是基于“椭圆曲线”的而基于椭圆曲线的东西需要更大的有限域比如$2^{256}$大。Goldilocks域是$p{2}^{64}-2^{32}+1$这足够小——意味着使用64位字段就可表达Golidilocks域内任一元素。这也适用于很多CPU。这在许多CPU上都能很好地工作。在Polygon Labs的2022年11月博客Plonky2: A Deep Dive中指出其使用FRI 64-bit Golidilocks域 而不是 KZG 256-bit field性能提升了40倍。

正如过往在Polygon的新系统“Plonky3”的代码库中偶然发现一个更小的字段被使用也就不足为奇了Mersenne31。此字段足够小可以处理32位数据类型。这意味着在通常使用32位的GPU/CPU上有更好的性能。详情可参看

• Daniel Lubarov在2023年Future Computing Research Workshop (March 2023, Denver)分享的视频, Brainstorming Plonky3

3. 不应无脑使用小域

不依赖于椭圆曲线的系统可准备使用这些小域。但当证明系统必须与密码学原语如ECDSA签名进行交互时即意味着必须使用椭圆曲线时使用小域就会带来一系列的并发症

• 如Brendan Farmer所指出这将增加Prover time。

“If one works over a field of size less than 2^256, one has to allocate multiple field elements to represent a single uint256 data type…This roughly doubles the prover costs required to support these data types.”
Doesn’t this assume that prover costs are equal across proving systems using different fields? Using a smaller field might indeed increase the number of rows needed for bigint ops. However, in practice, the savings received offered by a proving system w/ more hardware-friendly fields should greatly outweigh the additional cost in rows even for bigint ops.
“Working over a small field actually increases proving time when proving knowledge of ECDSA signatures…For example, this may be why Starkware works over a 251-bit field that matches certain ECDSA signatures, not a smaller field.”
I think this is a common misconception: that using smaller fields forces devs to simulate EC ops non-natively, but you can always use a curve defined over an extension field very efficiently on smaller fields, as long as you have flexibility in your choice of curve.

其中的

• 论点之一就是需要使用更多的域元素来表示椭圆曲线数据类型从而给Prover制造瓶颈。
• 另一论点 是为non-native 256-bit运算采用对CPU硬件友好的域。

小域可用于不适用椭圆曲线的系统如FRI那是否适用于有椭圆曲线的系统如KZG呢
答案是可能的

• 如使用的某小域其具有的‘extension field’可支持EC运算等non-native运算。
  extension field自身就是限制操作$F.E<F$的域。
• 也可使用stack fields又名‘Towers of fields’类似F1<F2<…<Fn。

这些扩域的安全性仍在审查中一些研究表明在某些假设下它们的安全性较差详情见2016年论文Extended Tower Number Field Sieve with Application to Finite Fields of Arbitrary Composite Extension Degree。也不清楚在这些域上使用哪些曲线从而仍然允许递归许多ZKP系统中使用的方法。

4. 若某些小域的扩域是安全的然后呢

目前有少量具有扩域的曲线目前暂无明显漏洞。如

• 2022年论文EcGFp5: a Specialized Elliptic Curve 中提出的ecGFp5曲线并声称

  “We describe here the choice of a secure curve, amenable to safe cryptographic operations such as digital signatures, that maps to such models, while still providing reasonable performance on general purpose computers.”

• 2022年论文Security Analysis of Elliptic Curves over Sextic Extension of Small Prime Fields 中提出的Cheetah曲线其开源代码实现见

  • https://github.com/ToposWare/cheetahRust

  同时该论文作者声称

  “Elliptic curves based on extension fields may suffer from specific attacks that do not apply to common elliptic curves constructed over large prime fields and may outperform regular Pollard-Rho attacks, and hence require more scrutiny when evaluating their estimated security level.”

对于基于FRI的系统来说定制这些曲线似乎是一项合理的努力但需要一点勇气。

能否简单地使用这些较小的域然后在必要时使用它们的扩域呢如用于EC运算大多数运算可在小域中完成而需要较大域运算时可在扩域中完成。这似乎就是“Plonky3”团队所追求的因为其添加了128位扩域feature。

或反过来在EC系统中使用小域正如之前所述难点在于找到同时支持扩域和递归的椭圆曲线对。不过只要相信终有可能能找到相应的椭圆曲线对。

在其他使用域运算的系统如sum-check协议中这似乎是可能的。在这种情况下大多数运算将在小域中完成的而某些运算则从较大的扩域中提取。这项研究是非常新的其理论含义尚未公开讨论。

对于扩域所带来的并发症这取决于所使用的ZKP方案的其他方面。如

• 使用扩域来做特定随机运算以确保在IOP中仅使用base域运算 所带来的挑战。若该挑战得到解决则很多情况就很好处理了这是最理想的方案。

参考资料

[1] Starknet book Part 1: Trace and Low-Degree Extension
[2] RISC Zero zkVM白皮书2023年8月版 RISC Zero zkVM: Scalable, Transparent Arguments of RISC-V Integrity
[3] ICME 2023年9月博客 Once Upon a Finite Field: journeying through Towers with Goldilocks and BabyBear, in the enchanted world of small fields for ZKP performance.