Serialization in compressed format

[gromakovsky]

In my application I need to encode and decode secp256k1 public keys in the same format as Bitcoin uses: https://www.oreilly.com/library/view/programming-bitcoin/9781492031482/ch04.html

According to that page it is called "Compressed SEC Format". I know that there is another library specialized to secp256k1, but I am already using cryptonite and don't want to add more dependencies. I am using Crypto.PubKey.ECC.ECDSA.PublicKey with hardcoded Curve, so I only need to encode and decode Crypto.PubKey.ECC.Types.Point. It is quite easy to implement encoding function (here I am using ByteString for simplicity, it can be generalized to ByteArray):

publicKeyToBytes :: HasCallStack => ECDSA.PublicKey -> ByteString
publicKeyToBytes (ECDSA.PublicKey curve publicPoint) =
  case publicPoint of
    -- We are using `i2ospOf_` because `curveSizeBits` ensures that
    -- the number won't have more than that many bytes.
    Point x y -> prefix y <> i2ospOf_ (curveSizeBits curve `div` 8) x
    PointO -> error "PublicKey somehow contains infinity point"
  where
    prefix :: Integer -> ByteString
    prefix y
      | odd y = "\003"
      | otherwise = "\002"

Decoding function is a bit trickier, I haven't tried implementing it yet, but the algorithm is described in the linked page, so I think I can do it as well.

I know that there is EllipticCurve class with encodePoint and decodePoint functions, but I couldn't find any implementation that uses compressed format.

So I have a couple of questions:

1. Is such functionality already present anywhere in the library (maybe I just missed that)? Maybe not encoding/decoding, but at least a function which takes x coordinate and Curve and returns y coordinate or Point? It would be very helpful for decoding.
2. If there is no such functionality, does it make sense to add it? If yes, where should I put it? I can do it in Crypto.PubKey.ECC.ECDSA or I can add a newtype wrapper which customizes EllipticCurve instance so that encodePoint and decodePoint use compressed format.

P. S. I am a crypto newbie, so please don't hate me if I wrote nonsense ^_^

[ocheron]

We don't have this currently. Compressed format saves some space but the deserialization is very slow compared to just validation of (x,y).

EC/SEC_p256k1/uncompressed               mean 650.1 ns  ( +- 18.28 ns  )
EC/SEC_p256k1/compressed                 mean 11.50 μs  ( +- 164.1 ns  )
EC/SEC_p256k1/hybrid                     mean 11.43 μs  ( +- 163.4 ns  )

The link you gave is for Fp with p = 4u + 3, it will not apply to all curves.

[ocheron]

For now I think we can add the number functions required to deserialize compressed coordinates but not the deserialization code itself.

• square root in Fp → merged Modular square root #303
• square root in F2m → merged implement square roots in f2m #322
• quadratic equation in F2m

[nomeata]

but not the deserialization code itself.

Why not? Seem appropriate for the “self-proclaimed kitchen sink” :-)

The instance EllipticCurve Curve_P256R1 even implements a format with this byte tag…