Research · Papers · Formal verification and machine-checked proof · MF-016
Formal verification of large cryptographic circuits via cone-local proofs
Per-cone proofs composed via existing semantic theorems compile no-sorry in seconds to minutes when monolithic `bv_decide` is intractable
Published 2026-08-29
For everyone
Plain summary
Verifying an entire cryptographic circuit all at once can overwhelm automated proof tools. This method splits that work into manageable pieces. Instead of running bv_decide—Lean's bit-vector solver—on an entire round simultaneously, the proof targets smaller dependency cones or local blocks. Existing semantic theorems then connect those local proofs back to the full circuit. These modular runs compile cleanly without proof gaps (sorryAx) in seconds to minutes. The entry records the verification technique and its compilation performance rather than an optimized design for a specific circuit. It carries a SHOW verdict with no prior-art comparison or novelty claim.
Result
When monolithic bv_decide over a complete round is intractable, per-cone proofs composed via existing semantic theorems compile no-sorry in seconds to minutes. The method supports certified optimization pipelines for large cryptographic circuits.
Setting and definitions
bv_decide is the Lean decision procedure for bit-vector propositions. A monolithic check submits an entire round as a single goal. A cone-local proof restricts the proof obligation to a single output dependency cone, while a block-local proof scopes verification to a named sub-block. Transport lifts these local results into the surrounding circuit model through existing semantic equivalence theorems.
No-sorry compilation confirms that the proof term contains no invocations of sorryAx. The register records compilation latency at the scale of seconds to minutes without a granular per-cone breakdown.
Method
Where whole-round bit-vector decision obligations fail to scale, the method factors verification into per-cone or block-local subgoals. Each local proof discharges in bv_decide, and pre-established semantic theorems transport the local equivalences to the full round.
This paper's downloadable evidence pack provides the compilation receipts validating that cone-local and block-local goals compile without sorryAx in seconds to minutes. The entry introduces no new circuit architectures, gate-count reductions, semantic lemmas, or exhaustive truth-table replays; its scope is the compositional proof architecture and its verified compilation profile.
Discussion
MF-016 resolves proof scalability by exploiting circuit modularity: decomposing an intractable round-level goal into cone- or block-level lemmas enables automated checking without unproved axioms.
The contribution remains purely methodological. The record does not quantify performance across arbitrary circuits, provide detailed per-stage timing tables, or benchmark specific circuit optimizations. It demonstrates that compositional transport makes formal verification practical where monolithic bv_decide stalls.
Curation records list no corrections. The entry asserts no novelty claims or prior-art comparisons and carries a SHOW verdict under the METHOD classification.
For everyone — the takeaway
What this means
This method shrinks the problems sent to automated proof checkers. Instead of testing an entire circuit at once, engineers can verify small wiring clusters and stitch the results together with established mathematical rules. The proof compiles fully without skipped steps in seconds to minutes. This gives developers a reliable framework to verify circuit optimizations without hitting solver timeouts, though performance will still vary across different circuit designs.
Register references
MF-016
HANDOFF §4
Prior art: the register does not record this.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 0 of 0 receipt files bundled (1 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.