thanks for coming so I'm going to talk
about transparent snacks from dark
compiler tips today and this is joint
work with Alan Japan Jack and Ben fish
and the the main problem that zero
knowledge proof solvers is something
that you can see here in a Bitcoin
transaction and the same holds for
aetherium transactions it's that if I
want to check the validity of a Bitcoin
transactions then I need to know the you
know the check it for a bit content
section is that the sum of the inputs is
greater or equal than the sum of the
outputs and to do this check to check
that the transaction as well as I need
to know these amounts right I need to
know how much money is being sent and
very similar in etherium I need to check
that the person who's sending some money
has enough balance in the account to
send the money the the difference is
actually the fee see a bit but the
problem is that this is actually really
bad for privacy and the the the because
everything is public so what this means
is if I get my salary in Bitcoin for
example in etherium then my salary will
be public on the blockchain and
everybody can see it and that's not
something that I want to have so for
example also if I'm a supplier then you
know if I buy some some if I'm a company
right and I buy some supplies for my
company then all of my competitors will
exactly see how much I'm paying for
these suppliers and that's a important
business secret and you know this this
really leads to this maybe slightly
controversial statement but that Bitcoin
in the way that works now it's really
unusable for businesses and in a similar
way for aetherium you know if I run
maybe some some investment fund on me
theorem right then then everybody can
see exactly what my investing strategy
is right now my whole billion secret is
the whole secret sauce is my investment
strategy but if this fund is on e
theorem then everybody can exactly see
if it's a melon or something then
everybody can exactly see what I'm
investing in they confront money you
know that creates all sort of prominent
and this really means that a theorem is
a new
suitable for for many financial services
well luckily we sort of know how to
solve this problems and that is by using
cryptography and especially something
called zero knowledge and there the idea
is that instead of having you know a
Bitcoin transaction that looks like this
I'm going to hide all of the amounts so
I'm going to use something called a
cryptographic commitment to hide all of
these amounts so no one can can see what
these amounts are they're they're
basically encrypted and the question
though is then how do I check that the
transaction is valid how do I check that
you know the the sum of inputs is equal
to the sum of outputs past apiece and
similarly in a theorem how do I check
that the sender has enough money in
their account to sent the transaction
and the way to do that is using
something called a zero knowledge proof
and this is really a magical
cryptographic tool where Peggy can
convince Victor so the prover can
convince a verify that something is true
without giving up any information about
why it's true so for example I can
convince you that you know I'm
committing to a positive number right
like the remaining balance that I have
is positive but I reveal no other
information and especially I don't
reveal what my balances right all of
that remains private and the way that
this works is basically you know one way
to imagine it is through sort of this
interactive challenge response protocol
where Victor gets to ask questions that
Peggy wouldn't know the answer to
if this wasn't true right she could not
answer these questions if the statement
wasn't true of the transit if the
balance was negative but the answers
don't reveal any information whatsoever
about what what the statement is so what
we really need though in a blockchain
setting is not this this sort of
interactive proof we and in the end the
victor has no idea what X is but it's
positive and Pena's know it and
what we really need in this interactive
setting is a music and non interactive
zero knowledge proof of knowledge where
basically the prover can just write down
the proof and the verify can read it and
check it and everybody can read it and
check it it's publicly verifiable and
this relies on some common reference
string that both the prover and the
verify have access to and there's many
different kinds of zero knowledge proves
there's maybe you've heard of snarks you
have heard of stark sort of bullet
proofs and then there's also a bunch of
others right you know there's a
tremendous development happening in this
space and I'm gonna like vastly
oversimplified who it's been wrong the
the orange ones should be green the
orange ones are good so the vast
oversimplification is that you know like
looking just it's snark Starks and Bowa
proves is that snarks and bulla proves
they're good on the proof size starts
not so much the verification is great
for snarks and Starks and you know
Starks are great now but unfortunately
they have this thing called trusted
setup where you know someone needs to
perform a trust set up I'll talk about
the trusted setup and why this is a
problem in a second but basically
there's this party who creates a proving
key and a verification key and if that
party cheats then really bad things are
going to happen and you know maybe a
little bit more and more in-depth
comparison that I don't want you to read
but you know this is a recent comparison
and basically there's no snark without
trusted set-up that doesn't have our no
proof system without trust and set up
that has logarithmic crew size or and
logarithmic verification time and this
is exactly what I'm going to present
today the first practical snark with
logarithmic proof size and logarithmic
verification time so Snorks have this
trusted set up so what is the trusted
set up it means that there's some party
you know some really nice guy who
creates a proving key and a verification
key and the prover uses the proving key
to create the proof and the verify uses
the verification key to check the proof
but if that party colludes with the
prover if that party cheats
then it can break math then it can say
that three plus three is equal to four
or seven or whatever and why is this a
problem well if the trusted setup is
averted the prover can create fake
proofs and what this means is if we have
subversion then I can create money out
of thin air I can have you know one Z
cash coin and create a million out of
them because I can break math and that's
really problematic because you know
suddenly we have undetectable inflation
the privacy still holds it's really
really bad you can alleviate that
through a distributed set up which is
what Z cash did and they did a really
good job with it and those are like the
smartest and the absolute words ackward
expert in in in in snarks and they still
messed it up right there were the the
setup was broken they luckily caught it
before something bad happened or at
least we think so we don't know and but
you know this set up was broken so it's
really difficult to get this right and
one other thing that is really annoying
is for the most efficient snarks you
every time you have a new functionality
you need a new setup so for example if i
want to have one snort per my contract
and i need to have a new set of every
time and every time that setup can be
broken so this is quite quite
problematic so really the goal is to
remove this need for a trusted set up
and bulletproof for example does that
but bulla proves works for small and
medium complexity transactions but for
large complexity transactions it just
takes too long to verify it doesn't have
the succinctness property where proofs
are very efficient to verify even if
they're very complex and snarks have
that so this is why we build dart proofs
and supersonic so how does that work
well the main thing that we build is a
new polynomial commitment so what is
this so this is a cryptographic tool
where the prove it has some polynomial
so you know 3 plus 2x plus 5 x squared
and so on
of degree D so it has D plus 1 terms and
the prover senses commitment which is a
small value even though the polynomial
is large the very
I can send the point Z and then the
prover can tell you the polynomial
evaluated at Z is equal to Y and give a
small proof that this is true so this is
a polynomial commitment and recently
there was this cool new proof system
called Sonic which is a new kind of
snark by I dropped the reference there
but Mary Muller and and Shambo and
others and and it's it's a snark system
that uses a polynomial commitment scheme
and it has a trusted set up still but
this trusted set up is only for the
polynomial commitments game so nothing
else requires a trusted set and it's
also it already is universal so it
already removes this problem that you
need a new trusted set upper circuit so
it already is great and it got even
improved you know the constants got
improved by by new proof systems called
Plunket Marlin but they're you know all
the same family of proofs and what we do
is we build a new polynomial commitment
scheme which uses so-called do fifteen
arguments of knowledge so integers
integer equations and that's why we call
it a dark and it uses these so-called
class groups and it has logarithmic
communication time and logarithmic
verification trend and most importantly
it doesn't have a trusted cetera so what
does this give us well the the
we have sonic right and now then we plug
in this new dark proofs and then we get
this sort of messed up but we get it
happened here I'm gonna fix this
these for this night we're gonna get
supersonic which you know is the first
snark with short proves in no chess it
set up the proof says is about is less
than 10 kilobytes verification time is
less than 100 milliwatts milliseconds so
it's very nice so how do we build this
well we built this something you know
now it gets now we're getting into so
the technical part trying to understand
how this actually works so we're
building this using something called a
polynomial IOP so what is a polynomial
eiope well basically think of it as if
the prover and the verifier have access
to some polynomial may be in multiple
variables in the sky and then in every
round to prove your sense maybe a new
polynomial the verify sense challenged
and you get some new polynomials and so
on so there's some interaction where the
prover and the verifier you know send
you some polynomials and then you sent
the the verifier sense is some
challenges and these polynomials may be
large but what we can then do if we have
a proof system like this and sonic is a
proof system like this then we can use a
polynomial commitment scheme to not send
the polynomials but just sent the
commitments to the polynomials and it
turns out you know this is interactive
there's a generic transformation called
the Fourier transform to transform this
from an interactive proof to a non
interactive proof so basically all we
need now is is this thing and then we
can focus on you know kind of compiling
these things down so this is the this
general recipe of how we can build these
snacks and a lot of different snarks
actually fall into this category of
polynomial I hope ease so if we build a
new polynomial a commitment scheme it
helps improve all of these snarks and
make them or all of these proof systems
and make them have no trusted set up so
that's exactly what we did and sonic
you know as I already said gives you a
five-round IP with 24 Oracle's but in
general you know we can we can make this
work so let's focus on the main
construction so the first thing of this
polynomial commitment scheme right so
this is why we're trying to do we've
boiled it down to we just have to build
this problem on my commitment scheme so
you know let's recall what a polynomial
looks like and so what we're going to do
is we're going to take this polynomial
and encode it as an integer so what we
do is we pick simply pick a large queue
so all of these normally these
polynomials are in a field in a prime or
a field CP but what we're going to do is
we're going to represent it over the
integers and pick a queue this is larger
than each of the coefficients and then
just simply evaluate the polynomial Q so
this might seem a little bit weird why
are we doing this what does this mean
well let's think about very concrete so
our polynomial is 4 X cubed plus 2 x
squared plus X plus 3 and then we take Q
equals to 10 and we evaluate f hat at 10
well what do we get we get 4 2 1 3 it's
literally just the coefficients written
next to each other right because 10 is a
you know where we're thinking in
decimals so with 10 it looks really nice
but you can do this with any other
number you know if I had chosen 8 or 5
or whatever this would have worked as
well okay or 100 you know so what we do
here is we transform our polynomial into
an integer so why do we do that well
this integer encoding has very nice
properties so if this Q is large enough
and there's no overflow then actually
this has homomorphic properties additive
properties so I have a you know one
polynomial 4-2-3-1 you know I just give
you the integer representation and
another one 1 4 4 3 and it turns out
that if I add these integers I get the
encoding of another polynomial which is
literally the sum of the the original
polynomials right so if I add the
polynomials and then
code it's exactly the same as if I
encode and then add the integers so this
is what we call a homomorphic property
so this is an additive homomorphism and
it turns out there's also a
multiplicative harmon orphism or
monomial homomorphism so if I want to
shift the the polynomial by a degree X
to the K you know say x squared then
this is simply equivalent to just
multiplying it with Q to the K so x
squared times H of X is 5x squared plus
6 6 to the fourth and you know this is
simply equivalent to just multiplying
hundred times the encoding right X is 10
or Q is 10 10 squared is 100 so all of
this works so now we've transformed our
polynomial to integers so why why does
this help well there's these
cryptographic tools called a group of
unknown order right these integers are
still large in my polynomials large the
integer is large so I cannot send you
the integer that would be much too like
it would be way too large but now
cryptography comes into play and we have
this thing called a group of unknown
order and all you need to know is that
basically this is a commitment to
integers which shrinks down the integer
it doesn't matter how large the integers
you know could be hundreds of millions
of digits it shrinks it down to
something that is constant size but the
homomorphic properties these additive
properties are still preserved so I can
give you a commitment to integer 3 and I
1 to 4 and then if I add these things
then I get a commitment to 7 right and
so what I can do now to commit to my
polynomials I lift it to the integers I
evaluated at Pew and then I compute G to
the F of Q so now I have a way and then
I can still do all of these additive
operations up to a certain amount so
this is the way that we commit to the
polynomial and this is the main tool
that will you that we're using and then
so what are these groups of unknown
order well you know there's there's
different ones but one that you could
use is this class groups which you know
in general cryptography is it's
important to think about abstractions so
don't go look
class groups it's not worth your time
right like just use them as a tool and
but there are a group of unknown order
and so we believe that computing the
order is hard we believe that taking
routes is hard and most importantly they
do not require a trusted set up so I can
generate this group I only need to do it
once and it doesn't have to have a
trusted set up and they're a little bit
you know compared to say elliptic curse
which by the way elliptic curves are not
an integer commitment because I do know
the order so you know if I commit to
some large integer I can reduce it mod
these so-called order of the group but
the problem is that these groups have
unknown order to be secured they need to
be quite large but that's unfortunately
something that we have to deal with so
how do we build a polynomial commitment
so let's think of this again just you
know in terms of polynomials so what I
want to do is I have a polynomial of
degree D so with deep terms so it's as
large polynomial and then we're going to
use recursion so to reuse recursion
we'll split it up into two parts the
left half and the right half so F L of X
and f of X such that F L of X plus X to
the D over 2 times f of X is equal to f
of X the proven then sense F L of X and
f of X to the verifier the verify checks
that this equation holds right checks
that f of X is equal to this using again
in the end this will use the this
homomorphisms and then the verify sends
a random challenge so this is a random
alpha and then the prover combines these
two polynomials just using the linear
combination F L plus alpha times f of X
and this gives us you know F prime of X
and importantly now after these this one
step we now have a polynomial of degree
D over 2 so we reduce something from
degree D to something to a degree over D
over 2 and then we can just repeat right
and if you do the math and you have how
often do we need to repeat well we need
to repeat log 2 of D times so say the
polynomials of degree a million we need
to repeat 22
degree a billion we need to repeat 30
times so of course we cannot send these
photo moments in the clear so what we're
going to do we really send you know
these these encoding right again we
evaluate the polynomial Q we raise it to
the power and so on and so forth but you
know it's it's important to think about
this interactive thing but I also want
to evaluate the polynomial at a point
right this doesn't you know there's no
evaluation here so what I'm going to
give you is additionally I'll give you
you know I'll claim that the polynomial
evaluated that Z mod P is equal to Y and
then basically in parallel to sending
these things I always also send you you
know if L of Z in Z P and F R of Z and Z
P and these things are constant size so
these things are small and you can
efficiently check and then again you can
efficiently you know check this equation
right so this would be yl + Z to the D
over 2 is equal to yr plus yr x yr is
equal to Y so I can check this equation
both for the polynomials and for the
evaluation very efficiently and then I
can compute my Y Prime and the last
round I compute my Y prime which is
equal to F prime of Z which is equal to
Y L plus alpha times y ax sorry maybe
that was a little bit too fast but it
turns out that basically you know I send
you these polynomials I split them in
half take a random linear combination
and then recurs and if I want to
evaluate this polynomial I also do this
on the evaluation and then in the final
step I have a polynomial which is just a
constant degree right it's just a single
element doesn't have an X term anymore
and I also have the commitment to the
polynomial and I have the proposed
evaluation so the proof which is since
then F 0 in the clear degrees 0 and the
verified checks that F 0 is a small
constant and that C is equal to G to the
F 0 and that F 0 is equal to Y right
where F
mod P is actually equal to Y but you
know that's a detail and so what this
gives us is a polynomial commitment with
two lagdi group elements in every round
to look the field elements and we can
use lots of matching tricks to make this
really efficient and you know there's
this some more tricks that you need to
apply to to make the verifier efficient
so for example you know you need to use
some tricks to make sure that that this
check here is efficient but using some
some recent work in the space of VDS we
can also do that and yeah so I am done
with the main part of the talk I think
maybe it's I can talk about some
optimizations but maybe you know there
are some questions and I think I'll just
take the questions now thank you
[Applause]
you