This post presents some ideas we have been working on at cryptonet to obtain simple verifiable databases.

If you need more context on the setting, please see this page. As a refresher on the setting though:

• assume there is a public short commitment to a spreadsheet or a large database;
• we want to support queries on these data so that it is fast to cryptographically guarantee that the query response was correct given a short certificate for the query.

We generically refer to this setting as verifiable tables.

What’s Tavloid?

Tavloid is a simple approach to verifiable tables that mainly strives for:

• Concrete efficiency
• Simplicity: based on few basic components, easy to understand as possible, fast to implement.

There is a vast literature on the problem, but much of it focuses on asymptotic behavior using sophisticated (but complex) data structures; often it does not achieve the practical efficiency (especially in proof size) we may hope for.

In addition to being efficient and simple, Tavloid aims at:

• Being “SNARK later” (rather than “SNARK first”): general-purpose SNARKs a sledgehammer-type solution to the problem. Tavloid strives for more targeted solutions and that do not require compiling to a special representation, such as a circuit.
• Being extensible: while what we describe here supports a very basic application setting, it is possible to make it more powerful without sacrificing modularity. For this reason Tavloid strives for the use of algebraically-flavored commitments (think: KZG-ish yes; Merkle-tree-ish no) which can connect easily with other proof systems (not necessarily general-purpose).

What it can do: queries and efficiency

What it supports: Tavloid supports simple SELECT and (inner) JOIN queries in databases. It is especially suited for SELECT queries for membership of categorical data (see example below) or testing for small ranges. JOINs in Tavloid are also efficient on categorical data.