The process of Distributed Key Generation is the first requisite step. MPC wallets utilize certain specialized algorithms for generating valid signatures. These algorithms exhibit properties based on the type of signature to be computed, and all fall under the broad category of Threshold Signature Schemes (TSS). As the name implies, these algorithms enable the creation of a valid signature once a particular participation threshold is attained.
Threshold Signature Scheme (TSS) algorithms can differ in terms of message exchange among participants and the computation required to reach the final outcome. We will discuss some of the most popular solutions in the following sections to understand their advantages and shortcomings. As our focus is on signature algorithms, we'll presume participants have already undergone a key generation or sharing phase, meaning they each have a share of a global key-pair.
It's critical to note that the schemes presented herein aim to develop solutions independent of the blockchain used for transaction submission. Alternatives that involve multiple blockchain accounts or multi-signature wallets are not considered in this document, though they may present viable solutions in certain cases.
ECDSA
The Elliptic Curve Digital Signature Algorithm (ECDSA) is the most frequently used signature algorithm in the crypto ecosystem, adopted by both Bitcoin and the Ethereum Virtual Machine. While ECDSA has been a stable and dependable choice for traditional uses, adapting it to a threshold scheme has proven challenging due to its one-time-use random component included in the signature's equation. Any breach in the generation of this term could lead directly to the exposure of the signer's private key.
Fast, Secure Two-Party ECDSA Signing
Yehuda Lindell's work provides a solution to the TSS challenge for ECDSA by limiting the number of signing parties to two – the pair capable of reconstructing the global secret. The popularity and practicality of this algorithm have led to its adoption in some recent and actively used libraries, such as the OKX threshold-lib, the BNB-Chain tss-lib, and the Particle Network wallet service.
The signing sub-protocol utilizes the Paillier cryptosystem due to its additive homomorphic properties, and the signature's random component is computed in the Diffie-Helman style. It operates on the presumption of party correctness, and leverages zero-knowledge proofs to verify important messages contain the expected information.
This signing protocol completes in four message rounds, with the protocol initiator ending up with the final complete signature. The original paper also outlines the number of operations required by each party for message verification and calculation.
In this process, the first party carries out seven elliptic curve (ec) multiplications alongside a Paillier decryption. Conversely, the second party performs five ec multiplications, one Paillier encryption, one Paillier homomorphic addition, and one Paillier homomorphic scalar multiplication. The computational cost of any other operations involved pales in comparison to those already enumerated.
Fast, Secure Multiparty ECDSA with Practical Distributed Key Generation
This ECDSA alternative recently received updates in May 2023 to implement an efficient MPC protocol for ECDSA in a t-out-of-n context. No public open-source library currently implements it, but three of the four authors are associated with Coinbase, indicating the company's interest in this direction. A parallel work, GG18, provides a similar solution.
The protocol takes five rounds, and a key computational improvement involves eliminating the use of more expensive Paillier keys in favor of ElGamal keys over elliptic curves.
EdDSA
Edwards-curve Digital Signature Algorithm (EdDSA), a variant based on Edwards curves, is another option. The most widespread implementation utilizes the elliptic curve Curve25519, which is referred to as ed25519, and is relied upon by the Solana blockchain.
For threshold signatures, ed25519 proves quite adaptable, and custom cryptographic tools are not required. Rather, protocol must simply formalize the necessary messages. Given the signature equation, only small adjustments are needed. In particular, considering the two components of the signature (R; S) both elliptic curve points, it is necessary to cooperatively compute a common R, based on the message to sign, random values and the global public key, while the S can be then computed by summing up individual partial signatures. The IETF provides some proposals and documentation for TSS EdDSA.
In this configuration, the threshold signature can be completed in three communication rounds, allowing entities to compile a valid signature. An initial commitment to a random partial R is needed, then the decommitment of such value allows each individual to compute the partial signature, and finally with the third round entities can put together a valid signature.
Comparison
The table below broadly outlines the primary characteristics of the discussed TSS solutions.
The demonstrated configurations highlight the applicability of certain schemes to diverse use cases. The t-out-of-n setting is the most general one, with the only constraint being t <= n.
The required rounds before a valid signature can be issued by any participant in the protocol is also a key consideration when choosing a solution, as it represents the number of times each party must interact with the others. For a wallet user, in a conventional usage scenario, they sign a transaction and submit it to a blockchain node, requiring just one communication before the transaction reaches the mempool. However, with TSS, once a user employs their TSS wallet to sign a transaction, they must wait for the prescribed message exchanges (seen in the Rounds column) before the transaction is ready for inclusion in the blockchain mempool. The "Implemented" column summarizes the current usability of the schemes from a developer's perspective. Developers unfamiliar with implementing cryptographic algorithms can rely on existing libraries.
Conclusion
We've examined some of the most recent and popular proposals for Threshold Signature Schemes aimed at streamlining and decentralizing Web3 wallet interactions. Major players in the ecosystem are investing in research and development in this area, and new proposals are likely on the horizon. Meanwhile, existing works already provide secure solutions, and many services are being built on these protocols. It's up to the Web3 developers and users, armed with a basic understanding of the underlying processes, to decide what to request or integrate into their services.
