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

1 引言

STARKs效率低下的一个主要原因是：实际程序中的大多数数值都较小，如for循环中的索引、真假值、计数器等。然而，为了确保基于Merkle树证明的安全性，使用Reed-Solomon编码对数据进行扩展时，许多额外的冗余值会占据整个域，即使原始值本身非常小。为解决该问题，降低域的大小成为了关键策略。

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

相比于Goldilocks、BabyBear、Mersenne31等近几年新研究发现的有限域，二进制域的研究可追溯到上个世纪80年代。当前，二进制域已经广泛应用于密码学中，典型例子包括：

• 高级加密标准(AES)，基于F28域；

• Galois消息认证码(GMAC)，基于F2128域；

• QR码，使用基于F28的Reed-Solomon编码；

• 原始FRI和zk-STARK协议，以及进入SHA-3决赛的Grøstl哈希函数，该函数基于F28域，是一种非常适合递归的哈希算法。

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

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

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

2 原理解析

当前大多数SNARKs系统的构建通常包含以下两部分：

• 信息理论多项式交互预言机证明（Information-Theoretic Polynomial Interactive Oracle Proof, PIOP）：PIOP作为证明系统的核心，将输入的计算关系转化为可以验证的多项式等式。不同的PIOP协议通过与验证者的交互，允许证明者逐步发送多项式，使得验证者通过查询少量多项式的评估结果即可验证计算是否正确。现有的PIOP协议包括：PLONK PIOP、Spartan PIOP 和 HyperPlonk PIOP 等，它们各自对多项式表达式的处理方式有所不同，从而影响整个 SNARK 系统的性能与效率。

• 多项式承诺方案（Polynomial Commitment Scheme, PCS）：多项式承诺方案用于证明PIOP生成的多项式等式是否成立。PCS是一种密码学工具，通过它，证明者可以承诺某个多项式并在稍后验证该多项式的评估结果，同时隐藏多项式的其他信息。常见的多项式承诺方案有KZG、Bulletproofs、FRI（Fast Reed-Solomon IOPP）和Brakedown等。不同的PCS具有不同的性能、安全性和适用场景。

根据具体需求，选择不同的PIOP和PCS，并结合合适的有限域或椭圆曲线，可以构建具有不同属性的证明系统。例如：

• Halo2：由 PLONK PIOP 与 Bulletproofs PCS 结合，并基于Pasta曲线。Halo2设计时，注重于可扩展性，以及移除ZCash协议中的trusted setup。

• Plonky2：采用PLONK PIOP与FRI PCS结合，并基于Goldilocks域。Plonky2是为了实现高效递归的。在设计这些系统时，选择的PIOP和PCS必须与所使用的有限域或椭圆曲线相匹配，以确保系统的正确性、性能和安全性。这些组合的选择不仅影响SNARK的证明大小和验证效率，还决定了系统是否能够在无需可信设置的前提下实现透明性，是否可以支持递归证明或聚合证明等扩展功能。

Binius：HyperPlonk PIOP + Brakedown PCS + 二进制域。具体而言，Binius包括五项关键技术，以实现其高效性和安全性。首先，基于塔式二进制域（towers of binary fields）的算术化构成了其计算的基础，能够在二进制域内实现简化的运算。其次，Binius在其交互式Oracle证明协议（PIOP）中，改编了HyperPlonk乘积与置换检查，确保了变量及其置换之间的安全高效的一致性检查。第三，协议引入了一个新的多线性移位论证，优化了在小域上验证多线性关系的效率。第四，Binius采用了改进版的Lasso查找论证，为查找机制提供了灵活性和强大的安全性。最后，协议使用了小域多项式承诺方案（Small-Field PCS），使其能够在二进制域上实现高效的证明系统，并减少了通常与大域相关的开销。

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

塔式二进制域是实现快速可验证计算的关键，主要归因于两个方面：高效计算和高效算术化。二进制域本质上支持高度高效的算术操作，使其成为对性能要求敏感的密码学应用的理想选择。此外，二进制域结构支持简化的算术化过程，即在二进制域上执行的运算可以以紧凑且易于验证的代数形式表示。这些特性，加上能够通过塔结构充分利用其层次化的特性，使得二进制域特别适合于诸如Binius这样可扩展的证明系统

