Toward application-specific reduction such as TurboPlonk and Halo2

weikengchen commented 2 years ago

Summary

We may need to get some clarity in how to enable arkworks-rs to support a large class of Plonk implementation and their variants.

Problem Definition

Implementing a specific version of Plonk, or providing a standard implementation like zk-Garage efforts (https://github.com/ZK-Garage/plonk), does not actually appeal to me very much.

I see a trend that different applications and systems will design different Plonk. For example, Rescue can be very efficient if the powering is made into a customized gate type. For example, twisted Edwards curve operations can be made efficient as well.

Customized gates are basically using FFT to exchange for fewer MSM. It also has a lot to do with sparsity when Lagrange bases are used.

The current use of TurboPlonk already goes beyond the notion of "gates". For example, one can add binary checking over existing wires of a gate, by playing with the polynomials. Halo2 can also do this as well.

This leads to a question:

What would be a (Turbo)Plonk interface that would be suitable for a large number of Plonk variants?

Proposal

This would just be the beginning and followup of #155 discussion.

First, we probably should start with finding a way to have Halo2 in arkworks-rs, as it has a very comprehensive implementation of PLONKish, and our work would be mostly filling in gadgets, i.e., instead of "r1cs-std" we would have "plonkish-std".

This is likely going to be a separate implementation, since Halo2 does not need to, and probably should not, be built over arkworks-rs since it already has its own foundation. So, a question is: how stable or finalized Halo2 is? (@daira)

Second, Jordi Baylina (@jbaylina) has been working on polynomial identity language (PIL) which seems to be closer to the different Plonk variants that are not plonkish, which is here: https://github.com/0xpolygonhermez/pilcom

This is a step that arkworks-rs needs to go sooner or later.

For Admin Use

[x] Not duplicate issue
[x] Appropriate labels applied
[x] Appropriate contributors tagged
[x] Contributor assigned/self-assigned

weikengchen commented 2 years ago

In other words, I feel we need to bring up "polynomial IOP" in the codebase.

weikengchen commented 2 years ago

This is likely going to be a long project. One way to make this more possible is to allow "using R1CS" in the TurboPlonk or Halo2, by having a ConstraintSystemRef that actually wraps some basic operations (+, *) that each Plonk implementation needs to explicitly support, as a requirement of the trait. So existing R1CS programs immediately are Plonk-ready.

This is to reflect the case that performance bottleneck often comes from repeated computation, such as points, such as binary testing, for which customized gates can easily take care of. For the rest, it doesn't need to.

This is in essence similar to the design of hardware acceleration for ZKP---you combine a general-purpose processor and an ASIC.

CPerezz commented 2 years ago

We're currently migrating https://github.com/ZK-Garage/plonk into a halo2-like system with Plonkish arithmetization. It still uses arkworks as base and should allow to write almost anything you would like without the learning curve that halo2 has.

We did some initial documents on the API shape but have changed significantly. So hopefully we can push all the stuff we have been doing soon so you can analyze it.

The actual implementation is being done in another repo. But we want to start migrating it now under ZKGarage since it's already decently started.

I'm not suggesting that you change your direction nor anything similar. Just wanted to inform that this effort is happening in case you might want to check it and take stuff from it or collaborate or whatever :smile:

arkworks-rs / snark