zorch.pcs.fri.prover

FRI prover for univariate point evaluation (the DEEP quotient trick).

To open f at z with claim v, the prover shows the quotient g(x) = (f(x) − v)/(x − z) is low degree: g is a polynomial of degree deg f − 1 exactly when v = f(z). g is never opened from a separate commitment — the verifier rebuilds its layer-0 pair from the already-committed f at the queried points and checks it against the committed fold chain — so open Merkle-commits g's fold layers (conjugate-pair leaves, pre-fold) and threads the transcript through the fold challenges. This is the structural opposite of KZG on the same PCS seam: interactive, Merkle-backed, no SRS, and entirely field/NTT arithmetic that lowers on both CPU and GPU (no MSM). The query phase is device-batched — positions are a device int32 array and each Merkle opening is one vmap over them — while the fold phase stays a Python for over rounds: each round Merkle-commits a half-size layer, so the loop is not scan-shaped (see docs/reference/conventions.md). Scope: a single base-field polynomial per opening, fixed small parameters — a demonstration of the seam, not a hardened prover.

FriCommittedPoly dataclass

One committed polynomial's retained witness: ascending coefficients, the raw [n] codeword (the DEEP quotient divides it pointwise), the [n//2, 2] conjugate-pair leaves (the Merkle commitment), and its digest layers.

A registered pytree so it crosses the open @jit boundary.

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

@partial(
    frx.tree_util.register_dataclass,
    data_fields=["coeffs", "codeword", "leaves", "digest_layers"],
    meta_fields=[],
)
@dataclass(frozen=True)
class FriCommittedPoly:
    """One committed polynomial's retained witness: ascending coefficients, the
    raw `[n]` codeword (the DEEP quotient divides it pointwise), the `[n//2, 2]`
    conjugate-pair leaves (the Merkle commitment), and its digest layers.

    A registered pytree so it crosses the `open` `@jit` boundary."""

    coeffs: Array
    codeword: Array
    leaves: Array
    digest_layers: list[Array]

FriProverData dataclass

Retained witness from FriProver.commit, one entry per committed poly.

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

@dataclass(frozen=True)
class FriProverData:
    """Retained witness from `FriProver.commit`, one entry per committed poly."""

    polys: tuple[FriCommittedPoly, ...]

FriProver dataclass

Bases: ProverStage[OpeningClaim[FriCommitment], OpeningWitness[FriProverData], TrivialClaim, OpeningProof[list[FriProof]]]

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

@dataclass(frozen=True)
class FriProver(
    ProverStage[
        OpeningClaim[FriCommitment],
        OpeningWitness[FriProverData],
        TrivialClaim,
        OpeningProof[list[FriProof]],
    ]
):
    params: FriParams

    def commit(self, polys: Sequence[Array]) -> tuple[FriCommitment, FriProverData]:
        """RS-encode each coefficient vector and Merkle-commit its codeword's
        conjugate-pair leaves. Returns stacked roots and the prover data."""
        committed = [
            _commit_one(self.params.code, self.params.tree, coeffs) for coeffs in polys
        ]
        roots = [poly.digest_layers[-1][0] for poly in committed]
        return fnp.stack(roots), FriProverData(tuple(committed))

    def prove(
        self,
        claim: OpeningClaim[FriCommitment],
        witness: OpeningWitness[FriProverData],
        transcript: Transcript,
    ) -> ProveResult[TrivialClaim, OpeningProof[list[FriProof]]]:
        """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: FriProverData,
        points: Sequence[Array],
        transcript: Transcript,
    ) -> tuple[Array, list[FriProof], Transcript]:
        if len(prover_data.polys) != len(points):
            raise ValueError(
                f"batch mismatch: {len(prover_data.polys)} polys vs "
                f"{len(points)} points"
            )
        values, proofs = [], []
        t = transcript
        for committed, z in zip(prover_data.polys, points):
            v = _eval_poly(committed.coeffs, z)
            t, proof = _open_one(self.params, committed, z, v, t)
            values.append(v)
            proofs.append(proof)
        return fnp.stack(values), proofs, t

commit

commit(
    polys: Sequence[Array],
) -> tuple[FriCommitment, FriProverData]

RS-encode each coefficient vector and Merkle-commit its codeword's conjugate-pair leaves. Returns stacked roots and the prover data.

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

def commit(self, polys: Sequence[Array]) -> tuple[FriCommitment, FriProverData]:
    """RS-encode each coefficient vector and Merkle-commit its codeword's
    conjugate-pair leaves. Returns stacked roots and the prover data."""
    committed = [
        _commit_one(self.params.code, self.params.tree, coeffs) for coeffs in polys
    ]
    roots = [poly.digest_layers[-1][0] for poly in committed]
    return fnp.stack(roots), FriProverData(tuple(committed))

prove

prove(
    claim: OpeningClaim[FriCommitment],
    witness: OpeningWitness[FriProverData],
    transcript: Transcript,
) -> ProveResult[
    TrivialClaim, OpeningProof[list[FriProof]]
]

Open the committed polynomials at the claim's points.

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

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

def prove(
    self,
    claim: OpeningClaim[FriCommitment],
    witness: OpeningWitness[FriProverData],
    transcript: Transcript,
) -> ProveResult[TrivialClaim, OpeningProof[list[FriProof]]]:
    """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)