[bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 8979 bytes --]

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>

[-- Attachment #2: Type: text/html, Size: 9874 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Cory Fields]

[-- Attachment #1: Type: text/plain, Size: 9902 bytes --]

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
>

[-- Attachment #2: Type: text/html, Size: 11336 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 2040 bytes --]

On Fri, Sep 18, 2020 at 05:51:39PM -0700, Jeremy via bitcoin-dev wrote:
> 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.

Interesting idea!  This is going to take a while to think about, but I
have one immediate question:

> 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.

Is this in the reference implementation?  I don't see it and I'm
confused by this text.  I think it could mean either:

1. Sponsor Tx A can be replaced by Sponsor Tx B if A and B have at least
   one input in common (which is part of the "normal replacement policies")

2. A can be replaced by B even if they don't have any inputs in common
   as long as they do have a Sponsor Vector in common (while otherwise
   using the "normal replacement policies").

In the first case, I think Mallory can prevent Bob from
sponsor-fee-bumping (sponsor-bumping?) his transaction by submitting a
sponsor before he does; since Bob has no control over Mallory's inputs,
he can't replace Mallory's sponsor tx.

In the second case, I think Mallory can use an existing pinning
technique to make it expensive for Bob to fee bump.  The normal
replacement policies require a replacement to pay an absolute higher fee
than the original transaction, so Mallory can create a 100,000 vbyte
transaction with a single-vector sponsor at the end pointing to Bob's
transaction.  This sponsor transaction pays the same feerate as Bob's
transaction---let's say 50 nBTC/vbyte, so 5 mBTC total fee.  In order
for Bob to replace Mallory's sponsor transaction with his own sponsor
transaction, Bob needs to pay the incremental relay feerate (10
nBTC/vbyte) more, so 6 mBTC total ($66 at $11k/BTC).

Thanks,

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[nopara73]

[-- Attachment #1: Type: text/plain, Size: 2487 bytes --]

Wouldn't this enable a passive adversary listening the mempool to associate
unrelated TXO clusters to the same user?

On Sat, Sep 19, 2020, 15:38 David A. Harding via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> On Fri, Sep 18, 2020 at 05:51:39PM -0700, Jeremy via bitcoin-dev wrote:
> > 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.
>
> Interesting idea!  This is going to take a while to think about, but I
> have one immediate question:
>
> > 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.
>
> Is this in the reference implementation?  I don't see it and I'm
> confused by this text.  I think it could mean either:
>
> 1. Sponsor Tx A can be replaced by Sponsor Tx B if A and B have at least
>    one input in common (which is part of the "normal replacement policies")
>
> 2. A can be replaced by B even if they don't have any inputs in common
>    as long as they do have a Sponsor Vector in common (while otherwise
>    using the "normal replacement policies").
>
> In the first case, I think Mallory can prevent Bob from
> sponsor-fee-bumping (sponsor-bumping?) his transaction by submitting a
> sponsor before he does; since Bob has no control over Mallory's inputs,
> he can't replace Mallory's sponsor tx.
>
> In the second case, I think Mallory can use an existing pinning
> technique to make it expensive for Bob to fee bump.  The normal
> replacement policies require a replacement to pay an absolute higher fee
> than the original transaction, so Mallory can create a 100,000 vbyte
> transaction with a single-vector sponsor at the end pointing to Bob's
> transaction.  This sponsor transaction pays the same feerate as Bob's
> transaction---let's say 50 nBTC/vbyte, so 5 mBTC total fee.  In order
> for Bob to replace Mallory's sponsor transaction with his own sponsor
> transaction, Bob needs to pay the incremental relay feerate (10
> nBTC/vbyte) more, so 6 mBTC total ($66 at $11k/BTC).
>
> Thanks,
>
> -Dave
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 3244 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 825 bytes --]

Hi Cory!

Thanks for taking a look. CC nopara as I think your questions are the same.

I think there are a few reason we won't see functionally worse privacy:

1. RBF/CPFP may require the use of an external to the original transaction
to pay sufficient fee.
2. RBF/CPFP may leak which address was the change and which was the payment.

In addition, I think there is a benefit in that:

1. RBF/CPFP requires access to the keys in the same 'security zone' as the
payment you made (e.g., if it's a multi-sig to multi-sig requires m of N to
cpfp/or RBF, whereas sponsors could be anyone).
2. Sponsors can be a fully separate arbitrary wallet.
3. You can continually coinjoin the funds in your fee-paying wallet without
tainting your main funds.
4. You can keep those funds in a lightning channel and pay your fees via
loop outs.

[-- Attachment #2: Type: text/html, Size: 2919 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 1925 bytes --]

Hi David!

Thanks for taking a look, and great question.

> Is this in the reference implementation?

It is indeed in the reference implementation. Please see
https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:subsidy-tx#diff-24efdb00bfbe56b140fb006b562cc70bR741-R743

There is no requirement that there be any input in common, just that the
sponsor vectors are identical (keep in mind that we limit our sponsor
vector by policy to 1 element, because, as you rightfully point out,
multiple sponsors is more complex to implement).


> In the second case, I think Mallory can use an existing pinning
> technique to make it expensive for Bob to fee bump.  The normal
> replacement policies require a replacement to pay an absolute higher fee
> than the original transaction, so Mallory can create a 100,000 vbyte
> transaction with a single-vector sponsor at the end pointing to Bob's
> transaction.  This sponsor transaction pays the same feerate as Bob's
> transaction---let's say 50 nBTC/vbyte, so 5 mBTC total fee.  In order
> for Bob to replace Mallory's sponsor transaction with his own sponsor
> transaction, Bob needs to pay the incremental relay feerate (10
> nBTC/vbyte) more, so 6 mBTC total ($66 at $11k/BTC).

Yup, I was aware of this limitation but I'm not sure how practical it is as
an attack because it's quite expensive for the attacker. But there are a
few simple policies that can eliminate it:

1) A Sponsoring TX never needs to be more than, say, 2 inputs and 2
outputs. Restricting this via policy would help, or more flexibly limiting
the total size of a sponsoring paying transaction to 1000 bytes.
2) Make A Sponsoring TX not need to pay more absolute fee, just needs to
increase the feerate (perhaps with a constant relay fee bump to prevent
spam).

I think 1) is simpler and should allow full use of the sponsor mechanism
while preventing this class of issue mostly.

What do you think?

[-- Attachment #2: Type: text/html, Size: 4668 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 1267 bytes --]

On Sat, Sep 19, 2020 at 09:30:56AM -0700, Jeremy wrote:
> Yup, I was aware of this limitation but I'm not sure how practical it is as
> an attack because it's quite expensive for the attacker. 

It's cheap if:

1. You were planning to consolidate all those UTXOs at roughly that
   feerate anyway.

2. After you no longer need your pinning transaction in the mempool, you
   make an out-of-band arrangement with a pool to mine a small
   conflicting transaction.

> But there are a few simple policies that can eliminate it:
> 
> 1) A Sponsoring TX never needs to be more than, say, 2 inputs and 2
> outputs. Restricting this via policy would help, or more flexibly
> limiting the total size of a sponsoring transaction to 1000 bytes.

I think that works (as policy).

> 2) Make A Sponsoring TX not need to pay more absolute fee, just needs to
> increase the feerate (perhaps with a constant relay fee bump to prevent
> spam).

