ZK10: How to build a modern SNARK - Zac Williamson

Transcript

foreign [Music] MC hello everybody you ready for some math I can't hear you are you ready for some math all right it is amazing to see the crowd here today I mean wow Ezekiel Summit 10. I'm amazed this thing still exists in 2023 but all credit to Anna and a team amazing stuff I was there physique Summit too that was my earliest one where wow things were very very different it was a more of a less you know less promo more hole in the wall

he's Berlin a bit communist but Soviet but the Vibes were great and it's amazing to see so many people from there still still with us today and wow how things have changed I mean did you know that take us on the door here 650 pounds incredible I've um be doing a bit of you know a bit of online dating met someone through hinge had a few nice dates it was enjoyable then um yeah so she was like for the next date take me somewhere expensive so yeah she's not returning my calls anymore okay well before I get into the meat of this talk um I have an announcement to make uh quite quite a special one really so I've been in this industry in this working in

ZK privacy with Aztec for six years six years before the must and for all that time The Shining City on a Hill that Beacon that we've been aiming for is has been programmable privacy program based the ability to transact in a decentralized peer-to-peer manner either between individuals or small groups without intermediaries without revealing who you are or what you're doing we've always realized from the very start that it is the apotheosis in my opinion of blockchain if you think about the original cypherpunk vision from 2008 of what blockchain could be used for you know the global settlements layer everyone's going to be using Bitcoin

everything's going to be digital asset well it's been 15 years and let's be honest it's not really come true uh I like board Apes as much as the next person but it's not quite what we were imagining all the time ago and I would argue that the reason for that is because we do not have privacy without privacy you do not have the ability to link an identity to a cryptocurrency account without that you cannot link cryptocurrencies with real world assets and with the actual sources of value that people are transacting with in their day-to-day lives and privacy solves that and why I am talking about this just give me a second is because we have an announcement to make after a lot of work and a lot of effort we have finally been launched the Aztec sandbox so

the answer network is being designed as the end game for blockchain privacy it is one of the most if not the most ambitious and complete solution for privacy first blockchain applications that has ever been attempted it's taking us a lot of time to get here we've had to invent our own goddamn cryptography to get here but we're getting there and as previously mentioned the building of sandbox is taking just five months only five months from inception and it's a testament to the quality of the Aztec team to the dedication of my colleagues my team members and the ever improving modularity of our technology our open source technology the sandbox is our first major milestone in the development roadmap that includes a multi-phase test net for Aztec and our execution environments our fee model our

sequences our previous or culminating in a privacy preserving ZK roll-up that is fully decentralized at mainnet launch I don't need to click too many things too many things I'm going to move over here yes yes um so I mean the sandbox is effectively a local developer test net um a development environment for private smart contracts and what does that mean that means you've got private function execution public function execution and composability between private and part that private public link comparability between L1 and L2 the ability to create hybrid applications private State Management hidden function execution it looks and corks and quacks like a blockchain but you have private States

as a first class primitive and that's what comes in the Box alongside our local node testing environment our RPC servers and the Frameworks that allow developers to compose useful meaningful transaction flows that involve privacy which is a very new kind of pattern the sandbox has helps future looking developers get a head start with ZK native blockchain environments we have Concepts like private State account abstraction understanding the patterns that keep private information private and organizing contracts into the private and public executable logic components and so what I want to say is well you can get started in 10 minutes at sandbox.as technology Network that is the wait no I didn't click sorry I didn't click sandbox Network we've

launched and tomorrow tomorrow on Thursday we are doing a developer Workshop right here in London that QR code is will get you a sign up link so if you want to start getting get working with programmable privacy tomorrow scan that QR code no I don't see enough phones scanning we might need to change that Genevieve can you help me out here I think we might need a bit of motivation for people I don't see enough phones scanning the QR code all right who wants an airdrop who wants a goddamn airdrop all right there's more that came from

but it takes us a while to load all right all right can you hear that seriously this has been the combination of so much work at Aztec you know we've been trying to do this for six gone down years a lot of stuff in between Aztec one Aztec Two so you know we're gonna put the concussion back in ZK right that's the talk exactly it only says oh no okay if if any Aztec folks are here that

can help with that or sort it out or if they've just maybe that's just not enough space I'm sorry well I think we're live streaming it too what the bloody hell is hunk that is a question one of the questions in the planet today so it's hot stands for highlights on my Splunk and it's our attempt at creating a composable smart con uh crypto system that is very very privacy friendly and privacy first and what I want to talk about today is a little bit about how how it's built its techniques what we're using it for and how is how it's been made so to start with what are the four

like the the ZK snock landscape has become fantastically complex lately there's been an enormous amount of research into new protocols new techniques and we've been building layers upon layers upon layers of abstraction layers to enable us to increase complexity and increase proving speeds verifier speeds proof sizes Etc but this comes at a bit of a cost where everything is so complicated now it's very difficult to see how things actually work end to end um very rarely these days you get an actual paper which describes a protocol where it literally lists out the protocol it says here is an interactive protocol between a proven verifier do this do this do this do this do this because there's just so many abstractions and complexity it's very hard to do so I want to break some of that down today and talk about how we create an

end-to-end snark in a modern world with all of the new techniques and so this is what I think are the four kind of main key abstraction layers pillars of one CK snark you start with your circuit arithmetization that's effectively how do you um represent your program as algebraic relations what are those algebraic relations that you are evaluating you then compile that into a polynomial interactive Oracle proof so a piop will be an interactive protocol between approval and to verify that will validate the correctness of your arithmetization for a given instance and here is where a lot of the complexity lies in modern protocols there's lots of ways of doing it and then finally your Pio p is going to reduce the claim about the correct the correctness of your circuit to reclaim

about the some evaluations of committed polynomials and these polynomial schemes for that and there as well there's a huge design space mostly between um error correcting code based schemes hash-based schemes and uh additive groups basically curves and so and finally you have the defaulting schemes which uh as Anna's beautifully elucidated uh are somewhat complicated and yeah so Honkers are basically it's a parameterization of all four of these using various different choices and selections and I want to talk a little bit about it it's a snark for people who care about privacy still it's not many of us these days um so just a quick recap of what was it that we want our cryptography to do we have Aztec contracts are composed to

functions these functions are effectively individual snark circuits and a user transaction is a set of snark proofs that represent all of the functions that have been called within a transaction you then need another snark circuit uh candle circuit that will effectively verify the correctness of all these proofs and validate the transition functions between all of the proofs to verify that you know all the calls are correct this is very complicated um specifically because this kernel circuit with all of its intense recursion used to be computed client-side if you care about privacy because otherwise you leak secrets and that means that these proofs are being computed on wimpy consumer Hardware like phones and laptops and not only that but the proving environment is

probably webassembly because if you're interacting with a Dap in a web browser that's what you're going to get and so those are insane resource constraints that are absent if you do not if you are capable of delegating proof computation to a third party and that has knock-on effects for how the premium system is built because you care greatly about memory consumption here you care greatly about things like recursion not only because the architecture isn't inherently recursive but because you can use recursion to reduce memory consumption by breaking down your program into smaller chunks and iteratively proving them so what a song how do we do this so on the average position layer we use ultra plug which is effectively is planck plus and Gates lookup tables like Ram tables I can get into that in a bit uh very

efficient range checks it's basically all the tricks thrown in uh but it's relatively the actual alphabet position is pretty pretty old these days the IOP we use as a subject protocol of a multilinear polynomials very different from original hunk much faster it's linear time uh and then we use the xeromorph multi-linear polynomial commitment scheme to evaluate this these some check claims uh this was one of the effect of multinational PCS is one of the things that make multi-linear subjects a lot more useful these days and then finally we use the Proto star um folding scheme we use pretty galaxy performable instances but pretty star but they they pioneered this this concept and then finally we use Goblin flunk as a it's not really a word for it yet but it's a folding accelerator it

makes the complicated hard to do operations in folding schemes very efficient and cheap so these are some of the performance targets that we have for Pock uh we want our prover to be able to prove a million constraints in less than five seconds it doesn't seem too hard except that our prover is a phone and it's running webassembly um uh we have a gigabyte of ram not a terabyte a gigabyte which is a rubbish uh web browsers have a habit of killing tabs if you use more than that proof size needs to be small because we're a transaction Network a layer 2 which means that users are sending their transactions to a MIM pool if each transaction carries a zero knowledge proof and you want a very high transaction throughput and you want your nodes to be decentralized so any random

person can run a node oops that means they need to be able to um your network bandwidth cannot supersede an average board tracking connection so at a thousand TPS you can't have 100 kilobyte proofs um and finally we need our recursion unfolding cost to be certainly cheap we're targeting proof construction times of 20 milliseconds for recursion uh in webassembly uh so these are some rather weird requirements that you don't get from uh transparent systems in terms of asymptotics what is honk I mean I don't know I mean to be honest I've come up and make these numbers say whatever I want to uh the the thing that really matters is the code and actually what it really does but you can get a various of honkware in terms of elliptic

curve costs the equipment cost is equal to the number of unique wires in your circuit removing copies and then it's linear time in terms of field work uh so now I want to dive a little bit down peel back this abstractions and talk about these components in a bit more detail um what is like the multi-linear Assumption protocol I was speaking at um what was it faster or something realizing that actually whilst in my head this has been a big deal and a very very useful tool it's not really like that widespread that this is like amazing and that you want to use some checks in the multi in the multilinear form if you're evaluating uh complex expressions and that's because it's despite being a very very old technique it's all the problems that we're associated

with have been solved and it's very very efficient the idea is you have a bunch of input polynomials they can come from your input string your witness string they're in multilinear form and by multilinear I mean the the maximum degree of each variable is is one and you have some expression some expression of your polynomials that you want to evaluate and the idea is that what a substrate will do is you can you can sum over all of the possible evaluation points of your polynomials over some domain in this case zero and one and you check that the expression applied to those evaluations and then the sum of all the various different evaluation combinations you check this equal to zero and this is very easy to adapt into a system where you can check every constraint in a in a in a plonkish

type circuit or rmcs is zero by adding random polynomials in to make sure that you have linear Independence uh how it works it's pretty straightforward but for those for those who are unfamiliar the idea is that it you have a logarithmic number of rounds where you basically reduce the degree Bound by one each round um the audio is approver computes these univariate reductions where you evaluate the your expression over over your entire domain apart from for one variable which leaves in determinant that becomes your Universe polynomial gets sent to the verify the verified checks of that polynomial U at zero and one is zero because that's the whole the sum of everything on on zero and one is supposed to be zero and then the verify will generate a challenge ah and then we just iterate the idea is now

the produces a new universe except that one of that indeterminate variable is now being replaced with a the random challenge and you know make one of the additional variables in in determinus and you reduce the degree Bound by one and you keep that new unit variate sent to the verify the verify checks that that neither Union at zero and one equals the previous unit variate at the previous challenge that provides the continuity check between each univariate reduction and eventually once you perform log n rounds you will get to a relatively straightforward expression where there will be a claim a claim that your polynomial identity evaluated at a series of random points will equal a constant field element you can then check that with something like a polynomial commitment scheme the

once you have that you then need to move to well okay well what kind of commence scheme we use xeromorph so multilinear PCS have always been painful uh you know like logarithmic numbers of pairings blah blah blah uh recently there's been a bunch of solutions but basically you just compose a multilinear PCS out of it you never get one Gemini started this first uh xeromorph is an attempt to generalizing that and adding some efficiency tricks it's uh pretty efficient and the idea is pretty straightforward um well once it's been developed it was a brainchild of Tory one of our researchers is that there's just there's a linear iPhone modes and that's trivitely computable between the multilinear form and the univariate form of a polynomial um so if you have some kind of linear

relation over multilinear polynomials you can convert that to a linear relation of a universe polynomials by applying this isomorphism and this so happens that the Casey multi-linear kcg polynomial commitment scheme the relation that's being checked is linear is a linear expression so you can basically take multilinear multi multivariate kcg and apply these um isomorphisms to evaluate over univariate polynomials and compile everything to a univari PCS very efficient very nice and then we get to folding schemes so I think there's going to be some talks later today that will explain this in Far More depth than I can or will but at its core the idea is you have instead of having much a large number of proofs that you then construct independently and verify independently you take the input string witness string

tuples that describe um a relation that you want to prove and you take you take a set of those and you fold the input string witnessing tuples together um to create a new relation so the idea is instead of having a proven a verifier you now have approver an incremental verifier to verify the folds and a decider which was what your original verify would be the idea here is that you um the amazing thing about things like protocols like protostar is that they have a black box they can fold any arbitrary interactive critical along as long as you it can be categorized from this relatively straightforward structure where you um just you know you have an upper string witness string you have various rounds with messages and challenges and as long as you can evaluate fit into that structure you can

fold it with protostar it's very very powerful um and basically what it will do is it will take you had to find this randomized relation which is basically like your original relation but with an error term and what approaches star what filing students will do is they will take your an instance of a randomized relation it and multiple instances of the relation you want to fold and will spit out one instance of your randomized relation and the verify for that is very cheap and very effective so I have some slides here about how our circuit arithmetization works as well because there are a few little tricks that we can use I'm going to skip over these a little bit because running out of time uh too many too many shots with a cannon uh but um the uh uh yeah if you want to if you want to

ask me questions after the talk very happy to um but this is basically relatively standard autoblanc stuff but what I wanted to highlight is that there are some tactical tricks that we use in Ultra plunk that have not been widely disseminated which is worth talking about um specifically you can get super cheap range hacks with um blockage type systems you can get things like RAM and ROM tables dynamically accessible resizable arrays by manipulating the permutation arguments basically we take the original implementation argument you can imagine you have cells in a plonk circuit in your execution Trace like highlights some cells in red solid cells in green and you can you can efficiently prove that the set of the red cells is equal to the set of the green cells the values that is uh by manipulating the permutation just

tweaking some of the values and you're selected polynomials so it's effectively free and then you can use that to create things like cheap range checks let's say I want to range constrain the purple cells I want them all to be less than 2 to the 16. I will copy them into a new regionalized circuit there's that blue region I will apply a list equivalence check to prove that those two regions contain the same values but the blue one is sorted I will then apply arithmetic constraints or custom gates to validate that those blue cells are monotonically increasing in value uh so and check that the first one ends starts at zero the last one ends at two to the 16 minus one I've skipped out a few things here you need to add a few um dummy dummy wires as well so you can Traverse this range but ultimately you

can create a situation where doing a range Tech like a two like a 60 Minute range check effectively cost to prove a one group Edition not a scalar multiplication and addition I can talk about that after the talk and then we have Roman round tables this is relatively old techniques from like Arya and like and Tony Ram but the idea is you take a um a table entry is a tuple of index value and timestamp timestamp is kind of when in your circuit Trace you're performing a read and write and you can use this list equivalence check to effectively um copy the set of all of your table reads into a new sorted set where everything is sorted by index and then within that index

entries are sources by timestamp and then you can effectively if you have um you can compare pairs of rows and if the second row is a read operation you can assert that the values of the two rows have to be equal to one another and that gets you ram access effectively you can get it in about you can in two or three plonkers constraints or like 10 columns or nine columns you can validate the correctness of um like a dynamically resizable array we use it and while we use agnostic super powerful and then finally we have lookup tables which I really do not have time to go into but uh very powerful there's loads of new techniques that come out but what I really want to go through is a couple of open problems and new trends

that we've observed uh cropping up some of the exciting stuff that's happening first of all 40 schemes are a big deal they've massively change the critical design space because it introduces efficient and easy amortization effectively you can take a interactive protocol with a very expensive verify algorithm and use a folding to turn that into an expensive decide algorithm and then you can fold a large number of instances of this protocol using a cheap incremental verifier and effectively amortize away the cost of that expensive decider every protocol gets some of this for free for example with Planck when you use the following scheme you don't need to provide polynomial opening proofs for every single instance anymore and that's

a big deal but it that technique can extend a much more complicated scenarios and it's extremely powerful uh the other one is that gkr is a big deal so this is again a relatively old critical about creating layered alphabetic circuits we have this kind of recursive relation where um uh like previously it's been considered that you know you have some layered arithmetic circuit where the output wires of the current layer equal the input wise of the previous layer but I believe that's only can be generalized considerably and effectively what you can end up with is a scenario where any interactive protocol where the prover is sending messages to the verifier that can be derived from other messages you can eliminate those messages and there and the commitments that are sent along with them uh for

example with Planck you can remove the ground product polynomial um with lookups you can remove the log derivative um inverse polynomial it's extremely powerful but it's also an open problem to make it efficiently foldable because I believe currently folding GTR instances gives the incremental verifier a log squared n cost in terms of hashing because the gcap protocol is lost quite in which is rather painful so before I go so I think I might be running over slightly one minute um I mentioned before it's very rare these days for a protocol to be just like written abouts where you actually have where where the writer will describe an interactive protocol between a two render verifier that will just say do this do this do this do this do this

so I figured I'd have a go for hunk and so uh Once Upon a Time there was a psychological horror um this is just the first page yeah yeah uh so yeah this is why they aren't written out anymore the end [Applause]