1
$\begingroup$

I have a blockchain wallet with a single signature wallet, is there a way of making this wallet "multi-signature"? F.e can we use some secret sharing scheme to distribute the single private key among custodians? What I need in the end is to make several users control access to a single wallet.

$\endgroup$
  • $\begingroup$ You'll need to be more specific here in order to get a useful answer. What kind of wallet are you talking about? Are you talking about a single specific wallet which you already created and you now need to share between multiple users without changing the public key, or are you talking about designing a new kind of wallet which needs to interoperate with existing verifiers, or are you designing a new system altogether for which interoperability with existing verifiers is not necessary? $\endgroup$ – Squeamish Ossifrage Mar 20 '18 at 10:23
  • $\begingroup$ When I answered, I assumed you meant that you already have a specific wallet whose public key is already fixed and which you now want some subset of several users, say $k$ of $n$, to have to agree on any transactions with the wallet before they are valid. But it's possible I read too much into your phrasing. $\endgroup$ – Squeamish Ossifrage Mar 20 '18 at 10:27
2
$\begingroup$

(Responding to Squeamish Ossifrage) Threshold signatures do not require any single member to reconstruct the whole secret. Ideally each party produces a partial signature and only when they are all combined is the signature valid.

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

This enables a pre-determined group to share a single schnorr identity without changing the verification side of the protocol. Any subset of $k$ members may collaborate to sign a common message. The secret sharing is verified and the dealer cannot cheat. The co-signers cannot be tricked by their peers.

MuSig: n-of-n threshold schnorr via aggregation

MuSig also doesn't change the verification side. A group is derived from the list of all public keys required to sign the common message. With only two-rounds of communication, the group produces the signature.

Crypto conditions: off-chain contracts resolving to minimal proofs of execution

Crypto-conditions are a form of multi-sig contract that doesn't attempt to aggregate any identities. Instead it uses hash commitments to commit to some boolean circuit. I.e. A contract may require "either Alice, or both Bob and Carol", or any arbitrary logic. The contract is a single hash. The proof of execution reveals only the relevant branches. The contract is valid if all leaves are valid and all intermediate steps have appropriate thresholds.

ANY-k is implemented as k-of-n. OR/ANY as 1-of-n. AND/ALL as n-of-n. A fullfillment may be either a hash-lock that is just a revealed symmetric secret key, or a signing public key whose corresponding secret signs the transaction that it approves.

Any irrelevant (or dead/unresolved) branches are truncated to a single hash commitment; enabling an arbitrarily large contract to resolve to a minimal proof.

Conclusion

I believe it would be worth implementing all of these. Notably $(t,n)$ enables a group to divide their signing right such that no single, or fewer-than-t subset may impersonate the group. N-of-N MuSig enables opportunistic groups to compress the crypto-condition contracts, which can describe any boolean circuits - not just subsets or all.

bonus: BLS is signature scheme that supports aggregation of many distinct-signatures. But this is not schnorr-friendly and does not work with any curves not explicitly designed to be pairing-friendly.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, it the first protocol applicable to bitcoin? waves? $\endgroup$ – Solon Mar 23 '18 at 3:33
  • $\begingroup$ @Solon Yes, it could be used for cryptocurrencies. Is it? AFAIK not yet. But there have been efforts in switching to schnorr to enable MuSig; which would imply being able to use $(t,n)$. $\endgroup$ – cypherfox Mar 23 '18 at 3:36
  • $\begingroup$ the question is can I do it by myself? can I share bitcoin/waves private key, between n nodes to allow only a set of k to produce a signature? without changing chain verification method $\endgroup$ – Solon Mar 23 '18 at 3:38
  • $\begingroup$ Using ECDSA? No. If you switch to say Ed25519, an EdDSA that uses schnorr, then yes. There may be other ways for ECDSA, but I don't follow ECDSA because EdDSA is far more useful. $\endgroup$ – cypherfox Mar 23 '18 at 3:41
  • $\begingroup$ With BTC and other ECDSA, you must use the "script" to implement multisig. I'm not versed in the BTC script language, but I'm pretty sure they have a fat-$(t,n)$ variant. $\endgroup$ – cypherfox Mar 23 '18 at 3:41
0
$\begingroup$

In principle, yes, if you destroy the inputs to the secret-sharing scheme—but the moment any one party assembles all the shares to make a signature, that party has the unilateral power to make signatures until you destroy that party. So the party who reassembles the secret is a single point of eternal failure every time you need to make a signature.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I understand the drawback of this approach, that is why I only used it as examples, is there any schemes that don't have such problem? $\endgroup$ – Solon Mar 20 '18 at 2:25
  • $\begingroup$ Yes: real threshold/collective signatures, a.k.a. multisignatures. See this question for a quick sketch of a limited $n$-of-$n$ one (which requires no changes to verifiers) and some references to relevant literature. But you will need to make a new wallet even for the limited one sketched there with all the parties participating in the key generation—and change the software in the verifiers if you use a $k$-of-$n$ threshold signature scheme for $k < n$ that they don't already support. $\endgroup$ – Squeamish Ossifrage Mar 20 '18 at 2:30
  • $\begingroup$ So, if I have simple asymmetric encryption wallet I can only implement n-of-n threshold, but not k-of-n? $\endgroup$ – Solon Mar 20 '18 at 3:10
  • $\begingroup$ @Solon Threshold signatures aren't about encryption — they're about signature. Imagine a document with two lines on which to sign, which is valid only if two different authorized parties sign it. Whether your particular kind of wallet can even be adapted to use an $n$-of-$n$ threshold signature like I sketched depends on what kind of signature scheme it uses. Need a lot more details to say what you can and can't do with your particular wallet. E.g., I suspect the $n$-of-$n$ scheme I sketched can't be made to work with ECDSA, so it's no good for Bitcoin (though BTC has multisig wallets). $\endgroup$ – Squeamish Ossifrage Mar 20 '18 at 3:17
  • $\begingroup$ @SqueamishOssifrage You can use a verified signature sharing scheme with a threshold signature scheme without enabling any party (not even the dealer) to recover the secret key. Each party produces a partial signature. See my answer for a reference. $\endgroup$ – cypherfox Mar 20 '18 at 4:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.