From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 16:16:05 -0800 Received: from mail-oi1-f191.google.com ([209.85.167.191]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vT7sB-00041W-Id for bitcoindev@gnusha.org; Tue, 09 Dec 2025 16:16:05 -0800 Received: by mail-oi1-f191.google.com with SMTP id 5614622812f47-45015d0d16asf8806601b6e.2 for ; Tue, 09 Dec 2025 16:16:03 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1765325757; x=1765930557; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :from:to:cc:subject:date:message-id:reply-to; bh=CJJ8lrXCqIQZVizbZkMXxAOko3+vBcBL4IAPq4fjTa0=; b=IvtLNJhfaQzvjn1c4SDGLfwxWlbQO1sAqoD2xkmpDu5Z19zlVAbxZxNEg+PrBjjCXI ZX+osnB/mrd3wodvD+PbxOog1C+btzbV3BqZKr5qiVVE11vYqc0hE5vkkeINsU9Y5gyn 5uJkHy2f1+skiHEDzy8KVygw4GXjNwrgmbsJ0iJAZ2BF15G3r+hW7+FyHEqJJJ+S+nXu SMU9+naBfFqz6BrMBi2yOXDUrhMpppcFOXJpu2WibNsUlOakYGo5NyWG/xPK9XhzOSig 7nbztboynlDyRBddaOmgzcUHNuhdM7ltxim4tFCh4a4Av+erqytcF12vKm6o1NN3aPDD S5+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765325757; x=1765930557; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :x-beenthere:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=CJJ8lrXCqIQZVizbZkMXxAOko3+vBcBL4IAPq4fjTa0=; b=CsUdURgT8vogRuhozUKfjLxedw9+tik/7FwaTS5n05smuDn3Qh2m57Pne8CgT24UF1 V160dY0Eod6Wc48S+Uw+oTz4d16+Z2xJ85kOswIx8iLJ9rCmIXfw65IKg/8Z8A5rostT XDze1bWRdQOA7MDEnc7kFMAdzNkX3+Yyx5CxGU81qP7DOGW3N4AYaOjeetxZ4itEWe9c XZOgmvgIK+uQIjWz95KpL41+vKY3jqEM6hvQhkmpRNM6O9JglhTH0C9SGayRT+Ghutf2 beS0EPFwirSlluN/gVDwzWTntjl/7HRYdHyq4wG9B72OgixzSGNC55A+GB54JqXS4jBC ww7w== X-Forwarded-Encrypted: i=1; AJvYcCUKvRDMv/8wwHTnjevWAa5od78trsIFPX7v2AGTf/PQzE8DhprdRb1BriQ6tz1IvZzJIIN/8X0akvBU@gnusha.org X-Gm-Message-State: AOJu0YzeVaFMfRO/xBlF99KybluXPt6S4N3cM8UwagaSiwLixR6V345K iDE71nfenuy6YGytFnjmkb305QV3cIZGlbs64dq9XijkfjPYD+qPmAdb X-Google-Smtp-Source: AGHT+IFCLLrCpg+K1NbDN0i+tpA2nbrxTVLrdaFrQXCa28B0UJpH76ZTx8ql8wTtyntUsaD3z/JmgA== X-Received: by 2002:a05:6808:6901:b0:44f:8f65:1e24 with SMTP id 5614622812f47-4558656d108mr411540b6e.60.1765325757302; Tue, 09 Dec 2025 16:15:57 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWZZuuenGsUgY9UYSjKX5BG00EAi15eFY/4T+cO0q8Qq9Q==" Received: by 2002:a05:6870:9a1d:b0:3db:9632:4d51 with SMTP id 586e51a60fabf-3f50904860els3348546fac.1.-pod-prod-09-us; Tue, 09 Dec 2025 16:15:53 -0800 (PST) X-Received: by 2002:a05:6808:1491:b0:442:1d6:dfc3 with SMTP id 5614622812f47-45586580dc3mr496296b6e.10.1765325753391; Tue, 09 Dec 2025 16:15:53 -0800 (PST) Received: by 2002:a05:690c:c36b:b0:780:f7eb:fdf with SMTP id 00721157ae682-78c23b71cfdms7b3; Tue, 9 Dec 2025 16:14:48 -0800 (PST) X-Received: by 2002:a05:690e:1485:b0:63f:9c11:cfed with SMTP id 956f58d0204a3-6446e936e0fmr712608d50.32.1765325687471; Tue, 09 Dec 2025 16:14:47 -0800 (PST) Date: Tue, 9 Dec 2025 16:14:47 -0800 (PST) From: "'conduition' via Bitcoin Development Mailing List" To: Bitcoin Development Mailing List Message-Id: <018ee35e-af3d-49d8-a8f2-5c478e681efan@googlegroups.com> In-Reply-To: References: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com> <492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com> Subject: Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_245052_1565323084.1765325687128" X-Original-Sender: conduition@proton.me X-Original-From: conduition Reply-To: conduition Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -1.0 (-) ------=_Part_245052_1565323084.1765325687128 Content-Type: multipart/alternative; boundary="----=_Part_245053_463662434.1765325687128" ------=_Part_245053_463662434.1765325687128 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Mike, > You did a really nice job, I was wondering if it will be hard to add the= =20 different modifications to your implementations?=20 Thanks! It shouldn't be too hard. I already have some Rust code for=20 SPHINCS-alpha and SPHINCS+C on my experimental testing implementation:=20 - 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= =20 would execute the WOTS message compression. But still, the fruits of such optimizations are dwarfed by the benefits of= =20 parallelism and parameter tuning. > With this derivation technique you propose, am I understanding correctly= =20 that if the user signs with the hash-based scheme, then the user would=20 reveal that the different pub keys are linked? Exactly right, since every child address would contain the same SLH-DSA=20 pubkey. To maximize privacy with SLH-DSA, you'd need to use hardened=20 derivation to derive different child SLH-DSA keys for each address. In everyday use this would not be a problem though, because most people=20 will use the more efficient schemes: ML-DSA, SQIsign, or for the time=20 being, Schnorr BIP340. You'd want to throw a pseudorandom nonce into the=20 SLH-DSA tap leaf script to make sure its tap leaf hash is always unique for= =20 every unhardened child address. If you do that, nobody can link them=20 together unless you use the key to sign a TX. If you do reveal the key,=20 then yes, you're doxxing common ownership for any coins you spend under=20 that key. However personally I expect that'd only be necessary in an=20 emergency where ML-DSA is broken and is no longer safe to spend with.=20 > I think it is true, that limiting the number of signatures is the main=20 optimisation we should look at. But if we use different parameters sets=20 don=E2=80=99t we already loose the compatiability with the standardized sch= emes?=20 And if we already deviate from the standards, why don=E2=80=99t add the=20 modifications that can save us extra couple of hundred bytes. From the=20 implementation complexity, of course this is subjective, but I think these= =20 modifications are pretty straight forward.=20 There are two different levels of "compatibility": The algorithms, and the= =20 parameters. If we change both, then we're really not using SLH-DSA at all;= =20 we're using some variant of SPHINCS+. We lose compatibility with all=20 current and future hardware and software built for SLH-DSA. If we change only the parameters of FIPS-205=20 , but keep the=20 same algorithms, then sure, some software will not be compatible, but=20 changing a few constants is *much* easier than rewriting algorithms. Most= =20 SLH-DSA implementations are written to support different parameter sets, so= =20 extending code to support Bitcoin's parameter set(s) would be easy. =20 It'd also be attractive to do so. If Bitcoin's SLH-DSA implementation=20 adopts a new set of parameters, then existing/future software and hardware= =20 would have good reason to integrate with Bitcoin, and little reason not to.= =20 They get compatibility almost for free, simply by adding new sets of=20 constants into their code - no need for forking, or dedicated=20 implementations. HSMs set up for SLH-DSA firmware signing could be=20 repurposed as high-security bitcoin signing devices; Open source authors=20 could broaden the impact of their libraries; All by changing less than 10= =20 lines of code. I would argue that's way more valuable than saving 4%=20 signature size on an algorithm we hope we never need. regards, conduition On Tuesday, December 9, 2025 at 6:17:10=E2=80=AFPM UTC-5 Mikhail Kudinov wr= ote: > Dear Conduition, > > You did a really nice job, I was wondering if it will be hard to add the= =20 > different modifications to your implementations?=20 > > As for lattice-based schemes and other assumptions, we also thought about= =20 > investigations the possibilities there.=20 > > With this derivation technique you propose, am I understanding correctly= =20 > that if the user signs with the hash-based scheme, then the user would=20 > reveal that the different pub keys are linked? > > I think it is true, that limiting the number of signatures is the main=20 > optimisation we should look at. But if we use different parameters sets= =20 > don=E2=80=99t we already loose the compatiability with the standardized s= chemes?=20 > And if we already deviate from the standards, why don=E2=80=99t add the= =20 > modifications that can save us extra couple of hundred bytes. From the=20 > implementation complexity, of course this is subjective, but I think thes= e=20 > modifications are pretty straight forward.=20 > > Best, > > Mike > > > =D0=A1=D1=80, 10 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0=B3. =D0=B2 09:48, M= ikhail Kudinov : > >> Dear Greg, >> >> Thank you for your feedback, your points are important, and I appreciate= =20 >> the opportunity to continue the discussion and clarify a few aspects of= =20 >> your response. >> >> >> On public-key and signature sizes: >> >> My main point was that when we compare with other pq alternatives (such= =20 >> as Lattice-based schemes) we should take their public key sizes into=20 >> 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 scale= s=20 >> with block size. At the same time, I believe it is still important to=20 >> highlight the ratio between signature size and verification cost. For=20 >> certain parameter sets, this ratio is significantly more favorable than = for=20 >> Schnorr signatures. For some parameter sets it can be more than 10 times= =20 >> better: if we look at the parameters sets in the Table 1, we can achieve= =20 >> 4480 bytes signatures (under the 2^40 signatures limit) with verificatio= n=20 >> ratio being almost 9 times better. I would welcome further feedback here= .=20 >> Specifically, would it be reasonable to choose larger signatures if they= =20 >> offer lower verification costs? >> >> >> On stateful vs. stateless security: >> >> Regarding your comment, =E2=80=9CI think schemes with weakened stateless= security=20 >> could be improved to ~full repeated-use security via statefulness (e.g.,= =20 >> grinding the message to avoid revealing signatures that leak key=20 >> material),=E2=80=9D I did not fully grasp your argument. Could you pleas= e elaborate? >> >> >> On combining threshold Schnorr with a PQ scheme: >> >> You mentioned that =E2=80=9Cthere may be advantages to using a threshold= Schnorr=20 >> in series with a single PQ scheme.=E2=80=9D My current thinking is that = such=20 >> constructions could already be implemented at the scripting layer; in th= at=20 >> sense, users could assemble them without additional opcodes (beyond the = PQ=20 >> signature opcode itself). While I see the potential benefits, I am also= =20 >> worried that such an approach risks introducing loosely-defined security= =20 >> models, which can lead to vulnerabilities. >> >> >> Best, >> >> Mike >> >> >> =D0=92=D1=82, 9 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0=B3. =D0=B2 19:20, B= oris Nagaev : >> >>> Hi Mikhail, Jonas and all! >>> >>> > If we look at multi/distributed/threshold-signatures, we find that=20 >>> current approaches either don't give much gains compared to plain usage= of=20 >>> multiple signatures, or require a trusted dealer, which drastically lim= its=20 >>> the use-cases.=20 >>> >>> I think there's room to explore N/N Multiparty computation (MPC) for=20 >>> hash-based signatures. In principle you can secret-share the seed and r= un=20 >>> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS wor= k,=20 >>> so the chain sees a single normal hash-based signature while it is a re= sult=20 >>> of cosigning by all N parties. The output stays a single standard-size= =20 >>> signature (e.g., a 2-of-2 compressed to one sig), so you save roughly b= y N=20 >>> times versus N separate signatures, but the cost is a heavy MPC protoco= l to=20 >>> derive the pubkey and to produce each signature. There's no linearity t= o=20 >>> leverage (unlike MuSig-style Schnorr), so generic MPC is heavy, but it= =20 >>> could be interesting to quantify the overhead versus just collecting N= =20 >>> independent signatures. >>> >>> As a small reference point, here's a two-party SHA-256 MPC demo I=20 >>> recently wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):= =20 >>> https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol=20 >>> moves about 700 KB of messages and completes in three rounds while=20 >>> privately computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-p= arty=20 >>> restriction, quantum-vulnerable OT, and semi-honest model could all be= =20 >>> upgraded, but it shows the shape of the protocol. >>> >>> With a malicious-secure upgrade and PQ OT, sha2pc would already be=20 >>> enough for plain Lamport signatures by repeating it 256x2 times. For=20 >>> WOTS-like signatures you'd need another circuit, but the same repo has= =20 >>> tooling for arbitrary circuits, and WOTS is just a hash chain, so it is= =20 >>> doable; circuit and message sizes should grow linearly with the WOTS ch= ain=20 >>> depth. >>> >>> Curious to hear thoughts on whether N/N MPC with hash-based sigs is=20 >>> worth prototyping, and what overhead targets would make it compelling= =20 >>> versus plain multisig. >>> >>> Best, >>> Boris >>> >>> On Monday, December 8, 2025 at 5:47:49=E2=80=AFPM UTC-3 Mikhail Kudinov= wrote: >>> >>> Hi everyone, >>> >>> We'd like to share our analysis of post-quantum options for Bitcoin,=20 >>> focusing specifically on hash-based schemes. The Bitcoin community has= =20 >>> already discussed SPHINCS+ adoption in previous mailing list threads. W= e=20 >>> also looked at this option. A detailed technical report exploring these= =20 >>> schemes, parameter selections, security analysis, and implementation=20 >>> considerations is available at https://eprint.iacr.org/2025/2203.pdf.= =20 >>> This report can also serve as a gentle introduction into hash-based=20 >>> schemes, covering the recent optimization techniques. The scripts that= =20 >>> support this report are available at=20 >>> 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= =20 >>> for several reasons. They rely solely on the security of hash functions= =20 >>> (Bitcoin already depends on the collision resistance of SHA-256) and ar= e=20 >>> conceptually simple. Moreover, these schemes have undergone extensive= =20 >>> cryptanalysis during the NIST post-quantum standardization process, add= ing=20 >>> confidence in their robustness. >>> >>> One of the biggest drawbacks is the signature sizes. Standard SPHINCS+= =20 >>> signatures are almost 8KB. An important observation is that SPHINCS+ is= =20 >>> designed to support up to 2^64 signatures. We argue that this bound can= be=20 >>> set lower for Bitcoin use-cases. Moreover, there are several different= =20 >>> optimizations (like WOTS+C, FORS+C, PORS+FP) to the standard SPHINCS+= =20 >>> scheme, that can reduce the signature size even more.=20 >>> For example, with these optimizations and a bound on 2^40 signatures we= =20 >>> can get signatures of size 4036 bytes. For 2^30 signatures, we can achi= eve=20 >>> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the sig= ning=20 >>> time reasonable.=20 >>> >>> We should not forget that for Bitcoin, it is important that the size of= =20 >>> the public key plus the size of the signature remains small. Hash-based= =20 >>> schemes have one of the smallest sizes of public keys, which can be aro= und=20 >>> 256 bits. For comparison, ML-DSA pk+sig size is at least 3732 bytes. >>> >>> Verification cost per byte is comparable to current Schnorr signatures,= =20 >>> alleviating concerns about blockchain validation overhead.=20 >>> >>> As for security targets, we argue that NIST Level 1 (128-bit security)= =20 >>> provides sufficient protection. Quantum attacks require not just O(2^64= )=20 >>> operations but approximately 2^78 Toffoli depth operations in practice,= =20 >>> with limited parallelization benefits. >>> >>> One of the key design decisions for Bitcoin is whether to rely=20 >>> exclusively on stateless schemes (where the secret key need not be upda= ted=20 >>> for each signature) or whether stateful schemes could be viable. Statef= ul=20 >>> schemes introduce operational complexity in key management but can offe= r=20 >>> better performance. >>> >>> We explored the possibilities of using hash-based schemes with=20 >>> Hierarchical Deterministic Wallets. The public child key derivation doe= s=20 >>> not seem to be efficiently achievable. The hardened derivation is natur= ally=20 >>> possible for hash-based schemes.=20 >>> >>> If we look at multi/distributed/threshold-signatures, we find that=20 >>> current approaches either don't give much gains compared to plain usage= of=20 >>> multiple signatures, or require a trusted dealer, which drastically lim= its=20 >>> the use-cases.=20 >>> >>> We welcome community feedback on this approach and hope to contribute t= o=20 >>> the broader discourse on ensuring Bitcoin's long-term security in the= =20 >>> post-quantum era. In particular, we are interested in your thoughts on = the=20 >>> following questions: >>> 1) What are the concrete performance requirements across various=20 >>> hardware, including low-power devices? >>> 2) Should multiple schemes with different signature limits be=20 >>> standardized? >>> 3) Is there value in supporting stateful schemes alongside stateless=20 >>> ones? >>> >>> Best regards, >>> Mikhail Kudinov and Jonas Nick >>> Blockstream Research >>> >>> --=20 >>> You received this message because you are subscribed to the Google=20 >>> Groups "Bitcoin Development Mailing List" group. >>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>> an email to bitcoindev+...@googlegroups.com. >>> To view this discussion visit=20 >>> https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e9= 03b321a977n%40googlegroups.com=20 >>> >>> . >>> >> --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 018ee35e-af3d-49d8-a8f2-5c478e681efan%40googlegroups.com. ------=_Part_245053_463662434.1765325687128 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Mike,

> You did a really nice job, I was wonderi= ng if it will be hard to add the different modifications to your implementa= tions?

Thanks! It shouldn't be too hard. I alre= ady have some Rust code for SPHINCS-alpha and SPHINCS+C on my experimental = testing implementation:=C2=A0

-=C2=A0https://git= hub.com/conduition/slh-experiments/compare/main...sphincs%2Bc
-= =C2=A0https://github.com/conduition/slh-experiments/compare/main...balanced=

For SLHVK, I'd add one extra shader at the 2nd-to-la= st 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 c= orrectly that if the user signs with the hash-based scheme, then the user w= ould reveal that the different pub keys are linked?

E= xactly right, since every child address would contain the same SLH-DSA pubk= ey. To maximize privacy with SLH-DSA, you'd need to use hardened derivation= to derive different child SLH-DSA keys for each address.

<= /div>
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 tim= e 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 toget= her 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. H= owever personally I expect that'd only be necessary in an emergency where M= L-DSA is broken and is no longer safe to spend with.=C2=A0

=
> I think it is true, that limiting the number of signatures = is the main optimisation we should look at. But if we use different paramet= ers sets don=E2=80=99t we already loose the compatiability with the standar= dized schemes? And if we already deviate from the standards, why don=E2=80= =99t add the modifications that can save us extra couple of hundred bytes. = >From the implementation complexity, of course this is subjective, but I thi= nk these modifications are pretty straight forward.=C2=A0

<= /div>
There are two different levels of "compatibility": The algorithms= , and the parameters. If we change both, then we're really not using SLH-DS= A at all; we're using some variant of SPHINCS+. We lose compatibility with = all current and future hardware and software built for SLH-DSA.
<= br />
If we change only the parameters of=C2=A0FIPS-205, but keep t= he same algorithms, then sure, some software will not be compatible, but ch= anging a few constants is much=C2=A0easier than rewriting algorithms= . Most SLH-DSA implementations are written to support different parameter s= ets, so extending code to support Bitcoin's parameter set(s) would be easy.= =C2=A0=C2=A0

It'd also be attractive to do so. I= f Bitcoin's SLH-DSA implementation adopts a new set of parameters, then exi= sting/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 forki= ng, or dedicated implementations. HSMs set up for SLH-DSA firmware signing = could be repurposed as high-security bitcoin signing devices; Open source a= uthors could broaden the impact of their libraries; All by changing less th= an 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
<= div dir=3D"auto" class=3D"gmail_attr">On Tuesday, December 9, 2025 at 6:17:= 10=E2=80=AFPM 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= ?=C2=A0

As for= lattice-based schemes and other assumptions, we also thought about investi= gations the possibilities there.=C2=A0

With t= his 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 thin= k it is true, that limiting the number of signatures is the main optimisati= on we should look at. But if we use different parameters sets don=E2=80=99t= we already loose the compatiability with the standardized schemes? And if = we already deviate from the standards, why don=E2=80=99t add the modificati= ons 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.=C2=A0

Best,<= /span>

Mike



=D0=A1=D1=80, 10 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0= =B3. =D0=B2 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 accoun= t. 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 scale= s with block size. At the same time, I believe it is still important to hig= hlight 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: i= f 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 ver= ification costs?


On stateful vs. stateless security:

Regarding your comment, =E2=80=9CI 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 ma= terial),=E2=80=9D I did not fully grasp your argument. Could you please ela= borate?


On combining threshold Schnorr with a PQ scheme:

You mentioned that =E2=80=9Cthere may be advantages to using a threshold= Schnorr in series with a single PQ scheme.=E2=80=9D My current thinking is= that such constructions could already be implemented at the scripting laye= r; in that sense, users could assemble them without additional opcodes (bey= ond the PQ signature opcode itself). While I see the potential benefits, I= =C2=A0 am also worried that such an approach risks introducing loosely-defi= ned security models, which can lead to vulnerabilities.


Best,

Mike



=D0=92=D1=82, 9 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0=B3= . =D0=B2 19:20, Boris Nagaev <bna...@gmail.com>:
Hi=C2=A0Mikhail,=C2=A0Jonas=C2=A0a= nd all!

> If we look at multi/distri= buted/threshold-signatures, we find that=20 current approaches either don't give much gains compared to plain usage= =20 of multiple signatures, or require a trusted dealer, which drastically=20 limits the use-cases.

I think there's room to= explore N/N Multiparty computation (MPC) for hash-based signatures. In pri= nciple you can secret-share the seed and run MPC to (a) derive the pubkey a= nd (b) do the per-signature WOTS/FORS work, so the chain sees a single norm= al 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 compress= ed 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 Sc= hnorr), so generic MPC is heavy, but it could be interesting to quantify th= e overhead versus just collecting N independent signatures.

As a sma= ll reference point, here's a two-party SHA-256 MPC demo I recently wrot= e (not PQ-safe, EC-based oblivious transfer, semi-honest): https:/= /github.com/markkurossi/mpc/tree/master/sha2pc . The protocol moves abo= ut 700 KB of messages and completes in three rounds while privately computi= ng SHA256(XOR(a, b)) for two 32-byte inputs. The two-party restriction, qua= ntum-vulnerable OT, and semi-honest model could all be upgraded, but it sho= ws the shape of the protocol.

With a malicious-secure upg= rade and PQ OT, sha2pc would already be enough for plain Lamport signatures= by repeating it 256x2 times. For WOTS-like signatures you'd need anoth= er 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 gro= w linearly with the WOTS chain depth.

Curious to hear thought= s on whether N/N MPC with hash-based sigs is worth prototyping, and what ov= erhead targets would make it compelling versus plain multisig.
Best,
Boris

On Monday, December 8, 2025 at 5:47:49=E2=80=AFPM UTC-3 Mikhail Kudinov = wrote:
Hi everyone,

We'd li= ke to share our analysis of post-quantum options for Bitcoin, focusing spec= ifically 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 sel= ections, security analysis, and implementation considerations is available = at https://eprint.iacr.o= rg/2025/2203.pdf. This report can also serve as a gentle introduction i= nto hash-based schemes, covering the recent optimization techniques. The sc= ripts that support this report are available at https://git= hub.com/BlockstreamResearch/SPHINCS-Parameters .
Below, we give a qu= ick summary of our findings.

We find hash-based signatures to be a c= ompelling post-quantum solution for several reasons. They rely solely on th= e security of hash functions (Bitcoin already depends on the collision resi= stance of SHA-256) and are conceptually simple. Moreover, these schemes hav= e undergone extensive cryptanalysis during the NIST post-quantum standardiz= ation process, adding confidence in their robustness.

One of the big= gest drawbacks is the signature sizes. Standard SPHINCS+ signatures are alm= ost 8KB. An important observation is that SPHINCS+ is designed to support u= p 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 si= gnature size even more.
For example, with these optimizations and a bou= nd on 2^40 signatures we can get signatures of size 4036 bytes. For 2^30 si= gnatures, we can achieve 3440 bytes, and for 2^20, one can get 3128 bytes, = while keeping the signing time reasonable.

We should not forget tha= t for Bitcoin, it is important that the size of the public key plus the siz= e of the signature remains small. Hash-based schemes have one of the smalle= st sizes of public keys, which can be around 256 bits. For comparison, ML-D= SA pk+sig size is at least 3732 bytes.

Verification cost per byte is= comparable to current Schnorr signatures, alleviating concerns about block= chain validation overhead.

As for security targets, we argue that N= IST Level 1 (128-bit security) provides sufficient protection. Quantum atta= cks require not just O(2^64) operations but approximately 2^78 Toffoli dept= h 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 signat= ure) or whether stateful schemes could be viable. Stateful schemes introduc= e operational complexity in key management but can offer better performance= .

We explored the possibilities of using hash-based schemes with Hie= rarchical Deterministic Wallets. The public child key derivation does not s= eem to be efficiently achievable. The hardened derivation is naturally poss= ible for hash-based schemes.

If we look at multi/distributed/thresh= old-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 communit= y 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 p= articular, 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 state= ful schemes alongside stateless ones?

Best regards,
Mikhail Kudin= ov and Jonas Nick
Blockstream Research

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+...@googlegro= ups.com.
To view this discussion visit https= ://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a97= 7n%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/018ee35e-af3d-49d8-a8f2-5c478e681efan%40googlegroups.com.
------=_Part_245053_463662434.1765325687128-- ------=_Part_245052_1565323084.1765325687128--