ecdsa public key format uncompressed vs compressed

[leighmcculloch]

Reviewing the SDK and environments crypto functions and noticed that we're returning the public key from secp256k1_recover as 65-bytes uncompressed.

I expected that this would have been the 33-byte compressed form.

The value returned will likely be == compared with a public key stored in contract storage, or passed in as an input into to a contract fn, and so the format returned by this function will likely influence how contract developers pass ecdsa public keys to contracts, and how they use keys in their own applications.

The reason I expected compressed form is that it's less data being passed around and stored, meaning more cost effective.

Also the uncompressed form has a quality that developers must be aware of: the points may not be on the curve, and may not be valid. The compressed form doesn't have this quality because developers must derive one of the points and so the points will always be valid. I don't think this quality would especially affect Soroban development directly, but if Soroban encourages the uncompressed form it's possible it encourages use of uncompressed form in the ecosystem outside contracts.

I'm not sure if compressed vs uncompressed was a conscious and intentional decision. Compressed form does require the Soroban environment to do more work and maybe we evaluated that was too expensive? I think we should reconsider though.

This is the function exposed in the Soroban SDK:

/// Recovers the ECDSA secp256k1 public key.
///
/// The public key returned is the SEC-1-encoded ECDSA secp256k1 public key
/// that produced the 64-byte signature over a given 32-byte message digest,
/// for a given recovery_id byte.
pub fn secp256k1_recover(
    &self,
    message_digest: &BytesN<32>,
    signature: &BytesN<64>,
    recorvery_id: u32,
) -> BytesN<65>

Ref: https://github.com/stellar/rs-soroban-sdk/blob/349cd57fc7f20c67730ff89762e99e64e280e4d5/soroban-sdk/src/crypto.rs#L50-L60

This is the code in the Soroban Environment that generates the public key. It appears that changing to compressed is a one line change not including updating tests and redoing calibration:

rs-soroban-env/soroban-env-host/src/host/crypto.rs

Lines 158 to 160 in 8e593ab

	recovered_key
	.to_encoded_point(/*compress:*/ false)
	.as_bytes(),

I started a conversation about this on Discord, but the issue can be discussed here on GitHub.

Related issue:

• ecdsa signature format has side-car recovery id instead of inline #1235

[leighmcculloch]

@kwantam do you have an opinion if ecdsa apis that output public keys should do so uncompressed or compressed? Any insight if this is okay as is or concerns we might not be considering?

[kwantam]

@leighmcculloch your summary of the tradeoffs here is on target. A few random thoughts:

• my general impression is that Eth-ish and Btc-ish APIs tend to work with uncompressed keys (as examples: Eth and Btc addresses are hashes of the uncompressed key; the ecrecover precompile returns an uncompressed key). (EDIT: For bitcoin I'm wrong: p2pkh and p2wpkh use compressed, not uncompressed.)

• it's a pretty straightforward byte manipulation to go from uncompressed to compressed SEC1 format. Rustishly:

  let sec1_uncompressed_pubkey: [u8; 65] = get_uncompressed_public_key();
  let sec1_compressed_pubkey = {
      let mut tmp = [0u8; 33];
      tmp[1..].copy_from_slice(&sec1_uncompressed_pubkey[1..33]);
      tmp[0] = 0x02 | (sec1_uncompressed_pubkey[64] & 0x01);
      tmp
  };

  So at least in principle if the keygen or recovery procedure returns uncompressed it's still efficient to check against compressed.

• if you only use public key recovery to check ECDSA signatures, you don't have to worry about off-curve public keys: the recovery procedure will always return a valid curve point

• the recovery procedure needs to do a point decompression whether it returns a compressed or uncompressed point. So you'd end up paying for a modular square-root either way.

• Corollary to the above: the only way to get the computational efficiency benefit of working with uncompressed keys is to avoid key recovery in favor of the standard signature verification procedure. And in this case, of course, it's vital to check that the purported public key is really on the curve.

In sum, there doesn't seem to be much of a disadvantage to working with compressed points; there's probably not even an efficiency hit. On the other hand, it's (potentially) a departure from the way folks are used to doing things in other ecosystems, and it's not clear there's any safety benefit if people are anyway going to be using public key recovery for signature verification.

[leighmcculloch]

Thanks for the insight @kwantam. Sounds like this is okay as is then from a safety perspective.

From a resource perspective the benefit would be 33 bytes vs 65 bytes being stored and transmitted.

If we wanted to improve this later we could introduce a second recover fn that returns the compressed form, or add a host fn that converts a BytesN<65> uncompressed into a BytesN<33> compressed so that folks don't have to store or transmit the slice from host to guest and back.

[graydon]

Yeah, I'm not too concerned with the size difference at the API level. If someone's making zillions of them and want to optimize, yeah they can transform to compressed manually (I expect they'll be compressing XDR long before, but whatever). I went with the uncompressed because as @kwantam originally pointed out it's what existing systems use. Less deviation.