💻 computer science

Automating Bitvector and Finite Field Equivalence Proofs in Lean

This paper introduces BitModEq, a novel Lean tactic that automates equivalence proofs between bitvectors and finite fields using range lemmas and case analysis, outperforming state-of-the-art SMT solvers in verifying Zero-Knowledge Proof circuit encodings.

Original authors: Elizaveta Pertseva, Valentin Robert, Clark Barrett, James Parker

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Elizaveta Pertseva, Valentin Robert, Clark Barrett, James Parker

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Two Different Languages for Math

Imagine you are trying to verify that a secret recipe (a Zero-Knowledge Proof) works correctly. The problem is that the recipe is written in two different languages that don't mix well:

Finite Fields: Think of this as a "Clock Math" world. If you have a clock with 17 hours, adding 10 and 10 doesn't give you 20; it gives you 3 (because you wrap around). This is how many modern cryptographic systems (like those used in cryptocurrencies) do their math.
Bitvectors: Think of this as "Computer Math." Computers don't wrap around like clocks; they just have a fixed number of switches (bits) that are either on or off. If you add numbers and run out of switches, the extra bits just get chopped off.

The Problem:
When developers build these cryptographic systems, they have to translate the "Clock Math" into "Computer Math" to make it run on real hardware. This translation is called arithmetization.

If the translation is wrong, the whole security system is broken.
Checking if the translation is correct is incredibly hard.
Manual checking is like proofreading a novel by reading every word with a magnifying glass: it's accurate but takes forever and is prone to human error.
Automatic checking (using standard computer solvers) is like using a spell-checker: it's fast, but it often gets confused by the weird "Clock Math" rules and gives up on complex sentences.

The Solution: The "BitModEq" Translator

The authors built a new tool called BitModEq inside a system called Lean (which is like a super-strict math tutor that checks every step of a proof).

Think of BitModEq as a specialized translator that doesn't just swap words; it understands the logic behind the words. It uses a three-step process to prove that the "Clock Math" recipe is exactly the same as the "Computer Math" recipe:

Step 1: The "Unwrapping" (Translation)

The tool takes the "Clock Math" (Finite Fields) and tries to "unwrap" it into normal numbers (Natural Numbers).

The Challenge: In Clock Math, $5 - 10$ might be a positive number because of the wrap-around. In normal math, it's negative.
The Trick: The tool looks at the numbers and asks, "Is it possible for this number to wrap around?" If the numbers are small enough (like bits in a computer), it knows wrapping won't happen. It safely removes the "Clock" rules and treats them as normal math. If it's not sure, it keeps the "Clock" rules but adds a safety check.

Step 2: The "Safety Net" (Range Analysis)

This is the paper's secret sauce. Before the tool tries to convert the math into computer bits, it performs a Range Analysis.

The Analogy: Imagine you are packing a suitcase. You don't just throw clothes in; you check the size of the suitcase and the size of the clothes.
How it works: The tool looks at the variables and asks, "What is the biggest this number could possibly be?"
- If it knows a number is between 0 and 1 (like a single light switch), it can ignore the complex "Clock" rules entirely.
- This step is crucial because it simplifies the problem so much that the computer can solve it easily. Without this "safety net" check, the computer gets overwhelmed by the complexity.

Step 3: The "Bit-Blasting" (Final Proof)

Once the tool has simplified the problem into pure "Computer Math" (bits), it uses a technique called bit-blasting.

The Analogy: This is like taking a complex lock and trying every single combination of keys until you find the one that opens it.
Because the tool simplified the problem in Step 2, the "lock" is now small enough for the computer to try every combination instantly and prove the math is correct.

Why This Matters (The Results)

The authors tested their tool on real-world cryptographic systems (specifically Jolt and CirC).

The Competition: They compared their tool against the best existing automatic solvers (like cvc5).
The Result: The existing solvers often got stuck or timed out when the problems got big (like 32-bit numbers). They were like a spell-checker trying to read a dictionary.
BitModEq's Win: The new tool solved 19% more problems than the best existing tools. It could handle much larger numbers (up to 32 bits) where the others failed.
Bonus: Because it runs inside Lean, the proof is kernel-checked. This means the computer didn't just guess; it followed a strict set of logical rules that are guaranteed to be correct, shrinking the risk of hidden bugs.

A Real-World Discovery

During their testing, the tool actually found a bug in the CirC compiler. The compiler had a mistake in how it handled large numbers (specifically, a 32-bit right shift). The bug only showed up with large numbers, which is why previous, smaller-scale tests missed it. The developers fixed the bug after the authors reported it.

Summary

The paper presents a new way to automatically verify that cryptographic math works correctly. Instead of struggling to translate between "Clock Math" and "Computer Math" manually or with clumsy tools, they built a smart translator that:

Checks the size of the numbers first (Range Analysis).
Simplifies the math by removing unnecessary "Clock" rules.
Uses brute-force logic to prove the final result is correct.

This makes verifying complex security systems faster, more reliable, and capable of catching bugs that other tools miss.

Technical Summary: Automating Bitvector and Finite Field Equivalence Proofs in Lean

Problem Statement

The verification of Zero-Knowledge Proof (ZKP) circuit encodings faces a critical challenge: proving the correctness of quantifier-free statements that simultaneously utilize bitvector operations (standard machine arithmetic modulo $2^N$ ) and finite field operations (arithmetic modulo a large prime $P$ ). ZKP systems often require "arithmetizations" that encode bitvector logic as finite field polynomials. Ensuring these encodings are correct is vital for the soundness of ZKP systems, yet constructing them is error-prone.

Existing verification workflows suffer from two primary limitations:

Manual Verification: Embedding entire ZKP systems in Interactive Theorem Provers (ITPs) like Lean provides strong guarantees but requires substantial human effort. As ZKP optimizations evolve rapidly, these manual proofs frequently require significant rework.
Automatic SMT Verification: Reducing verification to Satisfiability Modulo Theories (SMT) queries offers greater automation but struggles with two fundamental issues:
- Theory Conversion: SMT solvers lack native support for converting between finite fields and bitvectors. Workarounds like bit-splitting introduce excessive variables, and range checks require complex polynomials that degrade solver performance.
- Trusted Code Base (TCB): SMT solvers have a much larger TCB than ITPs, increasing the risk of missed bugs.

Methodology

The authors present BitModEq, a novel Lean tactic designed to automatically prove the equivalence between finite field encodings and their corresponding bitvector semantics. The approach leverages the rich semantics of ITPs to perform direct type conversions while retaining the automation of SMT solving through a specialized workflow.

Core Workflow

BitModEq operates in four distinct phases (illustrated in Figure 1 of the paper):

Finite Field to Natural Number Conversion: All terms of sort Finite Field ($FP$) are converted to Natural Numbers ( $N$ ). This involves pushing conversion operators (like toNat) inward through arithmetic expressions.
Range Analysis: Inequalities over natural numbers generated during conversion are discharged using a dedicated range analysis algorithm.
Natural Number to Bitvector Conversion: Remaining natural number terms are converted to bitvectors ( $BV_N$ ).
Bit-Blasting: The final bitvector equality goals are discharged using bv_decide, a bit-blasting decision procedure implemented in Lean.

Key Technical Components

1. Translation Calculus (Sections 4.2)
The tactic employs a set of translation rules to move between domains:

$FP \to N$ : Rules such as distNat distribute toNat over addition and multiplication. Crucially, the tactic distinguishes between cases where modular wraparound can be ruled out (allowing simple subtraction) and cases where it cannot (requiring the addition of the modulus $P$ followed by a modulo operation). Rules like sqrBds detect bit encodings (where $x^2 = x$ ) and translate them to bounds ( $x \le 1$ ).
$N \to BV$ : Rules like distBV distribute toBV over operations. Unlike the $FP \to N$ step, these rules do not require adding a modulo operator because the target space is naturally modulo $2^N$ .

2. Range Analysis (Section 4.3)
Standard Lean tactics (e.g., omega, linarith) often fail on ZKP arithmetizations due to large coefficients and complex variable dependencies. BitModEq introduces a custom, syntax-directed range analysis calculus:

Placeholder Variables: The algorithm introduces existential placeholder variables to decompose complex inequalities.
Decomposition & Elimination: Rules decompose inequalities (e.g., $a + b \le w$ becomes $a \le w_1, b \le w_2, w_1+w_2 \le w$ ) and eliminate placeholders by instantiating them with bounds derived from hypotheses or known properties (e.g., finite field elements are bounded by $P-1$ ).
Dependency Handling: Specialized rules (ineqCases, ineqXOR) perform targeted case analysis on variables simulating bits (0 or 1) to resolve dependencies that standard arithmetic solvers miss.

3. Implementation
The tactic is implemented in Lean 4.23.0, utilizing mathlib for lemmas and bv_decide for the final bit-blasting step. It relies on Lean's kernel for proof checking, ensuring a minimal Trusted Computing Base.

Key Contributions

BitModEq Tactic: A Lean tactic that translates finite field operations to bitvectors and solves the resulting goals via bit-blasting, retaining the correctness guarantees of ITPs.
Bounded Verification of Real-World Encodings: A proof-of-concept verification of two real-world ZKP systems (Jolt and CirC) that achieves higher bit-width bounds than previous techniques.
Specialized Range Analysis: A new Lean tactic for proving goals resulting from the translation, specifically designed to handle the variable dependencies and inequality constraints common in ZKP arithmetizations.

Results and Evaluation

The authors evaluated BitModEq against state-of-the-art SMT solvers (specifically cvc5 with full and split Gröbner bases) on benchmarks extracted from Jolt (a zkVM) and CirC (a zkVM compiler).

Performance: BitModEq solved 19% more benchmarks than the best-performing SMT configurations.
- On Jolt benchmarks (8-bit and 32-bit lookup tables), BitModEq solved 3 more 8-bit and 7 more 32-bit instances than cvc5 (weak encoding).
- On CirC benchmarks, BitModEq solved more instances for 13 out of 17 tested bit widths.
Scalability: While cvc5 performed better on smaller bit widths, its performance degraded significantly as bit widths increased due to the explosion of variables from bit-splitting. BitModEq scaled effectively up to 32-bit inputs.
Efficiency: An ablation study showed that the custom range analysis is critical; removing case splits reduced the number of solved benchmarks significantly (e.g., from 737 to 720 on CirC, and from 24 to 21 on Jolt). Replacing the custom analysis with standard Lean tactics (ring_nf, linarith, etc.) resulted in a drastic drop in solved instances (e.g., 434 vs 737 on CirC).
Runtime: Range analysis accounts for approximately 52% of the total runtime, followed by translation (23%) and bit-blasting (21%).
Bug Discovery: During the evaluation of CirC, the authors identified a soundness bug in the 32-bit arithmetic right shift implementation related to integer overflow, which was not detected at smaller bit widths.

Significance and Claims

The paper claims that BitModEq addresses the specific limitations of current ZKP verification workflows by combining the soundness of ITPs with automated reasoning. By translating finite field constraints back to bitvectors, the approach avoids the performance bottlenecks of SMT theory conversion and the large TCB of SMT solvers.

The authors emphasize that their approach is particularly effective for ZKP arithmetizations that simulate bit-level operations within a finite field, a common pattern in modern ZK systems. While the method is not complete (it may return "unknown" for certain complex dependencies or field-specific operations like inverses), it successfully verifies real-world encodings that were previously intractable for automatic tools, providing kernel-checked proofs for the correctness of these critical cryptographic components.