Binius STARKs原理解析及其优化思考

1 引言

STARKs效率低下的一个主要原因是:实际程序中的大多数数值都较小，但为了确保基于Merkle树证明的安全性，使用Reed-Solomon编码对数据进行扩展时，许多额外的冗余值会占据整个域。降低域的大小成为了关键策略。

第1代STARKs编码位宽为252bit，第2代为64bit，第3代为32bit，但32bit编码位宽仍然存在大量浪费空间。相较而言，二进制域允许直接对位进行操作，编码紧凑高效而无任意浪费空间，即第4代STARKs。

二进制域已经广泛应用于密码学中，典型例子包括:

• 高级加密标准(AES)，基于F28域
• Galois消息认证码(GMAC)，基于F2128域
• QR码，使用基于F28的Reed-Solomon编码
• 原始FRI和zk-STARK协议，以及进入SHA-3决赛的Grøstl哈希函数

当采用较小的域时，扩域操作对于确保安全性愈发重要。Binius所使用的二进制域，需完全依赖扩域来保证其安全性和实际可用性。

Binius提出了一种创新的解决方案:

• 使用多变量（具体是多线性）多项式代替单变量多项式，通过其在"超立方体"上的取值来表示整个计算轨迹
• 将超立方体视为方形，基于该方形进行Reed-Solomon扩展

2 原理解析

Binius = HyperPlonk PIOP + Brakedown PCS + 二进制域

Binius包括五项关键技术:

1. 基于塔式二进制域的算术化
2. 改编版HyperPlonk乘积与置换检查
3. 新的多线性移位论证
4. 改进版Lasso查找论证
5. 小域多项式承诺方案

2.1 有限域:基于towers of binary fields的算术化

塔式二进制域的优势:

• 高效计算:二进制域本质上支持高度高效的算术操作
• 高效算术化:二进制域结构支持简化的算术化过程
• 灵活表示:同一个字符串可以在二进制域的上下文中以多种方式解释
• 无需归约:二进制域在加法和乘法运算中均无需引入进位
• 高效平方运算:(X + Y)2 = X2 + Y2

2.2 PIOP:改编版HyperPlonk Product和PermutationCheck

核心检查机制:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

相比HyperPlonk的改进:

• ProductCheck优化
• 除零问题的处理
• 跨列PermutationCheck

2.3 PIOP:新的multilinear shift argument

关键方法:

• Packing:通过将词典序中相邻位置的较小元素打包成更大的元素来优化操作
• 移位运算符:重新排列块内的元素，基于给定偏移量进行循环移位

2.4 PIOP:改编版Lasso lookup argument

Lasso协议的优势:

• 高效证明:对于大小为n的表中的m次查找,只需承诺m+n个域元素
• 无需承诺大表:如果表t是结构化的,则无需对其进行承诺,可处理超大表

Lasso协议的组成:

• 大表的虚拟多项式抽象
• 小表查找
• 多集合检查

Binius对Lasso的改编:

• 引入乘法版本的Lasso协议
• 要求证明方承诺一个处处非零的读取计数向量

2.5 PCS:改编版Brakedown PCS

核心思想:packing

两种方案:

1. 采用concatenated code
2. 采用block-level encoding技术,支持单独使用Reed-Solomon codes

主要技术:

• 小域多项式承诺与扩展域评估
• 小域通用构造
• 块级编码与Reed-Solomon码

3 优化思考

四个关键优化点:

1. GKR-based PIOP:针对二进制域乘法运算
2. ZeroCheck PIOP优化:Prover与Verifier计算开销权衡
3. Sumcheck PIOP优化:基于小域的Sumcheck协议
4. PCS 优化:FRI-Binius降低Binius proof size

3.1 GKR-based PIOP:基于GKR的二进制域乘法

核心思想:

将"检查2个32-bit整数A和B是否满足 A·B =? C" 转换为
"检查中(gA)B =? gC 是否成立"

优势:

• 只需一个辅助承诺
• 减少Sumchecks的开销

3.2 ZeroCheck PIOP优化

优化方向:

• 减少证明方的数据传输
• 减少证明方评估点的数量
• 代数插值优化

3.3 Sumcheck PIOP优化

改进重点:

• 切换轮次的选择
• 基域大小对性能的影响
• Karatsuba算法的优化收益
• 内存效率的提升

具体成效:

• 在基域为GF[2]的情况下,算法4的性能比朴素算法高出近30倍
• 算法4仅需0.26MB的内存,而算法3则需67MB

3.4 PCS 优化:FRI-Binius

四个创新点:

1. 扁平化多项式
2. 子空间消失多项式
3. 代数基打包
4. 环交换SumCheck

成效: 将Binius证明大小减少一个数量级

4 小结

Binius的优势:

• 可为witnesses使用最小的power-of-two域
• 低内存使用率,快速证明
• 基本完全移除了Prover的commit承诺瓶颈

FRI-Binius方案: 从域证明层中消除嵌入开销,而不会导致聚合证明层的成本激增

最新进展:

• Irreducible团队正在开发其递归层,并与Polygon团队合作构建Binius-based zkVM
• JoltzkVM正从Lasso转向Binius,以改进其递归性能
• Ingonyama团队正在实现FPGA版本的Binius