TruthTable Proves SQL Results Against Committed Databases

Bharath Namboothiry frames TruthTable around a simple but consequential problem: a client sends a query to a server, receives an answer, and lacks the resources to independently recompute it. That is ordinary practice for SQL systems. It becomes inadequate when the answer is operationally important.

He offers on-chain analytics as one example. A smart contract may need historical blockchain data that it cannot itself query, so it relies on an indexer. If that indexer is adversarial, the wrong answer can have direct financial consequences. He gives high-stakes AI agents as another: a legal agent may retrieve precedent from a database while helping to assemble a case file, but a lawyer cannot rely on a citation merely because the system produced it. The desired response would include not only a cited result but a small cryptographic proof that the result genuinely came from the relevant public legal database.

TruthTable works in the standard verifiable-database model. A trusted data owner takes the database, commits to it cryptographically, leaves the database with an untrusted server, and gives the commitment to a computationally weak client. The data owner may be a distinct party, the client that originally collected and outsourced the data, or—in cases where the server owns the data—the root of trust for that data. Once the commitment exists, the client sends a normal query. The server returns both a result and a proof that the result is the correct execution of that query over the committed database.

In an exchange with Esha, Namboothiry makes the boundary of that guarantee explicit. TruthTable proves correct execution against the committed database, while trust in the underlying data and in the correctness of its commitment remains with the trusted data owner. Whoever is trusted to source the database is also trusted to have computed its commitment correctly.

That distinction matters. The system does not establish that the committed data was collected honestly, complete, or otherwise fit for purpose. It establishes that the returned result follows from the committed data. Namboothiry says a broader system could also prove provenance—for example, with a chain of commitments from an empty state and a transition function—but that is outside the model described for TruthTable.

The commitment-bound guarantee also distinguishes this model from a proof that merely establishes that some database could produce a given answer. Here, the result is bound to the database commitment the client received.

Namboothiry describes the conventional alternative as turning an SQL query and a fixed database shape into a circuit, then handing the circuit to an off-the-shelf SNARK setup. It is a natural starting point but an awkward fit for database work. Complex queries produce complex circuits; a change to the query or even to the shape of the database calls for a fresh circuit; and the design remains constrained by the generic prover and verifier underneath it. Most importantly, it leaves the structure developed by decades of database-query research largely unused.

TruthTable instead adopts the query plan, the graph-like internal representation used by execution engines. A query that joins users with orders on an ID and then filters for orders above 100 becomes a graph: the two input tables feed an inner join, whose intermediate result feeds a filter. The plan is semantically equivalent to the textual SQL, but it exposes the individual computations that produce the result.

The key proposition is that a query result is correct if there exists a set of intermediate tables satisfying every node in that plan. Those intermediate results become witnesses. Rather than prove one monolithic claim about an entire SQL computation, TruthTable proves that each constituent operation was performed correctly—join, filter, aggregation, ordering, or another operator—and composes those proofs along the plan.

The resulting protocol family covers projection, ordering, joins, distinctness, identity, aggregation, filtering, limits, arithmetic, logic, and comparisons. The conspicuous gap is string parsing: prefix, infix, and related expressions. Namboothiry says these operations do not fit the system’s current cryptographic representation cleanly. The current approach hashes strings into the field representation, but substring-style operations require a different encoding using multiple polynomials.

The implementation is intended to be a complete system rather than a collection of isolated protocols. It comprises roughly 54,000 lines of Rust, accepts databases and plain-text queries, supports Apache DataFusion query plans, applies both conventional and proof-specific plan optimizations, discovers intermediate witnesses, and returns a query result with a proof. Underneath, it uses polynomial interactive oracle proofs, or PIOPs, for relational operators and compiles them into a non-interactive proof.

A filter illustrates why executing a query and proving it correct are different tasks. Suppose an input table lists students and departments, and the query keeps only rows where dept = CS. An output table is a correct filter only if three conditions hold:

1. Every output row is a distinct input row.
2. Every output row satisfies the filter condition.
3. Every input row not included in the output fails the filter condition.

The third condition is essential. Without it, a server could return only some qualifying rows—or none at all—while still showing that every row it did return was valid. A proof of correctness must establish completeness as well as validity.

For joins, the obvious formulation is too expensive. An inner join can be described as the full cross product of two tables, filtered to pairs whose keys match. But explicitly constructing or proving over all possible pairs becomes impractical at scale. A pair of large input tables can have an enormous cross product even when the actual join output is relatively small.

TruthTable instead adds provenance witnesses to every output row: leftsrc and rightsrc, the row IDs in the left and right input tables from which that output row originated. In the presentation’s example, a row pairing Ali from the CS department with a CS Cryptography course contains the identifiers of both source rows.

That changes the correctness relation. A join output is correct when:

1. Each output row is a matching-key pair from the two input tables. The tuple containing leftsrc and the left-side values must appear in the left table, with the equivalent condition for the right side and rightsrc.
2. Each (leftsrc, rightsrc) pair is unique.
3. The number of output rows equals the total number of matching-key pairs between the two inputs.

The source IDs distinguish an illicit repeated output from genuine duplicate-looking source values. Two otherwise identical course rows can legitimately correspond to different right-table row IDs. Repeating the same left/right source pair cannot.

Once validity and uniqueness are established, matching the output cardinality to the total number of eligible pairs rules out omitted matches. The presentation characterizes the resulting work as proportional to the sizes of the two inputs and output, rather than their full cross product.

TruthTable implements these relations through a hierarchy of PIOPs. For a join, a lookup protocol establishes that the claimed input tuples occur in their source tables. A no-duplicate check establishes uniqueness of source-ID pairs. Namboothiry describes a simpler construction: make a lexicographically sorted copy of the pairs, prove that the copy and original are equivalent, then prove the ordering is strict, which rules out repeated adjacent values. A match-pair check establishes the required output cardinality.

These tools sit below operator-specific protocols for join, aggregate, projection, distinct, filter, limit, algebra, logic, comparison, ordering, and identity. At the bottom, the system reduces its protocols to sumcheck-based claims. That common base is significant because it makes work from separate nodes in a query plan eligible for batching.

The practical consequence of TruthTable’s data representation is that it can preserve a table’s rows while changing only the part of the representation needed to express an operator. For filters in particular, the prover need not construct and commit to an entirely new set of data columns; it can retain the original columns and send a new activation polynomial identifying the rows that survived.

Cryptographic protocols do not natively operate on tables, typed columns, or SQL values. TruthTable first converts column values into elements of a large prime field. UINT64 values can be represented directly; Boolean values become 0 and 1. Each column then becomes a multilinear extension: a multivariate, degree-one polynomial whose evaluations on a Boolean hypercube represent the column values.

A three-row table needs a hypercube with four available locations. The unused location cannot simply be left undefined, so TruthTable adds an activation polynomial, or activator. Its Boolean values mark real rows with 1 and padding with 0. The table’s data columns together with its activator form what the presentation calls an arithmetized table.

For the department filter, the output can reuse the input’s name and department polynomials. Only the output activator changes: rows that fail dept = CS are switched off. That reduces the fresh material from three polynomials to one Boolean polynomial.

The filter’s semantic conditions then become algebraic claims. Let act be the input activator and act* the output activator. The requirement that an output row came from an active input row is expressed as:

If the input activation is zero, that equation forces the output activation to be zero. The requirement that selected rows satisfy the predicate becomes:

The activator makes that condition apply only to selected rows. The remaining completeness condition is a nonzero claim over rows active in the input but inactive in the output: each must fail the predicate. TruthTable uses zerocheck and nonzerocheck protocols to prove those claims.

New activators must themselves be proven Boolean unless they have a canonical form the verifier can derive. An activator with a known number of leading ones followed by zeros, for example, need not be transmitted as a new object; the verifier can construct the polynomial from that count. The all-ones activator is simply a constant.

The representation also defines a technical boundary. TruthTable uses field arithmetic rather than an emulation of u64 arithmetic, and assumes intermediate arithmetic does not exceed the approximately $2^{256}$-sized range Namboothiry describes. Strings are the principal values that do not naturally fit. They are currently hashed into the field, which supports the presented operator set but not substring-oriented SQL.

For TruthTable, the cost of a query plan is not just the work needed to execute it. The system must also find intermediate witnesses, commit to them, and prove the relations between them. That makes the size and representation of intermediate tables central design choices.

It still benefits from familiar database transformations. Consider a plan that joins users and orders, then filters for orders above 100. If the join condition is not selective, the join can create a large intermediate table, only for the subsequent filter to discard most of it. Filter pushdown moves the predicate beneath the join: orders is filtered first, and only the surviving rows join with users. The semantics remain unchanged, but the witness that needs to be committed to and proved can be much smaller.

TruthTable also makes choices a conventional execution optimizer would not necessarily make. Filtering naturally produces a sparse representation: the data columns remain in their original shape while an activator marks many positions inactive. That is efficient for the filter proof itself, because only an activator needs to change. But it may be a poor input to a downstream join.

The presentation’s example starts with a four-slot filtered table containing only two active rows. An identity operation can rematerialize the same semantic table as a compact two-row table. The compact representation occupies a smaller Boolean hypercube and needs fewer polynomial variables, which can reduce downstream proof work. The identity does not alter query semantics; it changes the form in which an intermediate witness is represented.

Compaction is not automatic. Namboothiry notes that its own cost can outweigh its benefit. The planner must decide whether it is cheaper to preserve the sparse representation or pay to compress it before the next operator. The important distinction is that two semantically equivalent plans can have materially different proving costs.

The verifier does not have the database and cannot independently determine whether a particular intermediate result was sparse enough to justify compaction. Instead, the proof includes a serialized list of applied optimizations. The verifier derives the deterministic plan from the query, applies only transformations from a known set of sound optimizations, and reconstructs the plan being proved. It can accept an inserted identity operation because identity preserves semantics regardless of why the prover chose it.

After witness discovery, the optimized plan becomes a graph of operator PIOPs. The prover commits to the intermediate witnesses and produces a proof for that graph. The verifier derives the same proof plan, checks it against the committed database, and accepts or rejects.

The system also avoids paying independently for every constituent PIOP. Because individual protocols reduce to sumcheck claims, ark-PIOP can batch them: rather than prove every sumcheck separately, it forms a random linear combination and proves the combined claim. Namboothiry presents this as a technique applicable to sumcheck- and PIOP-based systems generally, not only SQL.

ark-PIOP also performs heuristic degree reduction because sumcheck cost grows superlinearly with polynomial degree; batches zerocheck, nonzero, and lookup-style claims; and uses sparsity and constant-awareness to avoid unnecessary field operations. The design goal is to optimize not just the logical query plan but the full proof-execution graph.

TruthTable’s own evaluation measures complete TPC-H queries, while its comparisons with industrial systems are limited to individual operators such as filter, aggregate, join, and limit. The presentation says those systems were not benchmarked on whole TPC-H queries. The displayed relative gains are therefore not a direct end-to-end comparison over the same multi-operator workload.

The academic comparison has a separate limitation. Namboothiry says Poneglyph proves a different statement because it lacks binding to a database commitment. In his characterization, it proves that there exists a database for which a result is correct, rather than that the result is correct for a specified committed database. He argues that adding a gadget binding an entire database to its commitment would impose substantial additional cost, making the reported comparison a lower bound on TruthTable’s claimed improvement rather than a like-for-like full-model measurement.

The presentation reports that TruthTable supports 17 of 21 TPC-H queries. The source description states 17 of 22, but the slides and spoken evaluation use 17 of 21; the figures below follow the evaluation shown in the presentation. The remaining gap is consistent with the system’s stated lack of string-parsing support.

The displayed TPC-H benchmark uses scale factor 0.1, a main table with 600,000 rows, and a stated capacity of one million rows.

The source’s prover-time chart shows a substantial reduction with four threads. Namboothiry characterizes the scaling as more or less linear.

The verifier-time chart separates cryptographic verification from non-cryptographic work. The latter includes deriving and interpreting the optimized query plan and reducing the plan to the proof system’s underlying claims. Namboothiry describes the overall verification time as roughly evenly split between those two categories.

During questions, he clarifies that prover timing excludes the up-front commitment to the database, which is done in advance. It includes commitments to intermediate witnesses. Asked how much of the measured time comes from those witness commitments rather than field operations, he says he does not have that breakdown.

Against Poneglyph, TruthTable reports hand-optimized circuits for six of 21 TPC-H queries on the other side, compared with automated proofs for 17 of 21 in TruthTable. The presentation reports roughly five-times faster proving with similar verification time and proof size, subject to the commitment-model difference.

The industrial comparison slide identifies Proof of SQL with Space and Time and QEDB with Provably. It reports up to 80 times faster prover time and up to 175 times faster verifier time than QEDB, with similar proof sizes. Against Proof of SQL, it reports up to 50 times faster proving, similar proof sizes, and verifier performance ranging from four times slower to two times faster depending on the operator.

Those operator-level results are evidence for the system’s protocols, but not yet evidence for an end-to-end advantage over those systems on full TPC-H workloads. Namboothiry says that comparison remains unavailable because the other systems’ benchmarks did not support it.