From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 00:20:33 -0800 Received: from mail-ot1-f60.google.com ([209.85.210.60]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vSsxT-0004wz-WE for bitcoindev@gnusha.org; Tue, 09 Dec 2025 00:20:32 -0800 Received: by mail-ot1-f60.google.com with SMTP id 46e09a7af769-7c6d4a76d9csf9609550a34.3 for ; Tue, 09 Dec 2025 00:20:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1765268425; x=1765873225; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=WUz2NVvDBr/oOMmScbeBfFjUKq0Lnd+B31NdJ0+Cfhc=; b=fUCMBoCFSd72YlxB92b5XlE4Sf0XmX11pMqV/e/Hx5QzJ5FP8HjJp1f6x3opkvkhIG DPvhpn9EDr9zOwZ5Uz91q2oFEXkCga7KKHH6sJxZ50v87DYT6ZsgK4EavfcVeR0HRyhD utRLNw0Hb8pp55gLI88Wje5NlfesEMsirykvHjQDGXQNpO7qsv54Toot0r5Gw4lWANJd MX2eD+HBZYVNpRRMhponVtq2IK4BlGtVlzHrwxJPIK8ERPOGwqY94j0Cjnw9G2Y8C0Ie gxWxCaj7cMl9NFkBdnZs7sbM6fVEzG2uXkgTB1a01EEsbYewjZHvs7t+tgJWxUW1kTGw cUew== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765268425; x=1765873225; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence: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=WUz2NVvDBr/oOMmScbeBfFjUKq0Lnd+B31NdJ0+Cfhc=; b=ELCMpLRx1nt8Rj571MYkE/OETmThjj0nah7fBxsCPhkIP2fCuY3hC5xkD9WJGEh9FL aAG8oZQdYHq1Dmc/tailp3yv6Uj2Q2h/KKv688ImZGw2ta1QvkCoD3j+zlRji5yyoabF POlM64aqjJAVrimzd4qz34qe8cNm0FbeoT6fsw8S36DGbj9ddRnCxJBSo5iOc/jZmX+/ DfdnHljmWx+vWxfRRfh86q11BMxFoFB+GjIhtJHDnw6kE/gOvw68KDmcYD1wzMXZnWA+ MJWU6yZEUnsCZCujHKj73Ab+sB4Q0rH4MK/mF7hSROu6GwU9TztnUZptcNsZkYlOqwUi ZtTQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765268425; x=1765873225; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=WUz2NVvDBr/oOMmScbeBfFjUKq0Lnd+B31NdJ0+Cfhc=; b=w1L37ui6pCJYIEMFV7oX0PQVt9BsZH+7ZQ78IWzLqKh31EG9KwCERJ+A5orC6kaNRv DIlSwmJdXI6ughRNunpih4ij+F7nVa/N9UveA4XFVg5p5beNgVTHAq5CUtg0vRcT5xvh 3wQVHrFqViLpJ+QMZ8krQZ+kTsOSgNsum1efn7BX6urEVaWsmyGJjfwvPi1FFAjqxqQZ DLysH0AXa1c2RUIbbRDU2WluTKdALle4s4rIbtZhDncFpmCs13lm3CtlH50z+3qn+/R2 i6+yTxOppZcg4uijdadGCepiEyoQonTthHOA42qdX+GeHg/cfNozKfUpCqoZjuehLr+y psTg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCUEXUbBzCQfDlhgvfYmxsa3yM5DrTXuF1kCGH5tW1m3AczNuCvsTUsOT1jCqXewYYwGx6uAXsBZH59P@gnusha.org X-Gm-Message-State: AOJu0YzO445d3DEKhUYJZr8w6bMrcYY19WAYkb8K2DWHgQ6ExHstWCCU J1fTzQTc2gDmqEl9vkHubvBKeUP0wN+cZFj8nNzviOKmekbRAKTStG+R X-Google-Smtp-Source: AGHT+IG/PnTa8V1t0q2FBkxfNwJ0l7JWlv/M9PpCCxuv5SzLepwNjafeIPx50nWnSB3A0LPb2z4q8w== X-Received: by 2002:a05:6820:138f:b0:659:9a49:8f93 with SMTP id 006d021491bc7-6599a8ad9a1mr4025157eaf.12.1765268425282; Tue, 09 Dec 2025 00:20:25 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWZSi8tvJCmBtkpwbPprHaB1daJ/J9lkXPr05uXM5+IpTA==" Received: by 2002:a05:6820:4dfb:b0:656:cf0d:b8f9 with SMTP id 006d021491bc7-6597d0eb658ls2939926eaf.2.-pod-prod-01-us; Tue, 09 Dec 2025 00:20:20 -0800 (PST) X-Received: by 2002:a05:6808:c257:b0:450:d8ef:d804 with SMTP id 5614622812f47-4539e06c063mr2776094b6e.39.1765268420341; Tue, 09 Dec 2025 00:20:20 -0800 (PST) Received: by 2002:a05:690c:768f:b0:786:8d90:70d8 with SMTP id 00721157ae682-78c23b93f22ms7b3; Tue, 9 Dec 2025 00:06:24 -0800 (PST) X-Received: by 2002:a05:690c:67c9:b0:787:e9bc:fad5 with SMTP id 00721157ae682-78c33c166afmr89341657b3.33.1765267583969; Tue, 09 Dec 2025 00:06:23 -0800 (PST) Date: Tue, 9 Dec 2025 00:06:23 -0800 (PST) From: Boris Nagaev To: Bitcoin Development Mailing List Message-Id: <492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com> In-Reply-To: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com> References: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com> Subject: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_758700_1509409264.1765267583329" X-Original-Sender: bnagaev@gmail.com 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: -0.5 (/) ------=_Part_758700_1509409264.1765267583329 Content-Type: multipart/alternative; boundary="----=_Part_758701_1753429275.1765267583329" ------=_Part_758701_1753429275.1765267583329 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 limits= =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 run= =20 MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS work,= =20 so the chain sees a single normal hash-based signature while it is a result= =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 by N= =20 times versus N separate signatures, but the cost is a heavy MPC protocol to= =20 derive the pubkey and to produce each signature. There's no linearity to=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 recently= =20 wrote (not PQ-safe, EC-based oblivious transfer, semi-honest):=20 https://github.com/markkurossi/mpc/tree/master/sha2pc . The protocol moves= =20 about 700 KB of messages and completes in three rounds while privately=20 computing SHA256(XOR(a, b)) for two 32-byte inputs. The two-party=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 enough= =20 for plain Lamport signatures by repeating it 256x2 times. For WOTS-like=20 signatures you'd need another circuit, but the same repo has tooling for=20 arbitrary circuits, and WOTS is just a hash chain, so it is doable; circuit= =20 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= =20 prototyping, and what overhead targets would make it compelling versus=20 plain multisig. Best, Boris On Monday, December 8, 2025 at 5:47:49=E2=80=AFPM UTC-3 Mikhail Kudinov wro= te: 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. We=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. This= =20 report can also serve as a gentle introduction into hash-based schemes,=20 covering the recent optimization techniques. The scripts that support this= =20 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 for= =20 several reasons. They rely solely on the security of hash functions=20 (Bitcoin already depends on the collision resistance of SHA-256) and are=20 conceptually simple. Moreover, these schemes have undergone extensive=20 cryptanalysis during the NIST post-quantum standardization process, adding= =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 can= =20 get signatures of size 4036 bytes. For 2^30 signatures, we can achieve 3440= =20 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing time= =20 reasonable.=20 We should not forget that for Bitcoin, it is important that the size of the= =20 public key plus the size of the signature remains small. Hash-based schemes= =20 have one of the smallest sizes of public keys, which can be around 256=20 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 exclusively= =20 on stateless schemes (where the secret key need not be updated for each=20 signature) or whether stateful schemes could be viable. Stateful schemes=20 introduce operational complexity in key management but can offer better=20 performance. We explored the possibilities of using hash-based schemes with Hierarchical= =20 Deterministic Wallets. The public child key derivation does not seem to be= =20 efficiently achievable. The hardened derivation is naturally possible for= =20 hash-based schemes.=20 If we look at multi/distributed/threshold-signatures, we find that current= =20 approaches either don't give much gains compared to plain usage of multiple= =20 signatures, or require a trusted dealer, which drastically limits the=20 use-cases.=20 We welcome community feedback on this approach and hope to contribute to=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 hardware,= =20 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 --=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/= 492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com. ------=_Part_758701_1753429275.1765267583329 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi=C2=A0Mikhail,=C2=A0Jonas=C2=A0and all!

<= /div>
> If we look at multi/distributed/threshold-signatures, we fin= d 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 e= xplore N/N Multiparty computation (MPC) for hash-based signatures. In princ= iple 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. T= he 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 ea= ch signature. There's no linearity to leverage (unlike MuSig-style Schnorr)= , so generic MPC is heavy, but it could be interesting to quantify the over= head 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/mar= kkurossi/mpc/tree/master/sha2pc . The protocol moves about 700 KB of messag= es 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 i= t 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 chai= n, 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 wo= uld make it compelling versus plain multisig.

Be= st,
Boris

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

We'd like = to share our analysis of post-quantum options for Bitcoin, focusing specifi= cally on hash-based schemes. The Bitcoin community has already discussed SP= HINCS+ adoption in previous mailing list threads. We also looked at this op= tion. A detailed technical report exploring these schemes, parameter select= ions, security analysis, and implementation considerations is available at = https://eprint.iacr.org/2025/2203.pdf. This report can also s= erve 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/SP= HINCS-Parameters .
Below, we give a quick summary of our findings.=

We find hash-based signatures to be a compelling post-quantum s= olution for several reasons. They rely solely on the security of hash funct= ions (Bitcoin already depends on the collision resistance of SHA-256) and a= re conceptually simple. Moreover, these schemes have undergone extensive cr= yptanalysis during the NIST post-quantum standardization process, adding co= nfidence in their robustness.

One of the biggest drawbacks is th= e signature sizes. Standard SPHINCS+ signatures are almost 8KB. An importan= t 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 mo= re.
For example, with these optimizations and a bound on 2^40 signatu= res we can get signatures of size 4036 bytes. For 2^30 signatures, we can a= chieve 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 signa= ture remains small. Hash-based schemes have one of the smallest sizes of pu= blic keys, which can be around 256 bits. For comparison, ML-DSA pk+sig size= is at least 3732 bytes.

Verification cost per byte is comparabl= e to current Schnorr signatures, alleviating concerns about blockchain vali= dation overhead.

As for security targets, we argue that NIST Le= vel 1 (128-bit security) provides sufficient protection. Quantum attacks re= quire not just O(2^64) operations but approximately 2^78 Toffoli depth oper= ations in practice, with limited parallelization benefits.

One o= f the key design decisions for Bitcoin is whether to rely exclusively on st= ateless schemes (where the secret key need not be updated for each signatur= e) or whether stateful schemes could be viable. Stateful schemes introduce = operational complexity in key management but can offer better performance.<= br />
We explored the possibilities of using hash-based schemes with H= ierarchical Deterministic Wallets. The public child key derivation does not= seem to be efficiently achievable. The hardened derivation is naturally po= ssible for hash-based schemes.

If we look at multi/distributed/= threshold-signatures, we find that current approaches either don't give muc= h gains compared to plain usage of multiple signatures, or require a truste= d dealer, which drastically limits the use-cases.

We welcome co= mmunity feedback on this approach and hope to contribute to the broader dis= course 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 hard= ware, including low-power devices?
2) Should multiple schemes with dif= ferent signature limits be standardized?
3) Is there value in supporti= ng 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 &= 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/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegroups.com.
------=_Part_758701_1753429275.1765267583329-- ------=_Part_758700_1509409264.1765267583329--