ZK Paris: Kevin Jue - Recursive Proofs

Transcript

Okay, so uh next talk today is combining proof systems to push the limits of ZK by Kevin Jew at Six Sinct. Hey, so um my name is Kevin Jew and I'm an engineer at Six Sinct Labs. And today I will be talking about how we are combining proof systems to push limits of ZK.

So, quick background on Six Sinct. So, we're interested in exploring the ZK application space beyond uh the current main use cases. So, um mostly like, you know, ZK EVM uh and like private private transfers using uh projects like Tornado Cash. So, as part of that exploration, we pioneered um ZK light clients. And what that is is that we we are verifying consensus protocols efficiently in um the EVM.

So, uh here's kind of a illustrative example of what we're doing. Um we are taking uh so, we are basically uh uh building a uh we have a circuit that proves that um uh that verifies consensus. So, specifically the Ethereum light client consensus. And then uh the generated proof is then verified on um an execution chain uh that is EVM compatible. So, um basically what that does enables is that this proof kind of attests that um like these following headers are all valid.

So, here's a quick uh overview of our architecture. Um So the inputs into our prover is basically uh basically the artifacts of the Ethereum consensus protocol. Um So that includes like the aggregated signature, uh the block headers um that are mined, and the current validator set. Um so that is all input into the prover, and then what is outputted is uh the generated proof of um again attesting that uh the the block header is valid and the number of signatures.

So um uh that protocol is is uh it was earlier this uh this year was um released live on mainnet, and it can be um is accessible uh right now. Um so this enables a number of different use cases. Uh so one of them is uh basically sending arbitrary messages from Ethereum to any of our existing destination chains. Um uh and uh with that we can also uh we also enable um calling remote functions on Ethereum to again any of the any of the destination chains.

Another use case is um on these destination chains uh any smart contract can read uh the full Ethereum state. So it's essentially like an Ethereum uh data oracle. And another use case is um uh that we are bringing the the consensus data um onto uh the execution layer. Um so this is I mean in a sense like a consensus data data oracle. And again, this is because we're um using a SNARK to verify the light client protocol, this um this has the security of that protocol.

So um we don't want to just stop at Ethereum. Um we are uh very uh very much actively working on other consensus protocols. Um So, the ones that we're working on is is Tendermint, which is um uh is uh used uh mainly in Cosmos and as well as Grandpa and Babe consensus, and that is used uh within the Substrate SDK, which is um uh the SDK that's that's Polkadot is using. And eventually we plan to um uh do full Ethereum consensus. Um so, right now we are just doing the the light client uh Ethereum light client consensus, um but once we uh complete full Ethereum consensus, it

would provide even more security. So, um So, all of these consensus protocols have uh like very very similar um uh a very similar uh like parameters that they have to deal with. Um So, so one of them is, you know, obviously verifying signatures. Uh another is uh is calculating hashes of block headers. Um and then decoding like individual fields within the header.

Um and the and the general like pseudo code for all of these like consensus verification algorithms is like, you know, verifying the signature and making sure at least like a quorum or like a two-thirds of the validators have signed. Um proving the validator transition function. Um and then generally uh doing like Merkle proofs to uh uh prove like committed data uh within the header. So, in this talk, um I'm going to talk about how we're super supercharging ZK circuits to handle consensus protocols with a hundred like over a hundred thousand validators.

And here's a kind of quick outline of the um of the techniques that we're using. And then I'm going to touch a little bit at the end about some of our open source repos. All right. So so very very verifying validator signatures and hashes is is is embarrassingly embarrassingly repetitive repetitive and then parallelizable. So basically you know these like when we're verifying a number of like like signatures there's really no dependencies among this like set of computation.

The thing though is that circuit-based proof systems don't really take advantage of this kind of neat structure of this workload. So we asked if we can do if we can do this any better. So through that thought process we are thinking of bringing the SIMD computation computational model. And what is SIMD stands for single instruction multiple data. And and this computational model is actually already you know widely used in existing like devices. So like you know AVX instructions and GP GPUs.

But basically it is like doing you know computation on like doing computation on data that is very much independent and and doing the same like computation on each on pieces each pieces of that data. So to kind of try to implement this one this this computational model we we believe that STARKs is is a good like underlying proof system for it. And the reason is you know STARKs have a single state transition function over a set of registers.

And that generally makes it much more lightweight to prove and and has faster proving times than Plonk. Especially for again for this kind of repeated like structure. So we figured out a way to arithmetize these constraints within the stark and have built and like a abstraction that is very similar to to Simdi. And basically it is computing the the the same function over over independent inputs. You know XY and then like the computing the result Y1 to to to to YN.

So here's kind of a illustration of one of our existing stark circuits. So what what this is doing is doing basically number of 256 to be exact of of scalar multiplication which you know it's it's basically the most like expensive operation for instance signature verification. So so basically every row here you can think of it as a batch of rows of 256 rows.

And what we're doing here is that we are taking like like the elliptical curve point and then you know sending it to the first row of every batch. Then we are doing a bit composition of each scalar and then that's that that bit copy decomposition is then put into one of the rows of this you know of of the sorry this one of the columns in in this in this matrix. And then that so that bit bit decomposition essentially is going to act like as like a selector column. So as we kind of iterate down that we're we're we're basically doing a double and add and then like and then that selector will kind of determine whether when when we want to

do the double. So in addition to that we have I guess on the very right hand side accumulator column. So what this is doing is that it will take the results of each one of the um the scalar moles. Uh basically, you know, it'll be I kind of I I guess that the last row of the batch. Um uh at the last row of you know each batch. And then we'll take some randomness. And then, you know, multiply it with the with the calculated result and then, you know, sum them sum them all up. And then at the very last row of this um of this trace matrix, we will then uh do the same accumulation with like witnessed expected uh scalar

mole results. And then, you know, and then uh do the um uh constraint to verify that they both match. So um so we have some benchmarks on on this one uh specific circuit. Um So uh so we are able to verify 80 signatures, uh sorry, 256 signatures in 80 seconds. And which that amounts to about like 300 milliseconds per per signature. Um and given some comparison to some other uh proof um proof systems that we're that we're using. Uh so uh so for Plonky2 and Gnark, they're somewhat similar around 17 and 14 uh seconds. Um so yeah, I mean, it goes to show that like this

Dark base approach is like an order of magnitude faster. So, we can also enable even more um parallelization. Uh so, where let's say we have like a fleet of machines in you know in this in the leaf of this one like tree diagram, and each of them are is doing is running that one like Stark proof generation that that I just talked about. Um and then we can then aggregate all the all the proofs using something like, you know, Plonky2 with its, you know, fast like uh uh recursive like proof support. Um so we can just aggregate them in this kind of tree structure, uh which will produce a final proof saying that like the whole, you know, the whole like large batch of

um of signatures are all valid. Uh so but so one thing about like recursive friendly proof systems that they're not like that um EVM friendly and you know, the main reason is because of the the the fry protocol that they use. Um Uh and you know, which would just generally make like verification of that like pretty expensive on the um uh you know, within a smart contract. So, um to solve this, uh you know, we'll we're using uh recursive proofs again.

Um but in this case, what we're doing is that uh we've we've actually built uh Groth16 um circuit uh using Gnark um that will verify um Plonky2 proofs. Right? So, we're essentially um I guess like converting much of that you know, fry competition into more into uh uh into um you know, easy pairing operations basically, uh which will then have like um we can just utilize like the Ethereum's uh pairing uh precompiles when when verifying the proofs.

Yeah, so um I mean if I think this is a great example of us using proof composition uh where you know, we're using STARKs, Plonk Fry, and Plonk KZG to essentially um you know, enable fast proving, fast recursion, and cheap EVM verification. So, um here's the kind of a concrete example of one of the uh proof generation pipelines that we currently have. Um so here in the first step, um which we kind of call like the application specific circuit, um is where like a lot of the um uh well, you know, application specific like like logic that is like circuit logic that's implemented. So, for example, like the the Tendermint

consensus verifier or the Grandpa consensus verifier. Um and then once that is generated or once the proof is generated, then we can feed we we feed it into a Plonky2 recursive circuit, which um essentially kind of normalizes these proofs. So, what that means is that it will generate proofs that are that are all the same size and then all using the same custom gates. Um and then that is then fed into our SNARK recursive circuit um which will then uh verify these uh the um these Plonky2 proofs.

Um Yeah. So, so that is one of the like like I said, one of the existing um pipelines that we have for for our proof generation. And here's some some benchmarking. Uh so, for the Plonky2 recursive circuit, uh we were able to get that to be about you know, 1.5 seconds, um you know, witness gen plus proof gen. And for the Groth16 recursive circuit, we were getting we were um we're getting like speeds of about like 25 seconds for, you know, witness gen plus proof gen.

And so, one other like I guess like trick, you know, up our sleeve is that um because we are generating these proofs for many different types of consensus protocols, uh we we plan to aggregate them all into one proof um so that when we actually go ahead and like um verify them on the EVM, it uh you know, it will be much cheaper. Like it's for uh yeah. So, so you know, so normally it's like like around like 300k gas to verify one proof, but now that you know, we'll be able to do it for many many proofs. Um so, you know, it will get this kind of like nice amortized effect.

Um yeah, and then you know, like I said like you know, we're moving using many different types of uh you know, proof techniques and uh kind of composing them all together. Um in terms of like our repo, so the the ZK-SIMD that um uh that I talked about, so that will be open source pretty soon under the MIT license. But um our Gnark-based Plonky2 verifier, that is already open source and and also under MIT license. Um and we know we are very open for collaborators on these and and also users. So um yeah, so reach out if you um if then any of you have any questions about them.

Does anyone have any questions for Kevin? Hello. Um thank you. I was more wondering about the point of aggregating all these different contentions. Is it like to have some atomicity across the main? Oh, no, it's purely um I mean, I think that that's a kind of interesting point, but it's this is purely for like cost savings, right? So um you know, we'll aggregate like let's say you know, n different proofs into one, right? And then you know, when you verify right, it'll be it'll be cheaper. Okay okay. Yeah. Uh yeah, I mean, that's the plan, yeah.

Mhm. That's it for questions. Any more? For any more? Thank you.