TruthTable: A Verifiable Query Engine

TruthTable addresses the critical problem of trust in SQL query results, especially for computationally weak clients querying untrusted servers. Traditional approaches often rely on simply trusting server responses, which can have significant consequences in areas like on-chain analytics or high-stakes AI applications (e.g., legal or medical AI agents).

Limitations of Prior Work

Previous verifiable database systems, such as IntegraDB, VSQL, ZKSQL, PonyGlyph, and QEDB, commonly used off-the-shelf SNARKs. This approach, while natural, suffered from several drawbacks:

• Pre-generated, Complex Circuits: Circuits representing query computations had to be generated in advance and could be arbitrarily complex.
• Lack of Flexibility: A fresh circuit was required for every change in the query or database schema (e.g., adding a filter or a row).
• Performance Bottleneck: Performance was limited by the efficiency of generic SNARK provers and verifiers, without leveraging the inherent structure of SQL queries.

TruthTable’s Approach: Co-design of Cryptography and Database Techniques

TruthTable introduces a novel approach inspired by decades of research in query execution engines, focusing on leveraging the intrinsic structure of SQL queries.

Query Plan-Centric Design

The system uses query plans (graph-like structures) to represent SQL queries, where intermediate results of operations (e.g., join, filter) are treated as cryptographic witnesses. This allows for a modular approach where correctness of the final result is proven if and only if a witness satisfies all nodes in the plan.

Operator-Specific Proof Protocols (PIOPs)

TruthTable develops specific proof protocols for almost the entire set of SQL relational operators, from simple ones like FILTER and PROJECT to complex ones like JOIN, GROUP BY, and ORDER BY. String parsing expressions (e.g., prefix, infix) are noted as areas for future work.

Data Representation

• Polynomial Encoding: Each column of a database table is encoded as a multilinear polynomial over a large prime field (FP elements). Integers and booleans are converted to FP elements; strings are currently hashed. This encoding enables efficient cryptographic operations.
• Activator Polynomials: To handle sparsity and varying table sizes, an activator boolean polynomial flags which elements are real rows and which are not (tombstoned with zero).

Proof of Correctness (PIOPs)

Each operator’s correctness is defined by a set of algebraic conditions. These conditions are then proven using Polynomial Interactive Oracle Proofs (PIOPs), which are compiled into SNARKs using polynomial commitment schemes and the Fiat-Shamir heuristic.

• Filter Example: For FILTER, conditions include: every output row is a distinct input row, every output row satisfies the filter condition, and every input row not in the output fails the filter condition. This is optimized by copying input column polynomials and only updating the activator polynomial for the output.
• Join Example: For JOIN, correctness involves proving: each output tuple comes from a matching input pair (using left_source and right_source witnesses), no matching key pair is repeated (non-duplicate check), and the cardinality of the output matches the total number of matching pairs.

PIOP Toolbox and Sum Check Reduction

The system relies on a set of fundamental protocols (the “PIP toolbox”) such as logup (for lookup claims), non-duplicate check (for uniqueness), and match pair (for cardinality). Crucially, all these protocols ultimately boil down to sum check claims, providing a unified and optimizable foundation.

Query Planner Optimizations

TruthTable’s query planner incorporates both traditional database optimizations and proof-specific optimizations:

• Traditional Optimizations: Examples include filter pushdown, which rearranges operations to reduce the size of intermediate tables, thus minimizing witness sizes.
• Proof-Specific Optimizations: Compaction is an example, where sparse intermediate tables are re-represented in a smaller hypercube to reduce proving costs, using ‘identity’ operations where semantically identical.

ARCPOP: Batch Compilation Engine

To handle the complexity of compiling multiple PIOPs for arbitrary queries, TruthTable includes ARCPOP, an open-source PIOP proof engine for batch compilation. ARCPOP applies several optimization techniques:

• Heuristic Degree Reduction: Reduces polynomial degrees to optimize sum check costs, which grow super-linearly.
• Batching Fundamental Claims: Batches various types of claims (zero check, non-zero, lookup) early, rather than waiting for individual sum check reductions.
• Sparsity/Constant Awareness: Avoids unnecessary field operations by leveraging the sparsity of polynomials.

TruthTable Workflow

1. Prover: Receives the query plan, desired result, database, and identified optimizations. It computes witness values and generates a proof using ARCPOP, which includes the proof itself, commitments to intermediate witnesses, and a serialized list of applied optimizations.
2. Verifier: Receives the query, expected result, database commitment, and the proof. It re-derives the query plan by applying the serialized optimizations (ensuring they are sound) and then uses the ARCPOP verifier to check the proof against the database commitment and witness commitments.

Performance and Evaluation

TruthTable demonstrates significant performance improvements and wide SQL coverage:

• Coverage: Supports 17 out of 22 queries in the TPC-H benchmark, making it the most expressive verifiable database to date (excluding full string parsing).
• TPC-H (Scale Factor 0.1, ~1 million rows):
  • Average proving time: 55 seconds.
  • Average verification time: 32 milliseconds (split roughly 50/50 between query plan derivation and proof verification).
  • Average proof size: 24 kB.

Comparisons

• Academic (PonyGlyph): TruthTable achieves 5x faster proving times with similar verification times and proof sizes, while providing automated proofs for arbitrary queries and a full binding to a database commitment (PonyGlyph lacks this, significantly understating its actual cost if included).
• Industrial (Proof of SQL, QEDB): TruthTable shows up to 80x faster proving times (vs. QEDB) and 175x faster verification times (vs. QEDB), along with competitive proof sizes. These comparisons are based on individual query benchmarks, as industrial systems have yet to release TPC-H results.

• Tags:
• Feature
• Cryptography
• Zero-Knowledge Proofs
• Relational Databases
• SQL
• Verifiable Databases
• SNARKs
• Query Engines
• PIOPs
• TPC-H Benchmarking
• Polynomial Commitments