ZKPodcast: Digging into recursive zkSNARKs with Coda

Transcript

[Music] welcome to zero knowledge a podcast where we explore the latest in blockchain technology and the decentralized web the show is hosted by me Anna and me Fredrik [Music] in this episode we'll sit down with Isaac and Evan from Owen labs to discuss recursive snarks and their project coda that's using this construction to make a blockchain thank you to Pio a network for sponsoring this episode a theorem

sidechains provides speed efficiency and low cost transactions the problem here is interoperability specifically how do you move tokens between chains so Pio a network transforms this process connecting chains with their ERC 22 ERC 20 token bridge the token bridge can be setup for any EVM chain providing near-instant seamless conversion from one ERC token to another learn more about this tech at github comm /p o a network / token - bridge we're gonna put the link in our show notes so thank you again POA network for sponsoring this episode one last thing if you'd like to support this podcast please check out our patreon page at patreon.com slash zero knowledge or follow us on twitter

at zero knowledge fm so now here's our interview with Koda so today we're sitting with Isaac and Evan from Kota hey guys hello hey how's it going and also Frederick hi Fredrik hello so I think to kick this off we'd love to hear a little bit about you guys maybe you can start with a quick introduction of who you are and how you got into this space hi I'm Evan I'm the CEO of Owen labs which is the company behind Kota my background is mostly in computer science

and I've been you know interested in space for a long time but it was really last year when Izzie and I started exploring ways of applying ciruno its proofs and novel cryptography to cryptocurrency that I really started taking my hands into it what were you doing before um before I guess I I guess the main thing I was doing before was I did a computer science degree at Carnegie Mellon and then I did a bunch of work in robotics as part of the Master's um a research into actually like task planning so getting robots to do not just picking something up but doing multiple steps in a row which

turns out to be a really interesting problem due to the dependencies between these different steps and then for a while I was just reading papers and thinking whether to do a PhD or not before deciding maybe I didn't want to do a PhD and really jumping into this and what about you Isaac so I guess I started my professional career working as a programmer at a trading firm called Jane Street so that's where I fell in love with a camel and functional programming after that I was a PhD student at Berkeley I was in the math program but my advisor was in computer science and I was studying cryptography mostly kind of theoretical multi-party computation so but I was very fortunate

to take a class with also under kia's which is how I first got interested in using CK snarks and actually I shared I shared an office with with Howard woohoo you guys had on the podcast you know was it that was very helpful for you know learning about lip snark and stuff too so yeah so I I guess that's kind of how I got a first started getting involved in the space you know Evan and I started working on code about a year and a half ago maybe a maybe a little earlier than that even and you know we'd northing up working on it ever since so so let's dig into coda a little bit this protocol and this this project well you know you've been working on what's the high-level view of that at a very

high level kotas and you cryptocurrency protocol that leverages zero knowledge proof to realize a cryptocurrency that has a constant size blockchain so what constant size blockchain means is that instead of a blockchain that grows with every transaction that it performs the blockchain stays the same size which means that it stays extremely cheap to verify even um as the crypto currencies used by more people and it can be used really on any device it can instantly sync to like you know phones or laptops or even like something like an Internet of Things device or web browser cool so there's a lot of things to unpack in that I think in and will probably get into a lot of it but are you just using zero knowledge proof for the compression or for privacy as well is it like Z

cache but small or is it like Bitcoin but small it's like Bitcoin but small yeah yeah it's it it's conceivable that at some point in the future privacy functionality will be added but as Evan says it's like Bitcoin but small now it's a nice that we already have zero knowledge proof SPECT into the protocol it makes it easy potentially in the future to augment it with things like privacy I think the first thing that we should try to cover here is this property of using zk snarks I assume it's ZK snarks for compression something though we've talked or I've mentioned on the podcast quite a bit before aware you know there's a lot of talk in especially

in like the stateless client world of using snarks to compress Merkle tree path and you could use the same thing for a blockchain of course like you could say here's here's 50 blocks and here's the zero knowledge proof that they're all valid like why would I wanted those 50 blocks if I can assume that they're all valid with just the proof so is it something to this degree yeah exactly exactly so I I guess like the most generic way to say it is if you have any statement of the form I know some data such that you know if you ran some program on that data it would output something you can make a zero knowledge proof which certifies that fact which is very small and easy to

verify so in particular as you exactly as you said you can make as your own screw physique a snark in our in our case that certifies a statement I know you know a long block chain such that if you were rich were to run basically the verification procedure of the blockchain on it you would end up with you know such and such a database of accounts and with such and such you know such and such sort of information for consensus as far as I can understand the purpose of using zk snarks in coda is less about privacy and it seems to be much more about efficiency or scalability like is it where does that live what or what is the use case for ZK snore in Kota yeah yeah exactly so Kota uses the case much

for scalability it's it's it's exactly solving this problem that with existing blockchain designs the more people two are transacting the harder and harder verification becomes for the typical user to the point where you know most people in practice don't verify things at all actually so we think this is you know a big a big problem especially as transaction volume 10x is 100 X's thousand X's as people actually want to do and and so the use of ZK snarks makes it possible to effectively verify the entire blockchain while only downloading a very small amount of data so I assume that you're not doing something as simplistic as like waiting for 50 blocks and then producing like a new ZK snark of the

whole chain every time because that would be impossible eventually so there you're doing something there - something different I assume yeah yeah that's right and this is where this idea of recursive composition comes in maybe that was kind of a leading question but you know I'll take her I'll take care of you so right so there's this a very general idea of proof composition which in theory it's very useful for getting theoretical constructions with certain properties but it's also practical useful but but let me just say a little bit about the general idea usually with the proof system you know I want to prove to you something right you're over there and I have some I have some

knowledge that I wanted I want to share with you or convince you of and the way that I do it is by doing you know there's some formalized kind of proof that that we engage in the idea of proof composition is okay well yeah we can do that but also imagine I had some other kind of proof system you know another proof has some on top of that and instead of proving to you directly and sort of the bottom proof system the proof you know proof system one on the bottom and proof system to let's say is on the top instead of proving to you directly in proof system one I prove to you in proof system - hey there is a proof in proof system one that have you engaged with me about that proof it would have convinced you which is basically as good as just doing the

proof is in proof system one so in basically you generate as their knowledge proof and then you generate a zero knowledge proof of the computation that verifies that proof yeah yeah what exactly so let's make it a little bit more concrete so as we said you know zero knowledge proof say let you serve by computational statements so we can start with one like I I know you I know you you all use a pseudo Q example personally I hate this example so if it's if it's okay I'll use a different one not that I really have a better one - gonna actually gonna be very boring no maybe I should use the Sudoku example okay I'll use the Sudoku example so right as we all know from listening to

this podcast this your knowledge groups are very useful for proving sodoku knowledge solutions so one thing that I might like to do I have my very secret sodoku answer I can prove to you oh I know a solution to this pseudo goop puzzle okay that's great and you you know I send I send you that snark you run it through the snark purifier it says true and you really know that I know a solution to that Sudoku puzzle okay that's great so I can tell you I know I can prove to you I know solution Sudoku puzzle well instead something else I could do you might ask why would you want to do this well we'll get to that later I could do the following I could prove I know is the case snark such that if you were to check it against the statement you know

I know a Sudoku solution it would verify so instead of proving to you directly that I know is a Sudoku solution I prove to you that I know a proof that proves that I know a Sudoku solution what which is you know which is which is basically the same thing but the the really cool thing about this is it lets you compose proof together so let's say you know I have two proofs each of which says here the Sudoku example starts to become a little bit you know even more contrived I have two proofs each of which says you know I know sodoku solution right well you know I could sort of join those together to prove in a single snark I know two proofs each of which certifies the existence of some pseudo true

solution so I can prove to you that I know two sodoku solutions using just one proof instead of two proofs is it a little bit like I mean as I this is the topic here is recursive composition of ZK snarks as I've understood it it's like a proof of a proof of a proof of a proof of a proof that sort of goes down some sort of rabbit hole is that wrong is it not it's not exactly a train of proofs yeah so that's that's basically right actually the way it works in coda for certain efficiency reasons is it it's not exactly a train of groups it's sort of a train of groups with these trees dangling off of the Train I I could draw a picture but you know it's a podcast so but I you know I guess I want

you to imagine listener a sequence of sort of a chain with with trees dangling off the chain and those trees are for efficiency reasons for sort of distributed proof generation that we can talk about later but is it a tree for each block then yeah essentially yeah is that what you've just defined is that general recursive snark or recursive construction of snarks or is that specifically coda well okay so you know recursive composition is a really general technique that applies not only for snarks but for not surely for every proof system but for many classes of proof systems you can do composition the the neat thing about snarks is it's particularly efficient for snarks but you know this thing that I just described with this this chain it

the exact way that you compose the proofs is that's got to you you know that's your own personal snarky texture we call it you know that particular snarky texture with like a chain with trees trees have proofs dangling off of it that particular pattern of composition that's something particularly coda but the technique of recursive composition is something very general is code of the first project that's putting recursive composition together with snarks or is that a long-standing like academic pursuit is that something that other people have tried in the past so let me give like a little bit of the history I think the probably the first paper kind of handling this idea of recursive

composition of something which are essentially snarks is paul balance paper called incrementally verifiable computation or knowledge implies time space efficiency this is a really fun paper I recommend people to read it he has this really funny example in their of like he starts by giving the so-called human motivation for his problem which is supposed humanity I'm quoting now suppose humanity needs to construct a very long computation which will run which will span super polynomially many generations each generation runs the computation until their deaths when they pass on the computational configuration to the next generation this computation is so important that they also pass on a proof that the current figuration is correct for fear that the following generations without such a guarantee might abandon

the project can this be done so basically he asked the question is it possible to run a computation over thousands and thousands of years in such a way that people can be assured that the computation was run correctly it's kind of a funny motivation I don't know you know it's it's it's it's a such a bizarre fantasy really when you think about it I mean those you know no civilization has ever lasted that long but okay maybe maybe it could happen it reminds me of the book the three-body problem where it's like one of the things is like they're in a simulation that runs many many generations and they sort of dehydrate the entire pop relation and stored themselves and then rehydrate when the Sun comes back and things like that it's it's interesting

and they also describe how you build a computer out of people yeah so I guess that's basically the first paper and then there's this paper called recursive composition and bootstrapping for snark super scaring data which is beat and ski kinetic isn't tremor which is really talking I guess about it you know it's it's beginning to sort of make it more practical more realistic talking about recursive composition specifically in the context of snarks and then there's this this this paper after that called scalable zero knowledge via cycles of elliptic curves that adds even more techniques for making recursive composition really practical and that's like from 2014 I guess you know there there has been some academic work we're

really relatively small amount coda is is the first project that's trying to make rigorous composition really practical for practical problems cool um I was somebody you also mentioned the and I don't know if I'm gonna say this correctly it's like tiny Ram is this a is this related to what you guys are doing I mean in some way so tiny Ram is this virtual machine that that I I believe was designed with the explicit purpose of you know being having its execution certified by snarks not necessarily recursively composed snarks but just sort of snarks in general but we don't use tiny ram in any way and yeah an interesting thing i think if if

you google around on zero knowledge proof sand snarks and things in general tiny rama then chili pops up being kind of see this thing being talked about and yeah like you can express any computation and run any program in this VM and you automatically get the proof but then at the end of every presentation this look it's like but you need you know two terabytes of RAM and it's gonna take you four years to run any reasonable program right but so I'm curious about you have this recursive composition structure when it comes to how its applied to a blockchain can walk

through sort of you have the Genesis bar you execute that block verify its then generate a proof to say this block is accurate then when the next block comes I assume you execute that generator I prove that this block is also accurate and that the previous one was accurate and then you go on in that fashion yeah yeah that's exactly right so basically at any given time in coda there's this single proof which says there is a block chain of length such-and-such and with you know last block timestamp being such and such and so a little bit more information for consensus such that you know if you were to read all that whole

blockchain all the transactions in it are correct and the Merkel route of the database of accounts would be H and then when a new block is generated you essentially incrementally update this old proof by recursively composing it with the new block so now you want to prove there's a block chain of length n plus 1 with state you know s prime or whatever basically you say ok first I have this old proof it said there's a block chain of length and with state s and I have a block which if you applied it to the block chain which is in state s you'd get a block chain in state s Prime and then you obtain you know your new proof and and you you saw on there there is a question of like oh you know that's actually very interesting that it's like you know but it takes a long

time for generate snarks like like how do you actually have high throughput while having start there's a big efficiency question there do that just maybe before we go into efficiency I just have a few more questions about this so I'm just trying to be clear on the object that's actually minimized by the snark is it the blockchain or is it the state or is it like what is it the change what at what's being actually I don't think snark Oh Phi is a word but we say snark if I did all the time by the way ok so I cool I mean I think has definitely as far as anyone who's working on coda is concerned it's not curved is definitely a word yeah so so essentially what what gets compressed or what gets snarky fied is the entire

history of the blockchain so people who are proposing blocks they have the current state they have the current database of accounts what they what they don't have is is the history the sequence of blocks which resulted in that state they just have a proof in place of that you know normally the way that you're you sync with a with the with the cryptogram with let's say with a blockchain protocol in general is you download the whole blockchain right you download the history the whole sequence of blocks and then from that you know then you go through that you execute all all the transactions you verified signatures and and you're convinced over the current state in coda you you just get the current state and this proof and if you're a typical end-user who doesn't need the whole state you just download

the parts of the state that you care about along with this proof so but it's a I assume it's a proof of work blockchain right or what what is the consensus algorithm so recursive snarks in general are kind of generic over your choice you consensus mechanism we're going with the perfect state consensus mechanism for Kota okay but then how do you prove that I'm trying to think of a fork choice rule where it's like if you have two snarks that both prove to valid chains how do you choose which one is the correct one to go by so I'll keep this example I guess to prefer work because it's fairly clean for that so so far we have this snark that's verifying all these transactions and making sure

the merkel route of the database is correct we can also use that snark to make sure that the consensus information is been computed correctly so for example let's say that you have you know a proof of some blockchain scape and you have a new block you want to add on to that the snort can prove that both that the previous strength of that previous blockchain was correct and that if you add on the new block given its target difficulty the strength of the new blockchain has been computed correctly as well but but they're both computed correctly it's a matter of comparing which one is the largest right so now so now that so if you have these two block chains each let's say you have like a you know two different block chains the

choose between you're wondering which one is stronger if you look at them you can look at their proof-of-work strength and you can see that both of their strengths were computed correctly which means you can just directly compare them and take the one that was actually stronger okay so it's sort of because you have that extra metadata around the snark as well at the sort of tip of the chain you can you can just compare those and trust that the numbers are correct yeah yeah yeah exactly exactly so like the snark is certifying not only that you're applying transactions to the database correctly but also that you're updating this consensus metadata correctly all right so you just used the example of proof of work but instead you've used proof of stake I understood you just

used it for simplicity sake are there any other changes that happen if you're using proof of stake so sort of so the actual you know metric and what you define you know which one of two box chains is stronger is a little bit different it includes you know both like yeah basically basically the lengths of those two competing chains um the trick is that you have to verify a little bit more information because you have to verify that stakeholders that have one you know a block actually you know have the block seen at that time wasn't such a state and they had a like their stake was correct such that they were the ones who actually won that

block that's to keep things very simplistic but um just a town proof of work you can check the sums of all of these different difficulties in crude of snake you can check that people who won slots who won created blocks actually are very valid winners of those blocks and you can calculate the length is correct from that and choose to everyone has the longer length yeah so at the end of this compression like you said you compress the the blockchain itself essentially you removed history which is something that all block chains want to do without sacrificing the security of being able to check that the history is correct but then you still have to deal

with the state database how do you sync and pass that around because normally and in like a big corner of our theory in blockchain you pass the blocks around and you get to the state by executing those blocks so maybe it's worth I guess speaking a little bit about the database model in Kota so in Kota we use an account based system so that Merkle we mentioned that you know this mark is verifying that's a Merkel root of all the account data so if you have that Merkel root and you have all the leaves of that Merkel tree you effectively have all the information you need so when you're joining the channel you don't have the accounts yes oh so that's the information you need the accounts are the things are the leaves so if you're joining the you know if you're joining

quota for the first time I guess there's maybe two primary cases you might fall into the first is that you're just a regular node you're a participant you do not need the full state in that case once you get the medical group then all you need to do is ask someone for a merkel path down to your particular account you care about and that's all you need to verify the value in that account the other case is if you're an O that wants the fold state like let's say if your consensus note where it's actually required you have the full state in that case you have to you know synchronize with the network and you have to download all the accounts that's still way smaller though than downloading the whole watchin and so that that's equivalent as far as I understand to the theorem model where

the first thing you describe is a like clients and the second is a full note basically but in coda they're both full notes well you don't well it depends on what you mean by full note I mean a full not--and ethereum is something that has the whole states I see yeah they're both fully we you could say they're both fully verifying nodes yeah yeah and so that that's the different that's the terminology difference between Bitcoin like clients or like node where they say it's sort of not fully verifying and aetherium like client is fully verifying it just doesn't have the full state database it downloads all the headers and verifies everything along the way requests merkel proofs exactly like you say for the the state request oh well I mean in the case of

myth Miriam or something it's such a white client isn't really fully verifying though in the sense that it's not executing any transactions no but it's verifying the work yeah so I mean it could be fooled into following a branch that has invalid transactions if it was mined enough we've talked a bunch of times about like the state database blockchain and then the stay paid if it was at the state database history like the various snapshots that's no different in this correct this is like you're not recording every state snapshot and snark could find that well I mean that's in the the proof of the state snapshot is

the merkel roots and that's part of the smart yeah technically yes oh wait III guess Anna could you say like a little bit more what exactly you mean so what I'm trying to say is like okay so as I've understood it you have the blockchain with the history and then you have the state database but if changes have been made from one state to another you wouldn't actually see that you'd only see the most recent state there is there's these things called like I think they're called archival nodes and it's very rare that it's gets used but sometimes you do have like snapshots of previous states and I'm wondering if it's in any way incorporated into your

model just because you're able to compress it so fully like do the various snapshots of states exist anywhere oh they only exist if someone decides to store them most people don't actually need them but we will support such archival nodes that people want to you know have access to such historical data but you couldn't actually reproduce the snap like you couldn't set up an archival node post fact you would have to have it running from day one yes ah and unlike currently where you could actually recreate state based on history because it's all very visible with this you'd have to have been like actually logging statements state-by-state yeah

Christine there's a little bit of an offshoot there but thanks guys I mean this model sounds very similar to basically a stateless clients where you're only dealing with your own state and then proofs of the validity of the chain and and how things get updated but in in the stateless client model you to two problems one is that it requires a bunch of bandwidth that no one really knows how to pay for this is the same problem it's like if a dream-like clients full node and centralization problem and the second thing is data availability if you're requesting the

state of something how do you actually know that it's available on the network if you know how do you find it and how do you know it's available sure yeah I can there's both me require a minute so let's see where do we start um let's start with bandwidth I guess um so let's say that we did have infinite bandwidth and you know if in a bandwidth and from the compute everything's amazing then we could scale quota up just arbitrarily to as many transactions per second as we wanted to which would be awesome it turns out though that bandwidth is still the limiting factor in an architecture like this so you know you have to make an assumption around how many you know megabits per second you expect participants to have and given a few megabits per second per participant

you can still get up to a few thousands of transactions per second so you can still do really good he just can't do you know arbitrarily good Oh every night I think a bandwidth question at Friedrich was talking about was like how do you get yeah how do you get the the nodes who are the nodes who are maintaining the whole state to give these Merkel proofs to the nodes or just verifying is that what you're asking about Friedrich yes so I think the the thing you just explained is is a good point as well because I that that's more like the block size question in other blockchain size posts like how do you actually pass these transactions around but yeah the additional thing of yeah

how do you actually request the state I I guess there's just like a bunch of different piece information you we want to request on the network but there's just a general strategy for this which is just as how I'm Bitcoin like you can kind of tell whether I know it is behaving honestly or not by its activity on the gossip network you can do the same thing in coda and you know really any cryptocurrency where some data is expected to be sent to render the network you can see like whether your neighbors are you know behaving in a way where they're sending information around in a way that's expected and you can use that to kind of decide your communication pattern to them which provides adequate incentive to participate honestly well I mean it's not so much honesty my opinion of life

how do you how to define who to ask it's more someone that doesn't store the full state themselves are essentially leeches on the network right like they will request things and they have nothing to give back I mean unless you build in and a sense of ization model for those that store the full state if I keep requesting my balance every time then the people who store the full state have no incentive to answer that and even if they are it requires a lot of bandwidth to keep requesting that that balance rather than like storing the full state myself so that's the trade-off like that happens within the theorem like Klein full node model where I trade-off disk

space for bandwidth basically so I guess to start off with just like kind of the incentivization problem you can kind of do something similar still to like the question of you know requiring people to give these paths out to be considered to be participating honestly because no one really knows who it is requesting the data from them when they request the data they just know that if the node that the data was requested from knows that they have to return data or else whoever's on the other end is going to consider them to be dishonest in some way so there's still some property in the whole network of some incentives ation around wanting to return Merkle pads when requested I don't have the calculations like you know here right now but like there's another question too of like figuring out the ratio

between you know full nodes and non full nodes as well as you know how much data the you know nodes that aren't storing the whole database are requesting you'd imagine for example if there's only one guy who was you know doing consensus and had the full database would be expensive for him but if you have a lot of nodes doing that it's not as bad yeah that sort of leads into the second part of that which is how do you ensure data availability you need date availability for running consensus like you said but the problem we run into like with the people running consensus don't share that data so they only participate in the consensus making process they don't

actually respond to like client requests so then you need to find someone that isn't a consensus node that is willing to share their data and as it gets into this sort of murky waters of like I'm not actually sure that this will always be available to me hmm so I I guess just to like clarify this is the question of making sure that when people share an update to the blockchain they're actually sharing like the full update of the blockchain they're not just sharing part of it and that's gonna like make everyone confuse later when something is missing yeah okay I mean that's another thing too yeah okay yeah I'll start without one I guess then so yes I mean you know it's the same same sort of problem so I think you would be the same solution

so basically coda solves this in two ways um the first is something that is F more than consensus layer and the other one is something actually inside of the snark so when participants are sharing blocks in the network other consensus nodes do not consider that those blocks to be valid unless you know the full data the full transaction data and that block has been included otherwise other consensus nodes will reject those blocks so assuming the majority of nodes are you know following the protocol then already you have a situation where it would not be possible to you know pass around a block that has enough missing data because no one's going to accept it additionally um we have a mechanism in

coda where when you produce up to the blockchain you have to prove knowledge of a random account or random set of accounts in the updated state database so because you have to prove a random account in the state database if something is missing eventually it'll be found out because eventually you'll be in a situation where someone's random path they won't have the data at the end of that path and because it's in the snark you know that everyone up to the your current point in the blockchain was able to do that successfully so people were storing the full state I think that still doesn't address the general sort of discoverability problem of finding a node that actually has the full state and is willing to

share that posts consensus essentially but we're already pretty deeply off topic from our ZK snark general topic here so I think we should should move on a little bit and I think I mean that problem it's nothing unique to this structure either it's something that every block Shane has I was just curious if it's if it's something that that you had thought about and I think in in at the end of the day it's about like how many nodes will be storing the full state versus not and storing the full state and ethereum is becoming a pain in the ass but for an account based system that doesn't have smart contracts that state database will probably never

actually be all that big I should mention also you know that we have more thoughts in this as well and maybe people can find me offline later too if they're curious about how we solve this you know the bigger picture of solving this as well so a little while back you brought up this idea of efficiency we didn't really dig into that and curious like when it comes to creating an efficiency or the challenge of efficiency is it the efficiency of creating the snarks like that can be a pretty time intensive our resource intensive process so how are you guys dealing with that yeah I guess there are a few different aspects to addressing this the problem of efficiency there is this architectural question which is how

do you architect your system in such a way to deal with the fact that in practice snarks are not as fast as you'd want them to be to get the kind of throughput that you might want to get to say a little bit more about that generating a snark proof that corresponds to basically one transaction takes on the order of seconds if you do recursive composition in a naive way where you're doing transactions sort of one after the other your throughput is going to be limited to like you know one transaction for several seconds so clearly that's not going to fly so what are you doing practice well there's this idea for a cursive composition up a tree which is basically you don't have to recursively compose proofs you know one after the other you can do them in basically a tree where you know I have a

bunch of transaction let's say I have four transactions and you can think of them as being the leaves of some kind of proof tree what I basically say is I have one snark on top of two of these transactions which says I know two transactions you know such that if you were to execute them you get from state a to state B and then you have another snark on top of the the other two which says I know two transactions which get you from from state B to state D or maybe I should have said a to C and D to e a to see anyway it may roughly get the picture basically you sort of compressed transactions two by two up a tree and the cool thing here is it's actually kind of like Howard's disick thing I mean it's a it's a little different but

then that effect is similar which is that you can snorkel by a computation of length n in time which is like wall clock time which is logarithmic and n if you have enough parallelism yeah the time to snorkel by 1024 transactions isn't the time of doing you know 1024 snarks serially it's the time of doing 10 that's because 1024 - to the ten of these compression players it's essentially a MapReduce of snarks yeah yeah exactly it's like a MapReduce I saw I mean so I saw your talk at C Conn's ero and you had this nice little graphic that I found very helpful we obviously as a podcast can't really show that and

we can't really describe it either because it's very specific to this but yeah we'll definitely share that graphic and I think that if our audience is curious I think it would be worthwhile for them to check out a little bit of like what you how you drew that out because I think it is it is a lot more clear that way but thanks for explaining it on audio anyway I know it's hard you know in in that cartoon that I drew that you alluded to you know it's it's sort of like a picture of a picture of a picture of a picture in twos yeah I try to explain the the recursive tree without without having access to a whiteboard but it's more gonna be an attempt than a than a nearly no

