Date: Mon, 10 Feb 2020 10:20:11 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20200210002011.lelhcdmjejmoh6xv@erisian.com.au>
References: <CABaSBaxgdfeyPrnaJD+Gs-5agV4sX+b66ZA6AfkjiHvuE0JSXA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CABaSBaxgdfeyPrnaJD+Gs-5agV4sX+b66ZA6AfkjiHvuE0JSXA@mail.gmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
Subject: Re: [bitcoin-dev] Taproot (and graftroot) complexity
Precedence: list

On Sun, Feb 09, 2020 at 02:19:55PM -0600, Bryan Bishop via bitcoin-dev wrote:
> However, after
> our review, we're left perplexed about the development of Taproot (and
> Graftroot, to a lesser extent).

I think the main cause of the perplexity is not seeing the benefit of
taproot. 

For me, the simplest benefit is that taproot lets everyone's wallet change
from "if you lose this key, your funds are gone" to "if you lose this key,
you'll have to recover 3 of your 5 backup keys that you sent to trusted
friends, and pay a little more, but you won't have lost your funds". That
won't cost you *anything* beyond upgrading your wallet sotware/hardware;
if you never lose your main key, it doesn't cost you any more, but if
you do, you now have a new recovery option (or many recovery options).

Note that doing graftroot isn't proposed as it requires non-interactive
half-signature aggregation to be comparably efficient, and the crypto
hasn't been worked out for that -- or at least, the maths hasn't been
properly written up for criticism. (If you don't care about efficiency,
you can do a poor man's graftroot with pre-signed transactions and CPFP)

More detailed responses below. Kinda long.

> In essence, Taproot is fundamentally the same as doing
> https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and Schnorr
> signatures separately.
> 
> Suppose a MAST for {a,b,c,d,e,f,g,h} spending conditions it looks something
> like this:
> 
>       /\
>      /  \
>     /    \
>    /      \
>   /\      /\
>  /  \    /  \
> /\  /\  /\  /\
> a b c d e f g h
> 
> If we want this to be functionally equivalent to Taproot, we add a new path:
> 
>        /\
>       /\ {<pk> schnorr_checksig}
>      /  \
>     /    \
>    /      \
>   /\      /\
>  /  \    /  \
> /\  /\  /\  /\
> a b c d e f g h

There's a bit more subtlety to the difference between a merkle branch
and a taproot alternative. In particular, imagine you've got three
alternatives, one of which has 60% odds of being taken, and the other
two have 20% odds each. You'd construct a merkle tree:

    /\
   a /\
    b  c

And would reveal:

  60%: a [#(b,c)]
  20%: b [#a, #c]
  20%: c [#a, #b]

So your overhead would be 32B 60% of the time and 64B 40% of the time,
or an expected overhead of 44.8 bytes.

With taproot, you construct a tree of much the same shape, but 60% of
the time you no longer have to reveal anything about the path not taken:

  60%: a-tweaked
  20%: b [a, #c]
  20%: c [a, #b]

So your overhead is 0B 60% of the time, and 65B 40% of the time, for an
expected overhead of 26B.

That math only works out as an improvement if your common case really
is (or can be made to be) a simple key path spend, though.

You can generalise taproot and combine it with a merkle tree arbitrarily,
with the end result being that using a merkle branch means you can
choose either the left or right sub-tree for a cost of 32B, while a
taproot branch lets you choose the left *leaf* for free, or a right
sub-tree for (essentially) 64B. So for equally likely branches you'd
want to use the merkle split, while if there's some particular outcome
that's overwhelmingly likely, with others just there for emergencies,
then a taproot-style alternative will be better. See:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-October/016461.html

for slightly more detailed background.

Ultimately, I think we can do this better, so that you could choose
whether to make the free "taproot" path be a key or a script, or to use
the taproot method to make other likely leaves cheaper than unlikely
ones, rather than just having that benefit available for the most likely
leaf.

But I also think that's a lot of work, much of which will overlap with
the work to get cross-input signature aggregation working, so fwiw,
my view that the current taproot feature set is a good midway point to
draw a line, and get stuff out and released. This overall approach was
discussed quite a while ago:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/015951.html

> However, if we do the same script via taproot, we now need to provide the base
> public key (33 bytes) as well as the root hash (32 bytes) and path and then the
> actual scripts. 

You need to provide the internal public key, the actual script and the
path back; the root hash is easily calculated from the script and the
path, and then verified by ECC math against the scriptPubKey and the
internal public key.

>       /\
>      /  \
>     /    \
>    /      \
>   /\      /\
>  /  \    /  \
> /\  /\  /\  /\
> a b c d e f/\ {<pk> schnorr_checksig}
>           g  h
>
> We could argue that this is more private than Taproot, because we don't
> distinguish between the Schnorr key case and other cases by default, so chain
> analyzers can't tell if the signature came from the Taproot case or from one of
> the Script paths.

In that example there is no taproot case -- you reveal the existance of
other paths no matter which leaf you make use of. In particular, the "pk
schnorr_checksig" alternative now has 96B of additional overhead (#gh,
#ef, #abcd).

> This
> allows you to not completely fracture the anonymity set between people who want
> plain Schnorr and people who want MAST 
> (at least until they go to spend).

The benefit of taproot is that often you can preserve the anonymity set
even after you spend.

> Overall, we are left with concerns both about the merit of doing Taproot
> versus alternatives, as well as the process through which we got to be here.
> 1) Is Taproot actually more private than bare MAST and Schnorr separately? What
> are the actual anonymity set benefits compared to doing the separately?

Yes, presuming single-pubkey-single-signature remains a common
authorisation pattern.

> 2) Is Taproot actually cheaper than bare MAST and Schnorr separately? What
> evidence do we have that the assumption it will be more common to use Taproot
> with a key will outweigh Script cases?

Taproot with a key is about as cheap as it gets -- you've got a 35 byte
scriptPubKey and 66 bytes of witness data.

It's then 33 bytes of witness data more expensive to use a script, which
presumably will make it more likely that people use the simple key path.

At the time you create a utxo, provided you don't reuse keys, all taproot
spends are indistinguishable. At the time you spend a taproot utxo,
you can distinguish:

 - spent via key path
 - spent via script path, internal key not known
 - spent via script path, internal key known NUMS point

but there's no fee rate advantage between reusing a NUMS point and
generating a fresh NUMS point (via NUMS + rand*G), so the third case is
avoidable.

Looking at blocks 616650 to 616700, I see outputs of:

     738  0.3% "pubkey"
    2091  0.8% "witness_v0_scripthash"
   42749 16.8% "witness_v0_keyhash"
  102962 40.4% "pubkeyhash"
  106441 41.7% "scripthash"

So for plain segwit, over 95% of outputs are plain key; and overall,
over 57.5% of outputs are plain key/signature -- that's not counting
however many p2sh-encoded p2wpkh there are, because they'll just look
like pubkeyhash until they're spent.

> 3) Is Taproot riskier than bare MAST and Schnorr separately given the new
> crypto? 

I don't think so; most of the risk for either of those is in getting
the details right.

> How well reviewed is the actual crypto parts? 

That's pretty hard to evaluate if you can't review the crypto parts
yourself, but some resources are:

https://github.com/bitcoin-core/secp256k1/pull/558
https://github.com/apoelstra/taproot
https://github.com/ajtowns/taproot-review

Most of the complicated crypto parts are at the application layer: muSig,
threshold signatures, adaptor signatures, scriptless scripts, etc.

> None of us personally feel
> comfortable reviewing the crypto in Schnorr -- what's the set of people who
> have
> thoroughly reviewed the crypto and aren't just ACKing because they trust other
> developers to have looked at it close enough?

That... sounds like it's asking for a group of other developers that
have looked at it close enough for you to trust?

> 4) Design wise, couldn't we forego the NUMS point requirement and be able to
> check if it's a hash root directly?

That would decrease the anonymity set by a lot, make the code a bit
more complicated, and only end up saving 8 vbytes.

> 5) Is the development model of trying to jam a bunch of features into Bitcoin
> all at once good for Bitcoin development? Would we be better off if we embraced
> incremental improvements that can work together (e.g., MAST and then Schnorr)?

IMO, the driving force for bundling these changes together is the
advantages of taproot -- that is:

 - you can have either a simple public-key and signature to authorise
   a spend, or you can have a script, and decide which to use when
   you spend
 - using the key path comes at no cost compared to not using taproot
 - adding a script path comes at no cost if you don't end up using it
 - if you can interactively verify the script conditions off-chain,
   you can always use the key path

The latter of those means we want schnorr so that the key path can be
multisig, and using schnorr means that we can use scriptless scripts /
adaptor signatures for things like lightning making the key path more
common.

You can't do taproot cheaply with segwit v0 -- you'd have to use p2wsh
and then reveal something like "<point> OP_TAPROOT_VERIFY DROP DROP 1"
as the script, and then have either a signature or the script and its
witness data encoded as the arguments to that script, which is ugly,
but more importantly requires an extra 37 odd byte reveal of the point
every time.

So that leads to doing segwit v1 -- as otherwise you'd lose the
malleability protection segwit brought, or you'd have to reimplement
segwit to allow a top level "OP_TAPROOTVERIFY" to use witness data.

If you're doing segwit v1, you might as well make it so script is
more upgradable -- otherwise as soon as you want to upgrade script
further you'll end up having to jump to segwit v2. That brings in the
generalisation of "p2sh" that allows different scripts to satisfy a script
hash via a merkle path, the leaf version, OP_SUCCESS and the CHECKSIG*
changes, and that pretty much covers everything that's in bips 340-342.

> SUBJECT: An Alternative Deployment Path for Taproot Technologies
> 1) A separate soft-fork for Merkle Branch Witnesses based on Taproot;

