From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 09 Dec 2025 16:46:19 -0800 Received: from mail-oi1-f191.google.com ([209.85.167.191]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vT8LR-000527-EC for bitcoindev@gnusha.org; Tue, 09 Dec 2025 16:46:18 -0800 Received: by mail-oi1-f191.google.com with SMTP id 5614622812f47-45033344baesf13416329b6e.1 for ; Tue, 09 Dec 2025 16:46:17 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1765327571; cv=pass; d=google.com; s=arc-20240605; b=ersS3GZyPKJ0qwHf1EYcksFDtremVJ4YNbULUI4KO5zAsUSdEGn23HJa/x27OPzpzF f7caFO7TFwl0GmZubVwnXbY41gNiJQgQ0zoCns07UhHYc1N1VwtD7YjAFCibqwjRbCwt kd6rZno8uW8TW4p45qY3DvnjD/AxRQb/02Zp3W982jlxDQ8DnpY4UEL1JC03kli8YO2z UI8AYKMXpM/5ZEtCsBzzr8/Mem6lY9zIvQnTO4Wbcm5jBE3KqrDG/D6wW5SW3aROznXO qhVRN25TzoyL/hB28lE4TzczF8ZwSoLMUiLp146wGpoJEg+F2i5IVUWiEHX/FQzpBpM0 w0cA== 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=/j/qjmdcoWuCLDkKIaBp3TwnsK7hU1VZ2B4ibxRvo+Q=; fh=Vk3C8fTXfkPbB7Bk+W3Xf2FuwgmOcJ9l8BbZP1O3SFQ=; b=PSNT94HbWsSC3cu1PCihYkgg9fktBqZ7cmRGsTSx/lkqnEyMmZKKP/tHj4LaBNFolR gazLjkgNbAhYBM+0dpszbh5z3ALafQ4tEXDS2aEJonVRff7EaSwc2FiQBypu0OHZj7Vp pYRALWnBMIVUIFIEnnPaIQccwgCRI4SmGUA5r9QVHinuQxOUxxqfszprslP+hSSggVwO FG5zWUduNm/6HpEvn9nI25lkNS0wZkFD7ioVge+wfDKMSitzeru5iMfR4U3r8ZIuN2C7 v9N1iJo0iO9s3CMTWMDGwW1CUINLVXB0mHIGOHFVAjuYNhgrBDXxcv2nVfC04cTdlNGe W6rg==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=Rswaaeb7; spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::112c 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=1765327571; x=1765932371; 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=/j/qjmdcoWuCLDkKIaBp3TwnsK7hU1VZ2B4ibxRvo+Q=; b=hQDKIROW1ftnjL9MY/YFGeEYnrwZgTNJuNqNwJ8PAs2D1XhbnpaYxwaj1r6fDdw5Fn OphmP6BPIli9GbZ64balZDnyMW0gAxW0wiXcKEiSgP9EILn0kOakOHXtkcpQo21JeOEa npf7BJhscZoOW4IQxkBb9cFFKyHBkunt9XiifWELTT+OFnjEcPJiLt7nHkSPtPg1PnM6 8AXEUeXmtpJUDE4u7ffKVU7kLE9iDb8pKKWiffSp4W3SjAvsp3KWlGYLuOeyiWlugau3 ZqDiGz6LMqxxMJPJKiQVY1cvSpsxtb9a8K3KtJ+Ob/EiQLFNg3t4Ix0wzVm2ZyMuoQKP xbWg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1765327571; x=1765932371; 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=/j/qjmdcoWuCLDkKIaBp3TwnsK7hU1VZ2B4ibxRvo+Q=; b=L3SM7v3XgYaq+HjOvlDzmc1IAXaq6qFlD2s6oGzM7gv5/L/0ePFw9sJjZ7WBNPJ9IV YCsAZ8g/xKGFX73tMWCANaRL7Zqjn2S5meLqMxfok9ZVU372TJPpP15q+ZogBqBHOMiz xg3EVuELRqMi6cJXkzOmzpSE3xjaafxyGu83Vgf+VKWvYtRPZu4FmC9LuzfdaaX3WqCT OCwCtu7gcYDXCAqUGJ5bbhzw+E2GlDqS+nJ/XhryI+ki3Nv2cynWVC6+BixuOI1jPmEv RzL6dE2rHvmL/GmKDRpiSKDrSXBgdBYKj538BEQSjyDtKe4Sqweh4Qo5TtouMlzUGyMP m/5Q== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1765327571; x=1765932371; 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=/j/qjmdcoWuCLDkKIaBp3TwnsK7hU1VZ2B4ibxRvo+Q=; b=tpsFkXixqDNYYauxOQaqVWBAlAH8mCeTCFTh/F4KF1FEIESkKXVYz1qAbXRELgp6nK fc1acKqZNpHvVutndzTE3TFmgbTXoEMJPo2ImVMfUzOxOdi2iTroJMaBkASFi/xTfinf Bl/de3N9RBWcBHUs+Ti8mfrEBO1c0gq5nx+rkkPxWK7YATxG9QDGWByyVnmmpEjb+1ao AJOHUxoLM1k5WPipQgPGWHaehSVb3/Uk4A8oZnI8Po7VStmKmoYZL9kCoLEn3GG2z3Kd b4nMtVIk1t+PgClexHlWySDToUKdE3B4L5OmlF2LiTq8kXuqsZHFDIq+itDWKM3FBq8U xUHA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCVc/LE+B37eqxe10/sR+VE401jyr1+Ss9axnAXMCUaReYz1tP5dvKr3pYa1APWf7KSHT+okLVUY0P/3@gnusha.org X-Gm-Message-State: AOJu0YzbmkS8FeuX+RAyDuzmt6dKlvo69bf2kXe2k132nxXHQcTyZF1T S+UkqmJmZxvOEmpPN9PRXKLE+jWSOOpYrA5kAZeSz7WwqqIDXqder0ok X-Google-Smtp-Source: AGHT+IE6vOv8C2SkhmDhZDjDeGgKM99iViCqsV/khBrf2HBFl3QOKffDOMqYREyc1EJe9KPZQEixnw== X-Received: by 2002:a05:6820:4ded:b0:659:9a49:8f84 with SMTP id 006d021491bc7-65b2acf5d8fmr488073eaf.73.1765327571176; Tue, 09 Dec 2025 16:46:11 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AWVwgWYQVfhokPAROThYh0pjLPGg94tgLcwNISUuk38QR1obEQ==" Received: by 2002:a05:6820:4dfb:b0:656:cf0d:b8f9 with SMTP id 006d021491bc7-6597d0eb658ls3424856eaf.2.-pod-prod-01-us; Tue, 09 Dec 2025 16:46:07 -0800 (PST) X-Received: by 2002:a05:6808:c294:b0:44f:775b:729f with SMTP id 5614622812f47-4558660ccc0mr512359b6e.28.1765327567192; Tue, 09 Dec 2025 16:46:07 -0800 (PST) Received: by 2002:ae9:e10c:0:b0:892:e292:65ef with SMTP id af79cd13be357-8b64abc508cms85a; Tue, 9 Dec 2025 16:42:02 -0800 (PST) X-Received: by 2002:a05:620a:3196:b0:8a3:ee38:be9d with SMTP id af79cd13be357-8ba38c7d8f3mr157352985a.6.1765327321402; Tue, 09 Dec 2025 16:42:01 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1765327321; cv=none; d=google.com; s=arc-20240605; b=WFiWqzrYr13Bj2wRD2BLP55pfX85vmsZ87NiJGg9u3I93XsPXRl5SLEGfFadXkukRD 2TAW0aPDLdtnR+pFuIrPGv3O/KXt3gorfEGfZ2F+o/WcnbG/hA18bFYD64fZLcVMFK5D 35r+bqLT4G4f46BMvjnBR7t5myeLWoALFIUodHPIDtpEpFqnjIKxNEoQG6uslc+WCr4M g29jrMa5AoDuN9OB5dRtOYoq45mNswQILpJrujLeLL+OAw+WnhoDa2g5HaZABh/vYSSl V2UVKaHgaqz0dvwHam+1lgzQf1KNA2wjcDgnpac6YaE61Yn3tXjojzxvE6bXu/A2CVZt XHZQ== 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=7ovAPWpUzm9TVFVZuE/U0FXwDXriQ9yPfJuo4HsinrE=; fh=AraWG4EtKgnVZC3vx0kKXPCQKgjblcoyQOn27ZV865o=; b=jsXesWYRoy0DHBAUAn9vyoTnUA7eFmcvG+GeVLKkd0xxPpIZquiQLRJzoudUtjt5cz Sx4rSMSFuJr9Y4sEibWsGVwteex+hR9s9XGNvxair5MF1pvgi7k1J6Rf8+6dHaQNFy+u F6Q9hO/0POPWXQMafGYZCUscF6sYFCdGNmXPAg122TiBKBbnQCb55iVlRLtBRr9uFeF2 Bk7qcUhN9SnYPzGyceNbJphGpceUJudITAzSVTTB2bhuN9tzb1bdu/FOzxrR2M32g7JW 7CNWQLZMFEpFQcUIDVI3udwNVQYrITF9PMxDdlAaPHKcaev38ZbIMEYCf0eYrBqJ+b/w OGrw==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=Rswaaeb7; spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::112c 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-x112c.google.com (mail-yw1-x112c.google.com. [2607:f8b0:4864:20::112c]) by gmr-mx.google.com with ESMTPS id af79cd13be357-8b627aec0cbsi69495985a.9.2025.12.09.16.42.01 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 09 Dec 2025 16:42:01 -0800 (PST) Received-SPF: pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::112c as permitted sender) client-ip=2607:f8b0:4864:20::112c; Received: by mail-yw1-x112c.google.com with SMTP id 00721157ae682-78a76afeff6so70699767b3.0 for ; Tue, 09 Dec 2025 16:42:01 -0800 (PST) X-Gm-Gg: AY/fxX4L1g9pSOF59DTnarvKUAMkcGIa/shxlWAo/N67Nv8DlHyQ36TIb62wt6odG0P uz8te2XHNzBUoR5K2wuhG/Xc7rZbiAA5CkvSfTCNkETVIZeXo/wDhEVz5MLUQbrAo2YwcwJSQJs GUyMWBfx4PQwDl4H6eKKo2y4nxmB4t2f8mOTcmf3tLZWC8Rtx8aXSL6afpMKCe8p1b16EGrdV/V SbTrzM56ScfnvLB0wbig1JQDj2/YIFwsCEdhr6Nrc8tV+q4dalXUwgSiLEdrPoSQ7a9uyn1cZVv k0D0jS0a3AuDIts4zbTd8IweJYX2 X-Received: by 2002:a05:690c:3508:b0:78a:75b2:be66 with SMTP id 00721157ae682-78c95a2f3famr6573877b3.11.1765327320745; Tue, 09 Dec 2025 16:42:00 -0800 (PST) MIME-Version: 1.0 References: <3e815d03-5e21-41ed-ba1a-4f9b2120a986n@googlegroups.com> <0e2402c5-d593-49ff-b002-5ab348b46964n@googlegroups.com> In-Reply-To: <0e2402c5-d593-49ff-b002-5ab348b46964n@googlegroups.com> From: Olaoluwa Osuntokun Date: Tue, 9 Dec 2025 16:41:48 -0800 X-Gm-Features: AQt7F2qBBmGr_z4urVWvBJ6nOICiU6H-_9s_J9P62P2hC2qZkgkpYLASr_x3vwc Message-ID: Subject: Re: [bitcoindev] Hash-Based Signatures for Bitcoin's Post-Quantum Future To: conduition Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000dd8ab406458e4b06" 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=Rswaaeb7; spf=pass (google.com: domain of laolu32@gmail.com designates 2607:f8b0:4864:20::112c 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 (/) --000000000000dd8ab406458e4b06 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi y'all, conduition wrote: > I'm personally hoping that we'll find a way to derive child pubkeys using > lattices (ML-DSA) and/or isogenies (SQIsign), but I haven't heard of any > solid proposals yet. This paper [1] proposes a variant of Dilithium (dubbed DilithiumRK, RK for 'randomized keys' presumably) that enables BIP-32-like functionality. It achieves this by getting rid of a public key compression step in the OG algorithm that results in a loss of homomorphic properties. There're algorithmic changes required (eg: a new public network param is needed which is used for seed/key generation), so it isn't vanilla FIP 204. Aside from the deviation from the standard, the scheme introduces some additional trade offs: * Signatures arger as signatures carry a new error hint * Signing is 2.7x slower * Verification is 1.75x slower There's also a published BIP-32-like like scheme for Falcon signatures [2]. I'm less familiar with the details here, but the signature size blows up to ~24KB compared to ~666 bytes for normal Falcon signatures. -- Laolu [1]: https://cic.iacr.org/p/2/3/3 [2]: https://link.springer.com/article/10.1186/s42400-024-00216-w On Mon, Dec 8, 2025 at 10:49=E2=80=AFPM 'conduition' via Bitcoin Developmen= t Mailing List wrote: > Great work Jonas and Mikhail, glad to see more eyes and ears surveying > these schemes and their potential. Also shameless plug for some of my > prior work on related topics > . > > The post-quantum HD wallet derivation problem is one i've been thinking > about a lot lately. Due to the lack of algebraic structure in SLH-DSA it'= s > gonna be impossible to fully emulate BIP32 with that scheme alone. I'm > personally hoping that we'll find a way to derive child pubkeys using > lattices (ML-DSA) and/or isogenies (SQIsign), but I haven't heard of any > solid proposals yet. Currently reading on isogeny crypto as that sounds > like a promising candidate. > > If such a thing is possible, then we could derive BIP360 tap trees > containing a static SLH-DSA pubkey, alongside dynamically derived keys fo= r > a more structured algebraic PQ scheme like ML-DSA, and finally a regular = EC > BIP340 pubkey derived by regular BIP32. The idea being one could distribu= te > a 'post quantum xpub' containing a regular BIP32 key extended with PQ > public keys. Wallets or 3rd parties could derive child addresses which > contain tap trees with one leaf per signing scheme. Since SLH-DSA doesn't > support unhardened derivation, the SLH-DSA public key would have to be us= ed > as-is in every child leaf, without any derivation (maybe with an extra > pseudorandom nonce thrown in to avoid reusing the same tap leaf hash in > different TXs). Think of defining: CDKPub_slh(spx_pubkey, chaincode, n) := =3D > (spx_pubkey, HMAC(chaincode, n)) > > Regarding smaller signatures: I used to be a big fan of SPHINCS+C and > SPHINCS-=CE=B1 . I asked Andreas Hulsin= g, > the SPHINCS+ team lead, why weren't these obviously better schemes > standardized instead? he said NIST shied away from them because they > complicated the implementation for little material benefit. There were al= so > "political" considerations, owing to the fact that they were proposed lat= e > in the standardization competition's timeline. Obviously bitcoin is a > different ballgame entirely, but the point is we should optimize where it > matters most. IMO that means smaller parameter set(s). Even without PoW > compression, hybercubes , or other > modern tricks to optimize SLH-DSA, we can make sigs *much* smaller by > just tweaking constants, and we can do so *without* losing compatibility > with the NIST-compliant algorithm. So that idea has a big +1 from me. NIS= T > is in the process of standardizing smaller parameter sets > but > they have much higher signing/keygen perf overhead. If we want smaller > hash-based sigs, we should pick new parameter sets to standardize in > Bitcoin, covering different use cases, and use them with the standardized > FIPS-205 algorithm. Agreeing on *which* parameter sets will be hard > though. See https://github.com/chrisfenner/slh-dsa-rls > > I agree with Greg about the verification cost, you can't just consider > cycles/byte, you have to consider the cost of verifying entire blocks ful= l > of these signatures. While my recent research showed that SLH-DSA signing > and keygen can be very effectively parallelized, verification is much > harder to parallelize. You have to parallelize generically across > signatures in a block (which can also be done with ECC, or any sig-verify > algo for that matter). > > On statefulness: I once felt quite strongly that we should have stateful > WOTS on-chain as an opcode - WOTS is pretty much the smallest hash-based > signatures you can get. But talking with Ethan and Hunter has since > convinced me that stateless sigs are the only way to go. There's just too > many landmines and footguns to step on with schemes like WOTS, or even it= s > big daddy XMSS, if you use them to sign non-deterministic data statefully= . > > Finally, while everyone (including me) is really excited about hash-based > signatures because we know and love and trust hash functions, in reality > the performance, functionality, and sig-size tradeoffs will lead to 99% o= f > people using schemes with new assumptions like ML-DSA for everyday usage. > Hash based sigs will be the worst-case scenario fallback, in case the mor= e > efficient schemes like ML-DSA or SQIsign turn out to be cryptographically > broken (a real possibility, the feds have standardized broken schemes > before after all). > > > I don't think it matters much if signing is slow on low power devices -= - > e.g. taking seconds per input. > > It's far worse than that. Here are some benchmarks run by Trezor on their > Model T signing device > . 75 > seconds to create one SLH-DSA-SHA2-128s signature. RAM requirements are > quite low for SLH-DSA compared to ML-DSA which is nice. Apparently some o= f > their newer devices have dedicated chips which can execute SHA256 much > faster than the ARM M4, but i haven't seen any benchmarks on those yet. I > think those kinds of hash accelerators, or FPGAs etc, will need to become > standard for hardware wallets if they plan to use SLH-DSA signing (or > keygen). I don't know about ledger, because they apparently don't think > quantum is a serious risk :/ > > > regards, > conduition > > On Monday, December 8, 2025 at 4:58:18=E2=80=AFPM UTC-5 Greg Maxwell wrot= e: > >> On Mon, Dec 8, 2025 at 8:47=E2=80=AFPM 'Mikhail Kudinov' via Bitcoin Dev= elopment >> Mailing List wrote: >> >>> 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. >>> >> >> No scheme has such a limitation, because any scheme can use a hash of th= e >> underlying primitive as the public key-- which Bitcoin has done since da= y >> one. The correct figure of merit is the the size of the signature, pubk= ey, >> and a hash combined or-- if the pubkey is under 500 bits or so, just th= e >> size of the signature plus pubkey. >> >>> >>> Verification cost per byte is comparable to current Schnorr signatures, >>> alleviating concerns about blockchain validation overhead. >>> >> >> Though hash based signatures don't really concern me much in validation >> costs, I disagree with the premise of this statement. If the size was >> similar then I'd agree that cost per byte being similar was enough to ma= ke >> validation costs not a concern, but the size is some 40 times larger and >> 40x validation costs is certainly a concern unless the scheme is deploye= d >> without an effective increase in block capacity-- and without a capacity >> increase the utility of such large signatures is potentially pretty >> dubious. Even if a proposal doesn't itself include a capacity increase >> one should be regarded as inevitable along with it, particularly becaus= e >> just securing *your* coins against this attack won't do you any good if = 95% >> of all other coins get stolen by it-- so a performance analysis should >> anticipate needing the capacity for all of the transaction flow to use t= he >> scheme, even if that isn't the case for the initial usage. >> >> 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. >>> >> >> It's not an either/or, I believe. I think schemes with weakened stateles= s >> security could be improved to ~full repeated use security via statefulne= ss >> (e.g. grinding the message to avoid revealing signatures that leak key >> material). There may be possibilities for other hybrids: an otherwise >> stateless wallet which is assumed to have visibility to its own confirme= d >> transactions. It may be that a 'few time secure' scheme could be adequa= te >> when coupled with best effort statefulness (e.g. blockchain visibility) >> and a series composed schnorr signature (which means the brittleness of = the >> hash signature only matters if the schnorr signature is broken). >> >> Statefulness is not a great assumption with how bitcoin private keys >> work, particularly for cold storage. Especially since key loss is usua= lly >> the greatest risk to coin possession and the best mechanism against key >> loss is duplicate copies separately stored. Although correct usage of >> bitcoin results in keys being single use or nearly so, it's a security >> footgun to make a strong assumption. >> >> 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. >>> >> >> There may be advantages there to using a threshold schnorr in series wit= h >> a single PQ scheme, in that case the security model is "a threshold of >> participants must agree OR a participant must agree and have a successfu= l >> attack on the threshold schnorr signature". This may well be a reasonab= le >> compromise considering the costs of multiple PQ keys-- particularly when >> the participants are known entities and not e.g. an anonymous channel >> counterparty. >> >> 1) What are the concrete performance requirements across various >>> hardware, including low-power devices? >>> >> >> I don't think it matters much if signing is slow on low power devices -- >> e.g. taking seconds per input. It would obviously matter to *some* user= s >> but those users could use higher power signing devices. The minimum amo= unt >> of dynamic ram needed for signing (even at low performance) is probably >> pretty important. >> >> 2) Should multiple schemes with different signature limits be >>> standardized? >>> 3) Is there value in supporting stateful schemes alongside stateless >>> ones? >> >> >> Depends on their relative costs. Plain stateful (of the 'two signatures >> breaks your security' sort) is a very concerning footgun with bad side >> effects (e.g. can't even bump fees) but even that could be attractive if >> the size is much smaller. Having a totally free configuration is quit= e >> bad for privacy, however, and of dubious value. I think that just havi= ng >> two options, e.g. secure for 'few' and secure for 'many' (but no need fo= r >> 2^128) with both supporting but not requiring statefulness as a best eff= ort >> hail-mary protection against self-compromise might be interesting, but i= t >> would depend on their relative performance. One possibility would be to >> just always have both alternatives available (at a cost of 32 bytes) and >> for the user to decide at signing time. >> >> >> >> >> -- > 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/0e2402c5-d593-49ff-b002-5ab3= 48b46964n%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/= CAO3Pvs_cetTGP54zDzJJGRPeN7gXrRYGZZYk4mRYnhJQnwotdA%40mail.gmail.com. --000000000000dd8ab406458e4b06 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi y'all,

conduition wrote:
> I'= ;m personally hoping that we'll find a way to derive child pubkeys usin= g
> lattices (ML-DSA) and/or isogenies (SQIsign), but I haven't h= eard of any
> solid proposals yet.

This paper [1] proposes a v= ariant of Dilithium (dubbed DilithiumRK, RK for
'randomized keys'= ; presumably) that enables BIP-32-like functionality. It
achieves this b= y getting rid of a public key compression step in the OG
algorithm that = results in a loss of homomorphic properties. There're
algorithmic ch= anges required (eg: a new public network param is needed
which is used f= or seed/key generation), so it isn't vanilla FIP 204.

Aside fro= m the deviation from the standard, the scheme introduces some
additional= trade offs:

=C2=A0 * Signatures arger as signatures carry a new err= or hint

=C2=A0 * Signing is 2.7x slower

=C2=A0 * Verification= is 1.75x slower

There's also a published BIP-32-like like schem= e for Falcon signatures [2]. I'm
less familiar with the details here= , but the signature size blows up to
~24KB compared to ~666 bytes for no= rmal Falcon signatures.

-- Laolu

[1]: https://cic.iacr.org/p/2/3/3

[2]: https://link.s= pringer.com/article/10.1186/s42400-024-00216-w


On Mon, Dec 8, 2025= at 10:49=E2=80=AFPM 'conduition' via Bitcoin Development Mailing L= ist <bitcoindev@googlegro= ups.com> wrote:
Great work Jonas and Mikhail, glad to see more eyes and ears surveyi= ng these schemes and their potential. Also shameless plug for some of my prior = work on related topics.

The post-quantum HD w= allet derivation problem is one i've been thinking about a lot lately. = Due to the lack of algebraic structure in SLH-DSA it's gonna be impossi= ble to fully emulate BIP32 with that scheme alone. I'm personally hopin= g that we'll find a way to derive child pubkeys using lattices (ML-DSA)= and/or isogenies (SQIsign), but I haven't heard of any solid proposals= yet. Currently reading on isogeny crypto as that sounds like a promising c= andidate.

If such a thing is possible, then we cou= ld derive BIP360 tap trees containing a static SLH-DSA pubkey, alongside dy= namically derived keys for a more structured algebraic PQ scheme like ML-DS= A, and finally a regular EC BIP340 pubkey derived by regular BIP32. The ide= a being one could distribute a 'post quantum xpub' containing a reg= ular BIP32 key extended with PQ public keys. Wallets or 3rd parties could d= erive child addresses which contain tap trees with one leaf per signing sch= eme. Since SLH-DSA doesn't support unhardened derivation, the SLH-DSA p= ublic key would have to be used as-is in every child leaf, without any deri= vation (maybe with an extra pseudorandom nonce thrown in to avoid reusing t= he same tap leaf hash in different TXs). Think of defining: CDKPub_slh(spx_= pubkey, chaincode, n) :=3D (spx_pubkey, HMAC(chaincode, n))

<= /div>
Regarding smaller signatures: I used to be a big fan of SPHINCS+C= and SPHINCS= -=CE=B1. I asked Andreas Hulsing, the SPHINCS+ team lead, why weren'= ;t these obviously better schemes standardized instead? he said NIST shied = away from them because they complicated the implementation for little mater= ial benefit. There were also "political" considerations, owing to= the fact that they were proposed late in the standardization competition&#= 39;s timeline. Obviously bitcoin is a different ballgame entirely, but the = point is we should optimize where it matters most. IMO that means smaller p= arameter set(s). Even without PoW compression, hybercubes, or other modern tricks t= o optimize SLH-DSA, we can make sigs much smaller by just tweaking c= onstants, and we can do so without=C2=A0losing compatibility with th= e NIST-compliant algorithm. So that idea has a big +1 from me. NIST is in t= he process of standardizing smaller parameter sets but they have much higher signing/keygen perf overhead. If we want small= er hash-based sigs, we should pick new parameter sets to standardize in Bit= coin, covering different use cases, and use them with the standardized FIPS= -205 algorithm. Agreeing on which=C2=A0parameter sets will be hard t= hough. See=C2=A0https://github.com/chrisfenner/slh-dsa-rls

=
I agree with Greg about the verification cost, you can't jus= t consider cycles/byte, you have to consider the cost of verifying entire b= locks full of these signatures. While my recent research showed that SLH-DS= A signing and keygen can be very effectively parallelized, verification is = much harder to parallelize. You have to parallelize generically across sign= atures in a block (which can also be done with ECC, or any sig-verify algo = for that matter).=C2=A0

On statefulness: I once fe= lt quite strongly that we should have stateful WOTS on-chain as an opcode -= WOTS is pretty much the smallest hash-based signatures you can get. But ta= lking with Ethan and Hunter has since convinced me that stateless sigs are = the only way to go. There's just too many landmines and footguns to ste= p on with schemes like WOTS, or even its big daddy XMSS, if you use them to= sign non-deterministic data statefully.=C2=A0

Fin= ally, while everyone (including me) is really excited about hash-based sign= atures because we know and love and trust hash functions, in reality the pe= rformance, functionality, and sig-size tradeoffs will lead to 99% of people= using schemes with new assumptions like ML-DSA for everyday usage. Hash ba= sed sigs will be the worst-case scenario fallback, in case the more efficie= nt schemes like ML-DSA or SQIsign turn out to be cryptographically broken (= a real possibility, the feds have standardized broken schemes before after = all).

> I don't think it matters much if si= gning is slow on low power devices -- e.g. taking seconds per input.=C2=A0<= /div>

It's far worse than that. Here are some benchmarks run by Trezor on their Model T signing devic= e. 75 seconds to create one SLH-DSA-SHA2-128s signature. RAM requiremen= ts are quite low for SLH-DSA compared to ML-DSA which is nice. Apparently s= ome of their newer devices have dedicated chips which can execute SHA256 mu= ch faster than the ARM M4, but i haven't seen any benchmarks on those y= et. I think those kinds of hash accelerators, or FPGAs etc, will need to be= come standard for hardware wallets if they plan to use SLH-DSA signing (or = keygen). I don't know about ledger, because they apparently don't t= hink quantum is a serious risk :/=C2=A0


=
regards,
conduition

On Monday, December 8, = 2025 at 4:58:18=E2=80=AFPM UTC-5 Greg Maxwell wrote:
On M= on, Dec 8, 2025 at 8:47=E2=80=AFPM 'Mikhail Kudinov' via Bitcoin De= velopment Mailing List <bitco...@googlegroups.com> wrote:

<= div dir=3D"ltr">
No scheme has such a limita= tion, because any scheme can use a hash of the underlying primitive=C2=A0as= the public key-- which Bitcoin has done since day one.=C2=A0 The correct f= igure of merit is the the size of the signature, pubkey, and a hash combine= d=C2=A0 or-- if the pubkey is under 500 bits or so, just the size of the si= gnature plus pubkey.
Though h= ash based signatures don't really concern me much in validation costs, = I disagree with the premise of this statement.=C2=A0 If the size was simila= r then I'd agree that cost per byte being similar was enough to make va= lidation costs not a concern, but the size is some 40 times larger and 40x = validation costs is certainly a concern unless the scheme is deployed witho= ut an effective increase in block capacity-- and without a capacity increas= e the utility of such large signatures is potentially pretty dubious.=C2=A0= =C2=A0Even if a proposal doesn't itself include a capacity increase on= e should be regarded as inevitable along with it,=C2=A0 particularly becaus= e just securing *your* coins against this attack won't do you any good = if 95% of all other coins get stolen by it-- so a performance analysis shou= ld anticipate needing the capacity for all of the transaction flow to use t= he scheme, even if that isn't the case for the initial usage.

It's no= t an either/or, I believe. I think schemes with weakened=C2=A0stateless sec= urity could be improved to ~full repeated use security via statefulness (e.= g. grinding the message to avoid revealing signatures that leak key materia= l).=C2=A0 There may be possibilities for other hybrids: an otherwise statel= ess wallet which is assumed to have visibility to its own confirmed transac= tions.=C2=A0 It may be that a 'few time secure' scheme could be ade= quate when coupled with best effort statefulness (e.g. blockchain visibilit= y)=C2=A0 and a series composed schnorr signature (which means the brittlene= ss of the hash signature only matters if the schnorr signature is broken).<= /div>

Statefulness is not a great assumption with how bi= tcoin private keys work, particularly for cold storage.=C2=A0 =C2=A0Especia= lly since key loss is usually the greatest risk to coin possession and the = best mechanism against key loss is duplicate copies separately stored.=C2= =A0 =C2=A0Although correct usage of bitcoin results in keys being single us= e or nearly so, it's a security footgun to make a strong assumption.
De= pends on their relative costs.=C2=A0 Plain stateful (of the 'two signat= ures breaks your security' sort) is a very concerning footgun with bad = side effects (e.g. can't even bump fees) but even that could be attract= ive if the size is much smaller.=C2=A0 =C2=A0 Having a totally free configu= ration is quite bad for privacy, however, and of dubious value.=C2=A0 =C2= =A0I think that just having two options, e.g. secure for 'few' and = secure for 'many' (but no need for 2^128) with both supporting but = not requiring statefulness as a best effort hail-mary protection against se= lf-compromise might be interesting, but it would depend on their relative p= erformance.=C2=A0 One possibility=C2=A0would be to just always have both al= ternatives available (at a cost of 32 bytes) and for the user to decide at = signing time.=C2=A0=C2=A0



--
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/0e2402c5-d593-49ff-b002-5ab348b46964n%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/CAO3Pvs_cetTGP54zDzJJGRPeN7gXrRYGZZYk4mRYnhJQnwotdA%40mail.g= mail.com.
--000000000000dd8ab406458e4b06--