path: root/1a/61124320fff16bfd067cd2971aebc3c0fc4f8f

Return-Path: <sdaftuar@gmail.com>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id ED202C002D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  8 Jun 2022 15:59:19 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id C427C419A2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  8 Jun 2022 15:59:19 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: smtp4.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id YchHmY75pgS2
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  8 Jun 2022 15:59:16 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-yb1-xb2b.google.com (mail-yb1-xb2b.google.com
 [IPv6:2607:f8b0:4864:20::b2b])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 7C19A41948
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  8 Jun 2022 15:59:16 +0000 (UTC)
Received: by mail-yb1-xb2b.google.com with SMTP id s39so9680498ybi.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed, 08 Jun 2022 08:59:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
 bh=30N/JiZ9Cz8JsUlL0Ytfk9DFR30GI+yyoPyUKs7ar8U=;
 b=KRJDPA7a3YH/7q1jCyBogAasC96Vadnc0D7uZ4dnextWIBwjCW45ET+M517SzI/svJ
 7+aqZs3dWYI80MBcQJefFTL8tsMloJUnitjHT14GSlgCYGkA89qrPyccokQDO2AQMqj4
 qy+hwl8s9fcOftOoKUnDVowE2aQTkaB2aJkjmCkIahFwIGc9yUGyl9k349A7Bq40SYfZ
 o5v5gktboxx+z5tObnimH9EPdOAEleU5Qb1KPiEhnGgc07LbCZ0zyzOk7DxaNODqJjCl
 6SIsl22NkNNo+ei6MHu4I4LMRH9suvxITA7kPtSgHT82TRlk585z8gkgyZkaRmy1qvPZ
 qgRg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20210112;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to;
 bh=30N/JiZ9Cz8JsUlL0Ytfk9DFR30GI+yyoPyUKs7ar8U=;
 b=7VkjkfKAkToSmmMjRYZD//iHHpyhsBL/HYzLy/Kz1X8K/SClr5ggTs3qgIRDBV/WW+
 CJvrZF9kCJ+kZHdFKtpdw8X2p0vEox/DBAejrw3v0SaOY/FB9UPR3cI2CpvGmno+EqZw
 j0Sb3s0RrFCoapS1Ql4c9D6NzrdLobEr1X4CvpssTO38U1uy3ww7CZ9ZXIRKwDFBVxYn
 ZTb5JntL4BdnM/K8YEtEsobM3NYK6L+/ZaYapXFQ/5UeFLsIvhxn750/SCtEg5+QTgHM
 Gjjp81bsNOWD5UflqNZlRTlDKqI/Kh/b4O9dEXQP8h0YutK9LGUxR8fTGLhzU03Xh8DK
 kaJQ==
X-Gm-Message-State: AOAM533Z4qq/klBsSbWWFEwt6J1bG8VmcC47cvv5o/umpVLQDgk9iT5b
 Iq90cAiLADiStMDI138kJ16aw4guNLmQlTc2f7r70Y1n
X-Google-Smtp-Source: ABdhPJz/PE2boKVIeeLkSN7ng5GNVZajqVB587f6X+4NZ9B9/WBU1WV1tX86ObhwbYNt6g2VtOzYVaVo/0Fqdt2uwoo=
X-Received: by 2002:a25:22d5:0:b0:64f:f06c:d96c with SMTP id
 i204-20020a2522d5000000b0064ff06cd96cmr33011207ybi.123.1654703954001; Wed, 08
 Jun 2022 08:59:14 -0700 (PDT)
MIME-Version: 1.0
References: <CAFXO6=JROe_9ih2h+_CCH-UbxehsM5RQ6YyNnPesEpveBEtdow@mail.gmail.com>
 <20220518003531.GA4402@erisian.com.au>
 <CAFXO6=LWM4eHM=zJhejw5981+8h7QHTbwpz0jEbWkrLOX0037Q@mail.gmail.com>
 <20220523213416.GA6151@erisian.com.au>
 <CAFXO6=KXToP2MFWQ1JVKX6jV++utw8E4Z13T4cH+mfgtyeUx_A@mail.gmail.com>
 <2B3D1901-901C-4000-A2B9-F6857FCE2847@erisian.com.au>
 <CAFXO6=K6FXNFwOZ3VyT6_RZY2F2BX+iTy+MyOshRBfNnn9Hqyg@mail.gmail.com>
 <8FFE048D-854F-4D34-85DA-CE523C16EEB0@erisian.com.au>
 <017501d87079$4c08f9c0$e41aed40$@voskuil.org>
 <001201d870ac$8d7a06a0$a86e13e0$@voskuil.org>
 <CAFXO6=LGX4zRN3rBPs89cgYKrM5H3kViR1QZRdMeyaS_HELPTQ@mail.gmail.com>
In-Reply-To: <CAFXO6=LGX4zRN3rBPs89cgYKrM5H3kViR1QZRdMeyaS_HELPTQ@mail.gmail.com>
From: Suhas Daftuar <sdaftuar@gmail.com>
Date: Wed, 8 Jun 2022 11:59:03 -0400
Message-ID: <CAFp6fsE0ceXtwS=9wrzoKzuuay=n=66Ve9hcqcNPa09KfJCgcw@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000632bb205e0f1c9fa"
Subject: Re: [bitcoin-dev] Package Relay Proposal
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, 08 Jun 2022 15:59:20 -0000

--000000000000632bb205e0f1c9fa
Content-Type: text/plain; charset="UTF-8"

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> 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
>
> [1]:
> https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#cmpctblock
> [2]:
> https://github.com/bitcoin/bitcoin/blob/master/src/blockencodings.cpp#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> 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 <eric@voskuil.org>
>> > Sent: Wednesday, May 25, 2022 1:52 PM
>> > To: 'Anthony Towns' <aj@erisian.com.au>; 'Bitcoin Protocol Discussion'
>> > <bitcoin-dev@lists.linuxfoundation.org>; 'Gloria Zhao'
>> > <gloriajzhao@gmail.com>
>> > Subject: RE: [bitcoin-dev] Package Relay Proposal
>> >
>> > > From: bitcoin-dev <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,
>> > > >23*24/2 = 276, seems like 36 bytes for a child-with-parents package.
>> > >
>> > > If you're doing short ids that's maybe 25*4B=100B 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
>> > > 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
>

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

<div dir=3D"ltr">Hi,<div><br></div><div>Thanks again for your work on this!=
</div><div><br></div><div>One question I have is about potential bandwidth =
waste in the case of nodes running with different policy rules.=C2=A0 Here&=
#39;s my understanding of a scenario I think could happen:</div><div><br></=
div><div>1) Transaction A is both low-fee and non-standard to some nodes on=
 the network.</div><div>2) Whenever a transaction T that spends A is relaye=
d, new nodes will send INV(PKGINFO1, T) to all package-relay peers.</div><d=
iv>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&#39;s unconfirm=
ed parents (~32 bytes * number of parents(T)).</div><div>4) Such nodes will=
 reject T.=C2=A0 But because of transaction malleability, and to avoid bein=
g blinded to a transaction unnecessarily, these nodes will likely still sen=
d getdata(PKGINFO1, T) to every node that announces T, in case someone has =
a transaction that includes an alternate set of parent transactions that wo=
uld pass policy checks.</div><div><br></div><div>Is that understanding corr=
ect?=C2=A0 I think a good design goal would be to not waste bandwidth in no=
n-adversarial situations.=C2=A0 In this case, there would be bandwidth wast=
e from downloading duplicate data from all your peers, just because the ann=
ouncement doesn&#39;t commit to the set of parent wtxids that we&#39;d get =
from the peer (and so we are unable to determine that all our peers would b=
e telling us the same thing, just based on the announcement).</div><div><br=
></div><div>Some ways to mitigate this might be to: (a) include a hash (may=
be even just a 20-byte hash -- is that enough security?) of the package wtx=
ids (in some canonical ordering) along with the wtxid of the child in the i=
nitial announcement; (b) limit the use of v1 packages to transactions with =
very few parents (I don&#39;t know if this is reasonable for the use cases =
we have in mind).</div><div><br></div><div>Another point I wanted to bring =
up is about the rules around v1 package validation generally, and the use o=
f a blockhash in transaction relay specifically.=C2=A0 My first observation=
 is that it won&#39;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 topo=
logically, because there may be (non-parent) ancestors that are missing fro=
m the package and the best a peer can validate is topology within the packa=
ge -- this means that a peer can validly (under this BIP) relay transaction=
 packages out of the true topological sort (if all ancestors were included)=
.</div><div><br></div><div>This makes me wonder how useful this topological=
 rule is.=C2=A0 I suppose there is some value in preventing completely brok=
en 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 t=
ransactions 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 transa=
ctions are already properly ordered, and this is helpful even if unenforcea=
ble in general.=C2=A0=C2=A0</div><div><br></div><div>The other observation =
I wanted to make was that having transaction relay gated on whether two nod=
es agree on chain tip seems like an overly restrictive criteria.=C2=A0 I th=
ink an important design principle is that we want to minimize disruption fr=
om network splits -- if there are competing blocks found in a small window =
of time, it&#39;s likely that the utxo set is not materially different on t=
he two chains (assuming miners are selecting from roughly the same sets of =
transactions when this happens, which is typical).=C2=A0 Having transaction=
 relay bifurcate on the two network halves would seem to exacerbate the dif=
ference between the two sides of the split -- users ought to be agnostic ab=
out how benign splits are resolved and would likely want their transactions=
 to relay across the whole network.</div><div><br></div><div>Additionally, =
use of a chain tip might impose a larger burden than is necessary on softwa=
re that would seek to participate in transaction relay without implementing=
 headers sync/validation.=C2=A0 I don&#39;t know what software exists on th=
e network, but I imagine there are a lot of scripts out there for transacti=
on submission to the public p2p network, and in thinking about=C2=A0modifyi=
ng such a script to utilize package relay it seems=C2=A0like an unnecessary=
 added burden to first learn a node&#39;s tip before trying to relay a tran=
saction.</div><div><br></div><div>Could you explain again what the benefit =
of including the blockhash is?=C2=A0 It seems like it is just so that a nod=
e could prioritize transaction relay from peers with the same chain tip to =
maximize the likelihood of transaction acceptance, but in the common case t=
his 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 bandwi=
dth in one direction or the other.=C2=A0 If we solve the problem I brought =
up at the beginning (of de-duplicating package data across peers with a pac=
kage-wtxid-commitment in the announcement), I think this is just some waste=
d pkginfo bandwidth on a single-link, and not across links (as we could cac=
he validation failure for a package-hash to avoid re-requesting duplicate p=
kginfo1 messages).</div><div><br></div><div>Best,</div><div>Suhas</div><div=
><br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"g=
mail_attr">On Tue, Jun 7, 2022 at 1:57 PM Gloria Zhao via bitcoin-dev &lt;<=
a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">b=
itcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid=
 rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div>Hi Eric, aj, all,=
</div><div><br></div><div>Sorry for the delayed response. @aj I&#39;m inclu=
ding some paraphrased points from our offline discussion (thanks).<br></div=
><div><br></div><div>&gt; Other idea: what if you encode the parent txs as =
a short hash of the=20
wtxid (something like bip152 short ids? perhaps seeded per peer so=20
collisions will be different per peer?) and include that in the inv=20
announcement? Would that work to avoid a round trip almost all of the=20
time, while still giving you enough info to save bw by deduping parents?</d=
iv><div><span><br></span></div><div><span>&gt; As I suggested earlier, a pa=
ckage is fundamentally a compact block (or<br>
&gt; block) announcement without the header. Compact block (BIP152) announc=
ement<br>
&gt; is already well-defined and widely implemented...<br>
</span></div><div><span><br></span></div><div><span>&gt; Let us not reinven=
t the wheel and/or introduce accidental complexity. I see<br>
&gt; no reason why packaging is not simply BIP152 without the &#39;header&#=
39; field, an<br>
&gt; updated protocol version, and the following sort of changes to names</=
span></div><div><br></div><div>Interestingly, &quot;why not use BIP 152 sho=
rtids to save bandwidth?&quot; is by far the most common suggestion I hear =
(including offline feedback). Here&#39;s a full explanation:<br><br>BIP 152=
 shortens transaction hashes (32 bytes) to shortids (6 bytes) to save a sig=
nificant amount of network bandwidth, which is extremely important in block=
 relay. However, this comes at the expense of computational complexity. The=
re 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 shor=
tids for every transaction in their mempools every time they receive a pack=
age, we are creating a DoS vector. Unconfirmed transactions don&#39;t need =
PoW and, to have a live transaction relay network, we should expect nodes t=
o handle transactions at a high-ish rate (i.e. at least 1000s of times more=
 transactions than blocks). We can&#39;t pre-calculate or cache shortids fo=
r mempool transactions, since the SipHash key depends on the block hash and=
 a per-connection salt.<br><br>Additionally, shortid calculation is not des=
igned to prevent intentional individual collisions. If we were to use these=
 shortids to deduplicate transactions we&#39;ve supposedly already seen, we=
 may have a censorship vector. Again, these tradeoffs make sense for compac=
t block relay (see shortid section in BIP 152 [3]), but not package relay.<=
/div><div><br></div><div>TLDR: DoSy if we calculate shortids on every packa=
ge and censorship vector if we use shortids for deduplication.</div><div><b=
r></div><div>&gt; Given this message there is no reason =C2=A0<br>&gt; to s=
end a (potentially bogus) fee rate with every package. It can only be =C2=
=A0<br>&gt; validated by obtaining the full set of txs, and the only recour=
se is =C2=A0<br>&gt; dropping (etc.) the peer, as is the case with single t=
xs.<br><br></div><div>Yeah, I agree with this. Combined with the previous d=
iscussion with aj (i.e. we can&#39;t accurately communicate the incentive c=
ompatibility of a package without sending the full graph, and this whole da=
nce is to avoid downloading a few low-fee transactions in uncommon edge cas=
es), I&#39;ve realized I should remove the fee + weight information from pk=
ginfo. Yay for less complexity!<br></div><div><br></div><div>Also, this mig=
ht be pedantic, but I said something incorrect earlier and would like to co=
rrect myself:<br><br>&gt;&gt; In theory, yes, but maybe it was announced ea=
rlier (while our node was down?) or had dropped from our mempool or similar=
, either way we don&#39;t have those txs yet. =C2=A0<br><br>I said &quot;It=
&#39;s fine if they have Erlay, since a sender would know in advance that B=
 is missing and announce it as a package.&quot; But this isn&#39;t true sin=
ce we&#39;re only using reconciliation in place of flooding to announce tra=
nsactions as they arrive, not for rebroadcast, and we&#39;re not doing full=
 mempool set reconciliation. In any case, making sure a node receives the t=
ransactions announced when it was offline is not something we guarantee, no=
t an intended use case for package relay, and not worsened by this.</div><d=
iv><br></div><div>Thanks for your feedback!</div><div><br></div><div>Best,<=
br></div><div>Gloria</div><div><div><br></div><div>[1]: <a href=3D"https://=
github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#cmpctblock" target=
=3D"_blank">https://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#=
cmpctblock</a><br>[2]: <a href=3D"https://github.com/bitcoin/bitcoin/blob/m=
aster/src/blockencodings.cpp#L49" target=3D"_blank">https://github.com/bitc=
oin/bitcoin/blob/master/src/blockencodings.cpp#L49</a><br>[3]: <a href=3D"h=
ttps://github.com/bitcoin/bips/blob/master/bip-0152.mediawiki#short-transac=
tion-id-calculation" target=3D"_blank">https://github.com/bitcoin/bips/blob=
/master/bip-0152.mediawiki#short-transaction-id-calculation</a></div></div>=
</div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">=
On Thu, May 26, 2022 at 3:59 AM &lt;<a href=3D"mailto:eric@voskuil.org" tar=
get=3D"_blank">eric@voskuil.org</a>&gt; wrote:<br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">Given that packages have no header, the pa=
ckage requires identity in a<br>
BIP152 scheme. For example &#39;header&#39; and &#39;blockhash&#39; fields =
can be replaced<br>
with a Merkle root (e.g. &quot;identity&quot; field) for the package, uniqu=
ely<br>
identifying the partially-ordered set of txs. And use of &#39;getdata&#39; =
(to<br>
obtain a package by hash) can be eliminated (not a use case).<br>
<br>
e<br>
<br>
&gt; -----Original Message-----<br>
&gt; From: <a href=3D"mailto:eric@voskuil.org" target=3D"_blank">eric@vosku=
il.org</a> &lt;<a href=3D"mailto:eric@voskuil.org" target=3D"_blank">eric@v=
oskuil.org</a>&gt;<br>
&gt; Sent: Wednesday, May 25, 2022 1:52 PM<br>
&gt; To: &#39;Anthony Towns&#39; &lt;<a href=3D"mailto:aj@erisian.com.au" t=
arget=3D"_blank">aj@erisian.com.au</a>&gt;; &#39;Bitcoin Protocol Discussio=
n&#39;<br>
&gt; &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D=
"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&gt;; &#39;Gloria Zhao&#3=
9;<br>
&gt; &lt;<a href=3D"mailto:gloriajzhao@gmail.com" target=3D"_blank">gloriaj=
zhao@gmail.com</a>&gt;<br>
&gt; Subject: RE: [bitcoin-dev] Package Relay Proposal<br>
&gt; <br>
&gt; &gt; From: bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev-bounces@lists=
.linuxfoundation.org" target=3D"_blank">bitcoin-dev-bounces@lists.linuxfoun=
dation.org</a>&gt; On<br>
&gt; Behalf<br>
&gt; &gt; Of Anthony Towns via bitcoin-dev<br>
&gt; &gt; Sent: Wednesday, May 25, 2022 11:56 AM<br>
&gt; <br>
&gt; &gt; So the other thing is what happens if the peer announcing package=
s to us<br>
&gt; is<br>
&gt; &gt; dishonest?<br>
&gt; &gt;<br>
&gt; &gt; They announce pkg X, say X has parents A B C and the fee rate is<=
br>
garbage.<br>
&gt; But<br>
&gt; &gt; actually X has parent D and the fee rate is excellent. Do we requ=
est the<br>
&gt; &gt; package from another peer, or every peer, to double check? Otherw=
ise<br>
&gt; we&#39;re<br>
&gt; &gt; allowing the first peer we ask about a package to censor that tx =
from<br>
us?<br>
&gt; &gt;<br>
&gt; &gt; I think the fix for that is just to provide the fee and weight wh=
en<br>
&gt; announcing<br>
&gt; &gt; the package rather than only being asked for its info? Then if on=
e peer<br>
&gt; makes<br>
&gt; &gt; it sound like a good deal you ask for the parent txids from them,=
<br>
dedupe,<br>
&gt; &gt; request, and verify they were honest about the parents.<br>
&gt; <br>
&gt; Single tx broadcasts do not carry an advertised fee rate, however the&=
#39;<br>
&gt; feefilter&#39; message (BIP133) provides this distinction. This should=
 be<br>
&gt; interpreted as applicable to packages. Given this message there is no<=
br>
reason<br>
&gt; to send a (potentially bogus) fee rate with every package. It can only=
 be<br>
&gt; validated by obtaining the full set of txs, and the only recourse is<b=
r>
&gt; dropping (etc.) the peer, as is the case with single txs. Relying on t=
he<br>
&gt; existing message is simpler, more consistent, and more efficient.<br>
&gt; <br>
&gt; &gt; &gt;&gt; Is it plausible to add the graph in?<br>
&gt; &gt;<br>
&gt; &gt; Likewise, I think you&#39;d have to have the graph info from many=
 nodes if<br>
&gt; you&#39;re<br>
&gt; &gt; going to make decisions based on it and don&#39;t want hostile pe=
ers to be<br>
&gt; able to<br>
&gt; &gt; trick you into ignoring txs.<br>
&gt; &gt;<br>
&gt; &gt; Other idea: what if you encode the parent txs as a short hash of =
the<br>
wtxid<br>
&gt; &gt; (something like bip152 short ids? perhaps seeded per peer so coll=
isions<br>
&gt; will<br>
&gt; &gt; be different per peer?) and include that in the inv announcement?=
 Would<br>
&gt; &gt; that work to avoid a round trip almost all of the time, while sti=
ll<br>
giving<br>
&gt; you<br>
&gt; &gt; enough info to save bw by deduping parents?<br>
&gt; <br>
&gt; As I suggested earlier, a package is fundamentally a compact block (or=
<br>
&gt; block) announcement without the header. Compact block (BIP152)<br>
&gt; announcement<br>
&gt; is already well-defined and widely implemented. A node should never be=
<br>
&gt; required to retain an orphan, and BIP152 ensures this is not required.=
<br>
&gt; <br>
&gt; Once a validated set of txs within the package has been obtained with<=
br>
&gt; sufficient fee, a fee-optimal node would accept the largest subgraph o=
f<br>
the<br>
&gt; package that conforms to fee constraints and drop any peer that provid=
es a<br>
&gt; package for which the full graph does not.<br>
&gt; <br>
&gt; Let us not reinvent the wheel and/or introduce accidental complexity. =
I<br>
see<br>
&gt; no reason why packaging is not simply BIP152 without the &#39;header&#=
39; field,<br>
an<br>
&gt; updated protocol version, and the following sort of changes to names:<=
br>
&gt; <br>
&gt; sendpkg<br>
&gt; MSG_CMPCT_PKG<br>
&gt; cmpctpkg<br>
&gt; getpkgtxn<br>
&gt; pkgtxn<br>
&gt; <br>
&gt; &gt; &gt; For a maximum 25 transactions,<br>
&gt; &gt; &gt;23*24/2 =3D 276, seems like 36 bytes for a child-with-parents=
 package.<br>
&gt; &gt;<br>
&gt; &gt; If you&#39;re doing short ids that&#39;s maybe 25*4B=3D100B alrea=
dy, then the<br>
above<br>
&gt; is<br>
&gt; &gt; up to 36% overhead, I guess. Might be worth thinking more about, =
but<br>
&gt; maybe<br>
&gt; &gt; more interesting with ancestors than just parents.<br>
&gt; &gt;<br>
&gt; &gt; &gt;Also side note, since there are no size/count params,<br>
&gt; <br>
&gt; Size is restricted in the same manner as block and transaction broadca=
sts,<br>
&gt; by consensus. If the fee rate is sufficient there would be no reason t=
o<br>
&gt; preclude any valid size up to what can be mined in one block (packagin=
g<br>
&gt; across blocks is not economically rational under the assumption that o=
ne<br>
&gt; miner cannot expect to mine multiple blocks in a row). Count is<br>
incorporated<br>
&gt; into BIP152 as &#39;shortids_length&#39;.<br>
&gt; <br>
&gt; &gt; &gt; wondering if we<br>
&gt; &gt; &gt;should just have &quot;version&quot; in &quot;sendpackages&qu=
ot; be a bit field instead of<br>
&gt; &gt; &gt;sending a message for each version. 32 versions should be eno=
ugh right?<br>
&gt; <br>
&gt; Adding versioning to individual protocols is just a reflection of the<=
br>
&gt; insufficiency of the initial protocol versioning design, and that of t=
he<br>
&gt; various ad-hoc changes to it (including yet another approach in this<b=
r>
&gt; proposal) that have been introduced to compensate for it, though I&#39=
;ll<br>
&gt; address this in an independent post at some point.<br>
&gt; <br>
&gt; Best,<br>
&gt; e<br>
&gt; <br>
&gt; &gt; Maybe but a couple of messages per connection doesn&#39;t really =
seem worth<br>
&gt; &gt; arguing about?<br>
&gt; &gt;<br>
&gt; &gt; Cheers,<br>
&gt; &gt; aj<br>
&gt; &gt;<br>
&gt; &gt;<br>
&gt; &gt; --<br>
&gt; &gt; Sent from my phone.<br>
&gt; &gt; _______________________________________________<br>
&gt; &gt; bitcoin-dev mailing list<br>
&gt; &gt; <a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=
=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br>
&gt; &gt; <a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bit=
coin-dev" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundatio=
n.org/mailman/listinfo/bitcoin-dev</a><br>
<br>
<br>
</blockquote></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--000000000000632bb205e0f1c9fa--