(57)【要約】【課題】合意形成に参加する複数のノードを有するネットワークにおいてｆ個のビザンチン障害ノードを仮定したときに適した合意形成方法を提供する。【解決手段】各ノードは待ちの状態にあり（Ｓ３０１）、決定論的な計算によって当該ラウンドにおける提案者１３０が選ばれる。提案者１３０は、合意形成対象のデータを含むメッセージを各ノードに送信する。提案者は送信により、他のノードは当該メッセージを受信したことに応じて提案済みとなる（Ｓ３０２）。提案を受領した各ノードは提案の有効性を判定し、有効な場合その旨の投票メッセージを送信する。各ノードは、受信した投票メッセージの数が所定の値Ｑに達した場合、提案を受け入れる旨のメッセージを送信する（Ｓ３０３−１）。次に、各ノードは、受信した受け入れメッセージの数が値Ｑに達した場合、提案を合意されたものとして扱う旨のメッセージを送信して合意形成プロセスを完了する（Ｓ３０４）。【選択図】図３
2019012415.tif 000002
【特許請求の範囲】
【請求項１】
合意形成に参加するＮ個（Ｎは１以上の整数）のノードを有するネットワークにおいてｆ個（ｆは１以上Ｎ／３未満の整数）のビザンチン障害ノードを仮定したときに適した合意形成方法であって、
他のノードから、合意形成の対象となるデータを含むメッセージを提案として有効と判定した旨の第１のメッセージを受領するステップと、
受領した第１のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を受け入れる旨の第２のメッセージを送信し、所定時間内に、有効な第１のメッセージの数が前記所定の値Ｑに達しない場合、各ノードに、自ノードは前記提案を却下する旨の第３のメッセージを送信するステップと、
受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を前記ネットワークにおいて合意されたものとして扱う旨の第４のメッセージを送信するステップと
を含むことを特徴とする合意形成方法。
【請求項２】
ｆの値が既知の場合、前記所定の値Ｑは、（ｆ＋Ｎ＋１）／２以上の整数であることを特徴とする請求項１に記載の合意形成方法。
【請求項３】
前記ｆは、Ｎ／３未満であることを特徴とする請求項２に記載の合意形成方法。
【請求項４】
第２のメッセージを定期的又は断続的に送信することを特徴とする請求項１から３のいずれかに記載の合意形成方法。
【請求項５】
他のノードから自ノード以上のラウンド（合意形成の過程の単位を「ラウンド」と呼ぶ。）における第２のメッセージを受信した場合、各ノードに、前記第２のメッセージを送信するステップをさらに含むことを特徴とする請求項１から４のいずれかに記載の合意形成方法。
【請求項６】
他のノードから第４のメッセージを受信した場合、合意形成を完了させることを特徴とする請求項１から５のいずれかに記載の合意形成方法。
【請求項７】
第３のメッセージを定期的又は断続的に送信することを特徴とする請求項１から６のいずれかに記載の合意形成方法。
【請求項８】
受領した第３のメッセージの数が所定の数Ｑに達した場合、各ノードに次のラウンド（合意形成の過程の単位を「ラウンド」と呼ぶ。）に進むための第５のメッセージを送信するステップをさらに含むことを特徴とする請求項１から７のいずれかに記載の合意形成方法。
【請求項９】
他のノードから同一のラウンド又は自ノードよりも大きなラウンドにおける第５のメッセージを受信した場合、各ノードに、前記第５のメッセージを送信するステップをさらに含むことを特徴とする請求項８に記載の合意形成方法。
【請求項１０】
前記提案を行うノードをラウンドごとに（合意形成の過程の単位を「ラウンド」と呼ぶ。）決定論的に選択するステップをさらに含むことを特徴とする請求項１から９のいずれかに記載の合意形成方法。
【請求項１１】
各ノードは、順序付け可能な識別子が割り振られ、
前記選択は、ラウンド数をｒとしてｒ  ｍｏｄ  Ｎにより定まる順序のノードが選ばれることを特徴とする請求項１０に記載の合意形成方法。
【請求項１２】
受領した第１のメッセージの数が所定の値Ｑに達した場合又は他のノードから第２のメッセージを受領した場合、ロックを設定して以後の動作を限定することを特徴とする請求項１から１１のいずれかに記載の合意形成方法。
【請求項１３】
前記限定は、提案を行うノードとして選択された場合、ロック時と合意形成対象のデータが同一の提案を行うことを含むことを特徴とする請求項１２に記載の合意形成方法。
【請求項１４】
前記限定は、提案を受領した場合、ロック時の合意形成対象のデータと同一のデータが合意形成対象であるときに、提案として有効と判断した旨の第１のメッセージを送信可能とすることを含むことを特徴とする請求項１２に記載の合意形成方法。
【請求項１５】
自ノードのロック時よりも大きなラウンドにおける受け入れメッセージを受領した場合、前記大きなラウンドにおける合意形成対象のデータについて新たにロックを設定して以後の動作を限定することを特徴とする請求項１２から１４のいずれかに記載の合意形成方法。
【請求項１６】
前記第２のメッセージは、前記所定の値Ｑが満たされたと判定した根拠となる証拠データを含むことを特徴とする請求項１から１５のいずれかに記載の合意形成方法。
【請求項１７】
前記第４のメッセージは、合意形成対象のデータ又はそれから計算されるハッシュ値を含むことを特徴とする請求項１から１６のいずれかに合意形成方法。
【請求項１８】
前記データはブロックであり、
各ノードは、受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードが有するブロックチェーンに前記ブロックを追加することを特徴とする請求項１から１７のいずれかに記載の合意形成方法。
【請求項１９】
コンピュータに、合意形成に参加するＮ個（Ｎは１以上の整数）のノードを有するネットワークにおいてｆ個（ｆは１以上Ｎ／３未満の整数）のビザンチン障害ノードを仮定したときに適した合意形成方法を実行させるためのプログラムであって、前記合意形成方法は、
他のノードから、合意形成の対象となるデータを含むメッセージを提案として有効と判定した旨の第１のメッセージを受領するステップと、
受領した第１のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を受け入れる旨の第２のメッセージを送信し、所定時間内に、有効な第１のメッセージの数が前記所定の値Ｑに達しない場合、各ノードに、自ノードは前記提案を却下する旨の第３のメッセージを送信するステップと、
受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を前記ネットワークにおいて合意されたものとして扱う旨の第４のメッセージを送信するステップと
を含むことを特徴とするプログラム。
【請求項２０】
合意形成に参加するＮ個（Ｎは４以上の整数）のノードを有するネットワークにおいてｆ個（ｆは１以上Ｎ／３未満の整数）のビザンチン障害ノードを仮定したときに適した合意形成を行うためのノードであって、
他のノードから、合意形成の対象となるデータを含むメッセージを提案として有効と判定した旨の第１のメッセージを受領し、
受領した第１のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を受け入れる旨の第２のメッセージを送信し、所定時間内に、有効な第１のメッセージの数が前記所定の値Ｑに達しない場合、各ノードに、自ノードは前記提案を却下する旨の第３のメッセージを送信し、
受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を前記ネットワークにおいて合意されたものとして扱う旨の第４のメッセージを送信することを特徴とするノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークにおける合意形成方法及び当該ネットワークを構成するノードに関し、より詳細には、ネットワークにおいてビザンチン障害ノードの存在を仮定したときに適した合意形成方法及び当該ネットワークを構成するノードに関する。
【背景技術】
【０００２】
ブロックチェーンが中央集権的な第三者機関による従来の信用付与のメカニズムを代替可能な技術として注目されている。「ブロック」と呼ばれるデータの単位が当該ブロックについての合意形成に参加する複数のノードに与えられ、その有効性（ｖａｌｉｄｉｔｙ）がそれぞれのノードにおいて評価（ｅｖａｌｕａｔｅ）される。所定の条件が満たされることにより、各ノードは、複数の可能性のあるブロックの中から、当該ブロックについてその採択の合意（ｃｏｎｓｅｎｓｕｓ）が形成されたと判定して、当該ブロックを受け入れる。より具体的には、当該ブロックが、各ノードが有するブロックチェーンに追加される。合意形成の対象となるブロックは、いずれかのノードによって、各ノードに対して提案される。
【０００３】
ここで、どのような手順で合意を形成するか、何を合意形成のための所定の条件とするかという合意アルゴリズムがブロックチェーンネットワークの信頼性と性能を左右する。合意アルゴリズム次第で、たとえば通信状況・電力供給等の物理的な理由により正常に動作しない障害（「良性障害（ｂｅｎｉｇｎ  ｆａｉｌｕｒｅ）」とも呼ばれる。）の許容可能な数が異なり、また、合意アルゴリズムに定められた所定のルールに従わないような任意のあらゆる障害（「ビザンチン障害（Ｂｙｚａｎｔｉｎｅ  ｆａｉｌｕｒｅ）」とも呼ばれる。）の許容可能な数が異なる。あるノードが所定のルールに従わないような場面としては、物理的な理由のほか、当該ノードに対する不正アクセスがあった場合、当該ノードの管理者自身に不正の意図があった場合等が挙げられる。
【０００４】
ブロックチェーンネットワークにどの程度の障害耐性（ｆａｕｌｔ  ｔｏｌｅｒａｎｃｅ）を要求するかは、ブロックチェーンの用途に応じて異なり、現在さまざまな可能性が探られている。特に、一定の用途においては、良性障害のみならず、所定の数のビザンチン障害ノードを許容し得るビザンチン障害耐性（Ｂｙｚａｎｔｉｎｅ  ｆａｕｌｔ  ｔｏｌｅｒａｎｃｅ）をもつ合意アルゴリズムが求められている。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
合意アルゴリズムに一般に求められる性質としては、大きく安全性（ｓａｆｅｔｙ）と活性（ｌｉｖｅｎｅｓｓ）とがあり、前者は、あるデータに対して一度合意が形成されれば正常に振る舞うノードのすべてが当該合意を覆すことなく共有することを意味し、後者は、有限時間内に合意形成が可能であることを意味する。
【０００６】
ｆ個（ｆは１以上の整数）のビザンチン障害ノードを仮定したときにどのような合意アルゴリズムの下で各ノードを動作させれば十分な安全性及び活性が得られるのか、特に現実的な時間内に得られるのかという問題は、今後のこの技術の普及の上で決定的に重要となってくる。安全性のある合意アルゴリズムは、ファイナリティがあるとも表現されることがある。
【０００７】
本発明は、このような問題点に鑑みてなされたものであり、その目的は、合意形成に参加する複数のノードを有するネットワークにおいてｆ個のビザンチン障害ノードを仮定したときに適した合意形成方法及びそのためのプログラム並びに当該合意形成方法に従って動作するノードを提供することにある。
【課題を解決するための手段】
【０００８】
このような目的を達成するために、本発明の第１の態様は、合意形成に参加するＮ個（Ｎは１以上の整数）のノードを有するネットワークにおいてｆ個（ｆは１以上Ｎ／３未満の整数）のビザンチン障害ノードを仮定したときに適した合意形成方法であって、
【０００９】
他のノードから、合意形成の対象となるデータを含むメッセージを提案として有効と判定した旨の第１のメッセージを受領するステップと、受領した第１のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を受け入れる旨の第２のメッセージを送信し、所定時間内に、有効な第１のメッセージの数が前記所定の値Ｑに達しない場合、各ノードに、自ノードは前記提案を却下する旨の第３のメッセージを送信するステップと、受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を前記ネットワークにおいて合意されたものとして扱う旨の第４のメッセージを送信するステップとを含むことを特徴とする。
【００１０】
また、本発明の第２の態様は、第１の態様において、ｆの値が既知の場合、前記所定の値Ｑは、（ｆ＋Ｎ＋１）／２以上の整数であることを特徴とする。
【００１１】
また、本発明の第３の態様は、第２の態様において、前記ｆは、Ｎ／３未満であることを特徴とする。
【００１２】
また、本発明の第４の態様は、第１から第３のいずれかの態様において、第２のメッセージを定期的又は断続的に送信することを特徴とする。
【００１３】
また、本発明の第５の態様は、第１から第４のいずれかの態様において、他のノードから自ノード以上のラウンド（合意形成の過程の単位を「ラウンド」と呼ぶ。）における第２のメッセージを受信した場合、各ノードに、前記第２のメッセージを送信するステップをさらに含むことを特徴とする。
【００１４】
また、本発明の第６の態様は、第１から第５のいずれかの態様において、他のノードから第４のメッセージを受信した場合、合意形成を完了させることを特徴とする。
【００１５】
また、本発明の第７の態様は、第１から第６のいずれかの態様において、第３のメッセージを定期的又は断続的に送信することを特徴とする。
【００１６】
また、本発明の第８の態様は、第１から第７のいずれかの態様において、受領した第３のメッセージの数が所定の数Ｑに達した場合、各ノードに次のラウンド（合意形成の過程の単位を「ラウンド」と呼ぶ。）に進むための第５のメッセージを送信するステップをさらに含むことを特徴とする。
【００１７】
また、本発明の第９の態様は、第８の態様において、他のノードから同一のラウンド又は自ノードよりも大きなラウンドにおける第５のメッセージを受信した場合、各ノードに、前記第５のメッセージを送信するステップをさらに含むことを特徴とする。
【００１８】
また、本発明の第１０の態様は、第１から第９のいずれかの態様において、前記提案を行うノードをラウンドごとに（合意形成の過程の単位を「ラウンド」と呼ぶ。）決定論的に選択するステップをさらに含むことを特徴とする。
【００１９】
また、本発明の第１１の態様は、第１０の態様において、各ノードは、順序付け可能な識別子が割り振られ、前記選択は、ラウンド数をｒとしてｒ  ｍｏｄ  Ｎにより定まる順序のノードが選ばれることを特徴とする。
【００２０】
また、本発明の第１２の態様は、第１から第１１のいずれかの態様において、受領した第１のメッセージの数が所定の値Ｑに達した場合又は他のノードから第２のメッセージを受領した場合、ロックを設定して以後の動作を限定することを特徴とする。
【００２１】
また、本発明の第１３の態様は、第１２の態様において、前記限定は、提案を行うノードとして選択された場合、ロック時と合意形成対象のデータが同一の提案を行うことを含むことを特徴とする。
【００２２】
また、本発明の第１４の態様は、第１２の態様において、前記限定は、提案を受領した場合、ロック時の合意形成対象のデータと同一のデータが合意形成対象であるときに、提案として有効と判断した旨の第１のメッセージを送信可能とすることを含むことを特徴とする。
【００２３】
また、本発明の第１５の態様は、第１２から第１４のいずれかの態様において、自ノードのロック時よりも大きなラウンドにおける受け入れメッセージを受領した場合、前記大きなラウンドにおける合意形成対象のデータについて新たにロックを設定して以後の動作を限定することを特徴とする。
【００２４】
また、本発明の第１６の態様は、第１から第１５のいずれかの態様において、前記第２のメッセージは、前記所定の値Ｑが満たされたと判定した根拠となる証拠データを含むことを特徴とする。
【００２５】
また、本発明の第１７の態様は、第１から第１６のいずれかの態様において、前記第４のメッセージは、合意形成対象のデータ又はそれから計算されるハッシュ値を含むことを特徴とする。
【００２６】
また、本発明の第１８の態様は、第１から第１７のいずれかの態様において、前記データはブロックであり、各ノードは、受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードが有するブロックチェーンに前記ブロックを追加することを特徴とする。
【００２７】
また、本発明の第１９の態様は、コンピュータに、合意形成に参加するＮ個（Ｎは１以上の整数）のノードを有するネットワークにおいてｆ個（ｆは１以上Ｎ／３未満の整数）のビザンチン障害ノードを仮定したときに適した合意形成方法を実行させるためのプログラムであって、前記合意形成方法は、他のノードから、合意形成の対象となるデータを含むメッセージを提案として有効と判定した旨の第１のメッセージを受領するステップと、受領した第１のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を受け入れる旨の第２のメッセージを送信し、所定時間内に、有効な第１のメッセージの数が前記所定の値Ｑに達しない場合、各ノードに、自ノードは前記提案を却下する旨の第３のメッセージを送信するステップと、受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を前記ネットワークにおいて合意されたものとして扱う旨の第４のメッセージを送信するステップとを含むことを特徴とする。
【００２８】
また、本発明の第２０の態様は、合意形成に参加するＮ個（Ｎは４以上の整数）のノードを有するネットワークにおいてｆ個（ｆは１以上Ｎ／３未満の整数）のビザンチン障害ノードを仮定したときに適した合意形成を行うためのノードであって、他のノードから、合意形成の対象となるデータを含むメッセージを提案として有効と判定した旨の第１のメッセージを受領し、受領した第１のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を受け入れる旨の第２のメッセージを送信し、所定時間内に、有効な第１のメッセージの数が前記所定の値Ｑに達しない場合、各ノードに、自ノードは前記提案を却下する旨の第３のメッセージを送信し、受領した第２のメッセージの数が所定の値Ｑに達した場合、各ノードに、自ノードは前記提案を前記ネットワークにおいて合意されたものとして扱う旨の第４のメッセージを送信することを特徴とする。
【発明の効果】
【００２９】
本発明の一態様によれば、後述する提案メッセージ、投票メッセージ、受け入れメッセージ、却下メッセージ、表明メッセージ及びネクストラウンドメッセージのそれぞれを受け取った際の各ノードの振る舞いとノード間での通信につき、特有の構成を採用することによって、合意形成に参加する複数のノードを有するネットワークにおいてのビザンチン障害ノードを仮定したときに適した合意形成方法を提供することができる。
【図面の簡単な説明】
【００３０】
【図１】本発明の一実施形態におけるネットワークを示す図である。
【図２】本発明の一実施形態におけるメッセージのデータ構造の模式図である。
【図３】本発明の一実施形態における各ノードの状態遷移を示す図である。
【発明を実施するための形態】
【００３１】
以下、図面を参照して本発明の実施形態を詳細に説明する。
【００３２】
（第１の実施形態）  
ブロックを含む何らかのデータについての合意形成に参加するノードの総数をＮ（Ｎは１以上の整数）、ビザンチン障害ノードの数をｆと仮定する。本発明は、この仮定の下で、安全性及び活性が得られる合意形成方法を提供する。
【００３３】
図１に、本発明の一実施形態におけるネットワークを示す。ネットワーク１００は、例示としてＮが６であり、各ノード１１０は、通信インターフェースなどの通信部１１１と、プロセッサ、ＣＰＵ等の処理部１１２と、メモリ、ハードディスク等の記憶装置又は記憶媒体を含む記憶部１１３とを備えるコンピュータであり、所定のプログラムを実行することによって、以下で説明する各処理を実現することができ、当該ノード１１０は、１又は複数の装置ないしサーバを含むことがあり、また当該プログラムは、１又は複数のプログラムを含むことがあり、また、コンピュータ読み取り可能な記憶媒体に記録して非一過性のプログラムプロダクトとすることができる。符号１１０で示すノードについてのみ、そのハードウェアの構成を図示しているが、その他のノードについても同様である。
【００３４】
所定のプログラムには、合意アルゴリズムにかかるルールが定められており、記憶部１１３又は各ノード１１０からネットワークを介してアクセス可能な記憶装置又は記憶媒体に記憶しておくことができる。ビザンチン障害ノード１２０以外のノードは、当該ルールに基づいて正常な動作をするものとする。図１の例では、ｆは１である。
【００３５】
ノード間では、メッセージが直接的又は間接的に送受信され、ネットワークを構成する他のノードに合意形成にかかるデータを伝え、また、他のノードからデータを受け取ることができる。図２に模式的に示すように、メッセージ２００には、送信されるブロックなどの何らかのデータ２０１が含まれ、加えて、送信者であるノードによる署名２０２が付加される。ネットワークを構成する各ノードに割り振られ、各ノードを一意に識別する一組の識別子を各ノードは有しており、メッセージに付加される送信者の署名２０２を当該識別子を用いて検証することによって、当該メッセージを送信したノードを確認することができる。具体的には、各ノードに関連づけられた秘密鍵に対応する公開鍵を当該ノードの識別子とし、署名２０２は、送信されるメッセージ２００若しくはデータ２０１又はこれらから計算されるハッシュ値に基づいて秘密鍵により生成したものとすることができる。
【００３６】
まず、各ノードは、待ち（ｗａｉｔ）の状態（ｓｔａｔｅ）にあり（Ｓ３０１）、決定論的な計算によって、いずれかのノードが提案者（ｐｒｏｐｏｓｅｒ）１３０として選ばれる。ここで、「決定論的（ｄｅｔｅｒｍｉｎｉｓｔｉｃ）」とは、いずれのノードにおいても同一の結果が得られることを意味する。本発明では、合意形成の試行の単位を「ラウンド」と呼び、ラウンドの数をｒで表す。たとえば、ｒ  ｍｏｄ  Ｎの計算によって提案者となるノード１３０を決定論的に選ぶことができる。一例として、上述の一組の識別子を順序付け可能な識別子により構成することで、Ｎが６、ｒが１のときは１番目のノードが選ばれ、ｒが２のときは２番目のノードが選ばれる。ｒ  ｍｏｄ  Ｎの代わりにｒ＋ａ  ｍｏｄ  Ｎ（ａは定数）のようにしてもよい。各ノードにおいて上記計算が行われ、各ノードは自ノードの現在のラウンド数ｒを記憶部１１３に記憶しているか、ネットワークを介してアクセス可能であり、参照可能であるため、自ノードが提案者であるか否かを各ノードは判定することが可能である。後述のように、ノードごとに次のラウンドに進むことがあるため、自ノードとは異なるラウンドにいるノードからのメッセージを受信することがある。
【００３７】
提案者１３０は、合意形成対象のデータを含むメッセージをネットワーク１００を構成する各ノードに署名付きで送信して提案する。送信後、提案者は提案済み（ｐｒｏｐｏｓｅｄ）の状態となり、他のノードは、当該メッセージを受信したことに応じて提案済みの状態となる（Ｓ３０２）。提案者も自ノードからの提案を受け取るものとし、より一般的には、何らかのメッセージを送信したノードも自ノードからのメッセージを受け取るものとする。ここで、自ノードからの受け取りには、自ノードに記憶されたメッセージを参照することを含む。提案者は、提案の送信ではなく受け取りに応じて提案済みの状態となるようにしてもよい。また、提案のためのメッセージ及び以下で説明するその他のメッセージには、現在のラウンド数ｒを含む。
【００３８】
提案を受領した各ノードは、当該提案を評価して、それが有効（ｖａｌｉｄ）であるか否かを判定する。有効か否かの判定は、当該提案がそのラウンドで提案者として選択されたものによって送信されたものであるか否かの判定を含み、たとえば、データ形式が用途に応じた所定の形式その他の所定の条件を満たすか否かの判定をさらに含んでもよい。有効と判定したノードは、各ノードにその旨のメッセージを自ノードによる署名付きで送信する。当該メッセージは、有効な提案に対する投票という意味で、投票メッセージ（「第１のメッセージ」に対応）と呼ぶことがある。投票メッセージには、データ２０１として、提案内容又はそれから計算されるハッシュ値が含まれる。以下の処理においても、受け取ったメッセージの有効性の判定を必要に応じて行い、有効なメッセージのみをカウントなどの処理対象とするようにすることができる。提案を受け取ったノードは、当該提案が有効である場合に提案済みの状態に遷移するようにしてもよい。
【００３９】
ビザンチン障害ノード１２０が提案者１３０でないにも関わらず、各ノードに提案をしたような際には、ここで、無効と判定される。また、ビザンチン障害ノード１２０が提案者１３０であり、合意アルゴリズムに定められた所定のルール上はラウンドごとに同一の提案を各ノードにすべきであるにも関わらず、複数の異なる提案を行ってしまったり、一部のノードに提案を送らないといったことが考えられる。このような場合には、有効性の判定が送信者の適否のみであれば、ビザンチン障害ノード１２０は提案者としては有効であるため、各ノードは、それぞれのノードが受け取った提案に対する投票メッセージを送信することとなる。このような状況においても、以下に説明する本実施形態にかかる処理によって、合意形成が可能である。
【００４０】
各ノードは、同一ラウンド内で受信した同じ提案に対する投票メッセージの数が所定の値Ｑに達した場合、各ノードに自ノードは当該提案を受け入れる旨のメッセージを署名付きで送信して、受け入れ（ａｃｃｅｐｔｅｄ）の状態に遷移する（Ｓ３０３−１）。当該メッセージは、受け入れメッセージ（「第２のメッセージ」に対応）と呼ぶことがある。受け入れメッセージは、当該ノードが所定の値Ｑが満たされたと判定した根拠となる証拠データ（ｅｖｉｄｅｎｃｅ  ｄａｔａ）を含むことができる。証拠データは、具体的には、受け取ったＱ個以上の投票メッセージ又はこれに対応するデータとすることができる。また、受け入れメッセージは、提案内容又はそれから計算されるハッシュ値を含むことができる。受け入れの状態にあるノードは、活性を高めるために、定期的又は断続的に受け入れメッセージを送信するのが望ましい。
【００４１】
ここで、所定の値Ｑは、ｆの値が既知の場合、（ｆ＋Ｎ＋１）／２以上の整数とすることが安全性を確保する上で必要であることが分かる。実際には、（ｆ＋Ｎ＋１）／２以上の最小の整数とすればよい。すなわち、安全性を確保するには、複数の異なる提案について所定の値Ｑが満たされないようにすることが必要であり、そのためには、Ｑ個のノードが投票したときには、（Ｎ−ｆ）個の正常なノードの過半数が投票をしていることが求められ、
Ｑ＞（Ｎ−ｆ）／２
が満たされなければならない。投票メッセージを送信したＱ個のノードのうち、ビザンチン障害ノード１２０が最大ｆ個存在し得るため、さらに
Ｑ−ｆ＞（Ｎ−ｆ）／２
が満たされることが求められ、これは
Ｑ＞（Ｎ＋ｆ）／２
となり、（Ｎ＋ｆ＋１）／２以上と表すこともできる。
【００４２】
また、活性を確保するためには、正常なノードの数（Ｎ−ｆ）が所定の値Ｑ以上であることが求められる。したがって、上記Ｑの条件を代入して、ビザンチン障害ノード１２０の数ｆは（Ｎ−１）／３以下となることが要求される。これは、Ｎ／３未満と表現することもできる。ｆの値が（Ｎ−１）／３以下であること以上は不明である場合、所定の値Ｑは、（２Ｎ＋１）／３以上の最小の整数とすればよい。一例として、Ｎが４のとき、Ｑが３となる。
【００４３】
また、各ノードは、所定時間内に、受信した投票メッセージの数が所定の値Ｑに達しない場合、各ノードに自ノードは当該ラウンドにおける提案を却下する旨のメッセージを署名付きで送信して、却下（ｄｉｓｍｉｓｓｅｄ）の状態に遷移する（Ｓ３０３−２）。当該メッセージは、却下メッセージ（「第３のメッセージ」に対応）と呼ぶことがある。上記所定時間は、たとえば、１０秒とすることが考えられる。却下の状態にあるノードは、活性を高めるために、定期的又は断続的に却下メッセージを送信するのが望ましい。
【００４４】
次に、各ノードは、受信した受け入れメッセージの数が所定の数Ｑに達した場合、必要に応じて各メッセージの証拠データの存在を確認した上で、各ノードに自ノードは当該提案をネットワーク１００により合意されたものとして扱う旨のメッセージを送信して、合意形成プロセスを完了（ｃｏｍｐｌｅｔｅ）する（Ｓ３０４）。当該メッセージは、提案を合意されたものとして扱う旨の表明（ｃｏｍｍｉｔ）という意味で、表明メッセージ（「第４のメッセージ」に対応）と呼ぶことがある。表明メッセージは、提案内容又はそれから計算されるハッシュ値を含み、提案内容がブロックの場合、完了を受けて当該ノードが有するブロックチェーンが加えられる。また、表明メッセージは、提案内容又はそれから計算されるハッシュ値を含むことができる。また、表明メッセージは、当該ノードが所定の値Ｑが満たされたと判定した根拠となる証拠データを含むことができる。証拠データは、具体的には、受け取ったＱ個以上の受け入れメッセージ又はこれに対応するデータとすることができる。
【００４５】
図３では、受け入れの状態又は却下の状態から合意形成プロセスが完了に至るように示しているが、条件を満たせば、各ノードが待ちの状態又は提案済みの状態にあっても、合意形成プロセスは完了することができる。表明メッセージを受信したノードは、それを受けて、必要に応じて証拠データの存在を確認した上で、合意形成プロセスを完了する。
【００４６】
また、各ノードは、受信した却下メッセージの数が所定の数Ｑに達した場合、各ノードに次のラウンドに進むためのメッセージを送信して、自ノードも次のラウンドにおける待ちの状態に遷移する。当該メッセージは、ネクストラウンドメッセージ（「第５のメッセージ」に対応）と呼ぶことがある。合意に至らなかったため、次のラウンドに進み、新たな提案者１３０の下で合意形成のプロセスが進められる。ネクストラウンドメッセージは、当該ノードが所定の値Ｑが満たされたと判定した根拠となる証拠データを含むことができる。証拠データは、具体的には、受け取ったＱ個以上の却下メッセージ又はこれに対応するデータとすることができる。また、ネクストラウンドメッセージは、提案内容又はそれから計算されるハッシュ値を含むことができる。
【００４７】
図３では、点線矢印によって、受け入れの状態又は却下の状態から次のラウンドの待ちの状態に遷移するように示しているが、条件を満たせば、各ノードが待ちの状態又は提案済みの状態にあっても、次のラウンドに進むことができる。また、上記条件を満たさなくとも、他のノードから同一のラウンドのネクストラウンドメッセージを受け取った際に、次のラウンドの待ちの状態に遷移するようにしてもよく、さらに各ノードにネクストラウンドメッセージを送信するようにしてもよい。
【００４８】
上述の説明では、提案済みの状態から受け入れの状態に遷移するように記述しているが、待ちの状態からでも、あるいは却下の状態からでも、上記条件を満たせば、遷移を発生させることができる。更に、受信した投票メッセージの数が所定の値Ｑに達しない場合であっても、他のノードから同一のラウンドの受け入れメッセージを受け取った際に、受け入れの状態に遷移するようにしてもよい。自ノードよりも低いラウンドからの受け入れメッセージについては、ビザンチン障害ノード１２０が受け入れメッセージを送るべきラウンドでは送らずに遅延させて送ることが考えられ、これに基づいて他のノードが受け入れてしまうと、複数の提案について合意が形成され、分岐が生じるおそれがある。
【００４９】
なお、「××のみに基づいて」、「××のみに応じて」、「××のみの場合」というように「のみ」との記載がなければ、本明細書においては、付加的な情報も考慮し得ることが想定されていることに留意されたい。
【００５０】
（第２の実施形態）  
本発明の第２の実施形態においては、第１の実施形態にかかる合意形成方法に対し、各ノードの動作を一定の動作に限定する「ロック（ｌｏｃｋ）」の設定を行う。ロックがなされることで、たとえば、一つのノードが複数の投票等を行ってしまうような状況を抑止し、複数の異なる提案について所定の値Ｑの条件が満たされる可能性をゼロまで下げ、安全性を高めることができる。
【００５１】
具体的には、各ノードが受け入れの状態に遷移するとともに、ロックの設定を行うことができる。一例として、ロックされた場合、提案を受け取っても、合意形成対象のデータがロック時におけるものと同一でなければ、当該提案が有効であっても投票を行わない。また、自ノードが提案者として選択された場合、ロック時のラウンドにおける合意形成対象のデータを提案しなければならないようにすることができる。
【００５２】
（第３の実施形態）  
ネットワークの切断、遅延等によって異なるラウンドからのメッセージを受け取ることがある。具体的には、自ノードよりも大きいラウンドにおける受け入れメッセージを受領した場合、それを無視するのではなく、ロックされていればそれを解除して、自ノードのラウンドを当該ラウンドに更新し、更にロックの設定をしてもよい。また、自ノードのラウンドよりは低いが自ノードがロックされた際のラウンドよりは大きいラウンドにおける受け入れメッセージを受領した場合、ロックを解除して、当該受け入れメッセージのラウンドにおける提案内容でロックを設定し、ラウンド数については、自ノードのラウンドのままとすることができる。ロックの解除をこのように可能とすることで、合意形成における活性を高めることができる。ビザンチン障害ノードが根拠なく大きいラウンドの受け入れメッセージを送信することが考えられることから、根拠データの存在の確認が必要に応じて行われる。
【００５３】
また、自ノードよりも大きいラウンドにおけるネクストラウンドメッセージを受領した場合、自ノードのラウンドを当該ラウンドに更新し、当該ラウンドにおいてネクストラウンドメッセージを送信してもよい。
【００５４】
また、自ノードよりも大きいラウンドにおける提案を受領した場合、自ノードのラウンドを当該ラウンドに更新し、当該提案が有効なとき、当該ラウンドにおいて投票メッセージを送信してもよい。より詳細には、ｒが２以上の場合には提案のメッセージには、前のラウンドのネクストラウンドメッセージを含め、提案を受け取ったノードは当該ネクストラウンドメッセージの根拠データの存在を確認した上で自ノードのラウンドを更新するようにしてもよい。あるいは、提案のメッセージを受け取った際に、送信元のノードに前のラウンドのネクストラウンドメッセージの送信を要求するようにしてもよい。
【００５５】
また、自ノードと異なるラウンドから表明メッセージを受け取ることがあり、この際には、ラウンドに関わらず、またロックの有無にかかわらず、当該ラウンドにおける提案ネがネットワーク１００により合意されたものとして扱い、合意形成プロセスを完了することができる。
【符号の説明】
【００５６】
１００  ネットワーク
１１０  ノード
１１１  通信部
１１２  処理部
１１３  記憶部
１２０  ビザンチン障害ノード
１３０  提案者
２００  メッセージ
２０１  データ
２０２  署名
【図１】
2019012415.tif 000003
【図２】
2019012415.tif 000004
【図３】
2019012415.tif 000005