This should be done in a separate branch eg (deepiavl), as we shouldn't assume this will be merged into iavl upstream.

How to add deep trees:

1. Add a DeepTree (deep_tree.go) that inherits or extends MutableTree
2. Modify this Verify function and the functions it calls to add a DeepTree instance as an (optional) parameter, all the way down the stack into computeRootHash
3. In pathWithLeaf.computeRootHash and pathToLeaf.computeRootHash, every time a hash for a leaf or a node is computed, add it to to the nodeCache in the nodeDB of the MutableTree of the DeepTree (or your own custom cache/map), by creating new Node() object with nil left and right nodes
4. After a range proof is verified with Verify(), DeepTree should loop through all the the entries in nodeCache to populate Node objects with pointers to their respective left and right Node objects, where available (you can also do this step inside computeRootHash instead of doing it after, as well)
5. You can now call Set() in MutableTree with the root node to update values in the deep tree (you'll need to set the ImmutableTree's root first), and call Hash() in MutableTree's ImmutableTree to get the root hash

Tracking:

• #2
• #6
• #12
• #15
• #14
• #19
• #20
• #21
• #22

Reference comment: #8 (comment)

We'd like to add randomized tests for Set and Remove that add new keys and delete existing keys respectively. Mainly, we'd like to make sure that Deep Subtrees are constructed with all the data they might need to rebalance correctly when new keys are added or existing keys are removed.

Light fuzzing in the tests might be useful as well.

Suggested tests:

• Batch-add random keys.
• Randomize both the operations, Set and Remove, and the keys they are operating on so calls to both are interleaved together in no particular order.

Make sure the tree rebalances correctly at each stage (check against existing IAVL tree: mutable tree).

Overall, the goal of this issue is to have strong substantial tests for an IAVL Deep Subtree.

We'd like to be able to load Witness Data generated in #19 in a Deep Subtree and later on be able to perform all operations recorded in the Witness Data.

When an operation is performed on the Deep Subtree, it should first check that the operation matches the current operation in the Witness Data that hasn't been performed. Also, we should verify all the existence proofs inside the Witness Data to make sure they match up with the root hash of the Deep Subtree at any point.

Parent issue: #19

We would like to support empty tree roots in a Deep Subtree in conformance with RFC-6962

See: https://github.com/celestiaorg/iavl/blob/07d15352ad09d0c1fd7f616f1e53c2fc88b89185/node.go#L267

This is needed in order to support store keys that are not used while making a fraudproof in cosmos-sdk.

We'd like to add table-driven tests for each new method in IAVL deep subtrees and check it against a full IAVL tree.

We'd like to support iterator operations in a deep subtree since they can be used by a cosmos-sdk multi-store.

We'd like to add tracing for keys accessed in the IAVL tree along with the operation itself during the following operations:

• Set
• Get
• Remove

For each operation above, the keys accessed should be used to generate the existence proofs needed for performing the said operation.

Overall, after performing a bunch of operations, an IAVL tree should have the following struct inside it to record all the operations and existence proofs required for each operation:

type WitnessData struct {
	Operation Operation
	Key       []byte
	Value     []byte
	Proofs    []*ics23.ExistenceProof
}

Also, add an option to enable/disable tracing in an IAVL tree.

In current fuzzing tests, we only test Set and Remove. We'd also like to test the Get operation for deep subtrees.

A Deep Subtree should be able to be initialized with an initial root hash since the root is set to nil for an empty Deep Subtree. However, if a non-nil root exists in the Deep Subtree, it should have priority over the initial root hash and the working hash of the Deep Subtree should be used as the root hash.

Add setters and getters for initial root hash along with using it in verifyOperation and buildTree.

Parent issue: #20

The current deep subtree changes are made on top of a branch forked off of an IAVL version before the dragonberry exploit took place. We want to rebase these changes on top of a newer version post dragonberry fix.

Create a Deep Subtree structure that supports value updates of existing leaf nodes using their key

Steps:

• DeepTree structure is introduced
• Nodes can be added to the underlying NodeDB of a DeepTree
• Tree structure is properly linked (by pointers in Node objects) using NodeDB
• Root of underlying ImmutableTree is set properly
• Override Set to support value updates of existing leaf nodes using corresponding keys
• Write unit tests that test value updates. Example here: https://ethresear.ch/t/data-availability-proof-friendly-state-tree-transitions/1453/23

We need to support adds in a Deep Subtree, because a transaction being fraud-proven may add keys.

Description of how to do it here: #1 (comment)

Note that there is extra data that needs to go into the proof for this in order to allow IAVL to have the data it needs to do rebalancing.