ハッシュ木(マークル木)って何なんだぜ(^~^)!?

はっぴょー(^~^) おぴょー(^◇^) ぶっぴょーん(^q^) 公開下書き

ハッシュ木(マークル木)って何なんだぜ(^~^)!?

20210124shogi2a2b1.png
「 マークル木 とか言われても 分からんよな。
時給の高い求人、技術ドキュメントを自分で読んで解決できる人募集、とかだし……」

kifuwarabe-futsu.png
「 情報科学、情報処理の畑にいるやつの マークル木分からん発言 わらう」

ohkina-hiyoko-futsu.png
「 もう学校にいるわけでもない大人は 自分で調べるのよ」

順を追って説明

20210623blog34a2.png

ramen-tabero-futsu2.png
「 👆 ファイル4つで1セットのものを 配りたいやつがいるんだぜ。
1つが欠けてるとか、全部 改ざん されてるとかあったら 受け取る人に ちゃんと行き渡らないだろ」

20210623blog34a3.png

ramen-tabero-futsu2.png
「 👆 そこで、ファイル1つ1つから、なんらかの計算をして ハッシュ という数 を出しておくんだぜ。
この計算は 誰がやっても 同じ ハッシュ が出てくるものとするぜ。
ハッシュは 別のファイルと被る(衝突する)こともあるが、 宝くじに当たるような感じで 確率的に ほぼ起こらないものとしようぜ」

kifuwarabe-futsu.png
「 ハッシュを 教えてもらえば、ファイルが 改ざん されているかどうか 確認できるな」

20210623blog34a4.png

ramen-tabero-futsu2.png
「 👆 そのハッシュをいくつかまとめて、またハッシュを作るんだぜ」

ohkina-hiyoko-futsu.png
「 ディレクトリごとに まとめるとかした方が よくない?」

20210623blog34a5.png

ramen-tabero-futsu2.png
「 👆 そのハッシュをいくつかまとめて、最終的には 1つの ハッシュ を作るんだぜ。
これを トップハッシュ とか、 マスターハッシュ とか、 ルートハッシュ と呼ぶそうだぜ」

kifuwarabe-futsu.png
「 ハッシュって、カレーと関係あるのかだぜ?」

ramen-tabero-futsu2.png
「 バラバラに切り刻む、という意味では同じだぜ」

ramen-tabero-futsu2.png
「 で、 この トップハッシュ 1つを、 受け取る人に教えておけばいいわけだぜ。
全部のファイルのハッシュを教えなくていい」

ohkina-hiyoko-futsu.png
「 いいのかなあ」

20210623blog34a6.png

ramen-tabero-futsu2.png
「 👆 そして今 受け取った人のパソコンには ファイル2 と、 教えられたトップハッシュ の2つがあるとしよう。
この ファイル2 が本当に 改ざん されていないかは どうやって 確認するんだぜ?」

kifuwarabe-futsu.png
「 ファイル2 のことは忘れて寝て、明日起きたら 昨日のことは思い出さずに 新しい人生を生きていこうぜ」

20210623blog34a7.png

ohkina-hiyoko-futsu.png
「 👆 ハッシュB は 誰でも 計算で出せるんでしょ。
ファイルを配ったやつが寝ていたら 電話で起こして ファイル2 のハッシュを聞き出すことかしらねぇ?」

ramen-tabero-futsu2.png
「 まあ そうだな」

20210623blog34a8.png

ramen-tabero-futsu2.png
「 👆 ファイル3、4 だけを拾ったやつは、
ファイル1個1個のハッシュを聞かなくても ハッシュCD を聞けば 改ざん されてないことが分かるので
便利だな」

20210623blog34a8.png

ramen-tabero-futsu2.png
「 👆 じゃあ今、 ハッシュB と ハッシュCD は 知っているわけだぜ」

ramen-tabero-futsu2.png
「 でも ハッシュB と ハッシュCD から ハッシュBCD を作っても、
ファイルを配ったやつから 教えてもらった トップハッシュ と同じにならないぜ。
何か ファイルが欠けてんのかだぜ?」

ohkina-hiyoko-futsu.png
「 要らんファイル 混ざってるかも知れないわね」

kifuwarabe-futsu.png
「 ファイルが欠けてるとか、要らないファイルが混ざってるとか、
このツリー構造を知らない わたしたち には 知る由もないのでは?」

ramen-tabero-futsu2.png
「 どこかに インデックス的な、 ツリーの形を教えてくれる情報がないと そもそも マークル木 できないよな。
Wikipedia 舐めてんのかな?」

ohkina-hiyoko-futsu.png
「 ツリーの形は 情報として与えられているとしましょう」

20210623blog34a9.png

ramen-tabero-futsu2.png
「 👆 ファイルを丸ごと一式受け取った方は、あとは ファイル1のハッシュ を計算で求めておけば、
トップハッシュ と比較するために必要なものは 揃うわけだぜ」

20210623blog34a10.png

ramen-tabero-futsu2.png
「 👆 だから 要点としては
ある程度の かたまり のハッシュを持っておくというのが アイデア で、
ファイル1個1個のハッシュを見直す必要がなくて 計算量が減っるということを 理由に、
改ざん があるかどうかのチェックが高速になる というメリットがある、
ということかだぜ?」

ohkina-hiyoko-futsu.png
「 そうなのかなあ?」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事