installation so I guess maybe one way to think about this recursive tree of the ugly case ARC's is thinking about like kind of taking a picture so maybe if you can take a picture of a picture the first time you take a picture it's just of one transaction but then the next time you take a picture you take a picture of two other pictures take another picture now you have four pictures then you have eight and 16 and 32 so every time you take another picture you're doubling the number of transactions that you're able to include in a single Zeke a snark so by only increasing by one more picture you've doubled the number of transactions and that lets us get the performance improvements necessary to get a very large number of transactions into a small number of Zeke a snark

pictures so that that covers a bit of the architectural choices made to achieve performance I think there's a bit of like code level optimizations I'd like to cover that a little bit too but another thing I just a random thought is maybe this influenced your choice and consensus algorithm because if you have a proof of stake consensus algorithm you don't have a mining race and so you basically have almost the full block time to produce this proof so yes that's that's correct and that actually like eliminating that variance in block time does help a lot to get into the full ik architecture a little bit it's actually

very helpful to kind of decouple the actual block time from when these proofs are produced so there's a little bit of things happening at the tip that are asynchronous I think that'll be really hard to explain without like oh wait for you I can try and say something about that because it's I think it's interesting and I think it's an actually an important contribution of what we've done and so I think people should know about it this is something that you know really all credit goes to our engineers let me call it Brandon and Deepthi in particular who were working on this there's as Evan said you really want to kind of to couple the consensus from the proof generation as much as possible so that you can have more time to produce the proofs than just a single block time cuz you know in some cases you really

want to make the block time lower it helps with security in some ways and and and so on so how it actually works is in Kota there's essentially kind of a buffer what happens is the consensus participants when they win a block they have the right to sort of B&Q transactions into this buffer now the chins the buffer it actually has a fixed size they can't in queue as many transactions as they want there's also some pending work to be done so there are some in progress proof trees that they need to also do some work on to free up space on the queue to incur their their new transactions and the way that it's actually done it's really interesting any person in the network doesn't have to be consensus node can contribute work to this buffer this work queue in exchange for a fee to be paid

by them for the by that can by the block producer sounds similar to the way if their aim lets miners mine multiple blocks in parallel because there is uncle rewards there's various like game theoretic economic reasons you might want to do the ideas you verify all the time and then when you produce a block you have some work done that you can kind of shove into a block and move on pretty much yeah I'm curious on whether or not you use lip snark or have built something on your own right now we use lip snark for fourth approver but it's actually something we're trying to move away from so let me kind of tell you our whole proof stack as it stands right now so I guess at the top of top of it is snarky which is our Oh camel DSL you

know for writings in case narcs basically I really like it it's it's a much higher level kind of language than using something like lip snark directly it's a no camel so it integrates really well with the rest of our system already and you can use the type system to get good guarantees about what your smart code is supposed to be doing sitting below that is lip snark so basically you run your snarky program it gets compiled into a big constraint system and that gets handed off to live snark to do whatever it needs to do this this is a similar an idea to something like a Socrates yeah yeah so it's a it's in terms of the how the pipeline works it's quite similar to Socrates that said snarky is very generic over the back end and in particular right now we're

actually working on a little project to implement the snark prover on GPU we're working on that we've kind of recently started collaborating with some of the protocol labs people on it as well and I encourage any people who are interested in implanting the snark Gruber on GPU to reach out to us and we can all collaborate are you doing that in no camel as well so yeah it's funny it's it's a bit it's a mixture of Russ and no camel mmm interesting I was going to ask why oh camel but then you said you work for Jane Street so I think I understand that that's only the incidental reason I mean well you know when you should ask a religious person why they believe in God they don't say it's because my parents believed in God

so you know I guess it's an incidental reason that that person is religious but you know III we use a camel because it's I think a really great programming language for building fast and secure systems I was lucky enough to have been exposed to it at Jane Street though so we want to move on to another topic that I think has so when doing research for generally for recursive snarks the question of security came up a lot now I haven't fully understood why that question comes up so maybe you guys can help me to understand like why what is the security challenge I think the main thing that you might be talking about is this problem of how deep is how deep

recursion is safe the this is kind of from the people from the experts that I've talked to you it seems mostly like a theoretical artifact of how the definition of knowledge extractors phrased and in practice composing deeply I don't think is an issue so is the depth referred to the depth of like your tree of this MapReduce structure or of the length of the blockchain yeah it's sort of how many proofs are you composing inside each other how deeply so it would be it's very equivalent to the length of the blockchain yes in this architecture that extract yet it's something else that I saw was the specific curve used to be able to I guess efficiently compose is of

