[Bitcoin-development] Making fee estimation better

[Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1239 bytes --]

Quick thought on how to make blockchain-based fee estimates work better
in the context of out-of-band mining contracts: have miners advertise in
their coinbase's what fees were actually paid, as opposed to appear to
have been paid.

The logic is very simple: we assume miners aren't an effective cartel
and are willing to undercut each other. Therefore it's in their
interests for people to broadcast a transaction with a fee that is
competitive the first time around so they can get onto mining it
immediately.

Granted, those incentives may not be as strong as one would like, and
there could be some perverse ones as well, but it's a line of thought
worth thinking about more.


A related idea: let miners advertise a address to submit transactions
too. (like a node IP) The inherent proof-of-work is nice and could help
people more securely find someone to connect too with the inherent proof
that a lot of work went into mining the block with the address in it.

Obviously, lots of downsides too, but it's a different security model
than other forms of bootstrapping, and that's probably useful in of
itself.

-- 
'peter'[:-1]@petertodd.org
0000000000000001fce0617deb31cc20bec2903cd10dc352ac3b2fc1af6b27f0

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 788 bytes --]

On Thu, Oct 24, 2013 at 4:30 PM, Peter Todd <pete@petertodd.org> wrote:

> Quick thought on how to make blockchain-based fee estimates work better
> in the context of out-of-band mining contracts: have miners advertise in
> their coinbase's what fees were actually paid, as opposed to appear to
> have been paid.


This is interesting, but I suppose some miners may have business models
that can't be easily summed up as a "fee" - like all-you-can-eat deals with
certain providers, or preference to certain kinds of transactions etc.

For the concern that estimation might force fees down too far if miners
include private transactions, I thought the estimates were calculated only
on broadcast transactions, so transactions that just appear in a block
won't ever influence the estimate?

[-- Attachment #2: Type: text/html, Size: 1158 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1568 bytes --]

On Thu, Oct 24, 2013 at 04:38:16PM +0200, Mike Hearn wrote:
> On Thu, Oct 24, 2013 at 4:30 PM, Peter Todd <pete@petertodd.org> wrote:
> 
> > Quick thought on how to make blockchain-based fee estimates work better
> > in the context of out-of-band mining contracts: have miners advertise in
> > their coinbase's what fees were actually paid, as opposed to appear to
> > have been paid.
> 
> 
> This is interesting, but I suppose some miners may have business models
> that can't be easily summed up as a "fee" - like all-you-can-eat deals with
> certain providers, or preference to certain kinds of transactions etc.

For sure, although *usually* all kinds of odd-ball forms of compensation
can be turned into a dollar figure. :)

> For the concern that estimation might force fees down too far if miners
> include private transactions, I thought the estimates were calculated only
> on broadcast transactions, so transactions that just appear in a block
> won't ever influence the estimate?

The thing is if a miner is mining a transaction, even in exchange for a
out-of-band fee if they succeed, they probably still have an incentive
to a: ask the sender to include enough of a fee that it propagates, and
b: broadcast it themselves to make sure it's in other nodes signature
caches so their blocks propagate fast. (esp. with by-txid-only relaying)

Anyway, in what circumstance would a customer want an exclusive contract
with a miner?

-- 
'peter'[:-1]@petertodd.org
0000000000000000bf7bcf3da1b3b228216b72fefccbed84becaaba6fcc6aff2

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 566 bytes --]

Well, miners are all supposed to be more or less equivalent - modulo
differences in tx acceptance policies - so I'd hope that having out of bad
fee mechanisms yet still broadcasting the TX isn't that common. If it was
broadcasted, it should get mined in short order, otherwise things are going
wrong.

On Thu, Oct 24, 2013 at 4:43 PM, Peter Todd <pete@petertodd.org> wrote:

> Anyway, in what circumstance would a customer want an exclusive contract
> with a miner?
>

I was thinking for transactions that aren't standard so have to be
submitted to miners directly.

[-- Attachment #2: Type: text/html, Size: 984 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1351 bytes --]

On Thu, Oct 24, 2013 at 04:46:41PM +0200, Mike Hearn wrote:
> Well, miners are all supposed to be more or less equivalent - modulo
> differences in tx acceptance policies - so I'd hope that having out of bad
> fee mechanisms yet still broadcasting the TX isn't that common. If it was
> broadcasted, it should get mined in short order, otherwise things are going
> wrong.

Eligius has contracts to do transaction mining, and it's currently 10%
of the hashing power.

As I said elsewhere, a good use-case for OOB fee payment is for
merchants who use the payment protocol, and want to get their customers
transactions mined as efficiently and cheaply as possible.
(child-pays-for-parent has more blockchain bloat and thus extra expense)

> On Thu, Oct 24, 2013 at 4:43 PM, Peter Todd <pete@petertodd.org> wrote:
> 
> > Anyway, in what circumstance would a customer want an exclusive contract
> > with a miner?
> >
> 
> I was thinking for transactions that aren't standard so have to be
> submitted to miners directly.

Sure, but even then there's no harm in letting more than one miner know
about it.

There's even an existing form of this: P2Pool lets shares be accompanied
by up to 50KB worth of transactions of any form.

-- 
'peter'[:-1]@petertodd.org
000000000000000d2860c825ea223b805c60a33b26b9b70616698033d360b066

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 2079 bytes --]

On Fri, Oct 25, 2013 at 12:54 AM, Peter Todd <pete@petertodd.org> wrote:

> Eligius has contracts to do transaction mining, and it's currently 10%
> of the hashing power.
>

Yes, and I asked Luke what percentage of that 10% is OOB fee payments, and
the answer is "a small percentage."

So: there are multiple layers of reasons why OOB fee payments will not
screw up the fee estimation code:

+ If the transactions are not broadcast, then they have no effect on the
estimates.

+ If the transactions are broadcast but not relayed because their priority
and fee are way below current estimates then they will have very close to
zero effect on the estimates.

+ If the OOB transaction is zero-fee, zero-priority (e.g comes from a
high-tx-volume service and relies on recently spent outputs) it will have
zero effect on the estimates.

+ If they make up less than about 40% of broadcast transactions they will
have very close to zero effect on the fee estimate (because of the
distribution of fees and behavior of taking a median)

The only case where the estimation code is even slightly likely to get
confused is estimating the priority needed to get into a block IF there are
a significant number of zero-fee, low-but-not-zero-priority OOB
transactions being broadcast.

And since priority naturally increases over time, even if that case DOES
occur the failure is very mild-- it means your free transactions might have
to build up more priority than the code estimates before successfully
entering a block.  If that gets to be an actual problem, then implementing
Pieter's idea of keeping track of memory pool transactions that are NOT
getting mined would fix it. But I don't want to waste time on a theoretical
problem when it is very possible miners will decide to stop accepting free
transactions alltogether.



And all of the above is completely orthogonal to child-pays-for-parent
and/or replace-with-higher-fee.

PS: I would appreciate it if you stop saying things like "Regarding the
transaction fee estimate code, it's not very well thought out."

-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 2959 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2284 bytes --]

On Fri, Oct 25, 2013 at 06:39:34AM +1000, Gavin Andresen wrote:
> Yes, and I asked Luke what percentage of that 10% is OOB fee payments, and
> the answer is "a small percentage."
> 
> So: there are multiple layers of reasons why OOB fee payments will not
> screw up the fee estimation code:

I've responded to nearly all those arguments elsewhere, but anyway...

> And all of the above is completely orthogonal to child-pays-for-parent
> and/or replace-with-higher-fee.

Indeed. Quoting myself here: "What we should have is both: fee
estimation with replacement so you can replace transactions in the event
that the estimate was too low."

So on IRC you were talking about very agressive mempool expiration - as
little as a block or two before tx's are expired. Now if a tx does fail
to get mined in that short window, am I correct in saying you want a way
to modify the fee it pays and rebroadcast? In which case wallet software
and other players in the ecosystem will have to adjust to the fact that
they can expect to see relatively frequent double-spends of unconfirmed
transactions?

As you know I've already written relaying/mempool code for
tx-replacement and replace-by-fee; it's the wallet code that's the hard
part that I haven't done. If you're already planning on changing the
wallet side of things to handle replacement-through-expiration that'd
save me a lot of hard work. You're probably better qualified to write
that code too; I'm not very familiar with the wallet.

Worth thinking about the whole ecosystem of wallets involved; they all
have to handle double-spends gracefully to make tx replacement of any
kind user friendly. We should try to give people a heads up that this is
coming soon if that's your thinking.


Also, regarding tx replacement user experience:

> Come back a few hours later and find out you need to type in your
> password again so your client can unlock your wallet, resign, and
> re-transmit with a higher fee?

Password-using wallets sign multiple versions of the transaction in
advance of course and release the higher fee versions only later if
required. (could be applied to coinjoin too)

-- 
'peter'[:-1]@petertodd.org
0000000000000005391e2338afe5204414d66b1f140b172da651daedf5663af2

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Jeremy Spilman]

[-- Attachment #1: Type: text/plain, Size: 759 bytes --]

Gavin, can you confirm the best place to  read  up on the discuss fee  
estimation changes for v0.9?

I think fee estimation at its core is about providing a data point, or  
even call it an API, which can be used however you see fit.

What parameters do I want to see in a 'fee estimation' API?

  - 30 minutes vs 24 hours processing time
  - Confidence Levels (50%/90%)

What properties does the result have?
   - Is it globally consistent?

Talking about fees.. I read this:  
https://gist.github.com/gavinandresen/2961409 and there is so much there I  
really liked.

Any pointers for reading more about the leading theories on transaction  
fees? For example, how well do they correlate with network security? Are  
we getting what we are paying for? :-)

