マークルツリーは、大量の情報の正確性を非常に迅速かつ効率的に検証できるデータを構造化する方法です。 すべてのマークルツリーは、マークルルートと呼ばれる単一のデータ文字列になります。 マークルルートと他のいくつかのデータがあれば、どのコンピュータでもマークルツリーの他のすべてのエントリを効率的に検証できます。 ブロックチェーン技術では、これらのエントリはトランザクション識別番号です。
ブロックチェーンの世界に関わっている人なら、「マークルツリー」という言葉を目にしたことがあるかもしれません。 マークルツリーは広く理解されている概念ではありませんが、それほど複雑でもありません。 この記事では、マークルツリーを平易な英語で説明し、それらがどのようにブロックチェーン技術を可能にするかを理解するのに役立ちます。
マークルツリーズの物語は、1979年にラルフ・マークルという男から始まりました。 スタンフォード大学の大学院在学中に、マークルは「A Certified Digital Signature」という学術論文を書きました。 このエッセイで、マークルは デジタル署名 を作成する方法を説明し、暗号証明を作成するための新しい非常に効率的な方法を確立しました。 言い換えれば、彼は、コンピューターがかつてないほど高速に作業を行えるように、データを検証するプロセスを設計したのです。
マークルは、このアイデアを「ツリー署名」または「ツリー認証」と呼んだ。 今日では、このアイデアは発明者にちなんで名付けられたマークルツリーとしてよく知られています。
マークルツリーは、暗号の世界に革命をもたらし、ひいては暗号化されたコンピュータプロトコルの機能に革命をもたらしたと言っても過言ではありません。 実際、マークルツリーは、ビットコインを世界に紹介した サトシナカモトの2008年のエッセイ で繰り返し言及されています。 これらはビットコインプロトコルで広く使用されています。
では、マークルツリーとはいったい何なのでしょうか? 確認してみましょう。
まず、暗号化ハッシュ関数の概念を理解することが重要です。 簡単に言うと、ハッシュ関数は、1 文字から百科事典のセット全体のテキストまで、任意の長さの入力を受け取り、固定長のランダムな出力を生成する不可逆的な数学関数です。 出力はランダムに見え、固定長であるため、攻撃者はどの入力が特定の出力を生成したかについての手がかりがありません。 ハッシュ関数も決定論的であるため、同じ入力は常に同じ出力を生成します。 最後に、ハッシュ関数は不可逆的であるため、出力の知識だけでは入力を確認する方法はまったくありません。
これらのプロパティはすべて、ハッシュ関数が特定の入力の電子フィンガープリントを作成できるようにします。 ブロックチェーンネットワークは、ハッシュ関数を使用して、各トランザクションの暗号化ハッシュ(電子指紋)を作成します。 トランザクションの暗号化ハッシュは、単にトランザクションIDと呼ばれます。 ほぼすべてのブロックチェーンプロトコルでは、各トランザクションIDは64文字(256ビット)の英数字のデータ文字列です。
ブロックチェーンは通常、数十万のブロックで構成されており、各ブロックには数千ものトランザクションが含まれていることを考えると、トランザクションの検証が計算上どれほど速く困難になるかは想像に難くありません。 そのため、トランザクションの処理と検証を行う際に使用するデータはできるだけ少なくするのが最適です。 これにより、CPUの処理時間が最小限に抑えられると同時に、最高レベルのセキュリティが確保されます。
まあ、それはまさにマークルツリーが行うことです。 非常に簡単に言うと、マークルツリーは膨大な数のトランザクションIDを取得し、それらを特定の方法で構造化し、暗号化ハッシュ関数を使用して、データ本文全体の電子指紋として機能する単一の64文字の英数字文字列を導き出します。
マークルルートと呼ばれるこのデータ文字列は、特定のトランザクションが特定のブロックで行われたことを可能な限り効率的にコンピューターがすばやく確認できるようにするため、非常に重要です。
マークルツリーが生成する単一の256ビット文字列は、マークルルートと呼ばれます。 ブロックチェーンの各ブロックには、1つだけあります。 そして、先ほど述べたように、マークルルートは、コンピューターが信じられないほどの速度と効率で情報を検証できるようにするため、重要なデータです。
もう少し深く掘り下げてみましょう。 マークルルートはどのように生成されますか? 最初のステップは、すべてのデータ入力 (この場合はトランザクション ID) を整理することです。 マークルツリーは、設計上、常にすべての入力をペアにグループ化します。 入力の数が奇数の場合、最後の入力がコピーされ、それ自体とペアになります。 これは、ブロックチェーンのブロックに書き込まれたすべてのトランザクションIDに当てはまります。
たとえば、1 つのブロックに合計 512 個のトランザクションが含まれているとします。 マークルツリーは、これらの512のトランザクションIDを256のペアにグループ化することから始めます。 次に、これらの 256 組のトランザクション ID が数学的プロセス (ハッシュ関数またはハッシュ アルゴリズムと呼ばれることもあります) を通過し、256 個の新しい 64 文字の暗号化ハッシュが作成されます。
まったく同じプロセスが再び発生します。 これらの 256 個の新しいハッシュはペアになり、128 個のハッシュに変換されます。 このプロセスが繰り返され、ハッシュが 1 つだけになるまで、毎回ハッシュの数を半分に減らします。 その1つのハッシュがマークルルートです。
この概念を明確にするために、マークルツリーの非常に簡単な例を見てみましょう。 1つの特定のブロックで8つのトランザクションが実行されたと想像してください。 実際には、トランザクション ID の長さは 64 文字ですが、わかりやすくするために、8 文字しかないと仮定しましょう。 さらに簡単にするために、数字のみを使用しましょう(文字は完全に無視します)。
したがって、この例では、8つのトランザクションIDは次のようになります。
ここで、トランザクション ID をハッシュする方法が、結合される 2 つの ID のそれぞれから 1 桁目、3 桁目、5 桁目、7 桁目を取得し、それらの数字を単純にプッシュして新しい 8 桁のコードを形成することであるとします。
もちろん、実際には、ハッシュアルゴリズムの背後にある数学はこれよりもはるかに複雑です。 しかし、この簡単なデモンストレーションでは、この基本システムで十分です。
これは、マークルツリーがどのように見えるかです。
コードの数は、マークルツリーのステップごとに半分に減っていることに注意してください。 8つのトランザクションIDから始めて、わずか3つのステップで、1つのコード(マークルルート)にたどり着きます。 この例では、マークルルートは下部のボックスのコード12345678です。
マークルツリーの主な利点は、データを非常に迅速に検証できることです。 単一のトランザクションIDを検証したい場合、ブロック上のすべてのトランザクションを再確認する必要はありません。 むしろ、マークルツリーの特定の「枝」を確認するだけで済みます。
現在の例でトランザクションIDを検証したいとしましょう。 ボブはアリスに一定のビットコインを支払ったと言い、トランザクションIDは88888888だと教えてくれます。 彼はまた、77777777、55556666、11223344の3つのハッシュも送信します。 ボブのアリスへの支払いを確認するために送受信する必要がある情報はこれだけです。
これら3つのハッシュは、問題のトランザクションIDとこの特定のブロックのマークルルートとともに、ボブのアリスへの支払いを確認するために必要な唯一のデータです。 これは、マークルツリー全体を検証するために必要なデータよりもはるかに少ないデータです。 その結果、検証プロセスは誰にとってもはるかに速く、はるかに効率的になります。
その仕組みはこうです。 ブロックのマークルルートはすでにあるので、ボブはそれを送る必要はありません。 彼は、トランザクションIDと上記の3つの追加ハッシュを送信してくれました。 また、ハッシュを使用する順序と配置に関するわずかな情報も送信します。 あとは、Bob が提供した一連のデータに対してハッシュ アルゴリズムを実行するだけです。
まず、トランザクション ID 88888888で最初のコード77777777をハッシュし、結果77778888を取得します。 ボブはこのコードを送ってくれませんでしたが、私たちはボブと同じハッシュアルゴリズムを使用しているので、送る必要はありませんでした。 したがって、まったく同じ結果が得られます。
次に、Bob から送られてきた 2 番目のコード55556666を取得し、先ほど導出した新しいコード77778888ハッシュ化します。 もちろん、これは数55667788を生成します。
最後に、Bob が11223344 から渡した 3 番目のコードを、受け取った別の新しいコード 55667788 でハッシュすると、正しい Merkle Root である 12345678 になります。
Bob からの 3 つのコードのみが必要であり、Bob のトランザクションが有効であることを確認するためにハッシュ アルゴリズムを 3 回実行するだけでよかったことに注意してください。 つまり、私たちのコンピュータは、マークルツリー全体を検証するために必要な作業の半分以下しか行っていないことになります。 元のマークルツリー図には15個の数字があり、ハッシュアルゴリズムは7回実行する必要があります。 しかし、そのツリーの半分以上は、ボブのトランザクションを検証するために必要ではありません。
この手順は、ボブが送信した他のコードと一緒にハッシュされたときに、この特定のブロックに当てはまることがすでにわかっているのと同じマークルルートを生成したため、ボブが実際にアリスに特定の金額のビットコインを支払ったことを確認するのに十分です。
ボブは、偽のトランザクションIDと、ハッシュ関数を通すと真のマークルルートを生成する偽のコードの追加セットを見つける必要があるため、トランザクションを偽造することはできません。 これが起こる可能性は天文学的に非常に小さいので、私たちは自信を持って不可能だと言うことができます。
この単純な例では、コンピューティング能力の節約はそれほど大きくないように思えるかもしれません。 しかし、ブロックチェーンのブロックに数千のトランザクションが含まれていることを考えると、マークルツリーがいかに効率を劇的に向上させるかは容易に理解できます。
要するに、それがマークルツリーの主な利点です。 これにより、コンピューターは、マークルツリーなしで必要なデータよりもはるかに少ないデータで、非常に効率的に情報を検証できます。
マークルツリーは、ブロックチェーンのスケーラビリティ問題に対するKomodoプラットフォームのソリューションの基本概念でもあります。 Komodoのスケーリングソリューションは、完全なブロックチェーンの相互運用性を可能にし、Komodoが地球上の他のどの決済処理サービスよりも高速にトランザクションを処理できるようにします。 現在、Komodoの新しいスケーリング技術は、テスト環境で毎秒20,000以上のトランザクションを処理しています。
マークルツリーは、大量の情報の正確性を非常に迅速かつ効率的に検証できるデータを構造化する方法です。 すべてのマークルツリーは、マークルルートと呼ばれる単一のデータ文字列になります。 マークルルートと他のいくつかのデータがあれば、どのコンピュータでもマークルツリーの他のすべてのエントリを効率的に検証できます。 ブロックチェーン技術では、これらのエントリはトランザクション識別番号です。
ブロックチェーンの世界に関わっている人なら、「マークルツリー」という言葉を目にしたことがあるかもしれません。 マークルツリーは広く理解されている概念ではありませんが、それほど複雑でもありません。 この記事では、マークルツリーを平易な英語で説明し、それらがどのようにブロックチェーン技術を可能にするかを理解するのに役立ちます。
マークルツリーズの物語は、1979年にラルフ・マークルという男から始まりました。 スタンフォード大学の大学院在学中に、マークルは「A Certified Digital Signature」という学術論文を書きました。 このエッセイで、マークルは デジタル署名 を作成する方法を説明し、暗号証明を作成するための新しい非常に効率的な方法を確立しました。 言い換えれば、彼は、コンピューターがかつてないほど高速に作業を行えるように、データを検証するプロセスを設計したのです。
マークルは、このアイデアを「ツリー署名」または「ツリー認証」と呼んだ。 今日では、このアイデアは発明者にちなんで名付けられたマークルツリーとしてよく知られています。
マークルツリーは、暗号の世界に革命をもたらし、ひいては暗号化されたコンピュータプロトコルの機能に革命をもたらしたと言っても過言ではありません。 実際、マークルツリーは、ビットコインを世界に紹介した サトシナカモトの2008年のエッセイ で繰り返し言及されています。 これらはビットコインプロトコルで広く使用されています。
では、マークルツリーとはいったい何なのでしょうか? 確認してみましょう。
まず、暗号化ハッシュ関数の概念を理解することが重要です。 簡単に言うと、ハッシュ関数は、1 文字から百科事典のセット全体のテキストまで、任意の長さの入力を受け取り、固定長のランダムな出力を生成する不可逆的な数学関数です。 出力はランダムに見え、固定長であるため、攻撃者はどの入力が特定の出力を生成したかについての手がかりがありません。 ハッシュ関数も決定論的であるため、同じ入力は常に同じ出力を生成します。 最後に、ハッシュ関数は不可逆的であるため、出力の知識だけでは入力を確認する方法はまったくありません。
これらのプロパティはすべて、ハッシュ関数が特定の入力の電子フィンガープリントを作成できるようにします。 ブロックチェーンネットワークは、ハッシュ関数を使用して、各トランザクションの暗号化ハッシュ(電子指紋)を作成します。 トランザクションの暗号化ハッシュは、単にトランザクションIDと呼ばれます。 ほぼすべてのブロックチェーンプロトコルでは、各トランザクションIDは64文字(256ビット)の英数字のデータ文字列です。
ブロックチェーンは通常、数十万のブロックで構成されており、各ブロックには数千ものトランザクションが含まれていることを考えると、トランザクションの検証が計算上どれほど速く困難になるかは想像に難くありません。 そのため、トランザクションの処理と検証を行う際に使用するデータはできるだけ少なくするのが最適です。 これにより、CPUの処理時間が最小限に抑えられると同時に、最高レベルのセキュリティが確保されます。
まあ、それはまさにマークルツリーが行うことです。 非常に簡単に言うと、マークルツリーは膨大な数のトランザクションIDを取得し、それらを特定の方法で構造化し、暗号化ハッシュ関数を使用して、データ本文全体の電子指紋として機能する単一の64文字の英数字文字列を導き出します。
マークルルートと呼ばれるこのデータ文字列は、特定のトランザクションが特定のブロックで行われたことを可能な限り効率的にコンピューターがすばやく確認できるようにするため、非常に重要です。
マークルツリーが生成する単一の256ビット文字列は、マークルルートと呼ばれます。 ブロックチェーンの各ブロックには、1つだけあります。 そして、先ほど述べたように、マークルルートは、コンピューターが信じられないほどの速度と効率で情報を検証できるようにするため、重要なデータです。
もう少し深く掘り下げてみましょう。 マークルルートはどのように生成されますか? 最初のステップは、すべてのデータ入力 (この場合はトランザクション ID) を整理することです。 マークルツリーは、設計上、常にすべての入力をペアにグループ化します。 入力の数が奇数の場合、最後の入力がコピーされ、それ自体とペアになります。 これは、ブロックチェーンのブロックに書き込まれたすべてのトランザクションIDに当てはまります。
たとえば、1 つのブロックに合計 512 個のトランザクションが含まれているとします。 マークルツリーは、これらの512のトランザクションIDを256のペアにグループ化することから始めます。 次に、これらの 256 組のトランザクション ID が数学的プロセス (ハッシュ関数またはハッシュ アルゴリズムと呼ばれることもあります) を通過し、256 個の新しい 64 文字の暗号化ハッシュが作成されます。
まったく同じプロセスが再び発生します。 これらの 256 個の新しいハッシュはペアになり、128 個のハッシュに変換されます。 このプロセスが繰り返され、ハッシュが 1 つだけになるまで、毎回ハッシュの数を半分に減らします。 その1つのハッシュがマークルルートです。
この概念を明確にするために、マークルツリーの非常に簡単な例を見てみましょう。 1つの特定のブロックで8つのトランザクションが実行されたと想像してください。 実際には、トランザクション ID の長さは 64 文字ですが、わかりやすくするために、8 文字しかないと仮定しましょう。 さらに簡単にするために、数字のみを使用しましょう(文字は完全に無視します)。
したがって、この例では、8つのトランザクションIDは次のようになります。
ここで、トランザクション ID をハッシュする方法が、結合される 2 つの ID のそれぞれから 1 桁目、3 桁目、5 桁目、7 桁目を取得し、それらの数字を単純にプッシュして新しい 8 桁のコードを形成することであるとします。
もちろん、実際には、ハッシュアルゴリズムの背後にある数学はこれよりもはるかに複雑です。 しかし、この簡単なデモンストレーションでは、この基本システムで十分です。
これは、マークルツリーがどのように見えるかです。
コードの数は、マークルツリーのステップごとに半分に減っていることに注意してください。 8つのトランザクションIDから始めて、わずか3つのステップで、1つのコード(マークルルート)にたどり着きます。 この例では、マークルルートは下部のボックスのコード12345678です。
マークルツリーの主な利点は、データを非常に迅速に検証できることです。 単一のトランザクションIDを検証したい場合、ブロック上のすべてのトランザクションを再確認する必要はありません。 むしろ、マークルツリーの特定の「枝」を確認するだけで済みます。
現在の例でトランザクションIDを検証したいとしましょう。 ボブはアリスに一定のビットコインを支払ったと言い、トランザクションIDは88888888だと教えてくれます。 彼はまた、77777777、55556666、11223344の3つのハッシュも送信します。 ボブのアリスへの支払いを確認するために送受信する必要がある情報はこれだけです。
これら3つのハッシュは、問題のトランザクションIDとこの特定のブロックのマークルルートとともに、ボブのアリスへの支払いを確認するために必要な唯一のデータです。 これは、マークルツリー全体を検証するために必要なデータよりもはるかに少ないデータです。 その結果、検証プロセスは誰にとってもはるかに速く、はるかに効率的になります。
その仕組みはこうです。 ブロックのマークルルートはすでにあるので、ボブはそれを送る必要はありません。 彼は、トランザクションIDと上記の3つの追加ハッシュを送信してくれました。 また、ハッシュを使用する順序と配置に関するわずかな情報も送信します。 あとは、Bob が提供した一連のデータに対してハッシュ アルゴリズムを実行するだけです。
まず、トランザクション ID 88888888で最初のコード77777777をハッシュし、結果77778888を取得します。 ボブはこのコードを送ってくれませんでしたが、私たちはボブと同じハッシュアルゴリズムを使用しているので、送る必要はありませんでした。 したがって、まったく同じ結果が得られます。
次に、Bob から送られてきた 2 番目のコード55556666を取得し、先ほど導出した新しいコード77778888ハッシュ化します。 もちろん、これは数55667788を生成します。
最後に、Bob が11223344 から渡した 3 番目のコードを、受け取った別の新しいコード 55667788 でハッシュすると、正しい Merkle Root である 12345678 になります。
Bob からの 3 つのコードのみが必要であり、Bob のトランザクションが有効であることを確認するためにハッシュ アルゴリズムを 3 回実行するだけでよかったことに注意してください。 つまり、私たちのコンピュータは、マークルツリー全体を検証するために必要な作業の半分以下しか行っていないことになります。 元のマークルツリー図には15個の数字があり、ハッシュアルゴリズムは7回実行する必要があります。 しかし、そのツリーの半分以上は、ボブのトランザクションを検証するために必要ではありません。
この手順は、ボブが送信した他のコードと一緒にハッシュされたときに、この特定のブロックに当てはまることがすでにわかっているのと同じマークルルートを生成したため、ボブが実際にアリスに特定の金額のビットコインを支払ったことを確認するのに十分です。
ボブは、偽のトランザクションIDと、ハッシュ関数を通すと真のマークルルートを生成する偽のコードの追加セットを見つける必要があるため、トランザクションを偽造することはできません。 これが起こる可能性は天文学的に非常に小さいので、私たちは自信を持って不可能だと言うことができます。
この単純な例では、コンピューティング能力の節約はそれほど大きくないように思えるかもしれません。 しかし、ブロックチェーンのブロックに数千のトランザクションが含まれていることを考えると、マークルツリーがいかに効率を劇的に向上させるかは容易に理解できます。
要するに、それがマークルツリーの主な利点です。 これにより、コンピューターは、マークルツリーなしで必要なデータよりもはるかに少ないデータで、非常に効率的に情報を検証できます。
マークルツリーは、ブロックチェーンのスケーラビリティ問題に対するKomodoプラットフォームのソリューションの基本概念でもあります。 Komodoのスケーリングソリューションは、完全なブロックチェーンの相互運用性を可能にし、Komodoが地球上の他のどの決済処理サービスよりも高速にトランザクションを処理できるようにします。 現在、Komodoの新しいスケーリング技術は、テスト環境で毎秒20,000以上のトランザクションを処理しています。