Binius STARKs原理及优化：高效证明系统解析

微小发报道：

1. 引言
   STARKs ，与传统的基于椭圆曲线的SNARKs不同，可以视作hash-based SNARKs。当前STARKs效率不高的主要原因是程序中大多数数值都偏小，比如for循环中的索引、真假值和计数器等。为了保证Merkle树证明的安全性，使用Reed-Solomon编码扩展数据时，很多冗余值占据整个域，就算原始值很小。这就需要降低域的大小，成为了解决问题的关键策略。

   如表1所示，第1代STARKs编码位宽为252bit，第2代为64bit，第3代仅32bit，但32bit编码仍然存在大量浪费空间。相比之下，二进制域允许直接操作位，编码更紧凑高效，避免任何浪费，这便是第4代STARKs的优势。

   二进制域的研究可追溯到上世纪80年代，较之Goldilocks、BabyBear、Mersenne31等新兴有限域，二进制域在密码学中已被广泛应用，典型实例包括：

   • 高级加密标准 (AES)，基于F28域；
   • Galois消息认证码 (GMAC)，基于F2128域；
   • QR码，使用基于F28的Reed-Solomon编码；
   • 原始FRI和zk-STARK协议，还有进入SHA-3决赛的Grøstl哈希函数，基于F28域，适合递归的哈希算法。

   当使用较小的域时，扩域操作对确保安全性变得尤为重要。Binius所采用的二进制域完全依赖于扩域来保证安全性和实际可用性。大多数Prover计算中涉及的多项式无需扩域处理，只需在基域下操作，这样能在小域中实现高效率。不过，随机点检查和FRI计算仍需深入扩域，确保安全性到位。 基于二进制域构建证明系统时，有俩大问题。首先，STARKs 中计算 trace 表示时，域的大小得大于多项式的阶；其次，STARKs 的 Merkle tree 承诺需要做 Reed-Solomon 编码，域大小得大于编码扩展后的大小。

Binius 则提出了一个创新方案，分别解决这俩问题，采用两种不同方式表示相同数据：第一，换用多变量（具体是多线性）多项式，利用其在“超立方体”上的取值来展现整个计算轨迹；第二，由于超立方体每个维度的长度都是 2，无法像 STARKs 那样做标准的 Reed-Solomon 扩展，但可以把超立方体当做方形，基于这个方形进行 Reed-Solomon 扩展。这方法在确保安全性的同时，极大提升了编码效率与计算性能。🚀

原理解析

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

· 信息理论多项式交互预言机证明（PIOP）： PIOP 是证明系统的核心，把输入的计算关系转化成可验证的多项式等式。不同的 PIOP 协议通过与验证者的交互，允许证明者逐步发送多项式，让验证者通过查询少量多项式的评估结果来验证计算是否正确。现有的 PIOP 协议有 PLONK PIOP、Spartan PIOP 和 HyperPlonk PIOP 等，它们对多项式表达式的处理方式不一样，从而影响整个 SNARK 系统的性能与效率。

· 多项式承诺方案（PCS）： PCS 用于证明 PIOP 生成的多项式等式是否成立。它是个密码学工具，证明者可以承诺某个多项式，稍后验证该多项式的评估结果，同时隐藏其他信息。常见的多项式承诺方案有 KZG、Bulletproofs、FRI（Fast Reed-Solomon IOPP）和 Brakedown 等。不同的 PCS 在性能、安全性和适用场景上各有千秋。✨ 根据不同需求，选择合适的 PIOP（可交互证明协议）和 PCS（证明系统），还能结合特定的有限域或椭圆曲线，打造多样化的证明系统。比如：

•   halo2： 结合了 PLONK PIOP 和 Bulletproofs PCS，基于 Pasta 曲线设计。halo2 强调可扩展性，同时摆脱了 ZCash 协议中的可信设置。

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

•   binius： 结合 HyperPlonk PIOP 和 Brakedown PCS，采用二进制域。binius 包含五项关键技术，以确保高效且安全。首先，基于 塔式二进制 域的算术为其计算奠定基础，实现了简化运算。其次，在交互式 Oracle 证明协议中，binius 改编了 HyperPlonk 乘积与置换检查，确保变量及其置换之间的安全一致性。第三，引入了 新的多线性移位论证，提升了在小域上验证多线性关系的效率。第四，采用改进版的 Lasso 查找论证，为查找机制提供灵活性和强大的安全性。最后，协议运用 小域多项式承诺方案，使其在二进制域上实现高效证明系统，并降低了通常与大域相关的开销。

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

