Cosmos-sdk: Coins.AmountOf bug

[jackzampolin]

When trying to run gentx on the gaia-10k @zmanian and I encountered an issue where unless the bondDenom was the last token in the array the AmountOf function didn't return the proper amount (it returned 0). The binary search is not working correctly, it seems like it doesn’t find values in position 0:

midIdx := len(coins) / 2 // 2:1, 3:1, 4:2
coin := coins[midIdx]

if denom < coin.Denom {
  return coins[:midIdx].AmountOf(denom)
} else if denom == coin.Denom {
  return coin.Amount
} else {
  return coins[midIdx+1:].AmountOf(denom)
}

[zmanian]

Here is the thing, this code assumes that the coins are sorted by denom.

Are we expected to maintain that as an invariant?

[rigelrozanski]

yes the coins array must always be sorted, deviation from this is an unsupported state AFAICT

is this prelaunch? - we are only launching with one token

[cwgoes]

Are we expected to maintain that as an invariant?

Yes. This behavior is expected. We should validate that coins in the genesis file are sorted, or sort them when reading the genesis file.

[alessio]

From genesis_accts.go:

            coins, err := sdk.ParseCoins(args[1])
            if err != nil {
                return err
            }
            coins.Sort()

Did you guys add/modify the offending account manually?

[zmanian]

Yeah the account was added by scripts used to build the large genesis file used before. I can't ensure that coins are sorted in future scripts.

[alexanderbez]

@jackzampolin @zmanian what exact call is this breaking at? Should be straightforward to ensure coins are manually sorted prior to any essential business logic.

[zmanian]

func accountInGenesis(genesisState app.GenesisState, key sdk.AccAddress, coins sdk.Coins) error {
    accountIsInGenesis := false
    bondDenom := genesisState.StakingData.Params.BondDenom

    // Check if the account is in genesis
    for _, acc := range genesisState.Accounts {
        // Ensure that account is in genesis
        if acc.Address.Equals(key) {

            // Ensure account contains enough funds of default bond denom
            if coins.AmountOf(bondDenom).GT(acc.Coins.AmountOf(bondDenom)) {
                return fmt.Errorf(
                    "account %v is in genesis, but it only has %v%v available to stake, not %v%v",
                    key.String(), acc.Coins.AmountOf(bondDenom), bondDenom, coins.AmountOf(bondDenom), bondDenom,
                )
            }
            accountIsInGenesis = true
            break
        }
    }

in gentx.go

[zmanian]

Do you think we should sort inside that function?

[alexanderbez]

great! I can think of a few options here:

• Add a Sanitize method to GenesisState. For now, all this method will do is sort coins. This will be called right after it's loaded from file and right before accountInGenesis is called.
• Or, do as you suggest and manually call Sort in accountInGenesis.

I think the former might be more useful.

[zmanian]

I'm in favor of Sanitize

[alexanderbez]

Ok, super trivial then. I'm sure @alessio or I can quickly wrap this up for you 👍

[shanev]

Just got burned by this. It's not clear outside of looking at the SDK source that coins need to be sorted by denom. This is an easy mistake to make since sdk.Coins is essentially a slice which can be appended.

A simple fix would be to check IsValid() before all operations.

[alexanderbez]

@shanev nearly all, if not all, Coins godoc have this invariant stated. We could call IsValid() but that would add additional overhead.

[shanev]

@alexanderbez I only see sorting mentioned in a handful of places in godoc. To a noob it would be unclear what this means. Sort by amount? Denom? Denom is only mentioned in Plus(). It doesn't specifically state you'll get non-deterministic behavior if coins aren't sorted. You probably want to avoid non-deterministic behavior in the first place in a blockchain SDK. In our case, we were getting insufficient funds errors when testers were trying to stake with certain coins. Ideally it should never even get there. I personally think it should even panic when unsorted. When I get some free time I'll PR some improvements to the comments.

[alexanderbez]

Agreed the documentation should be more clear and updated (although I think sorted by denom is implicit and somewhat obvious). However, if we can find a low performance cost way of further guaranteeing safety and avoiding such a situation altogether, I'm all for it. Do you have suggestions? Perhaps we can can implement radix sort on denoms for near constant time.

[shanev]

Let me think on it. My only immediate suggestion would be to add something like "Coins must be sorted by denom" to the godoc for all functions that depend on coins being sorted, like HasCoins() in bank keeper, and AmountOf().

[alessio]

Hello @shanev,

And thanks for taking the time to share your feedback and helping to make the SDK better!

In our case, we were getting insufficient funds errors when testers were trying to stake with certain coins.

Can you provide more information on your specific use case please? Terminal log excerpts and gaiacli version/gaiad version output would be greatly appreciated.