Threshold ECDSA Signatures

That’s right: both for the existing “chain key technology” and the upcoming threshold ECDSA protocols, even though a public keys live forever, the sharing of the corresponding private keys (among the replicas in a subnet) is periodically refreshed, with old shares being erased. This is a concept known as “proactive security” (not exactly the same thing as “forward secrecy”, BTW, but certainly related). So as long as not too many shares leak in any short interval of time, the long-term security of the private key is assured.

9 Likes

Hi! I believe this video by Jens Groth may help. Skip to 16:40.

4 Likes

Update: we should have a 1-pager for the community to read tomorrow Friday September 10th. We will post then.

5 Likes

Hi folks, I updated the main description with the latest timeline.

4 Likes

Hey folks,

I just updated the timeline for this feature based on what we currently see as potential engineering scope (within an order of magnitude, and it will get clearer as we get more info).

2 Likes

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

Have you considered

    derivation_path : blob;

i.e. instead of having a “special” key (derivation_path = null) and then many named keys, conceptually just have one set of named keys per canister.

This avoids questions like: Is derivation_path = null and derivation_path = opt blob "" the same thing?

2 Likes

Hi Joachim
Nice to hear from you. Thank you for the suggestion. We could do that as well.
Cheers!

1 Like

(Not constructive comment:)
I can’t help but notice that if the Internet Computer application model would have a first class notion of capability, then “the right to ask the subnet to sign with a given private key” woudldn’t be eternally rigidly tied to a single canister, but could be moved around and shared. And the API would actually be easier (derivation path only relevant when creating the key and capability, but not further on). Maybe next time :wink:

(More constructive question:)
How will this interact with a hypothetical feature of moving canisters transparently from one subnet to another? Or splitting subnets? For example, the routing table is designed to allow that to happen; would canister-bound ECDSA signatures prevent that?

5 Likes

Seems like another risk is the subnet becoming corrupted somehow. If you lose the subnet, you lose the keys. If you’re going to go BIP32, what if the whole network used the same key? That way all subnets would have to fail. Maybe it is a bigger security risk because all nodes have a share of the key and collusion could be easier?

They had me at ‘consensus/crypto’ interface. Seriously tho’ skilesare think a comment u made on a previous thread that ‘present security’ applies is apropos. So if using zero knowledge proofs to decrypt my encryption (what’s in the box) is the heavy lifting now …ECDSA requires several more shared values which can only be used for a single signing request…. A symphony of communication orchestrated by a conductor beacon begets Perpetual Public Keys (FTW. :sunglasses:) Am sure that the stress testing will be front and center for all us. Will offer a comment and am happy to hear, down the road, if your results match , I think that u can push the non-malicious down to 60% from 66%. If there is such a thing as a faster time frame in this asynchronous platform ( the arrow of time putting the Tok after Tik ) u might be able to go to 30%. Again just a theory , there to be disproven. Looking forward to your seminal documentation.

Good point! Indeed, the current plan is that there will be a single master key that will be deployed in several subnets. Individual canisters will derive subkeys (as in BIP32) from this master key (we have been analyzing other derivation procedures, but for compatibility reasons, we will likely stick with BIP32). This means we can do disaster recovery as you suggest, unless all subnets on which the master key is deployed fail simultaneously. To protect the secrecy of the master key, any subnet that deploys the master key will have to meet certain security requirements (meaning, at the very least, it is “large enough”).

We have longer term plans to implement other disaster recovery strategies as well, but this is the initial plan.

7 Likes

Shouldn’t security requirements be “large enough” AND “distributed enough”?

The distributed enough means that a nation actor cannot expose a master-key deployed in a subnet with collusion with similar-minded nation actors.

2 Likes

Yes, good point! That’s why I said “at the very least” :slight_smile:

1 Like

Thanks, Victor.

This is an actual proposal with target dates. The community is banking on this proposal being implemented and deployed within ROM of time as projected out. In other words, this is, hopefully, no longer theoretical.

We know that setting up nodes/node providers take time. Therefore isn’t it time to fix what are the exact security requirements?

What is the exact definition of "large enough "? 17 nodes? 29 nodes? …

What is the exact definition of “distributed enough”? Do we think that we have an requirement of having node providers in Africa/South America prior to go live of this features?

Are there other such security features?

I fear that unless we fix these(and other) constraints, we will find that this proposal will get delayed by a lot. Additionally BTC/ETH integration has this proposal as a pre-requisites.

The community stands ready, I believe, to help. But we need you/dfinity to lead with open discussions about what are the key security considerations; so that we can provide constructive critiques(as many have done already).

1 Like

Fair enough! Part of the issue is that I’m not certain what level of detail is appropriate for this particular forum, or even for the NNS proposal. That’s mainly on me… I’m kind of a noob when it comes to these communication process issues.

In terms of the precise parameters for allowable subnet configs in this setting, I’ll get back to you on that soon.

1 Like

Thanks, Victor, for your candid response.

I believe that you/dfinity should think about the technical details embedded in the forum or the NNS proposal in the following ways (as two ends of a pendulum); especially for threshold signatures.

(WAY-1)

The theory: The algorithms are way too complicated for a regular reader of the forum/nns proposal to even understand. Posting a couple of papers which virtually nobody will understand will cause additional FUD for threshold signatures. The community should trust us/dfinity as the cryptographic experts on the algorithm and the implementation of the algorithm. Besides we don’t want to “open source” this critical piece of tech at this point in ICs dev ; so as not to give a leg up to our competition.

The practice: Assuming the correctness of the algorithm and its implementation, it still must be deployed on the IC. The key consideration of security and other requirements of such powerful technology will take substantial time to document and engage with the community; further delaying the deployment of powerful technology. The community in any event relies on us/dfinity to be the experts and we can always explain post-facto.

(WAY-2)
The theory: The algorithms are pretty complicated. They might have some hidden bugs/issues; which given enough eyes might lead to be surfaced. Besides the community would see this technology as pretty critical for them to trust IC with BTC/ETH. Let’s release the papers and implementation as soon as possible so as to get the public review started asap.

The practice: Assuming the correctness of the algorithm and its implementation, it still must be deployed on the IC. The community should be completely aware about the different tradeoffs (security and others) that we are making on the deployment of this powerful technology. They will then understand better the risk that they are taking on these tradeoffs. Perhaps they can convince us/dfinity that certain tradeoffs are not good enough and we can change our minds. Therefore let’s release this as well asap.

The truth, of course, will be in shades of gray. That said, I think that being transparent about what decision paths are being taken along these or similar dimensions would be extremely beneficial for the community at large.

2 Likes

Please see discussion (Threshold ECDSA Signatures - #39 by mparikh) on some additional requirements that MIGHT percolate up for system and integration testing.

Hi @mparikh !
The current plan is to enable this ability per subnet via an NNS proposal. That is why I believe whether a subnet meets the criteria could be discussed separately later, since the implementation of a project of this extent will take many months.

3 Likes

Do we have an ball park of what is large enough? I think this question will also be tied to “decentralized enough”. For example, is it a legitimate security threat if all the 17/29/… nodes belong to the same node provider?

Also I think we are way underestimating the amount of lead time required to establish node providers in other regions of the world.

Currently the projection is that threshold signature will be implemented in Q4, 2021. IF the requirements for a subnet is to be “decentralized enough” so that subnet will need node providers in South America & Africa, not sure about the time frame that that will take.

2 Likes