From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 16:10:44 -0800 Received: from mail-oo1-f63.google.com ([209.85.161.63]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vT7n1-0003to-2V for bitcoindev@gnusha.org; Tue, 09 Dec 2025 16:10:44 -0800 Received: by mail-oo1-f63.google.com with SMTP id 006d021491bc7-6574475208esf4065931eaf.3 for ; Tue, 09 Dec 2025 16:10:42 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1765325437; cv=pass; d=google.com; s=arc-20240605; b=DAp8tLAFAZWLG/PnQCa/mxS2dwkhv4zL68dhSEP5LS3iKgt0XSK1FC9vz/R6KJYp9o cZGxg7lMyBiGforh4jD5CjiaFPoRoVAJvY0jnCgitJkf4CxYOt++fZw0LQOnca7T22QQ bRvmeOsOLQu3DVpFBDSrMUsUkoaOpusY+zLD0pHjeaNxsw17GWkCNYzlGMrB+HFHhGE1 WnpFBve8SBANHn6y2hZNyAOooRPNPT1QLkwv2wgNUOO6c7ArjoWR/nm57ScNGynTjHHq 21XIUQOxFacNf1AoYjP2GU4MNQ/+HOFBKoyqVVE0p98dOYDqkLaH3AeEYMEFZPhFPh49 0bew== 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=0NuyXlJzEn964rSvNCut/fNVkA2U0opUJBthJsOBW+0=; fh=FzYRzpiUzN716zJGTtfFKqYZr1wCB7IRoEy1b6yOTA4=; b=X1O37Yib9QAOQvd6FmXSR5O+yagRB43+0Bh6loTwS1J7bGU4XnHQEDMF4wUzH9wRJo +JZelTP2/cg9b1wLWS76pnYeXY+ao7qvjUt0fGhO76SkWcj+sK3Gry3AD76st3/DFoEI V61wsr6MTZCSd2j5cSpvkZXrnRbqnpOTJmeWk6sOQpYF10GobD93HLgWatmBUyRjVa7s nmsZd+3C1YYqydoEgsheV0sX54pdleYPSA4/yKufUtnm1+r5Iwo9BG6+AaeiQGxtUwzS hRoBy3VXn+baAmIst80YIpkMdrkGBLKaRxKxqLKfrl8n+FUGR7hSXcEkU0R1neVWcRpe j9Ag==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=UIMCAeIn; 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=1765325437; x=1765930237; 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=0NuyXlJzEn964rSvNCut/fNVkA2U0opUJBthJsOBW+0=; b=bo0yaUyFN8Iyd64fo2Ts2QDV9eEk+6ru+ubnLExLdmbObPMSggdnRnlCdEb2d5kf4h lPriO/HjPqQfSLrpAAiovl6dMsRcXk8/wHSDWwskTsLmM6NrTbm6U2vfZ0T7gfyAhvQp Mmn11PXcSTKwWxpzXIOLvFgkKGBuPk2Fbg8FdFcw/B/vjYbhyIGabC6YOCuRsESG6NWJ NvtM+PS+9AlA9TaEY9S/olQKXr8fjbBr+zle3PKgmlpKc2zJztJV2mdBz/QfXNHxLCtT aPnNNVmhcB6mXcVZn6HuDrkbU1PczIXaoByeEAm4PirGbIcSa6mD5vM1AjBZXeqiYk35 b/Jw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765325437; x=1765930237; 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=0NuyXlJzEn964rSvNCut/fNVkA2U0opUJBthJsOBW+0=; b=Nw1KU+Ib+irXREYmEm35N+BSQQjaERMG1/2HYdlKHi8X73qZTeDLl8/LwcJ4zCuR4O JP9H6O1fqv7R5pLr69vljDAgbgjBW3on9Cggxtnm7B4MY0lR6A2ICVvzd9VzS8uBYEeM GXODpvyEyEU0rJ1wcboAVrJdjgyVuLDzVDfttqTp2PhMDWozuY8eD2benV2p1mhxeYXc GUxOFIPNF+w9h6sDiEOr/t36+BFcoROBCt6HZ6oEbdDmn6PdvSQF8GGjAWIk0yNLao9b d5oCusixwjMUWCnZ2Tkq6oRYNYIK8Xbz4eBc+73cAiorzkSPmKPpzROIYL7h84fnVrb7 huIA== X-Forwarded-Encrypted: i=2; AJvYcCV/BiCMtte70K2NcT1ySLEgVIEUcqvZjEm0Zem+nrcZZjYo5zH99qq4i5YSOh0U51pSKLw1z3joG2i1@gnusha.org X-Gm-Message-State: AOJu0YwEzfOiH8Tsuf8qD7iS9LgHaSvFuH3Dn3r9gnX+NFHFN0Q5LpjF t+Q+hrndirEuACX2Ly6PuQzkhhPLP+35N1vvI+3oIXPQA15mBhRzkL/6 X-Google-Smtp-Source: AGHT+IHOE0UArRhlq/d4q8MwDuH1Hz5eQUw2+7rFMVmGb+Tz35a/Pp5npJgWw5M+tjHbzL0bN45JgQ== X-Received: by 2002:a05:6820:f009:b0:659:9a49:90b6 with SMTP id 006d021491bc7-65b2ace5a11mr422855eaf.53.1765325436435; Tue, 09 Dec 2025 16:10:36 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWbO7xak8ZFdo9cxPq8AIWbtZt1jmfnviVmTxTMIf40NMA==" Received: by 2002:a05:6871:589:20b0:3f5:b4fb:c7a7 with SMTP id 586e51a60fabf-3f5b4fbd345ls245515fac.2.-pod-prod-02-us; Tue, 09 Dec 2025 16:10:31 -0800 (PST) X-Received: by 2002:a05:6808:c1b6:b0:450:12a9:3fd1 with SMTP id 5614622812f47-455863d65a4mr417694b6e.23.1765325431255; Tue, 09 Dec 2025 16:10:31 -0800 (PST) Received: by 2002:aa7:d4c9:0:b0:643:1f87:ab0e with SMTP id 4fb4d7f45d1cf-647be34e591msa12; Tue, 9 Dec 2025 16:01:39 -0800 (PST) X-Received: by 2002:a17:906:c14a:b0:b73:8cea:62b3 with SMTP id a640c23a62f3a-b7ce846cab9mr52129666b.41.1765324897335; Tue, 09 Dec 2025 16:01:37 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1765324897; cv=none; d=google.com; s=arc-20240605; b=GbDv0Md8Jriq1waej3v9Yp/09A/BNxtiqBAPx2+gCKuK6X8hw5eCIVh02zP2gY9NHw TvpKffylrNYe3hOT6mwfKGzdbLaeCSYOfivpsW6oDKqcnwfdzLdMkxjX3LKc+bCUhG1/ qeiyCwJRa+QqjYAZwox2ig2rivEBkM4PngdX2m+VKkctSLiIDrVzxbrxpY6GZeQnRUkr F2Jg65+o1EAfw3pBZZMumv91RP8AnPrlZ32VhgnqD7sXoQTskroIC1laJBv+d7nsgi93 u2zURRlFutzWGE2low/aCLKXMDezKPfJpNwfSS9Qj1Dq6n6b1S9oxxLRHz4DFV1tWIeu 6RZA== 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=l9bOztM05rfP+c3xnFlvO3TlGwKMT0bH8oocdMPOeoQ=; fh=6b1pLcW6tcZ6I7AhOCDpUTdU/HBZRb+DjIxd1ga4+Sc=; b=lJuv2hdvz3S8UYLpuUNzK29GE4OfPFNXiugefmGHHE69gBS8auW54fusv9aZQnBlML 5vHowr4ykpCo/TploMYrE5cithUPp/iz5q/5IOlrwKyENNfFUl+TYNdZg/XGtoo8NS3a zcWPFV9ZFUFDn9RyDQMqc/InbnYQdKsvlawDuV04rSpQgwV+1iF1K0pQxVMP1OS+E26n iiaaK7012qLgoAKnKOAM7gXKMcvhV+VJ4uh86UkjuRpx2kyV6ITYJ+2D8qpIf1EWmWxk 1ipNWjI5ElGWDNPPz8m+nmCQrrtC6HHB4JOAsyEtsWpSf2tDPoyuiLPVttr4OKU5Tquu 3d1A==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=UIMCAeIn; 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 4fb4d7f45d1cf-647b3169bc7si144389a12.5.2025.12.09.16.01.37 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 09 Dec 2025 16:01:37 -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-598e9f63169so157664e87.2 for ; Tue, 09 Dec 2025 16:01:37 -0800 (PST) X-Gm-Gg: ASbGncscO88ieMW6Xm43ymhya9aOoYO7pEwtAd1Lusl9DZU6ENWewqbLUKT/wMibamw 3Ltw8liFkqwdGxUNB+FBHur9ep9e0VwntCq77OEP83Zqd6GZIheMlQU+J7NB5M29DUarauJLG5+ WGKCIzL6kFbBhNNco7t4FnKEE4XYiX4w5BCzLfPmsj7JGfIF4PleyMdEedduCKSxzBWCS/94GUv qRbDDnoy/w96f8XndTVuXuhoKa1LGOl8pWTBoYMAAEYrbSQplWm495DEDOD/AhMghKQyOya X-Received: by 2002:a05:6512:a8b:b0:595:9d47:b464 with SMTP id 2adb3069b0e04-598ee536542mr123744e87.1.1765324896369; Tue, 09 Dec 2025 16:01:36 -0800 (PST) MIME-Version: 1.0 References: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com> <492feee7-e0da-4d4d-bb7a-e903b321a977n@googlegroups.com> In-Reply-To: From: "'Mikhail Kudinov' via Bitcoin Development Mailing List" Date: Wed, 10 Dec 2025 11:01:24 +1100 X-Gm-Features: AQt7F2o7EDvQsocJHIaxmktjOEo1vii-q448yXPksy0IeWSTIrFhdX7X9vh4qqk 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="0000000000005c8d3a06458dbba2" 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=UIMCAeIn; 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: -0.3 (/) --0000000000005c8d3a06458dbba2 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Dear Boris, We also explored general MPC approaches. We discuss this in Section 15.3, and it appears they are not suitable. We cite an estimate indicating that generating a SPHINCS+ signature via a general MPC would take around 85 minutes. Even if we scale down from SPHINCS+ to a much smaller number of signatures, the approach still does not seem efficient enough. For a single WOTS instance it might be feasible, but then the question becomes whether adopting a simple WOTS scheme is desirable at all. As mentioned above, stateful schemes already introduce significant complexity, and one-time signatures are even more restrictive. Best, Mike =D0=A1=D1=80, 10 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0=B3. =D0=B2 10:06, Mik= hail Kudinov : > 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=E2=80=99t we already loose the compatiability with the standardized s= chemes? > 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 think thes= e > modifications are pretty straight forward. > > 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 >> 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 scale= s >> 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 verificatio= n >> 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= security >> 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 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 >> 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 th= at >> 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, B= oris 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= of >>> multiple signatures, or require a trusted dealer, which drastically lim= its >>> 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 r= un >>> MPC to (a) derive the pubkey and (b) do the per-signature WOTS/FORS wor= k, >>> so the chain sees a single normal hash-based signature while it is a re= sult >>> 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 b= y N >>> times versus N separate signatures, but the cost is a heavy MPC protoco= l to >>> derive the pubkey and to produce each signature. There's no linearity t= o >>> 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-p= arty >>> 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 ch= ain >>> 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= 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. W= e >>> 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 ar= e >>> conceptually simple. Moreover, these schemes have undergone extensive >>> cryptanalysis during the NIST post-quantum standardization process, add= ing >>> 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 achi= eve >>> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the sig= ning >>> 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 aro= und >>> 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 upda= ted >>> for each signature) or whether stateful schemes could be viable. Statef= ul >>> schemes introduce operational complexity in key management but can offe= r >>> better performance. >>> >>> We explored the possibilities of using hash-based schemes with >>> Hierarchical Deterministic Wallets. The public child key derivation doe= s >>> not seem to be efficiently achievable. The hardened derivation is natur= ally >>> 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 lim= its >>> the use-cases. >>> >>> We welcome community feedback on this approach and hope to contribute t= o >>> 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+unsubscribe@googlegroups.com. >>> To view this discussion visit >>> https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e9= 03b321a977n%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/= CAPcK4uT99o15z04s772Cu4y7G9WNnVKvdNV0thv_FW129a9TSw%40mail.gmail.com. --0000000000005c8d3a06458dbba2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Dear Boris,

We also = explored general MPC approaches. We discuss this in Section 15.3, and it ap= pears they are not suitable. We cite an estimate indicating that generating= a SPHINCS+ signature via a general MPC would take around 85 minutes. Even = if we scale down from SPHINCS+ to a much smaller number of signatures, the = approach still does not seem efficient enough. For a single WOTS instance i= t might be feasible, but then the question becomes whether adopting a simpl= e WOTS scheme is desirable at all. As mentioned above, stateful schemes alr= eady introduce significant complexity, and one-time signatures are even mor= e restrictive.

= Best,

Mike

<= /div>



=D0=A1=D1=80, 10 = =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0=B3. =D0=B2 10:06, Mikhail Kudinov <= mkudinov@blockstream.com>= ;:

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 <mkudinov@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 <bnagaev@gmail.com>:
Hi=C2=A0Mikhail,=C2= =A0Jonas=C2=A0and 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= =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/ms= gid/bitcoindev/CAPcK4uT99o15z04s772Cu4y7G9WNnVKvdNV0thv_FW129a9TSw%40mail.g= mail.com.
--0000000000005c8d3a06458dbba2--