塔式二进制域✨是快速可验证计算的秘密武器，原因主要有两个：高效的计算和算术化。二进制域可谓是算术操作的超级高手，特别适合对性能要求高的密码学应用。更妙的是，它的结构让算术化过程变得简单，运算可以用紧凑且易验证的代数形式表达。这些优点，加上塔结构的层次特性，让二进制域成为像Binius这样的可扩展证明系统的最佳选择。

说到“canonical”，这可是二进制域中元素的独特ID哦。在最基本的二进制域F2里，任何k位的字符串都能直接对应到一个k位的二进制域元素。这和素数域可不一样，素数域在定长内可没这待遇。虽然32位的素数域可以包容32位，但并不是所有32位字符串都能对应一个唯一的域元素，而二进制域则完美解决了这个一对一映射的问题。至于素数域Fp，常见的归约方法有B*arrett归约、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)² = X² + Y²的简化法则。💡 如图 1 所示，128 位字符串在二进制域中有多种解读方式。它不仅可以被看作128位二进制域的独特元素，还能被视为两个64位、四个32位、16个8位或128个F2域的元素。这种灵活性不需要额外计算，只是简单的类型转换，真是个有趣且实用的特性。同时，小域元素可以无缝打包成更大的域元素而不需额外计算。Binius 协议就是利用了这一点，提升了计算效率。此外，论文《On Efficient Inversion in Tower Fields of Characteristic Two》探讨了在 n 位塔式二进制域（可分解为 m 位子域）中进行乘法、平方和求逆运算的复杂度。

2.2 PIOP：改编版 HyperPlonk 产品与排列检查——专为二进制域设计

在 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 在以下三个方面进行了妙招改进：

· ProductCheck 优化： 在 HyperPlonk 中，ProductCheck 要求分母 U 在超立方体上处处非零且乘积得等于特定值；Binius 把这个值简化为 1，轻松化了检查流程，降低了计算的复杂度。

· 除零问题的处理： HyperPlonk 对于除零的情况处理得不够好，导致无法确保 U 在超立方体上的非零性；Binius 则聪明地解决了这个问题，ProductCheck 即使在分母为零的情况下也能顺利处理，允许推广到任意乘积值。

· 跨列 PermutationCheck： HyperPlonk 没有这项功能；而 Binius 支持在多个列之间进行 PermutationCheck，能更灵活地处理复杂的多项式排列情况。

综上所述，Binius 通过对现有 PIOPSumCheck 机制的改良，显著提升了协议的灵活性和效率，尤其是在处理复杂的多变量多项式验证时，提供了更强的功能支持。这些妙招不仅解决了 HyperPlonk 的局限，还为未来基于二进制域的证明系统打下了坚实基础。 在微小发报道中，咱们来聊聊PIOP的新特性，特别是它的multilinear shift argument，适合于布尔超立方体的应用，听起来酷吧？

1. Binius 协议中的虚拟多项式：这可是个关键技术，能高效生成和处理从输入句柄或其他虚拟多项式派生出的多项式。核心有两个方法：

   • 打包（Packing）：这个方法通过把词典序中相邻位置的较小元素合并成一个更大的元素来优化操作。Pack 运算符作用于大小为 2κ 的块，将它们合成高维域中的单一元素。借助多线性扩展（MLE），这个虚拟多项式能高效评估和处理，把函数 t 转换为另一多项式，提升计算性能，简直牛逼！💪

   • 移位运算符：这个家伙负责重新排列块内的元素，基于给定的偏移量 o 进行循环移位。适用于大小为 2b 的块，每个块都根据偏移量进行移位。这个运算符通过检测函数的支持来定义，确保在处理虚拟多项式时的一致性和效率。特别是，在处理大数据集或布尔超立方体的高维场景时，构造的复杂度随块大小线性增长，真是个好帮手！📈

再来看看PIOP的另一面，改编版 Lasso lookup argument，这次适用于二进制域。

1. Lasso 协议的承诺机制：这个协议允许证明方承诺一个向量 a ∈ Fm，并证明它的所有元素都在一个预先指定的表 t ∈ Fn 中。这一设计引入了“查找奇点”（lookup singularities）的概念，适合多线性多项式承诺方案。它的效率主要体现在两个方面：

   • 证明效率：对于大小为 n 的表中的 m 次查找，证明方只需承诺 m+n 个域元素。这些元素小巧玲珑，均位于集合 {0,...,m} 中。在基于多次幂运算的承诺方案中，证明方的计算成本为 O(m + n) 次群运算（比如椭圆曲线点加），还得加上验证多线性多项式是否为表元素的求值成本，真是让人头疼的数学！🤯 · 无需承诺大表： 当表 t 是结构化的，就不需要承诺，这样就能轻松处理超大表（比如 2128 或更大）。证明方的运行时间只和被访问的表条目有关。对于任意整数参数 c > 1，证明方的主要成本主要体现在证明的大小上，承诺的域元素数量为 3·c m + c·n1/c。这些域元素都是小的，位于集合 {0,...,max{m,n1/c,q} − 1} 中，其中 q 是 a 中的最大值。

Lasso 协议包含以下三个部分：

· 虚拟多项式抽象： 通过虚拟多项式的组合，实现在大表上的高效操作，确保表内查找和处理的效率。

· 小表查找： Lasso 的核心是小表查找，它是虚拟多项式协议的重要组成部分，利用离线内存检测来验证一个虚拟多项式在布尔超立方体上的求值是否是另一个虚拟多项式求值的子集。这个查找过程可以简化为多集合检测的问题。

· 多集合检查： Lasso 还引入了虚拟协议，用于执行多集合检查，验证两个集合的元素是否相等或满足特定条件。

Binius 协议则将 Lasso 适应于二进制域的操作，假设当前域是一个大特征的素数域（远大于被查找列的长度）。Binius 引入了 Lasso 协议的乘法版本，要求证明方和验证方共同递增协议的“内存计数”操作，不是简单地加 1，而是通过二进制域中的乘法生成元来递增。不过，这个乘法改编增加了复杂性，因为乘法生成元并不总是在所有情况下递增，且在 0 处存在单一轨道，这可能成为攻击的切入点。为了防止这种潜在攻击，证明方必须承诺一个处处非零的读取计数向量，以确保协议的安全性。

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

构建 BiniusPCS 的核心概念是 packing。在 Binius 论文中，介绍了两种基于二进制域的 Brakedown 多项式承诺方案：一种是利用 concatenated code 来实现，另一种则采用 block-level encoding 技术，支持单独使用 Reed-Solomon codes。第二种方案虽然证明和验证流程更简化，但 proof size 比第一种略大。不过，考虑到其带来的实施优势，这样的取舍是完全值得的。

Binius 多项式承诺 主要结合了 小域多项式承诺与扩展域评估、小域通用构造以及 块级编码与 Reed-Solomon 码技术。

• 小域多项式承诺与扩展域评估：在 Binius 协议中，承诺是在 小域 K 上进行多项式承诺，并在更大的 扩展域 L/K 中进行评估。这种方式确保每个多线性多项式 t(X0,...,Xℓ−1) 属于域 K[X0,...,Xℓ−1]，而评估点则可以在扩展域 L 中。这种承诺方案特别设计为小域多项式，能够在扩展域上进行查询，同时保持承诺的安全性和效率。

• 小域通用构造：通过定义参数 ℓ、域 K 及其相关线性块码 C，小域通用构造确保扩展域 L 足够大，以支持安全的评估。协议通过扩展域的特性和线性块码来编码多项式，提升安全性，同时保持计算效率，确保承诺的稳健性。

• 块级编码与 Reed-Solomon 码：对于比线性块码字母表更小的多项式，Binius 提出了 块级编码方案。这个方案使得即便在小域（如 F2）中定义的多项式，也能借助如 F216 这样的较大字母表的 Reed-Solomon 码 进行高效承诺。选择 Reed-Solomon 码是因为其高效性和最大距离分离特性。该方案通过将消息打包并逐行编码，再利用 Merkle 树 进行承诺，简化了操作复杂度。块级编码让小域多项式的高效承诺变得可能，同时避免了与大域相关的高计算开销，确保在 F2 等小域中承诺多项式时的计算效率。

