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

From: Jeremy <jlrubin@mit•edu>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)
Date: Fri, 14 Feb 2020 12:07:15 -0800	[thread overview]
Message-ID: <CAD5xwhh=71XDAcSCJL9AQhZOriWmdGq4C5xT34K5wjR_g7FDfA@mail.gmail.com> (raw)
In-Reply-To: <d42234f4-411c-40a6-dcb8-b9408c21ef16@gmail.com>

[-- Attachment #1: Type: text/plain, Size: 20795 bytes --]

Dave,

I think your point:

*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) *

Is the same if Schnorr + Merkle Branch without Taproot optimization, unless
I'm missing something in one of the cases? I guess there's a distinction on
"can" v.s. "are likely"?

Jonas,

That's a really interesting point about K-N systems making the most likely
K-K the taproot key. (For the uninitiated, MuSig can do N-of-N aggregation
non-interactively, but K-of-N requires interaction). I think this works
with small (N choose K), but as (N choose K) increases it seems the
probability of picking the correct one goes down?

I guess the critical question is if cases where there's not some timelock
will be mandatory across all signing paths.

cheers,

jeremy

--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

On Mon, Feb 10, 2020 at 9:16 AM Jonas Nick via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> wrote:

> I agree with most of the comments so far, but the group brings up an often
> overlooked point with respect to the privacy benefits of taproot. In the
> extreme
> case, if there would be no policies that have both a key and a script spend
> path, then taproot does not improve anonymity sets compared to the "Taproot
> Public NUMS Optimization" proposal (which saves 8 vbytes in a
> script-spend). (*)
>
> In fact, the cases where scripts would have to be used given usage of
> Bitcoin
> today are be rare because threshold policies, their conjunctions and
> disjunctions can be expressed with a single public key. Even if we
> disregard
> speculation that timelocks, ANYPREVOUT/NOINPUT and other interesting
> scripts
> will be used in the future (which can be added through the leaf or key
> versions
> without affecting key-spend anonymity sets), not all of today's
> applications are
> able to be represented single public keys because there are applications
> that
> can not deal with interactive key setups or interactive signing. For
> applications where this is possible it will be a gradual change because of
> the
> engineering challenges involved. For example, k-of-n threshold policies
> could
> have the most likely k-of-k in the taproot output key and other k-of-k in
> the
> leaves, instead of going for a k-of-n taproot output key immediately.
>
> Given that anonymity sets in Bitcoin are permanent and software tends to be
> deployed longer than anyone would expect at the time of deployment,
> realistically Taproot is superior to the "Public NUMS Optimization" and "An
> Alternative Deployment Path".
>
> (*) One could argue that the little plausible deniability gained by a very
> small
> probability of the change of a script-spend being a key-spend and vice
> versa is
> significantly better than no probability at all.
>
> On 2/9/20 8:47 PM, Bryan Bishop via bitcoin-dev wrote:
> > Apologies for my previous attempt at relaying the message- it looks like
> > the emails got mangled on the archive. I am re-sending them in this
> > combined email with what I hope will be better formatting. Again this is
> > from some nym that had trouble posting to this mailing list; I didn't see
> > any emails in the queue so I couldn't help to publish this sooner.
> >
> > SUBJECT: Taproot (and Graftroot) Complexity
> >
> > This email is the first of a collection of sentiments from a group of
> > developers who in aggregate prefer to remain anonymous. These emails have
> > been sent under a pseudonym so as to keep the focus of discussion on the
> > merits of the technical issues, rather than miring the discussion in
> > personal politics.  Our goal isn't to cause a schism, but rather to help
> > figure out what the path forward is with Taproot. To that end, we:
> >
> > 1) Discuss the merits of Taproot's design versus simpler alternatives
> (see
> > thread subject, "Taproot (and Graftroot) Complexity").
> >
> > 2) Propose an alternative path to deploying the technologies described in
> > BIP-340, BIP-341, and BIP-342 (see thread subject, "An Alternative
> > Deployment Path for Taproot Technologies").
> >
> > 3) Suggest a modification to Taproot to reduce some of the overhead (see
> > thread subject, "Taproot Public NUMS Optimization").
> >
> > Now that the BIP has moved to draft we felt that now was the time to
> > prioritize review to make sure it was an acceptable change for our
> > activities. As a group, we're excited about the totality of what Taproot
> > has to offer. However, after our review, we're left perplexed about the
> > development of Taproot (and Graftroot, to a lesser extent).
> >
> > We also want to convey that we have nothing but respect for the
> developers
> > and community who have poured their heart and soul into preparing
> Taproot.
> > Self evidently, it is an impressive synthesis of ideas. We believe that
> the
> > highest form of respect to pay such a synthesis of ideas is a detailed
> and
> > critical review, as it's pertinent to closely consider changes to
> Bitcoin.
> >
> >
> > In essence, Taproot is fundamentally the same as doing
> > https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and
> Schnorr
> > signatures separately.
> >
> > The main reason for putting them together -- as mentioned in the BIP --
> is
> > a gain in efficiency. But this efficiency pre-supposes a specific use
> case
> > and probability distribution of use cases.
> >
> > Compare:
> >
> > 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
> >
> > Now, to spend from this MBV you have to reveal 32 bytes on the stack for
> > the not taken branch, and 35 bytes for the <pk> schnorr_checksig (1 byte
> > push, 33 bytes PK, 1 byte checksig).
> >
> > This is 67 bytes more than Taproot would require for the same spending
> > condition.
> >
> > However, suppose we wanted to use one of the script paths instead. We
> still
> > need to have one extra hash for the {<pk> schnorr_checksig} (depending on
> > if we put the key in this position or not--see below). But now we can
> spend
> > with just a logarithmic control program path.
> >
> > 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. With the need for 2 push bytes, this ends up
> being
> > back at 67 bytes extra.
> >
> > Is Taproot just a probability assumption about the frequency and
> likelihood
> > of the signature case over the script case? Is this a good assumption?
> The
> > BIP only goes as far as to claim that the advantage is apparent if the
> > outputs *could be spent* as an N of N, but doesn't make representations
> > about how likely that N of N case would be in practice compared to the
> > script paths. Perhaps among use cases, more than half of the ones we
> expect
> > people to be doing could be spent as an N of N. But how frequently would
> > that path get used? Further, while the *use cases* might skew toward
> things
> > with N of N opt-out, we might end up in a power law case where it's the
> one
> > case that doesn't use an N of N opt out at all (or at a de minimis level)
> > that becomes very popular, thereby making Taproot more costly then
> > beneficial.
> >
> > Further, if you don't want to use a Taproot top-level key (e.g., you need
> > to be able to audit that no one can spend outside of one of the script
> > conditions), then you need to use a NUMS (nothing up my sleeve) point.
> This
> > forces users who don't want Taproot to pay the expense, when if they just
> > had a MAST based witness type they would be cheaper. So if this use case
> is
> > at all common, Taproot leaves them worse off in terms of fees. Given that
> > script paths are usually done in the case where there is some contested
> > close, it's actually in the interest of protocol developers that the
> > contested script path be as efficient as possible so that the fees paid
> > maximally increase the feerate. We think this can be fixed simply in
> > Taproot though, as noted below.
> >
> >
> >
> > On privacy, we're also a bit confused as to the goal of Taproot over MAST
> > and Schnorr. Earlier, we presented a design with MAST which is very close
> > to Taproot.  However, it'd also be possible to just add {<pk>
> > schnorr_checksig} to the set {a,b,c,d,e,f,g,h}, shuffle them, and compute
> > some MAST structure (perhaps probability encoded) on them. This has the
> > effect of not having much additional fees for adding the extra Schnorr
> path
> > at redeem time (only 1 extra branch on 2/8 script paths), e.g.
> >
> >
> >       /\
> >      /  \
> >     /    \
> >    /      \
> >   /\      /\
> >  /  \    /  \
> > /\  /\  /\  /\
> > 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. There's also no NUMS point required, which
> > means chain analyzers can't tell when you spend that there was no top
> level
> > key if the NUMS point is not per-output indistinguishable. By using a
> > semi-randomized MAST structure, chain analyzers also can't tell exactly
> how
> > big your spend condition MAST was. In particular, you care more about
> > privacy when you are contesting a close of a channel or other script path
> > because then the miners could be more likely to extract a rent from you
> as
> > "ransom" for properly closing your channel (or in other words, in a
> > contested close the value of the closing transaction is larger than
> usual).
> >
> > It would also be possible to do something really simple which is to allow
> > the witness type to be either a MAST hash OR a schnorr key (but not a
> > Taproot). 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). This fix can also be used in Taproot in place
> of a
> > NUMS point, to decrease extra fees. It's unclear if this plays negatively
> > with any future batch validation mechanism though, but the contextual
> > checks to exclude a witness program from the batch are relatively simple.
> > See thread subject, "Taproot Public NUMS Optimization".
> >
> > The considerations around Graftroot, a proposed delegation mechanism, is
> a
> > bit similar. Delegation is a mechanism by which a UTXO with script S can
> > sign a script R which can then be executed in addition to S without
> > requiring a transaction. This allows an output to monotonically and
> > dynamically increase the number of conditions under which it can be
> spent.
> > As noted by Pieter Wiulle here:
> >
> https://github.com/kanzure/diyhpluswiki/commit/a03f6567d714f8733b578de263a4b149441cd058
> > delegation was originally possible in Bitcoin, but got broken during an
> > emergency fork to split the scriptSig and scriptpubkey separation. Rather
> > than adding some fancy delegation mechanism in Bitcoin, why not just
> have a
> > P2SH-like semantic which allows a delegated script to be evaluated? See
> > BIP-117 https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki.
> > This way we aren't special casing where delegation can occur, and we can
> > allow taproot nested spending conditions (i.e., with timelocks) to
> generate
> > their own delegations. As I've seen Graftroot discussed thus far, it is
> as
> > a top-level witness program version like Taproot and non-recursive.
> Similar
> > to the above discussion, top-level is more efficient if you suspect that
> > delegation will be most likely occurring at the top level, but it's not
> > clear that's a good assumption as it may be common to want to allow
> > different scripts to delegate.
> >
> >
> > 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?
> >
> > 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?
> >
> > 3) Is Taproot riskier than bare MAST and Schnorr separately given the new
> > crypto? How well reviewed is the actual crypto parts? 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?
> >
> > 4) Design wise, couldn't we forego the NUMS point requirement and be able
> > to check if it's a hash root directly? This would encumber users who
> don't
> > need the key path a cheaper spend path. See thread subject, "Taproot
> Public
> > NUMS Optimization".
> >
> > 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)?  Although the BIP raises some points about anonymity sets
> > being why to do them all at once, it's not clear to me this argument
> holds
> > water (same goes for businesses not upgrading). If we can take things as
> > smaller steps, we are not only more secure, but we also have more time to
> > dedicate review to each change independently. We also end up co-mingling
> > changes that people end up accepting only because they want one and
> they're
> > bundled (e.g., MAST and Schnorr, MAST seems like a much less risky
> addition
> > versus Schnorr). See thread subject, "An Alternative Deployment Path for
> > Taproot Technologies".
> >
> >
> >
> >
> > Our provocation with this email is primarily that we think we should more
> > carefully consider the benefits of Taproot over simpler primitives that
> are
> > not only easier to review, but could have been made available much sooner
> > rather than waiting on putting everything all together for an unclear
> > aggregate benefit.
> >
> > We do think that most of the developers have been honest about the
> benefits
> > of Taproot, but that on closer look we feel the general ecosystem has
> > oversold Taproot as being the key enabler for a collection of techniques
> > that we could do with much simpler building blocks.
> >
> >
> > At the end of the day, we do not strongly advocate not deploying Taproot
> at
> > this point in the review cycle. We think the Taproot Public NUMS
> > Optimization may be a good idea, worth considering if it's not insecure,
> as
> > it cuts through the case where you would otherwise need a NUMS point.
> > Things like TapScript and its MAST mechanisms are well designed and offer
> > exciting new deployment paths, and would be something we would use even
> if
> > we opted for MAST instead of Taproot. However, we also believe it is our
> > duty to raise these concerns and suggestions, and we look forward to
> > listening to the responses of the community.
> >
> > Great thanks,
> >
> > The Group
> >
> > ----
> >
> > SUBJECT: An Alternative Deployment Path for Taproot Technologies
> >
> > This email is the second of a collection of sentiments from a group of
> > developers who in aggregate prefer to remain anonymous. These emails have
> > been sent under a pseudonym so as to keep the focus of discussion on the
> > merits of the technical issues, rather than miring the discussion in
> > personal politics. Our goal isn't to cause a schism, but rather to help
> > figure out what the path forward is with Taproot. To that end, we: [clip
> > repeat]
> >
> > As a follow up to our prior message, we propose a different path forward
> > for the Taproot family of changes:
> >
> > 1) A separate soft-fork for Merkle Branch Witnesses based on Taproot;
> >
> > 2) A separate soft-fork for Schnorr Signatures
> >
> > 3) A separate follow up soft-fork which enables Taproot and Graftroot
> >
> > We think that the first 2 forks can be offered at the same time or one
> at a
> > time.
> >
> > Taproot, as a follow up to changes 1 and 2, can be enabled as a soft-fork
> > on the existing semantics, but requiring a new witness version. With the
> > Public NUMS Optimization, wallets could upgrade by just changing one
> > version byte to be in the same anonymity set as Taproot.
> >
> > It's not clear to us that the time to prepare a BIP and implementation
> for
> > 1 and 2 at this point would be any less than the time to do Taproot as
> > currently proposed. However, we believe that such a deployment plan is a
> > reasonable option as it is more conservative, as Merkle Branch witnesses
> > are relatively simple and users only have to use Schnorr signing if they
> > want to, and can otherwise continue to use ECDSA. A further benefit of
> > waiting on 3 is that we get to collect real world protocol engineering
> > experience to see how frequently the Taproot frequency of use assumption
> > holds, and if it is worth doing or not.
> >
> >
> > Great thanks,
> >
> > The Group
> >
> >
> > ----
> >
> > SUBJECT: Taproot Public NUMS Optimization
> >
> > This email is the third of a collection of sentiments from a group of
> > developers who in aggregate prefer to remain anonymous. These emails have
> > been sent under a pseudonym so as to keep the focus of discussion on the
> > merits of the technical issues, rather than miring the discussion in
> > personal politics. Our goal isn't to cause a schism, but rather to help
> > figure out what the path forward is with Taproot. To that end, we:
> [clipped
> > again]
> >
> > We propose to modify Taproot's specification in BIP-341 by adding the
> rule:
> >
> > If there is one element on the witness stack:
> >
> > 1) Attempt hashing it to see if it's equal to  the witness program. The
> > first byte is the control byte for leaf versioning.
> >
> > 2) If it's not the witness program, and it's 65 bytes, try signature
> > validation
> >
> > If there is more than one element on the witness stack:
> >
> > If the control block is even, treat it as a non-Taproot MAST and get the
> > leaf version as the last byte of the script (so you can pop it off before
> > hashing).
> >
> >
> > If greater anonymity is required, a NUMS point can still be used in
> > Taproot, at the expense of the additional data. However, if NUMS points
> are
> > just a couple well known constants this could actually decrease privacy
> as
> > then the NUMS points could differ from application to application
> > fingerprinting wallets.  Instead, the NUMS point should only be used
> when a
> > single use nonce can be sent, so that NUMS cannot be distinguished from a
> > normal Taproot to a third party who doesn't know the setup (e.g., that
> the
> > NUMS is H(X) for known X).
> >
> >
> > Great thanks,
> >
> > The Group
> >
> >
> > _______________________________________________
> > 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: 27326 bytes --]