Remove hard-coded fee rules #3024

gavinandresen commented at 4:52 AM on September 23, 2013: contributor

See https://gist.github.com/gavinandresen/6548612 for complete design; executive summary:

This removes use of hard-coded fee constants for non-miners. Instead, fees are estimated based on transactions that recently left the memory pool because they were accepted into a block.

Pull-requesting this to get code review; I'll be working on a test plan next. @sipa suggested the estimate would be better if we looked at transactions that languished in the memory pool, instead; I think that would best be accomplished by implementing a memory-limited memory pool, and keeping track of priority/fee for transactions that get evicted from the pool because it was full. In any case, we will probably get a better estimate of miner's behavior by looking at both transactions that are accepted into blocks AND transactions that don't.

petertodd commented at 1:43 PM on September 23, 2013: contributor

@mikehearn I wrote up that proof-of-tx propagation idea we talked about a few weeks ago and posted it to the email list.

Given that fee estimation is still going to result in users getting their transactions stuck with few ways to fix the problem I think we'd be much better off pursuing tx-replacement first rather than easily sybilled fee estimation. Replacement can be implemented in a zero-conf safe way if desired (albeit at the cost of occasionally failing due to a lack of txouts) and would make wallets and other software across the whole Bitcoin ecosystem more resilient to the replacement-related errors that we'd see anyway with memory limited mempools. (never mind people exploiting tx mutability, or CoinJoin, or a zillion other ways)

gavinandresen commented at 7:30 PM on September 23, 2013: contributor

@petertodd: re: replacement: I haven't seen any reports of people using un-hacked reference code having transactions permanently stuck, so I don't see any need for transaction replacement yet. And this code should be strictly better at getting the fee or priority right the first time than the hard-coded rules we have now. @mikehearn: a 'txrejected' message when refusing to relay a transaction sounds reasonable to me, although you'll of course have to be careful about peers that lie or peers that send you a flood of 'txrejected' messages.

petertodd commented at 10:43 PM on September 23, 2013: contributor

@gavinandresen I've seen them get stuck for a dozen blocks - pretty poor user experience. No amount of fee estimation can predict the future, IE the network getting backlogged due to a string of bad luck.

sipa commented at 10:44 PM on September 23, 2013: member

I think getting wallets to deal well with non-confirming transactions is required for this anyway. We should detect conflicts of wallets with the mempool and the blockchain, and be able to mark non-confirming transactions as dead. If we have that, we'll have much more freedom to experiment with things like this.

petertodd commented at 10:56 PM on September 23, 2013: contributor

@sipa #2596 was going to be able to better handle those cases, although I haven't seen any action on that patch lately.

I think the correct logic is for the wallet to replace any existing transaction it sees with another transparently provided that at least one input is conflicting (making it not possible for both to be mined) and all outputs with scriptPubKey's in the wallet are greater or equal in value. Otherwise continue broadcasting the version we wanted mined.

The actual mempool replacement code I wrote awhile back: if at least one input conflicts, no new inputs are already spent, no output is already spent and new outputs are a superset of the old (txout value may be increased) replace the transaction.

luke-jr commented at 11:01 PM on September 23, 2013: member

Is there a summary of the logic used? How does it handle out-of-band mining arrangements, spam filters that use different logic than its own, etc?

sipa commented at 11:06 PM on September 23, 2013: member

@luke-jr That's the reason for suggesting looking at transaction remaining in the memory pool, rather than transactions being accepted.

See it this way: the P2P network is one way to distribute transactions to miners, but we shouldn't assume it's the only one. The memory pool is how we observe this distribution channel specifically. The block chain is the result of all miner's transactions combined.

petertodd commented at 11:25 PM on September 23, 2013: contributor

@sipa @luke-jr That's not what this patch implements: https://github.com/gavinandresen/bitcoin-git/commit/61bd47fa9b495ef99df9c3b995ac067344981b88#L4R19 and https://github.com/gavinandresen/bitcoin-git/commit/61bd47fa9b495ef99df9c3b995ac067344981b88#L4R340 - tx estimate data is added when a transaction is included in a block. Any miner who is accepting out-of-band payment for transactions previously broadcast will seriously mess up the estimates, driving required fees/priority down and getting users' transactions stuck. (though oddly it seems that tx's with both positive fees and priority are ignored: https://github.com/gavinandresen/bitcoin-git/commit/61bd47fa9b495ef99df9c3b995ac067344981b88#L4R101 - this ignores data from wallets that don't do priority calculations, probably the majority of transactions)

One really ugly thing about the out-of-band payment case is by driving down apparent fees it wastes network bandwidth relaying transactions that as little as a single miner can profitably mine.

