The problem of managing state

[lontivero]

@turbolay's work on synchronization performance as well as @molnard work on mempools synchronization had revived many discussions/critics about our wallet design that I think it worth to share with the team.

Definition

We don't have strict definitions for some critical concepts like wallet. What exactly is a bitcoin wallet? I think it means different things for different people but it should be expected to have a very clear and shared meaning for developers, however I think that's not completely true so, just of the sake of this discussion let define a wallet as a set of scripts that we know (and control, in the majority of the cases).

Building an useful cache (utxoset)

For each transaction in the blockchain, the script set is evaluated against the tx's outputs to discover new utxos while each tx's input is evaluated against the utxoset to remove the uxto from it. The wallet's balance is simply the sum of the individual utxos' value.

Everything in this process is deterministic, what means that for a given set of keys and a set of transactions the utxo set is always the same no matter how many times we recompute it. These two things (script set + transaction set, equal to utxoset) are enough to answer all our questions simply because there isn't anything else. For example, to know whether a script is used or not we just need to look for it in the list of relevant output (spent + unspent outputs). This means that the number of relevant data structures is small and processing transactions to compute/update the utxoset is simple.

The utxoset is then no other thing that a convenient data structure (aggregate) that worth to be saved, otherwise we should rescan the whole blockchain again and again for every single action.

In the case of light wallets as Wasabi, we do not persist the utxo set but the relevant transactions that allow us to rebuild it. This makes sense basically because they are a few.

Buiding (and maintaing) other caches

While the number of scripts in our wallet grows, as well as the number of relevant transactions, answering questions by traversing transactions become slower. Using the uxtoset is faster but again not ideal. Fortunately everything is deterministically computed and that means it is safe to cache the result of those computations.

The question now is what to cache, what not to cache, what to persist and what not to persist, and why.

Caching (and persiting) the wallet public key sets

Wasabi caches the public keys and even when deriving 10,000 keys in a laptop takes a very few seconds (1.7 seconds in my laptop) this set is queried lots of times what makes caching it a good idea. However, why are we persisting the keys in a file? It is not for the labels by sure because given the keys are deterministically derived, it would be enough to save them as a (keypath, label) pair. It is not for the clean/used state because that is also deterministically determined during the transaction processing time. Is it for the locked state? nop.

Persisting the public keys and loading them with the wallet make all the keys to be known ahead of time in case of a resync, resulting on unnecessary false positive blocks to be downloaded and processed. As usual, for each problem there are two alternative solutions: remove the source of the problem or, add some extra complexity to solve it (and create even more problems). Anyway, in summary, caching pubkeys in memory makes a lot of sense but persisting them is at best unnecessary.

Caching utxos/keys metadata

In a imaginary wallet desinged without any caching other than the uxtoset, every question can be answered just by querying a couple of data structures, for example:

• Is $key_{1234}$ used? requires simply to look for the corresponding script in the utxoset.
• Is $coin_{e34af1...:0}$ banned? requires simply to look for it in the bannedcoins list.
• Is $coin_{e34af1...:0}$ replaceable? requires simply to look for the it in the inputs of the unconfirmed transactions marked as RBF.
• and so on.

In this imaginary wallet, given that there is not state to maintain, processing the transactions is simple. The wallet could be slow for wallets with long history (and it could be impossible to use after a point) but the code would be simpler by sure. On the other hand, in Wasabi the transaction processing algorithm is really complex, why? Because it has to maintain a couple of data structures all onsync, what is pretty hard to do well. These structures are: the keyset (keymanager), utxoset (coinregistry), relevant transactionset (transactionstore). Each of these play together and have to keep internal structures onsync too. For example, the transactionstore has to move transaction from/to mempoolstore and confirmedstore, the blockchainanalyzer has to update the keys' anonymityset and clusters, coinregistry has to keep also internal data structures for spent/unspent coins, coins by outpoints and so on.

One of the hardest problems

Cache invalidation is one of the hardest problems in programming, especially when it requires invalidating multiple caches that have to remain on sync all the time and which entries could have been manipulated by random parts of the code just for convenience. What happen with the anonymity set gained by a key once it is spent and then the spending transaction is replaced by a new transaction that doesn't include that key? who knows!

Every time a problem is solved by restarting or resync'ing your wallet, Well, you have hit a cache sync/invalidation problem and by restarting you are reconstructing everything from scratch.

State management

Imagine we need a mechanims for detecting transactions that "disappear" from the network (whenever that's possible or not, just imagine it). You detected that a coinjoin transaction that you've participated in was forgotten by the network, what shoud you do? Well, rollback everything, absoltely everything from removing the tx and all its descendant from the transaction store, set the keys used keys back to locked, remove the coins from the coinregistry and reintroduce the spent ones (do not forget to set the SpenderTransactionId back to null), reset the anonymityset of those received coins, unmerge the clusters, set the previous height for LatestSpendingHeight property, what else? do anyone knows? are you sure?

Flags

Flags are another kind of state which requires careful maintainance and synchronization that we should be aware of. Think about flags as HdPubKey::IsInCoinjoin, HdPubKey::IsBanned or similar. These are not cache items but they have to be "invalidated" somehow too. I will not explain the problem of this because I have already done that many many times but I think it is already clear why we should avoid adding these kind of "things".

NOTE: ## We have another problem with cache invalidation when for some reason (error conditions for example) they are never invalidated.

Caching the same thing in multiple places

In our imaginary wallet without any state other than the utxoset, knowing the spending state of a coin is easy: take a look at the utxoset. However, in a stateful wallet like Wasabi you can check the coinregistry (it keeys a list of spent coins) or check the SpenderTransaction property. Keeping these things synchronized can be really challenging.

As a partail conclusion we could say that more state requires more state management, more state management means more code and more code means more problems.

Avoiding state

As a rule we should avoid creating and maintaining more states. Some guidelines to decide:

• Things that never change can be cached.
• Things that never change and are expensive to get/compute should be cached.
• Things that can change and are trivial to recompute should never ever be cached.

Bitcoin is hard to change and the blockchain is costly to rewrite, for that reason there are many things that we can excpect to never change after they are crashed under a ton of PoW. I mean, imagine we don't want to cache the SmartCoin::IsSpent property, instead we want to have a method in the CoinRegistry for that, in that case we could assume that if the coin was spent more than 100 blocks ago then it is still spent.

public bool IsSpent(SmartCoin coin, Height tipHeight)
{
   if (spentCoinsCache.Contains(coin))
   {
      return true;
   }
   
   // Some heavy process here. 
   var isSpent = coins.SelectMany(c => c.CreatedByTransaction.Inputs).Any(i => i == coin.Outpoint);

   if (isSpent && coin.Height > tipHeight + 100)
   {
     spentCoinsCache.Add(coin)
   }
   return isSpent;
}

These kind of local cache that doesn't need to be invalidated are a cheap alternative to more global and frequently-updated structures.

Conclusion

Taking into account how complex the subject is, we are handling it surprisingly well. Sadly, we shouldn't overestimate our capacity and try to minimize the number of data structures that we have to maintain, otherwise we could find problems that could be really hard to solve soon.