* [bitcoin-dev] PSA: Taproot loss of quantum protections
@ 2021-03-15 21:48 Luke Dashjr
2021-03-15 22:05 ` Matt Corallo
` (3 more replies)
0 siblings, 4 replies; 29+ messages in thread
From: Luke Dashjr @ 2021-03-15 21:48 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
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
^ permalink raw reply [flat|nested] 29+ messages in thread* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 21:48 [bitcoin-dev] PSA: Taproot loss of quantum protections Luke Dashjr @ 2021-03-15 22:05 ` Matt Corallo 2021-03-15 22:30 ` Robert Spigler ` (2 more replies) 2021-03-15 23:12 ` Andrew Poelstra ` (2 subsequent siblings) 3 siblings, 3 replies; 29+ messages in thread From: Matt Corallo @ 2021-03-15 22:05 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 22:05 ` Matt Corallo @ 2021-03-15 22:30 ` Robert Spigler 2021-03-15 22:40 ` Jeremy 2021-03-16 3:44 ` Luke Dashjr 2 siblings, 0 replies; 29+ messages in thread From: Robert Spigler @ 2021-03-15 22:30 UTC (permalink / raw) To: Matt Corallo, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 22:05 ` Matt Corallo 2021-03-15 22:30 ` Robert Spigler @ 2021-03-15 22:40 ` Jeremy 2021-03-15 22:48 ` Matt Corallo 2021-03-16 3:44 ` Luke Dashjr 2 siblings, 1 reply; 29+ messages in thread From: Jeremy @ 2021-03-15 22:40 UTC (permalink / raw) To: Matt Corallo, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 22:40 ` Jeremy @ 2021-03-15 22:48 ` Matt Corallo 2021-03-15 23:01 ` Karl-Johan Alm 0 siblings, 1 reply; 29+ messages in thread From: Matt Corallo @ 2021-03-15 22:48 UTC (permalink / raw) To: Jeremy, Bitcoin Protocol Discussion 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> > ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 22:48 ` Matt Corallo @ 2021-03-15 23:01 ` Karl-Johan Alm 2021-03-15 23:19 ` Matt Corallo ` (2 more replies) 0 siblings, 3 replies; 29+ messages in thread From: Karl-Johan Alm @ 2021-03-15 23:01 UTC (permalink / raw) To: Bitcoin Protocol Discussion 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) ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 23:01 ` Karl-Johan Alm @ 2021-03-15 23:19 ` Matt Corallo 2021-03-15 23:46 ` Lloyd Fournier 2021-03-16 0:50 ` Anthony Towns 2 siblings, 0 replies; 29+ messages in thread From: Matt Corallo @ 2021-03-15 23:19 UTC (permalink / raw) To: Karl-Johan Alm, Bitcoin Protocol Discussion 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 > ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 23:01 ` Karl-Johan Alm 2021-03-15 23:19 ` Matt Corallo @ 2021-03-15 23:46 ` Lloyd Fournier 2021-03-16 0:50 ` Anthony Towns 2 siblings, 0 replies; 29+ messages in thread From: Lloyd Fournier @ 2021-03-15 23:46 UTC (permalink / raw) To: Karl-Johan Alm, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 23:01 ` Karl-Johan Alm 2021-03-15 23:19 ` Matt Corallo 2021-03-15 23:46 ` Lloyd Fournier @ 2021-03-16 0:50 ` Anthony Towns 2021-03-16 2:38 ` ZmnSCPxj 2 siblings, 1 reply; 29+ messages in thread From: Anthony Towns @ 2021-03-16 0:50 UTC (permalink / raw) To: Karl-Johan Alm, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-16 0:50 ` Anthony Towns @ 2021-03-16 2:38 ` ZmnSCPxj 0 siblings, 0 replies; 29+ messages in thread From: ZmnSCPxj @ 2021-03-16 2:38 UTC (permalink / raw) To: Anthony Towns, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 22:05 ` Matt Corallo 2021-03-15 22:30 ` Robert Spigler 2021-03-15 22:40 ` Jeremy @ 2021-03-16 3:44 ` Luke Dashjr 2021-03-16 13:28 ` Andrew Poelstra 2021-03-16 17:25 ` Matt Corallo 2 siblings, 2 replies; 29+ messages in thread From: Luke Dashjr @ 2021-03-16 3:44 UTC (permalink / raw) To: Matt Corallo, ZmnSCPxj, Karl-Johan Alm, Andrew Poelstra Cc: Bitcoin Protocol Discussion (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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-16 3:44 ` Luke Dashjr @ 2021-03-16 13:28 ` Andrew Poelstra 2021-03-16 17:25 ` Matt Corallo 1 sibling, 0 replies; 29+ messages in thread From: Andrew Poelstra @ 2021-03-16 13:28 UTC (permalink / raw) To: Luke Dashjr; +Cc: Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-16 3:44 ` Luke Dashjr 2021-03-16 13:28 ` Andrew Poelstra @ 2021-03-16 17:25 ` Matt Corallo 2021-03-17 1:23 ` Ryan Grant 1 sibling, 1 reply; 29+ messages in thread From: Matt Corallo @ 2021-03-16 17:25 UTC (permalink / raw) To: Luke Dashjr, ZmnSCPxj, Karl-Johan Alm, Andrew Poelstra Cc: Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-16 17:25 ` Matt Corallo @ 2021-03-17 1:23 ` Ryan Grant 2021-03-17 11:56 ` Eoin McQuinn 0 siblings, 1 reply; 29+ messages in thread From: Ryan Grant @ 2021-03-17 1:23 UTC (permalink / raw) To: Bitcoin Protocol Discussion 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. ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-17 1:23 ` Ryan Grant @ 2021-03-17 11:56 ` Eoin McQuinn 0 siblings, 0 replies; 29+ messages in thread From: Eoin McQuinn @ 2021-03-17 11:56 UTC (permalink / raw) To: Ryan Grant, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 21:48 [bitcoin-dev] PSA: Taproot loss of quantum protections Luke Dashjr 2021-03-15 22:05 ` Matt Corallo @ 2021-03-15 23:12 ` Andrew Poelstra 2021-03-16 14:10 ` Andrea 2021-03-16 0:24 ` [bitcoin-dev] PSA: Taproot loss of quantum protections David A. Harding 2021-03-22 14:24 ` Erik Aronesty 3 siblings, 1 reply; 29+ messages in thread From: Andrew Poelstra @ 2021-03-15 23:12 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 23:12 ` Andrew Poelstra @ 2021-03-16 14:10 ` Andrea 2021-03-16 15:15 ` [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) Andrew Poelstra 0 siblings, 1 reply; 29+ messages in thread From: Andrea @ 2021-03-16 14:10 UTC (permalink / raw) To: bitcoin-dev 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... ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) 2021-03-16 14:10 ` Andrea @ 2021-03-16 15:15 ` Andrew Poelstra 2021-03-17 4:24 ` ZmnSCPxj 0 siblings, 1 reply; 29+ messages in thread From: Andrew Poelstra @ 2021-03-16 15:15 UTC (permalink / raw) To: Andrea, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) 2021-03-16 15:15 ` [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) Andrew Poelstra @ 2021-03-17 4:24 ` ZmnSCPxj 2021-03-17 8:29 ` Andrea 0 siblings, 1 reply; 29+ messages in thread From: ZmnSCPxj @ 2021-03-17 4:24 UTC (permalink / raw) To: Andrew Poelstra, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) 2021-03-17 4:24 ` ZmnSCPxj @ 2021-03-17 8:29 ` Andrea 2021-03-20 16:31 ` Andrea Barontini 0 siblings, 1 reply; 29+ messages in thread From: Andrea @ 2021-03-17 8:29 UTC (permalink / raw) To: ZmnSCPxj, Andrew Poelstra, Bitcoin Protocol Discussion 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 > ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) 2021-03-17 8:29 ` Andrea @ 2021-03-20 16:31 ` Andrea Barontini 0 siblings, 0 replies; 29+ messages in thread From: Andrea Barontini @ 2021-03-20 16:31 UTC (permalink / raw) To: ZmnSCPxj, Andrew Poelstra, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 21:48 [bitcoin-dev] PSA: Taproot loss of quantum protections Luke Dashjr 2021-03-15 22:05 ` Matt Corallo 2021-03-15 23:12 ` Andrew Poelstra @ 2021-03-16 0:24 ` David A. Harding 2021-04-05 0:27 ` Lloyd Fournier 2021-03-22 14:24 ` Erik Aronesty 3 siblings, 1 reply; 29+ messages in thread From: David A. Harding @ 2021-03-16 0:24 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-16 0:24 ` [bitcoin-dev] PSA: Taproot loss of quantum protections David A. Harding @ 2021-04-05 0:27 ` Lloyd Fournier 2021-04-16 3:47 ` ZmnSCPxj 0 siblings, 1 reply; 29+ messages in thread From: Lloyd Fournier @ 2021-04-05 0:27 UTC (permalink / raw) To: David A. Harding, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-04-05 0:27 ` Lloyd Fournier @ 2021-04-16 3:47 ` ZmnSCPxj 2021-04-16 5:00 ` Lloyd Fournier 0 siblings, 1 reply; 29+ messages in thread From: ZmnSCPxj @ 2021-04-16 3:47 UTC (permalink / raw) To: Lloyd Fournier, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-04-16 3:47 ` ZmnSCPxj @ 2021-04-16 5:00 ` Lloyd Fournier 0 siblings, 0 replies; 29+ messages in thread From: Lloyd Fournier @ 2021-04-16 5:00 UTC (permalink / raw) To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-15 21:48 [bitcoin-dev] PSA: Taproot loss of quantum protections Luke Dashjr ` (2 preceding siblings ...) 2021-03-16 0:24 ` [bitcoin-dev] PSA: Taproot loss of quantum protections David A. Harding @ 2021-03-22 14:24 ` Erik Aronesty 2021-03-23 9:36 ` Martin Schwarz ` (2 more replies) 3 siblings, 3 replies; 29+ messages in thread From: Erik Aronesty @ 2021-03-22 14:24 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-22 14:24 ` Erik Aronesty @ 2021-03-23 9:36 ` Martin Schwarz 2021-03-23 10:50 ` Tim Ruffing 2021-08-12 22:08 ` Erik Aronesty 2 siblings, 0 replies; 29+ messages in thread From: Martin Schwarz @ 2021-03-23 9:36 UTC (permalink / raw) To: Erik Aronesty, Bitcoin Protocol Discussion [-- 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 --] ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-22 14:24 ` Erik Aronesty 2021-03-23 9:36 ` Martin Schwarz @ 2021-03-23 10:50 ` Tim Ruffing 2021-08-12 22:08 ` Erik Aronesty 2 siblings, 0 replies; 29+ messages in thread From: Tim Ruffing @ 2021-03-23 10:50 UTC (permalink / raw) To: Bitcoin Protocol Discussion 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). ^ permalink raw reply [flat|nested] 29+ messages in thread
* Re: [bitcoin-dev] PSA: Taproot loss of quantum protections 2021-03-22 14:24 ` Erik Aronesty 2021-03-23 9:36 ` Martin Schwarz 2021-03-23 10:50 ` Tim Ruffing @ 2021-08-12 22:08 ` Erik Aronesty 2 siblings, 0 replies; 29+ messages in thread From: Erik Aronesty @ 2021-08-12 22:08 UTC (permalink / raw) To: Luke Dashjr, Bitcoin Protocol Discussion 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 ^ permalink raw reply [flat|nested] 29+ messages in thread
end of thread, other threads:[~2021-08-12 22:08 UTC | newest] Thread overview: 29+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2021-03-15 21:48 [bitcoin-dev] PSA: Taproot loss of quantum protections Luke Dashjr 2021-03-15 22:05 ` Matt Corallo 2021-03-15 22:30 ` Robert Spigler 2021-03-15 22:40 ` Jeremy 2021-03-15 22:48 ` Matt Corallo 2021-03-15 23:01 ` Karl-Johan Alm 2021-03-15 23:19 ` Matt Corallo 2021-03-15 23:46 ` Lloyd Fournier 2021-03-16 0:50 ` Anthony Towns 2021-03-16 2:38 ` ZmnSCPxj 2021-03-16 3:44 ` Luke Dashjr 2021-03-16 13:28 ` Andrew Poelstra 2021-03-16 17:25 ` Matt Corallo 2021-03-17 1:23 ` Ryan Grant 2021-03-17 11:56 ` Eoin McQuinn 2021-03-15 23:12 ` Andrew Poelstra 2021-03-16 14:10 ` Andrea 2021-03-16 15:15 ` [bitcoin-dev] Provisions (was: PSA: Taproot loss of quantum protections) Andrew Poelstra 2021-03-17 4:24 ` ZmnSCPxj 2021-03-17 8:29 ` Andrea 2021-03-20 16:31 ` Andrea Barontini 2021-03-16 0:24 ` [bitcoin-dev] PSA: Taproot loss of quantum protections David A. Harding 2021-04-05 0:27 ` Lloyd Fournier 2021-04-16 3:47 ` ZmnSCPxj 2021-04-16 5:00 ` Lloyd Fournier 2021-03-22 14:24 ` Erik Aronesty 2021-03-23 9:36 ` Martin Schwarz 2021-03-23 10:50 ` Tim Ruffing 2021-08-12 22:08 ` Erik Aronesty
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox