feat: subversion resistant setup

[akakou]

Problem: Malicious Trusted Setup

As is widely known, Trusted Setup has certain drawbacks in zk-SNARKs. These cryptographic protocols rely on the assumption that the entities conducting the Trusted Setup, known as the CRS (Common Reference String) makers, will securely dispose of the setup information. This assumption is quite strong and can undermine the overall security of zk-SNARKs.

Related Work: Subversion Resistant zk-SNARKs

To address this issue, some research proposed a subversion-resistant setup. Subversion-resistant zk-SNARKs maintain robust zero-knowledge properties even if a malicious entity conducts the setup. In this approach, the CRS maker generates proof of the CRS's validity, which can be transparently verified by anyone. Additionally, implementing a subversion-resistant setup may only require an update to the Trusted Setup, making the associated costs not too high (as far as I know).

https://eprint.iacr.org/2017/587.pdf
https://eprint.iacr.org/2017/599.pdf

Proposal: Adoption of the Subversion-Resistant zk-SNARKs

I propose that Gnark adopt support for a subversion-resistant setup. This enhancement would significantly strengthen the zero-knowledge properties of Gnark.

[ivokub]

Thanks for the proposal - it seems interesting. I don't however recall many real-life implementations using this technique. Are there some more recent results showing the deficiencies of subversion resistant setups?

On the other hand - is there also something for PLONK? PLONK requires only a trusted KZG setup, not per-circuit setup. The default recommendation is to use an existing setup which is produced through a MPC ceremony.

[akakou]

@ivokub

Since I’m not an expert in subversion-resistant zk-SNARKs, I’m still unfamiliar with the potential drawbacks of these protocols. Yesterday I searched for recent papers that analyze these shortcomings, but I haven’t found any yet.

From what I’ve gathered so far, two significant limitations remain:

1. Full zero-knowledge and soundness cannot be achieved simultaneously—one of the two properties still relies on a trusted setup performed by an honest party.
2. Making the common reference string (CRS) subversion-resistant increases the cost of both proof generation and verification.

I’m still investigating whether a subversion-resistant version of PLONK exists. If it does, such a scheme would preserve zero-knowledge even when all parties behave maliciously.

If you’re interested in subversion-resistant zk-SNARKs, I'll try to reach out to a specialist in the field. Would you like me to do that?

[ivokub]

Thanks for the reply and looking into it. In that case there are definitely drawbacks for using subversion-resistant setup. As there already are known setups for KZG SRS which imo can be also used for Groth16 first phase, then there would be a potential use-case for Groth16 second phase setup. But as there is overhead, then I think the default implementation could stay as-is (and in practice done using MPC) and it would be great if we add possibility for doing subversion-resistant second phase setup.

I checked the authors of the papers and I actually know a few people. I'll keep the issue open for now and will get in touch with them in the future if we proceed. But for now we don't have a direct plan of implementing subversion resistant setup.

[akakou]

@ivokub
Thank you for your consideration and polite reply.

I apologize if I have misunderstood your concern; my English is still improving. Are you worried about the overhead?

If so, please note that the overhead of CRS proof generation and verification is minimal. It occurs off the hot-path: the CRS maker generates the proof and each user needs to verify it, but both required only once per circuit. Moreover, because the proof is transparently verifiable, (majority of) users no longer need to verify the CRS. Importantly, the subversion-resistant setup does not affect latencies in normal proof generation or verification.

[ivokub]

Thanks for the clarification. I understood at first that there is overhead for every proof creation and verification. But if there is only a one-time cost per setup, then it makes it more appealing. I'll add the papers to the reading list and will have a look at it.