argumentcomputer / argumentcomputer/sphinx

Parse proper SEC1 EC point encoding in Secp256k1 decompress precompile

Open
#22 0 comments 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.