Delivery-date: Sun, 23 Mar 2025 18:28:49 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of lloyd.fourn@gmail.com designates 2607:f8b0:4864:20::82b as permitted sender) client-ip=2607:f8b0:4864:20::82b;
MIME-Version: 1.0
References: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
 <XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE=@protonmail.com>
In-Reply-To: <XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE=@protonmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Mon, 24 Mar 2025 11:24:38 +1100
Message-ID: <CAH5Bsr0muoF27besnoQh32vL-keujeR+d-_JurE0+yXY5gPKQg@mail.gmail.com>
Subject: Re: [bitcoindev] Hashed keys are actually fully quantum secure
To: Antoine Poinsot <darosior@protonmail.com>
Cc: =?UTF-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>, 
	Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="000000000000c3f5db06310ba235"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

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

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

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 spen=
t
> along with a QR output at least X blocks old. This would give the honest
> user a headstart in this race, but meh.
>

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

LL


> On Sunday, March 16th, 2025 at 2:25 PM, Martin Habov=C5=A1tiak <
> martin.habovstiak@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
> 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 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
> spendable output also commits to a signature of QR public key. This prove=
s
> 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 tomorro=
w
> 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 th=
at
> 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-b=
yGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com
> .
>
>
> --
> 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/XHIL8Z4i4hji8LhbJ0AiKQ4eago2=
evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4=
txKE%3D%40protonmail.com
> <https://groups.google.com/d/msgid/bitcoindev/XHIL8Z4i4hji8LhbJ0AiKQ4eago=
2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-=
4txKE%3D%40protonmail.com?utm_medium=3Demail&utm_source=3Dfooter>
> .
>

--=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/=
CAH5Bsr0muoF27besnoQh32vL-keujeR%2Bd-_JurE0%2ByXY5gPKQg%40mail.gmail.com.

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

<div dir=3D"ltr"><div dir=3D"ltr"><br></div><br><div class=3D"gmail_quote g=
mail_quote_container"><div dir=3D"ltr" class=3D"gmail_attr">On Tue, 18 Mar =
2025 at 00:48, &#39;Antoine Poinsot&#39; via Bitcoin Development Mailing Li=
st &lt;<a href=3D"mailto:bitcoindev@googlegroups.com">bitcoindev@googlegrou=
ps.com</a>&gt; wrote:</div><div dir=3D"ltr" class=3D"gmail_attr"><br></div>=
<blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-=
left:1px solid rgb(204,204,204);padding-left:1ex"><div style=3D"font-family=
:Arial,sans-serif;font-size:14px">I suppose you could in theory have, in ad=
dition to making spending old outputs invalid on their own, a rule which di=
ctates they may only be spent along with a QR output at least X blocks old.=
 This would give the honest user a headstart in this race, but meh.<br></di=
v></blockquote><div><br></div><div>Yes this is how I read the OP &quot;afte=
r sufficient number of blocks&quot;. I think this is a really nice idea. Th=
e head start can be arbitrarily large so that the attacker simply cannot co=
mpete. It&#39;s probably not too difficult to design some honest RBF mechan=
ism either such that you can bump the fee with a new QR signature if it&#39=
;s taking too long.</div><div><br></div><div>LL</div><div><br></div><div>=
=C2=A0</div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0=
.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style=3D=
"font-family:Arial,sans-serif;font-size:14px"></div><div>
        On Sunday, March 16th, 2025 at 2:25 PM, Martin Habov=C5=A1tiak &lt;=
<a href=3D"mailto:martin.habovstiak@gmail.com" target=3D"_blank">martin.hab=
ovstiak@gmail.com</a>&gt; wrote:<br>
        <blockquote 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&#39;s recent post but diffe=
rent 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 yours=
elf, &quot;hashed keys are not actually secure, because a quantum attacker =
can just snatch them from mempool&quot;. However this is not strictly true.=
</div><div dir=3D"auto"><br></div><div dir=3D"auto">It is possible to imple=
ment fully secure 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 signing deployed, it can be done even after QC becomes viable (th=
ough not without economic cost)</div><div dir=3D"auto">1. the user obtains =
a small amount of bitcoin sufficient to pay for fees via external means, he=
ld on a QR script</div><div dir=3D"auto">2. the user creates a transaction =
that, aside from having a usual spendable output also commits to a signatur=
e of QR public key. This proves that the user knew the private key even tho=
ugh the public 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 transaction. Spending requires revealing the previously-committed=
 sigature. Spending 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 th=
e chain to steal 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 effecti=
vely become private keys. However they already kinda are - one needs to pro=
tect xpubs for privacy and to avoid the risk of getting marked as &quot;dir=
ty&quot; by some agencies, which can theoretically render them unspendable.=
 And non-x-pubs generally do not leak alone (no reason to reveal them witho=
ut spending).</div><div dir=3D"auto"><br></div><div dir=3D"auto">I think th=
at 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 cos=
tly and we don&#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 ex=
tremely dangerous for reputation of Bitcoin (no comments on freezing coins =
with revealed pubkeys, I haven&#39;t made my mind yet)</div><div dir=3D"aut=
o"><br></div><div dir=3D"auto">If the time comes I&#39;d be happy to run a =
soft fork that implements this sanely.</div><div dir=3D"auto"><br></div><di=
v dir=3D"auto">Cheers</div><div dir=3D"auto"><br></div><div dir=3D"auto">Ma=
rtin</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" rel=3D"n=
oreferrer nofollow noopener" target=3D"_blank">bitcoindev+unsubscribe@googl=
egroups.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" rel=3D"noreferrer nofollow noopener" target=3D"_blank">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" target=
=3D"_blank">bitcoindev+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&amp;utm_source=3Dfooter" target=3D"_blank">https://groups.google.c=
om/d/msgid/bitcoindev/XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDp=
Ho6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com<=
/a>.<br>
</blockquote></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/CAH5Bsr0muoF27besnoQh32vL-keujeR%2Bd-_JurE0%2ByXY5gPKQg%40mail.g=
mail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/=
d/msgid/bitcoindev/CAH5Bsr0muoF27besnoQh32vL-keujeR%2Bd-_JurE0%2ByXY5gPKQg%=
40mail.gmail.com</a>.<br />

--000000000000c3f5db06310ba235--