在许多依赖多项式承诺的零知识证明系统当中，使用了不同的承诺协议。根据 a16z 的 Justin Thaler 在 2022 年 8 月文章「Measuring SNARK performance: Frontends, backends, and the future」的评估，Brakedown 虽然有较大的 Proof Size，但是无疑是当下最快的多项式承诺协议。0 Q% B# }* J7 c

5 z: d+ s; i- k& T& G' B# vFRI、KZG、Bulletproof 是更为常见的多项式承诺协议，但速度是它们的瓶颈。zkSync 采用的 Plonky、Polygon zkEVM 采用的 Plonky2、Scroll 采用的 Ultra-Plonk 等算法都是基于 KZG 的多项式承诺。Prover 涉及到大量的 FFT 计算和 MSM 运算生成多项式和承诺，这两者都会带来大量的计算负担。 虽然 MSM 有运行多线程加速的潜力，但需要大量内存，即使在高并行下也很慢，而大型 FFT 则严重依赖算法运行时数据的频繁洗牌，难以通过分布式加速跨计算集群加载。
# Q1 O7 C* `4 G$ ]" G' }( v/ @7 a/ X, R, u- |) u3 o
正是由于有了更为快速的多项式承诺协议 Brakedown，才使这类运算的复杂度大幅降低。, `% Z% x' t$ q3 }5 u" e
- R! J( x9 x) X) R6 S+ P6 {/ r2 Y
FOAKS 即 Fast Objective Argument of Knowledges，是由 Fox Tech 提出的一种基于 Brakedown 的零知识证明系统框架。FOAKS 在 Orion 的基础上进一步减少 FFT 运算，目标是最终消除 FFT。此外，FOAKS 还设计出一种全新的非常精妙的证明递归方式来减少证明大小。FOAKS 框架的优势在于在实现线性证明时间的基础上有着较小的证明大小，非常适合应用于 zkRollup 场景当中。& L# b" Q; M( Z# w: p* H8 t- i

7 s6 Y4 D  A) J, g( j6 O下文我们将详细介绍 FOAKS 所使用的多项式承诺协议 Brakedown。
) Z1 _* D/ j) w- Y: d& q- h6 K& u) V6 l) V. l/ f& `
在密码学当中，承诺（Commitment）协议由证明者（Prover）对某一个秘密值进行承诺，生成一个公开的承诺值，这个承诺值具有绑定性（Binding）和隐藏性（Hiding），之后提交者需要打开此承诺并将消息发送到验证者，以验证承诺与消息之间的对应关系。这一点，使得承诺协议和哈希函数的作用有许多共通之处，但是承诺协议往往依赖于公钥密码学领域的数学结构。而多项式承诺（Polynomial Commitment）是一类对于多项式的承诺方案，也就是说被承诺值是多项式。而同时多项式承诺协议当中还包含了在给定的点取值并给出证明的算法，这就使得多项式承诺协议本身成为一类重要的密码学协议，是许多零知识证明系统的核心部分。
8 i. E) E& ^% e$ @3 k% p  w5 d" i. w* ?. Q+ `
而在最新的密码学领域的研究当中，由于发现了张量积（Tensor Product）和多项式取值之间的联系，所以诞生了一系列与此相关的多项式承诺协议，Brakedown 是其中的代表性协议。" H. {- m" @% v& v/ `
$ S$ ~$ m( ?$ M# {- S
在详细介绍 Brakedown 的协议细节之前，需要先了解一些基础知识。我们需要先了解线性码（Linear Code）、抗碰撞哈希函数（Hash Function）、默克尔树（Merkle Tree）、张量积（Tensor Product）的运算以及多项式取值的张量积表示。$ m* I2 X6 j: a* M  j6 U- T1 E$ r

: l4 K  v2 I; I3 {0 |2 l2 [首先是线性码（Linear Code）。一个消息长度为 k，码字长度为 n 的线性码是一个线性子空间* ]5 h- C7 U5 ?( y% ?4 a3 G
% _8 Y: q  m% ?' G  Y) r# U