Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9F2AEC002D for ; Tue, 24 May 2022 21:05:48 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id 78C20840C0 for ; Tue, 24 May 2022 21:05:48 +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 nrJGe6q-aMMU for ; Tue, 24 May 2022 21:05:47 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-yb1-xb33.google.com (mail-yb1-xb33.google.com [IPv6:2607:f8b0:4864:20::b33]) by smtp1.osuosl.org (Postfix) with ESMTPS id 7F3F2840DE for ; Tue, 24 May 2022 21:05:47 +0000 (UTC) Received: by mail-yb1-xb33.google.com with SMTP id y141so5579925ybe.13 for ; Tue, 24 May 2022 14:05:47 -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=AfTlkvb7Eet/FWk2a824XOqcWVOM4ngxQp+PKofhZhU=; b=bRvibcrmPyvA7kiFp9tf7UY+E8J7lcA6GPQ8a2gaJDqRfwpzaMnxbpGq6rHGAnR5Xu +ZBU+oYZv8ew0L+N6CiIGuWLdXL2zKMEakx6ONJP87icRP8vJa1Sc25+ph6RAKJKtNXj t9ewcCm9lWoOUzXJJXgwUobPQqKSlXGd/JIhX0dmm91f2VpOyU3cnf8D+poQP034rLkQ YY5m8aiQOwPgoNmvlHhQP01uKmUsCAKXf2GfJcfRzfzujauzExf3HneuS5JBKZa+46/s b4d7jksIpnL30fDP7nAlpZ5KCjHhV98qy+E/XvwZq95ELuVKs5TF8ovof2DP/E85E7Nx BYKQ== 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=AfTlkvb7Eet/FWk2a824XOqcWVOM4ngxQp+PKofhZhU=; b=eIq9t4voRNo2mpIQts+m0oj+sC8aBEWLbdnNM+772YF/ZOqyoSJJJ3mkP7Z2ki4ZB7 QH/1/GrZ7XV7tBVzCSruNRrmtdj3JudgGtCCHlDbCjROJF9PeU6h5iUX47oKR0Pg1w9f c4aH/V4buvE6SkXoW++ErX7Av+yq5ZK/UwFMHi2vyWJpOyADy2/WL6yHA1jREQ1tXR6W naumCWdCX//0MKr4sZMEqZwKZV0iGOcbvXdsUcDAenOVVz7trNXXYmRiE24GHnB6MQNO Mz0I7lBnjLJ679+wXbFafqeAt/Eylfc2j0DPRUe0al53rHTD6IyppMENcGMbymoh2Sm1 m/6A== X-Gm-Message-State: AOAM5335PVQ652HiEIknTNWzHXDbB1BiQno/MbyemK1Fi41j/msfy4V3 W5zq4nqR837ufXiaM6EOvaeFnGqTUALG9hl50wODfgG1tyE= X-Google-Smtp-Source: ABdhPJw49WgTLF5MoIqBXmgH3kUwGYu4Q3fuKJCWIdOx+Nzs5k+yTsAhZIvGfHASV7wiF1UqWcGn6Empf57FUvBZn3E= X-Received: by 2002:a25:928b:0:b0:64d:9560:ecbb with SMTP id y11-20020a25928b000000b0064d9560ecbbmr27537071ybl.551.1653426346352; Tue, 24 May 2022 14:05:46 -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> In-Reply-To: <2B3D1901-901C-4000-A2B9-F6857FCE2847@erisian.com.au> From: Gloria Zhao Date: Tue, 24 May 2022 14:05:35 -0700 Message-ID: To: Anthony Towns Content-Type: multipart/alternative; boundary="0000000000000967ea05dfc8522f" X-Mailman-Approved-At: Tue, 24 May 2022 23:21:24 +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: Tue, 24 May 2022 21:05:48 -0000 --0000000000000967ea05dfc8522f Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi aj, > If you've got (A,B,C,X) where B spends A and X spends A,B,C where X+C is below fee floor while A+B and A+B+C+X are above fee floor you have the problem though. 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 :=3D X.size, f :=3D X.fees, R :=3D [X] > * for P =3D P1..Pn: > * do I already have P? then skip to the next parent > * s +=3D P.size, f +=3D P.fees, R +=3D [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? Please lmk if you were imagining something different. I think I may be missing something. > Is it plausible to add the graph in? Fun to think about. Most basic design would be to represent {spends, doesn=E2=80=99t spend} for a previous transaction in the package as a bit. = Can think of it as a matrix where row i, column j tells you whether Tx j (directly) spends Tx i. But of course you can omit the last row, since the child spends all of them. And since topological ordering is a requirement, you only need as many bits as there are transactions preceding this one in the package. If you have up to 24 parents, you need 1 + 2 + ... + 23 bits to codify spending for the 2nd ... 24th parent. For a maximum 25 transactions, 23*24/2 =3D 276, seems like 36 bytes for a child-with-parents package. A fe= w more for tx-with-ancestors. Then you can split it up into sub-packages and everything. Still not sure if we really need to. 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? Best, Gloria On Tue, 24 May 2022 at 12:48 Anthony Towns wrote: > On 23 May 2022 9:13:43 pm GMT-04:00, Gloria Zhao > wrote: > >> If you're asking for the package for "D", would a response telling you= : > >> txid_D (500 sat, 100vB) > >> txid_A (0 sat, 100vB) > >> txid_B (2000 sat, 100 vB) > >> be better, in that case? Then the receiver can maybe do the logic > >> themselves to figure out that they already have A in their mempool > >> so it's fine, or not? > >Right, I also considered giving the fees and sizes of each transaction i= n > >the package in =E2=80=9Cpckginfo1=E2=80=9D. But I don=E2=80=99t think th= at information provides > >additional meaning unless you know the exact topology, i.e. also know if > >the parents have dependency relationships between them. For instance, in > >the {A, B, D} package there, even if you have the information listed, yo= ur > >decision should be different depending on whether B spends from A. > > I don't think that's true? We already know D is above our fee floor so if > B with A is also above the floor, we want them all, but also if B isn't > above the floor, but all of them combined are, then we also do? > > If you've got (A,B,C,X) where B spends A and X spends A,B,C where X+C is > below fee floor while A+B and A+B+C+X are above fee floor you have the > problem though. > > Is it plausible to add the graph in? > > Cheers, > aj > > > > -- > Sent from my phone. > --0000000000000967ea05dfc8522f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi aj,

