When Satoshi wrote the first version of bitcoin, s/he made what was almost
certainly an unintentional mistake. A bug in the original CHECKMULTISIG
implementation caused an extra item to be popped off the stack upon completion.
This extra value is not used in any way, and has no consensus meaning. Since
this value is often provided in the witness, it unfortunately provides a
malleability vector as anybody can change the extra/dummy value in the
signature without invalidating a transaction. In legacy scripts NULLDUMMY is a
policy rule that states this value must be zero, and this was made a consensus
rule for segwit scripts.
This isn’t the only problem with CHECKMULTISIG. For both ECDSA and Schnorr
signatures, batch validation could enable an approximate 2x speedup, especially
during the initial block download phase. However the CHECKMULTISIG algorithm,
as written, seemingly precludes batch validation for threshold signatures as it
attempts to validate the list of signatures with the list of pubkeys, in order,
dropping an unused pubkey only when a signature validation fails. As an
example, the following script
[2 C B A 3 CHECKMULTISIG]
Could be satisfied by the following witness:
[0 c a]
Where “a” is a signature for pubkey A, and “c” a signature for pubkey C. During
validation, the signature a is checked using pubkey A, which is successful, so
the internal algorithm increments the signature pointer AND the pubkey pointer
to the next elements in the respective lists, removing both from future
consideration. Next the signature c is checked with pubkey B, which fails, so
only the pubkey pointer is incremented. Finally signature c is checked with
pubkey C, which passes. Since 2 signatures passed and this is equal to the
specified threshold, the opcode evaluates as true. All inputs (including the
dummy 0 value) are popped from the stack.
The algorithm cannot batch validate these signatures because for any partial
threshold it doesn’t know which signatures map to which pubkeys.
Not long after segwit was released for activation, making the NULLDUMMY rule
consensus for segwit scripts, the observation was made by Luke-Jr on IRC[1]
that this new rule was actually suboptimal. Satoshi’s mistake gave us an extra
parameter to CHECKMULTISIG, and it was entirely within our means to use this
parameter to convey extra information to the CHECKMULTISIG algorithm, and
thereby enable batch validation of threshold signatures using this opcode.
The idea is simple: instead of requiring that the final parameter on the stack
be zero, require instead that it be a minimally-encoded bitmap specifying which
keys are used, or alternatively, which are not used and must therefore be
skipped. Before attempting validation, ensure for a k-of-n threshold only k
bits are set in the bitfield indicating the used pubkeys (or n-k bits set
indicating the keys to skip). The updated CHECKMULTISIG algorithm is as
follows: when attempting to validate a signature with a pubkey, first check the
associated bit in the bitfield to see if the pubkey is used. If the bitfield
indicates that the pubkey is NOT used, then skip it without even attempting
validation. The only signature validations which are attempted are those which
the bitfield indicates ought to pass. This is a soft-fork as any validator
operating under the original rules (which ignore the “dummy” bitfield) would
still arrive at the correct pubkey-signature mapping through trial and error.
Aside: If you wanted to hyper-optimize, you could use a binomial encoding of
the bitmask hint field, given that the n-choose-k threshold is already known.
Or you could forego encoding the k threshold entirely and infer it from the
number of set bits. However in either case the number of bytes saved is
negligible compared to the overall size of a multisig script and witness, and
there’d be a significant tradeoff in usability. Such optimization is probably
not worth it.
If you’d rather see this in terms of code, there’s an implementation of this
that I coded up in 2019 and deployed to a non-bitcoin platform:
https://github.com/tradecraftio/tradecraft/commit/339dafc0be37ae5465290b22d204da4f37c6e261
Unfortunately this observation was made too late to be incorporated into
segwit, but future versions of script could absolutely use the hint-field trick
to enable batch validation of CHECKMULTISIG scripts. So you can imagine my
surprise when reviewing the Taproot/Tapscript BIPs I saw that CHECKMULTISIG was
disabled for Tapscript, and the justification given in the footnotes is that
CHECKMULTISIG is not compatible with batch validation! Talking with a few other
developers including Luke-Jr, it has become clear that this solution to the
CHECKMULTISIG batch validation problem had been completely forgotten and did
not come up during Tapscript review. I’m posting this now because I don’t want
the trick to be lost again.
Kind regards,
Mark Friedenbach
PS: One could make the argument that threshold signatures are implementable
with the new CHECKSIGADD opcode, so why bother? For example, the above 2-of-3
threshold could be implemented in Tapscript as:
[OP_0 A CHECKSIGADD B CHECKSIGADD C CHECKSIGADD 2 EQUAL]
However (1) this requires six opcodes in addition to the pubkey pushes, instead
of just 3, and the number of wasted opcodes scales linearly with the size of
the threshold; and (2) the intent is less clear. Because the intent is not
encoded directly in the program in the form of an explicit threshold but rather
inferred from the program structure, there is a higher likelihood of making a
mistake. Particularly for more advanced scripts than this.
One could also argue that there is no need for explicit k-of-n thresholds now
that we have Schnorr signatures, as MuSig-like key aggregation schemes can be
used instead. In many cases this is true, and doing key aggregation can result
in smaller scripts with more private spend pathways. However there remain many
use cases where for whatever reason interactive signing is not possible, due to
signatures being pre-calculated and shared with third parties, for example, and
therefore explicit thresholds must be used instead. For such applications a
batch-validation friendly CHECKMULTISIG would be useful.
[1] I believe it was Luke-Jr, and in 2016 or 2017, probably in
#bitcoin-wizards. I don’t have logs to check, however._______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
