[bitcoin-dev] Transaction Merging (bip125 relaxation)

[Rhavar via bitcoin-dev]

So my half-baked idea is very simple:

Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.

This is currently not possible because of the bip125 rule:
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."

Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.

I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?

---
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.

From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.

However, the real problem is tracking the mess. Consider this sequence of events:
1) I have unconfirmed transaction A
2) I replace it with B, which pays John 1 BTC
3) Transaction A gets confirmed

So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.

One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.

However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.

There's a few other hacks you can do to make it work in a few more cases, but nothing that is realistic to expect anyone to implement any time soon.

However, if there was a straight foward way to merge N unconfirmed transactions, it would be easy get into production, and potentially offer some pretty nice savings for everyone.

[Rhavar via bitcoin-dev]

If you spent your change from transaction A, that would be safe. There'd be no way you John could end up with 2 BTC from you then.

Yes, that's what the following paragraph says -- along with it's limitations =)

-Ryan

-------- Original Message --------

So now I still owe John 1 BTC, however it's not immediately clear if it's safe to send to him

If you spent your change from transaction A, that would be safe. There'd be no way you John could end up with 2 BTC from you then.

Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."
Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?
---
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
1) I have unconfirmed transaction A
2) I replace it with B, which pays John 1 BTC
3) Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.
There's a few other hacks you can do to make it work in a few more cases, but nothing that is realistic to expect anyone to implement any time soon.
However, if there was a straight foward way to merge N unconfirmed transactions, it would be easy get into production, and potentially offer some pretty nice savings for everyone.
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Moral Agent via bitcoin-dev]

Along the same lines, I wonder if unrelated people with tx that are not
confirming could cooperate to merge their disparate tx into a CoinJoin tx
with a higher fee rate?

Perhaps they could even replace old tx with economically equivalent summary
transactions?

The mempool seems like nature's accumulator for pre-mining compression
opportunities.

On Mon, Jan 22, 2018 at 1:18 PM, Rhavar via bitcoin-dev <

If you spent your change from transaction A, that would be safe. There'd

be no way you John could end up with 2 BTC from you then.
Yes, that's what the following paragraph says -- along with it's limitations =)
-Ryan
-------- Original Message --------

So now I still owe John 1 BTC, however it's not immediately clear if it's

safe to send to him
If you spent your change from transaction A, that would be safe. There'd
be no way you John could end up with 2 BTC from you then.
On Mon, Jan 22, 2018 at 1:40 PM, Rhavar via bitcoin-dev <

Allow users to merge multiple unconfirmed transactions, stripping
extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum
paid by the original transactions."
Because the size of the merged transaction is smaller than the original
transactions, unless there is a considerable feerate bump, this rule isn't
possible to observe.
I my question is: is it possible or reasonable to relax this rule? If
this rule was removed in its entirety, does it introduce any DoS vectors?
Or can it be changed to allow my use-case?
---
Full backstory: I have been trying to use bip125 (Opt-in Full
Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I
owe John 1 bitcoin, and have promised to pay him immediately: Instead of
creating a whole new transaction if I have an in-flight (unconfirmed)
transaction, I can follow the rules of bip125 to create a replacement that
accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
1) I have unconfirmed transaction A
2) I replace it with B, which pays John 1 BTC
3) Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if
it has change, so if the original transaction confirms -- payments can
immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.
There's a few other hacks you can do to make it work in a few more cases,
but nothing that is realistic to expect anyone to implement any time soon.
However, if there was a straight foward way to merge N unconfirmed
transactions, it would be easy get into production, and potentially offer
some pretty nice savings for everyone.
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Rhavar via bitcoin-dev]

Perhaps they could even replace old tx with economically equivalent summary transactions?

I imagine with schnorr signatures, the incentives will emerge for that to make sense. But right now if I want to merge my transaction with an untrusted party in general we're only really going to be saving like 12 bytes of overhead or something. But if I'm merging my own transactions, I can get that fixed overhead, strip extraneous inputs and merge my change outputs (which also means in the future it's cheaper to spend).

Although it's obviously a lot worse for privacy, I do like the pattern of broadcast the transaction standalone and then merge it for savings. It helps keep the more or less fire-and-forget style, without a ridiculous amount of complexity "if this happens, do this, if this, then this, ..."

-Ryan

-Ryan

-------- Original Message --------

Along the same lines, I wonder if unrelated people with tx that are not confirming could cooperate to merge their disparate tx into a CoinJoin tx with a higher fee rate?
Perhaps they could even replace old tx with economically equivalent summary transactions?
The mempool seems like nature's accumulator for pre-mining compression opportunities.

Post by Rhavar via bitcoin-dev

If you spent your change from transaction A, that would be safe. There'd be no way you John could end up with 2 BTC from you then.

Yes, that's what the following paragraph says -- along with it's limitations =)
-Ryan
-------- Original Message --------

So now I still owe John 1 BTC, however it's not immediately clear if it's safe to send to him

If you spent your change from transaction A, that would be safe. There'd be no way you John could end up with 2 BTC from you then.

Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."
Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?
---
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
1) I have unconfirmed transaction A
2) I replace it with B, which pays John 1 BTC
3) Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.
There's a few other hacks you can do to make it work in a few more cases, but nothing that is realistic to expect anyone to implement any time soon.
However, if there was a straight foward way to merge N unconfirmed transactions, it would be easy get into production, and potentially offer some pretty nice savings for everyone.
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Peter Todd via bitcoin-dev]

Post by Rhavar via bitcoin-dev
Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."
Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?

It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth. You'd also be able to push others' txs out of the mempool.

Post by Rhavar via bitcoin-dev
---
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
1) I have unconfirmed transaction A
2) I replace it with B, which pays John 1 BTC
3) Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.

Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

[Rhavar via bitcoin-dev]

Post by Peter Todd via bitcoin-dev
Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

It's actually a common misconception. With good coin selection, I am able to avoid change about ~75% of the time in my simulations (on my real world data). In practice it's a bit lower, probably about 40-50% of the time because of the need to keep the majority of my funds offline where they can't be used for coin selection, and I have not been able to accurate simulate how I consolidate.

Also the other misconception is that inputs don't need to match exactly the requested payment, it's totally fine to do something I call a "miner sacrifice" where you overpay txfees up to the amount that that would otherwise be the total cost (immediate + consolidation) of creating change.

Also another trick I use, is something I call "output selection". If I have N queued non-time sensitive payments, I don't really need to send them all at the same time. So I can pick the best combination of inputs+outputs.

Obviously none of this applies to consumer wallets, who typically have less than a handful of options. But for a service, avoiding change can be the norm with good coin selection.

---

-Ryan

-------- Original Message --------

Post by Peter Todd via bitcoin-dev

Post by Rhavar via bitcoin-dev
Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."
Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?

It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth. You'd also be able to push others' txs out of the mempool.

Post by Rhavar via bitcoin-dev
---------------------------------------------------------------
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
- I have unconfirmed transaction A
- I replace it with B, which pays John 1 BTC
- Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.

Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

[Rhavar via bitcoin-dev]

Post by Peter Todd via bitcoin-dev
It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth.

I think I'm missing something, as I don't really understand this DoS vector. Relay bandwidth is already very cheap and easy to use by repeatedly fee bumping. And it's not obvious to me that requiring an absolute higher fee actually makes such an attack more expensive.

I can see that my "proposed" change would make it cheaper to evict low-fee transactions from other node's mempool. Maybe I'm being naive, but I don't really see why this would be such a big deal.

But what about a compromise, and require that the absolute fee must be >= half the original fees. I know everyone hates magic values, but I think in practice it will allow legitimate and useful use of "retroactive transaction merging" without much downside.

And really the great thing about "retroactive transaction merging" is just how easy it is to implement. In fact, right now it's quite possible to do -- but because of the "higher absolute fee" rule the benefits are pretty muted (although if you can compress 2 change into 1, that's still likely worthwhile)

-Ryan

-------- Original Message --------

Post by Peter Todd via bitcoin-dev

Post by Rhavar via bitcoin-dev
Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."
Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?

It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth. You'd also be able to push others' txs out of the mempool.

Post by Rhavar via bitcoin-dev
---------------------------------------------------------------
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
- I have unconfirmed transaction A
- I replace it with B, which pays John 1 BTC
- Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.

Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

[Moral Agent via bitcoin-dev]

Another way to limit abuse would be to have the fee *rate* be required to
increase, which is kind of the spirit of RBF, applied to this situation.

That is to say, if you wished to replace transactions A and B with C which
spends the same inputs as A and B, then the following must be true before C
will be relayed:

(Fee_A + Fee_B) / (Weight_A + Weight_B) < Fee_C / Weight_C

On Tue, Jan 23, 2018 at 11:31 AM, Rhavar via bitcoin-dev <

Post by Peter Todd via bitcoin-dev
It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth.
I think I'm missing something, as I don't really understand this DoS
vector. Relay bandwidth is already very cheap and easy to use by repeatedly
fee bumping. And it's not obvious to me that requiring an absolute higher
fee actually makes such an attack more expensive.
I can see that my "proposed" change would make it cheaper to evict low-fee
transactions from other node's mempool. Maybe I'm being naive, but I don't
really see why this would be such a big deal.
But what about a compromise, and require that the absolute fee must be >=
half the original fees. I know everyone hates magic values, but I think in
practice it will allow legitimate and useful use of "retroactive
transaction merging" without much downside.
And really the great thing about "retroactive transaction merging" is just
how easy it is to implement. In fact, right now it's quite possible to do
-- but because of the "higher absolute fee" rule the benefits are pretty
muted (although if you can compress 2 change into 1, that's still likely
worthwhile)
-Ryan
-------- Original Message --------
Allow users to merge multiple unconfirmed transactions, stripping
extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid
by the original transactions."
Because the size of the merged transaction is smaller than the original
transactions, unless there is a considerable feerate bump, this rule isn't
possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this
rule was removed in its entirety, does it introduce any DoS vectors? Or can
it be changed to allow my use-case?
It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth. You'd also be able to push others' txs out of the mempool.
------------------------------
Full backstory: I have been trying to use bip125 (Opt-in Full
Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I
owe John 1 bitcoin, and have promised to pay him immediately: Instead of
creating a whole new transaction if I have an in-flight (unconfirmed)
transaction, I can follow the rules of bip125 to create a replacement that
accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
1. I have unconfirmed transaction A
2. I replace it with B, which pays John 1 BTC
3. Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if
it has change, so if the original transaction confirms -- payments can
immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.
Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Rhavar via bitcoin-dev]

Interesting. I didn't think about this before, but it seems like bip125 is rather incentive incompatible right now? If we're assuming a competitive mempool, it really doesn't seem generally rational to accept a replacement transaction of a lower fee rate.

So how about if we change the fee requirement to bet at least:

MIN(
$ORIGINAL_FEE_RATE * $REPLACEMENT_TX_SIZE + $RELAY_FEE * ( REPLACEMENT_TX_SIZE + $ORIGINAL_SIZE),
$ORIGINAL_ABS_FEE / 3
) in fees

This could make it:
* More incentive compatible
* Support more use-cases (my transaction merging example)
* Be resistant to any attacks (that I can see, there's no doubt cases I haven't thought about)

-Ryan

-------- Original Message --------

Another way to limit abuse would be to have the fee *rate* be required to increase, which is kind of the spirit of RBF, applied to this situation.
(Fee_A + Fee_B) / (Weight_A + Weight_B) < Fee_C / Weight_C

Post by Rhavar via bitcoin-dev

Post by Peter Todd via bitcoin-dev
It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth.

I think I'm missing something, as I don't really understand this DoS vector. Relay bandwidth is already very cheap and easy to use by repeatedly fee bumping. And it's not obvious to me that requiring an absolute higher fee actually makes such an attack more expensive.
I can see that my "proposed" change would make it cheaper to evict low-fee transactions from other node's mempool. Maybe I'm being naive, but I don't really see why this would be such a big deal.
But what about a compromise, and require that the absolute fee must be >= half the original fees. I know everyone hates magic values, but I think in practice it will allow legitimate and useful use of "retroactive transaction merging" without much downside.
And really the great thing about "retroactive transaction merging" is just how easy it is to implement. In fact, right now it's quite possible to do -- but because of the "higher absolute fee" rule the benefits are pretty muted (although if you can compress 2 change into 1, that's still likely worthwhile)
-Ryan
-------- Original Message --------

Post by Peter Todd via bitcoin-dev

Post by Rhavar via bitcoin-dev
Allow users to merge multiple unconfirmed transactions, stripping extraneous inputs and change as they go.
"The replacement transaction pays an absolute fee of at least the sum paid by the original transactions."
Because the size of the merged transaction is smaller than the original transactions, unless there is a considerable feerate bump, this rule isn't possible to observe.
I my question is: is it possible or reasonable to relax this rule? If this rule was removed in its entirety, does it introduce any DoS vectors? Or can it be changed to allow my use-case?

It would definitely introduce DoS vectors by making it much cheaper to use
relay bandwidth. You'd also be able to push others' txs out of the mempool.

Post by Rhavar via bitcoin-dev
---------------------------------------------------------------
Full backstory: I have been trying to use bip125 (Opt-in Full Replace-by-Fee) to do "transaction merging" on the fly. Let's say that I owe John 1 bitcoin, and have promised to pay him immediately: Instead of creating a whole new transaction if I have an in-flight (unconfirmed) transaction, I can follow the rules of bip125 to create a replacement that accomplishes this goal.
From a "coin selection" point of view, this was significantly easier than
I had anticipated. I was able to encode the rules in my linear model and
feed in all my unspent and in-flight transactions and it can solve it without difficulty.
- I have unconfirmed transaction A
- I replace it with B, which pays John 1 BTC
- Transaction A gets confirmed
So now I still owe John 1 BTC, however it's not immediately clear if
it's safe to send to him without waiting $n transactions. However even
for a small $n, this breaks my promise to pay him immediately.
One possible solution is to only consider a transaction "replaceable" if it has change, so if the original transaction confirms -- payments can immediately be made that source the change, and provide safety in a reorg.
However, this will only work <50% of the time for me (most transactions
don't have change) and opens a pandora's box of complexity.

Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gregory Maxwell via bitcoin-dev]

On Tue, Jan 23, 2018 at 10:19 PM, Rhavar via bitcoin-dev

Post by Rhavar via bitcoin-dev
Interesting. I didn't think about this before, but it seems like bip125 is
rather incentive incompatible right now? If we're assuming a competitive
mempool, it really doesn't seem generally rational to accept a replacement
transaction of a lower fee rate.

BIP125 replacement requires that the fee rate increases. The text of
the BIP document is written in a confusing way that doesn't make this
clear.

