search

ZK-Garage / plonk

A pure Rust PLONK implementation using arkworks as a backend.
https://discord.gg/XWJdhVf37F
Mozilla Public License 2.0
295 stars 76 forks source link

Support Weierstrass inner curves in StandardComposer #108

Open markulf opened 2 years ago

markulf commented 2 years ago

It would be ideal to use ModelParameters instead of TEModelParameters (so that short weierstrass inner curves can be used) but it's difficult to do in a fully generic way.

The inner curve abstractions in arkworks are lacking here, and in general, there should be a trait that defines the addition and scalar multiplication laws for the curves directly, and the StandardComposer just queries that trait for implementing the circuit. Then, when constructing the circuit, you specify which instance of this trait you want, and the circuit is populated with the correct constraints. The arkworks abstractions are too low level to be leveraged to do this, since they are more about specifying the kind of curve (and performing the direct native computation), than specifying the algorithm itself at compile-time.

Originally posted by @bhgomes in https://github.com/ZK-Garage/plonk/issues/61#issuecomment-1003421592

See also https://github.com/ZK-Garage/plonk/pull/61/files/dc22df80f380de0ee87d51ab7f1b6f00aa94599a#r779095875

ghost commented 2 years ago

I also wasted way too many hours trying to figure this out, and I also think there should be some changes on arkworks side to facilitate all of this.

One alternative (besides defining the laws for the curve in arkworks) is to change ModelParameters to be an enum type instead of a trait. This would be a better conceptual fit, as a ModelParameters is really only ever one of 3 different kinds, and this would allow matching on the type (for example, to pick which kind of addition laws to use). As far as I know, while this is not exactly a compile time choice, the match should probably be optimized out.

(I messed around a bit with making this kind of change here: https://github.com/joebebel/algebra/commit/d8344915a7e665153cbb3e40d7e63a6b658d3614)

ghost commented 2 years ago

See section 4.1 of this thesis: https://core.ac.uk/download/pdf/10898289.pdf and this paper: https://eprint.iacr.org/2015/1060.pdf for details on complete formulae for weierstrass curves.

It's probably worth implementing both complete and incomplete arithmetic.