Brakedown and Shockwave
$$ \gdef\setn#1{\mathcal{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\vec#1{\mathbf{#1}} \gdef\enc{\mathsf{enc}} \gdef\p#1{\left({#1}\right)} $$
From GLS⁺21. Like in Hyrax, we will create a commitment to a matrix $\mat M ∈ 𝔽^{n×m}$ such that we can later compute double contractions $$ s = \vec p ⋅ \mat M ⋅ \vec q = \sum_{ij} \mat M_{ij}⋅p_i⋅q_j $$ for some arbitrary vectors $\vec p, \vec q$.
Take a linear code $\enc: 𝔽^m→𝔽^M$ with rate $ρ = m/M$. When instantiated with a linear-time encoding codes, it is known as Brakedown Polynomial Commitments. When instantiated with Reed-Solomon codes, it is known as Ligero Polynomial Commitments AHIV17. (And when used to instantiate Spartan they are known as Brakedown and Shockwave respectively.)
Commitment
Prover has $\mat M ∈ 𝔽^{n×m}$.
- Prover sends the column-wise Merkle-hash of $\mat E = [\enc(\mat M_i)]_{i∈[n]}$.
Evaluation
In addtion to above, prover and verifier have $\vec p ∈ 𝔽^n$, $\vec q ∈ 𝔽^m$ and want to compute the double contraction $s = \vec p ⋅ \mat M ⋅ \vec q$. The protocol is as above, with $\vec r$ substituted by $\vec p$:
- Verifier sends random $\mat R ∈ 𝔽^{k×n}$.
- Prover sends $\mat U = [\vec p; \mat R]⋅ \mat M$.
- Verfier computes $\mat C = [\enc(\mat U_i)]_{i∈[k]}$.
- Verifier sends $\setn C ⊂ [m]$.
- Prover decommits columns $\mat E_{\setn C}$.
- Verifier checks $\mat C_{\setn C} = [\vec p; \mat R] ⋅ \mat E_{\setn C}$.
- Verifier checks $s = \mat U_0 ⋅ \vec q$
Parameter Choices for Reed-Solomon Codes
Given security target $λ$ in bits. Assuming the matrix dimensions and encoding rate are fixed, the main protocol parameters are the number of random combinations $k$ and queries $|\setn C|$. Following GLS⁺21 theorem B.7 (see also reference implementation 1 2), these are set to:
$$ \begin{aligned} k = 1 + \left\lfloor \frac{λ - 1}{\log_2 |𝔽| - \log_2 M} \right\rfloor && |\setn C| = \left\lceil \frac{λ}{1 - \log_2 (1 + \frac{m}{M})} \right\rceil \end{aligned} $$
For $λ = 128$ and large field $|𝔽| ≥ 2^{200}$ with reasonably sized $M < 2^{64}$ we will always have $k = 1$. The number of queries $|\setn C|$ decays exponentially from about $2.5 ⋅ λ$ for $M = 2⋅m$ down to $λ$ as $M$ increases.
The randomized checks created by $k$ serve to verify that the commitment is constructed correctly. This only has to be done once, so for repeated evaluations or when the commitment is trusted we can set $k=0$ (see GLS⁺21 p. 12).
Question. Does the process of grinding as used in FRI help to boost soundness and reduce $|\setn C|$?
References
- AHIV17 Scott Ames, Carmit Hazay, Yuval Ishai & Muthuramakrishnan Venkitasubramaniam (2017). Ligero: Lightweight Sublinear Arguments Without a Trusted Setup.
- BCG20 Jonathan Bootle, Alessandro Chiesa, and Jens Groth (2020). Linear-Time Arguments with Sublinear Verification from Tensor Codes
- GLS⁺21 Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, Riad S. Wahby (2021). Brakedown: Linear-time and field-agnostic SNARKs for R1CS.