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 [email protected]. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/c2abfd68-f118-4951-ba4a-499fc819332f%40gmail.com.
