~72k lines of pure-std Rust. 33 crates. 1,313 tests. Zero external dependencies.
LZX is a from-scratch, production-oriented implementation of the modern lattice-based zero-knowledge proof stack: it implements seventeen research papers end-to-end (prover + verifier + exact algebraic identity tests), ports the labinius lattice PCS and the LaBRADOR proof system as native Rust, and assembles them into a proving zkVM for RV64IMAC programs with a bounded canonical proof envelope.
Repo navigation: IMPLEMENTATION_LOG.md (the timestamped
build history) · IMPLEMENTATION_CHECKLIST.md (what is
implemented / partial / open) · NEXT_STEPS.md (the research backlog
- the honest ledger) ·
docs/PAPERS_MAP.md(the papers' inner connections) ·docs/INDEX.md(the search index) ·docs/analysis/(the formal analyses: the multi-stage LaBRADOR extraction, the D4 binding closure).
Two recent papers round out the prover stack: the monomial-basis
(projective) sum-check (ePrint 2026/762 — the {0,∞} interpolating set,
subtraction-free binding, the (e, e·r) table recurrences, claim-preserving
batched dummy rounds, upper-limb Montgomery challenges over 256-bit fields)
and proving CPU executions in small space (ePrint 2025/611 — streaming
witness oracles with checkpointed regeneration, the O(n)-space sum-check
prover, the hybrid space/time switch, the prefix-suffix inner product
protocol, streaming grand products, √N-matrix commitments, and the
client-side facade): proving is streaming and client-side, with
round messages bit-identical to the in-memory engine.
The lookup layer now runs over the CRT-split lattice ring itself
(lattice-lookup-ring, ePrint 2026/471): Ring-Plookup and Ring-LogUp
with the Section-4 attack demonstrations, the full Appendix-B PIOP
toolkit, the Section-6 RAM batch verification, and the three
follow-ups — the Greyhound-style compile onto the Ajtai/carrier stack
(digit windows + the tensor binding pass), the Fp256 port of the
binding pass on the CIOS Montgomery grid, and the zkVM's v3 pipeline
whose memory arguments replace the Twist & Shout layer with the
ring-lookup composition. The LatticeFold+ norm-control layer also
gained the ℓ2-norm checks of ePrint 2026/721 (the JL projection
RoK + the exact-shortening RoK + the no-drift norm ledger).
The labinius PCS path runs upstream's AVX-512 kernel designs natively (runtime-detected,
pure std intrinsics, exact scalar fallbacks): vertical batch-of-32 binary NTT kernels with
vpermb lookup tables and lazy reduction, the vpmaddwd raw-accumulation commitment MAC with
compile-time fold-back periods, PCLMULQDQ binary-field arithmetic — all verified bit-exact
against the scalar reference. See PERFORMANCE.md for the full efficiency analysis:
the reference round runs 49x end-to-end (3885 -> 79 ms) with the proof 1.63x smaller
(915 -> 560 KB), plus vectorized Goldilocks sumcheck and LaBRADOR ring arithmetic.
Wave 6 (shared substrate + soundness-critical fixes) is in: paper-calibrated short
ring-element challenge distributions with certified operator-norm bounds (the family-wide
challenge-space fix), hard norm wraparound gates on every folding module, the Ajtai
cached-NTT fast path (4.2x on every commit/verify), the committed Quasar lookup protocol
(closing the verifier-binds-nothing hole), F_{q²} extension fields, the ~2^50
quadratic-slot incomplete NTT at RoKoko's own modulus, zero-skipping pay-per-bit commitment
inputs, and a zero-dependency SIS security estimator (ADPS16/BDGL16/LGSA). See
NEXT_STEPS.md for the per-paper research backlog driving Waves 6-8.
prove_program(RV64IMAC bytecode) -> Proof envelope -> verify_program(envelope) == Ok(())
| # | Paper | Crate | What is implemented |
| 1 |-------|-------|---------------------|
| 2 | ProtogaLattice (constant-round folding) | lattice-folding | Cross-term extraction via finite-difference Newton inversion (diagonal snapshots); exact fold identity for degree-2 and degree-3 relations |
| 3 | Akita (lattice PCS) | lattice-akita | Packed commitments, sumcheck evaluation proofs with norm-checked openings, grouped openings, schedule catalog + security profiles |
| 4 | Cyclo (lattice PCS) | lattice-folding | Extension commitment (iterative-borrow chunking, exact recomposition), partial range checks, accumulator with additive norm growth + refresh; the §7 R1CS bridge + the compact-PCS terminal (the witness-free decider) |
| 5 | HyperWolf (lattice PCS) | lattice-pcs | Standard-soundness PCS backend + the PcsBackend trait boundary |
| 6 | LatticeFold+ (folding + Ajtai commitments) | lattice-folding | Algebraic range proof (eq-multiplied booleanity sumcheck + point reconstruction), double-commitment folding, tensor rings |
| 7 | PikkuFold (folding) | lattice-folding | Layered biased-ternary random projections with certified JL norm bounds, no in-fold commitments, linear-relation binding |
| 8 | Quasar (lookup arguments) | lattice-lookup | Committed grand-product lookup (Q1: Ajtai commitments to T/R/Q, τ from commitments, counting-map difference, forged-triple rejection) + partial-evaluation multi-instance accumulation |
| 9 | RoKoko (lattice PCS) | lattice-rokoko | Coarse/fine two-stage committed refinement with ternary projections; incomplete-NTT completion |
| 10 | SALSA (zk sumcheck) | lattice-salsa | Norm sumcheck, LDE tensor relation, structured (negacyclic) matrix checks, zk sumcheck with statement-derived masks; D4 — the Akita/zkVM response-layer swap (the byte-packed SALSAA chain in the v2 pipeline: polylog, zero disclosure) |
| 11 | Symphony (folding + SNARK) | lattice-folding | High-arity (mu-ary) one-shot folding with full subset cross-term bookkeeping; exact mu-ary identity verified |
| 12 | Twist & Shout (small-space zkVM) | lattice-memory, lattice-vm, lattice-zkvm | Twist (read/write timeline) and Shout (read-only table) checks with grand-product fingerprint identities; canonical RV64IMAC decoder + deterministic executor + subword-correct sparse memory + LR/SC & AMO atomics; end-to-end prove/verify |
| 13 | ZK-PCD from Accumulation Schemes (ePrint 2026/289) | lattice-pcd | The special-sound framework (R1CS/CCS/permutation instances, homogeneous algebraic maps), the CFS17/XZZ+19 zero-knowledge sum-check with the KS24 point-update, the zk-Protogalaxy accumulation scheme (masking vector + eq-interpolated F(X) + the error commitment E + decider), the FS NARK, and the two-circuit ZK-PCD construction over vector-Pedersen BN254 commitments |
| 14 | PCD via Holography Accumulation (ePrint 2026/538) | lattice-holo (+ pc_short) | The GBF relation family with both univariate and multivariate representations, Π_GBF1 (Marlin-style) + Π_GBF2 (Spartan-style) with the h₁/h₂ domain sum-check, Π_batchM, Π_Collapse, Barebones (SuperMarlin/SuperSpartan recovery), Π_Fold (the holography accumulation), the non-uniform decider, and the PCD construction; + the deviation-ledger follow-ups: the PQ commitment route (Ajtai-over-F_r with digit layers, the E-fold closure, the norm ledger, the MSIS double-open kernel) and the accumulatable short-opening PC (the Accordion module-sumcheck over F_r: O(log n) openings, γ-accumulation, the amortized decider) |
| 15 | Accordion — Revisiting the IPA-sumcheck connection (ePrint 2025/1325) | lattice-accordion | The lattice instantiation of the whole paper: the module-valued sum-check (Lemma 3.1) over (R_q)^rows at q = 2^50−2687, the ml-PCS with accumulation (Def 4.3) — com through 16-bit digit layers on the layered cube, reduce (the deferred (V−baP')/a terminal), accumulate (the γ-fold with e(X) = Σγⁱ eq(X,rᵢ)), the amortized decide (Ĝ(r), once per batch — the FRI decider's lattice obstruction documented), and the executable two-α extraction harness (Lemma 5.2) with the shortness verdicts and the [G\|P] MSIS-kernel outcomes |
| 16 | CauchyFold — Residue-Optimal High-Arity Lattice Folding (ePrint 2026/2011) | lattice-cauchyfold | The full paper at the scaled profile: the Cauchy carrier algebra (Prop 4.4 identity, Lemma 4.5 discrepancy, the A.3 fast construction — differential-tested), the executable boundary-width theory (Thm 4.1 / Lemma 4.2 / Cor 4.3 pinned by exact K-linear algebra), the node protocol with the 19 root objects (the field-check sum-check, the level-2 ΓW=Y system with ring-structured commitment rows, the R16 fingerprint), the §5.5 linear chain (projection with retries, the symmetric h-before-challenge, the D46 certified challenges, the response identities), the §5.6 terminal codec, and the §6 extraction (Lemma 6.2 compare-before-clearing, the coordinate replay, the loss accounting) |
| 17 | LatticeBlindFold — A Lattice-Based Analogue of NovaBlindFold (ePrint 2026/1857) | lattice-blindfold | The blinding stack for SuperNeo, complete: the Libra-style masked Sum-Check over K = F_{q^2} (the mask never opened — the final check lives at the ABDLOP-commitment level), the componentwise ABDLOP commit-and-prove with the rank-doubling ψ embedding, the full PoK family (Π_many^(1)/(2)/(ct)/Π_anc with Rej1/Rej2 and the (g₀,g₁,g₂) quadratic garbage triple), Protocols 6/7/8 (all 18 R1CS-reduction steps, the Wmax-capped RLC mask loop with the Cy,0 tuple, the fresh-salt decomposition), the samplers, Π_LBF + the accumulator-free Π°_LBF + the folding blueprint, the blinded layout with Lemma 3.3 hiding, and the Table-2 parameter sets with the consolidated error budget (Remark 4.19's ≈116/121-bit verdicts, Remark 4.23's 2^−112 blinding cap) |
Plus two ports of external systems:
| System | Crate | Notes |
|---|---|---|
labinius PCS (osdnk/labinius crates/pcs) |
lattice-labinius |
Full PCS: const-evaluated ring tables (conductor-1944 split + conductor-972 quadratic), exact mixed-radix scalar NTT, GF(2^162) with carry-less multiplication, Ajtai commitment key (7 moduli), SHAKE-256 Fiat-Shamir, weight-28 bounded challenges, slot-domain fold, eval layer, bit-dropped opening (Garner digits + residual norm check), Clear + BitDropped modes, reference round |
| LaBRADOR (lattice-dogs vendored C) | lattice-labrador |
Native pure-std Rust: Z_Q[X]/(X^64+1), Q=2^48-59, exact i64/i128 arithmetic, SIS-rule parameters, inner/outer commitments with digit decomposition, JL projection with rejection, amortization, full verify; simple-statement API with content digests |
| LaBRADOR (ePrint 2022/1341) + Greyhound (ePrint 2024/1293) | lattice-greyhound |
The paper-faithful engine at the papers' q=2^32-99: the principal relation F/F', Figure 2/3 protocol (LIFTS aggregation, g/h garbage, amortization), §5.3 recursion + §5.6 tail (2r-1 interleaved garbage), §6 R1CS reductions (binary Figure 4 + mod-2^64+1 Figure 5 with NAF encodings), the Greyhound PCS (Setup/Commit/Open/Eval with the σ^{-1} Z_q translation, Figure 1 three-round protocol, Figure 2 batching, Lemma 3.2 CWSS extractor, §4.5 hiding/HVZK), Table 4 parameters + the 53KB accounting — 57 lib tests + the integration/tamper suites |
lattice-core Goldilocks field (carry-compensated), Keccak-f1600/SHA3/SHAKE,
Fiat-Shamir transcript, dense MLEs, gadget decomposition,
challenge sets (sparse ternary / uniform / small interval),
short ring-element challenges with certified Γ_C bounds (W6),
symbolic NormBudget hard gates (W6), F_{p²} extension field (W6)
lattice-ring Negacyclic NTT (CT/GS, psi-scaling, Barrett-reduced hot path),
R_q arithmetic, incomplete NTT + completion, 3x22-bit split
packing, CRT carriers, R_q[Y]/(Y²+1) extension ring (W6),
Modulus50 quadratic-slot incomplete NTT (W6)
lattice-commitment Ajtai Module-SIS commitments (seed-derived A, cached-NTT fast
path, zero-skipping MAC, statement-absorption API),
ABDLOP-style linear proofs, digit-decomposed norm proofs,
bit-packed one-hot column packing (pay-per-bit)
lattice-sumcheck Generic virtual-polynomial sumcheck, Spartan-style zerocheck,
batched claims
lattice-relations CCS with sparse matrices + RLC utilities
lattice-folding ProtogaLattice, LatticeFold+, Cyclo, PikkuFold, Symphony, SuperNeo
(all with hard norm gates + public-coin FS hygiene)
lattice-lookup Quasar lookups (committed Q1 protocol + accumulation)
lattice-salsa SALSA norm/LDE/structured-matrix/zk sumchecks
lattice-widthfold the shared width-fold core (the recursive staging, the ring-functional fold)
lattice-rokoko RoKoko two-stage refinement
lattice-akita Akita PCS (full)
lattice-pcs PcsBackend trait + HyperWolf backend
lattice-embeddings Hachi-style slot embeddings + trace functionals
lattice-labinius labinius PCS port
lattice-labrador LaBRADOR native Rust port
lattice-greyhound LaBRADOR (2022/1341) + Greyhound (2024/1293) — the paper-faithful engine, the PCS, the 53KB accounting
lattice-sis-estimator Offline SIS security estimator: ADPS16/BDGL16 costs, LGSA
simulator, infinity + Euclidean attack paths (W6)
lattice-vm RV64IMAC decoder (all base+M+A incl. compressed), executor,
trace rows, subword-correct sparse memory, LR/SC + AMO
lattice-memory Twist & Shout grand-product memory checks
lattice-zkvm End-to-end prove_program / verify_program, canonical envelope
lattice-zk Zero-knowledge layer: secret entropy, HVZK simulators,
ABDLOP ZkLinearProof, Libra-style blinded zk-sumcheck
(chi-square KATs)
lattice-qrom QROM accountability: query ledger, attestations,
production domain registry, composition review
lattice-bench Pure-std reproducible benchmark matrix (35 stages + sizes)
- 1,313 tests, 0 failures, 0 clippy warnings — every fold identity, PCS round, and VM conformance class is verified exactly (algebraic identities, not statistical approximations); the full workspace is now clippy-clean on ALL targets and rustfmt-normalized, with CI running both profiles (debug = overflow checks ON) plus the evidence examples.
- Differential ISA conformance — a second, independent byte-level RV64IMAC interpreter
(
lattice-vm/reference.rs) is compared against the traced executor over 131 randomized programs; golden vectors cover every instruction class. - Zero-knowledge with machine-checked simulators — HVZK simulator + chi-square KAT (alpha = 0.001) for ABDLOP linear proofs; distributional simulator for blinded sumcheck.
- QROM accountability — query ledgers with worst-case rejection amplification,
digest-bound attestations, and a composition-review protocol as the only granting path
for the
QromFiatShamircapability. - Envelope hardening — total-bytes cap enforced before allocation; 4000-mutation no-panic fuzz corpus; strict version/caps/duplicate/trailing-byte rejection.
- KAT manifest — 29 digest-pinned known-answer vectors (field / transcript / NTT / packing / commitment / zk / mle).
- Soundness-critical hard gates (Wave 6) — norm wraparound gates
β < min(q/2, β*)on every folding module (wraparound mod q silently destroys SIS binding; folds refuse instead); paper-calibrated ring-challenge distributions with certified operator norms; the committed Quasar lookup path (statement-bound τ, SIS-bound openings, counting-map multiset verification); a SIS security estimator pricing the toy-parameter regime honestly (seelattice-sis-estimatorandAUDIT_CHECKLIST.md).
See SECURITY.md (capability statement, threat model, four fixed-vulnerability
post-mortems) and AUDIT_CHECKLIST.md (G1-G8 evidence map).
cargo test --workspace # 1,313 tests (debug = overflow checks ON)
cargo clippy --workspace --all-targets -- -D warnings # clean
cargo run --release -p lattice-bench --bin lattice-bench # 35-stage benchmark matrix
cargo run --release -p lattice-widthfold --example extraction_table # the extraction ledgers
cargo run --release -p lattice-akita --example salsa_bound_size # the D4 closure/split evidence
cargo run --release -p lattice-labinius --example round_bench # labinius reference round
cargo run --release -p lattice-labinius --example backend_bench # scalar vs AVX-512 backends
cargo run --release -p lattice-labrador --example cmod_bench # LaBRADOR reduction/products
cargo run --release -p lattice-greyhound --example greyhound_bench # LaBRADOR+Greyhound: the PCS pipeline, the 2^26-scale sub-proof, the 53KB accounting (GREYHOUND_230=1 for the 2^30 statement)No external dependencies; builds with stable Rust (1.75+). Benchmarks are pure-std
and reproducible (median-of-runs timing harness). The AVX-512 / PCLMULQDQ backends are
runtime-detected (is_x86_feature_detected!) with the exact scalar reference paths as
fallback — the same binary runs unchanged on machines without the features.
Reference-round of the labinius PCS at sizem (2^18 GF(2^162) elements, 128 columns,
3889+2917), pure-std Rust on 2 cores — scalar reference → AVX-512 backend → full
upstream-parity wave (generic-input transforms, vertical fold, slot-table commitment fold,
rANS-coded opening):
| Stage | scalar | AVX-512 backend | parity wave | total speedup |
|---|---|---|---|---|
| commit | 3134 ms | 84 ms | 46 ms | 68x |
| evaluate | 327 ms | 9.4 ms | 8.8 ms | 37x |
| fold | 332 ms | 48 ms | 7.2 ms | 46x |
| challenge | 12 ms | 12.6 ms | 12.5 ms | — (hash-bound) |
| verify | 78 ms | 67 ms | 2.8 ms | 28x |
| total round | 3885 ms | 222 ms | 79 ms | 49x |
| proof size | 915 KB | 915 KB | 560 KB | 1.63x |
Beyond the PCS round: sumcheck prove 2.9x (Goldilocks AVX-512 field_simd kernels +
vectorized hot loops, digests bit-identical), LaBRADOR ring ops 2.2–2.4x (the exact
split-2^24 vectorized negacyclic convolution). Kernel-level (batch of 32 ring elements):
forward NTT 270x, commitment MAC + finish 436x, carry-less multiply 66x
(PCLMULQDQ). Full analysis, technique map and the executed roadmap: PERFORMANCE.md.
This is research-grade code implementing preprint and conference protocols. Parameter
sets are illustrative and must be reviewed before production use (see
AUDIT_CHECKLIST.md, external items). Fiat-Shamir is ROM-shaped with QROM composition
reviews recorded in lattice-qrom; the ZK capability is granted only behind
machine-checked simulators. Fixed vulnerabilities and their post-mortems are documented
in SECURITY.md.
MIT.
The soundness/size frontier's three landings: (1) the recursive
width-collapse staging (lattice-widthfold — the extracted shared
fold core + chain.rs): the Sound profile's coverage extends from
n̄ ≤ 16 to the benchmark streams through log-stages of
estimator-gated rows (every stage ≥ 128 bits + the grinding
allowance; the measured boundary ships as --example chain_coverage); the Sound memory argument lands at 55.2 KB at
the test scale. (2) SALSA D4 — the Akita/zkVM response-layer
swap: the v2 pipeline's grouped openings run the byte-packed SALSAA
chain (the ψ-functional carrier with verifier-computed weights
replaces the transmitted LDE base) — 640–928 B responses, zero
witness disclosure, 61–671× vs the Clear mode. (3) the Cyclo §7
bridge's compact-PCS terminal (cyclo_terminal.rs): the decider
decides the ride-the-fold claims without the opened witness (the
ring-functional width fold carrying (D1)/(D2)/(D3)).
The three honest-ledger follow-ups, all closed the same day: the
multi-stage LaBRADOR extraction ledger (lattice-widthfold:: extraction — the degree-law unwind as five machine-checked laws,
ENFORCED in the chain gate; docs/analysis/MULTISTAGE_EXTRACTION.md);
the D4 binding closure (lattice-akita::salsa_binding — the
byte-witness↔commitment authenticated opening via the width-collapse
chain, composed into the v2 pipeline as Stage5Mode::Bound;
docs/analysis/D4_BINDING_CLOSURE.md); the r-column capacity
split (byte_capacity = the exact Lemma-4 cap of 2,048
values/commitment + the μ-weighted split beyond it — BENCHMARKS
§2l). Workspace 1,237 tests green.
Protocol completion landed: ProtogaLattice PGL-Fold/PGL-Boot
(crates/lattice-folding/src/pgl.rs), SALSAA D1+D2 + the A2–A5
stack (crates/lattice-salsa/src/{ring_sc,salsaa,air}.rs: Π_norm+,
Π_bin, the staircase RoK, the VDF binary staircase, committed-AIR +
folding), the full HyperWolf Protocols 1/2/3
(crates/lattice-pcs/src/hyperwolf.rs — ring mapping + balanced
gadget + leveled commitment, the guarded recursive evaluation, k-round
folding, the certified challenge space, own u64 ring at q ≡ 5 mod 8),
the RoKoko committed-refinement core
(crates/lattice-rokoko/src/{com,protocol}.rs — recursive COM Fig 1,
Ξ^lin_COM, Π^fold-split, sumcheckify, Π^lin, the round driver), the
labinius wire/ + Recursive layers, Serval (the slack-free
split-and-fold IPA, crates/lattice-labrador/src/serval.rs), and the
Hachi ring-switch (crates/lattice-embeddings/src/ring_switch.rs)
— all ported from the lattice-zk-lab reference implementation to this
workspace's pure-std conventions. Full part-by-part paper coverage —
implemented / partial / unimplemented — lives in docs/:
start at docs/ARCHITECTURE.md and
docs/papers/README.md.
Testing: cargo test --workspace (1136 tests at this commit);
cargo clippy --workspace clean. Benchmarks: cargo run --release -p lattice-bench --bin bench (26 stages, reproducible matrix) — see
PERFORMANCE.md for the methodology.