(57)【特許請求の範囲】
【請求項１】
複数のコンピュータデバイスに動作可能に結合されたネットワークを介して、第１のコンピュータデバイスに関連する第１の公開鍵に論理的に関連付けられた第１のレコードを含む分散型データベースを実装する前記複数のコンピュータデバイスに含まれるように構成された前記第１のコンピュータデバイスにおける前記分散型データベースのインスタンスの部分と、
前記分散型データベースの前記インスタンスの前記部分に動作可能に結合された前記第１のコンピュータデバイスのプロセッサと
を備え、前記プロセッサは、
前記複数のコンピュータデバイスのうちの第２のコンピュータデバイスから、前記第１のコンピュータデバイスに関連する第１の公開鍵で暗号化され、前記第２のコンピュータデバイスに関連し、前記分散型データベースの第２のレコードに論理的に関連付けられた、前記第２のコンピュータデバイスに関連する第１の公開鍵を受信し、
前記第１のコンピュータデバイスにおいて、前記第１のコンピュータデバイスに関連する前記第１の公開鍵とペアである秘密鍵によって、前記第２のコンピュータデバイスに関連する前記第１の公開鍵を復号し、
前記第２のコンピュータデバイスへ、前記第２のコンピュータデバイスに関連し、前記分散型データベースの第４のレコードに論理的に関連付けられた第２の公開鍵で暗号化され、前記分散型データベースの第３のレコードに論理的に関連付けられた、前記第１のコンピュータデバイスに関連する第２の公開鍵を送信し、
前記第１のレコードおよび前記第４のレコードを含む複数のソースレコードのうちからの各ソースレコードから、前記第２のレコードおよび前記第３のレコードを含む複数の宛先レコードのうちからの異なる宛先レコードへ値を譲渡するように構成された譲渡コマンドを分散型データベースにポストするための信号を送信するように構成され、前記譲渡コマンドは、前記秘密鍵によって署名され、前記複数の宛先レコードのうちからの各宛先レコードに関連するコンピュータデバイスのアイデンティティが、前記第１のコンピュータデバイスおよび前記第２のコンピュータデバイスを含むコンピュータデバイスのセットの中で隠されるように実行されるように構成される、装置。
【請求項２】
前記分散型データベースの前記インスタンスは、前記分散型データベースの第１のインスタンスであり、前記複数のコンピュータデバイスのうちの第３のコンピュータデバイスにおける前記分散型データベースの第２のインスタンスは、前記第１のレコード、前記第２のレコード、前記第３のレコード、および前記第４のレコードを含む複数のレコードを含み、
前記分散型データベースの前記第１のインスタンスは、前記複数のレコードのうち全てのレコードを含むのではない、請求項１に記載の装置。
【請求項３】
前記譲渡コマンドは、前記複数のソースレコードのうちからの各ソースレコードから前記複数の宛先レコードのうちからの異なる宛先レコードへ前記値を譲渡する前に、前記複数のソースレコードのうちからの各ソースレコードが少なくとも前記値を有することを識別するように構成される、請求項１に記載の装置。
【請求項４】
前記譲渡コマンドは、時間に前記分散型データベースにポストされ、
前記複数のソースレコードのうちからの各ソースレコードが前記時間に少なくとも前記値を有さない場合、前記譲渡コマンドは、前記複数のソースレコードのうちからの各ソースレコードが少なくとも前記値を有するまで前記譲渡を遅延させるように構成される、請求項１に記載の装置。
【請求項５】
前記譲渡コマンドは期間に関連し、前記期間内の時間に前記複数のソースレコードのうちからの各ソースレコードが少なくとも前記値を有する場合、前記複数のソースレコードのうちからの各ソースレコードから前記複数の宛先レコードのうちからの異なる宛先レコードへ前記値を譲渡するように構成される、請求項１に記載の装置。
【請求項６】
前記譲渡コマンドは第１の譲渡コマンドであり、前記第２のレコードは第１の宛先レコードであり、前記コンピュータデバイスのセットはコンピュータデバイスの第１のセットであり、
前記プロセッサは、前記第１の譲渡コマンドが実行される前に前記分散型データベースにポストされる信号を送信するように構成され、第２の譲渡コマンドは、第２の宛先レコードに論理的に関連付けられた公開鍵に対応する秘密鍵に関連するコンピュータデバイスのアイデンティティが前記コンピュータデバイスの第１のセットを含むコンピュータデバイスの第２のセットの中で隠されるように、前記第１の宛先レコードから前記第２の宛先レコードへ前記値を譲渡するように構成され、
前記第２の譲渡コマンドは、前記第１の宛先レコードが期間内の時間に前記値を有する場合、前記第１の宛先レコードから前記第２の宛先レコードへ前記値を譲渡するように構成される、請求項１に記載の装置。
【請求項７】
前記プロセッサは更に、
前記第１のコンピュータデバイスに関連する前記第１の公開鍵と、前記第１のレコードから差し引かれ前記譲渡コマンドの実行によって前記複数の宛先レコードのうちからの各宛先レコードに合計される数値とを前記第２のコンピュータデバイスへ送信するように構成される、請求項１に記載の装置。
【請求項８】
前記譲渡コマンドは更に、
時間閾値より前にコンセンサスプロトコルによって収束に至らなかった場合、前記譲渡コマンドが破棄されるように調整する前記時間閾値を含むように構成される、請求項１に記載の装置。
【請求項９】
前記プロセッサは、
前記第１のコンピュータデバイスに関連する前記第２の公開鍵と前記第２のコンピュータデバイスに関連する前記第１の公開鍵との辞書的比較を実行することによって、前記譲渡コマンドを定義するように構成される、請求項１に記載の装置。
【請求項１０】
前記値は、デジタル資産の金額に対応する、請求項１に記載の装置。
【請求項１１】
複数のコンピュータデバイスに動作可能に結合されたネットワークを介して、第１のコンピュータデバイスに関連する第１の公開鍵に論理的に関連付けられた第１のレコードを含む分散型データベースを実装する前記複数のコンピュータデバイスに含まれるように構成された前記第１のコンピュータデバイスにおける前記分散型データベースのインスタンスの部分と、
前記分散型データベースの前記インスタンスに動作可能に結合された前記第１のコンピュータデバイスのプロセッサと
を備え、前記プロセッサは、
前記複数のコンピュータデバイスのうちの第２のコンピュータデバイスから、前記第２のコンピュータデバイスに関連する第１の公開鍵、および前記第２のコンピュータデバイスに関連する前記第１の公開鍵に論理的に関連付けられた第２のレコードから譲渡するように要求された値を受信し、
前記第１のコンピュータデバイスに関連する暗号化された第２の公開鍵を定義するために、前記第２のコンピュータデバイスに関連する前記第１の公開鍵によって、前記第１のコンピュータデバイスに関連する第２の公開鍵を暗号化し、
前記第２のコンピュータデバイスへ、前記第１のコンピュータデバイスに関連する前記暗号化された第２の公開鍵を送信し、
前記第１のレコードおよび前記第２のレコードを含む複数のソースレコードのうちからの各ソースレコードから、前記第１のコンピュータデバイスに関連する前記第２の公開鍵に論理的に関連付けられた第３のレコードおよび前記第２のコンピュータデバイスに関連する第２の公開鍵に論理的に関連付けられた第４のレコードを含む複数の宛先レコードのうちからの異なる宛先レコードへ前記値を譲渡するように構成された譲渡コマンドであって、前記第１のコンピュータデバイスに関連する前記第１の公開鍵とペアである秘密鍵によって署名され、前記複数の宛先レコードのうちからの各宛先レコードに関連するコンピュータデバイスのアイデンティティが、前記第１のコンピュータデバイスおよび前記第２のコンピュータデバイスを含むコンピュータデバイスのセットの中で隠されるように実行されるように構成された前記譲渡コマンドを、前記分散型データベースにポストするための信号を送信するように構成される、装置。
【請求項１２】
前記分散型データベースの前記インスタンスは、前記分散型データベースの第１のインスタンスであり、前記複数のコンピュータデバイスのうちの第３のコンピュータデバイスにおける前記分散型データベースの第２のインスタンスは、前記第１のレコード、前記第２のレコード、前記第３のレコード、および前記第４のレコードを含む複数のレコードを含み、
前記分散型データベースの前記第１のインスタンスは、前記複数のレコードのうち全てのレコードを含むのではない、請求項１１に記載の装置。
【請求項１３】
前記譲渡コマンドは、期間に関連し、前記期間内の時間に前記複数のソースレコードのうちからの各ソースレコードが少なくとも前記値を有する場合、前記複数のソースレコードのうちからの各ソースレコードから前記複数の宛先レコードのうちからの異なる宛先レコードへ前記値を譲渡するように構成される、請求項１１に記載の装置。
【請求項１４】
前記譲渡コマンドは第１の譲渡コマンドであり、前記第３のレコードは第１の宛先レコードであり、前記コンピュータデバイスのセットはコンピュータデバイスの第１のセットであり、
前記プロセッサは、前記第１の譲渡コマンドが実行される前に前記分散型データベースにポストされる信号を送信するように構成され、第２の譲渡コマンドは、第２の宛先レコードに論理的に関連付けられた公開鍵に対応する秘密鍵に関連するコンピュータデバイスのアイデンティティが前記コンピュータデバイスの第１のセットを含むコンピュータデバイスの第２のセットの中で隠されるように、前記第１の宛先レコードから前記第２の宛先レコードへ前記値を譲渡するように構成され、
前記第２の譲渡コマンドは、前記第１の宛先レコードが期間内の時間に前記値を有する場合、前記第１の宛先レコードから前記第２の宛先レコードへ前記値を譲渡するように構成される、請求項１１に記載の装置。
【請求項１５】
前記譲渡コマンドは更に、
時間閾値より前にコンセンサスプロトコルによって収束に至らなかった場合、前記譲渡コマンドが破棄されるように調整する前記時間閾値を含むように構成される、請求項１１に記載の装置。
【請求項１６】
前記プロセッサは、
前記第１のコンピュータデバイスに関連する前記第２の公開鍵と前記第２のコンピュータデバイスに関連する前記第２の公開鍵との辞書的比較を実行することによって、前記譲渡コマンドを定義するように構成される、請求項１１に記載の装置。
【請求項１７】
前記値は、デジタル資産の金額に対応する、請求項１１に記載の装置。
【請求項１８】
複数のコンピュータデバイスに動作可能に結合されたネットワークを介して、第１の公開鍵に論理的に関連付けられた第１のレコード、第２の公開鍵に論理的に関連付けられた第２のレコード、第３の公開鍵に論理的に関連付けられた第３のレコード、および第４の公開鍵に論理的に関連付けられた第４のレコードを含む分散型データベースを実装する前記複数のコンピュータデバイスに含まれるように構成された第１のコンピュータデバイスにおける前記分散型データベースの第１のインスタンスと、
前記分散型データベースの前記第１のインスタンスに動作可能に結合された前記第１のコンピュータデバイスのプロセッサと
を備え、前記プロセッサは、
前記第１のレコードからの値および前記第２のレコードからの値を、前記値が第１の宛先レコードへ提供され、前記値が第２の宛先レコードへ提供されるように譲渡する要求を含むデータベース動作の指標を受信し、
前記第１のレコードおよび前記第２のレコードから前記第１の宛先レコードおよび前記第２の宛先レコードへ前記値を譲渡するように構成され、前記第３の公開鍵に対応する秘密鍵に関連する第２のコンピュータデバイスのアイデンティティおよび前記第４の公開鍵に対応する秘密鍵に関連する第３のコンピュータデバイスのアイデンティティを隠すように実行されるように構成された譲渡コマンドを、前記分散型データベースの前記第１のインスタンスにおいて実行するように構成される、装置。
【請求項１９】
前記データベース動作の前記指標は、前記第２のコンピュータデバイスから受信され、
前記第２のコンピュータデバイスおよび前記第３のコンピュータデバイスは、前記複数のコンピュータデバイスに含まれない、請求項１８に記載の装置。
【請求項２０】
前記データベース動作の前記指標は、前記第２のコンピュータデバイスから受信され、
前記第２のコンピュータデバイスは、前記複数のコンピュータデバイスに含まれない、請求項１８に記載の装置。
【請求項２１】
前記値は、デジタル資産の金額を示す、請求項１８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
［１００１］  本出願は、参照によってその全体が本明細書に組み込まれる、２０１６年１１月１０日に出願された、“ＭＥＴＨＯＤＳ  ＡＮＤ  ＡＰＰＡＲＡＴＵＳ  ＦＯＲ  Ａ  ＤＩＳＴＲＩＢＵＴＥＤ  ＤＡＴＡＢＡＳＥ  ＩＮＣＬＵＤＩＮＧ  ＡＮＯＮＹＭＯＵＳ  ＥＮＴＲＩＥＳ”と題された米国仮特許出願第６２／４２０，１４７号に対する優先権を主張するものである。
【背景技術】
【０００２】
［１００２］  本明細書において説明される実施形態は、一般にデータベースシステムに関し、より具体的には、ネットワーク内の複数のデバイスにわたるデータベースシステムを実装するための方法および装置に関する。
【０００３】
［１００３］  いくつかの既知の分散型データベースシステムは、分散型データベースシステム内で（たとえば、取引が発生する順序に関する）値に関するコンセンサスを実現しようと試みる。たとえば、多人数参加型オンラインゲームは、ゲームをプレイするためにユーザがアクセスすることができる多数のコンピュータサーバを有し得る。２人のユーザが同時にゲーム内の特定のアイテムを獲得しようとした場合、分散型データベースシステム内のサーバが最終的に、２人のユーザのどちらが最初にアイテムを獲得したかに関する合意に至ることが重要である。
【０００４】
［１００４］  そのような分散型コンセンサスは、たとえばＰａｘｏｓアルゴリズムまたはその変形などの方法および／またはプロセスによって処理され得る。そのような方法および／またはプロセスの下で、データベースシステムのサーバの１つが「リーダ」として設定され、リーダがイベントの順序を決定する。（たとえば多人数参加型ゲーム内の）イベントはリーダに転送され、リーダは、イベントに関する順序付けを選択し、データベースシステムの他のサーバへ順序付けを広める。
【０００５】
［１００５］  しかし、そのような既知のアプローチは、データベースシステムのユーザ（たとえばゲームのプレーヤ）によって信頼された関係者（たとえば中央管理サーバ）によって操作されるサーバを用いる。したがって、データベースシステムを操作するためのリーダまたは信頼された第三者を必要としない分散型データベースシステムのための方法および装置へのニーズがある。
【０００６】
［１００６］  他の分散型データベースは、リーダを有さないように設計されるが、そのような分散型データベース内の取引は公開である。したがって、分散型データベースの他の例は、分散型データベースのどのインスタンスが特定の取引を開始したかを識別することができる。
【０００７】
［１００７］  したがって、リーダがなくともコンセンサスを実現し、かつ取引の匿名性を維持することが可能な分散型データベースシステムへのニーズがある。
【発明の概要】
【課題を解決するための手段】
【０００８】
［１００８］  いくつかの実施形態において、装置は、コンピュータデバイスのグループに動作可能に結合されたネットワークを介して分散型データベースを実装するコンピュータデバイスのグループに含まれるように構成された第１のコンピュータデバイスにおける分散型データベースの第１のインスタンスの少なくとも一部を含む。分散型データベースは、第１のコンピュータデバイスに関連する第１の公開鍵に論理的に関連付けられた第１のレコードを含む。装置は、分散型データベースの第１のインスタンスの一部に動作可能に結合されたプロセッサも含む。プロセッサは、コンピュータデバイスのグループのうちの第２のコンピュータデバイスから、（１）第１のコンピュータデバイスに関連する第１の公開鍵によって暗号化され、（２）分散型データベースの第２のレコードに論理的に関連付けられた、第２のコンピュータデバイスに関連する第１の公開鍵を受信するように構成される。プロセッサは、第１のコンピュータデバイスに関連する第１の公開鍵とペアである秘密鍵によって、第２のコンピュータデバイスに関連する第１の公開鍵を暗号化するように構成される。プロセッサは、第２のコンピュータデバイスに関連する第２の公開鍵によって暗号化された、第１のコンピュータデバイスに関連する第２の公開鍵を第２のコンピュータデバイスへ送信するように構成される。第１のコンピュータデバイスおよび第２のコンピュータデバイスの双方は、第１のコンピュータデバイスに関連する第１の公開鍵に関連するソースレコード、および第２のコンピュータデバイスに関連する第２の公開鍵に関連するソースレコードから、第１のコンピュータデバイスに関連する第２の公開鍵に関連する宛先レコード、および第２のコンピュータデバイスに関連する第１の公開鍵に関連する宛先レコードへの譲渡にデジタル署名またはこれを承認するように構成される。この譲渡はその後、２つのソースレコードから２つの宛先レコードへ値を譲渡する。
【図面の簡単な説明】
【０００９】
【図１】［１００９］実施形態に係る、分散型データベースシステムを示す高レベルブロック図である。
【図２】［１０１０］実施形態に係る、分散型データベースシステムのコンピュータデバイスを示すブロック図である。
【図３】〜
【図６】［１０１１］実施形態に係る、ハッシュグラフの例を示す。
【図７】［１０１２］実施形態に係る、第１のコンピュータデバイスと第２のコンピュータデバイスとの間の通信フローを示すフロー図である。
【図８】［１０１３］実施形態に係る、ハッシュグラフの例である。
【図９】［１０１４］実施形態に係る、ハッシュグラフの例である。
【図１０】［１０１５］実施形態に係る、２つのコンピュータデバイス間での匿名データベース取引のグラフィカル表現の例である。
【図１１】［１０１６］実施形態に係る、様々なコンピュータデバイス間での匿名データベース取引を表すツリーの複数のレベルにわたる匿名データベース取引のグラフィカル表現を示す。
【図１２】［１０１７］実施形態に係る、様々なコンピュータデバイス間で並行して実行される匿名データベース取引のグラフィカル表現を示す。
【図１３Ａ】〜
【図１３Ｂ】［１０１８］実施形態に係る、ハッシュグラフと併用するためのコンセンサス方式の例を示す。
【図１４Ａ】〜
【図１４Ｂ】［１０１９］他の実施形態に係る、ハッシュグラフと併用するためのコンセンサス方式の例を示す。
【発明を実施するための形態】
【００１０】
［１０２０］  いくつかの実施形態において、装置は、コンピュータデバイスのグループに動作可能に結合されたネットワークを介して分散型データベースを実装するコンピュータデバイスのグループに含まれるように構成された第１のコンピュータデバイスにおける分散型データベースの第１のインスタンスの少なくとも一部を含む。分散型データベースは、第１のコンピュータデバイスに関連する第１の公開鍵に論理的に関連付けられた第１のレコードを含む。装置は、分散型データベースの第１のインスタンスの一部に動作可能に結合されたプロセッサも含む。プロセッサは、コンピュータデバイスのグループのうちの第２のコンピュータデバイスから、（１）第１のコンピュータデバイスに関連する第１の公開鍵によって暗号化され、（２）分散型データベースの第２のレコードに論理的に関連付けられた、第２のコンピュータデバイスに関連する第１の公開鍵を受信するように構成される。プロセッサは、第１のコンピュータデバイスに関連する第１の公開鍵とペアである秘密鍵によって、第２のコンピュータデバイスに関連する第１の公開鍵を復号するように構成される。プロセッサは、第２のコンピュータデバイスに関連する第２の公開鍵によって暗号化された、第１のコンピュータデバイスに関連する第２の公開鍵を第２のコンピュータデバイスへ送信するように構成される。第１のコンピュータデバイスおよび第２のコンピュータデバイスの双方は、第１のコンピュータデバイスに関連する第１の公開鍵に関連するソースレコードおよび第２のコンピュータデバイスに関連する第２の公開鍵に関連するソースレコードから、第１のコンピュータデバイスに関連する第２の公開鍵に関連する宛先レコードおよび第２のコンピュータデバイスに関連する第１の公開鍵に関連する宛先レコードへの譲渡にデジタル署名またはこれを承認するように構成される。この譲渡はその後、２つのソースレコードから２つの宛先レコードへ値を譲渡する。
【００１１】
［１０２１］  いくつかの実施形態において、装置は、コンピュータデバイスのグループに動作可能に結合されたネットワークを介して分散型データベースを実装するコンピュータデバイスのグループに含まれるように構成された第１のコンピュータデバイスにおける分散型データベースの少なくとも一部の第１のインスタンスを含む。分散型データベースは、第１のコンピュータデバイスに関連する第１の公開鍵に論理的に関連付けられた第１のレコードを含む。第１のコンピュータデバイスのプロセッサは、分散型データベースの少なくとも一部の第１のインスタンスに動作可能に結合される。プロセッサは、コンピュータデバイスのグループのうちの第２のコンピュータデバイスから、第１のコンピュータデバイスに関連する第１の公開鍵で暗号化された、第２のコンピュータデバイスに関連する第１の公開鍵、および第２のコンピュータデバイスに関連する第２の公開鍵に論理的に関連付けられた第２のレコードから分散型データベース内で作成される宛先レコードへ譲渡されることが要求された値を受信するように構成される。第１のコンピュータデバイスおよび第２のコンピュータデバイスはいずれも、第１のレコードおよび第２のレコードから第３のレコードおよび第４のレコードへ値を譲渡するように構成された譲渡コマンドを分散型データベース内へポストするための信号を送信するように構成され、それによって分散型データベース内に第３および第４のレコードが作成される。第３のレコードは、第１のコンピュータデバイスに関連する第２の公開鍵に論理的に関連付けられ、第４のレコードは、第２のコンピュータデバイスに関連する第１の公開鍵に論理的に関連付けられる。譲渡コマンドは、第１のコンピュータデバイスに関連する第１の公開鍵とペアである秘密鍵によって署名され、第２のコンピュータデバイスに関連する第２の公開鍵とペアである秘密鍵によっても署名され、第１のコンピュータデバイスに関連する第２の公開鍵に対応する秘密鍵に関連するコンピュータデバイスのアイデンティティが、第１のコンピュータデバイスおよび第２のコンピュータデバイスを含むコンピュータデバイスのセットの中で隠されるように実行されるように構成される。
【００１２】
［１０２２］  いくつかの実施形態において、装置は、コンピュータデバイスのグループに動作可能に結合されたネットワークを介して分散型データベースを実装するコンピュータデバイスのグループに含まれるように構成された第１のコンピュータデバイスにおける分散型データベースの少なくとも一部の第１のインスタンスを含む。分散型データベースは、第１の公開鍵に論理的に関連付けられた第１のレコード、第２の公開鍵に論理的に関連付けられた第２のレコード、第３の公開鍵に論理的に関連付けられた第３のレコード、および第４の公開鍵に論理的に関連付けられた第４のレコードを含む。第１のコンピュータデバイスのプロセッサは、分散型データベースの少なくとも一部の第１のインスタンスに動作可能に結合される。プロセッサは、第１のレコードに関連する値および第２のレコードに関連する値を第３のレコードおよび第４のレコードの両方へ譲渡する要求を含むデータベース動作のインジケーションを受信するように構成される。譲渡コマンドは、第３の公開鍵に対応する秘密鍵に関連するコンピュータデバイスのアイデンティティおよび第４の公開鍵に対応する秘密鍵に関連するコンピュータデバイスのアイデンティティを隠すように実行されるように構成される。
【００１３】
［１０２３］  本明細書で用いられる場合、モジュールはたとえば、特定の機能の実行に関連する動作可能に結合された電気部品の任意のアセンブリおよび／またはセットであってよく、たとえばメモリ、プロセッサ、電気トレース、光コネクタ、（ハードウェア内で実行する）ソフトウェアなどを含んでよい。
【００１４】
［１０２４］  本明細書で用いられる場合、単数形の「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈が特に明示しない限り、複数形への言及を含む。よって、たとえば「モジュール」という用語は、単一のモジュールまたはモジュールの組み合わせを意味することが意図される。たとえば「ネットワーク」は、単一のネットワークまたはネットワークの組み合わせを意味することが意図される。
【００１５】
［１０２５］  図１は、実施形態に係る、分散型データベースシステム１００を示す高レベルブロック図である。図１は、４つのコンピュータデバイス（コンピュータデバイス１１０、コンピュータデバイス１２０、コンピュータデバイス１３０、およびコンピュータデバイス１４０）にわたり実装される分散型データベース１００を示すが、理解すべき点として、分散型データベース１００は、図１に示されないコンピュータデバイスを含む任意の数のコンピュータデバイスのセットを用いてよい。ネットワーク１０５は、有線ネットワークおよび／または無線ネットワークとして実装され、コンピュータデバイス１１０、１２０、１３０、１４０を動作可能に結合するために用いられる、任意の種類のネットワーク（たとえばローカルエリアネットワーク（ＬＡＮ）、広域ネットワーク（ＷＡＮ）、仮想ネットワーク、テレコミュニケーションネットワーク）であってよい。本明細書において更に詳しく説明するように、いくつかの実施形態において、たとえばコンピュータデバイスは、インターネットサービスプロバイダ（ＩＳＰ）およびインターネット（たとえばネットワーク１０５）を介して互いに接続されたパーソナルコンピュータである。いくつかの実施形態において、接続は、ネットワーク１０５を介して、任意の２つのコンピュータデバイス１１０、１２０、１３０、１４０の間に確立され得る。図１に示すように、たとえば接続は、コンピュータデバイス１１０と、コンピュータデバイス１２０、コンピュータデバイス１３０、またはコンピュータデバイス１４０のいずれか１つとの間に確立され得る。
【００１６】
［１０２６］  いくつかの実施形態において、コンピュータデバイス１１０、１２０、１３０、１４０は、中間ネットワークおよび／または交換ネットワーク（図１に不図示）を介して互いに通信（たとえばデータを送信および／または受信）し、かつネットワークと通信してよい。そのような中間ネットワークおよび／または交換ネットワークは、ネットワーク１０５と同じ種類および／または異なる種類のネットワークであってよい。
【００１７】
［１０２７］  各コンピュータデバイス１１０、１２０、１３０、１４０は、他のコンピュータデバイスの１または複数からのデータを送信および／または受信するためにネットワーク１０５を介してデータを送信するように構成された任意の種類のデバイスであってよい。コンピュータデバイスの例は、図１に示される。コンピュータデバイス１１０は、メモリ１１２、プロセッサ１１１、および出力デバイス１１３を含む。メモリ１１２は、たとえばランダムアクセスメモリ（ＲＡＭ）、メモリバッファ、ハードドライブ、データベース、消去可能プログラマブル読取専用メモリ（ＥＰＲＯＭ）、電気的消去可能読取専用メモリ（ＥＥＰＲＯＭ）、読取専用メモリ（ＲＯＭ）などであってよい。いくつかの実施形態において、コンピュータデバイス１１０のメモリ１１２は、分散型データベースのインスタンス（たとえば分散型データベースインスタンス１１４）に関連するデータを含む。いくつかの実施形態において、メモリ１１２は、プロセッサに、分散型データベースの他のインスタンス（たとえば、コンピュータデバイス１２０における分散型データベースインスタンス１２４）との間で、同期イベントのレコード、他のコンピュータデバイスとの以前の同期イベントのレコード、同期イベントの順序、パラメータに関する値（たとえば取引を定量化するデータベースフィールド、イベントが発生する順序を定量化するデータベースフィールド、および／またはデータベースに値が格納され得る他の任意の適当なフィールド）を送信および／または受信することに関連するモジュール、プロセス、および／または機能を実行させるための命令を格納する。
【００１８】
［１０２８］  分散型データベースはたとえば、データの格納、修正、および／または削除を含む、データの操作を行うように構成され得る。いくつかの実施形態において、分散型データベースインスタンス１１４は、リレーショナルデータベース、オブジェクトデータベース、ポストリレーショナルデータベース、および／または他の任意の適当な種類のデータベースであってよい。たとえば分散型データベースインスタンス１１４は、任意の特定の機能および／または業種に関連するデータを格納してよい。たとえば分散型データベースインスタンス１１４は、特定の金融商品の所有権の履歴に関連する値および／または値のベクトルを含む、（たとえばコンピュータデバイス１１０のユーザの）金融取引を格納してよい。一般に、ベクトルは、パラメータの値の任意のセットであってよく、パラメータは、様々な値をとることができる任意のデータオブジェクトおよび／またはデータベースフィールドであってよい。よって、分散型データベースインスタンス１１４は、複数のパラメータおよび／またはフィールドを有してよく、その各々が値のベクトルに関連付けられる。値のベクトルは、そのデータベースインスタンス１１４内のパラメータおよび／またはフィールドに関する実際の値を決定するために用いられる。
【００１９】
［１０２９］  いくつかの例において、分散型データベースインスタンス１１４は、たとえば（鍵、値）ペアのセットなど、他のデータ構造を実装するために用いられてもよい。分散型データベースインスタンス１１４によって記録された取引は、たとえば、（鍵、値）ペアのセットにおける（鍵、値）ペアの追加、削除、または修正であってよい。
【００２０】
［１０３０］  いくつかの例において、分散型データベースシステム１００または分散型データベースインスタンス１１４、１２４、１３４、１４４のいずれかが照会され得る。たとえば、照会は鍵で構成されてよく、分散型データベースシステム１００または分散型データベースインスタンス１１４、１２４、１３４、１４４から返信された結果は、鍵に関連付けられた値であってよい。いくつかの例において、分散型データベースシステム１００または分散型データベースインスタンス１１４、１２４、１３４、１４４のいずれかは、取引を通して修正されてもよい。たとえば、データベースを修正する取引は、修正取引を承認する関係者によるデジタルシグネチャを含んでよい。
【００２１】
［１０３１］  分散型データベースシステム１００は、たとえば様々なユーザに関連付けられた属性を分散型アイデンティティシステムに格納することなど、多数の目的で用いられ得る。たとえばそのようなシステムは、ユーザのアイデンティティを「鍵」として用い、ユーザに関連付けられた属性のリストを「値」として用いてよい。いくつかの例において、アイデンティティは、そのユーザが知っている対応する秘密鍵を有する暗号公開鍵であってよい。各属性はたとえば、その属性を主張する権利を有する当局によってデジタル署名され得る。また各属性は、たとえば、属性を読み取る権利を有する個人または個人のグループに関連付けられた公開鍵で暗号化されてもよい。いくつかの鍵または値は、その鍵または値を修正または削除することが許可された関係者の公開鍵のリストを添付されてもよい。
【００２２】
［１０３２］  他の例において、分散型データベースインスタンス１１４は、たとえばゲームプレイアイテムの現在のステータスおよび所有権など、多人数同時参加型ゲーム（ＭＭＧ）に関連するデータを格納してよい。いくつかの例において、分散型データベースインスタンス１１４は、図１に示すように、コンピュータデバイス１１０内に実装され得る。他の例において、分散型データベースのインスタンスは、コンピュータデバイスによって（たとえばネットワークを介して）アクセス可能であるが、コンピュータデバイスには実装されない（図１には不図示）。
【００２３】
［１０３３］  コンピュータデバイス１１０のプロセッサ１１１は、分散型データベースインスタンス１１４を作動および／または実行するように構成された任意の適当な処理デバイスであってよい。たとえばプロセッサ１１１は、本明細書で更に詳しく説明するように、コンピュータデバイス１２０からの信号の受信に応答して分散型データベースインスタンス１１４を更新し、および／またはコンピュータデバイス１２０へ信号を送信させるように構成され得る。より具体的には、本明細書で更に詳しく説明するように、プロセッサ１１１は、他のコンピュータデバイスからの取引に関連する同期イベント、同期イベントの順序に関連するレコードなどの受信に応答して、分散型データベースインスタンス１１４を更新するためのモジュール、機能、および／またはプロセスを実行するように構成され得る。他の実施形態において、プロセッサ１１１は、分散型データベースの他のインスタンス（たとえばコンピュータデバイス１２０における分散型データベースインスタンス１２４）に格納されたパラメータの値の受信に応答して分散型データベースインスタンス１１４を更新し、および／またはコンピュータデバイス１１０における分散型データベースインスタンス１１４に格納されたパラメータの値をコンピュータデバイス１２０へ送信させるためのモジュール、機能、および／またはプロセスを実行するように構成され得る。いくつかの実施形態において、プロセッサ１１１は、汎用プロセッサ、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、特定用途向け集積回路（ＡＳＩＣ）、デジタル信号プロセッサ（ＤＳＰ）などであってよい。
【００２４】
［１０３４］  ディスプレイ１１３は、たとえば液晶ディスプレイ（ＬＣＤ）、陰極線管ディスプレイ（ＣＲＴ）など、任意の適当なディスプレイであってよい。他の実施形態において、コンピュータデバイス１１０、１２０、１３０、１４０のいずれかは、ディスプレイ１１３、１２３、１３３、１４３の代替または追加として他の出力デバイスを含む。たとえばコンピュータデバイス１１０、１２０、１３０、１４０のいずれか１つは、オーディオ出力デバイス（たとえばスピーカ）、触覚出力デバイスなどを含んでよい。また他の実施形態において、コンピュータデバイス１１０、１２０、１３０、１４０のいずれかは、ディスプレイ１１３、１２３、１３３、１４３の代替または追加として入力デバイスを含む。たとえばコンピュータデバイス１１０、１２０、１３０、１４０のいずれか１つは、キーボード、マウスなどを含んでよい。
【００２５】
［１０３５］  コンピュータデバイス１２０は、それぞれプロセッサ１１１、メモリ１１２、およびディスプレイ１１３と構造的および／または機能的に同様であってよいプロセッサ１２１、メモリ１２２、およびディスプレイ１２３を有する。また、分散型データベースインスタンス１２４は、分散型データベースインスタンス１１４と構造的および／または機能的に同様であってよい。
【００２６】
［１０３６］  コンピュータデバイス１３０は、それぞれプロセッサ１１１、メモリ１１２、およびディスプレイ１１３と構造的および／または機能的に同様であってよいプロセッサ１３１、メモリ１３２、およびディスプレイ１３３を有する。また、分散型データベースインスタンス１３４は、分散型データベースインスタンス１１４と構造的および／または機能的に同様であってよい。
【００２７】
［１０３７］  コンピュータデバイス１４０は、それぞれプロセッサ１１１、メモリ１１２、およびディスプレイ１１３と構造的および／または機能的に同様であってよいプロセッサ１４１、メモリ１４２、およびディスプレイ１４３を有する。また、分散型データベースインスタンス１４４は、分散型データベースインスタンス１１４と構造的および／または機能的に同様であってよい。
【００２８】
［１０３８］  コンピュータデバイス１１０、１２０、１３０、１４０は、互いに同様であるものとして示されるが、分散型データベースシステム１００の各コンピュータデバイスは、他のコンピュータデバイスと異なってもよい。分散型データベースシステム１００の各コンピュータデバイス１１０、１２０、１３０、１４０は、たとえばコンピューティングエンティティ（たとえばデスクトップコンピュータ、ラップトップコンピュータなどのパーソナルコンピューティングデバイス）、モバイルフォン、パーソナルデジタルアシスタント（ＰＤＡ）などのいずれかであってよい。たとえば、コンピュータデバイス１１０はデスクトップコンピュータであってよく、コンピュータデバイス１２０はスマートフォンであってよく、コンピュータデバイス１３０はサーバであってよい。
【００２９】
［１０３９］  いくつかの実施形態において、コンピュータデバイス１１０、１２０、１３０、１４０の１または複数の部分は、ハードウェアベースのモジュール（たとえばデジタル信号プロセッサ（ＤＳＰ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ））および／またはソフトウェアベースのモジュール（たとえば、メモリに格納されおよび／またはプロセッサで実行されるコンピュータコードのモジュール）を含んでよい。いくつかの実施形態において、コンピュータデバイス１１０、１２０、１３０、１４０に関連する機能（たとえば、プロセッサ１１１、１２１、１３１、１４１に関連する機能）の１または複数は、１または複数のモジュールに含まれ得る（たとえば図２を参照）。
【００３０】
［１０４０］  コンピュータデバイス（たとえばコンピュータデバイス１１０、１２０、１３０、１４０）のプロパティを含む分散型データベースシステム１００のプロパティ、コンピュータデバイスの数、およびネットワーク１０５は、任意の数の方法で選択され得る。いくつかの例において、分散型データベースシステム１００のプロパティは、分散型データベースシステム１００の管理者によって選択され得る。他の例において、分散型データベースシステム１００のプロパティは、分散型データベースシステム１００のユーザによって集合的に選択され得る。
【００３１】
［１０４１］  分散型データベースシステム１００が用いられることにより、コンピュータデバイス１１０、１２０、１３０、および１４０の中からリーダが指名されることはない。具体的には、コンピュータデバイス１１０、１２０、１３０、または１４０のいずれも、コンピュータデバイス１１０、１２０、１３０、１４０の分散型データベースインスタンス１１１、１２、１３１、１４１に格納された値間での論議を解決するためのリーダとして識別および／または選択されない。代わりに、本明細書で説明されるイベント同期プロセス、投票プロセスおよび／または方法を用いて、コンピュータデバイス１１０、１２０、１３０、１４０は集合的にパラメータの値に収束してよい。
【００３２】
［１０４２］  分散型データベースシステム内にリーダを有さないことにより、分散型データベースシステムの安全性が高まる。具体的には、リーダがいる場合、攻撃および／または故障の単一ポイントが存在する。悪意のあるソフトウェアがリーダに侵入し、および／またはリーダの分散型データベースインスタンスにおけるパラメータの値が悪意的に変更された場合、故障および／または不正値が他の分散型データベースインスタンス全体に伝搬する。しかしリーダレスシステムにおいて、攻撃および／または故障の単一ポイントは存在しない。具体的には、本明細書で更に詳しく説明するように、リーダレスシステムの分散型データベースインスタンスにおけるパラメータが値を含む場合、その値は、その分散型データベースインスタンスがシステム内の他の分散型データベースインスタンスと値を交換した後、変更される。また、本明細書で説明されるリーダレス分散型データベースシステムは、本明細書で更に詳しく説明するように、デバイス間で送信されるデータの量を低減するとともに収束の速度を増加させる。
【００３３】
［１０４３］  図２は、実施形態に係る、分散型データベースシステム（たとえば分散型データベースシステム１００）のコンピュータデバイス２００を示す。いくつかの実施形態において、コンピュータデバイス２００は、図１に関して示され説明されたコンピュータデバイス１１０、１２０、１３０、１４０と同様であってよい。コンピュータデバイス２００は、プロセッサ２１０およびメモリ２２０を含む。プロセッサ２１０およびメモリ２２０は、互いに動作可能に結合される。いくつかの実施形態において、プロセッサ２１０およびメモリ２２０は、図１に関して詳しく説明されたプロセッサ１１１およびメモリ１１２とそれぞれ同様であってよい。図２に示すように、プロセッサ２１０は、データベース収束モジュール２１１および通信モジュール２１０を含み、メモリ２２０は、分散型データベースインスタンス２２１を含む。通信モジュール２１２は、コンピュータデバイス２００が他のコンピュータデバイスと通信（たとえば他のコンピュータデバイスとの間でデータを送信および／または受信）することを可能にする。いくつかの実施形態において、通信モジュール２１２（図１には不図示）は、コンピュータデバイス１１０がコンピュータデバイス１２０、１３０、１４０と通信することを可能にする。通信モジュール２１０は、たとえばネットワークインタフェースコントローラ（ＮＩＣ）、無線接続、有線ポートなどを含み、および／または有効にしてよい。このように、通信モジュール２１０は、コンピュータデバイス２００と他のデバイスとの間の（たとえば図１のネットワーク１０５またはインターネット（不図示）などのネットワークを介した）通信セッションを確立および／または維持することができる。同様に述べると、通信モジュール２１０は、コンピュータデバイス２００が他のデバイスとの間でデータを送信および／または受信することを可能にしてよい。
【００３４】
［１０４４］  いくつかの例において、データベース収束モジュール２１１は、他のコンピューティングデバイスとイベントおよび／または取引を交換し、データベース収束モジュール２１１が受信するイベントおよび／または取引を格納し、イベント間の参照のパターンによって定められた半順序に基づいてイベントおよび／または取引の順序付けを計算することができる。各イベントは、２つの先行イベントの（そのイベントを２つの先行イベントおよびそれらの祖先イベントに結び付ける、またはその逆の）暗号ハッシュ、（たとえば記録すべき取引などの）ペイロードデータ、たとえば現在時間、作成者が主張する、イベントが最初に定義された時間であるタイムスタンプ（たとえばデータおよびＵＴＣ時間）といった他の情報などを含むレコードであってよい。いくつかの例において、メンバによって定義された第１イベントは、他のメンバによって定義された単一イベントのハッシュしか含まない。そのような例において、メンバは、以前の自己ハッシュ（たとえば、そのメンバによって過去に定義されたイベントのハッシュ）を未だ有さない。いくつかの例において、分散型データベース内の第１イベントは、（その分散型データベースに関する先行イベントが存在しないために）任意の先行イベントのハッシュを含まない。
【００３５】
［１０４５］  いくつかの実施形態において、そのような２つの先行イベントの暗号ハッシュは、イベントを入力として用いる暗号ハッシュ関数に基づいて定義されたハッシュ値であってよい。具体的には、そのような実施形態において、イベントは、（そのイベントの情報を表す）特定のバイトシーケンスまたはストリングを含む。イベントのハッシュは、そのイベントに関するバイトシーケンスを入力として用いるハッシュ関数からの戻り値であってよい。他の実施形態において、イベントに関連する他の任意の適当なデータ（たとえば識別子、シリアル番号、イベントの特定の部分を表すバイトなど）が、そのイベントのハッシュを計算するためのハッシュ関数への入力として用いられ得る。任意の適当なハッシュ関数が、ハッシュを定義するために用いられ得る。いくつかの実施形態において、各メンバは、所与のイベントに関して各メンバにおいて同じハッシュが生成されるように、同じハッシュ関数を用いる。イベントはその後、イベントを定義および／または作成するメンバによってデジタル署名され得る。
【００３６】
［１０４６］  いくつかの例において、イベントのセットおよびそれらの相互接続は、有向非巡回グラフ（ＤＡＧ）を形成してよい。いくつかの例において、ＤＡＧ内の各イベントは、２つの先行イベントを参照し（そのイベントを２つの先行イベントおよびそれらの祖先イベントに結び付け、またはその逆であり）、各参照は、厳密に１つに対するものであり、ループは存在しない。いくつかの実施形態において、ＤＡＧは、暗号ハッシュに基づくので、データ構造は、（本明細書において「ハッシュＤＡＧ」とも称される）ハッシュグラフと呼ばれ得る。ハッシュグラフは、半順序を直接符号化し、すなわち、ＹがＸのハッシュを含む場合、またはＸのハッシュを含むイベントのハッシュをＹが含む場合、または任意の長さのそのような経路に関して、イベントＸはイベントＹより前に来ることが知られる。ただし、ＸからＹへの、またはＹからＸへの経路が存在しない場合、半順序は、どのイベントが最初になるかを定義しない。したがって、データベース収束モジュールは、半順序から全順序を計算することができる。これは、コンピュータデバイスが同じ順序を計算するように、コンピュータデバイスによって用いられる任意の適当な確定関数によって行われ得る。いくつかの実施形態において、各メンバは、各同期後にこの順序を再計算してよく、最終的にコンセンサスが現れるようにこれらの順序は収束してよい。
【００３７】
［１０４７］  コンセンサスアルゴリズムは、ハッシュグラフ内のイベントの順序および／またはイベント内に格納された取引の順序を決定するために用いられ得る。一方、取引の順序は、順序に従ってこれらの取引を行った結果としてデータベースの状態を定義してよい。定義されたデータベースの状態は、データベース状態変数として格納され得る。
【００３８】
［１０４８］  いくつかの例において、データベース収束モジュールは、ハッシュグラフ内の半順序から全順序を計算するために以下の関数を用いてよい。（「メンバ」と呼ばれる）他のコンピュータデバイスの各々について、データベース収束モジュールは、そのメンバによってイベント（および／またはこれらのイベントの指標）が受信された順序を知るために、ハッシュグラフを調査してよい。データベース収束モジュールはその後、そのメンバが各イベントに数値「ランク」を割り当てたように計算してよく、ランクは、メンバが受信した第１イベントに対して１であり、メンバが受信した第２イベントに対して２であり、以下同様である。データベース収束モジュールは、ハッシュグラフ内の各メンバにこれを行ってよい。その後、各イベントについて、データベース収束モジュールは、割り当てられたランクの中央値を計算し、それらの中央値によってイベントを分類してよい。分類は、２つの同順位イベントをそれらのハッシュの番号順に分類することなど決定的方法で、または他の何らかの方法によって同順位を打破してよく、各メンバのデータベース収束モジュールは同じ方法を用いる。この分類の結果が全順序である。
【００３９】
［１０４９］  図６は、全順序を決定するための一例のハッシュグラフ６４０を示す。ハッシュグラフ６４０は、２つのイベント（最も下の縞模様の円および最も下の点模様の円）、および各メンバがこれらのイベントの指標を受信する最初の時間（他の縞模様および点模様の円）を示す。上部における各メンバの名前は、遅い順でどのイベントが最初であるかによって色分けされる。点模様よりも縞模様の初期投票が多いので、メンバの各々に関するコンセンサス投票は縞模様である。すなわち、メンバは最終的に、縞模様のイベントが点模様のイベントより先に発生したという合意に収束する。
【００４０】
［１０５０］  この例において、メンバ（アリス、ボブ、キャロル、デイブ、およびエドと表示されたコンピュータデバイス）は、イベント６４２またはイベント６４４のどちらが最初に発生したかのコンセンサスを定めるために働く。各縞模様の円は、メンバがイベント６４４（および／またはイベント６４４の指標）を最初に受信したイベントを示す。同様に、各点模様の円は、メンバがイベント６４２（および／またはイベント６４２の指標）を最初に受信したイベントを示す。ハッシュグラフ６４０に示すように、アリス、ボブ、およびキャロルの各々は、イベント６４２より先にイベント６４４（および／またはイベント６４４の指標）を受信した。デイブおよびエドの両者は、イベント６４４（および／またはイベント６４４の指標）より先にイベント６４２（および／またはイベント６４２の指標）を受信した。したがって、イベント６４２より先にイベント６４４を受信したメンバの数が多いため、各メンバによって、イベント６４４がイベント６４２より先に発生したことを示すように全順序が決定され得る。
【００４１】
［１０５１］  他の例において、データベース収束モジュールは、ハッシュグラフ内の半順序から全順序を計算するために様々な関数を用いてよい。そのような実施形態において、たとえばデータベース収束モジュールは、全順序を計算するために以下の関数を用いてよく、ここで正の整数Ｑは、メンバによって共有されるパラメータである。
ｃｒｅａｔｏｒ（ｘ）＝イベントｘを作成したメンバ
ａｎｃ（ｘ）＝ｘ自体を含む、ｘの先駆けとなるイベントのセット
ｏｔｈｅｒ（ｘ）＝ｘが作成される直前に同期したメンバによって作成されたイベント
ｓｅｌｆ（ｘ）＝同じ作成者によるｘより前の最後のイベント
ｓｅｌｆ（ｘ，０）＝ｓｅｌｆ（ｘ）
ｓｅｌｆ（ｘ，ｎ）＝ｓｅｌｆ（ｓｅｌｆ（ｘ），ｎ−１）
ｏｒｄｅｒ（ｘ，ｙ）＝ｋ、ここでｙは、ｃｒｅａｔｏｒ（ｘ）が学んだｋ番目のイベントである
ｌａｓｔ（ｘ）＝｛ｙ｜ｙ∈ａｎｃ（ｘ）Λ¬∃ｚ∈ａｎｃ（ｘ），（ｙ∈ａｎｃ（ｚ）Λｃｒｅａｔｏｒ（ｙ）＝ｃｒｅａｔｏｒ（ｚ））｝
【数１】
0006966544.tif 000002
ｆａｓｔ（ｘ，ｙ）＝要素ｚ∈ａｎｃ（ｘ）が中央値ｓｌｏｗ（ｗ，ｚ）によって分類され、各イベントのハッシュｗ∈ｌａｓｔ（ｘ）によって引き分けが解消された、分類されたリスト内でのｙの位置
【００４２】
［１０５２］  この実施形態において、ｆａｓｔ（ｘ，ｙ）は、ｘが作成および／または定義されたほぼ直後の、ｃｒｅａｔｏｒ（ｘ）の意見における、イベントの全順序におけるｙの位置を与える。Ｑが無限である場合、上記は、先述した実施形態における全順序と同じ全順序を計算する。Ｑが有限であり、全てのメンバがオンラインである場合、上記は、先述した実施形態における全順序と同じ全順序を計算する。Ｑが有限であり、所与の時間にメンバの半数以下がオンラインである場合、この関数により、オンラインメンバは、新しいメンバが緩慢に１人ずつオンラインになる際に変わらず保たれるオンラインメンバ間でのコンセンサスに至ることができる。ただし、ネットワークのパーティションが存在する場合、各パーティションのメンバは、彼ら自身のコンセンサスに至ることができる。その後、パーティションが解消すると、より小さいパーティションのメンバは、より大きいパーティションのコンセンサスを採択する。
【００４３】
［１０５３］  また他の例において、図８、図９、および図１３Ａ〜１４Ｂに関して説明するように、データベース収束モジュールは、ハッシュグラフ内の半順序から全順序を計算するために、また異なる関数を用いてよい。図８〜９に示すように、各メンバ（アリス、ボブ、キャロル、デイブ、およびエド）は、イベント（図８に示す１４０１〜１４１３、図９に示す１５０１〜１５０６）を作成および／または定義する。図８、図９、および図１３Ａ〜１４Ｂに関して説明される関数およびサブ関数を用いて、イベントに関する全順序は、本明細書で更に詳しく説明するように、イベントをそれらの受信ラウンドによって分類すること、それらの受信タイムスタンプによって同順位を打破すること、およびそれらの署名によってこれらの同順位を打破することによって計算され得る。他の例において、イベントに関する全順序は、それらの受信ラウンドによってイベントを分類すること、それらの（受信タイムスタンプの代わりに）受信世代によって同順位を打破すること、およびそれらの署名によってこれらの同順位を打破することによって計算され得る。以下の段落は、イベントに関する順序を決定するためにイベントの受信ラウンドおよび受信世代を作成および／または定義するために用いられる関数を明示するものである。
【００４４】
［１０５４］  「親」：ＹがＸのハッシュを含む場合、イベントＸはイベントＹの親である。たとえば図８において、イベント１４１２の親は、イベント１４０６およびイベント１４０８を含む。
【００４５】
［１０５５］  「祖先」：イベントＸの祖先は、Ｘ、Ｘの親、Ｘの親の親、と続く。たとえば図８において、イベント１４１２の祖先は、イベント１４０１、１４０２、１４０３、１４０６、１４０８、および１４１２である。イベントの祖先は、そのイベントにリンクされると言ってよく、逆もしかりである。
【００４６】
［１０５６］  「子孫」：イベントＸの子孫は、Ｘ、Ｘの子、Ｘの子の子、と続く。たとえば図８において、イベント１４０１の子孫は、図に示される全てのイベントである。また他の例として、イベント１４０３の子孫は、イベント１４０３、１４０４、１４０６、１４０７、１４０９、１４１０、１４１１、１４１２、および１４１３である。イベントの子孫は、そのイベントにリンクされると言ってよく、逆もしかりである。
【００４７】
［１０５７］  「Ｎ」：母集団におけるメンバの総数である。たとえば図８において、メンバは、アリス、ボブ、キャロル、デイブ、およびエドと表示されたコンピュータであり、Ｎは５に等しい。
【００４８】
［１０５８］  「Ｍ」：Ｎの特定の割合より大きい（たとえばＮの２／３より大きい）最小の整数である。たとえば図８において、割合が２／３に定められた場合、Ｍは４に等しい。他の例において、Ｍはたとえば、Ｎの異なる割合（たとえば１／３、１／２など）、特定の所定の数、および／または他の任意の適当な方法で定められてよい。
【００４９】
［１０５９］  「自己親」：イベントＸの自己親は、同じ方法によって作成および／または定義された親イベントＹである。たとえば図８において、イベント１４０５の自己親は１４０１である。
【００５０】
［１０６０］  「自己祖先」：イベントＸの自己祖先は、Ｘ、Ｘの自己親、Ｘの自己親の自己親、と続く。
【００５１】
［１０６１］  「シーケンス番号」（または「ＳＮ」）：イベントの自己親のシーケンス番号足す１として定義される、イベントの整数属性である。たとえば図８において、イベント１４０５の自己親は１４０１である。イベント１４０１のシーケンス番号は１であるので、イベント１４０５のシーケンス番号は２（すなわち、１足す１）である。
【００５２】
［１０６２］  「世代番号」（または「ＧＮ」）：イベントの親の世代番号の最大値足す１として定義される、イベントの整数属性である。たとえば図８において、イベント１４１２は、それぞれ世代番号４および２を有する２つの親、イベント１４０６および１４０８を有する。したがってイベント１４１２の世代番号は５（すなわち、４足す１）である。
【００５３】
［１０６３］  「ラウンドインクリメント」（または「ＲＩ」）：０または１のいずれかであり得るイベントの属性である。
【００５４】
［１０６４］  「ラウンド番号」（または「ＲＮ」）：イベントの整数属性である。いくつかの例において、ラウンド番号は、イベントの親のラウンド番号の最大値足すイベントのラウンドインクリメントとして定義され得る。たとえば図８において、イベント１４１２は、２つの親であるイベント１４０６および１４０８を有し、その両方がラウンド番号１を有する。またイベント１４１２は、ラウンドインクリメント１を有する。したがって、イベント１４１２のラウンド番号は２（すなわち、１足す１）である。他の例において、イベントが、全てラウンド番号Ｒ−１を有する、異なるメンバによって定義および／または作成された少なくともＭ個のイベントを（本明細書で説明するように）強く目撃することができるように、Ｒが最小の整数である場合、ラウンド番号Ｒを有してよい。そのような整数がない場合、イベントのラウンド番号は、デフォルト値（たとえば０、１など）であってよい。そのような例において、イベントのラウンド番号は、ラウンドインクリメントを用いずに計算され得る。たとえば図８において、ＭがＮの１／２よりも大きい最小の整数であるように定義される場合、Ｍは３である。よってイベント１４１２は、各々が異なるメンバによって定義されたものでありラウンド番号１を有するＭ個のイベント１４０１、１４０２、および１４０８を強く目撃する。イベント１４１２は、異なるメンバによって定義されたラウンド番号２を有する少なくともＭ個のイベントを強く目撃することができない。したがって、イベント１４１２のラウンド番号は２である。いくつかの例において、分散型データベースにおける第１イベントは、ラウンド番号１を含む。他の例において、分散型データベースにおける第１イベントは、ラウンド番号０または他の任意の適当な番号を含んでよい。
【００５５】
［１０６５］  「分岐」：イベントＸおよびイベントＹが同じメンバによって定義および／または作成され、どちらも他方の自己祖先ではない場合、イベントＸはイベントＹの分岐である。たとえば図９において、メンバのデイブは、イベント１５０３および１５０４を生成および／または定義することによって分岐し、両方のイベントが同じ自己親（すなわちイベント１５０１）を有するので、イベント１５０３はイベント１５０４の自己祖先ではなく、イベント１５０４はイベント１５０３の自己祖先ではない。
【００５６】
［１０６６］  分岐の「識別」：分岐は、互いに分岐する２つのイベントがいずれもこれら２つのイベントの後に作成および／または定義された第３イベントの祖先である場合、第３イベントによって「識別」され得る。たとえば図９において、メンバのデイブは、どちらも他方の自己祖先ではないイベント１５０３および１５０４を作成することによって分岐する。この分岐は、イベント１５０３および１５０４がいずれもイベント１５０６の祖先であるため、後のイベント１５０６によって識別され得る。いくつかの例において、分岐の識別は、特定のメンバ（たとえばデイブ）が不正をしたことを示してよい。
【００５７】
［１０６７］  イベントの「識別」：イベントＸは、Ｘが、Ｙの分岐である祖先イベントＺを有さない場合、祖先イベントＹを「識別」または「目撃」する。たとえば図８において、イベント１４０３はイベント１４１２の祖先であり、イベント１４０３の分岐である祖先イベントをイベント１４１２が有さないため、イベント１４１２はイベント１４０３を識別する（「目撃する」とも称される）。いくつかの例において、ＸがイベントＹより前の分岐を識別しない場合、イベントＸはイベントＹを識別することができる。そのような例において、イベントＸが、イベントＹを定義するメンバによるイベントＹより後の分岐を識別しても、イベントＸはイベントＹを目撃できる。イベントＸは、分岐より後のそのメンバによるイベントを識別しない。また、メンバが、いずれもメンバの履歴内の第１のイベントである２つの異なるイベントを定義した場合、イベントＸは分岐を識別することができ、そのメンバによる任意のイベントを識別しない。
【００５８】
［１０６８］  イベントの「強い識別」（本明細書において「強い目撃」とも称される）：イベントＸは、ＸがＹを識別する場合、Ｘと同じメンバによって作成および／または定義された祖先イベントＹを「強く識別」（または「強く目撃」）する。イベントＸは、（１）ＸおよびＹの両方を含み、（２）イベントＸの祖先であり、（３）祖先イベントＹの子孫であり、（４）Ｘによって識別され、（５）各々がＹを識別することができ、（６）少なくともＭ個の異なるメンバによって作成および／または定義されたイベントのセットＳが存在する場合、Ｘと同じメンバによって作成および／または定義されていない祖先イベントＹを「強く識別」する。たとえば図８において、ＭがＮの２／３より大きい最小の整数（すなわち、Ｍ＝１＋下限（２Ｎ／３）であり、この例では４）であるように定義された場合、イベント１４０１、１４０２、１４０６、および１４１２のセットが、イベント１４１２の祖先かつイベント１４０１の子孫である少なくとも４つのイベントのセットであり、デイブ、キャロル、ボブ、およびエドの４人のメンバによってそれぞれ作成および／または定義され、イベント１４１２がイベント１４０１、１４０２、１４０６、および１４１２の各々を識別し、イベント１４０１、１４０２、１４０６、および１４１２の各々がイベント１４０１を識別するので、イベント１４１２は、祖先イベント１４０１を強く識別する。同様に述べると、Ｘが、各々がＹを目撃することができる、異なるメンバによって作成または定義された少なくともＭ個のイベント（たとえばイベント１４０１、１４０２、１４０６、および１４１２）を目撃することができる場合、イベントＸ（たとえばイベント１４１２）はイベントＹ（たとえばイベント１４０１）を「強く目撃」することができる。
【００５９】
［１０６９］  「ラウンドＲ第１」イベント（本明細書において「目撃者」とも称される）：イベントが（１）ラウンド番号Ｒを有し、（２）Ｒよりも小さいラウンド番号を有する自己親を有するか、または自己親を有さない場合、そのイベントは「ラウンドＲ第１」イベント（または「目撃者」）である。たとえば図８において、イベント１４１２は、ラウンド番号２を有し、その自己親が（２よりも小さい）ラウンド番号１を有するイベント１４０８であるため、「ラウンド２第１」イベントである。
【００６０】
［１０７０］  いくつかの例において、イベントＸのラウンドインクリメントは、Ｘが少なくともＭ個の「ラウンドＲ第１」イベントを「強く識別」する場合かつその場合に限り、１と定義され、ここでＲはＸの親の最大ラウンド番号である。たとえば図８において、ＭがＮの１／２よりも大きい最小の整数に定義された場合、Ｍは３である。よってイベント１４１２は、Ｍ個のイベント１４０１、１４０２、および１４０８を強く識別し、それらすべてがラウンド１第１イベントである。１４１２の両方の親がラウンド１であり、１４１２が少なくともＭ個のラウンド１第１を強く識別するので、１４１２のラウンドインクリメントは１である。図内の「ＲＩ＝０」と記されたイベントの各々は、少なくともＭ個のラウンド１第１を強く識別できないので、それらのラウンドインクリメントは０である。
【００６１】
［１０７１］  いくつかの例において、以下の方法は、イベントＸが祖先イベントＹを強く識別できるかを決定するために用いられ得る。各ラウンドＲ第１祖先イベントＹに関して、メンバごとに１つ、整数のアレイＡ１を保持し、イベントＸの最小シーケンス番号を付与するものとし、その場合、そのメンバがイベントＸを作成および／または定義し、ＸがＹを識別できる。各イベントＺに関して、ＺがＹを識別できるように、メンバごとに１つ、整数のアレイＡ２を保持し、そのメンバによって作成および／または定義されたイベントＷの最大シーケンス番号を付与するものとする。Ｚが祖先イベントＹを強く識別できるかを決定するために、Ａ１［Ｅ］≦Ａ２［Ｅ］であるように要素位置Ｅの数をカウントする。イベントＺは、このカウントがＭより大きい場合かつその場合に限り、Ｙを強く識別することができる。たとえば図８において、メンバのアリス、ボブ、キャロル、デイブ、およびエドの各々はイベント１４０１を識別することができ、これが可能である最初のイベントは、それぞれイベント｛１４０４、１４０３、１４０２、１４０１、１４０８｝である。これらのイベントは、Ａ１＝｛１、１、１、１、１｝のシーケンス番号を有する。同様に、イベント１４１２によって識別される各人による最後のイベントは、イベント｛ＮＯＮＥ、１４０６、１４０２、１４０１、１４１２｝であり、１４１２はアリスによるイベントをどれも識別することができないので、アリスは「ＮＯＮＥ」と記載される。これらのイベントは、それぞれＡ２＝｛０、２、１、１、２｝のシーケンス番号を有し、全てのイベントが正のシーケンス番号を有するので、０は、アリスが１４１２によって識別されるイベントを有さないことを意味する。リストＡ１とリストＡ２とを比較すると、｛１≦０、１≦２、１≦１、１≦１、１≦２｝という結果がもたらされ、これは｛偽、真、真、真、真｝に等しく、４つの真の値を有する。したがって、１４１２の祖先であり１４０１の子孫である４つのイベントのセットＳが存在する。４はＭ以上であるため、１４１２は１４０１を強く識別する。
【００６２】
［１０７２］  Ａ１およびＡ２によって、イベントＸが祖先イベントＹを強く識別できるかを決定するための方法の実装に関するまた他の変形例は、以下のとおりである。両方のアレイにおける整数要素が１２８未満である場合、各要素を１バイトに格納し、そのような要素を１つの６４ビットワードにパックし、Ａ１およびＡ２をそのようなワードのアレイとすることが可能である。Ａ１における各バイトの最上位ビットは０に設定され、Ａ２における各バイトの最上位ビットは１に設定され得る。２つの対応するワードを引き、最上位ビットを除いて全てのゼロに対しマスクを有するビットごとのＡＮＤを実行し、その後、７ビット位置だけ右シフトし、Ｃプログラミング言語で（（Ａ２［ｉ］‐Ａ１［ｉ］）＆０ｘ８０８０８０８０８０８０８０８０）＞＞７）と表される値を得る。これは、ゼロに初期化された実行時アキュムレータＳに加えられ得る。これを複数回行った後、バイトをシフトおよび加算することによってアキュムレータをカウントに変換し、（（Ｓ＆０ｘｆｆ）＋（（Ｓ＞＞８）＆０ｘｆｆ）＋（（Ｓ＞＞１６）＆０ｘｆｆ）＋（（Ｓ＞＞２４）＆０ｘｆｆ）＋（（Ｓ＞＞３２）＆０ｘｆｆ）＋（（Ｓ＞＞４０）＆０ｘｆｆ）＋（（Ｓ＞＞４８）＆０ｘｆｆ）＋（（Ｓ＞＞５６）＆０ｘｆｆ））が得られる。いくつかの例において、これらの計算は、たとえばＣ、Ｊａｖａなどのプログラミング言語で実行され得る。他の例において、計算は、たとえばＩｎｔｅｌ社およびＡＭＤ社によって供給されるＡｄｖａｎｃｅｄ  Ｖｅｃｔｏｒ  Ｅｘｔｅｎｓｉｏｎｓ（ＡＶＸ）命令などのプロセッサ固有命令、またはグラフィック処理ユニット（ＧＰＵ）または汎用グラフィック処理ユニット（ＧＰＧＰＵ）における均等物を用いて実行され得る。いくつかのアーキテクチャにおいて、計算は、たとえば１２８、２５６、５１２ビット、またはそれ以上など、６４ビットより大きいワードを用いて高速で実行され得る。
【００６３】
［１０７３］  「有名な」イベント：ラウンドＲイベントＸは、（１）イベントＸが「ラウンドＲ第１」イベント（または「目撃者」）であり、（２）後述するように、ビザンチン合意プロトコルの実行によって「ＹＥＳ」の決定が下った場合、「有名」である。いくつかの実施形態において、ビザンチン合意プロトコルは、分散型データベースのインスタンス（たとえば分散型データベースインスタンス１１４）および／またはデータベース収束モジュール（たとえばデータベース収束モジュール２１１）によって実行され得る。たとえば図８において、５つのラウンド１第１である１４０１、１４０２、１４０３、１４０４、および１４０８が示される。ＭがＮの１／２よりも大きい最小の整数に定義された場合、Ｍは３であり、１４１２はラウンド２第１である。プロトコルがより長く動作する場合、ハッシュグラフは上向きに成長し、最終的に、他の４人のメンバもまた、この図の最上部より上にラウンド２第１を有する。各ラウンド２第１は、ラウンド１第１の各々が「有名」であるかに関する「投票権」を有する。イベント１４１２は、自身が識別できるラウンド１第１が１４０１、１４０２、および１４０３であるため、それらが有名であることに対しＹＥＳを投票する。イベント１４１２は、１４０４を識別できないため、１４０４が有名であることに対しＮＯを投票する。たとえば１４０２など所与のラウンド１第１に関し、それが「有名」であるか否かの状態は、それが有名であるか否かに関する各ラウンド２第１の投票を計算することによって決定される。これらの投票はその後、最終的に１４０２が有名であったかに関する同意が得られるまで、ラウンド３第１へ、次にラウンド４第１へと、以下同様に伝搬する。同じプロセスが他の第１について繰り返される。
【００６４】
［１０７４］  ビザンチン合意プロトコルは、「有名なイベント」を識別するために、「ラウンドＲ第１」イベントの投票および／または決定を収集し、用いてよい。たとえば、「ラウンドＲ＋１第１の」Ｙは、ＹがイベントＸを「識別」することができる場合、「ＹＥＳ」を投票し、そうでない場合、「ＮＯ」を投票する。投票はその後、任意のメンバによって決定が下されるまで、Ｇ＝Ｒ＋２、Ｒ＋３、Ｒ＋４などである各ラウンドＧに関して計算される。決定が下されると、各ラウンドＧに関して投票が計算される。これらのラウンドのいくつかは、「多数決」ラウンドであってよく、他のいくつかは、「コイン」ラウンドであってよい。いくつかの例において、たとえばラウンドＲ＋２は多数決ラウンドであり、今後のラウンドは、（たとえば既定のスケジュールに従って）多数決ラウンドまたはコインラウンドのいずれかとして指定される。たとえばいくつかの例において、今後のラウンドが多数決ラウンドであるかコインラウンドであるかは、２つの連続したコインラウンドが存在し得ないという条件の下、任意に決定され得る。たとえば、５つの多数決ラウンドが存在し、次に１つのコインラウンド、次に５つの多数決ラウンド、次に１つのコインラウンド、といったように合意に達するまでの間繰り返されることが既定され得る。
【００６５】
［１０７５］  いくつかの例において、ラウンドＧが多数決ラウンドである場合、投票は、以下のように計算され得る。Ｖを投票する少なくともＭ個のラウンドＧ−１第１を強く識別するラウンドＧイベントが存在する場合（ここでＶは「ＹＥＳ」または「ＮＯ」のいずれかである）、コンセンサス決定はＶであり、ビザンチン合意プロトコルは終了する。他の場合、各ラウンドＧ第１イベントは、各ラウンドＧ第１イベントが強く識別し得るラウンドＧ−１第１の過半数である新たな投票を計算する。過半数ではなく引き分けが存在する例において、投票は、「ＹＥＳ」と指定され得る。
【００６６】
［１０７６］  同様に述べると、ＸがラウンドＲ目撃者（またはラウンドＲ第１）である場合、ラウンドＲ＋１、Ｒ＋２、以下同様における投票結果が計算されてよく、各ラウンドにおける目撃者は、Ｘが有名であるかに関して投票する。ラウンドＲ＋１において、Ｘを目撃することができる全ての目撃者がＹＥＳを投票し、その他の目撃者はＮＯを投票する。ラウンドＲ＋２において、全ての目撃者は、自身が強く目撃することができるラウンドＲ＋１目撃者の投票の過半数に従って投票する。同様に、ラウンドＲ＋３において、全ての目撃者は、自身が強く目撃することができるラウンドＲ＋２目撃者の投票の過半数に従って投票する。これが複数ラウンド継続し得る。引き分けの場合、投票はＹＥＳに設定され得る。他の例において、引き分けはＮＯに設定されてよく、あるいはランダムに設定され得る。任意のラウンドが、ＮＯを投票する少なくともＭ個の目撃者を有する場合、選挙は終了し、Ｘは有名ではない。任意のラウンドが、ＹＥＳを投票する少なくともＭ個の目撃者を有する場合、選挙は終了し、Ｘは有名である。ＹＥＳまたはＮＯのどちらも少なくともＭ個の票を有さない場合、選挙は次のラウンドに継続する。
【００６７】
［１０７７］  例として、図８において、図の下側に示される何らかのラウンド第１イベントＸを考える。この時、各ラウンド１第１は、Ｘが有名であるかに関する票を有する。イベント１４１２は、ラウンド１第１イベント１４０１、１４０２、および１４０８を強く識別することができる。よってイベント１４１２は、それらの投票に基づいて投票する。これが多数決ラウンドである場合、１４１２は、｛１４０１、１４０２、１４０８｝のＭ個以上がＹＥＳの票を有するかを確かめる。そうである場合、決定はＹＥＳであり、合意が実現される。それらのＭ個以上がＮＯを投票する場合、決定はＮＯであり、合意が実現されない。投票結果がいずれの方向にもＭ個以上を有さない場合、１４１２は、１４０１、１４０２、および１４０８の投票の過半数である票を与えられる（引き分けであった場合、ＹＥＳを投票することにより引き分けを解消する）。その投票はその後、次のラウンドで用いられ、合意に至るまで継続する。
【００６８】
［１０７８］  いくつかの例において、ラウンドＧがコインラウンドである場合、投票結果は以下のように計算され得る。イベントＸが、Ｖ（Ｖは「ＹＥＳ」または「ＮＯ」のいずれかである）を投票するＭ個以上のラウンドＧ−１第１を識別することができる場合、イベントＸは自身の投票をＶに変更する。そうでない場合、ラウンドＧがコインラウンドである場合、各ラウンドＧ第１イベントＸは、自身の投票を、イベントＸのシグネチャの最下位ビットと定義される、（いくつかの例におけるコインフリップと同様の）疑似ランダム決定の結果に変更する。
【００６９】
［１０７９］  同様に述べると、そのような例において、選挙がラウンドＲ＋Ｋ（コインラウンド）に到達すると、選挙は、そのラウンドで終了せず、ここでＫは指定の係数（たとえば、３、６、７、８、１６、３２などの数または他の任意の適当な数の倍数）である。選挙は、このラウンドに到達すると、少なくとも更に１ラウンド継続し得る。そのようなラウンドにおいて、イベントＹがラウンドＲ＋Ｋの目撃者であり、Ｖを投票するラウンドＲ＋Ｋ−１からのＭ個以上の目撃者を強く目撃することができる場合、ＹはＶを投票する。そうでない場合、Ｙはランダムな値に従って（たとえば、１＝ＹＥＳかつ０＝ＮＯ、またはその逆であるイベントＹのシグネチャのビット（たとえば最下位ビット、最上位ビット、ランダムに選択されたビット）に従って、イベントＹのタイムスタンプに従って、暗号「共有コイン」プロトコルおよび／または他の任意のランダムな決定を用いて）投票する。このランダムな決定は、Ｙが作成される前に予測不可能であるので、イベントおよび合意プロトコルの安全性を高めることができる。
【００７０】
［１０８０］  たとえば図８において、ラウンド２がコインラウンドであり、ラウンド１より前の何らかのイベントが有名であったかに関して投票する場合、イベント１４１２は最初に、｛１４０１、１４０２、１４０８｝のうちＭ個以上がＹＥＳと投票したかＮＯと投票したかを確かめる。そのような場合、１４１２は同様に投票をする。どちらにもＭ個以上が投票していない場合、１４１２は、（たとえば、エドがイベント１４１２を作成および／または定義した時、これに署名した時にイベント１４１２のために作成したデジタルシグネチャの最下位ビットに基づいて）ランダムまたは疑似ランダム投票をする。
【００７１】
［１０８１］  いくつかの例において、疑似ランダム決定の結果は、たとえばラウンド番号の閾値シグネチャの最下位ビットとして実装され得る暗号共有コインプロトコルの結果であってよい。
【００７２】
［１０８２］  システムは、上述した疑似ランダム決定の結果を計算するための方法のいずれか１つによって構築され得る。いくつかの例において、システムは、様々な方法を何らかの順序でサイクルする。他の例において、システムは、既定のパターンに従って様々な方法の中から選択してよい。
【００７３】
［１０８３］  「受信ラウンド」：イベントＸは、Ｒが、ラウンド番号Ｒを有する有名なラウンドＲの第１イベント（または有名な目撃者）の少なくとも半分がＸの子孫である、および／またはＸを目撃できるような最小整数である場合、Ｒの「受信ラウンド」を有する。他の例において、他の任意の適当な割合が用いられ得る。たとえば他の例において、イベントＸは、Ｒが、ラウンド番号Ｒを有する有名なラウンドＲ第１イベント（または有名な目撃者）の所定の割合（たとえば４０％、６０％、８０％など）以上がＸの子孫である、および／またはＸを目撃できる場合、イベントＸはＲの「受信ラウンド」を有する。
【００７４】
［１０８４］  いくつかの例において、イベントＸの「受信世代」は、以下のように計算され得る。イベントＸを識別できる各ラウンドＲの第１イベントをどのメンバが作成および／または定義したかを求める。次に、Ｘを識別できるそのメンバによる最初のイベントの世代番号を決定する。次に、Ｘの「受信世代」を、そのリストの中央値として定義する。
【００７５】
［１０８５］  いくつかの例において、イベントＸの「受信タイムスタンプ」Ｔは、Ｘを識別および／または目撃する、各メンバによる第１イベントを含むイベントにおけるタイムスタンプの中央値であってよい。たとえば、イベント１４０１の受信タイムスタンプは、イベント１４０２、１４０３、１４０３、および１４０８に関するタイムスタンプの値の中央値であってよい。いくつかの例において、イベント１４０１のタイムスタンプが中央値の計算に含まれ得る。他の例において、Ｘに関する受信タイムスタンプは、Ｘを識別または目撃する各メンバによる第１イベントであるイベントにおけるタイムスタンプの値の組み合わせ、または他の任意の値であってよい。たとえばＸに関する受信タイムスタンプは、タイムスタンプの平均、タイムスタンプの標準偏差、（たとえば計算から最初および最後のタイムスタンプを取り除くことによって）修正された平均などに基づいてよい。また他の例において、拡張中央値が用いられ得る。
【００７６】
［１０８６］  いくつかの例において、イベントに関する全順序および／またはコンセンサス順序は、それらの受信ラウンドによってイベントを分類すること、それらの受信タイムスタンプによって引き分けを解消すること、それらのシグネチャによってそれらの引き分けを解消することによって計算される。他の例において、イベントに関する全順序は、それらの受信ラウンドによってイベントを分類すること、それらの受信世代によって引き分けを解消すること、およびそれらのシグネチャによってそれらの引き分けを解消することによって計算され得る。以下の段落は、イベントの受信ラウンド、受信タイムスタンプ、および／または受信世代を計算および／または定義するために用いられる関数を明示する。
【００７７】
［１０８７］  他の例において、各イベントのシグネチャを用いる代わりに、同じ受信ラウンドおよび／またはそのラウンド内の受信世代を有する有名なイベントまたは有名な目撃者のシグネチャを有するイベントＸＯＲｅｄのシグネチャが用いられ得る。他の例において、イベントシグネチャの他の任意の適当な組み合わせが、引き分けを解消してイベントのコンセンサス順序を定めるために用いられ得る。
【００７８】
［１０８８］  また他の例において、リストの中央値として「受信世代」を定義する代わりに、「受信世代」がリスト自体として定義され得る。よって、受信世代によって分類する場合、２つの受信世代がそれらのリストの中央要素によって比較されてよく、中央値の直前の要素によって引き分けを解消し、中央値の直後の要素によってこれらの引き分けを解消し、引き分けが解消されるまで、これまで用いられた要素より前の要素と後の要素とを交互に繰り返すことによって継続する。
【００７９】
［１０８９］  いくつかの例において、中央タイムスタンプの代わりに「拡張中央値」が用いられ得る。そのような例において、単一の受信タイムスタンプではなく、タイムスタンプのリストが各イベントに関して定義され得る。イベントＸに関するタイムスタンプのリストは、Ｘを識別および／または目撃する各メンバによる第１イベントを含んでよい。たとえば図８において、イベント１４０１に関するタイムスタンプのリストは、イベント１４０２、１４０３、１４０３、および１４０８のタイムスタンプを含んでよい。いくつかの例において、イベント１４０１のタイムスタンプも含まれ得る。タイムスタンプのリストを用いて引き分けを解消する（すなわち、２つのイベントが同じ受信ラウンドを有する）場合、各イベントのリストの中央タイムスタンプ（または二等分できる長さの場合、２つの中央タイムスタンプの所定の第１または第２のタイムスタンプ）が比較され得る。これらのタイムスタンプが同じである場合、中央タイムスタンプの直後のタイムスタンプが比較され得る。これらのタイムスタンプが同じである場合、中央タイムスタンプの直前のタイムスタンプが比較され得る。これらのタイムスタンプもまた同じである場合、３つの既に比較されたタイムスタンプより後のタイムスタンプが比較される。これを、引き分けが解消されるまで交互に繰り返し続けてよい。上記と同様に、２つのリストが同じである場合、２つの要素のシグネチャによって引き分けが解消され得る。
【００８０】
［１０９０］  また他の例において、「拡張中央値」の代わりに「短縮された拡張中央値」が用いられ得る。そのような例において、タイムスタンプのリスト全体が各イベントについて格納されるのではない。代わりに、リストの中央付近のいくつかの値のみが格納され、比較のために用いられる。
【００８１】
［１０９１］  受信された中央タイムスタンプは、イベントの全順序の計算に加えて他の目的に用いられる可能性がある。たとえば、ボブは、彼がその契約により結ばれることに同意すると述べる契約に、アリスが同じ契約に署名した取引を含むイベントＸが存在する場合かつその場合に限り、特定のデッドライン上またはその前にあるＸに関する受信タイムスタンプによって署名し得る。そのような場合、ボブは、上述したように「受信中央タイムスタンプ」によって示されたようなデッドラインより後にアリスが署名した場合、契約によって結ばれない。
【００８２】
［１０９２］  いくつかの例において、分散型データベースの状態は、コンセンサスが実現された後に定義され得る。たとえば、Ｓ（Ｒ）が、ラウンドＲにおける有名な目撃者によって目撃され得るイベントのセットである場合、Ｓ（Ｒ）内の全てのイベントが最終的に、既知の受信ラウンドおよび受信タイムスタンプを有する。その時点で、Ｓ（Ｒ）内のイベントのコンセンサス順序は既知であり、変化しない。この時点に到達すると、メンバは、イベントおよびそれらの順序の表現を計算および／または定義してよい。たとえばメンバは、Ｓ（Ｒ）内のイベントのハッシュ値をそれらのコンセンサス順序において計算してよい。メンバはその後、ハッシュ値にデジタル署名し、そのメンバが定義する次のイベントにハッシュ値を含めてよい。これは、そのメンバが、Ｓ（Ｒ）内のイベントが変化しない所与の順序を有すると決定したことを、他のメンバに通知するために用いられ得る。メンバのＭ人以上（または他の任意の適当な数またはパーセンテージのメンバ）がＳ（Ｒ）のハッシュ値に署名（かつ、それに伴いハッシュ値によって表される順序に合意）した後、メンバのシグネチャのリストとともにイベントのコンセンサスリストは、コンセンサス順序がＳ（Ｒ）内のイベントに関して主張されるものであったことを証明するために用いられ得る単一のファイル（または他のデータ構造）を形成してよい。他の例において、イベントが、（本明細書で説明されるような）分散型データベースシステムの状態を更新する取引を含む場合、ハッシュ値は、Ｓ（Ｒ）内のイベントの取引をコンセンサス順序で適用した後の分散型データベースシステムの状態に関するものであってよい。
【００８３】
［１０９３］  いくつかの例において、（上述したような）Ｍは、単にメンバの総数の分数、百分率、および／または値ではなく、各メンバに割り当てられた重み値に基づいてよい。そのような例において、各メンバは、分散型データベースシステムにおける関心および／または影響に関連するステークを有する。そのようなステークが重み値であってよい。そのメンバによって定義された各イベントは、これを定義するメンバの重み値を有すると言える。よってＭは、全メンバの合計ステークの分数であってよい。Ｍに依存するものとして上述されたイベントは、Ｍ以上のステーク総和を有するメンバのセットが合意した場合、発生する。したがって特定のメンバは、自身のステークに基づいて、システム、およびコンセンサス順序がどのように導出されるかに対してより大きな影響力を有し得る。いくつかの例において、イベント内の取引は、１または複数のメンバのステークを変更し、新たなメンバを追加し、および／またはメンバを削除してよい。そのような取引がラウンドＲを受信した場合、受信ラウンドが計算された後、ラウンドＲ目撃者の後のイベントは、修正されたステークおよび修正されたメンバリストを用いて自身のラウンド番号および他の情報を再計算する。ラウンドＲイベントが有名であるかに関する投票は、古いステークおよびメンバリストを用いるが、Ｒより後のラウンドに関する投票は、新たなステークおよびメンバリストを用いる。コンセンサスを決定するために重み値を用いることに関する追加の細部は、参照によってその全体が本願に組み込まれる、２０１６年１２月２１日に出願された“Ｍｅｔｈｏｄｓ  Ａｎｄ  Ａｐｐａｒａｔｕｓ  Ｆｏｒ  Ａ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｄａｔａｂａｓｅ  Ｗｉｔｈ  Ｃｏｎｓｅｎｓｕｓ  Ｄｅｔｅｒｍｉｎｅｄ  Ｂａｓｅｄ  Ｏｎ  Ｗｅｉｇｈｔｅｄ  Ｓｔａｋｅｓ”と題された米国特許出願第１５／３８７，０４８号において説明される。
【００８４】
［１０９４］  図２において、データベース収束モジュール２１１および通信モジュール２１２は、プロセッサ２１０内に実装されるものとして示される。他の実施形態において、データベース収束モジュール２１１および／または通信モジュール２１２は、メモリ２２０内に実装され得る。また他の例において、データベース収束モジュール２１１および／または通信モジュール２１２は、ハードウェアベース（たとえばＡＳＩＣ、ＦＰＧＡなど）であってよい。
【００８５】
［１０９５］  いくつかの例において、（たとえば図１に関して図示および説明される）分散型データベースは、「代理取引」の処理を可能にしてよい。いくつかの例において、そのような代理取引は、分散型データベースの非メンバ（たとえば、分散型データベースのインスタンスを有さないコンピュータデバイス）の代理となる分散型データベースのメンバ（たとえば、分散型データベースの少なくとも一部のインスタンスを有するコンピュータデバイス）、全権利未満を有する（たとえば、読取権利を有するが書込み権利を有さない、コンセンサス決定に関与しないなどの）分散型データベースのメンバなどによって実行され得る。たとえば、アリスが分散型データベースに取引ＴＲを提起したいが、彼女は分散型データベースの完全メンバではない（たとえば、アリスはメンバではない、または限られた権利を有する）ものとする。ボブは完全メンバであり、分散型データベースにおける全権利を有するものとする。この場合、アリスは取引ＴＲをボブへ送信し、ボブが、分散型データベースに影響するように取引ＴＲをネットワークに提起してよい。いくつかの例において、アリスはＴＲにデジタル署名してよい。いくつかの例において、ＴＲはたとえば、ボブへの支払い（たとえば、分散型データベースにＴＲを提起するボブのサービスに対する料金）を含んでよい。いくつかの例においてアリスは、ボブまたは他の観察者が、ＴＲがアリスから到来したことを決定することができないように、たとえばＴＯＲオニオンルーティングネットワークなどの匿名化ネットワークを介してボブへＴＲを通信してよい。
【００８６】
［１０９６］  いくつかの例において、（たとえば、図１に関して図示および説明された）分散型データベースは、暗号通貨を実装するために用いられ得る。そのような例において、各分散型データベースインスタンス１１４、１２４、１３４、１４４は、暗号通貨を格納するための１または複数の（本明細書においてウォレットとも称される）ウォレットデータ構造を定義してよい。ウォレットデータ構造は、鍵ペア（公開鍵および秘密鍵）を含んでよい。いくつかの例において、ウォレットの鍵ペアは、そのウォレットが発祥するコンピュータデバイスによって生成され得る。たとえばアリスがウォレット（Ｗ，Ｋ）を定義し、Ｗが（ウォレットの識別子としても機能し得る）公開鍵であり、Ｋが秘密鍵である場合、アリスは、分散型データベースの他のインスタンス（またはそれらのユーザ）が、ウォレットＷがアリスに関連することを識別できないように、分散型データベースの残りのインスタンスへＷを（たとえばイベント内で）公開しながらも自身のアイデンティティ匿名性を維持することができる。ただしいくつかの例において、暗号通貨の譲渡は公開である。したがって、アリスの雇用主が（たとえばイベント内の取引を用いて）Ｗへ金銭を譲渡し、後にアリスが（たとえば異なるイベント内の異なる取引を用いて）Ｗから店舗へ金銭を譲渡することによって購買を行う場合、雇用主および店舗は、Ｗがアリスに属すること、および購買を行ったのがアリスであることを、結託して決定することができる。したがって、これを回避するために、アリスにとって、自身の取引匿名性を維持するために新たな匿名ウォレットへ金銭を譲渡することが有利であり得る。
【００８７】
［１０９７］  いくつかの実装において、ＷＡＬＬＥＴ＿ＡＤＤ動作は、分散型データベースにペア（Ｗ，Ｄ）を格納するために用いられ、ＷＡＬＬＥＴ＿ＤＥＬは、ウォレットを削除するために用いられ得る。いくつかの例において、ユーザは、料金を支払うことによって分散型データベースにウォレットを追加することができ、そのようなウォレットは、支払われた料金によって保証される時間、分散型データベース内でアクティブに保たれ得る。ペア（Ｗ，Ｄ）内のパラメータＷは、ウォレットの公開鍵に対応し、パラメータＤは、各々が秘密鍵に対応する公開鍵のリストを含み得るデータ構造であり、そのような秘密鍵のいずれかは、たとえばＷＡＬＬＥＴ＿ＤＥＬ動作に署名するために用いられ得る。他の例において、そのような秘密鍵の任意の十分大きいセットが、ＷＡＬＬＥＴ＿ＤＥＬ動作に署名するために用いられ得る。たとえばそのような例において、ＷＡＬＬＥＴ＿ＤＥＬに署名するそのような秘密鍵の数は、所定の閾値を上回らなければならない。
【００８８】
［１０９８］  他の実装において、ＷＡＬＬＥＴ＿ＡＤＤ（Ｗ，Ｄ）は、公開鍵Ｗにデジタル証明書を追加および／または結合する動作または機能であってよい。デジタル証明書は、証明書の主体および証明書を使用できるアプリケーションおよびサービスに関する情報を提供することによって、ユーザ、コンピュータ、またはサービスのアイデンティティを公開鍵に結合する電子クレデンシャルである。したがっていくつかの例において、データ構造Ｄは、Ｗの公開鍵証明書（たとえばＸ．５０９証明書）、および公開鍵Ｗからの証明書を解くことが許可される公開鍵のリストを含んでよい。そのようなリスト内の公開鍵は、Ｗと、公開鍵証明書の連鎖内の鍵との両方を含み得る。
【００８９】
［１０９９］  メンバ、たとえばアリスは、ＷＡＬＬＥＴ＿ＡＤＤ（Ｗ，Ｄ）動作によって新たなウォレットを作成および／または定義することができる。そのようなウォレットは、公開鍵Ｗを含む。デフォルトで、新たに作成されたウォレットは、ウォレットをメンバのアリス（すなわち、アリスと表されるコンピュータデバイス）にリンクするものがウォレット内にないため匿名である。また分散型データベースによってメンバは、たとえばマネーロンダリング動作、脱税を防止し、顧客熟知（ＫＹＣ）法または他の適当なポリシや慣例に準拠するために非匿名ウォレットを作成することもできる。したがって、アリスおよび分散型データベースの他のメンバは、（１）メンバのアイデンティティ（たとえばアリスのアイデンティティ）を検証し、ウォレットＷにメンバを結び付ける証明書（たとえばＸ．５０９証明書）を取得するために、信頼された認証局（ＣＡ）を用いる、および／または（２）メンバのアイデンティ（たとえばアリス）を検証し、そのようなメンバによって作成されたアイデンティティエスクローファイル（ＩＥＦ）のブラインドシグネチャを実行し、ＩＥＡの署名鍵の証明書（たとえばＸ．０５９証明書）を取得するために、信頼されたアイデンティティエスクロー局（ＩＥＡ）を用いることができる。
【００９０】
［１１００］  いくつかの例において、分散型データベースのメンバは、たとえば動作ＷＡＬＬＥＴ＿ＡＤＤ（Ａ，Ｄ）を用いて、ＣＡまたはＩＥＦによって作成された証明書Ｄをウォレットに添付し、動作ＷＡＬＬＥＴ＿ＤＥＬ（Ａ，Ｄ）を用いて、そのような証明書を最終的に削除することができる。そのような場合、証明書連鎖は、証明書を発行したＣＡまたはＩＥＡまで拡大し、および／または、ＣＡまたはＩＥＡが分散型データベース内で用いられることを承認する機関、たとえば政府機関または他の適当な機関までさらに拡大し得る。
【００９１】
［１１０１］  いくつかの例において、分散型データベースを通して実行される取引がＫＹＣ法またはポリシに準拠する必要がある場合、ウォレット、銀行口座、および／または商品およびサービスの個人販売者の間の取引は、ＣＡによって発行される証明書の検証後に実行され得る。そのような場合、証明書連鎖は、ＣＡを承認した機関（たとえば政府機関）まで拡大し得る。したがって、そのような取引は、その機関によって追跡され得る。いくつかの例において、ユーザは、料金を支払うことによってウォレットに証明書を結合してよく、そのようなウォレットは、支払った料金によって保証される時間、分散型データベース内でアクティブに保たれ得る。
【００９２】
［１１０２］  いくつかの例において、分散型データベースを通して実行される取引は、ＫＹＣ法またはポリシおよびプライバシー法またはポリシに準拠してよい。そのような例において、たとえば、商品およびサービスの個人販売者と取引とは、ＩＥＡによって発行される証明書の検証後に実行され得る。そのような場合、証明書連鎖は、ＩＥＡを承認した機関まで拡大し得る。たとえばＩＥＦは、ＩＥＡを承認した機関によって所有される公開鍵によって暗号化された、Ｗおよびユーザの氏名および住所を含んでよい。したがって、そのような機関は、Ｗおよびユーザの氏名および住所に対応するフィールドを復号し、ウォレットの所有者を識別することができる。ただしユーザのアイデンティティは、分散型データベースまたは他の機関の他のメンバおよび／またはユーザにはアクセス不可能である。
【００９３】
［１１０３］  いくつかの例において、たとえばメンバは、複数のランダムなウォレット（たとえば１００のランダムなウォレット）を作成および／または定義し、それらが対応するアイデンティティエスクローファイル（たとえば１００のファイル）のブライドバージョンをＩＥＡへ送信し、その後、ＩＥＡによってランダムに選択されたそれらのファイル（たとえば９９のファイル）のサブセットのブラインドをはずし復号するためにＩＥＡへ情報を送信してよい。そのようなメンバは、９９のファイルに関連付けられた９９のウォレットを破棄し、残りのアイデンティティエスクローファイルのブラインドシグネチャをＩＥＡから受信してよい。メンバはその後、残りのアイデンティティエスクローファイルのブラインドをはずし、それを残りのウォレットに添付してよい。したがって、ＩＥＡは、そのようなメンバが、預託されたアイデンティティを残りのウォレットに添付していることを請け負ってよい。このようにメンバは、ＩＥＡからのプライバシーを有してよく、ＩＥＡを承認する機関のみが、預託された情報へのアクセス権を有してよい。
【００９４】
［１１０４］  いくつかの例において、たとえば国または他の団体がプライバシー法的枠組みを有する場合、アイデンティティエスクローファイルを復号するための単一の鍵を有するのではなく、政府または他の団体が、メンバのアイデンティティを復号するために協働するいくつかの機関を有し得る（たとえば、各機関および／または団体が、アイデンティティエスクローファイルを復号するために鍵の他の部分と組み合わせられる鍵の一部を有する）ように、システムは更に強化され得る。したがって、合意または協働動作は、メンバのアイデンティティを開示するために複数の機関にわたり行われ得る。よって、分散型データベースは、分散型データベースのメンバまたはユーザのプライバシーと、分散型データベースを介して実行される取引の透明性との間で均衡のとれたトレードオフを等しく提供し得るツールとして働く。また、アイデンティティエスクローファイルを復号するための単一の鍵を分割することにより、分散型データベースを実装するコンピュータデバイスの安全性およびプライバシーが向上する。
【００９５】
［１１０５］  以下の例は、次の取引が（たとえばイベント内で）発行された場合、Ｃ個の暗号通貨コインがウォレットＷからウォレットＲへ譲渡されることを想定し、ここで、最後の＿Ｋは、取引が秘密鍵Ｋによってデジタル署名されることを意味する。次の表記が用いられ得る。
ＴＲＡＮＳＦＥＲ（Ｃ，Ｗ，Ｒ）＿Ｋ
【００９６】
［１１０６］  いくつかの例において、暗号通貨の譲渡における匿名性を実現するために、新たな取引類型および／または分散型データベース機能が定められ得る。たとえば、以下の取引は、Ｃ１個のコインをウォレットＷ１からウォレットＲ１へ移動し、Ｃ２個のコインをウォレットＷ２からウォレットＲ２へ移動する。いくつかの例において、本明細書で更に詳しく説明するように、たとえばウォレットＷ１およびＲ１は、分散型データベースの第１のインスタンスに関連し、ウォレットＷ２およびＲ２は、分散型データベースの第２のインスタンスに関連してよい。いくつかの例において、取引は、それらを接続するために機能する任意の識別子Ｎ（たとえば会話識別子および／またはプロセス識別子）を含んでよい。
ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ（Ｎ，  Ｃ１，Ｗ１，Ｒ１，  Ｃ２，Ｗ２，Ｒ２，  Ｔ）＿Ｋ１
ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ（Ｎ，  Ｃ１，Ｗ１，Ｒ１，  Ｃ２，Ｗ２，Ｒ２，  Ｔ）＿Ｋ２
【００９７】
［１１０７］  いくつかの例において、これらの取引は、一方が（公開鍵Ｗ１に関連する秘密鍵を用いて）Ｋ１によって署名され、他方が（公開鍵Ｗ２に関連する秘密鍵を用いて）Ｋ２によって署名された２つの同一コピーが発行され、分散型データベースの他のインスタンスへ（たとえば１または複数のイベント内で）拡散されない限り、効果を有さない。いくつかの例において、各取引は、上述したように安全タイムスタンプも含んでよい。この安全タイムスタンプは、取引が関連するイベントの安全タイムスタンプまたは取引の個別の安全タイムスタンプであってよい。両方の取引が互いのＴ秒以内のタイムスタンプを有して発行された（たとえば、取引の安全タイムスタンプが互いの所定の期間内である）場合、両方の通貨譲渡が発生する。そうでない場合、どちらの譲渡も発生しない。
【００９８】
［１１０８］  他の例において、Ｔは用いられず、いずれかの関係者が譲渡を取り消す取引をポストする前に両方の取引が発生した場合のみ、通貨譲渡が発生する。たとえば、アリスは、自身の署名付き取引（たとえばアリスのＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ取引）を発行し、その後、第１の取引に関する取消メッセージを含む別の署名付き取引を発行し、次にボブが、自身の署名付き取引を発行する。ボブの取引がアリスの取消メッセージよりも後であった場合、取引は発生しないが、ボブの取引がアリスの取消メッセージよりも先であった場合、取引が発生する。このようにシステムは、取引の順序付けるコンセンサスを用いて、Ｔおよびタイムスタンプを用いずに作動してよい。他の例において、Ｔおよび取消メッセージの両方がサポートされ得る。
【００９９】
［１１０９］  以下の例は、データ（たとえば通貨など）の譲渡を匿名的かつ安全に開始するために「ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ」取引タイプおよび／または分散型データベース機能がどのように用いられ得るかを示す。以下の例において、アリスは、彼女の雇用主が金銭を譲渡したウォレットＷ１を有する。アリスは、Ｗ１から、彼女が作成し、後に購買のために用いられる匿名ウォレットＷ２へＣ個のコインを譲渡したいと所望する。しかしアリスは、取引を見ている者が匿名ウォレットＷ２にＷ１が関連することを知ることがないように、匿名性を保護したいと所望する。アリスの雇用主が店舗と結託して匿名性を攻撃した場合でも、匿名性が安全でなくてはならない。また、たとえばボブは、自身のウォレットＷ３から、彼が作成する匿名ウォレットＷ４へコインを譲渡する際、同じく安全な匿名性を所望する。
【０１００】
［１１１０］  アリスおよびボブは、以下のプロトコルを実行することによって、匿名性の形成を実現することができる。これは、互いに直接電子メールすること、チャットサイトまたはオンラインフォーラムサイトを通して互いにメッセージすること、または（たとえばイベント内で）暗号通貨をホストする同じ公開台帳内で発行された取引を介してなど、任意の形式で互いに連絡を取り合うことを伴ってよい。以下の例は、プロトコルが公開台帳を介して実行されることを想定する。アリスおよびボブは、最初は知り合いではないが、双方が公開台帳に取引を発行する能力を有し、他者が公開台帳に発行する取引を読み取ることができるものとする。アリスおよびボブは、（たとえば１または複数のイベント内で）以下の取引を公開台帳に発行することができる。
アリスが発行：Ａｎｏｎｙｍｉｚｅ１（Ｎ, Ｃ, Ｗ１）＿Ｋ１ 
ボブが計算：                                    Ｂ ＝ ｅｎｃｒｙｐｔ（Ｗ４, Ｗ１）
ボブが発行：Ａｎｏｎｙｍｉｚｅ２（Ｎ, Ｗ３, Ｂ）＿Ｋ３
アリスが計算：                                        Ａ ＝ ｅｎｃｒｙｐｔ（Ｗ２, Ｗ３）
アリスが発行：Ａｎｏｎｙｍｉｚｅ３（Ｎ, Ａ）＿Ｋ１
両者が計算：                                   ＭＩＮ ＝ ｍｉｎ（Ｗ２, Ｗ４）
両者が計算：                                   ＭＡＸ ＝ ｍａｘ（Ｗ２, Ｗ４）
ボブが発行：ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ（Ｎ,  Ｃ, Ｗ１, ＭＩＮ,  Ｃ, Ｗ３, ＭＡＸ,  Ｔ）＿Ｋ３
アリスが発行：ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ（Ｎ,  Ｃ, Ｗ１, ＭＩＮ,  Ｃ, Ｗ３, ＭＡＸ,  Ｔ）＿Ｋ１
【０１０１】
［１１１１］  この例において、アリスは、ウォレットＷ１からＷ２へＣ個のコインを譲渡しようとし、ボブは、ウォレットＷ３からＷ４へＣ個のコインを譲渡しようとする。アリスおよびボブの各々は、各ウォレットの（公開鍵、秘密鍵）鍵ペアを生成することによって自身の所有するウォレットを生成する。ここでは、ウォレットの公開鍵は、ウォレットの名前としても用いられる（他の例において、ウォレットを識別するために別の識別子が用いられ得る）。アリスおよびボブは、観察者が、ウォレットＷ１の所有者がＷ２またはＷ４のいずれかの所有者でもあることを識別できるが、そのどちらであるかを識別できないような方法で、これらの譲渡を遂行したいと所望する。同様に、アリスおよびボブは、観察者が、ウォレットＷ３の所有者がＷ２またはＷ４のいずれかの所有者でもあることを識別できるが、そのどちらであるかを識別できないような方法で、これらの譲渡を遂行したいと所望する。公開鍵Ｗ１を有するウォレットは、秘密鍵Ｋ１を有する。同様に、ウォレットＷ２、Ｗ３、およびＷ４は、それぞれ秘密鍵Ｋ２、Ｋ３、およびＫ４を有する。上述した各取引または命令は、最後に記載された秘密鍵によって署名される。たとえば、最初の取引または命令は、秘密鍵Ｋ１によってデジタル署名される。
【０１０２】
［１１１２］  第１の取引（Ａｎｏｎｙｍｉｚｅ１（Ｎ，Ｃ，Ｗ１）＿Ｋ１）は、アリスがＣ個のコインをＷ１から匿名ウォレットへ譲渡しようとしていることを通知するために用いられる。この取引は、取引のハッシュ、取引に含まれる乱数、および／または他の任意の適当な識別子であってよい識別子番号Ｎを含む。このＮ（たとえば会話識別子および／またはプロセス識別子）は、一度に発生するいくつかの類似したプロセスおよび／または会話が存在する場合、混同を回避する（およびプロセスまたは会話を識別することができる）ように、プロセスを開始した取引を再び参照するために後続の取引において用いられ得る。いくつかの例において、Ｎはタイムアウトデッドライン（たとえばＴ）を含んでよく、その後、Ｎを含む取引は無視される。この取引は、Ｋ１によってデジタル署名される。
【０１０３】
［１１１３］  関数暗号（Ｗ４、Ｗ１）は、公開鍵Ｗ１を用いてＷ４（ボブのターゲット匿名ウォレットとして彼によって所有および定義されるウォレットの公開鍵）を暗号化し、対応する（アリスによって保持される）秘密鍵Ｋ１によってのみ復号することができる結果Ｂをもたらす。これにより、取引を閲覧している分散型データベースの他のインスタンスはいずれも、Ｗ１の所有者（この例ではアリス）を除き、Ｗ４を識別できないことが確実になる。
【０１０４】
［１１１４］  取引匿名化２（Ｎ，Ｗ３，Ｂ）＿Ｋ３は、プロセスまたは会話Ｎの一部として、ボブがＷ３から、Ｂによって識別される匿名ウォレットへＣ個のコインを譲渡しようとしていることを示す。この取引は、秘密鍵Ｋ３を用いてデジタル署名される。アリスはその後、ボブのターゲット匿名ウォレットをＷ４と識別するために秘密鍵Ｋ１を用いてＢを復号してよい。
【０１０５】
［１１１５］  アリスは、関数暗号（Ｗ２，Ｗ３）を実行してよい。これは、公開鍵Ｗ３（ボブの最初のウォレット）を用いてＷ２（アリスのターゲット匿名ウォレットとして彼女によって所有および定義されるウォレットの公開鍵）を暗号化する。アリスはその後、取引匿名化３（Ｎ，Ａ）＿Ｋ１を発行してよい。ボブは、秘密鍵Ｋ３を用いてＡを復号することによって、Ｗ２をアリスのターゲット匿名ウォレットと識別してよい。
【０１０６】
［１１１６］  関数ｍｉｎ（Ｗ２，Ｗ４）は、２つの公開鍵Ｗ３およびＷ４のどちらが辞書順（アルファベット順）で最初であるかを戻す。関数ｍａｘ（Ｗ２，Ｗ４）は、２つの公開鍵Ｗ３およびＷ４のどちらが辞書順（アルファベット順）で最後であるかを戻す。したがって、ＭＩＮはＷ２またはＷ４のいずれかであってよく、ＭＡＸはＷ２またはＷ４のいずれかであってよい。ｍｉｎおよびｍａｘ関数は、アリスおよびボブの両者が識別できるが他者が識別できないウォレットＷ２およびＷ４の順序付けを可能にする。他の例において、たとえばハッシュ関数、ランキングなど、アリスおよびボブが匿名ウォレットＷ２およびＷ４をどのように順序付けるかを識別するために、他の任意の決定関数が用いられ得る。
【０１０７】
［１１１７］  ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ取引は、ボブおよびアリスの両者によって発行され、それぞれのデジタルシグネチャＫ１およびＫ３によって署名され得る。ボブおよびアリスの両者は、それぞれの匿名ウォレットの各々へ同じ数のコインＣを譲渡しているので、どちらのソースウォレットＷ１またはＷ３がどちらの宛先ウォレットＷ２またはＷ４へコインを譲渡するかは問題にならない。したがって、いくつかの例において、アリスは、Ｃ個のコインを自身の所有する匿名ウォレットへ譲渡し、ボブは、Ｃ個のコインを自身の所有する匿名ウォレットへ譲渡する。他の例において、アリスはボブの匿名ウォレットへＣ個のコインを譲渡し、ボブはアリスの匿名ウォレットへＣ個のコインを譲渡する。これは、ＭＩＮおよびＭＡＸ関数によって決定される。またこれにより、観察者はＷ２およびＷ４の両方を識別できるが、どちらのウォレットがＷ１の所有者によって定義され、どちらのウォレットがＷ３の所有者によって定義されたかを識別できないことが確実になる。取引が発行された後、観察者は、ウォレットＷ１およびＷ３の所有者が共同して各々Ｃ個のコインをウォレットＷ２およびＷ４へ譲渡していることを知るが、どちらの送付者がどちらの受取ウォレットを所有するかを知ることはないので、ウォレットＷ２およびＷ４は、ウォレットＷ１およびＷ３よりもわずかに匿名性が高い。
【０１０８】
［１１１８］  いくつかの例において、取引は「代理取引」であってよく、これは、ネットワーク内のノードが他者の代わりに取引を提起することを意味する。上の例において、アリスはウォレットＷ１およびＷ２を所有し、いくつかの取引を発行しようとしている。キャロルが、全権を有する分散型データベースのメンバである場合、アリスは、アリスの代わりに分散型データベースに提起するキャロルへ取引を送信してよい。いくつかの例において、代理取引は、そのサービスに対して支払うためにウォレットＷ１からキャロルへ少額の料金を譲渡する権限を与えることを含んでよい。いくつかの例において、アリスは、たとえばＴＯＲオニオンルーティングネットワークなど、通信を匿名化するネットワークを介してキャロルと通信してよい。
【０１０９】
［１１１９］  いくつかの例において、アリスはその後、上述したデイブとの匿名プロトコルを繰り返してよく、ボブは、エドとのプロトコルを繰り返してよい。その時点で、分散型データベースの他のインスタンスは、アリスが４つのウォレットの１つを所有することを識別できるが、どれであるかを知ることはない。１０回のそのような動作後、アリスは、２１０である１０２４のうち１つのウォレットを所有する。２０回の動作後、セットは１００万を超える。３０回の後、セットは１０億を超える。４０回の後、セットは１兆を超える。プロトコルを実行するためには何分の１秒かしか要さない。しかし、各プロトコルが実行するのに１秒を要する場合でも、自身のウォレットを匿名化しようと試みる誰もが、１分を大幅に下回る時間でランダムに互いにスワップされる。観察者は、結果として生じるウォレットの１つをアリスが所有することを知るが、どの１つであるかを知ることはない。
【０１１０】
［１１２０］  このシステムは、自身のウォレットを匿名化しようと試みる人間が少ない場合に限り、安全性が低い。追加の安全性のために、アリスは、ある期間（たとえば１日、１時間、１週間など）待機し、その後、彼女の最終的なウォレットを更に匿名化してよい。このようにすると、アリスは最終的に、非常に長期間にわたり匿名化を試みた分散型データベースの他のインスタンスを含む群衆の中に隠れることができる。システムを用いる分散型データベースのインスタンスが多いほど、アリスは迅速に目標に到達することができる。
【０１１１】
［１１２１］  システムは、アリスが分散型データベースを実装するネットワーク（たとえばインターネット）と通信する時に攻撃者が彼女のＩＰアドレスを識別することができる場合、損なわれる可能性がある。アリスが所与のＩＰアドレスからプロトコルを実行していることを攻撃者が識別し、即時に、同じアドレスからウォレットＷ２にプロトコルを実行している何者かを目撃した場合、彼らは、アリスがウォレットＷ２を所有するという結論を下し得る。いくつかの例において、ＩＰアドレスは匿名化され得る。たとえば、匿名通信を実現するために匿名通信ネットワーク（たとえばＴｏｒネットワーク）が用いられ得る。その場合、分散型データベースの残りのインスタンスは、Ｗ２がプロトコルを実行し取引に署名したことを識別できるが、Ｗ２がアリスのコンピュータを用いるかボブのコンピュータを用いるかを識別することはできない。
【０１１２】
［１１２２］  管轄区によっては、政府は、人民が（たとえば隣人、犯罪者、外国政府などによる）スパイから匿名であることを可能にしながらも、たとえばマネーロンダリングおよび脱税などの犯罪を防止するために、法律制定によって確実に通貨の流れを監視することができるようにしたいと所望し得る。いくつかの例において、上述した匿名方式およびシステムは、そのような法律制定に対応し得る。そのような例において、政府は、ウォレットが特定の人間に関連することを証明する暗号化証明書を作成および／または定義するために特定の認証局（ＣＡ）または複数のＣＡを作成または承認してよい。暗号は、政府のみが（場合によっては裁判所命令がある場合のみ）それを復号できるようなものであってよい。アリスがウォレットを作成および／または定義した場合、彼女は任意選択的に、そのような証明書をウォレットに添付することができ、これは、ウォレットがアリスに属することを隣人が知ることはできないが、政府は証明書を復号し、アリスをウォレットの所有者と識別できることを意味する。政府は、そのような証明書を有するウォレットに自国内の雇用主のみが預金できること、およびそのような証明書を有するウォレットからの支払いを自国内の店舗のみが受領できることを主張してよい。よってアリスは、ウォレットの連鎖を作成および／または定義するために上記プロトコルを繰り返し実行し、連鎖内の最初および最後のウォレットの適切な証明書を取得することができる。
【０１１３】
［１１２３］  各ウォレットデータ構造は単一の公開秘密鍵ペアを有するものとして上述されたが、他の例において、ウォレットデータ構造は、１つが署名用であり１つが暗号用である２つの公開秘密鍵ペアを含んでよい。そのような例において、上述した方法は、署名のために署名鍵を用い、暗号化のために暗号鍵を用いるように修正され得る。
【０１１４】
［１１２４］  ハッシュグラフを用いてイベント内で取引を格納および交換することが上述されたが、他の例において、安全かつ匿名性の取引を容易にするための上記方法を実行するために他の任意の適当な分散型データベースおよび／または分散型台帳技術が用いられ得る。たとえば、そのような方法を実行するために、ブロックチェーン、ＰＡＸＯＳ、ＲＡＦＴ、ビットコイン、イーサリアムなどの技術が用いられ得る。いくつかの例において、安全かつ匿名性の取引を容易にするための上記方法を実行するために、これらの技術に安全タイムスタンプが追加（たとえばそれらの上に構築）され得る。他の例において、上述したようにタイムスタンプは使用されない。
【０１１５】
［１１２５］  匿名化方法は、分散型データベースの２つの異なるインスタンス間で実行されるものとして上述されたが、他の例において、分散型データベースの２より多い数のインスタンスによって実行され得る。たとえば他の例において、「ＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥ」取引は、追加の数の取引に対応し得る。たとえば、３つの異なるウォレットデータ構造間でのデータの譲渡をサポートするために、ＴＲＡＮＳＦＥＲ＿ＴＲＩＰＬＥ取引が定義され得る。
【０１１６】
［１１２６］  暗号通貨を実装することが上述されたが、他の例において、他の任意の種類の分散型データベース内での取引が匿名化され得る。たとえば、商品の交換のレコード、個人のアイデンティティの認証、特定のリソースを使用するための承認などが匿名化され得る。そのような例において、分散型データベース内での取引の安全性が高められ得る。
【０１１７】
［１１２７］  図３〜図６は、実施形態に係るハッシュグラフの例を示す。５人のメンバが存在し、各々が黒い縦線によって表される。各円は、イベントを表す。イベントから２本の下り線は、２つの過去イベントのハッシュを表す。この例において、各メンバの第１のイベントを除き、全てのイベントが２本の下り線（１つが同じメンバへの太線、１つが他のメンバへの細線）を有する。時間は上向きに進む。図３〜６において、分散型データベースのコンピュータデバイスは、アリス、ボブ、キャロル、デイブ、およびエドと示される。理解すべき点として、そのような指標は、コンピュータデバイスが、図１に関して図示および説明されたコンピュータデバイス１１０、１２０、１３０、および１４０と構造的かつ機能的に同様であることを示す。
【０１１８】
［１１２８］  図７は、実施形態に係る、イベントを同期する２つのコンピュータデバイスの信号フロー図を示す。具体的には、いくつかの実施形態において、分散型データベースインスタンス７０３および８０３は、収束を得るためにイベントを交換してよい。コンピュータデバイス７００は、コンピュータデバイス７００との関係、コンピュータデバイス７００との近接度、コンピュータデバイス７００に関連する順序付きリストなどに基づいて、コンピュータデバイス８００とランダムに同期することを選択してよい。いくつかの実施形態において、コンピュータデバイス８００は、分散型データベースシステムに属するコンピュータデバイスのセットからコンピュータデバイス７００によって選択されてよく、コンピュータデバイス７００は、コンピュータデバイス８００を複数回連続的に選択してよく、あるいは一時コンピュータデバイス８００を選択しなくてもよい。他の実施形態において、過去に選択されたコンピュータデバイスの指標がコンピュータデバイス７００に格納され得る。そのような実施形態において、コンピュータデバイス７００は、コンピュータデバイス８００を再び選択することができるようになる前に、所定の回数の選択の間待機してよい。上述したように、分散型データベースインスタンス７０３および８０３は、それぞれコンピュータデバイス７００のメモリおよびコンピュータデバイス８００のメモリに実装され得る。
【０１１９】
［１１２９］  上記の用語、定義、およびアルゴリズムは、図８〜１２において説明される実施形態および概念を説明するために用いられる。図１３Ａおよび図１３Ｂは、数学形式で示されるコンセンサス方式および／またはプロセスの第１の応用例を示す。図１４Ａおよび図１４Ｂは、数学形式で示されるコンセンサス方式および／またはプロセスの第２の応用例を示す。
【０１２０】
［１１３０］  システム例１：コンピュータデバイス７００がアリスと呼称され、コンピュータデバイス８００がボブと呼称される場合、それらの間の同期は図７に示すとおりであってよい。アリスとボブとの間の同期は、以下のとおりであってよい。
【０１２１】
［１１３１］  アリスはボブに、分散型データベース７０３に格納されたイベントを送信する。
【０１２２】
［１１３２］  ボブは、以下を含む新たなイベントを作成および／または定義する。
【０１２３】
［１１３３］  ボブが作成および／または定義した最後のイベントのハッシュ
【０１２４】
［１１３４］  アリスが作成および／または定義した最後のイベントのハッシュ
【０１２５】
［１１３５］  ボブによる上記のデジタルシグネチャ
【０１２６】
［１１３６］  ボブはアリスに、分散型データベース８０３に格納されたイベントを送信する。
【０１２７】
［１１３７］  アリスは、新たなイベントを作成および／または定義する。
【０１２８】
［１１３８］  アリスはボブに、そのイベントを送信する。
【０１２９】
［１１３９］  アリスは、イベントの全順序をハッシュグラフの関数として計算する。
【０１３０】
［１１４０］  ボブは、イベントの全順序をハッシュグラフの関数として計算する。
【０１３１】
［１１４１］  所与の時間に、メンバは、これまでに受信したイベントを、各イベントを作成および／または定義したコンピュータデバイスおよび／または分散型データベースインスタンスに関連する識別子とともに格納してよい。各イベントは、（親ハッシュを有さない）最初のイベントおよび新たなメンバごとの（彼らを招待し参加させた既存メンバのイベントを表す、単一の親イベントハッシュを有する）第１のイベントを除き、２つの先行イベントのハッシュを含む。このイベントセットを表す図が描かれ得る。図は、各メンバに関する縦線、およびそのメンバによって作成および／または定義された各イベントに関する線上の点模様を示し得る。イベント（上側の点模様）が先行イベント（下側の点模様）のハッシュを含む場合常に、２つの点模様間に対角線が描かれる。イベントは、そのイベントがそのイベントのハッシュを介して（直接、または中間イベントを介してのいずれかで）他のイベントを参照し得る場合、他のイベントにリンクされると言える。
【０１３２】
［１１４２］  たとえば、図３は、ハッシュグラフ６００の例を示す。イベント６０２は、キャロルとの同期の結果として同期後にボブによって作成および／または定義される。イベント６０２は、イベント６０４（ボブによって作成および／または定義された過去のイベント）のハッシュおよびイベント６０６（キャロルによって作成および／または定義された過去のイベント）のハッシュを含む。いくつかの実施形態において、たとえば、イベント６０２内に含まれるイベント６０４のハッシュは、直近の祖先イベントであるイベント６０８および６１０へのポインタを含む。このように、ボブは、イベント６０８および６１０を参照するためにイベント６０２を用い、先行イベントへのポインタを用いてハッシュグラフを再構成してよい。いくつかの例において、イベント６０２は、先行する祖先イベントを介してハッシュグラフ６００内のイベントの各々を参照することができるので、ハッシュグラフ６００内の他のイベントにリンクされると言える。たとえばイベント６０２は、イベント６０４を介してイベント６０８にリンクされる。他の例として、イベント６０２は、イベント６０６およびイベント６１２を介してイベント６１６にリンクされる。
【０１３３】
［１１４３］  システム例２：イベントが、記録するために取引の「ペイロード」または他の情報も含む、システム例１に基づくシステム。そのようなペイロードは、コンピュータデバイスの直近の先行イベントから、発生し、および／または定義された任意の取引および／または情報によってイベントを更新するために用いられ得る。たとえばイベント６０２は、イベント６０４が作成および／または定義されてからボブによって行われた任意の取引を含んでよい。したがって、他のコンピュータデバイスとイベント６０２を同期する時、ボブはこの情報を共有することができる。その結果、ボブによって行われた取引は、イベントに関連し、イベントを用いる他のメンバと共有され得る。
【０１３４】
［１１４４］  システム例３：イベントが、デバッギング、診断、および／または他の目的のために役立つ現在時間および／または日付も含む、システム例１に基づくシステム。時間および／または日付は、コンピュータデバイス（たとえばボブ）がイベントを作成および／または定義するローカル時間および／または日付であってよい。そのような実施形態において、そのようなローカル時間および／または日付は、その他のデバイスと同期されない。他の実施形態において、時間および／または日付は、デバイス間で（たとえばイベントの交換時に）同期され得る。また他の実施形態において、時間および／または日付を決定するためにグローバルタイマが用いられ得る。
【０１３５】
［１１４５］  システム例４：アリスがボブに、ボブによって作成および／または定義されたイベントまたはそのようなイベントの祖先イベントを送信しない、システム例１に基づくシステム。ｙがｘのハッシュを含む場合、またはｘの祖先であるイベントのハッシュをｙが含む場合、イベントｘはイベントｙの祖先である。同様に述べると、そのような実施形態において、ボブはアリスに、アリスによって未だ格納されていないイベントを送信し、アリスによって既に格納されたイベントを送信しない。
【０１３６】
［１１４６］  たとえば図４は、イベント６２２（黒い円）の祖先イベント（点模様の円）および子孫イベント（縞模様の円）を示すハッシュグラフ例６２０を示す。直線は、イベントにおける半順序を確立するものであり、ここで祖先は黒色イベントより前にあり、子孫は黒色イベントより後にある。半順序は、白色イベントが黒色イベントの前であるか後であるかを示さないので、それらの順序を決定するために全順序が用いられる。他の例として、図５は、１つの特定のイベント（塗りつぶされた円）および各メンバがそのイベントの指標を受信する最初の時間（線模様の円）を示すハッシュグラフ例を示す。キャロルがイベント６２４を作成および／または定義するためにデイブと同期する時、キャロルはイベント６２２の祖先イベントを既に知っており受信しているので、デイブはキャロルにそのようなイベントを送信しない。代わりにデイブはキャロルに、キャロルがキャロルの分散型データベースインスタンスに未だ受信および／または格納していないイベントを送信する。いくつかの実施形態において、デイブは、キャロルが過去に受信したイベントに関してデイブのハッシュグラフが何を示すかに基づいて、どのイベントをキャロルへ送信するかを識別してよい。イベント６２２は、イベント６２６の祖先である。したがって、イベント６２６の時点で、デイブは既にイベント６２２を受信している。図４が示すように、デイブは、キャロルからイベント６２２を受信したボブからイベント６２２を受信したエドからイベント６２２を受信した。また、イベント６２４の時点で、イベント６２２は、キャロルによって作成および／または定義されたデイブが受信している最後のイベントである。したがってデイブはキャロルに、デイブがイベント６２２以外に格納しているイベントおよびその祖先を送信してよい。また、デイブからイベント６２６を受信すると、キャロルは、キャロルの分散型データベースインスタンスに格納されたイベント内のポインタに基づいて、ハッシュグラフを再構成してよい。他の実施形態において、デイブは、キャロルがデイブにイベント６２２を送信していること（図４には不図示）およびキャロルが既に受信しているイベントを識別するためにデイブがイベント６２２（およびその中の参照）を用いて識別することに基づいて、どのイベントをキャロルへ送信するかを識別してよい。
【０１３７】
［１１４７］  システム例５：イベントが、そのイベントの祖先を受信者が受信および／または格納する後まで送信されないように、両方のメンバが他方へイベントを送信する、システム例１に基づくシステム。したがって送信者は、２つのハッシュと既に受信された２つの祖先イベントとを比較することによって、イベントが受信されると同時に受信者が各イベントにおける２つのハッシュを確認できるように、最も古いものから最も新しいものまでイベントを送信する。送信者は、送信者のハッシュグラフの現在状態（たとえば、送信者によって定義されたデータベース状態変数）およびそのハッシュグラフが、受信者が既に受信していることを示すことに基づいて、どのイベントを受信者へ送信するかを識別してよい。図３を参照すると、たとえば、イベント６０２を定義するためにボブがキャロルと同期する時、キャロルは、イベント６１９が、ボブによって作成および／または定義されキャロルが受信している最後のイベントであることを識別してよい。その結果キャロルは、ボブがそのイベントおよびその祖先を知っていることを決定してよい。よってキャロルはボブに、イベント６１８およびイベント６１６（すなわち、キャロルが受信しておりボブが未だ受信していない最も古いイベント）を送信してよい。キャロルはその後、イベント６１２、次にイベント６０６をボブへ送信してよい。これによりボブは、イベントを容易にリンクさせ、ボブのハッシュグラフを再構成することができる。ボブが未だ受信していないイベントがどれかを識別するためにキャロルのハッシュグラフを用いることにより、同期の効率性が高くなり、ボブがキャロルからのイベントを要求しないため、ネットワークトラフィックが低減され得る。
【０１３８】
［１１４８］  他の実施形態において、最も新しいイベントが最初に送信され得る。受信者が、２つの過去イベントのうちの１つを未だ受信していないことを（最も新しいイベントにおける２つの過去イベントのハッシュおよび／または最も新しいイベントにおける過去イベントへのポインタに基づいて）決定した場合、受信者は送信者に、そのようなイベントを送信することを要求してよい。これは、受信者が最も新しいイベントの祖先を受信および／または格納するまで発生し得る。図３を参照すると、そのような実施形態において、たとえばボブがキャロルからイベント６０６を受信すると、ボブは、イベント６０６におけるイベント６１２およびイベント６１４のハッシュを識別してよい。ボブは、イベント６０４の作成および／または定義時にアリスからイベント６１４を過去に受信されたことを決定してよい。したがってボブは、キャロルからのイベント６１４を要求する必要はない。ボブは、イベント６１２が未だ受信されていないことも決定してよい。よってボブは、キャロルからのイベント６１２を要求してよい。ボブはその後、イベント６１２内のハッシュに基づいて、ボブがイベント６１６または６１８を受信していないことを決定し、それに従ってキャロルからのこれらのイベントを要求してよい。イベント６１６および６１８に基づいて、ボブはその後、彼がイベント６０６の祖先を受信していることを決定することができる。
【０１３９】
［１１４９］  システム例６：メンバが、いくつかのイベントの中で次に送信するイベントの選択肢を有する場合、イベントは、そのメンバによって作成および／または定義されこれまでに送信された総バイト数を最小にするように選択されるという追加の制約を有する、システム例５に基づくシステム。たとえば、アリスがボブへ送信するために残っている２つのイベントのみを有し、１つが１００バイトであってキャロルによって作成および／または定義されたものであり、１つが１０バイトであってデイブによって作成および／または定義されたものであり、この同期においてこれまでにアリスは既にキャロルによるイベントを２００バイト、デイブによるイベントを２１０バイト送信している場合、アリスはデイブのイベントを最初に送信し、その後キャロルのイベントを送信しなければならない。なぜならば、２１０＋１０＜１００＋２００であるためである。これは、単一のメンバが単一の巨大なイベントまたは大量の小さなイベントを送信する攻撃に対処するために用いられ得る。トラフィックが多くのメンバのバイト制限を超える場合（システム例７に関して説明するように）、システム例６の方法は、正当なユーザのイベントではなく攻撃者のイベントが無視されることを確実にすることができる。同様に述べると、（接続を提携させる１つの巨大イベントに対して防御するために）大きなイベントより前に小さなイベントを送信することによって攻撃が緩和され得る。また、メンバが単一の同期において（たとえばネットワーク制限、メンバのバイト制限などによって）イベントの各々を送信することができない場合、そのメンバは、攻撃者によって定義および／または作成されたイベントのみを送信し、他のメンバによって作成および／または定義されたイベントを全く（ほとんど）送信しないのではなく、各メンバからの少数のイベントを送信してよい。
【０１４０】
［１１５０］  システム例７：ボブがアリスに、自身がこの同期中に受信する気のある最大バイト数を示す数を送信し、アリスが自身の制限について返答するという追加の第１のステップを有する、システム例１に基づくシステム。アリスはその後、次のイベントがこの制限を超える場合、送信を停止する。ボブも同様である。そのような実施形態において、送信されるベイト数が制限される。これにより、収束にかかる時間が増加し得るが、同期ごとのネットワークトラフィック量が低減される。
【０１４１】
［１１５１］  システム例８：同期プロセスの最初に以下のステップが追加される、システム例１に基づくシステム。
【０１４２】
［１１５２］  アリスは、ボブによって作成および／または定義されたイベントまたはボブによって作成および／または定義されたイベントの祖先であるイベントを抜いて、自身が受信および／または格納したイベントのセットであるＳを識別する。
【０１４３】
［１１５３］  アリスは、Ｓ内の各イベントを作成および／または定義したメンバを識別し、メンバのＩＤ番号のリストをボブへ送信する。またアリスは、各メンバによって作成および／または定義され自身が既に受信および／または格納したイベントの数も送信する。
【０１４４】
［１１５４］  ボブは、他のメンバによって作成および／または定義されたイベントを彼がいくつ受信したかのリストを用いて返答する。
【０１４５】
［１１５５］  その後アリスはボブに、ボブが未だ受信していないイベントのみを送信する。たとえば、アリスがボブに、キャロルによって作成および／または定義された１００のイベントを受信したことを示し、ボブが、キャロルによって作成および／または定義された９５のイベントを受信したことを返答した場合、アリスは、キャロルによって作成および／または定義された最新の５つのイベントのみを送信する。
【０１４６】
［１１５６］  システム例９：不正人物を識別および／または処理するための追加のメカニズムを有する、システム例１に基づくシステム。各イベントは２つのハッシュを含み、１つはそのメンバによって作成および／または定義された最後のイベントから得られ（「自己ハッシュ」）、１つは他のメンバによって作成および／または定義された最後のイベントから得られる（「対外ハッシュ」）。メンバが、同じ自己ハッシュを有する２つの異なるイベントを作成および／または定義した場合、そのメンバは「不正人物」である。アリスが、デイブによって作成および／または定義された同じ自己ハッシュを有する２つの異なるイベントを受信することによってデイブが不正人物であることを知った場合、彼女は、デイブが不正人物であるという指標を格納し、今後、彼との同期を差し控える。デイブが不正人物であることをアリスが知り、それでもなお再びデイブと同期し、その事実を記録する新たなイベントを作成および／または定義した場合、アリスもまた不正人物となり、アリスがデイブと更に同期していることを知る他のメンバは、アリスとの同期を中断する。いくつかの実施形態において、これは一方向への同期にしか影響を及ぼさない。たとえばアリスが、自身が各メンバに関して受信したイベントの数および識別子のリストを送信する時、彼女は、不正人物に関するＩＤまたは数を送信しないので、ボブは、任意の対応する数を用いて返答しない。その後アリスはボブに、彼女が受信した不正人物のイベントを送信し、これに関してアリスは、ボブがそのようなイベントを受信したという指標を受信していない。その同期が完了した後、ボブもまた、（デイブが不正人物であることを既に識別していなければ）デイブが不正人物であることを決定することができ、ボブも不正人物との同期を拒絶する。
【０１４７】
［１１５７］  システム例１０：アリスが、自身が識別した不正者のリスト、および彼女が未だ格納している不正者のイベントのリストをボブへ送信することによって同期プロセスを開始し、ボブは、アリスが識別した不正人物に加えて自身が識別した任意の不正人物で応答することが追加された、システム例９におけるシステム。その後、彼らが通常どおりに継続するが、互いに同期する際に不正人物を数に入れない。
【０１４８】
［１１５８］  システム例１１：同期中に受信された任意の新たなイベント内での取引に基づいて、（たとえば、システムのメンバによって定義されたデータベース状態変数によって捕捉されたように）現在状態を繰り返し更新するプロセスを有する、システム例１におけるシステム。これは、以前の状態のコピーに遡ること、および新たな順序でイベントを処理することにより現在状態を再計算することによって、イベントのシーケンスが変化した場合常に、その状態（たとえばイベントの順序）を繰り返し再構築する第２のプロセスも含んでよい。いくつかの実施形態において、現在状態は、取引の結果に関連する状態、残高、条件などである。同様に述べると、状態は、取引によって修正されたデータ構造および／または変数を含んでよい。たとえば、取引が銀行口座間での振替である場合、現在状態は、口座の現在の残高であってよい。他の例として、取引が多人数参加型ゲームに関連する場合、現在状態は、ゲームに関連する位置、生存者の数、獲得アイテム、ゲーム状態などであってよい。
【０１４９】
［１１５９］  システム例１２：状態（たとえば、銀行口座残高、ゲーム状態など）を維持するために「高速クローン」アレイリストを使用することによって高速化された、システム例１１におけるシステム。高速クローンアレイリストは、１つの追加の特徴を有するアレイとして機能するデータ構造であり、オリジナルのコピーである新たなオブジェクトを作成および／または定義するために出現する「クローン」動作をサポートする。クローンに対する変更はオリジナルに影響を及ぼさないので、クローンは、真正コピーであるかのように機能する。しかし、クローンの作成は、１つのアレイリストのコンテンツ全体を他のアレイリストへコピーおよび／または更新することを実際に伴わないので、クローン化動作は真正コピーの作成よりも高速である。オリジナルリストの２つのクローンおよび／またはコピーを有する代わりに、各々がオリジナルリストに対するハッシュテーブルおよびポインタを有する２つの小オブジェクトが用いられ得る。クローンに書込みが行われると、ハッシュテーブルは、どの要素が修正されたかおよび新たな値を記憶する。ある位置で読取りが行われると、ハッシュテーブルが最初に確認され、その要素が修正されていた場合、ハッシュテーブルから新たな値が戻される。そうでない場合、オリジナルアレイリストからの要素が戻される。このように、２つの「クローン」は最初、オリジナルアレイリストに対するポインタにすぎない。しかし、各々が繰り返し修正されると、それ自体とオリジナルリストとの差を格納する大きなハッシュテーブルを有するものへと成長する。クローンはそれ自体がクローン化されてよく、データ構造を、各々が自身のハッシュテーブルおよび親に対するポインタを有するオブジェクトのツリーに拡大させる。したがって要求されたデータを有する頂点が発見されるまで、または根に到達するまで、読取りによってツリーを登ることになる。頂点が過度に大きくまたは複雑になると、それは親の真正コピーと交換されてよく、ハッシュテーブル内の変更がコピーに行われてよく、ハッシュテーブルは破棄される。また、クローンが必要でなくなった場合、ごみ回収中にクローンはツリーから消去されてよく、ツリーは崩壊し得る。
【０１５０】
［１１６０］  システム例１３：状態（たとえば、銀行口座残高、ゲーム状態など）を維持するために「高速クローン」ハッシュテーブルを使用することによって高速化された、システム例１１におけるシステム。これは、ツリーの根がアレイリストではなくハッシュテーブルである点を除き、システム１２と同じである。
【０１５１】
［１１６１］  システム例１４：状態（たとえば銀行口座残高、ゲーム状態など）を維持するために「高速クローン」リレーショナルデータベースを使用することによって高速化された、システム例１１におけるシステム。これは、既存のリレーショナルデータベースマネージメントシステム（ＲＤＢＭＳ）の周囲のラッパーとして機能するオブジェクトである。各見かけ上の「クローン」は、実際には、ＩＤ番号およびデータベースを含むオブジェクトへのポインタを有するオブジェクトである。ユーザのコードが、構造化照会言語（ＳＱＬ）照会をデータベースに行おうと試みる場合、その照会は最初に修正され、次に実データベースへ送信される。実データベースは、各テーブルがクローンＩＤに関する追加の１フィールドを有する点を除き、クライアントコードが見るデータベースと同一である。たとえば、クローンＩＤ１を有するオリジナルデータベースが存在するものとすると、ＩＤ２および３を有する、データベースの２つのクローンが作られる。各テーブルにおける各行は、クローンＩＤフィールド内に１、２、または３を有する。ユーザコードからクローン２に照会が到来すると、照会は、そのフィールド内の２または１を有する行からしか読み取られないように修正される。同様に、３への読取りは、３または１のＩＤを有する行を探し求める。構造化照会言語（ＳＱＬ）コマンドがクローン２へ向かい、行を削除するように述べ、その行が１を有する場合、コマンドは、１を３に変更しなければならず、それによってその行は、クローン２および３によって共有されなくなり、３にのみ可視であるようにマークされる。動作内にいくつかのクローンが存在する場合、その行のいくつかのコピーが挿入されてよく、各々は、異なるクローンのＩＤに変更されてよく、新たな行は、行を「削除」したばかりのクローン以外のクローンに可視である。同様に、クローン２に行が追加された場合、その行は、２のＩＤを有するテーブルに追加される。行の修正は、削除およびその後の挿入に等しい。前述のとおり、いくつかのクローンはごみ回収され、ツリーは単純化され得る。そのツリーの構造は、クローンがアクセス不可能であり完全に内部で使用される追加のテーブルに格納される。
【０１５２】
［１１６２］  システム例１５：状態を維持するために「高速クローン」ファイルシステムを使用することによって高速化された、システム例１１におけるシステム。これは、ファイルシステムの周囲のラッパーとして機能するオブジェクトである。ファイルシステムは、様々なバージョンのファイルシステムを管理するために高速クローンリレーショナルデータベースを用いて、既存のファイルシステムの上に構築される。基礎となるファイルシステムは、大量のファイルを一方向に、または（ディレクトリを小さく保つために）ファイル名に従って分割して格納する。ディレクトリツリーは、データベースに格納され、ホストファイルシステムには提供されなくてよい。ファイルまたはディレクトリのクローンが作られると、「クローン」は単にＩＤ番号を有するオブジェクトであり、データベースは、このクローンが現在存在することを反映するように修正される。高速クローンファイルシステムのクローンが作られた場合、これはユーザには、完全な新しいハードドライブが作成および／または定義され、既存のハードドライブのコピーによって初期化されたものとして出現する。１つのコピーに対する変更は、他のコピーに影響を及ぼし得ない。実際は、各ファイルまたはディレクトリの１つのコピーが存在するだけであり、１つのクローンによってファイルが修正されると、コピーが発生する。
【０１５３】
［１１６３］  システム例１６：高速クローンファイルシステムにおけるファイルの各Ｎバイト部分に関してホストオペレーティングシステムにおいて個別ファイルが作成および／または定義される、システム例１５におけるシステム。Ｎは、たとえば４０９６または１０２４など、何らかの適当なサイズであってよい。この方法では、大きなファイルにおいて１バイトが変更されると、大きなファイルの１チャンクのみがコピーされ修正される。またこれにより、数バイトしか異ならないドライブ上の多数のファイルを分類する時の効率性が高められる。
【０１５４】
［１１６４］  システム例１７：各メンバが、自身が作成および／または定義するイベントの一部または全部において、イベントの順序におけるコンセンサスが現在存在することをメンバが認識および／または識別することを示す、過去の何らかの時点における状態のハッシュを、その時点までに発生したイベントの数とともに含む、システム例１１におけるシステム。メンバが、所与の状態に関してユーザの過半数からそのようなハッシュを含む署名付きイベントを収集した後、メンバは、その時点におけるコンセンサス状態の証拠としてそれを格納し、その時点より前のイベントおよび取引をメモリから消去してよい。
【０１５５】
［１１６５］  システム例１８：中央値または過半数を計算する動作の代わりに重み付き中央値または重み付き過半数が用いられ、メンバが自身の「ステーク」によって重み付けされる、システム例１におけるシステム。ステークは、メンバの投票がどの程度重視されるかを示す数である。ステークは、暗号通貨の持ち分、あるいは単にメンバが最初に招待され参加した時に割り当てられ、そのメンバが参加を招待する新たなメンバに分配された任意の数であってよい。十分なメンバがコンセンサス状態に合意し、彼らの合計ステークが既存のステークの過半数である場合、古いイベントは破棄され得る。メンバによって寄与されたランクの中央値を用いて全順序が計算される場合、その結果は、メンバの半数が高い方のランクを有し、半分が低い方のランクを有する数である。一方、重み付き中央値を用いて全順序が計算される場合、その結果は、合計ステークの約半分がそれより低いランクに関連し、半分がそれより高いランクに関連する数である。重み付き投票および中央値は、１人のメンバが、各々が招待するメンバによって制御される偽名にすぎない多数の「自作自演」ユーザを招待して参加させるシビル攻撃の防止に役立ち得る。招待するメンバが、招待された人に自身のステークを分配することを強いられる場合、自作自演は、コンセンサス結果を制御しようとする試みる攻撃者にとって役に立たない。したがって、いくつかの状況において、プルーフオブステークが役立ち得る。
【０１５６】
［１１６６］  システム例１９：単一の分散型データベースの代わりに、階層内に複数のデータベースが存在する、システム例１におけるシステム。たとえば、ユーザがそのメンバである単一のデータベースが存在し、次にいくつかのより小さなデータベース、または「チャンク」が存在してよく、その各々がメンバのサブセットを有する。イベントがチャンク内で発生すると、イベントはチャンクのメンバにわたり同期され、チャンク外のメンバには同期されない。その後、チャンク内でコンセンサス順序が決定された後、随時、その結果生じる状態（またはコンセンサス全順序を有するイベント）が大きいデータベースのメンバシップ全体に共有され得る。
【０１５７】
［１１６７］  システム例２０：状態を（たとえば、システムのメンバによって定義されたデータベース状態変数によって捕捉されたように）更新するためにソフトウェアを更新するイベントを有する能力を備えた、システム例１１におけるシステム。たとえばイベントＸおよびＹは、それらのイベントにおける取引を読み取るソフトウェアコードに従って状態を修正し、その後、状態を適切に更新する取引を含んでよい。次にイベントＺは、新たなバージョンのソフトウェアが利用可能であるという通知を含んでよい。全順序が、Ｘ、Ｚ、Ｙの順序でイベントが発生することを述べる場合、状態は、Ｘにおける取引を古いソフトウェアによって処理し、Ｙにおける取引を新たなソフトウェアによって処理することによって更新され得る。しかしコンセンサス順序がＸ、Ｙ、Ｚである場合、ＸおよびＹは古いソフトウェアによって更新され、それによって異なる最終状態がもたらされ得る。したがって、そのような実施形態において、コミュニティが、いつ古いバージョンから新しいバージョンへ切り換えるかに関するコンセンサスを実現し得るように、コードをアップグレードする通知がイベント内で発生してよい。これにより、メンバが同期状態を維持することが確実になる。また、アップグレード中も、プロセスを再起動または再開する必要なく、システムが実行し続け得ることも確実になる。
【０１５８】
［１１６８］  システム例２１：上述したシステムは、最終的なコンセンサスをもたらす、分散型コンセンサスに関する効率的な収束メカニズムを作成および／または実現することが予想される。これに関していくつかの定理が、以下に示すように証明され得る。
【０１５９】
［１１６９］  図１０は、第１のデータベースレコード（たとえばウォレット１００２Ａ）および第２のデータベースレコード（たとえばウォレット１００２Ｂ）を有するメンバのアリス、および第１のデータベースレコード（たとえばウォレット１００４Ａ）および第２のデータベースレコード（たとえばウォレット１００４Ｂ）を有するメンバのボブを示す。上述したように、アリスおよびボブは、コンピュータデバイスを介して、たとえばパラメータとして公開秘密鍵ペアを有するウォレット（Ｗ，Ｋ）（たとえば、Ｗは新たなレコードに論理的に関連付けられた公開鍵であり、Ｋは新たなレコードに論理的に関連付けられた秘密鍵である）などのコマンドをポストすることによって、新たなデータベースレコードを作成または定義することができる。分散型データベースは、たとえばアリスの第１のウォレット１００２Ａおよびボブの第１のウォレット１００４Ａに格納されたデジタル資産（たとえば暗号通貨）の金額に対応する値のレコードを追跡および／または維持することができる。いくつかの例において、分散型データベースのメンバまたはユーザは、ウォレット１００２Ａがアリスに属すること、およびウォレット１００４Ａがボブに属することを識別してよい。そのような場合、アリスは、分散型データベースの他のメンバまたはユーザが、ウォレット１００２Ｂがアリスに属することを識別できないように、第２のウォレット（たとえばウォレット１００２Ｂ）を作成および／または定義してよい。言い換えると、アリスは、ウォレット１００２Ｂに行われる取引を分散型データベースの他のメンバまたはユーザに対して匿名に保つように匿名ウォレット１００２Ｂを定義または作成することができる。同様にボブは、匿名ウォレット１００４Ｂを作成し、ウォレット１００４Ｂに行われる取引を匿名に保つことができる。
【０１６０】
［１１７０］  アリスの第２のウォレット１００２Ｂおよびボブの第２のウォレット１００４Ｂは、インスタンス作成後は空であり、未だ分散型データベースの一部ではない。アリスは、自身の第１のウォレット１００２Ａから自身の第２のウォレット１００２Ｂへの直接暗号通貨譲渡をポストし、そのような直接譲渡は、分散型データベースの他のメンバまたはユーザに対し可視である。同様に、ボブの第１のウォレット１００４Ａから彼の第２のウォレット１００４Ｂへの暗号通貨の直接譲渡は、分散型データベースの他のメンバまたはユーザに対し可視である。
【０１６１】
［１１７１］  有利には、いくつかの例において、アリスおよびボブは、図１０に示す譲渡プロトコルまたは動作のシーケンスを実行して、自身の第１のウォレットから自身の第２のウォレットへ匿名の譲渡を行うことができる。図１０に示す動作のいくつかは上述される（たとえば、上述したＴＲＡＮＳＦＥＲ＿ＤＯＵＢＬＥは、図１０に示すＴＲＡＮＳＦＥＲ２と機能的に同様である）。そのような例において、アリスは、ボブにスワップ要求１００１を送信してよい。スワップ要求１００１は、アリスの第１のウォレット１００２Ａの公開鍵Ａ１、アリスが自身の第２のウォレット１００２Ｂへ譲渡しようとするデジタル資産（たとえば暗号通貨）の金額を示す値Ｃ、（たとえば、匿名の譲渡に関連する一連の関連取引を識別するための）乱数識別子Ｎ、および満了タイムスタンプＴを含んでよい。スワップ要求１００１は、ボブへのプライベートメッセージを介して、および／または、公開フォーラム、公開台帳、分散型データベース、または他の適当な通信媒体へのスワップ要求のポストによって、アリスによって行われ得る。いくつかの例において、アリスは、自身の第１のウォレット１００２Ａに対応する秘密鍵Ａ１’を用いてスワップ要求に署名してよく、それによってボブは、アリスの公開鍵Ａ１を用いて、たとえばアリスがスワップ要求を行っていることを検証することができる。
【０１６２】
［１１７２］  いくつかの例において、ボブは、スワップ応答１００３によってスワップ要求１００１に返答してよい。スワップ応答１００３は、ボブの公開鍵Ｂ１、（１００１で受信された）乱数Ｎ、およびアリスの第１のウォレットの公開鍵Ａ１によって暗号化されたボブの第２のウォレット１００４Ｂの公開鍵Ｂ２を含んでよい。したがって、アリスは自身の第１のウォレットの公開鍵（すなわちＡ１）とペアである秘密鍵Ａ１’を有するので、アリスのみが、ボブの第２のウォレット１００４Ｂの公開鍵を復号することができる。同様にボブは、彼の第１のウォレット１００４Ａの公開鍵（すなわちＢ１）とペアである秘密鍵Ｂ１’を用いてスワップ応答１００３に署名してよい。ボブは、アリスがスワップ要求１００１を送信するために用いたのと同じ通信媒体を用いて、または、たとえばアリスによって示されたユニバーサルリソースロケータのアドレスなどのアドレスへ、スワップ応答１００３をポストまたは送信してよい。いくつかの例において、アリスは、ボブがアリスの第２のウォレット１００２Ｂの公開鍵Ａ２を非公開に識別することができるように、ボブの第１のウォレット１００２Ａの公開鍵によって暗号化されたアリスの第２のウォレット１００２Ｂの公開鍵Ａ２もボブへ送信してよい。
【０１６３】
［１１７３］  アリスは、スワップ応答１００３を受信すると、自身の第１のウォレット１００２Ａに対応する秘密鍵Ａ１’によって署名された譲渡コマンド１００５を分散型データベースにポストしてよい。譲渡コマンド１００５は、アリスの第１のウォレット１００２Ａの公開鍵Ａ１およびボブの第１のウォレット１００４Ａの公開鍵Ｂ１、譲渡される予定のデジタル資産を表す金額または値Ｃ、乱数Ｎ、および満了タイムスタンプＴを含んでよい。上述したように、タイムスタンプＴは、Ｔより前にコンセンサスプロトコルを介して分散型データベース内で収束が実現しなかった場合、譲渡コマンド１００５が却下または破棄されるように調整する時間閾値を示す。譲渡コマンド１００５は、第１のレコードまたはウォレット１１０２Ａおよび第２のレコードまたはウォレット１１０４Ａが少なくとも値Ｃのデジタル資産を有するかを識別または決定するように構成される。デジタル資産の値Ｃは、譲渡コマンド１００５の実行時にソースレコード（たとえばウォレット１００２Ａまたは１００４Ａ）から差し引かれ、宛先レコード（たとえばウォレット１００２Ｂまたは１００４Ｂ）に合計される数値であってよい。譲渡コマンド１００５は、アリスの第２のウォレット１００２Ｂの公開鍵Ａ２およびボブの第２のウォレット１００４Ｂの公開鍵Ｂ２も含んでよい。
【０１６４】
［１１７４］  アリスの第２のウォレット１００２Ｂの公開鍵Ａ２およびボブの第２のウォレット１００４Ｂの公開鍵Ｂ２の各々は、文字列として表され得る。各文字列は、関連する辞書値を有してよい。譲渡コマンド１００５をポストする前に、アリスは、公開鍵Ａ２およびＢ２を辞書順に分類してよい。譲渡コマンドがｍｉｎ（Ａ２，Ｂ２）を示す場合、アリスは、２つの文字列の最小値を含んでよい。したがって、アリスが、文字列Ａ２が文字列Ｂ２よりも辞書順で前に来ることを決定した場合、アリスは、譲渡コマンド１００５に（すなわち、図１０内でｍｉｎ（Ａ２，Ｂ２）が示される場所に）Ａ２を含める。同様に、譲渡コマンド１００５をポストする前に、アリスは、２つの文字列の最大値を求めるために公開鍵Ａ２およびＢ２を辞書順に分類してよい。譲渡コマンドがｍａｘ（Ａ２，Ｂ２）を示す場合、アリスは、２つの文字列の最大値を含んでよい。したがって、アリスが、文字列Ｂ２が文字列Ａ２よりも辞書順で後に来ることを決定した場合、アリスは、譲渡コマンド１００５に（すなわち、図１０内でｍａｘ（Ａ２，Ｂ２）が示される場所に）Ｂ２を含める。言い換えると、関数ｍｉｎおよびｍａｘは、パラメータとして受信された公開鍵の辞書的比較を実行する。したがって、Ａ２およびＢ２の両方が譲渡コマンド１００５に含まれる場合、譲渡コマンド内でＡ２およびＢ２を記載する順序は、Ａ２およびＢ２に関連するウォレットの所有権または関連付けに基づくものではない。
【０１６５】
［１１７５］  したがって、譲渡コマンド１００５は、金額Ｃのデジタル資産が２つのソースレコード（たとえばアリスの第１のウォレット１００２Ａおよびボブの第１のウォレット１００２Ａ）の各々から差し引かれ、金額Ｃのデジタル資産が２つの宛先レコード（たとえばアリスの第２のウォレット１００２Ｂおよびボブの第２のウォレット１００４Ｂ）の各々へ記入されるように、分散型データベースに譲渡を命令してよい。公開鍵Ａ２およびＢ２の最小および最大の決定は、宛先ウォレット１００２Ｂまたは１００４Ｂのどちらがソースウォレット１００２Ａまたは１００４Ａのどちらに関連するか（および／または、宛先ウォレット１００２Ｂまたは１００４Ｂのどちらがアリスに関連し、どちらがボブに関連するか）を隠しながら、金額Ｃのデジタル資産がアリスの第２のウォレット１００２Ｂおよびボブの第２のウォレット１００４Ｂの各々へ譲渡されることを保証する。ｍｉｎおよびｍａｘ関数によって求められる分類順序は、各ウォレットを誰が所有するかに無関係であることにより、その情報を分散型データベースの他のメンバまたはユーザから隠す。よって、アリスが譲渡コマンド１００５をポストした後、分散型データベースの他のメンバまたはユーザは、最大でも、デジタル資産金額Ｃが譲渡される宛先ウォレットの１つ（すなわち１００２Ｂまたは１００４Ｂ）をアリスが所有することしか推測できず、２つの宛先ウォレット１００２Ｂまたは１００４Ｂのどちらが実際にアリス（またはアリスによって表されるコンピュータデバイスに関連するユーザ）によって所有されるかを知ることはない。言い換えると、宛先レコード（たとえば１００２Ｂまたは１００４Ｂ）に論理的に関連付けられた公開鍵（たとえばＡ２またはＢ２）とペアである秘密鍵（たとえばＡ２’またはＢ２’）に関連するコンピュータデバイスのアイデンティティ（たとえばアリスまたはボブ）は、アリスおよびボブを含むコンピュータデバイスのセットの中で隠される。
【０１６６】
［１１７６］  ボブは、アリスによってポストされた譲渡コマンド１００５に対応するおよび／または同一であり、かつボブの第１のウォレットに対応する秘密鍵Ｂ１’を用いて署名された譲渡コマンド１００７をポストしてよい。具体的には、ボブは、アリスと同じ取引をポストするためにアリスと同じ分類（たとえば、公開鍵Ａ２およびＢ２の辞書的分類）を実行してよい。あるいは、アリスは、譲渡コマンド１００５をボブに送信するだけであってよく、ボブが、両方のシグネチャとともに単一の譲渡コマンド１００７を分散型データベースにポストしてよい。その後、両方のシグネチャが有効であった場合、分散型データベースは、コンセンサスに至った時点で、ポストされた譲渡コマンドを実行してよい。よって、譲渡プロトコルのいくつかの例において、譲渡コマンド１００５および１００７の両方が分散型データベースにポストされ得るが、他の例において、譲渡コマンド１００７のみが、両方のシグネチャとともに分散型データベースにポストされる。
【０１６７】
［１１７７］  アリスおよびボブは、第２のウォレットの公開鍵Ａ２およびＢ２の最小値および最大値を決定するものとして上述されたが、他の実装において、宛先レコードに関連する公開鍵Ａ２およびＢ２を提示する順序を識別するために他の任意の決定論的分類が用いられ得る。したがって、アリスおよびボブの両者が以下を実行することができる。
Ｓ＝｛Ａ１，Ｂ１｝
Ｄ＝ｓｏｒｔＬｉｓｔ（｛Ａ２，Ｂ２｝）
Ｐｏｓｔ／Ｓｅｎｄ：Ｔｒａｎｓｆｅｒ２（Ｓ，Ｄ，Ｃ，Ｎ，Ｔ）
【０１６８】
［１１７８］  他のいくつかの例において、アリスおよびボブは、第三者（たとえば図１０には示されないキャロル）へメッセージを送信してよく、それによってキャロルは、ボブおよび／またはアリスの代わりに分散型データベースに譲渡コマンドをポストする。また他の例において、第三者は、アリスとボブとの間の匿名性の譲渡に関連する通信のための仲介者として機能する。したがって、アリスおよび／またはボブが仲介者として第三者を用いる場合、彼らのレコード（すなわちウォレット）は、分散型データベースに含まれてよく、それらに関連する公開鍵は、アリスおよびボブに対応するコンピュータデバイスが分散型データベースを実装していない（または分散型データベースのサブセットおよび／または一部しか実装していない）場合でも、分散型データベースによって用いられ得る。そのような場合、分散型データベースの他のメンバ（たとえばキャロル）は、データベース動作の指標、たとえばアリスからの（デジタル資産の金額を示す）値Ｃの（スワップ要求１００１と同様の）譲渡要求を受信し、キャロルがこの要求をボブへ受け渡してよい。その後ボブは、キャロルを介してアリスへ（スワップ応答１００３と同様の）スワップ応答を送信することによってアリスに返答してよい。その後アリスおよびボブは、たとえば（譲渡コマンド１００５および１００７と同様の）彼らの譲渡コマンドなどのデータベース動作の指標をキャロルに提供してよく、キャロルは、要求されたデータベース動作（たとえば譲渡コマンド）を分散型データベースにポストしてよい。
【０１６９】
［１１７９］  他の例として、いくつかの例において、アリスに対応するコンピュータデバイスは分散型データベースを実装していないが、ボブに対応するコンピュータデバイスは実装している。そのような場合、アリスは、データベース動作の指標をキャロルへ送信してよく、キャロルは、対応する譲渡コマンドをアリスの代わりに分散型データベースにポストしてよい。言い換えると、分散型データベースは、分散型データベースを実装していないコンピュータデバイスによって所有されるレコード（すなわちウォレット）を含み、分散型データベースを実装するおよび／または分散型データベースのメンバである第三者コンピュータデバイスを介して、これらのレコードを用いる譲渡プロトコルを実行してよい。
【０１７０】
［１１８０］  また他の例として、いくつかの例において、アリスおよび／またはボブは、分散型データベースの一部を実装および／または格納してよい。具体的には、第三者コンピュータデバイス（キャロル）が分散型データベースのメンバである、および／または分散型データベース全体を実装および／または格納する場合、アリスおよび／またはボブは、キャロルが格納しているものの一部を格納および／または保持してよい。例として、アリスは、自身の公開鍵に関連するレコードを格納することができるが、分散型データベースの他のユーザに関連するレコードを格納することができない。同様にボブは、自身の公開鍵に関連するレコードを格納することができるが、分散型データベースの他のユーザに関連するレコードを格納することができない。そのような例において、アリスおよびボが、分散型データベースの一部を格納するのに対し、キャロルは、分散型データベース全体にアクセスするためにアリスおよびボブの代理として機能してよい。
【０１７１】
［１１８１］  いくつかの実装において、分散型データベースは、所与のウォレットがその中に隠されるウォレットのセット内のウォレットの数を表す、各ウォレットの整数「プールサイズ」を格納してよい。よって、観察者が、ウォレットＸがＮ人の異なるメンバの１人によって所有されることしか知らない場合、どの程度強力に匿名化されているかを示すプールサイズＮがそのウォレットに添付され得る。たとえば１００２Ａおよび１００４Ａなどの非匿名化ウォレットは、所有者が知られているので１のプールを有してよく、よって観察者は、ただ１人の個人のセットにアイデンティティを絞ることができる。他のウォレットは、そのようなウォレットに関してプロトコルが複数回実行された場合、より高度に匿名化され得る。たとえば、観察者が、ウォレットＡ１がＰＡ１人の個人のうち１人によって所有されること、およびＢ１がＰＢ１人の個人のうち１人によって所有されることを識別することができる場合、整数ＰＡ１はＡ１に関連し、整数ＰＢ１はＢ１に関連し得る。
【０１７２】
［１１８２］  いくつかの例において、メッセージ１００１、１００３、１００５、および／または１００７の１または複数は、ＰＡ１およびＰＢ１を含んでよい。アリスおよびボブは、デジタル資産の譲渡を継続するかを決定するために、ＰＡ１およびＰＢ１を用いてよい。たとえば、アリスがこのプロセスを既に１０回行っている場合、ＰＡ１は１０２４であり得る。ボブがこのプロセスを未だ行っていない場合、ＰＢ１は１であり得る。したがってアリスは、自身の匿名性が１０２４のウォレットのプールに隠された状態から１０２５のウォレットのプールに隠された状態へとわずかな増加しかもたらされないため、ボブとのプロトコルを実行することを拒絶し得る。アリスは、一度の反復によりＰＡ１を１０２４から２０４８まで増加させ得るように、１０２４のプールサイズを有するウォレットとの連動を好み得る。いくつかの例において、ウォレットは、整数ではなくウォレットのセットに関連し得る。これは、観察者が、セット内のウォレットの１つを所与のメンバが所有することを知るが、どの１つであるかを知ることがないようなウォレットのセットである。後述の例において、ＰＡ１は１０２４のウォレットのセットであり、ＰＢ１は、１０２４のウォレットのセットである。プロトコルが完了した後、ＰＡ１は、ＰＡ１およびＰＢ１のセットのユニオンに拡大される。アリスは、彼女の匿名性を少量しか増加させないプロセスに時間を割くことがないように、このユニオンがＰＡ１よりも大幅に大きくなるようなウォレットとの連動のみに同意し得る。
【０１７３】
［１１８３］  いくつかの例において、メッセージ１００１は、たとえばアリスが受諾する意思があるＰＢ２の最小閾値を示すパラメータを含んでよい。したがってアリスは、たとえばＰＢ１が最小閾値未満である場合、ボブとのスワップを継続しないことを決定してよい。
【０１７４】
［１１８４］  いくつかの実装において、メッセージ１００１、１００３、１００５、および／または１００７の１または複数は、（１）ユーザコメントを表す文字列値、（２）メッセージが提出された日付および時間、（３）ユーザのウォレット（複数も可）から、メッセージまたは取引を提起またはポストするコンピュータデバイスのウォレットへ料金を移転する承認、（４）ユーザのウォレットから、コンピュータデバイスインターネットプロトコル（ＩＰ）アドレス（たとえば、ＴＯＲネットワーク内のコンピュータデバイス）の匿名化に寄与するコンピュータデバイス（複数も可）への料金の移転の承認、および／または他の任意の適当なメタデータを含んでよい。
【０１７５】
［１１８５］  他の実装において、譲渡コマンドは、たとえば
ＴＲＡＮＳＦＥＲ２（Ｓ，Ｗ，Ｒ，Ｄ，Ｎ，Ｔ）
などの譲渡取引を用いて実行されてよく、ここで、
Ｋ＝送付側ウォレットの数
Ｓ＝公開鍵｛Ｓ１，Ｓ２，．．．，ＳＫ｝を有する送付側ウォレットのリスト
Ｗ＝各ウォレット｛Ｗ１，Ｗ２，．．．，ＷＫ）から差し引かれるデジタル資産の金額またはコインの数
Ｍ＝受取り側ウォレットの数
Ｒ＝公開鍵｛Ｒ１，Ｒ２，．．．，ＲＭ｝を有する受取り側ウォレットのリスト
Ｄ＝各ウォレット｛Ｄ１，Ｄ２，．．．，ＷＭ｝に預金されるデジタル資産の金額またはコインの数
Ｎ＝乱数
Ｔ＝満了タイムスタンプ
であり、差し引かれるコインの数またはデジタル資産金額Ｗの合計は、各ウォレットＤに預金されるコインの数またはデジタル資産金額の合計に対応し、Ｓ内の公開鍵に関連する秘密鍵によるシグネチャが存在する。単一の取引ＴＲＡＮＳＦＥＲ２（Ｓ，Ｗ，Ｒ，Ｄ，Ｎ，Ｔ）は、そのような秘密鍵によって署名された添付ファイルを含んでよい。いくつかの例において、複数の（同じＮを有する）同一取引が存在してよく、その各々がシグネチャの１または複数を有し、必要なシグネチャを集合的に有する。ＴＲＡＮＳＦＥＲ２コマンドに含まれ得る他のパラメータは、（１）コメントを通信するための文字列、（２）譲渡コマンドがポストされた時間を示す日付／時間、（３）レコード（すなわちウォレット）から、譲渡コマンドをポストするための第三者として用いられたコンピュータデバイスのレコード（すなわちウォレット）へ料金を移転する承認を示すパラメータ、および他の適当なメタデータを含んでよい。
【０１７６】
［１１８６］  他の実装において、譲渡コマンド１００５および１００７は、図１０に示すパラメータよりも少ない数のパラメータを含むように修正され得る。たとえば譲渡コマンド１００５は、ＴＲＡＮＳＦＥＲ２（ｍｉｎ（Ａ２，Ｂ２），ｍａｘ（Ａ２，Ｂ２），Ｎ，Ｔ）Ａ１’として分散型データベースにポストされ、譲渡コマンド１００７は、ＴＲＡＮＳＦＥＲ２（Ｎ，Ｔ）Ｂ１’としてポストされ得る。そのような場合、匿名譲渡に伴う一連の関連取引を独自に識別する乱数Ｎの独自性に頼ることによって、余分なパラメータによって消費される帯域幅が低減される。
【０１７７】
［１１８７］  図１１は、ウォレット間の譲渡を匿名化するための、図１０を参照して説明された譲渡プロトコルの反復応用によって生成される４レベルツリー構造を示す。上述したように、図１０の譲渡プロトコルの４つのメッセージを実行した後、ウォレット１００２Ａおよび１００４Ａ内のコインは、ウォレット１００２Ｂおよび１００４Ｂへ譲渡される。分散型データベースのメンバまたはユーザは、分散型データベースに記録された取引の履歴から、たとえばアリスの第１のウォレット１１０１からボブの第２のウォレット１１０４またはアリスの第２のウォレット１１０５のいずれかへの譲渡が実行されたことを推測し得る。同様に、ボブの第１のウォレット１１０３からボブの第２のウォレット１１０４またはアリスの第２のウォレット１１０５のいずれかへの譲渡が実行されたことが推測され得る。したがって、ツリー構造のレベル１において、アリスの第２のウォレット１１０５は、２つのウォレット（すなわちウォレット１１０４および１１０５）のプールの中で、分散型データベースの他のメンバまたはユーザから隠されている。
【０１７８】
［１１８８］  レベル２において、アリスは、図１０を参照して説明された譲渡プロトコルをデイブと繰り返す。ボブは、譲渡プロトコルをキャロルと繰り返す。したがってレベル２において、アリスの第２のウォレット１１０５からウォレット１１０７または１１０９の１つへ複数のコインまたはデジタル資産額が譲渡され、アリスのウォレットは、４つのウォレット、すなわちウォレット１１０７、１１０９、１１１１、および１１１３の中で、分散型データベースの他のメンバまたはユーザから隠されている。アリスは、図１０を参照して説明された譲渡プロトコルを繰り返し続けてよい。各レベルにおいて、アリスのウォレットは、指数関数的に増加するウォレットのプール内で隠される。たとえばレベル３において、アリスは、ハンクと譲渡プロトコルを繰り返し、アリスのウォレット１１１５は、８つのウォレットのプールに隠される。レベル４において、アリスは、オスカーと譲渡プロトコルを繰り返し、アリスのウォレット１１１７は、１６のウォレットのプールに隠される。レベル４０（図１１には不図示）において、アリスのウォレットは、１兆を超えるウォレットのプールに隠される。
【０１７９】
［１１８９］  図１１に示す譲渡プロトコルは、図１２に示すように並列で同様に実行され得る。たとえばアリスは、譲渡が同時またはほぼ同時に実行されるように、ボブ、デイブ、ハンク、およびオスカーとの譲渡プロトコルを実行してよい。したがってアリスは、１２０１、１２０３、１２０５、および１２０７に示される譲渡プロトコルの動作を同時に実行および／またはポストしてよい。コンセンサス順序に至った時点で、金額Ｃのデジタル資産を譲渡するように設定されたウォレットの全てが少なくともそのような金額を有する場合、全ての譲渡が並列で実行される。金額Ｃのデジタル資産を譲渡するように設定されたウォレットの少なくとも１つがそのような金額を有さない場合、１２０１、１２０３、１２０５、および１２０７に示す譲渡プロトコルの動作の１または複数が、「アクティブ」状態で分散型データベースに格納され得る。したがって、「アクティブ」状態で格納された１２０１、１２０３、１２０５、および１２０７に示す譲渡プロトコルの動作は、金額Ｃのデジタル資産を有さなかったウォレットが少なくともそのような金額を有する、コンセンサス履歴内の最初の時点で実行され得る。
【０１８０】
［１１９０］  上述したように、分散型データベースにポストされた譲渡コマンドは、満了時間を示すパラメータＴを含んでよい。１２０１、１２０３、１２０５、および／または１２０７に示す譲渡プロトコルの動作が実行される前に時間Ｔに到達した場合、そのような動作は却下され、実行されない。何らかの時点で、１２０１、１２０３、１２０５、および／または１２０７に示す譲渡プロトコルの動作が分散型データベース内で「アクティブ」であり、ウォレットが十分な金額のデジタル資産（たとえば金額Ｃ）を有するまで実行されることを待機している場合、そのようなウォレットに十分な金額のデジタル資産が投入されると、１２０１、１２０３、１２０５、および／または１２０７に示す譲渡プロトコルの動作の１または複数は、それらのコンセンサス順序でトリガされる。そのような場合、１２０１、１２０３、１２０５、および／または１２０７に示す譲渡プロトコルの動作のコンセンサス順序は、そのような譲渡プロトコルの動作に含まれる署名付き動作のコンセンサス順序の最後であってよい。したがって、譲渡プロトコルの動作は遅延され、または時間Ｔに到達するまで「アクティブ」状態に保たれ得る。「アクティブ」状態の動作を実行するために十分な金額のデジタル資産が時間Ｔまでにレコードに投入されない場合、１２０１、１２０３、１２０５、および／または１２０７に示す譲渡プロトコルの動作は却下される。
【０１８１】
［１１９１］  図１２に示す例において、アリスは、１２０１、１２０３、１２０５、および／または１２０７に示す譲渡プロトコルの動作を、実質的に並行して実質的に同時に分散型データベースにポストする。そのような動作は、コンセンサス順序に到達すると、ソースレコードまたはウォレットが、ポストされた譲渡コマンドにおいて明示されたように期間Ｔ以内に少なくとも金額Ｃのデジタル資産を有した後、実行される。言い換えると、１２０１における公開鍵（Ａ１，Ｂ１）、１２０３における（Ａ２，Ｄ２）、１２０５における（Ｏ４，Ａ４）、および１２０７における（Ａ３，Ｈ３）に関連するレコードが、期間Ｔ内の任意の時点で少なくとも金額Ｃのデジタル資産に関連する場合、譲渡プロトコル１２０１、１２０３、１２０５、および１２０７の動作は、公開鍵が金額Ｃに関連付けられると実行される。しかし、取引に関与する公開鍵に関連するレコードの１つが、期間Ｔ内の時点で少なくとも金額Ｃのデジタル資産を含まない場合、その譲渡は（期間Ｔの満了後に）取り消されるが、他の任意の取引は、その取引の公開鍵に関連するレコードが期間Ｔ内の時点で金額Ｃに関連付けられさえすれば実行される。したがって、１２０１、１２０３、１２０５、１２０７に示す譲渡プロトコルの動作の実行は、ソースレコードまたはウォレットが譲渡を設定された金額Ｃを有するか、および有さない場合は、ソースレコードまたはウォレットは時間Ｔが経過する前に金額Ｃのデジタル資産を取得するかに基づいてよい。これにより、取引が連続的に実行されることが可能でありながら、メンバ（たとえばアリス）は、複数の連続取引を分散型データベースに同時にポストすることができる。
【０１８２】
［１１９２］  たとえば、アリスが１２０１、１２０３、１２０５、１２０７に示す譲渡プロトコルの動作を実質的に並行して実質的に同時に分散型データベースにポストするが、ポスト時、レコードＡ１およびＢ１のみが金額Ｃを含む場合、取引１２０１のみが実行する。これは、Ａ２およびＢ２に関連するレコードへの金額Ｃの譲渡である。Ｄ２に関連するレコードもまた期間Ｔ内に金額Ｃを取得した場合、（Ａ２に関連するレコードが取引１２０１につき金額Ｃを受け取ってから）取引１２０３が実行する。同様に、取引１２０７、次に取引１２０５が実行してよい。したがって、取引１２０１、１２０３、１２０５、および１２０７の各々は、同時に分散型データベースにポストされ得るが、金額Ｃがレコードに受け取られた（期間Ｔ内の）時間に基づいて連続的順序で実行する。
【０１８３】
［１１９３］  定理例１：半順序においてイベントｘがイベントｙよりも先行する場合、所与の時間における所与のメンバの他のメンバに関する知識において、他のメンバの各々は、ｙより前にｘの指標を受信するか、あるいはｙの指標を未だ受信していない。
【０１８４】
［１１９４］  証明：半順序においてイベントｘがイベントｙよりも先行する場合、ｘはｙの祖先である。メンバがｙの指標を最初に受信する時、そのメンバは、先にｘの指標を既に受信しているか（この場合、彼らはｙより前にｘを認識している）、あるいは同期がそのメンバにｘおよびｙの両方を提供する場合がある（この場合、単一の同期中に受信されるイベントは、システム例５に関して説明したように祖先関係と一致する順序で受信されていると考えられるので、彼らはその同期中にｙより前にｘを認識する）。証明終了。
【０１８５】
［１１９５］  定理例２：任意の所与のハッシュグラフに関して、半順序においてｘがｙよりも先行する場合、ｘは、そのハッシュグラフに関して計算された全順序においてｙよりも先行する。
【０１８６】
［１１９６］  証明：半順序においてｘがｙに先行する場合、定理１によって、
【０１８７】
［１１９７］  全てのｉに関し、ｒａｎｋ（ｉ，ｘ）＜ｒａｎｋ（ｉ，ｙ）であり、
【０１８８】
［１１９８］  ここでｒａｎｋ（ｉ，ｘ）は、メンバｉによってイベントｘに割り当てられたランクであり、ｘがメンバｉによって受信された第１のイベントである場合、１であり、第２のイベントである場合、２であり、以下同様である。ｍｅｄ（ｘ）は全てのｉにわたるｒａｎｋ（ｉ，ｘ）の中央値であり、ｍｅｄ（ｙ）についても同様であるものとする。
【０１８９】
［１１９９］  所与のｋについて、ｒａｎｋ（ｉ１，ｘ）がｋ番目に小さいｘランクであり、ｒａｎｋ（ｉ２，ｙ）がｋ番目に小さいｙランクであるように、ｉ１およびｉ２を選択する。すると、
【０１９０】
［１２００］  ｒａｎｋ（ｉ１，ｘ）＜ｒａｎｋ（ｉ２，ｙ）である。
【０１９１】
［１２０１］  これは、ｒａｎｋ（ｉ２，ｙ）が、各々が対応するｘランクよりも厳密に大きいｙランクのｋ以上であるためである。したがって、ｒａｎｋ（ｉ２，ｙ）はｘランクの少なくともｋよりも厳密に大きいので、ｋ番目に小さいｘランクよりも厳密に大きい。この論証は、あらゆるｋに関して成り立つ。
【０１９２】
［１２０２］  ｎを（ｉ値の数である）メンバの数とする。ｎは奇数または偶数のいずれかでなくてはならない。ｎが奇数である場合、ｋ＝（ｎ＋１）／２とすると、ｋ番目に小さいランクが中央値である。よって、ｍｅｄ（ｘ）＜ｍｅｄ（ｙ）である。ｎが偶数である場合、ｋ＝ｎ／２の時、ｋ番目に小さいｘランクは、ｋ番目に小さいｙランクよりも厳密に小さく、また（ｋ＋１）番目に小さいｘランクは、（ｋ＋１）番目に小さいｙランクよりも厳密に小さい。そのため２つのｚランクの平均は、２つのｙランクの平均よりも小さい。よって、ｍｅｄ（ｘ）＜ｍｅｄ（ｙ）である。したがって両方の場合において、ｘランクの中央値は、ｙランクの中央値よりも厳密に小さい。よって、中央値ランクによってアクションを分類することにより全順序が定義される場合、ｘは全順序においてｙよりも先行する。証明終了。
【０１９３】
［１２０３］  定理例３：「ゴシップ期間」が、既存のイベントが同期を通して全てのメンバに伝搬する時間である場合、
【０１９４】
［１２０４］  １ゴシップ期間後：全てのメンバがイベントを受信する。
【０１９５】
［１２０５］  ２ゴシップ期間後：全てのメンバが、これらのイベントの順序において合意する。
【０１９６】
［１２０６］  ３ゴシップ期間後：全てのメンバが、合意に至ったことを知る。
【０１９７】
［１２０７］  ４ゴシップ期間後：全てのメンバが、このコンセンサス順序を是認する、他の全てのメンバからのデジタルシグネチャを取得する。
【０１９８】
［１２０８］  証明：Ｓ０が、所与の時間Ｔ０までに作成および／または定義されたイベントのセットであるものとする。全てのメンバが最終的に他の全てのメンバと何度でも同期するものとすると、確率１の場合、最終的に、Ｓ０内のイベントが全てのメンバに拡散され全てのメンバがイベントを認識する時間Ｔ１が存在する。これは、第１のゴシップ期間の終了である。Ｓ１が、時間Ｔ１に存在し、Ｔ０には未だ存在しないイベントのセットであるものとする。確率１の場合、最終的に、時間Ｔ１に存在したセットＳ１内の全てのイベントを全てのメンバが受信する時間Ｔ２が存在する。これは、第２のゴシップ期間の終了である。同様に、Ｔ３は、Ｔ２までに存在するがＴ１以前には存在しないＳ２内の全イベントが全メンバに拡散される時間である。ただし、各ゴシップ期間は最終的に、確率１で終了する。平均して、ｎ人のメンバがいる場合、各々は、Ｌｏｇ２（ｎ）回の同期を実行する限り継続する。
【０１９９】
［１２０９］  時間Ｔ１までに、全てのメンバがＳ０内の全てのイベントを受信する。
【０２００】
［１２１０］  時間Ｔ２までに、所与のメンバであるアリスは、Ｓ０内の全てのイベントを受信している他のメンバの各々のレコードを受信する。したがってアリスは、全てのメンバに関するＳ０内の全てのアクションの（そのメンバがそのアクションを受信した順序である）ランクを計算し、ランクの中央値によってイベントを分類する。その結果生じる全順序は、Ｓ０内のイベントに関して変化しない。なぜなら、結果である順序は、これらのイベントの各々の指標を各メンバが最初に受信した順序の関数であり、これは変わることがないためである。アリスが計算した順序は、Ｓ０イベントの中に散在するＳ１からのいくつかのイベントを有する。これらのＳ１イベントは、Ｓ０イベントのシーケンス内のどこに含まれるかが変わることがある。しかし、Ｓ０内のイベントの相対的順序は変化しない。
【０２０１】
［１２１１］  時間Ｔ３までに、アリスは、Ｓ０およびＳ１のユニオンにおける全順序、およびそのユニオン内のイベントの相対的順序が変化しないことを学ぶ。彼女は更に、このシーケンス内でＳ１からの最先イベントを知ることができ、Ｓ０外の新たなイベントの挿入による場合でも、Ｓ１より前のイベントのシーケンスは変化しないと結論を下すことができる。したがって時間Ｔ３までに、アリスは、第１のＳ１イベントより前の履歴におけるイベントの順序に関してコンセンサスが実現されたと決定することができる。彼女は、この順序で発生するこれらのイベントの結果生じる（たとえばアリスによって定義されたデータベース状態変数によって捕捉された）状態のハッシュにデジタル署名し、彼女が作成および／または定義する次のイベントの一部としてシグネチャを送信することができる。
【０２０２】
［１２１２］  時間Ｔ４までに、アリスは、他のメンバから同様のシグネチャを受信する。その時点で、彼女は、シグネチャが証明する状態とともにそのシグネチャリストを保持するだけでよく、彼女が第１のＳ１イベントより前に格納したイベントを破棄してよい。証明終了。
【０２０３】
［１２１３］  本明細書で説明されるシステムは、迅速かつ安全にコンセンサスを実現する分散型データベースを説明する。これは、多数の応用例のための有用な構成ブロックであり得る。たとえば、取引が、１つの暗号通貨ウォレットから別のウォレットへの暗号通貨の譲渡を表す場合、かつ状態が単純に各ウォレット内の通貨額の記述である場合、このシステムは、既存のシステムにおける高費用のプルーフオブワークを回避する暗号通貨システムを継続する。現在の暗号通貨において一般的ではない機能を追加するための自動規則の実施がこれを可能にする。たとえば、ウォレットが特定の期間暗号通貨を送付も受取りもしない場合、そのウォレットは削除され、その価値が、現在持っている額に比例して他の既存のウォレットへ分配される規則を実施することによって、失われたコインが回復し、デフレーションが回避され得る。このような場合、ウォレットの秘密鍵が失われた場合でも、貨幣供給が膨張または収縮することはない。
【０２０４】
［１２１４］  他の例は、サーバ上でプレイされている多人数参加型オンライン（ＭＭＯ）ゲームのように機能するが中央サーバを用いずに実現する分散型ゲームである。コンセンサスは、制御される任意の中央サーバがなくとも実現され得る。
【０２０５】
［１２１５］  他の例は、そのようなデータベースの上に構築されるソーシャルメディアのためのシステムである。取引はデジタル署名され、メンバが他のメンバに関する情報を受信することにより、現在のシステムに優る安全性および利便性の利点が提供される。たとえば、電子メールが偽造返信アドレスを有し得ないことにより、強力なスパム対策ポリシを有する電子メールシステムが実装され得る。そのようなシステムは、電子メール、ツイート、テキスト、フォーラム、ウィキ、および／または他のソーシャルメディアによって現在行われている機能を単一の分散型データベースに結合する統合ソーシャルシステムにもなり得る。
【０２０６】
［１２１６］  他のアプリケーションは、たとえばグループが全体として約定または文書に署名するグループデジタルシグネチャなど、より高度な暗号関数を含んでよい。この形式および他の形式の他者同時計算は、そのような分散型コンセンサスシステムを用いて有用に実装され得る。
【０２０７】
［１２１７］  他の例は、公開台帳システムである。誰でも金銭を支払ってシステム内に何らかの情報を格納することができ、システムに情報を格納するために年ごとにバイト当たり少額の暗号通貨（または実際の通貨）を支払う。これらの資金はその後、そのデータを格納するメンバ、およびコンセンサスを実現するために繰り返し同期して働くメンバに自動的に分配され得る。メンバが同期する度に、それらのメンバへ少額の暗号通貨を自動的に譲渡することができる。
【０２０８】
［１２１８］  これらの例が示すように、分散型コンセンサスデータベースは、多数の応用例の構成要素として有用である。データベースは、高費用のプルーフオブワークを用いず、代わりにより安価なプルーフオブステークを用いるので、より小さなコンピュータまたはモバイルおよび埋込型デバイス上で動作するフルノードによって動作することができる。
【０２０９】
［１２１９］  イベントは、前の２つのイベントのハッシュ（１つの自己ハッシュおよび１つの対外ハッシュ）を含むものとして上述されたが、他の実施形態において、メンバは、前の３つのイベントのハッシュ（１つの自己ハッシュおよび２つの対外ハッシュ）を含むイベントを作成および／または定義するために２人の他メンバと同期してよい。また他の実施形態において、任意の数のメンバからの前のイベントの任意の数のイベントハッシュがイベント内に含まれ得る。いくつかの実施形態において、異なるイベントは、前のイベントの異なる数のハッシュを含んでよい。たとえば、第１のイベントは２つのイベントハッシュを含んでよく、第２のイベントは３つのイベントハッシュを含んでよい。
【０２１０】
［１２２０］  イベントは、前のイベントのハッシュ（または暗号ハッシュ値）を含むものとして上述されたが、他の実施形態において、イベントは、ポインタ、識別子、および／または前のイベントへの他の任意の適当な参照を含むように作成および／または定義されてよい。たとえばイベントは、前のイベントに関連し前のイベントを識別するために用いられるシリアル番号を含むことによってイベントをリンクさせるように作成および／または定義され得る。いくつかの実施形態において、そのようなシリアル番号はたとえば、イベントを作成および／または定義したメンバに関連する識別子（たとえば、メディアアクセス制御（ＭＡＣ）アドレス、インターネットプロトコル（ＩＰ）アドレス、割当てアドレスなど）およびそのメンバによって定義されたイベントの順序を含んでよい。たとえば、識別子１０を有するメンバは、そのメンバによって作成および／または定義された１５番目のイベントの場合、そのイベントに識別子１０１５を割り当ててよい。他の実施形態において、イベントに識別子を割り当てるために他の任意の適当なフォーマットが用いられ得る。
【０２１１】
［１２２１］  他の実施形態において、イベントは、暗号ハッシュ全部を含んでよいが、それらのハッシュの一部のみが同期中に伝送される。たとえば、ハッシュＨを含むイベントをアリスがボブへ送信し、ＪがＨの第１の３バイトであり、アリスが、自身が格納しているイベントおよびハッシュのうち、ＨはＪから始まる唯一のハッシュであることを決定すると、アリスは、同期中に、ＨではなくＪを送信してよい。その後ボブが、Ｊから始まる他のハッシュを自身が有することを決定すると、ボブはアリスに応答し、Ｈ全部を要求する。このように、ハッシュは伝送中に圧縮され得る。
【０２１２】
［１２２２］  図示され上述されたシステム例は、他のシステムに関して説明されるが、他の実施形態において、システム例およびそれらの関連機能の任意の組み合わせが、分散型データベースを作成および／または定義するために実装され得る。たとえば、システム例１、システム例２、およびシステム例３は、分散型データベースを作成および／または定義するために組み合わせられ得る。他の例として、いくつかの実施形態において、システム例１０は、システム例１を伴うがシステム例９を伴わずに実装され得る。また他の例として、システム例７は、システム例６と組み合わせられ、実装され得る。また他の実施形態において、他の任意の適当なシステム例の組み合わせが実装され得る。
【０２１３】
［１２２３］  様々な実施形態が上述されたが、それらは限定ではなく例示的に提示されたものにすぎないことを理解すべきである。上述した方法が、特定の順序で発生する特定のイベントを含む場合、特定のイベントの順序は変更され得る。また、いくつかのイベントは、上述したように連続的に実行されるのと同様に、可能であれば並列プロセスで同時に実行されてよい。
【０２１４】
［１２２４］  本明細書で説明される実施形態のいくつかは、様々なコンピュータ実装動作を実行するための命令またはコンピュータコードを有する（非一時的プロセッサ可読媒体とも称され得る）非一時的コンピュータ可読媒体を備えるコンピュータストレージ製品に関する。コンピュータ可読媒体（またはプロセッサ可読媒体）は、一時的な伝搬信号（たとえば、空間またはケーブルなどの伝送媒体において情報を搬送する伝搬電磁波）自体を含むものではないという意味で、非一時的である。媒体および（コードとも称され得る）コンピュータコードは、特定の１または複数の目的のために設計および構成されたものであってよい。非一時的コンピュータ可読媒体の例は、たとえばハードディスク、フロッピーディスク、および磁気テープなどの磁気記憶媒体、たとえばコンパクトディスク／デジタルビデオディスク（ＣＤ／ＤＶＤ）、コンパクトディスク読取専用メモリ（ＣＤ−ＲＯＭ）、およびホログラフィックデバイスなどの光記憶媒体、たとえば光ディスクなどの光磁気記憶媒体、モジュールを処理する搬送波信号、および、たとえば特定用途向け集積回路（ＡＳＩＣ）、プログラマブル論理デバイス（ＰＬＤ）、読取専用メモリ（ＲＯＭ）、およびランダムアクセスメモリ（ＲＡＭ）デバイスなど、プログラムコードを格納および実行するように特に構成されたハードウェアデバイスを含むが、これに限定されない。本明細書で説明される他の実施形態は、たとえば本明細書で説明される命令および／またはコンピュータコードを含むことができるコンピュータプログラム製品に関する。
【０２１５】
［１２２５］  コンピュータコードの例は、マイクロコードまたはマイクロ命令、たとえばコンパイラによって生成されるような機械命令、ウェブサービスを生成するために用いられるコード、およびインタープリタを用いてコンピュータによって実行される高レベル命令を含むファイルを含むが、これに限定されない。たとえば実施形態は、命令型プログラミング言語（たとえばＣ、Ｆｏｒｔｒａｎなど）、関数型プログラミング言語（たとえばＨａｓｋｅｌｌ、Ｅｒｌａｎｇなど）、論理型プログラミング言語（たとえばＰｒｏｌｏｇ）、オブジェクト指向プログラミング言語（たとえばＪａｖａ、Ｃ＋＋など）、または他の適当なプログラミング言語および／または開発ツールを用いて実装され得る。コンピュータコードの追加の例は、制御信号、暗号化コード、および圧縮コードを含むが、これに限定されない。
【０２１６】
［１２２６］  様々な実施形態が上述されたが、それらは限定ではなく例示的に提示されたものにすぎず、形式および細部における様々な変更がなされ得ることを理解すべきである。本明細書で説明される装置および／または方法の任意の一部は、相互排他的な組み合わせを除き、任意の組み合わせで組み合わせられてよい。本明細書で説明される実施形態は、説明された様々な実施形態の機能、構成要素、および／または特徴の様々な組み合わせおよび／または部分的組み合わせを含んでよい。
【図１】
0006966544.tif 000003
【図２】
0006966544.tif 000004
【図３】
0006966544.tif 000005
【図４】
0006966544.tif 000006
【図５】
0006966544.tif 000007
【図６】
0006966544.tif 000008
【図７】
0006966544.tif 000009
【図８】
0006966544.tif 000010
【図９】
0006966544.tif 000011
【図１０】
0006966544.tif 000012
【図１１】
0006966544.tif 000013
【図１２】
0006966544.tif 000014
【図１３Ａ】
0006966544.tif 000015
【図１３Ｂ】
0006966544.tif 000016
【図１４Ａ】
0006966544.tif 000017
【図１４Ｂ】
0006966544.tif 000018