rollkit / iavl

Merkleized IAVL+ Tree implementation in Go

IAVL+ Tree

Note: Requires Go 1.18+

A versioned, snapshottable (immutable) AVL+ tree for persistent data.

Benchmarks

The purpose of this data structure is to provide persistent storage for key-value pairs (say to store account balances) such that a deterministic merkle root hash can be computed. The tree is balanced using a variant of the AVL algorithm so all operations are O(log(n)).

Nodes of this tree are immutable and indexed by their hash. Thus any node serves as an immutable snapshot which lets us stage uncommitted transactions from the mempool cheaply, and we can instantly roll back to the last committed state to process transactions of a newly committed block (which may not be the same set of transactions as those from the mempool).

In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Whenever this condition is violated upon an update, the tree is rebalanced by creating O(log(n)) new nodes that point to unmodified nodes of the old tree. In the original AVL algorithm, inner nodes can also hold key-value pairs. The AVL+ algorithm (note the plus) modifies the AVL algorithm to keep all values on leaf nodes, while only using branch-nodes to store keys. This simplifies the algorithm while keeping the merkle hash trail short.

In Ethereum, the analog is Patricia tries. There are tradeoffs. Keys do not need to be hashed prior to insertion in IAVL+ trees, so this provides faster iteration in the key space which may benefit some applications. The logic is simpler to implement, requiring only two types of nodes -- inner nodes and leaf nodes. On the other hand, while IAVL+ trees provide a deterministic merkle root hash, it depends on the order of transactions. In practice this shouldn't be a problem, since you can efficiently encode the tree structure when serializing the tree contents.

iavl's Issues

Add deep trees for IAVL, for fraud proofs and stateless execution

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

Support Deletes in a Deep Subtree

Create deep tree structure using an ICS23-style approach: Updates

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

Add table-driven tests for each public method

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

Test Get operation in randomized tests

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

Add randomized tests for adding/removing keys

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.

Add initial root hash in Deep Subtree

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

Generate Witness Data in IAVL tree by tracing operations

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.

Support iterator operation in Deep Subtrees

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

Support Adds in a Deep Subtree

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.

Use Witness Data generated by IAVL tree in Deep Subtrees

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

Rebase Deep Subtree changes on top of a 0.19.x release

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.

Support Empty Hashes in Deep Subtrees

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.