Threshold ECDSA Signatures

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

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

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

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

5 Likes

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

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

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

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

:fire:

4 Likes

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

Ooh, sounds exciting!

1 Like

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

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

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

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

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

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

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

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

2 Likes

That might resolve things. I’m guessing there are a large set of potential portion combinations that can be shuffled or reselected to keep the public key the same. Does it invalidate the old keys? I think that is the issue…if there are a set of previously available keys floating around or that eventually fall into the wrong hands then a bad actor could reconstitute. Of course, there are probably some cryptographic schemes that would allow for a very distributed set of portions…but I’m not sure how to deal with historic portions. Perhaps I need to go back and watch those key-sharing videos from the launch!

1 Like

My understanding is that the main innovation of chain key technology is that there is an eternal public key that has a corresponding “private key” maintained by a dynamic set of participants who hold secret key shares. When I looked into the paper, I believe a core component was that the secret key shares were safe against compromise because of the property of forward secrecy. Past shares can’t be used to compromise the key pair.

That’s my understanding, hopefully someone with actual expertise could back that up.

4 Likes