summaryrefslogtreecommitdiff
path: root/f5/5c33c21b8fcfd26ef9e7287bd5316fd14a4a85
blob: 8dbd4849d31780203ff983cdbd6e5e073112ae14 (plain)
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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
Return-Path: <ali@notatether.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 852CFC002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 20 Aug 2022 13:49:19 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 4BB74417CF
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 20 Aug 2022 13:49:19 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 4BB74417CF
Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key,
 unprotected) header.d=notatether.com header.i=@notatether.com
 header.a=rsa-sha256 header.s=protonmail header.b=IZO6HPzQ
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.101
X-Spam-Level: 
X-Spam-Status: No, score=-2.101 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H2=-0.001,
 SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 1FQErtB_s8BD
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 20 Aug 2022 13:49:16 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 32DDB417CD
Received: from mail-4317.proton.ch (mail-4317.proton.ch [185.70.43.17])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 32DDB417CD
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 20 Aug 2022 13:49:15 +0000 (UTC)
Date: Sat, 20 Aug 2022 13:49:05 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=notatether.com;
 s=protonmail; t=1661003352; x=1661262552;
 bh=yBzIb6byJFMeVKUeDagenbrQcWsSJEI6YmzoUAE9PUY=;
 h=Date:To:From:Cc:Reply-To:Subject:Message-ID:Feedback-ID:From:To:
 Cc:Date:Subject:Reply-To:Feedback-ID:Message-ID;
 b=IZO6HPzQacEEYzfATxgDXVP6jHm8XERrKnQDphdxEJSMddHTRviSPiJ5xbPf2QbDl
 99pdsbE80PpzhoFXCxIgR0pZjDWv07WTn+fvSnN/tW+L9FahHt65jHZiJbd1CzjGMS
 Kq9Ll9tu7iW3V47Clt07S/fMKvpoVJSVkHN9v2g/pys2CCbhPB361+PnWP8uG9Rzek
 EPUcTvrYpwIkuHm0t28+uec81HAYHUwAASGcyre+7jUzINjVSLo9pjw1HITDyEvKqc
 GS1M0CJIlktl+MWhde9vFYnT1e+qg4KzicWKhrvPdBYSZTYN7+AOigIl9cr4XeXpBZ
 FzNxatrCT7yxw==
To: bitcoin-dev@lists.linuxfoundation.org
From: Ali Sherief <ali@notatether.com>
Reply-To: Ali Sherief <ali@notatether.com>
Message-ID: <20220820134850.ofvz7225zwcyffit@artanis>
Feedback-ID: 34210769:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Sat, 20 Aug 2022 14:19:29 +0000
Cc: luke_bipeditor@dashjr.org
Subject: [bitcoin-dev] [BIP] Implementing Multisig Using Taproot
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: Sat, 20 Aug 2022 13:49:19 -0000

Greetings list.

Following the discussions I made about BIP322 delegation on this mailing li=
st and in other places, I have decided that that delegation depends on a ve=
ry similar problem that arises when writing contracts and commitments. That=
 problem is how to implement private Multisig.

Of course, this can already be done using Taproot. But I doubt that many pe=
ople know how to do it using script paths. BIP342 briefly touches on the su=
bject but leaves it open. So I wrote a BIP to plug this hole, that precisel=
y follows the guidelines hinted by BIPs 341 and 342, for creating and spend=
ing Multisig outputs.

