Multi-signature virtualization (Bitcoin and all ECDSA/EdDSA cryptocurrencies)

[vincenzo]

Hi,

first of all, I hope this is the right board for this topic: if not, please feel free to move it to the most appropriate one.

I am the co-founder of Conio, an Italian-based startup focused on custody of Bitcoin. We have recently worked with the University of Trento on a research project on threshold signatures.

In short, we have been able to generalize the concept of multi-signature, with a 2-of-3 solution that does not require all parties to be online, resulting in a single signature transaction to the underlying blockchain. This approach can be applied to any cryptocurrency, even the ones that do not natively support multi-signature (e.g. Ethereum).
More importantly, it can be applied to Bitcoin and reduce current multi-signature transactions to a single signature transaction: this leads to improvements in transaction size/fees, privacy (no parties public keys are revealed), and trust (private key is never created).

Info here: https://medium.com/conio/custody-at-conio-part-3-623292bc9222

It's a topic that needs further revisions, and I truly appreciate technical feedback.
We will also be at the Bitcoin Optech workshop in London this February 5: happy to chat in person if you're also there.

Thank you very much,
Vincenzo

[AB de Royse777]

In short, we have been able to generalize the concept of multi-signature, with a 2-of-3 solution that does not require all parties to be online, resulting in a single signature transaction to the underlying blockchain.

Help me to understand: You are saying in a multi sig concept you are doing something that will not require more than one party online? Why do all need to be online at all?

For instance, in a two by three - to broadcast a tx the minimum requirement is two sign for the tx by at least two key owners. They do not need to be online and wait for each others. One can sign the tx and the other one can come after a year and can sign the tx before to broadcast.

Besides, in a multi sig if it does not require more than one party to broadcast a tx then why do we even need it?

Your topic seems to be in the right section by the way.

[pooya87]

i skimmed through the article and i have to say the process you are trying to create sounds a lot like Schnorr's aggregated signatures where multiple parties create multiple keypairs (one each) then communicate the public keys and come up with a single signature in the end.
i have to spend more time going through the details to see how you are proposing to do it using ECDSA since the algorithm is not designed for such things.

by the way there is already a well designed method called MuSig proposed (found here: https://eprint.iacr.org/2018/068.pdf) that solves some problems with the key communication and also uses the inherent properties of Schnorr signature algorithm to create that singular aggregated signature from multiple participants.

[vincenzo]

Help me to understand: You are saying in a multi sig concept you are doing something that will not require more than one party online? Why do all need to be online at all?

Thanks for your reply. I skipped some details, so my apologies if I was not clear.

Briefly, we use threshold signatures to emulate, from a user point of view, the same flow as multi-signature. But it's not the classic multi-signature scheme used in Bitcoin.
In usual threshold signatures schemes, all parties need to be online to interact in rounds of multi-party computation. Our solution is able to avoid it, and keeps one of the three parties offline. The party offline is used for emergency situations, for example to recover funds when the user has lost his/her secret.

I hope it is more clear now.

Your topic seems to be in the right section by the way.

Thanks.

[vincenzo]

i skimmed through the article and i have to say the process you are trying to create sounds a lot like Schnorr's aggregated signatures where multiple parties create multiple keypairs (one each) then communicate the public keys and come up with a single signature in the end.
i have to spend more time going through the details to see how you are proposing to do it using ECDSA since the algorithm is not designed for such things.

by the way there is already a well designed method called MuSig proposed (found here: https://eprint.iacr.org/2018/068.pdf) that solves some problems with the key communication and also uses the inherent properties of Schnorr signature algorithm to create that singular aggregated signature from multiple participants.

Thanks for your reply. Regarding scaling, the importance of Schnorr + Taproot is indisputabile. However, Schnorr requires implementation on the consensus layer (even if soft fork). The scheme we propose works on top of such layer (as you see, supporting both ECDSA and EdDSA) and creates a signature same as a P2PKH/P2WPKH, independent from the number of parties involved.

In addition, unlike the usual threshold signatures solutions, ours does not requires all parties to be online (as I just answered Royse777 above), and also allows for a BIP32-like key derivation.

Please let me know if you have questions. Thanks for sharing the paper BTW.

[fillippone]

This is something very interesting if, as you said, works on top of current bitcoin protocol.
Hope to hear more about this in the future!

[pooya87]

i am not a cryptography expert but here are some thoughts after reading the paper more.

* the algorithm seems to be way too long and complicated and it also contains certain steps that require addition of cryptography classes that are not currently present in any of the bitcoin clients and possibly not even in some of the cryptography libraries. for instance i haven't seen Paillier anywhere. so if a wallet wanted to implement this scheme they would have to implement it from scratch. for instance Electrum that relies on python-ecdsa and/or libsec256k1 crypto libraries won't be able to do it since neither one have it. and complicated algorithms are harder to both verify for security and implement without bugs.

* you mention EdDSA, and since it is basically Schnorr algorithm it also supports native multi-signature algorithms (aggregating signatures). example: https://crypto.stackexchange.com/questions/50448/schnorr-signatures-multisignature-support

* the use case of this scheme is very specific and limited since it is adding a certain level of centralization. in any scheme the focus is always on keeping things still decentralized and keeping user in 100% control. which means user must be able to access his funds without needing anybody else as the last resort (for example the multi-sig designs where user controls 2 out of 3 keys and the third party has 1 key. the scheme is 2of3 and user keeps 1 key online and uses the third party to provide the second signature but user can recover that cold-stored key and access his funds without the server too).
in this design user will always rely on a third party and if both A and B go away, he won't be able to recover his funds anymore, although risks of both going away may be low.
a solution could be to increase the size of the redeem scripts a little bit with a condition. something like this:

Code:

IF
  <The multi-pubkey> CheckSig
Else
  <The user's individual and separate pubkey> CheckSig

the first expression would be for general use with the scheme described in OP and the second expression is the last resort where user creates a key pair and keeps it secret so that if some day he needed to recover funds without A or B he could.
although this may be over-kill but i personally like to know that i still have 100% control.

[vincenzo]

Thanks a lot for your feedback Pooya. You gave us some food for thought.

* the algorithm seems to be way too long and complicated and it also contains certain steps that require addition of cryptography classes that are not currently present in any of the bitcoin clients and possibly not even in some of the cryptography libraries. for instance i haven't seen Paillier anywhere. so if a wallet wanted to implement this scheme they would have to implement it from scratch. for instance Electrum that relies on python-ecdsa and/or libsec256k1 crypto libraries won't be able to do it since neither one have it. and complicated algorithms are harder to both verify for security and implement without bugs.

The complexity of the algorithm stems from the offline requirement of one of the parties. Usually threshold signature schemes require all parties to be online at the same time and have rounds of multi-party computation: though, that's not the design we want to support.
As for Paillier, we need an additive-homomorphic encryption scheme. Paillier has this property, but we are not bound to Paillier: anything equivalent would be fine (we considered El Gamal, but it does not work well here). If you have any suggestion, please let me know.

* you mention EdDSA, and since it is basically Schnorr algorithm it also supports native multi-signature algorithms (aggregating signatures). example: https://crypto.stackexchange.com/questions/50448/schnorr-signatures-multisignature-support

The main problem is not the signature aggregation per se, but requiring a threshold of signatures. The answer to the link refers to a draft research paper (https://datatracker.ietf.org/doc/draft-ford-cfrg-cosi/) that introduces the concept: I am not sure if the research has been completed or if it has been implemented, but it is indeed a great read. Thanks for the pointer.

* the use case of this scheme is very specific and limited since it is adding a certain level of centralization. in any scheme the focus is always on keeping things still decentralized and keeping user in 100% control.

Yes, you're right. I know this is a sensitive subject, but for my experience normal people, sooner or later, often end up losing their keys. And when that happens, they're too scared to deal with crypto anymore. This scheme removes total control, but at the same time allows for recovery. A trade-off geared to the non-tech savvy person, not to the expert.
I like the solution you suggest, but the weak link is still the single key on the backup side (which can be lost or stolen).

although this may be over-kill but i personally like to know that i still have 100% control.

I totally understand. But unfortunately most people are still not familiar with the technology and do stupid mistakes (see Peter Schiff...). There are no perfect solutions on custody for any kind of person.

[fillippone]

<...>
This scheme removes total control, but at the same time allows for recovery. A trade-off geared to the non-tech savvy person, not to the expert.
I like the solution you suggest, but the weak link is still the single key on the backup side (which can be lost or stolen).

Also, I might add, this scheme is useful to investor who are, by compliance, obliged to have some security in holding their funds.
I am thinking about, just tossing a guess, investment funds in cryptocurrencies, where there is an involvement from the fund, the trading desk, and the depositary entity of the fund itself.
This solution could be used in such situation where conflicts might arise from different agent.