ZKPodcast: Proof of Necessary Work with Akis Kattis (NYU)

Transcript

[Music] welcome to zero knowledge a podcast where we talk about the latest in zero knowledge research and the decentralized web the show is hosted by me Anna and me Fredrik in this week's episode myself and guest host Tarun Chitra chat with Aki catus a PhD student at NYU and the co-author of a paper called proof of necessary work now before we start in I want to just let you know that the zk summit videos are now live on our youtube channel if

you weren't able to make the event this spring be sure to check out the talks now here are a couple topics that we covered plumo plonk Z KVM circum fractal zinc as well as new elliptic curves new libraries new consensus protocols I've added the link in the show notes be sure to head over there and subscribe so that you can be notified as we release new videos all episodes are actually released there's videos as well as the zk summit videos and the Z case study club with the ZK study club we tend to do deeper more technical talks with a group of experts so if that's interesting to you you might want to check that out as well cool so now here's our episode on proof of necessary work so quick change for this week's episode with polka dot about

to launch Frederick's availability has made scheduling a little bit more of a challenge and we agreed that we would actually recruit some co-hosts to help out for the next month or two and so I'm really excited to invite Tarun Tarun Chitra who's the co-founder of gauntlet networks and a frequent ZK podcast guest to co-host so welcome to the show Tarun hey thanks thanks for having me as the this was the first podcast I've ever been on it's also fitting that's the first podcast I've ever been the co-host of well today we're gonna be interviewing Aki catus who is a PhD in computer science at NYU and whose advisor is actually Joseph Pineau who's

been on the show before talking about PDFs so welcome to the show hey guys it's good to be here sort of the the topic that we want to get into for this episode is this proof of necessary work it's a paper that I saw you present I think it's scaling Bitcoin and at the Stanford blockchain conference I think it would be I think that's going to be the majority the episode but to start in we should probably find out a little bit about you so maybe you can share some context about what led you to this work what were you doing before yeah how did you get started on the topic okay yeah so I've been working on this for a couple of years now actually so when I started over at NYU I was interested in a lot of

the zero knowledge proof related work but from the beginning I kind of wanted to tackle the problem around how these things can be usable rather than how these things can be specifically designed and I was looking more around the kind of mining architecture an ecosystem that could support any zero knowledge proof based technology yeah and this will led me to thinking that one of the the things that would be needed if if these things were to be bootstrapped in in blockchains for scalability like people were using at the time then I would need to look at the mining architecture and then

potentially the kind of properties that these these snarks would need to possess to be used as proof of work and that sort of became an informed my context on on the space and you know as this thing has been developing over the last year year and a half I feel like there's still a need to resolve this issue so exactly how do you incentivize different entities to do you generate these these narcs and and that's sort of led to this work did you explore any other sort of combo proof-of-work zkp do it to explore Z cache were you excited by anything else before yeah so of course I mean the first work in in the zkp stuff was Z cache you know I I still remember when

they first launched and you know all the different trade offs that came came out because of that and you know I was I was looking into those things I was very excited by the work that the coda team was doing at the time they're they're a very exciting project and I felt like in all of those teams you know it just made it more and more obvious and to me inevitable that ZK peas would actually end up being used in some form of another and identifying exactly sort of what the issues are with creating these things and sort of designing systems and embedding that around them sort of it's reinforced my my interest in that you know seeing these projects for sure so so one question I might ask is I know you you had worked with coda early on in

their in their Genesis how did working on a proof of stake a version of a consensus meeting zkp type of system influence how you thought about proof of necessary work because you'd kind of seen the other end of the spectrum with proof of stake yes oh that's a good question so you know for me I've seen these to us there's basically two orthogonal directions in in bootstrapping these EK peas on payment systems as i saw it so when i was a code the guys were doing really really good work in you know getting an efficient prover getting the set up in a way that can be commercially viable and you know there were a lot of areas that needed to be tackled and discussed around that but

as it has to do with consensus you know the the good thing here is that these EK peas can be used with consensus of black box right so you know in proof of steak you can encode the kind of consensus that you want and that can inform sort of who gets to pick and choose the next blocks and you know in proof of steak it's it's a different set of design questions because all of this gets encoded in the snark so it has to do with you know exactly what kind of properties they want to get out of their system I you know I I thought it was a very interesting thing because it helped me it crystallized in my head the fact that it can be very modular to change the consensus algorithm but in the case

of proof of work there also have to be certain extra properties that this proof system needs to satisfy because in addition to just encoding consensus it also needs to satisfy properties as to you know what it hashes to and all of that stuff so it did inform a lot my view on on how zkp scannin should be used but in a way that was different to what ended up neat really mattering in how to build the proof of work system its distinctive enough system in the in the design properties that requires one of the topics that I really want to touch on almost before we jump into your work it's the idea of proof of useful work and how I have been told repeatedly

