ZK Podcast: Stateless validation with Alin Tomescu

Transcript

[Music] welcome to xero knowledge a podcast where we talk about the latest in zero knowledge research and the decentralized web the show is hosted by me anna and me frederick this week frederick and i chat with alin temescu a postdoc researcher at vmware and we talk all about the concept of stateless validators but before we start in i want to remind you about the next zk summit which is coming up november 23rd and 24th if you haven't yet bought your

ticket it's coming up fast so i suggest you do so quickly and actually this isn't the only awesome event coming up this week's sponsor parity technologies wanted me to let you know about another event you should definitely check out in the coming weeks that is polka dot decoded which is happening on december 3rd this free online event is the polkadot community conference and the first polkadot gathering since the multi-chain network's launch and decentralization it features a full program of talks exploring all aspects of polka dot by the teams that are actually building the network's core technology as well as those building ecosystem pair chains applications and cross network bridges get to learn the latest and future developments in the polkadot ecosystem and connect with the community

you can catch the fireside chat with polkadot founder gavin wood you can learn about the state of defy in polkadot and about polkadot's ethereum bitcoin bridges with snow fork and interlay you can dive into polka dots on chain governance and treasury and more you can check out the full program for polka dot decoded and register for free at decoded.polkadot.network i've added the link in the show notes so thank you again parity technologies now here's our interview with aline temescu this week we have alin tomesku a postdoc researcher at vmware here with us to talk about the concept of stateless validators welcome allen thank you anna and thank you frederick

for hosting me today it's a great pleasure to be here welcome to the show in this episode we want to revisit this concept of like state state full stateless and we want to understand a little bit about why this is an architecture that's even being proposed what the challenges are and where we are at in the research but i think before we kick that off i'm sort of curious your postdoc at vmware what is the work that you're actually doing there is it related to this yep so uh i started at vmware research in february 2020 right before the pandemic i got one good month

[Music] before all of this fun stuff happened and as i started there um i just continued working on my previous mit research and at mit i worked on vector commitments which is a type of authenticated data structure that takes a vector of n elements and represents it as a succinct commitment now this thing is very useful for stateless validation because if you look at a cryptocurrency like ethereum the state in ethereum is actually a vector it's a vector that maps position i to the balance of user i and the public key of user i so in a stateful validating system like the

current ethereum right now all the miners store this vector this mapping from user i to their public imbalance and the miners can check transactions against this state very easily and update the state very easily and in the stateless counterpart of the system what would happen is the miners would not store this vector which is really large it would be on the order of gigabytes they would instead store this succinct commitment of the vector and against this commitment of the vector they can now verify transactions if these transactions are augmented with proofs for each position so for example if i have a transaction from user i sending money to user j then i can include a proof

for user i's balance in the transaction and the miner can verify this proof against the vector commitment so that's kind of what i started doing at vmware research as i arrived the work you're doing at mit had that already put you in contact with like ethereum and the cryptocurrency ecosystem no it's kind of funny how i ended up being in contact with the ethereum folks it was right after the pandemic started i actually got sick and i was very you know depressed i'm like oh man what am i doing i'm sick i haven't done any work so i started writing this blog post about our previous vector commitment scheme and the ethereum folks apparently read it and found it

potentially of of interest and we started talking about that scheme and then we started thinking about some other schemes and we came up with this so-called aggregateable sub-vector commitment scheme which like i discussed earlier can be used for stateless validation cool so let's dig into the the topic at hand which is um stateless client stateless validation but i think to to get there we need to define something so you talk about vector commitments we did a whole episode on merkle trees which is a type of vector commitment and what the ethereum uses today um so i'd be curious maybe first we just talk about you know what what is states

exactly yes um but then also what's the problem right why we already have merkle trees why aren't they just enough like why do we need to do anything at all perfect and by the way if we're going to discuss what is state we kind of have to split into two types of discussions state for utxo based systems like bitcoin and state for account based systems like ethereum so that might sort of complicate the discussion a little bit we can handle it but just a heads up i think it's relevant to define the case for both though and i think that hopefully gives a good idea of what yes what we're talking about as well when we talk about states yes and in fact

you need different data structures because the states are different and some are easier and somewhere harder so yeah so i think the question we're trying to answer is how does validation work currently in cryptocurrencies like bitcoin and ethereum and how can it be improved in in some dimension in particular how can it be improved via so-called statelessness so what we're going to talk about is the current stateful validation of systems like bitcoin and ethereum when you get a transaction in these systems the miners rely on a bunch of data called state these databases that are stored on disk to check that the users transferring money from one another have enough money to transfer and to also after update these balances the new balances of the users

so we called we refer to this database as the state of the system and whether you're talking about bitcoin or ethereum you have different types of states so for example in bitcoin bitcoin operates in this so-called utxo model where the state is a bunch of so-called coins what is a coin well a coin is an amount comma a public key which means hey if you have the secret key corresponding to this public key you are allowed to transfer this coin to somebody else and create a new utxo or a bunch of other utxos that says amount new public key amount a new public key amount new public key and so on such that all of these new amounts

sum up to the original transfer amount so this is the utxo model it's just a bunch of utxos and then in systems like ethereum we have the account model which is simpler to think about in my mind and also has some advantages for smart contracts validations and the account model works as you map each user's public key to that user's balance and this is what determines a dictionary so a dictionary maps a public key to that user's balance and that's the state of ethereum so we have these two types of systems utxo systems account systems and they all have their own types of states and we understand now that when a transaction is validated the miner goes

checks that the users have enough balance and then update the state to reflect the new balance after the transfer and the question is can we do this without having the miners store this large amount of state for example could the miners succinctly represent the state as a digest or as a commitment and get proofs that users have enough balance with respect to this commitment of the state and by verifying the proof the miner can be sure the user that's transferring the amount of coins actually has those coins and then after the proof is verified the miner can update the state by updating the digest rather than the full database stored on disk

and that's kind of the core idea one way that i feel like we've in the past discussed state we all we mainly discussed it in the context of an account based system and what i always understood it as is it was like the snapshot of now like the history the background isn't necessarily it's it's in there somewhere but like it's what you have in the state is the current connection between like you said the public key and the balance good i think yes and that's implicit in everything i've been saying and perhaps that should be clarified so the way and you touch upon a really good point which is you kind of got the reverse of it so it's not like you get the history

from the state but you do get the state from the history if you start with the history of all transactions at the end what you get is the balances of all users in the account model or in the utxo model you get the the utxos of each public key you know how many coins does each person die i have a bunch of etxo maybe each one has a different public key so you get that after applying gold transactions so yes i think that would be very useful to clarify there's a history of transactions and then there's sort of a computation being done on these transactions like each transaction is being applied to the null state initially and the state evolves over time and it ends up being what it ends up being a mapping from public key to coins associated with that public key

whether it's utxor account at a high level that's what's happening is this is the amount of coins and this is the public key that can spend those coins and the way you authorize such a spending is by doing a digital signature with the secret key associated with the public key one other distinction that i kind of want to make or clarification is around the concept of like a stateless client because we've heard the term stateless client but as i kind of understand it doesn't necessarily in this conversation we're going to be talking about stateless validation and stateless client can mean something else so what is a stateless client yeah so i suspect what people mean by stateless client are these thin clients that you can run on your

mobile phone on devices that don't have enough storage to store the entire bitcoin state and so in systems like bitcoin you can already run a bitcoin wallet which is a thin client which is a stateless client if you want and you can send transactions and you can receive transactions and you can manage your bitcoins there very easily now i will say the the same thing is possible in ethereum of course because ethereum uses markle trees and each balance of each user has a path in that merkle tree and the next thing the next point i want to make is that if you have a stateless validation system that allows miners to verify

transactions statelessly that immediately implies a stateless client or a thin client because what's a stateless client well it's a subset of a validator it just needs to validate its own transactions broadly speaking in this case like a light client is a light client a stateless client or yeah so i mean this is where i think i don't really know what bitcoin's terminology is as well as i maybe should but in the ethereum world when people talk about stateless clients they really talk about making the blockchain stateless like having stateless validation having stateless signers in some way because it otherwise you call it a like client because that is like what you just described as a like clients where you don't actually have

any state by you request state like if i want to know what what this smart contract holds i request that states with its accompanying merkle proof from a full node um and that's just like altruistic behavior on the full nodes to actually provide that i don't know what people talk about in in bitcoin world if they talk about stateless clients or think clients or like clients or whatever but good um that that that is a confusion that i have seen is is like like client stateless clients whatever um but here we're gonna talk about like the full picture of it like actually doing it for miners okay that's a very eye-opening for me because i i think you're right actually the ethereum

folks have been using the stateless client terminology to mean stateless validation and at the end of the day it seems like here we're just talking about terminology so when i think of a of client i i think of an end user running a software on their device and from my perspective a miner is not a client because they're not really an end user well they are but that's not what people think about their they they achieve their own goals they mine coins so they are some sort of user but the end users of a cryptocurrency in my mind would be the people transferring money miners are sort of a facilitator for that goal right so in that sense i think of a client as the stuff running on the wallets and then if you're going to tell me what is a stateless client i'm going to

say well it's a client that runs on your mobile phone and lets you manage your coins it seems that that previous terminology is not consistent with that so that's good to clarify yeah totally so before we go into like even further into the stateless system the stateless validation i do want to touch on something you said just before which is this idea of the history defines the state but like as i understand it like the state also because it has all of this history it ends up being big or heavy like there's something about the current systems where even though it's it's sort of a snapshot it carries with it a lot of i don't know what you call this is it

storage data it's information stuff information it's it's stored in these merkle trees which are meant to kind of compress that down but yet there's still i guess a lot that you have to download a lot that you have to to have present in order to calculate this yes i think it actually i mean this goes to to what i was talking about with what is that problem actually because i don't know maybe it's my personal opinion but i don't think storage is actually the problem like if you look at the size of the bitcoin state that's actually very small compared to the history yes and so what we want to try to do is actually well there's a couple of things we want to do and

uh ellen maybe you can actually help us get into that but part of it is compensation part of it is actually not having to deal with that history like avoiding the history by going stateless because then you don't need the history to rebuild the state all the time right so eline what would you say is like the main problem that we're trying to to solve by introducing stateless validators okay good good so that really touches on on the core issue and and i'm not sure whose question to answer so i'm gonna just answer the letter the last question that's good so so what problem does stateless validation pretend to solve and uh it depends on who you ask in my

mind the key advantage of stateless validation is that when you want to scale cryptocurrencies like ethereum you usually think of scaling them by sharding the cryptocurrency and when you start the cryptocurrency what you do is you split up the state into let's say a bunch of so-called shards and when you do that each chart has its own set of validators and as a result you lessen the security of the system when you split up the validators among the shards because if you compromise one shard it's much easier to compromise one short because it has n over the number of shards validators if you had originally n validators right

so now what you want to do to deal with that is you want to switch validators between shards periodically with some frequency but in order to do that when a validator switches it has to download the state of the chart it switches to so now we can immediately see how the size of the state becomes problematic because it affects the speed at which validators can switch shards and it lessens the security of a sharded consensus protocol is this even the case in like the eth 2 setup where yes it's sharded but there is sort of this real what do they call beacon chain yeah the beacon chain is just responsible for for doing that shifting of validators around right so the same problem exists still that's actually a very good point though i

haven't really thought of that point to be able to switch validators more often when we've talked about stateless clients or stateless validation in the past we've approached it from looking at a full node a full node has two modes that it can operate in either it's syncing or it's synced and keeping up with the network and like validating blocks when it's sinking sinking in ethereum if you just normal sync an ethereum node it takes i don't know how long anymore weeks something like that right what is happening then is you're downloading all the transactions and re-executing everything so every transaction you're reading

something from your hard drive doing some computation writing something new to your hard drive and you keep doing that for millions of transactions in a row and that's why it takes weeks to do so if we can just say okay we're going to have a stateless client you don't need to do any of that right you just need to sync the header chain which is really fast you get the merkle roots and then you get to say here's the correct state for this merkle root and or like here's you know a quick transaction whatever right the other problem is for miners so in the second mode where you have synced and you're now operating what a miner does is downloads all of or they have all of his transactions in a mempool and then they construct a block and execute that

and then you know try to do that as fast as possible so they can start mining on top of it and currently it takes like 200 milliseconds or something to create a block to minor and there's a scaling problem in that too that you don't want this time to be too long because then it takes away from the mining time and therefore like lessens the security to some degree but the question there that i have is if stateless mining is to address this then getting the proofs and validating the proofs has to be faster yes than one disk read and one disk writes and the computation in between right and it's sort of up in the air to me if that

is actually faster or not oh yes but then the third point that you just brought up of actually being able to both sing quickly and like stay up to date with the the chain and because you're hopping chains all the time this now becomes exponentially much more important and there's two things i want to touch upon from what you said the first thing was you said that to sync in ethereum you have to download the history of transactions execute them and get the state but i suppose that's the slowest way to sync in ethereum because the faster way would be you get the latest merkel route and you download the state directly and you don't care about the transactions and that's what we call warp sync right but and i don't see a fundamental reason

why you would ever want to do the slow sync if you're willing to buy that the consensus in ethereum is secure then you can download you know the merkel route from let's say two days ago if you want to have more security you download the state which is going to be faster and then you apply the new transactions from the last two days so that would be a faster way to sync ethereum but note that you still have to download the state and ethereum which when you account for smart contracts it's my understanding is that it's on the order of 100 gigabytes the state not the transactions no the state is more like well when you account for smart contracts i don't know it was uh it was a year since i last just checked uh a year ago was more like 15 gigs so i doubt it's up to 100 but it's so

large it's still like a sizable download that is problematic for most people okay so all i'm trying to say is that there are faster ways to sync in ethereum right now and those ways leverage authenticated data structures like merkle trees which are just an example of authenticated dictionaries and with stateless validation you can further improve that sync time because now you no longer have to download the state because the validation never actually needs the state so you want to add a new peer-to-peer node to ethereum just spawn it up it downloads a single 32 byte commitment of the state and it starts validating without spending time downloading gigabytes of data so so stateless validation or stateless mining as you refer to it

could help with that and the second point you made about the computation uh speed of validating statelessly versus the computational speed of validating statefully by going to the disk that's really the key open problem in the space in the sense that nobody has spent time to implement these systems and look at the trade-offs and i would love to work on this in the future because you know i have for example italia ram one of my collaborators yes and has been on the show before so given that i love working on authenticated data structures and i love working on consensus we could actually potentially work on this together in the future and explore the trade-offs better but nobody has so far and frederick you

bring up a good point is validating statelessly slower than going to disk and it may as well be but even so it's not clear because of the point that you brought up that it's going to be sufficiently slow not to give you advantages when you shard things so what you're saying is it might actually be slower than what exists today that is like the state plus merkle trees but once you introduce sharding it potentially could speed it up is it actually about speed or does it become less complicated um i think it's just about scaling the sharded consensus so it's about speed okay and yes that may well be true what you're saying and that's really what the research

uh community and and that's probably what the ethereum theme is already working on finding out something that comes up again and again when talking about stateless client stateless validation though is data availability who actually distributes this state if i want to send some tokens to someone or interact with a smart contract i need to know what that is i need to download some state from somewhere so that i can interact with that state so how do i do that good good so there's a few ways i want to answer this question if you just consider payment only cryptocurrencies there's less of a data availability problem there because each user stores its balance and

it's proof for its balance so the state is perfectly distributed amongst the users themselves and users have incentive to store this constant size information and the other data availability problem that arises in payment only cryptocurrencies would be that well you might want to store the history of transactions over time somewhere and you know potentially we need an incentive mechanism for this i'm not as concerned about it there's no incentive mechanism to store this data in bitcoin right now and people seem to store it anyway but the problem does get worse when you switch to data availability for smart contracts totally but actually before we get there i also want to say that in payment only cryptocurrencies

that are statelessly validated you also have the problem that users have to keep these proofs updated all the time and users would ideally not like to do that because for them to do that they have to keep up with every new transaction in the system and apply it to their proof and update their proof so they have to do a lot of work and a lot of communication and to solve that problem you have to introduce these proof serving nodes that actually maintain all proofs for all users or a subset of proofs for a subset of the users and those again have a data ability problem like why should these nodes do the computation and there's a very interesting incentivization question for that and we have some work on that actually that hopefully will release

soon on how to incentivize these proof serving notes properly i also think of that as a data availability problem now switching to smart contracts so in smart contracts when you think about validating statelessly the question is i have a smart contract a who stores the state for that smart contract a and one simple answer is to say well a smart contract is deployed by a person and it's that person's responsibility to store the state of that smart contract now that's not very appealing because that kind of takes away from the decentralized nature of a cryptocurrency right so again i i think this is yet to be explored in future work because i think we only have one or two papers on stateless validation for cryptocurrencies um so there's the point proof paper by

gorbanov who explores stateless validation with smart contracts and they have a very nice vector commitment scheme for that and there's a new eprint out by shashank agrawal and srini raguraman on authenticated dictionaries from rsa that are very amenable to stateless validation but none of these two papers explore sort of the intricacies of who stores the contract state and how do you incentivize that storage and i know the ethereum folks have been doing a lot of work on this if you go on earth research you can see a lot of fraught proofs availability proofs and so on and i don't have a satisfying answer to this problem yet i think it's something

that we have to look at in future work and so far we've barely started to come up with the right authentic data structures for the problem and the next step will be like we discussed earlier making sure that this makes sense in an implementation and then incentivizing the distribution of the data but yet they're all intertwined because if you don't have one you can't get the other so it's just people end up working on what they want to work on leading into what you talked about with authenticated data structures i want to lead into it with another problem which i think we can solve that is when talking about stateless mining or validation whatever we call it on ethereum either one specifically when we start

digging into these schemes we find that if you could have a stateless system on eth1 where you only provide the miner with the merkle root and then a merkle proof of your transactions and they can just validate that proof and move on with their lives they don't actually have to keep this they don't have to do any of this work the problem with that is it would require an insane amount of bandwidth because these proofs are so large yes so how do we solve that problem well that's the great question that's exactly what we're doing frederick what we're doing is we're coming up with better merkle trees where the proofs are smaller and it's not just that they're smaller

they can also be aggregated so when you have a bunch of transactions each one with their proofs in them you can take all of these proofs which cause most of the overhead and compress them into a single one so we did work on this with the ethereum folks themselves that's our asvc paper from scn20 where we build a merkle tree which is you know it's not a miracle tree but you can think of it as a miracle tree in the sense that it commits to a vector but it has this nice property that if you have a bunch of proofs you can aggregate them into a single one and then most recently we built a stronger primitive called an authenticated dictionary which again you can think of it as a miracle tree and if you have a bunch of proofs you can compress them into a single proof

and not only that if you have a bunch of proofs with respect to different merkle trees perhaps you have a different merkle tree for smart contracts memory you can take all of these proofs that are each for the execution of a different smart contract and compress them into a single proof and this kind of i guess nicely gets us to talk about the difference between a vector commitment and an authenticated dictionary so what's the difference i i think it would be a good point to clarify that so in a vector commitment scheme the data the state or whatever you want to call it that you're authenticating is a vector it's a list of n positions that has a value vi at position i and this can be sufficient for things like

representing the balances of all users in the system if you have end users and you represent that as a vector but it's not as good for representing smart contracts because in a smart contract in ethereum at least you have memory addresses from 0 up to 2 to the power of 256 and you can't have vectors that are this large because by the time you finish creating these vectors the universe is going to die so you need a different authenticated data structure for that and that's what the dictionary is for a dictionary maps a key from a really large universe so a key of 256 bits for example just like the memory locations in the ethereum smart contracts to its value so to the value stored at the memory location and

you need now an authenticated dictionary in order to commit the memory of such a smart contract with a really sparse memory with indices from 0 to 2 to the 256 and it turns out that obtaining vector commitments and authenticated dictionaries are authenticated dictionaries are a bit more difficult there are sort of constructions that use vector commitments to get authenticated dictionaries but they lose something in the process so coming up with authenticated dictionaries that are inherently super efficient is a bit harder than coming up with a vector commitment it seems as far as we can tell that's not the case in merkle trees though if you use merkle trees as your authentication data structure let's say whether you're committing to a vector or a dictionary

you can organize the merkle tree very easily to get both efficiently but when you start switching to different primitives like bilinear accumulators or constant size polynomial commitments or you know hidden order groups it's not as easy to organize the data structure to get either a vector or a dictionary you have to do crazier tricks and it gets more difficult and that's what's exciting actually about this field is what kind of clever mathematical things can you come up with that allows you to represent a vector using these more fancy cryptographic primitives not merkle trees can i ask you a question that might even be a little bit of a step back from this yes like we did an episode with ben fish on accumulators generally and i'm just curious like when

you talk about an authenticated dictionary is that instead of an accumulator or is it using is it like mapping throughout an accumulator oh this is this i love this question actually and the reason i love it is because we actually haven't defined what an accumulator is so we talked about vectors and vector commitments we talked about dictionaries yeah and authenticated dictionaries yes if we talk about sets then we're talking about accumulators so an accumulator is just a commitment to a set just like a vector commitment is a commitment to a vector an authenticated dictionary is a commitment to a dictionary right so accumulators are useful for committing to sets now why might you want to do that well it turns out in systems like

bitcoin the state is actually just a set it's the set of all utxos and when you do a transactions you remove on utxo from the set and you add some new ones and in order to actually turn bitcoin to be stateless all you need is an accumulator that has some some properties like given the accumulator commitment the commitment the small thing not the full set can you remove something from it and can you add something to it right and it turns out you can do these things and that's what ben fish's paper is about well i think in that interview though we also talked about merkle trees falling into the category of accumulators that is the case of course so that's why merkel trees are so interesting because you can use them

to come into a set you can use them to come into a vector or to a dictionary or to all sorts of other fancy things so so merkle trees are much more powerful than some might realize then they've been around since 87 i want to say and you can do all sorts of crazy stuff with merkle trees and organize them in all sorts of fancy ways i really like the way you defined those three things and you were saying like merkel trees are almost like the technique in these yes yes that's really important to understand there's a researcher at the mit digital currency initiative page some of you know him and he has this really beautiful paper on building accumulators from merkle trees that are much more efficient than what you might normally come up with and again he comes up with a way to

commit to a set using merkle trees but his construction has this advantage that you can remove and add things to the set very easily unlike other merkle based constructions which have more overheads and i think that's the perfect example of the really amazing power of merkle trees and what you can do with them now and actually that scheme is really good for bitcoin stateless validation it's unclear whether you might want to use actual rsa accumulators or bilinear accumulators instead of pages scheme because stage schemas has very small proofs in practice and it's also so efficient to execute by the miners which might uh make up for the fact that the proofs will be slightly larger than a bilinear accumulator says but yes coming up to the merkle tree point merklizing something is just a

technique you know there's people that localize code executions what's that what's that about right it's and i'm we've just talked about three different kinds of data or sets uh dictionaries and vector commitments which are useful for turning stateful systems like bitcoin and ethereum into stateless ones and there's these all of these things are related so for example we have a paper on using accumulators so commitments to sets to get dictionaries to get authenticated dictionaries from just an accumulator and mostly the use of the accumulator is black box in the sense that we don't need to change much about the accumulator so so there are interesting connections and there's some connections like i said earlier between vector commitments and dictionaries you can get one from the others for example

bankrupt feist that ethereum research has a post they're on building he calls them hash maps in other words authenticated dictionaries map dictionaries same thing where he uses a vector commitment in a pretty much black box way to get an authenticated dictionary which can be used for stateless validation so yes it's just a beautiful space i think it's fascinating how these all these different terms come up because it it seems like such a mix of math and computer science where like it's vector commitment versus accumulator versus authenticated well you could just call an accumulator an authenticated set and a vector commitment an authenticated vector yes and i guess that's why like in computer science now it's talked more

about like authenticated data structures generally instead of like all of these individual things yeah broadly speaking this yes good so you touch upon a great point i'm actually having a lot of trouble tagging my papers in my bibliography with the right tags why should i use the accumulator here is this under authenticated data structures or not this is should i call it a set instead of an accumulator i don't know but you're right that's what we're best at right coming up with the same name for different things and then publishing a new paper uh be wary be wary of that researcher technique i have a question sort of following up on the merkel like we just talked about sort of the glorious markle trees but there are also like variations or

evolutions like there are other things you could use in your modeling are you also looking at other techniques for stateless validation yeah beyond authenticated data structures you sort of mentioned that merkle trees do exist in there but i mean there were these ideas like merkel mountains i don't know if that just falls under the accumulator side but are there other techniques like merkle trees but that are not merkle trees that you're actually experimenting with in there so merkel mountain range is a merkle tree technique there's nothing inherently different about it i see it just sort of falls under that category yeah in my mind i mean i don't see a need to differentiate between that so what you're doing is you have a bunch of leaves and you marcalize them up but you stop and you stop at some point and you get

multiple trees when do you stop you stop when well you really you marcalize up in powers of two you get the biggest power of two uh of your data and you mercalyze up and then you move on to the next power of two in terms of other techniques i guess that's what we're trying to do right so we're coming up with uh techniques that use algebraic groups rather than merkle trees so we have prime order algebraic groups which gives give rise to polynomial commitments which give rise to vector commitments then we have hidden order groups which give rise to rsa accumulators which give rise to dictionaries or they give rise to vector commitments for example the catalan or fiora vector commitment which can be turned in a non-black box way into a dictionary

which is what we show in our in our latest work and also what the paper i mentioned earlier by uh shashank agrawal and shinira guraman also shows so yes there's a bunch of alternatives to merkel techniques and actually that's what makes the space exciting because these alternatives they give you much more power so with hidden order groups for example you can aggregate proofs which you cannot do in merkle trees efficiently in principle you can do it in merkle trees with snarks and maybe you can replace the hash function with something that's more snack friendly and you can get some amount of efficiency but good luck beating the efficiency of the rsa-based aggregation for example with hidden or groups you also get incremental aggregation which means that as you have n proofs that you've aggregated into a single one if you get

an n plus one proof you can incrementally accumulate it in the previous aggregation rather than restarting the aggregation from scratch and there's all sorts of other crazy properties that these things give you that merkle trees would never do update ability is one of them for example in a merkle tree if you want to update the proof for position i let's say it's a vector commitment built using a miracle tree so you have a position i and a proof for position i in other words a merkle proof and position j changed by some delta and now you want to update your proof for position i you can't just update it you also need as auxiliary information you need the proof for the position j that changed this is kind of annoying in the stateless setting because if i'm user i and i'm sending money to user j i need

to include user js proof in the transaction for the miners to update the state and for other users to update their proof so with these techniques you can you can do that without this auxiliary information you can just update the digest this is actually so helpful to understand a little bit more at least for me it's helping me to really position the exact research that you're doing or at least part of it i didn't fully get that i didn't get that from our early just like earlier in this conversation that it's actually like it is the replacement of the merkle tree that these authenticated dictionaries could provide yes and the stateless validation requires something more efficient or some

technique that is different from the merkle trees but has some of the same properties or outcomes yeah so i would say i just gave a talk about this yesterday actually that the simplest way to understand why we need to move beyond merkle trees is to realize that when you move to stateless validation there's a few key operations that you must be able to do you must be able to update the commitment of the state whether it's a vector commitment an accumulator or a authenticated dictionary you have to update on the miner side because the miner gets new transactions has an old commitment needs to compute the new commitment to reflect those new transactions so with merkle trees you need that auxiliary information earlier that i that i mentioned earlier you need those proofs for the changed

positions in the state for example and if you move beyond merkle trees you realize you can come up with constructions that you don't need that auxiliary information and as a result you decrease transaction size and you decrease block size too because that auxiliary information no longer needs to be included in the blocks and another key thing that merkle trees don't give you and i mentioned before and is necessary in stateless validation is proof aggregation because once again we have the miner he has a commitment of the state and he gets proofs in a bunch of different transactions but now this miner has to create a block after validating those transactions and verifying those proofs and he would normally need to re-include those proofs in the block why because other miners need to validate

