Refactor CreateNewBlock transaction selection algorithm #1240

• Transaction fees for children might help the parent transaction get confirmed
• Transaction fees can boost the priority of transactions included

So far, I have done some minimal testing by analyzing the output of getmemorypool.

Eligius has found 2 valid blocks (and none invalid) with this code (plus #1246, for safety) so far, at its default settings. I am now testing with a huge weigh toward transaction fees, to increase the likelihood of dependent transactions paying for their parents (and therefore risking any potential child-before-parent problems).

Things I need to address:

1. False "may be used uninitialized" warnings
2. Config option names differ between actual code and -help
3. Second-pass priorities should be printed with -printpriority
4. Fee influence should be multiplied by total input value (input please: is this a good idea? should the total input be reduced by the fee amount first?)
5. -printpriority shouldn't require fDebug (is this ok?)

FWIW, 10 total valid blocks found with this (most recent is …30E6C09A4FF45348A0EF0AA1A), zero issues caught by #1246, and zero invalid blocks logged by bitcoind.

Integrated my 5 "things to address".

Eligius has been running this from block 179513 (56 blocks found) and EclipseMC from 180573 (11 blocks), totalling 67 valid blocks with no problems found.

(EMC: 180788(1040); Eligius: …9DA7D49DC2539F9D299AF8E5A)

Also passes the unit tests I just wrote on #1246.

This seems to be be excessively slow, and possibly exploitable right now.

Define "this" ?

This pull request. Eligius is getting stuck in some huge dependency trees, it seems. Trying to figure it out, but don't have time just this second.

Fixed the major performance hit from complex dependency trees. Still not as fast as the old algorithm, but not absurdly slow either. I'd say the ability to pay for "parent" transactions is worth it.

(Fix verified by about 10 days of testing on Eligius)

I certainly agree to the idea of this patch. I haven't checked the source yet though.

Need to be very careful not to accidentally introduce a potential DoS attack by arranging transactions that require N^2 time or space to figure out fees/priority.

@gavinandresen I think SatoshiDice tested that for me (the fix from ~16 days ago)

Could you write up a gist that explains what formula for priority you're using? And maybe talk about how it will handle transactions from old clients (who calculate priority the old way) ?

• DepthWeight = user configurable (default: 1.0)
• FeeWeight = user configurable (default: 1.0)
• DepthScore = sum(sum(value * depth) for each input)
• FeeScore = sum(value for each input) * fee
• WeighedScore = (DepthScore * DepthWeight) + (FeeScore * FeeWeight)
• EffectiveSize = datasize + sum(datasize for each (transaction this depends on that is not yet in a block))
• Priority = WeighedScore / EffectiveSize

Old clients don't take priority into consideration at all right now AFAIK, nor does this code (or the code it's replacing) completely exclude transactions based on their priority.

NACK, the priority formula would make it easy for somebody with (say) 100,000 BTC to pay tiny fees and get priority over higher-fee-paying transactions. That's a bad incentive, it would encourage people to do dangerous things like keep more funds in their 'hot' wallet or add extra inputs to their transactions (and just have bigger change outputs) to get higher priority.

So, should I take the input value out of FeeScore?

Sadly, in addition to being NAK'd this conflicts heavily with @gavinandresen 's work redoing CreateNewBlock() You should work with @gavinandresen to coordinate changes in that area, before posting another pull request relating to CreateNewBlock() + TX selection/fees.