[-- Attachment #2.1: Type: text/html, Size: 1168 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Andreas Petersson]

> Worth thinking about the whole ecosystem of wallets involved; they all
> have to handle double-spends gracefully to make tx replacement of any
> kind user friendly. We should try to give people a heads up that this is
> coming soon if that's your thinking.

If there is a situation where wallets are supposed to constantly monitor
the tx propagation and recreate their transactions with different fees,
this would make a lot of usecases inconvenient.
half-offline bluetooth transactions, users with unstable connections,
battery power lost, etc, etc. - and last but not least power concerns on
hardware wallets on the bitcoincard (tx signing drains a significant amount
of power and should therefore only be done once)

-Andreas

Re: [Bitcoin-development] Making fee estimation better

[Mark Friedenbach]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

There's no reason the signing can't be done all at once. The wallet
app would create and sign three transactions, paying avg-std.D, avg,
and avg+std.D fee. It just waits to broadcast the latter two until it
has to.

On 10/25/13 5:02 AM, Andreas Petersson wrote:
> 
> 
>> Worth thinking about the whole ecosystem of wallets involved;
>> they all have to handle double-spends gracefully to make tx
>> replacement of any kind user friendly. We should try to give
>> people a heads up that this is coming soon if that's your
>> thinking.
> 
> If there is a situation where wallets are supposed to constantly
> monitor the tx propagation and recreate their transactions with
> different fees, this would make a lot of usecases inconvenient. 
> half-offline bluetooth transactions, users with unstable
> connections, battery power lost, etc, etc. - and last but not least
> power concerns on hardware wallets on the bitcoincard (tx signing
> drains a significant amount of power and should therefore only be
> done once)
> 
> -Andreas
> 
> ------------------------------------------------------------------------------
>
> 
October Webinars: Code for Performance
> Free Intel webinars can help you accelerate application
> performance. Explore tips for MPI, OpenMP, advanced profiling, and
> more. Get the most from the latest Intel processors and
> coprocessors. See abstracts and register > 
> http://pubads.g.doubleclick.net/gampad/clk?id=60135991&iu=/4140/ostg.clktrk
>
> 
_______________________________________________
> Bitcoin-development mailing list 
> Bitcoin-development@lists.sourceforge.net 
> https://lists.sourceforge.net/lists/listinfo/bitcoin-development
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG/MacGPG2 v2.0.19 (Darwin)
Comment: GPGTools - http://gpgtools.org
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQIcBAEBAgAGBQJSanJVAAoJEAdzVfsmodw4RHYQAKBrku4S80GXtbt4wBgkRMgx
EQuobBrwtknxHOhKyYuBeAJ+h8ao1zSSNeqLvS5fJShH7vwBD2UOePLw4Nsy5p9U
pe56c07pRmgi+EWdq/3o1tggp9HN0FR3HDRwt03U4qrPTx449kHb11aOw5KZH7VS
ZiG09gKxkMPOtUy9dmVukjkG3zQ1AWjax+aOoseCnkU8u1I4kfhOyWLIjD7ciMm4
07gD8MzBLHTfJ6/pwUczQCby76Xdg51G/5d/toT3EnXyEOC7tCbI4xunAn1eIyg3
eCUNYaOQ7WYV9tjBUDGFwjVkGDJ8KdzEUqMPEK5nAWF29vmrwBSGJ4H2C47OkTQA
58Ie0hEYc5FMNuUCUWz3IGt2zoQ/8YENtNUDKG8oVoNhAIp5zkLK8wsMAJjZP6WM
z56JUl8NZ2Ka5U1OelImGGVZIx4NXrXlccyxemAn3/c+krkpNv0CHAeMCeNbPG8i
e4l2vQandiBW4NBGVYcm5A/EO6VJHAJhLEPT0pjmbuq4qTACo4Fgeb0LpOnWb/1a
6b1SdGGhMMrXeR2IaIbnx0+0WArixsOPl9w+R9WbrMh8g7hYBLH8EpGrRj0omim7
OoJb+W599HU37XZyWtuov+8Ouh5DpnP9l4hvNxHmro77uPPq10i/ibMd0Bnm4zZd
ALtIYpYYgUCN1D9lQwPQ
=BjIH
-----END PGP SIGNATURE-----

Re: [Bitcoin-development] Making fee estimation better

[Andreas Petersson]

> There's no reason the signing can't be done all at once. The wallet
> app would create and sign three transactions, paying avg-std.D, avg,
> and avg+std.D fee. It just waits to broadcast the latter two until it
> has to.

i see several reasons why this is problematic. 
So how would that work in a setting where the user signs a transaction
created offline, transmitted via Bluetooth via a one-way broadcast?
does it transmit all 3 tx to the receiver and just hopes they he will do
the "right thing"?


> 
> On 10/25/13 5:02 AM, Andreas Petersson wrote:
>> 
>> 
>>> Worth thinking about the whole ecosystem of wallets involved;
>>> they all have to handle double-spends gracefully to make tx
>>> replacement of any kind user friendly. We should try to give
>>> people a heads up that this is coming soon if that's your
>>> thinking.
>> 
>> If there is a situation where wallets are supposed to constantly
>> monitor the tx propagation and recreate their transactions with
>> different fees, this would make a lot of usecases inconvenient. 
>> half-offline bluetooth transactions, users with unstable
>> connections, battery power lost, etc, etc. - and last but not least
>> power concerns on hardware wallets on the bitcoincard (tx signing
>> drains a significant amount of power and should therefore only be
>> done once)
>> 
>>

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1681 bytes --]

On Fri, Oct 25, 2013 at 02:02:35PM +0200, Andreas Petersson wrote:
> 
> 
> > Worth thinking about the whole ecosystem of wallets involved; they all
> > have to handle double-spends gracefully to make tx replacement of any
> > kind user friendly. We should try to give people a heads up that this is
> > coming soon if that's your thinking.
> 
> If there is a situation where wallets are supposed to constantly monitor
> the tx propagation and recreate their transactions with different fees,
> this would make a lot of usecases inconvenient.
> half-offline bluetooth transactions, users with unstable connections,
> battery power lost, etc, etc. - and last but not least power concerns on
> hardware wallets on the bitcoincard (tx signing drains a significant amount
> of power and should therefore only be done once)

Anyway, as I've said repeatedly my problem with fee estimation is that
it needs to be combined with some form of transaction replacement to
give users a way to recover from bad estimates, not that I think the
idea shouldn't be implemented at all. After all, we alrady have fee
estimation: wallet authors and users manully estimate fees!

This particular case is a nasty one re: recovering from a bad estimate,
and it's exactly why the payment protocol is designed for the sender to
give the receiver a copy of every transaction they make so the receiver
can be held responsible for getting them mined, eg. with
child-pays-for-parent, out-of-band fee payment, or maybe even by adding
inputs to the transaction. (SIGHASH_ANYONECANPAY)

-- 
'peter'[:-1]@petertodd.org
0000000000000001231d6e04b4b18f85fa0ad00e837727e7141eaa8cfecc734b

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Jeremy Spilman]

Do you think we're at the point where wallets have to be able to "actively  
bid" the fee using replacement due to block contention?

I think a fee estimation API is just a data point. Depending on the  
properties of the estimator, and how that's presented in the UI, it could  
serve to either increase or decrease the need for recovery.

Like you said, we already have "fee estimation" in the form of "user,  
please estimate the fee!" Now we want to make fee estimation "better", and  
one key aspect of better fee estimation is decreasing the need for  
recovery. Techniques like signing multiple transactions with different fee  
levels should become less useful the better you are at estimating the fee.

What I find interesting is that fee estimation can look at the size and  
type of the transaction, the age of the inputs, the number of inputs  
versus outputs, amount of the outputs, factor in [assumptions about] what  
fee policies miners are actually using, and after all that, look at the  
actual competing transactions on the blockchain and try to figure out how  
many of those are even real.

For example, if you just look at fee-per-KB of mempool versus fee-per-KB  
of recently mined transactions, without taking into account input age,  
number of inputs vs outputs, output amounts... all the other things miner  
might have used to discriminate between transactions, then I don't think  
you'll end up with a better fee estimator.

Contention might bump you out of a few blocks, but if the basis for  
calculating the fee is fundamentally compatible with the relay policies  
and the transaction-inclusion policies being run by large mining pools,  
the transaction isn't dead, it's just pending.

On Fri, 25 Oct 2013 09:13:23 -0700, Peter Todd <pete@petertodd.org> wrote:

> On Fri, Oct 25, 2013 at 02:02:35PM +0200, Andreas Petersson wrote:
>>
>>
>> > Worth thinking about the whole ecosystem of wallets involved; they all
>> > have to handle double-spends gracefully to make tx replacement of any
>> > kind user friendly. We should try to give people a heads up that this  
>> is
>> > coming soon if that's your thinking.
>>
>> If there is a situation where wallets are supposed to constantly monitor
>> the tx propagation and recreate their transactions with different fees,
>> this would make a lot of usecases inconvenient.
>> half-offline bluetooth transactions, users with unstable connections,
>> battery power lost, etc, etc. - and last but not least power concerns on
>> hardware wallets on the bitcoincard (tx signing drains a significant  
>> amount
>> of power and should therefore only be done once)
>
> Anyway, as I've said repeatedly my problem with fee estimation is that
> it needs to be combined with some form of transaction replacement to
> give users a way to recover from bad estimates, not that I think the
> idea shouldn't be implemented at all. After all, we alrady have fee
> estimation: wallet authors and users manully estimate fees!
>
> This particular case is a nasty one re: recovering from a bad estimate,
> and it's exactly why the payment protocol is designed for the sender to
> give the receiver a copy of every transaction they make so the receiver
> can be held responsible for getting them mined, eg. with
> child-pays-for-parent, out-of-band fee payment, or maybe even by adding
> inputs to the transaction. (SIGHASH_ANYONECANPAY)

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4314 bytes --]

On Fri, Oct 25, 2013 at 12:35:34PM -0700, Jeremy Spilman wrote:
> Do you think we're at the point where wallets have to be able to
> "actively bid" the fee using replacement due to block contention?

If Bitcoin continues to grow we probably will be at some as-yet-unknown
point in the future.

> I think a fee estimation API is just a data point. Depending on the
> properties of the estimator, and how that's presented in the UI, it
> could serve to either increase or decrease the need for recovery.
> 
> Like you said, we already have "fee estimation" in the form of
> "user, please estimate the fee!" Now we want to make fee estimation
> "better", and one key aspect of better fee estimation is decreasing
> the need for recovery. Techniques like signing multiple transactions
> with different fee levels should become less useful the better you
> are at estimating the fee.

Yes, but equally all estimates are imperfect, and you can trade-off risk
that your transaction will not go through initially for lower fees.

Estimates can be made sufficiently conservative that they are rarely
wrong - this is basically the strategy of the current system. Given that
demand for blockchain space isn't "saturated" it works reasonably well
for now. But without a good mechanism to recover from an initial bad
estimate you have to be more conservative than is efficient.

> What I find interesting is that fee estimation can look at the size
> and type of the transaction, the age of the inputs, the number of
> inputs versus outputs, amount of the outputs, factor in [assumptions
> about] what fee policies miners are actually using, and after all
> that, look at the actual competing transactions on the blockchain
> and try to figure out how many of those are even real.
> 
> For example, if you just look at fee-per-KB of mempool versus
> fee-per-KB of recently mined transactions, without taking into
> account input age, number of inputs vs outputs, output amounts...
> all the other things miner might have used to discriminate between
> transactions, then I don't think you'll end up with a better fee
> estimator.

To a first approximation there's not much reason for miners to take
anything other than fee-per-KB into account when determining what
transactions to mine; you want to stuff your 1MB block full of high
paying transactions. That a child tx may make a parent more profitable
to mine complicates things - Gavin's current fee estimator also makes
too-low-estimates in that case - and not all algorithms to do so will
come to the same conclusion. (doing it perfectly is something like
O(n^2), and imperfectly is O(1) but doesn't handle multiple children
well)

There are some second-order effects, a block is less likely to be
orphaned if all transactions in it have propagated sufficiently, thus a
miner should penalize very recently broadcast transactions. In addition
because miners never orphan themselves large miners have a significant
advantage regarding orphan-inducing effects. However those effects all
tend to be miner specific, and/or only temporary.

FWIW the logic behind orphans is currently rather frightening: a
rational miner will, the moment they learn that a block exists via the
quickly propagating block header, start working to extend that block
with one that either doesn't contain any transactions, or only contains
transactions they can be reasonably sure another miner didn't mine.
(e.g. via exclusive tx mining contracts) This boosts their profit
because they aren't wasting their effort while the rest of the block
propagates, removes much of the incentive have any limit on block size,
and incentivizes miners to extend chains they haven't actually validated
yet. (relying on the other miners incentive not to produce an invalid
block)

> Contention might bump you out of a few blocks, but if the basis for
> calculating the fee is fundamentally compatible with the relay
> policies and the transaction-inclusion policies being run by large
> mining pools, the transaction isn't dead, it's just pending.

With a size-limited blocks inclusion is more a matter of supply and
demand than policy.

-- 
'peter'[:-1]@petertodd.org
00000000000000066c29f3319f83f1c6e912b5add5534da1b938c4c65a07b02a

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1372 bytes --]

On Fri, Oct 25, 2013 at 12:51:22AM -0700, Jeremy Spilman wrote:
> Gavin, can you confirm the best place to  read  up on the discuss
> fee estimation changes for v0.9?
> 
> I think fee estimation at its core is about providing a data point,
> or even call it an API, which can be used however you see fit.
> 
> What parameters do I want to see in a 'fee estimation' API?
> 
>  - 30 minutes vs 24 hours processing time
>  - Confidence Levels (50%/90%)
> 
> What properties does the result have?
>   - Is it globally consistent?
> 
> Talking about fees.. I read this:
> https://gist.github.com/gavinandresen/2961409 and there is so much
> there I really liked.

State-of-the-art thinking has changed a lot; that document is over a
year old and needs significant changes to update it.

> Any pointers for reading more about the leading theories on
> transaction fees? For example, how well do they correlate with
> network security? Are we getting what we are paying for? :-)

Network security is currently funded by inflation rather than
transaction fees. This is likely to remain true for at least a few more
years. FWIW the cost of that security on a per transaction basis is
about $18, see http://blockchain.info/charts/cost-per-transaction

-- 
'peter'[:-1]@petertodd.org
0000000000000009b86605cc3235f2674600d5131dd437d941b479e78588177b

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Gavin Andresen]

[-- Attachment #1: Type: text/plain, Size: 4022 bytes --]

On Fri, Oct 25, 2013 at 5:51 PM, Jeremy Spilman <jeremy@taplink.co> wrote:

> **
> Gavin, can you confirm the best place to  read  up on the discuss fee
> estimation changes for v0.9?
>

The blog post is the best place for high-level overview.

The (closed for now, but it will come back) pull request is the best place
for low-level details and nit-picking discussion:
  https://github.com/bitcoin/bitcoin/pull/3024



> I think fee estimation at its core is about providing a data point, or
> even call it an API, which can be used however you see fit.
>
> What parameters do I want to see in a 'fee estimation' API?
>
>  - 30 minutes vs 24 hours processing time
>  - Confidence Levels (50%/90%)
>

The pull request adds an 'estimatefees' JSON-RPC api call:

====
estimatefees [prioritymedian=0.1] [feemedian=0.5]
Estimates the priority or fee a transaction needs
to be relayed across the network and included in
the block chain.

prioritymedian and feemedian are values from 0.0
to 1.0, where 0.0 will return the smallest
recently-included-in-a-block priority (or fee) seen,
1.0 the largest, and 0.5 the median priority (or fee)
for transactions that were broadcast on the network and
included in a block.

The default value for prioritymedian (0.1) is
chosen to return a priority for free transactions that
will eventually be confirmed, but might take several hours.
The default value for feemedian (0.5) returns how much
fee you should include to have your transactions confirmed
in an average amount of time.

Values returned are:
 freepriority : priority needed to out-compete a prioritymedian
  fraction of free transactions to be relayed and included in blocks.
 feeperbyte : fee, in satoshis/byte, needed to out-compete a
  feemedian fraction of fee-paying transactions.

Values of -1.0 are returned if not enough transactions
have been seen to make a good estimate.
====

That API doesn't give "30 minute versus 24 hour" confirmation time or
confidence intervals. I've always regretted not taking a statistics class;
if you want to help write code that estimates confidence intervals send me
an email. The API certainly isn't set in stone.

  - Is it globally consistent?
>

Ummm.... roughly, yes, it will be. Nodes that have just joined the network
and haven't seen enough transactions enter and leave the memory pool will
have a different estimate than long-running nodes, but in my testing the
estimate narrows down very quickly (with three or four blocks enough
fee-paying transactions have been seen to make a reasonable estimate; it
takes longer to see enough free transactions to get a good estimate of the
priority needed to get into the free space of a block).

RE: lots of other comments:

I feel like there is a lot of "in the weeds" discussion here about
theoretical, what-if-this-and-that-happens-in-the-future scenarios.

I would just like to point out (again) that this is not intended to be The
One True Solution For Transaction Fees And Transaction Prioritization. If
you've got a better mechanism for estimating fees, fantastic! If it turns
out estimates are often-enough wrong to be a problem and you've got a
solution for that, fantastic!

RE: are we already seeing pressure on transaction fees:

I believe we are, yes. As part of the prep work for the smart fee work I
spent some time plotting priority (for zero-fee transactions) and
transaction fee (for zero-priority transactions) versus confirmation time,
and it looks to me like people/services are starting to include more than
the hard-coded fees in the reference implementation-- I assume because they
want their transactions to be confirmed more quickly.

There is definitely already competition among zero-fee transactions for the
"free" block space. One of the reasons I'm comfortable with the fee changes
I'm proposing is if the estimation code gets it very wrong we'll see that
first as free transactions taking "too long" to confirm, but they'll
confirm eventually because priority increases over time.

-- 
--
Gavin Andresen

[-- Attachment #2: Type: text/html, Size: 5903 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1074 bytes --]

On Sat, Oct 26, 2013 at 10:25:06AM +1000, Gavin Andresen wrote:
> RE: lots of other comments:
> 
> I feel like there is a lot of "in the weeds" discussion here about
> theoretical, what-if-this-and-that-happens-in-the-future scenarios.

Um... yeah. Note how I said on your original pull-req that I'd be happy
to see it merged once the bugs were fixed (95% of the transactions it
produced had zero fees even with zero priority txins for some reason)
and you added a lower bound on fees in the wallet code as a "do no harm"
measure.

In fact, I think I wasn't being conservative enough given that it
affects relaying of transactions. Instead add both lower and upper
bounds to what the wallet and relaying code uses for 0.9.0 and it'd
probably be safe to merge.  We can get relax those "training wheels" in
0.9.1 or 0.9.2 once we've had some real-world experience with how the
estimation system works in practice, particularly for how it affects
relaying.

-- 
'peter'[:-1]@petertodd.org
00000000000000036253c7a02061121b6a12484278a3c472a22e47a821c28a69

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Making fee estimation better

[John Dillon]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On Sat, Oct 26, 2013 at 12:25 AM, Gavin Andresen
<gavinandresen@gmail.com> wrote:
> I feel like there is a lot of "in the weeds" discussion here about
> theoretical, what-if-this-and-that-happens-in-the-future scenarios.
>
> I would just like to point out (again) that this is not intended to be The
> One True Solution For Transaction Fees And Transaction Prioritization. If
> you've got a better mechanism for estimating fees, fantastic! If it turns
> out estimates are often-enough wrong to be a problem and you've got a
> solution for that, fantastic!

This discussion seems to be a lot of hot air over a simple observation that
estimates are imperfect and always will be. I do not understand you vehement
opposition the notion that a backup is a good thing except in the context that
replacement to change fees is halfway to profit-seeking replacement by fee.


Peter Todd:

You did a fair bit of leg work for replace-by-fee. Seems to me that
replace-for-fee will help prep infrastructure to eventual replace-by-fee usage,
while avoiding some of the politics around zero-conf transactions.

Go dust off your code and make it happen. I want to see a mempool
implementation similar to what you did for me on replace-for-fee, and I
understand much of the code is written in any case. This time I also want to
see a increasetxfee RPC command, and erasewallettx RPC command to deal with
duplicates. (I know touching the wallet code is scary) Having all will enable
usage, and I can imagine getting pools to use this will be easy enough.
(eligius?)

Here is your 4BTC bounty. In the event I am not around Gregory Maxwell can also
adjudicate. If both you and him feel someone else deserves it, by all means
send them the funds

bitcoind decodescript
522102d527466a144aac2030cd16d8be3d91231af26a95c2f8fc345a0ea0e8d53ac3914104d34775baab521d7ba2bd43997312d5f663633484ae1a4d84246866b7088297715a049e2288ae16f168809d36e2da1162f03412bf23aa5f949f235eb2e71417834104f005d39733ec09a1efa0cf8dcf3df50691e22c2374ff9a96d1d9ecb98a1e866c9f558a9fa1ba8ef0bbbad01f396768c0cb2dda9924dc0aaee1481604a8bd9ce453ae
{
    "asm" : "2 02d527466a144aac2030cd16d8be3d91231af26a95c2f8fc345a0ea0e8d53ac391
04d34775baab521d7ba2bd43997312d5f663633484ae1a4d84246866b7088297715a049e2288ae16f168809d36e2da1162f03412bf23aa5f949f235eb2e7141783
04f005d39733ec09a1efa0cf8dcf3df50691e22c2374ff9a96d1d9ecb98a1e866c9f558a9fa1ba8ef0bbbad01f396768c0cb2dda9924dc0aaee1481604a8bd9ce4
3 OP_CHECKMULTISIG",
    "reqSigs" : 2,
    "type" : "multisig",
    "addresses" : [
        "1L9p6QiWs2nfinyF4CnbqysWijMvvcsnxe",
        "1FCYd7j4CThTMzts78rh6iQJLBRGPW9fWv",
        "1GMaxweLLbo8mdXvnnC19Wt2wigiYUKgEB"
    ],
    "p2sh" : "3BST1dPxvgMGL3d9GPCHvTyZNsJ7YKTVPo"
}

(I realized right after my Tor payment protocol bounty that I would need some
bit of uniqueness like a bounty-specific pubkey to disambiguate multiple such
bounties!)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)

iQEcBAEBCAAGBQJSbg9wAAoJEEWCsU4mNhiPROQH/j+eWccx7oSVsr94cgGu7qza
kdnA7B6BAlnCPg3D+nqEFKDqzOyFppeHLadCCIYHHc5iVRfJuu9J1Gh9lgMCuyCW
qN7ZOBCARjiVOqrHPQR1pf18i0ko7dQWw2hZjy51XKuFxAsHwZpB/fzQCbVVzyB6
l5SECCou58bJ/x7B0L93K+yjXuMGnvi9jqiLAKkLWYDzVm7TeVWNVQr04B7sqi6A
mY+BfG61e7sqM2UJd69yGLeQdEfghYTmtA+EaaqYS0L11m7yFGZdUqD7UNy1FKO7
44M1JTh2ANnQRjSTJWOBXQNHMa/mxDCji1VFUtJhZKEuOZyWpGm7HMH1D3vcvcQ=
=4flN
-----END PGP SIGNATURE-----

[Bitcoin-development] Zeroconf-safe tx replacement (replace-for-fee)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 2083 bytes --]

On Mon, Oct 28, 2013 at 07:17:50AM +0000, John Dillon wrote:
> This discussion seems to be a lot of hot air over a simple observation that
> estimates are imperfect and always will be. I do not understand you vehement
> opposition the notion that a backup is a good thing except in the context that
> replacement to change fees is halfway to profit-seeking replacement by fee.
> 
> 
> Peter Todd:
> 
> You did a fair bit of leg work for replace-by-fee. Seems to me that
> replace-for-fee will help prep infrastructure to eventual replace-by-fee usage,
> while avoiding some of the politics around zero-conf transactions.

Here's the easy part done:

https://github.com/petertodd/bitcoin/tree/replace-for-fee

The rules are pretty simple: a replacement can only happen if every
output in the old transaction has a corresponding output in the new with
the same scriptPubKey, and of equal or greater value. All old tx outputs
must also be unspent. For implementation reasons, the order of the
outputs must also be the same, and the code will never replace two
transactions with one.

If someone wanted to mine with the above code, I'd say go right ahead.
(modulo general testing concerns)

Client-side though it shows a flaw with the Bitcoin wallet code that I
should have realized months ago: essentially a transaction in your
wallet with double-spent inputs forever blocks those inputs from being
spent. This doesn't happen too often because you're wallet will
currently never create double-spends, and will never respend unconfirmed
coins from someone else, but any CoinJoin implementation violates that
assumption and an attacker could easily cause a lot of havok.

I'll have to think about the issue further, but essentially the wallet
needs to recognize when a transaction's inputs no longer exist, and mark
the remaining inputs as unspent. Actually deleting those transactions
from your wallet is secondary to that more important concern.

-- 
'peter'[:-1]@petertodd.org
000000002fdfe6bbcffea72c934475cd4fcfe78d8d06910016d707c9b4a9e827

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Zeroconf-safe tx replacement (replace-for-fee)

[Adam Back]

Might leak less wiggle room and be simpler/more robut to validate that
*everything* has to be the same except for the amount going to one (presumed
change) address.  A privacy leak I know, but dont do that - ie send enough
change the first time.  And network analysis has shown change addresses
arent adding hardly any privacy.

We need more robust privacy fixes independently.  I do not support damaging
the 0-conf feature, so I think this later approach is a better track for
revising fees.

Adam

On Mon, Nov 04, 2013 at 05:52:43AM -0500, Peter Todd wrote:
>On Mon, Oct 28, 2013 at 07:17:50AM +0000, John Dillon wrote:
>> This discussion seems to be a lot of hot air over a simple observation that
>> estimates are imperfect and always will be. I do not understand you vehement
>> opposition the notion that a backup is a good thing except in the context that
>> replacement to change fees is halfway to profit-seeking replacement by fee.
>>
>>
>> Peter Todd:
>>
>> You did a fair bit of leg work for replace-by-fee. Seems to me that
>> replace-for-fee will help prep infrastructure to eventual replace-by-fee usage,
>> while avoiding some of the politics around zero-conf transactions.

Re: [Bitcoin-development] Zeroconf-safe tx replacement (replace-for-fee)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1267 bytes --]

On Mon, Nov 04, 2013 at 12:10:38PM +0100, Adam Back wrote:
> Might leak less wiggle room and be simpler/more robut to validate that
> *everything* has to be the same except for the amount going to one (presumed
> change) address.  A privacy leak I know, but dont do that - ie send enough
> change the first time.  And network analysis has shown change addresses
> arent adding hardly any privacy.
> 
> We need more robust privacy fixes independently.  I do not support damaging
> the 0-conf feature, so I think this later approach is a better track for
> revising fees.

There's been a number of uses found for tx-replacement beyond simply
modifying fees. In additition, allowing for the value of a specificly
designated change address to be changed after the fact is not compatible
with current zero-conf-using implementations; they don't know to treat a
txout as special so allowing its value to be reduced would allow for a
zeroconf attack.

Anyway, if you look at the code that actually implements the
replacement, it's extremely simple already. I see no reason to make it
less general; transaction relaying rules are not part of consensus.

-- 
'peter'[:-1]@petertodd.org
000000000000000a6dd96c551eca7299463e4e523462798a006535f412b519c7

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]