ZK10: Pathway to Scalable Recursive Finality Proofs - Nicolas Ramsrud

Transcript

[Music] hi everyone my name is Nicholas ramud I am uh one of the co-founders of an interoperability layer called wrinkle and I'm going to be talking about a slice of what we're working on in creating scalable recursive finality proofs and and Lord help me this is like an hour long talk in in 10 minutes so be with me okay so what are we what exactly is our goal here so our goal is to create succinctly verified proof of finality for a given consensus mechanism in comparable times to network progression now why would we want to do this this is a it sounds painful um so it really comes down to the core problem

of interoperability which is enabling smart contracts to verify external data from external domains in in this case speaking specifically for blockchains so what's the optimal result here well it would be to enable Smart contracts to run their own full node but that doesn't exactly work right you can't do that and so what normally is done is to offload this verification offchain uh which introduces trust we try to reduce that risk by decentralization um but it's been with the Advent of of snarks that have opened this door to to reducing trust in these systems by verifying some artifact of consensus right whether that that

artifact results in a verifiable light node where securi in between a multisig and a fullprof of consensus or to the far end of security where you look to encapsulate the consensus mechanism in a snark which gives you data verifiability uh with no additional trust assumptions so I'd love to dive into what consensus looks like and finality looks like uh but for the sake of time we'll just talk about ethereum at a very high level so one proof of finality is uh a proof of 248 aggregate BLS signatures containing uh over or around 800,000 validators and doing that in six minutes time that is uh really awful but importantly verifying consensus

finality is not just verifying signatures it's also verifying there that there are the right signatures so these are other proofs that we have to do on top of this to get the real Economic Security but for for the sake of time we'll just talk about the the hard part about doing this which is the signature verification okay so if your if your first thought is to uh just just Brute Force this thing constrain arithmetization in R1 CS is 22.5 million constraints which means an Epoch is 46 billion constraints uh yeah oof uh that's that doesn't really work so you can see here that that even at this

level we're we're three orders of magnitude out of the range of practicality so that doesn't work but instead can we take advantage of some of the recursive structure inherent in the consensus protocol where you have each one of these uh these these aggregate proofs running in parallel to make use of something like Nova to reduce the statement from the linear in size of the statement proof that was before to linear Pro work but in size of a single step and yes you can and you can actually extend that across the the epoch and and run those uh slot proofs in parallel folding to get your final Epoch proof here uh in doing so we we see in immediate Improvement an order of

magnitude Improvement at the slot level um but the real savings is at the epoch level and that's because you can run those slot proofs in parallel so can we take that parallelization down into the slots uh and that would be running instead of running these in a single chain Nova proof where everything is linear andn uh reducing these down to parallel instances uh and and and folding them together in a binary tree like fashion and that would reduce the total runtime to logarithmic in N uh in in practice uh that doesn't work out very well and that's because to do this you need to duplicate uh the the circuit as well as the setup for each one of

those instances which means that for our case this is a 12 GB circuit and a 50 GB setup which which means that you're you're trying to duplicate those in memory and so what you gain in parallelization you lose in memory and efficiency and you can see that uh you know we we actually killed our machine although it's a large machine killed it to trying to do the epoch proof um and so we did see logarithmic in N for smaller smaller set sizes like up to like 16 but then it returned to being linear after that so what are our takeaways well we need two orders of magnitude one to two orders of magnitude Improvement to achieve our practicality goal but this barrier is largely driven by the statement size so we can focus on

optimizations uh you know um custom Gates better folding schemes Etc but it's all going to be driven by that statement size or can we cheat so recall BLS signatures is this two- pairing check over this uh bilinear map and the signature scheme is defined over the group elements uh where for a verifying a list of signat feur you have this list which starts to kind of look like inner products over uh vectors of group elements right and if the message is all the same you can aggregate the signature down to a single one uh and move it over to the left- hand side and what results is actually something you can constrain and uh this actually is a a proof over

all of or proving the the aggregate signature over vectors of group elements in an inner product and this was actually this was actually first proposed by Benedict buns Mary merer at all in their uh paper proofs of inner product or inner pairing products um and so if we take this actually we can extend this across slots as well as Epoch because you're able to do this verification in batch over different messages as well so if we take this as our our proof construction what do we get well we reduce those 4,096 pairings down to a single pairing check with no witness generation no setup which means it's completely trustless it's memory efficient and fully parallelizable which

