Skip to content

zorch.sumcheck.sqrt_space

SqrtSpace sumcheck (Algorithm 2): a sumcheck proving the same round polynomials as the linear-time prover while holding only O(√N) folded state.

The first l/2 rounds never fold the factors — they keep the running eq(r[<i], ·) table and refold over the bound prefix on the fly (Formula 10, √-space for recompute). The tail is a plain sumcheck (summand_evals + fold) over the state folded down at the phase boundary. Messages match a linear-time prover on the same challenges (testing/sqrt_space_test.py).

Generic over two orthogonal axes: the round summand (the SumcheckSummand seam StandardRound and ProductSummand share) and the sampling EvalDomain. The √-space memory trick refolds each factor independently, so it is orthogonal to how the factors combine AND to where the round poly is sampled. Defaults keep a product sumcheck on the compressed Û_degree domain, so prove_sqrt_space(p) is unchanged; pass a homogeneous summand and/or another EvalDomain (Gruen {0,1,extra,eq_root(z)}, {0,½}, {0,2,4}) to retarget it. The ∞-leading Û message needs a homogeneous summand (leading coeff = combine(slopes)); a finite domain lifts that restriction for any summand.

SqrtSpaceRound

Bases: ProverRound

One first-phase round: refold on the fly, send the summand's round poly over the sampling domain, and extend the eq table by the sampled challenge (the factors stay put). Bound to a SumcheckSummand and an EvalDomain.

challenges is shared with StandardRound, so both phases use one challenge-field and squeeze policy. This lets a √-space run serve as the tail of an extension-field sumcheck without a second configuration spelling.

Source code in zorch/sumcheck/sqrt_space.py 
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class SqrtSpaceRound(ProverRound):
    """One first-phase round: refold on the fly, send the summand's round poly over
    the sampling domain, and extend the eq table by the sampled challenge (the
    factors stay put). Bound to a SumcheckSummand and an EvalDomain.

    `challenges` is shared with `StandardRound`, so both phases use one
    challenge-field and squeeze policy. This lets a √-space run serve as the tail
    of an extension-field sumcheck without a second configuration spelling."""

    def __init__(
        self,
        summand: SumcheckSummand,
        domain: EvalDomain,
        challenges: ChallengePolicy,
    ) -> None:
        self.summand = summand
        self.domain = domain
        self.challenges = challenges

    def _round_poly(self, state: SqrtSpaceState) -> Array:
        return summand_evals(
            compute_folded_evaluations(*state), self.summand._combine, self.domain
        )

    def __call__(
        self, carry: FoldingClaim, transcript: Transcript
    ) -> tuple[FoldingClaim, Transcript, Array]:
        p_stacked, eq_evals = carry.state
        msg = self._round_poly(carry.state)
        transcript, r = self.challenges.observe_and_sample(transcript, msg)
        reduced, _ = reduce_domain(carry.claim.value, msg, r, self.domain)
        folded = (p_stacked, expand_hypercube_step(eq_evals, r))
        return carry.advance(folded, reduced, r), transcript, msg

compute_folded_evaluations 

compute_folded_evaluations(
    p_stacked: Array, eq_evals: Array
) -> Array

Refold the factors over the bound prefix (Equation 4): pₖ(r[<i], x') = Σ_b eq(r[<i], b)·pₖ(b, x'), returning (d, 2ˡ⁻ⁱ).

Source code in zorch/sumcheck/sqrt_space.py 
47
48
49
50
51
52
53
54
def compute_folded_evaluations(p_stacked: Array, eq_evals: Array) -> Array:
    """Refold the factors over the bound prefix (Equation 4):
    pₖ(r[<i], x') = Σ_b eq(r[<i], b)·pₖ(b, x'), returning (d, 2ˡ⁻ⁱ)."""
    d = p_stacked.shape[0]
    l = log2_strict_usize(p_stacked.shape[1])
    i = log2_strict_usize(eq_evals.shape[0])
    p_reshaped = fnp.reshape(p_stacked, (d, 1 << i, 1 << (l - i)))
    return (p_reshaped * eq_evals[None, :, None]).sum(axis=1)

prove_sqrt_space 

prove_sqrt_space(
    p_initial: Array,
    claim: Array,
    transcript: Transcript,
    summand: SumcheckSummand | None = None,
    domain: EvalDomain | None = None,
    *,
    challenges: ChallengePolicy
) -> tuple[Array, Transcript, list[Array]]

Prove the sumcheck: √-space first phase, standard second phase. summand defaults to the product over the factors (ProductSummand) and domain to the compressed Û_degree; pass a homogeneous SumcheckSummand and/or another EvalDomain to retarget the engine. challenges configures both phases; an extension policy makes this a drop-in tail for univariate skip. Returns the final folded factors (d, 1) beside the reduced claim, the transcript, and all l messages. Both phases reduce the claim as they fold, so a caller gets the reduced claim without replaying its own proof.

Source code in zorch/sumcheck/sqrt_space.py 
 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
131
132
def prove_sqrt_space(
    p_initial: Array,
    claim: Array,
    transcript: Transcript,
    summand: SumcheckSummand | None = None,
    domain: EvalDomain | None = None,
    *,
    challenges: ChallengePolicy,
) -> tuple[Array, Transcript, list[Array]]:
    """Prove the sumcheck: √-space first phase, standard second phase. `summand`
    defaults to the product over the factors (ProductSummand) and `domain` to the
    compressed Û_degree; pass a homogeneous SumcheckSummand and/or another EvalDomain
    to retarget the engine. `challenges` configures both phases; an extension
    policy makes this a drop-in tail for univariate skip. Returns the final
    folded factors (d, 1) beside the reduced claim, the transcript, and all l
    messages. Both phases reduce the claim as they fold, so a caller gets the
    reduced claim without replaying its own proof."""
    summand = summand or ProductSummand(degree=p_initial.shape[0])
    domain = domain or uhat_domain(summand.degree, p_initial.dtype)
    l = log2_strict_usize(p_initial.shape[1])
    l_half = l // 2

    state: SqrtSpaceState = (p_initial, fnp.ones(1, dtype=p_initial.dtype))
    start = RunningClaim(claim, fnp.zeros((l,), challenges.dtype), fnp.int32(0))
    carry, transcript, phase1 = fold_rounds(
        SqrtSpaceRound(summand, domain, challenges),
        FoldingClaim(state, start),
        transcript,
        l_half,
    )

    # Boundary: materialize the deferred state — fold the whole bound prefix down at
    # once — then run standard sumcheck rounds over the explicit evaluations.
    folded = compute_folded_evaluations(*carry.state)
    carry, transcript, phase2 = fold_rounds(
        StandardRound(summand, domain, challenges=challenges),
        FoldingClaim(folded, carry.claim),
        transcript,
        l - l_half,
    )
    return carry, transcript, phase1 + phase2