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
|
Delivery-date: Thu, 17 Apr 2025 09:38:52 -0700
Received: from mail-oa1-f57.google.com ([209.85.160.57])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDD5RM5R7QJRBEO5QTAAMGQE2Q3ELEA@googlegroups.com>)
id 1u5SGJ-0008Ef-Tn
for bitcoindev@gnusha.org; Thu, 17 Apr 2025 09:38:52 -0700
Received: by mail-oa1-f57.google.com with SMTP id 586e51a60fabf-2cc00fc06fdsf797667fac.2
for <bitcoindev@gnusha.org>; Thu, 17 Apr 2025 09:38:52 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1744907926; cv=pass;
d=google.com; s=arc-20240605;
b=VRYHxCGQW1fsmELDOiv7e46z0XvFHgbfUe/oNkkdvxindTtWbJt68tjcoywuz0dR3d
MIezYPXb3oPFzl6qp4GhjGgjAn4dhvJU4uMxnfyZgW9clkW/145NLNba6fhYaEOl/Cg1
vUQ/abOEwSQaXx9Cgyp7878kOoQlbMkTuzvC2fCKgfbeGRpCC9C7YGbdBg+Or5IL1F8p
A6CiALofulfwbTcctKoZKoN+5/lG47If6BJ5Pn3Csl9OE/TLw95VI7lkpzmf5j0a80z0
Ktc3zcjTUEHHKbT/8je9lV8TCBT8OmlrPH1Riwu4mXOsZ5pyMgJrZgL/9RmKgaCTWjHm
wshQ==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:subject:from:to:content-language
:user-agent:mime-version:date:message-id:sender:dkim-signature;
bh=fsDJ3KAcXXlfeX6t1jEjjOqZCcvZJhsYqJntwheszIU=;
fh=mQeUe5VpuU1BuKbKf6hvxik0kCQJIiYk0g5TM3k+7PY=;
b=XB7Z3/PhD0bpVjJeCkffwaQC5hVG/i+KXWJt4HvtnQu4Epn5Qbg3aQpgBnoDKevm8A
RjXkcXBK0Y5iRgNUrhKmcNoP5tg71fCcpAY3/OwzJV870E0j8ftYzYYc+5QY9wIP+HSZ
P+YHfYpvfpqBS64/5t0ZGun/S/MdOvJRG2iUcUs3UO8KfN3kR2mXAzuhvc1QQwknjDPG
wMr79VQumffn4sWX+uQdNIl4PbGC2av4+v6v6RlMLhUX0JX5NoIfmUGcgLreCVBlnPKX
kUr4Q1Zmmdpw5FRbiuIk1MaHay042zjaQibABL1YdVaT6gRamv9xE5/gDv9UHWhfBNNf
FJeQ==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZYUsD9Gu;
spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1744907926; x=1745512726; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:subject:from:to:content-language:user-agent
:mime-version:date:message-id:sender:from:to:cc:subject:date
:message-id:reply-to;
bh=fsDJ3KAcXXlfeX6t1jEjjOqZCcvZJhsYqJntwheszIU=;
b=TLxctsEQUhdNW++qYVI/KO0csopYOdFv1XYJv7EnGsQj5b9Dfv6nBFEu0XelbTffat
aDpjbgGY6qALhGKtr6z/Pw2NJ+RmxictlW+SxisXuHEeo90PjOPoV5VykX4inZDX7Cxh
SjmqaaaSqDTC2QwTdSC3ObltG1k4tlsS7jbP1uqmOCa2N6fTyI/5JcE/qtXTncW5ZBso
5lc1AQyAGtgBaA6zZlQ3NMVLr4Bz4H08+d6ijJHOXBZU32JSFAxtSl4FJomEmKr+thoc
ZsOg4yJE5lcC7Fm5T7EFX8wt1XhcRKTbZp+9yGLydMK90AfSNMXV9vA9UDXozTIcU4rN
2abQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1744907926; x=1745512726;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:subject:from:to:content-language:user-agent
:mime-version:date:message-id:sender:x-beenthere:x-gm-message-state
:from:to:cc:subject:date:message-id:reply-to;
bh=fsDJ3KAcXXlfeX6t1jEjjOqZCcvZJhsYqJntwheszIU=;
b=fg7mHtxkML9j0zLYvaTK5Fk9Qvw2OXcPvmkcx8nMlY1fR1NtVV8Ig6S5E7gRmUY41u
8p2FDxqWyO/R1qT/FLZEshG8FsKP8JAldtpDAppY9BkhiuCIVBV7c+BjxvY0xQUSps5j
8i8od8iBBWXPla/yDM2uBH+Y522LnX6zGvD6psuB5LkaPpni9KDUIRnwRrn3hCzRrnlh
5oGT1UHRv6GYeSiOFvzqQa36DYjBiLGAQVPqHcw3ziCHsGQTYDzIH5hDaqyUADo/yzto
CUXm4LbTwt0AA4QUGmkMF8eF8KLG31EJFic1PJ7iA/WLP+WOrYY/kCaCIkTDrx4YcBNR
ceyA==
X-Forwarded-Encrypted: i=2; AJvYcCVNKRzA3ItQScxBJJvVbZccNYi/MoNVd0nEai/ISUHhLLXc8xoRam7+Rh/pA1otiHw+vksYfMulaNT6@gnusha.org
X-Gm-Message-State: AOJu0YwjgjWaYXaa0W33kbfrIXWJmSYr9B7qfJNIPMwDFBYW8vX/2Nyb
nclrFBj7ePAlTq8V63E41g8QCgWbizAsf59/wW3eDbbdiH6xM3+j
X-Google-Smtp-Source: AGHT+IHoJljZMQCRzmpCP3Bp0EiZAaxCMyQ8MQoH60O6RmkIpM+yAFDIcpEkQbizsEv6B4uL/1Hx2w==
X-Received: by 2002:a05:6871:848a:b0:2a3:8331:717c with SMTP id 586e51a60fabf-2d4d2a920e3mr4035679fac.10.1744907926076;
Thu, 17 Apr 2025 09:38:46 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJ/pHV3A4d7xzcsXUi9oMBT4x0HHutq71gL8bRXXkB4wQ==
Received: by 2002:a05:6871:6502:b0:2c2:35f3:8a19 with SMTP id
586e51a60fabf-2d4eb9eb6c8ls947737fac.0.-pod-prod-03-us; Thu, 17 Apr 2025
09:38:41 -0700 (PDT)
X-Received: by 2002:a05:6808:250a:b0:3f8:498c:9ef4 with SMTP id 5614622812f47-400b021ac4emr3492732b6e.24.1744907921083;
Thu, 17 Apr 2025 09:38:41 -0700 (PDT)
Received: by 2002:ab3:1084:0:b0:293:3256:5107 with SMTP id a1c4a302cd1d6-29f11a50a26msc7a;
Thu, 17 Apr 2025 09:27:08 -0700 (PDT)
X-Received: by 2002:ac2:4e16:0:b0:54a:c4af:15 with SMTP id 2adb3069b0e04-54d6dc9f0e2mr159292e87.19.1744907226423;
Thu, 17 Apr 2025 09:27:06 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1744907226; cv=none;
d=google.com; s=arc-20240605;
b=VpXAIcvWgisJZIg2AWfcHPH5DVtBEnKIH1jL3GCJZvDPitB2ZMMDBgjCKiKOAgm482
W74cq+HwzhLS8p89g/Ht4otdtvKvezP4FFtcavLBkJuUt9Y+l0I5iDOy41Rftl43qpCh
tgCKT7W+sXTxEj5gJglmL8MnY/ZtMcHK7VzlwLx6r4JRWJM9D9oyG6+VGipQ3qSuimBV
yc7siUSZStUlkzWmYMOBe77+30Oj8Z+h1vZaoMdc12FCqSr66nMG5RF2pMFiDJdEOlvI
eaF5XQVuQmTE9EbNdXTBcse3JtrKk1cEuMDJA9lr9HBddZBDygPlFphm5fovPxt9z4+s
cEsQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=content-transfer-encoding:subject:from:to:content-language
:user-agent:mime-version:date:message-id:sender:dkim-signature;
bh=3X0PXU7CSA+1bgKzW2aHa7X13zQpBzs8wxPLfwHmw30=;
fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
b=gS4gNpeMInLu9ZAxHRp4JjGhpWmBezknd0OD8z4ZhfWWJr272zIJQSCM7ovWWGkBI3
htyT0iaDMmhiWQ7zbX04+NzDOdSwbbChsqnByxvrfj1jxUb0iWEhVntfHwUvpn+kH7S8
goLUYOU0mXId2nKw3jH1dJg9GWx1R/ifJRCMwXwoDAiwa5+xhL0RlX38cqGiVWbC/Meg
Dg+AnpPYnmbZ36fWSG01742zBLSJfLGBBr3dVWZhXVKpglx9/estv9Tv3T3WW9bHwVYD
oohn0ygjBYU43Z8xO5Jozd/hktObMgRKE/OEYt2bC+wKKCfFbI6kSqQ7FP6VRIDJzzXW
1zBA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZYUsD9Gu;
spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com;
dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
dara=pass header.i=@googlegroups.com
Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com. [2a00:1450:4864:20::329])
by gmr-mx.google.com with ESMTPS id 2adb3069b0e04-54d6dfd5e69si749e87.8.2025.04.17.09.27.06
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Thu, 17 Apr 2025 09:27:06 -0700 (PDT)
Received-SPF: pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) client-ip=2a00:1450:4864:20::329;
Received: by mail-wm1-x329.google.com with SMTP id 5b1f17b1804b1-43cf628cb14so16500185e9.1
for <bitcoindev@googlegroups.com>; Thu, 17 Apr 2025 09:27:06 -0700 (PDT)
X-Gm-Gg: ASbGnctKO7UKkgnlH4SHkzVAQ51TL2wkJuy28xjNg95HQWfE/Efg8hEecuhM17+y7Yi
8dLb8cErTl7yNRXusp161x5Fa5N2OLVrOUisxB+7xyg3Q85f0d2Ip9DMl9M6tx2maaDq04HmH+q
O12KbUReeYJ5XYFAqs9nq+t09WYUAOysiR1R+RrvNnwCWqt0bN4KOHatVMJMtgIlz87wCbIQtZk
QssW7lTIWDS2vvWFOkTs19ihxohZSwr68yxasIbQrEB47JMhwwCj/5F2Ym35eF+xR53/eAM4MBm
TctyitM0fHHPKUKtNIOnoCTBIwVHhWeENBT9xEvnfCW1Gq2k/3ioqC/9AmgbLZAAwPVJ6aM85nU
=
X-Received: by 2002:a7b:cd85:0:b0:440:69f5:f179 with SMTP id 5b1f17b1804b1-44069f5f20emr1050575e9.7.1744907225661;
Thu, 17 Apr 2025 09:27:05 -0700 (PDT)
Received: from [10.11.10.42] (p57b13477.dip0.t-ipconnect.de. [87.177.52.119])
by smtp.googlemail.com with ESMTPSA id ffacd0b85a97d-39efa4206ecsm78162f8f.17.2025.04.17.09.27.04
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Thu, 17 Apr 2025 09:27:05 -0700 (PDT)
Sender: Jonas Nick <jonasdnick@gmail.com>
Message-ID: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
Date: Thu, 17 Apr 2025 16:27:04 +0000
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Content-Language: en-US
To: bitcoindev@googlegroups.com
From: Jonas Nick <jonasd.nick@gmail.com>
Subject: [bitcoindev] DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures
Content-Type: text/plain; charset="UTF-8"; format=flowed
X-Original-Sender: jonasdnick@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@gmail.com header.s=20230601 header.b=ZYUsD9Gu; spf=pass
(google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329
as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass
(p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.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 (/)
Hi list,
Cross-Input Signature Aggregation (CISA) has been a recurring topic here, aiming
to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yannick
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 their own
message, which distinguishes it from multi- and threshold signatures, where all
signers sign the same message. This makes aggregate signature schemes the
natural cryptographic primitive for cross-input signature aggregation 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 logarithm
problem on secp256k1 currently used in Bitcoin signatures (e.g., groups with
efficient pairings).
- Were "folklore" constructions, lacking detailed descriptions and security
proofs.
Besides presenting DahLIAS, the paper provides a proof that a class of these
folklore constructions are indeed secure if the signer does _not_ use key
tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, we show
that there exists a concrete attack against a folklore aggregate signature
scheme derived from MuSig2 when key tweaking is used.
In contrast, DahLIAS is proven to be compatible with key tweaking. Moreover, it
requires two rounds of communication for signing, where the first round can be
run before the messages to be signed are known. Verification of DahLIAS
signatures is asymptotically twice as fast as half-aggregate Schnorr signatures
and as batch verification of individual Schnorr signatures.
We believe DahLIAS offers an attractive building block for a potential CISA
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.
--
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 email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/be3813bf-467d-4880-9383-2a0b0223e7e5%40gmail.com.
|
