Move ecc and wrong-field arithmetic gadgets to bellpepper-gadgets

[mpenciak]

The src/gadgets/ folder has a lot of gadgets for elliptic curve and wrong-field operations that could be broadly useful in other projects.

We should move these gadgets to bellpepper-gadgets.

[adr1anh]

For future reference, it would be good to see if the ECC gadget can be optimized further.

Some resources:

• https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf
• https://zcash.github.io/halo2/design/gadgets/ecc.html

[adr1anh]

Regarding safety, I was under the assumption that alloc would perform point validation, by calling internally the check_on_curve method. This seems like an under-constrained foot-gun. We should rename alloc to alloc_unconstrained and define a new alloc that actually checks if the point is on the curve.

[adr1anh]

If we specialize this to Weierstrass curves $y^2 = x^3 + b$ (where $a = 0$), then we can define the identity as $(0,0)$ since it is not a valid point. We could then represent a point in the transcript as only $(x,y)$ and avoid including the is_infinity bit.

[huitseeker]

@adr1anh thanks for those notes. One thing to remark (because it has consequences on the footprint of our code) is the shift you're suggesting in the in-circuit representation of the infinity (i.e. giving the infinity point coordinates) already exists implicitly in the out-of-circuit representation.

(Fledgeling) Zcash dogma would return None as CurveAffine::coordinates on the identity point:
https://github.com/zcash/pasta_curves/blob/df67e299e6644c035a213dbad369be279276919c/src/arithmetic/curves.rs#L111
and does for the pasta curves, but the halo2curves implementation of this interface does return coordinates for that point.

Which is why our implementation of the nova::provider::traits::DlogGroup::to_coordinates method looks like this for pasta:
https://github.com/lurk-lab/arecibo/blob/dev/src/provider/pasta.rs#L123-L130
and like that for everything from halo2curves:
https://github.com/lurk-lab/arecibo/blob/dev/src/provider/traits.rs#L149-L156

This doesn't remove anything from what you're saying (we could indeed compact the identity point inside the affine coordinate data model), I'm just documenting the details of what already happens out of circuit for shared understanding.

[adr1anh]

Thanks for the additional context, my guess is the original API must have been designed this way to account for constant-time computation. We should definitely be careful if we were to change the semantics of the gadget, but that's something we can explore in more detail later.

[adr1anh]

Another thing to explore would be the use of the GLV endomorphism which is supported on BN254, this may potentially lead to a small speedup.

[adr1anh]

Copy pasting a comment from Zulip for future reference:

For the folding circuit, we are only performing two types of operations

• u0 + r mod p
• x0 + r * x1 mod p, computed ~4 times with same r

Arecibo currently implements a full non-native field arithmetic gadget, even though only these operations are needed. This also represents a significant amount of complicated circuit logic that is hard to audit.

We also have bellpepper-emulated which could replace the existing big field gadget.

I’m wondering if anyone here has any insight into how both implementations compare in terms of efficiency. If the number of constraints are even approximately equivalent, it seems like a no brainer to switch to the bell pepper implementation.

IIRC, an add-mul currently costs ~1700 constraints with the Arecibo gadget. Could we expect any significant improvement by “inlining” the two operations and tailoring it to the specific field (BN254 base)?