From: Luke Dashjr <luke@dashjr.org>
To: Matt Corallo <lf-lists@mattcorallo.com>,
 ZmnSCPxj <ZmnSCPxj@protonmail.com>,
 "Karl-Johan Alm" <karljohan-alm@garage.co.jp>,
 Andrew Poelstra <apoelstra@wpsoftware.net>
Date: Tue, 16 Mar 2021 03:44:25 +0000
User-Agent: KMail/1.9.10
References: <202103152148.15477.luke@dashjr.org>
 <a88cd471-fdc9-de35-86cd-595b387249c8@mattcorallo.com>
In-Reply-To: <a88cd471-fdc9-de35-86cd-595b387249c8@mattcorallo.com>
MIME-Version: 1.0
Content-Type: Text/Plain;
  charset="utf-8"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
Message-Id: <202103160344.26299.luke@dashjr.org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections
Precedence: list

(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