Date: Fri, 29 Sep 2017 01:53:55 +0000
In-Reply-To: <359FFE85-86AF-4FBD-9491-3528382E5002@friedenbach.org>
References: <359FFE85-86AF-4FBD-9491-3528382E5002@friedenbach.org>
MIME-Version: 1.0
Content-Type: multipart/alternative;
	boundary="----W9T8BLP4L26NF71V3ZRYJIEU5PAV22"
Content-Transfer-Encoding: 7bit
To: Mark Friedenbach <mark@friedenbach.org>,
	Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
	Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
From: Matt Corallo <lf-lists@mattcorallo.com>
Message-ID: <DC1B3730-756E-4A9B-BE6E-481B78E4104D@mattcorallo.com>
Subject: Re: [bitcoin-dev] Rebatable fees & incentive-safe fee markets
Precedence: list

------W9T8BLP4L26NF71V3ZRYJIEU5PAV22
Content-Type: text/plain;
 charset=utf-8
Content-Transfer-Encoding: quoted-printable

I'm somewhat curious what the authors envisioned the real-world implication=
s of this model to be=2E While blindly asking users to enter what they're w=
illing to pay always works in theory, I'd imagine in such a world the fee s=
election UX would be similar to what it is today - users are provided a lis=
t of options with feerates and expected confirmation times from which to se=
lect=2E Indeed, in a world where users pay a lower fee if they paid more th=
an necessary fee estimation could be more willing to overshoot and the UX a=
round RBF and CPFP could be simplified greatly, but I'm not actually convin=
ced that it would result in higher overall mining revenue=2E

The UX issues with RBF and CPFP, not to mention the UX issues involved in =
optimizing for quick confirmation are, indeed, quite significant, but I bel=
ieve them to be solveable with rather striaght-forward changes=2E Making th=
e market more useable (for higher or lower overall miner revenue) may be a =
sufficient goal, however, to want to consider something like this=2E

On September 28, 2017 9:06:29 PM EDT, Mark Friedenbach via bitcoin-dev <bi=
tcoin-dev@lists=2Elinuxfoundation=2Eorg> wrote:
>This article by Ron Lavi, Or Sattath, and Aviv Zohar was forwarded to
>me and is of interest to this group:
>
>    "Redesigning Bitcoin's fee market"
>    https://arxiv=2Eorg/abs/1709=2E08881
>
>I'll briefly summarize before providing some commentary of my own,
>including transformation of the proposed mechanism into a relatively
>simple soft-fork=2E  The article points out that bitcoin's auction
>model for transaction fees / inclusion in a block is broken in the
>sense that it does not achieve maximum clearing price* and to prevent
>strategic bidding behavior=2E
>
>(* Maximum clearing price meaning highest fee the user is willing to
>   pay for the amount of time they had to wait=2E  In other words, miner
>   income=2E  While this is a common requirement of academic work on
>   auction protocols, it's not obvious that it provides intrinsic
>   benefit to bitcoin for miners to extract from users the maximum
>   amount of fee the market is willing to support=2E  However strategic
>   bidding behavior (e=2Eg=2E RBF and CPFP) does have real network and
>   usability costs, which a more "correct" auction model would reduce
>   in some use cases=2E)
>
>Bitcoin is a "pay your bid" auction, where the user makes strategic
>calculations to determine what bid (=3Dfee) is likely to get accepted
>within the window of time in which they want confirmation=2E  This bid
>can then be adjusted through some combination of RBF or CPFP=2E
>
>The authors suggest moving to a "pay lowest winning bid" model where
>all transactions pay only the smallest fee rate paid by any
>transaction in the block, for which the winning strategy is to bid the
>maximum amount you are willing to pay to get the transaction
>confirmed:
>
>> Users can then simply set their bids truthfully to exactly the
>> amount they are willing to pay to transact, and do not need to
>> utilize fee estimate mechanisms, do not resort to bid shading and do
>> not need to adjust transaction fees (via replace-by-fee mechanisms)
>> if the mempool grows=2E
>
>
>Unlike other proposed fixes to the fee model, this is not trivially
>broken by paying the miner out of band=2E  If you pay out of band fee
>instead of regular fee, then your transaction cannot be included with
>other regular fee paying transactions without the miner giving up all
>regular fee income=2E  Any transaction paying less fee in-band than the
>otherwise minimum fee rate needs to also provide ~1Mvbyte * fee rate
>difference fee to make up for that lost income=2E  So out of band fee is
>only realistically considered when it pays on top of a regular feerate
>paying transaction that would have been included in the block anyway=2E
>And what would be the point of that?
>
>
>As an original contribution, I would like to note that something
>strongly resembling this proposal could be soft-forked in very easily=2E
>The shortest explanation is:
>
>    For scriptPubKey outputs of the form "<max-42-byte-push>", where
>    the pushed data evaluates as true, a consensus rule is added that
>    the coinbase must pay any fee in excess of the minimum fee rate
>    for the block to the push value, which is a scriptPubKey=2E
>
>Beyond fixing the perceived problems of bitcoin's fee auction model
>leading to costly strategic behavior (whether that is a problem is a
>topic open to debate!), this would have the additional benefits of:
>
>    1=2E Allowing pre-signed transactions, of payment channel close-out
>       for example, to provide sufficient fee for confirmation without
>       knowledge of future rates or overpaying or trusting a wallet to
>       be online to provide CPFP fee updates=2E
>
>    2=2E Allowing explicit fees in multi-party transaction creation
>       protocols where final transaction sizes are not known prior to
>       signing by one or more of the parties, while again not
>       overpaying or trusting on CPFP, etc=2E
>
>    3=2E Allowing applications with expensive network access to pay
>       reasonable fees for quick confirmation, without overpaying or
>       querying a trusted fee estimator=2E  Blockstream Satellite helps
>       here, but rebateable fees provides an alternative option when
>       full block feeds are not available for whatever reason=2E
>
>Using a fee rebate would carry a marginal cost of 70-100 vbytes per
>instance=2E  This makes it a rather expensive feature, and therefore in
>my own estimation not something that is likely to be used by most
>transactions today=2E  However the cost is less than CPFP, and so I
>expect that it would be a heavily used feature in things like payment
>channel refund and uncooperative close-out transactions=2E
>
>
>Here is a more worked out proposal, suitable for critiquing:
>
>1=2E A transaction is allowed to specify an _Implicit Fee_, as usual, as
>   well as one or more explicit _Rebateable Fees_=2E  A rebateable fee
>   is an ouput with a scriptPubKey that consists of a single, minimal,
>   nonzero push of up to 42 bytes=2E  Note that this is an always-true
>   script that requires no signature to spend=2E
>
>2=2E The _Fee Rate_ of a transaction is a fractional number equal to the
>   combined implicit and rebateable fee divided by the size/weight of
>   the transaction=2E
>
>   (A nontrivial complication of this, which I will punt on for the
>    moment, is how to group transactions for fee rate calculation such
>    that CPFP doesn't bring down the minimum fee rate of the block,
>    but to do so with rules that are both simple, because this is
>    consensus code; and fair, so as to prevent unintended use of a
>    rebate fee by children or siblings=2E)
>
>3=2E The smallest fee rate of any non-coinbase transaction (or
>   transaction group) is the _Marginal Fee Rate_ for the block and is
>   included in the witness for the block=2E
>
>4=2E The verifier checks that each transaction or transaction grouping
>   provides a fee greater than or equal to the threshold fee rate, and
>   at least one is exactly equal to the marginal rate (which proves
>   the marginal rate is the minimum for the block)=2E
>
>This establishes the marginal fee rate, which alternatively expressed
>is epsilon less than the fee rate that would have been required to get
>into the block, assuming there was sufficient space=2E
>
>5=2E A per-block _Dust Threshold_ is calculated using the marginal fee
>   rate and reasonable assumptions about transaction size=2E
>
>6=2E For each transaction (or transaction group), the _Required Fee_ is
>   calculated to be the marginal fee rate times the size/weight of the
>   transaction=2E  Implicit fee is applied towards this required fee and
>   added to the _Miner's Fee Tally_=2E  Any excess implicit fee
>   remaining is added to the _Implicit Fee Tally_=2E
>
>7=2E For each transaction (group), the rebateable fees contribute
>   proportionally towards towards meeting the remaining marginal fee
>   requirement, if the implicit fee failed to do so=2E  Of what's left,
>   one of two things can happen based on how much is remaining:
>
>     A=2E If greater than or equal to the dust threshold is remaining in
>        a specific rebateable fee, a requirement is added that an
>        output be provided in the coinbase paying the remaining fee to
>        a scriptPubKey equal to the push value (see #1 above)=2E
>
>        (With due consideration for what happens if a script is reused
>         in multiple explicit fees, of course=2E)
>
>     B=2E Otherwise, add remaining dust to the implicit fee tally=2E
>
>8=2E For the very last transaction in the block, the miner builds a
>   transaction claiming ALL of these explicit fees, and with a single
>   zero-valued null/data output, thereby forwarding the fees on to the
>   coinbase, as far as old clients are concerned=2E  This is only
>   concerns consensus in that this final transaction does not change
>   any of the previously mentioned tallies=2E
>
>   (Aside: the zero-valued output is merely required because all
>    transactions must have at least one output=2E It does however make a
>    great location to put commitments for extensions to the block
>    header, as being on the right-most path of the Merkle tree can
>    mean shorter proofs=2E)
>
>9=2E The miner is allowed to claim subsidy + the miner's fee tally + the
>   explicit fee tally for themselves in the coinbase=2E  The coinbase is
>   also required to contain all rebated fees above the dust threshold=2E
>
>In summary, all transactions have the same actual fee rate equal to
>the minimum fee rate that went into the creation of the block, which
>is basically the marginal fee rate for transaction inclusion=2E
>
>A variant of this proposal is that instead of giving the implicit fee
>tally to the miner (the excess non-rebateable fees beyond the required
>minimum), it is carried forward from block to block in the final
>transaction and the miner is allowed to claim some average of past
>fees, thereby smoothing out fees or providing some other incentive=2E

------W9T8BLP4L26NF71V3ZRYJIEU5PAV22
Content-Type: text/html;
 charset=utf-8
Content-Transfer-Encoding: quoted-printable

<html><head></head><body>I&#39;m somewhat curious what the authors envision=
ed the real-world implications of this model to be=2E While blindly asking =
users to enter what they&#39;re willing to pay always works in theory, I=
9;d imagine in such a world the fee selection UX would be similar to what i=
t is today - users are provided a list of options with feerates and expecte=
d confirmation times from which to select=2E Indeed, in a world where users=
 pay a lower fee if they paid more than necessary fee estimation could be m=
ore willing to overshoot and the UX around RBF and CPFP could be simplified=
 greatly, but I&#39;m not actually convinced that it would result in higher=
 overall mining revenue=2E<br>
<br>
The UX issues with RBF and CPFP, not to mention the UX issues involved in =
optimizing for quick confirmation are, indeed, quite significant, but I bel=
ieve them to be solveable with rather striaght-forward changes=2E Making th=
e market more useable (for higher or lower overall miner revenue) may be a =
sufficient goal, however, to want to consider something like this=2E<br><br=
><div class=3D"gmail_quote">On September 28, 2017 9:06:29 PM EDT, Mark Frie=
denbach via bitcoin-dev &lt;bitcoin-dev@lists=2Elinuxfoundation=2Eorg&gt; w=
rote:<blockquote class=3D"gmail_quote" style=3D"margin: 0pt 0pt 0pt 0=2E8ex=
; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<pre class=3D"k9mail">This article by Ron Lavi, Or Sattath, and Aviv Zohar=
 was forwarded to<br />me and is of interest to this group:<br /><br />    =
&quot;Redesigning Bitcoin's fee market&quot;<br />    <a href=3D"https://ar=
xiv=2Eorg/abs/1709=2E08881">https://arxiv=2Eorg/abs/1709=2E08881</a><br /><=
br />I'll briefly summarize before providing some commentary of my own,<br =
/>including transformation of the proposed mechanism into a relatively<br /=
>simple soft-fork=2E  The article points out that bitcoin's auction<br />mo=
del for transaction fees / inclusion in a block is broken in the<br />sense=
 that it does not achieve maximum clearing price* and to prevent<br />strat=
egic bidding behavior=2E<br /><br />(* Maximum clearing price meaning highe=
st fee the user is willing to<br />   pay for the amount of time they had t=
o wait=2E  In other words, miner<br />   income=2E  While this is a common =
requirement of academic work on<br />   auction protocols, it's not obvious=
 that it provides intrinsic<br />   benefit to bitcoin for miners to extrac=
t from users the maximum<br />   amount of fee the market is willing to sup=
port=2E  However strategic<br />   bidding behavior (e=2Eg=2E RBF and CPFP)=
 does have real network and<br />   usability costs, which a more &quot;cor=
rect&quot; auction model would reduce<br />   in some use cases=2E)<br /><b=
r />Bitcoin is a &quot;pay your bid&quot; auction, where the user makes str=
ategic<br />calculations to determine what bid (=3Dfee) is likely to get ac=
cepted<br />within the window of time in which they want confirmation=2E  T=
his bid<br />can then be adjusted through some combination of RBF or CPFP=
=2E<br /><br />The authors suggest moving to a &quot;pay lowest winning bid=
&quot; model where<br />all transactions pay only the smallest fee rate pai=
d by any<br />transaction in the block, for which the winning strategy is t=
o bid the<br />maximum amount you are willing to pay to get the transaction=
<br />confirmed:<br /><br /><blockquote class=3D"gmail_quote" style=3D"marg=
in: 0pt 0pt 1ex 0=2E8ex; border-left: 1px solid #729fcf; padding-left: 1ex;=
"> Users can then simply set their bids truthfully to exactly the<br /> amo=
unt they are willing to pay to transact, and do not need to<br /> utilize f=
ee estimate mechanisms, do not resort to bid shading and do<br /> not need =
to adjust transaction fees (via replace-by-fee mechanisms)<br /> if the mem=
pool grows=2E<br /></blockquote><br /><br />Unlike other proposed fixes to =
the fee model, this is not trivially<br />broken by paying the miner out of=
 band=2E  If you pay out of band fee<br />instead of regular fee, then your=
 transaction cannot be included with<br />other regular fee paying transact=
ions without the miner giving up all<br />regular fee income=2E  Any transa=
ction paying less fee in-band than the<br />otherwise minimum fee rate need=
s to also provide ~1Mvbyte * fee rate<br />difference fee to make up for th=
at lost income=2E  So out of band fee is<br />only realistically considered=
 when it pays on top of a regular feerate<br />paying transaction that woul=
d have been included in the block anyway=2E<br />And what would be the poin=
t of that?<br /><br /><br />As an original contribution, I would like to no=
te that something<br />strongly resembling this proposal could be soft-fork=
ed in very easily=2E<br />The shortest explanation is:<br /><br />    For s=
criptPubKey outputs of the form &quot;&lt;max-42-byte-push&gt;&quot;, where=
<br />    the pushed data evaluates as true, a consensus rule is added that=
<br />    the coinbase must pay any fee in excess of the minimum fee rate<b=
r />    for the block to the push value, which is a scriptPubKey=2E<br /><b=
r />Beyond fixing the perceived problems of bitcoin's fee auction model<br =
/>leading to costly strategic behavior (whether that is a problem is a<br /=
>topic open to debate!), this would have the additional benefits of:<br /><=
br />    1=2E Allowing pre-signed transactions, of payment channel close-ou=
t<br />       for example, to provide sufficient fee for confirmation witho=
ut<br />       knowledge of future rates or overpaying or trusting a wallet=
 to<br />       be online to provide CPFP fee updates=2E<br /><br />    2=
=2E Allowing explicit fees in multi-party transaction creation<br />       =
protocols where final transaction sizes are not known prior to<br />       =
signing by one or more of the parties, while again not<br />       overpayi=
ng or trusting on CPFP, etc=2E<br /><br />    3=2E Allowing applications wi=
th expensive network access to pay<br />       reasonable fees for quick co=
nfirmation, without overpaying or<br />       querying a trusted fee estima=
tor=2E  Blockstream Satellite helps<br />       here, but rebateable fees p=
rovides an alternative option when<br />       full block feeds are not ava=
ilable for whatever reason=2E<br /><br />Using a fee rebate would carry a m=
arginal cost of 70-100 vbytes per<br />instance=2E  This makes it a rather =
expensive feature, and therefore in<br />my own estimation not something th=
at is likely to be used by most<br />transactions today=2E  However the cos=
t is less than CPFP, and so I<br />expect that it would be a heavily used f=
eature in things like payment<br />channel refund and uncooperative close-o=
ut transactions=2E<br /><br /><br />Here is a more worked out proposal, sui=
table for critiquing:<br /><br />1=2E A transaction is allowed to specify a=
n _Implicit Fee_, as usual, as<br />   well as one or more explicit _Rebate=
able Fees_=2E  A rebateable fee<br />   is an ouput with a scriptPubKey tha=
t consists of a single, minimal,<br />   nonzero push of up to 42 bytes=2E =
 Note that this is an always-true<br />   script that requires no signature=
 to spend=2E<br /><br />2=2E The _Fee Rate_ of a transaction is a fractiona=
l number equal to the<br />   combined implicit and rebateable fee divided =
by the size/weight of<br />   the transaction=2E<br /><br />   (A nontrivia=
l complication of this, which I will punt on for the<br />    moment, is ho=
w to group transactions for fee rate calculation such<br />    that CPFP do=
esn't bring down the minimum fee rate of the block,<br />    but to do so w=
ith rules that are both simple, because this is<br />    consensus code; an=
d fair, so as to prevent unintended use of a<br />    rebate fee by childre=
n or siblings=2E)<br /><br />3=2E The smallest fee rate of any non-coinbase=
 transaction (or<br />   transaction group) is the _Marginal Fee Rate_ for =
the block and is<br />   included in the witness for the block=2E<br /><br =
/>4=2E The verifier checks that each transaction or transaction grouping<br=
 />   provides a fee greater than or equal to the threshold fee rate, and<b=
r />   at least one is exactly equal to the marginal rate (which proves<br =
/>   the marginal rate is the minimum for the block)=2E<br /><br />This est=
ablishes the marginal fee rate, which alternatively expressed<br />is epsil=
on less than the fee rate that would have been required to get<br />into th=
e block, assuming there was sufficient space=2E<br /><br />5=2E A per-block=
 _Dust Threshold_ is calculated using the marginal fee<br />   rate and rea=
sonable assumptions about transaction size=2E<br /><br />6=2E For each tran=
saction (or transaction group), the _Required Fee_ is<br />   calculated to=
 be the marginal fee rate times the size/weight of the<br />   transaction=
=2E  Implicit fee is applied towards this required fee and<br />   added to=
 the _Miner's Fee Tally_=2E  Any excess implicit fee<br />   remaining is a=
dded to the _Implicit Fee Tally_=2E<br /><br />7=2E For each transaction (g=
roup), the rebateable fees contribute<br />   proportionally towards toward=
s meeting the remaining marginal fee<br />   requirement, if the implicit f=
ee failed to do so=2E  Of what's left,<br />   one of two things can happen=
 based on how much is remaining:<br /><br />     A=2E If greater than or eq=
ual to the dust threshold is remaining in<br />        a specific rebateabl=
e fee, a requirement is added that an<br />        output be provided in th=
e coinbase paying the remaining fee to<br />        a scriptPubKey equal to=
 the push value (see #1 above)=2E<br /><br />        (With due consideratio=
n for what happens if a script is reused<br />         in multiple explicit=
 fees, of course=2E)<br /><br />     B=2E Otherwise, add remaining dust to =
the implicit fee tally=2E<br /><br />8=2E For the very last transaction in =
the block, the miner builds a<br />   transaction claiming ALL of these exp=
licit fees, and with a single<br />   zero-valued null/data output, thereby=
 forwarding the fees on to the<br />   coinbase, as far as old clients are =
concerned=2E  This is only<br />   concerns consensus in that this final tr=
ansaction does not change<br />   any of the previously mentioned tallies=
=2E<br /><br />   (Aside: the zero-valued output is merely required because=
 all<br />    transactions must have at least one output=2E It does however=
 make a<br />    great location to put commitments for extensions to the bl=
ock<br />    header, as being on the right-most path of the Merkle tree can=
<br />    mean shorter proofs=2E)<br /><br />9=2E The miner is allowed to c=
laim subsidy + the miner's fee tally + the<br />   explicit fee tally for t=
hemselves in the coinbase=2E  The coinbase is<br />   also required to cont=
ain all rebated fees above the dust threshold=2E<br /><br />In summary, all=
 transactions have the same actual fee rate equal to<br />the minimum fee r=
ate that went into the creation of the block, which<br />is basically the m=
arginal fee rate for transaction inclusion=2E<br /><br />A variant of this =
proposal is that instead of giving the implicit fee<br />tally to the miner=
 (the excess non-rebateable fees beyond the required<br />minimum), it is c=
arried forward from block to block in the final<br />transaction and the mi=
ner is allowed to claim some average of past<br />fees, thereby smoothing o=
ut fees or providing some other incentive=2E<br /></pre></blockquote></div>=
</body></html>
------W9T8BLP4L26NF71V3ZRYJIEU5PAV22--