I think it'd be hard to find a constant relay fee bump amount that was
high enough to prevent abuse but low enough not to unduly hinder
legitimate users.

> I think 1) is simpler and should allow full use of the sponsor mechanism
> while preventing this class of issue mostly.

Agreed.

Thanks,

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 15960 bytes --]

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 >=1 ? 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][nVersion][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=1 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 à 20:52, Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> 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
>

[-- Attachment #2: Type: text/html, Size: 17238 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 16839 bytes --]

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 à 14:39, Antoine Riard <antoine.riard@gmail.com> a
écrit :

> 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 >=1 ? 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][nVersion][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=1 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 à 20:52, Jeremy via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> a écrit :
>
>> 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
>>
>

[-- Attachment #2: Type: text/html, Size: 18074 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 1851 bytes --]

Antoine,

Yes I think you're a bit confused on where the actual sponsor vector is. If
you have a transaction chain A->B->C and a sponsor S_A, S_A commits to txid
A and A is unaware of S.


W.r.t your other points, I fully agree that the 1-to-N sponsored case is
very compelling. The consensus rules are clear that sponsor commitments are
non-rival, so there's no issue with allowing as many sponsors as possible
and including them in aggregate. E.g., if S_A and S'_A both sponsor A with
feerate(S*) > feerate(A), there's no reason not to include all of them in a
block. The only issue is denial of service in the mempool. In the future,
it would definitely be desirable to figure out rules that allow mempools to
track both multiple sponsors and multiple sponsor targets. But in the
interest of KISS, the current policy rules are designed to be minimally
invasive and maximally functional.

In terms of location for the sponsor vector, I'm relatively indifferent.
The annex is a possible location, but it's a bit odd as we really only need
to allow one such vector per tx, not one per input, and one per input would
enable some new use cases (maybe good, maybe bad). Further, being in the
witness space would mean that if two parties create a 2 input transaction
with a desired sponsor vector they would both need to specify it as you
can't sign another input's witness data. I wholeheartedly agree with the
sentiment though; there could be a more efficient place to put this data,
but nothing jumps out to me as both efficient and simple in implementation
(a new tx-level field sounds like a lot of complexity).


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

yes, this has been fixed in the gist (cred to Dmitry Petukhov for pointing
it out first), but is correct in the code. Thank you for your careful
reading.

[-- Attachment #2: Type: text/html, Size: 3282 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 3794 bytes --]

Right, I was off the shot. Thanks for the explanation.

As you mentioned, if the goal of the sponsor mechanism is to let any party
drive a state N's first tx to completion, you still have the issue of
concurrent states being pinned and thus non-observable for sponsoring by an
honest party.

E.g, Bob can broadcast a thousand of revoked LN states and pin them with
low-feerate sponsors such as these malicious packages absolute fee are
higher than the honest state N. Alice can't fee-sponsor
them as we can assume she hasn't a global view of network mempools. Due to
the proposed policy rule "The Sponsor Vector's entry must be present in the
mempool", Alice's sponsors won't propagate. Even amending this rule, we
can't assume Alice has a thousand of sponsoring utxos to avoid conflict
between her own broadcast.

Of course, offchain protocols designers can limit a participant's
capability to construct a pinning package by constraining its malleability
and thus to always have a compelling feerate. E.g in Lightning you can bind
the size of a commitment transaction by refusing relayed HTLCs and thus
have less HTLC outputs. This security increase comes at the price of less
protocol flexibility, e.g reducing payments throughput.

Further, a malicious counterparty can still take advantage of
mempool-congestion spikes. Even if the pinning package has a compelling
feerate, high enough to bounce off a honest broadcast, there is no
guarantee it stays such. Just after the pinning, congestion can increase
and bury it for long-enough until a timelock expires.

If we want to solve the hard cases of pinning, I still think mempool
acceptance of a whole package only on the merits of feerate is the easiest
solution to reason on.

Le sam. 19 sept. 2020 à 15:46, Jeremy <jlrubin@mit.edu> a écrit :

> Antoine,
>
> Yes I think you're a bit confused on where the actual sponsor vector is.
> If you have a transaction chain A->B->C and a sponsor S_A, S_A commits to
> txid A and A is unaware of S.
>
>
> W.r.t your other points, I fully agree that the 1-to-N sponsored case is
> very compelling. The consensus rules are clear that sponsor commitments are
> non-rival, so there's no issue with allowing as many sponsors as possible
> and including them in aggregate. E.g., if S_A and S'_A both sponsor A with
> feerate(S*) > feerate(A), there's no reason not to include all of them in a
> block. The only issue is denial of service in the mempool. In the future,
> it would definitely be desirable to figure out rules that allow mempools to
> track both multiple sponsors and multiple sponsor targets. But in the
> interest of KISS, the current policy rules are designed to be minimally
> invasive and maximally functional.
>
> In terms of location for the sponsor vector, I'm relatively indifferent.
> The annex is a possible location, but it's a bit odd as we really only need
> to allow one such vector per tx, not one per input, and one per input would
> enable some new use cases (maybe good, maybe bad). Further, being in the
> witness space would mean that if two parties create a 2 input transaction
> with a desired sponsor vector they would both need to specify it as you
> can't sign another input's witness data. I wholeheartedly agree with the
> sentiment though; there could be a more efficient place to put this data,
> but nothing jumps out to me as both efficient and simple in implementation
> (a new tx-level field sounds like a lot of complexity).
>
>
> > n >=1 ? I think you can have at least one vector and this is matching
> the code
>
> yes, this has been fixed in the gist (cred to Dmitry Petukhov for pointing
> it out first), but is correct in the code. Thank you for your careful
> reading.
>
>

[-- Attachment #2: Type: text/html, Size: 5389 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[David A. Harding]

[-- Attachment #1: Type: text/plain, Size: 2330 bytes --]

On Sun, Sep 20, 2020 at 07:10:23PM -0400, Antoine Riard via bitcoin-dev wrote:
> As you mentioned, if the goal of the sponsor mechanism is to let any party
> drive a state N's first tx to completion, you still have the issue of
> concurrent states being pinned and thus non-observable for sponsoring by an
> honest party.
> 
> E.g, Bob can broadcast a thousand of revoked LN states and pin them with
> low-feerate sponsors such as these malicious packages absolute fee are
> higher than the honest state N. Alice can't fee-sponsor
> them as we can assume she hasn't a global view of network mempools. Due to
> the proposed policy rule "The Sponsor Vector's entry must be present in the
> mempool", Alice's sponsors won't propagate. 

Would it make sense that, instead of sponsor vectors
pointing to txids, they point to input outpoints?  E.g.:

1. Alice and Bob open a channel with funding transaction 0123...cdef,
   output 0.

2. After a bunch of state updates, Alice unilaterally broadcasts a
   commitment transaction, which has a minimal fee.

3. Bob doesn't immediately care whether or not Alice tried to close the
   channel in the latest state---he just wants the commitment
   transaction confirmed so that he either gets his money directly or he
   can send any necessary penalty transactions.  So Bob broadcasts a
   sponsor transaction with a vector of 0123...cdef:0

4. Miners can include that sponsor transaction in any block that has a
   transaction with an input of 0123...cdef:0.  Otherwise the sponsor
   transaction is consensus invalid.

(Note: alternatively, sponsor vectors could point to either txids OR
input outpoints.  This complicates the serialization of the vector but
seems otherwise fine to me.)

> If we want to solve the hard cases of pinning, I still think mempool
> acceptance of a whole package only on the merits of feerate is the easiest
> solution to reason on.

I don't think package relay based only on feerate solves RBF transaction
pinning (and maybe also doesn't solve ancestor/dependent limit pinning).
Though, certainly, package relay has the major advantage over this
proposal (IMO) in that it doesn't require any consensus changes.
Package relay is also very nice for fixing other protocol rough edges
that are needed anyway.

-Dave

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 2799 bytes --]

Responses Inline:

Would it make sense that, instead of sponsor vectors
> pointing to txids, they point to input outpoints?  E.g.:
>
> 1. Alice and Bob open a channel with funding transaction 0123...cdef,
>    output 0.
>
> 2. After a bunch of state updates, Alice unilaterally broadcasts a
>    commitment transaction, which has a minimal fee.
>
> 3. Bob doesn't immediately care whether or not Alice tried to close the
>    channel in the latest state---he just wants the commitment
>    transaction confirmed so that he either gets his money directly or he
>    can send any necessary penalty transactions.  So Bob broadcasts a
>    sponsor transaction with a vector of 0123...cdef:0
>
> 4. Miners can include that sponsor transaction in any block that has a
>    transaction with an input of 0123...cdef:0.  Otherwise the sponsor
>    transaction is consensus invalid.
>
> (Note: alternatively, sponsor vectors could point to either txids OR
> input outpoints.  This complicates the serialization of the vector but
> seems otherwise fine to me.)
>

*This seems like a fine suggestion and I think addresses Antoine's issue.*


*I think there are likely some cases where you do want TXID and not Output
(e.g., if you *

*are sponsoring a payment to your locktime'd cold storage wallet (no CPFP)
from an untrusted third party (no RBF), they can grift you into paying for
an unrelated payment). This isn't a concern when the root utxo is multisig
& you are a participant.*

*The serialization to support both, while slightly more complicated, can be
done in a manner that permits future extensibility as well if there are
other modes people require.*



>
> > If we want to solve the hard cases of pinning, I still think mempool
> > acceptance of a whole package only on the merits of feerate is the
> easiest
> > solution to reason on.
>
> I don't think package relay based only on feerate solves RBF transaction
> pinning (and maybe also doesn't solve ancestor/dependent limit pinning).
> Though, certainly, package relay has the major advantage over this
> proposal (IMO) in that it doesn't require any consensus changes.
> Package relay is also very nice for fixing other protocol rough edges
> that are needed anyway.
>
> -Dave
>

*I think it's important to keep in mind this is not a rival to package
relay; I think you also want package relay in addition to this, as they
solve different but related problems.*


*Where you might be able to simplify package relay with sponsors is by
doing a sponsor-only package relay, which is always limited to 2
transactions, 1 sponsor, 1 sponsoree. This would not have some of the
challenges with arbitrary-package package-relay, and would (at least from a
ux perspective) allow users to successfully get parents with insufficient
fee into the mempool.*

[-- Attachment #2: Type: text/html, Size: 5016 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 4618 bytes --]

I think this is a worthy idea as the funding outpoint of any off-chain
protocols is an invariant known by participants. Thus by sponsoring an
outpoint you're requiring from network mempools to increase the feerate of
the package locally known without assuming about the concrete state as any
of them confirming is moving protocol forward.

That said, a malicious counterparty can still broadcast a heavy-weighted
transaction such as an honest party, devoid of knowledge of this weight,
won't attach a sponsor with a fee high enough to timely confirm the
sponsoree. This counterparty capability is a function of package
malleability allowed by the off-chain protocol.

Thus an honest party has to overshoot your bump as a default setting. Now
this is a new concern as such a mechanism can be used as a fee-burning one
by your counterparty. I believe we want a fee-burning equilibrium for any
pinning solution, Mallet shouldn't force Alice to overpay in fee more than
Mallet is ready to feerate-bid in network mempools.

> I don't think package relay based only on feerate solves RBF transaction
> pinning (and maybe also doesn't solve ancestor/dependent limit pinning).

Yes I agree with this. There are some really nasty cases of pinning where
an adversary with knowledge of the tx-relay topology can block your
compelling feerate bids (sponsors/package relay/anchor whatever) from
propagating by leveraging conflicts and RBF logic.

Outbound tx-relay peers rotation which makes the tx-relay topology harder
to observe could help.

Antoine

Le lun. 21 sept. 2020 à 12:27, Jeremy <jlrubin@mit.edu> a écrit :

> Responses Inline:
>
> Would it make sense that, instead of sponsor vectors
>> pointing to txids, they point to input outpoints?  E.g.:
>>
>> 1. Alice and Bob open a channel with funding transaction 0123...cdef,
>>    output 0.
>>
>> 2. After a bunch of state updates, Alice unilaterally broadcasts a
>>    commitment transaction, which has a minimal fee.
>>
>> 3. Bob doesn't immediately care whether or not Alice tried to close the
>>    channel in the latest state---he just wants the commitment
>>    transaction confirmed so that he either gets his money directly or he
>>    can send any necessary penalty transactions.  So Bob broadcasts a
>>    sponsor transaction with a vector of 0123...cdef:0
>>
>> 4. Miners can include that sponsor transaction in any block that has a
>>    transaction with an input of 0123...cdef:0.  Otherwise the sponsor
>>    transaction is consensus invalid.
>>
>> (Note: alternatively, sponsor vectors could point to either txids OR
>> input outpoints.  This complicates the serialization of the vector but
>> seems otherwise fine to me.)
>>
>
> *This seems like a fine suggestion and I think addresses Antoine's issue.*
>
>
> *I think there are likely some cases where you do want TXID and not Output
> (e.g., if you *
>
> *are sponsoring a payment to your locktime'd cold storage wallet (no CPFP)
> from an untrusted third party (no RBF), they can grift you into paying for
> an unrelated payment). This isn't a concern when the root utxo is multisig
> & you are a participant.*
>
> *The serialization to support both, while slightly more complicated, can
> be done in a manner that permits future extensibility as well if there are
> other modes people require.*
>
>
>
>>
>> > If we want to solve the hard cases of pinning, I still think mempool
>> > acceptance of a whole package only on the merits of feerate is the
>> easiest
>> > solution to reason on.
>>
>> I don't think package relay based only on feerate solves RBF transaction
>> pinning (and maybe also doesn't solve ancestor/dependent limit pinning).
>> Though, certainly, package relay has the major advantage over this
>> proposal (IMO) in that it doesn't require any consensus changes.
>> Package relay is also very nice for fixing other protocol rough edges
>> that are needed anyway.
>>
>> -Dave
>>
>
> *I think it's important to keep in mind this is not a rival to package
> relay; I think you also want package relay in addition to this, as they
> solve different but related problems.*
>
>
> *Where you might be able to simplify package relay with sponsors is by
> doing a sponsor-only package relay, which is always limited to 2
> transactions, 1 sponsor, 1 sponsoree. This would not have some of the
> challenges with arbitrary-package package-relay, and would (at least from a
> ux perspective) allow users to successfully get parents with insufficient
> fee into the mempool.*
>
>
>
>
>

[-- Attachment #2: Type: text/html, Size: 6973 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Suhas Daftuar]

[-- Attachment #1: Type: text/plain, Size: 7025 bytes --]

Hi,

I think the topic of how to improve transaction relay policy and fee
bumping is an important one that needs to be worked on, so I'm glad
this is a topic of discussion.  However I am pretty skeptical of this
consensus change proposal:

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.


That means that if a transaction is confirmed in a block without its
sponsor, the sponsor is no longer valid.  This breaks a design principle
that has been discussed many times over the years, which is that once a
valid transaction is created, it should not become invalid later on unless
the inputs are double-spent.  This principle has some logical consequences
that we've come to accept, such as transaction chains being valid across
small reorgs in the absence of malicious (double-spend) behavior.

I think that this principle is a useful one and that there should be a high
bar for doing away with it.  And it seems to me that this proposal doesn't
clear that bar -- the fee bumping improvement that this proposal aims at is
really coming from the policy change, rather than the consensus change. But
if policy changes are the direction we're going to solve these problems, we
could instead just propose new policy rules for the existing types of
transaction chaining that we have, rather than couple them to a new
transaction type.

My understanding of the main benefit of this approach is that this allows
3rd parties to participate in fee bumping.  But that behavior strikes me as
also problematic, because it introduces the possibility of 3rd party
griefing, to the extent that sponsor transactions in any way limit chains
of transactions that would be otherwise permitted.  If Alice sends Bob some
coins, and Alice and Bob are both honest and cooperating, Mallory shouldn't
be able to interfere with their low-feerate transaction by (eg) pinning it
with a large transaction that "sponsors" it (ie a large transaction that is
just above the feerate of the parent, which prevents additional child
transactions and makes it more expensive to RBF).

This last issue of pinning could be improved in this proposal by requiring
that a sponsor transaction bring the effective feerate of its package up to
something which should be confirmed soon (rather than just being a higher
feerate than the tx it is sponsoring).  However, we could also carve out a
policy rule just like that today, without any consensus changes needed, to
help with pinning (which is probably a good idea!  I think this would be
useful work).  So I don't think that approaches in that direction would be
unique to this proposal.

We allow one Sponsor to replace another subject to normal replacement
> policies, they are treated as conflicts.


This policy rule of allowing sponsor transactions to RBF each other also
seems problematic; that means that if Alice is paying Bob in a transaction
that is also sponsoring some other transaction (perhaps from Alice to
someone else), then Mallory can cause the transaction going to Bob to
become invalid by RBF bumping it and sponsoring the parent transaction
herself?  Allowing 3rd parties to interfere with transactions between
others seems like a complex and undesirable design to introduce.

In summary: this proposal seems like a CPFP replacement, requiring many
policy rules along with a consensus change to be worked out to get right; I
think we could achieve largely the same effect by improving the current
policy rules to make CPFP work better without a consensus change.  And
while what is unique about this proposal is that it allows for 3rd parties
to attach themselves to the transaction graph of other parties, I think
that is a complex interaction to introduce and has negative side effects as
well.



On Mon, Sep 21, 2020 at 12:27 PM Jeremy via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Responses Inline:
>
> Would it make sense that, instead of sponsor vectors
>> pointing to txids, they point to input outpoints?  E.g.:
>>
>> 1. Alice and Bob open a channel with funding transaction 0123...cdef,
>>    output 0.
>>
>> 2. After a bunch of state updates, Alice unilaterally broadcasts a
>>    commitment transaction, which has a minimal fee.
>>
>> 3. Bob doesn't immediately care whether or not Alice tried to close the
>>    channel in the latest state---he just wants the commitment
>>    transaction confirmed so that he either gets his money directly or he
>>    can send any necessary penalty transactions.  So Bob broadcasts a
>>    sponsor transaction with a vector of 0123...cdef:0
>>
>> 4. Miners can include that sponsor transaction in any block that has a
>>    transaction with an input of 0123...cdef:0.  Otherwise the sponsor
>>    transaction is consensus invalid.
>>
>> (Note: alternatively, sponsor vectors could point to either txids OR
>> input outpoints.  This complicates the serialization of the vector but
>> seems otherwise fine to me.)
>>
>
> *This seems like a fine suggestion and I think addresses Antoine's issue.*
>
>
> *I think there are likely some cases where you do want TXID and not Output
> (e.g., if you *
>
> *are sponsoring a payment to your locktime'd cold storage wallet (no CPFP)
> from an untrusted third party (no RBF), they can grift you into paying for
> an unrelated payment). This isn't a concern when the root utxo is multisig
> & you are a participant.*
>
> *The serialization to support both, while slightly more complicated, can
> be done in a manner that permits future extensibility as well if there are
> other modes people require.*
>
>
>
>>
>> > If we want to solve the hard cases of pinning, I still think mempool
>> > acceptance of a whole package only on the merits of feerate is the
>> easiest
>> > solution to reason on.
>>
>> I don't think package relay based only on feerate solves RBF transaction
>> pinning (and maybe also doesn't solve ancestor/dependent limit pinning).
>> Though, certainly, package relay has the major advantage over this
>> proposal (IMO) in that it doesn't require any consensus changes.
>> Package relay is also very nice for fixing other protocol rough edges
>> that are needed anyway.
>>
>> -Dave
>>
>
> *I think it's important to keep in mind this is not a rival to package
> relay; I think you also want package relay in addition to this, as they
> solve different but related problems.*
>
>
> *Where you might be able to simplify package relay with sponsors is by
> doing a sponsor-only package relay, which is always limited to 2
> transactions, 1 sponsor, 1 sponsoree. This would not have some of the
> challenges with arbitrary-package package-relay, and would (at least from a
> ux perspective) allow users to successfully get parents with insufficient
> fee into the mempool.*
>
>
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 10088 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Jeremy]

[-- Attachment #1: Type: text/plain, Size: 10797 bytes --]

Hi Suhas,

Thanks for your thoughtful response!

Overall I'll boil down my thoughts to the following:

If we can eventually come up with something clever at the user+policy layer
to emulate a sponsor like mechanism, I would still greatly prefer to expose
that sort of functionality directly and in a fully-abstracted usable way
for the minimum amount of mempool attack risk in 2nd layer protocols, even
at the expense of some base layer complexity. It's better to pay a security
sensitive engineering cost once, than to have to pay it repeatedly and
perhaps insufficiently.

Specific responses inline below:

Best,

Jeremy

>> 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.
> That means that if a transaction is confirmed in a block without its
sponsor, the sponsor is no longer valid.  This breaks a design principle
that has been discussed many times over the years, which is that once a
valid transaction is created, it should not become invalid later on unless
the inputs are double-spent.  This principle has some logical consequences
that we've come to accept, such as transaction chains being valid across
small reorgs in the absence of malicious (double-spend) behavior.

*Certainly, this property is strictly broken by this proposal. It does not
break the weaker property that the transactions can be reorged onto another
chain, however (like OP_GETBLOCKHASH or similar would), which is important
to note. It's also important to note this property is not preserved against
reorgs longer than 100 blocks.*

> I think that this principle is a useful one and that there should be a
high bar for doing away with it.  And it seems to me that this proposal
doesn't clear that bar -- the fee bumping improvement that this proposal
aims at is really coming from the policy change, rather than the consensus
change.

*I think this is possibly correct.*

*IMO the ability to implement the policy changes is purely derived from the
consensus changes. The consensus changes add a way of third parties to a
transaction to specify economic interest in the resolution of a
transaction. This requires a consensus change to work generically and
without forethought.*


*It's possible that with specific planning or opt-in, you can make
something roughly equivalent. But such a design might also consume more
bandwidth on-chain as you would likely have to e.g. always include a CPFP
hook output.*


> But if policy changes are the direction we're going to solve these
problems, we could instead just propose new policy rules for the existing
types of transaction chaining that we have, rather than couple them to a
new transaction type.
>
> My understanding of the main benefit of this approach is that this allows
3rd parties to participate in fee bumping.  But that behavior strikes me as
also problematic, because it introduces the possibility of 3rd party
griefing, to the extent that sponsor transactions in any way limit chains
of transactions that would be otherwise permitted.  If Alice sends Bob some
coins, and Alice and Bob are both honest and cooperating, Mallory shouldn't
be able to interfere with their low-feerate transaction by (eg) pinning it
with a large transaction that "sponsors" it (ie a large transaction that is
just above the feerate of the parent, which prevents additional child
transactions and makes it more expensive to RBF).

*It's possible to modify my implementation of the policy such that there is
no ability to interfere with the otherwise permitted limits, it just
requires a little bit more work to always discount sponsors on the
descendant counting.*


*W.r.t. griefing, the proposed amendment to limit sponsors to 1000 bytes
minimizes this concern. Further, pinning in this context is mainly an issue
if Alice and Bob are intending to RBF a transaction, at a policy level we
could make Sponsoring require that the transaction be RBF opted-out (or
sponsor opted in). *


> This last issue of pinning could be improved in this proposal by
requiring that a sponsor transaction bring the effective feerate of its
package up to something which should be confirmed soon (rather than just
being a higher feerate than the tx it is sponsoring).  However, we could
also carve out a policy rule just like that today, without any consensus
changes needed, to help with pinning (which is probably a good idea!  I
think this would be useful work).  So I don't think that approaches in that
direction would be unique to this proposal.

*I agree this is useful work and something that Ranked indexes would help
with if I understand them correctly, and can be worked on independently of
Sponsors. Overall I am skeptical that we want to accept any child if it
puts something into an upper percentile as we still need to mind our DoS
budgets (which the sponsors implementation keeps a tight bound on). *


>> We allow one Sponsor to replace another subject to normal replacement
policies, they are treated as conflicts.
> This policy rule of allowing sponsor transactions to RBF each other also
seems problematic; that means that if Alice is paying Bob in a transaction
that is also sponsoring some other transaction (perhaps from Alice to
someone else), then Mallory can cause the transaction going to Bob to
become invalid by RBF bumping it and sponsoring the parent transaction
herself?  Allowing 3rd parties to interfere with transactions between
others seems like a complex and undesirable design to introduce.

*If you'll note in the BIP draft text and implementation recursive
sponsoring is not permitted by policy for this reason. Sponsors may not
sponsor a transaction that is sponsoring another transaction, and a further
restriction that sponsors may not have any children.*


> In summary: this proposal seems like a CPFP replacement, requiring many
policy rules along with a consensus change to be worked out to get right; I
think we could achieve largely the same effect by improving the current
policy rules to make CPFP work better without a consensus change.  And
while what is unique about this proposal is that it allows for 3rd parties
to attach themselves to the transaction graph of other parties, I think
that is a complex interaction to introduce and has negative side effects as
well.


*This is where I most significantly disagree. Some thoughts below on why a
consensus change is likely required for this and why the sponsors mechanism
may not be that invasive (if done right) on the way we currently understand
the transaction graph.*


*1)*
*The main issue with CPFP like mechanisms is that they require an
omniscient like behavior around how to coordinate.*


*Given the complexity of CPFP, it's not possible to ever abstract its use
from the contract protocol you are implementing. It always requires deep
integration into any protocol as a mechanism, and many bespoke protocols
for game theoretically ensuring you can pay fees is much more brittle than
one higher-order composable mechanism (which is what sponsors aims to
achieve, but may fall short on in current incarnation).*


*Further, CPFP based protocols can be wasteful, requiring at least one CPFP
hook/anchor output per participant always. These CPFP hooks need a mempool
CPFP exemption (so that you don't get pinned by a sibling), which will have
to apply recursively in case your payment protocol is not at the base of a
transaction chain (as can happen within a multiparty channel factory). Thus
CPFP as a mechanism inherently suffers from chain bloat issues and it
composes poorly when used recursively.*


*I think it will be essentially impossible to generically handle CPFP based
on transaction graph anchors both from a protocol implementers side and
from a mempool policy side. And in the event that a new attack is
discovered, a mechanism that works with fewer assumptions about the setup
of your protocol should be more robust, or at least fixable. Whereas with a
pure CPFP transaction graph based design, once you are pinned, it may be
impossible to externally correct the incentives. *




*2)*
*Third parties can already -- trustfully -- insert themselves into
another's transaction chain by bribing mining pools to escalate priority of
a transaction. These out-of-band fees are somewhat inevitable, so if your
protocol is not robust against 3rd party feerate boosting you may have
larger issues.*

*3)*
*Because we already do not handle 100 block reorgs with the replayability
property, one fine change to the BIP would be to enforce a 100 block
maturing period on sponsor transactions outputs after confirmation. This
might make usage a little bit more unwieldy, but then it would not have the
issue on small reorg validity.* *I believe this could be safely done* *only
via policy and not consensus, as if someone wants to double spend a
transaction in a reorg they can, but it's fine either way.*

*4)*

*It's not particularly important that a transaction be in the same block
once sponsored, it could also be in the last 100 blocks (the opposite of
proposed change 3). The main benefit to having same-block resolution is
that you never pay for something that would have gone in anyways, but this
mechanism could actually be generically useful if you are operating a
business and need to make reorg safe payments contingent on funds received
into cold-storage. This implies a new rolling index of txids, which has
some overhead, but combined with appropriate mempool policy (e.g., a 200
block txid index in consensus and only a 100 block index available by
mempool policy) would ensure that most reorgs could be handled cleanly.*


*5)*
*The behavior of sponsors is already emulable in a transaction graph. A
more complicated construction is possible that's a more accurate emulation,
but a simple version is as follows:*


*if you were to require:*

*A) All non-sponsor transactions include a single CPFP anchor output/CPFP
hook with an OP_TRUE as the last output*

*B) Miners sweep all OP_TRUE outputs at the end of the block to an
OP_RETURN.*


*Then it would be possible for third parties to be a sponsor by spending
that OP_TRUE output.*

*With a couple modifications (happy to discuss off-list, they end up being
aggregately more complicated than the sponsors mechanism) this can also
permit multiple sponsors in the same block.*

*Because it's possible to convert sponsors mechanism into this transaction
graph (and back again), I don't see a sponsors mechanism as breaking any
strong inherent property of the transaction graph, it's merely an
optimization of a pattern that could be implemented without breaking the
property.*

*Therefore I am unconcerned with the impact that a sponsors-like mechanism
has on the properties of the transaction graph itself.*

[-- Attachment #2: Type: text/html, Size: 19727 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Dmitry Petukhov]

В Wed, 23 Sep 2020 15:10:22 -0700
Jeremy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:

> It's not particularly important that a transaction be in the same
> block once sponsored, it could also be in the last 100 blocks (the
> opposite of proposed change 3).

This will in effect enable "inverse timelock" mechanism for up to 100
blocks for sponsor transactions: broadcast a transaction A, and
then make a pre-signed sponsor transaction B that sponsors A.

Transaction B will become invalid after 100 blocks due to this rule.

If you put a timelock on B to make it valid after 50 blocks,
then it will be valid between block 50 and 100 after A is confirmed.

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 1769 bytes --]

Hello AC,

Yes that's a real issue. In the context of multi-party protocols, you may
pre-signed transactions with the feerate of _today_ and then only going to
be broadcast later with a feerate of _tomorrow_.
In that case the pre-signed feerate may be so low that the transaction
won't even propagate across network mempools with a local minimal feerate
higher.

That's why you want to be sure that the feerate of your  package of
transactions (either sponsor+sponsoree or parent+CPFP) is going to be
evaluated as a whole to decide acceptance of each element of the package.

Antoine


Le mar. 22 sept. 2020 à 03:28, ArmchairCryptologist via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> Not sure if I'm missing something, but I'm curious if (how) this will work
> if the sponsored transaction's feerate is so low that it has been largely
> evicted from mempools due to fee pressure, and is too low to be widely
> accepted when re-broadcast? It seems to me that the following requirement
>
> >1. The Sponsor Vector's entry must be present in the mempool
>
> means that you enter a catch-22 where the sponsor transaction cannot be
> broadcast because the sponsored transaction is not in the mempool, and the
> sponsored transaction cannot be (re-)broadcast because the fee is too low.
> This requirement might therefore need to be revised.
>
> There is of course no global mempool, but RBF by its nature would still
> work in this case, by replacing the transaction if it exists and inserting
> it if it does not.
>
> --AC
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 2438 bytes --]

Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring

[ArmchairCryptologist]

[-- Attachment #1: Type: text/plain, Size: 805 bytes --]

Not sure if I'm missing something, but I'm curious if (how) this will work if the sponsored transaction's feerate is so low that it has been largely evicted from mempools due to fee pressure, and is too low to be widely accepted when re-broadcast? It seems to me that the following requirement

>1. The Sponsor Vector's entry must be present in the mempool

means that you enter a catch-22 where the sponsor transaction cannot be broadcast because the sponsored transaction is not in the mempool, and the sponsored transaction cannot be (re-)broadcast because the fee is too low. This requirement might therefore need to be revised.

There is of course no global mempool, but RBF by its nature would still work in this case, by replacing the transaction if it exists and inserting it if it does not.

--AC

[-- Attachment #2: Type: text/html, Size: 931 bytes --]