From: Tadge Dryja <rx@awsomnet•org>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
Date: Mon, 16 Dec 2024 14:20:04 -0800 (PST) [thread overview]
Message-ID: <374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com> (raw)
In-Reply-To: <Z2ALlBGIyZLVbfVG@erisian.com.au>
[-- Attachment #1.1: Type: text/plain, Size: 5219 bytes --]
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/374d6201-fb43-48df-abbc-f01ef1944a7dn%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 5914 bytes --]
next prev parent reply other threads:[~2024-12-16 22:22 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 [this message]
2024-12-17 5:31 ` 'conduition' via Bitcoin Development Mailing List
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=374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com \
--to=rx@awsomnet$(echo .)org \
--cc=bitcoindev@googlegroups.com \
/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