Delivery-date: Mon, 17 Mar 2025 06:49:02 -0700
Received-SPF: pass (google.com: domain of darosior@protonmail.com designates 185.70.43.22 as permitted sender) client-ip=185.70.43.22;
Date: Sun, 16 Mar 2025 18:50:45 +0000
To: =?utf-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>
From: "'Antoine Poinsot' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Hashed keys are actually fully quantum secure
Message-ID: <XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE=@protonmail.com>
In-Reply-To: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
References: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
Feedback-ID: 7060259:user:proton
MIME-Version: 1.0
Content-Type: multipart/alternative;
 boundary="b1=_hClUf7Eq5SqjRpKoGPXdd2QGIwvtUK2MV2SRVpYRo"
Reply-To: Antoine Poinsot <darosior@protonmail.com>
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

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

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

Or just create its own "QR output"?

If your threat model assumes an attacker can promptly recover the private k=
ey from the public key then once the user broadcasts his transaction spendi=
ng both the old output and his own QR output the attacker could simply crea=
te his own QR output and RBF the honest transaction.

I suppose you could in theory have, in addition to making spending old outp=
uts invalid on their own, a rule which dictates they may only be spent alon=
g with a QR output at least X blocks old. This would give the honest user a=
 headstart in this race, but meh.
On Sunday, March 16th, 2025 at 2:25 PM, Martin Habov=C5=A1tiak <martin.habo=
vstiak@gmail.com> wrote:

> 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 ke=
ys 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 o=
f hashed keys unless done through the following scheme:
> 0. we assume we have *some* QR signing deployed, it can be done even afte=
r 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 spendab=
le output also commits to a signature of QR public key. This proves that th=
e 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 a=
ssumed 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 priva=
cy and to avoid the risk of getting marked as "dirty" by some agencies, whi=
ch can theoretically render them unspendable. And non-x-pubs generally do n=
ot leak alone (no reason to reveal them without spending).
>
> I think that the mere possibility of this scheme has two important implic=
ations:
> * the need to have "a QR scheme" ready now in case of a QC coming tomorro=
w is much smaller than previously thought. Yes, doing it too late has the e=
ffect 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 pub=
keys, I haven't made my mind yet)
>
> If the time comes I'd be happy to run a soft fork that implements this sa=
nely.
>
> 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/bitcoinde=
v/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%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/=
XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_Gu=
iTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com.

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

<blockquote style=3D"border-left: 3px solid rgb(200, 200, 200); border-colo=
r: rgb(200, 200, 200); padding-left: 10px; color: rgb(102, 102, 102);"><div=
 style=3D"font-family: Arial, sans-serif; font-size: 14px;"><span dir=3D"au=
to"></span><span dir=3D"auto">This way, the attacker would have to revert t=
he chain to steal which is assumed impossible.</span><br></div></blockquote=
>
<div class=3D"protonmail_signature_block protonmail_signature_block-empty" =
style=3D"font-family: Arial, sans-serif; font-size: 14px;">
    <div class=3D"protonmail_signature_block-user protonmail_signature_bloc=
k-empty">
       =20
            </div>
   =20
            <div class=3D"protonmail_signature_block-proton protonmail_sign=
ature_block-empty">
       =20
            </div>
</div>
<div style=3D"font-family: Arial, sans-serif; font-size: 14px;"><br></div><=
div style=3D"font-family: Arial, sans-serif; font-size: 14px;">Or just crea=
te its own "QR output"?</div><div style=3D"font-family: Arial, sans-serif; =
font-size: 14px;"><br></div><div style=3D"font-family: Arial, sans-serif; f=
ont-size: 14px;">If your threat model assumes an attacker can promptly reco=
ver the private key from the public key then once the user broadcasts his t=
ransaction spending both the old output and his own QR output the attacker =
could simply create his own QR output and RBF the honest transaction.</div>=
<div style=3D"font-family: Arial, sans-serif; font-size: 14px;"><br></div><=
div style=3D"font-family: Arial, sans-serif; font-size: 14px;">I suppose yo=
u 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 user a headstart i=
n this race, but meh.<br></div><div class=3D"protonmail_quote">
        On Sunday, March 16th, 2025 at 2:25 PM, Martin Habov=C5=A1tiak &lt;=
martin.habovstiak@gmail.com&gt; wrote:<br>
        <blockquote class=3D"protonmail_quote" type=3D"cite">
            <div dir=3D"auto">Hello list,<div dir=3D"auto"><br></div><div d=
ir=3D"auto">this is somewhat related to Jameson's recent post but different=
 enough to warrant a separate topic.</div><div dir=3D"auto"><br></div><div =
dir=3D"auto">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.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">It is possible to implement fully sec=
ure recovery if we forbid spending of hashed keys unless done through the f=
ollowing scheme:</div><div dir=3D"auto">0. we assume we have *some* QR sign=
ing deployed, it can be done even after QC becomes viable (though not witho=
ut economic cost)</div><div dir=3D"auto">1. the user obtains a small amount=
 of bitcoin sufficient to pay for fees via external means, held on a QR scr=
ipt</div><div dir=3D"auto">2. the user creates a transaction that, aside fr=
om 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.</div><div dir=3D"auto">3. after sufficient number=
 of blocks, the user spends both the old and QR output in a single transact=
ion. Spending requires revealing the previously-committed sigature. Spendin=
g the old output alone is invalid.</div><div dir=3D"auto"><br></div><div di=
r=3D"auto">This way, the attacker would have to revert the chain to steal w=
hich is assumed impossible.</div><div dir=3D"auto"><br></div><div dir=3D"au=
to">The only weakness I see is that (x)pubs would effectively become privat=
e keys. However they already kinda are - one needs to protect xpubs for pri=
vacy and to avoid the risk of getting marked as "dirty" by some agencies, w=
hich can theoretically render them unspendable. And non-x-pubs 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 ne=
ed 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 t=
emporarily freezing coins which is costly and we don't want that but it's n=
ot nearly as bad as theft</div><div dir=3D"auto">* freezing of *these* coin=
s 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)</div><div dir=3D"auto"><br></div><div dir=3D"auto">If the time comes =
I'd be happy to run a soft fork that implements this sanely.</div><div dir=
=3D"auto"><br></div><div dir=3D"auto">Cheers</div><div dir=3D"auto"><br></d=
iv><div dir=3D"auto">Martin</div></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups "=
Bitcoin Development Mailing List" 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" rel=3D"n=
oreferrer nofollow noopener">bitcoindev+unsubscribe@googlegroups.com</a>.<b=
r>
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gma=
il.com" target=3D"_blank" rel=3D"noreferrer nofollow noopener">https://grou=
ps.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr2=
0yZqMmdJUnQ%40mail.gmail.com</a>.<br>

        </blockquote><br>
    </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/XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAH=
PUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com?utm_medium=
=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoindev/=
XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_Gu=
iTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com</a>.<br />

--b1=_hClUf7Eq5SqjRpKoGPXdd2QGIwvtUK2MV2SRVpYRo--