Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id E5926C002D for ; Tue, 7 Jun 2022 17:44:59 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id C6E5B83EFD for ; Tue, 7 Jun 2022 17:44:59 +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: smtp1.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id u0IVkvL1B0mJ for ; Tue, 7 Jun 2022 17:44:58 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-yw1-x112a.google.com (mail-yw1-x112a.google.com [IPv6:2607:f8b0:4864:20::112a]) by smtp1.osuosl.org (Postfix) with ESMTPS id ECE6D83EF8 for ; Tue, 7 Jun 2022 17:44:57 +0000 (UTC) Received: by mail-yw1-x112a.google.com with SMTP id 00721157ae682-30ec2aa3b6cso183694677b3.11 for ; Tue, 07 Jun 2022 10:44:57 -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 :cc; bh=PSMw8L8ggHwygoNXLsDNhSUcCE1Z8VAOKjkBXW0X1uQ=; b=gOmAL2eW0waq2hoW8+vY4voJfOsLGoAf1Ds57t2HfOYyuHxfx7G1Vdf5I9yRlQpTPd qg+1+PgBErIhki8ikesQ/LId1kWk+bMLZNIjMmueXCPRAkWReNv0K1vlxFFizKtRVjac J/K2OdmIq2sOOe2Nezy/BEfgMt7o2jVc56lZfdopEVsK+mB9p3XL935ay8lmH0CduaAD ByqV2UMGT1uqcCtrMG5lhymuo35Fyl07vxXRUyZXZ/tvr5gCkHRBL/DgntOt1VGoyngY NPiah3VPSuwmXrWxBKveEO9D3rznGrqi5Qrpp8ZX2bm+yv3TlxquLRmg+hUJ7VBEkibZ 8Mgg== 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:cc; bh=PSMw8L8ggHwygoNXLsDNhSUcCE1Z8VAOKjkBXW0X1uQ=; b=WFu71mEpXav7xs+sgw5/xyX/byR+U4nh3hOJiKu23yXNQLeruoJHgZ4oLr7FiRBnuc NaHIvSvZcXlBAqsRwtPLpUuBeJurUtcvM1bZPxKq3EVKMNnyHFgvu7VHLinkor5y57Fo d0K4UlPyzMhqJZ64hq+ceDe2NhWuOV1KVHAswIr8ikZCZWrjf5BFG6gOHkah3TlNRuvY N13XASZixfEDjrB4reRqFMB2o4250Fe24StceXpP8Q6SoaqRJYG63xoyif9EZLS+u1/Z gOT0t9MUCsOrs7eA6/nXEaFRPVy/SVfT+igiw2Mw37JhPmpRFlAUI2oiBNSdnCcb4reX Xv4g== X-Gm-Message-State: AOAM533t10PC/vMXJ4gBB+3ABz1p/s3rpVwTnI6ylfLrBlMhj2WelNQt PmXVM3j6rhpN/SgTi4OVJguYqikvElqMPxJSqimeBlqInfv7WQ== X-Google-Smtp-Source: ABdhPJxO2eEFv4crXuIrwiLr2CHwVp5wale0CMFCyA5tzinJ7fAOJZNZ+O9L4vKZpulvl7zCVBNK6TEnevWTj6/K4gI= X-Received: by 2002:a81:248f:0:b0:2ea:fe10:ef5a with SMTP id k137-20020a81248f000000b002eafe10ef5amr33509531ywk.1.1654623896685; Tue, 07 Jun 2022 10:44:56 -0700 (PDT) MIME-Version: 1.0 References: <20220518003531.GA4402@erisian.com.au> <20220523213416.GA6151@erisian.com.au> <2B3D1901-901C-4000-A2B9-F6857FCE2847@erisian.com.au> <8FFE048D-854F-4D34-85DA-CE523C16EEB0@erisian.com.au> <017501d87079$4c08f9c0$e41aed40$@voskuil.org> <001201d870ac$8d7a06a0$a86e13e0$@voskuil.org> In-Reply-To: <001201d870ac$8d7a06a0$a86e13e0$@voskuil.org> From: Gloria Zhao Date: Tue, 7 Jun 2022 18:44:45 +0100 Message-ID: To: eric@voskuil.org Content-Type: multipart/alternative; boundary="00000000000099511705e0df25f1" X-Mailman-Approved-At: Tue, 07 Jun 2022 17:56:47 +0000 Cc: Bitcoin Protocol Discussion , Anthony Towns 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 07 Jun 2022 17:45:00 -0000 --00000000000099511705e0df25f1 Content-Type: text/plain; charset="UTF-8" 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 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 > > Sent: Wednesday, May 25, 2022 1:52 PM > > To: 'Anthony Towns' ; 'Bitcoin Protocol Discussion' > > ; 'Gloria Zhao' > > > > Subject: RE: [bitcoin-dev] Package Relay Proposal > > > > > From: bitcoin-dev 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 > > > --00000000000099511705e0df25f1 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Eric, aj, all,

Sorry for = the delayed response. @aj I'm including some paraphrased points from ou= r offline discussion (thanks).

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

> As I suggested earlier, a package is fundamentally a compact bloc= k (or
> block) announcement without the header. Compact block (BIP152) announc= ement
> is already well-defined and widely implemented...

> Let us not reinvent the wheel and/or introduce accident= al complexity. I see
> no reason why packaging is not simply BIP152 without the 'header&#= 39; field, an
> updated protocol version, and the following sort of changes to names

Interestingly, "why not use BIP 152 sho= rtids 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 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'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't pre-calculate or cache shortids fo= r mempool transactions, since the SipHash key depends on the block hash and= a per-connection salt.

Additionally, shortid calculation is not des= igned 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 compac= t block relay (see shortid section in BIP 152 [3]), but not package relay.<= /div>

TLDR: DoSy if we calculate shortids on every packa= ge and censorship vector if we use shortids for deduplication.
> Given this message there is no reason =C2=A0
> to s= end a (potentially bogus) fee rate with every package. It can only be =C2= =A0
> validated by obtaining the full set of txs, and the only recour= se is =C2=A0
> dropping (etc.) the peer, as is the case with single t= xs.

Yeah, I agree with this. Combined with the previous d= iscussion with aj (i.e. we can'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've realized I should remove the fee + weight information from pk= ginfo. Yay for less complexity!

Also, this mig= ht be pedantic, but I said something incorrect earlier and would like to co= rrect myself:

>> 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't have those txs yet. =C2=A0

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 sin= ce we're only using reconciliation in place of flooding to announce tra= nsactions as they arrive, not for rebroadcast, and we'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.

Thanks for your feedback!

Best,<= br>
Gloria

On Thu, May 26, 2022 at 3:59 AM <eric@voskuil.org> wrote:
Given that packages have no header, the pa= ckage 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, uniqu= ely
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@vosku= il.org <eric@v= oskuil.org>
> Sent: Wednesday, May 25, 2022 1:52 PM
> To: 'Anthony Towns' <aj@erisian.com.au>; 'Bitcoin Protocol Discussio= n'
> <bitcoin-dev@lists.linuxfoundation.org>; 'Gloria Zhao= 9;
> <gloriaj= zhao@gmail.com>
> Subject: RE: [bitcoin-dev] Package Relay Proposal
>
> > From: bitcoin-dev <bitcoin-dev-bounces@lists.linuxfoun= dation.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 package= s to us
> is
> > dishonest?
> >
> > They announce pkg X, say X has parents A B C and the fee rate is<= br> garbage.
> But
> > actually X has parent D and the fee rate is excellent. Do we requ= est the
> > package from another peer, or every peer, to double check? Otherw= ise
> 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 wh= en
> announcing
> > the package rather than only being asked for its info? Then if on= e 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&= #39;
> feefilter' message (BIP133) provides this distinction. This should= be
> interpreted as applicable to packages. Given this message there is no<= br> 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 t= he
> 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 pe= ers 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 coll= isions
> 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 sti= ll
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<= br> > sufficient fee, a fee-optimal node would accept the largest subgraph o= f
the
> package that conforms to fee constraints and drop any peer that provid= es 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&#= 39; field,
an
> updated protocol version, and the following sort of changes to names:<= br> >
> sendpkg
> MSG_CMPCT_PKG
> cmpctpkg
> getpkgtxn
> pkgtxn
>
> > > For a maximum 25 transactions,
> > >23*24/2 =3D 276, seems like 36 bytes for a child-with-parents= package.
> >
> > If you're doing short ids that's maybe 25*4B=3D100B alrea= dy, 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 broadca= sts,
> by consensus. If the fee rate is sufficient there would be no reason t= o
> preclude any valid size up to what can be mined in one block (packagin= g
> across blocks is not economically rational under the assumption that o= ne
> 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&qu= ot; be a bit field instead of
> > >sending a message for each version. 32 versions should be eno= ugh right?
>
> Adding versioning to individual protocols is just a reflection of the<= br> > insufficiency of the initial protocol versioning design, and that of t= he
> 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.linuxfoundatio= n.org/mailman/listinfo/bitcoin-dev


--00000000000099511705e0df25f1--