ZK Paris: Chao - Nova Folding with MACI Circuits

Transcript

foreign folding with Mackie circuits by chalma at PSE [Applause] hi today I will talk about the no RVC Macy so basically we apply the Nova folding skin on the missing circuits so my talk consists of three parts the first I will give a brief introduction to Missy and the Nova and the second part is about the engineering implementation and the last is about the future work so Missy stands for the minimum anti-clusion infrastructure which

originally proposed by vitalik and this is a Anonymous engine building system so the major issue that Messi wants to solve is the off-chain primary issue so basically Alex can buy the Bob's private key and voting represent the vote for the so basically basically Alex can break both and buy his voting key to vote for her so this is a major issue means you want to solve and the technical underlying technical part is about using the circle and the back end is a growth grade 16. so this is our common implementation so there are various applications such as the anonymous voting as well as the

anonymous like a quadratic funding so like a clear tool found and purify to such projects and the code base is in the under the PSC repo so Nova stands for the recursive zero knowledge argument from the folding scheme so Nova is one kind of the IVC and IVC stands for the incremental verifiable computation so so the traditional or the before the Nova the IVC usually involves to verify the proof for each of the step circuits and after the Nova instead of verify the proof we can just extract the accumulator or what what the Innova

called the R1 sales instance from the IVC circuit and fold it into the running instance so you can assuming this is also kind of the accumulator from the traditional language of the IVC but without verify the proof of each step and they are basically two components in the IVC circuit so one component is we have to write a circuit to prove the step circuit function is correctly executed so the input for example at the step I is zi and we have radar circuit so f is the step circuit function output will be there plus one so this is one part of the IVC circuit and the other

part we have to correctly folding the little U and capital UI so here the little UI is basically extracted from the IVC circuit as accumulator and the capital UI is kind of running a cumulator so basically it contains the information from all the previous steps we have running for the IVC circuit another recursing overhead for the IVC circuit is kind of minimum it's only dominated by the two scalar modification and the normal code is also show up here novice Nova Scotia is a library written by nulling this is used to transform the circle circuits into the Nova step

circuits so we can using the Nova Scotia together with Nova to just folding our music circuit so that is all the two tooling blocks we needed so the second part I will talk about is the engineering detail about the implementation so here is a basic workflow we're starting from the amazing contract and message circuit so from the music contract we're basically using the message COI to extract the necessary States as a circuit inputs and also Mississippi will generate the R1 CS file needed by the Nova so with this output the novice will call the Nova Scotia to

the R16 file to get the public parameter which is depending on the size of rxs and also create the IVC circuit from the information of the rncs and also we can generate the witness from the circuit input and around sales file so with all this output from the Nova Scotia we can directly call the Nova Library so basically normal Library will take the output from the novice question and generate the recursive snack for each step so suppose we have unzip we'll just apply this end times together final recursive snack or the compressed recursive snack so as a last step we can just call the verifier So currently we

have the off-chain referral writing by the novas Library so right in Rust we can verify it so after the verification passed it means of the previous own steps is correctly so this is basically the workflow and the next I'll talk about the cycles of illegal curves so basically in Nova we're using the cycles of 11 curves the reason is that they are the dominating operation is a scalar multiplication and the ellipse curves contains two Fields so suppose here the definition of the ellipse curve is y Square equal x cubed plus X plus b in the real stress form and the X Y is the coordinate and they

belong to the base field and whenever we have the scalar multiplication a Lambda times the point down the curve this is basically the Lambda naturally located on the scalar field and for the parent finale curve we cannot find such such field that FP co-fr so the best we can find is like cycles of curves so basically we can find two curves E1 and E2 and this satisfy the same equation so basically A and B is exactly the same for this E1 and E2 however the base field one is the scale Middle Field of the other so when you write a constraint system the constraint system is naturally using the scalar field so whenever we want to do some operation on the base field for example for the

scalar multiplication this involves a lot of operation on the coordinate which is the base field so one way is we can using non-natural field using the scalar field to emulate the base field to do this we have to do the big integer big integer operation so this is the cost is higher than using the natural field so why there is without this kind of operation we can using the constraint system of the Dual curve because the Dual curves scalar field is equal to this field of the current curve so basically we can have two running system constraint system and whenever we want to do the base field operation we can use the Dual curve constraint system to

verify that so basically the here the most heavy operation what I mentioned is the scalar multiplication for the electrical point and the example is there are for example the palace Vista curves this is one type of due curve and is used in the Nova implementation and this is another curve called The bn256 Curve so this is what we used in the Missy as well as any Syrian solidity so basically and luckily we also have the curves for the bn256 curve so basically the cycle is a billion 256 and gromping curves they also form a due curve and the next slide will be the engineering work on this implementation

