タグ: "Merkle tree"

イーサリアム(Ethereum)のデータ構造~マークルパトリシアツリー

イーサリアム(Ethereum)のデータ構造~マークルパトリシアツリー

2018/05/10 at 5:55 PM 0 comments
はじめに 前回の記事で説明したように、イーサリアム(Ethereum)上ではユーザーの残高は、Account Stateで管理されています。そしてこのAccount Stateは、ブロックチェーンには含まれません。しかし、この仕組みでは異なるノード(マイナー)同士で各アカウントが持っている残高などの合意が取れないため、発行された全てのアカウントから抽出されるState rootという値を、ブロックチェーンに刻むことによって合意を取ることを説明しました。その際、State Rootはマークルツリーなどを用いて計算されることを述べましたが、その詳細は割愛しました。 そこで今回は、①State Rootの計算方法と②State変更が生じた際のState Rootの再計算方法について解説します。まずはじめに、Sate Rootがどのように計算されるのかについて説明します。さらに、トランザクションによってアカウントのStateが変更された時に、どのようにその変更が伝わって、State Rootが計算され直すかについて説明していきます。 イーサリアム(Ethereum)上でのデータ管理 前節で述べたように、各アカウントの状態はブロックチェーンには刻まれません。そのため、改ざんに対して耐性を持たせる必要があります。また、全てのStateをノードのコンピュータに保存するので、データ容量を小さくする必要もあります。さらに、約15秒に1度ブロックが生成されるので、その都度、アカウントの状態(残高など)の変更をState Rootに反映させる必要があります。State Rootに変更を反映するには、はじめに当該アカウントの検索をし、当該アカウントの状態を変更した後、変更があった全てのアカウントを元に計算されたハッシュ値をブロックに書き込む、といったステップが必要です。 そのためアカウントの状態は、以下の条件を満たすように保存されるのが望ましいと考えられます。 データ構造が改ざんに対して耐性を持っている。 データ容量を抑えられる。効率的に保持できる。 検索、データの挿入、削除が早く容易。 イーサリアムのKeyとvalue イーサリアム(Ethereum)では、各アカウントのアドレスとそのアカウントの残高が紐づいています。そのため特定のトランザクションがあった時に、トランザクションに記述されているアドレスをもとに、コンピューターが変更を加えるべきアカウントを探しに行きます。 このとき、特定の情報を探すためのキーワードをKeyと呼び、探すもの自体をvalueとよびます。イーサリアム(Ethereum)の場合、Keyはユーザーのアドレスに対応し、ValueはAccount Stateとなります Tree(ツリー) ここまでで準備ができたので、上であげた要件を満たすための仕組みについて考えていきましょう。ここでは、まず基礎となるPrefix Treeについて説明します。その後、Patricia TreeとMerkle Treeについて説明し、最後にイーサリアム(Ethereum)で用いられているMerkle Patricia Treeについて述べます。 Prefix Tree(プレフィックスツリー) イーサリアム(Ethereum)では、トランザクションに応じてアカウント状態をその都度変更する必要があります。その際、状態に変更があったアカウントの検索を高速にする必要があります。 イーサリアム(Ethereum)における検索の仕組みに入る前に、まずは検索のイメージを掴んでもらいたいと思います。例としてA,B,C,D のアルファベットからなる4文字の文字列を複数並べて見ました。並べ方は二種類用意してあります。文字列を不規則に並べた場合と、樹形図状に並べた場合です。 それでは以下に示す二つの図からBCDAという文字列を探してみてください。 不規則に並ぶ文字列(下図) すぐに見つけられたでしょうか? では、同じBCDAを次の樹形図状の配列の中から探してください。これは簡単ですね。この樹形図がBから始まる図では、上から順にB→C→D→Aというように探している文字を追って行くことで、目的物にたどり着ける構造になっています。 樹形図状に並ぶ文字列(下図) どうでしょうか? 仕組みさえわかってしまえば、樹形図状の構造の方が整理されていて、すぐに見つけられることが実感できたと思います。また、データの数がさらに多くなると、この樹形図はさらに威力を増します。(辞書などが良い例です) 。このデータ構造のことをPrefix Treeと呼びます。 EthereumにおけるPrefix Treeの考え方 これをEthereumに対応させて考えて見ましょう。上の文字列でBCDAなどのアルファベットに対応する部分は、Ethereumのアドレスに対応します。例えば、6f46cf5569aefa1acc100929・・・というkeyに紐づくアカウントの状態(value)を探す場合は、6→f→4→6・・・のようにtreeをたどることですぐに見つけることができます!! Patricia Tree(パトリシアツリー) Patricia Treeは、Prefix Treeをデータの容量面でさらに進化させて、データ量を軽量化させた構造です。比較のために先ほどのPrefix TreeとPatricia Treeの図を示します。 Prefix Tree(下図) はじめにあげた図とは異なり、BACD、BCADというアドレスをもつアカウントがないとしましょう。このとき、一番左側(BADCの枝)の経路のようにAからは必ずDに行く分岐のない経路が現れます。このような場合、AとDを別々に保存する必要がなくまとめてしまおうというのがPatricia Treeの考え方です。以下のようにADをまとめて保存することでデータ容量を節約して軽量化した構造を作ることができます。ちなみに、Patricia Treeは、Radix Treeとも呼ばれることもあります。 Patricia Tree(下図) Merkle Tree(マークルツリー) Merkle Treeは、大きなデータを要約し、その値を検証することでデータが改ざんされていないかを検証できる構造のことです。要約の際に、ハッシュ関数を用います。そのためハッシュツリーとも呼ばれます。ハッシュ関数とは任意の長さの文字列を入力したとき、一定の長さの入力文字列を反映した文字列を出力する関数です。早速、Ethereumの場合でこの要約の方法について見ていきましょう。 EthereumにおけるMerkle Treeの考え方 前回の記事でも述べたように、Account Stateには四つの情報(nonce,code,storage,残高)がありました。この情報をつなぎ合わせて要約(ハッシュ関数に入れる)して、一つのハッシュ値(要約した値なのでダイジェスト値とも呼びます)を得ます。例えば、 hash(nonce)が17で、codeはなくて残高は0.17ethでstorageには何もない)=ba57d3f1ef8・・・ というようにです。(実際には日本語ではありません。) アカウントの情報が要約できたら、この要約を他のアカウントの要約値と合わせてさらに要約します。 下図は、その要約構造を示しています。HAはアカウントA(一番左のアカウント)を、HBはアカウントB(左から二番目のアカウント)を要約したハッシュ値です。これらをまたハッシュ関数に入れてさらに要約値を得ます。これを繰り返すことで、図の一番上のRoot値が得られます。 注意すべきことは、最下層のアカウントの情報が少しでも書き変わると、このRoot値が全く異なる値に変化します。このようにして、アカウントの状態が改ざんされていないかどうかを、この要約値を使って瞬時にチェックできる仕組みがMerkle Treeです。 また、前回の記事で紹介したTransaction RootもReceipts Rootも、どちらもこの構造を用いていて、データの検証を行なっています。 Merkle Tree(下図) ハッシュ化、ハッシュ関数に関しては、以前の記事を参考にしてください。 [イーサリアムアドレス 〜EIP-55によるチェックサムの導入〜](https://consensysmediajapan.com/4443.html#chapter-4) Merkle Patricia Tree(マークルパトリシアツリー) 上であげたPatricia TreeとMerkle Treeを合わせることで、三つの要件を満たすデータ構造が作れます。それがMerkle Patricia treeです。 はじめに述べたように、Ethereumではブロック生成時間が15秒程度に一度なので、トランザクションが起きたらすぐに関連するアカウントをPatricia Treeから探してきて残高などを変更し、さらに改ざんに対して耐久を持たせるために、変更後の要約(ハッシュ)値をすぐに計算する必要があります。 実は、Merkle Treeは以下の図にあるように、変更が加えられたハッシュ値以外は変わらないので、着目しているトランザクションに関係ないアカウントの要約値は変更しないような仕組みなっています。そのため例えば、アカウントC(左から三つ目)の状態が変わったとしても左側の分岐のハッシュ値は変わらないので、ハッシュをすぐに計算する構造も備わっています。 Merkle Tree(Account Stateの変更)(下図) それでは、最後にMerkle Patricia Treeがどのような構造でできているか考えていきましょう。 以下では、Key(ユーザーのアドレスに対応する値)が7b2d(便宜上、4桁の場合を考えています。)であるアカウントに紐づくAccount Stateを見つけにいきましょう。7→b→2→dとたどることでアカウントにたどり着けるはずです。そこで、下図にあるように、16進数なので0,1,2,・・・fの中から7の四角に進みます。 ここで、ポインターと呼ばれる次にどこのデータの塊を参照すればいいかを示すある値を得ます。今回、7に紐づく値は、a85fだったとしましょう。(もちろん、他の値にもそれぞれ特定のポインターが紐づいています。) 今度は、この値を参考にa85fに紐づくデータの塊のなかで、ユーザーのアドレスの7の次のbの値に対応するポインターを参照します。そこには、3aa7とかいてあるのでその値に対応するデータの塊を参照します。これを繰り返すことで、目的であるアドレスが0x7b2dのAccount Stateにたどりつけます。 ここで、ポイントとなるのは、今まで参照してきた謎のポインターの値は、実は複数のアカウントから抽出された要約(ハッシュ)値であったということです。Merkle Patricia treeの最下層には、全てのAccount Stateが紐づきそれの要約値が、まとめられてその情報の塊を参照するポインターの役割をしているわけです。   このような構造によって、Etherrumのカウント構造は効率よく変更され管理されているわけです。この構造は、うまくできていて感動します。 まとめ Merkle Patricia Tree の構造は、少々複雑です。ですが、解説記事があまり少なかったため今回まとめました。もっと詳しい実装に関しては、Ethereumのgithubが参考になります。わからないところがあれば下記のコメントからも質問を受け付けます。 [Patricia Tree](https://github.com/ethereum/wiki/wiki/Patricia-Tree)