argumentcomputer / argumentcomputer/sphinx
Parse proper SEC1 EC point encoding in Secp256k1 decompress precompile
- Dominant language
- Rust
- Stars
- 80
- Forks
- 8
- PR merge metrics
- No merged PRs in 30d
Description
Paraphrasing from https://github.com/wormhole-foundation/wp1/pull/138#discussion_r1575949868:
[This](https://github.com/wormhole-foundation/wp1/blob/de39fca2178c6000c1fb6b30a1064bf62c4eaa00/core/src/syscall/precompiles/secp256k1/decompress.rs#L50-L52) call to `k256::AffinePoint::decompress` is actually making assumptions on representation which I'm not sure are represented elsewhere.
Indeed, just like BLS12-381, Secp256k1 has a point serialization standard in compressed form, and I'm not sure if the API of the Secp256k1 precompile should be this "compressed serialization" format, or a generic coordinate format.
The compressed serialization for Secp256k1 is defined through [SEC1](https://www.secg.org/sec1-v2.pdf) paragraphs 2.3.3 and 2.3.4. Basically, it's a 33-byte serialization format, with the MSB being 02 if the intended y coordinate is even, 03 if it's odd.
The call we're making here to `k256::AffinePoint::decompress` in `secp256k1_decompress` is *not* following SEC1:
https://github.com/RustCrypto/elliptic-curves/blob/6ff3bb7d8632ea9970aa583c89e944356b8bc8d1/k256/src/arithmetic/affine.rs#L185
But `k256` contains conversions to/from `EncodedPoint` that do follow that standard:
https://github.com/RustCrypto/elliptic-curves/blob/6ff3bb7d8632ea9970aa583c89e944356b8bc8d1/k256/src/arithmetic/affine.rs#L302-L312
And the `EncodedPoint` embeds those conventions:
https://github.com/RustCrypto/elliptic-curves/blob/6ff3bb7d8632ea9970aa583c89e944356b8bc8d1/primeorder/src/affine.rs#L164-L195
Leaving this issue open until we decide whether we want to improve on this (by using the proper `EncodedPoint` functions with full SEC1 support, and handling that both in and out of circuit), or decide that the current state is good enough and we just make sure to properly document the precompile mentioning this caveat.
Contributor guide
Research direction
Start in core/src/syscall/precompiles/secp256k1/decompress.rs at secp256k1_decompress and review the k256::AffinePoint::decompress call. Compare it with k256's EncodedPoint conversions and the SEC1 paragraphs cited in the issue, including how the representation is handled in and out of circuit. Done means either SEC1 compressed encoding is supported consistently or the precompile's current format and caveat are documented.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cryptography
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100