I just listed the major part we needed to do so from the Missy part the first thing is we have to change our socket interface follow the standard defined by the Nova so basically you have an input of the step circuit and output of a step step socket and the input and output format and the dimension should be the same so basically z a and Zi plus 1 look similar similar format and the zi will be the information for example the hash of the state and some auxiliary variable such as the index of each batch so here the state means is the state is defined as a hash of the state root of Steel tree and the root of the battle tree so

basically contain whenever we we process the voting message so the voting message is extracted from Smart contract as anonymously and whenever we process each message we actually updated the states of the state tree and better tree so whenever we apply this step function once here the step circuit is a messy socket we will update the state so with this modification and some other modifications such as like unchanged solidity repair for the gross testing and the like a COI to generate circuit inputs with this setup the missing part is done and for the hilt so basically as I just mentioned we have to support the

building so basically the billion 256 and grounding curves using the music oh sorry using the Nova but originally the code only supports the palace and pasta curves so we have to edit the support for new type of curved cycles and luckily in the PSC Ripple Halo 2 curves we we already have such curve support the bn256 and the ground key however one of the missing one of the algorithms missing the to curve algorithm this is used to generate the public parameter or the commitment key for for the Nova so we have to add this report and in the beginning I just write a simple try and

increment algorithm to unblock my development and later I discussed with him from the peer seating and he added a new svdw algorithm into this report so later I will replace my current simple algorithm with hence implementation so with all these Halo 2 curve support added we can edit the support in the Nova repo to support the building 256 and the ground picking curves so with this we have to modify several basically Nova Define civil traits required by when you add into 11 curves for example the group trade which contains the hash to curve algorithm so with all this

preparation we can do our Benchmark so here is the code base for all the dependency we have and for The Benchmark I have tested the steel three depths for the six so basically all the three here is a queen Retreat it means for example the steel tree depth is six so we have a total of five to the power of 6 maximum users and the message to depth is 8 it means we have the five to the 8 maximum messages so with all this setup the R16 file is about 500 megabyte and Z key is one gigabyte The Petal file and the public parameter for the Nova is stimulus similar size like a four gigabyte so this gives you some rough the idea of

the size of the circuit and I have tested the various combination of the user and the vote for users so basically this eventually result is kind of linear with respect to the total voting message so in this case we have like 100 user and 10 votes per user so which is a 1000 votes uh according to this like a message batch three devs used to so basically you have five to the five square 25 per a message per batch so you have the one thousand divided by 25 which is 40 batches and you can assuming from the missing perspective we treat it batch by batch so each batch is kind of one step of our circuit and here is the Benchmark

the time cost is in the unit of seconds so the generator circuit input is common for both missing and Nova Missy this is the right in the message using JavaScript is unoptimized and the most time consuming part is about 460 seconds and for the crease improved for music part is everything for the create proof except the general circuit inputs part so this is about like a 170 seconds and because as we just mentioned when we do the Miss Nova voting we don't need to using the proofs so there is no such step to Creator proof and we only need to do the folding and so no one

Missy for the folding part is the total time is about 38 seconds so it's using rust so as you can see for this part is faster than the BC however the current dominating time is still in the generated circuit inputs so I would say in total time it's kind of slightly better from the povert side however because we are using IVC it means in in this test case we have 14 batches so in the original music we have to verify on the solidity verifier 14 times however with this setup we only verify one time for the last step so basically you greatly reduce the verifier verifier unchanging gas cost with this approach

so that's a benchmark result and the future work is uh so the first thing we have to add is unchanged solidity repair So currently I'm only using the off chain welfare already using writing in the Nova Library so we have to export it the verifier to the solidity so we can Implement a small contract verifier and because the Nova using The Spar down very viruses this is something we plan to do and the next is add the support for the other missing circuits So currently we only do the do the circuit for the process message for all the users voting message so next we'll do the televotes and the subsidy calculation so this is the two other

features in music so that is all the future work and thank you and the Furious reference hello so my question was um did you explore the idea of basically proving sorry verifying the Nova proof in another snark prover such that then you can verify this proof efficiently on chain like verifying the Nova proof in a growth 60 improver so you basically

reduce the size of the Nova proof and you eventually verified efficiently in uh on chain so you don't need to write the Nova verifier in solidity yeah I think so you mean we instead of using Spartan welfare we verify this in the using the like row 16 right verifier part so as I'm uh so in this slides so here the recursive snack is something without the ZK and without in any compression so we can using ailing back end for example in the novas original paper they just using Spartan but we can also using like row 16 as to

compress the recursive snack so in this case we can writing uh let's say girl 16 very fine chain yeah so we can just decide which one to choose yes okay do you know if this tooling are already existing like a uh I don't know if there are already existing one if it's existing one we can just use it yeah otherwise we will just implemented ourselves yeah yeah cool thank you I just wanted to say quickly on that it does exist it's called it's called testudo this other girl sex thing it combines Spartan with uh growth 16. Okay cool so

I think I will search for that any other questions [Applause]