ビットコインの計算量問題・脆弱性を抜本解決する新合意形成技術

2022.10.20 By 東京電機大学

情報

技術概要

ノードIDとブロック通番に対するディジタル署名と時刻情報のHash値が閾値以下の場合に、当該ブロックの検証者(ノード)とみなすことで、少ない計算量で不正ができない合意形成を実現する。従来技術は数学問題を解く計算量の予測不可能性を利用したが、本技術は公開鍵暗号方式の安全性を利用し、1回の計算で検証者を決定可能とした点に特徴がある。

用途・応用

・マイナンバーや健康保険番号に基づく分散台帳システム
・銀行口座番号に基づくサーバレス決済システム
・その他、ブロックチェーンの応用が期待されている全ての分野。

背景

 取引データ(以下、トランザクションデータ)を記録する分散型台帳システムにおいて、台帳の更新時にトランザクションデータの内容の正当性について利用者間で合意を取る、ブロックチェーンを用いた分散合意形成技術が提案されている。

 台帳システムは、集中型と分散型に分類できる。集中型の場合、利用者の識別子(Identifier、以下、ID)の一意性、IDに対応するIdentityの実在性を保証する機能(以下、IdP)と、利用者間のトランザクションデータの正当性を検証する機能と、それらトランザクションデータを蓄積する機能を1箇所(集中サーバ)に配備する。全利用者は集中サーバのIdP機能によりIDを割り当てられ、利用者間で取引の内容を合意すると、合意したトランザクションデータを集中サーバに登録する。集中サーバはトランザクションデータの正当性を確認すると、ディジタル署名を付与して、集中サーバ内に蓄積する。利用者が過去のトランザクションデータを閲覧したい場合は、集中サーバを参照し、集中サーバの署名によりトランザクションデータの内容が正当と判断する。ところが、集中サーバの信頼性が不確実な場合、トランザクションデータの正当性や、同一データを他の利用者も参照していることの確認(一貫性の確認)ができない問題がある。

 それら問題を解決する、分散型台帳システムが提案されている。以下に、Bitcoinの場合の実現方法を説明する。Bitcoinでは、集中サーバを設置せず、上記3機能を各利用者のノードに配備する。すなわち各利用者のノードは自分で公開鍵と秘密鍵のペアを生成し、秘密鍵を各利用者のノードが保持する。利用者のノード間で取引、例えば電子マネーの支払いが発生すると、当該取引のトランザクションデータを、全利用者のノードに転送し、全利用者のノードが全取引のデータ(台帳)を蓄積する。

 各利用者のノードは、トランザクションデータを受信すると、当該データの内容が正当かどうか、判定する。例えば、過去に同一な電子マネーの支払い(2重払い)がないことを、後述するメインチェーン内のトランザクションデータおよび、チェーンに接続せずに保持しているトランザクションデータと突合して確認する。

 各ノードは、正当と判断したトランザクションをまとめて、ブロックを構成する。図1(以下、図・式は詳細資料に記載)に、ブロックの構成を示す(図1ではトランザクションをTxとして示している)。当該検証者が受信し検証済みの1つ前のブロック(メインチェーンの最上位のブロック)のHash値(図1のPrev Hash)を付与し、当該一つ前のブロックに含まれる全トランザクションについても当該検証者が正当性を検証している、という証跡とする。図のNonceはPoW(Proof of Work)で用いる情報であるが、詳細は後述する。次に、利用者のノードの中から無作為に検証者を決定する。決定する方法は後述するPoWが使用されている。なおPoWの代替としてPoS(Proof of Stake)が提案されている。

 検証者のノードは、当該ブロックを、他の利用者のノードに転送する。他の利用者のノードは当該ブロックを受信すると、再度当該ブロック内のトランザクションの検証を行う。各トランザクションが正当であれば、当該ブロックのHash値が示すブロックに続く最上位ブロックとして保持する(以下、チェイニング)。また即時に、次のブロックを作成し、条件を満たすNonceの探索を開始する(Nonce探索の詳細は後述する)。

 ネットワーク内の転送遅延などの影響で、最上位ブロックの更新が伝わらず、古いブロックにチェイニングするブロックが遅れて到着する場合がありうる。その場合、各ノードは、チェーンを分岐し、遅れて到達したブロックを、セカンダリチェーン、分岐前のチェーンをメインチェーンとして保持する。検証者のノードはブロックをメインチェーンにチェイニングするため、多くの利用者がメインチェーンと認識した方のチェーンが長くなる。チェイニングされたブロックがメインチェーンに属する場合、そのブロックから最上位ブロックまでのブロックの繋がる数(ブロックの深さ)が大きくなるほど、当該ブロックの正当性と一貫性が、より多くの検証者に保証されたと考えることが出来る。Bitcoinでは、利用者間での合意が形成され、以降くつがえる可能性が低い安全な深さ(安全段数)として、深さ6を推奨している。

 なお、複数の利用者が結託し(以下、結託グループ)結託グループ内の利用者が連続して検証者に選ばれることに成功すると、過去に承認済みの支払いを以下に示す手順により無効にすることが出来る。

 結託グループ内の利用者の一人が、被害者に電子マネーを送金するトランザクション(以下正規トランザクション)を作成し被害者及び他の利用者に転送する。また、被害者に電子マネーを送金する前の時刻で、当該電子マネーを結託グループの別の利用者に送金するトランザクション(不正トランザクション)を作成する。次いで、当該トランザクションを含むブロックを作成し、前述の正規トランザクションを含むブロックより古いブロックにチェイニングし、チェーンを分岐する(正規であるメインチェーンと、不正なセカンダリチェーン)。ただし、当該ブロックは結託グループ以外には転送しない。なお、結託グループ内でブロックを転送する手段は任意のものを使用出来る。さらにセカンダリチェーンに続くブロックを作成する。こちらも結託グループ以外には転送しない。

 前述の生起ブロックを含むブロックの深さが十分深くなり、被害者が、当該正規トランザクションが広く承認されたと判断し、電子マネーの対価を結託グループに渡すと、結託グループは上記不正チェーンを構成するブロックを他の全利用者のノードに転送する。各利用者のノードは、不正チェーンを構成するブロック内のトランザクションを検証するが、各トランザクション(前述の不正トランザクションを含む)は正当(過去に同一電子マネーの支出はない)なため、前述のメインチェーンよりセカンダリチェーンの長さの方が長くなり、メインとセカンダリの立場が逆転し、前述の正規トランザクションは無効となる(支払いの不正取り消し)。

 ただし、「ブロックの深さが十分深い」と判断する深さ(安全段数)を長くすることで、等比級数的に、上記「支払いの不正取り消し」が成功する確率を低くすることができる。また、ネットワークの障害により、ある地域の利用者が他の利用者が接続するネットワーク(以下、インターネットとして記述する)から長時間孤立し、その後再接続した場合、以下に示す問題が発生する。

 第1に、孤立後、孤立したネットワーク内のメインチェーンが安全段数以上伸長し当該ブロックに含まれるトランザクションが確定したとみなされた後で、インターネットに再接続すると、確定したトランザクションが一旦不確定となってしまう。第2に、当該ネットワークがインターネットと孤立中に、双方のネットワークと接続する手段がある利用者のノードは、本来であればブロックを双方のネットワーク間で転送する必要がある。ところが、不正にブロックの転送を遮断し、代わりに同一電子マネーを異なる利用者向けに使用するトランザクションをそれぞれのネットワークに送信することで、不正な2重使用を実現できてしまう。

 このため、利用者のノードは、信頼する他の利用者や主要なWebサーバなどとのIP接続確認などの手段により、インターネットからの孤立を監視し、孤立中はトランザクションを生成しない(電子マネーの支払いを受け付けない)必要がある。

 利用者の中から無作為に検証者を決定する技術に、proof of works(以下、PoWと称する。)とproof of stake(以下、PoSと称する。)がある。何れも検証者になると、報酬に電子マネーを与えることで、利用者が検証者になろうとする動機としている。ただし、ブロック生成毎に、検証者が無作為に選ばれるようにする仕組みに差分がある。

 PoWはBitcoinで使用されている技術である。PoWでは、検証者になろうとする利用者のノードは、トランザクションをまとめてブロックを構成すると、当該ブロックにNonceと呼ばれる一定の長さの任意のbit列を結合してHash計算を行う。Hash結果が予め設定されている上限値(difficulty-target)以下となるNonceを最初に発見(マイニング)した利用者のノードが検証者となる。検証者の上限値は平均検証時間間隔が10分になるように調整されている。当該ブロックを転送された他の利用者のノードは、Nonceを含むブロックのHash値を計算しdifficulty-target以下であることを確認できれば、当該ブロックの検証者のノードが無作為に決定されたと判断することができる。各利用者のノードは、正当なブロックを受信すると、当該ブロック受信までに受信したトランザクションを対象として、マイニングを開始する。

 現時点では、条件に合うNonceを逆計算により導出する方法は知られておらず、Hashが取りうる値を一つずつ変化させて、条件にあう結果になるか計算する必要がある。すなわち、使用する計算機の性能に比例して検証者となれる確率が増大する。なお、通常のトランザクションは、取引物の送り元と送り先の両方が必要である。ただし、検証者になると特別に、送り元が存在しない(ブランクな)一定量の電子マネーを検証者自身に支払うトランザクション(以下、コインベーストランザクション)を当該ブロックに含める事が可能になる(新しいマネーが発生することになる)。すなわち、当該コインベーストランザクションが、検証者になったことに対する報酬である。本技術には以下に示す問題がある。

 PoWにおける問題1:公平性の逸脱
 PoWは、各利用者の利用可能な計算機リソースがほぼ同一であれば、各利用者が検証者になれる確率もほぼ同一となる。したがって、計算量に基づく公平性が保証された「くじ」と言える。しかしながら、検証者になれる確率が、当該利用者のもつ計算機リソースの量に比例するため、資金に余裕のある一部の利用者が計算機リソースに投資し、結果、公平性が損なわれる問題がある。

 PoWにおける問題2:処理量PoWは、検証者になるためには条件を満たすNonceを発見する必要があるが、膨大な量の計算が必要であり、一般ユーザ向けの安価なスマートフォンやPCは、単独では検証者になることが困難である。また、計算のために膨大な量の電力の消費が必要であり、電力料金によっては報酬を上回る可能性がある。

 PoWにおける問題2に示す処理量の問題を解決することを目的とした技術に、PoSがある。PoSでは、電子マネーを多く持つ利用者は不正をしない、と仮定し、保有する電子マネーの量に基づく公平な「くじ」の実現をねらっている。PoSでは各利用者のノードは1秒毎に以下の計算(以下、富くじ)を行い、各利用者のIDが以下の式(1)を満たす場合(以下、富くじに当選)、検証者となる資格を得る(検証者候補)。
(数1)
 Hash[前のブロックのHash値+自分のID+TS]<Stake/調整係数⋯式(1)

 なお左辺はHash長をLとした時に、2^Lで除して0~1(double)の範囲に正規化されているものとする。TS(タイム スタンプ)は上記富くじを引く時刻(1秒単位)、Stakeは自分(当該ID)に紐づく電子マネーの総額である。調整係数は、当選確率を調整するためのパラメータである。

 TSがHashの入力にあるのは、1回の富くじで当選者が出ない場合、当選者が現れるまで再度富くじを引くためである。ここで、「+」はbit列の結合を意味する。あるデータのHash計算を行うと、その結果は当該データと相関のない値を取り、逆計算は困難である。よって式(1)のHashの入力値(前のブロックのHash、自分のID、TS)の全てが恣意的に選択出来ない場合、当該ブロックの検証者候補が無作為に決定されたと判断することができる。

 PoSでは利用者がもつIDは一人につき1つであり、トランザクション中に、送金後の送信元IDの持つ電子マネーの量Stakeが記載される。富くじに当たった検証者候補は、当該ブロックに報酬となるコインベーストランザクションを追加し、当該ブロックを全利用者に転送する。各利用者のノードは、受信したブロックについて、式(1)を計算し、式(1)を満たし、かつ、最初に当該利用者に到達したブロックを有効とする。すなわち、当該ブロックを作成した検証者候補が検証者となる。なお、利用者自身が自分のIDを作れるが、ID生成直後はStakeが0なため、IDの生成により不正に当選することは出来ない。以前にトランザクションを生成していないIDを除外する方法もある。本PoS技術には以下に示す問題がある。

 PoSにおける問題1:検証者当選確率の不正制御
 PoSでは、検証者のノードは、受信したトランザクションの中で、どれをブロックに加えるか選ぶことが出来る。n個のトランザクションについて、ブロックに加えるか除くか制御できる場合、当該ブロックのHash値を2^n個の中から選択することができてしまう。また新たなトランザクションを生成し、Hash値を変更することもできる。すなわち、今回当選した検証者が、結託者グループのメンバーであり、他の結託者のIDを知っている場合、他の結託者が次のブロックの富くじに当たる確率を制御できることになる。このため、結託者グループの誰かが運良く当選すると、当該グループの誰かが引き続く複数のブロックの検証者になれる確率を高くできる。PoSではお金持ちは不正をしない、と仮定しているので、連続してStakeが少ない検証者が当選している場合、不正があったと判断することが出来るが、どの程度有効に攻撃を検出できるか不明確である。また検証者が公正に富くじに当選しているにもかかわらず、不正があったと判断される可能性もある。

 PoSにおける問題2:転送遮断攻撃に対する安全性
ブロックチェーン技術では、ブロックは、利用者間で転送されて、全利用者に行き渡る。各利用者のノードは自分がメインチェーンの最上位と認めたブロックを、他の多くの利用者もメインチェーンの最上位と認めたほうが都合が良い(メインチェーン内で承認されれば、報酬を使用できるようになる)。このため、通常は、ブロックの転送を遮断する動機はない。ところが、PoSの式(1)の計算は、検証者候補以外でも実施することができる。このため、前のブロックを転送する利用者のノードは、転送先の利用者が当選するかどうか、転送前に評価することが出来るので、当該利用者へは当該ブロックを転送しないDoS攻撃が可能である。

 PoSにおける問題3:公平性の逸脱本PoS技術では、保持する電子マネーが多いと、プログラムを起動しておくだけで、検証者に当選し、報酬を得ることができる。また、お金持ちは不正をしない、との仮説に基づいているため、お金持ちであれば不正に成功する確率が高いと言うことも出来る。

課題

 本開示は、PoWにおける公平性の逸脱及び処理量、並びにPoSにおける検証者当選確率の不正制御、転送遮断攻撃に対する安全性及び公平性の逸脱の問題を解決することを目的とする。すなわち、本開示は、検証者候補の当選がノードの処理能力に依存することなく公平であり、かつ検証者候補の不正制御や転送遮断攻撃を防ぐことを目的とする。

