1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 366BEC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 20 Oct 2022 22:03:05 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id E6D208433B
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 20 Oct 2022 22:03:04 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org E6D208433B
Authentication-Results: smtp1.osuosl.org;
dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com
header.a=rsa-sha256 header.s=protonmail3 header.b=YmdALk26
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.202
X-Spam-Level:
X-Spam-Status: No, score=-0.202 tagged_above=-999 required=5
tests=[BAYES_05=-0.5, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H2=-0.001,
SPF_HELO_PASS=-0.001, SPF_PASS=-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 hMI9V7wrrjLu
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 20 Oct 2022 22:03:03 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 6B3668431C
Received: from mail-40132.protonmail.ch (mail-40132.protonmail.ch
[185.70.40.132])
by smtp1.osuosl.org (Postfix) with ESMTPS id 6B3668431C
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 20 Oct 2022 22:03:03 +0000 (UTC)
Date: Thu, 20 Oct 2022 22:02:51 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail3; t=1666303381; x=1666562581;
bh=YJLJ3hy04/DA18+8pJFPR67gVUUR4W7sPwc78ZjxX6k=;
h=Date:To:From:Subject:Message-ID:In-Reply-To:References:
Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID:
Message-ID;
b=YmdALk26ANmIC2qqSwB97hpd5ex0PoG8XUgIH4zCp6wrm9P5DAIV4tTzBZue2Whmf
AyXcvboR+B98aQpyaIu1titGvG+gV9HixHCqAmnyE396TY2VPa4IjI1RUWfmZbfrK4
/nugKb3CgzsSF9vu88MpLGRifU2AwcEC5moFTlpke+iZLRYcR7BiBSjaHZ3JTQY7Lw
Zz3KEGxJL8P1AXZ3YAfal39UUKDlZ+Etr0Uhkq8DjLjKDexTFhmx0+BiR6cbfLbutO
jkD97qB+drjqfjQ/yZre723CwIAVmmOnzKSJz0JJYwshtjZq+7T5MlRHFY0wC3528n
Vncz4Cg9o8MVg==
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
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: Thu, 20 Oct 2022 22:03:05 -0000
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
|
