Subject: Re: [bitcoindev] P2QRH / BIP-360 Update

From: Hunter Beast <[email-masked]>
Date: Sun, 23 Feb 2025 12:33:03 -0800 (PST)

Hi Matt,

The only problem with that approach is that SLH-DSA signatures are quite 
large. NIST has also approved ML-DSA and FN-DSA, which, while both are 
based on lattice cryptography, they're not only standardized, but becoming 
widely supported. One consideration is hardware acceleration, and I believe 
those three algorithms will have the best chance of having hardware 
implementations as PQC extensions are added to CPUs and SoCs.

As for gating P2TR, the problem with that approach is that keypath spends 
would need to be disabled and that has a confiscatory effect that I'm 
seeking to avoid in this BIP.

An additional opcode should not be necessary if multisig capability is 
built into the attestation.

I agree with your statement on full BIP-32 compatibility. BIP-360 is just a 
starting point, and maybe you're right, it's best thought of as a "break 
glass" implementation. It's not ideal, it's full of compromises, not 
everyone is 100% happy with it, and that's probably okay, because bitcoin 
isn't perfect-- but it doesn't have to be in order to work.

Thank you for your thoughts.

Hunter

On Friday, February 21, 2025 at 3:18:21 AM UTC-7 Matt Corallo wrote:

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

BIP 32 compatibility isn't a really huge deal if we're talking about an 
"emergency break glass" 
kinda setup - most wallets are set up with a root key and can just embed 
the same PQ pubkey in all 
of their outputs. The privacy cost is only realized in a break glass case, 
and long before then 
hopefully whatever we do today is replaced with something better, with the 
knowledge that we'll gain 
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, 
> 
> 
> 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 <
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 signmany 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 <
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 <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] <mailto:[email-masked]>. 
> To view this discussion visit 
https://groups.google.com/d/msgid/bitcoindev/8797807d-e017-44e2- 
> b419-803291779007n%40googlegroups.com <
https://groups.google.com/d/msgid/bitcoindev/8797807d- 
> e017-44e2-b419-803291779007n%
40googlegroups.com?utm_medium=email&utm_source=footer>. 

-- 
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/866ee206-4a4e-4cd6-9de3-fa2fa35e2230n%40googlegroups.com.