Quote from: gmaxwell on January 25, 2020, 03:48:18 PM

How do you imagine preventing an attacker from spending all your coins at once and sending most of their value to fee? E.g. you have three 1 BTC outputs which require that the output be a 1 BTC payment to address bc1apple. A transaction which spends all three at once to a single 1 BTC bc1apple would comply, and yet turning 2 BTC to fees is probably not what you intended to permit.

In my opinion that BIP is essentially focused on a single use case but it kinda pretends to be more generic. The single use case absolutely requires no malleability, and that ends up creating a lot of limitations. But even without that, additional flexibility is difficult to get right. I think it would be worth the time to do it right. The protocol's author disagrees and instead believes he'll be able to ram it down the network's throat really quickly if he keeps it narrowed to his use case.

I hope the network does not deploy that proposal.

I think where we can agree is that additional flexibility is:

1) Worth pursuing.
2) Difficult to get right.

For the benefit of other's tuning in, we've chatted about OP_CTV at some length on IRC, the logs for which are here: http://gnusha.org/bitcoin-wizards/2019-11-28.log

I'll pull some quotes from that conversation for context so that I can respond to these concerns here, and then respond to the closing point of Greg's post, that he hopes the network doesn't adopt CTV.

One of Greg's core objections to CTV is that it's encoding for just a specific use case, one that will be made redundant or not very popular. What I want to make clear is that there is a difference between how Greg is using "use-case" and a general parlance for use-case. Here, I interpret use-case to be a use-pattern. This use-pattern can be used in different contexts (much like an HTLC is core to both atomic swaps and lightning).

Quote

12:36 < gmaxwell> I don't think opcodes that essentially hard code a specific
use case are ones that would be easy to get through... they just turn into
technical debt if the usecase is eclipsed or turns out to not be popular.
12:37 < jeremyrubin> I don't think it's fair to say CTV is a hard coded specific
use case
12:37 < gmaxwell> and a couple lightning specifc things have essentially been
shot down for that reason in the past.
12:38 < gmaxwell> jeremyrubin: no, but I don't think it's clear that it doesn't
either. Stuff like making it essentialy impossible to add inputs is a really
extreme restriction. (yes you can allow multiple inputs, but as I pointed out--
I think it's really hard if not impossible to do that safely due to double
dipping)
12:40 < gmaxwell> There is a natural tension between wanting to provide a
generic mechenism that has the most usecases, providing something that is simple
to implement and review, and proving something that isn't a heinous footgun that
is hard/impossible to use safely.
12:41 < jeremyrubin> The multi-input use cases listed are basically limited to
wallet vault infrastructure, where you are implementing stuff in a walled
garden. Easy enough to prevent key reuse which obviates that concern.

Core to this point not just that Greg feels the multi-input case is not really usable, but that the single input use case is not very useful.

This comes up in the context of fees, where Greg shares a specific concern that fees are hard to add.

Quote

11:59 < gmaxwell> jeremyrubin: as far as masking flags go, one concern I have
had with your opcode is that it's extremely specific for its usecase, e.g.
binding all outputs and the input count makes it basically impossible to add
additional fees. I know there are anti-doubledipping reasons why particular
applications may want to cover all fields, but it's a pretty extreme
restriction.

There are multiple ways to handle fees with OP_CTV (it's pretty flexible). Imagine you have a chain of CTV transactions, where an arrow `->` indicates one of the outputs is spent.

A -> B -> C

There are a few different ways to ensure fees.

One obvious way, in use today by certain services, is to just wildly overpay fees. This isn't robust, as fees can't be perfectly predicted, but if you're signing over 1000 BTC into a vault you may as well over-spend a bit on fees. Let's ignore this, and assume we want something that works when we don't want to over-pay. (In general, overpayment isn't a bad idea, especially because for protocols it can often be only overpay in the non-cooperative case, but assume we want mechanisms robust and not overpaid when we are completely non-interactive).

The next most obvious way is to use Child Pays For Parent.

In this case, you create a spend D

A -> B -> C -> D such that D pays high enough fee to cover A B C. This is kind-of obvious to do, but it turns out that there are two specific drawbacks:

1) The MemPool is not that good at handling long-chain CPFP (we're working on improving this though!)
2) It requires spending from C which you might want to *create* the output D spends, but not consume it.

Gas Outputs:
To make this better, another way of adding fees would be to add an output at some point in the chain which exists only to be spent in a CPFP. E.g. A->B->C{0,1}, C.1->E. Now spending C.1 to E covers the fee, and C.0 can stay unspent. This can be applied recursively.

Imagine a protocol with some really long chain DAG. Now, a user can craft a transaction spending all of the Gas Outputs along that path, and pay an appropriate fee. This has a nice atomicity property -- either you've paid for the full execution trace you wanted, or nothing extra at all and you can re-emit your fee bump transaction.

This is particularly nice because you do not disturb the sub-protocols in the DAG (e.g., LN channels).

Gas outputs also work nicely (if more than one is used, and CPFP becomes more rational) for cooperative fee-sharing.

Gas Inputs

In this case, we can specify a CTV A which has an additional input slot which can be filled with all fees. But what about change addresses? Well, the solution is to separately create that perfectly-sized UTXO in a transaction to be spent with the desired nodes.

The main issue here is that the transaction is now malleable (both by third party and first party). See below (conditionalizing) for ways of dealing with this.

Conditionalizing
It's also possible to write the script IF ELSE ENDIF OP_CTV.

With taproot, this is even better.

We can specify (at least) four different types of conditions:

1) More Gas Inputs
2) More Gas Outputs
3) More Fees (subtracted from outputs) after a longer sequence from original spend

These options can be hidden from miners so that it's not seen that delaying a txn will get them more fees.

Conditioning more Gas Inputs (from 0 to 1) is slightly problematic in that it introduces malleability. Now an arbitrary third party can malleate the transaction by adding fee. One way of dealing with this would be to write the script:

IF CTV ELSE IF ELSE <1 month lock> CSV <1 key checksig> CTV ENDIF ENDIF

In this case, the logic expresses that at any time, with no modified fee, and no interaction, the original transaction may be broadcast.

At any time, N of N may agree to a new transaction.

If we haven't made progress for a month, then any participant (assuming the 1 key is known to all N) may make progress, potentially malleating the txid but not the outputs. One can imagine writing a script that goes N, N-1, N-2.... 1 in order to balance agreement and non-malleability of the txid (e.g., if the protocol step contains lightning channel outputs).

New Fee OpCode

In general, it might be advisable to introduce an arbitrary CPFP relationship flag or opcode that allows an unrelated transaction to "observe" if another transaction exists in the present block. This would take some engineering to get right, but it can be expressed using the same logic as CPFP today.

This is nice conceptually because we can then abstract from the transactions you are doing (which are the execution) and how you're paying for it. CTV doesn't contain a proposal for this today, but I think this is of independent interest as more protocols are built on Bitcoin struggle to figure out how to pay fees.

New General OpCode

As opposed to conditionality, it's also possible that with the addition of OP_CAT it's much easier to dynamically add a fee input/output.

It's then trivial to write something like (definitely not correct here -- written expediently for the gist):

stack top: <1 or more> X X

OP_SWAP OP_CAT OP_SWAP
<1 known sequences> OP_SWAP OP_CAT OP_SHA256 OP_SWAP OP_CAT OP_SWAP
OP_SWAP OP_CAT OP_SHA256 OP_SWAP OP_CAT
OP_SWAP OP_CAT OP_SHA256 OP_CTV

This type of operation would allow the witness to pass in some arbitrary new change input and output data, while keeping the original intent intact. However, like above, you have malleability.

The above presents many different ways of paying fees, and I also hope helps underscore that CTV actually is pretty flexible! In practice, applications will probably just pick one mechanism to work with.

The larger question that I have is what sort of fee paying flexibility is being imagined that isn't provided as above? This seems to cover most cases -- short of, the common protocol desire of "I wish I didn't have to think about fees" (although a new fee opcode seems to get close to that). Keep in mind, any new proposal for a different path to covenants also has to answer similar questions about fees, and I don't think something simple can be accomplished as a part of the covenants mechanisms.

A further contention is that this is something that graftroot has an advantage in.

Quote
11:27 < gmaxwell> Is it just me or does the CHECKTEMPLATEVERIFY proposal totally
miss the insight of graftroot? -- that a signature is a lot more flexible than
a hash, and except for storage considerations, basically strictly superior?
11:28 < gmaxwell> ISTM that proposal would be much better constructed if it
pushed the output hash (with optional masking) onto the stack... where it could
then be constrained for equality or validated w/ a signature operator that
checksigs stuff on the stack.
11:28 < gmaxwell> then it could be used either in a stateless taproot sort of
way, or in a more flexible graftroot sort of way.

Quote
12:09 < gmaxwell> jeremyrubin: as far as non-interactive goes, graftrooting
doesn't necessarily imply interaction. If the signature used doesn't commit to
the pubkey, then it can be used as a disguised hash. E.g. I can pick a nums
signature and compute the pubkey that makes it valid for a particular message.
A third party that doesn't know the nums seed can't distinguish that from a
signature. I would have
12:09 < gmaxwell> lobbied heavily to never do taproot and only do graftroot,
except an additional signature is space inefficient.
12:09 < jeremyrubin> Hmmm
12:09 < jeremyrubin> Well then isn't there an issue if you do that of not being
able to bind multiple values?
12:09 < jeremyrubin> Or are you imaging a graftroot opcode?
12:10 < jeremyrubin> Because OP_IF OP_CTV OP_ELSE OP_CTV
OP_ENDIF is a pretty desirable script
12:11 < gmaxwell> If you use a nums signature to treat a signature has a
hashcheck then you're stuck with a single value. But it has the nice property
that a third party observer can't tell that you did that. Only the first and
second party can. It has the downside that it's bigger than a hash.
12:11 < gmaxwell> Of course, in applications where you might revise the outputs
(e.g. using a decrementing CSV sequence like a payment channel), the ability to
make revised outputs is probably super useful... it just comes at a cost of
interaction.

I think this is a reasonable point. It certainly seems to be the case that were there to be a graftroot like thing available, you would use
it to elide a CTV script for compactness reasons (in fact I've previously suggested being able to hide a CTV hash in a taproot leaf for efficiency). However, it doesn't really suit the CTV use case that well because we want to support non-interactive cases with multiple branches.

Unless there is a script level graftroot which supports recursion, in which case it's possible that you can make it work by conditionalizing different keys to different CTV-equivalents. But a recursive graftroot construction would seem to me to be fraught to design.

Further, if you're doing complex programs which require large compilations, the curve operations may make it prohibitive compared to just hashing.

Lastly, Greg's point that a signature is more flexible than a hash is kind-of incorrect. A hash must be strictly more flexible, in a sense, because a signature contains a hash. As shown above in the discussion of fees, you can do some really flexible stuff with CTV.

Another issue Greg brings up is an important one, which is covered in the BIP.
Quote
12:02 < gmaxwell> (and, I think actually if you ever allow 2 inputs, I think it
immediately opens up a "spend two outputs at once that allow two inputs,
converting half the funds into fees" attack. E.g. I create two idencial coins,
A and A' which allow two inputs, so they can get a variable fee input, and each
one requires an output of B with all its value. But then an attacker makes a
txn that spends both at
12:02 < gmaxwell> once, creating only one B output, and sends the rest of the
funds to fees)

This is addressed in two different ways. The first, is by restricting the number of inputs.

If you're fitting within a common use case of a single input per branch of a CTV tree, you "for free" don't have to worry about most of the malleability issues and can merrily design your protocol.

If you do need more than one, you now have 2 issues:

1) Malleability
2) Key-Reuse

Malleability is in two categories:

1) Third party
2) First Party

The key reuse issue is "solved" by including the index at which a coin should be spent at in the the hash. This means if I spend to two identical basic CTV scripts, they provably cannot be spent in the same transaction. If you specify two different indexes, that's you indicating that you're open to them being spent together, and should take similar precautions to malleability.

If you're worried about third party malleability, and you have more than one input, one option is to include a public key that is known to all participants in addition to the CTV. Now, no third party can create a spend in an unintended way, because first-parties have to "approve" of the CTV for it to go through (signing other outputs).

If you're worried about first party malleability, it requires some tradeoffs (or something like OP_CAT) to make it truly robust (see as presented in the fees section).

These solutions also end up solving, for the most part, the "half-spend" problem Greg mentioned. In typical uses, it shouldn't come up.

The last application point I wanted to cover, was this claim:
Quote
12:16 < gmaxwell> And for things like payment pools, interaction is assumed, so
real signatures are fine. (I didn't look at your applications yet, so I don't
know if you've got payment pools there, perhaps under another name)

In general, this is exactly what CTV is here to avoid. We don't want signatures because they are interactive and they preclude non-interactive setups. Non interactive setups are a much more scalable solution because it means that senders can *pay into* complex protocol setups immediately.

E.g., coinbase can redeem users *always* into payment pools, where the participants online can immediately begin transacting (I have thoughts on how payment pools should be architected, the conclusion of those thoughts being that creating a CTV tree of multiparty channels which terminates in 2-of-2 channels, and "novates up the tree" when needed, has the best set of tradeoffs for privacy and efficiency).

--------------------------------------------------------------------------------------------------------------------------------------------

I sincerely hope that the network adopts CTV, and reject the notion that it's worth not deploying in the near term to take time to come up with a more powerful model for smart contracts (perhaps one day we'll know how to do a compact zero knowledge EVM for all I know).

With BIP-119, I've worked diligently to look at a wide variety of use cases and patterns to make sure that CHECKTEMPLATEVERIFY is compatible, even with it's restrictions.

I'm not confident that we'd be able to ever make something much more flexible than CHECKTEMPLATEVERIFY given the propensity for such transaction introspection to trigger superlinear hashing issues.

It's also less clear to me that additional flexibility is required for CheckTemplateVerify to cover the bases sufficiently. Is there a particular application that you have in mind that you believe CheckTemplateVerify to not work well for? I am happy to look into it and see if there's a similar design that works well under CTV.

From my experience designing around it, CheckTemplateVerify is going to be a useful tool in the belt for payment channels, vaults, payment pools, and much more. For some protocols where CheckTemplateVerify seems insufficient or unwieldy to use, what I've seen is that a small set of new opcodes (such as OP_CAT, OP_MBV, OP_CHECKINPUT) were required for the design in addition to a covenant system, but the designs were ultimately compatible with OP_CTV (without crazy scripts like checksigfromstack covenants).

If you can give a concrete protocol example of where you think OP_CTV falls short I'm happy to walk through how you can build something sufficient with OP_CTV.

In general, I also think that rather than pursuing a "magic bullet" (which could be some snark verifier opcode, potentially), it's nice to add functionality in compose-able chunks so that the network can benefit from new use cases immediately and we can inform our later engineering efforts from real world use cases.

Lastly, I apologize to anyone who feels that I've been trying to ram a change down the network's throat. I've tried to make every effort to form an inclusive review and development process, with numerous presentations, online resources at https://utxos.org, mailing lists posts, reference implementations, a BIP, one on one meetings with companies, and a workshop that many will attend next weekend (invite still stands Greg!), but I understand that individuals expectations of procedure vary. At the end of the day, everyone wants something different from Bitcoin.

While I don't agree with Greg's characterizations of my work -- neither on a technical level nor on a procedural level -- I trust the Bitcoin network & it's participants carefully weigh changes and improvements and decide what's best.