* [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY @ 2019-11-26 1:50 Jeremy 2019-11-27 21:32 ` Russell O'Connor 2020-06-07 16:51 ` Joachim Strömbergson 0 siblings, 2 replies; 17+ messages in thread From: Jeremy @ 2019-11-26 1:50 UTC (permalink / raw) To: Bitcoin development mailing list [-- Attachment #1: Type: text/plain, Size: 2659 bytes --] Bitcoin Developers, Pleased to announce refinements to the BIP draft for OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily: 1) Changed the name to something more fitting and acceptable to the community 2) Changed the opcode specification to use the argument off of the stack with a primitive constexpr/literal tracker rather than script lookahead 3) Permits future soft-fork updates to loosen or remove "constexpr" restrictions 4) More detailed comparison to alternatives in the BIP, and why OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may make it semi-redundant. Please see: BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki Reference Implementation: https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify I believe this addresses all outstanding feedback on the design of this opcode, unless there are any new concerns with these changes. I'm also planning to host a review workshop in Q1 2020, most likely in San Francisco. Please fill out the form here https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in participating (even if you can't physically attend). And as a "but wait, there's more": 1) RPC functions are under preliminary development, to aid in testing and evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted` shows one way to use OP_CHECKTEMPLATEVERIFY. See: https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. `sendmanycompacted` is still under early design. Standard practices for using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a separate BIP. This work generalizes even if an alternative strategy is used to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. 2) Also under development are improvements to the mempool which will, in conjunction with improvements like package relay, help make it safe to lift some of the mempool's restrictions on longchains specifically for OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268 This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's fate. Neither of these are blockers for proceeding with the BIP, as they are ergonomics and usability improvements needed once/if the BIP is activated. See prior mailing list discussions here: * https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html * https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html Thanks to the many developers who have provided feedback on iterations of this design. Best, Jeremy -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> [-- Attachment #2: Type: text/html, Size: 7629 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2019-11-26 1:50 [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY Jeremy @ 2019-11-27 21:32 ` Russell O'Connor 2019-11-28 19:59 ` Jeremy 2020-06-07 16:51 ` Joachim Strömbergson 1 sibling, 1 reply; 17+ messages in thread From: Russell O'Connor @ 2019-11-27 21:32 UTC (permalink / raw) To: Jeremy, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4236 bytes --] Thanks for this work Jeremy. I know we've discussed this before, but I'll restate my concerns with adding a new "global" state variable to the Script interpreter for tracking whether the previous opcode was a push-data operation or not. While it isn't so hard to implement this in Bitcoin Core's Script interpreter, adding a new global state variable adds that much more complexity to anyone trying to formally model Script semantics. Perhaps one can argue that there is already (non-stack) state in Script, e.g. to deal with CODESEPARATOR, so why not add more? But I'd argue that we should avoid making bad problems worse. If we instead make the CHECKTEMPLATEVERIFY operation fail if it isn't preceded by (or alternatively followed by) an appropriate sized (canonical?) PUSHDATA constant, even in an unexecuted IF branch, then we can model the Script semantics by considering the PUSHDATA-CHECKTEMPLATEVERIFY pair as a single operation. This allows implementations to consider improper use of CHECKTEMPLATEVERIFY as a parsing error (just as today unbalanced IF-ENDIF pairs can be modeled as a parsing error, even though that isn't how it is implemented in Bitcoin Core). I admit we would lose your soft-fork upgrade path to reading values off the stack; however, in my opinion, this is a reasonable tradeoff. When we are ready to add programmable covenants to Script, we'll do so by adding CAT and operations to push transaction data right onto the stack, rather than posting a preimage to this template hash. Pleased to announce refinements to the BIP draft for OP_CHECKTEMPLATEVERIFY > (replaces previous OP_SECURETHEBAG BIP). Primarily: > > 1) Changed the name to something more fitting and acceptable to the > community > 2) Changed the opcode specification to use the argument off of the stack > with a primitive constexpr/literal tracker rather than script lookahead > 3) Permits future soft-fork updates to loosen or remove "constexpr" > restrictions > 4) More detailed comparison to alternatives in the BIP, and why > OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may > make it semi-redundant. > > Please see: > BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki > Reference Implementation: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify > > I believe this addresses all outstanding feedback on the design of this > opcode, unless there are any new concerns with these changes. > > I'm also planning to host a review workshop in Q1 2020, most likely in San > Francisco. Please fill out the form here > https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in participating > (even if you can't physically attend). > > And as a "but wait, there's more": > > 1) RPC functions are under preliminary development, to aid in testing and > evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted` > shows one way to use OP_CHECKTEMPLATEVERIFY. See: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. > `sendmanycompacted` is still under early design. Standard practices for > using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a > separate BIP. This work generalizes even if an alternative strategy is used > to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. > 2) Also under development are improvements to the mempool which will, in > conjunction with improvements like package relay, help make it safe to lift > some of the mempool's restrictions on longchains specifically for > OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268 > This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's > fate. > > > Neither of these are blockers for proceeding with the BIP, as they are > ergonomics and usability improvements needed once/if the BIP is activated. > > See prior mailing list discussions here: > > * > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html > * > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html > > Thanks to the many developers who have provided feedback on iterations of > this design. > > Best, > > Jeremy > > -- > @JeremyRubin <https://twitter.com/JeremyRubin> > [-- Attachment #2: Type: text/html, Size: 8350 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2019-11-27 21:32 ` Russell O'Connor @ 2019-11-28 19:59 ` Jeremy 2019-12-11 0:37 ` Jeremy 0 siblings, 1 reply; 17+ messages in thread From: Jeremy @ 2019-11-28 19:59 UTC (permalink / raw) To: Russell O'Connor; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 6800 bytes --] Thanks for the feedback Russell, now and early. It deeply informed the version I'm proposing here. I weighed carefully when selecting this design that I thought it would be an acceptable tradeoff after our discussion, but I recognize this isn't exactly what you had argued for. First off, with respect to the 'global state' issue, I figured it was reasonable with this choice of constexpr rule given that a reasonable tail recursive parser might look something like: parse (code : rest) stack alt_stack just_pushed = match code with OP_PUSH => parse rest (x:stack) alt_stack True OP_DUP => parse rest (x:stack) alt_stack False // ... So we're only adding one parameter which is a bool, and we only need to ever set it to an exact value based on the current code path, no complicated rules. I'm sensitive to the complexity added when formally modeling script, but I think because it is only ever a literal, you could re-write it as co-recursive: parse_non_constexpr (code : rest) stack alt_stack = match code with OP_PUSH => parse_constexpr rest (x:stack) alt_stack OP_DUP => parse_non_constexpr rest (x:stack) alt_stack // ... parse_constexpr (code : rest) stack alt_stack = match code with OP_CTV => ... _ => parese_non_constexpr (code : rest) stack alt_stack If I recall, this should help a bit with the proof automatability as it's easier in the case by case breakdown to see the unconditional code paths. In terms of upgrade-ability, one of the other reasons I liked this design is that if we do enable OP_CTV for non-constexpr arguments, the issue basically goes away and the OP becomes "pure" without any state tracking. (I think the switching on argument size is much less a concern because we already use similar upgrade mechanisms elsewhere, and it doesn't add parsing context). It's also possible, as I think *should be done* for tooling to treat an unbalanced OP_CTV as a parsing error. This will always produce consensus-valid scripts! However by keeping the consensus rules more relaxed we keep our upgrade-ability paths open for OP_CTV, which as I understand from speaking with other users is quite desirable. Best (and happy thanksgiving to those celebrating), Jeremy -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Thu, Nov 28, 2019 at 6:33 AM Russell O'Connor <roconnor@blockstream•io> wrote: > Thanks for this work Jeremy. > > I know we've discussed this before, but I'll restate my concerns with > adding a new "global" state variable to the Script interpreter for tracking > whether the previous opcode was a push-data operation or not. While it > isn't so hard to implement this in Bitcoin Core's Script interpreter, > adding a new global state variable adds that much more complexity to anyone > trying to formally model Script semantics. Perhaps one can argue that > there is already (non-stack) state in Script, e.g. to deal with > CODESEPARATOR, so why not add more? But I'd argue that we should avoid > making bad problems worse. > > If we instead make the CHECKTEMPLATEVERIFY operation fail if it isn't > preceded by (or alternatively followed by) an appropriate sized > (canonical?) PUSHDATA constant, even in an unexecuted IF branch, then we > can model the Script semantics by considering the > PUSHDATA-CHECKTEMPLATEVERIFY pair as a single operation. This allows > implementations to consider improper use of CHECKTEMPLATEVERIFY as a > parsing error (just as today unbalanced IF-ENDIF pairs can be modeled as a > parsing error, even though that isn't how it is implemented in Bitcoin > Core). > > I admit we would lose your soft-fork upgrade path to reading values off > the stack; however, in my opinion, this is a reasonable tradeoff. When we > are ready to add programmable covenants to Script, we'll do so by adding > CAT and operations to push transaction data right onto the stack, rather > than posting a preimage to this template hash. > > Pleased to announce refinements to the BIP draft for >> OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily: >> >> 1) Changed the name to something more fitting and acceptable to the >> community >> 2) Changed the opcode specification to use the argument off of the stack >> with a primitive constexpr/literal tracker rather than script lookahead >> 3) Permits future soft-fork updates to loosen or remove "constexpr" >> restrictions >> 4) More detailed comparison to alternatives in the BIP, and why >> OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may >> make it semi-redundant. >> >> Please see: >> BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki >> Reference Implementation: >> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify >> >> I believe this addresses all outstanding feedback on the design of this >> opcode, unless there are any new concerns with these changes. >> >> I'm also planning to host a review workshop in Q1 2020, most likely in >> San Francisco. Please fill out the form here >> https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in >> participating (even if you can't physically attend). >> >> And as a "but wait, there's more": >> >> 1) RPC functions are under preliminary development, to aid in testing and >> evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted` >> shows one way to use OP_CHECKTEMPLATEVERIFY. See: >> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. >> `sendmanycompacted` is still under early design. Standard practices for >> using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a >> separate BIP. This work generalizes even if an alternative strategy is used >> to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. >> 2) Also under development are improvements to the mempool which will, in >> conjunction with improvements like package relay, help make it safe to lift >> some of the mempool's restrictions on longchains specifically for >> OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268 >> This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's >> fate. >> >> >> Neither of these are blockers for proceeding with the BIP, as they are >> ergonomics and usability improvements needed once/if the BIP is activated. >> >> See prior mailing list discussions here: >> >> * >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html >> * >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html >> >> Thanks to the many developers who have provided feedback on iterations of >> this design. >> >> Best, >> >> Jeremy >> >> -- >> @JeremyRubin <https://twitter.com/JeremyRubin> >> > [-- Attachment #2: Type: text/html, Size: 16011 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2019-11-28 19:59 ` Jeremy @ 2019-12-11 0:37 ` Jeremy 2019-12-13 23:06 ` Jeremy 0 siblings, 1 reply; 17+ messages in thread From: Jeremy @ 2019-12-11 0:37 UTC (permalink / raw) To: Jeremy; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 17789 bytes --] Three changes I would like to make to the OP_CTV draft. I think this should put the draft in a very good place w.r.t. outstanding feedback. The changes can all be considered/merged independently, though, they are written below assuming all of them are reasonable. 1) *Make the hash commit to the INPUT_INDEX of the executing scriptPubKey.* *Motivation:* As previously specified, a CTV template constructed specifying a transaction with two or more inputs has a "half-spend" issue whereby if the template script is paid to more than once (a form of key-reuse), they can be joined in a single transaction leading to half of the intended outputs being created. *Example:* Suppose I have a UTXO with a CTV requiring two inputs. The first is set to be the CTV template, and the input has enough money to pay for all the outputs. The second input is added to allow the adding of a fee-only utxo. Now suppose someone creates an similar UTXO with this same CTV (even within the same transaction). TxA {vin: [/*elided...*/], vout: [TxOut{1 BTC, <TxB template hash> CTV}, TxOut {1 BTC, <TxB template hash> CTV}]} *Intended Behavior:* TxB0 {vin: [Outpoint{TxA.hash(), 0}, /*arbitrary fee utxo*/], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] TxB1 {vin: [Outpoint{TxA.hash(), 1}, /*arbitrary fee utxo*/], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] *Possible Unintended Behaviors:* * Half-Spend:* TxB {vin: [Outpoint{TxA.hash(), 1}, Outpoint{TxA.hash(), 0}], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] *Order-malleation:* TxB0 {vin: [/*arbitrary fee utxo*/, Outpoint{TxA.hash(), 0}], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] TxB1 {vin: [Outpoint{TxA.hash(), 1}, /*arbitrary fee utxo*/], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] With the new rule, the CTV commits to the index in the vin array that it will appear. This prevents both the half-spend issue and the order-malleation issue. Thus, the only execution possible is: *Intended Behavior:* TxB0 {vin: [Outpoint{TxA.hash(), 0}, /*arbitrary fee utxo*/], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] TxB1 {vin: [Outpoint{TxA.hash(), 1}, /*arbitrary fee utxo*/], vout : [TxOut {1 BTC, /* arbitrary scriptPubKey */}] *Impact of Change:* This behavior change is minor -- in most cases we are expecting templates with a single input, so committing the input index has no effect. Only when we do specify multiple inputs, committing the INPUT_INDEX has the side effect of making reused-keys not susceptible to the "half-spend" issue. This change doesn't limit the technical capabilities of OP_CTV by much because cases where the half-spend construct is desired can be specified by selecting the correct inputs for the constituent transactions for the transaction-program. In the future, Taproot can make it easier to express contracts where the input can appear at any index by committing to a tree of positions. This change also has the benefit of reducing the miner-caused TXID malleability in certain applications (e.g., in a wallet vault you can reduce malleability from your deposit flow, preventing an exponential blow-up). However in such constructions the TXIDs are still malleable if someone decides to pay you Bitcoin that wasn't previously yours through a withdrawal path (a recoverable error, and on the bright side, someone paid you Bitcoin to do it). This change also has a minor impact on the cacheability of OP_CTV. In the reference implementation we currently precompute and store single hash for the StandardTemplateHash of the entire transaction. Making the hash vary per-input means that we would need to precompute one hash per-input, which is impractical. Given that we expect the 0-index to be the exceedingly common case, and it's not horribly expensive if we aren't cached (a constant sized SHA-256), the spec will be updated to precompute and cache only the hash for the 0th index. (The hash is also changed slightly to make it more efficient for un-cached values, as noted in change 3). *2) Remove Constexpr restriction* *Changes:* Currently it is checked that the template hash argument was not 'computed', but came from a preceding push. Remove all this logic and accept any argument. *Motivation:* I've had numerous conversations with Bitcoin developers (see above, see #bitcoin-wizards on Nov 28th 2019, in person at local meetups, and in private chats with ecosystem developers) about the constexpr restriction in OP_CTV. There have been a lot of folks asking to remove template constexpr restriction, for a few reasons: a) Parsing Simplification / no need for special-casing in optimizers like miniscript b) The types of script it disables aren't dangerous c) There are exciting things you can do were it not there and other features were enabled (OP_CAT) d) Without other features (like OP_CAT), there's not really too much you can do No one has expressed any strong justification to keep it. The main motivation for the constexpr restriction was to keep the CTV proposal very conservative in scope, increasing the likelihood that it is an acceptable change. It was also designed to be able to be easily lifted in a future soft-fork. There isn't a *specific* behavior the constexpr restriction is attempting to prevent, it's just a belt-and-suspenders measure to limit how creatively CTV could be used now or in the future. Future OpCodes + OP_CTV may introduce a broader set of functionality than possible if OP_CTV were to retain the constexpr rule. But I think given that these future op-codes will likely be introduced intentionally to introduce broader functionalities, we shouldn't limit the functionality of OP_CTV today. *Impact of Changes:* The only mildly interesting thing that could be done with this change (with no additional changes; that I could think of) would be to write a script like: <serialization of transaction fields according to hash spec> SHA256 OP_CTV which would be a "self-describing" covenant (for no space savings). This could be useful in some protocols where "the public" should be able to execute some step with only chain-data. N.B. This cannot enable a case where the CTV is in the scriptSig like: scriptPubKey: <key> CHECKSIG scriptSig: <serialization of transaction details> OP_SHA256 CTV <sig> because the serialization of the transaction contains a commitment to non-null scriptSigs, a self-reference/hash cycle. *3) Modify the template digest to be easier to cache and work with in script.* *Changes:* The current hash is: uint256 GetStandardTemplateHash(const CTransaction& tx) { auto h = TaggedHash("StandardTemplateHash") << tx.nVersion << tx.nLockTime << GetOutputsSHA256(tx) << GetSequenceSHA256(tx) << uint64_t(tx.vin.size()); for (const auto& in : tx.vin) h << in.scriptSig; return h.GetSHA256(); } I propose changing it to: uint256 GetStandardTemplateHash(const CTransaction& tx, uint32_t input_index) { uint256 scriptSig_hash{}; bool hash_scriptSigs = std::count(tx.vin.begin(), tx.vin.begin(), CScript()) != tx.vin().size(); if (hash_scriptSigs) { auto h = CHashWriter() for (const auto& in : tx.vin) h << in.scriptSig; scriptSig_hash = h.GetSHA256(); } auto h = CHashWriter() << tx.nVersion << tx.nLockTime; if (hash_scriptSigs) h << scriptSig_hash; h << uint64_t(tx.vin.size()) << GetSequenceSHA256(tx) << uint32_t(tx.vout.size()) << GetOutputsSHA256(tx) << input_index; return h.GetSHA256(); } This changes a few things: 1) Getting rid of the TaggedHash use 2) Re-ordering to put input_index last 3) Re-ordering to put Outputs SHA256 second-to-last 4) Only computing scriptSig_hash if any scriptSig is non-null 5) Making scriptSig data hashed in it's own hash-buffer 6) explicitly committing to the vout.size() 7) Casting vout.size() but not vin.size() to uint32_t (vout is capped by COutpoint indicies to 32 bits, vin is not) *Motivation:* The current digest algorithm is relatively arbitrarily ordered and set up. Modifying it makes it easier to cache (given the input index change) and makes it easier to construct templates in script (once OP_CAT, or OP_SUBSTR, or OP_STREAMSHA256 are added to core). *Impact of Changes:* *1) Getting rid of the TaggedHash use* Low-impact. TaggedHash didn't add any security to the template hashes, but did make it harder to "confuse" a StandardTemplateHash for a hash of another type. However, the tagged hash makes it slightly more difficult/costly to construct (with OP_CAT enabled) a template hash within script, so it is removed. *2) Re-ordering to put input_index last* The input index should be put last because this makes it easy to cache the intermediate hash state *just before* hashing the index, which makes recomputing for different indexes cheaper. It also allows (with OP_CAT or STREAMSHA256) to easily allow setting the accepted indexes from script. *3) Re-ordering to put Outputs SHA256 second-to-last* In the future, with OP_CAT/SHA256STREAM or similar, changing the outputs in the covenant is the most likely change. Placing it near the end simplifies this operation. *4) Only computing scriptSig_hash if any scriptSig is non-null* There is no need to hash the scriptSig data at all if they are all null. This is in most cases true, so we avoid extra hashing. But the bigger win is for scripted construction of templates, which can just completely ignore the scriptSig hashing if it is known to be using all bare CTV/non-p2sh segwit inputs (which should be the common case). *5) Making scriptSig data hashed in it's own hash-buffer, when hash is included.* This implies that there are two possible sizes for the hashed data, +/- 1 hash (for scripSig_hash). This eliminates concerns that directly hashing elements into the template hash buffer might expose some length extension issue when constructing a template in script. *6) explicitly committing to the vout.size()* This makes it easier, when OP_CAT or similar is added, to write restrictions that guarantee a limit on the number of inputs that may be created. *7) Casting vout.size() but not vin.size() to uint32_t (vout is capped by COutpoint indicies to 32 bits, vin is not)* This is just kind of annoying, but technically you can have more inputs in a transaction than outputs because more than 32-bits of outputs breaks the COutpoint class invariants. -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Thu, Nov 28, 2019 at 11:59 AM Jeremy <jlrubin@mit•edu> wrote: > Thanks for the feedback Russell, now and early. It deeply informed the > version I'm proposing here. > > I weighed carefully when selecting this design that I thought it would be > an acceptable tradeoff after our discussion, but I recognize this isn't > exactly what you had argued for. > > First off, with respect to the 'global state' issue, I figured it was > reasonable with this choice of constexpr rule given that a reasonable tail > recursive parser might look something like: > > parse (code : rest) stack alt_stack just_pushed = > match code with > OP_PUSH => parse rest (x:stack) alt_stack True > OP_DUP => parse rest (x:stack) alt_stack False > // ... > > So we're only adding one parameter which is a bool, and we only need to > ever set it to an exact value based on the current code path, no > complicated rules. I'm sensitive to the complexity added when formally > modeling script, but I think because it is only ever a literal, you could > re-write it as co-recursive: > > parse_non_constexpr (code : rest) stack alt_stack = > match code with > OP_PUSH => parse_constexpr rest (x:stack) alt_stack > OP_DUP => parse_non_constexpr rest (x:stack) alt_stack > // ... > > parse_constexpr (code : rest) stack alt_stack = > match code with > OP_CTV => ... > _ => parese_non_constexpr (code : rest) stack alt_stack > > > If I recall, this should help a bit with the proof automatability as it's > easier in the case by case breakdown to see the unconditional code paths. > > > In terms of upgrade-ability, one of the other reasons I liked this design > is that if we do enable OP_CTV for non-constexpr arguments, the issue > basically goes away and the OP becomes "pure" without any state tracking. > (I think the switching on argument size is much less a concern because we > already use similar upgrade mechanisms elsewhere, and it doesn't add > parsing context). > > > It's also possible, as I think *should be done* for tooling to treat an > unbalanced OP_CTV as a parsing error. This will always produce > consensus-valid scripts! However by keeping the consensus rules more > relaxed we keep our upgrade-ability paths open for OP_CTV, which as I > understand from speaking with other users is quite desirable. > > > Best (and happy thanksgiving to those celebrating), > > Jeremy > > -- > @JeremyRubin <https://twitter.com/JeremyRubin> > <https://twitter.com/JeremyRubin> > > > On Thu, Nov 28, 2019 at 6:33 AM Russell O'Connor <roconnor@blockstream•io> > wrote: > >> Thanks for this work Jeremy. >> >> I know we've discussed this before, but I'll restate my concerns with >> adding a new "global" state variable to the Script interpreter for tracking >> whether the previous opcode was a push-data operation or not. While it >> isn't so hard to implement this in Bitcoin Core's Script interpreter, >> adding a new global state variable adds that much more complexity to anyone >> trying to formally model Script semantics. Perhaps one can argue that >> there is already (non-stack) state in Script, e.g. to deal with >> CODESEPARATOR, so why not add more? But I'd argue that we should avoid >> making bad problems worse. >> >> If we instead make the CHECKTEMPLATEVERIFY operation fail if it isn't >> preceded by (or alternatively followed by) an appropriate sized >> (canonical?) PUSHDATA constant, even in an unexecuted IF branch, then we >> can model the Script semantics by considering the >> PUSHDATA-CHECKTEMPLATEVERIFY pair as a single operation. This allows >> implementations to consider improper use of CHECKTEMPLATEVERIFY as a >> parsing error (just as today unbalanced IF-ENDIF pairs can be modeled as a >> parsing error, even though that isn't how it is implemented in Bitcoin >> Core). >> >> I admit we would lose your soft-fork upgrade path to reading values off >> the stack; however, in my opinion, this is a reasonable tradeoff. When we >> are ready to add programmable covenants to Script, we'll do so by adding >> CAT and operations to push transaction data right onto the stack, rather >> than posting a preimage to this template hash. >> >> Pleased to announce refinements to the BIP draft for >>> OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily: >>> >>> 1) Changed the name to something more fitting and acceptable to the >>> community >>> 2) Changed the opcode specification to use the argument off of the stack >>> with a primitive constexpr/literal tracker rather than script lookahead >>> 3) Permits future soft-fork updates to loosen or remove "constexpr" >>> restrictions >>> 4) More detailed comparison to alternatives in the BIP, and why >>> OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may >>> make it semi-redundant. >>> >>> Please see: >>> BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki >>> Reference Implementation: >>> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify >>> >>> I believe this addresses all outstanding feedback on the design of this >>> opcode, unless there are any new concerns with these changes. >>> >>> I'm also planning to host a review workshop in Q1 2020, most likely in >>> San Francisco. Please fill out the form here >>> https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in >>> participating (even if you can't physically attend). >>> >>> And as a "but wait, there's more": >>> >>> 1) RPC functions are under preliminary development, to aid in testing >>> and evaluation of OP_CHECKTEMPLATEVERIFY. The new command >>> `sendmanycompacted` shows one way to use OP_CHECKTEMPLATEVERIFY. See: >>> https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. >>> `sendmanycompacted` is still under early design. Standard practices for >>> using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a >>> separate BIP. This work generalizes even if an alternative strategy is used >>> to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. >>> 2) Also under development are improvements to the mempool which will, in >>> conjunction with improvements like package relay, help make it safe to lift >>> some of the mempool's restrictions on longchains specifically for >>> OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268 >>> This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's >>> fate. >>> >>> >>> Neither of these are blockers for proceeding with the BIP, as they are >>> ergonomics and usability improvements needed once/if the BIP is activated. >>> >>> See prior mailing list discussions here: >>> >>> * >>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html >>> * >>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html >>> >>> Thanks to the many developers who have provided feedback on iterations >>> of this design. >>> >>> Best, >>> >>> Jeremy >>> >>> -- >>> @JeremyRubin <https://twitter.com/JeremyRubin> >>> >> [-- Attachment #2: Type: text/html, Size: 38780 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2019-12-11 0:37 ` Jeremy @ 2019-12-13 23:06 ` Jeremy 2019-12-19 20:08 ` Jeremy [not found] ` <20191214122546.5e72eb93@simplexum.com> 0 siblings, 2 replies; 17+ messages in thread From: Jeremy @ 2019-12-13 23:06 UTC (permalink / raw) To: Jeremy; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 521 bytes --] I've prepared a draft of the changes noted above (some small additional modifications on the StandardTemplateHash described in the BIP), but have not yet updated the main branches for the BIP to leave time for any further feedback. See below: BIP: https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki Implementation: https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2 Thank you for your feedback, Jeremy -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> [-- Attachment #2: Type: text/html, Size: 2194 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2019-12-13 23:06 ` Jeremy @ 2019-12-19 20:08 ` Jeremy [not found] ` <20191214122546.5e72eb93@simplexum.com> 1 sibling, 0 replies; 17+ messages in thread From: Jeremy @ 2019-12-19 20:08 UTC (permalink / raw) To: Jeremy; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1279 bytes --] I've updated the main branch (ctv) to match ctv-v2, and pushed branches ctv-v1 which points at the prior versions. Thanks to Dmitry Petukhov for helping me fix several typos and errors. I also wanted to share some some "non-technical" tax analysis covering the use of OP_CTV for batched payments. See here: https://utxos.org/analysis/taxes/ As an aside, the site https://utxos.org/ generally is a repository of information & material on OP_CTV, it's design, applications, and analysis. If you're interested in contributing any content please let me know! Best, Jeremy -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Fri, Dec 13, 2019 at 3:06 PM Jeremy <jlrubin@mit•edu> wrote: > I've prepared a draft of the changes noted above (some small additional > modifications on the StandardTemplateHash described in the BIP), but have > not yet updated the main branches for the BIP to leave time for any further > feedback. > > See below: > > BIP: https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki > Implementation: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2 > > Thank you for your feedback, > > Jeremy > -- > @JeremyRubin <https://twitter.com/JeremyRubin> > <https://twitter.com/JeremyRubin> > > [-- Attachment #2: Type: text/html, Size: 4880 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
[parent not found: <20191214122546.5e72eb93@simplexum.com>]
[parent not found: <CAD5xwhgwhOwuPjKz-0_y7HP=jTi=6wJo8uH6HqCvOndr6wo0+Q@mail.gmail.com>]
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY [not found] ` <CAD5xwhgwhOwuPjKz-0_y7HP=jTi=6wJo8uH6HqCvOndr6wo0+Q@mail.gmail.com> @ 2020-02-14 11:18 ` Dmitry Petukhov 2020-02-14 19:16 ` Jeremy 2020-02-15 0:24 ` ZmnSCPxj 0 siblings, 2 replies; 17+ messages in thread From: Dmitry Petukhov @ 2020-02-14 11:18 UTC (permalink / raw) To: Jeremy, Bitcoin Protocol Discussion I decided to take this thread back on-list because I beleive that the 'revocation utxo' feature enabled by OP_CTV commiting to scriptSig may have wider implications that can slightly change the behavior of Bitcoin as a system, and some might not expect such changes or might not find them desireable (although there is already a case for such behaviour with RBF). There is a principle that some find valuable: "During reorgs of depth less than 100, it is always possible to eventually replay transactions from the old branch into the new branch as long as no double spends are attempted" (quoted from Russel O'Connor from the discussion about 'revocation utxo' on Elements Slack channel). As far as I can tell, this principle can be violated with the use of RBF: "(tx) that was included in branch A and then RBF-ed (tx') in branch B and then branch A wins -> children of (tx') can't be replayed" Some may hold an opinion that introducing new rules that violate that principle should be done with caution. The 'revocation utxo' feature enabled by OP_CTV essentially introduces a manually triggered 'inverse timelock' - normal timelocks make tx invalid until certain point in time, and inverse timelock make tx invalid _after_ certain point in time, in this case by spending an unrelated UTXO. In a reorg, one branch can have that UTXO spent before the OP_CTV transaction that depends on it is included in the block, and the OP_CTV transaction and its children can't be replayed. This is the same issue as an 'automatic inverse timelock' that could be enforced by the structure of the transaction itself, if there was appropriate mechanism, with the difference that 'revocation utxo' is manually triggered. The absense of 'automatic inverse timelock' mechanism in Bitcoin hints that it was not seen as desireable historically. I was not able to find the relevant discussions, though. I would like to add that the behaviour enabled by inverse timelocks could be useable in various schemes with covenants, like the vaults with access revocable by spending the 'revocation utxo', or in the trustless lending schemes where the covenant scripts can enforce different amounts of interest paid to lender based on the point in time when the loan is returned - the obsolete script paths (with smaller interest paid) can be disabled by inverse timelock. В Fri, 13 Dec 2019 23:37:19 -0800 Jeremy <jlrubin@mit•edu> wrote: > That's a cool use case. I've thought previously about an > OP_CHECKINPUT, as a separate extension. Will need to think about if > your construction introduces a hash cycle (unless > SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely). > > Also re signatures I think it's definitely possible to pick a > (signature, message) pair and generate a pk from it, but in general > the Bitcoin message commits to the pk so forging isn't possible. > > On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov <dp@simplexum•com> > wrote: > > > Another idea for smart vaults: > > > > The ability to commit to scriptSig of a non-segwit input could be > > used for on-chain control of spending authorization (revoking the > > spending authorization), where CTV ensures that certain input is > > present in the transaction. > > > > scriptSig of that input can contain a signature that commits to > > certain prevout. Unless it is possible to forge an identical > > signature (and I don't know how strong are guarantees of that), > > such an input can only be valid if that prevout was not spent. > > > > Thus spending such prevout makes it impossible to spend the input > > with CTV that commits to such scriptSig, in effect revoking an > > ability to spend this input via CTV path, and alternate spending > > paths should be used (like, another taproot branch) > > > > > > В Fri, 13 Dec 2019 15:06:59 -0800 > > Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> > > пишет: > > > I've prepared a draft of the changes noted above (some small > > > additional modifications on the StandardTemplateHash described in > > > the BIP), but have not yet updated the main branches for the BIP > > > to leave time for any further feedback. > > > > > > See below: > > > > > > BIP: > > > https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki > > > Implementation: > > > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2 > > > > > > Thank you for your feedback, > > > > > > Jeremy > > > -- > > > @JeremyRubin <https://twitter.com/JeremyRubin> > > > <https://twitter.com/JeremyRubin> > > > > ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-02-14 11:18 ` Dmitry Petukhov @ 2020-02-14 19:16 ` Jeremy 2020-09-03 14:42 ` Dmitry Petukhov 2020-02-15 0:24 ` ZmnSCPxj 1 sibling, 1 reply; 17+ messages in thread From: Jeremy @ 2020-02-14 19:16 UTC (permalink / raw) To: Dmitry Petukhov; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 9161 bytes --] Hi Dmitry, I don't think that this is fundamentally introducing new behavior, but let's take a closer look. We can talk about the issue you bring up purely in terms of a hypothetical "OP_CHECKINPUTOUTPOINTVERIFY" and "OP_CHECKINPUTSCRIPTVERIFY" (CIOV, CISV) with obvious implied by name semantics, as a separate construct from CTV itself. Such opcodes would be strictly more powerful/flexible than what CTV is enabling. Using these opcodes I can make an output that can *only* be spent with another output -- e.g., <s> <n> OP_CISV OP_DROP <pk> OP_CHECKSIGVERIFY <h, i> <n> OP_CIOV OP_DROP <pk> OP_CHECKSIGVERIFY Let's look at CISV first: 1) Assume that <s> is from the same owner as PK 2) Assume that <s> is from a different owner than PK In case 1, the wallet can create or recreate the appropriate output as needed if it gets spent/stuck In case 2, the wallet can get "frozen" in a reorg until a signer on <s> re-spends. For CIOV: 1) Assume that <h, i> exists in the chain somewhere 2) Assume that <h, i> exists in the mempool somewhere 3) Assume that <h, i> does not exist (or, is provably non-creatable -- h = txid(x) | x.IsValid() == false) In case 2, this is just a fancy op-return. Case 1 degrades into case 2 in the event of a reorg. In Case 2, if the output <h, i> is spent in another transaction, our script becomes provably unspendable (unless a second reorg). Otherwise, it is possible to mine a block with our transaction. Compare the above to normal transactions: 1) If a reorg occurs, and someone double-spends, your transaction gets cancelled. 2) You can re-sign your UTXO onto a different transaction However, if you have deleted your key (e.g. using a pre-signing HSM), or your transaction was using a multi-sig with an uncooperating party, you will have an output that may be effectively burned. These issues are -- as with CTV -- not present in the single input use case. Thus I argue that CTV -- whose semantics are less powerful/flexible than CISV/CIOV -- aren't introducing something that's not already present when doing protocols involving more than one input. Further, on CTV "monotonic authorization": Generally we want Bitcoin Scripts to have the property that once a condition is reached, it is 'permanently' a true case. E.g., showing a hash preimage to C x, H(x) == C. This can't change with the weather or anything else. Even things like timelocks -- although not obvious at first glance -- have this property. They express logic that says "given the chain is at this height, ...". This means that on any chain at such a height the txn is valid. CISV/CIOV semantics also fall in line with this description. It says, "given such an input U, ...". If that input is realizable one time, it is provably realizable across reorgs. However, that doesn't mean someone couldn't interrupt U from being created. But generally, with Reorg + Double spend, or Reorg > 100 blocks (potentially destroying CB reward), all bets are off as to the replay-ability of transactions. I want to also point out that this "revocation" property -- to the extent it is something new that can't already be emulated with pre-signeds or RBF -- is entirely opt-in as far as CTV is concerned. You have to specify that an output can only be spent with another, most wallets shouldn't do that, and it can't "infect" other wallets to an extent more than spending from any recently confirmed output exposes you to more reorg risk. *In sum, we do not need to worry about this for CTV.* Lastly, I want to note that revocation is part of what CTV is designed to do (absent reorgs). It allows us to prune spending conditions by playing a transaction forward. E.g., spending conditions {Alice & Bob, Preimage(H(X)) + Eve, CTV({Alice & Bob}, 1 day)} Expresses that Eve has 1 day to reveal the preimage to H(X), otherwise Alice and Bob can take the coin back by removing Eve's HTLC path. What's cool about this revocation v.s. just {Alice & Bob, Preimage(H(X)) + Eve} is that Alice and Bob don't need to coordinate a multisig to revoke Eve. -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Fri, Feb 14, 2020 at 3:17 AM Dmitry Petukhov <dp@simplexum•com> wrote: > I decided to take this thread back on-list because I beleive that the > 'revocation utxo' feature enabled by OP_CTV commiting to scriptSig may > have wider implications that can slightly change the behavior of Bitcoin > as a system, and some might not expect such changes or might not find > them desireable (although there is already a case for such behaviour > with RBF). > > There is a principle that some find valuable: "During reorgs of depth > less than 100, it is always possible to eventually replay transactions > from the old branch into the new branch as long as no double spends are > attempted" (quoted from Russel O'Connor from the discussion about > 'revocation utxo' on Elements Slack channel). > > As far as I can tell, this principle can be violated with the use of > RBF: "(tx) that was included in branch A and then RBF-ed (tx') in branch > B and then branch A wins -> children of (tx') can't be replayed" > > Some may hold an opinion that introducing new rules that violate that > principle should be done with caution. > > The 'revocation utxo' feature enabled by OP_CTV essentially introduces > a manually triggered 'inverse timelock' - normal timelocks make tx > invalid until certain point in time, and inverse timelock make tx > invalid _after_ certain point in time, in this case by spending an > unrelated UTXO. > > In a reorg, one branch can have that UTXO spent before the OP_CTV > transaction that depends on it is included in the block, and the OP_CTV > transaction and its children can't be replayed. > > This is the same issue as an 'automatic inverse timelock' that could > be enforced by the structure of the transaction itself, if there was > appropriate mechanism, with the difference that 'revocation utxo' is > manually triggered. > > The absense of 'automatic inverse timelock' mechanism in Bitcoin hints > that it was not seen as desireable historically. I was not able to find > the relevant discussions, though. > > I would like to add that the behaviour enabled by inverse timelocks > could be useable in various schemes with covenants, like the vaults > with access revocable by spending the 'revocation utxo', or in the > trustless lending schemes where the covenant scripts can enforce > different amounts of interest paid to lender based on the point in time > when the loan is returned - the obsolete script paths (with smaller > interest paid) can be disabled by inverse timelock. > > В Fri, 13 Dec 2019 23:37:19 -0800 > Jeremy <jlrubin@mit•edu> wrote: > > > That's a cool use case. I've thought previously about an > > OP_CHECKINPUT, as a separate extension. Will need to think about if > > your construction introduces a hash cycle (unless > > SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely). > > > > Also re signatures I think it's definitely possible to pick a > > (signature, message) pair and generate a pk from it, but in general > > the Bitcoin message commits to the pk so forging isn't possible. > > > > On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov <dp@simplexum•com> > > wrote: > > > > > Another idea for smart vaults: > > > > > > The ability to commit to scriptSig of a non-segwit input could be > > > used for on-chain control of spending authorization (revoking the > > > spending authorization), where CTV ensures that certain input is > > > present in the transaction. > > > > > > scriptSig of that input can contain a signature that commits to > > > certain prevout. Unless it is possible to forge an identical > > > signature (and I don't know how strong are guarantees of that), > > > such an input can only be valid if that prevout was not spent. > > > > > > Thus spending such prevout makes it impossible to spend the input > > > with CTV that commits to such scriptSig, in effect revoking an > > > ability to spend this input via CTV path, and alternate spending > > > paths should be used (like, another taproot branch) > > > > > > > > > В Fri, 13 Dec 2019 15:06:59 -0800 > > > Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> > > > пишет: > > > > I've prepared a draft of the changes noted above (some small > > > > additional modifications on the StandardTemplateHash described in > > > > the BIP), but have not yet updated the main branches for the BIP > > > > to leave time for any further feedback. > > > > > > > > See below: > > > > > > > > BIP: > > > > https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki > > > > Implementation: > > > > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2 > > > > > > > > Thank you for your feedback, > > > > > > > > Jeremy > > > > -- > > > > @JeremyRubin <https://twitter.com/JeremyRubin> > > > > <https://twitter.com/JeremyRubin> > > > > > > > > [-- Attachment #2: Type: text/html, Size: 18385 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-02-14 19:16 ` Jeremy @ 2020-09-03 14:42 ` Dmitry Petukhov 2020-09-03 17:34 ` Jeremy 0 siblings, 1 reply; 17+ messages in thread From: Dmitry Petukhov @ 2020-09-03 14:42 UTC (permalink / raw) To: Jeremy; +Cc: Bitcoin Protocol Discussion Just had an idea that an an "inverse timelock" can be made almost-certainly automatic: a revocation UTXO shall become anyone-can-spend after a timeout, and bear some non-dust amount. Before the timelock expiration, it shall be spendable only along with the covenant-locked 'main' UTXO (via a signature or mutual covenant) This way, after a timeout expires, a multitude of entities will be incentivized to spend this UTXO, because this would be free money for them. It will probably be spend by a miner, as they can always replace the spending transaction with their own and claim the amount. After the revocation UTXO is spent, the covenant path that commits to having it in the inputs will be unspendable, and this would effectively constitute an "inverse timelock". В Fri, 14 Feb 2020 11:16:26 -0800 Jeremy <jlrubin@mit•edu> wrote: > Hi Dmitry, > > I don't think that this is fundamentally introducing new behavior, but > let's take a closer look. > > We can talk about the issue you bring up purely in terms of a > hypothetical "OP_CHECKINPUTOUTPOINTVERIFY" and > "OP_CHECKINPUTSCRIPTVERIFY" (CIOV, CISV) with obvious implied by name > semantics, as a separate construct from CTV itself. Such opcodes > would be strictly more powerful/flexible than what CTV is enabling. > > Using these opcodes I can make an output that can *only* be spent with > another output -- e.g., > > <s> <n> OP_CISV OP_DROP <pk> OP_CHECKSIGVERIFY > <h, i> <n> OP_CIOV OP_DROP <pk> OP_CHECKSIGVERIFY > > Let's look at CISV first: > > 1) Assume that <s> is from the same owner as PK > 2) Assume that <s> is from a different owner than PK > > In case 1, the wallet can create or recreate the appropriate output as > needed if it gets spent/stuck > > In case 2, the wallet can get "frozen" in a reorg until a signer on > <s> re-spends. > > > For CIOV: > > 1) Assume that <h, i> exists in the chain somewhere > 2) Assume that <h, i> exists in the mempool somewhere > 3) Assume that <h, i> does not exist (or, is provably non-creatable > -- h = txid(x) | x.IsValid() == false) > > In case 2, this is just a fancy op-return. > > Case 1 degrades into case 2 in the event of a reorg. > > In Case 2, if the output <h, i> is spent in another transaction, our > script becomes provably unspendable (unless a second reorg). > > Otherwise, it is possible to mine a block with our transaction. > > > Compare the above to normal transactions: > > 1) If a reorg occurs, and someone double-spends, your transaction gets > cancelled. > 2) You can re-sign your UTXO onto a different transaction > > However, if you have deleted your key (e.g. using a pre-signing HSM), > or your transaction was using a multi-sig with an uncooperating > party, you will have an output that may be effectively burned. > > These issues are -- as with CTV -- not present in the single input > use case. > > Thus I argue that CTV -- whose semantics are less powerful/flexible > than CISV/CIOV -- aren't introducing something that's not already > present when doing protocols involving more than one input. > > Further, on CTV "monotonic authorization": > > Generally we want Bitcoin Scripts to have the property that once a > condition is reached, it is 'permanently' a true case. E.g., showing > a hash preimage to C x, H(x) == C. This can't change with the weather > or anything else. Even things like timelocks -- although not obvious > at first glance -- have this property. They express logic that says > "given the chain is at this height, ...". This means that on any > chain at such a height the txn is valid. CISV/CIOV semantics also > fall in line with this description. It says, "given such an input U, > ...". If that input is realizable one time, it is provably realizable > across reorgs. However, that doesn't mean someone couldn't interrupt > U from being created. But generally, with Reorg + Double spend, or > Reorg > 100 blocks (potentially destroying CB reward), all bets are > off as to the replay-ability of transactions. > > I want to also point out that this "revocation" property -- to the > extent it is something new that can't already be emulated with > pre-signeds or RBF -- is entirely opt-in as far as CTV is concerned. > You have to specify that an output can only be spent with another, > most wallets shouldn't do that, and it can't "infect" other wallets > to an extent more than spending from any recently confirmed output > exposes you to more reorg risk. > > *In sum, we do not need to worry about this for CTV.* > > > Lastly, I want to note that revocation is part of what CTV is > designed to do (absent reorgs). It allows us to prune spending > conditions by playing a transaction forward. > > E.g., spending conditions {Alice & Bob, Preimage(H(X)) + Eve, > CTV({Alice & Bob}, 1 day)} > > Expresses that Eve has 1 day to reveal the preimage to H(X), otherwise > Alice and Bob can take the coin back by removing Eve's HTLC path. > What's cool about this revocation v.s. just {Alice & Bob, > Preimage(H(X)) + Eve} is that Alice and Bob don't need to coordinate > a multisig to revoke Eve. > > > > -- > @JeremyRubin <https://twitter.com/JeremyRubin> > <https://twitter.com/JeremyRubin> > > > On Fri, Feb 14, 2020 at 3:17 AM Dmitry Petukhov <dp@simplexum•com> > wrote: > > > I decided to take this thread back on-list because I beleive that > > the 'revocation utxo' feature enabled by OP_CTV commiting to > > scriptSig may have wider implications that can slightly change the > > behavior of Bitcoin as a system, and some might not expect such > > changes or might not find them desireable (although there is > > already a case for such behaviour with RBF). > > > > There is a principle that some find valuable: "During reorgs of > > depth less than 100, it is always possible to eventually replay > > transactions from the old branch into the new branch as long as no > > double spends are attempted" (quoted from Russel O'Connor from the > > discussion about 'revocation utxo' on Elements Slack channel). > > > > As far as I can tell, this principle can be violated with the use of > > RBF: "(tx) that was included in branch A and then RBF-ed (tx') in > > branch B and then branch A wins -> children of (tx') can't be > > replayed" > > > > Some may hold an opinion that introducing new rules that violate > > that principle should be done with caution. > > > > The 'revocation utxo' feature enabled by OP_CTV essentially > > introduces a manually triggered 'inverse timelock' - normal > > timelocks make tx invalid until certain point in time, and inverse > > timelock make tx invalid _after_ certain point in time, in this > > case by spending an unrelated UTXO. > > > > In a reorg, one branch can have that UTXO spent before the OP_CTV > > transaction that depends on it is included in the block, and the > > OP_CTV transaction and its children can't be replayed. > > > > This is the same issue as an 'automatic inverse timelock' that could > > be enforced by the structure of the transaction itself, if there was > > appropriate mechanism, with the difference that 'revocation utxo' is > > manually triggered. > > > > The absense of 'automatic inverse timelock' mechanism in Bitcoin > > hints that it was not seen as desireable historically. I was not > > able to find the relevant discussions, though. > > > > I would like to add that the behaviour enabled by inverse timelocks > > could be useable in various schemes with covenants, like the vaults > > with access revocable by spending the 'revocation utxo', or in the > > trustless lending schemes where the covenant scripts can enforce > > different amounts of interest paid to lender based on the point in > > time when the loan is returned - the obsolete script paths (with > > smaller interest paid) can be disabled by inverse timelock. > > > > В Fri, 13 Dec 2019 23:37:19 -0800 > > Jeremy <jlrubin@mit•edu> wrote: > > > > > That's a cool use case. I've thought previously about an > > > OP_CHECKINPUT, as a separate extension. Will need to think about > > > if your construction introduces a hash cycle (unless > > > SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely). > > > > > > Also re signatures I think it's definitely possible to pick a > > > (signature, message) pair and generate a pk from it, but in > > > general the Bitcoin message commits to the pk so forging isn't > > > possible. > > > > > > On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov <dp@simplexum•com> > > > wrote: > > > > > > > Another idea for smart vaults: > > > > > > > > The ability to commit to scriptSig of a non-segwit input could > > > > be used for on-chain control of spending authorization > > > > (revoking the spending authorization), where CTV ensures that > > > > certain input is present in the transaction. > > > > > > > > scriptSig of that input can contain a signature that commits to > > > > certain prevout. Unless it is possible to forge an identical > > > > signature (and I don't know how strong are guarantees of that), > > > > such an input can only be valid if that prevout was not spent. > > > > > > > > Thus spending such prevout makes it impossible to spend the > > > > input with CTV that commits to such scriptSig, in effect > > > > revoking an ability to spend this input via CTV path, and > > > > alternate spending paths should be used (like, another taproot > > > > branch) > > > > > > > > > > > > В Fri, 13 Dec 2019 15:06:59 -0800 > > > > Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> > > > > пишет: > > > > > I've prepared a draft of the changes noted above (some small > > > > > additional modifications on the StandardTemplateHash > > > > > described in the BIP), but have not yet updated the main > > > > > branches for the BIP to leave time for any further feedback. > > > > > > > > > > See below: > > > > > > > > > > BIP: > > > > > https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki > > > > > Implementation: > > > > > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2 > > > > > > > > > > Thank you for your feedback, > > > > > > > > > > Jeremy > > > > > -- > > > > > @JeremyRubin <https://twitter.com/JeremyRubin> > > > > > <https://twitter.com/JeremyRubin> > > > > > > > > > > > > ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-09-03 14:42 ` Dmitry Petukhov @ 2020-09-03 17:34 ` Jeremy 2020-09-03 17:47 ` Jeremy 0 siblings, 1 reply; 17+ messages in thread From: Jeremy @ 2020-09-03 17:34 UTC (permalink / raw) To: Dmitry Petukhov; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1104 bytes --] CTV does not enable this afaiu because it does not commit to the inputs (otherwise there's a hash cycle for predicting the output's TXID. -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Thu, Sep 3, 2020 at 7:39 AM Dmitry Petukhov <dp@simplexum•com> wrote: > Just had an idea that an an "inverse timelock" can be made > almost-certainly automatic: a revocation UTXO shall become > anyone-can-spend after a timeout, and bear some non-dust amount. > > Before the timelock expiration, it shall be spendable only along with > the covenant-locked 'main' UTXO (via a signature or mutual covenant) > > This way, after a timeout expires, a multitude of entities will be > incentivized to spend this UTXO, because this would be free money for > them. It will probably be spend by a miner, as they can always replace > the spending transaction with their own and claim the amount. > > After the revocation UTXO is spent, the covenant path that commits to > having it in the inputs will be unspendable, and this would effectively > constitute an "inverse timelock". > > > [-- Attachment #2: Type: text/html, Size: 2008 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-09-03 17:34 ` Jeremy @ 2020-09-03 17:47 ` Jeremy 0 siblings, 0 replies; 17+ messages in thread From: Jeremy @ 2020-09-03 17:47 UTC (permalink / raw) To: Jeremy; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 1489 bytes --] It's also not something that's trivial to set up in any scheme because you have to have an ordering around when you set up the tx intended to be the inverse lock before you create the tx using it. -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Thu, Sep 3, 2020 at 10:34 AM Jeremy <jlrubin@mit•edu> wrote: > CTV does not enable this afaiu because it does not commit to the inputs > (otherwise there's a hash cycle for predicting the output's TXID. > > > -- > @JeremyRubin <https://twitter.com/JeremyRubin> > <https://twitter.com/JeremyRubin> > > > On Thu, Sep 3, 2020 at 7:39 AM Dmitry Petukhov <dp@simplexum•com> wrote: > >> Just had an idea that an an "inverse timelock" can be made >> almost-certainly automatic: a revocation UTXO shall become >> anyone-can-spend after a timeout, and bear some non-dust amount. >> >> Before the timelock expiration, it shall be spendable only along with >> the covenant-locked 'main' UTXO (via a signature or mutual covenant) >> >> This way, after a timeout expires, a multitude of entities will be >> incentivized to spend this UTXO, because this would be free money for >> them. It will probably be spend by a miner, as they can always replace >> the spending transaction with their own and claim the amount. >> >> After the revocation UTXO is spent, the covenant path that commits to >> having it in the inputs will be unspendable, and this would effectively >> constitute an "inverse timelock". >> >> >> [-- Attachment #2: Type: text/html, Size: 3083 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-02-14 11:18 ` Dmitry Petukhov 2020-02-14 19:16 ` Jeremy @ 2020-02-15 0:24 ` ZmnSCPxj 1 sibling, 0 replies; 17+ messages in thread From: ZmnSCPxj @ 2020-02-15 0:24 UTC (permalink / raw) To: Dmitry Petukhov, Bitcoin Protocol Discussion Good morning Dmitry, and Jeremy, > There is a principle that some find valuable: "During reorgs of depth > less than 100, it is always possible to eventually replay transactions > from the old branch into the new branch as long as no double spends are > attempted" (quoted from Russel O'Connor from the discussion about > 'revocation utxo' on Elements Slack channel). > > As far as I can tell, this principle can be violated with the use of > RBF: "(tx) that was included in branch A and then RBF-ed (tx') in branch > B and then branch A wins -> children of (tx') can't be replayed" But an RBF-ed transaction *is* a double-spend, and the principle makes an exception specifically for double-spends. Thus RBF, and other double-spends, are exempt from this principle. My vague understanding of the "revocation UTXO" feature is that it is implemented as a double-spend of a precommitted `OP_CTV`, so that also is exempted from the principle. As Jeremy notes as well, the *actual* principle is that "a script that is valid now remains valid in the future" (as this is required by the script cache implementation of Bitcoin Core), and this principle does not mention UTXOs, only scripts; the existence or non-existence of a required UTXO is separate here. Thus, an "automatic inverse timelock" is not possible to implement with **only** script (it implies that a script that is valid now will become invalid in the future), but requires some action on the blockchain (notice that HTLCs effectively implement an "inverse timelock" on the hash-branch participant, by threatening a spend (i.e. blockchain activity) by the counterparty if does not comply). Regards, ZmnSCPxj > > Some may hold an opinion that introducing new rules that violate that > principle should be done with caution. > > The 'revocation utxo' feature enabled by OP_CTV essentially introduces > a manually triggered 'inverse timelock' - normal timelocks make tx > invalid until certain point in time, and inverse timelock make tx > invalid after certain point in time, in this case by spending an > unrelated UTXO. > > In a reorg, one branch can have that UTXO spent before the OP_CTV > transaction that depends on it is included in the block, and the OP_CTV > transaction and its children can't be replayed. > > This is the same issue as an 'automatic inverse timelock' that could > be enforced by the structure of the transaction itself, if there was > appropriate mechanism, with the difference that 'revocation utxo' is > manually triggered. > > The absense of 'automatic inverse timelock' mechanism in Bitcoin hints > that it was not seen as desireable historically. I was not able to find > the relevant discussions, though. > > I would like to add that the behaviour enabled by inverse timelocks > could be useable in various schemes with covenants, like the vaults > with access revocable by spending the 'revocation utxo', or in the > trustless lending schemes where the covenant scripts can enforce > different amounts of interest paid to lender based on the point in time > when the loan is returned - the obsolete script paths (with smaller > interest paid) can be disabled by inverse timelock. > > В Fri, 13 Dec 2019 23:37:19 -0800 > Jeremy jlrubin@mit•edu wrote: > > > That's a cool use case. I've thought previously about an > > OP_CHECKINPUT, as a separate extension. Will need to think about if > > your construction introduces a hash cycle (unless > > SIGHASH_ALL|SIGHASH_ANYONECANPAY is used it seems likely). > > Also re signatures I think it's definitely possible to pick a > > (signature, message) pair and generate a pk from it, but in general > > the Bitcoin message commits to the pk so forging isn't possible. > > On Fri, Dec 13, 2019, 11:25 PM Dmitry Petukhov dp@simplexum•com > > wrote: > > > > > Another idea for smart vaults: > > > The ability to commit to scriptSig of a non-segwit input could be > > > used for on-chain control of spending authorization (revoking the > > > spending authorization), where CTV ensures that certain input is > > > present in the transaction. > > > scriptSig of that input can contain a signature that commits to > > > certain prevout. Unless it is possible to forge an identical > > > signature (and I don't know how strong are guarantees of that), > > > such an input can only be valid if that prevout was not spent. > > > Thus spending such prevout makes it impossible to spend the input > > > with CTV that commits to such scriptSig, in effect revoking an > > > ability to spend this input via CTV path, and alternate spending > > > paths should be used (like, another taproot branch) > > > В Fri, 13 Dec 2019 15:06:59 -0800 > > > Jeremy via bitcoin-dev bitcoin-dev@lists•linuxfoundation.org > > > пишет: > > > > > > > I've prepared a draft of the changes noted above (some small > > > > additional modifications on the StandardTemplateHash described in > > > > the BIP), but have not yet updated the main branches for the BIP > > > > to leave time for any further feedback. > > > > See below: > > > > BIP: > > > > https://github.com/JeremyRubin/bips/blob/ctv-v2/bip-ctv.mediawiki > > > > Implementation: > > > > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-v2 > > > > Thank you for your feedback, > > > > > > > > Jeremy > > > > > > > > ------- > > > > > > > > @JeremyRubin https://twitter.com/JeremyRubin > > > > https://twitter.com/JeremyRubin > > bitcoin-dev mailing list > bitcoin-dev@lists•linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2019-11-26 1:50 [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY Jeremy 2019-11-27 21:32 ` Russell O'Connor @ 2020-06-07 16:51 ` Joachim Strömbergson 2020-06-07 22:45 ` Jeremy 1 sibling, 1 reply; 17+ messages in thread From: Joachim Strömbergson @ 2020-06-07 16:51 UTC (permalink / raw) To: Jeremy, Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 4208 bytes --] Hello everyone, regarding OP_CTV, I am considering the scaling use case, specifically an exchange (or similar) who wants to batch pay to OP_CTV to many users, and I wonder 1) How do you expect the exchange to communicate the proof of the payment to the user wallets such that they are able to construct the follow up transactions and accept the payment. This is UI question. Do you expect exchanges to provide a certain importable file/blob that the wallet will allow you to entry? 2) Who pays the fees and how for the transaction within the structure that OP_CTVed output is committed to? Say there is a tree structure and I want to get the coin out. Someone needs to send log(N) transactions to the chain in order for me to get access to the final UTXO I am interested in. Who can construct such transaction path and what do they need for it and who pays fees on that (which input)? 3) Depending on 2) above, is it not possible for a malicious entity who is among the many users being paid, but who has very small UTXO there relative to others, to construct this middle transaction and use a very small fee rate in order to DoS other participants. Is it even possible for this attacker to create the middle transaction with RBF disabled? Thank you, Joachim Sent with [ProtonMail](https://protonmail.com) Secure Email. ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ On Tuesday, November 26, 2019 1:50 AM, Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > Bitcoin Developers, > > Pleased to announce refinements to the BIP draft for OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily: > > 1) Changed the name to something more fitting and acceptable to the community > 2) Changed the opcode specification to use the argument off of the stack with a primitive constexpr/literal tracker rather than script lookahead > 3) Permits future soft-fork updates to loosen or remove "constexpr" restrictions > 4) More detailed comparison to alternatives in the BIP, and why OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may make it semi-redundant. > > Please see: > BIP:https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki > Reference Implementation:https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify > > I believe this addresses all outstanding feedback on the design of this opcode, unless there are any new concerns with these changes. > > I'm also planning to host a review workshop in Q1 2020, most likely in San Francisco. Please fill out the form here https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in participating (even if you can't physically attend). > > And as a "but wait, there's more": > > 1) RPC functions are under preliminary development, to aid in testing and evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted` shows one way to use OP_CHECKTEMPLATEVERIFY. See: https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. `sendmanycompacted` is still under early design. Standard practices for using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a separate BIP. This work generalizes even if an alternative strategy is used to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. > 2) Also under development are improvements to the mempool which will, in conjunction with improvements like package relay, help make it safe to lift some of the mempool's restrictions on longchains specifically for OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's fate. > > Neither of these are blockers for proceeding with the BIP, as they are ergonomics and usability improvements needed once/if the BIP is activated. > > See prior mailing list discussions here: > > * https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html > * https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html > > Thanks to the many developers who have provided feedback on iterations of this design. > > Best, > > Jeremy > -- > [@JeremyRubin](https://twitter.com/JeremyRubin)https://twitter.com/JeremyRubin [-- Attachment #2: Type: text/html, Size: 9164 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-06-07 16:51 ` Joachim Strömbergson @ 2020-06-07 22:45 ` Jeremy 2020-06-08 6:05 ` Dmitry Petukhov 0 siblings, 1 reply; 17+ messages in thread From: Jeremy @ 2020-06-07 22:45 UTC (permalink / raw) To: Joachim Strömbergson; +Cc: Bitcoin Protocol Discussion [-- Attachment #1: Type: text/plain, Size: 10145 bytes --] Hi Joachim, Fantastic questions! I think it makes sense to think about it in terms of today, and then in terms of a long-dated future where wallets have much richer native understandings of these things. This helps preserve the purity of the arguments I'm making with respect to what it would look like today v.s. what it could look like with strong integration. Today: 1) I would expect that exchanges do this as a CTV txn that is one initial confirmation to a single output, and then that output expands to either all the payments in the batch, or to a histogram of single-layer CTVs based on priority/amount being spent. E.g, either A -> B -> {C,D,E,F,G...} or A->B->{C -> {D,E,F}, G -> {H, I J}, K -> ....}. I would further expect that the entire tree would include fees such that it will get into at least the bottom of the mempool. See https://utxos.org/analysis/batching_sim/ for more info. If txns land in the mempool, then users learn about it (even with an un-updated wallet) just like the learn of normal unconfirmed transactions. Even this simple two-step transaction can deliver massive batching savings. OpTech has some coverage of this simple commit-now-distribute-later scheme here https://bitcoinops.org/en/newsletters/2019/05/29/#proposed-new-opcode-for-transaction-output-commitments . I'd also expect that exchanges in particular already store their outbound transactions in resilient storage (for audit and compliance as well as liability protection), so they would likely be able to make this data available to their customers on inquiry if discarded. I'm all for redundancy, so exchanges can also e.g. send an email with a backup file if they want to. But that's not necessary for it to work today, you can just watch the mempool like wallets already do. A slightly patched wallet can treat CTV outs as more confirmed (e.g., like an own-change address) than a normal unconfirmed out. 2) I would expect that exchanges pay a reasonable amount of fees for the transaction so it can expect to at least get to the bottom range of the mempool for children, and top of the mempool for the parent. Your question seems to be more about after this phase. First I would note that it is truly O(log(N)), but E[O(1)], because it amortizes. That is, to claim out all of the outputs is a total overhead of O(N), not O(N log N). Fees in this model are paid by CPFP. Because CPFP is currently *Child* pays for parent and not *Children* pay for parent, we don't (unfortunately) have rational txn selection for this case. Any wallet can construct this spend path by rebroadcasting (if evicted) the parents and spending the txn. The exchange can also 'bound' themselves to seeing a transaction to completion by including some change address at the leaf node layer (not much overhead depending on radix). Thus the payer of fees is the person who needs to spend. 3) Not exactly, the middle txns are immutable. but it may be possible to construct a low-fee longchain which can cause transaction pinning. If you do a shallow tree as described in (1), the current lightning carve should help to prevent this. Future: 1) Most likely the desirable radix for a tree is something like 4 or 5 which minimizes the amount of work on an individual basis (you can compute this by figuring out how deep the tree would be and the per-tx overheads, 4 or 5 pop out as being minimal overhead and the benefit is recursive). Mempool broadcast still should work, but it's possible that for privacy reasons it's preferred to not broadcast through mempool. It's also possible that all payouts are into non-interactive lightning channels with N-of-N taproot at each layer, so you receive a proof through your lightning wallet and can immediately route payments, and when you want to close opportunistically cooperate to reduce chain overhead. You can think of CTV as an anchor for bootstrapping these layer two protocols with an on-chain bisection algorithm to discover online participants to re-negotiate with. A privacy and scalability win! I further expect business wallets (like exchanges) to be able to credit deposits from CTV trees without requiring full expansion. This is also a privacy win, and can decrease latency of moving large value funds (e.g., exceeding inter exchange channel balances) and crediting funds for trading. 2) I think we'll eventually converge on a non-destructive way of adding fees. RBF is destructive in that you're replacing a TX. CPFP is destructive in that you have a spend a coin to drive progress. Without a new opcode you can emulate this with CTV by at nodes in the tree having a consumable output that serves as a CPFP hook/a RBF hook. You can see some discussion here (animated, so use pres mode) https://docs.google.com/presentation/d/1XDiZOz52XyJc4LDSbiD9_JAaJobyF5QDGtR3O9qD7yg/edit#slide=id.g7d267915e2_0_44. This adds some extra chain weight, but is possible without further extension. What I think we'll eventually land on is a way of doing a tx that contributes fee to another tx chain as a passive observer to them. While this breaks one abstraction around how dependencies between transactions are processed, it also could help resolve some really difficult challenges we face with application-DoS (pinning and other attacks) in the mempool beyond CTV. I have a napkin design for how this could work, but nothing quite ready to share yet. 3) Hopefully 2 solves pinning :) -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Sun, Jun 7, 2020 at 9:51 AM Joachim Strömbergson < joachimstr@protonmail•com> wrote: > Hello everyone, > > regarding OP_CTV, I am considering the scaling use case, specifically an > exchange (or similar) who wants to batch pay to OP_CTV to many users, and I > wonder > > 1) How do you expect the exchange to communicate the proof of the payment > to the user wallets such that they are able to construct the follow up > transactions and accept the payment. This is UI question. Do you expect > exchanges to provide a certain importable file/blob that the wallet will > allow you to entry? > > 2) Who pays the fees and how for the transaction within the structure that > OP_CTVed output is committed to? Say there is a tree structure and I want > to get the coin out. Someone needs to send log(N) transactions to the chain > in order for me to get access to the final UTXO I am interested in. Who can > construct such transaction path and what do they need for it and who pays > fees on that (which input)? > > 3) Depending on 2) above, is it not possible for a malicious entity who is > among the many users being paid, but who has very small UTXO there relative > to others, to construct this middle transaction and use a very small fee > rate in order to DoS other participants. Is it even possible for this > attacker to create the middle transaction with RBF disabled? > > Thank you, > Joachim > > > > Sent with ProtonMail <https://protonmail.com> Secure Email. > > ‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐ > On Tuesday, November 26, 2019 1:50 AM, Jeremy via bitcoin-dev < > bitcoin-dev@lists•linuxfoundation.org> wrote: > > Bitcoin Developers, > > Pleased to announce refinements to the BIP draft for > OP_CHECKTEMPLATEVERIFY (replaces previous OP_SECURETHEBAG BIP). Primarily: > > 1) Changed the name to something more fitting and acceptable to the > community > 2) Changed the opcode specification to use the argument off of the stack > with a primitive constexpr/literal tracker rather than script lookahead > 3) Permits future soft-fork updates to loosen or remove "constexpr" > restrictions > 4) More detailed comparison to alternatives in the BIP, and why > OP_CHECKTEMPLATEVERIFY should be favored even if a future technique may > make it semi-redundant. > > Please see: > BIP: https://github.com/JeremyRubin/bips/blob/ctv/bip-ctv.mediawiki > Reference Implementation: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify > > I believe this addresses all outstanding feedback on the design of this > opcode, unless there are any new concerns with these changes. > > I'm also planning to host a review workshop in Q1 2020, most likely in San > Francisco. Please fill out the form here > https://forms.gle/pkevHNj2pXH9MGee9 if you're interested in participating > (even if you can't physically attend). > > And as a "but wait, there's more": > > 1) RPC functions are under preliminary development, to aid in testing and > evaluation of OP_CHECKTEMPLATEVERIFY. The new command `sendmanycompacted` > shows one way to use OP_CHECKTEMPLATEVERIFY. See: > https://github.com/JeremyRubin/bitcoin/tree/checktemplateverify-rpcs. > `sendmanycompacted` is still under early design. Standard practices for > using OP_CHECKTEMPLATEVERIFY & wallet behaviors may be codified into a > separate BIP. This work generalizes even if an alternative strategy is used > to achieve the scalability techniques of OP_CHECKTEMPLATEVERIFY. > 2) Also under development are improvements to the mempool which will, in > conjunction with improvements like package relay, help make it safe to lift > some of the mempool's restrictions on longchains specifically for > OP_CHECKTEMPLATEVERIFY output trees. See: https://github.com/bitcoin/bitcoin/pull/17268 > This work offers an improvement irrespective of OP_CHECKTEMPLATEVERIFY's > fate. > > > Neither of these are blockers for proceeding with the BIP, as they are > ergonomics and usability improvements needed once/if the BIP is activated. > > See prior mailing list discussions here: > > * > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016934.html > * > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-June/016997.html > > > Thanks to the many developers who have provided feedback on iterations of > this design. > > Best, > > Jeremy > -- > @JeremyRubin <https://twitter.com/JeremyRubin> > <https://twitter.com/JeremyRubin> > > > [-- Attachment #2: Type: text/html, Size: 18698 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY 2020-06-07 22:45 ` Jeremy @ 2020-06-08 6:05 ` Dmitry Petukhov 2020-06-08 6:43 ` [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation Jeremy 0 siblings, 1 reply; 17+ messages in thread From: Dmitry Petukhov @ 2020-06-08 6:05 UTC (permalink / raw) To: Jeremy via bitcoin-dev В Sun, 7 Jun 2020 15:45:16 -0700 Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > What I think we'll eventually land on is a way of doing a tx > that contributes fee to another tx chain as a passive observer to > them. While this breaks one abstraction around how dependencies > between transactions are processed, it also could help resolve some > really difficult challenges we face with application-DoS (pinning and > other attacks) in the mempool beyond CTV. I have a napkin design for > how this could work, but nothing quite ready to share yet. I had an idea of 'Pay for neighbor' transaction where a transaction that is not directly a child of some other transaction can specify that it wants to pay the fee for that other transaction(s). It can become like 'ghost child' transaction for them, in what it cannot be mined unless its 'ghost parents' are confirmed, too. It will be like CPFP, but without direct dependency via inputs. Such 'PFN' transaction would not spend any coins beside what it specifies in its own inputs, of course. The idea required a hardfork at first, but Anthony Towns suggested a way to make it into a soft fork (past-taproot) by putting the txids of 'ghost parents' into taproot annex. PFN transaction would still be valid if some of 'ghost parents' are already confirmed, so the miners could have more fees than strictly necessary. But this is the same as with CPFP. Looking at the mempool code, it seems that only a way how parent/child transactions relationships are established will need to be adjusted to account for this 'ghost relationships', and once established, other logic will work as with CPFP. There could be complications regarding transaction package size. But I cannot claim that I understand that code enough to say something about this with certainty. ^ permalink raw reply [flat|nested] 17+ messages in thread
* [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation 2020-06-08 6:05 ` Dmitry Petukhov @ 2020-06-08 6:43 ` Jeremy 2020-06-08 7:15 ` Dmitry Petukhov 0 siblings, 1 reply; 17+ messages in thread From: Jeremy @ 2020-06-08 6:43 UTC (permalink / raw) Cc: Jeremy via bitcoin-dev [-- Attachment #1: Type: text/plain, Size: 4693 bytes --] Broke out to a separate thread. At core, the reason why this method *might* work is that it's essentially just CPFP but we can guarantee that the link we're examining is always exactly one hop away, so we get rid of most of the CPFP graph traversal issues. Your description largely matches my thinking for how something like this could work (pay for neighbor). The issue is that the extant CPFP logic is somewhat brittle and doesn't work as expected (Child not Children, which is problematic for multiple PFN's). > PFN transaction would still be valid if some of 'ghost parents' are already confirmed, so the miners could have more fees than strictly necessary. But this is the same as with CPFP. This is problematic and can't be done as it requires a new index of all past txns for consensus. My thinking is that a Fee Bump transaction can name a list of TXIDs (Or one TXID which implies all ancestors of) that it wishes to be included in a block with. It must be included in that block. A Fee Bump transaction may have no unconfirmed ancestors nor any children. Potentially, it also may not be RBF'd. You treat the Fee Bump Transactions as the lowest descendant of whatever it targets and then set it's feerate/total fee based on the package that would have to co-confirm for it to be worth mining. This makes it sort like normal transactions for inclusion. You can require some minimums for mempool inclusion at all. If it's target is confirmed or replaced, it should drop from the mempool. Transactions in the mempool may set a flag that opts out of CPFP for descendants/blocks any descendants. Channel protocols should set this bit to prevent pinning, and then use the Fee Bump to add fees to whatever txns need to go through. If done right you can also layer a coinswap protocol with the fee-bumping txns change so that you are getting a privacy benefit at the same time. BTW the annex *could* be used for this purpose, but it would also be acceptable to have it be in some kind of anyone can spend output. Then it would just be a anyone-can-spend tx with OP_CHECK_TXID_IN_BLOCK (or OP_CHECK_UTXO_SPENT_IN_BLOCK), and a miner could claim all such outputs at the end of the block. This is worse in terms of on-chain overheads, but nice in that it's the minimal semantic change & introduces some general purpose functionality. But my thoughts are still pretty loose at the moment around it. I suspect that to make fee bumping work nicely would require removing CPFP entirely, but I don't know that to be the case concretely. -- @JeremyRubin <https://twitter.com/JeremyRubin> <https://twitter.com/JeremyRubin> On Sun, Jun 7, 2020 at 11:02 PM Dmitry Petukhov <dp@simplexum•com> wrote: > В Sun, 7 Jun 2020 15:45:16 -0700 > Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > > What I think we'll eventually land on is a way of doing a tx > > that contributes fee to another tx chain as a passive observer to > > them. While this breaks one abstraction around how dependencies > > between transactions are processed, it also could help resolve some > > really difficult challenges we face with application-DoS (pinning and > > other attacks) in the mempool beyond CTV. I have a napkin design for > > how this could work, but nothing quite ready to share yet. > > I had an idea of 'Pay for neighbor' transaction where a transaction > that is not directly a child of some other transaction can specify that > it wants to pay the fee for that other transaction(s). It can become > like 'ghost child' transaction for them, in what it cannot be mined > unless its 'ghost parents' are confirmed, too. It will be like CPFP, > but without direct dependency via inputs. Such 'PFN' transaction would > not spend any coins beside what it specifies in its own inputs, of > course. > > The idea required a hardfork at first, but Anthony Towns suggested > a way to make it into a soft fork (past-taproot) by putting the txids of > 'ghost parents' into taproot annex. > > PFN transaction would still be valid if some of 'ghost parents' are > already confirmed, so the miners could have more fees than strictly > necessary. But this is the same as with CPFP. > > Looking at the mempool code, it seems that only a way how parent/child > transactions relationships are established will need to be adjusted to > account for this 'ghost relationships', and once established, other > logic will work as with CPFP. There could be complications regarding > transaction package size. But I cannot claim that I understand that > code enough to say something about this with certainty. > > [-- Attachment #2: Type: text/html, Size: 7627 bytes --] ^ permalink raw reply [flat|nested] 17+ messages in thread
* Re: [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation 2020-06-08 6:43 ` [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation Jeremy @ 2020-06-08 7:15 ` Dmitry Petukhov 0 siblings, 0 replies; 17+ messages in thread From: Dmitry Petukhov @ 2020-06-08 7:15 UTC (permalink / raw) To: bitcoin-dev В Sun, 7 Jun 2020 23:43:39 -0700 Jeremy via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> wrote: > > PFN transaction would still be valid if some of 'ghost parents' are > > > already confirmed, so the miners could have more fees than strictly > necessary. But this is the same as with CPFP. > > This is problematic and can't be done as it requires a new index of > all past txns for consensus. If the logic would match CPFP, then PFN would be valid if some of the 'ghost parents' are confirmed, but would be invalid if some of them are spent. I believe in this case txindex won't be required. > My thinking is that a Fee Bump transaction can name a list of TXIDs > (Or one TXID which implies all ancestors of) that it wishes to be > included in a block with. It must be included in that block. A Fee > Bump transaction may have no unconfirmed ancestors nor any children. > Potentially, it also may not be RBF'd. You treat the Fee Bump > Transactions as the lowest descendant of whatever it targets and then > set it's feerate/total fee based on the package that would have to > co-confirm for it to be worth mining. This makes it sort like normal > transactions for inclusion. You can require some minimums for mempool > inclusion at all. > > If it's target is confirmed or replaced, it should drop from the > mempool. Re "may not be RBF'd": What if the sender of PFN tx wants to increase the fee it offers for the 'ghost parents'? RBF-ing PFN tx itself seems like less wasteful way than RBF-ing some of the parents/'ghost parents' just for this purpose. Sometimes I think the sender of PFN will not be even able to replace any other transactions beside their own PFN tx (like when they offer 'fee bumping' service for others) ^ permalink raw reply [flat|nested] 17+ messages in thread
end of thread, other threads:[~2020-09-03 17:47 UTC | newest]
Thread overview: 17+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-11-26 1:50 [bitcoin-dev] BIP OP_CHECKTEMPLATEVERIFY Jeremy
2019-11-27 21:32 ` Russell O'Connor
2019-11-28 19:59 ` Jeremy
2019-12-11 0:37 ` Jeremy
2019-12-13 23:06 ` Jeremy
2019-12-19 20:08 ` Jeremy
[not found] ` <20191214122546.5e72eb93@simplexum.com>
[not found] ` <CAD5xwhgwhOwuPjKz-0_y7HP=jTi=6wJo8uH6HqCvOndr6wo0+Q@mail.gmail.com>
2020-02-14 11:18 ` Dmitry Petukhov
2020-02-14 19:16 ` Jeremy
2020-09-03 14:42 ` Dmitry Petukhov
2020-09-03 17:34 ` Jeremy
2020-09-03 17:47 ` Jeremy
2020-02-15 0:24 ` ZmnSCPxj
2020-06-07 16:51 ` Joachim Strömbergson
2020-06-07 22:45 ` Jeremy
2020-06-08 6:05 ` Dmitry Petukhov
2020-06-08 6:43 ` [bitcoin-dev] [was BIP OP_CHECKTEMPLATEVERIFY] Fee Bumping Operation Jeremy
2020-06-08 7:15 ` Dmitry Petukhov
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox