Instantly share code, notes, and snippets.

0xekez/counterintuitive-runtime.md

Created June 4, 2023 08:29
Show Gist options
• Save 0xekez/d6dcd62ad074da3224fa77c95c4d04b4 to your computer and use it in GitHub Desktop.

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
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.