なるほど!をお届けする仮想通貨情報メディア

  • BTCBTC

    387,640円

  • ETHETH

    10,016円

  • ETCETC

    442.94円

  • LTCLTC

    2,718.5円

  • BCHBCH

    11,679円

  • XRPXRP

    33.911円

  • LSKLSK

    0.0000円

  • XEMXEM

    8.0199円

merkle treeからみる量子コンピューター耐性をもつ署名の探求

 

導入

ブロックチェーンは各ブロックが鎖のように繋がることでデータを連続して保管する台帳技術です。各ブロックにはトランザクションデータが格納されており、トランザクションの増加とともに書き込まれるデータが増加してしまい、ネットワークに負荷がかかってしまうので、データを効率よく書き込む技術が発明されています。

 

署名

公開鍵方式を用いてメッセージを暗号化することでプライバシーが担保される一方で、その送信の最中に改ざんされたりなりすましをされたりするリスクがあります。

そのリスクである改ざんなしとなりすましなしを確認するためにデジタル署名を行います。一般的にメッセージをハッシュ関数に通し、細かく切り刻むことで一定の長さのダイジェストを作ります。

異なる平文から同一のダイジェストが取得されることは計算上ありえず、また平文からダイジェストを作れてもダイジェストから平文を取得することはできません。

 

ハッシュ関数

例えば、広く用いられているSHA-256は平文から256ビットのダイジェストを取得します。ダイジェストは平文のファイルサイズに関わらず一定のサイズで取得されることがポイントです。

 

merkle tree(マークルツリー)

マークルツリーは、1979年ラルフ・マークルによって発明され、ハッシュ木とも呼ばれています。元々の目的は大量のランポート署名を効率よく管理することでした。

マークルツリーは、ファイルなどの比較的大きなデータを要約しデータを格納するツリー構造の管理方法の一種です。

大きなデータを要約し、検証を行う際に役立ちます。

要約する時に通常SHA-1、Whirlpool、Tigerなどといった暗号学的ハッシュ関数を使用します。ハッシュ関数は、入力されたデータを一定の長さの値にして返す一方向性の関数で、この処理を繰り返すことで、より短い値になります。

ハッシュ木はノードにハッシュ値を持つ二分木であり、葉の部分にはでデータブロックのハッシュ値が入っています。葉から、より上位のノードにはそれぞれの子ノードのハッシュ値を足し合わせてハッシュ化した値が入っており、繰り返すことで、トップの値であるマークルルートを取得することができます。

出典:http://gaiax-blockchain.com/merkle-tree

 

ビットコインへの応用例

ブロックチェーンには、ブロックヘッダーと呼ばれるブロックの情報が書き込まれている部分があります。

ブロックヘッダーには、①ひとつ前のブロックのハッシュ値、②(Proo of Work)ナンス、③取引記録全体を表すマークルートで構成されています。

この各トランザクションのハッシュ値をマークルツリーを活用することで、ブロック毎にひとつのハッシュにまとめあげることができます。

二つの取引データのハッシュ値を足し合わせて、ハッシュ化する作業を繰り返して、最終的にマークルルートを得ることができます。

このマークルルートをブロックヘッダーに格納することで、ブロックに書き込まれている全トランザクションの値が改ざんされていないことを証明することができます。

 

SPV(Simplified Payment Verification)

ビットコインのブロックチェーン上で取引データをひとつにまとめあげたマークルルートを活用しているのが、SPVと呼ばれる方式です。

ブロックチェーンに保存されている取引データを全てダウンロードする必要がなく、取引の整合性を確認することができます。

一般的に使用される振るノードでは、起動する際に最初から現在までのブロックの取引データを全てダウンロードしなくてはいけないので、効率化が図れるためライトウォレットとして利用できます。

 

Lamport Signature(ランポート署名)

ランポート署名は、量子コンピューター耐性がある署名方式の一種ですが、単独ではひとつの秘密鍵にひとつのメッセージの署名にしか使用できないという制限があります。

なので、ランポート署名にマークルツリーとを組み合わせることで、ひとつの秘密鍵に対して複数のメッセージを付加して署名できるようになり、効率的なデジタル署名を実現できます。



秘密鍵と公開鍵の作成

通常暗号化では、メッセージと秘密鍵を使用してハッシュ化し、公開鍵を作成します。この際に秘密鍵を使用して署名します。

