Counterintuitive Runtime

The Cosmos SDK has a KV store that smart contracts and modules can read and write to. Reading from and writing to this KV store costs gas and is metered as follows:

func KVGasConfig() GasConfig {
	return GasConfig{
		HasCost:          1000, // does key exist?
		DeleteCost:       1000, // delete key
		ReadCostFlat:     1000, // start reading
		ReadCostPerByte:  3,    // read cost per byte
		WriteCostFlat:    2000, // start writing
		WriteCostPerByte: 30,   // write cost per byte
		IterNextCostFlat: 30,   // iterate over sorted keys
	}
}

In the underlying data-structure, all operations are $O(\mathbb{log}(N))$ where $N$ is the number of nodes in the tree; however, gas costs don't change with the size of the KV store.

The operation that makes this interesting is iter which returns the next element in a sorted, ascending or descending, range of keys. This operation being $O(1)$ gas, means that getting a sorted list of the keys in a map is $O(N)$ where $N$ is the number of elements that need to be read. To do a sort, you repeatedly call iter and read the next value.

In addition to being able to sort in linear time, you can sort lazily and retrieve the first element in sorted order in $O(1)$. To do this, call iter and then read the first value. To get the last element, call iter with descending order.

Sorting being $O(N)$, and reading and writing being $O(1)$, makes some strange data-structures possible. For example, cw-wormhole or an $O(1)$ FIFO queue.