Delivery-date: Thu, 20 Feb 2025 17:44:27 -0800 Received: from mail-yb1-f186.google.com ([209.85.219.186]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tlI5Z-0006VO-Fz for bitcoindev@gnusha.org; Thu, 20 Feb 2025 17:44:27 -0800 Received: by mail-yb1-f186.google.com with SMTP id 3f1490d57ef6-e5dc2822ae6sf2277621276.1 for ; Thu, 20 Feb 2025 17:44:24 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1740102259; x=1740707059; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=B0oXU4WTGHI2web6tetPg0RyHZkR2XAXiKuUZuisqNw=; b=wFW09ef3BThmNXskrUnJ1EaUNbpc6+qL0UTEFWkhLCPpcmnxqxSIsIdF2x7Td4Uw3s 6xlH4qF60q8K6tXA77eQuQiGxMe+i/SNg6lfy4u4tV5krE5ZqoRelw1JWQ6jCgL00qaV xBHFTciwgekG/Vi+eRBvCSkiMKdNgNtepqjGtJJcaSF1R1dy8fpA/i2/XG75QtxF+Ips mwv9kFxgAyRoLPy3cH1NIPxbkj3UnGPmkwakmceAVt6DRvY99y6VXB091TbCjOCMcLSB MxZM6lCAXDlbrOm/rqYHIF4mLzOMlx4T31HJvGx9uuoNec6KUDL7lmFIPEXtlsvFqBvX Zq2g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740102259; x=1740707059; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=B0oXU4WTGHI2web6tetPg0RyHZkR2XAXiKuUZuisqNw=; b=V3gCdr8bYAas4GKH1WxYYTwiE11rLWKAXDSsJkDGoQTjpkCEBvJxE/hw4jopCFia2r DXujIioRBgieA0K/p1VrcIMDHxrcHKSE6JwrGsTSOBRbkL3W+A7Qy4FG4vqm5M4DyhOn Xc+W1hSwnn47CUdNbalRT5K1UUYuJunmPXoNRND4vX9WodvN7dZ2ogShcdTzxTQsprFn Kp6UOwe3RJEEBOfrg50BGzHffYJQV3qtIBF+8/O/1Q5ArQdOeUxIEwp6Zq7WuGHQHLru 7aVo+5TrI5Zt0BKRAumo/SFhOe/9uBKyHjJ9DbxNtw8MxOne0pDZ7MEh9nnRZMuzdLRt yFzQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCU16+JXJp/8U68n8hnn/jozsBMCgeH1IXaTjrcrO2iW343KKNgIkzC0Oh4g1cwRUUvN/GW/d851N7/Z@gnusha.org X-Gm-Message-State: AOJu0YwXq/oBbYgQ887uQMWmYnsv5uzsADxj5acVIqBslbqQlOW890Mt 0yREvw2GvWo51mckqMljIJSndJbNFThUjgtat058UbZeAhTl+gZK X-Google-Smtp-Source: AGHT+IHyFEazvZKk7fOLs+VQClt5yQ2jTOdIkHNHxcE05/f/gax75/4yvqTh7rpUtdKaQnJRe+mGrg== X-Received: by 2002:a05:6902:10ce:b0:e57:d3c8:554b with SMTP id 3f1490d57ef6-e5e246015e7mr1190498276.22.1740102258909; Thu, 20 Feb 2025 17:44:18 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVHxtDkxy9PW1FEtVgb6o+bsiGg7mdmq03v5NbzAiwFiGg== Received: by 2002:a25:aa26:0:b0:e5b:3fa5:8102 with SMTP id 3f1490d57ef6-e5ea78e6070ls192411276.2.-pod-prod-03-us; Thu, 20 Feb 2025 17:44:15 -0800 (PST) X-Received: by 2002:a05:690c:6888:b0:6fb:b36b:300f with SMTP id 00721157ae682-6fbcc81788emr9810757b3.27.1740102255029; Thu, 20 Feb 2025 17:44:15 -0800 (PST) Received: by 2002:a81:be1a:0:b0:6f9:77a0:782b with SMTP id 00721157ae682-6fb44a6cc88ms7b3; Wed, 19 Feb 2025 14:58:05 -0800 (PST) X-Received: by 2002:a05:690c:4904:b0:6ef:8c41:defc with SMTP id 00721157ae682-6fb582803a0mr215571807b3.11.1740005880056; Wed, 19 Feb 2025 14:58:00 -0800 (PST) Date: Wed, 19 Feb 2025 14:57:59 -0800 (PST) From: Hunter Beast To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com> Subject: Re: [bitcoindev] P2QRH / BIP-360 Update MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_202314_444941088.1740005879177" X-Original-Sender: hunter@surmount.systems 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.0 (/) ------=_Part_202314_444941088.1740005879177 Content-Type: multipart/alternative; boundary="----=_Part_202315_1117001371.1740005879177" ------=_Part_202315_1117001371.1740005879177 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > HD wallets libbitcoinpqc will require key entropy to be provided, so it should=20 maintain compatibility with that feature of HD wallets, so that's not a=20 concern. The larger problem is for full BIP-32 support, I'm not really sure= =20 how xpubs or watch-only wallets will work. > Security levels You're not the first person to say that NIST V is overkill... I'll update= =20 the spec for NIST I. If more security is desired, they can use all three=20 algorithms, plus Schnorr. On Wednesday, February 19, 2025 at 11:47:04=E2=80=AFAM UTC-7 Dustin Ray wro= te: > Thanks for your work on this, it's exciting to watch it move along. > > One item I have not yet addressed yet that is worth discussing is the=20 > hierarchical deterministic seed characteristic of private keys for any of= =20 > the post quantum schemes you have mentioned so far. At present, if FALCON= =20 > is shortlisted, how do you propose to backup private keys? Must a new=20 > wallet backup be made for each new public key that is generated? > > Per your comment on security levels, I agree that your previous proposal= =20 > was absolutely overkill. My personal thought is that we will be just fine= =20 > by matching the current security levels provided by ecdsa, many years of= =20 > scrutiny has shown that this is sufficient. > > > On Wed, Feb 19, 2025 at 7:57=E2=80=AFAM Hunter Beast =20 > wrote: > >> Dear Bitcoin Dev Community, >> >> A bit over six months after introducing the P2QRH proposal (now BIP-360)= ,=20 >> I'm writing to share significant developments and request additional=20 >> feedback on our post-quantum roadmap, and I'd also like to mention a=20 >> potential P2TRH post-quantum mitigation strategy. >> >> First, now that there's a BIP number assigned, you can find the update= =20 >> BIP here: >> >> https://github.com/cryptoquick/bips/blob/p2qrh/bip-0360.mediawiki >> >> The revised BIP-360 draft reflects substantial changes since initial=20 >> publication, particularly regarding algorithm selection. While we=20 >> originally considered SQIsign, it has 15,000x slower verification compar= ed=20 >> to ECC [1]. If it takes 1 second to verify a fully ECC block, it would t= ake=20 >> 4 hours to validate a block filled with SQIsign transactions. This has= =20 >> obvious and concerning DDoS implications. >> >> While it would take a long time to sign many thousands of SQIsign=20 >> transactions as well, the increased time needed to sign the transactions= =20 >> likely won=E2=80=99t affect the practicality of DDoS attacks-- another c= oncern=20 >> which has been brought to my attention. As such, I've decided to depreca= te=20 >> SQIsign from the BIP. >> >> It's worth mentioning because it was brought up in the PR, there's a new= =20 >> class of algorithms that support signature aggregation, but they general= ly=20 >> result in signatures that are still quite large. Chipmunk and RACCOON ar= e=20 >> good examples [2], [3]. I do expect that to improve with time. It might = be=20 >> worthwhile to shorten the list by making signature aggregation a=20 >> requirement, so as not to regress too far from Schnorr signatures. That= =20 >> said, I think those capabilities should be introduced in a separate BIP= =20 >> once they're more mature and worthwhile. >> >> Our current shortlist prioritizes FALCON for its signature aggregation= =20 >> potential, with SPHINCS+ and CRYSTALS-Dilithium as secondary candidates.= =20 >> However, major technical challenges remain, particularly BIP-32=20 >> compatibility issues affecting xpub generation in watch-only wallets, as= =20 >> detailed by conduition in another mailing list discussion [4], and also,= =20 >> how we should handle multisig wallets. >> >> Additionally, I think it's worthwhile to restrict BIP-360 to=20 >> NIST-approved algorithms to maintain FIPS compliance. That's because HSM= s=20 >> such as those provided by Securosys already have support for all three= =20 >> algorithms [5], which is essential for secure deployment of federated L2= =20 >> treasuries. >> >> Presently, for multisigs, we have a merkle tree configuration defined fo= r=20 >> encumbering the output with multiple keys. While that's efficient, it's = a=20 >> novel construction. I'm not certain we should proceed with the merkle tr= ee=20 >> commitment scheme-- it needs more scrutiny. We could use a sort of P2SH= =20 >> approach, just modifying the semantics of OP_CHECKMULTISIG in a witness= =20 >> script to alias to public keys in the attestation. But that could introd= uce=20 >> additional overhead in a signature scheme that already uses a lot more= =20 >> space. Without this, however, we do not yet have a way specified to=20 >> indicate thresholds or a locking script for the attestation, as it is=20 >> designed to be purposely limited, so as specified it is only capable of = n/n=20 >> multisig. I consider m/n multisigs to be the single largest obvious=20 >> omission in the spec right now. It definitely needs more thought and I'm= =20 >> open to suggestions. Perhaps two additional bytes at the top level of th= e=20 >> SegWit v3 output hash could be provided to indicate PQC signature thresh= old=20 >> and total, and those would be hashed and committed to in the output, the= n=20 >> provided in a field in the attestation once spent. >> >> While finalizing PQC selections, I've also drafted P2TRH as an interim= =20 >> solution to secure Taproot keypath spends without disabling them, as=20 >> Matthew Corallo proposes in the aforementioned mailing list thread [4]. = The=20 >> P2TRH approach hashes public keys rather than exposing them directly,=20 >> particularly benefiting: >> >> - MuSig2 Lightning channel implementations >> >> - FROST-based MPC vaults >> >> - High-value transactions using private pools that don't reveal the bloc= k=20 >> template >> >> For those interested, take a look at the draft BIP for P2TRH here:=20 >> https://github.com/cryptoquick/bips/blob/p2trh/bip-p2trh.mediawiki >> >> I have my hands full with P2QRH advocacy and development and would prefe= r=20 >> to focus on that, but I wanted to introduce P2TRH in case that is=20 >> attractive as the community's preferred solution-- at least for Taproot= =20 >> quantum security. The tradeoff is that it adds 8.25 vB of overhead per= =20 >> input, and key tweaking might have slightly less utility for some=20 >> applications, and it also doesn't protect against short exposure quantum= =20 >> attacks as defined in BIP-360. >> >> Returning to P2QRH and what's needed to push it across the finish line..= . >> >> I still need to finish the test vectors. I'm implementing these using a= =20 >> fork of rust-bitcoin and modeling them after Steven Roose's work on=20 >> BIP-346. I've been told that's not a blocker for merging the draft, but = if=20 >> it isn't merged by the time I'm finished, hopefully that will provide so= me=20 >> additional impetus behind it. >> >> One concern Murch brought up is that introducing four new algorithms int= o=20 >> the network was too many-- adding too much complexity to the network and= to=20 >> wallets and other applications-- and I agree.=20 >> >> Hopefully this is addressed to some degree by removing SQIsign=20 >> (especially in its current state lacking implementation maturity), and w= ill=20 >> help push the BIP below a certain complexity threshold, making it somewh= at=20 >> easier to review. >> >> =20 >> >> I think it's still important to include multiple signature algorithm=20 >> options for users to select their desired level of security. It's not 10= 0%=20 >> certain that all of these algorithms will remain quantum resistant for a= ll=20 >> time, so redundancy here is=E2=80=A6 key. >> >> Another concern is that NIST level V is overkill. I have less conviction= =20 >> on this since secp256k1 technically has 128 bits of security due to=20 >> Pollard's rho attacks. But if the intention was for 256 bits of security= ,=20 >> should level V security be the default? It's difficult for me to say.=20 >> Perhaps both level V and level I implementations could be included, but= =20 >> this would be a deviation from the BIP as presently specified, which=20 >> defaults to level V security. The disadvantage of including level I supp= ort=20 >> for each algorithm is that it essentially doubles the complexity of=20 >> libbitcoinpqc. >> >> Ultimately, I hope the default of NIST V and selection of 3 mature=20 >> NIST-approved algorithms demonstrate a focused, polished, and conservati= ve=20 >> proposal. >> >> At this point, the major call to action I would like to highlight is=20 >> simply the need for more feedback from the community. Please review and= =20 >> provide feedback here: https://github.com/bitcoin/bips/pull/1670 >> >> I look forward to feedback and opinions on P2QRH and P2TRH. >> >> P.S. I'll be advocating for BIP-360 at OP_NEXT in VA, btc++ in Austin,= =20 >> Consensus in Toronto, and BTC 25 in Las Vegas, and later this year, TABC= onf=20 >> in Atlanta. >> >> >> [1] https://pqshield.github.io/nist-sigs-zoo >> >> [2] https://eprint.iacr.org/2023/1820.pdf >> >> [3] https://eprint.iacr.org/2024/1291.pdf >> >> [4] https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/7uu4dZNgAwAJ >> >> [5]=20 >> https://docs.securosys.com/tsb/Tutorials/Post-Quantum-Cryptography/pqc-r= elease-overview >> >> --=20 >> You received this message because you are subscribed to the Google Group= s=20 >> "Bitcoin Development Mailing List" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n=20 >> email to bitcoindev+...@googlegroups.com. >> To view this discussion visit=20 >> https://groups.google.com/d/msgid/bitcoindev/8797807d-e017-44e2-b419-803= 291779007n%40googlegroups.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/= aa62f885-2807-41af-a672-5b1ff4c0b6b6n%40googlegroups.com. ------=_Part_202315_1117001371.1740005879177 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > HD wallets

libbitcoinpqc will require key entropy= to be provided, so it should maintain compatibility with that feature of H= D wallets, so that's not a concern. The larger problem is for full BIP-32 s= upport, I'm not really sure how xpubs or watch-only wallets will work.

> Security levels

You'= re not the first person to say that NIST V is overkill... I'll update the s= pec for NIST I. If more security is desired, they can use all three algorit= hms, plus Schnorr.

On Wednesday, February 19, 2025 at 11:47:04=E2= =80=AFAM UTC-7 Dustin Ray wrote:
Thanks for your work on this, it= 9;s exciting to watch it move along.

One item I have= not yet addressed yet that is worth discussing is the hierarchical determi= nistic seed characteristic of private keys for any of the post quantum sche= mes you have mentioned so far. At present, if FALCON is shortlisted, how do= you propose to backup private keys? Must a new wallet backup be made for e= ach new public key that is generated?

Per your comme= nt on security levels, I agree that your previous proposal was absolutely o= verkill. My personal thought is that we will be just fine by matching the c= urrent security levels provided by ecdsa, many years of scrutiny has shown = that this is sufficient.


On Wed, Feb 19, 2025 at 7:57=E2=80=AFAM Hunte= r Beast <hun...@surmount.systems> wrote:

De= ar Bitcoin Dev Community,


A bit over six months after introducing = the P2QRH proposal (now BIP-360), I'm writing to share significant deve= lopments and request additional feedback on our post-quantum roadmap, and I= 'd also like to mention a potential P2TRH post-quantum mitigation strat= egy.


First, now that there's a BIP number assigned, you can fi= nd the update BIP here:

https://github.com/cryptoquick/bips/blob/p2= qrh/bip-0360.mediawiki


The revised BIP-360 draft reflects subs= tantial changes since initial publication, particularly regarding algorithm= selection. While we originally considered SQIsign, it has 15,000x slower v= erification compared to ECC [1]. If it takes 1 second to verify a fully ECC= block, it would take 4 hours to validate a block filled with SQIsign trans= actions. This has obvious and concerning DDoS implications.


<= p dir=3D"ltr" style=3D"line-height:1.38;margin-top:0pt;margin-bottom:0pt"><= span style=3D"font-size:11pt;font-family:Arial,sans-serif;font-variant-nume= ric:normal;font-variant-east-asian:normal;font-variant-alternates:normal;ve= rtical-align:baseline;background-color:transparent;color:rgb(0,0,0)">While = it would take a long time to sign many thousands of S= QIsign transactions as well, the increased time needed to sign the transact= ions likely won=E2=80=99t affect the practicality of DDoS attacks-- another= concern which has been brought to my attention. As such, I've decided = to deprecate SQIsign from the BIP.


It's worth mentioning becau= se it was brought up in the PR, there's a new class of algorithms that = support signature aggregation, but they generally result in signatures that= are still quite large. Chipmunk and RACCOON are good examples [2], [3]. I = do expect that to improve with time. It might be worthwhile to shorten the = list by making signature aggregation a requirement, so as not to regress to= o far from Schnorr signatures. That said, I think those capabilities should= be introduced in a separate BIP once they're more mature and worthwhil= e.


Our current shortlist prioritizes FALCON for its signature aggr= egation potential, with SPHINCS+ and CRYSTALS-Dilithium as secondary candid= ates. However, major technical challenges remain, particularly BIP-32 compa= tibility issues affecting xpub generation in watch-only wallets, as detaile= d by conduition in another mailing list discussion [4], and also, how we sh= ould handle multisig wallets.


Additionally, I think it's worth= while to restrict BIP-360 to NIST-approved algorithms to maintain FIPS comp= liance. That's because HSMs such as those provided by Securosys already= have support for all three algorithms [5], which is essential for secure d= eployment of federated L2 treasuries.


Presently, for multisigs, we= have a merkle tree configuration defined for encumbering the output with m= ultiple keys. While that's efficient, it's a novel construction. I&= #39;m not certain we should proceed with the merkle tree commitment scheme-= - it needs more scrutiny. We could use a sort of P2SH approach, just modify= ing the semantics of OP_CHECKMULTISIG in a witness script to alias to publi= c keys in the attestation. But that could introduce additional overhead in = a signature scheme that already uses a lot more space. Without this, howeve= r, we do not yet have a way specified to indicate thresholds or a locking s= cript for the attestation, as it is designed to be purposely limited, so as= specified it is only capable of n/n multisig. I consider m/n multisigs to = be the single largest obvious omission in the spec right now. It definitely= needs more thought and I'm open to suggestions. Perhaps two additional= bytes at the top level of the SegWit v3 output hash could be provided to i= ndicate PQC signature threshold and total, and those would be hashed and co= mmitted to in the output, then provided in a field in the attestation once = spent.


While finalizing PQC selections, I've also drafted P2TR= H as an interim solution to secure Taproot keypath spends without disabling= them, as Matthew Corallo proposes in the aforementioned mailing list threa= d [4]. The P2TRH approach hashes public keys rather than exposing them dire= ctly, particularly benefiting:


- MuSig2 Lightning channel implemen= tations

- FROST-based MPC vaults

- High-value transactions using = private pools that don't reveal the block template


For those i= nterested, take a look at the draft BIP for P2TRH here: https://github.com/cryptoq= uick/bips/blob/p2trh/bip-p2trh.mediawiki


I have my hands full = with P2QRH advocacy and development and would prefer to focus on that, but = I wanted to introduce P2TRH in case that is attractive as the community'= ;s preferred solution-- at least for Taproot quantum security. The tradeoff= is that it adds 8.25 vB of overhead per input, and key tweaking might have= slightly less utility for some applications, and it also doesn't prote= ct against short exposure quantum attacks as defined in BIP-360.

=

R= eturning to P2QRH and what's needed to push it across the finish line..= .


I still need to finish the test vectors. I'm implementing th= ese using a fork of rust-bitcoin and modeling them after Steven Roose's= work on BIP-346. I've been told that's not a blocker for merging t= he draft, but if it isn't merged by the time I'm finished, hopefull= y that will provide some additional impetus behind it.


One concern= Murch brought up is that introducing four new algorithms into the network = was too many-- adding too much complexity to the network and to wallets and= other applications-- and I agree.=C2=A0


Hopefully this is address= ed to some degree by removing SQIsign (especially in its current state lack= ing implementation maturity), and will help push the BIP below a certain co= mplexity threshold, making it somewhat easier to review.

=C2=A0

I think it's still important to include multiple signature algorithm o= ptions for users to select their desired level of security. It's not 10= 0% certain that all of these algorithms will remain quantum resistant for a= ll time, so redundancy here is=E2=80=A6 key.


Another concern is th= at NIST level V is overkill. I have less conviction on this since secp256k1= technically has 128 bits of security due to Pollard's rho attacks. But= if the intention was for 256 bits of security, should level V security be = the default? It's difficult for me to say. Perhaps both level V and lev= el I implementations could be included, but this would be a deviation from = the BIP as presently specified, which defaults to level V security. The dis= advantage of including level I support for each algorithm is that it essent= ially doubles the complexity of libbitcoinpqc.


Ultimately, I hope = the default of NIST V and selection of 3 mature NIST-approved algorithms de= monstrate a focused, polished, and conservative proposal.


At this = point, the major call to action I would like to highlight is simply the nee= d for more feedback from the community. Please review and provide feedback = here: https://github.com/bitcoin/bips/pull/1670<= /a>


I look forward to feedback and opinions on P2QRH and P2TRH.

= P.S. I'll be advocating for BIP-360 at OP_NEXT in VA, btc++ in Austin, = Consensus in Toronto, and BTC 25 in Las Vegas, and later this year, TABConf= in Atlanta.



[1] https://pqshield.github.= io/nist-sigs-zoo

[2] https://eprint.iacr.org/2023/1= 820.pdf

[3] https://eprint.iacr.org/2024/1291.pdf

[4] https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/7uu4dZNg= AwAJ

[5] https://docs.se= curosys.com/tsb/Tutorials/Post-Quantum-Cryptography/pqc-release-overview


--
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/aa62f885-2807-41af-a672-5b1ff4c0b6b6n%40googlegroups.com.
------=_Part_202315_1117001371.1740005879177-- ------=_Part_202314_444941088.1740005879177--