Can we make Sybil attacks virtually impossible? I suspect that we CAN make them virtually impossible, but that we have not yet done so.  We operate on the assumption that computing a private key from the public key is virtually impossible.  We also operate on the assumption that computing a pre-image from a SHA256 hash is virtually impossible.  We are comfortable with these assumptions because we have theoretical responses to handle their failure.  We are prepared, but we are doing nothing to implement the changes required to handle failures of these assumptions.

We are, however, doing a lot of work to avoid the problems that a Sybil attack can cause.  It would be nice if we established some prophylactics so that effort can be directed more toward improving bitcoin than toward handling Sybil attacks gracefully.

Specifically, we trust "the network" as represented by eight (or more, if you enable upnp) "random" peers that are part of it, but that trust only goes so far.  We still (by default) validate every transaction in every block.  We still haven't figured out how to compensate non-mining nodes for providing a route between whatever miner solves the next block and a peer who needs such a route.  And we resist sharding the blockchain because we don't want to have to trust strangers.

It seems to me that the difficulty of progress in those areas would be significantly reduced if A)the software made Sybil attacks virtually impossible, and B)the virtual impossibility was well established through the natural and existing bitcoin education channels.

Some methods I've been pondering are:


How many valid blocks would indicate that you are connected to the entire network?
Has the difficulty been relatively stable?
Cycle the set of peers you're using.
Make it easy for a node operator to provide IRL contact info, as that would make a node far more trustworthy.
Validate peers by requesting known information, like the firstbits of the first transaction hash in the blocktip, or of a transaction that should be in the mempool.  The bitcoin software would include instructions to get this, including a warning that a Sybil attack can include spoofing popular bitcoin data websites like blockchain.info.
Proof of work is what makes Sybil attacks very difficult. Put simply, you trust the chain with the most proof-of-work on it. This cannot easily be faked (at least without significant mining power). It is possible that all the peers you happen to connect to give you false information, but at any time, if you have even one peer that tells the truth, this can be determined cheaply and easily by seeing that the chain has more proof-of-work than the others.

Flooding the bitcoin network with nodes that don't tell the truth is possible, but as long as there are some nodes that tell the truth, it's easy enough to know which ones are telling the truth and therefore easy enough to thwart such Sybil attacks.