[Peter Todd via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
On Tue, Jan 23, 2018 at 10:19 PM, Rhavar via bitcoin-dev

Post by Rhavar via bitcoin-dev
Interesting. I didn't think about this before, but it seems like bip125 is
rather incentive incompatible right now? If we're assuming a competitive
mempool, it really doesn't seem generally rational to accept a replacement
transaction of a lower fee rate.

BIP125 replacement requires that the fee rate increases. The text of
the BIP document is written in a confusing way that doesn't make this
clear.

In fact I considered only requiring an increase in fee rate, based on the
theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.

[Alan Evans via bitcoin-dev]

So, OP, in your scenario, you have 1 transaction in the mempool, A, then
you want to spend the change before confirmation, so you broadcast a new
transaction, B, which replaces A.

Post by Rhavar via bitcoin-dev
Because the size of the merged transaction is smaller than the original

transactions, unless there is a considerable feerate bump, this rule isn't
possible to observe.

I'm confused, the mempool only sees 1 transaction at a time, first A, then
later B. " the original transactions", plural, should not exist in the
mempool.

B's fee and rate needs to be larger than A's, but B will be greater than or
equal to A anyway. So, just increasing the fee rate will cause a larger fee
anyway.

Am I missing something?


On Wed, Jan 24, 2018 at 3:44 AM, Peter Todd via bitcoin-dev <

Post by Rhavar via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
On Tue, Jan 23, 2018 at 10:19 PM, Rhavar via bitcoin-dev

Post by Rhavar via bitcoin-dev
Interesting. I didn't think about this before, but it seems like

bip125 is

Post by Gregory Maxwell via bitcoin-dev

Post by Rhavar via bitcoin-dev
rather incentive incompatible right now? If we're assuming a

competitive

Post by Gregory Maxwell via bitcoin-dev

Post by Rhavar via bitcoin-dev
mempool, it really doesn't seem generally rational to accept a

replacement

Post by Gregory Maxwell via bitcoin-dev

Post by Rhavar via bitcoin-dev
transaction of a lower fee rate.

BIP125 replacement requires that the fee rate increases. The text of
the BIP document is written in a confusing way that doesn't make this
clear.

In fact I considered only requiring an increase in fee rate, based on the
theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.
--
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Rhavar via bitcoin-dev]

I'm confused, the mempool only sees 1 transaction at a time, first A, then later B. "the original transactions", plural, should not exist in the mempool.
B's fee and rate needs to be larger than A's, but B will be greater than or equal to A anyway. So, just increasing the fee rate will cause a larger fee anyway.
Am I missing something?

Kind of. The first case is that you do the "smarter" type of merging, where you get an original transaction and then say add an additional output(s) to it.

The issue with this, is from a practical perspective is _very_ complex. Because you really need to do a lot of tracking to see which of the two transactions actually confirm. And if you are promising fast payments, you can be stuck in a weird limbo state where you're waiting for the original one to "safely" confirm before it's safe to make a re-payment (even a non-malicious will likely contain the replacement).

bip125 already supports this use-case, but I will suggest that the logic to deploy this is sufficiently complex that no one is going to attempt any time in the near future.


But "retroactive transaction merging" is actually pretty approachable problem for a service to implement. You just get N valid transactions you've made, merge them into one. Strip extraneous inputs[1], and combine and alter the change amount.

The reason this is so appealing to implement, is there is very little complexity. If the "retroactive transaction merge" fails, or doesn't get confirmed, it actually has no impact. If it does get confirmed, that's just pure cost-savings.

However, the rules of bip125 currently make it (unnecessarily?) unappealing, because I can never lower the absolute amount of fees I pay. Hence I think it'd be pretty sweet if they could be relaxed to support this if it can be done in a pretty risk free way.



[1] Need to be very careful with that, if you're ever merging a merged transaction.

Post by Peter Todd via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
On Tue, Jan 23, 2018 at 10:19 PM, Rhavar via bitcoin-dev

Post by Rhavar via bitcoin-dev
Interesting. I didn't think about this before, but it seems like bip125 is
rather incentive incompatible right now? If we're assuming a competitive
mempool, it really doesn't seem generally rational to accept a replacement
transaction of a lower fee rate.

BIP125 replacement requires that the fee rate increases.  The text of
the BIP document is written in a confusing way that doesn't make this
clear.

In fact I considered only requiring an increase in fee rate, based on the
theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.
--
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Sjors Provoost via bitcoin-dev]

I can see how merging after the fact could be more practical than appending existing transactions.

I think what Moral Agent suggested is the same as your original proposal, namely dropping rule 3. Only fee per weight unit increase from rule 4 would matter.

The minimum per WU increase could be far higher than the minimum relay fee. The few times I’ve used RBF in practice I increased the fee by at least 50%. Rule 4 could be made more strict. I don’t know what number, if any, would address concerns about relay spam?

This wouldn’t be backward compatible. Does that matter as long as there’s enough nodes that follow the new rules? Is there a punishment for relaying transactions that violate rule 3? Could a recipient using the older rules be mislead (in a way that’s worse than the fact that RBF allows the sender to replace the transaction with anything they want anyway)?

Post by Peter Todd via bitcoin-dev
You'd also be able to push others' txs out of the mempool.

Can you elaborate on this issue?

Post by Peter Todd via bitcoin-dev
payment service for instance where a large number of deposits are aggregated into a smaller number of payments

So this would involve wallets (of users who deposit coins) cooperating with an exchange API to consolidate in-mempool transactions?

Post by Peter Todd via bitcoin-dev
In fact I considered only requiring an increase in fee rate, based on the

theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.

Why would you need to consider the whole mempool? Let’s say a miner is considering to replace transaction A and B with transaction C, where C pays a higher fee per byte than both A and B. This creates space for ~ one additional transaction in the block. It seems to me the miner only needs to check that the lowest fee per weight transaction > min_fee(A,B). At least in first approximation.

Sjors

Post by Peter Todd via bitcoin-dev

I'm confused, the mempool only sees 1 transaction at a time, first A, then later B. "the original transactions", plural, should not exist in the mempool.
B's fee and rate needs to be larger than A's, but B will be greater than or equal to A anyway. So, just increasing the fee rate will cause a larger fee anyway.
Am I missing something?

Kind of. The first case is that you do the "smarter" type of merging, where you get an original transaction and then say add an additional output(s) to it.
The issue with this, is from a practical perspective is _very_ complex. Because you really need to do a lot of tracking to see which of the two transactions actually confirm. And if you are promising fast payments, you can be stuck in a weird limbo state where you're waiting for the original one to "safely" confirm before it's safe to make a re-payment (even a non-malicious will likely contain the replacement).
bip125 already supports this use-case, but I will suggest that the logic to deploy this is sufficiently complex that no one is going to attempt any time in the near future.
But "retroactive transaction merging" is actually pretty approachable problem for a service to implement. You just get N valid transactions you've made, merge them into one. Strip extraneous inputs[1], and combine and alter the change amount.
The reason this is so appealing to implement, is there is very little complexity. If the "retroactive transaction merge" fails, or doesn't get confirmed, it actually has no impact. If it does get confirmed, that's just pure cost-savings.
However, the rules of bip125 currently make it (unnecessarily?) unappealing, because I can never lower the absolute amount of fees I pay. Hence I think it'd be pretty sweet if they could be relaxed to support this if it can be done in a pretty risk free way.
[1] Need to be very careful with that, if you're ever merging a merged transaction.

Post by Peter Todd via bitcoin-dev

Post by Gregory Maxwell via bitcoin-dev
On Tue, Jan 23, 2018 at 10:19 PM, Rhavar via bitcoin-dev

Post by Rhavar via bitcoin-dev
Interesting. I didn't think about this before, but it seems like bip125 is
rather incentive incompatible right now? If we're assuming a competitive
mempool, it really doesn't seem generally rational to accept a replacement
transaction of a lower fee rate.

BIP125 replacement requires that the fee rate increases. The text of
the BIP document is written in a confusing way that doesn't make this
clear.

In fact I considered only requiring an increase in fee rate, based on the
theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.
--

[David A. Harding via bitcoin-dev]

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
In fact I considered only requiring an increase in fee rate, based on the
theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.

Why would you need to consider the whole mempool?

Imagine a miner is only concerned with creating the next block and his
mempool currently only has 750,000 vbytes in it. If two 250-vbyte
transactions each paying a feerate of 100 nanobitcoins per vbyte (50k
total) are replaced with one 325-vbyte transaction paying a feerate of
120 nBTC (39k total), the miner's potential income from mining the next
block is reduced by 11k nBTC.

Moving away from this easily worked example, the problem can still exist
even if a miner has enough transactions to fill the next block. For
replacement consideration only by increased feerate to be guaranteed
more profitable, one has to assume the mempool contains an effectively
continuous distribution of feerates. That may one day be true of the
mempool (it would be good, because it helps keep block production
regular sans subsidy) but it's often not the case these days.

-Dave

[Rhavar via bitcoin-dev]

I don't think this is a realistic concern. The incentive compatibility _already_ exists (just in reverse: miners are refusing transactions that would increase their total fees in the next block), and as the mempool is already generally competitive enough it's actually worse the way it is.

But I don't think it makes sense to take a zealous approach on "incentive compatibility". Bitcoin is already built on a whole bunch of incentive incompatible behaviors, even things as simple as "change outputs" (you'd be better off privately giving your transaction to trusted miners without change, who deduct the min fee they would've needed and refund the rest OOB). Not to mention, we expect miners to avoid reorgs and stuff even if it's in their short-term interest.

At least personally, I think DoS risks are the real concern.

-Ryan

-------- Original Message --------

Post by David A. Harding via bitcoin-dev

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
In fact I considered only requiring an increase in fee rate, based on the
theory that if absolute fee went down, the transaction must be smaller and thus
miners could overall earn more from the additional transactions they could fit
into their block. But to do that properly requires considering whether or not
that's actually true in the particular state the mempool as a whole happens to
be in, so I ditched that idea early on for the much simpler criteria of both a
feerate and absolute fee increase.

Why would you need to consider the whole mempool?

Imagine a miner is only concerned with creating the next block and his
mempool currently only has 750,000 vbytes in it. If two 250-vbyte
transactions each paying a feerate of 100 nanobitcoins per vbyte (50k
total) are replaced with one 325-vbyte transaction paying a feerate of
120 nBTC (39k total), the miner's potential income from mining the next
block is reduced by 11k nBTC.
Moving away from this easily worked example, the problem can still exist
even if a miner has enough transactions to fill the next block. For
replacement consideration only by increased feerate to be guaranteed
more profitable, one has to assume the mempool contains an effectively
continuous distribution of feerates. That may one day be true of the
mempool (it would be good, because it helps keep block production
regular sans subsidy) but it's often not the case these days.
-Dave

[Moral Agent via bitcoin-dev]

