Computer Science editorial
Efficient Branch-and-Bound Testing and Verification of zkVMs
The core problem
Zero-knowledge virtual machines (zkVMs) enable verifiable execution of general-purpose programs by translating virtual machine semantics into algebraic constraints over execution traces. The correctness of these constraints is critical: a single incorrect constraint can admit forged proofs (under-constrained) or reject valid executions (over-constrained). Existing approaches do not provide meaningful guarantees at production scale: fuzzers and unit tests often miss bugs, SMT solvers struggle with the size and nonlinearity of constraints, and theorem provers require substantial manual effort.
This paper presents ZEBRA, a fully automated verification and bug-detection framework. For a given program and input, the constraint must admit exactly one valid execution trace—no more and no fewer. This reduces zkVM verification to a solution-set cardinality problem over a canonical trace space, where redundancies such as null-row padding and non-deterministic permutations are eliminated prior to counting. To compute cardinality tractably, ZEBRA lifts analysis from finite-field witnesses to an integer interval lattice, exploiting a structural sparsity property of zkVM constraints: across 5 r
Innovation
ZEBRA was evaluated on five real-world zkVMs. The framework discovered 11 zero-day bugs; 6 have already been independently confirmed and 3 have been fixed by developers. Compared to SMT-based verification, ZEBRA is 51.5x faster, verifies 16.5 percentage point more instances, and its range verification provides up to 63x efficiency gain over repeated single-input verification.
The sparsity property was measured across the five zkVMs: constraints utilize only 14.0% of their theoretical connectivity capacity on average. This sparsity is a key enabler of ZEBRA's efficiency. The parallel branch-and-bound search scales well with the number of cores, and the interval propagation achieves tight bounds with limited approximation error.
Table 1 summarizes the performance comparison:
| Metric | ZEBRA | SMT-based |
|--------|-------|-----------|
| Speed | 51.5x faster | Baseline |
| Instances verified | +16.5 pp | Baseline |
| Range verification efficiency | up to 63x gain | Baseline |
These results demonstrate that ZEBRA provides a practical and effective solution for zkVM verification at production scale.
Why it matters
ZEBRA's approach addresses the limitations of existing verification methods. Fuzzers and unit tests are insufficient because they cannot exhaustively explore the constraint space. SMT solvers struggle with the size and nonlinearity of zkVM constraints, often timing out or failing to verify. Theorem provers require substantial manual effort and expertise, making them impractical for continuous integration.
ZEBRA's key innovation is the reduction of zkVM verification to a solution-set cardinality problem over a canonical trace space, combined with the use of an integer interval lattice to compute cardinality tractably. The sparsity of zkVM constraints (14.0% connectivity utilization) is a structural property that ZEBRA exploits to achieve tight interval propagation. The parallel branch-and-bound search ensures scalability.
The discovery of 11 zero-day bugs, with 6 independently confirmed and 3 fixed, highlights the practical impact of ZEBRA. The 51.5x speedup over SMT-based verification and the 63x efficiency gain for range verification make ZEBRA suitable for production-scale verification. Future work could extend ZEBRA to other constraint systems and further optimize the branch-and-bound search.
In conclusion, ZEBRA provides a fully automated, efficient, and effective framework for verifying zkVMs, addressing a critical need in the security and correctness of zero-knowledge proofs.
Who should read this
Opening member content…