[bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

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.

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[darosior]

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

Hi,

> ## 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.

Unfortunately, ACP | SINGLE is trivially pinable [0] (TL;DR: i can just attach an output paying immediately to me, and construct a tx chain spending it). We are using ACP | ALL for Revault,
which is the reason why we need a well laid-out pool of fee-bumping UTXOs (as you need to consume them entirely).

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

I believe that it's better to broadcast a single fan-out transaction creating your entire UTXO pool in advance. You could create one coin per contract you are watching which value would be
used to bump your transaction feerate from the presigned one to -say- the average feerate over the past month, and then have smaller coins that you could attach to any transaction to bump
by a certain threshold (say, 10sat/vbyte). You would create as many small coin as your reserve algorithm tells you (which could be "i need to be able, worst case, to close all my contracts
with the worst historical feerate." or (fractional reserve version) "i need to be able, worst case, to close 10% of my contracts at the average feerate of the past year, the remaining ones sorry
for my loss"). [1]

This method is both much more optimal (though you need to sometimes incur the cost of many small additional inputs) and also makes sure that your feebump does not depend on the confirmation
of a first stage transaction (as you can only RBF with new inputs if they are confirmed).

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

Why not just attaching it at the tail of the chain? Bumping the last child with additional input would effectively be a CPFP for the entire chain in this case.

Thanks for starting this discussion :)
Antoine

[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017835.html
[1] Credits to Jacob Swambo, who came up with the single fan-out transaction and with whom i'm discussing how to practically apply these ideas to Revault.

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

> Unfortunately, ACP | SINGLE is trivially pinable [0] (TL;DR: i can just
attach an output paying immediately to me, and construct a tx chain
spending it). We are using ACP | ALL for Revault,
> which is the reason why we need a well laid-out pool of fee-bumping UTXOs
(as you need to consume them entirely).

Oh yes, I should have mentioned this pinning vector. The witnessScript I've
in mind to make secure that type of chain of transactions would be one
MuSig key for all contract participants, where signature are committed with
SIGHASH_ANYPREVOUT | SIGHASH_IOMAP, one pubkey per participant to lockdown
the transaction with SIGHASH_ALL. I think it works and prevents malicious
in-flight attachment of input/output to a multi-party transaction ?

> I believe that it's better to broadcast a single fan-out transaction
creating your entire UTXO pool in advance. You could create one coin per
contract you are watching which value would be
> used to bump your transaction feerate from the presigned one to -say- the
average feerate over the past month, and then have smaller coins that you
could attach to any transaction to bump
> by a certain threshold (say, 10sat/vbyte). You would create as many small
coin as your reserve algorithm tells you (which could be "i need to be
able, worst case, to close all my contracts
> with the worst historical feerate." or (fractional reserve version) "i
need to be able, worst case, to close 10% of my contracts at the average
feerate of the past year, the remaining ones sorry
> for my loss"). [1]

> This method is both much more optimal (though you need to sometimes incur
the cost of many small additional inputs) and also makes sure that your
feebump does not depend on the confirmation of a first stage transaction
(as you can only RBF with new inputs if they are confirmed).

I see, so you spread your bumping UTXO pool in two ranges : at least one
bumping utxo per contract, and a subpool of emergency smaller coins, ready
to be attached on any contract. I think this strategy makes sense for
vaults as you can afford a bunch of small coins at different feerates,
spending the ones not used afterwards. And higher cells of feerate reserve
as the worst historical feerate are relatively not that much compared to
locked-in vaults value. That said, I'm more dubious about LN, where node
operators might not keep the worst-case fee-bumping reserve, as the time
value of the coins aren't worth the channel liquidity at stake.

> Why not just attaching it at the tail of the chain? Bumping the last
child with additional input would effectively be a CPFP for the entire
chain in this case.

Yes, input-based bumping targeting the tail of the chain works at the
transaction level. But if you assume bounded visibility of network
mempools, one of your counterparties might have broadcast a concurrent
state, thus making your CPFP irrelevant for propagation. Though smarter
tx-relay techniques such as "attach-on-contract-utxo-root" CPFP (or also
known as "blinded CPFP") might solve this issue.

Le jeu. 27 mai 2021 à 17:45, darosior <darosior@protonmail.com> a écrit :

> Hi,
>
> ## 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.
>
>
> Unfortunately, ACP | SINGLE is trivially pinable [0] (TL;DR: i can just
> attach an output paying immediately to me, and construct a tx chain
> spending it). We are using ACP | ALL for Revault,
> which is the reason why we need a well laid-out pool of fee-bumping UTXOs
> (as you need to consume them entirely).
>
> 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.
>
>
> I believe that it's better to broadcast a single fan-out transaction
> creating your entire UTXO pool in advance. You could create one coin per
> contract you are watching which value would be
> used to bump your transaction feerate from the presigned one to -say- the
> average feerate over the past month, and then have smaller coins that you
> could attach to any transaction to bump
> by a certain threshold (say, 10sat/vbyte). You would create as many small
> coin as your reserve algorithm tells you (which could be "i need to be
> able, worst case, to close all my contracts
> with the worst historical feerate." or (fractional reserve version) "i
> need to be able, worst case, to close 10% of my contracts at the average
> feerate of the past year, the remaining ones sorry
> for my loss"). [1]
>
> This method is both much more optimal (though you need to sometimes incur
> the cost of many small additional inputs) and also makes sure that your
> feebump does not depend on the confirmation
> of a first stage transaction (as you can only RBF with new inputs if they
> are confirmed).
>
> 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.
>
>
> Why not just attaching it at the tail of the chain? Bumping the last child
> with additional input would effectively be a CPFP for the entire chain in
> this case.
>
>
> Thanks for starting this discussion :)
> Antoine
>
> [0]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017835.html
> [1] Credits to Jacob Swambo, who came up with the single fan-out
> transaction and with whom i'm discussing how to practically apply these
> ideas to Revault.
>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[darosior]

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

> Oh yes, I should have mentioned this pinning vector. The witnessScript I've in mind to make secure that type of chain of transactions would be one MuSig key for all contract participants, where signature are committed with SIGHASH_ANYPREVOUT | SIGHASH_IOMAP, one pubkey per participant to lockdown the transaction with SIGHASH_ALL. I think it works and prevents malicious in-flight attachment of input/output to a multi-party transaction ?

So something like `or(and(pk(FB),pk(A)),and(pk(FB),pk(B)),and(pk(FB),pk(C)))` with each `or` in their own leaf? I think it works, but only if the keys `A`, `B`, `C` are "hot", as in available to the
fee-bumper. For Revault it means introducing a key for each watchtower in the vaults descriptors, which is meh but technically feasible since they are identified. This kinda break our replication
model though. On the other end for Lightning... You'd need to know what watchtower (or your node) is going to be willing to feebump? The descriptor can very quickly get very convoluted:
`or(and(pk(FB),pk(A_NODE)),and(pk(FB),pk(A_WT1)),and(pk(FB),pk(A_WT2)),and(pk(FB),pk(B_NODE)),and(pk(FB),pk(B_WT1)),and(pk(FB),pk(B_WT2)))` for only 2 participants in a channel
where one of either the node or two watchtowers (identified beforehand !!) can feebump.

> I see, so you spread your bumping UTXO pool in two ranges : at least one bumping utxo per contract, and a subpool of emergency smaller coins, ready to be attached on any contract. I think this strategy makes sense for vaults as you can afford a bunch of small coins at different feerates, spending the ones not used afterwards. And higher cells of feerate reserve as the worst historical feerate are relatively not that much compared to locked-in vaults value. That said, I'm more dubious about LN, where node operators might not keep the worst-case fee-bumping reserve, as the time value of the coins aren't worth the channel liquidity at stake.

Yes. That's a bit concerning, but i guess it's a tradeoff. Amusingly the incentive is at odds with routing: you want to keep your channels unbalanced if you run on fractional fee-bumping reserves
so that if things go south you can still salvage most of your funds by focusing your fee-bumping on the unbalanced (to you) channels :p .

> Yes, input-based bumping targeting the tail of the chain works at the transaction level. But if you assume bounded visibility of network mempools, one of your counterparties might have broadcast a concurrent state, thus making your CPFP irrelevant for propagation. Though smarter tx-relay techniques such as "attach-on-contract-utxo-root" CPFP (or also known as "blinded CPFP") might solve this issue.

Oh, yes, good point.

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

> So something like
`or(and(pk(FB),pk(A)),and(pk(FB),pk(B)),and(pk(FB),pk(C)))` with each `or`
in their own leaf? I think it works, but only if the keys `A`, `B`, `C` are
"hot", as in available to the
fee-bumper. For Revault it means introducing a key for each watchtower in
the vaults descriptors, which is meh but technically feasible since they
are identified. This kinda break our replication
model though. On the other end for Lightning... You'd need to know what
watchtower (or your node) is going to be willing to feebump? The descriptor
can very quickly get very convoluted:
`or(and(pk(FB),pk(A_NODE)),and(pk(FB),pk(A_WT1)),and(pk(FB),pk(A_WT2)),and(pk(FB),pk(B_NODE)),and(pk(FB),pk(B_WT1)),and(pk(FB),pk(B_WT2)))`
for only 2 participants in a channel
where one of either the node or two watchtowers (identified beforehand !!)
can feebump.

I'm not sure if we agree on the purpose of the finalizing key ? Its goal is
to finalize the transaction state once another fee-bumping input has been
attached and should be part of the witnessScript of the "main" input. If a
third-party try to attach a malicious pinning input, doing so breaks the
finalizing signature and the transaction will be rejected as invalid by
network mempools.

This key doesn't secure funds and as such can be shared to any fee-bumper
entity (contract source, sourced towers, outsourced towers ?). Of course,
it means an outsourced tower can re-introduce malicious transaction
malleability but at least it's moving away malleability from the
contract-level and it's now a holder tower policy decision ?

Overall I agree any fee-bumping techniques comparison should also account
tower key management complexity (and this one was missing).

> Yes. That's a bit concerning, but i guess it's a tradeoff. Amusingly the
incentive is at odds with routing: you want to keep your channels
unbalanced if you run on fractional fee-bumping reserves
so that if things go south you can still salvage most of your funds by
focusing your fee-bumping on the unbalanced (to you) channels :p .

That's a good point! Switching to anchor now rebalances a security matter,
not sure if it was an intended effect of the design :) Also, you might take
HTLC forwarding acceptance decisions holistically instead of a per-channel
level. If your number of HTLC in-flight expressed as outputs on one
commitment transaction goes up, don't accept anymore HTLC on other
channels, otherwise, you might run short of fee-bumping reserve...

Le ven. 28 mai 2021 à 18:25, darosior <darosior@protonmail.com> a écrit :

>
> Oh yes, I should have mentioned this pinning vector. The witnessScript
> I've in mind to make secure that type of chain of transactions would be one
> MuSig key for all contract participants, where signature are committed with
> SIGHASH_ANYPREVOUT | SIGHASH_IOMAP, one pubkey per participant to lockdown
> the transaction with SIGHASH_ALL. I think it works and prevents malicious
> in-flight attachment of input/output to a multi-party transaction ?
>
>
> So something like
> `or(and(pk(FB),pk(A)),and(pk(FB),pk(B)),and(pk(FB),pk(C)))` with each `or`
> in their own leaf? I think it works, but only if the keys `A`, `B`, `C` are
> "hot", as in available to the
> fee-bumper. For Revault it means introducing a key for each watchtower in
> the vaults descriptors, which is meh but technically feasible since they
> are identified. This kinda break our replication
> model though. On the other end for Lightning... You'd need to know what
> watchtower (or your node) is going to be willing to feebump? The descriptor
> can very quickly get very convoluted:
> `or(and(pk(FB),pk(A_NODE)),and(pk(FB),pk(A_WT1)),and(pk(FB),pk(A_WT2)),and(pk(FB),pk(B_NODE)),and(pk(FB),pk(B_WT1)),and(pk(FB),pk(B_WT2)))`
> for only 2 participants in a channel
> where one of either the node or two watchtowers (identified beforehand !!)
> can feebump.
>
> I see, so you spread your bumping UTXO pool in two ranges : at least one
> bumping utxo per contract, and a subpool of emergency smaller coins, ready
> to be attached on any contract. I think this strategy makes sense for
> vaults as you can afford a bunch of small coins at different feerates,
> spending the ones not used afterwards. And higher cells of feerate reserve
> as the worst historical feerate are relatively not that much compared to
> locked-in vaults value. That said, I'm more dubious about LN, where node
> operators might not keep the worst-case fee-bumping reserve, as the time
> value of the coins aren't worth the channel liquidity at stake.
>
>
> Yes. That's a bit concerning, but i guess it's a tradeoff. Amusingly the
> incentive is at odds with routing: you want to keep your channels
> unbalanced if you run on fractional fee-bumping reserves
> so that if things go south you can still salvage most of your funds by
> focusing your fee-bumping on the unbalanced (to you) channels :p .
>
> Yes, input-based bumping targeting the tail of the chain works at the
> transaction level. But if you assume bounded visibility of network
> mempools, one of your counterparties might have broadcast a concurrent
> state, thus making your CPFP irrelevant for propagation. Though smarter
> tx-relay techniques such as "attach-on-contract-utxo-root" CPFP (or also
> known as "blinded CPFP") might solve this issue.
>
>
> Oh, yes, good point.
>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[darosior]

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

Hi,

Another thing to consider when comparing these two techniques is anti-fee sniping protection. If you are going to feebump directly
your revocation transaction by adding inputs to it, the nLockTime has already been signed in advance. Therefore your are sponsoring
a transaction that could be included in any reorged block.

This is not a big deal for now but i'm concerned it may become one, especially since this type of transaction might be the highest fee-paying
ones on the network (there is a lot at stake). Having a new sighash type not masking the nLockTime so that it can be set by the feebumper
could help with this, even though the presumably low pre-signed fee can still be snipped (since the ALL signature is added to the feebump inputs).

The recent BIP proposal by Chris Belcher [0] also just uncovered (to me) a new hack: if the feebumping coins are less than 65,535 blocks old, we
could also set the nSequence of these coins to achieve the same purpose [1]. And this can be done with today's Bitcoin!

Antoine P.

[0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-June/019048.html
[1] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002412.html
‐‐‐‐‐‐‐ Original Message ‐‐‐‐‐‐‐
Le vendredi 28 mai 2021 à 6:13 AM, Antoine Riard <antoine.riard@gmail.com> a écrit :

>> Unfortunately, ACP | SINGLE is trivially pinable [0] (TL;DR: i can just attach an output paying immediately to me, and construct a tx chain spending it). We are using ACP | ALL for Revault,
>> which is the reason why we need a well laid-out pool of fee-bumping UTXOs (as you need to consume them entirely).
>
> Oh yes, I should have mentioned this pinning vector. The witnessScript I've in mind to make secure that type of chain of transactions would be one MuSig key for all contract participants, where signature are committed with SIGHASH_ANYPREVOUT | SIGHASH_IOMAP, one pubkey per participant to lockdown the transaction with SIGHASH_ALL. I think it works and prevents malicious in-flight attachment of input/output to a multi-party transaction ?
>
>> I believe that it's better to broadcast a single fan-out transaction creating your entire UTXO pool in advance. You could create one coin per contract you are watching which value would be
>> used to bump your transaction feerate from the presigned one to -say- the average feerate over the past month, and then have smaller coins that you could attach to any transaction to bump
>> by a certain threshold (say, 10sat/vbyte). You would create as many small coin as your reserve algorithm tells you (which could be "i need to be able, worst case, to close all my contracts
>> with the worst historical feerate." or (fractional reserve version) "i need to be able, worst case, to close 10% of my contracts at the average feerate of the past year, the remaining ones sorry
>> for my loss"). [1]
>
>> This method is both much more optimal (though you need to sometimes incur the cost of many small additional inputs) and also makes sure that your feebump does not depend on the confirmation of a first stage transaction (as you can only RBF with new inputs if they are confirmed).
>
> I see, so you spread your bumping UTXO pool in two ranges : at least one bumping utxo per contract, and a subpool of emergency smaller coins, ready to be attached on any contract. I think this strategy makes sense for vaults as you can afford a bunch of small coins at different feerates, spending the ones not used afterwards. And higher cells of feerate reserve as the worst historical feerate are relatively not that much compared to locked-in vaults value. That said, I'm more dubious about LN, where node operators might not keep the worst-case fee-bumping reserve, as the time value of the coins aren't worth the channel liquidity at stake.
>
>> Why not just attaching it at the tail of the chain? Bumping the last child with additional input would effectively be a CPFP for the entire chain in this case.
>
> Yes, input-based bumping targeting the tail of the chain works at the transaction level. But if you assume bounded visibility of network mempools, one of your counterparties might have broadcast a concurrent state, thus making your CPFP irrelevant for propagation. Though smarter tx-relay techniques such as "attach-on-contract-utxo-root" CPFP (or also known as "blinded CPFP") might solve this issue.
>
> Le jeu. 27 mai 2021 à 17:45, darosior <darosior@protonmail.com> a écrit :
>
>> Hi,
>>
>>> ## 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.
>>
>> Unfortunately, ACP | SINGLE is trivially pinable [0] (TL;DR: i can just attach an output paying immediately to me, and construct a tx chain spending it). We are using ACP | ALL for Revault,
>> which is the reason why we need a well laid-out pool of fee-bumping UTXOs (as you need to consume them entirely).
>>
>>> 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.
>>
>> I believe that it's better to broadcast a single fan-out transaction creating your entire UTXO pool in advance. You could create one coin per contract you are watching which value would be
>> used to bump your transaction feerate from the presigned one to -say- the average feerate over the past month, and then have smaller coins that you could attach to any transaction to bump
>> by a certain threshold (say, 10sat/vbyte). You would create as many small coin as your reserve algorithm tells you (which could be "i need to be able, worst case, to close all my contracts
>> with the worst historical feerate." or (fractional reserve version) "i need to be able, worst case, to close 10% of my contracts at the average feerate of the past year, the remaining ones sorry
>> for my loss"). [1]
>>
>> This method is both much more optimal (though you need to sometimes incur the cost of many small additional inputs) and also makes sure that your feebump does not depend on the confirmation
>> of a first stage transaction (as you can only RBF with new inputs if they are confirmed).
>>
>>> 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.
>>
>> Why not just attaching it at the tail of the chain? Bumping the last child with additional input would effectively be a CPFP for the entire chain in this case.
>>
>> Thanks for starting this discussion :)
>> Antoine
>>
>> [0] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-May/017835.html
>> [1] Credits to Jacob Swambo, who came up with the single fan-out transaction and with whom i'm discussing how to practically apply these ideas to Revault.

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Lloyd Fournier]

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

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 <output index> <publickey>
<value> <signature>.
This would check that <signature> is valid against <publickey> if the
current transaction had the output at <output index> reduced by <value>. 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, <fee-bump-value>, <original-signature>)
OP_CHECKSIGADD(p1-fee-bump-key, <p1-fee-bump-signature>)  OP_2
OP_NUMEQUALVERIFY
2. OP_CHECKSIG_MUTATED(1, 0x02, <fee-bump-value>, <original-signature>)
OP_CHECKSIGADD(p2-fee-bump-key, <p2-fee-bump-signature>) 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 <original-signature> and adds a signature under their
fee-bump-key for the new tx and reveals their fee bump leaf.
<original-signature> 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
>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

Hi Lloyd,

Thanks for this tx mutation proposal extending the scope of fee-bumping
techniques. IIUC, the <output_index> 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 ?

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
* 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 ?

Further, I think tx mutation scheme can be achieved in another way, with
SIGHASH_ANYAMOUNT. A contract participant tapscript will be the following :

<contract_key> <finalizing_alice_key>

Where <contract_signature> 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].

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 ?

Cheers,
Antoine

[0] Incautious sighash alleability is unsafe. Be careful, otherwise kitties
will perish by the thousands :
https://github.com/revault/practical-revault/pull/83

Le dim. 6 juin 2021 à 22:28, Lloyd Fournier <lloyd.fourn@gmail.com> 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 <output index> <publickey>
> <value> <signature>.
> This would check that <signature> is valid against <publickey> if the
> current transaction had the output at <output index> reduced by <value>. 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, <fee-bump-value>, <original-signature>)
> OP_CHECKSIGADD(p1-fee-bump-key, <p1-fee-bump-signature>)  OP_2
> OP_NUMEQUALVERIFY
> 2. OP_CHECKSIG_MUTATED(1, 0x02, <fee-bump-value>, <original-signature>)
> OP_CHECKSIGADD(p2-fee-bump-key, <p2-fee-bump-signature>) 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 <original-signature> and adds a signature under their
> fee-bump-key for the new tx and reveals their fee bump leaf.
> <original-signature> 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
>>
>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[darosior]

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

