CosmWasm key value store that allows incrementing and decrementing values at a times in the future

cw-future-map.md

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