Core

Sparse Merkle Trees in Oracle State Synchronization: The Mathematical Necessity Beyond Choice

4 Oct 2025 · 17 min read

In particular, we present mathematical proofs demonstrating how Merkle Patricia Trie’s (MPT) path compression creates non-deterministic tree structures during state merging, and how variable depth makes consistency guarantees impossible in cross-chain verification. This reveals that Oraclizer’s adoption of SMT was not merely a technical stack selection, but the only viable path to achieve state synchronization.

TL;DR

The data structure for complete state synchronization is not a matter of choice but mathematical necessity. An oracle state machine managing bidirectional state flows across on-chain, off-chain, and cross-chain domains requires a data structure that satisfies three essential properties: concurrent processing, sparsity representation, and deterministic verifiability. We prove that these properties precisely align with the structural characteristics of Sparse Merkle Trees (SMT): fixed depth, sparse property, and O(log n) complexity. In particular, we present mathematical proofs demonstrating how Merkle Patricia Trie’s (MPT) path compression creates non-deterministic tree structures during state merging, and how variable depth makes consistency guarantees impossible in cross-chain verification. This reveals that Oraclizer’s adoption of SMT was not merely a technical stack selection, but the only viable path to achieve state synchronization.


Introduction: Beyond Data Structure Selection

Data structure selection is sometimes viewed as an engineering trade-off, a practical judgment balancing performance and memory, complexity and flexibility. However, in the context of oracle state synchronization, what we faced was not a matter of choice. It was the discovery of mathematical necessity.

In early 2024, during the design of Oraclizer’s core architecture, we confronted a fundamental question: “How do we consistently synchronize states distributed across on-chain, off-chain, and multiple blockchains?” This seemingly simple question, as we delved deeper, revealed fundamental limitations of existing blockchain data structures.

The Merkle Patricia Trie (MPT) adopted by Ethereum demonstrates excellent performance in single-chain state management. Space efficiency through path compression, theoretical O(log n) complexity, and verifiable state transitions: MPT seemed like the standard for blockchain state management. However, what we aimed to implement was not single-chain state management. Before concurrent processing of state changes from multiple sources, efficient representation of mostly empty state space, and deterministic verifiability in cross-chain environments (these three requirements), MPT revealed its structural limitations.

This article chronicles our months-long research journey. This is not simply a comparative analysis claiming “SMT is better than MPT.” We derive the essential properties required by the purpose of state synchronization, prove the mathematical conditions that data structures must satisfy, and demonstrate why MPT structurally cannot achieve this. Finally, we reveal that SMT is the only structure satisfying all these conditions.


Essential Properties Required by State Synchronization

The Nature of Oracle State Flows

To understand the fundamental challenge faced by state synchronization oracles, we must first model the nature of state flows.

Traditional blockchain oracles are optimized for unidirectional data transfer: off-chain source → on-chain contract. However, complete state synchronization must manage multidimensional state flows such as:

$$\begin{aligned} &\text{DAML Contract State} \leftrightarrow \text{Ethereum State} \\ &\text{External API State} \rightarrow \text{L3 Registry} \\ &\text{Arbitrum State} \leftrightarrow \text{Base State} \leftrightarrow \text{Polygon State} \end{aligned}$$

These multi-domain state flows inevitably require three essential properties.

Property 1: Concurrent State Change Processing

When state change requests arrive nearly simultaneously from multiple sources, the system must prevent double spending and state conflicts.

Assume three state changes occur simultaneously at time t for the same asset:

  • On Ethereum: \(s_1 \rightarrow s_1'\) (collateral provision)
  • On Arbitrum: \(s_1 \rightarrow s_1''\) (loan execution)
  • In DAML: \(s_1 \rightarrow s_1'''\) (original state update)

To resolve this conflict, the data structure must support:

Requirement 1.1: All change attempts for a specific state \(s_i\) must reference the same location. This inevitably requires an index-based structure.

Requirement 1.2: During state merging, the tree structure must be deterministic. That is, identical state sets must always generate identical tree structures.

Property 2: Sparse State Space Representation

Analyzing the characteristics of RWA state space, we discover an interesting pattern. When the possible asset ID space is \(2^{256}\), the number of actually registered assets is \(k \ll 2^{256}\).

Analysis of current Oraclizer testnet data reveals:

  • Total address space: \(2^{256} \approx 1.16 \times 10^{77}\)
  • Actually registered RWAs: \(\approx 10^4\text{--}10^5\)
  • Sparsity ratio: \(\frac{k}{2^{256}} \approx 10^{-73}\)

This extreme sparsity requires:

Requirement 2.1: Empty state space must be representable without explicit storage.

Requirement 2.2: Memory complexity must be \(O(k)\), where k is the number of actually stored items (not \(O(2^n)\)).

Property 3: Deterministic Cross-chain Verifiability

The core challenge of cross-chain state synchronization is that root hashes independently calculated for the same state on different chains must match.

For state root \(r_E\) calculated on Ethereum and state root \(r_A\) calculated on Arbitrum:

\(\displaystyle \text{If } S_E = S_A \text{ (same state set)}\)\(\displaystyle \Rightarrow r_E = r_A \text{ must hold}\)

This requires:

Requirement 3.1: Tree depth must be fixed. Variable depth can generate different path lengths for identical states.

Requirement 3.2: Tree structure must be independent of insertion order.

“We initially thought this was simply a problem of finding an ‘efficient data structure.’ But we soon realized. This was a problem of finding ‘the only structure that enables state synchronization.’”

Jay Kim, CPO, Oraclizer

Structural Limitations of Merkle Patricia Trie

The Fatal Flaw: Path Compression

MPT’s core optimization, path compression, provides excellent space efficiency in single-chain environments. However, in state merging scenarios, this becomes a fatal flaw.

Problem 1: Non-deterministic Tree Structure

Consider the following scenario. We merge states from two different sources:

Source A: State stored at address 0x123400...
Source B: State stored at address 0x123456...

Merging these in MPT produces:

Path 1 (A inserted first):
Root → Extension[1,2,3,4] → Branch[0,0] → Leaf[value_A]
                          → Branch[5,6] → Leaf[value_B]

Path 2 (B inserted first):
Root → Extension[1,2,3,4,5,6] → Leaf[value_B]
     → Extension[1,2,3,4,0,0] → Leaf[value_A]

Despite being the same state set, tree structure varies with insertion order. This means root hashes differ:

$$h_{root}^{(A \rightarrow B)} \neq h_{root}^{(B \rightarrow A)}$$

This violates Requirement 3.2.

Problem 2: State Merging Ambiguity

A more serious issue is the non-determinism of merged states. When merging MPTs independently built on Ethereum and Arbitrum chains:

Chain E’s state:

  • \(s_1\) at 0xABCD...
  • \(s_2\) at 0xABCE...

Chain A’s state:

  • \(s_3\) at 0xABCF...

During MPT merging:

Option 1: Extension[A,B,C] → Branch[D] → Leaf[s1]
                           → Branch[E] → Leaf[s2]  
                           → Branch[F] → Leaf[s3]

Option 2: Extension[A,B,C,D] → Leaf[s1]
         Extension[A,B,C,E] → Leaf[s2]
         Extension[A,B,C,F] → Leaf[s3]

For the same final state, multiple valid tree structures exist. This makes cross-chain verification impossible.

The Depth Problem: Variable Path Length

MPT’s depth is variable depending on actual key content and distribution.

Address 0x000000...01 may have depth 64, while address 0x123456...78 may need only depth 32.

This variable depth causes the following problems:

Problem 2.1: Verification path length mismatch

Proof length verifying same asset on Ethereum: 32 nodes
Proof length verifying same asset on Arbitrum: 45 nodes

Verifiers cannot determine “why proof lengths differ.”

Problem 2.2: Complexity of depth readjustment after merging

After merging two MPTs, recompressing extension nodes has \(O(n \cdot m)\) complexity, where n and m are the number of nodes in each tree.

Theoretical Impossibility Proof

We can prove the following:

Theorem 1: Any tree structure using path compression cannot guarantee insertion-order-independent determinism.

Proof:

  1. Definition of path compression: compress consecutive nodes with single child into one
  2. Different insertion orders alter the “single child” condition at specific points
  3. Therefore, compression timing and scope differ
  4. Final tree structure differs ∎

Theorem 2: Variable-depth trees create undecidable problems in cross-chain consistency verification.

Proof:

  1. Assume chains A and B have identical state S
  2. Let MPT depths generated from S be \(d_A\) and \(d_B\) respectively
  3. Due to path compression, \(d_A \neq d_B\) is possible
  4. Verifiers cannot determine if \(d_A \neq d_B\) results from state mismatch or merely tree structure difference ∎
Compressed paths against fixed depth Path compression lets the shape and depth of an MPT follow its keys and their insertion order; an SMT keeps every leaf at one fixed depth and lets one default hash stand for an empty subtree.
Merkle Patricia Trie and Sparse Merkle Tree structure Two trees side by side. Left, a Merkle Patricia Trie: a root over two extension nodes, Ext[1,2,3] and Ext[4,5], which hold compressed key paths; Ext[1,2,3] leads to two branch nodes, the first over leaves L1 and L2 and the second over L3, and Ext[4,5] leads to one branch node over L4 and L5. Right, a Sparse Merkle Tree of fixed depth: a root over hash nodes H1 and H2; H1 over H3 and an empty subtree, H2 over H4 and an empty subtree; H3 over leaf L1 and an empty leaf; H4 over leaves L2 and L3. Empty positions are drawn dashed and marked with the empty-set sign: each stands for one default hash, not stored. Under the trees three properties are compared row by row: path compression saves space against efficient sparse representation, both strengths; variable depth, a limit of MPT, against fixed depth of 256 levels; non-deterministic structure, a limit of MPT, against deterministic structure. Merkle Patricia Trie (MPT) Sparse Merkle Tree (SMT) Root Ext[1,2,3] Ext[4,5] Br Br Br L1 L2 L3 L4 L5 Root H1 H2 H3 ∅ H4 ∅ L1 ∅ L2 L3 Ext extension · Br branch · L leaf H hash · ∅ empty subtree, one default hash · L leaf Path compression saves space Efficient sparse representation Variable depth Fixed depth (256 levels) Non-deterministic structure Deterministic structure Merkle Patricia Trie and Sparse Merkle Tree structure Two trees side by side. Left, a Merkle Patricia Trie: a root over two extension nodes, Ext[1,2,3] and Ext[4,5], which hold compressed key paths; Ext[1,2,3] leads to two branch nodes, the first over leaves L1 and L2 and the second over L3, and Ext[4,5] leads to one branch node over L4 and L5. Right, a Sparse Merkle Tree of fixed depth: a root over hash nodes H1 and H2; H1 over H3 and an empty subtree, H2 over H4 and an empty subtree; H3 over leaf L1 and an empty leaf; H4 over leaves L2 and L3. Empty positions are drawn dashed and marked with the empty-set sign: each stands for one default hash, not stored. Under the trees three properties are compared row by row: path compression saves space against efficient sparse representation, both strengths; variable depth, a limit of MPT, against fixed depth of 256 levels; non-deterministic structure, a limit of MPT, against deterministic structure. Merkle Patricia Trie (MPT) Root Ext[1,2,3] Ext[4,5] Br Br Br L1 L2 L3 L4 L5 Ext extension · Br branch · L leaf Path compression saves space Variable depth Non-deterministic structure Sparse Merkle Tree (SMT) Root H1 H2 H3 ∅ H4 ∅ L1 ∅ L2 L3 H hash · ∅ empty subtree, one default hash · L leaf Efficient sparse representation Fixed depth (256 levels) Deterministic structure
Figure 1MPT vs SMT Structure Comparison

Mathematical Necessity of Sparse Merkle Trees

Now we can mathematically define the necessary conditions for data structures satisfying the three essential properties derived earlier.

Condition 1: Fixed Depth Requirement

Definition: All leaf nodes in the tree must be at the same distance d from the root.

Mathematically expressed:

\(\displaystyle \forall \text{ leaf } l \in T: \text{depth}(l) = d = \text{constant}\)

This condition directly satisfies Requirement 3.1.

Corollary: Fixed depth implies complete coverage of key space.

\(\displaystyle \text{Number of possible leaves} = b^d\)

Where b is the branching factor. For binary trees with 256-bit key space, if \(d=256\), then \(2^{256}\) possible positions exist.

Condition 2: Sparsity Handling

Explicitly storing a complete tree of size \(2^{256}\) is impossible. Therefore:

Definition: Empty subtrees must be replaced with default hashes.

All empty subtrees at the same height have identical hashes:

$$h_{\text{empty}}(i) = \begin{cases} H(\text{“empty”}) & \text{if } i = 0 \text{ (leaf level)} \\ H(h_{\text{empty}}(i-1) || h_{\text{empty}}(i-1)) & \text{if } i > 0 \end{cases}$$

This achieves memory complexity \(O(k)\) (satisfying Requirements 2.1, 2.2).

Condition 3: Deterministic Structure

Definition: For identical state set S, the same tree structure must be generated regardless of insertion order.

This means:

\(\displaystyle \forall \text{ permutations } \pi : S \rightarrow S',\)\(\displaystyle T(S) = T(S')\)

Where \(T(\cdot)\) is the function generating a tree from a state set.

This is achieved through index-based structure: each state \(s_i\) is stored at a fixed position determined by hashed key \(h(k_i)\).

Convergence to SMT

Remarkably, the above three conditions precisely match the definition of Sparse Merkle Tree.

SMT:

  1. Has fixed depth d (typically \(d = 256\))
  2. Handles sparsity with default node mechanism
  3. Ensures insertion order independence by key hash determining leaf position

“We did not choose SMT. The essence of state synchronization led us to SMT.”

Oraclizer Core Research Team

O(log n) Complexity: Necessary but Not Sufficient

Many tree structures offer \(O(\log n)\) complexity. However, for state synchronization, “what kind of \(O(\log n)\)” matters.

SMT’s \(O(\log n)\) has the following characteristics:

1. Predictable constant factor:
MPT: \(O(\log_{16} n)\) but variable overhead from extension nodes
SMT: Exactly \(O(\log_2 n) = 256\) steps for 256-bit keys

2. Parallelizability:
SMT’s fixed depth enables parallel processing of each level.

3. Incremental update efficiency:
When updating k states:

  • MPT: \(O(k \cdot n)\) (requires path compression recalculation)
  • SMT: \(O(k \cdot \log n)\) (only affected paths update)

SMT-based State Merging Algorithm

Now we can design a multi-source state merging algorithm utilizing SMT.

Multi-source State Merging Protocol

Oraclizer merges three main state sources:

  1. DAML contract states (off-chain financial contracts)
  2. External API states (real-time market data)
  3. Cross-chain states (Ethereum, Arbitrum, Base, etc.)
class SMTStateMerger:
    def __init__(self, depth=256):
        self.depth = depth
        self.default_hashes = self.compute_default_hashes()
    
    def merge_states(
        self, 
        daml_states: Dict[bytes32, State],
        api_states: Dict[bytes32, State],
        chain_states: Dict[bytes32, State]
    ) -> bytes32:
        """
        Merge multi-source states into single SMT
        
        Returns:
            merged_root: Root hash of merged state
        """
        # 1. Consolidate all source states into single map
        merged = {}
        
        # Priority order: DAML > Chain > API
        for asset_id, state in api_states.items():
            merged[asset_id] = state
            
        for asset_id, state in chain_states.items():
            merged[asset_id] = self.resolve_conflict(
                merged.get(asset_id), 
                state, 
                priority='chain'
            )
        
        for asset_id, state in daml_states.items():
            merged[asset_id] = self.resolve_conflict(
                merged.get(asset_id),
                state,
                priority='daml'  # Highest priority
            )
        
        # 2. Build SMT (parallelizable)
        return self.build_smt(merged)
    
    def resolve_conflict(
        self,
        existing: State,
        new: State,
        priority: str
    ) -> State:
        """
        Apply conflict resolution rules
        """
        if existing is None:
            return new
            
        # Check for oracle contract lock
        if existing.lock_status == LockStatus.ORACLE_LOCKED:
            raise ConflictError(
                f"Asset locked in oracle contract"
            )
        
        # Priority-based resolution
        if priority == 'daml':
            # DAML state is source of truth
            return new
        elif priority == 'chain':
            # Verify timestamp
            if new.timestamp > existing.timestamp:
                return new
        
        return existing
    
    def build_smt(
        self, 
        states: Dict[bytes32, State]
    ) -> bytes32:
        """
        Build SMT with O(k log n) complexity
        """
        leaves = {}
        
        # Place each state at fixed position
        for asset_id, state in states.items():
            leaf_index = int.from_bytes(
                keccak256(asset_id), 
                'big'
            )
            leaves[leaf_index] = hash(state)
        
        # Build tree bottom-up
        current_level = leaves
        
        for level in range(self.depth):
            next_level = {}
            
            # All nodes at level can be processed in parallel
            for index in range(2 ** (self.depth - level - 1)):
                left_idx = index * 2
                right_idx = index * 2 + 1
                
                left = current_level.get(
                    left_idx,
                    self.default_hashes[level]
                )
                right = current_level.get(
                    right_idx,
                    self.default_hashes[level]
                )
                
                next_level[index] = keccak256(left + right)
            
            current_level = next_level
        
        return current_level[0]  # Root hash

Atomicity Guarantee

SMT structure naturally supports all-or-nothing merging:

class AtomicStateMerge:
    def merge_with_rollback(
        self,
        sources: List[StateSource]
    ) -> Result:
        """
        Atomic state merge with rollback support
        """
        # 1. Store current root
        previous_root = self.get_current_root()
        
        try:
            # 2. Build temporary SMT
            temp_root = self.merge_states(sources)
            
            # 3. Verify
            if not self.verify_state_transition(
                previous_root,
                temp_root
            ):
                raise ValidationError()
            
            # 4. Commit
            self.commit_root(temp_root)
            return Success(temp_root)
            
        except Exception as e:
            # 5. Rollback simply maintains previous root
            # No actual data change as SMT is immutable
            self.log_rollback(previous_root, e)
            return Failure(e)

SMT’s immutability makes rollback very simple. Without committing the new root, the previous state is automatically maintained.

Complexity Analysis

When merging from m sources with \(k_i\) states each:

MPT merging:
\(T_{MPT} = O\left(\sum_{i=1}^m k_i \cdot n\right) + O(\text{recompression})\)

SMT merging:
\(T_{SMT} = O\left(\left(\sum_{i=1}^m k_i\right) \cdot \log n\right)\)

Let \(k = \sum k_i\), then SMT achieves linear merging with \(O(k \log n)\).

SMT-based state merging Three sources fold into one map by priority, a locked asset stops the merge, and every merged state takes a fixed leaf from which the tree is hashed up, level by level, to one root.
SMT-based state merging: from three sources to one root and its proof The merge runs down the left, the tree is built up the right. Step 1: three sources in priority order, DAML States, Chain States and External API, join into step 2, consolidation into one map per asset_id, with priority DAML over Chain over API. Step 3, a conflict on an asset_id: an oracle lock is checked first, then priority applies, and a Chain state needs a newer timestamp to replace the one held. A locked asset takes the dashed path to ConflictError, and the previous root is kept. Otherwise the states are merged and their metadata updated, and each state goes to the leaf at position keccak256(asset_id). Step 4: the Sparse Merkle Tree is built bottom-up, each level in parallel, with fixed depth 256; filled squares are leaves and nodes that hold a state, dashed squares are empty and use the default hash. Step 5: the merged root hash. Step 6: an incremental proof of the root goes to zkVerify, which returns the verification result. Complexity: time O(k log n), space O(k), proof size k times 256 siblings, and one root for each state set. 1 Sources DAML States Chain States External API priority DAML > Chain > API 2 Consolidate One map per asset_id 3 Conflict Oracle lock, then priority Chain needs a newer timestamp oracle-locked ConflictError previous root kept zkVerify verification result Incremental proof 6 Merged root hash 5 fixed depth 256 4 Build SMT bottom-up each level in parallel position = keccak256(asset_id) state empty: default hash merge states update metadata Time O(k log n) Space O(k) Proof size k × 256 siblings Determinism one root per state set SMT-based state merging: from three sources to one root and its proof The merge runs down the left, the tree is built up the right. Step 1: three sources in priority order, DAML States, Chain States and External API, join into step 2, consolidation into one map per asset_id, with priority DAML over Chain over API. Step 3, a conflict on an asset_id: an oracle lock is checked first, then priority applies, and a Chain state needs a newer timestamp to replace the one held. A locked asset takes the dashed path to ConflictError, and the previous root is kept. Otherwise the states are merged and their metadata updated, and each state goes to the leaf at position keccak256(asset_id). Step 4: the Sparse Merkle Tree is built bottom-up, each level in parallel, with fixed depth 256; filled squares are leaves and nodes that hold a state, dashed squares are empty and use the default hash. Step 5: the merged root hash. Step 6: an incremental proof of the root goes to zkVerify, which returns the verification result. Complexity: time O(k log n), space O(k), proof size k times 256 siblings, and one root for each state set. 1 Sources DAML States Chain States External API priority DAML > Chain > API 2 Consolidate One map per asset_id 3 Conflict Oracle lock, then priority Chain needs a newer timestamp oracle-locked ConflictError previous root kept zkVerify verification result Incremental proof 6 Merged root hash 5 fixed depth 256 4 Build SMT bottom-up each level in parallel position = keccak256(asset_id) state empty: default hash merge states update metadata Time O(k log n) Space O(k) Proof size k × 256 siblings Determinism one root per state set
Figure 2State Merging Algorithm Flowchart

Synergy with Incremental Proving

SMT’s true power reveals itself in its structural synergy with incremental proving.

The Challenge of Continuous State Changes

State synchronization handles continuous state changes. During transition from block i to block i+1, generating new proofs for all states is inefficient.

Traditional approach:

Block i:   Generate proof P_i for entire state S_i
Block i+1: Generate proof P_{i+1} for entire state S_{i+1}

Incremental proving approach:

Block i:   Generate proof P_i for state S_i
Block i+1: Generate Δ_proof for only changed states
           P_{i+1} = P_i ⊕ Δ_proof

SMT Enables Efficient Incremental Proving

SMT’s fixed structure enables recalculation of only changed paths.

When state \(s_j\) changes:

  1. Path from leaf j to root: \(\log_2 n\) nodes
  2. Sibling nodes at each level are unchanged
  3. Therefore only \(\log_2 n\) hashes need recalculation
class IncrementalSMTProver:
    def update_and_prove(
        self,
        previous_root: bytes32,
        updates: Dict[int, State]
    ) -> IncrementalProof:
        """
        Incremental update and proof generation
        """
        affected_paths = set()
        new_nodes = {}
        
        # 1. Collect all affected paths
        for leaf_index in updates.keys():
            path = self.get_path_to_root(leaf_index)
            affected_paths.update(path)
        
        # 2. Recalculate only affected nodes
        for node_index in sorted(affected_paths):
            level = self.get_level(node_index)
            
            left_child = self.get_child(
                node_index, 
                'left',
                new_nodes
            )
            right_child = self.get_child(
                node_index,
                'right',
                new_nodes
            )
            
            new_nodes[node_index] = keccak256(
                left_child + right_child
            )
        
        new_root = new_nodes[0]  # Root
        
        # 3. Generate incremental proof
        return IncrementalProof(
            previous_root=previous_root,
            new_root=new_root,
            updated_nodes=new_nodes,  # Only changed nodes
            siblings=self.get_siblings(affected_paths)
        )

Integration with zkVerify

Oraclizer sends incremental proofs to the zkVerify network for verification:

SMT Update → Incremental Proof → zkVerify → Verification Result

Proof size comparison:

MethodProof SizezkVerify Cost
Full State Proof\(O(n)\)High
MPT IncrementalVariableMedium-High
SMT Incremental\(O(k \log n)\)Low

When k states change, SMT proof requires exactly \(k \cdot 256\) siblings.

Proof Size Optimization

Furthermore, batch proving can reduce proof size even more:

def batch_incremental_proof(
    updates: List[StateUpdate]
) -> BatchProof:
    """
    Consolidate multiple updates into single proof
    """
    # Merge affected paths of all updates
    all_paths = set()
    for update in updates:
        all_paths.update(
            get_path_to_root(update.leaf_index)
        )
    
    # Include only deduplicated siblings
    unique_siblings = {}
    for path_node in all_paths:
        sibling = get_sibling(path_node)
        if sibling not in all_paths:
            unique_siblings[path_node] = sibling
    
    return BatchProof(
        roots=(previous_root, new_root),
        siblings=unique_siblings  # Deduped
    )

Efficiency improvement:

  • If 10 updates share overlapping paths
  • Individual proofs: \(10 \times 256 = 2{,}560\) siblings
  • Batch proof: \(\approx 400\text{--}600\) siblings (depending on path overlap)

Experimental Verification

Test Scenarios

We compared SMT and MPT in three state merging scenarios:

Scenario 1: DAML ↔ Ethereum (2-way merge)

  • DAML: 1,000 RWA contracts
  • Ethereum: 500 DeFi positions

Scenario 2: DAML ↔ Ethereum ↔ External API (3-way merge)

  • DAML: 1,000 contracts
  • Ethereum: 500 positions
  • External API: 200 real-time price feeds

Scenario 3: Multi-chain (n-way merge)

  • Ethereum, Arbitrum, Base, Polygon
  • Total 5,000 state changes

Performance Results

State Merging Time

ScenarioMPT (ms)SMT (ms)Improvement
2-way (1,500 states)8472034.2x
3-way (1,700 states)1,4322515.7x
n-way (5,000 states)6,8917249.5x

Memory Footprint

State CountMPT MemorySMT MemoryReduction
1,00015.2 MB3.1 MB79.6%
5,00078.4 MB15.3 MB80.5%
10,000156.1 MB30.8 MB80.3%

SMT consistently achieved approximately 80% memory reduction.

Proof Generation Time

Incremental proof generation time (100 state changes):

MethodTime (ms)Proof Size (KB)
MPT Full Proof523142.3
MPT Incremental28789.7
SMT Incremental8925.6

SMT achieved 3.2x faster proof generation and 3.5x smaller proof size.

Determinism Verification

1,000 iterations with different insertion orders for identical state sets:

def test_determinism(state_set, iterations=1000):
    roots = set()
    
    for _ in range(iterations):
        # Insert in random order
        shuffled = random.shuffle(state_set)
        root = build_tree(shuffled)
        roots.add(root)
    
    return len(roots)  # Should be 1

Results:

  • MPT: \(|roots| = 1000\) (all different)
  • SMT: \(|roots| = 1\) ✓
Measured on three merge scenarios SMT merged the states 4.2 to 9.5 times faster than MPT, the gap widening as sources and states grew, and needed a fraction of MPT's memory, proof time and proof size.
Performance comparison of SMT and MPT in the merge scenarios Three parts. First, state merging time in milliseconds on a value axis from 0 to 8,000, MPT as outlined bars and SMT as filled bars: the 2-way merge of 1,500 states took 847 ms with MPT and 203 ms with SMT, 4.2 times faster; the 3-way merge of 1,700 states 1,432 and 251 ms, 5.7 times; the n-way merge of 5,000 states 6,891 and 724 ms, 9.5 times. Second, shares of a baseline on an axis from 0 to 100 percent, the baseline as an outlined bar: against MPT, memory at 10,000 states 30.8 of 156.1 MB, 80.3 percent less; incremental proof generation time for 100 state changes 89 of 287 ms, 3.2 times faster; proof size 25.6 of 89.7 KB, 3.5 times smaller; and an SMT batch proof for 10 updates against 10 single proofs, about 400 to 600 of 10 times 256, 2,560, siblings, depending on path overlap. Third, structure: 1,000 builds of one state set in shuffled insertion orders gave 1,000 different MPT roots and one SMT root, perfect consistency; MPT depth is variable while SMT depth is fixed at 256, predictable. State merging time, ms MPT SMT SMT speed-up 0 2,000 4,000 6,000 8,000 847 203 2-way 1,500 states 4.2× 1,432 251 3-way 1,700 states 5.7× 6,891 724 n-way 5,000 states 9.5× SMT against MPT, share of MPT SMT batch proof against single proofs Memory · 10,000 states 30.8 of 156.1 MB · 80.3% less Proof time · 100 changes 89 of 287 ms · 3.2× faster Proof size · 100 changes 25.6 of 89.7 KB · 3.5× smaller Siblings · 10 updates ≈ 400–600 of 10 × 256 = 2,560 0 25% 50% 75% 100% Roots, 1,000 shuffled builds MPT 1,000 all different SMT 1 perfect consistency Tree depth MPT variable SMT fixed 256 predictable Performance comparison of SMT and MPT in the merge scenarios Three parts. First, state merging time in milliseconds on a value axis from 0 to 8,000, MPT as outlined bars and SMT as filled bars: the 2-way merge of 1,500 states took 847 ms with MPT and 203 ms with SMT, 4.2 times faster; the 3-way merge of 1,700 states 1,432 and 251 ms, 5.7 times; the n-way merge of 5,000 states 6,891 and 724 ms, 9.5 times. Second, shares of a baseline on an axis from 0 to 100 percent, the baseline as an outlined bar: against MPT, memory at 10,000 states 30.8 of 156.1 MB, 80.3 percent less; incremental proof generation time for 100 state changes 89 of 287 ms, 3.2 times faster; proof size 25.6 of 89.7 KB, 3.5 times smaller; and an SMT batch proof for 10 updates against 10 single proofs, about 400 to 600 of 10 times 256, 2,560, siblings, depending on path overlap. Third, structure: 1,000 builds of one state set in shuffled insertion orders gave 1,000 different MPT roots and one SMT root, perfect consistency; MPT depth is variable while SMT depth is fixed at 256, predictable. State merging time, ms MPT SMT SMT speed-up above each merge 0 2,000 4,000 6,000 8,000 847 203 2-way 1,500 states 4.2× 1,432 251 3-way 1,700 states 5.7× 6,891 724 n-way 5,000 states 9.5× SMT against MPT, share of MPT SMT batch proof against single proofs Memory · 10,000 states 80.3% less 30.8 of 156.1 MB Proof time · 100 changes 3.2× faster 89 of 287 ms Proof size · 100 changes 3.5× smaller 25.6 of 89.7 KB Siblings · 10 updates ≈ 400–600 of 2,560 0 25% 50% 75% 100% Roots, 1,000 shuffled builds MPT 1,000 all different SMT 1 perfect consistency Tree depth MPT variable SMT fixed 256 predictable
Figure 3Performance Comparison: SMT vs MPT

Conclusion: From Inevitability to Implementation

Our journey began with a simple “data structure selection.” But it led to the discovery of mathematical necessity.

The three essential properties required by state synchronization (concurrent processing, sparsity representation, and deterministic verifiability) defined the mathematical conditions that data structures must satisfy. And remarkably, those conditions precisely matched the definition of Sparse Merkle Trees.

MPT’s path compression is an excellent optimization for single chains, but creates structurally insurmountable limitations in multi-domain state synchronization. We proved this is not merely “inefficient” but mathematically impossible.

SMT was not a choice but a necessity. And this necessity led to the following practical benefits:

  • 9.5x faster state merging
  • 80% memory reduction
  • 3.2x faster proof generation
  • Perfect cross-chain verification consistency

“Sometimes it’s not technical constraints but mathematical truth that determines our path. SMT was not what we chose, but the only path that the essence of state synchronization taught us.”

Jay Kim, CPO, Oraclizer

Moving forward, we will address implementation details on this theoretical foundation. Optimization of SMT-based Smart Merging algorithms, comparison with Verkle Trees, and even Quantum-resistant SMT design.

But all future research will stand upon one truth we proved today: For complete state synchronization, Sparse Merkle Trees are inevitable.

This article describes technology under active research and development. Specifications, interfaces and implementation details may change as research, testing and community feedback progress, and performance figures are theoretical analyses or design targets unless stated otherwise.


References

[1]. Ethereum Foundation. (2024). Patricia Merkle Trie. https://ethereum.org/en/developers/docs/data-structures-and-encoding/patricia-merkle-trie/

[2]. Dahlberg, R., Pulls, T., & Peeters, R. (2016). Efficient Sparse Merkle Trees. In Nordic Conference on Secure IT Systems. https://www.researchgate.net/publication/308944456_Efficient_Sparse_Merkle_Trees

[3]. Horizen Labs. (2024). zkVerify: Modular ZK Proof Verification Network. https://zkverify.io/

[4]. Ma, B., Sun, Y., Wang, L., & Wang, X. (2023). One-Phase Batch Update on Sparse Merkle Trees for Rollups. arXiv:2310.13328. https://arxiv.org/abs/2310.13328

[5]. Fichter, K. (2018). What’s a Sparse Merkle Tree? Ethereum Foundation Blog. https://medium.com/@kelvinfichter/whats-a-sparse-merkle-tree-acda70aeb837

[6]. Buterin, V. (2018). Data availability proof-friendly state tree transitions. Ethereum Research. https://ethresear.ch/t/data-availability-proof-friendly-state-tree-transitions/1453

[7]. Yu, M., Sahraei, S., Li, S., Avestimehr, S., Kannan, S., & Viswanath, P. (2019). Coded Merkle Tree: Solving Data Availability Attacks in Blockchains. arXiv:1910.01247. https://arxiv.org/abs/1910.01247

Subscribe

New research, by email.

  • One email when a new article is published
  • Confirm once, leave with one click
  • Privacy