Ethereum Storage Proofs in a ZK-SNARK, in the Browser

Transcript

Intro

foreign we're going to run through um ethereum storage proofs uh today uh and some of the work we've been doing to make them work uh in a zero North snark and uh in the browser um uh I'm joining one of the co-founders of Aztec and uh we've got Sean here as well uh if you want to give a quick intro yeah I'm Sean sometimes goodbye Maria um yeah I'm a protocol engineer at Aztec awesome um so yeah today we're going to run through kind of in detail uh what a storage proof is uh kind of how they work and how how data is stored on on ethereum uh if that's kind of uh that

doesn't doesn't get an L on the head we'll do some learning by examples um which can help uh in more detail on how storage groups actually work on on ethereum um and the underlying data data structures uh kind of used and maybe then uh some some text on kind of why we would want to do this in aziki snark and some of the benefits compared to normal storage proofs and if we have time a quick demo uh on kind of this end-to-end working uh and kind of the missing pieces to get this working in a browser cool so uh what is the storage proof um so my my take on

WTF is a storage proof?

um I guess trying to sum this up in a sentence um is a verifiable claim that something happened on ethereum uh so that's something could be a payment a transaction uh just a piece of State exists uh in in the ethereum state tree and the key part here is that it's verifiable so you can prove that happened to someone else without having to give them the entire um ethereum kind of uh database still not that clear so maybe we can look at some examples to make things a a bit clearer um so just the the most commonly used one is proof of payment um so let's say I want to pay Sean um uh one eighth and I want to kind of

Storage proofs by example

prove that I've done that uh to a third party or smart contract um I can use the storage proof to actually prove a transaction happened on ethereum and prove that the the balance was one eighth and it went from my address to Sean's address um another popular example is kind of the crypto Punk example so you can prove uh that you own a particular nft by proving a value in a contracts uh storage route we have a demo of this later on uh to prove who owns the first crypto Funk um you can also do this for kind of any nft and this can be used to do kind of gated voting or or similar kind of actions

and the most interesting one um which would have been useful around the FTX time was kind of proving that uh kind of centralized exchanges balance uh is is of all its liabilities um so you can do proof of solvency um with storage proofs you can sum up multiple different accounts and kind of prove uh that the some of the uh assets is greater than the liabilities thank you cool so uh maybe over to Sean to uh go through how he's actually working in detail showing your mute

How do storage proofs work?

what's this so this here is an example of uh what is what is inside an ethereum block so at the top of the block We have basically a lot of metadata that makes up the block and then the main ones that we are interested in are these things called The Well the state roots of a series of um tries so each try so the world State tribe represents the state of all contracts and then if you go further down to the account State you can then prove particular storage slots inside a contract so we pop onto the next slide

so the example of proving a piece of storage in an ethereum smart contracts these are the tries that we care about so with the account storage try I can prove a particular storage slot so for the crypto Punk example I will look for a user's address in the balances mapping and then from there that will that will store that will be stored in a particular path in this account to try I can prove all my way up to the top to the storage route and then I can go into my world State try prove all the way up to my world State and then I'm in the blog cache and in the block and then if I can recalculate the block hash

I can prove that this piece of state does exist so to go over like what these proofs actually look like we can start with something quite simple so we have like a Merkle treatment so to do a market tree proof um I take the node that I want to prove about and then I this this will have to we'll have to um click a few times here to work our way up the tree so I get the sibling path and kind of hash my way up till I get to the root and that is how we if I can recalculate the root of the tree then I can with 100 confidence we're pretty close to it confirm that the

value that I was proving is exists within the tree so this this gets a little bit more complicated with Patricia tries so instead of it just being a binary tree where we hash one piece of data well two two pieces of data all the way up we instead have a choice of things to Hash so this is why these become very expensive within synonyms so for example if I take a particular storage slot I like let's say it's storage lot zero within a contract I hash it to get the path in the root of them of the data trial

and then I follow that path to get to where the leaf the the data will be stored and this path can be made up of either a branch node which is kind of like a traffic Junction that is splits all 16 potential like uh hex values of each nibble in the in the path and then it could have these extension nodes which are kind of shortcuts and then Leaf nodes which store the values themselves so each proof is made up of a combination of this so this is what a branch node looks like so let's say that I am going from the hash is zero a and that's the path that I'm going to go on I would first go

to the node on the very left this this hash on the left and then that will be stored there will be the subtree the hash of the sub tree underneath it and to get the hash of this entire node I hash everything together and then there's also extension nodes which basically contain what we call shared nibbles so let's say that I only have one piece of data in a in an account and it's one value it's bit it's a bit wasteful for me to have about 32 Branch notes to get to the very bottom of the tree instead we have this thing called these extension nodes that basically fill in the gaps so if there's I can basically store 30 nibbles here

and then only have a tree that's of depth three so they're allows us to have shallow trees and then at the leaf we will have again just the hash of the the key itself so the path that's been taken to get to this Loop and then the value itself um so what is the key as I said earlier the key is going to be the ketchup hash of the storage Swap and then the tree is traversed with a combination of the three nodes that were shown above and this is a little small example that kind of demonstrates what the branch and leaf node are actually doing so if the path for a particular hash is one two three four five six I will have a branch node at the top

and then as the first nibble of my path is one I could then take the one in the branch node and then instead of having five more Branch nodes I can just have an extension node that takes me straight to my leaf and this is a depth three three I'll try um what does the proof of this look like so as the the depth of the tree is only three I only have three values of my proof and the proof is going to be the rlp encoding of the hash of each particular of the data in each node so for the leaf node it will be the rlp encoding of the key with the value itself and then on the extension node is going

to be the roleplay encoding of the extension with the hash of the child's tree and then the branch node is going to be an encoding of 17 hashes or 1732 bytes because we have a sub hash for for each of the subtrused range of the potential branches so it's a it's a huge piece of data and what makes these very expensive in scenario is that we have to pay for the branch node at every leaf at every level of the tree which is a sub-optimal so to get a storage proof I can simply ask an ethereum node for one

and they all have this very handy method um from eip1186 that allows you to define a particular contract and storage slot that you would like to get approved for and it will give you um a storage proof all the way up to the block hash so this is as an example of a storage proof for the um the owner of crypto Punk with id1 so and this is this is particularly the proof within the contracts the data tree so this is a five deep Patricia try as you can see there are three large Blobs of data they are the three branch notes in our proof and then we have one

extension node which is the second last piece of data and then the last piece of data is the ROK encoding of the actual Leaf itself so to prove to zoom in on what the first Branch node step looks like this is the ROP encoding of it and then in the next size this is what it is when it's decoded so we can see that there are 16 hashes one for um each hex numeral and then we have an empty value field which is also exists on the branch node so this is just the big blobs aren't too scary once you rlp decode them they're simply just representing leaves of the tree and this is the leaf node at the very

end so as we can see that when you ROP decode it we have the key which is the uh the hash of the storage law itself and then we have the piece of data so for um crypto Punk one the current owner is the address zero X nine four and yeah that is that is a storage proof and how they work cool um so I guess if these ethereum nodes have uh have building methods to to get the data needed to to kind of attest to this claim that something exists on ethereum why do we need to make this more complicated and do it inside a zero knowledge proof or why do we need to

Why do I need Noir or ZKPs?

write this in in a normal circuit um and I guess like to look at that we can kind of uh uh look look at these these uh examples again on the next couple of slides but um I think normal storage proof uh the way I think about this is it convinces a verifier that the state is correct so you can use this in a like client um to kind of uh prove prove that you know the currency of the ethereum blockchain and kind of make some action based on that you could use it in a smart contract um well the data's kind of public but um you don't want to pay a heavy cost for for read uh read items and solilities so you do a lot of week requests in Orange proof

um there's some interesting research on universal protocols that use uh this this mentality you can prove the last uh the price of like Ethan die is between a certain range for the last 100 blocks uh to get a very accurate uh representation of the price um and really it's kind of normal storage proofs are done uh when you need kind of efficiency over the data or one of the parties involved doesn't have all of the data available so you need this kind of efficient proof representation using a Merkel uh Merkel path the main downside though is everything is public so in all of these examples

