Consider changing the type of NodeKey.nonce to uint32

[elias-orijtech]

The type of NodeKey.nonce is currently an int32:

https://github.com/cosmos/iavl/blob/d0241db89d211a17e9dbd249587cba257d36a4f9/node.go#L24

However, a quick skim of the uses of nonce doesn't reveal a special meaning of its sign. Therefore a better type is uint32 to avoid special handling of the first bit. In particular, > 0 should be equivalent to != 0.

Came up while reviewing https://github.com/cosmos/iavl/pull/750/files.

CC @odeke-em

[yihuang]

I think no harm to just use int64, since we already store with varint encoding?

[yihuang]

regarding signed vs unsigned, on one hand unsigned type is more truthful for non-negative values as you mentioned, but there are also different opinions on this: https://hamstergene.github.io/posts/2021-10-30-do-not-use-unsigned-for-nonnegativity/

[elias-orijtech]

To me a nonce is an opaque value that should never participate in arithmetic. For that, I consider the signed-ness at best a distraction (one bit of the value is special), at worst a source of bugs as you can see from the review where > means something subtly different than !=.

In summary, unsigned types are simpler than signed types. Even better would be something like

const nonceSize = 4
type Nonce [nonceSize]byte

where only equality and inequality operators work.

[cool-develope]

I am not sure if the []byte is more efficient since we are saving nonce using EncodeVarint (https://github.com/cosmos/iavl/blob/747bc123a38b5803b470fb0faa649207a6c2d739/internal/encoding/encoding.go#L141) Will it require extra conversion? Also if we store it as a byte array, I am worried it will increase the storage size.

[elias-orijtech]

I am not sure if the []byte is more efficient since we are saving nonce using EncodeVarint (

https://github.com/cosmos/iavl/blob/747bc123a38b5803b470fb0faa649207a6c2d739/internal/encoding/encoding.go#L141 ) Will it require extra conversion? Also if we store it as a byte array, I am worried it will increase the storage size.

Correct. And from discussions in the team call yesterday it seems that nonce is more like a seqnum, no? If so, the ideal type would be uint32/uint64.

[tac0turtle]

I was Talking to @yihuang about using uint64 because on genesis import there are cases where the genesis file would be gbs if not 10s of gbs bug which could push close to maxuint32. Since we don't have a clean way to test this and if there no performance deforestations we might as well go to uint64 .

[tac0turtle]

modified in the pr of lazy set to use uint32