https://eprint.iacr.org/2024/1609.pdf

Blaze is a multilinear PCS over binary extension fields that commits to the truth table of a multilinear polynomial using an interleaved Repeat–Accumulate–Accumulate (RAA) code and a Merkle tree; openings reduce to a small Basefold/FRI-style check over a random linear combination of rows. The heavy lifting is just XOR-like work (field additions) thanks to packing in $\mathbb{F}_{2^f}$. Blaze combines:

• a Repeat–Accumulate–Accumulate (RAA) error-correcting code (packed over $\mathbb{F}_{2^f}$),
• interleaving (to shrink the inner instance the prover handles),
• a compact IOPP that checks the RAA pipeline (permutations + prefix-sums),
• and a Merkle tree + Fiat–Shamir to compile into a non-interactive PCS.

It yields linear-time commits, linear-time openings with tiny constants, and polylogarithmic verification time and proof size.

The main idea (what Blaze does)

Blaze is a multilinear polynomial commitment scheme built to be fast for the prover and tiny for the verifier. It does this by combining four simple ingredients:

1. Encode the table of the polynomial with a very fast code.

   Take the truth table $m\in F^{2^k}$ of your multilinear polynomial and run it through a packed RAA code (Repeat → Permute → Accumulate → Permute → Accumulate) over a binary-extension field. This encoding is basically XORs and prefix sums, so it’s linear-time and CPU friendly.

2. Commit with a Merkle tree.

   Put the encoded word into a Merkle tree; the commitment is just the root. No heavy public-key crypto.

3. Shrink evaluation checking via interleaving + a random linear combo.

   To prove $f(z)=v$, Blaze interleaves the codeword into many short rows and sends the tiny vector of the rows’ partial evaluations. A Fiat–Shamir-derived random vector $r$ folds all rows into one small combo instance. That means the heavy work is done on a structure $\sim 1/t$ the original size, so the proof is polylogarithmic in the original table size.

4. Prove only simple linear facts about the code pipeline.

   The combo instance must satisfy the RAA steps:

   $\mathrm{Repeat} \longrightarrow \pi_1 \longrightarrow A \longrightarrow \pi_2 \longrightarrow A$

   which are all linear relations. Blaze checks them with:

   • Sumcheck for the two accumulation (prefix-sum) steps, and

   • a compact permutation argument for the two permutation steps,

     plus a few Merkle openings for the positions the verifier touches.

Put together: commit = Merkle root; open = a tiny vector, a few Merkle paths, and a short transcript that the linear pipeline is consistent. Prover runs in (near) linear time, verifier time and proof size are polylogarithmic in the table size.

Public Parameters

Let $n=2^m$ be the table size of $f:\{0,1\}^m \to F$ over a binary extension field $F=\mathbb{F}_{2^f}$.

• RAA parameters
  • $r$: repetition factor (typical $r=4$, i.e., rate 1/4)
  • $\pi_1,\pi_2$: public permutations on $[nr]$ sampled once (with quick distance tests)
• Interleaving
  • $t$: interleaving factor
• Hash / Transcript
  • Hash $H$ (Merkle) and domain separators for Fiat–Shamir

There is no trusted CRS. The only randomness is in choosing $\pi_1,\pi_2$ once, optionally followed by lightweight distance tests.