From: Boris Nagaev <bnagaev@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
Date: Tue, 9 Dec 2025 00:06:23 -0800 (PST) [thread overview]
Message-ID: <492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com> (raw)
In-Reply-To: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com>
[-- 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 --]
next prev parent reply other threads:[~2025-12-09 8:20 UTC|newest]
Thread overview: 17+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-12-08 20:28 [bitcoindev] " '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 ` Boris Nagaev [this message]
2025-12-09 22:48 ` [bitcoindev] " 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-09 23:06 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-10 0:01 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2025-12-10 0:14 ` 'conduition' via Bitcoin Development Mailing List
2025-12-10 15:55 ` Jonas Nick
2025-12-10 0:53 ` Olaoluwa Osuntokun
2025-12-16 7:25 ` Jonas Nick
2026-01-19 1:12 ` 'conduition' via Bitcoin Development Mailing List
2025-12-18 18:45 ` Erik Aronesty
2025-12-19 8:36 ` Jonas Nick
2025-12-20 1:14 ` Erik Aronesty
2025-12-24 15:02 ` david torrealba
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com \
--to=bnagaev@gmail.com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox