What's the intended behavior of filterContained ?

[mitmotw]

prysm/proto/prysm/v1alpha1/attestation/aggregation/attestations/maxcover.go

Line 271 in a85b444

c, err := filtered[len(filtered)-1].AggregationBits.Contains(al[i].AggregationBits)

Hi all,

These days I got curious of attestations, so was reading prysm codes, and
I got suspicious of this filterContained function.

As the comment says in code,
I think the intended behavior is getting not overlapping attestations.
// filterContained removes attestations that are contained within other attestations.

However it's checking 'contains' between the 'last element of filtered' and new attestation from given attestation list.
So what I'm worrying is like below case.

let the given attestation list has 3 attestations and aggregation bits are like below.
(Just assumed aggregation bits are 6 bits for convenience)

attestation[0].AggregationBits = [1, 1, 1, 1, 0, 0]
attestation[1].AggregationBits = [0, 0, 0, 0, 1, 1]
attestation[2].AggregationBits = [0, 0, 0, 1, 0, 0]

Here I expect all the 3 elements will be included in the final returned list, filtered.

At the first iteration,
attestation[1] will be appended because attestation[0].AggregationBits does not contain attestation[1].AggregationBits.

At the second iteration,
attestation[2] will be appended because attestation[1].AggregationBits (which is the final element of filtered) does not contain attestation[2].AggregationBits.

Like this, all 3 elements will be included in filtered list even though attestation[0].AggregationBits contains attestation[2].AggregationBits.

Is this intended behavior for this function?
Please let me know if I'm missing something.

[potuz]

Thank you for spotting this, this code from early 2020 seems wrong to me as well, here's a test that fails with your parameters

func TestFilterContained(t *testing.T) {
        sign := bls.NewAggregateSignature().Marshal()
        al := attList{
                {AggregationBits: bitfield.Bitlist{0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0b00111100, 0b1}, Signature: sign},
                {AggregationBits: bitfield.Bitlist{0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0b00000011, 0b1}, Signature: sign},
                {AggregationBits: bitfield.Bitlist{0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0b00000100, 0b1}, Signature: sign},
        }
        filtered, err := al.filterContained()
        require.NoError(t, err)
        require.Equal(t, 2, len(filtered))
}

[mitmotw]

Thank you @potuz for confirm. 😄
I added a pull request for this.

#12740