[bitcoin-dev] Taproot (and graftroot) complexity

[bitcoin-dev] Taproot (and graftroot) complexity

[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 --]

[bitcoin-dev] An alternative deployment path for taproot technology (Re: Taproot (and graftroot) complexity)

[Bryan Bishop]

[-- Attachment #1: Type: text/plain, Size: 2400 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 is message (2/3).

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: 2755 bytes --]

[bitcoin-dev] Taproot public NUMS optimization (Re: Taproot (and graftroot) complexity)

[Bryan Bishop]

[-- Attachment #1: Type: text/plain, Size: 2202 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 is message (3/3).

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:

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").

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


- Bryan
http://heybryan.org/
1 512 203 0507

[-- Attachment #2: Type: text/html, Size: 2556 bytes --]

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

[Matt Corallo]

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] Taproot (and graftroot) complexity (reflowed)

[Bryan Bishop]

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

Apologies for my previous attempt at relaying the message- it looks like
the emails got mangled on the archive. I am re-sending them in this
combined email with what I hope will be better formatting. Again this is
from some nym that had trouble posting to this mailing list; I didn't see
any emails in the queue so I couldn't help to publish this sooner.

SUBJECT: Taproot (and Graftroot) Complexity

This email is the first of a collection of sentiments from a group of
developers who in aggregate prefer to remain anonymous. These emails have
been sent under a pseudonym so as to keep the focus of discussion on the
merits of the technical issues, rather than miring the discussion in
personal politics.  Our goal isn't to cause a schism, but rather to help
figure out what the path forward is with Taproot. To that end, we:

1) Discuss the merits of Taproot's design versus simpler alternatives (see
thread subject, "Taproot (and Graftroot) Complexity").

2) Propose an alternative path to deploying the technologies described in
BIP-340, BIP-341, and BIP-342 (see thread subject, "An Alternative
Deployment Path for Taproot Technologies").

3) Suggest a modification to Taproot to reduce some of the overhead (see
thread subject, "Taproot Public NUMS Optimization").

Now that the BIP has moved to draft we felt that now was the time to
prioritize review to make sure it was an acceptable change for our
activities. As a group, we're excited about the totality of what Taproot
has to offer. However, after our review, we're left perplexed about the
development of Taproot (and Graftroot, to a lesser extent).

We also want to convey that we have nothing but respect for the developers
and community who have poured their heart and soul into preparing Taproot.
Self evidently, it is an impressive synthesis of ideas. We believe that the
highest form of respect to pay such a synthesis of ideas is a detailed and
critical review, as it's pertinent to closely consider changes to Bitcoin.


In essence, Taproot is fundamentally the same as doing
https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and Schnorr
signatures separately.

The main reason for putting them together -- as mentioned in the BIP -- is
a gain in efficiency. But this efficiency pre-supposes a specific use case
and probability distribution of use cases.

Compare:

Suppose a MAST for {a,b,c,d,e,f,g,h} spending conditions it looks something
like this:


      /\
     /  \
    /    \
   /      \
  /\      /\
 /  \    /  \
/\  /\  /\  /\
a b c d e f g h

If we want this to be functionally equivalent to Taproot, we add a new path:

       /\
      /\ {<pk> schnorr_checksig}
     /  \
    /    \
   /      \
  /\      /\
 /  \    /  \
/\  /\  /\  /\
a b c d e f g h

Now, to spend from this MBV you have to reveal 32 bytes on the stack for
the not taken branch, and 35 bytes for the <pk> schnorr_checksig (1 byte
push, 33 bytes PK, 1 byte checksig).

This is 67 bytes more than Taproot would require for the same spending
condition.

However, suppose we wanted to use one of the script paths instead. We still
need to have one extra hash for the {<pk> schnorr_checksig} (depending on
if we put the key in this position or not--see below). But now we can spend
with just a logarithmic control program path.

However, if we do the same script via taproot, we now need to provide the
base public key (33 bytes) as well as the root hash (32 bytes) and path and
then the actual scripts. With the need for 2 push bytes, this ends up being
back at 67 bytes extra.

Is Taproot just a probability assumption about the frequency and likelihood
of the signature case over the script case? Is this a good assumption?  The
BIP only goes as far as to claim that the advantage is apparent if the
outputs *could be spent* as an N of N, but doesn't make representations
about how likely that N of N case would be in practice compared to the
script paths. Perhaps among use cases, more than half of the ones we expect
people to be doing could be spent as an N of N. But how frequently would
that path get used? Further, while the *use cases* might skew toward things
with N of N opt-out, we might end up in a power law case where it's the one
case that doesn't use an N of N opt out at all (or at a de minimis level)
that becomes very popular, thereby making Taproot more costly then
beneficial.

Further, if you don't want to use a Taproot top-level key (e.g., you need
to be able to audit that no one can spend outside of one of the script
conditions), then you need to use a NUMS (nothing up my sleeve) point. This
forces users who don't want Taproot to pay the expense, when if they just
had a MAST based witness type they would be cheaper. So if this use case is
at all common, Taproot leaves them worse off in terms of fees. Given that
script paths are usually done in the case where there is some contested
close, it's actually in the interest of protocol developers that the
contested script path be as efficient as possible so that the fees paid
maximally increase the feerate. We think this can be fixed simply in
Taproot though, as noted below.



On privacy, we're also a bit confused as to the goal of Taproot over MAST
and Schnorr. Earlier, we presented a design with MAST which is very close
to Taproot.  However, it'd also be possible to just add {<pk>
schnorr_checksig} to the set {a,b,c,d,e,f,g,h}, shuffle them, and compute
some MAST structure (perhaps probability encoded) on them. This has the
effect of not having much additional fees for adding the extra Schnorr path
at redeem time (only 1 extra branch on 2/8 script paths), e.g.


      /\
     /  \
    /    \
   /      \
  /\      /\
 /  \    /  \
/\  /\  /\  /\
a b c d e f/\ {<pk> schnorr_checksig}
          g  h

We could argue that this is more private than Taproot, because we don't
distinguish between the Schnorr key case and other cases by default, so
chain analyzers can't tell if the signature came from the Taproot case or
from one of the Script paths. There's also no NUMS point required, which
means chain analyzers can't tell when you spend that there was no top level
key if the NUMS point is not per-output indistinguishable. By using a
semi-randomized MAST structure, chain analyzers also can't tell exactly how
big your spend condition MAST was. In particular, you care more about
privacy when you are contesting a close of a channel or other script path
because then the miners could be more likely to extract a rent from you as
"ransom" for properly closing your channel (or in other words, in a
contested close the value of the closing transaction is larger than usual).

It would also be possible to do something really simple which is to allow
the witness type to be either a MAST hash OR a schnorr key (but not a
Taproot). This allows you to not completely fracture the anonymity set
between people who want plain Schnorr and people who want MAST (at least
until they go to spend). This fix can also be used in Taproot in place of a
NUMS point, to decrease extra fees. It's unclear if this plays negatively
with any future batch validation mechanism though, but the contextual
checks to exclude a witness program from the batch are relatively simple.
See thread subject, "Taproot Public NUMS Optimization".

The considerations around Graftroot, a proposed delegation mechanism, is a
bit similar. Delegation is a mechanism by which a UTXO with script S can
sign a script R which can then be executed in addition to S without
requiring a transaction. This allows an output to monotonically and
dynamically increase the number of conditions under which it can be spent.
As noted by Pieter Wiulle here:
https://github.com/kanzure/diyhpluswiki/commit/a03f6567d714f8733b578de263a4b149441cd058
delegation was originally possible in Bitcoin, but got broken during an
emergency fork to split the scriptSig and scriptpubkey separation. Rather
than adding some fancy delegation mechanism in Bitcoin, why not just have a
P2SH-like semantic which allows a delegated script to be evaluated? See
BIP-117 https://github.com/bitcoin/bips/blob/master/bip-0117.mediawiki.
This way we aren't special casing where delegation can occur, and we can
allow taproot nested spending conditions (i.e., with timelocks) to generate
their own delegations. As I've seen Graftroot discussed thus far, it is as
a top-level witness program version like Taproot and non-recursive. Similar
to the above discussion, top-level is more efficient if you suspect that
delegation will be most likely occurring at the top level, but it's not
clear that's a good assumption as it may be common to want to allow
different scripts to delegate.


Overall, we are left with concerns both about the merit of doing Taproot
versus alternatives, as well as the process through which we got to be here.

1) Is Taproot actually more private than bare MAST and Schnorr separately?
What are the actual anonymity set benefits compared to doing the separately?

2) Is Taproot actually cheaper than bare MAST and Schnorr separately? What
evidence do we have that the assumption it will be more common to use
Taproot with a key will outweigh Script cases?

3) Is Taproot riskier than bare MAST and Schnorr separately given the new
crypto? How well reviewed is the actual crypto parts? None of us personally
feel comfortable reviewing the crypto in Schnorr -- what's the set of
people who have thoroughly reviewed the crypto and aren't just ACKing
because they trust other developers to have looked at it close enough?

4) Design wise, couldn't we forego the NUMS point requirement and be able
to check if it's a hash root directly? This would encumber users who don't
need the key path a cheaper spend path. See thread subject, "Taproot Public
NUMS Optimization".

5) Is the development model of trying to jam a bunch of features into
Bitcoin all at once good for Bitcoin development? Would we be better off if
we embraced incremental improvements that can work together (e.g., MAST and
then Schnorr)?  Although the BIP raises some points about anonymity sets
being why to do them all at once, it's not clear to me this argument holds
water (same goes for businesses not upgrading). If we can take things as
smaller steps, we are not only more secure, but we also have more time to
dedicate review to each change independently. We also end up co-mingling
changes that people end up accepting only because they want one and they're
bundled (e.g., MAST and Schnorr, MAST seems like a much less risky addition
versus Schnorr). See thread subject, "An Alternative Deployment Path for
Taproot Technologies".




Our provocation with this email is primarily that we think we should more
carefully consider the benefits of Taproot over simpler primitives that are
not only easier to review, but could have been made available much sooner
rather than waiting on putting everything all together for an unclear
aggregate benefit.

We do think that most of the developers have been honest about the benefits
of Taproot, but that on closer look we feel the general ecosystem has
oversold Taproot as being the key enabler for a collection of techniques
that we could do with much simpler building blocks.


At the end of the day, we do not strongly advocate not deploying Taproot at
this point in the review cycle. We think the Taproot Public NUMS
Optimization may be a good idea, worth considering if it's not insecure, as
it cuts through the case where you would otherwise need a NUMS point.
Things like TapScript and its MAST mechanisms are well designed and offer
exciting new deployment paths, and would be something we would use even if
we opted for MAST instead of Taproot. However, we also believe it is our
duty to raise these concerns and suggestions, and we look forward to
listening to the responses of the community.

Great thanks,

The Group

----

SUBJECT: An Alternative Deployment Path for Taproot Technologies

This email is the second of a collection of sentiments from a group of
developers who in aggregate prefer to remain anonymous. These emails have
been sent under a pseudonym so as to keep the focus of discussion on the
merits of the technical issues, rather than miring the discussion in
personal politics. Our goal isn't to cause a schism, but rather to help
figure out what the path forward is with Taproot. To that end, we: [clip
repeat]

As a follow up to our prior message, we propose a different path forward
for the Taproot family of changes:

1) A separate soft-fork for Merkle Branch Witnesses based on Taproot;

2) A separate soft-fork for Schnorr Signatures

3) A separate follow up soft-fork which enables Taproot and Graftroot

We think that the first 2 forks can be offered at the same time or one at a
time.

Taproot, as a follow up to changes 1 and 2, can be enabled as a soft-fork
on the existing semantics, but requiring a new witness version. With the
Public NUMS Optimization, wallets could upgrade by just changing one
version byte to be in the same anonymity set as Taproot.

It's not clear to us that the time to prepare a BIP and implementation for
1 and 2 at this point would be any less than the time to do Taproot as
currently proposed. However, we believe that such a deployment plan is a
reasonable option as it is more conservative, as Merkle Branch witnesses
are relatively simple and users only have to use Schnorr signing if they
want to, and can otherwise continue to use ECDSA. A further benefit of
waiting on 3 is that we get to collect real world protocol engineering
experience to see how frequently the Taproot frequency of use assumption
holds, and if it is worth doing or not.


Great thanks,

The Group


----

SUBJECT: Taproot Public NUMS Optimization

This email is the third of a collection of sentiments from a group of
developers who in aggregate prefer to remain anonymous. These emails have
been sent under a pseudonym so as to keep the focus of discussion on the
merits of the technical issues, rather than miring the discussion in
personal politics. Our goal isn't to cause a schism, but rather to help
figure out what the path forward is with Taproot. To that end, we: [clipped
again]

We propose to modify Taproot's specification in BIP-341 by adding the rule:

If there is one element on the witness stack:

1) Attempt hashing it to see if it's equal to  the witness program. The
first byte is the control byte for leaf versioning.

2) If it's not the witness program, and it's 65 bytes, try signature
validation

If there is more than one element on the witness stack:

If the control block is even, treat it as a non-Taproot MAST and get the
leaf version as the last byte of the script (so you can pop it off before
hashing).


If greater anonymity is required, a NUMS point can still be used in
Taproot, at the expense of the additional data. However, if NUMS points are
just a couple well known constants this could actually decrease privacy as
then the NUMS points could differ from application to application
fingerprinting wallets.  Instead, the NUMS point should only be used when a
single use nonce can be sent, so that NUMS cannot be distinguished from a
normal Taproot to a third party who doesn't know the setup (e.g., that the
NUMS is H(X) for known X).


Great thanks,

The Group

-- 
- Bryan
http://heybryan.org/
1 512 203 0507

[-- Attachment #2: Type: text/html, Size: 16574 bytes --]

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

[Antoine Riard]

[-- 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 --]

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

[David A. Harding]

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

On Sun, Feb 09, 2020 at 02:47:29PM -0600, Anon via Bryan Bishop via bitcoin-dev wrote:
> 1) Is Taproot actually more private than bare MAST and Schnorr separately?

Yes.

> What are the actual anonymity set benefits compared to doing the separately?

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)

The four cases above represent an overwhelming percentage of the spends
seen on the block chain today and throughout Bitcoin's entire history to
date, so optimizing to include them in the anonymity set presents a huge
benefit.

> 2) Is Taproot actually cheaper than bare MAST and Schnorr separately? 

Earlier in y'alls email, you claim that the difference between the two
approaches for a particular example is 67 bytes.  I haven't checked that
calculation, but it seems you're talking entirely about bytes that could
appear in the witness data and so would only represent 16.75 vbytes.
Compare that to the size of the other elements which would need to be
part of a typical input:

- (36 vbytes) outpoint
- (1) scriptSig compactSize uint
- (4) nSequence 
- (16.25) schnorr signature (includes size byte)

That's 57.25 vbytes exclusive of your example data or 74.00 vbytes
inclusive.  That means the overhead you're concerned about adds only
about 23% to the size of the input (or 30% on an exclusive basis).
That's definitely worth considering optimizations for, but I'm
personally ok with requiring users of advanced scripts (who can't manage
to produce mutual closes) pay an extra 23% for their inputs in order to
allow the creation of the large anonymity set described above for all
the other cases.

If, subsequent to deployment, large numbers of users do end up using
taproot script-path spends and we want to make things more fair, we can
even out the weighting, perhaps by simply increasing the weight of
key-path spends by 16.75 vbytes (though that would, of course,
proportionally lower the capacity of the block chain).  As mentioned in
a separate email by Matt Corallo, it seems worthwhile to optimize for
the case where script-path spenders are encouraged to look for
mutually-agreed contract resolutions in order to both minimize block
chain use and increase the size of the anonymity set.

> What evidence do we have that the assumption it will be more common to
> use Taproot with a key will outweigh Script cases?

The evidence that current users of single-sig, n-of-n, and k-of-n (for
small n) with a default k-set, and mutual-agreed contract protocol
outcomes vastly outweigh all other transaction inputs today and for all
of Bitcoin's history to date.

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Anthony Towns]

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

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

[ZmnSCPxj]

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

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

[Jonas Nick]

I agree with most of the comments so far, but the group brings up an often
overlooked point with respect to the privacy benefits of taproot. In the extreme
case, if there would be no policies that have both a key and a script spend
path, then taproot does not improve anonymity sets compared to the "Taproot
Public NUMS Optimization" proposal (which saves 8 vbytes in a script-spend). (*)

In fact, the cases where scripts would have to be used given usage of Bitcoin
today are be rare because threshold policies, their conjunctions and
disjunctions can be expressed with a single public key. Even if we disregard
speculation that timelocks, ANYPREVOUT/NOINPUT and other interesting scripts
will be used in the future (which can be added through the leaf or key versions
without affecting key-spend anonymity sets), not all of today's applications are
able to be represented single public keys because there are applications that
can not deal with interactive key setups or interactive signing. For
applications where this is possible it will be a gradual change because of the
engineering challenges involved. For example, k-of-n threshold policies could
have the most likely k-of-k in the taproot output key and other k-of-k in the
leaves, instead of going for a k-of-n taproot output key immediately.

Given that anonymity sets in Bitcoin are permanent and software tends to be
deployed longer than anyone would expect at the time of deployment,
realistically Taproot is superior to the "Public NUMS Optimization" and "An
Alternative Deployment Path".

(*) One could argue that the little plausible deniability gained by a very small
probability of the change of a script-spend being a key-spend and vice versa is
significantly better than no probability at all.

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

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

[Jeremy]

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

Dave,

I think your point:
















*When schnorr and taproot are done together, all of the following
transaction types can be part of the same set:     - single-sig spends
(similar to current use of P2PKH and P2WPKH)     - n-of-n spends with musig
or equivalent (similar to current use of       P2SH and P2WSH 2-of-2
multisig without special features as used by       Blockstream Green and LN
mutual closes)     - k-of-n (for low values of n) using the most common k
signers       (similar to BitGo-style 2-of-3 where the keys involved are
    alice_hot, alice_cold, and bob_hot and almost all transactions are
  expected to be signed by {alice_hot, bob_hot}; that common case       can
be the key-path spend and the alternatives {alice_hot,       alice_cold}
and {alice_cold, bob_hot} can be script-path spends)     - contract
protocols that can sometimes result in all parties       agreeing on an
outcome (similar to LN mutual closes, cross-chain       atomic swaps, and
same-chain coinswaps) *

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


Jonas,

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

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


cheers,

jeremy

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


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

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

[-- Attachment #2: Type: text/html, Size: 27326 bytes --]

Re: [bitcoin-dev] Taproot public NUMS optimization (Re: Taproot (and graftroot) complexity)

[Jeremy]

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

I am working on CTV, which has cases where it's plausible you'd want a
taproot tree with a NUMS point.

The need for NUMS points is a little bit annoying. There are a few reasons
you would want to use them instead of multisig:

1) Cheaper to verify/create.
If I have a protocol with 1000 people in it, if I add a multisig N of N to
verify I need a key for all those people, and the probability of use seems
low.
I then also need to prove to each person in the tree that their key is
present. My memory on MuSig is a bit rusty, but I think they key
aggregation requires sending all the public keys and re-computing. (Maybe
you can compress this to O(log n) using a Merkle tree for the tweak L?)
Further, these keys can't just be the addresses provided for those 1000
people, as if those addresses are themselves N of Ns or scripts it gets
complicated, fast (and potentially broken). Instead we should ask that each
participant give us a list of keys to include in the top-level. We'd also
want each participant to provide
two signatures with that key of some piece of non-txn data (so as to prove
it itself wasn't a NUMS point -- otherwise may as well skip this all and
just use a top-level nums point).
2) Auditable.
If I set up an inheritance scheme, like an annuity or something, and the
IRS wants me to pay taxes on what I've received, adverse inference will
tell them to assume that my parent gave me a secret get all the money path
and this is a tax dodge. With a NUMS point, heirs can prove there was no
top-level N of N.
3) I simply don't want to spend it without a script condition, e.g.,
timelock.


Now, assuming you do want a NUMS, there is basically 4 ways to make one
(that I could think of):

1) Public NUMS -- this is a constant, HashToCurve("I am a NUMS Point").
Anyone scanning the chain can see spends are using this constant. Hopefully
everyone uses the same constant (or everyone uses 2,3,4) so that "what type
of NUMS you are using" isn't a new fingerprint.
2) Moslty Public NUMS -- I take the hash of some public data (like maybe
the txid) on some well defined protocol, and use that. Anyone scanning the
chain and doing an EC operation per-txid can see I'm using a constant --
maybe my HashToCurve takes 10 seconds (perhaps through a VDF to make it
extra annoying for anyone who hasn't been sent the shortcut), but in
practice it's no better than 1.
3) Interactive NUMS -- I swap H(Rx), H(Ry) with the other participant and
then NUMS with H(Rx || Ry). This is essentially equivalent to using a MuSig
key setup where one person's key is a NUMS. Now no one passively scanning
can see that it's NUMS, but I can prove to an auditor later.
4) 1/2 RTT Async-Interactive NUMS -- I take some public salt -- say the
txid T, and hash it with a piece of random data R and then HashToCurve(T ||
R)... I think this is secure? Not clear the txid adds any security. Now I
can prove to you that the hash was based on the txid, but I've blinded it
with R to stop passive observers. But I also need ot send you data out of
band for R (but I already had to do this for Taproot maybe?)

The downsides with 3/4 is that if you lose your setup, you lose your
ability to spend/prove it's private (maybe can generate R from a seed?). So
better hold on to those tightly! Or use a public NUMS.

Only 3,4 provide any "real" privacy benefit and at a small hit to
likelihood of losing funds (more non-deterministic data to store). I guess
the question becomes how likely are we to have support for generating a
bunch of NUMS points?

Comparing with this proposal which removes the NUMS requirement:

1) NUMS/Taproot anonymity set *until* spend, MAST set after spend
2) No complexity around NUMS generation/storage
3) If people don't have ecosystem-wide consistent NUMS practices, leads to
additional privacy leak v.s. bare MAST which would be equivalent to case 1
(Public NUMS)
4) Slightly less chain overhead (32 bytes/8 vbytes).
5) Slightly faster chain validation (EC Point tweak is what like 10,000 -
100,000 times slower than a hash?)


Matt raises a interesting point in the other thread, which is that if we
put the option for a more private NUMS thing, someone will eventually write
software for it. But that seems to be irrespective of if we make no-NUMS an
option for bare MAST spends.

Overall I think this is a reasonable proposal. It effectively only
introduces bare MAST to prevent the case where people are using a few
different Public NUMS leaking metadata by putting incentive to use the same
one -- none. Using a private NUMS is unaffected incentive wise as it's
essentially just paying a bit more to be in the larger anonymity set. I
think it makes some class of users better off, and no one else worse off,
so this change seems Pareto.

Thus I'm in favor of adding a rule like this.

I think reasonable alternative responses to accepting this proposed change
would be to:

1) Add a BIP for a standard Public NUMS Point exported through secp256k1 to
head off people defining their own point.
2) Add a discounting rule if the point P is the Public NUMS that discounts
the extra weight somehow.
3) Take a Bit out of the leaf version portion of C[0] to denote Public NUMS
and then elide having to include the point (as it's just standard). This
has the benefit of not needing as much code-change as The Group's proposed
change, but the downside of still requiring an extra EC Mul in validation.

Rejecting the proposal is also, IMO, reasonable. On my personal
preferences, I'd rather get something like Taproot and MAST available
sooner than later, even if there are small quirks on privacy and cost, and
ignore a small benefit rule change/exception that would hold it up by more
than a month or two. I don't see why a small tweak would add substantial
delay, but I think other BIP authors/reviewers would be able to better
comment.

Best,

Jeremy

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


On Sun, Feb 9, 2020 at 12:25 PM Bryan Bishop via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> 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 is message (3/3).
>
> 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:
>
> 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").
>
> 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
>
>
> - Bryan
> http://heybryan.org/
> 1 512 203 0507
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 15287 bytes --]

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

[David A. Harding]

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

On Fri, Feb 14, 2020 at 12:07:15PM -0800, Jeremy via bitcoin-dev wrote:
> Is the same if Schnorr + Merkle Branch without Taproot optimization, unless
> I'm missing something in one of the cases? 

That's fair.  However, it's only true if everyone constructs their
merkle tree in the same way, with a single `<schnorr_pk> OP_CHECKSIG` as
one of the top leaves.   Taproot effectively standardizes the position
of the all-parties-agree condition and so its anonymity set may contain
spends from scripts whose creators buried or excluded the the all-agree
option because they didn't think it was likely to be used.

