A Comprehensive Understanding of the Polynomial Commitment Protocol in FOAKS Brakedown

Written by: Fox Tech CEO Kang Shuiyue, Fox Tech Chief Scientist Meng Xuanji

Introduction: If cryptographers had not discovered the connection between Tensor Product and polynomial evaluation, it would have been difficult to develop the polynomial commitment protocol Brakedown, and thus, new fast algorithms like Orion and FOAKS based on Brakedown would not have emerged.

In many zero-knowledge proof systems that rely on polynomial commitments, different commitment protocols are used. According to a16z's Justin Thaler in his August 2022 article "Measuring SNARK performance: Frontends, backends, and the future," Brakedown, despite having a large Proof Size, is undoubtedly the fastest polynomial commitment protocol currently available.

FRI, KZG, and Bulletproof are more common polynomial commitment protocols, but speed is their bottleneck. Algorithms like Plonky used by zkSync, Plonky2 used by Polygon zkEVM, and Ultra-Plonk used by Scroll are all based on KZG polynomial commitments. Prover involves a large number of FFT calculations and MSM operations to generate polynomials and commitments, both of which impose a significant computational burden. Although MSM has the potential for multi-threaded acceleration, it requires a lot of memory and is slow even under high parallelism, while large FFTs heavily rely on frequent shuffling of runtime data, making it difficult to achieve distributed acceleration across computing clusters.

It is precisely because of the faster polynomial commitment protocol Brakedown that the complexity of such computations has been significantly reduced.

FOAKS, or Fast Objective Argument of Knowledge, is a zero-knowledge proof system framework based on Brakedown proposed by Fox Tech. FOAKS further reduces FFT computations based on Orion, aiming to ultimately eliminate FFT. Additionally, FOAKS has designed a new and ingenious proof recursion method to reduce proof size. The advantage of the FOAKS framework lies in achieving a small proof size while maintaining linear proof time, making it very suitable for zkRollup scenarios.

In the following text, we will detail the polynomial commitment protocol Brakedown used by FOAKS.

In cryptography, a commitment protocol involves a prover committing to a secret value, generating a public commitment value that has binding and hiding properties. The committer then needs to open this commitment and send the message to the verifier to validate the correspondence between the commitment and the message. This aspect makes commitment protocols and hash functions share many similarities, but commitment protocols often rely on mathematical structures from public-key cryptography. Polynomial Commitment is a type of commitment scheme for polynomials, meaning the committed value is a polynomial. Moreover, polynomial commitment protocols also include algorithms for evaluating at given points and providing proofs, making polynomial commitment protocols an important class of cryptographic protocols and a core part of many zero-knowledge proof systems.

In the latest research in cryptography, a series of polynomial commitment protocols related to the connection between Tensor Product and polynomial evaluation have emerged, with Brakedown being a representative protocol.

Before detailing the protocol specifics of Brakedown, some foundational knowledge needs to be understood. We first need to understand Linear Code, Hash Function, Merkle Tree, the operations of Tensor Product, and the tensor product representation of polynomial evaluation.

First, let's discuss Linear Code. A linear code with message length k and codeword length n is a linear subspace CFn, such that there exists an injective mapping from messages to codewords, called encoding, denoted as EC: Fk → Fn. Any linear combination of codewords is still a codeword. The distance between two codewords u and v is their Hamming distance, denoted as (u,v). The minimum distance is d = min{u,v}(u,v). Such a code is denoted as [n,k,d] linear code, with d_n representing the relative distance of the code.

Next, we discuss Hash Function and Merkle Tree.

Using H: {0,1}^2 → {0,1} to represent a hash function. A Merkle Tree is a special data structure that can commit to 2^d messages, generating a hash value h, and requires d+1 hash values to open any message.

A Merkle Tree can be represented as a binary tree of depth d, where L message elements m1, m2, …, ml correspond to the leaves of the tree. Each internal node of the tree is computed by hashing its two child nodes. To open message mi, the path from m_i to the root node needs to be revealed.

Using the following notation:

1. hMerkle.Commit(m1,…,m_l)

2. (m_i,i)Merkle.Open(m,i)

3. {0,1}Merkle.Verify(i,m_i,h)

Figure 1: Merkle Tree

We also need to understand how the operation of Tensor Product is performed. Mathematically, a tensor is an extension of vectors and matrices to higher-dimensional spaces and is an important object of study. A detailed discussion of tensors exceeds the scope of this article; here we only introduce the tensor product operation for vectors and matrices.

Figure 2: Tensor Product Operation of Vectors and Matrices

Next, we need to know the tensor product representation of polynomial evaluation.
As mentioned in [GLS+], the evaluation of a polynomial can be represented in the form of a tensor product. Here we consider the commitment of multilinear polynomials.

Specifically, given a polynomial, its evaluation at vectors x0, x1, …, x_{logN-1} can be written as:

(x0,x1,…,x{logN-1}) = Σ{i0=0}^{1} Σ{i1=0}^{1} … Σ{i{logN-1}=0}^{1} w{i0 i1 … i{logN-1}} x0^{i0} x1^{i1} … x{logN-1}^{i_{logN-1}}

