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

1 引言

相比常规STARKs系统，Binius采用二进制域直接对位操作，实现了更紧凑高效的编码。Binius使用塔式二进制域算术化、改进版HyperPlonk乘积与置换检查、小域多项式承诺等技术，从多方面提升了效率。本文将深入分析Binius的核心原理,并探讨其在二进制域乘法、ZeroCheck、SumCheck、PCS等方面的进一步优化空间。

2 原理解析

Binius由五项关键技术构成:

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

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

塔式二进制域支持高效的算术操作和简化的算术化过程,特别适合构建可扩展的证明系统。二进制域元素可灵活表示为不同维度的塔域元素,无需额外计算开销即可打包为更大的域元素。

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

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

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

2.3 PIOP:新的多线性移位论证

Binius引入了两种关键方法:Packing和移位运算符,用于高效生成和操作虚拟多项式。

2.4 PIOP:改编版Lasso查找论证

Binius将Lasso协议适应于二进制域操作,引入乘法版本的Lasso协议,并采取措施防止潜在攻击。

2.5 PCS:改编版Brakedown PCS

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

3 优化思考

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

利用GKR协议替代Lasso Lookup算法,可大幅降低Binius的承诺开销。

3.2 ZeroCheck PIOP优化

通过在证明方和验证方之间调整工作量分配,可优化ZeroCheck操作效率。

3.3 Sumcheck PIOP优化

针对小域Sumcheck的改进方案,可进一步减少小域上的计算负担。

3.4 PCS优化:FRI-Binius

FRI-Binius实现了二进制域FRI折叠机制,可将Binius证明大小减少一个数量级。

4 小结

Binius通过使用最小power-of-two域,实现了对witnesses的高效处理。其价值主张在于可根据需求灵活选择域大小,并通过硬件、软件与FPGA协同设计,实现快速低内存的证明生成。目前,Binius已基本移除了Prover的commit承诺瓶颈,新的瓶颈集中在Sumcheck协议。未来,借助专用硬件可望进一步提升Sumcheck效率。