Binius STARKs技术原理解析与性能优化方案探讨

引言

与传统的基于椭圆曲线的SNARKs技术不同，STARKs本质上是一种基于哈希的SNARKs实现。当前STARKs在实际应用中面临的主要效率瓶颈在于，程序运行过程中产生的大部分数值（如循环索引、布尔值和计数器等）通常都很小，但为了确保Merkle树证明的安全性，系统必须采用Reed-Solomon编码对数据进行扩展，这就导致了大量冗余值占用整个域空间。要解决这一效率问题，关键在于如何有效缩减域的大小。

从表1可以看出，STARKs技术经历了显著的发展演进：第一代STARKs采用252bit编码位宽，第二代缩减至64bit，第三代进一步优化到32bit。然而即便是32bit的编码位宽，仍然存在明显的空间浪费问题。相比之下，二进制域允许直接对位进行操作，其编码方式更加紧凑高效，完全消除了空间浪费，这就是第四代STARKs的创新所在。

表1：STARKs技术演进路径

相较于近期备受关注的Goldilocks、BabyBear和Mersenne31等有限域技术，二进制域的研究历史可以追溯到1980年代。如今，二进制域已在密码学领域得到广泛应用，典型的应用场景包括：

• 基于𝐹₂⁸域的高级加密标准（AES）
• 基于𝐹₂¹²⁸域的伽罗瓦消息认证码（GMAC）
• 采用𝐹₂⁸域Reed-Solomon编码的QR二维码
• 原始的FRI和zk-STARK协议，以及在SHA-3竞赛中入围决赛的Grøstl哈希函数

在使用较小域时，域扩展操作对确保安全性至关重要。Binius采用的二进制域完全依赖域扩展来保证安全性和实用性。大多数与证明者操作相关的多项式计算只需在基域中进行，从而在小域环境下实现高效运算。不过，随机点检查和FRI计算仍需在更大的扩展域中执行，以确保达到必要的安全级别。

在基于二进制域构建证明系统时，面临两个主要挑战：首先，STARKs中用于轨迹表示的域大小必须大于多项式的度数；其次，用于Merkle树承诺的域大小需大于经过Reed-Solomon编码扩展后的数据规模。Binius通过创新的多变量多项式表示方法和特殊的Reed-Solomon扩展方案，有效解决了这些问题。

Binius技术原理

现代SNARK系统的构建通常包含两个核心组件：信息论多项式交互式神谕证明（PIOP）和多项式承诺方案（PCS）。PIOP作为证明系统的核心，负责将计算关系转换为可验证的多项式方程；PCS则是一种加密工具，用于证明PIOP生成的多项式方程的有效性。

通过选择不同的PIOP和PCS方案，并与适当的有限域或椭圆曲线相结合，可以构建具有不同特性的证明系统。例如，Halo2结合了PLONK PIOP与Bulletproofs PCS，在Pasta曲线上运行；而Plonky2则采用PLONK PIOP与FRI PCS的组合，基于Goldilocks域优化递归效率。

Binius创新性地结合了HyperPlonk PIOP与Brakedown PCS，并在二进制域中运行。具体而言，Binius整合了五项关键技术：基于二进制域塔的算术、HyperPlonk乘积和置换检查、新型多线性移位论证、改进的Lasso查找论证，以及专为小域设计的多项式承诺方案。这些技术创新使Binius能够在二进制域中实现高效、安全的证明系统。

有限域：塔式二进制域算术

塔式二进制域是实现快速可验证计算的关键技术，其优势主要体现在高效计算和高效算术化两个方面。二进制域本质上支持高度优化的算术操作，特别适合对性能要求严苛的密码学应用。此外，二进制域结构支持简化的算术化过程，使得运算可以以紧凑且易于验证的代数形式表示。

如图1所示，一个128位字符串在二进制域中可以灵活地以多种方式进行解释：既可以视为128位二进制域中的独立元素，也可以解析为两个64位、四个32位或十六个8位的塔域元素。这种表示的灵活性不需要任何计算开销，仅需进行简单的类型转换。Binius协议充分利用了这一特性来提升计算效率。

图1：塔式二进制域结构

PIOP：适用于二进制域的HyperPlonk改进

Binius协议中的PIOP设计借鉴了HyperPlonk，采用了一系列核心检查机制来验证多项式和多变量集合的正确性。这些检查包括门电路验证、置换检查、查找验证、多重集合检查、乘积检查、零点检查、求和检查以及批量检查等。

虽然Binius与HyperPlonk在协议设计上有许多相似之处，但Binius在三个方面做出了重要改进：优化了乘积检查过程、正确处理了除零问题，并支持跨列置换检查。这些改进不仅解决了HyperPlonk中的局限性，还为未来基于二进制域的证明系统奠定了基础。

PCS：适用于小域的Brakedown改进

Binius多项式承诺方案的核心思想是packing技术。论文中提出了两种基于二进制域的Brakedown多项式承诺方案：一种采用级联码实现，另一种采用块级编码技术配合Reed-Solomon码。第二种方案虽然证明尺寸略大，但显著简化了实现过程。

Binius的PCS主要采用小域多项式承诺与扩展域评估、小域通用构造以及块级编码与Reed-Solomon码技术。这些技术的结合使得在小域（如F₂）中承诺多项式成为可能，同时保持了高效的计算性能。

Binius性能优化

为了进一步提升Binius协议的性能，研究者们提出了四个关键优化方向：基于GKR的二进制域乘法运算、ZeroCheck PIOP优化、小域Sumcheck协议优化，以及通过FRI-Binius降低证明尺寸。

基于GKR的二进制域乘法

Binius论文最初引入的基于lookup的二进制域乘法算法虽然在一定程度上优化了乘法操作，但仍需要与limbs数量线性相关的辅助承诺。相比之下，基于GKR协议的整数乘法算法通过巧妙的数学转换，仅需一个辅助承诺，并大幅减少了Sumchecks开销，使算法更加高效。

ZeroCheck PIOP优化

ZeroCheck PIOP优化通过在证明方和验证方之间重新分配工作量，显著降低了数据传输量和计算复杂度。优化方法包括减少证明方的数据传输、减少评估点数量以及采用代数插值优化等技术。这些改进在常见的d=3情况下，使成本降低了5/3倍。

小域Sumcheck协议优化

针对小域的Sumcheck协议优化主要关注切换轮次t的选择。研究表明，在最佳切换点时，优化算法比朴素算法的性能提升可达一个数量级。特别是对于基域为GF[2]的情况，优化算法的性能优势最为显著。

图2：切换轮次与改进因子的关系

FRI-Binius降低证明尺寸

FRI-Binius通过四种创新技术实现了证明尺寸的显著降低：扁平化多项式、子空间消失多项式、代数基打包以及环交换SumCheck。这些技术的结合使得Binius的证明尺寸减少了一个数量级，使其更加接近最先进的证明系统。

表2：Binius与FRI-Binius证明尺寸比较

结论

Binius的核心价值在于可以根据实际需求选择最小化的power-of-two域大小。该系统通过硬件、软件与FPGA加速的Sumcheck协议协同设计，能够以极低的内存占用实现快速证明。目前，Irreducible团队正在开发递归层，并与Polygon合作构建基于Binius的zkVM；Jolt zkVM也从Lasso转向Binius以改进递归性能；Ingonyama团队则正在实现FPGA版本的Binius。

图3：承诺成本对比

参考文献

1. 2024.04 Binius Succinct Arguments over Towers of Binary Fields
2. 2024.07 Fri-Binius Polylogarithmic Proofs for Multilinears over Binary Towers
3. 2024.08 Integer Multiplication in Binius: GKR-based approach
4. 2024.06 zkStudyClub – FRI-Binius: Polylogarithmic Proofs for Multilinears over Binary Towers
5. 2024.04 ZK11: Binius: a Hardware-Optimized SNARK – Jim Posen

声明

1. 本文转载自bitlayer，著作权归属原作者lynndell。
2. 免责声明：本文所表达的观点和意见仅代表作者个人观点，不构成任何投资建议。
3. 文章其他语言版本由Gate Learn团队翻译，转载需注明出处。