NACK

sipa commented at 11:32 PM on September 23, 2013: member

@petertodd Oh, I didn't claim this patch did. Just explaining why I suggested using not-included-transactions (which Gavin mentioned in the pullreq).

sipa commented at 11:34 PM on September 23, 2013: member

@gavinandresen Maybe looking at mined transactions gives a bit better estimation than by looking at those that don't, but if that means a system that is more easily gamed (which is what it seems, to me), that's not necessarily worth it.

petertodd commented at 11:39 PM on September 23, 2013: contributor

@sipa Oh, sorry. Agreed on disliking easily gamed systems, especially given that we've got some fairly large transaction makers like bc.i who might very well have enough volume to create large amounts of out-of-band payments. (@luke-jr eligius has an agreement with mt. gox or something to mine tx's right?)

Anyway, the tx's getting stuck by accident problem is a good enough reason to do things differently.

petertodd commented at 11:52 PM on September 23, 2013: contributor

@luke-jr Also come to think of it the estimation code can't handle child-pays-for-parent properly either, particularly cases where one child pays for multiple parents. Similarly it doesn't properly handle anomalies in the average fee-per-kb paid by larger transactions compared to smaller ones, which will be the case given the tendency for wallets to apply minimum fees for small transactions. (a single large transaction has the same statistical sample weight as a single small one)

luke-jr commented at 12:21 AM on September 24, 2013: member

@sipa On the other hand, only looking at not-included-in-blocks fails to account for better spam filters on miners (for example, many miners filter out DP spam using non-mainline algorithms). So we definitely need to consider both sides of the spectrum. @petertodd I think you have a good case that we need transaction replacement, but we also need to get away from hard-coded fees too. Until @gavinandresen wrote this, I don't think anyone was actively working on either problem. So this is definitely a step forward - someone just needs to get the other foot to move forward along with it. The current algorithms already don't work nicely with CPFP, so I don't think that should be considered a blocker.

mikehearn commented at 8:24 AM on September 24, 2013: contributor

We're not going to do anything that breaks unconfirmed transactions.

bitcoinj already has some support for dead tx handling, although it's incomplete/buggy. However it's for double spends. We don't have reports of transactions getting stuck due to lack of fees from people using un-modified bitcoinj based wallets. When transactions don't go through for some reason it tends to be for other reasons (flaky network etc). However, a part of that reason is that we never generate free transactions. If we tried to do that, then transactions would get stuck due to the entirely arbitrary 27kb limit. Regular bitcoind nodes know when it's got full because they have the mempool, but other types of wallet don't. Removing the 27kb limit is an obvious and simple way to solve that.

gavinandresen commented at 9:42 AM on September 24, 2013: contributor

@petertodd : I am not claiming that this is the perfect solution. I am claiming that it is strictly better than the code that exists in the reference implementation today. You have a habit of claiming that things are "impossible" and simply being wrong (estimating can easily be extended to related-groups-of-transactions instead of single transactions for parent-pays functionality, for example).

RE: off-blockchain side-deals : please tell me more about how those actually work (@luke-jr : what is CPFP????).

gmaxwell commented at 1:36 PM on September 24, 2013: contributor

@mikehearn "Regular bitcoind nodes know when it's got full because they have the mempool, but other types of wallet don't.", no they don't— they don't make use of the knowledge. I suspect it wouldn't be super useful... I've never seen a stuck report that I could attribute to that.

(ah, I was busily typing out saying that I couldn't believe you weren't getting stuck reports— But android wallet doesn't support importing keys, does it? I think a majority of stuck reports I've gotten are not fee related, but are due to things like importing keys from bc.i wallets in an attempt to unstick a transaction there, and only ending up with more things stuck)

petertodd commented at 1:54 PM on September 24, 2013: contributor

@mikehearn Any users of bitcoinj out there who are often making large (1K+) transactions? Because the default rules are to have a minimum absolute transaction fee most people are paying at least twice the minimum fee/KB, and there's lots of traffic paying absolute minimums. In any case "stuck" is relative: if a transaction won't confirm for a few hours because everything else is paid more fees than me I'd very much call that stuck if I'm trying to buy some Bitcoins in person - that there is no way to set fees in the Android wallet is a complaint I've heard from people doing trades at the local Bitcoin meetup.

How do you feel zero-conf safe version of replacement breaks unconfirmed transactions? @gavinandresen Rather than trying to make this personal and putting words in my mouth, how about you just respond as to why you think this patch as it stands doesn't have cases where it will get people's transactions stuck due to bad fee estimation? If it does, how are you going to fix that before we merge it? @luke-jr I wouldn't say the current algorithms don't play nice with CPFP, rather I'd say they don't take advantage of it. The wallet doesn't re-spend unconfirmed transactions other than your own anyway, so the parent tx will always have what the wallet considers sufficient fees.

gmaxwell commented at 1:59 PM on September 24, 2013: contributor

@gavinandresen "Child pays for parent" @petertodd you sure about that? CPFP means that a block may contain a bunch of too-low-fee transactions which just got accepted because of a high fee parent. This means that CPFP will also distort the metric here.

petertodd commented at 2:01 PM on September 24, 2013: contributor

@gmaxwell I pointed out that problem above; by "current algorithms" luke and I mean what is in the current version, not this patch.

luke-jr commented at 9:09 PM on September 24, 2013: member

@mikehearn "Stuck" means never confirming, not merely delayed (as is the case with no-fee transactions that don't meet the 27kB limit - eventually, they'll get to be in the highest priority 27 kB!). The delay for no-fee transactions is by-design and intentional. It's fine for mempool-less nodes. @gavinandresen Off-chain side deals: for example, MtGox publishes a list of their outstanding txids, and Eligius uses the prioritisetransaction RPC call to give them priority over others, including when they might have otherwise failed to meet minimum fee rules. @petertodd CPFP is ignored by relay nodes already, thus a parent may not get relayed despite having children that make it worth mining.

petertodd commented at 10:25 PM on September 24, 2013: contributor

@luke-jr You know, given you already do this for MtGox it'd be really useful if Eligius had a program that used the inputs.io API to accept off-chain payments to artificially add priority to a given txid. At the simplest you'd just have to publish an inputs.io account name ("prioritize_tx@eligius.st") and tell people to put the txid in the "notes" field; pass whatever amount they pay as the argument to prioritizetx. The hardest part would probably be that people would want you to implement logic to give people their money back if you don't have the tx and/or it gets mined by another pool.

mikehearn commented at 8:42 AM on October 4, 2013: contributor

Mempool-less (i.e. SPV/ultralite) clients aren't going to create transactions that routinely take hours or days to confirm, that's not what users want. I don't know who or what is using the free area right now, but I guess it's not smartphone clients.

gavinandresen commented at 5:32 AM on October 9, 2013: contributor

Anybody have a good theory for why the win32 pull-tester build is breaking:

In file included from /usr/lib/gcc/i586-mingw32msvc/4.2.1-sjlj/../../../../i586-mingw32msvc/include/windows.h:50,
                 from allocators.h:23,
                 from serialize.h:22,
                 from core.h:9,
                 from main.h:12,
                 from txmempool.cpp:11:
/usr/lib/gcc/i586-mingw32msvc/4.2.1-sjlj/../../../../i586-mingw32msvc/include/winbase.h:1142: error: â€˜PVECTORED_EXCEPTION_HANDLERâ€™ has not been declared

My sleuthing:

allocators.h include windows.h. windows.h includes windef.h (unles RC_INVOKERC is set) windef.h include winnt.h ... and PVECTORED_EXCEPTION_HANLDER is typedef'ed in winnt.h, so I have no idea what is wrong...

wtogami commented at 5:53 AM on October 9, 2013: contributor

Perhaps look into conditional situations from other preprocessor variables that cause PVECTORED_EXCEPTION_HANDLER to be defined or not.

i586-mingw32msvc-g++ -E -dM $(mktemp --suffix=.h)

You can read the actual preprocessor defines from here. Add more compile flags to match the exact build environment.

wtogami commented at 5:55 AM on October 9, 2013: contributor

I believe the concerns above pertaining to the real potential for stuck transactions from fee misestimation have not been adequately addressed.

gavinandresen commented at 6:44 AM on October 9, 2013: contributor

@wtogami: RE: stuck transactions:

Ok, let me see if I can address those concerns.

Before this pull request, clients assume that if a transaction has a fee greater than 0.0001 XBT or a priority greater than 54million then it will be confirmed.

So, before this pull request, if transaction volumes goes up, those assumptions break, and people will see transactions never confirm.

I believe all of the concerns discussed in this pull request fall into the "perfect is the enemy of the good" category, and that is why I claim that this pull request, while not perfect, is much better than the code that exists in the tree today. As block space becomes scarce, the code in this pull request will give a BETTER estimate than the hard-coded rules we have now.

Anybody who commented above: please let me know if I missed some subtle interaction that makes you think that this pull request will be worse than the code in the tree before this pull request.

Remove include of windows.h from allocators.h

Create an allocators.cpp, and move all of the #ifdef WIN32
code and the #include of windows.h into it.

Two motives for this cleanup:
1. I'm getting a weird error in windows.h in my smartfee branch.
2. allocators.h is included (indirectly) just about everywhere, so
this should speed up Windows compiles quite a lot.

d8315d1650

Send multiple inv messages if mempool.size > MAX_INV_SZ

Changes the response to the 'mempool' command so that if
the memory pool has more than MAX_INV_SZ transactions (50,000)
it will respond with multiple 'inv' messages.

862399bd33

Refactor: CTxMempool class to its own txmempool.{cpp,h} 0a13d82306

Mempool refactors/cleanups

Remove mempool locktime support for obsolete 0.1.5 clients

Refactor: CTxMemPool::lookup

lookup now returns a boolean and, if lookup is successful,
a CTransaction. Cuts down on number of lines of code and
potential for error.

It also acquires the CriticalSection itself; I'm working towards
making CTxMemPool better encapsulated.

Refactor: CTxMemPool.fSanityCheck

Encapsulate the sanity-check flag.

6c4129305b

Refactor: move GetValueIn(tx) to tx.GetValueIn()

GetValueIn makes more sense as a CTransaction member.

ba52fb9593

Add verbose flag to getrawmempool 2f7b121032

estimatefees JSON-RPC method

Watches memory pool transactions to estimate miner's selection
policy, and, therefore, fee/priority needed to get into a block.

e1bcce50dd

Save/restore mempool 74471385ed

New relay policy

Use estimated miner policy to accept all high fee or priority transactions,
but start dropping low fee/priority transactions (and drop almost all
very-low-fee, very-low-priority transactions).

c26fd4a7a1

Refactor AllowFree(dPriority) --> CTransaction::dMinFreePriority

Also moved CTransaction static vars from main.cpp to core.cpp
And added new knob for miners: -minfreepriority to override
default COIN*144/250.

4ad2698305

remove GetMinFee, replace with mempool.estimate b6c79c3500

Un-harcode the "is dust" test, use mempool estimate of min fee cd89e8d800

Remove CTransaction::nMinRelayTxFee a5dc7246a1

Update release notes with fee changes d3f8fef572

wtogami commented at 7:19 AM on October 9, 2013: contributor

i586-mingw32msvc? Should pulltester be using that when the official win32 gitian binary will be built by 12.04's i686-w64-mingw32 instead?

in src/core.cpp:None in d3f8fef572

 114 | @@ -107,6 +115,23 @@ bool CTransaction::IsNewerThan(const CTransaction& old) const
 115 |      return fNewer;
 116 |  }
 117 |  
 118 | +/** Amount of bitcoins spent by the transaction.
 119 | +    @return sum of all outputs (note: does not include fees)
 120 | + */
 121 | +int64 CTransaction::GetValueOut() const

petertodd commented at 9:59 AM on October 9, 2013:

Suggestion: call this GetSumValueOut()

Diapolo commented at 10:31 AM on October 9, 2013: none

@wtogami I agree and I'm sure Gavin and Matt are working on upgrading the @BitcoinPullTester build environment. It should match the one in our release process as close as possible IMHO.

in src/core.h:None in d3f8fef572

  10 | @@ -11,6 +11,10 @@
  11 |  
  12 |  #include <stdio.h>
  13 |  
  14 | +/** No amount larger than this (in satoshi) is valid */
  15 | +static const int64 MAX_MONEY = 21000000 * COIN;
  16 | +inline bool MoneyRange(int64 nValue) { return (nValue >= 0 && nValue <= MAX_MONEY); }

Diapolo commented at 10:33 AM on October 9, 2013:

Aren't similar functions in util.h or at least used there by our helper functions?

in src/test/miner_tests.cpp:None in d3f8fef572

  96 | @@ -97,7 +97,7 @@ struct {
  97 |      {
  98 |          tx.vout[0].nValue -= 1000000;
  99 |          hash = tx.GetHash();
 100 | -        mempool.addUnchecked(hash, tx);
 101 | +        mempool.addUnchecked(hash, CTxMemPoolEntry(tx, 11, 111.0, 11));

Diapolo commented at 10:39 AM on October 9, 2013:

Any comment about these values anywhere?

petertodd commented at 10:48 AM on October 9, 2013: contributor

@gavinandresen My point was the mining code still has fixed CTransaction::nMinTxFee and CTransaction::dMinFreePriority logic; the fee estimator will happily estimate fees that are less than those minimums and transactions will get stuck in that case. If you make the fee estimation have a fixed lower bound then you'd have a system that's strictly better than the current one.

Anyway right now there is the opposite problem: I've been testing the code on one of my nodes and right now estimatefees calculates the 1% cut-off used for relaying to be 0.23mBTC/KB, lower than the 0.1mBTC/KB hardcoded default. At initial startup after upgrading or if the mempool data is wiped for any reason estimateFees falls back to the hardcoded values until the estimates get enough data, which would mean that transactions created by the user in that time-frame would have fees so low they wouldn't even get into the mempool and thus would get stuck.

Anyway without the ability to actually change the fee on a transaction after the fact we're always going to run into cases like that - what's your plan to fix this?

gavinandresen commented at 1:01 PM on October 9, 2013: contributor

@petertodd: RE: fixed lower: that would ruin the entire point, which is to let fees float up or down based on miner behavior.

RE: "we have the opposite problem now" : EXACTLY MY POINT. The hard-coded fees are not high enough to guarantee speedy transaction confirmation.

RE: what to do if a transaction doesn't get relayed/mined: I like Mike's idea of a "txrejected" message from your peers if they reject your transaction, that is then plumbed up to Do The Right Thing. The Right Thing is complicated, though-- for example, if the wallet is locked then the wallet code can't just create a higher-fee version of the transaction and try again. What do you suggest?

petertodd commented at 1:29 PM on October 9, 2013: contributor

@gavinandresen Both cases where I show estimatefees being fooled into a too low fee are things that can happen without actual transaction volume pressure, and result in worse outcomes than the current code; add a fixed minimum and estimate fees will never make a worse decision than the current code. Once that's done we can consider merging.

Long term as I said before we need to have the ability to increase the fees on a transaction after the fact - replace-by-fee does that efficiently, and replace-by-fee+txouts are a strict superset maintains the current zero-conf behavior.

Sure, the right thing is a bit complicated, but start moving in that direction now - replacement will break all kinds of really badly written merchant code, but the longer we wait the more of that code will get written. (e.g. BIP70 doesn't make it clear as I suggested before that a payment should be considered valid if a given scriptPubKey:value pair exists, so people will write code that assumes a given txid)

re: txrejected, thoughts on tx propagation proofs? http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg02868.html

petertodd commented at 4:44 AM on October 10, 2013: contributor

Also, this patch is broken right now on my system and always creates transactions with no fee at all, even on low priority coins, and even when the paytxfee option is set. (estimatefees returns fee value estimates, so I don't think it's a startup issue)

mikehearn commented at 8:42 AM on October 10, 2013: contributor

I think it might be time to introduce a more general error message construct into the protocol. TX rejection is just one way that nodes can choose to drop or reject messages. There's also block rejection, command rejection, etc.

Although it's a little bit more work (sorry Gavin!) it's probably not a big piece of code to spec and write. Just a new "error" message with some appropriate fields to help the receiving node categorise. Perhaps if we're feeling adventurous a protocol version bump so messages can have sequence numbers and errors can be linked back to the message that caused them.

BitcoinPullTester commented at 6:01 AM on October 11, 2013: none

Automatic sanity-testing: FAILED BUILD/TEST, see http://jenkins.bluematt.me/pull-tester/d3f8fef5726f8588c118b7562004c93f021a2e5e for binaries and test log.

This could happen for one of several reasons:

It chanages paths in makefile.linux-mingw or otherwise changes build scripts in a way that made them incompatible with the automated testing scripts (please tweak those patches in qa/pull-tester)
It adds/modifies tests which test network rules (thanks for doing that), which conflicts with a patch applied at test time
It does not build on either Linux i386 or Win32 (via MinGW cross compile)
The test suite fails on either Linux i386 or Win32
The block test-cases failed (lookup the first bNN identifier which failed in https://github.com/TheBlueMatt/test-scripts/blob/master/FullBlockTestGenerator.java)

If you believe this to be in error, please ping BlueMatt on freenode or TheBlueMatt here.

This test script verifies pulls every time they are updated. It, however, dies sometimes and fails to test properly. If you are waiting on a test, please check timestamps to verify that the test.log is moving at http://jenkins.bluematt.me/pull-tester/current/ Contact BlueMatt on freenode if something looks broken.

gavinandresen commented at 9:32 PM on October 11, 2013: contributor

I'm going to close this as "not ready for merge."

My TODO before bringing it back:

Test plan
Figure out some way to unit test CreateTransaction and the should-a-transaction-have-a-fee logic.
"error" protocol message

gavinandresen closed this on Oct 11, 2013

Bushstar referenced this in commit d57cbc615b on Apr 8, 2020

Bushstar referenced this in commit ea8569e97b on Apr 8, 2020

DrahtBot locked this on Sep 8, 2021