As you point out, depending on the mempool, sometimes a miner makes more
fee by including A and B, while other times a miner makes more fee by
including C (the replacement for A and B) and D (a hypothetical transaction
that cannot be fit into a block that contains A and B but can be fit into a
block with C.

So what are we to make of this? Is it better to relay C or better to not
relay C?

Clearly it is better for the miner if they know about C, because knowing
about C costs them nothing, but not knowing about C will sometimes result
in them earning less fees.

Clearly it is better for the people who are creating C for those
transactions to be mined instead of the more expensive A and B transactions.

Everyone else is better off in that more transactions would get included in
blocks.

A concern about burdening full nodes with extra transactions to relay that
may not be more profitable to mine than the transactions they replace is
still rational -- though intuitively it seems like there would be a limit
on how many times an attacker could cheaply reorganize transactions into
something with a higher fee rate.

Perhaps there are also concerns with reconstruction of blocks from compact
blocks, given that miners would have more decisions to make about which tx
to include?



On Sun, Jan 28, 2018 at 12:29 PM, David A. Harding via bitcoin-dev <

Post by Peter Todd via bitcoin-dev

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
In fact I considered only requiring an increase in fee rate, based on

the

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
theory that if absolute fee went down, the transaction must be smaller

and thus

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
miners could overall earn more from the additional transactions they

could fit

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
into their block. But to do that properly requires considering whether

or not

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
that's actually true in the particular state the mempool as a whole

happens to

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
be in, so I ditched that idea early on for the much simpler criteria

of both a

Post by Sjors Provoost via bitcoin-dev

Post by Peter Todd via bitcoin-dev
feerate and absolute fee increase.

Why would you need to consider the whole mempool?

Imagine a miner is only concerned with creating the next block and his
mempool currently only has 750,000 vbytes in it. If two 250-vbyte
transactions each paying a feerate of 100 nanobitcoins per vbyte (50k
total) are replaced with one 325-vbyte transaction paying a feerate of
120 nBTC (39k total), the miner's potential income from mining the next
block is reduced by 11k nBTC.
Moving away from this easily worked example, the problem can still exist
even if a miner has enough transactions to fill the next block. For
replacement consideration only by increased feerate to be guaranteed
more profitable, one has to assume the mempool contains an effectively
continuous distribution of feerates. That may one day be true of the
mempool (it would be good, because it helps keep block production
regular sans subsidy) but it's often not the case these days.
-Dave
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[Gregory Maxwell via bitcoin-dev]

On Mon, Jan 22, 2018 at 8:00 PM, Peter Todd via bitcoin-dev

Post by Peter Todd via bitcoin-dev
Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

It's quite easy to get no change with a not-dumb algorithm selecting
coins if you have a decent number of outputs well under the value
you're paying.

The number of ways n choose m combines grows exponentially, and you
only need to get close enough over the right value so that you're
paying excess fees equal or less than the cost of the change (which
should include the current cost output itself as well as estimated
cost of the future signature to spend it).

Achow101 and Murch have code to implement an efficient algorithm for
finding these solutions for Bitcoin core which will hopefully get in
soon.

[Peter Todd via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
On Mon, Jan 22, 2018 at 8:00 PM, Peter Todd via bitcoin-dev

Post by Peter Todd via bitcoin-dev
Most transactions don't have change?! Under what circumstance? For most
use-cases the reverse is true: almost all all transactions have change, because
it's rare for the inputs to exactly math the requested payment.

It's quite easy to get no change with a not-dumb algorithm selecting
coins if you have a decent number of outputs well under the value
you're paying.
The number of ways n choose m combines grows exponentially, and you
only need to get close enough over the right value so that you're
paying excess fees equal or less than the cost of the change (which
should include the current cost output itself as well as estimated
cost of the future signature to spend it).
Achow101 and Murch have code to implement an efficient algorithm for
finding these solutions for Bitcoin core which will hopefully get in
soon.

Oh, Bitcoin Core doesn't already do that? I though that was what the (rather
complex) knapsack code was supposed to be doing.

In any case, you're assuming that there actually are a large number of outputs.
That's not likely to be the case in most "consumer-like" use-cases where the
number of deposits into the wallet is relatively low compared to the number of
withdrawls as coins are spent in smaller amounts; that's the pattern most of my
Bitcoin usage follows, particularly as I keep the amount of funds in my hot
wallets low.

Having said that, Rhavar's usage patterns could easily be different; I'd be
completely wrong in the case of a payment service for instance where a large
number of deposits are aggregated into a smaller number of payments; that
use-case happens to be a particularly interesting one for using tx replacement
to add outputs, so my criticism was definitely premature.

[Adam Ficsor via bitcoin-dev]

Post by Gregory Maxwell via bitcoin-dev
It's quite easy to get no change with a not-dumb algorithm selecting

coins if you have a decent number of outputs well under the value
you're paying.

I have been playing around quite a lot these lines, too and created some
content that is worth to look at:
https://github.com/nopara73/ZeroLink/#coin-selection
Also, you can try a simpler privacy oriented coin control implementation
with HiddenWallet:
https://medium.com/@nopara73/coin-control-is-must-learn-if-you-care-about-your-privacy-in-bitcoin-33b9a5f224a2