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
|
Delivery-date: Thu, 17 Jul 2025 06:34:55 -0700
Received: from mail-yw1-f188.google.com ([209.85.128.188])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDD5RM5R7QJRB5PX4PBQMGQEBK7AY2Q@googlegroups.com>)
id 1ucOlD-0006tN-Fk
for bitcoindev@gnusha.org; Thu, 17 Jul 2025 06:34:55 -0700
Received: by mail-yw1-f188.google.com with SMTP id 00721157ae682-713ff70871dsf9464947b3.1
for <bitcoindev@gnusha.org>; Thu, 17 Jul 2025 06:34:55 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1752759289; cv=pass;
d=google.com; s=arc-20240605;
b=LwuAqCKGZN6K8rii+kR4YZOFQ9sIGdnhu/TBeunGO0CKhQeJVoizLuCY6ZOYMMiPiU
cJ9g4FLD+wn/WvlTSv6379eNM9aKghIM9BPWSqPL4qfeNpRUFI/Vw7b37BUhVO9BnB3k
pSH8WSKMaCaJUDhjHwQuBgJnFP6kgxhtpDlF1/ejQ+xbWSDknD5wmg9ulGQRdyeCOD6Y
X5w/wFMZfAX4P8zucC++H1/GKj4cU9sKe2e3Vzl6wXzsLlk0ICd4K8Oj7l//RcE6294N
6wDykRxEfFC00BZdj3ku5H3JpjbxeDz8/0XFBTeDqc69V5uzmfEobDMboT9C/gaWPVG5
JjXg==
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:in-reply-to:from:content-language
:references:to:subject:user-agent:mime-version:date:message-id
:sender:dkim-signature;
bh=YxTucA+Syi1LRtoe0hb+U5cLUdbzKGDSsTf0zIKzOaw=;
fh=L7lh9zRRuBdfziV5SPwDP3lJZsDu9EVB9IjhLuNDf+4=;
b=AgV/Jx3gP6MZC5GlQz+ObXc62in2sP4VijJfTSOJMOjJ18+AfqD8XQMEFhcchoIzQw
5pq8TGrlpuVHzX/Q7fWk2VjBOKl1vWc0e/u1WJT2ErVfWQax8w0QBadfZlRhL7U+4Hne
r0j275LpgZ9oFrLfsRZ6Apomu+UTm2YHhIv+TE1nrD5UF/iJ10NTVe69HJWC/hozbqXb
yA518RXHr3m1qtTrgQHGs3hSuTpO0tfwyNaSxRu6nIWE/U3ozsFaxcyIt9oy6PhejqLy
EDPRZQolmpg3DCdouf7X+0LQFaR/8qSBejsWKVAo1zA6ZsbSeZVpIaK3b1J59s9tEkPP
Jd4A==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZOylojUX;
spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::62f 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=1752759289; x=1753364089; 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:in-reply-to:from:content-language:references:to
:subject:user-agent:mime-version:date:message-id:sender:from:to:cc
:subject:date:message-id:reply-to;
bh=YxTucA+Syi1LRtoe0hb+U5cLUdbzKGDSsTf0zIKzOaw=;
b=YCmb3zwBw2/wR53Ad32tTUKwuu28y4kelcEc3f2BXqeoK918+ce3vgpzxs15dh4v4X
YbR73wQebpZupJ6n4eJHHMC8LWa+aLKapf4HWNBOfEc1LZpkfxqq7qFt6VP6sHsn906e
tH/EQjrACjPM54e4iANe7doMq3P6Z+Ha+/xwXNycskDJU/jZ7yke7ilUKQtI7SHktxBF
df4NnUjn+wfkOS7usrnaaSHiJkHosK2svZt+QvlyP7yX21hjfZqOOB3gUBs8qEghSD9R
t3XlHiZUaqeLOpkitI84jptbYvg0up3d0XRo3wKutIcf5JSBMo3tZyNIjk1ubihga9In
G9qA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1752759289; x=1753364089;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-authentication-results
:x-original-sender:in-reply-to:from:content-language:references:to
:subject:user-agent:mime-version:date:message-id:sender:x-beenthere
:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
bh=YxTucA+Syi1LRtoe0hb+U5cLUdbzKGDSsTf0zIKzOaw=;
b=WC4ixRg4DNfFKN3nxy2p2Jqb63S53MPfoDAz1m/oli8GL9ZV1VZWFBjdrlCS5Sd0/q
cm5oaa0SxB82Xsz8u8Ld1U2Gt7nU1J14N5yk0Hf/vn5o81JKc/3ImLabfOxwl39DhXPk
SyRitKJyCQBRHySC4uYGv2q2NBkjiXhxZM8URah+N/iJJXDWvcpmm5kZqgVAOCIu6HYN
CwdeCNKoalwu3pyaga094lgSwPLdPF5tT0l1/n3ppPGi5FuwuyGw/RTluidb1jlPccnZ
VWkzV/bNx/EbyRLfnwPqT+4mptW1yTWKC23p7HNA7mIbCu1EajlFRQsUH6YStYXcktZB
J/XA==
X-Forwarded-Encrypted: i=2; AJvYcCWM6cHSjD735iZLM/qCxdVScqhhMwDzUgN9UpuGykPre4tlLgHwQEdOzG2PcToTPKRYIKu6mgBbt5dY@gnusha.org
X-Gm-Message-State: AOJu0YxYsgsLU8T9o7iBHj+yzkJDJ5KcsYAl5CRdRhGaDMc1oeLN0lIn
5KAgvP+ou30kA2x8OKyZvNUrlXYWE9bacW9n8Ldaa1/tqZZhPTbqep6p
X-Google-Smtp-Source: AGHT+IEUEQzz8NMb7/yGHLL5SspUHrsGGQYRCQ4UaK1qH6NnCtFjf3kaEsjtylbSqHNVXWy3AzgZ7w==
X-Received: by 2002:a05:6902:220d:b0:e87:add0:2e9c with SMTP id 3f1490d57ef6-e8bc24f1a74mr7279129276.31.1752759289000;
Thu, 17 Jul 2025 06:34:49 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZfhTyuTKsevrpb8lDdqHCCv1AgNSSywEUvDWbAfMIjiwg==
Received: by 2002:a05:6902:610c:b0:e82:492d:12c with SMTP id
3f1490d57ef6-e8bd449aa55ls1107246276.0.-pod-prod-06-us; Thu, 17 Jul 2025
06:34:45 -0700 (PDT)
X-Received: by 2002:a05:690c:f07:b0:718:3992:9144 with SMTP id 00721157ae682-71839929448mr80511027b3.40.1752759285002;
Thu, 17 Jul 2025 06:34:45 -0700 (PDT)
Received: by 2002:a05:600c:198e:b0:456:ce4:c44e with SMTP id 5b1f17b1804b1-4562dbf0f83ms5e9;
Thu, 17 Jul 2025 06:15:45 -0700 (PDT)
X-Received: by 2002:a05:6000:43c8:b0:3a6:ec1b:5742 with SMTP id ffacd0b85a97d-3b60dd4f78amr4896125f8f.22.1752758142779;
Thu, 17 Jul 2025 06:15:42 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1752758142; cv=none;
d=google.com; s=arc-20240605;
b=HLIpuNsPKlpPdK4xK+DiFbZNbgshADZ8cemRkSPVDzJ4dg9ZI5SCq1ygHeKpvdd97a
BvKwjwjqwLUqZrM+zHbPj1cW4QjRMEvoYfZndx2qgfRnJxISxP+Z9NLG7Rq0bM6HxKjF
/74Q6RKuJpxDD8tMIA5fVRjlTu8kLBQ2nKTZL+PI57ZbQfUn3dCU8KGtmysKVvIl6rEq
yyikolpYSZ0/Fyw56FDasJPJS91aafXLC02yKO6sRPkuIlelgPrQT65mcWZZCzFSApjC
PYJA4PkdbwB3Ypmm0FUzTf/vC0nmMXa+lxkWPUCsmHr2sG7jPdVyaUKIwE0tPD5ZW9aI
Z8lA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=content-transfer-encoding:in-reply-to:from:content-language
:references:to:subject:user-agent:mime-version:date:message-id
:sender:dkim-signature;
bh=aOVyOrJ4Gd/0aVuiP5YdmzyJ+3ZzV8lEScr2ps0QM/Y=;
fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
b=NraEowMxFixkLPS2ZBS9rAVaove7OQPQM+7Bmj2gWVQ0SAiDqA/d4Ka8ArbG/sKl0Y
8Y+Wm4TZTa18gBYhbY07MsfvIJlzEpr/7UTTCRELFBeGdBfYY22hArPYabJYa16qKA0f
Oe+pJKRHam4eQlaastDuIqvhIEB0ElDSmCW8ZjwDgKVAMhakgeZAFVsHbBIsRAfSSh8f
HX80Dg6vRb1lK/xKYN0HHIj82jmiJCinQf005ReMCVqiHpGYSCm61W0pwDY5qfQUkRcy
u/2s4DDH81gIl6Fr7vbm1UQd49HGZKTV5hWuqFcqJDaBNG/jNxgM6Y6aVgf34+vV7XpZ
KK/w==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZOylojUX;
spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::62f 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-ej1-x62f.google.com (mail-ej1-x62f.google.com. [2a00:1450:4864:20::62f])
by gmr-mx.google.com with ESMTPS id ffacd0b85a97d-3b5e8e020ffsi466074f8f.5.2025.07.17.06.15.42
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Thu, 17 Jul 2025 06:15:42 -0700 (PDT)
Received-SPF: pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::62f as permitted sender) client-ip=2a00:1450:4864:20::62f;
Received: by mail-ej1-x62f.google.com with SMTP id a640c23a62f3a-ae360b6249fso142925566b.1
for <bitcoindev@googlegroups.com>; Thu, 17 Jul 2025 06:15:42 -0700 (PDT)
X-Gm-Gg: ASbGncvMt6eYC2LT0Fp7A+ZfPoRLkuOgT+0ob0oTYV1HRxr+QjSzjOrld1a6OltnEAo
jTQEm67BA44rG0TkElEj6t2p8wrxSXGF6JxFUQPpWmP+7EsWV8sdHSe+Xoq19QSGjGVHSBlAxE2
hLnbk4VviZ0M8xD0/JXDOD2re3mYNe2s4JM6SN/+hgTDrS7lUsM2CXCtNM5kYI6PoLPFGXtiCFf
WT09/dbzsFvEIudxXN1zBHirUvbE4SEKtM60hSsm5IeDszXl98Yy6yUmU+zyexzZN5zVledrc9f
gvCu9eaVT6N543O9OVODJO+Hhj/sSaYx9bIhVySbiCFKCsY8oDycc+pb2SjxEIl1jXABnqoQqWZ
pLgBHRLDUiUnDBjsT7tXSzqDBA2PR4TPwCA+XjCbxdwQwWukwrTmhYgiqG7wUgE9duq8BHwQ=
X-Received: by 2002:a17:907:944c:b0:ae0:b3be:f214 with SMTP id a640c23a62f3a-ae9c994a31emr693855366b.9.1752758141839;
Thu, 17 Jul 2025 06:15:41 -0700 (PDT)
Received: from [192.168.1.55] (188-22-134-228.adsl.highway.telekom.at. [188.22.134.228])
by smtp.googlemail.com with ESMTPSA id a640c23a62f3a-ae6e8294bc2sm1361773966b.135.2025.07.17.06.15.40
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Thu, 17 Jul 2025 06:15:41 -0700 (PDT)
Sender: Jonas Nick <jonasdnick@gmail.com>
Message-ID: <e15cf0db-bc04-454d-8d63-029bd864d08b@gmail.com>
Date: Thu, 17 Jul 2025 13:15:40 +0000
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive
Aggregate Signatures
To: bitcoindev@googlegroups.com
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
<039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
<604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com>
<f9e082e3-4079-40b6-aa49-5d1b9b3b1e29@gmail.com>
<a9f133ff-1d8e-45a3-8186-79fb52bbd467n@googlegroups.com>
<3f23ebaa-02c7-45d1-bf57-9baf48c133a3n@googlegroups.com>
<437237c5f0debe352aafd0a184d6266c14d6e142.camel@timruffing.de>
<182e01b0-30f0-4dec-b4bb-5057bd4ef89fn@googlegroups.com>
Content-Language: en-US
From: Jonas Nick <jonasd.nick@gmail.com>
In-Reply-To: <182e01b0-30f0-4dec-b4bb-5057bd4ef89fn@googlegroups.com>
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=ZOylojUX; spf=pass
(google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::62f
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 waxwing,
Thanks again for your comments.
> My initial reaction would be, since it's not worsening the scaling of the
> verifier, does it matter?
I think saving time in signing does matter (3 group exponentiations requiring
O(1) group operations in total vs. O(n/log n) group operations); for example, in
constrained signing devices as you mention. In particular, the "single-b"
variant with the larger signing cost doesn't appear to have advantages (see
below) compared to "multi-b" which has lower signing cost.
> The scheme is explicitly not limited to Bitcoin, nor blockchains, though,
> so there's that; is that relevant here?
The scheme is not limited to Bitcoin, but the main application we designed for
is Bitcoin. I agree that verification performance is of primary importance. We
would choose a scheme with lower signing performance, if it gives us a better
verification performance in return (if the trade-off is reasonable).
> Yes, those are some interesting points to consider. On one detail: "In any
> case, identifying disruptive participants will work reliably only if the
> coordinator is honest, so let's assume this." -- this could also be addressed
> with proofs of knowledge, no?
Maybe I misunderstand what you're getting at, but I don't understand how proofs
of knowledge would get rid of the honest coordinator requirement for identifying
disruptive signers. Moreover, both R_{2,i} and R_{2,j} could have a valid proof
of knowledge attached (for example, if parties i and j share the dlog of R_{2,i}
= R_{2,j}).
> Anyway, for me it was more a sort of preference for purely algebraic
> algorithms. It's a little fanciful, but algebraic algorithms are easier to
> encode in circuits in zero knowledge (though things like equality checks are
> entirely doable ofc!) and maybe easier to "encode" into modular schemes that
> use them as a building block. Maybe. Less conditional branches / loops to
> traverse in the code?
Why exactly would it be easier to encode the multi-b variant in a circuit? The
single-b variant requires checking whether there exists i such that R_{2,i}
matches a fixed R_{2,j}. In the multi-b variant we'd need to compute the product
of all R_{2,i}^{b_i}, which, even with a multiexp implementation, requires at
least visiting all elements plus the actual multiexponentiation involving
O(n/log n) group operations. So encoding the single-b variant appears to be
strictly easier.
--
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/e15cf0db-bc04-454d-8d63-029bd864d08b%40gmail.com.
|
