本文将介绍Sparse Merkle Tree（以下简称SMT）、其和一般习惯的Merkle Tree 的不同，以及它的优点及用途。在了解SMT 之前，你会需要知道密码学杂凑函式（Cryptographic Hash Function）的特质。如果你已经知道Merkle Tree 和Merkle Proof，可以跳过接下来这一段，直接进到下一段Sparse Merkle Tree。

熟悉的Merkle Tree

这边我们以区块链的区块里的Transaction Merkle Tree 为例，简短复习一下平常熟悉的Merkle Tree。

Merkle Tree：

Transaction Merkle Tree（叶节点是H(Tx)，交易内容的杂凑值）：

每个区块所包含的交易的交易内容不会全部直接塞在Block Header 里，而是将这些交易做杂凑，然后再将这些杂凑值组成(Transaction) Merkle Tree，最后只会有一个值(Transaction) Merkle Root 存在Block Header 里。

为什么要这么做因为并不需要所有人都知道这个区块打包了哪些交易。像是轻节点，它不像全节点一样需要验证过每个区块的每一个交易以确保自己纪录的链是一个合法的链。

轻节点用一些信任换取一些便利性：它只验证Block Header 的合法性，像是PoW、Previous Header Hash，并且相信全节点给它的(Transaction) Merkle Root 所包含的交易存在且合法。

Membership Proof

那这样做对它有什么帮助呢轻节点身为一般使用者和区块链之间的桥梁，它只在意这个使用者在意的交易，它只要确保自己（高机率）是在最长链上，且确保它在意的交易已被打包在某个区块里。而这就带到我们要介绍的Merkle Tree 的其中一个最大的优点：Membership Proof，证明某个值存在在某个Merkle Root 对应的Merkle Tree 里。

而且这个证明是精简(Compact) 的！想像一下，如果你有上面图中四笔交易，你可以选择把这四笔交易接起来丢进杂凑函式里得到一个杂凑值，并放在Block Header 里，简单粗暴：

H(Tx_A || Tx_B || Tx_C || Tx_D)

当你要向我证明Tx_B 被打包在这个区块里时，你就给我Tx_A、Tx_C 和Tx_D，然后我再用同样方式把它们接起来丢进杂凑函式，再把结果和Block Header 里的值做比对。

但当今天交易数量有数百笔、数千笔时，你为了要向我证明其中一个交易存在，你要给我其他全部的交易我才能验证，这样一点也不精简、不有效！

Compact Membership Proof

那如果今天换成Merkle Tree，要怎么证明Tx_A 存在在Block 2 的Transaction Merkle Tree 里

橘色是你我已知的资讯：Merkle Root 及Tx_A。接下来你只要提供给我绿色的部分就行了，我拿着橘色和绿色的值，照着原本组出Merkle Tree 的方式就可以自己算出Merkle Root 了。绿色的部分就叫做Merkle Proof。

而Merkle Proof 的大小不会随叶节点数量线性增长，而是对数增长。假设叶节点数量有100 万个时，Merkle Proof 的数量只会增长到20 个。

Recap:

Merkle Tree -> Compact Membership Proof！

State Tree(Trie)

在进入SMT 前，让我再延伸一下介绍(Ethereum) State Tree，因为这会和SMT 的优点有关。

可以看到Ethereum 的Block Header 除了Transaction 的Merkle Root 外，还有一个State Root，而图中State Tree 的叶节点是一个Ethereum Account 的State，里面包含这个Account 相关的资讯。

证明某个Account 在某个区块的State 长怎样（例如Balance 多少、Nonce 多少）的方式也和Transaction 一样。

Sparse Merkle Tree

SMT 和一般Merkle Tree 第一个不一样的地方就在于，它的大小预先就固定了。

从前面的Transaction Merkle Tree 范例中可以看到，当一个区块收入四笔交易时，它的Transaction Merkle Tree 就由这四笔交易组成，即它的叶节点只会有四个；如果一个区块收入一百笔交易，那它的Transaction Merkle Tree 就由这一百笔交易组成，这棵树会更大棵。

但把一个Merkle Tree 的大小预先就设好有什么用处Transaction Merkle Tree 由每个区块收入的交易多寡来决定该区块的树长多大，这是动态、不固定的。但如果今天我们要用来存预先就知道有多少数量且数量不会改变的东西的话，用一个固定大小的树来存就非常合理了。

那有什么东西是预先知道有多少数量且数量不会改变的呢像是Ethereum 的Account 数量：Ethereum 地址长度20 bytes，表示有2¹⁶⁰ 个不同的地址，即2¹⁶⁰ 个Account。Ethereum 的state 就可以用SMT 来存。

固定大小、固定的值

Transaction Merkle Root 因为知道Transaction 有哪些，所以可以知道叶节点要填什么值。但SMT 有这么多叶节点，不可能Ethereum 的所有Account 都有Balance 吧这些不存在的Account 要填什么值答案是预设值。

什么预设值可以是0，可以是1，或任意值，只要你的Protocol 有订好一个预设值就行了。

预设值为H(0) 的SMT

你可以看到，基本上这棵树的每一层的预设值都会是一样的：

H(0)、H(H(0) + H(0))、…

所以任何人只要知道树高及预设值，都可以自己算出每一层的预设值。

所以事实上你的节点在保存SMT 时，是不需要把空白（是预设值的）节点存在资料库里的！你只需要储存非空白的节点：

而这就是为什么它会被称作Sparse 的原因了。

Proof 的大小

你可能会想，Transaction Merkle Tree 里，如果交易放得少，那棵Merkle Tree 的Proof 大小就会小。那今天Ethereum State 这棵SMT 里如果Account 很少，结果每个Merkle Proof 都是一样、固定的，这样不是很浪费吗

是没错，但这其实是可以优化的：大部分节点都会是空白节点，也就是预设值，这时候你给我的Merkle Proof 里除了非空白节点，其他是空白节点的，你只要用一个bit 告诉我在这一层要用预设值就好，这样我就能自己补出完整的Merkle Proof 了。

虽然最后拼出来的Merkle Proof 还是固定大小的，但我们之间传递的资料量却可以缩小很多，避免网络频宽成为一个效能瓶颈。

Non-membership Proof

接下来就要直接进入SMT 的最大优点之一：Non-membership Proof。直觉上听起来会有点奇怪，要怎么证明一个东西不存在某个群体里或是更直接的，为什么

要怎么证明一个东西不存在某个群体里(How)

首先要先定义出这个群体，才能证明一个东西不存在这个群体。我们以Ethereum State 为例，这个群体就是Ethereum State 定义的2¹⁶⁰ 个Account。目前Ethereum 累积的地址数才只有1.9 亿个（约是2²⁸），所以绝大多数Ethereum State Tree 里的叶节点都是预设值（即空的Account：Balance、Nonce 等等都是0 的Account）。

为什么(Why)

如果我要向你证明某个地址还不存在、还没有任何活动痕迹，就是要向你证明那个Account 在Ethereum State 里的值是预设值！这就是我们利用SMT 来证明一个东西不存在某个群体的方式及原因。

（正确的定义可能是要说：证明某个地址不存在于活跃的Ethereum 地址群体中，但你知道我的意思。下面还有另一个例子会更合理。）

如果我要向你证明地址3（假设这个State 总共只有16 个地址）不存在、是空的，我就给你图中绿色的部分，你就能验证地址3 的值真的是预设值。

Replay Protection

最后要讲到的是SMT 目前的一个很大的用途，也是因为我常常要解释这个用途，解释了太多遍，干脆把它写下来介绍完整：Replay Protection。

如果你今天设计了一个应用或系统，你要怎么防止交易被replay 而导致使用者或是系统受害

如果交易是一笔transfer，则必须要防止同样一笔transfer 能再被replay 一次，导致使用者赔钱 如果交易是投下一张选票或是按一个赞，则必须要防止同样一张选票或点赞能再被replay，导致整个系统被操弄

其中一个答案是：证明交易不存在（交易存在则表示这是一个replay）

透过SMT Non-membership Proof，就可以用验证Merkle Proof 这个有效率的方式来验证一笔交易是否存在过，避免交易被replay。

附注

内文在SMT 的段落里有提到Ethereum state 可以用SMT 来储存。Ethereum state 目前是用Merkle Patricia Trie (MPT) 的结构储存，虽然实际上运作方式及优缺点不一样，但我个人觉得抽象来说Ethereum state 的MPT 也是属于一种SMT 的：固定高度、可以证明Non-membership、不需存中间的空白节点（Sparse Tree）。