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
|
Delivery-date: Mon, 07 Jul 2025 18:15:50 -0700
Received: from mail-oa1-f63.google.com ([209.85.160.63])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBCL7RHHJZYJBBO7CWHBQMGQENGD6XNA@googlegroups.com>)
id 1uYww1-0004Ex-Vu
for bitcoindev@gnusha.org; Mon, 07 Jul 2025 18:15:50 -0700
Received: by mail-oa1-f63.google.com with SMTP id 586e51a60fabf-2e95bf2f61dsf3196756fac.1
for <bitcoindev@gnusha.org>; Mon, 07 Jul 2025 18:15:49 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1751937343; cv=pass;
d=google.com; s=arc-20240605;
b=dAgqbN8gHhKkG+6i08w+9eVcQiSkoaLyaTed7x6hJKdkBphqWDhsI3HT/BMQZcO22l
jHzuEB0FXfN2SFC9brKM4DCkwUIBcpUgLK53mS7Lg8drtTg6sGhY4POmJoIX2qKz4jkk
7G7FREHQJ9w4b14Vpg6o4KncdCDckxuz9oROJXF1UPhR4PmY+ybmo5Yg5GgP/WmiI8xf
z4CKy3LK2LYk9Wc1z+IRtredOMN1oNErHuHQDWgfOGuTJy9dXne4pQja3cCu9cRtVDbz
OJPUmv6qrWOW1MFsK5WpXYqTGa4y2PissFuhSdZlt1E9hraa0OOdERBLqawoI0K/LpTM
EBzQ==
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:reply-to:mime-version:feedback-id
:references:in-reply-to:message-id:subject:cc:from:to:date
:dkim-signature;
bh=KhniX7MVPqB492/nEGMFZwDaZOdDaw1BcU21F2icQqE=;
fh=55W0gd9zHgqJGE+YsV4y4Yuf59h/UWeiSUPEmHzyWIY=;
b=dmxZAbxBr95MRe4CfsKN59SOipw2nIGd+AOjD8XC/ovkiojGtiakdQ4oVr3VKWvtyt
RpCYA8zh2Ibt2maWvZaKVEKSdyhmjZaRUHz7RGvK2KokTrwG6xP9PHkXriXmObxhFZxG
Ez6MiKa8Ey4MFSCZlZTMx0KpKyGG03r0bZRhdyrgIuhhV9pNVL2cQ/otGyVjOVKst7gM
TRu/MD/3IwhhAsqsB7D7lwAd5s5VQ1/ZPGoZbfPdvo3Ba41ETWfecZ018sT2GVukOlag
vOQH4J1C5sFSazPNHzXIBRTs4GUREcF5mV087SiO5RRr/8BsT2eKjBTNa+QkglF0lQK8
FSbw==;
darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
dkim=pass header.i=@proton.me header.s=protonmail header.b=cJzNpeQX;
spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) smtp.mailfrom=conduition@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1751937343; x=1752542143; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to
:x-original-authentication-results:x-original-sender:mime-version
:feedback-id:references:in-reply-to:message-id:subject:cc:from:to
:date:from:to:cc:subject:date:message-id:reply-to;
bh=KhniX7MVPqB492/nEGMFZwDaZOdDaw1BcU21F2icQqE=;
b=HZkXJu1ztN5O2EqPabyuh9aYEMvYCogXeB2G8KVK6Yi37LaTOEf2HAebpGviZgkaj6
09j3mvS+1vPfJ0FkKe9fpTbnvX9h9wmRCji0JsnEB02fX5f2VaoX9hYqe6IvOKbaWV91
+JXZ1ZmLGwufMLYichbFvuW38SjYIXoN8zDO/+KDUlsL9aQwUrkrN20ta+H6rQA0CMjf
tsQ+81+3Q53JeDjDMsf/WqOSwMpiZvd154QEfJEXZ/bli5orTCk8aOySgfuJYYJx/GJq
7nqqrBoqBhnk+DKUgOnxONPX6gDtP0pFlznXcskJggK1d4/P7yeMBy8yEOGQt0Sb6eWr
fCJw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1751937343; x=1752542143;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:reply-to
:x-original-authentication-results:x-original-sender:mime-version
:feedback-id:references:in-reply-to:message-id:subject:cc:from:to
:date:x-beenthere:x-gm-message-state:from:to:cc:subject:date
:message-id:reply-to;
bh=KhniX7MVPqB492/nEGMFZwDaZOdDaw1BcU21F2icQqE=;
b=EcLbnWCC46WnBkOYepbbEbUrpsuF0W/wPsbtvExS4Q262FDKWtwzziKzsrJzpMwear
NxY7pB/9rtW5NFKV2l3RqsFp1e6INibAorDuDsvigqeszJ26SMB6biEEna9zk/d0bWIJ
Y3d+dCJPu6BKzBEvKEwk1/fZRepuXRv6z0ZePBHILvWcKolEWUPjMWe76n6lTFEaQFP+
D4QFw+3/Lsdava3HOK0G1pFyZvZQXbaD9HEKcA3AUz5eakl1n+P3reRxMUhXjnWj7nlm
YXwS3u5uIsu8GSBG8BNiiBpDhcbfnPN6DF/zNKIu10gThDIbR90knnA6PNHbvd4acIHJ
8XLQ==
X-Forwarded-Encrypted: i=2; AJvYcCWZu2fxC/KRXPaRDycVwdT5+RF5GSZitQArj9rugXuhmem/Aoi3TmM+ZlHtwkxK19STQ0KYLlRX/leN@gnusha.org
X-Gm-Message-State: AOJu0YwVOPhq40OrE58MMaac/ETt5daaF4xfzCuoLWlHAMa7Y/yAD7MH
E6BWPH3M/nGIQvAQ/5DmN1qhsWHlw7ndJ0VgmulSCww7DJTPaKal3kII
X-Google-Smtp-Source: AGHT+IGRW2fiWsZwreoo3n1i0D3rAk2eAUlbPsdLtn/io2IdTMkYk6Z50FbdMzCp0/b3V4K7AR2YBw==
X-Received: by 2002:a05:6870:b204:b0:2e9:925b:206f with SMTP id 586e51a60fabf-2fb70ea7b5amr668047fac.17.1751937343490;
Mon, 07 Jul 2025 18:15:43 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZflN1F3sfxB5mFKswBKKELLkbuw0rEZXrAcKCPnMdRHvw==
Received: by 2002:a05:6870:c103:b0:2d5:17b7:9f8c with SMTP id
586e51a60fabf-2f79b6b651bls1584847fac.1.-pod-prod-00-us; Mon, 07 Jul 2025
18:15:39 -0700 (PDT)
X-Received: by 2002:a05:6808:152b:b0:40a:641d:677e with SMTP id 5614622812f47-41148d481c0mr634714b6e.11.1751937339673;
Mon, 07 Jul 2025 18:15:39 -0700 (PDT)
Received: by 2002:a05:6808:870a:b0:40c:f667:a8e0 with SMTP id 5614622812f47-40cf667aaa7msb6e;
Mon, 7 Jul 2025 17:16:39 -0700 (PDT)
X-Received: by 2002:a05:6808:3a0e:b0:407:9a0a:3f54 with SMTP id 5614622812f47-411493890acmr608691b6e.14.1751933799189;
Mon, 07 Jul 2025 17:16:39 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1751933799; cv=none;
d=google.com; s=arc-20240605;
b=Gxu1Rvc1ARCL+Y8FruGxu8P+ADczoqLvsopOXhQLU3Uz3QXp/rz4r5lBxqMeCHRCir
FH8aWmVgM64pTLsGKbzBUHIFyL4v5Ir933kTZOmcErM/ptp3sJYZ51tt9guCy0WcoBmP
SeEHtdOrSzWWjuUyVt8tYdO/oe4FGJxItrOFy1UD53zPGzbHsrph9FRUXo23E1yCy+Q+
/RRWG1H6vqi/zdiJxDVUMBvWNOguC7T4XDKT+7SJPOeO+WCKkWHyidD/W6bOcuoGM1/c
P2ZlN4+WewuTcDRvkFxFgSKeEflt1O5UW3/z1gNLvTvZNA9vQbp8h0482jjMuL2L1JtQ
7Cog==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
h=mime-version:feedback-id:references:in-reply-to:message-id:subject
:cc:from:to:date:dkim-signature;
bh=+7tQjwno83wg0q6eenFVYar+jhsGFwsHHd78rVsQ8ks=;
fh=eQwyrPB7DiKLZfk3HA1+IBNTG62m+FxzJ3AFq+zftRc=;
b=UfbZ6UiKN5dq5qXoaCTKEQO4eeXdEBIs+cEoEmeqRzeua3V5nGh/SD0zF8bkZGQ5XE
TD7lqMUAg6dDZ4AexUOEoduB5KFwV1S+BAxHxnQ0ialNoFAXmIbmL4On1gskuYJyYL0d
C8eyQfyLFcdk+WaedWHUtpV0kEgm/RjZ6B4L5oPlGiFnwWZF6+scVgSQhJsstPa9BS49
ZK87Sjtadb6YRpQMDbt3PufESXR2YWIl38W5dAIMGGcBrKG/4LuwGC/DfMu/7cJqZEq6
4er8hdSpv1P81Jmt+Mv3mcbh4B5L4xWQeo1ro702ci9JDF7GXrKHl9B7tTtUp9bLokXK
NfgQ==;
dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
dkim=pass header.i=@proton.me header.s=protonmail header.b=cJzNpeQX;
spf=pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) smtp.mailfrom=conduition@proton.me;
dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
Received: from mail-24417.protonmail.ch (mail-24417.protonmail.ch. [109.224.244.17])
by gmr-mx.google.com with ESMTPS id 5614622812f47-40d02a1e4edsi398662b6e.1.2025.07.07.17.16.38
for <bitcoindev@googlegroups.com>
(version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
Mon, 07 Jul 2025 17:16:38 -0700 (PDT)
Received-SPF: pass (google.com: domain of conduition@proton.me designates 109.224.244.17 as permitted sender) client-ip=109.224.244.17;
Date: Tue, 08 Jul 2025 00:16:33 +0000
To: Anthony Towns <aj@erisian.com.au>
From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures
Message-ID: <h9N4uIp0MgaASuEBpqsHjiQb9ahGbca3mG5V6iPVumT9ICT4monwV1ScgV3kdV2ka9CkQiSqEGkxA_eqqGQJ1TtFmWUlJEhi0McZU6yGBl0=@proton.me>
In-Reply-To: <aGkYLuZZz2itqVJx@erisian.com.au>
References: <uCSokD_EM3XBQBiVIEeju5mPOy2OU-TTAQaavyo0Zs8s2GhAdokhJXLFpcBpG9cKF03dNZfq2kqO-PpxXouSIHsDosjYhdBGkFArC5yIHU0=@proton.me> <aGkYLuZZz2itqVJx@erisian.com.au>
Feedback-ID: 72003692:user:proton
X-Pm-Message-ID: 56e6b3383c1a3bbf95c80801ff6cbdc8a2db62e2
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef"; charset=utf-8
X-Original-Sender: conduition@proton.me
X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass
header.i=@proton.me header.s=protonmail header.b=cJzNpeQX; spf=pass
(google.com: domain of conduition@proton.me designates 109.224.244.17 as
permitted sender) smtp.mailfrom=conduition@proton.me; dmarc=pass
(p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=proton.me
X-Original-From: conduition <conduition@proton.me>
Reply-To: conduition <conduition@proton.me>
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: -1.0 (-)
This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef
Content-Type: multipart/mixed;boundary=---------------------8d0c2c9798e42661525f30a084d771e3
-----------------------8d0c2c9798e42661525f30a084d771e3
Content-Type: text/plain; charset="UTF-8"
Great idea AJ, I didn't think about OP_DUP OP_ADD as a
stand-in for OP_LSHIFT. That saves a bunch of bytes. We can
save even more by using `OP_SIZE` to check if the combined
number is greater than 127, since the interpreter's OP_ADD
`output` should always be canonically represented as a
2-byte value if `128 <= output <= 255` (correct?).
This lets us elide the SWAP/ROT operations, dropping it to
35 bytes per of script per iteration of that loop (down
from 58 in my first impl!). Total savings across all loops
is 736 bytes, bringing the total script+witness size down
to about 7212 bytes, or 1803 vbytes. Very groovy!
// ... <b63> <b64>
SWAP DUP ADD DUP ADD DUP ADD DUP ADD ADD
SIZE <2> EQUAL IF
<128> SWAP SUB
IFDUP NOT IF <0x80> ENDIF
ELSE
DUP NOT IF <0x00> ENDIF
ENDIF
I revised the gist with the updated bitshift code, and more
detailed comments. Thank you!
https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182#file-winternitz-ts-L100-L137
regards,
conduition
On Saturday, July 5th, 2025 at 6:54 AM, Anthony Towns <aj@erisian.com.au> wrote:
> On Sun, Jun 08, 2025 at 03:20:08AM +0000, 'conduition' via Bitcoin Development Mailing List wrote:
>
> > See a prototype implementation in pseudo-script on
> > github here.
> >
> > https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182
>
>
> I think you can do the four-bit pair to eight-bit conversion slightly
> better with:
>
> DUP 8 GREATERTHANOREQUAL # is the high-bit going to be set?
> SWAP ROT SWAP # drop that flag lower in the stack
> DUP ADD DUP ADD DUP ADD DUP ADD ADD # combine them mathematically
> SWAP IF # was the flag set?
> 128 SWAP SUB # subtract from 128 converts 0x8100-0xff00 to 0x81-0xff
> IFDUP NOT IF "0x80" ENDIF # special case 0x80 "negative zero"
> ELSE
> IFDUP NOT IF "0x00" ENDIF # special case actual 0
> ENDIF
>
> Should save about 640 bytes of script (11%, 8% total), I think.
>
> > PS If anyone would like to test this on signet, I'd
> > be more than happy to help. I couldn't get my OP_CAT
> > transactions mined for some reason so i stuck to regtest.
>
>
> inquisition.bitcoin-signet.net was down for a few days when you posted
> this, due to running out of disk space, which probably would have made
> getting txs relayed pretty hard. You'd probably have more luck now.
>
> Cheers,
> aj
>
> --
> 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/aGkYLuZZz2itqVJx%40erisian.com.au.
--
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/h9N4uIp0MgaASuEBpqsHjiQb9ahGbca3mG5V6iPVumT9ICT4monwV1ScgV3kdV2ka9CkQiSqEGkxA_eqqGQJ1TtFmWUlJEhi0McZU6yGBl0%3D%40proton.me.
-----------------------8d0c2c9798e42661525f30a084d771e3
Content-Type: application/pgp-keys; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc"
LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4ak1FWkRub0tSWUpLd1lCQkFI
YVJ3OEJBUWRBcnBZYWFjZDgwcXdocmNaQW9VbW9NSHNWS21iZWlPZUEKcFhXbk1ybFdPZkxOSzJO
dmJtUjFhWFJwYjI1QWNISnZkRzl1TG0xbElEeGpiMjVrZFdsMGFXOXVRSEJ5CmIzUnZiaTV0WlQ3
Q2pBUVFGZ29BUGdXQ1pEbm9LUVFMQ1FjSUNaQjRLV3p0aFBhenhRTVZDQW9FRmdBQwpBUUlaQVFL
YkF3SWVBUlloQkVkSWthMENNdHJMZGcxM2EzZ3BiTzJFOXJQRkFBQTZhQUVBM1RmNHdqSVoKYnox
K0diS0h4K09WQytNUXlVdi84RStoWUpjTE5QZnA0NEFBLzNiak5OTXN4WHdJTGZEM0xManNVVWFo
CitBV2JyblVjVUFqQ2R1d3hUT01LempnRVpEbm9LUklLS3dZQkJBR1hWUUVGQVFFSFFDSXYxZW5J
MU5MbAo3Zm55RzlVWk1wQ3ZsdG5vc0JrTmhQUVZxT3BXL3RKSkF3RUlCOEo0QkJnV0NBQXFCWUpr
T2VncENaQjQKS1d6dGhQYXp4UUtiREJZaEJFZElrYTBDTXRyTGRnMTNhM2dwYk8yRTlyUEZBQUFR
TFFEL2NCR2kwUDdwCkZTTkl2N1B6OVpkeUNVQjhzTy90dWZkV3NjQkNZK2ZMYTV3QkFNK0hTL3Jp
S014RGt0TkhLakRGc2EvUgpEVDFxUGNBYXZCaXc2dDZ4Ti9jRgo9Y3d5eAotLS0tLUVORCBQR1Ag
UFVCTElDIEtFWSBCTE9DSy0tLS0tCg==
-----------------------8d0c2c9798e42661525f30a084d771e3--
--------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"
-----BEGIN PGP SIGNATURE-----
Version: ProtonMail
wrsEARYKAG0FgmhsY1IJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp
b25zLm9wZW5wZ3Bqcy5vcmf0ShO5xMGOnx8BOa3ifmhpGx3YyMIFpHXiwET0
/mhGqBYhBEdIka0CMtrLdg13a3gpbO2E9rPFAADJzgD+LWbQDKSJBvCSIHlv
hId1rN7Hv1/ApIYFgZuDGK6wdxcBAOElQ7OukfmANqfir/fEJ3Xsvhpv9aK1
8aDitoNmZDUF
=p+p3
-----END PGP SIGNATURE-----
--------8724a8f0d23825c5842189b2d4d6a437660188c4965ef56dc2ae196e5ad045ef--
|
