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.
It's easy to know if some Tor nodes are related and who runs them: there's a large number of high-bandwidth donation-based nodes run by various charitable organizations, e.g. torservers.net, and those nodes are well known. Tor
does not fundamentally break by having who runs what nodes be publicly known - that's exactly how Tor already works.
The other interesting thing is that because tor is a semi-centralized system proof-of-bandwidth and proof-of-low-latency is practical - the central organization is trusted and can make the measurements - and that makes for a good lower-bounds on the financial resources expended to run those Tor nodes and the geographical decentralization of them. Basically it's a better version of proof-of-sacrifice, better because the "sacrifice" is inherently the thing you're suppose to be providing.
You're criticisms do apply to the I2P network though, a common criticism of it verses Tor.
Meanwhile if the GCHQ is your adversary, why are you making their job
easier by giving them a huge advantage - they have access to tens of thousands of real and faked passports - that the honest defenders don't have?