path: root/17/40a0829dee1427942c8625dab02abdd6c61141

Return-Path: <eric@voskuil.org>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id E0117C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  5 Oct 2022 00:01:10 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp3.osuosl.org (Postfix) with ESMTP id B46F860AFB
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  5 Oct 2022 00:01:10 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org B46F860AFB
Authentication-Results: smtp3.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=2VeuAXo7
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 smtp3.osuosl.org ([127.0.0.1])
 by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id VTLO6M4C1NRb
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  5 Oct 2022 00:01:07 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 8B87B60AD8
Received: from mail-pj1-x102f.google.com (mail-pj1-x102f.google.com
 [IPv6:2607:f8b0:4864:20::102f])
 by smtp3.osuosl.org (Postfix) with ESMTPS id 8B87B60AD8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  5 Oct 2022 00:01:07 +0000 (UTC)
Received: by mail-pj1-x102f.google.com with SMTP id
 v10-20020a17090a634a00b00205e48cf845so272685pjs.4
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 04 Oct 2022 17:01:07 -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:to:from
 :from:to:cc:subject:date;
 bh=je8iivXu/Xy/ULTHz+ApLuCNa73pbuG3D/1xhJVeh3Q=;
 b=2VeuAXo7GNNA/UYBTF30lWAGVUo6F1trqWU2ilDYa+DrXyoGWceJfZEwWmzZ5fdCt+
 zHmLDOXXx9ufTMb1el+oUUBfHjlI578saI+AkKG8DlUhR9R2SRa6AI+cgl2LZ60BmGeT
 RdJQuKdKoUaLF9PGZyy9AE0qy31ykBfhLnds3X0p5x1BOtsY3pmGRqQJbgZuJ7LoKs3L
 mOjcme1YQ1m9FDlFMiqRn6qdr3vFmf8t1rMRbrwvszVFxaNyjv+rTjy04ZatMMIUOtfa
 +oxc4xyg/devY+Qv/t33IzVw8+HIYs+uTySRoEs2tpImnv4KLRjp/J52W6RTFKDL8KoL
 Z5HQ==
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:to:from
 :x-gm-message-state:from:to:cc:subject:date;
 bh=je8iivXu/Xy/ULTHz+ApLuCNa73pbuG3D/1xhJVeh3Q=;
 b=vD5b0aL6KYN1VLNqRwHdDBN+A3vlqmX/cNFyhzuLjcqMzb7qTz241NvJPP7gQViHJi
 DfIdHeNfqoMgmjW35XxoNe4Xcx7jD/SgXc46yhcN0Z5D7b+ciD9rGpfCzvNTicVCy5js
 9KDBqekXMUNNstfVHTYvJhzp/Q7oxNhk9rbWEM6ChvrSOsMqov5f3lV1RTPTiZ+0++5A
 VF4xIq4HVhlaPZRvHkVR5Kcwrvlo8nt/9MKtqFQ/X1m287GAiBxFLasE3Tq5iySrHX1Q
 SbGak4nbUGcbcbZ5AvLgOpepoLqa6fXKKn7yhINRp2YJyW7Xd5dpANiQI7LrMoeEEhld
 fwhg==
X-Gm-Message-State: ACrzQf2o4ClNmUWG8mK3pj7GSVPOysIv4CRBjhFmEcS3kcUe9HTZYQ7q
 cx8mhjsuR4Uq6dS6v72woi3mAs1qlGKOjQ==
X-Google-Smtp-Source: AMsMyM6NW5nfHa45Un5B3DXjxgB3uXzaPIsBOeiMONLmGS4HfF4we6aVnve89aV8B8o14ZxEohDWQQ==
X-Received: by 2002:a17:903:2c6:b0:17a:7e1:16f8 with SMTP id
 s6-20020a17090302c600b0017a07e116f8mr29012912plk.59.1664928066238; 
 Tue, 04 Oct 2022 17:01:06 -0700 (PDT)
Received: from ERICDESKTOP ([50.35.79.94]) by smtp.gmail.com with ESMTPSA id
 kx1-20020a17090b228100b0020a28156e11sm125743pjb.26.2022.10.04.17.01.04
 (version=TLS1_2 cipher=ECDHE-ECDSA-AES128-GCM-SHA256 bits=128/128);
 Tue, 04 Oct 2022 17:01:05 -0700 (PDT)
From: <eric@voskuil.org>
To: "'Suhas Daftuar'" <sdaftuar@gmail.com>,
 "'Bitcoin Protocol Discussion'" <bitcoin-dev@lists.linuxfoundation.org>
References: <005e01d87b89$3d99df60$b8cd9e20$@voskuil.org>
 <CAFp6fsF=fLVq4=PSEpK+4yD+SZ+uVMJLM616q3F--zcuuqL3pg@mail.gmail.com>
In-Reply-To: <CAFp6fsF=fLVq4=PSEpK+4yD+SZ+uVMJLM616q3F--zcuuqL3pg@mail.gmail.com>
Date: Tue, 4 Oct 2022 17:01:04 -0700
Message-ID: <02fc01d8d84d$90a7b120$b1f71360$@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: AQLNpoIM2pVq9V6wiGYHqtH7YA7ZbgI9L/JKrAMpcfA=
Content-Language: en-us
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: Wed, 05 Oct 2022 00:01:11 -0000

> Hi,
>=20
> Thanks for sharing your thoughts on packaged transaction relay.

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
> 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).

Yes - there is always the presumption of an optimally-performing =
protocol (not limited to bandwidth), this is just a restatement from the =
OP.

The OP fails to eliminate orphan announcement, fails to prevent packages =
with insufficient fee from getting stuck in the same manner as txs =
(without explicitly re-announcing them again in an even larger package =
of higher feerate), and results in orphaned package announcements for =
the same reason (a static package is effectively just a larger tx).

Due to the resulting orphaning, a node must allow its peer to continue =
to broadcast unverifiable orphans to it, potentially chasing ancestry. =
So in addition to bandwidth waste, there is also an inherent problem of =
bandwidth DOS. These are problems specifically addressed by packaged =
relay.

[Regarding bandwidth waste: I've pointed out in years past that breaking =
the Bitcoin versioning scheme creates a requirement that any unknown =
message type be considered valid. Up until a recently-deployed protocol =
change, it had always been possible to validate messages by type. I =
noticed recently that validating nodes have been dropping peers at an =
increasing rate (a consequence of that deployment). Despite being an =
undocumented compatibility break, it is now unfortunately a matter of =
protocol that a peer must allow its peers to waste its bandwidth to =
remain compatible - something which we should eliminate.]

> 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.

It is certainly possible that there is ambiguity in BIP133 (and BIPs =
that modify it). However it's not clear to me which such ambiguity you =
are referring to. There is no guessing proposed.

> 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,

This is a possible implementation. What makes it undesirable?

> and, at any rate, is more complex than merely comparing a pair of =
feerates.

There are no necessary protocol changes (though a new INV type is =
ideal), so the relative complexity you are implying could only arise =
from implementation. While implementation considerations are relevant, =
achieving simplicity in the protocol is presumably the priority. =
Further, implementation complexity must be considered from what is =
necessary to actually achieve the objectives, and not from the =
perspective of any given implementation.

Merely comparing a pair of feerates produces the problems described =
above, which includes not resolving the central problem, so this is an =
apples-to-oranges comparison. It's also more complex than doing nothing, =
but that also doesn't resolve the problem.

> 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:
>=20
> - 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,

Yes

> 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.
>=20
> - Let A be a high fee, but low feerate transaction.

Low feerate means low fee (as high/low can only be relative to size), =
it's not clear how these can both be true.

>  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),

As a node knows which txs it has relayed to its peer, order of arrival =
is inconsequential.

> 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.=20

Block inclusion in not pertinent, either may be included.

> 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.

Given that A and B are conflicts, A and B+C are conflicts. This is no =
different than the original conflict of A and B, and decided based on =
the required BIP125 fee increment. If A arrives first, B must be an =
increment over A, and vice versa. Upon the arrival of C, given prior =
acceptance of both A and B, B+C must be an increment over A, as the =
conflict arises from A/B.

> 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.

Predicting a peer's set of confirmable transactions ("mempool") is not =
the objective or a requirement. As far as I can tell it is sufficient to =
achieve requirements to the extent there are no unpublished policies.

Upon startup and connection to a peer, a node may have an empty mempool. =
In this case there will be no orphan or redundant announcements from the =
peer.

A node with a populated mempool may connect to a peer. In that case the =
peer will receive announcements from the peer for txs which it may =
already have. This will also occur due to multiple peer connections. =
Redundancy is not within the scope of this or the OP proposals (there =
are other proposals for limiting this redundancy in both scenarios to =
the extent desirable).

Once a node has been connected to the network for some amount of time, =
there will be no orphans or connection-specific redundancies announced =
to it. This provides a basis for the node to drop non-conforming peers =
(that support packaged relay), improving protection against =
bandwidth-wasting peers.

Any node which implements unpublished policies can expect to receive =
orphan announcements. This raises the question of whether the protocol =
should incorporate a facility for such a node to chase down orphans in =
the case where it is orphaning them by deleting their ancestors, even =
though it publishes that it accepts them based on feerate/rbf. This =
would imply that there is some other discretionary aspect of =
transactions that, as a matter of protocol, should be considered for =
relay.

Any such aspect internal to a tx would be economically-irrational to =
consider (which includes censorship), in which case it would seem =
preferrable to let such nodes simply accept the fact that they are =
creating orphans for themselves.

Any such aspect external to the tx would also be economically-irrational =
(mining wants the greatest possible fee opportunity), but may be a =
consequence of resource limitations. Storing confirmable txs in RAM =
constrains such resources by orders of magnitude, and an assumption that =
an implementation must do this would be an error (some do not). Yet =
storage remains finite, so this remains a possible though marginal =
consideration given the presumption that all accepted txs are both =
confirmable and satisfy feerate/rbf policy. In the case where a node is =
discarding previously accepted and yet-unconfirmed txs, the node accepts =
the possibility that this will result in it receiving orphan =
announcements.

The rational way to reduce the size of the mempool is to raise the =
published feerate, discarding txs that no longer conform. While this was =
not specifically described in the fairly informal proposal, the receipt =
of a reduced peer feerate message can cause a node to update its state =
for that peer, eliminating the possibility of orphan announcements to =
it.

>  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.

I don't think this has been shown, but finding such issues is of course =
why we discuss it.

> 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.

The problems that I see with static packaging are:

1) Does not fully resolve the problem - a static package itself can get =
stuck for the same reason as a tx.
2) Requires wallet formation of a static packages - to resolve what is =
fundamentally a network issue.
3) Adds a complex new protocol to achieve what can be accomplished with =
almost no protocol change.
4) Is not bandwidth optimal, as it continues to relay/chase orphans =
(singular and packaged).
5) Is not DOS optimal, as it requires allowance for orphans and =
redundancies.

Regarding complexity - searching and marking a DAG is basic CS, and =
there isn't much else to the necessary implementation. There are no new =
messages, just a version bump and a preferably a new INV type. In terms =
of performance and therefore any possible increase to relay latency, =
this is easily measured in terms of complexity. Whether this would be a =
latency increase or decrease in relation to the OP is unclear.

The complexity of the search for is linear in the size of the mempool =
subgraph (1) induced by the traversal of ancestors from the potential =
package's last tx, and (2) reduced by the set of txs known to the peer. =
(2) includes both txs sent to and received from the peer. This would =
appear to be a marginal cost.

A draft of the search algorithm is available here:

https://github.com/libbitcoin/libbitcoin-network/wiki/Iterative-Channel-P=
ackage-Computation

Best,
e