Canister ECDSA Signatures

Public key:

Message hash:

Signature:

Canisters can sign messages, using ECDSA on the secp256k1 curve. At present, we can only do so on local nets; this feature will soon be enabled on the production Internet Computer. (The final API may be slightly different.)

We follow the steps described by the ECDSA Signing Demo to start a suitable local network with dfx version 0.9.3.

In one terminal:

~/.cache/dfinity/versions/0.9.3/ic-starter \
    --replica-path ~/.cache/dfinity/versions/0.9.3/replica \
    --subnet-features ecdsa_signatures \
    --dkg-interval-length=20 \
    --subnet-type system \
    --create-funds-whitelist '*'

In another:

~/.cache/dfinity/versions/0.9.3/icx-proxy \
    --fetch-root-key \
    --address 127.0.0.1:8000 \
    --replica http://localhost:8080

We’re ready to try out the signing API, which lives on a pseudo-canister known as the management canister. The signing API is fussy: it only allows canisters to call it. In fact, the API is invisible to users:

$ dfx canister call aaaaa-aa sign_with_ecdsa
Error: Attempted to call an unsupported management canister method: sign_with_ecdsa

Thus to demonstrate signing, we’ll need a canister to make the calls. We can do this with a wallet canister; one way to ensure a wallet is present is to simply deploy any canister.

We can look up our wallet canister ID:

$ cat .dfx/local/wallets.json

Set an environment variable to your wallet, for example:

$ WALLET_ID=rwlgt-iiaaa-aaaaa-aaaaa-cai

Signing

Now we’re good to go:

$ dfx canister --wallet $WALLET_ID call aaaaa-aa sign_with_ecdsa
Error: An error happened during the call: 5: Error decoding candid: No more values on the wire, the expected type record {
  key_id : text;
  derivation_path : vec vec nat8;
  message_hash : vec nat8;
} is not opt, reserved or null

Encoding the following with our Rebel Candid tool:

record
{ key_id = text "secp256k1"
; derivation_path = vec blob {}
; message_hash = blob 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
}

yields:

4449444c036d7b6d006c03bbebadff0371ada8b2b105018689b3dc0b00010209736563703235366b310020e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

The message hash must be exactly 32 bytes long; we’ve chosen the SHA-256 hash of the empty string.

We use an empty derivation path to produce the canister’s "default" key. Then we sign our hash:

$ dfx canister --wallet $WALLET_ID call aaaaa-aa sign_with_ecdsa --type raw
4449444c036d7b6d006c03bbebadff0371ada8b2b105018689b3dc0b00010209736563703235366b310020e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
(
  record {
    359_375_608 = blob "vI\e8\f7k\a8oOr=f\ca\1f?jMA@\be\ed\0f\03\1c\17\12\cc\c7\c2h/\c5\07LFNuRV\00\ea\c3\c3(\bb\03\8c\9e4n;\ae\8d\cc.\b4\b8\1b\f6\b9^\8d\b5\0f\8c";
  },
)

The raw output is easier to work with, and it turns out the last 64 bytes are the signature, which we can extract with tail:

$ dfx canister --wallet $WALLET_ID call aaaaa-aa sign_with_ecdsa --type raw 4449444c036d7b6d006c03bbebadff0371ada8b2b105018689b3dc0b00010209736563703235366b310020e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
--output raw | tail -c 128
c78518b1412498a231548f113895bd2ce0e274c1d7cc77dc7048ea36472952f71a67918fe6a0d586167c36359aac088deb5796b1b84ad400549accef10f3d6de

This signature differs from that of our previous run because signing with ECDSA involves picking a random number.

An ECDSA signature consists of two 32-byte numbers, often called r and s.

Verification

We can look up canister’s public key via get_ecdsa_public_key. If we omit the optional canister_id field, then we get the caller’s public key, which in this case is the wallet:

Paste the following into Rebel Candid:

record
{ key_id = text "secp256k1"
; derivation_path = vec blob {}
}

Then send the result to the management canister, for example:

$ dfx canister --wallet $WALLET_ID call aaaaa-aa get_ecdsa_public_key --type raw 4449444c036d7b6d006c02bbebadff0371ada8b2b10501010209736563703235366b3100
(
record {
  881_350_601 = blob "\03\a2\83\bd\12<\ae\19\c9\f2\15\0ci\ba\84\c5\f2\8a\89\b8\89\d2\8dyvd\0d\e0\12\da\bf\c9\a9";
  3_110_171_755 = blob "Tl\14\1e\af\f6\c8\f9\e9\08\ee\e4h\cb/I\07\0e\ba~\c6\99\7f\1ac\be,\bc\1a\27\ca\94";
  },
)

The first blob is the public key. The second is the chain code which can be used to derive keys from paths offline. We have no need for the chain code since we’re getting the management canister to do everything for us.

The public key is the 33 bytes:

03a283bd123cae19c9f2150c69ba84c5f28a89b889d28d7976640de012dabfc9a9

We can confirm the signature verifies with the widget at the top of this page.

Key derivation

We could choose another derivation path to get another public key under our control via a generalization of BIP-32 (see ia.cr/2021/1330, Appendix D). This is analogous to ledger subaccounts.

The following widget performs one derivation step. To derive the entire path, repeatedly replace the parent public key and chain code with that of the child, and change the bytes to the next entry in the path.

Parent public key:

Chain code:

Bytes:

First principles

The arithmetic powering ECDSA is simple; the tricky part is proving the mathematics all works out. Indeed, we can easily verify secp256k1 signatures with any language that supports arbitrary precision integers, such as Haskell.

It turns out we’ll find an excuse to use (<|>), so we import it:

import Control.Applicative ((<|>))

We define arithmetic modulo the p constant of secp256k1. Recall we can compute the inverse of a (nonzero) element by raising it to the power of p - 2 (which suits crypto better than the extended Euclid’s algorithm because it resists timing attacks).

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
data Fp = Fp { unFp :: Integer } deriving (Show, Eq)
instance Num Fp where
  Fp a + Fp b = Fp $ (a + b) `mod` p
  Fp a - Fp b = Fp $ (a - b) `mod` p
  Fp a * Fp b = Fp $ (a * b) `mod` p
  fromInteger x = Fp $ x `mod` p
invertFp = (^(p-2))

And again for n, the order of the curve:

n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
data Fn = Fn { unFn :: Integer } deriving (Show, Eq)
instance Num Fn where
  Fn a + Fn b = Fn $ (a + b) `mod` n
  Fn a - Fn b = Fn $ (a - b) `mod` n
  Fn a * Fn b = Fn $ (a * b) `mod` n
  fromInteger x = Fn $ x `mod` n
invertFn = (^(n-2))

We also define a Num typeclass instance for the group of points over the curve y2 = x3 + 7 mod p. The (*) operator does point addition while (+) is left undefined. We get point multiplication with (^) for free.

We represent point at infinity with Nothing, and finite points with Just (x, y) where x and y have type Fp. It is here we use (<|>) gratuitously, because its Maybe instance happens to capture point addition involving the point at infinity.

data G = G { unG :: Maybe (Fp, Fp) } deriving Show
instance Num G where
  G (Just a) * G (Just b) = G $ pointAdd a b
  G a * G b = G $ a <|> b
  fromInteger 1 = G Nothing
pointAdd (px, py) (qx, qy)
  | px /= qx            = slope $ (qy - py) * invertFp (qx - px)
  | py == qy && py /= 0 = slope $ 3*px^2 * invertFp (2*py)
  | otherwise           = Nothing
  where
  slope t = Just (rx, ry) where
    rx = t^2 - px - qx
    ry = (px - rx)*t - py

[We’re abusing Num to represent rings and groups. For G, an alternative is to import Data.Semigroup and define Semigroup and Monoid instances, in which case point mulitplication is mtimesDefault.]

The secp256k1 base point:

base = G $ Just (
  0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
  0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)

One nice feature of the secp256k1 curve is the ease of finding y-coordinates corresponding to an x-coordinate. The two solutions are negations of one another, thus we can identify them with a parity bit.

We define a function that returns the y-coordinate with the desired parity corresponding to a given x-coordinate.

ySolve x parity = if unFp y `mod` 2 == parity then y else -y
  where y = (x^3 + 7)^((p + 1) `div` 4)

Then the heart of ECDSA verification is the following:

verify pub z r s = case base^(unFn $ z*s1) * pub^(unFn $ r*s1) of
  G Nothing -> False
  G (Just (x, _)) -> unFp x == unFn r
  where s1 = invertFn s

[I find it odd that the signer sends s, which the verifier must invert before use. It’s the only reason we bother defining Fn above rather than hard-wiring a couple of multiplications modulo n. Wouldn’t it be better to send its inverse in the first place? It seems to be the same amount of work for the signer.]

By the way, in real life more checks should be performed. For example, we should confirm the public key indeed lies on the curve and has the right order, and that r and s lie in the right range.

We test with our signature above on the empty message. The first byte of our public key is 0x03, indicating a y-coordinate of parity 1. The other bytes represent the x-coordinate.

test_emptyMessage = verify pub z r s where
  x = 0xa283bd123cae19c9f2150c69ba84c5f28a89b889d28d7976640de012dabfc9a9
  pub = G $ Just (x, ySolve x 1)
  z = 0xe3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
  r = 0xc78518b1412498a231548f113895bd2ce0e274c1d7cc77dc7048ea36472952f7
  s = 0x1a67918fe6a0d586167c36359aac088deb5796b1b84ad400549accef10f3d6de

💡