Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133]) by lists.linuxfoundation.org (Postfix) with ESMTP id AD693C0001 for ; 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 ; 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 ; 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 ; Sat, 29 May 2021 15:05:09 +0000 (UTC) Received: by mail-yb1-xb35.google.com with SMTP id g38so9738904ybi.12 for ; 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> In-Reply-To: From: =?UTF-8?B?Sm9yZ2UgVGltw7Nu?= Date: Sat, 29 May 2021 16:04:57 +0100 Message-ID: To: Antoine Riard , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
Sounds really interesting, thanks. Making CPFP reliable w= ould be very nice in my opinion.

On Sat, May 29, 2021, 14:24 Antoine Riard v= ia bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
Hi Mark and Clara,

Great researc= h, thanks for it!

Few questions out of mind after a first read.
<= br>> This approach enables block building to consider Child Pays For Par= ent (CPFP) constellations.

I think that's a really interesting p= oint, it'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'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' 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.

> From the point of view of global blockspace demand, = if miners generally became DPFA-sensitive,
it could encourage creation o= f additional transactions for the sole purpose of bumping stuck ancestors.<= br>
As ASB's ancestor set and CSB's candidate set, a fee bidder,= we'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)

Antoine
<= br>
Le=C2= =A0mar. 25 mai 2021 =C3=A0=C2=A010:34, Murch via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit=C2=A0:<= br>
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 unconfirmed<= br> 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=C2=A0 =C2=A0 5=C2=A0 =C2=A0 1
B=C2=A0 =C2=A010=C2=A0 =C2=A0 1
C=C2=A0 =C2=A015=C2=A0 =C2=A0 1
D=C2=A0 =C2=A014=C2=A0 =C2=A0 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/5cb413fe9f26dbce57abfd344ebbf= af2#file-candidate-set-based-block-building-md

Research Code:
https://github.com/Xekyo/blockbuilding

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundati= on.org/mailman/listinfo/bitcoin-dev
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundati= on.org/mailman/listinfo/bitcoin-dev
--0000000000006e506c05c3795151--