ZKPodcast: Accumulators with Ben Fisch

Transcript

[Music] welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik [Music] in this week's episode we sit down with Ben fish to talk about his recent work in RSA accumulators we dig into those Merkle trees vector commitments and their applications to stateless clients [Music] before we start we want to say thank you

to this week's sponsor Stark where Stark where we'll be putting on the stark wear sessions in Tel Aviv on September 16th the event will be bringing together the brightest minds in the field of zero knowledge proof from both the academic and application arenas topics include self custodial trading starts for layer one stark friendly hash functions and other cool things you can do with stark proofs fun fact I will actually be hosting one of the stages so if you're interested in this exciting cutting-edge tech do join the starter sessions or come a day early for the stark 101 workshop where you could actually build a stark prover from scratch use the code ZK podcast to get 20% off any ticket we have about 50 of these available so get

it fast as always info will be in the show notes so again thank you stark ware for supporting this podcast and now here's our interview with Ben fish so today we're sitting with Ben fish who's a PhD student at Stanford and part of Dan Bernays applied cryptography group hi Ben hi Anna and as always we're with Frederick hello today we're gonna be talking about accumulators and hopefully get a chance to touch on Ben's work working on the RSA accumulator paper and project we have recorded a few episodes one on Merkel trees went on NPCs those might be worth listening to before you

listen to this episode just because we're going to be touching on those topics but I think before we start in on that we should probably have you know a bit of an intro to you and find out a little bit about what got you excited about cryptography in the first place sure that goes back quite a while I was a junior in college and I was studying math and dabbling a little bit in computer science as well and I internship at the Weitzman Institute in Israel with this cryptographer moneena or just to do some kind of applied math research over the summer and and he happened to be a cryptographer and we did some work in cryptography and I

guess I was hooked on cryptography as a research topic ever since so yeah that was already seven years ago how did you bridge from like working on cryptography and just being in this world to like being in the blockchain space which you kind of are kind of not right so yeah I would say right now I'm and I'm very much in the blockchain space because even now all my research seems to be centered around applications to watching but it did it did take a while going in and out in fact in that first internship I did doing research in cryptography we weren't looking into Bitcoin as a

potential research topic and this was back in 2012 when few researchers were actually looking at that coin we did some analysis there we were we're looking at doing some graph analysis of the Bitcoin network but I really ended up focusing on other problems in that internship and didn't really return to ever looking at the coin again until I started doing work on Bitcoin mining pools that was when I was living in New York I was working with Raphael past from Cornell Tech and Abbie shallot and we were looking at basically trying to explain what is the optimal mining pool

there's so many different mining pool strategies in Bitcoin what can you say about what you know given some given some assumptions about the risk profile of a miner what mining pool strategy should they take and I guess that was my gateway back into working on research on on block chains and here at Stanford danwon has group does a lot of work on you know specifically cryptography tools that can be applied in the blockchain space and that was when I started working on verifiable delay functions which became a big thing I got involved with file coin because I was working on proof of space and prints

of replication useful Bruce's face Bruce's face word that you can use to actually store useful data which is the basis of file coined and and and from there I just kept on working on more topics and cryptography as applied to boxing and right now I'm more interested in using zero knowledge to balance privacy and transparency in blockings before we go more into these projects I still want to go back to that original question of like what is it about cryptography that got you excited because I think this is a great like bio of how you got into it but what was it like why was it just because it was like challenging was it it's a good question

I had to be brutally honest I think that when I first got into cryptography it was more about the challenge and and and then that that's often the case for you know for for researchers it I was a math student and this seemed like a cool application of math and it wasn't really anything more than that I think the reason why I stayed in cryptography was because I enjoyed or found higher meaning in the in the projects that I was working on and and and I and I think I was also drawn to the fact that there is there seems to be such a gap between how much of the cryptography that we have developed in research is actually

used and you know when I was working on research and in back in 2012 this was before blockchain started using a lot of fancy cryptography and so there weren't really any at least well-known applications of zero knowledge and yet it just seems like such a powerful concept the idea that you can you know prove anything without revealing details beyond what exactly you want to prove and so there's these really kind of beautiful concepts that seemed to be very powerful and useful but weren't being used and there was something exciting about that being I did that in short time with you know my own career a lot of the things that photographers were working on would start being used increasingly

more and that actually came true so as usual with guests that do a lot of cool stuff it's hard to talk about one thing we we have the same problem with Benedict where I want them back every week to talk about a different thing but we can't really do that we have to define something to talk about and in this episode I wanted to dig into accumulators and this is something that and I has done a study group on before and then something that we've touched on just barely in various previous episodes maybe we just start out with a simple quote unquote question what is an accumulator well an accumulator is a compact representation

of a set the easiest way to think of it is if you know what a hash function is right then a hash functions kind of gives a fingerprint for a much larger file and and it's it's a commitment it's also called a commitment to the file as its it's binding in a sense that if I give you the file after giving you the hash there's only one unique file that I can give you that will match that hash that fingerprint an accumulator allows you to go further than that and be able to give you individual items in a set and you would be able to verify that those items match that small fingerprint that you were given you don't have to be

given all the items and asset at once in order to verify that and that's the general sort of definition of accumulator but it also sounds a lot like a definition that a lot of our listeners will know which is that of a Merkel tree absolutely is a Merkel tree and accumulator the Merkel tree is definitely an example of an accumulator there's one you know minor nitpicky definitional thing that if you talk to cryptographers or look at the literature on accumulators accumulators are sometimes defined to have constant size witnesses okay and Merkel trees have logarithmic size witnesses but I would say in a more

flexible the evening human accumulators Merkel trees are definitely an accumulator just was slightly larger and we can get into what these different terms are called because I have slightly larger what's called a witness then say other types of accumulators like RSA key miners so they're sort of like related in the same family but when you use the term accumulators are you actually kind of talking about something else like does it do accumulators also have their own like you just said it's like a continent needs to have a constant size witness yeah so the the witness going back to my very basic explanation of what an accumulator is when I claimed that after giving you the acute what's

called the accumulator state commitment which in the case of Merkel trees is the Merkel tree root okay then I can give you an item which is in the set and a witness which is a proof that that item is actually consistent with the state commitment that I gave you Merkel trees would be giving you a Merkel branch which is the witness for a leaf of the Merkel tree and you can verify that against the Merkel root Merkel trees are examples of accumulators the only reason why we use the term accumulator is because it explains a more general potential space of you know of constructions of this abstract concept and so there are

accumulators that have smaller witnesses mainly consul trees have logarithmic size witnesses Merkel trees are actually more than accumulators their vector commitments and we can talk about that to know I'm curious we should get back to this point of the different like properties like witness size commitment size storage size and like it how they differ why you would want to use one or the other because I think that sort of clarifies what the difference is or when you would want one or the other going back a little bit to definitions and literature like when you read on this

topic you will come across things like dynamic accumulator so Universal accumulators batching aggregating proofs witnesses let's maybe start like what's the difference between a dynamic and universal accumulator well dynamic Dinah I mean a dynamic accumulators are as a subset of the universal accumulator so dynamic refers to the ability to update the set that the accumulator commits to so this could be adding elements to that set and then updating the state commitment that you're given right so in it it's always easy to go back to a concrete example so

in the Merkle tree example if you have the root of a Merkle tree and i add an element to the Merkle tree is there a way for me to have you you know can I for you to be able to update the root of the Merkle tree on your own a tribute way to make a you know an accumulated and dynamic would be to just redo the entire computation of the root that would not be considered a dynamic accumulator dynamic accumulator specifically means that it you know there's some way that that you holding the only the root of the accumulator can can perform an efficient update without having to redo all the work that you did

in the first place building the accumulator from scratch if that usually that change is that usually like changing the value of one of the Leafs or is it changing the path changing the value of one of the Leafs could be viewed as an addition and deletion of an element that would be so you would need a dynamic cure it would sort of fall under the dynamic accumulator right in any specific example of a dynamic accumulator Merkle trees by the way can be made dynamic depending on your particular instantiation of the accumulator there may be a much more efficient way to update a particular element in the set than performing an add and then a delete but the definition of the dynamic accumulator is just

saying that okay we can form adds we can perform deletes that handles the case of updates as well at least it in in a theoretical sense and a universal one is what right so Universal accumulators are dynamic but they also support both membership and non membership witnesses so this is another thing we've been talking about membership witnesses which are like Merkel branches that prove that the leaf element is in the Merkel tree you also might want to give a proof that something is not in your set I'm not in your Merkel tree and that's called a non

membership proof accumulators which allow for both non membership and membership proofs and are dynamic are basically universal they do everything that's why they're called universal no I originally my background as a developer on like blockchain software I come very much from like the Merkel tree world and I knew Merkle trees intimately and then when I started reading and studying accumulators and found out that like non-membership proofs are a thing I was like wait really you can't you can have that you can have something that or you can prove like non-existence and I think I think that's pretty cool yeah you can even do it with basically Merkle trees

the typical way of doing it with the Merkel tree is maintaining us Merkle tree of sorted elements at the leaves then being able you can you can prove that something is not in the set by basically showing that you find two elements which are both greater and lesser than the elements that you're trying to prove is not in the set and you prove that both of them are in the tree and adjacent and so that shows that as long as you as long as there's this invariant that all of the elements that the leaves are maintained in the right order then you do have the capability of giving non-membership roots that's cool how do you prove that they're adjacent well all the leaves of the Merkel tree have indices and so this is the other

thing the trees are actually they're actually laying out the paths yeah yeah so they're so this is why Merkel Jews I said I've actually powerful than your average accumulator there vector commitments because they not only are binding to the set they're binding to the position of elements within the set you can show that this is an element in the set at this particular position in other words this is the eye element of this vector and this actually gives them the quality of half at least in certain contexts being able to define a non-member witness or like you were able to actually yes that's cool that's right but it's not necessary to be a vector commitment in order to support non-membership witnesses so RSA

accumulators are not vector commitments so they're not positioned binding accumulators however it is possible to give non-membership proofs and membership proofs with RSA accumulators yeah so it all depends on on the particulars of the construction so we've just talked about the dynamic accumulators being sort of like a subset of the universal but I'm guessing there's also like the opposite right or like our like what's an accumulator that isn't universal so Universal is I guess an inclusive term right so accumulators which are not universal might be really good at one of these things like really good at membership proofs are non-membership proofs but don't support

both or they are dynamic in the sense that they support ads but they don't support deletes madri's untick instruct a non universal accumulator that's really good at one of these things but doesn't do all of them at once the last two things that I just want to touch on before we talk a little bit more specifics is the concepts of batching and aggregating because that's sort of relevant to your paper that we will talk about later and and it's also a little bit maybe on the more forefront of research II topics in how accumulators work right so what is what is batching and aggregating proofs I think the best way to explain this is maybe to go again

back to the concrete example of a Merkel tree so Merkel trees do not batch or aggregate when you prove that a particular element is committed in the Merkel tree you give a Merkel branch for that element or Merkel proof and if you want to prove that two different elements are in the marquetry then you'll have to give two different Merkel branches as proofs and so on and so forth if you're proving 100 elements are in the tree then you have to give a hundred different Merkel proofs and the size of this proof basically grows linearly now you might observe that if the elements in the Merkel tree are very close to each other then some of these

proofs overlap so you may get some minor savings right let's say that oh you know they're proving the inclusion of the elements at the leaves of some subtree say like the first 100 elements then you do get some amortization you know effects where you don't get giving a proof which is exactly a hundred times the size of proving that one element is in there but in general these merkel piece you can observe do not aggregate very well so aggregation is basically saying that we can take a bunch of individual proofs of a given size and combine them together into a more compact single proof that covers all the original proofs are batching and

aggregating the same term here them to be precise they're not there's different uses of you know of batching a negation and and I guess different researchers have different strong opinions on when you should use the term batching and when you should use the term aggregation but generally like aggregation refers to taking a bunch of the existing proofs and combining them into a smaller proof whereas batching could refer to the the action of generating a large set of proofs more efficiently or verifying a large sort of proof more efficiently or even creating and I would say this is maybe where I would defer from other

researchers but I think that batching can be used to to refer to the action of creating from scratch a single proof for proving a whole bunch of you know smaller proofs that is more efficient not only in the action of generating it so the computational efficiency but also for absent the size of the proof that you act that you end up with at the end that's uh that was my understanding as well but maybe that's because I've read mostly your research but yeah so batching being I want to prove membership of these hundred items and here's one proof like you generate that one proof for those hundred items whereas aggregating is you generate a

hundred proofs and exam after the fact combine them well although yeah although some researchers would say that aggregation should batching should only be used for referring to efficiency that you create a hundred proofs in the end but you just create them more efficiently in in this bro that's generation process intuitively to me I like the idea that aggregation is taking existing things and combining them and thatching is saying that from scratch being able to say I want to prove these a hundred different things I don't need to give you a hundred different proofs I can give you a super efficient proof that I can say either create more efficiently or make it smaller but I'm doing it from scratch and that I would

call batching other than aggregation I think you've like in your description of Merkel trees you just sort of mentioned you you basically used a term that is the same term as membership witness but there you called it the Merkel branch set them is that what we call it like the Merkel branch is a membership witness yeah well you know Merkel tree thing it's sometimes referred to you as as that yeah I mean basically the and the the actual proof of a given leaf at the item is constructed by following the the branch that extends from that you know the route to that leaf and then also actually you don't provide the you don't

provide the nodes on on that path from root to B if you provide the adjacent nodes to each of those nodes right but that collection of items that you give could be referred to as a Merkel branch or a membership witness or a membership with misery of a Merkel tree so the the last point of definition that I want to because this also pops up kind of everywhere when we were talking about accumulators particularly RSA accumulators and that is groups of unknown order what are groups of unknown order it sounds like a very mystical term they're groups and for which you do not know their order so so first you have a

finite group and basically I mean groups have a have a have a mathematical definition we don't need to get into the full definition of a definition of a group I think it's more useful to talk about examples of finite groups right so one of the key properties of a group is that you have some operation that you perform on the elements of the group and the group is closed under that operation there's other properties as well such as in person so let's talk about a curried example like integers the integers are a group under addition take any two integers you can add them together you get another integer there's an inverse

operation to that which is subtraction and the integers are not a finite group they're an infinitely large group there's infinitely many integers if you keep adding integers to each other you're you could get ever larger integers now if you look at the integers modulo n now you're talking up and you talk about addition modulo n now you're in a finite group take a number and then there there's exactly n elements in the integers modulo n we know the order of that group kind of by construction you can talk about slightly different groups such as multiplication modulo n okay so now we're not looking at adding numbers

together and finding the remainder of mod n we're talking about multiplying integers together and then reducing mod n and the size of that group depends very much on the end that you pick so if n is prime then there's exactly P minus 1 elements in this group but if you choose and differently then in general if the size of the of the group will be Phi of n but it's just 5 then it's this is something that you can compute knowing the factorization of n so if n is equal to for example if n is equal to a product of two primes n is equal to P times Q then 5 and will be P

minus 1 times Q minus 1 if you don't know the factorization of n it's very hard to compute Phi of n or at least it's as hard as computing the factorization of n RSA works in groups of unknown order because it works in a group of where you know doing integer multiplication mod N and the factorization events that that so yeah the the order of the group is how many elements are in that group is that race that's right and in in the case of multiplication modulo n it depends on these two primes and I think and anyone who's looked into RSA crypto and is

familiar with this is it's part of their like trapdoor function stuff and so is this why they're called RSA humilate because they are based on the same assumption of multiplication over two primes yes they're called RC accumulators because typically they're instantiated using the RSA group as the group of n an order but one of the points that we discuss in our paper is that you could use other groups of unknown order as well and you don't need to restrict yourself to the RSA group and in fact in other groups of on an order there's benefits such as not having to do a trusted set up but we can get into that a little bit later

what does RSA stand for the authors of RSA so Ron Rivest Adi Shamir Leonard Adelman yeah this was a point of trip that I didn't actually know there is this thing called RSA laboratories right I don't actually know what RSA laboratories is or does is that a company that they started I think yeah so there was a company RSA you know that that was that was I think then they were involved in the founding of this company as well that pushed forward then does industry adoption of RSA encryption um his irony laboratories the same as the RSA company again I'm not entirely sure

either I couldn't say but it is this company that publishes these RSA groups they it they mentioned so you kind of need to to trust this company if you're using these groups mm-hmm or you construct your own right I mean there is we know ways around this you can construct an RSA group we're using multi-party computation right the same way that Z cash use a multi-party computation for their trusted set up you could use a multi-party computation to establish the RSA group before we dig too deep into RSA human leaders particularly maybe we cover just slightly what our vector commitments

we've mentioned these already how do they fit into this story so vector commitments are similar to human leaders but you there positional commitments meaning that I have a list of items and and and then I can prove that the item of his list was committed to by the vector commitment state commitment so it's very very similar to accumulator we have state commitment but the state commitment I can give you a vector and then opening Bruce and it proves that a particular item is at a particular position of factor so a Merkle tree could be a vector commitment as well if it's sorted but like the etherium Merkle

tree wouldn't be it would still be an accumulator but not a vector of commitment because it's not sorted no actually the the Merkle tree is just it's a vector commitment already without having the Natalie's sort of because I can prove to you that the ice leaf has this value so it doesn't matter that the leaves are sorted according to some ordering criteria and right it just matters that I can prove to you yet what is the leaf at any given position of the tree so that makes it a vector commitment I see what would be an example of other vector commitments um so we actually construct a different kind of vector commitment in our paper there were other doctors I