means it's totally computationally bound yeah so it looks good it feels good but but how good is it uh well it turns out we achieve our practicality goals we're able to generate slot and Epoch proofs in half of the time uh it takes for consensus to be reached um and since it's computationally bound we we also ran it on bare metal machine a 32 core bare metal machine and and saw fact an additional factor of two reduction which means a proof of those 248 aggregate signatures over a million signers in just about a minute okay so what's the catch well it's not a succinct verifier it's it takes 9 seconds to verify a proof of 248

signatures and it's because of these these two log n group Ops that the verifier needs to do in order to uh verify the proof and so we need a grth 16 wrapper if we're going to be using this on chain so we went ahead and did that so the one pairing check uh is is 11 million constraints looks good like we might actually get there no we don't and it's because those group operations just absolutely kill us and that's that's five five another 565 million constraints um and so this is kind of where we're at today and what we're working on is is optimizing these things and there's several paths um that that we're looking at but what's what's more important is the kind of convergence

towards layer 2 proving system design and achieving these uh you know large large proofs that are very computationally intensive that can be used on chain where you have structures of of pro or efficient proofs that are then compressed down and so what's next well I only told you about half of the the proof the other half is the set membership and majority proof that ends up having this a very similar structure that we presented before with a full holding scheme over individual proofs the set membership is a lookup argument and the majority proofs is several uh uh sum Che arguments and together those are then compressed down into a proof of finality

which can be used to uh validate data from ethereum outside of ethereum with the full Economic Security of ethereum so what does this have to do with wrinkle well it would be optimal to extend this proven system out to other blockchains right where we we establish a proof of finality or proof of consensus for other blockchains and blockchain types but doing so that would mean n proofs for end chains and pro validating those n proofs on those end chains individually so it's not it's not financially scalable and so since we're we're already doing this work to create a very efficient proof accumulation and compression layer we can extend those

proofs to merging those things down into a single proof of finality or proof of consensus and extend that across other state machines and state verification types to create one merged proof of finality and since that is not very extensible right you're that's going to take years to develop proofs of finality for all different consensus mechanisms and optimize them and audit them we introduce our own uh data consensus layer called the wrinkle layer which merges external states of blockchains into one state route as an attestation layer and in the same way that you produce a proof of consensus for other blockchains we produce one for the wrinkle layer which enables us to have a

single proof connecting all blockchains but since that introduces trust where we really don't want it right uh we we end up working continually working to move uh blockchains out of this proving layer right move them out as we generate those proofs of consensus into achieving a minimally trusted uh proof aggregation layer that ends up achieving kind of the end goal of this right which is kind of one proof to connect them all and in the darkness bind them uh so quickly heartfelt thanks to all those that have helped us along the way Stefano Taro and nirvan tiagi of

University of Washington they've given kind of pointed help that is that has given us and led to our step function improvements SHO uh not only for for Nova and the inspiration behind our proving system design but also some benchmarking help as well as Alf who um their code actually helped us with the the binary tree construction because we couldn't have done that alone uh and obviously all the Giants that we're building upon so if you're interested in connecting I know that was one heck of a data dump uh with a lot of information so if you want to talk later or uh connect to talk about help us build that is our website as well as my my Twitter where I post a lot of sorry X where I

post a lot of this uh stuff and the work that we're doing so thank you did I do [Applause] it okay any questions no yes great sorry if it's a very random question but I was wondering if you you've looked at um things like igon layer um to to see how this sort of I feel like there's some connection there of some sort yes that's right so so the the wrinkle attestation layer ultimately will continue to exist right even as we create consensus proofs because there will always be a need for some some

level of external verification right and that's a proof of stake Network and so we are working and have talked with igen layer to help bootstrap that as well as talking with with uh projects like B on so that because we're not rooted in any one ecosystem we can utilize kind of any any uh Network's core asset native asset as a stake in collateral awesome what is the killer application of finality proofs so it is it is in creating verifiable interoperability across chains with economic security right so right now it's really unclear what the level of security of a lot of the interoperability prot Protocols are

out there right even even in ZK light node designs there's no slashing conditions upon those uh signing sets and so trying to get to the point where we have interoperability across chains that is also economically secured so if you think you know sending sending your assets from one blockchain to another um that's verified on a state proof of ethereum a full finality proof that means that reverting that transaction would would cost validators you know upwards of $10 billion right so that is the ultimate goal also I believe uh not just bridging assets you could also build something

like bridging arbitrary data using this exactly right it is my my core belief that that in the future applications will be not only natively multi-chain but also um totally abstracted chains will be abstracted away from users right and so that requires a a base layer Foundation that is secure data transfer across chains and the only way to do it is with verifying the state of those blockchains externally cool thank you I think we should we have time for one more question if there in fact are any but I don't think so so thank you very much Nicholas thank

[Applause] you