<aside> 💡 Merkle Tree、Merkle Patricia Tree、Rollup State Tree、Verkle Tree和在Airdrop中的使用

</aside>

问题背景

1. 对不同的数据结构求Hash

   

   https://learnmeabitcoin.com/technical/merkle-root

   1. 对Struct求Hash，数据拼接

      1. BlockHash = hash(BlockHeader) = hash(Version+PrevBlock+Time+…)
      2. TxHash = hash(Tx) = hash(To+Value+Sig+…)

   2. 对Array求Hash？

      1. hash([TxHash0, TxHash1, TxHash2,…]) ?

   3. 对Map求Hash？

      1. hash({Address0: State0, Address1: State1, …}) ？

   4. 对Array/Map的进行数据拼接

      

      https://learnmeabitcoin.com/technical/merkle-root

2. Proof of Inclusion（PoI）

   1. Wallet的需求，Proof of Inclusion
      1. 需要知道一笔交易TxHash是否在链上
      2. 需要知道一个状态Address: State是否在链上
   2. 基于拼接法对Array/Map求Hash，PoI验证过程复杂
      1. Array：需要知道其他所有交易TxHash才能证明
      2. Map：需要知道其他所有状态Address: State才能证明
      3. 空间复杂度O(N)，时间复杂度O(N)

3. 需求：对Array/Map求Hash，且PoI复杂度低

Merkle Tree

1. Merkle Tree是一种对Array求Hash的方法，且提供简洁的PoI

   

   https://bitcoin.org/bitcoin.pdf

   1. 对Array的数据按树状进行拼接，计算得到Merkle Root / Root Hash
      1. Hash01 = hash(TxHash0+TxHash1)
   2. 用Merkle Path / Merkle Proof作为PoI
      1. PoI(TxHash3) = ((Hash2, Hash01), MerkleRoot, Index3)
      2. 验证过程：空间复杂度 O(N) → O(logN)，时间复杂度O(N) → O(2·logN)

Merkle Patricia Tree

1. Patricia Tree，也叫Radix Tree、Trie

   

   https://en.wikipedia.org/wiki/Radix_tree

   1. Trie是Map的一种数据结构，根据key的前缀进行索引
      1. 类比Hash Map（hash+bucket），Binary Search Tree（比较key的大小）
   2. Patricia Tree理解为Trie的一种优化实现，对相同路径的node进行了聚合
   3. Patricia Tree的特点在于
      1. 高效支持按key前缀的范围查找
      2. 树结构的确定性，和插入顺序无关
      3. 增删查的时间复杂度是O(K)，K是key的长度
      4. 理解和实现起来简单

2. Merkle Patricia Tree

   1. 可理解为把Merkle Tree从2叉树变成16叉树，再加个value字段

      

      https://medium.com/@chiqing/merkle-patricia-trie-explained-ae3ac6a7e123

   2. 把所有的node存到key-value DB里，以hash(node)作为key

   3. node里面叶子的指针替换为叶子的hash(node)

      

      https://ethereum.stackexchange.com/questions/268/ethereum-block-architecture

3. Merkle Patricia Tree的问题：同时负责了Map的PoI和索引，互相制约性能

   1. 索引时，需要$O(log_{16}N)$次DB请求，比普通Map的1次DB请求慢很多，时间复杂度O(K) →$O(K·log_{16}N)$
   2. PoI时，空间复杂度$O(16·log_{16}N)$，比普通Merkle Tree的O(logN)慢
   3. 改成2叉树/2为底，则索引的DB请求次数更多

Rollup的State Tree

1. Rollup的State Tree对性能要求高：需要在合约验证PoI

2. 对Map的key-value pairs排序后建立Merkle Tree

   1. {Address0: State0, Address1: State1, …} →

      1. Map索引：{Address0: Index0, Address1: Index1, ...} +
      2. key-value pairs排序：[(Address0, State0), (Address1, State1), ...]

   2. 举例：{Alice: 0, Bob: 6, Charlie: 12, ...} +

      

      https://vitalik.ca/general/2021/01/05/rollup.html

3. 分析

   1. Map和PoI的数据结构分离，互不影响
   2. 索引的性能和Map一致
   3. 16叉树回到2叉树，PoI性能等同Merkle tree

Verkle Tree

1. 需求：Stateless Client

   1. 节点不存完整的State Tree，只获取需要的State来验证Block
   2. Portal Network
   3. 对State Tree的PoI更高的性能要求

2. 回顾Data Availability里的KZG commitment

   1. 每个leaf都是polynomial上的点
   2. constant size proof，和leaf数量无关

   

   https://docs.google.com/presentation/d/1-pe9TMF1ld185GL-5HSWMAsaZLbEqgfU1sYsHGdD0Vw

3. Verkle Tree

   

   https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html

4. 空间复杂度从Merkle Patricia Tree的$O(16·log_{16}N)$、Merkle Tree的O(logN)， 提升为 $O(log_{16}N)$