ETHParis: SNARKs vs SONICS

you will need to know about generics upfront at least a little bit and how they work and especially for a grass 16 probe system I guess well but first before we go further I mean I think everyone who has a main problem of snarks at least at the current integration of the technology of the snark consensus across 16 grow 17 proof system and what Sukesh guys use is a need for a trusted setup and so the same this slide is a little bit hyping but why Sonic's are important and why it's the next step I think because Sonic's are the same waste quite general its general proof system which is succinct anyway was updatable which is not that important practice but the most important part is universal comm the reference string for any circuit up to the given size so you can do use the trusted set up once run it together with metallic just didn't break what I'm very Joe Lubin and any other parties could just don't care about what will be in your common reference string and they don't have any incentive to break it make it once make it for a very large size apt like largest circuit you can imagine to be practically usable and then just use it for any circuit it the best example is like shuffling the deck of card let's see for previous proof systems if you wanted to play some game you need to take a deck to take a fresh deck shuffle it under the table pass it to someone who also shuffles and there is a table then you put the stack on the table and you plays a game and you need to do it every time for every particular game or every particular arm if you want to make it with Sonics you take the deck of cards you shuffle it you give it to someone who shall sit under the table and then you put it on a table then you magically clone it and use it for a game and someone else can magically clone it and use it for their game too I think it's like the simplest parallel and yeah but this has been practiced the comparison between cross 16 and Sonic proof systems and for people who already know I hope people know arcs at least a little bit as a waste to difficult to explain every single from scratch so cross 16 starts with rank on constraint system which people ready know how to work with several - links how to you can make what's called the gadgets and circuits in this paradigm the main parameters I'm a practical parameter as number of constraints because a larger number of constraints a most approving time and there is a practical limits on the number of constraints which you can use for some for example for assumes current curve which will be on the next slide and also for because this proof system is there for our three years already through our practice is recommendations so you can just take the goat make your own circuit and run the software which was written for you which can do the proving and the proving is time-consuming so it has to be made highly efficient so there are practical implementations which are highly efficient and the verification cast is also very low in specific budget mode you can make it down to two hundred thousand gas which is very low compared to onyx they jump person one okay for some reason so for Sonic's you can alpha start with rank one constraint system so this part is good because he just sonics work in some as a paradigm which is called the multiplication gates and linear constraints but you can convert from one to another without in many problems like hundred times of code will do everything for you the main parameter in this paradigm is a number of multiplication gates yeah and it's related to the number of constraints in the rank on constraint system I will later show how it's actually related and yeah and the largest problem is unfortunately the implementation and the verification guest first of all there is no full implementation and I would emphasize full efficient implementation and even when fast is more for implementation of which can do so sin proofs I will go to this part so he needs to send proofs so your very fire can run on the public blockchain you want as little communication complexity and verification complexity ideally canceling complexity to be actually able to run it in a public blockchain the verification will be still more expensive so now we talk about the efficient implementation this is completely different story as the original paper which introduces their knowledge proofs in principle as how snarks work there is no hard limit for a circuit size but there is a hard limit for efficiently provable circuit size and this limit depends on a number of roots of unity because you need to do Lagrange interpolation which requires roots of unity if you want to do it in linear time and because we work in a large circle in practice where most of the application you will want to work in a large circuits and it literally means that any operation you run should be linear in in the size of the input parameters otherwise you will never finish your work so for growth 16 it's known that all expensive operations are all sufficiently parallelizable by using the 50 which is efficiently parallelizable or operations like multi exponentiation which are all sufficiently parallelizable but the prover for growth 16 runs in both g1 and g2 groups on elliptic curve g2 operations multiplication for example can be taken roughly as four times more expensive it's not the largest contribution to the proper complexity and proper running time but still it's not negligible or sonics yeah now we get to the funny part in principle as the original paper states it's a number of constraints or well not constraint multiplication gates which you can do with a sonic is roughly the prime order of the curves group which is in Syria there you get good soundness in practice you need to do multiplication of the polynomials of the size roughly seven by number of multiplication gates and how to do multiplication of polynomials efficiently yes you do need to do an F of T and this also means you need roots of unity so this factor of seven gives you a hard limit so your practical circuit size will be like eight times smaller then for a current implementation a current grow sixteen proof system so it can still fit well you can still find applications whereas the Circa size is more than sufficient but we talk about the efficient implementation and hard limits in here the second one yes implementation as itself every iteration Elsa is at least for me looks parallelizable one was less effort another one was much more effort but still you can do it but you just need to sit and write it and the premiere actually does only multiplications in g1 which is Elsa gate and there because it's just one operation which you run very often you can go GP using you know go FPGAs you can go Asics as a all other kinds of special processors if you really want it so for a complete example how we can transform circuit from once from rank one constraint system 2 sonics and this will hold for most of the circuits just take the basic Mimzy circuit which has 644 constraints and it tells a day you will get 968 multiplication gates and well this 1.5 multiplier is it's very close to reality if you just divide one over another because the conversion procedure works that you convert every rank on constrained to one multiplication gate plus you more or less a line can make to like allocate two variables for one multiplication gates so this is like the final number we will get always very close to it so the original paper let's part is more about the original paper and how to read it a problem is it was a little bit hard to understand and I would name some parts of it a little bit different but let's stick to the original naming and what was there there was a procedure was just plain protocol how he makes approves that was so called helped procedure and and help procedure so let's start with a basic part which has just proved which does three paranormal commitments which are a viable income some time just want information and can be efficiently bunched together plus what's called the signature of correct computation the signature of correct computation is just evaluation fun polynominal over 1 multivariate polynomial to values for each variable and this part at the original protocol this part is not sustained in verification in the original protocol like the simplest protocol given on the fifth page it requires really fire to use this verification of signature of computation just but by brute force the refire also takes as polynomial and as polynomial just encodes every constraint in the system so it doesn't depend on any witnesses which prover takes like witness which you want to be actually hide it just depends on the public parameters if everyone that was the circuit they can always derive the s polynomial and so it will always get the same result and refire had to do this all by himself just this way fire will never work in a public key the second part what's called what was called the help procedure I would just call it batching really the same way proven makes now not one but few proofs all over the same statement or just over the same circuit those each of those consists of three polynomial commitments plus the signature of correct computations also for each of those what the helper can do as the helper can take this M proofs of M signatures of current computation which are signatures of evaluation of the polynomial and just make one I just transform them to like one once a proof which will require for verification just one evaluation of this s polynomial just but over the different points s just reduces the very fiery complexity from linear in number of proofs to some component which is succinct and and one and another component which is still linear in the number of multiple engage so this will also not work in a public blockchains but why it's called helped I think it should be just raised there was the same procedure which was called ant help but pretty doesn't have anything with help or not here the prover that's the same way the prover makes three poly normal commitments plus a signature of credit computation but spends more time by making the proof of correct computation to make the verifications to Sint so basically now is the very fire can actually run in a constant time and this is how it can be run on the public blockchain well the paper doesn't say as you don't need to stop here you can maybe make try to make what I try to call maybe the most optimal approach as you can make em proofs because masters application program will make a lot of probes anyway and you can save on verifications this way so you can make em proofs each of those is just poly normal commitments and the signature of grade computation HS on a he'll procedure and your helper doesn't just aggregate those signatures to create computation helpers pens now more time to make as a syn proof for this aggregated signature of computation and this procedure will be actually constant time it will be constant because constant time to verify the signature of computation plus well linear time is number of proofs but still you never proof is not huge let's say 10 to most like is this procedure is optimal also not implemented original implementation which was public and made on a github only implemented this procedure example and not efficiently so this is a difficult part the benchmarks will be in Berlin because the case I want to compare apples to apples and they cannot compare highly efficient implementation across 16 without first making the highly efficient implementation of sonics and the highly efficient means the most efficient which I can make up right now so if you want go to the key summit I think tickets are still available but speaker slots icing taken oh or contact you should know Anna from their knowledge podcast yeah thank you for your patience since it's quite high level of complexity and I can now try to answer your questions - just try to lower this level of complexity yeah anyone I mean yes it's highly involved but if you have a question I hope I can answer okay so grad 16 has seen some years of scrutiny by the community and still like some awkwardness was being found recently in Z cache how long does it take in your opinion for Sonic to be ready for production well first of all regarding the growth 16 a recent PR message from Z cache wasn't about grass 16 we will not discuss this story it wasn't a bug Ross 16 is the first place so the time between gross releasing his paper and sin cache actually using it in fact and some security analysis done it's taken two years so I think now because more and more people are get interested and security analysis is as Academical well is in interest of academia and we're a limited set of guys who actually want to do this I think it will take at least a year but due to also limitations which I mentioned before it will take at least a year to be able to efficiently use it on the cerium just due to the constant current choose of the curve which is available and the current pricing which well some of you knows that for last year there is a serum improvement protocol which reduces some of the elliptic curve operations from 15 to 5 times and it was implemented like the optimized implementation was made for gas and parity and was actually accepted in the baseline repository the eastern boom but this proposal was never accepted even also now every client already runs a fish in the competition so it could be in principle reduced and no one will be hurt you will not sponsor the price you will not sponsor as a computer as a processor time but yes it will take at least a year first for wait for some security analysis make efficient implementations two things first of all no one has found the killer feature for public place application yet so this is like connected story you can reason about whether there is a problem why it wasn't found yet either because not necessary or just doesn't scale or just because no one just yet has found it but for example neglecting the scaling and privacy and some fancy things like recursiveness which you can do what you can do is the previous speaker has mentioned in each Burling we did the game it just allows you to play interactive game with snarks without consuming the gas without consuming the storage without well verification of the snark may be important but you can get away with it actually with some tricks so what you can do is you can make it trust us there is no dealer there is no shuffling on the deck with some unknown entropy everyone comes into the room they supply some entropy and then you can prove that you shuffle your deck properly for example and then everyone knows that there their entropy was actually included in a deck shuffle they can play after it and even game itself can be make made as another snark which will healthy fish n't transforms us from interactive part with like everyone submits its transaction to the public blockchain to the part where everyone suggests either as a form of state channel or as a form of consecutive proving of their like their turns they can make a game yes the technology is well is not well the cross 16 I would say mature everything else is not yet especially with the Starks which will be closers for quite on time yes killer features a great yes it's wise their public home to be dished unnecessary searching someone even where if like even if all of us home is taken about the killer feature for snacks someone just finds it it should be a wait for him to implement it at the first place and just at least as the technology should be available and ideally have better tonics you're biased thank you everyone for your time [Applause]