Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 2F381C002D for ; Sat, 28 May 2022 01:54:28 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 16D3040AC3 for ; Sat, 28 May 2022 01:54:28 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.099 X-Spam-Level: X-Spam-Status: No, score=-0.099 tagged_above=-999 required=5 tests=[AC_HTML_NONSENSE_TAGS=1.999, 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=no autolearn_force=no Authentication-Results: smtp2.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com 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 ubqDTLEGpUh2 for ; Sat, 28 May 2022 01:54:27 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-yw1-x112e.google.com (mail-yw1-x112e.google.com [IPv6:2607:f8b0:4864:20::112e]) by smtp2.osuosl.org (Postfix) with ESMTPS id DF608400E5 for ; Sat, 28 May 2022 01:54:26 +0000 (UTC) Received: by mail-yw1-x112e.google.com with SMTP id 00721157ae682-306b5b452b1so31124337b3.1 for ; Fri, 27 May 2022 18:54:26 -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=npIr78k4lb6fB0S/w4Lo8OBjzxJoFmqLNJn5qDoMiow=; b=QAxnPuaw9Je0H82nkKG82QO49MBq2Ypf39BNSij/4z8r5zsgFg7B0+Hbelj5bOTDm/ RdG12vmdne+JoShjA3nhcNTjpVNleMb3aWkvr1CrStzGf2+N87WTNJ89P8y9GOPu1gJx 0LufL6BaujnTHRq27cdjxp2kFk42O3Q8EnV6USXLXgZ2GzkVemZ0treON6i3J+mspbHf /jCFUVxYGlo9GzCnEOW1EYivKqhZ/TrAef8Bmjg20oHvI4UWioAfOgfs8FI3gwpWIb7z sg10LVDEpIIx/j8YHKcLfv5QBkLfBv7rQgHmX7mtoCAWrDLUjRuaICNXX+lR9+RI5bK5 UO6w== 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=npIr78k4lb6fB0S/w4Lo8OBjzxJoFmqLNJn5qDoMiow=; b=NsltYpDYvlYTXbFgdiuHM2fphm8hiSdGIyr8TImpnH5c5nUfMCeLd63hs2cEHotOyu e2UnVopvcdTKeCjrvayuFgcazgClN7Wrfq4olFsUPR04YjGTpeu8iZVpJ6FNJf9wjkqw slw5k85rmXz/7iH8NqkOQq+MrDdG6IN0y0w0fMC0F3h59kq3a3HwR1ktJ4jAmgccWJ2W HcT5XVSc9JIUVR2SibBFaFyScfBgdTJXspJW09WKY/2DpGBdB1iL4S/f3QfJlpmDbX2l 1qHMvClIcijpi9AWMwDaEIkR6JHZeWA3eTA0xgzzXsdk7GRGJZJBhRHrFvl019g4beY4 Rq5A== X-Gm-Message-State: AOAM531n19pjfP+R7NA9JcnbqDpvc/6V4J42BtGdnPSpmfyBEKEoNCcL YpnRAGTzk3kaXnRK/W6SEmHKYEWUNl/MYVQ0wqVU6K+E8Q8= X-Google-Smtp-Source: ABdhPJyAOV/hgFWOnA4LAu+qEb95WrR/fFawuw/u3FwxHtggouYXxxHMhN2wnUYvNTigGbhILAM/0gwep6S1IpeSv5M= X-Received: by 2002:a81:248f:0:b0:2ea:fe10:ef5a with SMTP id k137-20020a81248f000000b002eafe10ef5amr47568381ywk.1.1653702865022; Fri, 27 May 2022 18:54:25 -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> In-Reply-To: <8FFE048D-854F-4D34-85DA-CE523C16EEB0@erisian.com.au> From: Gloria Zhao Date: Fri, 27 May 2022 18:54:13 -0700 Message-ID: To: Anthony Towns Content-Type: multipart/alternative; boundary="000000000000d5746605e008b346" X-Mailman-Approved-At: Sat, 28 May 2022 08:04:31 +0000 Cc: Bitcoin Protocol Discussion 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: Sat, 28 May 2022 01:54:28 -0000 --000000000000d5746605e008b346 Content-Type: text/plain; charset="UTF-8" Hi aj, answering slightly out of order: > 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? Yes, providing false information shouldn't be worse than not announcing the package at all, otherwise we have a censorship vector. In general, the request logic should not let one peer prevent us from requesting a similar announcement from another peer. Yes I was indeed expecting that we would ask for package info from everyone who announces it until it accepts the package or has full information. I can see that it's a fair bit of messages (request pckginfo, oh it's low fee, request pckginfo from somebody else), but we also need to track announcements / potentially go through the same circle to handle "notfound"s, right? In normal running, the fee filter should stop a bunch of honest nodes from telling us packages that are low fee. > 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. > 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. I don't think providing more information up front can ever sufficiently resolve the censorship issue. If we want to prevent any one peer from being able to censor requests to other peers, we need to store all announcements and be prepared to request from everybody. Would it be better if we just took out the fee information and had "pckginfo" only consist of transaction ids? Sender tries its best to apply the fee filter? Presumably you have a txInventoryKnown of your peer based on what they've announced to you... just take the ancestor set of a transaction, subtract what they already have, and apply the fee filter to that? Or some kind of algorithm that ensures we don't underestimate? If it's imperfect, the worst case is the receiver downloads a few transactions and rejects them. Given that our goal is just to avoid this case, perhaps opting for simplicity is better than adding a topology graph serialization/deserialization + feerate assessment algorithm on top of this protocol...? >>We'd erroneously ask for A+B+C+X, but really we should only take A+B. >>But wouldn't A+B also be a package that was announced for B? > 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. Hm. It's fine if they have Erlay, since a sender would know in advance that B is missing and announce it as a package. A potential tack-on solution would be to request package information whenever you have a "low fee" error on a parent and "missing inputs" on a child. Or we solve it at the validation level - instead of submitting each tx individually, we submit each ancestor subset. Do you think any of these is sufficient? At least the package properly propagates across nodes which are online when it is broadcasted... Best, Gloria On Wed, May 25, 2022 at 11:55 AM Anthony Towns wrote: > On 24 May 2022 5:05:35 pm GMT-04:00, Gloria Zhao via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >To clarify, in this situation, I'm imagining something like > >A: 0 sat, 100vB > >B: 1500 sat, 100vB > >C: 0 sat, 100vB > >X: 500 sat, 100vB > >feerate floor is 3sat/vB > > > >With the algo: > >> * is X alone above my fee rate? no, then forget it > >> * otherwise, s := X.size, f := X.fees, R := [X] > >> * for P = P1..Pn: > >> * do I already have P? then skip to the next parent > >> * s += P.size, f += P.fees, R += [P] > >> * if f/s above my fee rate floor? if so, request all the txs in R > > > >We'd erroneously ask for A+B+C+X, but really we should only take A+B. > >But wouldn't A+B also be a package that was announced for B? > > 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. > > >Please lmk if you were imagining something different. I think I may be > >missing something. > > That's what I was thinking, yes. > > 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. > > >> 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? > > > > 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, 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? > > Maybe but a couple of messages per connection doesn't really seem worth > arguing about? > > Cheers, > aj > > > -- > Sent from my phone. > --000000000000d5746605e008b346 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi aj, answering slightly out of order:

> what happens if the peer announcing packages to us is d= ishonest?
> They announce pkg X, say X has parents A B C and the fee rate is=20 garbage. But actually X has parent D and the fee rate is excellent. Do=20 we request the package from another peer, or every peer, to double=20 check? Otherwise we're allowing the first peer we ask about a package t= o censor that tx from us?

Yes, providing false informat= ion shouldn't be worse than not announcing the package at all, otherwise we have a censorship vector. In general, the= request logic should not let one peer prevent us f= rom requesting a=20 similar announcement from another peer.<= /span>
Yes I was indeed expecting that w= e would ask for package info from everyone who announces it until it accept= s the package or has full information.
= I can see that it's a fair bit of messages (request pckginf= o, oh it's low fee, request pckginfo from somebody else), but we also n= eed to track announcements / potentially go through the same circle to hand= le "notfound"s, right?
In normal running, the fee filter should stop a bunch o= f honest nodes from telling us packages that are low fee.
=

<= /span>
> I think the fix for that is just to provide the fee and = weight when=20 announcing the package rather than only being asked for its info? Then=20 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=20 parents.
> Likewise, I think = you'd have to have the graph info from many nodes if=20 you're going to make decisions based on it and don't want hostile p= eers=20 to be able to trick you into ignoring txs.

<= span>
I don't think providi= ng more information up front can ever sufficiently resolve the censorship i= ssue. If we want to prevent any one peer from being able to censor requests= to other peers, we need to store all announcements and be prepared to requ= est from everybody.

Would it be better if we just = took out the fee information and had "pckginfo" only consist of t= ransaction ids? Sender tries its best to apply the fee filter? Presumably y= ou have a txInventoryKnown of your peer based on what they've announced= to you... just take the ancestor set of a transaction, subtract what they = already have, and apply the fee filter to that? Or some kind of algorithm t= hat ensures we don't underestimate? If it's imperfect, the worst ca= se is the receiver downloads a few transactions and rejects them. Given tha= t our goal is just to avoid this case, perhaps opting for simplicity is bet= ter than adding a topology graph serialization/deserialization + feerate as= sessment algorithm on top of this protocol...?

>>We'd erroneously ask for A+B+C+X= , but really we should only take A+B.
=
>>But wouldn't A+B also be a package that was announced for B?
> In theory, yes, but maybe it was announced earlier (while our node was= =20 down?) or had dropped from our mempool or similar, either way we don't= =20 have those txs yet.

= Hm. It's fine if they have Erlay, since a sender would know in ad= vance that B is missing and announce it as a package. A potential tack-on s= olution would be to request package information whenever you have a "l= ow fee" error on a parent and "missing inputs" on a child. O= r we solve it at the validation level - instead of submitting each tx indiv= idually, we submit each ancestor subset. Do you think any of these is suffi= cient? At least the package properly=20 propagates across nodes which are online when it is broadcasted... <= /span>

Best,
Gloria

On Wed, May 25, 2022 at 11:55 AM Anthony Towns <aj@erisian.com.au> wrote:
<= blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l= eft:1px solid rgb(204,204,204);padding-left:1ex">On 24 May 2022 5:05:35 pm = GMT-04:00, Gloria Zhao via bitcoin-dev <bitcoin-dev@lists.linuxfoundatio= n.org> wrote:
>To clarify, in this situation, I'm imagining something like
>A: 0 sat, 100vB
>B: 1500 sat, 100vB
>C: 0 sat, 100vB
>X: 500 sat, 100vB
>feerate floor is 3sat/vB
>
>With the algo:
>>=C2=A0 * is X alone above my fee rate? no, then forget it
>>=C2=A0 * otherwise, s :=3D X.size, f :=3D X.fees, R :=3D [X]
>>=C2=A0 * for P =3D P1..Pn:
>>=C2=A0 =C2=A0* do I already have P? then skip to the next parent >>=C2=A0 =C2=A0* s +=3D P.size, f +=3D P.fees, R +=3D [P]
>>=C2=A0 * if f/s above my fee rate floor? if so, request all the txs= in R
>
>We'd erroneously ask for A+B+C+X, but really we should only take A+= B.
>But wouldn't A+B also be a package that was announced for B?

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.

>Please lmk if you were imagining something different. I think I may be<= br> >missing something.

That's what I was thinking, yes.

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. B= ut 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= 9;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 announc= ing 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, de= dupe, request, and verify they were honest about the parents.

>> 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 p= eers 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 wil= l be different per peer?) and include that in the inv announcement? Would t= hat work to avoid a round trip almost all of the time, while still giving y= ou enough info to save bw by deduping parents?


> For a maximum 25 transactions,
>23*24/2 =3D 276, seems like 36 bytes for a child-with-parents package.<= br>
If you're doing short ids that's maybe 25*4B=3D100B already, then t= he 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, wondering if we >should just have "version" in "sendpackages" be a b= it field instead of
>sending a message for each version. 32 versions should be enough right?=

Maybe but a couple of messages per connection doesn't really seem worth= arguing about?

Cheers,
aj


--
Sent from my phone.
--000000000000d5746605e008b346--