MIME-Version: 1.0
References: <CAD5xwhi6+Q-UX2xVnD4TE9uEbe-omQ748tpJJpYdrMNnG6D5vA@mail.gmail.com>
In-Reply-To: <CAD5xwhi6+Q-UX2xVnD4TE9uEbe-omQ748tpJJpYdrMNnG6D5vA@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Sat, 19 Sep 2020 14:39:41 -0400
Message-ID: <CALZpt+FbRGrcW7LZY=4NtR9w4CP=kavVdqutfrX86OYnouHUJg@mail.gmail.com>
To: Jeremy <jlrubin@mit.edu>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000006bf32f05afaef130"
Subject: Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive
 TXID Dependencies for Fee Sponsoring
Precedence: list

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

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 lack
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 committed
in the Sponsoree signature hash means the Sponsor feerate is part of this
commitment and can't be unilaterally adjusted to actual mempool-congestion.

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 the
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 in
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 protocols.
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 can
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 the
code

> If there is another convenient place to put 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 semantic.

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

`[nVersion][marker][flag][txins][txouts][witness][nLockTime][nSponsor][nVer=
sion][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 requirements.

Though it's more demanding 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 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 dependency
to scope. What we should be worried about is network mempools partitions
between 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 which is a far reduced
cost compared to N-Parent-1-CPFP as the CPFP must include an input for each
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/002758.=
html

[1] See the recent Dynamic Commitments proposal to ponder this concern
https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-July/002763.=
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 CP=
FP and RBF for
> increasing fees on transactions in the mempool that should be more robust=
 against attacks.
>
> A reference implementation demonstrating these rules is available
> [here](https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:su=
bsidy-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/92a9fc4c6531817f66c2934282e=
71fdf).
>
> 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-destruct=
ive (i.e., not requiring
> the spending of a coin) dependencies on specific transactions being in th=
e 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 th=
at 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 transa=
ction pinning) or must go
> through great amounts of careful protocol engineering to guard against kn=
own mempool attacks.
>
> This is insufficient because if new attacks are found, there is limited a=
bility 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 und=
erlying 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 follow=
ed by n*32 bytes, where
> n>1, it is interpreted as a vector of TXIDs (Sponsor Vector). The Sponsor=
 Vector TXIDs  must also be
> in the block the transaction is validated in, with no restriction on orde=
r 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_DEPEN=
DENCY, 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_VE=
R followed by a sequence of 32*n
> +            // bytes
> +            // vout.back() must exist because it is checked in CheckBloc=
k
> +            const CScript& dependencies_script =3D tx->vout.back().scrip=
tPubKey;
> +            // 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, sto=
p +=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.vtxundo=
.back(), pindex->nHeight);
>      }
> +    if (!dependencies.empty()) {
> +        return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, "ba=
d-dependency-missing-target-txid");
> +    }
> ```
>
> ### Design Motivation
> The final output of a transaction is an unambiguous location to attach me=
tadata to a transaction
> such that the data is available for transaction validation. This data cou=
ld 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 tr=
ansaction 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 mech=
anism.
>
> 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-transac=
tion dependencies.
>
> In this BIP, we only care to ensure a subset of behavior sufficient to re=
place 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 hav=
e a sponsor, but that the
> mempool prefers to not accept new true children while there are parents t=
hat can be cleared.
>
> To prevent garbage sponsors, we also require that:
>
> 1. The Sponsor's feerate must be greater than the Sponsored's ancestor fe=
e rate
>
> We allow one Sponsor to replace another subject to normal replacement pol=
icies, 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 bloc=
k (this is incompatible
> with CTV, exercise left to reader). These use cases are in a sense incide=
ntal to the motivation
> of this mechanism, and add a lot of implementation complexity.
>
> What is wanted is a minimal mechanism that allows arbitrary unconnected t=
hird parties to attach
> fees to an arbitrary transaction. The set of rules given tightly bounds h=
ow much extra work the
> mempool might have to do to account for the new sponsors in the worst cas=
e, while providing a "it
> always works" API for end users that is not subject to traditional issues=
 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 i=
s a benefit of the
> minimality of the consensus rule, it is compatible with future policy sho=
uld it be implemented.
>
>
> #### Attack Analysis of new Policy
>
> In the worst case the new policy can lead to a 1/2 reduction in the numbe=
r of children allowed
> (e.g., if there are 13 children submitted, then 12 sponsors, the 25 child=
 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 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 sponso=
r pool with an eviction
> policy that would enable sponsors to be queried and tracked for transacti=
ons that have too low fee
> to enter the mempool in the first place. This is treated as a separate co=
ncern, 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:su=
bsidy-tx). This is a best
> effort implementation, but has not been carefully audited for correctness=
 and likely diverges from
> this document in ways that should either be reflected in this document or=
 amended in the code.
>
>
> Best,
>
> Jeremy
>
>
>
> --
> @JeremyRubin <https://twitter.com/JeremyRubin>
> <https://twitter.com/JeremyRubin>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

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

