Zero-Knowledge State Lineage: Building ZK-ORIGIN from Scratch

How I Built a Recursive Proof System to Solve a $2 Billion Problem

I spent six weeks building something that didn’t exist. Not because I needed it for a job, but because I kept seeing the same exploit pattern over and over again, and nobody seemed to be solving the root cause.

This is the story of ZK-ORIGIN, a zero-knowledge proof system that tracks where blockchain state actually comes from. Not just whether state is valid, but whether it’s legitimate.

Let me explain why that distinction matters.

The Exploit That Started Everything

Last year, I was reading through the Ronin bridge postmortem. $625 million gone. The technical details were straightforward enough — attackers compromised validator keys and approved fraudulent withdrawals.

But one line stuck with me: “All transactions were valid according to protocol rules.”

Valid. The withdrawals were mathematically valid. The signatures checked out. The state transitions followed every rule in the smart contract. From the protocol’s perspective, nothing was wrong.

Except everything was wrong.

The validators who signed those transactions weren’t supposed to sign them. The authorization came from compromised keys, not from the actual validator set operating under normal conditions. The state was valid, but its origin was illegitimate.

I started looking at other exploits. Wormhole, $320 million. Nomad, $190 million. Over and over, the same pattern. Valid state transitions with illegitimate origins.

Current zero-knowledge systems can prove computation is correct. They can prove state transitions follow the rules. What they can’t prove is who authorized the transition and whether that authorization was proper.

That’s the gap I wanted to close.

What I Actually Built

ZK-ORIGIN tracks state lineage. Every state in the system carries a cryptographic commitment to its entire history — not just what the state is, but how it came to be.

Think of it like a chain of custody for data. When you receive evidence in a legal case, you don’t just care that the evidence exists. You care that it was collected properly, stored properly, and handled by authorized people at every step. The provenance matters.

The system works through origin classes. Every state transition gets tagged with who authorized it:

• User: Normal transaction from a regular user
• Admin: Privileged operation requiring multisig
• Bridge: Cross-chain import with attestation
• Governance: DAO-approved action with vote proof

Each origin class has rules about what it can create. Users can only create user-originated state. Admins can create user or admin state. Bridges can only create user state (they can import assets, but those assets become regular user assets).

These rules are encoded in a policy, and the policy is enforced cryptographically. You can’t fake an origin class. You can’t bypass the transition rules. Every state proves it came from an unbroken chain of legitimate origins back to genesis.

The clever part is making this efficient. A state might have millions of transitions in its history. Proving the entire lineage naively would require millions of proofs. That’s not practical.

So I used recursive proofs. Each step folds into the previous proof, producing a constant-size proof regardless of history length. Ten transitions or ten million transitions, the proof is the same size.

The Hard Parts Nobody Talks About

Building ZK circuits is humbling. I’ve written a lot of code over the years, but nothing prepared me for debugging constraints.

When a normal program fails, you get an error message. Maybe a stack trace. Something that points you toward the problem.

When a ZK circuit fails, you get “constraint not satisfied.” That’s it. The constraint could be anywhere in thousands of lines of circuit code. The bug could be a mismatched field type, a wrong index, an off-by-one error in a loop. You have no idea.

I spent four hours once tracking down a bug that turned out to be a single character. I was using Fr when I should have been using F. Both are valid field types. The code compiled fine. The circuit just didn't work.

The debugging process is binary search. Comment out half the circuit. Does it work? Yes? The bug is in the other half. No? The bug is in this half. Repeat until you find it.

I started writing assertions compulsively. Check every intermediate value. Print everything. Trust nothing.

Why I Chose Nova

There are several ways to build recursive proofs. The traditional approach is proof composition — you verify a SNARK inside another SNARK. The problem is that SNARK verifiers are expensive. About 40,000 constraints just to verify a single proof. Each layer of recursion adds this overhead.

Nova uses a different approach called folding. Instead of verifying the previous proof, you fold it into the current proof. Two proof instances become one combined instance. If the combined instance is valid, both originals were valid.

Folding costs about 10,000 constraints. That’s four times cheaper than verification.

The tradeoff is complexity. Nova requires a cycle of curves — two elliptic curves where each curve’s scalar field equals the other’s base field. The implementation juggles two circuits running on different curves, accumulating proofs together.

I won’t pretend I understood it immediately. I read the Nova paper three times. I traced through the nova-snark crate line by line. I drew diagrams. Eventually it clicked, but it took a week of focused study before I felt confident implementing.

The Architecture That Emerged

The system has three layers.

The bottom layer is a Circom circuit that defines a single step. Given a previous state and a transition, verify the policy allows this transition and compute the new lineage commitment. About 1,400 constraints for the simplified version, closer to 3,000 for the full version with Merkle proofs and counter verification.

The middle layer is a Rust prover using Nova. It takes the step circuit and wraps it in the recursive folding machinery. Each transition extends the proof. At the end, you compress the accumulated proof into a constant-size output.

The top layer is Solidity contracts. A Groth16 verifier (auto-generated from the circuit) and a LineageVerifier contract that checks proofs and maintains on-chain state.

I built two modes for the prover. A fast commitment mode that uses hash chains instead of real proofs, and a real Nova mode that generates actual zero-knowledge proofs. The commitment mode is for development — you can iterate quickly without waiting for proof generation. The Nova mode is for production.

This dual-mode architecture turned out to be one of the best decisions I made. Debugging is painful enough without waiting 30 seconds for every test.

Numbers That Surprised Me

My estimates going in were based on reading papers and other implementations. I expected Nova setup to take 30–120 seconds. It took 1.4 seconds. I expected per-step proving to take 500–2000 milliseconds. It took 60–140 milliseconds.

The proof size surprised me the other direction. I expected about 300 bytes. I got 10 kilobytes. The difference is serialization overhead — I’m including metadata that wouldn’t be strictly necessary. Production optimization would bring it down.

The constraint counts were lower than expected too. I had budgeted for 13,000 constraints per step including Nova overhead. The actual count was about 10,000 for the primary circuit and 10,000 for the secondary. Within the same ballpark, but different distribution than I predicted.

Estimation is hard. Real implementation always surprises you. I’m glad I left buffer time in my schedule.

What Policy Enforcement Actually Looks Like

The policy is a Merkle tree of allowed transitions. Each leaf is a hash of (from_origin, to_origin). To prove a transition is allowed, you provide a Merkle proof that the leaf exists in the tree.

This means policy updates don’t require changing the circuit. You just build a new tree with different allowed transitions and use the new root. The circuit doesn’t care what the policy is, only that you can prove membership.

Rate limiting works through epoch counters. Each origin class has a maximum number of transitions per epoch. The prover tracks counters and commits to them cryptographically. If you try to exceed a rate limit, the proof won’t generate.

I tested this by setting a low admin limit and trying to exceed it. The system rejected the transition before even attempting to prove — fail fast, don’t waste computation on something that won’t work.

What I’d Do Differently

If I started over, I’d spend more time on test infrastructure before writing any circuit code. The debugging would have been easier with better tooling.

I’d also be more careful about curve compatibility from the start. I built my Circom circuits on BN254 because that’s what Ethereum uses. Then I built my Nova prover on Pallas/Vesta because that’s what nova-snark uses best. The hash outputs don’t match between curves because the field arithmetic is different.

For the MVP this is fine — they’re separate systems demonstrating the same concept. For production, you’d want everything on compatible curves. Either commit to Pallas/Vesta and build a custom on-chain verifier, or do the extra work to get Nova running on BN254/Grumpkin.

I’d also think harder about the on-chain verification story earlier. Nova’s compressed proofs use Spartan, which doesn’t have a standard Solidity verifier. I ended up using Groth16 for the on-chain piece, which works but adds complexity.

Why This Matters Beyond the Code

The bridge exploits keep happening. While I was building this, there were three more incidents totaling over $100 million. The root cause is always the same — valid state from illegitimate origins.

ZK-ORIGIN doesn’t solve everything. It’s not a magic security button. But it provides a tool that didn’t exist before. If you can prove where your state came from, you can detect when something goes wrong. You can build systems that check provenance, not just validity.

The lineage proof is also useful for compliance. Regulators often ask “where did this asset come from?” Currently that requires forensic analysis of transaction history. With lineage proofs, the answer is cryptographic. The proof either verifies or it doesn’t.

I’m not claiming this will prevent all exploits or satisfy all regulators. I’m saying it’s a piece of infrastructure that should exist and didn’t. Now it does.

The Learning That Mattered Most

I went into this project knowing ZK theory. I came out understanding ZK practice. Those are very different things.

Theory tells you that Poseidon hashes are efficient in circuits. Practice teaches you that the efficiency depends on parameter selection, that different implementations use different constants, that verifying your circuit hash matches your native hash requires explicit testing.

Theory tells you that recursive proofs enable constant-size history verification. Practice teaches you that memory grows with each fold, that you need checkpointing strategies for long sequences, that the “constant size” proof still has serialization overhead.

Theory tells you what’s possible. Practice teaches you what’s hard.

I also learned that building in public has unexpected benefits. Posting progress updates forced me to actually understand what I was doing well enough to explain it. Several times I started writing a post, realized I couldn’t explain something clearly, and went back to study more before continuing. The writing was a forcing function for understanding.

Where This Goes Next

The codebase is on GitHub. It’s not production-ready — there are optimizations needed, edge cases to handle, documentation to write. But it works. You can run the demo and see proofs generated and verified.

I’m looking at a few directions for future work. Parallel proving would improve throughput for high-volume applications. Proof aggregation would let multiple lineages be verified together. Cross-chain lineage tracking would extend the concept beyond single-chain state.

But honestly, the main thing I want is for someone to use this. Not necessarily my code — the implementation is what it is — but the concept. State lineage should be something the industry thinks about. Origin class enforcement should be a standard security feature.

If this project contributes to that conversation, it was worth building.

For Those Who Want to Build Similar Things

Start with the theory, but don’t stay there. Read the papers, understand the math, then close the papers and try to build. You’ll discover what you actually understand versus what you think you understand.

Build incrementally. Don’t write 3,000 lines of circuit code and then try to debug. Write 50 lines. Test. Write 50 more. Test. This is slower initially but faster overall.

Choose your tools carefully. I used Circom for the base circuit because the tooling is mature. I used Rust for the prover because nova-snark is excellent. I used Hardhat for contracts because it’s what I knew. You don’t get points for using exotic tools. You get points for shipping working code.

Document your decisions. Future you will not remember why you chose depth 4 for the policy tree or why you used Poseidon with width 3 for lineage commitments. Write it down.

And finally, be honest about what you don’t know. I spent a week confused about cycle of curves. I spent two days debugging hash mismatches. I made mistakes and fixed them. That’s how learning works.

Performance Benchmarks

ZK-ORIGIN is a recursive zero-knowledge system designed to verify the lineage and policy compliance of state transitions. This benchmark evaluates the performance of the system across different proving modes, scalability scenarios, circuit complexity, and on-chain costs.

The results demonstrate that recursive folding allows ZK-ORIGIN to maintain constant proof size, constant verification time, and predictable proving cost, regardless of how long the lineage becomes.

Proving Modes Comparison

ZK-ORIGIN currently supports two proving configurations: Commitment Mode and Nova Mode.

Commitment Mode is designed primarily for development and testing environments. It prioritizes extremely fast proving and minimal setup overhead but does not provide zero-knowledge privacy.

Nova Mode, on the other hand, is intended for production deployments. It uses recursive folding to generate zero-knowledge proofs that can be verified efficiently on-chain.

Commitment Mode (Development)

• Setup time: approximately 93 milliseconds
• Per-step proving time: about 240 microseconds
• Proof generation time: roughly 4 microseconds
• Verification time: about 346 nanoseconds
• Proof size: 32 bytes
• Zero-knowledge: No

Nova Mode (Production)

• Setup time: approximately 1.46 seconds
• Per-step proving time: 60–140 milliseconds
• Final proof generation: about 1.96 seconds
• Verification time: ~406 nanoseconds
• Proof size: about 10 KB
• Zero-knowledge: Yes

Although Nova mode is slower than commitment mode, it provides strong privacy guarantees and supports recursive proofs, making it suitable for production systems.

Scalability Analysis

One of the most important characteristics of ZK-ORIGIN is its constant per-step proving cost, even when the lineage grows.

In traditional systems, verification complexity grows with the number of previous states. However, Nova’s folding mechanism allows each step to be recursively compressed into a single proof.

Benchmark tests show that the per-step proving time remains approximately 68 milliseconds, regardless of how many previous steps exist.

For example:

• A lineage with 3 steps takes about 203 ms total.
• 10 steps require roughly 680 ms.
• 50 steps take around 3.4 seconds.
• 100 steps take about 6.8 seconds.
• 500 steps require roughly 34 seconds.
• 1000 steps complete in approximately 68 seconds.

Even though the total proving time grows linearly with the number of steps, the per-step cost remains constant. This behavior is the key advantage of recursive folding.

Get Zkchainforge’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The final proof size remains constant at approximately 10 KB, regardless of how many steps are included.

Circuit Statistics

The ZK-ORIGIN step circuit is implemented in Circom.

The circuit responsible for validating a single lineage transition contains:

• 630 non-linear constraints
• 794 linear constraints
• 1,424 total constraints
• 3 public inputs
• 4 private inputs
• 2 public outputs
• 1,426 wires
• 2,222 labels

When integrated into Nova recursion, the circuit expands into two interacting circuits:

• A primary circuit using the Pallas curve, with roughly 9,831 constraints
• A secondary circuit using the Vesta curve, with roughly 10,357 constraints

This results in about 20,188 constraints per recursive step.

Constraint Distribution

The total circuit workload is distributed across several functional components.

More than half of the constraints are dedicated to policy verification via Merkle proofs.

Approximate breakdown:

• Policy Merkle verification accounts for about 55% of constraints.
• Counter verification represents around 14%.
• Transition hashing using Poseidon contributes another 14%.
• Lineage hashing requires roughly 12%.
• Counter updates represent about 3%.
• Origin validation consumes less than 2%.

This distribution highlights that policy verification is the dominant computational cost in the circuit.

Hash Function Choice: Poseidon vs SHA-256

A major performance optimization in ZK-ORIGIN is the use of the Poseidon hash function instead of traditional cryptographic hashes such as SHA-256.

In zero-knowledge circuits, standard hash functions are extremely expensive in terms of constraints.

Approximate constraint costs:

• SHA-256 requires around 25,000 constraints
• Keccak-256 requires around 150,000 constraints
• Poseidon requires roughly 287–412 constraints

ZK-ORIGIN uses five Poseidon hashes per step.

If SHA-256 were used instead, the circuit would require roughly 125,000 constraints per step. By using Poseidon, the system reduces this to approximately 1,500 constraints, achieving an 83× efficiency improvement.

On-Chain Verification Costs

The final proof generated by ZK-ORIGIN can be verified on Ethereum smart contracts.

Estimated mainnet costs (assuming a gas price of 30 gwei) are as follows:

• Deploying the Groth16 verifier contract costs roughly 1.5 million gas, or about $90.
• Deploying the lineage verification contract requires around 800,000 gas, or about $48.
• Verifying a proof consumes approximately 250,000 gas, which is roughly $15.
• Updating the policy root requires around 50,000 gas.

Because the proof itself is about 10 KB, calldata adds roughly 160,000 gas.

Overall, verifying a ZK-ORIGIN proof transaction on Ethereum mainnet costs approximately 410,000 gas, or about $25.

Layer-2 Verification Costs

Running verification on Layer-2 networks dramatically reduces costs.

On networks such as Arbitrum or Optimism, where gas prices are around 0.1 gwei, the same proof verification costs roughly:

• ~$0.05 for proof verification
• ~$0.08 for the entire transaction

This makes large-scale deployments significantly more affordable.

Comparison With Other Proof Systems

Compared to other modern proof systems, ZK-ORIGIN (using Nova recursion) achieves a strong balance between proof size, proving time, and verification efficiency.

Typical characteristics include:

• Proof size: about 10 KB
• Proving time: ~68 ms per step
• Verification time: less than 1 millisecond
• Recursion: native support

For comparison:

• Groth16 produces extremely small proofs (128 bytes) but recursion is expensive.
• PLONK provides flexible circuits but slower verification.
• STARK systems have very large proofs (50–200 KB).
• Halo2 supports recursion but typically requires longer proving times.

Nova was selected because recursive folding is significantly cheaper than verifying proofs inside circuits, making it ideal for lineage systems.

Memory Usage

Memory consumption varies depending on the phase of the proving process.

Typical peak memory usage:

• Parameter generation: about 2 GB
• Per-step proving: around 180 MB
• Proof compression: roughly 1.5 GB
• Verification: about 50 MB

Memory usage grows linearly with the number of steps because the prover accumulates witness data.

For example:

• 10 steps require about 220 MB
• 50 steps require about 450 MB
• 100 steps require about 800 MB
• 500 steps require about 2.5 GB
• 1000 steps require about 4.5 GB

For very long histories, periodic proof compression checkpoints can be used to control memory growth.

Circuit Artifact Sizes

The compiled circuit artifacts are relatively compact.

Typical sizes include:

• R1CS constraint file: about 196 KB
• WASM witness generator: around 500 KB
• Proving key (.zkey): approximately 632 KB
• Verification key JSON: about 3.6 KB
• Solidity verifier contract: roughly 15 KB

In total, the circuit artifacts occupy around 1.35 MB.

Nova parameters used for recursion are larger:

• Public parameters: roughly 50 MB
• Prover key: about 25 MB
• Verifier key: around 5 MB

Summary of Key Results

The benchmark results highlight several important performance characteristics of ZK-ORIGIN:

• Proof size remains constant at about 10 KB, regardless of lineage length.
• Verification time remains under 1 millisecond.
• Per-step proving cost remains approximately 68 milliseconds.
• Policy enforcement achieves 100% correctness, blocking all invalid transitions.
• Poseidon hashing provides an 83× efficiency improvement compared to SHA-256.

Production Readiness

The current implementation has already completed several milestones:

• Core proving pipeline is functional
• Verification pipeline is operational
• Policy enforcement logic is implemented
• Rate limiting mechanisms are active
• Smart contracts successfully deploy on Ethereum

However, a few improvements remain before full production deployment:

• Reducing proof size from 10 KB to under 1 KB
• Adding BN254 curve compatibility
• Performing additional gas optimizations

Closing Thoughts

Six weeks ago, this was an idea in my head. A frustration with repeated exploits and a vague sense that something was missing from ZK infrastructure.

Now it’s code. Circuits that compile. Proofs that generate. Contracts that verify. A system that does something useful.

I don’t know if anyone will use ZK-ORIGIN specifically. But I know that building it taught me more than any course or tutorial could have. The learning came from the struggle, from the bugs, from the moments when nothing worked and I had to figure out why.

That’s the thing about building from scratch. You don’t just learn how to use someone else’s tool. You learn how the tool works. You understand the tradeoffs because you made them. You know the edge cases because you hit them.

If you’re considering building a ZK project, do it. Pick a problem you care about. Accept that it will be harder than you expect. Build anyway.

The industry needs more builders, not more people who read papers and nod along. Build something. Ship it. Learn from it.

That’s what I did. I’m better for it.

The ZK-ORIGIN codebase is available at https://github.com/ZKChainForge/zk-origin . Questions and feedback welcome.