默克尔树

MPT 全称是 Merkle Patricia Trie 也叫 Merkle Patricia Tree，是 Merkle Tree 和 Patricia Tree 的混合物。 Merkle Tree(默克尔树) 用于保证数据安全，Patricia Tree(基数树,也叫基数特里树或压缩前缀树) 用于提升树的读写效率。

在设计十六进制 trie 时，一些设计选择在当时听起来很棒，但是经过 5 年的实践，被证明带来了很多复杂性。鉴于 ETH 1.x 想要转向二进制 trie，我们正好可以借此机会研究一下状态的存储方式。

iden3.io 的 blog 最近发表了一篇关于默克尔树的图解文章，相当不错，特摘取了文章的图解部分。

默克尔化抽象语法树（Merklized Abstract Syntax Trees, MAST）是一项为比特币提议的升级，可以实现更小的交易体积、更好的隐私性，以及更大的智能合约。在本文中，我们会解释 MAST 的基本原理，讲解其潜在好处，并总结目前一些包含这项技术的提案。