(57)【要約】  本発明は、クライアントが１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含む複数n個のサーバに対してデータをビザンチン障害耐性複製する方法であって、f個のサーバは任意に故障する場合があり、n個のサーバは全てトラステッド計算実体（TCE）を有し、  a)前処理手順を実行し、  b)要求手順を実行し、  c)準備手順を実行し、  d)コミット手順を実行する各ステップを含む方法に関する。【選択図】図２
2019536108.tif 000002
【特許請求の範囲】
【請求項１】
複数n個のサーバに対してデータのビザンチン障害耐性複製を行う方法であって、前記複数n個のサーバは１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含み、f個のサーバは任意に故障する場合があり、n個の全てのサーバはトラステッド計算実体（TCE）を有し、前記方法は前記PNのTCEにより実行される前処理手順を含み、前記前処理手順は
実行される動作を要求する要求メッセージに割り当てられる一意で単調かつ連続したカウンター（UMSC）についてランダムな秘密値を計算し、
前記ランダムな秘密値及び前記UMSCについてコミットメントを計算し、
前記ランダムな秘密値を複数のシェアに分割し、
各シェアのサーバ別の認証付き暗号を、復号が指定された前記各サーバによってのみ実行できるように計算し、後の手順中前記要求メッセージを検証するために前記サーバ別の複数のシェアが用いられ、
計算された前記サーバ別の複数のシェア及び計算された前記コミットメントを前記各サーバに提供する
各ステップを含む、方法。
【請求項２】
前記PNは特定の動作を要求する要求メッセージを受信し、
前記PNは少なくとも前記要求メッセージの内容と一意の識別子（UI）とを含む準備メッセージを計算し、前記UIは前記PNのTCEにより計算され前記要求メッセージの暗号署名及び前記UMSCに基づくものであり、
前記PNは前記準備メッセージを前記BNに提供する、請求項1に記載の方法。 
【請求項３】
viii.前記BNが前記BN別のシェアを復号し復号された前記シェアを前記PNに提供し、
ix.前記PNがいくつかのシェアを集め、
x.前記PNが集められた前記シェア及び／又は前記PNのシェアに基づいて前記秘密値を再構築し、
xi.前記PNが再構築された前記秘密を用いて前記前処理手順中に計算された前記コミットメントを開けることにより再構築された前記秘密を検証し、前記前記PNは再構築された前記秘密が検証されたときに前記要求を実行してもよく、
xii.開けられた前記コミットメントを前記BNに伝達し、開けられた前記コミットメントはブロードキャストティングにより伝達されてもよく、
xiii.前記BNのそれぞれが受信され伝達され開けられた前記コミットメントを前記前処理段階中に受信した前記コミットメントと比較する
各ステップのうちの少なくとも１つを更に含む、請求項1に記載の方法。
【請求項４】
ステップii)の前に、前記BNのそれぞれが前記各BNの前記TCEのそれぞれにより前記UIをチェックすることにより前記準備メッセージの妥当性を確認するステップi)が実行され、
ステップvii)の後、前記BNが前記比較の肯定的な結果に基づいて前記要求メッセージの要求を実行するステップviii)が実行される、請求項2又は3に記載の方法。 
【請求項５】
集められたシェアの数が複数n個のサーバの数より少ない場合、集められた各シェアの完全性が前記秘密値を再構築する前に前記PNによりチェックされ、
前記シェアの数はサーバの数と等しくてもよい、請求項1〜4のいずれかに記載の方法。
【請求項６】
認証付き暗号に対して、各BNの公開鍵が用いられる、又は前記PNと前記BNのそれぞれとの間のペアの対称暗号が用いられる、請求項1〜5のいずれかに記載の方法。
【請求項７】
能動的BNが前記PNにより検出され、
前記方法の少なくとも１つのステップを実行するために、決定された前記能動的BNだけが用いられ、
前記能動的BNはノード群を含み前記PNで根を張ったスパニングツリーの形にまとめられてもよく、
通信は前記ツリー内の中間ノード群によりシェア群を集約する能動的BNの前記スパニングツリーに沿って実行されてもよい、請求項1〜6のいずれかに記載の方法。
【請求項８】
前記PNは全てのサーバの中から選択され、
前記PNに障害があると判断された場合、新しいPNが能動的BNの中から選択され、
PNは、前記要求メッセージを提供した後ある一定時間の経過後に応答メッセージを受信しないことにより障害があると判断されてもよい、請求項1〜7のいずれかに記載の方法。
【請求項９】
前記新しいPNは
a)BNが、PNの応答を待つための前記一定時間の経過後、全ての他のBNにビュー変更メッセージを送信することによりビュー変更を要求し、
b)距離パラメータに従って新しいPNを能動的であり前記古いPNに最も近いBNとして選び、
c)前記新しいPNが履歴メッセージを計算し、該履歴メッセージは最新のローカルカウンター値の情報並びに前記新しいPNと前記古いPNとの間及び前記新しいPNと他のBNとの間で行われる通信についての要求履歴情報を含み、
d)前記新しいPNが前記履歴メッセージを全ての他のBNに送信し、
e)前記BNのそれぞれが受信された前記要求履歴情報を検証した後ビュー変更メッセージを計算し、
f)受信された履歴メッセージの前記要求履歴情報を検証した後、計算された前記ビュー変更メッセージを全ての他のBNに提供し、
g)BNが、検証された要求履歴を含むf個の一致するビュー変更メッセージ群を受信次第、検証された前記履歴を処理し、
h)前記新しいPNが、f個の一致するビュー変更メッセージ群を受信次第、新しいPNが確立されていることを示すビュー変更メッセージ群を前記f個のBNに提供する
各ステップにより選択される、請求項8に記載の方法。
【請求項１０】
障害のあるBNは
a)BNが、メッセージの送信及び受信の少なくともいずれかが発生次第、直接接続された各BNと関連するタイマーを起動し、
b)直接接続されたBNから、直接接続された該BNのタイマーの期限前に有効なシェアを受信しなかった場合、直接接続された前記BNの故障の可能性を示す疑いメッセージを少なくとも前記PNに提供し、
c)前記PNが、少なくとも１つの疑いメッセージを受信次第、前記障害の可能性があるBNを特定し特定された前記障害のあるBNの代替BNを選択し、
d)特定された前記障害のあるBNがその他のBNに無視されるように前記代替BNについての情報を前記他のBNに提供する
各ステップにより特定される、請求項1〜9のいずれかに記載の方法。
【請求項１１】
直接接続された前記BNは前記BNの子ノード群であり、
前記疑いメッセージは前記PNの親ノードにも提供され、
疑いメッセージは前記ツリーに沿って前記PNに提供される、請求項7及び10に記載の方法。
【請求項１２】
PNであるある特定のサーバ及びBNである他のサーバ群を決定する現在のビューを示すためにビュー番号が前記メッセージ群に含められる、請求項1〜11のいずれかに記載の方法。
【請求項１３】
再構築された前記秘密が有効であると検証され次第、前記PNは前記要求を実行し、
実行された前記要求の結果は増加したカウンター値とともに前記BNに伝達される、請求項1〜12のいずれかに記載の方法。
【請求項１４】
複数n個のサーバに対してデータのビザンチン障害耐性複製を行うシステムであって、前記複数n個のサーバは１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含み、f個のサーバは任意に故障する場合があり、n個の全てのサーバはトラステッド計算実体（TCE）を有し、前記PNのTCEは
実行される動作を要求する要求メッセージに割り当てられる一意で単調かつ連続したカウンター（UMSC）についてランダムな秘密値を計算し、
前記ランダムな秘密値及び前記UMSCについてコミットメントを計算し、
前記ランダムな秘密値を複数のシェアに分割し、
各シェアのサーバ別の認証付き暗号を、復号が指定された前記各サーバによってのみ実行できるように計算し、後の手順中前記要求メッセージを検証するために前記サーバ別の各シェアが用いられ、
計算された前記サーバ別の各シェア及び計算された前記コミットメントを前記各サーバに提供する
各ステップを実行する、システム。
【請求項１５】
コンピュータに複数n個のサーバに対してデータのビザンチン障害耐性複製を行う方法を実行させるプログラムを記憶する非一時的コンピュータ可読媒体であって、前記複数n個のサーバは１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含み、f個のサーバは任意に故障する場合があり、n個の全てのサーバはトラステッド計算実体（TCE）を有し、前記方法は前記PNのTCEにより実行される前処理手順を含み、前記前処理手順は
実行される動作を要求する要求メッセージに割り当てられる一意で単調かつ連続したカウンター（UMSC）についてランダムな秘密値を計算し、
前記ランダムな秘密値及び前記UMSCについてコミットメントを計算し、
前記ランダムな秘密値を複数のシェアに分割し、
各シェアのサーバ別の認証付き暗号を、復号が指定された前記各サーバによってのみ実行できるように計算し、後の手順中前記要求メッセージを検証するために前記サーバ別の各シェアが用いられ、
計算された前記サーバ別の各シェア及び前記計算されたコミットメントを前記各サーバに提供する
各ステップを含む、非一時的コンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クライアントが１つのプライマリノード（primary node: PN）及びn-1個のバックアップノード（backup nodes: BN）を含む複数n個のサーバに対してデータをビザンチン障害耐性複製する方法であって、f個のサーバは任意に故障する場合があり複数n個のサーバは全てトラステッド計算実体（trusted computing entity: TCE）を有する方法に関する。
【０００２】
本発明は更に、クライアントが１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含む複数n個のサーバに対してデータをビザンチン障害耐性複製するシステムであって、f個のサーバは任意に故障する場合があり複数n個のサーバは全てトラステッド計算実体（trusted computing entity: TCE）を有するシステムに関する。
【０００３】
本発明は更に、クライアントが１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含む複数n個のサーバに対してデータをビザンチン障害耐性複製する方法をコンピュータに実行させるプログラムを記憶する非一時的コンピュータ可読媒体であって、f個のサーバは任意に故障する場合があり複数n個のサーバは全てトラステッド計算実体（TCE）を有する非一時的コンピュータ可読媒体に関する。
【背景技術】
【０００４】
例えば、非特許文献L. Lamport, R. Shostak, and M. Pease, “The byzantine generals problem,” ACM Trans. Program. Lang. Syst., vol. 4, no. 3, pp. 382-401, Jul. 1982に開示されているように、障害プロセスの任意の挙動を捕捉するためにいわゆる「ビザンチン障害」が導入された。例えば、敵対者は、システムの残り部分に誤ったやり方で挙動させるために損なわれたプロセスの挙動をコントロールすることができる。非同期性は時間特性についての前提を持たない、すなわち、処理速度及び伝送遅延についての前提を持たない。敵対者が十分にネットワークをコントロールしている場合この（非）前提は現実的である：攻撃者は処理や通信に対しDoS攻撃を仕掛けることにより一部のタイミング特性を頻繁に損なうことができる。例えば、攻撃者はある期間、処理の通信を遅延させてシステムの適時性についての前提の一部を無効にする場合がある。
【０００５】
このシステムモデル−ビザンチン障害と非同期性−は不可能性結果につながり、これは単一の処理がクラッシュする可能性がある場合（非特許文献T. C. Group, “Tpm main, part 1 design principles. specification version 1.2, revision 103.” 2007に記載されるように、しばしば“フィッシャー・リンチ・パターソン”（Fischer-Lynch-Paterson: FLP）結果と呼ばれる）、非同期システムではコンセンサスは決定論的に解決できないことを示す。不可能であるのは、クラッシュした処理を単純に遅い処理又は遅いネットワークリンクにより接続された処理から区別することが不可能だからである。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ビットコインなどの暗号通貨の広範なデプロイとともに、それらのサポート技術の１つであるブロックチェーンがますます普及する。ブロックチェーンは、暗号通貨取引のための公開台帳となる分散型コンセンサスプロトコルである。そのようなコンセンサスプロトコルの問題点の１つは、それらが確率論的な整合性保証だけを提供するということである。
【０００７】
強力な整合性保証を提供する分散型コンセンサスシステムを構築するために、金融機関は、n個のサーバのうちのf個が任意の（「ビザンチンの」）やり方で不正な挙動又は誤作動しても、n個のサーバが単一の機械として共同で動作できるようにする従来のビザンチン障害耐性（Byzantine fault tolerant: BFT）プロトコルの研究を始めている。しかしながら、実務者たちは通常２つの理由でそのようなBFTプロトコルをデプロイすることを躊躇する。第１の理由は、例えば、http://doi.acm.org/10.1145/1294261.1294280でオンラインで閲覧可能な非特許文献B.-G.Chun, P.Maniatis, S.Shenker, and J.Kubiatowicz, “Attested append only memory: Making adversaries stick to their word,” in Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, ser. SOSP ’07. New York, NY, USA: ACM, 2007, pp. 189-204に開示されているように、BFTプロトコルはそのネットワーク通信が各要求についてO(n2)個ものメッセージを含む集中型であるためサーバ数の面でスケーラビリティが低いことである。第２の理由は、例えば、http://dl.acm.org/citation.cfm?id=296806.296824でオンラインで閲覧可能な非特許文献M. Castro and B. Liskov, “Practical byzantine fault tolerance,” in Proceedings of the Third Symposium on Operating Systems Design and Implementation, ser. OSDI ’99. Berkeley, CA, USA: USENIX Association, 1999, pp. 173-186に開示されているように、BFTプロトコルは多くのリソースを消費するためn≧3f + 1個のサーバが最大f個の障害に耐えることを要求されるからである。
【０００８】
状態機械複製サービスのための実用的ビザンチン障害耐性（practical Byzantine fault tolerance: PBFT）と呼ばれるもう１つの従来のBFTプロトコルが、http://doi.acm.org/1/1294261.1294280でオンラインで閲覧可能な非特許文献B.-G.Chun, P.Maniatis, S.Shenker, and J.Kubiatowicz, “Attested append only memory: Making adversaries stick to their word,” in Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, ser. SOSP ’07. New York, NY, USA: ACM, 2007, pp. 189-204に示されている。そのようなサービスは、分散型システム内の異なるサーバに渡って複製される状態機械としてモデル化される。各サーバはサービス状態を維持しサービス動作を実行する。各クライアントはサーバに動作実行要求を送り、PBFTは障害のない全てのサーバが同じ順序で同じ動作を実行するようにする。
【０００９】
最近、トラステッドハードウェアが物品計算プラットフォーム上で広範に利用可能になっている。トラステッド実行環境（Trusted execution environments：TEEs）は、例えば、非特許文献J. Ekberg, K. Kostiainen, and N. Asokan, “The untapped potential of trusted execution environments on mobile devices,” IEEE Security & Privacy, vol.12, no.4, pp. 29-37, 2014に開示されているように、既にモバイルプラットフォームに普及しており、また、例えば、非特許文献F.McKeen, I.Alexandrovich, A.Berenzon, C.V.Rozas, H.Shafi, V.Shanbhogue, and U.R.Savagaonkar, “Innovative instructions and software model for isolated execution,” in HASP, 2013, pp. 10:1-10:1又はインテル“Software Guard Extensions Programming Reference,” 2013に開示されているように、より新しいTEEsがPCやサーバ上にデプロイされている。TEEはそのメモリー内のデータに対し機密性及び完全性の保護を提供し、誰もその動作に干渉できないようにする。
【００１０】
トラステッドハードウェアはまた、例えば、以下の非特許文献に開示されたBFTプロトコルにおいてサーバ数及び／又は通信段階数を減らすために用いられてきた。
-M. Correia, N. F. Neves, and P. Verissimo, “How to tolerate half less one byzantine nodes in practical distributed systems,” in Reliable Distributed Systems, 2004. Proceedings of the 23rd IEEE International Symposium on, Oct 2004, pp. 174-183, 
-G. S. Veronese, M. Correia, A. N. Bessani, L. C. Lung, and P. Verissimo, “Efficient byzantine fault-tolerance,” IEEE Transactions on Computers, vol. 62, no. 1, pp. 16-30, Jan 2013, 
-G. S. Veronese, M. Correia, A. N. Bessani, and L. C. Lung, “Ebawa: Efficient byzantine agreement for wide-area networks,” in High-Assurance Systems Engineering (HASE), 2010 IEEE 12th International Symposium on, Nov 2010, pp. 10-19, 
-R. Kapitza, J. Behl, C. Cachin, T. Distler, S. Kuhnle, S. V. Mohammadi, W. Schroeder-Preikschat, and K. Stengel, “Cheapbft: Resource-efficient byzantine fault tolerance,” in Proceedings of the 7th ACM European Conference on Computer Systems, ser. EuroSys ’12. New York, NY, USA: ACM, 2012, pp. 295-308, 
-B.-G. Chun, P. Maniatis, S. Shenker, and J. Kubiatowicz, “Attested append-only memory: Making adversaries stick to their word,” in Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, ser. SOSP ’07. New York, NY, USA: ACM, 2007, pp. 189-204, and
-D. Levin, J. R. Douceur, J. R. Lorch, and T. Moscibroda, “Trinc: Small trusted hardware for large distributed systems,” in Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation, ser. NSDI’09. Berkeley, CA, USA: USENIX Association, 2009, pp. 1-14. 
【００１１】
例えば、MinBFTは、非特許文献G. S. Veronese, M.Correia, A. N. Bessani, L. C. Lung, and P. Verissimo, “Efficient byzantine fault-tolerance,” IEEE Transactions on Computers, vol.62, no.1, pp. 16-30, Jan 2013などに開示されているように、トラステッド単調カウンターを用いて“一意連続識別子生成器”（Unique Sequential Identifier Generator：USIG）サービスを構築しそれによって障害サーバがあいまい表現と呼ばれる矛盾した記述を生成するのを防ぐ。その結果、必要なサーバの数は3f+1から2f+1に減り、通信段階の数は3から2に減る。より詳細には、トラステッド単調カウンターを用いて各サーバに存在するローカルサービスである“一意連続識別子生成器”（USIG）を構築する。USIGは要求された各メッセージに、暗号署名Mである一意の識別子（unique identifier：UI）を一意で単調かつ連続するカウンターcとともに割り当てる。これら３つの特性は、USIGが(1)同じ識別子を２つの異なるメッセージに割り当てない（一意性）、(2)過去の識別子より低い識別子を割り当てない（単調性）、(3)過去の識別子の後続者ではない識別子を割り当てない（連続性）ことを示している。これらの特性はサーバが損なわれた場合でも保証され、サービスはトラステッド実行環境内で実行される。
【００１２】
例えば、CheapBFTは、非特許文献R.Kapitza, J.Behl, C.Cachin, T.Distler, S.Kuhnle, S.V.Mohammadi, W.Schroeder-Preikschat, and K.Stengel, “Cheapbft: Resource-efficient byzantine fault tolerance,” in Proceedings of the 7th ACM European Conference on Computer Systems, ser. EuroSys ’12. New York, NY, USA: ACM, 2012, pp. 295-308などに開示されているように、復号合意プロトコルを起動することにより性能を更に向上させる。障害がない場合、CheapBFTはf+1個のサーバだけが能動的にクライアントの要求に同意しこれを実行することを求める。その他のf個の受動的なサーバは能動的なサーバにより提供される状態更新を処理することによりそれぞれの状態を単に修正する。障害挙動の疑いがある場合、CheapBFTは移行プロトコルを起動して受動的サーバを稼働させその後MinBFTに移行する。
【００１３】
ただし、MinBFTは、非特許文献T. C. Group, “Tpm main, part 1 design principles. specfication version 1.2, revision 103” 2007などに開示されているように、カウンター生成速度を制限する“トラステッドプラットフォームモジュール”（Trusted Platform Module：TPM）を用い、CheapBFTはFPGAベースのトラステッドサブシステムを用いる。また、MinBFTとCheapBFTはともに、各（能動的）サーバにマルチキャスト又は通信／メッセージ複合体O(n2)につながるオール・ツー・オールのブロードキャストの実行を要求する。
【００１４】
非特許文献E. Syta, I. Tamas, D. Visher, D. I. Wolinsky, L. Gasser, N. Gailly, and B. Ford, “Keeping authorities “honest or bust” with decentralized witness cosigning,” in 37th IEEE Symposium on Security and Privacy, 2016には、メッセージの集約を可能にするマルチシグネチャ手順が示されている。しかしながら、このマルチシグネチャ手順にはメッセージサイズを増大させ処理時間を長くするという欠点がある。もう１つの欠点は、複製が別々のメッセージに署名しなければならないことである。
【００１５】
したがって、本発明の少なくとも１つの実施形態は、少なくとも通信コストを大幅に増大させずに計算コストを下げることによりデータのビザンチン障害耐性複製の性能を向上させるという課題に対処する。また、本発明の少なくとも１つの実施形態は、署名などのメッセージに対する複製の動作の数を最小化するという別の課題にも対処する。
【課題を解決するための手段】
【００１６】
一実施形態において、本発明は複数n個のサーバに対してデータのビザンチン障害耐性複製を行う方法を提供する。前記複数n個のサーバは１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含み、f個のサーバは任意に故障する場合があり、n個の全てのサーバはトラステッド計算実体（TCE）を有し、前記方法は前記PNのTCEにより実行される前処理手順を含み、前記前処理手順は
実行される動作を要求する要求メッセージに割り当てられる一意で単調かつ連続したカウンター（UMSC）についてランダムな秘密値を計算し、
前記ランダムな秘密値及び前記UMSCについてコミットメントを計算し、
前記ランダムな秘密値を複数のシェアに分割し、
各シェアのサーバ別の認証付き暗号を、復号が指定された前記各サーバによってのみ実行できるように計算し、後の手順中前記要求メッセージを検証するために前記サーバ別の複数のシェアが用いられ、
計算された前記サーバ別の複数のシェア及び計算された前記コミットメントを前記各サーバに提供する
各ステップを含む。
【００１７】
更なる実施形態において、本発明は複数n個のサーバに対してデータのビザンチン障害耐性複製を行うシステムを提供する。前記複数n個のサーバは１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含み、f個のサーバは任意に故障する場合があり、n個の全てのサーバはトラステッド計算実体（TCE）を有し、前記PNのTCEは
実行される動作を要求する要求メッセージに割り当てられる一意で単調かつ連続したカウンター（UMSC）についてランダムな秘密値を計算し、
前記ランダムな秘密値及び前記UMSCについてコミットメントを計算し、
前記ランダムな秘密値を複数のシェアに分割し、
各シェアのサーバ別の認証付き暗号を、復号が指定された前記各サーバによってのみ実行できるように計算し、後の手順中前記要求メッセージを検証するために前記サーバ別の各シェアが用いられ、
計算された前記サーバ別の各シェア及び計算された前記コミットメントを前記各サーバに提供する
各ステップを実行する。
【００１８】
更なる実施形態において、本発明はコンピュータに複数n個のサーバに対してデータのビザンチン障害耐性複製を行う方法を実行させるプログラムを記憶する非一時的コンピュータ可読媒体を提供する。前記複数n個のサーバは１つのプライマリノード（PN）及びn-1個のバックアップノード（BN）を含み、f個のサーバは任意に故障する場合があり、n個の全てのサーバはトラステッド計算実体（TCE）を有し、前記方法は前記PNのTCEにより実行される前処理手順を含み、前記前処理手順は
実行される動作を要求する要求メッセージに割り当てられる一意で単調かつ連続したカウンター（UMSC）についてランダムな秘密値を計算し、
前記ランダムな秘密値及び前記UMSCについてコミットメントを計算し、
前記ランダムな秘密値を複数のシェアに分割し、
各シェアのサーバ別の認証付き暗号を、復号が指定された前記各サーバによってのみ実行できるように計算し、後の手順中前記要求メッセージを検証するために前記サーバ別の各シェアが用いられ、
計算された前記サーバ別の各シェア及び前記計算されたコミットメントを前記各サーバに提供する
各ステップを含む。
【００１９】
本発明の少なくとも１つの実施形態は、秘密シェアリングを用いてカウンターベースのプロトコルの計算コストを削減して公開鍵操作を最小化する又は完全に取り除きそれにより計算コストを大幅に削減するという利点を有する場合がある。
【００２０】
本発明の少なくとも１つの実施形態は、複製がメッセージの広範なブロードキャスト、例えば、オール・ツー・オールのブロードキャストを実行しなくてもいいようにメッセージを集約するという利点を有する場合がある。
【００２１】
本発明の少なくとも１つの実施形態は、例えば、クライアントが、１つの要求についてf+1個のメッセージではなく１つのメッセージだけを受信するという利点を有する場合がある。
【００２２】
本発明の少なくとも１つの実施形態は、全ての複製が同じカウンター値を維持するという利点を有する場合がある。
【表１】
2019536108.tif 000003
【００２３】
「コンピュータ可読媒体」とは、計算装置又はコンピュータとともに使用可能で情報を保存可能な任意の種類の媒体を指す場合がある。前記情報はコンピュータのメモリーに読み込み可能な任意の種類のデータであってよい。例えば、前記情報には前記コンピュータを用いて実行するプログラムコードが含まれてもよい。コンピュータ可読媒体の例として、テープ、CD-ROM、DVD-ROM、DVD-RAM、DVD-RW、ブルーレイ、DAT、ミニディスク、ソリッドステートディスク（SSD）、フロッピーディスク、SDカード、CFカード、メモリースティック、USBスティック、EPROM、EEPROMなどが挙げられる。
【００２４】
「クライアント」、「サーバ」、及び「プライマリノード」はそれぞれ、特に請求項において、好ましくは明細書において、パーソナルコンピュータ、タブレット、携帯電話、サーバなどの計算を実行する実体、装置、又は計算装置を指し、１つ又は複数のコアを有する１つ又は複数のプロセッサを含み、本発明の１つ又は複数の実施形態の対応するステップを実行するように構成されたアプリケーションを記憶するメモリーに接続可能であってもよい。任意のアプリケーションが、プロセッサ（群）がその上で動作するメモリーにソフトウェアベース及び／又はハードウェアベースでインストールされてもよい。各実体は、計算対象の対応するステップが最適なやり方で実行されるように構成されてもよい。例えば、異なるステップが単一のプロセッサの異なるコア上で並立に実行されてもよい。また、複数の同一又は異なる実体が単一の計算実体を構成してもよい。実体又は実体群はまた、単一の又は複数の物理計算リソース上で動作する仮想実体としてインスタンス化されてもよい。従って、異なる実体が前記物理計算リソース上で実行されてもよい。
【００２５】
「トラステッド計算実体」、すなわち、「TCE」は、特に請求項において、好ましくは明細書において、１つの実体又はサーバ上で動作する他の全てのハードウェア及びソフトウェアからセキュリティクリティカルなロジックを分離・保護する実体、装置、又は計算装置を指す。トラステッド計算実体は該トラステッド計算実体上のトラステッド実行環境内で動作するトラステッドアプリケーションに対して機密性及び完全性の保護を提供して前記トラステッド実行環境の外で動作するいずれのアプリケーションも前記トラステッドアプリケーションの動作に干渉できないようにしている。トラステッド計算実体により提供される又はトラステッド計算実体が対象にするトラステッド実行環境は何らかの形のリモート認証を提供してリモートユーザがトラステッドアプリケーションの現在の構成と挙動を確認できるようにしてもよい。トラステッド実行環境は中央処理装置などの形態で提供されてもよい。
【００２６】
「マルチキャスティング」は、特に請求項において、好ましくは明細書において、情報が宛先装置群に同時に向けられるグループ通信を指す。マルチキャストは一対多通信又は多対多通信としても知られる。
【００２７】
メッセージについての「一意で単調かつ連続するカウンター」とは、特に請求項において、好ましくは明細書において、２つの異なる情報について同じではなく（一意性）、過去のものより低く（単調性）、過去のものの後続者ではない（連続性）カウンターが割り当てられる情報、データ、又はメッセージを指す。
【００２８】
「スタートポロジー」、「ツリートポロジー」、及び「ツリー」はそれぞれの最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、物理的に及び／又は仮想的にスター又はツリーとしてまとめられることがあるサーバ間の接続トポロジーを指す。スタートポロジーにおいて、スターの中心を構成している実体又は装置はこのトポロジー内の他の実体群又は装置群のそれぞれに直接物理的又は仮想的に接続されている。ツリートポロジーにおいて、ネットワークを実行している実体群又は装置群の１つは１つ又は複数の子ノードに接続されているツリーのルートであり、前記子ノード、すなわち、現在の親ノードは他の１つ又は複数の子ノードなどに再度接続されてもよい。
【００２９】
「スパニングツリー」はその最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、IEEE 802.1Dに準拠するスパニングツリープロトコルSTPを指す。
【００３０】
「署名」又は「シェア」に関して「集約された」とは、特に請求項において、好ましくは明細書において、複数の署名部分、複数のシェア、又は秘密の複数の部分を用いて生成された署名、シェア、又は秘密を指し、前記署名部分又は秘密部分は異なる実体群又は装置群により生成され単一の集約署名又は単一の集約秘密を計算する前に集められる。
【００３１】
「ビュー」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、あるネットワーク構成を指す。例えば、あるビューにおいて、１つのサーバはプライマリサーバPNであり、その他のサーバはバックアップサーバである。例えば、PNはクライアント群Cにより要求された動作群の実行の順序を取得する。例えば、PNは次の利用可能シーケンス番号をある要求に割り当てこの割り当てをバックアップサーバ群に送信することによりこれを行う。しかしPNに障害が発生する場合がある。すなわち、PNが同一のシーケンス番号を異なる要求に割り当てる場合がある、又はシーケンス番号の割り当てを中止する場合がある、又はシーケンス番号の間に空白を作る場合がある。そのため、各バックアップサーバはPNにより割り当てられたシーケンス番号をチェックしタイムアウトを用いてPNによる割り当ての中止を検出してもよい。各バックアップサーバは、現在のPNが故障したと思われるときにビュー変更を引き起こして新しいPNを選択してもよい。 
【００３２】
「サーバ別のシェア」又は「BN別のシェア」はそれぞれ、特に請求項において、好ましくは明細書において、その最も広い意味において理解されるべきであり、そのシェアが対応するサーバ又はノードによってのみ復号可能であるように認証付き暗号を介して計算されたシェアを指す。
【００３３】
「コミットメント」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、ある人が選ばれた値やステートメントを他人に秘匿しながらかつコミットされた値やステートメントを後に明らかにする能力を持ってその値やステートメントにコミットできるようにするスキームを指す。
【００３４】
「妥当性を確認する」及び「検証する」とはそれぞれの最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、見直し、調査、（再）チェック、コントロール、確証、（再）保証、証明、肯定、認証などを実行する手順を指す。
【００３５】
任意の種類のデータ、情報、メッセージ、シェアなどに関する「完全性」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、前記データ、情報、メッセージ、シェアなどの完全さ、無損傷性、侵害されていないこと、不可侵性などを指す。
【００３６】
任意の種類のデータ、情報、メッセージ、シェアなどに関する「集める」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、前記データ、情報、メッセージ、シェアなどをフェッチ、受信、取得、入手、要求、及び受信することを指す。
【００３７】
任意の種類のデータ、情報、メッセージ、シェアなどに関する「再構築する」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、前記データ、情報、メッセージ、シェアなどの再建、再配列、再構成、再構築、再設計、再計算、再組み立てなどを行うことを指す。
【００３８】
「サーバ」又は「BN」に関する「能動的」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、クライアント要求などの要求を実行するサーバ群を指し、一方、「サーバ」又は「BN」に関する「受動的」とは、前記受動的サーバが、例えば、能動的なサーバにより提供される状態更新を処理することによりその状態を単に修正することを意味する。
【００３９】
「距離パラメータ」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、例えば、ネットワークトポロジー、ネットワーク管理者、及び／又はスループット、ラウンドトリップ時間、ラウンドトリップ遅延などのネットワークパラメータにより定義される２つの計算実体の間のある種の物理又は仮想空間、範囲、離隔、距離などを示すパラメータを指す。
【００４０】
「履歴情報」とはその最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、準備された要求群のための準備メッセージ群、コミットされた要求群のためのコミットメッセージ群、実行された要求群のための応答メッセージ群、及び前処理パスを受信しない要求に対する要求群を含むことがあるがそれらに限定されない情報を指す。換言すれば、「履歴情報」には全ての準備された要求群、コミットされた要求群、及び実行された要求群が含まれる。
【００４１】
「マッチング」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、正当性、類似性、品質などのための比較、複製、調整、バランス、及びチェックを指す。
【００４２】
「接続」又は「接続している」に関する「直接」とは、その最も広い意味において理解されるべきであり、特に請求項において、好ましくは明細書において、迂回路、回り道、ループ路を介さない任意の種類の物理又は仮想接続を指す。
【００４３】
更なる特徴、利点並びに更なる実施形態が以下の記載の中で説明される、又は明らかになる場合がある。
【００４４】
前記PNはある動作を要求するための要求メッセージを受信してもよく、また少なくとも前記要求メッセージの内容及び一意の識別子（unique identifier: UI）を含む準備メッセージを計算してもよい。前記UIは前記PNのTCEにより計算され、前記要求メッセージの暗号署名及び前記UMSCに基づくものである。前記PNは前記BNに前記準備メッセージを提供してもよい。これにより、前記準備メッセージ内で前記UMSCを前記要求メッセージに割り当てることができる。
【００４５】
ii.前記BNが前記BN別のシェアを復号し復号された前記シェアを前記PNに提供し、
iii.前記PNがいくつかのシェアを集め、
iv.前記PNが集められた前記シェア及び／又は前記PNのシェアに基づいて前記秘密値を再構築し、
v.前記PNが再構築された前記秘密を用いて前記前処理手順中に計算された前記コミットメントを開けることにより再構築された前記秘密を検証し、前記前記PNは再構築された前記秘密が検証されたときに前記要求を実行してもよく、
vi.開けられた前記コミットメントを前記BNに伝達し、開けられた前記コミットメントはブロードキャストティングにより伝達されてもよく、
vii.前記BNのそれぞれが受信され伝達されかつ開けられた前記コミットメントを前記前処理段階中に受信した前記コミットメントと比較する
各ステップのうちの少なくとも１つを実行してもよい。これにより、効率的なやり方で前記要求メッセージを検証することができる。
【００４６】
ステップii)の前に前記BNのそれぞれが各BNのTCEのそれぞれにより前記UIをチェックすることにより前記準備メッセージの妥当性を確認するステップi)を実行してもよく、ステップvii)の後前記BNが前記比較の肯定的な結果に基づいて前記要求メッセージの要求を実行するステップviii)を実行してもよい。これにより、前記準備メッセージの妥当性を確認し前記要求を実行することができる。
【００４７】
集められたシェアの数がn個のサーバの数より少ない場合、集められた各シェアの完全性は前記秘密値を再構築する前に前記PNによりチェックされてもよく、前記シェアの数はサーバの数と等しくてもよい。これにより、破損したシェアを持つ秘密が完全に再構築されるのが避けられるので計算リソースの無駄が回避される。
【００４８】
認証付き暗号については、各BNの公開鍵を用いてもよく、PNと前記BNのそれぞれとのペアで対称的な暗号を用いてもよい。対称的な鍵暗号を用いることにより、例えば、公開鍵操作を省くことができる。
【００４９】
前記PNは再構築された前記秘密が検証されたときに前記要求を実行してもよい。これにより、検証された秘密が利用可能になったとき直ちに前記要求を実行することができる。
【００５０】
能動的BNは前記PNにより検出されてもよく、前記方法の少なくとも１つのステップを実行するために、決定された前記能動的BNだけを用いてもよい。これにより、中心実体が能動的BNを決定し決定された能動的BNだけを用いて前記方法の各ステップを実行することができる。これにより、通信コストが更に削減され、能動的であるBNの検出が単一の実体により実行される。
【００５１】
前記能動的BNは前記PNによりノード群を含み前記PNで根を張るスパニングツリーの形にまとめられてもよく、通信はシェアを集約する能動的BNのスパニングツリーに沿って前記ツリー内の中間ノード群により実行される。これによりスケーラビリティが向上する。
【００５２】
前記PNは全てのサーバの中から選択されてもよく、前記PNに障害があると判断された場合、能動的BNの中から新しいPNが選択される。これにより障害のあるPNが現在PNとして動作する全サーバのうちの新しいBNと交換されるので効率性が高まる。
【００５３】
前記要求メッセージを送信した上である一定時間が経過した後に応答メッセージを受信しないことにより、前記クライアントがPNに障害があると判断してもよい。これにより、容易なやり方で障害のあるPNを特定することができる。
【００５４】
前記新しいPNは
a)BNが、PNの応答を待つための前記一定時間の経過後、全ての他のBNにビュー変更メッセージを送信することによりビュー変更を要求し、
b)距離パラメータに従って新しいPNを能動的であり前記古いPNに最も近いBNとして選び、
c)前記新しいPNが履歴メッセージを計算し、該履歴メッセージは最新のローカルカウンター値の情報並びに前記新しいPNと前記古いPNとの間及び前記新しいPNと他のBNとの間で行われる通信についての要求履歴情報を含み、
d)前記新しいPNが前記履歴メッセージを全ての他のBNに送信し、
e)前記BNのそれぞれが受信された前記要求履歴情報を検証した後ビュー変更メッセージを計算し、
f)受信された履歴メッセージの前記要求履歴情報を検証した後、計算された前記ビュー変更メッセージを全ての他のBNに提供し、
g)BNが、検証された要求履歴を含むf個の一致するビュー変更メッセージ群を受信次第、検証された前記履歴を処理し、
h)前記新しいPNが、f個の一致するビュー変更メッセージ群を受信次第、新しいPNが確立されていることを示すビュー変更メッセージ群を前記f個のBNに提供する
各ステップにより選択されてもよい。
【００５５】
これにより、迅速かつ効率的なやり方でビュー変更、すなわち、障害のあるPNから新しいPNへの切り替えを行うことができる。
【００５６】
障害のあるBNは
a)BNが、メッセージの送信及び受信の少なくともいずれかが発生次第、直接接続された各BNと関連するタイマーを起動し、
b)直接接続されたBNから、直接接続された該BNのタイマーの期限前に有効なシェアを受信しなかった場合、直接接続された前記BNの故障の可能性を示す疑いメッセージを少なくとも前記PNに提供し、
c)前記PNが、少なくとも１つの疑いメッセージを受信次第、前記障害の可能性があるBNを特定し特定された前記障害のあるBNの代替BNを選択し、
d)特定された前記障害のあるBNがその他のBNに無視されるように前記代替BNについての情報を前記他のBNに提供する
各ステップにより特定されてもよい。
【００５７】
これにより、迅速かつ効率的なやり方で障害のあるBNを検出することができる。
【００５８】
直接接続された前記BNは前記BNの子ノード群であってもよく、前記疑いメッセージは前記BNの親ノードにも提供されてよく、疑いメッセージは前記ツリーに沿って前記PNに提供されてもよい。このツリーに沿った受け渡しにより、タイマーを休止させ通信の削減を意味する疑いメッセージ数の削減を実現できる。
【００５９】
PNである特定のサーバ及びBNである他のサーバ群を決定する現在のビューを示すためにビュー番号をメッセージ群に含めてもよい。これにより、最小のデータを用いた容易なやり方でPN及びBNの現在の構成を決定することができる。
【００６０】
再構築された前記秘密の有効な検証に基づいて前記PNは前記要求を実行してもよく、実行された前記要求の結果は増加されたカウンター値とともに前記BNに伝達されてもよい。
【００６１】
本発明の内容を有利なやり方で設計し発展させる方法がいくつもある。このため、独立請求項に従属する請求項、及び以下の図示された例としての本発明の更なる実施形態の説明を参照されたい。図に補助された本発明の更なる実施形態の説明と関連して、本発明の内容の更なる実施形態及び更なる進歩が説明されよう。
【図面の簡単な説明】
【００６２】
【図１】図1は本発明の一実施形態によるシステムを示す。
【図２】図2は本発明の一実施形態による方法のステップの一部を示す。
【図３】図3は本発明の更なる実施形態による方法のステップの一部を示す。
【発明を実施するための形態】
【００６３】
図1において、ビザンチンフリーの耐性アプリケーションを実行するためのリッチ実行環境（rich execution environment: REE）と一意連続識別子生成器（unique sequential identifier generator: USIG）が起動されるトラステッド実行環境であるTEEとを含むプライマリノード2を有する状態機械複製サービス1が示されている。また、状態機械複製サービスにおいて実行されるビザンチンフリーの耐性プロトコルを実行するバックアップサーバ群3も示されている。クライアントCはある特定の動作の実行の要求を図２により詳細に示されているプライマリノード2及び全バックアップサーバ群3に送信する。 
【００６４】
図2は本発明の一実施形態による方法のステップの一部を示し、図3は本発明の更なる実施形態による方法のステップの一部を示す。
【００６５】
参照符号2を有する用語SpはプライマリノードPNと交換可能に用いられ、参照符号3を有する用語Siは図2及び3においてi番目の能動的BNと交換可能に用いられ、参照符号4は受動的BN/複製を表す。
【００６６】
図2では、最初のステップ1)において、プライマリノードPNにより以下の設定手順が実行される：
・SpのローカルTEEは各BN/SiのSiのローカルTEEを用いて秘密鍵kiを設定する。
・Spは能動的Si群をスパニングツリーの形にまとめる。
【００６７】
第２のステップ2において、PN Spは以下の前処理手順を実行する：
各カウンター値cjについて、SpのローカルTEEは以下のことを行う：
1)ランダム秘密sjを生成し数１を計算する。
2)sjを数２に分割する。
3)各能動的Siについて、数３（E()は認証付き暗号である）を計算する。SkはSiの直接の子ノードの１つであるとし、数４が数５（数６はSkの子孫ノードの組である）として計算される。
4)TEE内の署名キーを用いて生成された署名である数７を計算する。
5)数７及び数８をSpに対して明らかにする。
【数１】
2019536108.tif 000004
【数２】
2019536108.tif 000005
【数３】
2019536108.tif 000006
【数４】
2019536108.tif 000007
【数５】
2019536108.tif 000008
【数６】
2019536108.tif 000009
【数７】
2019536108.tif 000010
【数８】
2019536108.tif 000011
【００６８】
換言すれば、前処理段階において、Spのローカルトラステッドハードウェアは一組のカウンター値{cj}についてメッセージ認証コード群数９（sjはランダム秘密である）を事前計算する。その後sjをシェア群数１０に分割し各数１１について数１２を計算する。E()は認証付き暗号である。一実施形態では、E()はその秘密復号鍵が各Siのトラステッドハードウェアにのみ知られている各Siの公開暗号鍵を用いる。第２の実施形態では、E()はSp及びSiのトラステッドハードウェアモジュール間であらかじめ合意されたペアの対称キーを用いる。次に、Spのローカルトラステッドハードウェアはhj及び数１３をSpに明らかにし、Spは別のステップ数１４でそれらを対応するSiに送信する。
【数９】
2019536108.tif 000012
【数１０】
2019536108.tif 000013
【数１１】
2019536108.tif 000014
【数１２】
2019536108.tif 000015
【数１３】
2019536108.tif 000016
【数１４】
2019536108.tif 000017
【００６９】
本実施形態では、“(f+1)から(f+1)”秘密シェアリングが用いられる。具体的に、秘密siは数１５として分割され、各複製はMAC(si, ci)として計算された数１６を取得する。 
【数１５】
2019536108.tif 000018
【数１６】
2019536108.tif 000019
【００７０】
更なる実施形態では、“nから(f+1)”秘密シェアリングが用いられてもよい。具体的に、Spのトラステッドハードウェアはまずn個のランダム値x1,…,xnを生成し、各xiについて 数１７を計算する。その後、各カウンター値ciについて、Spのトラステッドハードウェアは秘密siをシェアするための多項式数１８を生成する。各複製はfi (xj)をシェア数１９として取得し、SpはMax(fi (xi))を取得する。hiは同様にMAC(si, ci)として計算される。秘密を再構築するために、SpはまずMax(fi (xi))がSpが受信したものと等しいかどうかをチェックする。その後、Spはf+1個のシェアを取り上げ数２０を計算する。
【数１７】
2019536108.tif 000020
【数１８】
2019536108.tif 000021
【数１９】
2019536108.tif 000022
【数２０】
2019536108.tif 000023
【００７１】
その後プライマリノードSpは、図2に示されるように、数２１を各能動的複製Siに送信する。プライマリノードSpはこれらのメッセージを一括して全カウンターに送信することができる。
【数２１】
2019536108.tif 000024
【００７２】
その後クライアントCは以下に従って要求手順を実行する：
Cは数２２をSpだけに送信することによりopの実行を要求する。Cはタイムアウトの前に応答を受信しなかった場合REQUESTを全ての複製にブロードキャストする。
【数２２】
2019536108.tif 000025
【００７３】
その後PN Spは以下の準備手順3)を実行する： 
Spはツリー数２３に沿って全ての能動的Siにマルチキャストする又は送信する。 数２４（cjは現在のカウンター値）がSpのローカルTEEにより戻される。 
【数２３】
2019536108.tif 000026
【数２４】
2019536108.tif 000027
【００７４】
j番目の要求の準備段階では、Spのトラステッドハードウェアは現在のカウンター値cjを内部に持つPREPAREメッセージに署名しそれをSpに与え、Spはそれを全Siにマルチキャストする。一実施形態において、この署名はSpのトラステッドハードウェアにのみ知られている本物の非対称署名キーにより行われる。第２の実施形態において、署名は全サーバのトラステッドハードウェアモジュール間でシェアされるグローバル対称キーを用いて行われる。
【００７５】
その後各能動的BNは以下のコミット手順4)及び5)を実行する：
【００７６】
各能動的Siは数２５及び対応する数２６を自身のローカルTEEに与え、各ローカルTEEは以下を検証する：
・σpの有効性；
・数２６の完全性；
・数２６内のカウンター値がcjに等しいかどうか；
・cjがそれ自身により記録された最新のカウンターに連続しているかどうか。
【数２５】
2019536108.tif 000028
【数２６】
2019536108.tif 000029
【００７７】
全てが有効である場合、各TEEはcjを自身のメモリーに最新のカウンター値として記録し、数２７を復号し、結果をSiに示す。
【数２７】
2019536108.tif 000030
【００７８】
BNのツリー状組織構造において、Siはまずその直接の子ノードSkのそれぞれから部分集約シェア数２８を受信するまで待機する。その後、Siは数２９かどうかを検証する。そうである場合、Siは自身の応答数３０を計算し図3のステップ4)に従ってその親ノードに送信する。
【数２８】
2019536108.tif 000031
【数２９】
2019536108.tif 000032
【数３０】
2019536108.tif 000033
【００７９】
ただし、図2において集約は行わなくてもよく、数３１はSiより直接処理ノード2に送信される。
【数３１】
2019536108.tif 000034
【００８０】
換言すれば、コミット段階において、各複製SiはこのPREPAREメッセージを対応する数３２とともに自身のローカルトラステッドハードウェアに与え、ローカルトラステッドハードウェアはa)PREPAREメッセージ内の署名の有効性、b)数３２の完全性、c)PREPAREメッセージ内のカウンター値cjが数３２内のそれと一致するかどうか、及びd)cjがそれ自身により記録された最新のカウンターに連続しているかどうかを検証する。全てが問題なければ、各複製Siは数３３をSiに示し、Siはその後シェア数３４をSpに戻す。Spは少なくとも閾値数の応答を受信すると秘密sjを再構築する。この秘密が正しい（この秘密及び対応するカウンター値のMACが過去のhjを満たす）場合、Spは、例えば、この秘密を各複製BNにマルチキャストする。各複製の観点から、この秘密はCOMMITメッセージの閾値数を表す。
【数３２】
2019536108.tif 000035
【数３３】
2019536108.tif 000036
【数３４】
2019536108.tif 000037
【００８１】
従って、当該秘密を検証した後、各複製BNは以下に示すようにPREPAREメッセージ内の要求を実行する：有効な集約シェア群を受信後、Spはsjを再構築しそれをhjで検証する。有効である場合、Spはopを実行し結果resを取得する。その後、Spは図２のステップ5に従って数３５（cj+1=cj+1）を全ての能動的Siにマルチキャストする。図3において、前記コミットメッセージはツリーに沿って全ての能動的BNに伝達される。その後別のステップにおいて有効なsjを受信次第、各能動的Siはopを実行し結果resを得る。その後各能動的Siはコミット段階と同じ手順を実行してsj+1を開きその結果を図2及び3のステップ6)に従ってPN Spに直接又は図３のツリーに沿って返送する。Spは応答メッセージ数３６をC及びステップ７の他の全ての複製にマルチキャストする。
【数３５】
2019536108.tif 000038
【数３６】
2019536108.tif 000039
【００８２】
PREPARE/COMMITメッセージを受信する及び／又は送信する障害のある複製を特定するために、Siは、PREPARE/COMMITメッセージを受信及び／又は送信次第、自身の直接の子ノードのそれぞれのタイマーを起動する。タイマーが時間切れになる前にSkから有効なシェアを受信した場合、SiはSkのタイマーを休止する。そうでなければ、SiはSUSPECTメッセージ数３７をSp及びツリー構造の場合の親ノードの両方に送信してSpの故障を知らせる。また、Siがその子ノードからSUSPECTを受信した場合、そのメッセージはルートに達するまでツリーに沿ってその親ノードに転送される。ツリーに沿ってメッセージを受け渡すことにより、タイマーを中止しSUSPECTメッセージの数を減らすことができる。Spが同じ経路に沿って複数のSUSPECTメッセージを受信した場合、リーフに最も近いSUSPECTメッセージだけが扱われる。
【数３７】
2019536108.tif 000040
【００８３】
SUSPECTメッセージを受信すると、Spは数３８メッセージを全ての複製に送って被疑複製Skをランダムに選ばれた受動的複製に交換し告発者Siをリーフの位置に移動する。それ以降、Siはもはやいずれの複製も告発できない。Siはプロトコルの仕様に従う又は合意に参加しないことを選択し、その場合、Siは受動的複製側に移動されるので障害のある複製は常に他の複製を「告発」できない。例えば、図２に示されるようなスター状構造の場合、BN間の直接接続は必要ない。従って、障害のあるBNはそのときに受動的BN／複製と見なされるようにPNにより認識されればよい。
【数３８】
2019536108.tif 000041
【００８４】
複製BNが有効なクライアント要求を受信したがタイムアウト後プライマリノードSpから応答を受信しない場合、当該複製BNはプライマリノードSpに障害があると疑って以下のようにビュー変更を開始してもよい。
【００８５】
1)疑いをかけている複製は数３９メッセージを他の全ての複製に送信し、他の全ての複製は全ての複製が通知されるように当該メッセージを再ブロードキャストすることにより応答する。
【数３９】
2019536108.tif 000042
【００８６】
2)新しいプライマリノードSp’がSpとは別の最も低いidを有する能動的複製として決定論的に選ばれる。Sp’は数４０（cは当該プライマリノードのローカルTEEにより記録された最新のカウンター値であり、Oは以下を含むアボート履歴である）を全ての複製に送信する：
・実行された要求群のためのREPLYメッセージ群；
・コミットされた要求群のためのCOMMITメッセージ群；
・準備された要求群のためのPREPAREメッセージ群；
・PREPAREメッセージを受信しない要求群のためのREQUESTメッセージ群。
【数４０】
2019536108.tif 000043
【００８７】
3)SiがSp’からHISTORYメッセージを受信すると、まず履歴Oを検証し次に数４１を送信する。ある複製が異なる複製から正しい履歴及びf個の一致するVIEW-CHANGEメッセージ群を取得すると、当該履歴は安定する。この場合、当該複製はそのローカル状態を考慮しながらアボート履歴を処理する。当該履歴の処理後、障害のない全ての複製は一貫した状態にあるため新しいビューに安全に移行することができる。
【数４１】
2019536108.tif 000044
【００８８】
4)f個の一致するVIEW-CHANGEメッセージ群を受信した後、Sp’は数４２（RはSp’により命名されたf+1個の新しい能動的複製の組）をブロードキャストする。
【数４２】
2019536108.tif 000045
【００８９】
更なる実施形態において、本発明は以下のステップを含むビザンチン障害耐性データ複製方法を提供する。
【００９０】
1)あるクライアントが要求を発することによりシステムを起動する。
2)あるビューにおいて、nノード群のうちの１つがプライマリノードとして選ばれる。その他のノード群はバックアップノード群である。
3)オフライン段階中、このプライマリノードのセキュアなハードウェアが以下の動作を実行する：
a.将来REQUESTメッセージmjに割り当てられるカウンターcjについてランダムな秘密値sjを生成する。
b.sj及びcjのコミットメントをhj=MAC(sj,cj)として計算する。 
c.sjからn個の秘密シェアを数４３として生成する。
d.対応するノード Siのセキュアなハードウェアによってのみ復号できる各シェアの認証付き暗号を数４４として計算する。
e.暗号化されたシェア数４５を各ノードSiに送信する。
4)オンライン段階中、プライマリノードはREQUESTメッセージを受信した後単調なカウンター値cjとともにそのセキュアなハードウェアにより署名されたPREPAREメッセージをバックアップノード群にブロードキャストする。
5)各バックアップノードはこのPREPAREメッセージを検証して署名をチェックし更にカウンターcjがプライマリノードから最後に認識されたカウンターまで連続しているかどうかをチェックする。このチェックは各バックアップノードのセキュアなハードウェアにより行われる。
6)当該PREPAREメッセージが有効である場合、各バックアップノードのセキュアなハードウェアは記録されたプライマリカウンターをcjに更新し、対応する暗号化されたシェア数４５を取得し、それを復号し、シェア数４６をプライマリノードに示す。
7)プライマリノードはnシェア群の中からtを集め秘密数sj（数４７はプライマリノード自身のシェアを含む）を再構築する。t<nである場合、受信された各シェアの完全性は再構築の前にチェックされる。
8)再構築された秘密sjを用いて、プライマリノードはそれがオフライン段階中に生成されたコミットメントhjを開けるかどうかを検証する。それが正常である場合、プライマリノードはオープニング(sj,cj)をバックアップノード群にブロードキャストする。
9)各バックアップノードは受信したオープニングsoをオフライン段階中に受信したコミットメントhjと対照して検証する。オープニングが正常である場合、バックアップノードは要求メッセージを受け入れてもよい。
【数４３】
2019536108.tif 000046
【数４４】
2019536108.tif 000047
【数４５】
2019536108.tif 000048
【数４６】
2019536108.tif 000049
【数４７】
2019536108.tif 000050
【００９１】
更なる実施形態において、本発明は能動的複製群がオール・ツー・オールブロードキャストを除外できかつクライアント群（更に受動的複製群）が１つの要求について(f+1)個のREPLY (UPDATE)メッセージの代わりに１つを受信すればよいようにcheapBFT手順のメッセージ群を集約／コミット／応答／更新する方法を提供する。ここで、プライマリノードSpはトラステッドカウンターを用いSi群にそれぞれのTEE内に最新のカウンター値を記録させる。その結果、全ての複製が同じカウンター値を維持する。
【００９２】
一実施形態において、本発明は更に公開鍵操作を用いることなくメッセージ集約を可能にする。前処理段階を用いることにより、SpのローカルTEEはランダムな秘密値の組を生成し各秘密についてコミットメント（ハッシュ）を生成する。その後SpのローカルTEEは各秘密をシェアに分割し各シェアを各能動的SiのTEEに与える。SpのローカルTEEはまた各コミットメントを全ての複製に示す。その後コミット段階において、各能動的SiはそのローカルTEEからシェアを取得し自身のCOMMITメッセージを表すそのシェアをSpに送信する。f個のシェアを集めた後、Spは秘密を再構築しf+1個のCOMMITメッセージを表す当該秘密を全てのSiに送信する。同じことがUPDATE/REPLYメッセージ群にも当てはまる。ただし、秘密は前処理段階で生成されるため秘密を要求に結びつけることはできない。その代わりに、SpのTEEは前処理段階において秘密をカウンター値に結びつけ準備段階において当該カウンター値を要求に結びつける。これにより、要求は特定の秘密と結びつけられる。
【００９３】
一実施形態において、本発明は更にメッセージの複雑さをO(n2)からO(n)へ削減することができ、プライマリノードSpはf+1個の能動的複製をそれ自身において根付くスパニングツリーの形にまとめて通信コストと計算コストの両方を分散してもよい。各シェアはボトムアップ処理において送信され、各中間ノードはそれ自身のシェアとともにその子ノード群のシェアを集約し、最後にSpは一定の少数のシェアを受信し集約すればよい。これにより、スケーラビリティが向上する。この実施形態はツリー構造を効率的に活用している。それはf+1個の全ての能動的複製が要求群にコミットしそれらを実行することを求められるからである。従って、障害のある中間ノードがそのサブツリー全体を「障害状態」にしても時間の遅延が生じない。
【００９４】
一実施形態において、本発明は更に以下に従って障害のある複製が検出され受動的複製に交換されるのを可能にする：いずれのノードも署名された疑いメッセージをツリー上に送信することによりその直接の子ノードだけを疑うことができる；障害のあるノードは単純にクラッシュする又は誤ったシェアを送信する場合がある。その親ノードはタイムアウトにより当該クラッシュ故障を検出し；また当該シェアを検証することによりビザンチン故障を検出する；Spは告発された当該複製をある受動的複製と交換し当該告発者が他の複製を告発し続けられないように告発者をリーフの中に入れる。Spに障害がある場合、全ての複製がビュー変更動作を実行して新しいプライマリノード及び新しい能動的複製の組を選ぶ。
【００９５】
本発明、特に一部の又は全ての実施形態は、本明細書に参照により取り込まれている非特許文献G. S. Veronese, M. Correia, A. N. Bessani, L. C. Lung, and P. Verissimo, “Efficient byzantine fault-tolerance,” IEEE Transactions on Computers, vol. 62, no. 1, pp. 16-30, Jan 2013に開示されているように、MinBFTの少なくとも一部に基づいても少なくとも一部を用いてもよい。
【００９６】
本発明、特に一部の又は全ての実施形態は、本明細書に参照により取り込まれている非特許文献R. Kapitza, J. Behl, C. Cachin, T. Distler, S. Kuhnle, S. V. Mohammadi, W. Schroder-Preikschat, and K. Stengel, “Cheapbft: Resource-efficient byzantine fault tolerance,” in Proceedings of the 7th ACM European Conference on Computer Systems, ser. EuroSys ’12.New York, NY, USA: ACM, 2012, pp. 295-308に開示されているように、Cheap BFTの少なくとも一部に基づいても少なくとも一部を用いてもよい。
【００９７】
本発明、特に一部の又は全ての実施形態は、本明細書に参照により取り込まれている非特許文献S. Duan, H. Meling, S. Peisert, and H. Zhang, “Bchain: Byzantine replication with high throughput and embedded reconfiguration,” in Principles of Distributed Systems: 18th International Conference, OPODIS 2014, Cortina d’Ampezzo, Italy, December 16-19, 2014. Proceedings, M. K. Aguilera, L. Querzoni, and M. Shapiro, Eds. Cham: Springer International Publishing, 2014, pp. 91-discharge valve 106に開示されているように、故障検出手順の少なくとも一部に基づいても少なくとも一部を用いてもよい。
【００９８】
本発明、特に一部の又は全ての実施形態は、本明細書に参照により取り込まれている、http://dl.acm.org/citation.cfm?id=296806.296824でオンラインで閲覧可能な非特許文献M. Castro and B. Liskov, “Practical byzantine fault tolerance,” in Proceedings of the Third Symposium on Operating Systems Design and Implementation, ser. OSDI ’99. Berkeley, CA, USA: USENIX Association, 1999, pp. 173-186に開示されているように、実用的ビザンチン障害耐性手順の少なくとも一部に基づいても少なくとも一部を用いてもよい。
【００９９】
更に、本発明の少なくとも一実施形態は以下を可能にする又は提供する：
1)同じ通信コストを有しながら競争原因が減るようにビザンチン障害耐性プロトコル内での公開鍵操作を最小化する又はほぼ完全に取り除くための秘密シェアリング。
2)トラステッド計算技術の利用。
【０１００】
要約すると、本発明は必要なサーバの数を3f+1から2f+1に削減し通信ラウンドの数を3から2に削減することができる。また、本発明は高いスループットを可能にする対称かつ軽量の暗号法に依存する対称暗号法に依存しない。
【０１０１】
ここで説明した本発明の多数の変形例や他の実施形態が、本発明が関係し上記の説明や添付の図面に示された内容の恩恵を受ける当業者により想到されよう。従って、本発明は開示された特定の実施形態に限定されるべきではなく、変形例や他の実施形態が添付の特許請求の範囲に含まれることが意図されていると理解すべきである。ここでは特定の用語が使われているが、それらは限定する目的ではなく一般的及び説明的意味で使われている。
【図１】
2019536108.tif 000051
【図２】
2019536108.tif 000052
【図３】
2019536108.tif 000053
【国際調査報告】
2019536108.tif 000054
2019536108.tif 000055