TruthTable: A Verifiable Query Engine

  • Bharath Namboothiry, University of Pennsylvania; Kim Laine, Microsoft

TruthTable is a verifiable database engine that allows a prover to produce a succinct proof that convinces a verifier of the correct execution of the verifier’s SQL query over the prover’s committed database. TruthTable supports a large subset of SQL, enabling it to prove 17 out of 22 queries in the standard TPC-H benchmark. To our knowledge, this is the widest support out of all prior work. Moreover, TruthTables proofs are small, and fast to generate and verify: on the TPC-H benchmark with a database of a million rows, TruthTables average proving time is 55 seconds, average verification time is 32 milliseconds, and average proof size is 24kB. Compared to prior work, TruthTable’s proving times are between 6.3-63x better, while the verification times and proof sizes are competitive. TruthTable achieves these properties via a codesign of cryptography and database techniques. On the cryptographic front, we propose a new polynomial representation of database tables, and design new subprotocols for proving the correct execution of various relational operators on these representations. On the database front, we propose a query planner that optimizes queries for minimal proving time, as opposed to minimal execution time. We also design new optimizations for this planner that reduce proving time by up to 2x.

Series: Cryptography Talk Series