メルケルツリーの紹介: それは何ですか?そしてどのように機能しますか?

マークル ツリーはハッシュ値のバイナリ ツリーであり、各リーフ ノードは単一のデータまたはデータのハッシュを表します。大量のデータの整合性を効率的に検証するために使用されます。 1979 年にラルフ マークルによって発明され、ビットコインやイーサリアムなどの暗号通貨で広く使用されています。

ハッシュ関数は指紋認証機のようなものです。ファイル、テキスト、数値などの入力を受け取り、入力よりもはるかに短いハッシュと呼ばれる固有の出力を生成します。ハッシュは入力の指紋のようなものです。同じハッシュを持つ 2 つの異なる入力を見つけるのは困難です。そして、ハッシュから元の入力を取得することは不可能です。

たとえば、サイズが 1 MB の「 kishan.jpg 」というファイルがある場合、ハッシュ関数を使用すると、 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F 84FAD1BB4FD9B47568DA1F570C067D9A4867F など、わずか64文字の長さのハッシュを取得できます。

ファイル内の 1 ピクセルでも変更すると、ハッシュはC69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AFのようにまったく異なります。

したがって、ハッシュを使用して、ファイルが以前と同じであることを確認できます。

しかし、ファイルがたくさんある場合はどうなるでしょうか?各ファイルのハッシュを個別に計算して保存するのは面倒です。そこでマークル ツリーが役に立ちます。

マークル ツリーはハッシュの家系図のようなものです。ツリーの葉として各ファイルのハッシュから開始します。次に、ハッシュをペアにして結合して、新しいハッシュを取得します。ツリーの最上部に到達すると、ハッシュが 1 つだけ残るまで、このプロセスを繰り返します。このハッシュはマークル ルートと呼ばれます。

マークル ルートは、ツリー内のすべてのファイルの指紋のようなものです。ファイルが変更されると、そのハッシュも変更され、マークル ルートが変更されるまでその上のすべてのハッシュも変更されます。したがって、マークル ルートを使用して、すべてのファイルが以前と同じであることを確認できます。

しかし、特定のファイルをどうやって検証するのでしょうか?ツリー内のすべてのファイルをダウンロードして確認する必要はありません。ファイルから Merkle ルートまでのパスに沿っていくつかのハッシュをダウンロードして確認するだけです。このパスはマークル証明と呼ばれます。

たとえば、ファイル「cat.jpg」が正しいかどうかを確認したいとします。ダウンロードする必要があるのは、そのハッシュHA ( 0a6df4 )、その兄弟のハッシュHB (ea12e7) 、その親の兄弟のハッシュH CD (b582ae) 、およびマークル ルートH ABCD (7bd24f)だけです。

次に、 HAとHB組み合わせてH ABを計算し、 H AB と H CD を組み合わせてH ABCDを計算できます。 H ABCD がマークル ルートと一致する場合、." cat.jpg " が正しいと確信できます。

同じ例えを使用して、cat.jpg や Dog.txt の代わりにマークル ルートを検証することで、ブロック内に存在するトランザクションが緩和されているかどうかを検証できます。リーフノードでは大量のトランザクションが発生します。

注: 図をきれいに見せるために、上の例ではハッシュ値を 6 文字に切り詰めています。

リーフ ノードが 3 つしかない場合はどうなりますか?マークル ツリーを作成するにはどうすればよいですか?

このシナリオは、1 つのノードを複製してノードの合計数を 4 にすることですぐに対処できます。

たとえば、トランザクションがあるとします。 TA 、 TB 、およびTC 。ハッシュを計算できます。 HA 、 HB 、およびHC 。次に、 HC を複製して HC' を取得できます。その後;ハッシュをペアにして結合して、 H AB 、 H CC' 、およびH ABCC'を取得できます。マークルルートはH ABCC'です。

要約すると、マークル ツリーは、多くのコンピューターが大量のデータを共有して検証する必要があるブロックチェーンやその他の分散システムに利益をもたらします。マークル ツリーを使用すると、帯域幅、ストレージ、計算時間を節約できます。

以下は、独自のマークル ツリーを作成する方法を示す簡単な Java の例です。

 import java.nio.charset.StandardCharsets; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; class MerkleTree{ static class Node { String content; public Node(String content) { this.content = content; } public String getHash() throws NoSuchAlgorithmException { MessageDigest md = MessageDigest.getInstance("SHA-256"); byte[] hash = md.digest(content.getBytes(StandardCharsets.UTF_8)); StringBuilder buffer = new StringBuilder(); for (byte b : hash) { buffer.append(String.format("%02x", b)); } return buffer.toString(); } } public static void main(String[] args) throws NoSuchAlgorithmException{ Node cat = new Node("I am a cat, this is a cat file called cat.jpg"); Node dog = new Node("I am a dog, this is a dog file called dog.txt"); // we have two leaf nodes, in order to create a merkle root, // we simple need to get their individual hashes // and then combine those hashes and hash them again String HA = cat.getHash(); String HB = dog.getHash(); Node merkleRoot = new Node(HA + HB); String HAB = merkleRoot.getHash(); System.out.println("Merkle Root: " + merkleRoot.getHash()); // let's say we altered the cat file cat = new Node("I am a cat, this is a cat file called dog.jpg"); // notice we have changed the cat.jpg to dog.jpg String HA_MODIFIED = cat.getHash(); Node modifiedMerkleRoot = new Node(HA_MODIFIED + HB); String HAB_MODIFIED = modifiedMerkleRoot.getHash(); System.out.println("Merkle Root: " + HAB_MODIFIED); } }

出力：

 Merkle Root: d1da3503d679f032134b4330768d31e67813fcfe2824fceed93f8185a405bdf9 Merkle Root: 1a898c7fee0e46647e55d5f9874f090e5ed76726acf39308527a0bba22a34b3e

私の記事を読んでいただきありがとうございます。私が記事を公開するたびに通知が届くように、 Hackernoonで私をフォローして私をサポートしてください。

どうもありがとう。

分散システム、テクノロジー、AI のトレンドに関する洞察力に富んだ記事をご覧ください。 https://www.0xkishan.com 。ぜひ訪問してサポートを示してください。

こちらでも公開しております。