[bitcoindev] OP_CAT Enables Winternitz Signatures

[bitcoindev] OP_CAT Enables Winternitz Signatures

['conduition' via Bitcoin Development Mailing List]

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

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.

[-- Attachment #1.2: opcat_txs.txt --]
[-- Type: text/plain, Size: 16477 bytes --]

020000000001011600859fc9c11266a660092eb6f648b4dc3467e037719a5972c84623109fcc3b0100000000fdffffff0200e1f50500000000225120b341a660f69cee5eee853ef774b22d53d9498f5a3ec3cfe7ab05085f36dfabff4c0f1d1801000000225120675dd55037f571063c5398c50f16d744e6e944ab43fbd2d2829e8666067b69d40140c2c009f4a5864c1727c18cb3896b80c15f44f024fd3ddecb884f722c86b2ba769b85b8d76f7d72ba30205bf7426009711b544c2d436b90e35210824aecfe8f1acc000000

02000000000101b9810ddb2fb352f2bbbbeceb823ddc77b9654b94b6fbf4e1b491b7e116a629410000000000000000000148d5f505000000001600149979398effb98d27f2a431674744b7b0fb7b8d29832078b233678ab92a28a10928d4d77d0ae88e95e0ad8376a038bf0cd15d9a83df05010820a56ab64b41ab2d1a308f50ffafea47760a7541bd5cf85588d4ba86aab11481a70101209e2bcd2e3c390b2fe7f8d6c344acf672e4401695967c6aed7b39506607ea702b010b2039edba0537c7ed142fa55790ffc7c853aa2a986ab056ac80ffcde392d0f1a976010b205c7fadc8aeed3ad4178d0d124e0b97d5f329d9f688d280248681d1d5bf5c9244010e20457ad7c211615cf3a7fe0c27008a1556d8fb6d45cd541501d53e92f7551112dd010b20ae5e8702fa536690f9fd4e70bcaabc385a5297c7c5994bd31ffb83ee8f27f8760102203470462c29d12a422ac91ecf046e5cc83e2ab25ce0539d17aa32d977b00a1910010f20c95b24ab8f9195ab1f062d895224888c9c68c6429b2b848bb3623dc9a77b43ec010c20c6fdde73c41104dbc2dd8631aa64feec982e6d3ac93262c0ade15bb57153aacd01022033ed8ba09e5c16abc7feebf287abaceb4345e78b7a1718cc274f0ec8da85c676010f20c1d263d50ceb63cc9d7170ab5c17b699dcc4e7e7760279635e43cb395ff08dba010220015d503eacf2343d45eb589005a334fab1f8389a6da6ab33193c8fced83e00ac010220cb7aba6c70df6b1ba96f5789f0067f1279b7328fd10f08131c298c5d27964e2d0106202a49c630ddeaf3ed36b8a34fcbd59ccfa310a63db09020ff1c31f35dfb1ae744010a20990a3288bf9b4d25b422b1e4f100e73f1093fe6d4e2c0704ece9c6e516a2e32d010c2036caa9e1d3ef893d50d1847c93088593e1e807382702e7aa28f8272a0e14e853010920bbcb59b152c63611930ddad94710cf224ece31db3044fab21de70835cbfd38ed010c208b73d0f49674093bbbace2fdd3fae16adbb5dd2426baf287399a353e530402a70108202146adfc52944912841028338047782d893aea4fc1f423cc389ede99974e30c3010b20ee1fbc80db22948074311f337cf37d99a4806b79da2401bcade31a3192160ce10105206394f2c7ff90593112b927c43db3c56f83046338cf9664c6af30fb8942881d23010420160247ef998f7b03aeef33894cbf3bd15ce2aafee39ac5b82b7291806c79c9c5010a2045d9a55b6003485c1471e94973f1480cc347a9186656764f26601ff18a2bc8d9010f205def6e2a3d589e84776baa3aaab9f9d377390d6dfc2b8d4de9792b55abd4fa5c0108208ea4c92dc910a70a30a0e492aed6ebd82dbec1ff3c342415145bfe238bb71b2a0020121ebe2242f4065c81d5da5bdf1e99497432e4744d249aaf8fe021baa3edf9b90109202fabafd5d55aa86a0709ff528c6cc9075295ab3a5dd9372c5158019b9076fcbe010d2006efc4bf7857f573b3f3d8a9785156bf4bfdaa02ab0109112f2e493635b19c01010220818c038ccea094d134cf0374fa0270133ba73fcd9a7af0590c2af016ee532d90010120710a5f1d8fdc2dbf5b659233861ab1236d3b5d21e07da88351d24eb616a46eb50108207c3be454059a8443351bf1a6cad574f0711dd7cbec3be83094c16a797cb07d5d010e205a8c4961a07c9934bf35ad3c14222bcfbbac4e3d878d21e041f1e5e5dce03651010d2073e5a4934b1f9ca5c391e3ccfe02082bd30fa9c9ea6c17d90a47831f6951c3f1010820d32e9a0ccd8ae49d380560695c8f553ee45d4eab7e6bd50e4e2d2da02748758b010720e1980797856bfee2619cdc5a6821ee862eab934cee581611b3491cf9fa95aae70105207a3b569c7a4c5efadc2c4c86201b64ff4275126ddedd8e6dca5a6751b9e1104101032080fc2a24fb299142f61b98287c9d5b26395a8a8b2da0248d4f0210a0fe0371a2010d20579d5068314b183b7a9fafbf5c2537da5d1f80dd3088713848466a98a29f531e010a201a8db945a3595a38d3cafb6a9eb29be87bc4626bdd6a629e2580e8eaed5abc3f010520fb7ce66f625dca347d33fb01cd39cf4ff9ea0d698593f28fc724692aa6ba558b010e20ec31e24b3860f16f53d3024769f5090e17438497a7b63fc5575334589881031d010b20f9a435e5d56ac77b4ec1473821f999d928afe8b94596f064dafb3bb10aeb163d0020e1492aafe14e15a2444584e22a9609adb15696a9876aa26dce594230df66c29e01062042d5925da459e28f1e3be15c05b4a0ef749f43fabdbf7ede7f2ce6357e2e67fb010e20298300248af42f3e7b8edeb9212de442cdf84a285b23af93127132baa55e6491010320399995b503688a9dc4754494696cbd98e5a9391433922b0cc9101ec6d55fd164010e204c2c3e6b88ba9e586f48017df811de0380fe5f17ee8583d63640b9773f0181da010d2063a8882961d0279f18d269437b1cf1a81b7c49f55ec87ae26506a6cc7a34e8720104209c2f0b077a4ec76bcfa5a6eba7989c4d96260b42669cf892682942e48a23fb760103203716fa218e803c6bf516a6262e9fe7f298d29711379623aa33d2996eecc91266010520d782fb918ae9a179554158e20cdd2149781d895188603a5b8ec0e1499156fa780108206573811d475d6499119c9bcce7da41f6ab21f88234ed527f826d09d08eac3e4c010c20a95cd9adc7c042ce7562dcea6ef9cf69d630bdfa7fe68182245b98450583f30f01022086dc2ff788098a6732db1843d07e1c09ced76144f249a3bb6122685d13aa2604010720e1a7f00ecb19dc6837cad7509a7d0f914bcb492cc99cba9b5832eafdc58131d7010f20a642bb549bae642a95f40a048681752a3e4a5163899a3661e4048b50a5fe51c7010120aec7a64e921dc7584b93a7d8377a870b353171084f5980839bf02b0dbb8c1c62010b206515f02b531e6364c54d8ae19c9ea3c22e9f19858ecbf8c31a6d75ce00ae7612010e20cb5954027e0df197b3b9328515d2201ee9f7558407d47921c7ce8c1da433530a010120a9fb87650d78160d5161ba4fe491622b0b65dcbbe2825611ff1af5d2f1bc4fa1010420001f59589eca24e28d66f57536afff3126f5d1fba2314aada3415da587e627c800203be60676c0c10c5537082e2e89f517bd6ce62f2fbe39d3c1a238e97142836d6f010b201db96ba40e8a1ff3f8fa65f8c007ad3946753ee0f7066edaf87b3238dd928da3010c40f51efc924d4d910a4e071746e67aba294b9e329fdbd69ef98c2d33201a4a15068ddfa43e6bf98706e7025525243df59ab9c2fbf317c728b265be660e34b67e30fde815766b2079be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798ad766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b766b5f7c947658a2637caaaaaaaa7c5894687654a2637caaaa7c5494687652a2637caa7c52946876637ca87c8c6891696b6c6c7d7c6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b6c7ea87c6c7d937b205a0db13c7f4f07fe9c1ff911f8975debd04029c3435aa9d39e116608ef7a91448802000288007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b007b7658a2635894516700687b7b7654a26354947c0140937c687652a26352947c0120937c68636093687b937c637692638f6775018068686b6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c6c7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e7e6ca88721c150929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac000000000

[-- Attachment #1.3: 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 --]

Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

['conduition' via Bitcoin Development Mailing List]

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

Hi Dustin,

I agree that in a best case scenario, we should
hope for much smaller signatures as the default 

in a post-quantum bitcoin network. Ideally some 

new age cryptography such as lattices allows
this. If every Bitcoin transaction used a large
hash-based signature like Lamport, WOTS, or 

SPHINCS, then L1 TPS would have to drop, or 

blocksize would have to increase, and nobody 

wants that.

But it's good to have options. WOTS not an ideal
one by any means, but it works, and assumes little
compared to lattices.

Maybe useful as an emergency quantum-resistant
escape hatch, in case the network doesn't come
to consensus on  a more compact signature scheme,
or if the novel scheme that we do use turns out
to be insecure.

Best case is that in a few years, someone
invents a scheme with 64 byte signatures which
is quantum resistant, and we add a new opcode or
address format, and everyone migrates to that.
But let's not put all our eggs in one basket.

PS thanks for the link Yuval, I wasn't aware of
that prior work. I believe my construction
improves on Jonas', on two counts:

- My approach requires only CAT, not full GSR. If
  we had more opcodes (namely OP_LSHIFT), my
  script would get even smaller.
- My script results in much smaller witnesses.
  8kb vs 24kb.

However, I didn't attempt to implement WOTS+, only
vanilla WOTS with checksum compression. This was
mostly because of the difficulty of XORing without
access to OP_XOR.

regards,
conduition

On Sunday, June 8th, 2025 at 4:20 PM, Dustin Ray <dustinray117@pm.me> wrote:

> I don't mean to sound crass but i do find it incredibly ironic that the same community that went to war over the block size all of those years ago is now seriously considering dumping kilobytes of possibly *stateful* signature data into the blockchain.
> 

> I am very concerned that allowing that volume of data is going to seriously harm decentralization. Low power and casual devices might struggle to keep up with managing a ledger with such a substantial footprint.
> 

> 

> 

> On Sun, Jun 8, 2025 at 3:59 AM, 'conduition' via Bitcoin Development Mailing List <bitcoindev@googlegroups.com> wrote:
> 

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

-- 
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/PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk%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 --]

Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

[Jonas Nick]

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.

Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

['conduition' via Bitcoin Development Mailing List]

[-- 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 --]

Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

[Anthony Towns]

On Sun, Jun 08, 2025 at 03:20:08AM +0000, 'conduition' via Bitcoin Development Mailing List wrote:
> See a prototype implementation in pseudo-script on
> github here.
> 
> https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182

I think you can do the four-bit pair to eight-bit conversion slightly
better with:

DUP 8 GREATERTHANOREQUAL  # is the high-bit going to be set?
SWAP ROT SWAP  # drop that flag lower in the stack
DUP ADD DUP ADD DUP ADD DUP ADD ADD  # combine them mathematically
SWAP IF  # was the flag set?
  128 SWAP SUB  # subtract from 128 converts 0x8100-0xff00 to 0x81-0xff
  IFDUP NOT IF "0x80" ENDIF  # special case 0x80 "negative zero"
ELSE
  IFDUP NOT IF "0x00" ENDIF  # special case actual 0
ENDIF

Should save about 640 bytes of script (11%, 8% total), I think.

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

inquisition.bitcoin-signet.net was down for a few days when you posted
this, due to running out of disk space, which probably would have made
getting txs relayed pretty hard. You'd probably have more luck now.

Cheers,
aj

-- 
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/aGkYLuZZz2itqVJx%40erisian.com.au.

Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

['conduition' via Bitcoin Development Mailing List]

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

Great idea AJ, I didn't think about OP_DUP OP_ADD as a
stand-in for OP_LSHIFT. That saves a bunch of bytes. We can
save even more by using `OP_SIZE` to check if the combined
number is greater than 127, since the interpreter's OP_ADD
`output` should always be canonically represented as a
2-byte value if `128 <= output <= 255` (correct?).

This lets us elide the SWAP/ROT operations, dropping it to
35 bytes per of script per iteration of that loop (down
from 58 in my first impl!). Total savings across all loops
is 736 bytes, bringing the total script+witness size down
to about 7212 bytes, or 1803 vbytes. Very groovy!

// ... <b63> <b64>
SWAP DUP ADD DUP ADD DUP ADD DUP ADD ADD
SIZE <2> EQUAL IF
  <128> SWAP SUB
  IFDUP NOT IF <0x80> ENDIF
ELSE
  DUP NOT IF <0x00> ENDIF
ENDIF

I revised the gist with the updated bitshift code, and more
detailed comments. Thank you!

https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182#file-winternitz-ts-L100-L137

regards,
conduition



On Saturday, July 5th, 2025 at 6:54 AM, Anthony Towns <aj@erisian.com.au> wrote:

> On Sun, Jun 08, 2025 at 03:20:08AM +0000, 'conduition' via Bitcoin Development Mailing List wrote:
> 

> > See a prototype implementation in pseudo-script on
> > github here.
> > 

> > https://gist.github.com/conduition/c6fd78e90c21f669fad7e3b5fe113182
> 

> 

> I think you can do the four-bit pair to eight-bit conversion slightly
> better with:
> 

> DUP 8 GREATERTHANOREQUAL # is the high-bit going to be set?
> SWAP ROT SWAP # drop that flag lower in the stack
> DUP ADD DUP ADD DUP ADD DUP ADD ADD # combine them mathematically
> SWAP IF # was the flag set?
> 128 SWAP SUB # subtract from 128 converts 0x8100-0xff00 to 0x81-0xff
> IFDUP NOT IF "0x80" ENDIF # special case 0x80 "negative zero"
> ELSE
> IFDUP NOT IF "0x00" ENDIF # special case actual 0
> ENDIF
> 

> Should save about 640 bytes of script (11%, 8% total), I think.
> 

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

> 

> inquisition.bitcoin-signet.net was down for a few days when you posted
> this, due to running out of disk space, which probably would have made
> getting txs relayed pretty hard. You'd probably have more luck now.
> 

> Cheers,
> aj
> 

> --
> 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/aGkYLuZZz2itqVJx%40erisian.com.au.

-- 
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/h9N4uIp0MgaASuEBpqsHjiQb9ahGbca3mG5V6iPVumT9ICT4monwV1ScgV3kdV2ka9CkQiSqEGkxA_eqqGQJ1TtFmWUlJEhi0McZU6yGBl0%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 --]