From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id C2497C0177 for ; Fri, 14 Feb 2020 20:07:33 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by fraxinus.osuosl.org (Postfix) with ESMTP id A6D4F86A6C for ; Fri, 14 Feb 2020 20:07:33 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from fraxinus.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id FJ2dVX1M8ZcC for ; Fri, 14 Feb 2020 20:07:30 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by fraxinus.osuosl.org (Postfix) with ESMTPS id DEF7886A63 for ; Fri, 14 Feb 2020 20:07:29 +0000 (UTC) Received: from mail-io1-f54.google.com (mail-io1-f54.google.com [209.85.166.54]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 01EK7RH4002011 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT) for ; Fri, 14 Feb 2020 15:07:28 -0500 Received: by mail-io1-f54.google.com with SMTP id d15so11892781iog.3 for ; Fri, 14 Feb 2020 12:07:28 -0800 (PST) X-Gm-Message-State: APjAAAU6HD98jRIfMzM/Vl2u6uhif+blwd6BmCSi1UOjC14BjURoiqMw i2/2iDn+eink3RKeQqBO2Ps+4ubIoTSl1C195UE= X-Google-Smtp-Source: APXvYqzvpOMoZWATvEXsa5ulVVhxeZ8rsbZgyC5K3SVYtJVku81yQ1DOoi9yGmqmomJWYR7JttazoGuxzej2xfMhqzw= X-Received: by 2002:a6b:6103:: with SMTP id v3mr3764072iob.49.1581710847192; Fri, 14 Feb 2020 12:07:27 -0800 (PST) MIME-Version: 1.0 References: In-Reply-To: From: Jeremy Date: Fri, 14 Feb 2020 12:07:15 -0800 X-Gmail-Original-Message-ID: Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="0000000000002f338d059e8ec18c" X-Mailman-Approved-At: Fri, 14 Feb 2020 20:13:29 +0000 Subject: Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed) X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 14 Feb 2020 20:07:33 -0000 --0000000000002f338d059e8ec18c Content-Type: text/plain; charset="UTF-8" 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 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: > > > > /\ > > /\ { 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 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 { 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 { > > 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/\ { 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 > --0000000000002f338d059e8ec18c Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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:
=C2=A0 =C2=A0 - single-sig spends (similar to current use of P2PKH and P2WP= KH)
=C2=A0 =C2=A0 - n-of-n spends with musig or equivalent (similar to current = use of
=C2=A0 =C2=A0 =C2=A0 P2SH and P2WSH 2-of-2 multisig without special feature= s as used by
=C2=A0 =C2=A0 =C2=A0 Blockstream Green and LN mutual closes)
=C2=A0 =C2=A0 - k-of-n (for low values of n) using the most common k signer= s
=C2=A0 =C2=A0 =C2=A0 (similar to BitGo-style 2-of-3 where the keys involved= are
=C2=A0 =C2=A0 =C2=A0 alice_hot, alice_cold, and bob_hot and almost all tran= sactions are
=C2=A0 =C2=A0 =C2=A0 expected to be signed by {alice_hot, bob_hot}; that co= mmon case
=C2=A0 =C2=A0 =C2=A0 can be the key-path spend and the alternatives {alice_= hot,
=C2=A0 =C2=A0 =C2=A0 alice_cold} and {alice_cold, bob_hot} can be script-pa= th spends)
=C2=A0 =C2=A0 - contract protocols that can sometimes result in all parties=
=C2=A0 =C2=A0 =C2=A0 agreeing on an outcome (similar to LN mutual closes, c= ross-chain
=C2=A0 =C2=A0 =C2=A0 atomic swaps, and same-chain coinswaps)
=
= Is the same if Schnorr + Merkle Branch without Tap= root optimization, unless I'm missing something in one of the cases? I = guess there's a distinction on "can" v.s. "are likely&qu= ot;?


Jonas,

That's a really interesting point about K-N systems making th= e 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 quest= ion is if cases where there's not some timelock will be mandatory acros= s all signing paths.


cheers,

jeremy
=
--
@JeremyRubin


On Mon, Feb 10, 2020 at 9:16 AM Jonas Nick via bitcoin-dev = <bitcoin-dev@li= sts.linuxfoundation.org> wrote:
I agree with most of the comments so far, but the gr= oup brings up an often
overlooked point with respect to the privacy benefits of taproot. In the ex= treme
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 "Ta= proot
Public NUMS Optimization" proposal (which saves 8 vbytes in a script-s= pend). (*)

In fact, the cases where scripts would have to be used given usage of Bitco= in
today are be rare because threshold policies, their conjunctions and
disjunctions can be expressed with a single public key. Even if we disregar= d
speculation that timelocks, ANYPREVOUT/NOINPUT and other interesting script= s
will be used in the future (which can be added through the leaf or key vers= ions
without affecting key-spend anonymity sets), not all of today's applica= tions are
able to be represented single public keys because there are applications th= at
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 cou= ld
have the most likely k-of-k in the taproot output key and other k-of-k in t= he
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&quo= t; 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 vers= a 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 li= ke
> 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= 9;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<= br> > developers who in aggregate prefer to remain anonymous. These emails h= ave
> been sent under a pseudonym so as to keep the focus of discussion on t= he
> merits of the technical issues, rather than miring the discussion in > personal politics.=C2=A0 Our goal isn't to cause a schism, but rat= her 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 alternati= ves (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 Alternativ= e
> Deployment Path for Taproot Technologies").
>
> 3) Suggest a modification to Taproot to reduce some of the overhead (s= ee
> 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 T= aproot
> has to offer. However, after our review, we're left perplexed abou= t the
> development of Taproot (and Graftroot, to a lesser extent).
>
> We also want to convey that we have nothing but respect for the develo= pers
> and community who have poured their heart and soul into preparing Tapr= oot.
> Self evidently, it is an impressive synthesis of ideas. We believe tha= t 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/b= lob/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 some= thing
> like this:
>
>
>=C2=A0 =C2=A0 =C2=A0 =C2=A0/\
>=C2=A0 =C2=A0 =C2=A0 /=C2=A0 \
>=C2=A0 =C2=A0 =C2=A0/=C2=A0 =C2=A0 \
>=C2=A0 =C2=A0 /=C2=A0 =C2=A0 =C2=A0 \
>=C2=A0 =C2=A0/\=C2=A0 =C2=A0 =C2=A0 /\
>=C2=A0 /=C2=A0 \=C2=A0 =C2=A0 /=C2=A0 \
> /\=C2=A0 /\=C2=A0 /\=C2=A0 /\
> a b c d e f g h
>
> If we want this to be functionally equivalent to Taproot, we add a new= path:
>
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 /\
>=C2=A0 =C2=A0 =C2=A0 =C2=A0/\ {<pk> schnorr_checksig}
>=C2=A0 =C2=A0 =C2=A0 /=C2=A0 \
>=C2=A0 =C2=A0 =C2=A0/=C2=A0 =C2=A0 \
>=C2=A0 =C2=A0 /=C2=A0 =C2=A0 =C2=A0 \
>=C2=A0 =C2=A0/\=C2=A0 =C2=A0 =C2=A0 /\
>=C2=A0 /=C2=A0 \=C2=A0 =C2=A0 /=C2=A0 \
> /\=C2=A0 /\=C2=A0 /\=C2=A0 /\
> a b c d e f g h
>
> Now, to spend from this MBV you have to reveal 32 bytes on the stack f= or
> 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} (dep= ending 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 pat= h 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 likel= ihood
> of the signature case over the script case? Is this a good assumption?= =C2=A0 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 representa= tions
> 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 e= xpect
> people to be doing could be spent as an N of N. But how frequently wou= ld
> that path get used? Further, while the *use cases* might skew toward t= hings
> 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., y= ou 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 th= ey just
> had a MAST based witness type they would be cheaper. So if this use ca= se is
> at all common, Taproot leaves them worse off in terms of fees. Given t= hat
> script paths are usually done in the case where there is some conteste= d
> close, it's actually in the interest of protocol developers that t= he
> contested script path be as efficient as possible so that the fees pai= d
> 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 ov= er MAST
> and Schnorr. Earlier, we presented a design with MAST which is very cl= ose
> to Taproot.=C2=A0 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 comp= ute
> some MAST structure (perhaps probability encoded) on them. This has th= e
> 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.
>
>
>=C2=A0 =C2=A0 =C2=A0 =C2=A0/\
>=C2=A0 =C2=A0 =C2=A0 /=C2=A0 \
>=C2=A0 =C2=A0 =C2=A0/=C2=A0 =C2=A0 \
>=C2=A0 =C2=A0 /=C2=A0 =C2=A0 =C2=A0 \
>=C2=A0 =C2=A0/\=C2=A0 =C2=A0 =C2=A0 /\
>=C2=A0 /=C2=A0 \=C2=A0 =C2=A0 /=C2=A0 \
> /\=C2=A0 /\=C2=A0 /\=C2=A0 /\
> a b c d e f/\ {<pk> schnorr_checksig}
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0g=C2=A0 h
>
> We could argue that this is more private than Taproot, because we don&= #39;t
> distinguish between the Schnorr key case and other cases by default, s= o
> 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<= br> > semi-randomized MAST structure, chain analyzers also can't tell ex= actly how
> big your spend condition MAST was. In particular, you care more about<= br> > privacy when you are contesting a close of a channel or other script p= ath
> because then the miners could be more likely to extract a rent from yo= u as
> "ransom" for properly closing your channel (or in other word= s, in a
> contested close the value of the closing transaction is larger than us= ual).
>
> It would also be possible to do something really simple which is to al= low
> the witness type to be either a MAST hash OR a schnorr key (but not a<= br> > Taproot). This allows you to not completely fracture the anonymity set=
> between people who want plain Schnorr and people who want MAST (at lea= st
> 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 neg= atively
> with any future batch validation mechanism though, but the contextual<= br> > checks to exclude a witness program from the batch are relatively simp= le.
> 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 c= an
> 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 sp= ent.
> As noted by Pieter Wiulle here:
> https://= github.com/kanzure/diyhpluswiki/commit/a03f6567d714f8733b578de263a4b149441c= d058
> delegation was originally possible in Bitcoin, but got broken during a= n
> emergency fork to split the scriptSig and scriptpubkey separation. Rat= her
> than adding some fancy delegation mechanism in Bitcoin, why not just h= ave a
> P2SH-like semantic which allows a delegated script to be evaluated? Se= e
> BIP-117 https://github.com/bitcoi= n/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 gen= erate
> 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. Si= milar
> to the above discussion, top-level is more efficient if you suspect th= at
> 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 allo= w
> different scripts to delegate.
>
>
> Overall, we are left with concerns both about the merit of doing Tapro= ot
> 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 separat= ely?
> What are the actual anonymity set benefits compared to doing the separ= ately?
>
> 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<= br> > 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 perso= nally
> feel comfortable reviewing the crypto in Schnorr -- what's the set= of
> people who have thoroughly reviewed the crypto and aren't just ACK= ing
> 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 w= ho don't
> need the key path a cheaper spend path. See thread subject, "Tapr= oot Public
> NUMS Optimization".
>
> 5) Is the development model of trying to jam a bunch of features into<= br> > Bitcoin all at once good for Bitcoin development? Would we be better o= ff if
> we embraced incremental improvements that can work together (e.g., MAS= T and
> then Schnorr)?=C2=A0 Although the BIP raises some points about anonymi= ty sets
> being why to do them all at once, it's not clear to me this argume= nt 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-mingli= ng
> changes that people end up accepting only because they want one and th= ey're
> bundled (e.g., MAST and Schnorr, MAST seems like a much less risky add= ition
> versus Schnorr). See thread subject, "An Alternative Deployment P= ath for
> Taproot Technologies".
>
>
>
>
> Our provocation with this email is primarily that we think we should m= ore
> carefully consider the benefits of Taproot over simpler primitives tha= t are
> not only easier to review, but could have been made available much soo= ner
> rather than waiting on putting everything all together for an unclear<= br> > aggregate benefit.
>
> We do think that most of the developers have been honest about the ben= efits
> of Taproot, but that on closer look we feel the general ecosystem has<= br> > oversold Taproot as being the key enabler for a collection of techniqu= es
> that we could do with much simpler building blocks.
>
>
> At the end of the day, we do not strongly advocate not deploying Tapro= ot 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 ins= ecure, as
> it cuts through the case where you would otherwise need a NUMS point.<= br> > Things like TapScript and its MAST mechanisms are well designed and of= fer
> exciting new deployment paths, and would be something we would use eve= n if
> we opted for MAST instead of Taproot. However, we also believe it is o= ur
> 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 h= ave
> been sent under a pseudonym so as to keep the focus of discussion on t= he
> 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: [cl= ip
> repeat]
>
> As a follow up to our prior message, we propose a different path forwa= rd
> for the Taproot family of changes:
>
> 1) A separate soft-fork for Merkle Branch Witnesses based on Taproot;<= br> >
> 2) A separate soft-fork for Schnorr Signatures
>
> 3) A separate follow up soft-fork which enables Taproot and Graftroot<= br> >
> 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-f= ork
> on the existing semantics, but requiring a new witness version. With t= he
> 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 implementa= tion 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 witness= es
> are relatively simple and users only have to use Schnorr signing if th= ey
> 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 assumpti= on
> 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<= br> > developers who in aggregate prefer to remain anonymous. These emails h= ave
> been sent under a pseudonym so as to keep the focus of discussion on t= he
> 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: [cl= ipped
> 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=C2=A0 the witness pr= ogram. The
> first byte is the control byte for leaf versioning.
>
> 2) If it's not the witness program, and it's 65 bytes, try sig= nature
> 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 t= he
> leaf version as the last byte of the script (so you can pop it off bef= ore
> 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 point= s are
> just a couple well known constants this could actually decrease privac= y as
> then the NUMS points could differ from application to application
> fingerprinting wallets.=C2=A0 Instead, the NUMS point should only be u= sed when a
> single use nonce can be sent, so that NUMS cannot be distinguished fro= m 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/mail= man/listinfo/bitcoin-dev
--0000000000002f338d059e8ec18c--