zcash_client_backend: Use knowledge of inserted treestates to reduce time to spendability

[nuttycom]

In order to minimize the amount of scanning work required at the chain tip, we should implement the following:

• Add a priority that is higher than ChainTip, call it AnchorRange or something of the sort. The semantics of an AnchorRange scanning range are that when a wallet encounters such a range, it immediately downloads the treestate corresponding to the last block prior to the start of the range and inserts that frontier directly into the note commitment tree (using a to-be-defined WalletCommitmentTrees method).
• After updating scan ranges, the following must hold:
  • the AnchorRange scanning range is at most PRUNING_DEPTH blocks long and has its end equal to the chain_tip + 1
  • any previously existing AnchorRange range with a starting height < stable_height has its priority reduced to Historic
  • if the the shard containing stable_height has no unscanned ranges below stable_height, no AnchorRange must exist, because in this case it's unnecessary to download or insert any additional tree state.

It might be possible to repurpose the ChainTip priority to have these semantics, but I think it's better to be explicit about the circumstance where the tree state should be downloaded, and we should continue to support wallets that don't want to download tree states; such wallets will treat AnchorRange ranges in the same fashion as they currently treat ChainTip ranges.

[str4d]

Do we even need to modify the scan ranges? This feels like it is trying to shoe-horn additional semantics or signals into suggest_scan_ranges, that complicate it over "scan these ranges in priority order".

The need to obtain a tree state at the anchor height is associated with a change to the chain tip height. We could therefore instead modify update_chain_tip to return metadata that includes "height at which the wallet should be given a tree state to make its desired anchor spendable". If the caller ignores that metadata, then they continue to work correctly because they scan ChainTip.

[nuttycom]

The need to obtain a tree state at the anchor height is associated with a change to the chain tip height. We could therefore instead modify update_chain_tip to return metadata that includes "height at which the wallet should be given a tree state to make its desired anchor spendable". If the caller ignores that metadata, then they continue to work correctly because they scan ChainTip.

We'll have to keep track somewhere of the fact that we've been given the tree state & combine the information about that latest-provided-tree-state with information about scan ranges. We'll need this whichever way we do it, so I guess that just keeping ChainTip could work, because what we really want to know is that there are no unscanned ranges (of whatever priority) between max(anchor_shard_start, downloaded_tree_state_position)

[str4d]

Yeah, when a treestate at a specific height is provided, we could look at the height and if it intersects a ChainTip range then we can alter that range to deprioritise it or subdivide it as necessary.

[nuttycom]

A couple more insights:

This change will mean that we can no longer use whether or not a subtree is completely scanned as a condition for determining whether a note is spendable. Instead, we will likely want to store an extra piece of shard metadata, which is the height in the shard above which it's possible to build a witness.

[daira]

Is scanning work at the chain tip actually a bottleneck? I would have thought that it's desirable to always scan the chain tip when we see new blocks, and that it takes very little time in the steady state. (If the database reopening on each FFI call is why it's taking a significant time, then that's what we should address, rather than adding complexity elsewhere.)

[nuttycom]

In my experience with Zashi, it can take more than a minute, sometimes even several minutes, to scan enough blocks to fill up the 2^16 notes in the tip shard; 2^16 notes is still ~0.1% of the chain, and in sparse block periods that can be weeks worth of blocks.

[nuttycom]

I want to generalize this task to "the wallet downloads the tree state corresponding to the previous block for every one of the user's notes that is discovered, and inserts this tree state into the note commitment tree". This doesn't reveal any information to the lightwalletd server that fetching the memos doesn't already reveal.

This would make it so that blocks prior to the discovered note could be downgraded to Historic scanning priority. Changes to the note selection logic would be required to make these notes selectable without having to scan the previous blocks in the subtree (the blocks within the subtree following the one containing the received note would still have to be scanned, but this could be further optimized by skipping trial decryption and just doing commitment tree updates.)

[nuttycom]

After #1262 we have the treestates downloaded and inserted for every block range, so we just need to ensure that the scan queue logic can take advantage of them by deprioritizing the range prior to the first tree state for one of our notes in a block.

[str4d]

A relevant change for this issue is to alter the FoundNote ranges to not include blocks prior to the treestate that was inserted as part of the scan range that the note was found in, because per above we provably do not require it. For wallets that are scanning in reverse (e.g. #913) this would enable them to scan other ranges that might be more immediately useful rather than the beginning of the subtree in which the note was found.