# Large capacity Sparse Merkle trees Currently, our Sparse Merkle tree implementation (i.e., the `Smt` struct) has a purely in-memory representation. This will work fine when the amount of data stored in the tree is dozens of GB, but will break down when we'll need to store hundreds of GB in an `Smt` (as we may need for the nullifier and account tree in the Miden rollup). The purpose of these improvements would be to develop an approach which implements a variant of our `Smt` struct (ideally, with very similar interface) which can efficiently accommodate up to several terabytes of data inserted into it. ### Performance goals Main metric we'd like to optimize for: - RAM footprint: ideally, the in-memory part of the tree should not require more than 16 GB of RAM regardless of the underlying tree size. - Opening speed: time to build a Merkle path for a given leaf should be under 100 µs (currently, under 1 µs). - Update/insert speed: time to update/insert a batch of 10,000 leaves should be under 1 second on a 16-core CPU (currently should be under 300 ms). - Tree initialization: time to load the in-memory part of the tree should be under 1 minute on a 16-core CPU regardless of the underling tree size. - Disk footprint: this is difficult to for me to estimate as I don't have any intuition here. A potential target to throw out is that an SMT with 1 billion key-value pairs should require something between 100GB and 1TB of disk space. The implementation should be crash-tolerant - e.g., terminating a process while an update is in progress should not corrupt the underlying data structure. ### Some design ideas - We could load the top of the tree (e.g., top 24 levels) into memory as a fully-materialize binary tree. This should make traversing this part of the tree very fast (faster even than our current implementation). - The rest of the tree could be stored on disk - either directly or using some high-performance in-process database. - To reduce disk footprint, we could keep some number of bottom levels as "virtual" - but this would also make opening/insertion speed a bit slower. Some literature on the subject: - [Nearly optimal state merkelization](https://sovereign.mirror.xyz/jfx_cJ_15saejG9ZuQWjnGnG-NfahbazQH98i1J3NN8). - [Sparse Merkle tree](https://ouvrard-pierre-alain.medium.com/sparse-merkle-tree-86e6e2fc26da) from AERGO.