Store Sapling & Orchard note commitment trees in finalized and non-finalized state

[conradoplg]

Motivation

For #3156 we need to be able to return a Sapling & Orchard tree state (a note commitment tree, represented as a frontier, like we already do) for multiple block heights. However, while we do store the Sprout trees for every height, for Sapling and Orchard we only store it for the finalized tip (and also for non-finalized tips, in memory).

ZecWallet Lite expects to have a tree state for every block from Sapling or Orchard activation, for good performance on first use.

We don't need to store them for every height since z_gettreestate supports a skipHash return value that requests the caller to look up a tree in a previous height. But we do need to store them every X blocks for some value of X.

Designs

• Change the sync to store all the Orchard & Sapling note commitment trees in the finalized and non-finalized state. This will require a database version bump.

Follow Up Tasks

Optimisation:

• De-duplicate note commitment trees in the finalized and non-finalized state #3757

[ftm1000]

Hey team! Please add your planning poker estimate with ZenHub @conradoplg @dconnolly @gustavovalverde @jvff @oxarbitrage @teor2345 @upbqdn

[teor2345]

Aditya told us that ZecWallet requires every block's tree state for good performance. This will cost us about 1.5 GB for Sapling.

[upbqdn]

Should the note commitment trees be included in the non-finalized state as well?

[conradoplg]

Should the note commitment trees be included in the non-finalized state as well?

I think so, since the non-finalized blocks can be queried too

[upbqdn]

Note: We store and query Sprout note commitment trees by anchors, not heights. I updated the description of the issue so that it reflects this.

Since #3156 will query the note commitment trees by heights, we will have to have two more column families in the database: sapling_note_commitment_tree_by_height and orchard_note_commitment_tree_by_height. Similarly, for the non-finalized state, the Chain structure will have two more members. I will use the same names for those.

I'm not going to include the Sprout note commitment trees because lightwalletd doesn't require them.

[teor2345]

Since #3156 will query the note commitment trees by heights, we will have to have two more column families in the database: sapling_note_commitment_tree_by_height and orchard_note_commitment_tree_by_height. Similarly, for the non-finalized state, the Chain structure will have two more members. I will use the same names for those.

It looks like we already store sapling and orchard trees by height in the finalized state?
(But we delete every height except for the latest height.)

https://github.com/ZcashFoundation/zebra/blob/main/book/src/dev/rfcs/0005-state-updates.md#rocksdb-data-structures

zebra/zebra-state/src/service/finalized_state/zebra_db/shielded.rs

Lines 260 to 270 in 699c062

	self.zs_insert(
	sapling_note_commitment_tree_cf,
	height,
	note_commitment_trees.sapling,
	);
	self.zs_insert(
	orchard_note_commitment_tree_cf,
	height,
	note_commitment_trees.orchard,
	);

[teor2345]

I split out this optimisation task, because it's optional:

• De-duplicate note commitment trees in the finalized and non-finalized state #3757

But we might need it to get better performance.

[upbqdn]

I realized I forgot to mention this issue in the corresponding PR, so it didn't get closed. Should we close this?

[conradoplg]

I realized I forgot to mention this issue in the corresponding PR, so it didn't get closed. Should we close this?

Sure! I linked the PR and I'm closing this