zorch.pcs.basefold.prover

BaseFold prover — the commit slice of the multilinear PCS on the pcs seam.

commit is the low-degree extension of each column (FoldableCode.encode; the native-NTT Reed-Solomon today) followed by a Merkle commit of the codeword rows. Unlike kzg/fri — which commit each polynomial in the batch independently and return one root per poly — BaseFold is a matrix commitment: the columns share one code domain and the Merkle leaves are codeword rows spanning all columns, so the whole batch binds under a single root.

open is the BaseFold batch open: it reduces one or more separately committed matrices, evaluated at a shared point, to a single FRI. Each matrix's columns are combined with the others' by a staggered partial-Lagrange RLC into one codeword and one MLE; an interleaved sumcheck folds that MLE while the FRI folds the codeword by the same per-round challenge, the round committing the pre-fold layer's conjugate-pair leaves before sampling the fold challenge. A single matrix is the degenerate one-round batch.

The open is driven by a (BasefoldConfig, BasefoldChoreography) pair: the config fixes the fold schedule (commit cadence + leaf grouping), the choreography fixes the Fiat-Shamir framing (round-message form, root/terminal observes, query sampling, grinding). BasefoldProver's defaults are zorch's native wire — commits_per_round (pre-fold arity-2 pair commit every round) + the native BasefoldChoreography — so the plain BasefoldProver(code, tree, num_queries=…) construction is byte-for-byte today's implementation. A byte-fixed consumer supplies its own config + choreography and drives open_with_basis instead — the raw-basis entry mirroring LigeritoProver.open_with_basis.

BasefoldProverData dataclass

Retained witness from BasefoldProver.commit: the Merkle digest layers, the message-domain MLE [S, K] (the sumcheck folds it), the codeword [block_len, K] (the fold halves it), the committed base-field leaves (what the Merkle commit/open hashes — the codeword's rows reinterpreted as base-field limbs, identity for a base-field code), plus per-column widths. A pytree so commit/open ride a @jit zone.

Source code in zorch/pcs/basefold/prover.py

@partial(
    frx.tree_util.register_dataclass,
    data_fields=["digest_layers", "mle", "codeword", "leaves"],
    meta_fields=["widths"],
)
@dataclass(frozen=True)
class BasefoldProverData:
    """Retained witness from `BasefoldProver.commit`: the Merkle digest layers,
    the message-domain MLE `[S, K]` (the sumcheck folds it), the codeword
    `[block_len, K]` (the fold halves it), the committed base-field leaves (what
    the Merkle commit/open hashes — the codeword's rows reinterpreted as
    base-field limbs, identity for a base-field code), plus per-column widths. A
    pytree so `commit`/`open` ride a `@jit` zone."""

    digest_layers: list[Array]
    mle: Array  # [S, K] message-domain columns
    codeword: Array  # [block_len, K] codeword (the fold halves it)
    leaves: Array  # [block_len, K*limbs] base-field Merkle leaves
    widths: tuple[int, ...]

BasefoldProver dataclass

Bases: ProverStage[OpeningClaim[BasefoldCommitment], OpeningWitness[BasefoldProverData], TrivialClaim, OpeningProof[BasefoldProof], TranscriptT], Generic[TranscriptT]

BaseFold PCS prover. code fixes the per-column message length (= the MLE height S); tree commits the codeword rows; choreography fixes the Fiat-Shamir wire (share the instance with the verifier); config fixes the fold schedule. The defaults are zorch's native wire — the plain BasefoldProver(code, tree, num_queries=…) construction is byte-for-byte today's implementation. config=None derives the native per-open config (commits_per_round, num_vars from the opening point).

Source code in zorch/pcs/basefold/prover.py

@dataclass(frozen=True)
class BasefoldProver(
    ProverStage[
        OpeningClaim[BasefoldCommitment],
        OpeningWitness[BasefoldProverData],
        TrivialClaim,
        OpeningProof[BasefoldProof],
        TranscriptT,
    ],
    Generic[TranscriptT],
):
    """BaseFold PCS prover. `code` fixes the per-column message
    length (= the MLE height `S`); `tree` commits the codeword rows;
    `choreography` fixes the Fiat-Shamir wire (share the instance with the
    verifier); `config` fixes the fold schedule. The defaults are zorch's native
    wire — the plain `BasefoldProver(code, tree, num_queries=…)` construction is
    byte-for-byte today's implementation. `config=None` derives the native
    per-open config (`commits_per_round`, `num_vars` from the opening point)."""

    code: FoldableCode
    tree: MerkleTree
    num_queries: int = 4  # query repetitions; placeholder, not soundness-calibrated
    choreography: BasefoldChoreography[TranscriptT] = BasefoldChoreography()
    kernel: SumcheckKernel = SumcheckKernel()
    config: BasefoldConfig | None = None

    def _resolved_config(self, num_vars: int) -> BasefoldConfig:
        """The config driving an open over `num_vars` variables: the explicit
        one (checked against the point dimension) or the native default
        (`commits_per_round`, `num_queries` from the prover)."""
        if self.config is None:
            return BasefoldConfig(num_vars=num_vars, num_queries=self.num_queries)
        if self.config.num_vars != num_vars:
            raise ValueError(
                f"config.num_vars={self.config.num_vars} doesn't match the open's "
                f"variable count {num_vars}"
            )
        return self.config

    def commit(
        self, polys: Sequence[Array]
    ) -> tuple[BasefoldCommitment, BasefoldProverData]:
        return _commit_body(self.code, self.tree, list(polys))

    def prove(
        self,
        claim: OpeningClaim[BasefoldCommitment],
        witness: OpeningWitness[BasefoldProverData],
        transcript: TranscriptT,
    ) -> ProveResult[TrivialClaim, OpeningProof[BasefoldProof], TranscriptT]:
        """Open a single committed matrix — the degenerate one-round batch.

        Terminal: an opening closes its claim rather than reducing it, so the
        reduced claim is trivial. `values` is the matrix's per-column
        evaluations `[K]`."""
        values, proof, transcript = self.open_batch(
            [witness.prover_data], claim.points, transcript
        )
        return ProveResult(TrivialClaim(), OpeningProof(values[0], proof), transcript)

    def open_batch(
        self,
        rounds: Sequence[BasefoldProverData],
        points: Sequence[Array],
        transcript: TranscriptT,
    ) -> tuple[list[Array], BasefoldProof, TranscriptT]:
        """Batch-open the committed matrices `rounds` at the shared point.

        Returns `(values, proof, transcript)` where `values[r]` is round `r`'s
        per-column evaluations `[w_r]`. A single-element `rounds` is the
        degenerate (un-batched) open.
        """
        if len(points) != 1:
            raise ValueError(
                f"BaseFold opens the matrices at one shared point, got {len(points)}"
            )
        if not rounds:
            raise ValueError("BaseFold opens at least one committed matrix, got none")
        z = points[0]  # (log_S,)
        num_vars = z.shape[0]
        # Eager shape guards, ahead of the jit zone (mirrors the verifier).
        if num_vars < 1:
            raise ValueError("BaseFold opens over at least one variable, got none")
        for pd in rounds:
            if pd.mle.shape[0] != (1 << num_vars):
                raise ValueError(
                    f"point dimension {num_vars} doesn't match MLE height "
                    f"{pd.mle.shape[0]} (expected 2^{num_vars})"
                )
        self._resolved_config(num_vars).require_native("open")
        return _open_batch_body(self, list(rounds), z, transcript)

    def open_with_basis(
        self,
        prover_data: BasefoldProverData,
        basis: Array,
        value: Array,
        transcript: TranscriptT,
    ) -> tuple[BasefoldProof | CadenceProof, 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. Mirrors
        `LigeritoProver.open_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 — this entry is for a basis
        consumer).

        Under a non-native fold schedule (`row_batch_prefix` / `fold_arities`)
        this returns a generic `CadenceProof` the consumer serializes; under the
        native uniform schedule it returns a `BasefoldProof` (and the native
        binding refuses the basis entry, as before)."""
        if basis.shape[0] != prover_data.mle.shape[0]:
            raise ValueError(
                f"basis length {basis.shape[0]} must equal the MLE height "
                f"{prover_data.mle.shape[0]} (= 2^num_vars)"
            )
        num_vars = log2_strict_usize(basis.shape[0])
        config = self._resolved_config(num_vars)
        if not config.commits_per_round:
            # Non-native fold schedule (row-batch prefix + multi-arity epochs):
            # the eager, host-Fiat-Shamir cadence driver, returning a generic
            # `CadenceProof` the consumer serializes. A byte-wire consumer drives
            # this entry with its own choreography + kernel.
            return _open_with_basis_cadence(
                self, prover_data, basis, value, config, transcript
            )
        return _open_with_basis_body(self, prover_data, basis, value, transcript)

prove

prove(
    claim: OpeningClaim[BasefoldCommitment],
    witness: OpeningWitness[BasefoldProverData],
    transcript: TranscriptT,
) -> ProveResult[
    TrivialClaim, OpeningProof[BasefoldProof], TranscriptT
]

Open a single committed matrix — the degenerate one-round batch.

Terminal: an opening closes its claim rather than reducing it, so the reduced claim is trivial. values is the matrix's per-column evaluations [K].

Source code in zorch/pcs/basefold/prover.py

def prove(
    self,
    claim: OpeningClaim[BasefoldCommitment],
    witness: OpeningWitness[BasefoldProverData],
    transcript: TranscriptT,
) -> ProveResult[TrivialClaim, OpeningProof[BasefoldProof], TranscriptT]:
    """Open a single committed matrix — the degenerate one-round batch.

    Terminal: an opening closes its claim rather than reducing it, so the
    reduced claim is trivial. `values` is the matrix's per-column
    evaluations `[K]`."""
    values, proof, transcript = self.open_batch(
        [witness.prover_data], claim.points, transcript
    )
    return ProveResult(TrivialClaim(), OpeningProof(values[0], proof), transcript)

open_batch

open_batch(
    rounds: Sequence[BasefoldProverData],
    points: Sequence[Array],
    transcript: TranscriptT,
) -> tuple[list[Array], BasefoldProof, TranscriptT]

Batch-open the committed matrices rounds at the shared point.

Returns (values, proof, transcript) where values[r] is round r's per-column evaluations [w_r]. A single-element rounds is the degenerate (un-batched) open.

Source code in zorch/pcs/basefold/prover.py

def open_batch(
    self,
    rounds: Sequence[BasefoldProverData],
    points: Sequence[Array],
    transcript: TranscriptT,
) -> tuple[list[Array], BasefoldProof, TranscriptT]:
    """Batch-open the committed matrices `rounds` at the shared point.

    Returns `(values, proof, transcript)` where `values[r]` is round `r`'s
    per-column evaluations `[w_r]`. A single-element `rounds` is the
    degenerate (un-batched) open.
    """
    if len(points) != 1:
        raise ValueError(
            f"BaseFold opens the matrices at one shared point, got {len(points)}"
        )
    if not rounds:
        raise ValueError("BaseFold opens at least one committed matrix, got none")
    z = points[0]  # (log_S,)
    num_vars = z.shape[0]
    # Eager shape guards, ahead of the jit zone (mirrors the verifier).
    if num_vars < 1:
        raise ValueError("BaseFold opens over at least one variable, got none")
    for pd in rounds:
        if pd.mle.shape[0] != (1 << num_vars):
            raise ValueError(
                f"point dimension {num_vars} doesn't match MLE height "
                f"{pd.mle.shape[0]} (expected 2^{num_vars})"
            )
    self._resolved_config(num_vars).require_native("open")
    return _open_batch_body(self, list(rounds), z, transcript)

open_with_basis

open_with_basis(
    prover_data: BasefoldProverData,
    basis: Array,
    value: Array,
    transcript: TranscriptT,
) -> tuple[BasefoldProof | CadenceProof, 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. Mirrors LigeritoProver.open_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 — this entry is for a basis consumer).

Under a non-native fold schedule (row_batch_prefix / fold_arities) this returns a generic CadenceProof the consumer serializes; under the native uniform schedule it returns a BasefoldProof (and the native binding refuses the basis entry, as before).

Source code in zorch/pcs/basefold/prover.py

def open_with_basis(
    self,
    prover_data: BasefoldProverData,
    basis: Array,
    value: Array,
    transcript: TranscriptT,
) -> tuple[BasefoldProof | CadenceProof, 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. Mirrors
    `LigeritoProver.open_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 — this entry is for a basis
    consumer).

    Under a non-native fold schedule (`row_batch_prefix` / `fold_arities`)
    this returns a generic `CadenceProof` the consumer serializes; under the
    native uniform schedule it returns a `BasefoldProof` (and the native
    binding refuses the basis entry, as before)."""
    if basis.shape[0] != prover_data.mle.shape[0]:
        raise ValueError(
            f"basis length {basis.shape[0]} must equal the MLE height "
            f"{prover_data.mle.shape[0]} (= 2^num_vars)"
        )
    num_vars = log2_strict_usize(basis.shape[0])
    config = self._resolved_config(num_vars)
    if not config.commits_per_round:
        # Non-native fold schedule (row-batch prefix + multi-arity epochs):
        # the eager, host-Fiat-Shamir cadence driver, returning a generic
        # `CadenceProof` the consumer serializes. A byte-wire consumer drives
        # this entry with its own choreography + kernel.
        return _open_with_basis_cadence(
            self, prover_data, basis, value, config, transcript
        )
    return _open_with_basis_body(self, prover_data, basis, value, transcript)