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.
Hrm. The problem is that even if the network decided to ask for passport blind-signing, that solution doesn't work for this use case because the attacker can issue passports.
On the other hand, it's a thought. If you had to sign with an identity that was fundamentally difficult to create due to some
other consideration...