>=20 If you've got (A,B,C,X) where B spends A and X spends A,B,C where X+C i= s below fee floor while A+B and A+B+C+X are above fee floor you have the=20 problem though.

To clarify, in this situation, I&#= 39;m imagining something like
A: 0 sat, 100vB
B: 15= 00 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? t= hen 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?
Please lmk if you were imagining someth= ing different. I think I may be missing something.

> Is it plausible to add t= he graph in?

Fun to think about. Most basic design would be to represent {spe= nds, doesn=E2=80=99t spend} for a previous transaction in the package as a = bit. Can think of it as a matrix where row i, column j tells you whether Tx= j (directly) spends Tx i.
But of course you can omi= t the last row, since the child spends all of them. And since topological o= rdering is a requirement, you only need as many bits as there are transacti= ons preceding this one in the package.
If you ha= ve up to 24 parents, you need 1 + 2 + ... + 23 bits to codify spending for = the 2nd ... 24th parent. For a maximum 25 transactions, 23*24/2 =3D 276, se= ems like 36 bytes for a child-with-parents package. A few more for tx-with-= ancestors.
Then you can split it up into sub-packages and eve= rything. Still not sure if we really need to.
Also side note, since there are no size/count params, wonderin= g if we should just have "version" in "sendpackages" be= a bit field instead of sending a message for each version. 32 versions sho= uld be enough right?

Best,
Gloria

On Tue, 24 May 2022 at 12:48 Anthony Towns <aj@erisian.com.au> wrote:
On 23 May 2022 9:13:43 = pm GMT-04:00, Gloria Zhao <gloriajzhao@gmail.com> wrote:
>> If you're asking for the package for "D", would a re= sponse telling you:
>>=C2=A0 =C2=A0txid_D (500 sat, 100vB)
>>=C2=A0 =C2=A0txid_A (0 sat, 100vB)
>>=C2=A0 =C2=A0txid_B (2000 sat, 100 vB)
>> be better, in that case? Then the receiver can maybe do the logic<= br> >> themselves to figure out that they already have A in their mempool=
>> so it's fine, or not?
>Right, I also considered giving the fees and sizes of each transaction = in
>the package in =E2=80=9Cpckginfo1=E2=80=9D. But I don=E2=80=99t think t= hat information provides
>additional meaning unless you know the exact topology, i.e. also know i= f
>the parents have dependency relationships between them. For instance, i= n
>the {A, B, D} package there, even if you have the information listed, y= our
>decision should be different depending on whether B spends from A.

I don't think that's true? We already know D is above our fee floor= so if B with A is also above the floor, we want them all, but also if B is= n't above the floor, but all of them combined are, then we also do?

If you've got (A,B,C,X) where B spends A and X spends A,B,C where X+C i= s below fee floor while A+B and A+B+C+X are above fee floor you have the pr= oblem though.

Is it plausible to add the graph in?

Cheers,
aj



--
Sent from my phone.
--0000000000000967ea05dfc8522f--