SNARK Light Clients

foreign [Music] and this is John and we're going to be talking about succinct verification of consensus as um and we're part of succinct labs okay so let's just start with the super high overview of the multi-chain and costume landscape so in the past few years a bunch of different l1s and l2s and app chains have come online and they all lie on very different points of the trade-off curve in terms of decentralization security transaction cost and throughput but basically as the number of applications on these different l1s and l2s has increased uh it's important that users are able to interact between these different applications and in this future in the multi-chain future Bridges have become critical infrastructure to make blockchains interoperable it's really important that users funds and assets are not siled in one ecosystem and they can interact with all the applications that they want to interact with in a seamless manner for the best user experience so bridges are really important um and so let's talk a little bit about what Bridges look like today so today most L1 bridges are built with multi-cigs or off-chain oracles and so the high level design is you have a multi-sig run by a centralized entity that watches for deposits on one chain and then we'll sign off on withdrawals on another chain and these multi-sig designs are generally pretty bad for a lot of reasons so they're you know sensorable they're not permissionless they're very centralized and they're actually you know empirically have been very insecure and there's been many such Bridge hacks uh and I would argue that these Bridge hacks are not only bad for the users who've lost billions of dollars of funds but they're actually broadly bad for the entire space it reduces The credibility of the entire space and then leads to severe Downstream consequences like regulation okay so that's kind of like an overview of the current problem and so let's start talking about Solutions so what does a maximally secure and Trust minimized bridge look like between l1s well we already have a mechanism for a decentralized group of people to come to agreement on the state of a chain that's called the consensus protocol and so the key idea here very simply is that bridge security should be based on the same mechanisms that validators already use to agree on state which is verification of consensus so if you're able to verify the consensus of a source chain in the execution layer of our Target chain then in a trust minimized way you can know the state of the source chain without having a centralized intermediary like a multi-sig that has to sign off on what the state of a source chain looks like so now that Uma has painted a picture of why these proof-based uh proof of consensus based Bridges make a lot of sense let's think from a high level overview what implementing the system end to end might look like so it means that we have some blockchain like ethereum and over the course of its lifetime it's naturally producing information about its consensus such as block headers validator signatures attestations and other important metadata and normally the peer-to-peer network of ethereum would broadcast and gossip this information to all the other honest validators and these validators will also verify the consensus algorithm but what if instead of just broadcasting this information to other honest validators we broadcast this information to a Smart contract on the execution layer of another chain which will re-implement the honest validator's logic the reason why this is so powerful is that if we can verify the consensus algorithm in a smart contract that means we can essentially run a like client on chain and this means that essentially we can trustlessly access any state from The Source Chain by simply providing a Merkle proof proves the inclusion of some sort of data and inside these block headers we have access to basically commitments to the entire state of the source chain such as like you know how much eth I have in my wallet um what transactions were sent in the past and what events were emitted in contracts and essentially we can access all this state with just a simple Merkel proof If we have this like client running on chain so the question is why hasn't anyone done this before and the big problem especially with these proof of stake based blockchains is that verifying the consensus algorithm is really expensive and in particular with ethereum the challenge is that the validator set is so large there's over 400 000 validators and to run this verification of consensus you have to keep track of all 400 000 validators their public Keys how much they've staked whether some new validators have came in whether old Auditors have unbought in their stake and this is quite difficult to implement a contract in a gas efficient way the second problem is that the signature scheme used by ethereums to Beacon chain is the signature schemina as BLS and unfortunately the elliptic curve needed to compute the signature is not currently supported by the execution layer on many evm blockchains so even outside the context where we want to do this in a smart contract basically running a like client from for a proof of stake blockchain like ethereum is just ridiculously expensive even on like consumer Hardware like iPhones or laptops which is why the consensus folks essentially implemented a specific consensus algorithm for like clients and this protocol is known as the sync committee so essentially instead of verifying consensus against 400 000 validators the sync committee reduces this problem down to listening to the signatures of 512 validators which are randomly chosen every 27 hours and it works exactly as how you'd imagine essentially these validators will sign every block and if enough values sign up from the Block you know the block is Justified and after some finalization rules the block is also considered finalized and obviously at the cost of being much cheaper to verify the sync committee uh sync committee provides much weaker security guarantees and it requires a two-thirds honesty assumption however we originally explored the possibility of verifying this like client protocol on chain and what we found is that even in this scenario where there's only 500 to validators actually verifying this consensus on chain is still too expensive so as do concrete reasons why it's too expensive it has to do with the fact that you still have to store 512 of these public keys on chain and you have to rotate them every 27 hours and storing a state on chain is still very expensive furthermore like I said before the current evm doesn't support a pre-compiles for the specific elliptic curve you needed to verify these signature schemes which means that we have to implement you know this this elliptic curve natively in solidity and in terms of gas costs this is also probably expensive so our key Insight basically is you know you know to implement the honest validators Logic on chain is obviously a super competition expensive task but what we have available to us is the power of zero knowledge proofs which have this magical property of succinctness which basically means that for any arbitrary long computation we can generate a succinct proof which can be verified on chain so essentially you know the code in solidity is going to look something like this where we have some function that validates a new block and you know obviously you have some pre-processing step you have some step to verify that the current validator set is valid and that we rotate the stakes and whatnot and then finally of course we have to verify this be these BLS signatures and as I've mentioned in these previous slides I've talked a lot about how verifying the vouchers that and verifying these BL signatures is quite expensive but what we can do is we can just compute a ZK proof that does these two expensive operations off chain and instead on chain we just implement the same function but we swap out these two expensive Parts with just the verification of this narc which will verifiably prove that we computed those things correctly and I think this is really exciting because this is just this is a framework that generalizes outside of like this ethereum sync committee and can be generalized to other blockchains to basically make it very easy to verify the consensus algorithm in the state of other blockchains in any execution layer that supports the opcode for verifying ZK proofs and I think in the same way that ZK is being used to scale like the throughput of blockchains um this is really exciting because it's showing that we can now scale the verification of these consensus algorithms and yeah for these reasons we're trying to coin this term called proof of consensus we're essentially trying to build these Bridges which use ZK snarks to generate a validity proof of the state of some blockchain and yeah we believe that these things these things called succinct line clients will be sort of the end game for cross-chain interoperability between many different ecosystems okay so John gave a really great overview of you know how we're going to use snarks to make these succinct like clients so now I'll talk more about the details of how we did this for the ethereum sync committee so as John mentioned the sync committee does two things one is for every single block header the 512 validators will sign that header and they'll produce an aggregate BLS signature of the particular block header and then the other thing they'll do is they have to sign off on the new sync committee that gets rotated every 27 hours and it's really important the validators in the sync committee get rotated every so often for like security reasons and like making making sure that set is decentralized ETC so we actually have two different snarks so one snark verifies an aggregate BLS signature of a particular block header and make sure that like the signature is coming from the set of validators in the sync committee so every block header that we want to have accessible in the execution layer of the other chain uh we need to generate a proof that this BLS signature was like actually verified for that header and we have to send that to the like client contract on the different chain and then once every 27 hours we have to generate another proof that will update the sync committee validators and set the new validator set that we're going to verify against so we have two different snarks so without going into too much detail but to kind of cover some of the Primitives that we had to build uh to produce those snarks that I mentioned on the previous slide we used a program called cross 16 and we used the programming language circom invented by Jordy and his team at item three and so our suite of circuits was pretty complicated and resulted in over 70 million constraints which is one of the largest circuits that we've heard of uh being used at least in surcom and so some of the Primitives we had to build were a public key Edition and aggregate verification so you basically have to add up all the validator public keys to produce an aggregate public key we also had to implement verification of the block headers so this involved implementing pairing in a snark and then having the pairing check the BLS signature which we other collaborators at Xerox Park Yi and Jonathan and Vincent uh worked on and then we also have to implement uh serialization methods to basically check that these public keys are actually being are actually like the correct public keys so we implement the SSD serialization that two uses which is a Shaw hash function basically and then we also had to implement Poseidon commitments to a vector of public Keys which is a snark-friendly hash function and there's one trick that we use that actually helped us significantly save on gas costs of storing public keys so I'll go into that a little bit because I think it's pretty interesting so at a high level snarks have public and private inputs so the public inputs are in red because they're bad because if we have to if we have to verify a proof on chain then the public inputs means we also have to put that data on chain which is expensive private inputs are transparent like we don't need to put them on chain when we're verifying this proof so if we were to implement the verification snark we would have all the public Keys as a public input because we need to make sure the public Keys correspond to the correct validator set unfortunately storing public keys on chain is really expensive so our idea was we could store to the public Keys instead so we can store the public Keys as a private input in the snark as you can see here it turns into green and then the public input becomes this commitment which is basically like a hash of the public keys and it's like much shorter but then the question is how do we update the commitment once the committee rotates so one idea is that when the current sync committee is signing the rotation of the new sync committee they basically sign an SSD which is this eth2 serialization they use of the new public keys and so we could just use this SSD serialization of the new public Keys as the commitment but the problem is ssds really snark unfriendly uh because it's a bunch of Shaw hashes so it's really expensive to compute in every header verification snark and so what we our idea was what we could do is we could map this snark unfriendly SSD to a snark-friendly commitment and so our second snark that I mentioned below for the sync committee rotation basically Maps it takes in the public keys and then it produces the SSD commitment and then also produces a snark friendly commitment called a Poseidon commitment and then it just asserts that those two things are the same and the bottom line is that we were able to save around 70 million constraints in our header verification snark which we run every update that we want which is like a huge savings in terms of proving time and just for some benchmarks so our sync committee rotation snark has the SSD computation so that's why it has 68 million constraints which is quite a lot uh thankfully the proving time uh is not that bad it's four minutes and that's the snark we run every 27 hours and then we have another that's verifying the signed header that has around 20 million constraints and it's proving times also around four minutes yeah so everything that me anduma have we've described here we have like working prototypes of it and we actually built a two-way like client bridge between gorily and gnosis chain which is actually um another L1 which implements ethereum because that's exactly so we're able to reuse many of our circuits so we have a demo demo succinct XYZ and fair warning it's in beta and it works much better on your laptop but here we have some screenshots of like what it can do so basically you know you choose your networks right now we only have like one pair obviously and you choose your currency and yeah you can just Bridge the tokens you send a deposit transaction and essentially what's going on behind the scenes here is quite interesting so when you make your deposit transaction it basically stores some data on some contract on corally that indicates that you've made a deposit and what you have to wait for is essentially for the like client on the target chain gnosis in this case to be updated with a block header that can now reflect your new deposit so you're going to wait for the finalization of an ethereum block which is around 12 minutes and on top of that you're gonna have to wait for our proving time which is right now is three minutes and after that period we can send a transaction to the like client to update it to the latest block header and then to initiate your withdrawal transaction essentially you have to provide a Merkle proof proving that you made a deposit on Gorly and this basically this merkelproof will essentially unlock funds on the target chain and you can see yeah over after some time like the top emoji becomes like green check mark and uh yeah yeah so yeah to zoom out a bit I want to take some time to compare what the trade-offs are between you know this proof-based bridge versus the bridges that exist today because I think they very much um exist at different trade-off points and I think they have different use cases so with these proof-based Bridges you know obviously the really big benefits are that there's much higher security guarantees you know assuming that the ZK uh Stark security is fine essentially you're able to borrow security directly from the source chain which I think is something really powerful and that many of the existing methods don't have at all another property is that because we don't have any additional trust assumptions besides trusting the l1's validators um this this protocol can be very permissionless and censorship resistant because theoretically anyone can be running the operator that generates the proofs and anyone can be updating the like clients and yeah for these reasons it's much more permissive than jcentralized now the cons are I think you might imagine is that you know verifying this ZK snark proof is much more expensive than verifying you know a threshold signature scheme that a multi-sigma implement but thankfully with like graph 16 and stuff we expect that the verification cost will be around 300K gas and obviously another con is that you have to wait for the proof generation time and in our case you know our circuits we didn't spend that much time optimizing them but you know right now it's three minutes and I think in the context of ethereum this is okay because the finalization period is already so long but for other consensus protocols you know you might want to have a much faster proving uh proving time and that's something you could probably fix by using your generation improving systems and many of the techniques that a lot of the zkv and people are exploring actually furthermore another challenge with this approach compared to multi-sync approach is that for every new chain you want to adopt or a new L1 or even when a consensus algorithm on ethereum changes you sort of have to rebuild the circuit and you have to like kind of hand design these snarks to verify the consensus algorithm and I think from the developer's perspective this can mean that onboarding new chains can be quite difficult so in terms of our roadmap we're trying to take what we currently built for ethereum to production and I think our end goal is essentially to be this like trust minimized entropy layer for ethereum and other decentralized palette forms and we want this to all be powered by proof of consensus and adopting these values of decentralization and permissionlessness and I think in the future the two things we're really excited about is building these succinct line Titans for other blockchain ecosystems and also exploring these new approving systems to decrease the proving time significantly and yeah finally we wanted to give a big shout out to gnosis Dao who originally funded this work and super um were super helpful and also Xerox Park um where we worked uh for the summer and the community provide us a lot of support and help thank you