CoSNARKs in halo2 | Ying Tong, Independent Researcher | ETHTaipei 2025

Thank you. Um, thanks for coming to my talk uh about collaborative storms in Halo 2. And Halo 2 here is a zero knowledge proof system. It's not the video game. Um so I think my talk will be the first of several in this session about programmable cryptography.

And basically programmable cryptography is a way to enable very expressive programs um to be verified cheaply on chain. So you may have heard of this primitive called zero knowledge snarks or zero knowledge proofs. Um this is what's underlying uh all zk rollups. Um so the idea behind a zk snark is that you can outsource an expensive computation offchain. um have the prover produce a very short proof of the integrity of their computation and then verify the computation on chain without having to redo it yourself.

And this is how ZK rollups work. Um, so now a collaborative zk snark introduces a multi-party element into the zk snark. And what this means is that the witness, the secret data of the computation no longer has to be owned by a single party and instead it can be split up across multiple parties. So why this might be useful? Um let's go to let's go to an example.

So the first use case um that comes to mind is verifiable private inference. Uh by this I mean machine learning inference. So imagine a use case where one party has inputs to a model that they want to keep private. For example, it's um data about people's healthcare records or um it's like your a trade that you want to make and you don't want to reveal to your counterparty. And then the other party has a set of proprietary weights to [snorts] their machine learning model that they don't want to reveal like their trading algorithm or maybe it's some kind of classifier that they don't want you to be able to game.

Maybe it's chat GPT. So the idea here is that without revealing their private data to the other party, the two parties can jointly compute a zk snark um over their input. So in other words, they can run their model that they can run the private model on the private weight and produce a proof that would convince the both of them as well as any third party verifier that this was done correctly. So um this project um that I worked on has actually implemented this um it's um project called Ezekiel uh and yeah right now they've integrated collaborative snarks um into their pipeline. So from an onnx machine learning model uh you can get to a collaborative snark.

Um so a few neat use cases for verifiable private inference include um as I mentioned sophisticated trading strategies and two-sided marketplaces um that can be done offchain um anything that involves a confidential model for example an under a secret underwriting model and a credit scoring that you don't want people to name um anything that deals with sensitive data that cannot be shared. For example, um the sending and receiving accounts in a banking in an interbank transaction. Um we need information about both these accounts to detect fraud, but we we're not able to share them in in the plain text. Um and also KYC or identity verification. I think one thing that's important to note is that at the end of this we want a short verifiable proof.

Um in other words we want this whole computation to be auditable efficiently by arbitrary third parties and in many use cases this is really important. For example, um banks need to justify um um banks need to justify any decisions they make uh to block transactions or to uh flat them as fraudulent. So the second use case is kind of related to the previous talk. Um so onchain dark pools whereby traders can collaboratively try to match their take and make orders. Um and if they if their orders do match like say it's a limit order and it falls within that range um then they successfully create a transaction um that performs the swap.

If their orders don't match, then basically we abort when we fail to create a snark. But the point being, we don't learn anything more about the counterparty's orders besides the fact that it didn't match yours. Um, and so I used to work on this um private payments protocol called Zcash. And Zcash is actually um planning to introduce um Zcash shielded assets. So like uh like userdefined asset types on Zcash.

And the point of doing this is to let people swap tokens. But yeah, right now to swap tokens on Zcash or you would basically need to reveal your order in in plain text to a third party market maker. And I think this defeats the whole point of Zcash. Um and yeah, I think well uh this project I'm presenting today was already written in Halo 2, the proof system um which happens to be what the Zcash uh circuits are written in. So, a a really cool project I think would be to integrate collaborative snarks in Zcash and enable um privacy preserving asset swaps.

And this is what um is already done by a protocol called Renegade. So for the rest of this talk, I'm going to walk you through basically the back end and what is involved in adapting a ZK Snark proof system into a multiplayer collaborative Snark proof system. Um so if you're not familiar already with the internals of ZK Snarks, I would not worry about it. Um, in this short time all I hope to communicate is some kind of intuition and to point out to you maybe some future work areas for improvement if you're interested. So yeah, basically we can understand the backend proof system um in three modular components.

Um and oh I want to give you sort of a preview of how the API looks like right now. So the in the setup um we basically define uh which values are owned by party zero and which values are owned by party one. So I've only implemented this for two parties. And then um the interface looks really similar for parties zero and one. So party zero would basically declare the values that they know and the values that they don't know they just put unknown and then party one does the complimentary thing and then behind the scenes are we're just secret sharing the values that we do know and then secret sharing zero for the values that we don't know.

It's pretty straightforward. Um, so yeah, I guess concretely these values um are laid out as a matrix and each matrix contains um a value in a finite field and um these values in the finite field are what we are secret sharing. So yeah, basically what it means to secret share is um to more or less do a one-time pad with a random masking value. So let's say party zero is trying to share the value a and this is an element in a finite field. What they can do?

They want to end up with this um tpple a z a1 that both both a z and a1 look completely random. These are the secret shares. So a z is just a random mask that party zero picks and then a1 is you can think of like a one time pad of a plus a z. Yeah. And then so now you have two completely random looking secret shares.

And later on if you want to reconstruct the original value you simply have to add them together. So this is called additive secret sharing. It's one of many um schemes for multi-party computation. And for our particular use case working over a finite field, this is one of the more efficient ways um to secret share values. So now um we're working over this matrix of values and we're putting basically um constraints on them in the form of addition and multiplication operations.

So yeah, you could visualize them as an arithmetic circuit as well. Um, and the nice thing about addition in additive secret sharing is that it comes for free. By free I mean that each party can do it fully locally. So you can see here that um the secret sharing of a plus b can be separated very nicely into party zero and party one's um shares of a plus b. And so to open the final sum they just need to add together their partial secret shared sums.

So this is really nice. Um what is less nice is multiplication. um multiplication. Basically, if you naively um try to add the products um the secret shared products, you're going to get a bunch of cross terms. Um and yeah, to get rid of these cross terms, what we need to do is interact with the other party.

Um so this is a trick called beaver's triples that um uses pre-processing step to generate a bunch of um xyz tpples such that x * y equals z and then we're going to use um cleverly to um construct these secret shared values which cancel out the cross terms. That's a high level intuition. But you can see that um each party needs to open um these new values and that is the step of interaction that is introduced. Uh yeah. And so when we're talking about the efficiency of an MPC protocol, uh what we mean is the amount of interaction needed.

So the efficiency of an MPC protocol is proportional to the number of multiplication operations it needs. Um and yeah this is something also very different from zero knowledge proofs which are completely non-interactive. So um we can move on as usual. Now that we have addition and multiplication, we can move on with the normal constraints um in the circuit over secret shared elements. Um and I wouldn't worry too much about the details of these constraints.

Um really what they're doing is enforcing um arbitrary relations. um that are chosen in the circuit definition. So for example, enforcing that this neural net was run correctly or that your age is over 18, whatever like NP statement. Um so I think something interesting that did emerge um from my implementation is the fact that the realization that several well yeah [snorts] certain well is the implement uh is is that ZK snarks and MPC are incompatible in a very fundamental way. So in particular, ZK snarks uh are used for verification.

So they're useful when you already know the whole execution trace of a program and you want to enforce constraints on it. On the other hand, MPC is useful for computation when you don't know or the output of a program and you're trying to compute it with your counterparty together. So what this means is that um several tricks that we use to speed up computation in zk snarks do not carry over into MPC. Yeah. And this kind of subtlety I think only emerged from having implemented this and run into a roadblock.

So in particular um in ZK snarks we can make use of this primitive called the lookup table um in which we premputee um a set of inputs and outputs for some very expensive function and look them up in the circuit instead of doing the computation ourselves. Now um this involves um in witness generation this involves comparing the values in your input to each value in the table. So if you knew the values in your input this would be a simple n or better comparison. The problem now is our input values are secret shared and so it is not um so basically we we have to do the comparison in MPC. Um and an a comparison in MPC as far as I know would require some kind of boolean decomposition.

Um so yeah I think [snorts] this was uh this was an important insight um and potentially yeah from these sorts of problems could arise interesting research questions of whether we could find alternative primitives that are MPC friendly uh that we can use as dropins uh in in collaborative of snarks. So we're done basically with the first part of the proof system. Um this is called arithmetization and uh it's basically us secret sharing our values doing a bunch of addition and multiplication gates on them and also um introducing other constraints such as lookup constraints. Um the next part of our proof system is this interactive protocol um between the prover and the verifier. So this is a series of interactions that allows the verifier to efficiently check that the constraint has been properly enforced um on the values in the circuit.

And um so I think what's interesting here is that um like this seems like really scary operations over polomials, evaluations, commitments but if we look closely um the operations underlying this are all linear and so we can absolutely do them just with additions and multiplications. it was really not a problem. So yeah, when we're sort of constructing um the constraints over a circuit, we need to do a fast for transform that's just a linear operation. Um and also the commitments and evaluations that the proverates to the verifier are all public. um they're part of the public transcript that's part of the zero knowledge proof and so they can all just be opened.

Um so I think the last step here in the in realizing the ZK proof is basically how these commitments are produced. Um and the the thing I want to emphasize again is that um these commitments are just linear operations. Um under the hood they're um scalar multiplications in an elliptic curve. And again this is completely supported by um our scheme since we did the secret sharing at the level of field elements and curve points um and are able to do additions and multiplications over them. So yeah, I think the highle takeaway here is that um there's sort of several well there's like zk snorics and multi-party computation interact in interesting ways.

Um, there's several sort of tricks of computation used in ZK Snarks that don't carry over to MPC, but there's also several very nice so like there's some snarks that are very nice and amanable to multi-party computation and in particular these snarks are the ones that mostly use uh linear operations on the prover side. So I was thinking about basically like lots of interesting research questions emerged here. Um so first of all could we make this collaborative snark [snorts] um more efficient in the asymmetric setting? meaning um for example if if the model inputs are a lot smaller than the model weights then could party zero do less work than party one. Um and basically this would unlock um collaborative snarks for a whole class of resource constraint provers such as mobile devices and allow them to still produce proofs about large statements that they can submit on chain.

So this would be a really powerful setting and primitive if we could realize it. Um yeah and um I was also thinking about exploring this technique for other proof systems. So there's proof systems that are um that use lots of nonlinear operations and in that case we could we we wouldn't use um arithmetic circuits and we would instead use boolean circuits. Um, and yeah, I think there's lots of tricks you could do. Um, like yeah, the final goal is to have a publicly auditable MPC computation uh that you can post somewhere on chain.

Um, and so besides collaborative snarks, are there other publicly auditable MPC schemes um that we can compose with a normal snark? for instance. Um, yeah, I think that's all I have. Thank you. [applause] Yeah.

How much time? I think you have about like five minutes for Q&A. Yeah. So, you're open to Q&A. Does anyone has any questions there?

Hey Mo. Uh, yeah. So, I I feel like co snucks might actually be a oxymoron because like snucks uh meant to reduce like the um like the need for this interactive pro verifier scheme and now we introduce back an interactive scheme between all the nodes. Um should there be a different name for this scheme or is there like any benefit to using snacks? What if we use like I guess things in in the literature like sigma protocols which are already interactive like um like why snucks versus like I guess like more traditional schemes which are are interactive to begin with.

Yeah. Yeah. Uh that's a really good question. So the short answer is that like in the MPC literature this is called publicly auditable MPC. So it's like basically an MPC computation that can be verified by any third party.

That's the primitive that we want. Um but it is true that a lot of publicly auditable MPC schemes are linear in the verifier. Um unlike snarks which are succinct. So the main benefit of co snarks is the succinctness. Um and yeah, I think coerc only makes sense when you have a resource constraint verifier like a blockchain.

So for example, if you wanted to verify um like the correct execution of a trading strategy and then on that basis um unlock like some escrow or some or execute some trade on chain, you would need like a succinct proof. Um but yeah, I I I definitely agree that like these primitives don't compose completely cleanly. Um like in the witness generation layer like introducing interaction, it it it does feel a little bit forced. Um cuz you snarks really like snarks are yeah purposebuilt for like non-interactive and succinct proofs and yeah I I I think there's to to like my short answer and intuition is that there's a limited set of use cases for which coarks make sense. Yeah.

me. Okay. Yeah. One more. Um here he needs the microphone.

Uh could you please elaborate on why a boolean circuit would make more sense for nonlinear commitments? Yeah. So the proof system that I was using here um involved on the prover side mostly uh operations in the finite field and elliptic curve group whereas there are some other proof systems where the prover is mainly doing um say a shot 256 hash and uh that involves a lot of bit shifts exors uh operations which are very expensive in a finite field. Yeah. Um [snorts] Yeah.

And I think it it is an interesting problem space cuz or yeah, I'm only focusing on the two-party setting. Uh which means that actually garbble circuits are also uh a good option for me. So yeah, I I think like the meta takeaway here is that um we we should tailor our solution to the requirements and also be aware that um this solution only makes sense for a limited set of use cases. Thank you. Okay.

So, thank you Anton. [gasps] [applause] Bye. [music]