Danno Ferrin 🛸 State Proofs and Transaction Verification

[Music] is everything cool with a and uh pick me up on the microphone Okay cool so I just want to say it's great to be back in Prague um five years ago I started my journey in crypto I'd started at consensus a couple weeks before they had a pegasus offsite the week after Devcon so it's kind of come in Full Circle for me to come and talk about um some of the things uh that uh on my mind about um censorship resistance so I'm going to talk about uh mind your own business State PRS and transaction verification and then what on Earth does this have to do with parallelism we'll get to that but first a little bit of context about what mind your business is and what I'm going after with that so this is a picture of something called the fujio scent the fujio scent was the first uh currency circulated by the US not the first currency minted by the US Mint but the first actually circulated currency and there's a lot of trivia and a lot of coin information that goes with that but what's interesting to me is this little logo this little model put on the bottom of mind your business it's something that Benjamin Franklin was really excited about you know and who was sharing with people that you should always mind your business and it's kind of a strange phrase it had a lot of different implication 200 300 years ago than it does today because when you hear the phrase mind your business usually what you think is mind your own business and that's what people tend to worry about when they talk about censorship is they're worried about cameras and the government and everyone looking into things that quite frankly don't matter to them and minding things that just really they shouldn't be caring about and then being invasive and looking into all those things and people want privacy in this regard so that what they do in private stays private so when you hear the phrase of mind your business you sometimes put in mind your own business saying stay out stay out this isn't you this is kind of an outside inl looking V of it and honestly the government is not the worst version of this mind your business situation I think surveillance capitalism is probably a bigger impact of this whole mind your own business situation where you got people who are build companies who are building these giant data centers to collect all of this data and to to combine it together and to figure out whether it's better to sell you an ad on a cookie or an ad on a car and they're using all this massive amount of information to do it but when I think of mind your business I actually think of a Netflix series called inventing Anna and there's a very pivotal scene in that where Anna this woman who's trying to uh do a confidence game on on high society in New York to to build her dreams for an art studio um keeps getting kicked out of hotels and keeps getting um you know she doesn't have the money but she's living like she has all sorts of money another character named nef is one of the conci one of the hotels that she's work living in and Ne is one of her closest friends if she has friends that really understands because these two they recognize people that have hustle in their life recognize people who are making things happen so when things are starting to collapse at the hotel that nef works at she she gets uh Anna to the side for a moment and she tells her mind your business and what she see saying there is something not about you know don't stay out of my business what she's saying is take care of your business you have bills to pay here you need to pay them because things are ending and I think that's really when we talk about mind your business we're talking about taking care of your business taking care of the things that you need to worry about being able to to uh pay your bills make sure that your checkbook balance is properly make sure that your bet is made make sure that your car is running properly and these are the things that we really need to worry about in a censorship resistance world it's it's like can I still do the things that I need to do and that's kind of the Counterpoint to privacy I need to worry about it do other people need to worry about it well I don't know if other people are going to worry about it but I I need to take care of my stuff so this brings us to the dark side of scalability which is kind of the direction on that things are starting to go this is this is a problem related to success it's probably one of the better things to happen to ethereum but it's still a problem so let's take an example of getting paid on chain let's say you're you're a box Packer or a barista or a high school teacher and in the future you've been moved to having your payments happen online if you want to prove that you've been paid if you want to prove that the contracts executed properly and that everything is there you either need to don't run the execution and just hope everyone's analysis of it runs or you need to execute it yourself and execute it yourself you need to run every previous transaction that leads up to that to prove that people had the balance and then when they had the balance they took the balance and then they paid you and all of the other various side effects of that so to calculate all this information and get all this this information it takes a rather beefy computer in the cloud to calculate all of this and and typically to run a node you need something like four cores 2 terabytes of hard disk 200 gbits of bandwidth and 300 iops and that's not something that a that a high school teacher is going to use their salary to spend on just to verify that they can get paid this is a problem for broader and wider adoption of crypto if we want people to fully participate in the censorship resistance and it's no more trer than then pinia who yesterday posted a post just yesterday and I'm just going to read what he said because or I don't know if it's a he or a she but what they said was very insightful into the problems that we're having with with these growing nodes they said the more transactions the network processes the higher everyone's Hardware requirements the more nodes in the network the more inefficient and slower it becomes or alternately you limit accessibility so very few people in very few places can run unsubsidized independent nodes effectively leading to a dystopia that is infinitely more centralized than traditional Finance and I like to call this censorship by wealth if you are not rich enough you cannot participate in the system and this is kind of the opposite of a lot of the enablement that we've been going for in ethereum to make sure that everyone at all different levels can participate in their Financial Freedom this is if if this goes unbounded it's going to be more effective than Banks ever could have done so how can we address this problem how can we solve this how can we make sure that you can mind your business in in the entire world economic system that having to process the world's economic systems that's where State proofs and transaction verifications come in state proofs are a witness of the block to say here's what was happening before and here's the data that you would need to prove it and transaction verification is actually running these blocks improving the verification we have there so instead of drinking from the fire hose while the while the world burns down it's a small drinking fountain in the park providing the uh the refreshing water that you need to run just your transactions in the airpl blocks typically these things include the minimum things like a header the block header um that you're verifying for the block the accounts that were read to or written from um read read from or written to the contract storage that was read from or written to any intermediate tree nodes that are needed to calculate the state route to prove that you have a consistent State the code that you need to execute and maybe in some situations we might need to include some prior block hates depending upon which operations you executed in and if all those things are in aate proof then you don't need those giant machines in the cloud you could verify this block with a phone that you keep in your pocket and I'm not even talking to high-end phone this could be like the $99 special that you get out of Google f with this sort of information you can verify your transactions occurred in a much more reasonable system there's a problem though is that we don't have it today and why don't we have it today the problem relates to our current merel Patricia tree our merel Patricia tree um if you seen the typical images of it you'll see a nice cute binary tree with maybe five levels and really small consistent proofs but the reality is these trees are 16 nodes wide they're often 30 layers deep and for for a block proof typically it takes up to a megabyte bad block proofs will take up to 2 megabytes so we can do this today but we can't do it in a way that can be efficiently be spread worldwide for transactions at scale and this is by the way at about you know 12 million blocks 12 million gas blocks 15 million gas blocks take more um 30 30 million gas blocks are going to take even more than that so this gets worse and worse the good news is there is a solution that we're working on to address this size problem and it goes by the name vertical trees there's even an EIP for it so we take these big 16 blocks and we compress them into witnesses to instead of needing 16 values to prove that your next step of the block is true you only need three you need to know where you are in the parent commitment you need to know what your value is you need to calculate a special little thing called proof I don't fully understand the math into it but I know that the side effect is it takes what used to take kilobytes into a matter of tens of bytes um so so veral trees are basically a tree of these Vector commitments to where and what's even better about this is um if you look at some of the details it fixes the side problem because rather than being 16 wide these things are 256 wide so we even make the tree shallower in addition to having smaller leaves you have less leaves and smaller leaves and we're packing everything into this tree that we need we're packing all of the account State we're packing the code we're packing um contract State and known State these things are going to be in the veral tree and they're going to be available and accessible um in a much smaller system and from this we can reasonably as part of the protocol with every block send out a proof and something that takes kilobytes instead of megabytes and this will allow us to scale we've almost made it we could almost do it today but what happens when we grow what happens when we have billion gas blocks what happens when we have transactions on the scale of visa on one chain and one network so this is where parallelism comes in and when people talk about parallelism this is kind of a topic on Twitter that people talk about but I think this is kind of the there's a stealth way that we can use parallelism to help solve these issues and when we talk about parallelism there's like three layers of of places we could put the parallelism and I think we've only really touched on one or two of them the first I term prefix parallelism this is where before you trans submit your transaction you put information into the transaction that you think might be useful for parallelism you might use access list to say hey I'm going to be accessing these storage slots and nothing else and systems can use that in their transaction to schedule so that you won't have conflicts and another version of parallelism that's been out for years is called sharding instead of doing everything in one block where we have a billion gas let's have a, one million blocks in split it up into smaller shards sharding is actually a parallelism solution when you look at it what people are working on today is what I term infix parallelism this is where you take parallelism into the execution of the block um stuff that Mo that um monad is working on there's so many m1s I want to call the modular but monad is working on a solution that they borrowed from DM um which then became appos in something called block STM where they're taking the execution of the block and they're using um optimistic concurrency control to just execute it in parallel and when things go wrong they reexecute it with a new information they've also introduced another interesting idea that I'll come to later in the talk called Delta writes instead of writing value goes from one to two just say value increases by one and that's a parallel uh that's a that's a parallel optimization that's something that's used in a lot of parallel systems to um make sure that the the impacts don't Collide but I think the most interesting area of parallelism can be apply on what I call postfix parallelism this is where you've executed the transaction and you know the details about the transaction and you apply information to your output to say here's how you can execute it in parallel so you might not you might notice which transactions conflict and you could put metadata into the transaction receipts to say these transactions conflict it must be done in a certain order and from this we can identify something that I'm calling a compatible transaction group where we have groups of transactions that can be included or removed and all the side effects will be the same regardless of how many of those that you um evaluate now I've been thinking about parallelism for a time and here's here's a tweet just from just July but I've had graphs for this parallelism stuff for years as Tim could attest to we had a little thing in in consensus we were thinking how could we parallelize this um and the problem is actually the database back four years ago why I didn't go into parallelism but it's interesting we should talk about databases because when you talk about database transactions there is a a famous acronym called acid which talks about got four characteristics that any database transaction needs and these database transactions are always done in parallel they're always distributed they're always done um with bunch of people at the same time the first concern is atomicity that what you do only succeeds or passes in one group the second is consistency the work that you're doing won't cause problems in the work someone else is doing this is important in issues like you know um in dat larger data collections to make sure that when you add to a map that you're not going to make the map have itself referential Loop the third is isolation and that your transaction only interacts with its own world and doesn't need to worry about anyone else and the final one is durability is this actually stored in the database but of these four principles I think the most important one to parallel transactions is that of isolation we can take our transactions we can isolate them from the other transactions in the block and if we isolate them we only need to carry about the transactions that you put in there and you don't care about the other 999,999 transactions in this million transaction block because you can identify the the consequences that come from this and as eth uh as as one of the repliers said you know what sounds like a topological sort problem kind of is so here's a simple seven transaction block you can see that some of them have dependencies and some of them cause dependencies um if we wanted to just worry about our transaction if we don't conflict with other transactions it's easy we can just alide the other six transactions from our block witness just evaluate our and be confident that our side effects will be seen gets more tricky though if we're Downstream from other people's transactions if we want to make sure that our side effects are consistent we need to see other people's side effects so this is what what a what a uh building parallelism into a um into what protocol would do is it might identify these conflicts you can efficiently get your transaction groups that you would need to evaluate to make sure that your is is true and another one we don't even need to to worry about other people as we go Downstream if there's a transaction that impacts multiple people you just carry about what your ancestors are and again if you're just the Upstream transaction you don't care what the side effects of the downstream are because um you're only concerned about your own side effects but I think the Holy Grail is the situation where yes you do have transactions that have changes before you but that you can um not care about them that you can get the the necessary information in the block to make sure that if you evaluate just your transaction that the side effect are going to be true and correct and everything that you evaluate to make sure that you can verify this transaction one of the steps towards this is an e proposed a couple months ago that brings in the sedit and S debit operations and this is basically bringing Delta rights into ethereum instead of writing that we're going to set block one from 100 to 200 we're going to say we're going to add 100 to block one and we're going to take a 100 out of block two so this allows us for a situation where like like to to allow us to prove more interesting things like say let's say Alice has 200 coins and there's three transactions that affect Alice 100 is sent to Bob 100 is sent to Christie and Dave sends her 300 so from that precondition that if Alice has at least 100 coins you can do any of the next three transactions in any order you can do any of the three transactions you feel like you can do all of them you can do one of them you can do two of them and all the side effects in those three transactions are all going to be the same this is the power that parallelism um postfix parallelism can provide for us in transaction verification if you can prove these ranges and also um saves a tiny bit of gas the gas golfers are going to love this so it might be easier to get this in than we think so from this we can Pro produce groups in in in the protocol of compatible transactions we can identify sets of transactions and here's my definition it's a set of transactions where you can um where you can have the sets the transactions in this set done in any order and also you can evaluate any subset of the transaction within it and the side effects of those transactions are all going to be the same so you can have some one or all and you can do them in any order and if it's in a in a compatible set then it doesn't matter what you do there now combine this with the ZK validity of the block proof we can alide almost all the other data out of the block proof and provide this to someone to say hey I paid you and here you can evaluate the transaction and here you can observe the side effects and with a feature like this this is going to allow us to mind your business mind all of your business and you only have to mind your business if that's the only thing you care about so uh again this is my vision for how transaction verification can really help resistance uh to censorship by well so that everyone on any device can verify that their transactions were part of the ethereum chain questions