path: root/7f/a3cc0a909fd603bde53725de1902baa396e3a4

Return-Path: <jtimon@jtimon.cc>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id AD693C0001
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 29 May 2021 15:05:10 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 9ACCB4012E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 29 May 2021 15:05:10 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.92
X-Spam-Level: 
X-Spam-Status: No, score=-0.92 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 FROM_EXCESS_BASE64=0.979, HTML_MESSAGE=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001] autolearn=no autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=jtimon-cc.20150623.gappssmtp.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 pbAqnNtmMRud
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 29 May 2021 15:05:09 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-yb1-xb35.google.com (mail-yb1-xb35.google.com
 [IPv6:2607:f8b0:4864:20::b35])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 5B8A940114
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 29 May 2021 15:05:09 +0000 (UTC)
Received: by mail-yb1-xb35.google.com with SMTP id g38so9738904ybi.12
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 29 May 2021 08:05:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=jtimon-cc.20150623.gappssmtp.com; s=20150623;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc; bh=VjVj1w5+r5/SCDuTEBAJEC2rWqM3GsozEsIppwKLwyk=;
 b=WxIZb2kkg4cAsXqh0psdq+cZ4TmfA5JXI+qn2g20jhBPFwtNt5jqIepULOuh/ltJjS
 Xlx1rqIXE/DJ1rH6pMzTGGgpQpsu/KSAPy8oOqHxdCHs7+VIQQiJXEx0RptS3C1jC+tg
 giqsFeo87KRTkFxH3VCQFNOPxHWRwkbSF7JLe355II83Kc/O/FH6AKD+Z0k3q4ij0a1z
 qx26tKRoMCGiTEXQdqFXjFT1/djIZPZK399ctXLu2J7hk5MTDl/l3/v4IpQGNYh88vw0
 w/f+B9j7WY2D5CkHMgvQbbvIjm0GMbWIxfbH82EmRVofrgCZ1/RpVvqfoV7nsThjevi6
 CbOA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc;
 bh=VjVj1w5+r5/SCDuTEBAJEC2rWqM3GsozEsIppwKLwyk=;
 b=j9w+XYtEARAVwhpoy1ENSeHESnQor1fsurXVMdARv1IHS7/0ltD+EvwUh0Ie7MyAH7
 2X4GKgND3ELueg6lFURTTyGRZwPgig3QowUtF0j96hc76vFwjQ7FbMIKevcPQ/hos9O7
 5m7a/aSsQUYpCrMrocJrBu8BpGzpZjLnxeN+rtsU8YDb6PQI1YwRCpyuL3CLqQtSHx3A
 jJQLMt+xWrDi06NhNMV7jpKpsuRrLNRMHWVD/aqwGPipmFlZeD2UFB53LhcM5FYjRx3e
 e2TeyqXY2Cv4rNoCc5lbIXoOlt7fN0Uj/ziKGnZtvbPI+VxqNaGy26cJsk20MIUrBwzd
 kKZQ==
X-Gm-Message-State: AOAM533wUvxfI7UDfYOHfdwf7YU8YkvI92x2QIn9JNJfU66hf8cfxeDL
 IO8cugM3mC0R1ylRsxBoXala+dV1IO8pFc006c4wfw==
X-Google-Smtp-Source: ABdhPJyFoh+/MCumFUhM/kUURxvdZSwwdN/co+bFRdhO0esqXJSvpK/jxM4XF2dO/Zk6BViWrlDcGAlGUT4VMpmIH6Q=
X-Received: by 2002:a25:aa53:: with SMTP id s77mr3290996ybi.89.1622300708189; 
 Sat, 29 May 2021 08:05:08 -0700 (PDT)
MIME-Version: 1.0
References: <25ab1452-78a8-90f1-9b47-8de050d632d2@murch.one>
 <CALZpt+Fj4=EiWSR1j65-ucwiTnwgVc-gvLuwaye3zNyApbuxFA@mail.gmail.com>
In-Reply-To: <CALZpt+Fj4=EiWSR1j65-ucwiTnwgVc-gvLuwaye3zNyApbuxFA@mail.gmail.com>
From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= <jtimon@jtimon.cc>
Date: Sat, 29 May 2021 16:04:57 +0100
Message-ID: <CABm2gDpeWtge=OuPb2Ps15Og3-+Qk1wJ+cYfHnxoMxZF30h6Nw@mail.gmail.com>
To: Antoine Riard <antoine.riard@gmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000006e506c05c3795151"
Cc: clara@chaincode.com
Subject: Re: [bitcoin-dev] Improvement on Blockbuilding
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: Sat, 29 May 2021 15:05:10 -0000

--0000000000006e506c05c3795151
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Sounds really interesting, thanks. Making CPFP reliable would be very nice
in my opinion.

On Sat, May 29, 2021, 14:24 Antoine Riard via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Mark and Clara,
>
> Great research, thanks for it!
>
> Few questions out of mind after a first read.
>
> > This approach enables block building to consider Child Pays For Parent
> (CPFP) constellations.
>
> I think that's a really interesting point, it's likely that such
> transaction graphs with multiple disjunctive branches become far more
> regular in the future. One can think about OP_CTV's style
> congestion-tree, LN's splicing or chain of coinjoins. If this phenomenon
> happens, can you expect CSB feerate perf to improve ?
>
> > CSB is more complex and requires more computation
>
> Let's say a malicious miner identifies and connects to its competitors'
> mempools then starts to broadcast to them hard-to-traverse CPFP
> constellations. Doing so, this malicious miner would prevent them either
> from assembling block templates at all or slow down their assemblage
> computation enough to gain an advantage in fee collection. Following
> current mempools limits, it would be relevant to know by how much CSB mak=
es
> that kind of DoS possible/efficient.
>
> > From the point of view of global blockspace demand, if miners generally
> became DPFA-sensitive,
> it could encourage creation of additional transactions for the sole
> purpose of bumping stuck ancestors.
>
> As ASB's ancestor set and CSB's candidate set, a fee bidder, we'll have t=
o
> pay the feerate to cover the new transaction fields, high enough to catch
> up with the already-present feerate set ? Likely more feerate efficient t=
o
> RBF the first child, though you have to swallow the replacement feerate
> penalty (default 1 sat/vbyte iirc)
>
> Antoine
>
> Le mar. 25 mai 2021 =C3=A0 10:34, Murch via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :
>
>> Hi Bitcoin Devs,
>>
>> We are writing to share with you a suggested improvement to the current
>> bitcoin core block building algorithm. In short, currently Bitcoin Core
>> uses a straightforward greedy algorithm which evaluates each
>> transaction=E2=80=99s effective fee rate in the context of its unconfirm=
ed
>> ancestors. This overlooks situations in which multiple descendant
>> transactions could be grouped with their shared ancestors to form a more
>> attractive transaction set for block inclusion.
>>
>> For example, if we have 4 transactions A,B,C, and D, with fee rates and
>> weights as follows
>>
>> Tx Fee Weight
>> A    5    1
>> B   10    1
>> C   15    1
>> D   14    1
>>
>> And dependencies:
>> =E2=80=A2 B is a descendant of A
>> =E2=80=A2 C is a descendant of B
>> =E2=80=A2 D is a descendant of A
>> The current algorithm will consider {A,B,C} best which has an effective
>> fee rate of 10. Our suggested algorithm will also consider {A,B,C,D},
>> which has an effective fee rate of 11.
>>
>> Experimental data shows that our suggested algorithm did better on more
>> than 94% of blocks (99% for times of high congestion). We have also
>> compared the results to CBC and SAT Linear Programming solvers. The LP
>> solvers did slightly better, at the price of longer running times. Greg
>> Maxwell has also studied LP solvers in the past, and his results suggest
>> that better running times are possible.
>>
>> The full details are given in this document, and we are happy to hear
>> any comment, critic or suggestion!
>>
>> Best,
>> Mark and Clara
>>
>> Full details:
>>
>> https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#file-cand=
idate-set-based-block-building-md
>>
>> Research Code:
>> https://github.com/Xekyo/blockbuilding
>>
>> _______________________________________________
>> 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
>

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

<div dir=3D"auto">Sounds really interesting, thanks. Making CPFP reliable w=
ould be very nice in my opinion.</div><br><div class=3D"gmail_quote"><div d=
ir=3D"ltr" class=3D"gmail_attr">On Sat, May 29, 2021, 14:24 Antoine Riard v=
ia bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org"=
>bitcoin-dev@lists.linuxfoundation.org</a>&gt; wrote:<br></div><blockquote =
class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid=
;padding-left:1ex"><div dir=3D"ltr">Hi Mark and Clara,<br><br>Great researc=
h, thanks for it!<br><br>Few questions out of mind after a first read.<br><=
br>&gt; This approach enables block building to consider Child Pays For Par=
ent (CPFP) constellations.<br><br>I think that&#39;s a really interesting p=
oint, it&#39;s likely that such transaction graphs with multiple disjunctiv=
e branches become far more regular in the future. One can think about OP_CT=
V&#39;s style<br>congestion-tree, LN&#39;s splicing or chain of coinjoins. =
If this phenomenon happens, can you expect CSB feerate perf to improve ?<br=
><br>&gt; CSB is more complex and requires more computation <br><br>Let&#39=
;s say a malicious miner identifies and connects to its competitors&#39; me=
mpools then starts to broadcast to them hard-to-traverse CPFP constellation=
s. Doing so, this malicious miner would prevent them either from assembling=
 block templates at all or slow down their assemblage computation enough to=
 gain an advantage in fee collection. Following current mempools limits, it=
 would be relevant to know by how much CSB makes that kind of DoS possible/=
efficient.<br><br>&gt; From the point of view of global blockspace demand, =
if miners generally became DPFA-sensitive,<br>it could encourage creation o=
f additional transactions for the sole purpose of bumping stuck ancestors.<=
br><br>As ASB&#39;s ancestor set and CSB&#39;s candidate set, a fee bidder,=
 we&#39;ll have to pay the feerate to cover the new transaction fields, hig=
h enough to catch up with the already-present feerate set ? Likely more fee=
rate efficient to RBF the first child, though you have to swallow the repla=
cement feerate penalty (default 1 sat/vbyte iirc)<br><br>Antoine<br></div><=
br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=
=A0mar. 25 mai 2021 =C3=A0=C2=A010:34, Murch via bitcoin-dev &lt;<a href=3D=
"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank" rel=3D"nor=
eferrer">bitcoin-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9crit=C2=A0:<=
br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8e=
x;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Bitcoin Devs,=
<br>
<br>
We are writing to share with you a suggested improvement to the current<br>
bitcoin core block building algorithm. In short, currently Bitcoin Core<br>
uses a straightforward greedy algorithm which evaluates each<br>
transaction=E2=80=99s effective fee rate in the context of its unconfirmed<=
br>
ancestors. This overlooks situations in which multiple descendant<br>
transactions could be grouped with their shared ancestors to form a more<br=
>
attractive transaction set for block inclusion.<br>
<br>
For example, if we have 4 transactions A,B,C, and D, with fee rates and<br>
weights as follows<br>
<br>
Tx Fee Weight<br>
A=C2=A0 =C2=A0 5=C2=A0 =C2=A0 1<br>
B=C2=A0 =C2=A010=C2=A0 =C2=A0 1<br>
C=C2=A0 =C2=A015=C2=A0 =C2=A0 1<br>
D=C2=A0 =C2=A014=C2=A0 =C2=A0 1<br>
<br>
And dependencies:<br>
=E2=80=A2 B is a descendant of A<br>
=E2=80=A2 C is a descendant of B<br>
=E2=80=A2 D is a descendant of A<br>
The current algorithm will consider {A,B,C} best which has an effective<br>
fee rate of 10. Our suggested algorithm will also consider {A,B,C,D},<br>
which has an effective fee rate of 11.<br>
<br>
Experimental data shows that our suggested algorithm did better on more<br>
than 94% of blocks (99% for times of high congestion). We have also<br>
compared the results to CBC and SAT Linear Programming solvers. The LP<br>
solvers did slightly better, at the price of longer running times. Greg<br>
Maxwell has also studied LP solvers in the past, and his results suggest<br=
>
that better running times are possible.<br>
<br>
The full details are given in this document, and we are happy to hear<br>
any comment, critic or suggestion!<br>
<br>
Best,<br>
Mark and Clara<br>
<br>
Full details:<br>
<a href=3D"https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbfaf2#f=
ile-candidate-set-based-block-building-md" rel=3D"noreferrer noreferrer" ta=
rget=3D"_blank">https://gist.github.com/Xekyo/5cb413fe9f26dbce57abfd344ebbf=
af2#file-candidate-set-based-block-building-md</a><br>
<br>
Research Code:<br>
<a href=3D"https://github.com/Xekyo/blockbuilding" rel=3D"noreferrer norefe=
rrer" target=3D"_blank">https://github.com/Xekyo/blockbuilding</a><br>
<br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank" =
rel=3D"noreferrer">bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer noreferrer" target=3D"_blank">https://lists.linuxfoundati=
on.org/mailman/listinfo/bitcoin-dev</a><br>
</blockquote></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank" =
rel=3D"noreferrer">bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer noreferrer" target=3D"_blank">https://lists.linuxfoundati=
on.org/mailman/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000006e506c05c3795151--