path: root/0d/c618edb5ce21780a25415d18e987c329204cee

Return-Path: <mark@friedenbach.org>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id CA6E9C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 19 Oct 2022 03:51:57 +0000 (UTC)
Received: by mail-pj1-x1029.google.com with SMTP id
 o17-20020a17090aac1100b0020d98b0c0f4so17978072pjq.4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>
 (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 <mark@friedenbach.org>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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

<html><head><meta http-equiv=3D"content-type" content=3D"text/html; charset=3D=
utf-8"></head><body dir=3D"auto"><div dir=3D"ltr"><p dir=3D"ltr" style=3D"-w=
ebkit-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;"><span style=3D"fo=
nt-size: 11pt; font-family: Arial; font-variant-ligatures: normal; font-vari=
ant-east-asian: normal; font-variant-position: normal; vertical-align: basel=
ine; white-space: pre-wrap;">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.</span></p><br style=3D"-=
webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0=
);"><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-b=
ottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Arial; font-varian=
t-ligatures: normal; font-variant-east-asian: normal; font-variant-position:=
 normal; vertical-align: baseline; white-space: pre-wrap;">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</span></p><br style=3D"-webkit-text-size-adjust=
: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><p dir=3D"ltr" styl=
e=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;"><span styl=
e=3D"font-size: 11pt; font-family: Arial; font-variant-ligatures: normal; fo=
nt-variant-east-asian: normal; font-variant-position: normal; vertical-align=
: baseline; white-space: pre-wrap;">&nbsp;&nbsp;&nbsp;&nbsp;[2 C B A 3 CHECK=
MULTISIG]</span></p><br style=3D"-webkit-text-size-adjust: auto; caret-color=
: rgb(0, 0, 0); color: rgb(0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-s=
ize-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); line-heigh=
t: 1.38; margin-top: 0pt; margin-bottom: 0pt;"><span style=3D"font-size: 11p=
t; font-family: Arial; font-variant-ligatures: normal; font-variant-east-asi=
an: normal; font-variant-position: normal; vertical-align: baseline; white-s=
pace: pre-wrap;">Could be satisfied by the following witness:</span></p><br s=
tyle=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); color: rg=
b(0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-size-adjust: auto; caret-c=
olor: rgb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38; margin-top: 0pt;=
 margin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Arial; fo=
nt-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-=
position: normal; vertical-align: baseline; white-space: pre-wrap;">&nbsp;&n=
bsp;&nbsp;&nbsp;[0 c a]</span></p><br style=3D"-webkit-text-size-adjust: aut=
o; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><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;"><span style=3D"f=
ont-size: 11pt; font-family: Arial; font-variant-ligatures: normal; font-var=
iant-east-asian: normal; font-variant-position: normal; vertical-align: base=
line; white-space: pre-wrap;">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.</span></p><br style=3D"-webkit-text-size-=
adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><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;"><spa=
n style=3D"font-size: 11pt; font-family: Arial; font-variant-ligatures: norm=
al; font-variant-east-asian: normal; font-variant-position: normal; vertical=
-align: baseline; white-space: pre-wrap;">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.</span></p><br style=3D"-webkit-text-=
size-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><p dir=3D=
"ltr" style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); co=
lor: rgb(0, 0, 0); line-height: 1.38; margin-top: 0pt; margin-bottom: 0pt;">=
<span style=3D"font-size: 11pt; font-family: Arial; font-variant-ligatures: n=
ormal; font-variant-east-asian: normal; font-variant-position: normal; verti=
cal-align: baseline; white-space: pre-wrap;">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.</span></p><br style=3D"=
-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0=
);"><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-b=
ottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Arial; font-varian=
t-ligatures: normal; font-variant-east-asian: normal; font-variant-position:=
 normal; vertical-align: baseline; white-space: pre-wrap;">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.</span></p><br style=3D"-webkit-text-size-adjust: auto; caret-color: rg=
b(0, 0, 0); color: rgb(0, 0, 0);"><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;"><span style=3D"font-size: 11pt; f=
ont-family: Arial; font-variant-ligatures: normal; font-variant-east-asian: n=
ormal; font-variant-position: normal; vertical-align: baseline; white-space:=
 pre-wrap;">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.</span></p><br style=3D"-webkit-text-size=
-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><p dir=3D"lt=
r" 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;"><sp=
an style=3D"font-size: 11pt; font-family: Arial; font-variant-ligatures: nor=
mal; font-variant-east-asian: normal; font-variant-position: normal; vertica=
l-align: baseline; white-space: pre-wrap;">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:</span></p><br style=3D"-webki=
t-text-size-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><=
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;"><a href=3D"https://github.com/tradecraftio/tradecraft/commit/339dafc=
0be37ae5465290b22d204da4f37c6e261" style=3D"text-decoration: none;"><span st=
yle=3D"font-size: 11pt; font-family: Arial; color: rgb(17, 85, 204); font-va=
riant-ligatures: normal; font-variant-east-asian: normal; font-variant-posit=
ion: normal; text-decoration: underline; text-decoration-skip-ink: none; ver=
tical-align: baseline; white-space: pre-wrap;">https://github.com/tradecraft=
io/tradecraft/commit/339dafc0be37ae5465290b22d204da4f37c6e261</span></a></p>=
<br style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); colo=
r: rgb(0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-size-adjust: auto; ca=
ret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38; margin-top:=
 0pt; margin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Aria=
l; font-variant-ligatures: normal; font-variant-east-asian: normal; font-var=
iant-position: normal; vertical-align: baseline; white-space: pre-wrap;">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.</span></p><br style=3D"=
-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0=
);"><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-b=
ottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Arial; font-varian=
t-ligatures: normal; font-variant-east-asian: normal; font-variant-position:=
 normal; vertical-align: baseline; white-space: pre-wrap;">Kind regards,</sp=
an></p><p dir=3D"ltr" style=3D"-webkit-text-size-adjust: auto; caret-color: r=
gb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38; margin-top: 0pt; margin=
-bottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Arial; font-vari=
ant-ligatures: normal; font-variant-east-asian: normal; font-variant-positio=
n: normal; vertical-align: baseline; white-space: pre-wrap;">Mark Friedenbac=
h</span></p><br style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0,=
 0, 0); color: rgb(0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-size-adju=
st: auto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38;=
 margin-top: 0pt; margin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-=
family: Arial; font-variant-ligatures: normal; font-variant-east-asian: norm=
al; font-variant-position: normal; vertical-align: baseline; white-space: pr=
e-wrap;">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:</span></p><br sty=
le=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); color: rgb(=
0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-size-adjust: auto; caret-col=
or: rgb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38; margin-top: 0pt; m=
argin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-family: Arial; font=
-variant-ligatures: normal; font-variant-east-asian: normal; font-variant-po=
sition: normal; vertical-align: baseline; white-space: pre-wrap;">&nbsp;&nbs=
p;&nbsp;&nbsp;[OP_0 A CHECKSIGADD B CHECKSIGADD C CHECKSIGADD 2 EQUAL]</span=
></p><br style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0);=
 color: rgb(0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-size-adjust: aut=
o; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38; margin=
-top: 0pt; margin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-family:=
 Arial; font-variant-ligatures: normal; font-variant-east-asian: normal; fon=
t-variant-position: normal; vertical-align: baseline; white-space: pre-wrap;=
">However (1) this requires six opcodes in addition to the pubkey pushes, in=
stead of just 3, and the number of wasted opcodes scales linearly with the s=
ize of the threshold; and (2) the intent is less clear. Because the intent i=
s not encoded directly in the program in the form of an explicit threshold b=
ut rather inferred from the program structure, there is a higher likelihood o=
f making a mistake. Particularly for more advanced scripts than this.</span>=
</p><br style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0); c=
olor: rgb(0, 0, 0);"><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-t=
op: 0pt; margin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-family: A=
rial; font-variant-ligatures: normal; font-variant-east-asian: normal; font-=
variant-position: normal; vertical-align: baseline; white-space: pre-wrap;">=
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.</sp=
an></p><br style=3D"-webkit-text-size-adjust: auto; caret-color: rgb(0, 0, 0=
); color: rgb(0, 0, 0);"><p dir=3D"ltr" style=3D"-webkit-text-size-adjust: a=
uto; caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0); line-height: 1.38; marg=
in-top: 0pt; margin-bottom: 0pt;"><span style=3D"font-size: 11pt; font-famil=
y: Arial; font-variant-ligatures: normal; font-variant-east-asian: normal; f=
ont-variant-position: normal; vertical-align: baseline; white-space: pre-wra=
p;">[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.</span></p></div></body=
></html>=

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