Substrate vs Cosmos — Storage Deep Dive

1Patricia Merkle Trie (Substrate)
2━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
3Property          │ Value
4──────────────────┼──────────────────────────────────
5Type              │ Radix trie (compressed paths)
6Branching factor  │ Variable (2–16 children per node)
7Node types        │ 1 flexible type (partial_key + children + value)
8Path length       │ Varies by key similarity
9Ordering          │ Lexicographic on the raw key
10Self-balancing    │ NO — structure follows key distribution
11Node hash         │ Blake2b-256 (or Keccak-256, configurable)
12Empty slots       │ Not stored (bitmask marks used children)
13Merkle root       │ Hash of root node → 32 bytes

1IAVL Tree (Cosmos SDK)
2━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
3Property          │ Value
4──────────────────┼──────────────────────────────────
5Type              │ Immutable AVL (Adelson-Velsky-Landis) tree
6Branching factor  │ 2 (binary tree)
7Node types        │ 2: inner nodes + leaf nodes
8Path length       │ O(log₂ n) — guaranteed balanced
9Ordering          │ Sorted by key (BST property)
10Self-balancing    │ YES — rotations on every write
11Node hash         │ SHA256
12Empty slots       │ N/A (binary tree has exactly left + right)
13Merkle root       │ Hash of root node → 32 bytes
14Versioning        │ Every write creates new nodes; old nodes kept

1// Every key in Substrate is built from 3 parts:
2
3final_key =
4  Twox128("PalletName")          // 16 bytes — non-crypto hash of pallet name
5  ++ Twox128("StorageItemName")  // 16 bytes — non-crypto hash of storage item  
6  ++ KeyHasher(actual_key)       // 16-32 bytes — depends on storage type
7
8// Example: Balances pallet, Account storage map, for Alice:
9final_key = 
10  Twox128("Balances")            = 0x26aa394eea5630e07c48ae0c9558cef7
11  Twox128("Account")             = 0xb99d880ec681799c0cf30e8886371da9
12  Blake2_128Concat(Alice_pubkey) = 0xde1e86a9a8c739864cf3cc5ec2bea59f...
13
14// KEY PROPERTIES:
15// ✅ All Balances.Account entries share the same 32-byte prefix
16// ✅ Scanning all accounts in a pallet = prefix scan (very fast)
17// ✅ Cache-friendly: related data lives near each other in RocksDB
18// ❌ Key is opaque if you don't know the pallet/storage structure

1// Cosmos SDK uses a KV Store abstraction per module
2// Each module gets its own isolated KV namespace
3
4// Store key for Cosmos bank module:
5prefix = "bank/"   // module name as ASCII string prefix
6key    = "balances/cosmos1abc..."  // human-readable path
7
8// In the IAVL tree, the actual stored key is:
9iavl_key = prefix + key
10         = "bank/balances/cosmos1abc..."
11
12// The IAVL tree sorts keys lexicographically (BST property)
13// So all "bank/" keys are sorted and adjacent in the tree
14
15// KEY PROPERTIES:
16// ✅ Human-readable keys — easier debugging
17// ✅ Module isolation — each module's keys are contiguous
18// ✅ Natural range scans (sorted BST)
19// ✅ IBC proofs use full key path for cross-chain verification
20// ❌ Variable-length keys complicate some optimizations
21// ❌ No hashing on keys — prefix collision if not careful

1// IAVL is "immutable" — nodes are never modified in-place
2// Every write creates new nodes; old nodes remain in DB
3
4// Block 100: Alice has 100 ATOM
5root_100 = NodeHash {
6  left: NodeHash(Alice → 100),
7  right: NodeHash(Bob → 50)
8}
9
10// Block 101: Alice sends 10 ATOM to Bob
11// New nodes created for changed path; old nodes stay intact
12root_101 = NodeHash {
13  left: NodeHash(Alice → 90),   // NEW node
14  right: NodeHash(Bob → 60)     // NEW node
15}
16
17// Block 100 root_100 still exists in the DB!
18// You can query:
19iavl.GetVersioned(100, "balances/alice")  // returns 100 ATOM
20iavl.GetVersioned(101, "balances/alice")  // returns 90 ATOM
21
22// This is how Cosmos light clients work:
23// A validator can prove historical state without extra tooling
24// This is CRITICAL for IBC (cross-chain message verification)

1// Substrate does NOT version the trie by default
2// State is updated in-place (old nodes overwritten or deleted)
3
4// To get historical state, you need an ARCHIVE NODE:
5// Archive nodes keep all old state in a separate "state database"
6// They're much larger and slower to sync
7
8// Substrate's approach:
9// - Full node: keeps only recent state (prunable)
10// - Archive node: keeps all state (like Cosmos always does)
11
12// Substrate's TrieBackend:
13let backend = TrieBackend::new(storage, root);
14// "root" is the state root of a specific block
15// You can query historical state IF you have the archive
16// But the trie itself doesn't store old nodes natively
17
18// The advantage:
19// Full nodes are MUCH smaller (Substrate node: ~50-200GB vs Cosmos ~800GB+)
20// The disadvantage:
21// Historical queries require archive nodes or external indexers

1// Reading Balances.Account[Alice]:
21. Build key: Twox128("Balances") ++ Twox128("Account") ++ Blake2_128Concat(alice)
3   → fast (Twox is non-crypto, ~5ns per call)
4   
52. Look up in TrieBackend overlay (in-memory cache first)
6   → if hit: return immediately (sub-microsecond)
7   
83. If miss: traverse Patricia trie from current state root
9   → follow partial_key path through nodes
10   → each node: RocksDB read + SCALE decode
11   
124. Return SCALE-encoded value, decode on client side
13
14// Performance characteristics:
15// - Structured keys → high cache hit rate for related keys
16// - SCALE decode is fast (no schema lookup needed)
17// - Path length: bounded by key diversity
18// - Typical reads in a block: 95%+ come from overlay (RAM)

