[Music]
so this talk is supposed to be an
introduction to Zika snarks I will start
with a general problem setting then
trying to explain what Syrian knowledge
is and then give a quick walkthrough of
CK snarks so seekers narcs are important
especially for block chains in in two
aspects the first aspect is that block
chains scale much better if they only do
if they only verify a computation
instead of actually doing the
computation so we'll see later what that
actually means and the great thing about
CK snarks is that they the verification
is magnitudes faster than the actual
computation of CK snarks the downside
again is that sick is not stem-cell
themselves add an overhead but we'll
hope that this balance is also that they
can actually be a scaling solution in
the future then the second aspect is
that in block chains everything is
public all you send to a block chain is
readable by the whole world and Sikhi
snarks help there because they add a
property that is called zero knowledge
okay let's start explaining what zero
knowledge is or more importantly so zero
knowledge is a aspect of that or a
notion that was defined in the area of
interactive protocols and in an
interactive protocol you always have so
we have two parties approver and the
verifier and the proof of wants to
so I so this is a quite small room and I
think it's very important to get a very
high quality recording of these talk so
please don't do this stuff with the
lights sorry for the technical so we
aren't fixing just one moment please
okay in protocol you always have two
parties the prover and the verify and
the prover wants to convince the
verifier about a certain effect and it
has this protocol has the property of
zero knowledge if the proof can convince
the prior verify that the fact is true
but without verifying any detail about
why it is true this sounds really weird
and examples of such statements are that
a given message is a valid transact on
the blockchain or more abstractly there
is a W such that a f of X comma W is why
for a fixed function f but let's take a
more specific example and so one would
be a mini Sudoku board is solvable so
what is mini Sudoku you probably know
the regular nine times nine pseudo ku
and to fit it into the presentation I
will I will talk about a smaller version
a four times four Sudoku but which is
the same thing in the end so you have a
board with four times four cells and
some of these cells are pre filled with
numbers between one and four but not all
of them and the task is to fill all the
remaining cells in a way such that in
each row there is exactly so that one of
the numbers between one and four appears
exactly once in each row it appears
exactly once in each column and it
appears exactly
in each of the two times two in each of
the four or two times two sub squares
and so of course the regular Sudoku
games it's always clear that it's
solvable the question is how
but in this setting we want to so that
the prover wants to convince the
verifier that the board is solvable
without telling anything about how the
so the the solution looks like and in
the general setting you would also
consider boards which are not solvable
and then of course the prove it cannot
convince the verify that it's not
solvable so this only works in the
positive case and it's important to note
that the protocol we will see next the
size of the past is irrelevant for the
protocol it works for nine times nine or
four 1000 times 1000 boards and the only
things we need are a table a sheet of
paper and a pen and then an opaque
sticky tape and a dice okay and so it
starts so of course the prover has the
secret solution to the puzzle it looks
like that and what the the first step
what the prove it does is she shovels
shuffles the numbers so uses the dice to
create a replacement of the number two
she doesn't she doesn't move the numbers
on the board but she replaces each
number by a different one so each one is
replaced by a 3 h2 is provided by for
each 3 PI by a 2 and each four by one
and this is how the shuffled solution
looks like now and I also added the
replacement here and because of the
specific properties of the pseudocode
problem the shuffle solution is still a
solution so you still have each of the
numbers exactly once in each row exactly
one once it's called each column and
exactly once in each sub square but it
doesn't it doesn't necessarily fit
anymore to this initial setting of the
prefilled cells now the next thing that
happens is that the the prove of writes
the shuffle puzzle on a piece of paper
and covers each cell individually with
piece of sticky tape and then the
proverb puts the the paper on the table
for the sole heir for the verifier to
see and now it's the verifier stern okay
that's that's how it looks like now
everything is covered so all the both
the the cells and the replacement is
covered with tape now the verifier has
the following choices she can either ask
the prover to reveal a certain row
reveal a certain column reveal a certain
sub square or reveal the initially
filled cells from the initial setting
and the shuffling so let's assume she
chooses to see the initially fuel cells
then the prover will just peel off the
sticky tape from the from the cells from
the initial solution and from the
substitution from the shuffling and the
verifier will check that this matches
the initially given problem setting so
she looks at the at the problem setting
here on the right for example the and in
the top row there's a three she looks at
the replacement and the shuffling sees
that she's read three is replaced by two
looks at the cell in the in the
partially covered table and see that
that there's a two so that that matches
and she does that for all the cells in
the initial problem setting okay and
what what just happened so the prover
revealed parts of the rebuild of
shuffling right doesn't that reveal any
information I mean the the shuffling is
the proved it shows that in secret but
it's not part of the solution so that's
that's totally fine and all the initial
cells I mean that's nothing to be
learned there right so no private
information was shared in this in this
turn and now the this these steps 1 to 5
are repeated multiple times and the one
very important thing here is that the
prover always has to find a completely
random shuffling in each round
if the prover uses the same shuffling
and the verify knows the fact that
information can be revealed so yes and
only if you choose a new shuffling in
each round you achieve zero knowledge so
let's do a second round we have a newly
shuffle board with a newly randomly
chosen shuffling and cover that again
put it on the table and now the verify
again has these choices she chooses to
she wants to see column two so the
approver peels off the sticky tape from
column two but it's not peel off the
sticky tape from the from the shuffling
that's very important and now what the
prove it does ever the verifier does is
she checks that each of the numbers one
to four appears exactly once in this
column because that's a property we want
to have and now you might say okay the
proof were just revealed the numbers in
the solution so some private information
was revealed but that's actually not the
fact because the this replacement was
completely random any replacement has
equal probability and each replacement
actually corresponds to a permutation of
this of this column here so every every
correct solution inside this column is
equally likely so no not a single bit of
private information was revealed here
and yeah so and if you repeat this
multiple times then the prover can up
cheat or at least it becomes less and
less likely for the prover to cheat
because the verifier doesn't check
everything she only checks a certain
part of the solution in each round but
there's always a certain probability
that she will find the error and this
the overall chance of success in
cheating of course decreases
exponentially with the number of rounds
and the the important thing that
happened here is why this works is that
the prover actually writes the numbers
on the paper
but it would tape with tape so it's
impossible to change the numbers after
the verifier has made her decision what
to see that's basically the the way we
why this protocol works okay this was
mini Sudoku and from this example want
to go to CK snarks mini Sudoku still has
lots of problems it's not really nicely
usable protocol and the first problem is
that it doesn't use it doesn't work for
generic computation it just works for
these pseudo keyboards but that's
actually not true so you can you can
take an arbitrary problem in computation
and transform that into the Sudoku
problem so this is called a reduction or
you could also just see it as if you
have a solution written in one
programming language and you take a
compiler and compile it into a machine
language this is also I mean this is
done all the time this is just these
problems just look little less than
computers but they can actually encode
all these problems you could think of so
this is a soft problem it takes a lot of
engineering work to make that efficient
that take for granted but the general
problem is solved so a but what is
actually more yeah more problematic is
that mini pseudocode takes many rounds
of kind of interaction and this is
especially problematic for a block chain
where we want to create a transaction
send it the block chain and the block
chain should verify it and then yeah be
done with it instead of having all these
rounds of interactions and especially
the verifier is a person separate from
the block chain that has to use their
own randomness and that would also not
work in the blockchain context so we
have to reduce the rounds of that
interaction and at the best reduce it to
only one and the reason why we have this
many interactions is that because a
single tiny error could be hidden in any
Cell of this Sudoku board and if there
is a single error then the whole
solution is wrong so we
have to do these many rounds to increase
the likelihood of actually finding this
this tiny error that is hidden in a
single cell but if we take a different
problem that does not have this this if
we have a take a different game that
doesn't have this this problem then okay
let me stop so we have to find a
different game that doesn't have this
problem so we have to find a a setting
where a single error is visible almost
everywhere and polynomials have this
property so if you change a polynomial
in the time in a single place then this
will usually change the full polynomial
so take a look at this polynomial here
this is the graph and now let's change
this to X to the 4 into a 1 X to the 4
and we will get this graph here and you
see it's different at almost every point
and there's of course a theorem that
says that two different polynomials of
degree up to n can coincide in at most
endpoints so and of course this that we
we take polynomials that are low degree
I mean it can still be quite high degree
but the degree is usually tiny compared
to the number of points we can evaluate
the polynomial at so and with that we
get the we get the the error probability
to a point where it's negligible okay
how do stocks now work how do they use
these polynomials we use yeah special
polynomial equations where a proven
knows a secret polynomial W such that
for all X a of x times W of x equals B
of X times G of X this is simplification
usually you have multiple polynomials
and you have to have a way to choose
selection of polynomials according to
some rules but I would like to keep it
simple here and just take a single
polynomial so W is the secret solution
that is only known to the to the prover
and the prover wants to convince the
verifier that she knows this solution oh
yeah so and what happens now is that the
verify chooses a secret evaluation point
to check that these polynomials are
equal that this polynomial equation
holds and asks the prover to evaluate
the secret polynomials and you already
see that this doesn't really work so the
verify a secret point the prover has a
secret polynomial so and they both don't
want to reveal their secrets so we have
to add another tool and this is
homomorphic encryption homomorphic
encryption yeah and then so they use for
morphing encryption some magic happens
and then the verify can check whether
the two polynomials are equal or not so
what is homomorphic encryption it allows
it allows you to perform computations on
encrypted data so you have a known
function and own program but you don't
know the inputs they are encrypted some
way you perform the computation and the
result is the encrypted version of the
of the result this does not yet work for
arbitrary computations but so there is
theoretical work that allows that but
it's not really practical yet but we
have a tool called parings which can do
it up to a certain point and this point
is arbitrary sums and a single
multiplication at the end so a of x
times W of X is a single multiplication
so it works fine until you take a closer
look and see that we actually have more
than one multiplication here because X
is taken to certain powers inside the
polynomial but this can be worked around
by taking a look at this separate for
each power of X
yeah so you encrypt X so you take X to
the K and encrypt that and then perform
the addition inside the polynomial and
the multiplication here at the end yeah
and this allows the prover to evaluate
the polynomial at a unknown or encrypted
point and thus the verifier can check
the that the polynomials are equal or
whether they are equal okay we now
reduce this whole thing to a two round
protocol they prove a claim something
the verify chooses a circuit point
prover evaluates the polynomial verifier
checks that they are equal but we would
like to reduce that even further and
here is where this thing called trusted
setup comes into play the way it works
is okay sorry I'm out of sync with the
slides if you take a look at the the
procedure here you see that we don't
really need to go from the encrypted
form to the decrypted form in the end
again we can just check equality on the
encrypted form so if the encrypted
version of x equals the encrypted
version of X then x equals x so what we
actually what we what we don't actually
need is the is the decrypted version of
X so this initial X that got encrypted
then sent to the prover and the proof
evaluates the polynomial we don't need
this initial version anymore we only
need it once to encrypt it and this is
what the what the trusted setup does and
especially if nobody knows the non
encrypted version of X at any point then
we can actually reuse the encrypted
version of X all the time we just have
to generate it once and this is exactly
what the trusted setup does we generate
an encrypted version of X in a
distributed process in a simplified way
you can think of that like so and why do
we want it to be distributed because
we want to share the responsibility
among multiple persons so we want to if
anyone publishes this decrypted version
of X then we can create fake proofs and
if we do it in a way that the encrypted
version of X is a combined version of
the the secrets of all participants then
we require all participants to publish
the secrets in order to for it to be
broken so yeah that's how the trusted
setup works yes and this is the so these
seek numbers generated by the the
participants of this setup is also
called the toxic waste because they
should not ever publish it they should
just destroy it okay do I have time for
a quick wrap-up so we have to test
except that it generates a reusable
encrypted evaluation point the prover
evaluates the polynomials at this
encrypted point using homomorphic
encryption using pairings then verify
checks that the numbers are equal in an
encrypted form this is all quite
simplified I hope the next talks will go
into depth there more and zero knowledge
oh yeah right we didn't talk about your
knowledge this is actually I mean the
the interesting point about snarks is
actually not that they allows your
knowledge it's it's that they allow this
speed up in verification and people
people find your knowledge more
interesting because it's kind of
counterintuitive but actually it's it's
a triviality to add to the protocol here
so the protocol works so most of the
work in the protocol is to allows the
speed-up and the zero knowledge just
basically comes for free and this is how
it comes for free the prover just adds a
random encrypted number to both sides of
the equation because it's all encrypted
there's no way for the prover to cheat
there and that's how you get zero
knowledge and the proof itself is eight
group elements in an
the curve the verifying iz5 pairing
checks plus some elliptic curve
arithmetic and I'm Way out of time now
so thanks for your attention
[Applause]
[Music]