summaryrefslogtreecommitdiff
path: root/dc/3c97d0be4550136ddadee88cc28b7197304b25
blob: 0f34d3926a0018c97065390945d585319d251259 (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
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
Delivery-date: Sat, 26 Apr 2025 09:14:44 -0700
Received: from mail-yb1-f192.google.com ([209.85.219.192])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDI23FE35EIBB2EMWTAAMGQEOBM2PIA@googlegroups.com>)
	id 1u8iAt-0000wi-2N
	for bitcoindev@gnusha.org; Sat, 26 Apr 2025 09:14:44 -0700
Received: by mail-yb1-f192.google.com with SMTP id 3f1490d57ef6-e73290d75a8sf618819276.1
        for <bitcoindev@gnusha.org>; Sat, 26 Apr 2025 09:14:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1745684077; x=1746288877; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=IfnccuopvhWkNFd/ak4ul7p8Duk0KE+qzMSVKr1zAaA=;
        b=nURrDs4LYZSfddx5OPlnISIJLgiZ71x74B7sXP0V2OcnCEfD0FMxbY02TPV3/hKDUO
         cVRSBQi+EBj6CrB+2M4Ku7OEPCc9P+J38jNP/Z6qezdofvbHLe/sK8/OlDn8ZgO8OMLQ
         bxxOLwpnz6MdXCqvuTR6JSmfMEOX/by64uPx2JU92npKIVZo7F1J/HJwpafg94326Zm7
         rr7aQbdrNa/4zUO35XD/NWAdsF008DC3S0of9FYzBeb6qsUsRjlLA6RjFGXbe03Y4TUI
         ELG1Y446myqI9n67hMffCRTZ1um93Lnb9tT58BDEkUXSDihNRxz/QDSppvlZK7LC1Qdq
         nVFQ==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1745684077; x=1746288877; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:from:to:cc
         :subject:date:message-id:reply-to;
        bh=IfnccuopvhWkNFd/ak4ul7p8Duk0KE+qzMSVKr1zAaA=;
        b=kr1TPm5F44cAG0rPJhTQJGmcPPp8WibFSul6LjuyavJpgmChbHd9PnB2jZgs/zyNdA
         xKBzdHUJuH0CdapX06uFXxaxPi1hjR88pODZ1TRjJRuHqyYxAqPciy8lT0SgAQ9rTC84
         ejUo1S8ccyhc7F0+/3pqtoeX1bUiVMLv2E8zdGKdazG3RcK8x5u0ZUciE2DqH7KQsnP5
         WD7oQDZmWd5Sp5tdCKs62FIbhfzJEkcrOFR2BCewhpKIvplWMOgJ2qPsrU37rnHDeFRj
         qqDposQPt+xXsxwF9yeEgFmyS5hY71fcxhODdaFX7xyqwSRpovp+NclNWouY5F19uLGu
         eOvw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1745684077; x=1746288877;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=IfnccuopvhWkNFd/ak4ul7p8Duk0KE+qzMSVKr1zAaA=;
        b=huuPIoUpq4RdcxI7S9MqM2fLLRjEK1nU1uu7HLzSSlDRLF+s2HcGgk4zc473oIft/v
         08DIE2Bs2P2Pjb4DQUA/TJWWXasBnqKE0Aprh9tRXGFOSeDaHxF85LDQ31j8wV7T2c9q
         Ce74B7AZBnZCuKC3r9tXmiw8hcqPkMlLSG4xR0r4rgnQWStJeQw7vzjsP8B1vb/Q3wCj
         Se6XTil0yttAWNeZKW4O8qS/ZeH9AEqqvD59z+2nLRgbjn94Z2pFl/lttbkyyK667Ue1
         e9cpgSbAIriQa6q5ie45YBN8tUjVT88l+jbK2eLROois6cb+ukE4k4aYllq85OJsFk+7
         32Og==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVYSFEkSvqrskx0xONQJEY4y1Vq0cqETXKdfwpqiKZFnUQARWKBvNTf884i7NthYiLLNBAxzNL/eq1K@gnusha.org
X-Gm-Message-State: AOJu0Yx4fNsNm6dvKodSM2wwEApOcYtk/Wh5mJ8LJmmD7AqxQDN2l5MT
	ahELneSo3QOOfd6eAm/nojCrlP7LGD48PkmEfRL8FmssFbgKXIye
