Instantly share code, notes, and snippets.

# 0xekez/cw-future-map.md

Last active January 25, 2023 21:21
Show Gist options
• Save 0xekez/15fab6436ed593cbd59f0bdf7ecf1f61 to your computer and use it in GitHub Desktop.
CosmWasm key value store that allows incrementing and decrementing values at a times in the future

Here I describe a CosmWasm key value store that allows incrementing and decrementing values at a times in the future. For example, using this map a staking contract may increment claimable balances at time $now + unbondingDuration$ during an unstake transaction. I analyze its runtime and show that the complexity of a load is $O(1)$ and the complexity of a store scales with the number of times the unbonding duration has changed.

Let $snapshots$ be a map where $snapshots[key, time]$ holds the value of a key at a given time. If a $(key, time)$ pair does not have a value, its value is the most recently stored value for that key.

$$times(k) = \{t \mid \forall (k', t) \in snapshots,k=k'\}$$

$$load(k, t) = \begin{cases} snapshots[k, t] \quad \text{if}, (k, t) \in snapshots \\ \begin{cases} snapshots[k, t'] \quad \text{if}, \exists t'(t \ge t',t-t'= \text{min}\{t - t'' \mid t'' \in times(k)\} \\ \text{null} \quad \text{otherwise} \end{cases} \end{cases}$$

This map has two methods $increment(key, time, amount)$ and $decrement(key, time, amount)$.

$$decrement(k,t,v) = increment(k,t,\neg v)$$

To increment a key's value, the value and all future values are incremented.

fn increment(k, t, v):
if not (k, t) in snapshots:
snapshots[k][t] = load(k, t) || 0
for p in snapshots[k] where p >= t:
snapshots[k][p] += v


## $load$ Complexity

Taking advantage of the prefix features of CosmWasm maps $load$ can be implemented in $O(1)$ time and gas.

fn load(storage: &dyn Storage, t: u64, k: String) -> Option<String> {
let max = Bound::inclusive(t);
SNAPSHOTS
.prefix(k)
.range(storage, None, max, Order::Descending)
.next()
.transpose()?
.map(|(k, v)| v);
}

## $increment$ complexity

### General Case

We can take advantage of the prefix store to select [p for p in snapshots[k] where p >= t].

SNAPSHOTS
.prefix(k)
.range(storage, Bound::inclusive(t), None, Order::Ascending)

The complexity of $increment$ scales with the number of values in the range to be visited.

### Constant durations

Consider the case where $increment$ is only called at times a fixed amount into the future.

$$t := now + d$$

If time flows forward, $now$ is a monotonically increasing value, and $now + d$ is monotonically increasing.

Together with our earlier constraint this means, when $increment(k, t = (now + d))$ is called, there will never exist a $(k,t')$ in $snapshots$ where $t'&gt;t$. Thus, the max number of values in the range to be visited is one making $increment$ $O(1)$.

### Non-constant durations

Consider the case where the $d$ is a function of time.

$$t := now + d(t)$$

Let the $D$ be the set of values produced by $d$.

$$D := \{d(t_1), d(t_2), \cdots, d(t_N)\}$$

Let the set $D_k$ be the subset of values produced by $d$ when incrementing the key $k$. Below is an example set of calls to increment and the state of the sets afterwards.

increment(k_1, t_1, 1)
increment(k_2, t_1, 1)
increment(k_1, t_2, 1)


$$D = \{d(t_1), d(t_2)\}$$

$$D_1 =\{d(t_1), d(t_2)\}$$

$$D_2 = \{d(t_1)\}$$

The worst case for $increment$'s time complexity happens for a key $k$ when $D_k$ is monotonically decreasing, as each key write requires incrementing all other $(key, time)$ pairs, making $increment$ $O(|D|)$.

In other words, the complexity of $increment$ scales with the number of unique values $d(t)$ has produced.

This is nice for staking contracts that want to increment an addresses available balance a fixed duration into the future (after the unbonding duration), as in that language:

The gas cost of changing a value in the map scales with the number of unique values the unbonding duration has taken on.