Return-Path: Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id AE60FC0051 for ; Sat, 19 Sep 2020 19:14:12 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 9D1F8873DC for ; Sat, 19 Sep 2020 19:14:12 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Pp1LelpasE9H for ; Sat, 19 Sep 2020 19:14:10 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com [209.85.221.53]) by hemlock.osuosl.org (Postfix) with ESMTPS id E8B4281BB9 for ; Sat, 19 Sep 2020 19:14:09 +0000 (UTC) Received: by mail-wr1-f53.google.com with SMTP id m6so8845981wrn.0 for ; Sat, 19 Sep 2020 12:14:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=pXRlu7eorT7HWvY//jKCnWemXYLZPIFfEixKn6eSWfM=; b=AthKZBoEnKogvYxxtG1SOPolnmN4O6QMba9FPi4j5mZbXjkJvTPgsOZP09es+1URda 6FRQooOLBqJZJfYAIsra8P6/0azoqkP26/jZJEPDi3rkywF+WLP42NcuEPHi9ZvtKzpD Wl4hSaum8j4yuohiGx2WjzMW7YrA1T00GnZPU/vPPI/s0x7aHd4hcSoN7FsLy7l2qyQB XHo9xdmderN6VUAEs61fF6fIcxKz7pLFXqIOO/LnB4aYRlCZLMQhVo9nu/PVRPQPgCXs m8v+0l9PVG/Xt074FzJlnKCXuwruUpqrkDtpL2iZJz0e+1Q0BSL1vh93F/E+dVyveLT+ Sv7w== 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; bh=pXRlu7eorT7HWvY//jKCnWemXYLZPIFfEixKn6eSWfM=; b=UfF9P3x6ePinffhsxFOOmF7ztLpYOeqg0F+w2/y+Ghyna9HsYsB3U46gpJiIycTXpD uGrNk6zlOvBADhFNccxBf6s7IaQvirhmtwiw2LAjAnZ0kc9E/LKsIHdI12HCGalJHJJC Ed0gtITVfl9IH+1p/8zOSx4LEcXc2GL4pYtXzKgd38GzBiMv23+3mFkeZkF27sfr24x8 1pVepY1RNc98im4VM4YuolyBAYEpo4wgb8UwPoIVPMBlzTsQrNkhmEGkL0CiH00O/oQ+ QLK9GfdsfIslzBvKhA+quWxw0V+imHqPSwO9P424nzdll0PfiNAo6RVZhmWykn/4AdFn seOg== X-Gm-Message-State: AOAM5327MXyGf75v+AwU18T1jbZyWCvbo/0uDGLJuk23KXb5jO40rz9g ucVgJM7D0OehKZby3Z6QOfal1Mp9rnt91n88nJ6Z1PnKh4UoBA== X-Google-Smtp-Source: ABdhPJxkLsb+8XB2omszyEfpVf8ptbuAS+nuf1Yy2G46T4j3sp38CrFQ+oFV7ZVtmgSEx9PjoKvpnnBWWOkbaXGklqc= X-Received: by 2002:adf:f44d:: with SMTP id f13mr43882291wrp.224.1600542848246; Sat, 19 Sep 2020 12:14:08 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Antoine Riard Date: Sat, 19 Sep 2020 15:13:56 -0400 Message-ID: To: Jeremy , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000eae76705afaf6b1a" X-Mailman-Approved-At: Sat, 19 Sep 2020 19:36:31 +0000 Subject: Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring 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, 19 Sep 2020 19:14:12 -0000 --000000000000eae76705afaf6b1a Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable EDIT: I misunderstood the emplacement of the sponsor vector, please disregard previous review :( Beyond where the convenient place should live, which is still accurate I think. > The > Sponsor Vector TXIDs must also be > in the block the transaction is validated in, with no restriction on > order or on specifying a TXID > more than once. Le sam. 19 sept. 2020 =C3=A0 14:39, Antoine Riard = a =C3=A9crit : > Hi Jeremy, > > This is a really interesting proposal to widen the scope of fee > mechanisms. > > First, a wider point on what this proposal brings with regards to pinning= , > to the best of my knowledge. > > A pinning may have different vectors by exploiting a) mempools limits (e.= g > descendants) or b) mempools absolute-fee/feerate/conflicts logic. The lac= k > of a global mempool means you can creatively combine them to provoke > mempools-partitions [0] > > As far as I understand this proposal, it aims to solve the class a) of > pinnings by allowing fee-bumping with a new definition of dependencies. I= 'm > not sure it achieves to do so as the Sponsor Vector TXIDs being committe= d > in the Sponsoree signature hash means the Sponsor feerate is part of this > commitment and can't be unilaterally adjusted to actual mempool-congestio= n. > > After broadcasting the Sponsor/Sponsoree pair, mempools feerate may > increase again and thus obsoleting the previous fee-bump. Or you need a > Sponsor Vector for every blockspace feerate, in the worst-case bound by t= he > value of the Sponsoree funds. > > Further, I would say this proposal won't solve class b) of pinnings for > multi-party time-sensitive protocols without further modifications. E.g i= n > a LN-channel, assuming the commitment transaction is the Sponsoree, Alice > the honest party can't increase Sponsor feerate by mal eating its outputs > without breaking the sponsoring dependency. And thus evict a Bob's > malicious pin across network mempools. > > I think a further softfork proposal with regards to sighash malleability > is needed to achieve the security semantic for Lightning type of protocol= s. > Roughly, a SIGHASH_IOVECTOR allows N-inputs to commit to N-outputs, thus > committing to all the balance/HTLC outputs minus the last output Vector, > non-interactively malleable by channel participants. This would be a form > of transaction finalization delegation, allowing Alice to direct the > Sponsor vector to a good-feerate adjusted transaction. > > Note, I may have misunderstood completely the proposal as the feerate > observed might be the Sponsor _package_ one and each party could have a > pair of outputs to spend from to non-interactively increase the Sponsoree= . > Though sounds like re-introducing the limits issues... > > That said, see following review points. > > > This is insufficient because if new attacks are found, there is > > limited ability to deploy fixes for > > them against deployed contract instances (such as open lightning > > channels). What is required is a > > fully abstracted primitive that requires no special structure from an > > underlying transaction in > > order to increase fees to confirm the transactions. > > This is really true, in case of vulnerability discovered mass closing of > the channel would be in itself a concern as it would congest mempools and > open to looter behaviors [1]. Though I don't think a special structure ca= n > claim covering every potential source of vulnerability for off-chain > protocols as some of them might be tx-relay based (e.g reject-filters for > segwit txn). > > Further, a "fully abstracted primitive" is loosely defined, one could > argue that anchor outputs don't require special structure from an > underlying transaction (i.e on the order of outputs ?). > > > where > n>1, it is interpreted as a vector of TXIDs (Sponsor Vector). > > n >=3D1 ? I think you can have at least one vector and this is matching t= he > code > > > If there is another convenient place to put the TXID vector, that's fin= e > too. > > You might use the per-input future Taproot annex, and even apply a witnes= s > discount as this mechanism could be argued to be less blockspace expensiv= e > than a CPFP for the same semantic. > > An alternative could be a new transaction field like a new `stxid` : > > > `[nVersion][marker][flag][txins][txouts][witness][nLockTime][nSponsor][nV= ersion][n*STXID]` > > It would be cheaper as you likely save the output amount size and OP_VER. > And you don't have to subtract a dust output + 1 from the other output > amount to make sure the Sponsor output meets dust propagation requirement= s. > > Though it's more demanding on the tx-relay layer (new serialization and > transaction identifier) and new a version bump of the signature digest al= go > to avoid a third-party malleating the per-transaction sponsor field > > > To prevent garbage sponsors, we also require that: > > Does the reverse hold ? Garbage Sponsoree by breaking the dependency and > double-spending the utxo spent by the Sponsor and thus decreasing > Sponsoree's feerate to mempool bottom. AFAIK you can't do this with CPFP. > > > rational miners may wish to permit multiple sponsor > > targets, or multiple sponsoring > > transactions, > > I'm not sure if your policy sktech prevents multiple > 1-Sponsor-to-N-Sponsoree. Such a scheme would have some edges. A mempool > might receive Sponsoree in different order than evaluated by original > sender and thus allocate the Sponsor feerate to the less-urgent Sponsoree= . > > > This is treated as a separate > > concern, as any strides on > > package relay generally should be able to support sponsors trivially. > > This is one more reason to carefully version package relay, beyond the > transaction package complexity, you now have a new type of graph dependen= cy > to scope. What we should be worried about is network mempools partitions > between different mechanisms of incompatible package relay if we implemen= t > one. > > Overall, a missing point which is making this proposal compelling is the > fact that you may have one 1-Sponsor-for-N-Sponsoree which is a far reduc= ed > cost compared to N-Parent-1-CPFP as the CPFP must include an input for ea= ch > bumped parent. Here you only have the Sponsor output. Thus observing > input_size > output_size, this proposal is better for multi-transactions > bumping (but not for N=3D1 as you have to bear the input spending of the > Sponsor). > > Antoine > > [0] Within LN-context, for class b) see > https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-June/00275= 8.html > > [1] See the recent Dynamic Commitments proposal to ponder this concern > https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-July/00276= 3.html > > Le ven. 18 sept. 2020 =C3=A0 20:52, Jeremy via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit : > >> Hi Bitcoin Devs, >> >> >> I'd like to share with you a draft proposal for a mechanism to replace C= PFP and RBF for >> increasing fees on transactions in the mempool that should be more robus= t against attacks. >> >> A reference implementation demonstrating these rules is available >> [here](https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:s= ubsidy-tx) for those who >> prefer to not read specs. >> >> Should the mailing list formatting be bungled, it is also available as a= gist [here](https://gist.github.com/JeremyRubin/92a9fc4c6531817f66c2934282= e71fdf). >> >> Non-Destructive TXID Dependencies for Fee Sponsoring >> =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=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= =3D=3D=3D >> >> This BIP proposes a general purpose mechanism for expressing non-destruc= tive (i.e., not requiring >> the spending of a coin) dependencies on specific transactions being in t= he same block that can be >> used to sponsor fees of remote transactions. >> >> Motivation >> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> >> The mempool has a variety of protections and guards in place to ensure t= hat miners are economic and >> to protect the network from denial of service. >> >> The rough surface of these policies has some unintended consequences for= second layer protocol >> developers. Applications are either vulnerable to attacks (such as trans= action pinning) or must go >> through great amounts of careful protocol engineering to guard against k= nown mempool attacks. >> >> This is insufficient because if new attacks are found, there is limited = ability to deploy fixes for >> them against deployed contract instances (such as open lightning channel= s). What is required is a >> fully abstracted primitive that requires no special structure from an un= derlying transaction in >> order to increase fees to confirm the transactions. >> >> Consensus Specification >> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> >> If a transaction's last output's scripPubKey is of the form OP_VER follo= wed by n*32 bytes, where >> n>1, it is interpreted as a vector of TXIDs (Sponsor Vector). The Sponso= r Vector TXIDs must also be >> in the block the transaction is validated in, with no restriction on ord= er or on specifying a TXID >> more than once. This can be accomplished simply with the following patch= : >> >> >> ```diff >> + >> + // Extract all required fee dependencies >> + std::unordered_set dependencies; >> + >> + const bool dependencies_enabled =3D VersionBitsState(pindex->pprev,= chainparams.GetConsensus(), Consensus::DeploymentPos::DEPLOYMENT_TXID_DEPE= NDENCY, versionbitscache) =3D=3D ThresholdState::ACTIVE; >> + if (dependencies_enabled) { >> + for (const auto& tx : block.vtx) { >> + // dependency output is if the last output of a txn is OP_V= ER followed by a sequence of 32*n >> + // bytes >> + // vout.back() must exist because it is checked in CheckBlo= ck >> + const CScript& dependencies_script =3D tx->vout.back().scri= ptPubKey; >> + // empty scripts are valid, so be sure we have at least one= byte >> + if (dependencies_script.size() && dependencies_script[0] = =3D=3D OP_VER) { >> + const size_t size =3D dependencies_script.size() - 1; >> + if (size % 32 =3D=3D 0 && size > 0) { >> + for (auto start =3D dependencies_script.begin() +1,= stop =3D start + 32; start < dependencies_script.end(); start =3D stop, st= op +=3D 32) { >> + uint256 txid; >> + std::copy(start, stop, txid.begin()); >> + dependencies.emplace(txid); >> + } >> + } >> + // No rules applied otherwise, open for future upgrades >> + } >> + } >> + if (dependencies.size() > block.vtx.size()) { >> + return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS= , "bad-dependencies-too-many-target-txid"); >> + } >> + } >> + >> for (unsigned int i =3D 0; i < block.vtx.size(); i++) >> { >> const CTransaction &tx =3D *(block.vtx[i]); >> + if (!dependencies.empty()) { >> + dependencies.erase(tx.GetHash()); >> + } >> >> nInputs +=3D tx.vin.size(); >> >> @@ -2190,6 +2308,9 @@ bool CChainState::ConnectBlock(const CBlock& block= , BlockValidationState& state, >> } >> UpdateCoins(tx, view, i =3D=3D 0 ? undoDummy : blockundo.vtxund= o.back(), pindex->nHeight); >> } >> + if (!dependencies.empty()) { >> + return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, "b= ad-dependency-missing-target-txid"); >> + } >> ``` >> >> ### Design Motivation >> The final output of a transaction is an unambiguous location to attach m= etadata to a transaction >> such that the data is available for transaction validation. This data co= uld be committed to anywhere, >> with added implementation complexity, or in the case of Taproot annexes,= incompatibility with >> non-Taproot addresses (although this is not a concern for sponsoring a t= ransaction that does not use >> Taproot). >> >> A bare scriptPubKey prefixed with OP_VER is defined to be invalid in any= context, and is trivially >> provably unspendable and therefore pruneable. >> >> If there is another convenient place to put the TXID vector, that's fine= too. >> >> As the output type is non-standard, unupgraded nodes will by default not= include Transactions >> containing them in the mempool, limiting risk of an upgrade via this mec= hanism. >> >> Policy Specification >> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> >> The mechanism proposed above is a general specification for inter-transa= ction dependencies. >> >> In this BIP, we only care to ensure a subset of behavior sufficient to r= eplace CPFP and RBF for fee >> bumping. >> >> Thus we restrict the mempool policy such that: >> >> 1. No Transaction with a Sponsor Vector may have any child spends; and >> 1. No Transaction with a Sponsor Vector may have any unconfirmed parents= ; and >> 1. The Sponsor Vector must have exactly 1 entry; and >> 1. The Sponsor Vector's entry must be present in the mempool; and >> 1. Every Transaction may have exactly 1 sponsor in the mempool; except >> 1. Transactions with a Sponsor Vector may not be sponsored. >> >> >> The mempool treats ancestors and descendants limits as follows: >> >> 1. Sponsors are counted as children transactions for descendants; but >> 1. Sponsoring transactions are exempted from any limits saturated at the= time of submission. >> >> This ensures that within a given package, every child transaction may ha= ve a sponsor, but that the >> mempool prefers to not accept new true children while there are parents = that can be cleared. >> >> To prevent garbage sponsors, we also require that: >> >> 1. The Sponsor's feerate must be greater than the Sponsored's ancestor f= ee rate >> >> We allow one Sponsor to replace another subject to normal replacement po= licies, they are treated as >> conflicts. >> >> >> ### Design Motivation >> >> There are a few other ways to use OP_VER sponsors that are not included.= For instance, one could >> make child chains that are only valid if their parent is in the same blo= ck (this is incompatible >> with CTV, exercise left to reader). These use cases are in a sense incid= ental to the motivation >> of this mechanism, and add a lot of implementation complexity. >> >> What is wanted is a minimal mechanism that allows arbitrary unconnected = third parties to attach >> fees to an arbitrary transaction. The set of rules given tightly bounds = how much extra work the >> mempool might have to do to account for the new sponsors in the worst ca= se, while providing a "it >> always works" API for end users that is not subject to traditional issue= s around pinning. >> >> Eventually, rational miners may wish to permit multiple sponsor targets,= or multiple sponsoring >> transactions, but they are not required for the mechanism to work. This = is a benefit of the >> minimality of the consensus rule, it is compatible with future policy sh= ould it be implemented. >> >> >> #### Attack Analysis of new Policy >> >> In the worst case the new policy can lead to a 1/2 reduction in the numb= er of children allowed >> (e.g., if there are 13 children submitted, then 12 sponsors, the 25 chil= d limit will saturate >> before) and a 2x increase in the maximum children (e.g., if there are 25= children submitted, and >> then each are sponsored). Importantly, even in the latter attack scenari= o, the DoS surface is not >> great because the sponsor transactions have no children nor parents. >> >> #### Package Relay/Orphan Pool >> >> Future policy work might be able to insert sponsors into a special spons= or pool with an eviction >> policy that would enable sponsors to be queried and tracked for transact= ions that have too low fee >> to enter the mempool in the first place. This is treated as a separate c= oncern, as any strides on >> package relay generally should be able to support sponsors trivially. >> >> Reference Implementation >> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> A reference implementation demonstrating these rules is available >> [here](https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:s= ubsidy-tx). This is a best >> effort implementation, but has not been carefully audited for correctnes= s and likely diverges from >> this document in ways that should either be reflected in this document o= r amended in the code. >> >> >> Best, >> >> Jeremy >> >> >> >> -- >> @JeremyRubin >> >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > --000000000000eae76705afaf6b1a Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
EDIT: I misunderstood the emplacement of the spo= nsor vector, please disregard previous review :( Beyond where the convenien= t place should live, which is still accurate I think.

>= ; The
> Sponsor Vector TXIDs =C2=A0must also be
> in the block = the transaction is validated in, with no restriction on
> order or on= specifying a TXID
> more than once.


Le=C2=A0sam. = 19 sept. 2020 =C3=A0=C2=A014:39, Antoine Riard <antoine.riard@gmail.com> a =C3=A9crit=C2=A0:
<= /div>
Hi Jeremy,

This is a really interesting proposal to widen the scop= e of fee mechanisms.

First, a wider point on what this proposal bri= ngs with regards to pinning, to the best of my knowledge.

A pinning = may have different vectors by exploiting a) mempools limits (e.g descendant= s) or b) mempools absolute-fee/feerate/conflicts logic. The lack of a globa= l mempool means you can creatively combine them to provoke mempools-partiti= ons [0]

As far as I understand this proposal, it aims to solve the c= lass a) of pinnings by allowing fee-bumping with a new definition of depend= encies. I'm not sure it achieves to do=C2=A0 so as the Sponsor Vector T= XIDs being committed in the Sponsoree signature hash means the Sponsor feer= ate is part of this commitment and can't be unilaterally adjusted to ac= tual mempool-congestion.

After broadcasting the Sponsor/Sponsoree p= air, mempools feerate may increase again and thus obsoleting the previous f= ee-bump. Or you need a Sponsor Vector for every blockspace feerate, in the = worst-case bound by the value of the Sponsoree funds.

Further, I wou= ld say this proposal won't solve class b) of pinnings for multi-party t= ime-sensitive protocols without further modifications. E.g in a LN-channel,= assuming the commitment transaction is the Sponsoree, Alice the honest par= ty can't increase Sponsor feerate by mal eating its outputs without bre= aking the sponsoring dependency. And thus evict a Bob's malicious pin a= cross network mempools.

I think a further softfork proposal with reg= ards to sighash malleability is needed to achieve the security semantic for= Lightning type of protocols. Roughly, a SIGHASH_IOVECTOR allows N-inputs t= o commit to N-outputs, thus committing to all the balance/HTLC outputs minu= s the last output Vector, non-interactively malleable by channel participan= ts. This would be a form of transaction finalization delegation, allowing A= lice to direct the Sponsor vector to a good-feerate adjusted transaction.
Note, I may have misunderstood completely the proposal as the feerate= observed might be the Sponsor _package_ one and each party could have a pa= ir of outputs to spend from to non-interactively increase the Sponsoree. Th= ough sounds like re-introducing the limits issues...

That said, see = following review points.

> This is insufficient because if new at= tacks are found, there is
> limited ability to deploy fixes for
&g= t; them against deployed contract instances (such as open lightning
>= channels). What is required is a
> fully abstracted primitive that r= equires no special structure from an
> underlying transaction in
&= gt; order to increase fees to confirm the transactions.

This is real= ly true, in case of vulnerability discovered mass closing of the channel wo= uld be in itself a concern as it would congest mempools and open to looter = behaviors [1]. Though I don't think a special structure can claim cover= ing every potential source of vulnerability for=C2=A0 off-chain protocols a= s some of them might be tx-relay based (e.g reject-filters for segwit txn).=

Further, a "fully abstracted primitive" is loosely define= d, one could argue that anchor outputs don't require special structure = from an underlying transaction (i.e on the order of outputs ?).

>= =C2=A0where
n>1, it is interpreted as a vector of TXIDs (Sponsor Vec= tor).

n >=3D1 ? I think you can have at least one vector and this= is matching the code

> If there is another convenient place to p= ut the TXID vector, that's fine too.

You might use the per-input= future Taproot annex, and even apply a witness discount as this mechanism = could be argued to be less blockspace expensive than a CPFP for the same se= mantic.

An alternative could be a new transaction field like a new `= stxid` :

`[nVersion][marker][flag][txins][txouts][witness][nLockTime= ][nSponsor][nVersion][n*STXID]`

It would be cheaper as you likely sa= ve the output amount size and OP_VER. And you don't have to subtract a = dust output + 1 from the other output amount to make sure the Sponsor outpu= t meets dust propagation requirements.

Though it's more demandin= g on the tx-relay layer (new serialization and transaction identifier) and = new a version bump of the signature digest algo to avoid a third-party mall= eating the per-transaction sponsor field

> To prevent garbage spo= nsors, we also require that:

Does the reverse hold ? Garbage Sponsor= ee by breaking the dependency and double-spending the utxo spent by the Spo= nsor and thus decreasing Sponsoree's feerate to mempool bottom. AFAIK y= ou can't do this with CPFP.

> rational miners may wish to per= mit multiple sponsor
> targets, or multiple sponsoring
> transa= ctions,

I'm not sure if your policy sktech prevents multiple 1-S= ponsor-to-N-Sponsoree. Such a scheme would have some edges. A mempool might= receive Sponsoree in different order than evaluated by original sender and= thus allocate the Sponsor feerate to the less-urgent Sponsoree.

>= ; This is treated as a separate
> concern, as any strides on
> = package relay generally should be able to support sponsors trivially.
This is one more reason to carefully version package relay, beyond the tr= ansaction package complexity, you now have a new type of graph dependency t= o scope. What we should be worried about is network mempools partitions bet= ween different mechanisms of incompatible package relay if we implement one= .

Overall, a missing point which is making this proposal = compelling is the fact that you may have one 1-Sponsor-for-N-Sponsoree whic= h is a far reduced cost compared to N-Parent-1-CPFP as the CPFP must includ= e an input for each bumped parent. Here you only have the Sponsor output. T= hus observing input_size > output_size, this proposal is better for mult= i-transactions bumping (but not for N=3D1 as you have to bear the input spe= nding of the Sponsor).

Antoine

[0] Within LN-context, for cla= ss b) see https://lists.linuxfoundation.= org/pipermail/lightning-dev/2020-June/002758.html

[1] See the re= cent Dynamic Commitments proposal to ponder this concern https://lists.linuxfoundation.org/pipermail/lightning-dev/= 2020-July/002763.html

Le=C2=A0ven. 18 sept. 2020 =C3=A0=C2=A02= 0:52, Jeremy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org&= gt; a =C3=A9crit=C2=A0:
Hi Bitcoi=
n Devs,


I'd like to share with you a draft proposal for a mechanism to replace =
CPFP and RBF for
increasing fees on transactions in the mempool that should be more robust a=
gainst attacks.

A reference implementation demonstrating these rules is available
[here](https://github.com/bitcoin/bitcoin/com=
pare/master...JeremyRubin:subsidy-tx) for those who
prefer to not read specs.

Should the mailing list formatting be bungled, it is also available as a gi=
st [here](https://gist.github.com/JeremyRubin/92a9f=
c4c6531817f66c2934282e71fdf).

Non-Destructive TXID Dependencies for Fee Sponsoring
=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=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D

This BIP proposes a general purpose mechanism for expressing non-destructiv=
e (i.e., not requiring
the spending of a coin) dependencies on specific transactions being in the =
same block that can be
used to sponsor fees of remote transactions.

Motivation
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

The mempool has a variety of protections and guards in place to ensure that=
 miners are economic and
to protect the network from denial of service.

The rough surface of these policies has some unintended consequences for se=
cond layer protocol
developers. Applications are either vulnerable to attacks (such as transact=
ion pinning) or must go
through great amounts of careful protocol engineering to guard against know=
n mempool attacks.

This is insufficient because if new attacks are found, there is limited abi=
lity to deploy fixes for
them against deployed contract instances (such as open lightning channels).=
 What is required is a
fully abstracted primitive that requires no special structure from an under=
lying transaction in
order to increase fees to confirm the transactions.

Consensus Specification
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

If a transaction's last output's scripPubKey is of the form OP_VER =
followed by n*32 bytes, where
n>1, it is interpreted as a vector of TXIDs (Sponsor Vector). The Sponso=
r Vector TXIDs  must also be
in the block the transaction is validated in, with no restriction on order =
or on specifying a TXID
more than once. This can be accomplished simply with the following patch:


```diff
+
+    // Extract all required fee dependencies
+    std::unordered_set<uint256, SaltedTxidHasher> dependencies;
+
+    const bool dependencies_enabled =3D VersionBitsState(pindex->pprev,=
 chainparams.GetConsensus(), Consensus::DeploymentPos::DEPLOYMENT_TXID_DEPE=
NDENCY, versionbitscache) =3D=3D ThresholdState::ACTIVE;
+    if (dependencies_enabled) {
+        for (const auto& tx : block.vtx) {
+            // dependency output is if the last output of a txn is OP_VER =
followed by a sequence of 32*n
+            // bytes
+            // vout.back() must exist because it is checked in CheckBlock
+            const CScript& dependencies_script =3D tx->vout.back().=
scriptPubKey;
+            // empty scripts are valid, so be sure we have at least one by=
te
+            if (dependencies_script.size() && dependencies_script[=
0] =3D=3D OP_VER) {
+                const size_t size =3D dependencies_script.size() - 1;
+                if (size % 32 =3D=3D 0 && size > 0) {
+                    for (auto start =3D dependencies_script.begin() +1, st=
op =3D start + 32; start < dependencies_script.end(); start =3D stop, st=
op +=3D 32) {
+                        uint256 txid;
+                        std::copy(start, stop, txid.begin());
+                        dependencies.emplace(txid);
+                    }
+                }
+                // No rules applied otherwise, open for future upgrades
+            }
+        }
+        if (dependencies.size() > block.vtx.size()) {
+            return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, &=
quot;bad-dependencies-too-many-target-txid");
+        }
+    }
+
     for (unsigned int i =3D 0; i < block.vtx.size(); i++)
     {
         const CTransaction &tx =3D *(block.vtx[i]);
+        if (!dependencies.empty()) {
+            dependencies.erase(tx.GetHash());
+        }

         nInputs +=3D tx.vin.size();

@@ -2190,6 +2308,9 @@ bool CChainState::ConnectBlock(const CBlock& bloc=
k, BlockValidationState& state,
         }
         UpdateCoins(tx, view, i =3D=3D 0 ? undoDummy : blockundo.vtxundo.b=
ack(), pindex->nHeight);
     }
+    if (!dependencies.empty()) {
+        return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, "=
;bad-dependency-missing-target-txid");
+    }
```

### Design Motivation
The final output of a transaction is an unambiguous location to attach meta=
data to a transaction
such that the data is available for transaction validation. This data could=
 be committed to anywhere,
with added implementation complexity, or in the case of Taproot annexes, in=
compatibility with
non-Taproot addresses (although this is not a concern for sponsoring a tran=
saction that does not use
Taproot).

A bare scriptPubKey prefixed with OP_VER is defined to be invalid in any co=
ntext, and is trivially
provably unspendable and therefore pruneable.

If there is another convenient place to put the TXID vector, that's fin=
e too.

As the output type is non-standard, unupgraded nodes will by default not in=
clude Transactions
containing them in the mempool, limiting risk of an upgrade via this mechan=
ism.

Policy Specification
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

The mechanism proposed above is a general specification for inter-transacti=
on dependencies.

In this BIP, we only care to ensure a subset of behavior sufficient to repl=
ace CPFP and RBF for fee
bumping.

Thus we restrict the mempool policy such that:

1. No Transaction with a Sponsor Vector may have any child spends; and
1. No Transaction with a Sponsor Vector may have any unconfirmed parents; a=
nd
1. The Sponsor Vector must have exactly 1 entry; and
1. The Sponsor Vector's entry must be present in the mempool; and
1. Every Transaction may have exactly 1 sponsor in the mempool; except
1. Transactions with a Sponsor Vector may not be sponsored.


The mempool treats ancestors and descendants limits as follows:

1. Sponsors are counted as children transactions for descendants; but
1. Sponsoring transactions are exempted from any limits saturated at the ti=
me of submission.

This ensures that within a given package, every child transaction may have =
a sponsor, but that the
mempool prefers to not accept new true children while there are parents tha=
t can be cleared.

To prevent garbage sponsors, we also require that:

1. The Sponsor's feerate must be greater than the Sponsored's ances=
tor fee rate

We allow one Sponsor to replace another subject to normal replacement polic=
ies, they are treated as
conflicts.


### Design Motivation

There are a few other ways to use OP_VER sponsors that are not included. Fo=
r instance, one could
make child chains that are only valid if their parent is in the same block =
(this is incompatible
with CTV, exercise left to reader). These use cases are in a sense incident=
al to the motivation
of this mechanism, and add a lot of implementation complexity.

What is wanted is a minimal mechanism that allows arbitrary unconnected thi=
rd parties to attach
fees to an arbitrary transaction. The set of rules given tightly bounds how=
 much extra work the
mempool might have to do to account for the new sponsors in the worst case,=
 while providing a "it
always works" API for end users that is not subject to traditional iss=
ues around pinning.

Eventually, rational miners may wish to permit multiple sponsor targets, or=
 multiple sponsoring
transactions, but they are not required for the mechanism to work. This is =
a benefit of the
minimality of the consensus rule, it is compatible with future policy shoul=
d it be implemented.


#### Attack Analysis of new Policy

In the worst case the new policy can lead to a 1/2 reduction in the number =
of children allowed
(e.g., if there are 13 children submitted, then 12 sponsors, the 25 child l=
imit will saturate
before) and a 2x increase in the maximum children (e.g., if there are 25 ch=
ildren submitted, and
then each are sponsored). Importantly, even in the latter attack scenario, =
the DoS surface is not
great because the sponsor transactions have no children nor parents.

#### Package Relay/Orphan Pool

Future policy work might be able to insert sponsors into a special sponsor =
pool with an eviction
policy that would enable sponsors to be queried and tracked for transaction=
s that have too low fee
to enter the mempool in the first place. This is treated as a separate conc=
ern, as any strides on
package relay generally should be able to support sponsors trivially.

Reference Implementation
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
A reference implementation demonstrating these rules is available
[here](https://github.com/bitcoin/bitcoin/com=
pare/master...JeremyRubin:subsidy-tx). This is a best
effort implementation, but has not been carefully audited for correctness a=
nd likely diverges from
this document in ways that should either be reflected in this document or a=
mended in the code.


Best,

Jeremy

_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000eae76705afaf6b1a--