Introducing gnark, a Zero-Knowledge Proof Library

Transcript

all right sure so I guess we can start so thank you all for coming I'm here to introduce knock it's a fast and efficient she won alleged proof library written in go so first an overview of knock so what is knock at the first glance knock is a fast open source she wanna let proof library written entirely in pure go it's licensed under Apache to currently we support the growth 16 protocol so as described by the talk of Lawrence Kirk

before we plan to add more talks in the two or three more protocols in the future namely protocols that allows to have a universal trusted set up enough to write circuits you use the API that we provide so I'm gonna discuss that a little bit later it's not a DSL it's an API and now takes care of the rest in particular it solves rank one constraint system and of course knock exposes the standards related functions that we all know so the set up proof and verify algorithms we also come with a

command line tool so you just have to call narc setup not proven not verified so in short knox enables normal development cycle for your knowledge proof and the hope is that the API will abstract away the complexity of show knowledge proof that tend to confuse people and we hope that knock will enable flexible integration into complex solutions all right so first what is she wanna let poof so I will not dwell on that too much as I was a talk by lunch Kirk earlier this morning that described it pretty well I

just want to remind you of a couple of important properties of show knowledge puffs the first one is called computational integrity so the idea here is that if Alice wants to prove to Bob that she knows the input X such that when given to a program or circuit P it outputs y she will provide the proof and if the proof is valid it must be that the input is correct that is she cannot craft fail-proof a proof that is valid with an incorrect input and also one of the very powerful properties of snark is that the cost for

Bob to verify the proof is in fact much much smaller to actually execute the program P itself it's very important properties property for scaling solution on a theorem and it's a it is used for scaling solutions such as roll-up for instance so it is computational integrity and there is privacy so I'm sure that everybody here knows what this is so the idea here is that Bob is coming when he verifies the proof and if the proof is valid Bob is actually convinced that the execution and the input X that gives rise to Y is correct

but he learns nothing about X so you have notion of private input in this example X that is not known at all by the verifier of course it is used for doing private transactions in the cache where you have to prove that you know spending key of a given node okay so now I'm going to describe a little bit more in details gross 16 protocol so the protocols that knock support so in this protocol you have three main algorithm which shall set up proof on verify the setup phase you have

to done it you have to do it once per circuit basically you give to the set up a program or a circuit P and it will spit out proving key and a verification key to prove a statement so if Bob wants to prove a statement that he knows X such that when X is given to P it gives rise to wire he we call the proving algorithm he will give to you to the proving algorithm the program or circuit P he will give the private input X and the public input Y and the polling key and this algorithm will spit out a proof so concretely it's

just a short file so it's very lightweight and to verify poof Alice will call very file doorjamb and the program P and the claimed out input Y he will use a poof so the short file and the verification key and basically the verification procedure will output valid or invalid according to whether the proof is valid or not usually so typically the proving part is done obtain it requires a lot of work from the pool and the verification part is done on train typically for the cash for instance it is part of the consensus protocol you

have to verify zero knowledge proof to check that the chain is correct okay so the architecture of knock so many you have three layers knock you have the front end so rank one constraint system on the back end so the front end it's it's the user facing interface to write a program you will use a font and so a program is a circuit the idea of the front end is to convert a high-level statement for instance if you want to write a hash function for instance MC function or Poseidon you

write it using our API and knock takes care of converting it into a rank one constraint system so then of course you have the constraint the rank one constraint system itself one of the feature of knock is that it solves automatically the rank one constraint so a rank one constraint it's just a set of constraints involving the variables in your circuit the rank one constraint the rank one name just means that it's a very specific kind of constraint and then you have the back end so the back end you can for the user it's it's a it's a black box you can think of it as CEO knowledge engine so it's where there

is all the heavy lifting so apt occurs implementation and it's where the core 16 protocol is really implemented of course it's a bottleneck for for snacks it's you want the backend to be as fast as possible and of course the front-end you need it to be as easy to use as possible okay so in this snippet of code this is an example of how to write a circuit knock so here it's a simple goal executable so first you have to create the constraint system object so it's a

circuit viable here the second step is to define the input variables so from the first slide those are the X&Y X being private in this case and Y being public and then you specify the constraint system in this case it's a really stupid program it's a cubic equation so some of you might recognize this equation from an old blog post from vitalik and his snack explainers so to write this this function you just use our API so basically it provides the use of our arithmetic function so you can

add add multiply and false variables to be equal and you do that using our API so it's supposed to be to be really easy for user optionally you can sterilize the circuit on disk so it's what you do with the circuit right so dot our ones yes I don't have to know anything about it it's just the extension it means rank one constraint system and it's all sterilized on disk and you knock takes care of everything okay so forth back end as far as the back end is concerned sees all the users

need to know all right they don't know to know anything at all about the underlying protocol no the arithmetic libraries underlying knock so to set up proven verify a circuit you would just have to convert the circuit that was defined previously you just result of you you have to convert it into a rank one constraint system so this is what I do in the first line then you have to declare the proving key and verification key and then it's as simple as that you just have to call the setup to prove and verify algorithm algorithm and this is the gross 16 workflow so as far as the backend is

concerned sees all the users need to know okay so we also provide a common line tool so again it's nothing too fancy here it's really simple just have to call Mac setup with the dot I want zs file so the files that we share alized before it will spit out the cubic sorry is approving the coming key and the verification key so cubic dot PKA cubed VK to prove a statement you just have to call the proving algorithm again it takes as input the sterilized circuit so

proving he and the input so the input it's just currently it's a CSV file it might change in the future in which the user just specifies the input the user has to specify the visibility of the input if its private or public input it it spits out proof object completely it's just a very lightweight file in case of course 16 it's just a file choose under one kilobyte so it's really lightweight and you can prove very very huge statement so it's very it very efficient now it's binary file there's nothing private into the file actually

usually the proof goes on train you can open it you can do whatever you want with it there's nothing private in there verify statement you just have to call verify you give the proof so very foggy with the verification key and the input just have to take care here so knock wants you if you give the private input but in the input file input dot public file you just give the the public input all right you don't don't have to to provide the private input for verifying a proof and it outputs valid or invalid according to whether the proof is valid or not so it's as simple as that okay so a little bit more details about that so as you

noticed to write a program or circuit you use a constraint system object okay it's where we expose our API and it's where you can call the arithmetic functions but actually a circuit it's just a set a set of constraints it's not an executable okay and sometimes you want to debug a circuit that is you want to query the values of some intermediate variables into your circuit to do this we have the right one constraint system object alright to create this constraint system object you give it the produced object it's a constraint system and one

of the feature of nock is that it automatically solve the constraint system okay there are no non-deterministic fireballs you don't need to provide any hint or clues to the solver to instantiate all variables you can use this feature to debug a program so you can query the value of of an intermediate viable just to check if you didn't make any mistake for instance you can think of the I want yes as a internal representation as what is the internal representation of a program is for a compiler okay so a quick example again it's a go executable don't pay attention to the program itself it's a

program that doesn't do anything really in this case like before I create a circuit alright I create the constraint system by calling the API so here I created secret input I give it the name exponent I multiply it by 10 why not I want to create binary decomposition of the temp evil all right the five least significant bits and if I want to debug that is to query the value of the last two significant bits so b0 and b1 I just called tag method okay that takes us parameter a string it's a name that

you will give to the vial ball that you want to to debug okay then you just create a once yes object from the circuit then you create the assignment basically it consists just of giving a value of the secret of public input that you created and then you call the solve method on the and once yes by giving it the input and it automatically solves the constraint system so it automatically instantiates all the variables and you can query some intermediate variables that has been tagged okay so here I call the inspect method it outputs a map and you can query the variables that you have tagged

so here are busier on d1 you can check that it easy indeed equal to 0 1 1 and by default in knock it also had puts a private value input values of the user ok so some of you might have use others or knowledge libraries before and you know that one solution to build constraint system is to actually create your own DSL that is a subset of a long programming language we specifically chose not to do that instead we have chosen to create an API for several

reasons first it allows us to leverage all the nice features of go because we think that go is a sufficiently mature and widely used language which provides robust tool chain using defining a circuit using the Google API it allows users to debug and benchmark their program actually as they would do with any normal go-go program you conversion and unit test your program and you can work in a standard continuous integration workflow also the fact that we expose our own API

[Music] it allows not to be very flexible and to be very easily integrated to complex solutions okay so I claim that NOC is fast but how fast it is really to do those benchmarks we commissioned an edible us instance of 96 CPUs 192 gigabytes of RAM and we compare it against Batman which is a state of the art you know is proof cosec implementation so it's it's logical to to compare ourselves yes this state of

the art intimidation Batman is in rest just so you know so we commissioned this very large instance to build very large circuit up to 10 million constraints so you can notice that for relatively short programs ranging from so the number of constraints you can see it as a complexity of a program ok so the greatest number of constraints the more complicated the program also the longer the program is you can see that below 1 million constraints we are like significantly faster than Batman actually and you might notice that at the end for very large chocolate so

ranging from 1 million constraint the performance of Newark tend to degrade a little bit we have identified the problem actually it falls multi exponentiation for the prover we don't leverage all the power of the CPU and it turns out that we found that for 10 million constraints we only use 30% of the CPU and yet we managed to be 5% faster than Batman we are currently working on that in the coming weeks we will likely find a solution to leverage all spews and the numbers will be greater at the end ok so another

benchmark this time on a consumer-grade hardware so this time is the benchmarks up on a Macbook poll from 2016 with 8 cores says 16 gigabytes of ram we tested it against 40,000 constraints program it's not just a random number it's roughly the size of the Z cash spent circuit and you can see that we still have a significant advantage over the state of the art implementation ok it's roughly 18 percent of performance improvement ok so how did he manage to get this fast in parallel to knock

we needed a finite field library in go which didn't exist or wasn't as efficient as we wanted it to be so we developed in parallel a tool called Goffe it stands for go finite field it's just for ground field it does not handle field extensions ok it's a common line tool and basically it generates a code base given a modulus of optimized code code for a very fast arithmetic library just so you know there is no assembly in here we use the go intrinsic functions instead you can check out

our repo we also have some blog posts some technical articles belt it just also so you know we also found a nice outdoorsman improvement over the state-of-the-art modular multiplication that can be used only for the specific modulus of the curves that we support also we support the two BLS curves and the BN 256 curve in okay so feel free to check the report okay so I'm nearing the end of the presentation what's next NOC is currently released in alpha version we are in the process of

refactoring and cleaning the codebase a little bit so expect significant changes in the coming days or weeks according to demand we will convict some security audits on the code currently there are no security features at all it's clearly setting the git repository we will keep optimizing the code the code as according to feedbacks easier the integration process etc and welcome to the commutation and tutorials okay so that's it knock was written by gotten bottle gasket Oski and me tomatillo we

we are a research team at consensus you're interested in our work we invite you to to check out the route the repo and give us a shout thank you yes thank you create work I have a question I have actually multiple questions but I'll start with the most pressing one how are you planning to deal with conditionals yeah so yep we just said currently we only have the so you you're probably familiar with a select statement from the cache while you select it's how we under it

currently okay so this part is not straightforward for user they they have to be aware that they are building a constraint system so this is one of the part that would be easier with a DSL because with the DSL just for the if they segment and all the software is in charge of taking care of how to implement it here we just via our API we just provide a select statement basically you have to to write the branches of your if statement and at the end you just called select understatement so oh it's a bit edgy monteri theoretically you can do all the stuff that you can do with a standard if

statements the only thing that the user needs to be aware of that so his part is not as straightforward as it would be with a gesture if you check the repo we have a stand STD folder in which we implemented some examples some example some gadget examples in particular we have ETS a multiplication elliptic curve arithmetic and edward curves what akash called the jab jab curve so if you want to know white slide to code knock you can check those yeah we don't under if statement you know as easy fashion at it but it

could be with you today sir how do you think you managed to beat a bellman so what was it was like what's exactly you think is more advanced in your solution and did you measure it against witnessed generations like did you take witness generation as a separate step and profiler and did you compare that so witnessed what you called witness generation is actually is it instant in environment so like if I understand correctly in in narc when you construct the code and you call solve you will generate the witness for all the intermediate variables so the values of intermediate variables for like all

all down the circuit in Belmont this happens during the synthesize like when you call synthesize right and this is actually quite significant part of the of the time and this part is not paralyzed in Belmont unfortunately so I'm curious whether you taking this part into the comparison or is it outside the comparison I think it I might check the test again I think it's inside a comparison in fact I'm not sure how Ben man handles the synthesized functions like how it is implemented under the hood we do it in a very like if you want to rank one constraint system you can

think of it as a computational graph like if you order the constraints correctly you can execute them go through them as you would as you as you would go through a graph and just with the user input you can instantiate all the variables so enact this part is really cheap it's straightforward actually so it might be one of our advantages against Perelman enough it's not paralyzed all right because you have to do it sequentially actually you in fact you cannot pilot but it's it's really cheap in fact you just have to go through all the rank one constraint and you start to evaluate them to solve the

variables it just consists of solving just a normal equation with one variable which is really cheap also for the Y we beat the man I think the main reason is come from guff actually so you can you can check we have a technical blog post explaining Gulf implementation it turns out that in the curves that we use so we use BLS hundred seventy seven so you might be familiar with this curve from CXC we use BLS to endure the h-1 of course was the cash curve and yen two hundred fifty fifty six and those curves are defined on a finite field that have the property

that the highest the highest 64-bits chunk of the modulus it's not completely set and it turns out that you can simplify the state-of-the-art modular multiplication with that you are probably familiar with the montgomery multiplication so it turns out that with those special modules you can skip a a part of this loop that end up with like fourteen to fifteen percent improvement over the state-of-the-art algorithm and actually those modular multiplications it's actually the bottleneck of all those your knowledge engine it is called

billions of time it's one of the main reason also for the benchmarks so for the small circuits it my simply comes from the go Houghton Java very lightweight and cheap with joy versus in in Belmont they probably well they are using thread I guess massage trading and it's the cost of deploying those soft right let the overhead maybe for our advantages because we use go change and maybe with many cause it's a it helps not being being really fast but for but the main advantage comes from God so I have many questions to have so with

hash functions have you implemented and tested on this implementation of snarks yeah so currently the on the STD folder that I mentioned before we have a bunch of gadgets implementation we implemented the Mimzy functions like we didn't bother implementing sha-256 we know now that it's not stuck it's not knock friendly and there's a lot of research going on on how to find snack friendly hash functions so you don't no no not yet that plans to implement all the different hashing functions yeah according to demand will definitely add more gadgets specifically is those that are snack friendly it's very not costly

to deploy and to instrument so we like to implement those in the future you can according to demand and blast since it is a like go pure go implementation have you tried to build it course compile it for mobile devices like a smartphone or have you tried to build it as webassembly something like that it it should be possible right yeah it should be possible yes again it's one of the venues of what we can do later but we didn't look at that yes but again according to demand we might look at those areas more in depth ok thank you

thank you all for coming [Applause] okay so we're taking a small break until 1255 you can grab some lunch I think downstairs and we'll be back