* [bitcoindev] Hashed keys are actually fully quantum secure
@ 2025-03-16 18:25 Martin Habovštiak
2025-03-16 18:50 ` 'Antoine Poinsot' via Bitcoin Development Mailing List
` (3 more replies)
0 siblings, 4 replies; 13+ messages in thread
From: Martin Habovštiak @ 2025-03-16 18:25 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 2581 bytes --]
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.
[-- Attachment #2: Type: text/html, Size: 3474 bytes --]
^ permalink raw reply [flat|nested] 13+ messages in thread* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-16 18:25 [bitcoindev] Hashed keys are actually fully quantum secure 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-16 19:03 ` Agustin Cruz ` (2 subsequent siblings) 3 siblings, 2 replies; 13+ messages in thread From: 'Antoine Poinsot' via Bitcoin Development Mailing List @ 2025-03-16 18:50 UTC (permalink / raw) To: Martin Habovštiak; +Cc: Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 3890 bytes --] > This way, the attacker would have to revert the chain to steal which is assumed impossible. Or just create its own "QR output"? If your threat model assumes an attacker can promptly recover the private key from the public key then once the user broadcasts his transaction spending both the old output and his own QR output the attacker could simply create his own QR output and RBF the honest transaction. 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. 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. [-- Attachment #2: Type: text/html, Size: 6242 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 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 1 sibling, 0 replies; 13+ messages in thread From: Erik Aronesty @ 2025-03-18 16:48 UTC (permalink / raw) To: Bitcoin Development Mailing List [-- Attachment #1.1: Type: text/plain, Size: 864 bytes --] If your threat model assumes an attacker can promptly recover the private key from the public key then once the user broadcasts his transaction spending both the old output and his own QR output the attacker could simply create his own QR output and RBF the honest transaction. correct. this doesn't provide protection. and any such rule about "spent along with" would be a hard fork. which is fine if qr ever matters (there's still not a lot of evidence that it will). -- 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/94689568-7ec5-4f19-b626-c9bdab57f5d8n%40googlegroups.com. [-- Attachment #1.2: Type: text/html, Size: 1369 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 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 1 sibling, 2 replies; 13+ messages in thread From: Lloyd Fournier @ 2025-03-24 0:24 UTC (permalink / raw) To: Antoine Poinsot; +Cc: Martin Habovštiak, Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 4700 bytes --] 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 > <https://groups.google.com/d/msgid/bitcoindev/XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com?utm_medium=email&utm_source=footer> > . > -- 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. [-- Attachment #2: Type: text/html, Size: 6759 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 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 1 sibling, 0 replies; 13+ messages in thread From: Martin Habovštiak @ 2025-03-30 20:16 UTC (permalink / raw) To: Lloyd Fournier; +Cc: Antoine Poinsot, Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 5187 bytes --] Indeed, that's what I meant. Even crazy long period like two weeks is still better than losing everything. I have also assumed RBF and related rules to stay similar. Still, a better scheme was proposed already that I was unaware of so far, thus I withdraw my proposal in favor of that one. Dňa po 24. 3. 2025, 1:25 Lloyd Fournier <lloyd.fourn@gmail•com> napísal(a): > > > 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 >> <https://groups.google.com/d/msgid/bitcoindev/XHIL8Z4i4hji8LhbJ0AiKQ4eago2evXwjTGUOqqyAye_2nM3QicDpHo6KkcznBAHPUrIWSLj_GuiTQ_97KPjxcOrG8pE0rgcXucK2-4txKE%3D%40protonmail.com?utm_medium=email&utm_source=footer> >> . >> > -- 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/CALkkCJb4aJgpgBxrSqSwmCVb3wdnaDJDo7j%2Bw_D7qC0wFpMOOw%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 7545 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 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 1 sibling, 1 reply; 13+ messages in thread From: 'conduition' via Bitcoin Development Mailing List @ 2025-05-25 18:22 UTC (permalink / raw) To: Lloyd Fournier Cc: Antoine Poinsot, Martin Habovštiak, Bitcoin Development Mailing List [-- Attachment #1.1: Type: text/plain, Size: 7242 bytes --] 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. [-- Attachment #1.2: publickey - conduition@proton.me - 0x474891AD.asc --] [-- Type: application/pgp-keys, Size: 649 bytes --] [-- Attachment #2: OpenPGP digital signature --] [-- Type: application/pgp-signature, Size: 343 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-05-25 18:22 ` 'conduition' via Bitcoin Development Mailing List @ 2025-05-26 10:03 ` Nagaev Boris 0 siblings, 0 replies; 13+ messages in thread From: Nagaev Boris @ 2025-05-26 10:03 UTC (permalink / raw) To: conduition Cc: Lloyd Fournier, Antoine Poinsot, Martin Habovštiak, Bitcoin Development Mailing List 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. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-16 18:25 [bitcoindev] Hashed keys are actually fully quantum secure Martin Habovštiak 2025-03-16 18:50 ` 'Antoine Poinsot' via Bitcoin Development Mailing List @ 2025-03-16 19:03 ` Agustin Cruz 2025-03-16 20:52 ` Martin Habovštiak 2025-03-17 10:44 ` Lloyd Fournier 2025-03-30 15:41 ` David A. Harding 3 siblings, 1 reply; 13+ messages in thread From: Agustin Cruz @ 2025-03-16 19:03 UTC (permalink / raw) To: Martin Habovštiak; +Cc: Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 4833 bytes --] Hi Martin, Your approach of using a committed QR signature to “anchor” the spending of hashed keys is intriguing. If I understand correctly, the idea is: - A user commits to a QR signature in a first transaction (Tx1), proving ownership of the QR private key without exposing vulnerable data. - Later, they spend both the old P2PKH output and the QR output together (Tx2), revealing the QR signature, with rules ensuring the old output can’t be spent independently. - This forces an attacker to either forge a QR signature (infeasible with a quantum-resistant scheme) or rewind the chain past Tx1’s confirmation (infeasible with sufficient depth). This seems to provide a solid defense against quantum theft, assuming the QR scheme holds up and the blockchain remains secure. I also like how it mitigates the “theft vs. freeze” dilemma. Temporary freezing is indeed less catastrophic than permanent loss, and avoiding reputational damage is crucial. To better understand how this would work, I have two questions: 1. How would the QR signature commitment be encoded and verified in the script?. Would this require new opcodes or script functionality to check the commitment when spending? 2. How would you enforce that the old P2PKH output can only be spent with the QR output? Would this need a soft fork, and if so, what consensus changes would be required? Regards, Agustín El dom, 16 de mar de 2025, 3:31 p. m., Martin Habovštiak < martin.habovstiak@gmail•com> escribió: > 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 > <https://groups.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CAJDmzYw-Z2nB3BvSnuCT2OF%2Bahd-kbVrYauM_cZgmDytPYVfpA%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 6164 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-16 19:03 ` Agustin Cruz @ 2025-03-16 20:52 ` Martin Habovštiak 0 siblings, 0 replies; 13+ messages in thread From: Martin Habovštiak @ 2025-03-16 20:52 UTC (permalink / raw) To: Agustin Cruz; +Cc: Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 6183 bytes --] Antoine, "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." yes, this is what I meant but also the QR output must contain the commitment. This rule makes it not "a race". The attacker cannot make the commitment before knowing the private key and cannot reverse deep chain. Augustin, you understand it correctly. Sadly, the dilemma is only mitigated for hashed keys, not revealed ones. 1. we would presumably bump segwit version, so we can do whatever we like. I assume it'd be something similar to today's Annex but there are likely more ways to do it with their pros and cons. I don't think these details matter much today. But it's certainly possible. 2. of course, soft fork would be required but it will be anyway to deploy a QR signing algo. And I don't think anything saving coins from certain loss will be contentious. :) The changes would need to identify inputs using secp256k1 verification and look up the commitments in the other inputs. Also they'd need to check how deep the spent inputs are. Dňa ne 16. 3. 2025, 20:03 Agustin Cruz <agustin.cruz@gmail•com> napísal(a): > Hi Martin, > > Your approach of using a committed QR signature to “anchor” the spending > of hashed keys is intriguing. If I understand correctly, the idea is: > - A user commits to a QR signature in a first transaction (Tx1), proving > ownership of the QR private key without exposing vulnerable data. > - Later, they spend both the old P2PKH output and the QR output together > (Tx2), revealing the QR signature, with rules ensuring the old output can’t > be spent independently. > - This forces an attacker to either forge a QR signature (infeasible with > a quantum-resistant scheme) or rewind the chain past Tx1’s confirmation > (infeasible with sufficient depth). > > This seems to provide a solid defense against quantum theft, assuming the > QR scheme holds up and the blockchain remains secure. I also like how it > mitigates the “theft vs. freeze” dilemma. Temporary freezing is indeed less > catastrophic than permanent loss, and avoiding reputational damage is > crucial. > > To better understand how this would work, I have two questions: > > 1. How would the QR signature commitment be encoded and verified in the > script?. Would this require new opcodes or script functionality to check > the commitment when spending? > > 2. How would you enforce that the old P2PKH output can only be spent with > the QR output? Would this need a soft fork, and if so, what consensus > changes would be required? > > Regards, > Agustín > > El dom, 16 de mar de 2025, 3:31 p. m., Martin Habovštiak < > martin.habovstiak@gmail•com> escribió: > >> 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 >> <https://groups.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> > -- 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/CALkkCJZ6cT%3D9kq%2B%3DmSmkgFY%2B6x3zxTwo196crOOxTkFWq8w3vw%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 7903 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-16 18:25 [bitcoindev] Hashed keys are actually fully quantum secure Martin Habovštiak 2025-03-16 18:50 ` 'Antoine Poinsot' via Bitcoin Development Mailing List 2025-03-16 19:03 ` Agustin Cruz @ 2025-03-17 10:44 ` Lloyd Fournier 2025-03-17 11:07 ` Martin Habovštiak 2025-03-30 15:41 ` David A. Harding 3 siblings, 1 reply; 13+ messages in thread From: Lloyd Fournier @ 2025-03-17 10:44 UTC (permalink / raw) To: Martin Habovštiak; +Cc: Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 5695 bytes --] 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š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 > <https://groups.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > -- 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/CAH5Bsr3Yx1n22svy7QCTkT_BdzxLUqSmaR6Ji%2Bv7Zf4Pph9S7w%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 6942 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-17 10:44 ` Lloyd Fournier @ 2025-03-17 11:07 ` Martin Habovštiak 0 siblings, 0 replies; 13+ messages in thread From: Martin Habovštiak @ 2025-03-17 11:07 UTC (permalink / raw) To: Lloyd Fournier; +Cc: Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 6942 bytes --] Oh, great point that while the hashing in Taproot disallows spending when null tweak is used, it's still usable to produce a proof similar to what I suggested. Also very interesting point about address reuse being "fine" with taproot. I believe the QR signature scheme in tapleaf was already suggested but that has the problem that the scheme needs to be specified in advance. IIUC it's not currently clear which even is reasonable. My idea gives us more time to figure that out. However, I do not think that Taproot is generally safer than p2*pkh. Comparing to millions lost coins is not valid, since those at worst decrease the price of bitcoin but economically wouldn't set it to literal zero, thus the value of one's coins just decreases, while getting stolen from means the value of one's coins goes to literal zero. The difference wrt safety thus relies on how well one is able to avoid address reuse. Some people can avoid it completely, some can't. The social aspect is indeed messy. Dňa po 17. 3. 2025, 11:44 Lloyd Fournier <lloyd.fourn@gmail•com> napísal(a): > 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š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 >> <https://groups.google.com/d/msgid/bitcoindev/CALkkCJY%3Ddv6cZ_HoUNQybF4-byGOjME3Jt2DRr20yZqMmdJUnQ%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> > -- 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/CALkkCJZ3TBEfRYBHVv_NON18mqbsQixgUEtgGThau4D%3DW6gdGg%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 8573 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-16 18:25 [bitcoindev] Hashed keys are actually fully quantum secure Martin Habovštiak ` (2 preceding siblings ...) 2025-03-17 10:44 ` Lloyd Fournier @ 2025-03-30 15:41 ` David A. Harding 2025-03-30 20:11 ` Martin Habovštiak 3 siblings, 1 reply; 13+ messages in thread From: David A. Harding @ 2025-03-30 15:41 UTC (permalink / raw) To: Martin Habovštiak; +Cc: Bitcoin Development Mailing List On 2025-03-16 08:25, Martin Habovštiak wrote: > It is possible to implement fully secure recovery if we forbid > spending of hashed keys unless done through the following scheme: Hi Martin, How does this differ from Tim Ruffing's version[1] of Guy Fawkes signatures?[2][3] Thanks, -Dave [1] https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/ (but see also the whole thread and the links in it) [2] https://www.cl.cam.ac.uk/archive/rja14/Papers/fawkes.pdf [3] Amusing exploration of a blockchain cryptocurrency without signatures by Joseph Bonneau and Andrew Miller: https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf (never saw it before, but it came up in my search results for a Guy Fawkes signatures reference). -- 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/bb54cf2c858843e8a4a9029ac683b3ed%40dtrt.org. ^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [bitcoindev] Hashed keys are actually fully quantum secure 2025-03-30 15:41 ` David A. Harding @ 2025-03-30 20:11 ` Martin Habovštiak 0 siblings, 0 replies; 13+ messages in thread From: Martin Habovštiak @ 2025-03-30 20:11 UTC (permalink / raw) To: David A. Harding; +Cc: Bitcoin Development Mailing List [-- Attachment #1: Type: text/plain, Size: 2632 bytes --] Hi, conceptually they are the same idea, I didn't see that conversation before. Howerver, in that conversation there seems to be a better developed scheme that is more secure as far as I can tell. I have just assumed that the chain cannot be censored profitably if the number of blocks to wait for is high enough (why: the miners are giving up fees by not including the transaction and the attacker would have to split the reward between all miners but the honest user only needs to outbid the attacker once) That other idea seems to work even if the chain is censored for arbitrary number of blocks. In the meantime I was also thinking of a scheme that allows you to commit early and then wait for a any time you want but with the ability to detect that someone else is trying to spend it, so that you can act quickly. In some sense it was more similar but still not that good. The proposed scheme with unique decommitment is better and should be implemented instead of my idea. Anyway, I believe even my weaker idea is still good enough to make my point given how hard it is to censor a transaction. My point wasn't saying that my specific implementation is the best but saying we can postpone the decision to implement a QR scheme to much later than what some people might think. Have a nice day! Martin Dňa ne 30. 3. 2025, 17:41 David A. Harding <dave@dtrt•org> napísal(a): > On 2025-03-16 08:25, Martin Habovštiak wrote: > > It is possible to implement fully secure recovery if we forbid > > spending of hashed keys unless done through the following scheme: > > Hi Martin, > > How does this differ from Tim Ruffing's version[1] of Guy Fawkes > signatures?[2][3] > > Thanks, -Dave > > [1] > > https://gnusha.org/pi/bitcoindev/1518710367.3550.111.camel@mmci.uni-saarland.de/ > (but see also the whole thread and the links in it) > > [2] https://www.cl.cam.ac.uk/archive/rja14/Papers/fawkes.pdf > > [3] Amusing exploration of a blockchain cryptocurrency without > signatures by Joseph Bonneau and Andrew Miller: > https://jbonneau.com/doc/BM14-SPW-fawkescoin.pdf (never saw it before, > but it came up in my search results for a Guy Fawkes signatures > reference). > -- 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/CALkkCJYaLMciqYxNFa6qT6-WCsSD3P9pP7boYs%3Dk0htAdnAR6g%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 3921 bytes --] ^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2025-05-26 15:43 UTC | newest] Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2025-03-16 18:25 [bitcoindev] Hashed keys are actually fully quantum secure 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 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
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox