From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Dustin Ray <dustinray117@pm•me>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] OP_CAT Enables Winternitz Signatures
Date: Mon, 09 Jun 2025 15:31:47 +0000 [thread overview]
Message-ID: <PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk=@proton.me> (raw)
In-Reply-To: <QcOCx8vBMDuw4xf05H5SbIOPee2MZqV5IQa2opvAXcMeMzzFooHYL97qy5ZCLUEjqXHlHoyAucpmkwwU2i3bhO95SJrWP-oRU6mqamnTvRc=@pm.me>
[-- 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 --]
prev parent reply other threads:[~2025-06-09 15:46 UTC|newest]
Thread overview: 2+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-06-08 3:20 'conduition' via Bitcoin Development Mailing List
[not found] ` <QcOCx8vBMDuw4xf05H5SbIOPee2MZqV5IQa2opvAXcMeMzzFooHYL97qy5ZCLUEjqXHlHoyAucpmkwwU2i3bhO95SJrWP-oRU6mqamnTvRc=@pm.me>
2025-06-09 15:31 ` 'conduition' via Bitcoin Development Mailing List [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='PEvUekkEdjFXIGBrX3GTMxPkeD6Bn6q_UnsVGUSWmjdWfiRJzOXxg6oSoLQBju65BVwoKYaA3YwwhzvTlUvM1MXcWO_K5-ub9_lBkoC28Nk=@proton.me' \
--to=bitcoindev@googlegroups.com \
--cc=conduition@proton$(echo .)me \
--cc=dustinray117@pm$(echo .)me \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox