Delivery-date: Wed, 19 Feb 2025 07:57:29 -0800 Received: from mail-qt1-f186.google.com ([209.85.160.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 1tkmS0-0004cz-G1 for bitcoindev@gnusha.org; Wed, 19 Feb 2025 07:57:29 -0800 Received: by mail-qt1-f186.google.com with SMTP id d75a77b69052e-471f4381c1esf68633301cf.2 for ; Wed, 19 Feb 2025 07:57:28 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1739980642; x=1740585442; 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:message-id:to:from:date:sender:from:to:cc:subject:date :message-id:reply-to; bh=rq1v0xALieu2vzaeXQECKXg0Ep+OYR53RfDASvexD7E=; b=lMR8CfRyAWTWyHVn+J2UaVNNvJ5qP07EqA0RJRNizqm536hJD7JwVjEnypGEqb8SFQ lE+CcOt9N8gI6tG420t414rTqFSFJTYA5a0hdWbB8k+cgP+rwxvzvvH+M7aBbJnR13BG 5u+Klu4kCU6yOEuKDUcB3qKH8EZhlgDhBlLXytRBoD+pu0Ry9pZiwlTUCl4Ei7avroRM se3DoQp1e1kofPm1fUpBpnC5IIwtgNdFRCvPL21CC/lcoixPzYEiWBq1CKd1i6VmogAf 6VJyfX8u7+0p69ZX+uuB4K9Bkgaj+Fk0/OhFnSK7NC+5oQwLV/2kqQZkBMGiKOyNUHdh wD0A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1739980642; x=1740585442; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:message-id:to:from:date:x-beenthere:x-gm-message-state :sender:from:to:cc:subject:date:message-id:reply-to; bh=rq1v0xALieu2vzaeXQECKXg0Ep+OYR53RfDASvexD7E=; b=wm0yDBz0hVIZY7VFooPLluAdmsRPDHlNacBVnNd/2CLYaFYfDdL/fOr1czjR7E9ulY pD17ih6zaEKblIxdKdi4bwNa3wAjKNVP+r6O/0QdKQDo68OTDNHvN6skRV6O3hNyjQmP deShLaHtwVUyjMFT6ygnOCI2/Rq1MIvwEBFQpKEcPloW3QkvWtE+Q0rCjXpVyxOPRD46 RwQ9zW8N0tEI6jj+3BpXSHkdjieFKKUNklpSRa3VF7uAiTaIwiAjdhC4GD3T0oPjx+SY +yoPFE72pfd8DnYP3XmDO5PzSy2wVYsJLsO7zf7Jrp6le5ERTVic7/Gwq2oOa6gtCZ3a GWdQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWG1mo22DwiQFWGBoZQlzZwbhJY07fNCuWPnErMZsFYsx29vnef0hA0iyp5joBeekFqfrIgb5YHUJsR@gnusha.org X-Gm-Message-State: AOJu0YzJq85mcMNmr26yPq/bAd+xCZ0WcMY1k0d8vLBNmEjPDQtiazcg uDBplKvDI8R96Phc+1709ciF8BNxQGKK9kQiIGjNBFyT0R+hSByM X-Google-Smtp-Source: AGHT+IHpFop8SfN6a+A78xVw1/dBk00/1iFisC9ZPaEMtmTE4tmBJaL5UOquqR6s6ZLb7b54OFdAQg== X-Received: by 2002:a05:622a:1814:b0:471:cebf:c364 with SMTP id d75a77b69052e-47208270299mr61772581cf.14.1739980642401; Wed, 19 Feb 2025 07:57:22 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVGAb15GKhoxag+LByN7T7kY9Yb4HwttW4kzQX4LssJOHw== Received: by 2002:ac8:7dd3:0:b0:472:731:a5a with SMTP id d75a77b69052e-47207311242ls13882481cf.2.-pod-prod-07-us; Wed, 19 Feb 2025 07:57:18 -0800 (PST) X-Received: by 2002:a05:620a:27d2:b0:7c0:61d2:4ec5 with SMTP id af79cd13be357-7c0b5362865mr658988285a.53.1739980638359; Wed, 19 Feb 2025 07:57:18 -0800 (PST) Received: by 2002:a05:620a:3f46:b0:7c0:a61e:8ed0 with SMTP id af79cd13be357-7c0a61e8fb5ms85a; Wed, 19 Feb 2025 07:40:51 -0800 (PST) X-Received: by 2002:a05:690c:46c4:b0:6ef:8dd0:fff9 with SMTP id 00721157ae682-6fb58262370mr155815787b3.8.1739979650914; Wed, 19 Feb 2025 07:40:50 -0800 (PST) Date: Wed, 19 Feb 2025 07:40:50 -0800 (PST) From: Hunter Beast To: Bitcoin Development Mailing List Message-Id: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com> Subject: [bitcoindev] P2QRH / BIP-360 Update MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_173800_1247603409.1739979650454" 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.7 (/) ------=_Part_173800_1247603409.1739979650454 Content-Type: multipart/alternative; boundary="----=_Part_173801_680651586.1739979650454" ------=_Part_173801_680651586.1739979650454 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 BIP= =20 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 compared= =20 to ECC [1]. If it takes 1 second to verify a fully ECC block, it would take= =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 conc= ern=20 which has been brought to my attention. As such, I've decided to deprecate= =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 generally= =20 result in signatures that are still quite large. Chipmunk and RACCOON are= =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 NIST-approved= =20 algorithms to maintain FIPS compliance. That's because HSMs such as those= =20 provided by Securosys already have support for all three algorithms [5],=20 which is essential for secure deployment of federated L2 treasuries. Presently, for multisigs, we have a merkle tree configuration defined for= =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 tree= =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 introduce= =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 the= =20 SegWit v3 output hash could be provided to indicate PQC signature threshold= =20 and total, and those would be hashed and committed to in the output, then= =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 block= =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 prefer= =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 some= =20 additional impetus behind it. One concern Murch brought up is that introducing four new algorithms into= =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 (especially= =20 in its current state lacking implementation maturity), and will help push= =20 the BIP below a certain complexity threshold, making it somewhat easier to= =20 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 100%= =20 certain that all of these algorithms will remain quantum resistant for all= =20 time, so redundancy here is=E2=80=A6 key. Another concern is that NIST level V is overkill. I have less conviction on= =20 this since secp256k1 technically has 128 bits of security due to Pollard's= =20 rho attacks. But if the intention was for 256 bits of security, should=20 level V security be the default? It's difficult for me to say. Perhaps both= =20 level V and level I implementations could be included, but this would be a= =20 deviation from the BIP as presently specified, which defaults to level V=20 security. The disadvantage of including level I support for each algorithm= =20 is that it essentially doubles the complexity of libbitcoinpqc. Ultimately, I hope the default of NIST V and selection of 3 mature=20 NIST-approved algorithms demonstrate a focused, polished, and conservative= =20 proposal. At this point, the major call to action I would like to highlight is simply= =20 the need for more feedback from the community. Please review and provide=20 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, TABConf= =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-rele= ase-overview --=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/= 8797807d-e017-44e2-b419-803291779007n%40googlegroups.com. ------=_Part_173801_680651586.1739979650454 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Dear Bitcoin Dev Community,


A bit over six months after introducing the P2QRH proposal (now B= IP-360), I'm writing to share significant developments and request addition= al feedback on our post-quantum roadmap, and I'd also like to mention a pot= ential P2TRH post-quantum mitigation strategy.


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

https://github.com/cryptoquick/bips/blob/p2qrh/bip-0360.med= iawiki


The revised = BIP-360 draft reflects substantial changes since initial publication, parti= cularly regarding algorithm selection. While we originally considered SQIsi= gn, it has 15,000x slower verification compared to ECC [1]. If it takes 1 s= econd to verify a fully ECC block, it would take 4 hours to validate a bloc= k filled with SQIsign transactions. This has obvious and concerning DDoS im= plications.


While it wo= uld take a long time to sign many thousands of SQIsign t= ransactions as well, the increased time needed to sign the transactions lik= ely 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 because it was brought up in the PR, there's a new cl= ass of algorithms that support signature aggregation, but they generally re= sult in signatures that are still quite large. Chipmunk and RACCOON are goo= d examples [2], [3]. I do expect that to improve with time. It might be wor= thwhile to shorten the list by making signature aggregation a requirement, = so as not to regress too far from Schnorr signatures. That said, I think th= ose capabilities should be introduced in a separate BIP once they're more m= ature and worthwhile.


O= ur current shortlist prioritizes FALCON for its signature aggregation poten= tial, with SPHINCS+ and CRYSTALS-Dilithium as secondary candidates. However= , major technical challenges remain, particularly BIP-32 compatibility issu= es affecting xpub generation in watch-only wallets, as detailed by conduiti= on in another mailing list discussion [4], and also, how we should handle m= ultisig wallets.


Additi= onally, I think it's worthwhile to restrict BIP-360 to NIST-approved algori= thms to maintain FIPS compliance. That's because HSMs such as those provide= d by Securosys already have support for all three algorithms [5], which is = essential for secure deployment of federated L2 treasuries.


Presently, for multisigs, we have a me= rkle tree configuration defined for encumbering the output with multiple ke= ys. While that's efficient, it's a novel construction. I'm not certain we s= hould proceed with the merkle tree commitment scheme-- it needs more scruti= ny. We could use a sort of P2SH approach, just modifying the semantics of O= P_CHECKMULTISIG in a witness script to alias to public keys in the attestat= ion. But that could introduce additional overhead in a signature scheme tha= t already uses a lot more space. Without this, however, we do not yet have = a way specified to indicate thresholds or a locking script for the attestat= ion, 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 an= d I'm open to suggestions. Perhaps two additional bytes at the top level of= the SegWit v3 output hash could be provided to indicate PQC signature thre= shold and total, and those would be hashed and committed to in the output, = then provided in a field in the attestation once spent.


While finalizing PQC selections, I've also= drafted P2TRH as an interim solution to secure Taproot keypath spends with= out disabling them, as Matthew Corallo proposes in the aforementioned maili= ng list thread [4]. The P2TRH approach hashes public keys rather than expos= ing them directly, particularly benefiting:


- MuSig2 Lightning channel implementations

<= p dir=3D"ltr" style=3D"line-height: 1.38; margin-top: 0pt; margin-bottom: 0= pt;">- FROST-based MPC vaults

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


For those interested, take a look at the draft BIP for P2TR= H here: https://github.com/cryptoquick/b= ips/blob/p2trh/bip-p2trh.mediawiki


I have my hands full with P2QRH advocacy and development an= d would prefer to focus on that, but I wanted to introduce P2TRH in case th= at is attractive as the community's preferred solution-- at least for Tapro= ot quantum security. The tradeoff is that it adds 8.25 vB of overhead per i= nput, and key tweaking might have slightly less utility for some applicatio= ns, and it also doesn't protect against short exposure quantum attacks as d= efined in BIP-360.


Retu= rning to P2QRH and what's needed to push it across the finish line...


I still need to finish the t= est vectors. I'm implementing these using a fork of rust-bitcoin and modeli= ng them after Steven Roose's work on BIP-346. I've been told that's not a b= locker for merging the draft, but if it isn't merged by the time I'm finish= ed, hopefully 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-- addin= g too much complexity to the network and to wallets and other applications-= - and I agree.=C2=A0


Ho= pefully this is addressed to some degree by removing SQIsign (especially in= its current state lacking implementation maturity), and will help push the= BIP below a certain complexity threshold, making it somewhat easier to rev= iew.

=C2=A0

= I think it's still important to include multi= ple signature algorithm options for users to select their desired level of = security. It's not 100% certain that all of these algorithms will remain qu= antum resistant for all time, so redundancy here is=E2=80=A6 key.

Another concern is that NIST lev= el V is overkill. I have less conviction on this since secp256k1 technicall= y has 128 bits of security due to Pollard's rho attacks. But if the intenti= on 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 level I implementation= s could be included, but this would be a deviation from the BIP as presentl= y specified, which defaults to level V security. The disadvantage of includ= ing level I support for each algorithm is that it essentially doubles the c= omplexity of libbitcoinpqc.


Ultimately, I hope the default of NIST V and selection of 3 mature NIS= T-approved algorithms demonstrate a focused, polished, and conservative pro= posal.


At this point, t= he major call to action I would like to highlight is simply the need for mo= re feedback from the community. Please review and provide feedback here: https://github.com/bitcoin/bips/pull/1670


I look forward to feedback and opinions on P= 2QRH and P2TRH.


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



[1] https://pqs= hield.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= ] https://docs.securosys.com/tsb/Tutorials/Post-Quantum-Cryptography/pqc-re= lease-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/8797807d-e017-44e2-b419-803291779007n%40googlegroups.com.
------=_Part_173801_680651586.1739979650454-- ------=_Part_173800_1247603409.1739979650454--