Subject: Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)

From: "David A. Harding" <[email-masked]>
Date: Sun, 9 Feb 2020 18:15:54 -0600

On Sun, Feb 09, 2020 at 02:47:29PM -0600, Anon via Bryan Bishop via bitcoin-dev wrote:
> 1) Is Taproot actually more private than bare MAST and Schnorr separately?

Yes.

> What are the actual anonymity set benefits compared to doing the separately?

When schnorr and taproot are done together, all of the following
transaction types can be part of the same set:

    - single-sig spends (similar to current use of P2PKH and P2WPKH)

    - n-of-n spends with musig or equivalent (similar to current use of
      P2SH and P2WSH 2-of-2 multisig without special features as used by
      Blockstream Green and LN mutual closes)

    - k-of-n (for low values of n) using the most common k signers
      (similar to BitGo-style 2-of-3 where the keys involved are
      alice_hot, alice_cold, and bob_hot and almost all transactions are
      expected to be signed by {alice_hot, bob_hot}; that common case
      can be the key-path spend and the alternatives {alice_hot,
      alice_cold} and {alice_cold, bob_hot} can be script-path spends)

    - contract protocols that can sometimes result in all parties
      agreeing on an outcome (similar to LN mutual closes, cross-chain
      atomic swaps, and same-chain coinswaps)

The four cases above represent an overwhelming percentage of the spends
seen on the block chain today and throughout Bitcoin's entire history to
date, so optimizing to include them in the anonymity set presents a huge
benefit.

> 2) Is Taproot actually cheaper than bare MAST and Schnorr separately? 

Earlier in y'alls email, you claim that the difference between the two
approaches for a particular example is 67 bytes.  I haven't checked that
calculation, but it seems you're talking entirely about bytes that could
appear in the witness data and so would only represent 16.75 vbytes.
Compare that to the size of the other elements which would need to be
part of a typical input:

- (36 vbytes) outpoint
- (1) scriptSig compactSize uint
- (4) nSequence 
- (16.25) schnorr signature (includes size byte)

That's 57.25 vbytes exclusive of your example data or 74.00 vbytes
inclusive.  That means the overhead you're concerned about adds only
about 23% to the size of the input (or 30% on an exclusive basis).
That's definitely worth considering optimizations for, but I'm
personally ok with requiring users of advanced scripts (who can't manage
to produce mutual closes) pay an extra 23% for their inputs in order to
allow the creation of the large anonymity set described above for all
the other cases.

If, subsequent to deployment, large numbers of users do end up using
taproot script-path spends and we want to make things more fair, we can
even out the weighting, perhaps by simply increasing the weight of
key-path spends by 16.75 vbytes (though that would, of course,
proportionally lower the capacity of the block chain).  As mentioned in
a separate email by Matt Corallo, it seems worthwhile to optimize for
the case where script-path spenders are encouraged to look for
mutually-agreed contract resolutions in order to both minimize block
chain use and increase the size of the anonymity set.

> What evidence do we have that the assumption it will be more common to
> use Taproot with a key will outweigh Script cases?

The evidence that current users of single-sig, n-of-n, and k-of-n (for
small n) with a default k-set, and mutual-agreed contract protocol
outcomes vastly outweigh all other transaction inputs today and for all
of Bitcoin's history to date.

-Dave