🎉【Gate 3000万纪念】晒出我的Gate时刻,解锁限量好礼!
Gate用户突破3000万!这不仅是数字,更是我们共同的故事。
还记得第一次开通账号的激动,抢购成功的喜悦,或陪伴你的Gate周边吗?
📸 参与 #我的Gate时刻# ,在Gate广场晒出你的故事,一起见证下一个3000万!
✅ 参与方式:
1️⃣ 带话题 #我的Gate时刻# ,发布包含Gate元素的照片或视频
2️⃣ 搭配你的Gate故事、祝福或感言更佳
3️⃣ 分享至Twitter(X)可参与浏览量前10额外奖励
推特回链请填表单:https://www.gate.com/questionnaire/6872
🎁 独家奖励:
🏆 创意大奖(3名):Gate × F1红牛联名赛车模型一辆
👕 共创纪念奖(10名): 国际米兰同款球员卫衣
🥇 参与奖(50名):Gate 品牌抱枕
📣 分享奖(10名):Twitter前10浏览量,送Gate × 国米小夜灯!
*海外用户红牛联名赛车折合为 $200 合约体验券,国米同款球衣折合为 $50 合约体验券,国米小夜灯折合为 $30 合约体验券,品牌抱枕折合为 $20 合约体验券发放
🧠 创意提示:不限元素内容风格,晒图带有如Gate logo、Gate色彩、周边产品、GT图案、活动纪念品、活动现场图等均可参与!
活动截止于7月25日 24:00 UTC+8
3
Circle STARKs: 小字段上的高效零知识证明
探索Circle STARKs
近年来,STARKs协议设计趋向使用较小的字段。最早期的STARKs实现使用256位字段,对大数进行模运算,与基于椭圆曲线的签名兼容。但这种设计效率较低,处理大数字浪费算力。为解决这个问题,STARKs开始使用更小的字段:Goldilocks、Mersenne31和BabyBear。
这种转变提升了证明速度。例如Starkware能在M3笔记本上每秒证明620,000个Poseidon2哈希值。只要信任Poseidon2作为哈希函数,就可以解决高效ZK-EVM开发的难题。那么这些技术如何工作?小字段上如何建立证明?本文将探讨这些细节,特别关注Circle STARKs方案。
使用小字段的常见问题
在创建基于哈希的证明时,一个重要技巧是通过证明多项式在随机点的评估来间接验证多项式性质。这大大简化了证明过程。
例如,假设要证明多项式A满足A^3(x) + x - A(ωx) = x^N。协议可要求选择随机坐标r并证明A(r) + r - A(ωr) = r^N。然后反推A(r) = c,证明Q = (A - c)/(X - r)是多项式。
为防止攻击,需要在攻击者提供A后再选择r。在256位字段中很简单:选择随机256位数字即可。但在小字段中,可选的r值只有约20亿种,攻击者虽然工作量很大但仍可能尝试所有可能。
有两个解决方案:
多次检查简单有效,但存在效率问题。扩展字段类似复数,但基于有限域。引入新值α满足某关系,如α^2=某值。这创建了新的数学结构,可在有限域上进行更复杂运算。扩展域仅在需要随机线性组合时使用,大部分运算仍在基础字段进行。
常规FRI
构建SNARK或STARK的第一步是将计算问题转化为多项式方程P(X,Y,Z)=0。解决方案需证明提出的值是合理的多项式,且度数有限。这通过逐步应用随机线性组合实现:
B隔离A的偶数系数,C隔离奇数系数。给定B和C可恢复A:A(x) = B(x^2) + xC(x^2)。如果A度数<2^20,B和C的度数分别为A的度数和A度数-1。D作为随机组合,度数应为A的度数。
FRI通过将证明多项式度数为d简化为证明度数为d/2来简化验证。这个过程可重复多次,每次将问题简化一半。如果某阶段输出不符合预期度数,那一轮检查将失败。
FRI每步将多项式次数和点集规模减半。前者是FRI工作的关键,后者使算法运行极快:总计算成本是O(N)而非O(N*log(N))。
为实现域逐步减少,使用二对一映射。这种映射允许将数据集大小减半,且是可重复的。从乘法子群开始,每个元素x的倍数2x也在集合中。对集合S平方,新集合S^2保留同样属性。这允许持续减少数据集大小直到只剩一个值。
BabyBear的模数使其最大乘法子群包含所有非零值,大小为2^k-1。这非常适合上述技术,可通过重复映射有效减少多项式度数。Mersenne31的乘法子群大小为2^31-1,只能除以2一次,之后无法使用该技术。
Mersenne31域非常适合32位CPU/GPU运算。其模数特性(如2^31-1)使许多运算可利用高效位操作:超过模数的结果可通过位移减小。乘法可用特定CPU指令高效处理。Mersenne31的算术运算比BabyBear快约1.3倍。如果能在Mersenne31实现FRI,将显著提升效率。
Circle FRI
Circle STARKs的巧妙之处在于,给定质数p,可找到大小为p的群体,具有类似二对一特性。这个群体由满足特定条件的点组成,如x^2 mod p等于某值的点集。
这些点遵循加法规律:(x1,y1) + (x2,y2) = (x1x2 - y1y2, x1y2 + x2y1) 双倍形式:2*(x,y) = (2x^2 - 1, 2xy)
我们专注于圆上奇数位置的点。首先将所有点收敛到一条直线: f0(x) = (F(x,y) + F(x,-y))/2
然后进行随机线性组合,得到一维多项式P(x)。
从第二轮开始,映射变为: f0(2x^2-1) = (F(x) + F(-x))/2
这个映射每次将集合大小减半。每个x代表两个点:(x,y)和(x,-y)。(x → 2x^2 - 1)是点倍增法则。我们将圆上两个相对点的x坐标转换为倍增后点的x坐标。
Circle FFTs
Circle group也支持FFT,构造方式与FRI类似。关键区别是Circle FFT处理的不是严格多项式,而是Riemann-Roch空间:多项式模圆(x^2 + y^2 - 1 = 0)。
Circle FFT输出的系数是特定基础:{1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 - 8x^2 + 1...}
开发者几乎可以忽略这点。STARKs只需将多项式作为评估值集合存储。FFT仅用于低度扩展:给定N个值,生成k*N个同一多项式上的值。
商运算
STARK常见操作是对特定点进行商运算。例如,证明P(x)=y可通过以下步骤:
在circle group STARK中,由于没有通过单点的线性函数,需要不同技巧。可以构造切线函数,但它在点上具有重数2。因此必须在两点上评估来证明。
如果P在x1处等于y1,在x2处等于y2,我们选择插值函数L在这两点相等。然后证明P-L在这两点为零,通过L除以L来证明商Q是多项式。
消失多项式
STARK中试图证明的多项式方程通常形如C(P(x), P(next(x))) = Z(x) · H(x),Z(x)在原始评估域上恒等于零。
在圆形STARK中,相应函数是: Z1(x,y) = y Z2(x,y) = x Zn+1(x,y) = (2 * Zn(x,y)^2) - 1
反向位序
STARKs中多项式评估通常按反向位序排列。在circle STARKs中,折叠结构略有不同:
为调整反向位序,需反转除最后一位外的每一位,用最后一位决定是否翻转其他位。
效率
Circle STARKs非常高效。计算通常涉及:
效率关键在于充分利用计算跟踪空间。这里字段大小为2^31,浪费空间不大。Poseidon等哈希在任何字段中都充分利用每个数字的每一位。
Binius通过混合不同大小字段实现更高效位打包,但代价是概念更复杂。Circle STARKs概念上相对简单。
结论
Circle STARKs对开发者而言并不比STARKs复杂。实现中与常规FRI的主要区别在于上述三个问题。尽管背后数学复杂,但这种复杂性被很好地隐藏。
理解Circle FRI和FFTs可以成为理解其他特殊FFTs的途径,如二进制域FFTs和椭圆曲线FFTs。
结合Mersenne31、BabyBear和Binius等技术,我们正接近STARKs基础层效率极限。未来优化可能集中在: