From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from silver.osuosl.org (smtp3.osuosl.org [140.211.166.136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 179BCC0051 for ; Sat, 19 Sep 2020 02:10:58 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by silver.osuosl.org (Postfix) with ESMTP id ED20F204A4 for ; Sat, 19 Sep 2020 02:10:57 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org Received: from silver.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id NClBQsyrBQMT for ; Sat, 19 Sep 2020 02:10:56 +0000 (UTC) X-Greylist: delayed 00:23:32 by SQLgrey-1.7.6 Received: from mail-ed1-f44.google.com (mail-ed1-f44.google.com [209.85.208.44]) by silver.osuosl.org (Postfix) with ESMTPS id 9F9B520449 for ; Sat, 19 Sep 2020 02:10:55 +0000 (UTC) Received: by mail-ed1-f44.google.com with SMTP id e22so7825497edq.6 for ; Fri, 18 Sep 2020 19:10:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=coryfields.com; s=google; h=mime-version:references:in-reply-to:reply-to:from:date:message-id :subject:to; bh=VYgYJ3phkmcM0wxG3a7pXz2IAg6EjNV4Ucm5FiSKX7E=; b=pHlaX1uMghKd6LcmkxpD/gjJsBowOi90S1tbmF0+XTetLWJb+y7wdcpd2mLqjW2o+o vLv3mXCQav+fN3r9pcmvlB0ZKuALHMy76NbbedswRbJJbc3Q1P8Lo8QQ6hjIC5ZuOI+i i9/+LQUzut8eSkXujt1Z3/Jo4svYeEhdRPoMOkbuoNU8GxWUJwOB/H33EZyIV20wCih4 SKoOborw74swpeZ5q2PNrGTbbatjQUJqakjyTgH15d9e3C+G3foRiEEBateLmhaIlTb+ YRxvzvQYyJwQ11drd1a8CqhaTs0Z8A7hQtXaqIso7XQL3xY8iWWx9mUs3Ac2i1daBFQ5 n3XQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:reply-to :from:date:message-id:subject:to; bh=VYgYJ3phkmcM0wxG3a7pXz2IAg6EjNV4Ucm5FiSKX7E=; b=uOAAX54h9ECIUhfeGP2vj2veqfLzvtHMhGltdHWGr1g1NazlidqsoslrKvcRfWeEiK e/oIFSdCJk+kbXPTUMzFuLpTrkUo9Gl+WDfBbmc5C2tUPmsraVT8ARox/Pxbf4SfpJCc miIHMvsuutQgqjpBBf/fd0W89ty/rrmye/RgAlYNUcCOY6PAUdG6SvMq/QUI9LoyIgRV pImcacfd8IzclUkIKx3DCz5UtNrYEI5xnEhE+8lKHJKtilAEeeksvlRrFfnHRzmCHLmy zJHE90vId5wbfmU8OnwoWn63+N7YY4VGUx8fjWkC4TbrG89LPTpOjq/gGy18HH9sLE1o H7Xg== X-Gm-Message-State: AOAM531zNnhhHAtwwJ7ZmJo/TrepfqAjQ3/5uIWtbvjzP5iUHLCr3LzW KCeb9p+9CO1sy5TALdXRSHmGvgfXT0TTpK4lO4uBipaHu5s= X-Google-Smtp-Source: ABdhPJwSrEsdLJtcLtHSqyhnpVdeS5CyRPbszQ2ZttXaoNSk9NhdlLOLMCA70Fr5u2KlnetmL8ZGpz7+yNSBLGGA9XM= X-Received: by 2002:a17:906:aac7:: with SMTP id kt7mr38982431ejb.548.1600479567546; Fri, 18 Sep 2020 18:39:27 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: Reply-To: lists@coryfields.com From: Cory Fields Date: Fri, 18 Sep 2020 21:39:16 -0400 Message-ID: To: Jeremy , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000182c9e05afa0b029" Subject: Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 19 Sep 2020 02:10:58 -0000 --000000000000182c9e05afa0b029 Content-Type: text/plain; charset="UTF-8" Conceptually this is so simple and explicit it almost seems like an obvious primitive. Glossing over some of the design/policy decisions... I wonder what the real-world privacy implications are due to the dependencies now being encoded on-chain rather than requiring some effort to watch the mempool? Cory On Fri, Sep 18, 2020, 20:52 Jeremy via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > Hi Bitcoin Devs, > > > I'd like to share with you a draft proposal for a mechanism to replace CPFP and RBF for > increasing fees on transactions in the mempool that should be more robust against attacks. > > A reference implementation demonstrating these rules is available > [here](https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:subsidy-tx) for those who > prefer to not read specs. > > Should the mailing list formatting be bungled, it is also available as a gist [here](https://gist.github.com/JeremyRubin/92a9fc4c6531817f66c2934282e71fdf). > > Non-Destructive TXID Dependencies for Fee Sponsoring > ==================================================== > > This BIP proposes a general purpose mechanism for expressing non-destructive (i.e., not requiring > the spending of a coin) dependencies on specific transactions being in the same block that can be > used to sponsor fees of remote transactions. > > Motivation > ========== > > The mempool has a variety of protections and guards in place to ensure that miners are economic and > to protect the network from denial of service. > > The rough surface of these policies has some unintended consequences for second layer protocol > developers. Applications are either vulnerable to attacks (such as transaction pinning) or must go > through great amounts of careful protocol engineering to guard against known mempool attacks. > > This is insufficient because if new attacks are found, there is limited ability to deploy fixes for > them against deployed contract instances (such as open lightning channels). What is required is a > fully abstracted primitive that requires no special structure from an underlying transaction in > order to increase fees to confirm the transactions. > > Consensus Specification > ======================= > > If a transaction's last output's scripPubKey is of the form OP_VER followed by n*32 bytes, where > n>1, it is interpreted as a vector of TXIDs (Sponsor Vector). The Sponsor Vector TXIDs must also be > in the block the transaction is validated in, with no restriction on order or on specifying a TXID > more than once. This can be accomplished simply with the following patch: > > > ```diff > + > + // Extract all required fee dependencies > + std::unordered_set 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 > > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > --000000000000182c9e05afa0b029 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Conceptually this is so simple and explicit it almos= t 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?=C2=A0

Cory

On Fri, Sep 18, 2020, 20:52 Jeremy via bitcoi= n-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 a=
gainst 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 gi=
st [here](https://gis=
t.github.com/JeremyRubin/92a9fc4c6531817f66c2934282e71fdf).

Non-Destructive TXID Dependencies for Fee Sponsoring
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

Thus we restrict the mempool policy such that:

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


The mempool treats ancestors and descendants limits as follows:

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

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

To prevent garbage sponsors, we also require that:

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

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


### Design Motivation

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

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

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


#### Attack Analysis of new Policy

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

#### Package Relay/Orphan Pool

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

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


Best,

Jeremy

_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.li= nuxfoundation.org/mailman/listinfo/bitcoin-dev
--000000000000182c9e05afa0b029--