[bitcoin-dev] PSA: Taproot loss of quantum protections

[bitcoin-dev] PSA: Taproot loss of quantum protections

[Luke Dashjr]

I do not personally see this as a reason to NACK Taproot, but it has become 
clear to me over the past week or so that many others are unaware of this 
tradeoff, so I am sharing it here to ensure the wider community is aware of 
it and can make their own judgements.

Mark Friedenbach explains on his blog:
    https://freicoin.substack.com/p/why-im-against-taproot

In short, Taproot loses an important safety protection against quantum.
Note that in all circumstances, Bitcoin is endangered when QC becomes a 
reality, but pre-Taproot, it is possible for the network to "pause" while a 
full quantum-safe fix is developed, and then resume transacting. With Taproot 
as-is, it could very well become an unrecoverable situation if QC go online 
prior to having a full quantum-safe solution.

Also, what I didn't know myself until today, is that we do not actually gain 
anything from this: the features proposed to make use of the raw keys being 
public prior to spending can be implemented with hashed keys as well.
It would use significantly more CPU time and bandwidth (between private 
parties, not on-chain), but there should be no shortage of that for anyone 
running a full node (indeed, CPU time is freed up by Taproot!); at worst, it 
would create an incentive for more people to use their own full node, which 
is a good thing!

Despite this, I still don't think it's a reason to NACK Taproot: it should be 
fairly trivial to add a hash on top in an additional softfork and fix this.

In addition to the points made by Mark, I also want to add two more, in 
response to Pieter's "you can't claim much security if 37% of the supply is 
at risk" argument. This argument is based in part on the fact that many 
people reuse Bitcoin invoice addresses.

First, so long as we have hash-based addresses as a best practice, we can 
continue to shrink the percentage of bitcoins affected through social efforts 
discouraging address use. If the standard loses the hash, the situation 
cannot be improved, and will indeed only get worse.

Second, when/if quantum does compromise these coins, so long as they are 
neglected or abandoned/lost coins (inherent in the current model), it can be 
seen as equivalent to Bitcoin mining. At the end of the day, 37% of supply 
minable by QCs is really no different than 37% minable by ASICs. (We've seen 
far higher %s available for mining obviously.)

To conclude, I recommend anyone using Bitcoin to read Mark's article, my 
thoughts, and any other arguments on the topic; decide if this is a concern 
to you, and make your own post(s) accordingly. Mark has conceded the argument 
(AFAIK he doesn't have an interest in bitcoins anyway), and I do not consider 
it a showstopper - so if anyone else out there does, please make yourself 
known ASAP since Taproot has already moved on to the activation phase and it 
is likely software will be released within the next month or two as things 
stand.

Luke

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Matt Corallo]

There have been many threads on this before, I'm not sure anything new has been brought up here.

Matt

On 3/15/21 17:48, Luke Dashjr via bitcoin-dev wrote:
> I do not personally see this as a reason to NACK Taproot, but it has become
> clear to me over the past week or so that many others are unaware of this
> tradeoff, so I am sharing it here to ensure the wider community is aware of
> it and can make their own judgements.

Note that this is most definitely *not* news to this list, eg, Anthony brought it up in "Schnorr and taproot (etc) 
upgrade" and there was a whole thread on it in "Taproot: Privacy preserving switchable scripting". This issue has been 
beaten to death, I'm not sure why we need to keep hitting the poor horse corpse.

> 
> In short, Taproot loses an important safety protection against quantum.
> Note that in all circumstances, Bitcoin is endangered when QC becomes a
> reality, but pre-Taproot, it is possible for the network to "pause" while a
> full quantum-safe fix is developed, and then resume transacting. With Taproot
> as-is, it could very well become an unrecoverable situation if QC go online
> prior to having a full quantum-safe solution.

This has been discussed ad nauseam, and it all seems to fall apart once its noted just how much Bitcoin could be stolen 
by any QC-wielding attacker due to address reuse. Ultimately, no "pause" can solve this issue, and, if we learned about 
a QC attacker overnight (instead of slowly over time), there isn't anything that a non-Taproot Bitcoin could do that a 
Taproot Bitcoin couldn't.

> Also, what I didn't know myself until today, is that we do not actually gain
> anything from this: the features proposed to make use of the raw keys being
> public prior to spending can be implemented with hashed keys as well.
> It would use significantly more CPU time and bandwidth (between private
> parties, not on-chain), but there should be no shortage of that for anyone
> running a full node (indeed, CPU time is freed up by Taproot!); at worst, it
> would create an incentive for more people to use their own full node, which
> is a good thing!

This is untrue. The storage space required for Taproot transactions is materially reduced by avoiding the hash indirection.

> Despite this, I still don't think it's a reason to NACK Taproot: it should be
> fairly trivial to add a hash on top in an additional softfork and fix this.

For the reason stated above, i think such a fork is unlikely.

> In addition to the points made by Mark, I also want to add two more, in
> response to Pieter's "you can't claim much security if 37% of the supply is
> at risk" argument. This argument is based in part on the fact that many
> people reuse Bitcoin invoice addresses.
> 
> First, so long as we have hash-based addresses as a best practice, we can
> continue to shrink the percentage of bitcoins affected through social efforts
> discouraging address use. If the standard loses the hash, the situation
> cannot be improved, and will indeed only get worse.

I truly wish this were the case, but we've been beating that drum for at least nine years and still haven't solved it. 
Worse, there's a lot of old coins that are unlikely to move any time soon that are exposed whether we like it or not.

> Second, when/if quantum does compromise these coins, so long as they are
> neglected or abandoned/lost coins (inherent in the current model), it can be
> seen as equivalent to Bitcoin mining. At the end of the day, 37% of supply
> minable by QCs is really no different than 37% minable by ASICs. (We've seen
> far higher %s available for mining obviously.)

Except its not? One entity would be able to steal that entire block of supply rather quickly (presumably over the course 
of a few days, at maximum), instead of a slow process with significant upfront real-world cost in the form of electricity.

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Robert Spigler]

I agree with Matt.

The naked pubkey is required for some of the benefits being implemented (snicker coinjoins).

Even with pubkey hashes, bitcoin could still be stolen because the pubkey is published on spend.  Regardless, QC needs to be fixed later on (decades), and shouldn't be a reason to NACK taproot.


Personal Fingerprint:  BF0D 3C08 A439 5AC6 11C1 5395 B70B 4A77 F850 548F


‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
On Monday, March 15, 2021 6:05 PM, Matt Corallo via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> There have been many threads on this before, I'm not sure anything new has been brought up here.
>
> Matt
>
> On 3/15/21 17:48, Luke Dashjr via bitcoin-dev wrote:
>
> > I do not personally see this as a reason to NACK Taproot, but it has become
> > clear to me over the past week or so that many others are unaware of this
> > tradeoff, so I am sharing it here to ensure the wider community is aware of
> > it and can make their own judgements.
>
> Note that this is most definitelynot news to this list, eg, Anthony brought it up in "Schnorr and taproot (etc)
> upgrade" and there was a whole thread on it in "Taproot: Privacy preserving switchable scripting". This issue has been
> beaten to death, I'm not sure why we need to keep hitting the poor horse corpse.
>
> > In short, Taproot loses an important safety protection against quantum.
> > Note that in all circumstances, Bitcoin is endangered when QC becomes a
> > reality, but pre-Taproot, it is possible for the network to "pause" while a
> > full quantum-safe fix is developed, and then resume transacting. With Taproot
> > as-is, it could very well become an unrecoverable situation if QC go online
> > prior to having a full quantum-safe solution.
>
> This has been discussed ad nauseam, and it all seems to fall apart once its noted just how much Bitcoin could be stolen
> by any QC-wielding attacker due to address reuse. Ultimately, no "pause" can solve this issue, and, if we learned about
> a QC attacker overnight (instead of slowly over time), there isn't anything that a non-Taproot Bitcoin could do that a
> Taproot Bitcoin couldn't.
>
> > Also, what I didn't know myself until today, is that we do not actually gain
> > anything from this: the features proposed to make use of the raw keys being
> > public prior to spending can be implemented with hashed keys as well.
> > It would use significantly more CPU time and bandwidth (between private
> > parties, not on-chain), but there should be no shortage of that for anyone
> > running a full node (indeed, CPU time is freed up by Taproot!); at worst, it
> > would create an incentive for more people to use their own full node, which
> > is a good thing!
>
> This is untrue. The storage space required for Taproot transactions is materially reduced by avoiding the hash indirection.
>
> > Despite this, I still don't think it's a reason to NACK Taproot: it should be
> > fairly trivial to add a hash on top in an additional softfork and fix this.
>
> For the reason stated above, i think such a fork is unlikely.
>
> > In addition to the points made by Mark, I also want to add two more, in
> > response to Pieter's "you can't claim much security if 37% of the supply is
> > at risk" argument. This argument is based in part on the fact that many
> > people reuse Bitcoin invoice addresses.
> > First, so long as we have hash-based addresses as a best practice, we can
> > continue to shrink the percentage of bitcoins affected through social efforts
> > discouraging address use. If the standard loses the hash, the situation
> > cannot be improved, and will indeed only get worse.
>
> I truly wish this were the case, but we've been beating that drum for at least nine years and still haven't solved it.
> Worse, there's a lot of old coins that are unlikely to move any time soon that are exposed whether we like it or not.
>
> > Second, when/if quantum does compromise these coins, so long as they are
> > neglected or abandoned/lost coins (inherent in the current model), it can be
> > seen as equivalent to Bitcoin mining. At the end of the day, 37% of supply
> > minable by QCs is really no different than 37% minable by ASICs. (We've seen
> > far higher %s available for mining obviously.)
>
> Except its not? One entity would be able to steal that entire block of supply rather quickly (presumably over the course
> of a few days, at maximum), instead of a slow process with significant upfront real-world cost in the form of electricity.
>
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 4961 bytes --]

I think Luke is pointing out that with the Signature and the Message you
should be able to recover the key.

if your address is H(P) and the message is H(H(P) || txn), then the you can
use the public H(P) and the signature to recover the PK and verify that
H(P) == P (I think you then don't even have to check the signature after
doing that).

Therefore there is no storage benefit.

For the script path case, you might have to pay a little bit extra though
as you'd have to reveal P I think? But perhaps that can be avoided another
way...
--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>


On Mon, Mar 15, 2021 at 3:06 PM Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> There have been many threads on this before, I'm not sure anything new has
> been brought up here.
>
> Matt
>
> On 3/15/21 17:48, Luke Dashjr via bitcoin-dev wrote:
> > I do not personally see this as a reason to NACK Taproot, but it has
> become
> > clear to me over the past week or so that many others are unaware of this
> > tradeoff, so I am sharing it here to ensure the wider community is aware
> of
> > it and can make their own judgements.
>
> Note that this is most definitely *not* news to this list, eg, Anthony
> brought it up in "Schnorr and taproot (etc)
> upgrade" and there was a whole thread on it in "Taproot: Privacy
> preserving switchable scripting". This issue has been
> beaten to death, I'm not sure why we need to keep hitting the poor horse
> corpse.
>
> >
> > In short, Taproot loses an important safety protection against quantum.
> > Note that in all circumstances, Bitcoin is endangered when QC becomes a
> > reality, but pre-Taproot, it is possible for the network to "pause"
> while a
> > full quantum-safe fix is developed, and then resume transacting. With
> Taproot
> > as-is, it could very well become an unrecoverable situation if QC go
> online
> > prior to having a full quantum-safe solution.
>
> This has been discussed ad nauseam, and it all seems to fall apart once
> its noted just how much Bitcoin could be stolen
> by any QC-wielding attacker due to address reuse. Ultimately, no "pause"
> can solve this issue, and, if we learned about
> a QC attacker overnight (instead of slowly over time), there isn't
> anything that a non-Taproot Bitcoin could do that a
> Taproot Bitcoin couldn't.
>
> > Also, what I didn't know myself until today, is that we do not actually
> gain
> > anything from this: the features proposed to make use of the raw keys
> being
> > public prior to spending can be implemented with hashed keys as well.
> > It would use significantly more CPU time and bandwidth (between private
> > parties, not on-chain), but there should be no shortage of that for
> anyone
> > running a full node (indeed, CPU time is freed up by Taproot!); at
> worst, it
> > would create an incentive for more people to use their own full node,
> which
> > is a good thing!
>
> This is untrue. The storage space required for Taproot transactions is
> materially reduced by avoiding the hash indirection.
>
> > Despite this, I still don't think it's a reason to NACK Taproot: it
> should be
> > fairly trivial to add a hash on top in an additional softfork and fix
> this.
>
> For the reason stated above, i think such a fork is unlikely.
>
> > In addition to the points made by Mark, I also want to add two more, in
> > response to Pieter's "you can't claim much security if 37% of the supply
> is
> > at risk" argument. This argument is based in part on the fact that many
> > people reuse Bitcoin invoice addresses.
> >
> > First, so long as we have hash-based addresses as a best practice, we can
> > continue to shrink the percentage of bitcoins affected through social
> efforts
> > discouraging address use. If the standard loses the hash, the situation
> > cannot be improved, and will indeed only get worse.
>
> I truly wish this were the case, but we've been beating that drum for at
> least nine years and still haven't solved it.
> Worse, there's a lot of old coins that are unlikely to move any time soon
> that are exposed whether we like it or not.
>
> > Second, when/if quantum does compromise these coins, so long as they are
> > neglected or abandoned/lost coins (inherent in the current model), it
> can be
> > seen as equivalent to Bitcoin mining. At the end of the day, 37% of
> supply
> > minable by QCs is really no different than 37% minable by ASICs. (We've
> seen
> > far higher %s available for mining obviously.)
>
> Except its not? One entity would be able to steal that entire block of
> supply rather quickly (presumably over the course
> of a few days, at maximum), instead of a slow process with significant
> upfront real-world cost in the form of electricity.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 6790 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Matt Corallo]

Right, you can avoid the storage cost at the cost of significantly higher CPU usage, plus lack of ability to 
batch-validate. As Robert pointed out in a neighboring mail, it also reduces ability to do other, fancier, protocols 
using the fact that public keys are now a public part of a script_pubkey.

Overall, the tradeoffs here seem ludicrous, given that any QC issues in Bitcoin need to be solved in another way, and 
can't practically be solved by just relying on the existing hash indirection.

Matt

On 3/15/21 18:40, Jeremy wrote:
> I think Luke is pointing out that with the Signature and the Message you should be able to recover the key.
> 
> if your address is H(P) and the message is H(H(P) || txn), then the you can use the public H(P) and the signature to 
> recover the PK and verify that H(P) == P (I think you then don't even have to check the signature after doing that).
> 
> Therefore there is no storage benefit.
> 
> For the script path case, you might have to pay a little bit extra though as you'd have to reveal P I think? But perhaps 
> that can be avoided another way...
> --
> @JeremyRubin <https://twitter.com/JeremyRubin><https://twitter.com/JeremyRubin>
> 
> 
> On Mon, Mar 15, 2021 at 3:06 PM Matt Corallo via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org 
> <mailto:bitcoin-dev@lists.linuxfoundation.org>> wrote:
> 
>     There have been many threads on this before, I'm not sure anything new has been brought up here.
> 
>     Matt
> 
>     On 3/15/21 17:48, Luke Dashjr via bitcoin-dev wrote:
>      > I do not personally see this as a reason to NACK Taproot, but it has become
>      > clear to me over the past week or so that many others are unaware of this
>      > tradeoff, so I am sharing it here to ensure the wider community is aware of
>      > it and can make their own judgements.
> 
>     Note that this is most definitely *not* news to this list, eg, Anthony brought it up in "Schnorr and taproot (etc)
>     upgrade" and there was a whole thread on it in "Taproot: Privacy preserving switchable scripting". This issue has been
>     beaten to death, I'm not sure why we need to keep hitting the poor horse corpse.
> 
>      >
>      > In short, Taproot loses an important safety protection against quantum.
>      > Note that in all circumstances, Bitcoin is endangered when QC becomes a
>      > reality, but pre-Taproot, it is possible for the network to "pause" while a
>      > full quantum-safe fix is developed, and then resume transacting. With Taproot
>      > as-is, it could very well become an unrecoverable situation if QC go online
>      > prior to having a full quantum-safe solution.
> 
>     This has been discussed ad nauseam, and it all seems to fall apart once its noted just how much Bitcoin could be stolen
>     by any QC-wielding attacker due to address reuse. Ultimately, no "pause" can solve this issue, and, if we learned about
>     a QC attacker overnight (instead of slowly over time), there isn't anything that a non-Taproot Bitcoin could do that a
>     Taproot Bitcoin couldn't.
> 
>      > Also, what I didn't know myself until today, is that we do not actually gain
>      > anything from this: the features proposed to make use of the raw keys being
>      > public prior to spending can be implemented with hashed keys as well.
>      > It would use significantly more CPU time and bandwidth (between private
>      > parties, not on-chain), but there should be no shortage of that for anyone
>      > running a full node (indeed, CPU time is freed up by Taproot!); at worst, it
>      > would create an incentive for more people to use their own full node, which
>      > is a good thing!
> 
>     This is untrue. The storage space required for Taproot transactions is materially reduced by avoiding the hash
>     indirection.
> 
>      > Despite this, I still don't think it's a reason to NACK Taproot: it should be
>      > fairly trivial to add a hash on top in an additional softfork and fix this.
> 
>     For the reason stated above, i think such a fork is unlikely.
> 
>      > In addition to the points made by Mark, I also want to add two more, in
>      > response to Pieter's "you can't claim much security if 37% of the supply is
>      > at risk" argument. This argument is based in part on the fact that many
>      > people reuse Bitcoin invoice addresses.
>      >
>      > First, so long as we have hash-based addresses as a best practice, we can
>      > continue to shrink the percentage of bitcoins affected through social efforts
>      > discouraging address use. If the standard loses the hash, the situation
>      > cannot be improved, and will indeed only get worse.
> 
>     I truly wish this were the case, but we've been beating that drum for at least nine years and still haven't solved it.
>     Worse, there's a lot of old coins that are unlikely to move any time soon that are exposed whether we like it or not.
> 
>      > Second, when/if quantum does compromise these coins, so long as they are
>      > neglected or abandoned/lost coins (inherent in the current model), it can be
>      > seen as equivalent to Bitcoin mining. At the end of the day, 37% of supply
>      > minable by QCs is really no different than 37% minable by ASICs. (We've seen
>      > far higher %s available for mining obviously.)
> 
>     Except its not? One entity would be able to steal that entire block of supply rather quickly (presumably over the
>     course
>     of a few days, at maximum), instead of a slow process with significant upfront real-world cost in the form of
>     electricity.
>     _______________________________________________
>     bitcoin-dev mailing list
>     bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-dev@lists.linuxfoundation.org>
>     https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>     <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>
> 

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Karl-Johan Alm]

On Tue, 16 Mar 2021 at 07:48, Matt Corallo via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> Overall, the tradeoffs here seem ludicrous, given that any QC issues in Bitcoin need to be solved in another way, and
> can't practically be solved by just relying on the existing hash indirection.

The important distinction here is that, with hashes, an attacker has
to race against the spending transaction confirming, whereas with
naked pubkeys, the attacker doesn't have to wait for a spend to occur,
drastically increasing the available time to attack.

It may initially take months to break a single key. In such a
scenario, anyone with a hashed pubkey would be completely safe* (even
at spend time), until that speeds up significantly, while Super Secure
Exchange X with an ultra-cold 38-of-38 multisig setup using Taproot
would have a timer ticking, since the attacker need only find a single
privkey like with any old P2PK output.

(* assuming no address reuse)

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Matt Corallo]

Right, totally. There was substantial debate on the likelihood of such a QC existing (ie a slow one) on the original 
thread several years ago, but ignoring that, my broader point was about the address reuse issue. Given that, there's 
just not much we can do with the existing hash-indirection.

Matt

On 3/15/21 19:01, Karl-Johan Alm via bitcoin-dev wrote:
> On Tue, 16 Mar 2021 at 07:48, Matt Corallo via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
>>
>> Overall, the tradeoffs here seem ludicrous, given that any QC issues in Bitcoin need to be solved in another way, and
>> can't practically be solved by just relying on the existing hash indirection.
> 
> The important distinction here is that, with hashes, an attacker has
> to race against the spending transaction confirming, whereas with
> naked pubkeys, the attacker doesn't have to wait for a spend to occur,
> drastically increasing the available time to attack.
> 
> It may initially take months to break a single key. In such a
> scenario, anyone with a hashed pubkey would be completely safe* (even
> at spend time), until that speeds up significantly, while Super Secure
> Exchange X with an ultra-cold 38-of-38 multisig setup using Taproot
> would have a timer ticking, since the attacker need only find a single
> privkey like with any old P2PK output.
> 
> (* assuming no address reuse)
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 4254 bytes --]

On Tue, 16 Mar 2021 at 09:05, Matt Corallo via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> There have been many threads on this before, I'm not sure anything new has
> been brought up here.
>
> Matt
>
> On 3/15/21 17:48, Luke Dashjr via bitcoin-dev wrote:
> > I do not personally see this as a reason to NACK Taproot, but it has
> become
> > clear to me over the past week or so that many others are unaware of this
> > tradeoff, so I am sharing it here to ensure the wider community is aware
> of
> > it and can make their own judgements.
>
> Note that this is most definitely *not* news to this list, eg, Anthony
> brought it up in "Schnorr and taproot (etc)
> upgrade" and there was a whole thread on it in "Taproot: Privacy
> preserving switchable scripting". This issue has been
> beaten to death, I'm not sure why we need to keep hitting the poor horse
> corpse.
>
>
I read through this thread just now. The QC discussion starts roughly here:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015620.html

My own (very possibly wrong) interpretation of the situation is:

1. Current addresses are very vulnerable to QC and would require hardfork
to fix (and not fix particularly well).
2. Once a QC resistant spending procedure has been developed it could be
added as a backup spending policy as a new tapleaf version (wallets would
have to opt into it).
3. If QC does get to the point where it can break ECC then we can disable
key-path spends via softfork
4. If everyone has moved their coins to Taproot addresses with a QC
resistant tapleaf backup then we're ok.
5. Since the above is almost certainly not going to happen we can simply
congratulate the new QC owners on the Bitcoin they take from old addresses
(specter of QC encourages moving to taproot which could be thought of as a
good thing).
6. Otherwise we have to hard fork to stop old addresses being spent without
a quantum resistant ZKP (oof!).
7. Once we know what we're up against a new quantum resistant segwit
version can be introduced (if it hasn't already).
8. If QC develop far enough to degrade SHA256 sufficiently (ECC probably
breaks first) then that's a whole other ball game since it affects PoW and
txids and so on and will likely require a hard fork.

The ordering of the above events is not predictable. IMO Mark's post is on
the wildly optimistic side of projected rate of progress from my limited
understanding. Either way it is strictly better to enter a QC world with
Taproot enabled and most people are using it so we can introduce QC
resistant backup spend paths without hardforks before they become
practical. Depending on what happens they may not be needed but it's good
to have the option.

On Tue, 16 Mar 2021 at 10:11, Karl-Johan Alm via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Tue, 16 Mar 2021 at 07:48, Matt Corallo via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > Overall, the tradeoffs here seem ludicrous, given that any QC issues in
> Bitcoin need to be solved in another way, and
> > can't practically be solved by just relying on the existing hash
> indirection.
>
> The important distinction here is that, with hashes, an attacker has
> to race against the spending transaction confirming, whereas with
> naked pubkeys, the attacker doesn't have to wait for a spend to occur,
> drastically increasing the available time to attack.
>
>
First note that I am enthusiastically ignorant of QC technology so please
take the following with a bowl of salt.
The premise of Mark's post is that QC progress is currently exponential
(debatable) and will continue to be (unknowable) so "months" will turn into
days and into minutes in short time period. Since QC progress is
exponential and the speedup that ECC quantum algorithms offer is
exponential you're not dealing with the typical "Moore's law" progress in
terms of time to solve a particular problem; It's like exponential
exponential (math person help me now). You could easily go from ten
thousand years to break ECC to a few seconds within a year with that rate
of progress so I don't think "slow quantum" is an adversary worth
protecting against. I would love to know if I am wrong on this point.

Cheers,

LL

[-- Attachment #2: Type: text/html, Size: 5661 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Anthony Towns]

On Tue, Mar 16, 2021 at 08:01:47AM +0900, Karl-Johan Alm via bitcoin-dev wrote:
> It may initially take months to break a single key. 

From what I understand, the constraint on using quantum techniques to
break an ECC key is on the number of bits you can entangle and how long
you can keep them coherent -- but those are both essentially thresholds:
you can't use two quantum computers that support a lower number of bits
when you need a higher number, and you can't reuse the state you reached
after you collapsed halfway through to make the next run shorter.

I think that means having a break take a longer time means maintaining
the quantum state for longer, which is *harder* than having it happen
quicker...

So I think the only way you get it taking substantial amounts of time to
break a key is if your quantum attack works quickly but very unreliably:
maybe it takes a minute to reset, and every attempt only has probability
p of succeeding (ie, random probability of managing to maintain the
quantum state until completion of the dlog algorithm), so over t minutes
you end up with probability 1-(1-p)^t of success.

For 50% odds after 1 month with 1 minute per attempt, you'd need a 0.0016%
chance per attempt, for 50% odds after 1 day, you'd need 0.048% chance per
attempt. But those odds assume you've only got one QC making the attempts
-- if you've got 30, you can make a month's worth of attempts in a day;
if you scale up to 720, you can make a month's worth of attempts in an
hour, ie once you've got one, it's a fairly straightforward engineering
challenge at that point.

So a "slow" attack simply doesn't seem likely to me. YMMV, obviously.

Cheers,
aj

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[ZmnSCPxj]

Good morning aj,

> On Tue, Mar 16, 2021 at 08:01:47AM +0900, Karl-Johan Alm via bitcoin-dev wrote:
>
> > It may initially take months to break a single key.
>
> From what I understand, the constraint on using quantum techniques to
> break an ECC key is on the number of bits you can entangle and how long
> you can keep them coherent -- but those are both essentially thresholds:
> you can't use two quantum computers that support a lower number of bits
> when you need a higher number, and you can't reuse the state you reached
> after you collapsed halfway through to make the next run shorter.
>
> I think that means having a break take a longer time means maintaining
> the quantum state for longer, which is harder than having it happen
> quicker...
>
> So I think the only way you get it taking substantial amounts of time to
> break a key is if your quantum attack works quickly but very unreliably:
> maybe it takes a minute to reset, and every attempt only has probability
> p of succeeding (ie, random probability of managing to maintain the
> quantum state until completion of the dlog algorithm), so over t minutes
> you end up with probability 1-(1-p)^t of success.
>
> For 50% odds after 1 month with 1 minute per attempt, you'd need a 0.0016%
> chance per attempt, for 50% odds after 1 day, you'd need 0.048% chance per
> attempt. But those odds assume you've only got one QC making the attempts
> -- if you've got 30, you can make a month's worth of attempts in a day;
> if you scale up to 720, you can make a month's worth of attempts in an
> hour, ie once you've got one, it's a fairly straightforward engineering
> challenge at that point.
>
> So a "slow" attack simply doesn't seem likely to me. YMMV, obviously.

What you describe seems to match mining in its behavior: probabilistic, and scalable by pushing more electricity into more devices.

From this point-of-view, it seems to me that the amount of energy to mount a "fast" attack may eventually approach the energy required by mining, in which case someone who possesses the ability to mount such an attack may very well find it easier to just 51% the network (since that can be done today without having to pour R&D satoshis into developing practical quantum computers).

Regards,
ZmnSCPxj

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Luke Dashjr]

(To reiterate: I do not intend any of this as a NACK of Taproot.)

On Monday 15 March 2021 22:05:45 Matt Corallo wrote:
> > First, so long as we have hash-based addresses as a best practice, we can
> > continue to shrink the percentage of bitcoins affected through social
> > efforts discouraging address use. If the standard loses the hash, the
> > situation cannot be improved, and will indeed only get worse.
>
> I truly wish this were the case, but we've been beating that drum for at
> least nine years and still haven't solved it.

I think we've made progress over those 9 years, don't you?

> > Second, when/if quantum does compromise these coins, so long as they are
> > neglected or abandoned/lost coins (inherent in the current model), it can
> > be seen as equivalent to Bitcoin mining. At the end of the day, 37% of
> > supply minable by QCs is really no different than 37% minable by ASICs.
> > (We've seen far higher %s available for mining obviously.)
>
> Except its not? One entity would be able to steal that entire block of
> supply rather quickly (presumably over the course of a few days, at
> maximum), instead of a slow process with significant upfront real-world
> cost in the form of electricity.

My understanding is that at least initial successes would likely be very slow.
Hopefully we would have a permanent solution before it got too out of hand.


On Monday 15 March 2021 23:01:47 Karl-Johan Alm via bitcoin-dev wrote:
> The important distinction here is that, with hashes, an attacker has
> to race against the spending transaction confirming, whereas with
> naked pubkeys, the attacker doesn't have to wait for a spend to occur,
> drastically increasing the available time to attack.

More importantly, once an attack is recognised, with hashes, people can simply 
stop sending transactions and await a fix, to protect their stash. Without 
hashes, there is no defense at all (other than sending bitcoins to a 
non-taproot address and hoping they evade the attack in time).


On Monday 15 March 2021 23:12:18 Andrew Poelstra wrote:
> "No gain" except to save significant CPU time and bandwidth?

The CPU time is localised to involved nodes, and (correct me if I'm wrong) 
trivial in comparison to what is required to run a full node in the first 
place. I'm not sure how it looks with bandwidth.

> Having exposed keys also lets you do ring signatures over outputs, creating
> the ability to do private proof of funds via Provisions.

But you can also do comparable proofs behind a hash with Bulletproofs, right?

> > Despite this, I still don't think it's a reason to NACK Taproot: it
> > should be fairly trivial to add a hash on top in an additional softfork
> > and fix this.
>
> This would make Bitcoin strictly worse.

How so? People could just not use it if they don't care, right?
The alternative (if people care enough) is that those concerned about quantum 
risk would be forced to forego the benefits of Taproot and stick to p2pkh or 
such, which seems like an artificial punishment.

> > In addition to the points made by Mark, I also want to add two more, in
> > response to Pieter's "you can't claim much security if 37% of the supply
> > is at risk" argument. This argument is based in part on the fact that
> > many people reuse Bitcoin invoice addresses.
>
> 37% is a dramatic understatement. Every address which is derived using
> BIP32 should be assumed compromised to a QC attacker because xpubs are not
> treated like secret key material and are trivial to e.g. extract from
> hardware wallets or PSBTs. I expect the real number is close to 100%.

xpubs should be treated like secret key material IMO.

A quantum attacker would need to compromise your PC to attack a hardware 
wallet, right?

> In any case, Taproot keys, when used according to the recommendation in
> BIP-0341, are already hashes of their internal keys, so (a) Taproot outputs
> actually have better quantum resistance than legacy outputs; and (b) adding
> another hash would be strictly redundant.

It not only stops the attacker from obtaining the original key, but also 
prevents creating a new private key that can spend the output?


On Tuesday 16 March 2021 02:38:55 ZmnSCPxj via bitcoin-dev wrote:
> From this point-of-view, it seems to me that the amount of energy to mount
> a "fast" attack may eventually approach the energy required by mining, in
> which case someone who possesses the ability to mount such an attack may
> very well find it easier to just 51% the network (since that can be done
> today without having to pour R&D satoshis into developing practical quantum
> computers).

Mining adapts its difficulty to the block rate, so it will slow you down up to 
4x each retarget. An attack on public keys would probably scale better. :)

Luke

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 5234 bytes --]

On Tue, Mar 16, 2021 at 03:44:25AM +0000, Luke Dashjr wrote:
> (To reiterate: I do not intend any of this as a NACK of Taproot.)
>

Thanks, although it's still somewhat frustrating to be rehashing this
discussion again after so many years.
 
> On Monday 15 March 2021 23:12:18 Andrew Poelstra wrote:
> > "No gain" except to save significant CPU time and bandwidth?
> 
> The CPU time is localised to involved nodes, and (correct me if I'm wrong) 
> trivial in comparison to what is required to run a full node in the first 
> place. I'm not sure how it looks with bandwidth.
>

I really can't parse what "localized to involved nodes" means. All Bitcoin
nodes will be affected. Right now for nodes with sufficient bandwidth, signature
validation is the slowest part of validating transactions, which is why it
is disabled for the bulk of the chain during IBD. Taproot, by virtue of
enabling batch verification, would give a 2-3x speedup when validating the
same number of signatures.
 
> > Having exposed keys also lets you do ring signatures over outputs, creating
> > the ability to do private proof of funds via Provisions.
> 
> But you can also do comparable proofs behind a hash with Bulletproofs, right?
>

Yes, if you are willing to accept independent >100000x slowdowns on proving,
verification and code review.
 
> > > Despite this, I still don't think it's a reason to NACK Taproot: it
> > > should be fairly trivial to add a hash on top in an additional softfork
> > > and fix this.
> >
> > This would make Bitcoin strictly worse.
> 
> How so? People could just not use it if they don't care, right?
> The alternative (if people care enough) is that those concerned about quantum 
> risk would be forced to forego the benefits of Taproot and stick to p2pkh or 
> such, which seems like an artificial punishment.
>

People who do use it will reduce their privacy set, reduce the privacy set of
people who aren't using it, create confusion and delays for people implementing
Taproot, and slow down Bitcoin nodes who would have to validate the extra
material.
 
> > > In addition to the points made by Mark, I also want to add two more, in
> > > response to Pieter's "you can't claim much security if 37% of the supply
> > > is at risk" argument. This argument is based in part on the fact that
> > > many people reuse Bitcoin invoice addresses.
> >
> > 37% is a dramatic understatement. Every address which is derived using
> > BIP32 should be assumed compromised to a QC attacker because xpubs are not
> > treated like secret key material and are trivial to e.g. extract from
> > hardware wallets or PSBTs. I expect the real number is close to 100%.
> 
> xpubs should be treated like secret key material IMO.
> 

Your opinion is noted. This is not how xpubs are, in reality, treated. And
it would make them significantly less useful if you could no longer share
descriptors with people you would like to do multiparty transactions with.

> A quantum attacker would need to compromise your PC to attack a hardware 
> wallet, right?
> 

No, I expect you could get xpubs out of hardware wallets using any of the
web endpoints provided by hardware wallet vendors, or by asking it to update
a PSBT with any of its scriptpubkeys.

> > In any case, Taproot keys, when used according to the recommendation in
> > BIP-0341, are already hashes of their internal keys, so (a) Taproot outputs
> > actually have better quantum resistance than legacy outputs; and (b) adding
> > another hash would be strictly redundant.
> 
> It not only stops the attacker from obtaining the original key, but also 
> prevents creating a new private key that can spend the output?
> 

I don't know what you mean by this. If the original key is usable, i.e. a QC
has appeared overnight, then Bitcoin is screwed. (For that matter, the same is
true if there is an overnight break in SHA2, or ECDSA, or any other major
component of Bitcoin. Fortunately this is not how cryptographic breaks have
historically appeared.) There is no new private key that could be created.

If there is a QC where we have some warning, then we need to disable all EC
operations in Script, including keypath spends of Taproot outputs, and this
would be true with or without the redundant extra hash.

Taproot, with or without the redundant hash, has a few distinct benefits over
legacy outputs in this scenario:

  * Taproot keys are hashes of semi-secret data (at least as secret as xpubs)
    in a well-defined and simple way, by virtue of committing to an internal
    key and some script (usually unspendable)
  * By adding secret data to the script, users can provide extra data to prove
    in a QC-hard way, even if their internal key is compromised
  * Taproot keys can be chosen to be provably unspendable except by a DL break,
    as David Harding points out, by using a NUMS point as an internal key.

None of these factors are improved by adding an extra hash.

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Matt Corallo]

On 3/15/21 23:44, Luke Dashjr wrote:
> (To reiterate: I do not intend any of this as a NACK of Taproot.)

Frankly, then why parrot arguments you don't agree with in an already-tense discussion? I'm really not sure what there 
is to gain by dredging up years-old since-settled debates except to cause yet more delay and frustration.

> On Monday 15 March 2021 22:05:45 Matt Corallo wrote:
>>> First, so long as we have hash-based addresses as a best practice, we can
>>> continue to shrink the percentage of bitcoins affected through social
>>> efforts discouraging address use. If the standard loses the hash, the
>>> situation cannot be improved, and will indeed only get worse.
>>
>> I truly wish this were the case, but we've been beating that drum for at
>> least nine years and still haven't solved it.
> 
> I think we've made progress over those 9 years, don't you?

Some, sure, but not anywhere near the amount of progress we'd need to make to have an impact on QC security of the 
overall system.

>> Except its not? One entity would be able to steal that entire block of
>> supply rather quickly (presumably over the course of a few days, at
>> maximum), instead of a slow process with significant upfront real-world
>> cost in the form of electricity.
> 
> My understanding is that at least initial successes would likely be very slow.
> Hopefully we would have a permanent solution before it got too out of hand.

There is a lot of debate on this point in the original thread which discussed this several years ago. But even if it 
were the case, it still doesn't make "let QC owners steal coins" somehow equivalent to mining. There are probably 
several blocks of coins that can be stolen to the tune of much greater rewards than a block reward, but, more broadly, 
what?! QC owners stealing coins from old outputs isn't somehow going to be seen as "OK", not to mention because many old 
outputs do have owners with the keys, they aren't all forgotten or lost.

Matt

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Ryan Grant]

I enjoyed the reindexing using a distinct subject and I appreciate the
new clarifications by those whose instinct was to put effort into a
response.  Although I try to keep up, some of the taproot QC
mitigations that are possible had escaped my attention thus far.

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Eoin McQuinn]

[-- Attachment #1: Type: text/plain, Size: 659 bytes --]

How do people in other non-English-speaking parts of the world use and
develop Bitcoin Core?

On Wed, Mar 17, 2021 at 1:24 AM Ryan Grant via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> I enjoyed the reindexing using a distinct subject and I appreciate the
> new clarifications by those whose instinct was to put effort into a
> response.  Although I try to keep up, some of the taproot QC
> mitigations that are possible had escaped my attention thus far.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 1163 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 2362 bytes --]

On Mon, Mar 15, 2021 at 09:48:15PM +0000, Luke Dashjr via bitcoin-dev wrote:
> Also, what I didn't know myself until today, is that we do not actually gain 
> anything from this: the features proposed to make use of the raw keys being 
> public prior to spending can be implemented with hashed keys as well.
> It would use significantly more CPU time and bandwidth (between private 
> parties, not on-chain), but there should be no shortage of that for anyone 
> running a full node (indeed, CPU time is freed up by Taproot!); at worst, it 
> would create an incentive for more people to use their own full node, which 
> is a good thing!
> 

"No gain" except to save significant CPU time and bandwidth? As Matt points
out there is also a storage hit (unless you want to _really_ waste CPU time
by using pubkey recovery, eliminating any hope of batch validation while
introducing a new dependency on an algorithm with a very unclear patent
story).

Having exposed keys also lets you do ring signatures over outputs, creating the
ability to do private proof of funds via Provisions.

> Despite this, I still don't think it's a reason to NACK Taproot: it should be 
> fairly trivial to add a hash on top in an additional softfork and fix this.
> 

This would make Bitcoin strictly worse.

> In addition to the points made by Mark, I also want to add two more, in 
> response to Pieter's "you can't claim much security if 37% of the supply is 
> at risk" argument. This argument is based in part on the fact that many 
> people reuse Bitcoin invoice addresses.
> 

37% is a dramatic understatement. Every address which is derived using BIP32
should be assumed compromised to a QC attacker because xpubs are not treated
like secret key material and are trivial to e.g. extract from hardware wallets
or PSBTs. I expect the real number is close to 100%.


In any case, Taproot keys, when used according to the recommendation in
BIP-0341, are already hashes of their internal keys, so (a) Taproot outputs
actually have better quantum resistance than legacy outputs; and (b) adding
another hash would be strictly redundant.

-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Andrea]

Il 16/03/21 00:12, Andrew Poelstra via bitcoin-dev ha scritto:

> Having exposed keys also lets you do ring signatures over outputs, creating the
> ability to do private proof of funds via Provisions.
> 

Hi! Sorry for the OT, could you provide some references to ring 
signatures over/for/via taproot (I mean the schema or something like 
that)? And what is "Provisions" (the capital letter makes me think it's 
a product/technology)?
I'm a rookie following this mailing since just a few months...

Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections)

[Andrew Poelstra]

