From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from whitealder.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 97108C0171 for ; Mon, 10 Feb 2020 00:20:21 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id 8C9B184F5A for ; Mon, 10 Feb 2020 00:20:21 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id EZMCu1gPYykc for ; Mon, 10 Feb 2020 00:20:20 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226]) by whitealder.osuosl.org (Postfix) with ESMTPS id B1F3584F4C for ; Mon, 10 Feb 2020 00:20:19 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.89 #1 (Debian)) id 1j0woB-0000MV-0A for ; Mon, 10 Feb 2020 10:20:17 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Mon, 10 Feb 2020 10:20:11 +1000 Date: Mon, 10 Feb 2020 10:20:11 +1000 From: Anthony Towns To: Bitcoin Protocol Discussion Message-ID: <20200210002011.lelhcdmjejmoh6xv@erisian.com.au> References: MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: NeoMutt/20170113 (1.7.2) X-Spam-Score-int: -18 X-Spam-Bar: - Subject: Re: [bitcoin-dev] Taproot (and graftroot) complexity 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: Mon, 10 Feb 2020 00:20:21 -0000 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: > >        /\ >       /\ { 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/\ { 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 " 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