From: Greg Maxwell <gmaxwell@gmail.com>
To: Mikhail Kudinov <mkudinov@blockstream.com>
Cc: 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:50:31 +0000 [thread overview]
Message-ID: <CAAS2fgSrGz1-ShUfhx_-jZm_W__ZBquMLbVGQriCYS6khfV46Q@mail.gmail.com> (raw)
In-Reply-To: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com>
[-- Attachment #1: Type: text/plain, Size: 5742 bytes --]
On Mon, Dec 8, 2025 at 8:47 PM 'Mikhail Kudinov' via Bitcoin Development
Mailing List <bitcoindev@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/CAAS2fgSrGz1-ShUfhx_-jZm_W__ZBquMLbVGQriCYS6khfV46Q%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 7250 bytes --]
next prev parent reply other threads:[~2025-12-08 21:58 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 [this message]
2025-12-09 5:08 ` 'conduition' via Bitcoin Development Mailing List
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=CAAS2fgSrGz1-ShUfhx_-jZm_W__ZBquMLbVGQriCYS6khfV46Q@mail.gmail.com \
--to=gmaxwell@gmail.com \
--cc=bitcoindev@googlegroups.com \
--cc=mkudinov@blockstream.com \
/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