How do nodes bootstrap if some of the nodes are evil?
It's actually not that difficult to obtain a very large number of IP addresses. There are botnets that have hundreds of thousands of nodes.
Imagine that each bot in that botnet joined your network, and pretended to be a normal node. Then, the botnet controller makes those nodes claim that some transaction never happened. (Or, that some other transaction happened instead.) If a new node arrives to the network, who are they going to believe: the 99% who claim that the transaction never happened, or the 1% who do?
This is a deceptively simple sounding problem, and it's very easy to come up with proposals that sound good, but don't work.
What if two conflicting transactions show up at the same time?
Second, even supposing that the entire system came to consensus at the speed of light, I (an attacker) can still get two systems to disagree. I rent two servers in different parts of the world, and I get them both to broadcast different, conflicting transactions to local nodes. Because of the distance, it's guaranteed that even honest nodes will disagree about which transaction came first.
Because there's no way to stop peers from occasionally disagreeing, you need a way to resolve those disagreements. In Bitcoin, this is pretty simple. Each Bitcoin node has its own memory pool, some of which conflict. Each node tries to create a block. Eventually, one of them will win.
You're probably wondering, "Why not just ask your peers which transaction came first, and change your vote if a majority of them disagree?"
The problem with querying your peers: Cliques
Imagine a network structured like this:
The blue nodes believe that transaction A came first. The orange nodes believe that transaction B came first. The lines represent connections between peers.
From the perspective of each individual node, a majority of their peers agree with their vote, and so the two blocs will never come to agreement. In the worst case, the transaction will be in limbo forever.
This problem is solvable, but all of the solutions (including Bitcoin's solution) have nontrivial downsides.
