Date: Thu, 20 Oct 2022 22:02:51 +0000
To: Mark Friedenbach <mark@friedenbach.org>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <1DLM9USCnIBQkKKwOEzDLl0ufRo2FOYT_Fnxy7eVMWPPfoL2P6rC90JlinYdUnpvc-xQPG1mh8Lw5kMeW9BwpxpC1jyreFzlFAkMnKBp_h4=@protonmail.com>
In-Reply-To: <239D23FC-267F-4198-988D-35152E7E5AC8@friedenbach.org>
References: <239D23FC-267F-4198-988D-35152E7E5AC8@friedenbach.org>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] Batch validation of CHECKMULTISIG using an extra
	hint field
Precedence: list


Good morning Mark,

> 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 specif=
ying which keys are used, or alternatively, which are not used and must the=
refore be skipped. Before attempting validation, ensure for a k-of-n thresh=
old 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, firs=
t 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 e=
ven attempting validation. The only signature validations which are attempt=
ed are those which the bitfield indicates ought to pass. This is a soft-for=
k as any validator operating under the original rules (which ignore the =
=E2=80=9Cdummy=E2=80=9D bitfield) would still arrive at the correct pubkey-=
signature mapping through trial and error.

That certainly seems like a lost optimization opportunity.

Though if the NULLDATA requirement is already a consensus rule then this is=
 no longer a softfork, existing validators would explicitly check it is zer=
o?

> 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 th=
ere 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 instea=
d. For such applications a batch-validation friendly CHECKMULTISIG would be=
 useful.

As I understand it, MuSig aggregation works on n-of-n only.

There is an alternative named FROST recently, that supports k-of-n, however=
, MuSig aggregation works on pre-existing keypairs, and if you know the pub=
lic keys, you can aggregate the public keys without requiring participation=
 with the privkey owners.

For FROST, there is a Verifiable Secret Sharing process which requires part=
icipation of the n signer set.
My understanding is that it cannot use *just* pre-existing keys, the privke=
y owners will, after the setup ritual, need to store additional data (tweak=
s to apply on their key depending on who the k are, if my vague understandi=
ng is accurate).
The requirement of having a setup ritual (which does not require trust but =
does require saving extra data) to implement k-of-n for k < n is another re=
ason some protocol or other might want to use explicit `OP_CHECKMULTISIG`.

(I do have to warn that my knowledge of FROST is hazy at best and the above=
 might be wildly inaccurate.)

Regards,
ZmnSCPxj