From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id A8B33C002D for ; Tue, 27 Sep 2022 09:29:33 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 753146101F for ; Tue, 27 Sep 2022 09:29:33 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 753146101F Authentication-Results: smtp3.osuosl.org; dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com header.a=rsa-sha256 header.s=protonmail3 header.b=l0qrCTZh X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.101 X-Spam-Level: X-Spam-Status: No, score=-2.101 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, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id tDgAaOXBBKSj for ; Tue, 27 Sep 2022 09:29:30 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 73A1B60D4B Received: from mail-40132.protonmail.ch (mail-40132.protonmail.ch [185.70.40.132]) by smtp3.osuosl.org (Postfix) with ESMTPS id 73A1B60D4B for ; Tue, 27 Sep 2022 09:29:29 +0000 (UTC) Date: Tue, 27 Sep 2022 09:29:19 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1664270965; x=1664530165; bh=I7AjRxUWSqg2AUnGW2hIFvGqiekxk7qVSwsaEiurvvQ=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID; b=l0qrCTZhc6ussXmTJPjHCd3DhXm1igOAE6Att6E6SPk+HJckI2KFYcrLI9VPgbnMQ PTbELb7JGjVq2QpcmzVnuhnGXcRVd4ns6iDFvKgqkcyqXnxK9EZIuv4S00NRDUrGWO VTAGcjmNpnG0vmaxk45lj57+AbCwTJulAD7SJw8wmka1rLAXiXzY1nnjdnfuM5MdoY 1XK0Elrk982aopNZcMzKzvuI6njB8Og/WXoWFQw78vk5qw8wlFeQIG/2iGOncfUKvz Z1z1+nBVH4096R4w5MjCmzFzs/Oz4IWa4DWFgxGrvl+gI11EVRfj4J9/W4gWCvbErr 60KQLh1taGHmw== To: eric@voskuil.org From: alicexbt Message-ID: <9H5VUe-D8MlzIgitIRj0Z_yT_dj5RYwAcp4HJHdXcseZB3Hl1Wxl1_vpcmPYCMaolnYA6R18MC3qIsQgkxBeew3s5GLirhAMaNiEq5LOm4U=@protonmail.com> In-Reply-To: <00cb01d8d1ed$b0191dc0$104b5940$@voskuil.org> References: <005e01d87b89$3d99df60$b8cd9e20$@voskuil.org> <00cb01d8d1ed$b0191dc0$104b5940$@voskuil.org> Feedback-ID: 40602938:user:proton MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Tue, 27 Sep 2022 09:43:44 +0000 Cc: 'Bitcoin Protocol Discussion' Subject: Re: [bitcoin-dev] Packaged Transaction Relay 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, 27 Sep 2022 09:29:33 -0000 Hi Eric, > If by "range" you mean a connected tx subgraph, I don't see why not. But = note that nodes only operate over signed txs. PSBT is a wallet workflow. Matt Corallo mentioned that pre-signed transactions created with low fee ra= te become an issue when they are broadcasted after a long time and there is= a high demand for block space at that moment. Example:=20 Bob created PSBT1 in a multi party contract with fee rate 5 sat/vbyte howev= er its taking hours/days to confirm the transaction with such low fee rate. Carol created PSBT1 (5 sat/vbyte), PSBT2 (10 sat/vbyte) and PSBT3 (20 sat/v= byte) for spending same inputs. She broadcasted PSBT3 which got confirmed i= n a few minutes.=20 > Always. Only signed transactions are accepted. But assuming you are refer= ring to a transaction that has been produced by a pre-signing workflow, I'm= not sure how this would be distinct from any other tx. `minfeefilter` for all peers of my node was 0.00001000 at the time of writi= ng this email. I am assuming nobody creates pre-signed transaction with fee= rate below 1 sat/vbyte. How often does it happen that `minfeefilter` is ab= ove this default value? > I'm not sure I follow this, maybe you could reword it. But it seems that = you are saying that CPFP fee-bumping is a problem scenario and the complexi= ty of the proposed solutions are not justified by such scenarios. Sorry that sentence was confusing. Yes complexity isn't justified for CPFP = fee-bumping txs below minimum fee rate. > There are many node implementations used presently. And of course these a= re protocol proposals, which presumes more than one implementation. Yes, a few implementations exist (knots, libbitcoin, btcd, bcoin etc.) howe= ver they aren't used by lot of nodes. Based on this [chart][1] 98% nodes us= e bitcoin core. Lot of bitcoin protocol proposals are influenced by bitcoin= core contributors and things could be different if even 30% nodes used oth= er implementations. > I don't consider this relevant to any protocol considerations. Miners sho= uld always be expected to select the most optimal set of txs available in t= he time available to do so. Agree, miners should be expected to select most optimal set of txs. However= , according to one [comment][2] by Pieter Wuille, miners could affect the s= ecurity of some bitcoin projects with MEV. > Over time we are likely to see that the only policies that remain in wide= spread application are those that are necessary for DOS protection (fee rat= e), as other restrictions are not economically rational and cannot be enfor= ced. We've seen recent debate regarding dust policy, and op_return policy. = "non-standard" txs are perfectly valid but get stuck very easily. I'll reit= erate, any policy beyond what is published via the protocol will cause the = above problems. I completely agree with this. [1]: https://luke.dashjr.org/programs/bitcoin/files/charts/software.html [2]: https://bitcoin.stackexchange.com/questions/107787/front-running-in-bi= tcoin#comment123441_107796 /dev/fd0 Sent with Proton Mail secure email. ------- Original Message ------- On Tuesday, September 27th, 2022 at 2:49 AM, wrote: > > Hi Eric, > >=20 > > This email wasn't answered by anyone on mailing list however I did some > > research about packages yesterday including this email and below are my > > observations, questions etc. >=20 >=20 > Hello, thanks for the reply. >=20 > > > The sole objective, as expressed in the OP proposal, is to: > > >=20 > > > "Propagate transactions that are incentive-compatible to mine, even i= f they > > > don't meet minimum feerate alone." > >=20 > > According to bitcoinops: Without package relay, it=E2=80=99s not possib= le to > > effectively CPFP fee bump a transaction that=E2=80=99s below the minimu= m feerate > > nodes accept. >=20 >=20 > Yes, the problem statement is not in question, just the mechanism of reso= lution. The problem of stuck txs arises from minimum fee rate policy, which= is a necessary DOS guard. >=20 > A secondary issue is that of orphan relay. As a node must allow receipt o= f orphans, it has no means to differentiate a flood of unconfirmable txs fr= om those that are confirmable. >=20 > > Matt Corallo's thoughts in a bitcoin core issue: > >=20 > > "Matt Corallo recently wrote about an example on the bitcoin-dev mailin= g list > > involving lightning transactions, where pre-signed transactions might b= e > > broadcast to the blockchain long after they were generated, and thus no= t > > have been created with a fee that is sufficient to be confirmed quickly= (or > > even be accepted to node mempools). In such situations, channel > > participants may need to use chained transactions (CPFP) in order to in= crease > > the confirmation speed of such transactions, and that implies we may ne= ed > > to introduce a mechanism for those parent transactions to be relayed al= ong > > with their higher feerate children, even if the parent transaction woul= d be > > rejected by itself." >=20 >=20 > While this is a valid scenario, the problems directly affect Bitcoin. Tho= se problems propagate to layers, but are not unique to layering. >=20 > > 1)Is it possible to have multiple pre-signed transactions with differen= t fee > > rates in a range? Example: PSBT1: 5 sat/vbyte, PSBT2: 10 sat/vbyte, PSB= T3: 20 > > sat/vbyte and PSBT4: 100 sat/vbyte >=20 >=20 > If by "range" you mean a connected tx subgraph, I don't see why not. But = note that nodes only operate over signed txs. PSBT is a wallet workflow. >=20 > > 2)How would covenants affect this problem? >=20 >=20 > There are a good number of covenant proposals, though I assume they are a= ll implemented within script. If a tx is confirmable and satisfies fee rate= (for DOS protection), it is relayable. Covenants affect confirmability and= should not have any unique impact on relay. >=20 > > 3)How often does it happen that a pre-signed tx gets rejected by nodes > > because it did not meet the minimum fee rate? Is it predictable and cou= ld be > > managed in a different way? >=20 >=20 > Always. Only signed transactions are accepted. But assuming you are refer= ring to a transaction that has been produced by a pre-signing workflow, I'm= not sure how this would be distinct from any other tx. >=20 > > After reading several links related to packages and bitcoin core pull r= equests, > > I found it anti-bitcoin to introduce so much complexity because its not > > possible to CPFP fee bump a tx below minimum fee rate. >=20 >=20 > I'm not sure I follow this, maybe you could reword it. But it seems that = you are saying that CPFP fee-bumping is a problem scenario and the complexi= ty of the proposed solutions are not justified by such scenarios. >=20 > I would say that the problem is real, and that the least complex option i= s generally preferred. There are always tradeoffs, and balancing these is p= art of protocol development. But as a rule, complexity within a protocol (c= ommunication) is to be avoided where possible. >=20 > > > Furthermore any tx that is "stuck" can be freed by simply sending ano= ther > > > tx. The nodes at which the tx has become stuck will just package it u= p and > > > relay it to peers. In other words, there is no impact on wallet imple= mentation > > > apart from raising the aggregate fee using a descendant transaction. > >=20 > > It is easy to send another tx if there is only one user involved howeve= r > > packages are trying to fix issues in which multiple users and transacti= on pre- > > signed between them are involved. So, it will be difficult to coordinat= e and > > create new pre-signed transactions in some cases although it is possibl= e for > > some use cases. >=20 >=20 > Given that nodes do not deal in presigned txs, this coordination difficul= ty could not be increased in any scenario. >=20 > A node produces sets of txs ("packages") dynamically to satisfy its peer'= s feerate. When a wallet broadcasts a tx/package to a node, it is operating= as a peer on the p2p network. The wallet simply implements the same dynami= c packaging algorithm as any peer - because it is a peer. >=20 > > > This is barely a protocol change - it's primarily implementation. All= that > > > should be required is an additional INV element type, such as > > > MSG_TX_PACKAGE. > >=20 > > > * All elements of MSG_TX_PACKAGE in one INV message MUST to be of > > > the same package. > > > * A package MUST must define a set that can be mined into one block > > > (size/sigops constraint). > > > * A package SHOULD not contain confirmed txs (a race may cause this). > > > * A package MUST minimally satisfy peer.feerate. > > > * A partial tx order, as in the manner of the block.txs ordering, MUS= T be > > > imposed. > > > * A node SHOULD drop a peer that sends a package (or tx) below > > > node.feerate. > > > * A node MAY drop a peer that sends a non-minimal package according t= o > > > node.feerate. > >=20 > > This makes sense particularly if multiple node implementations are used= in > > future. >=20 >=20 > There are many node implementations used presently. And of course these a= re protocol proposals, which presumes more than one implementation. >=20 > > My other questions: > >=20 > > a)If a package has tx1, tx2, tx3, tx4 and tx5 and miner just include tx= 1 and tx2 > > in the block, how does this affect the projects considered for packages > > proposal? >=20 >=20 > I will leave that to authors of such proposals to answer. However in what= I have proposed it just means tx3/4/5 get considered for subsequent block = inclusion to the extent that fee rate policy is satisfied. >=20 > One of the several problems with static construction of packages is that = they can still get stuck by fee rate policy. This is just kicking the can d= own the road while complicating the protocol. >=20 > > b)How does changing the order of txs in a package affect these transact= ions? >=20 >=20 > There is no impact. I proposed the partial ordering to facilitate fail fa= st. >=20 > The partial ordering in block txs is unnecessary (given the PoW DOS guard= ). This is a consequence of the order imposed by Satoshi's implementation a= nd only serves to slow validation (order constrains concurrency). >=20 > > c)Do packages introduce more attack vectors in bitcoin for front runnin= g or > > MEV? MEV in bitcoin currently only affects the projects that are consid= ered > > in packages proposal. >=20 >=20 > I don't consider this relevant to any protocol considerations. Miners sho= uld always be expected to select the most optimal set of txs available in t= he time available to do so. >=20 > > d)What if the package contains a transactions with sanctioned address? >=20 >=20 > One can consider this a policy, much like fee rate. Any policy that is ap= plied to transactions and not known to its peers will result in the node re= ceiving orphans. As such the node either must allow orphans or drop peers s= ending orphans under the assumption that the peer is expected to have imple= mented the same policy. >=20 > > e)Why would miners use packages if the existing scenario in terms of fe= es > > per block is beneficial for them? >=20 >=20 > The presumption is that the miner is only ever seeing txs that satisfy it= s fee rate policy, so this is just more opportunity. >=20 > I'd add that the problem of "pinning" is related, but exacerbated by opaq= ue policy (internal to certain implementations). Any node that ejects txs f= rom its pool of valid but unconfirmed txs that satisfy fee rate policy is g= oing to see orphans and going to cause txs to get stuck. This is one of the= many problems with placing an arbitrary bound on the size of this pool. >=20 > A subset of this problem is RBF policy. It is nice to see some movement t= oward generalizing RBF. The term is really a misnomer. Conflicting txs and = subgraphs of txs are only problematic in the case of DOS, which is also res= olved through advertised fee policy. Any node that imposes policy beyond th= is will also see orphans and cause txs to get stuck. >=20 > The scenario and therefore complexity consequences of an implementation-s= pecific memory-constrained tx pool are becoming increasingly apparent. Thes= e are implementation issues, not protocol issues. This can be observed in a= recent thread: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/202= 2-September/020937.html >=20 > Over time we are likely to see that the only policies that remain in wide= spread application are those that are necessary for DOS protection (fee rat= e), as other restrictions are not economically rational and cannot be enfor= ced. We've seen recent debate regarding dust policy, and op_return policy. = "non-standard" txs are perfectly valid but get stuck very easily. I'll reit= erate, any policy beyond what is published via the protocol will cause the = above problems. >=20 > e >=20 > > /dev/fd0 > >=20 > > Sent with Proton Mail secure email. > >=20 > > ------- Original Message ------- > > On Thursday, June 9th, 2022 at 4:13 AM, Eric Voskuil via bitcoin-dev > dev@lists.linuxfoundation.org> wrote: > >=20 > > > Hi Suhas/Gloria, > > >=20 > > > Good questions. I've started a new thread because it became something > > > else... > > >=20 > > > Various ideas about packaging seem to be focused on the idea of an at= omic > > > message that is gossiped around the network like a transaction or blo= ck. > > > From my perspective that seems to create a set of problems without go= od > > > solutions, and it is not a proper analogy to those atomic structures.= It may be > > > worth taking the time to step back and take a close look at the under= lying > > > objective. > > >=20 > > > The sole objective, as expressed in the OP proposal, is to: > > >=20 > > > "Propagate transactions that are incentive-compatible to mine, even i= f they > > > don't meet minimum feerate alone." > > >=20 > > > Effectively producing this outcome with an atomic packaging approach > > > while at the same time maintaining network invariants seems unlikely,= if not > > > impossible. > > >=20 > > > Fees: > > >=20 > > > A node knows what fee rate a peer will accept, and announces individu= al > > > txs that satisfy peer.feerate. Similarly a node knows its own feerate= , and > > > SHOULD drop any peer that announces txs that do not satisfy node.feer= ate. > > >=20 > > > Orphans: > > >=20 > > > A node MAY drop a peer that announces txs that the node sees as orpha= ns > > > against its DAG. It SHOULD drop the orphan tx and MAY request missing > > > ancestors. Presumably after some amount of time connected to peer, no= de > > > does not expect to see any more orphans from that peer, so these choi= ces > > > could evolve with the channel. However, the design that can only cons= ider > > > each tx in isolation will continue to cause orphan announcements on t= he > > > channel. A below peer.feerate tx does not get announced to peer, and = later > > > a descendant high peer.feerate does get announced to the peer - as an > > > orphan. > > >=20 > > > BIP133 (feefilter): > > >=20 > > > "There could be a small number of edge cases where a node's mempool > > > min fee is actually less than the filter value a peer is aware of and > > > transactions with fee rates between these values will now be newly > > > inhibited." > > >=20 > > > https://github.com/bitcoin/bips/blob/master/bip-0133.mediawiki > > >=20 > > > Whether the problem is "small" or not depends on the disparity betwee= n > > > node fee rates, which is not a matter of protocol. This is an existin= g problem > > > that can and should be dealt with in packaging, as part of the above > > > objective. > > >=20 > > > Packaged Transaction Relay: > > >=20 > > > One might instead think of packaging as a per-connection function, > > > operating over its transaction (input->output) DAG and the feerate of= its > > > own node and that of the peer. Logically a "package" is nothing more = than a > > > set of transactions (optimized by announcement). Only a node can > > > effectively determine the packaging required by each of its peers, si= nce only > > > the node is aware of peer.feerate. > > >=20 > > > The only way to avoid dead-ending packages (including individual > > > transactions, as is the objective) is for a node to package txs for e= ach peer. > > > The origination of any package is then just a wallet peer doing what = a node > > > does - packaging transactions that satisfy peer.feerate (i.e. that of= its node). > > >=20 > > > Current transaction relay (txB->txA): > > >=20 > > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D > > > Node0 > > > txA.feerate > node.feerate, and not orphaned (accept txA) > > >=20 > > > txA.feerate > peer1.feerate (announce txA to peer1) > > >=20 > > > txA.feerate < peer2.feerate (do not announce txA to peer2) > > > ----- > > > txB.feerate > node.feerate (accept txB) > > >=20 > > > txB.feerate > peer1.feerate (announce txB to peer1) > > >=20 > > > txB.feerate > peer2.feerate (announce txB to peer2) > > >=20 > > > Node1 > > > Sees/accepts txA and txB. > > >=20 > > > Node2 > > > Never sees txA, sees/rejects txB (as an orphan). > > >=20 > > > Packaged transaction relay (txB->txA): > > >=20 > > > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D=3D=3D=3D=3D=3D > > > Node0 > > > txA.feerate > node.feerate, and not orphaned (accept txA) > > >=20 > > > txA.feerate > peer1.feerate (announce txA to peer1) > > >=20 > > > txA.feerate < peer2.feerate (do not announce txA to peer2) > > > ----- > > > txB.feerate > node1.feerate (accept txB) > > >=20 > > > txB.feerate > peer1.feerate (announce txB to peer1) > > >=20 > > > txB.feerate > peer2.feerate (do not announce txB to peer2) <=3D=3D av= oid > > > predictable orphan > > >=20 > > > txA.feerate + txB.feerate > peer2.feerate (announce pkg(A, B) to > > > peer2) <=3D create minimal package > > >=20 > > > Node1 > > > Sees/accepts txA and txB. > > >=20 > > > Node2 > > > pkg(A, B) > node2.feerate (accept txA, txB) > > >=20 > > > txA.feerate > peer3.feerate (announce txA to peer3) > > >=20 > > > txB.feerate > peer3.feerate (announce txB to peer3) > > >=20 > > > Sees/accepts pkg(A, B). > > >=20 > > > Node3 > > > Sees/accepts txA and txB. <=3D avoided unnecessary packaging > > >=20 > > > Summary: > > >=20 > > > In this design, any node that receives an announcement for a pkg (or = tx) > > > later determined to be less than node.feerate SHOULD drop the announc= ing > > > peer. Unlike with existing tx relay, a node can become "current" and > > > subsequently see few if any tx or pkg orphans, and MAY at some point > > > decide to drop any peer that announces one. Notice that packages are > > > created dynamically, and any package that doesn't need to be grouped = gets > > > trimmed down to individual transactions. Furthermore any tx that is "= stuck" > > > can be freed by simply sending another tx. The nodes at which the tx = has > > > become stuck will just package it up and relay it to peers. In other = words, > > > there is no impact on wallet implementation apart from raising the ag= gregate > > > fee using a descendant transaction. > > >=20 > > > This is barely a protocol change - it's primarily implementation. All= that > > > should be required is an additional INV element type, such as > > > MSG_TX_PACKAGE. > > >=20 > > > Additional constraints: > > >=20 > > > * All elements of MSG_TX_PACKAGE in one INV message MUST to be of > > > the same package. > > > * A package MUST must define a set that can be mined into one block > > > (size/sigops constraint). > > > * A package SHOULD not contain confirmed txs (a race may cause this). > > > * A package MUST minimally satisfy peer.feerate. > > > * A partial tx order, as in the manner of the block.txs ordering, MUS= T be > > > imposed. > > > * A node SHOULD drop a peer that sends a package (or tx) below > > > node.feerate. > > > * A node MAY drop a peer that sends a non-minimal package according t= o > > > node.feerate. > > >=20 > > > The partial ordering of block.txs introduces an ordering constraint t= hat > > > precludes full parallelism in validating input attachment. This is an > > > implementation artifact that made its way into consensus. However in = the > > > case of packaging, the set of txs is not presumed to be valid under t= he proof > > > of work DoS guard. As such constraints should minimize the work/traff= ic > > > required to invalidate the message. The partial order constraint ensu= res that > > > the DAG can be built incrementally, dropping the attempt (and peer as > > > desired) as soon as the first orphan is discovered. As a result the n= etwork > > > traffic and work required is not materially different than with tx re= lay, with > > > two exceptions. > > >=20 > > > These are the two central aspects of this approach (Avoiding Predicta= ble > > > Orphans and Creating Minimal Packages). These are graph search algori= thms, > > > some basic computer science. Minimality requires only that the packag= e does > > > not introduce txs that are not necessary to reach the peer.feerate (a= s these > > > can always be packaged separately). It does not require that nodes al= l > > > generate the same packages. It does not require negotiation, package > > > identity, cryptography, or hashing. As a graph search it should be O(= n) where > > > n is the unconfirmed ancestry of the package, but should typically be= much > > > lower, if not a single step. > > >=20 > > > Sufficiently-low-fee nodes will see only single txs. Moderate-fee > > > nodes may cause partial breakup of packages. Sufficiently high fee > > > nodes will cause peers (having received and completed the acceptance > > > of a tx/pkg with pkg.feerate < peer.feerate) to navigate from each > > > tx/package external input until reaching txs above peer.feerate, or > > > confirmed (both of which the peer is presumed to already have). If th= e > > > pkg.feerate is sufficiently high to connect all external inputs to th= e > > > intervening txs, they are added to the package and it is announced to > > > the high fee peer. Note that the individual tx.feerate > peer.feerate > > > is insufficient to ensure that the peer should have the tx, as there > > > may be ancestor txs that do not, and for which the tx was insufficien= t > > > to cause them to be packaged. So a non-caching algorithm must be able > > > to chase each package external input to a confirmed tx (or cache the > > > unconfirmed ancestry fee rate at each tx). Note that fee rates are no= t > > > directly additive, both size/ > > >=20 > > > weight and fee are required for summation (and aggregate sigops shoul= d > > > be considered). > > >=20 > > > This makes no assumptions about current implementations. The design > > > would call for maintenance of a transaction (input->output) DAG with > > > tx.feerate on each tx. This could be the unconfirmed tx graph (i.e. "= memory > > > pool") though it does not require maintenance of anything more than t= he > > > parameters necessary to confirm a set of validated txs within a block= . It is > > > very reasonable to require this of any participating node. A simple v= ersion > > > negotiation can identify a package-accepting/sending nodes. > > >=20 > > > I have thought about this for some time, but have not implemented eit= her > > > the graph search, source code, or BIP. Just wrote this off the top of= my head. > > > So I am sure there are some things I have incorrect or failed to cons= ider. But I > > > think it's worth discussing it at this point. > > >=20 > > > e > > >=20 > > > > -----Original Message----- > > > > From: bitcoin-dev bitcoin-dev-bounces@lists.linuxfoundation.org On > > > > Behalf Of Suhas Daftuar via bitcoin-dev > > > > Sent: Wednesday, June 8, 2022 8:59 AM > > > > To: Bitcoin Protocol Discussion > > > > bitcoin-dev@lists.linuxfoundation.org > > > > Subject: Re: [bitcoin-dev] Package Relay Proposal > > > >=20 > > > > Hi, > > > >=20 > > > > Thanks again for your work on this! > > > >=20 > > > > One question I have is about potential bandwidth waste in the case > > > > of nodes running with different policy rules. Here's my > > > > understanding of a scenario I think could happen: > > > >=20 > > > > 1) Transaction A is both low-fee and non-standard to some nodes on > > > > the network. > > > > 2) Whenever a transaction T that spends A is relayed, new nodes wil= l > > > > send INV(PKGINFO1, T) to all package-relay peers. > > > > 3) Nodes on the network that have implemented package relay, but do > > > > not accept A, will send getdata(PKGINFO1, T) and learn all of T's > > > > unconfirmed parents (~32 bytes * number of parents(T)). > > > > 4) Such nodes will reject T. But because of transaction > > > > malleability, and to avoid being blinded to a transaction > > > > unnecessarily, these nodes will likely still send getdata(PKGINFO1, > > > > T) to every node that announces T, in case someone has a transactio= n > > > > that includes an alternate set of parent transactions that would pa= ss > > > > policy checks. > > > >=20 > > > > Is that understanding correct? I think a good design goal would be > > > > to not waste bandwidth in non-adversarial situations. In this case, > > > > there would be bandwidth waste from downloading duplicate data from > > > > all your peers, just because the announcement doesn't commit to the > > > > set of parent wtxids that we'd get from the peer (and so we are > > > > unable to determine that all our peers would be telling us the same= thing, > > > > just based on the announcement). > > > >=20 > > > > Some ways to mitigate this might be to: (a) include a hash (maybe > > > > even just a 20-byte hash -- is that enough security?) of the packag= e > > > > wtxids (in some canonical ordering) along with the wtxid of the > > > > child in the initial announcement; (b) limit the use of v1 packages > > > > to transactions with very few parents (I don't know if this is reas= onable > > > > for the use cases we have in mind). > > > >=20 > > > > Another point I wanted to bring up is about the rules around v1 > > > > package validation generally, and the use of a blockhash in > > > > transaction relay specifically. My first observation is that it > > > > won't always be the case that a v1 package relay node will be able > > > > to validate that a set of package transactions is fully sorted > > > > topologically, because there may be (non-parent) ancestors that are > > > > missing from the package and the best a peer can validate is > > > > topology within the package -- this means that a peer can validly > > > > (under this > > > > BIP) relay transaction packages out of the true topological sort (i= f > > > > all ancestors were included). > > > >=20 > > > > This makes me wonder how useful this topological rule is. I suppose > > > > there is some value in preventing completely broken implementations > > > > from staying connected and so there is no harm in having the rule, > > > > but perhaps it would be helpful to add that nodes SHOULD order > > > > transactions based on topological sort in the complete transaction > > > > graph, so that if missing-from-package ancestors are already known > > > > by a peer (which is the expected case when using v1 package relay o= n > > > > transactions that have more than one generation of unconfirmed > > > > ancestor) then the remaining transactions are already properly orde= red, > > > > and this is helpful even if unenforceable in general. > > > >=20 > > > > The other observation I wanted to make was that having transaction > > > > relay gated on whether two nodes agree on chain tip seems like an > > > > overly restrictive criteria. I think an important design principle > > > > is that we want to minimize disruption from network splits -- if > > > > there are competing blocks found in a small window of time, it's > > > > likely that the utxo set is not materially different on the two > > > > chains (assuming miners are selecting from roughly the same sets of > > > > transactions when this happens, which is typical). Having > > > > transaction relay bifurcate on the two network halves would seem to > > > > exacerbate the difference between the two sides of the split -- > > > > users ought to be agnostic about how benign splits are resolved and > > > > would likely want their transactions to relay across the whole netw= ork. > > > >=20 > > > > Additionally, use of a chain tip might impose a larger burden than > > > > is necessary on software that would seek to participate in > > > > transaction relay without implementing headers sync/validation. I > > > > don't know what software exists on the network, but I imagine there > > > > are a lot of scripts out there for transaction submission to the > > > > public p2p network, and in thinking about modifying such a script t= o > > > > utilize package relay it seems like an unnecessary added burden to = first > > > > learn a node's tip before trying to relay a transaction. > > > >=20 > > > > Could you explain again what the benefit of including the blockhash > > > > is? It seems like it is just so that a node could prioritize > > > > transaction relay from peers with the same chain tip to maximize th= e > > > > likelihood of transaction acceptance, but in the common case this > > > > seems like a pretty negligible concern, and in the case of a chain > > > > fork that persists for many minutes it seems better to me that we > > > > not partition the network into package-relay regimes and just risk = a > > > > little extra bandwidth in one direction or the other. If we solve > > > > the problem I brought up at the beginning (of de-duplicating packag= e > > > > data across peers with a package-wtxid-commitment in the > > > > announcement), I think this is just some wasted pkginfo bandwidth o= n > > > > a single-link, and not across links (as we could cache validation f= ailure for a > > > > package-hash to avoid re-requesting duplicate pkginfo1 messages). > > > >=20 > > > > Best, > > > > Suhas > > > >=20 > > > > On Tue, Jun 7, 2022 at 1:57 PM Gloria Zhao via bitcoin-dev > > > dev@lists.linuxfoundation.org > > > dev@lists.linuxfoundation.org> > wrote: > > > >=20 > > > > Hi Eric, aj, all, > > > >=20 > > > > Sorry for the delayed response. @aj I'm including some paraphrased > > > > points from our offline discussion (thanks). > > > >=20 > > > > > 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= ? > > > >=20 > > > > > As I suggested earlier, a package is fundamentally a compact bloc= k > > > > > (or > > > > > block) announcement without the header. Compact block (BIP152) > > > > > announcement is already well-defined and widely implemented... > > > >=20 > > > > > Let us not reinvent the wheel and/or introduce accidental > > > > > complexity. I see no reason why packaging is not simply BIP152 > > > > > without the 'header' > > > > > field, an > > > > > updated protocol version, and the following sort of changes to > > > > > names > > > >=20 > > > > Interestingly, "why not use BIP 152 shortids to save bandwidth?" is > > > > by far the most common suggestion I hear (including offline feedbac= k). > > > > Here's a full explanation: > > > >=20 > > > > BIP 152 shortens transaction hashes (32 bytes) to shortids (6 bytes= ) > > > > to save a significant amount of network bandwidth, which is > > > > extremely important in block relay. However, this comes at the > > > > expense of computational complexity. There is no way to directly > > > > calculate a transaction hash from a shortid; upon receipt of a > > > > compact block, a node is expected to calculate the shortids of ever= y > > > > unconfirmed transaction it knows about to find the matches (BIP 152= : > > > > 1, Bitcoin Core: 2). This is expensive but appropriate for block > > > > relay, since the block must have a valid Proof of Work and new > > > > blocks only come every ~10 minutes. On the other hand, if we requir= e > > > > nodes to calculate shortids for every transaction in their mempools= every > > > > time they receive a package, we are creating a DoS vector. > > > > Unconfirmed transactions don't need PoW and, to have a live > > > > transaction relay network, we should expect nodes to handle > > > > transactions at a high-ish rate (i.e. at least 1000s of times more > > > > transactions than blocks). We can't pre- calculate or cache shortid= s > > > > for mempool transactions, since the SipHash key depends on the bloc= k > > > > hash and a per-connection salt. > > > >=20 > > > > Additionally, shortid calculation is not designed to prevent > > > > intentional individual collisions. If we were to use these shortids > > > > to deduplicate transactions we've supposedly already seen, we may > > > > have a censorship vector. Again, these tradeoffs make sense for > > > > compact block relay (see shortid section in BIP 152 [3]), but not p= ackage > > > > relay. > > > >=20 > > > > TLDR: DoSy if we calculate shortids on every package and censorship > > > > vector if we use shortids for deduplication. > > > >=20 > > > > > Given this message there is no reason to send a (potentially > > > > > bogus) fee rate with every package. It can only be validated by > > > > > obtaining the full set of txs, and the only recourse is dropping > > > > > (etc.) the peer, as is the case with single txs. > > > >=20 > > > > Yeah, I agree with this. Combined with the previous discussion with > > > > aj (i.e. we can't accurately communicate the incentive compatibilit= y > > > > of a package without sending the full graph, and this whole dance i= s > > > > to avoid downloading a few low-fee transactions in uncommon edge > > > > cases), I've realized I should remove the fee + weight information > > > > from pkginfo. Yay for less complexity! > > > >=20 > > > > Also, this might be pedantic, but I said something incorrect earlie= r > > > > and would like to correct myself: > > > >=20 > > > > > > 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. > > > >=20 > > > > I said "It's fine if they have Erlay, since a sender would know in > > > > advance that B is missing and announce it as a package." But this > > > > isn't true since we're only using reconciliation in place of > > > > flooding to announce transactions as they arrive, not for > > > > rebroadcast, and we're not doing full mempool set reconciliation. I= n > > > > any case, making sure a node receives the transactions announced > > > > when it was offline is not something we guarantee, not an intended = use > > > > case for package relay, and not worsened by this. > > > >=20 > > > > Thanks for your feedback! > > > >=20 > > > > Best, > > > >=20 > > > > Gloria > > > >=20 > > > > 0152.mediawiki#cmpctblock > > > > 2: > > > > https://github.com/bitcoin/bitcoin/blob/master/src/blockencodings.c= p > > > > p#L49 > > > > [3]: https://github.com/bitcoin/bips/blob/master/bip- > > > > 0152.mediawiki#short-transaction-id-calculation > > > >=20 > > > > On Thu, May 26, 2022 at 3:59 AM > > > mailto:eric@voskuil.org > wrote: > > > >=20 > > > > Given that packages have no header, the package requires identity i= n > > > > a > > > > BIP152 scheme. For example 'header' and 'blockhash' fields can be > > > > replaced with a Merkle root (e.g. "identity" field) for the package= , > > > > uniquely identifying the partially-ordered set of txs. And use of > > > > 'getdata' (to obtain a package by hash) can be eliminated (not a us= e > > > > case). > > > >=20 > > > > e > > > >=20 > > > > > -----Original Message----- > > > > > From: eric@voskuil.org mailto:eric@voskuil.org > > > > > > > > > > Sent: Wednesday, May 25, 2022 1:52 PM > > > > > To: 'Anthony Towns' > > > > mailto:aj@erisian.com.au >; 'Bitcoin Protocol Discussion' > > > > > > > > > dev@lists.linuxfoundation.org> >; 'Gloria Zhao' > > > > > > > > > > Subject: RE: [bitcoin-dev] Package Relay Proposal > > > > >=20 > > > > > > From: bitcoin-dev > > > > > bounces@lists.linuxfoundation.org > > > > > bounces@lists.linuxfoundation.org> > On > > > > > > Behalf > > > > > > Of Anthony Towns via bitcoin-dev > > > > > > Sent: Wednesday, May 25, 2022 11:56 AM > > > > >=20 > > > > > > So the other thing is what happens if the peer > > > > > > announcing packages to us > > > > > > is > > > > > > dishonest? > > > > > >=20 > > > > > > 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? > > > > > >=20 > > > > > > 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. > > > > >=20 > > > > > Single tx broadcasts do not carry an advertised fee rate, > > > > > however the' > > > > > feefilter' message (BIP133) provides this distinction. This > > > > > should be > > > > > interpreted as applicable to packages. Given this message > > > > > there is no > > > > > reason > > > > > to send a (potentially bogus) fee rate with every package. It > > > > > can only be > > > > > validated by obtaining the full set of txs, and the only > > > > > recourse is > > > > > dropping (etc.) the peer, as is the case with single txs. > > > > > Relying on the > > > > > existing message is simpler, more consistent, and more > > > > > efficient. > > > > >=20 > > > > > > > > Is it plausible to add the graph in? > > > > > >=20 > > > > > > 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. > > > > > >=20 > > > > > > 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? > > > > >=20 > > > > > As I suggested earlier, a package is fundamentally a > > > > > compact block (or > > > > > block) announcement without the header. Compact block > > > > > (BIP152) > > > > > announcement > > > > > is already well-defined and widely implemented. A node > > > > > should never be > > > > > required to retain an orphan, and BIP152 ensures this is not > > > > > required. > > > > >=20 > > > > > Once a validated set of txs within the package has been > > > > > obtained with > > > > > sufficient fee, a fee-optimal node would accept the largest > > > > > subgraph of > > > > > the > > > > > package that conforms to fee constraints and drop any > > > > > peer that provides a > > > > > package for which the full graph does not. > > > > >=20 > > > > > Let us not reinvent the wheel and/or introduce accidental > > > > > complexity. I > > > > > see > > > > > no reason why packaging is not simply BIP152 without the > > > > > 'header' field, > > > > > an > > > > > updated protocol version, and the following sort of changes > > > > > to names: > > > > >=20 > > > > > sendpkg > > > > > MSG_CMPCT_PKG > > > > > cmpctpkg > > > > > getpkgtxn > > > > > pkgtxn > > > > >=20 > > > > > > > For a maximum 25 transactions, > > > > > > > 2324/2 =3D 276, seems like 36 bytes for a child-with- > > > > > > > parents package. > > > > > >=20 > > > > > > If you're doing short ids that's maybe 254B=3D100B > > > > > > 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. > > > > > >=20 > > > > > > > Also side note, since there are no size/count params, > > > > >=20 > > > > > Size is restricted in the same manner as block and > > > > > transaction broadcasts, > > > > > by consensus. If the fee rate is sufficient there would be no > > > > > reason to > > > > > preclude any valid size up to what can be mined in one > > > > > block (packaging > > > > > across blocks is not economically rational under the > > > > > assumption that one > > > > > miner cannot expect to mine multiple blocks in a row). > > > > > Count is > > > > > incorporated > > > > > into BIP152 as 'shortids_length'. > > > > >=20 > > > > > > > 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? > > > > >=20 > > > > > Adding versioning to individual protocols is just a reflection > > > > > of the > > > > > insufficiency of the initial protocol versioning design, and > > > > > that of the > > > > > various ad-hoc changes to it (including yet another > > > > > approach in this > > > > > proposal) that have been introduced to compensate for it, > > > > > though I'll > > > > > address this in an independent post at some point. > > > > >=20 > > > > > Best, > > > > > e > > > > >=20 > > > > > > Maybe but a couple of messages per connection doesn't > > > > > > really seem worth > > > > > > arguing about? > > > > > >=20 > > > > > > Cheers, > > > > > > aj > > > > > >=20 > > > > > > -- > > > > > > Sent from my phone. > > > >=20 > > > > _______________________________________________ > > > >=20 > > > > > > bitcoin-dev mailing list > > > > > > bitcoin-dev@lists.linuxfoundation.org > > > > > dev@lists.linuxfoundation.org> > > > >=20 > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > > >=20 > > > > _______________________________________________ > > > > bitcoin-dev mailing list > > > > bitcoin-dev@lists.linuxfoundation.org > > > dev@lists.linuxfoundation.org> > > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > >=20 > > > _______________________________________________ > > > bitcoin-dev mailing list > > > bitcoin-dev@lists.linuxfoundation.org > > > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev