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 >