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.

• 
  SourceryKit: Runtime Verification of Agent Tool CallsIntroducing runtime verification for agent tool calling: how SourceryKit lets production agents prove and verify tool outputs at runtime, catch errors before they propagate, and move closer to reliable autonomy.
  Jul 08, 2026
• 
  Provably V2 is LiveProvably V2 is now live and available for anyone to access and use. Allows users to connect to Relation DBs, comes with an SQL IDE to run verifiable queries at speed.
  Mar 04, 2026
• 
  Beyond Circuits: A New Era for Verifiable DatabasesWhy QEDB makes verifiable SQL practical, without circuits or heavy SNARK overhead.
  Feb 08, 2026