ZK Whiteboard Sessions – Module Fourteen: Nova Crash Course with Justin Drake

Transcript

foreign [Music] welcome to another episode of the ZK hack whiteboard series um I'm Brendan I work at polygon and I'm here with Justin Drake uh Justin is an ethereum researcher he is I would say a polymath focused on crypto economic design zero knowledge proofs Hardware acceleration vdfs um every anything that touches the ethereum L1 so welcome Justin yeah thanks for having me Brendan um and what are we going to talk about

so the topic for today is Nova what is Nova good question um so Nova is a fairly recent construction that was published on the print in around March of last year so it's just over a Year's old it was invented by srinath seti and it's I kind of think about it as a pre-processing step for snogs so it's not a snock in and of itself but it's a very powerful technique that when used with a general purpose knock system can give us kind of the The Best of Both Worlds in terms of

in terms of very fast prover time and very very fast and cheap verify a Time cool sounds great um all right so what uh so it's a snark um it's used for batching or recursion or so how does it work yeah so um one way to think about it is as a generalization of BLS signatures so if you have um BLS signatures you know S1 S2 all the way up to SN the idea is that if these signatures are all signing over the same message you

can aggregate them and only have to verify the Aggregate and we use this actually on ethereum today on the beacon chain and this gives us roughly a 1000x Improvement in verification time because instead of verifying in signatures you essentially pay a cost to just verify many with sort of one operation exactly right and you can think of a signature as being a statement the statement being I know a private key that corresponds to this C uh to this public key and I'm signing over this message and you can ask yourself okay can we generalize the statement to be any NP

statement uh and and this is exactly what Nova does so you have S so you have n statements and instead of having to verify each of them individually you fold them together so the the term that is used as a folding scheme you fold them all together and then you you only have to verify the last folded instance cool so so I I guess for the non-complexity theory uh heads out there it's so I had these computations and yeah in normal sort of snark terms I would have to generate a snark proving that each one is valid and so instead I don't uh generate a stark I just take the statements I use Nova to

fold them together and then I can just verify the folded version yes because snox are very heavy machinery in the grand scheme of things and here basically it's a way to feed less work to the snog prover and do more pre-processing work up front very cool yeah and so one of the constraints here is that every statement has the same structure right just like BLS signatures every signature is a signature um the good news is that in the real world we have structure everywhere one example is vdfs and we can talk about this verifiable delay functions but maybe a more general purpose example is a virtual machine you think of the

ethereum virtual machine or think of a risk 5 CPU or a mips um um where basically you have cycles that are repeating over and over again just like a real CPU where the the configuration of the transistors is fixed that's the structure and then what you feed into the transistors is what changes that's that's your witness okay so so I I it wouldn't work if I was doing um maybe some elliptic curve group operations here and then hash functions here but uh in reality like what we're often concerned with is um like verifying the execution of some virtual machine that's doing the same

thing at every step and so we can exploit that repeated structure with Nova exactly cool right so in in just the same way that um the ethereum virtual machine kind of gives you escape velocity for programming whatever you want on top of it but the evm itself is fully fixed and immutable and ossified and difficult to change here is the same thing you can have a very fixed and ossified virtual machine that allows you to express whatever statements you want on top of it very cool so what is uh what sort of Nova being looked at for today is the ethereum foundation uh currently working on a project with Nova right so we're working with three nav on

the vdf project um so vdf stands for verifiable delay functions so we have these three letters and function is just means that it takes an input and produces an output this is not one of the most important letters this is maybe the most important letter which is the the delay part so Computing the output of the function takes time and the way that we mimic the notion of time with computation is using sequential computation that cannot be parallelized so you have an input you perform computation on it which is sequential that computation might take let's say

one nanosecond if you do a billion such steps then you simulate it one second's worth of delay and the verifiable aspect means that if you're a a verifier a weak verifier for example a blockchain you want to be convinced of the correctness of the output without having to do all the heavy work of doing the the sequential computation you want to be able to immediately verify the output so so you could prove to me that that something took you five minutes but it would only take me a couple milliseconds to verify that proof so if I'm like a validator on a blockchain I don't have

