クリプト

【python】マークルツリーを作ってみた

がくし's icon'
  • がくし
  • 2018/11/01 15:37

Content image


●著者

Content image

がくしです。






Content image


●目的

マークルツリーを理解するにあたって、プログラミングができるなら日本語よりコード読んだほうが早いだろうと思い、実際に作ってみました。


Content image


●概略

マークルツリーとは、データ群の要約を作成し、要約と元データの整合性を見ることで、改ざんが行われてないか検証をする技術です。その際に、データ群の一部のみを知ってるだけで、検証が可能な事がポイントとなります。


この仕組みは、walletを使う際に役立っています。walletがブロックチェーン上の全てのトランザクションデータを持つと重くなってしまうので、代わりに要約されたデータだけを持っています。しかしそれだけだと、トランザクションデータが見れないので、自身のアドレスの残高を参照することが出来ません。そこで、自身のアドレスのみを使って改ざんの有無を検証した上で、元データから自身のトランザクションデータを取得します。


Content image


●図解

サトシ・ナカモトの論文の図がわかりやすいです。

Content image

マークルツリーの概要です。各Txがトランザクションを表しています。それぞれのハッシュ値を連結したものを更にハッシュ化する事を繰り返し、Root Hash(マークルルート)を算出します。トランザクションからマークルルートに至るツリー構造を、マークルツリーと呼びます。また、マークルルートを含むブロックの要約(Block Header)のみを、walletは保持します。


Content image

マークルパスの概要です。マークルルートは、全てのトランザクションを知らなくても算出できます。図のように、Tx3/Hash2/Hash01の値だけで、マークルルートを算出できます。この算出に必要な最低限の値を、マークルパスと呼びます。マークルパスから算出したハッシュ値と、walletが既に持っているハッシュ値が一致することが、改ざんが行われていないことの証明となります。


Content image


●コード全文

まず全体をざっくり見てみましょう。

詳細は後述するので、雰囲気だけ見てください。

・Nodeクラス
・Treeクラス
・caluculator関数

の、3つから構成されています。

それぞれ見ていきましょう。


Content image


●Nodeクラス

【プロパティ】

・left       :子ノード(左)
・right     :子ノード(右)
・parent  :親ノード
・sibling  :兄弟ノード
・position:兄弟ノードとの位置関係
・data     :元のデータ
・hash     :ハッシュ値


・left/right/parent

親ノードと子ノードを格納しています。各ノードが親子関係のデータを持つことで、ツリー上の構造を表現します。


・sibling/position

siblingは、共通の親を持つ隣のノードです。positionは、siblingとの位置関係で、leftかrightの文字列を格納します。これらは、マークルパス作成時に使います。


・data/hash

保管したいデータと、それのハッシュ値です。ここではsha256関数を使ってハッシュ化してます。


Content image


●Treeクラス

【プロパティ】

・leaves:ツリーの末端のノード
・layer  :現在の最上層のノード集
・root   :マークルルート

・leaves

最下層のノード群です。元データを格納してるので、後述するsearchメソッドで使います。


・layer

ツリーを作成する最中の、最上層のノード群です。こちらはbuild_layerメソッドで使います。


・root

マークルルートです。


【メソッド】

・__init__     :初期化
・build_layer:layerを一つ上の階層のものに上書き
・build_tree :tree全体の作成
・search      :所望のデータを格納するnodeの検索
・get_pass   :マークルパスの作成



・__init__

文字列のリストとして受け取ったデータ群を、ノードのリストに変換してleavesに格納しています。また、そのleavesが最初の層になるので、コピーしたものをlayerに格納しています。


・build_layer

現在の最上層であるlayerの一個上の層をnew_layerとして作成し、最後にそれをlayerに上書きしています。各ノードの親子関係等の記入も、ここで行っています。また、layerのノード数が奇数だった場合、最後尾のノードの兄弟がいないので、自身の複製を兄弟として追加しています。


・build_tree

build_layerメソッドを、layerの長さが1になるまで繰り返すことでtreeを完成させます。その後、最上層のノードのハッシュ値をマークルルートとして格納します。


・search

任意のdataを持つノードをleavesから探します。


・get_pass

まず、任意のデータを持つノードをtargetとして保存します。targetの親を辿っていくことで、マークルパスを作成します。具体的には、親ノードの兄弟のhashとpositionが、マークルパスとなります。


もう一度図を見てみましょう。

Content image

hash3とhash2があれば親(hash23)のハッシュは計算できるので、親はマークルパスになりません。一方で、親の兄弟(hash01)は算出できないので、マークルパスに追加します。また、足し算の順番によってハッシュ値が変わるので、positionもマークルパスに必要となります。


Content image


●caluculator関数

マークルパスからマークルルートを算出する関数です。先頭の値は足し算の必要がないので、そのままvalueに代入しています。その後は、マークルパスに則って足し算した値のハッシュ値を、valueに上書きしていきます。全行程を終えた時のvalueが、算出されたマークルルートとなります。


Content image


●使ってみる

ブロックチェーンとウォレットを再現するのは難しいので、ここでは単純なデータ群を使って動作を確認してみます。マークルパスを使うことで、データ群の全てを知らずとも、改ざんの有無を検証できることを見てみましょう。


まず、データを入れたリストからマークルツリーを作成し、そのマークルルートを表示させています。ブロックチェーンで言えば、各文字列がトランザクション、リストがブロック、そしてマークルルートがウォレットに格納されるデータです。

Content image


次に、ウィスキーから伸びるマークルパスを見てみましょう。0番目がウィスキーのハッシュ値で、その後はハッシュ値とpositionの組になってるのが分かります。

Content image


このマークルパスからマークルルートを算出し、先程取得したmerkle_rootと一致することを確認しましょう。

Content image


今度は、元データのノンアルをテキーラに改ざんしてみましょう。そこから先程と同様にして、マークルツリーからマークルパスを取得し、マークルルートを算出してみましょう。改ざん前のツリーのマークルルートと異なる事が確認できます。

Content image


Content image


●最後に

ちょいと難しい内容だっただけに、この記事だけで理解できないかもしれませんし、もしかしたら私の理解も何か間違ってるかもしれません。幸い、もずく先生も図解でマークルツリーを解説しようと試みているようなので、そちらと合わせて理解を深めていただければと思います。


読者の前提知識を一切考えず書いた俺得記事になってしまいましたが、いつか誰かの役に立てることを祈っています。


かしこ。



公開日:2018/11/01
獲得ALIS:37.33
がくし's icon'
  • がくし
  • @gaxiiiiiiiiiiii
養蜂家。暇な時にプログラミングをして遊んでる。

投稿者の人気記事
コメントする
コメントする
こちらもおすすめ!
Eye catch
クリプト

NFT解体新書・デジタルデータをNFTで販売するときのすべて【実証実験・共有レポート】

Like token Tip token
120.79 ALIS
Eye catch
クリプト

クリプトスペルズで入手したMCHCを引き出す方法

Like token Tip token
186.20 ALIS
Eye catch
クリプト

CoinList(コインリスト)の登録方法

Like token Tip token
15.55 ALIS
Eye catch
クリプト

コインチェックに上場が決まったEnjin Coin(エンジンコイン)コインを解説

Like token Tip token
21.49 ALIS
Eye catch
クリプト

【第8回】あの仮想通貨はいま「テレグラム-TON/Gram」

Like token Tip token
69.90 ALIS
Eye catch
クリプト

【初心者向け】$MCHCの基本情報と獲得方法

Like token Tip token
16.32 ALIS
Eye catch
クリプト

ブロックチェーンの51%攻撃ってなに

Like token Tip token
0.00 ALIS
Eye catch
クリプト

【DeFi】複利でトークンを運用してくれるサイト

Like token Tip token
41.81 ALIS
Eye catch
クリプト

バイナンスの信用取引(マージン取引)を徹底解説~アカウントの開設方法から証拠金計算例まで~

Like token Tip token
3.50 ALIS
Eye catch
クリプト

UNISWAPでALISをETHに交換してみた

Like token Tip token
19.40 ALIS
Eye catch
クリプト

Bitcoin史 〜0.00076ドルから6万ドルへの歩み〜

Like token Tip token
947.13 ALIS
Eye catch
クリプト

Polygon(Matic)で、よく使うサイト(DeFi,Dapps)をまとめてみた

Like token Tip token
235.30 ALIS