(57)【要約】アセット混合プロトコルは、所与の参加者コンピュータシステムが異なったアセット混合トランザクションに含まれる入力及び出力アドレスを有し得るように作られたアセット混合トランザクションの組を用いて参加者コンピュータシステムのグループが彼らのアセットを混合することを可能にする。集積木から導出された数量の使用は、プロトコルが、ブロックチェーン上の全てのアセット混合トランザクションのブロードキャストに対して参加者コンピュータシステムによって行われたデポジットの償還をセキュアに条件付けることを可能にする。参加者コンピュータシステムからアセットを盗むことができる十分な情報を中央調整者又はディーラーが処理することから保護するセーフガードが提供される。【特許請求の範囲】
【請求項１】
出力シャッフルプロセスにおいて参加者コンピュータシステムの組を識別する圧縮情報を含むデータ構造を生成することと、
シャッフルされた出力アドレスの組を前記参加者コンピュータシステムの組から取得することと、
前記参加者コンピュータシステムの組に対応する寄与記録の組がブロックチェーンへコミットされていると決定することと、
前記シャッフルされた出力アドレスの組及び前記データ構造に少なくとも部分的に基づいて複数のトランザクションを生成することと、
前記複数のトランザクションを前記ブロックチェーンへサブミットすることと
を有する、コンピュータにより実施される方法。
【請求項２】
個々の参加者コンピュータシステムの組に関連する個別トランザクションが失敗したと第１タイムアウト後に決定することと、
個別トランザクションが失敗したとの決定の結果として、前記個々の参加者コンピュータシステムの組が前記寄与記録の組からの補償を請求すること又は前記個々の参加者コンピュータシステムの寄与記録を再請求することを可能にする暗号情報を前記個々の参加者コンピュータシステムの組へ供給することと
を更に有する、請求項１に記載のコンピュータにより実施される方法。
【請求項３】
寄与記録の各組は、ロッキングスクリプトを含み、
前記ロッキングスクリプトは、トランザクション出力が、前記シャッフルされた出力アドレスの組に基づいて個々の参加者コンピュータシステムによって請求されることを可能にする、
請求項２に記載のコンピュータにより実施される方法。
【請求項４】
前記ロッキングスクリプトは、入力が前記暗号情報を用いて再請求されることを可能にする、
請求項３に記載のコンピュータにより実施される方法。
【請求項５】
前記ロッキングスクリプトは、前記第１タイムアウトよりも長い第２タイムアウト後に入力が再請求されることを可能にする、
請求項４に記載のコンピュータにより実施される方法。
【請求項６】
前記ロッキングスクリプトは、OP_CHECKSEQUENCEVERIFY演算子を含む、
請求項５に記載のコンピュータにより実施される方法。
【請求項７】
前記シャッフルされた出力アドレスの組は、シャッフルされた出力アドレスの組を前記参加者コンピュータシステムの組の中の各参加者コンピュータシステムへルーティングされるようにすることによって、取得される、
請求項６に記載のコンピュータにより実施される方法。
【請求項８】
前記寄与記録の組の中の各寄与記録は、当該コンピュータにより実施される方法を促進するディーラーへ支払われるトランザクション手数料を含む、
請求項７に記載のコンピュータにより実施される方法。
【請求項９】
前記データ構造は、集積木であり、該集積木のリーフノードは、前記参加者コンピュータシステムの組を表し、参加者コンピュータシステムは、前記複数のトランザクションにおける入力アドレス及び出力アドレスを有する、
請求項８に記載のコンピュータにより実施される方法。
【請求項１０】
個別トランザクションにおける参加者コンピュータシステムは、前記集積木の中間ノードの下の前記リーフノードに対応する、
請求項９に記載のコンピュータにより実施される方法。
【請求項１１】
各参加者コンピュータシステムは、前記集積木の各リーフノードに関連する値のハッシュを供給する、
請求項１０に記載のコンピュータにより実施される方法。
【請求項１２】
前記トランザクションは、アセット混合トランザクションである、
請求項１１に記載のコンピュータにより実施される方法。
【請求項１３】
各参加者コンピュータシステムは、１つ以上のプロセッサと、該１つ以上のプロセッサによって実行される結果として、暗号通貨ウォレットアプリケーションを実施する命令を記憶しているメモリとを有するコンピュータシステムである、
請求項１２に記載のコンピュータにより実施される方法。
【請求項１４】
システムであって、
プロセッサと、
前記プロセッサによる実行の結果として、当該システムに、請求項１３に記載のコンピュータにより実施される方法を実行させる実行可能命令を含むメモリと
を有するシステム。
【請求項１５】
コンピュータシステムのプロセッサによって実行される結果として、前記コンピュータシステムに、請求項１４に記載のコンピュータにより実施される方法を少なくとも実行させる実行可能命令が記憶されている非一時的なコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、ブロックチェーン上に記録された複数のノンアトミック操作の使用を通じたアトミック操作の生成及び実行に概して関係がある。本開示は、複数の参加者からの寄与を含む合成アトミック操作の実行に特に適するが限られない。一般に、本開示は、アトミック操作の失敗時に如何なる個々の寄与も返されることを個々の参加者に保証するために集積木を使用する。
【背景技術】
【０００２】
本文書中、語「ブロックチェーン」は、いくつかのタイプの電子的な、コンピュータに基づく分散台帳（distributed  ledgers）のいずれかを指す。それらは、合意に基づくブロックチェーン及びトランザクションチェーン技術、許可（permissioned）及び無許可（un-permissioned）台帳、共有台帳、並びにこれらの変形を含む。ブロックチェーン技術の最も広く知られた応用は、他のブロックチェーン実施が提案及び開発されているとはいえ、ビットコイン台帳である。ビットコインの例が、便宜上、説明のために本開示で言及され得るが、本開示は、ビットコインブロックチェーンとともに使用することに限られず、代替のブロックチェーン実施及びプロトコルが本開示の適用範囲内にあることが留意されるべきである。例えば、本開示は、どんな制約がトランザクション内で符号化され得るかに関してビットコインに類似した制限を有している他のブロックチェーン実施において有用であることができる。
【０００３】
ブロックチェーンは、トランザクション及び他の情報から成るブロックで構成された、コンピュータに基づく非中央集権型の分散システムとして実装されるピア・ツー・ピアの電子台帳である。例えば、ビットコインによれば、各トランザクションは、ブロックチェーンシステム内の参加者間のデジタルアセットの制御の移動を符号化するデータ構造であり、少なくとも１つの入力及び少なくとも１つの出力を含む。いくつかの実施形態で、「デジタルアセット」（digital  asset）は、使用権に関連するバイナリデータを指す。いくつかの実施で、デジタルアセットの制御を移すことは、第１エンティティから第２エンティティへデジタルアセットの少なくとも一部を関連付けし直すことによって実行され得る。ブロックチェーンにその始まり以来書き込まれてきた全てのトランザクションの永久的且つ不変な記録を構成するようブロックどうしが連鎖するように、各ブロックは前のブロックのハッシュを含む。トランザクションは、それらの入力及び出力に埋め込まれたスクリプトとして知られている小さいプログラムを含む。スクリプトは、如何にして誰によってトランザクションの出力がアクセスされ得るかを特定する。ビットコインプラットフォームで、それらのスクリプトは、スタックに基づくスクリプト言語を用いて書かれている。
【０００４】
トランザクションがブロックチェーンに書き込まれるために、それは“妥当性確認”（validated）される。ネットワークノード（マイナー）は、各トランザクションが妥当であることを確かにする作業を実行し、妥当でないトランザクションはネットワークから拒絶される。ノードは、他のノードとは異なった妥当性の標準を有することができる。ブロックチェーンにおける妥当性は合意に基づく（consensus-based）ので、トランザクションが妥当であると大部分のノードが同意する場合に、トランザクションは妥当と見なされる。ノードにインストールされているソフトウェアクライアントは、部分的にＵＴＸＯロッキング（locking）及びアンロッキング（unlocking）スクリプトを実行することによって、未使用トランザクション（unspent  transaction，ＵＴＸＯ）を参照するトランザクションに対してこの妥当性確認作業を実行する。ロッキング及びアンロッキングスクリプトの実行が真（ＴＲＵＥ）になり、他の妥当性確認条件が、適用可能である場合に、満足される場合には、トランザクションはノードによって妥当性を確認される。妥当性を確認されたトランザクションは、他のネットワークノードへ伝えられ、そうすると、マイナーノードは、トランザクションをブロックチェーンに含めることを選択することができる。このようにして、トランザクションがブロックチェーンに書き込まれるために、それは、ｉ）トランザクションを受け取る第１ノードによって妥当性確認をされなければならず、トランザクションが妥当性を確認される場合に、ノードは、それをネットワーク内の他のノードへ中継し、そして、トランザクションは、ｉｉ）マイナーによって構築された新しいブロックに加えられ、ｉｉ）マイニング、すなわち、過去のトランザクションの公開台帳に付加、されなければならない。トランザクションを実質的に不可逆にするよう十分な数のブロックがブロックチェーンに付加されている場合に、トランザクションは承認されていると見なされる。
【０００５】
ブロックチェーン技術は、暗号通貨実施の使用のために最も広く知られているが、デジタル起業家は、新しいシステムを実装するために、ビットコインが基づく暗号化によるセキュリティシステムと、ブロックチェーン上に記憶され得るデータとの両方の使用を探求し始めている。暗号資産の分野に制限されない自動化タスク及びプロセスのためにブロックチェーンが使用される場合に、それは大いに有利である。そのような解決法は、ブロックチェーンの利益（例えば、イベントの永久的な耐タンパー性の記録、分散処理など）を活用しながら、それらの用途を広げることができる。
【０００６】
ブロックチェーントランザクション出力は、ロッキングスクリプトと、ビットコインなどのデジタルアセットの所有権に関する情報とを含む。ロッキングスクリプトは、解除条件（encumbrance）とも呼ばれることがあり、出力をアンロックするために満足される必要がある条件を指定することによってデジタルアセットを“ロック”する。例えば、ロッキングスクリプトは、関連するデジタルアセットをアンロックするよう特定のデータがアンロッキングスクリプトにおいて供給されることを求め得る。ロッキングスクリプトは、ビットコインでは「scriptPubKey」としても知られている。デジタルアセットをアンロックするためにデータを供給することをパーティに求める技術は、ロッキングスクリプト内にデータのハッシュを埋め込むことを含む。しかし、これは、ロッキングスクリプトが生成される時点でデータが未決定である（例えば、知られておらず固定されていない）場合に問題を提示する。
【発明の概要】
【０００７】
よって、相異なるノンアトミックトランザクションの結合を用いてアトミックトランザクションを実行する方法を提供することによって、ブロックチェーン技術を改善する方法及びシステムを提供することが望ましい。そのような、改善された解決法は、これより発明されている。よって、本開示に従って、添付の特許請求の範囲で定義されている方法が提供される。
【０００８】
よって、出力シャッフルプロセスにおいて参加者コンピュータシステムの組を暗号的に識別するデータ構造を生成することと、シャッフルされた出力アドレスの組を参加者コンピュータシステムの組から取得することと、参加者コンピュータシステムの組に対応する寄与記録の組（例えば、デポジットトランザクションの組）がブロックチェーンへコミットされていると決定することと、シャッフルされた出力アドレスの組及びデータ構造に少なくとも部分的に基づいて複数のトランザクションを生成することと、複数のトランザクションを前記ブロックチェーンへサブミットすることとを有する、コンピュータにより実施される方法を提供することが望ましい。
【０００９】
望ましくは、請求されているコンピュータにより実施される方法は、個々の参加者コンピュータシステムに関連する個別アセット混合トランザクションが失敗したと第１タイムアウト後に決定することと、個別アセット混合トランザクションが失敗したとの決定の結果として、個々の参加者コンピュータシステムが寄与記録の組からの補償を請求すること又は個々の参加者コンピュータシステムの寄与記録を再請求することを可能にする暗号情報を個々の参加者コンピュータシステムの組へ供給することとを更に有する実施形態であってよい。
【００１０】
望ましくは、請求されているコンピュータにより実施される方法は、寄与記録の各組がロッキングスクリプトを含み、ロッキングスクリプトにより、トランザクション出力が、シャッフルされた出力アドレスの組に基づいて個々の参加者コンピュータシステムによって請求されることが可能になる実施形態であってよい。
【００１１】
望ましくは、請求されているコンピュータにより実施される方法は、ロッキングスクリプトにより、入力が暗号情報を用いて再請求されることが可能になる実施形態であってよい。
【００１２】
望ましくは、請求されているコンピュータにより実施される方法は、ロッキングスクリプトにより、第１タイムアウトよりも長い第２タイムアウト後に入力が再請求されることを請求されることが可能にある実施形態であってよい。
【００１３】
望ましくは、請求されているコンピュータにより実施される方法は、ロッキングスクリプトがOP_CHECKSEQUENCEVERIFY演算子を含む実施形態であってよい。
【００１４】
望ましくは、請求されているコンピュータにより実施される方法は、シャッフルされた出力アドレスの組が、シャッフルされた出力アドレスの組を参加者コンピュータシステムの組の中の各参加者コンピュータシステムへルーティングされるようにすることによって、取得される実施形態であってよい。
【００１５】
望ましくは、請求されているコンピュータにより実施される方法は、寄与記録の組の中の各寄与記録が、コンピュータにより実施される方法を促進するディーラーへ支払われるトランザクション手数料を含む実施形態であってよい。
【００１６】
望ましくは、請求されているコンピュータにより実施される方法は、データ構造が集積木であり、集積木のリーフノードが参加者コンピュータシステムの組を表す実施形態であってよい。
【００１７】
望ましくは、請求されているコンピュータにより実施される方法は、個別アセット混合トランザクションにおける参加者コンピュータシステムが、集積木の中間ノードの下のリーフノードに対応する実施形態であってよい。
【００１８】
望ましくは、請求されているコンピュータにより実施される方法は、各参加者コンピュータシステムが、集積木の各リーフノードに関連する値のハッシュを供給する実施形態であってよい。
【００１９】
望ましくは、請求されているコンピュータにより実施される方法は、アセット混合トランザクションが、アセット混合トランザクションである実施形態であってよい。
【００２０】
望ましくは、請求されているコンピュータにより実施される方法は、各参加者コンピュータシステムが、１つ以上のプロセッサと、１つ以上のプロセッサによって実行される結果として、暗号通貨ウォレットアプリケーションを実施する命令を記憶しているメモリとを有するコンピュータシステムである実施形態であってよい。
【００２１】
また、プロセッサと、プロセッサによる実行の結果として、システムに、せいきゅうｓあれている方法のいずれかを実行させる実行可能命令を含むメモリとを有するシステムを提供することも望ましい。
【００２２】
コンピュータシステムのプロセッサによって実行される結果として、コンピュータシステムに、請求されている方法のいずれかを少なくとも実行させる実行可能命令が記憶されている非一時的なコンピュータ可読記憶媒体を提供することも望ましい。
【００２３】
本開示は、検証方法／システムとして、及び／又はブロックチェーンを介したデジタルアセットの交換又は転送を制御する制御方法／システムとして記載され得る。いくつかの実施形態で、デジタルアセットは、暗号通貨の部分又はトークンである。以下で説明されるように、本開示はまた、ブロックチェーンネットワーク又はプラットフォームを介して操作を実行する新しい、改善されたかつ有利な方法のためのセキュアな方法／システムとしても記載され得る。
【００２４】
本開示のこれら及び他の態様は、本明細書で記載される実施形態から明らかであり、それらを参照して説明される。本開示の実施形態は、これより、ほんの一例として、添付の図面を参照して説明される。
【図面の簡単な説明】
【００２５】
【図１】実施形態において、アセット混合を行うシステムの例を表す。
【図２】実施形態において、９つの要素の組についての集積木の例を表す。
【図３】実施形態において、各リーフノードが関連する要素ｅｉ（ｉ＝１，・・・，４）を有している集積木の例を表す。
【図４】実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分として行われる暗号化操作の例を表す。
【図５】実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分として行われる暗号解除操作の例を表す。
【図６】実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分として行われる出力アドレスの並べ替えの例を表す。
【図７】実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分としてデポジットに対して参加者によって生成されるロッキングスクリプトの例を表す。
【図８】実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションにおいて４人の参加者によって生成、署名、及びブロードキャストされた寄与記録の例を表す。
【図９】実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションにおいて参加者によって生成及び署名された２つのＣｏｉｎＪｏｉｎトランザクションの例を表す。
【図１０】実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによる実行の結果として、マルチＣｏｉｎＪｏｉｎトランザクションを実行するプロセスの例を表す。
【図１１】実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによる実行の結果として、キー共有を実行し、マルチＣｏｉｎＪｏｉｎトランザクションでの使用のために集積木を構築するプロセスの例を表す。
【図１２】実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによる実行の結果として、出力アドレスを再配置し、デポジットを生成し、マルチＣｏｉｎＪｏｉｎトランザクションのためのＣｏｉｎＪｏｉｎトランザクションを生成するプロセスの例を表す。
【図１３】実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによる実行の結果として、マルチＣｏｉｎＪｏｉｎトランザクションのためにリターン及び補償を処理するプロセスの例を表す。
【図１４】様々な実施形態が実施され得るコンピュータシステムを表す。
【発明を実施するための形態】
【００２６】
本文書は、ブロックチェーンに記録されたノンアトミックトランザクションの結合を用いてアトミックトランザクションを実行するようセキュリティ方法を実行するシステムについて記載する。実施形態において、システムは、ディーラーコンピュータシステムと、参加者コンピュータシステムの組とを識別する。参加者コンピュータシステムと協力して、ディーラーは、参加者コンピュータシステムへ供給される各参加者に特有の暗号情報を生成するために使用される集積木（accumulation  tree）を生成する。各参加者コンピュータシステムは、リソースをアトミック操作へコミットするトランザクションを生成する。ここで、トランザクションは、暗号情報に少なくとも部分的に基づいて、ロッキングスクリプトにより保護される。様々な例で、リソースは、暗号キー、コード、暗号通貨の数量、未使用トランザクション出力であってよい。実施形態において、ロッキングスクリプトは、何らかの理由によりアトミック操作が失敗する場合に、タイムアウト後に、トランザクション入力の償還を提供する。ディーラーコンピュータシステムは、全ての参加者がアトミック操作に対して彼らのリソースを適切に満たしているかどうかを判定し、そうである場合に、複数のトランザクションを生成しブロックチェーンにコミットする。ブロックチェーンは、凝集効果において、アトミック操作を実行する。全ての参加者コンピュータシステムがアトミック操作を完了するために必要なリソースをコミットしているわけではない場合に、ディーラーコンピュータシステムは、参加者コンピュータシステムが彼らのコミットされたリソースを回復することを可能にする集積木に関連した特定の情報を供給する。このようにして、参加者は、アトミック操作が完了されること、又は活動にコミットされた如何なるリソースも返されることのいずれかの暗号保証（cryptographic  assurance）を得ることができる。
【００２７】
いくつかの例で、システムは、単一のアセット混合操作がブロックチェーン上で複数のトランザクションに及ぶことを可能にすることによって、アセット混合操作の有効性を改善するために使用されてよい。アセット混合トランザクションの場合に、あて先アドレスからの個人情報の除外は、必ずしも、トランザクションにおける参加者の身元を不明りょうにしない。意欲的な個人は、特定の移動及びあて先アドレスに個人を関連付けることが可能な解析を実行するために、外部データセットとともに、公に利用可能な台帳内のトランザクション情報を利用することがある。本明細書で記載される実施形態は、単一のアセット混合操作を複数のコンポーネントトランザクションに分割することによって、この懸案事項を軽減する。本明細書で記載されるアセット混合システムは、大規模コンピューティングプール、投票システム、及び暗号通貨トランザクションなどの代替可能資産のプールにおいて交換が行われる可能性がある様々な問題にも適用可能である。
【００２８】
例えば、暗号通貨資産は、コインミキシングと呼ばれるアセット混合プロセスを用いて混合され得る。例えば、ビットコインのコインミキシング解決法は、ｎ人のユーザのビットコイン入力をプールし、次いで、プールされたビットコインを、ユーザによって所有されているｎ個のアドレスの代替の組へ出力することによって、アドレス間のリンクを隠す。コインミキシングのＣｏｉｎＪｏｉｎ実施は、１つの単一ビットコイントランザクションの使用を通じてコインミキシングプロセスを実行することによってプロセスを簡単にして、ＣｏｉｎＪｏｉｎトランザクションにおいてユーザの入力をユーザの出力と正確にリンクする確率を１／ｎまで低下させる。ＣｏｉｎＳｈｕｆｆｌｅなどのミキシングサービスは、ユーザが参加しているトランザクションへコインを送るＣｏｉｎＪｏｉｎトランザクションを介してビットコインユーザの身元を不明りょうにして、ブロックチェーンを通る個人のコインの流れを追跡することを難しくする解決法を提供する。トランザクションに関わる出力をシャッフルするプロセスは、トランザクションの入力及び出力の間に不鮮明な状態を作り出す。通常、ｎ人の参加者（各参加者はトランザクションにおいて１つの入力及び１つの出力を有している）を含むＣｏｉｎＪｏｉｎトランザクションの場合に、入力を出力と正確にリンクする（従って、参加者のコインフローを正確に推測する）確率は、１／ｎである。
【００２９】
１つの実施において、システムは、複数の参加者から未使用暗号通貨出力をプールし、出力アドレスの順序を再配置し、それによって、第三者が追跡することがより困難であるＣｏｉｎＪｏｉｎトランザクションからの新しい出力を各参加者に供給する。実施形態において、参加者のグループは、出力アドレスの組をシステムへ供給する。システムは、出力アドレスの順序をランダム化し、並べ替えられた出力アドレスを使用して、多数の独立したＣｏｉｎＪｏｉｎトランザクションを生成する。トランザクションは、各参加者が、２つの独特のＣｏｉｎＪｏｉｎトランザクションに含まれている関連した入力及び出力を有するように、配置される。
【００３０】
一般に、単一のＣｏｉｎＪｏｉｎトランザクションにおいて、個々のユーザは１つ（以上）の入力及び１つ（以上）の出力を有することになる。更に、ビットコイントランザクションの場合に、トランザクションサイズは１Ｍバイトに制限されており、これは、所与のトランザクションに含まれ得る入力及び出力の総数を制約し、従って、トランザクションに関連することができる参加者の数を制限する。
【００３１】
本明細書で記載される様々な実例で、システムは、トランザクションへの参加者が２つの異なったトランザクション（例えば、ブロックチェーンに書き込まれている２つの異なったトランザクション記録）に含まれる彼らの入力及び彼らの出力を有し得るように、複数の独立したＣｏｉｎＪｏｉｎトランザクションを構築する。システムは、参加者が個々のリーフノードによって表現される集積木をディーラーコンピュータシステムに生成させることによって、これを達成することができる。参加者によって使用されるロッキングスクリプトは、トランザクションが閾時間量の後に成功裏に完了していない場合に、個々の参加者が、ディーラーコンピュータシステムの助けを借りて、又はいくつかの例では、助けなしで、失敗したトランザクションに寄与した如何なるアセットも再請求することができるトランザクションのマルチフェーズ実行を強行する。各参加者は、独立した全てのＣｏｉｎＪｏｉｎトランザクションが公開台帳に含まれる場合にその参加者が請求することができる、以前に同意した、及びＣｏｉｎＪｏｉｎトランザクションで混合された量と同様のビットコインの量をデポジットする。プロトコルは、ＣｏｉｎＪｏｉｎトランザクションの１つが、そのトランザクションにおいて彼らの入力を加えると期待された参加者によって署名されない（例えば、トランザクションに割り当てられているサブグループ内の参加者に悪意がある）場合に、残りのトランザクションの１つに入力を加え署名した参加者が正当に補償されることを確かにする安全機構を備える。このプロトコルは、ＣｏｉｎＪｏｉｎトランザクションのリンク不能性（unlinkability）である顕著な特徴を提供するので、ＣｏｉｎＳｈｕｆｆｌｅなどの単一ＣｏｉｎＪｏｉｎトランザクションに基づく解決法と比べて許可可能な参加者の数を増やす。これは、ネットワーク上でＣｏｉｎＪｏｉｎトランザクションを署名及び送信する前に参加者によって行われたデポジットをロック及びアンロックするために参加者によって供給されたデータを用いて構築された静的な集積木（局所的及び大域的ダイジェスト）から導出された数量を用いて達成される。
【００３２】
図１は、実施形態において、コインミキシングを実行するシステム１００の例を表す。コインミキシングは、ユーザのグループが彼らのビットコインを一緒にプールし、それから、彼らのビットコインを代替のビットコインアドレスに分配してもらいたいと望むシステムである。そのような代替のアドレスは、ユーザの初期の組によって所有されてもされなくてもよい。システムは、外部の攻撃者に対する保護を提供する。これは、攻撃者が、一般的に、入力及び出力アドレスを関連付けることができないからである。例えば、ｎ個の入力及びｎ個の出力がある場合に、入力を出力アドレスと正確に結びつける確率は、約１／ｎである。これは、一般的に、全ての参加者が混合プールにおいて同量の暗号通貨を入力及び出力する限りは当てはまる。
【００３３】
図１に表される実施形態では、第１ユーザ１０２は第１クライアントコンピュータシステム１０４を操作し、第２ユーザ１０６は第２クライアントコンピュータシステム１０８を操作し、第３ユーザ１１０は第３クライアントコンピュータシステム１１２を操作する。各クライアントコンピュータシステムは、パーソナルコンピュータ、ラップトップコンピュータ、携帯型デバイス、ネットワーク家電、仮想コンピュータシステム、コンピュータサーバ、ＰＯＳ（point-of-sale）端末、又は他のコンピューティングデバイスであってよい。実施形態において、各コンピューティングデバイスは、クライアントデバイス上でメモリに記憶されている命令から成るクライアントアプリケーションをホストする。命令は、クライアントコンピュータシステムによる実行の結果として、クライアントアプリケーションの機能を実施する。クライアントアプリケーションは、ビットコイン台帳又は他の暗号通貨ブロックチェーンなどの、分散型記憶ネットワークに記憶されているブロックチェーン台帳とインターフェース接続する。いくつかの例で、各クライアントコンピュータシステムは、トランザクション記録を送信及び受信すること、又はコンピュータネットワークによって、ブロックチェーンとインターフェース接続する。コンピュータネットワークは、Ｅｔｈｅｒｎｅｔ（登録商標）若しくは光ファイバネットワークなどの有線ネットワーク、又はＷｉ−Ｆｉ若しくはセルラーネットワークなどの無線ネットワークを含んでよい。
【００３４】
実施形態において、３人のユーザの夫々は、ブロックチェーン１１４に記憶されるＣｏｉｎＪｏｉｎトランザクションへ入力及び出力を加える。ユーザの入力の夫々及びユーザの出力の夫々は、一致した暗号通貨の価値を有し、出力の順序付けは、ブロックチェーンを調べる攻撃者が、所与の出力がどのユーザからそもそも得られたかを知り得ないように、ランダムに配置される。
【００３５】
この解決法のいくつかの実施は、特定の望ましくない特性を示し得る協調サービスプロバイダに依存する：
●協調サービスプロバイダが、ユーザによって供給されたビットコインアドレスへビットコイン入力を転送しないことによって、ビットコインを盗む可能性があるリスクが存在する。  
●協調サービスプロバイダは、入力ファンド／アドレスと出力アドレスとの間のつながりに関する知識を持つことがある。サービスプロバイダがそうすることを選択するならば、サービスプロバイダは、この情報を意図的に又は誤って公開する可能性がある。  
●一般に、協調サービスは、コインミキシングサービスの利用のために手数料を課す。
【００３６】
本明細書で記載される様々な実施形態は、これら及び他の欠点を補償する。例えば、ＣｏｉｎＪｏｉｎは、ビットコインアドレス間の参加者のファンドの移動において、１つの共有されたビットコイントランザクションを使用する。各ユーザは、彼らのビットコインをビットコイントランザクションへ入力として加え、各ユーザは、彼らのあて先出力ビットコインアドレスをトランザクションへ加える。単一の共有されたトランザクションを使用することによって、コインミキシングサービスのトランザクションコストは低減され得る。しかし、協調サービス（例えば、ＣｏｉｎＪｏｉｎ）に依存する実施は、協調サービスが危殆化される場合に匿名性の喪失を危険にさらすことがある。いくつかの実施で、必ずしも‘中央サーバー’それ自体は存在しないが、ＣｏｉｎＪｏｉｎトランザクションにおける参加者は、それでもなお、トランザクション出力に対応するトランザクション入力を決定することが可能であり得る。例えば、入力アドレスが｛Ａ，Ｂ，Ｃ，Ｄ｝であり、出力アドレスが｛Ａ’，Ｂ’，Ｃ’，Ｄ’｝であるとする。ユーザが彼ら自身の情報をトランザクションに含める場合に、入力及び出力アドレスは、一般的に、同時にトランザクションに加えられ得る。この状況で、トランザクションの出力及び入力アドレスの順序は、それらがトランザクションに加えられる順序で相互に関連付けられてよく、トランザクションの参加者が入力アドレスと対応する出力アドレスとの間のリンクを推測することを可能にする。いくつかの実施で、ユーザは、彼らの出力アドレスを“公表”（announce）し、それをサービスによってプールに加えてもらい、それから、サービスによってシャッフルされた“出力アドレスの順序”を有してよい。しかし、そのような実施では、各ユーザの出力アドレスの公表は、公表者の入力及び出力アドレスの間のリンクを暴露する可能性がある。匿名性を維持するために、様々な実施は、第三者がユーザの出力アドレスを知っている確率をプロセスが１／ｎよりも増大さないように、出力アドレスをＣｏｉｎＪｏｉｎトランザクションに組み込む。ここで、ｎは、ＣｏｉｎＪｏｉｎトランザクションにおける出力の数である。実施形態において、シャッフルプロセスは、後に複数のＣｏｉｎＪｏｉｎトランザクションに含まれるシャッフルされた出力アドレスの組を生成する。
【００３７】
図２は、実施形態において、９個の要素の組について集積木Ｔ（ε）２００の例を表す。示される例では、集積木は、９つの要素及び３つのレベルを有しており、各内部ノードは、３つの子ノードを有している。表されている例では、集積木は、根ノードｒ２０２を有している。根ノードｒ２０２は、３つの子ノード、すなわち、第１中間ノードｄ２０４、第２中間ノードｅ２０６、及び第３中間ノードｆ２０８を有している。３つの中間ノードの夫々は、３つの子ノードを有しており、子ノードの夫々は、集積木のリーフノードである。第１中間ノードｄ２０４は、第１子ノードａ２１０、第２子ノードｂ２１２、及び第３子ノードｃ２１４を有している。第２中間ノードｅ２０６は、第１子ノードｇ２１６、第２子ノードｈ２１８、及び第３子ノードｉ２２０を有している。第３中間ノードｆ２０８は、第１子ノードｊ２２２、第２子ノードｋ２２４、及び第３子ノードｌ２２６を有している。
【００３８】
様々な実施形態で、暗号アキュムレータは、ハッシュテーブルにデータを格納し、メンバーシップ認証を実行するために使用されてよい。いくつかの例で、アキュムレータは、ＲＳＡベース又は双線形写像アキュムレータである。様々な例で、静的アキュムレータ（固定されたメンバーの組を有する）及び動的アキュムレータ（組内のメンバーの追加又は削除を認める）が使用されてよい。静的双線形写像アキュムレータは、次のように実施されてよい：
Ｇ１、Ｇ２を、生成元（generators）ｇ１、ｇ２による素数位数（prime  order）ｐの２つの巡回乗法群（cyclic  multiplicative  groups）とする。また、Φ（ｇ２）＝ｇ１であるような同型写像（isomorphism）Φ：Ｇ２→Ｇ１が存在すると仮定する。位数ｐの巡回乗法群であるＧＭを考えると、双線形ペアリングは、次の特性を有してｅ：Ｇ１×Ｇ２→ＧＭと定義され得る：
●双線形性（Bilinearity）：ｅ（Ｐａ，Ｑｂ）＝ｅ（Ｐ，Ｑ）ａｂ∀Ｐ∈Ｇ１、Ｑ∈Ｇ２及びａ，ｂ∈Ｚｐ。  
●非退化形式（Non-degeneracy）：（ｇ１，ｇ２）≠１。  
●計算可能性（Computability）：ｅ（Ｐ，Ｑ）∀Ｐ∈Ｇ１、Ｑ∈Ｇ２を計算するための効率的なアルゴリズムが存在する。
【００３９】
続く例では、Ｇ１＝Ｇ２＝Ｇ及びｇ１＝ｇ２＝ｇと設定され、ペアリングｅ：Ｇ×Ｇ→ＧＭが考えられる。双線形ペアリングに基づく双線形写像アキュムレータは、累積値ｆ’（Ｅ）＝ｇ（ｅ１’＋ｓ）（ｅ２’＋ｓ）・・・（ｅｎ’＋ｓ）におけるｎ個の要素の組Ｅ＝（ｅ１，・・・，ｅｎ）を累積することができる。累積値はＧの要素であり、それはＺｐ＊の要素を累積する。要素（ｅ１’，・・・，ｅｎ’）∈Ｇは、組Ｅ＝（ｅ１，・・・，ｅｎ）∈Ｇの元の要素の暗号ハッシュであり、すなわち、
【数１】
2021531689.tif 000002
として、ｅｉ’＝ｈ（ｅｉ）。
【数２】
2021531689.tif 000003
は、入力として巡回乗法群Ｇの要素を取り、出力として
【数３】
2021531689.tif 000004
の整数を生成する衝突耐性ハッシュ関数である。最後に、ｓは、秘密を保たれるトラップドア（trapdoor）情報を表す。
【００４０】
認証されたデータ構造を用いてデータを効率的に格納するために、集積木が使用される。これは、一般的に、一定の時間更新及び一定サイズ証明を提供する。集積木の使用は、一般的に、通信及び検証コストを下げるだけでなく、全ての可能性があるクエリへの解を予め計算する様々な代替案に対する記憶コストも下げる。
【００４１】
様々な実施形態で、集積木は、クエリに関与するサブセットについてハッシュ値の正確さを検証するために使用される。組のための公開ツリーダイジェストはハッシュ値を裏付け、転じて、ハッシュ値は組を妥当性確認する。
【００４２】
集積木は、０＜ε＜１として、Ｔ（ε）として表される。Ｔ（ε）は、ｎ個のリーフを有する根付き木（rooted  tree）に相当し、組Ｅのｎ個の要素が格納される。木のレベル数は、
【数４】
2021531689.tif 000005
として定義され、一方、ノードごとの子ノードの数はＯ（ｎε）である。リーフ（すなわち、組要素）は、レベル０により識別される同じレベルにある。
【００４３】
ｅ∈［ｅ１，・・・，ｅ９］を格納する木Ｔ（ε）内の各リーフノードｖについて、累積値ψ（ｖ）は、その要素自体の値に等しいと定義される：
ψ（ｖ）＝ｅ。
【００４４】
レベル１＜ｉ＜ｌ（ここで、ｌ＝２）での木Ｔ（ε）内の各非リーフノードについて、累積値ψ（ｖ）は、次のように定義される：
【数５】
2021531689.tif 000006
ここで、Ｃ（ｖ）は、ノードｖの子ノードの組であり、ψ（ｕ）は、ノードｕの双線形局所的ダイジェストである。例えば、図２の集積木の場合に、Ｃ（ｖ＝ｄ）＝｛ａ，ｂ，ｃ｝である。ｓは、スキームのトラップドアであり、
【数６】
2021531689.tif 000007
は、衝突耐性ハッシュ関数である。
【００４５】
組Ｅに属する所与の要素ｘの場合に、メンバーシップの証明π（ｘ）は、集積木のレイヤごとに１つである証明の順序付けられたシーケンスπ（ｘ）＝｛πｉ，ｉ＝１，・・・，ｌ｝を有する。証明の各要素は、レベルごとに要素の局所的ダイジェストαｉ及びブランチウィットネスβｉから成る対に対応する：
πｉ＝（αｉ、βｉ），ｉ＝１，・・・，ｌ。
【００４６】
１＜ｉ＜ｌとして、所与のレイヤについて、
【数７】
2021531689.tif 000008
が成立し、ここで、Ｓ（ｖｉ）は、木Ｔ（ε）内のノードｖｉの兄弟（siblings）の組に対応する。例えば、図２の集積木の場合に、兄弟の組は、Ｓ（ｖ＝ｄ）＝｛ｅ，ｆ｝である。
【００４７】
所与のレイヤｉの場合に、対応する証明要素は、次のコンポーネントを含む：
●根ｒへ要素ｘをリンクするノードのパスＰ（ｘ）：ｘ→ｒで見つけられる前のレイヤ（レイヤｉ−１）内のノードの双線形ダイジェストを表すαｉ。レイヤ１＜ｉ＜ｌの場合に、αｉは、レイヤｉ−１に存在する全ての要素について同じである。  
●クエリされているノードから木の根へのパスの欠落ノードが信頼できることを証明するウィットネスである“ブランチウィットネス”を表すβｉ。
【００４８】
証明は、一般的に、信頼できるパーティによって計算され、ユーザ／プローバ（prover）へ送られる。トラップ情報ｓは、しばしばプローバに知られていない。しかし、数量
【数８】
2021531689.tif 000009
は、（一般的にサードパーティによって）公にされる。
【００４９】
集積木の全体の大域的な双線形ダイジェストは、ｄ＝ψ（ｒ）である。ここで、
ψ（ｒ）＝ｇ（ｈ（ψ（ｄ））＋ｓ）（ｈ（Ψψ（ｅ））＋ｓ）（ｈ（ψ（ｆ））＋ｓ）
であり、ｒは、木の根（root）を示す。
【００５０】
検証フェーズにおいて、ユーザは、その証明π（ｘ）を検証は（verifier）へ供給する。ｇｓが公にされている場合に、検証者は、
１．α１＝ｘであることをチェックし、
２．ｉ＝２，・・・，ｌの場合に、ｅ（αｉ，ｇ）＝ｅ（βｉ−１，ｇｓ＋ｈ（αｉ−１））であることを検証する。
【００５１】
双線形写像特性を用いて、第２の関係はまた、次の数量を検証することと同等である：
【数９】
2021531689.tif 000010
この例では、証明は、上記の関係が成立する場合に受け入れられる。
【００５２】
本文書中、公開／秘密キー対は、参加者によって供給されたデータを用いて構築された集積木の局所的及び大域的ダイジェストを用いて生成される。キー対は、ブロックチェーンへの包含のためにＣｏｉｎＪｏｉｎトランザクションの提出前に参加者によって行われたデポジットをロック（し、後にアンロック）するために使用される。
【００５３】
様々な実施形態は、２つのパーティ間の共有秘密（secret）を確立するためにキー共有アルゴリズムを使用する。
【００５４】
ディフィー・ヘルマン（Diffie-Hellman）キー共有プロトコルは、２人のユーザが公開情報を交換することによって共有秘密を生成することを可能にするキー共有プロトコルである。いくつかの実施形態で、ディフィー・ヘルマンなどのキー共有アルゴリズムは、暗号通貨とともに使用されるステルスアドレスを生成するために使用されてよい。例えば、ステルスアドレスは、ビットコインプロトコルの匿名性を強化するために使用されてよい。ステルスアドレスが使用される場合に、ファンドの（潜在的な）受け手はシード値を発行し、それからアドレスが導出され得る。暗号通貨は、（受け手の既知の公開アドレスではなく）導出されたアドレスへ送られ、次いで、意図されたい受け手によって請求され得る。シードからアドレスを導出することは困難であるから、匿名性がもたらされる。いくつかの実施形態で、このアプローチは、受け手が正確なビットコイントランザクションを識別するために全ての入来トランザクションＴｘＯｕｔをスキャンする必要がある場合に、制約されることがある。
【００５５】
ディフィー・ヘルマンキー共有プロトコルの作業内容の説明がここで示される。それは、楕円曲線上の一般化された離散対数問題の上に構成される。すなわち、楕円曲線ディフィー・ヘルマンキー共有（Elliptic  curve  Diffie-Hellman  key  exchange，ＥＣＤＨ）である。
【００５６】
ＥＣＤＨプロトコルは、２人のユーザ、すなわち、送り手及び受け手を含む。送り手は、受け手によって後に回復され得る導出されたアドレスへいくつかのファンドを転送するために共有秘密を使用する。
【００５７】
●受け手は、秘密ＥＣキーｄと、対応する公開キーＱ＝ｄ×ｇを生成する。この公開キーは、広く利用可能にされる。
【００５８】
●送り手も、秘密キーｅと、その対応する公開キーＰ＝ｅ×ｇを生成する。
【００５９】
●両方の公開キーを交換又は公に利用可能にすることによって、送り手及び受け手は、ｃ＝Ｈ（ｅ×Ｑ）＝Ｈ（ｄ×Ｐ）として定義された秘密を共有する。ここで、Ｈは、暗号ハッシュ関数である。
【００６０】
●共有秘密とともに受け手の公開キーを使用して、送り手は新しい公開キー：
Ｑ’＝Ｑ＋ｃ×ｇ
を生成する。ＥＣの準同型性（homomorphic  property）を使用して、この新しい公開キーは：
Ｑ’＝ｄ×ｇ＋ｃ×ｇ＝（ｄ＋ｃ）×ｇ＝ｓ×ｇ
として再配置され得る。ここで、ｓ＝ｄ＋ｃは、新しく生成された公開キーＱ’に関連する秘密キーである。この新しい公開／秘密キー対の特徴は、送り手及び受け手の両方がＱ’を決定可能であるが、受け手しか、関連する秘密キーｓを知らないことである。
【００６１】
●ステルスアドレスの場合に、送り手は、自身の公開キーを直ぐには送らず、代わりに、新しい公開キーＱ’へファンドを送り、値Ｐが置かれるOP_RETURNトランザクション出力を含める。
【００６２】
●受け手は、それらのトランザクションのOP_RETURN出力の夫々に含まれるデータがＰであると推測し、ｃ＝Ｈ（ｄ×Ｐ）の共有秘密を計算する。検討中のトランザクションが公開キーＱ＋（ｃ×ｇ）によって生成されるアドレスへの支払いも有する場合に、そのアドレスのための秘密キーはｄ＋ｃである。受け手のみが、そのアドレスにあるビットコインを使用する能力を有している。これは、ｄ及びｃの両方が受け手によって知られており、他者には一般的に知られていないからである。
【００６３】
本文書は、ビットコインユーザによって所有されている入力及び出力アドレスの間のリンクが不明りょうにされるようにブロックチェーン上で複数の独立したＣｏｉｎＪｏｉｎトランザクションをブロードキャストすることを有する、アキュムレータに基づくマルチＣｏｉｎＪｏｉｎトランザクションサブミッション（Accumulators-based  Multi-CoinJoin  Transaction  Submission，ＡＭＣＴ）について記載する。プロトコルは、参加者の組と、参加者に関する情報を凝縮するよう構築された集積木と、参加者の情報を受け取り、それを使用して、参加者と共有される秘密、並びに局所的及び大域的ダイジェストなどの、集積木から導出された値を構成するディーラーとを含む。参加者は、彼らの出力アドレスをシャッフルし、シャッフルされた出力アドレスの組は、１つ以上のＣｏｉｎＪｏｉｎトランザクションを生成するために使用されるサブセットに分けられる。ＡＭＣＴプロトコルは、参加者が、出力アドレスのサブセットと交わらないサブグループに分けられることを可能にする。例えば、参加者は、２つの異なったＣｏｉｎＪｏｉｎトランザクションに含まれる自身の出力及び入力アドレスを有してよい。更に、ＣｏｉｎＪｏｉｎトランザクションは、攻撃者が容易にそれらを結びつけることを防ぐように生成され得る。様々な例で、集積木から導出された値は、ＣｏｉｎＪｏｉｎトランザクションがブロックチェーン上でブロードキャストされる前に参加者によって行われたデポジットをロック（し、後にアンロック）するために使用される。ディーラーは、１人以上の参加者が彼らの属するサブグループに関連するＣｏｉｎＪｏｉｎトランザクションに署名しない場合に、補償されるよう他の参加者によって必要とされる情報を公開することによって、セーフガードの役割を担ってよい。
【００６４】
実施形態において、ディーラーは、信頼できる第三者の役割を担う。参加者は、ｎ人の参加者の組Ｓであり、ここで、ｎは、２つの整数の積、ｎ＝Ｎ×ｍとして表現可能であり、Ｎは、組Ｓ内のサブグループ（Ｓ１，・・・，ＳＮ）の数であり、ｍは、所与のサブグループ内の参加者の数である。参加者の各サブグループＳｉは、ビットコインブロックチェーン上で１つのＣｏｉｎＪｏｉｎトランザクションＴＣｉをブロードキャストすることに関与する。
【００６５】
各参加者は、それらのＣｏｉｎＪｏｉｎトランザクションに含まれるべき１つの入力及び１つの出力を有している。参加者は、一般的に、出力アドレスでのファンドの受け手ではない。すなわち、参加者は、そのアドレスの１つから、それが秘密鍵を所有している新しいアドレスへファンドを動かそうと試みていない。この場合に、ファンドは、受け手の署名によりアンロックされ得る。
【００６６】
各ＣｏｉｎＪｏｉｎトランザクションは、ｍ個の入力及びｍ個の出力を含み、それらの夫々は、ｘビットコイン（ＢＴＣ）を支出（アンロック）し又は受け取る。集積木Ｔ（ε）は、ｎ人の参加者によって供給された要素（ｅ１，・・・，ｅｎ）を格納するようディーラーによって構築される。
【００６７】
集積木の構造は、組Ｓの間のサブグループ内の参加者の分布を反映している。すなわち、ｍは、集積木の最下層でのノードごとのリーフの数であり、Ｎは、最後から二番目の層でのノードの数である（Ｎ個の親ノードは、夫々ｍ個のリーフを有する）。
【００６８】
参加者の出力アドレスは、シャッフルされ、シャッフルされた出力アドレスの最終的な組は、ｍ個の出力アドレスのＮ個のサブセットに分けられる。ディーラーは、出力アドレスのサブセットごとにＣｏｉｎＪｏｉｎトランザクションを生成する。次いで、ディーラーは、ＣｏｉｎＪｏｉｎトランザクションを参加者Ｓｉのサブグループへ、彼らの各々の入力及び署名の付加のために送る。様々な例で、参加者は、その入力及びその出力を、異なったＣｏｉｎＪｏｉｎトランザクションに含まれている。追加の例では、ディーラーは、トランザクションのサイズに対する制限を解消するために、単一の大きいトランザクションを、複数の、より小さいトランザクションに分けてよい。
【００６９】
ブロックチェーンでの包含のためのＣｏｉｎＪｏｉｎトランザクションの提示の前に、各参加者は、ｙＢＴＣのデポジットをコミットする。デポジットは、Ｐ２ＳＨアドレスへ送られ、２つの顕著な方法においてアンロックされ得る：
−  所与の時点ΔＴより前に、全てのＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに成功裏に含まれる場合に、集積木から導出された数量を使用する。  
−  所与の時点ΔＴより前に、全てのＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに成功率に含まれない場合に、ディーラーによって示された数量を使用する。
【００７０】
Ｎ個のＣｏｉｎＪｏｉｎトランザクションは独立してかつ準同時にサブミットされるべきであるが、参加者は、その入力を、そのサブグループに割り当てられているＣｏｉｎＪｏｉｎトランザクションに加えず、従って、そのトランザクションを不完全なまま／妥当でないままとすることが起こり得る。結果として、サブグループ内の参加者は、彼らの入力をアンロックしない。その間に、ブロックチェーンでの包含のために彼らのＣｏｉｎＪｏｉｎトランザクションに署名しサブミットした他のサブグループ内の参加者は、ブロックチェーン上でブロードキャストされなかったトランザクションに彼らの出力アドレスが含まれる場合に、彼らの入力を費やしながら、出力アドレスでコインを受け取らないリストがある。参加者にその役割を果たすよう、つまり、その入力をＣｏｉｎＪｏｉｎトランザクションにおいて付加し署名するよう強制することは困難又は不可能なことがある。従って、いくつかの実施形態で、自身の入力を費やしながら、他の参加者の不作法によりコインを受け取らなかった参加者を補償するメカニズムが提供される。ＣｏｉｎＪｏｉｎトランザクションをブロックチェーンに含めることに成功しなかった参加者は、必ずしも悪意があるとは限らない。例えば、参加者は、プロトコル中に意図せず接続を失う可能性がある。また、１人の参加者がｍ個の入力／出力を有する１つのＣｏｉｎＪｏｉｎトランザクションのプロトコルをドロップした場合でさえ、トランザクションが失敗する可能性がある点に留意されたい。従って、悪意のある参加者と同じサブグループに属している参加者は、他の参加者の不作法に対して罰せられるべきではなく、またその恩恵を受けるべきでもない。
【００７１】
ＡＭＣＴプロトコルは、以下で詳細に記載される。集積木の構成と、参加者とディーラーとの間の情報の交換とについて論じる。それから、出力アドレスをシャッフルするプロセスについて記載する。それから、参加者のデポジットトランザクションの生成及び提示について論じる。次の項は、ＣｏｉｎＪｏｉｎトランザクションの生成及び提示と、ＣｏｉｎＪｏｉｎトランザクションの全て又は一部の提示後のリターン／補償請求とについて説明する。
【００７２】
本文書にわたって、実施形態は、２人の参加者の２つのサブグループに分けられた４人の参加者に関する簡単な場合を参照して記載される。参加者のランダムな順序（又はシーケンス）Ｕ１，Ｕ２，・・・，Ｕｎを考える。ここで、ｎ＝Ｎ×ｍであり、Ｎは、組内のサブグループの数であり、ｍは、所与のサブグループ内の参加者の数である。一例において、ｎ＝４、Ｎ＝ｍ＝２である。
【００７３】
各参加者Ｕｉは、楕円曲線上のランダムな点ｅｉを選択し、そのハッシュｅ’＝ｈ（ｅｉ）をディーラーへ送る。
【数１０】
2021531689.tif 000011
は衝突耐性ハッシュ関数である。ディーラーは、秘密ｓ（トラップドア情報）を選択し、次の通りに集積木の大域的ダイジェストを再構成する：
ｄ＝ψ（ｒ）＝ｇ（ｅ’１＋ｓ）（ｅ’２＋ｓ）・・・（ｅ’ｎ＋ｓ）。
【００７４】
トラップドア情報ｓは、参加者に未知である。しかし、数量ｇｓ，ｇｓ２，・・・，ｇｓｎは、公にされる。
【００７５】
ディーラーは、局所的ダイジェストψ（ｖ１），・・・，ψ（ｖＮ）を計算する、ここで、ｖｉ（ｉ∈［１，Ｎ］）は、集積木の最後から二番目の層にある親ノードの１つである。局所的ダイジェストも大域的ダイジェストも、参加者へ送られない。
【００７６】
ディーラーは、ダイジェストｄを秘密キーとして使用する。実施形態において、大域的ダイジェストは楕円曲線の点であるから、ディーラーは、それから導出された数ｖを選択する。例えば、ｖは、ｄの１つの座標（ｘｄ又はｙｄ）、若しくはその２つの連結（和）、又はハッシュ関数が入力として楕円曲線からの点をとり、Ｚｐ＊場の数を出力する関数（参加者には未知）である場合に、大域的ダイジェストのハッシングにより得られる数、であることができる。
【００７７】
ディーラーは、集積木の大域的ダイジェストに対応する楕円曲線内の点のｘ座標を使用する。このようにして、ｖ＝ｘｄが、秘密キーとして、Ｑが、関連する公開キーＱ＝ｖ×ｇ（ｇは、楕円曲線の生成元である）として定義される。
【００７８】
ディーラーは、Ｑを参加者に利用可能にする。
【００７９】
各参加者Ｕｉは、ランダムな秘密キーｙｉを選択し、対応する公開キーＰｉ＝ｙｉ×ｇを公開する。
【００８０】
参加者はまた、Ｚｐ＊場で、彼らがディーラーへ非公開で送る乱数（ソルト）も選択する（例えば、関連する暗号解読キーがディーラーによってのみ知られている参加者が、ディーラーによって公にされた暗号キーを用いて、彼らの乱数をディーラーへ送ってもよい）。ωｉは、参加者Ｕｉによって選択されたソルトとして表され、秘密キーと見なされ得る。ディーラー及び参加者Ｕｉの両方が、関連する公開キーＷｉ＝ωｉ×ｇを推定することができる。この公開キーは公にされない。
【００８１】
本文書では、図３に表されているような、２人の参加者（ｍ＝２）の２つのサブグループ（Ｎ＝２）に分けられたｎ＝４人の参加者に関する簡単な例を用いて、様々な例が説明されている。
【００８２】
図３は、実施形態において、各リーフノードが関連する要素ｅｉ（ｉ＝１，・・・，４）を有している集積木の例を表す。示される例では、集積木は、４つの要素及び３つのレベルを有しており、各中間ノードは、２つの子ノードを有している。表されている例では、集積木は、根ノードｒ３０２を有している。根ノードｒ３０２は、２つの子ノード、すなわち、第１中間ノードａ３０４及び第２中間ノードｂ３０６を有している。２つの中間ノードの夫々は、２つの子ノードを有しており、それらの夫々が集積木のリーフノードである。第１中間ノードａ３０４は、第１子ノードｅ１３０８及び第２子ノードｅ２３２０を有している。第２中間ノードｂ３０６は、第１子ノードｅ３３１２及び第２子ノードｅ４３１４を有している。
【００８３】
最初の２人の参加者（Ｕ１，Ｕ２）は局所的ダイジェストψ（ａ）を共有し、一方、参加者（Ｕ３，Ｕ４）の第２サブグループは局所的ダイジェストψ（ｂ）を共有する。この例の大域的ダイジェストは、次の関係：ｄ＝ψ（ｒ）＝ｇ（ｈ（ψ（ａ））＋ｓ）（ｈ（ψ（ｂ））＋ｓ）によって与えられる。
【００８４】
図４は、実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分として実行される出力シャッフルの例を表す。実施形態において、参加者によって与えられた出力アドレスの組をシャッフルするプロセスは、２つのフェーズ、すなわち、暗号化フェーズ及び暗号解読フェーズを含む。
【００８５】
暗号化フェーズにおいて、各参加者Ｕｉは、対応する公開／秘密キー対（Ｅｉ，ｋｉ）を有し、ここで、Ｅｉ＝ｋｉ×ｇである（ｇは、プロトコルによって選択された楕円曲線の生成元である）。公開キーＥ１，Ｅ２，・・・，Ｅｎはディーラーへ送られ、ディーラーは、それらを他の参加者に対して、参加者Ｕ１，Ｕ２，・・・，Ｕｎの順序が彼らに知られないように利用可能にする。例えば、ディーラーは、公開キーを、順序付きリスト又はアレイの形で利用可能にし得る。
【００８６】
暗号化フェーズにおいて、第１参加者Ｕ１は、第１参加者の公開キーＥ１により第１参加者の出力アドレスＯ１を暗号化する。結果として得られた暗号化された出力アドレスは、“シャッフルされた出力の組”（set  of  shuffled  outputs，ＳＳＯ）を有する。
【００８７】
Ｕ１は、次の参加者Ｕ２の公開キーであるＥ２でＳＳＯを暗号化し、暗号化されたＳＳＯをＵ２へ転送する。次いで、Ｕ２は、ｋ２を用いてＳＳＯを暗号解読し、Ｅ２を用いてＵ２の出力アドレスＯ２を暗号化し、この新たに暗号化されたアドレスをＳＳＯに加える。Ｕ２は、ＳＳＯ内の暗号化されたアドレスの順序をシャッフルし、シャッフルされたＳＳＯをＥ３で暗号化し、それから、暗号化されたＳＳＯを第３の参加者Ｕ３へ転送する。このプロセスは、Ｕｎに達するまで続く。ここで、ｎは、プロトコルにおける参加者の総数である。実例では、例を簡単にするために、ｎ＝４が選択される。しかし、一般的に、ｎの数は、よりずっと大きい方が好ましい。最後の参加者の暗号化された出力アドレスがＳＳＯに加えられた後、Ｕｎは最後のシャッフルを実行し、ＳＳＯをＥ１で暗号化し、ＳＳＯを最初の参加者Ｕ１へ送り返す。
【００８８】
図４に表されている例では、第１参加者４０２は、第１参加者の出力アドレス４１２を暗号化し、アドレスを、シャッフルされた出力の第１の組４１０に加える。第１参加者４０２は、第２参加者４０４の公開キーを用いて、シャッフルされた出力の第１の組４１０を暗号化し、シャッフルされた出力の暗号化された第１の組を第２参加者４０４へ供給する。
【００８９】
第２参加者４０４は、第２参加者の出力アドレス４１８を暗号化し、アドレスを、第１参加者の出力アドレス４１６を含むシャッフルされた出力の第２の組４１４に加える。第２参加者４０４は、第３参加者４０６の公開キーを用いて、シャッフルされた出力の第２の組４１４を暗号化し、シャッフルされた出力の暗号化された第２の組を第３参加者４０６へ供給する。
【００９０】
第３参加者４０６は、第３参加者の出力アドレス４２６を暗号化し、アドレスを、第１参加者の出力アドレス４２２及び第２参加者の出力アドレス４２４を含むシャッフルされた出力の第３の組４２０に加える。第３参加者４０６は、第４参加者４０８の公開キーを用いて、シャッフルされた出力の第３の組４２０を暗号化し、シャッフルされた出力の暗号化された第３の組を第４参加者４０８へ供給する。
【００９１】
第４参加者４０８は、第４参加者の出力アドレス４３６を暗号化し、アドレスを、第１参加者の出力アドレス４３０、第２参加者の出力アドレス４３２、及び第３参加者の出力アドレス４３４を含むシャッフルされた出力の第４の組４２８に加える。第４参加者４０８は、第１参加者４０２の公開キーを用いて、シャッフルされた出力の第４の組を暗号化し、シャッフルされた出力の暗号化された第４の組を第１参加者４０２へ供給する。
【００９２】
図５は、実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分として実行される暗号解読動作の例を表す。実施形態において、暗号解読フェーズの部分として、ＳＳＯは、ｎ人の元の参加者の夫々へルーティングされる。最初の暗号化シャッフルループの終わりに、第１参加者Ｕ１  ５０２は、シャッフルされた出力の第１の組５４０を持っている。シャッフルされた出力の第１の組５４０は、第１の暗号化された出力アドレス５４２、第２の暗号化された出力アドレス５４４、第３の暗号化された出力アドレス５４６、及び第４の暗号化された出力アドレス５４８を含む。Ｕ１  ５０２は、ＳＳＯを暗号解読し、ＳＳＯから第１参加者の暗号化された出力アドレス５４２を探し、関連する秘密キーｋ１を用いてアドレスを暗号解読する。
【００９３】
その時点で、第１参加者は、ＳＳＯにおけるその出力アドレスの新しい位置を知る。暗号解読フェーズ中に、参加者は、彼らの出力アドレスの位置をチェックし、それにより、彼らは、それを含むＣｏｉｎＪｏｉｎトランザクションをブロードキャストすることにどのサブグループが関与しているかを後に知る。しかし、参加者は、他の参加者の出力の位置を知らないままである。
【００９４】
そのために、ディーラーは、一時的な（ephemeral）公開／秘密キー対（ＥＤ，ｋＤ）を生成し、公開キーを参加者に利用可能にする。参加者は、ＥＤを使用して、シャッフルされたＳＳＯ内の彼らの出力アドレス（図５では、組５１０のアドレス５１２、組５２０のアドレス５２２、５２４、組５３０のアドレス５３２、５３４、５３６、及び組５４０のアドレス５４２、５４４、５４６、５４８として表されている）を暗号化する。
【００９５】
暗号解読フェーズが進むにつれて、第１参加者は、その出力アドレスを、関連する秘密キーｋ１を用いて暗号解読し、Ｏ１をＥＤで再暗号化する。次いで、Ｕ１は、新しいＳＳＯを第２参加者の公開キーＰ２で暗号化し、第２の暗号化された組５１０をＵ２  ５０４へ転送する。第２の暗号化された組５１０は、第１の暗号化された出力アドレス５１２、第２の暗号化された出力アドレス５１４、第３の暗号化された出力アドレス５１６、及び第４の暗号化された出力アドレス５１８を含む。第２参加者は、ｋ２を用いてＳＳＯを暗号解読し、第２参加者の出力アドレス５１４を見つけ、それをｋ２で暗号解読し、それをＥＤで再暗号化する。次いで、Ｕ２  ５０４は、新しいＳＳＯを公開キーＰ３で暗号化し、第３の暗号化された組５２０をＵ３  ５０６へ転送する。第３の暗号化された組５２０は、第１の暗号化された出力アドレス５２２、第２の暗号化された出力アドレス５２４、第３の暗号化された出力アドレス５２６、及び第４の暗号化された出力アドレス５２８を含む。第３参加者は、ｋ３を用いてＳＳＯを暗号解読し、第３参加者の出力アドレス５１４を見つけ、それをｋ３で暗号解読し、それをＥＤで再暗号化する。次いで、Ｕ３  ５０６は、新しいＳＳＯを公開キーＰ４で暗号化し、第４の暗号化された組５３０をＵ４  ５０８へ転送する。第４の暗号化された組５３０は、第１の暗号化された出力アドレス５３２、第２の暗号化された出力アドレス５３４、第３の暗号化された出力アドレス５３６、及び第４の暗号化された出力アドレス５３８を含む。様々な例で、プロセスは、各参加者がその暗号化された出力アドレスをＳＳＯで見つけ、それをその対応する暗号解読（及びＥＤで暗号化）された値で置き換えるまで続く。
【００９６】
最後の参加者５０８は、ＳＳＯをＥＤで暗号化し（それをＥ１で暗号化する代わりに）、暗号化されたＳＳＯをディーラーへ送る。それから、ディーラーは、暗号化された出力の組を持っている。ディーラーのみが秘密キーｋＤを知っているので、組及びその中の各出力アドレスを暗号解読することができる。
【００９７】
その時点でのＳＳＯ内の出力アドレスの入れ替えは、出力がＣｏｉｎＪｏｉｎトランザクションに含まれている最終的な順序を表す。
【００９８】
図６は、実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分として実行される出力アドレスの並べ替えの例を表す。出力アドレスが上述されたようにシャッフルされた後、各参加者は、シーケンス内の彼らの最初の位置と、彼らの出力アドレスの最終的な位置とを知っている。図５は、４人の参加者の例における出力アドレスのとり得る最終的な順序を表す。この例では、第３参加者Ｕ３は、その出力アドレスがＳＳＯ内の最初の要素であることを知っている。結果として、Ｕ３は、その出力アドレスが最初のＣｏｉｎＪｏｉｎトランザクションに含まれることになると知る。
【００９９】
この例では、夫々２人の参加者の２つのサブグループに分けられた４人の参加者の組が考えられている。従って、ディーラーは、２つのＣｏｉｎＪｏｉｎトランザクション、すなわち、図６に表されているＴＣ１  ６０２及びＴＣ２  ６０４を生成すると期待される：
−  第１トランザクションＴＣ１  ６０２は、第３及び第１参加者（夫々Ｕ３及びＵ１）の出力アドレス６０６を含む。  
−  第２トランザクションＴＣ２  ６０４は、第２及び第４参加者（夫々Ｕ２及びＵ４）の出力アドレス６０８を含む。
【０１００】
ディーラーは、これら２つのＣｏｉｎＪｏｉｎトランザクションを生成し、それらを参加者へ送る。参加者は、彼らの入力を付加し、トランザクションに署名し、それらを、ブロックチェーンに含めるためにサブミットする。ディーラーが上記のトランザクションを参加者へ送る前に、各参加者は、プロトコルが全てのＣｏｉｎＪｏｉｎトランザクションのブロードキャストの成功で終わる場合に後に再請求可能であるいくらかのコインを彼らがアンロックするトランザクションを生成しブロードキャストする。実施形態において、第１参加者は第１入力６１０をコミットし、第２参加者は第２入力６１２をコミットし、第３参加者は第３入力６１４をコミットし、第４参加者は第４入力６１６をコミットする。プロトコルが時期尚早に終わる（全てのＣｏｉｎＪｏｉｎトランザクションがブロードキャストされるわけではない）場合に、補償メカニズムが考えられる。
【０１０１】
実施形態において、プロトコルは、プロトコルに関わっているトランザクションがリンク不可能であることを確実にする。これは、攻撃者が、ネットワークへ送られたＣｏｉｎＪｏｉｎトランザクションを容易にリンクすることができないことを意味する。その上、デポジットトランザクションとＣｏｉｎＪｏｉｎトランザクションとの間にリンクは確立されない。従って、集積木から導出された数量に加えて、ディーラーと参加者との間の共有秘密を用いて、後述されるように、Ｐ２ＳＨアドレスが生成される。
【０１０２】
公に利用可能にされた情報と、ディフィー・ヘルマンキー共有プロトコルとを用いて、ディーラーは、参加者Ｕｉごとに秘密ｃｉを構成し、当該参加者と共有する：
ｃｉ＝Ｈ（ｖ×Ｐｉ）＝Ｈ（Ｑ×ｙｉ）
ここで、Ｈは、入力として楕円曲線からの点をとり、Ｚｐ＊場の数内の数を出力するハッシュ関数（参加者に知られている）である。
【０１０３】
参加者は、新しい公開キーを生成するために、この共有秘密を使用する：
Ｂｉ＝Ｐｉ＋Ｑ＋ｃｉ×ｇ
Ｂｉ＝ｓｉ×ｇ
なお、ｓｉ＝ｙｉ＋ｖ＋ｃｉである。ｓｉは、Ｂｉに関連する秘密キーである。Ｐｉ及びＱは公に知られているが、一般的に、ディーラー及び参加者Ｕｉしか共有秘密ｃｉを知らない。結果として、ディーラー及び参加者Ｕｉのみが公開キーＢｉを知っており、一方、誰（参加者又はディーラー）も、関連する秘密キーｓｉを知らない（ｖはディーラーによってのみ知られており、ｙｉは参加者Ｕｉによって秘密にされている）。ディーラーは、公開キーＢｉを用いて、Ｕｉによって生成されたビットコインアドレスの妥当性を検証することができる。このアドレスへ送られたファンドをアンロックすべく、参加者Ｕｉは、秘密キーｓｉを再構成するためにｖ（すなわち、集積木の大域的ダイジェスト）を計算する必要がある。これはまた、参加者のファンドを盗もうと試みる悪意あるディーラーに対して参加者を守る。
【０１０４】
各参加者Ｕｉは、乱数ωｉを選択しディーラーへ送る。ＳＳＯ内の出力アドレスの最初及び最終の順序を知っているので、参加者は次の公開キーを生成する：
Ｃｉ→ｊ＝Ｗｉ＋Ｐｊ＝ｃｉ→ｊ×ｇ
なお、ｃｉ→ｊ＝ωｉ＋ｙｊである。ここで、ｉは、出力アドレスの最初のインデックス（シーケンス内の参加者Ｕｉの実際の位置）に対応し、ｊは、シャッフル後の出力のインデックスに対応する。Ｐｊは、参加者Ｕｊに利用可能にされた公開キーである。ディーラー及び参加者Ｕｉの両方が公開キーθｉ及びＰｊを知っており、このことは、公開キーＣｉ→ｊから導出された如何なるアドレスの妥当性も検証することをディーラーに可能にするが、ディーラー及び参加者のどちらも、関連する秘密キーｃｉ→ｊを知らない。実際に、プロトコルのその時点で、誰も秘密キーｃｉ→ｊを知らない。最初の部分（ωｉ）は、ディーラー及び参加者Ｕｉによって知られており、一方、第２の部分（ｙｊ）は、参加者Ｕｊによってしか知られていない。ディーラーがωｉを公開すべきであったならば、そのとき初めて、参加者Ｕｊは、秘密ｃｉ→ｊを計算し、Ｃｉ→ｊから導出されたアドレスへ送られたファンドをアンロックし得る。
【０１０５】
図７は、実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションの部分としてデポジットのために参加者によって生成されたロッキングスクリプト７００の例を表す。
【０１０６】
妥当性がディーラーよって検証される参加者Ｕｉごとに、２つの新しい公開キーＢｉ７０２及びＣｉ→ｊ７０６が生成される：
−  Ｂｉ＝ｓｉ×ｇ（なお、ｓｉ＝ｙｉ＋ｃｉ）。参加者Ｕｉのみが秘密キーｓｉを知っている。  
−  Ｃｉ→ｊ＝ｃｉ→ｊ×ｇ（なお、ｃｉ→ｊ＝ωｉ＋ｙｊ）。ディーラー及び参加者Ｕｉの両方が公開キーＣｉ→ｊを知っている。参加者Ｕｊは公開キーＣｉ→ｊを知らない点に留意されたい。しかし、（ある時点で）ディーラーがωｉを公開すべきであったならば、その場合に、参加者Ｕｊ（のみ）は、秘密ｃｉ→ｊを計算し得る。
【０１０７】
これら２つの公開キーを用いて、参加者Ｕｉは、図７に示されるように、次のロッキングスクリプト７００を生成する。スクリプトは、ブロックチェーンでの包含のためのＣｏｉｎＪｏｉｎトランザクションの完成及び提出の前に、各参加者によって作られたｙＢＴＣのデポジットをアンロックするために使用される。
【０１０８】
ロッキング時間パラメータは、オペコードOP_CHECKSEQUENCEVERIFYを用いて定義される。ビットコインスクリプト記述システムのためのこの新しいオペコード（OP_CHECKSEQUENCEVERIFY）は、ＢＩＰ１１２で導入された。それは、使用されている出力の経過時間に基づいて、スクリプトの実行経路が制限されることを可能にする。
【０１０９】
ΔＴ７０４は、ブロックチェーン上のトランザクションの確認後の期間に対応し、その間、出力は使用不可能である（このＵＴＸＯをアンロックしようとする如何なるトランザクションも、ブロック内の使用済み出力の経過時間又は特定の時間スパンまでマイニングされない）。
【０１１０】
スクリプト７００は、参加者ＵｉによってブロードキャストされたデポジットトランザクションＤｘｉのＵＴＸＯをアンロックするために２つのオプション、すなわち、秘密ｓｉに関連する署名を供給することによる任意の時点、又は秘密ｃｉ→ｊ７０６に関連する署名供給することによるΔＴ７０４の後、を提示する。
【０１１１】
図８は、実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションにおいて４人の参加者によって生成、署名、及びブロードキャストされたデポジットトランザクション８００の例を表す。デポジットトランザクション８００は、ブロックチェーンに含めるためにサブミットされる。ブロックチェーンに含まれると、ディーラーは、部分的なＣｏｉｎＪｏｉｎトランザクションを参加者へ、ブロードキャスト前の彼らの入力の包含及び署名のために転送することができる。
【０１１２】
図８に表されている実施形態は、第１デポジットトランザクション８０２、第２デポジットトランザクション８０４、第３デポジットトランザクション８０６、及び第４デポジットトランザクション８０８を示す。各デポジットトランザクションは、対応する参加者によってサブミットされる。第１デポジットトランザクション８０２は、ｙＢＴＣをコミットする第１入力８１０を含む。第２デポジットトランザクション８０４は、ｙＢＴＣをコミットする第２入力８１２を含む。第３デポジットトランザクション８０６は、ｙＢＴＣをコミットする第３入力８１４を含む。第４デポジットトランザクション８０８は、ｙＢＴＣをコミットする第４入力８１６を含む。
【０１１３】
実施形態において、各デポジットトランザクションは、ｙＢＴＣを３つの条件のうちの１つへ支払う出力を含む。第１デポジットトランザクション８０２は、第１出力スクリプト８１８を含む。第２デポジットトランザクション８０４は、第２出力スクリプト８２０を含む。第３デポジットトランザクション８０６は、第３出力スクリプト８２２を含む。第４デポジットトランザクション８０８は、第４出力スクリプト８２４を含む。図８に示される実施形態では、各デポジットトランザクションの出力は、３つの方法で請求され得る。出力は、成功したＣｏｉｎＪｏｉｎトランザクションの部分として特定の参加者によって請求されてよく、出力は、特定の量の時間ΔＴの後にデポジッタ（depositor）によって請求されてよく、あるいは、出力は、ΔＴよりも長い第２時間量の後にデポジッタによって請求されてよい。
【０１１４】
図８に示される実施形態では、デポジットトランザクションにおいてＵＴＸＯをアンロックするための第３のオプションが含まれており、このオプションは、時間スパンΔＴ’＞ΔＴの後に利用可能である。第３のオプションは、（例えば、ディーラーに対する保護を提供するために、）プロトコルが時期尚早に終わる場合に特定の時点後に参加者が彼らのファンドを償還することを可能にするセーフガードである。この第３のオプションでは、参加者は、（ΔＴ’後に）ファンドがアンロックされるために、その署名を供給する。図７のスクリプトは、この第３のオプションを含めるよう変更され得る。
【０１１５】
ブロックチェーンに含まれると、ディーラーは、部分的なＣｏｉｎＪｏｉｎトランザクションを参加者へ転送する。
【０１１６】
図９は、実施形態において、マルチＣｏｉｎＪｏｉｎトランザクションにおいて参加者によって生成及び署名された２つのＣｏｉｎＪｏｉｎトランザクションの例を表す。
【０１１７】
この例で、ディーラーは、ＳＳＯにおいて与えられた出力アドレスを含めるとともに、OP_RETURN演算子を使用してトランザクションに余分の情報を含めながら、ＣｏｉｎＪｏｉｎトランザクションＴＣ１  ９０２及びＴＣ２  ９１２を生成する。第１ＣｏｉｎＪｏｉｎトランザクションは、第１入力９０４、第２入力９０６、第１出力９０８、及び第２出力９１０を含む。第２ＣｏｉｎＪｏｉｎトランザクションは、第１入力９１４、第２入力９１６、第１出力９１８、及び第２出力９２０を含む。
【０１１８】
集積木内の全ての要素のハッシュ及びトラップドア情報ｓを知っているので、ディーラーは、集積木の局所的ダイジェスト（図３のψ（ａ）及びψ（ｂ））を計算する。ディーラーは、参加者のサブグループの局所的ダイジェストを、サブグループ内の参加者がブロードキャスト前に完了する必要があるＣｏｉｎＪｏｉｎトランザクション内の余分の明白にアンロック可能な出力として付加する。
【０１１９】
次いで、ディーラーは、各不完全なＣｏｉｎＪｏｉｎトランザクションを各サブグループ内の第１参加者へ送る。例として、ＴＣ１がＵ１へ送られ、ＴＣ２がＵ３へ送られる。所与のサブグループ内の参加者は、協働して、彼らの各々の要素のハッシュを交換してよく、それにより、彼らは、彼らの共通の局所的ダイジェストを計算し、ディーラーによってOP_RETURNスクリプトに置かれたデータを検証する。
【０１２０】
サブグループ内の第１参加者は、彼らの入力を付加し、フラグSIGHASH_ALL|ANYONECANPAYを用いてトランザクションに署名する。次いで、それは、部分的に署名されたトランザクションを次の参加者へ転送する。これは、サブグループ内の最後の参加者がＣｏｉｎＪｏｉｎトランザクションに付加及び署名し、完成したＣｏｉｎＪｏｉｎトランザクションをブロックチェーン上でブロードキャストするまで続く。
【０１２１】
図１０は、実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによって実行される結果として、マルチＣｏｉｎＪｏｉｎトランザクションを実行するプロセスの例を表す。フローチャートは、ブロック１００２から開始するプロセス１０００を表す。ブロック１００４で、ディーラーは、ＣｏｉｎＪｏｉｎトランザクションを生成するための集積木を生成し、参加者は、ディーラーとのキー共有を実行する。ブロック１００６で、参加者は、ＣｏｉｎＪｏｉｎトランザクションのための最終的な順序付け及びグループ分けを決定するよう彼らの出力アドレスをシャッフルする。ブロック１００８で、各参加者は、多数のＢＴＣをコミットするデポジットトランザクションを生成する。
【０１２２】
決定ブロック１０１０で、ディーラーは、全ての参加者が彼らのデポジットをブロックチェーンへコミットしたかどうかを判定する。全ての参加者が彼らのデポジットをブロックチェーンへコミットしていない場合には、実行はブロック１０１２で停止し、ＣｏｉｎＪｏｉｎプロセスは中止される。全ての参加者が彼らのデポジットをブロックチェーンへコミットしたとディーラーが決定する場合には、実行はブロック１０１４へ進み、ディーラーはＣｏｉｎＪｏｉｎトランザクションを生成し、ＣｏｉｎＪｏｉｎトランザクションは、必要な署名を得るために参加者の間でルーティングされる。ブロック１０１６で、ディーラーは、トランザクションが成功裏に署名されブロックチェーンへコミットされたかどうかを判定し、一部又は全てのトランザクションで問題があった場合には、ディーラーは、フィールドトランザクションの適切な参加者に返還又は補償する動作を実行する。
【０１２３】
実施形態において、時点ＴＩは、全てのＣｏｉｎＪｏｉｎトランザクションがその時点に達する前にブロックチェーンに含まれるべきであるように、ディーラーと参加者との間で取り決められる。その時点に達すると、Ｎ個全てのＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに含まれることになるか、又はそうではない。
【０１２４】
場合１：ＴＩの前に、Ｎ個全てのＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに含まれる。
【０１２５】
ＣｏｉｎＪｏｉｎトランザクションは全て、ＴＩより前にブロックチェーンに含まれており、参加者は、各OP_RETURNスクリプトのデータを収集する。次いで、参加者は、集積木の大域的ダイジェストを計算することができる。実際に、２つのＣｏｉｎＪｏｉｎトランザクションのみがブロードキャストされる例では、大域的ダイジェストは、次のように、局所的ダイジェストの関数として表現され得る：
ｄ＝ψ（ｒ）＝ｇ（ｈ（ψ（ａ））＋ｓ）（ｈ（ψ（ｂ））＋ｓ）
【０１２６】
【数１１】
2021531689.tif 000012
は公にされていることを思い出されたい。
【０１２７】
参加者Ｕｉは、この場合に、ｓｉ＝ｖ＋ｙｉを計算することができる。ここで、ｖは、大域的ダイジェストから導出される。参加者Ｕｉは、先立ってブロードキャストしたデポジットトランザクションＤｘｉにおいて送られたファンドをアンロックすることができる。
【０１２８】
場合２：ＴＩの前に、Ｎ個全てのＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに含まれていない。
【０１２９】
何らかの理由により参加者が、そのサブグループに関連したＣｏｉｎＪｏｉｎトランザクションにその入力を付加して署名しない場合に、そのトランザクションは決してブロックチェーンに含まれない。
【０１３０】
結果として、参加者は、集積木の大域的ダイジェストを再構成することができないので、場合１のように彼らのデポジットで使用されているファンドをアンロックすることができない。
【０１３１】
この場合に、参加者は、４つのカテゴリに入る。
【０１３２】
カテゴリ１：自身の入力を使用しており（彼らが署名したＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに含まれている）、自身の出力アドレスでコインを受け取った（彼らの出力アドレスが、ブロックチェーンに含まれているＣｏｉｎＪｏｉｎトランザクションの１つに含まれている）参加者。そのような参加者は、一部又は全てのＣｏｉｎＪｏｉｎトランザクションのブロードキャスト後に−ｙＢＴＣの差引残高を有している。
【０１３３】
カテゴリ２：自身の入力を使用したが、自身の出力アドレスでコインを受け取っていない参加者。そのような参加者は、一部のみのＣｏｉｎＪｏｉｎトランザクションのブロードキャスト後に−ｘ−ｙＢＴＣの差引残高を有している。
【０１３４】
カテゴリ３：自身の入力をアンロックしなかった（彼らが署名した又は署名しなかったトランザクションが送られなかったか又は妥当でなかったために、ブロックチェーンに含まれていない）が、自身の出力アドレスでコインを受け取る参加者。そのような参加者は、一部のみのＣｏｉｎＪｏｉｎトランザクションのブロードキャスト後にｘ−ｙＢＴＣの差引残高を有している。
【０１３５】
カテゴリ４：自身の入力をアンロックしておらず、自身の出力アドレスでコインを受け取ってもいない参加者。そのような参加者は、ＣｏｉｎＪｏｉｎトランザクションの一部のブロードキャスト後又は全くＣｏｉｎＪｏｉｎトランザクションがブロードキャストされなかった後、−ｙＢＴＣの差引残高を有している。
【０１３６】
場合１は、全ての参加者がカテゴリ１であるシナリオに対応する。
【０１３７】
ディーラーは、参加者がカテゴリ２に入る場合に、参加者が彼らのデポジットを再請求し、場合によっては補償されるのを助けるよう、時間窓［ＴＩ，ΔＴ］を有している。
【０１３８】
ディーラーは、成功裏にブロックチェーンに含まれているＣｏｉｎＪｏｉｎトランザクションにおいて出力アドレスが具現されている参加者のωｉの値の組を明らかにする。これは、ＣｏｉｎＪｏｉｎトランザクションに自身の入力を付加し署名した参加者であって、カテゴリ２又は４に入る可能性がある者が正当に補償されることを可能にする。
【０１３９】
次いで、残りの参加者は、時点ｔ＞ΔＴで、彼らのデポジットトランザクションにおいて送られたファンドを、それらが補償フェーズ中に他の参加者によって使用されないままである場合に、償還することができる。
【０１４０】
ディーラーは、時間ΔＴが経過する前に、ωｉの値のサブセットを明らかにすべきである。実際に、１つを除いて全てのＣｏｉｎＪｏｉｎトランザクションがブロックチェーンに含まれる場合に、自身に割り当てられているＣｏｉｎＪｏｉｎトランザクションをブロードキャストしなかった悪意あるサブグループ内の一部又は全ての参加者は、全ての局所的ダイジェストを知っており、従って、各参加者のデポジットトランザクションで使用されているファンドをアンロックするのに必要な大域的ダイジェストを再構成することができる可能性がある。その場合に、悪意ある参加者が、そのグループに割り当てられているＣｏｉｎＪｏｉｎトランザクションにその入力を付加していないのに、他のＣｏｉｎＪｏｉｎトランザクションに含まれているその出力アドレスでコインを受け取るシナリオが想像され得る（カテゴリ３）。ΔＴの後、そのデポジットトランザクションで送られたＵＴＸＯが既に請求されている場合を除いて、その局所的ダイジェストを知っている参加者は、大域的ダイジェストを再構成し、当該ＵＴＸＯを収集することができる。
【０１４１】
例えば、４人の参加者に基づく例において、第３参加者がＴＣ２に署名しない場合を考える。
【０１４２】
時点Ｔｌ＜ｔ＜ΔＴで、４人の参加者の差引残高は、次の通りである：
【表１】
2021531689.tif 000013
【０１４３】
次いで、ディーラーは、値の組｛ω３，ω１｝を明らかにする。これは、第１参加者が数量ｃ３→１＝ｙ１＋ω３を計算することを可能にし、一方、第２参加者は、Ｃ１→２＝ｙ２＋ω１を計算する。従って、第１参加者は、Ｄｘ３におけるＵＴＸＯをアンロックすることができ、一方、第２参加者は、Ｄｘ１におけるＵＴＸＯをアンロックすることができる。
【０１４４】
時点ΔＴ＜ｔ＜ΔＴ’で、４人の参加者の差引残高は、次のように変化している：
【表２】
2021531689.tif 000014
【０１４５】
ΔＴ’が経過した後、残り２つのデポジットトランザクションＤｘ２及びＤｘ４におけるＵＴＸＯは、それらの元の創作者によって使用され得る。第２及び第４参加者は、彼らのデポジットを再請求する。
【０１４６】
時点ｔ＞ΔＴ’で、４人の参加者の差引残高は、次のように回復される：
【表３】
2021531689.tif 000015
【０１４７】
デポジットトランザクションごとに使用されるビットコインの量、すなわち、ｙＢＴＣは、ＣｏｉｎＪｏｉｎトランザクションで混合された量ｘＢＴＣに極めて近いはずであり、それにより、参加者ごとの総差引残高は、ＣｏｉｎＪｏｉｎトランザクションが全てブロードキャストされるか否かにかかわらずゼロに近い。ＣｏｉｎＪｏｉｎトランザクション及びデポジットトランザクションに含まれているマイナーの異なる手数料に起因する小さい差が存在し得る。
【０１４８】
図１１は、実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによって実行される結果として、キー共有を実行し、マルチＣｏｉｎＪｏｉｎトランザクションでの使用のために集積木を構築するプロセスの例を表す。フローチャートは、各参加者コンピュータシステムＵｉが要素ｅｉを生成し、要素のハッシュｈ（ｅｉ）及びソルトｗｉをディーラーへ送るブロック１１０２から開始するプロセス１１００を表す。ブロック１１０４で、ディーラーは、トラップドア情報ｓを選択し、集積木を生成する。ブロック１１０６で、トラップドア情報ｓは、ディーラーによって秘密に保たれるが、ディーラーは、値がトラップドア情報ｓから導出された楕円曲線上の点である
【数１２】
2021531689.tif 000016
を公開する。ここで、ｎは、参加者の数又は木のリーフの数である。ブロック１１０８で、ディーラーは、公開キーＱ＝ｖ×ｇを生成し、公開キーを公開する（ｖ＝ｘＤ）。ブロック１１１０で、ディーラーは、公開キーＥＤ＝ｋＤ×ｇを公開する。ブロック１１１２で、各参加者Ｕｉは、彼らの公開キーＥｉ＝ｋｉ×ｇ及びＰｉ＝ｙｉ×ｇを公開する。
【０１４９】
図１２は、実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによって実行される結果として、マルチＣｏｉｎＪｏｉｎトランザクションのために出力アドレスを再配置し、デポジットを生成し、ＣｏｉｎＪｏｉｎトランザクションを生成するプロセスの例を表す。プロセス１２００は、マルチＣｏｉｎＪｏｉｎトランザクションの各参加者が、図４に表されているように、彼らの出力アドレスのシャッフルを実行するブロック１２０２から開始する。ブロック１２０４で、シャッフルされた出力アドレスの組は、ディーラーコンピュータシステムへ供給される。ブロック１２０６で、ディーラーは、シャッフルされた出力アドレスを複数のサブセットに分け、各サブセットがビットコイントランザクションになる。ブロック１２０８で、各参加者は、上述されたように彼らの特定のロッキングスクリプトを生成し、そのデポジットトランザクションにおいてある量のビットコインをコミットして、マルチＣｏｉｎＪｏｉｎトランザクションに資金を出す。
【０１５０】
ブロック１２１０で、ディーラーは、デポジットが全ての参加者によってコミットされたかどうかを判定する。全ての参加者が彼らのデポジットをコミットしていない場合には、タイムアウト後に、実行はブロック１２１２へ進み、マルチＣｏｉｎＪｏｉｎトランザクションは中止される。ブロック１２１４で、ディーラーコンピュータシステムは、サブセットごとにＣｏｉｎＪｏｉｎトランザクションを生成し、次いで、各トランザクションをそのサブセット内の第１参加者へ送る。ブロック１２１６で、参加者は、参加者間でトランザクションをルーティングし、各参加者はトランザクションに署名する。ブロック１２１８で、ディーラーは、何らかの変換又は補償が必要とされるかどうかを判定し、図１３で記載されるように、関連する動作を実行する。
【０１５１】
図１３は、実施形態において、ディーラーコンピュータシステム及び１つ以上の参加者コンピュータシステムによって実行される結果として、マルチＣｏｉｎＪｏｉｎトランザクションのために返還及び補償を処理するプロセスの例を表す。プロセス１３００は、ブロック１３０２から開始する。決定ブロック１３０４で、ディーラーコンピュータシステムは、全てのトランザクションがブロードキャストされブロックチェーンにコミットされたかどうかを判定する。全てのトランザクションがブロードキャストされている場合には、実行は決定ブロック１３０６へ進む。決定ブロック１３０６で、第１経過時間が経過していない場合には、実行は決定ブロック１３０４へ戻る。第１経過時間が経過している場合には、実行はブロック１３０８へ進み、参加者は大域的ダイジェストを決定し、デポジットにおいてコミットされたファンドをアンロックし、そして、実行はブロック１３１０へ進み、プロセスは完了する。
【０１５２】
決定ブロック１３０４で、全てのトランザクションがブロードキャストされブロックチェーンにコミットされていないとディーラーコンピュータシステムが決定する場合には、実行はブロック１３１２へ進み、ディーラーは、出力アドレスが正常なデポジットに含まれているが、動作に問題があるサブセットに含まれている参加者のためのソルトを公開する。ブロック１３１４で、トランザクションにおいて差引残高がマイナスである参加者は、彼らの秘密キーを決定し、彼らのデポジットを回収するために支払われる如何なる補償もアンロックする。決定ブロック１３１６で、システムは、ブロック１３１８へ進む前に、第１経過時間よりも長い第２経過時間が経過するまで待機する。ブロック１３１８で、残りの参加者は、彼らのデポジットで使用されているファンドをアンロックし、そして、実行はブロック１３１０へ進み、プロセスは完了する。
【０１５３】
図１４は、本開示の少なくとも１つの実施形態を実施するために使用され得るコンピュータデバイス１４００の実例となる略ブロック図である。様々な実施形態で、コンピュータデバイス１４００は、先に例示及び記載されたシステムのいずれかを実施するために使用され得る。例えば、コンピュータデバイス１４００は、データサーバ、ウェブサーバ、可搬型コンピュータデバイス、パーソナルコンピュータ、又は任意の電子計算デバイスとしての使用のために構成され得る。図１４に示されるように、コンピュータデバイス１４００は、１つ以上のプロセッサ１４０２を含む。実施形態において、プロセッサ１４０２は、バスサブシステム１４０４を介して多数の周辺サブシステムと通信するよう構成されかつそれらへ通信上結合されている。いくつかの実施形態で、それらの周辺サブシステムは、メモリサブシステム１４０８及びファイル／ディスク記憶サブシステム１４１０を有する記憶サブシステム１４０６と、１つ以上のユーザインターフェース入力デバイス１４１２と、１つ以上のユーザインターフェース出力デバイス１４１４と、ネットワークインターフェースサブシステム１４１６とを含む。そのような記憶サブシステム１４０６は、情報の一時的な又は長期の記憶のために使用されてよい。
【０１５４】
いくつかの実施形態で、バスサブシステム１４０４は、コンピュータデバイス１４００の様々なコンポーネント及びサブシステムが意図されたように互いと通信することを可能にするメカニズムを提供する。バスサブシステム１４０４は単一バスとして概略的に示されているが、バスサブシステムの代替の実施形態は多数のバスを利用する。いくつかの実施形態で、ネットワークインターフェースサブシステム１４１６は、他のコンピュータデバイス及びネットワークへのインターフェースを提供する。ネットワークインターフェースサブシステム１４１６は、いくつかの実施形態において、他のシステムからデータを受信しかつコンピュータデバイス１４００から他のシステムへデータを送信するインターフェースとして働く。いくつかの実施形態で、バスサブシステム１４０４は、詳細、検索語、などのようなデータを送るために利用される。
【０１５５】
いくつかの実施形態で、ユーザインターフェース入力デバイス１４１２は、キーボード；組み込みマウス、トラックボール、タッチパッド、若しくはグラフィクスタブレットなどの指示デバイス；スキャナ；バーコードスキャナ；ディスプレイに組み込まれているタッチスクリーン；音声認識システム、マイクロホンなどの音声入力デバイス；及び他のタイプの入力デバイス、などの１つ以上のユーザ入力デバイスを含む。
【０１５６】
いくつかの実施形態で、コンピュータデバイス１４００は、少なくとも１つのローカルクロック１４２４を含む。ローカルクロック１４２４は、いくつかの実施形態では、特定の開始日から発生したディックの数を表すカウンタであり、いくつかの実施形態では、コンピュータデバイス１４００内に内蔵される。様々な実施形態で、ローカルクロック１４２４は、コンピュータデバイス１４００のプロセッサ及びコンピュータデバイス１４００に含まれているサブシステムにおいてデータ転送を特定のクロックパルスで同期させるために使用され、コンピュータデバイス１４００とデータセンター内の他のシステムとの間で同期動作を協調させるために使用され得る。他の実施形態では、ローカルクロックは、プログラム可能なインターバルタイマである。
【図１】
2021531689.tif 000017
【図２】
2021531689.tif 000018
【図３】
2021531689.tif 000019
【図４】
2021531689.tif 000020
【図５】
2021531689.tif 000021
【図６】
2021531689.tif 000022
【図７】
2021531689.tif 000023
【図８】
2021531689.tif 000024
【図９】
2021531689.tif 000025
【図１０】
2021531689.tif 000026
【図１１】
2021531689.tif 000027
【図１２】
2021531689.tif 000028
【図１３】
2021531689.tif 000029
【図１４】
2021531689.tif 000030