It's not clear to me what "Merkle Branch Witnesses" are. Google comes up
with:

  https://notes.ethereum.org/@vbuterin/rkhCgQteN
  https://www.btc-way.com/?p=8153

which don't go into specifics. There's different "MAST" proposals in
Bitcoin, such as bip 116+117 vs bip 114 -- bip 114 and taproot's bip 341
have a similar approach; bip 116 on the other hand gives a merkle verify
opcode, and 117 provides a tail-call semantic that combine allow a
script to produce MAST semantics; though in a more programmable way --
if you had a CAT opcode you could have two MASTs in a single script,
combine their result, and then execute it, for instance.

> 2) A separate soft-fork for Schnorr Signatures
> 3) A separate follow up soft-fork which enables Taproot and Graftroot

In order to do something like bip 341's merkle script paths, you'd need
a new segwit version, where the scriptpubkey would be the merkle root
of scripts. If not combined with Schnorr signatures, you'd need to
provide leaf versions or change the way CHECKSIG works from how it works
now in order to upgrade to Schnorr later.

But if we're designing soft-fork 1 in a particular way because we already
know we want to make particular changes from soft-fork 2, I don't think
it makes much sense to split them up.

Having done both of those, in order to do taproot, you'd need another
new segwit version, so that the scriptpubkey could be a taproot point,
but could otherwise reuse the script path.

Obviously I think taproot's desirable, and (roughly) ready to go now,
so I don't see any reason to split that up, particularly when doing so
would use up an additional segwit version.

> users only have to use Schnorr signing if they want to, and can otherwise
> continue to use ECDSA. 

Updating to schnorr signing makes it easier to validate the blockchain
(batch validation gives a modest speedup once there are many schnorr
signatures), and updating to the signature hashing algorithms described
in bip 341/342 has benefits for making hardware wallets more secure.
While it's obviously fine for people to not upgrade; upgrading sooner
rather than later does have systemic benefits.

Cheers,
aj