Halo 2 support in interpreter

[L-as]

Describe the feature you'd like

Support for verifying Sonic zk-SNARKs Halo 2 proofs on-chain.

Describe the approach you would take to implement this

Somehow integrate https://github.com/adjoint-io/sonic? https://github.com/zcash/halo2

Additional context / screenshots

If possible, we (MLabs) would like to cooperate with IOHK on this, as we want to make use of ZKPs on-chain, i.e. we are willing to do the full work required for this feature.

[L-as]

After thinking about this some more, it doesn't have to be Sonic. It could be PLONK, or whatever IOHK thinks fits best.

[michaelpj]

Supporting a ZK primitive seems like a good idea indeed. It looks like PLONK is probably the way forward. But someone who knows about it needs to actually propose what the primitive should be and how people would use it.

[L-as]

I've looked into this for a few more days, and in the end, I believe that Halo 2 is the best choice. The biggest reason by far is that it doesn't necessitate trusted setups, which means a huge reduction in the complexity of a possible implementation for Cardano compared to PLONK AFAICT. In addition, it supports recursive proofs, which is a very powerful tool. The proof sizes are seemingly bigger, but I currently believe that the trade-off is worth it.

The biggest issue is that the current implementation for Zcash appears not to be completely ready, although they're using it in Orchard.

They're supposed to use this in production on 2022-01-17 (https://z.cash/support/schedule/), and in that case, I assume that it's ready enough for usage in Cardano.

Darlin is another possible solution, but they seemingly do not have an implementation yet.

Pickles also exists, and they seemingly have an OCaml implementation that is used today, but I couldn't find much documentation on it. Making bindings to Zcash's Halo 2 implementation will likely also be easier, since it's Rust.

Some references:

• https://zcash.github.io/halo2/
• https://electriccoin.co/blog/technical-explainer-halo-on-zcash/
• https://zips.z.cash/zip-0224

[L-as]

I am still not completely sure how a possible integration into Plutus would look, but I'll try making some bindings to it, and see how it works.

[michaelpj]

I'd like to see some consultation with other potential users of ZK primitives before we go with something.

[L-as]

Definitely. Looking at https://iohk.io/en/research/library/ I can see that IOHK already has a couple of papers in this subject. Perhaps someone at IOHK has some strong opinions?

[morganthomas]

I think it would be helpful to include the following cryptographic primitives:

• Field operations for finite fields of prime order
• Ring operations for rings of polynomials over finite fields of prime order
• Group operations for elliptic curve groups over finite fields of prime order

• Miller's algorithm for computing elliptic curve pairings

  I believe such primitives would provide enough runway to implement PLONK and other similar cryptographic proof strategies in validator scripts in an efficient manner.

[morganthomas]

Another primitive that could be helpful here is polynomial division for rings of polynomials over finite fields of prime order.

[michaelpj]

Please open another issue if you want to talk about other primitives than ZK ones.

[morganthomas]

I think there may have been a misunderstanding here . What I'm suggesting is that what I listed above are suitable primitives for implementing ZKPs on Cardano. An alternative would be to provide a verifier primitive for a specific ZKP strategy. On the one hand, the latter approach would probably be more efficient, but on the other hand, it would tie users to a specific choice of ZKP strategy.

[morganthomas]

That said, I would be happy with a single additional primitive which is a verifier for PLONK zkSNARKs.

[morganthomas]

I am willing to assign one of the engineers working under me to add a Halo 2 proof validator primitive to Plutus, consistent with what @L-as and I asked for here.

[michaelpj]

A change like this needs a proper proposal. At least we need:

• Comparison of alternatives
• A collection of use cases
• A description of how it would actually be used in practice
• Identification of a viable and trustworthy implementation that we can safely link into the Cardano node
• Some attempt at figuring out how to cost such a function

[michaelpj]

Alternatively, if you could make a similar proposal for the corresponding numeric primitives that you want, that might also be viable.