Delivery-date: Fri, 21 Feb 2025 02:18:29 -0800
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of lf-lists@mattcorallo.com designates 2620:6e:a000:1::99 as permitted sender) client-ip=2620:6e:a000:1::99;
Message-ID: <737fe7bb-4195-439f-87a9-b6fabd14eeea@mattcorallo.com>
Date: Thu, 20 Feb 2025 17:11:30 -0500
MIME-Version: 1.0
Subject: Re: [bitcoindev] P2QRH / BIP-360 Update
To: Hunter Beast <hunter@surmount.systems>,
 Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com>
Content-Language: en-US
From: Matt Corallo <lf-lists@mattcorallo.com>
In-Reply-To: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"; format=flowed
Content-Transfer-Encoding: quoted-printable
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

If we want to do something like this in the short to medium term, IMO we sh=
ould strip out all the=20
signature schemes that are anything more than quite straightforward in thei=
r security assumptions=20
(i.e. only keep hash-based signatures, maybe just SPHINCS+), only embed the=
m in a taproot leaf, and=20
call it a day.

BIP 32 compatibility isn't a really huge deal if we're talking about an "em=
ergency break glass"=20
kinda setup - most wallets are set up with a root key and can just embed th=
e same PQ pubkey in all=20
of their outputs. The privacy cost is only realized in a break glass case, =
and long before then=20
hopefully whatever we do today is replaced with something better, with the =
knowledge that we'll gain=20
on the way to "then". We'd still want to do it in an opcode so that we can =
do multisig, though.

Matt

On 2/19/25 10:40 AM, Hunter Beast wrote:
> Dear Bitcoin Dev Community,
>=20
>=20
> A bit over six months after introducing the P2QRH proposal (now BIP-360),=
 I'm writing to share=20
> significant developments and request additional feedback on our post-quan=
tum roadmap, and I'd also=20
> like to mention a potential P2TRH post-quantum mitigation strategy.
>=20
>=20
> First, now that there's a BIP number assigned, you can find the update BI=
P here:
>=20
> https://github.com/cryptoquick/bips/blob/p2qrh/bip-0360.mediawiki <https:=
//github.com/cryptoquick/=20
> bips/blob/p2qrh/bip-0360.mediawiki>
>=20
>=20
> The revised BIP-360 draft reflects substantial changes since initial publ=
ication, particularly=20
> regarding algorithm selection. While we originally considered SQIsign, it=
 has 15,000x slower=20
> verification compared to ECC [1]. If it takes 1 second to verify a fully =
ECC block, it would take 4=20
> hours to validate a block filled with SQIsign transactions. This has obvi=
ous and concerning DDoS=20
> implications.
>=20
>=20
> While it would take a long time to signmany thousands of SQIsign transact=
ions as well, the increased=20
> time needed to sign the transactions likely won=E2=80=99t affect the prac=
ticality of DDoS attacks-- another=20
> concern which has been brought to my attention. As such, I've decided to =
deprecate SQIsign from the BIP.
>=20
>=20
> It's worth mentioning because it was brought up in the PR, there's a new =
class of algorithms that=20
> support signature aggregation, but they generally result in signatures th=
at are still quite large.=20
> Chipmunk and RACCOON are good examples [2], [3]. I do expect that to impr=
ove with time. It might be=20
> worthwhile to shorten the list by making signature aggregation a requirem=
ent, so as not to regress=20
> too far from Schnorr signatures. That said, I think those capabilities sh=
ould be introduced in a=20
> separate BIP once they're more mature and worthwhile.
>=20
>=20
> Our current shortlist prioritizes FALCON for its signature aggregation po=
tential, with SPHINCS+ and=20
> CRYSTALS-Dilithium as secondary candidates. However, major technical chal=
lenges remain, particularly=20
> BIP-32 compatibility issues affecting xpub generation in watch-only walle=
ts, as detailed by=20
> conduition in another mailing list discussion [4], and also, how we shoul=
d handle multisig wallets.
>=20
>=20
> Additionally, I think it's worthwhile to restrict BIP-360 to NIST-approve=
d algorithms to maintain=20
> FIPS compliance. That's because HSMs such as those provided by Securosys =
already have support for=20
> all three algorithms [5], which is essential for secure deployment of fed=
erated L2 treasuries.
>=20
>=20
> Presently, for multisigs, we have a merkle tree configuration defined for=
 encumbering the output=20
> with multiple keys. While that's efficient, it's a novel construction. I'=
m not certain we should=20
> proceed with the merkle tree 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 s=
cript to alias to public=20
> keys in the attestation. But that could introduce additional overhead in =
a signature scheme that=20
> already uses a lot more space. Without this, however, we do not yet have =
a way specified to indicate=20
> thresholds or a locking script for the attestation, as it is designed to =
be purposely limited, so as=20
> specified it is only capable of n/n multisig. I consider m/n multisigs to=
 be the single largest=20
> obvious omission in the spec right now. It definitely needs more thought =
and I'm open to=20
> suggestions. Perhaps two additional bytes at the top level of the SegWit =
v3 output hash could be=20
> provided to indicate PQC signature threshold and total, and those would b=
e hashed and committed to=20
> in the output, then provided in a field in the attestation once spent.
>=20
>=20
> While finalizing PQC selections, I've also drafted P2TRH as an interim so=
lution to secure Taproot=20
> keypath spends without disabling them, as Matthew Corallo proposes in the=
 aforementioned mailing=20
> list thread [4]. The P2TRH approach hashes public keys rather than exposi=
ng them directly,=20
> particularly benefiting:
>=20
>=20
> - MuSig2 Lightning channel implementations
>=20
> - FROST-based MPC vaults
>=20
> - High-value transactions using private pools that don't reveal the block=
 template
>=20
>=20
> For those interested, take a look at the draft BIP for P2TRH here: https:=
//github.com/cryptoquick/=20
> bips/blob/p2trh/bip-p2trh.mediawiki <https://github.com/cryptoquick/bips/=
blob/p2trh/bip-p2trh.mediawiki>
>=20
>=20
> I have my hands full with P2QRH advocacy and development and would prefer=
 to focus on that, but I=20
> wanted to introduce P2TRH in case that is attractive as the community's p=
referred solution-- at=20
> least for Taproot quantum security. The tradeoff is that it adds 8.25 vB =
of overhead per input, and=20
> key tweaking might have slightly less utility for some applications, and =
it also doesn't protect=20
> against short exposure quantum attacks as defined in BIP-360.
>=20
>=20
> Returning to P2QRH and what's needed to push it across the finish line...
>=20
>=20
> I still need to finish the test vectors. I'm implementing these using a f=
ork of rust-bitcoin and=20
> modeling them after Steven Roose's work on BIP-346. I've been told that's=
 not a blocker for merging=20
> the draft, but if it isn't merged by the time I'm finished, hopefully tha=
t will provide some=20
> additional impetus behind it.
>=20
>=20
> One concern Murch brought up is that introducing four new algorithms into=
 the network was too many--=20
> adding too much complexity to the network and to wallets and other applic=
ations-- and I agree.
>=20
>=20
> Hopefully this is addressed to some degree by removing SQIsign (especiall=
y in its current state=20
> lacking implementation maturity), and will help push the BIP below a cert=
ain complexity threshold,=20
> making it somewhat easier to review.
>=20
> I think it's still important to include multiple signature algorithm opti=
ons for users to select=20
> their desired level of security. It's not 100% certain that all of these =
algorithms will remain=20
> quantum resistant for all time, so redundancy here is=E2=80=A6 key.
>=20
>=20
> Another concern is that NIST level V is overkill. I have less conviction =
on this since secp256k1=20
> technically has 128 bits of security due to Pollard's rho attacks. But if=
 the intention was for 256=20
> bits of security, should 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 deviation from the BIP as=20
> presently specified, which defaults to level V security. The disadvantage=
 of including level I=20
> support for each algorithm is that it essentially doubles the complexity =
of libbitcoinpqc.
>=20
>=20
> Ultimately, I hope the default of NIST V and selection of 3 mature NIST-a=
pproved algorithms=20
> demonstrate a focused, polished, and conservative proposal.
>=20
>=20
> At this point, the major call to action I would like to highlight is simp=
ly the need for more=20
> feedback from the community. Please review and provide feedback here: htt=
ps://github.com/bitcoin/=20
> bips/pull/1670 <https://github.com/bitcoin/bips/pull/1670>
>=20
>=20
> I look forward to feedback and opinions on P2QRH and P2TRH.
>=20
>=20
> P.S. I'll be advocating for BIP-360 at OP_NEXT in VA, btc++ in Austin, Co=
nsensus in Toronto, and BTC=20
> 25 in Las Vegas, and later this year, TABConf in Atlanta.
>=20
>=20
>=20
> [1] https://pqshield.github.io/nist-sigs-zoo
>=20
> [2] https://eprint.iacr.org/2023/1820.pdf
>=20
> [3] https://eprint.iacr.org/2024/1291.pdf
>=20
> [4] https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/7uu4dZNgAwAJ
>=20
> [5] https://docs.securosys.com/tsb/Tutorials/Post-Quantum-Cryptography/pq=
c-release-overview
>=20
>=20
> --=20
> You received this message because you are subscribed to the Google Groups=
 "Bitcoin Development=20
> Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an=
 email to=20
> bitcoindev+unsubscribe@googlegroups.com <mailto:bitcoindev+unsubscribe@go=
oglegroups.com>.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoinde=
v/8797807d-e017-44e2-=20
> b419-803291779007n%40googlegroups.com <https://groups.google.com/d/msgid/=
bitcoindev/8797807d-=20
> e017-44e2-b419-803291779007n%40googlegroups.com?utm_medium=3Demail&utm_so=
urce=3Dfooter>.

--=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/=
737fe7bb-4195-439f-87a9-b6fabd14eeea%40mattcorallo.com.