Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com
	designates 209.85.218.54 as permitted sender)
	client-ip=209.85.218.54; envelope-from=danny.thorpe@gmail.com;
	helo=mail-oi0-f54.google.com; 
MIME-Version: 1.0
In-Reply-To: <20150526051305.GA23502@savin.petertodd.org>
References: <20150526051305.GA23502@savin.petertodd.org>
Date: Tue, 26 May 2015 14:20:35 -0700
Message-ID: <CAJN5wHXRMfZigtgJ4JTKqRMkoQgkZ-d8sZ5rkpspqySwFEQEKg@mail.gmail.com>
From: Danny Thorpe <danny.thorpe@gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=089e0115eef87df893051702b287
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] First-Seen-Safe Replace-by-Fee
Precedence: list

--089e0115eef87df893051702b287
Content-Type: text/plain; charset=UTF-8

Apologies if this has already been stated and I missed it, but:

Can transactions in a buried block be overridden/replaced by RBF?

Or is RBF strictly limited to transactions that have not yet been
incorporated into a block?

Thanks,
-Danny

On Mon, May 25, 2015 at 10:13 PM, Peter Todd <pete@petertodd.org> wrote:

> Summary
> -------
>
> First-seen-safe replace-by-fee (FSS RBF) does the following:
>
> 1) Give users effective ways of getting "stuck" transactions unstuck.
> 2) Use blockchain space efficiently.
>
> without:
>
> 3) Changing the status quo with regard to zeroconf.
>
> The current Bitcoin Core implementation has "first-seen" mempool
> behavior. Once transaction t1 has been accepted, the transaction is
> never removed from the mempool until mined, or double-spent by a
> transaction in a block. The author's previously proposed replace-by-fee
> replaced this behavior with simply accepting the transaction paying the
> highest fee.
>
> FSS RBF is a compromise between these two behaviors. Transactions may be
> replaced by higher-fee paying transactions, provided that all outputs in
> the previous transaction are still paid by the replacement. While not as
> general as standard RBF, and with higher costs than standard RBF, this
> still allows fees on transaction to be increased after the fact with
> less cost and higher efficiency than child-pays-for-parent in many
> common situations; in some situations CPFP is unusable, leaving RBF as
> the only option.
>
>
> Semantics
> ---------
>
> For reference, standard replace-by-fee has the following criteria for
> determining whether to replace a transaction.
>
> 1) t2 pays > fees than t1
>
> 2) The delta fees pay by t2, t2.fee - t1.fee, are >= the minimum fee
>    required to relay t2. (t2.size * min_fee_per_kb)
>
> 3) t2 pays more fees/kb than t1
>
> FSS RBF adds the following additional criteria to replace-by-fee before
> allowing a transaction t1 to be replaced with t2:
>
> 1) All outputs of t1 exist in t2 and pay >= the value in t1.
>
> 2) All outputs of t1 are unspent.
>
> 3) The order of outputs in t2 is the same as in t1 with additional new
>    outputs at the end of the output list.
>
> 4) t2 only conflicts with a single transaction, t1
>
> 5) t2 does not spend any outputs of t1 (which would make it an invalid
>    transaction, impossible to mine)
>
> These additional criteria respect the existing "first-seen" behavior of
> the Bitcoin Core mempool implementation, such that once an address is
> payed some amount of BTC, all subsequent replacement transactions will
> pay an equal or greater amount. In short, FSS-RBF is "zeroconf safe" and
> has no affect on the ability of attackers to doublespend. (beyond of
> course the fact that any changes what-so-ever to mempool behavior are
> potential zeroconf doublespend vulnerabilities)
>
>
> Implementation
> --------------
>
> Pull-req for git HEAD: https://github.com/bitcoin/bitcoin/pull/6176
>
> A backport to v0.10.2 is pending.
>
> An implementation of fee bumping respecting FSS rules is available at:
>
> https://github.com/petertodd/replace-by-fee-tools/blob/master/bump-fee.py
>
>
> Usage Scenarios
> ---------------
>
> Case 1: Increasing the fee on a single tx
> -----------------------------------------
>
> We start with a 1-in-2-out P2PKH using transaction t1, 226 bytes in size
> with the minimal relay fee, 2.26uBTC. Increasing the fee while
> respecting FSS-RBF rules requires the addition of one more txin, with
> the change output value increased appropriately, resulting in
> transaction t2, size 374 bytes. If the change txout is sufficient for
> the fee increase, increasing the fee via CPFP requires a second
> 1-in-1-out transaction, 192 bytes, for a total of 418 bytes; if another
> input is required, CPFP requires a 2-in-1-out tx, 340 bytes, for a total
> of 566 bytes.
>
> Benefits: 11% to 34%+ cost savings, and RBF can increase fees even in
>           cases where the original transaction didn't have a change
>           output.
>
>
> Case 2: Paying multiple recipients in succession
> ------------------------------------------------
>
> We have a 1-in-2-out P2PKH transaction t1, 226 bytes, that pays Alice.
> We now need to pay Bob. With plain RBF we'd just add a new outptu and
> reduce the value of the change address, a 90% savings. However with FSS
> RBF, decreasing the value is not allowed, so we have to add an input.
>
> If the change of t1 is sufficient to pay Bob, a second 1-in-2-out tx can
> be created, 2*226=452 bytes in total. With FSS RBF we can replace t1
> with a 2-in-3-out tx paying both, increasing the value of the change
> output appropriately, resulting in 408 bytes transaction saving 10%
>
> Similar to the above example in the case where the change address of t1
> is insufficient to pay Bob the end result is one less transaction output
> in the wallet, defragmenting it. Spending these outputs later on would
> require two 148 byte inputs compared to one with RBF, resulting in an
> overall savings of 25%
>
>
> Case 3: Paying the same recipient multiple times
> ------------------------------------------------
>
> For example, consider the situation of an exchange, Acme Bitcoin Sales,
> that keeps the majority of coins in cold storage. Acme wants to move
> funds to cold storage at the lowest possible cost, taking advantage of
> periods of higher capacity. (inevitable due to the poisson nature of
> block creation) At the same time they would like to defragment their
> incoming outputs to keep redemption costs low, particularly since
> spending their high-security 3-of-7 P2SH multisigs is expensive. Acme
> creates a low fee transaction with a single output to cold storage,
> periodically adding new inputs as funds need to be moved to storage.
> Estimating the cost savings here is complex, and depends greatly on
> details of Acme's business, but regardless the approach works from a
> technical point of view. For instance if Acme's business is such that
> the total hotwallet size needed heavily depends on external factors like
> volatility, as hotwallet demand decreases throughout a day they can add
> inputs to the pending transaction. (simply asking customers to deposit
> funds directly to the cold storage is also a useful strategy)
>
> However this is another case where standard RBF is significantly more
> useful. For instance, as withdrawal requests come in the exchange can
> quickly replace their pending transactions sending funds to cold storage
> with transactions sending those funds to customers instead, each time
> avoiding multiple costly transactions. In particular, by reducing the
> need to access cold storage at all, the security of the cold-stored
> funds is increased.
>
>
> Wallet Compatibility
> --------------------
>
> All wallets should treat conflicting incoming transactions as equivalent
> so long as the transaction outputs owned by them do not change. In
> addition to compatibility with RBF-related practices, this prevents
> unnecessary user concern if transactions are mutated. Wallets must not
> assume TXIDs are fixed until confirmed in the blockchain; a fixed TXID
> is not guaranteed by the Bitcoin protocol.
>
> --
> 'peter'[:-1]@petertodd.org
> 00000000000000000c7ea0fcac58a9d7267fef8551b9d6a5206bf42b849618cb
>
>
> ------------------------------------------------------------------------------
> One dashboard for servers and applications across Physical-Virtual-Cloud
> Widest out-of-the-box monitoring support with 50+ applications
> Performance metrics, stats and reports that give you Actionable Insights
> Deep dive visibility with transaction tracing using APM Insight.
> http://ad.doubleclick.net/ddm/clk/290420510;117567292;y
> _______________________________________________
> Bitcoin-development mailing list
> Bitcoin-development@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
>
>

--089e0115eef87df893051702b287
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Apologies if this has already been stated and I missed it,=
 but:<div><br></div><div>Can transactions in a buried block be overridden/r=
eplaced by RBF? =C2=A0=C2=A0</div><div><br></div><div>Or is RBF strictly li=
mited to transactions that have not yet been incorporated into a block?<br>=
</div><div><br></div><div>Thanks,</div><div>-Danny</div></div><div class=3D=
"gmail_extra"><br><div class=3D"gmail_quote">On Mon, May 25, 2015 at 10:13 =
PM, Peter Todd <span dir=3D"ltr">&lt;<a href=3D"mailto:pete@petertodd.org" =
target=3D"_blank">pete@petertodd.org</a>&gt;</span> wrote:<br><blockquote c=
lass=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;=
padding-left:1ex">Summary<br>
-------<br>
<br>
First-seen-safe replace-by-fee (FSS RBF) does the following:<br>
<br>
1) Give users effective ways of getting &quot;stuck&quot; transactions unst=
uck.<br>
2) Use blockchain space efficiently.<br>
<br>
without:<br>
<br>
3) Changing the status quo with regard to zeroconf.<br>
<br>
The current Bitcoin Core implementation has &quot;first-seen&quot; mempool<=
br>
behavior. Once transaction t1 has been accepted, the transaction is<br>
never removed from the mempool until mined, or double-spent by a<br>
transaction in a block. The author&#39;s previously proposed replace-by-fee=
<br>
replaced this behavior with simply accepting the transaction paying the<br>
highest fee.<br>
<br>
FSS RBF is a compromise between these two behaviors. Transactions may be<br=
>
replaced by higher-fee paying transactions, provided that all outputs in<br=
>
the previous transaction are still paid by the replacement. While not as<br=
>
general as standard RBF, and with higher costs than standard RBF, this<br>
still allows fees on transaction to be increased after the fact with<br>
less cost and higher efficiency than child-pays-for-parent in many<br>
common situations; in some situations CPFP is unusable, leaving RBF as<br>
the only option.<br>
<br>
<br>
Semantics<br>
---------<br>
<br>
For reference, standard replace-by-fee has the following criteria for<br>
determining whether to replace a transaction.<br>
<br>
1) t2 pays &gt; fees than t1<br>
<br>
2) The delta fees pay by t2, t2.fee - t1.fee, are &gt;=3D the minimum fee<b=
r>
=C2=A0 =C2=A0required to relay t2. (t2.size * min_fee_per_kb)<br>
<br>
3) t2 pays more fees/kb than t1<br>
<br>
FSS RBF adds the following additional criteria to replace-by-fee before<br>
allowing a transaction t1 to be replaced with t2:<br>
<br>
1) All outputs of t1 exist in t2 and pay &gt;=3D the value in t1.<br>
<br>
2) All outputs of t1 are unspent.<br>
<br>
3) The order of outputs in t2 is the same as in t1 with additional new<br>
=C2=A0 =C2=A0outputs at the end of the output list.<br>
<br>
4) t2 only conflicts with a single transaction, t1<br>
<br>
5) t2 does not spend any outputs of t1 (which would make it an invalid<br>
=C2=A0 =C2=A0transaction, impossible to mine)<br>
<br>
These additional criteria respect the existing &quot;first-seen&quot; behav=
ior of<br>
the Bitcoin Core mempool implementation, such that once an address is<br>
payed some amount of BTC, all subsequent replacement transactions will<br>
pay an equal or greater amount. In short, FSS-RBF is &quot;zeroconf safe&qu=
ot; and<br>
has no affect on the ability of attackers to doublespend. (beyond of<br>
course the fact that any changes what-so-ever to mempool behavior are<br>
potential zeroconf doublespend vulnerabilities)<br>
<br>
<br>
Implementation<br>
--------------<br>
<br>
Pull-req for git HEAD: <a href=3D"https://github.com/bitcoin/bitcoin/pull/6=
176" target=3D"_blank">https://github.com/bitcoin/bitcoin/pull/6176</a><br>
<br>
A backport to v0.10.2 is pending.<br>
<br>
An implementation of fee bumping respecting FSS rules is available at:<br>
<br>
<a href=3D"https://github.com/petertodd/replace-by-fee-tools/blob/master/bu=
mp-fee.py" target=3D"_blank">https://github.com/petertodd/replace-by-fee-to=
ols/blob/master/bump-fee.py</a><br>
<br>
<br>
Usage Scenarios<br>
---------------<br>
<br>
Case 1: Increasing the fee on a single tx<br>
-----------------------------------------<br>
<br>
We start with a 1-in-2-out P2PKH using transaction t1, 226 bytes in size<br=
>
with the minimal relay fee, 2.26uBTC. Increasing the fee while<br>
respecting FSS-RBF rules requires the addition of one more txin, with<br>
the change output value increased appropriately, resulting in<br>
transaction t2, size 374 bytes. If the change txout is sufficient for<br>
the fee increase, increasing the fee via CPFP requires a second<br>
1-in-1-out transaction, 192 bytes, for a total of 418 bytes; if another<br>
input is required, CPFP requires a 2-in-1-out tx, 340 bytes, for a total<br=
>
of 566 bytes.<br>
<br>
Benefits: 11% to 34%+ cost savings, and RBF can increase fees even in<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cases where the original transaction did=
n&#39;t have a change<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 output.<br>
<br>
<br>
Case 2: Paying multiple recipients in succession<br>
------------------------------------------------<br>
<br>
We have a 1-in-2-out P2PKH transaction t1, 226 bytes, that pays Alice.<br>
We now need to pay Bob. With plain RBF we&#39;d just add a new outptu and<b=
r>
reduce the value of the change address, a 90% savings. However with FSS<br>
RBF, decreasing the value is not allowed, so we have to add an input.<br>
<br>
If the change of t1 is sufficient to pay Bob, a second 1-in-2-out tx can<br=
>
be created, 2*226=3D452 bytes in total. With FSS RBF we can replace t1<br>
with a 2-in-3-out tx paying both, increasing the value of the change<br>
output appropriately, resulting in 408 bytes transaction saving 10%<br>
<br>
Similar to the above example in the case where the change address of t1<br>
is insufficient to pay Bob the end result is one less transaction output<br=
>
in the wallet, defragmenting it. Spending these outputs later on would<br>
require two 148 byte inputs compared to one with RBF, resulting in an<br>
overall savings of 25%<br>
<br>
<br>
Case 3: Paying the same recipient multiple times<br>
------------------------------------------------<br>
<br>
For example, consider the situation of an exchange, Acme Bitcoin Sales,<br>
that keeps the majority of coins in cold storage. Acme wants to move<br>
funds to cold storage at the lowest possible cost, taking advantage of<br>
periods of higher capacity. (inevitable due to the poisson nature of<br>
block creation) At the same time they would like to defragment their<br>
incoming outputs to keep redemption costs low, particularly since<br>
spending their high-security 3-of-7 P2SH multisigs is expensive. Acme<br>
creates a low fee transaction with a single output to cold storage,<br>
periodically adding new inputs as funds need to be moved to storage.<br>
Estimating the cost savings here is complex, and depends greatly on<br>
details of Acme&#39;s business, but regardless the approach works from a<br=
>
technical point of view. For instance if Acme&#39;s business is such that<b=
r>
the total hotwallet size needed heavily depends on external factors like<br=
>
volatility, as hotwallet demand decreases throughout a day they can add<br>
inputs to the pending transaction. (simply asking customers to deposit<br>
funds directly to the cold storage is also a useful strategy)<br>
<br>
However this is another case where standard RBF is significantly more<br>
useful. For instance, as withdrawal requests come in the exchange can<br>
quickly replace their pending transactions sending funds to cold storage<br=
>
with transactions sending those funds to customers instead, each time<br>
avoiding multiple costly transactions. In particular, by reducing the<br>
need to access cold storage at all, the security of the cold-stored<br>
funds is increased.<br>
<br>
<br>
Wallet Compatibility<br>
--------------------<br>
<br>
All wallets should treat conflicting incoming transactions as equivalent<br=
>
so long as the transaction outputs owned by them do not change. In<br>
addition to compatibility with RBF-related practices, this prevents<br>
unnecessary user concern if transactions are mutated. Wallets must not<br>
assume TXIDs are fixed until confirmed in the blockchain; a fixed TXID<br>
is not guaranteed by the Bitcoin protocol.<br>
<span class=3D"HOEnZb"><font color=3D"#888888"><br>
--<br>
&#39;peter&#39;[:-1]@<a href=3D"http://petertodd.org" target=3D"_blank">pet=
ertodd.org</a><br>
00000000000000000c7ea0fcac58a9d7267fef8551b9d6a5206bf42b849618cb<br>
</font></span><br>---------------------------------------------------------=
---------------------<br>
One dashboard for servers and applications across Physical-Virtual-Cloud<br=
>
Widest out-of-the-box monitoring support with 50+ applications<br>
Performance metrics, stats and reports that give you Actionable Insights<br=
>
Deep dive visibility with transaction tracing using APM Insight.<br>
<a href=3D"http://ad.doubleclick.net/ddm/clk/290420510;117567292;y" target=
=3D"_blank">http://ad.doubleclick.net/ddm/clk/290420510;117567292;y</a><br>=
_______________________________________________<br>
Bitcoin-development mailing list<br>
<a href=3D"mailto:Bitcoin-development@lists.sourceforge.net">Bitcoin-develo=
pment@lists.sourceforge.net</a><br>
<a href=3D"https://lists.sourceforge.net/lists/listinfo/bitcoin-development=
" target=3D"_blank">https://lists.sourceforge.net/lists/listinfo/bitcoin-de=
velopment</a><br>
<br></blockquote></div><br></div>

--089e0115eef87df893051702b287--