Published on: 2022-10-20T22:02:51+00:00
In this conversation, Mark discusses a potential optimization opportunity for the CHECKMULTISIG algorithm in Bitcoin. The idea suggests using a minimally-encoded bitmap to specify which public keys are used or skipped, instead of requiring the final parameter on the stack to be zero. This would allow for a more efficient validation process and could be beneficial for applications where interactive signing is not possible.While MuSig-like key aggregation schemes can be used for n-of-n thresholds, there are still use cases where explicit k-of-n thresholds must be used. FROST is an alternative that supports k-of-n but requires participation from all signers in the set and additional data storage by privkey owners after the setup ritual. Despite this, the proposed batch-validation friendly CHECKMULTISIG algorithm would still be useful for such applications.Satoshi unintentionally made a mistake in the original CHECKMULTISIG implementation, causing an extra item to be popped off the stack upon completion. This extra value provides a malleability vector as anyone can change the 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.Another issue with CHECKMULTISIG is that the algorithm seemingly precludes batch validation for threshold signatures. Batch validation could enable a 2x speedup during the initial block download phase. The algorithm cannot batch validate these signatures because it doesn't know which signatures map to which pubkeys.After SegWit was released, Luke-Jr observed that this new rule was suboptimal and Satoshi's mistake gave an extra parameter to CHECKMULTISIG. It was possible to use this parameter to convey extra information to the CHECKMULTISIG algorithm and enable batch validation of threshold signatures using this opcode.The updated CHECKMULTISIG algorithm requires the final parameter on the stack to be a minimally-encoded bitmap specifying which keys are used or skipped. Before validation, it is important to ensure that 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). During validation, the associated bit in the bitfield is checked to determine if the pubkey is used. If the bitfield indicates that the pubkey is not used, it can be skipped without even attempting validation.This solution is considered a soft-fork, as any validator operating under the original rules would still arrive at the correct pubkey-signature mapping through trial and error. This solution was completely forgotten and did not come up during Tapscript review. The justification given in the footnotes is that CHECKMULTISIG is not compatible with batch validation.Although threshold signatures can be implemented with the new CHECKSIGADD opcode, it 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. Additionally, there are many use cases where interactive signing is not possible, and explicit thresholds must be used. For such applications, a batch-validation friendly CHECKMULTISIG would be useful.
Updated on: 2023-08-02T08:15:12.146850+00:00