Date: Tue, 27 Sep 2022 09:29:19 +0000
To: eric@voskuil.org
From: alicexbt <alicexbt@protonmail.com>
Message-ID: <9H5VUe-D8MlzIgitIRj0Z_yT_dj5RYwAcp4HJHdXcseZB3Hl1Wxl1_vpcmPYCMaolnYA6R18MC3qIsQgkxBeew3s5GLirhAMaNiEq5LOm4U=@protonmail.com>
In-Reply-To: <00cb01d8d1ed$b0191dc0$104b5940$@voskuil.org>
References: <005e01d87b89$3d99df60$b8cd9e20$@voskuil.org>
 <EDCbz3IJLDkExNWyM1WLLSh5qUioK6HdMEh-eofWmete0baz1lo8uF1YFzLaTXxgQhzvtDtqpX2mTMaDpB7_4-SRNnpJX4F8zgL5e6NGS0U=@protonmail.com>
 <00cb01d8d1ed$b0191dc0$104b5940$@voskuil.org>
Feedback-ID: 40602938:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: 'Bitcoin Protocol Discussion' <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Packaged Transaction Relay
Precedence: list

Hi Eric,


> If by "range" you mean a connected tx subgraph, I don't see why not. But =
note that nodes only operate over signed txs. PSBT is a wallet workflow.

Matt Corallo mentioned that pre-signed transactions created with low fee ra=
te become an issue when they are broadcasted after a long time and there is=
 a high demand for block space at that moment.

Example:=20

Bob created PSBT1 in a multi party contract with fee rate 5 sat/vbyte howev=
er its taking hours/days to confirm the transaction with such low fee rate.

Carol created PSBT1 (5 sat/vbyte), PSBT2 (10 sat/vbyte) and PSBT3 (20 sat/v=
byte) for spending same inputs. She broadcasted PSBT3 which got confirmed i=
n a few minutes.=20


> Always. Only signed transactions are accepted. But assuming you are refer=
ring to a transaction that has been produced by a pre-signing workflow, I'm=
 not sure how this would be distinct from any other tx.


`minfeefilter` for all peers of my node was 0.00001000 at the time of writi=
ng this email. I am assuming nobody creates pre-signed transaction with fee=
 rate below 1 sat/vbyte. How often does it happen that `minfeefilter` is ab=
ove this default value?


> I'm not sure I follow this, maybe you could reword it. But it seems that =
you are saying that CPFP fee-bumping is a problem scenario and the complexi=
ty of the proposed solutions are not justified by such scenarios.


Sorry that sentence was confusing. Yes complexity isn't justified for CPFP =
fee-bumping txs below minimum fee rate.


> There are many node implementations used presently. And of course these a=
re protocol proposals, which presumes more than one implementation.


Yes, a few implementations exist (knots, libbitcoin, btcd, bcoin etc.) howe=
ver they aren't used by lot of nodes. Based on this [chart][1] 98% nodes us=
e bitcoin core. Lot of bitcoin protocol proposals are influenced by bitcoin=
 core contributors and things could be different if even 30% nodes used oth=
er implementations.


> I don't consider this relevant to any protocol considerations. Miners sho=
uld always be expected to select the most optimal set of txs available in t=
he time available to do so.


Agree, miners should be expected to select most optimal set of txs. However=
, according to one [comment][2] by Pieter Wuille, miners could affect the s=
ecurity of some bitcoin projects with MEV.


> Over time we are likely to see that the only policies that remain in wide=
spread application are those that are necessary for DOS protection (fee rat=
e), as other restrictions are not economically rational and cannot be enfor=
ced. We've seen recent debate regarding dust policy, and op_return policy. =
"non-standard" txs are perfectly valid but get stuck very easily. I'll reit=
erate, any policy beyond what is published via the protocol will cause the =
above problems.

I completely agree with this.


[1]: https://luke.dashjr.org/programs/bitcoin/files/charts/software.html
[2]: https://bitcoin.stackexchange.com/questions/107787/front-running-in-bi=
tcoin#comment123441_107796


/dev/fd0

Sent with Proton Mail secure email.

------- Original Message -------
On Tuesday, September 27th, 2022 at 2:49 AM, <eric@voskuil.org> wrote:


> > Hi Eric,
> >=20
> > This email wasn't answered by anyone on mailing list however I did some
> > research about packages yesterday including this email and below are my
> > observations, questions etc.
>=20
>=20
> Hello, thanks for the reply.
>=20
> > > The sole objective, as expressed in the OP proposal, is to:
> > >=20
> > > "Propagate transactions that are incentive-compatible to mine, even i=
f they
> > > don't meet minimum feerate alone."
> >=20
> > According to bitcoinops: Without package relay, it=E2=80=99s not possib=
le to
> > effectively CPFP fee bump a transaction that=E2=80=99s below the minimu=
m feerate
> > nodes accept.
>=20
>=20
> Yes, the problem statement is not in question, just the mechanism of reso=
lution. The problem of stuck txs arises from minimum fee rate policy, which=
 is a necessary DOS guard.
>=20
> A secondary issue is that of orphan relay. As a node must allow receipt o=
f orphans, it has no means to differentiate a flood of unconfirmable txs fr=
om those that are confirmable.
>=20
> > Matt Corallo's thoughts in a bitcoin core issue:
> >=20
> > "Matt Corallo recently wrote about an example on the bitcoin-dev mailin=
g list
> > involving lightning transactions, where pre-signed transactions might b=
e
> > broadcast to the blockchain long after they were generated, and thus no=
t
> > have been created with a fee that is sufficient to be confirmed quickly=
 (or
> > even be accepted to node mempools). In such situations, channel
> > participants may need to use chained transactions (CPFP) in order to in=
crease
> > the confirmation speed of such transactions, and that implies we may ne=
ed
> > to introduce a mechanism for those parent transactions to be relayed al=
ong
> > with their higher feerate children, even if the parent transaction woul=
d be
> > rejected by itself."
>=20
>=20
> While this is a valid scenario, the problems directly affect Bitcoin. Tho=
se problems propagate to layers, but are not unique to layering.
>=20
> > 1)Is it possible to have multiple pre-signed transactions with differen=
t fee
> > rates in a range? Example: PSBT1: 5 sat/vbyte, PSBT2: 10 sat/vbyte, PSB=
T3: 20
> > sat/vbyte and PSBT4: 100 sat/vbyte
>=20
>=20
> If by "range" you mean a connected tx subgraph, I don't see why not. But =
note that nodes only operate over signed txs. PSBT is a wallet workflow.
>=20
> > 2)How would covenants affect this problem?
>=20
>=20
> There are a good number of covenant proposals, though I assume they are a=
ll implemented within script. If a tx is confirmable and satisfies fee rate=
 (for DOS protection), it is relayable. Covenants affect confirmability and=
 should not have any unique impact on relay.
>=20
> > 3)How often does it happen that a pre-signed tx gets rejected by nodes
> > because it did not meet the minimum fee rate? Is it predictable and cou=
ld be
> > managed in a different way?
>=20
>=20
> Always. Only signed transactions are accepted. But assuming you are refer=
ring to a transaction that has been produced by a pre-signing workflow, I'm=
 not sure how this would be distinct from any other tx.
>=20
> > After reading several links related to packages and bitcoin core pull r=
equests,
> > I found it anti-bitcoin to introduce so much complexity because its not
> > possible to CPFP fee bump a tx below minimum fee rate.
>=20
>=20
> I'm not sure I follow this, maybe you could reword it. But it seems that =
you are saying that CPFP fee-bumping is a problem scenario and the complexi=
ty of the proposed solutions are not justified by such scenarios.
>=20
> I would say that the problem is real, and that the least complex option i=
s generally preferred. There are always tradeoffs, and balancing these is p=
art of protocol development. But as a rule, complexity within a protocol (c=
ommunication) is to be avoided where possible.
>=20
> > > Furthermore any tx that is "stuck" can be freed by simply sending ano=
ther
> > > tx. The nodes at which the tx has become stuck will just package it u=
p and
> > > relay it to peers. In other words, there is no impact on wallet imple=
mentation
> > > apart from raising the aggregate fee using a descendant transaction.
> >=20
> > It is easy to send another tx if there is only one user involved howeve=
r
> > packages are trying to fix issues in which multiple users and transacti=
on pre-
> > signed between them are involved. So, it will be difficult to coordinat=
e and
> > create new pre-signed transactions in some cases although it is possibl=
e for
> > some use cases.
>=20
>=20
> Given that nodes do not deal in presigned txs, this coordination difficul=
ty could not be increased in any scenario.
>=20
> A node produces sets of txs ("packages") dynamically to satisfy its peer'=
s feerate. When a wallet broadcasts a tx/package to a node, it is operating=
 as a peer on the p2p network. The wallet simply implements the same dynami=
c packaging algorithm as any peer - because it is a peer.
>=20
> > > 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.
> >=20
> > > * 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, MUS=
T 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 t=
o
> > > node.feerate.
> >=20
> > This makes sense particularly if multiple node implementations are used=
 in
> > future.
>=20
>=20
> There are many node implementations used presently. And of course these a=
re protocol proposals, which presumes more than one implementation.
>=20
> > My other questions:
> >=20
> > a)If a package has tx1, tx2, tx3, tx4 and tx5 and miner just include tx=
1 and tx2
> > in the block, how does this affect the projects considered for packages
> > proposal?
>=20
>=20
> I will leave that to authors of such proposals to answer. However in what=
 I have proposed it just means tx3/4/5 get considered for subsequent block =
inclusion to the extent that fee rate policy is satisfied.
>=20
> One of the several problems with static construction of packages is that =
they can still get stuck by fee rate policy. This is just kicking the can d=
own the road while complicating the protocol.
>=20
> > b)How does changing the order of txs in a package affect these transact=
ions?
>=20
>=20
> There is no impact. I proposed the partial ordering to facilitate fail fa=
st.
>=20
> The partial ordering in block txs is unnecessary (given the PoW DOS guard=
). This is a consequence of the order imposed by Satoshi's implementation a=
nd only serves to slow validation (order constrains concurrency).
>=20
> > c)Do packages introduce more attack vectors in bitcoin for front runnin=
g or
> > MEV? MEV in bitcoin currently only affects the projects that are consid=
ered
> > in packages proposal.
>=20
>=20
> I don't consider this relevant to any protocol considerations. Miners sho=
uld always be expected to select the most optimal set of txs available in t=
he time available to do so.
>=20
> > d)What if the package contains a transactions with sanctioned address?
>=20
>=20
> One can consider this a policy, much like fee rate. Any policy that is ap=
plied to transactions and not known to its peers will result in the node re=
ceiving orphans. As such the node either must allow orphans or drop peers s=
ending orphans under the assumption that the peer is expected to have imple=
mented the same policy.
>=20
> > e)Why would miners use packages if the existing scenario in terms of fe=
es
> > per block is beneficial for them?
>=20
>=20
> The presumption is that the miner is only ever seeing txs that satisfy it=
s fee rate policy, so this is just more opportunity.
>=20
> I'd add that the problem of "pinning" is related, but exacerbated by opaq=
ue policy (internal to certain implementations). Any node that ejects txs f=
rom its pool of valid but unconfirmed txs that satisfy fee rate policy is g=
oing to see orphans and going to cause txs to get stuck. This is one of the=
 many problems with placing an arbitrary bound on the size of this pool.
>=20
> A subset of this problem is RBF policy. It is nice to see some movement t=
oward generalizing RBF. The term is really a misnomer. Conflicting txs and =
subgraphs of txs are only problematic in the case of DOS, which is also res=
olved through advertised fee policy. Any node that imposes policy beyond th=
is will also see orphans and cause txs to get stuck.
>=20
> The scenario and therefore complexity consequences of an implementation-s=
pecific memory-constrained tx pool are becoming increasingly apparent. Thes=
e are implementation issues, not protocol issues. This can be observed in a=
 recent thread: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/202=
2-September/020937.html
>=20
> Over time we are likely to see that the only policies that remain in wide=
spread application are those that are necessary for DOS protection (fee rat=
e), as other restrictions are not economically rational and cannot be enfor=
ced. We've seen recent debate regarding dust policy, and op_return policy. =
"non-standard" txs are perfectly valid but get stuck very easily. I'll reit=
erate, any policy beyond what is published via the protocol will cause the =
above problems.
>=20
> e
>=20
> > /dev/fd0
> >=20
> > Sent with Proton Mail secure email.
> >=20
> > ------- Original Message -------
> > On Thursday, June 9th, 2022 at 4:13 AM, Eric Voskuil via bitcoin-dev <b=
itcoin-
> > dev@lists.linuxfoundation.org> wrote:
> >=20
> > > Hi Suhas/Gloria,
> > >=20
> > > Good questions. I've started a new thread because it became something
> > > else...
> > >=20
> > > Various ideas about packaging seem to be focused on the idea of an at=
omic
> > > message that is gossiped around the network like a transaction or blo=
ck.
> > > From my perspective that seems to create a set of problems without go=
od
> > > 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 under=
lying
> > > objective.
> > >=20
> > > The sole objective, as expressed in the OP proposal, is to:
> > >=20
> > > "Propagate transactions that are incentive-compatible to mine, even i=
f they
> > > don't meet minimum feerate alone."
> > >=20
> > > Effectively producing this outcome with an atomic packaging approach
> > > while at the same time maintaining network invariants seems unlikely,=
 if not
> > > impossible.
> > >=20
> > > Fees:
> > >=20
> > > A node knows what fee rate a peer will accept, and announces individu=
al
> > > 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.feer=
ate.
> > >=20
> > > Orphans:
> > >=20
> > > A node MAY drop a peer that announces txs that the node sees as orpha=
ns
> > > against its DAG. It SHOULD drop the orphan tx and MAY request missing
> > > ancestors. Presumably after some amount of time connected to peer, no=
de
> > > does not expect to see any more orphans from that peer, so these choi=
ces
> > > could evolve with the channel. However, the design that can only cons=
ider
> > > each tx in isolation will continue to cause orphan announcements on t=
he
> > > 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.
> > >=20
> > > BIP133 (feefilter):
> > >=20
> > > "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."
> > >=20
> > > https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki
> > >=20
> > > Whether the problem is "small" or not depends on the disparity betwee=
n
> > > 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 above
> > > objective.
> > >=20
> > > Packaged Transaction Relay:
> > >=20
> > > 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, si=
nce only
> > > the node is aware of peer.feerate.
> > >=20
> > > The only way to avoid dead-ending packages (including individual
> > > transactions, as is the objective) is for a node to package txs for e=
ach 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).
> > >=20
> > > Current transaction relay (txB->txA):
> > >=20
> > > =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
> > > Node0
> > > txA.feerate > node.feerate, and not orphaned (accept txA)
> > >=20
> > > txA.feerate > peer1.feerate (announce txA to peer1)
> > >=20
> > > txA.feerate < peer2.feerate (do not announce txA to peer2)
> > > -----
> > > txB.feerate > node.feerate (accept txB)
> > >=20
> > > txB.feerate > peer1.feerate (announce txB to peer1)
> > >=20
> > > txB.feerate > peer2.feerate (announce txB to peer2)
> > >=20
> > > Node1
> > > Sees/accepts txA and txB.
> > >=20
> > > Node2
> > > Never sees txA, sees/rejects txB (as an orphan).
> > >=20
> > > Packaged transaction relay (txB->txA):
> > >=20
> > > =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
> > > Node0
> > > txA.feerate > node.feerate, and not orphaned (accept txA)
> > >=20
> > > txA.feerate > peer1.feerate (announce txA to peer1)
> > >=20
> > > txA.feerate < peer2.feerate (do not announce txA to peer2)
> > > -----
> > > txB.feerate > node1.feerate (accept txB)
> > >=20
> > > txB.feerate > peer1.feerate (announce txB to peer1)
> > >=20
> > > txB.feerate > peer2.feerate (do not announce txB to peer2) <=3D=3D av=
oid
> > > predictable orphan
> > >=20
> > > txA.feerate + txB.feerate > peer2.feerate (announce pkg(A, B) to
> > > peer2) <=3D create minimal package
> > >=20
> > > Node1
> > > Sees/accepts txA and txB.
> > >=20
> > > Node2
> > > pkg(A, B) > node2.feerate (accept txA, txB)
> > >=20
> > > txA.feerate > peer3.feerate (announce txA to peer3)
> > >=20
> > > txB.feerate > peer3.feerate (announce txB to peer3)
> > >=20
> > > Sees/accepts pkg(A, B).
> > >=20
> > > Node3
> > > Sees/accepts txA and txB. <=3D avoided unnecessary packaging
> > >=20
> > > Summary:
> > >=20
> > > 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 announc=
ing
> > > 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 ag=
gregate
> > > fee using a descendant transaction.
> > >=20
> > > 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.
> > >=20
> > > Additional constraints:
> > >=20
> > > * 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, MUS=
T 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 t=
o
> > > node.feerate.
> > >=20
> > > The partial ordering of block.txs introduces an ordering constraint t=
hat
> > > 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 t=
he proof
> > > of work DoS guard. As such constraints should minimize the work/traff=
ic
> > > required to invalidate the message. The partial order constraint ensu=
res 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 n=
etwork
> > > traffic and work required is not materially different than with tx re=
lay, with
> > > two exceptions.
> > >=20
> > > These are the two central aspects of this approach (Avoiding Predicta=
ble
> > > Orphans and Creating Minimal Packages). These are graph search algori=
thms,
> > > some basic computer science. Minimality requires only that the packag=
e does
> > > not introduce txs that are not necessary to reach the peer.feerate (a=
s these
> > > can always be packaged separately). It does not require that nodes al=
l
> > > 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.
> > >=20
> > > 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 th=
e
> > > pkg.feerate is sufficiently high to connect all external inputs to th=
e
> > > 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 insufficien=
t
> > > 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 no=
t
> > > directly additive, both size/
> > >=20
> > > weight and fee are required for summation (and aggregate sigops shoul=
d
> > > be considered).
> > >=20
> > > 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 t=
he
> > > 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 v=
ersion
> > > negotiation can identify a package-accepting/sending nodes.
> > >=20
> > > I have thought about this for some time, but have not implemented eit=
her
> > > 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 cons=
ider. But I
> > > think it's worth discussing it at this point.
> > >=20
> > > e
> > >=20
> > > > -----Original Message-----
> > > > From: bitcoin-dev bitcoin-dev-bounces@lists.linuxfoundation.org On
> > > > Behalf Of Suhas Daftuar via bitcoin-dev
> > > > Sent: Wednesday, June 8, 2022 8:59 AM
> > > > To: Bitcoin Protocol Discussion
> > > > bitcoin-dev@lists.linuxfoundation.org
> > > > Subject: Re: [bitcoin-dev] Package Relay Proposal
> > > >=20
> > > > Hi,
> > > >=20
> > > > Thanks again for your work on this!
> > > >=20
> > > > One question I have is about potential bandwidth waste in the case
> > > > of nodes running with different policy rules. Here's my
> > > > understanding of a scenario I think could happen:
> > > >=20
> > > > 1) Transaction A is both low-fee and non-standard to some nodes on
> > > > the network.
> > > > 2) Whenever a transaction T that spends A is relayed, new nodes wil=
l
> > > > send INV(PKGINFO1, T) to all package-relay peers.
> > > > 3) Nodes on the network that have implemented package relay, but do
> > > > not accept A, will send getdata(PKGINFO1, T) and learn all of T's
> > > > unconfirmed parents (~32 bytes * number of parents(T)).
> > > > 4) Such nodes will reject T. But because of transaction
> > > > malleability, and to avoid being blinded to a transaction
> > > > unnecessarily, these nodes will likely still send getdata(PKGINFO1,
> > > > T) to every node that announces T, in case someone has a transactio=
n
> > > > that includes an alternate set of parent transactions that would pa=
ss
> > > > policy checks.
> > > >=20
> > > > Is that understanding correct? I think a good design goal would be
> > > > to not waste bandwidth in non-adversarial situations. In this case,
> > > > there would be bandwidth waste from downloading duplicate data from
> > > > all your peers, just because the announcement doesn't commit to the
> > > > set of parent wtxids that we'd get from the peer (and so we are
> > > > unable to determine that all our peers would be telling us the same=
 thing,
