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

1. 引言

STARKs的演进路径中,编码效率逐步提高但仍存在浪费。Binius通过直接对位操作,实现了更紧凑高效的编码,有望成为第4代STARK。Binius采用塔式二进制域算术化、改进的HyperPlonk乘积与置换检查、小域多项式承诺等技术,从多方面提升效率。在二进制域乘法、ZeroCheck、SumCheck、PCS等方面还可进一步优化,以提高证明速度和减小证明大小。

2. 原理解析

Binius结合了HyperPlonk PIOP、Brakedown PCS和二进制域,包含五项关键技术:

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

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

塔式二进制域支持高效计算和简化的算术化。二进制域元素可灵活表示,无需额外计算开销即可在不同大小的域之间转换。

2.2 PIOP:改编版HyperPlonk Product和PermutationCheck

Binius采用改进的HyperPlonk核心检查机制,包括GateCheck、PermutationCheck、LookupCheck等。主要改进包括:

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

2.3 PIOP:新的multilinear shift argument

Binius引入Packing和移位运算符两种关键方法,高效构造和处理虚拟多项式。

2.4 PIOP:改编版Lasso lookup argument

Binius将Lasso适应二进制域操作,引入乘法版本Lasso协议,并处理了潜在的安全问题。

2.5 PCS:改编版Brakedown PCS

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

3. 优化思考

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

借助GKR协议替换Lasso Lookup算法,可大幅降低承诺开销。

3.2 ZeroCheck PIOP优化

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

3.3 Sumcheck PIOP优化

针对小域Sumcheck的优化,进一步减少小域上的计算负担。

3.4 PCS优化:FRI-Binius

FRI-Binius实现二进制域FRI折叠机制,可显著降低Binius证明大小。

4. 小结

Binius移除了Prover的commit承诺瓶颈,新瓶颈在于Sumcheck协议。FRI-Binius为FRI变体,可消除域证明层嵌入开销。Binius正在开发递归层,并与多个团队合作构建zkVM和FPGA实现。