Re: [bitcoindev] P2QRH / BIP-360 Update

[Dustin Ray <dustinvonsandwich@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 17324 bytes --]

Matt, you make a potent and salient point. I think that when we survey the
current state of existing pqc solutions and try to apply them to bitcoin,
we keep coming up with either a massive chain, massive key sizes, extremely
degraded performance, confiscation, or some combination of those.

I think laying the groundwork for this inevitable task now is important,
but if I understand your points correctly, I would agree that existing
solutions do not seem equipped to carry bitcoin into the post quantum
landscape.

On Thu, Feb 27, 2025 at 6:41 PM Matt Corallo <lf-lists@mattcorallo.com>
wrote:

> I think you're approaching this from the wrong stance.
>
> If our goal is to "make bitcoin Quantum-secure", its gonna take a decade
> for the state of PQ
> research to build something that's ready for us to "just switch to". I
> don't buy that there's a
> world where we get serious about adding something lattice-based to Bitcoin
> for a longggg time (I'm
> not sure I've ever heard a serious cryptographer suggest that
> lattice-based systems are a good idea,
> rather than "a good thing to layer on top of a traditional non-PQC
> scheme").
>
> In the short-term, the only (remotely-practical) thing we can do is add
> something that we have high
> confidence will still be secure in two decades (which basically is only
> hash-based schemes) and get
> wallets to include it in their taproot outputs. That gives wallets created
> today the possibility of
> being robust in a QC world, but, indeed, it would require tough decisions
> in the future.
>
> If your view is that Bitcoin would simply be fine if we didn't confiscate
> any coins in response to a
> practical QC stealing 5% of total supply, I'm not really convinced, but we
> can also make it a
> version-2 segwit output ("taproot but a future softfork can freely freeze
> the keypath spends") if
> you really feel strongly.
>
> TBH the whole "would we confiscate if the time comes" question I think
> simply cannot be answered
> today because it depends very, very much on specific details (eg lets say
> we did the above proposal
> and its been around for 30 years and ~all wallets support it, that's a
> very very different world
> from, for example, deploying some PQC scheme under threat where a QC could
> realistically steal coins
> in five years). The only thing we can really do today is create the option
> in the future, we cannot
> decide for the future what to do.
>
> Matt
>
> On 2/23/25 3:33 PM, Hunter Beast wrote:
> > 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> <
> https://github.com/cryptoquick/ <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/ <https://github.com/cryptoquick/>
> >      > bips/blob/p2trh/bip-p2trh.mediawiki <
> 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/ <https://github.com/bitcoin/>
> >      > bips/pull/1670 <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 <
> https://pqshield.github.io/nist-sigs-zoo>
> >      >
> >      > [2] https://eprint.iacr.org/2023/1820.pdf <
> https://eprint.iacr.org/2023/1820.pdf>
> >      >
> >      > [3] https://eprint.iacr.org/2024/1291.pdf <
> https://eprint.iacr.org/2024/1291.pdf>
> >      >
> >      > [4]
> https://groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/7uu4dZNgAwAJ
> <https://
> >     groups.google.com/g/bitcoindev/c/8O857bRSVV8/m/7uu4dZNgAwAJ>
> >      >
> >      > [5]
> https://docs.securosys.com/tsb/Tutorials/Post-Quantum-Cryptography/pqc-release-overview
> >     <
> 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
> >      > bitcoindev+...@googlegroups.com <mailto:
> bitcoindev+...@googlegroups.com>.
> >      > To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/8797807d-
> >     e017-44e2- <
> https://groups.google.com/d/msgid/bitcoindev/8797807d-e017-44e2->
> >      > b419-803291779007n%40googlegroups.com <http://40googlegroups.com>
> <https://groups.google.com/
> >     d/msgid/bitcoindev/8797807d- <
> https://groups.google.com/d/msgid/bitcoindev/8797807d->
> >      > e017-44e2-b419-803291779007n%
> 40googlegroups.com?utm_medium=email&utm_source=footer
> >     <http://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
> > bitcoindev+unsubscribe@googlegroups.com <mailto:
> bitcoindev+unsubscribe@googlegroups.com>.
> > To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/866ee206-4a4e-4cd6-9de3-
> > fa2fa35e2230n%40googlegroups.com <https://groups.google.com/d/msgid/
> > bitcoindev/866ee206-4a4e-4cd6-9de3-fa2fa35e2230n%
> 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 bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/2e0fc337-3603-4a22-8056-59cf7e21aa43%40mattcorallo.com
> .
>

-- 
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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAC3UE4K1mLaj2AHUcK5S3QB0wtJ40qA-y%2BuEROb3BqxC2_G%2BXA%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 24086 bytes --]