Threshold ECDSA Signatures

Roadmap
30

Hi all!

In this post we’ll share a more concrete design on how we can integrate threshold ECDSA signatures into the internet computer. Please give us feedback! Similarly to the proposal for “increased canister storage”, we plan on submitting an NNS motion proposal for the community to vote on whether the final version of this design should be implemented.

NNS Proposal: threshold ECDSA signatures

Objective

We want canisters to be able to hold BTC, ETH, and for them to create Bitcoin and Ethereum transactions. Since those networks use ECDSA, a canister must be able to create ECDSA signatures. We do not want the corresponding secret key to be part of the replicated canister state, so instead the secret key will be shared among the replicas of the subnet, and they must be able to collaboratively create threshold ECDSA signatures whenever a canister makes a signature request.

Proposal

Canister interface

  • Requesting a signature: Canisters will be able to request a signature using the following method. When the derivation_path is set, the message is signed with the corresponding private key derived from the canister key.
sign_with_ecdsa : (record {
    message_hash : blob;
    derivation_path : opt blob;
}) -> (record {
    signature : blob
});
  • Retrieving the public key: Canisters will ask for their public keys via the following API. When the derivation_path is set, the corresponding public key is returned.
get_ecdsa_public_key : (record {
    derivation_path : opt blob;
}) -> (record {
    public_key : blob
});

Creation of ECDSA signatures

Every subnet will have a single ECDSA key pair for efficiency reasons. From that, we can apply standard key derivation mechanisms to derive per-canister keys. Canisters can then further derive many keys using BIP32 key derivation.

Creating the requested ECDSA signatures

Threshold ECDSA signatures are much more difficult to construct than threshold BLS signatures, which we already use on the Internet Computer. Threshold BLS signatures only require one secret key shared among the replicas. For ECDSA, we also need a secret key shared among the replicas, but additionally, we need several more shared values, and those values can only be used for a single signing request. This means that we will need to do many distributed key generations to be able to answer signing requests. For efficiency reasons, we will use an interactive DKG protocol (unlike the non-interactive DKG we use for BLS), as the interactive version is computationally more efficient. The full cryptographic details of the interactive DKG and threshold ECDSA signing will be published in a paper that should appear in the following weeks.

The consensus layer will orchestrate these interactive DKGs: blocks are extended with some extra payload indicating

  • which tuples of shared secrets are available for signing requests,
  • which signature requests are paired with a tuple or shared secrets and are ready for threshold signing,
  • Information about which interactive DKGs should be ongoing, which adds new shared secrets from which we can replendish the set of available tuples.
  • Completed signatures that can be delivered back to the canister

A separate component for threshold ECDSA will handle most of the real work based on the information in the block chain:

  • It creates & gossips the interactive DKG messages
  • It creates & gossips ECDSA signature shares
  • It creates & gossips completed ECDSA signatures by aggregating sufficiently many ECDSA signature shares

This component builds on the crypto component, and the consensus/crypto interface will be extended with methods to create dealings/validate interactive DKG messages, create/validate signature shares, and aggregate/validate ECDSA signatures.

Risks

  • Subnets cannot tolerate more than 1/3rd of the replicas being malicious. The threshold ECDSA feature also builds on that assumption: if a subnet has too many colluding malicious parties, they can create signatures on a canisters behalf without a canister’s approval.

Alternatives considered

  • Non-interactive DKG: for BLS signatures, we currently use a non-interactive distributed key generation algorithm, which has the advantage that it’s simpler conceptually and easier to integrate into the blockchain. This however requires computationally intensive zero-knowledge proofs. Since ECDSA signatures require many DKGs per signature, we believe we need a more efficient solution, and therefore prefer an interactive DKG.

Testing & Quality Assurance

This is a highly security-critical feature of the Internet Computer as substantial value in terms of Bitcoin and Ether will be secured with it in the future. Thus, the implementation of the feature needs to be covered by accordingly stringent automated testing. Clearly, unit tests and integration tests will be used to assure the correctness of individual methods and components, respectively.

System tests will help ensure that the feature as a whole works as intended and does not interfere with the behaviour of the Internet Computer in unintended ways. System tests are written using a Rust-based framework and spin up testing subnets for the feature in a testing environment. Production tests likewise end-to-end test the feature, however in an environment that is as close as possible to the future production environment. For example, our production testing framework will spin up a test Internet Computers with node machines in geographically distributed data centers to run our end-to-end tests for the feature. An area where production tests can give helpful insight is the identification of performance bottlenecks.

One specific example of a production test that we intend to write is that of a replica leaving the subnet while it is responsible for making a signature.

In addition to testing, we will perform a thorough security review of the threshold ECDSA implementation towards the end of the project, ensuring that the implementation truthfully and securely implements the protocol.

Rollout plan

This feature will be steered by a feature flag in the subnet record in the registry. That means that via proposals this feature can be enabled/disabled. Initially, we’ll disable this on all subnets, and we can via NNS proposals enable this feature on specific subnets.

We will mark the exposed API of the feature as experimental at initial launch. Once we have gained sufficient experience with the feature in a real-world production setting and its use by the community, we will mark it as no longer being experimental.

Timeline

Given the complexity of the feature and requirements for a rigorous quality assurance, we anticipate multiple months of engineering and testing effort. Optimistically we aim to complete this feature in 2021, but we clearly cannot compromise on quality and correctness of the implementation.

12 Likes