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 , 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 ., 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 ) or vector commitments (like ). 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.