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

1 引言

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

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

二进制域已广泛应用于密码学中，如AES、GMAC、QR码、原始FRI和zk-STARK协议等。

Binius采用二进制域时，需完全依赖扩域来保证安全性和实际可用性。大多数Prover计算中涉及的多项式无需进入扩域，而只需在基域下操作，从而在小域中实现了高效率。

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协议中的PIOP设计借鉴了HyperPlonk，采用一系列核心检查机制:

• GateCheck
• PermutationCheck
• LookupCheck
• MultisetCheck
• ProductCheck
• ZeroCheck
• SumCheck
• BatchCheck

Binius在以下3个方面做出改进:

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

2.3 PIOP：新的multilinear shift argument

Binius协议中虚拟多项式的构造和处理的关键方法:

• Packing
• 移位运算符

2.4 PIOP：改编版Lasso lookup argument

Lasso协议由三个组件构成:

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

Binius协议将Lasso适应于二进制域的操作，引入了乘法版本的Lasso协议。

2.5 PCS：改编版Brakedown PCS

Binius论文提供了2种基于二进制域的Brakedown多项式承诺方案:

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

小域多项式承诺与扩展域评估、小域通用构造和块级编码与Reed-Solomon码等技术被用于构建Binius多项式承诺。

3 优化思考

四个关键优化点:

1. GKR-based PIOP：针对二进制域乘法运算,借助GKR协议替换Lasso Lookup算法

2. ZeroCheck PIOP优化：在Prover与Verifier之间进行计算开销权衡

3. Sumcheck PIOP优化：针对小域Sumcheck的优化

4. PCS优化：通过FRI-Binius优化降低证明大小

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

基于GKR的整数乘法运算算法,通过将"检查2个32-bit整数A和B是否满足 A·B =? C"，转换为"检查中(gA)B =? gC 是否成立"，借助GKR协议大幅减少承诺开销。

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

主要优化方向:

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

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

主要优化点:

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

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

FRI-Binius实现了二进制域FRI折叠机制,带来4个方面的创新:

• 扁平化多项式
• 子空间消失多项式
• 代数基打包
• 环交换SumCheck

4 小结

Binius的价值主张是可为witnesses使用最小的power-of-two域。Binius中已基本完全移除了Prover的commit承诺瓶颈,新的瓶颈在于Sumcheck协议。

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

当前,Irreducible团队正开发其递归层,并与Polygon团队合作构建Binius-based zkVM；JoltzkVM正从Lasso转向Binius；Ingonyama团队正在实现FPGA版本的Binius。