I'm glad my little talk is prompting people to talk about sybil attacks, but this conversation is confusing because you're all mixing up the two different types of attack I discussed (with two different types of solution)

1) MITM on bad wifi connections. Proof of propagation/connecting directly to miners/etc is in the same general area as connecting to randomly chosen peers through a trusted proxy. Most users don't have trusted proxies, but we can pick some Tor exits at random and correlate their answers to approximate this, which is what I proposed in the talk (and actually we're working on this for bitcoinj already).

Don't get me wrong - I like proof of propagation, if the bandwidth and latency requirements work out (I'd like to see some more detailed maths checking this). But it's not a whole lot different for solving case 1 than just using Tor.

2) Flooding networks with peers that look unrelated but actually aren't. Tor has the same problem, so I'm interested in solutions that generalise to all P2P networks. For these proofs of propagation etc are irrelevant. For Bitcoin it might be possible in every case to come up with fancy tricks based on proof of work, though remember someone has to actually write the code for all of these ideas! But I don't see how to avoid the issue with Tor. There just isn't any reasonable way that the Tor directory operators can know if nodes are related today, and if they are, Tor fundamentally breaks. Given that GCHQ has been tasked with breaking Tor (they're thinking of the children you see), advanced sybil attacks on it seem more likely than not in the near future.

Anyway, like I said, I love all the ideas flying about. But ... I'd appreciate it if in future people don't take material that was written to be interesting for a short presentation and make stupid assumptions, like if I talk about one or two solutions that must automatically mean I didn't think about any other solutions, or am a "lazy thinker". It was a 15 minute meetup talk, not a university lecture series.