> 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 ?

Anchor outputs / malleability allow for real-time adjustment of long-lived contracts (for which the today worst case is much larger than the worst case
estimated at the contract creation time). However it's a really interested for vaults, as you have multiple parties with the same goal (getting this Cancel
transaction confirmed). Therefore you have this slight "tragedy of the commons" of whose fee-bumping wallet is going to pay for sponsoring the next
Cancel (and it's exacerbated by / for external redundancy providers). With this approach, fees are taxed from the shared coins, so there is no pernicious
incentive to delay the broadcast of your revocation transaction in the hope that another watchtower will pay the fee instead of you. I think this applies to
multi-party channels too, by having some kind of a shared budget.

You would also have a large UX improvement with regard to the fee-bumping wallet: no need to have one (fb wallet refills are really *really* poor UX)
one and maintain a nice laid-out UTXO pool.
In the end, both approaches seem desirable: the output for paying most of the fees from shared coins, therefore dwarfing the "tragedy of the common"
concerns, and the malleability to still be able to dynamically allocate more funds to feebump in case of a black swan event (but essentially needs a single
refill at startup as it's never spent from).

As a side note, this can "just" be implemented by exchanging N (varying depending on the granularity) signatures with increasing feerates. Again, this
might be reasonable in some usecases but not others (eg if you are already generating tons of sigs, or have longer chain of unconfirmed transactions).

> Cheers,
> Antoine
>
> [0] Incautious sighash alleability is unsafe. Be careful, otherwise kitties will perish by the thousands :
> https://github.com/revault/practical-revault/pull/83
>
> Le dim. 6 juin 2021 à 22:28, Lloyd Fournier <lloyd.fourn@gmail.com> 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 <output index> <publickey> <value> <signature>.
>> This would check that <signature> is valid against <publickey> if the current transaction had the output at <output index> reduced by <value>. 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, <fee-bump-value>, <original-signature>) OP_CHECKSIGADD(p1-fee-bump-key, <p1-fee-bump-signature>) OP_2 OP_NUMEQUALVERIFY
>> 2. OP_CHECKSIG_MUTATED(1, 0x02, <fee-bump-value>, <original-signature>) OP_CHECKSIGADD(p2-fee-bump-key, <p2-fee-bump-signature>) 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 <original-signature> and adds a signature under their fee-bump-key for the new tx and reveals their fee bump leaf. <original-signature> 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

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Lloyd Fournier]

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

