Delivery-date: Mon, 17 Mar 2025 06:36:28 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of lloyd.fourn@gmail.com designates 2607:f8b0:4864:20::836 as permitted sender) client-ip=2607:f8b0:4864:20::836;
MIME-Version: 1.0
References: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
In-Reply-To: <CALkkCJY=dv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ@mail.gmail.com>
From: Lloyd Fournier <lloyd.fourn@gmail.com>
Date: Mon, 17 Mar 2025 21:44:23 +1100
Message-ID: <CAH5Bsr3Yx1n22svy7QCTkT_BdzxLUqSmaR6Ji+v7Zf4Pph9S7w@mail.gmail.com>
Subject: Re: [bitcoindev] Hashed keys are actually fully quantum secure
To: =?UTF-8?Q?Martin_Habov=C5=A1tiak?= <martin.habovstiak@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="0000000000005523640630877aec"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

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

This seems like a very clever idea. It allows us to mostly ignore the QC
question until a threat actually materializes and then soft fork to
disallow bare public key spending with minimal actions needed to be taken
by users. Nice work!

A couple of important points:
- Taproot keys are also "hashed keys" since the internal key is technically
hashed to produce the external. If you disallow key path spend you can
apply the same rule by using the internal key to produce the commitment
signature.
- Taproot keys are actually better hashed keys since you don't have to
worry about whether you've revealed your public key on-chain in the past
e.g. via address re-use if you use external key spends (since this doesn't
reveal your internal key).

If this approach gains acceptance I think the main immediate action users
can take is to move to a taproot wallet. I predict trying to advise people
to move to p2pkh addresses or that p2pkh addresses are "fine" will create
confusion since there are huge numbers of coins in p2pkh addresses whose
public key has already been revealed and people may do address reuse
without knowing it.
Also an attractive approach is to embed the QR signature scheme in a
tapleaf before activating it so that most coins already have a QR spending
path ready to go. This is more straightforward if taproot is normalized
first.
I understand that people might feel "less protected" on a taproot address
because they might get sniped by the QC attacker before the freezing fork
has been activated but I don't think this is a serious concern relative to
the millions of coins available with known public keys. We have to freeze
it before they can be taken.

So outside of cryptography, the difficult task is to come to a social
consensus mechanism about when to trigger the freezing soft fork. It should
be done *before* a secp256k1 DLOG QC can be built but *after* we know that
one can be built. Right now it is certainly not clear that one *can* be
built ever and we won't have any indication this decade and maybe the next.
It may be a matter of debate whether we've reached that point in 10 years
(it certainly isn't now) and you can imagine malicious actors trying to
subvert the process either to hold it back or to push it forward.

LL

On Mon, 17 Mar 2025 at 05:31, Martin Habov=C5=A1tiak <martin.habovstiak@gma=
il.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
> <https://groups.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-=
byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.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/=
CAH5Bsr3Yx1n22svy7QCTkT_BdzxLUqSmaR6Ji%2Bv7Zf4Pph9S7w%40mail.gmail.com.

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

<div dir=3D"ltr"><div dir=3D"ltr">This seems like a very clever idea. It al=
lows us to mostly ignore the QC question until a threat actually materializ=
es and then soft fork to disallow bare public key spending with minimal act=
ions needed to be taken by users. Nice work!<br><br>A couple of important p=
oints:<br>- Taproot keys are also &quot;hashed keys&quot; since the interna=
l key is technically hashed to produce the external. If you disallow key pa=
th spend you can apply the same rule by using the internal key to produce t=
he commitment signature.<br>- Taproot keys are actually better hashed keys =
since you don&#39;t have to worry about whether you&#39;ve revealed your pu=
blic key on-chain in the past e.g. via address re-use if you use external k=
ey spends (since this doesn&#39;t reveal your internal key).<br><br>If this=
 approach gains acceptance I think the main immediate action users can take=
 is to move to a taproot wallet. I predict trying to advise people to move =
to p2pkh addresses or that p2pkh addresses are &quot;fine&quot; will create=
 confusion since there are huge numbers of coins in p2pkh addresses whose p=
ublic key has already been revealed and people may do address reuse without=
 knowing it.<br>Also an attractive approach is to embed the QR signature sc=
heme in a tapleaf before activating it so that most coins already have a QR=
 spending path ready to go. This is more straightforward if taproot is norm=
alized first.<br>I understand that people might feel &quot;less protected&q=
uot; on a taproot address because they might get sniped by the QC attacker =
before the freezing fork has been activated but I don&#39;t think this is a=
 serious concern relative to the millions of coins available with known pub=
lic keys. We have to freeze it before they can be taken.<br><br>So outside =
of cryptography, the difficult task is to come to a social consensus mechan=
ism about when to trigger the freezing soft fork. It should be done *before=
* a secp256k1 DLOG QC can be built but *after* we know that one can be buil=
t. Right now it is certainly not clear that one *can* be built ever and we =
won&#39;t have any indication this decade and maybe the next. It may be a m=
atter of debate whether we&#39;ve reached that point in 10 years (it certai=
nly isn&#39;t now) and you can imagine malicious actors trying to subvert t=
he process either to hold it back or to push it forward.<br><br>LL</div><br=
><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Mon, 1=
7 Mar 2025 at 05:31, Martin Habov=C5=A1tiak &lt;<a href=3D"mailto:martin.ha=
bovstiak@gmail.com" target=3D"_blank">martin.habovstiak@gmail.com</a>&gt; w=
rote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0p=
x 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><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 warra=
nt 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, &quot;hashed ke=
ys 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"au=
to"><br></div><div dir=3D"auto">It is possible to implement fully secure re=
covery if we forbid spending of hashed keys unless done through the followi=
ng scheme:</div><div dir=3D"auto">0. we assume we have *some* QR signing de=
ployed, it can be done even after QC becomes viable (though not without eco=
nomic cost)</div><div dir=3D"auto">1. the user obtains a small amount of bi=
tcoin sufficient to pay for fees via external means, held on a QR script</d=
iv><div dir=3D"auto">2. the user creates a transaction that, aside from hav=
ing 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 w=
asn&#39;t revealed yet.</div><div dir=3D"auto">3. after sufficient number o=
f blocks, the user spends both the old and QR output in a single transactio=
n. 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 the chain to steal wh=
ich is assumed impossible.</div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">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 priv=
acy and to avoid the risk of getting marked as &quot;dirty&quot; by some ag=
encies, which can theoretically render them unspendable. And non-x-pubs gen=
erally 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 possibi=
lity 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 h=
as the effect of temporarily freezing coins which is costly 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 extremely dangerous f=
or reputation of Bitcoin (no comments on freezing coins with revealed pubke=
ys, I haven&#39;t made my mind yet)</div><div dir=3D"auto"><br></div><div d=
ir=3D"auto">If the time comes I&#39;d be happy to run a soft fork that impl=
ements this sanely.</div><div dir=3D"auto"><br></div><div dir=3D"auto">Chee=
rs</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" target=
=3D"_blank">bitcoindev+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&amp;utm_source=3Dfooter" target=3D"_blank">https:=
//groups.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3J=
t2DRr20yZqMmdJUnQ%40mail.gmail.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/CAH5Bsr3Yx1n22svy7QCTkT_BdzxLUqSmaR6Ji%2Bv7Zf4Pph9S7w%40mail.gma=
il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/=
msgid/bitcoindev/CAH5Bsr3Yx1n22svy7QCTkT_BdzxLUqSmaR6Ji%2Bv7Zf4Pph9S7w%40ma=
il.gmail.com</a>.<br />

--0000000000005523640630877aec--