Episode 333 - Verifiable SQL, Reckle Trees and ZK Coprocessing with Lagrange Labs

Transcript

[Music] welcome to zero knowledge I'm your host Anna Rose in this podcast we will be exploring the latest in zero knowledge research and the decentralized web as well as new paradigms that promise to change the way we interact and transact online this week I chat with Ismael the founder CEO at lrange labs and babis chief scientist at lrange labs and co-director of the applied cryptography Lab at Yale University we revisit the concepts of ZK powered co-processors and dive into the work that babis has done

previous to joining lrange on verifiable SQL we then learn how this is incorporated into the lrange co-processing system the work that they're doing on recal trees future work and what all of this enables for dap developers we also discussed their new Prov Marketplace The General state of infrastructure and how they are Keen to bring more Concepts from general computing into decentralized blockchain systems before we kick off I want to share a message from one of our recent ZK Summit 11 sponsors the web 3 Foundation they are bringing back the legendary web 3 Summit the next Edition will be happening in Berlin from August 19th to 21st this is an event designed for Builders and researchers to collaborate and hack together and it's

programmed by the community in fact I put together the program on one of of the stages on the 19th which will be a dedicated ZK stage and we have some top speakers from the ZK ecosystem who will be presenting there you should head over to the web 3umm it.com to see the program as it's being confirmed and grab your tickets today they're offering a discount for listeners of this show we've added the code in the show notes so check it out now Tanya will share a little bit about this week's sponsors namada is the shielded asset Hub rewarding you to protect the multi-chain built to give you full control over Shar ing your personal information namada brings data protection to existing assets applications and networks namada ends the era of transparency by default

enabling shielded transfers and shielded cross-chain actions to protect your data even when interacting with transparent chains namada also introduces a novel shielding rewards system by holding your assets in a shielded set you help strengthen nada's data protection guarantees and collect n rewards in return namada will initially support IBC and ethereum based assets but will ultimately serve as a single shielded hub for all assets across the multi-chain learn more and follow namada mainnet launch at n.net Alo is a new layer one blockchain that achieves the programmability of ethereum the privacy of zcash and the scalability of a rollup driven by a mission for a truly secure internet Alo

has interwoven zero knowledge proofs into every facet of their stack resulting in a vertically integrated layer one blockchain that's unparalleled in its approach IO is ZK by Design dive into their programming language Leo and see what permissionless development looks like offering boundless opportunities for developers and innovators to build ZK apps this is an invitation to be part of a transformational ZK Journey dive deeper and discover more about Alo at al.org and now here's our [Music] episode today I'm here with Ismael the founder and CEO at L Grange Labs as well as babis Chief scientist at L gr labs and co-director of the applied

cryptography Lab at Yale University welcome to the show both of you thank you so much for having us Anna we've been a big fan of ZK podcast for a while and we're very excited to be on it a thank you Anna all right isma I want to start learning a little bit about you we actually met a few years ago when I think when you just started or you were just kind of like bringing L gr Labs out into the world we've also met through a few events but I want to hear a little bit about what Drew you to this space what got you excited about it yeah is there a specific problem that captured your imagination yeah what got you here so before I founded lrange earlier in my career I was a sity engineer and I worked on building onchain Defi and

social F applications and I continued to run into a rather intractable set of problems problems related to how an onchain dap can access and compute over data how can I determine my most loyal users and so as I bumped into these problems I started kind of thinking of what would the solution to these be and what it turned out to us was that the solution required some really fundamental Innovations in applied cryptography and so I was looking around the literature and I came across some of babis's work in particular some of his work on vsql Integrity B um hyper proofs balance proofs and I reached out to him and I think over a period of time Babas

and I started building a relationship and a lot of the the form of lrange has been designed and and created with this idea at its fundamental that innovation in authenticated data structure design and zero knowledge systems enable us to do things on chain that in the last generation of crypto applications was untenable what era were you as solidity Dev in is this 2017 no it was like 2018 2019 it's like um 2020 and then I I left a little bit to be a VC at a SAS fund yeah I went the wrong way um and then I had to go back you qu you Rage Quit crypto and then came back at the wrong

time right I I rage quit when stuff were going up okay I'm glad you corrected that you know trajectory fast enough were you going to hackathons and stuff at that time um a bit I was at a insurance company based out of Boston manual life John Hancock okay and I led engineer ing for their digital asset strategy um it was early decentralized Insurance products we were trying to use at that time zero knowledge proofs like early systems like zres to rein proove properties about baskets of policies that were merized on chain to be able to underwrite reinsurance vehicles um from liquidity pools wherein you could ensure some basket of policies where the desant data could be kept private but you would

be able to understand that you know there was there was some claims payout and there in the pool had a draw down on it H so then you left for a moment and then what was the exact thing that I mean it sounds like meeting babis and seeing that work kind of Drew you back in but yeah was there anything else that made you make that choice I mean I love crypto I I love the fact that we're solving problems that are foundational to Global Financial infrastructure that are foundational to kind of how I see the world working I I can't imagine a world where crypto is not a dominant force and for me it it didn't feel rights to be in any other industry cool all right bavis I want to hear a little bit of your backstory it sounds like you

were maybe correct me if I'm wrong but were you very much in the academic world leading up to your joining L gr Labs right right so my story with crypto started uh back in Maryland so before Gil I was a professor at Maryland and in the lab that I was part of it was Andrew Miller who's not professor at yeah University of Illinois he was starting out with his PhD student he was particularly excited about blockchain and cryptocurrencies and really it's uh because of him that I learned about this film we talking about 2013 right so so he was bringing a lot of excitement he was teaching us about Bitcoin and you know this is how I kind of learned about the space and then as years went by and

you know traditionally in my PhD I've been working on authenticate data structur so that was my PhD back in 2011 so I saw learning about the space that all of this techniques and data structure I've been studying are being used in blockchains and cryptocurrencies and then more more formally I got involved in 2019 in real crypto in Switzerland where yeah you know I met some people that kind of were interested in this in this authenticated data structures and uh you know Vector commitments and then of course when ismaile talked to me you know I got really interested to see what will be the application of my research in this in this Real World Systems when you say authenticated data what kind of thing does that like what does that mean

does and is there any like ZK overlap with authenticated data or is it very different actually so I meant authenticated data structures yeah so I worked on authenticated data structures back in 2011 uh so one authenticated as for example is this miracle Patricia TR that ethereum is using so it's basically combining data structures traditional data SES as we know them with um security right so how you verify a query that you can make on a data structure which is kind of a very very simple tythe of zero knowledge proof system right so it's like verification of a very very primitive computation yet get very important what was the work that kind of nerd sniped ISM or that where ISM decided to nerd snipe you what was

what was that specifically yeah so from my standpoint I think the question of how you can compute it for blockchain data specifically with zero knowledge proofs is constrained by the data structure of of ethereum and and that most evm compatible Ro UPS use the MPT tree where you have non-finite field friendly hash functions like ketak and you have rlp encodings for for serialization of nodes that make it computationally intensive in a circuit to prove the inclusion of a large subset of leaves within the tree in a current block or historical blocks and I think we know I could see the problem but it was very hard for me to identify a solution and with abbas's work in

particular hyper proofs balance proofs vsql Integrity B there were a lot of examples I saw in the academic literature of being able to devise ways to address these problems and other circumstances that I felt were not applied into crypto from a research standpoint people in crypto were looking at it solely from an engineering standpoint of how do we take the current tools and simply build something that hopefully works and nobody was going down to First principles on it and that's kind of was was the impetus behind me originally being nerd sned by this you just mentioned vsql and then what was it hyper proofs yeah what what are those so if you think about the work of authenticate data

structures that I did this is kind of preural to this vsql in authenticate data structures what you're trying to do is um you have a commitment to a set of data say like a binary tree and you want to verify some sort of query on this binary tree for example give me all the leaves that fall between this range MH okay so we know how to do that with meral is very very well studied and that was part of my PD thesis uh at Brown now the next step as I started my faculty career was to look at more complicated queries which is databased queries right you're not only doing ranges you want to do filters you want to do joints you want to do you know various group buys

various database operations mhm and really the public statement you have is a commitment to two tables right you have like commitment to two tables and you wanted to just run some queries queries and get proofs for the correctness of the answers right yeah so I started thinking about this problem starting out so we build Integrity B I think back then there was nothing about databases there were some sort of attempts from a database Community to build these verifiable systems but they didn't seem to scale that well because the cryptography that was used was not too sophisticated so we buil Integrity B which was the first verifiable database system that was handling a very limited subset of HL queries then we we went on and we built vsql which was a more more General

verifiable database system based on the S proving system so that was back in 2016 and after that you know I always that's a very very hard problem I always wanted to make more progress but I'd never kind of found the motivation and the right application to to attack the problem to to to to its full extent okay so then you know this whole notion of computing on blockchain data came up and then you know with ismile encouragement and you know as I was convinced that this going to be important started like working on the problem again of how to do things much much better so this is actually some of the work that we're

doing now very cool on verifiable database which is the perels that hopefully I'll have the time to talk about can I ask you some history questions like some Computer Science History questions yes sure Merkel trees the initial Merkel tree when when is that from actually so that is a a paper from Merkel in 1978 that's quite old yeah right and it was meant to uh it was cast as a digital signature as a way to has a message before you sign it okay and when of the Merkel Patricia tries introduced after this paper in 1978 there was no I I think that was it nobody talked about Miracle Tre I think about 1996 there was I think a paper by mon Devon bu that

they kind of took this to a data structure level and then you know my advisor at Brown Roberto tamasia started working on authenticated structures but specifically for Merle Patricia T I think you know the knowledge goes out there that you can do authenticated data structure for any data structure right there was like sort of like a compiler to go from any thata and geta but I think the very first time we learned about Merle Patricia Tri when when vitalic introduced them for ethereum in ethereum yeah years ago we actually did an episode many years ago we did an episode about Merkel trees Merkel tries on this show but trying to explain it in audio only format is tricky um because

it's really good to see what this thing looks like but during that time or around that time I feel like there was also this introduction and I don't know if it ever took off but like I remember Benedict Buon describing I think it was like Merkel mountains or something it was like these like Merkel trees but you were like they were different sort of size they weren't like symmetric in a way MH right did you hear do you know anything about that I don't even know if that's like a thing I've heard the 10 but I don't know technically exactly what it represent I have to to read on those but uh right you can have definitely authenticated are not symmetric actually one of the things that we're innovating right now like Grant is the notion of authenticated AVL tree basically you have completely

unbalanced mercel trees where you can arbitrarily insert delete elements and use underlying AVL operations to rebalance so that you don't get really bad worst case complexities so this is part of the things that we're currently building okay I have one more history question of course and this is about SQL because you talk about verified verifiable SQL but let let's talk a little bit about what SQL is generally I know it's a very important computer science term but yeah right right it's select query language so probably databased person will be able to explain this better than me but you know I'm a cryptographer but I'll I'll give it a try I believe what happened was you know when back in the 60s I mean we're trying

to understand how to write programs right and then the only data structure so to say existed was like you know kind of like arrays where you can access data but people realize the power of you know organizing data right and data structure was one way to do it but you know when you have data that massive amounts of data need to go to disk you need to use some sort of like database right so then there has to be a way to quer this database and you know they develop this language to create databases which uh it's called select query language from what I understand it's one of the most dominal ways to deal databases uh these days and I mean I think you have this query already written into it I feel like it's really good we Define that

because leading into the G I feel like there's there's there's where some of the connection comes but let's now talk about the V part so the verifiable SQL is a language right when you add the verifiable how do you change it right so before you add the verifiable what happens like normal SQL you have a database table you write a query in SQL which is a you know a short program in a specific language and then you execute this query and you get back some data can be for example return the set of records that fall within a specific range okay this can be expressed easily as an hql quy so what we want to do now is we want you know if if this query is

run by an unrusted entity right we want to be able to verify this query without having to execute the query ourselves right also we don't have a database locally at hand even if we wanted to execute the quer ourselves we won't be able to because we don't have the database right yeah so what we have is a commitment to the database right it's a small meral has so to say so we're still sending the query to the person that has database the person has database runs the query but also attaches a proof to it similarly with with zero knowledge right so it's an it's a proof for the SQ query when I get back the proof and the answer and then having the only thing I have is the commitment to that

I'm able to verify that the answer is correct with something like this would you would you be able to run kind of SQL in a private environment and then use this verifiable SQL to like prove that whatever is happening in that private environment is done correctly right so I guess what you're alluding to is some sort of zero knowledge version of orl actually or just any or fi like any environment where there's no visibility would this be useful right right so so potentially as far as the is concerned if you're willing to make more assumptions about the the medium that trans the computation you can potentially build a vsql that is faster by you know leveraging trusted Hardware

so for example you don't have to not trust everything you might choose to trust some parts of the computation and in this way you can definitely build a vis that is going to be faster but in in what you've described the vsql this is all happening in the open so this is for right public data or like viewable data Okay cool so I think this has been really great prep to dive into L Grange because I feel like you know in in what I know of the project it deals with a lot of this stuff but Ismael I want to talk first about the history of lrange um when we met a few years ago I remember in my mind at least like this was a co-processor in the way that some

of the other projects like axium Herodotus had proposed it um has it changed from that would you still say that that that is what it is or would you say the project has evolved somewhat yeah so lrange is still a ZK co-processor um but we've evolved a lot how we think about structuring computation of blockchain data and so a lot of the concepts that Bas has been talking about about authenticated data structure design proving computation over authenticated data structures really get to the the basic question of you know you have a large amount of blockchain data that is provable with respect to any of the recent block headers and so how do you structure a meaningful amount of computation whether you want to call it

co-processing or storage proofs or receipt proofs or VM extensions over that data such that an application developer on chain can verify that some computation is accurate with respect to that commitment so to put that in a very concrete terms what is the moving average of price over the last 10,000 blocks on uni V3 what is the volatility of the price of an asset of you know eth to USD on uni V3 so I can do black trolls and issue an option like very basic statistical analysis or computation or historical data um You can call that co-processing you can call that storage proofs but at the end of the day from a research standpoint we'

think of this as compute over an authenticated data structure this is what I learned back when I was kind of getting my head around co-processors was like on chain and you actually alluded to this as well like when you're creating a Dap on ethereum you can't actually look at the history there's nothing in the state at that moment which tells you what has happened before and I think people have previously been relying on oracles and kind of like other means to get that information into their application because they need it sometimes so yeah in this case you're kind of talking about a replacement to that it's offchain where it's happening and then I guess are you using zkps to prove it on chain or using these verifiable like is it is it a different

model to prove it on onto the main it is zkps and so that is a very good way of putting it so in effect there were previous generation solutions that used economic guarantees or used kven solutions that were NPC based or te based to try to verify computation over onchain State and the limitation of this are always security it is if you if you have a mission critical function to your application that's underwriting hundreds of millions and in option issuance or in swaps every year you need to ensure that the mechanism that is being used to secure that is proportionately secure to

the risk of this being compromised and so with what we do with lrange we're able to verify that computation over blockchain data so when we say he you know a contract makes a call to our co-processor and says you know what's the moving average of price over the last 40,000 blocks for this asset pair what they get back is the result and a proof and that proof is verifiable with respect to the block header of that chain that's accessible in the smart contract which means that you don't have to trust any offchain parties you don't have to trust any nodes you don't have to trust anybody you can get back the proof and the resulting computation so it's you know don't trust verifying m but for computation of rchain data that

was what you kind of were at the start and that is what you are today I guess but has something changed as well like I I I feel like just kind of yeah where you live which ecosystem you live in kind of evolved a bit Yeah there's been a lot of things so we've had that central vision to LR since the onset but there's a lot of things over how we've altered the course of the business to ensure that we have as performance systems as possible so we Rec launched uh aover Network on top of a reaking platform aan that we have had a great relationship with for a very long time and we have now a very large set of decentralized provs who are participating in our proving process we

have this run by some top tier institutional improvers in the space including coinbase Kraken okx figment P2P who are participating in this proving process and the reason we did that is because we felt that we could scale the computation we do much larger if we have multiple parties in this network and we can guarantee liveness which was an imperative for a lot of our customers and our partners who wanted to be able to actually guarantee that if they need pricing they need volatility they need some reward program or co-processor issue some proof to them that that proof would come when they expect it but the Journey of lrange has been a lot of that it's been a lot of trying to identify the best way to accomplish this goal changing how we're

doing the cryptography altering to proving systems altering all of these components to be able to get to a scalable performant and coste effective as a system as possible for Rend users uh what were you originally going to be like before participating in the reaking side of things and like I I'm assuming this Pro network will be like an ABS chain right mhm before that though what was your vision for how this system worked like did you just not have the pr Network at that point was it just the co-processor and then you realized you needed this or yeah and and sort of where did it live or where does it live like the actual co-processor side yeah so originally we were going to do the proving in a we were thinking of whether

or not it was worthwhile doing the proving in a decentralized or centralized capacity one of the main benefits of the way we've designed our systems is that they're hyperparallel they're they're naturally paralyzable which means we can distribute computation over 100,000 10,000 nodes and be able to coales and recurse these small proofs that each Prov computes back into something that from a performance standpoint can scale much better than these more monolithic attempts to do storage inclusion and so because of that we felt that it was very naturally suited to being deployed in a decentralized capacity because we were

already doing it internally in a distributed capacity but the final decision from us really came as always down to our partners and our customers which was do people want their proofs to be computed in a centralized way do they care about liveness and what we found from talking to a lot of people is that they do and so we decided that we were going to deploy our Network in that capacity and right now the co-processor lives on that Network so when you get a proof from lrange you actually can go to our dashboard and see who computed it oh wow which I think is a very interesting thing you can see if coinbase dat you can see how many proofs coinbase dat in the day you can see how many proofs Kraken is doing you can see how many proofs okx is doing you have big

exchanges now who are actually doing proven so this is interesting that you've basically adopted the pro Network model there are some other teams that are doing Prov networks there is another class of project which are doing these like verification aggregation MH do you know these as well like I don't know if you've seen I mean nebra I had on the show quite recently they originally had proposed to me that they were more like a proven Network and have since moved much more to the verification side how do you interface with that or do you provide that as well like are you also looking at that other side of the I guess you call it like the zkp timeline or the what is there's a word that people use life life cycle

supply chain supply chain that's it yeah um so we we don't do proof verification I mean obviously our proofs are verified on chain and we are agnostic to aggregation or verification Solutions nebra is a team that we think incredibly highly of we've had a great relationship ship with schumo for for quite a while and a lot of other teams in the space we have a tremendous amount of respect for um what L gr is focused on first and foremost is a generation of proofs okay for our ZK co-processor for State proofs that we do and potentially for other proofs down the line but right now we have a ton of foundational Innovation led by vavis on authenticated computer authenticated data structures or

co-processing over how we constructure SQL quaries over data that we're co-processing over and so with what Lon focuses on is how can we be as performant as possible and deliver the best value to our end users in the domains that we specialize in to run on the pro network are the kind of Agents the provs do they need to run specialized Hardware to do that how are you thinking about that action of making the proof yeah so we have a a configurable set of machines that provs can run at the end of the day they just have to be able to compute the proof within the allotted time slot for that proof obviously if they have a GPU accelerated machine and they're able to

do those proofs far faster they can they can make up a larger component of the network if even if they have a giant machine with that they've they've deployed and they're doing CPU proving they're going to be faster than some with a small machine but the way we' design it since it's hyperparallel we can simply benefit from from that since we have a large number of different actors in the network they have agency to select the machines that they consider to be the the right trade-off of cost for performance and cost for reward um and so that heterogeneity means it's very very easy to join and then it's very easy to skip would would a like one of these provs also be able to just use like Cloud infrastructure though to do it like I'm just kind of trying to understand how big are these

proofs like is it like something that's like you need specialized Hardware to be able to do it or is it actually somewhat General and you can like do it on a lot of different systems sounds like it's the ladder it is the ladder so the great thing about the ZK Co processor in the system that bab has developed is the types of proofs that we have in particular with reckle trees and with the verifiable SQL work that we do are very small and because of that you can have a single node that is not necessarily the largest machine that can compute proofs occasionally and it can compute them at a rate that's far lower than what someone would compute if they're running specialized Hardware but they can still participate and we have actors in the network and you know you

have the p2ps of the world you have the figments of the world who have the devops they have the experience they generate very large proof or generate a lot of very small proofs and they can contribute to a greater extent to the network so just to put it in perspective over the last month we've had about 990,000 quaries across 60,000 um unique users primarily on defi gamey and within those proofs we've we've had about two million proofs computed within the network that are very small but are recursively combined together as part of recal trees and verifi constructions so the scale of what we can do this network is is is just churning out proofs right now is it proving system dependent does it only support certain kinds of proving

like something like plunc or something like grth 16 like are do you do you have to do anything on your side to be compatible with these different proving systems or is there a single one that you've chosen and you only work with that one um so in theory the networks's agnostic all of that the only thing that I'd say is that in the current state you know most of the work that we do on the network is is is for our co-processor yeah when we think of of proving very broadly right there's a there's a lot of pro networks not a lot of teams actually doing proofs right now and so with the demand that we have on the co-processor side is is what we are serving within our Network right now but nothing in our network is is fundamentally or theoretically tied to a given improving

system so you know a lot of the work that we do right now is with plony 2 and babis has has been actually doing a lot of interesting work with with trying to alter some properties of planky 2 and general cion overall but there's nothing that stops us from moving to different system down line so the system that we have developed requires recursion as an abstraction MH so in theory it can use any proving system they can do recursion in theory all proving systems can okay right but not all as well Theory because because in theory you can always express the verifier circuit as a circuit for the zero knowledge proof

system that you're using now of course we need to build a system so we're using right now for our system the most performing recursion out there which is plony too right we have research ongoing that tries to build the Next Generation recursion system so we're interested in a performance recursion this is this is very important for for what we're doing and planky 2 offers some features that allow for more yeah performant recre BL 2 does recar in less than one second oh wow so this is this is quite important for us and so yeah just to kind of finish off that question though on the on the different proving system so what

you're saying is like because you are the biggest customer right now of the proving Network like it's mostly your proof and you're using a plony 2 system The Proven Network can definitely handle that but if you did open it up to other I don't know actors or or like applications that needed this would you yourselves need to implement anything or is it sort of like system agnostic it doesn't really matter um we we have some very great teams in pipeline that we're very excited about hopefully announcing soon we'll be building other things on on the network but I think at the fundamental um we don't necessarily have to implement anything there's standard interfaces that the network abides by that as long as you can you reach those interfaces with the type of proving

system that they're using and all major ones would be able to then you can have proof served by it the only thing I'd say though is that you know within any system no matter how permission there is work that has to be done to deploy something onto it and so from a from a from that standpoint you know obviously we work very closely with anyone who's who is looking to work with our Network and with our team this is also living as an ABS as you mentioned what does that entail from your perspective like what do you need to do to lock into that system yeah so you know one of the things I think is is very interesting obviously is a paralyzation of of the types of proving that we do which means we can benefit from having a large number of protocol participants doing

that proving uh we can actually benefit from scale in that case right whereas the network scales to more and more actors we're able to actually have much more computation across it than you could otherwise pay for underwrite in a centralized capacity but within every Network there's a a fundamental question over cost of capital so if you require someone to stake where that's staking for security of a POS system or whether that's taking for maybe liveness of a ZK system which we built for example you have to incentivize that capital and incentivizing capital in any capacity is expensive right there's a risk-free rate and then you have to make sure you're higher than that risk- free rate and then you have in effect the the the risk you have to then offset for holding some

native asset the risk of that asset decreasing in price and so what you find for rates in the cosmos for example is 15 25% annually has to be paid on those tokens to have anybody stake them with an AVS because you're having eth staking and you have a principal cost of capital paid for by by native staking on eth the benefit that you get is is much much cheaper staking which means you can pay orders of magnitude Less in Admissions and fees and still derive the benefits and for liveness guarantees for your approvers so prove it asn't computer proof on time they receive an economic penalty but the amount we have to pay them in order to stake the capital that we penalize is much lower what is the exact thing that powers the ABS like the person the actor oh they're just running

provs they're running provs but like in the case of like if you're borrowing from like the igen layer security model restak it's I'm I'm wondering on that front and this is maybe more of a question about igen layer's system what do you call the reaking agent there oh you'd have you have rakers and then you have operators who run infrastructure and operators have delegated stake typically so are the operators would be for example coinbase they run our approver and they have stake delegated to them would that actor then be running two things like they'd be acting as an operator on the AVS side and then improver as well operator improver would be synonymous in this case okay I think people often think that ZK systems are more expensive than economic systems but

typically those analyses don't account for cost of capital ah and I think this is something that we should maybe talk about because if I say you have to stake you know $40 million I'm typically not including when I'm looking at how much I pay my user the 2% I have to pay on the capital cost I just offset that with emissions of my token and then I don't amortise that across user transactions and so the the the fallacy is that typically those things are are cheaper when they're actually more expensive interesting so let's shift back to some of the cryptography one of the top like and a few of these have been mentioned through the episode but yeah I think you mentioned something called like rle am I saying this right rle trees reckle yeah so Merle verle reckle these are not English word you can't find them in

dictionary Merle is the name of of the person that invented it so veral which came after Merle comes from Vector commitments and Merle trees yeah because they replaced the internal on commitment with a vector commitment that made the note wider so to say so we kind of rolled on this wave and we called our research this fundamental Prem that we propos recal trees okay from recursive arguments and Merle trees so the combination of Merle trees andar snark so it's Rec plus Merle reckle re okay okay so I think I like the term I don't know if Community liked it but I liked

it so you know I went for it so are you okay with it sometimes rhyming with Merkel though because then it would be Merl cuz you said reckle reckle tree yeah reckle trees reckle trees yeah Okay cool so what is a reckle tree so it's a Merle tree but instead of storing passes in the internal nodes you actually store recursive proof generated through a recursive snark right so if you think about a recal tree at the root instead of having the root House of the Merle tree you have both the root housee and another proof of a snark proof so what does this proof tells you right and so with recal trees

you can prove computation that takes place on a subset of the leaves of a Merle tree right so for example you can use recal trees to prove something along the lines this is the map reduced computation on a on some subset of this Merle tree right uh to give you an example how you can prove what is the count of elements of leaves in a Merle how many leaves are there that are greater than five for example it's a filter right so you can use this notion of recursively computed proof um to to actually uh compute the final proof of the and and this is what recal TR is it's h it's basically so to say like uh

I like to call it proof carrying data on stero I mean it's sort of like an application of proof carrying data so to say right so the the use of Rec snark in a in a d and directly graph which in our case is a miracle tree mhm I want to tie this back though to the actual use case for the Gage because right like it when you use those terms like leaves and stuff it's like is that an entry a historic data entry like going back to this idea of you're trying to use this system to like perform computation on EX like historic data is the is that happening somewhere else and then is being put into this tree and then being kind of like you create one proof out of

it or is it like happening in the tree itself so you have this data leaves okay and there's a question about those the question is how many are there that are greater than six for example they greater than a number so this is independent of the Merle tree let's go to like a tangible use case like there's a price you're looking to find or something would it be like the price is actually in that leaf so for example how provide a list of users that have greater than six if in their balance perfect something like that so that's the that's the use case okay okay but would it be historically would it be like who had more than this much a month ago we could do that I think the best

way to think we can think of a single tree and then we can think of how in effect all this MB an MBT tree is is a connection between all of these single trees so we can instantiate reckle trees both over a single tree and then over all of this historical data too but I think the first example the easiest to think of is just one tree and then we'll extend from there onto how we can think of this over historical dat perfect cool cool thanks right so basically someone can tell you there's this is the list of users that have greater than 6 e in their account right uh but then how can you trust this right I know all users exist in the system have a commitment so I want to prove that saying from this commitment this is the list of users

that have more than six e in their account so you know recal Tre provides a way to actually produce such a proof right so imagine any type of computation that you can run on the leaves of a Merle tree uh you can use recal trees to to verify the computation now I just want to be clear here re is not the only way to do that right we this is a snark we can use snarks to do this thing right so we can we can basically write a giant snark circuit m that verifies inclusion and trans the computation at the same time now so what Rec gives on top of this solution that this is a

dominant solution that has been used in the space so two things first thing the proof this proof can be computed in a massively parallel fashion the way we compute our proof is what we call naturally paralyzable and you know so basically it can only in theory it can complete in a logarithmic number of steps and it can be fully distributed the way we computers proof it can be fully distributed number two if you compute a proof and you invest a certain amount of work to compute this proof and something changes in the next block what recal offer is this amazing property of updatability of proof what recal tells you if you maintain a data structure of

previously computed proofs you don't have to recompute the proof from scratch if something changes so for example if you have a count of elements greater than six and you know someone goes out next block you don't have to run the proof from scratch you can just spend time proportional to the amount of change so these are basically so hyper natural parallelization which leads to a massively distributed system for computing proofs plus updatability of proofs which is really really important for the blockchain setting where you want to maintain proofs from block I to block I + one and typically the entropy is not that big so the changes the

changes are small there's two questions I have one is actually trying to still clarify one point that I was asking before which is like in the leaves are those individual accounts balances or are they like comp are they calculations already in the leaf in the Leafs you have data so think about so the EMP data so you take mer Patricia try it's data that is stored in the blockchain which can be like ethereum balances it can be like uh local data of a contract right so these are data that are exposed through a blockchain header right okay but now I want to do something with this data right I want to ask meaningful queries so this is where recal TRS come right where you allows you to make use

of the data and extract information in a verifiable manner cool don't snark use Merkel trees already though like but not reckle trees not the recursive version usually not all snarks use Merkel trees for example growth 16 does not use merel trees but they are snark for example Ones based on F yeah like plony two they're using Merle trees as part of the proving and verification algorithm so the pr needs to use a Merle Tre to commit to the witness and the verifier needs to open you know to verify some proofs uh on this commitment right so this is two different W yeah yeah but on when you add the reckle trees you're just it's the recursion part that's being added what does it add what does

it change like what benefit does just that part bring adding recursion you mean yeah like having it be a a reckle tree instead of a Merkel tree right so Merkel tree you can only prove inclusion of a okay okay recel tree allows you to prove arbitrary computation on this Lea got it that's the difference right that's that's that's the main difference it's it's basically the way I used to call it when we start working that is Merle trees for computation and actually I was considering this this title for the paper but eventually I didn't use that I I I went with recal trees cool Isel I know you've had something you wanted to say for a moment for a while there but I wanted to get those questions in so to add a really concrete

example of this I think Babas mentioned you know e or we can think of usdc like an erc20 contract right where you have a large section of the PT Tree on ethereum in a given block that you want to structure computation so select all users that are the top 1% of asset balances or select all user with asset balance greater than than x and so what you want to do fundamentally is to prove this very quickly and then to be able to if required update that proof if you need to use it again so proving very quickly we get from being fundamentally paralyzable since the way we can prove this can benefit from the number of machines that it's running so if you think of the monolithic approach right I run inclusion proof on

slot one two three all the way to n and then I get all that data and I compute over that data it's expensive and then if I change one component of that I have to redo the whole thing from scratch and so in blockchains typically these are conceptually very low entropy data structures so between Block B and b+1 the majority of USC balances don't change and so the computation you've designed recal trees that is designed with recursive snarks only has to be updated proportionate to the change which is logarithmic which means that you can structure these very very big computations that are very very fast on every iterative FR one truly fantastic application of of recal trees is this notion of digest translation or consistency proofs on the blockchain

that we currently run these things are running on my grass Network right now so let me try to like say a few things about this so we want to remember our initial goal like grants is to run some computational blockchain data but as you know an blockchain data are katak based you know ethereum data structures use katak function which is truly truly expensive in snarks right so any any approach that tries to compute to run some snark and computation on cetch a cast data will will hit will hit a bottleneck right so one approach that we're using Rec for is to maintain this proof of consistency where we take the

the mer Patricia TR data structure based on ketak we transform it on an our data structure that uses posidon and we use recal trees to maintain a proof of consistency from the ketak based data struction to the posidon based data struction so all our queries are run on the posidon based data structure not on the K based data structure and we just maintain this proof of consistency between the two and this proof of consistency can be updated from block to block very fast because of the updatability property of of recal trees not too much changes right so we only need to compute a few kakes per block to maintain this proof consistency so I think in my view this is like really

really an amazing application of of recal trees and uh one we really have invested on right so the question over digest equivalence that bab has just discussed which is how do we take a large portion of the MPT tree and prove that that is equivalent to a now snark friendly far faster to computer or data structure is very relevant to a new line of work that we're doing called Perseus and it's verifiable SQL through decomposition um and so we we mentioned earlier at the start of this that that Babas has has authored a lot of the original Works related to verifiable SQL but is a new approach that our team has which is fundamental Tower co-processor works that leverages a lot of these

recal Tre benefits to do some things that were otherwise impossible in all prior works so so procel is is a new veryable database system that we're working on that uh is based on record trees and like I said the main idea of p is we want to be super general for hql we want to support arbitrary hql queries which by the way the previous work was also doing but I can't mention what was this is with the previous work so the idea of persos is remember recal trees is a framework that you can use to verify arbitrary map reduce computation on subsets of Merle leaves when we describe recal trees you know the paper is going to appear by the way in CCS

2024 in Utah in November so when we describe this work what we do in persus is we start with basic SQL operators like for example join uh Group by uh select project various filters and we take all of these and we map them to the map reduced framework of recal trees so we're trying to mimic how database Community deals with SQL quides okay the first thing that database compiler is going to do is going to take an HQ C it's going to decompose it to the Primitive operators that you can run in some sort of sequence and eventually give the output of theal query so we do

exactly the same yeah and now we do the decomposition and we have the verifiable operators and part of this we're doing is how to find the best m reduce mapping of this operators back to our framework so that we can use all the nice properties of recal trees like natural paralyzation massively distributed system and ofd datability and second is how to put all these proofs together which are not too many every hql operator can be decomposed every hql most most hql creu can be decomposed and I will say like six to seven SQL operators we have listed them in our table uh in the in the paper we're writing right now and that's how to put them together and compute an actual

single proof for every esql query so right now we're actually building that uh we're mapping we just finished mapping joints and we're moving on to map everything else so map reduces this framework where basically you do like some sort of computation on the leavs and then the outputs can be combined as you go up it's so interesting by the way as you go through this I'm just learning more about databases and how they how sqo Works in general like the idea of decomposing it I think must be very like obvious to you because that's how databases work but for me it's not so what it just sounds like is kind of like how co-processors were bringing one piece of the computer stack into

blockchain World it sounds like you're now trying to further bring some of those Concepts that have been well ver like well explored in in general computing and actually there's several interesting research challenges that come out of this interaction I I'll just name one because this is what something that I'm really really excited about so when you do this decomposition in databases you need to do this notion of result estimation to decide how you're going to decompose the query so before you run the query you need to have an idea what the result of an operator would be like for example if a join has a big result the first you time you apply it maybe you want to switch the order and but you don't want you cannot

run the query and then decide it right you have to right because then it defeats the purpose so you in databases they do this result estimation and they base the optimizes the composition optimization problem that is is solved using this result estimation now the interesting thing about our case is we have to run the query right we know what the results are so we can try different things because the main cost is actually Computing the proof right so this is something that we we can also explore in this uh in this notion interesting is that are you doing that in the work in the persus work or is that like future oh cool yes this part of the plan to build actually a query planner for very datab basis but uh I mean it's it's very very ambitious but uh we're working on

that at what state so yeah maybe just to clarify like persus is a paper that you're going to be presenting but like how far along are you in implementing any of this stuff the basis of persus recal trees is a paper accepted in CCS 2024 be presented in October I think in Utah Okay so the percel is a working paper that is based off recal trees that we're currently working on cool right so the main idea is there but you know it's uh but it's all of those things that I know where this is going it's just a matter of having good work e think just completing the work and just doing it I think our audience will will appreciate the tease I think they'll like that you're that you're sharing kind of what you're working on it's cool okay I think

also I wanted to mention from a product standpoint the the first version of the if iable SQL from via decomposition persus that bavis is talking about was on test a partial capacity now will be fully on testet for a a group of quaries that we're supporting right um that's entirely self-served where you can think of it like Dune but verifiable that only about six weeks away uh we have a engineering team that has been very very hard at work implementing a lot of these things you know one of the the things that we've been very lucky about as a company is we've been able to concurrently productionize breckel trees alongside the the paper and we are concurrently productionizing Perseus alongside the paper as well so this is not one of those situations where you

know you see the paper and you're waiting two years for it to be usable okay by the end of the summer people should have this entire Tech stack both something they can assess from an academic standpoint and read a literature on it and be able to actually use onchain in their products neat are there like analytics companies that would be using this kind of thing like you talk about sort of the applic ations using this information but like yeah would would an analytics something like Dune or something like actually want this as well or would they would it be easier for them to just go straight from historic data themselves so we've had good conversations with a dune team less someone actually consuming proofs since they can just index the chain and display the data to their users and they don't I don't know if they have a

requirement that their users want to know the data is accurate what we've had conversations mostly about is you know being able to actually offer that as a feature to a lot of users and this is something we're very excited about because we already have the usage of SQL within the blockchain context for how we visualize and think about data in things like nanson Dune Etc but we just can't use it in apps we can't use it on chain and so with what we're talking about now like the way I like to kind of describe it for people who might not be as as versed in cryptography is we think of you know a risk five zbm as being able to prove general purpose rust code you can almost think about this not from a academic or research

standpoint but just from a conceptual standpoint as a SQL VM where you can think of parsing the the SQL statement into how that would manipulate the data and then proving that without having to for example write a manual circuit for every little thing you want to do um and it just opens up the design space for what you can do across crypto rather materially in our view another question is how do you interface with l2s do you want to or do you yeah no we're live on three l2s right now we should be on that's this is the question when you say you're live on the L2 what does that actually mean your abs and the Prov network is living on the main chain on well on the igen layer stack and then your co-processor you said is sort of

like connected there but like what do you need to do on the L2 or or could people just access it already automatically so we we have a network of nodes doing proofs okay and those network of nodes doing proofs have stake that is recorded in a contra on ethereum but the proofs can go anywhere and the proofs can be of anything right and so right now we're live on Bas fraxel mantle and we're soon going to add support for for polygon ckvm arbitrum and a number of other uh chains that that we're integrating with and what what you can do is you can do two things you can a you can compute over L1 State and verify the proofs that were done over L1 State on L2 so what's the moving

average price on you swap on L1 you can verify that on Bas today because of how bass is built it lets you do that and the second thing you can do is is co-process over L2 state so what is a moving average of price in quick swap on polygon for example uh for some asset pair so you can do everything you would do on dl1 with your Cod processor on dl2 and that's partly because with the way we've designed a system with updatable proofs and with um digest translation it actually scales super super well for other execution spaces with fast block time and so when we typically have thought of co-processing most of these teams don't really do a very good job or

they they struggle to compute over L2 State they don't have access to being able to write their accumulators on chain and try to propagate all the information between them since we do everything in ZK we can actually just verify our proofs anywhere you have a block header when you interface with an L2 do you have to employ a contract there you sort of mentioned this accumulator so like you what what are you actually doing there we don't use an accumulator most of the other teams um try to do these like MMR accumulators where they just like try to they because they can't go back in historical block headers in their proofs so because we can do dig translation and scale things very well we can actually compute within a single proof back 10,000 100,000 blocks moving average we have a a query

right now that we support query right now we support over about a million blocks or a million storage slots and so we can really do these really big things and so because of that we don't have to do these like hacky Solutions in solidity that some of the other teams have had to do which means that we can just really deploy a verifier contract so entirely stateless on any L2 and then they can verify our proofs there's no need for these continued interactions and propagation of like weird things that some of the other co-processors are stuck doing because of issues with their star designs and that's sort of what I was trying to get at was like what exactly are you doing so you're saying there's like a verifier contract yes we we all we need is a single verifier contract for GR 16 snark okay on every

L2 that we want to support but aren't you using plunky 2 are you using we 16 okay o okay ah okay okay the final recursion I guess no no no we output plony to proofs but then we we do like I I guess a verification of a plony to proof within a gross extent right okay so you can view it as a f oration right cool the last question that I have is regarding sort of the target use cases I think every example that we've talked about today have been like Defi and dex's how are you thinking about the customer applications like are they primarily Financial do you have sort of a larger vision for where this could be

used yeah I think at its core user experience in crypto lacks because of the inability for daps to be able to reference data so every experience that we're familiar with in web 2 uses state from our prior interactions with that application with every iterative new interaction right loyalty programs signing experiences everything you do and so we can't do that on chain today and the experience that we feel therefore is these these very limited applications and so to make this concrete think of nft programs that give you rewards the longer you hold the nft or have

experiences baked on l2s that are entirely designed to to encourage you to continue to hold that asset you can think of points programs that reward you on loyalty both in terms of airdrop points and then in terms of continued issuance of like sushi Master Chef style defi points or defi reward bearing tokens and we can think of all of this as universal crypto we can think of gaming applications like onchain games very heavily require the ability to determine who their most loyal and frequent users are to give them experiences in that game that are suited for the amount of time or or the amount of effort that they put into that you know how have your historical sessions

been how many assets you've put in there all the way to gamble FY and things that people do there in terms of how they want to give rebates to to frequent users so the whole spectrum of everything you can do on chain could benefit fundamentally from better data access and so I think Define is the most concrete we can think of you deck incentives we can think of liquidity incentives we can think of pricing for options pricing for Lending but then we can go a level deeper and we can think of how a new generation of applications can be built without this idea that somehow we just can't access data onchain the same way we could offchain is there anything else that we should share before we sign off today last thing I want to share is you know one of

the things that we care a lot about at lrange is how do we both innovate on fundamental underlying cryptography and then how do we apply that in a product that people can use and use almost immediately after we're able to to come out with this new research and so we actually have a a brand new version of our co-processor that's coming out in early August that will let users for the first time in crypto actually structure SQL ques over large scale onchain state where they can Define their own Quarry the same way they would in a doe and be able to run those and verify the results in their contracts and so we're very very excited for that update to come very soon and so anyone here who is a defi developer or gamei developer nft

developer or anyone who might want to experiment with this we we'd love you to reach out and we'd love to try to find a way to kind of get this in your hands as soon as possible all right so I want to say thank you Ismael and babis for coming on the show thank you so much Anna thank you Anna it was great yeah it really gave me a chance to dig into the garage which I feel has been op I mean I've sort of seen it happening but this was really cool to to hear what all the work that you're doing and uh the direction you're taking I want to say a big thank you to the podcast team Rachel Henrik and Tanya and for listeners thanks for listening