マークル ツリーはハッシュ値のバイナリ ツリーであり、各リーフ ノードは単一のデータまたはデータのハッシュを表します。大量のデータの整合性を効率的に検証するために使用されます。 1979 年にラルフ マークルによって発明され、ビットコインやイーサリアムなどの暗号通貨で広く使用されています。 ハッシュ関数は指紋認証機のようなものです。ファイル、テキスト、数値などの入力を受け取り、入力よりもはるかに短いハッシュと呼ばれる固有の出力を生成します。ハッシュは入力の指紋のようなものです。同じハッシュを持つ 2 つの異なる入力を見つけるのは困難です。そして、ハッシュから元の入力を取得することは不可能です。 たとえば、サイズが 1 MB の「 」というファイルがある場合、ハッシュ関数を使用すると、 84FAD1BB4FD9B47568DA1F570C067D9A4867F など、わずか 文字の長さのハッシュを取得できます。 kishan.jpg 0A6DF48A27EF7DB48B213DF3DBA84FAD1BB4FD9B47568DA1F570C067D9A4867F 64 ファイル内の 1 ピクセルでも変更すると、ハッシュは のようにまったく異なります。 C69E60E932F3D0C6C2363B68301E202551C09123A71F639E6AB3BC8F847BE4AF したがって、ハッシュを使用して、ファイルが以前と同じであることを確認できます。 各ファイルのハッシュを個別に計算して保存するのは面倒です。そこでマークル ツリーが役に立ちます。 しかし、ファイルがたくさんある場合はどうなるでしょうか? マークル ツリーはハッシュの家系図のようなものです。 。次に、ハッシュをペアにして結合して、新しいハッシュを取得します。ツリーの最上部に到達すると、ハッシュが 1 つだけ残るまで、このプロセスを繰り返します。このハッシュは と呼ばれます。 ツリーの葉として各ファイルのハッシュから開始します マークル ルート マークル ルートは、ツリー内のすべてのファイルの指紋のようなものです。 。したがって、マークル ルートを使用して、すべてのファイルが以前と同じであることを確認できます。 ファイルが変更されると、そのハッシュも変更され、マークル ルートが変更されるまでその上のすべてのハッシュも変更されます しかし、特定のファイルをどうやって検証するのでしょうか?ツリー内のすべてのファイルをダウンロードして確認する必要はありません。ファイルから Merkle ルートまでのパスに沿っていくつかのハッシュをダウンロードして確認するだけです。このパスは と呼ばれます。 マークル証明 たとえば、ファイル「cat.jpg」が正しいかどうかを確認したいとします。ダウンロードする必要があるのは、そのハッシュ ( )、その兄弟のハッシュ 、その親の兄弟のハッシュ 、およびマークル ルート だけです。 HA 0a6df4 HB (ea12e7) H CD (b582ae) H ABCD (7bd24f) 次に、 と 組み合わせて を計算し、 H AB と H CD を組み合わせて を計算できます。 H ABCD がマークル ルートと一致する場合、." " が正しいと確信できます。 HA HB H AB 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 。ぜひ訪問してサポートを示してください。 こちらでも公開しております。
