ZK12: Make Web3 use Web2: verifiable SQL db for contracts - Nikkolasg N

Transcript

[Music] [Applause] thank you everyone so hi everyone today I'm going to speak to you about what we're doing at LR I'm going to talk about a bit of SQL and uh more technically what we are doing behind the scenes um so let's go about it so why do I mention SQL here basically we are very building a verifiable SQL VM so that means you can query the database and get a proof uh and the results that the result is correct um so how does it look concretely then okay it looks like this uh basically we are focusing first on

the historical blockchain uh data so basically if you have for example take a rc20 so think about usdc for example where there can be millions of entes from the user address to the balances um then you can actually register your SQL query where you say give me the average balance of this user for the last two weeks uh and for this address you can use placeholder as well and we're going to give back the result and the proof on chain okay that's more fact the product facing point of view um and I'm going to explain to you how we are doing it uh doing this talk and I'm happy to talk more about the produ side after my talk because it's only 15 minutes very short um cool so what do we do here um we are

talking first about indexing historical blockchain data so that means that every block we're going to insert the values of some slot of interest in the contract sole if you have the mapping we're going to insert all the mapping Andes into our own database okay that's called the indexing parts and we're going to do this at every block because because we want to keep the values uh and want to do the average from or over more complicated SQL queries down the line then comes the uh query Parts okay so this the first Ty is just insertion think of it as a Time Ser database and the second part is uh the cing Parts where we actually run the SQL C across a subset of this database and we prove the results so what is all database I'm been mentioning this uh since the beginning

but we need a database which is well proof friendly okay uh because we want to give a proof so that means we can't use things like I mean it's not very nice for us to use things like kak and rlp encoding for those who know how the MPT trees works on evm uh we want also to be Oly scalable just to give you a not of magnitudes if you want to do an average across a full week that's like on eum on L1 on etherum it's like 50k blocks if your mappings have I don't know 1 million entries you already 50 billions entries okay so we want to be originally scalable to be really endling large scale computation um the third point we want is also want efficiently updatable that's a very very important point for us imagine between block I and block I plus1 there's only one swap of token I

sell some of token and give to to another holder then I don't want want to have to reprove the millions of entes for this block I just want to efficiently update my database such that we only insert this new value for me and the recipients okay um so how does it work like I'm hinted before at every block we are looking at the storage LW interest in for some contracts so for the variable mapping thing this we can do St we can use single variabl thing this uh later we're also working on the transaction try receip try and everything and we are are we are extracting this value we're proving that all the value belong to this contract and we are inserting the same values but in a more ZK friendly format so no RP no K this with a nice think of it or

database as a nice BST mer with poson okay it's a fairly bit more involved than this but I'm going to skip the detail for this talk um and we do this at every block and uh so we transform we insert all this value into our database and then comes the query phase okay so the quer phase uh here it's a very simple example where you can imagine you want just to compute the average so you compute uh V1 plus V2 on the left node on the left side V3 plus V4 on the right side you can compute this in parallel so this is where the parallels property comes into before and then you can aggregate uh the proof to get the final proof at the end so here for the cury phase we use recursion as well bit um I'm going to focus a little bit more on

the indexing part because this is like really the Crux of of what we are we are building here um let's skip this one uh so how do we build this database so we need two major ingredients there first we need what we call recal Tre which is paper invented by the research team lrch so let's take the problem of we want to prove a membership proof for many leaves inside a tree okay it could be a Merc tree could be MPT tree um let's take the na approach okay if we if we use a regular proof system like gr 16 or for example dkm you the usual way you would do it is like you feed all the witnesses so you feed the value 1 2 3 four and you directly prove that they all uh are

inside this uh this tree okay uh what happens when we update the tree so for example from block I to block I plus one there is one value that changed let's say now of three it's eight okay well uh basically the path changed okay but the rest didn't change but inside the proof you still need to give all the values still so the combilation is linear in the number of entries here because remember we are appending uh things so we are copying all the values from block I to block I + one and only change the one that change uh here I still need to make run proof across all the values so that's not good for us uh because again think of a large scale contract with millions of mappings entries uh that's that's not scalable enough for so what

we do instead is we go more into the map reduce Paradigm instead of doing one big proof over many data we do many proof over small set of data so now we turn the F around and we say one node of the tree is equal one proof okay so we have one proof for the node one one proof for node two three and four each proof expose the hash of the sub tree uh that is rooted at this note okay so for example in the left orange one then we're going to have U the hash of the conation of the hash of one and the hash of two okay and so we're going to have two proof at the middle and one final proof for the roots here we use a lot regression you can see that the proof in the middle needs to verify the proof for

one and verify the proof for two and the top group proof needs to verify the children proof as well okay so we use recushion all the way here so we pay a bit a bit more because recushion is not uh cheap the nice thing about it for when we update well we don't need to recompute everything now we only need to recompute the proof from the value to the roots that change okay so this slide is wrong it should be eight here but imagine uh three is eight then you just recompute the proof for eight it's parent and it's parent and here for the four you can just load it up from the previous uh block you don't need to recompute it just take take the one that we had before okay and so that allows us to be to have a complexity

logarithmically in terms of number of updates now so our assumption is like the block entropy the entropy between blocks is fairly low so there's going to be a few updates between F transfer between blocks and so that all us to be very fast in proving updates now and so what we do is just copy the whole database and we just recompute the proof that we need to recompute and we leave it as it is that's the first tool okay um the second one is digest translation so this has been hinted already by uh Yan gr this morning and we also using uh multi set hashing so the the problem here is in MPT the order is um complicated let's say it really depend on the key you're putting in the mapping

like this uh evm and solidity have special rules and so you you don't have a nice structured order for exle we could have the value 1 1432 in this order if you just enumerate the Le like this uh and we have very different kind of branches and filling this and extension node and all this stuff uh these are non proof friendly at all and also it it imposes a certain order into it okay and we don't want this we want to build a database which is e efficient for crewing so that means we want indexes we want a bstd property as well anything this so how can we turn this weird ordering into all n's database we can't just use a hash function because the order is important here and this is where uh the multi set ashing comes into

place so uh basically it's as explained this morning you just uh take your message you hash it and you m to point in the group for this right now we're using plun 2 and we're using the EC gfp 5 curve and so we do a hash2 curve on this uh curve which is an based on an extension field the fif extension field Feld of gold Delux and we just compute the digest in vmpt okay so we have digest D here we compute the digest on own database from the same value so you can see D1 plus D2 plus D3 plus D4 this is the Merle Tree in order the D2 is from the MPT but then the result is the same so we at the end we we we very reely verify the true proof and to make

sure that both have the same digest and if both have the same digest that mean both contain the same data that we extracted and that's the second tool so basically when we put things together at each block we are extracting the value of interest from the PT ex extracting the value of interest for own DB we show that they contain the same digest we only update the proof that are needed during the update right and uh that's it we do it at every block then now comes the curry part of it so um I think have this slide so the cay part of it is uh fairly short because of this talk is quite short but um basically we treat each node of the tree as a logical SQL R so

think of it each node can contain your balance the total balance and the uh the user address for example um how we going to do the the cury well we're going to our tree is kind of a BST tree so we're going to look right in the portion that satisfy the predicates on the index so for example if we had an index on the address then we're going to sort the tree we have a BSD Tree on the addresses and so we're going to look at all the rules that satisfy the predicates we're going to show in circuits that they satisfy the predicates we're going to compute the results and then we simply grow up the tree and accumulate the results uh one by one okay so at the end when we reach the top of the tree we got the a aggregated proof iated results and

uh we can just submit this on chain um and we of course we do a wrapping grossing of chain to to submit on evm chains that's our main target trailer um a bit fast okay get five minutes so the other thing I want to quickly mention to you uh today is also the fact that as you saw we are using recession a lot so that means we are generating a lot of proof like I'm talking about uh 200 300 400 proof per minute easily so we're dealing with thousand and thousand of proof uh to generate all this proof in parallel we need a strong Prov Network so we also building our own Prov Network basically um so we're building the Prov

Network in the building of it dog footing and so here it also requires quite a lot of changes so we are an AVS with restak security from ion layer so here the economical security only comes for the live property so if I send a task to aover and it doesn't reply me with proof in certain timeout before a certain timeout then it's going to be penalized but the the guarantee that we the proof offer is still relying on Purely on the cryptography assumptions uh the the stake is only there for the liveness issue and yeah that's really basically the oversight of LR also what we are building again the pro Network and the application building on top of it um just a final quick slide to just where we are right now we delivered the

we shipped on the April vly test net with a basic site of query where we can only extract mappings we implemented The Proven network uh in May and we just recently we launch launch our Z processor one Z where we have the basic of the SQL VM now fully implemented and now it's just a matter for us to implement more and more SQL function for we're going to be working on joints order by Group by all these things uh simple select and we also more and more data but we want to extract we want to extract the reip tries and the truction try as well um and then coming up for Z 2 this is when uh the all the features will be will be there and I guess that's about it for me um I have two minutes for question if there is any questions

do we have any quick questions we have two minutes over there sorry great presentation can you do uh zero gas transactions with um with L gr can we do zero gas transaction yeah what what's the cost usually for a query okay so right now the cost First is to verifying a gross 16 Pro font chain so it's like 280 gas or something 200 gas depends on which type of uh grossy team we're using um and uh there's also the cost of uh quering so frle if you are

crying a month long average or a week long average if this is 50k block example for a week long if you're only cing for two hours if this 600 blocks so it's not the same range of uh computation as well uh so also the the the price Model is is to be determined as well according to the size of your query and there's also the part this is for the query part there also the indexing part because uh we automatically index some tabl so we need to also to uh to take inite into ion that we at every block we automatically making some proof so we we are doing also some some work there uh so the we have to pay for the indexing and for the cre but the the the the cost there is not that significant as if we can use

are pro a network efficiently and so because we are not paying the cost of proving them directly okay that's all oh wait is it a fast question it's ZK it's not good thanks for the presentation the the values that you're storing in these record trees are like usually public values or like a representation of like the storage of a smart contract on chain or they can be also private values yeah so here I presented our main use cases which is onchain historical data but again we are building a verifiable SQL VM so we could put any data into our SQL the nice thing about blockchain is we can prove that we correctly extracted

this value from this contract from this loot storage from this variables from this block header with this chain ID even we can be cross chain compatible anything like this but we can totally also upload just nft metadata which are not proven at all and we just said we just put a hash as a kind of commitment and that's about it but we can't the client will have to trust that it's done correctly because we can't prove it's come from thanks okay thank you Nicholas Round of Applause and