Great work! I really love the stateful sum vote DAG and the optimization there of only needing to update going back to the intersection between the old vote and the new vote.
Made some comments already in the sharding gitter. Copying some important ones:
- There’s an important optimization usable for all of these implementations, that if some set of validators are (attesting to | newly attesting to | no longer attesting to) the same block, those effects can be aggregated together and processed as one. So in the maximally happy case, where all validators participate every epoch so their new latest messages are in the current epoch and their previous ones are in the previous epoch, the fork choice rule can be computed/evaluated in O(128 * log(t)) time, with the exception of the preprocessing step, but that’s relatively trivial as it’s just up to 4 million arithmetic and equality checking operations.
- Need to take into account validator balance changes (see https://github.com/ethereum/eth2.0-specs/pull/571); but if we use
int(balance)instead of balance as in the PR then these changes should be infrequent. - In the longer term, changes like Rate-limiting entry/exits, not withdrawals might make it so that instead of using one validator set, there would be different validator sets active at different contexts. For example, if a block R has children A and B, and A has children A1 and A2, and B has children B1 and B2, the validator sets used to decide A vs B, A1 vs A2, and B1 vs B2 would all be different.