Consensus bug

[damip]

Issue found through external auditing.

Description

The function list_final_blocks() determines final blocks based on max cliques and descendant fitness. However, the final candidates may be selected incorrectly.

The function sorts the max cliques by size and initializes the final candidates with the blocks in the smallest max clique. Then it checks if the candidates are in other max cliques. If the auditing team understood the logic correctly, a final candidate has to be in all the max cliques.

    // short-circuiting intersection of cliques from smallest to largest
    let mut indices: Vec<usize> = (0..self.max_cliques.len()).collect();
    indices.sort_unstable_by_key(|&i| self.max_cliques[i].block_ids.len());
    let mut final_candidates = self.max_cliques[indices[0]].block_ids.clone();
    for i in 1..indices.len() {
        final_candidates.retain(|v| self.max_cliques[i].block_ids.contains(v));
        if final_candidates.is_empty() {
            break;
        }
    }

However, at line 181, the loop goes through max_cliques with i instead of indices[i], if the order of indices changes during the sort, the election will be invalid. More specifically, the function checks if the final candidates are in {max_cliques[i] | $i\in [1, n]$}, where $n =$ indices.len(), instead of {max_cliques[$i$] | $i\in [0, n]$ and $i \ne$ indices[0]}.

For example, suppose there are two max cliques [B1, B2, B3] (max_cliques[0]) and [B4, B5] (max_cliques[1]).

Step 1: Sort max cliques and set the indices [1, 0] as max_cliques[1] < max_cliques[0].
Step 2: Initialize final_candidates as [B4, B5] (max_cliques[indices[0]]).
Step 3: Check if [B4, B5] are in max_cliques[1]. Although [B4, B5] are not in max_cliques[0], they will be listed as final candidates because the function does not check if they are in max_cliques[0].

In this way, blocks not in all max cliques can still be listed as final blocks.

Recommendation

Recommend fixing the check of if the final candidates are in all max cliques:

    for i in 1..indices.len() {
        final_candidates.retain(|v| self.max_cliques[indices[i]].block_ids.contains(v));
        if final_candidates.is_empty() {
            break;
        }
    }