Save roots of complete 2^16 subtrees within the Sapling commitment trees

[str4d]

In order to use shardtree efficiently in a mobile client, lightwalletd needs to be able to supply it with information about roots of 2¹⁶ subtrees within the commitment tree. We need zcashd to store this information.

Currently, zcashd stores an IncrementalMerkleTree state as of the end of every block. This is a tree frontier, onto which new leaves can be appended to move the frontier forward, but that does not store any information allowing leaf removals.

We only need to store the roots of the 2¹⁶ subtrees:

• Smaller subtrees will be reconstructed by fetching the stream of note commitments within the subtree, which is at most 2MiB of leaf hashes (plus metadata).
• Larger subtree roots can be constructed from the 2¹⁶ subtree roots, which is at most 2MiB of hashes.

Additionally, because this is at most 2MiB of data, and we'll want it for the internal Orchard wallet eventually, we will just collect these roots for all nodes (not just when the -lightwalletd option is specified).

• When a block append causes a subtree to be completed, zcashd should store:
  • The index of the subtree.
    • Zero-indexed from the left; this can be derived from the position of any leaf within the subtree.
  • The root of the subtree
  • The height of block that completed this subtree
    • Either the position of the frontier at the end of the block is precisely on the 2¹⁶ subtree boundary (the last leaf appended is part of the subtree), or it is somewhere within the next subtree (as a block is not large enough to contain sufficient note commitments to cross multiple 2¹⁶ subtrees).
• When a block rewind uncompletes a subtree, we should remove its root from the coins DB.
• On start, when the coins DB is loaded, if there are no stored roots, scan the commitment tree frontiers stored in the coins DB from Sapling activation, finding the 2¹⁶ roots (by observing when the hash at position 16 changes across a block boundary), and storing them in the database.