feat(grandfather): Snapshotted trees

[LHerskind]

The power of the grandfather lies in reading from many different blocks in the same transaction. However, this is a true pain if the trees are not snapshotted, since you effectively need what behave as an Ethereum archive node where you can look up paths of a specific version of the note-hash and other trees.

Without snapshotting you will practically just be using the last block always. Need to figure out how state snapshotting can happen, and make it simple devex, similar to including a param with the block you want to query at.

[benesjan]

Here is how we could do this:

1. Snapshot approach
Snapshot the whole DB at each n-th block and then replay the state changes to get to the desired block.

E.g. every 5 blocks we would copy the DB and then we would replay the changes if we need to. So if I requested a sibling path of a leaf at block 8, I would get the db at block 5 and apply changes to it from block 6, 7 and 8. These changes are stored in the archival node so it shouldn't be that hard. Advantage of this approach is that it's quite simple but a big disadvantage is that it results in a lot of storage.

2. Storing-changes approach
With each new block, store only the changed nodes of the tree. Currently we store the trees in a flat structure (key-value map). In this structure each node of the db is under a key which consists of (tree_name, level, index).

What we could do is expand this key with block number so (tree_name, level, index) would become (tree_name, block_number, level, index).

But this begs a question of how would we figure out at would blocks each node was changed upon sibling path retrieval. That is, if I want to fetch a leaf at index 6 and its sibling path at block 10 how would I determine which keys to use?

2.1 Append-only tree
For the append-only tree this can be done very efficiently. This is especially true when we are inserting blocks of fixed sizes - fixed amount of new leafs. In a scenario of the fixed block size I can determine at what block the particular leaf was inserted just from its index. Having this information I can quite easily determine at what block all the nodes in the leaf's sibling path have changed as well. This achieves optimal results when it comes to storage requirements.

2.2 Sparse tree
For the sparse tree this is way more tricky because what nodes have changed at what block is essentially random. For this reason, along with the node value information stored under the (tree_name, block_number, level, index) key, we would also need to store the information at what blocks each leaf and node has changed. I would use bitmap to store this information and a positive bit would represent a change at the given block. In each bitmap I would store changes corresponding to 256 blocks (32 bytes of info). Given that in the sparse tree most nodes are empty I would also store a [(tree_name, level, index) --> bool] map indicating whether the node was ever set.

Bellow is an example flow of how fetching a leaf and a sibling path would work when trying to get a leaf at index 9 at block 259.

1. is non_empty_node_map(sparse_tree_1, bottom_level, index_9) empty? - NO
2. get change_bitmap for blocks from range 257 - 512 (both indices inclusive, first block with block number 1)
3. search back from block 259 and find at which block the node was last changed - leaf changed at block 259? - NO, 258? - NO, 257? - NO
4. get change_bitmap for blocks from range 1 - 256 and search back from block 256.
5. once you find the block in which the leaf changed get the leaf value at (sparse_tree_1, change_block_number, bottom_level, index_9)
6. Perform steps 1-5 for each node in the sibling path.

It's quite likely that the search back could be performed very efficiently using bitwise operations.

Overall I think it doesn't make sense to go with approach 1. because it's too inefficient, replaying can be tricky, and approach 2. is not that hard to implement. I think for the append-only tree the approach is quite elegant but I have doubts about the sparse tree. If someone is aware of a better way how to do this LMK.

I looked at what Erigon is doing and their optimization seem to be too low-level and hence irrelevant for sandbox. Here are their docs for anyone curious.

@iAmMichaelConnor we have a nice problem here which is blocking quite a lot of stuff 😆

[LHerskind]

Not sure we actually need a lot of input from @iAmMichaelConnor since this is more a implementation "detail" than something that changes the protocol. Essentially how do we store it efficiently for our case, but it don't change much in the protocol itself.

I think going with solution 1 might be fine for the sandbox, where the lifetime of the chain is somewhat limited, so the data that we need to store for each snapshot is not huge. When we are talking kb/mb of storage, it seems like a no-brainer to me as it should be possible to do quite quickly (I say naivly).

Since our nullifier updates are also quite funky from the tree view, it seems like spending a lot of engineering power here now is over-engineering 🤷.

For a production note, it would be horrible to do this, but I think it is workable here.

For solution 2, it sounds like you essentially end up with something that is like a dynamic predecessor problem? (Predecessor problem, finding the largest element $S$ that is $\le x$ where $S$ is a subset of the universe of elements $U$) In our case, find the newest set of notes $S$ that is the subset of the state $U$ with the freshest elements at time $x$. Might make sense to look at translating it if what I say make a bit of sense, then should be possible to use Y-fast tries or van Emda Boas 🤔 @benesjan

[iAmMichaelConnor]

Fun problem! I love implementing tree stuff!

An interesting future enhancement would be to enable a pxe to subscribe to hash path changes (each block) for the notes in the user's db. E.g. if a user owned a note, they could subscribe to the hash paths of the "low nullifier(s)" which 'jump over' that note's nullifier. This would allow a user to prove "this note wasn't nullified yet, in historic block b", without having to run an archive node.
Maybe it's too niche a use case, but would be cool.

[alexghr]

I think an alternative would be to store the tree nodes in the database as content-addressed entries (e.g. like pointers in memory) where the key is the actual value (hash) of that node and the value of the entry is a tuple of the two children that make up the node.

This would allow us to structurally share subtrees between different blocks (e.g. if something changes only the right subtree then the new root can point to the old left-subtree and the new right-subtree).

Getting the value of a leaf at a particular index at a particular block number comes down to traversing the tree down from the root (conveniently this would also give us the merkle path). To get the root of a subtree we could hold known references, e.g. "contracts_tree:block_5:root" => 0x123. These references could be updated in place if a block reorganisation happens.

Example with an append tree

Initially the tree and database are both empty (don't store null hashes)

Appending a to the tree would insert 4 new nodes and a reference for the current block

Appending b would against insert 4 new nodes but that's because the tree for the previous block still has references to the old values. The a entry in the database would be shared would be shared by both trees.

This becomes much more efficient with batched inserts because in the database we only need to keep the end state of the tree for each block.

Sparse tree

This would work the same way for sparse trees.

I'll have a think about how much storage this approach would take in the database.

WDYT?

[LHerskind]

WDYT?

I quite like it. Think it have similar performance to the ideas from @benesjan with append-only, but for sparse and nullifier trees it might go crazy with nodes to be updated.

I think we can could use it as the base idea of the trees, but would probably still need something like the store only every n to keep the disk usage down, and then replaying the changes of a few blocks if needing to compute something that is not in store already.

[alexghr]

we'll prune the branches old trees

[alexghr]

I think for an append-only tree the only thing that needs to be stored per snapshot is up to which index we've written leaves to. Since the tree only ever grows by adding leaves and historic values never change, we just have to check if a leaf's index was set at a particular block number (ie leaf index < max leaf index at block) and maybe the tree root for good measure. Am I missing something? This sounds really cheap and efficient.

Merkle proof would be a bit more involved though since we can't compute it on the most recent tree.

[LHerskind]

Merkle proof would be a bit more involved though since we can't compute it on the most recent tree.

The reason we want the snapshots is to get the sibling paths for merle inclusion proofs such that we can prove that they were part of historic state.