Delivery-date: Sun, 16 Mar 2025 11:31:41 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of martin.habovstiak@gmail.com designates 2607:f8b0:4864:20::92e as permitted sender) client-ip=2607:f8b0:4864:20::92e;
MIME-Version: 1.0
From: =?UTF-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>
Date: Sun, 16 Mar 2025 19:25:00 +0100
Message-ID: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
Subject: [bitcoindev] Hashed keys are actually fully quantum secure
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="000000000000c531b3063079ca58"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

--000000000000c531b3063079ca58
Content-Type: text/plain; charset="UTF-8"

Hello list,

this is somewhat related to Jameson's recent post but different enough to
warrant a separate topic.

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

It is possible to implement fully secure recovery if we forbid spending 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 fees
via external means, held on a QR script
2. the user creates a transaction that, aside from having a usual spendable
output also commits to a signature of QR public key. This proves that 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 and QR
output in a single transaction. Spending requires revealing the
previously-committed sigature. Spending the old output alone is invalid.

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

The only weakness I see is that (x)pubs would effectively become private
keys. However they already kinda are - one needs to protect xpubs for
privacy 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).

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

If the time comes I'd be happy to run a soft fork that implements this
sanely.

Cheers

Martin

-- 
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/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com.

--000000000000c531b3063079ca58
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto">Hello list,<div dir=3D"auto"><br></div><div dir=3D"auto">=
this is somewhat related to Jameson&#39;s recent post but different enough =
to warrant a separate topic.</div><div dir=3D"auto"><br></div><div dir=3D"a=
uto">As you have probably heard many times and even think yourself, &quot;h=
ashed keys are not actually secure, because a quantum attacker can just sna=
tch them from mempool&quot;. However this is not strictly true.</div><div d=
ir=3D"auto"><br></div><div dir=3D"auto">It is possible to implement fully s=
ecure recovery if we forbid spending of hashed keys unless done through the=
 following scheme:</div><div dir=3D"auto">0. we assume we have *some* QR si=
gning deployed, it can be done even after QC becomes viable (though not wit=
hout economic cost)</div><div dir=3D"auto">1. the user obtains a small amou=
nt of bitcoin sufficient to pay for fees via external means, held on a QR s=
cript</div><div dir=3D"auto">2. the user creates a transaction that, aside =
from having a usual spendable output also commits to a signature of QR publ=
ic key. This proves that the user knew the private key even though the publ=
ic key wasn&#39;t revealed yet.</div><div dir=3D"auto">3. after sufficient =
number of blocks, the user spends both the old and QR output in a single tr=
ansaction. Spending requires revealing the previously-committed sigature. S=
pending the old output alone is invalid.</div><div dir=3D"auto"><br></div><=
div dir=3D"auto">This way, the attacker would have to revert the chain to s=
teal which is assumed impossible.</div><div dir=3D"auto"><br></div><div dir=
=3D"auto">The only weakness I see is that (x)pubs would effectively become =
private keys. However they already kinda are - one needs to protect xpubs f=
or privacy and to avoid the risk of getting marked as &quot;dirty&quot; by =
some agencies, which can theoretically render them unspendable. And non-x-p=
ubs generally do not leak alone (no reason to reveal them without spending)=
.</div><div dir=3D"auto"><br></div><div dir=3D"auto">I think that the mere =
possibility of this scheme has two important implications:</div><div dir=3D=
"auto">* the need to have &quot;a QR scheme&quot; ready now in case of a QC=
 coming tomorrow is much smaller than previously thought. Yes, doing it too=
 late has the effect of temporarily freezing coins which is costly and we d=
on&#39;t want that but it&#39;s not nearly as bad as theft</div><div dir=3D=
"auto">* freezing of *these* coins would be both immoral and extremely dang=
erous for reputation of Bitcoin (no comments on freezing coins with reveale=
d pubkeys, I haven&#39;t made my mind yet)</div><div dir=3D"auto"><br></div=
><div dir=3D"auto">If the time comes I&#39;d be happy to run a soft fork th=
at implements this sanely.</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">Cheers</div><div dir=3D"auto"><br></div><div dir=3D"auto">Martin</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/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gma=
il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/=
msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40ma=
il.gmail.com</a>.<br />

--000000000000c531b3063079ca58--