Consumer chain removal sub-protocol fails to remove some chains

[ivan-gavran]

Surfaced from @informalsystems security feedback on Interchain Security at commit dc19c57

Problem

EndBlockCCR removes chains which timed out. However, when iterating through all chains, it stops as soon as it finds one chain that did not time out, falsely assuming that the chains are ordered by their time of arrival <=> expiration time.

Closing criteria

The bug is confirmed and fixed.

Problem details

Please describe the problem in all detail.

This part of the code might be wrong:

• it breaks out of iteration as soon as it finds one init timeout that has not expired (citing the assumption that they are ordered-implicitly-by the time of arrival)

 k.IterateInitTimeoutTimestamp(ctx, func(chainID string, ts uint64) bool {
 	if currentTimeUint64 > ts {
 		// initTimeout expired
 		chainIdsToRemove = append(chainIdsToRemove, chainID)
 		// continue to iterate through all timed out consumers
 		return true
 	}
 	// break iteration since the timeout timestamps are in order
 	return false
 })

• looking into the iteration function, it uses the KVStorePrefixIterator. This iterator iterates over keys in ascending order.
• but keys are simply a concatenation of a fixed prefix and the chainID as given in the proposal, thus, they do not encode the order of arrival
• thus, whether or not the function does what it promises to do, depends on the alphabetical order of chainIDs

I added a test illustrating the problem in my fork of the repo.

TODOs

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

[danwt]

Nice job, thanks!

[ivan-gavran]

@danwt , a similar pattern can be found just below, when iterating over VSC send timestamps. There, only a first send timestamp is checked, again assuming that the first in the iteration is also the first chronologically. However, the assumption is probably justified there, because the key consists of the part which is fixed per-chain and the vscID, where the sequence of vscIDs is an ascending sequence of natural numbers.

While this does not seem to be a problem, I am raising the issue here
a) so that you can double check my "no-problem" justification
b) to call your attention this somewhat unclear part of the code. Namely,

• what if in some future refactoring vscIds are generated as random keys?
• it might just be useful to have an explicit function GetTheOldest.., instead of accomplishing the same by iterating and stopping immediately after the first element.

[danwt]

Thanks for raising this. I will investigate soon. In the meantime I want to mention that we are aware of some problems with iterators

• Change our Iterators functions to take a stop callback to match the SDK iterator pattern #449
• Fix early returning iterator #433
• Map iteration non determinism in consumer AccumulateChanges #505

By now dc19c57 is quite old!

Thanks for the thorough work!

[danwt]

Another possibly related issue

• Document iteration in ConsumerAdditionPropsToExecute #446