手段

 本開示のノードは、自新規ブロックに適用する自ノードの暗号化IDを、自ノードに固有のIDに秘密鍵を適用することで生成し、他のノードと共通の演算式に、自ノードの暗号化ID及び前記新規ブロックを追加するブロックチェーンに既に含まれるブロックのうちの予め定められたブロックに格納されている暗号化IDを適用し、自ノードのHash値を求め、自ノードのHash値を用いて自ノードが当選したか否かを判定する。

 本開示の当選者決定方法は、ノードが、新規ブロックに適用する自ノードの暗号化IDを、自ノードに固有のIDに秘密鍵を適用することで生成し、他のノードと共通の演算式に、自ノードの暗号化ID及び前記新規ブロックを追加するブロックチェーンに既に含まれるブロックのうちの予め定められたブロックに格納されている暗号化IDを適用し、自ノードのHash値を求め、自ノードのHash値を用いて自ノードが当選したか否かを判定する。

効果

 本開示によれば、検証者候補の当選がノードの処理能力に依存することなく公平であり、かつ検証者候補の不正制御や転送遮断攻撃を防ぐことができる。

問い合わせ・詳細資料閲覧

特許情報詳細や資料のダウンロード等については無料会員登録後に閲覧していただけます。

本研究に関するご質問や、話を聞いてみたいなどご興味をお持ちになりましたら、是非お気軽に以下のフォームにお問い合わせください。

MktoForms2.loadForm(“//mk.as-1.co.jp”, “118-QIN-675”, 1351);

特許情報

特願2018-114659

JPB 007044364-000000