Delivery-date: Mon, 16 Dec 2024 14:22:51 -0800
Sender: bitcoindev@googlegroups.com
Date: Mon, 16 Dec 2024 14:20:04 -0800 (PST)
From: Tadge Dryja <rx@awsomnet.org>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com>
In-Reply-To: <Z2ALlBGIyZLVbfVG@erisian.com.au>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
 <Z2ALlBGIyZLVbfVG@erisian.com.au>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_10564_758607190.1734387604594"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_10564_758607190.1734387604594
Content-Type: multipart/alternative; 
	boundary="----=_Part_10565_1506854350.1734387604594"

------=_Part_10565_1506854350.1734387604594
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi everyone
 (disclosure: I'm highly skeptical QCs will break secp256k1 in my lifetime,=
=20
but who knows)

IMHO the activation dilemma is the trickiest part of Bitcoin dealing with=
=20
QCs.  On the one hand, you want a very long term plan, many years ahead of=
=20
time, so that everyone has time to migrate and not get their coins stolen=
=20
or destroyed.  But the further out a QC is, the less likely it seems it=20
will ever occur, and thus the less reason there is to write software to=20
deal with a theoretical, far off problem. (And that's not even getting into=
=20
the fact that nobody's in charge of Bitcoin so there's no long term roadmap=
=20
anyway.)

The ability to have a PQ fallback key with zero or very low on-chain cost=
=20
helps a lot with this, whichever activation path ends up happening. =20
Picking something and committing to it in wallets today, before any kind of=
=20
activation, is a bit scary since the PQ pubkey does become an exposed=20
private key.  But I think there is a pretty good way to do it with a=20
consensus level proof of quantum computer.

On Monday, December 16, 2024 at 7:35:47=E2=80=AFAM UTC-5 Anthony Towns wrot=
e:


- Disabling key path taproot spends via soft-fork is extremely=20
confiscatory -- for the consensus cleanup, we worry about even the=20
possibility of destroying funds due to transaction patterns never=20
seen on the network; here, shutting down key path spends would be=20
knowingly destroying an enormous range of utxos.=20


This is true, but faced with a QC you're in trouble either way: either the=
=20
coins are destroyed, or the first (non-nice) entity to get a QC steals=20
them.  We can hope that if the QC ever does arrive there will be enough=20
warning and coordination that there won't be *too* many of these utxos at=
=20
that point.

But there are still a lot of lost coins where nobody knows the private keys=
=20
anymore and in those cases, the lead time doesn't matter. The original=20
owners who lost the keys would probably prefer those coins to be destroyed=
=20
rather than stolen.  But of course there's no way for them to reliably=20
express that preference since they can no longer sign.

An on-chain proof of quantum computer (PoQC I guess :) ) would be a way to=
=20
reduce the damage of activation forks.  One way to build it: Create a NUMS=
=20
point pubkey - something like described in BIP341.  Send some coins to that=
=20
address, then watch if it gets spent.  Providing a preimage of the=20
x-coordinate of a point, as well as a valid signature from that point means=
=20
that either the hash function is broken or (what we're assuming here) the=
=20
one-wayness of the EC base point multiplication has been broken.  Nodes can=
=20
then have code which watches for such a proof and changes consensus rules=
=20
based on it.

This can be useful for the activation, or persistence of a confiscatory=20
restriction of key path spends.  For example:

Say people worry about an immanent QC.  They estimate it will be built in=
=20
5-8 years.  They write software which contains a temporary fork, which=20
activates in 3 years and *de*activates in 8 years.  This fork disables=20
almost all key path spends (as well as ECDSA signatures).  The only key=20
path spends allowed are from the NUMS utxos, and if any NUMS utxo is spent,=
=20
then the EC prohibition locks in to become permanent instead of reverting 3=
=20
years after initial enforcement.

In this case the soft fork is only (permanently) confiscatory if the QC=20
provably exists and would have (presumably, sooner or later) confiscated=20
all those coins anyway.  It also could also allow people to enable PQ=20
signatures and disable EC signatures a bit sooner than they otherwise would=
=20
have, since the cost of being wrong about a QC is lessened -- losing EC=20
operations would be painful, but even more so if it turns out the nearly=20
finished QC never quite gets there.

An opt-in, non-confiscatory fork could also use this mechanism.  A new P2TR=
=20
output type (PQ2TR?) could be used which is explicitly not key-spendable=20
post-PoQC, but the older P2TR, P2WPKH, etc output types are still EC=20
spendable (better move em quick).

It can also work the other way: The new PQ output type can work just like=
=20
P2TR, except that one opcode (the OP_PQCHECKSIG) becomes an OP_FAIL until=
=20
the PoQC.  Given PoQC, it's OP_SUCCESS.  That way we don't have to have a=
=20
consensus level definition the actual PQ signature algorithm yet; we've=20
just put a placeholder PQ signature opcode in, and an activation method.  A=
=20
later soft fork can then define the signature algo.  You'd want to define=
=20
it pretty soon after, since wallets committing to PQ pubkeys for schemes=20
that end up not getting implemented doesn't help.  But it does allow=20
wallets to do something soon for people who are worried and want to be=20
"quantum safe".

-Tadge


--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
374d6201-fb43-48df-abbc-f01ef1944a7dn%40googlegroups.com.

------=_Part_10565_1506854350.1734387604594
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div>Hi everyone<br /></div><div></div><div>=C2=A0(disclosure: I'm highly s=
keptical QCs will break secp256k1 in my lifetime, but who knows)<br /></div=
><div><br /></div><div><div>IMHO the activation dilemma is the trickiest pa=
rt of Bitcoin=20
dealing with QCs. =C2=A0On the one hand, you want a very long term plan, ma=
ny
 years ahead of time, so that everyone has time to migrate and not get=20
their coins stolen or destroyed. =C2=A0But the further out a QC is, the les=
s=20
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=20
there's no long term roadmap anyway.)<br /><br />The ability to have a PQ=
=20
fallback key with zero or very low on-chain cost helps a lot with this,=20
whichever activation path ends up happening.=C2=A0 Picking something and co=
mmitting to it in wallets today, before any kind of activation, is a bit sc=
ary since the PQ pubkey does become an exposed private key.=C2=A0 But I thi=
nk there is a pretty good way to do it with a consensus level proof of quan=
tum computer.</div><div><br /></div></div><div><div dir=3D"auto">On Monday,=
 December 16, 2024 at 7:35:47=E2=80=AFAM UTC-5 Anthony Towns wrote:<br /></=
div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; border-left: 1px solid =
rgb(204, 204, 204); padding-left: 1ex;"><br />
<br /> - Disabling key path taproot spends via soft-fork is extremely
<br />   confiscatory -- for the consensus cleanup, we worry about even the
<br />   possibility of destroying funds due to transaction patterns never
<br />   seen on the network; here, shutting down key path spends would be
<br />   knowingly destroying an enormous range of utxos.
<br /></blockquote><div><br /></div><div>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. =C2=A0We 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.<br /></div><div><br /></d=
iv><div>But there are still a lot of lost coins where nobody knows the priv=
ate keys anymore and in those cases, the lead time doesn't matter. The orig=
inal owners who lost the keys would probably prefer those coins to be destr=
oyed rather than stolen. =C2=A0But of course there's no way for them to rel=
iably express that preference since they can no longer sign.<br /><br />An =
on-chain proof of quantum computer (PoQC I guess :) ) would be a way to red=
uce the damage of activation forks.=C2=A0 One way to build it: Create a NUM=
S point pubkey - something like described in BIP341.=C2=A0 Send some coins =
to that address, then watch if it gets spent.=C2=A0 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.=C2=A0=
 Nodes can then have code which watches for such a proof and changes consen=
sus rules based on it.<br /><br />This can be useful for the activation, or=
 persistence of a confiscatory restriction of key path spends.=C2=A0 For ex=
ample:<br /><br />Say people worry about an immanent QC. =C2=A0They estimat=
e it will be built in 5-8 years. =C2=A0They write software which contains a=
 temporary fork, which activates in 3 years and *de*activates in 8 years. =
=C2=A0This fork disables almost all key path spends (as well as ECDSA signa=
tures). =C2=A0The 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 perm=
anent instead of reverting 3 years after initial enforcement.<br /><br />In=
 this case the soft fork is only (permanently) confiscatory if the QC prova=
bly exists and would have (presumably, sooner or later) confiscated all tho=
se coins anyway. =C2=A0It also could also allow people to enable PQ signatu=
res 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 operation=
s would be painful, but even more so if it turns out the nearly finished QC=
 never quite gets there.<br /><br />An opt-in, non-confiscatory fork could =
also use this mechanism. =C2=A0A new P2TR output type (PQ2TR?) could be use=
d which is explicitly not key-spendable post-PoQC, but the older P2TR, P2WP=
KH, etc output types are still EC spendable (better move em quick).<br /></=
div><div><br /></div><div>It can also work the other way: The new PQ output=
 type can work just like P2TR, except that one opcode (the OP_PQCHECKSIG) b=
ecomes an OP_FAIL until the PoQC.=C2=A0 Given PoQC, it's OP_SUCCESS.=C2=A0 =
That way we don't have to have a consensus level definition the actual PQ s=
ignature algorithm yet; we've just put a placeholder PQ signature opcode in=
, and an activation method.=C2=A0 A later soft fork can then define the sig=
nature algo.=C2=A0 You'd want to define it pretty soon after, since wallets=
 committing to PQ pubkeys for schemes that end up not getting implemented d=
oesn't help.=C2=A0 But it does allow wallets to do something soon for peopl=
e who are worried and want to be "quantum safe".</div><div><br /></div><div=
>-Tadge<br /></div><div><br /></div><div><br /></div><div><br /></div></div=
>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/374d6201-fb43-48df-abbc-f01ef1944a7dn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/374d6201-fb43-48df-abbc-f01ef1944a7dn%40googlegroups.com</a>.<br />

------=_Part_10565_1506854350.1734387604594--

------=_Part_10564_758607190.1734387604594--