On Fri, 11 Jun 2021 at 07:45, Antoine Riard <antoine.riard@gmail.com> wrote:

> Hi Lloyd,
>
> Thanks for this tx mutation proposal extending the scope of fee-bumping
> techniques. IIUC, the <output_index> 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 :
>
> <contract_key> <finalizing_alice_key>
>
> Where <contract_signature> 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
<contract_key>.


> 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
<contract_key> but this means we can't compress <contract_key> 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 <output index> 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 <output index> 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 <lloyd.fourn@gmail.com> 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 <output index> <publickey>
>> <value> <signature>.
>> This would check that <signature> is valid against <publickey> if the
>> current transaction had the output at <output index> reduced by <value>. 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, <fee-bump-value>, <original-signature>)
>> OP_CHECKSIGADD(p1-fee-bump-key, <p1-fee-bump-signature>)  OP_2
>> OP_NUMEQUALVERIFY
>> 2. OP_CHECKSIG_MUTATED(1, 0x02, <fee-bump-value>, <original-signature>)
>> OP_CHECKSIGADD(p2-fee-bump-key, <p2-fee-bump-signature>) 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 <original-signature> and adds a signature under their
>> fee-bump-key for the new tx and reveals their fee bump leaf.
>> <original-signature> 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
>>>
>>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Jeremy]

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

The API of a sponsor-like mechanism is close to ideal in my opinion:

- compatible with non malleable transactions
- 0 overhead if fees accurately estimated
- watchtower friendly
- post hoc, requires minimal 'protocol awareness'
- friendly with most mempool eviction policies, not much new required
- can work to atomically bump multiple txns
- can be bumped cooperatively by multiple sponsors w/o coordination
- 0 'rebroadcast overhead' (e.g., for a large batch) leasing to cascading
retransmission fees for replacement
- can be piggy backed with other future transactions or protocols (e.g.
coinjoin)
- compatible with change being in cold storage

The main drawback is it is chain space - wise less efficient, as an
additional transaction gets made. However, I think the API benefits
'product market fit' over alternative solutions outweigh other concerns,
and if the 'sponsorship efficiency hypothesis' holds true, then most
transactions will not require sponsors and therefore the savings of not
needing to preplan a few bumping mechanism will be more efficient overall
(efficient market will drive accuracy in estimating fees rather than
needing to sponsor).

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

Thanks for this analysis of a sponsor-like mechanism.

For sure, "watchtower friendly" and "post hoc" are really good point
towards sponsorship, at least other proposals are struggling with
watchtower support, at least in way where your watchtower policy doesn't
leak to your counterparties (which is really gross from a security
standpoint when you think about it!)

W.r.t to sponsorship chain/fee overhead (at least compared to
ANYPREVOUT+IOMAP), I think it's ultimately a question of how many contracts
are closed cooperatively-vs-non-coop on the long-term. Even if we can hope
for emergency closure for security reasons to be pretty rare in practice,
we might still have significant non-coop closing when counterparties can't
agree on the economic opportunity of pursuing the contract or not. E.g, a
big LN hub unilaterally closes small channels, either because it doesn't
earn routing fees or those mobile nodes have been offline for too long.

Still, I think the next step of the discussion would be to come up with a
consistent simulation against which we can all agree on and score all the
proposals against it.

Le dim. 13 juin 2021 à 10:16, Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> The API of a sponsor-like mechanism is close to ideal in my opinion:
>
> - compatible with non malleable transactions
> - 0 overhead if fees accurately estimated
> - watchtower friendly
> - post hoc, requires minimal 'protocol awareness'
> - friendly with most mempool eviction policies, not much new required
> - can work to atomically bump multiple txns
> - can be bumped cooperatively by multiple sponsors w/o coordination
> - 0 'rebroadcast overhead' (e.g., for a large batch) leasing to cascading
> retransmission fees for replacement
> - can be piggy backed with other future transactions or protocols (e.g.
> coinjoin)
> - compatible with change being in cold storage
>
> The main drawback is it is chain space - wise less efficient, as an
> additional transaction gets made. However, I think the API benefits
> 'product market fit' over alternative solutions outweigh other concerns,
> and if the 'sponsorship efficiency hypothesis' holds true, then most
> transactions will not require sponsors and therefore the savings of not
> needing to preplan a few bumping mechanism will be more efficient overall
> (efficient market will drive accuracy in estimating fees rather than
> needing to sponsor).
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

> 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 <lloyd.fourn@gmail.com> a
écrit :

> On Fri, 11 Jun 2021 at 07:45, Antoine Riard <antoine.riard@gmail.com>
> wrote:
>
>> Hi Lloyd,
>>
>> Thanks for this tx mutation proposal extending the scope of fee-bumping
>> techniques. IIUC, the <output_index> 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 :
>>
>> <contract_key> <finalizing_alice_key>
>>
>> Where <contract_signature> 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
> <contract_key>.
>
>
>> 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
> <contract_key> but this means we can't compress <contract_key> 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 <output index> 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 <output index> 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 <lloyd.fourn@gmail.com> 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 <output index> <publickey>
>>> <value> <signature>.
>>> This would check that <signature> is valid against <publickey> if the
>>> current transaction had the output at <output index> reduced by <value>. 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, <fee-bump-value>, <original-signature>)
>>> OP_CHECKSIGADD(p1-fee-bump-key, <p1-fee-bump-signature>)  OP_2
>>> OP_NUMEQUALVERIFY
>>> 2. OP_CHECKSIG_MUTATED(1, 0x02, <fee-bump-value>, <original-signature>)
>>> OP_CHECKSIGADD(p2-fee-bump-key, <p2-fee-bump-signature>) 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 <original-signature> and adds a signature under their
>>> fee-bump-key for the new tx and reveals their fee bump leaf.
>>> <original-signature> 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
>>>>
>>>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Lloyd Fournier]

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

On Tue, 15 Jun 2021 at 02:47, Antoine Riard <antoine.riard@gmail.com> wrote:

> > 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 ?
>

I claim that what I am suggesting is a single-party managed fee-bumping
system that solves all fee-bumping requirements of lightning without
needing external utxos and without additional interaction or fee
pre-agreement between parties. On the commit tx you have your balance going
exclusively towards you which you can unilaterally reduce to increase the
fee up to whatever threshold you want. With a HTLC or PTLC you also always
have a tx with an output that you can unilaterally drain to bump fee
(either the hltc-success or htlc-timeout). Are you saying that there are
protocols where this would require pre-arrangement or are you saying that
it would require pre-arrangement in lightning for some reason I don't see?

To further emphasise the generality of this idea you can easily imagine a
world where this is enabled on all Bitcoin transactions (of course you have
to stomach tx malleability -- a bit more palatable with ANYPREVOUT
everywhere). Even for a normal wallet-to-wallet payment the receiver could
efficiently increase the tx fee by making a signature under the key of
their output and replacing the original tx without interacting with the
sender who actually provided the funds for the payment.

Cheers,

LL

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Lloyd Fournier]

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

On Tue, 15 Jun 2021 at 10:59, Lloyd Fournier <lloyd.fourn@gmail.com> wrote:

>
>
> On Tue, 15 Jun 2021 at 02:47, Antoine Riard <antoine.riard@gmail.com>
> wrote:
>
>> > 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 ?
>>
>
> I claim that what I am suggesting is a single-party managed fee-bumping
> system that solves all fee-bumping requirements of lightning without
> needing external utxos and without additional interaction or fee
> pre-agreement between parties. On the commit tx you have your balance going
> exclusively towards you which you can unilaterally reduce to increase the
> fee up to whatever threshold you want. With a HTLC or PTLC you also always
> have a tx with an output that you can unilaterally drain to bump fee
> (either the hltc-success or htlc-timeout). Are you saying that there are
> protocols where this would require pre-arrangement or are you saying that
> it would require pre-arrangement in lightning for some reason I don't see?
>

Ok now I see what I am missing: We don't really know who owns certain
outputs in lightning until the most-recent-state-enforcement mechanism has
done its job. i.e. the outputs are 2-of-2s up until that has been resolved.
I was operating on some simplified imaginary lightning. Indeed this makes
the proposal far less attractive and does require interaction and
pre-agreement. This complexity here makes it worse than just keeping
external fee-bumping utxos around (as undesirable as this is). Thanks for
helping me figure this out.

LL

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Anthony Towns]

On Thu, May 27, 2021 at 04:14:13PM -0400, Antoine Riard via bitcoin-dev wrote:
> 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.

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

> [2] https://bitcointalk.org/index.php?topic=252960.0

I haven't seen any recent specs for "IOMAP", but there are a few things
that have bugged me about them in the past:

 (1) allowing partially overlapping sets of outputs could allow "theft",
     eg if I give you a signature "you can spend A+B as long as I get X"
     and "you can spend A+C as long as I get X", you could combine them
     to spend A+B+C instead but still only give me 1 X.

 (2) a range specification or a whole bitfield is a lot heavier than an
     extra bit to add to the sighash

 (3) this lets you specify lots of different ways of hashing the
     outputs, which then can't be cached, so you get kind-of quadratic
     behaviour -- O(n^2/8) where n/2 is the size of the inputs, which
     gives you the number of signatures, and n/2 is also the size of the
     outputs, so n/4 is a different half of the output selected for each
     signature in the input.

But under the "don't bring me problems, bring me solutions" banner,
here's an idea.

The easy way to avoid O(n^2) behaviour in (3) is to disallow partial
overlaps. So let's treat the tx as being distinct bundles of x-inputs
and y-outputs, and we'll use the annex for grouping, since that is
committed to by singatures. Call the annex field "sig_group_count".

When processing inputs, setup a new state pair, (start, end), initially
(0,0).

When evaluating an input, lookup sig_group_count. If it's not present,
then set start := end. If it's present and 0, leave start and end
unchanged. Otherwise, if it's present and greather than 0, set
start := end, and then set end := start + sig_group_count.

Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE,
that commits to each output i, start <= i < end. If start==end or end >
num_outputs, signature is invalid.

That means each output in a tx could be hashed three times instead of
twice (once for its particular group, as well as once for SIGHASH_ALL
and once for SIGHASH_SINGLE), and I think would let you combine x-input
and y-outputs fairly safely, by having the first input commit to "y"
in the annex, and the remaining x-1 commit to "0".

That does mean if you have two different sets of inputs (x1 and x2)
each spending to the exact same set of y outputs, you could claim all
but one of them while only paying a single set of y outputs. But you
could include an "OP_RETURN hash(x1)" tapleaf branch in one of the y
outputs to ensure the outputs aren't precisely the same to avoid that
problem, so maybe that's fine?

Okay, now that I've written and re-written that a couple of times,
it looks like I'm just reinventing Rusty's signature bundles from 2018:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015862.html

(though at least I think using the annex is probably an improvement on
having values that affect other inputs being buried deeper in an input's
witness data)



Without something like this, I think it will be very hard to incorporate
fees into eltoo with layered commitments [0]. As a new sighash mode it
would make sense to include it as part of ANYPREVOUT to avoid introducing
many new "unknown key types".

[0] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002448.html
    also, https://www.erisian.com.au/lightning-dev/log-2021-07-08.html

Cheers,
aj

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

On Thu, May 27, 2021 at 04:14:13PM -0400, Antoine Riard via bitcoin-dev
wrote:
> 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.

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

> [2] https://bitcointalk.org/index.php?topic=252960.0

> I haven't seen any recent specs for "IOMAP", but there are a few things
> that have bugged me about them in the past:

TBH, I don't think we have been further with Darosior than comparing the
compression schemes relevant for the bitfield :)

Thanks to start the hard grinding work!

>  (1) allowing partially overlapping sets of outputs could allow "theft",
>      eg if I give you a signature "you can spend A+B as long as I get X"
>      and "you can spend A+C as long as I get X", you could combine them
>      to spend A+B+C instead but still only give me 1 X.

Yes I think there is an even more unsafe case than described. A transaction
third-party knowledgeable about the partial sets could combine them, then
attach an additional siphoning output Y. E.g, if {A=50, B=50, C=50} and
X=100 the third-party could attach output Y=50 ?

Though I believe the validity of those thefts are a function of further
specification of the transaction digest coverage, as you might have a
malleability scheme where B or C's signatures hash are implicitly
committing to subset inputs order. If you have `H_prevouts(A || B)` and
`H_prevouts(A || C)`, an attacker wouldn't be able to satisfy both B and C
scripts in the same transaction ?

One mitigation which was mentioned in previous pinning discussion was to
add a per-participant finalizing key to A's script and thus lockdown
transaction template at broadcast. I don't think it works here as you can't
assume that your counterparties, from different protocol sessions, won't
collude together to combine their finalizing signatures and achieve a spend
replay across sessions ?

That said, I'm not even sure we should disallow partially overlapping sets
of outputs at the consensus-level, one could imagine a crowdfunding
application where you delegate A+B and A+C to different parties, and you
implicitly allow them to cooperate as long as they fulfill X's output value
?

>  (2) a range specification or a whole bitfield is a lot heavier than an
>      extra bit to add to the sighash

Yes, one quick optimization in case of far-depth output committed in the
bitfield could be to have a few initial bits serving as vectors to blank
out unused bitfield spaces. Though I concede a new sighash bits arithmetic
might be too fancy for consensus-code.


>  (3) this lets you specify lots of different ways of hashing the
>      outputs, which then can't be cached, so you get kind-of quadratic
>      behaviour -- O(n^2/8) where n/2 is the size of the inputs, which
>      gives you the number of signatures, and n/2 is also the size of the
>      outputs, so n/4 is a different half of the output selected for each
>      signature in the input.

If you assume n size of transaction data, and that each signature hash is
committing to inputs + half of outputs, yes I think it's even worst kind-of
quadratic, like O(3n^2/4) ? And you might even worsen the hashing in
function of flexibility allowed, like still committing to the whole
transaction size but a different combination order of outputs selected for
each signature.

But under the "don't bring me problems, bring me solutions" banner, here's
an idea.

> The easy way to avoid O(n^2) behaviour in (3) is to disallow partial
> overlaps. So let's treat the tx as being distinct bundles of x-inputs
> and y-outputs, and we'll use the annex for grouping, since that is
> committed to by singatures. Call the annex field "sig_group_count".

> When processing inputs, setup a new state pair, (start, end), initially
> (0,0).
>
> When evaluating an input, lookup sig_group_count. If it's not present,
> then set start := end. If it's present and 0, leave start and end
> unchanged. Otherwise, if it's present and greather than 0, set
> start := end, and then set end := start + sig_group_count.

IIUC the design rationale, the "sig_group_count" lockdowns the hashing of
outputs for a given input, thus allowing midstate reuse across signatures
input.

> Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE,
> that commits to each output i, start <= i < end. If start==end or end >
> num_outputs, signature is invalid.
>
> That means each output in a tx could be hashed three times instead of
> twice (once for its particular group, as well as once for SIGHASH_ALL
> and once for SIGHASH_SINGLE), and I think would let you combine x-input
> and y-outputs fairly safely, by having the first input commit to "y"
> in the annex, and the remaining x-1 commit to "0".
>
> That does mean if you have two different sets of inputs (x1 and x2)
> each spending to the exact same set of y outputs, you could claim all
> but one of them while only paying a single set of y outputs. But you
> could include an "OP_RETURN hash(x1)" tapleaf branch in one of the y
> outputs to ensure the outputs aren't precisely the same to avoid that
> problem, so maybe that's fine?

If the index i is absolute w.r.t to the transaction output index, I think
this design might have a shortcoming.

Let's say you want to combine {x_1, y_1} and {x_2, y_2} where {x, y}
denotes bundles of Lightning commitment transactions.

x_1 is dual-signed by Alice and Bob under the SIGHASH_GROUP flag with
`sig_group_count`=3.
x_2 is dual-signed by Alice and Caroll under the SIGHASH_GROUP flag, with
`sig_group_count`=2.
y_1 and y_2 are disjunctive.

At broadcast, Alice is not able to combine {x_1,y_1} and {x_2, y_2} for the
reason that x_1, x_2 are colliding on the absolute output position.

One fix could be to skim the "end > num_ouputs" semantic, and thus have
Alice negotiate (start,end) encompassing all her channels outputs index and
then strictly ordering her i indexes on all her counterparties. But I don't
think you can assume index order to be transitive across Lightning nodes,
at least without bundle combination gaps in your local set of channels.

I think this SIGHASH_GROUP proposal might solve other use-cases, but if I
understand the semantics correctly, it doesn't seem to achieve the batch
fee-bumping of multiple Lightning commitment with O(1) onchain footprint I
was thinking of for IOMAP...

One counter-proposal to solve this "pre-signed y-outputs ordinate" could be
instead to envision the SIGHASH_GROUP as vector coordinates and the annex
field as the projection.

Let's say annex field := (hashOutputsGroups) and SIGHASH_GROUP(i,j) where j
is a non-null integer.
Call i the starting index of the output group committed by this input.
Call j the output group size committed by this input.

At validation, compute `hashOutputsGroup` = H(outputs[i...i+j-1]).
If the computed `hashOutputGroup` isn't equal to the input annex field
`hashOutputsGroup`, fails validation.
Otherwise, substitute `hashOutputGroup` to bip-143 `hashOutputs` while
conserving , and proceed to signature verification.

As (i,j) are not included in the annex and are only part of witness data,
they can be selected by the bundles combiner at broadcast to construct a
valid transaction.

If the combiner is malicious and (i,j) points to another outputs group, the
computed hash is going to be invalid, as it doesn't satisfy the annex
`output_group` field.

If you want to disallow partial overlaps for your bundle, we could even
have a bit k. If k=1, verify that all transaction `output_group` fields are
not colliding.

Hmmmm, sounds more flexible but you might still have a bit of hashing
complexity to deal with ?

> Okay, now that I've written and re-written that a couple of times,
> it looks like I'm just reinventing Rusty's signature bundles from 2018:
>
>
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015862.html
>
> (though at least I think using the annex is probably an improvement on
> having values that affect other inputs being buried deeper in an input's
> witness data)
>
> Without something like this, I think it will be very hard to incorporate
> fees into eltoo with layered commitments [0]. As a new sighash mode it
> would make sense to include it as part of ANYPREVOUT to avoid introducing
> many new "unknown key types".

Well, I agree on the overall direction though maybe we should detail
primitive requirements a bit more, otherwise it might not fit the
second-layer use-case we're interested with.

Cheers,
Antoine

Le jeu. 8 juil. 2021 à 07:17, Anthony Towns <aj@erisian.com.au> a écrit :

> On Thu, May 27, 2021 at 04:14:13PM -0400, Antoine Riard via bitcoin-dev
> wrote:
> > 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.
>
> > 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.
>
> > [2] https://bitcointalk.org/index.php?topic=252960.0
>
> I haven't seen any recent specs for "IOMAP", but there are a few things
> that have bugged me about them in the past:
>
>  (1) allowing partially overlapping sets of outputs could allow "theft",
>      eg if I give you a signature "you can spend A+B as long as I get X"
>      and "you can spend A+C as long as I get X", you could combine them
>      to spend A+B+C instead but still only give me 1 X.
>
>  (2) a range specification or a whole bitfield is a lot heavier than an
>      extra bit to add to the sighash
>
>  (3) this lets you specify lots of different ways of hashing the
>      outputs, which then can't be cached, so you get kind-of quadratic
>      behaviour -- O(n^2/8) where n/2 is the size of the inputs, which
>      gives you the number of signatures, and n/2 is also the size of the
>      outputs, so n/4 is a different half of the output selected for each
>      signature in the input.
>
> But under the "don't bring me problems, bring me solutions" banner,
> here's an idea.
>
> The easy way to avoid O(n^2) behaviour in (3) is to disallow partial
> overlaps. So let's treat the tx as being distinct bundles of x-inputs
> and y-outputs, and we'll use the annex for grouping, since that is
> committed to by singatures. Call the annex field "sig_group_count".
>
> When processing inputs, setup a new state pair, (start, end), initially
> (0,0).
>
> When evaluating an input, lookup sig_group_count. If it's not present,
> then set start := end. If it's present and 0, leave start and end
> unchanged. Otherwise, if it's present and greather than 0, set
> start := end, and then set end := start + sig_group_count.
>
> Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE,
> that commits to each output i, start <= i < end. If start==end or end >
> num_outputs, signature is invalid.
>
> That means each output in a tx could be hashed three times instead of
> twice (once for its particular group, as well as once for SIGHASH_ALL
> and once for SIGHASH_SINGLE), and I think would let you combine x-input
> and y-outputs fairly safely, by having the first input commit to "y"
> in the annex, and the remaining x-1 commit to "0".
>
> That does mean if you have two different sets of inputs (x1 and x2)
> each spending to the exact same set of y outputs, you could claim all
> but one of them while only paying a single set of y outputs. But you
> could include an "OP_RETURN hash(x1)" tapleaf branch in one of the y
> outputs to ensure the outputs aren't precisely the same to avoid that
> problem, so maybe that's fine?
>
> Okay, now that I've written and re-written that a couple of times,
> it looks like I'm just reinventing Rusty's signature bundles from 2018:
>
>
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015862.html
>
> (though at least I think using the annex is probably an improvement on
> having values that affect other inputs being buried deeper in an input's
> witness data)
>
>
>
> Without something like this, I think it will be very hard to incorporate
> fees into eltoo with layered commitments [0]. As a new sighash mode it
> would make sense to include it as part of ANYPREVOUT to avoid introducing
> many new "unknown key types".
>
> [0]
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002448.html
>     also, https://www.erisian.com.au/lightning-dev/log-2021-07-08.html
>
> Cheers,
> aj
>
>

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

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Anthony Towns]

On Fri, Jul 09, 2021 at 09:19:45AM -0400, Antoine Riard via bitcoin-dev wrote:
> > The easy way to avoid O(n^2) behaviour in (3) is to disallow partial
> > overlaps. So let's treat the tx as being distinct bundles of x-inputs
> > and y-outputs, and we'll use the annex for grouping, since that is
> > committed to by singatures. Call the annex field "sig_group_count".
> > When processing inputs, setup a new state pair, (start, end), initially
> > (0,0).
> > When evaluating an input, lookup sig_group_count. If it's not present,
> > then set start := end. If it's present and 0, leave start and end
> > unchanged. Otherwise, if it's present and greather than 0, set
> > start := end, and then set end := start + sig_group_count.
> IIUC the design rationale, the "sig_group_count" lockdowns the hashing of
> outputs for a given input, thus allowing midstate reuse across signatures
> input.

No midstates, the message being signed would just replace
SIGHASH_SINGLE's:

  sha_single_output: the SHA256 of the corresponding output in CTxOut
  format

with

  sha_group_outputs: the SHA256 of the serialization of the group
  outputs in CTxOut format.

ie, you'd take span<CTxOut>{start,end}, serialize it (same as if it were
a vector of just those CTxOuts), and sha256 it.

> Let's say you want to combine {x_1, y_1} and {x_2, y_2} where {x, y} denotes
> bundles of Lightning commitment transactions.
> x_1 is dual-signed by Alice and Bob under the SIGHASH_GROUP flag with
> `sig_group_count`=3.
> x_2 is dual-signed by Alice and Caroll under the SIGHASH_GROUP flag, with
> `sig_group_count`=2.
> y_1 and y_2 are disjunctive.
> At broadcast, Alice is not able to combine {x_1,y_1} and {x_2, y_2} for the
> reason that x_1, x_2 are colliding on the absolute output position.

So the sha256 of the span of the group doesn't commit to start and end
-- it just serializes a vector, so commits to the number of elements,
the order, and the elements themselves. So you're taking serialize(y_1)
and serialize(y_2), and each of x_1 signs against the former, and each
of x_2 signs against the latter.

(Note that the annex for x_1_0 specifies sig_group_count=len(y_1)
and the annex for x_1_{1..} specifies sig_group_count=0, for "reuse
previous input's group", and the signatures for each input commit to
the annex anyway)

> One fix could be to skim the "end > num_ouputs" semantic,

That's only there to ensure the span doesn't go out of range, so I don't
think it makes any sense to skip it?

> I think this SIGHASH_GROUP proposal might solve other use-cases, but if I
> understand the semantics correctly, it doesn't seem to achieve the batch
> fee-bumping of multiple Lightning commitment with O(1) onchain footprint I was
> thinking of for IOMAP...

Does the above resolve that?

Cheers,
aj

Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent

[Antoine Riard]

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

> So the sha256 of the span of the group doesn't commit to start and end
> -- it just serializes a vector, so commits to the number of elements,
> the order, and the elements themselves.

Gotcha wasn't clear to me that the new state pair isn't committed as part
of the annex.

Have been confused by "Introduce a new SIGHASH_GROUP flag, as an
alternative to ALL/SINGLE/NONE, that commits to each output i, start <= i <
end."

> Does the above resolve that?

I think so. It shouldn't be susceptible to any spend replay attack, as the
state pair prevents output group overlapping though you might still have to
be careful about siphoning ? Something you should already care about if you
use SIGHASH_SINGLE and your x's amount > y's value.

Le ven. 9 juil. 2021 à 21:47, Anthony Towns <aj@erisian.com.au> a écrit :

> On Fri, Jul 09, 2021 at 09:19:45AM -0400, Antoine Riard via bitcoin-dev
> wrote:
> > > The easy way to avoid O(n^2) behaviour in (3) is to disallow partial
> > > overlaps. So let's treat the tx as being distinct bundles of x-inputs
> > > and y-outputs, and we'll use the annex for grouping, since that is
> > > committed to by singatures. Call the annex field "sig_group_count".
> > > When processing inputs, setup a new state pair, (start, end), initially
> > > (0,0).
> > > When evaluating an input, lookup sig_group_count. If it's not present,
> > > then set start := end. If it's present and 0, leave start and end
> > > unchanged. Otherwise, if it's present and greather than 0, set
> > > start := end, and then set end := start + sig_group_count.
> > IIUC the design rationale, the "sig_group_count" lockdowns the hashing of
> > outputs for a given input, thus allowing midstate reuse across signatures
> > input.
>
> No midstates, the message being signed would just replace
> SIGHASH_SINGLE's:
>
>   sha_single_output: the SHA256 of the corresponding output in CTxOut
>   format
>
> with
>
>   sha_group_outputs: the SHA256 of the serialization of the group
>   outputs in CTxOut format.
>
> ie, you'd take span<CTxOut>{start,end}, serialize it (same as if it were
> a vector of just those CTxOuts), and sha256 it.
>
> > Let's say you want to combine {x_1, y_1} and {x_2, y_2} where {x, y}
> denotes
> > bundles of Lightning commitment transactions.
> > x_1 is dual-signed by Alice and Bob under the SIGHASH_GROUP flag with
> > `sig_group_count`=3.
> > x_2 is dual-signed by Alice and Caroll under the SIGHASH_GROUP flag, with
> > `sig_group_count`=2.
> > y_1 and y_2 are disjunctive.
> > At broadcast, Alice is not able to combine {x_1,y_1} and {x_2, y_2} for
> the
> > reason that x_1, x_2 are colliding on the absolute output position.
>
> So the sha256 of the span of the group doesn't commit to start and end
> -- it just serializes a vector, so commits to the number of elements,
> the order, and the elements themselves. So you're taking serialize(y_1)
> and serialize(y_2), and each of x_1 signs against the former, and each
> of x_2 signs against the latter.
>
> (Note that the annex for x_1_0 specifies sig_group_count=len(y_1)
> and the annex for x_1_{1..} specifies sig_group_count=0, for "reuse
> previous input's group", and the signatures for each input commit to
> the annex anyway)
>
> > One fix could be to skim the "end > num_ouputs" semantic,
>
> That's only there to ensure the span doesn't go out of range, so I don't
> think it makes any sense to skip it?
>
> > I think this SIGHASH_GROUP proposal might solve other use-cases, but if I
> > understand the semantics correctly, it doesn't seem to achieve the batch
> > fee-bumping of multiple Lightning commitment with O(1) onchain footprint
> I was
> > thinking of for IOMAP...
>
> Does the above resolve that?
>
> Cheers,
> aj
>
>

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