From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 15:17:17 -0800 Received: from mail-oi1-f184.google.com ([209.85.167.184]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vT6xI-0002Li-Jj for bitcoindev@gnusha.org; Tue, 09 Dec 2025 15:17:17 -0800 Received: by mail-oi1-f184.google.com with SMTP id 5614622812f47-45396d397e0sf3852493b6e.3 for ; Tue, 09 Dec 2025 15:17:16 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1765322230; cv=pass; d=google.com; s=arc-20240605; b=EufcwzPEwYpvfjvqeoSf2IuQVKvqZCsQzKR6auZw/8Feh9pZaj5G+cEzVscQHpJ80v +RiRSq+GV6UuNJLxZMuSQpdUKZELAiBvv64kyOVkcJFWLdSytHkBS3JYMMws857HECAO whLhq8NaVRXQZQrebTtfc/ikGB6w824FlBRXkPfd9+9BUGCg0XE2B3NrRcFe2Jl9hdJs IqlkLYu4x/MaQHTofB60zGpkn2vOM9LvZ63bbbB2fQqElSnu5qWNPwbltgeuWVYBsd1U Bd5VZIv1t6Z90F13eC2w6HzS7UMdWlg1JHw6NcUfKdpdYzOw7Gxt3AJIYvjNhU1Z1Hy2 JSPg== 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=P+A5C3vNTbmgudorUpyZEgHYYb9HFnZipFukXWqgV4o=; fh=/43l3eVpsbYu6JN1eEOFXwcqP8TYUxwHptKzeH5e8Oo=; b=clwBMIXhMok9sYSktC7wTaUFEP2gTdg1R3UVfQd8xFVUUNiUWp47ARrwFaWdDcKzxS E0Vbs9kdU/Xtx7MQdAReOCgsA0LVxwwNJ7dd1EK1pDYCfX5ETNSeW3CpFTy4E5sJS8P4 pBxV5NKw8rFWe15yfax2x9mEQAJPIuWYneGxTqVVXoSuAs8qHBGzQCMoXSpnxt8S5jCw 5pfWZC67ewrw1KCvW56KVpNvS90psG6Urbq76evP06M5Gx1sOo0HmWo1EW5YuZD6AB1J F29s65vlKVMyFTtgXEyKPedh3ZRUN4JaDrARrp2PBs1wbXzgkh47fWNX3hwhRgl8nVw8 IiBg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=BPd9JVy3; spf=pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::22d 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=1765322230; x=1765927030; 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=P+A5C3vNTbmgudorUpyZEgHYYb9HFnZipFukXWqgV4o=; b=WL4KThrZ8Gt1Gj3/zpIyXIBiLKPfhFTL4k8esF37GucVs5JQY8Fl8HftKhTg3rS6QA t2bAxeQDe/oafa2xyeOhkPjGn7Jzl9QW97t0SsL7Cc+qJn49o7f0CTsb7dhXAKL6A8S7 DS3b7dGvX1glwbDJcNfZ4luzZME4NpQLbqhOScfZIXihZj5Lfh3eUqGvD5uml9zyh8yi LruWZVea0lbuceezAv0gEkZDGS0pefzFAB2c8TyypDMPNEwXmdC2LLLIM1nvqH2IVv+o PGPbog4IZSqQ4F/WCoVuPwHsLef8Z0RLtLPnNJePTdP9I4hUL2D5imKBLxVOZIllkcur r7Jg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765322230; x=1765927030; 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=P+A5C3vNTbmgudorUpyZEgHYYb9HFnZipFukXWqgV4o=; b=Mzimc5HAY7sP34kkkQaFSWeTIBOamUBN3W6KRV5eYpMVVMFmIqINn92RP+1IUTE9nf ReYW1w6XrYt4Xgltieo53uqi4r49eUkhb4NB7DWC3RP0IoVJFiXbh3C1ZPX3vWEjT5rZ r8QBPUvl4oJQG5vDb1f2nr7wGzN93QIhgR0RSK8gWlPNuJTNe0xASRbJLajYsyJXYl1b q48vks+dDHH0CRlQMBdZpB5H8sWnTl+87pY6ovMZMOCmC5uJrgWHD3qQGz5ECrGUxu59 gfKLm0AfcQYF3qnajLytxZzIOOkd5yR2FfRudk3uZgIsCvJM4V6zOW2rTWJ84pIU2IBx DXEw== X-Forwarded-Encrypted: i=2; AJvYcCW7QrIR4qw+CYb2YcV3Sp9whd8WBJ1fsy8/S+d5Ifrie7dzoW95T9kXF3ZHSlw3AeMUyy8S3fO+so1V@gnusha.org X-Gm-Message-State: AOJu0Yw6KEAeCjJKdImwEpyMquYBXcPZe9U0N2LI4uiFir1/+s+WIM4a r8kbHCgRn6YloSsJorXAEfF91bGbshH6zovQa4BNZonBdJhV7bo4YLXP X-Google-Smtp-Source: AGHT+IH8E8zUnZ7GXcHBIL3twDZpZZUNJ32NjZbsEVTqouYHFVW9STZrFgieOkaz6jtiGcUtKs+9CQ== X-Received: by 2002:a05:6808:c29a:b0:44d:bdd1:a5ee with SMTP id 5614622812f47-4558652d96cmr312022b6e.62.1765322230549; Tue, 09 Dec 2025 15:17:10 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWYbiBGm2pE7vWSXHnmuCy81C5bxp9n9UDOUopG/xvVFvw==" Received: by 2002:a05:6871:81d3:20b0:3ec:5edf:7cfc with SMTP id 586e51a60fabf-3f508ff5903ls2577057fac.1.-pod-prod-04-us; Tue, 09 Dec 2025 15:17:06 -0800 (PST) X-Received: by 2002:a05:6808:6d84:b0:453:5926:945f with SMTP id 5614622812f47-455863bc613mr310361b6e.27.1765322226358; Tue, 09 Dec 2025 15:17:06 -0800 (PST) Received: by 2002:aa7:d4c9:0:b0:643:1f87:ab0e with SMTP id 4fb4d7f45d1cf-647be34e591msa12; Tue, 9 Dec 2025 15:06:36 -0800 (PST) X-Received: by 2002:a05:6402:50cf:b0:643:18c2:123b with SMTP id 4fb4d7f45d1cf-6496cb62cf2mr606410a12.3.1765321594548; Tue, 09 Dec 2025 15:06:34 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1765321594; cv=none; d=google.com; s=arc-20240605; b=WJZaSgnK/mijIUc/PUPrPMC58NQ1UfWbRjwGFEcCefPo2nbqixpRIYNXgUa6FpZFux cRNnnj6xeNbjMNGACG5Jd8iQN9f9e6Wa/uGbA4qZke2FmL8mh1gn8klf40zR9iVXFbpL UdT6FiuxWfkxLQHmquoLX1iwcjT/f7+/cst9pacezOVtzYGfKzUS7+/Ev8hiXzkXhxqQ QICF6W6GQh1L04GmIfjuRu/l9Zv/fFJRNSc8XuCp4CNkbYNYJ5SQOkIjRHZfsnBaBvIp GRdp/+yS1COrTUMrFt2XV7s+BfsLQ14/Oyhcqokh4a9VB/OdshGNSpcqJ84ARKSxcFf0 biwQ== 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=pwAdyqQB2P+zpemx8qMKPOp/uZETj2I1lnFpXjErOa8=; fh=6b1pLcW6tcZ6I7AhOCDpUTdU/HBZRb+DjIxd1ga4+Sc=; b=UkZDp34nhswtIwRT6jUQdDeHZkjC1+Vke3j0ebEivbR+pek3Esn0g/I/PR3NfIzAie wkyaGqEpHC0FkJWEhUnTAfqIjfkCfJTus7QZg0Smz0NIGZJ561/eiN5mG+IrNVLFwXgM TDTBjZVxyQf2jgdDd5cDyRF4q1VCWACRaqfwmvlBeY00QN2C92w9JhGvf2o2daiB4jHq GxlTP1oAbMHU7fPtjyY9F7zv9qRp4KUGPSgcl2VLHvnH8birsVQjqlAUj+7j/SU+1nZf s/g+7vHwmXvQdfEnIZLNrDEEdQvCZHdTFmMFLgS9GyGB/UkBlvIXukc6TpIO4nAP/BQY EEkA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@blockstream.com header.s=google header.b=BPd9JVy3; spf=pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::22d 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-lj1-x22d.google.com (mail-lj1-x22d.google.com. [2a00:1450:4864:20::22d]) by gmr-mx.google.com with ESMTPS id 4fb4d7f45d1cf-647b2c51979si263332a12.0.2025.12.09.15.06.34 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 09 Dec 2025 15:06:34 -0800 (PST) Received-SPF: pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::22d as permitted sender) client-ip=2a00:1450:4864:20::22d; Received: by mail-lj1-x22d.google.com with SMTP id 38308e7fff4ca-37baf2d159bso7238951fa.3 for ; Tue, 09 Dec 2025 15:06:34 -0800 (PST) X-Gm-Gg: ASbGncuDCs9SOrM0kWzQ0w9Qhsybr+HmqTJJGNRyDa1bc7cXqxgd6jjuu/E2o5vHEv5 xRuqENyyXr/Ry0Q/tQo2ZUn2jvkYJgCAIKGxr2lcsyiEkwdjBkbsePQKP++kD76mz9WiRB2WKUx MfHmDGW1n62tytMlyX4ZhKUmRP3avw1iVSQ7He3xOSUP17F8kFzAelPtcXej8O6b3CiFzzqplgW CbtFys7SCz75bsvKgjMKuoYud5lGqEZo5jCAGs5CO3yGo3q/mam+XEtBytSeg6K5M8Rp7I4 X-Received: by 2002:a05:6512:a96:b0:594:5607:3b1a with SMTP id 2adb3069b0e04-598ee46f9a9mr102448e87.0.1765321593573; Tue, 09 Dec 2025 15:06:33 -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 10:06:21 +1100 X-Gm-Features: AQt7F2o5A4FKmQ98Bs0a6Gs4tQOEjWu_OczK3pwdp0mg_UsKN3x_KYdI_3tZskA 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="0000000000007fe41406458cf699" 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=BPd9JVy3; spf=pass (google.com: domain of mkudinov@blockstream.com designates 2a00:1450:4864:20::22d 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 (-) --0000000000007fe41406458cf699 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 sch= emes? 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 these 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, Mik= hail 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 a= s > 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 f= or > 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 = 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 please= 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 s= uch > constructions could already be implemented at the scripting layer; in tha= t > sense, users could assemble them without additional opcodes (beyond the P= Q > 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, Bo= ris 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 limi= ts >> 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 ru= n >> 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 res= ult >> 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 >> 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-pa= rty >> 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 enoug= h >> 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; circ= uit >> 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 wort= h >> 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. 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 >> for 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, addi= ng >> 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 achie= ve >> 3440 bytes, and for 2^20, one can get 3128 bytes, while keeping the sign= ing >> 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 arou= nd >> 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 updat= ed >> for each signature) or whether stateful schemes could be viable. Statefu= l >> 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 natura= lly >> 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 limi= ts >> 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 t= he >> 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 one= s? >> >> Best regards, >> Mikhail Kudinov and Jonas Nick >> Blockstream Research >> >> -- >> You received this message because you are subscribed to the Google Group= s >> "Bitcoin Development Mailing List" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n >> email to bitcoindev+unsubscribe@googlegroups.com. >> To view this discussion visit >> https://groups.google.com/d/msgid/bitcoindev/492feee7-e0da-4d4d-bb7a-e90= 3b321a977n%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/= CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t6hsd96PfMOYcA%40mail.gmail.com. --0000000000007fe41406458cf699 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

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/CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t6hsd96PfMOYcA%40mail.g= mail.com.
--0000000000007fe41406458cf699--