ネットワークの部分は置いておいて、イーサリアムはトランザクションがイーサリアムネットワーク上の状態を変更するステートマシンと言えるかもしれません。 状態はキーと値のペアで表現されます。 キーと値のペアを表現する方法はいくつかありますが、Ethereumの仕様では、Modified Merkle Patricia Trie（別名MPT）を状態を保存する方法として定義しています。
基本的にMPTはPatricia TrieとMerkle Treeを組み合わせたものですが、Ethereumの特徴に合う最適化をいくつか追加しています。 したがって、MPTの理解に先立ち、パトリシアのトライとメルクル木の理解が必要です。
パトリシアのトライは、プレフィックスツリー、基数木、トライとも呼ばれるデータ構造です。 トライはキーをパスとして使うので、同じプレフィックスを共有するノードは同じパスを共有することができます。 この構造は、共通の接頭辞を見つけるのが最も速く、実装が簡単で、必要なメモリも少なくて済む。 8086>
Merkle Tree
Merkle Treeはハッシュの木である。 リーフノードにはデータが格納される。 親ノードはその子のハッシュと、その子のハッシュの和のハッシュ値を含む。
二つの異なるノードが同じデータを持っているかどうかはMerkle Treeで効率よく調べることができる。 まず、2つのノードのトップハッシュ値を比較する必要がある。 もし同じであれば、その2つのノードは同じデータを持っていることになる。 例えば、上の図のように4つのノード（L1, L2, L3, L4）がある場合、トップハッシュが同じかどうかだけをチェックすればいい。 もしTop Hashが違っていて、どのデータが違うのか知りたい場合は、Hash0とHash1を比較して、どの枝が違うのかを確認すればよい。 8086>
Merkle Patricia Trie
MPTでもMerkle木と同じようにすべてのノードがハッシュ値を持っている。 各ノードのハッシュは、そのコンテンツのsha3ハッシュ値で決まる。 このハッシュは、ノードを参照するキーとしても使用される。 Go-ethereumはlevelDB、parityはrocksDBを使用して状態を保存します。 これらはキー・バリュー・ストレージである。 ストレージに保存されたキーと値は、イーサリアムのステートのキー値ではありません。 ストレージに保存される値はMPTノードの内容であり、キーはこのノードのハッシュである。
Ethereumステートのキー値はMPT上のパスとして使用される。 ニブルはMPTでキー値を区別するための単位なので、各ノードは最大で16個のブランチを持つことができます。 さらに、ノードは独自の値を持つため、ブランチノードは1つのノード値と16のブランチからなる17項目の配列となる。
子ノードを持たないノードをリーフノードと呼ぶ。 リーフノードは、そのパスと値の2項目からなる。 たとえば、キー “0xBEA “に1000、キー “0xBEE “に2000が格納されているとする。 このとき、「0xBE」のパスを持つ枝ノードがあり、その下に2つのパス（「0xA」と「0xE」）を持つ2つの葉ノードが付くことになる。
MPTでは枝ノードと葉ノード以外にもう1種類ノードがある。 それは拡張ノードである。 拡張ノードとは、ブランチノードを最適化したノードのことです。 イーサリアムの状態では、子ノードが1つしかないブランチノードがかなり頻繁に存在します。 これが、MPT が 1 つの子ノードしか持たないブランチノードを、パスと子ノードのハッシュを持つ拡張ノードに圧縮する理由です。
リーフノードと拡張ノードは両方とも 2 つのアイテムの配列なので、これらの 2 つのノードを区別する方法があるはずです。 そのような区別をするために、MPTはパスにプレフィックスを追加する。 ノードがリーフで、パスが偶数個のニブルで構成されている場合、プレフィックスとして0x20を追加するのです。 パスが奇数ニブルで構成されている場合は、プレフィックスとして0x3を追加する。 ノードが拡張ノードで、パスが偶数個のニブルから構成される場合、プレフィックスとして0x00を追加する。 奇数ニブルで構成されている場合は、プレフィックスとして0x1を追加する。 奇数ニブルのパスは1ニブル、偶数ニブルのパスは2ニブルを接頭辞とするため、パスは常にバイトで表現される
（韓国語原文はこちら）