Eth2.0-specs: Do we want to avoid NP hard problems for implementers

[JustinDrake]

The Sigmaprime people (@michaelsproul) are highlighting that there are NP hard problems for implementers for optimal validator behaviour. One example is inclusion of attestations in blocks. In a single block there can be multiple attestations corresponding to subsets of the same committee (this is because two partially-aggregated attestations cannot always be merged). In this instance, a protocol-level fix would be to only allow one single attestation per committee per block.

Question: Is avoiding NP hard problems for implementers a design goal for the beacon chain?

[djrtwo]

There are plenty of tractable near-optimal solutions to NP hard problems.

Given that we have a bag of attestations of which a subset needs to go into blocks, I'm pretty sure even with removing double committees this problem is still NP hard. The domain is just smaller. I don't see how to avoid this being NP hard if the client wants to "optimally" pack a block where optimal is profit maximizing.

In short, I lean toward not attempting to remove NP hard problems in general but can approach them case by case.

For this one, I lean toward allowing adding double committees in an attempt to bring more information on chain quicker. Maybe we wait until testnets and more data to see if we want to do this. The 1-second slot testnet should demonstrate how bad partial aggregations might get

[dankrad]

There are plenty of tractable near-optimal solutions to NP hard problems.

At least to some of them. I agree with @djrtwo that this should be decided case by case. The relevant question is how good the P approximation to this problem is.

[michaelsproul]

@dankrad: The relevant question is how good the P approximation to this problem is.

For including attestations in a block, I think the Maximum Coverage Problem is close, and the best possible approximation algorithm for MCP is a simple greedy algorithm with an approximation factor of 0.632. I've implemented it on a branch for Lighthouse.

@djrtwo: I'm pretty sure even with removing double committees this problem is still NP hard.

I think it might not be, you could score each aggregate attestation by the number of rewards it will net you (the number of validators for which it will be the earliest attestation in the epoch), and then take the best attestations, one per committee. Because you know that the attestations you take don't overlap in their committees, you don't need to worry about whether including one attestation changes the score of another.

Those two algorithms have similar runtimes, so maybe this is a moot point, and the ability to bundle multiple attestations per committee is worth keeping (i.e. leave it NP-Hard)

[djrtwo]

Another reason we would not want to prevent inclusion of multiple attestations from committees is that they might be attesting to different data, not just having mismatched aggregation. Even if the committee is attesting to a different head or shard block data, it might still contribute to on-chain finality and would be a loss to miss quick inclusion.

Also to note, the spec doesn't specify this as NP-hard. The client implementer wanting maximize profit makes it NP-hard :)

[JustinDrake]

the spec doesn't specify this as NP-hard

Is the validator doc part of the spec? :)

[djrtwo]

good question... forgot I wrote the following

To maximize profit, the validator should attempt to gather aggregate attestations that include singular attestations from the largest number of validators whose signatures from the same epoch have not previously been added on chain.

note, I said "attempt"!

[JustinDrake]

Closing this issue for now. I think we share an intuitive notion of what is "acceptable" NP-hard problem for implementers (e.g. one for which we have fast approximate algorithms). As it stands, I'm not aware of any non-acceptable NP-hard problem for implementers.