Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

[Jonas Nick <jonasd.nick@gmail.com>]

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.