From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 14:50:31 -0800 Received: from mail-oa1-f64.google.com ([209.85.160.64]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vT6XO-0001fV-5a for bitcoindev@gnusha.org; Tue, 09 Dec 2025 14:50:31 -0800 Received: by mail-oa1-f64.google.com with SMTP id 586e51a60fabf-3e890e6be00sf8299685fac.3 for ; Tue, 09 Dec 2025 14:50:29 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1765320624; cv=pass; d=google.com; s=arc-20240605; b=aUtBX/rFN3bB2WxXgmJJ/H7dHCO4oIYXsDAafpRpOiI97z3JA1P1QCWTy1T+Ad7wpn srSIUNz4rDEVoAoxsIT4H2X22MkEEaYH6U+JGYUIw76uHW2NpCSw+B1uZvqrdritdvcV yYU3fGLZo32X07dfAY0l+ReWrRI9oeTgiCAAez4aC6Co5rlHH9kW0/rk+4Y5eawyXm+l OCSCwKZ0Y8jIfk/R0wGRAS3nKQfmE6Kic+9eDynRrdZhclEuWX1+tjcZy5qROEQFd16e Z9I1G/SL6FV4hpb0+NkCwiJ/2DdtZJ6NDvJY9fss4nrkWnQtZxbKcxKWASs5rB3bQPUf SP/w== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:cc:to:subject:message-id :date:from:in-reply-to:references:mime-version:dkim-signature; bh=MrHWMDYS2wv75llXTOtAN8MU4TcxqHgrLVyjhs6LZnE=; fh=SHLGwVbeOE/Kt99bz9sMTzFRSYBi3UU09yAHdqsiyDQ=; b=ceg/BJ4YUBHdPKphFf9zSrK90Pn3DFI+ZYDc/TxeVOXCmfV4b75WMpuod47kJhEbcY zMSevmBPOZiMf32LKLcmIukSd/LdXYSSbWz02gteQs0LVwrENofCvTumcZJHfezmH7fU BsSZ6n2bNsfPZ9fwgIVMapGRvUZ/rZ680nKaR7cyN2bhzXNhDNzSaFtZaL2Bhm/pQNN9 hD+28IuYmqyfUB1BxUVKDEj0A9Gt0ZcYgBFie0FMWrlYvlYq0GW+rINDtjLHFxPQxnRf wP/+jcav2z00iJfgxhEcLw+O7NT1nOWY+QjOnq777W61RJ/dg29/7YLdbo0CjAK912Lt /TMg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=hxv1qMJ4; spf=pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::136 as permitted sender) smtp.mailfrom=mkudinov@blockstream.com; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=blockstream.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1765320624; x=1765925424; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:cc:to:subject :message-id:date:from:in-reply-to:references:mime-version:from:to:cc :subject:date:message-id:reply-to; bh=MrHWMDYS2wv75llXTOtAN8MU4TcxqHgrLVyjhs6LZnE=; b=wCxPyXvi9ecUcadJM4a1vzwaccR45jUiUylU6O63FfNt6Z1dKryQwikjnwDxSbQlbI uRh8HyO/mzInmMUyQy2VFljQGg9b7D3Aj4X7t253PxbXyUkw/PBAlZ/AzMtC5u7tzJ2a WbdmfQH0+d1bTzj/xtbuKy+mxnJVLeTR2dLfn3E7ZpFt9uZcakWpT6G+4VTaGmZflp1O OS7MTKUQzJccaMROA1Z3aqEMCztuD0z9NYnuP8fCxiGEMRHYstHrPxVVNALr1MEC/05m XzH5cvmqgN8xkB3g4F3h+8MQyxyxYtmkLyZh0oiMfd47R5sR1+BW6dPwWzYP4vT6JC82 W4dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765320624; x=1765925424; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to :x-original-authentication-results:x-original-sender:cc:to:subject :message-id:date:from:in-reply-to:references:mime-version:x-gm-gg :x-beenthere:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=MrHWMDYS2wv75llXTOtAN8MU4TcxqHgrLVyjhs6LZnE=; b=HZO+MvH237x+UlaAm+Aqz6ToQfkaJf4CvFadnYyvugYg2J+NMfFvdvuuBf23YYsu8R mOy9X9TvZ3berWUolop+FUoVSSl6+KML/knbT/jJUXH7s5qcr48kMpvDCuSZtAm9ETyU yWc9Rq/fFso62o5D8qXDEexjJuybVj6L4xw80RE9o4X04P3MBUUPgfQdJ+1AWRnGG6cS 2a1o7fhVC/WPz6awfOgk4xYmr3YF1tqIPqbw6skTbC9SO8kjeBLUn6RjnUx7lhnnWfpJ J4Q+5cTexfFQIjgUFUCt2Ob6oBbJSDoW5OAz4STDjEWsTbIcVajGwK3e8jKcYUTfjBxg DeVw== X-Forwarded-Encrypted: i=2; AJvYcCWy58RHWS7OLFb+HrFd4dwE87pd+K6Qcw1+FN02yFGj9vDqeWGjyHhGIwp9IeiECrbOKty0LFr+vCfy@gnusha.org X-Gm-Message-State: AOJu0YwzJp1Lsc6aCDIy0pPmDlwz9XP1dADyGA3rzhP35+UVdUrvL+1+ eY6T0GzDhJCgAsCXnZuYf++ozZfL+ZKJZNG/Pntlib01UBiPpIMkJRzC X-Google-Smtp-Source: AGHT+IGPQ30sE5AX7FRQxXuGOCj6RU7DjSnuNO/GT7krL1WBxv37hOvVA7e3OrEwPD13bxIb7lkdiQ== X-Received: by 2002:a05:6870:bb10:b0:3ec:3e53:aa36 with SMTP id 586e51a60fabf-3f5bdbd59e0mr368467fac.27.1765320623388; Tue, 09 Dec 2025 14:50:23 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWaNS5Zl8G4eXlG03zcznwzZ7yZsBrt0UUljIIOZaaoikA==" Received: by 2002:a05:6870:b621:b0:3e8:2785:9a19 with SMTP id 586e51a60fabf-3f508fe7b7els1280000fac.1.-pod-prod-08-us; Tue, 09 Dec 2025 14:50:19 -0800 (PST) X-Received: by 2002:a05:6808:1490:b0:437:dade:463f with SMTP id 5614622812f47-455866cd5d8mr295440b6e.34.1765320619191; Tue, 09 Dec 2025 14:50:19 -0800 (PST) Received: by 2002:a05:600c:181b:b0:471:13aa:415a with SMTP id 5b1f17b1804b1-47933ec5554ms5e9; Tue, 9 Dec 2025 14:49:11 -0800 (PST) X-Received: by 2002:a05:6000:2409:b0:42b:2e39:6d45 with SMTP id ffacd0b85a97d-42fa39d2258mr342098f8f.15.1765320549678; Tue, 09 Dec 2025 14:49:09 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1765320549; cv=none; d=google.com; s=arc-20240605; b=hCfrz96cAFdg/aS8a5WRlcNjzcgtcLEvkHrnnzaMd1/F0rotYMyf2XA4x5D2LiYpoS B8D+WaWxxD4SM8F2e6Mn1JnMuR7NORNzyvLpmhmFDMFP94Xx4zgUXYyNsEJGKZBd684t eBAHY1L0E4swcGjXNfPTZilTraQr2tR81mhEFntk+qrzwQSDYxAjb74/YSdaJBCgqHb6 DRnau7wNwGyHb6FxRT2KsHm9stb53Eplju9G6uJpdROuXU/cbSFohcS+Yt44a2MgC7rb SxsYH7nz9iFDnf2cBQBqFN7+IYpJXuOOGPkmWh9y21Kz5MBz3/ZKmGd5CztVnSPcVZ4G 86Tg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=kiUmPaF6hVMDPH+tDJx4SVLmVObFTqEePBdog7sVeo4=; fh=6b1pLcW6tcZ6I7AhOCDpUTdU/HBZRb+DjIxd1ga4+Sc=; b=ZibtHr527XoZFr6YzCMer6dxdmwUyuVdpnEeS3snDV2MseNuAplcjCWJgBxQAMlhPG Is4FL09JhiebZatYMgvtnqj+N5eRO1WNx4yY5KRx0+lJHyRwhcz5D27kwS+1FkVu9DQq m5tp9ckfGG/gInvkt5vTzwyNuksGFQ7vbxbQR3G7yZQBPGGMtN6u4ufFwb9l6+HqWj47 GE3FVzVYWTnmy7Ps9eJhkGP4crmbLewFNVf49scvLy5uftirlwSKotXLeHs/3XGTQvUv Tnu62V0mxHX1WAE1l7VA0q3JJBpp9R7QGcwSgHFvi3fe5WGGFJUi+f5koBNpn3foHFWM MJhw==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=hxv1qMJ4; spf=pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::136 as permitted sender) smtp.mailfrom=mkudinov@blockstream.com; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=blockstream.com; dara=pass header.i=@googlegroups.com Received: from mail-lf1-x136.google.com (mail-lf1-x136.google.com. [2a00:1450:4864:20::136]) by gmr-mx.google.com with ESMTPS id ffacd0b85a97d-42f7cbed3b2si295911f8f.4.2025.12.09.14.49.09 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 09 Dec 2025 14:49:09 -0800 (PST) Received-SPF: pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::136 as permitted sender) client-ip=2a00:1450:4864:20::136; Received: by mail-lf1-x136.google.com with SMTP id 2adb3069b0e04-598ea574e6eso127568e87.3 for ; Tue, 09 Dec 2025 14:49:09 -0800 (PST) X-Gm-Gg: ASbGnctiqfNhc2njgV3iMMqOjBsjs0ejNPJBhkBTIRMniQ9Q1+vKgYU0lbzb2MTmdwF a9Q6eW75mJoTzfErN7FKbiYQSaVY5NDLQx1Sk2v0fJJYIzpi0O8Hcm4CdowoE3vBhsbVj/7pzL9 SqDVP68CIFGA7EBC7D4NVf+04b7UytgF4Q5fjJNBiSqVNkaMNZQYhWo8hm/h+bA2U1vOlfm8R4O xLsxQ4tpyAaJWwYPd+a9F4MeJ2CGYi49Oq/suLhXdgKHJa32cRFP/kPbc9E1BZTdj08fVFe X-Received: by 2002:a05:6512:118a:b0:581:8db3:d5fe with SMTP id 2adb3069b0e04-598ee52f759mr96641e87.2.1765320548059; Tue, 09 Dec 2025 14:49:08 -0800 (PST) MIME-Version: 1.0 References: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com> <492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com> In-Reply-To: <492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com> From: "'Mikhail Kudinov' via Bitcoin Development Mailing List" Date: Wed, 10 Dec 2025 09:48:56 +1100 X-Gm-Features: AQt7F2outbwGSELQVTmwQCZdVUF834k7s5puazaQGC3FVdrBmrB08eLxuWQ9llo Message-ID: Subject: Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future To: Boris Nagaev Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="0000000000002e9b0506458cb8cb" X-Original-Sender: mkudinov@blockstream.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=hxv1qMJ4; spf=pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::136 as permitted sender) smtp.mailfrom=mkudinov@blockstream.com; dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=blockstream.com; dara=pass header.i=@googlegroups.com X-Original-From: Mikhail Kudinov Reply-To: Mikhail Kudinov 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 (-) --0000000000002e9b0506458cb8cb Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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, =E2=80=9CI think schemes with weakened stateless se= curity could be improved to ~full repeated-use security via statefulness (e.g., grinding the message to avoid revealing signatures that leak key material),=E2=80=9D I did not fully grasp your argument. Could you please e= laborate? On combining threshold Schnorr with a PQ scheme: You mentioned that =E2=80=9Cthere may be advantages to using a threshold Sc= hnorr in series with a single PQ scheme.=E2=80=9D 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 =D0=92=D1=82, 9 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0=B3. =D0=B2 19:20, Bori= s Nagaev : > 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 o= f > multiple signatures, or require a trusted dealer, which drastically limit= s > 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 resu= lt > 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 recentl= y > 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-par= ty > 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; circu= it > 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=E2=80=AFPM UTC-3 Mikhail Kudinov w= rote: > > 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 fo= r > 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, addin= g > 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 b= e > 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 achiev= e > 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the signi= ng > 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 aroun= d > 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 exclusivel= y > 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 natural= ly > possible for hash-based schemes. > > If we look at multi/distributed/threshold-signatures, we find that curren= t > approaches either don't give much gains compared to plain usage of multip= le > 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 th= e > 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 standardize= d? > 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-e903= b321a977n%40googlegroups.com > > . > --=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/= CAPcK4uQBvfWpNsOdOwW%2B%2BL_LgUxFH-9CvY7YFKb1b5OzJgJ_1A%40mail.gmail.com. --0000000000002e9b0506458cb8cb Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

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 <bnagaev@gmail.com>:
Hi=C2=A0Mikhail,=C2=A0Jonas=C2=A0and all!
<= div>
> If we look at multi/distributed/threshold-signature= s, 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.org/2025/2203.pdf. This report can als= o serve as a gentle introduction into hash-based schemes, covering the rece= nt optimization techniques. The scripts that support this report are availa= ble 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 solu= tion for several reasons. They rely solely on the security of hash function= s (Bitcoin already depends on the collision resistance of SHA-256) and are = conceptually simple. Moreover, these schemes have undergone extensive crypt= analysis during the NIST post-quantum standardization process, adding confi= dence in their robustness.

One of the biggest drawbacks is the signa= ture sizes. Standard SPHINCS+ signatures are almost 8KB. An important obser= vation is that SPHINCS+ is designed to support up to 2^64 signatures. We ar= gue 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 ca= n get signatures of size 4036 bytes. For 2^30 signatures, we can achieve 34= 40 bytes, and for 2^20, one can get 3128 bytes, while keeping the signing t= ime reasonable.

We should not forget that for Bitcoin, it is import= ant 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, wh= ich 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 Schn= orr signatures, alleviating concerns about blockchain validation overhead. =

As for security targets, we argue that NIST Level 1 (128-bit securi= ty) provides sufficient protection. Quantum attacks require not just O(2^64= ) operations but approximately 2^78 Toffoli depth operations in practice, w= ith limited parallelization benefits.

One of the key design decision= s for Bitcoin is whether to rely exclusively on stateless schemes (where th= e secret key need not be updated for each signature) or whether stateful sc= hemes could be viable. Stateful schemes introduce operational complexity in= key management but can offer better performance.

We explored the po= ssibilities of using hash-based schemes with Hierarchical Deterministic Wal= lets. The public child key derivation does not seem to be efficiently achie= vable. The hardened derivation is naturally possible for hash-based schemes= .

If we look at multi/distributed/threshold-signatures, we find tha= t current approaches either don't give much gains compared to plain usa= ge of multiple signatures, or require a trusted dealer, which drastically l= imits 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 intereste= d in your thoughts on the following questions:
1) What are the concrete = performance requirements across various hardware, including low-power devic= es?
2) Should multiple schemes with different signature limits be standa= rdized?
3) Is there value in supporting stateful schemes alongside state= less ones?

Best regards,
Mikhail Kudinov and Jonas Nick
Blocks= tream 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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.googl= e.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e903b321a977n%40googlegrou= ps.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/bitcoindev/CAPcK4uQBvfWpNsOdOwW%2B%2BL_LgUxFH-9CvY7YFKb1b5OzJgJ_1A%= 40mail.gmail.com.
--0000000000002e9b0506458cb8cb--