Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 90953AB8 for ; Fri, 29 Sep 2017 02:09:17 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-oi0-f51.google.com (mail-oi0-f51.google.com [209.85.218.51]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C8B3BD3 for ; Fri, 29 Sep 2017 02:09:14 +0000 (UTC) Received: by mail-oi0-f51.google.com with SMTP id i128so5342095oih.6 for ; Thu, 28 Sep 2017 19:09:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=z.cash; s=google; h=mime-version:in-reply-to:references:from:date:message-id:subject:to; bh=R4dd59OAohBHcJnQuUBCZnbljMuLv3MWclKV0VE8grQ=; b=SfDdntYOUnWSoLfrI25WW8F6rvYek2SUGDN7t/7Iwwnzb+3QU3rb+1HQ4TJYNLGfP4 rlBMH7Kpi04QaNma2vPDnahqS7I1RwRd69St31HsWk1hl2wGcZkBaGlVhobPTTHjOIH7 aOX15fB69JJQG5TGrZmJ/x7LH+VDK5OivmQd8Ry7KEa64UHdZ0ZiL2i5LehebW6tZO5L RZx3B0ZNywFW6gAN9TwNxiTLABXJDeiLyMA//tqaTSqyqBinTobPd9p95z+GlUM7TBbV ryJhQrGkSZAzR9XzHXxDbzdJOxzO6tuDH+/S+pjIkIOMDvYy2TpgRSbo9DeEQckSo8al ENzQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to; bh=R4dd59OAohBHcJnQuUBCZnbljMuLv3MWclKV0VE8grQ=; b=dBZzCNiqvVfo3hlg6stSOq6To01gZ6+g1Vgn9CsXtuuOr8e7k1wOde7mqWGBZGvNXN 8owogFhkCdr4oDuS6wV4yTzxf0+ZgmUNeDsdGeVTijnCwXihPvanTp/h9QUIbfUvM+Wa 6Ak9aGdLfLdiRsUjuiiq49msczBJvvLjzNwL8bPgvhQStSMBrcXKIGM9EF2kXWE0iiDj 9Q+4OVJY1HPFT3HWEdmGzaBnSgQBUKqrID/DUAIyEQ/oiKhf00S3A/xlHy/cXboYROXw /xKgs9Reb2JprxVkoLNzdTK55l4bIBKA7pmGpTU7LMIP2hup4QOkPCUkttvlbSPAU37p yIwA== X-Gm-Message-State: AHPjjUi4lcChMgnyzTOzwLc+0ebhzyuB0qQSLo0p/qyZ45is1Hfy73rO RmWpSjZ4JsHi0EC/lUKRdsJ+YYJ4SjJNbXJn81beMYMh X-Google-Smtp-Source: AOwi7QBec3a2fAYhiJfHWIBVTMd2R0dVPz5A6Y2YAOzvOFO6tfOtZQxF+K517qi9V6qUltKD7uvYAyxDCwWhmL4WvsE= X-Received: by 10.157.16.74 with SMTP id o10mr1871597oto.144.1506650954003; Thu, 28 Sep 2017 19:09:14 -0700 (PDT) MIME-Version: 1.0 Received: by 10.157.48.133 with HTTP; Thu, 28 Sep 2017 19:09:13 -0700 (PDT) In-Reply-To: References: <359FFE85-86AF-4FBD-9491-3528382E5002@friedenbach.org> From: Nathan Wilcox Date: Fri, 29 Sep 2017 11:09:13 +0900 Message-ID: To: Matt Corallo , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="001a1141be9eea0b81055a4a825e" X-Spam-Status: No, score=0.4 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,RCVD_IN_SORBS_SPAM autolearn=disabled version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Fri, 29 Sep 2017 03:03:47 +0000 Subject: Re: [bitcoin-dev] Rebatable fees & incentive-safe fee markets X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 29 Sep 2017 02:09:17 -0000 --001a1141be9eea0b81055a4a825e Content-Type: text/plain; charset="UTF-8" Happy to see Mark Friedenbach's strawman implementation. Two clarifying verifications: This implementation would allow old-style implicit fees which would have the same behavior (Pay-Your-Bid). Correct? In terms of space costs, rebateable fee txns (or CPFP chains, I'm less clear on that complication) add one UTXO 'internally' and new consensus rules require one UTXO in the coinbase for the rebate, correct? As for the paper itself: it doesn't account for high-latency/low-fee usage, correct? What if I want a transaction to complete anytime in the next N days for as cheap as given some probability of success? This has two parts: a. Is there a clear/clean game-theoretic-compatible UX for users? b. would the implementation be simple enough? If either a is 'no' or b is 'complicated', then the trade-off might not be much better than the status quo. Maybe for a high enough latency, the answer to a is 'yes' and b. is 'simple' by this strawman: try a tiny fee, if that doesn't work, try a new higher fee and repeat. Is that good enough? regards. Nathan On Fri, Sep 29, 2017 at 10:53 AM, Matt Corallo via bitcoin-dev < bitcoin-dev@lists.linuxfoundation.org> wrote: > I'm somewhat curious what the authors envisioned the real-world > implications of this model to be. While blindly asking users to enter what > they're willing to pay always works in theory, I'd imagine in such a world > the fee selection UX would be similar to what it is today - users are > provided a list of options with feerates and expected confirmation times > from which to select. Indeed, in a world where users pay a lower fee if > they paid more than necessary fee estimation could be more willing to > overshoot and the UX around RBF and CPFP could be simplified greatly, but > I'm not actually convinced that it would result in higher overall mining > revenue. > > 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 > believe them to be solveable with rather striaght-forward changes. Making > the market more useable (for higher or lower overall miner revenue) may be > a sufficient goal, however, to want to consider something like this. > > > On September 28, 2017 9:06:29 PM EDT, Mark Friedenbach via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> 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.org/abs/1709.08881 >> >> I'll briefly summarize before providing some commentary of my own, >> including transformation of the proposed mechanism into a relatively >> simple soft-fork. 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. >> >> (* Maximum clearing price meaning highest fee the user is willing to >> pay for the amount of time they had to wait. In other words, miner >> income. 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. However strategic >> bidding behavior (e.g. RBF and CPFP) does have real network and >> usability costs, which a more "correct" auction model would reduce >> in some use cases.) >> >> Bitcoin is a "pay your bid" auction, where the user makes strategic >> calculations to determine what bid (=fee) is likely to get accepted >> within the window of time in which they want confirmation. This bid >> can then be adjusted through some combination of RBF or CPFP. >> >> 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. >>> >> >> >> Unlike other proposed fixes to the fee model, this is not trivially >> broken by paying the miner out of band. 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. 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. 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. >> 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. >> The shortest explanation is: >> >> For scriptPubKey outputs of the form "", 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. >> >> 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. 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. >> >> 2. 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. >> >> 3. Allowing applications with expensive network access to pay >> reasonable fees for quick confirmation, without overpaying or >> querying a trusted fee estimator. Blockstream Satellite helps >> here, but rebateable fees provides an alternative option when >> full block feeds are not available for whatever reason. >> >> Using a fee rebate would carry a marginal cost of 70-100 vbytes per >> instance. 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. 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. >> >> >> Here is a more worked out proposal, suitable for critiquing: >> >> 1. A transaction is allowed to specify an _Implicit Fee_, as usual, as >> well as one or more explicit _Rebateable Fees_. A rebateable fee >> is an ouput with a scriptPubKey that consists of a single, minimal, >> nonzero push of up to 42 bytes. Note that this is an always-true >> script that requires no signature to spend. >> >> 2. 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. >> >> (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.) >> >> 3. 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. >> >> 4. 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). >> >> 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. >> >> 5. A per-block _Dust Threshold_ is calculated using the marginal fee >> rate and reasonable assumptions about transaction size. >> >> 6. For each transaction (or transaction group), the _Required Fee_ is >> calculated to be the marginal fee rate times the size/weight of the >> transaction. Implicit fee is applied towards this required fee and >> added to the _Miner's Fee Tally_. Any excess implicit fee >> remaining is added to the _Implicit Fee Tally_. >> >> 7. 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. Of what's left, >> one of two things can happen based on how much is remaining: >> >> A. 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). >> >> (With due consideration for what happens if a script is reused >> in multiple explicit fees, of course.) >> >> B. Otherwise, add remaining dust to the implicit fee tally. >> >> 8. 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. This is only >> concerns consensus in that this final transaction does not change >> any of the previously mentioned tallies. >> >> (Aside: the zero-valued output is merely required because all >> transactions must have at least one output. 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.) >> >> 9. The miner is allowed to claim subsidy + the miner's fee tally + the >> explicit fee tally for themselves in the coinbase. The coinbase is >> also required to contain all rebated fees above the dust threshold. >> >> 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. >> >> 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. >> >> > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev > > --001a1141be9eea0b81055a4a825e Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Happy to see Mark Friedenbach's st= rawman implementation. Two clarifying verifications:

This implementa= tion would allow old-style implicit fees which would have the same behavior= (Pay-Your-Bid). Correct?

In terms of space costs, rebateable fee tx= ns (or CPFP chains, I'm less clear on that complication) add one UTXO &= #39;internally' and new consensus rules require one UTXO in the coinbas= e for the rebate, correct?


As for the paper itself: i= t doesn't account for high-latency/low-fee usage, correct? What if I wa= nt a transaction to complete anytime in the next N days for as cheap as giv= en some probability of success?

This has two parts: a. Is ther= e a clear/clean game-theoretic-compatible UX for users? b. would the implem= entation be simple enough? If either a is 'no' or b is 'complic= ated', then the trade-off might not be much better than the status quo.=

Maybe for a high enough latency, the answer to a is 'yes&= #39; and b. is 'simple' by this strawman: try a tiny fee, if that d= oesn't work, try a new higher fee and repeat. Is that good enough?
<= br>
regards.
Nathan

<= br>
On Fri, Sep 29, 2017 at 10:53 AM, Matt Corall= o via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.o= rg> wrote:
I'm som= ewhat curious what the authors envisioned the real-world implications of th= is model to be. While blindly asking users to enter what they're willin= g to pay always works in theory, I'd imagine in such a world the fee se= lection UX would be similar to what it is today - users are provided a list= of options with feerates and expected confirmation times from which to sel= ect. Indeed, in a world where users pay a lower fee if they paid more than = necessary fee estimation could be more willing to overshoot and the UX arou= nd RBF and CPFP could be simplified greatly, but I'm not actually convi= nced that it would result in higher overall mining revenue.

The UX issues with RBF and CPFP, not to mention the UX issues involved in o= ptimizing for quick confirmation are, indeed, quite significant, but I beli= eve them to be solveable with rather striaght-forward changes. Making the m= arket more useable (for higher or lower overall miner revenue) may be a suf= ficient goal, however, to want to consider something like this.


On September 28, 2017 9:06:29= PM EDT, Mark Friedenbach via bitcoin-dev <bitcoin-dev@lists.linuxf= oundation.org> wrote:
This article by Ron Lavi, Or Sa=
ttath, and Aviv Zohar was forwarded to
me and is of interest to this gro=
up:

    "Redesigning Bitcoin's fee market"
    https://arxiv.or=
g/abs/1709.08881

I'll briefly summarize before providin=
g some commentary of my own,
including transformation of the proposed me=
chanism into a relatively
simple soft-fork.  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.

(* Maximum clearing p=
rice meaning highest fee the user is willing to
   pay for the amount of=
 time they had to wait.  In other words, miner
   income.  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 willin=
g to support.  However strategic
   bidding behavior (e.g. RBF and CPFP)=
 does have real network and
   usability costs, which a more "corre=
ct" auction model would reduce
   in some use cases.)

Bitcoi=
n is a "pay your bid" auction, where the user makes strategic
=
calculations to determine what bid (=3Dfee) is likely to get accepted
wi=
thin the window of time in which they want confirmation.  This bid
can t=
hen be adjusted through some combination of RBF or CPFP.

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 t=
he block, for which the winning strategy is to bid the
maximum amount yo=
u are willing to pay to get the transaction
confirmed:

 Users can then simply set their bids truthf=
ully 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 shadi=
ng and do
 not need to adjust transaction fees (via replace-by-fee mecha=
nisms)
 if the mempool grows.


Unlike other propo= sed fixes to the fee model, this is not trivially
broken by paying the m= iner out of band. If you pay out of band fee
instead of regular fee, th= en your transaction cannot be included with
other regular fee paying tra= nsactions without the miner giving up all
regular fee income. Any trans= action 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. So out of band fee is
only realistically considered when i= t pays on top of a regular feerate
paying transaction that would have be= en included in the block anyway.
And what would be the point of that?

As an original contribution, I would like to note that somethingstrongly resembling this proposal could be soft-forked in very easily.The shortest explanation is:

For scriptPubKey outputs of the fo= rm "<max-42-byte-push>", where
the pushed data evalu= ates as true, a consensus rule is added that
the coinbase must pay a= ny fee in excess of the minimum fee rate
for the block to the push v= alue, which is a scriptPubKey.

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. Allowing pre-signed transactions,= of payment channel close-out
for example, to provide sufficient = fee for confirmation without
knowledge of future rates or overpay= ing or trusting a wallet to
be online to provide CPFP fee updates= .

2. Allowing explicit fees in multi-party transaction creation<= br> protocols where final transaction sizes are not known prior to signing by one or more of the parties, while again not
ov= erpaying or trusting on CPFP, etc.

3. Allowing applications with= expensive network access to pay
reasonable fees for quick confir= mation, without overpaying or
querying a trusted fee estimator. = Blockstream Satellite helps
here, but rebateable fees provides an= alternative option when
full block feeds are not available for w= hatever reason.

Using a fee rebate would carry a marginal cost of 70= -100 vbytes per
instance. 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. However the cost is less than CPFP, and so = I
expect that it would be a heavily used feature in things like payment<= br>channel refund and uncooperative close-out transactions.


Here= is a more worked out proposal, suitable for critiquing:

1. A transa= ction is allowed to specify an _Implicit Fee_, as usual, as
well as o= ne or more explicit _Rebateable Fees_. A rebateable fee
is an ouput = with a scriptPubKey that consists of a single, minimal,
nonzero push = of up to 42 bytes. Note that this is an always-true
script that requ= ires no signature to spend.

2. The _Fee Rate_ of a transaction is a = fractional number equal to the
combined implicit and rebateable fee d= ivided by the size/weight of
the transaction.

(A nontrivial= complication of this, which I will punt on for the
moment, is how t= o group transactions for fee rate calculation such
that CPFP doesn&#= 39;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 fai= r, so as to prevent unintended use of a
rebate fee by children or si= blings.)

3. The smallest fee rate of any non-coinbase transaction (o= r
transaction group) is the _Marginal Fee Rate_ for the block and is<= br> included in the witness for the block.

4. 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 min= imum for the block).

This establishes the marginal fee rate, which a= lternatively expressed
is epsilon less than the fee rate that would have= been required to get
into the block, assuming there was sufficient spac= e.

5. A per-block _Dust Threshold_ is calculated using the marginal = fee
rate and reasonable assumptions about transaction size.

6.= For each transaction (or transaction group), the _Required Fee_ is
c= alculated to be the marginal fee rate times the size/weight of the
tr= ansaction. Implicit fee is applied towards this required fee and
add= ed to the _Miner's Fee Tally_. Any excess implicit fee
remaining= is added to the _Implicit Fee Tally_.

7. For each transaction (grou= p), the rebateable fees contribute
proportionally towards towards mee= ting the remaining marginal fee
requirement, if the implicit fee fail= ed to do so. Of what's left,
one of two things can happen based = on how much is remaining:

A. If greater than or equal to the du= st threshold is remaining in
a specific rebateable fee, a requir= ement is added that an
output be provided in the coinbase paying= the remaining fee to
a scriptPubKey equal to the push value (se= e #1 above).

(With due consideration for what happens if a s= cript is reused
in multiple explicit fees, of course.)

= B. Otherwise, add remaining dust to the implicit fee tally.

8. F= or the very last transaction in the block, the miner builds a
transac= tion claiming ALL of these explicit fees, and with a single
zero-valu= ed null/data output, thereby forwarding the fees on to the
coinbase, = as far as old clients are concerned. This is only
concerns consensus= in that this final transaction does not change
any of the previously= mentioned tallies.

(Aside: the zero-valued output is merely requ= ired because all
transactions must have at least one output. 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.)

9. The miner is allowed to claim s= ubsidy + the miner's fee tally + the
explicit fee tally for thems= elves in the coinbase. The coinbase is
also required to contain all = rebated fees above the dust threshold.

In summary, all transactions = have the same actual fee rate equal to
the minimum fee rate that went in= to the creation of the block, which
is basically the marginal fee rate f= or transaction inclusion.

A variant of this proposal is that instead= of giving the implicit fee
tally to the miner (the excess non-rebateabl= e 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 a= verage of past
fees, thereby smoothing out fees or providing some other = incentive.

______________= _________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.= linuxfoundation.org
https://lists.linuxfoundation.org= /mailman/listinfo/bitcoin-dev


--001a1141be9eea0b81055a4a825e--