mean there's other vector commitments I I think would be a little bit challenging to go into the details of how they work over the podcast but I think that actually that may be the easiest vector commitment to explain is is the one that we we do in our in our paper because it's basically using an accumulator to construct a vector to memo think of first about just a vector where all the elements are just 0 or 1 so like a bit factor right and I want to be able to to prove to you that the ice bit of this bit vector is 0 where I want to be able to prove to you this one right and you have some kind of state

commitment to this bit vector so what we can do is we can say that well let's build an accumulator that accumulates all the indices that are 1 then if we are able to give inclusion proofs and non-inclusion proofs in that accumulator then basically telling you whether the I did of this vector is either 0 1 is the same as telling you whether the i'f index is included in an accumulator that can missed all the indices which are 1 are not included in thank you mode and if it's a 1 then it should be included in the curator and if it's a zero then that eyes and X should not be included in the tumor that wouldn't really give

you an efficient vector commitment if you wanted to build vector commitments um on where the the the values that each index are larger than 1 right so let's say you wanted to have doctor commitments where you could have look at 256-bit value of any given index then I'd have to give you 250 six individual inclusion and non including proofs of each of those bits so I did a bitwise the beautiful thing about the batching and aggregation techniques of our paper in fact the main theoretical motivation was to be able to build this factor commitment which allows you to prove those 256 different bits all in

one compact proof so I give you basically a compact proof of all the bits that are set to 0 in this 256 bit value and a compact prove all these pits that are set to 1 and in this student this about bit value and then you have a constant size proof that this is the value of this at this index of the vector commitment so speaking a little bit about parse a human layers we haven't really defined them but I I don't think we have to go into the mathematical definition of it but generally how do RSA accumulators work how do they compare to Merkle trees why I would use one or the other well yes so RSA accumulators are able to achieve smaller membership proofs asymptotically

than that Merkle trees can but really if you're just using an RSA accumulator for proving inclusion of a single item it's not significantly better than the accumulator I've done a marquetry accumulator unless the Merkle tree accumulator is insanely like the number of items that are being accumulated it's insanely large I think why our work and gives renewed interest in RSA accumulators is because we were able to achieve aggregation or an batching of membership roots so the ability to give us a single constant size membership proof for arbitrarily many items in the RSA accumulator at once it's something

that you can't do with the Merkle tree that's really interesting so I mean if we take your theorem as an example it kind of suffers from both problems where on you know if we want to realized the goal of like every human has and aetherium accounts then there will be billions of members of this Merkel tree which probably prohibitive like when we make a like client request and say please give me you know the state of these contracts are like execute this call for me and give me the proofs that all these things were done correctly we are generating a ton of merkel proofs and sending that back so

in that sense maybe accumulating them would also be good right and so the RSA accumulators could be used to end up sending it you know in it in a transaction or in a message to a light client right a smaller compact message that that that summarizes what is being proved but I mean could you could you actually use the RSA accumulator in an etherium like set up because I always understood it sort of in the context of like a you TXO model could it actually also be used in an account based system so in an account basis simulaid vector commitments actually yeah actually what you really want is sparse vector commitment or a key value

commitment so I can be able to give you the item at this key right in an account is basically a key value store and sparse vector commitments give you that so sparse Merkel trees for example are sparse vector commitments we can also construct sparse vector commitments from our say acute layers as well so what exactly is that that your paper introduces is it a new type of accumulator a new type of vector commitment or modifications and new techniques on on the RSA accumulators so it has improvements on the RSA accumulator to be able to achieve you

know the batching and aggregation I was talking about and it gives a new kind of vector commitment that's constructed directly from the RSA accumulator techniques and is is basically able to achieve the same batching and aggregation properties four-vector commitments so I could open you know say many I could I could prove to you that many different accounts are consistent with the state commitment to you know the etherium blotching with a single constant size proof there are trade-offs of using our constructions in terms of computational efficiency now then Devils and always in the details in terms of whether this is

actually going to be appropriate for it for any of the systems and and nobody's quite experimented to see if if they work better than Merkel trees or Patricia trees you know for where the tasks that those are used for in systems like a theorem in Bitcoin there are trade-offs with her using something which is able to achieve you know massive efficiency gains in terms of the size of information that's communicated but then ends up putting much higher computational burdens on the parties that are trying to generate the proofs in the first place speaking about experimenting with this stuff is there any code accompanied with the paper like

have you guys implemented all this and is it you know open source anywhere so we did it directly along with the paper however there it now is a an open source library that implements all the things that we do in our paper it was put out by this company Cambrian labs so it's an open source project and we did help them understand the details of her paper when they were developing that nice do you know what language it's written in rest nice and I can go play with it a problem with RSA human leaders that we've already touched on they need some sort