其中"canonical"是指在二进制域中元素的唯一且直接的表示方式。例如，在最基本的二进制域F2中，任意k位的字符串都可以直接映射到一个k位的二进制域元素。这与素数域不同，素数域无法在给定位数内提供这种规范的表示。尽管32位的素数域可以包含在32位中，但并非每个32位的字符串都能唯一地对应一个域元素，而二进制域则具备这种一对一映射的便利性。在素数域Fp中，常见的归约方法包括Barrett归约、Montgomery归约，以及针对Mersenne-31或Goldilocks-64等特定有限域的特殊归约方法。在二进制域F2k中，常用的归约方法包括特殊归约（如AES中使用）、Montgomery归约（如POLYVAL中使用）和递归归约（如Tower）。论文《Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations》指出，二进制域在加法和乘法运算中均无需引入进位，且二进制域的平方运算非常高效，因为它遵循(X + Y )2 = X2 + Y 2 的简化规则。

如图1所示，一个128位字符串：该字符串可以在二进制域的上下文中以多种方式进行解释。它可以被视为128位二进制域中的一个独特元素，或者被解析为两个64位塔域元素、四个32位塔域元素、16个8位塔域元素，或128个F2域元素。这种表示的灵活性不需要任何计算开销，只是对位字符串的类型转换（typecast），是一个非常有趣且有用的属性。同时，小域元素可以被打包为更大的域元素而不需要额外的计算开销。Binius协议利用了这一特性，以提高计算效率。此外，论文《On Efficient Inversion in Tower Fields of Characteristic Two》探讨了在n位塔式二进制域中（可分解为m位子域）进行乘法、平方和求逆运算的计算复杂度。

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

Binius协议中的PIOP设计借鉴了HyperPlonk，采用了一系列核心检查机制，用于验证多项式和多变量集合的正确性。这些核心检查包括：

1. GateCheck：验证保密见证ω和公开输入x是否满足电路运算关系C(x,ω)=0，以确保电路正确运行。

2. PermutationCheck：验证两个多变量多项式f和g在布尔超立方体上的求值结果是否为置换关系f(x) = f(π(x))，以确保多项式变量之间的排列一致性。

3. LookupCheck：验证多项式的求值是否在给定的查找表中，即f(Bµ) ⊆ T(Bµ)，确保某些值在指定范围内。

4. MultisetCheck：检查两个多变量集合是否相等，即{(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H，保证多个集合间的一致性。

5. ProductCheck：检测有理多项式在布尔超立方体上的求值是否等于某个声明的值∏x∈Hµ f(x) = s，以确保多项式乘积的正确性。

6. ZeroCheck：验证一个多变量多项式在布尔超立方体上的任意点是否为零∏x∈Hµ f(x) = 0,∀x ∈ Bµ，以确保多项式的零点分布。

7. SumCheck：检测多变量多项式的求和值是否为声明的值∑x∈Hµ f(x) = s。通过将多元多项式的求值问题转化为单变量多项式求值，降低验证方的计算复杂度。此外，SumCheck还允许批处理，通过引入随机数，构造线性组合实现对多个和校验实例的批处理。

8. BatchCheck：基于SumCheck，验证多个多变量多项式求值的正确性，以提高协议效率。

尽管Binius与HyperPlonk在协议设计上有许多相似之处，但Binius在以下3个方面做出改进：

• ProductCheck优化：在HyperPlonk中，ProductCheck要求分母U在超立方体上处处非零，且乘积必须等于一个特定值；Binius通过将该值特化为1，简化这一检查过程，从而降低计算复杂度。

• 除零问题的处理：HyperPlonk未能充分处理除零情况，导致无法断言U在超立方体上的非零问题；Binius正确地处理了这一问题，即使在分母为零的情况下，Binius的ProductCheck也能继续处理，允许推广到任意乘积值。

• 跨列PermutationCheck：HyperPlonk无此功能；Binius支持在多个列之间进行PermutationCheck，这使得Binius能够处理更复杂的多项式排列情况。

因此，Binius通过对现有PIOPSumCheck机制的改进，提升了协议的灵活性和效率，尤其在处理更复杂的多变量多项式验证时，提供了更强的功能支持。这些改进不仅解决了HyperPlonk中的局限性，还为未来基于二进制域的证明系统奠定了基础。

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

在Binius协议中，虚拟多项式的构造和处理是关键技术之一，能够有效地生成和操作从输入句柄或其他虚拟多项式派生出的多项式。以下是两个关键方法：

• Packing：