From: ZmnSCPxj <ZmnSCPxj@protonmail•com>
To: Mark Friedenbach <mark@friedenbach•org>,
Bitcoin Protocol Discussion
<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Batch validation of CHECKMULTISIG using an extra hint field
Date: Thu, 20 Oct 2022 22:02:51 +0000 [thread overview]
Message-ID: <1DLM9USCnIBQkKKwOEzDLl0ufRo2FOYT_Fnxy7eVMWPPfoL2P6rC90JlinYdUnpvc-xQPG1mh8Lw5kMeW9BwpxpC1jyreFzlFAkMnKBp_h4=@protonmail.com> (raw)
In-Reply-To: <239D23FC-267F-4198-988D-35152E7E5AC8@friedenbach.org>
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 specifying which keys are used, or alternatively, which are not used and must therefore be skipped. Before 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 attempting 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 that the pubkey is NOT used, then skip it without even attempting validation. The only signature validations which are attempted are those which the bitfield indicates ought to pass. This is a soft-fork as any validator operating under the original rules (which ignore the “dummy” 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 zero?
> 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 there 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 instead. 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 public 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 participation of the n signer set.
My understanding is that it cannot use *just* pre-existing keys, the privkey owners will, after the setup ritual, need to store additional data (tweaks to apply on their key depending on who the k are, if my vague understanding 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 reason 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
prev parent reply other threads:[~2022-10-20 22:03 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-10-19 3:51 Mark Friedenbach
2022-10-20 22:02 ` ZmnSCPxj [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='1DLM9USCnIBQkKKwOEzDLl0ufRo2FOYT_Fnxy7eVMWPPfoL2P6rC90JlinYdUnpvc-xQPG1mh8Lw5kMeW9BwpxpC1jyreFzlFAkMnKBp_h4=@protonmail.com' \
--to=zmnscpxj@protonmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
--cc=mark@friedenbach$(echo .)org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox