エキゾチックなデータ構造：変更されたマークルパトリシアトライ

「これらのいまいましいすべてのアルゴリズムとデータ構造を、どのような悪魔として思い出すべきでしょうか？」

これについては、技術面接の通過に関するほとんどの記事のコメントに帰着します。 原則として、主な論文は、何らかの方法で使用されるすべてのものがすでに10回実装されており、この通常のプログラマーが対処しなければならない可能性はほとんどありません。 まあ、ある程度これは本当です。 しかし、結局のところ、すべてが実装されたわけではなく、残念ながら（または幸運なことに）データ構造を作成する必要がありました。

神秘的な修正マークルパトリシアトライ。

この木と媒体にはこの木に関する情報がまったくないので、もう少し、どのような動物で、何と一緒に食べられるのかを伝えたいと思います。

これは何ですか

免責事項：実装のための情報の主な情報源は、 イエローペーパー 、およびソースコードパリティイーサリアムとゴーイーサリアムでした 。 特定の決定の正当化に関する最小限の理論的情報があったため、特定の決定を下した理由に関するすべての結論は私の個人的なものです。 私が何かに間違えた場合-私はコメントの修正に喜んでいるでしょう。

ツリーは、接続された非循環グラフであるデータ構造です。 ここではすべてがシンプルで、誰もがこれに精通しています。

プレフィックスツリーは、ノードがパスの一部（プレフィックス）を含むノードと、格納された値を含むリーフノードの2つのタイプに分かれているため、キーと値のペアを格納できるルートツリーです。 キーを使用してツリーのルートから最後まで移動し、最後に値を持つノードを見つけることができる場合にのみ、値がツリーに存在します。

PATRICIAツリーは、プレフィックスがバイナリのプレフィックスツリーです。つまり、各キーノードは1ビットに関する情報を格納します。

マークルツリーは、ある種のデータチェーン上に構築されたハッシュツリーであり、これらの同じハッシュを1つ（ルート）に集約し、すべてのデータブロックの状態に関する情報を格納します。 つまり、ルートハッシュは、ブロックチェーンの状態の一種の「デジタル署名」です。 このことはブロックチェーンで積極的に使用されています 。詳細についてはこちらをご覧ください 。

合計：修正マークルパトリシアトライ（以下、略してMPT）は、キーと値のペアを格納するハッシュツリーであり、キーはバイナリ形式で提示されます。 そして、「修正」とは何なのかについては、後で実装について説明するときに少し調べます。

これはなぜですか？

MPTは、Ethereumプロジェクトで使用され、アカウント、トランザクション、その実行結果、およびシステムの機能に必要なその他のデータに関するデータを保存します。
状態が暗黙的で、各ノードによって個別に計算されるビットコインとは異なり、各アカウントの残高（およびそれに関連付けられているデータ）は、放送中のブロックチェーンに直接保存されます。 さらに、データの発見と不変性は暗号で提供されるべきです-客観的な理由なしにランダムな口座の残高が変化する暗号通貨を使用する人はほとんどいません。

Ethereum開発者が直面する主な問題は、キーと値のペアを効果的に保存し、同時に保存されたデータの検証を提供できるデータ構造の作成です。 そこで、MPTが登場しました。

どう？

MPTは、キーがバイトのシーケンスであるプレフィックスPATRICIAツリーです。

このツリーのエッジはニブルシーケンス（ハーフバイト）です。 したがって、1つのノードには最大16の子孫（0x0から0xFのブランチに対応）を含めることができます。

ノードは3つのタイプに分けられます。

• ブランチノード。 分岐に使用されるノード。 子ノードへの最大1〜16個のリンクが含まれます。 値を含めることもできます。
• 拡張ノード。 複数の子ノードに共通するパスの一部と、その下にあるブランチノードへのリンクを格納する補助ノード。
• 葉ノード。 パスの一部と格納された値を含むノード。 チェーンの終わりです。

すでに述べたように、MPTは別のkvリポジトリの上に構築され、「link」=>「 RLPエンコードされたノード」の形式でノードを保存します。

そして、ここで新しい概念RLPに出会います。 要するに、これはリストまたはバイトシーケンスを表すデータをエンコードする方法です。 例： [ "cat", "dog" ] = [ 0xc8, 0x83, 'c', 'a', 't', 0x83, 'd', 'o', 'g' ] 。 特に詳細には触れませんが、実装では既製のライブラリを使用します。このトピックを取り上げると、すでにかなり大きな記事が膨らむからです。 まだ興味がある場合は、 こちらをご覧ください 。 RLPでデータをエンコードし、デコードして戻すことができるという事実に限定しています。

ノードへのリンクは次のように定義されますkeccakエンコードされたノードの長さが32バイト以上の場合、リンクはノードのRLP表現からのkeccakハッシュです。 長さが32バイト未満の場合、リンクはノード自体のRLP表現です。

明らかに、2番目のケースでは、ノードをデータベースに保存する必要はありません。 完全に親ノード内に保存されます。

3種類のノードの組み合わせにより、キーが少ない場合（ほとんどのパスが拡張ノードとリーフノードに格納され、ブランチノードが少ない場合）、およびノー​​ドが多い場合（パスが明示的に格納されない場合）、データを効果的に格納できます。ただし、ブランチノードを通過するときに「収集」されます）。

あらゆる種類のノードを使用したツリーの完全な例：

お気づきかもしれませんが、パスの保存された部分にはプレフィックスがあります。 プレフィックスはいくつかの目的に必要です。

1. 拡張ノードとリーフノードを区別するため。
2. 奇数個のニブルのシーケンスを整列します。

プレフィックスを作成するためのルールは非常に簡単です。

• プレフィックスには1ニブルが必要です。 パスの長さ（プレフィックスを除く）が奇数の場合、パスはプレフィックスの直後から始まります。 パスの長さが偶数の場合-プレフィックスの後に整列するために、ニブル0x0が最初に追加されます。
• プレフィックスは最初は0x0です。
• パスの長さが奇数の場合、偶数の場合は0x1がプレフィックスに追加されます-0x0。
• パスがリーフノードにつながる場合、0x0が拡張ノードに追加されると、0x2がプレフィックスに追加されます。

ベアティックスでは、より明確になると思います：

 0b0000 =>  , Extension  0b0001 =>  , Extension  0b0010 =>  , Leaf  0b0011 =>  , Leaf  

除去ではない除去

ツリーにはノードを削除する操作があるという事実にもかかわらず、実際には、一度追加されたものはすべてツリーに永久に残ります。

これは、ブロックごとに完全なツリーを作成するのではなく、ツリーの古いバージョンと新しいバージョンの違いのみを保存するために必要です。

したがって、異なるルートハッシュをエントリポイントとして使用すると、ツリーがこれまでにあった状態を取得できます。

これらはすべて最適化されているわけではありません。 他にもありますが、それについては説明しません。したがって、記事は大きくなります。 ただし、自分で読むことができます。

実装

理論は終わりました。実践に移りましょう。 ITの世界の共通語、つまりpythonます。

たくさんのコードがあり、記事のフォーマットのために多くのコードを減らして分割する必要があるので、すぐにgithubへのリンクを残します。
必要に応じて、全体像を見ることができます。

まず、結果として取得するツリーインターフェイスを定義します。

 class MerklePatriciaTrie: def __init__(self, storage, root=None): pass def root(self): pass def get(self, encoded_key): pass def update(self, encoded_key, encoded_value): pass def delete(self, encoded_key): pass 

インターフェイスは非常にシンプルです。 利用可能な操作は、ルートハッシュの取得と同様に、取得、削除、挿入、および変更（更新で結合）です。

ストレージは__init__メソッドに転送されます。これは、 rootと同様にノードを格納するdict似たデータ構造であり、ツリーの「トップ」です。 Noneがrootとして渡された場合、ツリーは空であり、ゼロから動作していると想定します。

_注釈：メソッドの変数がなぜkey / valueだけでなく、 encoded_keyおよびencoded_valueという名前になっているのか疑問に思うかもしれません。 答えは簡単です。仕様によれば、すべてのキーと値はRLPでエンコードする必要があります。 私たちはこれに悩まされず、この職業を図書館利用者の肩に任せます。

ただし、ツリー自体の実装を開始する前に、2つの重要なことを行う必要があります。

1. 手動でエンコードしないように、ニブルのチェーンであるNibblePathクラスを実装します。
2. このクラスのフレームワーク内にNodeクラスを実装するには、 Extension 、 Leaf 、およびBranchます。

ニブルパス

したがって、 NibblePath 。 ツリー内を積極的に移動するため、クラスの機能の基礎は、パスの先頭から「オフセット」を設定する能力と、特定のニブルを受け取る能力である必要があります。 これを知って、クラスの基礎を定義します（また、以下のプレフィックスを操作するためのいくつかの便利な定数）：

 class NibblePath: ODD_FLAG = 0x10 LEAF_FLAG = 0x20 def __init__(self, data, offset=0): self._data = data # ,   . self._offset = offset #      def consume(self, amount): # "" N      . self._offset += amount return self def at(self, idx): #      idx = idx + self._offset #    ,   ,    , #   ,    -      . byte_idx = idx // 2 nibble_idx = idx % 2 #   . byte = self._data[byte_idx] #      . nibble = byte >> 4 if nibble_idx == 0 else byte & 0x0F return nibble 

とても簡単ですね。

ニブルのシーケンスをエンコードおよびデコードするための関数のみを記述することが残っています。

 class NibblePath: # ... def decode_with_type(data): #   : # ,     ,    . is_odd_len = data[0] & NibblePath.ODD_FLAG == NibblePath.ODD_FLAG is_leaf = data[0] & NibblePath.LEAF_FLAG == NibblePath.LEAF_FLAG #    ,     #    . offset  , #       "" . offset = 1 if is_odd_len else 2 return NibblePath(data, offset), is_leaf def encode(self, is_leaf): output = [] #    ,       . nibbles_len = len(self._data) * 2 - self._offset is_odd = nibbles_len % 2 == 1 #  . prefix = 0x00 #    ,    . #      (self.at(0))     . #           (0x0). prefix += self.ODD_FLAG + self.at(0) if is_odd else 0x00 #  ,  Leaf node,  . prefix += self.LEAF_FLAG if is_leaf else 0x00 output.append(prefix) # ,      ,  . pos = nibbles_len % 2 #          , #     2 ,    , #     , #    . while pos < nibbles_len: byte = self.at(pos) * 16 + self.at(pos + 1) output.append(byte) pos += 2 return bytes(output) 

原則として、これはニブルを使用した便利な作業に必要な最小限のものです。 もちろん、現在の実装にはまだいくつかの補助メソッドがあります（たとえば、 combine 、2つのパスを1つにマージするなど）が、それらの実装は非常に簡単です。 興味がある場合は、 ここでフルバージョンを見つけることができます 。

ノード

