Sybil-like attacks at the p2p level

[nkeywal]

tl;dr: Sybil attacks at the p2p layer are possible on ethv2/sharding. There are multiple ways to mitigate their effects. This post is just there to raise awareness on this subject as a part of the p2p discussions/choices.

On ethereum v1, it's not very interesting for an attacker to add a lot of nodes on the p2p network:

• supposing 20000 nodes, add 4000 Sybil nodes you control only 17% of the network
• there are not so many attacks possible, even if you control more nodes. And miners can spend a lot of time/money on their defense.

It's a little bit different with sharding:

• If we have 200 nodes + 300 validators per shard, with 4000 nodes you control ~90% of the p2p network on a chosen shard.
• slowing down the communications between the block producers and the attesters is enough to have an impact on the shard, preventing some of the block producers to receive transactions or to have their blocks accepted.

Some of the possible reasons for such attacks:

• a war a la bsv/bch with a party trying to sabotage the other (i.e. preventing it to create blocks)
• a byzantine block producer who wants to get more transactions for himself to get more fees

I ran a simulation (see here: https://github.com/ConsenSys/wittgenstein/blob/master/src/main/java/net/consensys/wittgenstein/protocol/P2PFlood.java) with 500 real nodes, 4000 byzantine nodes and 13 peers: on average the bloc producers will reach ~280 of the honest nodes out of the 500:

The easy workaround is to have more peers. With a minimum of 50 peers we reach nearly all honest nodes:

The impact on the timing is more complicated to estimate. If we consider (it's highly speculative) that we need 500ms to validate a block and we contact the peers one after another, with 300ms per peer we have the graph below. After 8 seconds you reach only 60 honest nodes out of 500. (this with 50 peers min. If you have only 13 peers per node you reach ~15 honest nodes in 8 seconds.)

On the workaround list:

• Another option for the block producer is to contact all nodes it can once it has generated the block (eg. there is no reason to contact only 13 peers: the block producer should send its block to as many nodes it can during slot_time /2).
• Having multiple block producers (a la dfinity) could also make this attack less interesting for an external attacker.
• Lastly, obviously this attack is easy to detect, so client-side configuration (like hardcoding some of peers known as honest) helps a lot (but it's less a trustless system in this case).

[jannikluhn]

Thank you for this great analysis!

An additional aspect to the workarounds you proposed that we should consider here is peer selection strategy. Today, nodes prefer peers with which they have been connected to for a long time. One could also send new messages to old peers first and only later to newer ones. Then an established network would not be attackable using only newly spun up nodes. Instead, one would have to wait some time for them to built up some reputation and get them higher up in the list, or get connections to nodes that join the network in this preparation phase. So such an attack would at least be a little more costly.

Also, one could try to increase the number of honest nodes per shard by "suggesting" nodes from one shard help out at other shards (this could just be the default, users could of course just turn it off). This would of course mean higher bandwidth (and in later phases maybe also computational) costs. But it would only be necessary in the beginning when the number of nodes is low, which conveniently is probably also a time at which network load is low (ideally the two quantities would be proportional to each other).

[nkeywal]

Instead, one would have to wait some time for them to built up some reputation and get them higher up in the list, or get connections to nodes that join the network in this preparation phase. So such an attack would at least be a little more costly.

I like this idea. It has an advantage as well: if you see thousands of nodes added to a shard all of a sudden, it gives you some time to react.
It would have to be implemented carefully however. For example and attacker could have very few nodes but highly connected to build its reputation before turning byzantine. It could also use a single computer with multiple public keys to build multiple reputation scores at the same time before starting the attack with multiple ip address.

I think that the best strategy for a validator, and especially for an attester, will be to connect to a lot of nodes as soon as possible (50 nodes or more given the numbers above). But it has two implications:

• without extra work, it will be very easy to do the mapping ip address <-> validator public key: validators will be sending their signed messages all over the place.
• either each node has a lot of connected peers (not great at all for scalability) either we can re-establish new connections quickly (i.e. QUIC).

Good reputation rules + connecting to a lot of peers may not solve the problem in theory (an attacker could still try to slow down the network to make it miss the slot time deadlines) but could be enough in practice (attack cost high enough for the little benefit).