X-Google-Smtp-Source: AGHT+IG7D0KMTyuyBwhVLn9FFT7C8PIgL6uo1iyG503BinbWwbZ4IAapc3J+uPoycDDEKJO5egADMg==
X-Received: by 2002:a05:6902:1006:b0:e64:3e3a:f000 with SMTP id 3f1490d57ef6-e7316ad5086mr8750663276.25.1745684076688;
        Sat, 26 Apr 2025 09:14:36 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBEIvza3FanXx/5ri8as2fjmM9gishZUyvkTmuNmfgaSwQ==
Received: by 2002:a25:7bc1:0:b0:e72:87fa:2588 with SMTP id 3f1490d57ef6-e730175a859ls1515305276.2.-pod-prod-08-us;
 Sat, 26 Apr 2025 09:14:32 -0700 (PDT)
X-Received: by 2002:a05:690c:3801:b0:703:ac44:d367 with SMTP id 00721157ae682-708540e1226mr92166277b3.6.1745684072188;
        Sat, 26 Apr 2025 09:14:32 -0700 (PDT)
Received: by 2002:a05:690c:3693:b0:708:1ea1:3cd5 with SMTP id 00721157ae682-70854ddd573ms7b3;
        Sat, 26 Apr 2025 08:30:54 -0700 (PDT)
X-Received: by 2002:a05:690c:6210:b0:703:c3ed:1f61 with SMTP id 00721157ae682-7085414505fmr84321757b3.20.1745681452917;
        Sat, 26 Apr 2025 08:30:52 -0700 (PDT)
Date: Sat, 26 Apr 2025 08:30:52 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
In-Reply-To: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
Subject: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive
 Aggregate Signatures
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_63930_85546993.1745681452380"
X-Original-Sender: ekaggata@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)

------=_Part_63930_85546993.1745681452380
Content-Type: multipart/alternative; 
	boundary="----=_Part_63931_1260739144.1745681452380"

------=_Part_63931_1260739144.1745681452380
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Some comments/questions on the general structure of the scheme:

When I started thinking about ways to change the algorithm, I started to=20
appreciate it more :) Although this algo is not specific to Bitcoin I'm=20
viewing it 100% through that lens here. Some thoughts:

We want this CISA algorithm to have the property that it doesn't require=20
the blockchain (and its verifiers) to incur linear cost in the number of=20
signers/signatures. For a 100 input transaction, we get big gains from the=
=20
owner or owners of the inputs choosing to use this algo, but that would=20
mostly be lost if either the verifying was linear in the number, or if the=
=20
size of the signature was linear in the number. So to avoid that we want a=
=20
(R, s) structure to be actually published, not an (R1..Rn, s) or a (R,=20
s1..sn). That pretty much forces us to make a sum R for all the individual=
=20
component's R-values, and the same for s.

However it doesn't quite force us to add literally everything. The pubkeys=
=20
*can* be kept separate, because they are retrieved implicitly from the=20
existing blockchain record, they are not published with the signature=20
(taproot). (Technically the same comment applies to the message being=20
signed). This allows us to use the more "pedestrian", "safe" idea; we are=
=20
not aggregating keys (as in MuSig) so we can actually add each with its own=
=20
challenge hash: sum( challenge_hash_i * X_i). This may worry you that there=
=20
is a performance issue because the verifier has to iterate through that=20
whole list ( the verification equation being: sG =3D?=3D R + c_1 X_1 + c_2X=
_2 +=20
.. ), but the paper specifically claims that comparing this with just batch=
=20
verifying the individual signatures (i.e. without CISA), this is twice as=
=20
fast.

So one could simplistically say "OK that's the pubkey side, they're treated=
=20
individually so we don't have to worry about that, but what about adding=20
the R values?" ("worry" here means: trivial key subtraction attacks or=20
sophisticated Wagner/ROS grinding). And here what is done is basically the=
=20
same as in MuSig2, which is to say, by breaking the nonce into two=20
components and including an additional challenge hash, you prevent the=20
counterparty/adversary from grinding R values successfully. Note that the=
=20
"b" coefficient used here is more explicit about hashing the full context,=
=20
than it was in MuSig2: it's hashing each individual pubkey and message as=
=20
well as the R2 subcomponents for each party. This is vaguely similar to=20
"client side validation" ideas: it's not really "validation" as in state=20
updates, but it's having the more complex/expensive part of the calculation=
=20
being done in the coordination before anything goes on-chain, and allowing=
=20
us to just use a single "R" value onchain that we know is safe.

(Side note: it's worth remembering that a lot (maybe a huge majority?) of=
=20
the usage of CISA will be a single signer of multiple inputs; for these=20
cases there is not the same security arguments required, only that the=20
final signature is not leaking the private key!).

That side note reminds me of my first question: would it not be appropriate=
=20
to include a proof of the zero knowledgeness property of the scheme, and=20
not only the soundness? I can kind of accept the answer "it's trivial"=20
based on the structure of the partial sig components (s_k =3D r_k1 + br_k2 =
+=20
c_k x_k) being "identical" to baseline Schnorr?

The side note also raises this point: would it be a good idea to explicitly=
=20
write down ways in which the usage of the scheme/structure can, and cannot,=
=20
be optimised for the single-party case? Intuitively it's "obvious" that you=
=20
may be able to streamline it for the case where all operations happen on=20
the same device, with a single owner of all the private keys. I realize=20
that this is a thorny point, because we explicitly want to account for the=
=20
corruption of parties that are "supposed" to be the same as the honest=20
signer, but aren't.

And my last question is about this multi-component-nonce technique:

Did you consider the idea of e.g. sending proofs of knowledge of R along=20
with R in the coordination step? This would keep the same number of rounds,=
=20
and I'm assuming (though not sure exactly) that it makes the security proof=
=20
significantly simpler, but my guess is you mostly dismiss such approaches=
=20
as being too expensive for, say, constrained devices? (I imagine something=
=20
like: 2 parties say, X1 sends (R1, pi_R1) and same for X2, to coordinator,=
=20
then sum directly for overall R; here pi_R1 is ofc just a schnorr sig on=20
r). If we're talking about bandwidth the current "ctx" object is already=20
pretty large, right, because it contains all the pubkeys and all the=20
messages (though in bitcoin they could be implicit perhaps).

(I won't mention the other idea, which is going back to MuSig1 style and=20
just committing to R, because that's what both MuSig2 and FROST went away=
=20
from, preferring fewer rounds.)

By the way after writing this overly long post I realised I didn't even get=
=20
in to the really tricky part of the algorithm, the "check our key and=20
message appears once" part because of the multisig-to-aggregated-sig=20
transformation and the hole previously identified in it, which to be fair=
=20
is the most interesting bit. Oh well, another time!

Cheers,
AdamISZ/waxwing
On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wrote:

> Hi list,
>
> Cross-Input Signature Aggregation (CISA) has been a recurring topic here,=
=20
> aiming
> to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yanni=
ck
> Seurin and I recently published DahLIAS, the first interactive aggregate
> signature scheme with constant-size signatures (64 bytes) compatible with
> secp256k1.
>
> https://eprint.iacr.org/2025/692.pdf
>
> Recall that in an aggregate signature scheme, each signer contributes=20
> their own
> message, which distinguishes it from multi- and threshold signatures,=20
> where all
> signers sign the same message. This makes aggregate signature schemes the
> natural cryptographic primitive for cross-input signature aggregation=20
> because
> each transaction input typically requires signing a different message.
>
> Previous candidates for constant-size aggregate signatures either:
> - Required cryptographic assumptions quite different from the discrete=20
> logarithm
> problem on secp256k1 currently used in Bitcoin signatures (e.g., groups=
=20
> with
> efficient pairings).
> - Were "folklore" constructions, lacking detailed descriptions and securi=
ty
> proofs.
>
> Besides presenting DahLIAS, the paper provides a proof that a class of=20
> these
> folklore constructions are indeed secure if the signer does _not_ use key
> tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, w=
e=20
> show
> that there exists a concrete attack against a folklore aggregate signatur=
e
> scheme derived from MuSig2 when key tweaking is used.
>
> In contrast, DahLIAS is proven to be compatible with key tweaking.=20
> Moreover, it
> requires two rounds of communication for signing, where the first round=
=20
> can be
> run before the messages to be signed are known. Verification of DahLIAS
> signatures is asymptotically twice as fast as half-aggregate Schnorr=20
> signatures
> and as batch verification of individual Schnorr signatures.
>
> We believe DahLIAS offers an attractive building block for a potential CI=
SA
> proposal and welcome any feedback or discussion.
>
> Jonas Nick, Tim Ruffing, Yannick Seurin
>
>
> [0] See, e.g., https://cisaresearch.org/ for a summary of various CISA
> discussions.
>

