Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

["'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>]

[-- Attachment #1.1: Type: text/plain, Size: 5425 bytes --]

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.

[-- Attachment #1.2: publickey - conduition@proton.me - 0x474891AD.asc --]
[-- Type: application/pgp-keys, Size: 649 bytes --]

[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 343 bytes --]