Versioned Merkle Tree

RISE employs a much more storage-efficient Versioned Merkle Tree. Versioned Merkle Trees use a version-based node key so all keys are naturally sorted on insertion. This minimises the compaction cost of the underlying key-value storage. Versioned trees also enable robust and efficient historical queries and proofs.

A popular Versioned Merkle Tree is the Jellyfish Merkle Tree (JMT) designed for Aptos. While JMT minimizes key-value storage compaction with versioned node keys, it still uses a general-purpose RocksDB with high write amplification, and compaction is triggered during pruning.

To address this, we adopt the LETUS approach, replacing the two-layered storage architecture with a streamlined one. Tree updates are delta-encoded, and key-value pairs are stored in log-structured files (not trees) to minimize read and write amplification.

We also experiment with ideas from NOMT, lowering the radix of the Merkle tree to reduce merkelization complexity. For the increased read complexity, we use an optimal on-disk representation to parallelly fetch all sub-trees for a key in one SSD roundtrip. NOMT can reduce to binary as each node is only 32 bytes, but this doesn’t apply to Versioned Merkle Trees due to the extra version storage. We also store the offset and value size to index the value in the log-structured files. The final design could be an 8-ary tree to balance read and write amplification.

This structure reduces read/write amplification from high-latency disk storage and improves overall system performance. It allows RISE to process hundreds of thousands of transactions per second while managing the rapidly growing state efficiently.