zkAcademy #1: Exploring Lagrange's Recproofs and their Impact on DeFi

Transcript

Hello again. Uh I'm Shravan Srinivasan. I work on a cryptographic cryptography at Lagrange. Uh welcome back to my talk on uh Rec Proofs. It's a Merkle tree-based vector commitment scheme with updatable batch proofs. Today, I'm excited to talk to you folks more about the applications of Rec Proofs. So, uh before uh I kick start, uh let me give a brief recap of what uh I I spoke last time. So, uh I'm going to give a recap of the problem Rec Proofs is solving and how it solves.

So, uh we all know our we all know and love our Merkle trees. Merkle tree allows us to commit to a ordered sequence of value with a short commitment. Say, when you have values A0 to A15, uh you can uh consecutively hash adjacent values, and you can do this recursively until you just have uh one value at the top, which is going to be the root of the Merkle tree. Uh in addition to just uh computing the commitment to a vector of values, you can also prove an opening using Merkle trees. So, say if I want to prove A5 is in this vector, I would give out these values highlighted in green, and any verifier can use these values to recompute the hash path from A5 to the root, and with that um

uh they can recompute the root and check if the uh this value is what they expect. If that is the case, they can accept this proof, else they can reject this proof. Um the um whenever there's a uh value changing in the vector, say in this example, A12 changes, you can update the proof of A5 by computing the path where A uh A12 to the root intersects with the proof of A5. In this particular example, it's going to intersect at the specific green node, and if I just update this green node, then we can update the proof of A5.

Similarly, all proofs can be updated in this manner. So, uh the focus of Rec Proofs is about batch proofs. A batch proof is a special type of membership proof. Rather than proving one element at a time, it will a single proof can uh open K arbitrary elements simultaneously. Uh a a new way of doing batch proofs is concatenating K individual membership proofs. That's why there's a key efficiency requirement that we need these proofs to be uh batch proofs to be much smaller than the K individual proofs, and preferably we should be able to verify much faster.

Uh current approaches are not updatable efficiently at least. Uh I'll tell you why this is the case, and uh the primary focus of Rec Proofs is how to build a batch proof that is also updatable. So, uh a quick run-through of uh a naive example. Let's say that an inefficient way of doing batch proofs is to concatenate all the proofs. So, say if I want to prove that A2, A4, A5, and A15 is in this batch, I would give out the individual membership proofs of A2, A4, A5, A15, and all of them put together would make up uh the batch proof of this set.

Unfortunately, this has a large proof size. It's going to be K times log n asymptotically. Uh uh and and it's all and uh one of the good things is you can just like the way you update individual proofs, you can uh easily update uh uh these um this batch proofs just by um invoking the same individual proof update uh K times. Uh you can get rid of some of the problems like being a a large proof size by compressing the batch proofs using SNARKs. However um it has its own drawbacks. Whenever an element in the vector changes, you have to recompute the entire batch proof from scratch. And whenever um the size of the batch changes, you have to figure out

how to reconfigure your circuit such such that uh you can uh batch uh more uh elements in the vector. So um the Rec Proofs primarily uses recursive SNARKs, and it can update batch proofs in log n time. And we can extend Rec Proofs to uh verify map-reduce style computation even when the underlying data changes. For example, when you want to verify that certain elements of the Merkle tree are greater than some value, you can generate a nice proof, which uh in fact attest to this uh any predicate of your choice.

So, um I'll be more I'll be talking more about the applications today, specifically on the BLS key aggregation and the digest translation later during the talk. So, a quick rundown of how Rec Proofs work. Let's say that you have a Merkle tree of a Merkle tree, which is going to contain these values A0 to A15, and the green values are the uh the hash values. Uh now, say that you want to compute a batch proof for A2, A4, A5, and A15. You would have a partial pruned partial tree with just these green values. And in addition to having these Merkle hash values and so on, you would need something called as a canonical digest.

Uh what this does is essentially at each uh node in this pruned tree is going to have something called uh as a canonical digest, and that is defined with respect to the uh respect to the batch it's trying to prove. So, if you look at the root node C here, it's going to contain a set in blue, which consists of A4, A5, and A15. So, uh these are all the values that are in this uh under this uh node uh a node rooted at this uh this uh this location in the tree.

Uh if you look at A12 uh C um CL, A2, A4, and A5 are the only values of the subset that are in this subtree. If you look at uh CR, A15 is the only value that is in the in this subtree, which belongs to the subset of the original subset. So, um I've highlighted these subset in blue, uh which we call as node subset. When you compute a short uh short accumulator digest of this uh node subset, we call that as a canonical uh digest.

So, um in addition to computing uh these uh values in blue, we also require a SNARK proof at each uh internal node of the pruned Merkle tree. So, essentially what the SNARK proof says is all the uh set values, which are highlighted in blue, and the Merkle values, which are in green, are consistent, and the entire subtree is valid. So, you keep on building such recursive proofs, which will attest to the values uh which are uh under the subtree. And the one which you have in the top is essentially going to attest to the fact that the subset A2, A4, A5, and A15 is in this vector, and the Merkle tree uh digest of this entire vector is going to be C. So, and

the root uh pi at the the the proof pi, which is at the root of this tree, is going to be the single batch proof um the uh that's going to prove that these elements are in the batch. So, uh whenever you want an update uh an element in this batch, all you have to do is just recompute the values along along the path from the leaf to the root. And this way, you can compute a new updated batch proof. In this example, it's going to be pi prime. So um we can generalize this approach to perform map-reduce style computation.

Say that you have A0 to A7, eight values in this vector. First, you assume that you have committed to this um vector using Merkle trees and C's commitment. Then, you can uh perform map-reduce style operations on this specific tree. So, when you perform map, you will get a specific output, and the reduce operation is going to take the values from the previous two uh pre- uh previous level and and and combine them, and give it's going to give out another value. So, in addition to doing uh the membership parts, you also attach a proof pi LL, which attests to the fact that the reduce operation was done correctly. And uh the Merkle digest uh at that specific uh subtree is also

correct. You can do this recursively all the way to the top, where you can take the results from the previous reduce operations, combine them together, and reduce it one more time, and attach a proof that the reduce operation was performed correctly. At the same time, the hash values uh the Merkle hash values in that subtree are correct. And the proofs that were in the previous level were also correct. You can do this all the way to the top, such that the root uh has a proof pi, which will attest to the fact that reduce map-reduce operations in this tree were performed correctly. At the same time, uh C is the digest of this uh vector.

So um let me jump into more about uh how we use uh um Rec Proofs in the context of blockchains. So, um blockchains have uh incremental state updates, meaning that um between uh uh consecutive blocks just updates uh updates the state of the blockchain by whatever uh transactions that are contained in this the specific block. So, um and Rec Proofs are designed to be such a way that it can incorporate such incremental updates. You can also um think about how to parallelize it in uh Rec Proofs in such a way that you can apply multiple updates uh simultaneously.

So um jumping a little bit more into the details of how the state looks like. So, uh essentially in a typical blockchain, the state is going to be the account balances and the contract smart contract storage. And when you want to make statements about say specific contract of your choice at from some memory slot, first thing that you would do is to prove the membership of that specific memory slot. However, just proving number however, making statements about just one memory slot is not that expressive and you would have to batch proofs when you want to make statements about multiple memory slots simultaneously.

A key thing to note here is whenever a new block comes in, this proof batch proof might change and if you standard name approaches like the one I mentioned using snarks, you might have to recompile the proofs from scratch. However, on the other hand, when you use rec proofs, you can update update them in logarithmic time and you can keep the batch proofs up to date and based on the updates that happen. So, let me practically tell you how this works. Let's say that there's a specific memory slot in the contract which keeps track of some specific price or some exchange value or something and you want to compute a moving average to see how it goes about. So,

a moving average is going to be in this particular example, the moving average window is going to be of size K and you want to take the last K values, compute the average over it and return this as the value at instance K. So, one way to do this is first you build you take the values P0 to P7, you build a Merkle tree out of it and then you perform the rec proof style map reduce at each level. So, in this specific instance, the reduce operation in purple is going to be P0 plus P1 and so on with other values and the and the snark proof here is going to attest to the fact that everything that was done in the subtree was done correctly and you can propagate this through

multiple levels where you can have take the results from the previous reduce operation and reduce them again and attach a proof that the subtree was done correctly until until you get to the root. At the root, you can simply divide them by the size of the tree and you get the average. So, in this case, the pi the proof pi is going to be is going to attest to the fact that this is the specific moving average at the specific instant. So, let's say that A0 when A0 gets replaced by A8, you can just change that specific value in the vector and recompute everything along the path from A8 B8 to the root and only those values have to be updated while reusing other

values and other proofs and other results of the Merkle tree and the rec proof tree that wasn't touched. So, that's the general flavor of things. So, once you have a moving average style approach, you can try to generalize this to compute standard deviation which is a useful metric in other scenarios where you want to compute the volatility of some specific option and so on. So, you can use such such techniques to do it. So, a new way of doing it is just to follow what we did in the map in the moving average example, you compute the the total sum and then you can use them you can use the mean to

to compute the standard deviation. Of course, there are clever ways you can go about and computing this and so on. So, in general, you can generalize this to multiple any making to to prove queries over any storage slot. Say that there's a game if I contract that wants to query some other contract based on some predicate. For example, you want to select star from some specific contract where the owner is XYZ. What you would do is you would just filter out the values based on the specific predicate in this example is going to be owner and then build build a rec proof style batch proof that's going to not just

attest to the subset of values that are in this tree, it's also going to attest to the fact that you filtered correctly and so on. So, jumping into the examples of other examples how where you can use rec proofs in a little bit more detail. Say that you want to aggregate BLS public keys. So, say that a smart contract has validators and the public keys are stored in each slot. Now, the goal is to compute the public key aggregated public key of a subset of validators and you also want to compute the size of the set at the same time the set can change across blocks. So, this is useful in emerging applications

in new blockchain systems where the number of people who signed in at this instance might might not show up the next one. At the same time, you want to compute an updated batch proof at the same time an updated aggregated public key that can be used to verify if certain threshold of people have signed a particular message at a block. So, in a little bit more detail, so we want to compute the aggregated public key APK and out of and we want to make a claim that T out of N public keys have signed this and the Merkle digest of such public keys is actually C.

So, it follows the same recipe which I've been showing you. So, you have these public keys in at the bottom, you first compute the Merkle root digest, you perform let's say that this example K2 K4 and SK5 have signed it, then you just perform the first operation in this example is going to be map where you there's just one have signed so far at that specific level so it's going to be one comma the public key and when you go to the next level, you can perform a reduce operation which takes in the results from the previous level. So, in this let's say if you look at the subtree of four and five, you can see that the count is going to be two which says that two nodes

two public keys have signed under this subtree and the product of those two public keys is the the aggregated public key for these two two public keys. You can keep doing this until the top while attaching a snark proof set which will attest to the fact that you have done this computation correctly at each level. And the previous level at the next level you'll also check if the snark proof is correct at the same time if these results were done correctly. At the end, when you have at the top, you would the count is going to be three three public keys have signed and the product of them is going to be the aggregated public key and pi is going to be the proof that attest to the

fact that the map and the reduce operation in this tree were done correctly and the value values you have received is in fact correct. So, in fact, another example of using this style of primitive is doing something called as a digest translation. Say that you have N values in the vector and and you compute the Merkle digest using a hash function H1 which which has which is used in let's say in the base chain or something where with strong security properties such as SHA-2 and so on and it also is has been optimized at the machine level.

However, at at the when you want to do something like a roll-up, you would preferably want to have hash functions that are snark friendly. So, let's say that you have another Merkle digest CC2 which is computed using the hash function H2 in this example is going to be say like something like Poseidon which is snark friendly over the same set of data. We can prove that we can prove that these two digests were computed using the same N values. So, this particular example of digest translation is useful in roll-ups as if you want to compute an inclusion proof at the roll-up level using SHA-256 256 proofs, it's going to be more

expensive to verify. So, to be a little bit more in detail, so Merkle digest C1 and C2 computed using hash functions H1 and H2 respectively correspond to the same N values. We want to prove the statement and and it is useful in roll-up style applications. So, the recipe is pretty much the same as you would have guessed. So, you would you would essentially compute the Merkle digest using C1 which is already there in the base level C base level and then you would perform the map operation. In this case, it's going to be the identity operator and you perform reduce operation which is going to be using the hash function H2 which is

going to be snark friendly. In the end, you're going to have another Merkle digest C2. It's essentially it's computed using the hash function H2 and the proof pi which states that C1 and C2 were computed over the same set of data A0 to A7. So, in essence, you can use rec proofs to perform many map reduce style computation. One key aspect which I did not touch today was how do you extract how do you probably extract, transform and verify and so on.

So, that's for some other time. But once you have the data transformed in some particular fashion, you can you can run rec proofs style proofs to compute that the computation was done correctly and the values are indeed correct. At the same time, you can generalize this approach to in multiple directions. Let's say say if you want to change the arity of the tree so that that is in line with the actual let's say something like Ethereum or so on. You can consider doing that. You can for example in the example which I gave you about the digest transition the trees might not be have to be have the same structure.

You can think about further extensions to direct proofs and yeah stay tuned for our subsequent releases about this work. Amazing. So on that was that was once again super educational. If you don't mind keeping the the slides on the screen because I do have a question Of course of course. on one of the slides.

Um I've actually had uh I've had a comment about entropy in my Twitter bio here for for a little while. Um so I'm curious if we could go it was relatively early maybe maybe like middle early in the slides. Um And I remember the slide it said that that this proof format yeah here we go. So helps to keep low entropy in storage state between blocks.

What does entropy mean in the context of of blocks on the blockchain? So I was referring to the standard example of entropy as a measure of randomness meaning let's say that you have a state at the end of some block and the the only transactions that are going to happen on top of the state is going to be the one the transactions that are included in this. So and the number of things that can go inside is going to be limited by the amount of transactions you pack. So it's going to be some few small updates that are going to make changes to this to the state and at the end of this you're going to be transformed to the new state and yeah that's going to be the the most

up-to-date state. So you don't have to be worried about many things changing simultaneously we will have to be worried about a reasonably few things. I'm not quantifying anything but it's reasonably few things that are changing and essentially if you just replay all of these transactions you go from Genesis you would you would end up with where you are. Yeah. Okay. That I guess a quick follow up is that because the Merkle tree extends the the the the leaves of the tree only in the direction where there's an update to the state? Let's say that the transactions you know on the left side of the tree don't have any updates to them then they won't have any more leaves any there's no more complexity on that part of the proof. Yeah one way to think about it is

like let's say that you have all the slots and not all slots might change simultaneously only few slots might change. Just forget about right and left it's more about picking a few slots and only few slots like might change based on value and when you have such changes you can when such changes are happening to the blockchain data or the state you can map such updates even on the direct proofs style. So you can make such changes is what I was trying to convey here. Cool. Okay.

I think I understand. Got you yeah. I've got one as well I think maybe close to slide 15 or 16 if you could go over there as well. Uh one more. Yeah so this equation here has has a lot a lot of of pieces and to understand any of these equations there's obviously a deep deep level of math and cryptography you know experience required but I'm curious from a like a personal and from an academia perspective how how you're able to kind of take equations like this which you can formulate on paper you know and through programs and proofs and then kind of translate that that

theoretical and and and and kind of proof based math onto onto like a a code language and perhaps not asking that correctly but I guess what I'm curious about is is taking this math and implementing it into the code that is required for for you know for a ZK proof. Yeah so I have the privilege of working on both sides of the aisle. So first when you come up with some scheme you're going to formally write down with let's say with certain set of mathematical properties. Let's say that let's take a CC commitments for an example a specific property about polynomials that are being satisfied every time when you give out an evaluation proof. So now once you

have something like that you would try to prove why it's correct. So you would go through the start exercise like like in the standard cryptographic class you would go through the start exercise of saying that hey if the adversary can break what are the possible other if someone can break the system can I just translate this attack into breaking something else. So what we would typically do is like we do write some sort of saying that reduction saying that hey if someone can break this they can also break the some other cryptographic assumption and once and we know that that assumption is not broken so and we retrace back saying that you can't do it. So um uh and once you have formally have proved and done these

uh from formally prove the protocol then comes the the fun part of bringing it to life in the real world. So at that point I it's more about finding optimizations doing finding out if there are any gaps in the way the protocol is written or in the or the way something a some case which was not covered or and so and so on. So that comes up during when you actually implement you would see hey this the performance of the system and and and this is what we expect. So and this is a very bad with this slide is a very bad way of giving specs. When I want to write some protocol I wouldn't want to be abstracted this level. I would want much more at the concrete level. There

are many ways to in fact to implement a standard deviation and standard deviation is fine but when you want to do something like a SNARK system there are so many ways to do all of the protocols that are listed and with each being really fast versus really slow. So you want to make sure that use the appropriate tools and so on. So it's a beautiful process like from writing the protocol down to them bring bringing it to life and writing code. And it's more about playing the role at each part like writing the best code when you do it making sure that when you write the protocol you're thinking through that everything was done correctly and formally. So you have to wear multiple hats. I'm sorry if I'm not sure if that

answered the question. No yeah it's yeah it's it's clear that it's a multi-step process requiring different kind of ways of thinking which is why it was super interesting to me because to me it seemed like the way of thinking of deploying contracts on a blockchain is definitely different than the way of thinking of answering you know a proof for a for a kind of math equation. Yeah I'll I wanted to touch more kind of on some of the on some of the earlier slides as well if you don't mind. Sure sure. I think around like slide five or six maybe.

Um we talked about the membership proofs. Efficient batch proofs go to Yeah this is an interesting one. Okay yeah so so yeah direct proofs this was the one. So basically I'd like you to explain why using recursive SNARKs and I think you did that you that you did a pretty good job in the in the slide here but the the recursive SNARK aspect is interesting because it's something that you know that we've heard about with something going back to all the way like Zcash right all the way back to that kind of technology and then now I know Starkware it is you know pioneering this kind of recursive SNARKs and they even got they even have STARKs. But why why is using recursive SNARKs the go-to

way to basically establish these batch proofs so just why is that technology for for these proofs so you know prominent I guess is there is there is there other technologies that are as good or as battle tested as well? So you are essentially in the using recursive SNARKs when you want to prove about a previous SNARK that was computed. So when you when you run counter such scenarios your best bet is using something like recursive SNARKs and go about it. So um and in in the in the context of direct proofs essentially what we do is let's say that if I want to compute pi LL I want to prove that the previous subtree

was done correctly. So rather than doing every tracing it all the way back to the leaves I would simply have another proof that says that pi LL is correct. So if pi LL is correct then I know that whatever is inside that is correct. So and pi LL has to just make sure that whatever is happening in that specific level is in is in fact correct or not. So these are the examples SNARK is able to sorry it's able to to basically prove that that data happened in that last block or in that last for lack of a better term section and then kind of transport that back in forward into the next section to kind of keep the the data in the chain valid.

