Add support for verifying ECDSA signature without recovery ID

[conr2d]

Is there an existing issue?

• I have searched the existing issues

Experiencing problems? Have you tried our Stack Exchange first?

• This is not a support question.

Motivation

The sp_core::ecdsa::Signature represents a recoverable ECDSA signature in a compact form (65 bytes: 64-byte signature + 1-byte recovery ID). While signature verification can be performed without the recovery ID when the associated public key is known, the current implementation of sp_core::ecdsa::Signature mandates the inclusion of the recovery ID. Specifically, sp_core::ecdsa::Pair::verify() utilizes the recover() method internally, thus preventing the verification of a 64-byte signature without the recovery ID. This feature is necessary to support signature verification for external protocols such as Cosmos SDK.

Request

Introduce a method to verify a 64-byte ECDSA signature without requiring the recovery ID.

Solution

1. Modify sp_core::ecdsa::Pair::verify() to leverage the underlying libraries (k256 or secp256k1) to handle the verification with a 64-byte signature. In this scenario, the last byte of sp_core::ecdsa::Signature (recovery ID) will be ignored, potentially altering the function's behavior.
2. Implement a new function, such as sp_io::crypto::secp256k1_ecdsa_verify(), that accepts a 64-byte signature, the message hash, and the public key for verification purposes.

Are you willing to help with this request?

Yes!

[burdges]

We fucked up by privileging ed25519, sr25519, and secp256k1 ecRecover, because we cannot maintain every flavor of every signature requjired by every bridge, etc. At some point, cosmos might adopt batch verification of secp256k1 schnorr, and then change batch verification flavors, etc.

We should externalize crypto from runtime libraries, but provide host calls for slow operations. If done naively, this incurs a 10x perforamnce hit in WASM, which PolkaVM may or may not improve. Assuming PolkaVM disappoints, or that WASM persists, then..

We'll fix performance by exposing hostcalls for slow operations like multi-scalar multiplications. I've described the overall architecture in https://hackmd.io/@rgbPIkIdTwSICPuAq67Jbw/rkipBanIn and tentative hostcalls exist, which can be used via https://github.com/paritytech/arkworks-extensions

Ideally, we'd audit several precise design choices there though, which requires consulting with someone like @huitseeker. I've not pushed doing this forward yet though, hence the hostcalls are not yet live on polkadot.

It's anways possible to simply use an external rust crate like https://docs.rs/libsecp256k1 or https://docs.rs/secp256k1/ or https://docs.rs/k256 directly, but with a performance penalty in the runtime.

[conr2d]

I understand your concerns and agree that exposing low-level arithmetic operations as host functions, similar to libgmp, would be beneficial. This approach would provide more flexibility to third-party developers while reducing the maintenance burden of different cryptographic primitives on the Polkadot SDK itself.

For this issue, we shouldn't need to introduce new host functions. Instead, we can modify sp_core::ecdsa::Pair::verify_prehashed() to support this feature. This change won't invalidate existing signatures but will allow users to verify the signature without the recovery ID.

You can see the proposed change here: conr2d@4ba01ab

For the canonical form of ECDSA signatures, if the given recovery ID is not zero, pass the signature to the original verification by recovery. Thus, only a recovery ID of 0 means it's ignorable. Alternatively, since using 0xff as a recovery ID is not a common convention, we could establish a rule where 0xff indicates that the signature is not meant to be recovered but should be verified with a public key.

If this change is not permissible, the second-best approach would be to iterate over recovery IDs from 0 to 3. If the verification is successful with any of these recovery IDs, consider it a valid signature for performance reasons.

[burdges]

It's less the number of host calls than their maintanance burden, so complicating one maybe worse than adding one. Zero is an allowed RecoveryId, so your change should brick some substrate chain somewhere, no?

Actually libgmp has the opposite problem of being too low-level. An elliptic curve addition needs one division and several multiplications in the base field aka libgmp operations, so an elliptic curve scalar multiplication would become thousands of libgmp hostcalls, and host calls bring their own overhead.

We'd target exactly the slow operations in all current verification algorithms for elliptic curve cryptography: snarks, signatures, IBE, etc.

[conr2d]

Yes, 0 is a valid recovery ID. However, there is currently no way to represent an unrecoverable signature (a 64-byte signature without a recovery ID) in Substrate, and no universal agreement on how to handle the last byte in this case. Using 0 as a placeholder for the recovery ID when it is not intended to be used was just one option. I discussed a similar case with the varsig maintainer from multiformats, and they also considered putting 0 for the recovery ID as the default value when it is not intended for use.

Your point that my change could affect other chains is correct, and I did not consider this initially. If some Substrate chains have signatures that were treated as invalid due to a wrong recovery ID, and my change causes these to be treated as valid signatures, it could lead to a consensus break. It's unlikely, but there could also be a case with 0xff. We cannot rule out the possibility entirely. I understand your point, and I need to consider how to address this while minimizing performance loss within the given Substrate framework.

Anyway, thank you for your feedback. @burdges

[burdges]

Can you ship whatever you need using WASM right now? Or some other hack that transforms the ECDSA signature for use with the existing host call? If so, just do it. Polkadot has lots of unused coretime right now. lol

We'll need to audit the new host call design imho, because it's a pretty radical departure. If done well, then most crypto crates on supported curves could be forked to use the hostcalls.

[conr2d]

It seems possible. We are trying to verify Cosmos transactions directly on-chain. The process involves wrapping the raw Cosmos transaction received from the RPC into a SelfContained extrinsic. Since this happens on the host, we can pre-calculate the recovery ID and include it as a hint in the extrinsic. This way, the existing recover function should be able to handle it.

[burdges]

Related: polkadot-fellows/RFCs#113 (comment)