Hi list, Jeremy Rubin's earlier work has already shown OP_CAT enables Lamport signatures [0]. Jeremy's approach gives us a script pubkey which is a little less than 8600 bytes, plus a witness stack of 2121 bytes, for a total witness size of ~10721 bytes. The scheme relied on using RMD-160 hashes to achieve these sizes - SHA256 would've bloated the scheme significantly. I'd like to concretely demonstrate one more post-quantum signature algorithm which OP_CAT enables: Winternitz One-Time Signatures (WOTS) [1]. Specifically we instantiate Winternitz using SHA256 hash chains of length 16 (AKA "w = 16"), with a checksum compression technique inspired by page 4 of the SPHINCS+ paper [2]. We use WOTS to sign the SHA256 hash of an EC signature, which is validated by OP_CHECKSIG. We break this 256 bit hash up into 64 words of 4 bits each, and then use script trickery to concatenate and verify the 64 words match the EC signature's hash. See a prototype implementation in pseudo-script on github here. https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182 With this approach, the script + witness stack are substantially smaller than with Lamport signatures, even when using 256-bit hashes. More concretely, the serialized witness stack looks like this: 64 x SHA256 hashes 2112 bytes 64 x message words 128 bytes 1 x BIP340 EC signature 65 bytes 1 x Witness Script 5610 bytes 1 x Control block 33 bytes -------------------------------------- Total 7948 bytes I suspect you could shrink this by a few more kilobytes: - If you were willing to compromise on security in favor of compactness, you could use RMD-160 hash chains, or sign RMD160(SHA256(ec_signature)) so that you only need to sign 40 words instead of 64 words. - One could experiment with Winternitz chains of length 4, breaking the message into 2-bit words instead of 4-bit words. - I'm no script wizard, so I'm sure there are optimizations left to make on the witness script. To be useful, this locking script would need to be hidden as a tapscript leaf and revealed only after OP_CAT activation. Naturally, this assumes key-path spending is disabled, otherwise the whole scheme would be easily defeated by a quantum attacker. I successfully tested this protocol out using a Bitcoin Inquisition [3] regtest node. A file containing example transactions is attached to this email. The second TX spends the first, using this Winternitz scheme. The spending TX comes in at only 2070 vbytes after accounting for the witness discount. (Big thanks to kallewoof for making the btcdeb debugging tool [4], without which I would've never gotten the script working) regards, conduition [0]: https://gnusha.org/pi/bitcoindev/CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com [1]: https://eprint.iacr.org/2011/191.pdf [2]: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=10179381 [3]: https://github.com/bitcoin-inquisition/bitcoin [4]: https://github.com/kallewoof/btcdeb 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. -- 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/uCSokD_EM3XBQBiVIEeju5mPOy2OU-TTAQaavyo0Zs8s2GhAdokhJXLFpcBpG9cKF03dNZfq2kqO-PpxXouSIHsDosjYhdBGkFArC5yIHU0%3D%40proton.me.