I also managed to figure out the formula that BIP342 vaguely hinted at for =
figuring out "cost-effective multisignatures" (hint: it's not quadratic).

As far as I can tell, such a BIP hasn't been advanced before, so there shou=
ld be no problem of "try working on the other BIP".

Use cases:

- Layer 2 protocols that use multisig (e.g. LN, Discrete Log Contracts)
- BIP322 message signatures, if it is decided that UTXO delegation is desir=
eable.

I'm pasting the draft of the BIP below, with the metadata shaved off, but r=
eferences are left intact. I haven't uploaded it to Github yet.

--------

=3D=3D Summary =3D=3D

This document defines the proper way to construct Multisig outputs and spen=
ds that utilize the privacy provided by Taproot script paths.

=3D=3D Copyright =3D=3D

This document is licensed under the 2-clause BSD license.

=3D=3D Abstract =3D=3D

A Multisignature (also called Multisig) unspent transaction output (UTXO) a=
ttached to an address allows two or more parties to restrict the spending o=
f the UTXO inside the address until a specified number of parties sign the =
output spending it. Multisig UTXOs are extremely useful for creating contra=
cts, and is therefore used in many applications where delegation of funds t=
o a committee is required, such as in Lightning Network channels, in DLCs (=
Discrete Log Contracts), and in other kinds of contracts.

=3D=3D Motivation =3D=3D

OP_CHECKMULTISIG has the disadvantage of revealing all co-signer public key=
s involved in a transaction. This compromises the privacy of those signers.=
 Additionally, this construct is not compatible with Taproot because OP_CHE=
CKMULTISIG is disabled in TapScript, thus those applications are unable to =
make use of Pay-to-Taproot (P2TR) addresses.

Constructing a Multisig output on Taproot is technically possible, but its =
implementation has not been specified by any existing BIP, to the author's =
knowledge. Additionally, most developers of Bitcoin applications do not kno=
w how to construct Multisig Taproot outputs.

=3D=3D Design =3D=3D

Taproot gives us three different options for implementing Multisig, each wi=
th their own advantages and disadvantages<ref>'''Multisig implementation op=
tions reference''' The options were originally enumerated in [https://jimmy=
song.github.io/taproot-multisig Jimmy Song's slideshow] in a more detailed =
manner.</ref>:
# Single-leaf with a TapScript implementing K-of-N Multisig. This is functi=
onally equivalent to legacy OP_CHECKMULTISIG, and shares all its advantages=
 and disadvantages. In particular, all public keys of signers are revealed =
in the TapScript embedded in the first element of the witness program, so t=
he privacy advantages of Taproot are compromised.
# Multiple leaves, each with a TapScript implementing K-of-K Multisig.
# Multiple leaves, each with a TapScript implementing MuSig of K keys (i.e.=
 aggregate of K public keys).

This document uses the second option for implementing Multisig, because it =
only reveals the public keys of those who sign the transaction.<ref>'''Why =
wasn't MuSig considered?''' Although MuSig provides even more privacy by no=
t revealing any original public keys all together, it is a cumbersome proce=
ss to create since K parties must be online not only at one point to create=
 the aggregated keys, but also at another point to create a signature. Ther=
e is the problem of who will be the trustee of the MuSigs themselves, as op=
posed to just the delegated UTXOs. Also, There is no BIP that implements Mu=
Sig, to the author's knowledge.</ref>

=3D=3D Specification =3D=3D

Notations used here are specified in [[bip-0340.mediawiki#design|BIP340]].

''taproot_output_script'' and ''taproot_sign_script'' refers to the Python =
functions of [[bip-0341.mediawiki|BIP341]] with the same name.

=3D=3D=3D Constructing K-of-N Multisig outputs =3D=3D=3D

All of the participating TapScripts must be collected together at construct=
ion-time. This implies that all signers must know each other beforehand<ref=
>'''Why should all signers know each other beforehand?''' Knowing all possi=
ble signers of a multisignature is required for many instances of delegatio=
n, so that an unknown party cannot insert a rogue signature at spending-tim=
e.</ref>.

The algorithm takes as inputs:
* An integer value  ''m'', greater than 0
* An array ''scripts'' of ''m'' TapScripts as byte-arrays.
** The scripts must be written in the following format: "[PubKey p<sub>1</s=
ub>] OP_CHECKSIG [PubKey p<sub>2</sub>] OP_CHECKSIGADD ... [PubKey p<sub>K<=
/sub>] OP_CHECKSIGADD OP_[K] OP_NUMEQUAL"<ref>'''1-of-N Multisig TapScripts=
''', it is possible to save two bytes in each script by dropping "OP_[K] OP=
_NUMEQUAL" from the end of each script. Since OP_CHECKSIG will return 1 on =
success and the empty array on failure, and the script interpreter consider=
s a final stack of truthy values such as 1 as the script succeeding, and li=
kewise for falsy values such as the empty array, the additional OP_NUMEQUAL=
 comparison and associated number push is redundant.</ref>
Where the list p<sub>1</sub> ... p<sub>K</sub> represents a unique combinat=
ion of K public keys from the total set of N public keys. In this way, each=
 TapScript is a K-of-K multisig, requiring the signatures of all parties pa=
rticipating in the TapLeaf.

And returns as the outputs:
* The scriptPubKey, including the hash of the generated withness program an=
d the push bytes.

Algorithm steps:
# Generate a random private key ''p'', in the range ''[0, n-1]''.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954=
b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G''<ref>'''Why is an =
arbitrary public key used for signing and spending?''' All possible combina=
tions of multisignature spends are already enumerated in the script path, s=
o the internal public key is not only redundant, but a security hazard sinc=
e it must be specified. Values that will make Taproot validation fail canno=
t be used. BIP341 advises that in such cases, an internal public key with u=
nknown discrete logarithm should be used.</ref>, where ''G'' is the secp256=
k1 generator point.
# Set ''script_tree'' to the empty list.
# For each script (''i'' in the range ''[0,m-1]'', convert it into a tuple =
with first element a byte 0xc0 and second element the script itself, and ap=
pend it to ''script_tree''.
# Return the result of ''taproot_output_script(internal_pubkey, script_tree=
)''.


=3D=3D=3D Spending K-of-N Multisig outputs =3D=3D=3D

Only one of the multisignature TapScripts will be spent in a K-of-N Taproot=
 Multisig.

The algorithm takes as inputs:
* An integer value  ''m'', greater than 0
* An array ''scripts'' of ''m'' TapScripts as byte-arrays, in the format ta=
ken by the Multisig Construction algorithm
* An integer value ''j'', greater than 0 and less than ''m'', that indicate=
s which multisignature TapScript will be used to spend the output.
* The witness stack ''inputs'' of the script ''scripts[i]'', as an array of=
 byte-arrays.
** The witness stack must be written in the following format: "[Signature s=
<sub>K</sub>] [Signature s<sub>K-1</sub>] ... [Signature s<sub>0</sub>]"
Where the list s<sub>1</sub> ... s<sub>K</sub> are the Schnorr signatures c=
orresponding to the public keys p<sub>1</sub> ... p<sub>K</sub>. Note that =
the list of signatures is coded in the reverse order, because the script in=
terpreter will pop the left-most byte-array as the first stack element, the=
 second-left-most byte array as the second stack element, and so on.

And returns as the outputs:
* The witness, that can spend the scriptPubKey returned by the Multisig Con=
struction algorithm.

Algorithm steps:
# Generate a random private key ''p'', in the range ''[0, n-1]''.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954=
b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G''<ref>'''Why is an =
arbitrary public key used for signing and spending?''' All possible combina=
tions of multisignature spends are already enumerated in the TapLeaves, so =
the internal public key is not only redundant, but a security hazard since =
it must be specified. Values that will make Taproot validation fail cannot =
be used. BIP341 advises that in such cases, an internal public key with unk=
nown discrete logarithm should be used.</ref>.
# Set the internal key ''internal_pubkey'' to ''lift_x(0x0250929b74c1a04954=
b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) + p*G'', where ''G'' is t=
he secp256k1 generator point.
# Set ''script_tree'' to the empty list.
# For each script (''i'' in the range ''[0,m-1]'', convert it into a tuple =
with first element a byte 0xc0 and second element the script itself, and ap=
pend it to ''script_tree''.
# Return the result of ''taproot_sign_script(internal_pubkey, script_tree, =
j, inputs)''.

=3D=3D Notes =3D=3D

[[bip342.mediawiki|BIP342]] mentions that a complete TapBranch of ''k-of-k'=
' multisignature leaves are "only more cost effective for small values of '=
'k'' (1-of-''n'' for any ''n'', 2-of-''n'' for ''n &ge; 6'', 3-of-''n'' for=
 ''n &ge; 9'', ...)". Since the scripts are all of fixed size, and the numb=
er of TapLeaves can similarly be calculated, it is possible to derive a for=
mula for the relative size in (v)bytes of a spent Multisig Taproot output.
* The size of each script is ''33*K + 2''.
* The size of the control block is ''33 + 32 * ceil(log2(nCr(N,K)))'', wher=
e ''nCr'' computes the binomial coefficient of ''N'' and ''K''.
* Therefore, the size of the witness inside the output is ''32*ceil(log2(nC=
r(N,K))) + 33*K + 35''. A table of output sizes is provided for the first f=
ew values of N and K.

N,K,Size (vbytes)
1,1,68
2,1,100
2,2,101
3,1,132
3,2,165
3,3,134
4,1,132
4,2,197
4,3,198
4,4,167
5,1,164
5,2,229
5,3,262
5,4,263
5,5,200
6,1,164
6,2,229
6,3,294
6,4,295
6,5,296
6,6,233

The data shows that 1-of-N Multisig TapScripts have the smallest witness ou=
tput, and K-of-N Multisig Tapscripts with ''K &gt; 1'' and progressively in=
creasing to ''N-1'' have increasingly larger sizes. Where the K-of-N combin=
ation has a smaller size than the equivalent N-of-N combination, it is deem=
ed to be cost-efficient. Hence, since 2 cosigners out of a maximum of 6 mak=
es a transaction size smaller than 6-of-6, 2-of-6 multisig is the largest c=
ost-effective combination for ''N =3D 6''. If the data is extended, it can =
similary be proven that 3-of-9 multisig is the largest cost-effective combi=
nation for ''N =3D 9''.<ref>'''Cost-effective delegations''' Several delega=
tion schemes such as Lightning Network channels use only a combination of 1=
-of-N and N-of-N multisig transactions, with small N &gt; 1.</ref>

The following Python 3.8 code an be used to calculate transaction sizes for=
 ''K &gt; 0'', ''N &gt; 0'', and ''N &ge; K'':

<source lang=3D"python">
>>> import math
>>> txsize =3D lambda n,k : 32*math.ceil(math.log2(math.comb(n, k))) + 33*k=
 + 35
>>> txsize(1,1)
68
# ...
</source>


=3D=3D Rationale =3D=3D

<references />

=3D=3D Acknowledgements =3D=3D

Thanks to garlonicon, vjudeu, and Ali Ashraf for providing feedback about m=
ultisignatures while this document was being written.

--------

I appreciate any comments about this, especially from the BIP editors.

- Ali