> This makes a lot of sense as it matches the semantics of what we are trying to achieve: allow the owner of an output (whether an individual or group) to reduce that output's value to pay a higher fee. Note, I think you're still struggling with some trust issue that anchor upgrade is at least eliminating for LN, namely the pre-agreement among a group of signers about the effective feerate to use at some unknown time point in the future. If you authorize your counterparty for a broadcast at feerate X, how do you prevent a broadcast at feerate Y, where Y is far under X, thus maliciously burning a lot of your fee-bumping reserve ? Of course, one mitigation is to make a contribution to a common fee-bumping output reserve proportional to what has been contributed as a funding collateral. Thus disincentivizing misuse of the common fee-bumping reserve in a game-theoretical way. But if you take the example of a LN channel, you're now running into another issue. Off-chain balances might fluctuate in a way that most of the time, your fee-bumping reserve contribution is out-of-proportion with your balance amounts to protect ? And as such enduring some significant timevalue bleeding on your fee-bumping reserve. Single-party managed fee-bumping reserve doesn't seem to suffer from this drawback ? Otherwise, I think your new construction OP_PUSH_TAPROOT_OUTPUT_KEY is correct and solves the O(log(n)) tapleaves issue. Le dim. 13 juin 2021 à 01:57, Lloyd Fournier a écrit : > On Fri, 11 Jun 2021 at 07:45, Antoine Riard > wrote: > >> Hi Lloyd, >> >> Thanks for this tx mutation proposal extending the scope of fee-bumping >> techniques. IIUC, the serves as a pointer to increase the >> output amount by value to recover the recompute the transaction hash >> against which the original signature is valid ? >> > > Right. > > >> Let's do a quick analysis of this scheme. >> * onchain footprint : one tapleaf per contract participant, with O(log n) >> increase of witness size, also one output per contract participant >> > > Yes but we can fix this (see below). > > * tx-relay bandwidth rebroadcast : assuming aforementioned in-place >> mempool substitution policy, the mutated transaction >> > * batching : fee-bumping value is extract from contract transaction >> itself, so O(n) per contract >> * mempool flexibility : the mutated transaction >> * watchtower key management : to enable outsourcing, the mutating key >> must be shared, in theory enabling contract value siphoning to miner fees ? >> > > Yes. You could use OP_LESSTHAN to make sure the value being deducted by > the watchtower is not above a threshold. > > >> Further, I think tx mutation scheme can be achieved in another way, with >> SIGHASH_ANYAMOUNT. A contract participant tapscript will be the following : >> >> >> >> Where is committed with SIGHASH_ANYAMOUNT, blanking >> nValue of one or more outputs. That way, the fee-to-contract-value >> distribution can be unilaterally finalized at a later time through the >> finalizing key [0]. >> > > Yes, that's also a way to do it. I was trying to preserve the original > external key signature in my attempt but this is probably not necessary. L2 > protocols could just exchange two signatures instead. One optimistic one on > the external key and one pessimistic SIGHASH_ANYAMOUNT one on the > . > > >> Note, I think that the tx mutation proposal relies on interactivity in >> the worst-case scenario where a counterparty wants to increase its >> fee-bumping output from the contract balance. This interactivity may lure a >> counterparty to alway lock the worst-case fee-bumping reserve in the >> output. I believe anchor output enables more "real-time" fee-bumping >> reserve adjustment ? >> > > Hmmm well I was hoping that you wouldn't need interaction ever. I can see > that my commitment TX example was too contrived because it has balance > outputs that go exclusively to one party. > Let's take a better example: A PTLC output with both timeout and success > pre-signed transactions spending from it. We must only let the person > offering the PTLC reduce the output of the timeout tx and the converse for > the success tx. > Note very carefully that if we naively apply OP_CHECKSIG_MUTATED or > SIGHASH_ANYAMOUNT with one tapleaf for each party then we risk one party > being able to lower the other party's output by doing a switcharoo on the > tapleaf after they see the signature for their counterparty's tx in the > mempool. In your example you could fix it by having a different > but this means we can't compress by just > using the taproot internal/external key. > > What about this: Instead of party specific "finalizing_alice_key" or > p1-fee-bump-key as I denoted it, we just use the key of the output whose > value we are reducing. This also solves the O(log(n)) tapleaves for > OP_CHECKSIG_MUTATED approach as well -- just have one tapleaf for fee > bumping but authorize it under the key of the output we are reducing. Thus > we need something like OP_PUSH_TAPROOT_OUTPUT_KEY which > takes the taproot external key at that output (fail if not taproot) and > puts it on the stack. So to be clear you have the on the > witness stack rather than having it fixed in a particular tapleaf (as per > my original post) and then use OP_DUP to pass it to both > OP_CHECKSIG_MUTATED and OP_PUSH_TAPROOT_OUTPUT_KEY. > This makes a lot of sense as it matches the semantics of what we are > trying to achieve: allow the owner of an output (whether an individual or > group) to reduce that output's value to pay a higher fee. > Furthermore this removes all keys from the tapleaf since they are all > aliased to either the input we are spending or one of the output keys of > the tx we are spending to. This is quite a big improvement over my original > idea. > > This works for lightning commit tx and for the case of a PTLC contract. It > also seems to work for the DLC funding output. I'd be interested to know if > anyone can think of a protocol where this would be inconvenient or > impossible to use as the main pre-signed tx fee bumping system. > > Cheers, > > LL > > Le dim. 6 juin 2021 à 22:28, Lloyd Fournier a >> écrit : >> >>> Hi Antione, >>> >>> Thanks for bringing up this important topic. I think there might be >>> another class of solutions over input based, CPFP and sponsorship. I'll >>> call them tx mutation schemes. The idea is that you can set a key that can >>> increase the fee by lowering a particular output after the tx is signed >>> without invalidating the signature. The premise is that anytime you need to >>> bump the fee of a transaction you must necessarily have funds in an output >>> that are going to you and therefore you can sacrifice some of them to >>> increase the fee. This is obviously destructive to txids so child presigned >>> transactions will have to use ANYPREVOUT as in your proposal. The advantage >>> is that it does not require keeping extra inputs around to bump the fee. >>> >>> So imagine a new opcode OP_CHECKSIG_MUTATED >>> . >>> This would check that is valid against if the >>> current transaction had the output at reduced by . To >>> make this more efficient, if the public key is one byte: 0x02 it references >>> the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to refer to >>> internal key[1]). >>> Now for our protocol we want both parties (p1 and p2) to be able to fee >>> bump a commitment transaction. They use MuSig to sign the commitment tx >>> under the external key with a decent fee for the current conditions. But in >>> case it proves insufficient they have added the following two leaves to >>> their key in the funding output as a backup so that p1 and p2 can >>> unilaterally bump the fee of anything they sign spending from the funding >>> output: >>> >>> 1. OP_CHECKSIG_MUTATED(0, 0x02, , ) >>> OP_CHECKSIGADD(p1-fee-bump-key, ) OP_2 >>> OP_NUMEQUALVERIFY >>> 2. OP_CHECKSIG_MUTATED(1, 0x02, , ) >>> OP_CHECKSIGADD(p2-fee-bump-key, ) OP_2 >>> OP_NUMEQUALVERIFY >>> >>> where <...> indicates the thing comes from the witness stack. >>> So to bump the fee of the commit tx after it has been signed either >>> party takes the and adds a signature under their >>> fee-bump-key for the new tx and reveals their fee bump leaf. >>> is checked against the old transaction while the fee >>> bumped transaction is checked against the fee bump key. >>> >>> I know I have left out how to change mempool eviction rules to >>> accommodate this kind of fee bumping without DoS or pinning attacks but >>> hopefully I have demonstrated that this class of solutions also exists. >>> >>> [1] >>> https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-0118.mediawiki >>> >>> Cheers, >>> >>> LL >>> >>> >>> >>> On Fri, 28 May 2021 at 07:13, Antoine Riard via bitcoin-dev < >>> bitcoin-dev@lists.linuxfoundation.org> wrote: >>> >>>> Hi, >>>> >>>> This post is pursuing a wider discussion around better fee-bumping >>>> strategies for second-layer protocols. It draws out a comparison between >>>> input-based and CPFP fee-bumping techniques, and their apparent trade-offs >>>> in terms of onchain footprint, tx-relay bandwidth rebroadcast, batching >>>> opportunity and mempool flexibility. >>>> >>>> Thanks to Darosior for reviews, ideas and discussions. >>>> >>>> ## Child-Pay-For-Parent >>>> >>>> CPFP is a mature fee-bumping technique, known and used for a while in >>>> the Bitcoin ecosystem. However, its usage in contract protocols with >>>> distrusting counterparties raised some security issues. As mempool's chain >>>> of unconfirmed transactions are limited in size, if any output is spendable >>>> by any contract participant, it can be leveraged as a pinning vector to >>>> downgrade odds of transaction confirmation [0]. >>>> >>>> That said, contract transactions interested to be protected under the >>>> carve-out logic require to add a new output for any contract participant, >>>> even if ultimately only one of them serves as an anchor to attach a CPFP. >>>> >>>> ## Input-Based >>>> >>>> I think input-based fee-bumping has been less studied as fee-bumping >>>> primitive for L2s [1]. One variant of input-based fee-bumping usable today >>>> is the leverage of the SIGHASH_ANYONECANPAY/SIGHASH_SINGLE malleability >>>> flags. If the transaction is the latest stage of the contract, a bumping >>>> input can be attached just-in-time, thus increasing the feerate of the >>>> whole package. >>>> >>>> However, as of today, input-based fee-bumping doesn't work to bump >>>> first stages of contract transactions as it's destructive of the txid, and >>>> as such breaks chain of pre-signed transactions. A first improvement would >>>> be the deployment of the SIGHASH_ANYPREVOUT softfork proposal. This new >>>> malleability flag allows a transaction to be signed without reference to >>>> any specific previous output. That way, spent transactions can be >>>> fee-bumped without altering validity of the chain of transactions. >>>> >>>> Even assuming SIGHASH_ANYPREVOUT, if the first stage contract >>>> transaction includes multiple outputs (e.g the LN's commitment tx has >>>> multiple HTLC outputs), SIGHASH_SINGLE can't be used and the fee-bumping >>>> input value might be wasted. This edge can be smoothed by broadcasting a >>>> preliminary fan-out transaction with a set of outputs providing a range of >>>> feerate points for the bumped transaction. >>>> >>>> This overhead could be smoothed even further in the future with more >>>> advanced sighash malleability flags like SIGHASH_IOMAP, allowing >>>> transaction signers to commit to a map of inputs/outputs [2]. In the >>>> context of input-based, the overflowed fee value could be redirected to an >>>> outgoing output. >>>> >>>> ## Onchain Footprint >>>> >>>> CPFP: One anchor output per participant must be included in the >>>> commitment transaction. To this anchor must be attached a child transaction >>>> with 2 inputs (one for the commitment, one for the bumping utxo) and 1 >>>> output. Onchain footprint: 2 inputs + 3 outputs. >>>> >>>> Input-based (today): If the bumping utxo is offering an adequate >>>> feerate point in function of network mempools congestion at time of >>>> broadcast, only 1 input. If a preliminary fan-out transaction to adjust >>>> feerate point must be broadcasted first, 1 input and 2 outputs more must be >>>> accounted for. Onchain footprint: 2 inputs + 3 outputs. >>>> >>>> Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): As long as the bumping >>>> utxo's value is wide enough to cover the worst-case of mempools congestion, >>>> the bumped transaction can be attached 1 input and 1 output. Onchain >>>> footprint: 1 input + 1 output. >>>> >>>> ## Tx-Relay Bandwidth Rebroadcast >>>> >>>> CPFP: In the context of multi-party protocols, we should assume bounded >>>> rationality of the participants w.r.t to an unconfirmed spend of the >>>> contract utxo across network mempools. Under this assumption, the bumped >>>> transaction might have been replaced by a concurrent state. To guarantee >>>> efficiency of the CPFP the whole chain of transactions should be >>>> rebroadcast, perhaps wasting bandwidth consumption for a still-identical >>>> bumped transaction [3]. Rebroadcast footprint: the whole chain of >>>> transactions. >>>> >>>> Input-based (today): In case of rebroadcast, the fee-bumping input is >>>> attached to the root of the chain of transactions and as such breaks the >>>> chain validity in itself. Beyond the rebroadcast of the updated root under >>>> replacement policy, the remaining transactions must be updated and >>>> rebroadcast. Rebroadcast footprint: the whole chain of transactions. >>>> >>>> Input-based(SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): In case of rebroadcast, >>>> the fee-bumping is attached to the root of the chain of transactions but it >>>> doesn't break the chain validity in itself. Assuming a future mempool >>>> acceptance logic to authorize in-place substitution, the rest of the chain >>>> could be preserved. Rebroadcast footprint: the root of the chain of >>>> transactions. >>>> >>>> ## Fee-Bumping Batching >>>> >>>> CPFP: In the context of multi-party protocols, in optimistic scenarios, >>>> we can assume aggregation of multiple chains of transactions. For e.g, a LN >>>> operator is desirous to non-cooperatively close multiple channels at the >>>> same time and would like to combine their fee-bumping. With CPFP, one >>>> anchor output and one bumping input must be consumed per aggregated chain, >>>> even if the child transaction fields can be shared. Batching perf: 1 >>>> input/1 output per aggregated chain. >>>> >>>> Input-based (today): Unless the contract allows interactivity, multiple >>>> chains of transactions cannot be aggregated. One bumping input must be >>>> attached per chain, though if a preliminary fan-out transaction is relied >>>> on to offer multiple feerate points, transaction fields can be shared. >>>> Batching perf: 1 input/1 output per aggregated chain. >>>> >>>> Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of >>>> transactions might be aggregated together *non-interactively*. One bumping >>>> input and outgoing output can be attached to the aggregated root. Batching >>>> perf: 1 input/1 output per aggregation. >>>> >>>> ## Fee-Bumping Mempool Flexibility >>>> >>>> CPFP: In the context of multi-party protocols, one of your >>>> counterparties might build a branch of transactions from one of the root >>>> outputs thus saturating the in-mempool package limits. To avoid these >>>> shenanigans, LN channels are relying on the carve-out mechanism. Though, >>>> the carve-out mechanism includes its own limitation and doesn't scale >>>> beyond 2 contract participants. >>>> >>>> Input-based: The root of the chain of transaction is the package's >>>> oldest ancestor, so package limits don't restrain its acceptance and it >>>> works whatever the number of contract participants. >>>> >>>> To conclude, this post scores 2 fee-bumping primitives for multi-party >>>> protocols on a range of factors. It hopes to unravel the ground for a real >>>> feerate performance framework of second-layers protocols . >>>> >>>> Beyond that, few points can be highlighted a) future soft forks allow >>>> significant onchain footprint savings, especially in case of batching, b) >>>> future package relay bandwidth efficiency should account for rebroadcast >>>> frequency of CPFPing multi-party protocols. On this latter point one >>>> follow-up might be to evaluate differing package relay *announcement* >>>> schemes in function of odds of non-cooperative protocol broadcast/odds of >>>> concurrent broadcast/rebroadcast frequencies. >>>> >>>> Thoughts ? >>>> >>>> Cheers, >>>> Antoine >>>> >>>> [0] >>>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-November/016518.html >>>> [1] Beyond the revault architecture : >>>> https://github.com/revault/practical-revault/blob/master/revault.pdf >>>> [2] Already proposed a while back : >>>> https://bitcointalk.org/index.php?topic=252960.0 >>>> [3] In theory, an already-relayed transaction shouldn't pass Core's >>>> `filterInventoryKnown`. In practice, if the transaction is announced as >>>> part of a package_id, the child might have changed, not the parent, leading >>>> to a redundant relay of the latter. >>>> _______________________________________________ >>>> bitcoin-dev mailing list >>>> bitcoin-dev@lists.linuxfoundation.org >>>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >>>> >>>