Implement Secp256k1

[Pratyush]

Summary

Implement the Bitcoin curve.

Possible issue: the existing field infrastructure in ark-ff does not support "full-wdith" moduli. For example, a 255-bit modulus is fine, but a 256-bit one might not be.

Proposal

The implementation can hopefully follow the existing curve implementations. Another option would be to wrap existing fast arithmetic from other libraries/implementations (though there are not many fast pure-Rust libraries).

---

For Admin Use

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

[ValarDragon]

I'm in favor of wrapping k256 (https://github.com/RustCrypto/elliptic-curves/tree/master/k256). See Tony's blog post on it: https://iqlusion.blog/k256-crate-pure-rust-projective-secp256k1-library.

[Pratyush]

I think it would make sense to only wrap their field code, and use our existing Short Weierstrass Jacobian type for curve arithmetic. This is so that we can easily reuse the existing gadget infrastructure in the future (which works only with our existing Twisted Edwards and Short Weierstrass structs).

[burdges]

Would Ed25519 make sense? Ristretto maybe less so

[weikengchen]

We can just move this one? https://github.com/FindoraNetwork/ark-bulletproofs-secq256k1/tree/main/src/curve/secp256k1

With the recent algebra library upgrade, this should be pretty easy. I just need a yes or no.

[Pratyush]

I think with the new infrastructure we can avoid the extra limb; I would be in favour of that.

[weikengchen]

Let me double check---I suspect that 256 can fit curve25519 but not secp256k1.

[Pratyush]

By "new infrastructure" I mean the new trait design, not the existing arithmetic routines. We would need to introduce a separate impl of montgomery reductions and multiplication to avoid the extra limb.