Goldilocks域 p = 2 64 − 2 32 + 1 p= 2^{64} - 2^{32} + 1 p=264−232+1,目前用于Polygon生态的多个项目中:
- Polygon Miden VM:在https://github.com/maticnetwork/miden 中使用了winterfell项目的winter-math库:https://github.com/novifinancial/winterfell/blob/main/math/src/field/f64/mod.rs(Rust语言)
- Polygon Zero Plonky2:https://github.com/mir-protocol/plonky2/blob/main/field/src/goldilocks_field.rs(Rust语言)
- Polygon Hermez 2.0:https://github.com/0xPolygonHermez/goldilocks(C++语言)
以Goldilocks域 p = 2 64 − 2 32 + 1 p= 2^{64} - 2^{32} + 1 p=264−232+1 为base prime field的椭圆曲线有:
- 1)Cheetah curve:
- 2022年论文 Security Analysis of Elliptic Curves over Sextic Extension of Small Prime Fields
- https://github.com/ToposWare/cheetah (Cheetah curve实现,Rust语言)
- https://github.com/ToposWare/cheetah_evidence (Cheetah curve安全性论证,Python和SageMath)
- 2)ecGFp5 curve:
- 2022年论文 EcGFp5: a Specialized Elliptic Curve
- https://github.com/pornin/ecgfp5(ecGFp5 curve实现,Rust和Python)
p
=
2
64
−
2
32
+
1
p= 2^{64} - 2^{32} + 1
p=264−232+1,
F
p
∗
\mathbb{F}_p^*
Fp∗的order为
p
−
1
p-1
p−1,即:
2
64
−
2
32
=
2
32
⋅
3
⋅
5
⋅
17
⋅
257
⋅
65537
2^{64}-2^{32}=2^{32}\cdot 3\cdot 5\cdot 17\cdot 257\cdot 65537
264−232=232⋅3⋅5⋅17⋅257⋅65537 即意味着该域具有
2
32
2^{32}
232-th root of unity。 相应的generator为:
g
=
7
g=7
g=7
2
32
2^{32}
232-th root of unity 为
g
(
p
−
1
)
/
2
32
=
0
x
185629
d
c
d
a
58878
c
=
1753635133440165772
g^{(p-1)/2^{32}}=0x185629dcda58878c=1753635133440165772
g(p−1)/232=0x185629dcda58878c=1753635133440165772。 相应的sage脚本为:
根据Ariel Gabizon twitter有:
- 1)采用A100 GPU,Goldilocks域乘法运算比BN254域快15.5倍:
- BN254: ~34*10^9 muls/s
- Goldilocks: ~527*10^9 muls/s
- 2)大多数CPU上,单个Goldilocks乘法运算需约2~3 cycles,256-bit乘法运算约需要80~100 cycles。
- 3)根据polygon zkEVM repo,在AMD EPYC 7773Xc处理器上,Goldilocks域乘法运算比BN254域快约9倍。在该及其上采用的是Karatsuba算法来对n-digital long integers进行乘法运算。
- 4)根据UIvetanna——ZKP加速(获得Bain Capital Crypto、Paradigm以及Jump Crytpo联合的1500万美金种子轮投资)的FPGA开发,Goldilocks域乘法运算的延迟要比BN254快约8倍,资源利用率要比BN254好10~15倍。
STARKs/SNARKs处理常规整数运算的难点在于:
- 所有的值都是以有限域元素表示。
- 将有限域运算 映射为 32-bit或64-bit整数运算 是昂贵的。(注意:EVM使用256-bit整数)
Miden VM原生支持所有32-bit unsigned integers(u32)运算,从而使得相应的运算效率很高:
- 每个u32运算仅需要一个VM cycle。
Goldilocks域 p = 2 64 − 2 32 + 1 p= 2^{64} - 2^{32} + 1 p=264−232+1,具有一些很好的特性:【详细见:u32 operations in Miden VM 】
- 1)值适于64-bit整数,从而使得基于该域的运算在现代CPU上运行很快。
- 2)2个32-bit整数乘法不存在域模溢出问题。
- 3)检查4个16-bit values是否构成了一个有效filed element 的效率可以很高。
Miden VM中的大多数u32运算(包括bit shifts、bit rotations、value comparison)仅需要少量的16-bit range checks。对于一些复杂的运算(如bitwise AND/OR/XOR),需要使用辅助lookup tables,但是这些复杂运算也是efficient的。
参考资料[1] twitter u32 operations in Miden VM [2] u32 operations in Miden VM [3] cronokirby 2022年9月1日博客 The Goldilocks Field [4] twitter Goldilocks Field