Automating Bitvector and Finite Field Equivalence Proofs in Lean

“Automating Bitvector and Finite Field Equivalence Proofs in Lean” by Elizaveta Pertseva, Valentin Robert, Clark W. Barrett, and James Parker. In Computer Aided Verification - 38th International Conference, CAV 2026, Lisbon, Portugal, July 26-29, 2026, Proceedings, Part II, (Eva Darulova, Anthony W. Lin, and Philipp Rümmer, eds.), 2026, pp. 165-187. Lisbon, Portgual.

Abstract

Efforts to verify Zero-Knowledge Proof circuit encodings have highlighted the challenge of proving the correctness of quantifier-free statements that make use of both bitvector and finite field operations. Existing verification workflows are either manual or rely on SMT solvers, which scale poorly on some classes of problems for reasons that include difficulties with conversion operators and challenges reasoning about inequalities. To address these limitations, we present a novel Lean tactic BitModEq that leverages range lemmas and case analysis to produce verified translations from finite fields to bitvectors. Our approach, combined with bit-blasting, outperforms state-of-the-art SMT solvers, solving 19% more ZKP arithmetization benchmarks.

BibTeX entry:

@inproceedings{PRB+26,
   author = {Elizaveta Pertseva and Valentin Robert and Clark W. Barrett
	and James Parker},
   editor = {Eva Darulova and Anthony W. Lin and Philipp R{\"u}mmer},
   title = {Automating Bitvector and Finite Field Equivalence Proofs in Lean},
   booktitle = {Computer Aided Verification - 38th International
	Conference, {CAV} 2026, Lisbon, Portugal, July 26-29, 2026,
	Proceedings, Part {II}},
   series = {Lecture Notes in Computer Science},
   volume = {16683},
   pages = {165--187},
   publisher = {Springer},
   year = {2026},
   doi = {10.1007/978-3-032-32526-6_8},
   note = {Lisbon, Portgual},
   url = {https://doi.org/10.1007/978-3-032-32526-6_8}
}

(This webpage was created with bibtex2web.)