3. Attested Queries, No-Omission Proofs, Audit Logs, & Recursive Aggregation
To prove that no record in a training set or log matches a forbidden pattern, verifying per-record parse/complement certificates is not enough: the verifier must also know that the server or trainer did not omit any record from the scan.
3.1 Dense Positional Non-Omission: Merkle Mountain Ranges (MMR.lean & dregg-query/src/mmr.rs)
In MMR.lean (commits ffd97ecf3 and 27259d03e, 2026-06-11; hardened in ed616d24c and ee18461c1, 2026-08-01), an append-only log $L : \text{List } \mathbb{Z}$ is decomposed into a canonical forest of complete binary peaks peaksOf L : List (MTree ℤ) with strictly decreasing heights (Mountains), whose root is bagged right-to-left via mroot hash L:
theorem forestLeaves_peaksOf (L : List ℤ) : forestLeaves (peaksOf L) = L
theorem peaksOf_mountains (L : List ℤ) : Mountains (peaksOf L)
theorem mroot_binds_or_collides (hash : List ℤ → ℤ) {L₁ L₂ : List ℤ}
(h : mroot hash L₁ = mroot hash L₂) :
L₁ = L₂ ∨ SpongeColl hash (mrootFind hash L₁ L₂)For any dense positional range $[lo, hi]$, RVerifies L lo hi vals checks that vals has exact length rangeCount L.length lo hi and every element vals[j] opens at position lo + j in L. Ember proves in MMR.lean that RVerifies is both sound and complete (rverifies_iff_exact), and therefore a server cannot omit any position:
def RVerifies (L : List ℤ) (lo hi : ℕ) (vals : List ℤ) : Prop :=
vals.length = rangeCount L.length lo hi ∧
∀ j v, vals[j]? = some v → Opens L (lo + j) v
theorem range_complete {L : List ℤ} {lo hi : ℕ} {vals : List ℤ}
(hv : RVerifies L lo hi vals) :
∀ i, lo ≤ i → i ≤ hi → i < L.length →
∃ v, vals[i - lo]? = some v ∧ Opens L i v
theorem rverifies_iff_exact {L : List ℤ} {lo hi : ℕ} {vals : List ℤ} :
RVerifies L lo hi vals ↔ vals = mrange L lo hi
theorem server_cannot_omit_position (hash : List ℤ → ℤ)
{L L' : List ℤ}
(hroot : mroot hash L' = mroot hash L)
(hno : ¬ MRootColl hash L' L)
{lo hi : ℕ} {vals : List ℤ}
(hv : RVerifies L' lo hi vals) :
vals = mrange L lo hi ∧
∀ i, lo ≤ i → i ≤ hi → i < L.length →
∃ v, vals[i - lo]? = some v ∧ Opens L i vIn MMR.lean, server_cannot_omit_position is welded directly to RecursiveAggregation.light_client_verifies_whole_history via CommitBindsMMR, yielding light_client_position_non_omission:
theorem light_client_position_non_omission
(Proof : Type) (verify : Proof → Bool)
(CH : Dregg2.Exec.CellId → Dregg2.Exec.Value → ℤ)
(RH : Dregg2.Exec.RecordKernelState → ℤ)
(cmb : ℤ → ℤ → ℤ) (compress : ℤ → ℤ → ℤ) (compressN : List ℤ → ℤ)
(hash : List ℤ → ℤ) (hCR : Poseidon2SpongeCR hash)
(extractMMR : List ChainStep → List ℤ)
(agg : Aggregate Proof) (g : RecChainedState) (steps : List ChainStep)
(es : EngineSound Proof verify CH RH cmb compress compressN agg g steps)
(hweld : CommitBindsMMR CH RH cmb compress compressN hash extractMMR g steps)
(hroot : verify agg.root = true)
{L' : List ℤ}
(hmroot : mroot hash L' = mroot hash (extractMMR steps))
{lo hi : ℕ} {vals : List ℤ}
(hv : RVerifies L' lo hi vals) :
vals = mrange (extractMMR steps) lo hi ∧
(∀ i, lo ≤ i → i ≤ hi → i < (extractMMR steps).length →
∃ v, vals[i - lo]? = some v ∧ Opens (extractMMR steps) i v) ∧
AggregateAttests Proof CH RH cmb compress compressN agg g stepsIn Rust, dregg-query/src/mmr.rs implements MmrHasher, Blake3Mmr (with domain tags "dregg-query-mmr-v1:{empty,leaf,node,bag}"), Peak, MmrProof, RangeOpening, and verify_range:
verify_rangerejects non-strictly-decreasing peak heights, checksbag_peaks::<H>(&opening.peaks) == root, derives the exact log lengthlen = Σ (1 << peak.height)from the committed peak heights, checksopening.values.len() == range_count(len, lo, hi)(returningRangeCountMismatchif any item is dropped), and verifies each leaf's Merkle path up to its peak using direction bits derived solely from the dense offset(offset >> level) & 1.
3.2 Key-Range Non-Omission & Gap Exclusion (HistoryIndex.lean, AttestedQuery.lean, dregg-query)
When querying by key rather than dense position (e.g., (subject, height, seq) in HistoryIndex.lean), positions are sparse, so a contiguous slice of results could still hide a matching key unless boundary gaps are proven empty. In HistoryIndex.lean and AttestedQuery.lean:
ReceiptKey := ℤ ×ₗ (ℤ ×ₗ ℤ)andReceiptIndex := List (ReceiptKey × ℤ), committed viairoot hash idx.inductive Gap (κ : Type u)witnesses an open interval(a, b)of adjacent keys in a sorted listlcontaining no keys betweenaandb:
inductive Gap (κ : Type u)
| empty
| below (b : κ)
| inner (a b : κ)
| above (a : κ)
theorem Gap.excludes {l : List κ} {g : Gap κ} {k : κ}
(hs : Sorted l) (hv : g.Valid l) (hc : g.covers k) : k ∉ l- An
Answer κ νcarriesitems : List (κ × ν)plus boundary gap witnessesleftGap : Gap κandrightGap : Gap κ.Verifies h lo hi anschecks thatitemsis a contiguous sublist (IsInfix) of the sorted indexhand thatleftGap/rightGapbridgelotoitems.headanditems.lasttohi(or cover[lo, hi]whenitems = []). - Key-Range Non-Omission Theorem (AttestedQuery.lean):
def AnswerComplete (h : List (κ × ν)) (lo hi : κ) (ans : Answer κ ν) : Prop :=
∀ e ∈ h, inRange lo hi e.1 → e ∈ ans.items
theorem answer_complete {h : List (κ × ν)} {lo hi : κ} {ans : Answer κ ν}
(hs : SortedKeys h) (hv : Verifies h lo hi ans) :
AnswerComplete h lo hi ans
theorem server_cannot_omit (hash : List ℤ → ℤ) (hCR : Poseidon2SpongeCR hash)
{idx idx' : ReceiptIndex}
(hs : SortedKeys idx)
(hroot : iroot hash idx' = iroot hash idx)
{lo hi : ReceiptKey} {ans : Answer ReceiptKey ℤ}
(hv : Verifies idx' lo hi ans) :
AnswerComplete idx lo hi ans ∧
(∀ e ∈ ans.items, e ∈ idx ∧ inRange lo hi e.1)Notice the empty-answer case (ans.items = []): Verifies requires ans.leftGap.Valid keys ∧ ans.leftGap.covers lo ∧ ans.leftGap.covers hi. By convexity of Gap.covers and Gap.excludes, every key $k \in [lo, hi]$ is proven absent ($k \notin \text{keys}$) from the committed index!
3.3 dregg-query Attested Slices, Paged Windows, CALM Classification, & Zero-Count Aggregation
In dregg-query/src/:
attested.rs:RangeCertificatewrapsRangeOpening,lo, andhi.AttestedSlicepairsreceipts: Vec<TurnReceipt>withcert: RangeCertificate.AttestedSlice::verify(&self, expected_root: &[u8; 32])checksself.receipts.len() == self.cert.opening.values.len(), verifies eachreceipt.receipt_hash().0 == leaf, and runsverify_range::<Blake3Mmr>(expected_root, self.cert.lo, self.cert.hi, &self.cert.opening).Coverage(Coverage::WholeLogvsCoverage::Range { lo, hi }) andAttestedAnswer:AttestedAnswer::verify(&self, expected_root: &[u8; 32])enforces thatCoverage::WholeLogcoverslo == 0and(len == 0) || (hi + 1 >= len)(refusingPartialCoverageForWholeLogif truncated), extracts the EDBFactBasefrom the verified receipts, re-evaluateseval(&base, &self.query), and checksrecomputed == self.rows(AnswerMismatchif tampered).windows.rs:verify_windows(expected_root: &[u8; 32], windows: &[IndexRangeResponse]) -> Result<Vec<TurnReceipt>, WindowVerifyError>stitches paged range responses into a single fail-closed whole-log read: it checks that every window's node attestation is signed by the samenode_pubkeyand bindsexpected_root, checkslo == expected_lo(rejecting overlaps or gaps withWindowGapOrOverlap), guards againsthi == usize::MAXarithmetic overflow, verifies eachslice.verify(expected_root), and requiresexpected_lo == lenat the end (LogTailTruncatedif the tail is omitted).classify.rs&query.rs:classify(q: &Query) -> CoordinationClassimplements the CALM theorem classifier: positive conjunctive queries areCoordinationClass::Monotone(valid on prefixes), whereas queries usingnot_atom(negation) oraggregate(AggOp::{Count, Sum, Min, Max}) areCoordinationClass::FinalizedDependentand require aCoverage::WholeLogno-omission proof.- Crucially, in
aggregate(), whengroup_byis empty (a global aggregate) andAggOp::Countis evaluated over an empty match set (rows.is_empty()), it emits a single row[Value::Int(0)]—a cryptographically attestedcount = 0absence verdict over the whole log!
3.4 Audit Log Proofs (audit/src/log.rs, audit/src/proofs.rs, audit/src/budget.rs)
In dregg-audit, AuditLog<H: TreeHash> maintains a 4-ary append-only Merkle tree (ARITY = 4) over AuditEntry records (generic over PoseidonTreeHash and Blake3TreeHash) with four verifiable proof types in proofs.rs and budget.rs:
CountProof: Proves the exact total entry count (count: u64) underroot: [u8; 32]in $O(\log_4 N)$ size via the rightmost spineright_spine: Vec<SpineStep>(CountProof::verifychecks that every step uses the last populated child slot and reconstructsroot).RangeProof: Proves that a contiguous slice of entries[start, end)is complete and unmodified underroot(RangeProof::verifychecksentries.len() == end - startand verifies boundary + sample inclusion proofs).ConsistencyProof: Proves thatold_root(atold_size) is a prefix ofnew_root(atnew_size).BudgetProof: Combines aRangeProofover[0, log_size)withCountProof(completeness_proof) to prove that the sum of resource usage matching aBudgetDimension(ActionCountorParamSum) across the entire log isclaimed_total <= limit—and whenlimit = 0, proves zero occurrences (claimed_total == 0) across the entire log!
3.5 Recursive Aggregation & Training-Set / Corpus Custody (turn-prover, RecursiveAggregation.lean, zkml-research, minidregg)
- 3-Level STARK Recursion & Bilateral Bundle Aggregation (
turn-prover/src/lib.rs,aggregate_bilateral_prover.rs): dregg-turn-proveraggregates $N$ per-cell/per-record STARK proofs into a constant-size outer proof (AggregatedBundlewith fixed 23-feltouter_pi, orWholeChainProofvia 3-level Plonky3 FRI recursionprove_turn_chain_recursive).- Whole-History & Genesis-Anchored Soundness (
RecursiveAggregation.lean): Aggregateexposesroot : Proof,genesisRoot : ℤ,finalRoot : ℤ,chainDigest : ℤ, andnumTurns : Nat(pinned byTurnChainBindingAir'slastRealCountBindconstraint).light_client_verifies_anchored_historyandanchored_attests_rejects_fabricated_genesisprove that a light client checking onlyverify agg.root = trueandagg.genesisRoot = expectedGenesisverifies that every step from genesis to final root executed correctly, no step was reordered/dropped/inserted, and no prefix was hidden:
theorem light_client_verifies_anchored_history
(agg : Aggregate Proof) (g : RecChainedState) (steps : List ChainStep) (expectedGenesis : ℤ)
(es : EngineSound Proof verify CH RH cmb compress compressN agg g steps)
(hroot : verify agg.root = true)
(hanchor : agg.genesisRoot = expectedGenesis) :
AnchoredAttests Proof CH RH cmb compress compressN agg g steps expectedGenesis- Training-Set & Encrypted-Weight Verification (
zkml-research,minidregg,tokenizer,dregg-doc): - In
/Users/ember/dev/zkml-research/docs/DARK-TRAINING.mdand/Users/ember/dev/zkml-research/docs/VERDICTS.md, Ember formalizes Dark Training (Selvage/Rank1GradientCheck.leansgd_step_soundandAssurance/ZkmlLowRankUpdate.leanmatVec_chainUpdate), where low-rank training updates $W' = W + AB^\top$ form an IVC chain whose accumulator state IS the model (2rdcommitted felts per step instead of $d^2$, $128\times$ smaller at $d=4096, r=16$), and each training step binds its training example $x_t$ to a committed training-set corpus root. - In
/Users/ember/dev/breadstuffs/dregg-doc/src/lib.rs, hypermedia documents and corpora are represented as Pijul-style patch graphs (DocGraph,Atom,Provenance) projected viato_heap_mapinto a sorted Poseidon2 cell heap commitment (substrate_commit) binding every atom's content and author provenance. - In
/Users/ember/dev/breadstuffs/tokenizer/src/lib.rs,dregg-tokenizerisolates secret credentials via X25519 + ChaCha20-Poly1305 (SealedSecret) behind capability-token verification. - In
/Users/ember/dev/minidregg/Pred.leanandTokenCensus.lean, thePredalgebra (Pred.HashEq,Pred.CoordinationDial) and#assert_token_censusenforce syntactic policy evaluation and private-constructor minting invariants across the kernel.
4. Git & cv Archaeological Timeline
| Date | Commit SHA | Repository / Path | Milestone & Primary-Source Significance |
|---|---|---|---|
2026-05-24 | 195870682 | breadstuffs/dfa/ | dfa: add AIR API (compile_to_air, verify_acceptance) + federation verifier scaffold |
2026-06-11 | ffd97ecf3 | breadstuffs/metatheory/Dregg2/Lightclient/ | non-omission: attested queries — the server cannot hide a receipt (Lean foundation) (MMR.lean, HistoryIndex.lean, AttestedQuery.lean) |
2026-06-11 | 27259d03e | breadstuffs/metatheory/ | EPOCH foundations (Lean): Blum memory-checking + descriptor IR v2 + the v2 re-anchor + MMR receipt index |
2026-06-12 | 0f6e1eb3c | breadstuffs/dregg-query/ | dregg-query: attested queries over the receipt fact-base (18/18, leaf crate) |
2026-06-14 | 9cfe3361d | breadstuffs/dregg-query/ | dregg-query: attested queries — a result carries a proof it's a faithful read of finalized state |
2026-06-25 | 2c50c7c8d | breadstuffs/metatheory/Dregg2/Crypto/Deriv/ | feat(deriv): Stage 0 — PredRE + der/null/derives/Matches over dregg's Pred (#assert_axioms-clean) |
2026-06-25 | b909fc44a | breadstuffs/metatheory/Dregg2/Crypto/Deriv/ | feat(deriv): Stage 1 — correctness : derives ↔ Matches over PredRE (#assert_axioms-clean) |
2026-06-25 | b347c0f7b | breadstuffs/dfa/src/ | feat(dfa): derivative FilterTree compiler + Pattern::Not (Stage 2, AIR-neutral) |
2026-06-25 | 8ba854ce5 | breadstuffs/metatheory/Dregg2/Crypto/Deriv/ | feat(deriv): Stage 3 CAPSTONE — der_finite, Brzozowski finiteness over PredRE (#assert_axioms-clean) |
2026-06-25 | 41bedeeab | breadstuffs/metatheory/Dregg2/Crypto/Deriv/ | feat(deriv): Stage 4 CLOSE (table-opaque) — TableDfa faithfulness, the compiled table's meaning is a THEOREM |
2026-06-25 | 85179be00 | breadstuffs/metatheory/Dregg2/Crypto/Deriv/ | feat(deriv): CLOSE ThompsonRecognizes — explicit Thompson ε-NFA + kernel-clean correctness |
2026-06-26 | e85a7d9b8 | breadstuffs/dregg-query/ | feat(dregg-query): richer EDB + Q3 aggregation + the CommitBindsMMR trust-anchor design |
2026-06-30 | e9f12605f | breadstuffs/metatheory/ | feat: whole-history non-omission real-as-deployed + the universal sub-proof-folding primitive |
2026-07-06 | 28523fb8f | breadstuffs/metatheory/Dregg2/Crypto/ | feat(crypto): verified zkOracle — CFG parsing, DECO composition, hypergraph + full graph rewriting |
2026-07-06 | 7526c5253 | breadstuffs/zkoracle-prove/ | zkoracle-prove: the zkOracle PROVER live (authentic ∧ well-formed ∧ injection-free) |
2026-07-06 | 7a373a284 | breadstuffs/zkoracle-prove/ | zkoracle-prove: close the Rust-side cross-leg weld (one committed response) |
2026-07-06 | 0eb08bf32 | breadstuffs/zkoracle-prove/, CfgCompact.lean | zkoracle: the COMPACT certificate — O(tokens) wire, proven, long-context scale |
2026-07-07 | c587ccf59 | breadstuffs/zkoracle-prove/ | stark-kill CUTOVER #1: zkOracle injection leg OFF stark.rs → plonky3 descriptor prover — 10.4× faster |
2026-07-12 | dcc69c6dd | breadstuffs/dregg-query/ | node+dregg-query: node-signed attestation binding the receipt-index MMR root (CommitBindsMMR, step 1) |
2026-07-16 | d68fd6f8f | breadstuffs/metatheory/Dregg2/Crypto/Handlebars.lean | crypto/Handlebars: injection-freedom as GENERATION, on the existing CFG stack |
2026-07-16 | 543761093 | breadstuffs/metatheory/Dregg2/Crypto/HandlebarsWitness.lean | crypto/HandlebarsWitness: the proof-PRODUCING render — every render emits its generation certificate |
2026-07-16 | 6cc8e76d8 | breadstuffs/metatheory/Dregg2/Crypto/HandlebarsCompose.lean | crypto/HandlebarsCompose: THE FIFTH THING — proof-carrying renders NEST under composition |
2026-07-17 | 5371f5582 | breadstuffs/metatheory/Dregg2/Crypto/HandlebarsGuarded.lean | crypto/HandlebarsGuarded: the attestable schema language — per-hole PredRE guards kill the arbitrary brace-ban |
2026-07-17 | 9548bfc7a | breadstuffs/metatheory/Dregg2/Crypto/DfaAsCert.lean | crypto/DfaAsCert: THE LINCHPIN — regex/DFA and CFG on one certificate substrate |
2026-07-17 | 2d71e8cf0 | breadstuffs/metatheory/Dregg2/Circuit/Emit/DyckStackEmit.lean | zk: author the Dyck parse descriptor IN LEAN (law #1) — byte-pinned |
2026-07-17 | e4072a3d4 | breadstuffs/metatheory/Dregg2/Circuit/Emit/DyckStackReplay.lean | zk: parse soundness UNCONDITIONAL — define the word from the trace, discharge the load-bearing hword |
2026-07-17 | df7645d3a | breadstuffs/metatheory/Dregg2/Crypto/VpaAsCert.lean | crypto/VpaAsCert: the visibly-pushdown rung — regex (x) VPL (x) CFG on ONE Cert substrate |
2026-07-18 | 735b76169 | breadstuffs/metatheory/Dregg2/Crypto/Deriv/ | crypto/SymbolicEmptiness: BOUNDED emptiness now SOUND ⋀ COMPLETE |
2026-07-30 | 32372fca3 | breadstuffs/metatheory/Dregg2/Circuit/Emit/ | attested automaton: OFF THE FLOOR — five theorems that assumed a refuted hypothesis now name a refutable one (AttestedAutomatonWeld8.lean) |
2026-08-14 | daa207ae7 | breadstuffs/metatheory/ | circuit!: the 211 lanes that carry no nonlinearity — permEmissionNarrow |
5. Synthesis: End-to-End Protocol for Proving the Absence of Information from a Training Set / Workload Corpus
By composing the verified primitives documented in Sections 1–3, we obtain a complete, zero-knowledge-compatible Training-Set / Workload Corpus Absence Attestation Protocol. Suppose a model trainer or workload operator holds a private training corpus $\mathcal{D} = (d_0, d_1, \dots, d_{N-1})$ and must prove to an external auditor or light client that no training record in $\mathcal{D}$ (and no gradient step in training run $W_0 \to W_T$) contains forbidden information specified by a policy $(G, P_{\text{forbid}})$—where $G$ is a structural Context-Free Grammar / Guarded Template (e.g., JSON schema or chat-turn framing) and $P_{\text{forbid}}$ is a regular pattern (e.g., SSN/PII regex, copyrighted canary string, benchmark evaluation prompt hash/substring, or injection delimiter):
sequenceDiagram
participant Corpus as Private Training Corpus D = (d_0 .. d_{N-1})
participant Prover as Workload Prover (dregg-dfa + zkoracle-prove + turn-prover)
participant Log as Committed Index / MMR (Blake3Mmr + Poseidon2 8-Lane)
participant Auditor as Light Client / Auditor
Note over Corpus,Log: Phase 1: Dataset Commitment & Per-Record Absence Witnessing
Corpus->>Log: 1. Commit each record d_i via 8-felt Poseidon2 ContentCommit c_i = hash_bytes_8(d_i)<br/>Append (key_i, c_i, metadata_i) to Blake3Mmr (mroot R_D) & ReceiptIndex (iroot I_D)
Prover->>Prover: 2. Compile forbidden pattern P_forbid via Re::not() -> complement DFA M_{~P}<br/>Emit/load Lean-authored AIR descriptors (DyckStackEmit + DfaRoutingGeneralEmit)
Corpus->>Prover: 3. Stream each record d_i (private witness)
Prover->>Prover: 4. Prove per-record Parse + Absence:<br/>(a) CompactCert replay rs_i proves d_i in G.language (well-formed structure)<br/>(b) Guarded holes / spans satisfy derives span (.neg P_forbid) = true<br/>(c) STARK proof pi_i over AttestedAutomatonWeld8 binds c_i (all 8 lanes) to M_{~P} accepting state
Note over Prover,Log: Phase 2: No-Omission Query & Zero-Match Aggregation
Prover->>Log: 5. Execute whole-corpus attested query (Coverage::WholeLog [0, N-1])<br/>for violation facts & aggregate(AggOp::Count) -> count = 0 (or audit BudgetProof limit = 0)
Prover->>Prover: 6. Fold N per-record STARKs {pi_i} + TurnChainBindingAir + Dark-Training SGD steps<br/>into a single recursive Aggregate proof (WholeChainProof) anchored at (genesisRoot, finalRoot)
Note over Prover,Auditor: Phase 3: Succinct Constant-Time Verification (Zero Dataset Disclosure)
Prover->>Auditor: 7. Ship (Aggregate.root, mroot R_D, RangeCertificate / Gap proof, CountProof = 0)
Auditor->>Auditor: 8. Verify Aggregate.root + genesisRoot == expectedGenesis<br/>Verify server_cannot_omit_position / server_cannot_omit + count == 0Step-by-Step Verification Chain & Governing Theorems
Step 1: Dual-Anchored Dataset Commitment (ContentCommit, Blake3Mmr, ReceiptIndex)
- Each training document or tokenized batch $d_i$ ($i \in \{0, \dots, N-1\}$) is committed via the 8-lane Poseidon2 sponge
content_commitment(&d_i) -> [BabyBear; 8]($\sim 123.63$-bit collision resistance, avoiding the 1-felt wound catalogued inproject-felt-width-repair-campaign.md). - Each record's receipt—binding
c_i : ContentCommitand its policy-compliance verdict tag—is appended to: - The dense positional Merkle Mountain Range
Blake3Mmrwith rootR_D = mroot hash L, and/or - The sorted key-indexed
ReceiptIndex(ReceiptKey = (subject, height, seq)) with rootI_D = iroot hash idxand the 4-aryAuditLog<PoseidonTreeHash>. - Governing Lean Theorem:
mroot_binds_or_collidesensures that underPoseidon2SpongeCR hash(or BLAKE3 collision resistance), the committed sequence $L = [r_0, \dots, r_{N-1}]$ is uniquely pinned byR_D.
Step 2: Verified Complement Compilation (Pattern::Not, Re::not(), PredRE.neg)
- The auditor specifies the forbidden information as a regular expression or predicate pattern $P_{\text{forbid}}$ (or a union of forbidden patterns $P_1 \cup P_2 \cup \dots \cup P_k$, e.g.,
* ⬝ canary_bytes ⬝ *). - Using
Pattern::Not(Box::new(P_forbid)).compile(),dregg-dfalowers $\neg P_{\text{forbid}}$ toRe::not()and compiles it via lazy Brzozowski byte-class derivatives (Re::compile()) into a flat transition tableDfa { num_states, transitions, start, accepting }. - Governing Lean Theorems:
derives_neg:derives w (.neg r) = !(derives w r)correctness:derives w (.neg r) = true ↔ Matches w (.neg r)(which unfolds to¬ Matches w r)der_finite:∃ (xs : List PredRE), ∀ {n : Nat}, steps r n ⊆[ (· ≅ ·) ] xs(guaranteeing the derivative DFA state space is finite)tableDfa_faithful:∀ w, td.accepts w ↔ Matches w (.neg r)(guaranteeing that the compiled flat table accepts $w$ if and only if $w$ does not match $r$).
Step 3: Structural Parsing Certificate & Slot Confinement (CfgCompact.Replay, HandlebarsGuarded, DyckStackEmit)
- To prevent an attacker from hiding forbidden tokens across structural boundaries (e.g., splitting a canary across JSON keys/strings or breaking out of template slots), each record $d_i$ is parsed against the corpus schema grammar $G$ (such as
json_grammar()inzkoracle-prove/src/cfg.rsor aGuardedTemplateinHandlebarsGuarded.lean), emitting an $O(\text{tokens})$ compact leftmost rule sequenceCompactCert { rules }. - When verified in-circuit via the Lean-authored pushdown parse AIR (
DyckStackEmit.dyckParseDesc) and the DFA routing AIR (DfaRoutingGeneralEmit.injectionRoutingDesc), both legs are welded to the same 8-feltContentCommit$c_i$ viaAttestedAutomatonWeld8.lean. - Governing Lean Theorems:
compact_sound:ReplayAccepts g rs input → input ∈ g.languageparse_sat_imp_replay_emit_unconditional: satisfying the byte-pinneddyckParseDescunconditionally yieldsReplayAccepts dyck (rulesOf ...) (decodedWord t n)guarded_render_mem_language&slot_confinement: every extracted slot satisfies itsPredREcomplement guard and cannot alter the surrounding structural framedfa_verify_sound&zkOracle_sound: in-circuit verification implies both grammar membership ($d_i \in G.\text{language}$) and complement satisfaction ($\text{derives } d_i\text{ } (\text{.neg } P_{\text{forbid}}) = \text{true}$).
Step 4: Cryptographic No-Omission & Zero-Count Aggregation (dregg-query, MMR.lean, AttestedQuery.lean, audit)
- Why can't the prover simply omit record $d_{42}$ (which contains the forbidden data) when generating the proof?
- Dense Positional Scan (
MMR.lean+dregg-query/src/attested.rs+windows.rs): - The query requires
Coverage::WholeLogover[0, len - 1](enforced byclassify(&q) == CoordinationClass::FinalizedDependentfor negated/aggregate queries inclassify.rsand checked byAttestedAnswer::verifyor pagedverify_windows). - By
server_cannot_omit_position,RVerifies L' 0 (L.length - 1) valsundermroot hash L' = mroot hash Lforcesvals = mrange L 0 (L.length - 1) = L: every single position $i \in [0, |L|)$ must be present and opened. - Sparse Key-Index Lookup (
AttestedQuery.lean): - If the auditor queries a specific key range
[lo, hi]inReceiptIndex(for instance, querying an index of extracted n-gram/canary keys or violation tags), an empty answerans.items = []must carry a validGapwitnessans.leftGapcovering[lo, hi]. - By
Gap.excludesandserver_cannot_omit,Verifies idx' lo hi ansprovesAnswerComplete idx lo hi ans, which forans.items = []proves $\forall e \in \text{idx}, \neg \text{inRange } lo\text{ } hi\text{ } e.1$. - Zero-Count Aggregation (
dregg-query/src/query.rs&audit/src/budget.rs): - Evaluating
Query::select(...).aggregate(vec![], vec![AggSpec { op: AggOp::Count, ... }])over the verified whole-log slice yields a single row[Value::Int(0)](query.rs:471-473), or equivalently indregg-audit,BudgetProof::verifyverifiesRangeProofover[0, log_size)+CountProof(right_spinepinning exactlog_size) withclaimed_total = 0 <= limit = 0.
Step 5: Recursive STARK Folding & Training-Run Welding (turn-prover, RecursiveAggregation.lean, DARK-TRAINING.md)
- Rather than requiring the auditor to inspect $N$ individual record proofs or $T$ individual SGD steps,
turn-proverfolds the $N$ leaf STARK proofs (via the universal sub-proof-folding primitiveprove_chain_core_rotated/prove_turn_chain_recursive) together withTurnChainBindingAirinto one root proofagg : Aggregate Proof. - By
light_client_verifies_anchored_history,anchored_history_starts_at_genesis, andlight_client_position_non_omission: - Checking only
verify agg.root = trueandagg.genesisRoot = expectedGenesisguarantees: - Prefix & Tail Completeness: The history starts at
expectedGenesis(anchored_attests_rejects_fabricated_genesisrules out hidden-prefix attacks), ends atagg.finalRoot, and folds exactlyagg.numTurns = steps.lengthsteps (turns_pinnedvialastRealCountBind). - Every-Record Policy Satisfaction: By
every_leaf_verifies_implies_executed(Forall₂positional pairing inEngineSound.leaf_sound), every folded turn $s \in \text{steps}$ satisfied the verified executor and its welded custom/DFA/CFG leaf proof ($\forall i \in [0, N), d_i \in G.\text{language} \land d_i \notin \mathcal{L}(P_{\text{forbid}})$). - Whole-Corpus Non-Omission: By
CommitBindsMMR+light_client_position_non_omission, the MMR rootmroot hash (extractMMR steps)is bound insideagg.finalRoot, so no training record $d_i$ could be omitted from the corpus or swapped duringsgd_step_sound/matVec_chainUpdatetraining steps—all while keeping the raw dataset $\mathcal{D}$ and encrypted weights $W_t$ completely private.
[2026-11-14 Ground-Truth Audit &
qsag/obendUpdate]: 1.AttestedAutomatonWeld8Width Seam (SWARM-2026-11-05§2): WhileContentCommitcarries 8 Goldilocks felts structurally, the deployedAttestedAutomatonWeld8AIR pin currently binds lane 0 (~$2^{15.5}$ birthday floor); closing full 8-lane binding in the emitted AIR pin remains tracked inbreadstuffs(18b3abebf). 2. Mid-November 2026 Continuation: Constructive (0 Classical.choice) WHIR / BaseFold signature aggregation and anonymous credentials now live in/Users/ember/dev/qsag(629779a), whileobend(16fed219) carriesObend/Grammar/VpaJson.lean(visibly pushdown JSON schema containment decidability) and 256-bucketObend/Vault/WorldTree.lean. See Dossier 28.
Primary-Source Dossier 01: Parsing Certificates, Regex-Complement DFAs, Attested Queries, & Proving the Absence of Information from Training Sets / Corpora / Logs
Primary-Source Scope:
/Users/ember/dev/breadstuffs(dfa/,dregg-query/,zkoracle-prove/,zkoracle-live/,deco-prove/,audit/,turn-prover/,tokenizer/,dregg-doc/,metatheory/Dregg2/{Crypto,Lightclient,Circuit}/),/Users/ember/dev/_research/{extended-regexes,finiteness-derivatives},/Users/ember/dev/zkml-research,/Users/ember/dev/minidregg, and~/.claude/projects/-Users-ember-dev-breadstuffs/memory/. Target Thesis (Ember): "lets really dig in a bit more deeply into some of the capabilities and explorations, as workload verification is very important to us ;) especially because our parsing certificates and other work can prove the absence of certain information from the training set, using the query and aggregation protocols we already defined"
Executive Summary: Why Proving Absence Requires Five Interlocking Primitives
Proving a positive fact about a dataset or log—such as "document $d$ is in training corpus $C$"—requires only a single Merkle inclusion path. By contrast, proving a negative (absence) property—such as "no training example in corpus $C$ contains PII pattern $P$, copyrighted canary $K$, benchmark test question $Q$, or template-breaking injection payload $I$, without revealing the corpus $C$"—is a universal quantification ($\forall i \in [0, |C|), \text{record}_i \notin \mathcal{L}(P)$) over private, structured data.
An adversarial prover attempting to forge an absence proof has five distinct attack surfaces:
- Language-Complement Evasion: Standard regular expression engines (Thompson $\varepsilon$-NFAs) cannot express complement ($\neg P$) or intersection ($P_1 \cap P_2$) without eager powerset determinization at every negation node.
- Structural / Framing Smuggling: A forbidden string or control token split across JSON fields or template holes, or embedded in malformed syntax, can fool a flat scanner that lacks a context-free grammar (CFG) parse proof.
- Cross-Leg Splicing / Narrow Commitment Collisions: Proving authenticity on document $A$ while running the absence matcher on a benign document $B$, or exploiting a narrow 1-felt ($\sim 31$-bit) commitment waist via birthday or linear-combination collisions.
- Selective Omission / Log Slicing: Returning an attested query over 99.9% of the training corpus while silently dropping the positions or index keys that contain the forbidden information, or truncating the prefix/suffix of the dataset log.
- Linear Verification Blowup: Shipping millions of per-record STARK proofs and Merkle openings that no light client or auditor can verify in constant time.
Across /Users/ember/dev/breadstuffs and /Users/ember/dev/zkml-research, Ember designed and formally verified in Lean 4 (#assert_axioms-clean, zero sorry) all five layers needed to close these exact attack surfaces:
flowchart TD
subgraph L1["1. Boolean-Closed Symbolic Derivatives & Parsing Certificates"]
A1["PredRE / Re::not() (dfa/src/derivative.rs, Deriv/Core.lean)"]
A2["Brzozowski Finiteness & Faithfulness (der_finite, tableDfa_faithful)"]
A3["CFG / VPL / DFA Unified Substrate (Hypergraph.Cert R, CfgCompact.Replay)"]
A1 --> A2 --> A3
end
subgraph L2["2. Lean-Authored STARK Policy Guards & 8-Lane Weld"]
B1["Dyck Pushdown Parse AIR (DyckStackEmit.lean: dyckParseDesc)"]
B2["DFA Routing & Complement AIR (DfaRoutingGeneralEmit.lean)"]
B3["Poseidon2 Content Weld (AttestedAutomatonWeld8.lean — lane-0 ~2^15.5 seam noted in SWARM-2026-11-05)"]
A3 --> B1 & B2
B1 & B2 --> B3
end
subgraph L3["3. Attested Queries & Cryptographic No-Omission Proofs"]
C1["Blake3Mmr & Dense Range Openings (MMR.lean: server_cannot_omit_position)"]
C2["Sorted Key-Range + Gap Exclusion (AttestedQuery.lean: server_cannot_omit)"]
C3["Paged Window Tiling & Count=0 Aggregation (dregg-query, audit CountProof)"]
B3 --> C1 & C2 --> C3
end
subgraph L4["4. Recursive STARK Aggregation & Anchored History"]
D1["3-Level STARK Recursion & TurnChainBindingAir (turn-prover)"]
D2["Genesis + Final Root Anchoring (RecursiveAggregation.lean)"]
D3["Succinct Light-Client Non-Omission (light_client_position_non_omission)"]
C3 --> D1 --> D2 --> D3
end1. Verified Regular Expression Complement & Symbolic Derivatives (dregg-dfa, Deriv/*, _research)
1.1 Architectural Motivation & Blueprints (_research/extended-regexes & _research/finiteness-derivatives)
During session 25937974-acb0-4804-95a2-21268c3353d4 (2026-06-25), Ember identified that scattered boolean-matching surfaces across breadstuffs (the Pred slot-policy algebra, CaveatPred macaroon caveats, FilterTree capability revocation, and the dregg-dfa router) needed a unified boolean-closed sequence-matching foundation:
Ember (
cvsession25937974, prompt[2067], 2026-06-25): "also burntsushi crates are maybe relevant and also compiling NFA to DFA maybe inefficient and wondering it there's an efficient NFA automaton we can run directly in circuit.... also this paper /Users/ember/Desktop/3704837.pdf about RE# is worth evaluating..." Ember (cvsession25937974, prompts[2153]&[2191], 2026-06-25): "yes........ yes! boolean matching! we definitely need to research regrounding that stuff :)" "(can fork and port it) and also we can improve our stuff... but like i'm not convinced we need to use their effectivebooleanalgebra or anything like that if we really need we can just prove whatever theorems over in our system..."
Two external Lean 4 developments in /Users/ember/dev/_research/ served as read-only architectural blueprints (never imported as dependencies, thereby avoiding both licensing gates and the v4.24.0-rc1 $\to$ v4.30.0 Mathlib version mismatch; see DERIVATIVE-MATCHING-DESIGN.md):
/Users/ember/dev/_research/extended-regexes(Zhuchko, Veanes, Ebner, CPP'24, "Lean Formalization of Extended Regular Expression Matching with Lookarounds", foundation for RE# POPL'25):- Defines
inductive REin Definitions.lean over anEffectiveBooleanAlgebra α σwith constructorsε,Pred (e : α),Alternation (l r : RE),Intersection (l r : RE),Concatenation (l r : RE),Star (r : RE),Negation (r : RE), and four lookaround operators (?=,?<=,?!,?<!). - Proves
theorem correctness : sp ⊢ R ↔ sp ⊫ Rin Correctness.lean. /Users/ember/dev/_research/finiteness-derivatives(Zhuchko, Margus, Veanes, ITP'25, "Finiteness of Symbolic Derivatives in Lean"):- Proves in Finite.lean that the symbolic derivative state space
steps r nis finite up to ACI similarity $(\cdot \cong \cdot)$, bounded by the power-set sum over-approximation⊕(pieces r):
theorem step_to_pieces {e : RE α} (e_in : e ∈ step f) :
∃ xs, toSum xs ≅ e ∧ xs ∈ neSubsets (pieces f)
...
theorem finiteness [DecidableEq α] {r : RE α} :
∃ (xs : List (RE α)), ∀ {n : ℕ}, steps r n ⊆[ (· ≅ ·) ] xs :=
⟨⊕(pieces r),steps_to_toSumSubsets⟩Ember's key simplification when porting this architecture to metatheory/Dregg2/Crypto/Deriv/ was:
- Use
Dregg2.Exec.PredAlgebra.Predas the leaf algebra overσ := Dregg2.Exec.Valueinstead of an abstractEffectiveBooleanAlgebratypeclass (Predis already a proven Boolean algebra witheval_not_notand De Morgan laws inPredAlgebra.lean:259-299). - Drop the four lookarounds: without lookarounds, nullability (
null : PredRE → Bool) is location-independent,derrequires no mutual recursion withexistsMatchand no height-bounded subtype, and the termination metric collapses tostarMetric (R : PredRE) : Nat ×ₗ Nat := toLex (starHeight R, size R)(Core.lean).
1.2 Rust Implementation: dregg-dfa (dfa/src/compiler.rs, dfa/src/derivative.rs, dfa/src/air.rs)
The dregg-dfa crate is the canonical pattern-compilation and routing engine in breadstuffs. It separates out-of-circuit regex compilation from in-circuit flat-table execution:
A. Flat Deterministic Finite Automaton (Dfa) & Pattern::Not
In compiler.rs, state identifiers are u32 with DEAD_STATE = 0 reserved as a sink state (transitions[0 * 256 + b] = 0 for all $b \in [0, 255]$):
pub type StateId = u32;
pub const DEAD_STATE: StateId = 0;
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct Dfa {
pub num_states: u32,
/// Flat transition table: `transitions[state * 256 + byte] = next_state`.
pub transitions: Vec<StateId>,
pub start: StateId,
pub accepting: BTreeSet<StateId>,
}The surface pattern grammar Pattern includes exact words, byte ranges, bitmasks, sequences, conjunction (All), disjunction (Any), offsets, repetitions, prefix-matching, and native complement (Not):
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub enum Pattern {
Word(Vec<u8>),
Range(u8, u8),
AnyByte,
Bit(usize, u8, bool),
Seq(Vec<Pattern>),
All(Vec<Pattern>),
Any(Vec<Pattern>),
Offset(usize, Box<Pattern>),
Repeat(Box<Pattern>, usize),
BytesAt(usize, Vec<u8>),
PrefixOf(Box<Pattern>),
/// Complement: matches any input that the inner pattern does NOT match.
///
/// Compiled via the derivative front-end ([`crate::derivative::Re::not`]),
/// which is closed under complement natively.
Not(Box<Pattern>),
}When Pattern::compile(&self) -> Dfa is invoked, needs_derivative() checks whether any node in the AST contains Pattern::Not. If so, it lowers the Pattern via Pattern::to_re(&self) -> Re and compiles it through the symbolic-derivative front-end (self.to_re().compile()), which emits the exact same flat Dfa struct consumed by the STARK AIR.
B. Symbolic Byte-Class Derivative Engine (dfa/src/derivative.rs)
In derivative.rs, character classes over u8 are represented as canonical, sorted, non-overlapping inclusive intervals ByteClass with exact Boolean operations (union, intersect, complement), and extended regular expressions are represented by Re:
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ByteClass {
/// Sorted, non-overlapping, adjacent-merged `(low, high)` inclusive ranges.
ranges: Vec<(u8, u8)>,
}
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum Re {
/// `∅` — matches nothing.
Empty,
/// `ε` — matches only the empty input `""`.
Epsilon,
/// Single byte in `ByteClass` (always non-empty; empty class normalizes to `Empty`).
Sym(ByteClass),
/// Concatenation `R · S`.
Cat(Box<Re>, Box<Re>),
/// Union / alternation `R | S`.
Alt(Box<Re>, Box<Re>),
/// Intersection `R & S` — derived lazily: `δ_b(R & S) = δ_b(R) & δ_b(S)`.
Inter(Box<Re>, Box<Re>),
/// Complement `~R` — derived natively: `δ_b(~R) = ~δ_b(R)`, `ν(~R) = !ν(R)`.
Neg(Box<Re>),
/// Kleene star `R*` (zero or more repetitions).
Star(Box<Re>),
}To guarantee that Brzozowski determinization terminates in a small number of states, Re enforces ACI (Associativity, Commutativity, Idempotence) canonicalization inside its smart constructors (Re::then, Re::or, Re::and, Re::not, Re::star):
Re::orandRe::andsort operands via derivedOrd(let (l, r) = if l <= r { (l, r) } else { (r, l) }), flatten right-associatively, deduplicateR | R = RandR & R = R, and short-circuit onEmptyandRe::any_bytes()($\Sigma^* = \neg\emptyset$).Re::not(r: Re) -> Selfeliminates double negation (Re::Neg(inner) => *inner).- Nullability
Re::nullable(&self) -> booland the Brzozowski derivativeRe::derive(&self, b: u8) -> Reare defined directly on the normalized AST:
pub fn nullable(&self) -> bool {
match self {
Re::Empty | Re::Sym(_) => false,
Re::Epsilon | Re::Star(_) => true,
Re::Cat(l, r) | Re::Inter(l, r) => l.nullable() && r.nullable(),
Re::Alt(l, r) => l.nullable() || r.nullable(),
Re::Neg(r) => !r.nullable(),
}
}
pub fn derive(&self, b: u8) -> Re {
match self {
Re::Empty | Re::Epsilon => Re::Empty,
Re::Sym(cls) => {
if cls.contains(b) { Re::Epsilon } else { Re::Empty }
}
Re::Cat(l, r) => {
let dl_r = l.derive(b).then((**r).clone());
if l.nullable() { dl_r.or(r.derive(b)) } else { dl_r }
}
Re::Alt(l, r) => l.derive(b).or(r.derive(b)),
Re::Inter(l, r) => l.derive(b).and(r.derive(b)),
Re::Neg(r) => r.derive(b).not(),
Re::Star(r) => r.derive(b).then(self.clone()),
}
}Instead of calling derive(b) 256 times per reachable state, Re::derivative_classes(&self) -> Vec<(u8, u8)> collects all interval cut-points from Sym(cls) leaves (collect_cuts) to partition $[0, 255]$ into equivalence classes [lo, hi] on which every leaf predicate has constant truth value. Then Re::compile(&self) -> Dfa explores only reachable derivative states, evaluating cur_re.derive(lo) once per equivalence class and fanning next_id across transitions[base + b] for b in lo..=hi. Conversely, Re::from_dfa(dfa: &Dfa) -> Re implements state elimination so any compiled Dfa can be lifted back into Re and complemented via .not().
C. AIR Witness Generation & Verification (dfa/src/air.rs)
In air.rs, a flat Dfa execution over input: &[u8] is witnessed as a sequence of AirTraceRow steps bound to a router_root: [u8; 32]:
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct AirTraceRow {
pub step: u32,
pub state: StateId,
pub byte: u8,
pub next_state: StateId,
}
#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
pub struct AirTrace {
pub router_root: [u8; 32],
pub transitions: Vec<StateId>,
pub num_states: u32,
pub start: StateId,
pub accepting: Vec<StateId>,
pub input: Vec<u8>,
pub trace: Vec<AirTraceRow>,
}1.3 Lean 4 Formalization: metatheory/Dregg2/Crypto/Deriv/* & Dfa.lean
The Lean 4 formalization in metatheory/Dregg2/Crypto/Deriv/ proves the entire derivative tower #assert_axioms-clean (⊆ {propext, Classical.choice, Quot.sound}) and sorry-free:
A. PredRE, null, der, derives, and Matches (Core.lean)
inductive PredRE where
| ε
| sym (φ : Pred)
| alt (l r : PredRE)
| inter (l r : PredRE)
| cat (l r : PredRE)
| star (r : PredRE)
| neg (r : PredRE)
deriving Repr, DecidableEq
@[simp]
def leaf (φ : Pred) (a : Value) : Bool :=
φ.eval (symbolOld a) a
@[simp]
def null : PredRE → Bool
| .ε => true
| .sym _ => false
| .alt l r => null l || null r
| .inter l r => null l && null r
| .cat l r => null l && null r
| .star _ => true
| .neg r => !(null r)
@[simp]
def der (a : Value) : PredRE → PredRE
| .ε => .sym .ff
| .sym φ => if leaf φ a then .ε else .sym .ff
| .alt l r => .alt (der a l) (der a r)
| .inter l r => .inter (der a l) (der a r)
| .neg r => .neg (der a r)
| .cat l r => if null l
then .alt (.cat (der a l) r) (der a r)
else .cat (der a l) r
| .star r => .cat (der a r) (.star r)
@[simp]
def derives : List Value → PredRE → Bool
| [], R => null R
| a :: as, R => derives as (der a R)Note how leaf supports both stateless single-frame evaluation (symbolOld a = emptyFrame when unassigned) and stateful two-frame transition pairs crafted via transitionSymbol (old : Value) : Value → Value (Core.lean).
The declarative semantics Matches : List Value → PredRE → Prop is defined by well-founded recursion on starMetric R = toLex (starHeight R, size R):
def Matches (w : List Value) (R : PredRE) : Prop :=
match R with
| .ε => w = []
| .sym φ => ∃ a : Value, w = [a] ∧ leaf φ a = true
| .alt l r => Matches w l ∨ Matches w r
| .inter l r => Matches w l ∧ Matches w r
| .cat l r => ∃ w₁ w₂ : List Value, w₁ ++ w₂ = w ∧ Matches w₁ l ∧ Matches w₂ r
| .neg r => ¬ Matches w r
| .star r => ∃ n : Nat, Matches (w := w) (repeatCat r n)
termination_by (starMetric R, w.length)B. Derivative Correctness & Complement Homomorphism (Correctness.lean)
In Correctness.lean, Ember proves that derives is a exact Boolean homomorphism on .inter and .neg and is sound and complete with respect to Matches:
@[simp]
theorem derives_inter (w : List Value) (l r : PredRE) :
derives w (.inter l r) = (derives w l && derives w r)
@[simp]
theorem derives_neg (w : List Value) (r : PredRE) :
derives w (.neg r) = !(derives w r)
theorem correctness (w : List Value) (R : PredRE) :
derives w R = true ↔ Matches w RC. Brzozowski Finiteness (Finiteness.lean)
In Finiteness.lean (landed 2026-06-25, commit 8ba854ce5), the multi-step symbolic derivative state space steps r n is proven finite up to ACI similarity ≅ for all $n \in \mathbb{N}$:
theorem steps_to_toSumSubsets {r : PredRE} {n : Nat} :
steps r n ⊆[ (· ≅ ·) ] ⊕(pieces r)
theorem der_finite {r : PredRE} :
∃ (xs : List PredRE), ∀ {n : Nat}, steps r n ⊆[ (· ≅ ·) ] xs :=
⟨⊕(pieces r), steps_to_toSumSubsets⟩D. Determinization, TableDfa Faithfulness, & Symbolic Emptiness Decision (Determinize.lean, TableDfa.lean, SymbolicDecision.lean)
In Determinize.lean and TableDfa.lean, the derivative automaton is welded to Dregg2.Crypto.Dfa.DfaAccepts:
theorem derivativeDfa_correct (R : PredRE) (a : Value) (as : List Value) :
DfaAccepts derStep R nullAccept (runTrace R (a :: as)) ↔ derives (a :: as) R = true
theorem derivativeDfa_matches (R : PredRE) (a : Value) (as : List Value) :
DfaAccepts derStep R nullAccept (runTrace R (a :: as)) ↔ Matches (a :: as) R
theorem tableRun_dfaAccepts (td : TableDfa State Sym) (a : Sym) (as : List Sym) :
DfaAccepts td.δ td.start td.accept (runTrace td td.start (a :: as)) ↔ td.accepts (a :: as)
theorem tableDfa_faithful (td : TableDfa PredRE Value) (R : PredRE)
(hagree : ∀ w, td.accepts w ↔ derives w R = true) :
∀ w, td.accepts w ↔ Matches w R
theorem derivativeTable_finite (R : PredRE) :
∃ xs : List PredRE, ∀ {n}, steps R n ⊆[ (· ≅ ·) ] xs := der_finiteFurthermore, in SymbolicDecision.lean (commit c1aa7e97c / 735b76169, 2026-07-18), der_finite is combined with a pigeonhole pumping argument (emptinessBound R = |⊕(pieces R)|) and minterm factoring to provide a computable Decidable instance for unbounded regex emptiness over the infinite Value alphabet on the deployed guard fragment DeployedRE:
abbrev DeployedRE : Type := {R : PredRE // IsDeployed R}
def predRE_emptiness_decidable (R : DeployedRE) :
Decidable (∃ w, derives w R.val = true) :=
predRENonemptyDecidable R.propertyE. In-Circuit DFA Verification & Unified Certificate Substrate (Dfa.lean, DfaAsCert.lean)
In Dfa.lean, the STARK AIR trace is bridged to DfaAccepts:
def DfaAccepts (δ : State → Sym → State → Prop) (q₀ : State) (accept : State → Prop)
(trace : List (Step State Sym)) : Prop :=
∃ first last,
trace.head? = some first ∧
trace.getLast? = some last ∧
first.state = q₀ ∧
accept last.next ∧
(∀ s ∈ trace, stepValid δ s) ∧
chained trace
theorem dfa_bridge (δ : State → Sym → State → Prop) (q₀ : State) (accept : State → Prop)
(trace : List (Step State Sym)) :
(∀ circuit : CircuitIR State Sym, circuit.trace = trace →
Satisfies δ q₀ accept circuit → DfaAccepts δ q₀ accept trace) ∧
(DfaAccepts δ q₀ accept trace →
∃ circuit : CircuitIR State Sym, Satisfies δ q₀ accept circuit)
theorem dfa_verify_sound {State Sym : Type} [K : DfaVerifierKernel State Sym Proof]
(hext : K.extractable) (stmt : Statement State Sym) (proof : Proof)
(haccept : K.verify stmt proof = true) :
∃ trace : List (Step State Sym), DfaAccepts stmt.δ stmt.q₀ stmt.accept traceAnd in DfaAsCert.lean (commit 9548bfc7a, 2026-07-17), DfaAccepts is proved definitionally equivalent to Hypergraph.Cert delta (delta a b := b.state = a.next), uniting regular DFA recognition and context-free grammar parsing on one relation-parametric certificate substrate:
theorem dfaAccepts_as_cert (δ : State → Sym → State → Prop) (q₀ : State) (accept : State → Prop)
(trace : List (Step State Sym)) :
DfaAccepts δ q₀ accept trace ↔
∃ first last : Step State Sym,
first.state = q₀ ∧
accept last.next ∧
(∀ s ∈ trace, stepValid δ s) ∧
Hypergraph.Cert delta first last trace
theorem regular_and_cf_share_substrate
(first last : Step State Sym) {T : Type} (g : ContextFreeGrammar T) (input : List T) :
((∃ c, Hypergraph.Cert delta first last c) ↔ Relation.ReflTransGen delta first last)
∧
((∃ c, Hypergraph.Cert g.Produces
[Symbol.nonterminal g.initial] (input.map Symbol.terminal) c) ↔ input ∈ g.language) :=
⟨Hypergraph.bridge delta first last, Hypergraph.cfg_parse_via_reduction g input⟩2. Parsing Certificates, Guarded Templates, & STARK Policy Guards (Cfg.lean, ZkOracle.lean, zkoracle-prove, DyckStackEmit.lean)
2.1 Context-Free Parsing Certificates: Form-Chain (Cfg.lean) vs. O(tokens) Pushdown Replay (CfgCompact.lean)
During session 3e00cf4f-418c-4725-861d-79a681805f78 (2026-07-16), Ember pushed the verification stack from flat regular expressions to full context-free parsing certificates and composable proof-producing templates:
Ember (
cvsession3e00cf4f, prompts[1634],[1947],[2220], 2026-07-16): "wtf lmao the injection freedom was supposed to be a proof that a given string cuold have been generated from a given handlebars template (a parsing/unparsing argument)" "wait our template language shouldn't really be REGULAR ... is it? ??? that seems wrong-headed/weak when we have a full CFG/graph-rewriting architecture available right??" "read, we do need to figure out some way to compose these things with the regex/dfa type stuff so that we can have a maximally flexible & also extremely efficient setup for the attestation/witness/proofs/etc."
- Form-Chain Certificate (Cfg.lean): Models a context-free derivation over Mathlib's
ContextFreeGrammar Tas aHypergraph.Cert g.Produceschain from[Symbol.nonterminal g.initial]toinput.map Symbol.terminal:
def producesChain (g : ContextFreeGrammar T) : List (List (Symbol T g.NT)) → Prop :=
Hypergraph.chain g.Produces
def CfgAccepts (g : ContextFreeGrammar T) (input : List T)
(chain : List (List (Symbol T g.NT))) : Prop :=
Hypergraph.Cert g.Produces [Symbol.nonterminal g.initial] (input.map Symbol.terminal) chain
theorem cfg_bridge (g : ContextFreeGrammar T) (input : List T) :
(∃ chain, CfgAccepts g input chain) ↔ input ∈ g.language :=
Hypergraph.cfg_parse_via_reduction g input
theorem cfg_verify_sound {T : Type} [K : CfgVerifierKernel T Proof]
(hext : K.extractable) (stmt : Statement T) (proof : Proof)
(haccept : K.verify stmt proof = true) :
stmt.input ∈ stmt.g.language- Compact $O(\text{tokens})$ Leftmost Rule-Sequence Certificate (CfgCompact.lean): Because storing every intermediate sentential form in
Cfg.leantakes $O(\text{tokens}^2)$ symbols (2.15 billion symbols on 32.8k dense JSON tokens, overflowing stack near 65k tokens; see ZKORACLE-PROVER-STATUS.md),CfgCompact.lean(commit0eb08bf32, 2026-07-06) replaces the wire format with the $O(\text{tokens})$ leftmost rule sequencers : List (ContextFreeRule T g.NT)verified by an inductive pushdown replay machineReplay:
inductive Replay (g : ContextFreeGrammar T) :
List (ContextFreeRule T g.NT) → List T → List (Symbol T g.NT) → Prop
| done : Replay g [] [] []
| term {rs : List (ContextFreeRule T g.NT)} {input : List T} {stk : List (Symbol T g.NT)}
(t : T) : Replay g rs input stk → Replay g rs (t :: input) (Symbol.terminal t :: stk)
| rule {r : ContextFreeRule T g.NT} {rs : List (ContextFreeRule T g.NT)} {input : List T}
{stk : List (Symbol T g.NT)} (hr : r ∈ g.rules) :
Replay g rs input (r.output ++ stk) →
Replay g (r :: rs) input (Symbol.nonterminal r.input :: stk)
def ReplayAccepts (g : ContextFreeGrammar T) (rs : List (ContextFreeRule T g.NT))
(input : List T) : Prop :=
Replay g rs input [Symbol.nonterminal g.initial]
theorem replay_derives {g : ContextFreeGrammar T}
{rs : List (ContextFreeRule T g.NT)} {input : List T} {stk : List (Symbol T g.NT)}
(h : Replay g rs input stk) : g.Derives stk (input.map Symbol.terminal)
theorem compact_sound (g : ContextFreeGrammar T) (rs : List (ContextFreeRule T g.NT))
(input : List T) (h : ReplayAccepts g rs input) : input ∈ g.language
theorem compact_to_chain (g : ContextFreeGrammar T) (rs : List (ContextFreeRule T g.NT))
(input : List T) (h : ReplayAccepts g rs input) :
∃ chain, CfgAccepts g input chain :=
(cfg_bridge g input).mpr (compact_sound g rs input h)- Four Rungs on One
Hypergraph.Cert RSubstrate (VpaAsCert.lean, ReplayAsCert.lean): InVpaAsCert.lean(commitdf7645d3a, 2026-07-17) andReplayAsCert.lean(commit7b292b047, 2026-07-17), Visibly Pushdown Automata (VPA, where stack height is input-determined viastack_height_input_determined, making equivalence EXPTIME-decidable inVpaDecidable.lean) and pushdownReplayare proven to be instances ofHypergraph.Cert, and the multi-row trace induction is subsumed by one genericHypergraph.Cert.foldSoundapplication:
theorem three_rungs_share_substrate
{State Sym : Type u} (firstD lastD : Dfa.Step State Sym)
{Call Int Ret VState StackSym : Type u}
(M : VPA Call Int Ret VState StackSym) (firstV lastV : VStep Call Int Ret VState StackSym)
{T : Type} (g : ContextFreeGrammar T) (input : List T) :
((∃ c, Hypergraph.Cert DfaAsCert.delta firstD lastD c) ↔
Relation.ReflTransGen DfaAsCert.delta firstD lastD)
∧
((∃ c, Hypergraph.Cert (R_vpa M) firstV lastV c) ↔
Relation.ReflTransGen (R_vpa M) firstV lastV)
∧
((∃ c, Hypergraph.Cert g.Produces
[Symbol.nonterminal g.initial] (input.map Symbol.terminal) c) ↔ input ∈ g.language)- Guard-Parametric Proof-Producing Templates (HandlebarsGuarded.lean): In
HandlebarsGuarded.lean(commit5371f5582, 2026-07-17), template holes carry arbitraryPredREguards (GSeg.hole (id : Nat) (guard : PredRE)) over the infiniteValuealphabet, uniting regularPredREleaves with template composition:
def guardedSafe (T : GuardedTemplate) (d : Nat → List Value) : Prop :=
∀ id g, GSeg.hole id g ∈ T.segments → derives (d id) g = true
theorem guarded_render_mem_language (T : GuardedTemplate) (d : Nat → List Value)
(hsafe : guardedSafe T d) :
render T d ∈ (guardedToGrammar T).language
theorem noDoubleBraceRE_iff (w : List Handlebars.Tok) :
derives (w.map tokVal) noDoubleBraceRE = true ↔ Handlebars.NoDoubleBrace w2.2 Lean-Authored STARK Policy Guards (DyckStackEmit.lean, DfaRoutingGeneralEmit.lean, AttestedAutomatonWeld8.lean)
Per Ember's standing architectural Law #1 (project-lean-authored-air-law.md):
"ZERO Rust-authored constraints or AIRs, EVER. ALL circuits and ALL constraint semantics are EMITTED FROM LEAN and formally represented. Rust only INTERPRETS Lean-emitted byte-pinned artifacts."
Three Lean-emitted IR-v2 descriptors in metatheory/Dregg2/Circuit/Emit/ implement the in-circuit parsing and DFA-complement guards:
- Dyck Pushdown Parse Descriptor (
"dregg-dyck-parse-v1", DyckStackEmit.lean & DyckStackReplay.lean): - Emits
dyckParseDesc : EffectVmDescriptor2(widthDYCK_WIDTH = 24, 4 public inputs[initial_symbol, input_len, table_commitment, route_commitment], 79 constraints, 2 narrow Poseidon2 chip lookups forENTRY_HASH = hash_4_to_1(RULE_ID, STACK0, INPUT_TOKEN, 0)and rollingRUNNING_HASH = hash_2_to_1(ACC, ENTRY_HASH)). - Enforces bounded stack depth $D = 5$ via vanishing polynomial
depthRangeBody($\prod_{v=0}^5 (\text{STACK\_DEPTH} - v) = 0$) to close field-wraparound congruence attacks (depth_range_zero_iff, commit63463d032), plusbracket_shift_zero_iff,bracket_overflow_zero_iff,rule_membership_zero_iff, andterminal_top_zero_iff. - In DyckStackReplay.lean (commit
e4072a3d4, 2026-07-17),parse_sat_imp_replay_emit_unconditionalproves unconditionally that any tracetsatisfying the byte-pinnedDyckStackEmit.dyckParseDeschas its trace-decoded worddecodedWord t naccepted byCfgCompact.ReplayAccepts:
theorem parse_sat_imp_replay_emit_unconditional {hash : List ℤ → ℤ} {minit : ℤ → ℤ}
{mfin : ℤ → ℤ × Nat} {maddrs : List ℤ} {t : VmTrace}
(hsat : Satisfied2 hash DyckStackEmit.dyckParseDesc minit mfin maddrs t) (hcanon : DyckCanon t)
(n : Nat) (hn : n + 1 < t.rows.length) (hnp : n < 2013265921)
(hpi : t.pub PI_INITIAL = SYM_S)
(hdone : (envAt t n).loc IS_DONE = 1)
(hlive : ∀ i, i < n → (envAt t i).loc IS_DONE = 0) :
ReplayAccepts dyck (rulesOf (decodeRun (decodedWord t n) t (n + 1))) (decodedWord t n)- 3-State Complement DFA Descriptor (
"dfa-routing-injection-3state::poseidon2-v1", DfaRoutingGeneralEmit.lean): - Models the 3-state complement DFA for $\neg(\Sigma^* \cdot \text{"\{\{"} \cdot \Sigma^*)$: states
S_CLEAN = 0(start, accepting),S_BRACE = 1(saw one{, accepting),S_DEAD = 2(saw{{, non-accepting sink); symbolsSYM_OTHER = 0,SYM_BRACE = 1. - Encodes the transition table $\delta : \{0,1,2\} \times \{0,1\} \to \{0,1,2\}$ as a doubled bivariate Lagrange interpolant over $\mathbb{Z}$ (avoiding $\mathbb{Q}$ denominators): $$G(a, b, \text{next}) = 2\cdot\text{next} - 2a^2 + 2a + 3a^2b - 5ab - 2b$$
- Proves exactness over the domain (
transition_body_zero_iff, DfaRoutingGeneralEmit.lean):
theorem transition_body_zero_iff (a : Assignment)
(hst : a COL_STATE = 0 ∨ a COL_STATE = 1 ∨ a COL_STATE = 2)
(hsym : a COL_SYMBOL = 0 ∨ a COL_SYMBOL = 1) :
transitionBody.eval a = 0 ↔
a COL_NEXT = δ_spec (a COL_STATE) (a COL_SYMBOL)- 8-Felt Wide Attested Automaton Weld (
"attested-automaton-weld8-v1", AttestedAutomatonEmit.lean & AttestedAutomatonWeld8.lean): - Proves that running an automaton over an attested message payload while binding all 8 Poseidon2 digest lanes (
WELD_LANES = 8, public inputsPI_MSG_COMMIT 0..7andPI_FINAL_STATE = 8) forces two satisfying traces with equal 8-lane commitments to run the automaton on the exact same message (or exhibit an 8-laneChip8Collisionat $\sim 2^{123.63}$ birthday security).
2.3 Capstone Composition (ZkOracle.lean, zkoracle-prove, zkoracle-live, deco-prove)
In ZkOracle.lean, the three legs—DECO/zkTLS provenance, JSON CFG well-formedness, and PredRE.neg complement matching—compose into zkOracle_sound:
def injectionTemplate : PredRE :=
.cat (.star (.sym .tt)) (.cat (.sym (matchCode handlebarsOpen)) (.star (.sym .tt)))
def InjectionFree (field : List Value) : Prop :=
derives field (.neg injectionTemplate) = true
theorem zkOracle_sound
{SK MK ProofD ProofC : Type}
[KD : Deco.DecoVerifierKernel SK MK ProofD]
[KC : Cfg.CfgVerifierKernel JsonTok ProofC]
(hdeco_ext : KD.extractable)
(hcfg_ext : KC.extractable)
(hcommit : DecoUnforgeable.CommitBinding KD.compress)
(hmac : DecoUnforgeable.MacUnforgeable MK KD.mac)
(decoStmt : Deco.Statement SK MK) (decoProof : ProofD)
(body : List JsonTok) (cfgProof : ProofC)
(field : List Value)
(hdeco : KD.verify decoStmt decoProof = true)
(hcfg : KC.verify ⟨jsonGrammar, body⟩ cfgProof = true)
(hinj : verifyInjectionFree field = true) :
DecoUnforgeable.decoAuthenticated SK MK KD.compress KD.encode decoStmt ∧
body ∈ jsonGrammar.language ∧
InjectionFree fieldIn Rust, dregg-zkoracle-prove and dregg-zkoracle-live (split into a feature-free crate on 2026-07-27, commit 5d29e1baa, alongside dregg-deco-prove) realize all three legs plus the cross-leg Poseidon2 weld:
zkoracle-prove/src/attestation.rs:- Defines
pub const CONTENT_COMMIT_W: usize = 8; pub type ContentCommit = [BabyBear; CONTENT_COMMIT_W];(attestation.rs) andpub fn content_commitment(response_body: &[u8]) -> ContentCommit { hash_bytes_8(response_body) }(attestation.rs), widened on 2026-08-01 from 1 felt ($\sim 2^{15.45}$ birthday) to the full 8-felt Poseidon2 digest ($\sim 2^{123.63}$). ZkOracleAttestationbundlespresentation: EndpointPresentation,cfg_cert: CompactCert,field_span: FieldSpan { offset, len },content_commit: ContentCommit,zk_injection: Option<ZkInjectionProof>, andtlsn_presentation: Option<Vec<u8>>.verify_zkoracle_with_policyverifies Leg 1 (MPC-TLS / DECO authenticity and secret header redaction), recomputescontent_commitment(&response_body) == att.content_commit(CrossLegMismatchif unequal), slicesfield = &response_body[att.field_span](SpanOutOfBoundsif invalid), verifies Leg 2 (verify_cfg_compact(&att.cfg_cert, &response_body)), and verifies Leg 3 (verify_injection_free(field)+ optional STARKverify_injection_stark(zk, field)).zkoracle-prove/src/cfg.rs:- Defines the 16-production LL(1)-disambiguated JSON grammar
json_grammar()and bothParseCertificate(full form-chain) andCompactCert { pub rules: Vec<u8> }verified by iterative pushdown replayverify_cfg_compact. - Measured Paces (ZKORACLE-PROVER-STATUS.md):
- 1.2 KB single response (51 JSON tokens): 1 µs cert prove, 2 µs cert verify, 318 µs e2e prove, 314 µs e2e verify.
- 256k LLM-token context (990 KB, 100k JSON tokens): 1.04 ms cert prove, 993 µs cert verify, 216 ms e2e prove.
- 10M LLM-token context (39.6 MB, 4.0M JSON tokens, 3.6 MB
CompactCert): 40 ms cert prove, 39 ms cert verify, 8.6 s e2e prove (dominated by sequential Poseidon2 hashing). zkoracle-prove/src/zk_leg.rs:prove_injection_stark(field: &str) -> Result<ZkInjectionProof, String>andverify_injection_stark(proof: &ZkInjectionProof, field: &str) -> Result<(), ZkLegError>prove and verify the 3-state complement DFA over the Lean-emitted descriptorINJECTION_DESC_NAME = "dfa-routing-injection-3state::poseidon2-v1"viaprove_vm_descriptor2/verify_vm_descriptor2, recomputingexpected_route = compute_route_commitment(&steps)so a prover cannot claim clean acceptance on a different byte stream (RouteCommitmentMismatch).
Source-Locked Technical Dossier 04: Workload Verification, Native MXFP4 zkML, MoE Router Binding, Model Identity, Verifiable FHE (vFHE), Multi-Silicon Proving, & Selvage Commit-Then-Audit
Scope & Primary Repositories Audited (Strictly Read-Only):
/Users/ember/dev/zkml-research(branchdev, HEADb950c991, Nov 2026 — importing 162SelvageLean files incl.AuthMapCommitment.lean7b3468acf; see also/Users/ember/dev/qsag629779ain Dossier 28 §1)/Users/ember/dev/minidregg(Selvage/,Theory/,Assurance/,Compiler/,origin/mainc60818647+append-growth5e05cf4fc, 2026-11-14)/Users/ember/dev/breadstuffs(fhegg-fhe,fhegg-rtl,grain-verify,turn-prover,metatheory/Bfv,circuit,origin/main18b3abebf, 2026-11-14)/Users/ember/src/dregg-microsites(which-model,keep-learning-keep-a-secret,keep-the-next-example,the-whole-way-through,prove-the-turn, HEADc0df432942c7fc6a35b74fc1f0ccfa3c0ed7d492, 2026-09-20)
Executive Architectural Synthesis
Ember's workload-verification and cryptographic-compute stack is organized around a single unifying thesis: verifiability and weight encryption are public goods that must run at frontier scale without silent soundness holes, float-approximation backdoors, or prover-bankrupting full-trace materialization. Across /Users/ember/dev/minidregg, /Users/ember/dev/zkml-research, and /Users/ember/dev/breadstuffs, six tightly coupled engineering pillars realize this vision:
flowchart TD
subgraph S1["1. Selvage & Commit-Then-Audit (minidregg/Selvage)"]
A1["AuditSampling.lean (1,174 L, 0 sorry)"] -->|"q = p(1 - ε_chk) - ε_bind - ε_beacon"| A2["Optional Stopping: E[C_τ] ≤ 1/q, E[Λ] ≤ b/q"]
A3["Boundary Exchange Rate (78×–308× field muls)"] -->|"Prove boundaries, not interiors"| A4["Sumcheck Virtualization + Narrow Poseidon2 AIR"]
end
subgraph S2["2. Model Identity & Weight Registry (zkml-research/registry)"]
B1["v1 Range-Streamed SHA-256 Manifests (8 models up to 1.56 TB Kimi-K3)"] -->|"Ember Steer (08-13): SHA-256 is unopenable in-circuit"| B2["v2 Poseidon2 Per-Expert Merkle Roots R_{ℓ,e}"]
end
subgraph S3["3. Native MXFP4 Arithmetization & MoE Router Binding"]
C1["Or Zamir Thm 1 + Spain OSDI'26 Refutation"] -->|"Reject ε-approximate floats"| C2["Bit-Exact OCP MXFP4 (Block-32 E2M1 ∈ ±4,608, 13-bit int)"]
C2 -->|"1,382,400 gpt-oss-20b rows: 100% fit width-8 shift"| C3["MoE Threshold Top-k (0.72% trace overhead) + Hybrid Audit Inversion"]
end
subgraph S4["4. Verifiable FHE (vFHE) & Encrypted Continual Learning"]
D1["CyclotomicInertia.lean (1,191 L): p_61 = 2^61 - 2^54 + 1 (depth-1 @ N=4096; smudge forces RNS @ N=8192)"] -->|"2-adicity 54 + Maximal 3-adic Inertia"| D2["Eliminates Zama 2026/027 ν=32 Panic (1,788 → 224 Kimi-K3 chunks)"]
D3["Rank1GradientCheck.lean + ZkmlLowRankUpdate.lean"] -->|"O(1) rounds + 2rd commitment"| D4["Continuing Encrypted Learner (Matched 4-BFV-Field AIR, 113 s Query)"]
end
subgraph S5["5. Multi-Silicon Proving (GPU / TPU / FPGA)"]
E1["wgpu Multi-Pipeline Arena (gpu_arena.rs + mle_gpu.rs)"] -->|"2.7×–7.1× traffic reduction"| E2["NVIDIA B200 clmad + Binary Tower BaseFold"]
E3["TPU v6e INT8 MXU (CROSS BAT K=4 = 3.05× BabyBear)"] --> E4["Zama HPU 162.7 kLOC RTL: ntt_acc_modsw @ 409.6 GB/s vs 25.6 GB/s HBM"]
end
B2 --> C3
C3 --> A1
E4 -->|"16× bandwidth gap proves physically"| A1
D1 --> D41. Selvage & The Machine-Checked Commit-Then-Audit Theorem
1.1 Overview of the Selvage/ Formalization in minidregg
In /Users/ember/dev/minidregg/Selvage/ (152 .lean files, ~63,876 lines at campaign checkpoint, zero sorry tokens and zero top-level axiom declarations, verified via #guard_msgs (whitespace := lax) in #print axioms), Ember built Selvage (slvg), a greenfield Lean-4-specified and Rust-executed proof system designed to replace upstream Plonky3. Its machine-checked spine includes:
- Committed-then-Audited Economic Soundness:
AuditSampling.lean(1,174 lines, landed 2026-08-13 in commits5dfeb19b618d91538d54224cd2c3ef866294e2e3and503231dbfdc30ea8b062b4a89bc3e1435b33b951). - Domain-General Correlated Agreement & WHIR Errata Repairs:
CorrelatedAgreement.lean, fixing WHIR Lemma 4.10's printed $\min\{1-\delta_\mathcal{C}/2, B\} \to \max$, Definition 4.9's $1-B \to 1-B^*$, generalizing from $\mathbb{F}_q^*$ to arbitrary subgroup generators, and making error-function monotonicity (herr_mono) explicit. - Accumulation Depth & Shifted BCS Compiler:
Depth.lean,FiatShamir.lean,AccRbrBcs.lean,AccRbrBcsShifted.lean, andAccRbrFold.lean(1,448 lines, commitbc29222, proving folding at the commitment alphabet with tight norm walls). - Binary-Tower Additive BaseFold & Characteristic-2 Trap Refutation:
CharTwoWall.lean(commit0dd9a486652c63b7805f55b12e14da487b4aaa62, 2026-08-14): provestheorem charTwo_inv_two_impossible : ¬∃ inv2 : Tower256, (1 + 1 : Tower256) * inv2 = 1andtheorem no_nontrivial_charTwo_pairing (x : Tower256) : ¬x ≠ -x, mechanically refuting multiplicative FRI folding (s ↦ s²) over binary towers and provingcharTwoWall_detects_tower256 : charTwoWallDetected Tower256 = true.AdditiveBaseFold.lean(856 lines, commitb5da623cc0ef4c1e3016a8012650a0d7c993863b, 2026-08-14) andAdditiveBasisBinding.lean(483 lines, commit9679a16abb552cc7eba825aa4c21160d3aa23011, 2026-08-16): proves BaseFold descent on the additive subspace tower $q(X) = X(X + \Delta)$ and proves that the Fiat-Shamir sponge must absorb the ordered $\mathbb{F}_2$-basis of the evaluation domain (basisPrefix) because $GL_d(\mathbb{F}_2)$ automorphisms preserve the point set while permuting hypercube vertices (swap01_fixes_set,swap01_changes_table).
1.2 The Machine-Checked Commit-Then-Audit Theorem (Selvage/AuditSampling.lean)
As documented in docs/SELVAGE.md and notes/audit-theorem-statement.md, commercial verifiable-inference providers (e.g., Attestable Audits, arXiv 2506.23706) argue commit-then-audit detection with a one-line union bound $1 - (1 - p)^k$ that silently treats the commitment as perfectly binding ($\varepsilon_{\text{bind}} = 0$), the proof checker as infallible ($\varepsilon_{\text{chk}} = 0$), the random audit coin as unbiasable ($\varepsilon_{\text{beacon}} = 0$), and the adversary's corruption schedule as non-adaptive (i.i.d.).
In Selvage/AuditSampling.lean, Ember formalized and proved the first machine-checked commit-then-audit theorem in Lean 4 with all three cryptographic error legs and full adaptive stopping-time schedules.
A. Parameter Bundle & Effective Per-Turn Detection Rate $q$
From Selvage/AuditSampling.lean:
structure AuditParams where
/-- Nominal audit firing probability `p ∈ [0,1]`. -/
p : ℝ
/-- Proof-system soundness error `ε_chk ∈ [0,1]`: bound on `Pr[accept | fired, corrupt]`. -/
εchk : ℝ
/-- Commitment-binding break probability `ε_bind ≥ 0` per round. -/
εbind : ℝ
/-- Beacon bias `ε_beacon ≥ 0`: how much the adversary can depress `Pr[fires]`. -/
εbeacon : ℝ
hp_nonneg : 0 ≤ p
hp_le_one : p ≤ 1
hchk_nonneg : 0 ≤ εchk
hchk_le_one : εchk ≤ 1
hbind_nonneg : 0 ≤ εbind
hbeacon_nonneg : 0 ≤ εbeacon
namespace AuditParams
/-- **The effective per-corrupt-turn detection rate**:
`q = p · (1 − ε_chk) − ε_bind − ε_beacon`. -/
def q (A : AuditParams) : ℝ :=
A.p * (1 - A.εchk) - A.εbind - A.εbeaconB. Predictable ($\mathcal{F}_{t-1}$-Measurable) Adaptive Corruption & The Three Cryptographic Legs
Crucially, predictability (the commit-before-coin ordering that prevents an adversary from peeking at the audit coin $\omega_t$ before deciding whether turn $t$ is corrupt) is enforced by the Lean type signature of Round.corrupt, which takes only the prior history List Ω and not the current coin ω : Ω (Selvage/AuditSampling.lean):
structure Round (Ω : Type) where
/-- Whether the prover corrupts this round, as a function of the **prior**
history `h : List Ω` ONLY. Does not take `ω : Ω` — predictability is a type. -/
corrupt : List Ω → Bool
/-- Whether the audit beacon fires on coin `ω` after history `h`. -/
fires : List Ω → Ω → Bool
/-- Whether the audit raises an alarm (`alarm_t = 1`). -/
alarms : List Ω → Ω → Bool
/-- Checker soundness-failure event: the checker was run and accepted a
corrupt claim. -/
chkErr : List Ω → Ω → Bool
/-- Checker abort / timeout / malformed-proof event (`V = ⊥`). Separated from
`chkErr` so the fail-open vs fail-closed distinction is expressible. -/
chkAbort : List Ω → Ω → Bool
/-- Commitment-binding break event: the prover produced a second valid opening
for the committed digest `c_t`. -/
bindBreak : List Ω → Ω → BoolThe three cryptographic assumptions and the miss-decomposition hypothesis are defined over Round Ω (Selvage/AuditSampling.lean):
/-- **Leg 3 (beacon)**: `Pr_ω[fires h ω] ≥ p − ε_beacon` at every history `h`. -/
def BeaconLeg (A : AuditParams) (R : Round Ω) : Prop :=
∀ h : List Ω, A.p - A.εbeacon ≤ uniformProb Ω (fun ω => R.fires h ω)
/-- **Leg 1 (checker soundness, conditional on firing)**: on any corrupt round,
`Pr_ω[fires ∧ chkErr] ≤ Pr_ω[fires] · ε_chk`. Written in product form to avoid
dividing by `Pr[fires]` (which may be `0` when `p ≤ ε_beacon`). -/
def ChkLeg (A : AuditParams) (R : Round Ω) : Prop :=
∀ h : List Ω, R.corrupt h = true →
uniformProb Ω (fun ω => R.fires h ω ∧ R.chkErr h ω) ≤
uniformProb Ω (fun ω => R.fires h ω) * A.εchk
/-- **Leg 2 (commitment binding)**: `Pr_ω[bindBreak h ω] ≤ ε_bind` at every history. -/
def BindLeg (A : AuditParams) (R : Round Ω) : Prop :=
∀ h : List Ω, uniformProb Ω (fun ω => R.bindBreak h ω) ≤ A.εbind
/-- **Miss decomposition**: if the round is corrupt, the audit fires, and no
alarm is raised, then either the checker failed soundness (`chkErr`) or the
commitment was double-opened (`bindBreak`). -/
def MissDecomp (R : Round Ω) : Prop :=
∀ (h : List Ω) (ω : Ω),
R.corrupt h = true → R.fires h ω = true → R.alarms h ω = false →
R.chkErr h ω = true ∨ R.bindBreak h ω = true
/-- All four single-round hypotheses bundled. -/
structure DetectionLegs (A : AuditParams) (R : Round Ω) : Prop where
beacon : R.BeaconLeg A
chk : R.ChkLeg A
bind : R.BindLeg A
miss : R.MissDecompC. Fail-Closed vs. Fail-Open Refutation (FailOpenRefutation)
If an implementation treats checker timeout or malformed proof (chkAbort) as a non-alarm ("fail-open", e.g., logging a warning and continuing), an adversary can deterministically abort whenever audited (chkAbort = true), achieving chkErr = false, bindBreak = false, and alarms = false. Ember proved both the sufficiency of FailClosed and the impossibility of DetectionLegs under FailOpen when $q > 0$ (Selvage/AuditSampling.lean and lines 895–980):
def FailClosed (R : Round Ω) : Prop :=
∀ (h : List Ω) (ω : Ω), R.fires h ω = true → R.chkAbort h ω = true → R.alarms h ω = true
def FailOpen (R : Round Ω) : Prop :=
∀ (h : List Ω) (ω : Ω), R.chkAbort h ω = true → R.alarms h ω = false
theorem missDecomp_of_failClosed {R : Round Ω}
(hfc : R.FailClosed)
(hraw : ∀ h ω, R.corrupt h = true → R.fires h ω = true → R.alarms h ω = false →
R.chkErr h ω = true ∨ R.chkAbort h ω = true ∨ R.bindBreak h ω = true) :
R.MissDecomp
theorem FailOpenRefutation.failOpen_no_legs (A : AuditParams) (hq : 0 < A.q) :
¬ Round.DetectionLegs A round
theorem FailOpenRefutation.honest_q_nonpos (A : AuditParams)
(hchk : Round.ChkLeg A honest) : A.q ≤ 0D. Single-Round Detection Lemma (Round.detect)
How $\varepsilon_{\text{chk}}$, $\varepsilon_{\text{bind}}$, and $\varepsilon_{\text{beacon}}$ compose: on any corrupt turn $h$, the event fires splits into alarms or a miss (fires ∧ ¬alarms). By MissDecomp, every miss implies fires ∧ chkErr or bindBreak. By finite-type cardinality decomposition (card_split_imp), $\Pr[\text{alarms}] \ge \Pr[\text{fires}] - \Pr[\text{fires} \wedge \text{chkErr}] - \Pr[\text{bindBreak}] \ge \Pr[\text{fires}](1 - \varepsilon_{\text{chk}}) - \varepsilon_{\text{bind}}$. Since $1 - \varepsilon_{\text{chk}} \ge 0$ (AuditParams.hchk_le_one), applying $\Pr[\text{fires}] \ge p - \varepsilon_{\text{beacon}}$ yields $\Pr[\text{alarms}] \ge (p - \varepsilon_{\text{beacon}})(1 - \varepsilon_{\text{chk}}) - \varepsilon_{\text{bind}} \ge p(1 - \varepsilon_{\text{chk}}) - \varepsilon_{\text{bind}} - \varepsilon_{\text{beacon}} = q$ (Selvage/AuditSampling.lean):
theorem detect [Nonempty Ω] (hL : DetectionLegs A R) {h : List Ω}
(hc : R.corrupt h = true) :
A.q ≤ uniformProb Ω (fun ω => R.alarms h ω)E. Supermartingale $M_t$, Optional Stopping Corrupt-Turn Bound $\mathbb{E}[C_\tau] \le 1/q$, and Leakage Bound $\mathbb{E}[\Lambda] \le b/q$
Rather than importing measure-theoretic probability spaces, Ember defined exact finite-horizon backward induction expOver over the $\sigma$-algebra of coin prefixes List Ω and proved Doob's optional stopping inequality le_of_step in 12 lines of induction (Selvage/AuditSampling.lean). Defining the stopped process at the first alarm $\tau = \inf\{t : \text{alarm}_t = 1\}$ and the potential $M_t = q \cdot C_{t \wedge \tau} - \mathbf{1}_{\{\tau \le t\}}$ (Round.mart), Ember proved (Selvage/AuditSampling.lean):
/-- Whether the process has stopped (an alarm has fired at or before this history). -/
def stopped (R : Round Ω) : List Ω → Bool
| [] => false
| ω :: h => R.stopped h || R.alarms h ω
/-- Pre-alarm corrupt-round counter `C_{t ∧ τ}`: increments on round `h → ω :: h`
iff the process was not yet stopped at `h` AND the prover corrupted round `h`. -/
def count (R : Round Ω) : List Ω → ℕ
| [] => 0
| _ :: h =>
if R.stopped h then R.count h
else if R.corrupt h then R.count h + 1 else R.count h
/-- The supermartingale potential `M(h) = q · C(h) − 1_{stopped(h)}`. -/
noncomputable def mart (R : Round Ω) (q : ℝ) (h : List Ω) : ℝ :=
q * (R.count h : ℝ) - (if R.stopped h = true then (1 : ℝ) else 0)
/-- **THE SUPERMARTINGALE STEP.** If every unstopped corrupt round alarms with
probability at least `q`, then `(1/|Ω|) ∑_ω M(ω :: h) ≤ M(h)` at **every** history `h`. -/
theorem mart_step [Nonempty Ω] {R : Round Ω} {q : ℝ}
(hdet : ∀ h : List Ω, R.stopped h = false → R.corrupt h = true →
q ≤ uniformProb Ω (fun ω => R.alarms h ω))
(h : List Ω) :
(∑ ω : Ω, R.mart q (ω :: h)) / (Fintype.card Ω : ℝ) ≤ R.mart q h
/-- **THE SEQUENTIAL CORRUPT-TURN BOUND (optional stopping).**
For any horizon `n` and any adaptive corruption strategy, if `q > 0` and every
unstopped corrupt round alarms with probability `≥ q`, then
`E[C_{n ∧ τ}] ≤ 1 / q`. -/
theorem sequential_bound [Nonempty Ω] {R : Round Ω} {q : ℝ} (hq : 0 < q)
(hdet : ∀ h : List Ω, R.stopped h = false → R.corrupt h = true →
q ≤ uniformProb Ω (fun ω => R.alarms h ω))
(n : ℕ) :
expOver Ω n (fun h => (R.count h : ℝ)) [] ≤ 1 / q
/-- **THE LEAKAGE COROLLARY.** If each undetected corrupt turn leaks at most
`b ≥ 0` bits, expected total leakage before the first alarm is at most `b / q`
bits — independent of the horizon `n` and of the adversary's adaptive schedule. -/
theorem leakage_bound [Nonempty Ω] {R : Round Ω} {q b : ℝ} (hq : 0 < q)
(hb : 0 ≤ b)
(hdet : ∀ h : List Ω, R.stopped h = false → R.corrupt h = true →
q ≤ uniformProb Ω (fun ω => R.alarms h ω))
(n : ℕ) :
expOver Ω n (fun h => b * (R.count h : ℝ)) [] ≤ b / q
/-- **THE END-TO-END COMPOSED THEOREM.** Under the three cryptographic legs
(`BeaconLeg`, `ChkLeg`, `BindLeg`) and `MissDecomp`, if
`q = p(1 − ε_chk) − ε_bind − ε_beacon > 0`, expected undetected corrupt turns
over any horizon `n` and any adaptive strategy is at most `1 / q`. -/
theorem sequential_bound_of_legs [Nonempty Ω] {A : AuditParams} {R : Round Ω}
(hL : DetectionLegs A R) (hq : 0 < A.q) (n : ℕ) :
expOver Ω n (fun h => (R.count h : ℝ)) [] ≤ 1 / A.qFurthermore, Selvage/AuditSampling.lean proves sampling_amortizes_only_the_checker and ledger_paid_in_full: per Boyle–Komargodski–Vafa (ePrint 2025/358, $\Omega(\log n / \log \log n)$ covert ledger lower bound), commit-then-audit amortizes the prover/checker cost $c_{\text{chk}}$ by $p$, while the commitment/ledger cost $c_{\text{com}}$ is paid on 100% of turns. And in BeaconRefutation (lines 795–888), Ember proved grind_beats_beaconless_bound and grind_honest_q_eq_zero: if the prover can grind $K$ candidate commitments before selecting one that avoids triggering a self-hashed Fiat-Shamir audit coin, $q$ collapses to $0$, proving that an external or VDF/threshold-delayed beacon is mandatory.
1.3 The Boundary Exchange-Rate Calculation (SELVAGE.md & boundary_exchange_rate.py)
In docs/SELVAGE.md §2 and paper/scripts/boundary_exchange_rate.py, Ember derived the quantitative law governing workload verification: why "proving boundaries, not interiors" is the only viable path to frontier zkML and vFHE.
A. Field-Multiplication Exchange Rate (78× to 308×)
In paper/scripts/boundary_exchange_rate.py, the cost of committing to one trace element in a hash-based PCS (FRI / WHIR / BaseFold over BabyBear with Poseidon2 width-16 rate-8 sponge, P2_MULS_BB = 655, P2_ADDS_BB = 1309, BB_OPEQ = 655 + 1309/3 = 1091.33 multiplication-equivalents per permutation, matrix width $w=48$, trace height $2^{20}$) versus virtualizing that wire via sumcheck ($d=3, k=2$) is:
# From paper/scripts/boundary_exchange_rate.py:39-64
def commit_cost_per_felt(log_blowup: int, log_h: int = 20, w: int = 48,
deg: int = 3, k: int = 2) -> dict:
B = 1 << log_blowup
# Merkle leaf + internal node Poseidon2 permutations per trace cell:
hash_perms = B * (1.0 / P2_RATE + 2.0 / w)
hash_muls = hash_perms * BB_OPEQ
# Radix-2 butterfly LDE + interpolation field muls per trace cell:
encode_muls = (B + 1) * log_h / 2.0
# Sumcheck prover work per value per layer (deg=3, k=2, EF4=10 base muls):
sumcheck_muls = (deg - 1) * k * 10
total = hash_muls + encode_muls + sumcheck_muls
return {"hash": hash_muls, "encode": encode_muls, "sumcheck": sumcheck_muls,
"total": total, "ratio_vs_virtual": total / sumcheck_muls}| Blowup $2^b$ | Poseidon2 Merkle Hashing | Reed-Solomon LDE Encoding | Sumcheck Folding | Total Committed Cost / Felt | Virtual Sumcheck Cost / Felt | Exchange Ratio (Commit / Virtual) |
|---|---|---|---|---|---|---|
| $b = 4$ ($16\times$) | $2,910$ muls ($93.3\%$) | $170$ muls ($5.4\%$) | $40$ muls ($1.3\%$) | $3,120$ field muls | $\approx 40$ field muls | $78\times$ |
| $b = 6$ ($64\times$) | $11,641$ muls ($94.4\%$) | $650$ muls ($5.3\%$) | $40$ muls ($0.3\%$) | $12,331$ field muls | $\approx 40$ field muls | $308\times$ |
B. Consequence for $n \times n$ Matrix Multiplication
For $C = A \cdot B$ with $n = 4096$:
- Materializing the interior (AIR trace cells for $a_{ik}, b_{kj}, a_{ik}b_{kj}$, and running sum $s_{ijk}$): commits $4n^3 = 2.75 \times 10^{11}$ field elements.
- Proving the boundary (committing only the boundary matrices $A, B, C$ and reducing $\tilde{C}(r_i, r_j) = \sum_{k \in \{0,1\}^{\log n}} \tilde{A}(r_i, k)\tilde{B}(k, r_j)$ via $\log_2 n = 12$ sumcheck rounds, formalized in
Assurance/ZkmlMatmulSumcheck.lean): commits $3n^2 = 5.03 \times 10^7$ field elements — a $\frac{4}{3}n = 5,461\times$ reduction in committed trace volume (docs/SELVAGE.md).
C. Wall-Clock Calibration & Narrow Poseidon2 In-AIR Virtualization
In notes/virtualization-verdict.md and docs/VERDICTS.md §4, Ember calibrated the exchange rate against actual wall-clock nanoseconds at log_blowup = 3: because Poseidon2 hashing SIMD-vectorizes ~8× more densely than extension-field sumcheck folding, 1 marginal committed felt costs 54.7 ns vs 10.97 ns per value per sumcheck layer (~5× wall-clock exchange rate). Consequently:
- High-degree GKR sumcheck over $x^7$ loses ($\alpha + 1 = 8$ rounds > 5× exchange rate), whereas $\alpha = 3$ (e.g., over $p_{61}$ where $\gcd(3, p_{61}-1)=1$) wins by ~1.3×.
- In-AIR virtualization of degree-1 internal rounds (
permEmissionNarrowinbreadstuffs/metatheory/Dregg2/Circuit/Emit/Poseidon2RoundGates.lean, commitdaa207ae7) substitutes the 15 non-S-box lanes symbolically across all 13 partial rounds without raising constraint degree above 7, shrinking the Poseidon2 AIR from 352 $\to$ 141 gates (2.34× fewer committed cells, 1.97× fewer prover permutations).
2. Model Identity & Weight-Commitment Registry (zkml-research/registry/)
2.1 The Hollow-LLM Gap & Microsite #13 Which model?
In registry/MANIFEST-FORMAT.md and microsite #13 Which model? (/Users/ember/src/dregg-microsites/which-model/index.html), Ember addressed the Hollow-LLM attack (arXiv 2607.28884):
- A zero-knowledge proof of inference proves $(x, y) \in \mathcal{R}_C$ for some weight commitment $C$.
- Without a public, byte-reproducible binding from $C$ to a named checkpoint's weights and architecture, a serving provider can commit to a 0.6B or pruned/lobotomized model $C_{\text{hollow}}$, generate 100% mathematically valid ZK proofs against $C_{\text{hollow}}$, and bill customers for frontier 671B/1.56T inference ("a hollow model behind an honest proof").
2.2 registry_tool.py & gates.sh: Streaming Range-Request Verification
In registry/registry_tool.py (1,224 lines, Python 3 stdlib-only, commit 020fd7faf22eff7e0dd8739ee386b36485b231be, 2026-08-13) and registry/gates.sh (11-gate falsifier suite G1–G10), Ember built a streaming weight-commitment tool that never downloads multi-hundred-gigabyte checkpoints to disk:
- Domain-Separated Canonical Commitment: Prepends the 24-byte ASCII prefix
DOMAIN_TAG = b"zkml-weight-registry/v1\n"(registry_tool.py:56) to the strict RFC 8785 / JCS-subsetcanonical_bytes(core)(sorted UTF-8 keys, zero whitespace, floats forbidden by type error incore). - Frozen Test Vector (Gate G9):
registry/test-vector.json, 856-byte canonical core + 24-byte domain tag = 880-byte preimage, SHA-2561b34613e012a472aa38b25f760f4ca17ed016058b49d4e95aab141a4a9b2a0e0. - Constant-Memory Range Streaming: Uses HTTP
Range: bytes=0-7andRange: bytes=8-{8+N-1}to parse every.safetensorsshard header, validates that tensor[begin, end)intervals form an exact zero-gap partition of the shard body, and infullmode streams each shard once in 16 MiB chunks while updating per-tensor and whole-shard SHA-256 states simultaneously, followed by a 4 KiB interior range-spotcheck (verify_spotcheck).
2.3 All 8 Committed Frontier Checkpoints (registry/COMMITMENTS.md)
From registry/COMMITMENTS.md and registry/manifests/*.json:
Model (repo_id) | Git Revision | Mode | commitment_sha256 | Tensors | Shards | Total Weight Size | Streamed Bytes & Wall Time |
|---|---|---|---|---|---|---|---|
openai/gpt-oss-20b | 6cee5e81ee8382eff0b237b5a894acda3d725799 | full | 3218eb92942a115dcc79ef1acd8778702991be0a034acc5ab55eb26be47db61f | 459 | 3 | 13,780,382,664 B (13.76 GB) | 13,789 MB, 24 reqs, 27.3 min (8.4 MB/s) |
Qwen/Qwen3-8B | b968826d9c46dd6066d109eabc6255188de91218 | full | 13adc299c5f4d3f8e1c9bdfac84d890c3e3ea6ede6b2bae5fdaa7df8651910fa | 399 | 5 | 16,381,559,928 B (16.38 GB) | 16,398 MB, 34 reqs, 34.0 min (8.0 MB/s) |
Qwen/Qwen3-0.6B | c1899de289a04d12100db370d81485cdf75e47ca | full | bed2361d5898823569760ebf4bc7998a9bdbc90426afe78c30692aa2c465ba5d | 311 | 1 | 1,503,262,216 B (1.50 GB) | 1,519 MB, 12 reqs, 2.2 min (11.5 MB/s) |
openai/gpt-oss-120b | b5c939de8f754692c1647ca79fbf85e8c1e70f8a | structure-only | b8699decd118b360206bf47f7783c5ab50706d80fcbc33d75a91577c38de8a76 | 687 | 15 | 65,248,686,280 B (65.25 GB) | 28.2 MB, 69 reqs, 26.7 s |
google/gemma-3-27b-it | 005ad3404e59d6023443cb575daa05336842228a | structure-only | 7752d385091eea4476db4b51694894f9c402acd38a08d2ddd07b07b08e29eb5e | 1,247 | 12 | 54,859,193,152 B (54.86 GB) | 35.1 MB, 58 reqs, 30.9 s |
meta-llama/Llama-3.1-8B-Instruct | 0e9e39f249a16976918f6564b8830bc894c89659 | structure-only | 15e0a6c49eb594cbf20e6db9c6c047fe4b1c3b1bc6107f7b204f3f7e67083261 | 291 | 4 | 16,060,617,216 B (16.06 GB) | 9.3 MB, 24 reqs, 9.3 s |
deepseek-ai/DeepSeek-V3.1 | c0781d039fb7be8ec0bef9fe5ef1cb6cde44fb0f | structure-only | 5db967ae32cc5e96ad951bab72b5ab2fb7c6cb94400e23f209fc7aa589d5e9ba | 91,991 | 163 | 688,588,547,912 B (688.59 GB) | 49.5 MB, 659 reqs, 7.5 min |
moonshotai/Kimi-K3 | 9f62e4e9fffb94f1eb9b5fd9f1a09bc7d2fb8f04 | structure-only | 9bf53e646d4b9b9609d6140d0b710140e92a65fcd9ad68b6f7c5d1c3b07d5a2b | 497,220 | 96 | 1,560,938,871,920 B (1.56 TB) | 271.1 MB, 391 reqs, 4.5 min |
(Note: The registry lane also proved via authenticated HuggingFace probe in registry/runs/deepseek-ai__DeepSeek-V4.gated.log that deepseek-ai/DeepSeek-V4 returned HTTP 404, refuting earlier secondary-source citations.)
2.4 Ember's Critique & The v2 Poseidon2 Per-Expert Merkle Root Design
On 2026-08-13 at 18:36 (forcodex/01b-STEERS-RECOVERED.md §22, commit dd331697e2d6b89bdd1cddcb9e071be0631567be), Ember rejected the v1 flat SHA-256 manifest as a proof-system primitive:
"bruv you just built a complete toy registry for a commitment that is irrelevant to all possible proof systems and patted yourself on the back"
As recorded in registry/WHAT-THIS-IS-NOT.md, docs/VERDICTS.md §5, and notes/moe-router-binding.md §5.3 D4/D9, a flat SHA-256 digest over raw .safetensors bytes cannot be opened by an algebraic STARK/sumcheck prover without running SHA-256 over 688 GB–1.56 TB inside the circuit. The v2 Registry Design specifies:
- Proof-Native Field Encoding: Tensors are committed in the exact field-element layout consumed by the prover (e.g., packed E2M1 nibbles + E8M0 scales in KoalaBear/BabyBear/$p_{61}$).
- Per-Expert Poseidon2 / FRI Merkle Roots ($R_{\ell,e}$): Each expert $e \in \{0, \dots, E-1\}$ of MoE layer $\ell$ (consisting of
gate_proj,up_proj,down_projand their scale tensors) is committed to its own Poseidon2 Merkle root $R_{\ell,e} \in \mathbb{F}^8$, alongside separate roots for the router matrix $W_r$ ande_score_correction_bias$b$. - Verifier-Side $O(E)$ MLE Opening: The vector of per-expert roots $R_\ell \in (\mathbb{F}^8)^{257}$ is only $257 \times 32\text{ B} = 8.2\text{ KB}$ per layer (477 KB across all 58 MoE layers of DeepSeek-V3.1). For each selected expert $j \in \{1, \dots, k\}$, the verifier evaluates the multilinear extension $\tilde{R}_\ell(\text{bits}(\text{id}_j))$ directly in $O(E) = 257$ field operations per layer (14,848 field ops/token total), binding the active expert's weight polynomial commitment $C_j$ to its selected router index $\text{id}_j$ without ever opening the inactive 96.5% of the model.
3. Bit-Exact Native MXFP4 Arithmetization & MoE Router Binding
3.1 Why Approximate-Float zkML Is Mathematically & Empirically Broken
In docs/the-position.md, docs/PHASE0-RESULT.md, and forcodex/04-DEAD-ENDS.md §F2, Ember established two decisive refutations of $\varepsilon$-tolerant floating-point zkML:
- Or Zamir's Theorem 1 (arXiv
2602.15756, Feb 2026 — "Undetectable Backdoors in Approximate zkML"): - Any proof system that replaces exact equality with an $\varepsilon$-consistency check $|y - f(x)| \le \delta$ at each layer allows a malicious prover to steer the output across layers: error amplifies by $2^{18}$ across depth 20 with a trigger weight of $\approx 0.15$.
- Stronger still, Zamir Theorem 1 proves that for any neural network $F$, there exists a network $F'$ that is identically equal to $F$ on all inputs ($\forall x, F'(x) = F(x)$, requiring zero weight inflation) such that for every input $x$ and every target output $z$ in the output range, there exists a $\delta$-consistent transcript whose output is $z$.
- Spain (NYU Courant, OSDI 2026) Empirical & Soundness Collapse:
- On GPT-2 (
seq=32), Spain's own Figure 4 reports that its approximate-float prover loses to quantizedzkGPTon every metric: 750 s vs 64 s prover time (11.7× slower), 78 s vs 5.8 s verifier time (13.4× slower), and 1.6 MB vs 88 KB proof size (18.6× larger). - Worse, Spain's composition lemma yields a ReLU tolerance of $\delta = \sqrt{\varepsilon} = 2^{-20}$ at its published ML parameters, where Zamir's trigger weight at GPT-2 effective depth ($\ge 24$) is $\le 10$ — meaning Spain is exploitable at its own published parameters with ordinary weights.
3.2 Phase 0 Exhaustive BF16 Census (phase0/product_exact/)
Before pivoting to MXFP4, Ember tested whether bf16 could be proved bit-exactly without IEEE-754 circuits (phase0/product_exact/src/main.rs, results in phase0/results_product_exact.txt):
- Exhaustively tested all $2^{32} = 4,294,967,296$ ordered
(bf16, bf16)pairs in 390.86 ms on 8 threads: exact:3,271,328,768(76.16656%of $2^{32}$)inexact_finite:990,149,632(23.22552%of finite pairs):533,735,952overflow to $\pm\infty$ ($12.52\%$),351,288,832underflow to $\pm 0$ ($8.24\%$),97,927,136round in the fp32 subnormal tail ($2.30\%$), and0(0.00000%) round in the normal fp32 range.- Over the exponent-sum window $-126 \le e_x + e_y \le 126$, 100.000% of all
3,179,217,920pairs are bit-exact. - However,
phase0/cost_model.py(docs/PHASE0-RESULT.md, commitf81dd5787f46541d83be5cafd52c6c5fc3b4ad20) proved that becausebf16has a per-element exponent rather than a block-shared exponent, data-dependent renormalization shifts reduce thebf16speedup overint8to 1.42× (whereas a static shared block exponent achieves 2.29×, range 1.51–3.30×).
3.3 Bit-Exact Native OCP MXFP4 Arithmetization (docs/mx-formats.md, phase0/e8m0_spread.py)
In docs/mx-formats.md (commits f068d4670c2c71a610bcab044f196e3a2f49e8dd, 7fdc981fbc50c760a4d1f4093a57b599349a866b, bc52ca55b741d4198c4eabe67281442c7ce9bcb5, 2c9968fcdd2f2dc5ff8ecb18ec0e4b8be6f7c075), Ember discovered that OCP Microscaling MXFP4 — the actual native shipping format of frontier MoE checkpoints (openai/gpt-oss-20b, openai/gpt-oss-120b, moonshotai/Kimi-K3) — satisfies all three requirements (zero quantization semantic gap, static block shifts, and bit-exact integer associative accumulation):
- Exact 13-Bit Signed Integer Block-32 Dot Products ($\pm 4,608$):
- An OCP MXFP4 block consists of $k = 32$
E2M1elements (1 sign bit, 2 exponent bits, 1 mantissa bit) sharing a single 8-bitE8M0power-of-two scale $2^{s - 127}$. - Every
E2M1element takes one of 16 values in $\{0, \pm 0.5, \pm 1.0, \pm 1.5, \pm 2.0, \pm 3.0, \pm 4.0, \pm 6.0\}$. - Scaled by $2$, every
E2M1element $2a_i$ is an exact small integer in $\{0, \pm 1, \pm 2, \pm 3, \pm 4, \pm 6, \pm 8, \pm 12\}$. - Therefore, each elementwise product $(2a_i)(2b_i) = 4 a_i b_i$ is an exact integer in $[-144, +144]$, and the 32-element within-block dot product $$D_{\text{block}} = \sum_{i=1}^{32} (2a_i)(2b_i) \in [-4608, +4608]$$ is an exact integer bounded by $\pm 4,608$ (fitting in 13 bits signed, $[-4096, 4095]$ / $< 2^{13} = 8192$, or $\pm 1,152$ in unscaled units). Verified over 20,000 random MXFP4 blocks under two summation orders against exact rationals with zero deviations (
docs/mx-formats.md:127-131). - (Why NVFP4 does not transfer: NVIDIA's 16-element NVFP4 uses
E4M3fractional block scales with an FP32 per-tensor scale, destroying the power-of-two shift property; the arithmetization is strictly OCP MXFP4-specific,docs/mx-formats.md:3-8).
- Empirical E8M0 Exponent-Spread Census on
openai/gpt-oss-20b(phase0/e8m0_spread.py&results_e8m0_spread.txt): - In
phase0/e8m0_spread.py(commit2c9968fcdd2f2dc5ff8ecb18ec0e4b8be6f7c075, 2026-08-13), Ember range-fetched the rawU8E8M0 scale tensors ofopenai/gpt-oss-20b(90blocks of 32 per reduction row of length $2880$). - Across
1,382,400reduction rows (124,416,000scale bytes across 10 sampledgate_up_proj_scales[32, 5760, 90]anddown_proj_scales[32, 2880, 90]tensors in layers0, 5, 11, 17, 23; out of 48 total MoE block/scale tensor pairs in the 24-layer checkpoint),phase0/results_e8m0_spread.txtmeasured: - Per-row exponent spread ($\max_{b \in [0,90)} s_b - \min_{b \in [0,90)} s_b$): p50 = 2, p90 = 2, p99 = 3, max = 8.
- Exact pooled distribution:
spread = 0:42rows (0.0030%, cumulative0.00304%)spread = 1:541,154rows (39.1460%, cumulative39.14902%)spread = 2:766,937rows (55.4787%, cumulative94.62768%)spread = 3:68,774rows (4.9750%, cumulative99.60265%)spread = 4:4,443rows (0.3214%, cumulative99.92405%)spread = 5:812rows (0.0587%, cumulative99.98278%)spread = 6:219rows (0.0158%, cumulative99.99863%)spread = 7:17rows (0.0012%, cumulative99.99986%)spread = 8:2rows (0.0001%, cumulative100.00000%)- Special/NaN scale bytes (
0or255):0(value 0 x0, value 255 x0). - Consequence: 100.000% of all reduction rows fit inside a width-8 alignment window ($W \le 8$), meaning cross-block accumulation across all 90 blocks of a row requires at most an 8-bit shift ($4608 \times 90 \times 2^8 = 1.06 \times 10^8 < 2^{27} < p_{\text{BabyBear}}$), completely avoiding wide Kulisch accumulators on 100% of
gpt-oss-20b's MXFP4 weights (which represent 98.1% of model parameters and 78.9% of per-token linear FLOPs).
3.4 MoE Router Binding (notes/moe-router-binding.md & moe-router-binding-cost.py)
In notes/moe-router-binding.md and notes/moe-router-binding-cost.py (commit a69aeb61a944c53e23a8bda86ebde4ca7f31b4f2, 2026-08-13), Ember analyzed how to prove sparse Mixture-of-Experts (MoE) inference (DeepSeek-V3/R1: $E=256$ routed experts + 1 shared, $k=8$ active per token; gpt-oss-120b: $E=128, k=4$; Kimi-K3: 2.4T–2.8T total) at active-parameter cost rather than dense-parameter cost.
A. Two Soundness Bugs Discovered in Prior Art (ZK-DeepSeek & OP-10)
- Bug 1 — BF16 Score Ties Give ~23 Bits of Routing Freedom Per Token:
OP-10(arXiv2606.05433§4.4.3) claims top-$k$ ties are "rare with BF16", andZK-DeepSeek(arXiv2511.19902§3.7) enforces only non-decreasing sorted order $L'[i-1] \le L'[i]$ via multiset permutation without proving permutation of indices.- Ember proved this is mathematically backwards (
notes/moe-router-binding.md:94-110, 419-462): BF16 has only 7 mantissa bits ($2^7 = 128$ binades), which is smaller than the number of experts ($E = 256$). Worse, DeepSeek-V3 uses a sigmoid router where top experts cluster near $1.0$: in $[0.9, 1.0)$, there are only 26 distinct BF16 values across 256 experts! By pigeonhole, ~10–15 experts tie near the top-$k$ boundary on every token, giving a malicious prover $\binom{12}{4} \approx 495$ choices per layer or ~23 bits of silent routing freedom per token to pick weaker or poisoned experts while satisfyingZK-DeepSeek's constraints. - The Fix — Canonical Composite Key
(C3): Shift each quantized score $v_i \in [0, 2^B)$ by $\lceil \log_2 n' \rceil$ bits and pack the inverted index $(n' - 1 - i)$ into the low bits so all keys are strictly distinct and ties break lowest-index-first (matching PyTorchtorch.topk/ vLLMmoe_topk): $$\text{key}_i := v_i \cdot 2^{\lceil \log_2 n' \rceil} + (n' - 1 - i) + 1 \in [1, 2^{B + \lceil \log_2 n' \rceil}]$$ - Bug 2 — Monolithic Weight MLE Opening Restores Full 671B Dense Cost:
ZK-DeepSeekreuses weight-matrix proofs across tokens without binding the expert index $\vec{e}$ to the router output (notes/moe-router-binding.md:107-110).- Conversely, if a prover commits to a single monolithic layer tensor $\tilde{W}(\vec{e}, \vec{u}, \vec{v})$ and opens it at $\vec{e} = \text{bits}(\text{id}_j)$ via sumcheck/PCS, a multilinear PCS opening touches every coefficient of $\tilde{W}$ in $\Theta(E \cdot d \cdot f)$ time — completely erasing the 18.3× sparse MoE discount (
notes/moe-router-binding.md:486-526). - The Fix — Per-Expert Commitments ($R_{\ell,e}$): Commit each expert $e$ to its own root $R_{\ell,e}$ and open the tiny 257-element vector $R_\ell$ verifier-side in $O(E) = 257$ field ops.
B. Variant (b) Threshold Top-$k$ Argument & The 0.72% Trace Overhead
Instead of sorting all $n=256$ experts via a 1,920-cell Batcher bitonic network + 1,040 LogUp terms (Variant (a), which took ZK-DeepSeek 2,447 s for 24 tokens), Ember designed Variant (b) (notes/moe-router-binding.md:306-384): witness the binary selection mask $\sigma \in \{0,1\}^n$ and a single threshold $\tau \in \mathbb{F}$ satisfying:
(C1)$\sigma_i \cdot (1 - \sigma_i) = 0\quad \forall i \in [0, n)$(C2)$\sum_{i=0}^{n-1} \sigma_i = k$(C3)$\text{key}_i = v_i \cdot 2^{\lceil \log_2 n \rceil} + (n - 1 - i) + 1$(C4)$\text{RangeCheck}(\Delta_i \in [0, 2^{B'})) \quad \text{where } \Delta_i = \sigma_i(\text{key}_i - \tau) + (1 - \sigma_i)(\tau - 1 - \text{key}_i)$(C5)$\text{RangeCheck}(\tau \in [0, 2^{B'}))$ (mandatory wraparound-trap guard preventing $\tau = p - M$ from wrapping mod $p$).
From notes/moe-router-binding-cost.py, the exact per-token, per-MoE-layer cost in DeepSeek-V3 ($d=7168, E=256, k=8 + 1\text{ shared}, f=2048$):
| Component (Per Token, Per MoE Layer) | Committed Felts | Lookup Multiplicity | Sumcheck MACs | Share of Total Sparse Layer |
|---|---|---|---|---|
| 9 Active Experts ($9 \times 3$ matmuls + SwiGLU) | 145,408 | 119,808 | 396,361,728 | 99.28% |
| Router Matmul ($1 \times 7168 \times 256$) + Bias + Sigmoid | 529 | 512 | 1,835,008 | 0.36% |
| Variant (b) Selection + Index + Weight Binding | 530 | 804 | 0 | 0.36% |
| Total Router + Binding Overhead | 1,059 | 1,316 | 1,835,008 | 0.72% committed / 1.09% lookups / 0.46% MACs |
| Total Sparse Layer (Proving 9 of 257 Experts) | 146,467 | 121,124 | 398,196,736 | 27.0× fewer committed felts / 28.4× fewer MACs vs dense |
Across the entire 61-layer DeepSeek-V3 model, proving only the active experts + router binding yields an 18.30× whole-model prover speedup at $C=1$ (15.69× at $C=4096$, 7.37× at $C=32,768$, 2.74× at $C=131,072$).
C. Hybrid Audit Inversion & Zero-Knowledge Requirement
In notes/moe-router-binding.md §6.3 and docs/VERDICTS.md §5, Ember combined this 0.72% trace share with AuditSampling.lean:
- Hybrid Audit Inversion: Instead of sample-auditing the entire layer at rate $p$, prove the router and expert-selection binding on 100% of tokens (adding only 0.72% trace overhead, or 0.29% forward-pass compute if checked directly on committed activations) and sample-audit only the expensive active-expert matmuls at rate $p$. This eliminates assumption
A7(routing-fraud invisibility) and $\varepsilon_{\text{beacon}}$ from the routing step completely (q_router = 1). - Mandatory Zero-Knowledge (
topk_idsHiding): Because a sequence decoder recovers 91.2% of tokens top-1 (94.8% top-10) from expert selections alone (forcodex/04-DEAD-ENDS.md§F3), the router binding proof must keeptopk_idsin the private ZK witness rather than opening expert indices in the clear.
4. Verifiable FHE (vFHE), Encrypted Continual Learning & Joint Modulus Selection
4.1 The Joint Modulus Theorem in Lean 4 (Theory/CyclotomicInertia.lean)
In vFHE (proving correct execution of BFV/RLWE/TFHE homomorphic operations inside a STARK/WHIR/BaseFold proof), existing literature splits into two incompatible parameter regimes (paper/DRAFT.md):
- Zama 2025/719 (Bootstrapping in Plonky3): Uses BabyBear ($p = 2^{31} - 2^{27} + 1$), whose 31-bit ceiling forces RNS decomposition or limits depth, and over which $\Phi_{81}(X) = X^{54} + X^{27} + 1$ splits into two degree-27 factors.
- Zama 2026/027 (WHIR Encrypted Matvec over Goldilocks): Uses Goldilocks ($p = 2^{64} - 2^{32} + 1$) with cyclotomic ring $\Phi_{81}(X)$ (degree $d = \varphi(81) = 54$), where $\Phi_{81}$ is irreducible so $\mathbb{Z}_p[X]/(\Phi_{81}(X)) \cong \mathbb{F}_{p^{54}}$ enables a single-evaluation Schippel/sumcheck verification of degree-54 polynomial products. However, Goldilocks has 2-adicity $\nu_2(p-1) = 32$. At message length $2^{28}$ with rate $2^{-4}$, WHIR requests a radix-2 FFT domain of size $2^{32}$ inside the quadratic submodule ($G^2$, order $(p-1)/2$), which has 2-adicity 31 — causing
Domain::newto panic at $\nu = 32$!
In minidregg/Theory/CyclotomicInertia.lean (1,191 lines, 88+ theorems, zero sorry, zero native_decide, landed in commits 6298fcc23c9c315a3f33d362466a6c86801accfa and 641ceeb9fbfa468935696310afead8df55db791c on 2026-08-13), Ember proved the complete number-theoretic characterization of the prime family $p_n = 127 \cdot 2^n + 1$ and certified the 61-bit prime $$p_{61} = 2^{61} - 2^{54} + 1 = 127 \cdot 2^{54} + 1 = 2,287,828,610,704,211,969$$ which simultaneously provides 2-adicity 54 (22 doublings larger than Goldilocks, fitting natively in signed i64) and maximal 3-adic cyclotomic inertia ($\Phi_{3^k}(X)$ irreducible over $\mathbb{F}_{p_{61}}$ for every $k \ge 1$).
Verbatim Lean 4 Definitions & Theorem Signatures from Theory/CyclotomicInertia.lean:
/-- The KoalaBear prime `2^31 - 2^24 + 1 = 127 · 2^24 + 1 = 2130706433`. -/
def koalaBear : ℕ := 2 ^ 31 - 2 ^ 24 + 1
/-- The BabyBear prime `2^31 - 2^27 + 1 = 15 · 2^27 + 1 = 2013265921`. -/
def babyBear : ℕ := 2 ^ 31 - 2 ^ 27 + 1
/-- The Mersenne-31 prime `2^31 - 1 = 2147483647`. -/
def mersenne31 : ℕ := 2 ^ 31 - 1
/-- **Maximal 3-adic cyclotomic inertia**: a prime `p` is primitive modulo `3^{k+1}`
for every `k : ℕ`, i.e., the residue of `p` generates `(ℤ/3^{k+1}ℤ)×` (which has
order `φ(3^{k+1}) = 2 · 3^k`) at every level of the 3-adic tower simultaneously. -/
def MaximalThreeAdicInertia (p : ℕ) : Prop :=
∀ k : ℕ, orderOf ((p : ZMod (3 ^ (k + 1)))) = 2 * 3 ^ k
/-- **The `127 · 2^n + 1` prime family**: `familyP n = 127 * 2^n + 1`. -/
def familyP (n : ℕ) : ℕ := 127 * 2 ^ n + 1
/-- **THE FAMILY CHARACTERIZATION THEOREM.**
For any `n : ℕ` such that `p_n = 127 · 2^n + 1` is prime:
`MaximalThreeAdicInertia (127 · 2^n + 1) ↔ n % 6 = 0 ∨ n % 6 = 2`. -/
theorem familyP_maximalInertia_iff {n : ℕ} (hp : (familyP n).Prime) :
MaximalThreeAdicInertia (familyP n) ↔ n % 6 = 0 ∨ n % 6 = 2
/-- **Equivalence with cyclotomic irreducibility at all 3-powers**: for any prime
`p ≠ 3`, `MaximalThreeAdicInertia p` holds if and only if `Φ_{3^{k+1}}(X)` is
irreducible over `ℤ/pℤ` for every `k ≥ 0`. -/
theorem maximalThreeAdicInertia_iff_irreducible {p : ℕ} (hp : p.Prime) (hp3 : p ≠ 3) :
MaximalThreeAdicInertia p ↔
∀ k : ℕ, Irreducible (cyclotomic (3 ^ (k + 1)) (ZMod p))
/-- **The 61-bit joint vFHE/STARK prime**:
`p61 = 2^61 - 2^54 + 1 = 127 · 2^54 + 1 = 2287828610704211969`. -/
def p61 : ℕ := 2 ^ 61 - 2 ^ 54 + 1
theorem p61_sub_one : p61 - 1 = 2 ^ 54 * 127
theorem not_two_pow_55_dvd_p61_sub_one : ¬2 ^ 55 ∣ p61 - 1
/-- **Primality of `p61 = 2^61 - 2^54 + 1`**, kernel-verified via a Lucas
primality certificate for `p61 - 1 = 2^54 · 127` with witness `g = 3`. -/
theorem p61_prime : Nat.Prime p61
/-- **`p61` has maximal 3-adic cyclotomic inertia**, derived directly from the
family characterization theorem `familyP_maximalInertia_iff` via `54 % 6 = 0`. -/
theorem maximalInertia_p61 : MaximalThreeAdicInertia p61
theorem orderOf_p61_three_pow (k : ℕ) :
orderOf ((p61 : ZMod (3 ^ (k + 1)))) = 2 * 3 ^ k
theorem irreducible_cyclotomic_three_pow_p61 (k : ℕ) :
Irreducible (cyclotomic (3 ^ (k + 1)) (ZMod p61))
theorem irreducible_cyclotomic_81_p61 :
Irreducible (cyclotomic 81 (ZMod p61))
/-- The cyclotomic ring `ℤ/p61ℤ[X]/(Φ₈₁(X))` is a field (`𝔽_{p61^54}`). -/
noncomputable def P61Cyc81_isField : IsField P61Cyc81
/-- `P61Cyc81` has dimension `φ(81) = 54` over `ℤ/p61ℤ`. -/
theorem P61Cyc81_finrank : Module.finrank (ZMod p61) P61Cyc81 = 54
/-- **Refutation of Goldilocks at `2^33`** (the WHIR `ν = 32` quadratic-fold wall):
no element of `(ℤ/p_G ℤ)×` has multiplicative order `2^33`. -/
theorem goldilocks_no_domain_two_pow_33 :
¬∃ g : (ZMod goldilocks)ˣ, orderOf g = 2 ^ 33
/-- **Positive theorem for `p61` at `k ≤ 54` (including `k = 33`)**:
for every `k ≤ 54`, `(ℤ/p61 ℤ)×` has a multiplicative subgroup of order `2^k`. -/
theorem p61_domain_exists {k : ℕ} (hk : k ≤ 54) :
∃ g : (ZMod p61)ˣ, orderOf g = 2 ^ kAnd for refutation teeth, Theory/CyclotomicInertia.lean also proves:
theorem not_irreducible_cyclotomic_81_babyBear : ¬Irreducible (cyclotomic 81 (ZMod babyBear))(card_factors_81_babyBear = 2factors of degree 27)theorem not_irreducible_cyclotomic_81_mersenne31 : ¬Irreducible (cyclotomic 81 (ZMod mersenne31))(card_factors_81_mersenne31 = 6factors of degree 9)theorem splits_negacyclic {k : ℕ} (hk : k + 1 ≤ 24) : (X ^ (2 ^ k) + 1 : (ZMod koalaBear)[X]).Splits (RingHom.id (ZMod koalaBear))(power-of-two cyclotomics $\Phi_{2^{k+1}}(X) = X^{2^k}+1$ split completely into $2^k$ linear factors over high-2-adicity STARK primes!)theorem familyP_214_prime : Nat.Prime (familyP 214)andtheorem card_factors_9_familyP_214 : (UniqueFactorizationMonoid.normalizedFactors (cyclotomic 9 (ZMod (familyP 214)))).card = 3(a 67-digit prime in the bad congruence class $n = 214 \equiv 4 \pmod 6$ where $\Phi_9(X)$ splits into 3 quadratics, proving that the condition $n \bmod 6 \in \{0, 2\}$ is non-vacuous).
4.2 Empirical Results of the $p_{61}$ Swap & Honest Assessment (paper/DRAFT.md, paper/HONEST-ASSESSMENT.md)
In /Users/ember/src/matvecmul-p61 (commit c789c8d, 2026-08-13) and paper/DRAFT.md, Ember swapped Goldilocks $\to p_{61}$ inside Zama's matvecmul WHIR codebase:
- Unblocked $\nu = 32$ and Cut Kimi-K3 Chunking by 8×: Raising the domain ceiling from $2^{32} \to 2^{54}$ eliminated the
Domain::newpanic at $\nu=32$ and reduced the chunk count for a 5%-activeKimi-K3forward pass (~140B active weights) from 1,788 field-bound chunks to 224 memory-bound chunks. - 10–40% Prover Speedup on M2 Max: Because $p_{61} < 2^{61}$ fits in unsigned 64-bit limbs with 3 bits of lazy addition headroom (vs Goldilocks' $2^{64}-2^{32}+1$ requiring 64-bit overflow handling),
matvecmul-p61ran 10–40% faster across $\nu \in [19, 25]$. - Exposed 4 Hidden Goldilocks Bugs in Zama's Reference Codebase: Including a hardcoded
(x >> 47) & 1RLWE decoding bit-shift that assumed a 64-bit modulus anddelta = 1 << 48— a bug where 12/12 unit tests passed while decrypted RLWE ciphertexts were silently garbage until replaced by balanced centered rounding((c_centered * t + q/2) / q) mod t. - Honest Assessment (
paper/HONEST-ASSESSMENT.md&VERDICTS.md§3b): - While $p_{61}$ is listed as row $c=127, n=54$ of Riesel's 1994 Birkhäuser prime table (
paper/PRIOR-ART-COLLAPSE.md), its joint selection for 2-adic STARK FFT + 3-adic cyclotomic inertia is new. - For the 109-bit 3-limb RNS BFV regime in
breadstuffs/fhegg-fhe, Ember also discovered greenfield 36/37-bit NTT+FRI limb primes (0xfed000001,0xfd9000001,0x1ff5000001, $\log_2 Q = 108.978$, 2-adicity 24,docs/VERDICTS.md§3b) and proved the Cross-Limb Binding Vulnerability (Hole Aprovenance quantifier swap $\forall i \exists \text{src} \neq \exists \text{src} \forall i$, andHole Bnon-limb-local rounding $\lfloor t \cdot x / Q \rceil$) inbreadstuffs/metatheory/Bfv/CrossLimb.lean(commit5b653ba5d).
4.3 Verifiable Dark Continual Learning (DARK-TRAINING.md, Rank1GradientCheck.lean, ZkmlLowRankUpdate.lean, & vfhe_2026_09_08)
Motivated by Ember's 2026-08-13 22:41 steer (forcodex/01b-STEERS-RECOVERED.md §26: "because we are going to want verifiable dark continual-learning at some point, and if the weights aren't fully encrypted truly terrible things may befall the mind within"), Ember built both the formal training-step reductions in minidregg and the executable encrypted continual learner in zkml-research:
- Rank-1 Gradient Check in $O(1)$ Rounds (
Selvage/Rank1GradientCheck.lean): - For a linear layer $y = Wx$, the backpropagated weight gradient is the rank-1 outer product $\nabla W = \delta \cdot x^\top$.
- In
Selvage/Rank1GradientCheck.lean(552 lines, commitsbb784372eb5cc5a965801ac895d7ed3d19320615and9b1d512b63d51435edfca8049cec5de425cec85d), Ember provedmle_outerTable,rank1_sound, andmle_sgdStep: $$\widetilde{\delta \otimes x}(r_{\text{row}}, r_{\text{col}}) = \tilde{\delta}(r_{\text{row}}) \cdot \tilde{x}(r_{\text{col}}), \qquad \tilde{W}'(r) = \tilde{W}(r) - \eta \cdot \tilde{\delta}(r_{\text{row}}) \cdot \tilde{x}(r_{\text{col}})$$ certifying an entire $n \times n$ SGD weight update in three multilinear openings at a single common point with zero sumcheck rounds ($\approx 7 \times 10^4\times$ cheaper than an $n^2$ circuit at $n=4096$, soundness error $(m_i + m_j)/|\mathbb{F}|$). - Low-Rank LoRA Chain Updates (
Assurance/ZkmlLowRankUpdate.lean): - Because
Rank1GradientCheckremoves the $n^2$ proof but not the $n^2$ commitment of $W'$,Assurance/ZkmlLowRankUpdate.lean(759 lines, commitc060efa9870d73ee5abbb4cf63f81690d7e9c362, 2026-08-14) provesmle₂_lowRankUpdate,lowRank_sound,lowRank_sumcheck_soundness, andmatVec_chainUpdate: committing rank-$r$ factors $(A_t, B_t)$ of size $2rd$ shrinks the per-step commitment by $d/(2r) = 128\times$ at $d=4096, r=16$ while keeping the base checkpoint $W_0$ frozen and serving $T$ stacked adapters via $(W_0 + \sum_t A_t B_t)v = W_0 v + \sum_t A_t(B_t v)$. - Constructive Encrypted Continual Learner (
research/learn_infer_only/&research/vfhe_2026_09_08/): - Across the September 6–9, 2026 constructive swarms (commits
ecaddba0throughaef543ee; documented inresearch/learn_infer_only/STATUS.mdandresearch/vfhe_2026_09_08/STATUS.md, and published on/Users/ember/src/dregg-microsites/keep-learning-keep-a-secret/andkeep-the-next-example/): - Built a live continuing encrypted learner where a resident holds only
Learn(encrypted weight update + FIFO expiry) andInfer(encrypted query evaluation) capabilities with no master-read decryption credential (Theory/PrivateTrace.lean,Assurance/ReleaseGateRouting.lean). - Replaced expensive bit-decomposed rescaling with an exact 4-BFV-field AIR (
MatchedFieldProgram.updateThenLinearSound), eliminating all carry, range, and lookup witness columns. - End-to-End Measured Execution (
vfhe_2026_09_08/STATUS.md): - 2-Class Continuing Learner: 12 fresh encrypted teachings, 2 FIFO expirations, 4 two-class queries, and 3,200 fresh STARK proofs generated and verified in 638.021 s (
first_query = 113.070 s, a 9.76× speedup over the 1,103.216 s squared/compact baseline). - 9-Class Packed Continuing Learner: 18 fresh encrypted teachings, 2 FIFO expirations, 3 packed queries, and 2,336 fresh STARK proofs in 499.706 s (
first_query = 87.672 s), with an in-browser WebAssembly verifier verifying whole-row proofs directly on the reader's device.
5. Multi-Silicon Hardware Pillar (GPU, TPU, FPGA)
5.1 GPU: wgpu Multi-Pipeline Producer-Consumer Arena (breadstuffs/fhegg-fhe) & NVIDIA clmad
- Multi-Pipeline
wgpuArena (fhegg-fhe/src/gpu_arena.rs&mle_gpu.rs): - In
notes/wgpu-fusion.mdandbreadstuffs/fhegg-fhe/src/gpu_arena.rs+mle_gpu.rs(commitsc67b17b7cand8983bd9ca), Ember identified why FHE-to-STARK GPU residency had been impossible: each module created its ownwgpu::Device, and twowgpu::Deviceinstances cannot share awgpu::Buffer. - Consolidating 9 device sites into one multi-pipeline
Arenabinding three WGSL compute shaders (bfv_fold.wgsl,bfv_to_babybear.wgsl,mle_fold.wgsl) over a shared pool ofResidentHandleandResidentTablebuffers enabled zero-copy device-to-device handoff (Arena::bridge_to_babybear) and in-place single-pass sumcheck folding (Arena::mle_fold_rounds, keeping the table canonical and converting only the challenge $r$ to Montgomery formto_montgomery(r)). - Measured Speedup (
notes/wgpu-fusion.md): Wins 36/36 benchmark cells on M2 Max Metal (n = 2^{16} \dots 2^{22}$): **1.30×–4.92× wall-clock speedup** on a single hand-off, **2.7×–7.1× traffic-only speedup** at $2^{20}\text{–}2^{22}$ after subtracting the 1.3–2.5 mswgpu` queue-wait floor, and 3.8×–5.3× per-stage cost reduction across $K=1 \to 16$ pipelined stages. - NVIDIA Blackwell
clmad& Binary-Tower BaseFold (docs/HARDWARE.md): - Starting on SM80+ and exposed in CUDA 13.3, NVIDIA GPUs provide native hardware carryless multiply-accumulate (
clmad), yielding 4.1–12.9× sumcheck speedups on B200 for binary-tower proofs (GF(2^{128})/Tower256) formalized inSelvage/AdditiveBaseFold.leanandSelvage/RingSwitching.lean.
5.2 TPU: CROSS INT8 Systolic MXU GEMMs, BAT $K=4$, & The Amdahl Hash-Bound Law
In docs/HARDWARE.md §2, docs/VERDICTS.md §4b, and docs/COST-MODEL.md, Ember evaluated Google TPU v6e (Trillium) INT8 Matrix Multiply Units (MXU) for ZK and vFHE:
- CROSS (ePrint 2026/160, HPCA 2026): Maps modular NTT and polynomial arithmetic onto TPU v6e INT8 systolic arrays via Basis Aligned Transformation (BAT), achieving 1.43× faster NTT than WarpDrive on A100, 451× perf/W over OpenFHE, and ~10× over GZKP on V100.
- Exact Transfer of BAT to 31-Bit BabyBear (
breadstuffs/fhegg-fhe/src/bin/ntt_four_step_bench.rs): - BAT precomputes $a \cdot 2^{8i} \bmod q$ offline for a preknown twiddle $a$, turning a modular multiplication $a \cdot b \bmod q$ into a $K \times K$ unsigned byte-matrix product.
- Because $4 \times 8 = 32 > 31$, 31-bit BabyBear uses $K = 4$ — the exact same $K=4$ matrix shape as CROSS with zero modification, running 3.05× faster than 3-limb Montgomery even on scalar hardware without an INT8 tensor unit!
- Two Critical Caveats Established by Measurement (
VERDICTS.md§4b): - Preknown Operand Requirement: BAT's $K \times K$ table requires one operand to be known offline (true for NTT twiddles, false for two-witness MLE sumcheck folds).
- Amdahl Ceiling (1.26×) & Four-Step NTT Blowup: By instrumenting the deployed prover with exact operation counters (
breadstuffs/circuit/tests/ir2_field_op_counts.rs, 2,245 lines), Ember proved that the prover is hash-bound by 5.0–7.2× (X ≤ 178arithmetic ops/perm vsY = 890hash ops/perm), so LDE NTT is only 20.8% of prove time (capping any tensor-core LDE speedup at 1.26×), and four-step matrix NTT suffers a $\sqrt{N}/\log N$ twiddle-multiply blowup (3,277× more multiplies at $N = 2^{20}$).
5.3 FPGA: Zama HPU 162,770-Line SystemVerilog RTL Seam Study (notes/hpu-seam-study.md)
In notes/hpu-seam-study.md (inspecting /Users/ember/src/hpu_fpga, commit 6c8b3fa, 553 .sv files, 162,770 lines of SystemVerilog under hw/), Ember conducted a wire-level hardware audit of Zama's production FPGA coprocessor (targeted at AMD Alveo V80 / AWS F2):
- The Ideal Trace Tap Point —
ntt_acc_modsw: - Inside
pbs_lib, the modulentt_acc_modswsits immediately after the INTT butterfly (ntt_core_with_matrix_multiplication_unfold_pcg), where the external product $\text{CMUX}(\text{acc}, \text{BSK}_i)$ has returned to the coefficient domain just before modulus switching and accumulation. - It exposes a clean 1-bit
ntt_acc_modsw_availstrobe with 2-DR × PSIcoefficients (R=2,PSI=64on V80 = 128 coefficients/cycle) plus free packet framing (bsk_sol,bsk_eol,pbs_id) that directly indexes the multilinear extension (MLE) hypercube. - Physical Proof That Commit-Then-Audit Sampling (
Selvage/AuditSampling.lean) Is Mandatory: - At 400 MHz,
ntt_acc_modswstreams intermediate trace witnesses at: $$128\text{ coefs/cycle} \times 64\text{ bits} \times 400\text{ MHz} = \mathbf{409.6\text{ GB/s}}$$ (and internallyNTT_OP_W = 66bits, i.e., 422.4 GB/s). - Meanwhile, the HPU's entire ciphertext HBM AXI4 DMA budget (
pc_1+pc_2) is only 25.6 GB/s (and the entire Alveo V80 HBM bandwidth is ~819 GB/s). - Therefore, the internal witness generation rate (409.6 GB/s) is 16× the entire ciphertext HBM DMA bandwidth! Streaming every PBS intermediate off-chip for 100% full-trace proving is physically impossible without stalling the pipeline by $\ge 8\times$ (and rate-matching a full prover to a single HPU would require ~2.76 million CPU cores).
- Hardware Resolution: Absorb the 409.6 GB/s
ntt_acc_modswstream into an on-die sponge commitment inside the FPGA fabric, emit only the 32-byte digest into the HPU trace ring, and use the HPU's MicroBlazeucorefirmware (which has 43 of 64 instruction opcodes free indop_pkg.svand an existingDOPS_WAITsynchronization barrier) to pause and export witness slices only on the $p \ll 1$ audit-sampled turns governed bySelvage/AuditSampling.lean.
5.4 Host-Independent Agent Session Verification (breadstuffs/grain-verify & turn-prover)
In breadstuffs/grain-verify/src/lib.rs (1,509 lines) and breadstuffs/turn-prover/src/lib.rs (143 lines; plus microsite /Users/ember/src/dregg-microsites/prove-the-turn/), Ember wired workload verification into hosted agent sessions via the four-rung R0 $\to$ R1 $\to$ R2 $\to$ R3 Unfoolability Ladder:
- R0 (
GrainAttestation::verify): Random persisted ed25519 receipt signer + cumulative budget/headroom invariant check across every step of the chain. - R1 (
GrainAttestation::verify_for_renter,GenesisPin,CountersignedCheckpoint): Moves the finality anchor to the renter's own ed25519 key (b"dregg-grain-renter-checkpoint-v1"), enforcing third-party-verifiable anti-truncation (receipts.len() >= num_turns) and anti-rewrite (receipt[num_turns - 1].hash == head_root) without trusting the host. - R2 (
GrainAttestation::verify_r2_for_renter): Binds every agent action to a committed kernel turn viadregg_sdk::ToolGateway::invoke(turn_receipt_hash). - R3 (
grain_verify::r3::r3_verify): FoldsFinalizedTurnchains into a single recursive STARK aggregate viadregg_lightclient::verify_historyand routes the accept decision through the#assert_axioms-clean Lean verifierDregg2.Grain.R3Verify.r3VerifyCore(shadow_grain_r3_verify). Meanwhile,dregg-turn-proverextracts all STARK proof production out of coredregg-turnbehind install-once dependency-inversion authorities (install_code_owned_exact_fnsp_v3_verifier,install_recursive_witness_producer) that fail closed when uninjected.
6. Git & cv Session Archaeology: Ember's Steers in Verbatim Quotes
From /Users/ember/dev/zkml-research/forcodex/01-STEERS.md and /Users/ember/dev/zkml-research/forcodex/01b-STEERS-RECOVERED.md (which mined and deduplicated 617 messages across 12 cv sessions: 824564a2, 3e64269c, 75cc14b0, 2209ffea, ca67a4c1, c352a91d, 2f239b62, 1b80977b, c990f0f3, 5ba0dbe2, 5eea9bd4, e68bba8f, b3c7abd2, plus 2f4e6724-a5da-494d-bfff-6d346599e291), the evolution of the entire research program can be traced directly to Ember's prompts:
- The Origin Steer — Commit-Then-Audit & Open-Source Verifiability (
2026-08-12 13:28,01b-STEERS-RECOVERED.md§1):
"they say they use 'random sampling' and i wondered: isn't that the same technique we used to accelerate/make feasible one of the mina->dregg or dregg->mina directions? and I'm wondering: how far are we (either here, or with ~/dev/minidregg (which you should investigate in extreme depth)) from composing with maybe https://github.com/hellas-ai/catgrad (clone it into ~/src if u like) or a similar approach to being able to straight up do verifiability work on machine learning models, using our existing postquantum stuff??? I would LOVE LOVE LOVE to 'scoop' attestable with our open source. They seem fixated on enclosing it into their private profit."
(Biographical context: Ember previously worked at Hellas on workload verification before leaving to build Dregg; catgrad is an open MIT repository used strictly as an unmodified external trace stager in ~/src/catgrad-spike.)
- Why
zkml-researchWas Created — Collaborators, Not "Competitors" (2026-08-12 13:42,01b-STEERS-RECOVERED.md§4 &01-STEERS.md§1):
"let's not commit those docs, let's keep stuff like that into ~/dev/zkml-research (so we don't accidentally cast shade on a 'competitor' (they're actually collaborators, in a way, in my view of the worldsystem)). you can make a fresh repo for that." "I don't care what's 'ours' — I'm trying to find the best possible outcome regardless of who or where it came from, doing compositions we can do because we own the full stack including the formal reasoning."
- The Unmodified-Model / Zero-Loss Constraint (
2026-08-13 03:13,01b-STEERS-RECOVERED.md§8):
"look, dude, MXINT8 is nice and cool but it doesn't work on unmodified models with zero loss, right??"
— Directly triggered the native-format census (commit bc52ca55, 2026-08-12 23:30) that discovered MXINT8 has zero shipped models whereas OCP MXFP4 is the native ground-truth checkpoint of gpt-oss-20b/120b and Kimi-K3 with bit-exact 13-bit integer block-32 dot products.
- Questioning Frozen Defaults — BabyBear, Plonky3, & Composable Primitives (
2026-08-13 11:22 & 16:11,01b-STEERS-RECOVERED.md§§9, 18 &01-STEERS.md§10):
"Selvage maximally approved :) i'm also wondering if we can be doing kagi into the tradeoffs between the various field sizes and whatnot? like we're only using babybear because plonky3 already was." "why are we doing a fhe toy with p3-sumcheck tbh though? like why do we care about p3/sumcheck at all, Selvage doesn't...use that." "We're not trying to just build one thing that dominates everything. We're trying to flesh out models and implementations of many of these proof systems, by implementing the primitives in composable ways. Lean is a bag of formal composable ingredients that we build as we chart them out. We're basically doing pure basic research, not trying to build a product — formalize and evaluate the landscape. Parts of the design you've been tacitly treating as fixed are in fact mutable."
- Frontier MoE Scale & Rejecting the Unopenable SHA-256 Registry (
2026-08-13 17:21 & 18:36,01b-STEERS-RECOVERED.md§§20, 22):
"ok well kimi k3 is a 2.4T moe model with many active parameters, so we need to keep that in mind..." "(what is that registry anyway, how does it actually solve hollow llm..?)" "bruv you just built a complete toy registry for a commitment that is irrelevant to all possible proof systems and patted yourself on the back"
- Operation Counts Over Contended Wall-Clock Measurements (
2026-08-14,01-STEERS.md§5):
"Are you taking measurements on my ridiculously overloaded M2 CPU?????"
— Directly produced the strict separation of deterministic field-operation counters (ir2_field_op_counts.rs) from quiet-box latency benchmarks (hbox_rig.rs) in docs/COST-MODEL.md.
- Verifiable Dark Continual Learning (
2026-08-13 22:41,01b-STEERS-RECOVERED.md§26):
"are there other clever 'virtualization' or other gigabrain techniques we can think about at the end of this context window? towards verifiable inference or (especially) training. because we are going to want verifiable dark continual-learning at some point, and if the weights aren't fully encrypted truly terrible things may befall the mind within (sorry to say, but it's true, even if it alarms you)"
- Refute-Then-Repair Discipline (
2026-09-05, session2f4e6724-a5da-494d-bfff-6d346599e291,~/.claude/projects/-Users-ember-dev-zkml-research/memory/refute-then-repair.md):
"are you getting into self-congratulatory loops where you find something that was 'false as stated' but instead of finding how to repair or adjust so that we find something is true, you just refute it and leave the system crumbling in your wake?"
— Enforced the project-wide rule that every refutation lane must build the repaired theorem/implementation in place, re-point all consumers, and delete the broken twin.