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