* [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future
@ 2025-12-08 20:28 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-08 21:50 ` Greg Maxwell
` (2 more replies)
0 siblings, 3 replies; 17+ messages in thread
From: 'Mikhail Kudinov' via Bitcoin Development Mailing List @ 2025-12-08 20:28 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 4220 bytes --]
Hi everyone,
We'd like to share our analysis of post-quantum options for Bitcoin,
focusing specifically on hash-based schemes. The Bitcoin community has
already discussed SPHINCS+ adoption in previous mailing list threads. We
also looked at this option. A detailed technical report exploring these
schemes, parameter selections, security analysis, and implementation
considerations is available at https://eprint.iacr.org/2025/2203.pdf. This
report can also serve as a gentle introduction into hash-based schemes,
covering the recent optimization techniques. The scripts that support this
report are available at
https://github.com/BlockstreamResearch/SPHINCS-Parameters .
Below, we give a quick summary of our findings.
We find hash-based signatures to be a compelling post-quantum solution for
several reasons. They rely solely on the security of hash functions
(Bitcoin already depends on the collision resistance of SHA-256) and are
conceptually simple. Moreover, these schemes have undergone extensive
cryptanalysis during the NIST post-quantum standardization process, adding
confidence in their robustness.
One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
signatures are almost 8KB. An important observation is that SPHINCS+ is
designed to support up to 2^64 signatures. We argue that this bound can be
set lower for Bitcoin use-cases. Moreover, there are several different
optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
scheme, that can reduce the signature size even more.
For example, with these optimizations and a bound on 2^40 signatures we can
get signatures of size 4036 bytes. For 2^30 signatures, we can achieve 3440
bytes, and for 2^20, one can get 3128 bytes, while keeping the signing time
reasonable.
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.
Verification cost per byte is comparable to current Schnorr signatures,
alleviating concerns about blockchain validation overhead.
As for security targets, we argue that NIST Level 1 (128-bit security)
provides sufficient protection. Quantum attacks require not just O(2^64)
operations but approximately 2^78 Toffoli depth operations in practice,
with limited parallelization benefits.
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.
We explored the possibilities of using hash-based schemes with Hierarchical
Deterministic Wallets. The public child key derivation does not seem to be
efficiently achievable. The hardened derivation is naturally possible for
hash-based schemes.
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.
We welcome community feedback on this approach and hope to contribute to
the broader discourse on ensuring Bitcoin's long-term security in the
post-quantum era. In particular, we are interested in your thoughts on the
following questions:
1) What are the concrete performance requirements across various hardware,
including low-power devices?
2) Should multiple schemes with different signature limits be standardized?
3) Is there value in supporting stateful schemes alongside stateless ones?
Best regards,
Mikhail Kudinov and Jonas Nick
Blockstream Research
--
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/3e815d03-5e21-41ed-ba1a-4f9b2120a986n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 4585 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-08 20:28 [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future '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
2025-12-09 8:06 ` [bitcoindev] " Boris Nagaev
2025-12-18 18:45 ` Erik Aronesty
2 siblings, 1 reply; 17+ messages in thread
From: Greg Maxwell @ 2025-12-08 21:50 UTC (permalink / raw)
To: Mikhail Kudinov; +Cc: Bitcoin Development Mailing List
[-- 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 --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-08 21:50 ` Greg Maxwell
@ 2025-12-09 5:08 ` 'conduition' via Bitcoin Development Mailing List
2025-12-10 0:41 ` Olaoluwa Osuntokun
0 siblings, 1 reply; 17+ messages in thread
From: 'conduition' via Bitcoin Development Mailing List @ 2025-12-09 5:08 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- 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 --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-08 20:28 [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-08 21:50 ` Greg Maxwell
@ 2025-12-09 8:06 ` Boris Nagaev
2025-12-09 22:48 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-16 7:25 ` Jonas Nick
2025-12-18 18:45 ` Erik Aronesty
2 siblings, 2 replies; 17+ messages in thread
From: Boris Nagaev @ 2025-12-09 8:06 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 6467 bytes --]
Hi Mikhail, Jonas and all!
> 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.
I think there's room to explore N/N Multiparty computation (MPC) for
hash-based signatures. In principle you can secret-share the seed and run
MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,
so the chain sees a single normal hash-based signature while it is a result
of cosigning by all N parties. The output stays a single standard-size
signature (e.g., a 2-of-2 compressed to one sig), so you save roughly by N
times versus N separate signatures, but the cost is a heavy MPC protocol to
derive the pubkey and to produce each signature. There's no linearity to
leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it
could be interesting to quantify the overhead versus just collecting N
independent signatures.
As a small reference point, here's a two-party SHA-256 MPC demo I recently
wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):
https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol moves
about 700 KB of messages and completes in three rounds while privately
computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party
restriction, quantum-vulnerable OT, and semi-honest model could all be
upgraded, but it shows the shape of the protocol.
With a malicious-secure upgrade and PQ OT, sha2pc would already be enough
for plain Lamport signatures by repeating it 256x2 times. For WOTS-like
signatures you'd need another circuit, but the same repo has tooling for
arbitrary circuits, and WOTS is just a hash chain, so it is doable; circuit
and message sizes should grow linearly with the WOTS chain depth.
Curious to hear thoughts on whether N/N MPC with hash-based sigs is worth
prototyping, and what overhead targets would make it compelling versus
plain multisig.
Best,
Boris
On Monday, December 8, 2025 at 5:47:49 PM UTC-3 Mikhail Kudinov wrote:
Hi everyone,
We'd like to share our analysis of post-quantum options for Bitcoin,
focusing specifically on hash-based schemes. The Bitcoin community has
already discussed SPHINCS+ adoption in previous mailing list threads. We
also looked at this option. A detailed technical report exploring these
schemes, parameter selections, security analysis, and implementation
considerations is available at https://eprint.iacr.org/2025/2203.pdf. This
report can also serve as a gentle introduction into hash-based schemes,
covering the recent optimization techniques. The scripts that support this
report are available at
https://github.com/BlockstreamResearch/SPHINCS-Parameters .
Below, we give a quick summary of our findings.
We find hash-based signatures to be a compelling post-quantum solution for
several reasons. They rely solely on the security of hash functions
(Bitcoin already depends on the collision resistance of SHA-256) and are
conceptually simple. Moreover, these schemes have undergone extensive
cryptanalysis during the NIST post-quantum standardization process, adding
confidence in their robustness.
One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
signatures are almost 8KB. An important observation is that SPHINCS+ is
designed to support up to 2^64 signatures. We argue that this bound can be
set lower for Bitcoin use-cases. Moreover, there are several different
optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
scheme, that can reduce the signature size even more.
For example, with these optimizations and a bound on 2^40 signatures we can
get signatures of size 4036 bytes. For 2^30 signatures, we can achieve 3440
bytes, and for 2^20, one can get 3128 bytes, while keeping the signing time
reasonable.
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.
Verification cost per byte is comparable to current Schnorr signatures,
alleviating concerns about blockchain validation overhead.
As for security targets, we argue that NIST Level 1 (128-bit security)
provides sufficient protection. Quantum attacks require not just O(2^64)
operations but approximately 2^78 Toffoli depth operations in practice,
with limited parallelization benefits.
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.
We explored the possibilities of using hash-based schemes with Hierarchical
Deterministic Wallets. The public child key derivation does not seem to be
efficiently achievable. The hardened derivation is naturally possible for
hash-based schemes.
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.
We welcome community feedback on this approach and hope to contribute to
the broader discourse on ensuring Bitcoin's long-term security in the
post-quantum era. In particular, we are interested in your thoughts on the
following questions:
1) What are the concrete performance requirements across various hardware,
including low-power devices?
2) Should multiple schemes with different signature limits be standardized?
3) Is there value in supporting stateful schemes alongside stateless ones?
Best regards,
Mikhail Kudinov and Jonas Nick
Blockstream Research
--
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/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 7215 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
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-16 7:25 ` Jonas Nick
1 sibling, 1 reply; 17+ messages in thread
From: 'Mikhail Kudinov' via Bitcoin Development Mailing List @ 2025-12-09 22:48 UTC (permalink / raw)
To: Boris Nagaev; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 9299 bytes --]
Dear Greg,
Thank you for your feedback, your points are important, and I appreciate
the opportunity to continue the discussion and clarify a few aspects of
your response.
On public-key and signature sizes:
My main point was that when we compare with other pq alternatives (such as
Lattice-based schemes) we should take their public key sizes into account.
For ML-DSA the public key is more than 1kB.
On verification costs:
I agree that it is important to consider how the verification cost scales
with block size. At the same time, I believe it is still important to
highlight the ratio between signature size and verification cost. For
certain parameter sets, this ratio is significantly more favorable than for
Schnorr signatures. For some parameter sets it can be more than 10 times
better: if we look at the parameters sets in the Table 1, we can achieve
4480 bytes signatures (under the 2^40 signatures limit) with verification
ratio being almost 9 times better. I would welcome further feedback here.
Specifically, would it be reasonable to choose larger signatures if they
offer lower verification costs?
On stateful vs. stateless security:
Regarding your comment, “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),” I did not fully grasp your argument. Could you please elaborate?
On combining threshold Schnorr with a PQ scheme:
You mentioned that “there may be advantages to using a threshold Schnorr in
series with a single PQ scheme.” My current thinking is that such
constructions could already be implemented at the scripting layer; in that
sense, users could assemble them without additional opcodes (beyond the PQ
signature opcode itself). While I see the potential benefits, I am also
worried that such an approach risks introducing loosely-defined security
models, which can lead to vulnerabilities.
Best,
Mike
Вт, 9 дек. 2025 г. в 19:20, Boris Nagaev <bnagaev@gmail.com>:
> Hi Mikhail, Jonas and all!
>
> > 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.
>
> I think there's room to explore N/N Multiparty computation (MPC) for
> hash-based signatures. In principle you can secret-share the seed and run
> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,
> so the chain sees a single normal hash-based signature while it is a result
> of cosigning by all N parties. The output stays a single standard-size
> signature (e.g., a 2-of-2 compressed to one sig), so you save roughly by N
> times versus N separate signatures, but the cost is a heavy MPC protocol to
> derive the pubkey and to produce each signature. There's no linearity to
> leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it
> could be interesting to quantify the overhead versus just collecting N
> independent signatures.
>
> As a small reference point, here's a two-party SHA-256 MPC demo I recently
> wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):
> https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol
> moves about 700 KB of messages and completes in three rounds while
> privately computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party
> restriction, quantum-vulnerable OT, and semi-honest model could all be
> upgraded, but it shows the shape of the protocol.
>
> With a malicious-secure upgrade and PQ OT, sha2pc would already be enough
> for plain Lamport signatures by repeating it 256x2 times. For WOTS-like
> signatures you'd need another circuit, but the same repo has tooling for
> arbitrary circuits, and WOTS is just a hash chain, so it is doable; circuit
> and message sizes should grow linearly with the WOTS chain depth.
>
> Curious to hear thoughts on whether N/N MPC with hash-based sigs is worth
> prototyping, and what overhead targets would make it compelling versus
> plain multisig.
>
> Best,
> Boris
>
> On Monday, December 8, 2025 at 5:47:49 PM UTC-3 Mikhail Kudinov wrote:
>
> Hi everyone,
>
> We'd like to share our analysis of post-quantum options for Bitcoin,
> focusing specifically on hash-based schemes. The Bitcoin community has
> already discussed SPHINCS+ adoption in previous mailing list threads. We
> also looked at this option. A detailed technical report exploring these
> schemes, parameter selections, security analysis, and implementation
> considerations is available at https://eprint.iacr.org/2025/2203.pdf.
> This report can also serve as a gentle introduction into hash-based
> schemes, covering the recent optimization techniques. The scripts that
> support this report are available at
> https://github.com/BlockstreamResearch/SPHINCS-Parameters .
> Below, we give a quick summary of our findings.
>
> We find hash-based signatures to be a compelling post-quantum solution for
> several reasons. They rely solely on the security of hash functions
> (Bitcoin already depends on the collision resistance of SHA-256) and are
> conceptually simple. Moreover, these schemes have undergone extensive
> cryptanalysis during the NIST post-quantum standardization process, adding
> confidence in their robustness.
>
> One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
> signatures are almost 8KB. An important observation is that SPHINCS+ is
> designed to support up to 2^64 signatures. We argue that this bound can be
> set lower for Bitcoin use-cases. Moreover, there are several different
> optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
> scheme, that can reduce the signature size even more.
> For example, with these optimizations and a bound on 2^40 signatures we
> can get signatures of size 4036 bytes. For 2^30 signatures, we can achieve
> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing
> time reasonable.
>
> 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.
>
> Verification cost per byte is comparable to current Schnorr signatures,
> alleviating concerns about blockchain validation overhead.
>
> As for security targets, we argue that NIST Level 1 (128-bit security)
> provides sufficient protection. Quantum attacks require not just O(2^64)
> operations but approximately 2^78 Toffoli depth operations in practice,
> with limited parallelization benefits.
>
> 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.
>
> We explored the possibilities of using hash-based schemes with
> Hierarchical Deterministic Wallets. The public child key derivation does
> not seem to be efficiently achievable. The hardened derivation is naturally
> possible for hash-based schemes.
>
> 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.
>
> We welcome community feedback on this approach and hope to contribute to
> the broader discourse on ensuring Bitcoin's long-term security in the
> post-quantum era. In particular, we are interested in your thoughts on the
> following questions:
> 1) What are the concrete performance requirements across various hardware,
> including low-power devices?
> 2) Should multiple schemes with different signature limits be standardized?
> 3) Is there value in supporting stateful schemes alongside stateless ones?
>
> Best regards,
> Mikhail Kudinov and Jonas Nick
> Blockstream Research
>
> --
> 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/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com
> <https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
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/CAPcK4uQBvfWpNsOdOwW%2B%2BL_LgUxFH-9CvY7YFKb1b5OzJgJ_1A%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 10511 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
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
` (2 more replies)
0 siblings, 3 replies; 17+ messages in thread
From: 'Mikhail Kudinov' via Bitcoin Development Mailing List @ 2025-12-09 23:06 UTC (permalink / raw)
To: Boris Nagaev; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 10563 bytes --]
Dear Conduition,
You did a really nice job, I was wondering if it will be hard to add the
different modifications to your implementations?
As for lattice-based schemes and other assumptions, we also thought about
investigations the possibilities there.
With this derivation technique you propose, am I understanding correctly
that if the user signs with the hash-based scheme, then the user would
reveal that the different pub keys are linked?
I think it is true, that limiting the number of signatures is the main
optimisation we should look at. But if we use different parameters sets
don’t we already loose the compatiability with the standardized schemes?
And if we already deviate from the standards, why don’t add the
modifications that can save us extra couple of hundred bytes. From the
implementation complexity, of course this is subjective, but I think these
modifications are pretty straight forward.
Best,
Mike
Ср, 10 дек. 2025 г. в 09:48, Mikhail Kudinov <mkudinov@blockstream.com>:
> Dear Greg,
>
> Thank you for your feedback, your points are important, and I appreciate
> the opportunity to continue the discussion and clarify a few aspects of
> your response.
>
>
> On public-key and signature sizes:
>
> My main point was that when we compare with other pq alternatives (such as
> Lattice-based schemes) we should take their public key sizes into account.
> For ML-DSA the public key is more than 1kB.
>
>
> On verification costs:
>
> I agree that it is important to consider how the verification cost scales
> with block size. At the same time, I believe it is still important to
> highlight the ratio between signature size and verification cost. For
> certain parameter sets, this ratio is significantly more favorable than for
> Schnorr signatures. For some parameter sets it can be more than 10 times
> better: if we look at the parameters sets in the Table 1, we can achieve
> 4480 bytes signatures (under the 2^40 signatures limit) with verification
> ratio being almost 9 times better. I would welcome further feedback here.
> Specifically, would it be reasonable to choose larger signatures if they
> offer lower verification costs?
>
>
> On stateful vs. stateless security:
>
> Regarding your comment, “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),” I did not fully grasp your argument. Could you please elaborate?
>
>
> On combining threshold Schnorr with a PQ scheme:
>
> You mentioned that “there may be advantages to using a threshold Schnorr
> in series with a single PQ scheme.” My current thinking is that such
> constructions could already be implemented at the scripting layer; in that
> sense, users could assemble them without additional opcodes (beyond the PQ
> signature opcode itself). While I see the potential benefits, I am also
> worried that such an approach risks introducing loosely-defined security
> models, which can lead to vulnerabilities.
>
>
> Best,
>
> Mike
>
>
> Вт, 9 дек. 2025 г. в 19:20, Boris Nagaev <bnagaev@gmail.com>:
>
>> Hi Mikhail, Jonas and all!
>>
>> > 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.
>>
>> I think there's room to explore N/N Multiparty computation (MPC) for
>> hash-based signatures. In principle you can secret-share the seed and run
>> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,
>> so the chain sees a single normal hash-based signature while it is a result
>> of cosigning by all N parties. The output stays a single standard-size
>> signature (e.g., a 2-of-2 compressed to one sig), so you save roughly by N
>> times versus N separate signatures, but the cost is a heavy MPC protocol to
>> derive the pubkey and to produce each signature. There's no linearity to
>> leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it
>> could be interesting to quantify the overhead versus just collecting N
>> independent signatures.
>>
>> As a small reference point, here's a two-party SHA-256 MPC demo I
>> recently wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):
>> https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol
>> moves about 700 KB of messages and completes in three rounds while
>> privately computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party
>> restriction, quantum-vulnerable OT, and semi-honest model could all be
>> upgraded, but it shows the shape of the protocol.
>>
>> With a malicious-secure upgrade and PQ OT, sha2pc would already be enough
>> for plain Lamport signatures by repeating it 256x2 times. For WOTS-like
>> signatures you'd need another circuit, but the same repo has tooling for
>> arbitrary circuits, and WOTS is just a hash chain, so it is doable; circuit
>> and message sizes should grow linearly with the WOTS chain depth.
>>
>> Curious to hear thoughts on whether N/N MPC with hash-based sigs is worth
>> prototyping, and what overhead targets would make it compelling versus
>> plain multisig.
>>
>> Best,
>> Boris
>>
>> On Monday, December 8, 2025 at 5:47:49 PM UTC-3 Mikhail Kudinov wrote:
>>
>> Hi everyone,
>>
>> We'd like to share our analysis of post-quantum options for Bitcoin,
>> focusing specifically on hash-based schemes. The Bitcoin community has
>> already discussed SPHINCS+ adoption in previous mailing list threads. We
>> also looked at this option. A detailed technical report exploring these
>> schemes, parameter selections, security analysis, and implementation
>> considerations is available at https://eprint.iacr.org/2025/2203.pdf.
>> This report can also serve as a gentle introduction into hash-based
>> schemes, covering the recent optimization techniques. The scripts that
>> support this report are available at
>> https://github.com/BlockstreamResearch/SPHINCS-Parameters .
>> Below, we give a quick summary of our findings.
>>
>> We find hash-based signatures to be a compelling post-quantum solution
>> for several reasons. They rely solely on the security of hash functions
>> (Bitcoin already depends on the collision resistance of SHA-256) and are
>> conceptually simple. Moreover, these schemes have undergone extensive
>> cryptanalysis during the NIST post-quantum standardization process, adding
>> confidence in their robustness.
>>
>> One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
>> signatures are almost 8KB. An important observation is that SPHINCS+ is
>> designed to support up to 2^64 signatures. We argue that this bound can be
>> set lower for Bitcoin use-cases. Moreover, there are several different
>> optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
>> scheme, that can reduce the signature size even more.
>> For example, with these optimizations and a bound on 2^40 signatures we
>> can get signatures of size 4036 bytes. For 2^30 signatures, we can achieve
>> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing
>> time reasonable.
>>
>> 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.
>>
>> Verification cost per byte is comparable to current Schnorr signatures,
>> alleviating concerns about blockchain validation overhead.
>>
>> As for security targets, we argue that NIST Level 1 (128-bit security)
>> provides sufficient protection. Quantum attacks require not just O(2^64)
>> operations but approximately 2^78 Toffoli depth operations in practice,
>> with limited parallelization benefits.
>>
>> 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.
>>
>> We explored the possibilities of using hash-based schemes with
>> Hierarchical Deterministic Wallets. The public child key derivation does
>> not seem to be efficiently achievable. The hardened derivation is naturally
>> possible for hash-based schemes.
>>
>> 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.
>>
>> We welcome community feedback on this approach and hope to contribute to
>> the broader discourse on ensuring Bitcoin's long-term security in the
>> post-quantum era. In particular, we are interested in your thoughts on the
>> following questions:
>> 1) What are the concrete performance requirements across various
>> hardware, including low-power devices?
>> 2) Should multiple schemes with different signature limits be
>> standardized?
>> 3) Is there value in supporting stateful schemes alongside stateless ones?
>>
>> Best regards,
>> Mikhail Kudinov and Jonas Nick
>> Blockstream Research
>>
>> --
>> 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/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com
>> <https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com?utm_medium=email&utm_source=footer>
>> .
>>
>
--
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/CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t6hsd96PfMOYcA%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 12304 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
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 0:53 ` Olaoluwa Osuntokun
2 siblings, 0 replies; 17+ messages in thread
From: 'Mikhail Kudinov' via Bitcoin Development Mailing List @ 2025-12-10 0:01 UTC (permalink / raw)
To: Boris Nagaev; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 11555 bytes --]
Dear Boris,
We also explored general MPC approaches. We discuss this in Section 15.3,
and it appears they are not suitable. We cite an estimate indicating that
generating a SPHINCS+ signature via a general MPC would take around 85
minutes. Even if we scale down from SPHINCS+ to a much smaller number of
signatures, the approach still does not seem efficient enough. For a single
WOTS instance it might be feasible, but then the question becomes whether
adopting a simple WOTS scheme is desirable at all. As mentioned above,
stateful schemes already introduce significant complexity, and one-time
signatures are even more restrictive.
Best,
Mike
Ср, 10 дек. 2025 г. в 10:06, Mikhail Kudinov <mkudinov@blockstream.com>:
> Dear Conduition,
>
> You did a really nice job, I was wondering if it will be hard to add the
> different modifications to your implementations?
>
> As for lattice-based schemes and other assumptions, we also thought about
> investigations the possibilities there.
>
> With this derivation technique you propose, am I understanding correctly
> that if the user signs with the hash-based scheme, then the user would
> reveal that the different pub keys are linked?
>
> I think it is true, that limiting the number of signatures is the main
> optimisation we should look at. But if we use different parameters sets
> don’t we already loose the compatiability with the standardized schemes?
> And if we already deviate from the standards, why don’t add the
> modifications that can save us extra couple of hundred bytes. From the
> implementation complexity, of course this is subjective, but I think these
> modifications are pretty straight forward.
>
> Best,
>
> Mike
>
>
> Ср, 10 дек. 2025 г. в 09:48, Mikhail Kudinov <mkudinov@blockstream.com>:
>
>> Dear Greg,
>>
>> Thank you for your feedback, your points are important, and I appreciate
>> the opportunity to continue the discussion and clarify a few aspects of
>> your response.
>>
>>
>> On public-key and signature sizes:
>>
>> My main point was that when we compare with other pq alternatives (such
>> as Lattice-based schemes) we should take their public key sizes into
>> account. For ML-DSA the public key is more than 1kB.
>>
>>
>> On verification costs:
>>
>> I agree that it is important to consider how the verification cost scales
>> with block size. At the same time, I believe it is still important to
>> highlight the ratio between signature size and verification cost. For
>> certain parameter sets, this ratio is significantly more favorable than for
>> Schnorr signatures. For some parameter sets it can be more than 10 times
>> better: if we look at the parameters sets in the Table 1, we can achieve
>> 4480 bytes signatures (under the 2^40 signatures limit) with verification
>> ratio being almost 9 times better. I would welcome further feedback here.
>> Specifically, would it be reasonable to choose larger signatures if they
>> offer lower verification costs?
>>
>>
>> On stateful vs. stateless security:
>>
>> Regarding your comment, “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),” I did not fully grasp your argument. Could you please elaborate?
>>
>>
>> On combining threshold Schnorr with a PQ scheme:
>>
>> You mentioned that “there may be advantages to using a threshold Schnorr
>> in series with a single PQ scheme.” My current thinking is that such
>> constructions could already be implemented at the scripting layer; in that
>> sense, users could assemble them without additional opcodes (beyond the PQ
>> signature opcode itself). While I see the potential benefits, I am also
>> worried that such an approach risks introducing loosely-defined security
>> models, which can lead to vulnerabilities.
>>
>>
>> Best,
>>
>> Mike
>>
>>
>> Вт, 9 дек. 2025 г. в 19:20, Boris Nagaev <bnagaev@gmail.com>:
>>
>>> Hi Mikhail, Jonas and all!
>>>
>>> > 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.
>>>
>>> I think there's room to explore N/N Multiparty computation (MPC) for
>>> hash-based signatures. In principle you can secret-share the seed and run
>>> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,
>>> so the chain sees a single normal hash-based signature while it is a result
>>> of cosigning by all N parties. The output stays a single standard-size
>>> signature (e.g., a 2-of-2 compressed to one sig), so you save roughly by N
>>> times versus N separate signatures, but the cost is a heavy MPC protocol to
>>> derive the pubkey and to produce each signature. There's no linearity to
>>> leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it
>>> could be interesting to quantify the overhead versus just collecting N
>>> independent signatures.
>>>
>>> As a small reference point, here's a two-party SHA-256 MPC demo I
>>> recently wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):
>>> https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol
>>> moves about 700 KB of messages and completes in three rounds while
>>> privately computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party
>>> restriction, quantum-vulnerable OT, and semi-honest model could all be
>>> upgraded, but it shows the shape of the protocol.
>>>
>>> With a malicious-secure upgrade and PQ OT, sha2pc would already be
>>> enough for plain Lamport signatures by repeating it 256x2 times. For
>>> WOTS-like signatures you'd need another circuit, but the same repo has
>>> tooling for arbitrary circuits, and WOTS is just a hash chain, so it is
>>> doable; circuit and message sizes should grow linearly with the WOTS chain
>>> depth.
>>>
>>> Curious to hear thoughts on whether N/N MPC with hash-based sigs is
>>> worth prototyping, and what overhead targets would make it compelling
>>> versus plain multisig.
>>>
>>> Best,
>>> Boris
>>>
>>> On Monday, December 8, 2025 at 5:47:49 PM UTC-3 Mikhail Kudinov wrote:
>>>
>>> Hi everyone,
>>>
>>> We'd like to share our analysis of post-quantum options for Bitcoin,
>>> focusing specifically on hash-based schemes. The Bitcoin community has
>>> already discussed SPHINCS+ adoption in previous mailing list threads. We
>>> also looked at this option. A detailed technical report exploring these
>>> schemes, parameter selections, security analysis, and implementation
>>> considerations is available at https://eprint.iacr.org/2025/2203.pdf.
>>> This report can also serve as a gentle introduction into hash-based
>>> schemes, covering the recent optimization techniques. The scripts that
>>> support this report are available at
>>> https://github.com/BlockstreamResearch/SPHINCS-Parameters .
>>> Below, we give a quick summary of our findings.
>>>
>>> We find hash-based signatures to be a compelling post-quantum solution
>>> for several reasons. They rely solely on the security of hash functions
>>> (Bitcoin already depends on the collision resistance of SHA-256) and are
>>> conceptually simple. Moreover, these schemes have undergone extensive
>>> cryptanalysis during the NIST post-quantum standardization process, adding
>>> confidence in their robustness.
>>>
>>> One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
>>> signatures are almost 8KB. An important observation is that SPHINCS+ is
>>> designed to support up to 2^64 signatures. We argue that this bound can be
>>> set lower for Bitcoin use-cases. Moreover, there are several different
>>> optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
>>> scheme, that can reduce the signature size even more.
>>> For example, with these optimizations and a bound on 2^40 signatures we
>>> can get signatures of size 4036 bytes. For 2^30 signatures, we can achieve
>>> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing
>>> time reasonable.
>>>
>>> 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.
>>>
>>> Verification cost per byte is comparable to current Schnorr signatures,
>>> alleviating concerns about blockchain validation overhead.
>>>
>>> As for security targets, we argue that NIST Level 1 (128-bit security)
>>> provides sufficient protection. Quantum attacks require not just O(2^64)
>>> operations but approximately 2^78 Toffoli depth operations in practice,
>>> with limited parallelization benefits.
>>>
>>> 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.
>>>
>>> We explored the possibilities of using hash-based schemes with
>>> Hierarchical Deterministic Wallets. The public child key derivation does
>>> not seem to be efficiently achievable. The hardened derivation is naturally
>>> possible for hash-based schemes.
>>>
>>> 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.
>>>
>>> We welcome community feedback on this approach and hope to contribute to
>>> the broader discourse on ensuring Bitcoin's long-term security in the
>>> post-quantum era. In particular, we are interested in your thoughts on the
>>> following questions:
>>> 1) What are the concrete performance requirements across various
>>> hardware, including low-power devices?
>>> 2) Should multiple schemes with different signature limits be
>>> standardized?
>>> 3) Is there value in supporting stateful schemes alongside stateless
>>> ones?
>>>
>>> Best regards,
>>> Mikhail Kudinov and Jonas Nick
>>> Blockstream Research
>>>
>>> --
>>> 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/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com
>>> <https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>>
--
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/CAPcK4uT99o15z04s772Cu4y7G9WNnVKvdNV0thv_FW129a9TSw%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 14372 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
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
2 siblings, 1 reply; 17+ messages in thread
From: 'conduition' via Bitcoin Development Mailing List @ 2025-12-10 0:14 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 14660 bytes --]
Hi Mike,
> You did a really nice job, I was wondering if it will be hard to add the
different modifications to your implementations?
Thanks! It shouldn't be too hard. I already have some Rust code for
SPHINCS-alpha and SPHINCS+C on my experimental testing implementation:
- https://github.com/conduition/slh-experiments/compare/main...sphincs%2Bc
- https://github.com/conduition/slh-experiments/compare/main...balanced
For SLHVK, I'd add one extra shader at the 2nd-to-last signing stage, which
would execute the WOTS message compression.
But still, the fruits of such optimizations are dwarfed by the benefits of
parallelism and parameter tuning.
> With this derivation technique you propose, am I understanding correctly
that if the user signs with the hash-based scheme, then the user would
reveal that the different pub keys are linked?
Exactly right, since every child address would contain the same SLH-DSA
pubkey. To maximize privacy with SLH-DSA, you'd need to use hardened
derivation to derive different child SLH-DSA keys for each address.
In everyday use this would not be a problem though, because most people
will use the more efficient schemes: ML-DSA, SQIsign, or for the time
being, Schnorr BIP340. You'd want to throw a pseudorandom nonce into the
SLH-DSA tap leaf script to make sure its tap leaf hash is always unique for
every unhardened child address. If you do that, nobody can link them
together unless you use the key to sign a TX. If you do reveal the key,
then yes, you're doxxing common ownership for any coins you spend under
that key. However personally I expect that'd only be necessary in an
emergency where ML-DSA is broken and is no longer safe to spend with.
> I think it is true, that limiting the number of signatures is the main
optimisation we should look at. But if we use different parameters sets
don’t we already loose the compatiability with the standardized schemes?
And if we already deviate from the standards, why don’t add the
modifications that can save us extra couple of hundred bytes. From the
implementation complexity, of course this is subjective, but I think these
modifications are pretty straight forward.
There are two different levels of "compatibility": The algorithms, and the
parameters. If we change both, then we're really not using SLH-DSA at all;
we're using some variant of SPHINCS+. We lose compatibility with all
current and future hardware and software built for SLH-DSA.
If we change only the parameters of FIPS-205
<https://nvlpubs.nist.gov/nistpubs/fips/nist.fips.205.pdf>, but keep the
same algorithms, then sure, some software will not be compatible, but
changing a few constants is *much* easier than rewriting algorithms. Most
SLH-DSA implementations are written to support different parameter sets, so
extending code to support Bitcoin's parameter set(s) would be easy.
It'd also be attractive to do so. If Bitcoin's SLH-DSA implementation
adopts a new set of parameters, then existing/future software and hardware
would have good reason to integrate with Bitcoin, and little reason not to.
They get compatibility almost for free, simply by adding new sets of
constants into their code - no need for forking, or dedicated
implementations. HSMs set up for SLH-DSA firmware signing could be
repurposed as high-security bitcoin signing devices; Open source authors
could broaden the impact of their libraries; All by changing less than 10
lines of code. I would argue that's way more valuable than saving 4%
signature size on an algorithm we hope we never need.
regards,
conduition
On Tuesday, December 9, 2025 at 6:17:10 PM UTC-5 Mikhail Kudinov wrote:
> Dear Conduition,
>
> You did a really nice job, I was wondering if it will be hard to add the
> different modifications to your implementations?
>
> As for lattice-based schemes and other assumptions, we also thought about
> investigations the possibilities there.
>
> With this derivation technique you propose, am I understanding correctly
> that if the user signs with the hash-based scheme, then the user would
> reveal that the different pub keys are linked?
>
> I think it is true, that limiting the number of signatures is the main
> optimisation we should look at. But if we use different parameters sets
> don’t we already loose the compatiability with the standardized schemes?
> And if we already deviate from the standards, why don’t add the
> modifications that can save us extra couple of hundred bytes. From the
> implementation complexity, of course this is subjective, but I think these
> modifications are pretty straight forward.
>
> Best,
>
> Mike
>
>
> Ср, 10 дек. 2025 г. в 09:48, Mikhail Kudinov <mkud...@blockstream.com>:
>
>> Dear Greg,
>>
>> Thank you for your feedback, your points are important, and I appreciate
>> the opportunity to continue the discussion and clarify a few aspects of
>> your response.
>>
>>
>> On public-key and signature sizes:
>>
>> My main point was that when we compare with other pq alternatives (such
>> as Lattice-based schemes) we should take their public key sizes into
>> account. For ML-DSA the public key is more than 1kB.
>>
>>
>> On verification costs:
>>
>> I agree that it is important to consider how the verification cost scales
>> with block size. At the same time, I believe it is still important to
>> highlight the ratio between signature size and verification cost. For
>> certain parameter sets, this ratio is significantly more favorable than for
>> Schnorr signatures. For some parameter sets it can be more than 10 times
>> better: if we look at the parameters sets in the Table 1, we can achieve
>> 4480 bytes signatures (under the 2^40 signatures limit) with verification
>> ratio being almost 9 times better. I would welcome further feedback here.
>> Specifically, would it be reasonable to choose larger signatures if they
>> offer lower verification costs?
>>
>>
>> On stateful vs. stateless security:
>>
>> Regarding your comment, “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),” I did not fully grasp your argument. Could you please elaborate?
>>
>>
>> On combining threshold Schnorr with a PQ scheme:
>>
>> You mentioned that “there may be advantages to using a threshold Schnorr
>> in series with a single PQ scheme.” My current thinking is that such
>> constructions could already be implemented at the scripting layer; in that
>> sense, users could assemble them without additional opcodes (beyond the PQ
>> signature opcode itself). While I see the potential benefits, I am also
>> worried that such an approach risks introducing loosely-defined security
>> models, which can lead to vulnerabilities.
>>
>>
>> Best,
>>
>> Mike
>>
>>
>> Вт, 9 дек. 2025 г. в 19:20, Boris Nagaev <bna...@gmail.com>:
>>
>>> Hi Mikhail, Jonas and all!
>>>
>>> > 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.
>>>
>>> I think there's room to explore N/N Multiparty computation (MPC) for
>>> hash-based signatures. In principle you can secret-share the seed and run
>>> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,
>>> so the chain sees a single normal hash-based signature while it is a result
>>> of cosigning by all N parties. The output stays a single standard-size
>>> signature (e.g., a 2-of-2 compressed to one sig), so you save roughly by N
>>> times versus N separate signatures, but the cost is a heavy MPC protocol to
>>> derive the pubkey and to produce each signature. There's no linearity to
>>> leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it
>>> could be interesting to quantify the overhead versus just collecting N
>>> independent signatures.
>>>
>>> As a small reference point, here's a two-party SHA-256 MPC demo I
>>> recently wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):
>>> https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol
>>> moves about 700 KB of messages and completes in three rounds while
>>> privately computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party
>>> restriction, quantum-vulnerable OT, and semi-honest model could all be
>>> upgraded, but it shows the shape of the protocol.
>>>
>>> With a malicious-secure upgrade and PQ OT, sha2pc would already be
>>> enough for plain Lamport signatures by repeating it 256x2 times. For
>>> WOTS-like signatures you'd need another circuit, but the same repo has
>>> tooling for arbitrary circuits, and WOTS is just a hash chain, so it is
>>> doable; circuit and message sizes should grow linearly with the WOTS chain
>>> depth.
>>>
>>> Curious to hear thoughts on whether N/N MPC with hash-based sigs is
>>> worth prototyping, and what overhead targets would make it compelling
>>> versus plain multisig.
>>>
>>> Best,
>>> Boris
>>>
>>> On Monday, December 8, 2025 at 5:47:49 PM UTC-3 Mikhail Kudinov wrote:
>>>
>>> Hi everyone,
>>>
>>> We'd like to share our analysis of post-quantum options for Bitcoin,
>>> focusing specifically on hash-based schemes. The Bitcoin community has
>>> already discussed SPHINCS+ adoption in previous mailing list threads. We
>>> also looked at this option. A detailed technical report exploring these
>>> schemes, parameter selections, security analysis, and implementation
>>> considerations is available at https://eprint.iacr.org/2025/2203.pdf.
>>> This report can also serve as a gentle introduction into hash-based
>>> schemes, covering the recent optimization techniques. The scripts that
>>> support this report are available at
>>> https://github.com/BlockstreamResearch/SPHINCS-Parameters .
>>> Below, we give a quick summary of our findings.
>>>
>>> We find hash-based signatures to be a compelling post-quantum solution
>>> for several reasons. They rely solely on the security of hash functions
>>> (Bitcoin already depends on the collision resistance of SHA-256) and are
>>> conceptually simple. Moreover, these schemes have undergone extensive
>>> cryptanalysis during the NIST post-quantum standardization process, adding
>>> confidence in their robustness.
>>>
>>> One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
>>> signatures are almost 8KB. An important observation is that SPHINCS+ is
>>> designed to support up to 2^64 signatures. We argue that this bound can be
>>> set lower for Bitcoin use-cases. Moreover, there are several different
>>> optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
>>> scheme, that can reduce the signature size even more.
>>> For example, with these optimizations and a bound on 2^40 signatures we
>>> can get signatures of size 4036 bytes. For 2^30 signatures, we can achieve
>>> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing
>>> time reasonable.
>>>
>>> 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.
>>>
>>> Verification cost per byte is comparable to current Schnorr signatures,
>>> alleviating concerns about blockchain validation overhead.
>>>
>>> As for security targets, we argue that NIST Level 1 (128-bit security)
>>> provides sufficient protection. Quantum attacks require not just O(2^64)
>>> operations but approximately 2^78 Toffoli depth operations in practice,
>>> with limited parallelization benefits.
>>>
>>> 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.
>>>
>>> We explored the possibilities of using hash-based schemes with
>>> Hierarchical Deterministic Wallets. The public child key derivation does
>>> not seem to be efficiently achievable. The hardened derivation is naturally
>>> possible for hash-based schemes.
>>>
>>> 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.
>>>
>>> We welcome community feedback on this approach and hope to contribute to
>>> the broader discourse on ensuring Bitcoin's long-term security in the
>>> post-quantum era. In particular, we are interested in your thoughts on the
>>> following questions:
>>> 1) What are the concrete performance requirements across various
>>> hardware, including low-power devices?
>>> 2) Should multiple schemes with different signature limits be
>>> standardized?
>>> 3) Is there value in supporting stateful schemes alongside stateless
>>> ones?
>>>
>>> Best regards,
>>> Mikhail Kudinov and Jonas Nick
>>> Blockstream Research
>>>
>>> --
>>> 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+...@googlegroups.com.
>>> To view this discussion visit
>>> https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com
>>> <https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>>
--
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/018ee35e-af3d-49d8-a8f2-5c478e681efan%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 17391 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-09 5:08 ` 'conduition' via Bitcoin Development Mailing List
@ 2025-12-10 0:41 ` Olaoluwa Osuntokun
0 siblings, 0 replies; 17+ messages in thread
From: Olaoluwa Osuntokun @ 2025-12-10 0:41 UTC (permalink / raw)
To: conduition; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 13469 bytes --]
Hi y'all,
conduition wrote:
> 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.
This paper [1] proposes a variant of Dilithium (dubbed DilithiumRK, RK for
'randomized keys' presumably) that enables BIP-32-like functionality. It
achieves this by getting rid of a public key compression step in the OG
algorithm that results in a loss of homomorphic properties. There're
algorithmic changes required (eg: a new public network param is needed
which is used for seed/key generation), so it isn't vanilla FIP 204.
Aside from the deviation from the standard, the scheme introduces some
additional trade offs:
* Signatures arger as signatures carry a new error hint
* Signing is 2.7x slower
* Verification is 1.75x slower
There's also a published BIP-32-like like scheme for Falcon signatures [2].
I'm
less familiar with the details here, but the signature size blows up to
~24KB compared to ~666 bytes for normal Falcon signatures.
-- Laolu
[1]: https://cic.iacr.org/p/2/3/3
[2]: https://link.springer.com/article/10.1186/s42400-024-00216-w
On Mon, Dec 8, 2025 at 10:49 PM 'conduition' via Bitcoin Development
Mailing List <bitcoindev@googlegroups.com> wrote:
> 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
> <https://groups.google.com/d/msgid/bitcoindev/0e2402c5-d593-49ff-b002-5ab348b46964n%40googlegroups.com?utm_medium=email&utm_source=footer>
> .
>
--
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/CAO3Pvs_cetTGP54zDzJJGRPeN7gXrRYGZZYk4mRYnhJQnwotdA%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 16590 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
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 0:53 ` Olaoluwa Osuntokun
2 siblings, 0 replies; 17+ messages in thread
From: Olaoluwa Osuntokun @ 2025-12-10 0:53 UTC (permalink / raw)
To: Mikhail Kudinov; +Cc: Boris Nagaev, Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 12933 bytes --]
Hi y'all,
Mike wrote:
> But if we use different parameters sets don’t we already loose the
> compatiability with the standardized schemes?
IIUC, these smaller SPHINCS+ parameters are under active consideration
by NIST [1].
On slide 3 of a recent talk [2] at the 6th PQC Standardization Conference
[3], Quynh Dang states:
> We plan to standardize 2^24-signature limit rls128cs1, rls192cs1,
rls256cs1
But then later in the same slide that:
> We don’t plan to standardize them now:
> Lower limits come with higher security risks when misuse happens
> Minimize the number of parameter sets
In the linked forum post the OP advocates for a swifter standardization
process for the new params:
> We believe all options should be standardized as soon as possible. To meet
> the 2030–2035 targets for post-quantum–only deployments, development must
> be finalized very soon. Roots of trust typically have lifetimes exceeding
> a decade, and any further delay could make it impossible to adopt these
> new options.
So it appears they do plan to standardize these additional parameter sets,
but it won't be done "soon"?
-- Laolu
[1]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/x-eaz9be6_U
[2]:
https://csrc.nist.gov/csrc/media/presentations/2025/sphincs-smaller-parameter-sets/sphincs-dang_2.2.pdf
[3]: https://csrc.nist.gov/Events/2025/6th-pqc-standardization-conference
On Tue, Dec 9, 2025 at 3:17 PM 'Mikhail Kudinov' via Bitcoin Development
Mailing List <bitcoindev@googlegroups.com> wrote:
> Dear Conduition,
>
> You did a really nice job, I was wondering if it will be hard to add the
> different modifications to your implementations?
>
> As for lattice-based schemes and other assumptions, we also thought about
> investigations the possibilities there.
>
> With this derivation technique you propose, am I understanding correctly
> that if the user signs with the hash-based scheme, then the user would
> reveal that the different pub keys are linked?
>
> I think it is true, that limiting the number of signatures is the main
> optimisation we should look at. But if we use different parameters sets
> don’t we already loose the compatiability with the standardized schemes?
> And if we already deviate from the standards, why don’t add the
> modifications that can save us extra couple of hundred bytes. From the
> implementation complexity, of course this is subjective, but I think these
> modifications are pretty straight forward.
>
> Best,
>
> Mike
>
>
> Ср, 10 дек. 2025 г. в 09:48, Mikhail Kudinov <mkudinov@blockstream.com>:
>
>> Dear Greg,
>>
>> Thank you for your feedback, your points are important, and I appreciate
>> the opportunity to continue the discussion and clarify a few aspects of
>> your response.
>>
>>
>> On public-key and signature sizes:
>>
>> My main point was that when we compare with other pq alternatives (such
>> as Lattice-based schemes) we should take their public key sizes into
>> account. For ML-DSA the public key is more than 1kB.
>>
>>
>> On verification costs:
>>
>> I agree that it is important to consider how the verification cost scales
>> with block size. At the same time, I believe it is still important to
>> highlight the ratio between signature size and verification cost. For
>> certain parameter sets, this ratio is significantly more favorable than for
>> Schnorr signatures. For some parameter sets it can be more than 10 times
>> better: if we look at the parameters sets in the Table 1, we can achieve
>> 4480 bytes signatures (under the 2^40 signatures limit) with verification
>> ratio being almost 9 times better. I would welcome further feedback here.
>> Specifically, would it be reasonable to choose larger signatures if they
>> offer lower verification costs?
>>
>>
>> On stateful vs. stateless security:
>>
>> Regarding your comment, “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),” I did not fully grasp your argument. Could you please elaborate?
>>
>>
>> On combining threshold Schnorr with a PQ scheme:
>>
>> You mentioned that “there may be advantages to using a threshold Schnorr
>> in series with a single PQ scheme.” My current thinking is that such
>> constructions could already be implemented at the scripting layer; in that
>> sense, users could assemble them without additional opcodes (beyond the PQ
>> signature opcode itself). While I see the potential benefits, I am also
>> worried that such an approach risks introducing loosely-defined security
>> models, which can lead to vulnerabilities.
>>
>>
>> Best,
>>
>> Mike
>>
>>
>> Вт, 9 дек. 2025 г. в 19:20, Boris Nagaev <bnagaev@gmail.com>:
>>
>>> Hi Mikhail, Jonas and all!
>>>
>>> > 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.
>>>
>>> I think there's room to explore N/N Multiparty computation (MPC) for
>>> hash-based signatures. In principle you can secret-share the seed and run
>>> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,
>>> so the chain sees a single normal hash-based signature while it is a result
>>> of cosigning by all N parties. The output stays a single standard-size
>>> signature (e.g., a 2-of-2 compressed to one sig), so you save roughly by N
>>> times versus N separate signatures, but the cost is a heavy MPC protocol to
>>> derive the pubkey and to produce each signature. There's no linearity to
>>> leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it
>>> could be interesting to quantify the overhead versus just collecting N
>>> independent signatures.
>>>
>>> As a small reference point, here's a two-party SHA-256 MPC demo I
>>> recently wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):
>>> https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol
>>> moves about 700 KB of messages and completes in three rounds while
>>> privately computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party
>>> restriction, quantum-vulnerable OT, and semi-honest model could all be
>>> upgraded, but it shows the shape of the protocol.
>>>
>>> With a malicious-secure upgrade and PQ OT, sha2pc would already be
>>> enough for plain Lamport signatures by repeating it 256x2 times. For
>>> WOTS-like signatures you'd need another circuit, but the same repo has
>>> tooling for arbitrary circuits, and WOTS is just a hash chain, so it is
>>> doable; circuit and message sizes should grow linearly with the WOTS chain
>>> depth.
>>>
>>> Curious to hear thoughts on whether N/N MPC with hash-based sigs is
>>> worth prototyping, and what overhead targets would make it compelling
>>> versus plain multisig.
>>>
>>> Best,
>>> Boris
>>>
>>> On Monday, December 8, 2025 at 5:47:49 PM UTC-3 Mikhail Kudinov wrote:
>>>
>>> Hi everyone,
>>>
>>> We'd like to share our analysis of post-quantum options for Bitcoin,
>>> focusing specifically on hash-based schemes. The Bitcoin community has
>>> already discussed SPHINCS+ adoption in previous mailing list threads. We
>>> also looked at this option. A detailed technical report exploring these
>>> schemes, parameter selections, security analysis, and implementation
>>> considerations is available at https://eprint.iacr.org/2025/2203.pdf.
>>> This report can also serve as a gentle introduction into hash-based
>>> schemes, covering the recent optimization techniques. The scripts that
>>> support this report are available at
>>> https://github.com/BlockstreamResearch/SPHINCS-Parameters .
>>> Below, we give a quick summary of our findings.
>>>
>>> We find hash-based signatures to be a compelling post-quantum solution
>>> for several reasons. They rely solely on the security of hash functions
>>> (Bitcoin already depends on the collision resistance of SHA-256) and are
>>> conceptually simple. Moreover, these schemes have undergone extensive
>>> cryptanalysis during the NIST post-quantum standardization process, adding
>>> confidence in their robustness.
>>>
>>> One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
>>> signatures are almost 8KB. An important observation is that SPHINCS+ is
>>> designed to support up to 2^64 signatures. We argue that this bound can be
>>> set lower for Bitcoin use-cases. Moreover, there are several different
>>> optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
>>> scheme, that can reduce the signature size even more.
>>> For example, with these optimizations and a bound on 2^40 signatures we
>>> can get signatures of size 4036 bytes. For 2^30 signatures, we can achieve
>>> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing
>>> time reasonable.
>>>
>>> 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.
>>>
>>> Verification cost per byte is comparable to current Schnorr signatures,
>>> alleviating concerns about blockchain validation overhead.
>>>
>>> As for security targets, we argue that NIST Level 1 (128-bit security)
>>> provides sufficient protection. Quantum attacks require not just O(2^64)
>>> operations but approximately 2^78 Toffoli depth operations in practice,
>>> with limited parallelization benefits.
>>>
>>> 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.
>>>
>>> We explored the possibilities of using hash-based schemes with
>>> Hierarchical Deterministic Wallets. The public child key derivation does
>>> not seem to be efficiently achievable. The hardened derivation is naturally
>>> possible for hash-based schemes.
>>>
>>> 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.
>>>
>>> We welcome community feedback on this approach and hope to contribute to
>>> the broader discourse on ensuring Bitcoin's long-term security in the
>>> post-quantum era. In particular, we are interested in your thoughts on the
>>> following questions:
>>> 1) What are the concrete performance requirements across various
>>> hardware, including low-power devices?
>>> 2) Should multiple schemes with different signature limits be
>>> standardized?
>>> 3) Is there value in supporting stateful schemes alongside stateless
>>> ones?
>>>
>>> Best regards,
>>> Mikhail Kudinov and Jonas Nick
>>> Blockstream Research
>>>
>>> --
>>> 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/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com
>>> <https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>> --
> 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/CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t6hsd96PfMOYcA%40mail.gmail.com
> <https://groups.google.com/d/msgid/bitcoindev/CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t6hsd96PfMOYcA%40mail.gmail.com?utm_medium=email&utm_source=footer>
> .
>
--
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/CAO3Pvs8A0GLW-xdSHCKosjPqo7WSf-%3DYJ7F7s7t65RvtArcBEQ%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 15461 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-10 0:14 ` 'conduition' via Bitcoin Development Mailing List
@ 2025-12-10 15:55 ` Jonas Nick
0 siblings, 0 replies; 17+ messages in thread
From: Jonas Nick @ 2025-12-10 15:55 UTC (permalink / raw)
To: bitcoindev
Thanks for all the feedback.
Trying to remain consistent with widely deployed, standardized variants of
SLH-DSA is a reasonable design consideration. But in that context it seems
noteworthy that using optimized schemes, instead of just tweaking parameters,
leads to way more than just a 4% reduction in signature size. The WOTS+C +
PORS+FP variant is 16% to 18% smaller than vanilla, size-optimized SPHINCS+ (for
2^40 signatures max) according to our scripts [0].
Another consideration is that in the scenario you [conduition] mention where
Bitcoin would adopt a lattice-based signature scheme and a hash-based signature
scheme, the lattice-based scheme may not be ML-DSA. Maximizing the functionality
benefits of lattice-based sigs may require a custom signature scheme that
supports public key derivation, multi/threshold signatures, aggregate
signatures, silent payments, etc. If the lattice-based signature scheme is
custom, there is little reason why the hash-based signature scheme should not be
custom as well.
More generally, one of my main motivations for working on this project was
whether there exist variants of hash-based signature schemes that are more
suitable for the "advanced" constructions we care about (HD wallets,
multi-signatures, ...). After doing this project with Mike (who has done
research on hash-based signatures for quite a few years), it seems like the
answer is basically no. We discuss some of the approaches in the paper, but it's
of course possible we're missing something. However, in that sense, the paper is
also a negative result.
I cannot follow the conclusion that 99% of people would use ML-DSA. Signature
size is pretty much the same as for parameter-optimized SPHINCS+. Without
lattice-based signature aggregation or silent payments, it seems like the main
benefit is verification time. Since you have probably the best collection of
numbers for perfomance of SLH-DSA, I'd be interested in the performance numbers
of ML-DSA you use for comparison with SLH-DSA.
[0] https://github.com/BlockstreamResearch/SPHINCS-Parameters/blob/main/costs.sage
--
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/27070789-50f0-4d2d-a107-c90be445db14%40gmail.com.
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-09 8:06 ` [bitcoindev] " Boris Nagaev
2025-12-09 22:48 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
@ 2025-12-16 7:25 ` Jonas Nick
2026-01-19 1:12 ` 'conduition' via Bitcoin Development Mailing List
1 sibling, 1 reply; 17+ messages in thread
From: Jonas Nick @ 2025-12-16 7:25 UTC (permalink / raw)
To: bitcoindev
Hi Boris,
Just to add to what Mike said: one of the most interesting questions is whether
MPC considerations should inform parameter selection. As of right now, the
generic MPC approach seems rather impractical, but that shouldn't discourage
experimentation and further research. It's possible to imagine scenarios where
85-minute signing is acceptable.
Moreover, stateful signature schemes like SHRINCS [0] only require a few hashes
in the best case, which would make MPC-based N/N multisig significantly more
tractable than with full SPHINCS+. However, since SHRINCS signatures are already
small, the absolute space savings are smaller.
[0] https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158
Jonas
--
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/34eaa8a5-69c1-4825-8f00-ff6de755ba09%40gmail.com.
^ permalink raw reply [flat|nested] 17+ messages in thread
* [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-08 20:28 [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-08 21:50 ` Greg Maxwell
2025-12-09 8:06 ` [bitcoindev] " Boris Nagaev
@ 2025-12-18 18:45 ` Erik Aronesty
2025-12-19 8:36 ` Jonas Nick
2 siblings, 1 reply; 17+ messages in thread
From: Erik Aronesty @ 2025-12-18 18:45 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 5271 bytes --]
hi, check this out. two simple new opcodes without requiring massive
hash-based signatures and gets you all the quantum resistance you need.
the trick is.. commit to a secret in one block, and reveal in a later
block. you use time-asymmetry to solve the information-asymmetry problem
without needing a full signature.
anchor-gated, template-bound spend using OP_CTV (BIP119) plus one new
opcode for on-chain anchor validation.
https://gist.github.com/earonesty/ea086aa995be1a860af093f93bd45bf2
two new opcodes needd:
OP_CTV : commit to a spending template ( well tested already)
OP_CHECKTXIDDEPTHVERIFY: check that a tx exists a given depth and contains
an op_return with specific value:
none of these are slow or expensive... and they are radically simpler than
quantum signature schemes, while still giving the spending limitations
needed for bitcoin
On Monday, December 8, 2025 at 12:47:49 PM UTC-8 Mikhail Kudinov wrote:
Hi everyone,
We'd like to share our analysis of post-quantum options for Bitcoin,
focusing specifically on hash-based schemes. The Bitcoin community has
already discussed SPHINCS+ adoption in previous mailing list threads. We
also looked at this option. A detailed technical report exploring these
schemes, parameter selections, security analysis, and implementation
considerations is available at https://eprint.iacr.org/2025/2203.pdf. This
report can also serve as a gentle introduction into hash-based schemes,
covering the recent optimization techniques. The scripts that support this
report are available at
https://github.com/BlockstreamResearch/SPHINCS-Parameters .
Below, we give a quick summary of our findings.
We find hash-based signatures to be a compelling post-quantum solution for
several reasons. They rely solely on the security of hash functions
(Bitcoin already depends on the collision resistance of SHA-256) and are
conceptually simple. Moreover, these schemes have undergone extensive
cryptanalysis during the NIST post-quantum standardization process, adding
confidence in their robustness.
One of the biggest drawbacks is the signature sizes. Standard SPHINCS+
signatures are almost 8KB. An important observation is that SPHINCS+ is
designed to support up to 2^64 signatures. We argue that this bound can be
set lower for Bitcoin use-cases. Moreover, there are several different
optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+
scheme, that can reduce the signature size even more.
For example, with these optimizations and a bound on 2^40 signatures we can
get signatures of size 4036 bytes. For 2^30 signatures, we can achieve 3440
bytes, and for 2^20, one can get 3128 bytes, while keeping the signing time
reasonable.
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.
Verification cost per byte is comparable to current Schnorr signatures,
alleviating concerns about blockchain validation overhead.
As for security targets, we argue that NIST Level 1 (128-bit security)
provides sufficient protection. Quantum attacks require not just O(2^64)
operations but approximately 2^78 Toffoli depth operations in practice,
with limited parallelization benefits.
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.
We explored the possibilities of using hash-based schemes with Hierarchical
Deterministic Wallets. The public child key derivation does not seem to be
efficiently achievable. The hardened derivation is naturally possible for
hash-based schemes.
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.
We welcome community feedback on this approach and hope to contribute to
the broader discourse on ensuring Bitcoin's long-term security in the
post-quantum era. In particular, we are interested in your thoughts on the
following questions:
1) What are the concrete performance requirements across various hardware,
including low-power devices?
2) Should multiple schemes with different signature limits be standardized?
3) Is there value in supporting stateful schemes alongside stateless ones?
Best regards,
Mikhail Kudinov and Jonas Nick
Blockstream Research
--
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/60d61084-f1aa-4911-a615-77d8597645c0n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 5953 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-18 18:45 ` Erik Aronesty
@ 2025-12-19 8:36 ` Jonas Nick
2025-12-20 1:14 ` Erik Aronesty
0 siblings, 1 reply; 17+ messages in thread
From: Jonas Nick @ 2025-12-19 8:36 UTC (permalink / raw)
To: bitcoindev
This appears to be a variant of a commit-reveal scheme, a design that has been
discussed a few times on this mailing list. Commit-reveal schemes come with
their own set of trade-offs.
--
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/b6df02a0-8d69-4882-a13c-411bc90adfa1%40gmail.com.
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-19 8:36 ` Jonas Nick
@ 2025-12-20 1:14 ` Erik Aronesty
2025-12-24 15:02 ` david torrealba
0 siblings, 1 reply; 17+ messages in thread
From: Erik Aronesty @ 2025-12-20 1:14 UTC (permalink / raw)
To: Jonas Nick; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 2019 bytes --]
this scheme has no mitm attack or replay attack because of the use of
covenants to secure each step in the chain
The best part about starting with something like this is that we can have a
safe quantum vault, too useful covenants that are broadly helpful for other
vaulting schemes, while we develop a proper library that is both performant
and efficient for quantum signatures.
secp256k1 has been optimized to the point where timing attacks are
challenging, and I wouldn't want to use some sort of quantum library that
hasn't had that level of optimization.
simple commit reveal schemes use hashes that are well known to be quantum
resistant. I consider that a lot safer at first step forward. especially
because we can take that step sooner than later without too much discussion
over implementation since the underlying covenants have been well studied.
(txhash and ctv)
we can't say that about any signature schemes.
On Fri, Dec 19, 2025, 3:34 AM Jonas Nick <jonasd.nick@gmail.com> wrote:
> This appears to be a variant of a commit-reveal scheme, a design that has
> been
> discussed a few times on this mailing list. Commit-reveal schemes come with
> their own set of trade-offs.
>
> --
> 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/b6df02a0-8d69-4882-a13c-411bc90adfa1%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/CAJowKgL-VBTgbacpbPStGMqe6u6Y7wB6fWNiGy28zWfkCODp%3DA%40mail.gmail.com.
[-- Attachment #2: Type: text/html, Size: 3060 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-20 1:14 ` Erik Aronesty
@ 2025-12-24 15:02 ` david torrealba
0 siblings, 0 replies; 17+ messages in thread
From: david torrealba @ 2025-12-24 15:02 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 3570 bytes --]
Hi everyone,
I've been following the discussion regarding the trade-offs of Post-Quantum
signature sizes and their performance impacts on low-power devices.
I wanted to share some practical insights from the *Cellframe* project that
might be relevant to these benchmarks. We have been running a C-based
blockchain implementation that natively supports multiple NIST-candidate
post-quantum algorithms (including *Crystal-Dilithium/ML-DSA* and others
discussed here) for several years.
Since our core is written in C with a focus on hardware optimization
(specifically targeting low-end embedded devices alongside high-performance
nodes), we have gathered significant real-world data regarding:
1.
Memory Footprint: The actual dynamic RAM usage differences between
Lattice-based vs. Hash-based signatures on constrained hardware.
2.
Verification Time*:* Concrete signing/verification times on low-power
ARM architectures when the code is highly optimized in C.
If the working group is interested, we would be happy to share our
benchmarks and optimization techniques to help validate the theoretical
constraints currently being discussed for Bitcoin's PQ transition. We
believe our experience dealing with the signature size overhead in a live
production environment could provide a useful reference point.
Best regards,
El sábado, 20 de diciembre de 2025 a las 8:04:18 UTC-4, Erik Aronesty
escribió:
> this scheme has no mitm attack or replay attack because of the use of
> covenants to secure each step in the chain
>
> The best part about starting with something like this is that we can have
> a safe quantum vault, too useful covenants that are broadly helpful for
> other vaulting schemes, while we develop a proper library that is both
> performant and efficient for quantum signatures.
>
> secp256k1 has been optimized to the point where timing attacks are
> challenging, and I wouldn't want to use some sort of quantum library that
> hasn't had that level of optimization.
>
> simple commit reveal schemes use hashes that are well known to be quantum
> resistant. I consider that a lot safer at first step forward. especially
> because we can take that step sooner than later without too much discussion
> over implementation since the underlying covenants have been well studied.
> (txhash and ctv)
>
> we can't say that about any signature schemes.
>
>
>
> On Fri, Dec 19, 2025, 3:34 AM Jonas Nick <jonas...@gmail.com> wrote:
>
>> This appears to be a variant of a commit-reveal scheme, a design that has
>> been
>> discussed a few times on this mailing list. Commit-reveal schemes come
>> with
>> their own set of trade-offs.
>>
>> --
>> 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+...@googlegroups.com.
>>
> To view this discussion visit
>> https://groups.google.com/d/msgid/bitcoindev/b6df02a0-8d69-4882-a13c-411bc90adfa1%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/769f97ee-7874-44cd-acdd-a9d283f79430n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 5276 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
2025-12-16 7:25 ` Jonas Nick
@ 2026-01-19 1:12 ` 'conduition' via Bitcoin Development Mailing List
0 siblings, 0 replies; 17+ messages in thread
From: 'conduition' via Bitcoin Development Mailing List @ 2026-01-19 1:12 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 1930 bytes --]
Hey Jonas,
I've been busy over the holidays but just got around to reading your
delving post on SHRINCS. Big +1 from me, perhaps not in the exact form you
propose - i suspect a more modular approach would make standardization
easier - But in principle this would be awesome to have as an option. It
has pitfalls, but until more size-efficient stateless schemes like SQIsign
mature, stateful HBS schemes are the smallest signatures available. Full
thoughts on delving here
<https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158/7?u=conduition>
regards,
conduition
On Tuesday, December 16, 2025 at 3:30:58 AM UTC-5 Jonas Nick wrote:
> Hi Boris,
>
> Just to add to what Mike said: one of the most interesting questions is
> whether
> MPC considerations should inform parameter selection. As of right now, the
> generic MPC approach seems rather impractical, but that shouldn't
> discourage
> experimentation and further research. It's possible to imagine scenarios
> where
> 85-minute signing is acceptable.
>
> Moreover, stateful signature schemes like SHRINCS [0] only require a few
> hashes
> in the best case, which would make MPC-based N/N multisig significantly
> more
> tractable than with full SPHINCS+. However, since SHRINCS signatures are
> already
> small, the absolute space savings are smaller.
>
> [0]
> https://delvingbitcoin.org/t/shrincs-324-byte-stateful-post-quantum-signatures-with-static-backups/2158
>
> Jonas
>
--
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/58e6a5e3-8705-43f5-8187-724b8e3a62den%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 2869 bytes --]
^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2026-01-19 1:25 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2025-12-08 20:28 [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future '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
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
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox