path: root/9f/318f2f537eb5ec92448a4c43d003a2e9fc24ac

Return-Path: <antoine.riard@gmail.com>
Received: from hemlock.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id AE60FC0051
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 19 Sep 2020 19:14:12 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by hemlock.osuosl.org (Postfix) with ESMTP id 9D1F8873DC
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 19 Sep 2020 19:14:12 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from hemlock.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id Pp1LelpasE9H
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 19 Sep 2020 19:14:10 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-wr1-f53.google.com (mail-wr1-f53.google.com
 [209.85.221.53])
 by hemlock.osuosl.org (Postfix) with ESMTPS id E8B4281BB9
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 19 Sep 2020 19:14:09 +0000 (UTC)
Received: by mail-wr1-f53.google.com with SMTP id m6so8845981wrn.0
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat, 19 Sep 2020 12:14:09 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to;
 bh=pXRlu7eorT7HWvY//jKCnWemXYLZPIFfEixKn6eSWfM=;
 b=AthKZBoEnKogvYxxtG1SOPolnmN4O6QMba9FPi4j5mZbXjkJvTPgsOZP09es+1URda
 6FRQooOLBqJZJfYAIsra8P6/0azoqkP26/jZJEPDi3rkywF+WLP42NcuEPHi9ZvtKzpD
 Wl4hSaum8j4yuohiGx2WjzMW7YrA1T00GnZPU/vPPI/s0x7aHd4hcSoN7FsLy7l2qyQB
 XHo9xdmderN6VUAEs61fF6fIcxKz7pLFXqIOO/LnB4aYRlCZLMQhVo9nu/PVRPQPgCXs
 m8v+0l9PVG/Xt074FzJlnKCXuwruUpqrkDtpL2iZJz0e+1Q0BSL1vh93F/E+dVyveLT+
 Sv7w==
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:from:date
 :message-id:subject:to;
 bh=pXRlu7eorT7HWvY//jKCnWemXYLZPIFfEixKn6eSWfM=;
 b=UfF9P3x6ePinffhsxFOOmF7ztLpYOeqg0F+w2/y+Ghyna9HsYsB3U46gpJiIycTXpD
 uGrNk6zlOvBADhFNccxBf6s7IaQvirhmtwiw2LAjAnZ0kc9E/LKsIHdI12HCGalJHJJC
 Ed0gtITVfl9IH+1p/8zOSx4LEcXc2GL4pYtXzKgd38GzBiMv23+3mFkeZkF27sfr24x8
 1pVepY1RNc98im4VM4YuolyBAYEpo4wgb8UwPoIVPMBlzTsQrNkhmEGkL0CiH00O/oQ+
 QLK9GfdsfIslzBvKhA+quWxw0V+imHqPSwO9P424nzdll0PfiNAo6RVZhmWykn/4AdFn
 seOg==
X-Gm-Message-State: AOAM5327MXyGf75v+AwU18T1jbZyWCvbo/0uDGLJuk23KXb5jO40rz9g
 ucVgJM7D0OehKZby3Z6QOfal1Mp9rnt91n88nJ6Z1PnKh4UoBA==
X-Google-Smtp-Source: ABdhPJxkLsb+8XB2omszyEfpVf8ptbuAS+nuf1Yy2G46T4j3sp38CrFQ+oFV7ZVtmgSEx9PjoKvpnnBWWOkbaXGklqc=
X-Received: by 2002:adf:f44d:: with SMTP id f13mr43882291wrp.224.1600542848246; 
 Sat, 19 Sep 2020 12:14:08 -0700 (PDT)
MIME-Version: 1.0
References: <CAD5xwhi6+Q-UX2xVnD4TE9uEbe-omQ748tpJJpYdrMNnG6D5vA@mail.gmail.com>
 <CALZpt+FbRGrcW7LZY=4NtR9w4CP=kavVdqutfrX86OYnouHUJg@mail.gmail.com>
In-Reply-To: <CALZpt+FbRGrcW7LZY=4NtR9w4CP=kavVdqutfrX86OYnouHUJg@mail.gmail.com>
From: Antoine Riard <antoine.riard@gmail.com>
Date: Sat, 19 Sep 2020 15:13:56 -0400
Message-ID: <CALZpt+EAWbPWh_knT7yDdPT396jEL1g+XSEv1JALuwaJVqNS7w@mail.gmail.com>
To: Jeremy <jlrubin@mit.edu>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000eae76705afaf6b1a"
X-Mailman-Approved-At: Sat, 19 Sep 2020 19:36:31 +0000
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 19 Sep 2020 19:14:12 -0000

--000000000000eae76705afaf6b1a
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 =C3=A0 14:39, Antoine Riard <antoine.riard@gmail.com>=
 a
=C3=A9crit :

> 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 lac=
k
> 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 committe=
d
> in the Sponsoree signature hash means the Sponsor feerate is part of this
> commitment and can't be unilaterally adjusted to actual mempool-congestio=
n.
>
> 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 t=
he
> 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 i=
n
> 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 protocol=
s.
> 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 ca=
n
> 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 >=3D1 ? I think you can have at least one vector and this is matching t=
he
> code
>
> > If there is another convenient place to put the TXID vector, that's fin=
e
> too.
>
> You might use the per-input future Taproot annex, and even apply a witnes=
s
> discount as this mechanism could be argued to be less blockspace expensiv=
e
> 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][nV=
ersion][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 requirement=
s.
>
> Though it's more demanding on the tx-relay layer (new serialization and
> transaction identifier) and new a version bump of the signature digest al=
go
> 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 dependen=
cy
> to scope. What we should be worried about is network mempools partitions
> between different mechanisms of incompatible package relay if we implemen=
t
> 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 reduc=
ed
> cost compared to N-Parent-1-CPFP as the CPFP must include an input for ea=
ch
> 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=3D1 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/00275=
8.html
>
> [1] See the recent Dynamic Commitments proposal to ponder this concern
> https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-July/00276=
3.html
>
> Le ven. 18 sept. 2020 =C3=A0 20:52, Jeremy via bitcoin-dev <
> bitcoin-dev@lists.linuxfoundation.org> a =C3=A9crit :
>
>> Hi Bitcoin Devs,
>>
>>
>> I'd like to share with you a draft proposal for a mechanism to replace C=
PFP and RBF for
>> increasing fees on transactions in the mempool that should be more robus=
t against attacks.
>>
>> A reference implementation demonstrating these rules is available
>> [here](https://github.com/bitcoin/bitcoin/compare/master...JeremyRubin:s=
ubsidy-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/92a9fc4c6531817f66c2934282=
e71fdf).
>>
>> 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-destruc=
tive (i.e., not requiring
>> the spending of a coin) dependencies on specific transactions being in t=
he 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 t=
hat 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 trans=
action pinning) or must go
>> through great amounts of careful protocol engineering to guard against k=
nown 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 channel=
s). What is required is a
>> fully abstracted primitive that requires no special structure from an un=
derlying 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 follo=
wed 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 ord=
er 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_V=
ER followed by a sequence of 32*n
>> +            // bytes
>> +            // vout.back() must exist because it is checked in CheckBlo=
ck
>> +            const CScript& dependencies_script =3D tx->vout.back().scri=
ptPubKey;
>> +            // empty scripts are valid, so be sure we have at least one=
 byte
>> +            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,=
 stop =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=
, "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& block=
, BlockValidationState& state,
>>          }
>>          UpdateCoins(tx, view, i =3D=3D 0 ? undoDummy : blockundo.vtxund=
o.back(), pindex->nHeight);
>>      }
>> +    if (!dependencies.empty()) {
>> +        return state.Invalid(BlockValidationResult::BLOCK_CONSENSUS, "b=
ad-dependency-missing-target-txid");
>> +    }
>> ```
>>
>> ### Design Motivation
>> The final output of a transaction is an unambiguous location to attach m=
etadata to a transaction
>> such that the data is available for transaction validation. This data co=
uld 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 t=
ransaction 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 mec=
hanism.
>>
>> 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-transa=
ction dependencies.
>>
>> In this BIP, we only care to ensure a subset of behavior sufficient to r=
eplace 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 ha=
ve 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 f=
ee rate
>>
>> We allow one Sponsor to replace another subject to normal replacement po=
licies, 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 blo=
ck (this is incompatible
>> with CTV, exercise left to reader). These use cases are in a sense incid=
ental 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 ca=
se, while providing a "it
>> always works" API for end users that is not subject to traditional issue=
s 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 sh=
ould it be implemented.
>>
>>
>> #### Attack Analysis of new Policy
>>
>> In the worst case the new policy can lead to a 1/2 reduction in the numb=
er of children allowed
>> (e.g., if there are 13 children submitted, then 12 sponsors, the 25 chil=
d 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 scenari=
o, 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 spons=
or pool with an eviction
>> policy that would enable sponsors to be queried and tracked for transact=
ions that have too low fee
>> to enter the mempool in the first place. This is treated as a separate c=
oncern, 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:s=
ubsidy-tx). This is a best
>> effort implementation, but has not been carefully audited for correctnes=
s and likely diverges from
>> this document in ways that should either be reflected in this document o=
r 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
>>
>

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

<div dir=3D"ltr"><div><div>EDIT: I misunderstood the emplacement of the spo=
nsor vector, please disregard previous review :( Beyond where the convenien=
t place should live, which is still accurate I think.<br></div><div><br>&gt=
; The<br>&gt; Sponsor Vector TXIDs =C2=A0must also be<br>&gt; in the block =
the transaction is validated in, with no restriction on<br>&gt; order or on=
 specifying a TXID<br>&gt; more than once.<br><br></div></div></div><br><di=
v class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0sam. =
19 sept. 2020 =C3=A0=C2=A014:39, Antoine Riard &lt;<a href=3D"mailto:antoin=
e.riard@gmail.com">antoine.riard@gmail.com</a>&gt; a =C3=A9crit=C2=A0:<br><=
/div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"ltr"><di=
v>Hi Jeremy,<br><br>This is a really interesting proposal to widen the scop=
e of fee mechanisms. <br><br>First, a wider point on what this proposal bri=
ngs with regards to pinning, to the best of my knowledge.<br><br>A pinning =
may have different vectors by exploiting a) mempools limits (e.g descendant=
s) or b) mempools absolute-fee/feerate/conflicts logic. The lack of a globa=
l mempool means you can creatively combine them to provoke mempools-partiti=
ons [0]<br><br>As far as I understand this proposal, it aims to solve the c=
lass a) of pinnings by allowing fee-bumping with a new definition of depend=
encies. I&#39;m not sure it achieves to do=C2=A0 so as the Sponsor Vector T=
XIDs being committed in the Sponsoree signature hash means the Sponsor feer=
ate is part of this commitment and can&#39;t be unilaterally adjusted to ac=
tual mempool-congestion. <br><br>After broadcasting the Sponsor/Sponsoree p=
air, mempools feerate may increase again and thus obsoleting the previous f=
ee-bump. Or you need a Sponsor Vector for every blockspace feerate, in the =
worst-case bound by the value of the Sponsoree funds.<br><br>Further, I wou=
ld say this proposal won&#39;t solve class b) of pinnings for multi-party t=
ime-sensitive protocols without further modifications. E.g in a LN-channel,=
 assuming the commitment transaction is the Sponsoree, Alice the honest par=
ty can&#39;t increase Sponsor feerate by mal eating its outputs without bre=
aking the sponsoring dependency. And thus evict a Bob&#39;s malicious pin a=
cross network mempools.<br><br>I think a further softfork proposal with reg=
ards to sighash malleability is needed to achieve the security semantic for=
 Lightning type of protocols. Roughly, a SIGHASH_IOVECTOR allows N-inputs t=
o commit to N-outputs, thus committing to all the balance/HTLC outputs minu=
s the last output Vector, non-interactively malleable by channel participan=
ts. This would be a form of transaction finalization delegation, allowing A=
lice to direct the Sponsor vector to a good-feerate adjusted transaction.<b=
r><br>Note, I may have misunderstood completely the proposal as the feerate=
 observed might be the Sponsor _package_ one and each party could have a pa=
ir of outputs to spend from to non-interactively increase the Sponsoree. Th=
ough sounds like re-introducing the limits issues...<br><br>That said, see =
following review points.<br><br>&gt; This is insufficient because if new at=
tacks are found, there is<br>&gt; limited ability to deploy fixes for<br>&g=
t; them against deployed contract instances (such as open lightning<br>&gt;=
 channels). What is required is a<br>&gt; fully abstracted primitive that r=
equires no special structure from an<br>&gt; underlying transaction in<br>&=
gt; order to increase fees to confirm the transactions.<br><br>This is real=
ly true, in case of vulnerability discovered mass closing of the channel wo=
uld be in itself a concern as it would congest mempools and open to looter =
behaviors [1]. Though I don&#39;t think a special structure can claim cover=
ing every potential source of vulnerability for=C2=A0 off-chain protocols a=
s some of them might be tx-relay based (e.g reject-filters for segwit txn).=
<br><br>Further, a &quot;fully abstracted primitive&quot; is loosely define=
d, one could argue that anchor outputs don&#39;t require special structure =
from an underlying transaction (i.e on the order of outputs ?).<br><br>&gt;=
 =C2=A0where<br>n&gt;1, it is interpreted as a vector of TXIDs (Sponsor Vec=
tor).<br><br>n &gt;=3D1 ? I think you can have at least one vector and this=
 is matching the code<br><br>&gt; If there is another convenient place to p=
ut the TXID vector, that&#39;s fine too.<br><br>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 se=
mantic.<br><br>An alternative could be a new transaction field like a new `=
stxid` :<br><br>`[nVersion][marker][flag][txins][txouts][witness][nLockTime=
][nSponsor][nVersion][n*STXID]`<br><br>It would be cheaper as you likely sa=
ve the output amount size and OP_VER. And you don&#39;t have to subtract a =
dust output + 1 from the other output amount to make sure the Sponsor outpu=
t meets dust propagation requirements.<br><br>Though it&#39;s more demandin=
g 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 mall=
eating the per-transaction sponsor field<br><br>&gt; To prevent garbage spo=
nsors, we also require that:<br><br>Does the reverse hold ? Garbage Sponsor=
ee by breaking the dependency and double-spending the utxo spent by the Spo=
nsor and thus decreasing Sponsoree&#39;s feerate to mempool bottom. AFAIK y=
ou can&#39;t do this with CPFP.<br><br>&gt; rational miners may wish to per=
mit multiple sponsor<br>&gt; targets, or multiple sponsoring<br>&gt; transa=
ctions,<br><br>I&#39;m not sure if your policy sktech prevents multiple 1-S=
ponsor-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.<br><br>&gt=
; This is treated as a separate<br>&gt; concern, as any strides on<br>&gt; =
package relay generally should be able to support sponsors trivially.<br><b=
r>This is one more reason to carefully version package relay, beyond the tr=
ansaction package complexity, you now have a new type of graph dependency t=
o scope. What we should be worried about is network mempools partitions bet=
ween different mechanisms of incompatible package relay if we implement one=
.<br></div><div><br>Overall, a missing point which is making this proposal =
compelling is the fact that you may have one 1-Sponsor-for-N-Sponsoree whic=
h is a far reduced cost compared to N-Parent-1-CPFP as the CPFP must includ=
e an input for each bumped parent. Here you only have the Sponsor output. T=
hus observing input_size &gt; output_size, this proposal is better for mult=
i-transactions bumping (but not for N=3D1 as you have to bear the input spe=
nding of the Sponsor).<br><br>Antoine<br><br>[0] Within LN-context, for cla=
ss b) see <a href=3D"https://lists.linuxfoundation.org/pipermail/lightning-=
dev/2020-June/002758.html" target=3D"_blank">https://lists.linuxfoundation.=
org/pipermail/lightning-dev/2020-June/002758.html</a><br><br>[1] See the re=
cent Dynamic Commitments proposal to ponder this concern <a href=3D"https:/=
/lists.linuxfoundation.org/pipermail/lightning-dev/2020-July/002763.html" t=
arget=3D"_blank">https://lists.linuxfoundation.org/pipermail/lightning-dev/=
2020-July/002763.html</a><br></div></div><br><div class=3D"gmail_quote"><di=
v dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0ven. 18 sept. 2020 =C3=A0=C2=A02=
0:52, Jeremy via bitcoin-dev &lt;<a href=3D"mailto:bitcoin-dev@lists.linuxf=
oundation.org" target=3D"_blank">bitcoin-dev@lists.linuxfoundation.org</a>&=
gt; a =C3=A9crit=C2=A0:<br></div><blockquote class=3D"gmail_quote" style=3D=
"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-le=
ft:1ex"><div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:=
arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)"><pre>Hi Bitcoi=
n Devs,


I&#39;d like to share with you a draft proposal for a mechanism to replace =
CPFP and RBF for
increasing fees on transactions in the mempool that should be more robust a=
gainst attacks.

A reference implementation demonstrating these rules is available
[here](<a href=3D"https://github.com/bitcoin/bitcoin/compare/master...Jerem=
yRubin:subsidy-tx" target=3D"_blank">https://github.com/bitcoin/bitcoin/com=
pare/master...JeremyRubin:subsidy-tx</a>) for those who
prefer to not read specs.

Should the mailing list formatting be bungled, it is also available as a gi=
st [here](<a href=3D"https://gist.github.com/JeremyRubin/92a9fc4c6531817f66=
c2934282e71fdf" target=3D"_blank">https://gist.github.com/JeremyRubin/92a9f=
c4c6531817f66c2934282e71fdf</a>).

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

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

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

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

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

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

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

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


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

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

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

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

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

If there is another convenient place to put the TXID vector, that&#39;s fin=
e too.

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

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

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

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

Thus we restrict the mempool policy such that:

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


The mempool treats ancestors and descendants limits as follows:

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

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

To prevent garbage sponsors, we also require that:

1. The Sponsor&#39;s feerate must be greater than the Sponsored&#39;s ances=
tor fee rate

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


### Design Motivation

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

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

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


#### Attack Analysis of new Policy

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

#### Package Relay/Orphan Pool

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

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


Best,

Jeremy

</pre></div><br clear=3D"all"><div><div dir=3D"ltr"><div dir=3D"ltr">--<br>=
<a href=3D"https://twitter.com/JeremyRubin" target=3D"_blank">@JeremyRubin<=
/a><a href=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div>=
</div></div></div>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
</blockquote></div>

--000000000000eae76705afaf6b1a--