Threshold ECDSA: The Key Ingredient Behind the Internet Computer’s Bitcoin and Ethereum Integrations
The design of threshold ECDSA signatures sets the stage for the IC’s integrations with Bitcoin, Ethereum, and other blockchains.
By Victor Shoup, Principal Research Scientist| DFINITY
The Internet Computer’s approach to direct integrations allows a decentralized blockchain to securely authenticate and interact with other blockchains and systems without involving intermediaries. Where previous cross-chain solutions have relied heavily on bridges, oracles, and custodial services, involving single points of failure, the Internet Computer enables blockchain integrations with the strongest possible trust properties thanks to the absence of additional trusted parties.
A direct integration with Bitcoin, for example, empowers canister smart contracts to directly conduct Bitcoin transactions without an intermediary or bridge, providing a trustless foundation for DeFi projects using Bitcoin.
Recently, the DFINITY R&D team set the stage for the Internet Computer’s integration with Bitcoin, Ethereum, and other blockchains by designing a new protocol for threshold ECDSA (Elliptic Curve Digital Signature Algorithm). The feature’s innovative design realizes a trustless way of computing ECDSA signatures using a cryptographic multi-party protocol, with canister smart contracts controlling ECDSA signing keys on a public blockchain.
The protocol is detailed in this research paper, with much of the security analysis being done in a related research paper that was presented very recently at Eurocrypt 2022, an international conference on all aspects of cryptology organized by the International Association for Cryptologic Research. DFINITY also engaged the NCC Group, a world-class cybersecurity consulting firm, to conduct a security and cryptography review of the threshold ECDSA implementation. We encourage the community to read the report and comment on it in the Developer Forum.
Before threshold ECDSA
Prior to initiating Bitcoin integration, the Internet Computer had already provided a distributed signing protocol based on a particular signature scheme called BLS, which is named after its inventors, Dan Boneh, Ben Lynn (now at DFINITY), and Hovav Shacham. The main reason for choosing BLS signatures as the basis for a distributed signing protocol is that it is possible to implement a much simpler and more efficient distributed signing protocol based on BLS, compared to any other signature scheme. Unfortunately, Bitcoin does not use BLS signatures. Rather, Bitcoin and many other blockchains use the ECDSA scheme. Thus, to support Bitcoin integration, as well as integration with other blockchains such as Ethereum, the NNS community adopted a proposal to implement a distributed ECDSA signing protocol on the Internet Computer.
In order to fully integrate with these external blockchains, canister smart contracts on the Internet Computer must be able to have Bitcoin or Ethereum public keys, for example, and create ECDSA signatures to authorize transactions. The solution is to have private keys secretly shared among all node machines (replicas) of a large subnet 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. However, a few nodes that do not meet the threshold cannot sign an unauthorized message themselves.
While BLS is relatively easy to implement as a threshold scheme, ECDSA is substantially more challenging. The main challenges in this feature have involved defining and implementing 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 have involved the secure distributed key generation protocol as well as a secure key backup and recovery scheme for the private signing keys.
We have designed new protocols that work in an asynchronous setting and guarantee that 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). These new protocols rely on the Internet Computer’s consensus protocol. 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).
Why digital signatures?
At the heart of a Bitcoin transaction is a cryptographic gadget called a digital signature, which Bitcoin uses to securely implement transactions on the Bitcoin ledger (i.e., blockchain). Very briefly, in a digital signature scheme, a given user generates a public key together with a corresponding private key. The user can use the secret key, which only they know, to digitally sign an arbitrary message, obtaining a digital signature. Before adding this message to the ledger, not only must the signature under the public key be verified, but it must also be verified that the previous transactions on the ledger indicate that the user associated with the public key had sufficient BTC to fulfill the transaction.
Given the message, the public key, and the signature, any other user can verify that the digital signature is valid. The essential security property of such a scheme is that no one other than the user who generated the public key can generate a valid signature under that public key on any message.
In the integration of Bitcoin into the Internet Computer, the role of a given user as outlined above will be played by a canister smart contract. The question then becomes: how does the Internet Computer securely store the secret key associated with a canister? The answer is to use a distributed signing protocol. Recall that a canister is hosted on a subnet composed of many replicas. In a distributed signing protocol, the secret key is not stored directly by any one replica. Rather, this secret key is shared among all of the replicas in the subnet, so that if one, or even several, replicas in the subnet were compromised, the secret key would still be secure. However, since the secret key is not stored on any one replica, a distributed signing protocol must be used. Such a protocol consists of two subprotocols:
- The first subprotocol (called a distributed key generation protocol) runs once to generate the public key in such a way that each replica obtains its share of the secret key.
- The second subprotocol is invoked whenever a signature under the public key on a given message is requested by the canister — since no one replica holds the secret key, they must work together somehow to generate the signature.
A distributed signing protocol must be resilient, meaning that it must function reliably and securely while generating digital signatures on demand in a timely fashion even if one, or several, of the replicas in the subnet are crashed or under the control of an attacker.
Here are some of the key features of our new distributed ECDSA signing protocol:
- It guarantees security, meaning that the only signatures an adversary can obtain are those that are requested by honest replicas.
- Other than its reliance on the Internet Computer’s underlying consensus protocol, it works under the very weak assumption of asynchronous communication, meaning that it does not assume any a priori upper bound on the time required to deliver protocol messages.
- It works assuming that less than a third of the replicas are corrupt — this means arbitrary Byzantine corruptions.
- It provides guaranteed output delivery, meaning that all signing requests will be fulfilled and the resulting signatures will be delivered to the honest replicas (to the extent that all messages between honest replicas are eventually delivered, and the consensus subprotocol provides liveness).
- It provides a very efficient, non-interactive online signing phase, meaning that assuming an appropriate message-independent precomputation, in response to a signing request, each replica simply broadcasts one “signature share”, and collects sufficiently many such “signature shares” to then compute the signature; in particular, the (more expensive) consensus subprotocol is not needed in the online signing phase.
- It supports BIP32-style additive key derivation, which means that many signing keys can be easily derived from a single signing key in a hierarchical fashion.
Secure, direct and trustless
The Internet Computer’s Bitcoin integration is establishing a secure, direct, and trustless interface with the Bitcoin ledger that does not rely on centralized intermediaries. DFINITY’s development of threshold ECDSA enables every canister smart contract to control ECDSA signing keys and hold BTC directly on the Bitcoin blockchain.
Together, these innovations are making it possible for developers to build dapps and DeFi projects that natively use the largest cryptocurrency in the world, leveraging immense value and bringing advanced smart contracts to Bitcoin. Next-generation DeFi projects like Sonic, InfinitySwap, and ICPSwap are already developing lending and borrowing protocols and exchanges that directly involve BTC. Threshold ECDSA also lays the foundation for further research on the direct integration with Ethereum in the coming future and unlocks an array of use cases for the Internet Computer.
____
