Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id CA6E9C002D for ; Wed, 19 Oct 2022 03:51:59 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 85FF183F5F for ; Wed, 19 Oct 2022 03:51:59 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 85FF183F5F Authentication-Results: smtp1.osuosl.org; dkim=pass (2048-bit key) header.d=friedenbach-org.20210112.gappssmtp.com header.i=@friedenbach-org.20210112.gappssmtp.com header.a=rsa-sha256 header.s=20210112 header.b=pk1yuetb X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.896 X-Spam-Level: X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FPQ9qUbeZBtK for ; Wed, 19 Oct 2022 03:51:58 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org ED5E283F36 Received: from mail-pj1-x1029.google.com (mail-pj1-x1029.google.com [IPv6:2607:f8b0:4864:20::1029]) by smtp1.osuosl.org (Postfix) with ESMTPS id ED5E283F36 for ; Wed, 19 Oct 2022 03:51:57 +0000 (UTC) Received: by mail-pj1-x1029.google.com with SMTP id o17-20020a17090aac1100b0020d98b0c0f4so17978072pjq.4 for ; Tue, 18 Oct 2022 20:51:57 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=friedenbach-org.20210112.gappssmtp.com; s=20210112; h=to:message-id:subject:date:mime-version:from :content-transfer-encoding:from:to:cc:subject:date:message-id :reply-to; bh=xpKfFIlSxUrk4typOEu624dZzAyrirXgNsDz8SSUfDU=; b=pk1yuetbHzm5a2WMAQ5QTaY0d/1DH4sz/YyHIAPTY2g0CjVluP82Y80d22BYcwbIvj mKO7xXSTyTLW8gVJnfUee4mpV7hf6xqpalPK4gXBknv+P+Vbtl/OAstDkm+ga4ekgaMF QkdwQHS+lra9ztGyC0Smbw0mTlx/KUYMQJGyL5qoe1c0CU7JUVJX0vScuwUQNBJsQ9fG BnWFYj5vX69SnkHEiSnTGAhPmcygk66tAfYlD7mrLh75rxEqhfkN/kLGWs4DTjCoccP/ xgKwG1uJfrvfu8KBxVAOVcsZAVjQuR8DNqJn8oUDTZJaEVSzFshf48Jvr/na0A/WMOSX n7RA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=to:message-id:subject:date:mime-version:from :content-transfer-encoding:x-gm-message-state:from:to:cc:subject :date:message-id:reply-to; bh=xpKfFIlSxUrk4typOEu624dZzAyrirXgNsDz8SSUfDU=; b=kRNqDDGOuewE0e3evG91JCp3dTs994WQPcDBkfe0BfT3WqX45LnsBMHvuFN/2ULEmF RJwGDJd6dZVqHVHVZaq1ThLDJ9vUNNw+zJrt9Ov4tif1bQoyy0vc5jAazRIQxFHfpYJ0 gsRo2pn9EIoBBssrUfMZioCnzy8KrQ46w32+gFtah0BX5PMwHVZ/8/H6S/BszZh80gH+ cWEqw0WF//dVt2QjauNXximZmnexqKvz/C6lUkqkBvQT0eDgcRcqrCP/oVxY/iunV1jU vRvZokFhuf7ofhKe1yT8izqn/eN8DOYGgEn5tft/HHQbf1aBN63Z+q8oWIX3KH0wxyIk p6/w== X-Gm-Message-State: ACrzQf110Bp3n8btrmq3djOdueWXq4HIrC7tpK2y1t1TD6thBNv488QA eDrkUnUfJbxJ0NGG8SOe5eaKAV8uWLr0J5FT X-Google-Smtp-Source: AMsMyM7lMWGEuF9BhvHJRUfow7LHizYsaiEEXoPOXq7XZoikqT5U+hrwcwZ94xMMxu8zlon9e7xPqQ== X-Received: by 2002:a17:90b:1b07:b0:20d:571c:1d3d with SMTP id nu7-20020a17090b1b0700b0020d571c1d3dmr7370729pjb.192.1666151516618; Tue, 18 Oct 2022 20:51:56 -0700 (PDT) Received: from smtpclient.apple ([2607:fb90:4a59:e907:d153:289f:ab58:995a]) by smtp.gmail.com with ESMTPSA id a1-20020a170902710100b0016f196209c9sm9574196pll.123.2022.10.18.20.51.55 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 18 Oct 2022 20:51:55 -0700 (PDT) Content-Type: multipart/alternative; boundary=Apple-Mail-78A94018-CA84-4779-B9FD-E07268EAACA0 Content-Transfer-Encoding: 7bit From: Mark Friedenbach Mime-Version: 1.0 (1.0) Date: Tue, 18 Oct 2022 20:51:42 -0700 Message-Id: <239D23FC-267F-4198-988D-35152E7E5AC8@friedenbach.org> To: Bitcoin Protocol Discussion X-Mailer: iPhone Mail (20A380) X-Mailman-Approved-At: Wed, 19 Oct 2022 11:31:23 +0000 Subject: [bitcoin-dev] Batch validation of CHECKMULTISIG using an extra hint field X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 19 Oct 2022 03:52:00 -0000 --Apple-Mail-78A94018-CA84-4779-B9FD-E07268EAACA0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable When Satoshi wrote the first version of bitcoin, s/he made what was almost c= ertainly an unintentional mistake. A bug in the original CHECKMULTISIG imple= mentation caused an extra item to be popped off the stack upon completion. T= his extra value is not used in any way, and has no consensus meaning. Since t= his value is often provided in the witness, it unfortunately provides a mall= eability 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 rul= e for segwit scripts. This isn=E2=80=99t the only problem with CHECKMULTISIG. For both ECDSA and S= chnorr signatures, batch validation could enable an approximate 2x speedup, e= specially during the initial block download phase. However the CHECKMULTISIG= algorithm, as written, seemingly precludes batch validation for threshold s= ignatures as it attempts to validate the list of signatures with the list of= pubkeys, in order, dropping an unused pubkey only when a signature validati= on fails. As an example, the following script [2 C B A 3 CHECKMULTISIG] Could be satisfied by the following witness: [0 c a] Where =E2=80=9Ca=E2=80=9D is a signature for pubkey A, and =E2=80=9Cc=E2=80=9D= a signature for pubkey C. During validation, the signature a is checked usi= ng pubkey A, which is successful, so the internal algorithm increments the s= ignature pointer AND the pubkey pointer to the next elements in the respecti= ve lists, removing both from future consideration. Next the signature c is c= hecked with pubkey B, which fails, so only the pubkey pointer is incremented= . Finally signature c is checked with pubkey C, which passes. Since 2 signat= ures passed and this is equal to the specified threshold, the opcode evaluat= es as true. All inputs (including the dummy 0 value) are popped from the sta= ck. The algorithm cannot batch validate these signatures because for any partial= threshold it doesn=E2=80=99t 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=E2=80=99s mistake gave u= s an extra parameter to CHECKMULTISIG, and it was entirely within our means t= o use this parameter to convey extra information to the CHECKMULTISIG algori= thm, and thereby enable batch validation of threshold signatures using this o= pcode. The idea is simple: instead of requiring that the final parameter on the sta= ck be zero, require instead that it be a minimally-encoded bitmap specifying= which keys are used, or alternatively, which are not used and must therefor= e be skipped. Before attempting validation, ensure for a k-of-n threshold on= ly k bits are set in the bitfield indicating the used pubkeys (or n-k bits s= et indicating the keys to skip). The updated CHECKMULTISIG algorithm is as f= ollows: when attempting to validate a signature with a pubkey, first check t= he associated bit in the bitfield to see if the pubkey is used. If the bitfi= eld indicates that the pubkey is NOT used, then skip it without even attempt= ing validation. The only signature validations which are attempted are those= which the bitfield indicates ought to pass. This is a soft-fork as any vali= dator operating under the original rules (which ignore the =E2=80=9Cdummy=E2= =80=9D bitfield) would still arrive at the correct pubkey-signature mapping t= hrough 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 know= n. Or you could forego encoding the k threshold entirely and infer it from t= he number of set bits. However in either case the number of bytes saved is n= egligible compared to the overall size of a multisig script and witness, and= there=E2=80=99d be a significant tradeoff in usability. Such optimization i= s probably not worth it. If you=E2=80=99d rather see this in terms of code, there=E2=80=99s an implem= entation of this that I coded up in 2019 and deployed to a non-bitcoin platf= orm: https://github.com/tradecraftio/tradecraft/commit/339dafc0be37ae5465290b22d2= 04da4f37c6e261 Unfortunately this observation was made too late to be incorporated into seg= wit, but future versions of script could absolutely use the hint-field trick= to enable batch validation of CHECKMULTISIG scripts. So you can imagine my s= urprise when reviewing the Taproot/Tapscript BIPs I saw that CHECKMULTISIG w= as disabled for Tapscript, and the justification given in the footnotes is t= hat CHECKMULTISIG is not compatible with batch validation! Talking with a fe= w 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=E2=80=99m posting this now b= ecause I don=E2=80=99t want the trick to be lost again. Kind regards, Mark Friedenbach PS: One could make the argument that threshold signatures are implementable w= ith 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, inst= ead of just 3, and the number of wasted opcodes scales linearly with the siz= e of the threshold; and (2) the intent is less clear. Because the intent is n= ot encoded directly in the program in the form of an explicit threshold but r= ather inferred from the program structure, there is a higher likelihood of m= aking a mistake. Particularly for more advanced scripts than this. One could also argue that there is no need for explicit k-of-n thresholds no= w 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 r= esult in smaller scripts with more private spend pathways. However there rem= ain many use cases where for whatever reason interactive signing is not poss= ible, due to signatures being pre-calculated and shared with third parties, f= or 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-wiza= rds. I don=E2=80=99t have logs to check, however.= --Apple-Mail-78A94018-CA84-4779-B9FD-E07268EAACA0 Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable

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 extr= a/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=E2=80=99= 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 w= ritten, seemingly precludes batch validation for threshold signatures as it a= ttempts to validate the list of signatures with the list of pubkeys, in orde= r, dropping an unused pubkey only when a signature validation fails. As an e= xample, the following script


    [2 C B A 3 CHECK= MULTISIG]


