From 3595c30acd59068b8a3d5150bc74157950c59b19 Mon Sep 17 00:00:00 2001 From: Pieter Wuille Date: Mon, 21 Oct 2019 16:16:47 -0700 Subject: Improve section on alternatives to OP_CHECKMULTISIG --- bip-tapscript.mediawiki | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) 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 OP_IF and OP_NOTIF opcodes must be either exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1)'''Why make MINIMALIF consensus?''' This makes it considerably easier to write non-malleable scripts that take branch information from the stack.. * '''OP_SUCCESSx opcodes''' As listed above, some opcodes are renamed to OP_SUCCESSx, and make the script unconditionally valid. * '''Signature opcodes'''. The OP_CHECKSIG and OP_CHECKSIGVERIFY are modified to operate on Schnorr public keys and signatures (see bip-schnorr) instead of ECDSA, and a new opcode OP_CHECKSIGADD is added. -** The opcode 186 (0xba) is named as OP_CHECKSIGADD. '''OP_CHECKSIGADD''' This opcode is added to compensate for the loss of OP_CHECKMULTISIG-like opcodes, which are incompatible with batch verification. OP_CHECKSIGADD is functionally equivalent to OP_ROT OP_SWAP OP_CHECKSIG OP_ADD, but only takes 1 byte. All CScriptNum-related behaviours of OP_ADD are also applicable to OP_CHECKSIGADD.'''Comparison of CHECKMULTISIG and CHECKSIG''' A CHECKMULTISIG script m ... n CHECKMULTISIG with witness 0 ... can be rewritten as script CHECKSIG ... CHECKSIGADD m NUMEQUAL with witness ... . Every witness element w_i is either a signature corresponding to the public key with the same index or an empty vector. A similar CHECKMULTISIGVERIFY script can be translated to bip-tapscript by replacing NUMEQUAL with NUMEQUALVERIFY. 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 CHECKSIGVERIFY ... CHECKSIGVERIFY CHECKSIG. 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. +** The opcode 186 (0xba) is named as OP_CHECKSIGADD. '''OP_CHECKSIGADD''' This opcode is added to compensate for the loss of OP_CHECKMULTISIG-like opcodes, which are incompatible with batch verification. OP_CHECKSIGADD is functionally equivalent to OP_ROT OP_SWAP OP_CHECKSIG OP_ADD, but only takes 1 byte. All CScriptNum-related behaviours of OP_ADD are also applicable to OP_CHECKSIGADD.'''Alternatives to CHECKMULTISIG''' There are multiple ways of implementing a threshold ''k''-of-''n'' policy using Taproot and Tapscript: +* '''Using a single OP_CHECKSIGADD-based script''' A CHECKMULTISIG script m ... n CHECKMULTISIG with witness 0 ... can be rewritten as script CHECKSIG ... CHECKSIGADD m NUMEQUAL with witness ... . Every witness element w_i is either a signature corresponding to the public key with the same index or an empty vector. A similar CHECKMULTISIGVERIFY script can be translated to bip-tapscript by replacing NUMEQUAL with NUMEQUALVERIFY. This approach has very similar characteristics to the existing OP_CHECKMULTISIG-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 CHECKSIGVERIFY ... CHECKSIGVERIFY CHECKSIG. 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 ≥ 6'', 3-of-''n'' for ''n ≥ 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. ===Rules for signature opcodes=== -- cgit v1.2.3