From: "'Mikhail Kudinov' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Algorithm Agility for Bitcoin to maintain security in the face of quantum and classic breaks in the signature algorithms
Date: Thu, 26 Feb 2026 05:24:27 -0800 (PST) [thread overview]
Message-ID: <45c53988-f011-4bc5-b58b-7656dcf5d080n@googlegroups.com> (raw)
In-Reply-To: <5ce409f5-2416-4d79-9883-c2fb4b3eaaa8n@googlegroups.com>
[-- Attachment #1.1: Type: text/plain, Size: 9869 bytes --]
Dear Javier,
Thank you for your work. I am happy that more people are looking at the
possibility of using Hash-based schemes as a PQ solution for Bitcoin.
As far as I understood, the main idea was to propose concrete
instantiations/parameters, and essentially, the small signatures come from
the 2^10 limit on the number of signatures + fast route for the first
signature. The other proposal was to use 128-bit hash functions for chains,
which I think is the default way for the 128-bit security requirement.
I don't see why one needs to use the full 256 hashes in the Merkle trees.
In the signature context, we don't require collision resistance for
security. We only need target collision resistance, which can not be
attacked with the birthday paradox.
As for the statefulness issue: I agree that the blockchain does record the
signed transactions, but some of them may not end on the blockchain, hence
it is not a 100% reliable source of state. Given that the reuse of a nonce
leads to a forgery of the signature scheme, we can not use blockchain state
as a source of state.
As for the comparison with the alternative schemes, I think we should not
omit the number of supported signatures. It is an important metric that is
tightly related to the efficiency of a hash-based signature scheme.
Regarding some details that you mention in the paper:
Second-preimage resistance is not enough for the security of W-OTS+. Even
in [9] they require preimage resistance and undetectability. There is a
newer and tighter proof for XMSS, which can be found
here: https://eprint.iacr.org/2023/408 (based on
https://eprint.iacr.org/2022/346).
To achieve 128-bit security with the non-tight reduction strategy, one
needs to add K + log(lw) bits rather than just log(lw). But with the tight
proof I referenced, this loss can be avoided.
I also did not understand how you suggest deriving the public seed from the
transaction, given that the public seed is needed to compute the public key
root.
The original SPHINCS scheme used HORST, not FORS. FORS was introduced later
for SPHINCS+ (SLH-DSA).
Best,
Mike
On Wednesday, February 25, 2026 at 12:32:47 PM UTC+1 Javier Mateos wrote:
> Hi list,
>
> Ethan’s framework of using Schnorr for everyday spending and a hash based
> signature as a fallback inside P2MR strikes me as the right direction. I’ve
> been working on a concrete proposal for that fallback role.
>
> WOTS-Tree [1] is essentially XMSS parameterized for Bitcoin: SHA-256
> truncated to 128 bits for the WOTS+ chains, and full SHA-256 for the Merkle
> tree. The fallback witness is 675 bytes with 1,024 leaves, or 353 bytes for
> single use UTXOs. Verification is bounded at 4,601 hash computations.
>
> It is deployed as a leaf under BIP 341 and is compatible with BIP 360.
> When spending with Schnorr, the extra cost is the same ~10 vbytes as any
> other unused leaf.
>
> It is stateful, which I understand is not ideal for everyone. However,
> unlike generic XMSS, the main risk of stateful schemes reusing an index and
> breaking security is mitigated here because the blockchain already records
> which leaves have been used. The paper describes a three step state
> recovery protocol based on the UTXO set, and chain isolation ensures that
> RBF does not force signature reuse.
>
> Paper with full security reduction, implementation, and test vectors:
> [1] https://eprint.iacr.org/2026/374 <https://eprint.iacr.org/2026/XXX>
> [2] https://github.com/javierpmateos/wots-tree
>
> Best regards,
> Javier
>
> El miércoles, 25 de febrero de 2026 a las 0:42:16 UTC-3, Alex escribió:
>
>> You don't need "the perfect signature" on day 1, you just need something
>> everyone can agree on is good enough as a migration step. SLH-DSA can
>> indeed fill that role - it means a transaction will cost about 10x more
>> than now.
>>
>> Whether SLH-DSA or ML-DSA is picked is IMO less important because
>> eventually "the perfect signature" will be ready: https://sqisign.org/
>>
>> SQIsign is 65 + 148 bytes and my DDR3 era Haswell PC (from 2014) can
>> verify 1000 sigs per second using the non-optimized reference
>> implementation. A modern budget CPU can do 30k verifications per second.
>>
>> You only need SLH-DSA as an (optional) signature that maybe is never even
>> used at all. It's just an insurance. When I hear people say "we don't need
>> this we can just make a ZK proof of the seed phrase" - I'm pretty sure such
>> a ZK proof is much larger than SLH-DSA anyways and would require a total
>> halt of the Bitcoin network and be way less efficient. With SLH-DSA you
>> would get that migration done seamlessly and more efficient anyways.
>>
>> måndag 23 februari 2026 kl. 23:03:03 UTC+1 skrev Ethan Heilman:
>>
>>> > I thought "tweaking", in general, is lost in SPHINCS, as well as
>>> multiparty sigs. Be interested to see those solutions. But, regardless,
>>> 17kb sigs are... not compatible with a decentralized bitcoin, imo.
>>> Lattice-sigs are the only reasonable PQ way forward and they aren't ready
>>> yet.
>>>
>>> SPHINCS is ~8kb (7,888 bytes) not 17kb.
>>>
>>> SPHINCS SLH-DSA-128s has 32 byte public keys and 7,856 byte signatures
>>> Total size of 7,888 bytes not 17kb.
>>>
>>> The Lattice sigs aren't that much better than SPHINCS
>>>
>>> CRYSTALS-Dilithium ML-DSA has 1,312 byte public keys and 2,420 byte
>>> signatures
>>> Total size of 3,732 bytes.
>>>
>>> Falcon has 897 byte public keys and 666 signatures
>>> 1,563 bytes
>>>
>>> ML-DSA currently has the most support in the Lattice world, but it is
>>> still too large to be a drop in replacement for ECC without a witness
>>> discount. If we had to choose tomorrow, I'd advocate for ML-DSA with a
>>> massive witness discount, but I'd be very unhappy with the witness
>>> discount. If the witness discount was out of the question, then I'd
>>> advocate for something similar to 324-byte stateful hash based SHRINCS
>>> signature. Neither is ideal.
>>>
>>> My current thinking is to use SLH-DSA as a backup. This keeps us safe if
>>> everything goes wrong and allows us to reach safety early so we can take
>>> time to determine the right drop-in replacement for ECC. Hopefully in 3
>>> years, SQI-sign is fast enough to be considered.
>>>
>>> On Mon, Feb 23, 2026 at 2:08 PM Erik Aronesty <er...@q32.com> wrote:
>>>
>>>>
>>>>>
>>>>> I'd be excited to learn about this as an option. Erik, could you
>>>>> please answer my previous questions about the viability of your linked
>>>>> protocol? I'm not questioning its quantum-resistance properties (yet). I'm
>>>>> wondering how it is possible to instantiate this scheme in a way that
>>>>> allows a wallet to actually use this commit/reveal scheme without knowing
>>>>> the final destination CTV templates (denoted T & E in the delving post) in
>>>>> advance of creating the phase 0 locking script.
>>>>>
>>>>
>>>> I provided an example script that shows how it works:
>>>> https://gist.github.com/earonesty/ea086aa995be1a860af093f93bd45bf2.
>>>> you don't pin to the final destination in phase 0.
>>>>
>>>> txhash is a partial-commitment, not over all fields. this give the
>>>> flexibility needed for the final spend, since you don't commit to it.
>>>>
>>>> however someone has pointed out a fee-problem that CCV's value-aware
>>>> composability can solve. coming around to thinking the ccv-based
>>>> construction would be necessary. CCV is more powerful but requires much
>>>> more care in policy and analysis. CTV is trivial, we could merge it
>>>> tomorrow and hardly worry about surface area issues. TXHASH is only
>>>> slightly more complicated. CCV has a much bigger burden of proof around
>>>> implementation and node safety... but i think you could do many kinds of
>>>> vaulting schemes with it alone.
>>>>
>>>>
>>>> But in the case of hash-based signature (HBS) schemes, i disagree. HBS
>>>>> is already mature. Whatever cryptanalytic breakthroughs the future holds,
>>>>> we can be reasonably sure that SHA256 preimage resistance will hold for a
>>>>> long time, so HBS security will hold. Even today md4 and md5 preimage
>>>>> resistance still holds. Securing coins using hashes alone is the ideal
>>>>> fallback, and even if HBS is not the most efficient class of schemes, that
>>>>> doesn't matter so much if we don't use HBS as our primary everyday
>>>>> signature scheme. Its value lies in security, not efficiency.
>>>>>
>>>>
>>>> When I mean "too soon", I'm including SPHINCS, not sure what
>>>>
>>>> 1. Earlier versions of the SPHINCS framework were found to be
>>>> susceptible to fault attacks
>>>> 2. Earlier "Tight" proof for v1 SPHINCS was flawed, leading to 60 bits
>>>> of security, not 128
>>>>
>>>> > If you're worried about stuff like how xpubs would work with HBS, we
>>>> have solutions for that too, and they are mostly drop-in replacements for
>>>> existing standards.
>>>>
>>>> I thought "tweaking", in general, is lost in SPHINCS, as well as
>>>> multiparty sigs. Be interested to see those solutions. But, regardless,
>>>> 17kb sigs are... not compatible with a decentralized bitcoin, imo.
>>>> Lattice-sigs are the only reasonable PQ way forward and they aren't ready
>>>> yet.
>>>>
>>>
--
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/45c53988-f011-4bc5-b58b-7656dcf5d080n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 12535 bytes --]
next prev parent reply other threads:[~2026-02-26 13:32 UTC|newest]
Thread overview: 42+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-02-09 14:20 Ethan Heilman
2026-02-10 8:53 ` Jonas Nick
2026-02-10 16:44 ` Ethan Heilman
[not found] ` <CAJowKg+WJLAJoMhyhVfkC9OSdks5jBieDWty9ce-Qju-84URFA@mail.gmail.com>
2026-02-10 23:13 ` Ethan Heilman
2026-02-11 0:19 ` Erik Aronesty
2026-02-11 2:40 ` Ethan Heilman
2026-02-11 7:25 ` Erik Aronesty
2026-02-11 16:37 ` Ethan Heilman
2026-02-17 4:13 ` 'conduition' via Bitcoin Development Mailing List
2026-02-17 7:39 ` 'conduition' via Bitcoin Development Mailing List
2026-02-19 14:35 ` Garlo Nicon
2026-02-20 1:41 ` Alex
2026-02-20 18:48 ` Erik Aronesty
2026-02-23 14:00 ` 'conduition' via Bitcoin Development Mailing List
2026-02-23 19:08 ` Erik Aronesty
2026-02-23 21:42 ` Ethan Heilman
2026-02-24 0:12 ` Alex
2026-02-25 10:43 ` Javier Mateos
2026-02-26 13:24 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List [this message]
2026-02-26 15:51 ` Matt Corallo
2026-02-27 15:18 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2026-02-27 19:31 ` 'conduition' via Bitcoin Development Mailing List
2026-03-01 12:24 ` 'Mikhail Kudinov' via Bitcoin Development Mailing List
2026-03-01 21:28 ` Alex
2026-02-11 18:53 ` Matt Corallo
2026-02-11 22:57 ` Ethan Heilman
2026-02-12 14:55 ` Matt Corallo
2026-02-12 15:35 ` Alex
2026-02-12 19:20 ` Matt Corallo
2026-02-12 18:08 ` Ethan Heilman
2026-02-12 19:13 ` Matt Corallo
2026-02-12 20:35 ` Ethan Heilman
2026-02-12 20:43 ` Matt Corallo
2026-02-12 15:13 ` Alex
2026-02-12 19:16 ` Matt Corallo
2026-02-12 15:36 ` waxwing/ AdamISZ
2026-02-12 19:35 ` Matt Corallo
2026-02-12 19:43 ` Matt Corallo
2026-02-14 12:39 ` waxwing/ AdamISZ
2026-02-15 12:12 ` Matt Corallo
2026-02-10 21:51 ` 'Brandon Black' via Bitcoin Development Mailing List
2026-02-10 22:19 ` Ethan Heilman
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=45c53988-f011-4bc5-b58b-7656dcf5d080n@googlegroups.com \
--to=bitcoindev@googlegroups.com \
--cc=mkudinov@blockstream.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox