zkSummit - Supersonic SNARKs: Trustless with Logarithmic Verification -Ben Fisch (Stanford, Findora)

Transcript

[Music] I'm been fish I'm a PhD student at Stanford University I'm also the chief scientist of Pandora and this is joint work with Allen's Benny AK who's here in the audience and as well and Benedict once so the new result the concrete in the result can be summarized as saying we have a snark with no trusted setup that for 128-bit security is about 10 kilobytes for circuit of 1 million gates and this is a significant improvement over what we knew before at least before we wrote this paper in terms of snarks with no

trusted set up for a similar level of security and a similar number of a similar complexity would be 200 to 600 kilobytes and verification will be under 100 milliseconds take these numbers however with a grain of salt because we have not implemented this scheme yet unlike some of the other talks you heard today this is new and we'll we'll be implementing it so we can get more accurate numbers it's based on reasonable estimates though for the underlying we can count the number of operations and we can measure how we know how much the operations how much how much the operations should take so asymptotically the complexity of the snark the size of the snark as well as

the verification time scales like log n in the size of the circuit this is hiding factors constant factors that depend on the security parameter so they're not actually constant as a security parameter increases so do those parameters but the constants are comparable to the same constants that you would find on other constructions in the space that have other terms dependent on the security parameter lambda so the key new tool however is a polynomial commitment scheme using groups of unknown order and this this polynomial comments

does not require a trusted set up when we instantiate the group of unknown order using this object called a class group so if you look at a recent comparison I'm taking this out of the Liebherr paper just so that you can kind of see some numbers along the spectrum of different constructions still the most efficient constructions are those that use a trusted set of per statement those are the raw 16 snarks or lip snark and you still see that the the verifier time and the prover time and the and the proof size is just so much so much lower than with any other construction but when you move to the realm of no trusted

set up then you have things like so I'm not showing so I guess I'm not showing your universal set up so this is a little bit old it does not include I guess the Libra paper did not include comparisons for plunk and Sonic etc and I will contain I will have some other slides with numbers for that if you look at the realm of specifically no trusted set up then you have schemes which have efficient verification verification time like lips dark but very large proof sizes or you have things like Bolla proofs which have pretty small proof sizes you have five and a half kilobytes this was a computation I think involving

about 15 million gates but then an expensive verification time and bullet proof is actually lint the verification time is linear in the in the circuit so if you look at where supersonic would fit in on this table it would be about less than 10 kilobytes and I 7.1 seconds in terms of verification so I don't need to dwell on this and I think it's something that everyone in this audience is familiar with motivation for moving to a trustless setup is that trusted setups a well if they're subverted then the prover can create fake proofs and that might in an undetectable way so you

don't even know that papers are being created even the fear that fake truths are being created can cause problems and especially in the context of designing a currency so it can be alleviated through a distributed setup but that's expensive and difficult sometimes broken when you try to do it in practice and there's low flexibility especially if you have to do it once per functionality which was the motivation for universal setup which alleviates that a little bit so just to review quickly pulling the one of the key new tool that we're using is a new polynomial commitment scheme you saw in

a previous slide a more formal presentation just so you have the picture in your mind again the polynomial Kermit schemes allowed you to send the prover to send a small value that commits to the polynomial and then later a verifier can ask for the opening of the polynomial at a point and obtain a small proof that the polynomial that was committed evaluates at the point Z to some value Y and the commitment scheme can also tell you that the the committed polynomial was a bounded degree so Sonic was a snark system that was built using polynomial commitments and had a one-time trusted set up for the polynomial commitment scheme itself and the and that was improved in plunk and Marlin dark proofs offer you a

different way of doing the polynomial commitment scheme using what we call do fantine arguments of knowledge because we represent the polynomial in terms of integers and then use homomorphic integer commitments using class groups and then make arguments about integer relations in the in the exponent of the group so I'll go through the details of some of the details of the construction but the point is that we get lagdi communication in the in in the proof and lagdi verification and no trusted setup so we we call our construction supersonic because it's sonic plus dark cruise you supersonic

but really the best numbers we gather when we plug in plunk instead of sonic which was an improvement of sonic and if you plug in plunk then I this is a slightly lower level of security it uses 1200 bit class group so if you went to 128-bit security would be about 10 10 kilobytes not 7.8 so we we don't so we don't have specific estimates in the prover but I'll tell you that it's about the same number of operations that are involved in Starks but if you compare hash functions to class group operations it's about a hundred times slower right so this is the kind of recent paradigm

which the previous talks have gone over of building a taking an arithmetic circuit and turning it into this interactive proof involving polynomials and then compiling that polynomial interactive Oracle proof using polynomial into an interactive argument which is then turned into finally a non interactive proof that would be a snark using fiat Shamir so just to kind of review a bit more abstract the polynomial IOPS or what are basically equivalent to algebraic holomorphic proofs which you saw in produce talk on marlin but the idea is that basically in a polynomial IOP the prover is sending a

polynomial Oracle in a box to this is an abstraction to the verifier and then the verifier queries this Oracle and gets the evaluation of the polynomial on points and this could be made into a multi round protocol where even in the pre-processing step the prover and verifier have already established some polynomial Oracle's that can be we read at points and in every round the the verifier would would ask the prover or send the prover a random challenge and then the prover might send some more polynomials the verifier can query those polynomials at points etc etc and the if you look at then how how we how we build

this to snarks we apply a polynomial commitment scheme as a cryptographic compiler to take this abstract idea of a polynomial interactive Oracle proof and make that very concrete so every time you send a polynomial in a box you're actually sending a small commitment to a polynomial and every time the verifier is querying that polynomial in a box at points the prover is supplying it with pert with the answer and with proofs for those answers so that's how you go from a polynomial IOP to a an interactive proof with succinct communication and then applying the future mere paradigm you can transform this into a snarf so

this is the similar theorem to the one that showed in in in Marlin says that any honest verifier zero-knowledge polynomial IOP you can compile into an honest verifier zero knowledge interactive argument of knowledge using polynomial commitments so if you can summarize the key contributions in Sonic and Marlin and plunk you get different polynomial IOPS in Sonic you basically get a five-round polynomial IOP with 39 univariate Oracle queries at 12 distinct points the number of distinct points is very important for our compiler and that's another interesting point is that different polynomial commitments may perform better or worse on different

characteristics of the underlying polynomial IOP so for us minimizing the number of distinct points at the expense of having more Oracle's is actually good which is why plunk is particularly good for us because this has a three round polynomial of P where the total number of distinct query points is just two and Marlin has a different yet a different polynomial IOP and so another thing that's being hidden is each of these are compiling circuits with slight with where you measure the complexity slightly differently so sonic was multiplicative complexity Blanc was arithmetic complexity Marlin is our one CS complexity so it's important to consider as well what do you what

computation are you starting with and how is it represented so anyways if you look at how super if we apply the dark poly McDermott's game which I'll describe two different polynomial IOPS as the as the underlying information theoretic component then if we plug in Sonic we get something which is about fifteen point three kilobytes for plunk ten point one kilobytes and for Marlin twelve point three kilobytes this is estimated again for a computation with where we where we set end to be 1 million but with Sonic plunk and Marlin in Marlin this would be the R 1 CS

complexity is 1 million and Plunkett's the arithmetic complexity and with Sonic it would be the multiplicative complexity so it's light differences and if we compare how just this polynomial commitment compiler works to other polynomial commitment compilers then this just contains the asymptotics based on pairings you get the smallest proof size and verification time it's basically constant right or it depends only on the the cost of performing group operations so it's just dependent on the security parameter but that doesn't that's not without that's not

transparent it doesn't it requires a trusted set up which is why when you build snarks with it you get snarky with the universal set up if you compare dark to previous constructions of polynomial commitment without trusted setup then you see a comparison that if you look at the proof size compared to Fri which you can kind of view as a as a polynomial commitment the complexity is is log D instead of log squared D so that's why we get a size improvement over the works that use Fri to build Trent to build transparent snarks and if you compare it to what you

would get if you use bullet proofs with bullet proof you get asymptotically about the the same size in terms of the the proofs the openings of the pollen element set points but the verifier time is much much worse so the verifier time is linear in d if you set mu equals 1 it's a univariate polynomial so that would be o of d and for us it would be scaling like log t there's also things but there's also one which is in between which has a square root size argument and there you get square root size square root of d sized proof size and square root of d verification time so comparing it to other again like

monolithic constructions of snarks it's better to really compare the underlying components that I think the theme that's coming out from all these talks is that they're all of all these constructions contain similar reusable components and they can be mix and match to get different results but if you look at supersonic which is combining the IOP from plunk together with the dart compiler then this is what you get so in terms of in terms of proof size it's much bigger than what you would get with with plunk or Gras 16 but those require trusted setups and compared to bullet proof it's larger proof size but much better verification time and compared to stark

it's a comparable verification time but a significantly smaller proof size so the main construction ideas are as follows so we start with a polynomial over a finite field and we build an integer encoding of that polynomial so first represent the polynomial as an integer as a polynomial with integer coefficients where each coefficient is in the range 0 to P okay then choose an integer Q which is greater than P and output your encoding which is the evaluation of this integer polynomial F at the point Q so

we haven't done anything to reduce the size we haven't built a compressed representation of the polynomial this is not a polynomial scheme this is just an integer encoding that we'll use as a building block so giving a small example here if I had P equals 5 and this was my polynomial then if I evaluated at 10 I get 4213 so why is this an encoding well the fact 1 is just that you could take the base Q decomposition of the integer and you get back the coefficients of the polynomial so you can always write an integer in terms of a formal sum of powers of Q with the coefficients less

than Q and you can recover back those coefficients uniquely doing the base Q decomposition unfortunately that is not enough for us an artifact of the construction and proving security you require a an encoding that allows some of the coefficients to be negative so the fact 2 which is the one we actually use is that every integer in this range negative Q to the D plus 1 over 2 to Q to the D plus 1 over 2 can be uniquely decodable to an integer polynomial and if you can uniquely decode an integer polynomial then you also uniquely to code a polynomial over FP of X just by reducing the coefficients mod p and so it's uniquely decodable to to polynomial

coefficients of absolute value less than Q over 2 meaning if you started with a polynomial whose coefficients were bounded by Q over to an absolute value and you encoded it in this way then you could get back the unique thing that you started with if you started with a polynomial with larger coefficients you wouldn't necessarily get back something YOUnique so steps two is to have so observe that there are certain homomorphic properties of this encoding if we add two encoding Stu gether then we get an encoding of the some of the underlying polynomials so long as Q is sufficiently large so in order to do homomorphic operations we need q not to just be bigger than P okay because then the the coefficients when you add them

together their old de will overflow Q so they're no longer be bounded by Q but if you start say with Q which is greater than 2 times P then you can add 2 together and it's a valid encoding of the sum of the original polynomials there's also this monomial homomorphism where if you multiply the encoding F of Q by Q to the K then you get the encoding of X to the K times f of X and those are the properties that we use to build our polynomial commitment scheme so in particular if you have another way of constructing something with these properties then you might be able to also construct a different polynomial pyramid scheme that uses other assumptions so we use groups of on an

order to build this we build an integer commitment scheme using groups of n an order and notice that in a group of one or in a group you have the the map that if you have G to the X and G to the Y then you multiply them together you get G to the X plus y so we commit to the to the representation of the integer representation of the polynomial by sticking it in the exponent of a group element so class groups are this thing built from quadratic number fields and basically the size of a class group element is about the size of the

discriminant and if you start with a 1200 bit discriminant and you get about a hundred bits of security based on current estimations its about equivalent to 2048 bit RSA so 1200 bit class groups would be like 2048 bit ours and they don't require a trusted setup to build we can just choose a random discriminant and then define the class group and it's believed that it's hard to find the size so the evaluation protocol information theoretically or abstractly is like this you start with the original polynomial f of X you split it up into a left side and a right side okay where the left side and the right side are both now degree D over 2 so you

have F L of X plus X to the D over 2 times F R of X so f L has all the left side coefficients fr has all the right side coefficients but we factored out a term of size X to the D over 2 so the code so the degree of Fr is now half and then the verifier sends a random challenge to the prover and we recurse the protocol on the linear combination of the left side and the right side so this becomes f prime of x which is a polynomial of degree D over 2 and we recurse the same protocol on this and in every step we do read reduce the degree by half so what we actually do is we put those polynomials in the exponent of a

group element so that's how he gets the sync nests and we send a commitment to the left side and a commitment to the right side and so how does the verifier check that all these things are being done correctly well the approver the because of the homomorphic properties of the commitment the verifier could just check that the left left commitment co times the right commitment raised to the power Q to the D over 2 is equal to the commitment that we started with at the beginning and as well the prover will supply the claimed evaluations of the polynomial at points so he claims that the polynomial evaluated at Z is equal to Y then he'll give a claimed evaluation for the left

part 2yl acclaimed evaluation to the right part 2yr and this has to satisfy this consistency check that the claimed thing for the original polynomial is equal to the left part plus the right part times e to the Q / - right the problem is the verifier can't actually perform this check CL x CR - the Q the D / - efficiently so instead of doing that we use a trick called a proof of exponentiation and it's the same trick used to build efficient PDFs so the prover will prove that CR to the Q to the D over 2 is equal to C over CL and the verifier can verify this proof just doing 228 big group exponentiations plus some other

work that but this is the this is really the bottleneck of the verification so at every step the prover does 2 exponentiations and we have a logarithmic number of steps so we have basically 2 log of d exponentiations is the total verification work and the in addition observe in terms of what we're actually sending we're just sending we and there's some optimizations we can make so you only send to group elements per round so we get to log D proof size to log the exponentiations for verification so the last thing is that the problem is that the coefficients are growing in each round because we

multiply the right side by a factor alpha so that's why we can't actually just set Q to be larger than P but we have to set it to be basically larger than P to the 2 log T so the last final step of recursion the verifier is just sent a polynomial of degree zero which is just a constant term and the verifier is given this constant term in the clear you can just check this directly now I haven't explained zero knowledge what I've described so far is not zero knowledge at all but we have a way of transforming this using kind of standard tricks into zero knowledge by doing

things over hiding commitments thank you and I'll take some questions there any questions that event great huh I had a question so what about this is specific the groups of unknown order could you not do this over like commitments right so if you have another way of building a homomorphic integer commitment scheme that also yeah so if you have another basically if you have another way of building a home over begins at your commitment scheme then you don't need to use groups of run an order but you have to it has to also have succinct openings so basically you

have to ensure that you don't wrap around what q right right so this is really the reason for using groups of unknown order is that you can prove relations about integers in the exponent because you can't reduce the equation in the exponent modulo anything [Applause]