Subject: [bitcoindev] P2QRH / BIP-360 Update

From: Hunter Beast <[email-masked]>
Date: Wed, 19 Feb 2025 07:40:50 -0800 (PST)

Dear Bitcoin Dev Community,

A bit over six months after introducing the P2QRH proposal (now BIP-360), 
I'm writing to share significant developments and request additional 
feedback on our post-quantum roadmap, and I'd also like to mention a 
potential 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.mediawiki

The revised BIP-360 draft reflects substantial changes since initial 
publication, particularly regarding algorithm selection. While we 
originally considered SQIsign, it has 15,000x slower verification 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 transactions. This has 
obvious and concerning DDoS implications.

While it would take a long time to sign many thousands of SQIsign 
transactions as well, the increased time needed to sign the transactions 
likely won’t 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 
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 too far from Schnorr signatures. That 
said, I think those capabilities should be introduced in a separate BIP 
once they're more mature and worthwhile.

Our current shortlist prioritizes FALCON for its signature aggregation 
potential, with SPHINCS+ and CRYSTALS-Dilithium as secondary candidates. 
However, major technical challenges remain, particularly BIP-32 
compatibility issues affecting xpub generation in watch-only wallets, as 
detailed by conduition in another mailing list discussion [4], and also, 
how we should handle multisig wallets.

Additionally, I think it's worthwhile to restrict BIP-360 to NIST-approved 
algorithms to maintain FIPS compliance. That's because HSMs such as those 
provided 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 merkle tree configuration defined for 
encumbering the output with multiple keys. While that's efficient, it's a 
novel construction. I'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 modifying the semantics of OP_CHECKMULTISIG in a witness 
script to alias to public keys in the attestation. But that could introduce 
additional overhead in a signature scheme that 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 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 indicate PQC signature threshold 
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 without disabling them, as 
Matthew Corallo proposes in the aforementioned mailing list thread [4]. The 
P2TRH approach hashes public keys rather than exposing them directly, 
particularly benefiting:

- MuSig2 Lightning channel implementations

- FROST-based MPC vaults

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

For those interested, take a look at the draft BIP for P2TRH here: 
https://github.com/cryptoquick/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 protect against short exposure quantum 
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 
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 the draft, but if 
it isn't merged by the time I'm finished, 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-- adding too much complexity to the network and to 
wallets and other applications-- and I agree. 

Hopefully 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 
review.

I think it's still important to include multiple signature algorithm 
options for users to select their desired level of security. It's not 100% 
certain that all of these algorithms will remain quantum resistant for all 
time, so redundancy here is… key.

Another concern is that 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 level I implementations could be included, but this would be a 
deviation from the BIP as presently specified, which defaults to level V 
security. The disadvantage of including level I support for each algorithm 
is that it essentially doubles the complexity of libbitcoinpqc.

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

At this point, the major call to action I would like to highlight is simply 
the need for more 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 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/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-release-overview

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/8797807d-e017-44e2-b419-803291779007n%40googlegroups.com.