Please see [Invalid] Another attempt at O(n) LMD GHOST that is constant time on the number of blocks since genesis for an updated version.
For background on CBC Casper, see: https://vitalik.ca/general/2018/12/05/cbc_casper.html
Here is an idea for a O(n) time estimator where n is the number of validators for the blockchain. In short, we are pushing all the information needed to execute the LMD GHOST fork choice rule into each block. In the map of bonded validators, in addition to their stakes, keep a counter that represents the depth of the last block the validator has proposed in the current chain. When proposing a new block, add 1 to the previous value of the counter for every other validator but yourself and set your counter to 0. Score the latest messages (blocks) based on the following formula:
-
Subtract the maximum counter value from all counters. Call this negative (or zero) value the normalized counter.
-
Build an list of tuples as follows. Drop the validator corresponding to the maximum value counter (which will be zero) and take the negated sum of all the remaining validator’s stakes. The first element will be a tuple of that sum followed by the largest normalized counter value remaining. Drop the validator corresponding to the second largest normalized counter and take the negated sum of all the remaining validator’s stakes. The second element will be a tuple of that sum followed by the value of the largest normalized counter value remaining. And so on. For tied normalized counter values, drop the validator with the higher stake. For example, if you have a map from validator stakes to normalized counters that look like {10:-4, 10:-5, 11:0, 10:0} this will become [(-30,0), (-20,-4), (-10,-5)].
-
The resulting array is the score. To compare scores, compare across the first element of each tuple down the array. Tiebreak using the second element of each tuple. For example, [(-31,0), (-21,-3), (-10,-5)] is smaller than [(-31,0), (-20,-4), (-10,-5)].
The estimator should return the latest message (block) with the LOWEST score. Note that this estimator returns the same result as the original LMD GHOST fork choice rule.
Edit: I change the algorithm to drop the validator with the higher stake for tied normalized counter values.