Skip to content

Instantly share code, notes, and snippets.

@0xekez
Last active August 29, 2024 22:40
Show Gist options
  • Save 0xekez/15fab6436ed593cbd59f0bdf7ecf1f61 to your computer and use it in GitHub Desktop.
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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment