Binius STARKs 分析及其优化

在加密货币和区块链技术的快速发展中，STARKs 作为一种零知识证明系统，扮演着重要角色。它们为确保交易和智能合约的隐私性提供了基础。然而，现有的 STARKs 系统在效率上还有待提高。特别是，第一代到第三代 STARKs 的位宽分别为252、64和32bit，虽然编码效率有所提升，但仍存在浪费空间。Binius 通过直接对位进行操作，实现了更紧凑高效的编码，很可能是未来第四代 STARKs 的代表。

大家都在用的虚拟币交易平台推荐：

• OKX（欧易）>>>进入官网<<< >>>官方下载<<<
• Binance（币安）>>>进入官网<<< >>>官方下载<<<

Binius 利用了基于塔式二进制域的算术化、改进版的 HyperPlonk 乘积与置换检查、以及小域多项式承诺等技术，从各个角度提升了效率。在二进制域乘法、ZeroCheck、SumCheck、PCS 等方面还有进一步优化的空间，以提高证明速度和降低证明大小。

引言

STARKs 可以被看作是基于哈希的 SNARKs，与基于椭圆曲线的 SNARKs 不同。它们在处理实际程序中较小的数值（如 for 循环中的索引、真假值、计数器等）时，效率较低。主要原因是 Reed-Solomon 编码在扩展数据时，会引入大量冗余值，即使原始值很小。因此，降低域的大小成为解决这一问题的关键策略。

第一代到第三代 STARKs 的编码位宽分别为252、64和32bit，但32bit 仍存在大量浪费空间。相比之下，二进制域允许直接对位进行操作，编码紧凑高效，没有任意浪费空间，这就是第四代 STARKs 的核心优势。

二进制域的研究可以追溯到上个世纪80年代，近年来新发现的有限域如 Goldilocks、BabyBear、Mersenne31 等，相比之下，二进制域已广泛应用于密码学中。例如，高级加密标准（AES）基于 F28 域，Galois 消息认证码（GMAC）基于 F2128 域，QR码使用基于 F28 的 Reed-Solomon 编码，原始 FRI 和 zk-STARK 协议，以及进入 SHA-3 决赛的 Grøstl 哈希函数，都是基于二进制域的典型例子。

在采用较小域时，扩域操作对于确保安全性变得尤为重要。Binius 所使用的二进制域完全依赖于扩域来保证其安全性和实际可用性。大多数 Prover 计算可以在基域下进行，从而在小域中实现高效率。然而，随机点检查和 FRI 计算仍需深入到更大的扩域中，以确保所需的安全性。

构建基于二进制域的证明系统时，存在两个实际问题：首先，STARKs 中计算 trace 表示时，所用域大小应大于多项式的阶；其次，STARKs 中 Merkle tree 承诺时，需要做 Reed-Solomon 编码，所用域大小应大于编码扩展后的大小。

Binius 提出了一种创新的解决方案，通过两种不同的方式表示相同的数据来处理这两个问题：首先，使用多变量（具体是多线性）多项式代替单变量多项式，通过其在“超立方体”（hypercubes）上的取值来表示整个计算轨迹；其次，由于超立方体每个维度的长度均为2，因此无法像 STARKs 那样进行标准的 Reed-Solomon 扩展，但可以将超立方体视为方形（square），基于该方形进行 Reed-Solomon 扩展。这种方法在确保安全性的同时，极大提升了编码效率与计算性能。

原理解析

大多数 SNARKs 系统的构建通常包含信息理论多项式交互预言机证明（PIOP）和多项式承诺方案（PCS）两部分。PIOP 将输入的计算关系转化为可以验证的多项式等式，常见的 PIOP 协议包括 PLONK PIOP、Spartan PIOP 和 HyperPlonk PIOP 等。PCS 用于证明 PIOP 生成的多项式等式是否成立，常见的 PCS 有 KZG、Bulletproofs、FRI 和 Brakedown 等。根据具体需求，选择不同的 PIOP 和 PCS，并结合合适的有限域或椭圆曲线，可以构建具有不同属性的证明系统。

Binius 采用 HyperPlonk PIOP 和 Brakedown PCS，并基于二进制域，具体包括五项关键技术：基于塔式二进制域的算术化、改编版的 HyperPlonk 乘积与置换检查、新的多线性移位论证、改编版的 Lasso 查找论证、小域多项式承诺方案。

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

塔式二进制域是实现快速可验证计算的关键，主要因为其高效计算和简化的算术化过程。二进制域支持高度高效的算术操作，且其结构支持简化的算术化过程，使其成为对性能要求敏感的密码学应用的理想选择。塔式二进制域的层次化特性，使其特别适合于如 Binius 这样的可扩展证明系统。

在二进制域中，元素的表示方式非常灵活，例如一个128位字符串可以被视为128位二进制域中的一个独特元素，或者被解析为两个64位塔域元素、四个32位塔域元素、16个8位塔域元素，或128个 F2 域元素。这种表示的灵活性不需要任何计算开销，Binius 协议利用了这一特性，以提高计算效率。

PIOP：改编版 HyperPlonk Product 和 PermutationCheck——适用于二进制域

Binius 协议中的 PIOP 设计借鉴了 HyperPlonk，采用了一系列核心检查机制，包括 GateCheck、PermutationCheck、LookupCheck、MultisetCheck、ProductCheck、ZeroCheck、SumCheck 和 BatchCheck。Binius 在 HyperPlonk 的基础上进行了三方面的改进：优化 ProductCheck、处理除零问题、支持跨列 PermutationCheck。这些改进提升了协议的灵活性和效率，尤其在处理更复杂的多变量多项式验证时，提供了更强的功能支持。

PIOP：新的 multilinear shift argument——适用于 boolean hypercube

在 Binius 协议中，虚拟多项式的构造和处理是关键技术之一。通过 Packing 和移位运算符，Binius 实现了高效的虚拟多项式操作。Packing 方法通过将词典序中相邻位置的较小元素打包成更大的元素来优化操作，而移位运算符则重新排列块内的元素，基于给定偏移量进行循环移位。这些方法提高了计算性能，特别适用于处理大数据集或布尔超立方体中的高维场景。

PIOP：改编版 Lasso lookup argument——适用于二进制域

Lasso 协议允许证明方承诺一个向量，并证明其所有元素均存在于一个预先指定的表中。Lasso 的效率体现在证明效率和无需承诺大表两个方面。Binius 将 Lasso 适应于二进制域的操作，引入了乘法版本的 Lasso 协议，通过二进制域中的乘法生成元来递增“内存计数”操作，以确保协议的安全性。

PCS：改编版 Brakedown PCS——适用于 Small-Field

Binius PCS 的核心思想是 packing，提供了两种基于二进制域的 Brakedown 多项式承诺方案：一种是采用 concatenated code 来实例化；另一种采用 block-level encoding 技术，支持单独使用 Reed-Solomon codes。第二种方案简化了证明和验证流程，但 proof size 略大，但所带来的简化和实现优势，使得这种取舍是值得的。

Binius 多项式承诺主要使用小域多项式承诺与扩展域评估、小域通用构造和块级编码与 Reed-Solomon 码技术。这些技术确保了在小域中承诺多项式的效率和安全性。

优化思考

为了进一步提升 Binius 协议的性能，本文提出了四个关键优化点：GKR-based PIOP、ZeroCheck PIOP 优化、Sumcheck PIOP 优化、PCS 优化。这些优化点分别针对二进制域乘法、ZeroCheck、Sumcheck 和 PCS 的不同方面，旨在降低承诺开销、提高计算效率和减小证明大小。

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

Binius 论文引入了一种基于 lookup 的方案来实现高效的二进制域乘法运算。通过 Lasso lookup argument 改编的二进制域乘法算法依赖于 lookups 和加法操作的线性关系，但仍需要与 limbs 数量线性相关的辅助承诺。GKR 协议通过将整数乘法运算转换为“检查2个32-bit 整数 A 和 B 是否满足 A·B =? C”，借助 GKR 协议大幅减少承诺开销，使该算法更加高效，特别是在 Sumchecks 操作比承诺生成更便宜的场景下。

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

论文《Some Improvements for the PIOP for ZeroCheck》提出了多种优化方案，通过在证明方和验证方之间调整工作量的分配，实现了计算开销的权衡。这些优化包括减少证明方的数据传输、减少证明方评估点的数量、以及代数插值优化。这些改进显著减少了计算和传输成本，降低了证明和验证的复杂性。

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

Binius 所实现的 STARKs 方案，其承诺开销很低，使得 prover 瓶颈不再是 PCS，而在于 sum-check 协议。Ingonyama 在 2024 年提出了针对基于小域的 Sumcheck 协议的改进方案，通过将 Karatsuba 算法合并到算法中，以额外的基域乘法为代价来最小化扩域乘法次数。这些改进在小域上表现出显著的优势，特别是在基域为 GF[2] 的情况下，算法性能提高了近 30 倍。此外，基于小域的 Sumcheck 协议在内存效率方面也表现出显著的优势，适用于资源有限的客户端证明环境。

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

Binius 协议的一个主要缺陷在于其相对较大的证明大小，随着见证大小的平方根按 O(√N) 缩放。FRI-Binius 通过实现二进制域 FRI 折叠机制，带来四方面的创新：扁平化多项式、子空间消失多项式、代数基打包、环交换 SumCheck。这些创新使得 Binius 证明大小减少了一个数量级，使其更加接近最先进的系统，同时保持与二进制域的兼容性。

小结

Binius 的整个价值主张在于，可为 witnesses 使用最小的 power-of-two 域，只需根据所需来选择域大小。它是“使用硬件、软件、与 FPGA 中加速的 Sumcheck 协议”的协同设计方案，可以以非常低的内存使用率来快速证明。相比 Halo2 和 Plonky3 等证明系统，Binius 已基本完全移除了 Prover 的 commit 承诺瓶颈，新的瓶颈在于 Sumcheck 协议，而 Sumcheck 协议中的大量多项式 evaluations 和域乘法等问题，可借助专用硬件高效解决。FRI-Binius 方案为 FRI 变体，提供了从域证明层中消除嵌入开销的选择，而不会导致聚合证明层的成本激增。当前，Irreducible 团队正在开发其递归层，并与 Polygon 团队合作构建 Binius-based zkVM；JoltzkVM 正从 Lasso 转向 Binius，以改进其递归性能；Ingonyama 团队正在实现 FPGA 版本的 Binius。