MIME-Version: 1.0
In-Reply-To: <6D3AACE5-D6CD-4785-8A55-F6DF0B94D927@ricmoo.com>
References: <6D3AACE5-D6CD-4785-8A55-F6DF0B94D927@ricmoo.com>
Date: Fri, 10 Jul 2015 17:28:02 +0100
Message-ID: <CAE-z3OV+-18VLbOfWzDnE5HWJ4436HGtC_qDFFVkFQTGyjGOVw@mail.gmail.com>
From: Tier Nolan <tier.nolan@gmail.com>
Cc: bitcoin-dev@lists.linuxfoundation.org
Content-Type: multipart/alternative; boundary=001a113a7d021c53a7051a87db6a
Subject: Re: [bitcoin-dev] Why not Child-Pays-For-Parent?
Precedence: list

--001a113a7d021c53a7051a87db6a
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

On Fri, Jul 10, 2015 at 5:09 PM, Richard Moore <me@ricmoo.com> wrote:

> I was also wondering, with CPFP, should the transaction fee be based on
> total transactions size, or the sum of each transaction=E2=80=99s require=
d fee? For
> example, a third transaction C whose unconfirmed utxo from transaction B
> has an unconfirmed utxo in transaction A (all of A=E2=80=99s inputs are c=
onfirmed),
> with each A, B and C being ~300bytes, should C=E2=80=99s transaction fee =
be 0.0001
> btc for the ~1kb it is about to commit to the blockchain, or 0.0003 btc f=
or
> the 3 transactions it is going to commit.
>

It should be whatever gives the highest fee.  In effect, child pays for
parent creates compound transactions.

A: 250 bytes, 0 fee
B: 300 bytes: 0.0005 fee
C: 400 bytes: 0.0001 fee

There are 3 combinations to consider

A: 0 fee for 250 bytes =3D 0 per byte
A&B: 0.0005 fee for 550 bytes =3D 0.91 uBTC per byte
A&B&C: 0.0006 fee for 950 bytes =3D 0.63uBTC per byte

This means that the A&B combination has the best fee per byte value.  A&B
should be added to the memory pool (if 0.91 uBTC per byte is above the
threshold).

Once A&B are added, then C can be reconsidered on its own.

C: 0.0001 for 400 bytes =3D 0.25 BTC per byte

If that is above the threshold, then C should be added.

In practice, it isn't possible to check every combination.  If there are N
transactions, then checking all triple combinations costs around N cubed.

A 2 pass system could get a reasonably efficient result.

B is 0.0005 fee for 300 bytes =3D 1.67 uBTC per byte and is assumed to be a
high value transaction.

The algorithm would be

Pass 1:
Process all transactions in order of BTC per byte, until block is full
    If the transaction's parents are either already in the pool or a
previous block, add the transaction.

Pass 1:
Process all non-included transactions in order of BTC per byte, until block
is full
    If the transaction's parents are either already in the pool or a
previous block, add the transaction.

    Otherwise, consider the transaction plus all non-included ancestors as
a single transaction
        If this combined transaction has a higher BTC per byte than the
lowest transaction(s),
            add the combined transaction
            drop the other transaction(s)

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

<div dir=3D"ltr"><br><div class=3D"gmail_extra"><br><div class=3D"gmail_quo=
te">On Fri, Jul 10, 2015 at 5:09 PM, Richard Moore <span dir=3D"ltr">&lt;<a=
 href=3D"mailto:me@ricmoo.com" target=3D"_blank">me@ricmoo.com</a>&gt;</spa=
n> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px =
0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div style=
=3D"word-wrap:break-word"><div>I was also wondering, with CPFP, should the =
transaction fee be based on total transactions size, or the sum of each tra=
nsaction=E2=80=99s required fee? For example, a third transaction C whose u=
nconfirmed utxo from transaction B has an unconfirmed utxo in transaction A=
 (all of A=E2=80=99s inputs are confirmed), with each A, B and C being ~300=
bytes, should C=E2=80=99s transaction fee be 0.0001 btc for the ~1kb it is =
about to commit to the blockchain, or 0.0003 btc for the 3 transactions it =
is going to commit.</div></div></blockquote><div><br></div><div>It should b=
e whatever gives the highest fee.=C2=A0 In effect, child pays for parent cr=
eates compound transactions.<br><br></div><div>A: 250 bytes, 0 fee<br></div=
><div>B: 300 bytes: 0.0005 fee<br></div><div>C: 400 bytes: 0.0001 fee<br><b=
r></div><div>There are 3 combinations to consider<br><br></div><div>A: 0 fe=
e for 250 bytes =3D 0 per byte<br></div><div>A&amp;B: 0.0005 fee for 550 by=
tes =3D 0.91 uBTC per byte<br></div><div>A&amp;B&amp;C: 0.0006 fee for 950 =
bytes =3D 0.63uBTC per byte<br></div><div><br></div><div>This means that th=
e A&amp;B combination has the best fee per byte value.=C2=A0 A&amp;B should=
 be added to the memory pool (if 0.91 uBTC per byte is above the threshold)=
.<br><br></div><div>Once A&amp;B are added, then C can be reconsidered on i=
ts own.=C2=A0 <br><br></div><div>C: 0.0001 for 400 bytes =3D 0.25 BTC per b=
yte<br><br></div><div>If that is above the threshold, then C should be adde=
d.<br><br></div><div>In practice, it isn&#39;t possible to check every comb=
ination.=C2=A0 If there are N transactions, then checking all triple combin=
ations costs around N cubed.<br><br></div><div>A 2 pass system could get a =
reasonably efficient result.<br><br></div><div>B is 0.0005 fee for 300 byte=
s =3D 1.67 uBTC per byte and is assumed to be a high value transaction.<br>=
<br></div><div>The algorithm would be<br><br></div><div></div><div>Pass 1:<=
br></div><div>Process all transactions in order of BTC per byte, until bloc=
k is full<br>=C2=A0=C2=A0=C2=A0 If the transaction&#39;s parents are either=
 already in the pool or a previous block, add the transaction.<br></div><di=
v><br><div>Pass 1:<br></div><div>Process all non-included transactions in o=
rder of BTC per byte, until block is full<br>=C2=A0=C2=A0=C2=A0 If the tran=
saction&#39;s parents are either already in the pool or a previous block, a=
dd the transaction.<br><br></div><div>=C2=A0=C2=A0=C2=A0 Otherwise, conside=
r the transaction plus all non-included ancestors as a single transaction<b=
r></div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 If this combined tr=
ansaction has a higher BTC per byte than the lowest transaction(s), <br>=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 add the com=
bined transaction<br></div><div>=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=
=C2=A0=C2=A0=C2=A0=C2=A0 drop the other transaction(s)<br></div><div><br><b=
r></div></div></div></div></div>

--001a113a7d021c53a7051a87db6a--