［入門篇］マークルツリーとは

もずく
2018/12/18 13:35

もずく・Ð・図解屋です。

魔法使いオズモンのシリーズ第4回は「マークルツリー」についてです。

は？マークルツリー？という人も多いかもしれません（入門篇ですし）。

Bitcoinはブロックチェーンと呼ばれるブロックの連鎖でできていて、各ブロックの中にはトランザクション（BTCを誰から誰に送ったという取引データ）がたくさん詰め込まれています。

マークルツリー（Merkle tree）というのは、そのトランザクション（のハッシュ値）が記録されているデータ形式のことです。

Bitcoinのブロックでは、重要なデータはブロックヘッダーという部分に記録されるのですが、いくらトランザクションが重要だとはいえ、すべてのトランザクション（のハッシュ値）を小さなヘッダー領域に入れるわけにはいきません。

マークルツリーというデータ形式では、たった一つの小さな情報（ハッシュ値）でデータ全体を要約することができます。

なので、トランザクション全体をブロックヘッダーに記録する代わりに、その要約情報だけをブロックヘッダーに入れておけば済みます。

ブロックヘッダーにトランザクションの要約情報を記録する理由は、ブロックに含まれているトランザクションが改ざんされていないか確認するためです。

マークルツリーも、ここまでのオズモンシリーズと同様、インターネット上での改ざんに対する対策なのです。

…という前知識をなんとなく頭に入れていただいた上で、魔法使いオズモンにバトンを譲りましょう～

マークルツリーではハッシュ関数が登場するので、第1回のオズモンシリーズをまだ読んでいない人や忘れてしまった人はお先にどうぞ。

やあ、魔法使いのオズモンだよ💫

前回と前々回は、魔法のカギを使って相手に荷物をちゃんと届けたり、それがボクの送った荷物であることを証明する魔法を紹介したね。

今回は初回のハッシュカメラの話にちょっと戻って、魔法の世界での荷物の検品の話をしたいと思う。

ハッシュカメラを使えばどんなモノでも固有の文字列プレートに変えてしまえるから、配送中に荷物が交換されても受取人のところで検品すればバレる。

ところが、実はこの方法、送る荷物が少ないときはいいんだけど、多くなってくると大変になるんだ。

確かにハッシュカメラは荷物がどれだけ多くても1枚の文字列プレートにできるんだけど、荷物が多すぎると文字列プレートの生成に時間がかかる。

それに検品のたびに全部元通りに並べ直すのは大変だよね…
並べ方がちょっとでも違うと別の文字列になってしまうし、実はすごくシビアな作業なんだ。

そこで、たくさんの荷物をまとめて一つの文字列プレートにするんじゃなくて、荷物を一つずつハッシュカメラで撮影してプレートを作ることを考えよう。

送る側は、箱に荷物を入れるときに撮影していけばいいから楽だよね。途中で荷物を変更したり、送るのをやめたりするときにも手間が少ない。

受け取る側も、荷物を取り出した順に撮影して、対応する文字列プレートと照合していけばいい。この作業は一見大変そうだけど、魔法で簡単に自動化できる。

でも、実はこの方法は配達人を困らせてしまう。

文字列プレートを生成したり照合したりすることは、多少荷物が増えても魔法で自動化できるから問題にはならない。

魔法の世界で一番難しいのは、アクマくんからイタズラされないように配送物を守ることなんだ。文字列プレートは検品するための保証となるものだから、とても大切に運ばないといけない。

そのプレートが荷物の数だけある…って、それはちょっと可哀想。荷物が一万個あったらプレートが一万枚になってしまう。

そこでボクが考えたのが、たくさんの文字列プレートを1枚にまとめる魔法。

まず、プレートを2枚ずつペアにして、それをハッシュカメラで撮影して1枚のプレートを作る。そうしてできたプレートをまた2枚ずつペアにしてハッシュカメラで撮影して1枚のプレートを作る。

こんな感じで、2枚をどんどん1枚にしていったら、最後には1枚の文字列プレートになるってわけ。（もちろん魔法で自動的に作るよ！）

こうすると、配達人が大事に守らないといけないのはこの最後の1枚のプレートだけで済むんだ。

絵にすると、なんだか木を逆さにしたみたいに見えない？

だから、この魔法の名前は「オズモン木」っていうことにした。ボクが最初に考えたからね。

逆さになったオズモン木の一番下、“葉っぱ”に当たるところが一つひとつの荷物の文字列プレートだよ。

そして、オズモン木の一番上、（ややこしいけど）“根っこ”に当たるところが一番大切なプレート。これを「根っこプレート」って呼ぶことにしよう。

