W.R.T. this paper and the oft-discussed miner backbone,
I'm wondering about an alternative protocol change that perhaps has less subtle implications than their suggested change. Rather than address the problem by assuming the network is full of sybil nodes and changing the rules for selecting the chain to build on, how about if we wrote code to automatically build a miner backbone by having IP addresses of nodes embedded into coinbases, then having any bitcoind that is creating work automatically connect to IPs that appeared in enough recent blocks?
This would have the effect of automatically linking all the major pools together, with no administration overhead.
For bonus points, the IPs could be IPv6 and then the trick we use to pack hidden services into IPv6 address space would allow nodes to be reached via Tor. This might be useful in the case of pools that don't to reveal the location of their bitcoin node[s], like for anti-DoS reasons.
It feels like this should be achievable with a few days of solid coding and a couple of new command line flags, and the impact is much easier to reason about than a fundamental rule change like the one proposed by the paper.