Iterating over maps is nondeterministic
Description
It is vitally important that any calculations done by the chain are deterministic and can be reproduced by every validator so that the state of the network can be agreed upon. One source of nondeterminism in Go is iterating over maps: the specification states, "The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next" (https://go.dev/ref/spec#RangeClause↗).
The removeInvalidBallots and countVotesAndUpdateExchangeRates functions are both called from an EndBlocker and iterate over a map:
func (k Keeper) removeInvalidBallots(
ctx sdk.Context,
pairBallotsMap map[asset.Pair]types.ExchangeRateBallots,
) (map[asset.Pair]types.ExchangeRateBallots, set.Set[asset.Pair]) {
whitelistedPairs := set.New(k.GetWhitelistedPairs(ctx)...)
totalBondedPower := sdk.TokensToConsensusPower(k.StakingKeeper.TotalBondedTokens(ctx), k.StakingKeeper.PowerReduction(ctx))
thresholdVotingPower := k.VoteThreshold(ctx).MulInt64(totalBondedPower).RoundInt()
minVoters := k.MinVoters(ctx)
for pair, ballots := range pairBallotsMap {
// If pair is not whitelisted, or the ballot for it has failed, then skip
// and remove it from pairBallotsMap for iteration efficiency
if _, exists := whitelistedPairs[pair]; !exists {
delete(pairBallotsMap, pair)
continue
}
// If the ballot is not passed, remove it from the whitelistedPairs set
// to prevent slashing validators who did valid vote.
if !isPassingVoteThreshold(ballots, thresholdVotingPower, minVoters) {
delete(whitelistedPairs, pair)
delete(pairBallotsMap, pair)
continue
}
}
return pairBallotsMap, whitelistedPairs
}
func (k Keeper) countVotesAndUpdateExchangeRates(
ctx sdk.Context,
pairBallotsMap map[asset.Pair]types.ExchangeRateBallots,
validatorPerformances types.ValidatorPerformances,
) {
rewardBand := k.RewardBand(ctx)
for pair, ballots := range pairBallotsMap {
exchangeRate := Tally(ballots, rewardBand, validatorPerformances)
k.SetPrice(ctx, pair, exchangeRate)
ctx.EventManager().EmitEvent(
sdk.NewEvent(types.EventTypeExchangeRateUpdate,
sdk.NewAttribute(types.AttributeKeyPair, pair.String()),
sdk.NewAttribute(types.AttributeKeyExchangeRate, exchangeRate.String()),
),
)
}
}Impact
Currently, the operations that are performed in k.SetPrice end up being the same regardless of the order it is called, so it is unlikely to cause a chain halt. However, a simple unrelated change to a keeper in the future could cause this issue to occur as the order that the pairs are processed can be different.
Recommendations
Instead of iterating over the map, the function should iterate over a sorted list of keys.
// countVotesAndUpdateExchangeRates processes the votes and updates the ExchangeRates based on the results.
func (k Keeper) countVotesAndUpdateExchangeRates(
ctx sdk.Context,
pairBallotsMap map[asset.Pair]types.ExchangeRateBallots,
validatorPerformances types.ValidatorPerformances,
) {
rewardBand := k.RewardBand(ctx)
keys := make([]string, 0, len(pairBallotsMap))
for key := range pairBallotsMap {
keys = append(keys, key.String())
}
sort.Strings(keys)
for _, key := range keys {
pair := asset.MustNewPair(key)
ballots := pairBallotsMap[pair]
exchangeRate := Tally(ballots, rewardBand, validatorPerformances)
k.SetPrice(ctx, pair, exchangeRate)
ctx.EventManager().EmitEvent(
sdk.NewEvent(types.EventTypeExchangeRateUpdate,
sdk.NewAttribute(types.AttributeKeyPair, pair.String()),
sdk.NewAttribute(types.AttributeKeyExchangeRate, exchangeRate.String()),
),
)
}
}Remediation
This issue has been acknowledged by Nibiru, and a fix was implemented in commit 3482a22d↗.