More importantly, there's no incentive for pure single-sig users to use a
merkle tree, since that would make both the scriptPubKey and the witness
data are larger for them than just continuing to use v0 segwit P2WPKH.
Given that single-sig users represent a majority of transactions at
present (see AJ Towns's previous email in this thread), I think we
really want to make it as convenient as possible for them to participate
in the anonymity set.

(To be fair, taproot scriptPubKeys are also larger than P2WPKH
scriptPubKeys, but its witness data is considerably smaller, giving
receivers an incentive to demand P2TR payments even if spenders don't
like paying the extra 12 vbytes per output.)

Rough sums:

- P2WPKH scriptpubkey (22.00 vbytes): `OP_0 PUSH20 <hash160>`
- P2WPKH witness data (26.75): `size(72) <sig>, size(33) <pubkey>`
- P2TR scriptpubkey (34.00): `OP_1 PUSH32 <pubkey>`
- P2TR witness data (16.25): `size(64) <sig>`
- BIP116 MBV P2WSH scriptpubkey (34.00): `OP_0 PUSH32 <sha256>`
- BIP116 MBV P2WSH witness data (42.00): `size(64) <signature>, size(32)
  <pubkey>, size(32) <inclusion_proof>, size(36) <PUSH1 <n> PUSH32
  <merkle_root> OP_MBV>`

-Dave

P.S. I think this branch of the thread is just rehashing points that
     were originally covered over two years ago and which haven't really
     changed since then.  E.g.:

    https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015629.html

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

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

[Pieter Wuille]

On Fri, 14 Feb 2020 at 14:37, David A. Harding via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> On Fri, Feb 14, 2020 at 12:07:15PM -0800, Jeremy via bitcoin-dev wrote:
> > Is the same if Schnorr + Merkle Branch without Taproot optimization, unless
> > I'm missing something in one of the cases?
>
> That's fair.  However, it's only true if everyone constructs their
> merkle tree in the same way, with a single `<schnorr_pk> OP_CHECKSIG` as
> one of the top leaves.   Taproot effectively standardizes the position
> of the all-parties-agree condition and so its anonymity set may contain
> spends from scripts whose creators buried or excluded the the all-agree
> option because they didn't think it was likely to be used.
>
> More importantly, there's no incentive for pure single-sig users to use a
> merkle tree, since that would make both the scriptPubKey and the witness
> data are larger for them than just continuing to use v0 segwit P2WPKH.
> Given that single-sig users represent a majority of transactions at
> present (see AJ Towns's previous email in this thread), I think we
> really want to make it as convenient as possible for them to participate
> in the anonymity set.

Right, I think we shouldn't just see Taproot as adding a possibility
of a cheap single-key branch to Merkle tree. It is actively choosing
to incentivize protocols and implementations that can use the key
path, making sure that the cheapest way spending of spending is also
the most private one - as we can assume that it indeed will be the
most frequent one. I don't believe having a separate MAST-no-Taproot
spending type (through whatever mechanism) is beneficial to that.
Taproot effectively gives everyone a "key path spend is included in
the price", making it maximally appealing even to those who don't care
about privacy.

I don't think this is an unreasonable angle. There are plenty of other
options that exists if we just want to make verification constructions
cheap but disregard incentives for privacy. For example, why don't we
research account-based state/payments? Being able to avoid change
would make simple payments significantly cheaper (both in terms of
block space and computation). Of course, the reason (or at least one
of them) is that it would result in a discount for those willing to
reduce their privacy (use accounts = reuse address = don't pay for
change), and this hurts everyone (and indirectly the fungibility of
the system as a whole). This is true even when there are use cases
that would legitimately benefit from having this option.

This is of course a much weaker case, but I think it is similar.
Having no-Taproot available would reduce the incentives for those who
don't care about spending policy privacy to put the engineering effort
into building key-path-spendable protocols and implementations - and I
think such protocols, wherever possible, should be the goal. There
probably are some use cases where key path spending is truly not an
option, but I suspect they're rare, or sufficiently high value that 8
vbyte differences don't matter to them. If that turns out to be wrong,
it remains possible to add a new output type/witness version that does
support them. This does mean distinguishable outputs, but only for
things that would be distinguishable at spending time anyway, and
that's a cost we'll have to pay anyway for future structural script
improvements (like cross-input aggregation or graftroot).

Cheers,

-- 
Pieter