# The Future of PlonK ish System

- Channel: [Devcon](https://streameth.org/devcon)
- Date: 2023-10-09
- Duration: 16:57
- Topics: blockchain, smart contracts, distributed ledger, ethereum, Science & Technology
- Watch: https://streameth.org/watch/yt-lDL-sirFB-Y
- YouTube: https://www.youtube.com/watch?v=lDL-sirFB-Y

## Description

Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on IPFS and more.
https://archive.devcon.org/archive/watch/6/cryptographic-optimizations-in-aztec/index

.

Speaker(s): Adrian Hamelink
Skill level: Beginner
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: zk

Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/ 

Devcon is the Ethereum conference for developers, researchers, thinkers, and makers. 
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/

## Transcript

foreign [Music] the next presentation is by Adrian from Aztec the future of punkish systems and I expect Adrian on the zoom later yeah hi everybody I'm Adrian and I work at Aztec basically making snarks faster I hope you're all having a wonderful time in Bogota this week um unfortunately I wasn't able to make it due to getting sick at the last moment last week and so this is why this presentation has been pre-recorded I'm going to be talking about some thoughts and hypotheses I have about what the next generation of plunkish systems is going to look like by the way there's going to be a q a once this video finishes so write down any questions you may have with slight numbers I'll do my best to answer it at that point and here's my Twitter and telegram handle if ever you have any questions that come up later so I'm going to start with a brief recap of the evolution of Planck until now in 2019 Zach and Ariel came up with this certainly name proof system that kind of revolutionizes EK space um the state of the art until then was basically growth 16 which is based on r1cs um but the per circuit trusted setup made it a bit more complicated to deploy with Planck now we had a ZK snark with very similar performance profile it only required a one-time trusted setup but really I think it's one of the main Innovations was that we're now able to represent circuits in a much more practical way which made writing circuits easier because they re the resulting representation looked a lot more like the actual functionality you wanted to compute over the years have followed many new techniques and tools and improvements were introduced that basically tried to tackle concrete efficiency um there's the introduction of different custom Gates um which allowed for more efficient elliptic curve uh group operations for uh different hash functions or really any kind of uh more specific computation you might have in mind that might appear several times inside of a circuits we also got lookup protocols which allowed us to essentially pre-compute the inputs and outputs of more complicated functions there might be a lot harder to do inside of a circuits and in a way that we can just look up the results from these huge tables and this made a big difference especially for uh not for operations or functions which are hard to do inside of a circle with that works over finite fields um it also made range checks a lot easier to check that an integer is in a certain range but beyond that there's also a lot of work done on just improving the tooling and the introduction of quite a few languages and um and dsls like Noir or Halo 2 which essentially help make more optimized circuits and one thing I want to note with all these improvements is that they all try to tackle the same thing which is prover time with a lot of these what you're trying to do is make the circuits smaller more optimized but the real concrete effect of this is that the approver has to do less work unfortunately there's only so much we can do and we're still faced with the same roadblocks like the ffts which mean that the proving time is going to be lower bounded by n log n so you may wonder what's next for plunk well recently at ZK Summit 8 in Berlin uh Benedict buns from espresso system announced hyperplunk and it claims to drastically efficially increase the efficiency of uh plunkish circuits the main Improvement is that there are no more ffts involved and the proof can now be generated in time linear in the circuit size at the heart is subject an incredibly efficient protocol from the 90s even though it's been out for almost 30 years at this point I don't think it's received nearly as much attention as it deserves especially in the context of starks this is great because this means we've got a brand new problem that's ripe for optimizations so in this talk I want to go over some of my personal hypotheses about what changes were likely going to see around CK snark circuits and deployments now that we've got this new proof system to work with so instead of a snark we need an efficient way of checking that n different polynomial equations vanish over a predetermined subset of the finite field previously this was done using a quotient test that relied heavily on ffts however we've now found out that this is doable with some check as well from a high level this table shows the main differences that come up when we use one system over another first of all we have to change the way we represent polynomials instead of interpolating a vector as a univariate polynomial over the roots of unity we use multilinear polynomials over a binary hypercube we notice something particular we have to sacrifice small proofs and fast verifiers in exchange for faster proverbs but when you want to implement snark these asymptotics hide way too much detail and I'm going to argue that the benefits for the prover are actually a lot better than just removing this login overhead from the ffts so let's get into the weed bit um recall it that we usually want to prove that we have this polynomial P usually called like the Planck identity which is a polynomial which equals zero when it's evaluated Over All Points little H belonging to a larger subset H now what this this Planck identity really look like well I'm going to give you a simplified view of it but essentially what it does is it is a sum of all the different Gates um that are would make up our circuits and multiply it by different selectors which either activate or disactivate a gate depending on which operation you're actually trying to do in each row now I want to emphasize that um this is a curse simplification of what is actually happening mainly to get everything to fit in the slides um and so don't go implementing this stuff um if we look at this identity I wrote down what we have is a certain number of custom Gates and each of them are multiplied by this multilinear binary selector polynomial SJ so this is just a vector the interpolation of a vector of zeros and ones and it multiplies this more complex gate polynomial which is going to be zero if the the gate is Satisfied by the input wires W along with some fixed constants uh Q so both W and Q are multilinear polynomials and G is just a function which combines these now if we take a closer look at the selector we can see that it's just the an indicator function over the over specific set HJ now I'm choosing to partition H in this way because it makes it more clear like in which parts of the circuit in which rows each gate is active and this is going to help us a bit later on basically the circuit is valid as this polynomial vanishes which is only the case when either the selector is zero for each gate or the gate itself equals zero the way you'd prove this in standard plan is just by Computing the polynomial which divides this polynomial P um where the the division is by the X N minus 1 which equals zero over all the roots of unity how do we do it with some check though now the way is usually presented is that it allows a proverb to approve a claim of the type Sigma is equal to the sum of all the evaluations over h of a certain polynomial function p now we we this doesn't help us right away but instead if we said P Prime is equal to P multiplied by this weird random equality polynomial that's often used uh in some check um proof systems well we can set Sigma equal to zero and because this random linear combination zero well proving the sub check essentially is equivalent to a Vanishing test now unfortunately due to the time constraints I I'm not going to be able to get into more detail about how to perform the actual sum check there's a little selfies involved and I need to make some big simplifications but one of the key observations I want to make is that if we look at the some check Sun for one particular gate so we just take the gate from the previous slide and multiply it by this equality polynomial this selector polynomial plays a big role because we notice when H ranges over big H well s of J is going to be zero whenever the gate is not active so this means that we can rewrite the sum ranging over um with a set of points at which H I wish G is active now concretely this means that the prover only actually has to evaluate this polynomial equation G in the number of times that it's actually used in other words the proving time is now much more closely linked to the time it would take to evaluate the actual circuits because we don't need to evaluate the gates in at indexes where they're not active um and the verifier time basically only depends on the maximum size of circuits again this is due to some check but for each additional custom gate that we have it only adds a constant amount of overhead so if we take a step back what do we actually get when we use some chicken practice so what I expect to see is it will have provers to find with way more custom Gates than we previously have and you may have some which have way more complexity which are able to do a lot more work at once even if those gates are not used very often because essentially due to those sparsity that's preserved by not having to do the ffts the prover is only going to be running the gates that are actually active in other words you're only paying for what you use to me this kind of feels like we're heading to a more uh an architecture for circuit that resembles a bit what we had with like x86 processors which are complex instruction set uh processors where you've got many different kind of functions um this is compared to the risk or reduced instruction sets type of processors where you only have a couple of instructions to use from so it's kind of interesting to see this difference in How We Do circuits compared to processors um however this isn't um the only thing that we get from subject in fact um if you've got like rather optimized implementations you you weigh smaller memory Footprints uh than what we currently have and another nice thing about the memory is that the access pattern is a lot better everything is more sequential which means that you're able to way more easily parallelize uh this sub check procedure now unfortunately we're still gonna have to deal with this annoying login uh verifier cost and proof size but one thing that's happened over the last few years is we we got a lot better at doing recursion and we understand it a lot better and what this means is we will be able to more efficiently and more easily um write a standard plunkish circuit that just performs the some check based plunk proof verification and therefore we end up with a Best of Both Worlds situation where we got a really fast proverb with relatively small overhead to generate a proof and the final proof is going to be constant sized with a fast verification another really nice thing is that some check doesn't really rely anymore on on a specific field so we because we don't do any more ffts but we don't really need any specific field which has a large um root of unity which means that we might be able to deploy snacks over different curves now um although that also depends on the trusted setups we have available Etc so with that I hope I've convinced you that um there's a lot to look forward to in terms of uh improvements for snarks and the future is going to be bright full of possible optimizations and I in any case can't wait to see what everybody is going to come up with um please let me know if you have any questions and again here's my handle if ever you have any questions that come up later thank you so any questions for Adrian I'm gonna put I actually have a question um oh you have a question go go for it yeah thanks for the presentation I have a question about the some check argument uh how we can handle not these things canceling out to zero are we going to need to choose a specific field size so because we are just adding a piece of stuff and we are assuming if they are all zero addition will be zero but what if sometimes are not zero and they somehow cancel each other out would that be possible or why it's not possible or anything but if I get your question right it's like when you have the sum over all the gates uh what I'm missing here is like a linear combination Factor like gamma like the the kind of one you would have in uh plunk as well that answers your question yeah it's like a random linear combination I get that we can do that for uh combining the addition for different circuits but for each circuit we have a sum right on HJ so why that summation would not be zero even if there are cases that all the terms are not zero does it make sense great so I missed like all this uh like the actual some check protocol what happened actually happens is you're proving that some by sending uh uniberate restriction polynomials so you you sum over like part of the points and you keep one free variable and you send login you know very polynomials which need to satisfy some property and like that's taking care of the Assumption okay we can continue this discussion async but thank you Adrian um cool