Re: [bitcoin-dev] Taproot (and graftroot) complexity
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 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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Taproot (and graftroot) complexity
On Sun, Feb 09, 2020 at 02:19:55PM -0600, Bryan Bishop via bitcoin-dev wrote:
> However, after
> our review, we're left perplexed about the development of Taproot (and
> Graftroot, to a lesser extent).
I think the main cause of the perplexity is not seeing the benefit of
taproot.
For me, the simplest benefit is that taproot lets everyone's wallet change
from "if you lose this key, your funds are gone" to "if you lose this key,
you'll have to recover 3 of your 5 backup keys that you sent to trusted
friends, and pay a little more, but you won't have lost your funds". That
won't cost you *anything* beyond upgrading your wallet sotware/hardware;
if you never lose your main key, it doesn't cost you any more, but if
you do, you now have a new recovery option (or many recovery options).
Note that doing graftroot isn't proposed as it requires non-interactive
half-signature aggregation to be comparably efficient, and the crypto
hasn't been worked out for that -- or at least, the maths hasn't been
properly written up for criticism. (If you don't care about efficiency,
you can do a poor man's graftroot with pre-signed transactions and CPFP)
More detailed responses below. Kinda long.
> In essence, Taproot is fundamentally the same as doing
> https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and Schnorr
> signatures separately.
>
> Suppose a MAST for {a,b,c,d,e,f,g,h} spending conditions it looks something
> like this:
>
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
>
> If we want this to be functionally equivalent to Taproot, we add a new path:
>
> /\
> /\ { schnorr_checksig}
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f g h
There's a bit more subtlety to the difference between a merkle branch
and a taproot alternative. In particular, imagine you've got three
alternatives, one of which has 60% odds of being taken, and the other
two have 20% odds each. You'd construct a merkle tree:
/\
a /\
b c
And would reveal:
60%: a [#(b,c)]
20%: b [#a, #c]
20%: c [#a, #b]
So your overhead would be 32B 60% of the time and 64B 40% of the time,
or an expected overhead of 44.8 bytes.
With taproot, you construct a tree of much the same shape, but 60% of
the time you no longer have to reveal anything about the path not taken:
60%: a-tweaked
20%: b [a, #c]
20%: c [a, #b]
So your overhead is 0B 60% of the time, and 65B 40% of the time, for an
expected overhead of 26B.
That math only works out as an improvement if your common case really
is (or can be made to be) a simple key path spend, though.
You can generalise taproot and combine it with a merkle tree arbitrarily,
with the end result being that using a merkle branch means you can
choose either the left or right sub-tree for a cost of 32B, while a
taproot branch lets you choose the left *leaf* for free, or a right
sub-tree for (essentially) 64B. So for equally likely branches you'd
want to use the merkle split, while if there's some particular outcome
that's overwhelmingly likely, with others just there for emergencies,
then a taproot-style alternative will be better. See:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-October/016461.html
for slightly more detailed background.
Ultimately, I think we can do this better, so that you could choose
whether to make the free "taproot" path be a key or a script, or to use
the taproot method to make other likely leaves cheaper than unlikely
ones, rather than just having that benefit available for the most likely
leaf.
But I also think that's a lot of work, much of which will overlap with
the work to get cross-input signature aggregation working, so fwiw,
my view that the current taproot feature set is a good midway point to
draw a line, and get stuff out and released. This overall approach was
discussed quite a while ago:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-May/015951.html
> However, if we do the same script via taproot, we now need to provide the base
> public key (33 bytes) as well as the root hash (32 bytes) and path and then
> the
> actual scripts.
You need to provide the internal public key, the actual script and the
path back; the root hash is easily calculated from the script and the
path, and then verified by ECC math against the scriptPubKey and the
internal public key.
> /\
> / \
> / \
> / \
> /\ /\
> / \ / \
> /\ /\ /\ /\
> a b c d e f/\ { schnorr_checksig}
> g h
>
> We could argue that this is more private than Taproot, because we don't
> distinguish between the Schnorr key case and other cases by default, so chain
> analyzers can't tell if the signature came from the Taproot case or from one
> of
> the Script paths.
In that example there is no taproot case -- you
Re: [bitcoin-dev] Taproot (and graftroot) complexity (reflowed)
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
signature.asc
Description: PGP signature
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Purge attacks (spin on sabotage attacks)
Good morning M, > I don't see how the scenario you outline here has anything to do with the > mechanism I proposed. An empty block doesn't contain any transactions (by > definition) so it wont contest any transactions in any given node's mempool. > The aim isn't to prevent empty nodes, it's to discourage miners from > including transactions in their block that conflict with the > eventually-consistent state of consensus in the mempool. > What? From the original post: > TLDR > * An attacker replaces the most recent blocks full of transactions with empty > blocks. Are you sure you are solving the same problem? The mempool **has no consensus**. It is strictly an optimization, preventing a node from needlessly broadcasting transactions. Making consensus dependent on the state of the mempool requires that you record the state of the mempool at the point at which the block snapshot was taken. Otherwise, newly-started nodes can be fooled into taking the "wrong" consensus branch leading to persistent chainsplits. > > > Always avoid violating that principle in any consensus code. > > If it is not committed to in the block and is not provable using only data > > you provide with the block, you cannot use it safely without risking > > chainsplit. > > > > (and no, banning or even disincentivizing SPV mining will not work, > > different nodes have different views of the mempool and temporary > > chainsplits can occur by chance where one chainsplit has transactions that > > are not confirmed in the other chainsplit, which again is just another > > short-term inadvertent Purge attack on the network.) > > > > > > > > > Purge attacks can still be defended against and does not require mass > > > > cooperation. > > > > If there is a transaction that is economically beneficial to me, it > > > > does so by paying some Bitcoins to me. > > > > If it pays Bitcoins to me, I can spend those Bitcoins in a transaction > > > > that just offers to pay mining fees and transfers it back to me (i.e. > > > > child pays for parent) to convince miners to mine the purged > > > > transaction. > > > > As the Purge attack is "just" a censorship attack (i.e. a censorship of > > > > all transactions in the block under attack), the increased mining fees > > > > for the transactions being censored (i.e. offered via > > > > child-pays-for-parent in this case) is an economic counterattack on the > > > > censoring miner (i.e. it forgoes the mining fees). > > > > > > > With enough self-interested users, the fee offered to confirm the > > > > transactions can be substantial enough that non-censoring miners can be > > > > convinced to mine those transactions. > > > > No coordination necessary, as is typical for all defenses against > > > > censorship (and the basis of the censorship-resistance of Bitcoin). > > > > > > The attack itself is better classified as a form of sabotage than > > > censorship. The goal is to demonstrate the ongoing mutability of > > > transactions beyond any inherent heuristic for “finality”. iow it is a > > > demonstration that will damage the network’s future ability to offer > > > settlement assurances. > > > > > > Trying to use Child Pays For Parent to defend in a bidding war against an > > > opportunist attacker retrieving spent Bitcoin via RBF is a losing game > > > for the defender. There’s no opportunity cost for the attacker, any > > > amount retrieved is profit. The defender, on the other hand, is always > > > losing value. This is exactly the kind of conflict and discoordination > > > the attack is intended to induce. > > > > Your defender, in this attack, should avoid the Sunk Cost Fallacy here. > > If the defender has been so foolish as to provide a product or service > > based on only a *few* confirmations, like 1 or 2, then that product or > > service has been Sunk, and it should ignore the Sunk Cost here. > > > > From that point of view, the attacker and the defender are simply bidding > > up from the *same* value, i.e. the value of the UTXO that is being removed > > by the purge attack. > > As the same value is under contest on both sides, they are equally matched > > and both censoring and non-censoring miners will get the same incentive, > > splitting up the network into two nearly equal halves, and then chance > > (lucky block discovery) decides between which is the winner or the loser. > > > > The difference here is that the chainsplit in this case is in a metastable > > state, and once a string of lucky block discoveries occurs, it falls into a > > stable state and now everybody agrees again on who won and who lost. > > Your solution risks *persistent* *stable* chainsplits. > > Worse, this occurrence without your solution would only happen if some > > miners actually attack the blockchain. > > With your solution, persistent chainsplits can occur without malice, simply > > chance. > > How would this mechanism produce a chainsplit by chance? I already de
Re: [bitcoin-dev] Taproot (and graftroot) complexity
> 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 > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] Taproot (and graftroot) complexity (reflowed)
Apologies for my previous attempt at relaying the message- it looks like
the emails got mangled on the archive. I am re-sending them in this
combined email with what I hope will be better formatting. Again this is
from some nym that had trouble posting to this mailing list; I didn't see
any emails in the queue so I couldn't help to publish this sooner.
SUBJECT: Taproot (and Graftroot) Complexity
This email is the first of a collection of sentiments from a group of
developers who in aggregate prefer to remain anonymous. These emails have
been sent under a pseudonym so as to keep the focus of discussion on the
merits of the technical issues, rather than miring the discussion in
personal politics. Our goal isn't to cause a schism, but rather to help
figure out what the path forward is with Taproot. To that end, we:
1) Discuss the merits of Taproot's design versus simpler alternatives (see
thread subject, "Taproot (and Graftroot) Complexity").
2) Propose an alternative path to deploying the technologies described in
BIP-340, BIP-341, and BIP-342 (see thread subject, "An Alternative
Deployment Path for Taproot Technologies").
3) Suggest a modification to Taproot to reduce some of the overhead (see
thread subject, "Taproot Public NUMS Optimization").
Now that the BIP has moved to draft we felt that now was the time to
prioritize review to make sure it was an acceptable change for our
activities. As a group, we're excited about the totality of what Taproot
has to offer. However, after our review, we're left perplexed about the
development of Taproot (and Graftroot, to a lesser extent).
We also want to convey that we have nothing but respect for the developers
and community who have poured their heart and soul into preparing Taproot.
Self evidently, it is an impressive synthesis of ideas. We believe that the
highest form of respect to pay such a synthesis of ideas is a detailed and
critical review, as it's pertinent to closely consider changes to Bitcoin.
In essence, Taproot is fundamentally the same as doing
https://github.com/bitcoin/bips/blob/master/bip-0114.mediawiki and Schnorr
signatures separately.
The main reason for putting them together -- as mentioned in the BIP -- is
a gain in efficiency. But this efficiency pre-supposes a specific use case
and probability distribution of use cases.
Compare:
Suppose a MAST for {a,b,c,d,e,f,g,h} spending conditions it looks something
like this:
/\
/ \
/\
/ \
/\ /\
/ \/ \
/\ /\ /\ /\
a b c d e f g h
If we want this to be functionally equivalent to Taproot, we add a new path:
/\
/\ { schnorr_checksig}
/ \
/\
/ \
/\ /\
/ \/ \
/\ /\ /\ /\
a b c d e f g h
Now, to spend from this MBV you have to reveal 32 bytes on the stack for
the not taken branch, and 35 bytes for the schnorr_checksig (1 byte
push, 33 bytes PK, 1 byte checksig).
This is 67 bytes more than Taproot would require for the same spending
condition.
However, suppose we wanted to use one of the script paths instead. We still
need to have one extra hash for the { schnorr_checksig} (depending on
if we put the key in this position or not--see below). But now we can spend
with just a logarithmic control program path.
However, if we do the same script via taproot, we now need to provide the
base public key (33 bytes) as well as the root hash (32 bytes) and path and
then the actual scripts. With the need for 2 push bytes, this ends up being
back at 67 bytes extra.
Is Taproot just a probability assumption about the frequency and likelihood
of the signature case over the script case? Is this a good assumption? The
BIP only goes as far as to claim that the advantage is apparent if the
outputs *could be spent* as an N of N, but doesn't make representations
about how likely that N of N case would be in practice compared to the
script paths. Perhaps among use cases, more than half of the ones we expect
people to be doing could be spent as an N of N. But how frequently would
that path get used? Further, while the *use cases* might skew toward things
with N of N opt-out, we might end up in a power law case where it's the one
case that doesn't use an N of N opt out at all (or at a de minimis level)
that becomes very popular, thereby making Taproot more costly then
beneficial.
Further, if you don't want to use a Taproot top-level key (e.g., you need
to be able to audit that no one can spend outside of one of the script
conditions), then you need to use a NUMS (nothing up my sleeve) point. This
forces users who don't want Taproot to pay the expense, when if they just
had a MAST based witness type they would be cheaper. So if this use case is
at all common, Taproot leaves them worse off in terms of fees. Given that
script paths are usually done in the case where there is some contested
close, it's actually in the interest of protocol developers that the
contested script path be as efficient as possible so that th
Re: [bitcoin-dev] Taproot (and graftroot) complexity
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
[bitcoin-dev] Taproot public NUMS optimization (Re: Taproot (and graftroot) complexity)
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
[bitcoin-dev] An alternative deployment path for taproot technology (Re: Taproot (and graftroot) complexity)
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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] Taproot (and graftroot) complexity
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:
/\
/\ { schnorr_checksig}
/ \
/\
/ \
/\ /\
/ \/ \
/\ /\ /\ /\
a b c d e f g h
Now, to spend from this MBV you have to reveal 32 bytes on the stack for
the not
taken branch, and 35 bytes for the schnorr_checksig (1 byte push, 33
bytes
PK, 1 byte checksig).
This is 67 bytes more than Taproot would require for the same spending
condition.
However, suppose we wanted to use one of the script paths instead. We still
need
to have one extra hash for the { schnorr_checksig} (depending on if we
put
the key in this position or not--see below). But now we can spend with just
a
logarithmic control program path.
However, if we do the same script via taproot, we now need to provide the
base
public key (33 bytes) as well as the root hash (32 bytes) and path and then
the
actual scripts. With the need for 2 push bytes, this ends up being back at
67
bytes extra.
Is Taproot just a probability assumption about the frequency and likelihood
of
the signature case over the script case? Is this a good assumption? The BIP
only goes as far as to claim that the advantage is apparent if the outputs
*could be spent* as an N of N, but doesn't make representations about how
likely
that N of N case would be in practice compared to the script paths. Perhaps
among use cases, more than half of the ones we expect people to be doing
could be
spent as an N of N. But how frequently would that path get used? Further,
while
the *use cases* might skew toward things with N of N opt-out, we might end
up in
a power law case where it's the one case that doesn't use an N of N opt out
at
all (or at a de minimis level) that becomes very popular, thereby making
Taproot
more costly then beneficial.
Further, if you don't want to use a Taproot top-level key (e.g., you need
to be
able to audit that no one can spend outside of one of the script
conditions),
then you need to use a NUMS (nothing up my sleeve) point. This forces users
who
don't want Taproot to pay the expense, when if they just had a MAST based
witness type they would be cheaper. So if this use case is at all common,
Taproot leaves them worse off in terms of fees. Given that script paths are
usually done in the case where there is some contested close, it's actually
in
the interest of protocol developers that the contested script path be as
efficient as possible so that the fees paid maximally increase the feerate.
We
think this can be fixed simply in Taproot though, as noted below.
On privacy, we're also a bit confused as to the goal of Taproot over MAST
and
Schnorr. Earlier, we presented a design with MAST whic
Re: [bitcoin-dev] Purge attacks (spin on sabotage attacks)
Hi ZmnSCPxj, On Sun, Feb 9, 2020 at 12:00 AM ZmnSCPxj wrote: > Good morning M, > > > > > Nodes reject announced blocks that: > > > > > > > > * include transactions that are in contest with any in their mempool > > > > * include transactions that are in contest with any in the contest > pool > > > > > > Is this intended to be a consensus rule, i.e. nodes will never accept > such a block? > > > > > > Because if so, this fails the principle of Blockchain > Self-Containment, i.e. consensus rules can only check what is in the > blockchain. > > > The mempool (and contest pool) is not in the blockchain as it is never > attested to in the blockchain. > > > > Yes, it intentionally violates that rule. It’s unclear to me right now > what the consequence/cost of doing so in this specific way would be. Are > you able to explain? > > Violation of this principle can cause persistent chainsplits where you > induce one set of nodes to see one view of reality while another set of > nodes see another view. > For instance, suppose two innocent miners happen to find blocks at nearly > the same time. > Unfortunately for them, one miner happened to be using "SPV" mining i.e. > mining empty blocks. > > From the point of view of arbitrary nodes, this is indistinguishable from > a one-block purge attack as described. > Yet this happenstance occurrence now causes a chainsplit, as some number > of nodes (those near to the SPV-mining miner) think that miner is innocent > of wrongdoing and will support the "purged" chainsplit, whereas those near > the other miner will consider that block bad and will support the other > "unpurged" chainsplit. > This is an even worse consequence than any purge attack, and could happen > completely by chance with no malice involved. > > I don't see how the scenario you outline here has anything to do with the mechanism I proposed. An empty block doesn't contain any transactions (by definition) so it wont contest any transactions in any given node's mempool. The aim isn't to prevent empty nodes, it's to discourage miners from including transactions in their block that conflict with the eventually-consistent state of consensus in the mempool. > Always avoid violating that principle in any consensus code. > If it is not committed to in the block and is not provable using only data > you provide with the block, you cannot use it safely without risking > chainsplit. > > (and no, banning or even disincentivizing SPV mining will not work, > different nodes have different views of the mempool and temporary > chainsplits can occur by chance where one chainsplit has transactions that > are not confirmed in the other chainsplit, which again is just another > short-term inadvertent Purge attack on the network.) > > > > > > > Purge attacks can still be defended against and does not require mass > cooperation. > > > If there is a transaction that is economically beneficial to me, it > does so by paying some Bitcoins to me. > > > If it pays Bitcoins to me, I can spend those Bitcoins in a transaction > that just offers to pay mining fees and transfers it back to me (i.e. child > pays for parent) to convince miners to mine the purged transaction. > > > As the Purge attack is "just" a censorship attack (i.e. a censorship > of all transactions in the block under attack), the increased mining fees > for the transactions being censored (i.e. offered via child-pays-for-parent > in this case) is an economic counterattack on the censoring miner (i.e. it > forgoes the mining fees). > > > > > With enough self-interested users, the fee offered to confirm the > transactions can be substantial enough that non-censoring miners can be > convinced to mine those transactions. > > > No coordination necessary, as is typical for all defenses against > censorship (and the basis of the censorship-resistance of Bitcoin). > > > > The attack itself is better classified as a form of sabotage than > censorship. The goal is to demonstrate the ongoing mutability of > transactions beyond any inherent heuristic for “finality”. iow it is a > demonstration that will damage the network’s future ability to offer > settlement assurances. > > > > Trying to use Child Pays For Parent to defend in a bidding war against > an opportunist attacker retrieving spent Bitcoin via RBF is a losing game > for the defender. There’s no opportunity cost for the attacker, any amount > retrieved is profit. The defender, on the other hand, is always losing > value. This is exactly the kind of conflict and discoordination the attack > is intended to induce. > > Your defender, in this attack, should avoid the Sunk Cost Fallacy here. > If the defender has been so foolish as to provide a product or service > based on only a *few* confirmations, like 1 or 2, then that product or > service has been Sunk, and it should ignore the Sunk Cost here. > > From that point of view, the attacker and the defender are simply bidding > up from the *same* value, i.e. the value of the UTXO
