# Optimizing Cryptographic Algorithms used in Gnark

- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2023-10-09
- Duration: 16:24
- Topics: blockchain, smart contracts, distributed ledger, ethereum, Science & Technology
- Watch: https://streameth.org/watch/yt-jL0vRNBBFns
- YouTube: https://www.youtube.com/watch?v=jL0vRNBBFns

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on IPFS and more.
https://archive.devcon.org/archive/watch/6/optimizing-cryptographic-algorithms-used-in-gnark/index

.

Speaker(s): Youssef El Housni
Skill level: Beginner
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: zk

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

foreign [Music] actually I'm gonna talk about some of the algorithmic optimizations we have in Canal that makes it fast so we are a team of five so far and we are building two libraries in go so one is called gunak which is a easy to use open source library for snacks and the other one is Gnar crypto which is a cryptographic library in Glo so uh Glock under the hood is basically composed of these components so you have a front end when you write your circuit a back end for per generation for verification and then underneath you have this you can architecture Library which is bearing based cryptography on the elliptic curve-based cryptography and uh finite field uh arithmetic Library so we have all the stock written in go no dependencies so in the back end we have so far got 16 and Planck with two polynomial commitments so kcg and Phi we have in the front side a standard library with the mimc ecdsa eddsa banks in circuit builders in circuits and we have both apis for not a native field and non-native field arithmetric and in Glock rate so we have a bunch of ellipticals ba and BLS 12 BLS 24 Two Chains with BNS 12 or 24 Twisted Watts we have fast multi-scanner multiplication fast pairing kcg 5 pillow caps and we have already recently implemented some check protocol gkl and in the finite field arithmetic we have different sizes ranging from 768 to 256 to cold Deluxe as well and it performs very very well on different targets so the usual workflow of snacks so same in Glock so we have a circuit that we write in Blingo so it's not in a DSL and then we compile it to some constraint system and then you call setup move and verify API so it is fairly easy to change the elliptical you want to use and the constraint system you want so you just change for example here BN 254 by bns12 and l1cs which is class 16 by SCS which stands for sparse gastrated and which is blocked uh so we have a playground uh where you can play with it in the browser we go 16 and Planck to see how you can write your circuits in go um and then you can download the constraints and look like look at what they look like both in row 16 and snack um so why Glock so we have no DSL plain go so no dependencies at all we compile large sockets in a few seconds so when you write your circuits in playing go you can use go to Links stand out go to links to the back test Benchmark your circuit but also we've developed a cool cool thing which we call constraints profiler so by just adding two lines of code you can have this key this this video here where you see in each function how many constraints does it consume um yeah and the several packages are already audited by algon and fastest bike get for one year I guess now and there is one code base that performs well in different architectures CPU mobile wasn't so in the mobile we have 70 faster than the Baseline in the Z price um so the question is why Clark is that fast so here I give an example of course 16 snack over on bn254 okay so this means msm's computations fft computations and parallelism so I took the examples of two of the most used libraries so Arc Works in our stands silicon with a rapid snark back and then C plus plus so two kind of uh circuit sizes so one is 65k the other one is 8 million constraints so this is a AWS AMD machine and we see that gnat performs very well for both kind of circuits so there are some libraries that are heavy optimized or large circuits for instance Glock is optimized for most so this is for the previous site for the verify your site which is Ghost 16 snack verifier so which is mainly pairing computation of lbn 254. so again we see that on same machine um Glock is very fast so it's uh a bit more than one milliseconds on this machine to verify to computer to verifiable which is mainly a multi-explanator appearing computation um yeah so it's a PDF it was interactive but anyway so the question is why gnarok is that fast so remember this diagram from the very beginning so we have a front-end backend I'm gonna click tool underneath and the question is so I will go through some of the algorithms that are highly optimized in knock so we start by writing a circuit see we generate the proof Pi of C which means that we will call ganache2 to compute ffts and mostly msms over so yeah so I'm giving the example of a cursive course 60 Improvement just to concentrate over the algorithmic optimizations I'm using a 2J so there is no long field arithmetic but it works also with long field arithmetic so it has an amazing 377 and then we write a circuit C Prime of the both pi we generate the poof Pi Prime of this circuit C Prime so the aggregation which means that we will call a galactic to compute a multi-scalar multiplication over the bw6761 curve which is the outside curve and um we verify the proof step five which means that we will calculate to compute the pain so I will be talking about the optimizations in those points that are in that are in boxes so mainly msms and pairings and writing circuits um so images of a BNS 12 377 so I this is a graph from the Z price uh submission uh some comparing to Arc works because it implements VLS work 377 so we are 40 up to 47 faster for 100 points surrounding from two to the eight to two to the 18. so this is tested on mobile so on a Samsung Galaxy and we have two so here I have two versions of Glock one using Twisted Advanced curves and the other one is using shop twice curve so the one is 40 to 47 and the other one is 20 to 35 faster and the question is why so um so both implementations do not use by computations but use parallelisms but in a different way I'm not going to talk about this so we use two enough buckets which reduces the size of the buckets by twice this is not using networks but most importantly here is the curve form and the coordinate system so we proved that any inner curve can be written in a Twisted Edwards curve with a equal to -1 and we extended a coordinate system so so we call it custom xyt in order to make computations faster so why is that so um so I call a b bit MSM is an MSM of size n with scalars of B bit so generally so all the libraries implement this variant of piplanger which is bucket list method so it goes in three steps so it uses the B bit MSM into CBS MSN for some success for some fixed C we solve each C bit MSM efficiently and then we combine the C bits MSM into the final bibet MSM so the overall cost is this one so -1 is in blue is when you use this uh in enough encoding of the scholars otherwise so you have two to the scene but this overall cost can be uh explicitly broken into what I call mixed additions additions and additions and doublings so um so for large msms so what sees most important is the mixed the additions because they scale with the number of points and the others are constants so if you look at all the shapes of the elliptic curves and all the coordinate systems that are over there so you can look at efd webpage so Twisted Edwards with a equal to minus one with extended coordinate system have seven multiplication for dedicated addition uh compared to for example 11 in artworks with Jacobian coordinates um so what we did is basically when I say addition is so those points are re-added in the package so they are the same so when you look at this unified addition so which means that we will not have any band any F else branches to to handle exception case so it is one multiplication plus but the multiplication is a multiplication by a constant which is 2 to the D so we come up with a custom coordinate system which is instead of having the Tuple X and Y you have y minus X Y plus X and 2 times D times x times y so you can do unified additions without branching at the same cost of the the dedicated addition to seven multiplication yeah and this is basically one of the the optimizations that makes MSM faster in crack this inbox was right in the circuit C Prime of the verification of Pi so in the previous presentations we've talked about parent check inside a circuit and how much it is expensive right so there is a long line of research of pairing computation outside of the circuit and we can do computations of BLS appearing of BLS 12377 outside of circuit in less than one millisecond but if you put mutations those optimizations inside of a circuit the number of constraints is roughly 80 000 in LS so we were able to reduce it to eight so 11.5 constraints so there are a few implementations so far so there is one in our quarks one in lips knocks and I believe one a new one in the ZK Peg by zero EXP in Arc Works which was the state of the art for this computation it was 19 000 constraints but we were able to reduce it to 11.5 so the the paper is here uh you can check it uh but the main ideas are basically um so the inverse is not costly and I almost here so you can do double and add in a fine so not double and double and uh we have a different representation of the line so that we have sparse multiplications by the line in our CS wise we use Choice based arithmetic inside of the circuit so it uses inverses that's why it wasn't used outside of the circuit but inside of the circuits it makes sense and the finance pronunciation is also using calabino SQL Atomic squaring instead instead of conjure Scots which is not used outside of the circuit and for both the media Loop and the final exponentiation we use short addition chains but the trick here is that normally in a short addition chain of Dublin ad you would like to have to optimize the the the doublings because doublings are faster than additions but constraints wise it's the opposite are doubling costs more constraint annulation because the line slope is has a square so it scores two constraints instead of one just switched division so the idea is cross section is only in 19 K constraint bearded signature is 14.8 constraint case constraint and kcg verifier is just uh 20 000 constraints um the last box so pairings over bw6761 um so we can compute this on a inside machine here in 1.22 milliseconds compared to 1.76 71 milliseconds and the question is why so actually we do not implement the same formula so um appearing is so of p and Q is this m of p and Q which is what we call the middle Loop so it is a loop and a final exponentiation which is the exponentiation by Q to this x minus 1 out of R so the optimization comes from the middle Loop so the original paper of bw6761 has this formula for computing the plane which is f of U plus plus one and F of u q minus uh Square minus U so which are two Miller Loops of size U plus one and uq minus U Square minus U so when you see those uh so they have bit size 64 and 190 and they humming weight in two and a half is 7 and 31. so what we did in gnoc is that we observed that U minus 1 square the Hamming weights of it in two half is just 12 compared to 31 and we already arranged the equation so that we uh have this second equation and basically you have two Miller Loops still but the second middle Loop uh this one is using the results of this one and it's not starting at one as as in these two and this is just a line computation and this point is already computed in this middle Loop so you have really just two Miller Loops as in here but with uh size with the loop size way smaller uh the X pronunciation by by Q are are cheap because these are just four videos so we have also a paper about this it is only punch you can check it out and we have a hack MD here blog where it explains uh the changes between these two and other algorithms because this one is just for one pairing and for multi-pairings we have other algorithms so a novel algorithm that we call Twisted States it was because in this kind of ellipticals bw6 G1 and G2 are on the same field so you can use State instead of eight and you can use the endomorphism then for multipacks it was way faster than than what we had previously so um this is just a couple of optimizations that I talked about in in Glock so it is really optimized in all the stack um if you have any questions with face to contact us on by email or on Twitter there are some useful links here and I'm happy to take any questions thank you [Applause] any questions hi good talk thank you I want to know why did you choose go instead of rust for example uh good question so um this work was started before I joined sectors already didn't go but uh yeah so um um so we think that goes still are so fast but also because there are many libraries and projects out over there that are using last and there are many blockchains that are using go so it was nice to have the snack Library written in Ingo so that we can have native uh integration with them you mentioned you guys had support for lookups and garc is that already released or yeah so it is but we do not have plonk with P Lucas we have we have just the pill lookup argument in Calcutta that will be used for the zika evm uh sorry I guess so you're saying you can use plookup but how to use it without the Planck integration so we do not have the integration so far but we have just the pillowcup arguments okay got it