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}.

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

  1. Verifier sends random \mat R ∈ 𝔽^{k×n}.
  2. Prover sends \mat U = [\vec p; \mat R]⋅ \mat M.
  3. Verfier computes \mat C = [\enc(\mat U_i)]_{i∈[k]}.
  4. Verifier sends \setn C ⊂ [m].
  5. Prover decommits columns \mat E_{\setn C}.
  6. Verifier checks \mat C_{\setn C} = [\vec p; \mat R] ⋅ \mat E_{\setn C}.
  7. 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

Remco Bloemen
Math & Engineering
https://2π.com