TruthTable: A Verifiable Query Engine
Bharath Namboothiry
Abstract:
Modern client-server applications routinely trust a server's reported query results without verification, even when the server is incentivized to misreport. Existing remedies each fall short: authenticated data structures support only a narrow fragment of SQL, trusted hardware is repeatedly undermined by side-channel attacks, and general-purpose SNARKs over whole queries incur substantial overhead. We present TruthTable, a verifiable query engine that proves query correctness via a modular composition of proof protocols for core relational operators. This modularity enables proof-aware query planning and rewrite rules tailored to the proving setting. To support these protocols, we develop a toolbox of new polynomial proof techniques — including protocols for no-duplicate detection, lexicographic sorting, and nonzero checks — which may be of independent interest. We fully implement TruthTable and evaluate it against leading academic and industrial verifiable query systems, achieving the fastest proving times and the broadest coverage of the TPC-H benchmark suite among all systems compared by a wide margin.
Bio:
Bharath Namboothiry is a second-year Ph.D. student in Computer Science at the University of Pennsylvania, advised by Prof. Pratyush Mishra. He received a B.S. in Mathematics and an M.S. in Computer Science from Stanford University, where he worked under the supervision of Prof. Dan Boneh. His research focuses on the design and efficiency of cryptographic proof systems and their deployment in real-world applications, with broader interests spanning theoretical computer science.