<div dir=3D"ltr"><div>Hi Jeremy,<br><br>This is a really interesting propos=
al to widen the scope of fee mechanisms. <br><br>First, a wider point on wh=
at this proposal brings with regards to pinning, to the best of my knowledg=
e.<br><br>A pinning may have different vectors by exploiting a) mempools li=
mits (e.g descendants) or b) mempools absolute-fee/feerate/conflicts logic.=
 The lack of a global mempool means you can creatively combine them to prov=
oke mempools-partitions [0]<br><br>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&#39;m not sure it achieves to do=C2=A0 so as =
the Sponsor Vector TXIDs being committed in the Sponsoree signature hash me=
ans the Sponsor feerate is part of this commitment and can&#39;t be unilate=
rally adjusted to actual mempool-congestion. <br><br>After broadcasting the=
 Sponsor/Sponsoree pair, mempools feerate may increase again and thus obsol=
eting the previous fee-bump. Or you need a Sponsor Vector for every blocksp=
ace feerate, in the worst-case bound by the value of the Sponsoree funds.<b=
r><br>Further, I would say this proposal won&#39;t solve class b) of pinnin=
gs for multi-party time-sensitive protocols without further modifications. =
E.g in a LN-channel, assuming the commitment transaction is the Sponsoree, =
Alice the honest party can&#39;t increase Sponsor feerate by mal eating its=
 outputs without breaking the sponsoring dependency. And thus evict a Bob&#=
39;s malicious pin across network mempools.<br><br>I think a further softfo=
rk proposal with regards to sighash malleability is needed to achieve the s=
ecurity semantic for Lightning type of protocols. Roughly, a SIGHASH_IOVECT=
OR allows N-inputs to commit to N-outputs, thus committing to all the balan=
ce/HTLC outputs minus the last output Vector, non-interactively malleable b=
y channel participants. This would be a form of transaction finalization de=
legation, allowing Alice to direct the Sponsor vector to a good-feerate adj=
usted transaction.<br><br>Note, I may have misunderstood completely the pro=
posal as the feerate observed might be the Sponsor _package_ one and each p=
arty could have a pair of outputs to spend from to non-interactively increa=
se the Sponsoree. Though sounds like re-introducing the limits issues...<br=
><br>That said, see following review points.<br><br>&gt; This is insufficie=
nt because if new attacks are found, there is<br>&gt; limited ability to de=
ploy fixes for<br>&gt; them against deployed contract instances (such as op=
en lightning<br>&gt; channels). What is required is a<br>&gt; fully abstrac=
ted primitive that requires no special structure from an<br>&gt; underlying=
 transaction in<br>&gt; order to increase fees to confirm the transactions.=
<br><br>This is really true, in case of vulnerability discovered mass closi=
ng of the channel would be in itself a concern as it would congest mempools=
 and open to looter behaviors [1]. Though I don&#39;t think a special struc=
ture can claim covering every potential source of vulnerability for=C2=A0 o=
ff-chain protocols as some of them might be tx-relay based (e.g reject-filt=
ers for segwit txn).<br><br>Further, a &quot;fully abstracted primitive&quo=
t; is loosely defined, one could argue that anchor outputs don&#39;t requir=
e special structure from an underlying transaction (i.e on the order of out=
puts ?).<br><br>&gt; =C2=A0where<br>n&gt;1, it is interpreted as a vector o=
f TXIDs (Sponsor Vector).<br><br>n &gt;=3D1 ? I think you can have at least=
 one vector and this is matching the code<br><br>&gt; If there is another c=
onvenient place to put the TXID vector, that&#39;s fine too.<br><br>You mig=
ht use the per-input future Taproot annex, and even apply a witness discoun=
t as this mechanism could be argued to be less blockspace expensive than a =
CPFP for the same semantic.<br><br>An alternative could be a new transactio=
n field like a new `stxid` :<br><br>`[nVersion][marker][flag][txins][txouts=
][witness][nLockTime][nSponsor][nVersion][n*STXID]`<br><br>It would be chea=
per as you likely save the output amount size and OP_VER. And you don&#39;t=
 have to subtract a dust output + 1 from the other output amount to make su=
re the Sponsor output meets dust propagation requirements.<br><br>Though it=
&#39;s more demanding on the tx-relay layer (new serialization and transact=
ion identifier) and new a version bump of the signature digest algo to avoi=
d a third-party malleating the per-transaction sponsor field<br><br>&gt; To=
 prevent garbage sponsors, we also require that:<br><br>Does the reverse ho=
ld ? Garbage Sponsoree by breaking the dependency and double-spending the u=
txo spent by the Sponsor and thus decreasing Sponsoree&#39;s feerate to mem=
pool bottom. AFAIK you can&#39;t do this with CPFP.<br><br>&gt; rational mi=
ners may wish to permit multiple sponsor<br>&gt; targets, or multiple spons=
oring<br>&gt; transactions,<br><br>I&#39;m not sure if your policy sktech p=
revents multiple 1-Sponsor-to-N-Sponsoree. Such a scheme would have some ed=
ges. A mempool might receive Sponsoree in different order than evaluated by=
 original sender and thus allocate the Sponsor feerate to the less-urgent S=
ponsoree.<br><br>&gt; This is treated as a separate<br>&gt; concern, as any=
 strides on<br>&gt; package relay generally should be able to support spons=
ors trivially.<br><br>This is one more reason to carefully version package =
relay, beyond the transaction package complexity, you now have a new type o=
f graph dependency to scope. What we should be worried about is network mem=
pools partitions between different mechanisms of incompatible package relay=
 if we implement one.<br></div><div><br>Overall, a missing point which is m=
aking this proposal compelling is the fact that you may have one 1-Sponsor-=
for-N-Sponsoree which is a far reduced cost compared to N-Parent-1-CPFP as =
the CPFP must include an input for each bumped parent. Here you only have t=
he Sponsor output. Thus observing input_size &gt; output_size, this proposa=
l is better for multi-transactions bumping (but not for N=3D1 as you have t=
o bear the input spending of the Sponsor).<br><br>Antoine<br><br>[0] Within=
 LN-context, for class b) see <a href=3D"https://lists.linuxfoundation.org/=
pipermail/lightning-dev/2020-June/002758.html">https://lists.linuxfoundatio=
n.org/pipermail/lightning-dev/2020-June/002758.html</a><br><br>[1] See the =
recent Dynamic Commitments proposal to ponder this concern <a href=3D"https=
://lists.linuxfoundation.org/pipermail/lightning-dev/2020-July/002763.html"=
>https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-July/002763=
.html</a><br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" cl=
ass=3D"gmail_attr">Le=C2=A0ven. 18 sept. 2020 =C3=A0=C2=A020:52, Jeremy via=
 bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">b=
itcoin-dev@lists.linuxfoundation.org</a>&gt; a =C3=A9crit=C2=A0:<br></div><=
blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l=
eft:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><div clas=
s=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-si=
ze:small;color:rgb(0,0,0)"><pre>Hi Bitcoin Devs,


I&#39;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](<a href=3D"https://github.com/bitcoin/bitcoin/compare/master...Jerem=
yRubin:subsidy-tx" target=3D"_blank">https://github.com/bitcoin/bitcoin/com=
pare/master...JeremyRubin:subsidy-tx</a>) for those who
prefer to not read specs.

Should the mailing list formatting be bungled, it is also available as a gi=
st [here](<a href=3D"https://gist.github.com/JeremyRubin/92a9fc4c6531817f66=
c2934282e71fdf" target=3D"_blank">https://gist.github.com/JeremyRubin/92a9f=
c4c6531817f66c2934282e71fdf</a>).

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&#39;s last output&#39;s scripPubKey is of the form OP_VER =
followed by n*32 bytes, where
n&gt;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&lt;uint256, SaltedTxidHasher&gt; dependencies;
+
+    const bool dependencies_enabled =3D VersionBitsState(pindex-&gt;pprev,=
 chainparams.GetConsensus(), Consensus::DeploymentPos::DEPLOYMENT_TXID_DEPE=
NDENCY, versionbitscache) =3D=3D ThresholdState::ACTIVE;
+    if (dependencies_enabled) {
+        for (const auto&amp; 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&amp; dependencies_script =3D tx-&gt;vout.back().=
scriptPubKey;
+            // empty scripts are valid, so be sure we have at least one by=
te
+            if (dependencies_script.size() &amp;&amp; dependencies_script[=
0] =3D=3D OP_VER) {
+                const size_t size =3D dependencies_script.size() - 1;
+                if (size % 32 =3D=3D 0 &amp;&amp; size &gt; 0) {
+                    for (auto start =3D dependencies_script.begin() +1, st=
op =3D start + 32; start &lt; 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() &gt; block.vtx.size()) {
+            return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, &=
quot;bad-dependencies-too-many-target-txid&quot;);
+        }
+    }
+
     for (unsigned int i =3D 0; i &lt; block.vtx.size(); i++)
     {
         const CTransaction &amp;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&amp; bloc=
k, BlockValidationState&amp; state,
         }
         UpdateCoins(tx, view, i =3D=3D 0 ? undoDummy : blockundo.vtxundo.b=
ack(), pindex-&gt;nHeight);
     }
+    if (!dependencies.empty()) {
+        return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, &quot=
;bad-dependency-missing-target-txid&quot;);
+    }
```

### 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&#39;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&#39;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&#39;s feerate must be greater than the Sponsored&#39;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 &quot;it
always works&quot; 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](<a href=3D"https://github.com/bitcoin/bitcoin/compare/master...Jerem=
yRubin:subsidy-tx" target=3D"_blank">https://github.com/bitcoin/bitcoin/com=
pare/master...JeremyRubin:subsidy-tx</a>). 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

</pre></div><br clear=3D"all"><div><div dir=3D"ltr"><div dir=3D"ltr">--<br>=
<a href=3D"https://twitter.com/JeremyRubin" target=3D"_blank">@JeremyRubin<=
/a><a href=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div>=
</div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>

--0000000000006bf32f05afaef130--