path: root/4d/5314c4692131d216b6d092573dbd74779127db

Delivery-date: Mon, 16 Dec 2024 14:22:51 -0800
Received: from mail-yb1-f183.google.com ([209.85.219.183])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDAPJ4GFTEFRBMOQQK5QMGQEFOKOAXI@googlegroups.com>)
	id 1tNJUI-0005vj-8u
	for bitcoindev@gnusha.org; Mon, 16 Dec 2024 14:22:51 -0800
Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e35e0e88973sf5970632276.0
        for <bitcoindev@gnusha.org>; Mon, 16 Dec 2024 14:22:50 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1734387764; x=1734992564; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=Fnx8ktG6ZtQOkyWcHA+yx9gj508VKVllPNGY/iJ31rE=;
        b=Y7sfrY8RBjXo9w6aLzPl98lFTmLhewi3F0gOl9iRSD2Z+LnOpSi93B3+9w1gM3SaJT
         vW8c94vqGojIJru4n7XkZRe2lht+z6fIvDDB41W05Y1f+TAJWsRTIQGOFOX3Um+ozVek
         v9WxVvAY3Mvx9eHZThDIvv/Wz9PMby7RTQZnqZBTFkhuyErfCbaXpkcZSoNuaOygHQgM
         YE81Jxt5gQkUxbaLRpjcAOtVbIsBI/Ctd5WqVoMs956gJIhw7aylzMn+m8UD8ykVq80l
         OpRomMTw+ePL0JFw8XH500/o1gSBGjOQ6Tn8jSD+l56d3lz8WEYWK+a3cwxtb59v5ntN
         WpdA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups-com.20230601.gappssmtp.com; s=20230601; t=1734387764; x=1734992564; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:from:to:cc
         :subject:date:message-id:reply-to;
        bh=Fnx8ktG6ZtQOkyWcHA+yx9gj508VKVllPNGY/iJ31rE=;
        b=FQ474KpU6HaI0L/2GIIyr4YW+nekgf62dZfbZw5NXqpd6P5LOqkzrivASd9TI4C9tL
         rYhBvp5dP4w/tEtqpQMYRS5vy9crUYHMXW0Sf44DEYdVkTsLpjI9PuV1yAZYV54j+qQt
         SuZhDAEHE6CFxMp1RU1lUsdVNsy0jc3YqYWCH4wmbQQkiIAFtJtxS686whvJOLICWXJF
         yH1MuxQUKk6Do7FrV5oXJBELXokL6a4cfnrIGZYtOcXeMSOfSe1BlRzMSIUaS9Zq2Xts
         GFUakYo1p6FhGTFVYNkwIMnNHt0+tkw57zMyYN26sj8mz/ZAAS10uyGzPU5yc/mYHFXb
         7uyA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1734387764; x=1734992564;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=Fnx8ktG6ZtQOkyWcHA+yx9gj508VKVllPNGY/iJ31rE=;
        b=nRtPNPs6AfTGJR+0MFZrl1lXg7DkVAlzxVb4GXVvTM4rw3OPLbc7GoTpspApi1nrIR
         0wZVcQKsfPOIQ56bxK8KTxYyV9GDLiUEy3wC4hIQ1IxALgX6zdE9fO1o+3ZAgK7m25yE
         BA11ATz249sC1Cz1XI3ivBVcg7/oMBARPyt1BVVF7xx8Pf0t/xhkUre+UChWFvLICxx/
         1GRvG3dKF8pd9nn05z64Qfk8Rj8xAkj2FKL+0f2kyLH9YOe3JXKc0gojaYDKLE5MA+Te
         77q5BET+xyZaXyOZoGOFbkKlgc/1R+JPTayuwpjt1riBQF47hgxnhRe3xQlFrbWpU2BN
         xibg==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCWXBe8ZxUmn88C4nuSLOspwodBvrdFicms6x8rzIYk/m2fqtndL9PeFLFZlTIiV31zQvYpKGvJi7jc7@gnusha.org
X-Gm-Message-State: AOJu0YwiWw6JRmA6lR6Ja0p88Er7CXtfGxnXXAehgiWN8fbr07b16UW4
	7E7c39rJJnpgq0Jcw7OzeHK3fkBnXspsyGxucy7Idw8/nRVeXHk+
X-Google-Smtp-Source: AGHT+IFJ2mg5d932CZtIPXFAka6gtA0M61lt/piEIGgpoeH/mABUHHG2iMSxNoUuY4kZTcFiAqh2Vg==
X-Received: by 2002:a05:6902:1201:b0:e39:8992:57c8 with SMTP id 3f1490d57ef6-e5328fcf290mr990728276.18.1734387763933;
        Mon, 16 Dec 2024 14:22:43 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:d394:0:b0:e38:94e3:87e with SMTP id 3f1490d57ef6-e43a6ee9a6dls550864276.0.-pod-prod-07-us;
 Mon, 16 Dec 2024 14:22:41 -0800 (PST)
X-Received: by 2002:a05:690c:4b0b:b0:6ee:66d2:e738 with SMTP id 00721157ae682-6f279adbfb9mr136552437b3.2.1734387761028;
        Mon, 16 Dec 2024 14:22:41 -0800 (PST)
Received: by 2002:a05:690c:fd3:b0:6ef:892f:89f3 with SMTP id 00721157ae682-6f278d02556ms7b3;
        Mon, 16 Dec 2024 14:20:05 -0800 (PST)
X-Received: by 2002:a05:690c:7443:b0:6ef:f020:601e with SMTP id 00721157ae682-6f2bbd280c7mr11843607b3.19.1734387604969;
        Mon, 16 Dec 2024 14:20:04 -0800 (PST)
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"
X-Original-Sender: rx@awsomnet.org
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.7 (/)

------=_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--