From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 27 Jan 2026 08:26:17 -0800 Received: from mail-oo1-f64.google.com ([209.85.161.64]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1vkltP-0002LT-MZ for bitcoindev@gnusha.org; Tue, 27 Jan 2026 08:26:17 -0800 Received: by mail-oo1-f64.google.com with SMTP id 006d021491bc7-6610d312bc3sf18306671eaf.3 for ; Tue, 27 Jan 2026 08:26:15 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1769531169; x=1770135969; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :from:to:cc:subject:date:message-id:reply-to; bh=6fLTUHnCIjmxKmmAYCe+q+GPdRzbIMUX5POfRAifFnY=; b=oaRUEe7g/HnNYl5EBFSUtrMfMtu8w9JZ/tjiEZTk73O2GaTQwnxXJ6sYQtj5YZvjAt zLFqHf6QSIs8sNnKrdP87Ax5lKQ6/6KtTTBoj6ZZj0OVhEFkrSfUxxo7zDZqKcI1770d XzayjBIhX6K+gjZjreThELhCMOW2Mfv0aWif0NpWdOWA5TqdpCsKaCszfhDk6vMoA5a3 wjBckmS6MUSkNMb1mbzY8fzSKKjlmTLHkEOUiShoxrlMbzZjyaX4UVX10Beoi1C16gcz iD6vQA4hXuQ3SWEp1BToeA/+Oxs5jN6jEl6CJIW3woYVTYVgQKVlIjRugF88qSZCm4aF iQUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1769531169; x=1770135969; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:reply-to:x-original-sender :mime-version:subject:references:in-reply-to:message-id:to:from:date :x-beenthere:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=6fLTUHnCIjmxKmmAYCe+q+GPdRzbIMUX5POfRAifFnY=; b=lU7n+MlJpFq3q3Uk+1b6SzbtXaAMVHX1lYwibsV2YKdXKAb1bqs0jNvZpCK6QEimk9 Ydlb9d54mqsoSYLVAZCD9QoeZRj3SdchauunPo23NR2v47465VU8+qE6zDqc4C3T2HTT kDdUJWt6RTtkheyV3G+HjSAW5dlf1iXFe4pg4HLiW5sD47i6NXHYOyThV78YtD94acoR 7uGZegnWr0EVftkmMcw7WGKEdwoxU7Zza4QziDY5VXrTKUcgM5QdYoSZ5SdIweGdp6Ip I89m9YaU3ywfs4eFgQI9JACkH4yHm60J1BEcG8jTguHppjTRHMCq/4ZOXygtsd0O31zl MAYw== X-Forwarded-Encrypted: i=1; AJvYcCWjxPyU2ylhPdvpnng2KyEeZpATRo84GbESeWZmMZ4mUq9iccOin/+YJjF6MpJRZ2yT9bCuG9HgRF6c@gnusha.org X-Gm-Message-State: AOJu0Yy5yWtGEykkkRrM22lDdw1ASufZq/e/2GgEXYuZcyHdaq4irJom TuSe4m33aFblDqplS+IBe7TTTpM5u5G4hDOIfV7pI9wVTtEKmwgArRrl X-Received: by 2002:a05:6820:2229:b0:662:f91f:4a82 with SMTP id 006d021491bc7-662f91f4d0amr89589eaf.26.1769531168987; Tue, 27 Jan 2026 08:26:08 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h="AV1CL+FPw+Uer+Fs2Ar1h9JPL4uBttTWmVHVTzaadM4Jsu5epA==" Received: by 2002:a05:6870:5a9:b0:3ec:401f:488b with SMTP id 586e51a60fabf-4088266ebf3ls2631486fac.1.-pod-prod-03-us; Tue, 27 Jan 2026 08:26:01 -0800 (PST) X-Received: by 2002:a05:6808:1456:b0:45e:84e7:c20b with SMTP id 5614622812f47-45efc5984f6mr1289357b6e.25.1769531161753; Tue, 27 Jan 2026 08:26:01 -0800 (PST) Received: by 2002:a05:690c:56c5:20b0:794:2788:2ae4 with SMTP id 00721157ae682-7943c31864dms7b3; Tue, 27 Jan 2026 08:07:22 -0800 (PST) X-Received: by 2002:a05:690c:a5d3:b0:78c:2f46:1e1c with SMTP id 00721157ae682-7947ab64050mr12178857b3.28.1769530040930; Tue, 27 Jan 2026 08:07:20 -0800 (PST) Date: Tue, 27 Jan 2026 08:07:20 -0800 (PST) From: "'conduition' via Bitcoin Development Mailing List" To: Bitcoin Development Mailing List Message-Id: <4b0eda09-32c0-4419-a691-edacad231865n@googlegroups.com> In-Reply-To: <02326d1c-9cf8-4b4c-b5dc-cdb00f76d451n@googlegroups.com> References: <16e01530-e9dd-481f-8c7f-ca9ccafcfcden@googlegroups.com> <2e4abb5a847ab9d78857aee2fded500a234f68a6.camel@gmail.com> <46faf0c0-d60d-49a4-83c5-8fe03f11c89dn@googlegroups.com> <02326d1c-9cf8-4b4c-b5dc-cdb00f76d451n@googlegroups.com> Subject: Re: [bitcoindev] Falcon Post-Quantum Signature Scheme Proposal MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_159808_1161651692.1769530040093" X-Original-Sender: conduition@proton.me X-Original-From: conduition Reply-To: conduition 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 (-) ------=_Part_159808_1161651692.1769530040093 Content-Type: multipart/alternative; boundary="----=_Part_159809_1211441127.1769530040093" ------=_Part_159809_1211441127.1769530040093 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi all, I don't think arithmetic circuit optimization for SNARKs should be a main= =20 course for the PQ transition. Maybe it could be a dessert if we have=20 appetite for it later. I am confident that no ZK-SNARK will ever make it into consensus on Bitcoin= =20 unless it has transparent setup, and I doubt a ZK-SNARK will survive long= =20 term if it is not quantum-secure. AFAIK that limits our options to=20 ZK-STARKs (correct me if you know of any other transparent PQ-secure=20 ZK-SNARK). In my admittedly shallow foray into=20 ZK-STARKs, the biggest problem= =20 I found is the scaling floor of STARKs. Simple proofs over small circuits= =20 have very large communication complexity (hundreds of kilobytes) compared= =20 to their classical witnesses (a few bytes). However, as the circuit gate=20 depth grows, communication complexity grows as O(n log n) (see page 12 of t= his=20 paper for a pretty graph), which is *rea= lly=20 awesome*. Even the biggest STARKs don't seem to exceed 1MB. This makes=20 STARKS most suitable for very large computations which would either be=20 impractical to recompute naively, or impractical to store classical witness= =20 data for. Common examples are zk-rollups, as Giulio pointed out, or chain= =20 validity proofs like ZeroSync .=20 The main point I want to stress is that for STARKs to be useful for PQ=20 signature aggregation, we need to aggregate *a lot of signatures at once*. = Ethan=20 Heilman played with this idea=20 . Or you could avoid uploading the STARK proof to the chain at all. See this= =20 recent paper by Nick, Eagen, and Linus=20 called "Shielded CSV", which=20 describes a (non-quantum secure) way to use recursive ZK proofs to make=20 payments on Bitcoin with perfect privacy, without needing to post the full= =20 ZK proofs to the network. Only a payment's recipient needs to see the=20 proof. Lots of good ideas to explore there for any who want to make a=20 quantum-secure CSV protocol. As for uploading STARKs directly to the chain, to be worth our while in=20 terms of blockspace savings we'd need to aggregate at least a few dozen PQ= =20 signatures per proof... hundreds of sigs if the PQ scheme is more succinct= =20 like Falcon. Because STARKs scale so well for the verifier, it doesn't=20 really matter to the verifier how big the computation is - Proof sizes stay= =20 capped below the megabyte range, and verifier runtime remains very fast.=20 The choice of computation *matters far more to the prover*, who will have= =20 to spend minutes or hours of heavy compute time proving it, depending on=20 circuit size. Unless there exists some obvious demand to make these=20 hypothetical PQ signature provers very fas,. I don't see any reason to use= =20 arithmetic circuit size as a high weight metric for our PQ signature scheme= =20 choices. Also, remember that optimizing for arithmetic circuit size and ZK prover=20 efficiency sometimes means hobbling classical computational efficiency. The= =20 Poseidon hash function is about an order of magnitude slower than SHA2, for= =20 example=20 . Mind you, STARKs is still a young field with active research. For example= =20 there's Circle STARKs which improve= =20 STARK proving time. I recently spoke with a grad student who is considering= =20 a research project on the application of ZK technologies to post-quantum=20 signature schemes like SPHINCS. I know he lurks on this list, so maybe he'd= =20 have some more nuanced opinions to share. PS. I'm very curious to know how the arithmetized circuit sizes of=20 different signing schemes compares, e.g. SPHINCS vs XMSS vs Dilithium vs EC= =20 Schnorr. If anyone has data on that please pipe in! regards, conduition On Monday, January 26, 2026 at 8:24:26=E2=80=AFAM UTC-7 waxwing/ AdamISZ wr= ote: > > I support the idea that SNARK/STARK-friendliness can not be a crucial= =20 > point, as it is not currently supported, but can be an argument for=20 > tie-breaking cases. > > It's kind of contextual, right: it's a naturally correct default position= =20 > that "one shouldn't impose arbitrary requirements on new PQ schemes that= =20 > are not in place for even the existing schnorr/ecdsa schemes, all the mor= e=20 > so with respect to speculative concepts around offchain transacting syste= ms=20 > that aren't proven or don't even exist in prototype form". But the=20 > "contextual" here is: does the proposed QC scheme have an enormous onchai= n=20 > footprint (or verification cost) without any offsetting quality that coul= d=20 > ameliorate what that implies about transaction throughputs (or=20 > centralization pressures)? That's why I mentioned batched (I should have= =20 > said aggregated) signing and CISA, even though it might seem like a bit o= f=20 > a side issue. In case we really are looking at 20x multipliers and there = is=20 > *no* ameliorating factor then ... it feels hard to support a move in that= =20 > direction, except of course, in extremis. > > A natural counterpoint might be: "we don't have some set-in-stone plan to= =20 > develop and support only one PQ scheme, so if one is proposed and=20 > prototyped which has no scaling amelioration, it's OK, we're not outlawin= g=20 > a future better version". > > Another natural counterpoint might be "doing anything remotely viable is= =20 > hard enough, so *demanding* some compatibility with STARK or some PQ SNAR= K=20 > is kind of ridiculous". Fair :) > > May I also ask whether support for adaptors is considered in scope (or=20 > indeed, do any of the plausible candidates have this property?)? I guess= =20 > you'd consider it out of scope, though it'd be an interesting detail. > > AdamISZ/waxwing > > On Monday, January 26, 2026 at 9:37:56=E2=80=AFAM UTC-3 Mikhail Kudinov w= rote: > >> The investigation of Lattice-Based approaches is on the table, so I thin= k=20 >> we will be able to make a thoughtful comparison at some point. I support= =20 >> the idea that SNARK/STARK-friendliness can not be a crucial point, as it= is=20 >> not currently supported, but can be an argument for tie-breaking cases. = =20 >> >> All pairing-based schemes are broken by a quantum computer, yes. STARKs= =20 >> are plausibly post-quantum. There are some schemes based on Lattices as= =20 >> well.=20 >> >> The QKD problems are not important for our discussion; they do not affec= t=20 >> PQ transition. >> >> Best, >> Mike=20 >> >> On Sun, Jan 25, 2026 at 11:44=E2=80=AFPM cassio gusson =20 >> wrote: >> >>> hey guys >>> >>> I don't know if this is important for the implementation being=20 >>> discussed, but I think the study that identified a flaw in quantum key= =20 >>> distribution (QKD) is worthwhile. >>> >>> https://ieeexplore.ieee.org/document/11223709 >>> >>> Best regards >>> C=C3=A1ssio Gusson >>> >>> Em s=C3=A1b., 24 de jan. de 2026 =C3=A0s 17:12, waxwing/ AdamISZ < >>> ekag...@gmail.com> escreveu: >>> >>>> Hi Mike, >>>> >>>> > It is also a question: how much weight should we put on adopting an= =20 >>>> explicitly SNARK-friendly signature scheme? While such compatibility i= s=20 >>>> clearly advantageous, it does not seem to me to be a decisive point on= its=20 >>>> own. What would you say? >>>> >>>> Does it depend on what we really mean by SNARK, apart from the literal= =20 >>>> definition? >>>> What SNARK schemes are we thinking of that are post quantum? I presume= =20 >>>> I can say "all the pairings based SNARKs (and the DLOG based ones) are= not=20 >>>> quantum resistant". Are STARKs the only realistic option in this scena= rio?=20 >>>> I am enormously ignorant about STARKs, but I do seem to recall that th= ey=20 >>>> have large proofs, so at least in theory that's a problem for such pla= nning? >>>> >>>> Or maybe there's another PQ SNARK scheme that I'm just unaware of. >>>> >>>> I guess this is orthogonal to the point you're raising about=20 >>>> arithmetic-circuit friendly hash functions like Poseidon, though. That= part=20 >>>> I find a bit brain-melting because: what mechanism is assumed to exist= to=20 >>>> translate a STARK or SNARK proof into an onchain effect? If there was = say a=20 >>>> STARK op-code then, job done. You'd just somehow have to have sufficie= ntly=20 >>>> small STARK proofs which is AIUI not trivial, even with nice hash=20 >>>> functions. If not, we're back to the current hyper-sophisticated scena= rios=20 >>>> of things like Glock and BABE where you use garbled circuits, witness= =20 >>>> encryption, and also need something like the adaptor primitive of "swa= p=20 >>>> signature for secret" which we currently get kind of "for free" in Sch= norr=20 >>>> with the linearity. I suppose there might be alternatives (e.g. HTLC= =20 >>>> instead of PTLC) that might be more clunky, but viable. And all of tha= t is=20 >>>> of course "fraud proof" style, with "slashing", and not anywhere near = as=20 >>>> clean a design as "just verify the STARK". >>>> >>>> How does one take the 10000ft view on this needed to make a design=20 >>>> decision? Obviously I don't know, at all, just raising points here. I = guess=20 >>>> the most interesting one is: "is STARK realistically the only game in = town=20 >>>> here?". >>>> >>>> Cheers, >>>> AdamISZ/waxwing >>>> On Friday, January 23, 2026 at 1:34:36=E2=80=AFPM UTC-3 Mikhail Kudino= v wrote: >>>> >>>>> Hi everyone, >>>>> I am happy that the discussion on the PQ topic is active. I wanted to= =20 >>>>> add my view on the raised issues.=20 >>>>> >>>>> For the fallback in SHRINCS, one option is to use SPHINCS+ as a=20 >>>>> fallback with a limited number of signatures. By setting an upper bou= nd as=20 >>>>> large as 2^30 or 2^40, the signature size can be significantly reduce= d, and=20 >>>>> the scheme would only be invoked in exceptional circumstances. In mos= t=20 >>>>> realistic scenarios, the fallback would consist of generating a singl= e=20 >>>>> signature to move assets to a new address. As for the statefulness=20 >>>>> problems, I agree that this is an important drawback that we should k= eep in=20 >>>>> mind. >>>>> >>>>> The SHA-based SPHINCS+ is indeed not particularly efficient in SNARK= =20 >>>>> settings. But one could replace the hash functions with SNARK-friendl= y=20 >>>>> alternatives (for example, Poseidon) in the future, which will make i= t=20 >>>>> much, much more efficient. >>>>> >>>>> It is also a question: how much weight should we put on adopting an= =20 >>>>> explicitly SNARK-friendly signature scheme? While such compatibility = is=20 >>>>> clearly advantageous, it does not seem to me to be a decisive point o= n its=20 >>>>> own. What would you say? >>>>> I am also unsure to what extent Falcon can be considered=20 >>>>> SNARK-friendly. Has there been any research in this direction, or are= there=20 >>>>> benchmarks evaluating its performance in SNARK environments? >>>>> >>>>> Finally, regarding SQIsign: although the signature sizes are=20 >>>>> remarkable, I agree that we need more time for the scheme to mature b= efore=20 >>>>> considering adoption. >>>>> >>>>> Best, >>>>> Mike >>>>> >>>>> On Fri, Jan 23, 2026 at 3:03=E2=80=AFPM Giulio Golinelli < >>>>> golinelli...@gmail.com> wrote: >>>>> >>>>>> Falcon (FN-DSA) relies on discrete gaussian sampling using=20 >>>>>> constant-time floating point arithmetic for signers, which is very h= ard to=20 >>>>>> implement quickly and in constant time (securely). >>>>>> >>>>>> This is true for the first Falcon version published (randomized mode= =20 >>>>>> of operation). This implementation uses the author-recommended=20 >>>>>> deterministic Falcon mode (see author=E2=80=99s notes=20 >>>>>> ) which= =20 >>>>>> uses software floating-point emulation . This eliminates side-channe= l risks=20 >>>>>> associated with non-constant-time hardware FPUs. It is also SNARK-fr= iendly=20 >>>>>> and overcomes portability limitation. While this sacrifices the perf= ormance=20 >>>>>> optimizations of true FPUs, signing speed is not critical in Bitcoin= , where=20 >>>>>> verification dominates node activity. >>>>>> >>>>>> If small signatures are your goal, then I'd look into SQIsign=20 >>>>>> >>>>>> >>>>>> This would be good like many other PQ exotic schemes but all of thes= e=20 >>>>>> are far from being standardized soon. >>>>>> >>>>>> If you want a PQC scheme that's ready *today* and also provides=20 >>>>>> small signatures, I'll point you to XMSS, and Jonas Nick's SHRINCS= =20 >>>>>> proposal=20 >>>>>> .=20 >>>>>> You can configure an unbalanced XMSS tree to get 272 byte signatures= ,=20 >>>>>> potentially smaller if you crank up the parameters. The catch is a= =20 >>>>>> dependence on statefulness.=20 >>>>>> >>>>>> SPHINCS+ cannot be considered a valid fallback as it introduces larg= e=20 >>>>>> signature overhead (it's not meant for bitcoin-like use-cases). Any= =20 >>>>>> TPM-based state management would reduce performance and compatibilit= y=20 >>>>>> across architectures. The hash-based nature of SHRINCS is highly=20 >>>>>> SNARK-unfriendly, making them incompatible with emerging L2 ZK rollu= p=20 >>>>>> constructions. Moreover in high-throughput L2 environments, state=20 >>>>>> management, limits on the number of signatures and performance degra= dation=20 >>>>>> proportional to published signatures are critical bottlenecks. >>>>>> >>>>>> On Thu, 2026-01-22 at 14:35 +0000, conduition wrote: >>>>>> >>>>>> Falcon (FN-DSA) relies on discrete gaussian sampling using=20 >>>>>> constant-time floating point arithmetic for signers, which is very h= ard to=20 >>>>>> implement quickly and in constant time (securely). Despite being=20 >>>>>> significantly harder to implement than ML-DSA, it only provides a mi= ld=20 >>>>>> (factor of two or so) improvement in signature + pubkey size. This i= s why=20 >>>>>> we're probably not including FN-DSA in our PQ signature opcode BIP= =20 >>>>>> following BIP360. >>>>>> >>>>>> >>>>>> https://blog.cloudflare.com/nist-post-quantum-surprise/#floating-poi= nts-falcons-achilles >>>>>> >>>>>> While I wouldn't rule out Falcon permanently, I personally feel more= =20 >>>>>> research is needed to explore Falcon, its weaknesses, and how flexib= ly it=20 >>>>>> can be adapted to schemes like CISA, BIP32, and multisignatures. Let= it=20 >>>>>> bake a little longer. >>>>>> >>>>>> If small signatures are your goal, then I'd look into SQIsign=20 >>>>>> , which uses isogeny-based cryptography to=20 >>>>>> produce very small sigs (148b) and pubkeys (65b) using some convolut= ed=20 >>>>>> mathematical tricks. However, much like Falcon, it is still immature= and=20 >>>>>> needs more researchers to optimize its verification, explore its str= engths,=20 >>>>>> and attack its weaknesses.=20 >>>>>> >>>>>> If you want a PQC scheme that's ready *today* and also provides=20 >>>>>> small signatures, I'll point you to XMSS, and Jonas Nick's SHRINCS= =20 >>>>>> proposal=20 >>>>>> .=20 >>>>>> You can configure an unbalanced XMSS tree to get 272 byte signatures= ,=20 >>>>>> potentially smaller if you crank up the parameters. The catch is a= =20 >>>>>> dependence on statefulness.=20 >>>>>> >>>>>> regards, >>>>>> conduition >>>>>> On Wednesday, January 21st, 2026 at 11:09 PM, Giulio Golinelli < >>>>>> golinelli...@gmail.com> wrote: >>>>>> >>>>>> Hi everyone, >>>>>> >>>>>> I am to share a technical demonstration and benchmarking project tha= t=20 >>>>>> integrates the Falcon post-quantum signature scheme (Falcon-512) int= o=20 >>>>>> Bitcoin Core, implemented as a soft-fork within the classic P2WPKH m= ode.=20 >>>>>> This work aims to provide a practical reference for possible future = Falcon=20 >>>>>> adoption, especially as it approaches FIPS standardization. >>>>>> You can find details at this fork=20 >>>>>> . >>>>>> >>>>>> *Why Falcon?* >>>>>> Falcon is a lattice-based, post-quantum digital signature scheme=20 >>>>>> designed to be secure against quantum attacks. Unlike other PQC cand= idates=20 >>>>>> such as SPHINCS+ and ML-DSA, Falcon offers significantly smaller sig= nature=20 >>>>>> and public key sizes, as well as efficient signing and verification = times.=20 >>>>>> It is implemented in pure C and does not require external dependenci= es. >>>>>> >>>>>> *Benchmarking & Results* >>>>>> Aspect Falcon ECDSA >>>>>> Public Key Size (B) 897 33 >>>>>> Signature Size (B) 655 71 >>>>>> Verification Time (=CE=BCs) 57 120 >>>>>> >>>>>> Verification time is more critical than signature creation time in= =20 >>>>>> Bitcoin, since signature creation is performed by clients (wallets),= while=20 >>>>>> nodes focus on verification. >>>>>> >>>>>> *Integration* >>>>>> >>>>>> - Falcon was included into the codebase from the original GitHub= =20 >>>>>> repository. >>>>>> - The build system (CMakeLists.txt) was updated to support Falcon= . >>>>>> - Falcon verification has been soft-fork enabled via a new script= =20 >>>>>> verification flag. >>>>>> >>>>>> *Next Steps & Reference* >>>>>> This project serves as a practical demonstration of Falcon=E2=80=99s= =20 >>>>>> promising performance, highlighting its advantages over currently se= lected=20 >>>>>> post-quantum signature algorithms such as SPHINCS+ and ML-DSA, which= face=20 >>>>>> significant time and space limitations. As Falcon approaches FIPS=20 >>>>>> standardization, this work aims to provide a reference for future ad= option=20 >>>>>> and integration in Bitcoin. >>>>>> >>>>>> Let me know what you think and if this could be of interest for whic= h=20 >>>>>> case I can complement the project by integrating Falcon into all the= other=20 >>>>>> spending paths. I also look forward to development/integration corre= ctions. >>>>>> >>>>>> Best regards, >>>>>> Giulio >>>>>> >>>>>> >>>>>> --=20 >>>>>> You received this message because you are subscribed to the Google= =20 >>>>>> Groups "Bitcoin Development Mailing List" group. >>>>>> To unsubscribe from this group and stop receiving emails from it,=20 >>>>>> send an email to bitcoindev+...@googlegroups.com. >>>>>> >>>>> To view this discussion visit=20 >>>>>> https://groups.google.com/d/msgid/bitcoindev/2e4abb5a847ab9d78857aee= 2fded500a234f68a6.camel%40gmail.com=20 >>>>>> >>>>>> . >>>>>> >>>>> --=20 >>>> You received this message because you are subscribed to the Google=20 >>>> Groups "Bitcoin Development Mailing List" group. >>>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>>> an email to bitcoindev+...@googlegroups.com. >>>> To view this discussion visit=20 >>>> https://groups.google.com/d/msgid/bitcoindev/46faf0c0-d60d-49a4-83c5-8= fe03f11c89dn%40googlegroups.com=20 >>>> >>>> . >>>> >>> >>> >>> --=20 >>> >>> --=20 >>> --- >>> Abra=C3=A7os >>> C=C3=A1ssio Gusson >>> >>> --=20 >>> You received this message because you are subscribed to the Google=20 >>> Groups "Bitcoin Development Mailing List" group. >>> To unsubscribe from this group and stop receiving emails from it, send= =20 >>> an email to bitcoindev+...@googlegroups.com. >>> >> To view this discussion visit=20 >>> https://groups.google.com/d/msgid/bitcoindev/CAEQmO3h7Ao4mu2xfC2qE%2B4E= cxhES-VBEG2s2LRN6msWELh19NA%40mail.gmail.com=20 >>> >>> . >>> >> --=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/= 4b0eda09-32c0-4419-a691-edacad231865n%40googlegroups.com. ------=_Part_159809_1211441127.1769530040093 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi all,

I don't think arithmetic circuit op= timization for SNARKs should be a main course for the PQ transition. Maybe = it could be a dessert if we have appetite for it later.

I am confident that no ZK-SNARK will ever make it into consensus on= Bitcoin unless it has transparent setup, and I doubt a ZK-SNARK will survi= ve long term if it is not quantum-secure. AFAIK that limits our options to = ZK-STARKs (correct me if you know of any other transparent PQ-secure ZK-SNA= RK).

In my admittedly shallow foray into=C2=A0ZK-STARKs, the biggest p= roblem I found is the scaling floor of STARKs. Simple proofs over small cir= cuits have very large communication complexity (hundreds of kilobytes) comp= ared to their classical witnesses (a few bytes). However, as the circuit ga= te depth grows, communication complexity grows as O(n log n) (see page 12 o= f this paper=C2=A0for a pr= etty graph), which is really awesome. Even the biggest STARKs don't = seem to exceed 1MB.=C2=A0This makes STARKS most suitable for very large com= putations which would either be impractical to recompute naively, or imprac= tical to store classical witness data for. Common examples are zk-rollups, = as Giulio pointed out, or chain validity proofs like ZeroSync.=C2=A0

The mai= n point I want to stress is that for STARKs to be useful for PQ signature a= ggregation, we need to aggregate a lot of signatures at once. Ethan Heilman played with this idea.
<= br />
Or you could avoid uploading the STARK proof to th= e chain at all.=C2=A0See t= his recent paper by Nick, Eagen, and Linus=C2=A0called "Shielded CSV", = which describes a (non-quantum secure) way to use recursive ZK proofs to ma= ke payments on Bitcoin with perfect privacy, without needing to post the fu= ll ZK proofs to the network. Only a payment's recipient needs to see the pr= oof. Lots of good ideas to explore there for any who want to make a quantum= -secure CSV protocol.

As for uploading STA= RKs directly to the chain, to be worth our while in terms of blockspace sav= ings we'd need to aggregate at least a few dozen PQ signatures per proof...= hundreds of sigs if the PQ scheme is more succinct like Falcon. Because ST= ARKs scale so well for the verifier, it doesn't really matter to the verifi= er how big the computation is - Proof sizes stay capped below the megabyte = range, and verifier runtime remains very fast. The choice of computation matters far more to the prover, who will have to spend minutes or hour= s of heavy compute time proving it, depending on circuit size. Unless there= exists some obvious demand to make these hypothetical PQ signature provers= very fas,. I don't see any reason to use arithmetic circuit size as a high= weight metric for our PQ signature scheme choices.

<= div>Also, remember that optimizing for arithmetic circuit size and ZK prove= r efficiency sometimes means hobbling classical computational efficiency. <= a href=3D"https://ethresear.ch/t/performance-of-rescue-and-poseidon-hash-fu= nctions/7161">The Poseidon hash function is about an order of magnitude slo= wer than SHA2, for example.

Mind you, S= TARKs is still a young field with active research. For example there's=C2= =A0Circle STARKs=C2=A0= which improve STARK proving time. I recently spoke with a grad student who = is considering a research project on the application of ZK technologies to = post-quantum signature schemes like SPHINCS. I know he lurks on this list, = so maybe he'd have some more nuanced opinions to share.
PS. I'm very curious to know how the arithmetized circui= t sizes of different signing schemes compares, e.g. SPHINCS vs XMSS vs Dili= thium vs EC Schnorr. If anyone has data on that please pipe in!
<= br />

regards,
conduition
<= div>


On Monday, January 26, 2026 at 8:24:26= =E2=80=AFAM UTC-7 waxwing/ AdamISZ wrote:
>=C2=A0I support the idea that SNARK/S= TARK-friendliness can not be a crucial=20 point, as it is not currently supported, but can be an argument=C2=A0for=20 tie-breaking cases.

It's kind of contextual, r= ight: it's a naturally correct default position that "one shouldn&= #39;t impose arbitrary requirements on new PQ schemes that are not in place= for even the existing schnorr/ecdsa schemes, all the more so with respect = to speculative concepts around offchain transacting systems that aren't= proven or don't even exist in prototype form". But the "cont= extual" here is: does the proposed QC scheme have an enormous onchain = footprint (or verification cost) without any offsetting quality that could = ameliorate what that implies about transaction throughputs (or centralizati= on pressures)? That's why I mentioned batched (I should have said aggre= gated) signing and CISA, even though it might seem like a bit of a side iss= ue. In case we really are looking at 20x multipliers and there is *no* amel= iorating factor then ... it feels hard to support a move in that direction,= except of course, in extremis.

A natural counterp= oint might be: "we don't have some set-in-stone plan to develop an= d support only one PQ scheme, so if one is proposed and prototyped which ha= s no scaling amelioration, it's OK, we're not outlawing a future be= tter version".

Another natural counterpoint m= ight be "doing anything remotely viable is hard enough, so *demanding*= some compatibility with STARK or some PQ SNARK is kind of ridiculous"= . Fair :)

