Grant Proposal: Formal Verification of Zcash's Consensus Libraries in Lean 4 (Zebra and Zakura)

Hello Zcash Community!

For most of Zcash’s life, zcashd was the reference implementation, and most of this year’s consensus bugs in Zebra were found by disagreeing with it.

This year alone Zebra had seven Critical consensus splits in a handful of consensus libraries.

In April it was accepting signatures zcashd rejected, which could split the chain, and two weeks later the fix itself split the chain a different way. In May a different signature rule broke, and two days after its fix some cases were still getting through. By the end of May it was sigop counting, and three days later came an advisory titled “Not Correctly Fixed”.

The tests in the code didn’t catch any of them, because it’s very difficult to test transactions you never intended to build.

So let’s prove the code against the spec instead!

We’ll write the consensus rules these libraries implement in Lean 4, from the protocol spec and the ZIPs, and from zcashd where the spec says nothing, so the transparent script rules get written down for the first time.

Each function in Zebra’s and Zakura’s versions of these libraries is transcribed into Lean, checked against the official test vectors, and proven to follow those rules for every input, accepting only valid blocks and rejecting invalid ones.

That’s where the proofs earn their keep. If a fix only covers part of a rule, the proof fails and we know before it ships. If one library quietly relies on a check another library never makes, which is how most of this year’s signature bugs happened, it shows up as an assumption the proof can’t get rid of. If the code and the spec disagree, or the spec leaves a choice open, the maintainers or the ZIP editors decide which one is wrong.

As Zebra and Zakura are proven against the same spec, they agree wherever they run the proven code, and the next upgrade becomes one set of rules to change instead of two codebases to compare.

The core developers’ own verification work is focused elsewhere: Ironwood’s formal verification covers the cryptography, and ZFND’s zebrafm lists Equihash, the digests, the script interpreter and the trees under “Uncovered areas”.

The libraries

  • equihash 0.3.0 and zakura-equihash 5.3.0: proof of work
  • zcash_primitives 0.31.0 and zakura-primitives 5.3.0: transactions, txid, auth digest and signature hash
  • zcash_encoding 0.5.0 and zakura-protocol 5.3.0’s encoding: byte encodings
  • zcash_protocol 0.11.0 and zakura-protocol 5.3.0: network upgrades, branch IDs and amounts
  • zcash_transparent 0.11.0 and zakura-transparent 5.3.0: transparent inputs and outputs
  • zcash_script 0.6.0 and zakura-zcash-script 0.0.1: the Rust script interpreter, which Zakura runs to check scripts and Zebra uses for parsing and sigop counts
  • zebra-script 14.0.0 and zakura-script 5.0.5: the digests handed to the interpreter
  • zcash_history 0.6.0 and zakura-mmr-tree 0.1.0: the history tree (ZIP 221)
  • zcash_note_encryption 0.5.1 and zakura-note-encryption 5.3.0: shielded coinbase decryption
  • incrementalmerkletree 0.9.0: the note commitment trees

Milestones

  • Milestone 1: transactions, the txid, auth digest and signature hash
  • Milestone 2: transparent scripts and sigop counting
  • Milestone 3: Equihash, the history tree, the note commitment trees and shielded coinbase

Supporting links

1 Like

I believe this work is most suited to the respective creators of Zebra (ZODL) and Zakura (Valar Group and @ebfull), not a third party, since the main issue with Lean formalisation is a false assumption: a Lean proof will pass if you fundamentally misunderstood what the proof was actually evaluating.

It provides a false sense of security and can be a fatal flaw.

The obvious counterargument is “If the original authors write the spec, they might encode the same misunderstanding into both the code and the formalization, and then the proof just confirms their blind spot.”, but then again, come on, it’s not like you’re reading the code either. It’s 2026: Claude wrote the code, and everyone will use Claude to write the Lean code. So unless you’re Least Authority, just… no.

(if you are writing Lean by hand I am very concerned about this being priced at $32,500)

1 Like

I don’t disagree that the maintainers are best placed here: they know what the code is meant to do better than anyone, and that’s exactly what a theorem has to be checked against. Writing the theorems down in Lean doesn’t remove that judgment; but it does put the gap somewhere they can check it.

Proving the wrong theorem is the real risk, and it’s the first one stated in the application:

Proving the wrong theorem: We know that Lean 4 can only check that a proof is correct, not that the theorem means what the spec or code intended. Since each theorem is short and cites the section it formalizes, it can be checked against the spec without reading the proof.

My task here is to write the Lean and review what it claims against the protocol spec and the Rust.

The longer vision is a human genome project for Zcash: the whole protocol spec formalized in Lean, with every implementation proven against it. I’m talking with the maintainers and Shielded Labs about it, and I’d love for them to make it their own, with me joining their effort rather than the other way round.