that that is is a bad idea and yet and I've mentioned like I've sort of repeated that statement but I haven't always exactly understood why is it a bad idea so why don't we first say proof of useful work jet-like traditionally has been considered you know not so good I know that the proof of necessary work that you've come up with actually is as I understand like one of the first examples where it potentially works but why normally why generally does proof of useful work not work yeah there's there's many different flavors of proofs of useful work that I've seen in the literature some of the most intuitive

types revolve around taking a problem that is useful outside of any cryptocurrency setting or any network protocol setting and you know encoding some kind of prime numbers that are useful or just independent problem inside the constraints and then showing that this can actually be incentivized to be created now you know I don't I don't see that as an inherently bad thing specifically I would love to hear what the critics of proof of useful work have to generally say but yeah I mean I do see the point that if you're providing computational power for a puzzle that isn't related to the protocol I can see how that could be viewed as a completely outside of the of

the system kind of benefit that most people or some some users may not be particularly happy about or interested in I think it did have something to do with like the incentives or rewards being muddled in a way because if you say you're performing some useful work and you can sell that useful work then there's this other economic motivation this that's that's what I've always understood is one of the reasons why maybe it's not like inherently bad but why it definitely complicates things or potentially could undermine some other you know some other behavior that you really want these miners to to participate in that's actually a very

good point yeah so definitely I mean if you're performing useful work and you know the output of this work has some monetary value within or without the system then you definitely need to reason a lot about exactly what incentives you're providing each of the participants especially in the cases where the useful work is done by the miners that are also validating and have some extra sort of like enforcement requirements on top of it yeah and that's why I feel like there could be many different ways that this could be created but that's why I feel that the most simple blueprint that of Nakamoto consensus in which the people who do the composition or computation get remunerated the way that anybody would be remunerated when they get a block

sort of at least in our setting keeps this incentive one-dimensional the same way that they wouldn't Bitcoin and and trying and to ensure that that is the case is actually the big design challenge for us because you don't want to be able to do things like break up your snark in different parts or play with the algorithm in a way that you can you can violate some of the randomness properties but yeah no I agree that the incentive issue is probably the most important issue and I think why this is difficult to do in the context of providing informational computation that is endogenous ly important yeah so once I think the first time I had really ever concretely felt like someone gave a good explanation for why proof of useful work

wouldn't work was like in 2014 I've been reading one of the early drafts of Joe burrows book on Bitcoin and cryptocurrencies it's like the Princeton Bitcoin book now but there they actually tried to formalize a puzzle hardness property which is which basically says if I solve I sort of solve the puzzle that wins blocks one two and three I shouldn't have any advantage up to some small error of winning block four than anyone else like and and right now I think people kind of take that a little bit for granted because they assume that there are these randomness properties like you know other cryptography papers

you kind of don't see this puzzle hardness described explicitly because it it sort of comes from the randomness that that you assume exists like whether it's a verifiable random function or something along those lines but I think you know if you go back in history I remember in 2012 and 13 there were a ton of coins and remember this is the time kind of a I was sort of blowing up there are a ton of coins that were like oh like solve this machine learning model and you'll get like block reward or do protein folding power king in protein folding them so people were like oh we can monetize protein folding and of course none of those works because if you solved you know I solve a linear regression and then I add one data point having solved

it on n data points makes it pretty easy to solve on n plus 1 versus for someone else solving it on n plus 1 so I guess I I think the thing that was most striking to me about proof of necessary work is like it's the first time that I've seen something where you kind of preserve this puzzle hardness property while also doing something that's useful to the chain and dodging ously and I think that it's very hard to construct non cryptographic things that have that property I think prime coin is also a weird example because there are certain properties of primes that are random and then there's certain properties that are completely deterministic and if you choose the wrong property it might be that for like the first thousand blocks

it's actually random but then at block a thousand one it's like deterministic so maybe you know I think it might be interesting to talk about like how you when you were working on this what the genesis process of getting to necessary work being in this endogenous snart computation was and kind of avoiding these pitfalls like how did you how did you kind of the see that well so I suspected from the very beginning that I wanted to be able to hash the snark the same way that you hashed you know the root of the tree plus the nonce or commitment to state plus the nonce and and get something that is exactly in a black box way the

same as what you would get from double sha and from there on we looked at all the different possible attacks that would prevent that from being the case so we sort of work backwards on that one yeah and I mean the the most fundamental issue you know why don't you just take a random snark and and you know hash it and do everything goes back to you know something that you mentioned earlier around if I have n data points versus n plus one it's the same idea you know if I generated the snark once I shouldn't be able to split it up and only resolve certain parts of the snark that depends that are dependent on the nonce and this really just brings us to the notion of non amortize ability of these kinds of functions and that's that's really the

big challenge and yeah I mean I mean the way that we we try to resolve it involved really trying to stay within all the constraints and restrictions of needing this thing to verify state so we wanted to do this specifically for a snark that verify stage transitions and that's why we wanted to play around with the kind of accumulator that was used and modify that to to get non advertised ability but it all begins with non amortize ability and in this context because that gives you everything else that you want so I think I think it's about time in the interview that we probably define proof well like what exactly is proof of necessary work and how you would summarize that I guess for

for our listeners yeah so the idea of proof of necessary work its most easy to understand in the context of a stock based blockchain but the idea is that you've got a set of miners and you've got a cent of n of end users and a sense of validators which are the clients and the idea is that the miners the proof of work problem that they are providing so the proof of work problems are solving for security in nakamoto consensus is also something that you can use to very quickly extract knowledge claims about the specific strength transition so when I am providing you with a proof that this block needs to go on blockchain this proof is a snart that in addition

to demonstrating proof of work in addition to you know satisfying the difficulty condition in the standard way also provides you with the ability to extract knowledge that indeed certain transactions do exist for this straight transition to be valid and the process by which to generate the specific proof is this exact same way all the time so randomly you generate this and you ideally want it to be done so with a Poisson process or some memoryless process so this is this part that you're talking about where it's like it doesn't matter if you've done one proof before exactly you have to do the entire thing again and it's gonna be the same a success time size mm-hm yeah and that's the cornerstone of the proof of work

security so you want to be able to ensure that it so this goes back to the censorship resistant property so you want to make sure that you know if you begin working now under some invariants over your hardware the chances that you're going to be able to get the next lock are always proportional to your hash rate and in order to do that you need to ensure that people can't reuse previous information that they received from other sort of tries in order to get the final answer because then this is going to mess up with the incentives as you mentioned and that's really no good because then we don't get the security that Nakamoto is based on and on which we can then make claims about consensus cool you mentioned just just in your

explanation you mention validator but I want to distinguish that because I I believe it's not validator in the proof of state content its validator what is that is that like a like client validating is that I mean thinking oh yeah sorry I I just meant something like in firms of the verifier and all these proofs this was like prove or verifier so the verify here or we're just assuming has very little memory it's just a smartphone it's like sort of like a light client or an user that would basically be just be checking a smart proof you know another another thing I think people often hear but is sort of important to like clients is incremental you know incrementally verifiable computation and recursion and

so maybe do you think you could walk walk us through how that plays a role in this construction and and why it's important for sure so actually what I would like to first say is that it's not really necessary for this construction it's not it's not something that you know if you don't have incrementally verifiable computation you won't be able to use this construction but rather that it works with this construction so if you do have some sort of blockchain architecture that is doing a pc d or IV c then you know as long as the way that you generate the specific predicate it's done in a way to ensure that no or very little informations reused then you can you can do that absolutely

no problem so you don't actually need any cycles or any recursion to do this you know in our prototype we we did do that we just wanted to make something that you know also has recursive verification and the main really cool thing that you get out of all of this is that you are you can basically take live clients that can verify the whole chain but in addition to verifying the whole chains they can also verify that proof of work has been computed at every single step and they can do that with the same guarantees that they would do in IVC but that's not strictly necessary you can you can have a context in which miners can do almost everything outside of the scenario except for some basic very basic operations inside that you

know correspond to the accumulator of the specific blockchain and then you know light clients would still need to verify every single state transition if we don't do recursion or if you just specifically work with with blocks marks I still I'm still not entirely clear on what like incrementally verifiable computation is though so like I did understand it as similar to recursion but you're saying it's not oh so I VC in general I just mean that former computation that you know builds on previous steps so this is how we we model the state transitions in the blockchain and the design question then here is do you want to verify the snark

of the previous of the previous block in the next block so do you want to actually specify the verifier out and actually do all of that specific computation or do you want to be doing that outside of the start and be doing it in the normal way that's the distinction that I meant and proof of necessary work is really invariant to this design choice that really depends on how much you want to how much work you want your light clients to be doing versus you or your miners which is orthogonal in a sense one of the points in the paper like you actually do you do talk about like clients at one point and you cut you cover a few different kind of accumulators or ways that like clients

are generated you mentioned fly client and then you mentioned ni pio pio W which I had never heard of what what is nip Popo I don't know if I'm saying that right it's yeah so it's an idea that goes in the same vein of resolving similar issues so the question is you know if I'm at a block height or if I'm at a certain level in the system you know and I want to receive you know or I want to have prove knowledge to myself that you know this specific chain hai actually has done all the proof of work

it's just a different way to do this with it asymptotically does better and a standard Bitcoin and I think that they do it in logarithmic number of blocks based on the way that they check for proof of work but it's really just another way that ensures you know when I get the block height instead of really needing to go back and double-check all of the hashes work out that I can do that more efficient in a sense it's a very similar kind of question to I want to verify all state transitions if part of the state transition is verification of proof of work so in a sense you can consider them as similar but it's just a more specific subset for the proof of work verification itself and the reason that we built the the design using recursion

and using all the PCD stuff was because we wanted to demonstrate that this kind of approach is also capable of doing that verification in Causton time the same way that it would do the state transition verification in constant time even though in practice you know if somebody wants to build it without recursion that is still feasible the puzzle is still gonna work out yeah what one interesting thing I think that you kind of Anna's point kind of points out is that ya know interactive proofs of personal works are quite quite old I think like it's like an Andrew Miller paper from 2014 but there's a sense in which people's memory is always tied to

whatever papers they read first where they saw did definition of X X is blah blah blah and they don't understand sort of sometimes the history of why that definition is good or useful or has shown up so it's kind of interesting to think about how I cross chain communication research like if someone started in 2016 verse starting in 18 they would have a very different vocabulary because they'd be referencing a completely different Genesis paper or they would uh they'd be looking at are there are there any are there any things that while you're working on this eve you've kind of felt like you started on the shoulders of giants to the point

that you didn't you don't even know necessarily the history of like it just was like okay we just everyone assumes that so it must be true oh well that's a great question I mean there's many different parts to to sort of what is needed to get this to a great design that a lot of that work you know and before this question is even relevant so you know when when in 2013 you know 2014 you've got you know miracle trees that you saw with millions of constraints you know when so the one dimension is is how fast these snark proofs can be generated and that's also something that introduces some trade-offs in our model that we should

probably talk a little bit about but yeah one one thing is you know the community that's been working on designing faster snarks that's bringing down proof generation time that's also bringing down proof sizes because we want to be putting all this stuff in the blockchain you know all of that work you know absolutely you know that needed to be done before what we did is even relevant in terms of taking assumptions that other people you know have considered to be standard the Bitcoin white paper is written in the random Oracle model you know they've they've got a very specific set up and I just felt like you know we just really wanted to deviate as little as possible from the Nakamoto proof so the the Bitcoin

paper argument as to what the specific you know hash functions should do and that's why we really didn't want to change very much from you know the hash cached proof of work based constructions but instead just literally switch out one bear specific part so to switch out the shop but we wanted to make sure everything else remained the same as much as possible um how does so like it's a proof of work system how does the mining like how would a miner act what does their actual work look like because they're also as I understand it like they're also generating a proof mmm and are they doing anything else maybe just just say what is the action of this

miner yeah that's all they're doing and they're doing it over multiple times you know it's already a lot of work so it's not we can make them do G bar yes they can make the sonars bigger so the the main idea here is that you know you've got a man pool mental has transactions in it in the exact same way as Bitcoin and in that man pool you just pick a bunch of transactions that you stick him in a start you generate the stock with a very specific knowledge that's also randomly generated you know think of this as you know you generate your block and then you're hashing your your block along with the nonce it's exactly the same idea only that instead

of putting them in a block you're putting them in a stock and then you generate your snart so you do all of the different parts of the computations that are needed but notice that because the nonce is also part of state here so it's also part of your inputs it's going to affect what that's not looks like it's going to affect your proof of knowledge claim the aim in this is that it affects it in a sense it affects as many variables as possible so that then you know you check at the end so you get a proof out of your proven you have the proof and then you check if it satisfies difficulty and if it doesn't satisfy difficulty then you change your nonce randomly you can keep you know the state-transition you want it exactly the same and then you

repeat the process and the idea is that every single one iteration of this needs to reuse zero information from everything else and then at the end when you do find the answer you post that on your network so you broadcast your yourse not proof everybody verifies check that it's correct verifies the updated quality and adds it to their to their sort of head block but do they do the other clients also have to run the snark somehow like if you're saying that they're very like do they have to do all of that work as well no no so the proving the proving side work is something that you also need to have stayed for so you need to be able to actually have the specific state

transitions for so in this model you know all of the miners have access to this you know that's a lot of stuff there's a big proving key in there and they have access to all this in order to generate the proof but the important thing here is that indeed the editing that are double-checking that we're at the right quality we're at the right level don't have to be the miners themselves those can be light clients so the light client just has a verification key checks that the stock is correct and that it actually corresponds to you know the deepest block and then you know hashes it themselves to to check the difficulty and the proof of work was performed that this is actually legit and that's all the verifier needs to do

now if they want to keep a copy of state they also need to process all these transactions you know and that's sort of the data availability side of it but that's really the main step and in terms of data availability in these in this model there is sort of a difference than than Bitcoin in the sense that the like clients are meant to be thinly dated like they don't actually use a store all the data and they kind of act as like these endpoints how does that play into sort of the the economics of this and you know how how mining pool dynamics will will grow if the mining pools end up needing to be the the pools that have the most state stored or like you know there's like kind of the state burden

that's kept on mining and proof generation how do you imagine that effects kind of how concentrated or how you know dispersed mining pools will be yeah so I feel like on that on that issue we looked at the question of like client verification in the sort of classical sense that people have been looking at assume you don't have the ability to store the whole blockchain you know what can we do for you from a verification perspective but we need to ensure that you know everybody who's mining everybody who's updating the Merkle tree or the accumulator needs to have access to the state that's really the main hard constraint here but you know in a sense that's that's the hard

constraint for anybody that wants to do a state transition anyway just because they need to know exactly what the updates are going to look like the main bog neck that comes out of this if you want to retain the trust model that you have in in crypto currencies like Bitcoin is that in a sense you've got to put all of this data on chain so that everybody going to be able to recreate the state-transition now you know I don't really feel like the really big burden here in terms of mining pool centralization rests on whether the miners have to keep state or not that may be the case if the the chain is you know multiple terabytes long but I feel like the the main question there is just

how non amortizing all can you get prototypes that you know solves these specific functions I feel like that's more of a factor on how big the mining pools are gonna get because of course you know you can also sort of check point in the blockchain and sort of keep a lot of stuff in the back of course you know there's corresponding trade offs in in in the model yeah but I don't really I don't really anticipate that the the biggest bottleneck to centralization in these systems is keeping the state but rather how well can you optimize the specific function which in our case is a snart proof generation so how low can this go in comparative to other people

in the system but like is there a difference is there actually a difference between like a big miners ability to do this versus a small minor yeah so that's really goes to the core of this I would say very is so there is one dimension in which they we can distinguish between big versus small miners and that's specific to solving snarks that are based on elliptic curve operations so there's a very so this is all the growth 16 Pinocchio all of that sort of flavor of snarks you know not stuff that's based on fry or start based stuff but you know in in that context

which is you know what we built this around there's a you know one main so there's basically two main operations that matter there's the fast Fourier transform that's done in order to generate polynomial coefficients and then there's the exponentiations that are done which are to generate the specific snark yeah we focused on the exponentiations which is also the asymptotically sort of hard parameter and the idea is that you know exponentiation is amortizable so that's you know a fact about exponentiation so if you want to do this kind of process while using exponentiation in in these elliptic curve groups you need to be able to understand the trade-off between

precomputing many of these values and not and really then the question becomes you know if I have a pre computation table that has every single potential value for you know this then I can solve this problem easily all the time that's right yeah yeah and and that's the faster is just more more often well if I if I just have a pre computation table with all the potential values I can just resolve it and faster all the time like I literally just query the specific index and then here we are so you know however this is not feasible in practice because you would require exponential space so the amount of space that you would require for this is really dependent on you know how many of like you know we can go more specifically

into numbers but it really it's really akin to enumerate all the exponents for all the potato all the different bases in your proving key that is gigantic so that's not really going to be how how you can you can differentiate between bigger and smaller miners what I think you'd see people doing in in reality would be to use some of these pre-computation sort of optimizations up to a certain level of space and then being able to bring down their computation time although that in a sense technically wouldn't affect the system because that's something that anybody would be able to do because that's a pre computation table that everybody can generate at the beginning

this would be a problem in the case that you know if you just add a corresponding amount of extra space you get substantial speed ups but on the asymptotics of this the amount of space that you would need to achieve you know 1% speed-up at every level goes up exponentially so there will be a certain point where there's going to be a good enough table that miners are using based of course on the memory that they have and then overall the rate at which they churn out proof circle is going to be very similar and the changes are going to be negligible so that's really the main way that I would envisage the difference between a big minor and a small minor specifically to the case when you do a limited curve cryptography

in order to generate your snarks this trade-off is better understood by us so you do end up with exponential space on that front now when it comes to other kinds of snarks snart's that don't use you know kate commitments that's a very different sort of area you know I don't have any specific and you know succinct results on that one yet but I think that it would be much easier to do this without that kind of trade-off so that would strengthen the non amortize ability properties of the system but that remains to be seen sorry when you say when you say that on Kate commitment you're referring to structured reference string type of systems yeah yeah yeah I should have I should have made that clear yeah so we

all of this comes from they need to compute Kate commitments using the universal structured reference strains that or non universal that they have in in growth and in some of these systems haven't looked at other systems though that don't do that that would be interesting this is a side note but is it Kate or is it cat a because I very much hurry I mean being a te no so it's a it's an idiot there so it's it's caught a but okay but like like all Indian people you just kind of don't really care about people pronounce it in the u.s. it's not Kate I need to relearn

that okay the rule of thumb for Indian names is add an H before or after every vowel age how do we pronounce your name correctly don't pronounce it correctly cuz know what it's like you know if you're saying it like my mom says it's Turan that roon oh wow cool so so kate kate is cotton but okay cata commitments all right I will but but I think everyone says Kate so they'll probably not know what you're talking about Arielle Gaby's on who says KJ and have said it on the podcast so I just want her to the correct that's much closer

I mean maybe yeah sorry side note are you gonna you should include that I will I have no idea how to ask this question I have written define adaptive throughput because I don't know what it is so maybe one way of saying it is you know one of the big advantages to this method is that you can have block sizes that vary which means that you're the throughput of the botching can doesn't have to be constantly 500,000 transactions per second but have empty blocks and it also just have to be slow like six transactions a second you can have when there's bursty demand it can

go up to a lot of transactions and when there's not many it goes down which means that the economics and fluctuate with the true demand rather than kind of being a little bit having a floor on the economics and so you know how you know that adaptive throughput has kind of been this holy grail that I think in 2017 people forgot because we were kind of there was kind of everyone was just selling TPS as a feature a key metric yeah feature metric I don't know I don't know what to call those days because I think a lot of the people who sold that also maybe you know did work they were just trying to fundraise amusing fun buzzwords I guess yeah 17 years

exactly kind of this benefit yeah cryptocurrencies are in some sense the ultimate Veblen good so Veblen goods are these whose demand whose price increases when demand increases like like supreme you know people are waiting out that's a web good so adaptive throughput is somehow this holy grail of turning this cryptocurrencies are weblink goods into something that makes the demand model makes one so how did how does that show up in proof necessary work how is it used how does it you know kind of walk us through maybe yeah so yeah so this goes really back to the issue of incentives that we discussed at the beginning so in general when you are

computing a proof and you've been able to bootstrap in there that you've also verified certain transactions that really is a necessary but not sufficient condition in order to get adaptive throughput and and so really what we mean by that is that ideally you want a system whereby the amount of demand and the amount of supply for transactions so this is sort of the set up here is something that is always clearing so it's something that you know if you see transaction fees go up you would you would rather want the system to sort of take note of this fact and then grow its TPS that it provides you know accordingly and the way that you know

the end user would see that is that this would put downward pressure on the transaction fees maybe because you're producing more of the good where the good is you know rate of transaction processing over time so you would like a system that indulgently endogenously it adapts for this fact and you know if you use something like proof of necessary works where you were in a sense saying that you know I'm I've got a snark this narc has s transactions in it and I've generated a proof of this fact and I've put it on the blockchain you know we noticed that at this point we've been able to make difficulty you know what people in the economics discipline would call a sufficient statistic for demand because you know if more people would like to use this then the transaction

fees are going to go up it's going to be more profitable to mine more miners are going to come up difficulty is going to go up and the you know that the problem with doing something like this as is on Bitcoin is that in a sense you're constraint to one dimension you know if you would like to keep difficulty very low that imposes security questions on the protocol so you know if you convert a little difficulty somebody's going to attack it and and that's something that means that difficulty in the sense is something that's a peg both to feasible demand and both security so you really can't the cupola things now in in our case the the cost so the security is actually a function of two things it's a function of the difficulty but it's also a function of the size of the predicate namely the

number of transactions so you know if you've got more transactions it's gonna be more difficult and you know if at every single step but every single block the only kind of predicate that the system takes in is one that has let's say s transactions then that's something that you can vary over time is the main idea so you know difficulty goes up and then you can have a second update rule so you know you've got your standard difficulty update rule and then you know difficulty goes up when there's more demand but then you have a different update rule that updates at a different light and separation of time scales and that actually acts to change the size of the snark block in a way that also affects difficulty so you know in the

case that difficulty goes up by one twice as many people are mining you know that corresponds to the fact that you've got higher transaction fees which is why more people are mining and then the system is going to actually increase the size of the predicate double the size of the predicate to be able to drop the difficulty back by one and so in a sense it's sort of like a system with gears so you know you've got you know difficulties going up until there is a change in the predicate and the predicate size goes up or down up in this case and then difficulty immediately drops down again and if you keep difficulty at a constant level you're actually capable of having a constant level of transaction fees as well because all of the security

guarantee that the proof-of-work does actually goes into the fact that your snark is much bigger so you don't actually have to compromise on security because you D Coupole the efficient statistics for both security and demand in this context so this is so this is why I think that something like this could be used for adaptive throughput guarantees with the ultimate aim being keeping transaction fees constant regardless of the amount of demand that comes into the system so has this have you really cracked this or is this still like a work in progress so yeah so this specific thing we haven't built this specific part using bits and bytes but we we do have a paper out that outlines this idea and we do

have formal guarantees around this in the Bitcoin model you know there's the specific kinds of relationships that the hash rate so the proof production needs to satisfy in order for something like this to be incentive compatible our formal result is a general equilibrium result on this so if you we look at demand shots of systems that run this kind of double at the adaptability rule so the difficulty part and the predicate size part and we're able to show for specific update rules that you can stabilize the so there exists a stable state equilibrium for the transaction fees regardless of the size of the

demand shot well with you know a specific upper bound and we were able to show that for you know a system that models the supply side and demand side of Bitcoin but that's more of a theoretical contribution but the idea is still there that it's this is basically free with low asterisk to build on top of systems that run proof of necessary work or or sixteenth block chains that's this kind of adaptability you can do outside of the snark so there's no real big design issues it's just a question of ensuring that the system is going to be able to price in any demand sauce and then always sort of like over time converge to a point where you're still the same initial level of transaction fees basically you know I like to think

you know and tarun didn't mention this a little bit earlier like I like to think of a system you know like a decentralized system is one that doesn't immediately begin with 10,000 TPS or at least the ones that have existed you know if we're looking at the centralized systems it's really just a function of how many people use it right and if the centralized system this kind of thing is gonna grow organically usually you know and we feel like you know we felt in in that paper that TPS also grows organically in the sense if you do have this sort of link in san link between the generation of the proof of work which you're forced to do and the generation of a proof of work that also verifies transactions whose size you can calibrate and it's really the

latter part that allows you to then adaptively change how big each specific predicate update is so you can actually take pressure off of the fact that you know you've got a constant block size and you take pressure off that by growing in a sense the system and so you know if trajectories are really high predicates that's gonna get bigger difficulties gonna go down so that's really the main idea um so you know I think one of the interesting most interesting things about this right is that you know in Bitcoin I'd say the biggest seminal event in Bitcoin post Genesis was the block size debate and the block size debate obviously is kind of thrown out by this world where you have constant size blocks powered by snarks and that's the reason you can get

these kind of constant transaction fee under bounded you know demand shocks limits because the block size physically in bits is not changing but the block size and content information wise is actually fluctuating and separating those two is what gives you this economic abstraction you know this is a very proof-of-work thing because it relies on difficulty adjustment do you think and you know especially since this is I remember when when Joe first brought this up at the the kind of reading group at NYU which is right where I actually first met Rocky was was like oh this is proof-of-work coda so the interesting thing is the difficulty adjustment is fundamentally different and I don't know how you can if you can replicate it in proof of State and so

that big difference between coda and profit necessary work you know what is there a way to actually do a staking version of this or is fundamentally a difference that can never be replicated in stake like this kind of demand adjustment so that's a real question um I'm not so sure actually that's a very good question the only thing so you know we had a modular approach to the way that we tried to prove these things now if there is a proof of state kind of consensus mechanism where you have a certain parameter that functions in a similar way as difficulty so in a sense that is the proxy for transaction fees then you know for demand then this can absolutely

work out that's that can just be plugged in there I'm just struggling so I don't actually know very very much about you know the most cutting edge or the latest in in the proof of stake literature but you know if that kind of property can be isolated and you can figure out a way to make sure that it isn't affected by the size of the predicate in the same way that we have here then that should be able to be plugged in very modular Li I just haven't actually looked at how this can be done in proof of stake yeah there may be there may be some issues if you don't actually have a parameter like difficulty there I'm not kind of another note how would you add like is it possible to add smart contract ease

stuff into this model does it does it work yeah I mean you know this is a snark right we you know we built our prototype based on transactions that move pebbles but you can do anything right like it's it's in NP you know you can the kind of transactions that you can be verifying could be other snarks that could be arbitrary computation for example that technically is possible and you know there's there's different trade-offs there because you know all of that is very expensive you know we didn't discuss any you know a6 or FPGA sort of stuff but you know that may be feasible then but yeah I mean it's really invariant you can make your state transition whatever you want yeah so you

know everything that kind of has been surrounding proofing the server actually sounds super appealing especially given that there's been such a huge amount of resources committed to trying to make proof of stake versions of these types of things working but you have kind of less on the proof-of-work side so I'm kind of curious what you you know what how you see the direction of implementation going and how you expect kind of the first version of proof sorry work in production to look will there have to be GPU miners only will there be FPGA miners Asics like what you know kind of how the how do you foresee the next one to five years so I think

that's important here to highlight you know you bring you bring up GPUs FPGAs etc so the the number one thing I would like to highlight here is sort of what our trade offs are and you know this kind of system only works well if it's very quick to iterate over many different snarks so many different proofs otherwise it loses the asymptotic properties that you want you know if and this is all in comparison to block time so that's really the ratio that we care about and that you know it gets to some security implications if this ratio is too high so I think any implementation is going to need to take this ratio down so the ratio of time to generate one proof to block time as long as that's

something that you can do in deployment then the system is going to be secure at least on on this front now whether you're gonna need FPGA Zoar GPUs or what kind of specialized hardware for this you know that would be great specialized hardware is going to make everything much much faster it's gonna give us these ten or a hundred ex you know increases in efficiency and a lot of these dimensions you know including TPS and in in other context now you know I am not so sure exactly the the kind of model that this would be implemented in initially it's most you know it can work as as I said you know both in the recursive and non recursive context if I

were to sort of speculate I would say that in the first sort of ways that if this was going to be deployed then you wouldn't really have a full-on you know fully recursive system that you know is you know can do an activity to really really large spread in really really large predicates you know and then also satisfy the fact that each snark is generated in like less than one second and also have 30 or 45 second long times right that's sort of where we want to get that's the kind of system that we want to see but you know getting there can happen incrementally you know you can build a system for example the kind of work code is doing where recursion is a very big part and you can put it in there you can build a system where you know you make

those snark generations more efficient only you sacrifice you know certain other properties you know you can even do this in a trustless snark although that's going to be less efficient so it really depends on the kind of design goals that you know anybody that wants to implement this has from the from the beginning but the ultimate sort of end point for this is that you know you want to be a be able to generate really really large predicates and you really want to bring down this bottleneck that you know if I actually have a big enough system where I need to do a hundred transactions per second I better be able generate a really really large snark and for me to be able to do that that's

probably gonna at least you know unless somebody comes up with the ultimate snort which they might you never know that's gonna require hardware acceleration and it's going to rewire it require ways to be able to resolve the fact that these things also take a lot of memory you know that is both a feature and a bug depending on how you build that so yeah that's you know we'll see what happens if people want to use this and if this is something that you know they're going to use on a you know more simple payment system or a more general one you know it depends on a lot of these of these factors I would say a few weeks ago Tarun and I actually did a talk where we tried to we were kind of talking about like this idea of monetizing privacy and this proof of necessary work was like a

component in that idea it's actually an idea that originally came from a talk that Tarun did with Georgio's at the ZK summit I wonder I mean I kind of I wanted to sort of wrap up this interview with just like a little chat about this because I don't think I've I don't think we've talked about it on the podcast before it might be interesting for people to start thinking about it yeah so I think one interesting thing about the philosophy is difference from from going from sort of traditional proof of work to a snark based work is that you know traditional proof of work was monetized by just evaluating hash function and having sort of this VDS like property but like instead of it being a delay the delay is

given by the hardness of the hash function or like the discrepancy I guess something like that but the you know I think especially if snark proving becomes a form of monetization because it it serves as the security bond for the network in some sense you can tie the security bond of the network to some type of privacy preserving aspects of a blockchain because you've now have found a way for people who are generating proofs that can be potentially that are preserving to some extent privacy if the snark is say proving verifying the state-transition of a bunch of transactions on blockchain but not you know not putting all the transactions on

chain you you're basically rewarding people for preserving privacy versus you know normally you resort you reward people for violating privacy so you know how do you how do you see se proof of necessary work as something where society can can actually provide a mechanism for for rewarding people for preserving privacy instead of sort of the monetizing ones data so yeah well first thing I say is I think the dream is good figuring out an incentive compatible way to ensure that the privacy related stuff is resolved I think that's the kind of right approach now in terms of how I see this fitting into the kind of work that

we've been doing in a sense I think of it as a as something that allows for a skeleton sort of chain in which people can plug in snarks of arbitrary computation in the sense I would take a step back and say you know it's it's really so it's really just an incentive compatible sort of backbone in which you can plug in verifications of specific kinds of computations and the privacy isn't so much on the transaction between two entities but rather on the privacy of the computation that is being done or that is being verified so I just I just seen that you know proof of necessary work as a first step towards trying to realize a system whereby you are able to find a

counterparty that's going to mint verification of arbitrary computation for you on a distributed ledger that's append-only and I feel like that sort of goes in into what you're saying in the sense that the privacy of the computation is something that's a feature in in all of this and and it's something that people are incentivized to do because the rules basically spell out that this is what you've got to do and but yeah but I see proof of necessary work in the context of you know enabling the maintenance or in a decentralized way of an depend on the ledger of records so in a sense it's record-keeping only that it's in this most general form that you know if you

use the right snarks or any of the snarks people use you can get these guarantees in zero knowledge and and and that I feel sort of comes on top of it and allows you to basically keep that kind of ledger out there because that's really the hard part right being able to maintain this thing without having centralized parties I would I actually so I would love to continue that conversation that idea of like by monetizing privacy potentially making it more than a nice to have but like deeply embedded in sort of a feature set it it comes along with the incentives it comes along with like the entire building block of the protocol but I think for this episode we kind of have to wrap up

which is a shame but it's been such a pleasure and it's been really fun to explore this topic in way more detail I definitely am walking away understanding it a lot better so thank you so much thanks a lot guys for having me it's what's fun well I'm just a guest so you're the guest you're the guest host thank you so much for coming on as the guest host this week I really liked having you here that's cool thanks Tom all right so then I guess to our listeners thanks for listening you [Music]