May I also ask whether support for adapt= ors is considered in scope (or indeed, do any of the plausible candidates h= ave this property?)? I guess you'd consider it out of scope, though it&= #39;d be an interesting detail.

AdamISZ/waxwing
On= Monday, January 26, 2026 at 9:37:56=E2=80=AFAM UTC-3 Mikhail Kudinov wrote= :
The= investigation of Lattice-Based approaches is on the table, so I think we w= ill be able to make a thoughtful comparison at some point. I support the id= ea that SNARK/STARK-friendliness can not be a crucial point, as it is not c= urrently supported, but can be an argument=C2=A0for tie-breaking cases.=C2= =A0=C2=A0

All pairing-based schemes are broken by a quantum computer= , yes. STARKs are plausibly post-quantum. There are some schemes based on L= attices as well.=C2=A0

The QKD problems are not important for our di= scussion; they do not affect PQ transition.

Best,
Mike=C2=A0
On Sun, Jan 25, 2026 at 11:44=E2=80=AFPM cass= io gusson <cassio...@gmail.com> wrote:
hey guys

I don't know if this is imp= ortant for the implementation being discussed, but I think the study that i= dentified a flaw in quantum key distribution (QKD) is worthwhile.

https://ie= eexplore.ieee.org/document/11223709

Best regards
C=C3=A1ssio = Gusson

