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

1. 引言

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

第1代STARKs编码位宽为252bit,第2代为64bit,第3代为32bit,但32bit仍存在大量浪费空间。二进制域允许直接对位操作,编码紧凑高效无浪费,可能是第4代STARKs。

二进制域广泛应用于密码学,如AES(F28)、GMAC(F2128)、QR码(F28)等。当采用较小域时,扩域操作对确保安全性愈发重要。Binius使用的二进制域,需完全依赖扩域来保证安全性和可用性。大多数Prover计算在基域下操作,高效;随机点检查和FRI计算需深入更大扩域,确保安全性。

Binius创新解决方案:

1. 使用多变量(多线性)多项式代替单变量多项式,通过"超立方体"取值表示计算轨迹
2. 将超立方体视为方形,基于方形进行Reed-Solomon扩展

2. 原理解析

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

五项关键技术:

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

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

塔式二进制域优势:

• 高效计算:二进制域支持高效算术操作
• 高效算术化:二进制域结构支持简化算术化过程
• 通过塔结构充分利用层次化特性

128位字符串可灵活解释:

• 128位二进制域中一个独特元素
• 两个64位塔域元素
• 四个32位塔域元素
• 16个8位塔域元素
• 128个F2域元素

2.2 PIOP:改编版HyperPlonk Product和PermutationCheck

Binius核心检查机制:

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

Binius对HyperPlonk改进:

• ProductCheck优化
• 正确处理除零问题
• 支持跨列PermutationCheck

2.3 PIOP:新的multilinear shift argument

关键方法:

• Packing:将相邻较小元素打包成更大元素
• 移位运算符:重新排列块内元素

2.4 PIOP:改编版Lasso lookup argument

Lasso协议优势:

• 证明效率高:m+n个域元素承诺
• 无需承诺大表:可处理超大表

Binius引入乘法版Lasso协议:

• 通过二进制域乘法生成元递增"内存计数"
• 证明方承诺非零读取计数向量确保安全

2.5 PCS:改编版Brakedown PCS

核心思想:packing

两种方案:

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

小域多项式承诺与扩展域评估:

• 承诺在小域K上
• 评估在更大扩展域L/K中

块级编码与Reed-Solomon码:

• 允许小域(如F2)多项式使用大字母表(如F216) Reed-Solomon码高效承诺

3. 优化思考

四个关键优化点:

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

将"检查A·B =? C"转换为"检查(gA)B =? gC"

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

3.2 ZeroCheck PIOP优化:Prover与Verifier计算开销权衡

优化方法:

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

3.3 Sumcheck PIOP优化:基于小域的Sumcheck协议

改进重点:

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

3.4 PCS优化:FRI-Binius降低proof size

四项创新:

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

FRI-Binius可将Binius证明大小减少一个数量级

4. 小结

Binius优势:

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

新瓶颈:Sumcheck协议

• 可借助专用硬件高效解决

FRI-Binius:

• 消除域证明层嵌入开销
• 不导致聚合证明层成本激增

当前进展:

• Irreducible团队开发递归层,与Polygon合作构建Binius-based zkVM
• JoltzkVM从Lasso转向Binius
• Ingonyama实现FPGA版Binius