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

From: Andrew Poelstra <apoelstra@wpsoftware•net>
To: Luke Dashjr <luke@dashjr•org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] PSA: Taproot loss of quantum protections
Date: Tue, 16 Mar 2021 13:28:34 +0000	[thread overview]
Message-ID: <YFCygncy/hyxFRWz@camus> (raw)
In-Reply-To: <202103160344.26299.luke@dashjr.org>

[-- 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 --]