this proposed block so they need the proofs so it's really important for the miner to be able to aggregate these proofs into a single thing so that the block size stays small imagine having a thousand transactions in a block and also having to include a thousand proofs versus including a single proof so proof aggregation is very important now can you get profibulation from our countries yes you can is it efficient not so much can we come up with better data structures that have more efficient propagation turns out we can they have other disadvantages like we touched upon earlier the validation of the proofs might be slower than than validating from the state on disk nonetheless the sharded consensus that it's made possible by these newer data structures could still be faster than than doing stateful

validation and doing expensive state transfer in the shredded consensus protocol and this is future work to be done this is actually suggested that i we asked this from itai i spoke to him about the fact that we're having you on he said we should ask you like how do polynomial commitments relate to the work and you did mention them when you were defining some of the different things but our polynomial commitments is that part of the tool set that you're using for the authenticated dictionaries are they related somehow yes the answer is the answer is they are definitely part of the tool set i can point you to three papers one by chipotle papamantu and zhang who use multivariate polynomial commitments to

build vector commitments and we will put those in the show notes for our listeners because so that they can also check those out another paper is our paper on authenticated multi-point evaluation trees which use univariate polynomial commitments to get vector commitments then we have our asvc paper which also use univariate polynomial quantities to get vector commitments they're absolutely relevant the question is why and to answer that question i'm trying to think if there is a an acceptable answer like a useful answer to that question without people understanding what a polynomial is yeah because if you don't understand what a polynomial is how can you understand what a polynomial commitment is so let's i guess first talk about what is a polynomial broadly speaking

and then we can talk about what a commitment to this polynomial is and how that lets you come up with a vector commitment for example or an authenticated dictionary that sounds good so we can really quickly define a polynomial as a function f that takes some input x and outputs some value y so f of x is equal to y for a bunch of different x's and it turns out that this function f is not just any function it has to have a particular form so for example polynomials that you might have seen in the past are f of x is equal to x plus 3. another one you might have seen is is equal to x squared plus x plus five in general you have f of x being equal

to coefficient c i times x to the i plus coefficient i minus one times x to the i minus one for a bunch of different coefficients ci that you pick and that's a polynomial it's just a mathematical object it's a function why is it useful well you could in principle come up with a way to represent a vector as a polynomial if you could for example come up with a polynomial f such that f of i is equal to the i position of the vector let's call this vi i can maybe come up with a way to compute a polynomial f such that f of i is equal to v i that seems plausible mathematically it turns out there is a way it's called

lagrange interpolation and you get a polynomial that has n of those coefficients c i if you have n positions in the vector i might be off by plus or minus one you know that's acceptable i'm having by the way flashbacks i'm having flashbacks to our interview with ariel gavison because he for sure talked through exactly this summer i remember this all so i might be off by plus or minus one but that's acceptable for computer scientists and uh you have a you have this polynomial now it has n coefficients so it's just a list of n numbers that's what the polynomial is and you can also represent it as you know x to the 4 plus x to the 3 plus whatever the representation follows immediately from this list of coefficients

and now i have this polynomial f of i is equal to v i it represents the vector unambiguously if i put a vector position in f it gives me the value of the vector but i haven't gotten anywhere like what i need to do is to come up with a succinct representation of this polynomial which would give me a succinct representation of the vector and then i need to come up with a way to prove that position i has vi there relative to this succinct representation so if i give you the commitment to the polynomial the succinct representation how do i convince you that i has value vi i have to give you some sort of proof that you can verify with respect to to the representation and that's what a polynomial commitment

scheme does it defines two things it defines a way to compute this commitment of the polynomial and it defines a way to prove that the polynomial has a certain value at a certain input so that f of i is equal to vi and that naturally gives you a vector commitment how you take the vector you do lagrange interpolation you get an f polynomial of of n coefficients then you commit to it using the polynomial commitment scheme and then you pre-compute all proofs for all n positions in the vector by computing each individual proof for f of i is equal to v i with respect to the polynomial commitment so you've defined the polynomial commitment is that the core

of what you are doing in order to i don't know if i'm going to say this correctly but map those connections between the key and the balance like going back to that original concept of the like what you're working on with the authenticated dictionary like how do those two things relate well um good so i can use a polynomial content to get a vector commitment and earlier on i claimed that if you look at a cryptocurrency like ethereum the state of ethereum can be represented as a vector because i can take each user i a user is a number from one to n let's say and i can map that user i to its public key and its balance and that defines my vector and then i can commit to this

vector using the polynomial commitment scheme and pre-compute all proofs for each user and that is what our asvc paper does joint work with the ethereum folks and i have to say this is not a new idea this is an idea that's been around since 2010 but what our paper shows is that you can also update this vector commitment very efficiently you can have a way to update the digest efficiently and most importantly something that wasn't well known before and we show is you can update the proofs for position i after position j changed efficiently without needing this auxiliary information and you can also aggregate the proofs for a bunch of different positions i what are the proofs themselves like you keep mentioning proof

proofs and we know there's your knowledge proofs but like what kind of proof are these good so i you know i could go uh i would love is that all is that a whole lot of excruciating detail uh maybe on the highest what are the proofs so the highest level i can give you is that the proofs are actually polynomial commitments themselves so a proof for the evaluation of f of i being vi is just a commitment to another polynomial and i can actually tell you what this polynomial is so i have my f polynomial that represents the vector imagine i divided this polynomial by x minus i which is another polynomial now how do you do this division you know that's like you've learned that

in one through eighth grade but you forgot it yeah and you know it's it's fine we all forget it because we don't use it it's normal but there's a way to do this division and it gives you a quotient and a remainder just like when you divide 5 by 2 you get quotient 2 and remainder 1. when you divide f by x minus i you get some quotient polynomial and some remainder polynomial the remainder it turns out it's actually the value f of i it's actually that and the quotient is some polynomial of degree n minus one and i'm actually off by one i now realize so the degree the degree of f is n minus 1 and the quotient is of degree n minus 2. so you get this other polynomial let's call it q quotient polynomial and now you commit

to this polynomial and that's the proof for a position i and this is beautifully explained in a lot of different papers i think one way one paper that explains it clearly is the kate zaverucha goldberg polynomial commitment paper kcg10 and all papers that sort of build upon this usually explain this clearly and you can also see my blog post about how this works i have some blog posts on my website about kcg itself the polynomial commitment scheme and about how we use it to build asvcs for example so i hope that kind of for me at least that's awesome yeah uh kind of a left field question but on

theme for the podcast is have you looked at their knowledge proofs and specifically in a stateless validation system it is a kind of an obvious thing that instead of just sending a transaction you send a transaction and the proof that it's correct yes you could do that but i mean that's what actually let me just say that that's exactly what we're doing yeah that's what you're doing even in f1 you're sending a proof that the transaction is valid it's a merkle proof and the miner has to validate it zero knowledge has nothing to do with it if you think about it why does it need to be zero knowledge who cares there's no need to hide anything so far in f1 and in f2 like if you're talking about zcash then you can talk about your knowledge when

you actually want to add things but actually what you want is you just want the proof is it a proof of knowledge not really not really it's just a proof so it's not even a snark it's just a proof yeah the reason i ask is it usually comes up in the context of talking about zero knowledge proofs as a compression mechanism where if you have a snark it's actually really tiny and especially compared to a merkle proof which is massive so that like as you have worked on your stuff have you compared it to you know what what if we used as an arc what are the differences in size good thing good so our asvc proofs are just 32 bytes

so much smaller than a snark i see um and i think that that should basically fully cover the question so you could do it with snarks in principle because you could have the data and you could prove with the snark that this is one of the elements in the data and the data could be anything a set a dictionary a vector like we talked before but why do all of that stuff when we have better ways more efficient to compute all proofs for example using uh vector commitments using polynomial commitments as an underlying building block i just wonder i mean alina i don't know if you're familiar with the system but it sort of reminds me it makes me think a little bit more about like the codas what used to be coda what is now mina

like they're also a proof of stake system they also use they do use like recursive snarks but i don't know about their validation part do you kind of know what i mean like i don't know if however they do use snarks uh for for stateless validation but block validators do not store the full state in the system but block proposers who propose and create new blocks have to so imagine the validated role usually the proposer and the validator role can be split up in bitcoin and ethereum it's kind of the same entity doing both yeah i guess in coda it's the same entity it's different entities so there's one entity who just validates block and there's other entities who propose blocks and those entities have to store

that state to propose blocks because they have to build these snarks that reason about the state roughly speaking we should call them they're they've changed their name they're mina so we should mention that actually they're called mina so i had a name change this is in stark contrast to to to stateless validation where even the proposers themselves don't store the state this is why i mentioned earlier that you need to be able to update the digest without auxiliary information because the updated digest will be in the new proposed block and you need to include proofs for all the transactions in the new block and aggregate those proofs and you can do all of this statelessly although in mina you cannot do this without state it seems uh but it doesn't maybe it's not

inherent maybe there's a way to do it in mina as well with recursive snarks yeah it seems like being able to update these proofs is really the the key because otherwise uh yeah like having to recompute that whole list of proofs for every user of a chain would be massive like it just wouldn't work yeah i mean assuming that we get the systems to this kind of scale that we want um yes so yeah that does seem like the key i completely agree and this kind of touches upon some differences in current let's focus on vector commitments construction so there are vector commitments like merkle trees which have lock-sized proofs which means

that when something changes you update a path in the tree and all other proofs are implicitly updated so you can do very quick updates of all proofs if you are for example a proof serving node in a stateless cryptocurrency managing this merkle tree but more cultures have other disadvantages as we discussed before then we have vector commitments from polynomial commitments such as our asvc scheme which have constant sized proofs now constant size proofs immediately implies that if something changes in the vector you have to do order and work to update all constant sized proofs whereas merkle trees because they have lock-sized proofs that intersect within a tree it's much easier to update all proofs and log in time so an open problem that vitalik buterin

actually pointed out on earth research i think in a post called an ideal vector commitment scheme is a vector commitment scheme that must inherently have non-constant size proofs that proofs are that such proofs are aggregateable and the data structure that defining the proofs potentially in a tree-like fashion is updatable efficiently so that all proofs can be updated in say logarithmic time and this is something we're working towards as well independently this leads into a question that that i had which was about like the open problems but also like what are the challenges in actually building this thing like would you say that the state of the research is such that there is a solution or would you say that we're talking like

30 in there's still like quite a road before stateless validation can be implemented uh my hunch is that we're in a state where there's enough room to innovate more on the authenticated data structure side to help inform the design of the stateless validation system and we could start prototyping some stateless validations designs including the consensus layer now with the work we have but i think there's more room for improvement so for example the open problem that i highlighted earlier and in principle maybe it's not necessary to solve this open problem maybe computing all in proofs periodically with our in this construction that has constant size

proof is fast enough if you do it periodically rather than all the time but that yet remains to be explored in future work so yeah my hunch is that uh we have more room to innovate before we finalize the design and that's informed also by some of the things we're working on yet that are yet to be revealed where we're coming up with ways to incentivize some actors in a stateless system which changes things a little bit one of the things i think we didn't quite cover yet on this show and in these questions though was say stateless validation is at a state where it can be implemented what does that actually mean for the

users of that system like what changes we talked about size we talked about like what would that mean what does that mean i love this i love this question i'm surprised we haven't said it yet yeah so in some sense it's kind of subtle i think what it means so one one implication of stateless validation that we touched upon earlier is that it immediately implies a thin client for your thin devices like your mobile phone like a small not heavy something that a lot of very unpowerful devices could still run yes and that's already the case in cryptocurrencies like ethereum and bitcoin but the current thin clients running on mobile phones for these cryptocurrencies

make some trust assumptions and users are not aware of that they probably just trust and you know they assume everything works so if you have stainless validation that allows you to come up with thin clients for your mobile phone that don't require these trust assumptions anymore or require less of them because you could actually validate yourself on the mobile phone if you keep up with all transactions in the system now whether you want to do that and waste all of your mobile phone precious data remains to be seen but maybe mobile phone isn't the right example but maybe something like a like a laptop something smaller but this is i think that's kind of the the hope with this right it's the idea that a validate a validator could you wouldn't need certain kinds of powerful machines you wouldn't need

although actually wait validators never need powerful machines now that i think about it well it depends on which chain you're talking about i mean it's not like miners they don't need mining power yeah not to that degree but it still needs to be a fast machine with a fast hard drive and like a good modern cpu and all because you still have the same essential problem as mining in that you have to make a base assumption of of some architecture that your blockchain will run well on because if someone comes in and is like way below that they can't produce or they can't even execute a block within the block time then obviously that doesn't work like you have a sort of lower bound on the hardware requirements and

this can either allow you to lower that lower bound or it can allow you to scale more so i think to like this simple answer like in an ideal world what this gives us is more security and better scaling and so it's a better system to use in some ways either a better ux or more transactions per second or what have you would it also allow more participants to be validators like is that is that part of that idea that it opens up that's actually what i wanted to to touch upon so i'm glad you and frederick brought this up so in 2016 or 17 i used to run a bitcoin note in my office at mit for fun for no reason whatsoever just for fun

i just thought it would be cool to keep the system up and running and after a while i just couldn't do that like i didn't have enough storage and i couldn't do that anymore and even now like if i wanted to do that for a cryptocurrency like ethereum if i don't have the space to spare to be honest and i don't want my ssd doing all of these writes and reads and messing up my hard disk lifetime so i what actually kind of excites me most about stateless validation is well first there's the charted consensus but second is that it really is a distributed system so a distributed system distributes computation but also storage and if you think of the current nature of ethereum in bitcoin they are distributed in some sense but not in the full sense of the word they do not distribute this the storage

and status validation is a first step towards that it does have caveats you need proof serving nodes but those proof serving nodes can also be distributed they can each maintain a part of the proofs you need somebody to store the transaction history but even that can be perfectly distributed so now you have kind of the holy grail the distributed system and then if you imagine a future where these cryptocurrencies are really secure what's the number one thing you want you want validators as many validators as you can get how do you get as many validators as you can get you lower the barrier to entry so everybody can do it for fun like i was doing it in 2017.

and stateless validation enables that so i think for me that's the most exciting thing because it's an exploration of a of an ideal distributed system and you know perhaps it's not there yet i mean most certainly it's not there in terms of the research but it's it's such an exciting vision and it's it's hard to it's hard to not work on it for me what is interesting is i mean i don't think we have time in this episode to cover it but it is what are the implications of having that many validators we don't know yet or what would it mean to make it so make the barrier to entry so low what potential dangers could that have but i also think that like in the moment just getting to that place sounds like a very exciting goal for security it should only increase security to have more

validators your adversary has to compromise more notes for throughput if you don't shard more validators usually slow you down but if you shard and you have more validators now you can have smaller shards which should increase throughput so it seems like the implications are mostly positive but you're right who knows what subtleties are there yeah there's one subtlety and if you lower the barrier you get validators that are less reliable so like in a in a high requirement system you can basically guarantee that they're always online because there's such a high barrier sentry if it's a super low barrier to entry i'm going to run it on my laptop and i'm you know i'm not validating when i'm shutting it down and what does that mean right so you get

churn you could get more churn as a result exactly yeah i like that point that's a really good point it sounds like there's still a lot of work and research kind of being done where should people go if they're curious about this maybe if they actually want to start getting into this research there's actually the academic work on stateless validation is just beginning to appear so i'm going to send you a list of i want to say 13 papers or so that tackled this problem in one way or another and i think that would be a good starting point for folks to see how academics look at the problem while keeping in mind that academics have their own limited vision into things and then there's other resources online so for example

i think one paper that points to these resources is the edrax paper by purnoy papamantuan and it points to to some websites that started talking about stateless validation as early as 2011 i want to say uh so this topic has been discussed in the bitcoin ethereum community much earlier than in the academic community and those resources are very important also f research is a good good resource and i think i am more also going to send you three links to add research and of course most importantly my own blog you know it's the most important research about this there are or i think people should also check out i don't know if i like i don't remember what was the first study club you did the aggregateable sub vector commitments

for stateless cryptocurrencies so then both of them are related so so i think people should also check out two study clubs zk study clubs you did actually with with us with me um that's on on the youtube channel so those are videos that i'll also add in the show notes i'm gonna add all of the links that you just shared i think there's a lot of work here a lot of resources for people so do check out those show notes yeah so thank you so much alin thank you for coming on the show thank you so much for having me it's been super fun and it's such a great opportunity for me to think more about these problems so i've i've really loved it and you guys have really insightful questions so i really appreciate it it's been very useful for me too

thank you very much thank you and to our listeners thanks for listening thanks for listening [Music]