From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future
Date: Tue, 9 Dec 2025 16:14:47 -0800 (PST) [thread overview]
Message-ID: <018ee35e-af3d-49d8-a8f2-5c478e681efan@googlegroups.com> (raw)
In-Reply-To: <CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t6hsd96PfMOYcA@mail.gmail.com>
[-- 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 --]
next prev parent reply other threads:[~2025-12-10 0:16 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 ` [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 [this message]
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=018ee35e-af3d-49d8-a8f2-5c478e681efan@googlegroups.com \
--to=bitcoindev@googlegroups.com \
--cc=conduition@proton.me \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox