What is the best way to prevent replay attacks in the event of a bitcoin hard fork? I originally thought it would be relatively simple to add replay attack protection (change something about how the tx hash is generated) in the event of a fork. But the BU folks mentioned that this would break SPV clients (including many mobile wallets). So it is not free to do that way, although still an option.

One solution we brainstormed, was using some coins that were only valid on one chain (for example newly mined coins) and adding 1 satoshi of "taint" to all generated transactions. This would work but is not perfect. For instance, newly mined coins can't be spent for 100 blocks, so at a minimum it would cause economic nodes to have a delay in the event of a hard fork. It is also non-trivial for all wallet software to implement this (fair amount of work, especially at scale). There is also an operational challenge that you would have to rush to get these newly mined coins while the hard fork was happening, so you could not prepare in advance. It would be a messy for sure.

Another option would be to try and double spend some coins across the forked chains (get a transaction with some coins going to two different addresses mined across the two chains). These coins could then also be used for "taint", but you wouldn't have to wait the full 100 blocks. This is a little bit better, but still not perfect.

I suspect there is a better solution though. What are people's thoughts?
One solution we brainstormed, was using some coins that were only valid on one chain (for example newly mined coins) and adding 1 satoshi of "taint" to all generated transactions. This would work but is not perfect.


It so sounds like you have two problems:


How to get some inputs that are only valid on one side of the chain.
How to mix these inputs in with all of your transactions.


I don't have any good answers for the second question; you'll have to mix in the inputs by either putting them in every transaction you send or by mixing them with a large amount of coins which you then split into dozens or hundreds of inputs that you'll use normally.

For the first question:

Coin splitting

The best way would be to push for replay protection in the hard forking client(s) as they're already changing the rules.  But if that's not possible, there are some potential differences between chains that can be used to get one version of a transaction confirmed on one chain and another version of the same transaction confirmed on the other chain.

I'll warn that (1) Bitcoin clients are not designed to operate under ongoing hard forks, so lots of things that would normally work just fine can end up resulting in monetary loss, (2) without replay attack protection, there's no guarantee that any of the mechanisms below will split your coins---so you should probably send the coins from yourself to yourself so that, if the split fails, you still have all your coins (minus any transaction fees), and (3) in a hard fork, any rule can be changed, so the following generic information may not apply on the hard-forked chain; check with the hard fork developers to be sure.

Methods:


Coinbase transactions: not the kind your company makes, but the kind miners use to claim subsidy and transaction fees.  As your question indicates, these are only valid on the side of the hard fork they're generated on but they also have to wait 100 blocks to mature.

Pros: simple, guaranteed to work

Cons: requires miner help, have to wait 100 blocks
nLockTime: if the two chains diverge in height, you can create a transaction with the nLockTime set to the height of longest chain.  That transaction can be immediately confirmed on that chain, but it can't be added to the shorter chain until that chain catches up to the same height---giving you a window of time into which to broadcast an alternative transaction on the shorter chain and split your coins.

Handily, Bitcoin Core has a feature called anti-fee sniping that automatically (in current versions) sets the nLockTime to the current block height for default wallet transactions, so this trick is pretty easy if you just want to split your Bitcoin Core wallet.

Pros: should be pretty effective because it depends on consensus rules

Cons: you still need to wait a few blocks after the fork to give the chains time to diverge in chain height.

(Credit: I first heard of a method like this from Peter Todd; I don't know if he originated it, nor if this is exactly the method he was thinking about---I had to guess at how it would work from him just saying "use nLockTime".)

You can also do the same thing with consensus-enforced nSequence, but it doesn't get you anything extra.
Fee differences: It's possible miners on one side of the fork may be mining transactions with lower fees than on the other side, so you can broadcast a low-fee version of your transaction on the low-fee chain, wait for it to confirm, and then broadcast a higher-fee version on the high-fee chain.

Pros: simple

Cons: you may still have to wait a few blocks for fees to diverge by much and since each miner has their own policy, you may need to try multiple times.  Also, many wallets don't let you chose arbitrary fees (they just give you a reasonable fee or let you choose from reasonable range of fees).

(Credit: I first heard this described today by @ElectrumWallet on Twitter.)
Find some other feature that diverges between miners on the two chains.  For example, as I write this, I think Bitcoin Core by default will not accept into its memory pool any transactions that require mining more than 20 ancestors first (this prevents abuse and allows the mining code to run more efficiently, since Bitcoin Core provides child-pays-for-parent (CPFP) mining); Bitcoin Unlimited, being based on an older version of Bitcoin Core, doesn't provide the CPFP optimization and so will allow an unlimited depth of transaction ancestors to enter the mempool.  This means you could get, say, 101 related transactions mined on one side of the fork and then you'd have up to five block to get a different 101st transaction mined on the other side of the fork.  

There are potentially other of these relay-level differences between clients that could be used.

Pros: relay differences could possibly be used immediately after a hard fork to get a transaction mined in the first fork block (if you knew when that was going to happen) or the second fork block (if you started as soon as the first fork block was produced).  Also, they may be fairly simple.

Cons: these tricks depend on all miners on one side of the chain running one version of the code and all miners on the other side running a different version of the code.  The more overlap there is, the lower the probability these tricks will work.