Provably V2 & QEDB: Verifiable Databases Without SNARKs

Databases form the foundation of our technological infrastructure across numerous domains. Indeed, databases power nearly every digital system our societies rely on databases to store, among others, financial systems data, scientific and academic data, social networks data and governments records.By 2024 the global “datasphere” had grown to approximately 149 zettabytes, that is 149 trillion gigabytes.

As organizations and users increasingly outsource storage and computation, one question becomes critical: how can you trust that a database query result is correct without redoing the work yourself?

This is the challenge of Verifiable Databases (VDBs) that Provably has taken up. A VDB lets a client hold a short digest of the data, then check any query result against a proof of correctness. This approach enables ”chains of trust”, allowing organizations to build reliable workflows using verified data, even when parties do not fully trust each other. For VDBs to be practically applicable in such a sense and in general settings, verification must be efficient (consuming significantly fewer resources than re-executing queries) and public (not limited to predefined verifiers).

Today, most expressive VDBs rely on general-purpose proof systems like SNARKs. While powerful, SNARK-based systems are complex, require large circuit representations of queries and databases, and often rely on heuristic assumptions.

Provably, working in team with Matteo Campanelli, has researched, designed and implemented QEDB (a recursive acronym standing for “qedb error-checks databases”) and takes a different path. Instead of SNARKs, it builds on specialized cryptographic data structures, achieving both simplicity, expressiveness, and efficiency. The result is a verifiable database framework that supports complex SQL queries (joins, aggregates, comparisons across columns); produces proofs whose size is independent of the database size; removes the quadratic blowup in the number of columns that plagued earlier ADS-based VDBs; runs efficiently in practice, scaling to millions of rows with small proof sizes (~0.5–1 KB). QEDB’s novelty comes from a modular framework, separating the logic of query verification from the cryptographic instantiations. This makes it easier to analyze, audit, and swap in new primitives (even post-quantum ones).

The cryptographic primitives at the core of QEDB are KZG polynomial commitments, Linear-Map Vector Commitments (LVCs), and Subvector-Opening Vector Commitments. By combining these primitives, QEDB compiles idealized query protocols into real-world VDB systems. The modularity also means new cryptographic backends (e.g., lattice-based polynomial commitments) could be plugged in for post-quantum verifiable databases.

QEDB is the protocol at the core of Provably v2, and it has already been deployed to a selected number of clients.