shielded K-of-N multisig using a tree of K-choose-N MultiRedDSA keys

[daira]

Someone asked how we proposed to do shielded K-of-N multisig, and I realised that my idea for how to do that hadn't been written up yet. #782 describes a complicated and inefficient approach using "partial spends", but there's a much better approach.

Assume that we've already implemented N-of-N shielded multisig using MultiRedDSA, as described in #3729.

To generate a K-of-N multisig address:

• The N parties each generate their key pair (ask_i, vk_i) and broadcast all of the vk_i to each other.
• Each party constructs the N-choose-K MultiRedDSA keys for sorted K-of-K subsets of the vk_i.
• They each construct a Pedersen hash Merkle tree over the compressed public keys, and verify that they have all obtained the same Merkle root akm.

The Spend circuit is modified to allow akm to be used in place of ak in the input to CRH^ivk. That is, add a Merkle tree check that akm is the root of a tree of fixed depth m containing ak. For compatibility, there is an extra private boolean input is_multisig that determines whether to use this Merkle check, or just directly check akm = ak. We also include is_multisig as input (probably in the personalization) to CRH^ivk.

Signing is essentially the same as for K-of-K. Verification of spend authorization signatures is oblivious to whether the key is multisig: you verify with a randomized key in the same way as in Sapling.

Advantages:

• Multisig public keys are indistinguishable from non-multisig public keys.
• Payments to and from shielded multisig addresses are indistinguishable from non-multisig payments.
• Scanning for incoming payments is the same.
• Leverages effort spent on specifying and implementing N-of-N multisig.
• Hardware wallets can authorize payments from K-of-N multisig addresses with essentially the same effort as N-of-N.
• It is easy to generalise this scheme to more complicated authorization structures, e.g. where one key is more important than the others, provided the number of authorized combinations remains within the bound 2^m.
• Changes in the consensus protocol are mostly isolated to the Spend circuit itself.

Disadvantages:

• Requires a Spend circuit upgrade, so the earliest it could be done is NU4, activating in October 2020. (No circuit upgrade is proposed for NU3.)
• For simple K-of-N, it requires that N-choose-K ≤ 2^m for some fixed m.
  • Bitcoin is theoretically able to support multisig addresses up to N = 15 for P2SH addresses, but only using non-standard transactions. A 7-of-15 or 8-of-15 key would require depth m = 13 in our multisig scheme.
  • If we restrict m to 7, for example, then we can accomodate up to any K-of-9; or {1,2,3,7,8,9,10}-of-10; or {1,2,N-2,N-1,N}-of-N for N in {11..16}; or {1,N-1,N}-of-N for N up to 128.
• Has a circuit overhead of m Merkle layers of Pedersen hashes (plus negligible bookkeeping). Each layer costs ~1380 constraints. For example, m = 7 has a roughly 9.5% overhead relative to the current Spend circuit size (although if we are updating the circuit, we can probably also apply some optimizations that were left out of Sapling).