Delivery-date: Sun, 25 May 2025 11:39:02 -0700
Received-SPF: pass (google.com: domain of conduition@proton.me designates 79.135.106.30 as permitted sender) client-ip=79.135.106.30;
Date: Sun, 25 May 2025 18:22:47 +0000
To: Lloyd Fournier <lloyd.fourn@gmail.com>
From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Cc: Antoine Poinsot <darosior@protonmail.com>, =?utf-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>, Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Hashed keys are actually fully quantum secure
Message-ID: <Rgj4DeSKQkdEWMRTmqYYLas84WIDyRftEKqmwlw0C9-ur4Tx9_d6g7SzTU_WBspYbezLDTMpgIFXon1_cpFSjgYOMtHlQJNS_utF2dZQ4ig=@proton.me>
In-Reply-To: <CAH5Bsr0muoF27besnoQh32vL-keujeR+d-_JurE0+yXY5gPKQg@mail.gmail.com>
References: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com> <XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE=@protonmail.com> <CAH5Bsr0muoF27besnoQh32vL-keujeR+d-_JurE0+yXY5gPKQg@mail.gmail.com>
Feedback-ID: 72003692:user:proton
MIME-Version: 1.0
Content-Type: multipart/signed; protocol="application/pgp-signature"; micalg=pgp-sha512; boundary="------750e04dc2af4165e16320527de00cbc0337b1d719ebf0be88b479807590197df"; charset=utf-8
Reply-To: conduition <conduition@proton.me>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

This is an OpenPGP/MIME signed message (RFC 4880 and 3156)
--------750e04dc2af4165e16320527de00cbc0337b1d719ebf0be88b479807590197df
Content-Type: multipart/mixed;boundary=---------------------aa5f66b12d3325082959de1875834ce7

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

Hey friends,

Even if we can require a pre-quantum output to be paired with
a QR output when spending in this way, and even if the QR output
must be at least X blocks old... What prevents an attacker from
just pre-minting a whole bunch of QR outputs, aging them for a while,
and then lying in wait to steal?

A well-prepared QC attacker's QR outputs may even be significantly
older than an honest user's QR outputs. An aged QR output committing
to a QR signature proves nothing about the ownership of an unrelated
pre-quantum UTXO.

The QR output must prove historical ownership of the vulnerable
EC key-hashed output. To fix this, we must change this line in OP:

> 2. the user creates a transaction that, aside from having a usual
> spendable output also commits to a signature of QR public key.

This transaction must be fully protected by QR signing. It must
commit to, but not reveal, the EC public key, while also proving
ownership. I would correct this description to:

> 2. the user creates a transaction with at least one QR input which,
> aside from having a usual spendable output also commits to
>=C2=A0*a signature from the legacy EC pubkey.*

This TX might have an OP_RETURN output or an inscription which embeds=20

SHA256(ec_signature).=C2=A0 Or, like taproot, the QR output script might
itself contain a hidden commitment to that hash.=C2=A0

A few blocks after this transaction is mined, the honest user can
spend the QR and legacy UTXOs together, opening the EC signature
commitment. Validating nodes would have to check the QR output is
old enough, but also check that it committed to the correct
pubkey+signature.

A QC attacker shouldn't be able to break this unless the legacy EC
pubkey has already been revealed prior to the commitment TX.
Only the authentic user could've pre-committed to that signature.
If we assume the QC attacker can't roll-back the chain more than
X blocks, they can't go back and insert an EC sig commitment
retroactively.

I suspect this might've been Martin's intent, judging from the way he
was writing?

regards,
conduition


On Sunday, March 23rd, 2025 at 8:24 PM, Lloyd Fournier <lloyd.fourn@gmail.c=
om> wrote:

>=20

>=20

> On Tue, 18 Mar 2025 at 00:48, 'Antoine Poinsot' via Bitcoin Development M=
ailing List <bitcoindev@googlegroups.com> wrote:
>=20

>=20

> > I suppose you could in theory have, in addition to making spending old =
outputs invalid on their own, a rule which dictates they may only be spent =
along with a QR output at least X blocks old. This would give the honest us=
er a headstart in this race, but meh.
>=20

>=20

> Yes this is how I read the OP "after sufficient number of blocks". I thin=
k this is a really nice idea. The head start can be arbitrarily large so th=
at the attacker simply cannot compete. It's probably not too difficult to d=
esign some honest RBF mechanism either such that you can bump the fee with =
a new QR signature if it's taking too long.
>=20

> LL
>=20

>=20

> > On Sunday, March 16th, 2025 at 2:25 PM, Martin Habov=C5=A1tiak <martin.=
habovstiak@gmail.com> wrote:
> >=20

> > > Hello list,
> > > this is somewhat related to Jameson's recent post but different enoug=
h to warrant a separate topic.
> > >=20

> > > As you have probably heard many times and even think yourself, "hashe=
d keys are not actually secure, because a quantum attacker can just snatch =
them from mempool". However this is not strictly true.
> > >=20

> > > It is possible to implement fully secure recovery if we forbid spendi=
ng of hashed keys unless done through the following scheme:
> > > 0. we assume we have *some* QR signing deployed, it can be done even =
after QC becomes viable (though not without economic cost)
> > > 1. the user obtains a small amount of bitcoin sufficient to pay for f=
ees via external means, held on a QR script
> > > 2. the user creates a transaction that, aside from having a usual spe=
ndable output also commits to a signature of QR public key. This proves tha=
t the user knew the private key even though the public key wasn't revealed =
yet.
> > > 3. after sufficient number of blocks, the user spends both the old an=
d QR output in a single transaction. Spending requires revealing the previo=
usly-committed sigature. Spending the old output alone is invalid.
> > >=20