--=20
You received this message because you are subscribed to the Google Groups "=
Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
039cb943-5c94-44ba-929b-abec281082a8n%40googlegroups.com.

------=_Part_63931_1260739144.1745681452380
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>Some comments/questions on the general structure of the scheme:</div><=
div><br /></div><div>When I started thinking about ways to change the algor=
ithm, I started to appreciate it more :) Although this algo is not specific=
 to Bitcoin I'm viewing it 100% through that lens here. Some thoughts:</div=
><div><br /></div><div>We want this CISA algorithm to have the property tha=
t it doesn't require the blockchain (and its verifiers) to incur linear cos=
t in the number of signers/signatures. For a 100 input transaction, we get =
big gains from the owner or owners of the inputs choosing to use this algo,=
 but that would mostly be lost if either the verifying was linear in the nu=
mber, or if the size of the signature was linear in the number. So to avoid=
 that we want a (R, s) structure to be actually published, not an (R1..Rn, =
s) or a (R, s1..sn). That pretty much forces us to make a sum R for all the=
 individual component's R-values, and the same for s.</div><div><br /></div=
><div>However it doesn't quite force us to add literally everything. The pu=
bkeys *can* be kept separate, because they are retrieved implicitly from th=
e existing blockchain record, they are not published with the signature (ta=
proot). (Technically the same comment applies to the message being signed).=
 This allows us to use the more "pedestrian", "safe" idea; we are not aggre=
gating keys (as in MuSig) so we can actually add each with its own challeng=
e hash: sum( challenge_hash_i * X_i). This may worry you that there is a pe=
rformance issue because the verifier has to iterate through that whole list=
 ( the verification equation being: sG =3D?=3D R + c_1 X_1 + c_2X_2 + .. ),=
 but the paper specifically claims that comparing this with just batch veri=
fying the individual signatures (i.e. without CISA), this is twice as fast.=
</div><div><br /></div><div>So one could simplistically say "OK that's the =
pubkey side, they're treated individually so we don't have to worry about t=
hat, but what about adding the R values?" ("worry" here means: trivial key =
subtraction attacks or sophisticated Wagner/ROS grinding). And here what is=
 done is basically the same as in MuSig2, which is to say, by breaking the =
nonce into two components and including an additional challenge hash, you p=
revent the counterparty/adversary from grinding R values successfully. Note=
 that the "b" coefficient used here is more explicit about hashing the full=
 context, than it was in MuSig2: it's hashing each individual pubkey and me=
ssage as well as the R2 subcomponents for each party. This is vaguely simil=
ar to "client side validation" ideas: it's not really "validation" as in st=
ate updates, but it's having the more complex/expensive part of the calcula=
tion being done in the coordination before anything goes on-chain, and allo=
wing us to just use a single "R" value onchain that we know is safe.</div><=
div><br /></div><div>(Side note: it's worth remembering that a lot (maybe a=
 huge majority?) of the usage of CISA will be a single signer of multiple i=
nputs; for these cases there is not the same security arguments required, o=
nly that the final signature is not leaking the private key!).</div><div><b=
r /></div><div>That side note reminds me of my first question: would it not=
 be appropriate to include a proof of the zero knowledgeness property of th=
e scheme, and not only the soundness? I can kind of accept the answer "it's=
 trivial" based on the structure of the partial sig components (s_k =3D r_k=
1 + br_k2 + c_k x_k) being "identical" to baseline Schnorr?</div><div><br /=
></div><div>The side note also raises this point: would it be a good idea t=
o explicitly write down ways in which the usage of the scheme/structure can=
, and cannot, be optimised for the single-party case? Intuitively it's "obv=
ious" that you may be able to streamline it for the case where all operatio=
ns happen on the same device, with a single owner of all the private keys. =
I realize that this is a thorny point, because we explicitly want to accoun=
t for the corruption of parties that are "supposed" to be the same as the h=
onest signer, but aren't.</div><div><br /></div><div>And my last question i=
s about this multi-component-nonce technique:</div><div><br /></div><div>Di=
d you consider the idea of e.g. sending proofs of knowledge of R along with=
 R in the coordination step? This would keep the same number of rounds, and=
 I'm assuming (though not sure exactly) that it makes the security proof si=
