ZK12: MegaPlonk. Or, how I learned to stop worrying and love the plonk. - Zac Williamson

Transcript

[Music] cool hello everyone so uh do I have a clicker ah here it is I'm just blind so yeah I'm Zack I am the CEO of Aztec and I'm here to bring the good news about about honk Mega honk so um who here has heard of Aztec hey okay I'm still going to explain what Astic is there for like the few few don't um so Astic is a privacy preserving um programmable Layer Two for ethereum so we do SNS but we also do privacy private State All That Jazz

um can't do technology um is this uh hello help h ah okay hey okay great so um yeah so we've been around for almost 7 years now um which in web 3 years makes us geriatric um you know so I'm about to I'm about to retire to to a home but um yeah so we've been pretty busy this all that all that time um so I got I was learning about CK SNS and all of that

jazz in 2018 and it's ever since then the goal has really been for me and and on our team to create programmable privacy preserving smart contracts um so you know as a a regular with free engineer can write a smart contract like they do on ethereum like they do in salana but you have uh private status first class Primitives and you can do all sorts of fancy things like um identity controls and um uh hidden State information games basically allowing the real world to interface with web free by creating trustless oracles Z get email the works and so yeah this is we've um um this originally what we're now calling Aztec was called Aztec 3 because

uh We've uh released several several uh private rollups um uh and various pieces of tech uh over the over the past six years but this is the culmination of all of our work this is the grand plan and the grand project for Aztec uh to create that fully program privacy preserving L2 uh and to ship it sometime next year this is our road map so just want to just want to tap this uh we put this together and announced it the other day um so we have a plan we have a concept of a plan even um and this is that so yes um uh if you want to know more that is the website link I don't think I've ever seen anyone actually follow a website link from a slide presentation

so if you'd like to be the first person in the world to do that please feel free um okay okay well the laser PO is more jetlagged than I am maybe it's just me yeah it doesn't like me who needs slides anyways um so well if if you can get it working uh that would be oh yes oh fantastic amazing what a wonderful modern world we live in so um yes um by the way you might have noticed or may not have noticed um uhi one of our um event managers has made

some wonderful Taylor Swift te friendship Bas it so we're all friends here this is the uh 11th ZK sem I've been to I believe so um who would like a Astic themed friendship bracelet yes ah who else anymore okay right back let's see if I can do that ah almost okay all right you ready for some plunk I didn't hear that woo you see I like to raise the expectations of everyone before crushing their dreams with boring cryptography

and maths so what do I want to talk about what the hell is privacy what the hell is and like okay so I want to talk about a few things before getting into what the hell is Mega because ever like the ziki S landscape is extremely diverse these days and um a lot of previous system proving systems are very much get becoming like tailored to quite specific use cases on the on the various tradeoff space and so at as we made some pretty pretty specific choices to satisfy some specific requirements that I want to talk about and also maybe sh Aztec slightly as well so privacy um what do we even mean by privacy in a in a blockchain context you know like do we mean um like what is a hidden transaction

so there are three times of privacy I think this was this came from Anna and I've been stealing it ever since basically you have data privacy user privacy and transaction privac contract privacy code privacy data privacy is you know you can see who's sending who's transacting but you don't know what they're doing what data they're transferring user privacy is obviously you don't know who the senders and the recipients are and code privacy when do not even know which smart contracts are being executed um and the goal of Aztec is to achieve all three and that's something that we are doing with the current Aztec Network so um this can kind of be summed up as basically saying if you have all three private privacy properties if you look at a blockchain you look at the list of transactions going through you

look at the transaction data or you can conclude as something happened and that's about it um so um how do we actually create privacy preserving State models um I don't know why I'm even looking here I can see it here I'm just blind um so there's a there's a pro there's a problem with privacy well there's many problems with privacy but it wouldn't have taken seven years otherwise but one of them is that if you have private State that's encrypted it's owned by effectively owned by the people that can decrypt that State uh and that can be a problem for things like shared Global States how do you create a decentralized exchange with a total liqu Supply um if that thing is encrypted CU

well who ears the decryption keys and you can solve that kind of thing with very very complicated multiparty competitions or you can just be a bit lazy about it um and have a hybrid system where you have um individual user state which is private but you also have protocol state for things like decentralized exchanges which can be public and you have composability between um the private and private public aspects basically things like uh you you in this example um you'd have a public token transer function and a private token transfer function and so um basically you can you can selectively disclose information if you want to but you can keep it private like the way that we refer to this is this this pattern is very much the concept of

privacy for the user but transparency for the protocol um which generally we think is the best of all world because when you have you know decentralized protocols you do want to be able to apply oversight to them and if they're hiding their data that's hard to do so the asset contract model is you have these private functions and public functions they modify different state trees in the ACH Network so you've got this unspent transaction object tree uh that handles the private side and on the public side you have a more regular ethereum based account Tre and of course we trying we want to abstract pretty much all of the like messiness around handling utxos away with um uh um using no's uh very Advanced semantics um but this is fundamentally what's going on

under the hood uh so the idea is that uh you have a data tree that is encrypted notes and a data tree that represents account based date um and yeah that's how you do um privacy so yes hang on let's oh let's not see that again so architecture um how does the ACH Network function broadly um so this was um our original kind of uh first attempt at creating the architecture diagram I don't think you can see it but it says this diagram is Mike's baby please do not edit it without first Consulting M smiley face um so very complicated very messy so let's try to break it down um a user transaction in a networ like Aztec

um is what do you what what an observer actually sees when they send that transaction to the transaction pool is you have this concept of a kernel proof which is a bit like the ZXI protocol uh a kernel is a program that validates the correctness of individual transactions so you have a Kel proof um a list of state variables to create a list of nullifiers which represent State variables to destroy a list of public functions to execute and the world state that was used to compute the kernel proof that's all that that an individual will see when they look at a usess transactions um and from that uh you can acquire very little information if they are not executing public functions and the number of utxo and nullifiers that they're creating uh is conforms to some

kind of standard say two in two out then this transaction you can make this transaction look uniform with thousands tens of thousands of other transactions um so the transaction flow is very much you have this concept of aernal proof which is going to be validating client side a lot of the ASC protocol hiding a lot of information um that then gets sent to the the proof gets sent to a sequencer Network peer-to-peer transaction network uh the block producer which is selected through a decentralized mechanism called finet um uh when they include your transaction in a block they will send that block off to a proven Network to make a proof that's when the public functions that um your calling in your in your transaction flow uh get proved um and then it goes to a

L1 rup contract simple right um so how do we build privacy preserving abstractions well we use a language called Noir um it's very much based on Rust uh and very uh actively under development um so we've been working on it for about three years now uh and it's a very different Beast to what it once was um pretty Advanced and sophisticated and um we we could use Noir to create very bespoke um abstractions around how to handle privacy preserving information how to efficiently encode programs of snar secs so data is represented as encrypted notes so you know you have a contract address a Nots your storage slot some storage data it's a bit like how ethereum does it except this stuff

is encrypted because um there should be a secret in there no we forgot um and then you have this concept of a nullifier so uh who here knows about nullifiers wonderful that's a lot of hands I'm very impressed uh so um for those who haven't raised their hands the problem with privacy preserving um transaction networks is if I let's say I send um some uh I send I want to send an ethereum to yens um and uh it's I want to do this an encrypted way well if I have a um like a note that says Zack owns one ethereum um even if it's encrypted the act of deleting that note

would leak information Lively uh because on the blockchain network you'd have to say Okay that note's destroyed now um and uh and so you could see the transaction that created that note you could see the transaction that destroyed that note you see the transaction graph that's a problem nullify solved this because nullify is effectively a way of recording a note as being deleted without uh revealing that information effectively what it is is a nullifier is is the is the note but encrypted under a different encryption algorithm um and so in order to spend a note I need to prove that the note exists and the nullifier does not exist and I prove that locally client site in a privacy preserving ZK snar so nobody else leaks this information and because

the nullifier so encrypted with a different algorithm if I create a nullifier and post on the Chain um nobody can link that nullifier to a note that I originally created um so basically you see if I wanted to send one e yens I would create Yen's note and I would create one nullifier uh but nobody would know like the the owners of those two entities uh so yeah encrypted notes in Aztec they're not I say notes because I'm using the like the Bitcoin nomenclature of utxo unspent transaction wait they don't use note either I don't know where not came from maybe zcash basically uh in Aztec notes don't represent cryptocurrency values they represent abstract arbitrary state

that a smart contract gets to Define how it's used a bit like storage data in an ethereum smart contract so here you know we're saying basically encrypted notes they live in storage slots within a contract uh so instead of having the the idea of um in a lot in other priv of preserving architectures the the concept is you have you have state that exists on a blockchain and you define birth and death predicates on that state um very literally creating State transition functions for single state variables we're taking more of the ethereum approach of you have a smart contract and that smart contract controls a bunch of arbitary states and you can Define like the modification rules um in a in a in a much more abstract way uh public private transactions of public effect so you can emit an event

if you want you can uh call public functions obviously this will leak some information so you be be careful with it uh but sometimes it's necessary uh um so yeah Tada um and then provs and sequences create this concept of recursive develop so once you have all your user transactions every user transaction has a very chunky zero knowledge proof attached to it that's not cool expensive to verify on chain so we don't we um had this rollup architecture basically this two to two to one compression function where you recursively verify two proofs make that one proof um and then you create like this tree hierarchy of um uh recursive provs uh which basically means as long as you have arbitrary computes which for a proven Network you basically do um

then the the overall time required to make that the full rollup proof is logarithmic in the number of transactions in the block which is nice allows us to get in theory High transaction throughputs okay so I know this talk was titled Mega Punk and I haven't talked about honk or plonk or anything yet so this is uh this is way I do that one second okay cryptography cryptography right so what do we want what do we want our cryptography to do um So based off of everything I've said we have a few requirements because we are focusing on privacy we need to do fast client sight approving because you

don't want we don't want to have to have users share information with other people uh that client side proving needs to be low memory because if you're working on a phone and you're interacting with a web application then your phone's browser is going to Nuke any tab that uses more than a gigabyte of memory which is fun um and we need extremely fast recursion of folding client side partially this is this is um how we uh architect are transactions because if you have a smart contract that calls another smart contract that calls another smart contract and you want to represent that all in a single transaction well all the smart contract calls are basically representing um arbitary the execution of arbitary untrusted code and so recursion creates a very nice abstraction where you can basically Silo that those those programs into individual snar circuits

recursively verify them together and then apply some additional logic to validate the snars are doing what they should be doing in our kernel circuit but that needs recursion we can also use recursion to get past memory bottlenecks by um uh recursing before you use too much memory and we need relatively small proof sizes this one is a little bit oblique um why do we need small proof sizes when all our proofs are going to be combined in a rollup it's because asers are going to be launched as a fully decentralized Network which means every user transaction is broadcast through a peer-to-peer Network and so if every us of transaction is large say it's let's say for example it's 100 kiloby then in order to get you know 100 TPS that means you have 10 megabytes a second you need 10 megabytes of second

through put on your P top network uh which means you need considerably greater latency um to get that much throughput so small prezes are kind of important for us so how do we do this so we have a rather complicated cryptography stack now um you know back in the day you used to just have a proving system and you were done um but nowadays we have lots of additional high level abstractions to handle things like the concept of incrementally verifiable computation which I'll get into a little bit so our main thing is honk honk stands for uh highly optimized plunk it's basically it's an iteration of the um uh well both the plunk protocol from 2019 and the uh hyper plunk paper um from a couple of years ago basically

it's take the original plunk paper replace the check the the um the quotient testing check where we check some quotient polinomial um is zero modular Vanishing polinomial and replace that with a sum Che critical uh why do we do that I'll get into that actually um add a lookup critical add a bunch of custom Gates and boom bobsy rle prot Galaxy is a incrementally verifiable computation scheme um produced by um arum it's an iteration of pro star uh and it's very very efficient at folding honk instances specifically it's efficient holding folding arbitrary H instances by instance I mean circuit so you can have a thousand different circuits you can fold them all together together and it does the job perfectly which is very a very rare property of

folding schemes uh but then we have something called Goblin plunk um so if you uh if you if you if you subject your your brain to be rotted on crypto Twitter you might have heard this phrase before so Goblin plunk is a uh computation deferral scheme acceleration scheme basically Proto Galaxy requires some expensive computations to be proven inside a circuit these things called non-native elliptic curve operations they're very painful to do we don't like to do them we like to be lazy so so we have this protocol to basically transform these difficult computations into easy computations which we get into a bit and then we have the thing called the data bus which is um how to transfer information efficiently between um like multiple steps of an incrementally verifiable computation

scheme so this one's a little a little little old uh we working we're working on a year ago I think yens has a very nice memory checking scheme which which um which is better than this but uh yeah we're uh focusing more on security these days so honk what does honk uh um so why do we use a some critical uh some checks are a much older technology than this concept of qu testing I think they were around in the 1990s um they they form the background of the of like of the early um Proto ZK snarks uh but it fell out of favor because back in the day they had some they had some diff they had some problems

specifically in order to efficiently like prove and verify some checks you need you need a multilinear polinomial commitment scheme which is more complicated Beast than a multi than a univariate polinomial commment scheme and until the last couple of years we didn't really know how to both efficiently encode a multilinear PCS whilst acquiring important properties needed for a plish circuit specifically this concept of a shift if you have a basically we use pols as vectors more or less um and so if you're committing to a vector um how do you get a like how do you do a off by one shift of that Vector that's really important and until recently we didn't really have a good way of doing that um in a mult with a multilinear polinomial because if you're representing your vector as a

multi-dimensional ban hyper Cube then there's no like uniform transformation you can do with the hyper Cube to get a shift uh um so yeah there are a few reasons why some checks weren't used until recently but those problems have been solved so now some checks are lovely because they are um they have linear complexity um in Prova time uh and they have very very low relative memory consumption because you don't have fph freia transforms you're not blowing up your your witness Trace um so for Aztec and the fact that we have a very very very small memory footprint of play rith this is very important for us and we have a paper we have a draft paper that's hopefully going to turn into a real paper before the end of the year so just

teasing that now um honk. PDF um so we've had to be relative aely uh um opinionated about like the specific configuration of honk that we're using for Noir and Aztec this is because we want to make sure that in the Aztec Network every proof that's being verified is has some has some uh common structures for example the the number of selected polinomial is the same the the algebraic statements being checked in the snar are the same and so this is basically what we settled on is in how do you compile programs to circuits where you can do like pry much like pretty Advanced arbit computations without a VM uh because client side

virtual machines add uh quite a big overhead to to memory consumption um and recursion costs sometimes so yeah basically we have Tic C operations arithmetic gates gates to do non-n field arithmetic efficiently if you've ever worked with this stuff you'll understand why um uh we have these kind of memory checking gates for these what we call romen Rab abstractions basically readon memory random axis memory so in Noir if you're creating an array and then you're reading from that array arbitary points or you're writing and reading into that array repeatedly um this is what's happening under the hood and then plup gates for the well originally it was the plup protocol it's now the log up protocol that we used so that should be changed and then we also have our a modification to our permutation argument

which create allows for implicit efficient range constraints for small range values um and the subset equivalence check concept basically in your circuit in your witness Trace you can basically Define uh imagine you like you you color a bunch of wires red you color a bunch of wires yellow you can prove the set of red wires is equal to the set of yellow wires but the ordering of the two is undefined and that's very useful for memory abstractions and range checks uh the paper will reveal all maybe if we have some of questions I can do that too so here's an example of what's in the paper sting gate this is really basic um how do we do range checks I'll go into it so because of this this subset equivalence check what

you can do is if you have a bunch of wires in your circuit you want a range constraint let's say you want to put them all to be within a well 14bit um Range we the at the end of constructing the circuit we add additional dummy gates at the very end and then what we do is we we tag all the wires that are need to be range constrained and we copy them into this into the additional spare Gates we created and then we apply a subset equivalence check so we say like the the copied the cloned wires their values are equal to for the original range checked wires why is that useful because in the cloned version they're sorted basic they're sorted incrementing value um and so um with the addition of a few additional dummy gates to make sure that you can uh transition across the range

what we do is in the sorted list we say we assert that the first wire is zero the last wire is two to the K minus one for a kbit range check and the relative difference between two adjacent y's in that list is z 1 2 or 3 so as long as you have 2 to the K divided by three dummy wires in the circuit um you can um guarantee you can always Traverse that range and what that does is it basically gives you constant complexity range checks instead of having to do decompositions um you can well in our case basically get a 14bit range check for a quarter of a gate and then you can obviously combine those for larger range checks why 14 bits um it's because we optimize for small circuits because we're doing client side proving and

the larger the range table the more dumy gates you need IVC so yeah this is where things get really complicated um who here has heard of incrementally verifiable computation got to say the level of literacy in this room is is amazingly High you should all you should be very proud of yourselves um so uh incrementally verifiable computation what the hell does that mean so imagine you have some some permanent State some database or something some input State and then you have multiple s um proofs that are modifying that state so you have some input State output State and then and then the output state becomes input state to when new circuit and on and on you go is called incrementally verified by computation because you're

just basically updating some blob of data over and over again uh repeatedly um and an Aztec transaction can be considered an IVC basically every single time you're calling a function you're modifying some State um and so it's a fancy way basically saying recursion um and recursion is a fancy way of saying verifying aof and a proof um but um not fully verifying a proof because that's expensive basically doing as little as you can to mostly verifier proof uh and yeah so FS with this current state of the art uh and they enil for ridiculously efficient recursion the idea here is in azc each private function compiles to a distinct circuit

and we need an IVC scheme that can compose what we say by compose the sequence of ARB functions means basically um we can uh we have a function call stack uh represented in our circuit and in the in the kernel circuit we pop a function of the function call stack and then we verify a proof associate with that function and then we examine that proof's public inputs and depending on what they do we may push additional functions onto the function call stack or emit other effects um and that's basically one iteration of the kernel circuit and so to fully execute a transaction you need to repeatedly prove the kernel circuit over and over and over again until the function Co step Bec empty uh so back in the day this was basically like a pipe dream when we

launched Aztec connect in 2022 it was one of the first uses of recursion on ethereum and it was 700,000 constraints to recurse to to do like 32 recursions took 5 minutes of a 128 core server and 128 gab of memory so the idea of doing this client side was a pipe dream but a lot has changed since 2022 now this is relatively easy um this is our IVC scheme can you can anyone see that I can't even see that and I'm like one meter away okay um so basic let me try and walk it through I can use the laser pointer so the idea is all these FS are functions that represent individual like smart contract functions and K represents a kernel circuit so the idea is what we're doing as every

iteration um coming in as a function statement and a proof um and the and the previous Cel instance we then ver vivc is basically folding we fold F2 uh the the function and the previous kernel circuit into some kind of accumulator um and then we spit out the um uh we spit out basically all the side effects that have been created from the transaction as well as the the newly created accumulator and the idea is you repeat that step that that process over and over and over and over again until we get to this concept of what we call a ceiling circuit which is basically where we add uh add in the zero knowledge because zero is somewhat expensive we don't want to do it unless we have to so here is where um all the information

that used to public becomes private and all you get out of this is the pure side effects basically those encrypted notes to create the encrypted nullifies to destroy the public functions to call everything else gets hidden away so you don't even know who's sending the transaction um and then that gets sent to a rollup which verifies this this absolute nightmare in something we call a tube circuit um what's Goblin oh dear how much time have I got what a few minutes wonderful um so what the hell is Goblin plunk so I think at one point it was basically a fever dream that turned into a sort of a protocol that is I think we're getting a paper out end of the year um I call this

a computation accelerator the idea is when you're folding when you're doing this thing every time you want to do a fold basically you have a you have uh commitments to your to to your circuits you have commitments to your incoming functions proof you have commitments to your uh incoming previous Cal iteration proof and those commitments are elliptic curve points and in order to fold them you need to do scal multiplications on those elliptic curve points which is annoying painful we don't want to do that because uh it's this unique it's it's a very uh like Infamous problem in in ziki SNS where if you're working over single elliptic curve and you want to do elliptic curve arithmetic in that elliptic curve um over a snack to find that elliptic curve the prime field you need to work with is not the same as a

prime field available in your circuit so you need to do emulated Prime field arithmetic very expensive very painful want to do it so we use Goblin plong instead uh okay so how does it work I should know I designed it um so we have this concept of of an operations CU so let's say you're in your circuit you know life is good you're doing folding and then oh no you need to do a bunch of you need to do Cur scale and multiplication how about instead you don't what you do instead is you have a little you have basically a table that you can write information into and in that table you basically you write in the elliptic curve instruction that you need to do and your claim as to what the result is and then you move on with your life you just assume the claim is correct um

obviously that is very efficient because you're not you're not doing any work um and that table that you're you're writing stuff into basically becomes a commitment to what we call a transcript a commitment to all the TIC curve operations that you need to prove but have not yet proven and the idea is in our IVC scheme as we are folding folding folding folding folding What's Happening Here is in some of the out in this in this side effect outputs um we're getting an an incrementing list of elliptic curve instructions to perform so basically it's a bit like um it's a bit like you know maybe when you know back at University we have a lot of a lot of a lot of assignments that do lots of responsibilities piling up and you're just ignoring them trying to drink the pain away until at some point you finally have to deal with it

uh and then how do we deal with it so um this I think we we we borrowed stole we inspired by the e Foundation um uh and their blob work with this which is basically so you have a commitments to elliptic curve operations um over let's say curve a um and we know that elliptic curve B can of can very efficiently evaluate operations of a curve a um so in asex case these two El curves are called bn24 and grumpkin um and so we have a bunch of b54 operations we need to do we'd rather do them on the grumpkin curve because it's really efficient so how do we we how do we do

that well the idea is you have this bn24 commitment to all the stuff you have to do what the prba does is they just magic out of thin air a commitment over the grumpkin curve to the same information and then you need to do two things one you need to prove that the commitments are commitments to the same information and two you need to prove and then you need to actually prove that the elliptic curve operations are correct over the grumpkin curve that second part is what we we have a circle called the elliptic curve virtual machine because it is the world's most um uni bespoke um artisanal virtue machine because it only does elliptic curve operations and nothing else uh that part is very efficient because now you're working with the grum con curve so B and 254 operations are really really cheap that's great lovely

but how do you prove the commitments for the same well that's fairly straightforward we have this thing called a translation circuit I say it straight forward because I didn't write it but uh yeah that chaper over there wrote it so he might have a different opinion um uh wait yeah there um so two minutes okay good good so in the translator circuit we basically so you got these two po commitments one of a b one of grum can use a a regular bog standard Normy polinomial commitment scheme in over the grumpkin curve to open your polinomial at a random Point evaluate them and then what you want to do is for the B&T commitment you want to pretend that they're grumpkin commitments you want to you want to imagine what it's like to be a commitment over the grumpkin curve and

pretend that you are one and then using emulated field arithmetic evaluate the information in committed to in the B and 2x4 curve um evaluate as if they were coefficients of a grum polinomial and that's actually relatively easy to do you just create a snar circuit that does some nonnative field arithmetic um uh to do that that step and what it effectively does is it translates non-native eliptic curve group operations scal models into a constant small number of non-native field operations which is a uh concretely ASM totically better um uh thing to do um like Asm can prove it it's less work um I think it's like by like um like something related to the security par of

the curve anyway it's very efficient really efficient it means that we can recurse in about 12,000 Gates and that's not even very optimized so um we're talking milliseconds there it's really good uh and so this is the the full completed thing um I did not make this diagram it's far too good for me uh this is one my colleague Mara um who did it but the idea here is you have um you have F and you have G so G is basically um uh elliptic curve operations over the grumpkin curve is it and F is basic it's your accumulated folding instance the as you're folding as you're folding as you're folding what you're doing is you are my L Point yeah um as you're as you're folding folding

folding folding folding you are um adding more information into this list of elliptic curve operations you're growing this list um and then um you uh uh basically you you kind of deal with this by creating these elliptic curve virtual machine and translator proofs um and so basically the output of an Aztec user transaction is the um proof of correctness for all of this IVC stuff which is where all the real logic of what you're doing is encoded and then these two proofs isvm and translator um so um yeah it's pretty efficient uh at least it's efficient on the client side verifying this stuff on the service server is uh less less so but we're working on that it's not really a big problem because we have a lot of resources at play there and so yeah that's basically a very brief um

overview of mega mega honk um papers coming out soon thank you for listening if you want to get in touch um join the Discord uh look at the road map look at our research um download Noir tinco around and yeah thank you very much for [Applause] listening all righty we have some time for questions does anyone have any questions okay how's it going thanks for the talk um just to uh check whether you're aware the idea of Shifting um a a polinomial on the cube um is is is solved um yeah

yeah yeah yeah that's why we use that's why we use some checks now but back in the day it wasn't a solve problem like you go back three four years okay yeah cool yeah any other questions okay thank you again Zach