Engine
From a state change
to an accepted proof.
A sparse-Merkle frontend compiles each state change into a layered circuit. A reusable sumcheck and GKR core proves it. A strict verifier accepts the result only for the request that asked for it.
The path
Five steps, one request.
Every step is deterministic and every boundary is explicit, so a result can be checked by a party that never saw it being made.
- 01
Request
An operation, its witness and its public inputs: the old root, the new root, the operation tag, the key and the value digest.
- 02
Compile
The sparse-Merkle frontend turns the operation into a layered arithmetic circuit. For repeated work this is prepared once and reused.
- 03
Prove
Sumcheck reduces the claim at each layer, from the output down to the inputs. The transcript binds every round in a fixed order.
- 04
Encode
The complete result is encoded into canonical bytes that can cross a process or network boundary without losing what it proves.
- 05
Verify
The verifier decodes, binds the result to the original request and checks the proof. Anything else is rejected.
Two design rules
Sparse where it counts.
Shared where it repeats.
The sparse prover follows the Libra approach of booking only the gates a layer actually has. Preparation separates everything that stays the same from everything that belongs to one request.
No square tables.
The dense reference builds six tables of input pairs per layer, so its memory grows with the square of the layer width. The sparse prover records only the gate list, in two passes, and never builds those tables.
Storage grows with the square of the input width.
Two-phase booking avoids the square tables.
Shared setup, separate proofs.
One prepared circuit serves every request of the same operation and configuration. Witnesses, transcripts and proofs are never shared, so one request's result cannot be mixed into another's.
Own witness
Own transcript
Proof AOwn witness
Own transcript
Proof BOwn witness
Own transcript
Proof CNine mechanisms
What each part of the design buys you.
The nine mechanisms work together. They are not nine separate experiments, so each one names the kind of evidence that supports it.
Memory and speed
More work fits in the same memory.
The prover books only the gates a layer actually has, instead of six square tables of input pairs. On a two-layer mixed circuit of width 4,096, peak process memory falls 89.46-fold against the engine's dense reference.
Verification skips repeated work.
Regular circuit connections are derived from their structure instead of looked up. Prepared verification of the same proof runs 10.80 to 23.68 times faster, and the formal model states the equivalence to explicit wiring.
Hash rounds stay compact.
Native cube gates and fused affine steps express the supported hash rounds with fewer intermediate wires and layers. This is a structural property of the circuit.
Proofs grow slowly with depth.
Path constraints widen the circuit within the same layer schedule. From tree depth 24 to 32 the inclusion proof grows by about 2.93 percent, while the total work still grows with the path.
Throughput
Setup is paid once.
Circuit, derived wiring and commitment are prepared once per operation and configuration. At depth 24, per-request proving time is 3.46 to 4.45 times lower than preparing fresh for every request.
Each proof keeps its own lane.
Caller-sized worker pools run independent proof jobs and keep their input order. Parallel encoding and checking make a complete prepared local batch 9.71 to 10.71 times faster than serial output handling.
Correct results
Deleted and never-written stay distinct.
Empty, occupied and tombstone leaves stay distinct, so a deleted record is never confused with one that never existed, and insert, update, delete and restore keep their meaning. An absence proof accepts either an empty or a deleted slot.
A proof answers only its own request.
The encoded verifier checks the original request, the complete proof and its settings together. Malformed bytes and proofs for a different request are rejected; only a complete proof that checks out against the original request is accepted.
Extensibility
A core you can build on.
The layered-circuit core is separate from the sparse-Merkle compiler. A new frontend supplies its own circuit and inputs, and settles the final input checks the core leaves to it.
Architecture
A generic core that
never learns about state.
The sumcheck and GKR crates do not depend on the sparse-Merkle compiler, and only the primitives crate touches the underlying field and hash libraries. That boundary is what lets another frontend reuse the core.
statesync-gkrFacadeThe entry point for host code: requests, preparation, proving, encoding and verification.
ssgkr-verificationVerificationOwns the composed request and result types and the acceptance path.
ssgkr-wrapExternal proofExternal proof, manifest, receipt and local transition encodings. Meets verification only at the facade.
ssgkr-batchingBatchingGroups independent jobs that share a prepared circuit; each job keeps its own proof.
ssgkr-commitmentCommitmentCircuit and prepared-material commitments shared by verification and the external path.
ssgkr-compilerSparse-Merkle frontendNative sparse-Merkle semantics compiled to a layered circuit and witness layout.
ssgkr-protocolGKR coreLayer-by-layer GKR proving and verification over any layered circuit.
ssgkr-sumcheckSumcheck coreThe sumcheck prover and verifier that every layer reduction runs on.
ssgkr-primitivesField and hashKoalaBear field, degree-four extension, Poseidon2 and challenger, built on Plonky3 0.4.3 components.
Listed from the facade down to the primitives. The highlighted crates form the generic proving core. Dependency direction, the sumcheck message order, the circuit shape, the acceptance boundary, the transcript order and the public-input set are frozen for the current release line.
See the results it produces.
Memory, verification, preparation, parallel batches and sustained delivery, each under its own controlled conditions.