In case anyone has missed it, Eyal&Sirer have posted about an enhancement to my puzzle scheme that makes it possible to reuse existing Bitcoin miners. It's too bad I missed this! Compatibility with existing Bitcoin miners is a major win for the plausibility of implementing this as a practical fix.
http://hackingdistributed.com/2014/06/18/how-to-disincentivize-large-bitcoin-mining-pools/

The 2-Phase puzzle they propose is a "weakly nonoutsourceable" puzzle according to my definition. The main idea is that instead of *each* attempt requiring knowledge of a private key, only some constant fraction (1/Y) of attempts need to. First you, configure an existing Bitcoin miner to mine blocks at a very low difficulty (1/X chance of winning), where your coinbase contains a commitment to some public key. Every time your mining rig outputs a partial solution, you perform a second check, which essentially involves signing the solution with the corresponding private key.

In total, 1/(XY) attempts must be made to find a solution, so XY should be set equal to the current difficulty. The tradeoff between X and Y should be chosen so that Y is small enough that an ordinary GPU or CPU can "keep pace" with the partial solutions generated by a typical Bitcoin mining rig, but Y is large enough that it would be infeasible for a miner to *interact* with the pool operator without learning the private key on its own. This is actually the same sort of analysis we did in Permacoin.

This scheme is compatible with most of the work of my existing puzzle schemes:
1. A good candidate for the signature scheme is the Merkle tree-based signature scheme used in this paper and in Permacoin. ECDSA, however, is out. It's essential that the signature scheme is deterministic - there should be exactly one valid signature for a given message and keypair.
2. Since this is a "weakly nonoutsourceable" puzzle, it can be *upgraded* to a "strongly nonoutsourceable" puzzle using the generic scheme described in our paper.... basically you can take any weak-NO puzzle and make it strong-NO by adding a zkSNARK option.