Map iteration non determinism in consumer AccumulateChanges

[danwt]

Problem

AccumulateChanges used to aggregate tendermint updates on the consumer uses non deterministic map iteration to produce a list, and then writes the list to store in one go. I think this could cause a consensus error.

Closing criteria

Fix the nondeterminism.

Problem details

interchain-security/x/ccv/utils/utils.go

Lines 29 to 31 in 25b0d01

	for _, update := range m {
	out = append(out, update)
	}

interchain-security/x/ccv/consumer/keeper/relay.go

Lines 58 to 59 in 25b0d01

	err := k.SetPendingChanges(ctx, ccv.ValidatorSetChangePacketData{
	ValidatorUpdates: pendingChanges,

TODOs

• Labels have been added for issue
• Issue has been added to the ICS project

[danwt]

I'm not sure that it's safe to use .String() to get the map key

interchain-security/x/ccv/utils/utils.go

Lines 19 to 25 in 25b0d01

	for i := 0; i < len(currentChanges); i++ {
	m[currentChanges[i].PubKey.String()] = currentChanges[i]
	}
	for i := 0; i < len(newChanges); i++ {
	m[newChanges[i].PubKey.String()] = newChanges[i]
	}

// DeterministicStringify returns a deterministic string representation of the
// key. This is useful to identify like keys with different representations.
func DeterministicStringify(k tmprotocrypto.PublicKey) string {
	sdkPubKey, err := cryptocodec.FromTmProtoPublicKey(k)
	if err != nil {
		panic("could not get sdk public key from tm proto public key")
	}
	return string(sdkPubKey.Bytes())
}

Maybe it's better to use consensus address here^^

// The list of tendermint updates should hash the same across all consensus nodes
	// that means it is necessary to sort for determinism.
	sort.Slice(consumerUpdatesAsList, func(i, j int) bool {
		if consumerUpdatesAsList[i].Power > consumerUpdatesAsList[j].Power {
			return true
		}
		return consumerUpdatesAsList[i].PubKey.String() > consumerUpdatesAsList[j].PubKey.String()
	})

[mpoke]

AccumulateChanges used to aggregate tendermint updates on the consumer uses non deterministic map iteration to produce a list, and then writes the list to store in one go. I think this could cause a consensus error.

Does ABCI require the lists of validator updates return by different nodes in EndBlock to be in the same order?

Maybe it's better to use consensus address here

Would that mean hashing the public key for every update? That sounds like a lot of hashing just for this purpose.

[mpoke]

It seems that the only requirement is that any two nodes return the same list of updates, but not necessarily in the same order. Confirmed by @sergio-mena

[danwt]

Ahh yeah I forgot that these are never committed to store, because the pending updates are always deleted in endblock. I think it's fine then.

[jtremback]

I still think we should fix this. The fix is very easy.

[danwt]

Snippet like

// The list of tendermint updates should hash the same across all consensus nodes
	// that means it is necessary to sort for determinism.
	sort.Slice(consumerUpdatesAsList, func(i, j int) bool {
		if consumerUpdatesAsList[i].Power > consumerUpdatesAsList[j].Power {
			return true
		}
		return consumerUpdatesAsList[i].PubKey.String() > consumerUpdatesAsList[j].PubKey.String()
	})

EDIT: not correct :/ lol