DAPPCON 2019: Websnarks - Jordi Baylina (Iden3)

Transcript

good morning everybody today I'm going to talk about Weber snark what the snark if is a very specific library mainly to work with zero knowledge proof in the browser as many of you know zero knowledge proof are very important for many of the applications it keeps it gives a lot of so it seemed very important for example for a scalability I think during this conference we'll have a lot of chances to talk about that but they also make a very important role for privacy for example here are some of the applications that make a lot of sense to work to do work with zero knowledge voting applications identity

applications of course mixers private transactions some games but you know in the scalability for example we can think also for our light wallet where you can prove all the chain with a single zero knowledge that would be great for example because the wallets will not have to download anymore the full blockchain or even the headers of the blockchain they just take this zero knowledge and they come verified in a constant time milliseconds okay so how well beforehand I want to explain a little bit how a zero knowledge works I'm gonna do a very short introduction but it should be clear so mainly a zero knowledge we are start with what we call

a circuit sometimes it's a stuntman it's a deterministic program we have inputs outputs and the main mainly what we want to do is prove that we know an input because result is the output but without revealing the input in general in a normal circuit this makes no sense if I do an addition it's very easy well it makes no sense to prove that you know two numbers that the addition is four you know it's everybody knows that it's reversible but zero knowledge makes a lot of sense when silk read when they're standing that we want to prove is not reversible for example the most simple circuit that we can have is a normal hash function here is for example sha-256 so in this case we can send

somebody H far you know a result of the hash and then proof that this is not just a random number that's a number that has been generated with an R but without revealing they are so in this case we would send hf r we will send the proof and then the verifier would be convinced that the prover news are in order to generate h far so let's see a more practical circuit for example let's do a simple voting okay this is a very example as more a small example but I think it's very illustrative how it works zero knowledge for doing about thing first we need to know what's the

census who can participate in the voting so let's imagine that we have four persons each of one has his public private key and we have all the public key in a miracle tree like that so we hash the public key and then we create this Merkle tree of all that just easy simple normal normal Merkle tree so if you want to prove that specific public key exists in the miracle tree we just ignore normally we would do just a normal miracle proof you know we see it was a key that we want to prove that scene there and then the the siblings of the miracle tree until we prove that it matches with the root but what happened when we put this verification inside a zero knowledge circle this case you know

the zero knowledge the program the Steinman in this circuit would be a verification a verification secret so as an input we would put all the siblings the public key and the output would be the road in this case the inputs would be made makuu could be may be private so we could prove for example that we know a public key we know a public key that can vote of course this is very useless at this point but because we said before that the census is public but you we see that we can start having a little bit of anonymity here ok another zero knowledge proof that we can do that's also very interesting is for example generating

you know a circuit that that generates the public key so they put ism or private key they'll put is your public key so mainly what you are proving here is that you know your private key this is a normal cryptography this is it's called proof of custody or something like that but in general it's done by signing your public key when you sign your public key with your private key that means that some proof that you have your private key well we can do exactly the same with zero knowledge we can prove that we know or private gifts but what happened when we put these two circuits together in this case have a more interesting circuit here imagine that we as an input we have our private key we compute the public key which is also private you know because it's

internally in the circuit okay and then we have the hash of the siblings of the miracle tree so here this circuit we are proving not that we know a public key we are proving that we have a private key that can vote we have a private key that belongs to the tree but without revealing Who am I without revealing exactly which private key is because all this side is private so here you can see that well with this we could start voting we still have a problem people could vote twice but with this we can vote anonymously in this case so let's how we fix the thing that we

cannot vote twice well we do a little bit more of work and mainly what we do is we compute with our private key and aborting Eddie is avoiding it is a constant let's say it's just a voting for d7 okay but just a random constant everybody knows is concerned so when we hash or private key with the voting key we generate a nullifier which is public so when we are going to vote we will say we will tell this modifier okay so the product of the public so that what will prove this circuit is that of course we can vote and that the newly fire is valid and as you can see only one modifier is valid and SCIM possible to go up backwards because we cannot

reverse the hash function so the only thing that needs to do maybe the smart contra that's collecting the boats is just having a list of modifiers and if somebody tries to go with the same only fire just don't let them okay but as you can see the mullah fire is not related it's impossible to now which newly fire belongs to which private key so as you see with this simple example we can create easily a voting an anonymous voting system with using just zero knowledge Technic ok so I think this is a good example to understand a little bit from zero knowledge worked so well here we in 93 we have develop some of the tooling for

working of zero knowledge we are not the only one that they are developing these tools but you have a set because we have a set of tools that you can work with the first is circle circum is a it's a language it's a programming language and a compiler where you can generate this circuit for example generating all this gray how you generate that in norther that can be used in a zero knowledge well you need to create this this this circuit in the case of circum is a dsl language it's a circuit that's good well you'll work by small components and joining them to bigger components and bigger companies very much as if you are designing electronic circuits so you are building more complex components through

the further smaller components this is the main this is so those is very much how it works and we have a huge set of libraries that you know with hash functions with a public key private key generation with the baby job even we have a miracle 3 sparse miracle tree so you go for example two lips circum lip there there is a lot of actually code library that with many circuits a ton that can be used for doing many of those circuits another is a snark j yes knowledge a gas is an implementation of the zero knowledge of the zika snark protocol in JavaScript it's well it's not it's like the first it was like the

first the first iteration and was very good to understand the protocol it's very useful for academic users your users but quite a slow it's right in JavaScript and JavaScript you can imagine it's not the best language for writing cryptography but works it's like writing in Python okay and then once we want to go more production and we want to use this in a real environment then we start creating creating with the web snark which is the what we are talking here Wepa snarks web starts mainly is a implementation done in off of this protocol in web personally well possibly as you know it what possibly is a build

a beautiful machine so it's a it's a it's a virtual machine that's running in the in the browser it has their own op codes okay in the normal way to writing programs with web assembly is using normal high-level languages like c or like go or like rust but the problem of doing this is that very slow especially when you are working with these low-level primitives now doing multiplications montgomery multiplications modular multiplications modular additions or this low-level with big numbers it works quite slow so the strategy here in order to go fast is to just try to write by hand the web personally the opcode

directly ask you if we write in it nasa me what assembly I tell you beforehand has some limitations first of all is that for example you can only do multiplications of on 32 bits of course you can do it well you can do it in 30 in 64 bits but you don't have the high part the high side and the low side you only have the long side so actually if you want to do a full multiplication you can only do in 32 bits this gives just by start a reduction of four times compared with a host so well possibly at the current version of a possibly it's going to be at least four times slower just because of that this is this is going to be fixed there is a

new version of 64 bits were personally and in the new versions will be fixed the other limitation that we have is that we don't have in web possum you don't have multi-thread right now's the risk well actually Google has like an extension so in the Chrome you can actually run web personally in parallel but it's disabled for security reasons at this point and not fully standard yet but it will come in I hope that in short it will can do you know what we are doing is we are using web web workers and the other thing of course we don't have any user specific machinery for

example in terms of these parallel parallel multiplications and some specific op codes that have some specific processors we can of course we cannot use all these this these specific parts of the processor so how it works so more or less what we have been doing is gonna show some code here so what we have been doing here is mainly using javascript as a macro language people that's odd maybe remember something that was called a macro assembler this is quite similar that's writing in JavaScript so mainly what we are doing is a JavaScript code that generates a

code that generates a web assembly so we are not really writing web assembly by hand but we are using the we are using web possibly to generate the code so we can generate a code that's exactly the code that we want for example we can generate an addition that's absolutely unroll it so we have exactly the instructions the perfect instructions that are the most optimal possible in order to generate this edition or the multiplication or a montgomery multiplication or any other primitives that we have so here we have a tool that's called wasum builder that mainly what it does it helps to do that so you can start you

