Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 0657EC002D for ; Tue, 24 May 2022 23:44:03 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id E996C409D0 for ; Tue, 24 May 2022 23:44:02 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.896 X-Spam-Level: X-Spam-Status: No, score=-1.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, MIME_QP_LONG_LINE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_NONE=0.001] autolearn=ham autolearn_force=no Authentication-Results: smtp4.osuosl.org (amavisd-new); dkim=pass (2048-bit key) header.d=voskuil-org.20210112.gappssmtp.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 XRCZpyWOdZSn for ; Tue, 24 May 2022 23:44:01 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 Received: from mail-pl1-x635.google.com (mail-pl1-x635.google.com [IPv6:2607:f8b0:4864:20::635]) by smtp4.osuosl.org (Postfix) with ESMTPS id 0D30E409BE for ; Tue, 24 May 2022 23:44:00 +0000 (UTC) Received: by mail-pl1-x635.google.com with SMTP id s14so17141630plk.8 for ; Tue, 24 May 2022 16:44:00 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=voskuil-org.20210112.gappssmtp.com; s=20210112; h=content-transfer-encoding:from:mime-version:subject:date:message-id :references:in-reply-to:to; bh=ErnUJrPl53CR1n1A29rzADy7UONz/qOQLR1oYqBt+UI=; b=btYOIo1YEl/tANffhEcg6F6MtZFhDyTiIQoVombFjMZlBjjHlttaWxc1/BN3KNjxpu jKiolI+htjOP2Hxd9+tCsfV8JOclvozrURshbKScf23GduHutjzFpzRNSa9jvjRto6cM S17A6yO5CRLscoRenrmb+FfnlkCKdnBU+UET5qJSeq4yDjMba2jKx9UHjDSE7rLJwhK1 GSD8uRW+e7llIFjQn8WEGEsDGPq9lYJuSZYJjhOlrEq/CgvRsvfZrq8Cjp7OkmQDgQBK gGUsbc47t0d6L8BCJMghVhVEf4XH8TJ9jpfvvOCAeqr4KAXs0LX/t0k/6VVltdRvVxVo 97cg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:content-transfer-encoding:from:mime-version :subject:date:message-id:references:in-reply-to:to; bh=ErnUJrPl53CR1n1A29rzADy7UONz/qOQLR1oYqBt+UI=; b=lZlBOCE2axUY9Af8M7civnpHb7AMh6MSxHuAhr6VB4ltzZj6JUOdvoFUUuPv2vInL0 jC0XmVnXeZQKMrA2ivURNwpx7E5EF6pbH1TsyCZC/oKQTrZZQit1X6kkWA4pdAStYpcL eUFlgOyIZqdF9Z9uIp6aMGWCdZdDYMAe1wSl0LwlBmI4i/cpw6gDj0Krr/WBYQ9pX0eD vwcL9iqatdGrlla11tbJt5eG6fOPB+eCtvIWPvgqkwZ+dm+VoL8tTIlov6ThixsJUqW4 u7YKPoqlj2eTaI46Dl/zmfBjwECrx+O6nYHYYK8uZNUtvQ4/EFpyXa39PUv+vUp05iOx 1aTA== X-Gm-Message-State: AOAM532VsEJP113zLV2mirxy01RP4eeABkBkBh2MTy0cytJq8fkQ51aM mDZsiGKsv3TNUfUS3Bu1ur5pQD1efM2E5Q== X-Google-Smtp-Source: ABdhPJy7g3x2VSWseK19At1ZQ2Ydt1ptB8GEhAF1spld74H2mYvJLISUGKt2Kxf5s16Tk2mQyWE0OA== X-Received: by 2002:a17:903:228e:b0:161:8632:2725 with SMTP id b14-20020a170903228e00b0016186322725mr29942252plh.126.1653435840288; Tue, 24 May 2022 16:44:00 -0700 (PDT) Received: from smtpclient.apple ([2600:380:4b20:edbf:d1a6:e63d:c395:792f]) by smtp.gmail.com with ESMTPSA id f18-20020aa79692000000b00512d13016d0sm9879109pfk.159.2022.05.24.16.43.58 (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 24 May 2022 16:43:59 -0700 (PDT) Content-Type: multipart/alternative; boundary=Apple-Mail-81C484C0-750A-415E-9859-1E25D2350D6A Content-Transfer-Encoding: 7bit From: Eric Voskuil Mime-Version: 1.0 (1.0) Date: Tue, 24 May 2022 16:43:57 -0700 Message-Id: <42B47B8A-947C-4B61-928C-F9F0CA684FDA@voskuil.org> References: In-Reply-To: To: Gloria Zhao , Bitcoin Protocol Discussion X-Mailer: iPhone Mail (19E258) 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 23:44:03 -0000 --Apple-Mail-81C484C0-750A-415E-9859-1E25D2350D6A Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable The set of txs is the graph. Anything else would just reproduce the tx graph= which must be traversed in any case. Similarly the set of txs is the fee, the sigops, the size, and the weight. T= he only information required by packaging is the association of the txs with= each other for the purpose of aggregate (vs. individual) net reward conside= ration. Since a package can only be reasonably considered for a single block, there i= s a natural effective limit on acceptable package size. Since any number of i= ndividual txs may be transmitted, and the size/weight/sigops of one tx is bo= unded only by block validity, there is no reason to put any other constraint= s on packages. A package is just a set of txs that may fit into a block and m= ay collectively be worth mining. A rational package is just a block or compa= ct block without the header. Making it any more than that is unnecessary com= plexity. If parts of a package satisfy profitability constraints, they will be accept= ed/mined and if other parts do not, they will be rejected. There=E2=80=99s n= o preventing this. The only pertinent feature missing in the p2p protocol is the ability to ass= ociate a set of txs for consideration, where the set (or subset) may satisfy= profitability constraints that would not be satisfied if the txs were consi= dered individually. e > On May 24, 2022, at 16:21, Gloria Zhao via bitcoin-dev wrote: >=20 > =EF=BB=BF > Hi aj, >=20 > > 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 prob= lem though. >=20 > 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 >=20 > 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 >=20 > 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 mis= sing something. >=20 > > Is it plausible to add the graph in? >=20 > 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 th= ink 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 the= m. And since topological ordering is a requirement, you only need as many bi= ts 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 spe= nding 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 few more for t= x-with-ancestors. > Then you can split it up into sub-packages and everything. Still not sure i= f we really need to. >=20 > Also side note, since there are no size/count params, wondering if we shou= ld just have "version" in "sendpackages" be a bit field instead of sending a= message for each version. 32 versions should be enough right? >=20 > Best, > Gloria >=20 >> On Tue, 24 May 2022 at 12:48 Anthony Towns wrote: >> On 23 May 2022 9:13:43 pm GMT-04:00, Gloria Zhao w= rote: >> >> 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. >>=20 >> 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 abo= ve the floor, but all of them combined are, then we also do? >>=20 >> If you've got (A,B,C,X) where B spends A and X spends A,B,C where X+C is b= elow fee floor while A+B and A+B+C+X are above fee floor you have the proble= m though. >>=20 >> Is it plausible to add the graph in? >>=20 >> Cheers, >> aj >>=20 >>=20 >>=20 >> --=20 >> Sent from my phone. > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev --Apple-Mail-81C484C0-750A-415E-9859-1E25D2350D6A Content-Type: text/html; charset=utf-8 Content-Transfer-Encoding: quoted-printable
The= set of txs is the graph. Anything else would just reproduce the tx graph wh= ich must be traversed in any case.

Similarly the set of txs is the fee, the sigops, the size, and the wei= ght. The only information required by packaging is the association of the tx= s with each other for the purpose of aggregate (vs. individual) net reward c= onsideration.

Since a packa= ge can only be reasonably considered for a single block, there is a natural e= ffective limit on acceptable package size. Since any number of individual tx= s may be transmitted, and the size/weight/sigops of one tx is bounded only b= y block validity, there is no reason to put any other constraints on package= s. A package is just a set of txs that may fit into a block and may collecti= vely be worth mining. A rational package is just a block or compact block wi= thout the header. Making it any more than that is unnecessary complexity.

If parts of a package satisfy= profitability constraints, they will be accepted/mined and if other parts d= o not, they will be rejected. There=E2=80=99s no preventing this.

The only pertinent feature missing in t= he p2p protocol is the ability to associate a set of txs for consideration, w= here the set (or subset) may satisfy profitability constraints that would no= t be satisfied if the txs were considered individually.

e

On May 24, 2022, at 16:21, Gloria Zhao via bitcoin-dev <bitcoin-de= v@lists.linuxfoundation.org> wrote:

=EF=BB=BF
= Hi aj,

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

To clarify, in this situation, I'm i= magining something like
A: 0 sat, 100vB
B: 1500 sat,= 100vB
C: 0 sat, 100vB
X: 500 sat, 100vB
f= eerate 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? th= en 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 sh= ould only take A+B.
But wouldn't A+B also be a package that was an= nounced for B?
Please lmk if you were imagining something differen= t. I think I may be missing something.

> Is it plausible to add the graph in?

Fun to t= hink 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 a= s 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 th= e 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 t= he package.
If you have up to 24 parents, you nee= d 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-w= ith-parents package. A few more for tx-with-ancestors.
Then yo= u can split it up into sub-packages and everything. Still not sure if we rea= lly need to.

Also side note, since= there are no size/count params, wondering if we should just have "version" i= n "sendpackages" be a bit field instead of sending a message for each versio= n. 32 versions should be enough right?

Best,
<= div>Gloria

On Tue, 24 May 2022 at 12:48 Anthony Towns <aj@erisian.com.au> w= rote:
On 23 May 20= 22 9:13:43 pm GMT-04:00, Gloria Zhao <gloriajzhao@gmail.com> wrote:
>> If you're asking for the package for "D", would a response telling y= ou:
>>   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<= br> >> 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 w= ith A is also above the floor, we want them all, but also if B isn't above t= he 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 bel= ow fee floor while A+B and A+B+C+X are above fee floor you have the problem t= hough.

Is it plausible to add the graph in?

Cheers,
aj



--
Sent from my phone.
_______________________________________________
bitcoi= n-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<= /span>
= --Apple-Mail-81C484C0-750A-415E-9859-1E25D2350D6A--