Skip to content

zorch.coding.foldable_code

The FoldableCode seam: a LinearCode whose codewords fold round-by-round.

BaseFold-style IOPPs (FRI, BaseFold) need more than linearity from their code. Layer level (length block_len >> level; layer 0 is the fresh codeword) pairs entries (j, j + half) as the two evaluations of a degree-1 polynomial at a code-defined point pair, and the fold by challenge beta evaluates that line at beta, halving the layer. That per-level point-pair structure — diag(T_i), diag(T'_i) in BaseFold (Zeilberger–Chen–Fisch, https://eprint.iacr.org/2023/1705, Definition 5) — is part of the code's identity, not the PCS's: Reed-Solomon folds on the (x, -x) conjugates of its NTT domain; a random foldable code folds on its sampled diagonals. Keeping the fold behind this seam keeps the PCS layer free of encoding-specific domain knowledge — a plain LinearCode (Brakedown, ...) is NOT enough to drive BaseFold, so the prover/verifier must require this type, not LinearCode.

FoldableCode

Bases: LinearCode, Protocol

Source code in zorch/coding/foldable_code.py 
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
@runtime_checkable
class FoldableCode(LinearCode, Protocol):
    def fold(self, codeword: Array, beta: Array) -> Array:
        """Fold a layer by `beta`, halving its length (prover side)."""
        ...

    def pair_leaves(self, codeword: Array) -> Array:
        """Arrange a layer's codeword into its conjugate-pair leaves `[n//2, 2]`:
        row `p` is `(codeword[lo], codeword[hi])` for `(lo, hi) =
        pair_indices(p, level)`, so committing these leaves lets one Merkle path
        open both legs of the pair that folds to position `p`. The layout is the
        code's identity (natural order pairs a half-layer apart, bit-reversed
        order adjacently), so it lives behind the seam with `fold`."""
        ...

    def fold_values(
        self, lo: Array, hi: Array, beta: Array, positions: Array, level: int
    ) -> Array:
        """Fold opened value pairs of layer `level` at `positions` (verifier side).

        `lo`/`hi` are the layer's entries at `pair_indices(positions, level)`.
        Must agree with `fold`: with `(l, h) = pair_indices(p, level)`,
        `fold(layer, beta)[p] == fold_values(layer[l], layer[h], beta, p, level)`.
        """
        ...

    def pair_indices(self, positions: Array, level: int) -> tuple[Array, Array]:
        """Leaf indices of layer `level`'s point pair for folded index
        `positions` — the pair whose fold lands at `positions` in layer
        `level + 1`. The pairing layout is part of the code's identity
        (natural order pairs a half-layer apart; bit-reversed order pairs
        adjacently), so it lives behind the seam with the fold."""
        ...

    def layer_positions(self, positions: Array, num_rounds: int) -> list[Array]:
        """Per-layer folded query indices for sampled `positions`: element
        `i` addresses layer `i`'s pair via `pair_indices` and is where that
        fold lands in layer `i + 1`."""
        ...

    def check_final(self, final: Array, claim: Array) -> Array:
        """Whether the fully folded layer is the base-code encoding of the
        scalar `claim` — the IOPP terminal membership check, tied to the final
        sumcheck claim."""
        ...

fold 

fold(codeword: Array, beta: Array) -> Array

Fold a layer by beta, halving its length (prover side).

Source code in zorch/coding/foldable_code.py 
29
30
31
def fold(self, codeword: Array, beta: Array) -> Array:
    """Fold a layer by `beta`, halving its length (prover side)."""
    ...

pair_leaves 

pair_leaves(codeword: Array) -> Array

Arrange a layer's codeword into its conjugate-pair leaves [n//2, 2]: row p is (codeword[lo], codeword[hi]) for (lo, hi) = pair_indices(p, level), so committing these leaves lets one Merkle path open both legs of the pair that folds to position p. The layout is the code's identity (natural order pairs a half-layer apart, bit-reversed order adjacently), so it lives behind the seam with fold.

Source code in zorch/coding/foldable_code.py 
33
34
35
36
37
38
39
40
def pair_leaves(self, codeword: Array) -> Array:
    """Arrange a layer's codeword into its conjugate-pair leaves `[n//2, 2]`:
    row `p` is `(codeword[lo], codeword[hi])` for `(lo, hi) =
    pair_indices(p, level)`, so committing these leaves lets one Merkle path
    open both legs of the pair that folds to position `p`. The layout is the
    code's identity (natural order pairs a half-layer apart, bit-reversed
    order adjacently), so it lives behind the seam with `fold`."""
    ...

fold_values 

fold_values(
    lo: Array,
    hi: Array,
    beta: Array,
    positions: Array,
    level: int,
) -> Array

Fold opened value pairs of layer level at positions (verifier side).

lo/hi are the layer's entries at pair_indices(positions, level). Must agree with fold: with (l, h) = pair_indices(p, level), fold(layer, beta)[p] == fold_values(layer[l], layer[h], beta, p, level).

Source code in zorch/coding/foldable_code.py 
42
43
44
45
46
47
48
49
50
51
def fold_values(
    self, lo: Array, hi: Array, beta: Array, positions: Array, level: int
) -> Array:
    """Fold opened value pairs of layer `level` at `positions` (verifier side).

    `lo`/`hi` are the layer's entries at `pair_indices(positions, level)`.
    Must agree with `fold`: with `(l, h) = pair_indices(p, level)`,
    `fold(layer, beta)[p] == fold_values(layer[l], layer[h], beta, p, level)`.
    """
    ...

pair_indices 

pair_indices(
    positions: Array, level: int
) -> tuple[Array, Array]

Leaf indices of layer level's point pair for folded index positions — the pair whose fold lands at positions in layer level + 1. The pairing layout is part of the code's identity (natural order pairs a half-layer apart; bit-reversed order pairs adjacently), so it lives behind the seam with the fold.

Source code in zorch/coding/foldable_code.py 
53
54
55
56
57
58
59
def pair_indices(self, positions: Array, level: int) -> tuple[Array, Array]:
    """Leaf indices of layer `level`'s point pair for folded index
    `positions` — the pair whose fold lands at `positions` in layer
    `level + 1`. The pairing layout is part of the code's identity
    (natural order pairs a half-layer apart; bit-reversed order pairs
    adjacently), so it lives behind the seam with the fold."""
    ...

layer_positions 

layer_positions(
    positions: Array, num_rounds: int
) -> list[Array]

Per-layer folded query indices for sampled positions: element i addresses layer i's pair via pair_indices and is where that fold lands in layer i + 1.

Source code in zorch/coding/foldable_code.py 
61
62
63
64
65
def layer_positions(self, positions: Array, num_rounds: int) -> list[Array]:
    """Per-layer folded query indices for sampled `positions`: element
    `i` addresses layer `i`'s pair via `pair_indices` and is where that
    fold lands in layer `i + 1`."""
    ...

check_final 

check_final(final: Array, claim: Array) -> Array

Whether the fully folded layer is the base-code encoding of the scalar claim — the IOPP terminal membership check, tied to the final sumcheck claim.

Source code in zorch/coding/foldable_code.py 
67
68
69
70
71
def check_final(self, final: Array, claim: Array) -> Array:
    """Whether the fully folded layer is the base-code encoding of the
    scalar `claim` — the IOPP terminal membership check, tied to the final
    sumcheck claim."""
    ...

KFoldableCode

Bases: LinearCode, Protocol

k-ary generalization of the FoldableCode seam: a layer folds by a static fold_factor k, regrouping the k entries of one folded point's k-th-root coset per step instead of a conjugate pair (the k=2 special case).

Additive to FoldableCode, not a replacement — a code may implement both (ReedSolomon does). The binary pair seam is left untouched so the k=2 path stays byte- and XLA-identical, while this k-group seam serves arbitrary-factor consumers. The two do not collapse into one: the single-group fold is Lagrange interpolation (reed_solomon.fri_fold_k), which at k=2 is the conjugate butterfly's strictly costlier twin, so they coexist by design. Every method here is the k-ary mirror of a FoldableCode pair method, named *group* to sit alongside it.

Source code in zorch/coding/foldable_code.py 
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
@runtime_checkable
class KFoldableCode(LinearCode, Protocol):
    """k-ary generalization of the FoldableCode seam: a layer folds by a static
    `fold_factor` k, regrouping the k entries of one folded point's k-th-root
    coset per step instead of a conjugate pair (the k=2 special case).

    Additive to FoldableCode, not a replacement — a code may implement both
    (ReedSolomon does). The binary pair seam is left untouched so the k=2 path
    stays byte- and XLA-identical, while this k-group seam serves arbitrary-factor
    consumers. The two do not collapse into one: the single-group fold is Lagrange
    interpolation (`reed_solomon.fri_fold_k`), which at k=2 is the conjugate
    butterfly's strictly costlier twin, so they coexist by design.
    Every method here is the k-ary mirror of a `FoldableCode` pair method, named
    `*group*` to sit alongside it."""

    fold_factor: int

    def fold_group(self, codeword: Array, beta: Array) -> Array:
        """Fold a layer by `beta`, dividing its length by `fold_factor` (prover
        side) — the k-ary counterpart of `FoldableCode.fold`."""
        ...

    def group_leaves(self, codeword: Array) -> Array:
        """Arrange a layer's codeword into its k-group leaves `[n // k, k]`: row
        `p` holds the `fold_factor` entries `group_indices(p, level)` whose fold
        lands at `p`, so one Merkle path opens the whole group. The k-ary
        `pair_leaves`."""
        ...

    def group_indices(self, positions: Array, level: int) -> tuple[Array, ...]:
        """The `fold_factor` leaf indices of layer `level`'s group whose fold
        lands at `positions` in layer `level + 1` — the k-ary `pair_indices`,
        returning k indices instead of a (lo, hi) pair."""
        ...

    def fold_group_values(
        self, group: Array, beta: Array, positions: Array, level: int
    ) -> Array:
        """Fold opened k-groups of layer `level` at `positions` (verifier side).

        `group` is `[Q, k]`, the layer's entries at `group_indices(positions,
        level)`. Must agree with `fold_group`: with `g = group_indices(p, level)`,
        `fold_group(layer, beta)[p] == fold_group_values(layer[g], beta, p,
        level)`. The k-ary `fold_values`."""
        ...

    def group_layer_positions(self, positions: Array, num_rounds: int) -> list[Array]:
        """Per-layer folded query indices for sampled `positions` under k-ary
        folding: element `i` addresses layer `i`'s group via `group_indices` and
        is where that fold lands in layer `i + 1`. The k-ary `layer_positions`."""
        ...

    def check_final(self, final: Array, claim: Array) -> Array:
        """Whether the fully folded layer is the base-code encoding of the scalar
        `claim` — identical to FoldableCode's terminal check (fold arity does not
        change the constant-polynomial membership test)."""
        ...

fold_group 

fold_group(codeword: Array, beta: Array) -> Array

Fold a layer by beta, dividing its length by fold_factor (prover side) — the k-ary counterpart of FoldableCode.fold.

Source code in zorch/coding/foldable_code.py 
91
92
93
94
def fold_group(self, codeword: Array, beta: Array) -> Array:
    """Fold a layer by `beta`, dividing its length by `fold_factor` (prover
    side) — the k-ary counterpart of `FoldableCode.fold`."""
    ...

group_leaves 

group_leaves(codeword: Array) -> Array

Arrange a layer's codeword into its k-group leaves [n // k, k]: row p holds the fold_factor entries group_indices(p, level) whose fold lands at p, so one Merkle path opens the whole group. The k-ary pair_leaves.

Source code in zorch/coding/foldable_code.py 
 96
 97
 98
 99
100
101
def group_leaves(self, codeword: Array) -> Array:
    """Arrange a layer's codeword into its k-group leaves `[n // k, k]`: row
    `p` holds the `fold_factor` entries `group_indices(p, level)` whose fold
    lands at `p`, so one Merkle path opens the whole group. The k-ary
    `pair_leaves`."""
    ...

group_indices 

group_indices(
    positions: Array, level: int
) -> tuple[Array, ...]

The fold_factor leaf indices of layer level's group whose fold lands at positions in layer level + 1 — the k-ary pair_indices, returning k indices instead of a (lo, hi) pair.

Source code in zorch/coding/foldable_code.py 
103
104
105
106
107
def group_indices(self, positions: Array, level: int) -> tuple[Array, ...]:
    """The `fold_factor` leaf indices of layer `level`'s group whose fold
    lands at `positions` in layer `level + 1` — the k-ary `pair_indices`,
    returning k indices instead of a (lo, hi) pair."""
    ...

fold_group_values 

fold_group_values(
    group: Array, beta: Array, positions: Array, level: int
) -> Array

Fold opened k-groups of layer level at positions (verifier side).

group is [Q, k], the layer's entries at group_indices(positions, level). Must agree with fold_group: with g = group_indices(p, level), fold_group(layer, beta)[p] == fold_group_values(layer[g], beta, p, level). The k-ary fold_values.

Source code in zorch/coding/foldable_code.py 
109
110
111
112
113
114
115
116
117
118
def fold_group_values(
    self, group: Array, beta: Array, positions: Array, level: int
) -> Array:
    """Fold opened k-groups of layer `level` at `positions` (verifier side).

    `group` is `[Q, k]`, the layer's entries at `group_indices(positions,
    level)`. Must agree with `fold_group`: with `g = group_indices(p, level)`,
    `fold_group(layer, beta)[p] == fold_group_values(layer[g], beta, p,
    level)`. The k-ary `fold_values`."""
    ...

group_layer_positions 

group_layer_positions(
    positions: Array, num_rounds: int
) -> list[Array]

Per-layer folded query indices for sampled positions under k-ary folding: element i addresses layer i's group via group_indices and is where that fold lands in layer i + 1. The k-ary layer_positions.

Source code in zorch/coding/foldable_code.py 
120
121
122
123
124
def group_layer_positions(self, positions: Array, num_rounds: int) -> list[Array]:
    """Per-layer folded query indices for sampled `positions` under k-ary
    folding: element `i` addresses layer `i`'s group via `group_indices` and
    is where that fold lands in layer `i + 1`. The k-ary `layer_positions`."""
    ...

check_final 

check_final(final: Array, claim: Array) -> Array

Whether the fully folded layer is the base-code encoding of the scalar claim — identical to FoldableCode's terminal check (fold arity does not change the constant-polynomial membership test).

Source code in zorch/coding/foldable_code.py 
126
127
128
129
130
def check_final(self, final: Array, claim: Array) -> Array:
    """Whether the fully folded layer is the base-code encoding of the scalar
    `claim` — identical to FoldableCode's terminal check (fold arity does not
    change the constant-polynomial membership test)."""
    ...