STARKs with small finite field：小域带来的迷人性能

本文主要是介绍STARKs with small finite field：小域带来的迷人性能，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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*2^{30}+1$ 。
RISC Zero zkVM的STARK证明系统所使用的有限域为BabyBear域 $p=2^{31}-2^{27}+1$ （也即 $p=15*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/cheetah（Rust）
同时该论文作者声称：

“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.

这篇关于STARKs with small finite field：小域带来的迷人性能的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！