Ooh, that sounds like a pretty slick improvement!

@gavinandresen can you have a look here?

@laanwj : yes, I'll review, but that might not happen until next week (I'm headed to Dublin tomorrow).

Thanks. I really like the new GUI in #5200. I think we should also change txconfirmtarget to default to 2 or higher for non QT usage. 1 is just dangerous given the fact that it's often impossible to be reliably confirmed in 1 transaction. Separately, #4082 is a somewhat substantial problem though. Is anyone working on the fixes @gavinandresen and @gmaxwell suggested? I just want to be sure we tie all these changes together to work well.

@morcos best to ask @cozz there I think

Code review mostly ACK, apart from a couple of nits.

I'll try to get a node up and running, generating estimates over time, to see how this behaves compared to the existing estimation code.

OK, I moved the dependency checking logic to main.cpp. It was a pretty clean change I think, and is more efficient because it saves us looping through all the inputs again. If that code ever gets moved out of main, I think it makes sense for those two checks on inputs to stay together. However if you don't like that, I can revert back to putting the logic inside CTxMemPoolEntry and I'll just call the constructor with a reference to the mempool itself. In both cases it now checks to be sure inputs aren't in the mempool as you suggest, as opposed to checking that they are in the chain as in my original version. I renamed the variable and also fixed the portability issue I think.

Node running this code and generating graphs at: http://core2.bitcoincore.org/smartfee/

(current HEAD code is running at http://bitcoincore.org/smartfee/ )

@gavinandresen How come the fee for 3 confirmation txs has stayed constant over the entire period. That can't be right, can it?

@rebroad The reason that happens is there aren't enough data points for transactions with lower fee rates. As people start placing transactions with lower fees, there will be more data points in the lower fee rate ranges and the estimate will get lower. I believe it makes sense for all of the 3+ confirmation estimates to be the same, because basically any fee will be confirmed within 3 confirms right now, so its just a matter of how low an estimate can you accurately give.

This doesn't seem to work well with #5200 currently. Even after leaving the node running for a while, the fee estimation doesn't kick in for anything other than 2 confirms. So sliding the slider to 20 gives the same fee as sliding it to 2, and then sliding it to 1 makes it say it needs longer to calculate (which then never happens).

I'm curious what fee its returning for you and how long it's been running. You can see by Gavin's charts linked above what the estimates are over time. But I do agree that if/when this is going to be merged, the GUI could be slightly modified to better handle the case where 1 doesn't give an estimate. It's not always a matter of not having enough data, but sometimes there really is no answer to the question, because there is no fee that is high enough that you'll reliably (> 85%) get confirmed within 1 block. In any case, I was operating under the assumption that this wasn't making it in for 0.10, so I was planning on waiting for that and then rebasing. I also have a couple small improvements to make.

OK I rebased off 0.10 (so the first 3 commits should still be what you reviewed Gavin). But then the 4th commit is new. It's addressing your comments above in a better way than I had previously done.

@gavinandresen, I've rebased this and added a couple of improvements, most notably, doing some tracking of transactions that are in the mempool and haven't been mined yet. So in particular the are code changes from what you reviewed before.

My compiler is unhappy.
Compiler:

Apple LLVM version 6.0 (clang-600.0.57) (based on LLVM 3.5svn)

Unhappiness:

./streams.h:406:9: error: call to 'Serialize' is ambiguous
        ::Serialize(*this, obj, nType, nVersion);
        ^~~~~~~~~~~
policyestimator.cpp:175:13: note: in instantiation of function template specialization 'CAutoFile::operator<<<unsigned long>' requested here
    fileout << confAvg.size();
            ^

... and:

./serialize.h:555:6: error: member reference base type 'unsigned long' is not a structure or union
    a.Unserialize(is, (int)nType, nVersion);
    ~^~~~~~~~~~~~
./streams.h:416:11: note: in instantiation of function template specialization 'Unserialize<CAutoFile, unsigned long>' requested here
        ::Unserialize(*this, obj, nType, nVersion);
          ^
policyestimator.cpp:197:12: note: in instantiation of function template specialization 'CAutoFile::operator>><unsigned long>' requested here
    filein >> maxConfirms;
           ^

Since the format of fee_estimates.dat will change, CTxMemPool::WriteFeeEstimates should change:

fileout << 99900; // version required to read: 0.9.99 or later
 .... should be
fileout << 109900; // version required to read: 0.10.99 or later

ah sorry, pushed too fast, i'd noticed that compilation problem, not sure why it was a problem, but i think i just pushed a fix... will wait for more comments before adding more fixes.

Been running this at home for a couple of days, estimates look reasonable.

I've updated the bitcoind on core2.bitcoincore.org; as soon as it catches up with the chain it will start generating new fee/priority estimate charts again.

Any thoughts on whether this is something we'd like to merge? I'd like to get it in early enough in the 0.11 release cycle that it gets some usage. I realize its a lot of complicated code, but it really only affects fee and priority estimates. I think the increased accuracy of the estimates makes it worthwhile. Compare (core2.) and bitcoincore.org/smartfee/fee_graph.html.

I'd like to see this in the 0.11 release.

Could you rename src/policyestimator.o to src/policy/estimator.o ?
I was planning on doing such a code movement and this seems like a perfect opportunity.
A later step would be to take the policy estimator out of the txmempool object, but this movement already helps with that independently of what you're doing inside the the estimator itself which I haven't reviewed.
This is what I had in mind after the movement: jtimon@ba88aa1

It will obviously have to change after this PR, but maybe you can get some ideas from there as well, and hopefully make the "rebase/rewrite" of that encapsulation easier. If you manage to incorporate the essence of that commit in your PR, I would love you for it, but that's probably too much to ask at this point.
In any case, I would already be happy with the file rename.

I'd be happy to give it shot. I'll ping you when I get around to it.

Rebased, cleaned up and squashed original commits.

Added 3 new commits.
This is ready for more review.
@jtimon I made the move you asked for but held off for now on the other changes until I know what the right way to couple the mempool to the estimator is. There are now 3 interface points instead of the previous 1 that the old code had.

Thanks for incorporating some of my suggestions, I'm specially happy about not using the minRelayTxFee global inside the estimator which was the most important nit. I agree all the suggestions not incorporated can wait and it's better not to slow this down.

Addressed nits (above and offline) by @sdaftuar and improved the readability of the rpc test.
@gavinandresen, I know there are a lot of small added commits here, and I'd like to squash them all down but just wanted to be sure you saw the changes in 64bf2bb. This slightly changes the startup behavior, but otherwise all other changes we just cleanups, and no change to behavior.

I've reviewed the code (particularly to understand the details of the calculations in policy/fees.cpp), and I've tested by running a node with this code, and this looks good to me (and improves the estimates substantially). ACK.

I'm going to make a summary of my review of this PR, hopefully it helps getting it merged soon.
Although, I have not reviewed or tested the changes in the estimator itself, I have paid special attention on making sure that it only changed fee policy behavior, so I'm convinced that this is completely consensus and network safe, anything-non-fee-estimator-related safe.
Reaching this conclusion was not hard because although coupled with txmempool, the estimator is encapsulated.
Apart from the changes in the estimator, this is an improvement in modularity, and will open the door to further improvements in fee policy encapsulation (the min relay fee should stop being a global, all functions using it should be methods of the estimator class, but one step at a time).
I repeated the moveonly part of this PR manually so if it had been separated in an individual commit I could have easily verified it, but then I git pruned that (I should have kept it).

In summary, still-untested-but-pretty-confident-ACK.

I didn't try to check or understand that code, but wanted to ask if the GUI (e.g. coincontrol and smart fees) is working with this without problems or if that needs to be verified.

@Diapolo Thanks for thinking about that. I think it could certainly use some more testing. There are two things in my mind that could use improving.

1. I think the default txConfirmTarget should be greater than 1. There are periods of time when 1 can be quite a high fee temporarily. I plan to open this discussion in a different PR at some point, because its a bit of a separate discussion. This doesn't really affect the GUI, though since that uses a default of 25.
2. It's also possible at times to not have an answer for estimatefee 1 but to have answer for all other estimates. This is a feature not a bug, but I think it would be possible to design a better UI experience in that case. Perhaps the slider bounces back to the first legitimate estimate, or gives you a helpful message such as "No amount of fee will get you reliably confirmed in the next block".

There are periods of time when 1 can be quite a high fee temporarily

A suggestion: if fractional arguments are allowed for estimatefee, it could avoid the need for MIN_SUCCESS_PCT, which in my view discards useful information, and perhaps is the reason for these kinds of problems (e.g. a fee bucket which for a given confTarget has a curPct that is close to the 0.85 threshold would result in unstable behavior, if I've understood properly).

With fractional confTarget, each fee bucket could be represented by its mean conf, and compared to confTarget directly to determine success. The default txConfirmTarget could then be set to fractional values, e.g. 1.2, which would perhaps result in greater stability.

not have an answer for estimatefee 1

With regard to fee buckets clearing the MIN_SUCCESS_PCT hurdle of 0.85, I've found in my own studies that the main reason why transactions with relatively high fees don't make it into the next block is because of the interval between miners updating their block transaction lists, which I believe is on the order of 30-60 seconds (source).

This means that if a transaction has been in the mempool for less than 60 seconds, there is a chance it won't be considered for block inclusion at all by the miner, regardless of the tx fee. After removing these transactions from the estimation, I've found that the relative frequency of high-fee transactions being included in the next block is pretty high and consistent, typically > 95%.

@bitcoinfees, thanks for the comments. I think asking for the mean number of blocks to confirmation is a slightly different question than I answered. It's not clear if one question is better than another, but the way I defined the question is what fee would you need to have a sufficiently high percentage chance of getting confirmed in the desired number of blocks, so it kind of requires a MIN_SUCCESS_PCT. But to your point, I do think that there could be a lot of improvements to this estimation algorithm, and hopefully they could build off the framework it provides.

I agree with your conclusion on why the success percentage has a ceiling around 90%. Hopefully with an improved transaction selection algorithm for mining in the future that will get better.

Code review and lightly tested ACK.

I'm updating core2.bitcoincore.org to run this version of the code now.

squashed to hopefully make it mergeable

nits addressed

utACK