(57)【要約】  シャードされたブロックチェーンネットワークのノードの間でブロックチェーンのブロックを維持管理するコンピュータ実施方法及びシステムが提供され、各ノードは複数のアクティブなシャードのうち1つ以上のシャードのメンバーである。当該方法及びシステムは、ブロックチェーンの新たなブロックを表すデータを生成し、新たなブロックを表すデータを記憶するために、複数のアクティブなシャードの特定のサブセットのメンバーである所与のノードを使用する。このようなデータは、i)新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連するトランザクションのトランザクション識別子のリスト、及び/又はii)新たなブロックの部分マークルツリーを含む。
2021522710.tif 000002
【特許請求の範囲】
【請求項１】
シャードされたブロックチェーンネットワークのノードの間でブロックチェーンのブロックを維持管理するためのコンピュータ実施方法であり、各ノードは複数のアクティブなシャードのうち1つ以上のシャードのメンバーである、コンピュータ実施方法であって、
前記複数のアクティブなシャードの特定のサブセットのメンバーである所与のノードにより前記ブロックチェーンの新たなブロックを表すデータを生成するステップと、
前記所与のノードにより前記新たなブロックを表す前記データを記憶するステップと
を含み、
前記データは、i)前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連するトランザクションのトランザクション識別子のリスト、及び/又はii)前記新たなブロックの部分マークルツリーを含む、コンピュータ実施方法。
【請求項２】
i)の前記トランザクション識別子のリストは、前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連しないトランザクションのトランザクション識別子を含まない、請求項１に記載のコンピュータ実施方法。
【請求項３】
i)の前記トランザクション識別子のリストは、前記新たなブロックに含まれるデータに基づいて、前記新たなブロックのトランザクション識別子の初期リストを構築し、前記複数のアクティブなシャードの前記特定のサブセットに関連しないトランザクションに対応するいずれかのトランザクション識別子を除去するように前記トランザクション識別子の初期リストを処理することにより生成される、請求項２に記載のコンピュータ実施方法。
【請求項４】
ii)の前記部分マークルツリーは、前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連しないトランザクションから導出されたハッシュ値を含み、一方で、前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連するトランザクションから導出されたハッシュ値を省略する、請求項１に記載のコンピュータ実施方法。
【請求項５】
ii)の前記部分マークルツリーは、前記新たなブロックに含まれるデータに基づいて前記新たなブロックの全マークルツリーを構築し、前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連するトランザクションから導出されたハッシュ値を、プレースホルダに置き換えることにより生成される、請求項１に記載のコンピュータ実施方法。
【請求項６】
前記全マークルツリーの処理は、前記全マークルツリーの最下位レベルからルートレベルまで反復し、隣接ノード対についての2つのハッシュ値を除去し、親ハッシュ値を残すことを更に含む、請求項５に記載のコンピュータ実施方法。
【請求項７】
前記全マークルツリーの処理は、前記全マークルツリーの最下位レベルからルートレベルまで反復し、前記複数のアクティブなシャードの前記特定のサブセットに関連しないトランザクションから導出されたハッシュ値を共に表さない2つの子ノードを有する親ツリーノードのハッシュ値を、プレースホルダに置き換えることを更に含む、請求項５に記載のコンピュータ実施方法。
【請求項８】
前記ブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連しないトランザクションへのアクセスを必要とせずに、ブロック承認のためのマークルルートハッシュ値を計算するために前記部分マークルツリーを処理するように前記ノードを動作させるステップを更に含む、請求項１に記載のコンピュータ実施方法。
【請求項９】
前記マークルルートハッシュ値を計算するための前記部分マークルツリーの処理は、前記部分マークルツリーの下位レベルからルートレベルまで反復し、プレースホルダを、前記部分マークルツリーの対応する子ハッシュ値から計算されたハッシュ値に置き換える、請求項８に記載のコンピュータ実施方法。
【請求項１０】
i)の前記トランザクション識別子のリスト及びii)の前記部分マークルツリーは、ノードのメンバーシップ及び前記シャードの間の前記トランザクションの割り当てに基づいて前記ノードの間で変化する、請求項１に記載のコンピュータ実施方法。
【請求項１１】
前記新たなブロックを表すデータを生成する際に、前記ノードは、前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連するトランザクションを承認し、一方で、前記新たなブロックの一部であり且つ前記複数のアクティブなシャードの前記特定のサブセットに関連しないトランザクションの承認をバイパスする、請求項１に記載のコンピュータ実施方法。
【請求項１２】
前記新たなブロックの一部である前記トランザクションは、トランザクション識別子に基づいて、前記複数のアクティブなシャードのうちのシャードに関連付けられる、請求項１に記載のコンピュータ実施方法。
【請求項１３】
前記新たなブロックの一部である前記トランザクションは、親ブロックチェーントランザクションに基づいて、前記複数のアクティブなシャードのうちのシャードに関連付けられ、前記親トランザクションは、子ブロックチェーントランザクションのインプットに対応するアウトプットにより定義され、前記親トランザクション及び前記子トランザクションの双方は、同じシャードに関連付けられる、請求項１に記載のコンピュータ実施方法。
【請求項１４】
システムであって、
プロセッサと、
前記プロセッサによる実行の結果として、当該システムに請求項１乃至１３のうちいずれか１項に記載のコンピュータ実施方法を実行させる実行可能命令を含むメモリと
を含むシステム。
【請求項１５】
コンピュータシステムのプロセッサにより実行された結果として、前記コンピュータシステムに請求項１乃至１３のうちいずれか１項に記載のコンピュータ実施方法を少なくとも実行させる実行可能命令を記憶した非一時的なコンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、概して、ブロックチェーントランザクションを処理するコンピュータ実施システム及び方法に関し、より詳細には、ブロックチェーンを分割し、分割されたブロックチェーンのトランザクション及びブロックを承認するシステム及び方法に関する。
【背景技術】
【０００２】
この文献では、「ブロックチェーン(blockchain)」という用語は、いくつかの形式の電子的なコンピュータに基づく分散型の台帳のいずれかを示す。これらは、コンセンサスに基づくブロックチェーン及びトランザクションチェーン技術、プライベート型(permissioned)及びパブリック型(un-permissioned)台帳、共有台帳及びこれらの変形を含む。ブロックチェーン技術の最も広く知られているアプリケーションはビットコイン台帳であるが、他のブロックチェーンの実装も提案されて開発されている。ここでは、本開示の便宜上及び説明上の目的でビットコインの例が参照されることがあるが、本開示は、ビットコインブロックチェーンでの使用に限定されず、代替のブロックチェーンの実装及びプロトコルも、本開示の範囲内に入る点に留意すべきである。例えば、本開示は、どの制約がトランザクション内で符号化可能であるかに関して、ビットコインと同様の制限を有する他のブロックチェーンの実装において有用になり得る。
【０００３】
ブロックチェーンは、ピアツーピアの電子台帳であり、これはコンピュータに基づく非集中的な分散型システムにより作成及び維持管理される。台帳はブロックで構成され、次に、ブロックはトランザクション及び他の情報で構成される。ブロックチェーンシステム又はブロックチェーンネットワークは、複数のブロックチェーンノードと、動作のセットとを含む。ブロックチェーンノードは、動作のセットの中の動作の一部又は全てを実行するように構成されてもよい。様々なブロックチェーンノードは、ノードオペレータにより操作されるコンピュータハードウェア、コンピュータソフトウェア又はその双方の組み合わせとして実装されてもよく、ノードオペレータは、他のノードオペレータと独立して無関係とすることができる。ブロックチェーンノードは、ブロックチェーン台帳のコピー又はそのいくつかの部分をそれぞれ維持管理してもよい。動作のセットは、トランザクションの作成と、トランザクションの伝搬と、ブロックチェーン台帳の読み取りと、ブロックチェーン台帳の評価と、ブロックチェーン台帳への追加の提案についての新たなブロックの生成(マイニング)と、他のブロックチェーンノードとの通信と、ユーザがトランザクションを作成してブロックチェーン資産を管理するためのウォレット機能の提供とを含んでもよい。
【０００４】
ブロックチェーン台帳は、いつ台帳が修正されるかを判断する単一のブロックチェーンノード又はエンティティが存在しないという点で非集中的である。その代わりに、ブロックチェーンノードのそれぞれは、ブロックチェーン台帳を検証し、他のブロックチェーンノードにより行われたアクションがルールと一致していることを検証するために、ブロックチェーンプロトコルのルールを認識するようにプログラムされる。「ブロックチェーン」という用語は、ブロックチェーン台帳が一連の連結されたブロックを含み、それぞれがコンピュータメモリ内のデータ構造として表現可能であり、コンピュータプロセスにより読み取り可能であり、データ伝送として送信可能であるという事実を示してもよい。ブロックは、1つ以上のトランザクションを含み、これも、コンピュータメモリ内のデータ構造として表現可能であり、コンピュータプロセスにより読み取り可能であり、データ伝送として送信可能である。ブロックは、ブロックチェーンに公式に追加されるそれぞれの新たなブロックが直前のブロックへの不変の参照を含み、これがその直前のブロックへの不変の参照を含み、以下同様に行われるという点で連結される。
【０００５】
所与のトランザクションがブロックチェーンに書き込まれるブロックに含まれるために、1つ以上のノードが所与のトランザクションを承認し、場合によってはトランザクションを他のノードに伝搬し、ノードは、ブロックが所定のトランザクションを含むトランザクションのブロックをマイニングし、他のノードは、ブロックの有効性とそのブロック内のトランザクションの有効性とを検証する。マイニングノードはこれらのルールを意識してプログラム又は構成されるので、マイニングノードは、ブロックを無効にするトランザクションをブロックに含める可能性は低い。その理由は、このようなブロックは、他のノードにより受け入れられず、マイニングノードは利益を取得しないことになるためである。例えば、多くのブロックチェーンネットワークでは、ブロックは「報酬(reward)」トランザクションを含むことができ、指定の量の価値がマイニングノードのオペレータに割り当てられる。このように、成功したマイナーは、そのブロックによって作成された価値により補償される。さらに、トランザクションはトランザクション料を含むことができ、これもマイニングノードのオペレータにとって有益になる。
【０００６】
ブロックチェーンネットワークにおけるトランザクションは、価値の単位及び他のデータ要素を含む様々なデータ要素を含む。価値の単位は(ビットコインSVのような)暗号通貨とすることができるが、他のデジタル資産を使用する他のバリエーションも可能である。非集中的な分散台帳システムでは、誰もが台帳を閲覧して台帳のブロックに記憶されているトランザクションにアクセスできるように、台帳は公開とすることができる。
【０００７】
ブロックチェーンネットワーク、例えば、ビットコインブロックチェーンネットワークは、各トランザクションがマイニングのために他のノードに伝搬できる前に承認される必要があるので、トランザクションのネットワーク伝搬における遅延により引き起こされる、トランザクション承認に関する性能の制限を受ける可能性がある。さらに、ブロックチェーンのサイズが大きくなるにつれて、トランザクション及びブロックを承認するノードの記憶要件も同様に大きくなる。
【発明の概要】
【０００８】
したがって、分割又はシャーディング(sharding)の使用を通じてブロックチェーン台帳のスケーラビリティを改善する改善されたシステム及び方法を提供することが望ましい。
【０００９】
ブロックチェーンネットワークをシャード(shard)に分割することは、ユーザがブロックチェーンネットワークとの関与の自分のレベルを選択することを可能にする。各ユーザは、1つ以上のシャードのメンバーになることを選択できる。全てのシャードよりも少ないメンバーであるユーザは、ユーザがメンバーであるシャードに割り当てられたトランザクションの全てを記憶するために、より少ない記憶空間を必要とする。トランザクションIDに基づいてトランザクションをシャードに割り当てることは、結果としてのシャードのサイズがほぼ等しくなるという利点を提供し、それにより、より小さいシャードのメンバーに対してより大きいシャードのメンバーに過度の負担をかけることを回避し、同時に、トランザクション及び関連する検証が過度の遅延なく正確に実行されることを可能にする。
【００１０】
ここで言及されるユーザは、1つ以上のノード又は計算デバイスに関連付けられてもよく、これらのノードはまた、分割されたブロックチェーンネットワーク内のクライアントエンティティとも呼ばれてもよい。以下、ユーザへの言及はまた、ユーザに関連付けられたノード又はエンティティ(シャード又は分割されたブロックチェーンネットワークの一部であるノード又はエンティティを所有又は制御してもよい)への言及であると理解されてもよい。各ノードは、分割されたブロックチェーンネットワーク内の少なくとも1つ以上の他のノードと通信可能に結合されてもよい。
【００１１】
本開示の他の態様(以下に説明する)と共に、これに関連してここで説明するこれらの利点は、ノードの構造と、シャードされたブロックチェーンネットワークの結果のネットワークトポロジー及びアーキテクチャと、ネットワークのノードに関連するプロトコルに起因する。このようなシャードされたネットワークにおいてUTXOを受信、記憶及び/又は承認することは、異なるシャードに属するノードとの通信に関連するルール及びプロトコルに基づいて、各シャード内のノードについての承認技術と共に、通信、データ記憶、データ共有のための、説明すると共に特許請求の範囲に記載される方法、ルール又はプロトコルを使用して実行される。
【００１２】
これらの特定の構造、データフローの方法、トランザクション割り当て及び承認プロトコルについて、本開示の様々な実施形態に関して以下に更に説明する。有利には、シャードされたブロックチェーンネットワーク内のトランザクションの割り当て及びこのような割り当てられたトランザクションの承認のためにここに記載されるシャードされたネットワーク構造又はアーキテクチャ及び関連する方法は、データフロー、データ記憶及びUTXO承認チェックのための新規な技術を可能にする。さらに、これらの技術は、構造及びデータ通信/承認プロトコルの観点から、ビットコインブロックチェーンにおけるシビル攻撃のような二重支出攻撃を有利に防止する。
【００１３】
したがって、本開示によれば、シャードされたブロックチェーンネットワークのノードの間でブロックチェーンのブロックを維持管理するコンピュータ実施方法及びシステムが提供されてもよく、各ノードは複数のアクティブなシャードのうち1つ以上のシャードのメンバーである。当該方法及びシステムは、複数のアクティブなシャードの特定のサブセットのメンバーである所与のノードを使用し、所与のノードは、ブロックチェーンの新たなブロックを表すデータを生成し、新たなブロックを表すデータを記憶するように構成される。このようなデータは、i)新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連するトランザクションのトランザクション識別子のリスト、及び/又はii)新たなブロックの部分マークルツリー(Partial  Merkle  Tree)を含む。i)のトランザクション識別子のリストは、新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連しないトランザクションのトランザクション識別子を含まない。
【００１４】
実施形態では、i)のトランザクション識別子のリストは、新たなブロックに含まれるデータに基づいて、新たなブロックのトランザクション識別子の初期リストを構築し、複数のアクティブなシャードの特定のサブセットに関連しないトランザクションに対応するいずれかのトランザクション識別子を除去することによってトランザクション識別子の初期リストを処理することにより生成できる。
【００１５】
実施形態では、ii)の部分マークルツリーは、新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連しないトランザクションから導出されたハッシュ値を含み、一方で、新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連するトランザクションから導出されたハッシュ値を省略する。
【００１６】
実施形態では、ii)の部分マークルツリーは、新たなブロックに含まれるデータに基づいて新たなブロックの全マークルツリー(Full  Merkle  Tree)を構築し、新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連するトランザクションから導出されたハッシュ値を、プレースホルダ(placeholder)に置き換えることにより生成できる。
【００１７】
実施形態では、全マークルツリーの処理は、全マークルツリーの最下位レベルからルートレベルまで反復し、隣接ノード対についての2つのハッシュ値を除去し、親ハッシュ値を残すことを更に含むことができる。
【００１８】
実施形態では、全マークルツリーの処理は、全マークルツリーの最下位レベルからルートレベルまで反復し、複数のアクティブなシャードの特定のサブセットに関連しないトランザクションから導出されたハッシュ値を共に表さない2つの子ノードを有する親ツリーノードのハッシュ値を、プレースホルダに置き換えることを更に含むことができる。
【００１９】
実施形態では、ノードは、ブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連しないトランザクションへのアクセスを必要とせずに、ブロック承認のためのマークルルートハッシュ値を計算するために部分マークルツリーを処理するように動作できる。
【００２０】
実施形態では、マークルルートハッシュ値を計算するための部分マークルツリーの処理は、部分マークルツリーの最下位レベルからルートレベルまで反復し、最下位レベルにおけるいずれかのプレースホルダを、i)のトランザクション識別子リストからの対応するハッシュ値に置き換え、最下位レベルの上のレベルにおけるいずれかのプレースホルダを、部分マークルツリーの対応する子ハッシュ値から計算されたハッシュ値に置き換えることを含むことができる。
【００２１】
実施形態では、i)のトランザクション識別子のリスト及びii)の部分マークルツリーは、ノードのメンバーシップ及びシャードの間のトランザクションの割り当てに基づいてノードの間で変化できる。
【００２２】
実施形態では、新たなブロックの一部であるトランザクションは、トランザクション識別子に基づいて、複数のアクティブなシャードのうちのシャードに関連付けられる(又は割り当てられる)ことができる。
【００２３】
他の実施形態では、新たなブロックの一部であるトランザクションは、親ブロックチェーントランザクションに基づいて、複数のアクティブなシャードのうちのシャードに関連付けられる(又は割り当てられる)ことができ、親トランザクションは、子ブロックチェーントランザクションのインプットに対応するアウトプットにより定義され、親トランザクション及び子トランザクションの双方は、同じシャードに関連付けられる。
【００２４】
実施形態では、ノードにより維持管理されるブロックデータは、ノードが属さないシャードの一部であるトランザクションデータを省略でき、したがって、ノード記憶空間を節約する。したがって、いくつかのノードはブロックチェーンのトランザクションの限られたサブセットのみについてブロックチェーンのデータ構造を記憶でき、一方で、他のノードはブロックチェーンのトランザクションの全てについてデータ構造を記憶できる。この場合、ブロックチェーンの限られたサブセットについてデータ構造を記憶するノードのデータ記憶容量は、全体のブロックチェーンについてデータ構造を記憶するノードのデータ記憶容量よりもはるかに小さくなり得る。
【００２５】
実施形態では、新たなブロックを表すデータを生成するとき、ノードは、新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連するトランザクションを承認でき、一方で、新たなブロックの一部であり且つ複数のアクティブなシャードの特定のサブセットに関連しないトランザクションの承認をバイパスできる。このような処理は、ブロック承認動作の計算作業を低減できる。この利点は、ブロックチェーンネットワークの特定のシャードについての低減したデータ記憶容量要件と共に、限られた計算リソースを有するノードがブロックチェーンネットワークに効果的に参加することを可能にできる。
【００２６】
したがって、本開示によれば、添付の特許請求の範囲に定義される方法が提供される。
【００２７】
本開示によれば、プロセッサと、コンピュータメモリと、ネットワークインタフェースデバイスとを含む電子デバイスが提供されてもよい。メモリは、実行されると、ここに記載の方法を実行するようにプロセッサを構成するコンピュータ実行可能命令を記憶している。
【００２８】
本開示によれば、非一時的なコンピュータ読み取り可能記憶媒体が提供されてもよい。コンピュータ読み取り可能記憶媒体は、実行されると、ここに記載の方法を実行するようにプロセッサを構成するコンピュータ実行可能命令を含む。
【図面の簡単な説明】
【００２９】
本開示のこれらの態様及び他の態様は、ここに記載の実施形態から明らかになり、それを参照して説明される。本開示の実施形態について、例のみとして、添付の図面を参照して以下に説明する。
【図１Ａ】様々な実施形態が実装できるブロックチェーンネットワークを示す。
【図１Ｂ】図１Ａのブロックチェーンネットワークにより維持管理でき、様々な実施形態が実装できるブロックチェーン台帳及び代表的なブロックを示す。
【図２】例示的なシャードされたブロックチェーンネットワークのノードを、このようなノードにより維持管理されるシャードされたブロックチェーン台帳のデータ構造と共に示す。
【図３Ａ】図２のシャードされたブロックチェーン台帳のようなシャードされたブロックチェーン台帳の一部としてのブロックチェーントランザクションの作成及び承認及びマイニングを示すフローチャートである。
【図３Ｂ】図２のシャードされたブロックチェーン台帳のようなシャードされたブロックチェーン台帳の一部としてのブロックチェーントランザクションの作成及び承認及びマイニングを示すフローチャートである。
【図４Ａ】マイナーにより生成された新たなブロックを承認する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートである。
【図４Ｂ】マイナーにより生成された新たなブロックを承認する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートである。
【図５】新たなブロックの部分マークルツリーを構築する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートである。
【図６Ａ】図５の動作の概略図である。
【図６Ｂ】図５の動作の概略図である。
【図６Ｃ】図５の動作の概略図である。
【図６Ｄ】図５の動作の概略図である。
【図７Ａ】ノードにより維持管理されるブロックデータを承認する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートであり、このような動作は、部分マークルツリーについてのマークルルートハッシュ値を計算するために、ブロックの部分マークルツリーを処理する。
【図７Ｂ】ノードにより維持管理されるブロックデータを承認する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートであり、このような動作は、部分マークルツリーについてのマークルルートハッシュ値を計算するために、ブロックの部分マークルツリーを処理する。
【図７Ｃ】ノードにより維持管理されるブロックデータを承認する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートであり、このような動作は、部分マークルツリーについてのマークルルートハッシュ値を計算するために、ブロックの部分マークルツリーを処理する。
【図７Ｄ】ノードにより維持管理されるブロックデータを承認する際に、全てのシャードのメンバーではないノードにより実行される動作を記述するフローチャートであり、このような動作は、部分マークルツリーについてのマークルルートハッシュ値を計算するために、ブロックの部分マークルツリーを処理する。
【図８Ａ】図７Ａ〜図７Ｄの動作の概略図である。
【図８Ｂ】図７Ａ〜図７Ｄの動作の概略図である。
【図８Ｃ】図７Ａ〜図７Ｄの動作の概略図である。
【図８Ｄ】図７Ａ〜図７Ｄの動作の概略図である。
【図９】様々な実施形態が実装できる計算環境を示す。
【発明を実施するための形態】
【００３０】
まず図１Ａに参照が行われ、図１Ａは、本開示の実施形態によるブロックチェーンに関連する例示的なブロックチェーンネットワーク100を示す。実施形態では、ブロックチェーンネットワーク100は、ブロックチェーンノードのオペレータの間で全体的或いは部分的に合意されたブロックチェーンプロトコルに従う動作を実行するソフトウェア及び/又はハードウェアのインスタンスをそれぞれ実行するピアツーピア分散電子デバイスとして実装され得るブロックチェーンノードを含む。いくつかの例では、これらの分散電子デバイスは、図１Ａのノード102のように、単に「ノード(node)」と呼ばれる。ブロックチェーンプロトコルの例はビットコインプロトコルである。
【００３１】
ノード102は、いずれか適切な計算デバイス(例えば、データセンタ内のサーバ、デスクトップコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、スマートフォン等のクライアント計算デバイス)、計算リソースサービスプロバイダの分散システム内の複数の計算デバイス、又は図９の計算デバイス2600のようないずれか適切な電子クライアントデバイスを含んでもよい。ノード102は、他のノードに関する情報と共に、トランザクション及び/又はブロックを表すデータメッセージ又はオブジェクトを受信するための入力を有することができる。ノード102は、例えば、トランザクションの状態の認識のようなこれらが維持管理する情報について問い合わせ可能でもよい。
【００３２】
図１Ａに示すように、いくつかのノード102は、ノード102のうち1つ以上の他のノードに通信可能に結合される。どのノード102がどの他のノードと通信できるかに関して、これらの詳細は、中央で決定される必要はない。ブロックチェーンプロトコルが転送するべきメッセージであると仮定して、ブロックチェーンネットワーク100内のアクティブなノードは、1つのノード102から他のノード102に渡されるメッセージがブロックチェーンネットワーク100(又は、そのかなりの部分)を通じて伝搬できるように、1つ以上の他のノード102と通信できることで十分になり得る。1つのこのようなメッセージは、ノード102Aのうち1つによる提案されたトランザクションの公開であり、これは、次いでパス106のようなパスに沿って伝搬する。他のこのようなメッセージは、ブロックチェーンに含めるために提案された新たなブロックの公開でもよい。
【００３３】
ノード102は、トランザクションに対応するデータ及びトランザクションのブロックに対応するデータを含む分散ブロックチェーン台帳(又はブロックチェーン)を記憶できる。ノード102は、ブロックチェーン台帳の完全なコピー又はその一部を記憶できる。例えば、いくつかのノードは、全体のブロックチェーン台帳のデータを記憶してもよく、一方で、他のノードは、未使用のトランザクションのみのデータを記憶してもよく、一方で、他のノードは、全体のブロックチェーン台帳を維持管理してもよい。ノード102は、受信した各ブロック及びこのようなブロック内のトランザクションを承認する機能を含んでもよい。ノード102のうちいくつかは、新たなブロックがブロックチェーン台帳に追加できるように、トランザクションを収集してトランザクションのブロックを作成するマイナーノードとすることができる。マイナーノードは、(不正なノードが容易に不適切なブロックを作成することを回避するために)複雑であり且つ(不正なノードが事前に複雑な動作を実行できないように)含まれるトランザクションのデータに依存するいくつかの作業を実行することが想定されてもよく、これらの作業の実行は、他のノードにより容易に検証される。場合によっては、複数のマイナーノードが、新たなブロックを作成する際に必要な作業を実行することを競合する可能性がある。これは「プルーフオブワーク(proof-of-work)」マイニングと呼ばれる。代替として、新たなブロックのマイナーノードは、ステーク(stake)としても定義されるその富に依存して決定論的な方法で選択できる。これは「プルーフオブステーク(proof-of-stake)」マイニング又はフォージングと呼ばれる。マイナーノードは、承認のために新たなブロックを他のノードに伝搬する。他のノードは、新たなブロック及び新たなブロックに埋め込まれたトランザクションを承認する。ノードにより実行された承認動作が成功すると、ノードは新たなブロックをブロックチェーンに追加し、新たなブロックを他のノードに伝搬する。これは、ブロックチェーン台帳への新たなブロックをコミットする。
【００３４】
いくつかの例では、ブロックはトランザクションのグループ化であり、しばしば前のブロックのタイムスタンプ及び「指紋(fingerprint)」(例えば、ハッシュ)でマーキングされる。このように、各ブロックが前のブロックに連結されることになり、それにより、ブロックチェーン台帳においてブロックを連結する「チェーン(chain)」を作成する。各ブロックは、そのブロックのトランザクションのグループを示すデータ(例えば、トランザクション識別子)を含む。実施形態では、有効なブロックは、ブロックチェーンネットワーク内のノードのコンセンサスによりブロックチェーン台帳に追加される。また、いくつかの例では、ブロックチェーン台帳は、承認されたブロックの順序付きのリストを含む。図１Ｂは、3つのブロック1221、1223及び1223のチェーンを有するブロックチェーン台帳1216を示す。ブロック1222は、ブロック1222についてのトランザクションのグループを示すデータ(例えば、ブロックヘッダ1230及びトランザクション識別子1231(1)、1231(2)、1231(3)…)を含む点に留意する。
【００３５】
本開示は、分割の使用を通じてブロックチェーン台帳のスケーラビリティを改善することを目的とする。当該技術分野における分割は、2つの特定の次元、すなわち、水平次元及び垂直次元を考慮する。水平分割では、データは、シャードとして知られる異なるセクションに分割され、異なるセクションは、事実上、特定のデータベーススキーマの複数のインスタンスであり、データはこれらのインスタンスのそれぞれの間に広がる(インスタンスの冗長性を割り引く)。垂直分割では、所与のデータベーススキーマが複数のノードの間に分散され、それにより、特定のオブジェクトの属性が正規化を使用して分散される。
【００３６】
本開示は、「シャード(shard)」と呼ばれる関連するノードのグループの中でのブロックチェーン台帳のデータ構造のために水平分割方式を使用する。各シャードは固有の識別子を割り振られる。全てのシャードを包含する「全シャード(All  Shards)」と呼ばれる1つのグループが存在する。ブロックチェーンネットワークの各ノードは、1つ以上のシャード(「全シャード」グループを含む)に属することができる。シャードに属するノードは、そのシャードのメンバーと呼ばれてもよい。図２の例では、ノードA1及びA2はシャードAのメンバーであり(属する)、ノードB1及びB2はシャードBのメンバーであり(属する)、ノードCはシャードA及びBのメンバーであり(属する)、ノードDは「全シャード」グループのメンバーである(属する)。他のシャードも同様に使用できる。さらに、各ノードは、属する1つ以上のシャードに対応するブロックチェーン台帳のデータ構造を記憶するように構成される。図２の例では、ブロックチェーン台帳のデータ構造は、シャードについてのUTXOセットと、シャードについてのトランザクションキュー(メモリプール(mempool))と、シャードについてのトランザクションデータ(TXデータとラベル付けされる)と、シャードについてのブロックデータとを含む、シャードについてのビットコイン関連のデータ構造を含む。シャードについてのUTXOセットは、新たなトランザクションへのインプットとして使用できる未使用のトランザクションアウトプット(unspent  transaction  output,  UTXO)を表す。
【００３７】
ここに記載の実施形態では、所与のノードにより維持管理されるブロックデータは、所与のノードが属する1つ以上のシャードについてのブロックデータを含む。このようなブロックデータは、ブロックチェーン台帳のブロックを表すデータを含み、ブロック毎に以下のデータ、すなわち、i)ブロックの他のデータと共に部分マークルツリーを含むブロックヘッダ、及び/又はii)ブロックの一部であるトランザクションのトランザクション識別子のリストを含むことができる。このリストは、ブロックの一部であり且つ所与のノードが属する1つ以上のシャードに関連するトランザクションのみのトランザクション識別子を含み、このリストは、ブロックの一部であり且つ所与のノードが属する1つ以上のシャードに関連しないトランザクションのトランザクション識別子を含まない。ブロックヘッダに記憶される部分マークルツリーは、ブロックの一部であり且つ所与のノードが属さない1つ以上のシャードに関連するトランザクションから導出されたハッシュ値を含み、一方で、ブロックの一部であり且つ所与のノードが属する1つ以上のシャードに関連するトランザクションから導出されたハッシュ値を省略する。部分マークルツリーは、ノードがブロックの一部であり且つノードが属する1つ以上のシャードに関連しないトランザクションへのアクセスを必要とせずに、ブロック承認のためにブロックのマークルルートハッシュ値を計算することを可能にするために使用できる。このように、異なるシャードのノードによりブロックデータの一部として記憶される所与のブロックのi)の部分マークルツリー及びii)のリストは、ノードのメンバーシップ及びシャードの間のトランザクションの分配に基づいて、ノードの間で変化できる。有利には、本実施形態に記載のように、ブロックのブロックヘッダ及び他のデータと関連して部分マークルツリーを使用することは、各ノードが、所与のトランザクションに関連する全てのUTXOを記憶及び承認することなく、ブロックが承認及び伝搬されるために必要な詳細を依然として正確に保持及び使用するために、各ノードが記憶できるか或いは記憶できない情報を確立するための、ここに記載のプロトコルと共にシャードされたブロックチェーンネットワークの構造の観点から可能になる。ここで更に説明するように、ブロック情報を処理するための部分マークルツリーの作成及び使用は、ノードが関連するシャードの外部の1つ以上のノードとの通信及びデータフローのための他のプロトコルに加えて、シャードされたネットワークのこのような構造と、同じシャード内の通信及びデータフローのためにシャードされたネットワーク内のノードにより適用されるプロトコルとにより実現される。
【００３８】
図２の例では、ノードA1及びA2は、シャードAについてのUTXOセットのコピーと、シャードAについてのトランザクションキュー(メモリプール)のコピーと、シャードAについてのトランザクションデータのコピーと、シャードAについてのブロックデータのコピーとを記憶する。ノードA1及びA2は、以下のもの、すなわち、他のシャード(シャードA以外)についてのUTXOセットのコピー、他のシャード(シャードA以外)についてのトランザクションキュー(メモリプール)のコピー及び他のシャード(シャードA以外)についてのトランザクションデータのコピーを記憶しない。さらに、シャードAについてのブロックデータは、ブロックチェーン台帳のブロックを表すデータを含み、ブロック毎に以下のデータ、すなわち、i)ブロックの他のデータと共に部分マークルツリーを含むブロックヘッダ、及びii)ブロックの一部であるトランザクションのトランザクション識別子のリストを含むことができる。このリストは、ブロックの一部であり且つシャードAに関連するトランザクションのみのトランザクション識別子を含み、このリストは、ブロックの一部であり且つシャードAに関連しないトランザクションのトランザクション識別子を含まない。ブロックヘッダに記憶される部分マークルツリーは、ブロックの一部であり且つシャードAに関連しないトランザクションから導出されたハッシュ値を含み、一方で、ブロックの一部であり且つシャードAに関連するトランザクションから導出されたハッシュ値を省略する。
【００３９】
ノードB1及びB2は、シャードBについてのUTXOセットのコピーと、シャードBについてのトランザクションキュー(メモリプール)のコピーと、シャードBについてのトランザクションデータのコピーと、シャードBについてのブロックデータのコピーとを記憶する。ノードB1及びB2は、以下のもの、すなわち、他のシャード(シャードB以外)についてのUTXOセットのコピー、他のシャード(シャードB以外)についてのトランザクションキュー(メモリプール)のコピー、他のシャード(シャードB以外)についてのトランザクションデータのコピーを記憶しない。さらに、シャードBについてのブロックデータは、ブロックチェーン台帳のブロックを表すデータを含み、ブロック毎に以下のデータ、すなわち、i)ブロックの他のデータと共に部分マークルツリーを含むブロックヘッダ、及びii)ブロックの一部であるトランザクションのトランザクション識別子のリストを含むことができる。このリストは、ブロックの一部であり且つシャードBに関連するトランザクションのみのトランザクション識別子を含み、このリストは、ブロックの一部であり且つシャードBに関連しないトランザクションのトランザクション識別子を含まない。ブロックヘッダに記憶される部分マークルツリーは、ブロックの一部であり且つシャードBに関連しないトランザクションから導出されたハッシュ値を含み、一方で、ブロックの一部であり且つシャードBに関連するトランザクションから導出されたハッシュ値を省略する。
【００４０】
ノードCは、シャードAについてのUTXOセットのコピーと、シャードBについてのUTXOセットと、シャードAについてのトランザクションキュー(メモリプール)のコピーと、シャードBについてのトランザクションキュー(メモリプール)のコピーと、シャードAについてのトランザクションデータのコピーと、シャードBについてのトランザクションデータのコピーと、シャードA及びBについてのデータブロックのコピーとを記憶する。ノードCは、以下のもの、すなわち、他のシャード(シャードA及びB以外)についてのUTXOセットのコピー、他のシャード(シャードA及びB以外)についてのトランザクションキュー(メモリプール)のコピー、及び他のシャード(シャードA及びB以外)についてのトランザクションデータのコピーを記憶しない。さらに、シャードA及びBについてのブロックデータは、ブロックチェーン台帳のブロックを表すデータを含み、ブロック毎に以下のデータ、すなわち、i)ブロックの他のデータと共に部分マークルツリーを含むブロックヘッダ、及びii)ブロックの一部であるトランザクションのトランザクション識別子のリストを含むことができる。このリストは、ブロックの一部であり且つシャードA又はBに関連するトランザクションのみのトランザクション識別子を含み、このリストは、ブロックの一部であり且つシャードA又はBに関連しないトランザクションのトランザクション識別子を含まない。ブロックヘッダに記憶される部分マークルツリーは、ブロックの一部であり且つシャードA又はBに関連しないトランザクションから導出されたハッシュ値を含み、一方で、ブロックの一部であり且つシャードA又はBに関連するトランザクションから導出されたハッシュ値を省略する。
【００４１】
ノードDは、全てのシャードについてのUTXOセットのコピーと、全てのシャードについてのトランザクションキュー(メモリプール)のコピーと、全てのシャードについてのトランザクションデータのコピーと、全てのシャードについてのブロックデータのコピーとを記憶する。
【００４２】
ノードにより維持管理されるブロックデータは、ノードが属さないシャードの一部であるトランザクションデータを省略することができ、したがって、ノードの記憶空間を節約する点に留意する。したがって、いくつかのノード(例えば、ノードA1、A2、B1、B2及びC)は、ブロックチェーン台帳のトランザクションの限られたサブセットのみについてブロックチェーン台帳のデータ構造を記憶し、一方で、他のノード(例えば、ノードD)は、ブロックチェーン台帳のトランザクションの全てについてデータ構造を記憶する。この場合、ブロックチェーンの限られたサブセットについてデータ構造を記憶するノード(例えば、ノードA1、A2、B1、B2及びC)のデータ記憶容量は、全体のブロックチェーン台帳についてデータ構造を記憶するノード(例えば、ノードD)のデータ記憶容量よりもはるかに小さくなり得る。他のブロックチェーン台帳では、異なるシャードについての他のデータ構造が記憶されて維持管理できる点に留意する。
【００４３】
図２の水平分割方式は、ノードのオペレータがブロックチェーンネットワークの1つ以上のシャードのメンバーになることを決めること又は選択することを可能にする。これは、限られたデータ記憶容量を有する小規模な関係者(趣味を楽しむ人等)が単一のシャードのメンバーになるのを選択することを可能にし、一方で、より大きいデータ記憶容量を有する大規模な関係者(金融機関等)は、全てのシャードのメンバーになるのを決めること又は選択することができる。
【００４４】
さらに、各ノードは、ノードが属する1つ以上のシャードに関連するトランザクションのみを承認するブロック承認動作を実行するように構成できる。このような動作では、ノードが属さない他のシャードに関連するいずれかのトランザクションの承認はバイパスされ、ブロックがノードにより有効であるとみなされるか否かに影響しない。この場合、単一のシャードのメンバーになることを選択したオペレータは、ブロックチェーン台帳における限られたセットのトランザクションを承認することにより、より軽量なセキュリティの関与を有し、一方で、全てのシェアーのメンバーになることを選択したオペレータは、ブロックチェーン台帳における全てのトランザクションを承認することにより、より大きいセキュリティの関与を有する。
【００４５】
ノードは、シビル攻撃を防止するために、単一のシャード内の複数の他のノードと通信するように構成できる点に留意する。これらの攻撃は、ノードから送信されたトランザクションを事実上無視でき、ネットワークを更に通じたこれらの伝搬を防止する。所与のシャード内の1つ以上のノードはまた、他のシャード内のノードに関する情報を交換するように割り振られることができ、このような割り振りは、所与のシャード内のノードの中で時間と共に回転できる。各ノードは、受信した全てのトランザクションを、これが結合される他のノードにブロードキャストでき、その所与のノードがそのシャードのメンバーでない場合、完全なトランザクション承認を行う代わりに、トランザクションを伝搬する前に基本的なトランザクションレベルのチェックを実行する。
【００４６】
異なる或いは特定の時間/インスタンスにおいて、他のノードに関する詳細もまた、特定のシャード内のノードの間で共有できる。これは、本開示の第2の実施形態に従って、addrプロトコルメッセージの修正バージョンを使用して実行される。ビットコインプロトコルの一部として現在存在するaddrメッセージの実装は、1つ以上のIPアドレス及びポートを列挙又は識別するために使用される。例えば、getaddr要求は、(例えば、ブートストラッピングのために)一束の既知のアクティブなピアを含むaddrメッセージを取得するために使用されてもよい。addrメッセージは、1つのアドレスのみをしばしば含むが、場合によっては更に多くを含み、いくつかの例では、1000個までを含む。いくつかの例では、全てのノードは、周期的に、すなわち、24時間毎に、自分のIPアドレスを含むaddrをブロードキャストする。次いで、ノードは、これらのメッセージを自分のピアに中継してもよく、新たなものである場合、中継されたアドレスを記憶できる。このように、ネットワーク内のノードは、ネットワークに接続した時点或いはその後に、どのIPがネットワークに接続されているかを合理的に明確に把握してもよい。ほとんどの場合、IPアドレスは、初期のaddrブロードキャストのため、全員のアドレスデータベースに追加される。
【００４７】
本開示による修正addrプロトコルの実装は、上記に加えて、特定のノードがどのシャードに属するかに関する更なる情報を送信できる。例えば、修正addrプロトコルでは、図１ｂのようなシャードされたネットワーク内のノードがネットワーク内の特定のシャードに参加するとき、addrメッセージの一部としてブロードキャストされるものはまた、それがメンバーである1つ以上のシャードを識別するフィールドを含んでもよい。したがって、この情報はまた、図１ｂのネットワーク内のピアからのgetaddr要求に応じて返信される。第1の実施形態で説明したように、このような情報は、各ノード及び/又はノードが関連する各シャードに関連するデータ構造に基づいてもよい。
【００４８】
図３Ａ及び図３Ｂは併せて、図２のシャードされたブロックチェーン台帳のようなシャードされたブロックチェーン台帳の一部としてのブロックチェーントランザクションの作成及び承認及びマイニングを示すフローチャートである。
【００４９】
ボックス301において、クライアントノードは、ブロックチェーントランザクションを生成し、ブロックチェーントランザクションは、ブロックチェーンネットワークの1つ以上のシャードに関連付けられる(或いは割り振られるか或いは割り当てられる)。有効なブロックチェーントランザクションに関連するシャードは、ブロックチェーントランザクション自体に関連するシャード、又は有効なブロックチェーントランザクションの1つ以上のトランザクションインプット若しくはトランザクションアウトプットに関連するシャードとすることができる。例えば、一実施形態では、有効なブロックチェーントランザクションに関連するシャードは、ブロックチェーントランザクションのトランザクションデータにSHA256関数を適用することによって作成されるブロックチェーントランザクションのトランザクション識別子に基づくことができる。より具体的には、有効なブロックチェーントランザクションに関連するシャードは、ブロックチェーンネットワーク上で現在アクティブなシャードの数のモジュロをトランザクション識別子に適用することにより、すなわち、シャード識別子=TX  ID  mod  nにより決定でき、nは現在アクティブなシャードの数である。他の実施形態では、有効なブロックチェーントランザクションに関連するシャードは、ブロックチェーントランザクションの最初のインプット又は他のインプットと、インプットが参照する前のトランザクションのアウトプットとに基づくことができる。この文脈では、後続のトランザクションの第1のインプットによりアウトプットが参照されるトランザクションは、「親」トランザクションと呼ばれ、後続のトランザクションは「子」トランザクションと呼ばれる。親を定義するための第1のインプットの使用は、当該方法に必須ではなく、複数のインプットが存在する場合、当該方法を実行するためにいずれかのインプットが選択されてもよい点に留意すべきである。例えば、前のトランザクションは、子トランザクションの特定の数のインプットが親と同じシャード内のトランザクションのアウトプットを参照する場合、子トランザクションの親として定義されてもよい。インプットの数は、子トランザクションのインプットの過半数と定義してもよい。これらのメカニズムの詳細は、英国特許出願番号1806907.0及び英国特許出願番号1806909.6に記載されており、これらは本出願の譲渡人に共通して譲渡されており、これらの全内容を参照により援用する。更に他の実施形態では、ブロックチェーントランザクションをブロックチェーンネットワークの1つ以上のシャードに関連付けるために、他のメカニズムが使用できる。
【００５０】
ボックス303において、クライアントノードは、ブロックチェーントランザクションに関連する1つ以上のシャードに属するノード(及び、場合によっては、ブロックチェーントランザクションに関連しないシャードに属する他のノード)への通信のために、ブロックチェーントランザクションをブロードキャストする。
【００５１】
ボックス305において、ブロックチェーントランザクションに関連する1つ以上のシャードに属するノードは、ブロックチェーントランザクションを受信する。
【００５２】
ボックス307において、ブロックチェーントランザクションに関連する1つ以上のシャードに属するノードは、受信したブロックチェーントランザクション又はその一部を承認し、このような各ノードは、受信したブロックチェーントランザクション又はその一部が有効であるとみなされた場合、ブロックチェーントランザクションを、これが属するシャード内の他のノードに伝搬する。
【００５３】
一実施形態(「トランザクションシャード承認」と呼ばれる)では、ボックス307のトランザクション承認は、トランザクションが関連するか或いは割り当てられているシャードにより実行される。上記のように、トランザクションは、トランザクションのトランザクション識別子に適用されるモジュロ関数の結果を使用して、シャードに関連付けられる(或いは割り振られる)ことができる。トランザクションは異なるシャードからのインプットを有することができるので、ノードは、UTXOチェックのために他のシャードのノードと通信できる。具体的には、1つ以上のシャードに属するノードは、他のシャードに属するノードに対して、他のシャードについてのUTXOセットを取得するように要求を行うことができる。どのノードも要求されたUTXOセットを有さない場合、ヌル応答が与えられ、問題のトランザクションは無効と見なされる。トランザクションインプットが有効であるとみなされた場合、トランザクションは、トランザクションが関連するか或いは割り当てられているシャードについてのトランザクションキュー(メモリプール)に追加され(ボックス309)、トランザクションは、このシャード内の他のノードに伝搬される(ボックス311)。
【００５４】
他の実施形態(「UTXOシャードベースの承認」と呼ばれる)では、ボックス307のトランザクション承認は、承認を実行するノードと同じシャード内にあるUTXOセットに関連するインプットに基づいてトランザクションを承認する。異なるシャード内のUTXOセットに関連するインプットは承認されない。各インプットの承認は、参照されたアウトプットのUTXOが使用されていないことをチェックすることと、インプットが参照されたアウトプットの値を収集することを許可されていることを検証すること(例えば、スクリプト検証)と、他の多くのチェックとを含むことができる。インプットが無効である場合(インプットに関連するUTXOが存在しない場合、トランザクションのアウトプットの値が対応するインプットのUXTOよりも大きい場合、又はスクリプトエラーが存在する場合等)、トランザクションは破棄され、同じシャード内の他のノードに伝搬されない。インプットが有効であるとみなされた場合、トランザクションは、承認を実行するノードのために、シャードのトランザクションキュー(メモリプール)に追加され(ボックス309)、トランザクションは、このシャード内の他のノードに伝搬される(ボックス311)。
【００５５】
「トランザクションシャード承認」の実施形態及び「UTXOシャードベースの承認」の実施形態の詳細は、英国特許出願番号1806911.2及び英国特許出願番号1806914.6に記載されており、これらは本出願の譲渡人に共通して譲渡されており、これらの全内容を参照により援用する。
【００５６】
実施形態では、ボックス307のトランザクションの承認はまた、トランザクションの構文及びデータ構造が正しいことをチェックすること、トランザクションが許容されるブロックサイズよりも小さく且つ100バイト以上であることをチェックすること、及びロックタイム(locktime)が最大許容数よりも小さいことをチェックすることのように、全体としてのトランザクションに関連するチェックを含むことができる。
【００５７】
ボックス309において、有効なブロックチェーントランザクションに関連するシャードに属するノードは、その有効なブロックチェーントランザクションを、有効なブロックチェーントランザクションに関連するシャードについてのトランザクションキュー(メモリプール)に追加する。
【００５８】
ボックス311において、1つ以上のノード(例えば、マイナー)は、シャードについてのトランザクションキュー(メモリプール)  (例えば、「全シャード」グループについてのメモリプール)からブロックを形成し、この新たなブロックを他のノードに伝搬する。
【００５９】
ボックス313において、ノードは、新たなブロックを受信し、コンセンサスプロトコルに基づくブロックの承認及びコミットメントのために新たなブロックを処理する。
【００６０】
図４Ａ及び図４Ｂは併せて、全てのシャードのメンバーではないノードのマイナーにより生成された新たなブロックを承認する際の図３Ａ及び図３Ｂのボックス313の動作を説明するフローチャートである。この場合、ノードは、アクティブなシャードの限られたサブセットに属し、したがって、1つ以上のアクティブなシャードに属さない。全てのシャードのメンバーであるいずれかのノードは、周知のブロック承認プロセスを使用して新たなブロックを承認できる点に留意する。
【００６１】
ボックス401において、ノードは新たなブロックを受信する。実施形態において、ブロックは、ブロックのTX識別子の順序付きのシーケンスを表すリストデータ及びブロックヘッダを含む。図２に示すようなビットコイン型の分散ブロックチェーンシステムでは、ブロックヘッダは以下のデータフィールドを含むことができる。
[1]ブロックバージョン番号は、どのセットのブロック承認ルールに従うべきかを示す。
[2]前のブロックのヘッダのハッシュは、前のブロックのヘッダの内部バイトオーダーのSHA256(SHA256())ハッシュである。これは、このブロックのヘッダを変更せずには、前のブロックが変更できないことを確保する。
[3]このブロックに含まれる全てのトランザクションのハッシュから導出されたマークルルートハッシュは、ヘッダを修正せずには、これらのトランザクションのいずれも修正できないことを確保する。
[4]ブロック時間は、(マイナーに従って)マイナーがヘッダのハッシュを開始したUNIX（登録商標）のエポック時間である。
[5]nBitsは、このブロックのヘッダハッシュがそれ以下でなければならないターゲット閾値の符号化されたバージョンである。
[6]ナンス(nonce)は、ターゲット閾値以下のハッシュを生成するために、ヘッダハッシュを修正するためにマイナーが変更する任意の数である。
【００６２】
これらのフィールドの例が図６Ａに示されている。
【００６３】
ボックス403において、ノードは、ボックス401において受信したブロックに記憶されたトランザクション識別子(「TX識別子」又は「TX  ID」)の順序付きのシーケンスを表すリストを抽出する。ブロックのトランザクション識別子の例示的なリストが図６Ａに概略的に示されている。
【００６４】
ボックス405において、ノードは、ボックス403において抽出されたブロックのトランザクション識別子の順序付きのシーケンスについての全マークルツリーを表すデータを生成する。全マークルツリーは、ブロックのトランザクション識別子の順序付きのシーケンスに対応するリーフノードの順序付きのシーケンスを有するツリーである。各リーフノードは、対応するトランザクション識別子により参照されるトランザクションデータのハッシュを含み、全ての非リーフノードは、その子ノードのハッシュ値の暗号ハッシュを含む。全マークルツリーの非リーフノードは、論理的に、リーフ(最下位)からルートまで上向きに延在するレベルで編成され、ルートは、周知のように全マークルツリーのルートハッシュ値を記憶する。ブロックの例示的な全マークルツリーが図６Ａに概略的に示されている。
【００６５】
ボックス407において、ノードは、ボックス401において受信したブロックのヘッダに記憶されているマークルルートハッシュ値を抽出し、ノードは、抽出されたマークルルートハッシュ値を、ボックス405において生成された全マークルツリーのルートハッシュ値と比較する。
【００６６】
ボックス409において、ノードは、ボックス407の比較を評価し、抽出されたマークルルートハッシュ値がボックス405において生成された全マークルツリーのルートハッシュ値と一致するか否かを決定する。そうでない場合、動作はボックス439及び441に進む。そうである場合、動作はボックス411に進む。
【００６７】
ボックス411において、ノードは、ブロックの有効性について他のヘッダ条件を評価する。
【００６８】
ボックス413において、ノードは、ブロックの有効性についての全ての他のヘッダ条件が満たされているか否かを決定するために、ボックス411の評価をチェックする。そうでない場合、動作はボックス439及び441に進む。そうである場合、動作はボックス415に進む。
【００６９】
ボックス415において、ノードは、ボックス403において抽出されたブロックのトランザクション識別子の順序付きのシーケンスを通じてループを構成し、ループ内のそれぞれの所与のトランザクション識別子に対してボックス417〜425の動作を実行する。
【００７０】
ボックス417において、ノードは、所与のトランザクション識別子により参照されるトランザクションに対応するシャードを識別する。トランザクションに対応するシャードは、トランザクション自体に関連するシャード、又はトランザクションの1つ以上のトランザクションインプット又はトランザクションアウトプットに関連するシャードでもよい。トランザクションと1つ以上のシャードとの間の関連付け(又は対応関係)を指定するために使用できるメカニズムの例は、図３Ａ及び図３Ｂのボックス301に関して上記に記載されている。
【００７１】
ボックス419において、ノードは、それがボックス417において識別されたシャードに属するか否かをチェックする。そうでない場合、動作はボックス421に進む。そうである場合、動作はボックス422に進む。
【００７２】
ボックス421において、ノードは、ボックス403において抽出されたブロックのトランザクション識別子の順序付きのシーケンスから所与のトランザクション識別子を除去し、動作はボックス425に進む。
【００７３】
ボックス423において、ノードは、所与のトランザクション識別子により参照されるトランザクションが有効であるか否かをチェックする。所与のトランザクション識別子により参照されるトランザクションが有効であると決定された場合、動作はボックス425に進む。そうでない場合、動作はボックス439及び441に進む。実施形態では、ノードは、所与のトランザクション識別子により参照されるトランザクションが、ノードが属するシャードについてのトランザクションキュー(メモリプール)に記憶されていることをチェックできる。そうである場合、トランザクションは有効であるとみなされることができ、動作はボックス425に進む。そうでない場合、ノードは、トランザクションのコピーを要求して取得するために、ネットワークの他のノードと通信できる。一旦受信すると、ノードは、受信したトランザクションを承認するための動作を実行できる。このような承認動作の例は、図３Ａ及び図３Ｂのボックス307を参照して上記に記載されている。トランザクションが有効であるとみなされた場合、動作はボックス425に進む。トランザクションが無効であるとみなされた場合、動作はボックス439及び441に進む。
【００７４】
ボックス425において、ノードは、全てのトランザクション識別子が、ボックス415において構成されたトランザクション識別子の順序付きのシーケンスを通じてループ内で処理されたか否かをチェックする。そうでない場合、動作はボックス415に戻り、リスト内の次のトランザクション識別子に対してループを継続する。そうである場合、動作はボックス427に進む。
【００７５】
ボックス419〜425の動作は、ノードが属するシャードに関連するトランザクションの有効性をチェックし、したがって、ノードが属さないシャードに関連するトランザクションの有効性をチェックすることをバイパスする点に留意する。
【００７６】
ボックス427において、ノードは、ブロックを有効としてマーキングするデータを生成して記憶できる。
【００７７】
ボックス429において、ノードは、ブロックのトランザクション識別子の結果リストを含むデータを記憶する。トランザクション識別子のこの結果リストは、ノードが属さないシャードに関連するトランザクション識別子を省略でき、したがって、ブロックのトランザクション識別子の順序付きのシーケンスの全リストを記憶することを回避する。
【００７８】
ボックス431において、ノードは、ブロックの部分マークルツリーを表すデータを導出する。このような動作の詳細について、図５を参照して以下に説明する。
【００７９】
ボックス433において、ノードは、ボックス431において導出されたブロックの部分マークルツリーを含むように、ブロックのヘッダデータを更新する。
【００８０】
ボックス435において、ノードは、ブロックを表すデータ(ボックス433においてブロックの部分マークルツリーで更新されたヘッダと、ボックス429において記憶されたブロックの結果リストを含むデータとを含む)を、ノードが属する1つ以上のシャードについてのブロックデータの一部として記憶する。このような動作は、ディスク又は他の形式の永続データストレージのような、永続ストレージへのブロックを表すものを記憶できる。例示的なヘッダデータ及びブロックを表すトランザクションリストデータが図６Ｄに概略的に示されている。
【００８１】
ボックス431の部分マークルツリーは、ノードが属さないシャードに関連するトランザクションから導出された分岐を省略し、ノードが属するシャードに関連するトランザクションから導出された分岐に沿って(ハッシュ値の)プレースホルダを含めることができる点に留意する。したがって、多くの場合、部分マークルツリーのノード及びレベルは、全マークルツリーの通常の形式と比較して不均衡になる。重要なことに、部分マークルツリーを作成するための全マークルツリーを低減する動作は、ノードが属する1つ以上のシャードについてのブロックデータのヘッダ内の部分マークルツリーの記憶要件を低減するために使用できる。マークルツリーの分岐は、分岐又はその下のリーフの連結及びハッシュの産物であるので、全マークルツリーは、ツリー内の完全なパスに基づいて低減できる。分岐が完全なリーフをもたらす場合、そのハッシュのみを残して、これらの分岐は除去できる。マークルルートからリーフへの各ハッシュは、プレースホルダの置き換えにより部分マークルツリーのルートハッシュが再び作成できるように除去できる。このプロセスを実行することにより、部分マークルツリーにおいて記憶を必要とするハッシュの数が低減でき、記憶要件を低下させる。
【００８２】
ボックス437において、ノードは、ボックス401において受信した新たなブロックを他のノードに伝搬できる。
【００８３】
ボックス439において、ノードは、ブロックを無効としてマーキングするデータを生成して記憶できる。
【００８４】
ボックス441において、ノードは、無効なブロックを表すデータを破棄し、無効なブロックを他のノードに伝搬することを回避できる。ノードはまた、シャードに割り振られた無効なブロックの一部である1つ以上のトランザクションのトランザクションデータを破棄し、必要に応じて、このようなトランザクションのUTXOをシャードについてのUTXOセットに戻すこともできる。
【００８５】
図５は、ブロックの部分マークルツリーを表すデータを導出するためにノードにより実行される例示的な動作を示すフローチャートである。
【００８６】
ボックス501において、ノードは、ブロックヘッダと、ブロックのトランザクション識別子の順序付きのリストとを読み取る。
【００８７】
ボックス503において、ノードは、ボックス501において読み取られたブロックのトランザクション識別子のリストを使用して、ブロックの全マークルツリーを表すデータを生成する。
【００８８】
ボックス505において、ノードは、ブロックのトランザクション識別子の順序付きのリストのトランザクション識別子を通じてループを構成し、これは、全マークルツリーの最下位レベルにおけるハッシュ値(左から右へ)に対応する。ループは、リスト内の所与のトランザクション識別子毎にボックス507〜513の動作を実行する。
【００８９】
ボックス507において、ノードは、所与のトランザクション識別子により参照されるトランザクションが、ノードが属するシャードに対応するか否かをチェックする。トランザクションと1つ以上のシャードとの間の関連付け又は対応関係を指定するために使用できるメカニズムの例は、図３Ａ及び図３Ｂのボックス301に関して上記に記載されている。所与のトランザクション識別子により参照されるトランザクションが、ノードが属するシャードに対応しない場合、動作はボックス509及びボックス513に進む。所与のトランザクション識別子により参照されるトランザクションが、ノードが属するシャードに対応する場合、動作はボックス511に進む。
【００９０】
ボックス511において、ノードは、リストの所与のトランザクション識別子(ハッシュ値)をプレースホルダに置き換え、動作はボックス513に進む。プレースホルダは、リストのトランザクション識別子の符号化サイズよりも小さい符号化サイズのデータ値又は文字である。プレースホルダはまた、リストのトランザクション識別子の許容値から容易に区別できるように構成される。実施形態において、プレースホルダは、ヌル値又は特定の文字とすることができる。理想的には、プレースホルダは、256ビットハッシュに対して最大の空間削減を提供すべきである。代替として、プレースホルダは、256ビットハッシュに対して他の何らかの最小から最大の空間削減を提供できる。
【００９１】
ボックス513において、ノードは、ボックス505において構成されたトランザクション識別子を通じてループ内で処理されるべきいずれかのトランザクション識別子が残っているか否かをチェックする。そうである場合、動作はボックス505に戻り、リスト内の次のトランザクション識別子についてのループを継続する。そうでない場合、動作はボックス515に進む。
【００９２】
ボックス507〜513の動作は、ノードが属するシャードに対応するトランザクションを、全マークルツリーの最下位(リーフ)レベルにおけるトランザクション識別子からのプレースホルダに置き換える点に留意する。
【００９３】
ボックス515において、ノードは、マークルツリーの現在のレベルポインタを、ボックス503において生成されたデータにより表す全マークルツリーの最下位(又はリーフノードレベル)に設定する。
【００９４】
ボックス517において、ノードは、マークルツリーの現在のレベルポインタが全マークルツリー内のルートレベルを示しているか否かをチェックする。そうでない場合、動作はボックス533に進む。そうである場合、動作はボックス519に進む。
【００９５】
ボックス519において、ノードは、(全マークルツリーの現在のレベルポインタにより参照される)全マークルツリーの現在のレベルにおける隣接ノード対を通じてループを構成する。このループは、全マークルツリーの現在のレベルにおけるそれぞれの所与の隣接ノード対についてボックス521〜529の動作を実行する。
【００９６】
ボックス521において、ノードは、所与の隣接ノード対の双方のノードが(プレースホルダから区別されるような)ハッシュ値をそれぞれ含むか否かをチェックする。全マークルツリーの最下位レベルにおける隣接ノード対のノードは、上記のようにボックス505〜513の動作から生じるプレースホルダ及びトランザクションの順序付きのリストの対応する要素を示す点に留意する。このような対応関係は、全マークルツリーの最下位レベルにおけるリーフノード位置(左から右へ)にプレースホルダ及びトランザクションのリストの位置をマッチングさせることにより記述される。この条件が満たされない場合、所与の隣接ノード対の双方のノードは、ボックス523において単独に残され、所与の隣接ノード対の親ツリーノードのハッシュ値は、ボックス525においてプレースホルダに置き換えられ、動作はボックス529に進む。この条件が満たされた場合、ノードは、ボックス527において、所与の隣接ノード対の双方のノードを除去し、隣接ノード対の親ツリーノードのハッシュ値だけを残し、動作はボックス529に進む。
【００９７】
ボックス529において、ノードは、全マークルツリーの現在のレベルにおけるいずれかの隣接ノード対が、ボックス519において構成された隣接ノード対を通じたループにおいて処理されるべきままに残っているか否かをチェックする。そうである場合、動作はボックス519に戻り、全マークルツリーの現在のレベルにおける次の隣接ノード対についてループを継続する。そうでない場合、動作はボックス531に進む。
【００９８】
ボックス531において、ノードは、全マークルツリー内の次のレベルを示すようにマークルツリーの現在のレベルポインタを調整し、動作は、全マークルツリーの次のレベルについてボックス517〜529の動作を繰り返し続ける。
【００９９】
ボックス533において、ノードは、全マークルツリーのルートノードハッシュ値をプレースホルダに置き換えるか或いは置換し、動作が終了する。
【０１００】
図６Ａは、例示的なブロックの全マークルツリーを示す。
【０１０１】
図６Ｂは、図６Ａの例示的なブロックの全マークルツリーについての図５のフローチャートのボックス519〜529の動作の結果を示す。これらの動作では、プレースホルダは、全マークルツリーの最下位レベルの6つのトランザクションについてのハッシュ値(トランザクション識別子)を置き換えており、このようなトランザクションは、ノードが属するシャードに対応する。
【０１０２】
図６Ｃは、図６Ａの全マークルツリーについての図５のフローチャートのボックス519〜529の動作の結果を示す。これらの動作では、ノードが属するシャードに対応しないトランザクションからハッシュ値が導出されるので、全マークルツリーの最下位レベル(全マークルツリーの左側)における2つの隣接するハッシュ値が除去されている。さらに、プレースホルダは、隣接ノードが双方とも対応するハッシュ値を有さず、したがって、ノードが属するシャードに対応する少なくとも1つのトランザクションから導出される3つの場合において、全マークルツリーの第2レベル(全マークルツリーの左側)の隣接リーフノードの親ノードを置き換えている。
【０１０３】
図６Ｄは、図６Ａの全マークルツリーについての図５のフローチャートの動作の結果である部分マークルツリーを示す。
【０１０４】
図７Ａ〜図７Ｃは併せて、図２のシャードされたブロックチェーン台帳のようなシャードされたブロックチェーン台帳の一部として記憶されたブロックを承認するために、全てのシャードのメンバーではないノードにより実行される動作を示すフローチャートである。この場合、ノードは、アクティブなシャードの限られたサブセットに属し、したがって、1つ以上のアクティブなシャードに属さない。全てのシャードのメンバーであるいずれかのノードは、周知のブロック承認プロセスを使用して新たなブロックを承認できる点に留意する。
【０１０５】
ボックス701において、ノードは、これが属するシャードについてのブロックデータからブロックを読み取る。ブロックデータは、ブロックの部分マークルツリーを表すデータを含むブロックヘッダを含む。ブロックヘッダは、他のフィールドも同様に含むことができる。ブロックデータはまた、ブロックの一部であり且つノードが属するシャードに対応するトランザクションのトランザクション識別子の順序付きのリストを含む。例示的なブロックデータが図８Ａに概略的に示されている。
【０１０６】
ボックス703において、ノードは、ボックス701において読み取られたブロックデータに記憶されたブロックのトランザクション識別子の順序付きのリストを抽出する。トランザクション識別子のリストは、場合によっては、ブロックの一部であり且つノードが属さない1つ以上のシャードに対応するトランザクションを省略し、したがって、ブロックのトランザクション識別子の順序付きのシーケンスの全リストを記憶することを回避する。
【０１０７】
ボックス705において、ノードは、ボックス701において読み取られたブロックデータに記憶されたブロックの部分マークルツリーを表すデータを抽出する。
【０１０８】
ボックス707において、ノードは、部分マークルツリーの現在のレベルポインタを、ボックス705において抽出されたデータにより表される部分マークルツリーの最下位レベルに設定する。
【０１０９】
ボックス709において、ノードは、部分的な全マークルツリーの現在のレベル(ボックス707において設定された部分マークルツリーの現在のレベルポインタにより参照される最下位レベル)におけるツリーノードを通じてループを構成する。このループは、部分マークルツリーの最下位レベルにおけるそれぞれの所与のツリーノードについてボックス711〜717の動作を実行する。
【０１１０】
ボックス711において、ノードは、所与のツリーノードがプレースホルダであるか否かをチェックする。そうでない場合、ノードは、ボックス713におけるツリーノードをスキップし、ボックス717に進む。そうである場合、ノードはボックス715に進み、ノードは、ボックス703において抽出されたリストからの対応するトランザクション識別子(ハッシュ値)でプレースホルダを置き換え、動作はボックス717に進む。ボックス703において抽出されたリストからのトランザクション識別子(ハッシュ値)とプレースホルダとの間の対応関係は、部分マークルツリーの最下位レベルにおけるプレースホルダの順序と、ボックス703において抽出されたリスト内のトランザクション識別子の順序との間の対応関係により記述できる点に留意する。
【０１１１】
ボックス717において、ノードは、部分マークルツリーの現在のレベルにおけるツリーノード(部分マークルツリーの現在のレベルポインタにより参照される)が、ボックス709において構成されたツリーノードを通じてループ内で処理されるべきままに残っているか否かをチェックする。そうである場合、動作はボックス709に戻り、次のツリーノードについてループを継続する。そうでない場合、動作はボックス719に進む。
【０１１２】
ボックス719において、ノードは、部分マークルツリーの現在のレベルポインタを、ボックス705において抽出されたデータにより表される部分マークルツリーの次のレベル(最下部リーフノードレベルの上のレベル)に設定する。
【０１１３】
ボックス721において、ノードは、部分マークルツリーの現在のレベルポインタが部分マークルツリーにおけるルートレベルを示しているか否かをチェックする。そうである場合、動作はボックス735に進む。そうでない場合、動作はボックス723に進む。
【０１１４】
ボックス723において、ノードは、部分的な全マークルツリーの現在のレベル(ボックス719又は733において設定された部分マークルツリーの現在のレベルポインタにより参照される)におけるツリーノードを通じてループを構成する。このループは、部分マークルツリーの現在のレベルにおけるそれぞれの所与の各ツリーノードについてボックス725〜731の動作を実行する。
【０１１５】
ボックス725において、ノードは、所与のツリーノードがプレースホルダであるか否かをチェックする。そうでない場合、ノードは、ボックス727においてツリーノードをスキップし、ボックス731に進む。そうである場合、ノードはボックス729に進み、ノードは、所与のツリーノードの2つの子ノードのハッシュ値に基づいてハッシュ値を計算し、プレースホルダをこの計算されたハッシュ値に置き換え、動作はボックス729に進む。
【０１１６】
ボックス729において、ノードは、部分マークルツリーの現在のレベルにおけるツリーノード(部分マークルツリーの現在のレベルポインタにより参照される)が、ボックス723において構成されたツリーノードを通じてループ内で処理されるべきままに残っているか否かをチェックする。そうである場合、動作はボックス723に戻り、次のツリーノードについてループを継続する。そうでない場合、動作はボックス733に進む。
【０１１７】
ボックス733において、ノードは、部分マークルツリーの現在のレベルポインタを部分マークルツリーにおける次のレベルを示すように調整し、動作は部分マークルツリーの次のレベルを処理するためにボックス721に戻る。
【０１１８】
ボックス735において、ノードは、ボックス709〜731の動作から決定されたルートノードの2つの子ノードに基づいてハッシュ値を計算し、ルートノードのプレースホルダをこの計算されたハッシュ値に置き換える。
【０１１９】
ボックス737において、ノードは、ボックス701において読み取られたブロックデータの一部としてブロックのヘッダに記憶されたマークルルートハッシュ値を抽出し、ノードは、抽出されたマークルルートハッシュ値を、ボックス735において計算された部分マークルツリーのルートハッシュ値と比較する。
【０１２０】
ボックス739において、ノードは、ボックス737の比較を評価し、抽出されたマークルルートハッシュ値がボックス735において計算された部分マークルツリーのルートハッシュ値と一致するか否かを決定する。そうである場合、動作はボックス741に進む。そうでない場合、動作はボックス755及び757に進む。
【０１２１】
ボックス741において、ノードは、ブロックの有効性について他のヘッダ条件を評価する。
【０１２２】
ボックス743において、ノードは、ボックス741の評価をチェックし、ブロックの有効性についての全ての他のヘッダ条件が満たされているか否かを決定する。そうである場合、動作はボックス745に進む。そうでない場合、動作はボックス755及び757に進む。
【０１２３】
ボックス745において、ノードは、ボックス703において抽出されたトランザクション識別子のリストを通じてループを構成する。トランザクション識別子のリストは、場合によっては、ノードが属さないシャードに関連するトランザクションを省略し、したがって、ブロックのトランザクション識別子の順序付きのシーケンスのリストの全リストを記憶することを回避する。このループは、このリスト内のそれぞれの所与のトランザクション識別子についてボックス747〜749の動作を実行する。
【０１２４】
ボックス747において、ノードは、所与のトランザクション識別子により参照されるトランザクションが有効であるか否かをチェックする。所与のトランザクション識別子により参照されるトランザクションが有効であると決定された場合、動作はボックス749に進む。そうでない場合、動作はボックス755及び757に進む。実施形態では、ノードは、所与のトランザクション識別子により参照されるトランザクションが、ノードが属するシャードについてのトランザクションキュー(メモリプール)に記憶されていることをチェックできる。そうである場合、トランザクションは有効であるとみなされることができ、動作はボックス749に進む。そうでない場合、ノードは、トランザクションのコピーを要求して取得するために、ネットワークの他のノードと通信できる。一旦受信すると、ノードは、受信したトランザクションを承認するための動作を実行できる。このような承認動作の例は、図３Ａ及び３Ｂのボックス307を参照して上記に記載されている。トランザクションが有効であるとみなされた場合、動作はボックス749に進む。トランザクションが無効であるとみなされた場合、動作は、ボックス755及び757に進む。
【０１２５】
ボックス749において、ノードは、いずれかのトランザクション識別子が、ボックス745において構成されたトランザクション識別子を通じてループ内で処理されるべきままに残っているか否かをチェックする。そうである場合、動作はボックス745に戻り、リスト内の次のトランザクション識別子についてループを継続する。そうでない場合、動作はボックス751及び753に進む。
【０１２６】
ボックス751において、ノードは、ブロックを有効としてマーキングするデータを生成して記憶する。
【０１２７】
ボックス753において、ノードは、有効なブロックを表すデータを、ノードと同じシャードのセットに属する他のノードに伝搬できる。
【０１２８】
ボックス755において、ノードは、ブロックを無効としてマーキングするデータを生成して記憶する。
【０１２９】
ボックス757において、ノードは、無効なブロックを表すブロックデータを破棄し、無効なブロックを表すブロックデータを他のノードに伝搬することを回避できる。ノードはまた、シャードに割り振られた無効なブロックの一部である1つ以上のトランザクションのトランザクションデータを破棄し、必要に応じて、このようなトランザクションについてのUTXOをシャードについてのUTXOセットに戻すことができる。
【０１３０】
図８Ａは、例示的なブロックの部分マークルツリーを示す図である。
【０１３１】
図８Ｂは、図８Ａの部分マークルツリー上の図７Ａ〜図７Ｄのフローチャートのボックス709〜717の動作の結果を示す。これらの動作では、部分マークルツリーの下位(リーフ)レベルにおける5つのプレースホルダが、ボックス703において抽出されたトランザクション識別子のリストの一部としての対応するハッシュ値(トランザクション識別子)に置き換えられている。
【０１３２】
図８Ｃは、図８Ａの部分マークルツリー上の図７Ａ〜図７Ｄのフローチャートのボックス723〜731の動作の結果を示す。これらの動作では、部分マークルツリーの第2レベルにおける3つのプレースホルダが、子ノードのハッシュ値から導出されたハッシュ値に置き換えられている。
【０１３３】
図８Ｄは、図８Ａの部分マークルツリー上の図７Ａ〜図７Ｄのフローチャートのボックス723〜737の動作の結果を示す。これらの動作では、部分マークルツリーのルートについてのハッシュ値は、子ノードのハッシュ値から導出され、承認のためにブロックのブロックヘッダに記憶されたマークルルートハッシュ値と比較される。
【０１３４】
図９は、本開示の少なくとも1つの実施形態を実施するために使用され得る計算デバイス2600の例示的な簡略化したブロック図である。様々な実施形態では、計算デバイス2600は、上記に図示及び記載のシステムのいずれかを実装するために使用されてもよい。例えば、計算デバイス2600は、データサーバ、ウェブサーバ、ポータブル計算デバイス、パーソナルコンピュータ又はいずれかの電子計算デバイスとして使用するために構成されてもよい。図９に示すように、計算デバイス2600は、バスサブシステム2604を介して多数の周辺サブシステムと通信するように構成されてもよく且つ動作可能に結合された1つ以上のプロセッサ2602を含んでもよい。プロセッサ2602は、ここに記載のように使用中のトランザクションを承認する一部として、ロック解除及びロックスクリプトを処理するために利用されてもよい。これらの周辺サブシステムは、メモリサブシステム2608及びファイル/ディスク記憶サブシステム2610を含む記憶サブシステム2606と、1つ以上のユーザインタフェース入力デバイス2612と、1つ以上のユーザインタフェース出力デバイス2614と、ネットワークインタフェースサブシステム2616とを含んでもよい。このような記憶サブシステム2606は、本開示に記載のトランザクション及びブロックに関連する詳細のような情報の一時的な記憶又は長期の記憶のために使用されてもよい。
【０１３５】
バスサブシステム2604は、計算デバイス2600の様々な構成要素及びサブシステムが、意図したように相互に通信することを可能にする機構を提供してもよい。バスサブシステム2604は、単一のバスとして概略的に示されているが、バスサブシステムの代替実施形態は、複数のバスを利用してもよい。ネットワークインタフェースサブシステム2616は、他の計算デバイス及びネットワークへのインタフェースを提供してもよい。ネットワークインタフェースサブシステム2616は、他のシステムからデータを受信し、計算デバイス2600から他のシステムにデータを送信するためのインタフェースとして機能してもよい。例えば、ネットワークインタフェースサブシステム2616は、データ技術者が、データセンタのような遠隔地にいる間に、データを送信及び受信することができるように、デバイスを無線ネットワークに接続することを可能にしてもよい。バスサブシステム2604は、詳細、検索項目等のデータを本開示の教師付きのモデルに通信するために利用されてもよく、教師付きのモデルの出力を1つ以上のプロセッサ2602に通信し、ネットワークインタフェースサブシステム2616を介して取引先及び/又は債権者に通信するために利用されてもよい。
【０１３６】
ユーザインタフェース入力デバイス2612は、キーボードのような1つ以上のユーザ入力デバイスと、統合マウス、トラックボール、タッチパッド又はグラフィックスタブレットのようなポインティングデバイスと、スキャナと、バーコードスキャナと、ディスプレイに組み込まれたタッチスクリーンと、音声認識システム、マイクロフォンのようなオーディオ入力デバイスと、他のタイプの入力デバイスとを含んでもよい。一般的に、「入力デバイス」という用語の使用は、情報を計算デバイス2600に入力するための全ての可能な種類のデバイス及び機構を含むことを意図する。1つ以上のユーザインタフェース出力デバイス2614は、表示サブシステム、プリンタ、又はオーディオ出力デバイスのような非視覚的ディスプレイを含んでもよい。表示サブシステムは、陰極線管(CRT)、液晶ディスプレイ(LCD)、発光ダイオード(LED)ディスプレイのようなフラットパネルデバイス、又は投影若しくは他の表示デバイスでもよい。一般的に、「出力デバイス」という用語の使用は、計算デバイス2600から情報を出力するための全ての可能な種類のデバイス及び機構を含むことを意図する。1つ以上のユーザインタフェース出力デバイス2614は、例えば、ユーザ相互作用が適切になり得るときに、ここに記載のプロセス及びその変形を実行するアプリケーションとのユーザ相互作用を実現するように、ユーザインタフェースを提示するために使用されてもよい。
【０１３７】
記憶サブシステム2606は、本開示の少なくとも1つの実施形態の機能を提供し得る基本的なプログラミング及びデータ構成を記憶するためのコンピュータ読み取り可能記憶媒体を提供してもよい。アプリケーション(プログラム、コードモジュール、命令)は、1つ以上のプロセッサにより実行されたとき、本開示の1つ以上の実施形態の機能を提供してもよく、記憶サブシステム2606に記憶されてもよい。これらのアプリケーションモジュール又は命令は、1つ以上のプロセッサ2602により実行されてもよい。記憶サブシステム2606は、本開示に従って使用されるデータを記憶するためのリポジトリを更に提供してもよい。記憶サブシステム2606は、メモリサブシステム2608と、ファイル/ディスク記憶サブシステム2610とを含んでもよい。
【０１３８】
メモリサブシステム2608は、プログラム実行中に命令及びデータを記憶するためのメインランダムアクセスメモリ(RAM)2618と、固定の命令が記憶され得る読み取り専用メモリ(ROM)2620とを含む、多数のメモリを含んでもよい。ファイル/ディスク記憶サブシステム2610は、プログラム及びデータファイルのための非一時的な永続的(不揮発性)ストレージを提供してもよく、ハードディスクドライブ、関連する取り外し可能媒体と共にフロッピーディスクドライブ、コンパクトディスク読み取り専用メモリ(CD-ROM)ドライブ、光学ドライブ、取り外し可能媒体カートリッジ及び他の同様の記憶媒体を含んでもよい。
【０１３９】
計算デバイス2600は、少なくとも1つのローカルクロック2624を含んでもよい。ローカルクロック2624は、特定の開始日から発生したティックの数を表すカウンタでもよく、計算デバイス2600内に一体的に配置されてもよい。ローカルクロック2624は、特定のクロックパルスにおいて、計算デバイス2600のためのプロセッサ及びそれに含まれる全てのサブシステムにおけるデータ転送を同期させるために使用されてもよく、計算デバイス2600とデータセンタ内の他のシステムとの間の同期動作を調整するために使用されてもよい。一実施形態では、ローカルクロック2624は原子クロックである。他の実施形態では、ローカルクロックはプログラム可能な間隔のタイマである。
【０１４０】
計算デバイス2600は、ポータブルコンピュータデバイス、タブレットコンピュータ、ワークステーション、又は以下に記載のいずれかの他のデバイスを含む、様々な種類のものでもよい。さらに、計算デバイス2600は、1つ以上のポート(例えば、USB、ヘッドフォンジャック、ライトニングコネクタ等)を通じて計算デバイス2600に接続され得る他のデバイスを含んでもよい。計算デバイス2600に接続され得るデバイスは、光ファイバコネクタを受け入れるように構成された複数のポートを含んでもよい。したがって、このデバイスは、光信号を電気信号に変換するように構成されてもよく、電気信号は、処理のために当該デバイスを計算デバイス2600に接続するポートを通じて送信されてもよい。コンピュータ及びネットワークの絶えず変化する性質のため、図９に示す例示的な計算デバイス2600の説明は、デバイスの好ましい実施形態を説明する目的のための特定の例としてのみ意図されている。図９に示すシステムよりも多くの構成要素又は少ない構成要素を有する多くの他の構成が可能である。
【０１４１】
上記の実施形態は、本発明を限定するものではなく例示するものであり、当業者は、添付の特許請求の範囲により定義される本開示の範囲から逸脱することなく、多くの代替実施形態を設計できる点に留意すべきである。特許請求の範囲において、括弧内に付したいずれかの参照符号は、特許請求の範囲を限定するものと解釈されないものとする。「含む(comprising)」及び「含む(comprises)」等の用語は、全体としていずれかの請求項又は明細書に列挙されたもの以外の要素又はステップの存在を除外しない。本明細書において、「含む(comprises)」とは、「含む(includes)又はからなる(consists  of)」を意味し、「含む(comprising)」とは、「含む(comprising)又はからなる(consisting  of)」を意味する。要素の単数形の参照は、このような要素の複数形の参照を除外するものではなく、逆も同様である。本発明は、いくつかの別個の要素を含むハードウェアにより、且つ、適切にプログラムされたコンピュータにより実装されてもよい。いくつかの手段を列挙するデバイスの請求項において、これらの手段のいくつかは、1つの同じハードウェアアイテムにより具体化されてもよい。特定の手段が相互に異なる従属項に記載されているという単なる事実は、これらの手段の組み合わせが有利に利用できないことを示すものではない。
【０１４２】
上記の説明は、例示的であり限定的ではないことを意図するものであることが理解されるべきである。多くの他の実装は、上記の説明を読んで理解することにより、当業者に明らかになる。本開示は、特定の例示的な実装を参照して記載されているが、本開示は、記載の実装に限定されず、添付の特許請求の範囲の範囲内の修正及び変更を用いて実施可能であることが認識される。したがって、明細書及び図面は、限定的な意味ではなく、例示的な意味で考えられるべきである。したがって、本開示の範囲は、添付の特許請求の範囲が権利を有する均等物の全範囲と共に、添付の特許請求の範囲を参照して決定されるべきである。
【図１Ａ】
2021522710.tif 000003
【図１Ｂ】
2021522710.tif 000004
【図２】
2021522710.tif 000005
【図３Ａ】
2021522710.tif 000006
【図３Ｂ】
2021522710.tif 000007
【図４Ａ】
2021522710.tif 000008
【図４Ｂ】
2021522710.tif 000009
【図５】
2021522710.tif 000010
【図６Ａ】
2021522710.tif 000011
【図６Ｂ】
2021522710.tif 000012
【図６Ｃ】
2021522710.tif 000013
【図６Ｄ】
2021522710.tif 000014
【図７Ａ】
2021522710.tif 000015
【図７Ｂ】
2021522710.tif 000016
【図７Ｃ】
2021522710.tif 000017
【図７Ｄ】
2021522710.tif 000018
【図８Ａ】
2021522710.tif 000019
【図８Ｂ】
2021522710.tif 000020
【図８Ｃ】
2021522710.tif 000021
【図８Ｄ】
2021522710.tif 000022
【図９】
2021522710.tif 000023
【国際調査報告】
2021522710.tif 000024
2021522710.tif 000025
2021522710.tif 000026