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

From: Antoine Riard <antoine.riard@gmail•com>
To: Jeremy <jlrubin@mit•edu>,
	 Bitcoin Protocol Discussion
	<bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] A Replacement for RBF and CPFP: Non-Destructive TXID Dependencies for Fee Sponsoring
Date: Sat, 19 Sep 2020 15:13:56 -0400	[thread overview]
Message-ID: <CALZpt+EAWbPWh_knT7yDdPT396jEL1g+XSEv1JALuwaJVqNS7w@mail.gmail.com> (raw)
In-Reply-To: <CALZpt+FbRGrcW7LZY=4NtR9w4CP=kavVdqutfrX86OYnouHUJg@mail.gmail.com>

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