to do something for five minutes to ensure that you know you were bounded by some delay exactly and the way that we use Nova for vdfs is by having a a two-part construction of vdf so we start with what we call a Proto vdf and the idea of a Proto vdf is that you have computation which is inherently sequential where going in One Direction is significantly harder than going in the other direction and the computation is reversible and one way to do it for example is by taking roots in a finite field so if you

take let's say the fifth root and you just do that again take the fifth root fifth Roots fifth root taking fifth roots in a finite field takes let's say a hundred operations but verifying a fifth root only takes a few operations because you only need to multiply a number with itself for four times and so going in this direction is about a hundred times slower than going in in this direction and what we do basically is that we um because we have this asymmetry we have we stand a chance for a snock-like prover to actually prove the easy

Direction which is equivalent to proving the hot Direction and what we do is that we basically take batches of these fifth roots and we fold them together and then at the end we only have to check one one batch cool so so to generate the uh the function outside the circuit it took you a long time yes but at the end you're able to hand me a snark that I can verify very cheaply that shows that the 3DF process or it allows me to verify the video um cool so yeah I guess what um what other like where do you see Nova playing into the ethereum ecosystem

right so um one of the the big themes nowadays and is I guess what you're working on as well uh a polygon is ZK EVMS um it's kind of what's what's Ezekiel good question so it's basically the evm the ethereum virtual machine which is snogified so let me write down evm e v ethereum virtual machine right so VM is a standard term which means virtual machine you basically simulating something like a CPU and E stands for ethereum is basically the ethereum

variance of the the VM and it was designed to um be useful in a in a blockchain context um and what we're trying to do basically is make the the job of processing transactions or more specifically verifying the validity of State routes that progress with transactions so you have batches of transactions that come in these are called blocks you feed them through the evm and that progresses the state and then you identify the state with a state route and you want to prove the validity of these State routes and if we use a a snark like proof system we

get these very easy to verify proofs that might take a few milliseconds to verify and that bypasses all the work that you have to do to kind of naively re-execute all the transactions one by one cool so so replacing so if I'm running my full node I won't have to uh you know execute every transaction and block I'll just download a proof download the updated State and and check the proof that sounds great exactly right um and because the evm is a is a fixed VM it has this structure it has these cycles that repeat and repeat and we can use this technique of folding um and if you if you zoom out

I I kind of think of Nova as being a pre-processing gadget for stocks so snox is very heavy machinery right which you only want to use if you really really need the benefits of snox but what you can do basically is take this repeating computation and then without having to deal with snacks at all start folding and pre-processing that and then you have a much smaller statement that you feed into your your snock prover so that you get a tiny tiny proof at the end so so that's really interesting maybe we could draw that out yeah and so I think that's an important point

because with Starks we were paying for succinctness right like we're paying to to have small proofs and so you're basically saying uh look for ethereum transactions in a block we don't need to to generate an individual snark for each one and pay for like sort of pay the cost to to shrink the verifier time instead we can use folding reduce the size of uh the statement that we're trying to prove until it's more efficient um to sort of snarkify it and make it exactly so you have you have two um kind of tools at your disposition one of the tools is a snock and that's extremely expensive

relative to the other thing and basically what it gives you is compression you can compress into something which is absolutely tiny to to verify but you want to feed as little work as possible through this compressor and so it's what you what you have is basically a hybrid system where you combine the compression with something else which is the folding and this folding stage kind of dramatically reduces the amount of work that you have to do in this compression stage um and so really you get the best of both worlds on the one hand you get

extremely fast proving or should I say folding and on the other hand the output of the compression is a very small and succinct proof yeah so so this is this is sort of our approach um we we use fry instead of Nova but at polygon we're trying to exploit this trade off in a very similar way where um proving ethereum transactions is the expensive part right and so we don't want to compress and we want to use a configuration that allows us to maximize proving uh time or I guess minimize proving time and maximize efficiency and then we can compress at the end when we like post to the blockchain and verification time starts to matter right

so I guess what you're saying is that let's use two snacks for both steps but these are stocks that are optimized for different things this one's optimized for fast and cheap verification this one for fast and cheap proving um but I guess the the realization of Nova is that you don't even need a stock this is overkill you can achieve something uh you you can get the power of snox by just using a folding very cool all right let's uh let's dig into Nova yeah so I guess we can look at some of the nice properties that folding has um one one of them is that there's only multi-expronunciations there's no no

ffts so why is this why is it nice to avoid ffts right so one reason why it's nice to avoid ffts is that you're doing one thing you're just doing multi-experentiations and if you want to accelerate a stock for example in the extreme build a snock Asic you want your Asic to be fairly simple um so that's one one advantage another Advantage is that um you don't need much memory like these ffts can be memory hungry but the multi-expensations they're much more streamable which is also good for proverb performance

um and I guess another Advantage is that the steps that you're folding into each other can be very big if you need to um and again because you don't have these constraints on on memory and so if you take an approach where you know you have a a very evm equivalent circuit that could be a humongous circuit um each individual step and you're not limited by the the memory constraints of the nft then fft yeah and we're also not limited in our choices of elliptic curves right because we don't need multiplicative subgroups for the effectives exactly yeah that's that that's a great point and actually the the curves that we're working with also don't need to be pairing friendly yes

um and so actually it turns out that you can use um SEC P which is the exact same curve that is used today for ethereum signatures and for Bitcoin signatures um you don't have to to invent exotic things um one thing that you do need however is what's called a cycle of elliptic curves and SEC P has kind of this dual friend which is called SECU and these two combined uh form a a curve okay so so what's this so how does this cycle work maybe we could diagram oh yeah for sure um so a cycle so the way that you define an elliptic curve is with basically

What's called the the base field so you have a field f and then that allows you to Define an elliptic curve which then generates a scalar field so um you have another field here ffp so this would be fq this would be FP and it turns out that there's an impossibility result whereby the p and the Q have to be different and so the question is can you have two curves such that the relationship between

the the base field and the scada field is symmetric for the for the for the two curves so one curve has FP as a base field the other one has fq as the base field and vice versa for the scalar field and this is useful because we are defining our constraints in the scalar field of of the elliptic curve so we're sort of programming in that field and we want that but we're verifying our proofs in the base field and so we we want to be able to efficiently we want those fields to match so we can efficiently verify base field operations in the scale of of one curve in the scalar field of another and vice versa exactly so one of the things

that I haven't touched on yet is folding sorry it's recursion in addition to the folding so it turns out that when you when you fold a statement into another I lied a little bit when I said you only need to verify the very last folder statements you also need to verify that the folding was done properly okay but the folding checking that the folding was on properly is very very cheap and so what you can do is you can actually do it as you go along in your circuit okay so you have your initial computation which is fairly large and then you add just a little bit of overhead to perform the recursion and

as you said in order to verify that the folding was done correctly you're working in the base field because you're working with elliptic curve points but the constraint System is using the the the scalar field and so really what we're going to have is we're going to have this this back and forth between the two fields and get the efficiency on both sides cool so so when we're folding maybe we could diagram that we're not we're not sort of compressing all at once we're uh like folding one into the other and and we have this chain of yes okay okay so let's let's draw this yeah so

the idea of uh of novice that you're going to have what's called a running instance so this is the the instance in which you're going to fold the statements progressively and it starts effectively empty the the the the the the trivial instance and then in red is where I'm going to be doing the real work for some repeating function f and then the next step is to fold the real work into the running instance to produce the next iteration of the the running instance so basically we're folding these two into here and the node here is where the

folding happens and then we're going to do more folding of real work and and the the pattern repeats so the red arrows are kind of the that repeated computation that we sort of Drew earlier um and the black is uh I think it's sometimes called an accumulator in the literature but basically tracks this uh like the progress of our folder right you could call it an aggregator if you're using the terminology of business aggregate signatures or you could call this an accumulator of sorts um now the as we said there is a cost to verifying the that the the folding

happened properly and so what we're going to do is this little trick where we're going to augment the function f to become a function f Prime so there's a there's a prime here in green and we're going to have F Prime verify that the folding done here all right was was done properly um and so basically the each step that does real work is also checking that the folding was done properly for the previous step okay and then now my statement is true my initial statement is true which is if you verify

the very last folded instance then you're kind of unraveling everything checking not only the validity of every single iteration of f but also that the folding was done properly yeah yeah cool so what um what are some of the concrete uh kind of performance characteristics of of Nova you said it's really fast right so there's no ffts you're only doing multi-expensations and the question becomes what is the constant so if you have n constraints for example nr1cs constraints you have to do um

basically two you have to do two multi-explanations of size n okay so basically the the constant is two which is at least a factor of two then the next best thing and if you take a proof system like Planck for example or graph 16 you you'll be several times faster than them and and also you don't have to do the ffts um so you're winning and also because you don't have a pairing friendly curve you have more performance so you might have let's say 2x more performance here you might have let's say

I don't know 4X more performance here here you have no ffts so that might give you like simplifications and a bit less less work to do and there's another benefit which is that the so-called um recursion overhead is very very low so this the verifying that the folding is done properly is dominated by two scalar multiplications okay and if you if if you were to write this as a circuit which is what we are doing here with this function f Prime it's on the order of twenty thousand Gates

so it's a very small recursion overhead which might give you you know a further boost here so potentially you can have a proof system which is roughly 10x faster on the folding than if you were to use a snock naively yeah yeah yeah it makes sense because we we want to minimize both the cost sort of the proving time for our statement but also if we're doing recursion or aggregation we need to minimize the the cost of actually performing the recursion yes exactly I mean and zooming out one of the the trends in in in snox is is recursion recursion is extremely useful for many

different things it allows us for example to break down very large statements which are too big to chew for snobberists and break them down into small chunks it allows us to have distributed proving where you give out work to different people all different um you know CPUs or different cores we within a single CPU so you unlock parallelism and distribution distributed proving and you also make it potentially easier to build Hardware because you can you can feed this uh these these chunks very cool yeah um let's see what are other advantages of uh of Nova

um I guess one of them is that there's no trusted setup so it's the transparent proof system and the general approach is also post Quantum upgradable meaning that if you want to use lattices instead of Peterson commitments um then you get you get you get the same construction which is uh instead of being based on the discrete log assumption you might base it on something like the lwe Assumption so it's a different assumption the one which is afford to be post Quantum secure so for the for the folding step we just need some additive

homomorphism or some structure and we can get that with with lattice exactly the the one constraint that we that we need is a linearly homomorphic commitment a vector commitment scheme right um now this this this technique of taking linear combinations you know is used you know for example with with polynomial commitments um but here we don't we're not even working with polynomials we're working with something which is less powerful which is purely a vector commitment um so that's kind of another Advantage as well here cool Okay so we've gone through the high level stuff let's start looking at some some of the the the details

um and I guess what we can do before diving in too much into uh the actual details maybe we can start with a warm-up example um so let's let's start with very simple statements uh which you know don't give us all the expressivity of MP but you know it will give us an idea of how things work so remember how I said that every statement needs to have the same structure so let's define the structure let's say that we have some Matrix a it could be any Matrix it could be one that's randomly generated for example and we have statements of the form a x i equals some Vector for example

the the vector which is all all ones okay which I'll I'll write as bold face one now let's say that as a a prover I claim to have two such vectors which satisfy this um and so I have X1 and I have X2 and I'm going to tell the the the the the the the the the verifier what the commitments of these vectors are so we have the when I have a line on the top I mean the commitment of X1

and the commitment of X2 so the claim really is here that I know two vectors X1 and X2 that corresponds to this commitments such that both X1 and X2 satisfy this now the verifier is very lazy right he doesn't want to do much work um and so kind of the naive approach would be for the prover to send over X1 to verify to check that it matches the commitment same thing for X2 and on top of that not only is there a lot of communication cost but there's also computational cost because the verifier needs to do this this Matrix operation

so instead what happens is that the verifier says I'm going to give you a random number okay and this is a classic cryptographic thing where we have an interactive game so the prover sent these commitments um so that's step one to prove that sends the commitments the verifier so the verifiers on on on the right side the provers on the left side the verifier just sends a random number r um and then the prover will will basically take both the prover and the verifier take a

random linear combinations of of these vectors so they take X1 plus r x 2 and the commitment corresponding to this Vector is going to be the same thing but with a hat so it's going to be X1 plus r X2 committed but because of the linear homomorphism of the commitment that we talked about earlier this is actually equal to X1 plus r X2 and so this is something that the verifier can can compute and now the proverb

just needs to send one single vector which is the opening of of this thing here the verifier checks the opening and it can check this operation so basically what we've done is that we've we've halved the amount of work and what is the the cost the cost is basically um one scalar multiplication plus an addition which is very very cheap for the for the verifier and this technique here what we've done is that we've folded two instances but we can fold a million a billion instances and still end up with this very very cheap thing at the end and these these commitments were just using the Peterson commitment

to generate um X1 and X2 hat and then uh so so instead of what we're doing is we're saving um the the verifier just needs to check uh a times this uh term instead of checking a X1 hat and then ax2 at yeah so instead of having to check a X1 and ax2 individually which requires one kind of receiving X1 and X2 kind of downloading all this data and then two doing the computation um you only have to download the data once for this random number combination and do the computation once um

right okay um so I guess the question is how do we go from this toy example uh which hopefully gives you the intuition to something more expressive so it turns out that like the one of the standards ways to to express an NP statement is with uh what's called r1cs so r1cs how does it work you have three matrices these are square matrices a b and c and these are going to define the structure of your computation and then the equation that you have is going to be

a Time times a vector Z times B times the vector Z equals c times the vector Z and so this this um round circle here means that you're taking the element by element multiplication of of vectors so the the dot product of the because vector vector exactly yes or sorry no not the doctor before the staff uh product yeah yeah so it's element wise multiplication so um the A B and C are matrices a times z

b times z c times Z are vectors and this Vector times a vector is is a vector now it turns out that um this trick of taking a linear combination let's imagine that Z is going to be a random linear combination of Z1 plus Z2 with a with a random coefficient it turns out that if you if you plug in a z like this and you expand it out you you get cross terms and by cross terms um we mean kind of

when you have both indices one and two that are involved and so what we want to do is actually generalize this r1cs to something that three enough has called relaxed r1cs and it's relaxed because you allow two things one is that you have an extra vector e which we call the slack vector and then we have an extra coefficient here U which is a scalar and so now your your witness for the statement is z u and E and the structure is still a b and c and so these terms just let us cancel

out the cross terms that might come up when we are taking the hadamard product of this error that you have this yeah exactly so the the the term e here absorbs will absorb the uh the cross products um so it's kind of a a more flexible r1cs that um and this this flexibility allows it to um to take the shape of what we want so basically what we want we want to be in a position whereby proving two statements of this form so basically where we have

a Z1 times B Z1 U1 Z1 E1 and proving the same thing but with a two a Z2 B Z2 equals U2 cz2 plus E2 proving these two things is equivalent to to proving a statement of the form a z b z equals u c z plus e where Z is this random linear combination

um yeah it feels weird to be going back to r1cs after so many years and uh in plant uh constraints this is interesting right so this this we started with rncs but we it turns out it's not flexible enough to do the the the folding but it it turns out that um you you can have much of the expressivity of other things like like the plan cash arithmetization or things like look up using relaxed r1cs very cool yeah um all right so so how do we how do we adapt uh this technique

um I guess it's straightforward adapting it to this relaxation yes yes it's it's straightforward but really what I have to to to do is kind of tell you What U and E must must be in order for this equivalence to be the same okay and you can just write it down and do the arithmetic but um I guess I can just you know tell you tell you what it is like you is going to end up being um U1 plus r U2 so very similar looking to to this guy and then e is going to end up

um being something like E1 Plus r squared E2 Plus the cross terms and the cross terms are going to look like a Z1 times B Z2 plus a Z2 B Z1 minus U C U1 cz2 minus U2 c z one

and every single cross term are basically crossing the ones and the twos and everything cancels out and everything works out nicely uh when when when when you plug it in cool so so when we we actually write uh constraints for this uh form we're defining like our sort of program is is is it a b c and e or is e uh part of our witness how does that so e is e is part of the witness okay okay yeah um and I guess one one important question here to to ask ourselves is um

what is going to be the the the cost for the for the for the verifier to come to keep an updated version of e u and z um and actually I for Z and E is going to be commitments of these things the verifier it's just like just like here basically the the verifier is only working with commitments these commitments are very succinct and so they're very easy to to work with but but as long as we have our linear homomorphism we're sort of set and we don't have to keep it exactly and so we can have a look how many scalar multiplications are there because

that's going to be the dominating thing so there's going to be one one here where you're multiplying by R in order to update Z the addition is very cheap you're going to have one here [Music] to multiply by r squared and in addition what the proofer does is that it's going to send a a commitment to this these cross products so we're going to define t which is all these cross products and the prover is going to send send a commitment to T

and so really what the verifier has to do is compute um sorry there's an R missing here is going to have to compute R times times times the commitment of T so we end up having three and scalar multiplications in the recursive verifier circuit and um this is something that I'll draw uh very very soon when when you're folding um in an r1cs something which is not relaxed but really the the standard r1cs you you end

up in a position where each e is zero right because that's but as a standard r1cs where e is zero and U is is one and so you you end up not having to do this this goes away in practice um and this costs about 10 000 Gates and constraints this is about 10 000 constraints and so together the whole verify verification circuit is about 20 000 constraints cool and we we can sort of see why we need that repeated structure because this uh only works if we if if a B and C are sort of different for each statement then uh then that doesn't work yeah exactly yeah

cool okay so let me try and provide some integration here because we have lots of symbols and and let's go back to the um to to this diagram so we have a running instance which gets updated with the instances where you do the the real work they get folded in and where does the verifier circuit come in basically we want to check that

the work of doing the verification here is correct and so the function here does this verification but one thing that I that I haven't shown yet is how do we work with the Cycles elliptic curves right and so here really we we're not going to have one running instance we're going to have two running instances um and the way that I that I think about it is with a a slightly staggered running instance so doing this this Arrow this green

arrow is inefficient because you have a mismatch in the fields the the base field in the scada field and so instead we want to be working my P here we're working with the prime P here we're working with the prime q and what is efficient is to be to be so here oh because the only thing that you're verifying here is just the folding I'm gonna have a a small a small Arrow because there's very little work to do relative to these red arrows where a lot of the work happens and so this small arrow is going to prove

the validity of this guy and then this guy here is going to prove the validity of the folding here and then same thing happens again these prove the validity like this and these guys provide the validity like this cool great um so I guess one thing that we've achieved here like the the the the the the term that we have here is what's called incrementally verifiable computation I IVC

and one of the downsides here is that you have this extremely sequential thing going on and this is this is not great if you want to have lots of parallelism or even better lots of distributed provers that all collaborate uh on on one task and it turns out there is a generalization of this diagram which gives us PCD proof carrying data where you can have multiple proofers and jointly collaborate and you can unlock parallelism uh do you want to see kind of the the diagrams okay um

so here I guess the the the basic building block is is this this this triangle here right where where the folding happens um and this is what basically defines the ver the verifier circuits that that that powers the recursion and the question is can we have a more generalized triangle that unlocks recursion and the answer is yes so so sort of the basic building block that we use for recursion whether we can have it have two arrows uh instead or sort of more than two exactly

exactly so let's so here we have two input arrows why don't we try four input arrows um okay so let's see we're gonna have two running instances in Black and we're going to have two instances where real work happens we're going to fold these into their own so this is an instance folded of these this is the folded instance of this and this and we're going to fold these two into yet another

folded in instance and this is going to Define our basic green triangle and now basically we want to have a pattern where we can recursively fit in this triangle so that all the inputs and outputs match and one way to do it is by basically having another triangle that come right next to it where okay I'm gonna have to erase erase this guy so we have two triangles each triangle

produces a a running instance so this produces a running instance this produces a running instance and now in order to fit the pattern we need to have two instances that do work two red instances like this and now we can complete the pattern like this and as you can see we have a new triangle here perfect like this but and um so in in reality I I think we would have like another like parallel running instance because we need to uh have our

cycle uh verifying this efficiently but yes yeah that's not not to over complicated yes yes but okay so so this makes a lot of sense that's very cool um and so basically um just to to give a little bit more explanation of of what's going on here is that we have these these instances that do the real work we're folding them but we also want to prove the validity of these these green triangles and this is done in the same way with um basically instances that sit outside the triangle and this is what allows us to do the recursion is like so this red line is going to prove the validity of

this triangle the folding of this triangle and this red line is going to prove the validity of this triangle here and so what we've done basically is um we've we've unlocked this very fast pre-processing stage which is parallelism friendly and distribute and friendly to distributed uh proofers yeah because we I mean if we're doing um if we're trying to process transactions in a block we we can divide the transactions in the block across many nodes and they can all proven parallel and then we can use the folding scheme to end up with our desired single

statement that we can then wrap and we can activate the compressor exactly yeah and I guess one question we can ask ourselves is what kind of compressor do we want at the very end so we're working with Peterson commitments so a very natural thing that we can use is bulletproofs um you need to do a little bit of work basically change the bulletproof scheme a little bit to work with this extra slack Vector um Serena himself has also a variant of of Spartan which kind of works well as this final wrapper and there's another project that different Foundation is working on which

is to have the final wrapper be basically a stock and use fry cool um what's the uh what's sort of the motivation there because we're we're kind of sacrificing succinctness a little bit um with fry right so the the just the reasoning here is that we want the final proof to be friendly to the evm and here we're using curves that are not evm friendly so we're using for example of the pasta curves that's what actually is being used in in production the Cycles oh okay yeah interesting so but but we could

um I mean we we we could use sick p and SEC Q um but then we can't really use bulletproofs uh with those and so okay so the the problem with I guess SEC p and secure is that even though the signature scheme it uses these curves I don't think there are up codes yeah so there's the ECU recover up code but I'm not sure there's all the other op codes that you need yeah that are exposed yeah okay okay so just being able to do uh like doubling and addition we we can't go right yeah exactly um wow so we've uh we've gone through

Nova we've learned about folding recursion we've moved from IVC to PCD um so where can people go to find more right so um as I mentioned like the the scheme is fairly recent it's from um March 2021 and there isn't that much educational material there's the paper on ePrint there's one 20-minute presentation by 3.5 on YouTube and there's also um about 10 pages uh in the Justin fellows book and actually I just learned that there is a Justin Fowler kind of study Club as part of ZK hack where a group of people including Justin himself

are running through the whole book so if that's of interest to you um do join that discussion um so yeah that's in terms of the educational material and I I feel like one reason I was excited to talk about Nova is because not many people know about it and I think there's a lot of potential there to uh to help with uh with ZK VMS potentially and one of the exciting things is that not only has three enough written an academic paper he's also written in Rust very high quality code an open source implementation which you can find on GitHub github.com Microsoft slash Nova

yeah MIT licensed um yeah srinath is one of the best I think academic uh sort of cryptography Engineers that his implementations are always super super fast right um and not only is its class to start with but we've also been collaborating with supernational that has made it even faster both in terms of having a super optimized CPU implementations of the the pasta operation pasta operations but also a GPU implementation acceleration for the the most consuming operations which is the multi-experunciations so you can take something which is off the

shelf and extremely fast pre-processing for your ZK evm very cool so so we we can see Nova in hopefully vdfs in the ethereum based chain potentially a future ZK VM um and yeah whatever future work so sort of comes from that yeah I mean there are some questions I guess for implementers um one question might be you know what is the the best final proof to use like one of the downsides of bulletproofs for example is you get succinctness of the proof but you don't get succinctness of the verification time the verification

time is still linear in your step size and so um I think the work that we're doing with the Mina foundation and the nil Foundation to use basically fry as the final step is going to be uh a useful primitive for the whole Space um this project is you know relatively ambitious and it's still in in the work and it might take a few more months uh to to really be be polished but um actually the the reason why we're we're working on frying I guess um

pasta multi-expensations is because the the Mina blockchain its proofs uses the pasta curves and we want to build a bridge between the Mina blockchain and the ethereum blockchain so it kind of allow us to have code reuse with the with with the Nova project there and I guess another question is around having to use r1cs right as we as we talked about um and you know people have been used to custom Gates that are very you know expressive and people have been used to things like like pluck up um and you know for example for custom

Gates one of the things you can do if you have a degree more than two gates you can reduce them down to degree two gates which you can do with our own CS um and um Serena also believes that there's a uh she's been talking to a PhD student quite a long time ago where basically the claim was that you can do pluck-up queries fairly cheaply even with r1cs you know something like five constraints for one lookup query I need to look into the details here and it's possible there's other teams also doing kind of independent work to kind of make these techniques be friendly to more

arithmetizations than just our NCS cool cool very cool um yeah I I I really was surprised by how how simple and sort of easy to understand the schemas and so right that's that's a cool feature well great thank you so much Justin um for for joining me um thanks to Anna and Tanya from the CK hack team and uh yeah we'll stay tuned for more on Nova yeah foreign [Music]