Proposed attnets revamp

[djrtwo]

Attnets revamp

Since the launch of the beacon chain, the "backbone" of attestation subnets (attnets) relies upon staking nodes connecting to a random set of subnets. The size of this random set is dictated by the quantity of validators attached to the node, up to the maximum of 64 (ATTESTATION_SUBNET_COUNT which maps to the expected SHARD_COUNT). The general idea at genesis was that a node's validator requirments will scale linearly when sharding is released thus we can put this linear subnet requirement for subnet backbones as an "honesty" assumption until sharding comes around.

An attestation subnet backbone is required so that at each epoch, validators can quickly find and publish to their assigned subnet. If there was no notion of persistence in these subnets, then there would be no subnet to "find" in he ~6 minute window and those no clear place to publish individual attestations before they are aggregated.

Backbone requirements:

• Subnets are relatively stable, slot-to-slot and epoch-to-epoch, allowing for reliable dissemination of messages on demand
• Subnets entry points can be found in a relatively short time (< 1 minute) and short search overhead (within a few hops of the DHT)
• (Nice to have) A method to discern whether a node is "honestly" performing the expected backbone duty

Problems

There are a few issues with the current structure:

1. This likely creates overly populated subnets in actuality, thus increasing the network's total bandwidth consumption with little to no gain
2. This relies on an unenforcable "honesty" of validator nodes when the rational behavior is to turn your attnets down to 1 or even 0.
3. As non-staking (user nodes) come online more and more, such (0-attnet) nodes will crowd the DHT, making the task of finding peers of particular subnets increasingly difficult. In the event that user nodes outpace staking nodes by 10-to-1 (a situation that should be applauded!), finding attestation backbones would become 10x more difficult.

Proposed solution

In an effort to solve the above issues, we propose:

• Remove random subnets per validator
• Add a single deterministic subnet per node, as a function of by the node_id, epoch

Rather than putting the backbone requirement on a brittle validator-honesty assumption, this puts the backbone requirement on the entire network of full nodes such that, on average one out of every ATTESTATION_SUBNET_COUNT nodes will be of a particular subnet.

This means that the size of subnets becomes a function of the total number of nodes on the network, rather than on staking node count combined with validator-node density. This means that we simultaneously reduce the over population of attnets by a small number of staking nodes and ensure that even if the Ethereum network (and DHT) grows by orders of magnitude, attnets will be able to be found within a few hops.

Additionally, due to the requisite subnet subscription being a function of a node's peer-id, honest/dishonesty wrt attnet backbone can be deterministically assessed allowing for peer downscoring and disconnects of dishonest peers.

The downside to this approach is that it puts a minimum of one attnet of load on every node rather than just on staking nodes, but in estimation, this is not a very high burden wrt home node resources and provides much more benefit in meeting the backbone requirements than negative.

Concrete spec mods

Remove random subscriptions

• Remove RANDOM_SUBNETS_PER_VALIDATOR from validator guide
• Remove attnets from ENR and MetaData in p2p spec
• Remove functionality described in Phase 0 attestation subnet stability

Add node-id subscription

• create function compute_subnet_from_node_id(node_id) -> uint64 that takes in a node_id and returns a value on [0, ATTESTATION_SUBNET_COUNT). Consider an epoch param that causes these subscriptions to slowly rotate on the order of ~1 day
• Add "MAY downscore peers that do no actively subscribe/participate in their currently assigned subnet based on compute_subnet_from_node_id
• In Lookahead section, replace attnets dht search with compute_subnet_from_node_id dht search

Strategy

We'd likely want to simulate and test this change in strategy in a controlled environment before pushing this to testnets and then mainnet.

Such a controlled environmnt to test gossipsub at scale seems critical to a number of the network optimization investigations underway.

Protocol Lab's testground could be a good candidate. Alternatively, another simulation framework or even spinning up 1k+ distributed networks for ~1 day tests could also be a viable path.

EDITED TO USE node_id instead of peer_id per discussions below

[dapplion]

This solution is really neat, having an enforceable condition is a great improvement. However, must be noted that for small stakers with a single key this requirement doubles their attestation processing cost while for large stakers / pools it'll represent a tiny increase, going against

The general idea at genesis was that a node's validator requirments will scale linearly when sharding is released

Post sharding, single key stakers will be expected two fully validate two shards if their random subnet != current duty subnet?

[Nashatyrev]

Add a single random subnet per node, dictated by the peer-id

@djrtwo Should the 'random' word be removed here? As I understand subnet is defined by deterministic function of (peerId, epoch) ?

[Nashatyrev]

Good proposal from my perspective 👍

It also has an extra benefit: it would make validator nodes not so trivially discoverable (currently it is even easy to estimate the number of validators per node with discovery attSubnets and syncSubnets attributes)

However we need to consider a potential attack on a single attestation subnet. An attacker could craft specific nodeIds and spin up malicious nodes to eclipse a specific subnets for some specific range of epochs. An attack on a single subnet would require just 1/64 of malicious nodes than attacking the whole network.

It might make sense to think of mixing a randao to the compute_subnet function. That will significantly limit an attacker time to build it's 'subnetwork' of nodes in terms of discovery and gaining reputation. This would prevent from building malicious nodes for attack at some distant epoch. That's just a spontaneous idea.

[djrtwo]

Should the 'random' word be removed here? As I understand subnet is defined by deterministic function of (peerId, epoch) ?

yeah, I guess I mean that you get an effective pseudo-random distribution. Will update

[djrtwo]

it would make validator nodes not so trivially discoverable

right! an incredible amount of information is leaked today.

An attacker could craft specific nodeIds and spin up malicious nodes to eclipse a specific subnets for some specific range of epochs

I see. I suppose you can attempt to flood the neighbor DHTs with peer-ids of a particular type so that when a node searches for a subnet, they find these "fake" subnet peers.

I would argue that the damage of eclipsing a small set of nodes wrt an attsetation subnet is likely limited -- a few validators might no get their individual attestations included. A targeted DOS could do the same thing with likely even fewer resources.

Additionally, gossipsub's IWANT/IHAVE and other mechanisms are primarily for these types of cases. To aid dissemination of data even under various attacks to subnets.

An attack on a single subnet would require just 1/64 of malicious nodes than attacking the whole network

Right, but this is likely better in the long run over our status quo. In the event that you have a 10:1 (or even 100:1) user_node:staking_node ratio then attacking subnets as a function of total network nodes degrades more and more.

It might make sense to think of mixing a randao to the compute_subnet function

Ah, okay. So you can't pre-compute a node-id table that will be useful for all time. This seems reasonable if you had short subscription times, but I think you likely want subscription times on the order of at a bare minimum 1-hour (or at least multiple epochs) to reduce subnet backbone churn. Once you get to 1-hour or 1-day an attack would be able to easily "mine" node-ids with a given randao. I suppose it makes it harder to get your peers positioned in the DHT though

[Nashatyrev]

Right, but this is likely better in the long run over our status quo.

Yep, the present solution looks even more vulnerable to me.

Ah, okay. So you can't pre-compute a node-id table that will be useful for all time. This seems reasonable if you had short subscription times, but I think you likely want subscription times on the order of at a bare minimum 1-hour (or at least multiple epochs) to reduce subnet backbone churn. Once you get to 1-hour or 1-day an attack would be able to easily "mine" node-ids with a given randao. I suppose it makes it harder to get your peers positioned in the DHT though

Yes, that's totally not a silver bullet, but limits an attacker time to 1-hour/1-day.
Additionally nodes wishing to join a subnet could prioritize nodes which were seen in discovery longer than 1-hour/1-day since they are 100% could not be specially crafted for that kind of attack.

[Nashatyrev]

Additional argument pro this solution:

I'm now gathering mainnet network statistics and it looks like large validator nodes (with many att subnets subscriptions) tend to restrict inbound connections: i.e. they either immediately drop connection or keep you connected for just several seconds and then disconnect with TOO_MANY_PEERS. (I think I could get back soon with some specific statistics)

That behavior seems reasonable when you have much at stake since every inbound connection adds more risk to be attacked. So I believe this tendency could evolve further with time and it would be even harder to join a subnet

UPD: some connection statistics:

Number of nodes tried to connect (>= 20 connection attempts): 2769
Total connection attempts: 812291

Nodes with subnet count [1..31]:
    Connected at least once: 1818
    Never connected: 451
Nodes with subnet count [32..64]:
    Connected at least once: 330
    Never connected: 170

Probability of being connected to a node (connected here means "negotiate on Eth2 level and then being connected for at least 5 slots") with grouping to 'small' validator nodes (from 1 to 31 att subnets) and 'large' validator nodes (more than 31 att subnets):

So large validator nodes indeed harder to connect to, but the overall statistics doesn't look too dramatic

[djrtwo]

I would argue that due to our attestation subnet search requirements that all nodes should have both a MAX_PEERS and TARGET_PEERS value that by-default are different (MAX_PEERS > TARGET_PEERS). This would allow for new inbound connections to be made (up to MAX_PEERS) while the node then prunes down to TARGET_PEERS.

Otherwise, node connections can become far to rigid and peer discovery for particular purposes (e.g. finding a subnet) can become more prone to error.

Lighthouse uses this mechanism and has since genesis.

We might evn consider specifying this as honest behaviour (e.g. MAX_PEERS >= TARGET_PEERS + 5 for any value of TARGET_PEERS. It's unenforceable but a better default/honest behaviour, imo

[Nashatyrev]

That behavior seems reasonable

I was probably trying to say 'behavior rational from validator node's perspective' rather than 'reasonable from the network point of view'

I agree that dropping inbound connections is not a honest behavior, but if I was maintaining a node with a lot of validators and acting rationally I would stick to some kind of conservative peer management policy like peering with just a limited known subset of nodes or something similar

[ajsutton]

I would argue that due to our attestation subnet search requirements that all nodes should have both a MAX_PEERS and TARGET_PEERS value that by-default are different (MAX_PEERS > TARGET_PEERS). This would allow for new inbound connections to be made (up to MAX_PEERS) while the node then prunes down to TARGET_PEERS.

Teku does this in a similar way to Lighthouse but because there are so many nodes with closed ports, any node with open ports gets far more incoming connection attempts than it needs (or can reasonably be expected to accept). So even with a large difference between TARGET_PEERS and MAX_PEERS the node winds up constantly at MAX_PEERS. That effect is even more amplified for a node that is subscribed to a lot of subnets because it's then a high value peer to have.

We've been recommending to users for a while that the best way to improve attestation performance is ensure incoming connections work because that not only lets you find peers faster, it gives you a much wider selection of peers to select from because you will inevitably have more incoming requests than your node could possibly handle.

[AgeManning]

Also in favour of the change. I'm just thinking about attacks mentioned and also discovery efficency.

Just to clarify, anyone can still spin up a bunch of nodes and subscribe to a single subnet and try and censor messages/cause havoc on a subnet. The change here (as I understand) is that we would actively search for specific peer-ids rather than ENRs with subnet fields. The attack as it stands today, would consist of just spinning up a bunch of nodes with enr's saying you are subscribed to a subnet and discovery would try and find those nodes. I think the change suggested is here is strictly safer in that now you can't just modify an ENR field, you have to pre-generate a bunch of node-ids.

I think the next interesting thing is about whether you can eclipse a target node via discovery with your malicious nodes (that you've pregenerated). We usually search for random node ids, which makes eclipsing a individual node hard provided there are sufficient good nodes in the DHT.

Another thought I had which would make searching easier/more efficient but could potentially increase the risk of these eclipses. Currently, we select a random node-id and troll through the closest nodes to this random id until we find enough that have an ENR that match a subnet. Instead, we could potentially do the following:

Instead of having it based on peer-id have it based on node-id (used in discovery can be calculated from ENR and most cases, peer-id). If we base the subnet a node should be subscribed to on the first 8 bits of the node-id (i.e the subnet number in binary) with the epoch rotating them in some way, then we can search for peers on a subnet by searching discovery for nodes closest to a node-id with the first 8 bits being the subnet-id we want. I think this would leverage the XOR metric in discovery and the query mechanism to find nodes based on this subnet more efficiently than randomly trolling the DHT (i.e we can get discovery to specifically find nodes on a subnet). I haven't fully thought through the draw backs in possible eclipsing however.

[nisdas]

One advantage of the current strategy is that while subnets are more concentrated, an attestation that is propagated there has a very high likelihood of making it into all the aggregates eventually broadcasted. This is simply for the fact that only nodes with active validators are going to be subscribed to a subnet. For attestations to be propagated to all nodes in the particular subnet requires a smaller number of hops.

Shifting this to now be dependant on a node's id would also bring in both staking and non-staking nodes to the current subnet. If we expect non-staking nodes to eventually be 10 times the amount of staking nodes this is a non-trivial increase. An increase in the number of hops would have an effect on whether a particular individual attestation can make it into the aggregate in time. This would definitely require a bit more involved testing/simulations to see how this would affect the overall participation of the network.

Things we would have to look out for:
-> With the increased number of hops per subnet, how much longer would it take for an attestation to reach all the relevant
aggregators in that subnet ?
-> If attestations now take longer to be propagated across the network, would this change lead to more disjoint aggregates, and along with that a higher CPU load for the entire network as now more individual aggregates have to be verified ?
-> How would this perform in situations such as late blocks ? If blocks are late, there is a chance that the particular attestation might never make it into an aggregate in time due to increased number of hops across the network and permanently go 'missing' .

Also on another note to add, the peer_id isn't perfectly random. Irregardless of what curve is used to create the underlying public key, the peer-id spec appends the function code and size of the key at the start of it:
https://github.com/libp2p/specs/blob/master/peer-ids/peer-ids.md#peer-ids . This can lead to the network being biased towards particular subnets. I would agree with @AgeManning that we should be using node-id here as we do for discovery in general. The node id in contrast is simply the keccak-256 hash of the uncompressed pubkey,

[djrtwo]

One thing to note is that this will degrade on small-node-count networks (e.g. testnets and devnets).

To counteract this -- I propose adding a configuration value (only updated at network upgrades) called ESTIMATED_NETWORK_NODE_COUNT (or something...) along with MINIMUM_TARGET_SUBNET_BACKBONE which then dictates how many subnets a node must be on for honest participation.

So concretely:

• ESTIMATED_NETWORK_NODE_COUNT -- e.g. 4500 on mainnet, 100 on prater, etc
• MINIMUM_TARGET_SUBNET_BACKBONE -- e.g. 50 or whatever we deem as safe in some analysis
• change compute_subnet_from_node_id to compute_subnets_from_node_id(node_id, epoch) -> List[uint64] -- thus returning a list of size max(1, MINIMUM_TARGET_SUBNET_BACKBONE // (ESTIMATED_NETWORK_NODE_COUNT // ATTESTATION_SUBNET_COUNT) up to a maximum of ATTESTATION_SUBNET_COUNT. This would ensure that the honest behaviour based on network node count estimates is to meet the minimum subnet backbone target. On mainnet this would likely be 1 but on small testnets it would ramp up

[djrtwo]

An increase in the number of hops would have an effect on whether a particular individual attestation can make it into the aggregate in time.

fortunately gossip hops generally scale with log(N) where N is size of the network. In expectation, this likely won't affect delivery times in a well-structured/distributed network

I would agree with @AgeManning that we should be using node-id here as we do for discovery in general. The node id in contrast is simply the keccak-256 hash of the uncompressed pubkey,

Agreed