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

1 引言

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

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

表 1: STARKs 衍化路径

| 特征 | 第1代STARKs | 第2代STARKs | 第3代STARKs | 第4代STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | 编码位宽 | 252bit | 64bit | 32bit | 1bit | | 代表性系统 | StarkWare | Plonky2 | BabyBear | Binius |

相比于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中的局限性，还为未来基于二进