From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
Date: Mon, 16 Dec 2024 21:31:27 -0800 (PST) [thread overview]
Message-ID: <0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n@googlegroups.com> (raw)
In-Reply-To: <374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com>
[-- Attachment #1.1: Type: text/plain, Size: 9806 bytes --]
Hey all, and thank you for this great idea Matt. It rhymes a little with my
DASK idea
<https://conduition.io/cryptography/quantum-hbs/#Upgrading-Bitcoin> but I
actually like yours a lot better, as it provides a cleaner upgrade path for
soft-fork compatibility than DASK.
However, I suggest we use one of the more succinct Winternitz one-time
signature algorithms instead of committing to SPHINCS right away. This
gives us the option of using the WOTS key as a certification layer for some
pubkey from a future signature algorithm, which may or may not even exist
yet.
Not only does this give researchers more time to find better algorithms, it
also makes devs' lives easier, and makes the transition to a PQ world more
incremental than a head-first dive committing to SPHINCS. WOTS is very
simple: it'd be easy to standardize and easy for wallets to implement and
derive. Its signatures can be as small as 1 kilobyte. Even if we do end up
choosing SPHINCS as the 2nd-layer whose pubkey we certify, the time/space
overhead added by one WOTS signature is negligible in comparison. Once the
WOTS pubkey is standardized, we can take our time choosing and
standardizing the probably-much-more-complicated 2nd layer signing
algorithm.
This certification layer idea is straight from SPHINCS' own whitepaper.
This is how SPHINCS authors created its many-time property without blowing
up the runtime.
----------
Tadge, your PoQC idea is neat but it relies on at least one "good guy" QC
willing to produce the proof. A self-interested QC would never willingly
crack a pubkey which it knows would activate a soft-fork against its own
interest. Any publicly-advertised PoQC honeypot addresses able to gather
large donations would be obvious, and a rational QC would ignore them. I
suppose users could sprinkle some hidden honeypot addresses around the
network and hope the QC bites one of them, but I don't think that's
practical - The QC would probably prioritize addresses with large balances
like Satoshi's wallets. I'm not sure if I have any better ideas though,
besides the also-risky option of relying on the community to act in unison,
triggering activation manually if/when a QC appears to be coming soon to a
blockchain near us. So a PoQC might be a good additional trigger, but we
also need to be able to manually activate the post-quantum upgrade in case
the PoQC is unavailable.
----------
Another fun aspect of QC's we haven't discussed yet is BIP32. Whatever
pubkey we hide in the OP_SUCCESS tap leaf, it needs to be derived via
quantum-secure means. So there can be no unhardened BIP32 anywhere in the
derivation chain of the PQ-secret-key, or else xpubs can be sold to a QC
for profit, even if the PQ soft fork upgrade is activated on time.
It seems like whatever upgrade path we go with, it will mean the end of
BIP32 xpubs as we know them. A 3rd party won't be able to derive my
post-quantum P2TR address from a regular xpub alone without also knowing
the OP_SUCCESS script's tap leaf hash, which by necessity must be
completely independent of the xpub. Sounds like we may need a new standard
for that too. Perhaps some kind of 'wrapper' which embeds a regular BIP32
xpub, plus the tap leaf hash of the OP_SUCCESS script? That'd be enough for
an untrusted 3rd party to derive a standard set of P2TR addresses with the
attached PQ fallback leaf script hash.
A second wacky idea which modifies (bastardizes) BIP32 instead of replacing
it: Replace the xpub's chain code with the OP_SUCCESS script's tap leaf
hash before distributing. You could derive the PQ keypair from the parent
xpriv, to maintain the integrity of BIP32's chained derivation, so in a it
would be like inserting a little modification into BIP32's hardened
derivation logic. Software which doesn't have PQ-fallback support will
derive the standard P2TR addresses we all use today. Software which *does* have
PQ-fallback support will derive the same child taproot internal keys, but
tweaked with a PQ-fallback script leaf. I imagine this might make
compatibility very complicated though, so i'm not sure if this is a smart
choice - throwing this out there in case it inspires better ideas but i
wouldn't advocate for it myself.
-c
On Monday, December 16, 2024 at 5:22:44 PM UTC-5 Tadge Dryja wrote:
> Hi everyone
> (disclosure: I'm highly skeptical QCs will break secp256k1 in my
> lifetime, but who knows)
>
> IMHO the activation dilemma is the trickiest part of Bitcoin dealing with
> QCs. On the one hand, you want a very long term plan, many years ahead of
> time, so that everyone has time to migrate and not get their coins stolen
> or destroyed. But the further out a QC is, the less likely it seems it
> will ever occur, and thus the less reason there is to write software to
> deal with a theoretical, far off problem. (And that's not even getting into
> the fact that nobody's in charge of Bitcoin so there's no long term roadmap
> anyway.)
>
> The ability to have a PQ fallback key with zero or very low on-chain cost
> helps a lot with this, whichever activation path ends up happening.
> Picking something and committing to it in wallets today, before any kind of
> activation, is a bit scary since the PQ pubkey does become an exposed
> private key. But I think there is a pretty good way to do it with a
> consensus level proof of quantum computer.
>
> On Monday, December 16, 2024 at 7:35:47 AM UTC-5 Anthony Towns wrote:
>
>
>
> - Disabling key path taproot spends via soft-fork is extremely
> confiscatory -- for the consensus cleanup, we worry about even the
> possibility of destroying funds due to transaction patterns never
> seen on the network; here, shutting down key path spends would be
> knowingly destroying an enormous range of utxos.
>
>
> This is true, but faced with a QC you're in trouble either way: either the
> coins are destroyed, or the first (non-nice) entity to get a QC steals
> them. We can hope that if the QC ever does arrive there will be enough
> warning and coordination that there won't be *too* many of these utxos at
> that point.
>
> But there are still a lot of lost coins where nobody knows the private
> keys anymore and in those cases, the lead time doesn't matter. The original
> owners who lost the keys would probably prefer those coins to be destroyed
> rather than stolen. But of course there's no way for them to reliably
> express that preference since they can no longer sign.
>
> An on-chain proof of quantum computer (PoQC I guess :) ) would be a way to
> reduce the damage of activation forks. One way to build it: Create a NUMS
> point pubkey - something like described in BIP341. Send some coins to that
> address, then watch if it gets spent. Providing a preimage of the
> x-coordinate of a point, as well as a valid signature from that point means
> that either the hash function is broken or (what we're assuming here) the
> one-wayness of the EC base point multiplication has been broken. Nodes can
> then have code which watches for such a proof and changes consensus rules
> based on it.
>
> This can be useful for the activation, or persistence of a confiscatory
> restriction of key path spends. For example:
>
> Say people worry about an immanent QC. They estimate it will be built in
> 5-8 years. They write software which contains a temporary fork, which
> activates in 3 years and *de*activates in 8 years. This fork disables
> almost all key path spends (as well as ECDSA signatures). The only key
> path spends allowed are from the NUMS utxos, and if any NUMS utxo is spent,
> then the EC prohibition locks in to become permanent instead of reverting 3
> years after initial enforcement.
>
> In this case the soft fork is only (permanently) confiscatory if the QC
> provably exists and would have (presumably, sooner or later) confiscated
> all those coins anyway. It also could also allow people to enable PQ
> signatures and disable EC signatures a bit sooner than they otherwise would
> have, since the cost of being wrong about a QC is lessened -- losing EC
> operations would be painful, but even more so if it turns out the nearly
> finished QC never quite gets there.
>
> An opt-in, non-confiscatory fork could also use this mechanism. A new
> P2TR output type (PQ2TR?) could be used which is explicitly not
> key-spendable post-PoQC, but the older P2TR, P2WPKH, etc output types are
> still EC spendable (better move em quick).
>
> It can also work the other way: The new PQ output type can work just like
> P2TR, except that one opcode (the OP_PQCHECKSIG) becomes an OP_FAIL until
> the PoQC. Given PoQC, it's OP_SUCCESS. That way we don't have to have a
> consensus level definition the actual PQ signature algorithm yet; we've
> just put a placeholder PQ signature opcode in, and an activation method. A
> later soft fork can then define the signature algo. You'd want to define
> it pretty soon after, since wallets committing to PQ pubkeys for schemes
> that end up not getting implemented doesn't help. But it does allow
> wallets to do something soon for people who are worried and want to be
> "quantum safe".
>
> -Tadge
>
>
>
>
--
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/0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 10668 bytes --]
next prev parent reply other threads:[~2024-12-17 5:42 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-12-15 21:42 Matt Corallo
2024-12-15 23:54 ` Luke Dashjr
2024-12-16 1:30 ` Weikeng Chen
2024-12-16 1:40 ` Matt Corallo
2024-12-16 11:14 ` Anthony Towns
2024-12-16 15:57 ` Matt Corallo
2024-12-16 22:20 ` Tadge Dryja
2024-12-17 5:31 ` 'conduition' via Bitcoin Development Mailing List [this message]
2024-12-18 3:29 ` Antoine Riard
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n@googlegroups.com \
--to=bitcoindev@googlegroups.com \
--cc=conduition@proton$(echo .)me \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox