Threshold ECDSA
Overview
This page gives a high-level outline of chain-key ECDSA signatures on ICP. Some of the information in this section is not required to use the feature, but may be of interest to the technically inclined reader for obtaining background information on the technology. ICP implements the threshold ECDSA protocol by Groth and Shoup as described in their Eurocrypt 2022 paper. Groth and Shoup have also published a comprehensive design and analysis of this distributed signing protocol.
At a high level, the threshold ECDSA implementation on ICP features multiple protocols as outlined next, all of which are crucial for a secure system setup and operation. Note that this goes far beyond just threshold ECDSA signing, which is the reason for calling this a protocol suite for chain-key ECDSA signatures.
- Key generation: this protocol is executed on a specified subnet; it generates a new threshold ECDSA key such that the private key is secret shared over the replicas of this subnet.
- XNet key re-sharing: this protocol re-shares an ECDSA key from a source subnet to a target subnet. It results in the same key being secret shared over the replicas of the target subnet using a different random secret sharing (potentially over a different number of replicas than the sharing in the source subnet uses).
- Periodic key re-sharing: this protocol re-shares an ECDSA key within the subnet it is secret shared on. This helps protect against an adaptive attacker that attempts to compromise replicas over time as every key resharing makes the previously-obtained key shares worthless.
- Computing pre-signatures, signing: these protocols compute signatures with the secret-shared private key. A protocol for computing pre signatures, i.e., quadruples that are used in the actual signing protocol, is run asynchronously to signing requests to precompute pre-signatures. This precomputation protocol computes the vast majority of the steps of creating threshold ECDSA signatures. A signing protocol is triggered by a signing request of a canister. A signing protocol consumes one precomputed quadruple to efficiently compute a threshold ECDSA signature.
- Public key retrieval: allows for retrieving a public key of a canister, including potential BIP-32-like key derivation based on a canister-provided derivation path.
It is crucial to note that the private key never exists in a reconstructed form, and only in secret-shared form during its whole lifetime, whether that is the key's generation, the re-sharing of the key within a subnet or from one subnet to another, or when computing signatures.
Various NNS proposals have been implemented to perform key management, i.e., initial key generation and key re-sharing. Those proposals are used to define on which subnet to generate an ECDSA master key, to which subnet to re-share the key for better availability, and which subnet to enable for answering signing requests.
ECDSA keys
ECDSA-enabled subnets hold what are called threshold ECDSA master keys, generated with the key generation protocol on selected subnets of ICP. A master ECDSA key is a key from which canister ECDSA keys can be derived, i.e., a single master key for a given elliptic curve suffices for the derivation of an ECDSA key for each canister on ICP, the canister root key, using an extension of the BIP-32 key derivation mechanism with the canister's principal as input. The key derivation is executed transparently by the protocol as part of the signing and public key retrieval APIs. See the level-0 key derivation in the below figure for the derivation of canister root keys from a master key.
From a canister root key, an unlimited number of ECDSA keys can be derived for the canister using a backward-compatible extension of the BIP-32 key derivation mechanism. The extension allows not only 32-bit integers, but arbitrary-length byte arrays, to be used as input for each level of the key derivation function. See the levels 1 and greater in the below figure illustrating the derivation of further canister keys based on the canister root key. This derivation is supported by the ECDSA API through the ecdsa_public_key method.
The derivation of further ECDSA keys from a canister root key can be done without involvement of ICP as well to facilitate certain use cases.
Threshold ECDSA master keys are always referred to through key identifiers in the threshold ECDSA API (as well as in the NNS proposals for managing the rollout). The key identifiers comprise an elliptic curve name and an identifier, e.g., an example key identifier is the 2-tuple (secp256k1, test_key_1). Those key identifiers are used by the system to refer to the correct key, e.g., for selecting the key share when computing a signature or in the implementation of the XNet routing of API calls and responses to/from the ECDSA-enabled subnet holding the key with the corresponding identifier.
There are currently two master keys deployed, a test and a production key.
(secp256k1, test_key_1): the test key deployed on a single 13-node subnet.(secp256k1, key_1)the production key deployed on two high-replication subnets, one activated for signing, and the other one for backing up the key for better key availability.
Deployment
Next, this guide outlines the deployments for the Chromium (Beta) release and the general availability release.
Chromium release (Beta)
As part of the Chromium release, only a test key for curve secp256k1 has been deployed on one subnet with a replication factor of 13. This key may be deleted with an according NNS proposal some time after the GA release and therefore should not be used for anything that has value, but only for development and testing purposes. More concretely, it is, for example, strongly advised against holding real bitcoin with the test key as those Bitcoin would be lost when the key gets deleted. The test key is rather intended to facilitate development of Bitcoin smart contracts and hold Testnet bitcoin as preparation for the GA release. The test key has the id (secp256k1, test_key_1) for referring to it in API calls.
General availability release
A single threshold ECDSA production key for the secp256k1 elliptic curve has been deployed with the GA release. The key with id (secp256k1, key_1) will be maintained in secret-shared form on two different subnets with high replication factor (around 30 nodes initially). The key will be initially generated on a high-replication subnet and kept there and re-shared to a new high-replication subnet using the re-sharing protocol. The latter subnet will be activated to act as the active signing subnet for this key. The further will hold the key in secret-shared form for backup purposes for achieving better key availability, but will not respond to signing requests. In case of the unlikely event of one of the subnets getting destroyed beyond recoverability, the approach of key replication improves key availability by allowing for the key to be re-shared to a different subnet, should this ever be required in case of a disaster.
Further Aspects
For both the current Chromium deployment with a test key and the GA release with a production key, requests to the threshold ECDSA API are always XNet requests because the ECDSA-enabled subnets do not host user's canisters, thus some seconds of extra latency is incurred due to Xnet communications from the calling canister's subnet to the threshold-ECDSA-enabled subnet holding the respective key and communicating the response back.
Support for further elliptic curves and additional corresponding master keys may be added in the future. The curve secp256r1 is interesting for supporting use cases such as decentralized certification authorities (CAs) and is the premier candidate group to be added to facilitate use cases like the mentioned one.
API
Next, this guide gives an overview of the API for threshold ECDSA. For the authoritative specification, the reader is referred to the corresponding part of the Internet Computer interface specification. The API comprises two methods: ecdsa_public_key for retrieving threshold ECDSA public keys, and sign_with_ecdsa for requesting threshold ECDSA signatures to be computed from the subnet holding the secret-shared private threshold ECDSA key.
Each API call refers to a threshold ECDSA master key by virtue of a 2-part identifier comprising a curve and a key id as outlined above. Derivation paths are used to refer to keys below a canister's root key in the key derivation hierarchy. The key derivation from the master key to the canister root key is implicit in the API.
ecdsa_public_key: this method returns a SEC1-encoded ECDSA public key for the given canister using the given derivation path. If thecanister_idis unspecified, it will default to the canister id of the caller. Thederivation_pathis a vector of variable length byte strings. Thekey_idis a struct specifying both a curve and a name. The availability of a particularkey_iddepends on implementation.
For curvesecp256k1, the public key is derived using a generalization of BIP32 (see ia.cr/2021/1330, Appendix D). To derive (non-hardened) BIP-0032-compatible public keys, each byte string (blob) in thederivation_pathmust be a 4-byte big-endian encoding of an unsigned integer less than 231.
The return result is an extended public key consisting of an ECDSApublic_key, encoded in SEC1 compressed form, and achain_code, which can be used to deterministically derive child keys of thepublic_key. This call requires that the ECDSA feature is enabled, and thecanister_idmeets the requirement of a canister id. Otherwise it will be rejected.sign_with_ecdsa: this method returns a new ECDSA signature of the givenmessage_hashthat can be separately verified against a derived ECDSA public key. This public key can be obtained by callingecdsa_public_keywith the caller'scanister_id, and the samederivation_pathandkey_idused here.
The signatures are encoded as the concatenation of the SEC1 encodings of the two valuesrands. For curvesecp256k1, this corresponds to 32-byte big-endian encoding.
This call requires that the ECDSA feature is enabled, the caller is a canister, andmessage_hashis 32 bytes long. Otherwise it will be rejected.
An example of the API can be found below:
ecdsa_public_key : (record {
canister_id : opt canister_id;
derivation_path : vec blob;
key_id : record { curve: ecdsa_curve; name: text };
}) -> (record { public_key : blob; chain_code : blob; });
sign_with_ecdsa : (record {
message_hash : blob;
derivation_path : vec blob;
key_id : record { curve: ecdsa_curve; name: text };
}) -> (record { signature : blob });
Note that in case of high system load, a request to compute an ECDSA signature may time out. In this case, the canister may want to back off and retry the request later.
API Fees
The fees for the ECDSA signing API are as defined below. The threshold ECDSA test key resides on a regular-sized (13-node) application subnet, while the threshold ECDSA production key resides on an about 30-node-sized fiduciary subnet. The subnet size of the subnet where the threshold signature key resides and the signatures are computed define the resulting cost. The size of the subnet of the calling canister does not matter for the fees. For costs in USD, the USD/XDR exchange rate as of of November 23, 2022 has been used.
If a canister using this feature is intended to be blackholed, but also for other canisters, it is recommended to send more cycles with the call than the advertised cost of the call so that if the subnet size of the signing subnet increases in the future, the higher costs per signature are still covered. Any cycles not charged in a call are refunded.
Fees for the t-ECDSA Test Key
| Transaction | Description | Cycles (test key) | USD |
|---|---|---|---|
| Threshold ECDSA signing | For computing one threshold ECDSA signature (sign_with_ecdsa) | 10_000_000_000 | $0.0130886 |
Fees for the t-ECDSA Production Key
| Transaction | Description | Cycles (production key) | USD |
|---|---|---|---|
| Threshold ECDSA signing | For computing one threshold ECDSA signature (sign_with_ecdsa) | 26_153_846_153 | $0.0342317 |
Environments
In order to facilitate developers throughout the canister development lifecycle on ICP, the feature is available in both the SDK for local development and testing as well as on ICP for pre-production testing and production operation of canisters.
SDK
The development of canisters is typically done in the developer's local environment, facilitated by use of the SDK. The SDK has been extended such that the management canister API for threshold ECDSA is available in the local canister execution environment. Thus, canisters using the threshold ECDSA API can be run locally for development and testing purposes. The feature is always enabled in the SDK, so no further user action is required in order to make use of the API.
When the replica of the SDK environment is first started up, a new ECDSA key is generated. This key is then stored in non-volatile memory so that it does not change with every restart of the replica.
For the technically interested readers, it is important to note that the SDK uses the exact same implementation of threshold ECDSA as the mainnet, but only runs a single replica. Thus, the protocol is operating with a single replica, which means it degenerates to a special case and incurs only little overhead, e.g., for key generation and signing, and can thus remain enabled by default in the SDK without noticeably affecting performance of the SDK environment. Also note that the signing throughput and latency in the local SDK environment is not representative for the throughput and latency on ICP.
Internet Computer
Any canister on any subnet of ICP can call the threshold ECDSA API exposed by the management canister. The calls are routed via XNet communication to the ECDSA-enabled subnet that holds the key referred to in the API call (only one such signing subnet holding a test key and one signing subnet holding the production key are available currently). Note that this test key is hosted on a subnet with a replication factor of only 13 and may be deleted in the future, thus it should not be used for anything of value, but rather solely for development and testing purposes. The main intended purpose is to facilitate the development and testing of Bitcoin-enabled dapps using Bitcoin testnet.
As part of the general availability (GA) release of the feature, a production ECDSA key on the secp256k1 elliptic curve has been deployed to be used for integration with the Bitcoin Mainnet and other use cases of interest.