According to the definition of multilinearity, each variable has a degree of 0 or 1, so there are N monomials and coefficients, as well as logN variables. Let i = j = 0, logN-1, where i0 i1 … i{logN-1} is the binary representation of i. Let w represent the polynomial coefficients, w[i] = w{i0 i1 … i{logN-1}}. Similarly, define Xi = x0^{i0} x1^{i1} … x{logN-1}^{i{logN-1}}. Let k = N, r0 = {X0, X1, …, X{k-1}}, r1 = {X0^k, X1^k, …, X{k-1}^k}. Thus, we have X = r0 r1.

Therefore, polynomial evaluation can be represented in the form of a tensor product: (x0,x1,…,x{logN-1}) = ⟨w,r0 r_1⟩.

Finally, let's look at the process of Brakedown used in FOAKS and Orion [XZS22].

First, PC.Commit divides the polynomial coefficients w into a k x k matrix form and encodes it (refer to "Preliminary Knowledge" for linear codes), denoted as C2. Then, for each column C2[:,i], a Merkle tree commitment is established, and another Merkle tree is created for the roots of each column's Merkle tree, serving as the final commitment.

In the computation of the evaluation proof, two points need to be proven: proximity and consistency. Proximity ensures that the committed matrix is indeed close enough to an encoded codeword. Consistency ensures that y = ⟨w,r0 r1⟩.

Proximity Check: The proximity check consists of two steps. First, the verifier sends a random vector 0 to the prover, who computes the inner product of 0 with C1, which is a linear combination of the rows of C1 weighted by the components of 0. Due to the properties of linear codes, C0 is a codeword of y0. Then, the prover proves that C0 is indeed computed from the committed codeword. To prove this, the verifier randomly selects t columns, and the prover opens the corresponding columns and provides Merkle tree proofs. The verifier checks that the inner products of these columns with 0 are equal to the corresponding positions in C0. [BCG20] proves that if the linear code used has a constant relative distance, then the committed matrix is overwhelmingly likely to be close to a codeword (overwhelmingly likely means that the probability of the negation of the proposition is negligible).

Consistency Check: The consistency check follows a process similar to the proximity check. The difference is that instead of using a random vector 0, r0 is directly used to complete the linear combination part. Similarly, C1 is also a linear code of message y1, and has (x) = ⟨y1,r_1⟩. [BCG20] proves that through the consistency check, if the committed matrix is close to a codeword, then y = (x) holds with overwhelming probability.

In pseudocode form, we present the process of the Brakedown protocol:

Public input: The evaluation point X, parsed as a tensor product X = r0 r1;

Private input: The polynomial, the coefficient of which is denoted by w.

Let C be the [n,k,d]-linear code, EC: Fk → Fn be the encoding function, N = k^k. If N is not a perfect square, we can pad it to the next perfect square. We use a Python-style notation mat[:,i] to select the i-th column of a matrix mat.

1. function PC.Commit():

2. Parse w as a k x k matrix. The prover locally computes the tensor code encoding C1, C2, where C1 is a k x n matrix, and C2 is an n x n matrix.

3. for i in [n] do

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

5. Compute a Merkle tree root R = Merkle.Commit([Root0,……Root{n-1}]), and output R as the commitment.

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

7. The prover receives a random vector 0 ∈ F_k from the verifier.

8. Proximity: C0 = Σ{i=0}^{k-1} 0[i] C1[:,i], y0 = Σ_{i=0}^{k-1} 0[i] w[i]

9. Consistency: C1 = Σ{i=0}^{k-1} r0[i] C1[:,i], y1 = Σ{i=0}^{k-1} r_0[i] w[i]

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

11. Verifier randomly samples t ∈ [n] as an array I and sends it to the prover.

12. for idx in I do

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

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

15. Proximity: idx in I, C0[idx] == ⟨0,C1[:,idx]⟩ and EC(y0) == C0

16. Consistency: idx in I, C1[idx] == ⟨r0,C1[:,idx]⟩ and EC(y1) == C_1

17. y == ⟨r1, y1⟩

18. idx in I, EC(C1[:,idx]) is consistent with ROOTidx, and ROOT_idx's Merkle tree proof is valid.

19. Output accept if all conditions above hold. Otherwise, output reject.

Conclusion: Polynomial commitment is a very important cryptographic protocol, widely used in many cryptographic systems, especially zero-knowledge proof systems. This article provides a detailed introduction to the polynomial commitment Brakedown protocol and its related mathematical knowledge. As a crucial underlying component of FOAKS, Brakedown plays an important role in enhancing the instantiation performance of FOAKS.

References

1. [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.

2. [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

3. [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.

4. Justin Thaler from A16zcrypto, Measuring SNARK performance: Frontends, backends, and the future
   https://a16zcrypto.com/measuring-snark-performance-frontends-backends-and-the-future/

5. Introduction to Tensor Product: https://blog.csdn.net/chenxy_bwave/article/details/127288938