タグ: "Account State"

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

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

2018/05/10 at 5:55 PM 1 comment
はじめに 前回の記事で説明したように、イーサリアム(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)
イーサリアム(Ethereum)のブロック構造とその仕組み

イーサリアム(Ethereum)のブロック構造とその仕組み

2018/04/17 at 4:44 PM 0 comments
はじめに 今回の連載記事では、イーサリアム(Ethereum)ブロックの構造を、ビットコイン(Bitcoin)などと比較しながら解説します。 はじめに、イーサリアム(Ethereum)におけるユーザーのアカウントや、スマートコントラクトなどの情報がどのように管理されているかについて、解説します。次に、Ethereumブロックの構造をBitcoinなどと比較しながら解説します。 ぜひ、この機会にEthereumのブロックがどのような情報を持っていて、どのように承認されるかについて学んでいきましょう。 Ethereum Account イーサリアム(Ethereum)のアカウントには、以下の二種類があります。 外部アカウント・・・EOA(Externally Owned Account)とも呼ばれます。Ethereumを利用するユーザーが保持しているアカウント。秘密鍵によってコントロールされます。 コントラクトアカウント・・・CA(Contract Account)とも呼ばれます。コントラクトに紐づくアカウントでコントラクトに関するコードや情報を持つアカウント。コントラクトアカウントは、秘密鍵は持っていません。 これらのアカウントは、どちらも20byteのアドレスと状態(State)と呼ばれる情報を持っています。このStateについては以下で説明します。また、コントラクトアカウントは、外部アカウントから作成されます。 実際にどのようにしてアドレスが生成されるかなどの詳細は、以下の記事が参考になります。 (参考:イーサリアムアドレス 〜EIP-55によるチェックサムの導入〜https://consensysmediajapan.com/4443.html) Account State アカウントの状態には、以下の4つの情報が含まれます。 どちらのアカウントも共通して、「残高(Balance)、nonce」を記録する部分を持っています。アカウントが持つnonceは、二重支払いを防ぐ役割をしています。着目しているアカウントが行うトランザクションの回数を記録するカウンターとして作用し、トランザクションは、このnonceの小さい方から順にブロックに詰められるようになっています。 そしてコントラクトアカウントのみが、コード(code)、ストレージ(storage)というスマートコントラクトのコードとデータを保存する部分を持っています。外部アカウントの場合、コード、ストレージは無く、空です。 このように、Ethereumでは、アカウントごとの残高が明示的に管理されています。これは、Bitcoinと異なる点です。Bitcoinでは、各アカウントごとに残高が管理されていません。散らばっているUTXOをかき集めることによって、着目しているアカウントがもつ残高を計算しています。そのため、Bitcoinではブロックチェーンから残高を導出する時間計算量も問題視されています。ビットコインのUTXOについては以下の記事が参考になります。 (参考:イーサリアムを理解するためにビットコインの基本を理解しようhttps://consensysmediajapan.com/2485.html) State Root 上であげた全てのアカウントの状態をEthereumのブロックに入れておこうとすると、ブロックのサイズがとてつもなく肥大化してしまいます。そこで、Ethereumでは以下の図に表すように、全てのアカウントの状態をマークルパトリシアツリー(下図の木構造のこと)によって管理しています。(Ethererumでは、すべてのアカウントの状態を記録して管理している全体を特にWorld Stateと呼びます。) すなわち、全てのアカウントの状態ではなく、全てのアカウントのハッシュ値を掛け合わせて作られたState rootと呼ばれるハッシュ値のみがブロックの中に格納され記録されます。このState rootは全てのアカウントのハッシュから計算されるので、いずれかのアカウントの状態が改ざんされると、このstate rootも変わってきます。そのため改ざんなどを防ぐ役割も担っています。 ちなみに、アカウントのStateはブロック内には保存されませんが、マークルパトラシアツリーの状態で各ノードに保存されています。また、全てのアカウントのStateは、ブロック内に保存されている全てのトランザクションから推測、生成することができます。 一番下の段が各アカウントであり、複数のアカウントがもつStateを繋げてハッシュ化することで、全てのアカウントの情報を含む一番上のState Rootが作られます。(マークルツリーなどでは一番上の値をRootと呼びます。) 今回は、あくまでブロックの構造を知ってもらうことをメインに解説しています。 そのためマークルツリーについては次回の記事で詳しく取り上げることにします。 次に、ブロックの中に保存されている項目について整理していきましょう。 ブロック構造 イーサリアム(Ethereum)のブロック構造は、ビットコイン(Bitcoin)のそれに対して複雑です。まず、ハッシュ化されるブロックヘッダーと呼ばれる「ブロックの核」となる部分について比較してみましょう。 BitcoinのBlock Header Bitcoinの場合は,ブロックヘッダーには以下の情報が含まれます。 - nVersion・・・現在のBitcoinのバージョン - hashPrevBlock・・・一つ前のブロックのブロックヘッダーのハッシュ値 - hashMerkleRoot・・・複数トランザクションを先ほど述べたマークルツリーで処理したRoot値 - nTime・・・現在のタイムスタンプ(おおよそ現在の時刻が記録されます) - nBits・・・difficulty(難易度)に関する値。目標とするbit数が入り、この値よりも小さな値になるよう計算を行います。 - nNonce・・・マイナーが選べる任意の値。上にあげたハッシュなどと合わせて、現在のblockから計算されるハッシュが、設定されているtargetよりも小さな値になるように決定します。 これら6つの要素から成り立っています。 ビットコイン(Bitcoin)のブロックチェーンに内包されるBlock header(下図) EthereumのBlock Header 次に、Ethereumのブロックヘッダーについてです。こちらは、項目がBitcoinに比べ格段に多くなります。 Ethereumは、ブロック生成時間が10分であるBitcoinとは異なり、13~15秒と40倍も速い速度でブロックの生成が行われます。 しかし、承認速度が早いということは、計算の難易度が比較的に容易で、すぐにフォークが起きてしまいます。そのため、Ethereumには、承認されなかったブロックに対しても分け前を与えるシステムがあります。また、このときに、承認されずフォークしてしまったブロックのことをUncleブロックと呼びます。このUncleブロックのハッシュ値なども現在のブロックに取り入れられる構造になっています。また、Gasと呼ばれるマイナーに働いてもらうための手数料も特徴的です。 - ParentHash・・・一つ前のブロックのブロックヘッダーのハッシュ値 - UnclesHash・・・Uncle ブロックのブロックヘッダーのハッシュ値(OmmersHash/sha256Unclesとも呼ばれる) - Timestamp・・・現在のタイムスタンプ - Difficulty・・・ブロックを生成する難易度.これ以前のブロックの難易度とTimestampから算出される.Bitcoinとは異なり難易度調整はブロック毎に変動します。 - Nonce・・・マイナーが選べる任意の値。ここにあげたhashなどと合わせて、現在のblockから計算されるhashが、設定されているtargetよりも小さな値になるように決めます。 - TxTrieRoot・・・トランザクションをマークルツリーで処理したRoot値 - Coinbase・・・ブロック生成のマイニング報酬を受け取るアドレス(minerとも呼ばれる) - LogsBloom・・・トランザクションに関連する内容と、それに付随する内容がブルームフィルタと呼ばれる空間効率の良い形で保存されています。(詳しくは,次回以降の記事で紹介する予定です。) - Number・・・ブロック高,現在のブロック数を表します。 - GasLimit・・・このブロックで使用できる最大のGasサイズ - GasUsed・・・このブロックで使用されたGasの使用量 - ExtraData・・・ブロックに関連する任意の情報を記録する場所. - MixHash・・・このブロックで十分な計算が実行されたことを証明するハッシュ - ReceiptsRoot・・・ブロックに入っているトランザクションの実行結果を先ほどのマークルツリーで処理して保存しています。. - StateRoot・・・先述した通り、Ethereum上の全アカウントの情報から得られるハッシュ値(KECCAK-256)。アカウントのstateはblockの外で管理され、ノード値のみブロックに格納されます。 合計15個から構成されています。(正確には、UncleBlockのhash値とUncle BlockのBlockheaderも含まれます。これを含めれば17個の要素から構成されていることになります。) 下図のように、BitcoinとEthereumとの対応が取れるものについては、上図と同じ色で統一しました。 イーサリアム(Ethereum)のブロックチェーンに内包されるBlock header(下図) イーサリアム(Ethereum)ブロック構造のまとめ 今回は、Ethereumのブロック構造について解説しました。今までよりも、ブロックにどのようなデータが格納されているか、具体的に理解が深まったのではないでしょうか。 最後に、イーサリアムのブロック構造をまとめます。上で述べたブロックヘッダーは、ブロックの中でたくさんの要素が含まれている大切な部分です。 Ethereumのブロックには、他にも各ブロックごとに、その時起きたトランザクションを保管する部分があります。これには、Uncleブロックの分も含まれます。このように大きく分けると三つの要素からブロックが構成されています。(下図) このブロックが連続的に繋がっていくことでブロックチェーンが長く長く伸びて行くのです。 イーサリアム(Ethereum)のブロックに格納される3要素(下図) 次回以降は、今回触れることができなかったトランザクションやGasなどについても詳しく解説して行きます。