暗号技術ツール入門 - ハッシュ関数とマークルツリーを解説
この記事では何を解説しますか？
ブロックチェーンにより、人々は仲介者を必要とせずに合意を形成できます。ブロックチェーンは信頼に頼るのではなく、暗号学的証明を利用します。この証明を提供するために使われるのが暗号プリミティブです。では、暗号プリミティブとは何でしょうか？
この記事では、ブロックチェーン上の暗号学的証明に不可欠な2つの暗号プリミティブ、ハッシュ関数とマークルツリーを取り上げます。ハッシュ関数の中核的な仕組み、ブロックチェーンにとって重要である理由、ハッシュポインタについて説明します。その後、従来型と並行マークルツリーを検討し、Solanaにおける重要性を解説します。
暗号プリミティブとは？
暗号プリミティブとは、暗号プロトコルや暗号システムを構築する基礎となる処理またはアルゴリズムです。暗号プロトコルに対する暗号プリミティブは、分子に対する原子のようなものであり、より複雑なソリューションを構成する基本要素です。乱数生成器、コミットメント方式、公開鍵暗号は、いずれも暗号プリミティブの例です。
暗号プリミティブは、単独では非常に限定的です。組み合わせることで、認証、機密性、完全性などの基本的なセキュリティ機能を提供します。暗号プリミティブの組み合わせは非常に繊細なプロセスであり、慎重な計画と、各プリミティブが互いにどう作用するかについての深い理解が必要です。このプロセスでは、達成したいセキュリティ目標を踏まえ、セキュリティ上の考慮事項に注意を払う必要があります。暗号プリミティブを組み合わせる方法は、大きく次のように分類できます。
- 逐次合成：プリミティブを順番に適用します（例：ハッシュチェーン）
- 並列合成：複数のプリミティブを同時かつ独立して使用します（例：データの暗号化とハッシュ化を同時に行う）
- 階層合成：ある暗号プリミティブを別の暗号プリミティブの内部で使用します（例：マークルツリー）
暗号プリミティブとは何か、どのように機能するか、組み合わせる際にどのような微妙な点があるかを理解すると、安全で効率的なシステムを理解し、設計できるようになります。最も広く使われ、組み合わされている暗号プリミティブの1つがハッシュ関数です。
ハッシュ関数とは？
ハッシュ関数とは、任意のサイズのデータを受け取り、固定サイズの値を返す暗号関数です。この関数が返す値は、ダイジェストまたはハッシュと呼ばれます。代表的なハッシュアルゴリズムには、SHA-1、SHA-2、SHA-3、MD5、Argon2があります。ハッシュ関数はブロックチェーンのあらゆる場所で使われるため、その概要と仕組みを理解することが重要です。
簡単なたとえ
豪華なチョコレートケーキを焼く場面を想像してください。ケーキは何層にも重なり、各層にはそれぞれ異なる材料が使われています。ケーキを焼いていると、友人から何をしているのか尋ねるメッセージが届きました。ケーキの作り方や使ったすべての材料を詳しく説明するのは、かなり面倒です。そこで代わりに、チョコレートケーキの写真を友人に送ることにしました。
この場合、ケーキの写真がハッシュの役割を果たします。つまり、はるかに複雑なものを単純かつコンパクトに表現したものです。友人はケーキに使われた材料を隅々まで知ることはできませんが、何を焼いたのかはよく分かります。チョコレートケーキの上にラズベリーが載っていたとしましょう。それを取り除いたり、イチゴに置き換えたりすると、ケーキの写真は完成品とまったく異なるものになります。同様に、ハッシュ化するデータを変更すると、新しいハッシュ値が生成されます。
優れた暗号学的ハッシュ関数の特性
実のところ、先ほど示したハッシュ関数の定義には誤解を招く部分があります。ハッシュ関数が可変サイズのハッシュを返すこともあり得ます。異なる2つの入力に対して同じハッシュを返すこともあり得ます。また、ハッシュから元の入力を非常に簡単に逆算できる場合もあります。先ほどの定義は、優れた暗号学的ハッシュ関数についてのものでした。では、暗号学的ハッシュ関数を優れたものにする要素は何でしょうか？
優れたハッシュ関数は決定的です。つまり、同じ入力からは必ず同じ出力が生成されます。「baseball」という入力をハッシュ化すると、どのシステムでも、そのハッシュ関数は毎回同じハッシュを出力します。また、これは入力のサイズにかかわらず、ハッシュのサイズが同じになることも意味します。これは処理効率とデータ保存にとって重要です。一意の入力からは常に一意の出力が生成され、その出力が常に固定サイズになることは、優れた暗号学的ハッシュ関数の明確な指標です。
優れたハッシュ関数は原像計算困難性を備えています。これは、ハッシュを基に入力値を逆算することが、計算上実行不可能であることを意味します。つまり、あるハッシュを渡されても、そのハッシュを生成したデータを特定できない必要があります。これは、異なる2組のデータが同じハッシュを生成してはならないという考えにもつながります。任意の2つの入力が決して同じハッシュを生成しない場合、その優れたハッシュ関数は衝突耐性があるとされます。
優れたハッシュ関数は雪崩効果を備えています。入力にわずかな変更を加えるだけで、ハッシュは大幅に変化する必要があります。1文字変更しただけでも、まったく異なるハッシュが生成されるべきです。したがって、ハッシュ出力から入力に関する情報が明らかになったり、認識可能なパターンが現れたりしてはなりません。上の図でハッシュがどのように異なるかに注目してください。赤いキツネが「走る」場合と「歩く」場合では、まったく異なるハッシュが生成されます。また、この2つのハッシュにほぼ同一の情報が含まれていることを示すものもありません。
優れたハッシュ関数は、高速に計算できる必要があります。低速なハッシュ関数は、トランザクション検証のようなリアルタイムまたはほぼリアルタイムの計算には実用的ではありません。低速なハッシュ関数は深刻なボトルネックとなり、スループットとネットワーク性能の両方を制限する可能性があります。ブロックチェーン上で効率的かつ安全に動作させるには、高速なハッシュ関数が必要です。
なぜブロックチェーンにとって重要なのですか？
ブロックチェーンは、ネットワーク全体のトランザクションを記録する、非中央集権型の分散台帳です。これらのトランザクションはブロックにまとめられ、優れたハッシュ関数によって安全に連結されます。各ブロックには、トランザクションデータ、タイムスタンプ、直前のブロックのハッシュが含まれます。各ブロックのハッシュは直前のブロックのハッシュに依存するため、ブロックの内容を変更するとそのハッシュが変わり、後続のすべてのブロックが無効になります。以前のハッシュを使って新しいハッシュを生成するこのプロセスは、ハッシュチェーンと呼ばれます。
ブロックチェーンに新しいブロックを追加することは、承認と呼ばれます。承認により、新しいブロック内のすべてのトランザクションと、それ以前のすべてのブロックが検証され、安全になります。新しい承認が増えるたびに、過去のブロックを変更することが難しくなるためです。過去のブロックを変更するには、攻撃者はそれ以降のすべてのハッシュを再計算する必要があります。このように、ハッシュチェーンによって、十分な数の承認を得たブロックがあるブロックチェーンを改ざんすることは事実上不可能になります。
簡単に言えば、ブロックチェーンとは、ハッシュ関数によって保護されたブロックの連鎖です。しかし、あるブロックから別のブロックを具体的にどう参照するのでしょうか？確かに、ブロック同士の連結には暗号学的ハッシュ関数が使われますが、過去のブロック内のデータをどうやって確認できるのでしょうか？優れた暗号学的ハッシュ関数は原像計算困難性を備えているはずです。
ハッシュポインタとは？
ポインタとは、特定のデータがメモリ内のどこに保存されているかを示す位置情報を保持する変数です。ポインタがデータの位置を「指し示す」ため、そのメモリアドレスにあるデータへ簡単にアクセスできます。ハッシュポインタはポインタに似たデータ構造ですが、参照先データの暗号学的ハッシュも含みます。そのため、ハッシュポインタは特定のデータへのアクセス先を示すと同時に、アクセスしたデータの完全性を確認できるようにします。
ブロックチェーンの構造は、ハッシュポインタを使用する連結リストと表現する方が正確です。直前のブロックのハッシュは、トランザクションの集合と、そのすべてのトランザクションのハッシュを指すハッシュポインタです。ハッシュポインタにより、ブロックの連結、各ブロックの完全性の確保、新しく追加されたブロックが直前のブロックへ正しく続いていることの検証が可能になります。
ハッシュポインタは、ブロック同士を効率的に連結するために使われます。では、ブロック内のトランザクションについてはどうでしょうか？1つのブロックに1,000件のトランザクションが含まれている場合、それぞれを個別に検証するのは高コストではないでしょうか？
マークルツリーとは？
マークルツリーは、大規模なデータ集合を整理して検証するためのデータ構造です。データはツリー状の構造に整理され、各葉またはノードにはデータ集合のハッシュが付けられます。葉ではない各ノードは、その子ノードのハッシュです。マークルツリーは、ブロックチェーンへ伝播される特定のブロックに含まれるトランザクションの検証に使われます。では、どのような仕組みなのでしょうか？
トランザクションはリストにまとめられ、ブロックを形成します。リスト内の各トランザクションは、優れたハッシュ関数を使ってハッシュ化されます。これらのハッシュが葉ノードになります。葉ノードを2つずつ組み合わせてハッシュ化し、新しいハッシュの層を作ります。この処理を反復し、マークルルートと呼ばれる1つのハッシュだけが残るまで続けます。マークルルートはブロックのヘッダーに保存され、そのブロック内にあるすべてのトランザクションのデジタルフィンガープリントとして機能します。マークルルートは、ブロックのハッシュとも呼べます。したがって、新しいブロックが直前のブロックのblockhashを使って連結されるというのは、新しいブロックのハッシュの一部として、直前のブロックのマークルルートが使われるという意味です。
マークルツリーを使うと、ブロック内の個々のトランザクションを効率的に検証できます。従来、特定のトランザクションを検証するには各トランザクションを検証する必要があり、コストも時間もかかりました。マークルツリーは、マークル証明と呼ばれる暗号学的な「近道」を提供し、この検証プロセスを支援します。マークル証明とは、トランザクションの葉ノードからマークルルートまでの経路です。上の図では、Data Aからマークルルートまでの経路と考えてください。この経路には兄弟ノード、つまり経路上の各ノードに隣接しながら、経路自体には含まれない葉も含まれます。検証者は証明経路を使ってハッシュを計算し、そのハッシュがマークルルートと一致するか確認できます。結果のハッシュが一致すれば、検証者はトランザクションが正当であり、改ざんされていないと確信できます。
新しい葉のデータをハッシュ化し、マークルルートを再計算することで、葉を変更できます。この新しいマークルルートは変更後の状態の検証に使われ、以前の証明は無効になります。Solanaのような高スループットのネットワークでは、バリデータがオンチェーンのマークルツリーに対する変更リクエストを短時間に連続して受信することがあります（同じスロット内など）。各データ変更を順番に再計算しなければ、同じスロット内で先に行われた変更リクエストによって、後続の変更リクエストが無効になります。葉のデータを変更して新しいマークルルートを計算する処理は、ブロックチェーンで頻繁に行われます。では、短時間に相次ぐ変更にはどう対処するのでしょうか？
並行マークルツリーとは？
並行マークルツリーは、読み取りと書き込みを並行して行えるよう最適化されたマークルツリーです。直近の変更、それぞれのルートハッシュ、その導出に必要な証明を記録した安全な変更履歴を保持します。この変更履歴は、ツリー専用のアカウントにオンチェーンで保存されます。また、マークルルートの有効性を維持したまま適用できる変更数には上限があります。この変更数の上限はmaxBufferSizeと呼ばれます。そのため、バリデータがオンチェーンのマークルツリーに対する変更リクエストを短時間に連続して受信した場合、この変更履歴を信頼できる情報源として使用し、同じスロット内でツリーに最大maxBufferSize件の変更を適用できます。
並行マークルツリーは従来のマークルツリーを改良したもので、Solanaのような高スループット環境に適しています。Solana上にオンチェーンの並行マークルツリーを作成する際は、ツリーのサイズ、作成コスト、ツリーに同時に適用できる変更数に影響する3つのプロパティがあります。
- 最大深度
- 最大バッファサイズ
- キャノピー深度
最大深度とは、任意の葉からマークルルートへ到達するまでに必要な最大ホップ数です。maxDepthは、ツリー内に保存できるノードの最大数を決定するために使われます。これは次の式で計算できます：numberOfNodes = 2 ^ maxDepth。ツリーの深度は作成時に設定する必要があるため、この式を使ってツリーに保存したいデータ数を決めることが重要です。
前述のとおり、最大バッファサイズとは、マークルルートの有効性を維持したままツリーに適用できる変更数の上限です。
キャノピー深度とは、オンチェーンに保存されるマークルツリーの一部分を指します。キャッシュされたこれらの証明は、ハッシュをオンチェーンのマークルルートと照合するために使われます。葉への書き込み時に元の所有権を検証するには、完全な証明経路を使用する必要があります。たとえば、NFTを転送する場合はツリーへの書き込みが必要です。キャノピーを使うと証明サイズを縮小でき、ツリーの検証にmaxDepthの証明サイズを使わずに済みます。maxDepthが20のツリーには、20の証明サイズが必要です。キャノピーが15の場合、書き込みトランザクションごとに送信する必要がある証明サイズは5だけです。つまり、キャノピー深度を大きくすると初期コストは高くなりますが、後から送信する証明を小さくできます。
キャノピー深度は、ツリーの作成コストを大きく左右します。キャノピー深度が大きいほど、必要なアカウントも大きくなるためです。開発者は@solana/spl-account-compressionパッケージを使って、指定したツリーサイズに必要な領域と、オンチェーンでその領域をツリーに割り当てるためのコストを計算できます。開発者はgetConcurrentMerkleTreeAccountSize関数を使い、パラメータに基づいて指定したアカウントに必要な領域を計算できます。さらに、必要な領域に対してgetMinimumBalanceForRentExemptionを使うことで、Lamports単位の最終コストを算出できます。
Solanaは、状態圧縮に並行マークルツリーを利用しています。状態圧縮とは、オフチェーンデータのハッシュを作成し、安全に検証できるようオンチェーンへ保存する手法です。状態圧縮の最も一般的なユースケースは圧縮NFTです。ミントのコストを大幅に削減できるためです。たとえば、Solanaで10億個のNFTをミントするコストは507 $SOLであり、「通常」のNFTでは12 000 000 $SOLかかります。ハッシュ化とマークルツリーについて十分に理解できたところで、今後の記事では圧縮NFTについて詳しく解説します。
まとめ
お疲れさまでした。この記事では、ブロックチェーンに不可欠な2つの暗号プリミティブであるハッシュ関数とマークルツリーを分析しました。ブロックチェーンを理解するのは容易ではありません。幅広い技術的理解を必要とする複雑な分散システムだからです。一般的な開発者、ユーザー、投資家には、この知識があることを前提とされる場合が少なくありません。この記事では、暗号プリミティブに関する事前知識を前提としていません。基礎から始め、従来型と並行マークルツリーに関する、より複雑な説明へと進みました。圧縮NFTのような、さらに複雑なトピックを掘り下げる準備として、この基礎を理解しておくことが極めて重要です。今回得た知識により、暗号プリミティブや、より複雑な暗号ソリューションに関するコードベースや議論を、これまで以上に理解しやすくなります。
ここまで読んでくださった皆さん、ありがとうございます！
追加リソースと参考資料
関連記事
Heliusを購読
Solana開発の最新情報や新しい記事の公開通知を受け取れます