Re: [bitcoindev] OP_CAT Enables Winternitz Signatures

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

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