multi-sig account without collaborative setup

We've been using gnosis-safe.io in some internal projects, and it works fine. It's a multi-sign (potentially with security policy support) smart contract that once deployed, can hold assets and accepts transactions with 2-out-of-n. Victor asked if αw supports multi-sig what will it look like.

I think that αW user base is mostly individuals, the ease of use (including easy setup and maintenance) is the priority. Setting up a multi-sig contract and securing it over time requires a vender such as gnosis-safe. A lightweight approach is more feasible.

I had this discussion with 丁晟超 more than 2 years ago. His memo is attached to the end of this message, which mentioned a paper with an off-chain (contract-less) multi-sign method.

Speaking of usability, I wonder if it supports 'direct-use' or 'setupless'. That is if it supports the following use flow:

  1. Alice has an address book in which there is Bob's public key†.
  2. Alice, of course, has her own private and public key.
  3. Without any further communication with Bob, Alice can compute a 2-out-of-2 multi-sig public key with Bob.
  4. Alice can make arrangements in such a way that cryptocurrency is sent to the address of the multi-sig public key.
  5. When Alice needs to spend the cryptocurrency held on the address of the multi-sig public key, she can communicate with Bob, once, with the message (the transaction that spends the money), and Bob can complete the multi-sig and broadcast the transaction.

If such usage is acceptable, it would be ideal as it doesn't involve smart contract, therefore not opening up attack surface and the maintenance issue that comes with it.

† (in practices, by knowing Bob's Ethereum address and can observe at least one transaction signed by him, therefore can recover his public key from Ethereum blockchain).


Memo from 丁晟超 Shengchao Ding

I have a quick glance at the paper "Secure Two-party Threshold ECDSA from ECDSA Assumptions" by Doerner et.al, which is published at IEEE S&P 18'. One of the author Eysa Lee also presented this work at TPMPC this year. The fourth author abhi shelat is a professor at Northwestern and a leading researcher in MPC community.

Here's my memos of this paper:

  1. In theoretical cryptography, there's the result that any multiparty computation function can be computed in two rounds, and two rounds is the bottom bound of round complexity.
  2. A threshold signature themes can be seen as a multiparty computation functionality. In this view, it seems that a "atomic" threshold signature requires at least two rounds communication. In the real scenario, it is also reasonable. Take the 2-out-of-2 case as an example, Alice makes a request to implement the 2-out-of-2 threshold signature, it sends some information to Bob, and Bob make some information to reply, thus concludes the 2 round.
  3. This work is not a generic k-out-of n threshold ECDSA case, it deals with the specific 2-out-of-n case, where k=2. The author said it can be extended to k-out-of-n case in TPMPC presentation, but I haven't find how to extend in their paper yet.
  4. This work achieves the bottom round complexity bound, i.e. there are only 2 rounds during the signing phase. (A "one-time" setup phase needs 5 rounds.)
  5. The cryptographic assumptions of this work is the same as ECDSA, which previous works don't achieve.
  6. The scheme is proved to be secure in the Universal Composable Model in the malicious adversary setting.
  7. Authors make an open source implement in Rust: neucrypt / mpecdsa · GitLab, the experimental results in both LAN and WAN setting can be found in the paper: https://eprint.iacr.org/2018/499.pdf

BTW, 2 other papers regarding this topic:

The papers mentioned solve a bit of a different issue than multi-signatures. Basically all these papers consider threshold signatures. For the intent and purpose you mention in this post, the difference is that in the papers show how a single public key is generated in a way where the private key is secret shared between the parties doing the generation. That is, these works show how to generate a single key from scratch and not how to combine two already existing ECDSA keys into a valid third ECDSA key. So unfortunately the case you describe will not be possible. Furthermore, both the paper referenced (and all other threshold ECDSA papers I know of) require some sort of interaction between Alice and Bob to do signing (although some recent work have shown how to do this before they know the message to be signed). Most work on multi-signatures consider Schnorr signatures for which it is possible to do what you ask. But unfortunately since this is not ECDSA it cannot be used directly to sign transactions.

Thanks that's very helpful to know!

If the setup process can be done without knowing the future message to be signed first but requires communication between multi-sig partners, it would still be useful. With such a method, there is not much usability improvement but only security (no smart contract attack surface) and cost (no contract-cost) advantage. So I still like to hear it.

Okay, cool! In that case I think this is the paper you are interested in Cryptology ePrint Archive: Report 2020/492 - UC Non-Interactive, Proactive, Threshold ECDSA. They show how to construct (interactively) a shared private key for ECDSA and how to (interactively) preprocess signatures before the messages to be signed is known. (This means that they can preprocess e.g. 1000 signatures and then will only need to interact again once they have (non interactively) signed those 1000 messages).

Once the message to get signed is known to both parties they can locally compute a share of the signature based on their key share and the data preprocessed. The signature shares are additive and thus can very simply be added together by any of the parties to construct the real, standard ECDSA signature.

I should mention that it is not a terrible inefficient protocol, but quite complex and using a lot of fancy cryptography. So it will be cumbersome to implement, but doable.