さて、この根っこプレート1枚だけでなぜ荷物が検品できるのかみてみよう。

検品するときには三つのものが必要になる。

A. 根っこプレート
B. 検品したい荷物
C. オズモン木（根っこプレート以外のところ）

このうち、アクマくんが手を出せないのは根っこプレートだけで、荷物とオズモン木はアクマくんがイタズラしているかもしれない。

検品の手順は次のとおり。

1. 検品したい荷物1つをハッシュカメラで撮影して文字列プレートを作る

2. その文字列プレートとオズモン木を使って「根っこプレートB」を作る

3. 配達人が大切に運んだ「根っこプレートA」と検品で作り直した「根っこプレートB」を重ね合わせて一致したら検品完了

ん？

オズモン木の葉っぱとして「検品したいモノの文字列プレート」そのものが含まれているんだから、わざわざ根っこプレートBを作る必要なくない？…と思ったあなた。

君のような勘のいいガキは嫌いだよ。

思い出してみよう、オズモン木もアクマくんにイタズラされている可能性があるんだ。

イタズラされていないと保証できるのは根っこプレートだけなので、一番最初の葉っぱのプレートと荷物のプレートが一致しても、荷物が本当にイタズラされていないかわからないんだ。

オズモン木もイタズラ可能なんだから、アクマくんだって荷物にイタズラするときにはついでにその文字列プレートを交換するでしょう？

さて、文字列プレートをこのオズモン木の形にしておくと、他にも良いことがあるんだ。というか、この“良いこと”のためにわざわざオズモン木の形にするっていうのが本当のところ。

オズモン木が真価を発揮するのは、たくさん送る荷物が全部ちゃんと揃っていてはじめて意味のあるような場合。

例えば、ボクからマギカちゃんに「等身大✕3倍オズモン人形」をプレゼントするとしよう。時々贈りたくなるよね、こういうの。

完成体で配送するにはちょっと大きいので、細かくパーツに分けることになる。

これは全部がちゃんと揃っていないと意味がないから、あるパーツを検品するときに「そのパーツがオズモン人形セットの一部である」ことも同時に確認したいわけ。

オズモン木で検品するときには、毎回、検品したいパーツとオズモン木を使って根っこプレートBを生成する。

根っこプレートは「オズモン人形セット」全体を1枚のプレートで要約したものだから、その根っこプレートBがオリジナル（根っこプレートA）と一致したということは、そのパーツがオズモン人形セットの一部であることも同時に保証されるんだ。

しかも、一つのパーツを検品するためにオズモン木の全体は必要とされない…というのもポイント！

これは絵を見てもらうのが早いんだけど、ある一つのパーツを検品する際、オズモン木から根っこプレートを作り出すのに必要なプレートは一部でいいんだよ。

その一部のプレートだけ抜き出したものを「オズモン枝」と呼ぼう。

もしパーツが32個あったら、オズモン木に含まれる文字列プレートの数は32+16+8+4+2+1=63枚（検品するパーツのプレートと根っこプレートを除いても61枚）になる。それに対して、オズモン枝に含まれるプレートの数は6枚だけ。

オズモン枝の6枚というのは、全パーツの文字列プレートを個別に用意しておく（32枚）よりも少ない。

あるパーツが「オズモン人形セット」の一部であることを確認するのに、そのセットのパーツ数よりも少ない文字列プレートでOKってすごいよね！

ちなみに、パーツ数が1024個あっても、オズモン枝に含まれるプレート数はたったの10枚。

2048個で11枚、4096個で12枚…

というふうに、セットにして送るモノの数が増えるほど、すべてのモノの文字列プレートを用意するよりも、オズモン木を使ったほうが文字列プレートがぐっと少なくて済むようになる。

☕ もちろん、セットに含まれる全てのモノを検品したいなら、オズモン木は全部必要になる。ここで言いたいのは、セットの中の一つを検品するときに必要になる文字列プレートの数。あとで説明するように、実際には全てのモノを一気に検品することはなく、順番に（または手分けして）検品することになるので、個々の検品に必要な文字列プレート数が少なくなるのは嬉しいんだ。

オズモン木のこの特徴は、とても大きな配送物のセットをバラバラにして送るときにすごく役立つんだ。

個々の配送単位には、

・バラバラにしたセットの一部
・その一部に対応したオズモン枝
・セットの根っこプレート（←これだけイタズラから死守！）

だけを含んでおけばいい。

死守しないといけないのは根っこプレート1枚だし、オズモン枝はセットすべての文字列プレートを運ぶよりもずっと少ない枚数で済むし、みんなハッピー。