深度解析FOAKS当中的多项式承诺协议Brakedown

图 1：默克尔树（Merkle Tree）

我们还需要了解张量积（Tensor Product）的运算是怎么做的。数学上，张量是向量和矩阵向高维空间的扩展，是很重要的研究对象，详细的讨论张量超出本文的研究范畴，这里只介绍向量和矩阵的张量积运算。

图 2：向量和矩阵的张量积运算

紧接着，我们需要知道多项式取值的张量积表示。

[GLS+] 当中提到，多项式的取值可以被表示成张量积的形式。在这里我们考虑多线性多项式的承诺。

具体来讲，给定一个多项式，他在向量 x0,x1,...,xlogN-1 的取值可以写成：

根据多线性的定义，每一个变量的次数是 0 或 1，因此，这里有 N 个单项式和系数，以及 logN 个变量。令

，其中 i0i1...ilogN-1 是 i 的二进制表示。令 w 表示多项式系数，

。同样的，定义

。令

于是有 X=r0r1。

从而，多项式取值可以被表示成张量积的形式：(x0,x1,...,xlogN-1)=

最后，我们来看 FOAKS、Orion[XZS22] 当中使用的 Brakedown 的过程。

首先，PC.Commit 将多项式系数 w 划分成 kk 的矩阵形式，并将其编码（参考「预备知识」中的线性码），记作 C2。之后对于 C2 的每一列 C2[:,i] 进行承诺建立一个默克尔树，然后再对于每一个列形成的默克尔树树根建立另一个默克尔树，作为最终的承诺。

在取值证明的计算中，需要证明两点，一是近似性（Proximity），二是一致性（Consistency）。近似性保证了承诺的矩阵确实和编码后的一个码字足够接近。一致性保证 y=

近似性检验：近似性检验由两步组成。首先，验证者发送一个随机向量 0 给证明者，证明者计算 Y0 与 C1 的内积，也就是以 Y0 的分量为系数对 C1 的行计算线性组合。由于线性码的性质，Cy0 是 Yy0 的码字。之后，证明者证明 Cy0 确实是从被承诺的码字计算出的。为了证明这一点，验证者随机选取 t 列，证明者打开对应的列并提供默克尔树证明。验证者检查这些列和 Y0 的内积和 Cy0 当中对应位置相等。[BCG20] 当中证明如果使用的线性码有常数的相对距离，那么被承诺的矩阵就以压倒性的概率与一个码字接近（压倒性的概率是指，命题的否命题成立的概率是可忽略的）。

一致性检验：一致性检验和近似性检验的流程完全类似。不同之处在于，不使用随机向量 Y0 而是直接使用 r0 来完成线性组合的部分。类似的，c1 也是消息 y1 的一个线性码，并且有

(x)=。[BCG20] 当中证明，通过一致性检验，如果被承诺的矩阵与一个码字接近，则以压倒性概率成立 y=(x)。

以伪代码形式，我们给出 Brakedown 协议的流程：

Public input：The evaluation point X，parsed as a tensor product X=r0r1;

Private input：The polynomial，the coefficient of is denoted by w.

Let C be the [n,k,d]-limear code，EC：FkFn be the encoding function，N=kk. If N is not a perfect square，we can pad it to the next perfect square. We use a python style notationmat[:,i] to select the i-th column of a matrix mat。

1、function PC. Commit()：

2、Parse w as a kk matrix. The prover locally computes the tensor code encoding C1，C2，C1 is a kn matrix，C2 is a nn matrix.

3、for i [n] do

4、Compute the Merkle tree root Roott=Merkle.Commit(C2[:,i])

5、Compute a Merkle tree root R=Merkle.Commit([Root0,......Rootn-1]),and output R as the commitment.

6、function PC. Prover(, X, R)

7、The prover receives a random vector Y0Fk from the verifier

8、Proximity

9、Consistency

10、Prover sends C1,y1,C0,y0 to the verifier.

11、Verifier randomly samples t[n] as an array and send it to prover

12、for idx do

13、Prover sends C1 [:,idx] and the Merkle tree proof of Rootidx for C2 [:,idx] under R to verifier

14、function PC. VERIFY_EVAL(X,X,y=(X),R)

15、Proximity: idx,CY0[idx]==and EC(Yy0)==CY0

16、Consistency:idx,C1[idx]==and EC(Y1)==C1

17、y==

18、idx, EC(C1[:,idx]) is consistent with ROOTidx, and ROOTidx』s Merkle tree proof is valid.

19、Output accept if all conditions above holds. Otherwise output reject.

结语：多项式承诺是一类非常重要的密码学协议，被广泛的应用在许多密码学系统当中，尤其是零知识证明系统。本文详细介绍了多项式承诺 Brakedown 协议以及和其相关的数学知识，作为 FOAKS 很重要的底层组件，Brakedown 对 FOAKS 的实例化性能的提升起到了重要作用。

参考文献

[GLS+]:Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. Brakedown: Linear-time and post-quantum snarks for r1cs. Cryptology ePrint Archive. https://ia.cr/2021/1043.

[XZS22]:Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]//Advances in Cryptology–

CRYPTO 2022: 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15–18, 2022, Proceedings, Part IV. Cham: Springer Nature Switzerland, 2022: 299-328.https://eprint.iacr.org/2022/1010

[BCG20]:Bootle, Jonathan, Alessandro Chiesa, and Jens Groth. "Linear-time arguments with sublinear verification from tensor codes." Theory of Cryptography: 18th International Conference, TCC 2020, Durham, NC, USA, November 16–19, 2020, Proceedings, Part II 18. Springer International Publishing, 2020.

Justin Thaler from A16zcrypto, Measuring SNARK performance: Frontends, backends, and the future

https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

张量积的介绍：https://blog.csdn.net/chenxy_bwave/article/details/127288938

本文来自投稿，不代表律动 BlockBeats 观点。