Could be satisfied by the following witness:


 &n= bsp;  [0 c a]


Where =E2=80=9Ca=E2=80=9D is a signature for p= ubkey A, and =E2=80=9Cc=E2=80=9D a signature for pubkey C. During validation= , the signature a is checked using pubkey A, which is successful, so the int= ernal algorithm increments the signature pointer AND the pubkey pointer to t= he next elements in the respective lists, removing both from future consider= ation. Next the signature c is checked with pubkey B, which fails, so only t= he pubkey pointer is incremented. Finally signature c is checked with pubkey= C, which passes. Since 2 signatures passed and this is equal to the specifi= ed threshold, the opcode evaluates as true. All inputs (including the dummy 0= value) are popped from the stack.


The algorithm cannot batch validat= e these signatures because for any partial threshold it doesn=E2=80=99t know= which signatures map to which pubkeys.


= Not long after segwit was relea= sed for activation, making the NULLDUMMY rule consensus for segwit scripts, t= he observation was made by Luke-Jr on IRC[1] that this new rule was actually= suboptimal. Satoshi=E2=80=99s mistake gave us an extra parameter to CHECKMU= LTISIG, and it was entirely within our means to use this parameter to convey= extra information to the CHECKMULTISIG algorithm, and thereby enable batch v= alidation of threshold signatures using this opcode.


The idea is simpl= e: instead of requiring that the final parameter on the stack be zero, requi= re instead that it be a minimally-encoded bitmap specifying which keys are u= sed, or alternatively, which are not used and must therefore be skipped. Bef= ore 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 atte= mpting 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 tha= t the pubkey is NOT used, then skip it without even attempting validation. T= he only signature validations which are attempted are those which the bitfie= ld indicates ought to pass. This is a soft-fork as any validator operating u= nder the original rules (which ignore the =E2=80=9Cdummy=E2=80=9D bitfield) w= ould still arrive at the correct pubkey-signature mapping through trial and e= rror.


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 a= lready known. Or you could forego encoding the k threshold entirely and infe= r 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 w= itness, and there=E2=80=99d be a significant tradeoff in usability. Such opt= imization is probably not worth it.


If you=E2=80=99d rather see this i= n terms of code, there=E2=80=99s an implementation of this that I coded up i= n 2019 and deployed to a non-bitcoin platform:


<= p dir=3D"ltr" style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0= , 0); color: rgb(0, 0, 0); line-height: 1.38; margin-top: 0pt; margin-bottom= : 0pt;">https://github.com/tradecraft= io/tradecraft/commit/339dafc0be37ae5465290b22d204da4f37c6e261

=

Unf= ortunately 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 sur= prise when reviewing the Taproot/Tapscript BIPs I saw that CHECKMULTISIG was= disabled for Tapscript, and the justification given in the footnotes is tha= t CHECKMULTISIG is not compatible with batch validation! Talking with a few o= ther developers including Luke-Jr, it has become clear that this solution to= the CHECKMULTISIG batch validation problem had been completely forgotten an= d did not come up during Tapscript review. I=E2=80=99m posting this now beca= use I don=E2=80=99t want the trick to be lost again.


Kind regards,

Mark Friedenbac= h


PS: One could make the argument that threshold signatures are imple= mentable with the new CHECKSIGADD opcode, so why bother? For example, the ab= ove 2-of-3 threshold could be implemented in Tapscript as:


 &nbs= p;  [OP_0 A CHECKSIGADD B CHECKSIGADD C CHECKSIGADD 2 EQUAL]


= One could also argue that there is no need for explicit k-of-n thresholds no= w 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 r= esult in smaller scripts with more private spend pathways. However there rem= ain many use cases where for whatever reason interactive signing is not poss= ible, due to signatures being pre-calculated and shared with third parties, f= or 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=E2=80=99t have logs to check, however.

= --Apple-Mail-78A94018-CA84-4779-B9FD-E07268EAACA0--