GetAllHistoricalInfo returns wrong order when height goes through 10^n (i.e. number of digits change)

[nnkken]

Summary of Bug

In staking module, when the block heights for historical info goes through boundary of 10^n (i.e. number of digits change), GetAllHistoricalInfo returns the info in wrong order.

Reason: the module is using decimal string of the block height as store key for historical info:

func GetHistoricalInfoKey(height int64) []byte {
	return append(HistoricalInfoKey, []byte(strconv.FormatInt(height, 10))...)
}

So when the number of digits in the decimal string changes, the key order will be wrong: 9, 10, 11 results in 10, 11, 9 since this is the character order for the strings.

Unfortunately there is no easy fix, since it's related to key format. Doing extra sort in GetAllHistoricalInfo will fix this function, but the iterator order can't be fixed.

Fortunately GetAllHistoricalInfo and IterateHistoricalInfo are not in use by any code in the SDK (including ibc-go) other than the test case. So why writing them in the first place?

Version

Tested in v0.44.6, suspects that this exists in every version

Steps to Reproduce

Simply change the block heights in TestGetAllHistoricalInfo from 10, 11, 12 to 9, 10, 11, then the test will fail.

func TestGetAllHistoricalInfo(t *testing.T) {
	_, app, ctx := createTestInput()

	addrDels := simapp.AddTestAddrsIncremental(app, ctx, 50, sdk.NewInt(0))
	addrVals := simapp.ConvertAddrsToValAddrs(addrDels)

	valSet := []types.Validator{
		teststaking.NewValidator(t, addrVals[0], PKs[0]),
		teststaking.NewValidator(t, addrVals[1], PKs[1]),
	}

	header1 := tmproto.Header{ChainID: "HelloChain", Height: 9}
	header2 := tmproto.Header{ChainID: "HelloChain", Height: 10}
	header3 := tmproto.Header{ChainID: "HelloChain", Height: 11}

	hist1 := types.HistoricalInfo{Header: header1, Valset: valSet}
	hist2 := types.HistoricalInfo{Header: header2, Valset: valSet}
	hist3 := types.HistoricalInfo{Header: header3, Valset: valSet}

	expHistInfos := []types.HistoricalInfo{hist1, hist2, hist3}

	for i, hi := range expHistInfos {
		app.StakingKeeper.SetHistoricalInfo(ctx, int64(9+i), &hi)
	}

	infos := app.StakingKeeper.GetAllHistoricalInfo(ctx)
	require.Equal(t, expHistInfos, infos)
}

Result:

...
                Diff:
                --- Expected
                +++ Actual
                @@ -8,3 +8,3 @@
                    ChainID: (string) (len=10) "HelloChain",
                -   Height: (int64) 9,
                +   Height: (int64) 10,
                    Time: (time.Time) {
                @@ -209,3 +209,3 @@
                    ChainID: (string) (len=10) "HelloChain",
                -   Height: (int64) 10,
                +   Height: (int64) 11,
                    Time: (time.Time) {
                @@ -410,3 +410,3 @@
                    ChainID: (string) (len=10) "HelloChain",
                -   Height: (int64) 11,
                +   Height: (int64) 9,
                    Time: (time.Time) {
Test:           TestGetAllHistoricalInfo

---

For Admin Use

• Not duplicate issue
• Appropriate labels applied
• Appropriate contributors tagged
• Contributor assigned/self-assigned

[tac0turtle]

@AdityaSripal does this effect IBC?

[alexanderbez]

Looks like the key is poorly designed, yes. If need be, we can fix it with a migration.

[AdityaSripal]

Yes that is unintended, but as stated, it luckily does not affect IBC.

The only place where it could have been an issue is in our pruning logic. Since we prune old historical info once we no longer need it.

But we retrieve it by getting each individual historical info here:

cosmos-sdk/x/staking/keeper/historical_info.go

Line 68 in 76895e6

func (k Keeper) TrackHistoricalInfo(ctx sdk.Context) {

Rather than iterating lexicographically.

It would be nice to fix this so that the above gets are efficient. But it is not a critical issue

[deepto98]

Can I pick this up?

[alexanderbez]

Yes please @deepto98! Thanks for all the help :)

[deepto98]

@alexanderbez @AdityaSripal I'm working on this, but am not able to reproduce the exact issue. For me, TestGetAllHistoricalInfo passes even when I pass 9,10,11 as the heights. Can you please give me a brief about the code and what changes I should implement?

[alexanderbez]

@deepto98 you mean you implemented the test in the issue body and it did not fail for you?

[babadro]

Hi, I would appreciate some early feedback.

The question is - how should we prepare the migration?
Should it be in a separate PR or included in the same one?

#15701