Delivery-date: Wed, 09 Jul 2025 11:56:13 -0700
Received-SPF: pass (google.com: domain of conduition@proton.me designates 185.70.43.22 as permitted sender) client-ip=185.70.43.22;
Date: Tue, 08 Jul 2025 07:03:37 +0000
To: Jonas Nick <jonasd.nick@gmail.com>
From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Cc: bitcoindev@googlegroups.com
Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures
Message-ID: <KZQi7ji4ah0m_ox6EN3K4cEsYvHbX-FFBmsPvdC5QXK_BfxuxCDwR6X2f0J32FoqOlN_MajHRmFPql5Pf0eCrlY531lOfVtTyFSBXclOizM=@proton.me>
In-Reply-To: <Um1180WhyfREJS4CHTfTCzAuDywzNlFlsaIFFwLEGcETcwKCDuJMgSwSs4idfqgCDqtMTuc4FUmcTHWnK2z_tzxw8bdVD9zDiGTCfdbJFjs=@proton.me>
References: <uCSokD_EM3XBQBiVIEeju5mPOy2OU-TTAQaavyo0Zs8s2GhAdokhJXLFpcBpG9cKF03dNZfq2kqO-PpxXouSIHsDosjYhdBGkFArC5yIHU0=@proton.me> <QcOCx8vBMDuw4xf05H5SbIOPee2MZqV5IQa2opvAXcMeMzzFooHYL97qy5ZCLUEjqXHlHoyAucpmkwwU2i3bhO95SJrWP-oRU6mqamnTvRc=@pm.me> <PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk=@proton.me> <c2abfd68-f118-4951-ba4a-499fc819332f@gmail.com> <Um1180WhyfREJS4CHTfTCzAuDywzNlFlsaIFFwLEGcETcwKCDuJMgSwSs4idfqgCDqtMTuc4FUmcTHWnK2z_tzxw8bdVD9zDiGTCfdbJFjs=@proton.me>
Feedback-ID: 72003692:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------75a7c93bd1b7370eec335449886f993bb19b0c5d7b132796a789f7640b3b9c89"; charset=utf-8
Reply-To: conduition <conduition@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------75a7c93bd1b7370eec335449886f993bb19b0c5d7b132796a789f7640b3b9c89
Content-Type: multipart/mixed;boundary=---------------------d1a8b04e81674bfce2ab1ca604336e20

-----------------------d1a8b04e81674bfce2ab1ca604336e20
Content-Type: text/plain; charset="UTF-8"

Minor correction: the optimal checksum for w = 16 should actually be 480, not 512. I forgot the average of [0, 16) is actually 7.5 and not 8.

On Monday, July 7th, 2025 at 6:15 PM, 'conduition' via Bitcoin Development Mailing List <bitcoindev@googlegroups.com> wrote:

> Hey Jonas, really cool to hear from you on this :)
> 

> > 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.
> 

> 

> If you take a second look at the script, we're actually
> doing fixed-sum winternitz [0]. For w = 16 as I selected,
> the optimal checksum for efficient signing is 512. You can
> compute the optimal checksum with the expression `w*(n / log2(w))/2` where n is the bit-length of the message to
> sign.
> 

> Though unlike traditional fixed-sum WOTS, I didn't
> implement the random salt counter appended to the sig, as
> it isn't strictly needed. Remember: we're not WOTS-signing
> a static TX sighash - we're signing an EC signature which
> in turn signs the TX sighash. We can retry the EC signature
> generation step with a new nonce `R` unlimited times until
> we get an `(R, s)` pair whose hash fits the hardcoded
> checksum requirement.
> 

> > 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.
> 

> 

> Agreed. AFAICT, the only reason we'd use WOTS+ over stock
> WOTS (w/o randomizers) would be if we wanted to use a less
> collision-resistant hash algo (RMD160) as the primary hash
> function. Someone would need to do the math to see if the
> hash size savings are enough to offset the added script
> size cost.
> 

> Maybe you're not the right person to ask, but riddle me
> this: Would OP_HASH160 (aka rmd160(sha256(...))) be a
> possible contender for the hash function here, to shrink
> the witness size further while still retaining some of the
> collision resistance of SHA256?
> 

> [0]: https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182#file-winternitz-ts-L95-L98
> 

> regards,
> conduition
> 

> On Monday, July 7th, 2025 at 3:43 AM, Jonas Nick jonasd.nick@gmail.com wrote:
> 

> > 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.
> 

> 

> --
> 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/Um1180WhyfREJS4CHTfTCzAuDywzNlFlsaIFFwLEGcETcwKCDuJMgSwSs4idfqgCDqtMTuc4FUmcTHWnK2z_tzxw8bdVD9zDiGTCfdbJFjs%3D%40proton.me.

-- 
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/KZQi7ji4ah0m_ox6EN3K4cEsYvHbX-FFBmsPvdC5QXK_BfxuxCDwR6X2f0J32FoqOlN_MajHRmFPql5Pf0eCrlY531lOfVtTyFSBXclOizM%3D%40proton.me.

-----------------------d1a8b04e81674bfce2ab1ca604336e20
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==
-----------------------d1a8b04e81674bfce2ab1ca604336e20--

--------75a7c93bd1b7370eec335449886f993bb19b0c5d7b132796a789f7640b3b9c89
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wrsEARYKAG0FgmhswrgJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp
b25zLm9wZW5wZ3Bqcy5vcmd+1mKdzVwk4Enc4sg0aJDCG9iYGtxGz8xweyCx
+l2A4RYhBEdIka0CMtrLdg13a3gpbO2E9rPFAADZ4AD+Px2pFVbGvpbi+SZ+
Ub1xj+8ArCkgRwcXjw8RucE5RIkA/i4PxJ6kvMKX86kf92l8O2ZUB4hpZUiR
m8RsGCLvfH0M
=6tFN
-----END PGP SIGNATURE-----


--------75a7c93bd1b7370eec335449886f993bb19b0c5d7b132796a789f7640b3b9c89--