* Re: [bitcoin-dev] Taproot (and graftroot) complexity
@ 2020-09-19 12:52 Jay Berg
2020-09-20 3:23 ` Lloyd Fournier
0 siblings, 1 reply; 9+ messages in thread
From: Jay Berg @ 2020-09-19 12:52 UTC (permalink / raw)
To: Jay Berg, Bitcoin Protocol Discussion
Newb here.. don’t know if "in-reply-to" header is misbehaving.
But this is the OP thread:
[bitcoin-dev] Taproot (and graftroot) complexity
Anthony Towns aj at erisian.com.au
Mon Feb 10 00:20:11 UTC 2020
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017622.html
<a href="mailto:bitcoin-dev%40lists.linuxfoundation.org?Subject=Re:%20Re%3A%20%5Bbitcoin-dev%5D%20Taproot%20%28and%20graftroot%29%20complexity&In-Reply-To=%3C20200210002011.lelhcdmjejmoh6xv%40erisian.com.au%3E" title="[bitcoin-dev] Taproot (and graftroot) complexity">aj at erisian.com.au
</a>
On 9/19/20, 5:35 AM, "bitcoin-dev on behalf of Jay Berg via bitcoin-dev" <bitcoin-dev-bounces@lists•linuxfoundation.org on behalf of bitcoin-dev@lists•linuxfoundation.org> wrote:
> 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,
does reusing keys act differently in taproot than with Pay-to-PubKey-Hash? Or is it the same deal.. same pubkey creates same address?
Question is: is the security/privacy implications worse when reusing pubkeys with taproot?
ty
jay
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists•linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
2020-09-19 12:52 [bitcoin-dev] Taproot (and graftroot) complexity Jay Berg
@ 2020-09-20 3:23 ` Lloyd Fournier
0 siblings, 0 replies; 9+ messages in thread
From: Lloyd Fournier @ 2020-09-20 3:23 UTC (permalink / raw)
To: Jay Berg, Bitcoin Protocol Discussion
Hi Jay,
I don't think there's much of a difference in security or privacy.
The advice to avoid key-reuse remains the same and for the same reasons.
LL
On Sat, Sep 19, 2020 at 11:08 PM Jay Berg via bitcoin-dev
<bitcoin-dev@lists•linuxfoundation.org> wrote:
>
> Newb here.. don’t know if "in-reply-to" header is misbehaving.
>
> But this is the OP thread:
>
> [bitcoin-dev] Taproot (and graftroot) complexity
> Anthony Towns aj at erisian.com.au
> Mon Feb 10 00:20:11 UTC 2020
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-February/017622.html
>
> <a href="mailto:bitcoin-dev%40lists.linuxfoundation.org?Subject=Re:%20Re%3A%20%5Bbitcoin-dev%5D%20Taproot%20%28and%20graftroot%29%20complexity&In-Reply-To=%3C20200210002011.lelhcdmjejmoh6xv%40erisian.com.au%3E" title="[bitcoin-dev] Taproot (and graftroot) complexity">aj at erisian.com.au
> </a>
>
> On 9/19/20, 5:35 AM, "bitcoin-dev on behalf of Jay Berg via bitcoin-dev" <bitcoin-dev-bounces@lists•linuxfoundation.org on behalf of bitcoin-dev@lists•linuxfoundation.org> wrote:
>
>
> > 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,
>
> does reusing keys act differently in taproot than with Pay-to-PubKey-Hash? Or is it the same deal.. same pubkey creates same address?
>
> Question is: is the security/privacy implications worse when reusing pubkeys with taproot?
>
> ty
> jay
>
> _______________________________________________
> 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
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
[not found] <<20200210002011.lelhcdmjejmoh6xv@erisian.com.au>
2020-09-19 7:13 ` Jay Berg
@ 2020-09-19 8:46 ` Jay Berg
1 sibling, 0 replies; 9+ messages in thread
From: Jay Berg @ 2020-09-19 8:46 UTC (permalink / raw)
To: bitcoin-dev
[-- Attachment #1: Type: text/plain, Size: 396 bytes --]
> 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,
does reusing keys act differently in taproot than with Pay-to-PubKey-Hash? Or is it the same deal.. same pubkey creates same address?
Question: does the security/privacy implications change when reusing pubkeys with taproot?
ty
jay
[-- Attachment #2: Type: text/html, Size: 3404 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
[not found] <<20200210002011.lelhcdmjejmoh6xv@erisian.com.au>
@ 2020-09-19 7:13 ` Jay Berg
2020-09-19 8:46 ` Jay Berg
1 sibling, 0 replies; 9+ messages in thread
From: Jay Berg @ 2020-09-19 7:13 UTC (permalink / raw)
To: bitcoin-dev
> 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,
does reusing keys act differently in taproot than with Pay-to-PubKey-Hash? Or is it the same deal.. same pubkey creates same address?
Question is: is the security/privacy implications worse when reusing pubkeys with taproot?
ty
jay
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
2020-02-09 20:19 Bryan Bishop
2020-02-09 20:40 ` Matt Corallo
2020-02-10 0:20 ` Anthony Towns
@ 2020-02-10 6:27 ` ZmnSCPxj
2 siblings, 0 replies; 9+ messages in thread
From: ZmnSCPxj @ 2020-02-10 6:27 UTC (permalink / raw)
To: Bryan Bishop, Bitcoin Protocol Discussion
Good morning The Group,
There are already many excellent arguments presented for Taproot, let me present a related one.
Notice your example MAST:
>
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
Of particular note is that the MAST has a predetermined set of scripts, `a` to `h`.
Now, practically speaking, each of these scripts `a`..`h` will be claimable by one or a number of known, pre-determined participants as well.
Scripts that do not have a pre-determined set of participants exist (e.g. a simple `OP_HASH160 <hash> OP_EQUAL` without any `OP_CHECKSIG` operations) but are generally not expected to actually be *useful* for a majority of use-cases (the above hash-only example could be double-spent by a majority miner, for example).
We expect a vast majority of scripts that will be in use will have a pre-determined fixed finitely-enumerable set of participants (so that miners cannot steal coins once the "solution" to the script puzzle is published in mempools), represented by pubkeys that are fed into `OP_CHECKSIG` operations in the script.
Since each script has (with high probability approaching 1.0) a pre-determined fixed finitely-enumerable set of participants within that script, and the entire MAST itself has a pre-determined fixed finitely-enumerable set of scripts, we can take the union of all sets of participants of all the scripts in the MAST.
Then we put the union of those sets as the signatories of a single Schnorr n-of-n multisignature, to be used as the Taproot keypath branch.
The advantage now is that with Taproot:
* If you can induce all participants to sign a transaction using the keypath spend, then you gain privacy (no part of the MAST is ever published, not even its root or the presence of the MAST!) *and* reduced onchain fees (because the MAST is not published and does not take up space on the blockchain).
* You can incentivize cooperation (beyond just the incentive of improved privacy) by letting participants recover some of the saved onchain fees.
Lightning does this, for example: the funder of the channel is the one paying for the closing fees, and the closing fee of the mutual close is almost always lower than the unilateral close case (or else is equal: the closing ritual has the unilateral close fee as the upper bound on whatever fee can be proposed at the mutual close ritual).
* Even if a participant does not cooperate (for example, it might have been hit by a rogue asteroid in the meantime) we still have the fallback of revealing the entire MAST.
(Just to be clear: I do not *currently* own any datacenters at locations that are likely to be hit by rogue asteroids.)
From this, we can generally conclude that the Taproot assumption --- that there exists some finitely enumerable set of participants we can derive from the scripts needed to enforce a contract --- holds, at a probability near ~1.0, for almost all complicated contracts and protocols we would find useful.
Such contracts and protocols can then be Taproot-ized in order to gain some privacy and transaction size benefits.
Other optimizations, such as selecting k of the n participants as "key participants" who are the most likely to be online and interested in the conclusion of the contract, can then be used to reduce the n-of-n to k-of-n, but the basic Taproot "there exists some n-of-n" assumption still holds and this is just an optimization on top of that.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
2020-02-09 20:19 Bryan Bishop
2020-02-09 20:40 ` Matt Corallo
@ 2020-02-10 0:20 ` Anthony Towns
2020-02-10 6:27 ` ZmnSCPxj
2 siblings, 0 replies; 9+ messages in thread
From: Anthony Towns @ 2020-02-10 0:20 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
On Sun, Feb 09, 2020 at 02:19:55PM -0600, Bryan Bishop via bitcoin-dev wrote:
> However, after
> our review, we're left perplexed about the development of Taproot (and
> Graftroot, to a lesser extent).
I think the main cause of the perplexity is not seeing the benefit of
taproot.
For me, the simplest benefit is that taproot lets everyone's wallet change
from "if you lose this key, your funds are gone" to "if you lose this key,
you'll have to recover 3 of your 5 backup keys that you sent to trusted
friends, and pay a little more, but you won't have lost your funds". That
won't cost you *anything* beyond upgrading your wallet sotware/hardware;
if you never lose your main key, it doesn't cost you any more, but if
you do, you now have a new recovery option (or many recovery options).
Note that doing graftroot isn't proposed as it requires non-interactive
half-signature aggregation to be comparably efficient, and the crypto
hasn't been worked out for that -- or at least, the maths hasn't been
properly written up for criticism. (If you don't care about efficiency,
you can do a poor man's graftroot with pre-signed transactions and CPFP)
More detailed responses below. Kinda long.
> In essence, Taproot is fundamentally the same as doing
> https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and Schnorr
> signatures separately.
>
> Suppose a MAST for {a,b,c,d,e,f,g,h} spending conditions it looks something
> like this:
>
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
>
> If we want this to be functionally equivalent to Taproot, we add a new path:
>
> /\
> /\ {<pk> schnorr_checksig}
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
There's a bit more subtlety to the difference between a merkle branch
and a taproot alternative. In particular, imagine you've got three
alternatives, one of which has 60% odds of being taken, and the other
two have 20% odds each. You'd construct a merkle tree:
/\
a /\
b c
And would reveal:
60%: a [#(b,c)]
20%: b [#a, #c]
20%: c [#a, #b]
So your overhead would be 32B 60% of the time and 64B 40% of the time,
or an expected overhead of 44.8 bytes.
With taproot, you construct a tree of much the same shape, but 60% of
the time you no longer have to reveal anything about the path not taken:
60%: a-tweaked
20%: b [a, #c]
20%: c [a, #b]
So your overhead is 0B 60% of the time, and 65B 40% of the time, for an
expected overhead of 26B.
That math only works out as an improvement if your common case really
is (or can be made to be) a simple key path spend, though.
You can generalise taproot and combine it with a merkle tree arbitrarily,
with the end result being that using a merkle branch means you can
choose either the left or right sub-tree for a cost of 32B, while a
taproot branch lets you choose the left *leaf* for free, or a right
sub-tree for (essentially) 64B. So for equally likely branches you'd
want to use the merkle split, while if there's some particular outcome
that's overwhelmingly likely, with others just there for emergencies,
then a taproot-style alternative will be better. See:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-October/016461.html
for slightly more detailed background.
Ultimately, I think we can do this better, so that you could choose
whether to make the free "taproot" path be a key or a script, or to use
the taproot method to make other likely leaves cheaper than unlikely
ones, rather than just having that benefit available for the most likely
leaf.
But I also think that's a lot of work, much of which will overlap with
the work to get cross-input signature aggregation working, so fwiw,
my view that the current taproot feature set is a good midway point to
draw a line, and get stuff out and released. This overall approach was
discussed quite a while ago:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/015951.html
> However, if we do the same script via taproot, we now need to provide the base
> public key (33 bytes) as well as the root hash (32 bytes) and path and then the
> actual scripts.
You need to provide the internal public key, the actual script and the
path back; the root hash is easily calculated from the script and the
path, and then verified by ECC math against the scriptPubKey and the
internal public key.
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f/\ {<pk> schnorr_checksig}
> g h
>
> We could argue that this is more private than Taproot, because we don't
> distinguish between the Schnorr key case and other cases by default, so chain
> analyzers can't tell if the signature came from the Taproot case or from one of
> the Script paths.
In that example there is no taproot case -- you reveal the existance of
other paths no matter which leaf you make use of. In particular, the "pk
schnorr_checksig" alternative now has 96B of additional overhead (#gh,
#ef, #abcd).
> This
> allows you to not completely fracture the anonymity set between people who want
> plain Schnorr and people who want MAST
> (at least until they go to spend).
The benefit of taproot is that often you can preserve the anonymity set
even after you spend.
> Overall, we are left with concerns both about the merit of doing Taproot
> versus alternatives, as well as the process through which we got to be here.
> 1) Is Taproot actually more private than bare MAST and Schnorr separately? What
> are the actual anonymity set benefits compared to doing the separately?
Yes, presuming single-pubkey-single-signature remains a common
authorisation pattern.
> 2) Is Taproot actually cheaper than bare MAST and Schnorr separately? What
> evidence do we have that the assumption it will be more common to use Taproot
> with a key will outweigh Script cases?
Taproot with a key is about as cheap as it gets -- you've got a 35 byte
scriptPubKey and 66 bytes of witness data.
It's then 33 bytes of witness data more expensive to use a script, which
presumably will make it more likely that people use the simple key path.
At the time you create a utxo, provided you don't reuse keys, all taproot
spends are indistinguishable. At the time you spend a taproot utxo,
you can distinguish:
- spent via key path
- spent via script path, internal key not known
- spent via script path, internal key known NUMS point
but there's no fee rate advantage between reusing a NUMS point and
generating a fresh NUMS point (via NUMS + rand*G), so the third case is
avoidable.
Looking at blocks 616650 to 616700, I see outputs of:
738 0.3% "pubkey"
2091 0.8% "witness_v0_scripthash"
42749 16.8% "witness_v0_keyhash"
102962 40.4% "pubkeyhash"
106441 41.7% "scripthash"
So for plain segwit, over 95% of outputs are plain key; and overall,
over 57.5% of outputs are plain key/signature -- that's not counting
however many p2sh-encoded p2wpkh there are, because they'll just look
like pubkeyhash until they're spent.
> 3) Is Taproot riskier than bare MAST and Schnorr separately given the new
> crypto?
I don't think so; most of the risk for either of those is in getting
the details right.
> How well reviewed is the actual crypto parts?
That's pretty hard to evaluate if you can't review the crypto parts
yourself, but some resources are:
https://github.com/bitcoin-core/secp256k1/pull/558
https://github.com/apoelstra/taproot
https://github.com/ajtowns/taproot-review
Most of the complicated crypto parts are at the application layer: muSig,
threshold signatures, adaptor signatures, scriptless scripts, etc.
> None of us personally feel
> comfortable reviewing the crypto in Schnorr -- what's the set of people who
> have
> thoroughly reviewed the crypto and aren't just ACKing because they trust other
> developers to have looked at it close enough?
That... sounds like it's asking for a group of other developers that
have looked at it close enough for you to trust?
> 4) Design wise, couldn't we forego the NUMS point requirement and be able to
> check if it's a hash root directly?
That would decrease the anonymity set by a lot, make the code a bit
more complicated, and only end up saving 8 vbytes.
> 5) Is the development model of trying to jam a bunch of features into Bitcoin
> all at once good for Bitcoin development? Would we be better off if we embraced
> incremental improvements that can work together (e.g., MAST and then Schnorr)?
IMO, the driving force for bundling these changes together is the
advantages of taproot -- that is:
- you can have either a simple public-key and signature to authorise
a spend, or you can have a script, and decide which to use when
you spend
- using the key path comes at no cost compared to not using taproot
- adding a script path comes at no cost if you don't end up using it
- if you can interactively verify the script conditions off-chain,
you can always use the key path
The latter of those means we want schnorr so that the key path can be
multisig, and using schnorr means that we can use scriptless scripts /
adaptor signatures for things like lightning making the key path more
common.
You can't do taproot cheaply with segwit v0 -- you'd have to use p2wsh
and then reveal something like "<point> OP_TAPROOT_VERIFY DROP DROP 1"
as the script, and then have either a signature or the script and its
witness data encoded as the arguments to that script, which is ugly,
but more importantly requires an extra 37 odd byte reveal of the point
every time.
So that leads to doing segwit v1 -- as otherwise you'd lose the
malleability protection segwit brought, or you'd have to reimplement
segwit to allow a top level "OP_TAPROOTVERIFY" to use witness data.
If you're doing segwit v1, you might as well make it so script is
more upgradable -- otherwise as soon as you want to upgrade script
further you'll end up having to jump to segwit v2. That brings in the
generalisation of "p2sh" that allows different scripts to satisfy a script
hash via a merkle path, the leaf version, OP_SUCCESS and the CHECKSIG*
changes, and that pretty much covers everything that's in bips 340-342.
> SUBJECT: An Alternative Deployment Path for Taproot Technologies
> 1) A separate soft-fork for Merkle Branch Witnesses based on Taproot;
It's not clear to me what "Merkle Branch Witnesses" are. Google comes up
with:
https://notes.ethereum.org/@vbuterin/rkhCgQteN
https://www.btc-way.com/?p=8153
which don't go into specifics. There's different "MAST" proposals in
Bitcoin, such as bip 116+117 vs bip 114 -- bip 114 and taproot's bip 341
have a similar approach; bip 116 on the other hand gives a merkle verify
opcode, and 117 provides a tail-call semantic that combine allow a
script to produce MAST semantics; though in a more programmable way --
if you had a CAT opcode you could have two MASTs in a single script,
combine their result, and then execute it, for instance.
> 2) A separate soft-fork for Schnorr Signatures
> 3) A separate follow up soft-fork which enables Taproot and Graftroot
In order to do something like bip 341's merkle script paths, you'd need
a new segwit version, where the scriptpubkey would be the merkle root
of scripts. If not combined with Schnorr signatures, you'd need to
provide leaf versions or change the way CHECKSIG works from how it works
now in order to upgrade to Schnorr later.
But if we're designing soft-fork 1 in a particular way because we already
know we want to make particular changes from soft-fork 2, I don't think
it makes much sense to split them up.
Having done both of those, in order to do taproot, you'd need another
new segwit version, so that the scriptpubkey could be a taproot point,
but could otherwise reuse the script path.
Obviously I think taproot's desirable, and (roughly) ready to go now,
so I don't see any reason to split that up, particularly when doing so
would use up an additional segwit version.
> users only have to use Schnorr signing if they want to, and can otherwise
> continue to use ECDSA.
Updating to schnorr signing makes it easier to validate the blockchain
(batch validation gives a modest speedup once there are many schnorr
signatures), and updating to the signature hashing algorithms described
in bip 341/342 has benefits for making hardware wallets more secure.
While it's obviously fine for people to not upgrade; upgrading sooner
rather than later does have systemic benefits.
Cheers,
aj
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
2020-02-09 20:40 ` Matt Corallo
@ 2020-02-09 22:32 ` Antoine Riard
0 siblings, 0 replies; 9+ messages in thread
From: Antoine Riard @ 2020-02-09 22:32 UTC (permalink / raw)
To: Matt Corallo, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 3191 bytes --]
> 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).
Not sure this point holds, independently of which Taproot/MASTmechanism
deployed,
any time-sensitive transaction will likely leak its "contestness" by the
setting of its
nSequence/nLocktime fields. E.g, for LN, justice tx are not encumbered by a
CSV
delay which distinguish them from a non-revoked spend. And when you're
relaying
htlcs and need to close unilaterally channel to prevent different
settlement on
incoming/outgoing links the HTLC-timeout tx broadcast have a nLocktime set.
Beyond LN, timelocks are a privacy leak and miner-withholding vector for any
offchain protocols but this problem is not tied to Taproot design.
Confidential
enforcement of them would be great but that's another debate..
Antoine
Le dim. 9 févr. 2020 à 15:40, Matt Corallo via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> a écrit :
> Responding purely to one point as this may be sufficient to clear up
> lots of discussion:
>
> On 2/9/20 8:19 PM, Bryan Bishop via bitcoin-dev wrote:
> > 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.
> Its not just about the frequency and likelihood, no. If there is a
> clearly-provided optimization for this common case in the protocol, then
> it becomes further more likely that developers put in the additional
> effort required to make this possibility a reality. This has a very
> significant positive impact on user privacy, especially those who wish
> to utilize more advanced functionality in Bitcoin. Further, yes, it is
> anticipated that the N of N case is possible to take in the vast
> majority of deployed use-cases for advanced scripting systems, ensuring
> that it is maximally efficient to do so (and thereby encouraging
> developers to do so) is a key goal in this work.
>
> Matt
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
[-- Attachment #2: Type: text/html, Size: 4056 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [bitcoin-dev] Taproot (and graftroot) complexity
2020-02-09 20:19 Bryan Bishop
@ 2020-02-09 20:40 ` Matt Corallo
2020-02-09 22:32 ` Antoine Riard
2020-02-10 0:20 ` Anthony Towns
2020-02-10 6:27 ` ZmnSCPxj
2 siblings, 1 reply; 9+ messages in thread
From: Matt Corallo @ 2020-02-09 20:40 UTC (permalink / raw)
To: Bitcoin Protocol Discussion
Responding purely to one point as this may be sufficient to clear up
lots of discussion:
On 2/9/20 8:19 PM, Bryan Bishop via bitcoin-dev wrote:
> 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.
Its not just about the frequency and likelihood, no. If there is a
clearly-provided optimization for this common case in the protocol, then
it becomes further more likely that developers put in the additional
effort required to make this possibility a reality. This has a very
significant positive impact on user privacy, especially those who wish
to utilize more advanced functionality in Bitcoin. Further, yes, it is
anticipated that the N of N case is possible to take in the vast
majority of deployed use-cases for advanced scripting systems, ensuring
that it is maximally efficient to do so (and thereby encouraging
developers to do so) is a key goal in this work.
Matt
^ permalink raw reply [flat|nested] 9+ messages in thread
* [bitcoin-dev] Taproot (and graftroot) complexity
@ 2020-02-09 20:19 Bryan Bishop
2020-02-09 20:40 ` Matt Corallo
` (2 more replies)
0 siblings, 3 replies; 9+ messages in thread
From: Bryan Bishop @ 2020-02-09 20:19 UTC (permalink / raw)
To: Bitcoin Dev, Bryan Bishop
[-- Attachment #1: Type: text/plain, Size: 13883 bytes --]
The following is a message forwarded from an anonymous email that, for
whatever reason, couldn't be relayed through the mailing list without my
assistance.
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:
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").
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
--
- Bryan
http://heybryan.org/
1 512 203 0507
[-- Attachment #2: Type: text/html, Size: 15597 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2020-09-20 3:23 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2020-09-19 12:52 [bitcoin-dev] Taproot (and graftroot) complexity Jay Berg
2020-09-20 3:23 ` Lloyd Fournier
[not found] <<20200210002011.lelhcdmjejmoh6xv@erisian.com.au>
2020-09-19 7:13 ` Jay Berg
2020-09-19 8:46 ` Jay Berg
-- strict thread matches above, loose matches on Subject: below --
2020-02-09 20:19 Bryan Bishop
2020-02-09 20:40 ` Matt Corallo
2020-02-09 22:32 ` Antoine Riard
2020-02-10 0:20 ` Anthony Towns
2020-02-10 6:27 ` ZmnSCPxj
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox