qedb: Rethinking Verifiable Databases from the Ground Up

We thank Nikolai for the pictures. 

And Matteo for the continuous collaboration.

Trust in computing has always been a difficult problem to solve. With time, the typical IT tech stack has grown to a complex system of hardware and software components that often are owned and managed by different actors. This complex system is also often underpinned by  a set of trust assumptions that depends on human behaviour rather than rigorous technological machineries. This is true when a user (human or not) needs to query a remote or third-party database. How can the answer be trusted? While it is true that a commercial/legal relationship can maintain a chain of trust, there are multiple scenarios in which the commercial/legal link can quickly become the weakest and slowest link in the chain.

The problem of querying a remote/outsourced database, and trusting its responses, has shaped a decade of research into verifiable databases (VDBs). Specifically, VDBS are systems designed to ensure that query results are not only correct but cryptographically provable. Over the years, two main approaches have defined this space: 

(1) systems built from authenticated data structures (ADS), and 

(2) systems that use general-purpose cryptographic proof systems (SNARKs). 

Today’s VDBs are at a crossroads. On one hand, SNARK-based systems can verify arbitrary computations, including SQL queries, but at the cost of complexity and high overhead. On the other, ADS-based designs are lighter and more intuitive but traditionally limited in expressiveness. QEDB, from provably,  emerges from the conviction that we can merge the best of both worlds: a return to the ADS roots, but equipping them with a modern algebraic engine.

Two lineages of verifiable databases

At the conceptual level, all VDBs aim to achieve the same goal: to transform untrusted query answers into verifiable statements. The difference lies in the approaches adopted for generating and verifying the proofs of the statements.

1. Authenticated Data Structures (ADS). The ADS approach is based on authenticating the database itself. Each dataset is represented by an authenticated object (often a Merkle tree, or a similar structure), and each query's answer is associated with a proof of consistency with that object. This approach traces back to early tree-based and signature-based methods, where proving membership or ranges was efficient but limited to simple key-value or set operations on small datasets. A milestone in this lineage is IntegriDB, which extends the ADS approach to SQL-like queries with nearly succinct proofs and efficient verification. Though nearly a decade old, it remains a solid reference for practical ADS-based verifiable databases. However, IntegriDB cannot efficiently handle complex relational queries, such as JOINs, that form the backbone of most modern analytical workloads. A particularly elegant conceptual step was taken by Miller et al., who showed how to systematically “compile” arbitrary data structures into authenticated counterparts. Their construction relied only on collision-resistant hashing, a clean, general idea, but one that cannot take advantage of the optimizations offered by algebraic constructions of polynomial commitments (like KZG) or vector commitments (like LVC). Here lies an important insight: while ADS frameworks provide us with structural clarity, we’ve been underusing algebraic tools that compress and accelerate proof construction and verification. This is one of the core ideas behind QEDB.
   
   
2. General-purpose proof systems. The second major path in VDB evolution stemmed from the rapid progress of SNARKs, STARKs, and other zero-knowledge proof systems. Instead of designing specialized proofs for database operations, systems like vSQL compile SQL queries into arithmetic circuits and verify such circuits using general proof systems based on protocols like Sum-Check. This ensures broad expressiveness: any computable query can, in theory, be verified. In practice, however, this comes at a high cost. As databases grow larger, proving time and memory consumption skyrocket, millions of rows mean prohibitively large circuits. Subsequent systems refine this model. ZKSQL, for instance, employs VOLE-based protocols to add zero-knowledge support, but remains non-succinct and struggles with scalability. PoneglyphDB, in contrast, is built on Halo2 and achieves succinctness and logarithmic verification time via recursive proofs. It represents the state of the art for fully general-purpose verifiable SQL evaluation: powerful, but dense and highly complex. Its internal mechanics involve expressing queries as polynomial constraints within the proof system, effectively transforming database logic into circuit logic. As such, in order to obtain reasonable performances over databases containing a few hundred thousand rows, a substantial amount of hardware resources (including GPUs) is needed. Despite their theoretical appeal, SNARK-based verifiable databases often are over-engineered for everyday relational workloads. They inherit the costs and constraints of their proving systems: circuit arithmetic, recursive composition, and heavy cryptographic machinery. For many use cases, this level of generality is unnecessary.

qedb, the third way

With qedb at provably we decided to take a step back and we asked ourselves:

“what if we stay close to the relational data model itself, and represent it with algebraic commitments instead of generic circuit logic?” 

The result is an ad-hoc, algebraically structured proof system that borrows the conceptual clarity of ADS and combines it with the succinctness and composability of modern generic proof systems. 

In qedb: 

• Queries are verified against authenticated algebraic representations of the database, not encoded into monolithic circuits. 
• Proofs remain succinct, leveraging polynomial and vector commitments and structured commitments to represent and verify relational constraints directly. 
• Verification stays efficient, it is  typically sublinear in the data size, without need for recursive proofs or complex circuit compilation. 
• This design approach separates verifiability from the query processing layer itself, rather than treating the database as a mere input to a system that computes a verified execution of the queries. 

In other words, qedb is not a “SNARK for SQL” but an ADS-based proof system reborn with algebraic structure. It is specialized, expressive, and efficient.

The landscape of verifiable databases is evolving fast. Academic prototypes, such as IntegriDB and PoneglyphDB, and commercial systems like Axiom, Lagrange Labs, and Space and Time, all highlight a growing demand for trustworthy query results. But the design tension remains: between generality and efficiency, between cryptographic abstraction and system-level simplicity. Our philosophy at provably is to resolve that tension through specialization: 

Instead of forcing databases to conform to the shape of generic proof systems, we let the proof system grow out of the structure of the database itself.

Verifiable computation started as a problem of proving anything about any function. Verifiable databases refine the challenge: proving statements about structured data. qedb is built on the belief that this difference isn’t cosmetic. The difference should be  foundational. 

And with the new foundation for VDBS that we are establishing at provably, our vision is to unlock a new set of verifiable applications at scale, from Defi to Blockchains to AI agents to Synthetic Data Generation.

By blending authenticated data structures with modern algebraic commitments, qedb opens a path toward lightweight, expressive, and genuinely practical verifiable databases. 

Finally the gap between theory and data-intensive real-world scenarios starts to close.