1// Reading bank.balances[alice]:
21. Look up in current version IAVL (in-memory working set)
3   → IAVL keeps the "working tree" in memory
4   → if hit: O(1) return
5   
62. If not in working set: traverse IAVL from root
7   → binary BST traversal: left or right at each inner node
8   → each node: RocksDB read + decode
9   → O(log₂ n) steps: for 1M entries = ~20 steps
10   
113. Return value (Protobuf-encoded), decode with generated code
12
13// Performance characteristics:
14// - O(log₂ n) guaranteed (balanced AVL)
15// - In-memory IAVL for current version = very fast for hot data
16// - SHA256 hash verification at each node (CPU cost)
17// - Binary tree = more levels than Patricia (for same data)
18// - Historical reads: fast (just use getVersioned() API)

1// Substrate write flow during block execution:
2//
3// 1. All pallet storage writes go to OverlayChangeset (RAM)
4//    → Zero disk I/O during block execution
5//
6// 2. At end of block: compute new state root
7//    → Traverse changed nodes in overlay
8//    → Blake2b-hash each changed node
9//    → Propagate hashes to root
10//
11// 3. Commit to RocksDB in one batch write
12//    → RocksDB batching is extremely fast
13//    → One fsync call instead of one per write
14
15// Example: 5000 state changes in one block
16// Substrate: 0 DB reads, 0 DB writes during execution
17//            1 batch DB write at block end (~10-50ms)
18//
19// Overhead per write: ~1 Blake2b hash + node re-encode (SCALE)
20// Blake2b: ~3-5ns per byte → very fast

1// Cosmos write flow during block execution:
2//
3// 1. Writes go to IAVL working tree (in-memory IAVL)
4//    → IAVL modified in memory → no disk I/O yet
5//    → BUT: AVL rebalancing happens in memory immediately
6//
7// 2. At end of block: Commit the IAVL
8//    → SaveVersion() called on the IAVL
9//    → New nodes written to RocksDB (old nodes kept!)
10//    → Every changed path = new nodes from leaf to root
11//
12// 3. SHA256 hashed at each node up the tree
13
14// Example: 5000 state changes in one block
15// Cosmos: 0 DB reads during execution (in-memory IAVL)
16//         ~5000-15000 new DB entries (write amplification from
17//          immutable nodes + path re-creation)
18//         SHA256 at each modified node = expensive CPU
19//
20// Additionally: IAVL rebalancing rotations on insert/delete
21// (see next section for full rebalancing cost analysis)

1// AVL Rotation Example (conceptual):
2//
3// BEFORE inserting key "D":
4//         B
5//        / \
6//       A   C
7//
8// After inserting D (tree becomes right-heavy):
9//         B
10//        / \
11//       A   C
12//             \
13//              D    ← Height diff = 2, UNBALANCED
14//
15// LEFT ROTATION at B:
16//         C         ← C promoted to root
17//        / \
18//       B   D
19//      /
20//     A
21//
22// In IAVL (immutable): B, C are NEW nodes in DB
23// Old B and C remain (for historical version)
24// Result: 2 writes for the old nodes + 2 writes for new = 4 writes
25//         for what is logically 1 insert
26
27// In Substrate Patricia Trie: NO rotation ever
28// Insert D: just add a new node at the correct position
29// 1 logical insert = ~1-2 actual node writes

1Scenario: 1,000 state updates in one block
2
3SUBSTRATE PATRICIA TRIE:
4  Logical writes:      1,000
5  Actual node writes:  ~2,000–4,000  (2-4× amplification)
6  Hash operations:     ~2,000–4,000  (Blake2b, ~5ns each)
7  Rotation events:     0
8  Estimated time:      ~10-30ms
9
10COSMOS IAVL (v1):
11  Logical writes:      1,000
12  Actual node writes:  ~5,000–12,000 (5-12× amplification from
13                         immutability + rotations)
14  Hash operations:     ~5,000–12,000 (SHA256, ~25ns each)
15  Rotation events:     ~200–400
16  Estimated time:      ~50-150ms
17
18COSMOS IAVL (v2, 2024):
19  Actual node writes:  ~3,000–7,000  (improved caching)
20  Estimated time:      ~25-80ms      (2-3× faster than v1)
21
22Note: Times are approximate and vary by hardware, state size,
23and specific workload. Source: Cosmos engineering blog, 
24informal.systems benchmarks, Osmosis state analysis.

1// IBC message proof flow (simplified):
2
3// Chain A sends a packet to Chain B:
4// 1. Chain A commits the packet in its IAVL state
5// 2. Relayer queries Chain A: "give me proof that packet P exists at height H"
6// 3. Chain A returns: iavl.ProveExistence("ibc/packets/channel-0/1", height=H)
7//    → Returns: [inner_node_hashes, leaf_data, version=H]
8// 4. Relayer submits proof to Chain B
9// 5. Chain B's light client verifies:
10//    → Uses Chain A's trusted block header (root hash at height H)
11//    → Reconstructs hash from proof → matches root → VALID
12
13// Without versioned state (like Substrate without archive):
14// Step 3 fails if height H is pruned from the node
15// → Requires archive infrastructure for reliable IBC
16
17// This is why Cosmos chose immutable IAVL despite the write cost:
18// The versioning is REQUIRED for IBC light client security