From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 16:56:17 -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 1vT8V5-0005KU-Hv for bitcoindev@gnusha.org; Tue, 09 Dec 2025 16:56:16 -0800 Received: by mail-oo1-f63.google.com with SMTP id 006d021491bc7-656ed76017asf583047eaf.1 for ; Tue, 09 Dec 2025 16:56:15 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1765328169; cv=pass; d=google.com; s=arc-20240605; b=jAiMquqnbo+A1uoBM0oLv6dUoSKkEi0zsEwsVxo8eKTZaeNBjjXgHHDHSHoXj5i6a+ e4D7Ompjh53NlvkjrR0GqAm/JnWsOOnqyZUNgSg2LV/8jrkrIz0O5btK7QfWLFOJ1JUS Wrh98aTuLHaBAiO73eI6CAKuR6Rb6gh6t1yz/2UFAUVT+qA0xTJFILYxMzrpKL2TIwov GKJIYsE/LcnMrBd7Xu/yUbXZoyGSfIP0YzHdw3G/EIcZt0hLzReM6NsPsdow3OhQQdlt F7fdJ+YiSRaCaz2MRb1Z//P7JXMW6PtiyU5o00IIlyHRXR+1D/Tnih1j/6Y3JcXjnL29 Fhxw== 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:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=yx5F4kySfzRQe10gFGOBrkwpxBniUflvOp89T9H31uM=; fh=3W7kllA+sqdRjcU9PuAvJxppHfGZPyVexTLxj118ddI=; b=ICEp0s7zveNe3uGGQ71Unw2CXF/+bOCORSEXsZPF6fyHmK3clnaYN3t60UCxEbol/t UPBQoUubQC3rLOr9HDQNYfr26CqF0Q5Yd1AdxjDoLqLj9v4zNr3+j77WGrWNUwbUxqNN q0tdL583H2pw6pe6n/dC2k9XrOtRvBTVUIl+baigDU2z/r2vGSfKbPXd7qCaLDOO9fGJ XdeRV+e4QxMsW2cXHxx0MEaY+uQVZkHuy3atHMKqEZ5rzZzii3WG03cgtr9PVRUz4UF4 ymQb60gBEqAkyautfmZenmZgxs1ARWC+biqg7zojLUisd8klnOc6ycXZLryqf3Y6Vc1j y7GQ==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=d4X26niy; spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::1134 as permitted sender) smtp.mailfrom=laolu32@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1765328169; x=1765932969; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=yx5F4kySfzRQe10gFGOBrkwpxBniUflvOp89T9H31uM=; b=ay9h1rXsSM7RtBOILUurXikPYzRpjX4z63hBbF2nP3RALF7pkxNOiu8fEEmAER9K2e OBz5PKwA55+UtH8g8cYWR0LflsS8dyP46/qrPcunzvGnBZdKxYeF25xI+j79frFtb82P oIhmTdZ+Qz5egjp3hnbPNXJTqYHynzhUVMlIeUVC55GUvGbzQY86omqmm01R0b8Y5Gvc M/4xcJerkrKdPtH/OpEBtSoOjJ/BXXvhmDK8Hdj5YrxtQODrrAD8fVCCAWoeUourZdz5 NqAKLWGuaZIycpDSdvA9laGjIGOUiYnC4SPkVKu75AxowhZoOPUBtPW4hSjMgKbi4UAv hbPg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765328169; x=1765932969; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence: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=yx5F4kySfzRQe10gFGOBrkwpxBniUflvOp89T9H31uM=; b=WpWP+JWt0UE6EJ8o1Eq99olPF0a8JZ0Y9MIgRPixVRgLvh8ljE2yA0V0Zg33bLWQZO 3W9yEreVjl67D5o18vrLX+XaWsRSmMGsyUGeeRQNQ58Z1ZUHWT1mmfgT9c6ADGSJV/Cf fBPiopVPhY+U60TJTAPt9ar0WJtVNQAOeOukH65CpiKj0QjSFgFR4HQHIU48PgSK/J2Z pyAMPWJN0GxIr9it/TXFETnGPXKWZyCBSdOA96OFLiNZsbJaUgDBPFa36EZ8oJ4q6+6s KDalltRlOVlpQ9z9EAmvgnN4equ0vbR4ZobZXwll0De1ZCJA+TrBGOnX+ElSWTa+uc2m RN/Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765328169; x=1765932969; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence: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 :sender:from:to:cc:subject:date:message-id:reply-to; bh=yx5F4kySfzRQe10gFGOBrkwpxBniUflvOp89T9H31uM=; b=YaqWc0FY7MQsQkT/ryJv0ez5bN4I7SD4IgHzVPtOA+K0Ghx3ncQzqOP8x//pgFss8W 3oxLbjFqJQyl3TD+zeREbKo7/i3m/0sFatq86S19Zk0K4g/EA8AYJXlnSPVFPQ4rLh3N UgwWOg9MqWznQWZJHjSXR8zWPq5AU7Ak1dCOiZG8THmXhU3/uR2INoUGxlZiTuG4V5+Y GO1oz/tWGudb0VYxidB8MoyGeeQitwmVxSG0KTEkxWuf77krszxEHWJZ2IwZGdFonwZu z/j/jZOUqrKvoP8JWlV0NWqsCrjOJUDjbD3Z7LiSzAvCb3f3NdMgKkfTMwFBsCyn/Qvl gVUA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCXLeFmVuHqJwbxV1EcV+TEAbDHgxaU4QgQyXBQPW6o8nSS1zyFzuDmoKmRk+BQ8PVwmUyPzs7TXI1qo@gnusha.org X-Gm-Message-State: AOJu0YxH5BXRl5ta37WRcGOqIMpb12Na3mD0sbUY1qkVFW5pjC2Iqea+ U20QUIs/kaMOea3ZoUqcUUVIcqEUxX8Zb7ero+r2rgFYolG9OISM+MUP X-Google-Smtp-Source: AGHT+IHYPTjQxrAEYzKr+lfCtQTyRQ8PN8CG5eOXkNBgYRBb5WTvj82t+VeeM70qsyGePum9ET6Row== X-Received: by 2002:a05:6820:150f:b0:65b:296e:a624 with SMTP id 006d021491bc7-65b2b1b5a60mr403644eaf.38.1765328169240; Tue, 09 Dec 2025 16:56:09 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWbKJTxd5lm0yePgqIDI8Yy5VfAnmNTeCOMeUCL9Kdt/+g==" Received: by 2002:a05:6871:d801:20b0:374:de90:136b with SMTP id 586e51a60fabf-3f5bbc482f1ls73076fac.2.-pod-prod-00-us-canary; Tue, 09 Dec 2025 16:56:05 -0800 (PST) X-Forwarded-Encrypted: i=2; AJvYcCW3x+iC0R5fbwr7wyB3JtkpOUATbEBNw4zuONxcnm0pe8irz0oJx85ClAXardpIUfl1GUfqfxJ1AVV/@googlegroups.com X-Received: by 2002:a05:6808:1507:b0:44f:8ccd:c489 with SMTP id 5614622812f47-455875ab320mr441238b6e.25.1765328165827; Tue, 09 Dec 2025 16:56:05 -0800 (PST) Received: by 2002:a05:6808:4a46:10b0:450:c180:fd79 with SMTP id 5614622812f47-4538890812cmsb6e; Tue, 9 Dec 2025 16:53:13 -0800 (PST) X-Forwarded-Encrypted: i=2; AJvYcCWKHoLPSZxy7NK1YI57Cj3gzssCI0DWJGEmbUJK+Cts0gKLOMUF2rC73MEMoNZUTM44ZhvHb/tYjUb1@googlegroups.com X-Received: by 2002:a05:6a20:7349:b0:34f:66ca:60aa with SMTP id adf61e73a8af0-366d8a48ed5mr640841637.6.1765327992119; Tue, 09 Dec 2025 16:53:12 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1765327992; cv=none; d=google.com; s=arc-20240605; b=arUHTAZ4bJcWczsiJ7ot+BD97RVzTHom2sUiHDl49KlwRHyZn/PgHtEf3KzwqkM1S7 K6gEAYmYT4Zv1nt7Bt4+yyehlI04dDEAtcebbtlz+/bVYbq4c5zEuIFWn1njZLceppBA tibmPSNmGUslr6rT3lAWXbfgor2vb+nqVai3y7gEzyiR5CqWIEQENq/nNm/cpsXuqop2 gEubaO3sZ5iiTO82DDqF/z31LKu+HLLHvK0eYqxjlWZhwAwjwcwhvxL79mACg9zSnr6v NQJle0oEf/dgBYXEaAPR/Ez5wntajtuV6zs8ljMUYsDgDXExIrY0jNiov/lL04VVUdqb EcBw== 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=9G0WlVgx3zNYowc9LWd2a92E5XJKLymyWCzOYhh0yKo=; fh=1FwwWdAY/PjXsI+hT1vE/UYfLqgE5UsQQM4UEmmUDK8=; b=CFBoskhK+l499/MY3yJNKUhBtsPZMZvyXATQ5i9XgMpKu1JZbV/6texd/7KexoYcmX +Z8c3SBExohM+GMKi4TylQxWkZl/txK7r7te83smkmJKedK0upJ5rhDajYN+++dDcPil BQGYGdsa2DwZEK5kDMc5VigEfdcMRw45rUrnyn0eNaJbYqECsUqzJbkYYAfNzkSeB5vD +tU6vLCeZLDMHT9k35yHnLaCZwMwZ2EDYecjBM/5uBqY+jUpQu9ctTCPd+Aaz4J4Zbfb abd04vFguJ9fJo9oJKBV05xM04s6Wdjl5bYV+r8CmA0YjcBPXambvKEMiYUWCYb+CmhS jAvg==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=d4X26niy; spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::1134 as permitted sender) smtp.mailfrom=laolu32@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-yw1-x1134.google.com (mail-yw1-x1134.google.com. [2607:f8b0:4864:20::1134]) by gmr-mx.google.com with ESMTPS id 98e67ed59e1d1-34a6fef7787si9382a91.2.2025.12.09.16.53.12 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 09 Dec 2025 16:53:12 -0800 (PST) Received-SPF: pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::1134 as permitted sender) client-ip=2607:f8b0:4864:20::1134; Received: by mail-yw1-x1134.google.com with SMTP id 00721157ae682-787eb2d8663so5956117b3.0 for ; Tue, 09 Dec 2025 16:53:12 -0800 (PST) X-Forwarded-Encrypted: i=1; AJvYcCVw9Q/l3OzGsDcf2S/7oh/w0SjOJ0zxRsIjEAEzjhhobmFs50IRBQoGL8KjIgrD8WYkqGCA/5Ny2uw6@googlegroups.com X-Gm-Gg: AY/fxX7396IEKqW6/1NuTj47q8Ekc2rVVnVYqOdbk6eqIxhljzIw2d9gPGWas39eHtj 7Gu4rgJq5/4MPbjV63aDZnqUSimY1PQhUSzMorPbucM2onsu+rtOwWeX0TTuUhAbl9wRMB7gTjT oH5II+Fsw93DzLcDpjKp2ywzDW3fyMn+S+VXJXuj/Ms5LaFQj+W0Qyp40q1BzSZNSW819HcML1H /3tSQ5M2PoOiAaPFx6RLy9kJ3rmD4iFlgZpvUqEQXgpgjXlVTzTmSMAJwjOetwjn3R5kAzo2wKX rwdEoMfbwkbSQsJ3TauaV9GAKnJ9yHpY3WDYOos= X-Received: by 2002:a05:690c:9a10:b0:787:badd:4f with SMTP id 00721157ae682-78c607759fcmr28799057b3.17.1765327991126; Tue, 09 Dec 2025 16:53:11 -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: Olaoluwa Osuntokun Date: Tue, 9 Dec 2025 16:53:00 -0800 X-Gm-Features: AQt7F2rvSqTLS8EVF_6WLdPfLA5OzFu87OJ-dBtozkHfnteOoaK-tJBjFABy1FM Message-ID: Subject: Re: [bitcoindev] Re: Hash-Based Signatures for Bitcoin's Post-Quantum Future To: Mikhail Kudinov Cc: Boris Nagaev , Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000d2bfc406458e7330" X-Original-Sender: laolu32@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=d4X26niy; spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::1134 as permitted sender) smtp.mailfrom=laolu32@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.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 (/) --000000000000d2bfc406458e7330 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi y'all, Mike wrote: > But if we use different parameters sets don=E2=80=99t we already loose th= e > compatiability with the standardized schemes? IIUC, these smaller SPHINCS+ parameters are under active consideration by NIST [1]. On slide 3 of a recent talk [2] at the 6th PQC Standardization Conference [3], Quynh Dang states: > We plan to standardize 2^24-signature limit rls128cs1, rls192cs1, rls256cs1 But then later in the same slide that: > We don=E2=80=99t plan to standardize them now: > Lower limits come with higher security risks when misuse happens > Minimize the number of parameter sets In the linked forum post the OP advocates for a swifter standardization process for the new params: > We believe all options should be standardized as soon as possible. To mee= t > the 2030=E2=80=932035 targets for post-quantum=E2=80=93only deployments, = development must > be finalized very soon. Roots of trust typically have lifetimes exceeding > a decade, and any further delay could make it impossible to adopt these > new options. So it appears they do plan to standardize these additional parameter sets, but it won't be done "soon"? -- Laolu [1]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/x-eaz9be6_U [2]: https://csrc.nist.gov/csrc/media/presentations/2025/sphincs-smaller-paramet= er-sets/sphincs-dang_2.2.pdf [3]: https://csrc.nist.gov/Events/2025/6th-pqc-standardization-conference On Tue, Dec 9, 2025 at 3:17=E2=80=AFPM 'Mikhail Kudinov' via Bitcoin Develo= pment Mailing List wrote: > Dear Conduition, > > You did a really nice job, I was wondering if it will be hard to add the > different modifications to your implementations? > > 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 >>> >>> . >>> >> -- > 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/CAPcK4uRf0hBNNiQUxLg1wWqJ2-P= -e4FrfyB0t6hsd96PfMOYcA%40mail.gmail.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/= CAO3Pvs8A0GLW-xdSHCKosjPqo7WSf-%3DYJ7F7s7t65RvtArcBEQ%40mail.gmail.com. --000000000000d2bfc406458e7330 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Hi= y'all,

Mike wrote:
> But if we use different parameters = sets don=E2=80=99t we already loose the
> compatiability with the sta= ndardized schemes?

IIUC, these smaller SPHINCS+ parameters are unde= r active consideration
by NIST [1].

On slide 3 of a recent talk [= 2] at the 6th PQC Standardization Conference
[3], Quynh Dang states:
=
> We plan to standardize 2^24-signature limit rls128cs1, rls192cs1, = rls256cs1

But then later in the same slide that:
> We don=E2= =80=99t plan to standardize them now:
> Lower limits come with highe= r security risks when misuse happens
> Minimize the number of paramet= er sets

In the linked forum post the OP advocates for a swifter stan= dardization
process for the new params:

> We believe all opti= ons should be standardized as soon as possible. To meet
> the 2030=E2= =80=932035 targets for post-quantum=E2=80=93only deployments, development m= ust
> be finalized very soon. Roots of trust typically have lifetimes= exceeding
> a decade, and any further delay could make it impossible= to adopt these
> new options.

So it appears they do plan to s= tandardize these additional parameter sets,
but it won't be done &qu= ot;soon"?

-- Laolu

[1]: https://groups.google.com/a= /list.nist.gov/g/pqc-forum/c/x-eaz9be6_U

[2]: https://csrc.nist.gov/csrc/media/presentations/2025/= sphincs-smaller-parameter-sets/sphincs-dang_2.2.pdf

[3]: h= ttps://csrc.nist.gov/Events/2025/6th-pqc-standardization-conference
=

On Tue, Dec 9, 2025 at 3:17=E2=80= =AFPM 'Mikhail Kudinov' via Bitcoin Development Mailing List <bitcoindev@googlegroups.com> wrote:

Dear Conduition,

You did a really nice job, I was wondering if= it will be hard to add the different modifications to your implementations= ?=C2=A0

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

With t= his derivation technique you propose, am I understanding correctly that if = the user signs with the hash-based scheme, then the user would reveal that = the different pub keys are linked?

I thin= k it is true, that limiting the number of signatures is the main optimisati= on we should look at. But if we use different parameters sets don=E2=80=99t= we already loose the compatiability with the standardized schemes? And if = we already deviate from the standards, why don=E2=80=99t add the modificati= ons that can save us extra couple of hundred bytes. From the implementation= complexity, of course this is subjective, but I think these modifications = are pretty straight forward.=C2=A0

Best,<= /span>

Mike



=D0=A1=D1=80, 10 =D0=B4=D0=B5=D0=BA. 2025=E2=80=AF=D0= =B3. =D0=B2 09:48, Mikhail Kudinov <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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://= groups.google.com/d/msgid/bitcoindev/CAPcK4uRf0hBNNiQUxLg1wWqJ2-P-e4FrfyB0t= 6hsd96PfMOYcA%40mail.gmail.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/CAO3Pvs8A0GLW-xdSHCKosjPqo7WSf-%3DYJ7F7s7t65RvtArcBEQ%40ma= il.gmail.com.
--000000000000d2bfc406458e7330--