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>
Subject: [bitcoin-dev] Batch validation of CHECKMULTISIG using an extra hint
	field
Precedence: list


--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--