gnificantly simpler, but my guess is you mostly dismiss such approaches as =
being too expensive for, say, constrained devices? (I imagine something lik=
e: 2 parties say, X1 sends (R1, pi_R1) and same for X2, to coordinator, the=
n sum directly for overall R; here pi_R1 is ofc just a schnorr sig on r). I=
f we're talking about bandwidth the current "ctx" object is already pretty =
large, right, because it contains all the pubkeys and all the messages (tho=
ugh in bitcoin they could be implicit perhaps).</div><div><br /></div><div>=
(I won't mention the other idea, which is going back to MuSig1 style and ju=
st committing to R, because that's what both MuSig2 and FROST went away fro=
m, preferring fewer rounds.)</div><div><br /></div><div>By the way after wr=
iting this overly long post I realised I didn't even get in to the really t=
ricky part of the algorithm, the "check our key and message appears once" p=
art because of the multisig-to-aggregated-sig transformation and the hole p=
reviously identified in it, which to be fair is the most interesting bit. O=
h well, another time!</div><div><br /></div><div>Cheers,</div><div>AdamISZ/=
waxwing</div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_at=
tr">On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wro=
te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e=
x; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hi list,
<br>
<br>Cross-Input Signature Aggregation (CISA) has been a recurring topic her=
e, aiming
<br>to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yan=
nick
<br>Seurin and I recently published DahLIAS, the first interactive aggregat=
e
<br>signature scheme with constant-size signatures (64 bytes) compatible wi=
th
<br>secp256k1.
<br>
<br><a href=3D"https://eprint.iacr.org/2025/692.pdf" target=3D"_blank" rel=
=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&am=
p;q=3Dhttps://eprint.iacr.org/2025/692.pdf&amp;source=3Dgmail&amp;ust=3D174=
5763806761000&amp;usg=3DAOvVaw2EtjcO7fqg6JikIOowq85H">https://eprint.iacr.o=
rg/2025/692.pdf</a>
<br>
<br>Recall that in an aggregate signature scheme, each signer contributes t=
heir own
<br>message, which distinguishes it from multi- and threshold signatures, w=
here all
<br>signers sign the same message. This makes aggregate signature schemes t=
he
<br>natural cryptographic primitive for cross-input signature aggregation b=
ecause
<br>each transaction input typically requires signing a different message.
<br>
<br>Previous candidates for constant-size aggregate signatures either:
<br>- Required cryptographic assumptions quite different from the discrete =
logarithm
<br>   problem on secp256k1 currently used in Bitcoin signatures (e.g., gro=
ups with
<br>   efficient pairings).
<br>- Were &quot;folklore&quot; constructions, lacking detailed description=
s and security
<br>   proofs.
<br>
<br>Besides presenting DahLIAS, the paper provides a proof that a class of =
these
<br>folklore constructions are indeed secure if the signer does _not_ use k=
ey
<br>tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,=
 we show
<br>that there exists a concrete attack against a folklore aggregate signat=
ure
<br>scheme derived from MuSig2 when key tweaking is used.
<br>
<br>In contrast, DahLIAS is proven to be compatible with key tweaking. More=
over, it
<br>requires two rounds of communication for signing, where the first round=
 can be
<br>run before the messages to be signed are known. Verification of DahLIAS
<br>signatures is asymptotically twice as fast as half-aggregate Schnorr si=
gnatures
<br>and as batch verification of individual Schnorr signatures.
<br>
<br>We believe DahLIAS offers an attractive building block for a potential =
CISA
<br>proposal and welcome any feedback or discussion.
<br>
<br>Jonas Nick, Tim Ruffing, Yannick Seurin
<br>
<br>
<br>[0] See, e.g., <a href=3D"https://cisaresearch.org/" target=3D"_blank" =
rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&amp;q=3Dhttps://cisaresearch.org/&amp;source=3Dgmail&amp;ust=3D17457638067=
61000&amp;usg=3DAOvVaw2JSE03N5G02-3HEV2G6Yjm">https://cisaresearch.org/</a>=
 for a summary of various CISA
<br>     discussions.
<br></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/039cb943-5c94-44ba-929b-abec281082a8n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/039cb943-5c94-44ba-929b-abec281082a8n%40googlegroups.com</a>.<br />

------=_Part_63931_1260739144.1745681452380--

------=_Part_63930_85546993.1745681452380--