know concatenating and maybe you are putting that in the loop so the costs are generated at you can generate that we can do you can do it at run time you can generate it before and then generate the Watson file and then create in there so we have all the of this library and all these machines as for example that generates a multiplication but as a parameter in the compile you say for example how much big should be the big numbers maybe 256 bits or 700 bits or whatever and it generates a code that's optimized for that size speed for that bit size so this is very optimal and I would say that's well maybe it's beatable because compilers in general used to get better but right now

we will see later that we are getting in EE faster than any other compiler is doing so let's continue the presentation okay so what in order to compute the proof what operations are inside the start so what are the primitives so actually what we are doing okay for computing a proof in zero knowledge mainly there are two things one is what's called a multi exponentiation what exponentiation is you just have different points in elliptic curve points different scholars the lowercase

parts and then you are doing this operation it's a scour times a point plus a scalar times the point process color times a point and you do that many times this is the what we call it's a smooth our multics initiation as you can see this is a very parallel visible function you can put inside paralyze that as much as you want it's very ok and the other part that I put that right now with a small circle which is not the bottleneck but when you go maybe with a bigger circuits is is it's going to be the bottleneck base because the first one is Owen the second part which is the FFT is n log n so this lock and at some point will crush the

lines and it will be more more less less less less efficient so we have this mainly these - dual functions so if we go to graph what we are doing is three multiplications in g1 which is a corp normal but we do understand as normal Corp one multix pronunciation in g2 g2 is also a corp it's very all the same that's an extension field that means it's like for example we are working with a complex number so the numbers instead of having just one number we have the real part and the imaginary part so for example multiplication is not as normal multiplication but you have to do two multiplications plus one addition and other so it's it's more costly in general then we have an fft

and the result of fft we need to do again a multi exponentiation in g2 of fft so this is very much and you can the number of the biggest the big it this is very proportional to the complexity of the of the circuit okay so this is very much what in growth 16 we need to do for computing that okay and here are some of the some of the results that we got of course this is relative numbers this is no random computer a Thank You adrià if it's here for doing all these numbers here the important part of this this works yeah so here the important part is you compare the weapon arc number

compared for example with the bellman so this is Russ compiler so this is you can see here the difference between one another running in one single thread here of course when you go to four cores then you divide that by four very much if you compare to normal host you see that more or less is four times it's around around four times less this is because the 32 multiplications but you can see that for example for a 50,000 constraints which is with this number for example you can create a easily a voting system for you know for maybe for millions persons so a circuit that looks like that would be around please this number of constraints so you can these

are the numbers that we are getting so six seconds well waiting as person for example for voting or for generating some kind of proof these seconds this is something that starts being doable okay if you go to 2150 34 seconds this is much worse and when you go to mobile phone and you need to more or less multiply that but at least by three depending on the mobile phone okay the other thing I want to mention is that whether snarks is not only it's not only for for generating the proofs it also actually it can also verify the proofs right now we are working with where we have it it's implemented into

curves in BN 128 and the MNT is six seven five three here are the most used course in the space for zero knowledge the first one BN 128 is the one that works in the theorem is the original that the G cash protocol used right now is not considered very secure it's around I think it's something like around 100 bits only so it's not the most advised Corp to work with it's it's still safe what's in in that limit okay actually the cache just moved in the sapling version just moved to the to the second curve to be less 1281 that has it worse with fields of 381 bits and it's

more safe it's considered more safe okay then we have an m NT 6 7 5 3 element e 4 7 5 3 this is a very very interesting curve because this with this curve you can create recursive snarks with recursive and snarks you can start well you can handle a lot of things for example for a scalability you can create a proof that proves another proof you can create for example three of proofs for for example and delegate the the degeneration of the proof to many servers you can generate for a grade for example a chain of proof so kind of pro team but with proofs or prove that it's approved and that in a way that because it's recursively just verifying the last

block means that you verify the full block chain without we know with without having to to have all the all the all the blockchain beforehand so that's that's an important one and cockpits is well this is using six and this is just a recursive it's our it's recursive at just one level okay in some applications with a single level of recursion is enough and the theories were reducing here here are of course there are more but this is are the most the most common and the most usual ones and here in you see in the right the time the times that are that we are getting in the that we're getting in the browser more or less to in order to verify that BN 128

is around 30 milliseconds and the M&P is six seven five three we'd work with several hundred bits it's a important curve the verification time is only 100 125 milliseconds that's quite good there I want to show a little demo how this would work it's very difficult to show a demo of that working because it's just here isn't here is in the VN the BN 128 so through the verification these are 50 thousand 50 thousand proofs and you can

see it that it takes less than five seconds and here is a proof and actually we can verify that so if we verify that it's what it says is good but it takes just 22 milliseconds in this case so this is quite quite quite fast if you go to the MMT 557 here is well this is the gonna run this this will take a little while because now here it generates a proof this is take it from the from the coda protocol have a they had a standard you know reference implementation it was writen in in in well in some languages that it's very very very slow and here

are the timings that we are getting so the original the original implement datian it tooks like 12 seconds to compute that the reference implementation that we had and this implementation it takes less than around 100 milliseconds so if we run here for example we can see that business we are generating here validating the proofs in this M&T in this recursive in this recursive as an art course so this is mainly the this is mainly the demo of what the web library works just to go backwards and show something that I think it's important that's here here is

okay we have the in the example that we had before we had the the circuit in this case would be the my circuit my circuit we will use theorem in order to generate in order to generate the compiled adverse you know theorem the circum generates mainly two things but the constraint system it's called my cercano JSON and it generates also a code that computer view in a witness computer witness means that executes the circuit so you would put the siblings in the case of the example it would put power the private key and it will generate all the intermediary signals and the output so it actually tributes the signal so with this we can this is we will need this witness suggestion we

will need it this is the lot of other values of all the signals that that does that the silk we generates okay so once we have the circuit here we have the setup this is probably the worst thing of the of the Seekers larks technology that we need this trusted setup this is in general is done with a multi-party computation this is something that we need to do only once per circuit but we need to do for every circuit with at least with this technology there are some papers that they can improve that and they have universal setups and it should be possible not to run it in every circuit but at the current the current in this version and in the blood right now we have to do this trusted

setup and then this trust syrup generates mainly to kiss the proving key and the verification key the proving key is what the prover does that maybe the prover what it takes it takes is proving key it takes a window so it takes the execution of that circuit so the circuit that's executed so this instance of the execution of the circuit and generates the proof and the verifier takes the verification key generated from the setup phase it takes a public it takes a public key and generates a verification and with this you become verify and save this if this proof is valid as well it does not this is an important piece you see how it works all together yeah and that's my me that's mine that's mine eat I don't know

if you have some questions about that [Applause] hi um does web snack support a multi-party trusted set up at the moment or does the does the the snark J's library support a distributed trusted set up at the moment this web store is right now hiren well it's good because this is a what I want to talk in the future this is very much in that so the idea is right now it only

generated web snark it's only the proving and the verification part but we will implement the setup part so that's this multi-party computation will be implemented in in web snark so in this way we can obsolete snarky yes we will keep it for we will keep it for academic purposes because I think it's a good code to learn how web snarks hold hope snark technology works we're also another improvement but I now the code to generate the the witness in circle it's a well it's an nasty JavaScript it's JavaScript that works but we are going to change and replace that so it generates webassembly so and then the other thing that we are going

to do is circum that's like the first version we are planning to generate a version 1.0 that's more production ready that can be audited and that can be well some with having a very good specification taking all the learnings that we have we had during this year for many people writing goals in the circum and trying to set up like what would be a 1.0 version of the circle that's very much the the planning is that we are running it that we want to run in them in the next month hi is the demo available on github a demo yeah everything is open source everything is in github you can go to identify repository you can

download there you can play there we have also a telegram group 5 and 3 you can if you are using that you can connect there we will answer any questions you have on that so but this is a this is a tooling that's absolutely open and we write that so where we write that because we need it in 9 and 3 but we write that also because I we believe that many other applications in the space will need it so yeah absolutely so it's open source free software so sorry any more questions about that's it thank you very much you