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
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);
}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.
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)$.
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.