优化思考

为了进一步提升 Binius 协议 的性能，本文提出了四个关键优化点： 1. GKR驱动的PIOP： 这个基于GKR协议的方案，直接替代了Binius论文中的Lasso Lookup算法，二进制域乘法变得轻松许多，承诺开销大幅下降，真是太赞了！🎉

2. ZeroCheck PIOP优化： 通过在Prover和Verifier之间的精妙计算权衡，ZeroCheck操作更高效，感觉就像在跑步时找到了最佳的节奏。🏃‍♂️

3. Sumcheck PIOP优化： 针对小域的Sumcheck进行优化，让小域上的计算负担减轻，简直像是给小家伙们减轻了背包的重量。👜

4. PCS优化： 利用FRI-Binius的优化策略，证明大小下降，协议性能整体提升，像给系统打了一针强心剂。💪

3.1 GKR驱动的PIOP：二进制域乘法

Binius论文提出了一种基于lookup的方案，目标是实现高效的二进制域乘法运算。通过对Lasso lookup argument的改编，这个算法依赖于lookups和加法操作之间的线性关系，而这又与单个word里的limbs数量成正比。尽管这个算法在某种程度上优化了乘法，但辅助承诺的需求仍与limbs数量线性相关。

GKR（Goldwasser-Kalai-Rothblum）协议的核心思想是，证明方（P）和验证方（V）围绕有限域F上的分层算术电路达成一致。电路中的每个节点都有两个输入，用于计算所需的函数。为了降低验证方的计算复杂度，协议使用SumCheck协议，将关于电路输出门值的声明逐步简化为更低层的门值声明，直到最终简化为关于输入的声明。这样一来，验证方只需检查电路输入的正确性，轻松应对！😎 基于 GKR 的整数乘法运算算法，通过将“检查 2 个 32-bit 整数 A 和 B 是否满足 A·B =? C”，转变为“检查中 (gA)B =? gC 是否成立”，利用 GKR 协议极大压缩承诺开销。相比于之前的 Binius lookup 方案，基于 GKR 的二进制域乘法运算仅需一个辅助承诺，并且通过减轻 Sumchecks 的开销，使得该算法更为高效，特别是在 Sumchecks 操作比承诺生成更便宜的情况下。随着 Binius 的优化深入，基于 GKR 的乘法运算逐渐成为降低二进制域多项式承诺开销的有效方式。

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

论文《Some Improvements for the PIOP for ZeroCheck》探讨了证明方（P）和验证方（V）之间工作量的重新分配，提出了多种优化策略以实现开销的权衡。这项工作研究了不同的 k 值配置，使得在证明方和验证方之间达成了成本效率，尤其是在减少数据传输和降低计算复杂度方面。

😎减少证明方的数据传输： 通过将部分任务转移给验证方 V，降低证明方 P 的数据发送量。在第 i 轮中，证明方 P 需向验证方 V 发送 vi+1(X)，其中 X=0,...,d + 1。验证方 V 验证数据正确性时检查以下等式：

vi = vi+1(0) + vi+1(1)。

优化办法：证明方 P 可以不发送 vi+1(1)，而是让验证方 V 自行计算：

vi+1(1) = vi − vi+1(0)。

此外，在第 0 轮时，诚实的证明方 P 总是发送 v1(0) = v1(1) = 0，这意味着无需进行任何评估计算，从而显著降低计算和传输成本，降低至 d2n−1CF + (d + 1)2n−1CG。

👾减少证明方评估点的数量： 在协议的第 i 轮中，验证者在之前的 i 轮中已经发送了一个值序列 r =(r0,...,ri−1)。当前协议要求证明者 (P) 发送多项式。 微小发报道：
优化方程：

• vi+1(X) = ∑ δˆn(α,(r,X,x))C(r,X,x).x∈H −−1

优化方法：

• 证明者 P 提供了这两个函数之间的关系：

  • vi(X) = vi′(X)·δi+1((α0,...,αi),(r,X))

• 这里，δˆi+1 是完全已知的，因为验证者掌握了 α 和 r。这个改进的亮点在于 vi′(X) 的次数比 vi(X) 少了 1，这意味着证明者需要评估的点大大减少。因此，主要的协议变化集中在轮次之间的检查过程。

• 此外，约束条件由原来的 vi = vi+1(0)+vi+1(1) 优化为：

  • (1−αi)vi′+1(0)+αivi′+1(1) = vi′(X)

• 这样，证明者需要评估和发送的数据量进一步减少，从而降低了传输数据的负担。计算 δˆn−i−1 的效率也高于 δˆn。通过这两项改进，成本大幅降低到约：

  • 2n−1(d− 1)CF + 2n−1dCG

• 在常见的 d=3 情况下，这些优化使成本降低了 5/3 倍。

代数插值优化：

• 对于诚实的证明者，C(x0,...,xn−1) 在 Hn 上为零，可以表示为：
  • C(x0,...,xn-1)= ∑xi(xi-1)Qi(x0,...,xn-1)
• 虽然 Qi 不是唯一的，但可以通过多项式长除法构造有序分解：从 Rn=C 开始，逐步除以 xi(xi−1) 来计算 Qi 和 Ri，其中 R0 是 C 在 Hn 上的多线性扩展，假设其为零。
• 分析 Qi 的次数，得到：对于 j> i，Qj 在 xi 上的次数与 C 相同；对于 j = i，次数减少 2；对于 j < i，次数最多为 1。
• 给定向量 r = (r0,...,ri)，Qj(r,X) 对于所有 j ≤ i 都是多线性的。
• 此外，1) Qj(r,X) 是与 C(r,X) 在 Hn−i 上相等的唯一多线性多项式。对于任何 X 和 x ∈ Hn−i−1，可以表示为：
  • C(r,X,x) − Qi(r,X,x) = X(X − 1)Qi+1(r,X,x)
• 因此，在协议的每一轮中，只需引入一个新的 Q，其评估值可以从 C 和先前的 Q 计算得出，实现插值优化。

微小发报道：3.3 Sumcheck PIOP 优化：基于小域的 Sumcheck 协议 微小发报道：Binius 的 STARKs 方案，承诺低开销，让 prover 瓶颈不再是 PCS，而是 sum-check 协议。Ingonyama 在 2024 年提出了对小域 Sumcheck 协议的改进（见图 2 中的 Algo3 和 Algo4），并开源了实现代码。算法 4 结合了 Karatsuba 算法到算法 3 中，以额外的基域乘法为代价，减少扩域乘法次数，适合扩域乘法成本远高于基域乘法的情况，从而提升性能。

🔄 切换轮次的影响与改进因子

小域 Sumcheck 协议的改进专注于切换轮次 t 的选择。切换轮次是指从优化算法切换回朴素算法的时机。实验结果显示，最佳切换点时，改进因子最大，之后呈抛物线趋势。如果超过这一点，优化算法的优势减弱，效率下降。小域的基域乘法与扩域乘法相比，时间比率更高，因此及时切换回朴素算法至关重要。

在 Cubic Sumcheck（d = 3）应用中，小域的 Sumcheck 协议相比朴素算法提升了一个数量级。在基域为 GF[2] 时，算法 4 的性能几乎比朴素算法高出 30 倍。

📏 基域大小对性能的影响

研究结果显示，较小的基域（如 GF[2]）使优化算法的优势更为明显。这是由于在较小基域下，扩展域与基域乘法的时间比率更高，优化算法表现出更高的改进因子。

⚡ Karatsuba 算法的优化收益

Karatsuba 算法在提升小域 Sumcheck 性能上效果显著。对于基域 GF[2]，算法 3 和算法 4 的峰值改进因子分别为 6 和 30，显示算法 4 比算法 3 高效五倍。Karatsuba 优化不仅提高了运行效率，还优化了算法的切换点，分别在算法 3 的 t=5 和算法 4 的 t=8 达到最佳。

💾 内存效率的提升 基于小域的 Sumcheck 协议，不仅让运行时间变得更快，还在内存使用上大放异彩✨。算法 4 的内存需求为 O(d·t)，而算法 3 则需要 O(2d·t)。比如，当 t=8 时，算法 4 仅需 0.26MB，反观算法 3 竟然要 67MB 来存储基域的乘积！这让算法 4 在内存有限的设备上展现了超强的适应性，特别适合那些资源紧张的客户端证明环境。

3.4 pcs 优化：fri-binius 降低 binius proof size

binius 协议有个显著的缺点，就是证明大小偏大，随着见证大小的平方根按 O(√N) 增长。这种平方根大小的证明和更高效的系统相比，简直是个短板💔。与之对比，对数级（polylogarithmic）的证明大小对于实现真正的“简洁”验证器至关重要，这在像 plonky3 这些先进系统中得到了验证，借助 FRI 等黑科技实现了对数级证明。

论文《Polylogarithmic Proofs for Multilinears over Binary Towers》，简称为 fri-binius，成功实现了二进制域 FRI 折叠机制，带来了四大创新：

• · 扁平化多项式：把原始的多线性多项式转为 LCH（低码高度）新颖多项式基。

• · 子空间消失多项式：在系数域上执行 FRI，并通过加性 NTT（数论变换）实现类似 FFT 的分解。

• · 代数基打包：支持协议中信息的高效打包，去除了嵌入开销。

• · 环交换 sumcheck：一种新颖的 sumcheck 方法，利用环交换技术来提升性能。

基于二进制域的 fri-binius 多线性多项式承诺方案（pcs）核心思想是：fri-binius 协议通过将初始的二进制域多线性多项式（定义于 F2 上）打包为在更大域 K 上定义的多线性多项式来运作。

在基于二进制域的 fri-binius pcs 中，过程如下： · 承诺阶段： 对一个ℓ变量的多线性多项式（在 F2 上定义）进行承诺，结果转化为对一个打包后的ℓ′变量多线性多项式（在 F2128 上定义）的承诺，系数数量因此减少了整整 128 倍。

· 评估阶段： 证明方与验证方通过ℓ′轮交叉环切换的 SumCheck 和 FRI 交互证明（IOPP）进行协作：

– FRI 开放证明占据了证明体积的大部分。

– 证明方的 SumCheck 成本与常规大域的 SumCheck 成本相当。

– 证明方的 FRI 成本也与常规大域相同。

– 验证方需要接收来自 F2128 的 128 个元素，并执行 128 次额外的乘法运算。

利用 FRI-Binius，Binius 的证明大小可以减少一个数量级。这一改变让 Binius 的证明规模更接近最先进的系统，同时依然兼容二进制域。特别为二进制域设计的 FRI 折叠技术，结合代数打包和 SumCheck 的优化，使得 Binius 在保持高效验证的同时，生成更加简洁的证明。

表 2: Binius vs. FRI-Binius 证明大小

表 3: Plonky3 FRI vs. FRI-Binius

4 小结

Binius 的核心价值在于为 witnesses 使用最小的 power-of-two 域，因此可以根据实际需要选择域的大小。Binius 是一个“结合硬件、软件与 FPGA 加速的 Sumcheck 协议”的协同设计方案，能够在非常低的内存使用率下快速生成证明。像 Halo2 和 Plonky3 这样的证明系统有 4 个关键步骤占用了大部分计算资源：生成 witness 数据、对 witness 数据进行承诺、vanishingargument 和 openingproof。以 Plonky3 中的 Keccak 和 Binius 中的 Grøstl 哈希函数为例，以上 4 个关键步骤的计算量占比如图 3 所示：

图 3: 更小的承诺成本 可见，Binius 已经有效解决了 Prover 的 commit 承诺瓶颈，现在的挑战转移至 Sumcheck 协议。在这个协议中，大量的多项式评估和域乘法问题，能够通过 专用硬件 实现高效处理。FRI-Binius 方案作为 FRI 的一种变体，提供了一个超级吸引人的选择——它能够从域证明层中剔除嵌入开销，同时不会让聚合证明层的成本飙升。目前，Irreducible 团队正在开发递归层，并已与 Polygon 团队 联手建设基于 Binius 的 zkVM；JoltzkVM 则正从 Lasso 转向 Binius，以提升递归性能；Ingonyama 团队也在实现 Binius 的 FPGA 版本。