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.