I would be wary of allowing fees to change the merit of the block because it's low-risk for a miner to publish a transaction with a large fee immediately before publishing a pre-mined block which has its merit artificially inflated because of the influence of the included transaction's fee. Let's not forget that the purpose of a fee is to pay a fair amount for the time taken to verify the transaction and the space it takes in the block-chain. There are a variety of distorting effects that transactions with large fees have so I suggest that a transaction's fee for the purpose of calculating transactionfee seconds be capped at a value which is no larger than the transaction with the largest fee that the client saw did not make it into the previous block.
That's a good suggestion, but still open to abuse. The selfish miner mines a normal block, then a block with a high fee tx. It releases the high fee tx before releasing either of the blocks. Now it looks like the tx did not make it into block 1, and block 2 gets full credit for the large fee-seconds count it displays. Of course this requires a minimum of two pre-mined blocks to work, so your countermeasure assures that the attacker has gamma=0 in the case where both the private and public chains are 1 block long, (which is the only case where gamma mattered in the SM attack as described), but at the cost of giving him gamma=1 for any block races where the split is more than 1 block back. It is trivial to adapt the SM attack to exploit this by not revealing the private chain when the lead gets reduced to 1, but rather only once the public chain catches up (since gamma=1 means everyone will prefer our fork), which allows us to build longer secret chains.
I am also concerned about the potential to exploit something like this by not working from the head (i.e. we give the public chain a 1 block headstart). Unless the block creator explicitly maximised his transaction-fee-seconds score at the cost of all other considerations, I can build a block with a higher txfee-seconds count and know that my block will win the block race.
I am sensitive to hannesnaude's concerns not to encourage block-bloating but hopefully the existing schemes to calculate transaction priority will cope with that. Am I right in thinking that clients are likely to fail to relay and otherwise drop transactions with very low priority?
Even if you fill up a 1MB block with 192 byte transactions, each carrying a 0.0001BTC fee, you only spend 0.546BTC in fees. A selfish miner will fill a block with all the public transactions it deems small enough and then fill all the remaining space with small secret transactions that carry fees (which he expects to get back). As soon as the block has been mined, he releases the secret transactions. Then no honest miner can exceed his transaction-seconds score, the best they can do is to match it, and unless they are using transaction-seconds as the only measure to optimise, they will probably end up with a lower transaction-seconds score.
Curious to hear your opinion on HanSolo's proposal.