ZK11: ZK Consensus: One Proof to Rule Them All - Calum Moore

Transcript

[Music] so I just did a little bit of background about me um I'm the CTO and co-founder of pay pay is a payments app so I think crypto venmo um but it's for private payments so uh we built uh in order to achieve that we actually had to build the phone app wallet and the network uh because there wasn't a uh private Network that we could use that was in mainnet uh so we deployed our first uh we deployed the first mnet ZK ZK rollup uh it's a validium roll up so that means um we just post the root hash onto ethereum or the L1 um and it's a ZK ZK

roll up which is kind of like a play on uh the fact that most ZK is used for scaling and not for privacy I think I actually stole that from Aztec so thanks um and uh one of the things that's really important for us uh we believe that to onboard the next billion people into crypto you need to be using uh a device that the next billion people are using and that's a mobile device uh and so we work really hard to get uh proof generation on the phone um and we worked on the constraints to get uh the proof generation on an iOS device uh down to one second uh so um that's just a bit of context about us CU it's kind

of going to make sense throughout the talk I'm going to kind of referencing uh that architecture so as I've kind of already talked about like there's been a lot of use for ZK for scaling uh and that's great um but we're starting to see ZK be used for privacy which I think you know that's the actual zero knowledge part um and I think the real end game is if we can actually use ZK for consensus because then we really can have a single proof that could summarize the whole network um so what do we have today well uh this is our architecture but it's fairly similar to uh an L you know any L2 architecture that you might see um with the exception that we do all the proofs on the client on the mobile

device so the transaction proof is sent to the sequencer the sequencer can't see any of the details of the transactions just that there's a proof and that it must be valid uh the sequencer combines uh or orders the transactions and then it sends it to the prover and we get a proof that is sent to the L1 as I said we're a validium so uh the proof will just be a single hash with the the proof uh with a single hash uh and then this is how it looks over time so as I said you have the sequencer it's doing lots of blocks uh but every so often we prove it and then we send it to the L1 but as you can see there's kind of a long delay between each of the rollups and that's because

it's super expensive to verify uh on ethereum if we do it too frequently um and we and so what we want to do is we want to provide some soft finality uh in between um rolling up to the L1 and and to do that we need consensus um so we actually implemented a consensus for our sequencer so it's a decentralized sequencer uh we actually use the Hot Stuff protocol for that um now we could have just gone the centralized route like uh is quite common with uh rollups um but I think the industry as a whole we need to move rollups into being a more decentralized uh entity um for obvious reasons that if it's not decentralized

uh then it's not censorship resistant um and if it's uh not decentralized then if the project stops going then the sequencer will most likely die uh and the project uh and the protocol will die with it um but the challenge with having a decentralized sequencer is we have to provide all of these signatures to the L1 because we need to kind of prove as part of the consensus okay this was a sequence of transactions that's valid uh as well as this is the proof for those valid transactions uh so what's the problem with sending signatures to ethereum uh well it's not a massive problem no it is a massive problem that's the whole point

of this slide uh so uh it's expensive to verify uh signatures it's about 3K gas per signature uh doesn't sound too bad but then when you have 100 validators that's 100 signatures that's 300K gas that's that's already more expensive than what it costs to verify as ZK proof um it limits the number of validators that you can actually have on the network because there's a hard limit of the transaction size that you can have for ethereum so that now we have a hard limit on the number of validators we can have we can never have more than you know we could never get to a million validators um clients have to download a lot of blocks to confirm soft finality so on the previous slide I talked about the soft finality of basically between

the rollups we want to provide some final otherwise it would take an hour to process a transaction um but if you've got a mobile device and you're coming online offline uh then you have to download all the blocks in between when you last came online um and so we want to try and avoid that and we want to try and give them a proof instead where they can be really up to date as quickly as possible uh oh yeah I should probably put this at the top but uh reduce security um because we're only providing the signatures for the last block obviously with consensus if you sign the block you signing all previous blocks um but it would be much better if we could actually have proof of every single signature uh for all blocks um as part

of the rollup okay so hopefully you agree we want to ZK the consensus uh because otherwise the rest of this talk will not work um so consensus proof requirements so what do we actually need from our consensus proof um what do we want the ZK to do well uh each validator will create a signature proof that kind of already happens as part of the consensus um we need to aggregate those signatures into a single proof otherwise it would be just as expensive to just send all the ZK signatures um we need to the proof size to be small um we want it to be small because again in a network environment if we've got mobile devices uh but just generally uh Network

bandwidth can be a big problem if the proof sizes are large um and we also want to verify on ethereum uh so we don't want a huge proof because then it's really tricky to do that um but the pro time can be a little bit longer because we were already proving the state transitions uh because we're a ZK rollup that's what we do we we we prove the state transitions already so we just need to do it at the same time we're doing that process um we need to ensure that the stake for all aggregated signature proofs is more than 2/3 that's just basic consensus stuff uh we need to make sure that we have 2/3 consensus uh and we need to make sure that each stake is only counted once um if we are doing if we're aggregating all these

proofs together the idea is to lose some information information we don't need to keep around uh but we don't want to lose the fact that someone's already we've already aggregated a signature in otherwise someone could just keep adding their signature and and take over the network okay so the first thing we need to do is think about signature orchestration so like how would the actual proof Construction or or uh system work so as I said we've got the validators they're creating their signature proofs and then we're going to have a layer on top which is going to aggregate those signature proofs uh and then you could have like n number of layers on top uh in this example I'm kind of showing uh we would do like four into one so we'd aggregate four

signature proofs into one uh aggregation proof we could do that on multiple levels um so if you look at how quickly we could have a lot of pro Ro aggregated if you have four levels that's 256 signatures aggregated if you have eight levels it's like 65k uh and then for uh 10 levels uh it would be a million so we can really quickly like a million signatures there kind of ethereum level signature aggregation for just 10 levels of aggregation um the this this orchestration is actually probably one of the harder challenges which is actually nothing to do with the ZK part is like how do you actually ensure that

all of these nodes because these different aggregation proofs would be assigned to different nodes on the network you'd need to have redundancy You' need to do it in a decentralized way to ensure that uh that if someone decides they're not going to produce the aggregation proof that there's a redundancy and a backup and an incentive for them to do that but let's just assume that is in place um because otherwise this uh would be Talk would be twice as long um okay so the signature proof what does that look like well uh actually we could just do a normal signature but we could actually do the signature proof in ZK uh because one of the cool things about ZKA is if you pass in a private key to a proof you effectively just create a signature um so what we're going to do is just going

to quickly witness the state hash and the stake so the state hash would be like the root of all state of the transactions that we're looking to add to the blockchain so uh if someone's made sent someone some money the state hash would change and that's what we're trying to verify uh we also need to witness the stake because that's uh going to be important later when we're adding up all the Stak to make sure we're over 2/3 uh if we take the private key and the private key is obviously going to be putting as a private input oh yeah so the blue here that's public inputs and the pink is private inputs into the proof If we compute a hash of the private key uh that will give us what we could deem an address or um represents

that private key um and then we can just constrain that address to be the same as a computed address and then we have something that looks kind of similar to a signature so in a traditional signature the state hash and the stake would be the message uh and then the address is basically the proof that only the person with that private key could ever create this proof uh which is a signature um the really cool thing about this proof is that it's 2 to the six constraints which is like nuts uh that's 64 constraints uh to do a signature proof um and so obviously it takes like no time at all to create this proof uh and the proof size is Tiny by the way we use

uh Halo 2 uh for all of our proofs um so this I wrote these all these proofs in Halo 2 um so just bear that in mind if it makes it'll probably make more sense on the next slide uh so uh yeah these are our signature proofs and then we want to aggregate them together uh I chose to aggregate four signature proofs together at a time um the again because we're using Halo 2 uh you basically need to play around with the number of proofs that you aggregate together because if you were for example aggregate five together the the time would like ex like double so you basically don't want to go over the

and need an extra advice column or you don't want to need to have to uh add more like a new set of constraints because basically it's like if you if you go over by one you pay the cost of going over by a lot um okay so this proof is going to be a lot more complex than the other one uh because we need to prove quite a few things but ultimately we're just trying to reduce our four proofs into one proof um and update um and keep track of some things along the way uh so obviously first thing we want to do is we want to verify uh the uh signature proof that we've been provided this is this is going to be for each of the proofs that we have the each of the four

proofs we need to verify the signature proof um and that gives us verified inputs within the ZK circuit um there's actually within Halo 2 there's a chip so chip in in Halo 2 is basically a module uh think of it like any Library like it has like pluggable modules you can use um so there's actually one that already exists for that which is great so you can kind of verify a proof inside a proof um we're checking that the state hash is equal to the verifi the the proof State hash because we're going to comine those four state hashes into one so we just need to make sure that all those proofs are stay in the same state hash and then we that's one way that we're reducing the amount of information that we need to

keep around right so before we had four state hashes as inputs because we had four proofs and now we're only going to have one state hash uh output um we need to verify the validator is in the validator set that makes sense right like want some random node just being like hey like aggregate this proof for me I'm not I'm I'm just a random node uh and to do that we need uh to have some kind of Merkel tree to keep track of things right and that was one of the key requirements is like how do I keep track of who has already signed a transaction um we're going to use a sparse mle tree because this is my favorite type of Merkle tree if you're allowed to have a favorite Merkle tree uh I just think they're really beautiful um so um don't tell oh this is recorded

okay um so I'm going to give like a really quick intro into this this type of merel tree uh just because it's not as as common as some of the other types of Mer tree so let's say I want to insert two into the Merkle tree uh I do some binary decomposition this is what two represents uh here's my Merkel tree where do I put this number two in the Merkel tree this is a two bit Merkle tree uh well what you can actually do with a spar tree is you can use the binary decomposition to know where in the tree the node should go so here it's going right and then because it's a zero it's going left and okay this is my location in the Merkel tree great uh and you can also insert values that are larger than the Merkel tree so this is a

three bit value but I'm trying to insert it into a two bit tree well that's fine just drop the first value this can lead to conflicts because obviously as you can see two and six would go into the same place in the tree and so you just need to figure out like is that is that important to you and we'll come back to whether that's important but if you try and insert values larger um than it is the size of the tree then you you can run into conflicts if your tree is 160 bits uh you're very even if you've got a 254 bit element so a much larger element you're not really going to run into conflicts whereas if you've got a smaller tree then you you definitely are uh so how do we prove inclusion in a spar Merkel tree well we take the

siblings we calculate the hashes and Bam you have proof of inclusion uh but what's really cool again about sparse M Tre is this is unique well not only Spar mle trees but this is one of the defining characteristics of The Spar Merkle tree is that you can prove exclusion so it can prove something's not in the tree uh and that's really important as we'll see why in a sec but it's basically you're just proving that that value at that slot is zero so it's the same proof construction um and then if you want to prove insertion well it's a combination of proving first that it wasn't in the tree and then proving that now it is in the tree and so you have the old hash would have to equal uh the the the exclusion proof uh and the new H

the new hash of the tree would equal the inclusion proof once you've included it okay so now we know we need a spar merry to uh identify uh whether our validator is in the validator set that's one of the key things we wanted to do uh the other key thing we want to do is we want to prevent a signature being uh added multiple times uh and so we'll use the same Merkel tree for both of these things because it's just more efficient to use one tree uh I'm going to use a 64- bit Merkel tree um and so that is quite a small uh Merk tree but I'm not so worried about conflicts because the validator set potentially doesn't change that often and we can we can handle

conflicts by just adding a nons um so that's not a problem for us in this in this particular case um each nonempty Leaf holds a hash so this is basically what does it mean to have a hash in the tree uh there'd be some kind of type to differentiate between whether it's a validator hash or a nullifier hash uh and then the address in the stake so if it if if we just put a one in there then it's a validator set if we put a two in there it's a nullifier um okay um so what I'm going to do is so I've got the validator leaf here um creating the leaf this is to prove that the validator is in this the validator set I'm going to do some bi

decomposition because I remember we need to do that for a spar Merkel tree and then we're going to calculate a rout um again there's a chip for this available we actually use a modified version inside of uh pay but there is one available publicly um we check that that equals the old rout um and then we're good um and then we do the same thing we're going to check that we're going to basically create a new route uh with a nullifier signature so uh we know that like if that nullifier is inserted and this new route if we use this new route then no one can reinsert the same one uh multiple times uh and again it's the same process but we've changed the type to two and then this time we're going to check uh that the value the signature

wasn't in the in the tree and then later we're going to check it is now in the tree and then this is the new route and then we're going to con uh uh I don't think I added this but you would want to oh I think I added it later you would constrain the new route to be that uh that new route is basically the new route that we're uh constraining um so then we have the stake uh bits we do some D B decomposition on that because we need to do a we need to check that the stake bits are less than the maximum field element uh because if if someone puts usually your element your field element is like 254 bits but a value could be 256 bit and so someone can basically just uh hack your network by providing a bigger um a bigger value than the the

because it's a modulus it would just reset and you could basically choose any stake value so we have to check that the stake bits is less than the maximum field element uh less sign is really hard in a snar circuit you basically have to line up two values with each of the bits lined up and then you go from the big big uh big endian and you go through and you check like is this a zero and this is zero okay move to next one and if you hit a one and a zero you know that that the first value is bigger than the other value so that's kind of uh how you do it again we wrote a chip to do that for us um and then we want to constrain um the sum so we want to sum up all of the proof uh uh stake uh and

then constrain the new route uh that we're outputting to be the last new route that that was in this for each thing so we're basically going old root new route and then and then the the new route for the last proof is the old route for the next proof so it kind of like links along um so there we have the signature aggregation proof um uh oh I didn't uh yeah so it's it's a little bit um say two to 21 constraints um so it's it's quite a big proof in CPU when I wrote this circuit it took 135 seconds on my laptop um in GP if we run it on G we could at least get it down to

like 30 seconds I think we could get it down to even less than that um and the proof size is a little bit larger but it's still within what we need so then finally what we want to do is a consensus proof uh we want to combine all those things together um and to do that we need to verify these two proofs so I haven't gone over the total stake proof but basically we'd want to have some way to go through the the validat set merkal tree calculate the entire um stake on the in the network and generate a proof and we could reuse as long as the validat set didn't change we could just reuse this proof every time and then the signature proof uh is the is the the output of the aggregation proof that we just

did um so uh we have the we're verifying the state hash and then we're saying that the validator set route should be the old Route um which is this is the very first route um that we used um and then we want to make sure again like we're doing a uh a less uh the signature stake is bigger than the two3 stakes so we again use the same chip for that um and then we want to verify uh the block proposal which I haven't covered here again like you'd want to make sure that the block proposal producing the block was actually the valid one again limited time so I didn't write a proof for that one um but we could do that so uh the old proof just

took reiterate that point like the old proof for this first okay it's not working okay but the old proof right on the far left would be the original validator set with no signatures in it and the far right route would be the new route um and then if you the for the consensus proof you would have like the old route would be the validator set and uh the new root would be the new one uh so this is how our roller works today we have the transaction proofs generated on the client we have the execution proof which does the state transition and then we send that with the signatures to the evm so uh how do we uh add the consensus

proof so we can have one proof to rule them all um well we take the transaction proofs uh these are the same uh we add the consensus proof with the new state hash uh we add it to a the final proof where we aggregate them all together and then uh we have we can send that to the evm and we can also send that to clients because they can verify uh uh that all together so that is one proof to rule them all uh any questions [Applause] okay uh yeah we use hot

I can repeat the question as well maybe I think the question was which consensus do you use so we currently use Hot Stuff consensus uh it's basically a uh the next iteration of like tender Min um nice thing about it is it has like quite hard finality so you can kind of be not just generating proof and then having to revert and redo all the proofs which would be very complex particularly as I said the orchestration uh is one of the hardest components to this so they want to kind of make sure that that's done correctly the back anyone raise your hands again uh uh sorry maybe I missed this in your

presentation uh I I understand the validation of the stake uh but whenever the committee changes like I missed that part like do you need to uh is there like drawing from a distribution to select a new committee or like how do do you change the how do you change the validator set yeah yeah so the validator set would be a Merkle tree so you do a very similar thing to what I just you know when I showed the sparse Merkel tree again I didn't show it as a natural diagram but you'd have a proof which would basically say okay we want to change the validator set and again you'd have to have some additional logic but you'd probably do that VI ethereum right so uh you'd have like the validator to to become a validator you would submit a transaction to ethereum

that would have a proof of the new validator set hash and at the same time as doing that you would check that you received money in to cover the balance of that stake um kind of similar to how we do the minting process right now so when you mint money onto the platform you basically send in usdc and we we include that in in the state hash sorry but then if I if I want to verify your uh your proof to rule them all I still need to use ethereum uh for some public inputs you You' only need ethereum when you're adding so you need just need to check the state hash or the the validator set hash in ethereum yes okay so I still need to every now and then I need to connect to ethereum pick the new

uh validator set and then I can use it for a stretch of time to verify your proof uh yes so I mean you could you could do it all in ZK and not have but we're in L2 and we borrow some of the security from ethereum so it makes sense for us to do it that in ethereum but technically speaking yes you could write one proof that was literally just a proof and you could have it as just just everything if you had You' basically have to add the staking logic to part of your state logic so that like you're you're applying that if that makes sense right that you're applying that to it thank you right let's let's do two more I'll get you if I understand correctly the

validator set is a point to decentralization yes is a point of what to to to to decentralize everything so as large the validator set is this is the de decentralization that I have right correct so uh what is the limitation the upper bound to the uh validator set how many validators could you have yes uh I mean I showed a million as an example you'd need 10 phases of aggregation for a million validators which would be around ethereum level mhm um but you could have an infinite number There's No Limit I mean your your issue would then be like

the consensus protocol it would have to be able to handle that many validators and so that's more on the like purely which consensus algorithm you use like hot stuff would struggle with a million validators um but the um Casper which ethereum uses does not so again depends on the consensus algorithm that you use H but the proving time will be affected to two right I go yeah so 10 10 levels of aggregation could be done in like 3 minutes mhm so it's not too bad thank you all right let's let's have the next speaker set up while we take the last question yeah uh so is the proof

aggregation inherently necessary uh for the scheme or is it mostly because it allows you to massively parallelized so alternatively uh one way to phrase it rephrase it would be uh if you had like a different proof system right which didn't truly support aggregation of proofs that well but had like a better end to end proving time uh for you right uh would that you know uh sort of like come up short or yeah yeah you could you could just have um one Prov just going through and aggregating them all into one proof you would have the proof would be massive so the proof size would increase um so you'd have to handle that situation and then you wouldn't be able to paralyze it so that would be the other issue with it um so yeah I think those would be the challenges but you

definitely could do that okay let's thank the speaker again