Improve section on alternatives to OP_CHECKMULTISIG

1 files changed, 5 insertions, 1 deletions

diff --git a/bip-tapscript.mediawiki b/bip-tapscript.mediawiki
index a325573..91ed97c 100644
--- a/bip-tapscript.mediawiki
+++ b/bip-tapscript.mediawiki
@@ -71,7 +71,11 @@ The execution rules for tapscript are based on those for P2WSH according to BIP1
 * '''Consensus-enforced MINIMALIF''' The MINIMALIF rules, which are only a standardness rule in P2WSH, are consensus enforced in tapscript. This means that the input argument to the <code>OP_IF</code> and <code>OP_NOTIF</code> opcodes must be either exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1)<ref>'''Why make MINIMALIF consensus?''' This makes it considerably easier to write non-malleable scripts that take branch information from the stack.</ref>.
 * '''OP_SUCCESSx opcodes''' As listed above, some opcodes are renamed to <code>OP_SUCCESSx</code>, and make the script unconditionally valid.
 * '''Signature opcodes'''. The <code>OP_CHECKSIG</code> and <code>OP_CHECKSIGVERIFY</code> are modified to operate on Schnorr public keys and signatures (see bip-schnorr) instead of ECDSA, and a new opcode <code>OP_CHECKSIGADD</code> is added.
-** The opcode 186 (<code>0xba</code>) is named as <code>OP_CHECKSIGADD</code>. <ref>'''<code>OP_CHECKSIGADD</code>''' This opcode is added to compensate for the loss of <code>OP_CHECKMULTISIG</code>-like opcodes, which are incompatible with batch verification. <code>OP_CHECKSIGADD</code> is functionally equivalent to <code>OP_ROT OP_SWAP OP_CHECKSIG OP_ADD</code>, but only takes 1 byte. All <code>CScriptNum</code>-related behaviours of <code>OP_ADD</code> are also applicable to <code>OP_CHECKSIGADD</code>.</ref><ref>'''Comparison of <code>CHECKMULTISIG</code> and <code>CHECKSIG</code>''' A <code>CHECKMULTISIG</code> script <code>m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG</code> with witness <code>0 <signature_1> ... <signature_m></code> can be rewritten as script <code><pubkey_1> CHECKSIG ... <pubkey_n> CHECKSIGADD m NUMEQUAL</code> with witness <code><w_1> ... <w_n></code>. Every witness element <code>w_i</code> is either a signature corresponding to the public key with the same index or an empty vector. A similar <code>CHECKMULTISIGVERIFY</code> script can be translated to bip-tapscript by replacing <code>NUMEQUAL</code> with <code>NUMEQUALVERIFY</code>. Alternatively, an m-of-n multisig policy can be implemented by splitting the script into several leaves of the Merkle tree, each implementing an m-of-m policy using <code><pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIG</code>. If the setting allows the participants to interactively collaborate while signing, multisig policies can be realized with [https://eprint.iacr.org/2018/068 MuSig] for m-of-m and with [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps threshold signatures] using verifiable secret sharing for m-of-n.</ref>
+** The opcode 186 (<code>0xba</code>) is named as <code>OP_CHECKSIGADD</code>. <ref>'''<code>OP_CHECKSIGADD</code>''' This opcode is added to compensate for the loss of <code>OP_CHECKMULTISIG</code>-like opcodes, which are incompatible with batch verification. <code>OP_CHECKSIGADD</code> is functionally equivalent to <code>OP_ROT OP_SWAP OP_CHECKSIG OP_ADD</code>, but only takes 1 byte. All <code>CScriptNum</code>-related behaviours of <code>OP_ADD</code> are also applicable to <code>OP_CHECKSIGADD</code>.</ref><ref>'''Alternatives to <code>CHECKMULTISIG</code>''' There are multiple ways of implementing a threshold ''k''-of-''n'' policy using Taproot and Tapscript:
+* '''Using a single <code>OP_CHECKSIGADD</code>-based script''' A <code>CHECKMULTISIG</code> script <code>m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG</code> with witness <code>0 <signature_1> ... <signature_m></code> can be rewritten as script <code><pubkey_1> CHECKSIG ... <pubkey_n> CHECKSIGADD m NUMEQUAL</code> with witness <code><w_1> ... <w_n></code>. Every witness element <code>w_i</code> is either a signature corresponding to the public key with the same index or an empty vector. A similar <code>CHECKMULTISIGVERIFY</code> script can be translated to bip-tapscript by replacing <code>NUMEQUAL</code> with <code>NUMEQUALVERIFY</code>. This approach has very similar characteristics to the existing <code>OP_CHECKMULTISIG</code>-based scripts.
+* '''Using a ''k''-of-''k'' script for every combination''' A ''k''-of-''n'' policy can be implemented by splitting the script into several leaves of the Merkle tree, each implementing a ''k''-of-''k'' policy using <code><pubkey_1> CHECKSIGVERIFY ... <pubkey_(n-1)> CHECKSIGVERIFY <pubkey_n> CHECKSIG</code>. This may be preferable for privacy reasons over the previous approach, as it only exposes the participating public keys, but it is only more cost effective for small values of ''k'' (1-of-''n'' for any ''n'', 2-of-''n'' for ''n &ge; 6'', 3-of-''n'' for ''n &ge; 9'', ...). Furthermore, the signatures here depend on the branch used, which means signers need to be aware of which other signers will be participating, or produce signatures for each of the tree leaves.
+* '''Using an aggregated public key for every combination''' Instead of building a tree where every leaf consists of ''k'' public keys, it is possible instead build a tree where every leaf contains a single ''aggregate'' of those ''k'' keys using [https://eprint.iacr.org/2018/068 MuSig]. This approach is far more efficient, but does require a 3-round interactive signing protocol to jointly produce the (single) signature.
+* '''Native Schnorr threshold signatures''' Multisig policies can also be realized with [http://cacr.uwaterloo.ca/techreports/2001/corr2001-13.ps threshold signatures] using verifiable secret sharing. This results in outputs and inputs that are indistinguishable from single-key payments, but at the cost of needing an interactive protocol (and associated backup procedures) before determining the address to send to.</ref>
 
 ===Rules for signature opcodes===