MIME-Version: 1.0
References: <CAD5xwhi6+Q-UX2xVnD4TE9uEbe-omQ748tpJJpYdrMNnG6D5vA@mail.gmail.com>
In-Reply-To: <CAD5xwhi6+Q-UX2xVnD4TE9uEbe-omQ748tpJJpYdrMNnG6D5vA@mail.gmail.com>
Reply-To: lists@coryfields.com
From: Cory Fields <lists@coryfields.com>
Date: Fri, 18 Sep 2020 21:39:16 -0400
Message-ID: <CAApLimiFXmX6OPe6wsvvV3YeL8i0-Y7RVvugzLBeADh3go-BzQ@mail.gmail.com>
To: Jeremy <jlrubin@mit.edu>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000182c9e05afa0b029"
Subject: Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive
 TXID Dependencies for Fee Sponsoring
Precedence: list

--000000000000182c9e05afa0b029
Content-Type: text/plain; charset="UTF-8"

Conceptually this is so simple and explicit it almost seems like an obvious
primitive.

Glossing over some of the design/policy decisions...

I wonder what the real-world privacy implications are due to the
dependencies now being encoded on-chain rather than requiring some effort
to watch the mempool?

Cory

On Fri, Sep 18, 2020, 20:52 Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Hi Bitcoin 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 against attacks.
>
> A reference implementation demonstrating these rules is available
> [here](https://github.com/bitcoin/bitcoin/compare/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 gist [here](https://gist.github.com/JeremyRubin/92a9fc4c6531817f66c2934282e71fdf).
>
> Non-Destructive TXID Dependencies for Fee Sponsoring
> ====================================================
>
> This BIP proposes a general purpose mechanism for expressing non-destructive (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
> ==========
>
> 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 second layer protocol
> developers. Applications are either vulnerable to attacks (such as transaction pinning) or must go
> through great amounts of careful protocol engineering to guard against known 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 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.
>
> Consensus Specification
> =======================
>
> 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 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. 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 = VersionBitsState(pindex->pprev, chainparams.GetConsensus(), Consensus::DeploymentPos::DEPLOYMENT_TXID_DEPENDENCY, versionbitscache) == 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 = tx->vout.back().scriptPubKey;
> +            // empty scripts are valid, so be sure we have at least one byte
> +            if (dependencies_script.size() && dependencies_script[0] == OP_VER) {
> +                const size_t size = dependencies_script.size() - 1;
> +                if (size % 32 == 0 && size > 0) {
> +                    for (auto start = dependencies_script.begin() +1, stop = start + 32; start < dependencies_script.end(); start = stop, stop += 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 = 0; i < block.vtx.size(); i++)
>      {
>          const CTransaction &tx = *(block.vtx[i]);
> +        if (!dependencies.empty()) {
> +            dependencies.erase(tx.GetHash());
> +        }
>
>          nInputs += tx.vin.size();
>
> @@ -2190,6 +2308,9 @@ bool CChainState::ConnectBlock(const CBlock& block, BlockValidationState& state,
>          }
>          UpdateCoins(tx, view, i == 0 ? undoDummy : blockundo.vtxundo.back(), 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 metadata 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, incompatibility with
> non-Taproot addresses (although this is not a concern for sponsoring a transaction 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 mechanism.
>
> Policy Specification
> ====================
>
> The mechanism proposed above is a general specification for inter-transaction dependencies.
>
> In this BIP, we only care to ensure a subset of behavior sufficient to replace 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 have 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 fee rate
>
> We allow one Sponsor to replace another subject to normal replacement policies, 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 block (this is incompatible
> with CTV, exercise left to reader). These use cases are in a sense incidental 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 case, 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 is a benefit of the
> minimality of the consensus rule, it is compatible with future policy should 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 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 sponsor pool with an eviction
> policy that would enable sponsors to be queried and tracked for transactions that have too low fee
> to enter the mempool in the first place. This is treated as a separate concern, as any strides on
> package relay generally should be able to support sponsors trivially.
>
> Reference Implementation
> ========================
> A reference implementation demonstrating these rules is available
> [here](https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:subsidy-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
>

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

<div dir=3D"auto"><div>Conceptually this is so simple and explicit it almos=
t seems like an obvious primitive.</div><div dir=3D"auto"><br></div><div di=
r=3D"auto">Glossing over some of the design/policy decisions...<br><div dir=
=3D"auto"><br></div><div dir=3D"auto">I wonder what the real-world privacy =
implications are due to the dependencies now being encoded on-chain rather =
than requiring some effort to watch the mempool?=C2=A0</div><div dir=3D"aut=
o"><br></div>Cory<br><br><div class=3D"gmail_quote" dir=3D"auto"><div dir=
=3D"ltr" class=3D"gmail_attr">On Fri, Sep 18, 2020, 20:52 Jeremy via bitcoi=
n-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=
=3D"_blank" rel=3D"noreferrer">bitcoin-dev@lists.linuxfoundation.org</a>&gt=
; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .=
8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"ltr"><div clas=
s=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-si=
ze:small;color:#000000"><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" rel=3D"noreferrer noreferrer" target=3D"_blank">https://=
github.com/bitcoin/bitcoin/compare/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" rel=3D"noreferrer noreferrer" target=3D"_blank">https://gis=
t.github.com/JeremyRubin/92a9fc4c6531817f66c2934282e71fdf</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" rel=3D"noreferrer noreferrer" target=3D"_blank">https://=
github.com/bitcoin/bitcoin/compare/master...JeremyRubin:subsidy-tx</a>). Th=
is 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" data-smartmail=3D"gmail=
_signature"><div dir=3D"ltr">--<br><a href=3D"https://twitter.com/JeremyRub=
in" rel=3D"noreferrer noreferrer" target=3D"_blank">@JeremyRubin</a><a href=
=3D"https://twitter.com/JeremyRubin" rel=3D"noreferrer noreferrer" target=
=3D"_blank"></a></div></div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" rel=3D"noreferrer =
noreferrer" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">https://lists.li=
nuxfoundation.org/mailman/listinfo/bitcoin-dev</a><br>
</blockquote></div></div></div>

--000000000000182c9e05afa0b029--