Threshold ECDSA Signatures

Roadmap
1

Summary

ECDSA signatures are widely used in the blockchain industry. This feature will enable Canisters to have an ECDSA public key and to sign with regard to it. The corresponding secret key is threshold-shared among the nodes of the subnet holding the Canister. This is a prerequisite for the integration of the Internet Computer with Bitcoin and Ethereum.

Status
Discussing

What you can do to help

  • Ask questions
  • Propose ideas

Key people involved

Jens Groth (@JensGroth), @Jan , Dieter Sommer (@dieter.sommer ), Victor Shoup (@victorshoup ), Manu Drijvers (@Manu), Andrea Cerulli

Timelines

  • 1-pager posted on the forum for review: September 10, 2021
  • Community Conversation with Victor Shoup: September 16 2021
  • NNS Motion Proposal (to approve design + project) submission: September 20, 202115:00 UTC
  • NNS Motion Proposal (to approve design + project) expiration: September 22,2021, 15:00 UTC
  • If NNS Motion Proposal passes, implementation + deploy would take months: Q4 2021.

Description

ECDSA signatures are widely used and will be a feature of the Internet Computer. The most important use case is the integration of the Internet Computer with the Bitcoin and Ethereum blockchains. On those blockchains transactions are ECDSA signed with respect to a public key that represents the assets holder. In order to fully integrate with those external blockchains, canisters on the Internet Computer should be able to have Bitcoin or Ethereum public keys and create ECDSA signatures to authorize transactions.

It is clearly not acceptable that any node on the Internet Computer holds and thus learns a private signing key, because the trust model of the Internet Computer is defined such that up to a third of the node machines hosting a canister may be arbitrarily faulty. The solution is to have private keys secret shared among all node machines running a canister and create the signature through threshold cryptography. That is, if a threshold of the nodes participates in and completes the signing protocol correctly, the output of this protocol is a valid signature. On the other hand, a few nodes that do not meet the threshold cannot sign an unauthorized message by themselves.

The main challenges in this feature are to define and implement a secure multi-party computation protocol to realize the threshold ECDSA signature scheme and to integrate it with the Internet Computer protocol stack. Further challenges around the core protocol are the secure distributed key generation protocol as well as a secure key backup and recovery scheme for the private signing keys.

Goal: canisters and users can ask the IC to create ECDSA keys and signatures

To reach scoped status: we need an MVP spec giving assurance the goal is achievable and on which we can estimate engineering steps and effort

Draft plan: ECDSA calls will be IC Management canister calls

  • Story (Execution and Bitcoin integration): write spec for ECDSA methods offered by IC Management canister, they will only be available on dedicated subnets
  • Story (Execution): decide on ECDSA cycle cost and billing
  • Epic (Message Routing): store ECDSA requests in an appropriate place for Consensus-ECDSA module to read them + store deterministic replicated state for ECDSA protocols
  • Epic (Consensus): poll MR (Message Routing Layer, the layer between Consensus and Execution) for new and state of existing ECDSA operations
  • Epic (Consensus): return responses to ECDSA requests to MR + agree on any intermediate state that is replicated across all participating nodes and return it to MR
  • Epic (Consensus/P2P/Crypto?): store state that is individual to nodes and not replicated
13 Likes
3

They have been worked a lot in TSS

10 Likes
4

Hi Diego,
thank you for writing this up, very insightful! I have two questions:

  • Is it possible for canister to request multiple ECDSA public keys?

  • What does MR refer to?

1 Like
5

I am not sure, I think Victor or @Manu may best suited to answer this. They are wrapping up some work, so I expect this thread to be more active next week.

This refers to “message routing.” This is the layer between Consensus and Execution. It is responsible for routing messages to the right smart contract canisters. I will update this in the summary.

2 Likes
6

Will a threshold signature scheme work for ECDSA? I thought BLS could be aggregated easily without many rounds of interactivity, but the same was not true for ECDSA. How does the team propose to solve this and improve on the work of Goldfeder and others?

2 Likes
7

Yes, we are planning to support that! Ideally we’ll do something like BIP32 to allow canisters to derive many public keys.

5 Likes
8

Cool, thank you!

How are access rights being checked? E.g. how to make sure that only the canister that “owns” the public key is able to request a signature?

1 Like
9

You are right that while BLS is relatively easy to implement as a threshold scheme, ECDSA is quite a bit more challenging. This paper (“A Survey of ECDSA Threshold Signing”, by Aumasson, Hamelink, and Shlomovits, see eprint 2020) surveys the state of the art for threshold ECDSA protocols (as of last year). Unfortunately, none of these protocols really satisfy all of our design constraints: they either assume a synchronous network or they allow a single faulty node to prevent signatures from being issued (i.e., they do not guarantee output delivery) or both.

We have designed new protocols that work in an asynchronous setting and which guarantee a signature is produced when requested, even if some nodes are faulty (but we do assume that less than one third are faulty, as usual in all of our protocols). Our new protocols rely on our consensus protocols. They also perform pre-computations that will ensure that when a signing request comes in, it should be satisfied with just a single round of communication (no consensus needed).

We are writing a couple of papers that detail our protocols and their security analysis. We hope to make these public soon!

10 Likes
10

Hi all, I’m Victor and I’m on the threshold ECDSA team. I’ll do my best to answer any questions that you may have.

6 Likes
11

I can see some progress being made already: Update from revision 8a5b9a2e1468dfb286c77084a9b3597b9e3993b5 · dfinity/ic@35dd8f9 · GitHub

:fire:

4 Likes
12

Access to the ECDSA signing key is controlled through some “system API”. Canisters can call this API in a way that is very similar to how they can call other canisters. In the system API, we simply keep track of which canister makes the signing request, and then the replicas of the subnet will collaboratively sign with that canister’s key. Does that make sense?

5 Likes
13

Ooh, sounds exciting!

1 Like
14

What is the probability that we end up not ever getting canister ability to hold ICP and it is instead implemented with this api where the canister has to instantiate an ephemeral key for access? It isn’t a terrible idea…but I also don’t want to wait. :grimacing:

2 Likes
15

Yes that makes sense, thank you! So you only need one “main” key that signs for derived public keys too?

16

I thought folks would find it helpful to get some context on Victor’s background:

a. Victor Shoup - Wikipedia
b. ‪Victor Shoup‬ - ‪Google Scholar‬

6 Likes
17

Update : Now that Increased Canister Storage has gone through community-wide voting, this is the next project (1 of multiple concurrently) that will go through a similar open design process and voting.

2 Likes
18

I assume these operations are mostly asynchronous, right? So I assume it wouldn’t be exposed via the System API directly, but rather via a virtual canister that you call asynchronously, like the existing access to secure randomness?

6 Likes
19

I assume these operations are mostly asynchronous, right? So I assume it wouldn’t be exposed via the System API directly, but rather via a virtual canister that you call asynchronously, like the existing access to secure randomness?

Hey Joachim! Yes you’re exactly right, thanks for clarifying that.

3 Likes
20

Copied from the Bitcoin thread:

I was listening to @Manu’s explanation on the podcast this morning and a question occurred to me.

The IC is secure because the subnets can refresh the public key and switch it out for a new key via a zk generation of a key portion. They can do this a bunch so bad actors have limited time to coordinate(I don’t know how often this actually happens…would be great to know).

With BTC and ETH integrating, we need to control addresses and contracts from a specific identity. Once these are generated and on chain, you can’t really swap them out(unless the contract you are interacting with supports it). So will these keys be inherently less secure? If I ask the subnet to generate an address for me, I’m guessing all nodes have a bit of the key. If >2/3 decide I have too much at my address they could collude to take it? And they have infinity amount of time to do this because I can’t change the key on the remote chains?

What if more than 1/3 of the original nodes that generated your key portions go offline permanently? The IC can just add new nodes and generate a new public key…ETH and BTC won’t be able to do this.

I’m probably missing something here, but I think it is worth understanding.

Edit: I’m sure on ETH you could overcome this by always sending requests through a wallet-like contract that has the functionality for swapping out keys…not sure about BTC.

1 Like
21

I thought subnets refresh their private key shares, but the public key doesn’t change. Does that resolve your worries?

2 Likes