既に知っているように、ノードはリーフ、エクステンション、ブランチの3つのタイプに分けられます。 それらはすべてエンコードおよびデコードでき、唯一の違いは内部に保存されるデータです。 正直に言うと、これが代数的なデータ型が求められるものであり、たとえばRustでは、私は精神の中で何かを書くでしょう：

 pub enum Node<'a> { Leaf(NibblesSlice<'a>, &'a [u8]), Extension(NibblesSlice<'a>, NodeReference), Branch([Option<NodeReference>; 16], Option<&'a [u8]>), } 

ただし、PythonにはADTがないため、 Nodeクラスを定義し、その中にノードタイプに対応する3つのクラスがあります。 ノードクラスにエンコードを直接実装し、ノードクラスにデコードを実装します。

ただし、実装は基本です。

葉：

 class Leaf: def __init__(self, path, data): self.path = path self.data = data def encode(self): #    --    , #   -  ,   -  . return rlp.encode([self.path.encode(True), self.data]) 

拡張子：

 class Extension: def __init__(self, path, next_ref): self.path = path self.next_ref = next_ref def encode(self): #    --    , #   -  ,   -    . next_ref = _prepare_reference_for_encoding(self.next_ref) return rlp.encode([self.path.encode(False), next_ref]) 

支店：

 class Branch: def __init__(self, branches, data=None): self.branches = branches self.data = data def encode(self): #    --    ,  #  16 -     (  ), #   -   (  ). branches = list(map(_prepare_reference_for_encoding, self.branches)) return rlp.encode(branches + [self.data]) 

すべてが非常に簡単です。 質問を引き起こす可能性があるのは、 _prepare_reference_for_encoding関数のみです。

それから私は、小さな松葉杖を使わなければならなかったことを告白します。 実際、 rlpているrlpライブラリはデータを再帰的にデコードし、別のノードへのリンクはrlpデータになる可能性がrlpます（エンコードされたノードの長さが32文字未満の場合）。 2つの形式（ハッシュバイトとデコードされたノード）でリンクを操作するのは非常に不便です。 したがって、ノードをデコードした後、バイト形式でリンクを返し、保存する前に必要に応じてデコードする2つの関数を作成しました。 これらの機能は次のとおりです。

 def _prepare_reference_for_encoding(ref): #    ( ,   ) --  . #       :) if 0 < len(ref) < 32: return rlp.decode(ref) return ref def _prepare_reference_for_usage(ref): #     -   . #          . if isinstance(ref, list): return rlp.encode(ref) return ref 

Nodeクラスを作成して、 Node終了します。 その中に2つのメソッドのみがあります：ノードをデコードし、ノードをリンクに変えます。

 class Node: # class Leaf(...) # class Extension(...) # class Branch(...) def decode(encoded_data): data = rlp.decode(encoded_data) # 17  -  Branch . if len(data) == 17: branches = list(map(_prepare_reference_for_usage, data[:16])) node_data = data[16] return Node.Branch(branches, node_data) #    17,   2.   - . #      ,     . path, is_leaf = NibblePath.decode_with_type(data[0]) if is_leaf: return Node.Leaf(path, data[1]) else: ref = _prepare_reference_for_usage(data[1]) return Node.Extension(path, ref) def into_reference(node): #    . #      32 , #   -   . #       . encoded_node = node.encode() if len(encoded_node) < 32: return encoded_node else: return keccak_hash(encoded_node) 

休憩

ふう！ 多くの情報があります。 リラックスする時間だと思います。 ここにあなたのための別の猫があります：

ミロタ、そう？ さて、私たちの木に戻りましょう。

マークルパトリシア

万歳-補助要素は準備ができています、私たちは最もおいしいに渡します。 念のため、ツリーのインターフェイスを思い出させます。 同時に、 __init__メソッドを実装します。

 class MerklePatriciaTrie: def __init__(self, storage, root=None): self._storage = storage self._root = root def root(self): pass def get(self, encoded_key): pass def update(self, encoded_key, encoded_value): pass def delete(self, encoded_key): pass 

ただし、残りのメソッドでは、1つずつ処理します。

得る

getメソッド（原則として、他のメソッドとして）は2つの部分で構成されます。 メソッド自体がデータを準備し、結果を期待される形式にしますが、実際の作業は補助メソッド内で行われます。

基本的な方法は非常に簡単です。

 class MerklePatriciaTrie: # ... def get(self, encoded_key): if not self._root: raise KeyError path = NibblePath(encoded_key) #       #  ,    ,    . result_node = self._get(self._root, path) if type(result_node) is Node.Extension or len(result_node.data) == 0: raise KeyError return result_node.data 

ただし、 _getそれほど複雑で_getません。目的のノードに到達するには、ルートから指定されたパス全体に移動する必要があります。 最後にデータ（リーフまたはブランチ）を持つノードが見つかった場合、データは受信されます。 成功しなかった場合、必要なキーがツリーにありません。

実装：

 class MerklePatriciaTrie: # ... def _get(self, node_ref, path): #      . node = self._get_node(node_ref) #    --   . #   ,      . if len(path) == 0: return node if type(node) is Node.Leaf: #     Leaf-,     , #      . if node.path == path: return node elif type(node) is Node.Extension: #    -- Extension,    . if path.starts_with(node.path): rest_path = path.consume(len(node.path)) return self._get(node.next_ref, rest_path) elif type(node) is Node.Branch: #    -- Branch,     . #   ,           #  :      . branch = node.branches[path.at(0)] if len(branch) > 0: return self._get(branch, path.consume(1)) #    ,        , #     . raise KeyError 

同時に、ノードを保存およびロードするためのメソッドを作成します。 それらは単純です：

 class MerklePatriciaTrie: # ... def _get_node(self, node_ref): raw_node = None if len(node_ref) == 32: raw_node = self._storage[node_ref] else: raw_node = node_ref return Node.decode(raw_node) def _store_node(self, node): reference = Node.into_reference(node) if len(reference) == 32: self._storage[reference] = node.encode() return reference 

更新する

update方法はすでに興味深いものです。 最後に到達してリーフノードを挿入するだけでは、常にうまくいくとは限りません。 キー分離ポイントは、すでに保存されているリーフまたは拡張ノード内のどこかにある可能性があります。 この場合、それらを分離し、いくつかの新しいノードを作成する必要があります。

一般に、すべてのロジックは次のルールで記述できます。

1. パスは既存のノードと完全に一致しますが、再帰的にツリーを下降します。
2. パスが終了し、ブランチノードまたはリーフノードにいる場合、 update単にこのキーに対応する値をupdateことを意味します。
3. パスが分割されている場合（つまり、値を更新せずに新しいパスを挿入する場合）、ブランチノードにいる場合は、リーフノードを作成し、対応するブランチブランチブランチにリンクを提供します。
4. パスが分割されており、リーフノードまたは拡張ノードにいる場合、パスを分離するブランチノードを作成する必要があり、必要に応じて、パスの共通部分の拡張ノードを作成する必要があります。

これを徐々にコードで表現しましょう。 なぜだんだん？ メソッドが大きく、一括して理解するのが難しいためです。
ただし、 ここで完全なメソッドへのリンクを残します 。

 class MerklePatriciaTrie: # ... def update(self, encoded_key, encoded_value): path = NibblePath(encoded_key) result = self._update(self._root, path, encoded_value) self._root = result def _update(self, node_ref, path, value): #       (,   ), #       . if not node_ref: return self._store_node(Node.Leaf(path, value)) #          #    . node = self._get_node(node_ref) if type(node) == Node.Leaf: ... elif type(node) == Node.Extension: ... elif type(node) == Node.Branch: ... 

一般的なロジックは十分ではありません。最も興味深いのはifの内部if 。

if type(node) == Node.Leaf

最初に、リーフノードを扱いましょう。 それらで可能なシナリオは2つだけです。

1. 私たちがたどっている残りのパスは、リーフノードに保存されているパスとまったく同じです。 この場合、値を変更し、新しいノードを保存してリンクを返すだけです。

   
   

2. パスが異なります。
   この場合、2つのパスを分離するブランチノードを作成する必要があります。
   パスの1つが空の場合、その値はブランチノードに直接転送されます。
   それ以外の場合、パスの共通部分の長さ+ 1ニブル（このニブルは、Branchノードの対応するブランチのインデックスで示されます）で短縮された2つのリーフノードを作成する必要があります。

   
   

また、拡張ノードも作成する必要があるかどうかを理解するために、パスの共通部分があるかどうかを確認する必要があります。

コードでは、次のようになります。

 if type(node) == Node.Leaf: if node.path == path: #  .       . node.data = value return self._store_node(node) #    . #    . common_prefix = path.common_prefix(node.path) #      . path.consume(len(common_prefix)) node.path.consume(len(common_prefix)) #  Branch . branch_reference = self._create_branch_node(path, value, node.path, node.data) # ,    Extension-. if len(common_prefix) != 0: return self._store_node(Node.Extension(common_prefix, branch_reference)) else: return branch_reference 

_create_branch_nodeプロシージャは次のとおりです。

 def _create_branch_node(self, path_a, value_a, path_b, value_b): #    Branch-. branches = [b''] * 16 # ,     Branch- . branch_value = b'' if len(path_a) == 0: branch_value = value_a elif len(path_b) == 0: branch_value = value_b #    Leaf-,  . self._create_branch_leaf(path_a, value_a, branches) self._create_branch_leaf(path_b, value_b, branches) #  Branch-     . return self._store_node(Node.Branch(branches, branch_value)) def _create_branch_leaf(self, path, value, branches): # ,     Leaf-. if len(path) > 0: #    ( ). idx = path.at(0) #  Leaf-   ,     . leaf_ref = self._store_node(Node.Leaf(path.consume(1), value)) branches[idx] = leaf_ref 

if type(node) == Node.Extension

拡張ノードの場合、すべてがリーフノードのように見えます。

1. Extensionノードからのパスがパスのプレフィックスである場合、単純に再帰的に進みます。

   
   

2. それ以外の場合は、上記の場合のように、分岐ノードを使用して分離を行う必要があります。

   
   

したがって、コード：

 elif type(node) == Node.Extension: if path.starts_with(node.path): #         . new_reference = \ self._update(node.next_ref, path.consume(len(node.path)), value) return self._store_node(Node.Extension(node.path, new_reference)) #  Extension-. #     . common_prefix = path.common_prefix(node.path) #  . path.consume(len(common_prefix)) node.path.consume(len(common_prefix)) #  Branch- ,  ,    . branches = [b''] * 16 branch_value = value if len(path) == 0 else b'' #     Leaf-  Extension- . self._create_branch_leaf(path, value, branches) self._create_branch_extension(node.path, node.next_ref, branches) branch_reference = self._store_node(Node.Branch(branches, branch_value)) # ,    Extension-. if len(common_prefix) != 0: return self._store_node(Node.Extension(common_prefix, branch_reference)) else: return branch_reference 

_create_branch_extensionプロシージャ_create_branch_extension 、 _create_branch_extensionプロシージャ_create_branch_extension論理的に同等_create_branch_extension 、Extensionノードで機能します。

if type(node) == Node.Branch

しかし、ブランチノードでは、すべてが簡単です。 パスが空の場合、新しい値を現在のブランチノードに保存するだけです。 パスが空でない場合-パスから1ニブルを「噛んで」再帰的に低くなります。

コードにはコメントは必要ないと思います。

 elif type(node) == Node.Branch: if len(path) == 0: return self._store_node(Node.Branch(node.branches, value)) idx = path.at(0) new_reference = self._update(node.branches[idx], path.consume(1), value) node.branches[idx] = new_reference return self._store_node(node) 

削除する

ふう！ 最後のメソッドは残ります。 彼は最も陽気です。 削除の複雑さは、削除されたキーだけを除いて、 updateチェーン全体を実行した場合に落ちていた状態に構造を戻す必要があることです。

そうしないと、同じデータを含む2つのツリーでルートハッシュが異なる状況が発生する可能性があるため、これは非常に重要です。 "", , .

. , N- , N+1 . enum — DeleteAction , .

delete :

 class MerklePatriciaTrie: # ... # Enum, ,         . class _DeleteAction(Enum): #    . #     , #        (_DeleteAction, None). DELETED = 1, #    (,    ). #     ,    #    : (_DeleteAction, ___). UPDATED = 2, #    Branch-  .   -- #    : # (_DeleteAction, (___, ___)) USELESS_BRANCH = 3 def delete(self, encoded_key): if self._root is None: return path = NibblePath(encoded_key) action, info = self._delete(self._root, path) if action == MerklePatriciaTrie._DeleteAction.DELETED: #   . self._root = None elif action == MerklePatriciaTrie._DeleteAction.UPDATED: #   . new_root = info self._root = new_root elif action == MerklePatriciaTrie._DeleteAction.USELESS_BRANCH: #   . _, new_root = info self._root = new_root def _delete(self, node_ref, path): node = self._get_node(node_ref) if type(node) == Node.Leaf: pass elif type(node) == Node.Extension: pass elif type(node) == Node.Branch: pass 

, get update . . .

if type(node) == Node.Leaf

. . — , , .

:

 if type(node) == Node.Leaf: if path == node.path: return MerklePatriciaTrie._DeleteAction.DELETED, None else: raise KeyError 

, "" — . , . .

if type(node) == Node.Extension

C Extension- :

1. , Extension- . — .
2. _delete , "" .
3. . 可能なオプション：

• . .
• . .
• Branch-. . , Branch- . , , Leaf-. — Extension-.

コードでは、次のようになります。

 elif type(node) == Node.Extension: if not path.starts_with(node.path): raise KeyError #   . #       . action, info = self._delete(node.next_ref, path.consume(len(node.path))) if action == MerklePatriciaTrie._DeleteAction.DELETED: return action, None elif action == MerklePatriciaTrie._DeleteAction.UPDATED: #    ,     . child_ref = info new_ref = self._store_node(Node.Extension(node.path, child_ref)) return action, new_ref elif action == MerklePatriciaTrie._DeleteAction.USELESS_BRANCH: #     Branch-. stored_path, stored_ref = info # ,     Branch-. child = self._get_node(stored_ref) new_node = None if type(child) == Node.Leaf: #  branch-  . #     Leaf-  Extension. path = NibblePath.combine(node.path, child.path) new_node = Node.Leaf(path, child.data) elif type(child) == Node.Extension: #  Branch-  Extension-. #       . path = NibblePath.combine(node.path, child.path) new_node = Node.Extension(path, child.next_ref) elif type(child) == Node.Branch: #  Branch-      Branch-. #    Extension-    . path = NibblePath.combine(node.path, stored_path) new_node = Node.Extension(path, stored_ref) new_reference = self._store_node(new_node) return MerklePatriciaTrie._DeleteAction.UPDATED, new_reference 

if type(node) == Node.Branch

.

まあ、ほとんど。 Branch-, …

なんで？ Branch- Leaf- ( ) Extension- ( ).
, . , — Leaf-. — Extension-. , , 2 — Branch- .

? :

:

1. , .
2. , _delete .

:

 elif type(node) == Node.Branch: action = None idx = None info = None if len(path) == 0 and len(node.data) == 0: raise KeyError elif len(path) == 0 and len(node.data) != 0: node.data = b'' action = MerklePatriciaTrie._DeleteAction.DELETED else: #   ,    . #    . idx = path.at(0) if len(node.branches[idx]) == 0: raise KeyError action, info = self._delete(node.branches[idx], path.consume(1)) #  ,   ,  . #      -    #    . node.branches[idx] = b'' 

_DeleteAction .

1. Branch- , ( , ). .

 if action == MerklePatriciaTrie._DeleteAction.UPDATED: #   . next_ref = info node.branches[idx] = next_ref reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.UPDATED, reference elif action == MerklePatriciaTrie._DeleteAction.USELESS_BRANCH: #    . _, next_ref = info node.branches[idx] = next_ref reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.UPDATED, reference 

1. ( , ), , .

. 可能なオプション：

• . , , , . , .
• , . Leaf- . .
• , . , , .
• , , Branch- . , _DeleteAction — UPDATED .

 if action == MerklePatriciaTrie._DeleteAction.DELETED: non_empty_count = sum(map(lambda x: 1 if len(x) > 0 else 0, node.branches)) if non_empty_count == 0 and len(node.data) == 0: # Branch- ,  . return MerklePatriciaTrie._DeleteAction.DELETED, None elif non_empty_count == 0 and len(node.data) != 0: #  ,   . path = NibblePath([]) reference = self._store_node(Node.Leaf(path, node.data)) return MerklePatriciaTrie._DeleteAction.USELESS_BRANCH, (path, reference) elif non_empty_count == 1 and len(node.data) == 0: #  ,   . return self._build_new_node_from_last_branch(node.branches) else: #  1+   ,  2+ . # Branch-  ,   - UPDATED. reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.UPDATED, reference 

_build_new_node_from_last_branch .

— Leaf Extension, , .

— Branch, Extension , , Branch.

 def _build_new_node_from_last_branch(self, branches): #    . idx = 0 for i in range(len(branches)): if len(branches[i]) > 0: idx = i break #     . prefix_nibble = NibblePath([idx], offset=1) #     child = self._get_node(branches[idx]) path = None node = None #   . if type(child) == Node.Leaf: path = NibblePath.combine(prefix_nibble, child.path) node = Node.Leaf(path, child.data) elif type(child) == Node.Extension: path = NibblePath.combine(prefix_nibble, child.path) node = Node.Extension(path, child.next_ref) elif type(child) == Node.Branch: path = prefix_nibble node = Node.Extension(path, branches[idx]) #  . reference = self._store_node(node) return MerklePatriciaTrie._DeleteAction.USELESS_BRANCH, (path, reference) 

. , … root .

ここに：

 class MerklePatriciaTrie: # ... def root(self): return self._root 

, .

… . , , Ethereum . , , , . , :)

, , pip install -U eth_mpt — .

結果

?

, -, , - , , . — , .

-, , , — . , skip list interval tree, — , , .

-, , . , - .

-, — .

, , — !

: 1 , 2 , 3 . ! , .