秘密鍵を256対、計512個の乱数を作成し、その乱数全てをハッシュ化した値を公開鍵とします

 

署名と検証の簡単な流れ

1.まずメッセージをハッシュ化する

2.次に、そのハッシュ値をSHA-256に通し、二進数に変換する

3.「0=a」、「1=b」として置換する。256ビット分。

4.左からn番目の文字がaであれば乱数対nではaを、同様にbでも行う

5.公開された256個の乱数(秘密鍵)によって検証された署名と、ハッシュ値(公開鍵)が等しいか確認する。

出典:https://moblock.jp/articles/17845

 

ランポート署名のメリット

現在の量子コンピューターの処理能力からすると、ひとつの公開鍵のハッシュ値から秘密鍵を求めるのに1分かかると言われており、256対の秘密鍵からメッセージを作成するのに計256分かかります。

ビットコインのブロック生成時間は10分と言われており、改ざんはスピード的な問題から不可能です。

また、マークル木と組み合わせたことで、多数のメッセージをハッシュ化し、組み合わせたので、大幅なコストとデータの削減になります。

 

Markle tree signature schemes(マークル木署名のスキーム)

ランポート署名は、署名とトランザクションの検証に対して満足のいく暗号セキュリティを提供してくれる一方で、それは一度秘密鍵が安全に使用されるだけであるということです。

もし、台帳アドレスが単一のOTS(one time signature)鍵ペアから生成された場合、きわめて制限されたブロックチェーン台帳を導くことになり、それは量子コンピューターへの脆弱性を示すことになります。

よって、今後の量子コンピューターの非線形な進歩を考慮すると、先ほど示したマークル木とランポート署名では不安が残るということです。

解決策のひとつとして、各台帳に対してひとつ以上の有効なOTS署名を合併して利用することで、署名スキームを拡張する戦略があります。

 

ランポート署名を利用する通貨の例

NEO(ネオ)

中国版イーサリアムとして有名で、分散型アプリケーションのプラットフォームです。イーサリアムに比較して取引速度が速かったり、開発言語が豊富な点が便利です。

公式サイト:https://neo.org/

Cardano(カルダノ)

独自に改良されたスマートコントラクト「Plutus」を活用して不正の起きないオンラインカジノゲームを提供することを目指します。

公式サイト:https://www.cardano.org/ja/home-2/

IOTA(アイオータ)

Iot機器の使用におけるシステム決済で発生するマイクロペイメントを可能にするプラットフォームです。独自アルゴリズムDAG(有向非循環グラフ)を採用することで取引手数料を無料にしています。

公式サイト:https://www.iota.org

SHIELD(シールド)

「匿名性」「耐量子性」「省電力性」の3つを同時に実現することを目的に作られた仮想通貨です。人気SNSで使用される通貨を目指しており、そのために便利な特徴をいくつか備えます。

公式サイト:https://shieldcurrency.com/

まとめ

現在量子コンピューターは、まだ実用段階に至っておらずブロック生成より遅いため改ざんされる心配はありません。

更に通常の署名方式よりも優れた量子コンピューター耐性のあるランポート署名を用いれば更にその可能性を軽減することができます。この署名方式にマークル木を組み合わせれば複数のメッセージをハッシュ関数SHA-256に通し、ダイジェストを作成し、そのマークル木から親マークル木を取得という流れを繰り返すことで、大幅な効率化と署名データサイズの削減が見込めます。

一方で、このマークル木とランポート署名の組み合わせる方法では、使用するハッシュ関数をSHA-256に依存しており、仮に量子コンピューターが非線形な進歩を遂げた場合、単一の関数から取得される公開鍵のハッシュは容易に脆弱性を突かれる心配があります。

そのため、より安心できる量子コンピューター耐性の署名方式として、有効な署名方式を併用して用いることが大事だとしています。

このソリューションはQuantum resistant ledger(クオンタム レジスタント レジャー)という量子コンピューター耐性をもった技術開発を進めているプロジェクトが提示しています。仮に現実となった場合、全ての取引履歴が改ざんされアドレスに保管するコインは全て盗難され、ビットコインをはじめとする仮想通貨は大きな影響を受けるでしょう。そういったことを現在の余裕ある段階で対策しておくべきであると考えます。