> > > This way, the attacker would have to revert the chain to steal which =
is assumed impossible.
> > >=20

> > > The only weakness I see is that (x)pubs would effectively become priv=
ate keys. However they already kinda are - one needs to protect xpubs for p=
rivacy and to avoid the risk of getting marked as "dirty" by some agencies,=
 which can theoretically render them unspendable. And non-x-pubs generally =
do not leak alone (no reason to reveal them without spending).
> > >=20

> > > I think that the mere possibility of this scheme has two important im=
plications:
> > > * the need to have "a QR scheme" ready now in case of a QC coming tom=
orrow is much smaller than previously thought. Yes, doing it too late has t=
he effect of temporarily freezing coins which is costly and we don't want t=
hat but it's not nearly as bad as theft
> > > * freezing of *these* coins would be both immoral and extremely dange=
rous for reputation of Bitcoin (no comments on freezing coins with revealed=
 pubkeys, I haven't made my mind yet)
> > >=20

> > > If the time comes I'd be happy to run a soft fork that implements thi=
s sanely.
> > >=20

> > > Cheers
> > >=20

> > > Martin
> > >=20

> > > --
> > > You received this message because you are subscribed to the Google Gr=
oups "Bitcoin Development Mailing List" group.
> > > To unsubscribe from this group and stop receiving emails from it, sen=
d an email to bitcoindev+unsubscribe@googlegroups.com.
> > > To view this discussion visit https://groups.google.com/d/msgid/bitco=
indev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.co=
m.
> >=20

> > --
> > You received this message because you are subscribed to the Google Grou=
ps "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/bitcoin=
dev/XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSL=
j_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com.
>=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=
 email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoinde=
v/CAH5Bsr0muoF27besnoQh32vL-keujeR%2Bd-_JurE0%2ByXY5gPKQg%40mail.gmail.com.

--=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/=
Rgj4DeSKQkdEWMRTmqYYLas84WIDyRftEKqmwlw0C9-ur4Tx9_d6g7SzTU_WBspYbezLDTMpgIF=
Xon1_cpFSjgYOMtHlQJNS_utF2dZQ4ig%3D%40proton.me.

-----------------------aa5f66b12d3325082959de1875834ce7
Content-Type: application/pgp-keys; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="publickey - conduition@proton.me - 0x474891AD.asc"; name="publickey - conduition@proton.me - 0x474891AD.asc"

LS0tLS1CRUdJTiBQR1AgUFVCTElDIEtFWSBCTE9DSy0tLS0tCgp4ak1FWkRub0tSWUpLd1lCQkFI
YVJ3OEJBUWRBcnBZYWFjZDgwcXdocmNaQW9VbW9NSHNWS21iZWlPZUEKcFhXbk1ybFdPZkxOSzJO
dmJtUjFhWFJwYjI1QWNISnZkRzl1TG0xbElEeGpiMjVrZFdsMGFXOXVRSEJ5CmIzUnZiaTV0WlQ3
Q2pBUVFGZ29BUGdXQ1pEbm9LUVFMQ1FjSUNaQjRLV3p0aFBhenhRTVZDQW9FRmdBQwpBUUlaQVFL
YkF3SWVBUlloQkVkSWthMENNdHJMZGcxM2EzZ3BiTzJFOXJQRkFBQTZhQUVBM1RmNHdqSVoKYnox
K0diS0h4K09WQytNUXlVdi84RStoWUpjTE5QZnA0NEFBLzNiak5OTXN4WHdJTGZEM0xManNVVWFo
CitBV2JyblVjVUFqQ2R1d3hUT01LempnRVpEbm9LUklLS3dZQkJBR1hWUUVGQVFFSFFDSXYxZW5J
MU5MbAo3Zm55RzlVWk1wQ3ZsdG5vc0JrTmhQUVZxT3BXL3RKSkF3RUlCOEo0QkJnV0NBQXFCWUpr
T2VncENaQjQKS1d6dGhQYXp4UUtiREJZaEJFZElrYTBDTXRyTGRnMTNhM2dwYk8yRTlyUEZBQUFR
TFFEL2NCR2kwUDdwCkZTTkl2N1B6OVpkeUNVQjhzTy90dWZkV3NjQkNZK2ZMYTV3QkFNK0hTL3Jp
S014RGt0TkhLakRGc2EvUgpEVDFxUGNBYXZCaXc2dDZ4Ti9jRgo9Y3d5eAotLS0tLUVORCBQR1Ag
UFVCTElDIEtFWSBCTE9DSy0tLS0tCg==
-----------------------aa5f66b12d3325082959de1875834ce7--

--------750e04dc2af4165e16320527de00cbc0337b1d719ebf0be88b479807590197df
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: OpenPGP digital signature
Content-Disposition: attachment; filename="signature.asc"

-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wrsEARYKAG0FgmgzX+gJkHgpbO2E9rPFRRQAAAAAABwAIHNhbHRAbm90YXRp
b25zLm9wZW5wZ3Bqcy5vcmek+gkfZpeIR/1d4KNqFMIwUlA4ex5KfeJYiiPy
h8PkoRYhBEdIka0CMtrLdg13a3gpbO2E9rPFAAAHUAD/Qia44dPRW/VQW0/g
59fV5d+2n9B5lXp30DywpUA3eHsBAPqUe3UupTuR2P3LnPFZ6cFwOdvR9oOI
k69HfYd8/P4A
=qQup
-----END PGP SIGNATURE-----


--------750e04dc2af4165e16320527de00cbc0337b1d719ebf0be88b479807590197df--