(57)【要約】  ここに記載の技術は、複数のワーカーノードの間で特定のワーカーノードの偏りのない選択を実行して計算タスクを実行するためのプロトコルを実装するために利用できる。分散ネットワークのノードは、マネージャノードにより定義されるパラメータを有するアキュムレーションツリーのような階層データ構造から少なくとも部分的に導出された量を生成することにより、グループメンバーシップに参加するために登録してもよい。マネージャノードは、複数のワーカーノードの中からワーカーノードの偏りのない選択を実行して計算タスクを実行するために、複数のワーカーノードにより提供される量を利用してもよい。本発明は、ビットコインのようなブロックチェーンネットワークでの使用に特に適しているが、これに限定されない。少なくともいくつかの場合、マネージャノードは、ワーカーノードにより供給される量に基づいて、特定のワーカーノードが計算タスクを実行するために選択されたか否かを決定できない。
2021530173.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ実施方法であって、
ブロックチェーン上の複数のトランザクションが条件を満たすことを検出するステップであり、前記複数のトランザクションは、第1の公開鍵及び第2の公開鍵に対応する第1のトランザクションを含み、前記第1の公開鍵は、階層データ構造の第1のセットの要素を符号化する、ステップと、
前記階層データ構造の第2のセットの要素に基づいて第3の公開鍵を生成するステップと、
前記第1の公開鍵、前記第2の公開鍵及び前記第3の公開鍵に少なくとも部分的に基づいて第2のトランザクションを生成するステップであり、前記第2のトランザクションは、計算タスクの少なくとも一部を符号化する、ステップと、
前記第1のセットの要素が前記第2のセットの要素に一致することによって、前記ブロックチェーンのノードに対して、前記ノードが第1の秘密鍵及び第2の秘密鍵へのアクセスを有することを少なくとも検証することにより、前記計算タスクを実行させるステップであり、前記第1の秘密鍵及び前記第1の公開鍵は、第1の鍵ペアを形成し、前記第2の秘密鍵及び前記第2の公開鍵は、第2の鍵ペアを形成する、ステップと
を含む方法。
【請求項２】
前記ノードが前記第1の秘密鍵及び前記第2の秘密鍵へのアクセスを有することを検証することは、前記第1の秘密鍵及び前記第2の秘密鍵がモジュラス(modulus)関係を満たすことを検証することを含む、請求項１に記載の方法。
【請求項３】
前記第1の公開鍵、前記第2の公開鍵及び前記第3の公開鍵は、楕円曲線上の点を参照する、請求項１又は２に記載の方法。
【請求項４】
前記階層データ構造の構造を決定するのに使用可能なパラメータのセットを利用可能にするステップを更に含む、請求項１乃至３のうちいずれか１項に記載の方法。
【請求項５】
前記階層データ構造は、双線形マップアキュムレーションツリーである、請求項１乃至４のうちいずれか１項に記載の方法。
【請求項６】
前記条件は、閾値時間の経過であり、前記閾値時間は、前記パラメータのセットにおいて示される、請求項１乃至５のうちいずれか１項に記載の方法。
【請求項７】
前記条件は、前記複数のトランザクションが最大閾値数に達することである、請求項１乃至６のうちいずれか１項に記載の方法。
【請求項８】
前記階層データ構造は、アキュムレーションツリーであり、
前記アキュムレーションツリーのリーフノードの数、前記第1のセットの要素内の要素の数及び前記最大閾値数は、前記複数のトランザクションのうち2つ以上のトランザクションが同じセットの要素を符号化する確率に少なくとも部分的に基づいて、併せて決定される、請求項１乃至７のうちいずれか１項に記載の方法。
【請求項９】
前記第2のトランザクションは、デジタル資産のセットを担保し、前記デジタル資産のセットは、前記複数のトランザクションのそれぞれにより担保されるデジタル資産に少なくとも部分的に基づいて決定され、
前記計算タスクは、実行された場合、前記デジタル資産のセットの少なくとも一部の制御を移転する、請求項１乃至８のうちいずれか１項に記載の方法。
【請求項１０】
前記条件を満たすことを検出したことに基づいて、前記第2のトランザクションを生成するための保証をブロードキャストするステップであり、前記保証は、前記複数のトランザクションのそれぞれにより担保される前記デジタル資産に基づいて第2のセットのデジタル資産を担保する、ステップを更に含む、請求項１乃至９のうちいずれか１項に記載の方法。
【請求項１１】
前記複数のトランザクションのトランザクションは、前記ブロックチェーンの異なるノードにより前記ブロックチェーンにブロードキャストされる、請求項１乃至１０のうちいずれか１項に記載の方法。
【請求項１２】
前記複数のトランザクションのうち少なくとも2つのトランザクションは、前記ブロックチェーンのノードにより前記ブロックチェーンにブロードキャストされる、請求項１乃至１１のうちいずれか１項に記載の方法。
【請求項１３】
前記計算タスクは、指定の期間内に実行される、請求項１乃至１２のうちいずれか１項に記載の方法。
【請求項１４】
システムであって、
プロセッサと、
前記プロセッサによる実行の結果として、請求項１乃至１３のうちいずれか１項に記載のコンピュータ実施方法を当該システムに実行させる実行可能命令を含むメモリと
を含むシステム。
【請求項１５】
コンピュータシステムの1つ以上のプロセッサによる実行の結果として、請求項１乃至１３のうちいずれか１項に記載のコンピュータ実施方法を前記コンピュータシステムに少なくとも実行させる実行可能命令を記憶した非一時的なコンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、ここではコンピュータネットワーク内のワーカーノードと呼ばれる、複数のコンピュータノード内の計算タスクの割り当てを分配するためのプロトコルに関する。プロトコルの一部として、分散ネットワークのノードは、マネージャノードにより定義されるパラメータを有するアキュムレーションツリー(accumulation  tree)から少なくとも部分的に導出された量を生成することにより、グループメンバーシップに参加するために登録してもよい。マネージャノードは、プロトコルの一部として、複数のワーカーノードの中からワーカーノードの偏りのない選択を実行して計算タスクを実行する(例えば、コンピュータプログラムを実行する)ために、複数のワーカーノードにより提供される量を利用する。本発明は、ブロックチェーンネットワークでの使用に特に適しているが、これに限定されない。少なくともいくつかの場合、マネージャノードは、ワーカーノードにより供給される量に基づいて、特定のワーカーノードが計算タスクを実行するために選択されたか否かを決定できない。
【背景技術】
【０００２】
ブロックチェーンは、ピアツーピアの電子台帳であり、これは、結果としてトランザクションで構成される、ブロックで構成されるコンピュータに基づく非集中的な分散型システムとして実装される。各トランザクションは、ブロックチェーンシステム内の参加者の間のデジタル資産の制御の移転を符号化するデータ構造であり、少なくとも1つのインプット及び少なくとも1つのアウトプットを含む。各ブロックは、前のブロックのハッシュを含み、それにより、ブロックチェーンの開始以降にブロックチェーンに書き込まれた全てのトランザクションの永続的で修正不可能なレコードを作成するように、ブロックが一緒につながれる。トランザクションは、トランザクションのインプット及びアウトプットに埋め込まれたスクリプトとして知られる小さいプログラムを含み、これは、トランザクションのアウトプットがどのように誰によってアクセスできるかを指定する。ビットコインプラットフォームでは、これらのスクリプトはスタックに基づくスクリプト言語を使用して記述される。
【０００３】
トランザクションがブロックチェーンに書き込まれるために、これは「承認され(validated)」なければならない。ネットワークノード(マイナー)は、各トランザクションが有効であることを確保するために作業を実行し、無効なトランザクションはネットワークから拒否される。ノードにインストールされたソフトウェアクライアントは、ロック及びロック解除スクリプトを実行することにより、未使用トランザクション(unspent  transaction,  UTXO)に対してこの承認動作を実行する。ロック及びロック解除スクリプトの実行がTRUEに評価された場合、トランザクションは有効であり、トランザクションはブロックチェーンに書き込まれる。したがって、トランザクションがブロックチェーンに書き込まれるために、これは、i)トランザクションを受信した最初のノードにより承認されなければならず、トランザクションが承認された場合、ノードはそれをネットワーク内の他のノードに中継し、ii)マイナーにより構築された新たなブロックに追加されなければならず、且つ、iii)マイニングされなければならず、すなわち、過去のトランザクションの公開台帳に追加されなければならない。
【０００４】
ブロックチェーン技術は、暗号通貨の実装の使用にとって最も広く知られているが、デジタル起業家は、新たなシステムを実装するために、ビットコインが基礎となる暗号セキュリティシステムと、ブロックチェーンに記憶できるデータとの双方の使用を調査し始めている。ブロックチェーンが、暗号通貨の領域に限定されない自動化タスク及びプロセスに使用され得る場合には、非常に有利になる。このような解決策は、ブロックチェーンの利点(例えば、イベントの永続的な改ざん防止記録、分散処理等)を利用することができる一方で、これらの用途においてより多目的になることができる。
【０００５】
この文献では、全ての形式の電子的なコンピュータに基づく分散型の台帳を含む「ブロックチェーン(blockchain)」という用語を使用する。これらは、コンセンサスに基づくブロックチェーン及びトランザクションチェーン技術、プライベート型(permissioned)及びパブリック型(un-permissioned)台帳、共有台帳及びこれらの変形を含む。ブロックチェーン技術の最も広く知られているアプリケーションはビットコイン台帳であるが、他のブロックチェーンの実装も提案されて開発されている。ここでは、便宜上及び説明上の目的でビットコインが参照されることがあるが、本発明は、ビットコインブロックチェーンでの使用に限定されず、代替のブロックチェーンの実装及びプロトコルも、本発明の範囲内に入る点に留意すべきである。「ユーザ」という用語は、ここでは人間又はプロセッサに基づくリソースを示すことがある。「ビットコイン」という用語は、ここではビットコインプロトコルから派生するか或いはこれに基づくいずれかのバージョン又はバリエーションを含むように使用される。
【発明の概要】
【０００６】
したがって、ブロックチェーンネットワークのような分散ネットワークにおいて、計算タスクがネットワークのノードの間で公平に分配されている(すなわち、計算タスクが偏りのない方式で分配されている)という計算的に検証可能な保証を提供することが望ましい。例えば、複数のワーカーノードにより供給される量に基づいて、選択を実行するノードが、計算タスクが完了した後まで特定のノードが計算タスクを実行するために選択されたか否かを予測できない選択プロセスを利用することは、有用且つ有利になり得る。
【０００７】
そこで、このような改善された解決策が考案されている。
【０００８】
本発明によれば、ブロックチェーンネットワークのノードのためのコンピュータ実装方法が提供されてもよい。当該方法は、暗号的に実施されてもよい。コンピュータ実施方法は、ブロックチェーン上の複数のトランザクションが条件を満たすことを検出するステップであり、複数のトランザクションは、第1の公開鍵及び第2の公開鍵に対応する第1のトランザクションを含み、第1の公開鍵は、階層データ構造の第1のセットの要素を符号化する、ステップと、階層データ構造の第2のセットの要素に基づいて第3の公開鍵を生成するステップと、第1の公開鍵、第2の公開鍵及び第3の公開鍵に少なくとも部分的に基づいて第2のトランザクションを生成するステップであり、第2のトランザクションは、計算タスクの少なくとも一部を符号化する、ステップと、第1のセットの要素が第2のセットの要素に一致することによって、ブロックチェーンのノードに対して、ノードが第1の秘密鍵及び第2の秘密鍵へのアクセスを有することを少なくとも検証することにより、計算タスクを実行させるステップであり、第1の秘密鍵及び第1の公開鍵は、第1の鍵ペアを形成し、第2の秘密鍵及び第2の公開鍵は、第2の鍵ペアを形成する、ステップとを含んでもよい。
【０００９】
この方法は、分散ネットワークのノードの間で計算タスクを公平に及び/又は実質的に均一に分配するために使用されてもよい。これは、効率性とリソース割り当てに関する技術的な利点を生じる。
【００１０】
好ましくは、ノードが第1の秘密鍵及び第2の秘密鍵へのアクセスを有することを検証することは、第1の秘密鍵及び第2の秘密鍵がモジュラス(modulus)関係を満たすことを検証することを含む。
【００１１】
好ましくは、第1の公開鍵、第2の公開鍵及び第3の公開鍵は、楕円曲線上の点を参照する。いくつかの場合、第1の公開鍵、第2の公開鍵及び第3の公開鍵のうち1つ以上のいくつかの組み合わせは、楕円曲線上の点を表す。
【００１２】
また、当該方法が、階層データ構造の構造を決定するのに使用可能なパラメータのセットを利用可能にするステップを更に含むことも望ましい。階層データ構造の構造を決定するために使用可能なパラメータのセットは、ブロックチェーンネットワークのノードに利用可能されてもよい。
【００１３】
好ましくは、階層データ構造は、双線形マップ(bilinear-map)アキュムレーションツリーのようなアキュムレーションツリーである。
【００１４】
好ましくは、条件は、閾値時間の経過であり、閾値時間は、パラメータのセットにおいて示される。
【００１５】
好ましくは、条件は、複数のトランザクションが最大閾値数に達することである。
【００１６】
好ましくは、階層データ構造は、アキュムレーションツリーであり、アキュムレーションツリーのリーフノードの数、第1のセットの要素内の要素の数及び最大閾値数は、複数のトランザクションのうち2つ以上のトランザクションが同じセットの要素を符号化する確率に少なくとも部分的に基づいて、併せて決定される。
【００１７】
好ましくは、第2のトランザクションは、デジタル資産のセットを担保(encumber)し、デジタル資産のセットは、複数のトランザクションのそれぞれにより担保されるデジタル資産に少なくとも部分的に基づいて決定され、計算タスクは、実行された場合、デジタル資産のセットの少なくとも一部の制御を移転する。
【００１８】
当該方法は、条件を満たすことを検出したことに基づいて、第2のトランザクションを生成するための保証をブロードキャストするステップであり、保証は、複数のトランザクションのそれぞれにより担保されるデジタル資産に基づいて第2のセットのデジタル資産を担保する、ステップを更に含んでもよい。
【００１９】
好ましくは、複数のトランザクションのトランザクションは、ブロックチェーンの異なるノードによりブロックチェーンにブロードキャストされる。
【００２０】
いくつかの場合、複数のトランザクションのうち少なくとも2つのトランザクションは、ブロックチェーンのノードによりブロックチェーンにブロードキャストされる。言い換えると、特定のブロックチェーンは、複数のトランザクションのうち少なくとも2つのトランザクションをブロックチェーンにブロードキャストしてもよい。
【００２１】
有利には、計算タスクは、指定の期間内に実行される。
【００２２】
また、プロセッサと、プロセッサによる実行の結果として、特許請求の範囲に記載の方法のいずれかをシステムに実行させる実行可能命令を含むメモリとを含むシステムを提供することも望ましい。
【００２３】
また、コンピュータシステムの1つ以上のプロセッサによる実行の結果として、特許請求の範囲に記載の方法のいずれかをコンピュータシステムに少なくとも実行させる実行可能命令を記憶した非一時的なコンピュータ読み取り可能記憶媒体を提供することも望ましい。
【図面の簡単な説明】
【００２４】
本発明のこれら及び他の態様は、ここに記載の実施形態から明らかになり、これを参照して解明される。次に、本発明の実施形態について、例のみとして、添付の図面を参照して説明する。
【図１】様々な実施形態が実装できるブロックチェーン環境を示す図である
【図２】少なくとも1つの実施形態に従ってワーカーノードが公開鍵を構築する計算環境を示す。
【図３】少なくとも1つの実施形態に従ってワーカーノード及びワーカーがメンバーシップグループへの登録を確認するために使用し得る対応するワーカーチケットを示す計算環境を示す。
【図４】少なくとも1つの実施形態に従って計算タスクを実行する(例えば、プログラムを実行する)ためのワーカーノードの選択に関連して利用され得る計算環境を示す。
【図５】少なくとも1つの実施形態に従って公開鍵がワーカーノードによりサブミットされたワーカーチケットから構築される計算環境を示す。
【図６】少なくとも1つの実施形態に従ってマネージャノードが実行トランザクションを生成する計算環境を示す。
【図７】少なくとも1つの実施形態に従って複数のワーカーノードからのワーカーノードの偏りのない選択を実行してタスクを実行する(例えば、プログラムを実行する)ために利用されるプロトコルロールバックトランザクションを生成する計算環境を示す。
【図８】実施形態に従ってメンバーシップグループに参加するためのワークチケット又はトランザクションの要求をサブミットするためのプロセスの例示的な例を示す。
【図９】少なくとも1つの実施形態に従って、複数のワーカーノードのワーカーノードの間で作業項目(例えば、プログラム実行)の偏りのない分配を実行するためのプロセスの例示的な例を示す
【図１０】様々な実施形態が実装できるコンピュータシステムを示す。
【発明を実施するための形態】
【００２５】
ここに記載の技術は、複数のワーカーノードをメンバーシップ/アソシエーションに登録し、複数のワーカーノードの間で特定のワーカーノードの偏りのない選択を実行して計算タスクを実行するプロセスの一部として、アキュムレーションツリーを利用するためのプロトコルを実装するために利用できる。実施形態では、偏りのない選択を実行するシステム(例えば、マネージャノード)は、ワーカーノードにより供給された量に基づいて(例えば、ブロックチェーンを介して)、実行トランザクションがブロックチェーン上で確認されるまで、特定のワーカーノードが計算タスクを実行するために選択されたか否かを予測できない。このプロトコルを利用することにより、ワーカーノードは、所望の結果に達するまでマネージャノードがランダム化された量を繰り返し生成する(例えば、特定のワーカーノードが計算タスクを実行することを事前に知っていることを生じる偏りのある選択を実行する)ことができないという、計算的に検証可能な保証を有してもよい。したがって、ここに記載の技術は、複数のノードの間の計算タスクの偏りのない委任(delegation)を、計算的に検証可能な方式で確保するプロトコルを提供することにより、コンピュータシステムの動作を改善し得る(例えば、分散システムにおける計算作業の公平な/偏りのない委任を確保する)。ここに記載の技術はまた、この開示を通じて記載されるプロトコルを使用して、異なるエンティティにより制御され得る複数の計算ノードの間の信頼保証を強化することにより、コンピュータネットワークのセキュリティを改善するために利用されてもよい。
【００２６】
図１に参照が行われてもよく、図１は、本開示の様々な実施形態が実施され得る例示的な計算環境100を示す。ここに記載のシステム及び方法は、複数のワーカーノード104の間でマネージャノード102からの計算タスクの偏りのない分配を確保するためのプロトコルに関してもよい。例えば、マネージャノードは、コンピュータプログラムの実行を、偏りのない方式で複数のワーカーノードのうち特定のワーカーノードに委任してもよい。説明の目的で、図１は、ワーカーノードのセット104を示しており、特定のワーカーノード116がコンピュータプログラムを実行するために選択されている。プロトコルの使用は、マネージャノードが、特定のワーカーノードPiが計算タスクを実行するために選択されたか否かを事前に決定できないという、計算的に検証可能な保証を提供してもよい。このように、選択プロセスは、偏りのない(或いは「公平な」)選択プロセスであり、マネージャノードは、実行トランザクション114が(例えば、ブロックチェーンネットワークに)ブロードキャストされるまで、特定のワーカーノードPiが同じ要素の組み合わせを選択するか否かを決定できない。要素の組み合わせは、図２に関連して以下に記載されるように、アキュムレーションツリーのリーフノードとして表されてもよい。いくつかの実施形態では、実行トランザクション114は、ブロックチェーンにブロードキャストされて確認されると、取消不能であり、それにより、マネージャノードが選択プロセスを変更する事後的な試みを行うことができないことを確保する。
【００２７】
マネージャノード102は、1つ以上の計算デバイスの1つ以上のプロセッサにより実行された場合、計算デバイスに対して、グループメンバーシップ内のノードの登録及びメンバーシップを管理させ、複数からのワーカーノードの偏りのない選択を管理させること等を行わせる実行可能コードを記憶するコンピュータサーバのような1つ以上の計算デバイスを示してもよい。いくつかの実施形態では、マネージャノード102は、いずれか適切な計算デバイス(例えば、データセンタ内のサーバ、クライアント計算デバイス(例えば、デスクトップコンピュータ、ラップトップコンピュータ、タブレットコンピュータ、スマートフォン等)、計算リソースサービスプロバイダの分散システム内の複数の計算デバイス、又は、図１０の計算デバイス1000のようないずれか適切な電子クライアントデバイス)から構成できる。いくつかの実施形態では、マネージャノード102は、ワークチケットの要求のような、提案されたトランザクションを表すデータメッセージ又はオブジェクトを受信するための入力を有し、ワークチケットは、ここに記載のトランザクションの例と考えられてもよい。いくつかの実施形態では、マネージャは、トランザクションの状態、メンバーシップグループの状態、ワークチケットの要求を構築するために利用され得るパラメータの情報等のような情報に対してクエリ可能である。
【００２８】
ノードは、ノードのうち1つ以上の他のノードと通信可能に結合されてもよい。このような通信結合は、有線又は無線通信のうちの1つ以上を含むことができる。実施形態では、ノードは、ブロックチェーン内のすべてのトランザクションの「台帳(ledger)」の少なくとも一部をそれぞれ維持する。このように、台帳は分散台帳になる。台帳に影響を与えるノードにより処理されるトランザクションは、台帳の完全性が維持されるように、他のノードのうち1つ以上により検証可能である。
【００２９】
どのノードがどの他のノードと通信できるかに関して、ブロックチェーンプロトコルが示すメッセージが転送されるべきであると仮定すると、ブロックチェーンネットワーク内のノードのそれぞれは、ノードの間で渡されるメッセージがブロックチェーンネットワーク(又はそのいくつかの重要な部分)を通じて伝搬できるように、ノードのうち1つ以上の他のノードと通信できることで十分である。1つのこのようなメッセージは、ブロックチェーンに含めるために提案された新たなブロックの公開である。一般的に言えば、この開示に記載される全てのノードは、上記のような特徴の一部又は全部を実装するように適合されてもよい。
【００３０】
計算環境100は、ワーカーノードのセット104を更に示してもよく、ワーカーノードは、マネージャノード102へのワークチケットのサブミットのための要求を提供し得るコンピュータシステムを示す。例えば、コンピュータシステムPiは、マネージャノード102により提供されたパラメータを使用して計算された量を含むワーカーチケットを要求側にサブミットすることにより、グループメンバーシップに参加する要求を行ってもよい(それにより、マネージャノードにより分配された計算タスクを実行するための機会を有する)。実施形態では、パラメータは、特定のグループに特有でもよく(例えば、マネージャノード102は、複数の計算タスクの実行のために複数のグループメンバーシップを動作してもよい)、特定のグループに特有のパラメータを有するアキュムレーションツリーを生成するために利用されてもよい。実施形態では、メンバーシップへのコンピュータシステムPiの登録は、コンピュータシステムPiが、プロトコルに従ってマネージャノード102により分配される計算タスクを受信して実行できるワーカーノードPiと考えられることを生じる。
【００３１】
実施形態では、ワーカーノードはワーカーチケット106を生成する。ワーカーノードのPiのワーカーチケットTxiは、ワーカーノードのセット104の中からワーカーノードの偏りのない選択を実行する選択ルーチンにおいて、マネージャノード102により使用可能な、ワーカーノードPiにより生成された特定の量を含んでもよい。実施形態では、ワーカーチケット106は、チケット公開鍵Ri及び検証公開鍵Tiを含み、チケット鍵は、マネージャノード102によりワーカーノードに提供されるパラメータのセットを有するアキュムレーションツリーに少なくとも部分的に基づいて生成され、パラメータのセットは、トラップドア(trapdoor)情報sとアキュムレーションツリーのパラメータとを含む。実施形態では、チケット公開鍵Ri108及び検証公開鍵Ti110に少なくとも部分的に基づいて生成される量は、計算タスクを実行するためのワーカーノードの偏りのない選択に関連して利用される。アキュムレーションツリーは、チケット公開鍵Ri及び検証公開鍵Tiの生成に関連して利用されてもよい。未登録のプレイヤは、登録されたワーカーノードに配布されたトラップドア情報sを認識せず、アキュムレーションツリーから導出された量を再構築できない。
【００３２】
様々な実施形態では、双線形マップアキュムレーションツリーが、効率的なデータ記憶及びメンバーシップ認証のために利用される。プロトコルに従って、ツリーに含まれる情報を圧縮するローカル及びグローバルダイジェスト(digest)のようなアキュムレーションツリーから抽出された量は、メンバーシップの参加者により行われた要素の選択又は組み合わせを表すために使用できる。このプロトコルでは、ワーカーノードは、これらの選択された組み合わせをワークチケット(ワーカーチケットとも呼ばれる)の要求にチケット公開鍵の一部として含め、マネージャノードは、このプロトコルに従って、要素の好適な組み合わせ(winning  combination)を選択することに基づいて、ワーカーノードの偏りのない選択を実行することを担い、コンピュータプログラムのような計算タスクを含む実行トランザクション114を構築する。プロトコルの一部として、マネージャノード102は、計算タスクを実行するための特定のワーカーノードを選択するために、アキュムレーションツリー112を利用してもよい。実施形態では、マネージャノード504は、ブロックチェーンから収集された複数の公開鍵R1,…,Rlに基づいて、実行トランザクション114がブロックチェーン上で確認されるまで、特定のワーカーノードPiが同じ要素の組み合わせを選択して、そのワーカーノードが作業タスク(例えば、プログラムの実行)を実行することを試みるか否かを予測できない。
【００３３】
実施形態では、コンピュータプログラムの成功した実行は、デジタル資産の移転を生じてもよい。実行トランザクション114は、計算タスクの成功した実行の一部として、実行トランザクションがブロックチェーン上で確認された後に、ワーカーノードが選択された組み合わせを所有しているという暗号的に検証可能な証明をワーカーノードが提供するような方式で担保されてもよい。一例として、図１は、選択されたワーカーノード116が(チェックマークにより示されるように)計算タスクを実行でき、他のワーカーノードが(「x」マークにより示されるように)タスクを成功して実行できないことを示す。
【００３４】
この開示の範囲内で様々な実施形態が考えられ、例えば、セーフティネット機構が実装されてもよく、それにより、プログラムを実行するように選択されたワーカーノードがない場合、各ワーカーノードは、ブロックチェーン上の実行トランザクションの確認後の或る時間の経過後に、デジタル資産の初期移転を償還(redeem)できる。実施形態では、このセーフティネット機構は、選択されたワーカーノードがプログラムの実行に失敗するか或いは拒否する場合、プログラムを誤って実行する場合、及び選択されたワーカーノードがプログラムを正しく実行しないという他のこのようなバリエーションの場合にも利用できる。さらに、マネージャノードは、計算タスクが実行されるまで、特定のワーカーノードが選択されたか否かを習得できない(例えば、実行プログラムに少なくとも部分的に符号化されたコンピュータプログラムの成功した実行は、ブロックチェーン台帳にブロードキャストされて確認される)。
【００３５】
図２は、分散システムで使用されるロックスクリプト208を生成するために、ワーカーノードPiにより使用されるアキュムレーションツリーを示しており、ワーカーは、プログラムを実行するためにワーカーノードのグループの中から選択される。ワーカーノード202は、いずれか適切なコンピュータシステムでもよく、図１に関連して説明したもののような、この開示のどこかに記載したものに従って実装されてもよい。
【００３６】
一般的に言えば、ハッシュテーブルへのデータ記憶を提供し、メンバーシップ認証を実行するために、暗号アキュムレータが使用できる。いくつかの場合、暗号アキュムレータは、RSAに基づくアキュムレータ又は双線形マップアキュムレータであり、静的(固定セットのメンバー)又は動的(セット内のメンバーの追加又は削除を可能にする)とすることができる。静的な双線形マップアキュムレータの背後にあるフレームワークについて、以下により詳細に説明し得る。例えば、G1、G2を、生成器g1、g2を有する素数位数(prime  order)pの2つの巡回乗法群とする。また、φ(g2)=g1であるような同型(isomorphism)φ:G2→G1が存在してもよい。GM、位数pの巡回乗法群が与えられれば、双線形ペアリングは、以下の特性によってe:G1×G2→GMで定義できる。
・双線形性e(Pa,Qb)=e(P,Q)ab∀P∈G1、Q∈G2且つa,b∈Zp
・非縮退(non-degeneracy):(g1,g2)≠1
・計算可能性:∃  e(P,Q)∀P∈G1,Q∈G2を計算するための効率的なアルゴリズム
以下ではG1=G2=G且つg1=g2=gと設定し、ペアリングe:G×G→GMを検討する。双線形ペアリングに基づく双線形マップアキュムレータは、n個の要素のセットE=(e1,…,en)∈Gを累積値
【００３７】
【数１】
2021530173.tif 000003
に累積できる。累積値はG内の要素であり、これはZp*内の要素を累積する点に留意する。実際に、要素(e1’,e2’,…,en’)∈Gは、セットE(e1,…,en)∈Gの元の要素の暗号ハッシュであり、すなわち、ei’=h(ei)であり、
【００３８】
【数２】
2021530173.tif 000004
である。
【００３９】
【数３】
2021530173.tif 000005
は、乗法巡回群Gの要素を入力とし、
【００４０】
【数４】
2021530173.tif 000006
内の整数を出力として生成する衝突耐性のあるハッシュ関数である。最後に、sは、秘密に保持されるトラップドア情報を表す。
【００４１】
実施形態では、アキュムレーションツリー204は、認証されたデータ構造を使用してデータを効率的に記憶するために使用される階層構造である。アキュムレーションツリー204は、通信及び検証コスト及び/又は記憶コストを低減するために使用されてもよい。アキュムレーションツリー204は、クエリに含まれるサブセットのハッシュ値の正確性を検証するために使用されてもよい。セットに対するパブリックツリーダイジェストはハッシュ値を保証し、また、ハッシュ値はセットを検証する。アキュムレーションツリー204はT(ε)(ここで、0<ε<1)として示されてもよく、T(ε)は、セットEのn個の要素が記憶されるn個のリーフを有するルート付きツリーを表す。ツリー内のレベルの数は、
【００４２】
【数５】
2021530173.tif 000007
として定義されてもよく、ノード毎の子ノードの数はO(nε)である。実施形態では、全てのリーフ(又はセットの要素)は、レベル0で識別される同じレベルにある。
【００４３】
要素e∈[e1,…,e9]を記憶するツリーT(ε)内の各リーフノードvについて、累積値Ψ(v)を要素自体の値に等しいものとして定義する。
Ψ(v)=e
レベル1<i<l(ここではl=2)にあるツリーT(ε)内の各非リーフノードについて、累積(accumulation)は以下のように定義される
【００４４】
【数６】
2021530173.tif 000008
ここで、C(v)はノードvの子の集合であり、Ψ(u)はノードuの双線形ローカルダイジェストである。例えば、図２に示すアキュムレーションツリーでは、C(v=N1)={a,b,c}であり、sはスキームのトラップドアであり、
【００４５】
【数７】
2021530173.tif 000009
は衝突耐性のあるハッシュ関数である。
【００４６】
セットEに属する所与の要素xについて、メンバーシップπ(x)のプルーフ(proof)は、アキュムレーションツリーの層毎に1つのプルーフの順序系列π(x)={πi,i=1,…,l}を含む。プルーフの各要素は、レベル毎の要素のローカルダイジェスト(local  digest)αi及び分岐証拠(branch  witness)により構成されるペアに対応する。
πi=(αi,βi),  i=1,…,l
したがって、所与の層i(ここで、1<i<l)について、所与の層iについて対応するプルーフの要素は、以下の2つの構成要素を含む。
・αi:これは、要素xをルートrにリンクするノードのパスP(x):x→rで見つかった、前の層(層i-1)におけるノードの双線形ダイジェストを表す。層1<i<lについて、αiは層i-1に存在する全ての要素について同じである。
・βi:これは「分岐証拠(branch  witness)」を表し、クエリ照会されたノードからツリーのルートまでのパスの欠落ノードを認証する証拠を表す。
【００４７】
いくつかの実施形態では、プルーフは、一般的に、信頼される関係者により計算され、ユーザ/証明者に送信される。トラップドア情報sは証明者にとって未知である。しかし、その量
【００４８】
【数８】
2021530173.tif 000010
は(例えば、第三者により)公開される。
【００４９】
全体のアキュムレーションツリーのグローバル双線形ダイジェストは、次のようになる。
d=Ψ(r)
ここで、Ψ(r)=g(h(Ψ(d))+s)(h(Ψ(e))+s)(h(Ψ(f))+s)であり、rはツリーのルートを示す。したがって、階層は、参加者(例えば、ワーカーノード)が階層内のそれぞれの位置に少なくとも部分的に基づいて異なる役割を期待するように配置され、これは、ワーカーノードにより選択された要素の組み合わせを反映してもよい。
【００５０】
検証段階では、ユーザはそのプルーフを検証器に提供する。gsが公開されている場合、検証器は、
1.α1=xであることを検査し、
2.i=2,..,lについて、
【００５１】
【数９】
2021530173.tif 000011
を検証する。
【００５２】
双線形マッピング特性を使用して、第2の関係は以下の式を検証することと等価である。
【００５３】
【数１０】
2021530173.tif 000012
このシナリオでは、上記の全ての関係が成立する場合にのみ、プルーフが受け入れられる。
【００５４】
実施形態では、公開鍵/秘密鍵ペアは、ワーカーノードにより提供されるデータを使用して構築されたアキュムレーションツリーのローカル及びグローバルダイジェストを使用して生成される。これらの鍵は、この開示に提示されたプロトコルにおいてワーカーノードにより選択された要素の組み合わせを表すために使用できる。鍵ペアは、暗号化/解読のような関連する動作を実行するために一緒に使用可能な公開鍵及び秘密鍵を示してもよい。いくつかの場合、秘密鍵は、秘密鍵の所有の証明を生成するために使用され、証明は、対応する公開鍵を使用して計算的に検証できる。
【００５５】
実施形態では、ワーカーノード202は、Sで与えられたN個の要素の中でc個の要素の組み合わせを選択する。実施形態では、ワーカーノードPiは、ワーカーの選択のc個の要素の親を表すノードN1のローカルダイジェストを構築する。実施形態では、ワーカーノードPiに対応するローカルダイジェストをΨi1として示す。実施形態では、ワーカーノードは、N個の要素の全体のセットを使用して、dとして示されるアキュムレーションツリー204のグローバルダイジェストを計算する。実施形態では、ローカル及びグローバルダイジェストは、楕円曲線上の点により表され、その和は、楕円曲線上の新たな点Ψi=Ψi1+dを取得するためにワーカーノードPiにより計算できる。実施形態では、ワーカーノードは、衝突耐性のあるハッシュ関数
【００５６】
【数１１】
2021530173.tif 000013
、すなわち、点Ψiのハッシュを使用して新たな数ci=h(Ψi)を計算する。実施形態では、この量ciは、Vi=ci×Gにより与えられる関連する公開鍵Viを用いた秘密鍵と考えられ、Gは楕円曲線の生成点である(g=G)。楕円曲線の同形性によって、ワーカーノードPiは、以下により与えられる新たな公開鍵Riを計算する。
Ri=Qi+Vi=ri×G
ここで、ri=ki+ciは公開鍵Riに関連する秘密鍵である。
【００５７】
実施形態では、図２は、ワーカーノード202の公開鍵を構築するための計算環境200を示す。例示的な例として、9個の要素のセットが図２に示されているが、ワーカーノードの数、選択される要素の数及びこれらの組み合わせのような様々な要因に基づいて、より大きいツリー及びより小さいツリーが利用できる。実施形態では、第1のワーカーノードPiは、要素の第1の組み合わせ(例えば、図２に示す(a,b,f))を選択し、第2のワーカーノードPjは、組み合わせ(例えば、(a,i,g))を選択し、その結果、異なる値を有するローカルダイジェストΨi1及びΨj1の生成を生じる。同じグローバルダイジェストdが、ローカルダイジェストΨi1及びΨj1を生成するためにワーカーノードにより使用される点に留意すべきである。
【００５８】
実施形態では、N1のローカルダイジェストは、c=3個の子の要素の順序に依存せず、残りの6個の要素(すなわち、図２の点線のボックスに表される、ワーカーの組み合せに選択されていない要素)の分布は、グローバルダイジェストの計算には無関係である。実施形態では、全ての要素e1,…,eNは、グローバルダイジェストを正確に計算するために、ワーカーノードにより生成されたアキュムレーションツリー206内に少なくとも1回(例えば、ちょうど1回)存在するが、残りの要素は無関係でもよい。
【００５９】
実施形態では、ワーカーノードPiは、公開鍵Riを使用してそのチケットのためのデジタル資産の移転を担う償還スクリプト208を生成し、後者は、その選択された組み合わせ及び一時的な公開鍵Tiを含む(しかし、隠蔽される)。実施形態では、ワーカーノードは、メンバーシップグループへの参加の一部として、マルチ署名スクリプトを構築する。例えば、ワーカーノードPiは、以下のように、1-of-3マルチ署名スクリプトを構築してもよい。
OP_1  Ri  Ti  D  OP_3  OP_CHECKMULTISIG
ここで、Riは、ワーカーノードPiにより選択された要素の組み合わせを含む公開鍵であり、Tiは、Piにより生成された第2の一時的な公開鍵であり、Dは、マネージャノードにより提供される公開鍵である。このマルチ署名スクリプトは、ワーカーノードPiが2つの公開鍵に割り当てられた空間を使用して、要素の選択された組み合わせ及び検証公開鍵を記憶することを可能にし、一方で、第3の空間は、マネージャノードが(公開鍵Dに関連する秘密鍵を提供することにより)スクリプトをロック解除するために使用される。したがって、実施形態では、ワーカーノードPiは、以下のスクリプト208を構築する。
【００６０】
【表１】
2021530173.tif 000014
実施形態では、スクリプト208は、ワーカーノードPiにより或いはワーカーノードPiの代わりに、いずれかの時点で関連するアドレスに送信されるデジタル資産の制御を移転するために実行でき(公開鍵Fiに関連する秘密鍵で署名する)、或いは、これは、マネージャノードが特定の時間ΔTSが経過した後に資金提供を償還することを可能にする(Dに関連する秘密鍵で署名する)。ビットコインのコアのリリースにバグがあるため、上記の量xは検査中にスタックから除去された余分な値でもよい点に留意すべきである。ここでは記載されているが、量は、この開示のいずれかの箇所で明確にするために省略されてもよい。
【００６１】
図３は、ワーカーノード302及びワーカーがメンバーシップグループへの登録を確認するために使用し得るワーカーチケット304を示す計算環境300を示す。実施形態では、マネージャノードは、メンバーシップグループのワーカーノードの間でコンピュータプログラムの実行を委任する。
【００６２】
実施形態では、メンバーシップグループに参加する各ワーカーノードは、メンバーシップグループへのノードの包含を認証するために使用できるワーカーチケットを生成してブロードキャストする。各ワーカーチケットは、マネージャノードにより、作業(例えば、コンピュータプログラム)の実行のためにワーカーノードを選択するために使用可能な、ワーカーノードにより生成された情報を含んでもよく、当該情報は、情報に関連する特定のワーカーノードの識別を明らかにしない。実施形態では、ワーカーチケット304は、ワーカーノード302によりグループ内のメンバーシップを確立するために使用され、メンバーシップグループ内の複数のワーカーノードの中のワーカーノードに作業(例えば、コンピュータプログラムの実行)を分配するための偏りのない選択及び検証プロセスにおいて使用される量(例えば、Ri及びTi)を含む。
【００６３】
図３に示すワーカーノードPiのような各ワーカーノードは、少なくとも1つのインプット及び1つのアウトプットを含むワーカーチケットTxiを生成する。実施形態では、1つ以上のインプットは、ワーカーノードにより所有される未使用トランザクションアウトプット(unspent  transaction  output,  UTXO)であるαiを含み、一方で、アウトプットは、要素xをルートrにリンクするノードのパスP(x):x→rで見つかった、前の層(層i-1)内のノードの双線形ダイジェストを含む。
【００６４】
実施形態では、ワーカーノードPiは、ワーカーチケットTxiを生成するために、図２に関連して説明したロックスクリプトのようなロックスクリプト306を使用し、ワーカーチケットTxiにおいて、ワーカーノード302は、デジタル資産をスクリプトから導出されたアドレスに移転する。トランザクションはブロックチェーンネットワークにブロードキャストされ、ワーカーノードが、作業(例えば、プログラムの実行)が分配されるメンバーシップグループのメンバーであることを認証するためにマネージャノードにより使用されてもよい。
【００６５】
実施形態では、各ワーカーノードPiは、2つの一時的な公開鍵/秘密鍵ペアを生成する。
Qi=ki×G
Ti=yi×G
ここで、Gは楕円曲線の生成子である(g=G)。2つの秘密鍵ki及びyiは、以下の関係を検証する。
ki=yi  mod  z
ここで、zは、マネージャノードにより選択されて公に利用可能にされている大きい数である。zは大きくなるべきであるが、楕円曲線が定義されるグループの順序を定義する素数pによってz≦pであることを検証すべきである。実施形態では、鍵ペアは、一回限りの使用の鍵である。この理由は、秘密鍵が、プログラムを実行するために選択されるワーカーノードにより明らかにされる(例えば、ブロックチェーンネットワークにブロードキャストされる)可能性があるからである。第2の一時的な公開鍵/秘密鍵ペアは、検証鍵ペアと呼ばれてもよく、いくつかの実施形態では、作業項目を実行するために選択されたと主張する特定のワーカーノードが実際に選択されたという計算的に検証可能な保証を提供するために使用される。いくつかの実施形態では、このような信頼関係が必要でないか或いは他の技術を使用して確立される場合のように、検証鍵ペアの実装は任意選択である。
【００６６】
実施形態では、ワーカーノードPiはトランザクションTxiをブロードキャストし、トランザクションはブロックチェーンに対して確認される。実施形態では、複数のワーカーノードP1,…Plは、ブロックチェーンネットワークに対して確認される対応するワーカーチケットを生成する。マネージャノードは、ブロックチェーン台帳の内容を監視し、複数のワーカーノードの公開鍵Ri及びTiを収集し、最大閾値数のワーカーノードがグループメンバーシップに登録したことを検出したとき、プログラムを実行するためのワーカーノードの選択を含むプロセスの次のステップに進んでもよい。
【００６７】
図４は、プログラムを実行するためのワーカーノードの選択に関連して利用され得る計算環境400を示す。マネージャノード402は、いずれか適切なコンピュータシステムでもよく、図１に関連して説明したもののような、この開示のどこかに記載したものに従って実装されてもよい。実施形態では、マネージャノード402は、ランダムに選択された要素を使用してアキュミュレーションツリー404を構築し、アキュミュレーションツリー404のランダムに選択されたリーフノードから導出された量に少なくとも部分的に基づいて公開鍵406を生成する。
【００６８】
マネージャノード402は、c個の要素のランダムな組み合わせを選択し、事前に選択されてワーカーノードに分配されたパラメータを使用して、図４に示されるアキュムレーションツリー404を構築し、第1のノードのローカルダイジェスト及びグローバルダイジェストを計算してもよい。図４に示すように、実施形態では、マネージャノードは、CW=cW×Gとして計算された新たな公開鍵406を取得し、cWは、マネージャノードにより選択された要素の組み合わせについてのローカルダイジェストと、アキュムレーションツリーのグローバルダイジェストとを表す楕円曲線上の2つの点の合計のハッシュである。例えば、図４において、マネージャノードにより選択されたランダムな組み合わせは、新たな公開鍵CWを計算するために使用される(b,d,e)でもよい。実施形態では、ランダムな組み合わせの一部として選択されない要素(図４の点線のボックスで表される)の順序付けは無関係であるが、要素のそれぞれがアキュムレーションツリー404に含まれることが必要であるが、
図５は、公開鍵が、メンバーシップグループに参加するワーカーノードによりサブミットされたワーカーチケットから構築される計算環境500を示す。計算環境500は、図１〜図４に関連して説明したもののような、この開示のどこかに記載したものに従ってもよい。
【００６９】
実施形態では、ワーカーノードP1,…,Pl502は、それぞれの公開鍵R1,…,Rl506を含むワーカーチケットをブロックチェーンネットワークにブロードキャストし、ワーカーチケットは、タスクを実行する(例えば、コンピュータプログラムを実行する)ために複数のワーカーノードの中からワーカーノードを選択することを担うマネージャノード504により検出されて収集される。ワーカーノードPiにより提供される各公開鍵Riについて、マネージャノード504は、それぞれの公開鍵Riから図４に関連して説明したランダムに選択された組み合わせCWに関連する点を減算することにより、楕円曲線上の新たな点Ciを計算する。
Ci=Ri-CW=(ki+ci-cW)×G
したがって、マネージャノード504は、公開鍵R1,…,Rlから複数の楕円曲線点C1,…,Cl508を計算してもよい。したがって、ci=cWである場合にのみ、例えば、減算から生じる公開鍵/秘密鍵ペアが、ワーカーノードのワーカーチケット(ciにより表される)がマネージャノードのランダムに選択された組み合わせから導出された量cWと一致する場合(ci=cW)に、ワーカーノードにより生成された(秘密に保持される)最初の一時的な鍵ペアに対応する場合にのみ、Ci=Qiが成立する。
【００７０】
実施形態では、マネージャノード504は、この等価性が所与のワーカーノードについて検証されるか否かを予期できない。したがって、マネージャノード504は、マネージャノード504が様々なワーカーノードにより選択される量を推定するために使用できる更なる知識を欠く様々な実施形態において、c個の要素の偏りのない組み合わせを引き出すことができる。実施形態では、マネージャノード504は、これらの新たに生成された公開鍵の有効性を検査できず、すなわち、マネージャノード504は、ブロックチェーンから収集された複数の公開鍵R1,…,Rl506に基づいて、実行トランザクションがブロックチェーン上で確認されてワーカーノードが作業タスク(例えば、プログラムの実行)を実行することを試みるまで、特定のワーカーノードPiが要素の同じ組み合わせを選択したか否かを予測できない。実施形態では、ロックスクリプト510は、実行トランザクション内で符号化され、図６に関連して説明するものに従う。実施形態では、マネージャノード504は、l個の新たな公開鍵ci(ここで、i∈[1,l])及びl個の検証公開鍵Ti(ここで、i∈[1,l])を使用してコンピュータプログラムの実行を担うロックスクリプト510を作成し、それにより、マネージャノードにより選択された組み合わせと同じランダムな組み合わせを選択してブロードキャストしたワーカーノードのみが、スクリプトをロック解除できるようにする。実施形態では、検証公開鍵の使用を取り巻く技術は任意選択であり、この開示の範囲で考えられるいくつかの実装から省略できる。
【００７１】
図６は、マネージャノード602が、メンバーシップグループ内の複数のワーカーノードから選択されたワーカーノードにより実行できるコンピュータプログラムの少なくとも一部を含む実行トランザクション604を生成する計算環境600を示す。実行トランザクション604は、メンバーシップグループ内のワーカーノードからの1つ以上のインプット(例えば、ワーカーノード毎に1つのインプット)と、選択されたワーカーノードのみがプログラムを正常に実行できるように、コンピュータプログラムの実行を担うロックスクリプトを含むアウトプットとを含んでもよい。
【００７２】
計算環境600に示すマネージャノード602は、図１、図４及び図５に関連して説明したものに従うマネージャノードでもよく、いずれか適切な方式で実装されてもよい。マネージャノード602は、コンピュータシステムにここに記載の様々な技術を実行させるようにコンピュータシステムの1つ以上のプロセッサにより実行できる命令を含む、1つ以上のコンピュータ読み取り可能媒体(例えば、非一時的なコンピュータ読み取り可能媒体)を含んでもよい。マネージャノード602は、ブロックチェーンネットワークのノードでもよい。
【００７３】
実施形態では、マネージャノード602は、l個の新たな公開鍵Ci(ここで、i∈[1,l])及びl個の検証公開鍵Ti(ここで、i∈[1,l])を使用して、コンピュータプログラムのためのロックスクリプト606を作成する。いくつかの実施形態では、マネージャノードは、公開鍵が与えられる順序を尊重する必要はなく、結果として、ワーカーノードPiにより提供される公開鍵Ci及びTiは、それぞれマネージャノード602により使用される2つのセットの公開鍵{C1,C2,..,Cl}及び{T1,T2,..,Tl}において同じ位置にある必要はない点に留意すべきである。
【００７４】
実施形態では、マネージャノードは、ワーカーノードが、ΔTEの後にTiに関連する秘密鍵で署名することにより、トランザクション内の1つのUTXOを償還できるような方法で、プロトコルロールバックトランザクションをブロードキャストする。この選択肢は、マネージャノード602がプロトコルに従って実行トランザクションをブロードキャストできない場合に対するワーカーノードへの保証として利用されてもよい。実施形態では、プロトコルは、実行トランザクション604が設定された期間内に公開されることを要求し、特定の数のインプット又はアウトプット、インプット及び/又はアウトプットとしての特定の量等を含む。実施形態では、プロトコルロールバックトランザクションはまた、どのワーカーノードもプログラムを実行しない場合に、ワーカーノードにロールバック選択肢を提供する。この理由は、ワーカーノードがマネージャノードと同じ組み合わせを選択しなかったため、ワーカーノードがプログラムを実行するのを拒否したため、ワーカーノードがプロトコルにより規定された時間内にプログラムを実行しなかったため等である。実施形態では、どのワーカーノードもプログラムを実行しない場合、ΔTEの後に、ワーカーノードはUTXOを要求することによりロールバックを実行し、プロトコルが終了する。
【００７５】
他方、どのワーカーノードもプログラムを実行せず、ワーカーノードがプロトコルロールバックトランザクションでUTXOを要求した場合、マネージャノードは、実行トランザクションで担保されたデジタル資産をロック解除できるはずである。したがって、実行トランザクション604内のUTXOにより担保されたデジタル資産をロックするスクリプトにおいて、マネージャノードは、特定の時間ΔTR≦ΔTEが経過した後にどのワーカーノードも行っていない場合には、UTXOに担保されたデジタル資産の制御を移転する選択肢を追加すべきである。
【００７６】
実施形態では、マネージャノード602は以下のロックスクリプト606を構築し、オペコードはビットコインに基づくネットワークで使用されるものに従ってもよい。さらに、オペコードOP_ECMULは楕円曲線上で点の乗算を実行できるオペコードを示す(コメント及び注釈は先行する「#」の記号で含まれており必須ではない)。
【００７７】
【表２】
2021530173.tif 000015
簡潔にするために、上記のロックスクリプトの例は、l=3個のワーカーノードを考慮しているが、更なるワーカーノードをサポートするように適合できる。例示的なロックスクリプトの最初の2行は、償還スクリプトの最後のインプットの値を検査する。
・1→locking_script_rollback:当該スクリプトは、マネージャノード(D)の署名及び公開鍵である2つ以上のインプットを期待する。当該スクリプトは、時間ΔTRが経過した後にロック解除できる。
・そうでない場合→locking_script_execution:2つのインプットが提供される。ワーカーノードPiは、スクリプトに含まれる公開鍵Ci及びTiに関連する2つの秘密鍵ki及びyiを使用してスクリプトを試みてロック解除することが期待される。
【００７８】
次いで、当該スクリプトは、デジタル資産を転送するための2つの選択肢を符号化するように、IF及びELSEステートメントに分割される。
【００７９】
IFステートメント内のオペコードのブロックは、locking_script_rollbackサブルーチンと呼ばれてもよく、どのワーカーノードも計算タスクを実行しなかった場合にマネージャノードのための(プロトコルロールバックトランザクションで転送されたデジタル資産の)ロールバックの選択肢を含む。実施形態では、スクリプトは、特定量の時間ΔTRが経過した後に、どのワーカーノードもプログラムを実行しなかった場合(例えば、ワーカーノードにより選択された組み合わせのいずれも好適な組み合わせに一致しないため)、スクリプトで使用された公開鍵Dに関連する秘密鍵で署名して、デジタル資産がマネージャノードにより償還できるように構築される。
【００８０】
ロックスクリプトのELSEステートメントにおけるオペコードの第2のブロックは、locking_script_executionサブルーチンと呼ばれてもよく、ワーカーノードが計算タスク(例えば、コンピュータプログラム)を実行するための選択肢を含む。ワーカーノードPiが2つのインプットa及びbでスクリプトをロック解除することを試みることを仮定する。スクリプトのこの部分は、3つのサブパートを含む。
・a×G=Cj,∀j∈[1,l]であるか否かを検査し、すなわち、ワーカーノードが選択され、集合{C1,C2,..,Cl}内の1つの公開鍵がQiに対応する(すなわち、a=ki)か否かを検査する。
・b×G=Tj,∀j∈[1,l]であるか否かを検査し、すなわち、1つの公開鍵がTiに対応する(すなわち、b=yi)に対応しているか否かを検査する。
・a=b  mod  zであるか否かを検査し、選択されたワーカーノードにより提供された2つの秘密鍵がモジュラス関係を検証し、ワーカーノードが当該ラウンドについて作成された2つの元の秘密鍵を提供することを確保するki=yi  mod  z。
【００８１】
実施形態では、最後の検査(すなわち、モジュラス検査)は、Vi≠CWであるときスクリプト内でCi=Qi+Vi-CWに関連する秘密鍵を計算することにより、ワーカーノードが選択されたとワーカーノードPiがだまされて誤って主張することを試みないことを確保する。いくつかの実施形態では、モジュラス検査は、秘密鍵のレベルにおいてのみ有効であり、等価性は、関連する公開鍵について真でない点に留意すべきである。マネージャノードは、プログラム実行のためのロックスクリプトを構築するときに、ワーカーチケットからワーカーノードの選択した組み合わせについて何も習得できない。
【００８２】
ロックスクリプトの例は、この開示の範囲内で考えられる多くの変形の中の1つに過ぎない。例えば、実施形態では、ロックスクリプトは、第2の公開鍵を検査するための命令及び/又はモジュラスa=b  mod  zが当てはまるか否かを検査するための命令を含まない。これらの検査は、ワーカーノードが誠実であり、ワーカーノードが実際には好適な組み合わせを選択しなかったときにプログラムを実行するように選択されたという不正な主張を試みないことを確保する、他の保証が存在する実施形態(例えば、他の信頼プロトコル)では不要でもよい。実施形態では、ELSEステートメント内のオペコードブロックの構造は、スクリプト内で考慮される鍵の数に依存する。図６に示す形式では、ELSEステートメント内のスクリプト(最初のサブパートのみ、すなわち最初の秘密鍵の検証)は以下のように展開できる。
【００８３】
【表３】
2021530173.tif 000016
実施形態では、マネージャノードは、上記のスクリプトによってロックされたl×x個のBTCの量の固有のアウトプットで、ワーカーノードにより使用されたl個のUTXOをインプットとして含む、ブロックチェーン上で確認されたワーカーチケットTxi(ここで、i∈[1,l])のトランザクション識別子を使用して実行トランザクションを構築する。実行トランザクションがΔTEの前にブロックチェーン上で確認されると仮定すると、ワーカーノードは、プログラムを実行することをそれぞれ試みることができる。しかし、好適な組み合わせを選択したワーカーノードのみが、プログラムを成功して実行できてもよく、成功した実行は、実行トランザクションにより担保されたデジタル資産の移転又はその他の機能を含んでもよい。
【００８４】
実施形態では、t>ΔTRにおいて、どのワーカーノードもプログラムを実行しなかった場合(場合によっては、マネージャノードにより選択された組み合わせが、どのワーカーノードにより選択された組み合わせとも一致しないことを示す)、マネージャノードは、プロトコルロールバックトランザクションにおいてマネージャノードにより移転されたデジタル資産の代替として、ワーカーチケットにより担保されたデジタル資産を償還する。その後すぐに、t≧ΔTEにおいて、ワーカーノードはプロトコルロールバックトランザクションにおいてx個のBTCをそれぞれ償還し、登録プロセスの一部としてワーカーノードのそれぞれがワーカーチケットにおいて提供したデジタル資産の移転を有効にロールバックする。
【００８５】
実施形態では、1つのワーカーノード(例えば、ワーカーノードPi)は、デジタル資産の制御を移転するために使用可能になり得るプログラムを成功して実行し、スクリプトをロック解除したときに2つの秘密鍵(ki及びyi)を明らかにする。次いで、マネージャノードはl個の秘密鍵のうち1つyiを認識し、その結果、プロトコルロールバックトランザクションにおいてスクリプトをロック解除でき、l個のアウトプットのデジタル資産の制御を効果的に移転する。
【００８６】
実施形態では、プロトコルに従って、l個のワーカーノードは、ブロックチェーントランザクションの形式のワーカーチケットをサブミットし、各トランザクションはアウトプットを有し、コンピュータプログラムの一部として実行された場合、マネージャノードへのデジタル資産の制御を移転し、ワーカーチケットは、所与のタスク(例えば、プログラム実行)のために選択されたN個の要素のセットの中でワーカーノードにより選択されたc個の要素の組み合わせを符号化する情報を含む。実行トランザクションのスクリプトのロックは、正しい情報を提供した場合に、最大で1つのワーカーノードのみが償還できるように構築される。
【００８７】
確率の原理によれば、1つのワーカーノードが選択される確率は、二項係数の逆数により与えられる。
【００８８】
【数１２】
2021530173.tif 000017
ここで、
【００８９】
【数１３】
2021530173.tif 000018
は、N個の要素のセットの中でc個の要素の可能な組み合わせの数を表す。
【００９０】
例えば、図２に関連して検討された例のようにN=9、c=3とすると、84個の可能な組み合わせが存在し、したがって、ワーカーノードが選択される確率は〜1.2%である。
【００９１】
実施形態では、各ワーカーノードは、要素の完全なセットが与えられ、N個の要素のセットの中でc個の要素のいずれかの組み合わせを選択する自由が与えられる。したがって、2つのワーカーノードPi及びPj(i≠j)が同じ組み合わせを選択する確率は以下により与えられる。
【００９２】
【数１４】
2021530173.tif 000019
例えば、様々な実施形態で検討される例のようにN=9、c=3とすると、2つのワーカーノードが同じ組み合わせを選択する確率は〜0.01%である。
【００９３】
したがって、2つ以上のワーカーノードが同じ組み合わせを選択する確率は以下により与えられる。
【００９４】
【数１５】
2021530173.tif 000020
ここで、先頭の項は、2つのワーカーノードが同じ組み合わせを選択する確率である。
【００９５】
実施形態では、パラメータ(N,c)及びn(ラウンド毎のワーカーノードの最大数)は、P(ci={cj},i≠j)が、2つ以上のワーカーノードが同じ組み合わせを選択する無視できる確率を超えないことを確保するために、閾値確率より下にとどまるように選択される。
【００９６】
図７は、マネージャノード702がタスクを実行する(例えば、プログラムを実行する)ために複数のワーカーノードからワーカーノードの偏りのない選択を実行するために、プロトコルに従って利用されるプロトコルロールバックトランザクション704を生成する計算環境700を示す。実施形態では、マネージャノード702は、時間TCにおいてブロックチェーン上のl個のワークチケットの確認を受信/観察すると、当該ワークチケットの償還スクリプトに含まれるl個の公開鍵ペア{Ri,Ti}を収集する。マネージャノード702は、Ri=Qi+Vi=(ki+ci)×Gを構築するときにワーカーノードPiにより選択された公開鍵/秘密鍵ペア(Qi,ki)を認識しないので、マネージャノード702はciを推定できず、したがって、ワーカーノードにより選択された組み合わせを習得できない。
【００９７】
ワーカーノードが好適な組み合わせを選択して実行トランザクションを構築する前に、マネージャノードは、マネージャノードがプロトコルに従うといういくつかの保証をワーカーノードに提供してもよい。実際に、特定の時点ΔTSの後に、マネージャノードは、ワーカーチケットTxi(ここで、i∈[1,l])においてワーカーノードによりコミットされたデジタル資産の制御を移転する機能を有する。その時点で、マネージャノードは単にデジタル資産を「盗み」、プロトコルを早期に終了させてもよい。いくつかの実施形態では、マネージャノードが正直であることを確保するために、後者はプロトコルロールバックトランザクションを作成し、マネージャノードが実行トランザクションをサブミットしない場合に各ワーカーノードがデジタル資産を取得する時間ウィンドウを有するように構築されたl個の異なるP2SHアドレスにデジタル資産の制御を移転する。実施形態では、プロトコルロールバックトランザクションの1つ以上のインプットは、デジタル資産を含み(例えば、ワーカーチケットにおいてワーカーノードによりマネージャノードに移転されたデジタル資産と同等の値又はこれに基づく値を有する)、マネージャノードにより制御されるデジタル資産の制御を移転するために使用可能である。
【００９８】
実施形態では、マネージャノード702は、ワーカーノードのワーカーチケットTxiの償還スクリプトに含まれる各登録ワーカーノードTiの公開鍵を使用して、プロトコルロールバックトランザクションのためのロックスクリプトを構築し、以下のロックスクリプトを構築する。
【００９９】
【表４】
2021530173.tif 000021
上記のコードは、マネージャノードの選択肢及びワーカーノードの選択肢の2つの実行パスが存在するロックスクリプトの様々な実装の中の1つと考えられてもよい。実施形態では、マネージャノードの選択肢の実行は、2つのインプット、すなわち、トランザクションに関連する署名及び2つの公開鍵(公開鍵D及びワーカーノードにより生成されたいずれかの公開鍵Ti(ここで、i∈[1,l]))を提供することにより、ロック解除できる。実施形態では、ワーカーノードの実行は、2つのインプット、すなわち、トランザクション及び公開鍵Tiに関連する署名と公開鍵Ti自体とを使用して、特定の時間ΔTEが経過した後にロック解除できる。
【０１００】
実施形態では、図７に示すように、スクリプトは、マルチ署名サブスクリプトを含む。様々なブロックチェーンネットワークのコンテキストでは、マルチ署名(multisignature)のアウトプットで許容される最大数の公開鍵が存在してもよい。より多くの公開鍵が検査される必要がある場合(例えば、ワーカーノードの数がマルチ署名のオペコードでサポートされる鍵の最大数を超える場合)にスクリプトを拡張するために、マネージャノードは、if-elseステートメントに埋め込まれたいくつかのマルチ署名スクリプトを含むロックスクリプトを構築したり、マネージャノードは、いくつかのプロトコルロールバックトランザクションを作成したりしてもよい。
【０１０１】
双方の選択肢は2つのインプットを必要とするので、2つの実行パスは、第3のインプット、すなわち、マネージャノードの選択肢では1及びワーカーノードの選択肢では2(又はいずれかの他の数)を使用して区別される。トランザクション及び公開鍵に関連する署名を生成するために、ユーザは、公開鍵に関連する秘密鍵を認識しなければならない。マネージャノードは、ワーカーノードPiにより与えられた公開鍵Tiを認識して、このようなスクリプトを構築できるが、マネージャノードは、Tiに関連する秘密鍵yiを認識せずに、最初にスクリプトをロック解除できない。他方、ワーカーノードPiは特定の時間ΔTEの後にこのようなスクリプトをロック解除できる。したがって、実施形態では、プロトコルは、マネージャノードが実行トランザクションを作成してそれがブロックチェーン上で確認されるのを見るために、時間ウィンドウ[ΔTS,ΔTE]を残す。様々な実施形態では、ウィンドウの継続時間は、特定のブロックチェーンネットワークに対して確認されるトランザクションの推定時間又は予想時間のような、様々な要因に基づいて選択できる。
【０１０２】
図８は、実施形態に従ってメンバーシップグループに参加するために、ワーカーチケット(ワークチケット又はトランザクションの要求とも呼ばれる)を提示するためのプロセス800の例示的な例を示す。プロセス800(又はここに記載のいずれかの他のプロセス又はその変形及び/又は組み合わせ)の一部又は全部は、コンピュータ実行可能命令で構成された1つ以上のコンピュータシステムの制御下で実行されてもよく、ハードウェア、ソフトウェア又はこれらの組み合わせにより、1つ以上のプロセッサ上で併せて実行するコード(例えば、コンピュータ実行可能命令、1つ以上のコンピュータプログラム又は1つ以上のアプリケーション)として実装されてもよい。プロセス800は、図１に関連して説明したもののような、この開示に従って記載されるワーカーノードにより実行されてもよい。コードは、例えば、1つ以上のプロセッサにより実行可能な複数のコンピュータ読み取り可能命令を含むコンピュータプログラムの形式で、コンピュータ読み取り可能記憶媒体上に記憶されてもよい。コンピュータ読み取り可能記憶媒体は、非一時的なコンピュータ読み取り可能媒体でもよい。いくつかの実施形態では、プロセス800を実行するために使用可能なコンピュータ読み取り可能命令の少なくとも一部は、一時的な信号(例えば、伝搬する一時的な電気又は電磁伝送)のみを使用して記憶されるものではない。非一時的なコンピュータ読み取り可能媒体は、一時的な信号のトランシーバ内に非一時的なデータ記憶回路(例えば、バッファ、キャッシュ及びキュー)を含んでもよい。
【０１０３】
システムは、メンバーシップグループに参加するための要求をサブミットしてもよい802。要求は、メンバーシップグループ内の複数のワーカーノードの間のタスク(例えば、プログラムの実行)の分配を調整するマネージャノードにサブミットされてもよい。実施形態では、マネージャノードは、マネージャノードがメンバーシップグループに参加するための要求を受け入れていることを(例えば、ブロックチェーンネットワーク又はいずれかの他の適切な機構を介して)ブロードキャストし、これは登録期間、登録が終了する前にメンバーシップグループに参加できるワーカーノードの最大数のような更なる情報を含んでもよい(いくつかの実施形態では、これはプロトコルを加速させる)。
【０１０４】
実施形態では、システムは、メンバーシップへのワーカーノードの登録を調整するマネージャノードからトラップドア情報s及び公開鍵Dを受信する804。実施形態では、トラップドア情報s及び公開鍵Dは、図２に関連して説明したような、この開示のどこかに記載された技術を使用してマネージャノードにより生成される。
【０１０５】
ステップ804から分離するか或いはステップ804と共に、システムは、アキュムレーションツリーのためのパラメータのセットを受信してもよい806。暗号アキュムレータは、ハッシュテーブル内のデータ記憶を提供するために使用でき、メンバーシップ認証を実行するために使用できる。実施形態では、グループメンバー登録において1つ以上のワーカーノードにより利用される暗号アキュムレータは、静的な双線形マップアキュムレータである。実施形態では、G1、G2は、生成器g1、g2及びφ(g2)=g1であるようなφ:G2→G1を有する素数位数pの巡回乗法群である。実施形態では、パラメータのセットは、N個の要素のセット{e1,…,eN}と、生成器gのグループと、要素の数c(ここで、1<c<N)と、セット内の要素の数Nとを含む。
【０１０６】
実施形態では、システムは、要素のセットで与えられたN個の要素の中でc個の要素の組み合わせを選択することにより公開鍵を構築し、選択されたc個の要素を表すローカルダイジェストを構築し、ローカル及びグローバルダイジェストに少なくとも部分的に基づいて計算された楕円曲線上の点Ψを取得する。実施形態では、ワーカーノードPiは、衝突耐性のあるハッシュ関数
【０１０７】
【数１６】
2021530173.tif 000022
、すなわち、点のハッシュΨiを使用して新たな数ci=h(Ψi)を計算する。実施形態では、この量ciは、Vi=ci×Gにより与えられる関連する公開鍵Viを用いた秘密鍵であると考えられ、Gは楕円曲線の生成点である(g=G)。楕円曲線の同形性によって、ワーカーノードPiは以下により与えられる新たな公開鍵Riを計算する
Ri=Qi+Vi=ri×G
ここで、ri=ki+ciは公開鍵Riに関連する秘密鍵である。
【０１０８】
実施形態では、システムは、第2の公開鍵Ti=yi×Gを生成し、Gは楕円曲線の生成器(g=G)であり、2つの秘密鍵ki及びyiは以下の関係、すなわち、ki=yi  mod  zを検証する。ここで、zはマネージャノードにより選択されて公に利用可能にされた大きい数である。実施形態では、システムは、デジタル資産の制御を移転するインプット(例えば、パラメータとしてワーカーノードにより指定される)と、Ri及びTiを含むトランザクションアウトプットとを含むワークチケットの要求をブロードキャストする810。ワーカーチケットは、図２に関連して記載されたものに従ってもよい。実施形態では、ワーカーノードは、異なる組み合わせを使用して生成された複数のワーカーチケットをサブミットしてもよい。
【０１０９】
図９は、少なくとも1つの実施形態に従って複数のワーカーノードのワーカーノードの間で作業項目(例えば、プログラム実行)の偏りのない分配を実行するためのプロセス900の例示的な例を示す。いくつかの場合、プロセス900は、図１〜図７に関連して説明したマネージャノードを少なくとも部分的に使用して実行される。
【０１１０】
実施形態では、マネージャノードは、ワーカーノードがグループメンバーシップに登録することを要求する指示を公開するか或いは公に利用可能にする。グループメンバーシップからのワーカーノードは、コンピュータプログラムの実行のような様々なタスクを実行するために選択されてもよい。実施形態では、ワークチケットの要求をサブミットするいずれかのワーカーノードは、グループメンバーシップに参加し、タスクを実行するために選択されてもよい。実施形態では、ワークチケットの要求のサブミットは、デジタル資産の移転を含む(例えば、デジタル資産の制御は、ワーカーノードからマネージャノードに移転される)。
【０１１１】
システムは、所定の期間、及び/又は最大数のワーカーノード及び/又は作業サブミットチケットが受信されるまで、グループメンバーシップの登録をオープンにしてもよい。
【０１１２】
実施形態では、システムは、グループメンバーシップに参加するための要求を受信する902。実施形態では、要求は、グループに関連する識別子を含む(例えば、マネージャノードは、複数のグループメンバーシップの間の作業項目の実行を同時に調整している)。システムは、上記のように、トラップドア情報s、公開鍵Dを提供してもよい904。システムはまた、N個の要素のセット{e1,...,eN}と、グループ生成器gと、要素の数c(ここで、1<c<N)と、セット内の要素の数Nとを含むパラメータのセットを提供してもよい906。提供される情報は、アキュムレーションツリーを生成するために、ワーカーノードにより使用されてもよい。
【０１１３】
システムは、更なる時点で、特定のノードがメンバーシップグループに参加するために登録しており、タスクを実行する(例えば、コンピュータプログラムを実行する)ように選択されることを希望するという指示を含むワークチケットの要求を受信してもよい。実施形態では、ワークチケットの各要求は、ワーカーノードPiについて、量Ri及びTiを含む。いくつかの場合、ワークチケットは、ワーカーノードからマネージャノードへのデジタル資産の移転を含む。実施形態では、マネージャノードは、最大数のワーカーノードに達したか否か908を検査する。ワーカーの最大数は、いずれか2つのワークチケットが重複する量を含む(例えば、同じ組み合わせが2つのチケットで選択される)確率が特定の閾値確率を下回るように調整される様々なパラメータに少なくとも部分的に基づいて選択されてもよい。実施形態では、ワーカーノードの最大数及び/又は登録ノードの数は、周期的に公開及び/又は更新される。
【０１１４】
システムはまた、登録ウィンドウが閉じたか否か910を検査してもよい。登録ウィンドウは、タスクを実行するためにいつノードが選択されるかを示す時間でもよい。グループメンバーシップが埋まっているときのようないくつかの場合、最初に決定された登録期限より前に登録ウィンドウが閉じられてもよい(例えば、期限は、単にプロトコルがワーカー選択段階に進む最終の期限である)。実施形態では、ワーカーの最大数に達したか否かの決定、及び登録ウィンドウが閉じられたか否かの決定は、並列又は非決定的な順序で実行されてもよい。
【０１１５】
システムは、登録段階が終了したと決定した後に(例えば、登録ウィンドウが過ぎたか、或いは最大数のノードが登録されたため)、選択段階に進んでもよく、ここで、ワーカーノードが計算タスクを実行する(例えば、コンピュータプログラムを実行する)ように選択される。システムは、図７に記載されるように、プロトコルロールバックトランザクションを生成し、ブロックチェーンにブロードキャストしてもよい。いくつかの実施形態では、プロトコルロールバックトランザクションのブロードキャストは、特定の時間ΔTSの前に発生しなければならず、そうでない場合、ワークチケットの要求は(例えば、デジタル資産をワーカーノードに再移転することによりデジタル資産の移転をロールバックすることのように、所定の時間ΔTSの後にロールバック動作を実行できるチケットに含まれる命令を実行することにより)ロールバックされてもよい。いくつかの実施形態では、マネージャノードの動作に関して更なる信頼の制約が存在する計算環境等では、プロトコルロールバックトランザクションは必要ない点に留意すべきである。例えば、マネージャノードが政府又は他のこのような組織により操作又は制御される場合、ワーカーノードは、政府がプロトコルに従って動作するという十分な信頼を有してもよく、及び/又は、プロトコルに従わない場合に政府に対して強制され得るオフチェーンの救済を有してもよい。
【０１１６】
実施形態では、実行トランザクションは、図４〜図６に従って説明した技術に従って生成され914、ブロードキャストされる。ワーカーノードは、時間ウィンドウ[ΔTS,ΔTE]内に実行トランザクションを作成してもよい。このプロセスの一部として、システムは、N個の要素のうちc個をランダムに選択してもよい。実施形態では、システムは、システムにより選択された組み合わせが他のワーカーノードにより選択された組み合わせと一致するか否かを検証するために、様々なワーカーノードにより選択された量を推定するために使用できる更なる認識を欠いているので、システムは、c個の要素の偏りのない組み合わせのみを引き出すことができる点に留意すべきである。実施形態では、実行トランザクションは、作業項目を含む。実施形態では、作業項目は、同じ組み合わせを有するワークチケットの要求を選択してサブミットしたグループメンバーシップのワーカーノードにより実行可能なコンピュータプログラムの少なくとも一部である。実行トランザクションがブロックチェーンネットワークにブロードキャストされると、ワーカーノードはプログラムを実行することを試みてもよい。
【０１１７】
システムは、所定の時間に、プログラムが実行されたか否か916を決定してもよい。実施形態では、プログラムが実行されている場合、マネージャノードは、プロトコルロールバックトランザクションにより担保されているデジタル資産を請求する918。プログラムが所定の時間までに実行されなかった場合、システムは、ワーカーチケットにより担保されているデジタル資産を収集してもよく920、ワーカーノードのそれぞれは、プロトコルロールバックトランザクションにより担保されているデジタル資産の一部をロールバック機構として請求してもよい。プロトコルロールバックトランザクションが存在しないような実施形態では、プログラムが実行されなかった場合、ワーカーノードのそれぞれが実行トランザクションにより担保されているデジタル資産の一部を請求することを生じてもよい。
【０１１８】
図１０は、本開示の少なくとも1つの実施形態を実施するために使用できる計算デバイス1000の簡略化したブロック図の例である。様々な実施形態では、計算デバイス1000は、上記に示して説明した実施システムのいずれかを実装するために使用されてもよい。例えば、計算デバイス1000は、データサーバ、ウェブサーバ、ポータブル計算デバイス、パーソナルコンピュータ又はいずれかの電子計算デバイスとして使用するために構成できる。図１０に示すように、計算デバイス1000は、1つ以上のプロセッサ1002を含んでもよく、実施形態では、1つ以上のプロセッサ1002は、バスサブシステム1004を介して複数の周辺サブシステムと通信するように構成されて動作可能に結合される。いくつかの実施形態では、これらの周辺サブシステムは、メモリサブシステム1008及びファイル/ディスク記憶サブシステム1010を含むメモリサブシステム1008と、1つ以上のユーザインタフェース入力デバイス1012と、1つ以上のユーザインタフェース出力デバイス1014と、ネットワークインタフェースサブシステム1016とを含む。このような記憶サブシステム1006は、情報の一時的又は長期的な記憶のために使用されてもよい。
【０１１９】
いくつかの実施形態では、バスサブシステム1004は、計算デバイス1000の様々な構成要素及びサブシステムが、意図したように相互に通信することを可能にする機構を提供してもよい。バスサブシステム1004は、単一のバスとして概略的に示されているが、バスサブシステムの代替実施形態は、複数のバスを利用してもよい。いくつかの実施形態では、ネットワークインタフェースサブシステム1016は、他の計算デバイス及びネットワークへのインタフェースを提供する。いくつかの実施形態では、ネットワークインタフェースサブシステム1016は、他のシステムからデータを受信し、計算デバイス2600から他のシステムにデータを送信するためのインタフェースとして機能する。いくつかの実施形態では、バスサブシステム1004は、詳細、検索項目等のようなデータを通信するために利用される。
【０１２０】
いくつかの実施形態では、ユーザインタフェース入力デバイス1012は、情報を計算デバイス1000に入力するための全ての可能な種類のデバイス及び機構を含む。いくつかの実施形態では、1つ以上のユーザインタフェース出力デバイス1014は、計算デバイス1000から情報を出力するための全ての可能な種類のデバイス及び機構を含む。1つ以上のユーザインタフェース出力デバイス1014は、例えば、ユーザ相互作用が適切になり得るときに、ここに記載のプロセス及びその変形を実行するアプリケーションとのユーザ相互作用を実現するように、ユーザインタフェースを提示するために使用できる。
【０１２１】
いくつかの実施形態では、記憶サブシステム1006は、本開示の少なくとも1つの実施形態の機能を提供する基本的なプログラミング及びデータ構成を記憶するためのコンピュータ読み取り可能記憶媒体を提供する。いくつかの実施形態では、アプリケーション(プログラム、コードモジュール、命令)は、1つ以上のプロセッサにより実行されたとき、本開示の1つ以上の実施形態の機能を提供し、実施形態では、記憶サブシステム1006に記憶される。これらのアプリケーションモジュール又は命令は、1つ以上のプロセッサ1002により実行できる。様々な実施形態では、記憶サブシステム1006は、本開示に従って使用されるデータを記憶するためのリポジトリを更に提供する。いくつかの実施形態では、記憶サブシステムは、メモリサブシステム及びファイル/ディスク記憶サブシステム1010を含む。
【０１２２】
実施形態では、メモリサブシステム1008は、命令及びプログラム実行中のデータの記憶のためのメインランダムアクセスメモリ(RAM)1018及び/又は固定の命令が記憶できる読み取り専用メモリ(ROM)1018のような複数のメモリを含む。いくつかの実施形態では、ファイル/ディスク記憶サブシステム1010は、プログラム及びデータファイルのための非一時的で永続的な(不揮発性)ストレージを提供し、ハードディスクドライブ、関連する取り外し可能媒体を有するフロッピーディスクドライブ、コンパクトディスク読み取り専用メモリ(CD-ROM)ドライブ光学ドライブ、取り外し可能媒体カートリッジ又は他の同様の記憶媒体を含むことができる。
【０１２３】
いくつかの実施形態では、計算デバイス1000は、少なくとも1つのローカルクロック1024を含む。いくつかの実施形態では、ローカルクロック1024は、特定の開始日から発生したティックの数を表すカウンタであり、いくつかの実施形態では、計算デバイス1000内に一体的に配置される。様々な実施形態では、ローカルクロック1024は、特定のクロックパルスにおいて、計算デバイス1000のプロセッサ及びそれに含まれるサブシステム内のデータ転送を同期させるために使用され、計算デバイス1000とデータセンタ内の他のシステムとの間の同期動作を調整するために使用できる。他の実施形態では、ローカルクロックは、プログラム可能なインターバルタイマである。
【０１２４】
コンピュータ及びネットワークの絶えず変化する性質のため、図１０に示す計算デバイス1000の説明は、デバイスの好ましい実施形態を説明する目的のための具体的な例としてのみ意図される。図１０に示すシステムよりも多くの構成要素又は少ない構成要素を有する他の多くの構成も可能である。
【０１２５】
したがって、明細書及び図面は、限定的な意味ではなく例示的な意味に考えられるべきである。しかし、特許請求の範囲に記載された本発明の範囲から逸脱することなく、様々な修正及び変更が行われてもよいことは明らかである。同様に、他のバリエーションも本開示の範囲内である。したがって、開示の技術は、様々な修正及び代替の構成を受けることができ、その特定の例示の実施形態が図面に示され、上記で詳細に説明されている。しかし、本発明を開示の特定の形式に限定する意図は存在せず、逆に、添付の特許請求の範囲に定義されているように、本発明の範囲内に入るすべての変更、代替構成及び均等物をカバーすることを意図することが理解されるべきである。
【０１２６】
「セット」(例えば、「項目のセット」)又は「サブセット」という用語の使用は、別段の注記がない限り或いは文脈によって矛盾がない限り、1つ以上のメンバーを含む空でない集合として解釈されるべきである。さらに、別段の注記がない限り或いは文脈によって矛盾がない限り、対応するセットの「サブセット」という用語は、必ずしも対応するセットの適切なサブセットを示すとは限らず、サブセット及び対応するセットは等しくてもよい。
【０１２７】
「A、B及びCのうち少なくとも1つ」、又は「A、B及びCのうち少なくとも1つ」という形式の結合語は、特に別段の記載がない限り或いは文脈によって明確に矛盾がない限り、或る項目、用語等がA若しくはB若しくはC、又はA、B及びCのセットのうちいずれかの空でないサブセットでもよいことを示すために一般的に使用されるように、文脈によって理解される。例えば、3つのメンバーを有するセットの例示的な例では、「A、B及びCのうち少なくとも1つ」及び「A、B及びCのうち少なくとも1つ」という結合語は、以下のセット、すなわち、{A}、{B}、{C}、{A,B}、{A,C}、{B,C}、{A,B,C}のいずれかを示す。したがって、このような結合語は、特定の実施形態がAのうち少なくとも1つ、Bのうち少なくとも1つ及びCのうち少なくとも1つがそれぞれ存在することを要求することを暗示することを一般的に意図する。さらに、別段の記載がない限り或いは文脈から明白な場合を除き、「に基づく」という語句は、「少なくとも部分的に基づく」ことを意味し、「のみに基づく」ことを意味しない。
【０１２８】
記載されたプロセスの動作は、他に指示がない限り或いは文脈によって明らかに矛盾しない限り、いずれか適切な順序で実行できる。記載のプロセス(又はその変形及び/又は組み合わせ)は、実行可能な命令で構成された1つ以上のコンピュータシステムの制御下で実行でき、ハードウェア又はこれらの組み合わせにより、1つ以上のプロセッサ上で併せて実行するコード(例えば、実行可能命令、1つ以上のコンピュータプログラム又は1つ以上のアプリケーション)として実装できる。いくつかの実施形態では、コードは、例えば、1つ以上のプロセッサにより実行可能な複数の命令を含むコンピュータプログラムの形式で、コンピュータ読み取り可能記憶媒体に記憶できる。いくつかの実施形態では、コンピュータ読み取り可能記憶媒体は非一時的である。
【０１２９】
提供されるあらゆる例又は例示的な言語(例えば、「のような」)の使用は、本発明の実施形態をより良く例示することのみを意図したものであり、他に特許請求の範囲に記載されない限り、本発明の範囲を制限するものではない。明細書中の用語は、特許請求の範囲に記載されていない如何なる要素も本発明の実施に不可欠であることを示すものとして解釈されるべきではない。
【０１３０】
本発明を実施するために発明者に知られている最良の形態を含む、本開示の実施形態が記載されている。これらの実施形態のバリエーションは、上記の説明を読むことにより当業者に明らかになる。発明者は、当業者がこのようなバリエーションを適宜使用することを期待しており、発明者は、本開示の実施形態が具体的に記載された以外の方法で実施されることを意図している。したがって、本開示の範囲は、適用可能な法律により許容されるように、ここに添付された特許請求の範囲に記載の対象物の全ての変更及び等価物を含む。さらに、全ての可能なバリエーションにおける上記の要素の如何なる組み合わせも、別段の指示がない限り或いは文脈によって明らかに矛盾しない限り、本開示の範囲に包含される。
【０１３１】
引用された刊行物、特許出願及び特許を含む全ての参考文献は、各参考文献が個別に且つ具体的に参照により援用されて全体として記載されているのと同じ程度に、参照によりここに組み込まれる。
【０１３２】
上記の実施形態は、本発明を限定するものではなく例示するものであり、当業者は、添付の特許請求の範囲により定義される本発明の範囲から逸脱することなく、多くの代替実施形態を設計できる点に留意すべきである。特定の手段が相互に異なる従属項に記載されているという単なる事実は、これらの手段の組み合わせが有利に利用できないことを示すものではない。
【図１】
2021530173.tif 000023
【図２】
2021530173.tif 000024
【図３】
2021530173.tif 000025
【図４】
2021530173.tif 000026
【図５】
2021530173.tif 000027
【図６】
2021530173.tif 000028
【図７】
2021530173.tif 000029
【図８】
2021530173.tif 000030
【図９】
2021530173.tif 000031
【図１０】
2021530173.tif 000032
【国際調査報告】
2021530173.tif 000033
2021530173.tif 000034
2021530173.tif 000035