> > > > just based on the announcement).
> > > >=20
> > > > Some ways to mitigate this might be to: (a) include a hash (maybe
> > > > even just a 20-byte hash -- is that enough security?) of the packag=
e
> > > > wtxids (in some canonical ordering) along with the wtxid of the
> > > > child in the initial announcement; (b) limit the use of v1 packages
> > > > to transactions with very few parents (I don't know if this is reas=
onable
> > > > for the use cases we have in mind).
> > > >=20
> > > > Another point I wanted to bring up is about the rules around v1
> > > > package validation generally, and the use of a blockhash in
> > > > transaction relay specifically. My first observation is that it
> > > > won't always be the case that a v1 package relay node will be able
> > > > to validate that a set of package transactions is fully sorted
> > > > topologically, because there may be (non-parent) ancestors that are
> > > > missing from the package and the best a peer can validate is
> > > > topology within the package -- this means that a peer can validly
> > > > (under this
> > > > BIP) relay transaction packages out of the true topological sort (i=
f
> > > > all ancestors were included).
> > > >=20
> > > > This makes me wonder how useful this topological rule is. I suppose
> > > > there is some value in preventing completely broken implementations
> > > > from staying connected and so there is no harm in having the rule,
> > > > but perhaps it would be helpful to add that nodes SHOULD order
> > > > transactions based on topological sort in the complete transaction
> > > > graph, so that if missing-from-package ancestors are already known
> > > > by a peer (which is the expected case when using v1 package relay o=
n
> > > > transactions that have more than one generation of unconfirmed
> > > > ancestor) then the remaining transactions are already properly orde=
red,
> > > > and this is helpful even if unenforceable in general.
> > > >=20
> > > > The other observation I wanted to make was that having transaction
> > > > relay gated on whether two nodes agree on chain tip seems like an
> > > > overly restrictive criteria. I think an important design principle
> > > > is that we want to minimize disruption from network splits -- if
> > > > there are competing blocks found in a small window of time, it's
> > > > likely that the utxo set is not materially different on the two
> > > > chains (assuming miners are selecting from roughly the same sets of
> > > > transactions when this happens, which is typical). Having
> > > > transaction relay bifurcate on the two network halves would seem to
> > > > exacerbate the difference between the two sides of the split --
> > > > users ought to be agnostic about how benign splits are resolved and
> > > > would likely want their transactions to relay across the whole netw=
ork.
> > > >=20
> > > > Additionally, use of a chain tip might impose a larger burden than
> > > > is necessary on software that would seek to participate in
> > > > transaction relay without implementing headers sync/validation. I
> > > > don't know what software exists on the network, but I imagine there
> > > > are a lot of scripts out there for transaction submission to the
> > > > public p2p network, and in thinking about modifying such a script t=
o
> > > > utilize package relay it seems like an unnecessary added burden to =
first
> > > > learn a node's tip before trying to relay a transaction.
> > > >=20
> > > > Could you explain again what the benefit of including the blockhash
> > > > is? It seems like it is just so that a node could prioritize
> > > > transaction relay from peers with the same chain tip to maximize th=
e
> > > > likelihood of transaction acceptance, but in the common case this
> > > > seems like a pretty negligible concern, and in the case of a chain
> > > > fork that persists for many minutes it seems better to me that we
> > > > not partition the network into package-relay regimes and just risk =
a
> > > > little extra bandwidth in one direction or the other. If we solve
> > > > the problem I brought up at the beginning (of de-duplicating packag=
e
> > > > data across peers with a package-wtxid-commitment in the
> > > > announcement), I think this is just some wasted pkginfo bandwidth o=
n
> > > > a single-link, and not across links (as we could cache validation f=
ailure for a
> > > > package-hash to avoid re-requesting duplicate pkginfo1 messages).
> > > >=20
> > > > Best,
> > > > Suhas
> > > >=20
> > > > On Tue, Jun 7, 2022 at 1:57 PM Gloria Zhao via bitcoin-dev <bitcoin=
-
> > > > dev@lists.linuxfoundation.org <mailto:bitcoin-
> > > > dev@lists.linuxfoundation.org> > wrote:
> > > >=20
> > > > Hi Eric, aj, all,
> > > >=20
> > > > Sorry for the delayed response. @aj I'm including some paraphrased
> > > > points from our offline discussion (thanks).
> > > >=20
> > > > > Other idea: what if you encode the parent txs as a short hash of
> > > > > the wtxid (something like bip152 short ids? perhaps seeded per
> > > > > peer so collisions will be different per peer?) and include that =
in the inv
> > > > > announcement?
> > > > > Would that work to avoid a round trip almost all of the time,
> > > > > while still giving you enough info to save bw by deduping parents=
?
> > > >=20
> > > > > As I suggested earlier, a package is fundamentally a compact bloc=
k
> > > > > (or
> > > > > block) announcement without the header. Compact block (BIP152)
> > > > > announcement is already well-defined and widely implemented...
> > > >=20
> > > > > Let us not reinvent the wheel and/or introduce accidental
> > > > > complexity. I see no reason why packaging is not simply BIP152
> > > > > without the 'header'
> > > > > field, an
> > > > > updated protocol version, and the following sort of changes to
> > > > > names
> > > >=20
> > > > Interestingly, "why not use BIP 152 shortids to save bandwidth?" is
> > > > by far the most common suggestion I hear (including offline feedbac=
k).
> > > > Here's a full explanation:
> > > >=20
> > > > BIP 152 shortens transaction hashes (32 bytes) to shortids (6 bytes=
)
> > > > to save a significant amount of network bandwidth, which is
> > > > extremely important in block relay. However, this comes at the
> > > > expense of computational complexity. There is no way to directly
> > > > calculate a transaction hash from a shortid; upon receipt of a
> > > > compact block, a node is expected to calculate the shortids of ever=
y
> > > > unconfirmed transaction it knows about to find the matches (BIP 152=
:
> > > > 1, Bitcoin Core: 2). This is expensive but appropriate for block
> > > > relay, since the block must have a valid Proof of Work and new
> > > > blocks only come every ~10 minutes. On the other hand, if we requir=
e
> > > > nodes to calculate shortids for every transaction in their mempools=
 every
> > > > time they receive a package, we are creating a DoS vector.
> > > > Unconfirmed transactions don't need PoW and, to have a live
> > > > transaction relay network, we should expect nodes to handle
> > > > transactions at a high-ish rate (i.e. at least 1000s of times more
> > > > transactions than blocks). We can't pre- calculate or cache shortid=
s
> > > > for mempool transactions, since the SipHash key depends on the bloc=
k
> > > > hash and a per-connection salt.
> > > >=20
> > > > Additionally, shortid calculation is not designed to prevent
> > > > intentional individual collisions. If we were to use these shortids
> > > > to deduplicate transactions we've supposedly already seen, we may
> > > > have a censorship vector. Again, these tradeoffs make sense for
> > > > compact block relay (see shortid section in BIP 152 [3]), but not p=
ackage
> > > > relay.
> > > >=20
> > > > TLDR: DoSy if we calculate shortids on every package and censorship
> > > > vector if we use shortids for deduplication.
> > > >=20
> > > > > Given this message there is no reason to send a (potentially
> > > > > bogus) fee rate with every package. It can only be validated by
> > > > > obtaining the full set of txs, and the only recourse is dropping
> > > > > (etc.) the peer, as is the case with single txs.
> > > >=20
> > > > Yeah, I agree with this. Combined with the previous discussion with
> > > > aj (i.e. we can't accurately communicate the incentive compatibilit=
y
> > > > of a package without sending the full graph, and this whole dance i=
s
> > > > to avoid downloading a few low-fee transactions in uncommon edge
> > > > cases), I've realized I should remove the fee + weight information
> > > > from pkginfo. Yay for less complexity!
> > > >=20
> > > > Also, this might be pedantic, but I said something incorrect earlie=
r
> > > > and would like to correct myself:
> > > >=20
> > > > > > In theory, yes, but maybe it was announced earlier (while our
> > > > > > node was down?) or had dropped from our mempool or similar,
> > > > > > either way we don't have those txs yet.
> > > >=20
> > > > I said "It's fine if they have Erlay, since a sender would know in
> > > > advance that B is missing and announce it as a package." But this
> > > > isn't true since we're only using reconciliation in place of
> > > > flooding to announce transactions as they arrive, not for
> > > > rebroadcast, and we're not doing full mempool set reconciliation. I=
n
> > > > any case, making sure a node receives the transactions announced
> > > > when it was offline is not something we guarantee, not an intended =
use
> > > > case for package relay, and not worsened by this.
> > > >=20
> > > > Thanks for your feedback!
> > > >=20
> > > > Best,
> > > >=20
> > > > Gloria
> > > >=20
> > > > 0152.mediawiki#cmpctblock
> > > > 2:
> > > > https://github.com/bitcoin/bitcoin/blob/master/src/blockencodings.c=
p
> > > > p#L49
> > > > [3]: https://github.com/bitcoin/bips/blob/master/bip-
> > > > 0152.mediawiki#short-transaction-id-calculation
> > > >=20
> > > > On Thu, May 26, 2022 at 3:59 AM <eric@voskuil.org
> > > > mailto:eric@voskuil.org > wrote:
> > > >=20
> > > > Given that packages have no header, the package requires identity i=
n
> > > > a
> > > > BIP152 scheme. For example 'header' and 'blockhash' fields can be
> > > > replaced with a Merkle root (e.g. "identity" field) for the package=
,
> > > > uniquely identifying the partially-ordered set of txs. And use of
> > > > 'getdata' (to obtain a package by hash) can be eliminated (not a us=
e
> > > > case).
> > > >=20
> > > > e
> > > >=20
> > > > > -----Original Message-----
> > > > > From: eric@voskuil.org mailto:eric@voskuil.org
> > > > > <eric@voskuil.org mailto:eric@voskuil.org >
> > > > > Sent: Wednesday, May 25, 2022 1:52 PM
> > > > > To: 'Anthony Towns' <aj@erisian.com.au
> > > > > mailto:aj@erisian.com.au >; 'Bitcoin Protocol Discussion'
> > > > > <bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-
> > > > > dev@lists.linuxfoundation.org> >; 'Gloria Zhao'
> > > > > <gloriajzhao@gmail.com mailto:gloriajzhao@gmail.com >
> > > > > Subject: RE: [bitcoin-dev] Package Relay Proposal
> > > > >=20
> > > > > > From: bitcoin-dev <bitcoin-dev-
> > > > > > bounces@lists.linuxfoundation.org <mailto:bitcoin-dev-
> > > > > > bounces@lists.linuxfoundation.org> > On
> > > > > > Behalf
> > > > > > Of Anthony Towns via bitcoin-dev
> > > > > > Sent: Wednesday, May 25, 2022 11:56 AM
> > > > >=20
> > > > > > So the other thing is what happens if the peer
> > > > > > announcing packages to us
> > > > > > is
> > > > > > dishonest?
> > > > > >=20
> > > > > > They announce pkg X, say X has parents A B C and the fee
> > > > > > rate is
> > > > > > garbage.
> > > > > > But
> > > > > > actually X has parent D and the fee rate is excellent. Do
> > > > > > we request the
> > > > > > package from another peer, or every peer, to double
> > > > > > check? Otherwise
> > > > > > we're
> > > > > > allowing the first peer we ask about a package to censor
> > > > > > that tx from
> > > > > > us?
> > > > > >=20
> > > > > > I think the fix for that is just to provide the fee and weight
> > > > > > when
> > > > > > announcing
> > > > > > the package rather than only being asked for its info?
> > > > > > Then if one peer
> > > > > > makes
> > > > > > it sound like a good deal you ask for the parent txids from
> > > > > > them,
> > > > > > dedupe,
> > > > > > request, and verify they were honest about the parents.
> > > > >=20
> > > > > Single tx broadcasts do not carry an advertised fee rate,
> > > > > however the'
> > > > > feefilter' message (BIP133) provides this distinction. This
> > > > > should be
> > > > > interpreted as applicable to packages. Given this message
> > > > > there is no
> > > > > reason
> > > > > to send a (potentially bogus) fee rate with every package. It
> > > > > can only be
> > > > > validated by obtaining the full set of txs, and the only
> > > > > recourse is
> > > > > dropping (etc.) the peer, as is the case with single txs.
> > > > > Relying on the
> > > > > existing message is simpler, more consistent, and more
> > > > > efficient.
> > > > >=20
> > > > > > > > Is it plausible to add the graph in?
> > > > > >=20
> > > > > > Likewise, I think you'd have to have the graph info from
> > > > > > many nodes if
> > > > > > you're
> > > > > > going to make decisions based on it and don't want
> > > > > > hostile peers to be
> > > > > > able to
> > > > > > trick you into ignoring txs.
> > > > > >=20
> > > > > > Other idea: what if you encode the parent txs as a short
> > > > > > hash of the
> > > > > > wtxid
> > > > > > (something like bip152 short ids? perhaps seeded per
> > > > > > peer so collisions
> > > > > > will
> > > > > > be different per peer?) and include that in the inv
> > > > > > announcement? Would
> > > > > > that work to avoid a round trip almost all of the time,
> > > > > > while still
> > > > > > giving
> > > > > > you
> > > > > > enough info to save bw by deduping parents?
> > > > >=20
> > > > > As I suggested earlier, a package is fundamentally a
> > > > > compact block (or
> > > > > block) announcement without the header. Compact block
> > > > > (BIP152)
> > > > > announcement
> > > > > is already well-defined and widely implemented. A node
> > > > > should never be
> > > > > required to retain an orphan, and BIP152 ensures this is not
> > > > > required.
> > > > >=20
> > > > > Once a validated set of txs within the package has been
> > > > > obtained with
> > > > > sufficient fee, a fee-optimal node would accept the largest
> > > > > subgraph of
> > > > > the
> > > > > package that conforms to fee constraints and drop any
> > > > > peer that provides a
> > > > > package for which the full graph does not.
> > > > >=20
> > > > > Let us not reinvent the wheel and/or introduce accidental
> > > > > complexity. I
> > > > > see
> > > > > no reason why packaging is not simply BIP152 without the
> > > > > 'header' field,
> > > > > an
> > > > > updated protocol version, and the following sort of changes
> > > > > to names:
> > > > >=20
> > > > > sendpkg
> > > > > MSG_CMPCT_PKG
> > > > > cmpctpkg
> > > > > getpkgtxn
> > > > > pkgtxn
> > > > >=20
> > > > > > > For a maximum 25 transactions,
> > > > > > > 2324/2 =3D 276, seems like 36 bytes for a child-with-
> > > > > > > parents package.
> > > > > >=20
> > > > > > If you're doing short ids that's maybe 254B=3D100B
> > > > > > already, then the
> > > > > > above
> > > > > > is
> > > > > > up to 36% overhead, I guess. Might be worth thinking
> > > > > > more about, but
> > > > > > maybe
> > > > > > more interesting with ancestors than just parents.
> > > > > >=20
> > > > > > > Also side note, since there are no size/count params,
> > > > >=20
> > > > > Size is restricted in the same manner as block and
> > > > > transaction broadcasts,
> > > > > by consensus. If the fee rate is sufficient there would be no
> > > > > reason to
> > > > > preclude any valid size up to what can be mined in one
> > > > > block (packaging
> > > > > across blocks is not economically rational under the
> > > > > assumption that one
> > > > > miner cannot expect to mine multiple blocks in a row).
> > > > > Count is
> > > > > incorporated
> > > > > into BIP152 as 'shortids_length'.
> > > > >=20
> > > > > > > wondering if we
> > > > > > > should just have "version" in "sendpackages" be a bit
> > > > > > > field instead of
> > > > > > > sending a message for each version. 32 versions should
> > > > > > > be enough right?
> > > > >=20
> > > > > Adding versioning to individual protocols is just a reflection
> > > > > of the
> > > > > insufficiency of the initial protocol versioning design, and
> > > > > that of the
> > > > > various ad-hoc changes to it (including yet another
> > > > > approach in this
> > > > > proposal) that have been introduced to compensate for it,
> > > > > though I'll
> > > > > address this in an independent post at some point.
> > > > >=20
> > > > > Best,
> > > > > e
> > > > >=20
> > > > > > Maybe but a couple of messages per connection doesn't
> > > > > > really seem worth
> > > > > > arguing about?
> > > > > >=20
> > > > > > Cheers,
> > > > > > aj
> > > > > >=20
> > > > > > --
> > > > > > Sent from my phone.
> > > >=20
> > > > _______________________________________________
> > > >=20
> > > > > > bitcoin-dev mailing list
> > > > > > bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-
> > > > > > dev@lists.linuxfoundation.org>
> > > >=20
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > > >=20
> > > > _______________________________________________
> > > > bitcoin-dev mailing list
> > > > bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-
> > > > dev@lists.linuxfoundation.org>
> > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > >=20
> > > _______________________________________________
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev