Delivery-date: Mon, 16 Dec 2024 21:42:41 -0800
Date: Mon, 16 Dec 2024 21:31:27 -0800 (PST)
From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n@googlegroups.com>
In-Reply-To: <374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
 <Z2ALlBGIyZLVbfVG@erisian.com.au>
 <374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_25508_1950947509.1734413487908"
Reply-To: conduition <conduition@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_25508_1950947509.1734413487908
Content-Type: multipart/alternative; 
	boundary="----=_Part_25509_1000266509.1734413487908"

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

Hey all, and thank you for this great idea Matt. It rhymes a little with my=
=20
DASK idea=20
<https://conduition.io/cryptography/quantum-hbs/#Upgrading-Bitcoin> but I=
=20
actually like yours a lot better, as it provides a cleaner upgrade path for=
=20
soft-fork compatibility than DASK.

However, I suggest we use one of the more succinct Winternitz one-time=20
signature algorithms instead of committing to SPHINCS right away. This=20
gives us the option of using the WOTS key as a certification layer for some=
=20
pubkey from a future signature algorithm, which may or may not even exist=
=20
yet.

Not only does this give researchers more time to find better algorithms, it=
=20
also makes devs' lives easier, and makes the transition to a PQ world more=
=20
incremental than a head-first dive committing to SPHINCS. WOTS is very=20
simple: it'd be easy to standardize and easy for wallets to implement and=
=20
derive. Its signatures can be as small as 1 kilobyte. Even if we do end up=
=20
choosing SPHINCS as the 2nd-layer whose pubkey we certify, the time/space=
=20
overhead added by one WOTS signature is negligible in comparison. Once the=
=20
WOTS pubkey is standardized, we can take our time choosing and=20
standardizing the probably-much-more-complicated 2nd layer signing=20
algorithm.

This certification layer idea is straight from SPHINCS' own whitepaper.=20
This is how SPHINCS authors created its many-time property without blowing=
=20
up the runtime.

----------

Tadge, your PoQC idea is neat but it relies on at least one "good guy" QC=
=20
willing to produce the proof. A self-interested QC would never willingly=20
crack a pubkey which it knows would activate a soft-fork against its own=20
interest. Any publicly-advertised PoQC honeypot addresses able to gather=20
large donations would be obvious, and a rational QC would ignore them. I=20
suppose users could sprinkle some hidden honeypot addresses around the=20
network and hope the QC bites one of them, but I don't think that's=20
practical - The QC would probably prioritize addresses with large balances=
=20
like Satoshi's wallets. I'm not sure if I have any better ideas though,=20
besides the also-risky option of relying on the community to act in unison,=
=20
triggering activation manually if/when a QC appears to be coming soon to a=
=20
blockchain near us. So a PoQC might be a good additional trigger, but we=20
also need to be able to manually activate the post-quantum upgrade in case=
=20
the PoQC is unavailable.

----------

Another fun aspect of QC's we haven't discussed yet is BIP32. Whatever=20
pubkey we hide in the OP_SUCCESS tap leaf, it needs to be derived via=20
quantum-secure means. So there can be no unhardened BIP32 anywhere in the=
=20
derivation chain of the PQ-secret-key, or else xpubs can be sold to a QC=20
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=20
BIP32 xpubs as we know them. A 3rd party won't be able to derive my=20
post-quantum P2TR address from a regular xpub alone without also knowing=20
the OP_SUCCESS script's tap leaf hash, which by necessity must be=20
completely independent of the xpub. Sounds like we may need a new standard=
=20
for that too. Perhaps some kind of 'wrapper' which embeds a regular BIP32=
=20
xpub, plus the tap leaf hash of the OP_SUCCESS script? That'd be enough for=
=20
an untrusted 3rd party to derive a standard set of P2TR addresses with the=
=20
attached PQ fallback leaf script hash.

A second wacky idea which modifies (bastardizes) BIP32 instead of replacing=
=20
it: Replace the xpub's chain code with the OP_SUCCESS script's tap leaf=20
hash before distributing. You could derive the PQ keypair from the parent=
=20
xpriv, to maintain the integrity of BIP32's chained derivation, so in a it=
=20
would be like inserting a little modification into BIP32's hardened=20
derivation logic. Software which doesn't have PQ-fallback support will=20
derive the standard P2TR addresses we all use today. Software which *does* =
have=20
PQ-fallback support will derive the same child taproot internal keys, but=
=20
tweaked with a PQ-fallback script leaf. I imagine this might make=20
compatibility very complicated though, so i'm not sure if this is a smart=
=20
choice - throwing this out there in case it inspires better ideas but i=20
wouldn't advocate for it myself.

-c

On Monday, December 16, 2024 at 5:22:44=E2=80=AFPM UTC-5 Tadge Dryja wrote:

> Hi everyone
>  (disclosure: I'm highly skeptical QCs will break secp256k1 in my=20
> lifetime, 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 o=
f=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 in=
to=20
> the fact that nobody's in charge of Bitcoin so there's no long term roadm=
ap=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 wr=
ote:
>
>
>
> - 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 th=
e=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=20
> keys anymore and in those cases, the lead time doesn't matter. The origin=
al=20
> owners who lost the keys would probably prefer those coins to be destroye=
d=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 t=
o=20
> reduce the damage of activation forks.  One way to build it: Create a NUM=
S=20
> point pubkey - something like described in BIP341.  Send some coins to th=
at=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 mea=
ns=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 c=
an=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 spen=
t,=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 wou=
ld=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=20
> P2TR output type (PQ2TR?) could be used which is explicitly not=20
> key-spendable post-PoQC, but the older P2TR, P2WPKH, etc output types are=
=20
> still EC 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/=
0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n%40googlegroups.com.

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

Hey all, and thank you for this great idea Matt. It rhymes a little with <a=
 href=3D"https://conduition.io/cryptography/quantum-hbs/#Upgrading-Bitcoin"=
>my DASK idea</a>=C2=A0but I actually like yours a lot better, as it provid=
es a cleaner upgrade path for soft-fork compatibility than DASK.<br /><br /=
>However, I suggest we use one of the more succinct Winternitz one-time sig=
nature algorithms instead of committing to SPHINCS right away. This gives u=
s 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.<br=
 /><br />Not only does this give researchers more time to find better algor=
ithms, it also makes devs' lives easier, and makes the transition to a PQ w=
orld 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 en=
d up choosing SPHINCS as the 2nd-layer whose pubkey we certify, the time/sp=
ace overhead added by one WOTS signature is negligible in comparison. Once =
the WOTS pubkey is standardized, we can take our time choosing and standard=
izing the probably-much-more-complicated 2nd layer signing algorithm.<div><=
div><br />This certification layer idea is straight from SPHINCS' own white=
paper. This is how SPHINCS authors created its many-time property without b=
lowing up the runtime.<br /><br />----------<br /><br />Tadge, your PoQC id=
ea is neat but it relies on at least one "good guy" QC willing to produce t=
he proof. A self-interested QC would never willingly crack a pubkey which i=
t knows would activate a soft-fork against its own interest. Any publicly-a=
dvertised PoQC honeypot addresses able to gather large donations would be o=
bvious, and a rational QC would ignore them. I suppose users could sprinkle=
 some hidden honeypot addresses around the network and hope the QC bites on=
e of them, but I don't think that's practical - The QC would probably prior=
itize 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 o=
n 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 t=
he post-quantum upgrade in case the PoQC is unavailable.</div><div><br /></=
div><div>----------</div><div><br /></div><div>Another fun aspect of QC's w=
e 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 upg=
rade is activated on time.</div><div><br /></div><div>It seems like whateve=
r upgrade path we go with, it will mean the end of BIP32 xpubs as we know t=
hem. 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 'wrappe=
r' which embeds a regular BIP32 xpub, plus the tap leaf hash of the OP_SUCC=
ESS script? That'd be enough for an untrusted 3rd party to derive a standar=
d set of P2TR addresses with the attached PQ fallback leaf script hash.</di=
v><div><br /></div><div>A second wacky idea which modifies (bastardizes) BI=
P32 instead of replacing it: Replace the xpub's chain code with the OP_SUCC=
ESS script's tap leaf hash before distributing. You could derive the PQ key=
pair from the parent xpriv, to maintain the integrity of BIP32's chained de=
rivation, so in a it would be like inserting a little modification into BIP=
32's hardened derivation logic. Software which doesn't have PQ-fallback sup=
port will derive the standard P2TR addresses we all use today. Software whi=
ch=C2=A0<i>does</i>=C2=A0have PQ-fallback support will derive the same chil=
d taproot internal keys, but tweaked with a PQ-fallback script leaf. I imag=
ine 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 bet=
ter ideas but i wouldn't advocate for it myself.</div><div><br /></div><div=
><div><div>-c<br /><br /></div></div></div></div><div class=3D"gmail_quote"=
><div dir=3D"auto" class=3D"gmail_attr">On Monday, December 16, 2024 at 5:2=
2:44=E2=80=AFPM UTC-5 Tadge Dryja wrote:<br/></div><blockquote class=3D"gma=
il_quote" style=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204=
, 204); padding-left: 1ex;"><div>Hi everyone<br></div><div></div><div>=C2=
=A0(disclosure: I&#39;m highly skeptical QCs will break secp256k1 in my lif=
etime, but who knows)<br></div><div><br></div><div><div>IMHO the activation=
 dilemma is the trickiest part 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&#39;=
