Introducing Multi-Party ECDSA library

Since we started KZen, we invested in the development of a cryptographic stack that would enable us to build a new generation of keyless crypto wallets with simpler and stronger security eliminating that way typical single point of failures and tedious setup and recovery schemes. 

Multiparty-ECDSA is our open-source cryptography library, written in Rust, for threshold ECDSA. This library is continuously developed and maintained by KZen since July 2018 to be used in ZenGo wallet. The library has evolved and is being successfully used nowadays by several other innovative projects in the blockchain space:

ThorChain is one of the public consumers of the library

This blog post is our official technical introduction to the library, accommodating the recent publication of the library audit. We hope it will extend the reach of the library and make it more accessible to projects who might benefit from it.

Some elements of background

Prof. Gennaro is one of the pioneers of threshold signatures research. He is also the author of one of the papers we implemented.

In Multiparty computation (MPC), a set of parties that do not trust each other try to jointly compute a function over their inputs while keeping those inputs private. 

“Threshold signature” is an instance of multiparty computation where the function to be computed is a cryptographic digital signature. ECDSA is one type of such a signature scheme, based on elliptic curves. ECDSA is used in Bitcoin, Ethereum and across the industry. 

To generate a signature one needs at least t+1 participants out of the total of n participants running the code. For example,  in the 2 party case, we have t=1 and we need both parties in order to sign. This is opposed to regular ECDSA where only a single signer is needed. In multisig scheme on the other hand, the same distributed signing can be achieved but the signature itself will look different, non-standard, giving away the identities of the signers.

In fact, threshold ECDSA is a set of two protocols: one for key generation in a distributed way, followed by another for ECDSA signing with key shares without ever combining them in a single place. 

 For a comprehensive write-up on threshold signatures, check out the Binance-academy article we published.

Potential use cases are many and we refer the reader to our Scaling-Bitcoin slides for a list with examples. 

Multiparty-ECDSA implements three of the mentioned in the article protocols for threshold ECDSA: 

  • [Lindell17] is a 2 party protocol with exceptionally fast signing time. 
  • [GG18] is a protocol for any threshold t of corruption and parties n 
  • [CCLST19] is a 2 party protocol slower than [Lindell17] that relies on better security assumptions

The library is the only audited open source code for threshold ECDSA today. 

Library core design principles

  • Multi-protocol support: The library currently provides an implementation for 3 protocols. We believe that the three of them are a good cross-section between state of the art and support for tradeoffs. The implementer role is to consider the various tradeoffs and choose the protocol that works best for his use case.
  • Built for cryptography engineers: threshold ECDSA protocols are multi-step, interactive protocols that utilize cryptographic primitives and zero-knowledge proofs. We built the code as close as possible to the protocol in the original paper. This way, the code is most understandable and cryptographic changes can be easily explained. In ZenGo we use a separate library just to wrap Multiparty ECDSA in a message format that will be usable to devs to interact with.
  • Foolproof:  secret data cannot be accessed and can be manipulated only via minimal API. State machine structure: higher rounds of computation can be called only once lower rounds have completed successfully.
  • Black box use of cryptographic primitives: The library is focused on the protocol level, all cryptographic primitives used are consumed from other well-established libraries. Concretely, Curv for elliptic curve cryptography, zk-paillier for paillier cryptosystem and our class-group library are all in the cryptographic layer below Multiparty-ECDSA. This is why the library can work with different elliptic curves for example.

Library security and audit 

The library was audited by Kudelski security between August and October 2019. The report can be found here and their note about the work can read here. We are happy to share no critical issue was found and all other secondary issues found were addressed by our team. The audit methodology is described on pages 4-5 of the report. 

The Multi-party ECDSA audit report

Auditing advanced cryptography is challenging. Kudelski has done a great job analyzing the code and its security and we urge implementers to read the audit report as it contains multiple insights on design choices we made. The cryptographic design was reviewed independently by our advisor Prof. Claudio Orlandi.

Some important disclosures: Side-channel attacks are considered much harder in a protocol where the secret is distributed. Therefore, the library was not tested against side-channels and only some best effort was put into it. 

Complementary code to explore further  

Multiparty-ECDSA library is not handling communication and network. We provide in the repo an example of [GG18] protocol that is handling communication using a trustless relay server. We have another project, called White-city where we offer a more advanced network architecture that is using Tendermint BFT SMR.

In our use case, we use the library for building a threshold wallet. In a short white paper we describe how to do it in a 2 party setting based on [L17]. We have a full demo code of a 2 party wallet called Gotham-city where in addition to the distributed key generation and distributed signing we support also secret share rotation and recovery of secret shares. Both algorithms are supported in Multiparty-ECDSA API but implemented in a wrapper library

Support, contributions and bug bounty

We feel fortunate to have so many members of the community engaging with the code at different levels: some contributed improvements on Rust and programming, some on cryptography. Some of the most serious bugs we had, were discovered with the help of the community. We are thankful to all. This is the magic of open-source and we remain committed to building more in that direction.

At ZenGo we put emphasis on security and our code is no different. We are highly available for feedback so feel free to reach out via the issue tracker, email or our research group telegram chat with any question or idea. Pull-requests are welcome and all will be treated fast and with the highest level of professionalism.

Finally, if you think you find a bug, we would be happy to reward you. If you believe it to be critical please send us an email before reporting and we will open a secure communication channel for the reporting.

Closing notes

We heard people call our github “Cryptography Disneyland”. While it is true we have a passion for advanced cryptography and experimentation, Multiparty-ECDSA library is at the core of what we are doing. A great amount of effort was put to build this new tool for threshold signing that will be secure and efficient. We think it is critical in earning and building more trust in what we do. We hope it can become useful for you as it is for us. 

We believe Multipart-ECDSA is a fundamental improvement to key management and will help the industry grow in adoption and use cases. Many already see the potential and we believe more will join soon to build more core code, apps, and services.