(57)【特許請求の範囲】
【請求項１】
いくつか（Ｎ個）のノードによって維持されるブロックチェーン上で実施されるコンピュータで実施される、ビュー変更プロトコルから退出する方法であって、前記方法は、ビュー変更プロトコル中の、前記Ｎ個のノードのうちのバックアップ・ノードである第１のノードによって実行され、前記方法は、
前記Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得することであって、各第１のメッセージは、（１）前記Ｎ個のノードの間で指定されるプライマリ・ノードを示す前記第２のノードに認識されている整合する現在のビューと、（２）前記第２のノードに認識されている整合する現在の順序番号とを含み、前記現在の順序番号は、前記第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、前記現在の順序番号は、前記第１のノードに認識されている第１の順序番号よりも大きく、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得することと、
前記少なくともＱ個の第１のメッセージを取得したことに応答して、前記ビュー変更プロトコルを終了することと
を含む、方法。
【請求項２】
前記少なくともＱ個の第１のメッセージを取得することは、
前記少なくともＱ個の第２のノードからそれぞれ、前記少なくともＱ個の第２のノードが前記ブロックチェーンに追加する次のブロックに同意することを示す少なくともＱ個のコミット・メッセージを取得することであって、前記Ｑ個のコミット・メッセージは、前記Ｑ個の第１のメッセージをそれぞれ含む、取得すること
を含む、請求項１に記載の方法。
【請求項３】
前記少なくともＱ個の第１のメッセージを取得することは、
前記少なくともＱ個の第２のノードからそれぞれ、前記少なくともＱ個の第２のノードが前記ブロックチェーンに追加する次のブロックに同意することを示す少なくともＱ個のコミット・メッセージを取得することであって、前記Ｑ個の第１のメッセージは、前記Ｑ個のコミット・メッセージにそれぞれ付加される、取得すること
を含む、請求項１に記載の方法。
【請求項４】
前記現在の順序番号は、前記第２のノードによって維持される前記ブロックチェーンの第２のコピーの高さを含み、前記ブロックチェーンの第２のコピーの前記高さは、前記ブロックチェーンの第２のコピー内のブロックの数に基づき、
前記第１の順序番号は、前記第１のノードによって維持される前記ブロックチェーンの第１のコピーの高さを含み、前記ブロックチェーンの第２のコピーの前記高さは、前記ブロックチェーンの第２のコピー内のブロックの数に基づく、
請求項１〜３のいずれかに記載の方法。
【請求項５】
前記現在の順序番号は、前記第２のノードによってコミットされた前記最新のトランザクションの順序番号を含み、
前記第１の順序番号は、前記第１のノードによってコミットされた最新のトランザクションの順序番号を含む、
請求項１〜３のいずれかに記載の方法。
【請求項６】
前記第１のメッセージは、両方とも前記第２のノードに認識されている前記現在のビューおよび前記現在の順序番号を保証するデジタル署名を含む、
請求項１〜５のいずれかに記載の方法。
【請求項７】
前記第１のメッセージは、前記最新のブロックまたは前記最新のトランザクションのダイジェストをさらに含む、
請求項１〜６のいずれかに記載の方法。
【請求項８】
前記ダイジェストは、前記最新のブロックまたは前記最新のトランザクションのハッシュ値を含む、
請求項７に記載の方法。
【請求項９】
前記ダイジェストは、前記第２のノードには認識されているが、前記第１のノードには認識されていない前記最新のブロックのマークル・ルートを含む、
請求項７または８に記載の方法。
【請求項１０】
前記ビュー変更プロトコルを終了することは、
前記第１のノードによって維持される前記ブロックチェーンの第１のコピーを、前記第２のノードによって維持される前記ブロックチェーンの第２のコピーと同期させることと、
前記第１のノードに対して前記整合する現在のビューを使用することによって、前記ビュー変更プロトコルから退出して、通常動作プロトコルに入ることと
を含む、請求項１〜９のいずれかに記載の方法。
【請求項１１】
前記少なくともＱ個の第２のノードに認識されている前記現在の順序番号は（ｎ＋１）であり、
前記第１のノードに認識されている前記第１の順序番号はｎである、
請求項１〜１０のいずれかに記載の方法。
【請求項１２】
前記少なくともＱ個の第２のノードの前記現在のビューはｖであり、
前記第１のノードは、前記ビュー変更プロトコル中の場合、ｖより大きい第１のビューを有する、
請求項１〜１１のいずれかに記載の方法。
【請求項１３】
前記Ｎ個のノードは、前記Ｎ個のノードのうちの１つが前記プライマリ・ノードとして機能し、その他の（Ｎ−１）個のノードがバックアップ・ノードとして機能する、実用的ビザンチン障害耐性（ＰＢＦＴ）ネットワークを形成する、
請求項１〜１２のいずれかに記載の方法。
【請求項１４】
１つまたは複数のプロセッサと、
前記１つまたは複数のプロセッサに結合され、請求項１〜１３のいずれかに記載の方法を実行するための、前記１つまたは複数のプロセッサによって実行可能な命令が記憶される、１つまたは複数のコンピュータ可読メモリと
を備える、ビュー変更システム。
【請求項１５】
請求項１〜１３のいずれかに記載の方法を実行するための複数のモジュールを備える、ビュー変更装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は一般には、ビュー変更を実行するための方法およびデバイスに関し、より詳細には、実用的ビザンチン障害耐性（ＰＢＦＴ：Ｐｒａｃｔｉｃａｌ  Ｂｙｚａｎｔｉｎｅ  Ｆａｕｌｔ  Ｔｏｌｅｒａｎｃｅ）システムにおいてビュー（Ｖｉｅｗ）の変更を終了するための方法およびデバイスに関する。
【背景技術】
【０００２】
実用的ビザンチン障害耐性（ＰＢＦＴ）は、ブロックチェーン・システムなどの分散システムにおいて実装することができる一種のコンセンサス・メカニズムである。ＰＢＦＴコンセンサス・メカニズムによって、分散システムは、システムの特定のノードが故障する（たとえば、不十分なネットワーク接続が原因で、もしくは他の原因で障害が生じる）可能性があろうと、他のピアに誤った情報を伝播する（たとえば、悪意を持って行動する）可能性があろうと、安全性および生存性（ｌｉｖｅｎｅｓｓ）を持って、十分なコンセンサスに到達することが可能になる。そのようなメカニズムの目的は、機能していないノードによる、システムの正しい機能への影響と、システム内の機能しているノード（たとえば、障害のない善意のノード）が到達するコンセンサスへの影響とを軽減することにより、壊滅的なシステム故障を防ぐことである。
【０００３】
ＰＢＦＴコンセンサス・メカニズムは、独立したノード故障と、特定の独立したノードによって伝播される改ざんされたメッセージとがあるという仮定を通じて、ビザンチン障害（たとえば、機能していないノード）を許容する実用的ビザンチン・ステート・マシンの複製を提供することに焦点を当てている。このＰＢＦＴコンセンサス・メカニズムでは、たとえば、ブロックチェーン・システム内の全てのノードはある順序に順序付けられ、あるノードはプライマリ・ノード（別名、リーダーまたはマスター・ノード）となり、その他はバックアップ・ノード（別名、フォロワー・ノード）と呼ばれる。システム内の全てのノードは互いに通信し、目標は、全ての善意のノードがシステムの状態に関する合意／コンセンサスに至ることである。
【０００４】
たとえば、ＰＢＦＴコンセンサス・メカニズムが機能するには、その前提は、ブロックチェーン・システム内の機能していないノードの量が、所与の脆弱性の窓において一斉にシステム内のノード全体の３分の１以上になってはならないというものである。この方法は、たかだかＦ個のノードが同時に機能していないノードである限り、生存性および安全性の両方を効果的に提供する。換言すれば、いくつかの実装形態では、ＰＢＦＴコンセンサス・メカニズムが許容できる機能していないノードの数Ｆは、（Ｎ−１）／３を最も近い整数に切り捨てた値に等しく、ここでＮはシステム内のノードの総数を表す。一部の実装形態では、ＰＢＦＴコンセンサス・メカニズムを実装しているブロックチェーン・システムは、全部で少なくとも３Ｆ＋１個のノードが存在する場合に、最大Ｆ個のビザンチン障害に対処することができる。コンセンサス検証を実行するために、各ノードはプライマリ・ノードのリーダーシップの下で通常動作プロトコルを実行する。プライマリ・ノードが機能していないとあるノードが考えた場合、そのノードはビュー変更プロトコルに入って、プライマリ・ノードの変更を開始することができる。大多数（ｍａｊｏｒｉｔｙ）のノードの合意の下で、新たなプライマリ・ノードが機能していないプライマリ・ノードに置き換わった後、それらのノードは通常動作プロトコルに戻る。
【０００５】
現在の技術では、ノードは従来の手順に従って、すなわち、大多数のノードが同様にビュー変更プロトコルに入り、プライマリ・ノードが機能していないことに合意するまで待機して、ビュー変更プロトコルから退出する。従来のビュー変更プロトコルでは、この条件は、少なくとも２Ｆ＋１個のノードがビュー変更プロトコルに入り、それぞれビュー変更メッセージをマルチキャストする場合、少なくとも２Ｆ＋１個のビュー変更メッセージを取得した新たなプライマリ・ノードが新ビュー・メッセージをマルチキャストして、それらのノードが通常動作に戻るのを支援することである。しかしながら、場合によっては、ネットワーク通信の途絶により、ノードが、プライマリ・ノードが機能していないと誤解し、その他のノードがまだ通常動作中である間にビュー変更プロトコルに入る場合がある。結果として、そのノードはビュー変更プロトコルで立ち往生し、コンセンサス・プロセスから実質的に遮断される。立ち往生しているノードが通常動作に戻るまでの遅延は、いつ本当のプライマリ・ノードの機能停止または誤動作が発生するかによる場合があるので、予測不可能である。そのため、立ち往生しているノードの計算能力は、他のノードがビュー変更に参加するのを待っている間、無駄になる。したがって、ノードがビュー変更プロトコルから退出するのを支援することができる代替メカニズムを提供することが望ましい。
【発明の概要】
【０００６】
本明細書の様々な実施形態は、ビュー変更を実行するためのシステム、方法、および非一時的コンピュータ可読媒体を含むが、これらに限定されない。
【０００７】
一実施形態によれば、いくつか（Ｎ個）のノードによって維持されるブロックチェーン上で実施されるコンピュータ実施ビュー変更方法は、ビュー変更プロトコル中の、Ｎ個のノードのうちの第１のノードによって実行される。この方法は、Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得することであって、各第１のメッセージは、（１）Ｎ個のノードの間で指定されるプライマリ・ノードを示す第２のノードに認識されている整合する現在のビューと、（２）第２のノードに認識されている整合する現在の順序番号とを含み、現在の順序番号は、第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きく、Ｑ（定足数（ｑｕｏｒｕｍ））は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得することと、少なくともＱ個の第１のメッセージを取得したことに応答して、ビュー変更プロトコルを終了することとを含む。
【０００８】
いくつかの実施形態では、少なくともＱ個の第１のメッセージを取得することは、少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第２のノードがブロックチェーンに追加する次のブロックに同意することを示す少なくともＱ個のコミット・メッセージを取得することであって、Ｑ個のコミット・メッセージは、Ｑ個の第１のメッセージをそれぞれ含む、取得することを含む。
【０００９】
他の実施形態では、少なくともＱ個の第１のメッセージを取得することは、少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第２のノードがブロックチェーンに追加する次のブロックに同意することを示す少なくともＱ個のコミット・メッセージを取得することであって、Ｑ個の第１のメッセージは、Ｑ個のコミット・メッセージにそれぞれ付加される、取得することを含む。
【００１０】
さらに他の実施形態では、現在の順序番号は、第２のノードによって維持されるブロックチェーンの第２のコピーの高さを含み、第１の順序番号は、第１のノードによって維持されるブロックチェーンの第１のコピーの高さを含む。
【００１１】
さらに他の実施形態では、現在の順序番号は、第２のノードによってコミットされた最新のトランザクションの順序番号を含み、第１の順序番号は、第１のノードによってコミットされた最新のトランザクションの順序番号を含む。
【００１２】
いくつかの実施形態では、第１のメッセージは、両方とも第２のノードに認識されている現在のビューおよび現在の順序番号を保証するデジタル署名を含む。
【００１３】
他の実施形態では、第１のメッセージは、最新のブロックまたは最新のトランザクションのダイジェストをさらに含む。
【００１４】
さらに他の実施形態では、ダイジェストは、最新のブロックまたは最新のトランザクションのハッシュ値を含む。
【００１５】
さらに他の実施形態では、ダイジェストは、第２のノードには認識されているが、第１のノードには認識されていない最新のブロックのマークル・ルートを含む。
【００１６】
いくつかの実施形態では、ビュー変更プロトコルを終了することは、第１のノードによって維持されるブロックチェーンの第１のコピーを、第２のノードによって維持されるブロックチェーンの第２のコピーと同期させることと、第１のノードに対して整合する現在のビューを使用することによって、ビュー変更プロトコルから退出して、通常動作プロトコルに入ることとを含む。
【００１７】
他の実施形態では、少なくともＱ個の第２のノードに認識されている現在の順序番号は（ｎ＋１）であり、第１のノードに認識されている第１の順序番号はｎである。
【００１８】
さらに他の実施形態では、少なくともＱ個の第２のノードの現在のビューはｖであり、第１のノードは、ビュー変更プロトコル中の場合、ｖより大きい第１のビューを有する。
【００１９】
さらに他の実施形態では、Ｎ個のノードは、Ｎ個のノードのうちの１つがプライマリ・ノードとして機能し、その他の（Ｎ−１）個のノードがバックアップ・ノードとして機能する、実用的ビザンチン障害耐性（ＰＢＦＴ）ネットワークを形成する。
【００２０】
いくつかの実施形態では、ビュー変更システムは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、前述の実施形態のいずれか１つの方法を実行するための、１つまたは複数のプロセッサによって実行可能な命令が記憶される、１つまたは複数のコンピュータ可読メモリとを備える。
【００２１】
他の実施形態では、ビュー変更装置は、前述の実施形態のいずれか１つの方法を実行するための複数のモジュールを備える。
【００２２】
他の実施形態によれば、ビュー変更システムはブロックチェーンを維持するためのものであり、いくつか（Ｎ個）のノードはブロックチェーンを維持し、このシステムは、ビュー変更プロトコル中の、Ｎ個のノードのうちの第１のノードとして機能する。このシステムは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、このシステムに動作を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成される、１つまたは複数の非一時的コンピュータ可読メモリとを備え、これらの動作は、Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得することであって、各第１のメッセージは、（１）Ｎ個のノードの間で指定されるプライマリ・ノードを示す第２のノードに認識されている整合する現在のビューと、（２）第２のノードに認識されている整合する現在の順序番号とを含み、現在の順序番号は、第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きく、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得することと、少なくともＱ個の第１のメッセージを取得したことに応答して、ビュー変更プロトコルを終了することとを含む。
【００２３】
さらに他の実施形態によれば、非一時的コンピュータ可読記憶媒体は、ブロックチェーンを維持するためのものであり、いくつか（Ｎ個）のノードはブロックチェーンを維持し、この記憶媒体は、ビュー変更プロトコル中の、Ｎ個のノードのうちの第１のノードに関連付けられる。この記憶媒体は、１つまたは複数のプロセッサに動作を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成され、これらの動作は、Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得することであって、各第１のメッセージは、（１）Ｎ個のノードの間で指定されるプライマリ・ノードを示す第２のノードに認識されている整合する現在のビューと、（２）第２のノードに認識されている整合する現在の順序番号とを含み、現在の順序番号は、第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きく、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得することと、少なくともＱ個の第１のメッセージを取得したことに応答して、ビュー変更プロトコルを終了することとを含む。
【００２４】
さらに他の実施形態によれば、ビュー変更装置はブロックチェーンを維持するためのものであり、いくつか（Ｎ個）のノードはブロックチェーンを維持し、この装置は、ビュー変更プロトコル中の、Ｎ個のノードのうちの第１のノードとして機能する。この装置は、Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得するための取得モジュールであって、各第１のメッセージは、（１）Ｎ個のノードの間で指定されるプライマリ・ノードを示す第２のノードに認識されている整合する現在のビューと、（２）第２のノードに認識されている整合する現在の順序番号とを含み、現在の順序番号は、第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きく、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得モジュールと、少なくともＱ個の第１のメッセージを取得したことに応答して、ビュー変更プロトコルを終了するための終了モジュールとを備える。
【００２５】
本明細書で開示した実施形態は、１つまたは複数の技術的効果を有する。いくつかの実施形態では、これらの方法およびシステムは、ビュー変更プロトコルに入ったＰＢＦＴコンセンサス・システムのノード（たとえば、第１のノード）が、効率的にビュー変更プロトコルから退出し、通常動作プロトコルを再開できるようにすることができる。他の実施形態では、通常動作プロトコル中の第２のノードは、コミット・メッセージをマルチキャストするときに、第１のメッセージをコミット・メッセージに追加または付加することができ、第１のメッセージは、第２のノードに認識されている現在のビューおよび現在の順序番号を含む。現在のビューは、プライマリ・ノードの第２のノードのビューを示し、現在の順序番号は、第２のノードがコミットした最新のトランザクションを示し、または第２のノードによって維持されるブロックチェーンの最新のブロックに関連するブロックチェーンの高さ（ブロックの高さとも呼ばれる）を示す。さらに他の実施形態では、ビュー変更プロトコルで立ち往生している第１のノードは、第１のメッセージから現在のビューおよび現在の順序番号を取得することができる。定足数Ｑの整合する第１のメッセージを受信すると、第１のノードは、それらを自身のビューおよび順序番号と比較して、ノードの大多数がまだ通常動作中であるか否かを判定することができる。他のノードの大多数がまだ通常動作中である場合、第２のノードは、ビュー変更プロトコルを終了し、通常動作プロトコルを再開することができる。さらに他の実施形態では、第１のメッセージ内の順序番号によって示されるように、大多数のノードが、コンセンサス検証順序における次のトランザクションまたは次のブロックに同意しており、次のトランザクションまたは次のブロックは、まだ第１のノードに認識されていない場合がある。大多数のノードがビュー変更に入らなかったと気付くことにより、第１のノードはスムーズにビュー変更プロトコルを終了することができる。いくつかの実施形態では、大多数のノードが同様にビュー変更に入り、新たなビューに同意してビュー変更プロトコルを終了しなくても、第１のノードはビュー変更を終了することができる。このようにして、通常動作中のノードの数、およびそれらの計算能力の提供を最適化することができる。
【００２６】
本明細書で開示したシステム、方法、および非一時的コンピュータ可読媒体のこれらおよび他の特徴のみならず、関連する構造要素の動作方法および機能、ならびに部品の組み合わせおよび製造の経済性は、添付図面を参照して以下の説明および添付の特許請求の範囲を考察するとより明らかになり、添付図面は全て本明細書の一部を形成し、同様の参照番号は様々な図における対応する部分を示す。しかしながら、図面は例示および説明のみを目的とするものであり、限定を意図したものではないことは明確に理解されたい。
【図面の簡単な説明】
【００２７】
【図１】様々な実施形態によるネットワークを示す図である。
【図２Ａ】ＰＢＦＴの通常動作プロトコルを示す図である。
【図２Ｂ】１つのレプリカが機能していない場合のＰＢＦＴの通常動作プロトコルを示す図である。
【図２Ｃ】ＰＢＦＴの通常動作プロトコルおよびビュー変更プロトコルを示す図である。
【図３Ａ】通常動作プロトコルとビュー変更プロトコルとの間での経路の切り替えのフローチャートである。
【図３Ｂ】様々な実施形態による、通常動作プロトコルとビュー変更プロトコルとの間での経路の切り替えのフローチャートである。
【図４】様々な実施形態によるビュー変更退出ステップのフローチャートである。
【図５Ａ】様々な実施形態によるビュー変更方法のフローチャートである。
【図５Ｂ】様々な実施形態によるビュー変更方法のフローチャートである。
【図６】様々な実施形態によるビュー変更システムのブロック図である。
【図７】本明細書に記載の実施形態のいずれかを実装することができるコンピュータ・システムのブロック図である。
【発明を実施するための形態】
【００２８】
本明細書で開示した実施形態は、限定はしないが、ＰＢＦＴシステムにおいて実装することができるビュー変更システム、方法、および非一時的コンピュータ可読媒体を含む。様々な実施形態において、ビュー変更プロトコルから退出し、通常動作プロトコルを再開する経路が提供される。ビュー変更に入ったノードは、少なくともＱ個のノードがビュー変更に入る必要がある従来のビュー変更プロトコルを経由せずに、通常動作に戻ることができる。Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｎはノードの総数を表し、４以上の整数であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である。ＰＢＦＴと同様に、開示したシステム、方法、および非一時的コンピュータ可読媒体は、他のコンセンサス・プロトコル、たとえば、ＳｅｃｕｒｅＲｉｎｇ、Ｂｙｚａｎｔｉｎｅ  Ｐａｘｏｓ、Ｑ／Ｕ、ＨＱ、Ｚｙｚｚｖｙｖａ、ＡＢｓＴＲＡＣＴｓ、ＲＢＦＴ、Ａｄａｐｔ、Ｔａｎｇａｒｏａ、ＣｈｅａｐＢＦＴ、ＭｉｎＢＦＴ、ＦａｓｔＢＦＴなどに適用することができる。ＰＢＦＴの様々な態様については、Ｍ．Ｃａｓｔｒｏ、Ｂ．Ｌｉｓｋｏｖ、「Ｐｒａｃｔｉｃａｌ  Ｂｙｚａｎｔｉｎｅ  Ｆａｕｌｔ  Ｔｏｌｅｒａｎｃｅ」、Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｔｈｉｒｄ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ、（１９９９年２月）を参照することができ、その全体が本明細書に引用により組み込まれている。
【００２９】
図１に、様々な実施形態によるネットワーク１２０を示す。以下に提示する構成要素は、例示的なものとする。図示のように、ネットワーク１２０は、ネットワーク・システム１１２を含むことができる。ネットワーク・システム１１２は、サーバ、コンピュータ、携帯電話などの１つまたは複数のコンピューティング・デバイスに実装された１つまたは複数のノード（たとえば、ノード０、ノード１、ノード２、ノード３、ノード４、ノードｉなど）を含むことができる。ネットワーク・システム１１２には、ネットワーク１２０の他のデバイスまたはさらなるシステムにアクセスするための適切なソフトウェア（たとえば、コンセンサス・プログラム）および／またはハードウェア（たとえば、有線、無線接続）をインストールすることができる。ノードは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合された１つまたは複数のメモリとを含むことができる。メモリは、非一時的かつコンピュータ可読にすることができ、１つまたは複数のプロセッサに本明細書に記載の動作を実行させるための、１つまたは複数のプロセッサによって実行可能な命令によって構成することができる。この図では、ノードは単一の構成要素として示しているが、これらのノードが単一のデバイスまたは互いに結合された複数のデバイスとして実装できることは理解されよう。一般に、ノードは互いに通信し、ネットワーク・システム１１２の外部の他のデバイスと通信することができてもよい。たとえば、１つまたは複数の有線または無線ネットワーク（たとえば、インターネット）を介して、データを通信することができる。
【００３０】
様々な実施形態において、ネットワーク・システム１１２は、様々なブロックチェーン・ノードを含むブロックチェーン・ネットワーク・システムとして実装することができる。図示のように、ブロックチェーン・ネットワーク・システムは、複数のブロックチェーン・ノード（たとえば、ノード０、ノード１、ノード２、ノード３、ノード４、ノードｉなど）を含むことができる。ブロックチェーン・ノードは、あるブロックチェーン・ノードが他のブロックチェーン・ノードと通信するネットワーク（たとえば、ピア・ツー・ピア・ネットワーク）を形成することができる。図示したブロックチェーン・ノードの順序および数は、単なる例であって、説明を簡単にするためのものである。ブロックチェーン・ノードは、サーバ、コンピュータなどに実装することができる。各ブロックチェーン・ノードは、ＴＣＰ／ＩＰなどの様々なタイプの通信方法によって互いに結合された１つまたは複数の物理的なハードウェア・デバイスまたは仮想デバイスに対応することができる。分類に応じて、ブロックチェーン・ノードは、フル・ノード、Ｇｅｔｈノード、コンセンサス・ノードなどを含むことができる。
【００３１】
様々な実施形態において、ブロックチェーン・ネットワーク・システムは、ノードＡおよびノードＢ（たとえば、軽量ノード）などの他のシステムおよびデバイスとインタラクト（ｉｎｔｅｒａｃｔ）することができる。インタラクションは、たとえば、要求を受信し、要求の実行結果を返すなどの目的の、データの送受信を含むことができる。一例では、ユーザＡはブロックチェーン・ネットワークを介してユーザＢと取引したい場合がある。トランザクションは、ユーザＡの口座の一部の資産をユーザＢの口座に送金することを含む場合がある。ユーザＡおよびユーザＢは、トランザクションのために適切なブロックチェーン・ソフトウェア（たとえば、暗号通貨ウォレットなど）がインストールされたノードＡおよびノードＢのそれぞれのデバイスを使用することができる。ノードＡはノード０との通信を通じてブロックチェーンにアクセスすることができ、ノードＢはノード１との通信を通じてブロックチェーンにアクセスすることができる。たとえば、ノードＡはノード０を介してブロックチェーンにトランザクション要求を提出することができ、ノードＢはノード１を介してブロックチェーンにスマート・コントラクト実行要求を提出することができる。ブロックチェーンから外れて、ノードＡおよびノードＢは、他の通信チャネル（たとえば、ノード０および１を経由しない通常のインターネット通信）を有することができる。
【００３２】
ブロックチェーン・ノードはそれぞれ、メモリを備えるか、またはメモリに結合することができる。いくつかの実施形態では、メモリは、プール・データベースを記憶することができる。プール・データベースは、分散方式で複数のブロックチェーン・ノードがアクセスできるようにすることができる。たとえば、プール・データベースは、ブロックチェーン・ノードのメモリにそれぞれ記憶することができる。プール・データベースは、ユーザによって操作されるノードＡおよびＢなどの１つまたは複数のユーザデバイスによって提出される複数のトランザクションを記憶することができる。
【００３３】
ブロックチェーン・ノードは、コンセンサスを通じて、ブロックチェーンと呼ばれる分散型台帳にトランザクションを記録するネットワーク（たとえば、Ｐ２Ｐネットワーク）を形成する。Ｐ２Ｐネットワークの参加者はノードと呼ばれる場合があり、ノードはブロックチェーンを維持するものである。ブロックチェーンＰ２Ｐネットワークでは、各ノードはコンセンサス検証に参加し、ブロックチェーンの完全な台帳のコピーを記憶する。全てのノードは、ブロックチェーン・コンセンサス方法によりトランザクションのバッチを確認することによって、全てのノードが整合する確認結果を有し、ひいてはブロックチェーンの整合するコピーを有するようにする。
【００３４】
ブロックチェーン・コンセンサス方法の１つは、実用的ビザンチン障害耐性（ＰＢＦＴ）である。ビザンチン障害耐性は、ビザンチン将軍問題が起源である。Ｐ２Ｐネットワーク・システムでは、そのような機能していないノードの数が特定の限度内である限り、システムは適切に機能し続けることができる。そのようなシステムは、ビザンチン障害耐性システムと呼ばれる。ＰＢＦＴは、ビザンチン障害耐性ネットワーク機能の最適化の一例である。ＰＢＦＴは、サーバをコピーし、クライアントのインタラクションをサーバのコピーと同期させることにより、ネットワークにビザンチン・ステート・マシンを提供する。
【００３５】
ＰＢＦＴ動作の中心となるのは、ブロックチェーンに記録された情報の整合するグローバルなビューの維持であり、これにより、分散方式でユーザが互いにインタラクトできるようにするためのバックボーンが形成される。ＰＢＦＴコンセンサス・モデルのセキュリティは、ブロックチェーン・プラットフォームにとって重要である。コンセンサス・モデルの２つの主要な特性は：１）安全性または整合性：全ての善意のノードが同じ有効な出力を生成すること、および、２）生存性：コンセンサスを得た全ての善意のノードは、中間段階で止まることなく最終的に値を生成すること、である。安全で堅牢なＰＢＦＴコンセンサス・プロトコルは、ネットワーク・ノードの故障、ネットワークの分割、メッセージ遅延、順不同のメッセージ配信、メッセージ破損などを含む多種多様なビザンチン行動を許容し、システム内の機能していないノードの数が限られている限り、ノード間でコンセンサスに到達する必要がある。その目的で、ＰＢＦＴモデルは、２つの相互に排他的なプロトコル：通常動作／整合性プロトコルおよびビュー変更プロトコルのいずれか一方の下で動作し、これらは以下でさらに説明する。本明細書では、機能していないということは、障害があるおよび／または悪意があることを意味し、機能しているということは、障害がなく善意であることを意味する。可能性のある障害または悪意がある行為は、メッセージの配信の失敗、メッセージの配信の遅延、順不同のメッセージ配信、ビザンチン障害（プロトコルに違反する恣意的なメッセージを様々なノードに配信する）などを含むことができる。
【００３６】
いくつかの実施形態では、実用的ビザンチン障害耐性（ＰＢＦＴ）システムはＮ個のノードを含むことができ、Ｎ個のノードのうちの１つはプライマリ・ノードとして機能し、Ｎ個のノードのうちのその他はバックアップ・ノードとして機能する。プライマリ・ノードの指定は特定のノードに固定されなくてもよく、その理由は、ビュー変更プロトコルを通じて他のノードが新たなプライマリ・ノードになるように選出することができるためである。たとえば、プライマリ・ノードは剰余演算によって選出することができ、最小のシリアル番号（ビュー番号の剰余）を有する機能しているノードが新たなプライマリ・ノードになる。現在のビューと、ノードの総数Ｎとによって、プライマリ・ノードｉｄ＝（ｖｉｅｗ＋１）ｍｏｄ  Ｎを決定することができる。ＰＢＦＴでは、新たなプライマリ・ノードが選出されるたびにビューが変更される。たとえば、ビュー変更のたびに、ビューはゼロから単調に増加する。すなわち、プライマリ・ノードの変更に伴い、ビューを変更することができる。
【００３７】
いくつかの実施形態では、プライマリ・ノードはビューｖで機能しており、通常動作プロトコルが実行される。通常動作では、プライマリ・ノードおよび／またはバックアップ・ノードは、１つまたは複数のクライアントから未検証のトランザクションに関連する要求を受信する場合がある。たとえば、クライアントとしてのノードＡは、プライマリ・ノードおよび／またはバックアップ・ノードに要求を送信する場合がある。要求は、未検証のトランザクション（たとえば、ブロックチェーンの新たなブロックに追加されるトランザクション）を含むことができる。未検証のトランザクションは、たとえば、ブロックチェーン・ベースの金融取引、スマート・コントラクト展開または実行トランザクションなどを含むことができる。プライマリ・ノードおよびバックアップ・ノードは、トランザクションの何らかの予備検証を実行してもよく、しなくてもよい。要求を受信したバックアップ・ノードは、受信した要求をプライマリ・ノードに転送することができる。プライマリ・ノードにおけるトランザクションが特定のレベルに達するかまたは他の方法でトリガー条件を満たす場合、プライマリ・ノードは１ラウンドのコンセンサス検証を開始し、未検証のトランザクションの検証結果を提案することができる。バックアップ・ノードはコンセンサスに対処し、コンセンサスに到達するための提案を確認することができる。ノードの要件は、それらが決定性であって、同じ状態で開始することである。最終的な結果は、全ての善意のノードがレコードの順序に関するコンセンサスに至り、それを受諾または拒否することである。コンセンサス検証されると、トランザクションは、ブロックチェーンの新たなブロック内にパックされ、ノードによって維持されるローカルのブロックチェーンのコピーに追加することができる。また、要求を元々に送信したクライアント（たとえば、ノードＡ）に通知される。
【００３８】
安全性を持続するために、主なＰＢＦＴ方法は、通常動作プロトコルに関する３つのフェーズ：事前準備、準備、およびコミット・フェーズを含む。図２Ａから図２Ｃを参照すると、ＰＢＦＴシステムの一例は、４つのレプリカ（レプリカとはノードの別名である）：レプリカ０、レプリカ１、レプリカ２、およびレプリカ３を含む。０〜３の番号は、新たなプライマリ・ノードを決定するために使用できるレプリカのシリアル番号である。レプリカ０はプライマリ・ノード０に対応することができ、レプリカ１、２、および３はバックアップ・ノード１、２、および３に対応することができる。レプリカは、たとえば、上記のネットワーク・システム１１２の様々なブロックチェーン・ノードに実装することができる。機能していないノードが存在しない場合の通常動作プロトコルを図２Ａに示し、レプリカ３が機能していないノードである場合の他の通常動作プロトコルを図２Ｂに示す。どちらの状況でも、通常動作プロトコルは、要求フェーズ、事前準備フェーズ、準備フェーズ、コミット・フェーズ、および返答フェーズに分けることができる。
【００３９】
図２Ａおよび図２Ｂを参照すると、通常動作は、クライアントが要求（メッセージ）をプライマリ・ノード（レプリカ０）に提出したときに、要求フェーズにおいて開始し、プライマリ・ノードはその要求の主唱（ａｄｖｏｃａｔｉｎｇ）を担当するものである。要求は、クライアント、要求動作（たとえば、コンセンサス検証されるトランザクション要求）、および要求タイムスタンプの情報を含むことができる。クライアント（クライアント・ノードとも呼ばれる）は、たとえば、上記のノードＡに実装することができる。ノードＡは、軽量ノード（たとえば、携帯電話に実装されたもの）とすることができる。それに加えてまたはその代わりに、クライアントは要求をバックアップ・ノードに送信することができ、バックアップ・ノードは事前準備フェーズの前に要求をプライマリ・ノードに転送する。プライマリ・ノードまたはバックアップ・ノードのいずれが要求を受信するかに関係なく、対応するノードは受信した要求をネットワーク内の他のノードにマルチキャストすることができる。このようにして、プライマリ・ノードが、クライアントによってコンセンサス・ネットワークに提出された保留中の要求を最終的に何らかの方法で取得することができる。
【００４０】
したがって、プライマリ・ノードはリーダーのように機能し、バックアップ・ノードをリードして、要求に関連するトランザクションを検証する。プライマリ・ノードは、そのビュー内での要求の実行の順序付けを担当する。事前準備フェーズにおいて、プライマリ・ノードは取得した要求を検証し、各要求に順序番号を提案することができる。このようにして、各要求に増加する順序番号を割り当てて、並べることができる。加えて、事前準備メッセージは、ブロックの高さを含むことができる。ブロックの高さは、ブロックチェーンの現在の高さに基づくことができる。たとえば、ブロックチェーンが現在１０００個のブロックを有する場合、ブロックの高さは１０００とすることができ、これは１０００個のブロックがブロックチェーンに既に存在していることを示し、または１００１とすることができ、これは要求に関連するトランザクションが、他のノードによってまだ検証されていないブロックチェーンの１００１番目のブロック内にパックされるように提案されることを示す。プライマリ・ノードは、要求を順序番号および／またはブロックの高さと共に転送することができる。たとえば、要求を取得した後、プライマリ・ノードは、順序番号を割り当てることにより、対応するトランザクションを実行する順序に要求を配列し、リストに記憶することができる。プライマリ・ノードは、ＰＢＦＴネットワーク・システム内の全てのバックアップ・ノード（レプリカ１からレプリカ３）に事前準備メッセージを送信することができる。図２Ａに示すように、プライマリ・ノードは、リストを事前準備メッセージ内で、またはそれと共にバックアップ・ノードにマルチキャストすることができる。図２Ｂに示すように、バックアップ・ノード（レプリカ３）が機能しておらず、プライマリ・ノードがそれに気付いていない場合であっても、プライマリ・ノードはなおも事前準備メッセージを送信することができる。各バックアップ・ノードは事前準備メッセージを、それが有効である限り受諾する。事前準備メッセージは、ビュー番号、順序番号、署名、ダイジェスト（ｄ）、その他のメタ・データなどを含むことができ、これによりメッセージの有効性を判定することが可能になる。
【００４１】
準備フェーズにおいて、バックアップ・ノードは、事前準備メッセージを受諾した場合、それに続いて、プライマリ・ノードを含むＰＢＦＴネットワーク・システム内の他のノードに準備メッセージをマルチキャストすることができる。準備メッセージをマルチキャストすることは、送信者ノードがその順序に同意することを示す。各準備メッセージは、有効である限り受信ノードによって受諾される。準備メッセージの有効性も同様に、ビュー番号、順序番号、署名、ダイジェスト（ｄ）、その他のメタ・データなどに基づいて判定することができる。ノードは、プライマリ・ノードからオリジナルの要求を受信し、事前準備を行い（たとえば、事前準備メッセージをマルチキャストする）、事前準備メッセージに合致する少なくとも（Ｑ−１）個の別個の有効かつ整合する準備メッセージを取得した場合に、準備が整う。（Ｑ−１）個の準備メッセージは、マルチキャストした準備メッセージを含むことができる。Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｎはノードの総数を表し、４以上の整数であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である。Ｑ個のノードのＰＢＦＴネットワーク・システムは、最大Ｆ個のビザンチン障害を許容することができる。いくつかの実施形態では、Ｎが少なくとも（３Ｆ＋１）である場合、Ｑは（２Ｆ＋１）である。ここでは、Ｑ個ではなく（Ｑ−１）個の準備メッセージが必要であり、その理由は、（プライマリ・ノード自体は準備メッセージを送信しなくてもよいが）事前準備メッセージをプライマリ・ノードの準備メッセージの同等物として扱うことができるためである。事前準備メッセージをもう１つの準備メッセージとしてカウントする場合、全てのノードのうちの少なくともＱ個が事前準備メッセージを受諾したことを示す少なくともＱ個の別個の有効な準備メッセージが存在することになり、そのうち最大Ｆ個の機能していないノードを許容することができる。このように、事前準備から準備までのフェーズによって、要求がビューｖにおいて実行される場合に、その順序番号で実行されることに、少なくとも（Ｑ−Ｆ）個の機能しているノード（Ｑ個の準備できたノードから最大Ｆ個の機能していないノードを除外したもの）が同意することが保証される。準備フェーズによって、ビュー内の各要求の障害耐性のある整合する順序付けが保証される。
【００４２】
いくつかの実施形態では、バックアップ・ノードは、事前準備メッセージおよび（Ｑ−１）個の準備メッセージを受信した後、順序を検証し、検証結果を、プライマリ・ノードによって事前準備メッセージ内に書き込まれた提案された検証結果と比較することができる。順序を検証するにはいくつかの方法があるであろう。たとえば、提案された検証結果は、ダイジェスト（ｄ）に書き込まれた提案されたマークル・パトリシア・トライ（Ｍｅｒｋｌｅ  Ｐａｔｒｉｃｉａ  Ｔｒｉｅ）のルートを含むことができる。バックアップ・ノードは、要求に関連するトランザクションを順序に従って配列し、マークル・パトリシア・トライのルートを計算して、マークル・パトリシア・トライのルートと比較することができる。この計算は、ブロックチェーン内の既存ブロックのノード・ハッシュなどの特定の既存情報を必要とすることもできる。この比較により、バックアップ・ノードによって計算されるダイジェスト（Ｄ（ｍ））が生成される。ダイジェスト（Ｄ（ｍ））がダイジェスト（ｄ）と整合する場合、検証は成功する。検証されると、バックアップ・ノードは、要求の順序付け（たとえば、要求に関連するトランザクションをブロックチェーンの新たなブロック内にパックする順序）に同意することができる。同様に、バックアップ・ノードは、受信したコミット・メッセージ（コミット・フェーズに関して後述する）が同じダイジェストＤ（ｍ）を含むか否かを検証して、他のノードも要求の順序付けに同意するか否かを判定することができる。準備できたノードがＱ個のコミット・メッセージを取得しており、より低い順序番号を有する要求が全て実行済みである場合、そのノードは要求を実行することができる。
【００４３】
いくつかの実施形態では、事前準備メッセージは、新たなブロックのダイジェスト（ｄ）、または要求の実行に他の方法で関連する情報（たとえば、要求に関連するトランザクション）を含むことができる。ダイジェスト（ｄ）（たとえば、ハッシュ値）は、トランザクションなどのデータにハッシュ・アルゴリズムを適用した数値結果とすることができる。バックアップ・ノードは、トランザクションを実行してダイジェスト（ｄ）を確認することができる。複数の要求の場合、バックアップ・ノードは、順序（すなわち、要求の順序番号）に従って要求を実行して、ダイジェストＤ（ｍ）を取得することができる。Ｄ（ｍ）およびｄが整合する場合、バックアップ・ノードは、バックアップ・ノードがプライマリ・ノードの検証結果に同意することを示すコミット・メッセージ（コミット・フェーズに関して後述する）をマルチキャストする。いくつかの実施形態では、コミット・メッセージは、コミット・メッセージをマルチキャストしたバックアップ・ノードが事前準備メッセージに同意し、別個のノードから（Ｑ−１）個以上の有効かつ整合する準備メッセージを取得したことを示す。特定の順序番号の保留中の要求に関して、準備できたノードがＱ個のコミット・メッセージを取得しており、より低い順序番号を有する要求が全て実行済みである場合、そのノードは要求を実行することができる。
【００４４】
コミット・フェーズでは、ノードが準備できている場合、コミット・メッセージを他のノードにマルチキャストすることができる。ノードは、他のノードからコミット・メッセージを受信することができる。各ノードはコミット・メッセージを有効である限り受諾する。コミット・メッセージは、ビュー番号、順序番号、署名、ダイジェスト、その他のメタ・データなどを含むことができ、これによりメッセージの有効性を判定することが可能になる。ノードが少なくともＱ個の別個の有効かつ整合するコミット・メッセージを取得した場合、これは、定足数のノードがコミットしており（すなわち、少なくとも（Ｑ−Ｆ）個の善意のノードが準備できており）、コンセンサスに到達したことを示す。少なくともＱ個の有効なコミット・メッセージは、マルチキャストしたコミット・メッセージを含むことができる。したがって、準備からコミットまでのフェーズによって、要求が最終的にビューｖにおいてその順序番号で実行されることに、少なくとも（Ｑ−Ｆ）個の機能しているノード（Ｑ個のコミット・メッセージから最大Ｆ個の機能していないノードを除外したもの）が同意することが保証される。ノードは異なるビューでコミットする場合があるので（たとえば、一部のノードが既に新たなビューに入っており、他の一部のノードが前のビューのままである場合）、受信されたコミット・メッセージは、異なるビューで実行されたコミットに対応する場合がある。機能しているノードが各要求の順序番号に同意するので、コミット・フェーズによって、ビュー全体にわたる各要求の障害耐性のある整合する順序付けが保証される。
【００４５】
いくつかの実施形態では、ノードが少なくともＱ個の別個の有効かつ整合するコミット・メッセージを取得した場合、そのノードは対応する要求を実行することができる。たとえば、Ｑ個のコミット・メッセージが取得されると、これは新たなブロックがコンセンサス検証されることを意味する。したがって、ノードは、ローカルに保持しているブロックチェーンのコピー内に新たなブロックをパックすることができる。そうでなければ、バックアップ・ノードは、ビュー変更プロトコルを直接トリガーすることができる。
【００４６】
返答フェーズでは、要求を実行した後、ノードは返答をクライアントに直接送信する。ブロックチェーン内にパックされたトランザクションについて、返答はブロックチェーン内のトランザクションのアドレスを含むことができる。最大Ｆ個の障害が許容されているので、クライアントは、異なるノードからの有効な署名と、同じ要求タイムスタンプおよび同じ実行結果を有する（Ｑ−Ｆ）個の返答を待機した後、結果を受諾する。図２Ａおよび図２Ｂに示すＰＢＦＴネットワーク・システムでは、合計４つのノードがあるので、最大で１つ（Ｎ＝４、Ｑ＝３、およびＦ＝１）の機能していないノードを許容することができる。したがって、図２Ｂにおいて、レプリカ３が機能していなくても、なおもコンセンサスに到達することができる。
【００４７】
生存性を持続するために、プライマリ・ノードが要求をマルチキャストせずに特定の時間が経過した場合、ビュー変更プロトコルにおいてプライマリ・ノードを置き換えることができる。たとえば、バックアップ・ノードはタイマーを保持することができる。バックアップ・ノードは、要求を受信し、タイマーがまだ動作していないときにタイマーを開始する。バックアップ・ノードは、要求を実行するために待機しなくなった（すなわち、要求が実行された）ときにタイマーを停止するが、その時点で１つまたは複数の他の要求を実行するために待機している場合は、タイマーを再開する。タイマーが時間切れになった場合、バックアップ・ノードは、プライマリ・ノードが機能していないと判定することができる。したがって、バックアップ・ノードは、ビュー変更メッセージを他のノードにマルチキャストすることができる。他の例では、バックアップ・ノードは、プライマリ・ノードが機能していないと判定することができる。したがって、バックアップ・ノードは、ビュー変更メッセージをマルチキャストすることができる。他の例では、クライアントはタイマーを使用して、クライアントがプライマリ・ノードに要求を送信してから応答を受信することなく時間が経過しすぎていないかを判定することができる。このタイマーが時間切れになった場合、クライアントはその要求を全てのノードに送信する。ノードが既に要求を認識している場合、再ブロードキャストは無視される。ノードが要求を認識していない場合、タイマーを開始する。ノードのタイマーがタイムアウトすると、ノードは、プライマリ・ノードが機能していないという疑いに基づいて、ビュー変更メッセージを他のバックアップ・ノードにマルチキャストすることにより、ビュー変更処理を開始する。ビュー変更メッセージは、（前の通常動作中の自身の準備メッセージを含むアーカイブ・メッセージの形式で）システム状態を含み、それによって他のノードは送信者ノードが故障していないことを知る。
【００４８】
圧倒的多数の善意のノードは、プライマリ・ノードが機能していないか否かを判定し、それを削除して、順番が次のプライマリ・ノードを代わりにすることができる。ビュー変更は、プライマリ・ノードが故障したと十分なノードが信じたときに行われる。図２Ｃの一部に、ビュー変更プロトコルを示す。図２Ｃを参照すると、ビュー変更フェーズの下で、現在のビューがｖである場合、ノードｐ＝（ｖ＋１）ｍｏｄ  Ｎは、新たなプライマリ・ノードになるためにＱ個の有効なビュー変更メッセージの取得を待機し、ここでｐはレプリカ／ノードのシリアル番号であり、ｖはビュー番号であり、Ｎはレプリカ／ノードの総数である。Ｑ個のビュー変更メッセージは、マルチキャストしたビュー変更メッセージを含むことができる。前のビューはｖであるので、ビュー変更メッセージはそれぞれ新たなビューｖ＋１を含むことができる。新たなプライマリ・ノードｐは、Ｑ個のビュー変更メッセージを取得すると、新ビュー・メッセージをマルチキャストする。このメッセージは、受信した全ての有効なビュー変更メッセージに加え、プライマリ・ノードの故障のためにまだ完了していない場合がある全ての要求のセットも含む。新たなプライマリ・ノードは、最新のチェックポイントを決定し、とりわけ、機能しているノードが最新の状態に追いつくようにすることができ、これは、新たなビューにおける以前の要求（たとえば、準備済みかつコミット済みであるが未実行の要求）を再コミットすることを含むことができる。ビュー変更が行われている間、新たな要求は受諾されない。ノードは、Ｑ個のビュー変更メッセージを含む有効な新ビュー・メッセージを受信した後、ビューｖ＋１に入り、未完了の要求のセットを処理する。その後、通常動作プロトコルが進行し、ノードは最新の安定したチェックポイントの順序番号と、準備メッセージ内の最大の番号との間の要求をやり直すが、要求を再実行しないようにする。通常動作プロトコルとビュー変更プロトコルとの間のノードのステータスの対応する切り替えを図３Ａに示す。図３Ａに示すように、たとえば、バックアップ・ノードのタイムアウトにより、通常動作プロトコルから（たとえば、通常動作プロトコルの任意のフェーズ中に）、ビュー変更プロトコルへの（たとえば、ビュー変更フェーズを開始する）切り替えをトリガーすることができる。ビュー変更プロトコルを実行した後、有効な新ビュー・メッセージを取得すると、バックアップ・ノードはビュー変更プロトコルから退出し、通常動作プロトコルを再開して保留中の要求を実行することができる。有効な新メッセージは、異なるノードからのＱ個のビュー変更メッセージを含むことができる。
【００４９】
図３Ｂに示すように、様々な実施形態によれば、ノードがビュー変更プロトコルから通常動作プロトコルに切り替えるための代替経路を提供することができる。いくつかの実施形態では、ビュー変更プロトコル中のノードは、Ｑ個の第１のメッセージを取得して、ビュー変更プロトコルを終了することができる。第１のメッセージは、現在のビュー、現在の順序番号、および／またはダイジェストを含むことができる。第１のメッセージに基づいて、ビュー変更プロトコル中のノードは、他のノードの大多数が通常動作中であると判定して、ビュー変更から退出することができる。さらなる詳細については、図４から図６を参照して以下で説明する。
【００５０】
図４に、本明細書の様々な実施形態によるビュー変更退出ステップ４１０のフローチャートを示す。ステップ４１０は、図１のシステム１００の１つまたは複数の構成要素（たとえば、上記のノード０、ノード１、ノード２、．．．、もしくはノードｉまたは同様のデバイス、あるいはそれらのノードのいずれかと、ノードＡなどの１つまたは複数のさらなるデバイスとの組み合わせ）によって実施することができる。ステップ４１０は、１つまたは複数のブロックチェーン・ノード（たとえば、プライマリ・ノード、バックアップ・ノード）によって実施することができる。プライマリ・ノードおよびバックアップ・ノードは、ＰＢＦＴモデルで定義されたものとすることができる。ステップ４１０は、様々なハードウェア・マシンおよび／またはソフトウェアを含むビュー変更システムまたはデバイス（たとえば、コンピュータ、サーバ）によって実施することができる。たとえば、ビュー変更退出システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、そのシステムまたはデバイス（たとえば、プロセッサ）にステップ４１０を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成される、１つまたは複数の非一時的コンピュータ可読記憶媒体（たとえば、１つまたは複数のメモリ）とを備えることができる。以下に提示する動作は、例示的なものとする。実装形態に応じて、これらの動作は、様々な順序でまたは並行して実行される追加のステップ、より少ないステップ、または代替のステップを含むことができる。
【００５１】
ステップ４１１において、第１のノード（たとえば、バックアップ・ノード）は、ビュー変更プロトコルに入ることができる。ステップ４１２において、第１のノードは、ビュー変更メッセージをマルチキャストすることができる。ビュー変更に入るために、第１のノードは通常動作プロトコルを終了し、上記のビュー変更プロトコルのビュー変更フェーズに入る。一実施形態では、第１のノードは、ビュー変更メッセージをマルチキャストすることにより、ビュー変更プロトコルに入ることができる。たとえば、第１のノードは、ビュー変更メッセージをプライマリ・ノードおよび他のバックアップ・ノードにマルチキャストすることができる。第１のノードは、プライマリ・ノードが障害があるかまたは他の原因で機能していないと判定し、ビュー変更プロトコルに従ってビュー変更メッセージのマルチキャストを開始することができる。
【００５２】
プライマリ・ノードおよび（Ｎ−１）個のバックアップ・ノードは、ＰＢＦＴコンセンサス・システムを形成することができる。ここで、プライマリ・ノードは、本当に機能していない場合と、そうでない場合とがある。プライマリ・ノードが本当に機能していない場合、大多数のバックアップ・ノード（たとえば、Ｑ個のバックアップ・ノード）は、それぞれビュー変更プロトコルに入り、それぞれビュー変更メッセージをマルチキャストすることができる。第１のノードは、Ｑ個のビュー変更メッセージを取得した場合、プライマリ・ノードが機能しておらず、新たなプライマリ・ノードが選出される必要があるというコンセンサスに大多数のノードが到達したと判定することができる。ビュー変更プロトコルの残りの部分を続けることができる。しかしながら、プライマリ・ノードがまだ機能している場合、第１のノードは以下のステップに従ってビュー変更プロトコルを終了することができる。そのような場合、第１のノードは、前述の事前準備メッセージ、準備メッセージ、またはコミット・メッセージの送信および／または受信の遅延を引き起こす、誤解、不安定な接続、および／またはその他の理由によって、ビュー変更に入った場合がある。
【００５３】
ステップ４１３において、第２のノードは、それぞれ第１のメッセージをマルチキャストすることができる。いくつかの実施形態では、第２のノードは、まだ通常動作プロトコル中であり、上述の手順を実行している場合がある（たとえば、事前準備メッセージの受信中、準備メッセージのマルチキャスト中、準備メッセージの受信中、コミット・メッセージのマルチキャスト、コミット・メッセージの受信中など）。通常動作プロトコルにおいて、第２のノードはそれぞれ、第１のメッセージを第１のノードに送信するか、または第１のメッセージをマルチキャストして、第１のノードが第１のメッセージを取得できるようすることができる。いくつかの実施形態では、第１のメッセージは、コミット・フェーズでマルチキャストするコミット・メッセージに含めることができる。他の実施形態では、第１のメッセージは、コミット・フェーズでマルチキャストするコミット・メッセージに付加することができる。さらに他の実施形態では、第１のメッセージは、たとえばコミット・メッセージをマルチキャストした後に、独立して送信またはマルチキャストすることができる。
【００５４】
一実施形態では、第１のメッセージは、両方とも第２のノードに認識されている現在のビューおよび現在の順序番号を含むことができる。現在のビューは、いずれのノードが、第２のノードにプライマリ・ノードとして認識されているかを示すことができる。現在の順序番号は、（１）コミット・フェーズにおいて第２のノードによってコミットされた最新の要求（たとえば、トランザクション要求）の順序番号、または（２）コミット・フェーズにおいて第２のノードによってコミットされた最新のブロックを示すブロックの高さ、を示すことができる。ブロックの高さは、ブロックチェーン内のブロックの数に基づくことができる。たとえば、あるブロックの高さは、そのブロックと創始（ｇｅｎｅｓｉｓ）ブロックとの間のチェーン内のブロック数とすることができる。ブロックチェーンの最初のブロックは、ブロックの高さ０を有することができ、次のブロックはブロックの高さ１を有することができ、などとすることができる。この例はブロックの高さを表す方法を限定することを意図したものではなく、ブロックの高さは、ブロックチェーンにおけるブロックのシリアル番号を示す限り、他のタイプの表現を有することができる。任意選択により、第１のメッセージは、最新の要求または最新のブロックのダイジェストを含むこともできる。
【００５５】
ステップ４１４において、第１のノードは、第２のノードからそれぞれ第１のメッセージを取得することができる。Ｑ個以上の整合する第１のメッセージを取得したことに応答して、第１のノードはビュー変更プロトコルを終了して、通常動作プロトコルに入ることができる。Ｑ個以上の第１のメッセージは、少なくともＱ個のノードが整合する「ビュー」および「順序番号」に同意したことを意味する。「ビュー」および「順序番号」が整合することは、ノードの大多数が、要求またはブロックに関する１つまたは複数のトランザクションのコンセンサス検証に成功したために、通常動作プロトコルで通常通りに機能していることを示す。第１のノードが、整合するビューおよび順序番号を有するＱ個の第１のメッセージを取得しなかった場合、第１のノードはビュー変更プロトコルのままでいることができる。
【００５６】
いくつかの実施形態では、Ｑ個以上の第２のノードに認識されている現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きい（たとえば、１だけ大きい）。これは、ノードの大多数が、第１のノードによって見逃された、要求またはブロックの１ラウンドのコンセンサス検証を完了していることを示す。したがって、少なくともＱ個の第１のメッセージを受信した第１のノードは、整合する第１のメッセージを通じて、ノードの大多数がまだ通常動作中であることを知ることができる。
【００５７】
いくつかの実施形態では、第１のノードは、少なくとも現在のビューに基づいて通常動作に入ることができる。たとえば、ビュー変更から退出すると、第１のノードは、現在のビューを自身のビューとして使用して、通常動作プロトコルに入ることができる。第１のノードは、最新のブロックの情報（たとえば、ダイジェスト）を組み込むことにより、ブロックチェーンの自身のコピーをブロックチェーンの最新のコピーと同期させることもできる。したがって、第１のノードは、正しいビューと、ブロックチェーンの更新されたコピーとを使用して、通常動作プロトコルを再開することができる。さらに、第１のノードがビュー変更に入ってから通常動作を再開するのにかかる時間は予測することができる。新たなブロックが追加されるとブロックチェーンの高さが増加するので、第１のノードがビュー変更に入り、新たなブロックのコンセンサス検証を見逃してから、１つの新たなブロックがブロックチェーンに追加されるまでに、第１のノードは自身の誤解に気付くことができる。したがって、通常動作を再開するのにかかる時間は、１ラウンドのコンセンサス検証を完了するための時間よりも短くすることができる。
【００５８】
したがって、ビュー変更に入ったノードは、代替経路を介してビュー変更プロトコルを効率的に終了し、他の通常動作しているノードに再参加することができる。この経路は、たとえば、誤解、不安定な接続、および／またはその他の理由により、ビュー変更に入ったノードに役立つことができる。この経路は、プライマリ・ノードを変更して通常動作を再開するためにＱ個のノードがビュー変更に同意する必要がある従来のビュー変更プロトコルを迂回する。したがって、通常動作の最大数のノードを確保することにより、ネットワーク・リソース全体をより効率的に利用することができる。
【００５９】
図５Ａに、本明細書の様々な実施形態によるビュー変更方法５１０のフローチャートを示す。方法５１０は、図１のシステム１００の１つまたは複数の構成要素（たとえば、上記のノード０、ノード１、ノード２、．．．、もしくはノードｉまたは同様のデバイス、あるいはそれらのノードのいずれかと、ノードＡなどの１つまたは複数のさらなるデバイスとの組み合わせ）によって実施することができる。方法５１０は、１つまたは複数のブロックチェーン・ノード（たとえば、ＰＢＦＴシステムのバックアップ・ノード）によって実施することができる。プライマリ・ノードおよびバックアップ・ノードは、ＰＢＦＴモデルで定義されたものとすることができる。方法５１０は、様々なハードウェア・マシンおよび／またはソフトウェアを含むビュー変更システムまたはデバイス（たとえば、コンピュータ、サーバ）によって実施することができる。たとえば、ビュー変更システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、そのシステムまたはデバイス（たとえば、プロセッサ）に方法５１０を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成される、１つまたは複数の非一時的コンピュータ可読記憶媒体（たとえば、１つまたは複数のメモリ）とを備えることができる。以下に提示する方法５１０の動作は、例示的なものとする。実装形態に応じて、方法５１０は、様々な順序でまたは並行して実行される追加のステップ、より少ないステップ、または代替のステップを含むことができる。方法５１０のさらなる詳細については、図１から図４および上記の関連する説明を参照することができる。方法５１０は、第１のノードによって実行することができる。
【００６０】
様々な実施形態において、方法５１０は、いくつか（Ｎ個）のノード（たとえば、ＰＢＦＴコンセンサス・システムのノード）によって維持されるブロックチェーン上で実施されるコンピュータ実施ビュー変更方法とすることができる。一実施形態では、Ｎ個のノードは、Ｎ個のノードのうちの１つがプライマリ・ノードとして機能し、その他の（Ｎ−１）個のノードがバックアップ・ノードとして機能する、実用的ビザンチン障害耐性（ＰＢＦＴ）ネットワークを形成する。方法５１０は、ビュー変更プロトコル中の、Ｎ個のノードのうちの第１のノード（たとえば、バックアップ・ノード）によって実行することができる。
【００６１】
いくつかの実施形態では、ブロック５１１の前に、第１のノードはビュー変更に入っている場合がある。ビュー変更に入ると、第１のノードは、ビュー変更メッセージを他のノードにマルチキャストすることができる。たとえば、第１のノードはバックアップ・ノードとすることができ、ビュー変更メッセージをプライマリ・ノードおよび他のバックアップ・ノードにマルチキャストすることができる。プライマリ・ノードおよびバックアップ・ノードは、ＰＢＦＴコンセンサス・システムを形成することができる。ビュー変更メッセージは、第１のノードが自身の通常動作プロトコルから退出し、ビュー変更プロトコルに入っていることを示す。第１のノードが他のノードから（Ｑ−１）個の同様のビュー変更メッセージを受信しない場合（したがって、自身のビュー変更メッセージを含む合計Ｑ個の整合するビュー変更メッセージを取得しない場合）、従来のビュー変更プロトコルの閾値は満たされない。それにもかかわらず、以下のステップにより、第１のノードはビュー変更プロトコルを終了し、通常動作プロトコルに入ることが可能になる。
【００６２】
ブロック５１１は、Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得することであって、各第１のメッセージは、（１）Ｎ個のノードの間で指定されるプライマリ・ノードを示す第２のノードに認識されている整合する現在のビューと、（２）第２のノードに認識されている整合する現在の順序番号とを含み、現在の順序番号は、第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きく（たとえば、１だけ大きく）、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得することを含む。Ｎは４以上の任意の整数とすることができる。いくつかの実施形態では、Ｎが少なくとも（３Ｆ＋１）である場合、Ｑは（２Ｆ＋１）である。最新のトランザクションに関連する現在の順序番号は、たとえば、対応する第２のノードによってコミットされた１つまたは複数の最新のトランザクションの順序番号を含むことができる。最新のブロックに関連する現在の順序番号は、たとえば、対応する第２のノードによって維持されるブロックチェーンのコピーの高さを含むことができる。前述のように、ブロックチェーンの高さは、ブロックチェーン内のブロックの数に依存し、最新のブロックの追加に伴って増加することができる。一実施形態では、第１のノードがビュー変更を終了するために、少なくともＱ個の第１のメッセージは、整合する現在のビューおよび整合する現在の順序番号を含むことができる。ブロック５１２は、少なくともＱ個の第１のメッセージを取得したことに応答して、ビュー変更プロトコルを終了することを含む。
【００６３】
いくつかの実施形態では、「トランザクション」という用語は、ブロックチェーン・システムによって実施され、ブロックチェーンに記録することができる。トランザクションは、たとえば、金融トランザクション、ブロックチェーン契約を展開するまたは呼び出すためのブロックチェーン契約トランザクション、ブロックチェーンの状態（たとえば、ワールド・ステート）を更新するトランザクションなどを含むことができる。トランザクションは金銭の交換を含む必要はない。
【００６４】
いくつかの実施形態では、少なくともＱ個の第１のメッセージを取得することは、少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第２のノードがブロックチェーンに追加する次のブロックに同意することを示す少なくともＱ個のコミット・メッセージを取得することであって、Ｑ個のコミット・メッセージは、Ｑ個の第１のメッセージをそれぞれ含む、取得することを含む。たとえば、コミット・メッセージは、現在のビューおよび現在の順序番号を含むことができる。
【００６５】
他の実施形態では、少なくともＱ個の第１のメッセージを取得することは、少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第２のノードがブロックチェーンに追加する次のブロックに同意することを示す少なくともＱ個のコミット・メッセージを取得することであって、Ｑ個の第１のメッセージは、Ｑ個のコミット・メッセージにそれぞれ付加される、取得することを含む。たとえば、第１のメッセージは、第２のノードによってコミット・メッセージと共に送信またはマルチキャストすることができる。
【００６６】
様々な実施形態において、少なくともＱ個の第２のノードの現在のビューはｖであり、第１のノードは、ビュー変更プロトコル中の場合、ｖより大きい第１のビューを有する。たとえば、第１のノードがビュー変更に入る前に、第１および第２のノードは全てビューｖを有する場合があり、しかしその後、第１のノードは、第１のノードが機能していないと疑い、ビューｖ＋１のビュー変更に入ったが、第２のノードはビューｖのままである。
【００６７】
いくつかの実施形態では、現在の順序番号は、第２のノードによって維持されるブロックチェーンの第２のコピーの高さ（ブロックの高さとも呼ばれる）を含み、第１の順序番号は、第１のノードによって維持されるブロックチェーンの第１のコピーの高さを含む。一実施形態では、少なくともＱ個の第２のノードに認識されている現在の順序番号は（ｎ＋１）であり、第１のノードに認識されている第１の順序番号はｎである。たとえば、第１のノードがビュー変更に入る前に、第１および第２のノードは全て、ビューｖにおいてブロックの高さが９９の（すなわち、ブロックチェーン内に１００個のブロックがある）ブロックチェーンから開始している場合がある。第１のノードがコミット・フェーズ（たとえば、コミット・メッセージをマルチキャストするもの）に入る前にビュー変更プロトコルに入って、コンセンサス検証から抜けた後、第２のノードは、１０１番目のブロックに関するコンセンサスに到達して、ブロックの高さを１００に増加させている。ビュー変更プロトコルで立ち往生している第１のノードに認識されていない１０１番目のブロックは、現在の順序番号（１００）と第１の順序番号（９９）との差を生じさせる場合がある。
【００６８】
他の実施形態では、現在の順序番号は、第２のノードによってコミットされた最新のトランザクションの順序番号を含み、第１の順序番号は、第１のノードによってコミットされた最新のトランザクションの順序番号を含む。一実施形態では、少なくともＱ個の第２のノードに認識されている現在の順序番号は（ｎ＋１）であり、第１のノードに認識されている第１の順序番号はｎである。たとえば、第１のノードがビュー変更に入る前に、第１および第２のノードは全て、コンセンサス検証される８０個の要求（たとえば、トランザクション要求）から開始している場合がある。要求には、増加する順序番号を割り当てることができる。ビューｖにおいて、第１および第２のノードは、５０個の要求をコンセンサス検証している場合がある。第１のノードがコミット・フェーズ（たとえば、コミット・メッセージをマルチキャストするもの）に入る前にビュー変更プロトコルに入って、コンセンサス検証から抜けた後、第２のノードは、５１番目の要求に関するコンセンサスに到達して、次の保留中の要求の順序番号を５２に増加させている。コンセンサス検証された５１番目の要求は、ビュー変更プロトコルで立ち往生している第１のノードには認識されておらず、現在の順序番号（５１）と第１の順序番号（５０）との差を生じさせる場合がある。
【００６９】
いくつかの実施形態では、第１のメッセージは、最新のブロックまたは最新のトランザクションのダイジェストをさらに含む。ダイジェスト（たとえば、ハッシュ値）は、トランザクションなどのデータにハッシュ・アルゴリズムを適用した数値結果とすることができる。一実施形態では、ダイジェストは、最新のブロックまたは最新のトランザクションのハッシュ値を含む。一例では、ダイジェストは、第２のノードにはコミットされているが、第１のノードにはコミットされていない最新のトランザクションのトランザクション・ハッシュを含む。他の例では、ダイジェストは、第２のノードにはコミットされているが第１のノードにはコミットされていない複数の最新のトランザクションの複数のトランザクション・ハッシュを含む。他の例では、ダイジェストは、第２のノードには認識されているが第１のノードには認識されていない最新のブロックのマークル・ルートを含む。他の例では、ダイジェストは、第２のノードには認識されているが第１のノードには認識されていない複数の最新のブロックの複数のマークル・ルートを含む。
【００７０】
いくつかの実施形態では、「ビュー」、「順序番号」、および／または「ダイジェスト」は、１つまたは複数のデジタル署名（または略して、署名）として第１のメッセージに含めることができる。第１のメッセージは、両方とも第２のノードに認識されている現在のビューおよび現在の順序番号を保証するデジタル署名を含む。「署名」は、対応するメッセージを送信したエンティティからの是認（ｅｎｄｏｒｓｅｍｅｎｔ）を示す。「署名」という用語は、あらゆる形態の承認を示すものとすることができる。一実施形態では、「ビュー」「順序番号」および／または「ダイジェスト」をまず一方向ハッシュ関数に入力し、その出力ハッシュ値を対応するノードの秘密鍵で暗号化して、デジタル署名を取得することができる。暗号化は様々な方法で、たとえば、公開−秘密鍵暗号化（非対称暗号とも呼ばれる）、デジタル署名アルゴリズム（ＤＳＡ：Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）、たとえば、楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ：Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ）などによって実現することができる。たとえば、ＲＳＡなどの公開鍵アルゴリズムを使用して、数学的にリンクされた２つの鍵：１つの秘密鍵および１つの公開鍵を生成することができる。公開鍵暗号が、２つの相互に認証する暗号鍵に依存するので、デジタル署名は機能する。デジタル署名を生成したノードは、自身の秘密鍵を使用して、「ビュー」、「順序番号」、および／または「ダイジェスト」を暗号化することができ、そのデータを復号する唯一の方法は、署名者ノードの公開鍵を使用することである。したがって、デジタル署名は、対応するノードに認識されている「ビュー」、「順序番号」、および／または「ダイジェスト」を表すことができる。
【００７１】
いくつかの実施形態では、ビュー変更プロトコルを終了することは、第１のノードによって維持されるブロックチェーンの第１のコピーを、第２のノードによって維持されるブロックチェーンの第２のコピーと同期させることと、第１のノードに対して整合する現在のビューを使用することによって、ビュー変更プロトコルから退出して、通常動作プロトコルに入ることとを含む。したがって、第２のノードがビューｖにあり、第１のノードがビュー（ｖ＋１）で立ち往生していた場合、第１のノードはビュー変更プロトコルを終了し、ビューｖで通常動作プロトコルに入ることができる。
【００７２】
図５Ｂに、本明細書の様々な実施形態によるビュー変更方法５２０のフローチャートを示す。方法５２０は、図１のシステム１００の１つまたは複数の構成要素（たとえば、上記のノード０、ノード１、ノード２、．．．、もしくはノードｉまたは同様のデバイス、あるいはそれらのノードのいずれかと、ノードＡなどの１つまたは複数のさらなるデバイスとの組み合わせ）によって実施することができる。方法５２０は、１つまたは複数のブロックチェーン・ノード（たとえば、ＰＢＦＴシステムのプライマリ・ノードまたはバックアップ・ノード）によって実施することができる。プライマリ・ノードおよびバックアップ・ノードは、ＰＢＦＴモデルで定義されたものとすることができる。方法５２０は、様々なハードウェア・マシンおよび／またはソフトウェアを含むビュー変更システムまたはデバイス（たとえば、コンピュータ、サーバ）によって実施することができる。たとえば、ビュー変更システムまたはデバイスは、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、そのシステムまたはデバイス（たとえば、プロセッサ）に方法５２０を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成される、１つまたは複数の非一時的コンピュータ可読記憶媒体（たとえば、１つまたは複数のメモリ）とを備えることができる。以下に提示する方法５２０の動作は、例示的なものとする。実装形態に応じて、方法５２０は、様々な順序でまたは並行して実行される追加のステップ、より少ないステップ、または代替のステップを含むことができる。方法５２０のさらなる詳細については、図１から図４および上記の関連する説明を参照することができる。方法５２０は、第２のノードによって実行することができる。第２のノードがプライマリ・ノードである場合、第２のノードはステップ５２１ａ、５２２ａ、５２３、５２４、５２５、および５２６を実行することができる。第２のノードがバックアップ・ノードである場合、第２のノードはステップ５２１ｂ、５２２ｂ、５２３、５２４、５２５、および５２６を実行することができる。
【００７３】
ブロック５２１ａは、第２のノード（たとえば、プライマリ・ノード）により、１つまたは複数の要求（たとえば、トランザクション要求）を取得することを含む。要求は、コンセンサス検証されるブロックチェーン・トランザクション（スマート・コントラクトの有無によらない）を含むことができる。一例では、要求は、コンセンサス検証され、ブロックチェーンに追加されるトランザクションに対応することができる。コンセンサス検証は、１ラウンドの通常動作プロトコルの実行中に実行することができる。あるいは、要求は他の動作に対応することができる。いくつかの実施形態では、プライマリ・ノードは、クライアント（たとえば、軽量ノード）から、またはクライアントから要求を取得し、要求をプライマリ・ノードに転送したバックアップ・ノードから要求を取得することができる。
【００７４】
ブロック５２２ａは、事前準備メッセージおよび要求をバックアップ・ノードにマルチキャストすることを含む。いくつかの実施形態では、複数の要求を取得した後、第２のノードは、事前準備メッセージおよび要求を各バックアップ・ノードにマルチキャストすることができる。事前準備メッセージは、要求の順序（たとえば、要求に関連するトランザクションの順序）を含むことができる。順序は、各要求の順序番号、および／またはブロックチェーンに追加する次のブロックの順序番号を含むことができる。
【００７５】
ブロック５２１ｂは、第２のノード（たとえば、バックアップ・ノード）により、事前準備メッセージおよび１つまたは複数の要求を取得することを含む。たとえば、事前準備メッセージおよび要求は、バックアップ・ノードによってプライマリ・ノードから取得することができる。同様に、バックアップ・ノードは、事前準備メッセージおよび要求を、それらの要求を実行する順序と共に取得することができる。
【００７６】
ブロック５２２ｂは、第２のノードが事前準備メッセージを受諾した場合に、準備メッセージをマルチキャストすることを含む。マルチキャストはブロードキャストを意味する場合がある。たとえば、準備メッセージは、バックアップ・ノードによってプライマリ・ノードおよび他のバックアップ・ノードにマルチキャストすることができる。
【００７７】
ブロック５２３は、（Ｑ−１）個以上の準備メッセージを取得することを含む。いくつかの実施形態では、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値であって、Ｎ個のノードのコンセンサス・システムを機能させ続けるために、Ｎ個のノード間で許容された機能していないノードの最大数を表す。（Ｑ−１）個以上の準備メッセージを取得することは、コミット・フェーズに入る前に満たすべき条件とすることができる。（Ｑ−１）個以上の準備メッセージは、対応するノード自身がマルチキャストした準備メッセージを含むことができる。
【００７８】
ブロック５２４は、（１）第２のノードに認識されているプライマリ・ノードを示す現在のビューと、（２）第２のノードに認識されている現在の順序番号と、を含むコミット・メッセージを他のノードにマルチキャストすることを含む。いくつかの実施形態では、マルチキャストされるコミット・メッセージは、現在のビューおよび現在の順序番号を暗号化した１つまたは複数のデジタル署名を含む。
【００７９】
いくつかの実施形態では、コミット・メッセージは、要求に関連する１つまたは複数のトランザクションのダイジェストをさらに含む。たとえば、ダイジェストは、最新のコミットされたトランザクションのトランザクション・ハッシュ、またはブロックチェーンの最新のブロックのマークル・トライ・ルートを含むことができる。
【００８０】
いくつかの実施形態では、第２のノードはビュー変更に入っておらず、第２のノードに認識されている現在の順序番号は、ビュー変更に入った第１のノードに認識されている第１の順序番号よりも（たとえば、１だけ）大きい。
【００８１】
いくつかの実施形態では、最大Ｆ個のノードが機能していなくてもよい。それにもかかわらず、ＰＢＦＴシステムは最大Ｆ個の機能していないノードを許容するので、説明した方法およびコンセンサス検証は適切に実行することができる。
【００８２】
ブロック５２５は、少なくともＱ個のコミット・メッセージを取得することを含む。Ｑ個のコミット・メッセージは、対応するノード自身がマルチキャストしたコミット・メッセージを含むことができる。
【００８３】
ブロック５２６は、１つまたは複数の要求を実行することを含む。たとえば、１つまたは複数の要求をコンセンサス検証し、それに対応してブロックチェーンのローカル・コピーに追加することができる。結果として、十分なノード（たとえば、Ｑ個のノード）が対応するトランザクションを検証した場合、そのトランザクションはブロックチェーン内にパックされる。
【００８４】
図６に、様々な実施形態によるビュー変更システム６１０のブロック図を示す。ビュー変更システム６１０（たとえば、コンピュータ・システム）は、上記のノード０、ノード１、ノード２、．．．、もしくはノードｉまたは同様のデバイス、あるいはそれらのノードのいずれかと、さらなるデバイス（たとえば、ノードＡ）との組み合わせの実装形態の一例とすることができる。方法５１０は、ビュー変更システム６１０によって実施することができる。ビュー変更システム６１０は、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、そのシステムまたはデバイス（たとえば、プロセッサ）に方法５１０を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成される、１つまたは複数の非一時的コンピュータ可読記憶媒体（たとえば、１つまたは複数のメモリ）とを備えることができる。ビュー変更システム６１０は、命令（たとえば、ソフトウェア命令）に対応する様々なユニット／モジュールを備えることができる。
【００８５】
いくつかの実施形態では、ビュー変更システム６１０は、ビュー変更装置と呼ばれる場合がある。ビュー変更装置は、ブロックチェーンを維持するためのものとすることができ、いくつか（Ｎ個）のノードがブロックチェーンを維持し、Ｎ個のノードのうちの１つはプライマリ・ノードとして機能し、その他の（Ｎ−１）個のノードはバックアップ・ノードとして機能し、コンセンサス装置は、ビュー変更プロトコル中の、Ｎ個のノードのうちの第１のノードとして機能する。コンセンサス装置は、１つまたは複数のプロセッサと、１つまたは複数のプロセッサに結合され、その装置に動作を実行させるための、１つまたは複数のプロセッサにより実行可能な命令によって構成される、１つまたは複数の非一時的コンピュータ可読メモリとを備えることができる。コンセンサス装置は、命令（たとえば、ソフトウェア命令）に対応する様々なユニット／モジュールを備えることができる。コンセンサス装置は、Ｎ個のノードのうちの少なくともＱ個の第２のノードからそれぞれ、少なくともＱ個の第１のメッセージを取得するための取得モジュール６１１であって、各第１のメッセージは、（１）Ｎ個のノードの間で指定されるプライマリ・ノードを示す第２のノードに認識されている整合する現在のビューと、（２）第２のノードに認識されている整合する現在の順序番号とを含み、現在の順序番号は、第２のノードによってコミットされた最新のブロックまたは最新のトランザクションに関連し、現在の順序番号は、第１のノードに認識されている第１の順序番号よりも大きく、Ｑ（定足数）は（Ｎ＋Ｆ＋１）／２を最も近い整数に切り上げた値であり、Ｆは（Ｎ−１）／３を最も近い整数に切り捨てた値である、取得モジュール６１１と、少なくともＱ個の第１のメッセージを取得したことに応答して、ビュー変更プロトコルを終了するための終了モジュール６１２とを備えることができる。
【００８６】
本明細書に記載の技術は、１つまたは複数の専用コンピューティング・デバイスによって実装される。専用コンピューティング・デバイスは、これらの技術を実装するためのハード・ワイヤードおよび／またはプログラム・ロジックを組み込んだ、デスクトップ・コンピュータ・システム、サーバ・コンピュータ・システム、ポータブル・コンピュータ・システム、ハンドヘルド・デバイス、ネットワーキング・デバイス、または他の任意のデバイスもしくはデバイスの組み合わせとすることができる。専用コンピューティング・デバイスは、パーソナル・コンピュータ、ラップトップ、携帯電話、カメラ付き携帯電話、スマート・フォン、携帯情報端末、メディア・プレーヤー、ナビゲーション・デバイス、電子メール・デバイス、ゲーム・コンソール、タブレット・コンピュータ、ウェアラブル・デバイス、またはそれらの組み合わせとして実装することができる。コンピューティング・デバイスは、通常、オペレーティング・システム・ソフトウェアによって制御および調整される。従来のオペレーティング・システムは、実行すべきコンピュータ・プロセスを管理およびスケジュールし、メモリ管理を実行し、ファイル・システム、ネットワーキング、Ｉ／Ｏサービスを提供し、とりわけグラフィカル・ユーザ・インターフェース（「ＧＵＩ」）などのユーザ・インターフェース機能を提供する。本明細書に記載の様々なシステム、装置、記憶媒体、モジュール、およびユニットは、専用コンピューティング・デバイス、あるいは１つまたは複数の専用コンピューティング・デバイスの１つまたは複数のコンピューティング・チップに実装することができる。いくつかの実施形態では、本明細書に記載の命令は、専用コンピューティング・デバイス上の仮想マシンに実装することができる。命令は、実行されると、専用コンピューティング・デバイスに、本明細書に記載の様々な方法を実行させることができる。仮想マシンは、ソフトウェア、ハードウェア、またはそれらの組み合わせを含むことができる。たとえば、仮想マシンは、イーサリアムでのスマート・コントラクトのためのランタイム環境を提供するイーサリアム仮想マシン（ＥＶＭ：Ｅｔｈｅｒｅｕｍ  Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ）ソフトウェアを含むことができる。
【００８７】
図７は、本明細書に記載の実施形態のいずれかを実装することができるコンピュータ・システム７００を示すブロック図である。システム７００は、本明細書に記載の方法のいずれか（たとえば、ビュー変更方法５１０、ビュー変更方法５２０）を実行することができる。システム７００は、本明細書に記載のシステムのいずれか（たとえば、ビュー変更システム６１０）に実装することができる。システム７００は、本明細書に記載のノードのいずれかに実装し、ブロックチェーン契約を実施するための対応するステップを実行するように構成することができる。コンピュータ・システム７００は、情報を伝達するためのバス７０２または他の通信メカニズム、情報を処理するための、バス７０２で結合された１つまたは複数のハードウェア・プロセッサ７０４を含む。ハードウェア・プロセッサ７０４は、たとえば、１つまたは複数の汎用マイクロプロセッサとすることができる。
【００８８】
コンピュータ・システム７００は、情報と、プロセッサ７０４によって実行可能な命令とを記憶するための、バス７０２に結合されたメイン・メモリ７０６、たとえば、ランダム・アクセス・メモリ（ＲＡＭ）、キャッシュ、および／または他の動的記憶デバイスなどをさらに含む。メイン・メモリ７０６は、プロセッサ７０４によって実行可能な命令の実行中に一時変数または他の中間情報を記憶するために使用することもできる。そのような命令は、プロセッサ７０４がアクセスできる記憶媒体に記憶されると、コンピュータ・システム７００を、それらの命令で指定された動作を実行するようにカスタマイズされた専用マシンにする。コンピュータ・システム７００は、プロセッサ７０４用の静的情報および命令を記憶するための、バス７０２に結合された読み取り専用メモリ（ＲＯＭ）７０８または他の静的記憶デバイスをさらに含む。情報および命令を記憶するためのストレージ・デバイス７１０、たとえば、磁気ディスク、光ディスク、またはＵＳＢサム・ドライブ（フラッシュ・ドライブ）などが設けられ、バス７０２に結合される。
【００８９】
コンピュータ・システム７００は、コンピュータ・システムと組んで、コンピュータ・システム７００を専用マシンにするかまたはそうなるようにプログラムする、カスタマイズされたハード・ワイヤード・ロジック、１つまたは複数のＡＳＩＣまたはＦＰＧＡ、ファームウェアならびに／あるいはプログラム・ロジックを使用して、本明細書に記載の技術を実装することができる。一実施形態によれば、本明細書に記載の動作、方法、および処理は、プロセッサ７０４が、メイン・メモリ７０６に含まれる１つまたは複数の命令の１つまたは複数のシーケンスを実行したことに応答して、コンピュータ・システム７００によって実行される。そのような命令は、ストレージ・デバイス７１０などの他の記憶媒体からメイン・メモリ７０６に読み込むことができる。メイン・メモリ７０６に含まれる命令のシーケンスを実行することにより、プロセッサ７０４は本明細書に記載の処理ステップを実行する。代替的実施形態では、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて、ハード・ワイヤード回路を使用することができる。
【００９０】
メイン・メモリ７０６、ＲＯＭ７０８、および／またはストレージ７１０は、非一時的記憶媒体を含むことができる。「非一時的媒体」という用語および類似の用語は、本明細書で使用する場合、マシンを特定の方法で動作させるデータおよび／または命令を記憶する媒体を指し、その媒体は一時的な信号を除外する。そのような非一時的媒体は、不揮発性媒体および／または揮発性媒体を含むことができる。不揮発性媒体には、たとえば、ストレージ・デバイス７１０などの光ディスクまたは磁気ディスクが含まれる。揮発性媒体には、メイン・メモリ７０６などの動的メモリが含まれる。非一時的媒体の一般的な形式には、たとえば、フロッピー（登録商標）・ディスク、フレキシブル・ディスク、ハード・ディスク、ソリッド・ステート・ドライブ、磁気テープ、またはその他の任意の磁気データ記憶媒体、ＣＤ−ＲＯＭ、その他の任意の光学データ記憶媒体、穴のパターンを有する任意の物理媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、フラッシュＥＰＲＯＭ、ＮＶＲＡＭ、その他の任意のメモリチップまたはカートリッジ、ならびにそれらのネットワーク接続バージョンが含まれる。
【００９１】
コンピュータ・システム７００は、バス７０２に結合されたネットワーク・インターフェース７１８をさらに含む。ネットワーク・インターフェース７１８は、１つまたは複数のローカル・ネットワークに接続された１つまたは複数のネットワーク・リンクに結合する双方向データ通信を提供する。たとえば、ネットワーク・インターフェース７１８は、サービス総合デジタル網（ＩＳＤＮ：ｉｎｔｅｇｒａｔｅｄ  ｓｅｒｖｉｃｅｓ  ｄｉｇｉｔａｌ  ｎｅｔｗｏｒｋ）カード、ケーブル・モデム、衛星モデム、または対応するタイプの電話回線へのデータ通信接続を提供するモデムとすることができる。他の例として、ネットワーク・インターフェース７１８は、互換性のあるＬＡＮへのデータ通信接続を提供するローカル・エリア・ネットワーク（ＬＡＮ）カード（またはＷＡＮと通信するためのＷＡＮコンポーネント）とすることができる。無線リンクを実装することもできる。任意のそのような実装形態では、ネットワーク・インターフェース７１８は、様々なタイプの情報を表すデジタル・データ・ストリームを運ぶ電気信号、電磁信号、または光信号を送受信する。
【００９２】
コンピュータ・システム７００は、ネットワーク、ネットワーク・リンク、およびネットワーク・インターフェース７１８を介して、メッセージを送信し、プログラム・コードを含むデータを受信することができる。インターネットの例では、サーバは、インターネット、ＩＳＰ、ローカル・ネットワーク、およびネットワーク・インターフェース７１８を介して、アプリケーション・プログラムの要求されたコードを送信してもよい。
【００９３】
受信されたコードは、受信されたときにプロセッサ７０４によって実行され、および／または後で実行するためにストレージ・デバイス７１０もしくはその他の不揮発性記憶装置に記憶することができる。
【００９４】
前のセクションで説明した処理、方法、およびアルゴリズムのそれぞれは、１つまたは複数のコンピュータ・システム、あるいはコンピュータ・ハードウェアを備えるコンピュータ・プロセッサによって実行されるコード・モジュールに具現化し、それによって完全にまたは部分的に自動化することができる。処理およびアルゴリズムは、特定用途向け回路に部分的または全体的に実装することができる。
【００９５】
上記の様々な特徴および処理は、互いに独立して使用することができ、または様々な方法で組み合わせることができる。可能な全ての組み合わせおよび部分的組み合わせは、本明細書の範囲内に入るものとする。加えて、特定の方法または処理ブロックは、実装形態によっては省略される場合がある。本明細書に記載の方法および処理も、任意の特定の順序に限定されるものではなく、それに関連するブロックまたは状態は、適切な他の順序で実行することができる。たとえば、説明したブロックまたは状態は、具体的に開示した順序以外の順序で実行することができ、あるいは複数のブロックまたは状態を単一のブロックまたは状態に組み合わせることができる。ブロックまたは状態の例は、直列に、並列に、または他の何らかの態様で実行することができる。開示した実施形態に対して、ブロックまたは状態を追加または削除することができる。本明細書に記載のシステムおよび構成要素の例は、記載とは異なるように構成することができる。たとえば、開示した実施形態と比較して、要素を追加、削除、または再配置することができる。
【００９６】
本明細書に記載の方法の様々な動作は、関連する動作を実行するように（たとえば、ソフトウェアで）一時的に構成されるまたは永続的に構成される１つまたは複数のプロセッサによって少なくとも部分的に実行することができる。一時的に構成されるか永続的に構成されるかにかかわらず、そのようなプロセッサは、本明細書に記載の１つまたは複数の動作または機能を実行するように動作するプロセッサ実装エンジンを構成することができる。
【００９７】
同様に、本明細書に記載の方法は、ハードウェアの一例である１つまたは複数の特定のプロセッサを使用して、少なくとも部分的にプロセッサで実装することができる。たとえば、方法の動作の少なくとも一部は、１つまたは複数のプロセッサまたはプロセッサ実装エンジンによって実行することができる。そのうえ、１つまたは複数のプロセッサは、「クラウド・コンピューティング」環境で、または「ソフトウェア・アズ・ア・サービス」（ＳａａＳ）として、関連する動作の実行をサポートするように動作することもできる。たとえば、動作の少なくとも一部は、（プロセッサを含むマシンの例としての）コンピュータのグループによって実行することができ、これらの動作はネットワーク（たとえば、インターネット）と、１つまたは複数の適切なインターフェース（たとえば、アプリケーション・プログラム・インターフェース（ＡＰＩ））とを介してアクセス可能である。
【００９８】
特定の動作の実行は、単一のマシン内にあるプロセッサだけでなく、いくつかのマシンに配備されたプロセッサの間で分散させることができる。いくつかの実施形態では、プロセッサまたはプロセッサ実装エンジンは、単一の地理的位置（たとえば、家庭環境、オフィス環境、またはサーバ・ファーム内）に配置することができる。他の実施形態では、プロセッサまたはプロセッサ実装エンジンは、いくつかの地理的位置にわたって分散させることができる。
【００９９】
本明細書全体を通して、複数のインスタンスが、単一のインスタンスとして記述した構成要素、動作、または構造を実装することができる。１つまたは複数の方法の個々の動作は別個の動作として図示および説明しているが、個々の動作のうちの１つまたは複数は同時に実行することができ、動作が図示した順序で実行される必要はない。構成において個別の構成要素として提示した構造および機能は、組み合わせられた構造または構成要素として実装することができる。同様に、単一の構成要素として提示した構造および機能は、個別の構成要素として実装することができる。これらおよび他の変形、修正、追加、および改良は、本明細書の主題の範囲内に入る。さらに、本明細書で使用する関連語（ｒｅｌａｔｅｄ  ｔｅｒｍｓ）（「第１の」、「第２の」、「第３の」など）は、いかなる順序、高さ、または重要性を示すものではなく、ある要素と他の要素とを区別するために使用する。さらに、「１つの（ａ）」、「１つの（ａｎ）」、および「複数の（ｐｌｕｒａｌｉｔｙ）」という語は、本明細書において数量の限定を示すものではなく、言及した項目のうちの少なくとも１つの存在を示すものである。
【０１００】
特定の実施形態を参照して本主題の概要を説明したが、本明細書の実施形態のより広い範囲から逸脱することなく、これらの実施形態に様々な修正および変更を加えることができる。詳細な説明は限定的な意味で解釈されるべきではなく、様々な実施形態の範囲は、添付の特許請求の範囲、ならびにそのような特許請求の範囲が権利を有する均等物の全範囲によってのみ定義される。
【図１】
0006882527.tif 000002
【図２Ａ】
0006882527.tif 000003
【図２Ｂ】
0006882527.tif 000004
【図２Ｃ】
0006882527.tif 000005
【図３Ａ】
0006882527.tif 000006
【図３Ｂ】
0006882527.tif 000007
【図４】
0006882527.tif 000008
【図５Ａ】
0006882527.tif 000009
【図５Ｂ】
0006882527.tif 000010
【図６】
0006882527.tif 000011
【図７】
0006882527.tif 000012