s
 not even getting into the fact that nobody&#39;s in charge of Bitcoin so=
=20
there&#39;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><div><div dir=3D"auto">O=
n 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 so=
lid 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><div><div>This is true, but faced wit=
h a QC you&#39;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 tha=
t if the QC ever does arrive there will be enough warning and coordination =
that there won&#39;t be *too* many of these utxos at that point.<br></div><=
div><br></div><div>But there are still a lot of lost coins where nobody kno=
ws the private keys anymore and in those cases, the lead time doesn&#39;t m=
atter. The original owners who lost the keys would probably prefer those co=
ins to be destroyed rather than stolen. =C2=A0But of course there&#39;s no =
way for them to reliably express that preference since they can no longer s=
ign.<br><br>An on-chain proof of quantum computer (PoQC I guess :) ) would =
be a way to reduce the damage of activation forks.=C2=A0 One way to build i=
t: Create a NUMS point pubkey - something like described in BIP341.=C2=A0 S=
end some coins to that address, then watch if it gets spent.=C2=A0 Providin=
g a preimage of the x-coordinate of a point, as well as a valid signature f=
rom that point means that either the hash function is broken or (what we=
9;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 consensus rules based on it.<br><br>This can be useful for the=
 activation, or persistence of a confiscatory restriction of key path spend=
s.=C2=A0 For example:<br><br>Say people worry about an immanent QC. =C2=A0T=
hey estimate 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 E=
CDSA signatures). =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 b=
ecome permanent instead of reverting 3 years after initial enforcement.<br>=
<br>In this case the soft fork is only (permanently) confiscatory if the QC=
 provably exists and would have (presumably, sooner or later) confiscated a=
ll those coins anyway. =C2=A0It also could also allow people to enable PQ s=
ignatures 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 ope=
rations would be painful, but even more so if it turns out the nearly finis=
hed QC never quite gets there.<br><br>An opt-in, non-confiscatory fork coul=
d also use this mechanism. =C2=A0A new P2TR output type (PQ2TR?) could be u=
sed which is explicitly not key-spendable post-PoQC, but the older P2TR, P2=
WPKH, 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 t=
ype can work just like P2TR, except that one opcode (the OP_PQCHECKSIG) bec=
omes an OP_FAIL until the PoQC.=C2=A0 Given PoQC, it&#39;s OP_SUCCESS.=C2=
=A0 That way we don&#39;t have to have a consensus level definition the act=
ual PQ signature algorithm yet; we&#39;ve just put a placeholder PQ signatu=
re opcode in, and an activation method.=C2=A0 A later soft fork can then de=
fine the signature algo.=C2=A0 You&#39;d want to define it pretty soon afte=
r, since wallets committing to PQ pubkeys for schemes that end up not getti=
ng implemented doesn&#39;t help.=C2=A0 But it does allow wallets to do some=
thing soon for people who are worried and want to be &quot;quantum safe&quo=
t;.</div><div><br></div><div>-Tadge<br></div><div><br></div><div><br></div>=
<div><br></div></div></blockquote></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/0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n%40googlegroups.com</a>.<br />

------=_Part_25509_1000266509.1734413487908--

------=_Part_25508_1950947509.1734413487908--