Skip to Content
⚠️ This documentation is AI-generated, for personal use only, and is not supported or endorsed by Google.
ReferenceProof SystemLigero

Ligero

The ligero/ module is Longfellow’s witness-hiding commitment scheme. The prover encodes the witness plus a zero-knowledge pad as a tableau of Reed-Solomon codewords, Merkle-commits to the codeword columns, and later opens a random subset of those columns to prove that the committed witness satisfies linear and quadratic constraints (derived from sumcheck). The rate (rateinv) and query count (nreq) together set the statistical soundness — this is the page you read to pick them.

When to reach for it

  • You need to pick rate and nreq for ZkVerifier and want to understand the trade-off.
  • You want a commit-to-witness-then-prove-constraints flow outside of a sumcheck context (rare, but the direct API supports it).
  • You are sizing proofs and need to know what drives blob size (code rate, number of queries, witness size).

Design overview

Witness encoding. The prover arranges the witness (plus a zero-knowledge pad) into a matrix of message blocks of size BLOCK, then extends each row into a Reed-Solomon codeword of length BLOCK_ENC = DBLOCK + BLOCK_EXT where DBLOCK = 2 * BLOCK - 1 (room for the squared quadratic-test polynomial) and BLOCK_EXT is chosen so that BLOCK / BLOCK_ENC is approximately 1 / rateinv. In the source (lib/ligero/ligero_param.h), the layout routine picks block = (block_enc + 1) / (2 + rateinv) and the constructor sweeps candidate block_enc values to minimise proof size.

Commitment. The Merkle tree is built over the columns of the extended matrix, not the rows. Opening a random column exposes one coordinate of every encoded row simultaneously — the trick that makes Ligero cheap to query. The commitment object LigeroCommitment<Field> is just the Merkle root; the full tableau stays with the prover.

Proving. Linear and quadratic constraints are packed into small per-constraint proofs: y_ldt (low-degree test response, size block), y_dot (dot-product response, size dblock), y_quad_0 and y_quad_2 (two pieces of the quadratic-test response — the middle w coordinates are known to be zero and are elided). The verifier then opens nreq random columns and checks that (a) each opened column is consistent with its Merkle leaf; (b) the openings satisfy the claimed linear and quadratic constraints; (c) every row decodes as a low-degree polynomial.

Subfield optimisation. The subfield_boundary parameter tells the prover that the first K witness elements live in the base field, not the full field extension. For those, blinding randomness is sampled from the subfield too, which shortens the opened-column serialisation. This optimisation has no safety implications; it simply makes proofs smaller when your witness is mostly bits or byte values — common in the attestation setting (hashed bytes, bit-packed curve points).

API surface

Parameters

  • LigeroParam<Field>(size_t nw, size_t nq, size_t rateinv, size_t nreq) — nw is witness count (including pad), nq is quadratic-constraint count, rateinv is the inverse code rate, nreq is the number of opened columns. The constructor auto-optimises block_enc and derives the per-row layout; a second overload accepts a pre-computed block_enc.
  • Two standard presets from lib/circuits/mdoc/mdoc_zk.h:
    • kLigeroRate = 4, kLigeroNreq = 128 — 86+ bits statistical security.
    • kLigeroRatev7 = 7, kLigeroNreqv7 = 132 — approximately 109 bits statistical security.

Prover

  • LigeroProver<Field, InterpolatorFactory>(const LigeroParam<Field>& p) — constructor; allocates the tableau.
  • void commit(LigeroCommitment<Field>& commitment, Transcript& ts, const Elt W[], size_t subfield_boundary, const LigeroQuadraticConstraint lqc[], const InterpolatorFactory& interpolator, RandomEngine& rng, const Field& F) — extends rows, Merkle-commits columns, appends the root to the transcript.
  • void prove(LigeroProof<Field>& proof, Transcript& ts, size_t nl, size_t nllterm, const LigeroLinearConstraint<Field> llterm[], const LigeroHash& hash_of_llterm, const LigeroQuadraticConstraint lqc[], const InterpolatorFactory& interpolator, const Field& F) — writes the per-constraint proofs and opens nreq columns.

Verifier

  • static void LigeroVerifier<Field, InterpolatorFactory>::receive_commitment(const LigeroCommitment<Field>&, Transcript&) — accepts the root and mirrors the prover’s transcript append.
  • static bool verify(const char** why, const LigeroParam<Field>& p, const LigeroCommitment<Field>&, const LigeroProof<Field>&, Transcript& ts, size_t nl, size_t nllterm, const LigeroLinearConstraint<Field> llterm[], const LigeroHash& hash_of_llterm, const Elt b[], const LigeroQuadraticConstraint lqc[], const InterpolatorFactory&, const Field& F) — checks everything. why receives a short failure string on error (for example "merkle_check failed" or "low_degree_check failed").

Parameter choice and soundness

Per-query soundness. A Ligero commitment is a Merkle root over the columns of the Reed-Solomon-extended witness matrix. The protocol’s soundness hinges on the prover being unable to pass a proximity test — on convincing the verifier that their matrix rows decode to a consistent witness while actually being far from any valid codeword. The Reed-Solomon code has minimum distance at least BLOCK_EXT+1=(rateinv−1)⋅BLOCK+1\mathrm{BLOCK\_EXT} + 1 = (\mathrm{rateinv} - 1) \cdot \mathrm{BLOCK} + 1 (Singleton bound). A cheating prover who commits to a matrix whose rows are far from real codewords would, at a random column, be caught with probability at least the code’s relative distance, roughly 1−1/rateinv1 - 1/\mathrm{rateinv}. For rateinv = 4 that is about 0.750.75 per query; for rateinv = 7 it is about 0.860.86.

Total soundness from nreq queries. Each of the nreq queried columns is independent under Fiat-Shamir, so a cheating prover’s probability of slipping past all of them is roughly (1−δ)nreq(1 - \delta)^{\mathrm{nreq}} where δ\delta is the per-query detection probability. Taking logs, statistical security in bits is approximately −nreq⋅log⁡2(1−δ)-\mathrm{nreq} \cdot \log_2(1 - \delta). For the (rateinv=4, nreq=128) preset, 1−δ≈0.251 - \delta \approx 0.25, so the raw number works out to 128⋅log⁡2(4)=256128 \cdot \log_2(4) = 256 bits — but the achieved soundness is worse, because the bound has to account for interleaved-test and low-degree-test slack, giving the 86+ bits figure quoted in mdoc_zk.h. For the (rateinv=7, nreq=132) preset, the same accounting gives approximately 109 bits. The intuition to keep: moving from rate 1/41/4 to rate 1/71/7 and adding four queries buys about +23 bits of security.

Tradeoffs when tuning. Higher rateinv yields smaller proofs (fewer bytes per opened column, since each column holds fewer field elements) at the cost of slower prover time — the Reed-Solomon extension is more aggressive, and FFT work grows superlinearly in code length. Higher nreq linearly adds bytes per proof but linearly adds soundness bits. If you are targeting attestation-scale workloads (a few dozen ECDSA signatures, a few SHA-256 blocks) and aim for at least 100-bit security, the v7 preset is a reasonable default; if proof size matters more than prover time and 86 bits is acceptable, the rate=4 preset (kLigeroRate = 4, kLigeroNreq = 128) produces smaller proofs. If you want different numbers, pick rateinv from {3,4,5,6,7}\{3, 4, 5, 6, 7\} and nreq large enough to clear your target: empirically, nreq≈bits/log⁡2(rateinv)\mathrm{nreq} \approx \mathrm{bits} / \log_2(\mathrm{rateinv}) plus a modest margin.

Example

The direct API below is adapted from lib/ligero/ligero_test.cc. Most users will go through zk/; reach for this only for advanced uses (custom constraint systems, profiling the commitment stage in isolation).

LigeroParam<Field> param(nw, nq, /*rateinv=*/4, /*nreq=*/128);
LigeroCommitment<Field> commitment;
LigeroProof<Field> proof(&param);
SecureRandomEngine rng;
LigeroProver<Field, ReedSolomonFactory> prover(param);
Transcript ts((uint8_t*)"direct-ligero", 13);
 
prover.commit(commitment, ts, W.data(), /*subfield_boundary=*/0,
              lqc.data(), rs_factory, rng, F);
prover.prove(proof, ts, nl, llterm.size(), llterm.data(),
             hash_of_llterm, lqc.data(), rs_factory, F);
 
Transcript tv((uint8_t*)"direct-ligero", 13);
LigeroVerifier<Field, ReedSolomonFactory>::receive_commitment(commitment, tv);
const char* why = "";
bool ok = LigeroVerifier<Field, ReedSolomonFactory>::verify(
    &why, param, commitment, proof, tv, nl, llterm.size(), llterm.data(),
    hash_of_llterm, b.data(), lqc.data(), rs_factory, F);

See it used

Last updated on
SumcheckMerkle Commitments