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
|
Delivery-date: Mon, 07 Jul 2025 03:43:26 -0700
Received: from mail-qt1-f186.google.com ([209.85.160.186])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDD5RM5R7QJRBQWJV3BQMGQEDI4SSPQ@googlegroups.com>)
id 1uYjJl-0004mU-Js
for bitcoindev@gnusha.org; Mon, 07 Jul 2025 03:43:25 -0700
Received: by mail-qt1-f186.google.com with SMTP id d75a77b69052e-4a9764b4dc9sf70381201cf.2
for <bitcoindev@gnusha.org>; Mon, 07 Jul 2025 03:43:25 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1751884999; cv=pass;
d=google.com; s=arc-20240605;
b=E79FBwYzxhHSOPZpg70A71euMGlVnkujrdcHAwiIV5o0lF6PO+fzf+JrjHX/GkjQ1+
PpTvfFwolq5cunA/NRTCkfSVHoDXO0pGD/hOQ+aT72Q2EKvQHruKOoEw8QORoTYq9uPK
y0vj66OZjrZqBPkLCcDjDTTqR/M0H6prSPBeTCZDsyXUJT+jiI8kDPwiO6UrMGwE+sWX
SAHQopKa6S4ECgvITNkV/qxliGtRS0ZHMA6FEl5fFay7WMALor/gyD5m8VXWmddnhcsW
fZ7RbzwKN2JJQJyLlv4UviGeIlehPZB9fmkDx+SOp8x1quJ9qEzRte9F2tiA9EFrcKGo
ONfQ==
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=Z3J956KgZLNBA3zRrjEfqAZSt6qS9S48IpqTHwZydWg=;
fh=VtNEVHVdlKz+f7W0vVYEBLsLb3zNYLHOVcWEodboUCY=;
b=biucNY1+f7+iZfwIXtDth8ZmIC/jT6xt/hB3te+PUWoIz0EIJV9AiXULwWPBbHOZB0
mQ7LPlJdJkqaBZxkmaWRKc0v9a7UUmpHh09jE7RmDGBnOfwBY73LTdU83HDrpQ4avcR+
vlBkq80pK7ORvBqIfmVMEzsyNAhBS5aXXJuGuBGf3t4z0oTGFRghnrFzxhty/L/jfpja
bgP/JDjNBVTBDJet419c8LqiaKIVJapgrKkez2pHg6lwbLgR3bg5cPoqcf3fYt1q+cLP
vdEGZvX17FHkcxFC63DOLqUzOzPzlfD+TQqwoOn8lm3HKcHFYUb752r48ddWl7MIAvoJ
l8gg==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=ckoXlurT;
spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f 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=1751884999; x=1752489799; 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=Z3J956KgZLNBA3zRrjEfqAZSt6qS9S48IpqTHwZydWg=;
b=mdtxZbKWd/c8sCNB1JBBvt34/1So8Dx3cbXlZ+PawtVWBdra9Iptbt0TcnJoQy5XRU
ZXGZ80WBIRU3WjMuVJnI3RSOrinQiZgl8fGfj45vcYFcuyg6pcB3INLP1bNhhuSyvwww
jj4DCE3gd2Xwk0VogKWnxetoO+wheRVNAA99GV+2TuflL9ZhHI4uHCm0XUF4Aa8UYwfP
w26HFb1ua8fKK8mbbkl+hItJkenEFDgwlXPoMBu2QLbulHvs9HeMfWCYqoReqDGNCG5Y
wTfk3r4ZI+dqZfskLqzsGm4aoKnRBoUdin8xClt9lQpaKL2fR3WQCZieEMezgEDuC52z
i5+g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1751884999; x=1752489799;
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=Z3J956KgZLNBA3zRrjEfqAZSt6qS9S48IpqTHwZydWg=;
b=nCJg3Fq3xixR4n68VNxjeZ3puzz4tcKzENu7qXmtEBo0IpQmneV8OkeJ0NGh74G3tJ
iBiV19w8lvlHmX9ngUF9roX6gKX4W/uZY1v+s1WR/j/Yuc6QAZho7Hm2o27iyq+xfWHQ
DxEg+XlEwiipKVHcm6rxUpbhuD7dd4j+cO4o1oJ/S3mUxfB13XTh/lCBsZJFu8/94j0p
C5PwL4FAOreoIAstNUB7PojShv9BE3I0zhj0YLdnGslokSPvbgP7XUn3b77PIiRhXXte
r467gegJdr+M4uOIDntkiZyalWWyV4FDr+jRxXhDdeDcKzGnltEuST28OUw0MVFgE82t
P6Gg==
X-Forwarded-Encrypted: i=2; AJvYcCX0TzLrW4WNAxoXlKZcNxTwSxUPW0I3vVd5jZMjw9Fz1LpZP6O/bWcrRPSePj+RFilm5abYdzTTr1eV@gnusha.org
X-Gm-Message-State: AOJu0YxTy226hd5MREXth4A5GtvdHXEqqciNSH5auwp2nAdiLoZAD72M
JW170zpw6m5tftXuxSFmncpLjBNwOZbnGWBpG7AhtY7mFmX9y8ZjWdb+
X-Google-Smtp-Source: AGHT+IF3P76Yt9HQFDRohpSgsqv4G28Lh8ofWoaCzdz1JV51aTh10Meft6IKWkraUaxgCsjv+7Wanw==
X-Received: by 2002:ac8:7d95:0:b0:4a7:5c51:cf5 with SMTP id d75a77b69052e-4a9987b05c2mr140636891cf.26.1751884998052;
Mon, 07 Jul 2025 03:43:18 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcLBghtiJ63+9QIaYB8S19P9yOK74tDpdAZDt/SyCekzQ==
Received: by 2002:a05:622a:50b:b0:4a5:a87e:51cf with SMTP id
d75a77b69052e-4a99be502b0ls54920491cf.1.-pod-prod-07-us; Mon, 07 Jul 2025
03:43:13 -0700 (PDT)
X-Received: by 2002:a05:620a:45a0:b0:7d4:4214:2cba with SMTP id af79cd13be357-7d5df1695cdmr1314689085a.40.1751884993779;
Mon, 07 Jul 2025 03:43:13 -0700 (PDT)
Received: by 2002:a05:6504:d91:b0:2b1:9626:e73d with SMTP id a1c4a302cd1d6-2b5fb63a227msc7a;
Mon, 7 Jul 2025 03:40:38 -0700 (PDT)
X-Received: by 2002:a05:6512:2104:b0:553:522f:61bb with SMTP id 2adb3069b0e04-557e5515b2emr1747271e87.12.1751884835579;
Mon, 07 Jul 2025 03:40:35 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1751884835; cv=none;
d=google.com; s=arc-20240605;
b=C3S3CR+/bd/V5syfuoDo/0X1jqw+cGDh2J3j+hsrfIfmhVVlhdlHt/epj2ap5adeal
JY5R/LC0rqgGVQjplopmHzJT+YnCWwDsH0NhdicOD9we0AGi4MW7aXrGROwWnKpRsBTm
uYC0GPi65djQbQFOf/cCA/oGIVCnHZoFL1jmCCgsGKAXTGEh9OLcF+KyVeqB7CXVFi7X
cpqkQ+fGtGn4kxmUYqGLYLJoZVRgs8GF/i1xPzfxm57E0H6lOqK0lBFFGLZqn9rObru3
Dw449XdIQr+vHZWla70ZSNUZ1lahwNGe63tV9PT3JhlJ1aMn3w5bKeF2YnUYvppZok/c
WXOA==
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=nIsG/c2qmGFhKMnXGC8sw3czuVmjz3qOppF9w+/Ya8s=;
fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
b=UKEBnJrfI+0B0AwpIzao62+g8G0P7D3iHKJn1fuhHu3FM5zMx2k/WwKohunMIVme9/
4Ak1BmKutMZ6BEySczDF1dDazz85b5qMlxbUx6rS5MegHazHXZfAoXoqY36goszcSFHe
uAWZjOw6OhyzW1QQi/Dd2YnfGBesGwnwpJ5ISY7ZJvVypvA3LZBfCZ3W+43Bm/EWerab
i3aH04RGy9m3YG6WwDDoPD3uHKDD1KzDyozG3BxBZKRpF2D1uAS9LyxHRbKeRWyAj93l
v769BtHIVuRymfKofAWeabOkrNIS7zZONK/BD+Hm2tFoY5GCMF1Ezhj+i+B6yrw5TsF2
y1DA==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@gmail.com header.s=20230601 header.b=ckoXlurT;
spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f 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-ed1-x52f.google.com (mail-ed1-x52f.google.com. [2a00:1450:4864:20::52f])
by gmr-mx.google.com with ESMTPS id 2adb3069b0e04-5563838e94dsi151778e87.1.2025.07.07.03.40.35
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Mon, 07 Jul 2025 03:40:35 -0700 (PDT)
Received-SPF: pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f as permitted sender) client-ip=2a00:1450:4864:20::52f;
Received: by mail-ed1-x52f.google.com with SMTP id 4fb4d7f45d1cf-607cf70b00aso5691449a12.2
for <bitcoindev@googlegroups.com>; Mon, 07 Jul 2025 03:40:35 -0700 (PDT)
X-Gm-Gg: ASbGncvq52L15MwHQO8VsBkY0O8QxlgjIWpt/pZEHYmQScOV3qN15m6Fg68Q/S2sr6W
lizgAsxViQ1vDw9A+hRs/1CJpD/eKUvokyh4CdU1crWZshb6cjXeFd2XzPWut+b3xh+gcdafzuX
IkT7WaGZmO1GYt4mwpRsm/RVQmaDezwUEhRdkIANtqOxTjuY3OPtXZ3OSVmeU1YGR3LSJEJtZYw
CxD/kJjKU9OuJTTBaiGHF3/tnIVivWxo4vwfPgOi1Sbb7d1bnfV6V4tbZ5uMLQl9t7XQ3W43vsb
ZmHuen+nRSjKFBjb+vbo89fmnyHk19OaT8qJJHHmZaJhUSnvxbtwRmSlfgMIBt8N5NxSgm/XMoO
bqsZDKlDZLvExuHHrlXMGJENZPf4IIPNx5ZY=
X-Received: by 2002:a05:6402:518d:b0:607:f63b:aa31 with SMTP id 4fb4d7f45d1cf-60ff38183b4mr7249477a12.6.1751884834491;
Mon, 07 Jul 2025 03:40:34 -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 4fb4d7f45d1cf-60feaf48af3sm3846126a12.35.2025.07.07.03.40.32
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
Mon, 07 Jul 2025 03:40:33 -0700 (PDT)
Sender: Jonas Nick <jonasdnick@gmail.com>
Message-ID: <c2abfd68-f118-4951-ba4a-499fc819332f@gmail.com>
Date: Mon, 7 Jul 2025 10:40:32 +0000
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures
To: bitcoindev@googlegroups.com
References: <uCSokD_EM3XBQBiVIEeju5mPOy2OU-TTAQaavyo0Zs8s2GhAdokhJXLFpcBpG9cKF03dNZfq2kqO-PpxXouSIHsDosjYhdBGkFArC5yIHU0=@proton.me>
<QcOCx8vBMDuw4xf05H5SbIOPee2MZqV5IQa2opvAXcMeMzzFooHYL97qy5ZCLUEjqXHlHoyAucpmkwwU2i3bhO95SJrWP-oRU6mqamnTvRc=@pm.me>
<PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk=@proton.me>
Content-Language: en-US
From: Jonas Nick <jonasd.nick@gmail.com>
In-Reply-To: <PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk=@proton.me>
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=ckoXlurT; spf=pass
(google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::52f
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 conduition,
Thanks for this work. I think it provides a very useful data point.
For further reductions in size, it may be worth looking into "Target Sum
Winternitz" [0], where the checksum is hardcoded into the verifier instead
of being an explicit part of the signature, at the cost of additional
signing complexity. In this scheme, the signer has to hash their message
with some randomness, encode into chunks and check if the sum of the chunks
matches the checksum. If not, they rehash the message with new randomness
until they have found the randomness that results in the correct checksum.
There is also some more recent work that promises "20% to 40% improvement in
the verification cost of the signature" [1]. However, I have not read the
paper and the increase in Bitcoin Script size may eat up theoretical
reductions in verification cost.
> I believe my construction improves on Jonas', on two counts: [...] My
> script results in much smaller witnesses. 8kb vs 24kb.
I think the size difference largely comes from the fact that my
implementation [2] is based on W-OTS+ [3] and not on W-OTS. The main
difference is that W-OTS relies on some variant of collision-resistance of
the hash function, whereas W-OTS+ only relies on the weaker preimage
resistance property. W-OTS+ is also standardized as part of XMSS [4] in the
form of a variant that was proven secure a little later [5].
However, using just W-OTS and therefore relying on collision-resistance seems
okay because Bitcoin already relies on collision-resistance of SHA256. If that
property was broken, the blockchain and the transaction Merkle tree would not
provide integrity anymore, resulting in chain splits. Therefore, I suggested [6]
to change my implementation to a Winternitz variant that does rely on
collision-resistance and whose Blockchain footprint is smaller. So far, no one
has implemented that, but it would certainly be very interesting to see if a
Great Script Restoration based implementation can significantly improve over
your implementation.
[0] https://eprint.iacr.org/2025/055.pdf
[1] https://eprint.iacr.org/2025/889.pdf
[2] https://github.com/jonasnick/GreatRSI
[3] https://eprint.iacr.org/2017/965.pdf
[4] https://datatracker.ietf.org/doc/html/rfc8391
[5] https://tches.iacr.org/index.php/TCHES/article/download/8730/8330/5451
[6] https://github.com/jonasnick/GreatRSI/issues/1#issuecomment-2548062773
--
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/c2abfd68-f118-4951-ba4a-499fc819332f%40gmail.com.
|
