perf(transcript): direct sponge-squeeze challenges, drop ChaCha20 (⚠️ proof-breaking) - #841
Conversation
…aCha20 The Fiat-Shamir challenge sampler seeded a fresh ChaCha20Rng from every 32-byte Keccak squeeze and pulled the field element from the keystream. On the recursion guest that ChaCha block is pure software (Keccak is a precompile, ChaCha is not), so it dominated the challenge-sampling cost while producing randomness the sponge already yields for free — ~2-3M guest instructions per proof across β/z/γ and the per-FRI-layer ζ's. Replace it with a Plonky3-style duplex challenger: `DefaultTranscript` now holds a 32-byte output buffer, and `sample_field_element`/`sample_u64` rejection-sample 64-bit candidates straight from the squeeze bytes (8 bytes at a time), refilling with one squeeze when drained. A cubic-extension element (3 coordinates) usually costs a single squeeze instead of a squeeze + a ChaCha block. Rejection sampling (`< GOLDILOCKS_PRIME`) is unchanged, so the distribution stays exactly uniform; squeezing field elements directly from the sponge is the standard FS instantiation (Plonky3/Winterfell), so soundness is preserved (arguably cleaner — ChaCha only expanded the same 32-byte seed). - `HasDefaultTranscript::get_random_field_element_from_rng(rng)` → `sample_field_element_from(next_u64)` (Goldilocks + cubic ext). - Output buffer is invalidated on every absorb (`append_bytes`/`append_field_element`) so a squeeze never reflects input appended after it; `Clone` copies the buffer, keeping the snapshot/restore contract byte-identical (the GPU-FRI fallback relies on it). - Drops `rand` + `rand_chacha` from crypto's non-dev dependencies (they were ChaCha-only). BREAKING: this changes the Fiat-Shamir hash-to-field, so all proofs and the pinned recursion ELFs must be regenerated — it is a transcript hard-fork, not a verifier-only change. Prover and verifier share `DefaultTranscript`, so they move in lockstep automatically. Validated: 190 stark prove→verify roundtrips pass (prover↔verifier lockstep with the new sampler), 47 crypto tests pass (snapshot/restore + sampling determinism), clippy clean. Guest-cycle benchmark = server (no local RISC-V toolchain).
|
/bench-verify |
|
⏳ Benchmark started on the bench server. The verifier bench takes ~5 min; the recursion-guest cycle comparison then adds guest builds — a few minutes when cached, up to ~1h on a cold run. The bench server is occupied until it finishes. |
Verifier benchmark —
|
| Metric | main | PR | Δ |
|---|---|---|---|
| Verify time (per-side) | 3.586s | 3.587s | +0.03% ⚪ |
| Proof size | 204.30 MiB | 204.30 MiB | +0.00% ⚪ |
Per-side (
⚠️ PR REJECTS the baseline's valid proof — likely a VERIFY REGRESSION, not a format change): A/B/B/A cancels machine drift but not proof-specific variance — read the Verify-time Δ as approximate.
pairs: 20 mean A (PR): 3.587s mean B (main): 3.586s
[parametric] paired-t mean +0.03% sd 0.61% se 0.14%
95% CI: [-0.25%, +0.32%] (t df=19 = 2.093)
[robust] median -0.01% Wilcoxon W+=102 W-=88 p(exact)=0.7983 (z=+0.26)
run-to-run jitter: A CV 0.43% B CV 0.33% (lower = steadier)
within-session drift: -0.19% over the run, 1st->2nd half -0.17%
⚪ INCONCLUSIVE — effect not separable from 0 at n=20 (point estimate ~-0.01%). Add pairs to resolve.
Drift-free interleaved A/B/B/A measurement. - = PR faster. Trust the verdict when paired-t and Wilcoxon agree.
Recursion guest cycles (main vs PR)
=== Recursion-guest cycle comparison — single query (blowup=2, 1 query) — deterministic to ~±100k cycles ===
REF_B (baseline) origin/main a864832 guest=recursion-min.elf
REF_A (PR) a7a0322 a7a0322 guest=recursion-min.elf
| Metric | REF_B (baseline) | REF_A (PR) | Δ (A-B) |
|---|---|---|---|
| Guest cycles | 43.6M | 42.0M | -1.6M (-3.75%) |
| Keccak calls | 3025 | 3025 | 0 |
note: cycles reproduce to ~±100k (build codegen + proof nondeterminism); treat sub-100k deltas as noise, not signal.
raw (exact integer counts)
ref_b_sha=a8648320867f7f4242fe286a5b266ffed1fb5519 ref_b_elf=recursion-min.elf ref_b_cycles=43608950 ref_b_keccak=3025 ref_b_execute_wall_s=1
ref_a_sha=a7a03227aa03853a08e4292e9922900bd52642c9 ref_a_elf=recursion-min.elf ref_a_cycles=41974211 ref_a_keccak=3025 ref_a_execute_wall_s=2
delta_cycles=-1634739 delta_keccak=0
|
/bench-verify |
|
⏳ Benchmark started on the bench server. The verifier bench takes ~5 min; the recursion-guest cycle comparison then adds guest builds — a few minutes when cached, up to ~1h on a cold run. The bench server is occupied until it finishes. |
|
/bench |
Benchmark — ethrex 20 transfers (median of 3)Table parallelism: auto (cores / 3)
Commit: b906bdd · Baseline: cached · Runner: self-hosted bench |
There was a problem hiding this comment.
⚠️ AI-generated review. Produced by an automated agent and posted from this account — not written by hand. Findings below are leads to verify, not confirmed conclusions.
This PR replaces ChaCha20 expansion with direct duplex squeezes in the Fiat-Shamir transcript, buffering 4 candidates per squeeze. The core change holds up: the sponge already yields uniform bytes, the rejection bound is unchanged, and the Keccak call count stays flat (3025 → 3025), so the ~1.6M cycles are pure ChaCha removal; FS ordering is preserved at the FRI commit loop, grinding seed and query-index call sites, and next_sample_u64's slice is guarded by out_pos + 8 > SQUEEZE_LEN, so no new panic path is introduced. The open issues are test coverage and the benchmark record.
crypto/crypto/src/fiat_shamir/default_transcript.rs:117 — the absorb-invalidation is the only new soundness-critical line in this PR and no test covers it. crypto/stark/src/fri/mod.rs:90 samples ζₖ (leaving buffered bytes), line 106 absorbs rootₖ, then the loop samples ζₖ₊₁; delete self.out_pos = SQUEEZE_LEN; from append_bytes/append_field_element and ζₖ₊₁'s leading coordinate comes from the pre-root squeeze — the prover knows part of the next FRI challenge before committing the layer. Every test in default_transcript_tests.rs still passes with those lines removed (they either use raw sample() only, or absorb while the buffer is already empty), as does the whole prove→verify suite and the FRI replay at crypto/stark/src/tests/fri_tests.rs:208: prover and verifier consume the same stale bytes in lockstep, so "190 roundtrips pass" is precisely the check that cannot see this. Missing test: two transcripts each sample_field_element() (leaving buffered bytes), one then append_bytes(b"x"), assert the next sample_field_element() differs — same for append_field_element and for an interleaved raw sample().
crypto/crypto/tests/transcript_snapshot.rs:24 — the Clone-snapshot test that the GPU fallback contract depends on is blind to the newly added state. It snapshots right after append_bytes(b"prelude"), so out_pos == SQUEEZE_LEN at that point, and it compares only state(), which is hasher.clone().finalize() and never observes out_buf/out_pos; a Clone that dropped the buffer passes it unchanged. The real snapshot is taken mid-buffer: γ is sampled at prover.rs:1475 (3 coords, 8 bytes left over) and nothing is absorbed before try_fri_commit_gpu's transcript.clone() at gpu_lde.rs:1835, so the first post-snapshot operation consumes the leftovers. A lossy restore would have the CPU fallback squeeze fresh bytes for ζ₀ while the verifier consumes the leftovers — a rejected proof appearing only on the GPU-failure path. Take the snapshot immediately after a sample_field_element() with no absorb after it, and assert the restored transcript replays identical subsequent sampled values instead of comparing state().
Bench record — the last /bench here is red: 30.840s → 38.056s (+23.4%), 57086 MB → 72987 MB (+27.9%), low variance. This diff cannot produce that: the prover does a few thousand samples per proof, each now strictly cheaper and allocation-free, and the struct grows by 40 bytes of stack — there is no mechanism for 15.9 GB of heap. It reads as a baseline artifact problem: benchmark-pr.yml's "Download baseline artifact" step takes the newest successful main-push run rather than one pinned to this branch's merge-base, and e9e7b24e had just merged #832/#847/#843/#844/#845 in. The head also moved to 2d2aeaaf while the run was in flight, so the recorded number is not even for the current head. Rerun on 2d2aeaaf against a fresh main baseline and close the flag out — a proof-breaking transcript fork shouldn't land with an unexplained 23%/28% prover regression as its last recorded result.
crypto/crypto/src/fiat_shamir/default_transcript.rs:26 — the −3.75% was measured at blowup 2 with 1 query. The removed work scales with the number of field-element challenges (β, z, γ, per-layer ζ); query-index sampling never touched ChaCha, so the ~1.6M absolute stays roughly constant while total guest cycles grow with query count. At the real inner setting (~219 queries) that headline drops to well under 1%. #846 landed the real-query-count recursion bench and is already merged into this branch — rerun there and quote the absolute per-proof saving. Relatedly, the doc comment and PR body put ChaCha at "~2–3M guest instructions/proof" while the measured total delta (which also includes whatever the buffer saves on squeezes) is 1.63M, so that figure should come down to what was actually measured.
Nits:
- crypto/crypto/src/fiat_shamir/is_transcript.rs:12 — "the inner state of the transcript that fully determines its outputs" is no longer true: a transcript refilled via
next_sample_u64and one that did a rawsample()have byte-identical hasher chains and identicalstate()but different next challenges; both current callers (grinding seed,prover.rs:1546/verifier.rs:1497) sit at protocol-synchronized points so it is safe today, but the contract should be reworded sostate()is not treated as a full transcript position. - crypto/math/Cargo.toml:18 —
randis dead in math after this trait change (no reference survives incrypto/math/src, onlybenches/goldilocks_benchmark.rs, which the existing dev-dependency covers) yet remains a mandatory dep in every consumer's graph including the guest, the opposite of the PR's stated goal; same for crypto's ownrand/rand_chachadev-deps at Cargo.toml:34-35, which nothing in that crate references now. - crypto/math/src/field/extensions_goldilocks.rs:575 — the per-coordinate loop is a verbatim copy of
GoldilocksField::sample_field_element_fromandFpEis exactly its return type;&mut closureimplementsFnMut, so three delegated calls produce the identical candidate stream and keep the rejection bound in one place. - crypto/crypto/src/tests/default_transcript_tests.rs:11 —
basic_challengepins bytes only for rawsample(), whose semantics didn't change; a known-answer test pinning the first ext3 element and asample_u64sequence crossing the refill boundary would be cheap insurance against later drift on the compatibility surface this PR breaks.
|
/bench |
…te semantics - Divergence tests for the buffer-invalidation lines (append_bytes, append_field_element, raw sample()): a removed invalidation hands out stale squeeze bytes to prover and verifier in lockstep, which roundtrip suites structurally cannot see; these tests fail on it directly. - Mid-buffer clone replay test (the GPU-FRI fallback clones the transcript between samples; state()-only comparisons never observe the buffer). - Known-answer test pinning the BE / 8-byte-chunk / refill-after-4 semantics across a squeeze boundary, plus ext3 coordinate order after an absorb — any accidental change is a transcript hard-fork and shows up here instead of as a red proof. - Docs: state() no longer claims to fully determine outputs (the duplex buffer position is deliberately not part of it). - Dedup: the ext3 sampler now delegates to the base-field rejection sampler, coordinate by coordinate (behavior-identical, covered by the known-answer test). - Drop dead rand deps: the mandatory rand in math and the rand/rand_chacha dev-deps in crypto were unused since the ChaCha removal (math's benches keep their own dev-deps).
|
/bench |
|
Fresh The earlier red +5.1% was baseline skew: the cached baseline included main's ECSM/PAGE prove-path speedups while the branch was still on 0893b6b. (The bench result-comment step has been failing silently since 07-25 — numbers above are from the run log.) Also pushed |
2 participants
What
The Fiat-Shamir challenge sampler seeded a fresh
ChaCha20Rngfrom every 32-byte Keccak squeeze and pulled the field element from the keystream (default_transcript.rs). On the recursion guest, that ChaCha block is pure software — Keccak is a precompile, ChaCha is not — so it dominated the challenge-sampling cost (~2–3M guest instructions/proof across β/z/γ and the per-FRI-layer ζ's) while producing randomness the sponge already yields for free.This replaces it with a Plonky3-style duplex challenger:
DefaultTranscriptholds a 32-byte output buffer, andsample_field_element/sample_u64rejection-sample 64-bit candidates straight from the squeeze bytes (8 at a time), refilling with one squeeze when drained. A cubic-extension element (3 coords) usually costs a single squeeze instead of a squeeze + a ChaCha block.Why it's sound
< GOLDILOCKS_PRIME) is unchanged → distribution stays exactly uniform.DefaultTranscript, so they derive identical challenges automatically (validated by the roundtrip suite).Details
HasDefaultTranscript::get_random_field_element_from_rng(rng)→sample_field_element_from(next_u64)(Goldilocks + cubic ext).append_bytes/append_field_element) so a squeeze never reflects input appended after it;Clonecopies the buffer, keeping the snapshot/restore contract byte-identical (the GPU-FRI fallback intry_fri_commit_gpudepends on it).rand+rand_chachafrom crypto's non-dev dependencies (ChaCha-only).This changes the Fiat-Shamir hash-to-field, so all proofs and the pinned recursion ELFs must be regenerated — it is a transcript hard-fork, not a verifier-only change. CI must recompile the recursion ELFs; any committed proof fixtures / pinned program-id digests regenerate.
Validation