From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future
Date: Mon, 8 Dec 2025 21:08:03 -0800 (PST) [thread overview]
Message-ID: <0e2402c5-d593-49ff-b002-5ab348b46964n@googlegroups.com> (raw)
In-Reply-To: <CAAS2fgSrGz1-ShUfhx_-jZm_W__ZBquMLbVGQriCYS6khfV46Q@mail.gmail.com>
[-- Attachment #1.1: Type: text/plain, Size: 11438 bytes --]
Great work Jonas and Mikhail, glad to see more eyes and ears surveying
these schemes and their potential. Also shameless plug for some of my prior
work <https://conduition.io/code/fast-slh-dsa/> on related topics
<https://conduition.io/cryptography/quantum-hbs/>.
The post-quantum HD wallet derivation problem is one i've been thinking
about a lot lately. Due to the lack of algebraic structure in SLH-DSA it's
gonna be impossible to fully emulate BIP32 with that scheme alone. I'm
personally hoping that we'll find a way to derive child pubkeys using
lattices (ML-DSA) and/or isogenies (SQIsign), but I haven't heard of any
solid proposals yet. Currently reading on isogeny crypto as that sounds
like a promising candidate.
If such a thing is possible, then we could derive BIP360 tap trees
containing a static SLH-DSA pubkey, alongside dynamically derived keys for
a more structured algebraic PQ scheme like ML-DSA, and finally a regular EC
BIP340 pubkey derived by regular BIP32. The idea being one could distribute
a 'post quantum xpub' containing a regular BIP32 key extended with PQ
public keys. Wallets or 3rd parties could derive child addresses which
contain tap trees with one leaf per signing scheme. Since SLH-DSA doesn't
support unhardened derivation, the SLH-DSA public key would have to be used
as-is in every child leaf, without any derivation (maybe with an extra
pseudorandom nonce thrown in to avoid reusing the same tap leaf hash in
different TXs). Think of defining: CDKPub_slh(spx_pubkey, chaincode, n) :=
(spx_pubkey, HMAC(chaincode, n))
Regarding smaller signatures: I used to be a big fan of SPHINCS+C and
SPHINCS-α <https://sphincs-alpha.github.io/>. I asked Andreas Hulsing, the
SPHINCS+ team lead, why weren't these obviously better schemes standardized
instead? he said NIST shied away from them because they complicated the
implementation for little material benefit. There were also "political"
considerations, owing to the fact that they were proposed late in the
standardization competition's timeline. Obviously bitcoin is a different
ballgame entirely, but the point is we should optimize where it matters
most. IMO that means smaller parameter set(s). Even without PoW
compression, hybercubes <https://eprint.iacr.org/2025/889>, or other modern
tricks to optimize SLH-DSA, we can make sigs *much* smaller by just
tweaking constants, and we can do so *without* losing compatibility with
the NIST-compliant algorithm. So that idea has a big +1 from me. NIST is in
the process of standardizing smaller parameter sets
<https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/vtMTuE_3u-0> but
they have much higher signing/keygen perf overhead. If we want smaller
hash-based sigs, we should pick new parameter sets to standardize in
Bitcoin, covering different use cases, and use them with the standardized
FIPS-205 algorithm. Agreeing on *which* parameter sets will be hard though.
See https://github.com/chrisfenner/slh-dsa-rls
I agree with Greg about the verification cost, you can't just consider
cycles/byte, you have to consider the cost of verifying entire blocks full
of these signatures. While my recent research showed that SLH-DSA signing
and keygen can be very effectively parallelized, verification is much
harder to parallelize. You have to parallelize generically across
signatures in a block (which can also be done with ECC, or any sig-verify
algo for that matter).
On statefulness: I once felt quite strongly that we should have stateful
WOTS on-chain as an opcode - WOTS is pretty much the smallest hash-based
signatures you can get. But talking with Ethan and Hunter has since
convinced me that stateless sigs are the only way to go. There's just too
many landmines and footguns to step on with schemes like WOTS, or even its
big daddy XMSS, if you use them to sign non-deterministic data statefully.
Finally, while everyone (including me) is really excited about hash-based
signatures because we know and love and trust hash functions, in reality
the performance, functionality, and sig-size tradeoffs will lead to 99% of
people using schemes with new assumptions like ML-DSA for everyday usage.
Hash based sigs will be the worst-case scenario fallback, in case the more
efficient schemes like ML-DSA or SQIsign turn out to be cryptographically
broken (a real possibility, the feds have standardized broken schemes
before after all).
> I don't think it matters much if signing is slow on low power devices --
e.g. taking seconds per input.
It's far worse than that. Here are some benchmarks run by Trezor on their
Model T signing device
<https://gist.github.com/onvej-sl/3851bdae7ae5aa1f2624ca769737ea2e>. 75
seconds to create one SLH-DSA-SHA2-128s signature. RAM requirements are
quite low for SLH-DSA compared to ML-DSA which is nice. Apparently some of
their newer devices have dedicated chips which can execute SHA256 much
faster than the ARM M4, but i haven't seen any benchmarks on those yet. I
think those kinds of hash accelerators, or FPGAs etc, will need to become
standard for hardware wallets if they plan to use SLH-DSA signing (or
keygen). I don't know about ledger, because they apparently don't think
quantum is a serious risk :/
regards,
conduition
On Monday, December 8, 2025 at 4:58:18 PM UTC-5 Greg Maxwell wrote:
> On Mon, Dec 8, 2025 at 8:47 PM 'Mikhail Kudinov' via Bitcoin Development
> Mailing List <bitco...@googlegroups.com> wrote:
>
>> We should not forget that for Bitcoin, it is important that the size of
>> the public key plus the size of the signature remains small. Hash-based
>> schemes have one of the smallest sizes of public keys, which can be around
>> 256 bits. For comparison, ML-DSA pk+sig size is at least 3732 bytes.
>>
>
> No scheme has such a limitation, because any scheme can use a hash of the
> underlying primitive as the public key-- which Bitcoin has done since day
> one. The correct figure of merit is the the size of the signature, pubkey,
> and a hash combined or-- if the pubkey is under 500 bits or so, just the
> size of the signature plus pubkey.
>
>>
>> Verification cost per byte is comparable to current Schnorr signatures,
>> alleviating concerns about blockchain validation overhead.
>>
>
> Though hash based signatures don't really concern me much in validation
> costs, I disagree with the premise of this statement. If the size was
> similar then I'd agree that cost per byte being similar was enough to make
> validation costs not a concern, but the size is some 40 times larger and
> 40x validation costs is certainly a concern unless the scheme is deployed
> without an effective increase in block capacity-- and without a capacity
> increase the utility of such large signatures is potentially pretty
> dubious. Even if a proposal doesn't itself include a capacity increase
> one should be regarded as inevitable along with it, particularly because
> just securing *your* coins against this attack won't do you any good if 95%
> of all other coins get stolen by it-- so a performance analysis should
> anticipate needing the capacity for all of the transaction flow to use the
> scheme, even if that isn't the case for the initial usage.
>
> One of the key design decisions for Bitcoin is whether to rely exclusively
>> on stateless schemes (where the secret key need not be updated for each
>> signature) or whether stateful schemes could be viable. Stateful schemes
>> introduce operational complexity in key management but can offer better
>> performance.
>>
>
> It's not an either/or, I believe. I think schemes with weakened stateless
> security could be improved to ~full repeated use security via statefulness
> (e.g. grinding the message to avoid revealing signatures that leak key
> material). There may be possibilities for other hybrids: an otherwise
> stateless wallet which is assumed to have visibility to its own confirmed
> transactions. It may be that a 'few time secure' scheme could be adequate
> when coupled with best effort statefulness (e.g. blockchain visibility)
> and a series composed schnorr signature (which means the brittleness of the
> hash signature only matters if the schnorr signature is broken).
>
> Statefulness is not a great assumption with how bitcoin private keys work,
> particularly for cold storage. Especially since key loss is usually the
> greatest risk to coin possession and the best mechanism against key loss is
> duplicate copies separately stored. Although correct usage of bitcoin
> results in keys being single use or nearly so, it's a security footgun to
> make a strong assumption.
>
> If we look at multi/distributed/threshold-signatures, we find that current
>> approaches either don't give much gains compared to plain usage of multiple
>> signatures, or require a trusted dealer, which drastically limits the
>> use-cases.
>>
>
> There may be advantages there to using a threshold schnorr in series with
> a single PQ scheme, in that case the security model is "a threshold of
> participants must agree OR a participant must agree and have a successful
> attack on the threshold schnorr signature". This may well be a reasonable
> compromise considering the costs of multiple PQ keys-- particularly when
> the participants are known entities and not e.g. an anonymous channel
> counterparty.
>
> 1) What are the concrete performance requirements across various hardware,
>> including low-power devices?
>>
>
> I don't think it matters much if signing is slow on low power devices --
> e.g. taking seconds per input. It would obviously matter to *some* users
> but those users could use higher power signing devices. The minimum amount
> of dynamic ram needed for signing (even at low performance) is probably
> pretty important.
>
> 2) Should multiple schemes with different signature limits be standardized?
>> 3) Is there value in supporting stateful schemes alongside stateless ones?
>
>
> Depends on their relative costs. Plain stateful (of the 'two signatures
> breaks your security' sort) is a very concerning footgun with bad side
> effects (e.g. can't even bump fees) but even that could be attractive if
> the size is much smaller. Having a totally free configuration is quite
> bad for privacy, however, and of dubious value. I think that just having
> two options, e.g. secure for 'few' and secure for 'many' (but no need for
> 2^128) with both supporting but not requiring statefulness as a best effort
> hail-mary protection against self-compromise might be interesting, but it
> would depend on their relative performance. One possibility would be to
> just always have both alternatives available (at a cost of 32 bytes) and
> for the user to decide at signing time.
>
>
>
>
>
--
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/0e2402c5-d593-49ff-b002-5ab348b46964n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 13749 bytes --]
next prev parent reply other threads:[~2025-12-09 6:49 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-12-08 20:28 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-08 21:50 ` Greg Maxwell
2025-12-09 5:08 ` 'conduition' via Bitcoin Development Mailing List [this message]
2025-12-10 0:41 ` Olaoluwa Osuntokun
2025-12-09 8:06 ` [bitcoindev] " Boris Nagaev
2025-12-09 22:48 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-09 23:06 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-10 0:01 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-10 0:14 ` 'conduition' via Bitcoin Development Mailing List
2025-12-10 15:55 ` Jonas Nick
2025-12-10 0:53 ` Olaoluwa Osuntokun
2025-12-16 7:25 ` Jonas Nick
2026-01-19 1:12 ` 'conduition' via Bitcoin Development Mailing List
2025-12-18 18:45 ` Erik Aronesty
2025-12-19 8:36 ` Jonas Nick
2025-12-20 1:14 ` Erik Aronesty
2025-12-24 15:02 ` david torrealba
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=0e2402c5-d593-49ff-b002-5ab348b46964n@googlegroups.com \
--to=bitcoindev@googlegroups.com \
--cc=conduition@proton.me \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
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