ECDSA

ECDSA, together with Schnorr, were two new signature algorithms introduced in Plutus during Cardano's Valentine upgrade.

Generalised specification

This section presents the generalized signature system ECDSA, and in the parameter section, we present the specific parameters used in Cardano. ECDSA is parametrized with the following parameters. An ECDSA signature consists of the following three algorithms:

  • takes as input the security parameter and returns a key-pair . First, it chooses . Finally, compute , and return .
  • takes as input a keypair and a message , and returns a signature . Let . Compute and interpret the result as its two individual coordinates . Next, compute . If , generate a new and start over. Finally compute . If , generate a new and start over. Otherwise, return .
  • takes as input a message , a verification key and a signature , and returns depending on whether the signature is valid or not. The algorithm returns if the following conditions hold and otherwise:
    • and are between and .
    • Compute and . Compute , and ensure it is not equal to the point at infinity. Checks that .

Parameters of instantiation

The above is the standard definition, and in cardano we instantiate it over curve SECP256k1. However, such a signature algorithm enables malleability. Given a valid signature , if one sets , then the pair is also a valid signature, as a point and its negative share the same x-coordinate. This can be problematic in consensus critical contexts. To that end, we follow Bitcoin's modification of only accepting signatures with small values of , i.e. with .

The signatures generated using Haskell's bindings (see here) use hash function SHA256. However, Plutus built-in function takes as input the hashed message, meaning that the signer and verifier can agree which hash function to use in their protocol.

While we follow the verification criteria used in Bitcoin, we do not follow their serialisation convention, DER-encoding, which results in variable sized signatures up to 72 bytes (instead of the 64 byte encoding we describe in this document).

More precisely, the following is what is the specification used in the plutus built-in functions:

  • The verification key must correspond to the (x, y) coordinates of a point on the SECP256k1 curve, where x, y are unsigned integers in big-endian form.
  • The verification key must correspond to a result produced by secp256k1_ec_pubkey_serialize, when given a length argument of 33, and the SECP256K1_EC_COMPRESSED flag. This implies all of the following:
    • The verification key is 33 bytes long.
    • The first byte corresponds to the parity of the y coordinate; this is 0x02 if y is even, and 0x03 otherwise.
    • The remaining 32 bytes are the bytes of the x coordinate.
  • The input to verify must be a 32-byte hash of the message to be checked. We assume that the caller of verifyEcdsaSecp256k1Signature receives the message and hashes it, rather than accepting a hash directly: doing so can be dangerous. Typically, the hashing function used would be SHA256; however, this is not required, as only the length is checked.
  • The signature must correspond to two unsigned integers in big-endian form; henceforth r and s.
  • The signature must correspond to a result produced by secp256k1_ecdsa_serialize_compact. This implies all of the following:
    • The signature is 64 bytes long.
    • The first 32 bytes are the bytes of r.
    • The last 32 bytes are the bytes of s.
        ┏━━━━━━━━━━━━━━┯━━━━━━━━━━━━━━━┓
        ┃ r <32 bytes> │ s <32 bytes>  ┃
        ┗━━━━━━━━━━━━━━┷━━━━━━━━━━━━━━━┛
        <--------- signature ---------->