qedb: Expressive and Modular Verifiable Databases (without SNARKs)

Verifiable Databases (VDBs) allow clients to outsource data storage without trusting the provider: a client holding only a short digest can verify any query response using a compact server-provided proof. Given the ubiquity of both databases and outsourced storage, VDBs address a fundamental need. Our work advances the state of the art in VDB design. Our main contribution is qedb, a simple and performant construction for SQL queries based on bilinear pairings. Like some prior VDB schemes, qedb leverages features specific to the database setting; however, it differs from such approaches in its technical blueprint, the breadth of supported queries, and performance. Notably, it is the first scheme of its kind with proof size independent of database size and without quadratic preprocessing. Compared to VDB solutions based on general-purpose proofs, qedb offers stronger tradeoffs in at least one of the following: provable security, proof size and verification time, or system complexity and maintainability (over an order of magnitude fewer lines of code). As additional contributions, we provide both an implementation of qedb and new theoretical foundations for VDB design-a novel framework modeling idealized protocols for verifiable databases, which future work can use in a plug-and-play manner. Through our modular approach we can get more provably secure instantiations of qedb for free, including a post-quantum one from lattices. Related Work Works on VDB can be (roughly) categorized into two broad categories, depending on the underlying approach: from authenticated data structures or from general cryptographic proof systems 10 9 qedb is a recursive acronym standing for "qedb error-checks databases". It is also a shameless pun on it being a proof system for DBs. 10 Besides this section, we compare qedb against other schemes in Section 7.