um you can see kind of all of the parts of the tree that you're hashing and most importantly you can see uh the leaf node at the end so in our in our crypto book example um Sean was able to kind of query an eighth node and figure out which crypto Punk we were talking about what the ID was and who owns it so so which address and that's kind of where normal storage proofs fall down and at the start of why we want to do things inside a zero knowledge proof um so to try and kind of put some color around this uh I've updated the the definition um to kind of describe what a zero knowledge story of proof uh may be um so here I think it's kind of letting

What is a zero-knowledge storage proof?

you prove prove something happened on ethereum um but without revealing what to the world uh and that may sound a bit abstract but uh kind of the last part of disclosing what is what the the zkp uh adds so we can put some examples um we'll go for the examples earlier on in the slides and kind of add zero knowledge on top of them to see how how the example changes so for the payment um we can now prove uh that Bob paid Sally uh without revealing to the world that it was Bob doing the payment or that Sally revealed the payment or even the amount so depending on the application

um uh you may want to kind of prove you bought a ticket uh without revealing your identity uh those sorts of applications now become possible again in the crypto Funk example I can prove that I'm part of a kind of nft community without revealing who I am or which nft I have um so a lot of this came out of some of the the noun style work which we'll talk about in a minute um that's kind of this enables private voting semantics um not kind of revealing who you are when you're voting uh and the last one kind of uh for an FTX style um uh proof of solvency most exchangers don't want to kind of reveal the sum of their assets or their liabilities it's

kind of business Secrets um so wrapping this in a zeroid snark can kind of obscure what your wallets are what the kind of total size of your balance sheet is but still give a guarantee that um the liabilities and assets add to zero so some some kind of rationale to try and see why we want to do this in a in a snark and as I was saying on the previous slide um a lot of This research that we're going to kind of look at on the next slides came from a kind of three-month research Sprint uh with with Aragon um which was uh undertaken as part of uh announced out RFP um the goal for the Sprint was to kind

NounsDAO: Private Voting Research Sprint

of take a storage proof and use it to enable private voting in the browser and so like the crypto bug example in this case we wanted to prove that a user owned one of the noun style nfts and enable them to vote privately on Treasury proposals um or the nouns community and over the last three months um we've had to do a lot of work between ourselves and Aragon to make this possible um we'll go through some of these uh these now but it's not it's not been an easy road but we've made a lot of progress to realize uh this this vision I think the initial circuit size for a storage proof uh

didn't really even compile so it was around 40 million constraints and really you can't prove that on any AWS machine let alone in the browser so we had to do some pretty serious kind of engineering and upgrades to start to make this more feasible the main one we did uh to kind of lower the constraint count uh was upgrade the back end proving system that Noir uses and so we moved from Turbo Planck which was something we made in in 2021 uh to the much faster ultra plonk um and that kind of reduced things by probably 5x in terms of constraint count um we also had a lot of refactoring uh

in the mobile compiler uh to kind of have a lot less bugs but also have things like Dynamic array indexes um uh and we also have a very efficient care track Uh custom gate in Ultra Blanc which the majority of the constraint reduction came from I think we reduced the cost of a ketchak uh kind of hash from around 160 180 000 constraints to around 18 000 which is a huge win especially given the amount of cash is needed in the Merkel Patricia try hashing here so yeah just a summary of those those optimizations here um and the last point is kind of one

What does Noir + UltraPLONK backend enable?

that actually kind of brings us into uh production so in order to get this working in the browser we've had to do uh some work to work around the limits of what's possible um and to do that we needed to have recursive proofs available in the browser so now with ultra Blanc we can do as I said before very efficient Care Tech hashes Dynamic array indexes uh in Noir circuits so you can have much more fancy for Loops for rlp encoding and these recursive proofs to bring it all together so trying to put this into a a snark still is not not the fastest um so we can look at kind of uh the raw

Even with Noir storage proofs are not slow…

amount of compute needed here um there are roughly five catcher caches per level of the tree um for the simple noun style circuit I think it can be up to around 16 in the worst case scenario if all of the um all of the branch nodes are full uh but for the the noun style contract uh it's not that not that larger tree uh because there's not many nouns holders at the moment so it's a bit smaller uh lots of rlb encoding every cache is rlb encoded before is hashed um and there's lots of hashes so that's a that's a kind of a large cost and yeah depending on on the activity in in the uh contract uh the tree can be anywhere between eight eight to 32

levels um for now's doubt it's around five to eight uh and for the uh crypto Punk example I think it's less than five um which we'll see in a second so even with this um we're still seeing circuits of around 800 000 constraints um and this is kind of an issue uh because the the the wasm limit in the browser is around 512 000 constraints just based on how much memory uh they're approving uh or the approval we use in the browser so um we had to make some some kind of adjustments here and the the end version of this uh will rely on the recursive uh proof construction we talked about

previously to actually get this working okay so what is recursion um recursion lets us verify a proof inside a proof um so instead of having to make a very large program um and kind of prove it all at once we can Chunk Up the program into smaller pieces um and layer them together to create arbitrary complex proofs so we still have to do the same amount of proving but we can um kind of split them into chunks and uh break down a larger program into something that can be proven uh in the background on a user's device and the key thing here is that we can prove it in the browser now so we can

What is Recursion?

break the complex storage proof down into thousand twelve thousand constraint chunks and verify those uh in in the browser inside one single recursor proof and for like ethereum uh this means we only have to pay one gas cost to verify one proof so we don't have to kind of verify each proof um individually on ethereum which will get very expensive we only have to pay for one verification a rough schematic of how uh how this could look um in this case if we have a small kind of uh local potassium try we can just do two proofs one which proves that the first four levels and one which proves

uh the next four levels and we can kind of recursively verify those together um in in one uh zero knowledge circuit and so depending on the size of the tree you may need more levels of recursive aggregation um but for for simple um storage proofs you can get away with two like this um we'll update this slide to actually have the relevant links to packages um but uh most of this work now is uh on on GitHub or npm um there's a storage proof Library written by the awesome Folks at Aragon which is could be used on the command line and it's being updated uh to work uh with the recursive Construction in

Relevant links to packages

the browser um you can also generate recursive Witnesses for proofs in the browser and that's now now working um and proving in the browser uh works with nextgs and you can prove kind of up to 512 000 constraints uh there's an npm package for that and we have examples of a recursion working in the browser which is being worked on as well uh do we have time to do a demo Sean yeah all right so I'll show my screen I'm just going to share them A terminal

Demo!

hope you guys can see this so this is this is first of all a typescript script which is going to basically use alchemy's API to get the proof I'm using alchemy's API because they bundle everything together it's quite nice they also give you the current storage hash as well and the default doesn't give you you should make an extra API call but yeah so I get this is the the address of the crypto pumps and then this is this storage slot were the first donor is basically stored so then I I'm writing all of these into a nargo proofer.com and that I will

improve so if I just run that script here so that will write the proof to our approval.com and if I go into what we're looking for here so it's gonna be this is our Noir um code that basically uses the library that Aragon have created which is the storage proof Library and takes in the proof from our prover.com and then basically constrains that storage proof is valid for this storage route that we've just requested from an ethereum node

so if I go into this terminal right here um I can run Margo proof demo and it will build the circuit and then construct a proof and then I can verify that's improve really quickly so this this takes around 20 seconds because it's constructing the proven key um of the circuit as well which takes up most of the time and then so that's verified well that's that's worked because there's no output so I can then run bye and this is now reconstructing the circuit to reconstruct the um

verification key and then it will verify the proof and this will take to do everything 18 seconds but the actual verify step is milliseconds yeah let's just run successfully um I can also just hop into the the proof a lot funnel as well so you can see what that looks like um whoops on file oh it's just gonna be in here isn't it true that's almost so this has the proof itself and then it's quite a large proof it's just an array of bytes and then the value that

we're proving so this is the ethereum address and then we have the storage that we're calculating against and if I run the script these this will regenerate these values which is Handy how many uh how many gates is this it's under the five twelve thousand right it's um um yes so this is a thing 434 000.

yeah so you'll be able to take this directly and and and use this in the browser without recursion but if you cross over the 512 000 um kind of limits uh kind of more popular contracts um or need to do more things in your in your circuit uh on the left-hand side here we've only got kind of a simple assertation that the storage proof is valid we're not doing any easy DSA or any other logic really um so depending on on how complex the program is you may need to split this out into two Bruce um and recursively verify them or you make it under the uh the limit to be in um I think that's everything so uh we'll

Outro

we'll link uh the kind of links uh in in the description of this when it gets posted and uh please join our Discord uh if you want to hack around with us and someone will be available to help you