Don't Trust the Server. Don't Trust Us Either.
The cryptographic core of qedb is now source-available. Here is what it does, how fast it is, and where its limits are.

The cryptographic core of qedb is now source-available. Here is what it does, how fast it is, and where its limits are.
A verifiable database lets you check the answer to a query without trusting the server that ran it. The answer comes with a short proof, and you check that proof against a small digest of the data. If the server lies, the proof fails.
We have written about qedb on this blog for a year: why we think it is a third way between authenticated data structures and general-purpose SNARKs, and why we moved away from circuits. Until now, the cryptography behind it lived only in our paper. Now it is code you can read, run and build on.
So today we are publishing qedb-primitives. It is a Rust crate that implements the cryptographic tests from our paper, qedb: Expressive and Modular Verifiable Databases (without SNARKs). You can read the code, run the benchmarks, and check every number in this post yourself.
What's in the crate
qedb has three layers. A parser reads a SQL query. An engine turns it into a sequence of cryptographic tests. Underneath both are the primitives: the tests themselves, which every qedb proof is made of. This crate is that bottom layer.
| Module | What it contains |
|---|---|
setup | the structured reference string (SRS) and the verifier key |
handle | sets of rows, slices of columns, and their commitments |
basic | the basic tests: subset, complement, intersection, union, zero test, inner product, read |
derived | the derived tests: nullifying test, range check, sign check, equal positions, sum check |
transcript | the Fiat–Shamir transcript that makes a sequence of tests non-interactive |
The primitives are where the security lives. Whatever the query, its proof is a sequence of these tests, so if one test is unsound, every proof that uses it is unsound. The primitives are also generic: nothing in them is specific to SQL. The repository's benchmark maps three queries to tests by hand, which is a good starting point if you want to build your own layer on top.
How it works: sets, slices, and tests
We'll use one table throughout: Transaction, with one row per trade and columns such as account_id, trade_date and price. qedb sees it through two kinds of objects:
- A set is a collection of row indices, such as the rows where
account_id = 5938. - A slice is a vector with one value per row, such as the
pricecolumn.
The verifier never sees these objects. It holds only short handles to them: KZG polynomial commitments over the BLS12-381 curve, 48 bytes each. When the data owner publishes the table, they publish a handle for every column, and for every value of a column, a handle for the set of rows with that value: one for account 5938, one for 1 January 2025, and so on.
To answer a query, the prover must convince the verifier of facts about the sets and slices behind these handles. It does so with tests: the prover sends a short proof, and the verifier checks it against the handles alone, with a few pairings. There are two families of tests:
- Basic tests state facts about sets and slices directly. A set is a subset of another, or the complement, intersection or union of others. A slice is zero on every row of a set. Two slices have a given inner product. The values of a slice on a set are the ones the prover claims.
- Derived tests are built from the basic ones, and cover what queries need. A sum check proves that a slice sums to a given value on a set. A range check proves that every value of a slice is an integer in [0, 2ℓ). A sign check proves that a slice is non-negative on a set. An equal-positions test finds the rows where two slices are equal.
For the complete list, see Fig. 8 (basic tests) and Table 2 (derived tests) of the paper.
A query is answered by chaining these tests. Take the total price of account 5938's transactions on 1 January 2025:
SELECT SUM(price) FROM Transaction
WHERE account_id = 5938 AND trade_date = '2025-01-01'The data owner has already published the set of rows for account 5938 and the set for 1 January 2025. So the prover:
- sends the handle of the selected rows, with an intersection test proving they are exactly the rows in both sets;
- sends the sum, with a sum check proving it is the sum of
priceon those rows.
A range filter takes more work, because no set was published for an arbitrary range. To count the transactions in the first quarter of 2025:
SELECT COUNT(*) FROM Transaction
WHERE trade_date BETWEEN '2025-01-01' AND '2025-03-31'the prover has to build the set itself. It splits the rows into three sets: before, inside, and after the quarter. A complement test proves the split covers every row exactly once, and sign checks prove each row is on the correct side of each bound. The count is then a sum check again, this time of a slice of all ones on the rows inside the quarter.
Both queries end with a sum check. Here it is in the crate, on a toy table of four rows:
use ark_bls12_381::Fr;
use ark_std::test_rng;
use qedb_primitives::derived::sum_check::SumCheckProof;
use qedb_primitives::handle::{Set, Slice};
use qedb_primitives::setup::Srs;
use qedb_primitives::transcript::Transcript;
// Setup: a table of 4 rows with one column. (Test-only SRS; see Limits below.)
let srs = Srs::setup(4, &mut test_rng())?;
let column = Slice::new([10u64, 20, 30, 40].map(Fr::from).to_vec()).commit(&srs)?;
// Prover: rows 1 and 3 are selected, and the column sums to 60 on them.
let rows = Set::new([1, 3]).commit(&srs)?;
let proof = SumCheckProof::prove(&srs, &column, &rows, Fr::from(60u64),
&mut Transcript::new("example"))?;
// Verifier: only the verifier key and the two handles.
let (column, rows) = (column.handle(), rows.handle());
proof.verify(&srs.verifier_key(), column, rows, Fr::from(60u64),
&mut Transcript::new("example"))?;The verifier never touches the column's values. It works only with two 48-byte handles, the claimed sum, and the proof.
More complex queries, such as joins, GROUP BY and nested queries, are built from the same tests. The paper describes how.
The numbers
The repository ships a benchmark that proves the three example queries from the paper on a generated Transaction table. Two of them are the queries above. The third returns the transactions of one day, and whether each one's price equals its expected_price:
-- QTot
SELECT SUM(price) FROM Transaction
WHERE account_id = 5938 AND trade_date = '2025-01-01';
-- QCntTx
SELECT COUNT(*) FROM Transaction
WHERE trade_date BETWEEN '2025-01-01' AND '2025-03-31';
-- QMatch
SELECT tx_id, price, expected_price, price = expected_price FROM Transaction
WHERE trade_date = '2025-04-05';We ran it on a commodity laptop, a MacBook Pro with an 11-core Apple M3 Pro chip, using the CPU only, on tables from 215 (32,768) to 220 (1,048,576) rows. As in the paper, QMatch returns one row in 128: 1,024 rows at 217.
Proving grows linearly with the table: twice the rows, twice the time. At a million rows, the prover takes about 14 s for QTot, 31 s for QCntTx and 6.5 s for QMatch. QCntTx takes the longest because range filters are the most expensive to prove: the prover has to show, for every row, on which side of the range it falls. Equality filters cost less, because their sets of rows were committed in advance.
Verification, the part the client runs, stays in milliseconds: about 6 ms for QTot and 14 ms for QCntTx, whatever the size of the table. QMatch goes from 7 to 10 ms, but only because it returns more rows on larger tables, from 256 to 8,192.
Proofs stay small: 1,120 bytes for QTot, 7,248 bytes for QCntTx and 720 bytes for QMatch, at every table size. To check one, the client needs only the published handles and the verifier key.
Part of this speed comes from the implementation. The tests prove the same statements as in the paper, but several use faster constructions: the verifier checks each test with a single multi-pairing, slices are committed directly from their values, and a range check commits to one quotient instead of running one test per bit. The README lists every change. These numbers also differ from the paper's, which were measured with an earlier version of the code.
To reproduce the numbers, run QEDB_LOG_ROWS=15,16,17,18,19,20 cargo bench --bench transactions. Each point in the figure is the best of three runs.
Limits
Before you build on the crate, a few things to know:
- It needs a trusted setup. KZG commitments rely on a secret value that nobody should know.
Srs::setupgenerates it locally: that is fine for tests and benchmarks, but whoever runs it could forge proofs. In production, the setup must come from a trusted-setup ceremony, loaded withSrs::from_powersorSrs::new. - Range and sign checks work on integers. They prove that values are non-negative integers of up to 254 bits. Decimals, dates and timestamps must first be mapped to integers, as the benchmark does with dates.
Try it
Add the crate to your Cargo.toml:
[dependencies]
qedb-primitives = { git = "https://github.com/ProvablyAI/qedb-primitives" }Or clone the repository and run the benchmark:
git clone https://github.com/ProvablyAI/qedb-primitives
cd qedb-primitives
make benchcargo doc --open opens the full API documentation with a worked example, and our paper has the proofs of security.
We built qedb because we think you shouldn't have to trust a database to believe its answers. Publishing its cryptographic core is a step in the same direction. Read it, break it, and open an issue when you find something. If you want verifiable SQL on your own data without assembling the tests yourself, that is what Provably does.
Tell us what you need to prove.