The three horsemen of NFT staking and voting power

[0xekez]

tl;dr: our current NFT staking contract has some subtle gas usage
issues that could cause NFTs to be locked if an address stakes enough
NFTs to trigger an out-of-gas issue. We need a new state design, but
it is pretty non-trivial to come up with a good one. This document
explains the problem and suggests a alternative state design.

to be clear, this does not impact any production code. the discussion here
is about the beta release of v2.0.0 which does not have any deployments.

Any non fungible token (NFT) staking contract has three requirements:

1. NFTs can be staked.
2. NFTs can be unstaked by specifying the token ID of the NFT.
3. A frontend can query all of the NFTs staked by an address.

Ours has one extra because we'd like to use staked NFTs as voting
power:

4. The number of NFTs staked by an address is available in constant
   time.

A synthesizing (1), (2), and (3) into data-structure level
requirements, we get that the following must happen in constant time:

1a. Determine if a given address previously staked a given token ID.
2a. Get an arbitrary token ID from the list of tokens staked by an
address.

(1a) is required as we need to be able to validate that addresses can
only unstake tokens that they previously staked; (2a) is required
because we need to be able to expose the list of tokens staked by a
user to a frontend, so that the user may select the ones they would
like to unstake.

Why this is hard

The easiest way to explain this is to walk through some ways we may
solve it, and then examine how each fails.

---

aside: all of the examples here use a Map for simplicity, in
practice we need this information as a function of block height so
we'd use a SnapshotMap.

---

Attempt one

A "CosmWasm native" approach might be to use its Map type as a set:

/// (address, token_id) -> empty. existence of key implies it has been
/// staked.
const M: Map<(Addr, String), Empty> = /* ... */;

This performs well for requirements (1a) and (2a), but falls on its
face when we want to determine how many tokens are owned by an
address. The reason being that we can't get the number of elements
that have a prefix (an address) without loading and iterating over all
of the elements with that prefix.

The reason for this is a bit nuanced, but comes down to two
things. First, for iterating over sections of a map, CosmWasm exports
two methods to wasm blobs:

#[cfg(feature = "iterator")]
fn db_scan(start_ptr: u32, end_ptr: u32, order: i32) -> u32;
#[cfg(feature = "iterator")]
fn db_next(iterator_id: u32) -> u32;

db_scan gives us a way to iterate over all the NFTs staked by an
address, but in order to determine the length of that iterator it
requires N db_next calls, where N is the number of tokens
staked. Another way to understand this (the second thing) is: Rust's
iterator API does not guarantee that calls to len are constant time.

Attempt two

We can trivially satisfy the requirements of (1a) and (2a) by storing
a mapping between addresses and their set of staked NFTs. For example:

const M: Map<Addr, HashSet<String>> = /* ... */;

This also satisfies requirement (4) so long as the HashSet
implementation allows for constant time length calls (which Rust's
hash map does), as this allows us to load and get the number of NFTs
an address has staked.

This has two problems:

1. Queries in CosmWasm are tightly gas limited. To mitigate this, most
   queries take a start_after argument which allows beginning a
   query in the middle of the list. Rust's HashSet does not allow
   beginning iteration in the middle of the data-structure in constant
   time.
2. Staking a new NFT is O(deserialization complexity) which is at
   least O(N) as we need to deserailize the entire set to add an
   element or check for the existence of an element.

We could mitigate (2) with some careful measurements and limits to the
number of staked NFTs which leads us to..

Attempt three

---

note: this is the approach currently taken by our NFT staking
contract. It has gas issues as a result of (2) above.

---

We can swap out the HashSet with a map that preserves order allows
iteration starting from arbitrary indexes in constant time:

const M: Map<Addr, IndexSet<String>> = /* ... */;

This resolves issue (1) from attempt two, but issue (2) remains.

A possible solution

We can add an additional map to "Approach one" above:

const N: SnapshotMap<Addr, u32> = /* ... */;

This map can store the number of NFTs staked per address, thus giving
us constant time voting power queries. It's less elegant than a single
state key, but I think we can wrap this in a nice abstraction.

Ultimately, I suspect this may also reduce overall contract state
usage as in the single-key model the map must be a snapshot map, but
in this model it does not (we only need historical numbers, not
values) making our complete state:

const M: Map<(Addr, String), Empty> = /* ... */;
const N: SnapshotMap<Addr, u32> = /* ... */;

Wrapped up in a type I think this could be quite elegant.