Introduction to SNARKs

[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]