Brakedown

This document aims to intuitively explain the goals and processes of the Brakedown protocol.

Introduction

Brakedown originates from the question, "How can we generate proofs for R1CS as quickly as possible?" It presents a scheme that achieves proof generation with $O(N)$ field operations. To accomplish this, it introduces a method of encoding that operates in linear time. While similar techniques were used in BCG, Brakedown distinguishes itself by being more practical. Additionally, it does not require a trusted setup, may offer quantum resistance, and is field-agnostic, making it more practical.

Background

See LinearCode for more details.

Why use Merkle Tree operations?

When committing to an $O(N)$-length vector, the operations involved generally have the following complexities:

• FFT Operations → $O(N \cdot \log N)$ field operations

• Merkle Tree Operations → $O(N)$ hash operations

• MSM Operations → Using Pippenger's algorithm, $O(N \cdot \lambda / \log(N \cdot \lambda))$ group operations

To achieve $O(N)$, FFT operations, which are $O(N \cdot \log N)$, cannot be used. Similarly, MSM operations are avoided because group operations are slower than field operations. Instead, Merkle Tree operations are utilized for commitment.

The traditional encoding function used in RS-codes involves FFT operations. However, due to the limitations mentioned earlier, alternative encoding methods must be explored.

Tensor Product

The Tensor Product is an operation that generates all possible combinations of two vectors v and u from different vector spaces. For example, if $\bm{q_1} = [a, b]$ and $\bm{q_2} = [x, y, z]$, the tensor product between the two is the following matrix:

$$\bm{q_1} \otimes \bm{q_2} = \begin{bmatrix} a \cdot x & a \cdot y & a \cdot z \\ b \cdot x & b \cdot y & b \cdot z \end{bmatrix}$$

Additionally, the tensor product can be used to express a Multi Linear Extension (MLE) evaluation like so:

$$\text{Given an evaluation point } \bm{r} \in \mathbb{F}^l\text{ and }z \in \mathbb{F}^{2^l} \\ \begin{align*} g(\bm{r}) &= \langle \otimes_{i=1}^{l} (r_1, 1 - r_1), z\rangle \\ &= \langle(r_1, 1 - r_1) \otimes\cdots\otimes(r_l, 1 - r_l), z\rangle \end{align*}$$

For example, when $l = 2$, the MLE evaluation is calculated as follows:

$$\begin{align*} g(\bm{r}) &= \mathsf{eq}((0, 0), \bm{r}) \cdot z_1 + \mathsf{eq}((0, 1), \bm{r}) \cdot z_2 + \mathsf{eq}((1, 0), \bm{r}) \cdot z_3 + \mathsf{eq}((1, 1), \bm{r}) \cdot z_4 \\ &= (1 - r_1)\cdot(1- r_2)\cdot z_1 + (1 - r_1)\cdot r_2\cdot z_2 + r_1\cdot(1- r_2)\cdot z_3 + r_1 \cdot r_2\cdot z_4 \\ &= \langle((r_1, 1-r_1) \otimes (r_2, 1-r_2)), (z_1, z_2, z_3, z_4)\rangle \\ &= \langle((r_1, 1-r_1) \otimes (r_2, 1-r_2)), z)\rangle \end{align*}$$

Protocol Explanation

Brief Overview

The protocol is divided into three phases: Commitment Phase, Testing Phase and Evaluation Phase.

Commitment Phase

This phase commits to the input matrix, with the following steps:

1. Each matrix $\bm{u}$ is provided as an input, where $\bm{u_i}$ represents the $i$-th row.

$$\bm{u}= \{ \bm{u_i} \}_{i \in [r]} \in (\mathbb{F}^c)^r$$

1. For a given rate $\rho$, each row of length $c$ is encoded into a row of length $N$, producing an $r \times N$ matrix $\bm{\hat{u}}$. The prover commits this $\bm{\hat{u}}$ matrix to the verifier using Merkle hash.

   

$$\bm{\hat{u}}= \{\mathsf{Enc}(\bm{u_i})\}_{i \in [r]} \in (\mathbb{F}^N)^r$$

Testing Phase

This phase verifies whether the encoding was performed correctly, with the following steps:

1. The verifier samples a random scalar $\alpha$ and sends it to the prover.

2. The prover computes $\bm{u'}$ using the random value $\alpha$ and sends it to the verifier:

   

$$\bm{u'} = \mathsf{RLC}(\bm{u}) = \sum_{i=1}^r\alpha^{i-1} \cdot \bm{u_i} \in \mathbb{F}^c$$

1. The verifier tests the following equality by sampling $l$ values between $1$ and $N$:

$$\sum_{i=1}^r\alpha^{i-1} \cdot \bm{\hat{u}_i} \stackrel{?}= \mathsf{Enc}(\bm{u'})$$

This holds because encoding and random linear combination (RLC) are commutative and the codeword is linear code. That is, encoding the rows of the matrix and then performing RLC is equivalent to performing RLC first and then encoding. According to Section 4, "Concrete Optimizations to the Commitment Scheme," the testing phase can be skipped if a Polynomial Commitment Scheme is used.

Evaluation Phase

This phase performs identical checks as in the testing phase but without encoding, with the following steps:

1. The verifier samples $\bm{q_1} \in \mathbb{F}^r$.

2. The prover computes $\bm{u''}$ and sends it to the verifier: (Identical to Testing Phase 2.)

$$u'' = \sum_{i=1}^rq_{1,i}\cdot u_i \in \mathbb{F}^c$$

1. The verifier tests the following equality by sampling $\bm{q_2} \in \mathbb{F}^c$: (Identical to Testing Phase 3.) Here, tensor product between $\bm{q_1}$ and $\bm{q_2}$ are flattened to the vector.

$$g(\bm{r}) = \langle(\bm{q_1} \otimes \bm{q_2}), \bm{u})\rangle \stackrel{?}= \langle \bm{u''}, \bm{q_2}\rangle$$

For example, when $r = 2$ and $c = 2$, the equation holds due to the following reasoning:

$$\begin{align*} \langle(\bm{q_1} \otimes \bm{q_2}), u\rangle &= q_{1,1}\cdot q_{2,1} \cdot u_{1,1} + q_{1,1}\cdot q_{2,2}\cdot u_{2,1} + q_{1,2}\cdot q_{2,1}\cdot u_{1,2}+ q_{1,2}\cdot q_{2,2}\cdot u_{2,2} \\ &= (q_{1,1}\cdot u_{1,1} + q_{1,2}\cdot u_{1,2})\cdot q_{2,1} + (q_{1,1}\cdot u_{2,1} + q_{1,2} \cdot u_{2,2})\cdot q_{2,2} \\ &= \langle\sum_{i=1}^{2} \bm{q_{1,i}} \cdot u_i, \bm{q_2}\rangle \end{align*}$$

Analysis

The proof generation time depends on the encoding and commitment operations. Since Merkle Tree is used for commitments, as long as encoding is performed in linear time, the overall execution time is $O(N)$.

The proof structure consists of:

• $c$: Fields used in Testing Phase Step 2 and Evaluation Phase Step 3.

• $r\cdot l$: Fields sampled during Testing Phase Step 3 and Evaluation Phase Step 4.

• $\alpha$: Opening proof size required for $l$-queries.

Verification time is $O(r \cdot l)$. While proof generation is fast, the proof size and verification time is directly proportional with $r$.

Linear-time Encoding

The figure above illustrates the linear-time encoding method used in Brakedown. For a given rate $\rho$, $\text{Enc}(\bm{x})$ is a function that generates a vector of length $n \cdot \rho^{-1}$ from an input vector $\bm{x}$ of length $n$. The output is divided into three parts: $(\bm{x}, \bm{z}, \bm{v})$. The encoding $\text{Enc}(\bm{x})$ proceeds as follows:

Vec Enc(Vec x) {
  if (x.size() < 900) {
    // As mentioned in Section 5 of the paper, 
    // the threshold is set at 900. 
    // Quadratic-time operations are acceptable here 
    // since their time contribution is negligible.
    return RSEnc(x);
  }
  // A is a sparse matrix.
  Matrix A = SampleMatrixA();
  CHECK_EQ(A.rows(), x.size());
  CHECK_EQ(A.cols(), kAlpha * x.size());
  Vec y = x * A ;
  Vec z = Enc(y);
  // B is a sparse matrix.
  Matrix B = SampleMatrixB();
  CHECK_EQ(B.rows(), z.size());
  CHECK_EQ(B.cols(), (kRateInv * - 1 - kAlpha * kRateInv) * x.size()); 
  Vec v = z * B;

  return Concatenate(x, z, v);  
}

Properties of the Encoded Output

For the encoded result $\bm{w} = \mathsf{Enc}(\bm{x})$, given the parameter $\beta$, the zero norm $\|\bm{w}\|_0$ and distance $\delta$ are given by:

$$\|\bm{w}\|_0 > \beta n\text{, } \delta = (\beta n) / (n\rho^{-1}) = \beta / r$$

The zero norm, also known as Hamming weight, represents the number of non-zero elements in $\bm{x}$:

$$\|\bm{x}\|_0 = \#\{i \, | \, x_i \neq 0\}$$

The execution time of encoding is proportional to the input vector $\bm{x}$'s length. Proofs related to this encoding method are detailed in Section 5.1 of the paper.

Linear-time Commitments for Sparse Multilinear Polynomials

Using techniques from Spartan, the input vector can be committed in linear time.

Representing the Vector as a Sparse Matrix

For example, the vector can be converted into a matrix as follows. Here, Rows = 4, Cols = 4, Non-zero Elements (N) = 4, Total Elements (M) = 16:

$$[0, 2, 0, 0, 3, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 5] \rightarrow \begin{bmatrix} 0 & 2 & 0 & 0 \\ 3 & 0 & 0 & 0\\ 0 & 0 & 4 & 0\\ 0 & 0 & 0 & 5\\ \end{bmatrix}$$

Simply using a naive polynomial commitment scheme would require a computational complexity of $O(M)$.

Sparse Representation of the Matrix

The sparse representation is defined using $\bm{R}$, $\bm{C}$ and $\bm{V}$ as the following: 1. Each row of $\bm{R}$,$\bm{C}$,$\bm{V}$ defines a single non-zero entry in the sparse matrix.

2. $M_{Rᵢ,Cᵢ}=Vᵢ$

$$\begin{bmatrix} 0 & 2 & 0 & 0 \\ 3 & 0 & 0 & 0\\ 0 & 0 & 4 & 0\\ 0 & 0 & 0 & 5\\ \end{bmatrix} \rightarrow \bm{R} = \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \\ \end{bmatrix}, \bm{C} = \begin{bmatrix} 1 \\ 0 \\ 2 \\ 3 \\ \end{bmatrix}, \bm{V} = \begin{bmatrix} 2 \\ 3 \\ 4 \\ 5 \\ \end{bmatrix}$$

Defining Sparse Polynomial D

The sparse polynomial $D$ is defined as:

$$D(\bm{r_x}, \bm{r_y}) = \sum_{\bm{k} = \{0,1\}^{\log N}} \mathsf{val}(\bm{k})\cdot \widetilde{\mathsf{eq}}(b^{-1}(\mathsf{row}(\bm{k})), \bm{r_x})\cdot \widetilde{\mathsf{eq}}(b^{-1}(\text{col}(\bm{k})), \bm{r_y}), \\ \text{where }\mathsf{val}(\bm{k}) = V_k, \mathsf{row}(\bm{k}) = R_k, \mathsf{col}(\bm{k}) = C_k, \\ b^{-1}: \text{canonical injection from }\mathbb{F} \text{ to } \{0, 1\}^{\log M}, \\ \widetilde{\mathsf{eq}}(\bm{x}, \bm{y}) = \begin{cases} 1,& \text{if } \bm{x} = \bm{y}\\ 0,& \text{otherwise} \end{cases}$$

Here is an example calculation of $\text{row}$, $\text{col}$, $\text{val}$ and $b^{-1}$ based on the previous example of a sparse matrix.

$$\mathsf{row}((0, 0)) = 0, \mathsf{row}((0, 1)) = 1, \mathsf{row}((1, 0)) = 2, \mathsf{row}((1, 1)) = 3 \\ \mathsf{col}((0, 0)) = 1, \mathsf{col}((0, 1)) = 0, \mathsf{col}((1, 0)) = 2, \mathsf{col}((1, 1)) = 3 \\ \mathsf{val}((0, 0)) = 2, \mathsf{val}((0, 1)) = 3, \mathsf{val}((1, 0)) = 4, \mathsf{val}((1, 1)) =5 \\ b^{-1}(0) = (0, 0), b^{-1}(1) = (0, 1), b^{-1}(2) = (1, 0), b^{-1}(3) = (1, 1)$$

Therefore, $D$ will be calculated as so:

$$D((0, 0), (0, 1)) = 2, D((0, 1), (0, 0)) = 3, \\D((1, 0), (1, 0)) = 4, D((1, 1), (1, 1)) = 5$$

Commitment and Opening Steps

1. Given $r_x$ and $r_y$, the prover provides oracles and $E_{r_y}$:

$$\forall \bm{k} \in \{0, 1\}^{\log N}, \space E_{r_x}(\bm{k}) = \widetilde{\mathsf{eq}}(b^{-1}(\mathsf{row}(\bm{k})), r_x) \\ \forall \bm{k} \in \{0, 1\}^{\log N}, \space E_{r_y}(\bm{k}) = \widetilde{\mathsf{eq}}(b^{-1}(\mathsf{col}(\bm{k})), r_y) \\$$

1. The prover and verifier perform a sumcheck protocol for the equation:

$$v \stackrel{?}= \sum_{\bm{k} \in \{0, 1\}^{\log N}} \mathsf{val}(\bm{k}) \cdot E_{r_x}(\bm{k}) \cdot E_{r_y}(\bm{k})$$

1. At the final round of sumcheck, the verifier checks the following:

$$v(\bm{r_z}) \stackrel{?}= v_{\text{val}} \land E_{r_x}(\bm{r_z}) \stackrel{?}= v_{E_{r_x}} \land E_{r_y}(\bm{r_z}) \stackrel{?}= v_{E_{r_y}}$$

To verify the prover's claims of $E_{r_x}$ and $E_{r_y}$, an Offline Memory Checking method is employed (refer to "Detour: offline memory checking" in Section 6 of the paper for details).

Reduction of R1CS to Sumcheck

Brakedown is a proving scheme for R1CS. Since the sumcheck protocol is integral to Brakedown, R1CS must be reduced to a sumcheck format. R1CS is defined as:

$$\bm{A}\cdot \bm{Z} \circ \bm{B} \cdot \bm{Z} = \bm{C} \cdot \bm{Z}\text{, where } \bm{A}, \bm{B}, \bm{C} \in \mathbb{F}_q^{M\times M}\text{ and } \bm{Z} \in \mathbb{F}_q^M$$

This can be converted into a sumcheck format as follows (simplified for illustration; see Section 7 for details):

$$0 \stackrel{?}= \sum_{\bm{x} \in \{0, 1\}^{\log M}} \widetilde{\text{eq}}(\bm{r}, \bm{x}) \cdot [(\sum_{\bm{y} \in \{0, 1\}^{\log M}} \widetilde{A}(\bm{x}, \bm{y})\cdot \widetilde{Z}(\bm{y}))\cdot (\sum_{\bm{y} \in \{0, 1\}^{\log M}} \widetilde{B}(\bm{x}, \bm{y})\cdot \widetilde{Z}(\bm{y})) - (\sum_{\bm{y} \in \{0, 1\}^{\log M}} \widetilde{C}(\bm{x}, \bm{y})\cdot \widetilde{Z}(\bm{y}))]$$

Conclusion

Brakedown introduces linear-time encoding and linear-time commitment for generating proofs for R1CS, enabling proof generation with $O(N)$ field operations. However, as mentioned earlier, the proof size is large, and the verification time is slow. These characteristics are evident in the following results:

The figure above, taken from the paper, benchmarks the performance of Brakedown's Polynomial Commitment Scheme. As shown, while Commit and Open operations are as fast as Ligero, the Verify and Communication stages are the slowest among the compared schemes.

This figure, also taken from the paper, shows that Brakedown achieves the fastest prove time and is among the fastest for encode time. However, it also confirms that verify remains slow, and the proof size is the largest.

Brakedown has since been improved and used in subsequent works, including Orion, Orion+, Vortex, and Binius.

Written by ryan Kim from A41