Paper 2025/1408

qedb: Expressive and Modular Verifiable Databases (without SNARKs)

Simone Bottoni, Provably Technologies

Matteo Campanelli, Offchain Labs, University of Tartu

Emanuele Ragnoli, Provably Technologies

Alberto Trombetta, Provably Technologies

Abstract

Verifiable Databases (VDBs) allow clients to outsource data storage without trusting the provider: a client holding only a short digest can verify any query response using a compact server-provided proof. Given the ubiquity of both databases and outsourced storage, VDBs address a fundamental need. Our work advances the state of the art in VDB design. Our main contribution is $\mathsf{qedb}$, a simple and performant construction for SQL queries based on bilinear pairings. Like some prior VDB schemes, $\mathsf{qedb}$ leverages features specific to the database setting; however, it differs from such approaches in its technical blueprint, the breadth of supported queries, and performance. Notably, it is the first scheme of its kind with proof size independent of database size and without quadratic scaling for storage or preprocessing. Compared to VDB solutions based on general-purpose proofs, $\mathsf{qedb}$ offers stronger tradeoffs in at least one of the following: provable security, proof size and verification time, or system complexity and maintainability (over an order of magnitude fewer lines of code). As additional contributions, we provide both an implementation of $\mathsf{qedb}$ and new theoretical foundations for VDB design—a new framework modeling $\textit{idealized}$ protocols for verifiable databases, which future works can use in a plug-and-play manner. Through our modular approach we can get more provably secure instantiations of $\mathsf{qedb}$ $\textit{for free}$, including a post-quantum one from lattices.

Note: Accepted at ACM CCS 2026

@misc{cryptoeprint:2025/1408,
      author = {Vincenzo Botta and Simone Bottoni and Matteo Campanelli and Emanuele Ragnoli and Alberto Trombetta},
      title = {qedb: Expressive and Modular Verifiable Databases (without {SNARKs})},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1408},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1408}
}