Jellyfish Merkle Tree in Libra Blockchain

Sun Mar 1, 2020 by lerencao in blog libra, blockchain, state-storage, MPT

Jellyfish Merkle Tree in Libra Blockchain

本文介绍了 Libra 中用来存储区块链状态数据的数据结构，Jellyfish Merkle Tree(JMT)。文章首先概述了 JMT 在 Libra 中扮演的角色，作用，及其主要的特征；然后重点阐述其接口以及内部实现；最后，拿它和以太坊的 MPT 树做对比，聊一聊它的优缺点。

Libra 在设计上和以太坊比较类似，都属于账户模型，但不同于以太坊把合约数据存储在一个单独的合约账户中，Libra 把合约数据抽象成 Resource，直接存储到账户下面（合约代码 Module 也是直接存储到账户中，代码即数据，两者在 Libra 存储中有着相同的地位）。当用户用了某个合约，合约产生的数据就放到用户账户下。因此，Libra 账户下，会包含有多个合约的多种 Resource。Jellyfish Merkle Tree 就是用来存储这些 (account_address，resources/modules) 的，重要性可见一斑。但是Libra 使用的共识是 PBFT（计划中会转向类 PoS 的共识），不存在分叉回滚这种说法。所以 JMT 的实现，和以太坊 Merkle Patricia Tree¹ 有些不同，不需要考虑分叉的问题。

以下，需要读者对以太坊 MPT 树有一定的了解，建议先阅读下文后的相关资料，以更好的理解 JMT。

MPT² 中，kv 对的查询，插入都是以某个世界状态的 root_hash: H256 作为整个树的入口开始的，插入 kv 对又会生成新的 state_root_hash，形成一个增量迭代的过程。有了 root_hash，上层调用者就可以方便的做回滚操作，只需要从某一个历史状态重新写入新的 kv 对，即可完成分叉。

那 JMT 是怎么做的呢？JMT 以 version: u64 作为调用入口。Libra 在最初的设计中，没有 block 的概念，只有 transaction，或者说每个 transaction 都是一个逻辑意义上的 block。这里的 version 表示已经在世界状态上执行的 transaction 的个数，初始是 0，每多一个 txn， version 就加 1。

这种做法，在可分叉的以太坊中，是行不通的。因为每个分叉链在分叉的时候，执行相同 version 的 txn 后的世界状态是不一样的，不然就不是分叉链了。

                  S_i        S_{i+1}
                /   \      /       \
               /     y   /          \
              / _______/             \
             //                       \
            o                          y'
           / \                        / \
          x   A                      z   B

这是 JMT 区别于 MPT 的一个主要特征，当然在内部实现也做了不少简化，下面就来重点分析下它的接口和实现。

JMT 实现

JMT 对外提供的接口比较简单，一个写接口，一个读接口，这里主要关注写接口（读接口比较简单，按照 key 往下寻址即可）。

    pub fn put_blob_set(
        &self,
        blob_set: Vec<(HashValue, AccountStateBlob)>,
        version: Version,
    ) -> Result<(HashValue, TreeUpdateBatch)>;


    pub fn get_with_proof(
        &self,
        key: HashValue,
        version: Version,
    ) -> Result<(Option<AccountStateBlob>, SparseMerkleProof)>;

put_blob_set 需要两个参数，

一是要更新的数据 blob_set，本质上是一个键值对的列表，键是用户账户地址的 hash，值是这个账户下的所有 resources&modules 序列化后的二进制数据，这里用 AccountStateBlob 表示。
二是这些更新是由哪个 version 的 transaction 产生的。

这里要特别说明的是，这个方法其实并没有真的去把数据写到底层存储中，而是返回对树的更新 TreeUpdateBatch，以及更新后的树的 merkle hash。TreeUpdateBatch 中包含了这个操作要增加哪些节点，要删除哪些节点，调用者拿到这些数据之后，再进行实际的写盘操作。

pub struct TreeUpdateBatch {
    pub node_batch: BTreeMap<NodeKey, Node>,
    pub stale_node_index_batch: BTreeSet<StaleNodeIndex>,
    pub num_new_leaves: usize,
    pub num_stale_leaves: usize,
}
pub struct StaleNodeIndex {
    pub stale_since_version: Version,
    pub node_key: NodeKey,
}

基本数据结构

讲到这里，需要对 JMT 的基础数据结构做个介绍。

NodeKey: NodeKey是底层 KV 存储引擎实际要存储的 Key。包含两部分，version 以及半字节表示的在树中的位置 nibble_path。在树中，通过 nibble_path 可以唯一确定树中的一个 node，再加上 version，就可以寻址到树在某个版本下的某个节点上的数据。
```
pub struct NodeKey {
    // The version at which the node is created.
    version: Version,
    // The nibble path this node represents in the tree.
    nibble_path: NibblePath,
}
```

Node：Node 在 JMT 中表示树的节点，也是底层KV存储引擎实际要存储的Value（序列化为二进制 bytes）。

pub enum Node {
    /// Represents `null`.
    Null,
    /// A wrapper of [`InternalNode`].
    Internal(InternalNode),
    /// A wrapper of [`LeafNode`].
    Leaf(LeafNode),
}
pub struct LeafNode {
    // The hashed account address associated with this leaf node.
    account_key: HashValue,
    // The hash of the account state blob.
    blob_hash: HashValue,
    // The account blob associated with `account_key`.
    blob: AccountStateBlob,
}
pub struct InternalNode {
    // Up to 16 children.
    children: HashMap<Nibble, Child>,
}
pub struct Child {
    // The hash value of this child node.
    pub hash: HashValue,
    pub version: Version,
    // Whether the child is a leaf node.
    pub is_leaf: bool,
}

Node::Null 是整棵树为空时候的表示。
Node::Leaf 代表树的叶子节点。比较好理解。LeadNode 存储了具体的账户地址信息，以及经过序列化后的账户数据。
Node::Internal 表示有子节点的中间节点。中间节点其实只是一个 HashMap，最大16元素，分别对于16个 Nibble 集合，0x00~0x0f，存储以不同 nibble 起始的子节点。这和 MPT 树是类似的设计。

下图给出了一个可能的树结构示意图。

起始的圆形节点，是用来寻找树根的 NodeKey，实线代表实际的物理寻址（数据库中的 KV 映射），虚线代表的逻辑寻址（tree 中的关联关系）。图中只标出了从 root 指针寻址到根节点数据这一个物理寻址过程，再往下省略了这一过程。读者只需要了解，每一个逻辑寻址在实现上，都有一个物理寻址的过程，父节点需要构造出子节点在存储中对应的 NodeKey。

图中共有5个叶子结点。

Leaf_0 的地址以 0 开头，且只有它以 0 开头。
Leaf_5c2 和 Leaf_5c4 的地址都以 5c 开头。
Leaf_a4 和 Leaf_ab 地地址都以 a 开头。
Leaf_ac5 和 Leaf_ac8 的地址都以 ac 开头。

图中省略了地址的剩余部分，以避免地址太长，影响图片的观感。

graph TD
root((root))
root --> i[Internal_]
i -.->|0| l0(Leaf_0)
i -.->|5| l5[Internal_5]
i -.->|a| la[Internal_a]
l5 -.->|c| l_5c[Internal_5c]
l_5c -.->|2| l_5c2(Leaf_5c2)
l_5c -.->|4| l_5c4(Leaf_5c4)
la -.->|4| i4(Leaf_a4)
la -.->|b| ib(Leaf_ab)
la -.->|c| ic[Internal_ac]
ic -.->|5| ic5(Leaf_ac5)
ic -.->|7| ic8(Leaf_ac8)

写数据流程

本节会列举几种常见的场景，来说明在不同位置上写数据对树结构产生的影响。

树初始状态为空。

场景1:在空树中添加节点。

这种情况下，直接构造 LeafNode，将 root key 指向它即可。

graph TD
classDef newElemclass fill:#f96;
subgraph s
root((root))
root --> l(Leaf_1a):::newElemclass
end

场景2: 新添加的地址，和某个 Leaf 节点有着相同的前缀。

下图中，Leaf_1b 是新加入的节点，它和已存在的 Leaf_1a 都以 1开头，这个时候，需要构造一个 Internal 节点，将 a, b 作为子节点加入到自己的 children 中。（图中橘红色代表新增的节点）

graph TD
classDef newElemclass fill:#f96;
subgraph s_j
rootb((root))
rootb --> l_1[Internal_1]:::newElemclass
l_1 -.->|a| l_1a(Leaf_1a)
l_1 -.->|b| l_1b(Leaf_1b):::newElemclass
end

subgraph s_i
roota((root))
roota --> l(Leaf_1a)
end

如果新地址和 leaf 节点的共同前缀不止一个，那就需要递归的构造 Internal 节点，直到共同部分都是 Internal 节点。

graph TD
classDef newElemclass fill:#f96;
subgraph s_j
rootb((root))
rootb --> l_1[Internal_1]:::newElemclass
l_1 -.->|a| l_1a[Internal_1a]:::newElemclass
l_1a -.->|1| l_1a1[Internal_1a1]:::newElemclass
l_1a1 -.->|b| l_1a1b(Leaf_1a1b)
l_1a1 -.->|c| l_1a1c(Leaf_1a1c):::newElemclass
end

subgraph s_i
roota((root))
roota --> l(Leaf_1a1b)
end

场景3: 新添加的地址，和 Internal 节点有着相同的前缀。

这种时候，只需要将，新节点添加到 Internal 节点的 children 中即可。下图中，Leaf_1a2 节点就会被放进 Internal_1a 的 nibble 为 2 的插槽中。（图中，黄色节点代表被替换的节点）

graph TD
classDef replaceElemclass fill:#f5dd42;
classDef newElemclass fill:#f96;
subgraph s_m
roota((root))
roota --> m_1[Internal_1]:::replaceElemclass
m_1 -.->|a| m_1a[Internal_1a]:::replaceElemclass
m_1a -.->|1| m_1a1[Internal_1a1]
m_1a1 -.->|b| m_1a1b(Leaf_1a1b)
m_1a1 -.->|c| m_1a1c(Leaf_1a1c)
m_1a -.->|2| m_1a2(Leaf_1a2):::newElemclass
end

subgraph s_l
rootb((root))
rootb --> l_1[Internal_1]
l_1 -.->|a| l_1a[Internal_1a]
l_1a -.->|1| l_1a1[Internal_1a1]
l_1a1 -.->|b| l_1a1b(Leaf_1a1b)
l_1a1 -.->|c| l_1a1c(Leaf_1a1c)
end

以上列举的三种场景，涵盖了写数据会遇到的几种情况。

物理寻址时的指针生成

在沿着 root 往下寻找共同前缀时，JMT 需要不断的去存储引擎获取子节点的数据信息，这中间涉及到如何通过 InternalNode 构造子节点的物理地址，本节将描述这个过程，补充这丢失的环节。

pub struct InternalNode {
    // Up to 16 children.
    children: HashMap<Nibble, Child>,
}
pub struct Child {
    // The hash value of this child node.
    pub hash: HashValue,
    pub version: Version,
    // Whether the child is a leaf node.
    pub is_leaf: bool,
}

前面我们给出了 InternalNode 的结构定义，它最多包含16个的“子节点”。这里的“子节点”并不存储真实的子节点数据，它只保存了少部分元信息，这些元信息可以构造出子节点数据的物理指针。（忽略 child.hash，这是为了计算 merkle proof 而缓存的子节点 hash 数据）

child.version: 子节点创建时的 version。
children.nibble: 子节点所在的"插槽”。
parent.nibble_path: 父节点在树中的 nibble_path。当寻址到父节点时，这个 nibble_path 就已知了。

再来看看物理指针 NodeKey 的定义。

pub struct NodeKey {
    // The version at which the node is created.
    version: Version,
    // The nibble path this node represents in the tree.
    nibble_path: NibblePath,
}

有了上面提到的元信息，就可以构造子节点的 NodeKey，利用这个 key 去存储引擎中提取子节点的实际数据。

node_key.version = child.version
node_key.nibble_path = parent.nibble_path + child.nibble

起始的 root 节点的 NodeKey，只有 version 信息，nibble_path 为空。

总结

JMT 的设计其实是比较简单的，除掉 Node::Null，就只有两种典型的节点。树的操作也不复杂，几张图基本就能够说清楚。因为不需要提供分叉功能，所以这么设计也是相对合理的。

但对比 MPT， JMT 有一个比较大的缺点。读者猜猜是什么？

在场景二中，我们提到，如果新地址和 leaf 节点的共同前缀不止一个，那就需要递归的构造 Internal 节点，直到共同部分都是 Internal 节点。

如果，这共同前缀太长呢？比如前31位都是一样的，只有最后一位有区别。JMT 在这种情况下，会不断构造中间节点，导致树变得很深。

随着这种情况越来越多，这些节点就会像水母的触手一样。整个树也形如水母。在这一点上，我觉得 JMT 可以参考 MPT 那样，将这些共同的前缀存储到 InternalNode 中，减少空间浪费。

Starcoin Blockchain

Sirius Protocol

Stargate Protocol

Thor Protocol

Jellyfish Merkle Tree in Libra Blockchain

JMT 实现

基本数据结构

写数据流程

物理寻址时的指针生成

总结