Grant Application: Formal Verification of Zcash's Halo 2 Proof System and Orchard Protocol in Lean 4

I’ve submitted a grant application to ZCG for formal verification of Zcash’s Halo 2 circuits and Orchard protocol using Lean 4.

GitHub Issue: Grant Application - Formal Verification of Halo 2 in Lean 4 · Issue #244 · ZcashCommunityGrants/zcashcommunitygrants · GitHub

Summary: This proposal covers systematic formal verification of Orchard’s core circuit gadgets (Sinsemilla, Poseidon, ECC, MerklePath, LookupRangeCheck), protocol-level security analysis of ZIP 224, and forward-looking research on post-quantum migration and privacy extensions.

Amount: $201,600 over 18 months ($11,200/month)

Category: R&D

Full proposal details are in the GitHub issue linked above. I welcome community feedback and questions.

@ZcashGrants

9 Likes

As a developer building the Hera’s Ledger privacy protocol on Halo 2, I’m thrilled to see this initiative for formal verification. Our current focus is heavily centred on minimising arithmetic constraints, so having a verified foundation is of immense value to our architecture. Looking forward!

2 Likes

I started to look at formalizing one of the Halo 2 gadgets already. You can also view it here.

2 Likes

Just a heads-up that I have amended the original proposal to 1) take into account work already completed, and 2) tighten the scope/timeline. Please have another fresh look at your convenience.

1 Like

Hello, and thank you for the proposal. I have a few general questions I would like to raise.

I find it difficult to assess your background in this specific area, since I do not have direct experience working with cryptography of this level myself. These are complex matters, so the only things I can really rely on are the public discussion around the proposal and publicly available sources. I was able to find some of your academic work, but it appears to be focused mainly on applied mathematics in the medical domain, rather than cryptography or zero-knowledge proof systems. Could you say more about what drew you to Halo in particular, especially in the context of Zcash?

I would also appreciate some clarification on how you frame this work. Do you see it primarily as work intended to improve the Zcash protocol, or more as work aimed at advancing Halo-related cryptographic research more broadly? It would be very helpful if you could provide some concrete practical examples of how the results of this work could be used.

Finally, how much interaction with the Zcash protocol team do you expect this work would require? Would it depend on substantial involvement from them during the course of the project? This is an important question to me, because specialist time is limited, and I am reading broader signals from community leadership that Zcash may have a relatively narrow window of opportunity to realize its potential.

2 Likes

Hi artkor, thank you for the thoughtful questions. I am happy to address each.

1. Background and motivation

My PhD thesis is from 2010 and was indeed in applied mathematics (mathematical biology). That was 16 years ago. In the time since, my career has been in software engineering, with the last several years focused specifically on Rust in the blockchain space, and my very recent work involving cryptographic protocols and formal verification.

Some concrete recent work that is more relevant than the thesis:

  • I have been an active security researcher across ZK and DeFi protocols, including bounty programs on PancakeSwap, Euler, Hyperliquid, and LayerZero, with confirmed findings involving smart contract analysis and protocol-level reasoning.

  • I have contributed to GitHub - GaloisInc/cryptol: Cryptol: The Language of Cryptography · GitHub , Galois’s domain-specific language for cryptographic algorithm specification, including implementing a DIMACS SAT adapter and a :count command for model counting (sharpSAT integration). Cryptol is used by the NSA and DARPA for crypto specification work.

  • Most directly relevant: I have already completed the LookupRangeCheck formalization in Lean 4 ( GitHub - MavenRain/halo2-formal · GitHub ) before requesting any funding. This is 244 lines of Lean 4 with soundness and completeness proofs grounded in Mathlib, covering the running-sum range check, the short range check, and the no-wrap guarantee for the Pallas field. It demonstrates the exact methodology that carries through to the remaining gadgets.

What drew me to Halo 2 specifically: the Zcash Orchard circuit is one of the more consequential deployed ZK systems (it protects real user funds and privacy), it has mature public specifications (ZIP 224, the Orchard book, the Halo 2 book), and Nethermind’s Halva framework proved the viability of extracting Halo 2 constraints into Lean 4, including discovering a severe soundness bug in Scroll’s Keccak circuit using this approach. Zcash’s own gadgets have not received this treatment yet, and the methodology is a natural fit for my current interests and skills.

2. Project framing

This is Zcash-specific work, not general Halo research. Every deliverable targets Zcash’s actual deployed Orchard circuit.

Concretely:

  • Phase 1 produces Lean 4 proofs that Zcash’s five Orchard gadgets (Sinsemilla, Poseidon/Pow5, ECC, MerklePath, LookupRangeCheck) correctly enforce the intended computation. If a constraint in the production circuit is unsound, these proofs will surface it. Over 80% of findings in ZK audit reports trace back to the circuit layer, and manual audits cannot provide completeness guarantees.

  • Phase 2 lifts this to the protocol layer, proving that Orchard (ZIP 224) achieves spend authorization, balance, and Fiat-Shamir soundness when instantiated with the verified circuits.

Practical example: Nethermind used Halva (the same framework I build on) to discover that Scroll’s deployed Keccak-256 circuit had a soundness bug, meaning an attacker could have produced accepting proofs for incorrect hash outputs. This class of vulnerability is exactly what formal verification catches and manual audit misses. My work would provide that assurance for Zcash’s own circuits.

3. Protocol team interaction

Minimal. The core inputs to this work are all public:

  • The Halo 2 Rust crates (zcash/halo2, zcash/orchard) on GitHub

  • The Halo 2 book and Orchard book

  • ZIP 224 specification

  • Nethermind’s open-source Halva framework

I do not anticipate needing substantial protocol team involvement. The work is self-contained: read the public code and specs, extract constraints into Lean 4, prove properties. If ambiguities arise in the specification, I would ask targeted questions (in a forum post, for example), but nothing that would consume ongoing specialist time.

The proposal is also structured to protect against overcommitment: milestone-gated payments, a scope-down option (Phase 1 only at $67,200 over 4 months), and the fact that one gadget is already done before any funding has been requested.

I hope this helps. Let me know if you have any further questions!

3 Likes

Based on the Aborist call details, I support this grant. :student:

2 Likes

Answering a question posed on the last Arborist call, I spoke with Julian Sutherland, and he informed me that Halva is considered stable, and he mentioned that there are a bunch of “precompiles”, or crypto primitive delegated to external calls, into which I could have a look.

Alternative Review Plan and Milestone Restructuring: Halo 2 / Orchard Lean 4 FV

This post is motivated in part by some of the discussion around this grant from the May 11th meeting.

I’m proposing a restructure of the milestones below in two ways: a Phase 1 milestone swap that pulls the ECC gadget to M1, and a Phase 3 reframe that replaces the two report-style deliverables with formal Lean 4 theorems. Total scope, total duration, and total budget are unchanged.

Change 1: M1 / M2 swap (ECC first)

The ECC gadget (variable-base scalar multiplication, fixed-base scalar multiplication, incomplete addition on the Pallas curve) is the single hardest item in Phase 1, as the original proposal already acknowledges in its risk-mitigation language. The original placed ECC at M2 alongside Merkle and RangeCheck; this revision pulls ECC forward to M1.

LookupRangeCheck is already complete (https://github.com/MavenRain/halo2-formal) and will be delivered at grant start, not as part of M1, so M1 carries only the ECC gadget.

Change 2: Phase 3 formal deliverables (not reports)

The original Phase 3 milestones (M5 post-quantum migration analysis, M6 privacy extensions) ended in technical reports. Under the same front-loading principle, this reads as a soft end. This revision rewrites both deliverables as formal Lean 4 artifacts:

  • M5 produces formal Lean theorems on which Orchard protocol properties survive a transition to a lattice-based or hash-based proof system, with the supporting compatibility model expressed as a typed structure. The accompanying technical report becomes a reading guide to the formal artifact, not the artifact itself.
  • M6 produces a formal Lean security model for cross-chain shielded transfers and a formal analysis of alternative key-exchange mechanisms for note encryption. Again, the report becomes a reading guide.

The research surface stays the same; the deliverable becomes a verifiable artifact rather than prose.

Revised month-by-month plan

Month Deliverable
1 ECC: variable-base scalar multiplication specification and completeness proof setup
2 ECC: soundness proof, including incomplete-addition edge cases
3 ECC: fixed-base scalar multiplication and integration. Milestone 1 (ECC complete; LookupRangeCheck delivered at grant start)
4 Sinsemilla: Pallas-based hash specification and Merkle integration setup
5 Sinsemilla: soundness and completeness proofs
6 Poseidon / Pow5: round-function constraints. Milestone 2 (Sinsemilla + Poseidon + Phase 1 technical report)
7 MerklePath: formalization (depends on Sinsemilla, complete at end of M2)
8 Orchard protocol formal model from ZIP 224
9 Spend authorization and balance formal proofs. Milestone 3
10 Fiat-Shamir soundness: transcript binding, Frozen-Heart class analysis
11 Binding signature verification and value balance
12 Note encryption correctness. Milestone 4 (ePrint preprint submitted)
13 Post-quantum migration: formal compatibility model as Lean structures; candidate-system survey
14 Post-quantum migration: formal Lean theorems for Orchard properties surviving lattice / hash transition
15 Post-quantum migration: new-assumption proofs and reading-guide report. Milestone 5
16 Privacy extensions: cross-chain shielded-transfer formal security model
17 Privacy extensions: alternative key-exchange formal analysis
18 Final integration and presentation. Milestone 6 (final code release, presentation)

The plan front-loads the most novel curve and hash work in months 1 through 6, places the protocol-level glue in months 7 through 12, and ends with the formal research deliverables that the original proposal carried as reports. Each month closes with an artifact in the public repository for asynchronous review between milestone boundaries.

Reviewer engagement plan

Daira Emma offered help and endorsed the proposal at the April 30th call, and Conrado confirmed on the same call that the Zcash Foundation has zero formal-verification bandwidth and welcomes outside contributors. I am grateful for both signals. I will coordinate per-milestone review with Zcash core developers, sharing work in progress between milestones for asynchronous review and requesting sign-off at each milestone boundary. Out of respect for everyone’s time, I will hold off on naming specific reviewers in public until they have agreed to take on particular milestones, and I will report each sign-off back to the committee as it comes in.

Acceptance of expert-review payment cadence

Milestone payments are contingent on expert review and may delay for reasons outside ZCG’s control. The work will continue while reviews are in flight, and I do not expect ZCG to compensate for review delays. I will budget cashflow accordingly.

Available for the next Arborist Call

I am available to present this restructured plan on a call, if needed, or to respond in writing to any further committee questions. The LookupRangeCheck repository, the methodology writeup, and the in-progress Lean 4 source are all open at https://github.com/MavenRain/halo2-formal for committee review at any time.

Onyeka (Oni) Obi (aka MavenRain)

1 Like

Thank you for submitting your proposal. Following a thorough review by the ZCG and a period for community feedback on the forum, the committee has decided not to move forward with this proposal.

We sincerely appreciate the time and effort you invested in your application and encourage you to stay involved and continue contributing to the Zcash community. Further details will be available in the meeting minutes to be posted in the next few weeks.

Dang! I’m disappointed, because I really want to see formal verification (of relative consistency) of the things that Zcash users rely on. I look forward to the meeting minutes so we can all learn how to do this better.

2 Likes

The minutes of the meeting will not include my full response, as this document is intended to be concise. Therefore, here is my full response.

I would like to explain in more detail why I voted to reject this proposal.

When this proposal first came in, my initial reaction was that it was too technically complex for me to independently judge how important it really was. That is why the idea came up to have the applicant present on an Arborist Call.

That happened, and I want to thank @isurvivable for giving an excellent presentation. It gave me a much clearer understanding of why this work is needed and why it is genuinely important. We want our code to do exactly the things described in the cryptographic specification, and nothing more.

But I also think there is another side to this.

Beyond the formal verification work itself, it matters to me as a Zcash investor that, at the end of this process, we have a document of this kind from a recognized leader in the field. I do not want to offend anyone, but to make clear what I mean, I will give an example.

In 2020, RAND published a report concluding that Zcash did not have a significant presence on dark web marketplaces, while Perkins Coie, a respected law firm, published a legal analysis arguing that privacy coins can fit within existing AML frameworks.

Those documents mattered not only because of what they said, but because of who stood behind them.

There would be nothing especially difficult about assigning that kind of work to me personally. I could spend a week browsing darknet markets, collecting screenshots, reviewing posts, maybe even trying to chat with sellers directly, and then publish a report saying that vendors refused to accept ZEC.

But that would obviously not carry the same weight for serious institutions, regulators, or market participants. What matters is not only that the work was done, but whose seal stands on the result.

And I think we are now in a similar situation here, especially after the vulnerability discovered in Orchard. It is not enough for us to be convinced ourselves; it is even more important to convince others.

That means it is no longer enough for us to simply say that formal verification was done. For serious investors, it will matter whose name stands behind that report.

That would matter to Ray Dalio. It would matter to the Norwegian sovereign wealth fund. It would matter to the Swiss National Bank. And frankly, it matters to me as well.

I do not think approving this proposal will help us with that task.

That is why I voted to reject.

Furthermore, I do not believe we have another eighteen months to delay this task.

I also want to thank @isurvivable for bringing this proposal forward.

FYI @zooko

3 Likes

Wow, Artkor. I sincerely appreciate the way you’ve — for many years now — demonstrated an unusual degree of candor and transparency in your communication. Thanks for explaining this to me. Very interesting. I will think about it.

1 Like

should adopt modular formal verification by verifying the code and circuits in chunks, drastically accelerate the verification