[-- Attachment #1: Type: text/plain, Size: 2458 bytes --]

On Tue, Mar 16, 2021 at 03:10:21PM +0100, Andrea via bitcoin-dev wrote:
> 
> Hi! Sorry for the OT, could you provide some references to ring signatures
> over/for/via taproot (I mean the schema or something like that)? And what is
> "Provisions" (the capital letter makes me think it's a product/technology)?
> I'm a rookie following this mailing since just a few months...
>

Thanks for posting such a positive message in an otherwise tense thread :)

Provisions is a scheme for providing proof of ownership of funds, developed
by Dagher et al in 2015 at https://eprint.iacr.org/2015/1008 . The way it
works is to collect all of the Bitcoin outputs which have exposed/known
public keys then associate to these keys a Pedersen commitment which commits
to the outputs' amounts in a homomorphic way.

Homomorphic means that even though the commitments hide what the original
amounts are, anyone can add them together (in some sense) to get a new
commitment to the sum of the original amounts.

So Provisions is essentially a zero-knowledge proof of the following statement

    1. I have a commitment to >100BTC (or whatever)...
    2. ...which is a sum of commitments of actual UTXO values...
    3. ...where these UTXOs come from the set of known-public-key UTXOs...
    4. ...and I am able to sign with the public keys associated to them.

which proves ownership of some amount of BTC, without revealing which specific
UTXOs were involved. This zero-knowledge proof can be done fairly efficiently
by exploiting the structure of EC public keys and Pedersen commitments.


Unfortunately, most unspent Bitcoin outputs do not have known public keys,
which means that you can only do a Provisions proof using a small anonymity
set. However, all Taproot outputs, by virtue of having exposed public keys
(which is the point under contention in this thread), will be in the set of
exposed-public-key UTXOs, allowing people to do Provisions proofs where
their anonymity set consists of a large proportion of active coins.


BTW, even without Provisions, there are some similar and simpler things you
can do with Taproot keys along these lines. See for example
https://twitter.com/n1ckler/status/1334240709814136833



-- 
Andrew Poelstra
Director of Research, Blockstream
Email: apoelstra at wpsoftware.net
Web:   https://www.wpsoftware.net/andrew

The sun is always shining in space
    -Justin Lewis-Webster


[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]

Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections)

[ZmnSCPxj]

Good morning Andrew and Andrea,

Further afield: https://en.bitcoin.it/wiki/Taproot_Uses

Taproot ring signatures was also asked by Andrea, above page contains this link (have not actually read it myself): https://github.com/jonasnick/taproot-ringsig

Regards,
ZmnSCPxj

Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections)

[Andrea]

Thanks for your time Andrew and ZmnSCPxj,

Jonas contrib was also referenced in twitter post provided by Andrew, 
but the repetion is an effective underlining of its importance :)

I'm busy-at-work for a couple of days, but I'm planning my weekend spare 
time to deal with infos from both of you... I guess I'll have further 
questions :)


Il 17/03/21 05:24, ZmnSCPxj ha scritto:
> Good morning Andrew and Andrea,
> 
> Further afield: https://en.bitcoin.it/wiki/Taproot_Uses
> 
> Taproot ring signatures was also asked by Andrea, above page contains this link (have not actually read it myself): https://github.com/jonasnick/taproot-ringsig
> 
> Regards,
> ZmnSCPxj
> 

Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections)

[Andrea Barontini]

Hi again Andrew and ZmnSCPxj,

I have dealt with the resources you provided me

Regarding Provisions I have concentrated my attention to Proof of assets 
and I have to say it has been a good "exercise" for my ZKP learning

Regarding Jonas Nick code I'm not sure I would call it "a use of 
Taproot" since -as far as I have understood (perhaps not enough)- the 
Taproot's role there is just to provide public keys for the anonimity 
set, so no Taproot core specificities applied to Rings

Always a pleasure to discover something new and feel a (humble) part of 
a community!

See ya

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 3838 bytes --]

On Mon, Mar 15, 2021 at 09:48:15PM +0000, Luke Dashjr via bitcoin-dev wrote:
> Note that in all circumstances, Bitcoin is endangered when QC becomes
> a reality [...] it could very well become an unrecoverable situation
> if QC go online prior to having a full quantum-safe solution.

The main concern seems to be someone developing, in secret, a quantum
computer with enough capacity to compromise millions of keys and then
deciding to use the most powerful and (probably) expensive computer ever
developed to steal coins that will almost immediately lose most or all
of their value.

That's certainly a threat we should consider, but like other "movie
plot" threats, I think we should weigh its unlikeliness in comparison
to the people who are losing smaller amounts of money on a regular basis
right now because we don't already have taproot---people who don't use
multisig, or contracts with threshold reduction timeout clauses, or
certain types of covenants because the contingencies these types of
scripts protect against come at too great a cost in fees for the typical
case where no contingencies are needed.

We have many ideas about how to mitigate the risk of effective quantum
computing attacks, from emergency protection to long-term solutions, so
it seems to me that the real risk in the movie plot scenario comes
entirely from *secret advances* in quantum computing.  Other similar
risks for Bitcoin exist, such as secret discoveries about how to
compromise the hash functions Bitcoin depends on.  One way to help
control those risks is to pay a public bounty to anyone who provably and
publicly discloses the secret advance (ideally while allowing the leaker
to remain anonymous).  Several years ago, Peter Todd created a series of
Bitcoin addresses that does exactly that.[1]

For example, if you pay 35Snmmy3uhaer2gTboc81ayCip4m9DT4ko, then
anyone[2] who can prove a collision attack against Bitcoin's primary
hash function, SHA256, will be able to claim the bitcoins you and other
people sent to that address.  Their claim of the funds will publicly
demonstrate that someone can create a SHA256 collision, which is an
attack we currently believe to be impractical.  This system was
demonstrated to work about four years ago[3] when the collision bounty
for the much weaker SHA1 function was claimed.[4]

We can already create an output script with a Nothing Up My Sleeve
(NUMS) point that would provide a trustless bounty to anyone proving the
capability to steal any P2PK-style output with secp256k1's 128-bit
security.  I curious about whether anyone informed about ECC and QC
knows how to create output scripts with lower difficulty that could be
used to measure the progress of QC-based EC key cracking.  E.g.,
NUMS-based ECDSA- or taproot-compatible scripts with a security strength
equivalent to 80, 96, and 112 bit security.

That way the people and businesses concerned about QC advances could
send a few BTC to those addresses to create a QC early warning system
that would allow us to continue confidently working on EC-based
protocols for now but also objectively alert us to when we need to shift
to working on post-QC protocols for the future.

Thank you,

-Dave

[1] https://bitcointalk.org/index.php?topic=293382.0

[2] Anyone claiming the reward may need to mine their own transaction to
    protect it against rewriting.  In the worst case, they may need to
    mine at a depth of several blocks or share their reward with miners
    to prevent sniping reorgs.

[3] https://blockstream.info/tx/8d31992805518fd62daa3bdd2a5c4fd2cd3054c9b3dca1d78055e9528cff6adc

[4] To the best of my knowledge, nothing in Bitcoin ever depended
    significantly on SHA1, and especially not on SHA1 collision
    resistance, which was known to be weak even in 2009 when Nakamoto
    first published the Bitcoin software.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 1199 bytes --]

On Tue, 16 Mar 2021 at 11:25, David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

>
> I curious about whether anyone informed about ECC and QC
> knows how to create output scripts with lower difficulty that could be
> used to measure the progress of QC-based EC key cracking.  E.g.,
> NUMS-based ECDSA- or taproot-compatible scripts with a security strength
> equivalent to 80, 96, and 112 bit security.


Hi Dave,

This is actually relatively easy if you are willing to use a trusted setup.
The trusted party takes a secp256k1 secret key and verifiably encrypt it
under a NUMS public key from the weaker group. Therefore if you can crack
the weaker group's public key you get the secp256k1 secret key.
Camenisch-Damgard[1] cut-and-choose verifiable encryption works here.
People then pay the secp256k1 public key funds to create the bounty. As
long as the trusted party deletes the secret key afterwards the scheme is
secure.

Splitting the trusted setup among several parties where only one of them
needs to be honest looks doable but would take some engineering and
analysis work.

[1] https://link.springer.com/content/pdf/10.1007/3-540-44448-3_25.pdf

Cheers,

LL

[-- Attachment #2: Type: text/html, Size: 1772 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[ZmnSCPxj]

Good morning LL,

> On Tue, 16 Mar 2021 at 11:25, David A. Harding via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> > I curious about whether anyone informed about ECC and QC
> > knows how to create output scripts with lower difficulty that could be
> > used to measure the progress of QC-based EC key cracking.  E.g.,
> > NUMS-based ECDSA- or taproot-compatible scripts with a security strength
> > equivalent to 80, 96, and 112 bit security.
>
> Hi Dave,
>
> This is actually relatively easy if you are willing to use a trusted setup. The trusted party takes a secp256k1 secret key and verifiably encrypt it under a NUMS public key from the weaker group. Therefore if you can crack the weaker group's public key you get the secp256k1 secret key. Camenisch-Damgard[1] cut-and-choose verifiable encryption works here.
> People then pay the secp256k1 public key funds to create the bounty. As long as the trusted party deletes the secret key afterwards the scheme is secure.
>
> Splitting the trusted setup among several parties where only one of them needs to be honest looks doable but would take some engineering and analysis work.

To simplify this, perhaps `OP_CHECKMULTISIG` is sufficient?
Simply have the N parties generate individual private keys, encrypt each of them with the NUMS pubkey from the weaker group, then pay out to an N-of-N `OP_CHECKMULTISIG` address of all the participants.
Then a single honest participant is enough to ensure security of the bounty.

Knowing the privkey from the weaker groups would then be enough to extract all of the SECP256K1 privkeys that would unlock the funds in Bitcoin.

This should reduce the need for analysis and engineering.

Regards,
ZmnSCPxj

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Lloyd Fournier]

[-- Attachment #1: Type: text/plain, Size: 2525 bytes --]

On Fri, 16 Apr 2021 at 13:47, ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning LL,
>
> > On Tue, 16 Mar 2021 at 11:25, David A. Harding via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > > I curious about whether anyone informed about ECC and QC
> > > knows how to create output scripts with lower difficulty that could be
> > > used to measure the progress of QC-based EC key cracking.  E.g.,
> > > NUMS-based ECDSA- or taproot-compatible scripts with a security
> strength
> > > equivalent to 80, 96, and 112 bit security.
> >
> > Hi Dave,
> >
> > This is actually relatively easy if you are willing to use a trusted
> setup. The trusted party takes a secp256k1 secret key and verifiably
> encrypt it under a NUMS public key from the weaker group. Therefore if you
> can crack the weaker group's public key you get the secp256k1 secret key.
> Camenisch-Damgard[1] cut-and-choose verifiable encryption works here.
> > People then pay the secp256k1 public key funds to create the bounty. As
> long as the trusted party deletes the secret key afterwards the scheme is
> secure.
> >
> > Splitting the trusted setup among several parties where only one of them
> needs to be honest looks doable but would take some engineering and
> analysis work.
>
> To simplify this, perhaps `OP_CHECKMULTISIG` is sufficient?
> Simply have the N parties generate individual private keys, encrypt each
> of them with the NUMS pubkey from the weaker group, then pay out to an
> N-of-N `OP_CHECKMULTISIG` address of all the participants.
> Then a single honest participant is enough to ensure security of the
> bounty.
>
> Knowing the privkey from the weaker groups would then be enough to extract
> all of the SECP256K1 privkeys that would unlock the funds in Bitcoin.


Yes! Nice idea.

Another idea that came to mind is that you could also just prove equality
between the weak group's key and the secp256k1 key. e.g. generate a 160-bit
key and use it both as a secp256k1 and a 160-bit curve key and prove
equality between them and give funds to the secp256k1 key. I implemented a
proof between ed25519 and secp256k1 a little while ago for example:
https://docs.rs/sigma_fun/0.3.0/sigma_fun/ext/dl_secp256k1_ed25519_eq/index.html

This would come with the extra assumption that it's easier to break the
160-bit key on the 160-bit curve as opposed to just breaking the 160-bit
key on the 256-bit curve. Intuitively I think this is the case but I would
want to study that further before taking this approach.

LL

[-- Attachment #2: Type: text/html, Size: 3218 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Erik Aronesty]

The argument that hashed public addresses provide meaningful quantum
resistance is flawed *when considered in the context*.of Bitcoin
itself.

This article by Andrew Chow is easy to read and makes a strong case
against the quantum utility of hashed public keys:
https://cryptowords.github.io/why-does-hashing-public-keys-not-actually-provide-any-quantum-resistance

And then, of course, one should be mindful of the case against quantum
computing itself - it is neither inevitable nor "just around the
corner".   Mikhail Dyakonov summarized the arguments well here:
https://t.co/cgrfrroTTT?amp=1.

My current stance (at my company at least) is that planning for
quantum computing should be limited to "a provable and written ability
to upgrade if it becomes clear that it's necessary."

Does anyone think it would it be useful to write up a more official,
and even partly functional plan for Bitcoin to use zero-knowledge
proofs to transition to quantum resistance?

- Erik Aronesty
  CTO, Atkama

On Mon, Mar 15, 2021 at 5:48 PM Luke Dashjr via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> I do not personally see this as a reason to NACK Taproot, but it has become
> clear to me over the past week or so that many others are unaware of this
> tradeoff, so I am sharing it here to ensure the wider community is aware of
> it and can make their own judgements.
>
> Mark Friedenbach explains on his blog:
>     https://freicoin.substack.com/p/why-im-against-taproot
>
> In short, Taproot loses an important safety protection against quantum.
> Note that in all circumstances, Bitcoin is endangered when QC becomes a
> reality, but pre-Taproot, it is possible for the network to "pause" while a
> full quantum-safe fix is developed, and then resume transacting. With Taproot
> as-is, it could very well become an unrecoverable situation if QC go online
> prior to having a full quantum-safe solution.
>
> Also, what I didn't know myself until today, is that we do not actually gain
> anything from this: the features proposed to make use of the raw keys being
> public prior to spending can be implemented with hashed keys as well.
> It would use significantly more CPU time and bandwidth (between private
> parties, not on-chain), but there should be no shortage of that for anyone
> running a full node (indeed, CPU time is freed up by Taproot!); at worst, it
> would create an incentive for more people to use their own full node, which
> is a good thing!
>
> Despite this, I still don't think it's a reason to NACK Taproot: it should be
> fairly trivial to add a hash on top in an additional softfork and fix this.
>
> In addition to the points made by Mark, I also want to add two more, in
> response to Pieter's "you can't claim much security if 37% of the supply is
> at risk" argument. This argument is based in part on the fact that many
> people reuse Bitcoin invoice addresses.
>
> First, so long as we have hash-based addresses as a best practice, we can
> continue to shrink the percentage of bitcoins affected through social efforts
> discouraging address use. If the standard loses the hash, the situation
> cannot be improved, and will indeed only get worse.
>
> Second, when/if quantum does compromise these coins, so long as they are
> neglected or abandoned/lost coins (inherent in the current model), it can be
> seen as equivalent to Bitcoin mining. At the end of the day, 37% of supply
> minable by QCs is really no different than 37% minable by ASICs. (We've seen
> far higher %s available for mining obviously.)
>
> To conclude, I recommend anyone using Bitcoin to read Mark's article, my
> thoughts, and any other arguments on the topic; decide if this is a concern
> to you, and make your own post(s) accordingly. Mark has conceded the argument
> (AFAIK he doesn't have an interest in bitcoins anyway), and I do not consider
> it a showstopper - so if anyone else out there does, please make yourself
> known ASAP since Taproot has already moved on to the activation phase and it
> is likely software will be released within the next month or two as things
> stand.
>
> Luke
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Martin Schwarz]

[-- Attachment #1: Type: text/plain, Size: 5186 bytes --]

Erik,

> Does anyone think it would it be useful to write up a more official,
and even partly functional plan for Bitcoin to use zero-knowledge
proofs to transition to quantum resistance?

yes, this would be appreciated very much! Andrew Chow's write-up
gives already some high-level idea, but a more detailed exposition
would be essential for further discussion.

thank you,
Martin

On Mon, Mar 22, 2021 at 3:47 PM Erik Aronesty via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> The argument that hashed public addresses provide meaningful quantum
> resistance is flawed *when considered in the context*.of Bitcoin
> itself.
>
> This article by Andrew Chow is easy to read and makes a strong case
> against the quantum utility of hashed public keys:
>
> https://cryptowords.github.io/why-does-hashing-public-keys-not-actually-provide-any-quantum-resistance
>
> And then, of course, one should be mindful of the case against quantum
> computing itself - it is neither inevitable nor "just around the
> corner".   Mikhail Dyakonov summarized the arguments well here:
> https://t.co/cgrfrroTTT?amp=1.
>
> My current stance (at my company at least) is that planning for
> quantum computing should be limited to "a provable and written ability
> to upgrade if it becomes clear that it's necessary."
>
> Does anyone think it would it be useful to write up a more official,
> and even partly functional plan for Bitcoin to use zero-knowledge
> proofs to transition to quantum resistance?
>
> - Erik Aronesty
>   CTO, Atkama
>
> On Mon, Mar 15, 2021 at 5:48 PM Luke Dashjr via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > I do not personally see this as a reason to NACK Taproot, but it has
> become
> > clear to me over the past week or so that many others are unaware of this
> > tradeoff, so I am sharing it here to ensure the wider community is aware
> of
> > it and can make their own judgements.
> >
> > Mark Friedenbach explains on his blog:
> >     https://freicoin.substack.com/p/why-im-against-taproot
> >
> > In short, Taproot loses an important safety protection against quantum.
> > Note that in all circumstances, Bitcoin is endangered when QC becomes a
> > reality, but pre-Taproot, it is possible for the network to "pause"
> while a
> > full quantum-safe fix is developed, and then resume transacting. With
> Taproot
> > as-is, it could very well become an unrecoverable situation if QC go
> online
> > prior to having a full quantum-safe solution.
> >
> > Also, what I didn't know myself until today, is that we do not actually
> gain
> > anything from this: the features proposed to make use of the raw keys
> being
> > public prior to spending can be implemented with hashed keys as well.
> > It would use significantly more CPU time and bandwidth (between private
> > parties, not on-chain), but there should be no shortage of that for
> anyone
> > running a full node (indeed, CPU time is freed up by Taproot!); at
> worst, it
> > would create an incentive for more people to use their own full node,
> which
> > is a good thing!
> >
> > Despite this, I still don't think it's a reason to NACK Taproot: it
> should be
> > fairly trivial to add a hash on top in an additional softfork and fix
> this.
> >
> > In addition to the points made by Mark, I also want to add two more, in
> > response to Pieter's "you can't claim much security if 37% of the supply
> is
> > at risk" argument. This argument is based in part on the fact that many
> > people reuse Bitcoin invoice addresses.
> >
> > First, so long as we have hash-based addresses as a best practice, we can
> > continue to shrink the percentage of bitcoins affected through social
> efforts
> > discouraging address use. If the standard loses the hash, the situation
> > cannot be improved, and will indeed only get worse.
> >
> > Second, when/if quantum does compromise these coins, so long as they are
> > neglected or abandoned/lost coins (inherent in the current model), it
> can be
> > seen as equivalent to Bitcoin mining. At the end of the day, 37% of
> supply
> > minable by QCs is really no different than 37% minable by ASICs. (We've
> seen
> > far higher %s available for mining obviously.)
> >
> > To conclude, I recommend anyone using Bitcoin to read Mark's article, my
> > thoughts, and any other arguments on the topic; decide if this is a
> concern
> > to you, and make your own post(s) accordingly. Mark has conceded the
> argument
> > (AFAIK he doesn't have an interest in bitcoins anyway), and I do not
> consider
> > it a showstopper - so if anyone else out there does, please make yourself
> > known ASAP since Taproot has already moved on to the activation phase
> and it
> > is likely software will be released within the next month or two as
> things
> > stand.
> >
> > Luke
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 6953 bytes --]

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Tim Ruffing]

On Mon, 2021-03-22 at 10:24 -0400, Erik Aronesty via bitcoin-dev wrote:
> 
> Does anyone think it would it be useful to write up a more official,
> and even partly functional plan for Bitcoin to use zero-knowledge
> proofs to transition to quantum resistance?

Yes, for sure. This is certainly something that the community should
discuss. Looking into this problem is also on my (too long) list of
research problems.

I think IF we arrive at the conclusion that this is a good idea (which
is possible but not at all clear to me at this point), then one of the
questions is whether it's desirable to use something more efficient
than a zero-knowledge proof, at the potential cost of committing to a
real public key of a simple post-quantum signature scheme. This could
for example be a hash-based one-time signature scheme (but something
more efficient than the often mentioned Lamport signatures, e.g.,
Winternitz or W-OTS+ signatures).

Re: [bitcoin-dev] PSA: Taproot loss of quantum protections

[Erik Aronesty]

Noe: for A. Chow's upgrade to work, there obviously has to be an
effort to deliberately-blacklist unupgraded coins, say after 10-20
years of opportunity to upgrade, or something like that, as long as
the transition to quantum isn't so fast that there's no way to do
this.

On Mon, Mar 22, 2021 at 10:24 AM Erik Aronesty <erik@q32.com> wrote:
>
> The argument that hashed public addresses provide meaningful quantum
> resistance is flawed *when considered in the context*.of Bitcoin
> itself.
>
> This article by Andrew Chow is easy to read and makes a strong case
> against the quantum utility of hashed public keys:
> https://cryptowords.github.io/why-does-hashing-public-keys-not-actually-provide-any-quantum-resistance
>
> And then, of course, one should be mindful of the case against quantum
> computing itself - it is neither inevitable nor "just around the
> corner".   Mikhail Dyakonov summarized the arguments well here:
> https://t.co/cgrfrroTTT?amp=1.
>
> My current stance (at my company at least) is that planning for
> quantum computing should be limited to "a provable and written ability
> to upgrade if it becomes clear that it's necessary."
>
> Does anyone think it would it be useful to write up a more official,
> and even partly functional plan for Bitcoin to use zero-knowledge
> proofs to transition to quantum resistance?
>
> - Erik Aronesty
>   CTO, Atkama
>
> On Mon, Mar 15, 2021 at 5:48 PM Luke Dashjr via bitcoin-dev
> <bitcoin-dev@lists.linuxfoundation.org> wrote:
> >
> > I do not personally see this as a reason to NACK Taproot, but it has become
> > clear to me over the past week or so that many others are unaware of this
> > tradeoff, so I am sharing it here to ensure the wider community is aware of
> > it and can make their own judgements.
> >
> > Mark Friedenbach explains on his blog:
> >     https://freicoin.substack.com/p/why-im-against-taproot
> >
> > In short, Taproot loses an important safety protection against quantum.
> > Note that in all circumstances, Bitcoin is endangered when QC becomes a
> > reality, but pre-Taproot, it is possible for the network to "pause" while a
> > full quantum-safe fix is developed, and then resume transacting. With Taproot
> > as-is, it could very well become an unrecoverable situation if QC go online
> > prior to having a full quantum-safe solution.
> >
> > Also, what I didn't know myself until today, is that we do not actually gain
> > anything from this: the features proposed to make use of the raw keys being
> > public prior to spending can be implemented with hashed keys as well.
> > It would use significantly more CPU time and bandwidth (between private
> > parties, not on-chain), but there should be no shortage of that for anyone
> > running a full node (indeed, CPU time is freed up by Taproot!); at worst, it
> > would create an incentive for more people to use their own full node, which
> > is a good thing!
> >
> > Despite this, I still don't think it's a reason to NACK Taproot: it should be
> > fairly trivial to add a hash on top in an additional softfork and fix this.
> >
> > In addition to the points made by Mark, I also want to add two more, in
> > response to Pieter's "you can't claim much security if 37% of the supply is
> > at risk" argument. This argument is based in part on the fact that many
> > people reuse Bitcoin invoice addresses.
> >
> > First, so long as we have hash-based addresses as a best practice, we can
> > continue to shrink the percentage of bitcoins affected through social efforts
> > discouraging address use. If the standard loses the hash, the situation
> > cannot be improved, and will indeed only get worse.
> >
> > Second, when/if quantum does compromise these coins, so long as they are
> > neglected or abandoned/lost coins (inherent in the current model), it can be
> > seen as equivalent to Bitcoin mining. At the end of the day, 37% of supply
> > minable by QCs is really no different than 37% minable by ASICs. (We've seen
> > far higher %s available for mining obviously.)
> >
> > To conclude, I recommend anyone using Bitcoin to read Mark's article, my
> > thoughts, and any other arguments on the topic; decide if this is a concern
> > to you, and make your own post(s) accordingly. Mark has conceded the argument
> > (AFAIK he doesn't have an interest in bitcoins anyway), and I do not consider
> > it a showstopper - so if anyone else out there does, please make yourself
> > known ASAP since Taproot has already moved on to the activation phase and it
> > is likely software will be released within the next month or two as things
> > stand.
> >
> > Luke
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev