Is Sharding a Good Alternative to MultiSig?

Question

For security reasons, we require that each withdrawal be "approved" by multiple servers so that in the event that a single server is compromised the attacker won't be able to siphon funds from the entire wallet. The typical approach used to execute this concept is a MultiSig address where the transaction is only approved after it is signed by multiple entities.

However, the fees for a 2/3 MultiSig transactions are nearly twice as high as fees for a regular transaction. If we wanted 3/4 (or higher) MultiSig the fees would be even costlier. This got me thinking of a way to take advantage of the security benefits offered by MultiSig transactions without suffering from excessive fee consumption in the process.

The immediate solution that comes to mind is sharding. In short, instead of using MultiSig we can safely break up the PK using Shamir's Secret Sharing Scheme with unlimited schemes (such as 4-of-7 or 3-of-4 etc) and store the shards on separate servers thereby requiring multiple servers to "sign" a withdrawal request.

Does MultiSig provide any (security) benefit over sharding? Is sharding a viable alternative to MultiSig?

Update:

Perhaps the only problem with this proposal is that each server cannot independently "authorize" the transaction using its "shard". At some point, all shards would need to be known to "reassemble" the PK so the attacker could still use this as the "weakest point of attack"? Is this correct?

Thanks

asked 1 hour ago

S.O.SS.O.S

2131 silver badge7 bronze badges

Pieter WuillePieter Wuille 63.6k7 gold badges138 silver badges207 bronze badges · Answer 1

Advantages of OP_CHECKMULTISIG over Shamir Secret Sharing for k-of-n:

There is no need to reconstruct the actual secret key on one specific machine. With SSS, you're inherently relying on that one machine being able to verify that what it's going to sign is what is intended - otherwise you may e.g. be sending your entire balance instead of just the payment you wanted to make. Also, if that key or (in case BIP32 public derivation is used) any related key is ever reused, that machine being compromised would in fact expose your entire wallet, including future funds. Given that the end goal is reducing the need to rely on the security of a single device, this is not ideal. Accountability: with an SSS-based signature, the on-chain signature cannot tell you which signer(s) actually signed for spending, while OP_CHECKMULTISIG does. If you want the ability to go after rogue signers.

Advantages of SSS over OP_CHECKMULTISIG:

Cheaper on-chain. Better policy privacy (you're not revealing on-chain that you were in fact using a multisig policy).

Now, with the hopefully upcoming activation of BIP 341-342 (Taproot) which includes support for BIP 340 Schnorr signatures, there will be more options (disclaimed: I'm a co-author of these proposals):

Native threshold signatures: with Schnorr signatures it is possible to perform something that's effectively equivalent to performing SSS on the public keys, and at signing time on the signatures, and end up with a valid combined signature for the combined public key. This gets you some of the advantages of both, and some additional disadvantages: No single machine where the private key needs to be combined on (only signatures ever get combined, which are only valid for the specific message the individual signers signed). Lack of accountability like SSS. Same on-chain cost as SSS. Same on-chain policy privacy as SSS. More complicated protocol that needs multiple interaction rounds between the signers. Also lots of edge cases to take into account to make this secure in practice. For recent work, see FROST. If all you need is n-of-n (rather than k-of-n), it is simpler and less involved; see e.g. MuSig2.

That's not the only option, though. More alternatives are listed in BIP 342, note 5. In a way, SSS and OP_CHECKMULTISIG are two extremes of a spectrum. For example, you can construct an output that contains a Merkle root of a tree for which every leaf is one k-of-k aggregated key. It can be spent by revealing the Merkle branch plus the aggregated signature. This is usually cheaper than OP_CHECKMULTISIG-like constructions that publish all keys and signatures, but not as good as the SSS-like approaches give you. On the other hand, it's simpler too.

Is Sharding a Good Alternative to MultiSig?

Not the answer you're looking for? Browse other questions tagged bitcoin-core transactions security private-key multi-signature or ask your own question.