relatively low security yeah that's right so the set of curves that's currently in Lib snark they were not sampled to be at the kind of security level that you wanna use in practice so we have another you know set of curves that are higher security level and such scripts exist we've been talking with with Alessandra about optioning the changes that we've made there into lip snark hopefully that happens soon is that also part of the plan of moving away from lib snark is to be able to use these different curves or I would say it's basically unrelated I mean in terms of moving away from lip snark that's that's really just from the point of view of prove our efficiency got it a reason we wanted to have you guys on was like the mere mention of for cursive snarks get people very excited and we are like cool what is this thing

and you are the people who are from what I understand like spending the most energy on it and looking closely at this idea but how far off are you guys or any other group from like using this in the wild like is it is this a project that's still very much in like research phase like has all the logic been figured out or is this something where you're still yeah so I encourage anyone interested to go to github.com slash co2 protocol all of our work is open-source you can you can check it check it out you can run a code a node you know it this is something that's running and working in practice so please you know download it and run it yourself well this it's live it's like well there is a test network

there's not a live main network let me say like that but you're able to create this system and it's functioning as yes so it's been an element yes yes cool I think this topic in general is super interesting and especially like you say Anna just thinking about thinking about zero knowledge person when you get once you get like into thinking about it and you're oh I can actually produce the zero knowledge proof to do this thing and I don't have to reveal anything like I imagine so many more cool things but then you go that extra depth of like I should construct a zero knowledge proof to prove this and this other thing and simply yeah it's a kind of mind-bending and I think you need to have started

thinking a little bit about zero knowledge proof before you can like really get into why composing them and recursing them would be cool but it's definitely an interesting thing on a previous episode we had Zuko on and we started talking about work that they've been doing on snarks to make those more efficient has that impacted at all the set up or the work that you guys are doing yes actually so we use an extremely similar construction to what Zeke ash is using in sapling for the Petersons hash function I think that's the main part of their work that we're using as far as the snart construction itself we actually use a different start construction we use in

NC cash in sapling they're using the grass 16 snark we're using the growth Mahler 2017 snark because it has an additional security property that we need so it has had an influence the other the one other thing that we talked about in that episode was the trusted setup and the ceremony that they had to do and the toxic waste idea and I'm just I'm imagining this must also impact what you guys are doing yeah totally so I guess as far as trusted setup goes I think what Zeke has produced is really a trust list set up as but especially as far as what they've deployed for sapling you know this is a this is a an NPC with many dozens of participants you'd have

to be you know really some kind of truth or to think that someone was it was able to corrupt it and we are planning on reusing to the extent possible the work that the cache team has done for producing their NPC code I think as far as the the setup goes the the most annoying part of it is is the fact that it's very logistically complicated so it's hard to do sort of rapid deployments of snarks there's a big lead-up time and you have to coordinate all these people but but I think that's I think the main annoyance of the setup is logistical not security related interestingly Zuko also hates the term trusted setup and that's why they start talking about toxic waste instead because it's more descriptive and the goal is to not produce toxic waste and

just have the components flying around but being sure that they get deleted have you guys thought at all about using like Starks or you know other types of zero knowledge proving systems that don't have this toxic waste or the risk of the toxic waste the toxic waste never gets made remember Zuko is very clear on that it's definitely something that we'd be open to considering using in the future when the technology is is more mature but right now you know especially for doing recursive composition snarks are the way to go do you guys have any last things that you want to share maybe some resources or places that people and find out a little bit more about the project okay so I think there's a few good places to look the first is I would recommend people to

check out coda protocol on get up all of our code is there it's open source you can play with snarky you can play with coda and there's you know some documentation on on how coda works and and all that the second thing is please check out some of our talks and I mentioned the Z con zero talk there have been a few iterations of that talk there's more clear versions now go to our website coda protocol comm to find those the third thing I would say join us on discord so on discord it's coda protocol I believe or maybe it's called server or something on just discord and you can come there talk to the devs and ask us questions that you want but please don't ask us too many questions we're gonna add all of those links and

the links you mentioned earlier on in the episode to the show notes thank you guys very much for coming on the show and talking to us about this super interesting topic I really think like I said before the idea of rehearsing these or composing these their own knowledge proofs is a really cool and powerful thing and I hope we get to see more of this kind of stuff in the future or not not just in the blockchain space and other stuff too so thank you very much thank you thank you alright and to our listeners thanks for listening thanks for listening