Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
> 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 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{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
>
>
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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{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
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
On Tue, 15 Jun 2021 at 10:59, Lloyd Fournier wrote: > > > On Tue, 15 Jun 2021 at 02:47, Antoine Riard > 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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
On Tue, 15 Jun 2021 at 02:47, Antoine Riard 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 ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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 > ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
> This makes a lot of sense as it matches the semantics of what we are trying to achieve: allow the owner of an output (whether an individual or group) to reduce that output's value to pay a higher fee. Note, I think you're still struggling with some trust issue that anchor upgrade is at least eliminating for LN, namely the pre-agreement among a group of signers about the effective feerate to use at some unknown time point in the future. If you authorize your counterparty for a broadcast at feerate X, how do you prevent a broadcast at feerate Y, where Y is far under X, thus maliciously burning a lot of your fee-bumping reserve ? Of course, one mitigation is to make a contribution to a common fee-bumping output reserve proportional to what has been contributed as a funding collateral. Thus disincentivizing misuse of the common fee-bumping reserve in a game-theoretical way. But if you take the example of a LN channel, you're now running into another issue. Off-chain balances might fluctuate in a way that most of the time, your fee-bumping reserve contribution is out-of-proportion with your balance amounts to protect ? And as such enduring some significant timevalue bleeding on your fee-bumping reserve. Single-party managed fee-bumping reserve doesn't seem to suffer from this drawback ? Otherwise, I think your new construction OP_PUSH_TAPROOT_OUTPUT_KEY is correct and solves the O(log(n)) tapleaves issue. Le dim. 13 juin 2021 à 01:57, Lloyd Fournier a écrit : > On Fri, 11 Jun 2021 at 07:45, Antoine Riard > wrote: > >> Hi Lloyd, >> >> Thanks for this tx mutation proposal extending the scope of fee-bumping >> techniques. IIUC, the serves as a pointer to increase the >> output amount by value to recover the recompute the transaction hash >> against which the original signature is valid ? >> > > Right. > > >> Let's do a quick analysis of this scheme. >> * onchain footprint : one tapleaf per contract participant, with O(log n) >> increase of witness size, also one output per contract participant >> > > Yes but we can fix this (see below). > > * tx-relay bandwidth rebroadcast : assuming aforementioned in-place >> mempool substitution policy, the mutated transaction >> > * batching : fee-bumping value is extract from contract transaction >> itself, so O(n) per contract >> * mempool flexibility : the mutated transaction >> * watchtower key management : to enable outsourcing, the mutating key >> must be shared, in theory enabling contract value siphoning to miner fees ? >> > > Yes. You could use OP_LESSTHAN to make sure the value being deducted by > the watchtower is not above a threshold. > > >> Further, I think tx mutation scheme can be achieved in another way, with >> SIGHASH_ANYAMOUNT. A contract participant tapscript will be the following : >> >> >> >> Where is committed with SIGHASH_ANYAMOUNT, blanking >> nValue of one or more outputs. That way, the fee-to-contract-value >> distribution can be unilaterally finalized at a later time through the >> finalizing key [0]. >> > > Yes, that's also a way to do it. I was trying to preserve the original > external key signature in my attempt but this is probably not necessary. L2 > protocols could just exchange two signatures instead. One optimistic one on > the external key and one pessimistic SIGHASH_ANYAMOUNT one on the > . > > >> Note, I think that the tx mutation proposal relies on interactivity in >> the worst-case scenario where a counterparty wants to increase its >> fee-bumping output from the contract balance. This interactivity may lure a >> counterparty to alway lock the worst-case fee-bumping reserve in the >> output. I believe anchor output enables more "real-time" fee-bumping >> reserve adjustment ? >> > > Hmmm well I was hoping that you wouldn't need interaction ever. I can see > that my commitment TX example was too contrived because it has balance > outputs that go exclusively to one party. > Let's take a better example: A PTLC output with both timeout and success > pre-signed transactions spending from it. We must only let the person > offering the PTLC reduce the output of the timeout tx and the converse for > the success tx. > Note very carefully that if we naively apply OP_CHECKSIG_MUTATED or > SIGHASH_ANYAMOUNT with one tapleaf for each party then we risk one party > being able to lower the other party's output by doing a switcharoo on the > tapleaf after they see the signature for their counterparty's tx in the > mempool. In your example you could fix it by having a different > but this means we can't compress by just > using the taproot internal/external key. > > What about this: Instead of party specific "finalizing_alice_key" or > p1-fee-bump-key as I denoted it, we just use the key of the output whose > value we are reducing. This also solves the O(log(n)) tapleaves for > OP_CHECKSIG_MUTATED approach as well -- just have one tapleaf for fee > bumping but authorize it under the key of the output we are reducing. Thus > we need
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
On Fri, 11 Jun 2021 at 07:45, Antoine Riard wrote: > Hi Lloyd, > > Thanks for this tx mutation proposal extending the scope of fee-bumping > techniques. IIUC, the serves as a pointer to increase the > output amount by value to recover the recompute the transaction hash > against which the original signature is valid ? > Right. > Let's do a quick analysis of this scheme. > * onchain footprint : one tapleaf per contract participant, with O(log n) > increase of witness size, also one output per contract participant > Yes but we can fix this (see below). * tx-relay bandwidth rebroadcast : assuming aforementioned in-place mempool > substitution policy, the mutated transaction > * batching : fee-bumping value is extract from contract transaction itself, > so O(n) per contract > * mempool flexibility : the mutated transaction > * watchtower key management : to enable outsourcing, the mutating key must > be shared, in theory enabling contract value siphoning to miner fees ? > Yes. You could use OP_LESSTHAN to make sure the value being deducted by the watchtower is not above a threshold. > Further, I think tx mutation scheme can be achieved in another way, with > SIGHASH_ANYAMOUNT. A contract participant tapscript will be the following : > > > > Where is committed with SIGHASH_ANYAMOUNT, blanking > nValue of one or more outputs. That way, the fee-to-contract-value > distribution can be unilaterally finalized at a later time through the > finalizing key [0]. > Yes, that's also a way to do it. I was trying to preserve the original external key signature in my attempt but this is probably not necessary. L2 protocols could just exchange two signatures instead. One optimistic one on the external key and one pessimistic SIGHASH_ANYAMOUNT one on the . > Note, I think that the tx mutation proposal relies on interactivity in the > worst-case scenario where a counterparty wants to increase its fee-bumping > output from the contract balance. This interactivity may lure a > counterparty to alway lock the worst-case fee-bumping reserve in the > output. I believe anchor output enables more "real-time" fee-bumping > reserve adjustment ? > Hmmm well I was hoping that you wouldn't need interaction ever. I can see that my commitment TX example was too contrived because it has balance outputs that go exclusively to one party. Let's take a better example: A PTLC output with both timeout and success pre-signed transactions spending from it. We must only let the person offering the PTLC reduce the output of the timeout tx and the converse for the success tx. Note very carefully that if we naively apply OP_CHECKSIG_MUTATED or SIGHASH_ANYAMOUNT with one tapleaf for each party then we risk one party being able to lower the other party's output by doing a switcharoo on the tapleaf after they see the signature for their counterparty's tx in the mempool. In your example you could fix it by having a different but this means we can't compress by just using the taproot internal/external key. What about this: Instead of party specific "finalizing_alice_key" or p1-fee-bump-key as I denoted it, we just use the key of the output whose value we are reducing. This also solves the O(log(n)) tapleaves for OP_CHECKSIG_MUTATED approach as well -- just have one tapleaf for fee bumping but authorize it under the key of the output we are reducing. Thus we need something like OP_PUSH_TAPROOT_OUTPUT_KEY which takes the taproot external key at that output (fail if not taproot) and puts it on the stack. So to be clear you have the on the witness stack rather than having it fixed in a particular tapleaf (as per my original post) and then use OP_DUP to pass it to both OP_CHECKSIG_MUTATED and OP_PUSH_TAPROOT_OUTPUT_KEY. This makes a lot of sense as it matches the semantics of what we are trying to achieve: allow the owner of an output (whether an individual or group) to reduce that output's value to pay a higher fee. Furthermore this removes all keys from the tapleaf since they are all aliased to either the input we are spending or one of the output keys of the tx we are spending to. This is quite a big improvement over my original idea. This works for lightning commit tx and for the case of a PTLC contract. It also seems to work for the DLC funding output. I'd be interested to know if anyone can think of a protocol where this would be inconvenient or impossible to use as the main pre-signed tx fee bumping system. Cheers, LL Le dim. 6 juin 2021 à 22:28, Lloyd Fournier a > écrit : > >> Hi Antione, >> >> Thanks for bringing up this important topic. I think there might be >> another class of solutions over input based, CPFP and sponsorship. I'll >> call them tx mutation schemes. The idea is that you can set a key that can >> increase the fee by lowering a particular output after the tx is signed >> without invalidating the signature. The premise is that anytime you need to >> bump the fee of a transaction you must necessarily have funds in
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
> 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 a écrit : > >> Hi Antione, >> >> Thanks for bringing up this important topic. I think there might be another >> class of solutions over input based, CPFP and sponsorship. I'll call them tx >> mutation schemes. The idea is that you can set a key that can increase the >> fee by lowering a particular output after the tx is signed without >> invalidating the signature. The premise is that anytime you need to bump the >> fee of a transaction you must necessarily have funds in an output that are >> going to you and therefore you can sacrifice some of them to increase the >> fee. This is obviously destructive to txids so child presigned transactions >> will have to use ANYPREVOUT as in your proposal. The advantage is that it >> does not require keeping extra inputs around to bump the fee. >> >> So imagine a new opcode OP_CHECKSIG_MUTATED >> . >> This would check that is valid against if the >> current transaction had the output at reduced by . To >> make this more efficient, if the public key is one byte: 0x02 it references >> the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to refer to >> internal key[1]). >> Now for our protocol we want both parties (p1 and p2) to be able to fee bump >> a commitment transaction. They use MuSig to sign the commitment tx under the >> external key with a decent fee for the current conditions. But in case it >> proves insufficient they have added the following two leaves to their key in >> the funding output as a backup so that p1 and p2 can unilaterally bump the >> fee of anything they sign spending from the funding output: >> >> 1. OP_CHECKSIG_MUTATED(0, 0x02, , ) >> OP_CHECKSIGADD(p1-fee-bump-key, ) OP_2 >> OP_NUMEQUALVERIFY >> 2. OP_CHECKSIG_MUTATED(1, 0x02, , ) >> OP_CHECKSIGADD(p2-fee-bump-key, ) OP_2 >> OP_NUMEQUALVERIFY >> >> where <...> indicates the thing comes from the witness stack. >> So to bump the fee of the commit tx after it has been signed either party >> takes the and adds a signature under their fee-bump-key >> for the new tx and reveals their fee bump leaf. is >> checked against the old transaction while the fee bumped transaction is >> checked against the fee bump key. >> >> I know I have left out how to change mempool eviction rules to accommodate >> this kind of fee bumping without DoS or pinning attacks but hopefully I have >> demonstrated that this class of solutions also exists. >> >> [1] https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-0118.mediawiki >> >> Cheers, >> >> LL >> >> On Fri, 28 May 2021 at 07:13, Antoine Riard via bitcoin-dev >> wrote: >> >>> Hi, >>> >>> This post is pursuing a wider discussion around better
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
Hi Lloyd, Thanks for this tx mutation proposal extending the scope of fee-bumping techniques. IIUC, the serves as a pointer to increase the output amount by value to recover the recompute the transaction hash against which the original signature is valid ? 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 : Where is committed with SIGHASH_ANYAMOUNT, blanking nValue of one or more outputs. That way, the fee-to-contract-value distribution can be unilaterally finalized at a later time through the finalizing key [0]. 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 a écrit : > Hi Antione, > > Thanks for bringing up this important topic. I think there might be > another class of solutions over input based, CPFP and sponsorship. I'll > call them tx mutation schemes. The idea is that you can set a key that can > increase the fee by lowering a particular output after the tx is signed > without invalidating the signature. The premise is that anytime you need to > bump the fee of a transaction you must necessarily have funds in an output > that are going to you and therefore you can sacrifice some of them to > increase the fee. This is obviously destructive to txids so child presigned > transactions will have to use ANYPREVOUT as in your proposal. The advantage > is that it does not require keeping extra inputs around to bump the fee. > > So imagine a new opcode OP_CHECKSIG_MUTATED > . > This would check that is valid against if the > current transaction had the output at reduced by . To > make this more efficient, if the public key is one byte: 0x02 it references > the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to refer to > internal key[1]). > Now for our protocol we want both parties (p1 and p2) to be able to fee > bump a commitment transaction. They use MuSig to sign the commitment tx > under the external key with a decent fee for the current conditions. But in > case it proves insufficient they have added the following two leaves to > their key in the funding output as a backup so that p1 and p2 can > unilaterally bump the fee of anything they sign spending from the funding > output: > > 1. OP_CHECKSIG_MUTATED(0, 0x02, , ) > OP_CHECKSIGADD(p1-fee-bump-key, ) OP_2 > OP_NUMEQUALVERIFY > 2. OP_CHECKSIG_MUTATED(1, 0x02, , ) > OP_CHECKSIGADD(p2-fee-bump-key, ) OP_2 > OP_NUMEQUALVERIFY > > where <...> indicates the thing comes from the witness stack. > So to bump the fee of the commit tx after it has been signed either party > takes the and adds a signature under their > fee-bump-key for the new tx and reveals their fee bump leaf. > is checked against the old transaction while the fee > bumped transaction is checked against the fee bump key. > > I know I have left out how to change mempool eviction rules to accommodate > this kind of fee bumping without DoS or pinning attacks but hopefully I > have demonstrated that this class of solutions also exists. > > [1] https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-0118.mediawiki > > Cheers, > > LL > > > > On Fri, 28 May 2021 at 07:13, Antoine Riard via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Hi, >> >> This post is pursuing a wider discussion around better fee-bumping >> strategies for second-layer protocols. It draws out a comparison between >> input-based and CPFP fee-bumping techniques, and their apparent trade-offs >> in terms of onchain footprint, tx-relay bandwidth rebroadcast, batching >> opportunity and mempool flexibility. >> >> Thanks to Darosior for reviews, ideas and discussions. >> >> ## Child-Pay-For-Parent >> >> CPFP is a mature fee-bumping technique, known and used for a while in the >> Bitcoin ecosystem. However, its usage in contract protocols with >> distrusting
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
> 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 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
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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 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 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,
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
Hi Antione, Thanks for bringing up this important topic. I think there might be another class of solutions over input based, CPFP and sponsorship. I'll call them tx mutation schemes. The idea is that you can set a key that can increase the fee by lowering a particular output after the tx is signed without invalidating the signature. The premise is that anytime you need to bump the fee of a transaction you must necessarily have funds in an output that are going to you and therefore you can sacrifice some of them to increase the fee. This is obviously destructive to txids so child presigned transactions will have to use ANYPREVOUT as in your proposal. The advantage is that it does not require keeping extra inputs around to bump the fee. So imagine a new opcode OP_CHECKSIG_MUTATED . This would check that is valid against if the current transaction had the output at reduced by . To make this more efficient, if the public key is one byte: 0x02 it references the taproot *external key* (similar to how ANYPREVOUT uses 0x01 to refer to internal key[1]). Now for our protocol we want both parties (p1 and p2) to be able to fee bump a commitment transaction. They use MuSig to sign the commitment tx under the external key with a decent fee for the current conditions. But in case it proves insufficient they have added the following two leaves to their key in the funding output as a backup so that p1 and p2 can unilaterally bump the fee of anything they sign spending from the funding output: 1. OP_CHECKSIG_MUTATED(0, 0x02, , ) OP_CHECKSIGADD(p1-fee-bump-key, ) OP_2 OP_NUMEQUALVERIFY 2. OP_CHECKSIG_MUTATED(1, 0x02, , ) OP_CHECKSIGADD(p2-fee-bump-key, ) OP_2 OP_NUMEQUALVERIFY where <...> indicates the thing comes from the witness stack. So to bump the fee of the commit tx after it has been signed either party takes the and adds a signature under their fee-bump-key for the new tx and reveals their fee bump leaf. is checked against the old transaction while the fee bumped transaction is checked against the fee bump key. I know I have left out how to change mempool eviction rules to accommodate this kind of fee bumping without DoS or pinning attacks but hopefully I have demonstrated that this class of solutions also exists. [1] https://github.com/ajtowns/bips/blob/bip-anyprevout/bip-0118.mediawiki Cheers, LL On Fri, 28 May 2021 at 07:13, Antoine Riard via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi, > > This post is pursuing a wider discussion around better fee-bumping > strategies for second-layer protocols. It draws out a comparison between > input-based and CPFP fee-bumping techniques, and their apparent trade-offs > in terms of onchain footprint, tx-relay bandwidth rebroadcast, batching > opportunity and mempool flexibility. > > Thanks to Darosior for reviews, ideas and discussions. > > ## Child-Pay-For-Parent > > CPFP is a mature fee-bumping technique, known and used for a while in the > Bitcoin ecosystem. However, its usage in contract protocols with > distrusting counterparties raised some security issues. As mempool's chain > of unconfirmed transactions are limited in size, if any output is spendable > by any contract participant, it can be leveraged as a pinning vector to > downgrade odds of transaction confirmation [0]. > > That said, contract transactions interested to be protected under the > carve-out logic require to add a new output for any contract participant, > even if ultimately only one of them serves as an anchor to attach a CPFP. > > ## Input-Based > > I think input-based fee-bumping has been less studied as fee-bumping > primitive for L2s [1]. One variant of input-based fee-bumping usable today > is the leverage of the SIGHASH_ANYONECANPAY/SIGHASH_SINGLE malleability > flags. If the transaction is the latest stage of the contract, a bumping > input can be attached just-in-time, thus increasing the feerate of the > whole package. > > However, as of today, input-based fee-bumping doesn't work to bump first > stages of contract transactions as it's destructive of the txid, and as > such breaks chain of pre-signed transactions. A first improvement would be > the deployment of the SIGHASH_ANYPREVOUT softfork proposal. This new > malleability flag allows a transaction to be signed without reference to > any specific previous output. That way, spent transactions can be > fee-bumped without altering validity of the chain of transactions. > > Even assuming SIGHASH_ANYPREVOUT, if the first stage contract transaction > includes multiple outputs (e.g the LN's commitment tx has multiple HTLC > outputs), SIGHASH_SINGLE can't be used and the fee-bumping input value > might be wasted. This edge can be smoothed by broadcasting a preliminary > fan-out transaction with a set of outputs providing a range of feerate > points for the bumped transaction. > > This overhead could be smoothed even further in the future with more > advanced sighash malleability flags like SIGHASH_IOMAP,
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
> 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.___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
> 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 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
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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.___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
[bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
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
