Skip to content

zorch.pcs.ligerito.prover

Ligerito recursive-open prover — the prover half of the recursive matrix PCS. Single-shot Ligero (pcs/ligero) sends the vector w = X̃·r_col in the clear, paying sqrt(N). Ligerito instead commits w and discharges the proximity check as one continuous interleaved sumcheck that batches every level's committed-w eval-claims and recurses on the residual.

The whole thing is one sumcheck Σ_x W(x)·B(x) = claim over the shrinking witness W (W starts as the committed multilinear f, B as the value basis eq(z), claim as y = f(z)). Each level:

  • folds fold_ks[j] variables (the current committed matrix M_j's interleave lanes) through the degree-2 product sumcheck;
  • re-commits the folded W as a fresh Ligero matrix M_{j+1} at a lower rate;
  • opens M_j's codeword rows and induces its proximity eval-claims <M_j[s], eq(c_j)> = eval_mle(W_folded, eval_point(s)) into the running sumcheck with a fresh separation challenge — the induce_sumcheck_poly analog, built code-generically from the TensorCode seam's eval_point rather than a basis-specific novel-basis tensor.

The final level sends the folded residual in the clear; its proximity ties the residual to the last committed matrix directly (no sumcheck needed), and the sumcheck's terminal claim closes against Σ_x residual(x)·B(x).

The commit basis — the (pre, expand) pair fixing how a codeword coordinate reads back as a point-eval of the committed row — is a CommitBasis (ligerito/basis.py), selected by LigeritoConfig.monomial_commit. The default EVAL_BASIS encodes mle_evals_to_coeffs(matrix), cancelling the TensorCode seam's coeffs_to_evals so both the proximity RHS and the value check read as clean eval_mles of the eval-basis witness (encode(w)[s] == eval_mle(coeffs_to_evals(w), eval_point(s))); MONOMIAL_BASIS is the raw-lane (coefficient) convention a byte-fixed consumer needs (flock, #32).

Reuses pcs/basefold's staggered partial-Lagrange batching for the per-level α weights and pcs/fold's query machinery (open_rows). Every transcript interaction routes through the LigeritoChoreography seam (statement binding, round hops, root/residual framing, query sampling), so a byte-fixed consumer swaps the wire without touching the recursion. Code-generic over a TensorCode; the multiplicative Reed-Solomon instantiation is the de-risk vehicle.

LigeritoProverData dataclass

Retained witness from LigeritoProver.commit: the eval-basis multilinear f and the initial matrix commitment M_0. open runs the recursion off these.

Source code in zorch/pcs/ligerito/prover.py 
126
127
128
129
130
131
132
133
@dataclass(frozen=True)
class LigeritoProverData:
    """Retained witness from `LigeritoProver.commit`: the eval-basis multilinear
    `f` and the initial matrix commitment `M_0`. `open` runs the recursion off
    these."""

    f: Array
    initial: CommittedMatrix

LigeritoProver dataclass

Bases: ProverStage[OpeningClaim[LigeritoCommitment], OpeningWitness[LigeritoProverData], TrivialClaim, OpeningProof[LigeritoProof], TranscriptT], Generic[TranscriptT]

Ligerito recursive PCS prover. make_code(message_len, log_inv_rate) builds each level's TensorCode; config fixes the fold schedule; tree commits every level's codeword rows; choreography fixes the Fiat-Shamir wire (share the instance with the verifier).

Generic in the transcript because the recursion grinds; the choreography must thread the same flavour, which is what stops a non-grinding wire being paired with a grinding schedule.

Source code in zorch/pcs/ligerito/prover.py 
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
@dataclass(frozen=True)
class LigeritoProver(
    ProverStage[
        OpeningClaim[LigeritoCommitment],
        OpeningWitness[LigeritoProverData],
        TrivialClaim,
        OpeningProof[LigeritoProof],
        TranscriptT,
    ],
    Generic[TranscriptT],
):
    """Ligerito recursive PCS prover. `make_code(message_len, log_inv_rate)`
    builds each level's `TensorCode`; `config` fixes the fold schedule; `tree`
    commits every level's codeword rows; `choreography` fixes the Fiat-Shamir
    wire (share the instance with the verifier).

    Generic in the transcript because the recursion grinds; the choreography
    must thread the same flavour, which is what stops a non-grinding wire being
    paired with a grinding schedule."""

    make_code: MakeCode
    tree: MerkleTree
    config: LigeritoConfig
    choreography: LigeritoChoreography[TranscriptT] = LigeritoChoreography()

    def _code(self, level: int, message_len: int) -> TensorCode:
        return self.make_code(message_len, self.config.log_inv_rates[level])

    def commit(
        self, polys: Sequence[Array]
    ) -> tuple[LigeritoCommitment, LigeritoProverData]:
        """Commit one multilinear as the initial Ligero matrix `M_0` (interleave =
        `fold_ks[0]` lanes)."""
        if len(polys) != 1:
            raise ValueError(
                f"Ligerito commits exactly one polynomial, got {len(polys)}"
            )
        f = polys[0]
        num_vars = log2_strict_usize(f.shape[0])
        if num_vars != self.config.num_vars:
            raise ValueError(
                f"polynomial has {num_vars} variables, config expects "
                f"{self.config.num_vars} (= sum(fold_ks))"
            )
        k0 = self.config.fold_ks[0]
        code0 = self._code(0, 1 << (num_vars - k0))
        basis = select_commit_basis(self.config.monomial_commit)
        initial = _commit(f, k0, code0, self.tree, basis=basis)
        return initial.root, LigeritoProverData(f=f, initial=initial)

    def prove(
        self,
        claim: OpeningClaim[LigeritoCommitment],
        witness: OpeningWitness[LigeritoProverData],
        transcript: TranscriptT,
    ) -> ProveResult[TrivialClaim, OpeningProof[LigeritoProof], TranscriptT]:
        """Open the committed polynomials at the claim's points.

        Terminal: an opening closes its claim rather than reducing it."""
        values, proof, transcript = self._open(
            witness.prover_data, claim.points, transcript
        )
        return ProveResult(TrivialClaim(), OpeningProof(values, proof), transcript)

    def _open(
        self,
        prover_data: LigeritoProverData,
        points: Sequence[Array],
        transcript: TranscriptT,
    ) -> tuple[Array, LigeritoProof, TranscriptT]:
        """Open the committed multilinear at `z`, returning `(value, proof,
        transcript)` with `value = f(z)`."""
        if len(points) != 1:
            raise ValueError(f"Ligerito opens at one point, got {len(points)}")
        z = points[0]
        if z.shape[0] != self.config.num_vars:
            raise ValueError(
                f"point dimension {z.shape[0]} must equal the variable count "
                f"{self.config.num_vars}"
            )
        one = fnp.ones((), z.dtype)
        B = expand_eq_to_hypercube(z, one)
        value = (prover_data.f * B).sum()  # f(z) = <f, eq(z)>; reuse B
        proof, t = _open(self, prover_data, z, B, value, transcript)
        return value, proof, t

    def open_with_basis(
        self,
        prover_data: LigeritoProverData,
        basis: Array,
        value: Array,
        transcript: TranscriptT,
    ) -> tuple[LigeritoProof, TranscriptT]:
        """Open the batched claim `<f, basis> = value` for a RAW hypercube basis
        instead of a point — the entry of outer protocols whose eval-claims
        arrive as an already-batched basis vector (flock's
        `recursive_prover_with_basis`). No point exists, so the choreography's
        `bind_statement` receives `point=None` and must bind the statement
        another way (the native binding refuses)."""
        if basis.shape[0] != 1 << self.config.num_vars:
            raise ValueError(
                f"basis length {basis.shape[0]} must be 2^{self.config.num_vars}"
            )
        return _open(self, prover_data, None, basis, value, transcript)

commit 

commit(
    polys: Sequence[Array],
) -> tuple[LigeritoCommitment, LigeritoProverData]

Commit one multilinear as the initial Ligero matrix M_0 (interleave = fold_ks[0] lanes).

Source code in zorch/pcs/ligerito/prover.py 
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
def commit(
    self, polys: Sequence[Array]
) -> tuple[LigeritoCommitment, LigeritoProverData]:
    """Commit one multilinear as the initial Ligero matrix `M_0` (interleave =
    `fold_ks[0]` lanes)."""
    if len(polys) != 1:
        raise ValueError(
            f"Ligerito commits exactly one polynomial, got {len(polys)}"
        )
    f = polys[0]
    num_vars = log2_strict_usize(f.shape[0])
    if num_vars != self.config.num_vars:
        raise ValueError(
            f"polynomial has {num_vars} variables, config expects "
            f"{self.config.num_vars} (= sum(fold_ks))"
        )
    k0 = self.config.fold_ks[0]
    code0 = self._code(0, 1 << (num_vars - k0))
    basis = select_commit_basis(self.config.monomial_commit)
    initial = _commit(f, k0, code0, self.tree, basis=basis)
    return initial.root, LigeritoProverData(f=f, initial=initial)

prove 

prove(
    claim: OpeningClaim[LigeritoCommitment],
    witness: OpeningWitness[LigeritoProverData],
    transcript: TranscriptT,
) -> ProveResult[
    TrivialClaim, OpeningProof[LigeritoProof], TranscriptT
]

Open the committed polynomials at the claim's points.

Terminal: an opening closes its claim rather than reducing it.

Source code in zorch/pcs/ligerito/prover.py 
186
187
188
189
190
191
192
193
194
195
196
197
198
def prove(
    self,
    claim: OpeningClaim[LigeritoCommitment],
    witness: OpeningWitness[LigeritoProverData],
    transcript: TranscriptT,
) -> ProveResult[TrivialClaim, OpeningProof[LigeritoProof], TranscriptT]:
    """Open the committed polynomials at the claim's points.

    Terminal: an opening closes its claim rather than reducing it."""
    values, proof, transcript = self._open(
        witness.prover_data, claim.points, transcript
    )
    return ProveResult(TrivialClaim(), OpeningProof(values, proof), transcript)

open_with_basis 

open_with_basis(
    prover_data: LigeritoProverData,
    basis: Array,
    value: Array,
    transcript: TranscriptT,
) -> tuple[LigeritoProof, TranscriptT]

Open the batched claim <f, basis> = value for a RAW hypercube basis instead of a point — the entry of outer protocols whose eval-claims arrive as an already-batched basis vector (flock's recursive_prover_with_basis). No point exists, so the choreography's bind_statement receives point=None and must bind the statement another way (the native binding refuses).

Source code in zorch/pcs/ligerito/prover.py 
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
def open_with_basis(
    self,
    prover_data: LigeritoProverData,
    basis: Array,
    value: Array,
    transcript: TranscriptT,
) -> tuple[LigeritoProof, TranscriptT]:
    """Open the batched claim `<f, basis> = value` for a RAW hypercube basis
    instead of a point — the entry of outer protocols whose eval-claims
    arrive as an already-batched basis vector (flock's
    `recursive_prover_with_basis`). No point exists, so the choreography's
    `bind_statement` receives `point=None` and must bind the statement
    another way (the native binding refuses)."""
    if basis.shape[0] != 1 << self.config.num_vars:
        raise ValueError(
            f"basis length {basis.shape[0]} must be 2^{self.config.num_vars}"
        )
    return _open(self, prover_data, None, basis, value, transcript)