Skip to content

Instantly share code, notes, and snippets.

@JeremyRubin
Last active September 20, 2020 19:41
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save JeremyRubin/92a9fc4c6531817f66c2934282e71fdf to your computer and use it in GitHub Desktop.
Save JeremyRubin/92a9fc4c6531817f66c2934282e71fdf to your computer and use it in GitHub Desktop.

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 for those who prefer to not read specs.

Should the mailing list formatting be bungled, it is also available as a gist here.

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:

+
+    // 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
  2. No Transaction with a Sponsor Vector may have any unconfirmed parents; and
  3. The Sponsor Vector must have exactly 1 entry; and
  4. The Sponsor Vector's entry must be present in the mempool; and
  5. Every Transaction may have exactly 1 sponsor in the mempool; except
  6. 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
  2. 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. 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

@whitslack
Copy link

with no restriction on order or on specifying a TXID more than once.

Why shouldn't we require the elements of the sponsor vector to be sorted and distinct? Isn't it preferable to have only one acceptable way of encoding any given intention?

@JeremyRubin
Copy link
Author

@whitslack perhaps. Generally I prefer to make the minimum additional restriction on consensus for a given goal, your change would require more restrictive rules & more things to verify. Wallets should likely sort the txids for privacy.

Similarly, there's no constraint on the order of transactions in a block. You could argue that the order should be such that sponsors come after targets, but the implementation is slightly more complex IMO.

@whitslack
Copy link

You could argue that the order should be such that sponsors come after targets

That might actually be necessary for some conceivable implementations. I think you should add that requirement. Parent transactions are required to appear in a block before their children, so it would only be consistent to require that sponsored transactions appear in a block before their sponsors.

@JeremyRubin
Copy link
Author

Why would it be necessary for certain implementations? The reference implementation provided does not have this property, and is quite simple.

It's fine if a mempool does have this property during GBT of course, since txn order is non-consensus outside of DAG sort.

@whitslack
Copy link

Why would it be necessary for certain implementations?

It's conceivable that some implementations would prefer to validate blocks in linear order. If they encountered a sponsoring transaction that referenced transactions they hadn't yet scanned, they might prefer to reject the block rather than remember the sponsorship and check it at the end. By allowing sponsoring transactions to appear in a block before their sponsored referents, you're effectively forcing implementations to build an auxiliary data structure to hold the dangling references until their referents are encountered.

@whitslack
Copy link

And, like I mentioned previously, child transactions cannot appear in a block before their parents. Do you suppose there was no good reason for that design decision either?

@JeremyRubin
Copy link
Author

Blocks are processed in linear order. Yes, you have to build a data structure for dependencies, but you would have to do this even if the dependencies were required to be "in order". If you can show me a correct algorithm where you don't have to build any additional data structure, but with some simple requirement on the ordering of transactions, that would be convincing. I don't believe there is such an algorithm, but I'd love to be surprised.

No, there isn't a substantial reason for transactions to have to be in order in the block, in fact there are reasons for them not to be (you can parallelize validation by splitting dependency checks and state application, requiring transactions to be lexicographically sorted would make certain SPV proofs simpler). The main reason for in-order blocks is that it is what Satoshi thought of first.

W.r.t. sponsor dependencies explicitly they are not child transactions, they are something else. We use the child tracking in the mempool as it's the right tool for the job, but these new dependencies are not children, they are sponsors, and they do not behave like children in several important ways.

@whitslack
Copy link

whitslack commented Sep 20, 2020

If you can show me a correct algorithm where you don't have to build any additional data structure, but with some simple requirement on the ordering of transactions, that would be convincing.

Simple: apply transactions to the UTxO database as you linearly scan through the block. When you encounter a sponsor vector, you can simply query the UTxO database for the presence of an unspent output from each of the sponsored transactions in the vector. If you don't find any unspent output for any sponsor vector element (EDIT: or if the output was created in a block other than the one you're scanning), then the block is invalid, and you roll back the UTxO database transaction.

@JeremyRubin
Copy link
Author

this algorithm is incorrect. Counterexample:

Tx1: Spends 0.0, creates 1.0 and 1.1
Tx2: Spends 1.0, creates 2.0
Tx3: Spends -1.0, creates 3.0 and Sponsors 1
Tx4 Spends 1.1, creates 4.0
Tx5 Spends -1.1, creates 5.0 and Sponsors 1

Tx 5 will fail but should succeed.

@JeremyRubin
Copy link
Author

Also w.r.t. your edit, that is a additional data that I don't think is currently available through CCoinsView, so would require an additional data structure.

@whitslack
Copy link

What does your syntax "spends -1.0" mean?

@whitslack
Copy link

Also w.r.t. your edit, that is a additional data that I don't think is currently available through CCoinsView, so would require an additional data structure.

The UTxO database must contain a reference to the block that each output appeared in, mustn't it? How else would relative-time-locked outputs work?

@JeremyRubin
Copy link
Author

integers just represent a Outpoint. Positive created in this block, <= 0 created in a prior block.

@JeremyRubin
Copy link
Author

The UTxO database must contain a reference to the block that each output appeared in, mustn't it? How else would relative-time-locked outputs work?

Sure, it does. But it doesn't guarantee UTXOs that have been spent are visible, which is the issue if you re-read the transcript I gave you.

@JeremyRubin
Copy link
Author

Also your suggested algorithm contains a new DoS vector because it allows one to cheaply query if on-disk coins exist or not.

@whitslack
Copy link

Just to make sure I understand your example…

Tx1: Spends 0.0, creates 1.0 and 1.1

The first transaction in the current block spends the zeroeth output of the zeroeth transaction in a previous block and creates two new outputs.

Tx2: Spends 1.0, creates 2.0

The second transaction in the current block spends the zeroeth output of the first transaction in the current block and creates one new output.

Tx3: Spends -1.0, creates 3.0 and Sponsors 1

The third transaction in the current block spends the zeroeth output of the first transaction in a previous block and creates one new output. Additionally, it sponsors the first transaction in the current block. A lookup for UTxOs from that transaction will find 1.0 and 1.1, so all good.

Tx4 Spends 1.1, creates 4.0

The fourth transaction in the current block spends the first output of the first transaction in the current block and creates one new output.

Tx5 Spends -1.1, creates 5.0 and Sponsors 1

The fifth transaction in the current block spends the first output of the first transaction in a previous block and creates one new output. Additionally, it sponsors the first transaction in the current block. A lookup for UTxOs from that transaction will find 1.0 only (as 1.1 was already spent by Tx4), so all good.

I don't see why Tx5 would fail.

@whitslack
Copy link

Oh, my bad. I forgot about Tx2. Then you're right: Tx5 will fail. But it SHOULD fail!

@JeremyRubin
Copy link
Author

TX 1 creates 1.0 and 1.1
Tx2 spends 1.0
Tx4 spends 1.1

Tx5 cannot see Tx1

@JeremyRubin
Copy link
Author

Why should it fail? What you're asking for adds a myriad of complexity and edge cases to handle that are not required.

@whitslack
Copy link

Didn't you specify that a sponsored transaction can't have any children? You wouldn't sponsor a parent transaction since CPFP had already been applied to it. You would sponsor one of the children (that itself has no children).

@whitslack
Copy link

Ahh, I see. Then Tx3 should have been invalidated by Tx4 but wasn't. Okay, I withdraw my suggestion.

@JeremyRubin
Copy link
Author

You're confusing policy and consensus. Policy refers to things that are optionally enforced by the mempool or other layers.

In consensus, you can sponsor whatever you like however you like.

Further, your idea of "sponsor one of the children" instead of sponsoring the parent is broken for a number of reasons. Two example reasons (there are more): it's less efficient as you have to pay for that child as well, this can lead to the very pinning issues that sponsors are designed to subvert, you might not even see the child tx at the time you sponsor.

@JeremyRubin
Copy link
Author

Also the policy rule is that the sponsoring transaction not have children, not the sponsored.

@JeremyRubin
Copy link
Author

@whitslack these are good questions to think through! I'd encourage you to try implementing your proposed changes to this spec as an exercise so you can run up against the challenges first hand :)

@dgpv
Copy link

dgpv commented Sep 20, 2020

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

This allows a third party to "un-sponsor" transactions:

(A in parentheses means what is sponsored)

  1. Alice sends TxSA(A) to sponsor TxA

  2. Bob replaces TxSA(A) with TxSB(A)

  3. Bob double-spends TxSB(A) with TxB

  4. TxA is no longer sponsored

Bob will have to pay extra fee at 2) and 3), of course. But they might be willing to do so if they at the same time attack TxA to prevent its fee bump via pinning, for example.

This is not a fundamental problem, as implementations should monitor mempool for their transactions and act accordingly if they disappear, because they can disappear from mempool for other reasons. But this dynamic makes such monitoring more important, as now a direct simple action from a third party can evict the sponsor transaction, like a "double-spend without owning the inputs"

@JeremyRubin
Copy link
Author

JeremyRubin commented Sep 20, 2020 via email

@JeremyRubin
Copy link
Author

JeremyRubin commented Sep 20, 2020 via email

@whitslack
Copy link

Perhaps we should add a rule though that pins transactions with sponsor [vectors] so they cannot be replaced with a tx that does not sponsor the same transaction[s]?

That could only be a mempool policy, much like the so-called "opt-in RBF," and like the latter, it would confer a false sense of safety, as miners can always be paid to replace a given transaction even if the default mempool policy would not allow such a replacement.

@dgpv
Copy link

dgpv commented Sep 20, 2020

Note that TxSA can be in this case resubmit immediately.

Yes. As I said, this dynamic just makes mempool monitoring more important, to be able to resubmit immediately.

@JeremyRubin
Copy link
Author

@whitslack correct, we're talking in the domain of policy. The consensus rules do not need adjusting. What is important tho is to ensure the policy is incentive compatible or rational miners will change behaviors.

@dgpv yep; I think all of this presupposes some level of active mempool monitoring anyways, via watchtowers or similar. Otherwise you would not even know if something were in the mempool or not. And generally, for protocols, you don't need to monitor the mempool actively, you need to monitor blocks within your chosen SLA and if triggered (e.g., by the publishing of a revoked state) respond within a given time window. Once such a protocol is started you are protected in the mempool by timelocks ensuring the final close state cannot be used with some relative bound (and cannot be in the mempool).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment