Binius STARKs分析及其优化

1. 引言

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

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

Binius使用基于塔式二进制域的算术化、改进版的HyperPlonk乘积与置换检查、小域多项式承诺等技术，从各个角度提升效率。

2. 原理解析

Binius由五项关键技术组成:

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

2.1 基于塔式二进制域的算术化

塔式二进制域支持高效的算术操作和简化的算术化过程。二进制域元素可以直接映射到k位的字符串,具有一对一映射的便利性。

2.2 改编版HyperPlonk乘积和置换检查

Binius借鉴了HyperPlonk的核心检查机制,包括GateCheck、PermutationCheck、LookupCheck等,并在以下方面做出改进:

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

2.3 新的多线性移位论证

Binius引入了Packing和移位运算符两个关键方法来构造和处理虚拟多项式。

2.4 改编版Lasso查找论证

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

2.5 小域多项式承诺

Binius提供了两种基于二进制域的Brakedown多项式承诺方案,主要使用小域多项式承诺与扩展域评估、小域通用构造和块级编码与Reed-Solomon码技术。

3. 优化思考

3.1 GKR-based PIOP

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

3.2 ZeroCheck PIOP优化

通过在证明方和验证方之间调整工作量分配,提出了多种优化方案:

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

3.3 Sumcheck PIOP优化

Ingonyama提出了针对基于小域的Sumcheck协议的改进方案,集中于切换轮次t的选择。

3.4 PCS优化:FRI-Binius

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

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

4. 小结

Binius是"使用硬件、软件、与FPGA中加速的Sumcheck协议"的协同设计方案,可以以非常低的内存使用率来快速证明。Binius中已基本完全移除了Prover的commit承诺瓶颈,新的瓶颈在于Sumcheck协议,而这可借助专用硬件高效解决。

FRI-Binius方案为FRI变体,可从域证明层中消除嵌入开销,而不会导致聚合证明层的成本激增。当前,多个团队正在开发Binius相关技术,包括递归层、zkVM等。