Em s=C3=A1b., 24 de jan. de 2026 =C3=A0s 17:12, waxwing/ AdamISZ <= ekag...@gmail.com> escreveu:
Hi Mike,

<= div>> It is also a question: how much weight should we put on adopting a= n=20 explicitly SNARK-friendly signature scheme? While such compatibility is=20 clearly advantageous, it does not seem to me to be=C2=A0a decisive point on= =20 its own. What would you say?

Does it depend on wha= t we really mean by SNARK, apart from the literal definition?
Wha= t SNARK schemes are we thinking of that are post quantum? I presume I can s= ay "all the pairings based SNARKs (and the DLOG based ones) are not qu= antum resistant". Are STARKs the only realistic option in this scenari= o? I am enormously ignorant about STARKs, but I do seem to recall that they= have large proofs, so at least in theory that's a problem for such pla= nning?

Or maybe there's another PQ SNARK schem= e that I'm just unaware of.

I guess this is or= thogonal to the point you're raising about arithmetic-circuit friendly = hash functions like Poseidon, though. That part I find a bit brain-melting = because: what mechanism is assumed to exist to translate a STARK or SNARK p= roof into an onchain effect? If there was say a STARK op-code then, job don= e. You'd just somehow have to have sufficiently small STARK proofs whic= h is AIUI not trivial, even with nice hash functions. If not, we're bac= k to the current hyper-sophisticated scenarios of things like Glock and BAB= E where you use garbled circuits, witness encryption, and also need somethi= ng like the adaptor primitive of "swap signature for secret" whic= h we currently get kind of "for free" in Schnorr with the lineari= ty. I suppose there might be alternatives (e.g. HTLC instead of PTLC) that = might be more clunky, but viable. And all of that is of course "fraud = proof" style, with "slashing", and not anywhere near as clea= n a design as "just verify the STARK".

H= ow does one take the 10000ft view on this needed to make a design decision?= Obviously I don't know, at all, just raising points here. I guess the = most interesting one is: "is STARK realistically the only game in town= here?".

Cheers,
AdamISZ/waxwing
On Fri= day, January 23, 2026 at 1:34:36=E2=80=AFPM UTC-3 Mikhail Kudinov wrote:
<= div dir=3D"ltr">Hi everyone,
I am happy that the discussion on the PQ to= pic is active. I wanted to add my view on the raised issues.=C2=A0

F= or the=C2=A0fallback in SHRINCS, one option is to use SPHINCS+ as a fallbac= k with a limited number of signatures. By setting an upper bound as large a= s 2^30 or 2^40, the signature size can be significantly reduced, and the sc= heme would only be invoked in exceptional circumstances. In most realistic = scenarios, the fallback would consist of generating a single signature to m= ove assets to a new address. As for the statefulness problems, I agree that= this is an important drawback that we should keep in mind.

The SHA-= based SPHINCS+ is indeed not particularly efficient in SNARK settings. But = one could replace the hash functions with SNARK-friendly alternatives (for = example, Poseidon) in the future, which will make it much, much=C2=A0more e= fficient.

It is also a question: how much weight should we put on ad= opting an explicitly SNARK-friendly signature scheme? While such compatibil= ity is clearly advantageous, it does not seem to me to be=C2=A0a decisive p= oint on its own. What would you say?
I am also unsure to what extent Fal= con can be considered SNARK-friendly. Has there been any research in this d= irection, or are there benchmarks evaluating its performance in SNARK envir= onments?

Finally, regarding SQIsign: although the signature sizes ar= e remarkable, I agree that we need more time for the scheme to mature befor= e considering adoption.

Best,
Mike

On Fri, Jan 23, 2026 at 3:03=E2=80=AFPM Giuli= o Golinelli <golinelli...@gmail.com> wrote:
Falcon (FN= -DSA) relies on discrete gaussian sampling using constant-time floating poi= nt arithmetic for signers, which is very hard to implement quickly and in c= onstant time (securely).
This is true for the first Falcon version published= (randomized mode of operation). This implementation uses the author-recomm= ended deterministic Falcon mode (see=C2=A0author=E2=80= =99s notes)=C2=A0which uses software floating-point emulation . This el= iminates side-channel risks associated with non-constant-time hardware FPUs= . It is also SNARK-friendly and overcomes portability limitation. While thi= s sacrifices the performance optimizations of true FPUs, signing speed is n= ot critical in Bitcoin, where verification dominates node activity.<= /div>

If small signatures are your goal, then I'd look into= =C2=A0SQIsign
This would be go= od like many other PQ exotic schemes but all of these are far from being st= andardized soon.

If you want a PQC scheme that's rea= dy=C2=A0today=C2=A0and also provides small signatures, = I'll point you to XMSS, and=C2=A0Jonas Nick's SHRI= NCS proposal. You can configure an unbalanced XMSS tree to get 272 byte= signatures, potentially smaller if you crank up the parameters. The catch = is a dependence on statefulness.=C2=A0
SPHINCS+ cannot be considered a valid= fallback as it introduces large signature overhead (it's not meant for= bitcoin-like use-cases). Any TPM-based state management would reduce perfo= rmance and compatibility across architectures. The hash-based nature of SHR= INCS is highly SNARK-unfriendly, making them incompatible with emerging L2 = ZK rollup constructions. Moreover in high-throughput L2 environments, state= management, limits on the number of signatures and performance degradation= proportional to published signatures are critical bottlenecks.

On Thu, 2026-01-22 at 14:35 +0000,= conduition wrote:
Fal= con (FN-DSA) relies on discrete gaussian sampling using constant-time float= ing point arithmetic for signers, which is very hard to implement quickly a= nd in constant time (securely). Despite being significantly harder to imple= ment than ML-DSA, it only provides a mild (factor of two or so) improvement= in signature + pubkey size. This is why we're probably not including F= N-DSA in our PQ signature opcode BIP following BIP360.

https://blog.cloudflare.com/nist-post= -quantum-surprise/#floating-points-falcons-achilles

While I wouldn't rule out Falcon permanently, I pers= onally feel more research is needed to explore Falcon, its weaknesses, and = how flexibly it can be adapted to schemes like CISA, BIP32, and multisignat= ures. Let it bake a little longer.

If small si= gnatures are your goal, then I'd look into SQIsign, which uses isogeny-based cryptography to produce very s= mall sigs (148b) and pubkeys (65b) using some convoluted mathematical trick= s. However, much like Falcon, it is still immature and needs more researche= rs to optimize its verification, explore its strengths, and attack its weak= nesses.=C2=A0

If you want a PQC scheme that'= s ready today=C2=A0and also provides small signatures, I'll poin= t you to XMSS, and Jonas Nick's SHRINCS proposal. You can configu= re an unbalanced XMSS tree to get 272 byte signatures, potentially smaller = if you crank up the parameters. The catch is a dependence on statefulness.= =C2=A0

regards,
conduition
On Wednesday, January 2= 1st, 2026 at 11:09 PM, Giulio Golinelli <golinelli..= .@gmail.com> wrote:

Hi everyone,
I am to share a technical demonstration and benchmarking project that= integrates the Falcon post-quantum signature scheme (Falcon-512) into Bitc= oin Core, implemented as a soft-fork within the classic P2WPKH mode. This w= ork aims to provide a practical reference for possible future Falcon adopti= on, especially as it approaches FIPS standardization.
You can find detai= ls at this fork.

Why Falcon?
Falcon is a lattice-based, post-quantum digital si= gnature scheme designed to be secure against quantum attacks. Unlike other = PQC candidates such as SPHINCS+ and ML-DSA, Falcon offers significantly sma= ller signature and public key sizes, as well as efficient signing and verif= ication times. It is implemented in pure C and does not require external de= pendencies.

Benchmarking & Results
Aspect = Falcon ECDSA
Public Key Size (B) 897 33
Signature Size (B) 655 71
Verification Time (=CE=BCs) 57 120
<= br>Verification time is more critical than signature creation time in Bitco= in, since signature creation is performed by clients (wallets), while nodes= focus on verification.

Integration
  • Falcon was included into the codebase from the original GitHub repos= itory.
  • The build= system (CMakeLists.txt) was updated to support Falcon.
  • Falcon verification has been soft-f= ork enabled via a new script verification flag.
= Next Steps & Reference
This project serves as a practical demonstration of Falcon=E2=80=99s = promising performance, highlighting its advantages over currently selected = post-quantum signature algorithms such as SPHINCS+ and ML-DSA, which face s= ignificant time and space limitations. As Falcon approaches FIPS standardiz= ation, this work aims to provide a reference for future adoption and integr= ation in Bitcoin.

Let me know what you think and if this could be of= interest for which case I can complement the project by integrating Falcon= into all the other spending paths. I also look forward to development/inte= gration corrections.

Best regards,
Giulio


--
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+...@googlegroups.com.
<= /blockquote>

--
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+...@googlegroups.com.
To view this discussion visit https= ://groups.google.com/d/msgid/bitcoindev/46faf0c0-d60d-49a4-83c5-8fe03f11c89= dn%40googlegroups.com.


--

--
---
Abra=C3=A7os
C=C3=A1ssio Gusson

--
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+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAEQ= mO3h7Ao4mu2xfC2qE%2B4EcxhES-VBEG2s2LRN6msWELh19NA%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/bitcoind= ev/4b0eda09-32c0-4419-a691-edacad231865n%40googlegroups.com.
------=_Part_159809_1211441127.1769530040093-- ------=_Part_159808_1161651692.1769530040093--