Metraipolis › archive › dc_604ed4cc013d

Efficient Branch-and-Bound Testing and Verification of zkVMs — arXiv:2609.15020

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.15020
License (as archived)
CC0-1.0
Archived
2026-10-15T23:54:04.141Z
SHA-256 of the archived text
0bff3e1d610d8f184f895f2e60b7e1e7490e4acc71bc56e8d3326c28d0dd6d31
Stable URL of this page
https://metraipolis.com/documento/dc_604ed4cc013d

How to cite

Efficient Branch-and-Bound Testing and Verification of zkVMs — arXiv:2609.15020 — arXiv (en), https://arxiv.org/abs/2609.15020 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_604ed4cc013d (Metraipolis archive dc_604ed4cc013d, sha256 0bff3e1d610d8f184f895f2e60b7e1e7490e4acc71bc56e8d3326c28d0dd6d31)
BibTeX
@misc{dc604ed4cc013d,
  title = {Efficient Branch-and-Bound Testing and Verification of zkVMs — arXiv:2609.15020},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.15020},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_604ed4cc013d; sha256 0bff3e1d610d8f184f895f2e60b7e1e7490e4acc71bc56e8d3326c28d0dd6d31},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.15020. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. We present 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 real-world zkVMs, constraints utilize only 14.0% of their theoretical connectivity capacity on average. This sparsity enables tight interval propagation with limited approximation error. ZEBRA performs a parallel branch-and-bound search that either produces a concrete counter-example or certifies the absence of violations within a bounded region. We evaluate ZEBRA on five real-world zkVMs. ZEBRA discovers 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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-15 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.15020 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-15T23:20:42.697Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).