From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1YxMHD-0002TJ-03 for bitcoin-development@lists.sourceforge.net; Tue, 26 May 2015 21:20:43 +0000 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; Received: from mail-oi0-f54.google.com ([209.85.218.54]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1YxMHA-0002d0-Vo for bitcoin-development@lists.sourceforge.net; Tue, 26 May 2015 21:20:42 +0000 Received: by oiww2 with SMTP id w2so88227692oiw.0 for ; Tue, 26 May 2015 14:20:35 -0700 (PDT) MIME-Version: 1.0 X-Received: by 10.60.33.74 with SMTP id p10mr5861241oei.62.1432675235524; Tue, 26 May 2015 14:20:35 -0700 (PDT) Received: by 10.60.2.105 with HTTP; Tue, 26 May 2015 14:20:35 -0700 (PDT) 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: From: Danny Thorpe To: Peter Todd Content-Type: multipart/alternative; boundary=089e0115eef87df893051702b287 X-Spam-Score: -0.6 (/) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (danny.thorpe[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record 1.0 HTML_MESSAGE BODY: HTML included in message -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1YxMHA-0002d0-Vo Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] First-Seen-Safe Replace-by-Fee X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 26 May 2015 21:20:43 -0000 --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 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
Apologies if this has already been stated and I missed it,= but:

Can transactions in a buried block be overridden/r= eplaced by RBF? =C2=A0=C2=A0

Or is RBF strictly li= mited 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 unst= uck.
2) Use blockchain space efficiently.

without:

3) Changing the status quo with regard to zeroconf.

The current Bitcoin Core implementation has "first-seen" mempool<= br> 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 >=3D the minimum fee =C2=A0 =C2=A0required 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 >=3D 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
=C2=A0 =C2=A0outputs 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
=C2=A0 =C2=A0transaction, impossible to mine)

These additional criteria respect the existing "first-seen" behav= ior 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&qu= ot; 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-to= ols/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
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 cases where the original transaction did= n't have a change
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 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=3D452 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]@pet= ertodd.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-develo= pment@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/bitcoin-de= velopment


--089e0115eef87df893051702b287--