of trusted set up and there's a way to solve this if I understand correctly but I don't really understand what it is or what the problem with it is so there are these things called class groups you already mentioned them there's a competition by Chia to be able to construct these sufficiently do class groups not exist are they not constructed yet or is it just a matter of like constructing them quickly or like what what's the deal with class groups right now class groups do exist in in general there are these groups that are defined over any algebraic number field and it's believed that you know if if chosen under some particular parameterization basically if

it has what's called a large discriminant then it's very difficult to compute the order the number of elements in the class group we just don't have efficient algorithms for doing that and you can define the class group and operate on elements in the class group without first specifying its order unlike cars say groups which by construction know the order that's not the case with class groups the competitions are more about trying to see how efficiently people can try to operate on elements within the class group I mean there's an interest in making class group operations more efficient but RSA group operations are like they're pretty straightforward it's

integer multiplication mod n we know that very well and if know how to optimize it in Hardware more so than we say know how to optimize class group operations there's also a competition surrounding the problem that we believe is hard which is how efficiently can you figure out the order of a class group once you specify it right so instead of using a group of unknown order we use group that where the order is extremely hard to compute oh that's all right that that is a group of unknown order so the we know that it's a finite group we it's hard to compute this order though the difference with RSA groups is that

whoever constructed the IRSA group knows his order and presumably nobody else does because that secret information wasn't shared with them whereas with class groups it's like we think and we can specify the group and the sacred stuff never exists you don't need to compute the order of the group in order to specify and the the competition stuff is more around operations of that group not to construct the group all right right I think I get so that's also the downside then no class groups and why I suppose people aren't using it as much is because they're not as efficient not yet yes so let's move into these questions of stateless clients Frederick I know this

is a question you were really excited about how what is the relationship here between stateless clients and all of the stuff that we're talking about well I mean I'm excited about stateless clients in general it's obviously a topic in the paper and I think Ben you presented very well in your presentations of this paper of like the motivation behind why we want stateless clients and what they are we have this problem in bitcoins Merkle tree is pretty localized or just proved like we're doing simple payment verification stuff and just kind of simple stuff but in etherium a lot of people are trying to do more and more

complex things with the Merkle tree particularly people are trying to do often computation and then like prove like submit the merkel proof on chain so that it's verified on chain but these proofs are massive and so you can't actually fit the proof in one-one block anymore and like you run into all these sorts of problems and I think accumulators solve that by saying our proof is no longer 100 megabytes or 10 megabytes or whatever it may be it's constant size or its linear insights or whatever it may be so maybe Ben can you talk a little bit about what stateless clients are and and how accumulators play a role yeah so the

basic idea of the stateless client and unfortunately stateless is I at least to me slight sounds slightly misleading because you're not actually getting rid of it any state it's just someone else storing it well more specifically so let's first say what stateless clients refer to stateless clients refer to basically making a blockchain node which is only needs to remember some small state commitment it doesn't need to store all the you know the entire state which includes the etherion the balances and all accounts or the

state values in all smart contracts right they would just need to store some kind of state commitment and then verified transactions against that state commitment when presented with proofs against that state commitment that the transaction correctly references information in the states like every transaction basically has information that can be locally verified and then references something and it needs to be referencing like account balances correctly with respect to the current state of the blockchain and on top of that these stateless clients need to be able to update the state after each transaction as well so

after processing transaction they need to be able to update the state commitment to get the next state commitment so they can verify transactions from there it's not a stateless system because it you know in the true sense of the word stateless because they do need to maintain this state commitment they can't basically experience a power power outage and completely lose all memory of the state commitment and come online a while later and be able to continue participating without trying to figure out what happened in between like that would be the true notion of stateless but they do

have very minimal state storage requirements right it's basically down to this compact state commitment rather than you know kicker bytes or terabytes of storage how do they relate to like clients then are like clients stateless clients is there any connection here yeah so again these I guess these are just terms that are that are use and also some people might confuse the terms with it when using them within the within the blockchain space these don't have like academically defined you know definitions but for my understanding like clients generally refer to a client that is trying to synchronize not

participate in validation of blockchain transactions but synchronize with the current state of the blockchain and be able to you know again download and sync efficiently and then be able to you know query the box chain in the authentic way so it's it's more about being able to to synchronize or query the blockchain without having to participate and there it's actually stateless you could forget everything or join the system from scratch and be able to sync efficiently as a light client but you're trusting that the system operated correctly or not you're not participating in the actual validation got it and a stateless client like the sort of umbrella term suggests that you still would be able to interact with it the stateless client

idea is basically saying that you know it could be Summers is this so light clients need to connect to a full a full node now that they trust and the full node needs to be a full-blown blockchain node they need to store the entire state of the blockchain and participate in you know blockchain validation like clients need to trust the full node and then be able to sync with it quickly a stateless client would be more like a stateless validator or stateless full node that can continue to participate in invalidating and determining that every transaction is correct without actually storing the entire state of the

blockchain in your talk you present the this sort of separation of states and consensus and I like that description of it where if I'm just running a mining node I don't actually want to store anything I just want to be able to progress like choose which transactions to include and progress to the next block examined I own like for it I think where it gets interesting then is for a user it was not like a miner but once so they would they have some interest in store the state because they have contracts they want to interact with or they want to see their balance or some other other stuff but they don't necessarily need to

participate in consensus so it makes perfect sense to separate these two concerns yes I think a question for me though is if we're constructing an RSA accumulator over the States as a user what state do I need to store can I store just my own balance and still be able to provide proofs that I'm doing the right thing when I'm like sending something to another address so unfortunately not if the validator is participating in consensus no longer store the entire state then they need to be provided with proofs right along with the transactions of those transactions

correctly reference stateful information so if this is in aetherium and people are referencing a balance and a particular account there needs to be a vector commitment based proof that the balances is correctly referenced in the transaction now I think the users need to be able to to store information to generate those proofs or there need to be services that do this I see that as a more realistic outcome that there will be services whose you know like you can call them data provider nodes whose sole business is to basically create

membership proofs for accumulators or be able to provide information to users that they need in order to open the vector commitment on their account and that can be a competitive market you're not trusting anyone that anybody can provide that service it's just a different say role and necessary for participating in blockchain consensus yeah and I marked like if you if you have a Merkle tree and I want to I have a balance I want to send something to another person I need to be able to prove what my own balance started at and what the other person's

balance ended at and those are the the Merkel proofs I need to include to convince someone that I'm doing this correctly and wellsite not so when the transaction is going to propose an update but the transaction can be validated that as long as it correctly references the current account balances of both your account and the recipient account so you need to prove you know to basically give membership proofs or I mean in this case we're talking about account balances vectored tournament openings of your account balance and the recipient account balance inside the transaction yeah so two on my side I actually only need to store my own

balance and the recipients balance and I don't need to store any other states that's right but you need to store you need to be able to generate the dr. commitment yeah proof so I made I need the rest of the Merkle tree sort of but not the leaves but in a in an RSA accumulator world is there such an equivalent that like I can store these intermediary states of america tree without necessarily storing all of the leaves so actually I mean you don't even need this storing the holes internal say to the merchants tree would be quite large you just need to store a few merkel branches that are relevant to your account and and the recipient

account and nars a accumulator again you need to just store the membership witnesses the problem is that every time new transactions are approved by the blockchain the state commitment changes right the Merkel route will change or the Narcy accumulator case the the RSA accumulator state commitment will change and when that happens sometimes the proofs also need to be updated right so that means that you as a user if you're just maintaining your own membership witness you need to be listening to the blockchain and updating it as new transactions are appended to the to the

ledger and that's a lot to ask from users to to basically remain in sync and keep updating the the proofs that they're maintaining which is why I think that that will become a data service that people will do for users in a completely it doesn't require any trust it just requires somebody else to perform the computation for you yeah I mean as much as I love the idea of stateless clients I have yet to see an actual practical proposal because they all sort of break down on this point that either I need to stay online all the time or you know there's other problems such as like requiring huge bandwidth if I really say that I don't stay online and just when I come online

I sync up with the rest of the network what the current state of the Merkle tree is well that can actually be pretty large still even if you're just maintaining some branches because realistically you're not just maintaining your own balance you you're probably maintaining a few things of like what you want to interact with and so forth so usually like huge bandwidth requirements right like you know in our paper where I mean we explain how these RSA accumulator witnesses can you know basically be updated just by looking at the sequence of transactions and so if I am listening to the blockchain I can continue to update my my RSA cumulate or witness if the problem of course is if I

go offline for some time that I need to download the sequence of transactions that happen since I was last listening um but we also explain how if you're trying to maintain any witnesses at at one so say again one of these data service providers I was talking about who maintained many membership witnesses on behalf of a whole set of clients there are amateurs ation benefits to that so there's ways of we call it batch generation of membership witnesses that can be done more fish that just maintaining and updating an individual one in the model that you think about would all of the proofs be included in the blocks so like would you

include the transactions and all of the proofs for that transaction in the block that's being produced or would you you know get rid of the proofs and just say I trust that the miner did this correctly well I think that's um I mean that's more of a matter of opinion of I mean anyone who wants to be able to verify that the transactions were were validated correctly would still need those proofs but there could be further you know aggregation of those proofs or even I mean and this is getting into the how people use snarks for first stateless verification where Azir a single succinct proof of knowledge could

summarize you know all of blockchain history until now and that's a a different direction of research seminars yeah it's an interesting thing to think about because like one of the pitfalls of stateless clients that I've seen is the Merkel tree version of it like the Merkel Pat's get so large that you can't actually include all the proofs with all the transactions in a block because the block would end up being huge and if you're if you have an RSA accumulator or something like it not only like is the individual proof smaller but your pointer like you could actually aggregate them as well it kind of changes the dynamic yeah one final

question I that just popped into my mind what is the the size of the human later like the Merkel tree you know grows pretty large because it has so many hashes like all the way up the tree right how large doesn't in an RSA a human very good so similarly it's linear right both Merkle trees and RSA accumulators the storage of all the internal information of the accumulator is linear and the number of items that are key new it and of course the Merkel tree root is constant size similarly mistake commitment in in the RSA accumulator is constant size but in order to be able to generate membership witnesses from

scratch you need to be storing the entire internal state unless you already have a membership witness for a particular item and are just interested in updating that are one of these two things faster like is there a speed-up so in general Merkle trees are just faster because hashing is fast our so with RSA accumulators verifying groups can be very fast and so and so if you for example compare verifying hundreds of merkel proofs compared to verifying a single you know aggregate inclusion proof of a hundred different items of

our sake and we're using our techniques you can start to get faster because you're just verifying a single proof that complexity verifying a single proof doesn't grow with the number of items that that proof accounts for we also use these tricks called proofs of exponentiation that speed this up it's related to techniques that are actually used for verifiably functions it's fun how all these different primitive size start borrowing techniques but the proofs of exponentiation make the verification of the purse very fast but Merkle trees in terms of the computational efficiency of generating proofs are generating you know the tree even they're much much faster it is a downside are safety limits as a

final note on this topic in the accumulator stuff your paper is just talking about batching techniques and and we're talking about performance are there other like big areas or like big improvements that you see that are necessary for all of this to become really practical or where you know if we just solve this one thing it's a no-brainer that it will be used everywhere i think it i mean i I've sort of already hinted out what needs to be improved for example with our sake humanism are obviously RSA accumulators and our work achieved this improvement in communication reducing the amount of information that that

would be sent in a stateless block to interstate was client design but then increases the computational burden quite significantly and so further developments there would I think be pretty necessary for making this practical one thing to notice that because RSA accumulators share some of the same tech you know technical building blocks as verified with the wave functions etherium is investing in hardware to make the operations in our say groups extremely fast so once that is developed it will be interesting to see if that makes our seyh accumulate is much much faster that would really change the game

as well hashing is super fast because it's also been optimized in Hardware right so so that will be really interesting to experiment with once that hardware is ready that's really cool cool this has been a really great conversation I feel like there's probably so many more things that we could talk about maybe just briefly what what are some upcoming research or projects that you're getting excited about these days or maybe something you're working on right so as I said sort of at the beginning of right now I'm very excited about working on sort of you know applications of zero

knowledge to balancing transparency and the confidentiality in in blogging systems like ICS or transparency it was one of the main benefits that blockchains can bring to financial transactions and and and yet we also wants to retain privacy confidentiality so in a private system what can you prove so for example I have this work that and I'm doing right now which will which will about soon on zero knowledge taxes being able to basically prove that your tax compliant if you're receiving payments

over an anonymous payment system like C cash and and also some of the techniques that I'm working on in research applying at the company that I helped found called Pandora which is all about balancing transparency and confidentiality in financial services that could then run over a block chain so you can imagine the future where a hedge fund is running its operation over AG locking in a very transparent way so that it it it can't run a Ponzi scheme or embezzle funds without users detecting that but yet it still can

retain its basic confidentiality or basic private balance sheet thank you so much for being on the show it was a fascinating conversation yeah thank you for having me it's really a pleasure hope to be back sometime I think that would be really cool yeah to our listeners thanks for listening thanks for listening you [Music]