Yeah exactly that's a very nice way to think about it. Just making sure the previous checkpoint is correct and so on. So recursive SNARKs have been very ubiquitous and people have been using it for variety of stuff. However there there is we are moving at a stage where the performance is have tremendously improved since 2008 when people thought started thinking about proof composition and so on and we are at that exciting times where there are plenty of ways to do recursive snarks.

One one is like you can write it inside a circuit. There are new schemes like folding schemes and so on. So there are new ways to think about how to prove something about the past. And and yeah, that's the I'm very fortunate that the state of the art has been coming forward with with a lot of great minds. I'm happy to be using them for my work. Yeah, that's awesome. Yeah, thanks thanks for that answer. That makes it super super simple and that's kind of what it's about for us here with with this entire series and with this with this video and speaking with you is some of these concepts obviously are quite high level and they require years of academic studies but being able to kind

of put them into the the the terms of of something like a checkpoint or something like understanding how blocks are are kind of processed and created on a on a blockchain. Yeah, it kind of illuminates that you know, while this is definitely out of reach for perhaps from a coding or math perspective from a from a high level understanding perspective, you know, it's certainly not somewhat unattainable. So thanks for that. I think one more question if you want to flip through the next slide or perhaps Rob has one but I think I've got one more if you have a more time.

Sure sure. Through through this next one too. Um Okay, so I through this one. Okay, so yeah, back to back to kind of this state here and I know Rob asked about the about the about the entropy but I'm kind of more curious about the diagram that's that's happening here. And basically what what we're seeing is is kind of explained in these in in these bullets but when you say Genesis, is that like the beginning of of the block or of the chain? Yeah, so a Genesis block is where it all started, right? Bitcoin has the Genesis block and so on. So essentially all of us agree that this is going to be the first block of this blockchain.

And from there you keep mining new blocks on top of it such that all the way you when you trace back, it all the way points to the first Genesis block which we agreed on. So and the figure which I was trying to go for here which essentially says that hey the state is essentially going to be you can think of it just like a fancy way of thinking about it. I mean a simple way of thinking about it is just a table. You have some indices and you have some values and the when it's a human, it's going to be each index is going to contain an account balance. If it's a smart contract, it's going to contain some some information about the state of the contract. So this is the only absolute state

that is relevant right now and when you want to make statements when you want to make statements about anything about this the state and how does batch proofs help? That's that's where I was getting at. The figure is more about putting them all together. You can't put the entire table in the in the in the block so you want to have a small digest some nice way of representing them and that's where Merkle trees, Merkle Patricia tries and such cool data structures help us do it. I'd like to point out one thing.

Yeah, one thing about this diagram that I'm just noticing now is that the arrows between the Genesis block and block B are actually pointing backwards in time. So we're this diagram is to show the proof mechanism of proving the validity of block B because you can trace these proofs all the way back to the Genesis block. Yeah, exactly so when when I mine the block B, I I would make sure that I would take the information from block B minus one, I would put them in the current block and then I would actually mine block B. If if you're more familiar with proof of work kind of idea, so you have to take the hash of the block B minus one, put it in the next one and only then you try to mine and so on.

This is this is a common case with every every blockchain where we pretty much want to attest to the fact that I'm building on top of B minus one. Yeah. Yeah. And then the the concept here in the middle in the middle about the state tree containing account balances and contract storage, this is something that that I've heard in various podcasts and I'm sure people who are listening have heard of the the blockchain state and you kind of described it as as as indices and kind of tables of data. So so how what's the best way to think about the blockchain state in like an abstract way that's that's like understandable? I I know it's tough to kind of just throw that at you but like what is like in the in the

realm of the chain of of blocks and and of the transactions in these blocks the state of the blockchain is thus represented by the account balances of the of the actors or of the wallets or of kind of the ledger and the contract storage. Could you kind of illuminate on on the state Sure, sure, sure, sure. Let's for the sake of simplicity, let's forget smart contracts on our day. So and it's just like a classical system where I want to transfer money from one user to another.

So I would have I would have let's say let's consider like going to a centralized bank or something. One way to think about when you want to do something like in a centralized bank, there's a huge fancy Excel sheet that says that some there's a going to be a column on the left, it's going to be have some information my ID saying that this could be my ID and this is the balance I have. It could the next row it could be the ID of yours, then it could have some some specific balance. So you can have this entire huge table. So when I want to transfer money, I would all I have to do is say that hey, I want to transfer few dollars from my account to your account. So at the end of the day, the transactions change this

table by moving value from one to another. And you want to make sure that I can't transfer more than what I have and so on and that's where the validity of these things come into play. So it's it's a glorified way of seeing this is a huge table. One one side contains the IDs, the other other side contains the the the account balances. And you can start generalizing this using contracts and so on. You have some information address about the contract and you have the digest about the contract state and and you can do this.

So that's the fundamental building block of accounts based blockchains and and when I mean the state, I essentially glorified way of referring to this huge table. That's what I do. Yeah, and then this this huge table this huge table basically takes up storage. Like it it is data which requires storage. And so when when when I'm going to extrapolate this all the way back to like a ZK roll up or or roll up. When a when a when a transaction or sorry, when a block is is then produced and and in this sense in by a sequencer or by some entity and then then is is

being redistributed back to L1 to to basically go to Ethereum. The state of the block in the ZK proof, that data is is is is that the reason why you are paying to then um process back to Ethereum? Like you're paying to take this data in the state of the ZK proof or of this kind of block on let's say an L2 and you're paying to put that data back onto the main chain. That data is the reason that you're that you're paying or it's the Ethereum block space but the data that you're transferring is what's in that proof and I kind of answered that there myself.

You're paying to the Ethereum block space but the data in the state is what is being transferred to L1 in a sense or am I kind of missing something there? Yeah, yeah, you are correct. Correct. Essentially, you can think of it like the smart contract has its own ledger that's part of the big ledger which I was talking about. So when we make transactions within the roll up, we just modify the small ledger at the at the contract level and that essentially when you make bunch of changes like you, me, Rob and so on. So when you make such changes, table gets updated and we want to reflect this back to the the master table which is going to be the the the the one at the at the L1. So and

we and yeah, we have to reflect this somehow and yeah, just like the way you said, we have to incentivize miners to do this and that's why we end up paying some some fee to uh to the person who does this for us. Yeah, thanks. Makes sense. So Yeah so that's the blockchain state. The state is an interesting way to state an interesting word to describe what is encompassed by by the states. Perhaps um Yeah, I'm not even sure what you could even say like a storage ledger or something. One of the ways that like we've talked about it before is like the constellation of all the account

balances in this table. Like the like the the configuration of accounts and balances at any given time or any given point like is considered the state. It's like the status of each account. Is that Sherwin, is that is that fair to say? It's a Yeah, sure. Yeah, you can the current uh state of essentially what what values do you have in that. So, yeah yeah, coming back to your question, Andy, so people used to classically call this a state machine replication. And with Bitcoin and so on, they started calling this as blockchains.

Uh yeah uh Oh, that's how that came. Yeah. So, the the abstraction which the classical literature was trying to give is you could have 10 machines uh running some piece of you could have 10 machines, but all of them should give an illusion that they're just one single monolithic machine. So, when I interact with it, I shouldn't be I shouldn't I shouldn't know that there are 10 machines that are going underneath. And any of these 10 machines could fail and so on, but at the for the for a user at the external level, it should pretend as if it's just one machine. So, and how do you do it? You just make sure that every machine keeps track of the keeps replicating the steps of

computation that needs to be done and so on. And that's how people called called it back a while before Bitcoin. And now it's it's going to be now it's called as blockchain. Yeah, and I speak one not blockchain. Yes someone. My my last question here is um basically can can I imagine this block be Let's say this is um let's say this is ZK-Sync era, right? Or ZK roll-up which can fit here, right? And so am I right to say that application one, it being Uniswap, application two being Aave, three being three dots, nobody likes that one anyways, and four being um you know,

some other So, each of these apps contribute the state in that time period of that block a unique ledger, if you will, which is then basically bottled up or brought together through through the Merkle tree and then all put into one state. So, it's so that you know, the the two ledgers of the first application state come together, then application one and two come together, then two, three, and four, then all into one. Is that like what Is that what is like happening when these when these blocks are being created and the states are being pulled from these these different applications? Or or is is is that all?

So, I'm I'm I'm simply uh what you said is pretty much the case in genetic scenario. But uh the specific slightly differ like I assumed it'd be a binary tree and so on. So, that is not the case. Ethereum, for example, has its own data structure. Uh it has a different kind of uh tree called a PT tree and it has uh it uses such an such ways to organize the the the updated state and so on. Yeah, that's the that's a nice way of thinking about it. The These are slight specifics which we can figure it out once we are actually coding it. But at the at the abstract level, we can simply think of them as a binary tree and we can keep doing it. Um

values could change, some values might not change, some contract might not have changed at all in this particular block. So, it will still have the same previous state what it had. So, uh for example, one of the Uniswap contract would have changed, its state would have changed, then you would have just updated that specific uh that specific uh address. So, yeah, that that's what I was going for this figure. Yeah thanks. So, it is clear that you you understand blockchains at a very very deep level.

And you've done you've done so. I mean, I I think so. And you've So, you've done the research to understand like the components of and the elements of of like the both the proof mechanisms and then the architecture overall. My question is what is the goal of your research? So, now at Lagrange, we are very motivated to have the best system out there to do data parallel computation. So, when you want to run arbitrary queries on blockchain, say some some information about the past, whether it's it's historical or whether it's current one, what is the best way I can give you a

proof that says that this computation this query was done performed correctly and and and and you can use this without pretty much lot of overhead. So, just best way to think about it is how do I do verifiable map reduce the blockchain data is one way to think about it. But it's more about generalizing it to arbitrary queries and how do we go about doing it the best way is what I spend most of my time these days thinking about. Very cool.

Yeah. So, a general purpose uh machine for recognizing and proving data across state replication machines overall. Yeah, it's There are so many layers to it, but in pretty much essentially, we want to uh run queries on top of blockchain data. And how do I prove it to you in a verifiable way? And it it has applications which, for example, the ones I listed here. And I'm hoping that our viewers are going to send us few more and what they think they are useful for them.

Yeah, I mean, what it what immediately comes to mind is a form of data availability similar to Celestia. I mean, I'm sure you thought about something like this, but if you have like inputs of data, then you can also provide you could prove that data to these blockchains um because if you're proving like if you're making queries and you're proving those queries from the blockchain, it makes sense that you can almost like make that backwards compatible so that you could then like supply the blockchains with data as a data availability solution as well. Yeah, so there are numerous challenges in thinking through all of these parts.

But yeah, one way to think about it is like yeah, you have this data and can I just make queries on it and answer some specific thing that is in of interest to me. Yeah, that's a very nice way to think about it. Awesome. Well, I'm all out of questions. Um Thank you so much for giving us four hours but I really appreciate your time, Sriram. It's been a pleasure. Um you know, they don't teach you this in college. Well, maybe they do, but they don't teach you this in any other place other than the roll-up. So, thanks for coming on, Sriram. It's been a It's been an absolute pleasure. And uh it was it was enlightening and very educational.

So, thank you. Yeah, it has been a pleasure to talking to you guys. Yeah, I enjoyed both of my uh talks with you guys. Thank you. Likewise. Cheers.