MIME-Version: 1.0
References: <005e01d87b89$3d99df60$b8cd9e20$@voskuil.org>
In-Reply-To: <005e01d87b89$3d99df60$b8cd9e20$@voskuil.org>
From: Suhas Daftuar <sdaftuar@gmail.com>
Date: Tue, 4 Oct 2022 11:15:42 -0400
Message-ID: <CAFp6fsF=fLVq4=PSEpK+4yD+SZ+uVMJLM616q3F--zcuuqL3pg@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000c2eec105ea36ef30"
Subject: Re: [bitcoin-dev] Packaged Transaction Relay
Precedence: list

--000000000000c2eec105ea36ef30
Content-Type: text/plain; charset="UTF-8"

(Apologies for the double-post -- I'm resending this message to the list
with much of the quoted text trimmed, because my first message was placed
in the moderation queue for being too large)

Hi,

Thanks for sharing your thoughts on packaged transaction relay.

The sole objective, as expressed in the OP proposal, is to:

"Propagate transactions that are incentive-compatible to mine, even if they
> don't meet minimum feerate alone."


I actually do think there are additional goals we should include in any
protocol change involving transaction relay, such as ensuring that we
minimize bandwidth waste as much as possible (as I mentioned in a previous
message in this thread).

While I understand your proposal seeks to improve on an idea of static
packages in favor of dynamic package construction based on knowledge a node
should have of its peers, I think the main drawback of your proposal is
that it doesn't take into account the complexities of what a peer's
"minimum feerate" might mean.  The consequence of this is that it's not
generally possible for a node to accurately guess whether a given
transaction should be sent in a package to a given peer, or not, and so in
addition to any "packaged transaction relay" mechanism that is implemented
by a transaction announcer, we'd still need to add protocol support for a
receiving peer to retrieve a package as well.

First of all, a node's feerate is a dynamic value.  BIP 133 allows for
nodes to send feefilter messages at any time during the lifetime of a peer
connection.  If we were to compare the feerate of ancestors of a relayed
transaction to the feerate in place at a peer as indicated by feefilter
messages, and use that determine whether those ancestors would have been
successfully relayed or not, then doing so accurately would seem to require
caching relay success for each transaction, for each peer, at the time such
transaction is relayed (or perhaps caching feefilter values that are
received from a peer?).  This seems likely to be undesirable, and, at any
rate, is more complex than merely comparing a pair of feerates.

But even more fundamental than feerates being dynamic is that feerate
itself is not a well-defined concept when applied to arbitrary transaction
(sub-)graphs, and this is at the crux of the difficulty in coming up with
proposals that would meet the objective of ensuring that transactions which
are incentive-compatible to mine all get relayed successfully across the
network.  Here are a couple examples that illustrate this:

- Let A be a low feerate transaction (below any peer's minimum feerate).
Let B and C be descendants of A (but are otherwise unrelated).  Suppose
these transactions are relayed to a node in the order A, B, C.  In the
algorithm you proposed, I believe the determination for whether C should be
announced to a given peer as a package (A, C) or as a singleton would
either (1) depend on whether the package (A, B) was sufficient to meet the
peer's feerate, or (2) waste bandwidth by engaging in packaged relay
whenever A was already successfully relayed as part of a package.  Both of
these approaches seem undesirable.

- Let A be a high fee, but low feerate transaction.  Suppose B is a
transaction that conflicts with A, has a high feerate, but lower total
fee.  In this situation, two different nodes that learned of these two
transactions in opposite order [(A, B) vs (B, A)] might be expected to have
differing mempools -- this at least would be the case in the BIP 125
algorithm (which requires that both feerate and total fee must increase
when replacing an existing transaction), and at any rate it's not obvious
from the information given which would be more optimal to include in a
block, as that depends on factors that go beyond just these two
transactions.  Suppose further that a new transaction C is relayed on the
network, which is a child of B and very high feerate, such that B + C have
higher fee and higher feerate than A, when taken together.  In this case
we'd want our relay protocol to ensure that even nodes which saw A first
should still have a chance to consider transaction C, but the packaging
design you propose (which would compare transaction B's feerate to the
peer's, and conclude packaging is unnecessary because B's feerate might
already exceed the peer's feerate) would not facilitate this.

To summarize, the point I'd make from these examples is that we should not
expect that "feerate" (whatever that means) alone will be a sufficient
predictor of what is in our peer's mempools.  So while there may be some
situations where a transaction relayer might be able to usefully package up
a transaction with its dependencies (perhaps in narrowly defined
situations), there will also always be situations where this isn't
possible, and what I conclude from that is that it should be helpful to add
to the protocol some way for the recipient of a transaction to request the
dependencies directly.

Taken together, I roughly understand Gloria's efforts here to be a
combination of these two approaches: add some amount of packaged
transaction relay for simple cases (ie where the transaction graph has been
sufficiently narrowed, to minimize bandwidth waste while reducing latency),
and also allow for a fallback mechanism where the recipient of a
transaction can efficiently retrieve dependencies.  There seems to be a
tradeoff involving latency, bandwidth, and robustness of these two
approaches (and maybe also implementation complexity), so I think it's
natural to expect that it will take some discussion and understanding of
what practices are common on the network and what behaviors wallet or other
software might adopt, given potential protocol changes, to figure out how
best to balance these ideas.

On Wed, Jun 8, 2022 at 6:43 PM <eric@voskuil.org> wrote:

> Hi Suhas/Gloria,
>
> Good questions. I've started a new thread because it became something
> else...
>
> Various ideas about packaging seem to be focused on the idea of an atomic
> message that is gossiped around the network like a transaction or block.
> From my perspective that seems to create a set of problems without good
> solutions, and it is not a proper analogy to those atomic structures. It
> may be worth taking the time to step back and take a close look at the
> underlying objective.
>
> The sole objective, as expressed in the OP proposal, is to:
>
> "Propagate transactions that are incentive-compatible to mine, even if
> they don't meet minimum feerate alone."
>
> Effectively producing this outcome with an atomic packaging approach while
> at the same time maintaining network invariants seems unlikely, if not
> impossible.
>
> Fees:
>
> A node knows what fee rate a peer will accept, and announces individual
> txs that satisfy peer.feerate. Similarly a node knows its own feerate, and
> SHOULD drop any peer that announces txs that do not satisfy node.feerate.
>
> Orphans:
>
> A node MAY drop a peer that announces txs that the node sees as orphans
> against its DAG. It SHOULD drop the orphan tx and MAY request missing
> ancestors. Presumably after some amount of time connected to peer, node
> does not expect to see any more orphans from that peer, so these choices
> could evolve with the channel. However, the design that can only consider
> each tx in isolation will continue to cause orphan announcements on the
> channel. A below peer.feerate tx does not get announced to peer, and later
> a descendant high peer.feerate does get announced to the peer - as an
> orphan.
>
> BIP133 (feefilter):
>
> "There could be a small number of edge cases where a node's mempool min
> fee is actually less than the filter value a peer is aware of and
> transactions with fee rates between these values will now be newly
> inhibited."
>
> https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki
>
> Whether the problem is "small" or not depends on the disparity between
> node fee rates, which is not a matter of protocol. This is an existing
> problem that can and should be dealt with in packaging, as part of the
> above objective.
>
> Packaged Transaction Relay:
>
> One might instead think of packaging as a per-connection function,
> operating over its transaction (input->output) DAG and the feerate of its
> own node and that of the peer. Logically a "package" is nothing more than a
> set of transactions (optimized by announcement). Only a node can
> effectively determine the packaging required by each of its peers, since
> only the node is aware of peer.feerate.
>
> The only way to avoid dead-ending packages (including individual
> transactions, as is the objective) is for a node to package txs for each
> peer. The origination of any package is then just a wallet peer doing what
> a node does - packaging transactions that satisfy peer.feerate (i.e. that
> of its node).
>
> Current transaction relay (txB->txA):
> ===============================
> Node0
> txA.feerate > node.feerate, and not orphaned (accept txA)
> txA.feerate > peer1.feerate (announce txA to peer1)
> txA.feerate < peer2.feerate (do not announce txA to peer2)
> -----
> txB.feerate > node.feerate (accept txB)
> txB.feerate > peer1.feerate (announce txB to peer1)
> txB.feerate > peer2.feerate (announce txB to peer2)
>
> Node1
> Sees/accepts txA and txB.
>
> Node2
> Never sees txA, sees/rejects txB (as an orphan).
>
> Packaged transaction relay (txB->txA):
> ===============================
> Node0
> txA.feerate > node.feerate, and not orphaned (accept txA)
> txA.feerate > peer1.feerate (announce txA to peer1)
> txA.feerate < peer2.feerate (do not announce txA to peer2)
> -----
> txB.feerate > node1.feerate (accept txB)
> txB.feerate > peer1.feerate (announce txB to peer1)
> txB.feerate > peer2.feerate (do not announce txB to peer2) <== avoid
> predictable orphan
> txA.feerate + txB.feerate > peer2.feerate (announce pkg(A, B) to peer2) <=
> create minimal package
>
> Node1
> Sees/accepts txA and txB.
>
> Node2
> pkg(A, B) > node2.feerate (accept txA, txB)
> txA.feerate > peer3.feerate (announce txA to peer3)
> txB.feerate > peer3.feerate (announce txB to peer3)
>
> Sees/accepts pkg(A, B).
>
> Node3
> Sees/accepts txA and txB. <= avoided unnecessary packaging
>
> Summary:
>
> In this design, any node that receives an announcement for a pkg (or tx)
> later determined to be less than node.feerate SHOULD drop the announcing
> peer. Unlike with existing tx relay, a node can become "current" and
> subsequently see few if any tx or pkg orphans, and MAY at some point decide
> to drop any peer that announces one. Notice that packages are created
> dynamically, and any package that doesn't need to be grouped gets trimmed
> down to individual transactions. Furthermore any tx that is "stuck" can be
> freed by simply sending another tx. The nodes at which the tx has become
> stuck will just package it up and relay it to peers. In other words, there
> is no impact on wallet implementation apart from raising the aggregate fee
> using a descendant transaction.
>
> This is barely a protocol change - it's primarily implementation. All that
> should be required is an additional INV element type, such as
> MSG_TX_PACKAGE.
>
> Additional constraints:
>
> * All elements of MSG_TX_PACKAGE in one INV message MUST to be of the same
> package.
> * A package MUST must define a set that can be mined into one block
> (size/sigops constraint).
> * A package SHOULD not contain confirmed txs (a race may cause this).
> * A package MUST minimally satisfy peer.feerate.
> * A partial tx order, as in the manner of the block.txs ordering, MUST be
> imposed.
> * A node SHOULD drop a peer that sends a package (or tx) below
> node.feerate.
> * A node MAY drop a peer that sends a non-minimal package according to
> node.feerate.
>
> The partial ordering of block.txs introduces an ordering constraint that
> precludes full parallelism in validating input attachment. This is an
> implementation artifact that made its way into consensus. However in the
> case of packaging, the set of txs is not presumed to be valid under the
> proof of work DoS guard. As such constraints should minimize the
> work/traffic required to invalidate the message. The partial order
> constraint ensures that the DAG can be built incrementally, dropping the
> attempt (and peer as desired) as soon as the first orphan is discovered. As
> a result the network traffic and work required is not materially different
> than with tx relay, with two exceptions.
>
> These are the two central aspects of this approach (Avoiding Predictable
> Orphans and Creating Minimal Packages). These are graph search algorithms,
> some basic computer science. Minimality requires only that the package does
> not introduce txs that are not necessary to reach the peer.feerate (as
> these can always be packaged separately). It does not require that nodes
> all generate the same packages. It does not require negotiation, package
> identity, cryptography, or hashing. As a graph search it should be O(n)
> where n is the unconfirmed ancestry of the package, but should typically be
> much lower, if not a single step.
>
> Sufficiently-low-fee nodes will see only single txs. Moderate-fee nodes
> may cause partial breakup of packages. Sufficiently high fee nodes will
> cause peers (having received and completed the acceptance of a tx/pkg with
> pkg.feerate < peer.feerate) to navigate from each tx/package external input
> until reaching txs above peer.feerate, or confirmed (both of which the peer
> is presumed to already have). If the pkg.feerate is sufficiently high to
> connect all external inputs to the intervening txs, they are added to the
> package and it is announced to the high fee peer. Note that the individual
> tx.feerate > peer.feerate is insufficient to ensure that the peer should
> have the tx, as there may be ancestor txs that do not, and for which the tx
> was insufficient to cause them to be packaged. So a non-caching algorithm
> must be able to chase each package external input to a confirmed tx (or
> cache the unconfirmed ancestry fee rate at each tx). Note that fee rates
> are not directly additive, both size/weight and fee are required for
> summation (and aggregate sigops should be considered).
>
> This makes no assumptions about current implementations. The design would
> call for maintenance of a transaction (input->output) DAG with tx.feerate
> on each tx. This could be the unconfirmed tx graph (i.e. "memory pool")
> though it does not require maintenance of anything more than the parameters
> necessary to confirm a set of validated txs within a block. It is very
> reasonable to require this of any participating node. A simple version
> negotiation can identify a package-accepting/sending nodes.
>
> I have thought about this for some time, but have not implemented either
> the graph search, source code, or BIP. Just wrote this off the top of my
> head. So I am sure there are some things I have incorrect or failed to
> consider. But I think it's worth discussing it at this point.
>
> e
>
>
>

--000000000000c2eec105ea36ef30
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div dir=3D"ltr">(Apologies for the double-post -- I&#39;m=
 resending this message to the list with much of the quoted text trimmed, b=
ecause my first message was placed in the moderation queue for being too la=
rge)<div><br></div><div><div dir=3D"ltr" style=3D"color:rgb(0,0,0)">Hi,<div=
><br></div><div>Thanks for sharing=C2=A0your thoughts on packaged transacti=
on relay.</div><span class=3D"gmail-im" style=3D"color:rgb(80,0,80)"><div><=
br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style=3D"c=
olor:rgb(0,0,0)">The sole objective, as expressed in the OP proposal, is to=
:</span></blockquote></span><div><span class=3D"gmail-im" style=3D"color:rg=
b(80,0,80)"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0=
.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span style=
=3D"color:rgb(0,0,0)">&quot;Propagate transactions that are incentive-compa=
tible to mine, even if they don&#39;t meet minimum feerate alone.&quot;</sp=
an></blockquote><div>=C2=A0</div></span><div>I actually do think there are =
additional goals we should include in any protocol change involving transac=
tion relay, such as ensuring that we minimize bandwidth waste as much as po=
ssible (as I mentioned in a previous message in this thread).</div><div><br=
></div><div>While I understand your proposal seeks to improve on an idea of=
 static packages in favor of dynamic package construction based on knowledg=
e a node should have of its peers, I think the main drawback=C2=A0of your p=
roposal is that it doesn&#39;t take into account the complexities of what a=
 peer&#39;s &quot;minimum feerate&quot; might mean.=C2=A0 The consequence o=
f this is that it&#39;s not generally possible for a node to accurately gue=
ss whether a given transaction should be sent in a package to a given peer,=
 or not, and so in addition to any &quot;packaged transaction relay&quot; m=
echanism that is implemented by a transaction announcer, we&#39;d still nee=
d to add protocol support for a receiving peer to retrieve a package as wel=
l.</div><div><br></div><div>First of all, a node&#39;s feerate=C2=A0is a dy=
namic value.=C2=A0 BIP 133 allows for nodes to send feefilter messages at a=
ny time during the lifetime of a peer connection.=C2=A0 If we were to compa=
re the feerate of ancestors of a relayed transaction to the feerate in plac=
e at a peer as indicated by feefilter messages, and use that determine whet=
her those ancestors would have been successfully relayed or not, then doing=
 so accurately would seem to require caching relay success for each transac=
tion, for each peer, at the time such transaction is relayed (or perhaps ca=
ching feefilter values that are received from a peer?).=C2=A0 This seems li=
kely to be undesirable, and, at any rate, is more complex than merely compa=
ring a pair of feerates.</div><div><br></div><div>But even more fundamental=
 than feerates being dynamic is that feerate itself is not a well-defined c=
oncept when applied to arbitrary transaction (sub-)graphs, and this is at t=
he crux of the difficulty in coming up with proposals that would meet the o=
bjective of ensuring that transactions which are incentive-compatible to mi=
ne all get relayed successfully across the network.=C2=A0 Here are a couple=
 examples that illustrate this:</div><div><br></div><div>- Let A be a low f=
eerate transaction (below any peer&#39;s minimum feerate).=C2=A0 Let B and =
C be descendants of A (but are otherwise unrelated).=C2=A0 Suppose these tr=
ansactions are relayed to a node in the order A, B, C.=C2=A0 In the algorit=
hm you proposed, I believe the determination for whether C should be announ=
ced to a given peer as a package (A, C) or as a singleton would either (1) =
depend on whether the package (A, B) was sufficient to meet the peer&#39;s =
feerate, or (2) waste bandwidth by engaging in packaged relay whenever A wa=
s already successfully relayed as part of a package.=C2=A0 Both of these ap=
proaches seem undesirable.</div><div><br></div><div>- Let A be a high fee, =
but low feerate transaction.=C2=A0 Suppose B is a transaction that conflict=
s with A, has a high feerate, but lower total fee.=C2=A0 In this situation,=
 two different nodes that learned of these two transactions in opposite ord=
er [(A, B) vs (B, A)] might be expected to have differing mempools -- this =
at least would be the case in the BIP 125 algorithm (which requires that bo=
th=C2=A0feerate and total fee must increase when replacing an existing tran=
saction), and at any rate it&#39;s not obvious from the information given w=
hich would be more optimal to include in a block, as that depends on factor=
s that go beyond just these two transactions.=C2=A0 Suppose further that a =
new transaction C is relayed on the network, which is a child of B and very=
 high feerate, such that B=C2=A0+ C have higher fee and higher feerate than=
 A, when taken together.=C2=A0 In this case we&#39;d want our relay protoco=
l to ensure that even nodes which saw A first should still have a chance to=
 consider transaction C, but the packaging design you propose (which would =
compare transaction B&#39;s feerate to the peer&#39;s, and conclude packagi=
ng is unnecessary because B&#39;s feerate might already exceed the peer&#39=
;s feerate) would not facilitate this.<br></div><div><br></div><div>To summ=
arize, the point I&#39;d make from these examples is that we should not exp=
ect that &quot;feerate&quot; (whatever that means) alone will be a sufficie=
nt predictor of what is in our peer&#39;s mempools.=C2=A0 So while there ma=
y be some situations where a transaction relayer might be able to usefully =
package up a transaction with its dependencies (perhaps in narrowly defined=
 situations), there will also always be situations where this isn&#39;t pos=
sible, and what I conclude from that is that it should be helpful to add to=
 the protocol some way for the recipient of a transaction to request the de=
pendencies directly.</div><div><br></div></div><div>Taken together, I rough=
ly understand Gloria&#39;s efforts here to be a combination of these two ap=
proaches: add some amount of packaged transaction relay for simple cases (i=
e where the transaction graph has been sufficiently narrowed, to minimize b=
andwidth waste while reducing latency), and also allow for a fallback mecha=
nism where the recipient of a transaction can efficiently retrieve dependen=
cies.=C2=A0 There seems to be a tradeoff involving latency, bandwidth, and =
robustness of these two approaches (and maybe also implementation complexit=
y), so I think it&#39;s natural to expect that it will take some discussion=
 and understanding of what practices are common on the network and what beh=
aviors wallet or other software might adopt, given potential protocol chang=
es, to figure out how best to balance these ideas.</div></div><div class=3D=
"gmail-yj6qo gmail-ajU" style=3D"outline:none;padding:10px 0px;width:22px;m=
argin:2px 0px 0px;color:rgb(0,0,0)"><br></div></div></div><div class=3D"gma=
il_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Wed, Jun 8, 2022 at 6:43=
 PM &lt;<a href=3D"mailto:eric@voskuil.org">eric@voskuil.org</a>&gt; wrote:=
<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8=
ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Suhas/Gloria=
,<br>
<br>
Good questions. I&#39;ve started a new thread because it became something e=
lse...<br>
<br>
Various ideas about packaging seem to be focused on the idea of an atomic m=
essage that is gossiped around the network like a transaction or block. Fro=
m my perspective that seems to create a set of problems without good soluti=
ons, and it is not a proper analogy to those atomic structures. It may be w=
orth taking the time to step back and take a close look at the underlying o=
bjective.<br>
<br>
The sole objective, as expressed in the OP proposal, is to:<br>
<br>
&quot;Propagate transactions that are incentive-compatible to mine, even if=
 they don&#39;t meet minimum feerate alone.&quot;<br>
<br>
Effectively producing this outcome with an atomic packaging approach while =
at the same time maintaining network invariants seems unlikely, if not impo=
ssible.<br>
<br>
Fees:<br>
<br>
A node knows what fee rate a peer will accept, and announces individual txs=
 that satisfy peer.feerate. Similarly a node knows its own feerate, and SHO=
ULD drop any peer that announces txs that do not satisfy node.feerate.<br>
<br>
Orphans:<br>
<br>
A node MAY drop a peer that announces txs that the node sees as orphans aga=
inst its DAG. It SHOULD drop the orphan tx and MAY request missing ancestor=
s. Presumably after some amount of time connected to peer, node does not ex=
pect to see any more orphans from that peer, so these choices could evolve =
with the channel. However, the design that can only consider each tx in iso=
lation will continue to cause orphan announcements on the channel. A below =
peer.feerate tx does not get announced to peer, and later a descendant high=
 peer.feerate does get announced to the peer - as an orphan.<br>
<br>
BIP133 (feefilter):<br>
<br>
&quot;There could be a small number of edge cases where a node&#39;s mempoo=
l min fee is actually less than the filter value a peer is aware of and tra=
nsactions with fee rates between these values will now be newly inhibited.&=
quot;<br>
<br>
<a href=3D"https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki" =
rel=3D"noreferrer" target=3D"_blank">https://github.com/bitcoin/bips/blob/m=
aster/bip-0133.mediawiki</a><br>
<br>
Whether the problem is &quot;small&quot; or not depends on the disparity be=
tween node fee rates, which is not a matter of protocol. This is an existin=
g problem that can and should be dealt with in packaging, as part of the ab=
ove objective. <br>
<br>
Packaged Transaction Relay:<br>
<br>
One might instead think of packaging as a per-connection function, operatin=
g over its transaction (input-&gt;output) DAG and the feerate of its own no=
de and that of the peer. Logically a &quot;package&quot; is nothing more th=
an a set of transactions (optimized by announcement). Only a node can effec=
tively determine the packaging required by each of its peers, since only th=
e node is aware of peer.feerate.<br>
<br>
The only way to avoid dead-ending packages (including individual transactio=
ns, as is the objective) is for a node to package txs for each peer. The or=
igination of any package is then just a wallet peer doing what a node does =
- packaging transactions that satisfy peer.feerate (i.e. that of its node).=
<br>
<br>
Current transaction relay (txB-&gt;txA):<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D<br>
Node0<br>
txA.feerate &gt; node.feerate, and not orphaned (accept txA)<br>
txA.feerate &gt; peer1.feerate (announce txA to peer1)<br>
txA.feerate &lt; peer2.feerate (do not announce txA to peer2)<br>
-----<br>
txB.feerate &gt; node.feerate (accept txB)<br>
txB.feerate &gt; peer1.feerate (announce txB to peer1)<br>
txB.feerate &gt; peer2.feerate (announce txB to peer2)<br>
<br>
Node1<br>
Sees/accepts txA and txB.<br>
<br>
Node2<br>
Never sees txA, sees/rejects txB (as an orphan).<br>
<br>
Packaged transaction relay (txB-&gt;txA):<br>
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D<br>
Node0<br>
txA.feerate &gt; node.feerate, and not orphaned (accept txA)<br>
txA.feerate &gt; peer1.feerate (announce txA to peer1)<br>
txA.feerate &lt; peer2.feerate (do not announce txA to peer2)<br>
-----<br>
txB.feerate &gt; node1.feerate (accept txB)<br>
txB.feerate &gt; peer1.feerate (announce txB to peer1)<br>
txB.feerate &gt; peer2.feerate (do not announce txB to peer2) &lt;=3D=3D av=
oid predictable orphan<br>
txA.feerate + txB.feerate &gt; peer2.feerate (announce pkg(A, B) to peer2) =
&lt;=3D create minimal package<br>
<br>
Node1<br>
Sees/accepts txA and txB.<br>
<br>
Node2<br>
pkg(A, B) &gt; node2.feerate (accept txA, txB)<br>
txA.feerate &gt; peer3.feerate (announce txA to peer3)<br>
txB.feerate &gt; peer3.feerate (announce txB to peer3)<br>
<br>
Sees/accepts pkg(A, B).<br>
<br>
Node3<br>
Sees/accepts txA and txB. &lt;=3D avoided unnecessary packaging<br>
<br>
Summary:<br>
<br>
In this design, any node that receives an announcement for a pkg (or tx) la=
ter determined to be less than node.feerate SHOULD drop the announcing peer=
. Unlike with existing tx relay, a node can become &quot;current&quot; and =
subsequently see few if any tx or pkg orphans, and MAY at some point decide=
 to drop any peer that announces one. Notice that packages are created dyna=
mically, and any package that doesn&#39;t need to be grouped gets trimmed d=
own to individual transactions. Furthermore any tx that is &quot;stuck&quot=
; can be freed by simply sending another tx. The nodes at which the tx has =
become stuck will just package it up and relay it to peers. In other words,=
 there is no impact on wallet implementation apart from raising the aggrega=
te fee using a descendant transaction.<br>
<br>
This is barely a protocol change - it&#39;s primarily implementation. All t=
hat should be required is an additional INV element type, such as MSG_TX_PA=
CKAGE.<br>
<br>
Additional constraints:<br>
<br>
* All elements of MSG_TX_PACKAGE in one INV message MUST to be of the same =
package.<br>
* A package MUST must define a set that can be mined into one block (size/s=
igops constraint).<br>
* A package SHOULD not contain confirmed txs (a race may cause this).<br>
* A package MUST minimally satisfy peer.feerate.<br>
* A partial tx order, as in the manner of the block.txs ordering, MUST be i=
mposed.<br>
* A node SHOULD drop a peer that sends a package (or tx) below node.feerate=
.<br>
* A node MAY drop a peer that sends a non-minimal package according to node=
.feerate.<br>
<br>
The partial ordering of block.txs introduces an ordering constraint that pr=
ecludes full parallelism in validating input attachment. This is an impleme=
ntation artifact that made its way into consensus. However in the case of p=
ackaging, the set of txs is not presumed to be valid under the proof of wor=
k DoS guard. As such constraints should minimize the work/traffic required =
to invalidate the message. The partial order constraint ensures that the DA=
G can be built incrementally, dropping the attempt (and peer as desired) as=
 soon as the first orphan is discovered. As a result the network traffic an=
d work required is not materially different than with tx relay, with two ex=
ceptions.<br>
<br>
These are the two central aspects of this approach (Avoiding Predictable Or=
phans and Creating Minimal Packages). These are graph search algorithms, so=
me basic computer science. Minimality requires only that the package does n=
ot introduce txs that are not necessary to reach the peer.feerate (as these=
 can always be packaged separately). It does not require that nodes all gen=
erate the same packages. It does not require negotiation, package identity,=
 cryptography, or hashing. As a graph search it should be O(n) where n is t=
he unconfirmed ancestry of the package, but should typically be much lower,=
 if not a single step.<br>
<br>
Sufficiently-low-fee nodes will see only single txs. Moderate-fee nodes may=
 cause partial breakup of packages. Sufficiently high fee nodes will cause =
peers (having received and completed the acceptance of a tx/pkg with pkg.fe=
erate &lt; peer.feerate) to navigate from each tx/package external input un=
til reaching txs above peer.feerate, or confirmed (both of which the peer i=
s presumed to already have). If the pkg.feerate is sufficiently high to con=
nect all external inputs to the intervening txs, they are added to the pack=
age and it is announced to the high fee peer. Note that the individual tx.f=
eerate &gt; peer.feerate is insufficient to ensure that the peer should hav=
e the tx, as there may be ancestor txs that do not, and for which the tx wa=
s insufficient to cause them to be packaged. So a non-caching algorithm mus=
t be able to chase each package external input to a confirmed tx (or cache =
the unconfirmed ancestry fee rate at each tx). Note that fee rates are not =
directly additive, both size/weight and fee are required for summation (and=
 aggregate sigops should be considered).<br>
<br>
This makes no assumptions about current implementations. The design would c=
all for maintenance of a transaction (input-&gt;output) DAG with tx.feerate=
 on each tx. This could be the unconfirmed tx graph (i.e. &quot;memory pool=
&quot;) though it does not require maintenance of anything more than the pa=
rameters necessary to confirm a set of validated txs within a block. It is =
very reasonable to require this of any participating node. A simple version=
 negotiation can identify a package-accepting/sending nodes.<br>
<br>
I have thought about this for some time, but have not implemented either th=
e graph search, source code, or BIP. Just wrote this off the top of my head=
. So I am sure there are some things I have incorrect or failed to consider=
. But I think it&#39;s worth discussing it at this point.<br>
<br>
e<br>
<br><br>
</blockquote></div></div>

--000000000000c2eec105ea36ef30--