ZK14 - qedb: Expressive and Modular Verifiable Databases (without SNARKs) - Emanuele Ragnoli

Transcript

So uh I'm going to talk about the databases and especially the idea of having expressive and modular databases. This is work that has been accepted at ACMCCS 2026 and it's work between myself Vincent Sabota Simon Bottoni Mat Campanelli and Alberto Tromba and it's collaboration between Prov Technology our startup of chain labs the University of Tartu the University of Warso and the University of Insubra and we don't have a timer here right Okay.

Uh now usually you start with motivation. So uh the typical one why did we do it? Because we liked it but also because it's quite important to have a verifiable databases especially in this era of privacy AI and multiplication of data. So uh databases as a matter of fact around the world they are sort of considered you know the poor stack of the IT framework but as a matter of fact it's where uh data sits all the time there is a bit of echo by the way over yeah okay um they are important in financial system scientific data social platform government records

and most of the time they are outsourced so and that creates It's what we call the trust problem. So, and the trust problem is uh we trust the provider of a DB with our data to do uh two jobs. The first one to stir the data correctly and the second one to execute the queries correctly. So, what happens if the uh database provider lies of there are some bugs or if gets compromised. Verifiable database is an idea that was uh already authored by Ostro Rakovven Smith in uh 2024. I don't remember

exactly the title of the paper but something like efficient computing etc etc but the idea of Ostrovski at all was the client holds only a short digest delta DB uh for every query that the client does to a verifiable DB the um the data owner the database provider attaching a succinct proof pie that is verified then and then the verifier verifies with delta DB the query gives an answer uh the proof pi and then the answer is accepted or rejected and if this is rejected some misbehavior is

called is is got what is the what was the overall goal and the important goal here is that the proof needs to be succinct it needs to be non-interactive and the verification must be public why non-interactive because we are not really doing a streaming or a line etc etc most of the time is a static entity uh that is hosted somewhere why it matters in practice because especially for financial reporting uh the regulators required a regular reporting of data but also of statistical analysis of the data for example to the SEC uh for data market aggregators uh untrusted aggregator s

just needed to certify SLA style claims like the record has been updated in the last 24 hours for blockchain oracles and analytics like offchain data must reach a smart contract and then automatically import it into the execution of the smart contract and after proof that have been untampered and anywhere that there is outsource storage that meets analytical queries Simplicity matters too because uh simpler designs are easier to audit, easier to maintain and historical less vulnerability pro.

What is a verifiable database? It's really uh for uh um probability polomial time algorithms. So we have a setup uh usually the typical tow setup etc etc for ks ag that is actually what we use uh the setup produces a pro a a a public a key for the prover and the key for the verifier there is a pre-processing algorithm in in which uh inputs like uh the prover key and the database outputs a commitment a digest of the database and the state that is on the server side. Um a query is then run. Uh the answer to

the query is given as a with a proof of pi and that is then verified. We then accept or reject. This proof needs to satisfy the requirement of completeness. That is if I have a honest server, the verifier accepts uh the answer uh always. Uh soundness that is if the adversary makes the verifier no sorry no polomial uh time algorithm uh adversary makes the verifier accept the wrong answer. And last but not the least it needs to be succeed. that is basically the size of the proof of the proof and the verifier

time are n o of the size of the answer plus the query. This is very important. Uh we want succinctness in terms of verifier and the proof time and we don't want that to be dependent on the database side size because databases tend to explode. So what is the state-of-the-art and the contribution? There are two main families of verifiable databases. Uh one that comes from authenticated data structures. Uh under these basically u past works have been using uh cryptographic primitives

like set accumulators, vector and polomial commitment and merkel style trees. It is simple. it's well understood and the state-of-the-art best prototype code base etc etc was integrated that was published in CCS uh 2015 and then recently uh general proof systems uh especially from the ZKP area entered the arena with the snarks JKR some check uh zero knowledge VMs they are highly expressive what do we mean by expressive ive it means that when we do a query to a database we want to be it to have the

possibility to be as rich as possible in terms of SQL and uh um examples are uh verifiable SQL zksql punoglyph db uh products of lrange action axium and space and time both the families come with non-trivial drawbacks So the limits of prior ads based system especially integrity DB is that they use a lot um set accumulators. What is a set accumulator? A set accumulators is a cryptographic primitive that essentially proves that an element belongs to a set.

Uh so integrb uh composed uh set accumulators with an authenticated interval freeze. Now the issue with this is that a database is not only a set. A database is a composition of row columns alignments etc etc. When we consider that only with the set operations then for example we lose a multiplicity. So for example if I have the element 10 that is in row five column six and then again it at row 10 of column six with a set accumulators I lose the fact that the element is uh reproduced two times.

Um to do that uh I need to increase bandwidth and to uh play tricks with the set for multiplicity and that leads to the proof in growing in size. Uh and normally this leads to quadratic prep-processing and storage in terms dependent on subject to the number of columns. There is also limited expressivity because I cannot combine columns in a row aware way again. So I'm just proving that the element exist. But for example, if I want to do the if I want to prove that the sum of two elements is a certain value, that is an issue because

the element was counted only once. And uh there is also an issue with the range proofs because for example it's very hard to prove that I selected certain elements for example bigger than a certain value. Integrity DB solves that by using an authenticating interval trees. But authenticated interval trees then uh imply the fact that the proof eventually grows with the size of the database. That is not one of the diserata that we had for um for verifiable databases in terms in when we talk about the other family. So the limits of general power

post approved systems we have issues with complexity zero knowledge VMs require instruction decoding memory consistency segmentation recussion final snark compression there are a lot of moving parts there is a burden in auditing because uh creating cirids based on that that replicate SQL queries etc etc require uh the circuit it normally to balloon and explode. And so there is a lack of simplicity that tends to increase uh the uh the the threat vector when it comes to security.

Now when we started this work the answer that we wanted to have was can we keep the simplicity of authenticated data structure while pushing expectivity and performance like we have in general proof systems. So uh we came up with a new uh verifiable databases construction uh that that is built from simple authenticated data structures in which we combine vector combinments and the set accumulators. It's more expressive than prior ads based work. The proof size is independent of the databases size. It's no quadratic preprocessing or storage and the order of magnitude is a fewer

line of code than ZKBM based uh VDBs. Uh a lot of fewer lines and we also create an abstract framework to express that in also also in order to make it modular such that we could basically swap in and out um the cryptographic primitives. We wrote it in in Rust. it can scale to millions of hours on the laptop. Technical overview. So this is how we constructed it. Uh we have a polomial commitment like a case ag uh basically that gives the digest of the DB and guarantees that the DBs that is claimed to be is the one claimed to

be. Uh we want to do operations that uh are satellike. So does a certain subset belongs in DDB etc etc. So we have the set accumulators but compared to intricate 3DB we don't do the set accumulators on the elements but the indexes of the rows. This is very important because it allows us to do a lot of operations like range proofs that were not possible before in ads type of structures. And then we needed to do operations sorry we needed to prove operations like sum average etc etc all the SQL type of aggregations and for

that so basically we use uh linear map vector commitments uh with the inner product tricks and um we build everything with a compiler uh and uh uh I'm going to skip this I already talked about this basically uh for example let's consider a sum query uh like I want to select uh the element such that the sum of two times the price plus an extra fee as s from a database that is called the price info. So the idea is that I treat each column as a vector that I access via horra endle. So

in the prep-processing the client receives a slice end P the price and another one that is extra fee. The server sends the claimed answer that is X sum of 2BI plus XI over all the eyes. So the client uses those handles to form h= 2 p + x homorphically because that's one of the properties that we include and it accepts it if and only if the inner product of that results with one is equal the sum that has been claimed. Why is this interesting and

exciting? because this was not supported by the previous ads structures like in integrity because as we said already so set based are really hard to achieve the combination of columns uh row by row the cryptographic translation of this abstraction is so I have the two um vector commitments sorry the two commitments cmp in which I commit a vector uh under prk of P and CMX in which I committed vector again under PRK of X. The prover uh answers S plus a proof ps that has been computed using openly uh of um the

linear vector commitment map. And the verifier takes those homorph does a sum of the commitments under homorphism and accept it if and only if the uh verification under linear u verifier key ch1 s uh ps is equal to one. So basically each idealized handle is replaced by an algebraic commitment and each idealized test by a few few uh uh cryptographic pairings.

If we introduce also a a filter like where so we want to select the elements that uh are bigger than a certain value. Now that's where the set accumulator comes in. So now the set S is the sum over a subset X of the number of the rows. We cannot send X in full because if the DB is very big then uh you know the proof becomes linear in the size of the DB. That's again something we didn't want to have but we want an a succinct digest of X and that is the set accumulators. Now the verifier must check the test is in the sum of p on the indexes in this uh set handle and the

set endle contains only and only the indexes with pi um bigger or equal than 100. The trick to do this is that now we need the vectors and sets to talk to each other. They are two different type of commitments. We need them we need to be able to compose them. The framework that we built this as I said before is abstracted from the cryptographic primitives such that we can swap them as eventually and modularize. So we have two opaque orable types that replace the physical access to the data. Think of them as a sort of immaterial pointers. So if you are a verifier you get these immaterial

pointers. You don't get the content of those. They just map basically to the to to the data in the data sets. the slice handle that points to a vector and the set handle that points to a set. The verifier never stores the underlying object and they capture the essential abstraction for uh VDB's blueprints and they capture succinctness and they closely follow SQL flavors. So columns to slices and row sets to sets. It's a little bit what happens in with the polomal IOPS for snarks.

So we created therefore an a a framework with a limited set of operations in a risk style interface. So we have a set of set operations like two sets are uh uh the unity the intersection the inclusion the complements. We have test on slices basically to replicate arithmetic operations using the inner products. We can get a new slices from homorphism and we can read the data with the pre-image style uh of of maps.

Um I'll skip this because we are running out of time. So um once basically the uh verifier received the SQL query now it has to replace each endle with a commitment. So the slice vector slice replaces is replaced with the vector commitments and the set slices is replaced with the set accumulators and each idealized test becomes for a set test an accumulator proof and in our product is mapped to open lib in LVC a read it's a sub vector opening again in LVC and theor slice

it's a verifier local on commitment there is one missing primitive as We said before we want sets to talk to vectors. So a way to test that a slice is a zero on an accumulated set of positions. And again this helps with range proofs. So uh we created this what is called the zero testing in which basically given uh a vector commitments a set accumulators and the proof we want to convince the verifier that vj is equal zero for all the js that are supposed to be selected by the query. Uh the construction theorem is in the paper uh properly proved etc. But informally

basically we use the trick that each row index generate a quotient polomial x minus s that makes vanishes on s if and only f if and only if z ds such that pv etc etc and uh this is a sound because of zippel so the typical I sent uh I I I tested with with the random values and it's absolutely improbable uh that the opposite happens. Um we then have compilation theorem in which basically uh if I have a query family and that meets a succinct

idealized VDBs then there exist a succinct cryptographic VDB for Q from either a holmorphic VC plus a set accumulator with the right test or any extractable homorphic polomial commitment. We have basically one blueprint that allows many instantiation and again because it's abstracted we can swap the uh cryptographic primitives and we can even put in latis based polomial commitments like the ones of one tree in their 2024 paper um >> three four minutes

then I'll skip this. So there are example of queries and how they are realized. Um I'll just mention this. So all the operation that we have done up to now basically support static databases. Uh but uh because L LVC is homorphic. Basically the vector commitments can be updated incrementally and that basically means that VDBs can support updates and proving that an update happens. Of course uh this cannot be done in 01 in the public verifiability settings but uh our the experiments that we have done up

to now supported the case that updates are practical for common patterns like insert delete and single cell updates. And this has been implemented in Rust with Arc Works MBLS 12381 multi-threaded prover single threaded verifier benchmark. It scales really well to million of rows on a simple laptop. We don't need a GPUs. Uh it's uh it's a it's it's a it's it's a middle layer middle layer middleware layer that plugs in into a lot of existing databases.

Uh these are more or less uh sorry these are uh the experimental results that we have in the paper um and that show that the proof size is independent of the size of the DB as we said one of the this is the data and it depends only on the query type and the response. So for example we can see there that a complex query like a Q match um so gets a higher verifier time uh uh etc and uh um the scalability is quasi linear uh the verifier is essentially constant

and uh I'll skip the comparison summary as well and uh I'll uh uh um what we have shown basically is that we have built something very simple ads based uh it has an abstraction layer the framework is idealized because there is a separation of concern and for instantiation and it's simple modular performant and uh extremely easy to audit thank you very much manually do we have any questions Hi, very nice talk. Thank you. Um, I'm

assuming because you're committing to the database that that commitment must be stored somewhere. Where are you planning to store it and share it? Is that something you've thought about? >> It's on the data owner side. >> Thank you. >> Thank you. Any other questions? Oh, everyone's hungry. Okay, so with that, we'll thank Emanuel once again and we can now head to lunch. Um, we'll resume I think at 2 p.m. Thanks.