Abstract
Satisfiability modulo finite fields enables automated verification for cryptosystems. Unfortunately, previous solvers scale poorly for even some simple systems of field equations, in part because they build a full Gröbner basis (GB) for the system. We propose a new solver that uses multiple, simpler GBs instead of one full GB. Our solver, implemented within the cvc5 SMT solver, admits specialized propagation algorithms, e.g., for understanding bitsums. Experiments show that it solves important bitsum-heavy determinism benchmarks far faster than prior solvers, without introducing much overhead for other benchmarks.
The Challenge of Finite Field Verification
Finite fields serve as the mathematical foundation for modern cryptography, including AES encryption and Zero-Knowledge Proofs (ZKPs). Verifying these systems is critical but computationally expensive. Standard automated verification tools rely on Satisfiability Modulo Theories (SMT) solvers, which typically employ Gröbner Bases (GB) to solve systems of polynomial equations.
The primary bottleneck is that computing a full GB is "doubly exponential" in the worst case. In practice, solvers often fail on a common pattern in ZKPs: the combination of bitsums (equations relating a field element to its binary representation) and bit constraints (quadratic equations like $x(1-x)=0$ that force variables to be binary). As the number of bits increases, the interaction between these constraints leads to a symbolic "bloat" that standard solvers cannot handle.
The BitSplit Architecture
To address this, the authors introduce BitSplit, a solver that utilizes Split Gröbner Bases. Rather than computing a single, monolithic GB for the entire system, BitSplit divides the equations into smaller, more manageable subsystems.
The architecture relies on a two-way split:
- The Sparse Basis: This module handles non-linear equations, specifically the quadratic bit constraints.
- The Linear Basis: This module handles linear equations, including the dense bitsum equations.
A specialized propagator acts as the bridge between these bases. By leveraging the mathematical property of congruence, this module infers new equalities and shares information between the bit-level constraints and field-level equations. This allows the solver to maintain global visibility without the overhead of merging the systems into a single complex GB.
Experimental Performance
The authors evaluated BitSplit against a diverse set of benchmarks, including the CirC-D family (verifying determinism in ZKP compilers) and several datasets from prior research (QED², CirC-S, TV).
The results demonstrate a significant performance leap:
- Efficiency: BitSplit solved 969 benchmarks, nearly doubling the 475 solved by traditional monolithic solvers.
- Scalability: On CirC-D benchmarks, monolithic solvers failed beyond 4-6 bits due to exponential time growth. In contrast, BitSplit solved these same problems for bitwidths up to 32 in negligible time.
- Real-World Impact: In real-world ZKP compiler verification, BitSplit enabled the verification of 66% more rule-bitwidth pairs than previous methods.
Conclusion and Future Work
BitSplit effectively bypasses the exponential explosion inherent in traditional GB computations for bitsum-heavy logic. While it represents a major advancement, limitations remain—particularly with non-linear operations like integer division and remainder when encoded as field constraints. Future work aims to integrate advanced SMT features like CDCL(T) theory lemmas and extend the split-basis framework to other cryptographic primitives, such as elliptic curves.
Summary updated