From: Nagaev Boris <bnagaev@gmail•com>
To: conduition <conduition@proton•me>
Cc: "Lloyd Fournier" <lloyd.fourn@gmail•com>,
"Antoine Poinsot" <darosior@protonmail•com>,
"Martin Habovštiak" <martin.habovstiak@gmail•com>,
"Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Hashed keys are actually fully quantum secure
Date: Mon, 26 May 2025 07:03:01 -0300 [thread overview]
Message-ID: <CAFC_Vt4wjLV_iAHYDMcAJYP=PRo=jNWQzmrUfJUK2_GXTiPnjA@mail.gmail.com> (raw)
In-Reply-To: <Rgj4DeSKQkdEWMRTmqYYLas84WIDyRftEKqmwlw0C9-ur4Tx9_d6g7SzTU_WBspYbezLDTMpgIFXon1_cpFSjgYOMtHlQJNS_utF2dZQ4ig=@proton.me>
Hey Conduition,
Isn't this a bit of a chicken-and-egg issue? The EC signature signs
the second transaction, which depends on the QR output's txid, which
in turn depends on the precommitted EC signature. One way to break
this circular dependency is to use the SIGHASH ANYONECANPAY modifier
to exclude the QR output from the EC signature scope. Or an
inscription can be used to commit to the EC signature without
affecting the txid of the first transaction.
That said, I've been thinking about an alternative approach that might
also be more convenient in practice.
What if we commit to the SHA256 of the EC public key instead of the EC
signature? If this hash is included in a QR output at least X blocks
in advance, it offers the same security under the assumption that a
quantum attacker can recover the private key from the public key.
However, there's a problem: an attacker can observe the creation of QR
outputs and create their own outputs committing to the same
SHA256(pubkey) in advance. To prevent this, the commitment to the EC
pubkey hash must be hidden from observers. One way to achieve this is
by embedding SHA256(pubkey) in a Taproot leaf. Since Taproot leaves
are not visible on-chain until revealed, the attacker can't learn
which pubkeys are being committed to. Once the commitment is revealed
at spend time, it's too late for the attacker to make a QR output and
wait out the delay. Multiple EC inputs of a transaction can reuse the
same QR input of the transaction.
The pubkey (and its SHA256 hash) is only revealed when spending an EC
output. A new consensus rule would require that such a spend be
accompanied by a QR output, with a tapleaf committing to the SHA256 of
the same EC pubkey, created at least X blocks earlier and spent in the
same transaction. An attacker seeing the EC pubkey in the mempool
would have to create their own QR output committing to the same hash,
mine it, wait X blocks, and then attempt an RBF — but by then, the
legitimate transaction would likely be confirmed.
From a usability standpoint, this seems cleaner: the user can
precommit to the SHA256 of the EC pubkey in advance and decide how to
spend it later. For example, if you're managing multiple EC UTXOs
(say, 10), you can commit to all of them in a single transaction
creating QR outputs, and handle second-stage spends later as needed.
This is not only simpler but also more efficient. You can also create
a single QR output with many tapleaves committing to SHA256 hashes of
multiple EC pubkeys, and spend all the EC coins plus one QR coin in a
single transaction.
In the original scheme, if the user has multiple EC UTXOs on the same
legacy EC address, they would need to create a separate QR output for
each one and spend all EC+QR pairs together in a single transaction.
With this alternative, a single QR output committing to the pubkey
hash can authorize the spend of multiple EC UTXOs in one transaction.
That significantly reduces the number of QR outputs required when
consolidating funds from a single EC key. Note that such coins must be
spent all together in both schemes, because spending a subset reveals
the EC pubkey, making the remaining coins vulnerable.
Would be curious to hear if others have considered this route or see
potential pitfalls.
Best,
Boris
On Sun, May 25, 2025 at 3:38 PM 'conduition' via Bitcoin Development
Mailing List <bitcoindev@googlegroups.com> wrote:
>
> 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
> > *a signature from the legacy EC pubkey.*
>
> This TX might have an OP_RETURN output or an inscription which embeds
>
> SHA256(ec_signature). Or, like taproot, the QR output script might
> itself contain a hidden commitment to that hash.
>
> 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•com> wrote:
>
> >
>
> >
>
> > 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 spent 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štiak <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 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.
> > >
>
> > > --
> > > 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/XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.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/CAH5Bsr0muoF27besnoQh32vL-keujeR%2Bd-_JurE0%2ByXY5gPKQg%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/Rgj4DeSKQkdEWMRTmqYYLas84WIDyRftEKqmwlw0C9-ur4Tx9_d6g7SzTU_WBspYbezLDTMpgIFXon1_cpFSjgYOMtHlQJNS_utF2dZQ4ig%3D%40proton.me.
--
Best regards,
Boris Nagaev
--
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/CAFC_Vt4wjLV_iAHYDMcAJYP%3DPRo%3DjNWQzmrUfJUK2_GXTiPnjA%40mail.gmail.com.
next prev parent reply other threads:[~2025-05-26 15:43 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-03-16 18:25 Martin Habovštiak
2025-03-16 18:50 ` 'Antoine Poinsot' via Bitcoin Development Mailing List
2025-03-18 16:48 ` Erik Aronesty
2025-03-24 0:24 ` Lloyd Fournier
2025-03-30 20:16 ` Martin Habovštiak
2025-05-25 18:22 ` 'conduition' via Bitcoin Development Mailing List
2025-05-26 10:03 ` Nagaev Boris [this message]
2025-03-16 19:03 ` Agustin Cruz
2025-03-16 20:52 ` Martin Habovštiak
2025-03-17 10:44 ` Lloyd Fournier
2025-03-17 11:07 ` Martin Habovštiak
2025-03-30 15:41 ` David A. Harding
2025-03-30 20:11 ` Martin Habovštiak
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='CAFC_Vt4wjLV_iAHYDMcAJYP=PRo=jNWQzmrUfJUK2_GXTiPnjA@mail.gmail.com' \
--to=bnagaev@gmail$(echo .)com \
--cc=bitcoindev@googlegroups.com \
--cc=conduition@proton$(echo .)me \
--cc=darosior@protonmail$(echo .)com \
--cc=lloyd.fourn@gmail$(echo .)com \
--cc=martin.habovstiak@gmail$(echo .)com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox