path: root/12/3c282efa03b7a273d51b27c5235648b25481e5

Return-Path: <eric@voskuil.org>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id B2DF9C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 26 Sep 2022 21:19:47 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 6D8AF405A8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 26 Sep 2022 21:19:45 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 6D8AF405A8
Authentication-Results: smtp2.osuosl.org;
 dkim=pass (2048-bit key) header.d=voskuil-org.20210112.gappssmtp.com
 header.i=@voskuil-org.20210112.gappssmtp.com header.a=rsa-sha256
 header.s=20210112 header.b=NXCvu9bM
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level: 
X-Spam-Status: No, score=-1.898 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001]
 autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id NVoiBNEsdbOw
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 26 Sep 2022 21:19:42 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 8FF2C40CA4
Received: from mail-pg1-x52a.google.com (mail-pg1-x52a.google.com
 [IPv6:2607:f8b0:4864:20::52a])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 8FF2C40CA4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 26 Sep 2022 21:19:42 +0000 (UTC)
Received: by mail-pg1-x52a.google.com with SMTP id b5so7672321pgb.6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Mon, 26 Sep 2022 14:19:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=voskuil-org.20210112.gappssmtp.com; s=20210112;
 h=content-language:thread-index:content-transfer-encoding
 :mime-version:message-id:date:subject:in-reply-to:references:cc:to
 :from:from:to:cc:subject:date;
 bh=KX6CYLnqIOq00g6RxF4M/MMMDAL0Rcn3sL9EP81Pgoo=;
 b=NXCvu9bMyVpQ+s480UR8p+NGW+MrWxwSUQ8tyJ57295q6BP5T4nxRdSnSUKdXtfKPM
 xyLlL3IkRakHnJ9G2VlcqcApNhuscSfntbaYShTDMkkG/BC/chOaldfu8RvAbCrgeX2a
 uK88IKsqi6qUfyhy4meMDQwoO9zymShIvTI7pndefqFybZShs97jjPLPyLfFuQLfwBiw
 6tZarI6Tlsu5SXAqvsR2FaMOa2bKJtaidEYUcddR0tE4wfqdXOr+aCJzO2g52Qt4pA46
 p16wz0N3OfWZQw+9bGfPW3/50JpBGgkgFC6ecWom25qlQZ8dsCFUZVy+TUz2zEjlzQ28
 f+LQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=content-language:thread-index:content-transfer-encoding
 :mime-version:message-id:date:subject:in-reply-to:references:cc:to
 :from:x-gm-message-state:from:to:cc:subject:date;
 bh=KX6CYLnqIOq00g6RxF4M/MMMDAL0Rcn3sL9EP81Pgoo=;
 b=FWZfXMi/K47wJJ/sbPRGOtnAPeQ6AW/zCMNYnOA0bRFFqw8YJ5D5/x8pPzj9n/c2EF
 xO/Uj/6Fo/82+Ebbo6MHqFDwyHHPLYFUk5jqM+CJ6x6MAJReI4XVUsyMM5gz75+IdHra
 uO58bs9CEsn2E3UMnkGkkwuuJr7N95HTVRT6dEHwYF/40DjewG38WK9M0Nf5nAgH0bhw
 nQUdRSLucMAWEI6nwHPNmYTdK5t/CPhG/qzrSVSmarKcsdsUu8xOR87pvSvJjGqFsK+i
 pdtZlmo9asBfWEGRjkuzENW009/TIZvPYC3F4g27px9b+QSo9tkT/U/Yblf/7DU7qvVe
 ATWQ==
X-Gm-Message-State: ACrzQf3BFXn6HEZ2FILp18fuUsbXPQdtCWWfmsIUMJfjWx3wXUhppH7N
 oWGixrbCy13ij6XBOhAnfcnPmzw+FcCYig==
X-Google-Smtp-Source: AMsMyM7vNRww0u8lzfMbj4Urz+A7BC1Gez1pDnUbxUJr7aCUIegCrk0JsA2bJVR4M0ahktbuc95rjg==
X-Received: by 2002:a05:6a00:248b:b0:542:6ae2:24d5 with SMTP id
 c11-20020a056a00248b00b005426ae224d5mr26128079pfv.65.1664227181714; 
 Mon, 26 Sep 2022 14:19:41 -0700 (PDT)
Received: from ERICDESKTOP ([50.35.67.197]) by smtp.gmail.com with ESMTPSA id
 jc6-20020a17090325c600b00176b63535adsm11611754plb.260.2022.09.26.14.19.38
 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128);
 Mon, 26 Sep 2022 14:19:39 -0700 (PDT)
From: <eric@voskuil.org>
To: "'alicexbt'" <alicexbt@protonmail.com>
References: <005e01d87b89$3d99df60$b8cd9e20$@voskuil.org>
 <EDCbz3IJLDkExNWyM1WLLSh5qUioK6HdMEh-eofWmete0baz1lo8uF1YFzLaTXxgQhzvtDtqpX2mTMaDpB7_4-SRNnpJX4F8zgL5e6NGS0U=@protonmail.com>
In-Reply-To: <EDCbz3IJLDkExNWyM1WLLSh5qUioK6HdMEh-eofWmete0baz1lo8uF1YFzLaTXxgQhzvtDtqpX2mTMaDpB7_4-SRNnpJX4F8zgL5e6NGS0U=@protonmail.com>
Date: Mon, 26 Sep 2022 14:19:39 -0700
Message-ID: <00cb01d8d1ed$b0191dc0$104b5940$@voskuil.org>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="utf-8"
Content-Transfer-Encoding: quoted-printable
X-Mailer: Microsoft Outlook 16.0
Thread-Index: AQLNpoIM2pVq9V6wiGYHqtH7YA7ZbgMBzWzhq/BpIbA=
Content-Language: en-us
Cc: 'Bitcoin Protocol Discussion' <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Packaged Transaction Relay
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Mon, 26 Sep 2022 21:19:47 -0000

> Hi Eric,
>=20
>=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.

Hello, thanks for the reply.

> > 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."
>=20
> According to [bitcoinops][1]: Without package relay, it=E2=80=99s not =
possible to
> effectively CPFP fee bump a transaction that=E2=80=99s below the =
minimum feerate
> nodes accept.

Yes, the problem statement is not in question, just the mechanism of =
resolution. The problem of stuck txs arises from minimum fee rate =
policy, which is a necessary DOS guard.

A secondary issue is that of orphan relay. As a node must allow receipt =
of orphans, it has no means to differentiate a flood of unconfirmable =
txs from those that are confirmable.

> Matt Corallo's thoughts in a bitcoin core [issue][2]:
>=20
> "Matt Corallo recently wrote about an example on the bitcoin-dev =
mailing list
> involving lightning transactions, where pre-signed transactions might =
be
> broadcast to the blockchain long after they were generated, and thus =
not
> 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 =
increase
> the confirmation speed of such transactions, and that implies we may =
need
> to introduce a mechanism for those parent transactions to be relayed =
along
> with their higher feerate children, even if the parent transaction =
would be
> rejected by itself."

While this is a valid scenario, the problems directly affect Bitcoin. =
Those problems propagate to layers, but are not unique to layering.

> 1)Is it possible to have multiple pre-signed transactions with =
different fee
> rates in a range? Example: PSBT1: 5 sat/vbyte, PSBT2: 10 sat/vbyte, =
PSBT3: 20
> sat/vbyte and PSBT4: 100 sat/vbyte

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.

> 2)How would covenants affect this problem?

There are a good number of covenant proposals, though I assume they are =
all 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.

> 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 =
could be
> managed in a different way?

Always. Only signed transactions are accepted. But assuming you are =
referring 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.

> After reading several links related to packages and bitcoin core pull =
requests,
> I found it anti-bitcoin to introduce so much complexity because its =
not
> possible to CPFP fee bump a tx below minimum fee rate.

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 =
complexity of the proposed solutions are not justified by such =
scenarios.

I would say that the problem is real, and that the least complex option =
is generally preferred. There are always tradeoffs, and balancing these =
is part of protocol development. But as a rule, complexity within a =
protocol (communication) is to be avoided where possible.

> > 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.
>=20
> It is easy to send another tx if there is only one user involved =
however
> packages are trying to fix issues in which multiple users and =
transaction pre-
> signed between them are involved. So, it will be difficult to =
coordinate and
> create new pre-signed transactions in some cases although it is =
possible for
> some use cases.

Given that nodes do not deal in presigned txs, this coordination =
difficulty could not be increased in any scenario.

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 dynamic 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, =
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.
>=20
> This makes sense particularly if multiple node implementations are =
used in
> future.

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

> My other questions:
>=20
> a)If a package has tx1, tx2, tx3, tx4 and tx5 and miner just include =
tx1 and tx2
> in the block, how does this affect the projects considered for =
packages
> proposal?

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.

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 down the road while complicating the protocol.

> b)How does changing the order of txs in a package affect these =
transactions?

There is no impact. I proposed the partial ordering to facilitate fail =
fast.

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 and only serves to slow validation (order constrains =
concurrency).

> c)Do packages introduce more attack vectors in bitcoin for front =
running or
> MEV? MEV in bitcoin currently only affects the projects that are =
considered
> in packages proposal.

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

> d)What if the package contains a transactions with sanctioned address?

One can consider this a policy, much like fee rate. Any policy that is =
applied to transactions and not known to its peers will result in the =
node receiving orphans. As such the node either must allow orphans or =
drop peers sending orphans under the assumption that the peer is =
expected to have implemented the same policy.

> e)Why would miners use packages if the existing scenario in terms of =
fees
> per block is beneficial for them?

The presumption is that the miner is only ever seeing txs that satisfy =
its fee rate policy, so this is just more opportunity.

I'd add that the problem of "pinning" is related, but exacerbated by =
opaque policy (internal to certain implementations). Any node that =
ejects txs from its pool of valid but unconfirmed txs that satisfy fee =
rate policy is going 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.

A subset of this problem is RBF policy. It is nice to see some movement =
toward 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 resolved through advertised fee policy. Any node that imposes =
policy beyond this will also see orphans and cause txs to get stuck.

The scenario and therefore complexity consequences of an =
implementation-specific memory-constrained tx pool are becoming =
increasingly apparent. These are implementation issues, not protocol =
issues. This can be observed in a recent thread: =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-September/02=
0937.html

Over time we are likely to see that the only policies that remain in =
widespread application are those that are necessary for DOS protection =
(fee rate), as other restrictions are not economically rational and =
cannot be enforced. 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 reiterate, any policy beyond what is published via the =
protocol will cause the above problems.

e

> /dev/fd0
>=20
> [1]: https://bitcoinops.org/en/topics/package-relay/
> [2]: https://github.com/bitcoin/bitcoin/issues/14895
>=20
> Sent with Proton Mail secure email.
>=20
> ------- Original Message -------
> On Thursday, June 9th, 2022 at 4:13 AM, Eric Voskuil via bitcoin-dev =
<bitcoin-
> dev@lists.linuxfoundation.org> wrote:
>=20
>=20
> > 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):
> >
> > =
=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)
> >
> > 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):
> >
> > =
=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)
> >
> > 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) <=3D=3D =
avoid
> > predictable orphan
> >
> > txA.feerate + txB.feerate > peer2.feerate (announce pkg(A, B) to
> > peer2) <=3D 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. <=3D 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
> >
> > > -----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
> > >
> > > Hi,
> > >
> > > Thanks again for your work on this!
> > >
> > > 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:
> > >
> > > 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 =
will
> > > 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 =
transaction
> > > that includes an alternate set of parent transactions that would =
pass
> policy checks.
> > >
> > > 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).
> > >
> > > 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 =
package
> > > 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 =
reasonable
> for the use cases we have in mind).
> > >
> > > 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 =
(if
> > > all ancestors were included).
> > >
> > > 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 =
on
> > > transactions that have more than one generation of unconfirmed
> > > ancestor) then the remaining transactions are already properly =
ordered,
> and this is helpful even if unenforceable in general.
> > >
> > > 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 =
network.
> > >
> > > 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 =
to
> > > utilize package relay it seems like an unnecessary added burden to =
first
> learn a node's tip before trying to relay a transaction.
> > >
> > > 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 =
the
> > > 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 =
package
> > > data across peers with a package-wtxid-commitment in the
> > > announcement), I think this is just some wasted pkginfo bandwidth =
on
> > > a single-link, and not across links (as we could cache validation =
failure for a
> package-hash to avoid re-requesting duplicate pkginfo1 messages).
> > >
> > > Best,
> > > Suhas
> > >
> > > 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:
> > >
> > > Hi Eric, aj, all,
> > >
> > > Sorry for the delayed response. @aj I'm including some paraphrased
> > > points from our offline discussion (thanks).
> > >
> > > > 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?
> > >
> > > > 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...
> > >
> > > > 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
> > >
> > > Interestingly, "why not use BIP 152 shortids to save bandwidth?" =
is
> > > by far the most common suggestion I hear (including offline =
feedback).
> > > Here's a full explanation:
> > >
> > > 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 =
every
> > > 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 =
require
> > > 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 =
shortids
> > > for mempool transactions, since the SipHash key depends on the =
block
> hash and a per-connection salt.
> > >
> > > 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 =
package
> relay.
> > >
> > > TLDR: DoSy if we calculate shortids on every package and =
censorship
> > > vector if we use shortids for deduplication.
> > >
> > > > 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.
> > >
> > > Yeah, I agree with this. Combined with the previous discussion =
with
> > > aj (i.e. we can't accurately communicate the incentive =
compatibility
> > > of a package without sending the full graph, and this whole dance =
is
> > > 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!
> > >
> > > Also, this might be pedantic, but I said something incorrect =
earlier
> > > and would like to correct myself:
> > >
> > > > > 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.
> > >
> > > 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. =
In
> > > 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.
> > >
> > > Thanks for your feedback!
> > >
> > > Best,
> > >
> > > Gloria
> > >
> > > 0152.mediawiki#cmpctblock
> > > [2]:
> > > =
https://github.com/bitcoin/bitcoin/blob/master/src/blockencodings.cp
> > > p#L49
> > > [3]: https://github.com/bitcoin/bips/blob/master/bip-
> > > 0152.mediawiki#short-transaction-id-calculation
> > >
> > > On Thu, May 26, 2022 at 3:59 AM <eric@voskuil.org
> > > mailto:eric@voskuil.org > wrote:
> > >
> > > Given that packages have no header, the package requires identity =
in
> > > 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 =
use
> > > case).
> > >
> > > e
> > >
> > > > -----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
> > > >
> > > > > 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
> > > >
> > > > > So the other thing is what happens if the peer
> > > announcing packages to us
> > > > is
> > > > > dishonest?
> > > > >
> > > > > 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?
> > > > >
> > > > > 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.
> > > >
> > > > 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.
> > > >
> > > > > >> Is it plausible to add the graph in?
> > > > >
> > > > > 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.
> > > > >
> > > > > 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?
> > > >
> > > > 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.
> > > >
> > > > 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.
> > > >
> > > > 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:
> > > >
> > > > sendpkg
> > > > MSG_CMPCT_PKG
> > > > cmpctpkg
> > > > getpkgtxn
> > > > pkgtxn
> > > >
> > > > > > For a maximum 25 transactions,
> > > > > >2324/2 =3D 276, seems like 36 bytes for a child-with-
> > > parents package.
> > > > >
> > > > > 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.
> > > > >
> > > > > >Also side note, since there are no size/count params,
> > > >
> > > > 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'.
> > > >
> > > > > > 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?
> > > >
> > > > 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.
> > > >
> > > > Best,
> > > > e
> > > >
> > > > > Maybe but a couple of messages per connection doesn't
> > > really seem worth
> > > > > arguing about?
> > > > >
> > > > > Cheers,
> > > > > aj
> > > > >
> > > > >
> > > > > --
> > > > > Sent from my phone.
> > > > >
> > > _______________________________________________
> > > > > bitcoin-dev mailing list
> > > > > bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-
> > > dev@lists.linuxfoundation.org>
> > > > >
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> > >
> > > _______________________________________________
> > > bitcoin-dev mailing list
> > > bitcoin-dev@lists.linuxfoundation.org <mailto:bitcoin-
> > > dev@lists.linuxfoundation.org>
> > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> >
> >
> >
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev