HAL-06 iteration over map source of non-determinism

[juniuszhou]

Description

The codebase contains instances of iteration over maps. As maps are not ordered in Go, iterations over maps are non-deterministic. If the consensus logic expects a deterministic result from the iteration, errors can occur where different nodes reach different states due to the differences in map ordering. If the nodes reach differing states, this can cause consensus issues, which could result in a chain halt.

Code Location:

x/tokenregistry/types/types.pb.go, Lines 582-601
Listing 8: Iteration over map (Line 582)
582 for k := range m. DoublePeggedNetworkMap {
583 v := m. DoublePeggedNetworkMap [k]
584 baseI := i
585 i- -
586 if v {
587 dAtA [i] = 1
588 } else {
589 dAtA [i] = 0
590 }
591 i- -
592 dAtA [i] = 0 x10
593 i = encodeVarintTypes (dAtA , i, uint64 (k))
594 i- -
595 dAtA [i] = 0x8
596 i = encodeVarintTypes (dAtA , i, uint64 (baseI -i))
597 i- -
598 dAtA [i] = 0x1
599 i- -
600 dAtA [i] = 0 x9a
601 }

Recommendation

Ensure that iterations over maps do not contain any logic that depends on a fixed ordering of the map. Alternatively, make use of an alternative data structure that has a deterministic ordering or ensure that maps are sorted before iterating over them.

[juniuszhou]

I don't agree with the report for the issue. Map is not determistic, but if use the same map realization and the same order of updates, then the result should be same. If we use the vector as suggested, it will be no efficient for date fetch. I suggest we won't fix it.

[juniuszhou]

close it if one more person agree with no fix. @banshee @smartyalgo @Brando753

[Brando753]

I disagree, this may still be an issue, a version of sifnode compiled with a different version of go could result in map iteration being different. We should not assume the order would be the same just because updates are made the same. I say we should huddle on this.

[juniuszhou]

After discuss with @smartyalgo , we think it is an issue, we should avoid using the map in keeper. will fix it.

[pandaring2you]

unit + integration tests modified and finished. PR awaiting review.

[pandaring2you]

@Brando753 to review PR

[pandaring2you]

@banshee reviewing. ETA next week.

[pandaring2you]

According to Michael: James is reorganizing solution to use keepers instead of maps.

[pandaring2you]

@juniuszhou to check with @banshee to see if he's currently working on a PR

[pandaring2you]

@juniuszhou to check in with James