Supersonic: Transparent SNARKs from DARK Compilers by Benedikt Bunz (Devcon5)

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