JP7743451B2 - ブロックチェーンネットワークにおけるデータを妥当性確認する方法及び装置 - Google Patents

Description

本開示は、ブロックチェーンネットワーク、特にブロックチェーンネットワーク内のデータを妥当性確認するための方法及び装置、例えばブロック内のトランザクションの存在及びインデックスを妥当性確認することに関する。

ブロックチェーンとは、分散型ピアツーピア（P２P）ネットワーク（以下で「ブロックチェーンネットワーク」とも呼ばれる）内の複数のノードの各々において、ブロックチェーンの重複コピーが維持され広く公表される、分散データ構造の形態を指す。ブロックチェーンは、データのブロックのチェーンで形成され、各ブロックは１つ以上のトランザクションを含む。所謂「コインベーストランザクション」以外の各トランザクションは、シーケンス内の先行するトランザクションをポイントする。シーケンスは、１つ以上のコインベーストランザクションまで１つ以上のブロックに跨がってよい。コインベーストランザクションは以下で議論される。ブロックチェーンネットワークに提出されるトランザクションは、新しいブロックに含まれる。新しいブロックは、「マイニング」として知られる処理により生成される。「マイニング」は、複数のノードの各々が「proof-of-work」を実行するために競争する、つまり、ブロックチェーンの新しいブロックに含まれることを待っている順序付き及び妥当性確認済みの保留中のトランザクションの定義されたセットの提示に基づき、暗号パズルを解くことを含む。留意すべきことに、ブロックチェーンはノードにおいてプルーニング（pruned）されてよく、ブロックの公開はブロックヘッダのみの公開を通じて達成できる。

ブロックチェーン内のトランザクションは、以下：デジタルアセット（つまり、多数のデジタルトークン）を運ぶこと、仮想台帳又はレジストリの中のジャーナルエントリのセットを順序付けること、タイムスタンプエントリを受信し処理すること、及び／又はインデックスポインタを時系列にすること、のうちの１つ以上を実行するために使用される。ブロックチェーンの上に追加の機能をレイヤ化するために、ブロックチェーンを利用することもできる。ブロックチェーンプロトコルは、トランザクション内のデータに追加のユーザデータ又はインデックスを格納できるようにし得る。単一トランザクション内に格納できる最大データ容量に対する予め指定された限度は存在しない。従って、より複雑なデータを組み込むことができる。例えば、これは、ブロックチェーン内に電子文書（electronic document）、或いはオーディオ若しくはビデオデータを格納するために使用され得る。

ブロックチェーンネットワークのノード（「マイナー」と呼ばれることがある）は、以下に説明する分散型トランザクション登録及び検証処理を実行する。つまり、この処理の間、ノードは、トランザクションの妥当性確認を行い、それらをブロックテンプレイトに挿入し、それに対して有効なproof-of-work解を特定しようと試みる。有効な解が見付かると、新しいブロックはネットワークの他のノードへと伝播され、それにより、各ノードがブロックチェーンに新しいブロックを記録できるようになる。トランザクションをブロックチェーンに記録させるために、ユーザ（例えば、ブロックチェーンクライアントアプリケーション）は、伝播させるために、ネットワークのノードの１つにトランザクションを送信する。トランザクションを受信したノードは、proof-of-work解を見付けるために競争し、妥当性確認されたトランザクションを新しいブロックに組み込む。各ノードは、トランザクションが有効であるための１つ以上の条件を含む同じノードプロトコルを実施するよう構成される。無効なトランザクションは、伝播されず、ブロックに組み込まれることもない。トランザクションが妥当性確認され、それによってブロックチェーンに受け入れられたと仮定すると、（任意のユーザデータを含む）トランザクションは、従って、不変の公開レコードとしてブロックチェーンネットワークの各ノードに登録されインデックスされたままである。

最新のブロックを生成するためにproof-of-workパズルを解くことに成功したノードは、標準的に、デジタルアセットの新しい量、つまりトークンの数を生成する「コインベーストランザクション（coinbase transaction）」と呼ばれる新しいトランザクションにより報酬を受ける。無効なトランザクションの検出及び拒否は、ネットワークのエージェントとして動作し及び不法行為を報告及び阻止するよう奨励される競合ノードの動作により実施される。情報の広範な公開により、ユーザはノードの性能を継続的に監査できる。単なるブロックヘッダの公開により、参加者はブロックチェーンの現下の完全性を保証できる。

「アウトプットベースの」モデル（UTXOに基づくモデルと呼ばれることもある）では、所与のトランザクションのデータ構造は、１つ以上のインプット及び１つ以上のアウトプットを含む。任意の使用可能アウトプットは、先行するトランザクションシーケンスから導出可能なデジタルアセットの量を指定する要素を含む。使用可能アウトプットは、時にUTXO（unspent transaction output、未使用トランザクションアウトプット）と呼ばれる。アウトプットは、アウトプットの将来の償還（redemption）のための条件を指定するロックスクリプトを更に含んでよい。ロックスクリプトは、デジタルトークン又はアセットを妥当性確認し及び移転するために必要な条件を定義する述部（predicate）である。（コインベーストランザクション以外の）トランザクションの各インプットは、先行するトランザクション内のそのようなアウトプットへのポインタ（つまり参照）を含み、ポイントされたアウトプットのロックスクリプトをアンロックするためのアンロックスクリプトを更に含んでよい。トランザクションのペアが第１トランザクション及び第２トランザクション（又は「ターゲット」トランザクション）とラベル付けできると考える。第１トランザクションは、デジタルアセットの量を指定する、及びアウトプットをアンロックする１つ以上の条件を定義するロックスクリプトを含む、少なくとも１つのアウトプットを含む。第２ターゲットトランザクションは、第１トランザクションのアウトプットへのポインタと、第１トランザクションのアウトプットをアンロックするためのアンロックスクリプトと、を含む少なくとも１つのインプットを含む。

このようなモデルでは、第２ターゲットトランザクションがブロックチェーンで伝播され記録されるブロックチェーンネットワークに送られるとき、各ノードで適用される有効性の基準の１つは、アンロックスクリプトが第１トランザクションのロックスクリプトで定義された１つ以上の条件のすべてを満たすことである。もう１つは、第１トランザクションのアウトプットが、別の前の有効なトランザクションによって未だ償還されていないことである。これらの条件のうちのいずれかに従いターゲットトランザクションが無効であると分かった任意のノードは、該トランザクションを（有効なトランザクションとして）伝搬させず（しかし、無効なトランザクションを登録する場合がある）、ブロックチェーンに記録させるために新しいブロックに含めることもしない。

トランザクションモデルの代替のタイプは、アカウントに基づくモデルである。この場合、各トランザクションは、過去の一連のトランザクションにおいて、先行するトランザクションのUTXOに戻って参照することによって移転される量を定義するのではなく、絶対的な口座（アカウント）残高を参照することによって移転される。すべてのアカウントの現在の状態は、ブロックチェーンと分離してノードによって保管され、絶えず更新される。

ブロックチェーンネットワークが多数の参加者にとって実用的に役立つように、エンドユーザ装置はクライアントアプリケーション（「ウォレット」又はSimplified Payment Verification （SPV）ソフトウェアと呼ばれることもある）を操作することがある。このようなクライアントアプリケーションは、完全なブロックチェーンノードの機能を備えておらず、ブロックチェーンの完全なコピーを持たない。エンドユーザ装置は、クライアントアプリケーションを通じて、特定のトランザクションがブロックチェーンに存在すること、つまりブロックに含まれていること、つまり「確認された」ことを証明するデータの要求をブロックチェーンノードに送信することができる。そのようなデータを提供し、エンドユーザ装置又は他のノードがブロックにトランザクションが含まれていることを証明したり、ブロックの他の機能を証明したりできるようにするための改善された方法と装置があると有利である。

例として、本願の例示的な実施形態を示す以下の添付の図面を参照する。

ブロックチェーンを実装するための例示的なシステムを示す。

トランザクションプロトコルの例を示している。

ライアントアプリケーションの例示的な実装を示している。

ライアントアプリケーションの例示的なユーザインタフェースを示している。

ブロックチェーンノードのノードソフトウェアの例を示している。

Merkleツリーの例を示す。

「部分」Merkleツリーの例を示す。

Merkleパスの例を示す。

フローチャート形式で、ブロックチェーンデータを妥当性確認する方法の例を示す。

図中の同様の参照符号は同様の要素及び特徴を示すために使用される。

一態様では、ブロックチェーン内のデータの妥当性を決定する、コンピュータが実施する方法が提供され得る。方法は、
リモートノードから、ブロック内のトランザクションのインデックスと、Merkleプルーフのための順序付けられたハッシュのセットを受信するステップと、
Merkleツリーの最下位レベルから開始して、最上位レベルに到達するまで、前記Merkleツリーの各レベルで、
前記順序付けられたハッシュのセットから提供されたハッシュを順に選択するステップと、
前記提供されたハッシュと現在のレベルの計算されたハッシュを、前記インデックスに基づいて決定された順序で連結するステップと、
前記連結をハッシュして上のレベルの計算されたハッシュを見つけるステップと、
前記インデックス、及び前記計算されたハッシュと前記順序付けられたハッシュのセットから提供された対応するハッシュとの各ペアから、前記トランザクションが前記ブロック内の最後のトランザクションであるかどうかを決定するステップと、
前記最上位レベルの計算されたハッシと前記ブロックのヘッダ内のMerkleルートを比較するステップと、
前記比較するステップ及び決定するステップの結果を出力するステップと、
を含んでよい。

幾つかの実装では、受信した前記インデックスが、前記ブロック内の順序付けられたトランザクションのセットの中の前記トランザクションの位置を示す位置インデックスであってよい。幾つかの実装では、前記方法は、最下位レベルより上の各レベルについて、モジュロ２より下のレベルのインデックスに基づいて、当該レベルのインデックスを決定するステップ、を更に含んでよい。

幾つかの実装では、前記トランザクションが前記ブロック内の最後のトランザクションであると決定することは、最上位レベルの計算されたハッシュ以外の各計算されたハッシュが、前記Merkleツリー内の右側の要素であると決定することを含んでよい。

幾つかの実装では、前記トランザクションが前記ブロック内の最後のトランザクションであると決定することは、ペアにされた左側の要素である任意の計算されたハッシュについて、対応する提供されたハッシュが前記計算されたハッシュと等しいと決定することを含んでよい。

幾つかの実装では、前記トランザクションが前記ブロック内の最後のトランザクションであるかどうかを決定することは、少なくとも１つの計算されたハッシュが左側の要素であり、それに対応する提供されたハッシュが該少なくとも１つの計算されたハッシュと等しくないと決定することに基づいて、前記トランザクションが前記ブロック内の最後のトランザクションではないことを決定することを含んでよい。

幾つかの実装では、少なくとも１つの計算されたハッシュが右側の要素であり、それに対応する提供されたハッシュが該少なくとも１つの計算されたハッシュと等しいと決定することに基づいて、インデックスが無効であると決定するステップ、を更に含んでよい。

幾つかの実装では、前記方法は、最初に、前記トランザクションの識別子を持つMerkleプルーフデータの要求を前記リモートノードに送信するステップ、を更に含んでよい。幾つかの実装では、受信するステップは、バージョンフィールドと、前記インデックスを含むインデックスフィールドと、前記順序付けられたハッシュのセットを含むデータ構造を含むパスフィールドと、を含むメッセージを受信するステップを含む。

幾つかの実装では、前記Merkleツリーの最下位レベルの計算されたハッシュが、前記トランザクションのトランザクション識別子であってよい。

幾つかの実装では、前記インデックスに基づいて決定される順序は、前記計算されたハッシュが、対応する提供されたハッシュとのペアの中で、左側の要素であるか右側の要素であるかを決定することを含んでよく、前記計算されたハッシュが左側の要素であるか右側の要素であるかを決定することは、当該レベルのインデックスがインデックスのモジュロ２に基づいて偶数であるか奇数であるかを決定することに基づく。

幾つかの実装では、前記順序付けられたハッシュのセットは、重複したハッシュ値を含む代わりに、重複したハッシュをシグナリングする構文要素を含む。

別の態様では、ブロックチェーン内のノードを実装するコンピューティング装置が提供されてよい。前記コンピューティング装置は、メモリと、１つ以上のプロセッサと、実行されると前記プロセッサに本願明細書に記載の方法のうちの１つ以上を実行させるコンピュータ実行可能命令と、を含んでよい。

更に別の態様では、プロセッサ実行可能命令を格納しているコンピュータ可読媒体であって、前記プロセッサ実行可能命令は、１つ以上のプロセッサにより実行されると、前記プロセッサに本願明細書に記載の方法のうちの少なくとも１つを実行させる、コンピュータ可読媒体が提供され得る。

本開示の他の例示的な実施形態は、図面と関連して以下の詳細な説明を読むことから当業者に明らかになるだろう。

本願では、用語「及び／又は」は、列挙された要素単独、任意の一部の組合せ、又は要素の全部、を含む列挙された要素の全部の可能な組合せ及び一部の組合せをカバーすることを意図しており、必ずしも追加要素を排除しない。

本願では、用語「．．．又は．．．のうちの少なくとも１つ」は、列挙された要素単独、任意の一部の組合せ、又は要素の全部、を含む列挙された要素の全部の可能な組合せ及び一部の組合せをカバーすることを意図しており、必ずしも追加要素を排除せず、必ずしも全部の要素を必要としない。

＜例示的なシステムの概要＞
図１は、ブロックチェーン１５０を実装するための例示的なシステム１００を示す。システム１００は、典型的にはインターネットのような広域インターネットワークであるパケット交換ネットワーク１０１を含んでよい。パケット交換ネットワーク１０１は、パケット交換ネットワーク１０１内にピアツーピア（P２P）ネットワーク１０６を形成するように配置され得る複数のブロックチェーンノード１０４を含む。図示されないが、ブロックチェーンノード１０４は、ほぼ完全なグラフとして配置されてよい。各ブロックチェーンノード１０４は、従って、他のブロックチェーンノード１０４と高度に結合される。

各ブロックチェーンノード１０４は、ピアのコンピュータ機器を含み、ノード１０４のうちの異なるノード１０４は異なるピアに属する。各ブロックチェーンノード１０４は、１つ以上のプロセッサ、例えば、１つ以上の中央処理装置（CPU）、アクセラレータプロセッサ、特定用途向けプロセッサ、及び/又はフィールドプログラマブルゲートアレイ（FPGA）、及び特定用途向け集積回路（ASIC）のような他の機器、により実装される処理機器を含む。各ノードはまた、メモリ、すなわち、非一時的コンピュータ読み取り可能媒体又は媒体の形態のコンピュータ読み取り可能記憶装置を備える。メモリは、１つ以上のメモリ媒体、例えば、ハードディスクなどの磁気媒体、固体ドライブ（solid-state drive （SSD））、フラッシュメモリ又はEEPROMなどの電子媒体、及び/又は光ディスクドライブなどの光学的媒体を使用する１つ以上のメモリユニットを含む。

ブロックチェーン１５０は、データのブロック１５１のチェーンを含み、ブロックチェーン１５０の各々のコピーは、分散型又はブロックチェーンネットワーク１６０内の複数のノード１０４の各々において維持される。上述のように、ブロックチェーン１５０のコピーを維持することは、必ずしも、ブロックチェーン１５０全体を格納することを意味しない。代わりに、各ブロックチェーンノード１５０が各ブロック１５１のブロックヘッダ（後述する）を格納する限り、ブロックチェーン１５０からデータを取り除くことができる。チェーン内の各ブロック１５１は、１つ以上のトランザクション１５２を含む、ここでは、この文脈におけるトランザクションは、一種のデータ構造を表す。データ構造の性質は、トランザクションモデル又はスキームの一部として使用されるトランザクションプロトコルのタイプに依存する。所与のブロックチェーンは、全体を通して、１つの特定のトランザクションプロトコルを使用する。１つの一般的なタイプのトランザクションプロトコルでは、各トランザクション１５２のデータ構造は、少なくとも１つのインプット及び少なくとも１つのアウトプットを含む。各アウトプットは、資産としてのデジタルアセットの量を表す量を指定する。この例では、アウトプットが暗号的にロックされているのはユーザ１０３である（ロックを解除し、それによって償還又は使用するために、そのユーザの署名又は他の解を必要とする）。各インプットは、先行するトランザクション１５２のアウトプットを指し示し、それによって、トランザクションをリンクする。

各ブロック１５１は、また、ブロック１５１への逐次的順序を定義するように、チェーン内の先に生成されたブロック１５１を遡ってポイントするブロックポインタ１５５を含む。（コインベーストランザクション以外の）各トランザクション１５２は、トランザクションのシーケンスに順序を定義するために、前のトランザクションへのポインタを有する（注：トランザクション１５２のシーケンスは、分岐することが許される）。ブロック１５１のチェーンは、チェーンの第１ブロックであったジェネシスブロック（genesis block （Gb））１５３にまで戻る。チェーン１５０の初期に１つ以上のオリジナルトランザクション１５２は、先行するトランザクションではなくジェネシスブロック１５３を指し示した。

ブロックチェーンノード１０４の各々はトランザクション１５２を他のブロックチェーンノード１０４へ転送し、それにより、ネットワーク１０６に渡りトランザクション１５２を伝播させるよう構成される。各ブロックチェーンノード１０４は、ブロック１５１を生成し、同じブロックチェーン１５０の各々のコピーを自身の各々のメモリに格納するよう構成される。各ブロックチェーンノード１０４はまた、ブロック１５１に組み込まれるのを待つトランザクション１５２の順序付きセット１５４を維持する。順序付きセット１５４は、時に「メモプール（mempool）」と呼ばれる。この用語は、本願明細書では、任意の特定のブロックチェーン、プロトコル、又はモデルに限定されない。それは、ノード１０４が有効であるとして受け付けた、及びノード１０４が同じアウトプットを使用しようと試みる他のトランザクションを受け付けないよう義務付けられたトランザクションの順序付きセットを表す。

所与の現在のトランザクション１５２jにおいて、インプット（又はその各々）は、トランザクションのシーケンスの中の先行トランザクション１５２iのアウトプットを参照するポインタを含む、このアウトプットが現在のトランザクション１５２jにおいて償還されるか又は「消費される（spent）」ことを指定する。一般に、先行するトランザクションは、順序付きセット１５４又は任意のブロック１５１内の任意のトランザクションであり得る。先行するトランザクション１５２iは、必ずしも、現在のトランザクション１５２jが生成された又はネットワーク１０６へ送信されたときに存在する必要はないが、先行するトランザクション１５２iは、現在のトランザクションが有効であるために存在し妥当性確認されている必要がある。従って、本願明細書で「先行する」は、ポインタによりリンクされた論理的シーケンスの中で先行するものを表し、必ずしも時系列の中での生成又は送信の時間を表さない。従って、それは、必ずしも、トランザクション１５２i,１５２jが順不同で生成され又は送信されることを排除しない（以下の親のない（orphan）トランザクションに関する議論を参照する）。先行するトランザクション１５２iは、等しく、祖先（antecedent）又は先行（predecessor）トランザクションと呼ばれ得る。

現在のトランザクション１５２jのインプットは、インプット認可、例えば先行するトランザクション１５２iのアウトプットがロックされているユーザ１０３aの署名も含む。次に、現在のトランザクション１５２jのアウトプットは、新しいユーザ又はエンティティ１０３bに暗号的にロックすることができる。従って、現在のトランザクション１５２jは、先行するトランザクション１５２iのインプットに定義された量を、現在のトランザクション１５２jのアウトプットに定義された新しいユーザ又はエンティティ１０３bに移転することができる。ある場合には、トランザクション１５２は、複数のユーザ又はエンティティ間でインプット量を分割するために複数のアウトプットを有してもよいエンティティ（そのうちの１つは、お釣りを与えるために、元のユーザ又はエンティティ１０３aであってもよい）。幾つかの場合には、トランザクションが複数のインプットを有し、１つ以上の先行するトランザクションの複数のアウトプットから量をまとめ、現在のトランザクションの１つ以上のアウトプットに再分配することもできる。

ビットコインのようなアウトプットに基づくトランザクションプロトコルによると、ユーザ又はマシンのようなエンティティ１０３は、新しいトランザクション１５２jに作用したいとき、エンティティは新しいトランザクションを自身のコンピュータ端末１０２から受信側へ送信する。エンティティ又は受信側は、結局、このトランザクションをネットワーク１０６のブロックチェーンノード１０４のうちの１つ以上（これらは、今日では、標準的にサーバ又はデータセンタであるが、原理的に他のユーザ端末も可能である）へと送信する。幾つかの例では、新しいトランザクション１５２jに作用するエンティティ１０３が、トランザクションを、受信側ではなくブロックチェーンノード１０４のうちの１つ以上へと送信し得ることも排除されない。トランザクションを受信するブロックチェーンノード１０４は、各ブロックチェーンノード１０４に適用されるブロックチェーンノードプロトコルに従って、トランザクションが有効であるかどうかをチェックする。ブロックチェーンノードプロトコルは、典型的には、ブロックチェーンノード１０４に、新しいトランザクション１５２j内の暗号署名が、トランザクション１５２の順序付きシーケンスの中の前のトランザクション１５２iに依存する、期待される署名と一致することをチェックすることを要求する。このようなアウトプットに基づくトランザクションプロトコルの場合、これは、新しいトランザクション１５２jのインプットに含まれるエンティティ１０３の暗号署名又は他の認証が、新しいトランザクションが割り当てる先行するトランザクション１５２jのアウトプットに定義された条件と一致することをチェックすることを含んでよく、この条件は、典型的には、新しいトランザクション１５２jのインプット内の暗号署名又は他の認証が、新しいトランザクションのインプットがリンクされた前のトランザクション１５２iのアウトプットをアンロックすることを少なくともチェックすることを含む。条件は、先行するトランザクション１５２iのアウトプットに含まれるスクリプトにより少なくとも部分的に定義されてよい。あるいは、単にブロックチェーンノードプロトコルだけで固定することもできるし、あるいは、これらの組み合わせによることもある。いずれにせよ、新しいトランザクション１５２jが有効であれば、ブロックチェーンノード１０４は、新しいトランザクションをブロックチェーンネットワーク１０６内の１つ以上の他のブロックチェーンノード１０４に転送する。これらの他のブロックチェーンノード１０４は、同じノードプロトコルに従って同じテストを適用し、新しいトランザクション１５２jを１つ以上のさらなるノード１０４に転送し、以下で同様である。このようにして、新しいトランザクションは、ブロックチェーンノード１０４のネットワーク全体に伝播される。

アウトプットベースのモデルでは、与えられ割り当てアウトプット（例えば、UTXO）が割り当てられるかどうかの定義は、ブロックチェーンノードプロトコルに従って別の今後の（onward）トランザクション１５２jのインプットによって既に有効に償還されているかどうかである。トランザクションが有効であるための別の条件は、それが割り当て又は償還を試みる先行するトランザクション１５２iのアウトプットが、別のトランザクションによって未だ割り当て/償還されていことである。ここでも、有効でない場合、トランザクション１５２jは、（無効であるとしてフラグが立てられ変更するために伝播されない限り）ブロックチェーン１５０に伝播又は記録されない。これは、取引者が同じトランザクションのアウトプットを複数回割り当てようとする二重支出を防ぐ。一方、アカウントベースモデルは、口座残高を維持することによって、二重支出を防ぐ。この場合も、トランザクションの順序が定義されているため、口座残高は、一度に単一の定義された状態を有する。

妥当性確認トランザクションに加えて、ブロックチェーンノード１０４は、また、「proof -of -work」により支えられているマイニングと呼ばれるプロセスで、トランザクションのブロックを最初に作成するために競合する。ブロックチェーンノード１０４では、ブロックチェーン１５０に記録されたブロック１５１にまだ現れていない有効なトランザクションの順序付きセット１５４に新しいトランザクションが追加される。ブロックチェーンノードは、次に、暗号パズルを解くことを試みることにより、トランザクションの順序付きセット１５４からトランザクション１５２の新しい有効なブロック１５１を組み立てるために競争する。これは、典型的には、ノンス（nonce）がトランザクションの順序付きセット１５４の表現と連結され、ハッシュされるときに、ハッシュのアウトプットが所定の条件を満たすような「ノンス」値を探すことを含む。例えば、所定の条件は、ハッシュのアウトプットが、所定の数の先頭ゼロを有することであってもよい。これは、単に１つの特定の種類のproof-of-workパズルであり、他の種類が排除されないことに留意する。ハッシュ関数の特性は、インプットに関して予測不可能なアウトプットを持つことである。従って、この探索は、ブルートフォースによってのみ実行することができ、従って、パズルを解決しようとしている各ブロックチェーンノード１０４において、相当量の処理リソースを消費する。

パズルを解いた第１ブロックチェーンノード１０４は、これをネットワーク１０６に通知し、その解を証明として提供する。この解は、ネットワーク内の他のブロックチェーンノード１０４によって簡単にチェックすることができる（ハッシュに対する解が与えられれば、ハッシュのアウトプットが条件を満たすことを確認することは簡単である）。第１ブロックチェーンノード１０４は、該ブロックを受け入れる閾値の他のノードの合意に、ブロックを伝播させ、従ってプロトコルルールを実施する。トランザクションの順序付きセット１５４は、次に、ブロックチェーンノード１０４の各々により、ブロックチェーン１５０内の新しいブロック１５１として記録されるようになる。また、新しいブロック１５１nにはブロックポインタ１５５が割り当てられ、チェーン内で前に作成されたブロック１５１n-１を指すようになっている。proof-of-work解を生成するために必要とされる例えばハッシュの形式の有意な量の労力が、ブロックチェーンプロトコルのルールに従うという第１ノード１０４の意図をシグナリングする。そのようなルールは、前に妥当性確認されたトランザクションと同じアウトプットを割り当てる場合に有効としてトランザクションを受け付けないこと、或いは二重支払いとして知られいることを含む。一旦生成されると、ブロック１５１は、ブロックチェーンネットワーク１０６内のブロックチェーンノード１０４の各々で認識され、維持されるので、修正することができない。また、ブロックポインタ１５５は、ブロック１５１に順序を課す。トランザクション１５２は、ネットワーク１０６内の各ブロックチェーンノード１０４において順序付きブロックに記録されるので、これは、トランザクションの不変の公開台帳を提供する。

パズルを解決するために常に競争している異なるブロックチェーンノード１０４は、いつ解を探し始めたか、又はトランザクションが受信された順序によって、いつでも未だ公開されていないトランザクションの順序付きセット１５４の異なるスナップショットに基づいてパズルを解いているかもしれないことに留意する。パズルを解く者は誰でも、最初に次の新しいブロック１５１nに含まれるトランザクション１５２を定義し、その順序で、未公開のトランザクションの現在のセット１５４が更新される。そして、ブロックチェーンノード１０４は、新たに定義された未公開トランザクションの現在の順序付きセット１５４からブロックを作り出すために、競争を続ける。また、生じ得る「分岐（フォーク、fork）」を解決するためのプロトコルも存在する。これは、２つのブロックチェーンノード１０４が互いに非常に短い時間内にパズルを解き、ブロックチェーンの矛盾したビューがノード１０４の間で伝播する場合である。要するに、分岐の枝が伸びるときは常に、最長のものが最終的なブロックチェーン１５０になる。これは、同じトランザクションが両方の分岐に現れるので、ネットワークのユーザ又はエージェントに影響しないことに留意する。

ビットコインブロックチェーン（及び殆どの他のブロックチェーン）によると、新しいブロック１０４を構成するのに成功したノードは、デジタルアセットの所定量を分配する新しい特別な種類のトランザクションの中でデジタルアセットの承認された量を割り当てる能力を与えられる（１人のエージェント又はユーザから別のエージェント又はユーザへとデジタルアセットの量を移転するエージェント間又はユーザ間トランザクションと異なる）。この特別な種類のトランザクションは、通常、「コインベーストランザクション」と呼ばれるが、「開始（initiation）トランザクション」とも呼ばれることがある。それは標準に新しいブロック１５１nの第１トランザクションを形成する。proof-of-workは、この特別なトランザクションが後に償還できるように、新しいブロックを構成したノードがプロトコルルールに従うことを意図していることをシグナリングする。ブロックチェーンプロトコルルールは、この特別なトランザクションが償還できる前に、満期、例えば１００ブロックを必要としてよい。通常の（非生成）トランザクション１５２は、そのアウトプットの１つに追加のトランザクション料を指定し、そのトランザクションが公開されたブロック１５１nを生成したブロックチェーンノード１０４に更に報酬を与えることが多い。この手数料は、通常、「トランザクション料」と呼ばれ、後述する。

トランザクションの妥当性確認及び公開に関連するリソースのために、典型的には、少なくともブロックチェーンノード１０４の各々は、１つ以上の物理的サーバユニットを含むサーバ、又はデータセンタ全体の形態をとる。しかしながら、原理的に、任意の所与のブロックチェーンノード１０４は、ユーザ端末又は互いにネットワーク接続されたユーザ端末又はユーザ端末のグループの形態をとることができる。

各ブロックチェーンノード１０４のメモリは、各々の１つ以上の役割を実行し、ブロックチェーンノードプロトコルに従ってトランザクション１５２を処理するために、ブロックチェーンノード１０４の処理装置上で動作するように構成されたソフトウェアを記憶する。ブロックチェーンノード１０４に属するいずれの動作も、各々のコンピュータ装置の処理装置上で実行されるソフトウェアによって実行され得ることが理解されよう。ノードソフトウェアは、アプリケーションレイヤにおける１つ以上のアプリケーション、又はオペレーティングシステムレイヤ若しくはプロトコルレイヤのような下位レイヤ、又はこれらの任意の組合せの中に実装されてよい。

また、ネットワーク１０１には、消費者ユーザの役割を果たす複数のパーティ１０３の各々のコンピュータ装置１０２も接続されている。これらのユーザは、ブロックチェーンネットワークと相互作用できるが、トランザクション及びブロックを妥当性確認し、構成し、又は伝播させることに参加しない。これらのユーザ又はエージェントのうちの一部は、トランザクションにおいて送信側及び受信側として動作してよい。他のユーザは、必ずしも送信側又は受信側として動作することなく、ブロックチェーン１５０と相互作用してよい。例えば、幾つかのパーティは、ブロックチェーン１５０のコピーを格納する（例えば、ブロックチェーンノード１０４からブロックチェーンのコピーを取得した）記憶エンティティとして動作してよい。

パーティ１０３の一部又は全部は、異なるネットワーク、例えば、ブロックチェーンネットワーク１０６の上に重ねられたネットワークの部分として結合されてよい。ブロックチェーンネットワークのユーザ（「クライアント」と呼ばれることが多い）は、ブロックチェーンネットワークを含むシステムの部分であると言うことができる。しかしながら、これらのユーザは、ブロックチェーンノードの要求される役割を実行しないので、ブロックチェーンノード１０４ではない。代わりに、各パーティ１０３は、ブロックチェーンネットワーク１０６と相互作用し、それにより、ブロックチェーンノード１０６に結合する（つまり通信する）ことにより、ブロックチェーン１５０を利用してよい。２つのパーティ１０３及び各々の機器１０２は、説明のために示されており、第１パーティ１０３a及びその各々のコンピュータ機器１０２a、ならびに第２パーティ１０３b及びその各々のコンピュータ機器１０２bである。より多くのこのようなパーティ１０３及びそれらの各々のコンピュータ機器１０２がシステム１００に存在し、参加することができるが、便宜上、それらは図示されていないことが理解されよう。各パーティ１０３は、個人又は組織であってもよい。純粋に例示として、第１パーティ１０３ａは、本明細書においてAliceと称され、第２パーティ１０３ｂは、Bobと称されるが、これは限定的なものではなく、本明細書においてAlice又はBobという言及は、各々「第１パーティ」及び「第２パーティ」と置き換えることができることは理解されるであろう。

各パーティ１０３のコンピュータ機器１０２は、１つ以上のプロセッサ、例えば、１つ以上のCPU、GPU、他のアクセラレータプロセッサ、特定用途向けプロセッサ、及び/又はFPGAを備える各々の処理装置を備える。各パーティ１０３のコンピュータ機器１０２は、更に、メモリ、すなわち、非一時的コンピュータ読み取り可能媒体又は媒体の形態のコンピュータ読み取り可能記憶装置を備える。このメモリは、１つ以上のメモリ媒体、例えば、ハードディスクのような磁気媒体、SSD、フラッシュメモリ又はEEPROMのような電子媒体、及び/又は光学ディスクドライブのような光学媒体を使用する１つ以上のメモリユニットを含むことができる。各パーティ１０３のコンピュータ機器１０２上のメモリは、処理装置上で動作するように配置された少なくとも１つのクライアントアプリケーション１０５の各々のインスタンスのようなソフトウェアを記憶する。本明細書で与えられたパーティ１０３に帰属されたいずれのアクションも、各々のコンピュータ装置１０２の処理装置上で実行されるソフトウェアを使用して実行され得ることが理解されよう。各パーティ１０３のコンピュータ機器１０２は、少なくとも１つのユーザ端末、例えばデスクトップ又はラップトップコンピュータ、タブレット、スマートフォン、又はスマートウォッチのようなウェアラブルデバイスを含む。所与のパーティ１０３のコンピュータ装置１０２は、ユーザ端末を介してアクセスされるクラウドコンピューティングリソースのような、１つ以上の他のネットワーク化されたリソースを含んでもよい。

クライアントアプリケーション１０５は、最初に、１つ以上の適切なコンピュータ読み取り可能な記憶媒体、例えばサーバからダウンロードされたもの、又はリムーバブルSSD、フラッシュメモリキー、リムーバブルEEPROM、リムーバブル磁気ディスクドライブ、磁気フロッピーディスク又はテープ、光ディスク、例えばCD又はDVD ROM、又はリムーバブル光学ドライブなどのリムーバブル記憶装置上で、任意の所与のパーティ１０３のコンピュータ機器１０２に提供され得る。

クライアントアプリケーション１０５は、少なくとも「ウォレット」機能を含む。これには主に２つの機能がある。これらのうちの１つは、各々のパーティ１０３が、ブロックチェーンノード１０４のネットワーク全体にわたって伝播され、それによってブロックチェーン１５０に含まれるべきトランザクション１５２を作成し、認可し（例えば署名し）、送信することを可能にすることである。もう１つは、現在所有しているデジタルアセットの量を各々のパーティに報告することである。アウトプットベースのシステムでは、この第２機能は、当該パーティに属するブロックチェーン１５０全体に散在する様々なトランザクション１５２のアウトプットの中で定義される量を照合することを含む。

注：種々のクライアント機能が所与のクライアントアプリケーション１０５に統合されるとして説明されることがあるが、これは、必ずしも限定的ではなく、代わりに、本願明細書に記載される任意のクライアント機能が２つ以上の異なるアプリケーションのスーツに実装されてよく、例えばAPIを介してインタフェースし、又は一方が他方へのプラグインであることが理解される。より一般的には、クライアント機能は、アプリケーションレイヤ、又はオペレーティングシステムのような下位レイヤ、又はこれらの任意の組合せにおいて実装され得る。以下は、クライアントアプリケーション１０５の観点で説明されるが、これは限定的ではないことが理解される。

各コンピュータ機器１０２上のクライアントアプリケーション又はソフトウェア１０５のインスタンスは、ネットワーク１０６のブロックチェーンノード１０４の少なくとも１つに動作可能に結合される。これにより、クライアント１０５のウォレット機能は、トランザクション１５２をネットワーク１０６に送信することができる。クライアント１０５は、また、ブロックチェーンノード１０４にコンタクトして、各々のパーティ１０３が受信側である任意のトランザクションについてブロックチェーン１５０に問い合わせることができる（又は、実施形態では、ブロックチェーン１５０は、部分的にその公開視認性を通じてトランザクションの信頼を提供する公開的設備であるため、実際には、ブロックチェーン１５０内の他のパーティのトランザクションを検査する）。各コンピュータ機器１０２上のウォレット機能は、トランザクションプロトコルに従ってトランザクション１５２を形成し、送信するように構成される。上述のように、各ブロックチェーンノード１０４は、ブロックチェーンノードプロトコルに従いトランザクション１５２を妥当性確認し、トランザクション１５２をブロックチェーンネットワーク１０６全体に渡り伝播させるために、トランザクション１５２を転送するよう構成されるソフトウェアを実行する。トランザクションプロトコルとノードプロトコルは互いに対応し、所与のトランザクションプロトコルは所与のノードプロトコルと共に所与のトランザクションモデルを実装する。同じトランザクションプロトコルは、ブロックチェーン１５０内の全部のトランザクション１５２について使用される。同じノードプロトコルは、ネットワーク１０６内の全部のノード１０４について使用される。

所与のパーティ１０３、例えばAliceがブロックチェーン１５０に含まれる新たなトランザクション１５２jを送信したいと望む場合、彼女は関連するトランザクションプロトコルに従って（彼女のクライアントアプリケーション１０５のウォレット機能を使用して）新たなトランザクションを作成する（formulate）。彼女は、次に、クライアントアプリケーション１０５からトランザクション１５２を、彼女が接続されている１つ以上のブロックチェーンノード１０４に送信する。例えば、これは、Aliceのコンピュータ１０２に最も良好に接続されているブロックチェーンノード１０４であってもよい。任意の所与のブロックチェーンノード１０４が新しいトランザクション１５２jを受信すると、ブロックチェーンノードプロトコル及びその各々の役割に従って、それを処理する。これは、最初に、新たに受信されたトランザクション１５２jが「有効」であるための特定の条件を満たしているかどうかをチェックすることを含まれていてもよい、その例については、簡単に詳述する。幾つかのトランザクションプロトコルでは、検証のための条件は、トランザクション１５２に含まれるスクリプトによってトランザクションごとに構成可能であってよい。或いは、条件は単にノードプロトコルの組み込み機能であってもよく、或いはスクリプトとノードプロトコルの組み合わせによって定義されてもよい。

新たに受信されたトランザクション１５２jが、有効であると見なされるテストに合格したという条件で（すなわち、「妥当性確認された」という条件で）、トランザクション１５２jを受信した任意のブロックチェーンノード１０４は、そのブロックチェーンノード１０４に維持されているブロックチェーンの順序付きセット１５４に、新たな妥当性確認済みトランザクション１５２を追加する。更に、トランザクション１５２jを受信する任意のブロックチェーンノード１０４は、妥当性確認済みトランザクション１５２をネットワーク１０６内の１つ以上の他のブロックチェーンノード１０４に伝播する。各ブロックチェーンノード１０４は同じプロトコルを適用するので、トランザクション１５２jが有効であると仮定すると、これは、ネットワーク１０６全体に間もなく伝播されることを意味する。

所与のブロックチェーンノード１０４において維持されるトランザクションの順序付きセット１５４に入れられると、該ブロックチェーンノード１０４は、新しいトランザクション１５２を含む、彼ら各々のトランザクションの順序付きセットの最新バージョンについて、proof-of-workパズルを解く競争を開始する（他のブロックチェーンノード１０４は、トランザクションの異なる順序付きセット１５４に基づきパズルを解こうとしているが、誰であっても１番の者が、最新のブロック１５１に含まれるトランザクションの順序付きセットを定義することに留意する）。最終的に、ブロックチェーンノード１０４は、Aliceのトランザクション１５２jを含む順序付きセット１５４の一部についてパズルを解く。一旦、新しいトランザクション１５２jを含む順序付きセット１５４についてproof-of-workが行われると、それは不変の方法でブロックチェーン１５０内のブロック１５１のうちの１つの一部となる。各トランザクション１５２は、以前のトランザクションへのポインタを含むので、トランザクションの順序もまた、不変的に記録される。

異なるブロックチェーンノード１０４は、最初に所与のトランザクションの異なるインスタンスを受信する可能性があり、従って、１つのインスタンスが公開（Publishing）されて新しいブロック１５１になる前に、どのインスタンスが「有効」であるかについて矛盾するビューを有することがあり、その時点で、全部のブロックチェーンノード１０４は公開されたインスタンスのみが有効なインスタンスであることに合意する。ブロックチェーンノード１０４が１つのインスタンスを有効であるとして受け入れ、次に第２インスタンスがブロックチェーン１５０に記録されていることを発見した場合、該ブロックチェーンノード１０４は、これを受け入れなければならず、最初に受け入れたインスタンス（つまり未だブロック１５１の中で公開されていないもの）を破棄する（つまり、無効であるとして扱う）。

アカウントベースのトランザクションモデルの一部として、幾つかのブロックチェーンネットワークにより運用される別のタイプのトランザクションプロトコルを「アカウントベース」のプロトコルと呼ぶことがある。アカウントベースの場合、各トランザクションは、過去の一連のトランザクションにおいて、先行するトランザクションのUTXOに戻って参照することによって移転される量を定義するのではなく、絶対的な口座（アカウント）残高を参照することによって移転される。すべてのアカウントの現在の状態は、ブロックチェーンと分離して、ネットワークのノードにより格納され、絶えず更新される。このようなシステムでは、トランザクションは、アカウントの連続したトランザクション記録（いわゆる「ポジション」）を用いて発注される。この値は、送信者により彼らの暗号署名の一部として署名され、トランザクション参照計算の一部としてハッシュされる。更に、任意的なデータフィールドもトランザクションに署名することができる。このデータフィールドは、例えば、前のトランザクションIDがデータフィールドに含まれている場合、前のトランザクションを遡ってポイントしてよい。

＜UTXOベースのモデル＞
図２は、トランザクションプロトコルの例を示している。これは、UTXOベースのプロトコルの例である。トランザクション１５２（「Tx」と略す）は、ブロックチェーン１５０（各ブロック１５１は１つ以上のトランザクション１５２を含む）の基本的なデータ構造である。以下は、アウトプットベース又は「UTXO」ベースのプロトコルを参照して説明される。しかし、これは、全ての可能な実施形態に限定されるものではない。例示的なUTXOベースのプロトコルは、ビットコインを参照して説明されるが、他の例示的なブロックチェーンネットワーク上でも等しく実施できることに留意する。

UTXOベースのモデルでは、各トランザクション（「Tx」）１５２は、１つ以上のインプット２０２及び１つ以上のアウトプット２０３を含むデータ構造である。各アウトプット２０３は、未使用トランザクションアウトプット（UTXO）を含んでもよく、これは、別の新しいトランザクションのインプット２０２のソースとして使用することができる（UTXOが未だ償還されていない場合）。UTXOは、デジタルアセットの量を指定する値を含む。これは、分散型台帳上のトークンの設定数を表す。また、他の情報の中でも、UTXOは、それが由来するトランザクションのトランザクションIDも含んでよい。トランザクションデータ構造はまた、ヘッダ２０１も含んでよく、ヘッダ２０１は、インプットフィールド２０２及びアウトプットフィールド２０３のサイズの指示子を含んでもよいヘッダ２０１を含んでよい。ヘッダ２０１は、トランザクションのIDも含んでもよい。幾つかの実施形態において、トランザクションIDは、トランザクションデータ（トランザクションID自体を除く）のハッシュであり、ノード１０４に提出された未処理トランザクション１５２のヘッダ２０１に格納される。

例えばAlice１０３aは、問題のデジタルアセットの量をBob１０３bに移転するトランザクション１５２jを作成したいと考えているとする。図２において、Aliceの新しいトランザクション１５２jは「Tx_１」とラベル付けされている。これは、Aliceにロックされているデジタルアセットの量を、シーケンス内の先行するトランザクション１５２iのアウトプット２０３に取り入れ、その少なくとも一部をBobに移転する。先行するトランザクション１５２iは、図２において「Tx_０」とラベル付けされている。Tx_０とTx_１は、単なる任意のラベルである。これらは、必ずしも、Tx_０がブロックチェーン１５１の第１トランザクションであること、又は、Tx_１がプール１５４の直ぐ次のトランザクションであることを意味しない。Tx_１は、まだAliceへのロックされた未使用アウトプット２０３を有する任意の先行する（つまり祖先）トランザクションのいずれかを指し示すことができる。

先行するトランザクションTx_０は、Aliceが彼女の新しいトランザクションTx_１を作成するとき、又は少なくとも彼女がそれをネットワーク１０６に送信するときに、既に妥当性確認され、ブロックチェーン１５０のブロック１５１に含まれていてもよい。それは、その時点で既にブロック１５１のうちの１つに含まれていてもよく、あるいは、順序付きセット１５４内でまだ待機していてもよく、その場合、新しいブロック１５１にすぐに含まれることになる。あるいは、Tx０及びTx１が生成されネットワーク１０６に送信されることができ、あるいは、ノードプロトコルが「孤児（orphan）」トランザクションのバッファリングを許容する場合にはTx１の後にTx０が送信されることもできる。ここでトランザクションのシーケンスの文脈で使用される「先行する」及び「後の」という用語は、トランザクション内で指定されたトランザクションポインタ（どのトランザクションがどの他のトランザクションを指すかなど）によって定義されるシーケンス内のトランザクションの順序を指す。それらは、「先行する」及び「相続する」又は「祖先」及び「子孫」、「親」及び「子」、等により、等しく置き換えられ得る。これは、必ずしも、それらが作成され、ネットワーク１０６に送られ、又は任意の所与のブロックチェーンノード１０４に到達する順序を意味しない。それにもかかわらず、先行するトランザクション（祖先トランザクション又は「親」）を指す後続のトランザクション（子孫トランザクション又は「子」）は、親トランザクションが妥当性確認されない限り、妥当性確認されない。親の前にブロックチェーンノード１０４に到着した子は孤児とみなされる。それは、ノードプロトコル及び/又はノードの行動に応じて、親を待つために特定の時間、破棄又はバッファリングされることがある。

先行するトランザクションTx_０の１つ以上のアウトプット２０３のうちの１つは、本明細書でUTXO_０とラベル付けされた特定のUTXOである。各UTXOは、UTXOによって表されるデジタルアセットの量を指定する値と、後続のトランザクションが検証されるために、従ってUTXOが正常に償還されるために、後続のトランザクションのインプット２０２の中のアンロックスクリプトによって満たされなければならない条件を定義するロックスクリプトとを含む。典型的には、ロックスクリプトは、特定のパーティ（それが含まれているトランザクションの受益者）に量をロックする。すなわち、ロックスクリプトは、標準的に以下のようなアンロック条件を定義する：後続のトランザクションのインプット内のアンロックスクリプトは、先行するトランザクションがロックされたパーティの暗号署名を含む。

ロックスクリプト（別名scriptPubKey）は、ノードプロトコルによって認識されるドメイン固有の言語で書かれたコードの一部である。そのような言語の特定の例は、ブロックチェーンネットワークにより使用される「スクリプト」（Script，大文字S）と呼ばれる。ロックスクリプトは、トランザクションアウトプット２０３を消費するために必要な情報、例えば、Aliceの署名の必要条件を指定する。トランザクションのアウトプットには、アンロックスクリプトが現れる。アンロックスクリプト（別名：scriptSig）は、ロックスクリプトの基準を満たすために必要な情報を提供するドメイン固有の言語で書かれたコードの一部である。例えば、Bobの署名を含んでもよい。アンロックスクリプトは、トランザクションのインプット２０２に現れる。

図示の例では、Tx_０のアウトプット２０３のUTXO_０は、ロックスクリプト[ChecksigP_A]を含む、これは、UTXO_０が償還されるために（厳密には、UTXO_０を償還しようとする後続のトランザクションが有効であるために）、Aliceの署名SigP_Aを必要とする。[Checksig P_A]は、Aliceの公開－秘密鍵ペアからの公開鍵P_Aの表現（つまりハッシュ）を含む。Tx_１のインプット２０２は、Tx_１を指すポインタ（例えば、そのトランザクションID、実施形態ではトランザクションTx_０全体のハッシュであるTxID_０による）を含む。Tx_１のインプット２０２は、Tx_０の任意の他の可能なアウトプットの中でそれを識別するために、Tx_０内のUTXO_０を識別するインデックスを含む。Tx_１のインプット２０２は、更に、Aliceが鍵ペアからのAliceの秘密鍵をデータの所定の部分（暗号において「メッセージ」と呼ばれることもある）に適用することによって作成された、Aliceの暗号署名を含むアンロックスクリプト<SigP_A>を含む。有効な署名を提供するためにAliceが署名する必要があるデータ（又は「メッセージ」）は、ロックスクリプトにより、又はノードプロトコルにより、又はこれらの組み合わせによって定義され得る。

新しいトランザクションTx_１がブロックチェーンノード１０４に到着すると、ノードはノードプロトコルを適用する。これは、ロックスクリプトとアンロックスクリプトを一緒に実行して、アンロックスクリプトがロックスクリプトで定義されている条件（この条件は１つ以上の基準を含むことができる）を満たしているかどうかをチェックすることを含んでよい。実施形態では、これは、２つのスクリプトの連結を含む。
<SigP_A> <P_A> || [Checksig P_A]

ここで、「||」は連結を表し、「<...>」はスタックにデータを配置することを意味し、「[...]」はロックスクリプトにより実行される機能である（本例では、スタックベースの言語）。同等に、スクリプトは。、スクリプトを連結するのではなく共通のスタックにより１つずつ実行されてよい。いずれの方法でも、一緒に実行する場合、スクリプトは、Tx_０のアウトプット内のロックスクリプトに含まれるAliceの公開鍵P_Aを使用して、Tx_１のインプット内のアンロックスクリプトが、データの期待部分に署名するAliceの署名を含むことを認証する。また、データの期待部分（「メッセージ」）も、この認証を実行するために含まれる必要がある。実施形態において、署名されたデータは、Tx_１の全体を含む（従って、データの署名された部分がすでに本質的に存在するので、データの署名された部分を平文で指定する別個の要素が含まれる必要はない）。

公開－秘密暗号法による認証の詳細は、当業者には周知であろう。基本的に、Aliceが彼女の秘密鍵を用いてメッセージに署名した場合、Aliceの公開鍵とそのメッセージが平文ならば、ノード１０４のような別のエンティティは、そのメッセージがAliceによって署名されていなければならないことを認証することができる。署名は、典型的には、メッセージをハッシュし、ハッシュに署名し、署名としてメッセージにこれをタグ付けすることを含み、それによって、公開鍵の所有者が署名を認証することを可能にする。従って、本明細書において、データの特定の部分又はトランザクションの一部などに署名するという言及は、実施形態において、そのデータの部分又はトランザクションの一部のハッシュに署名することを意味することができることに留意されたい。

Tx_１内のアンロックスクリプトが、Tx_０のロックスクリプトで指定された１つ以上の条件を満たす場合（示される例では、Aliceの署名がTx_１内で提供され、認証されている場合）、ブロックチェーンノード１０４は、Tx_１が有効であるとみなす。これは、ブロックチェーンノード１０４がTx_１をトランザクションの順序付きセット１５４に追加することを意味する。ブロックチェーンノード１０４は、トランザクションTx_１をネットワーク１０６内の１つ以上の他のブロックチェーンノード１０４に転送し、それによって、それがネットワーク１０６全体に電波されることになる。一旦、Tx_１が妥当性確認され、ブロックチェーン１５０に含まれると、これは、Tx_０からのUTXO_０を消費したものとして定義する。Tx_１は、未使用トランザクションアウトプット２０３を使用する場合にのみ有効であることに留意されたい。別のトランザクション１５２によって既に消費されたアウトプットを消費しようとする場合、Tx_１は、たとえ他のすべての条件が満たされていても無効となる。従って、ブロックチェーンノード１０４は、先行するトランザクションTx_０において参照されたUTXOが既に使用されているかどうか（既に別の有効なトランザクションへの有効なインプットを形成しているかどうか）もチェックする必要がある。これが、ブロックチェーン１５０がトランザクション１５２に定義された順序を課すことが重要である理由の１つである。実際には、所与のブロックチェーンノード１０４は、トランザクション１５２が消費されたUTXO２０３をマークする別個のデータベースを維持することができるが、最終的には、UTXOが消費されたかどうかを定義するのは、ブロックチェーン１５０内の別の有効なトランザクションへの有効なインプットを既に形成しているかどうかである。

所与のトランザクション１５２の全部のアウトプット２０３の中で指定された総量が全部のそのインプット２０２により指される総量より大きい場合、これは、殆どのトランザクションモデルにおいて無効の別の基礎である。従って、このようなトランザクションは、伝播されず、ブロック１５１に含まれることもない。

UTXOベースのトランザクションモデルでは、所定のUTXOを全体として使用する必要があることに注意する。UTXOで定義されている量のうち、別の分量が消費されている一方で、ある分量を「残しておく」ことはできない。ただし、UTXOからの量は、次のトランザクションの複数のアウトプットに分割できる。例えば、Tx_０のUTXO_０で定義された量は、Tx_１の複数のUTXOに分割できる。従って、AliceがBobにUTXO_０で定義された量の全てを与えることを望まない場合、彼女は残りの量を使って、Tx_１の第２アウトプットの中で自分自身にお釣りを与えるか、又は別のパーティに支払うことができる。

特に、Aliceは、通常、彼女のトランザクションを公開するビットコインノード１０４のために手数料も含む必要がある。Aliceがマイナーのための手数料を含まない場合、Tx_０はマイナーのブロックチェーンノード１０４によって拒否される可能性が高く、従って、技術的には有効であるが、それは依然として伝搬されず、ブロックチェーン１５０に含まれない（ノードプロトコルは、彼らが望まない場合には、ブロックチェーンノード１０４にトランザクション１５２を受け入れることを強制しない）。一部のプロトコルでは、トランザクション手数料は、独自の別個のアウトプット２０３を必要としない（すなわち、別個のUTXOを必要としない）。代わりに、インプット２０２によって示される総量と、所与のトランザクション１５２のアウトプット２０３で指定される総量との間の差は、トランザクションを公開するブロックチェーンノード１０４に自動的に与えられる。例えば、UTXO_０へのポインタがTx_１への唯一のインプットであり、Tx_１は１つのアウトプットUTXO_１しか持っていないとする。UTXO_０で指定されたデジタルアセットの量がUTXO_１で指定された量より多い場合、その差は、UTXO_１を含むブロックを公開するノード１０４により割り当てられてよい。しかし、代替的又は追加的に、必ずしも、トランザクション１５２のUTXO２０３のうちの独自のものにおいて、トランザクション手数料を明示的に指定できることは除外されない。

Alice及びBobのデジタルアセットは、ブロックチェーン１５０内の任意のトランザクション１５２の中で彼らにロックされたUTXOで構成されている。従って、典型的には、所与のパーティ１０３のアセットは、ブロックチェーン１５０を通して、様々なトランザクション１５２のUTXO全体に分散される。ブロックチェーン１５０内のどこにも、所与のパーティ１０３の総残高を定義する１つの数値は記憶されていない。各パーティへのロックされた、別の将来の（onward）トランザクションに未だ使用されていない全ての様々なUTXOの値をまとめることは、クライアントアプリケーション１０５におけるウォレット機能の役割である。ビットコインノード１０４のいずれかに格納されたブロックチェーン１５０のコピーをクエリすることにより、これを行うことができる。

スクリプトコードは、概略的に表現されることが多い（すなわち、正確な言語を用いない）ことに注意する。例えば、特定の機能を表現するオペレーションコード（opcode、オペコード）を使用してよい。「OP_....」は、スクリプト言語の特定のオペコードを表す。例として、OP_RETURNは、ロックスクリプトの始めにあるOP_FALSEが先行するとき、トランザクション内にデータを格納することができ、それによってデータをブロックチェーン１５０に不変に記録することができるトランザクションの使用不可能アウトプットを生成するためのスクリプト言語のオペコードである。例えば、データは、ブロックチェーンに格納することが望ましい文書を含むことができる。

標準的に、トランザクションのインプットは、公開鍵P_Aに対応するデジタル署名を含む。実施形態において、これは楕円曲線secp２５６k１を使用するECDSAに基づく。デジタル署名は、特定のデータに署名する。幾つかの実施形態では、所与のトランザクションについて、署名はトランザクションインプットの一部、及びトランザクションアウトプットの全部又は一部に署名する。署名するアウトプットの特定の部分はSIGHASHフラグに依存する。SIGHASHフラグは、通常、署名の最後に含まれる４バイトのコードであり、どのアウトプットが署名されるかを選択する（従って、署名の時点で固定される）。

ロックスクリプトは、通常、各々のトランザクションがロックされているパーティの公開鍵を含んでいることを表す「scriptPubKey」と呼ばれることがある。アンロックスクリプトは、通常、対応する署名を提供することを表す「scriptSig」と呼ばれることがある。しかし、より一般的には、UTXOが償還される条件が署名を認証することを含むことは、ブロックチェーン１５０の全てのアプリケーションにおいて必須ではない。より一般的には、スクリプト言語は、１つ以上の条件を定義するために使用され得る。従って、より一般的な用語「ロックスクリプト」及び「アンロックスクリプト」が好ましい。

図１に示されるようにAlice及びBobのコンピュータ装置１０２a、１２０bの各々にあるクライアントアプリケーションは、付加的な通信機能を備えてよい。この追加機能は、Alice１０３aが、（いずれかのパーティ又は第３者の勧誘で）Bob１０３bと別個のサイドチャネル３０１を確立することを可能にする。サイドチャネル３０１は、ブロックチェーンネットワークと別個にデータの交換を可能にする。このような通信は、時に「オフチェーン」通信と呼ばれる。例えば、これは、パーティの一方がネットワーク１０６にトランザクション１５２をブロードキャストすることを選択するまで、ブロックチェーンネットワーク１０６上に登録されることなく、又はチェーン１５０上に進むことなく、AliceとBobとの間でトランザクション１５２を交換するために使用され得る。このようにトランザクションを共有することは、時に、「トランザクションテンプレイト」の共有と呼ばれる。トランザクションテンプレイトは、完全なトランザクションを形成するために必要な１つ以上のインプット及び／又はアウトプットが欠けていてよい。代替又は追加で、サイドチャネル３０１は、任意の他のトランザクションに関連するデータ、例えば、鍵、交渉される量又は条項、データコンテンツ、等を交換するために使用されてよい。

サイドチャネル３０１は、ブロックチェーンネットワーク１０６と同じパケット交換ネットワーク１０１を介して確立されてもよい。代替又は追加で、サイドチャネル３０１は、モバイルセルラネットワーク、又はローカル無線ネットワークのようなローカルエリアネットワーク、又はAliceとBobの装置１０２a、１０２bの間の直接有線若しくは無線リンクのような異なるネットワークを介して確立されてよい。一般に、本願明細書のどこかで言及されるサイドチャネル３０１は、「オフチェーン」で、つまりブロックチェーンネットワーク１０６と別個にデータを交換するための１つ以上のネットワーキング技術又は通信媒体を介する任意の１つ以上のリンクを含んでよい。１つより多くのリンクが使用されるとき、全体としてのオフチェーンリンクのバンドル又は集合がサイドチャネル３０１と呼ばれてよい。従って、Alice及びBobが特定の情報又はデータ片等をサイドチャネル３０１を介して交換すると言われる場合、これは、必ずしも全部のこれらのデータ片が正確に同じリンク又は同じ種類のネットワークを介して送信される必要があることを意味しないことに留意する。

＜クライアントソフトウェア＞
図３Aは、本開示の方式の実施形態を実装するためのクライアントアプリケーション１０５の例示的な実装を示す。クライアントアプリケーション１０５は、トランザクションエンジン４０１と、ユーザインタフェース（UI）レイヤ４０２と、を含んでよい。トランザクションエンジン４０１は、クライアント１０５の基礎トランザクション関連機能、例えば、トランザクション１５２を形成し、トランザクション及び/又はサイドチャネル３０１を介して他のデータを受信及び/又は送信し、及び/又はブロックチェーンネットワーク１０６を介して伝播されるように１つ以上のノード１０４にトランザクションを送信するように、上述した処理に従って構成される。

UIレイヤ４０２は、各々のユーザコンピュータ機器１０２のユーザ入力／出力（I/O）手段を介して、機器１０２のユーザ出力手段により各々のユーザ１０３へ情報を出力すること及び機器１０２のユーザ入力手段により各々のユーザ１０３から入力を受信することを含む、ユーザインタフェースをレンダリングするよう構成される。例えば、ユーザ出力手段は、視覚的出力を提供する１つ以上のディスプレイスクリーン（タッチ又は非タッチスクリーン）、オーディオ出力を提供する１つ以上のスピーカ、及び／又は触覚出力を提供する１つ以上の触覚出力装置、等を含み得る。ユーザ入力手段は、例えば、１つ又は複数のタッチスクリーンの入力アレイ（出力手段に使用されるものと同じか又は異なる）、マウス、トラックパッド又はトラックボールなどの１つ又は複数のカーソルベースの装置、音声又は声の入力を受け取るための１つ又は複数のマイクロフォン及び音声認識アルゴリズム、手動又は身体のジェスチャの形態で入力を受け取るための１つ又は複数のジェスチャベースの入力装置、又は１つ又は複数の機械的ボタン、スイッチ又はジョイスティックなどを含ことができる。

本明細書における種々の機能は、同一のクライアントアプリケーション１０５に統合されていると記述することができるが、これは、必ずしも限定するものではなく、代わりに、２つ以上の別個のアプリケーション、例えば、一方が他方へのプラグインであるか、又はAPI（アプリケーションプログラミングインタフェース）を介したインタフェースで実装することができることに留意する。例えば、トランザクションエンジン４０１の機能は、UIレイヤ４０２と別個のアプリケーション、又は所与のモジュールの機能に実装されてよく、トランザクションエンジン４０１が１つより多くのアプリケーションの間で分割されてよい。また、記載の機能の一部又は全部が、例えばオペレーティングシステムレイヤに実装されることを除外しない。本願明細書のどこかで、単一の又は所与のアプリケーション１０５等を参照する場合、これが単に例としてであること、より一般的には、記載の機能が任意の形式のソフトウェアで実装され得ることが理解される。

図３Bは、Aliceの機器１０２a上のクライアントアプリケーション１０５aのUI層４０２によりレンダリングされてよいユーザインタフェース（UI）５００の例の模擬表示を与える。同様のUIが、Bobの機器１０２b上のクライアント１０５b、又は任意の他のパーティの機器によりレンダリングされてよいことが理解される。

例示として、図３Bは、Aliceの観点からUI５００を示す。UI５００は、ユーザ出力手段を介して別個のUI要素として描画される１つ以上のUI要素５０１、５０２、５０２を含む。

例えば、UI要素は、例えば、画面上の異なるボタン、又はメニュー内の異なるオプション等の１つ以上のユーザ選択可能要素５０１を含むことができる。ユーザ入力手段は、スクリーン上のUI要素をクリック若しくはタッチすることにより、又は所望のオプションの名称を発話することにより、ユーザ１０３（この場合にはAlice１０３a）がオプションのうちの１つを選択又は操作できるよう構成される（注：ここで使用される「手動（manual）」は単に自動の反対を意味し、必ずしも手の使用に限定されない）。

代替又は追加として、UI要素は、１つ以上のデータ入力フィールド５０２を含むことができる。これらのデータ入力フィールド５０２は、ユーザ出力手段、例えば、オンスクリーンを介してレンダリングされ、データは、ユーザ入力手段、例えば、キーボード又はタッチスクリーンを介してフィールドに入力することができる。あるいは、データは、例えば、音声認識に基づいて口頭で受信され得る。

代替的又は追加的に、UI要素は、ユーザに情報を出力するために出力される１つ以上の情報要素５０３を含んでもよい。例えば、情報は、スクリーン上に描画されるか、又は可聴でレンダリングされることがある。

例えば、この/これらは、スクリーン上に描画されるか、又は可聴で描画されることがある。これらのUI要素の機能は、間もなく更に詳細に議論される。また、図３Bに示されたUI５００は、単に概略的なモックアップであり、実際には、１つ以上のさらなるUIエレメントを含んでもよく、これは、簡潔さのために示されていないことが理解される。

＜ノードソフトウェア＞
図４は、UTXO又はアウトプットに基づくモデルの例における、ネットワーク１０６の各ブロックチェーンノード１０４で実行され得るノードソフトウェア４５０の例を示す。別のエンティティが、ネットワーク１０６上でノード１０４として分類されずに、つまり、ノード１０４に必要なアクションを実行せずに、ノードソフトウェア４５０を実行できることに注意する。ノードソフトウェア４５０は、プロトコルエンジン４５１、スクリプトエンジン４５２、スタック４５３、アプリケーションレベルの決定エンジン４５４、及び１つ以上のブロックチェーン関連機能モジュールのセット４５５を含んでよいが、それらに限定されない。各ノード１０４は、合意モジュール４５５C（例えば、proof-of-work）、伝播モジュール４５５P、及びストレージモジュール４５５S（例えば、データベース）の３つすべてを含むが、これらに限定されないノードソフトウェアを実行できる。プロトコルエンジン４０１は、標準的に、トランザクション１５２の異なるフィールドを認識し、それらをノードプロトコルに従い処理するよう構成される。トランザクション１５２j（Tx_j）が受信され、別の先行するトランザクション１５２i（Tx_m-１）のアウトプット（例えばUTXO）をポイントするインプットを有するとき、プロトコルエンジン４５１は、Tx_j内のアンロックスクリプトを識別し、それをスクリプトエンジン４５２に渡す。プロトコルエンジン４５１は、更に、Tx_jのインプットの中のポインタに基づき、Tx_iを識別し検索する。Tx_iはブロックチェーン１５０上で公開されてよい。この場合、プロトコルエンジンは、ノード１０４に格納されているブロックチェーン１５０のブロック１５１のコピーからTxiを取得できる。又は、Tx_iは、まだブロックチェーン１５０上で公開されていない可能性がある。その場合、プロトコルエンジン４５１は、ノード１５４によって保持されている未公開トランザクションの順序付きセット１５４からTx_iを取得することができる。いずれの方法も、スクリプトエンジン４５１は、Tx_jの参照されるアウトプットの中のロックスクリプトを識別し、これをスクリプトエンジン４５２に渡す。

スクリプトエンジン４５２は、従って、Tx_iのロックスクリプト、及びTx_j対応するインプットからのアンロックスクリプトを有する。例えば、Tx_０及びTx_１が図２に示されるが、同じことがトランザクションの任意のペアに適用され得る。スクリプトエンジン４５２は、前述のように２つのスクリプトを一緒に実行し、これらは、使用されているスタックに基づくスクリプト言語（例えばScript）に従い、スタック４５３にデータを置くことと、データを検索することとを含む。

スクリプトを一緒に実行することにより、スクリプトエンジン４５２は、アンロックスクリプトがロックスクリプトの中で定義された１つ以上の基準を満たすか否か、つまり、それがロックスクリプトが含まれるアウトプットを「アンロック」するか否かを決定する。スクリプトエンジン４５２は、この決定の結果をプロトコルエンジン４５１に返す。スクリプトエンジン４５２は、アンロックスクリプトは対応するロックスクリプトの中で指定された１つ以上の基準を満たすと決定した場合、結果「真」を返す。その他の場合、それは結果「偽」を返す。

アウトプットに基づくモデルでは、スクリプトエンジン４５２からの結果「真」は、トランザクションの有効性についての条件のうちの１つである。標準的に、同様に満たされなければならない、プロトコルエンジン４５１により評価される１つ以上の更なるプロトコルレベルの条件が更にあり、Tx_jのアウトプットの中で指定されたデジタルアセットの総量がそのインプットによりポイントされる総量を超えないこと、Tx_iのポイントされるアウトプットは別の有効なトランザクションにより未だ使用されていないこと、等である。プロトコルエンジン４５１は、１つ以上のプロトコルレベルの条件と一緒にスクリプトエンジン４５２からの結果を評価し、それら全部が真である場合、トランザクションTx_jを妥当性確認する。プロトコルエンジン４５１は、トランザクションが有効であるかどうかの指示を、アプリケーションレベル決定エンジン４５４に出力する。Tx_jが実際に妥当性確認されたことのみを条件として、決定エンジン４５４は、合意モジュール４５５Cび伝播モジュール４５５Pの一方又は両方を、それらの各々のブロックチェーンに関連する機能をTx_jに関して実行するよう制御することを選択してよい。これは、ブロック１５１に組み込むためにノードの各々の順序付きトランザクションセット１５４にTx_jを追加する合意モジュール４５５Cと、ネットワーク１０６内の別のブロックチェーンノード１０４にTx_jを転送する伝播モジュール４５５Pを含んでよい。任意的に、実施形態では、アプリケーションレベル決定エンジン４５４は、これらの機能のうちのいずれか又は両方をトリガする前に、１つ以上の追加条件を適用してよい。例えば、決定エンジンは、トランザクションが妥当性確認されたこと、及び十分なトランザクション手数料が残されることの両方を条件としてのみ、トランザクションを公開することを選択してよい。

用語「真（true）」及び「偽（false）」は、本願明細書では、必ずしも単一の２進数字（ビット）のみの形式で表現される結果を返すことに限定しないが、それは勿論１つの可能な実装であることに留意する。より一般的には、「真」は、成功又は肯定的な結果を示す任意の状態を表すことができ、「偽」は、不成功又は非肯定的な結果を示す任意の状態を表すことができる。例えば、アカウントに基づくモデルでは、「真」の結果は、署名の暗示的なプロトコルレベルの検証と、スマートコントラクトの追加の肯定的なアウトプットとの組合せにより示され得る（全体の結果は、両方の個々の結果が真である場合に、真を伝達すると考えられる）。

開示された技術の他の変形例又は使用事例は、本明細書で開示されると、当業者に明らかになり得る。本開示の範囲は、記載された実施形態によって限定されるものではなく、添付の特許請求の範囲によってのみ限定される。

例えば、上述の幾つかの実施形態は、ビットコインネットワーク１０６、ビットコインブロックチェーン１５０、及びビットコインノード１０４の観点で説明された。しかしながら、ビットコインブロックチェーンは、ブロックチェーン１５０の１つの特定の例であり、上述の説明は任意のブロックチェーンに一般的に適用されてよいことが理解される。つまり、本発明は、ビットコインブロックチェーンに何ら限定されない。より一般的には、上述のビットコインネットワーク１０６、ビットコインブロックチェーン１５０、及びビットコインノード１０４への言及は、ブロックチェーンネットワーク１０６、ブロックチェーン１５０、及びブロックチェーンノード１０４により各々置き換えられてよい。ブロックチェーン、ブロックチェーンネットワーク、及び／又はブロックチェーンノードは、ビットコインブロックチェーン１５０、ビットコインネットワーク１０６、及びビットコインノード１０４の上述の特性の一部又は全部を共有してよい。

本発明の幾つかの実施形態では、ブロックチェーンネットワーク１０６は、ビットコインネットワークであり、ビットコインノード１０４はブロックチェーン１５０のブロック１５１を生成し、公開し、伝播し、及び格納する上述の機能の少なくとも全部を実行する。これらの機能の全部ではなく１つ又は一部のみを実行する他のネットワークエンティティ（又はネットワーク要素）が存在することが除外されない。つまり、ネットワークエンティティは、ブロックを伝播し及び／又は格納する機能を実行してよいが、ブロックを生成し公開しなくてよい（これらのエンティティが好適なビットコインネットワーク１０６のノードと見なされないことを思い出してほしい）。

本発明の幾つかの他の実施形態では、ブロックチェーンネットワーク１０６はビットコインネットワークでなくてもよい。これらの実施形態では、ノードが、ブロックチェーン１５０のブロック１５１を生成し、公開し、伝播し、及び格納する機能の全部ではなく少なくとも１つ又は一部を実行してよいことが除外されない。例えば、これらの他のブロックチェーンネットワークでは、「ノード」は、ブロック１５１を生成し公開するよう構成されるが該ブロック１５１を格納し及び／又は他のノードに伝播しないネットワークエンティティを表すために使用されてよい。

更に一般的には、上述の用語「ビットコインノード」１０４の言及は、用語「ネットワークエンティティ」又は「ネットワーク要素」と置き換えられてよい。このようなエンティティ／要素は、ブロックを生成し、公開し、伝播し、及び格納する役割のうちの一部又は全部を実行するよう構成される。そのようなネットワークエンティティ／要素の機能は、ハードウェアで、ブロックチェーンノード１０４を参照して上述したのと同じ方法で実装されてよい。

＜Merkleプルーフ＞
前述のように、マイニングノードはトランザクションをブロックにグループ化する。ブロックのペイロードには、コインベースのトランザクションを含む、順序付けられたトランザクションのセットが含まれる。各ブロックには、Merkleルートを含む様々なデータフィールドを含むブロックヘッダがある。Merkleルートは、ペイロード内のデータ、つまり順序付けられたトランザクションのセットの要約又は「フィンガープリント」と見なされる場合がある。Merkleルートは、Merkleツリーを構築することによって決定される。

順序付けられた要素セットのMerkleツリーは、各要素をハッシュし、隣接するハッシュされた要素のペアを連結し、連結されたハッシュされた要素をハッシュすることによって次のレイヤを再帰的に作成することによって構築される。Merkleツリー５００の簡単な例を図５Aに示す。

この例では、説明を容易にするために、Merkleツリー５００は８つの要素のみの順序付けられたセットに関連している。他の例のMerkleツリーは、より小さいか、より一般的にははるかに大きい場合がある。Merkleツリー５００のレイヤは下から上にラベル付けされ、レイヤ０は基本レイヤであり、この例ではレイヤ３はMerkleルート５０２である。Merkleツリー５００は、まず要素をハッシュすることによって基本レイヤを作成することによって形成される。つまり、各基本レイヤノード５０４は、その位置にある対応する要素のハッシュである。ビットコインの場合、各基本レイヤノード５０４は、対応するトランザクションのハッシュ（ビットコインの場合、double-SHA２５６）である。トランザクションのdouble-SHA２５６ハッシュは、そのトランザクション識別子TXIDでもある。従って、ビットコインの場合、各基本レイヤノード５０４は、ブロック内のトランザクションの順序付けられたセットのその位置にあるトランザクションに対応するTXIDである。

Merkleツリー５００のレイヤ１ノードを構築するために、基本レイヤノードはペアにグループ化される。各ペア内で要素が連結され、次にハッシュされて、上のレイヤの親ノードの値が検索される。例えば、基本レイヤペア５０６にTxID_２とTxID_３が含まれている場合、２つのTxIDはTxID_２||TxID_３として連結され、結果として生じた値はハッシュされて要素５０８が計算される。

レイヤ２要素は、レイヤ１要素の連結ペアのハッシュとして計算される。以下同様である。例えば、要素５１２は、要素５１０と要素５０８の連結ペアのハッシュから計算される。Merkleツリー５００の中間レイヤのノードの中間ハッシュを計算することによるレイヤの構築は、Merkleルート５０２と呼ばれる最上位レイヤの単一の要素になるまで続行される。

全てのブロックが、正確に２ⁿ個の要素を含むトランザクションの完全なセットを持つわけではないことが理解される。このような場合は、「部分的な」Merkleツリーになる可能性がある。図５Bは、レイヤ０に５つの要素（例えば、ブロック内の５つのトランザクション）がある例を示している。最初の４つの要素はペアにすることができるが、参照符号５２０で示される最後のトランザクションは対応するペア要素を持たない。ベースレイヤで欠落しているペア要素は、最後の要素がペアの左側のメンバーである場合にのみ発生することが理解される。この状況でMerkleツリーを構築するために、左側の要素の「コピー」が右側の要素として使用される。つまり、参照符号５２０で示されるTxID_４はそれ自体と連結され、ノード５２２の親要素の値を見つけるためにハッシュされる。同様に、ノード５２２は、ノード５２２のペアの中に対応する右側の要素を持たないため、ノード５２２の要素は自身と連結され、レイヤ２のノード５２４の親要素の値を見つけるためにハッシュされる。

Merkleルート５０２は、ブロック内のトランザクションのフィンガープリントとして機能するようにブロックのヘッダに挿入される。

Merkleツリーは、エンドユーザ装置上のクライアントアプリケーションなどの軽量ノードが、ブロック全体又はブロックチェーン全体をダウンロードする必要なく、特定のトランザクションがブロックチェーン上のブロックに存在するかどうかを決定できるようにするのに役立つ。クライアントアプリケーションは、Merkleプルーフに基づいて、トランザクションがブロック内に存在するかどうかを決定できる。Merkleプルーフでは、トランザクションからMerkleツリーを介してMerkleルートへのパスをトレースし、トランザクションがブロックに含まれていることを確認する。

ノードは、Merkleプルーフを実行できるトランザクションに関連するデータを要求できる。一例では、要求されたデータは、Merkleルートに到達するためにパスに沿って必要とされるMerkleツリー内のペアにされたハッシュに対応する順序付けられたハッシュのセットの形式で、計算された及び／又は提供されたハッシュが各ペアの左側又は右側の要素であるかどうかを示すバイナリ信号と共に、提供される場合がある。

ここでの説明の目的で、次の表記法を使用できる。使用可能なデータ（例えば、トランザクションデータ、又はMerkleツリーの連結要素）のハッシュを使用して計算される要素は、c[n]を使用して示すことができる。ここで、nはツリーのレイヤを表し、最下位又は基本レイヤはn=０にある。Merkleプルーフの目的で、別のノードによって提供されるツリーの要素、例えば中間ハッシュは、p[n]を使用して表すことができる。

図６は、Merkleツリー６００を通るMerkleパスの例を示している。この場合のMerkleパスは、ブロック内のトランザクションTxの存在を妥当性確認することに関連している。このMerkleパスを使用してMerkleプルーフを達成するために、コンピューティング装置は、トランザクションTx（又は少なくともTxID）と、Merkleパスに沿ってペアを形成するために必要な要素に対応する順序付きハッシュのセット（中間ハッシュ）を持つ。この例では、順序付きセットはp[０]、p[１]、p[２]を含む。

コンピューティング装置には、提供された中間ハッシュがペアリングの左側の要素か右側の要素かを決定するメカニズムも必要である。これは、場合によってはバイナリフラグを使用してシグナリングできる。バイナリフラグは、各レイヤについて、計算されたハッシュ（又は指定されたハッシュ）が左側の要素であるか右側の要素であるかを示すことがある。場合によっては、各レイヤで計算されたハッシュ（又は提供されたハッシュ）が左側の要素であるか右側の要素であるかをシグナリングする代わりに、最下位レイヤ又は基本レイヤの計算されたハッシュの位置、つまり順序付き要素のセット内のインデックスをシグナリングすることがある。幾つかの実装では、これらは実質的に同等である場合がある。例えば、Merkleルート６０２からMerkleパスを下に移動するレイヤ２から０の計算された要素をトレースする左側（０）又は右側（１）のパスのビットごとのシグナリングは、ビット[０,１,０]を結果として生じる。同様に、c[０]要素のインデックスi=２がシグナリングされてよく、バイナリでは０１０となる。他の実装では、異なるシグナリング又はコーディングを使用することがある。

Merkleプルーフを実行するために、コンピューティング装置は、TxIDを取得するためにトランザクションTxをハッシュ（この例では、double-SHA２５６）することによってc[０]要素を決定する。場合によっては、すでにTxIDを持っていることもある。次に、それを、順序付けられたハッシュのセットp[０]の最初に提供されたハッシュと連結する。コンピューティング装置は、インデックスi又はビットシグナリングから、計算されたハッシュc[０]が左側の要素か右側の要素かを決定し、それに応じて連結する。次に、連結をハッシュしてc[１]を決定する。c[３]を決定するまで、このプロセスを続け、ブロックヘッダ内で見つかったMerkleルート６０２と比較する。一致した場合、コンピューティング装置はトランザクションTxがブロックに含まれていると決定する。一致しない場合、トランザクションTxはブロックに含まれていない（又は提供されたMerkleパスハッシュにエラーが含まれている）。

レイヤ内の順序付けられた要素のセット内の要素の位置は、「インデックス」と呼ばれ、n番目のレイヤ内の計算された要素のインデックスを参照するときに、i又はindexOf（c[n]）によって表されることがある。最下位レイヤ又は基本レイヤでは、インデックスiの範囲は０からブロック内のトランザクション数より１少ない数までである。

一態様では、本願は、インデックス位置フィールドを有利に含むMerkleプルーフデータをシグナリングするためのデータ構造を開示し、これは、ビットベクトルに基づくパスのトップダウントレースよりも、各計算要素の左/右位置の決定を容易にする。別の態様では、本願は、Merkleプルーフプロセス内で少なくとも１つの拡張された妥当性チェックを提供する。場合によっては、拡張妥当性チェックによってブロックのトランザクション数の検証、及び／又はインデックスの妥当性の証明が可能になる。

Merkleパスに沿って計算された要素の左側又は右側の位置を決定するメカニズムとして、位置インデックスを使用すると、単純なモジュラス計算を使用して左側／右側を決定できる。「mod２」演算は、値が偶数か奇数かをシグナリングする結果を効果的に生成する。例えば、式「indexOf（c[n]）mod２」は、indexOf（c[n]）の偶数値に対して０を生成し、indexOf（c[n]）の奇数値に対して１を生成する。次に、indexOf（c[n]）の値を２で除算して、上のレイヤの計算された要素のインデックス値、つまりindexOf（c[n+１]）を決定できる。実装では、２で除算するときにフロア関数を使用して、浮動小数点数で除算演算を行う場合に剰余をドロップできる。

位置インデックスを使用して有効にできる拡張妥当性チェックの１つは、計算された要素のいずれかが右側の要素であることをインデックスが示している場合、例えばindexOf（c[n]）mod２==１の場合、対応する左側の要素p[n]がc[n]と等しくなることはできないか、又は位置インデックスが誤っている可能性が高いことを確認することである。位置インデックスが誤っているにもかかわらず、そのような状況が、有効なMerkleルート計算をもたらす可能性がある。例えば、適切な位置インデックスがトランザクションリストの最後にある左側の要素を指しているが、位置インデックスが誤って右側にコピーされた要素を指している場合、インデックス値が間違っていても、Merkleルートの計算は正しい可能性がある。

位置インデックスを使用することで有効になる可能性のある、更に拡張された妥当性チェックは、ブロック内の最後のトランザクションを識別する機能である。コンピューティング装置は、ブロック内のトランザクションの合計数を知る場合と知らない場合がある。トランザクション数はブロック内のフィールドであるが、ブロックヘッダ内にあるとは限らないため、コンピューティング装置はそのような情報を持たない場合がある。その情報を持っているかどうかにかかわらず、コンピューティング装置は、計算された値がMerkleツリーのすべてのレイヤですべて右側の要素であるか、又は計算された値c[n]が任意のレイヤで左側の要素である場合は、対応する提供されたハッシュp[n]がc[n]に等しいことを見つけることによって、トランザクションが実際にブロック内の最後のトランザクションであることを妥当性確認できる場合がある。トランザクションが順序付けられたセットの最後、つまりブロック内の最後のトランザクションであることを妥当性確認することで、コンピューティング装置はそれによってブロック内のトランザクションの数を決定する（又はその情報を既に有している場合は有効にする）。

一部のデータ構造の実装では、順序付けられたハッシュのセット内のc[n]のコピーであるp[n]を提供するのではなく、c[n]がそのレイヤのコピーである必要があることを、提供するノードがシグナリングする場合があることが理解される。特定のコード、信号、フラグ、又はその他の構文要素を使用して、提供されたハッシュの代わりに、c[n]のコピーを使用する必要があることをシグナリングすることができる。

Merkleプルーフデータを送信するためのデータ構造の例を次に示す。

上記の例では、Merkleツリーの最下位レイヤ内のc[０]の位置インデックスがインデックス（index）フィールド内に設けられている。バージョン（version）フィールドは、様々なオプションをシグナリングするために使用できる。例えば、元のトランザクションはシグナリングされてもされなくてもよく、Merkleルートは含まれても含まれなくてもよく、ブロックヘッダは含まれても含まれなくてもよい、等である。バージョン（version）フィールドは、機能のどの組み合わせが含まれるかをシグナリングする。例示的なバージョンは限定ではないが以下を含む。

パス（path）フィールドには、提供されたハッシュの順序付けられたセットが含まれる。幾つかの例では、パスデータ構造は、提供されたハッシュの完全なセットであり、幾つかの例では、提供されたハッシュの完全なセットを生成するために展開又は復号可能な十分な情報を含む。元のTxID（例えば、c[０]）とMerkleルートの包含は、バージョンコードに基づいて決定される。

幾つかの例では、p[n]がc[n]のコピーである場合、p[n]がパスデータ構造に含まれていない可能性があり、p[n]がコピーであることをシグナリングするための構文要素に置き換えられることがある。例として、JSONでは、コピーをシグナリングするために特別な文字列「*」が使用される場合がある。

duplicated_indexesフィールドとduplicated_indexes_countフィールドが含まれる場合と含まれない場合がある。含まれる場合、コピーされたp[n]要素の数とそれらが発生するレイヤnは、これらのフィールドを使用してシグナリングされる場合がある。コピーされたp[n]要素をシグナリングするこのメカニズムが使用される場合、パスフィールドには、それらのレイヤに関してコピーをシグナリングするハッシュ又は構文要素のいずれも含まれないことが理解される。

図７は、トランザクションがブロックに含まれているかどうかを決定するための単純化された一例の方法７００をフローチャート形式で示す。方法７００は、例えばクライアントアプリケーションを使用して、ブロックチェーンノード又はエンドユーザ装置である可能性のある、ネットワーク接続されたコンピューティング装置によって実装される場合がある。方法７００は、プロセッサ実行可能命令により実施されてよい。プロセッサ実行可能命令は、プロセッサにより実行されると、プロセッサに、説明された動作を実行させる。操作には、メモリアクセス機能、信号又はデータの送受信機能、表示操作、及びプロセッサに結合されたコンポーネントに関連するその他の操作が含まれる場合がある。命令は、１つ以上のソフトウェアモジュール、アプリケーション、ルーチンなどに具体化される場合がある。

方法７００は、場合によっては、動作７０２によって示されるように、コンピューティング装置がリモートノードに要求を発行することによって開始される場合がある。リモートノードは、ブロックチェーンノードである場合もあれば、エンドユーザ装置である場合もある。例えば、コンピューティング装置は第１エンドユーザ装置であり、リモートノートは第２エンドユーザ装置である場合があり、どちらもトランザクションの交渉又は確定に従事している。この要求は、特定のトランザクションTxがブロックチェーン上のブロックに含まれていることの確認に関連している。例によっては、要求が複数のリモートノードに送信されることがある。要求には、Txのコピー又はTxの一意の識別子（TxIDなど）を含めることができる。

要求に応答して、動作７０４で、コンピューティング装置は、少なくとも、特定のブロック内のTxに関連付けられた位置インデックスとパスデータを含む応答メッセージを受信する場合がある。パスデータには、順序付けられたハッシュのセットを含めることができる。順序付けられたハッシュのセットには、特定のブロックのMerkleツリー内のTxに関するMerkleプルーフを実行するための提供されたハッシュを含めることができる。

動作７０６では、コンピューティング装置はMerkleツリーの最下位レベルから開始し、計算された要素を再帰的に計算し、順序付けられたハッシュのセット内の対応する提供された要素を識別し、インデックスに従ってそれらを連結し、ハッシュして親の計算された要素を見つける。コンピューティング装置は、Merkleルートに到達するまでMerkleパスを構築する。コンピューティング装置は、Merkleツリーのレベル数を知っていることに基づいてMerkleルートに到達したことを知る場合もあれば、順序付けられたハッシュのセットにそれ以上のハッシュがないという事実からMerkleツリーのレベル数を推測できる場合もある。

動作７０８では、コンピューティング装置は、インデックスと、計算されたハッシュとそれに対応する提供されたハッシュのペアから、そのトランザクションがブロック内の最後のトランザクションであるかどうかを決定する。Merkleルートを除くすべてのレベルで、インデックスが計算された要素が右側の要素であることを示している場合、コンピューティング装置は、インデックスに基づいてそのトランザクションをブロック内の最後のトランザクションとして識別できる。このような状況は、Merkleツリーが「完全」である場合、つまり基本レイヤに正確に２ⁿ個の要素があり、トランザクションが最も右側の要素である場合にのみ発生する。コンピューティング装置は、「部分的な」（例えば、non-full）Merkleツリーの場合には、計算された要素が、対応する提供された右側のメンバーp[n]がコピーであるペアの左側のメンバーであるときは常に、トランザクションがブロック内の最後のトランザクションであることを更に識別することができる。つまり、indexOf（c[n]）=０であるすべてのnに対して、c[n]=p[n]となる。

動作７０８は、議論を容易にするために個別に示されるが、Merkleパスが構築されるときに、動作７０６と同時に実行できることが理解される。

動作７１０では、コンピューティング装置はエラーが検出されたかどうかを決定できる。１つのエラーは、計算されたMerkleルートがブロックヘッダのMerkleルートと一致しないという決定である場合がある。もう１つのエラーは、計算された要素が右側の要素であり、そのペアの左側の位置に提供されたハッシュが、計算された要素のコピーである場合の検出であってよい。どちらの場合も、動作７１２では、コンピューティング装置はエラー通知を出力する。エラー通知は、検出されたエラーの性質、つまり不一致Merkleルート又は左側のコピーエラーを示す場合がある。それ以外の場合、コンピューティング装置は動作７１４で成功通知を出力し、Merkleプルーフが有効であり、トランザクションTxが指定された位置インデックスのブロックに含まれていることを確認する。成功通知は、Txがブロック内の最後のTxであると決定されたかどうか、及びその場合はそのブロック内のトランザクションの合計数を更に示す場合がある。

動作７１２及び７１４の通知には、聴覚通知、視覚通知、及び／又は触覚通知など、コンピューティング装置上の出力を含めることができる。通知には、Merkleプルーフの分析及び決定の結果を詳述するユーザインタフェースメッセージの表示を含めることができる。場合によっては、通知には、動作７０４でパスデータを取得したリモートノードを含む、１つ以上のリモートノードへの結果メッセージの送信を含めることができる。

実装の一例を、次のサンプルコードで示す。サンプルコードはjavascript形式で提供されており、提供されているハッシュのセットは長さ"hashes.length"のデータ構造であり、Merkleツリー内のレイヤ数を更に示し、Merkleルートがhashesデータ構造の最終要素として提供されている。この例では、コンピューティング装置は、「tx」により示されるトランザクションのコピーを有する。この例で使用されているハッシュアルゴリズムは、ビットコインの標準的なdouble-SHA２５６ハッシュであり、関数「sha２５６d（）」で示されている。

上述のコードは１つの例示的な実装であることが理解される。他の実装では、他のコーディング言語、構造体、手法が使用される場合がある。

リモートノードから提供されるデータには、Merkleルート、Merkleルートを含むブロックヘッダ、及び／又はブロックハッシュが含まれる場合がある。場合によっては、クライアントアプリケーションを実行しているエンドユーザ装置などのコンピューティング装置が、事前に検証されたブロックヘッダとブロックハッシュからヘッダへのインデックスを有し又はそれにアクセスできる場合がある。その場合、リモートノードはブロックハッシュを提供して、コンピューティング装置が対応する事前に検証されたブロックヘッダを特定し、プルーフを妥当性確認するためにそのMerkleルートを抽出できるようにすることがある。有利なことに、事前に検証されたブロックヘッダと対応するブロックハッシュ情報は、１つ又は複数の他のリモートブロックチェーンノードから取得されている可能性があり、これにより、コンピューティング装置は、ブロックヘッダが現在最長のproof-of-workチェーンを表しており、それらが多数のブロックチェーンノードによって検証されていることを確信する。

上述の種々の実施形態は、単なる例であり、本願の範囲を限定することを意味しない。本願の意図された範囲内にある変形のように、ここに記載された種々の技術革新は、当業者に明らかである。特に、上述の例示的な実施形態のうちの１つ以上からの特徴は、以上に明示的に示されない特徴の部分結合を含む代替の例示的な実施形態を生成するために選択されてよい。更に、上述の例示的な実施形態のうちの１つ以上からの特徴は、以上に明示的に示されない特徴の結合を含む代替の例示的な実施形態を生成するために選択され結合されてよい。このような結合及び部分結合に適する特徴は、本願の全体的吟味により当業者に直ちに明らかになるだろう。本願明細書及び請求項に記載された主題は、あらゆる適切な技術的変更をカバーし包含する。

Claims (14)

1. ブロックチェーン内のデータの妥当性を決定するための、コンピュータが実施する方法であって、
   リモートノードから、ブロック内のトランザクションのインデックスと、Merkleプルーフのための順序付けられたハッシュのセットを受信するステップと、
   Merkleツリーの最下位レベルから開始して、最上位レベルに到達するまで、前記Merkleツリーの各レベルで、
   前記順序付けられたハッシュのセットから提供されたハッシュを順に選択するステップと、
   前記提供されたハッシュと現在のレベルの計算されたハッシュを、前記インデックスに基づいて決定された順序で連結するステップと、
   前記連結をハッシュして上のレベルの計算されたハッシュを見つけるステップと、
   前記インデックス、及び前記計算されたハッシュと前記順序付けられたハッシュのセットから提供された対応するハッシュとの各ペアから、前記トランザクションが前記ブロック内の最後のトランザクションであるかどうかを決定するステップと、
   前記最上位レベルの計算されたハッシュと前記ブロックのヘッダ内のMerkleルートを比較するステップと、
   前記比較するステップ及び決定するステップの結果を出力するステップと、
   を含む方法。
2. 受信した前記インデックスが、前記ブロック内の順序付けられたトランザクションのセットの中の前記トランザクションの位置を示す位置インデックスである、請求項１に記載の方法。
3. 最下位レベルより上の各レベルについて、下のレベルのインデックスを２で割ったものに基づいて、当該レベルのインデックスを決定するステップ、を更に含む請求項２に記載の方法。
4. 前記トランザクションが前記ブロック内の最後のトランザクションであると決定することは、最上位レベルの計算されたハッシュ以外の各計算されたハッシュが、前記Merkleツリー内の右側の要素であると決定することを含む、請求項１～３のいずれか一項に記載の方法。
5. 前記トランザクションが前記ブロック内の最後のトランザクションであると決定することは、ペアにされた左側の要素である任意の計算されたハッシュについて、対応する提供されたハッシュが前記計算されたハッシュと等しいと決定することを含む、請求項１～４のいずれか一項に記載の方法。
6. 前記トランザクションが前記ブロック内の最後のトランザクションであるかどうかを決定することは、少なくとも１つの計算されたハッシュが左側の要素であり、それに対応する提供されたハッシュが該少なくとも１つの計算されたハッシュと等しくないと決定することに基づいて、前記トランザクションが前記ブロック内の最後のトランザクションではないことを決定することを含む、請求項１～５のいずれか一項に記載の方法。
7. 少なくとも１つの計算されたハッシュが右側の要素であり、それに対応する提供されたハッシュが該少なくとも１つの計算されたハッシュと等しいと決定することに基づいて、前記インデックスが無効であると決定するステップ、を更に含む請求項１～６のいずれか一項に記載の方法。
8. 最初に、前記トランザクションの識別子を持つMerkleプルーフデータの要求を前記リモートノードに送信するステップ、を更に含む請求項１～７のいずれか一項に記載の方法。
9. 受信するステップは、バージョンフィールドと、前記インデックスを含むインデックスフィールドと、前記順序付けられたハッシュのセットを含むデータ構造を含むパスフィールドと、を含むメッセージを受信するステップを含む、請求項８に記載の方法。
10. 前記Merkleツリーの最下位レベルの計算されたハッシュが、前記トランザクションのトランザクション識別子である、請求項１～７のいずれか一項に記載の方法。
11. 前記インデックスに基づいて決定される順序は、前記計算されたハッシュが、対応する提供されたハッシュとのペアの中で、左側の要素であるか右側の要素であるかを決定することを含み、前記計算されたハッシュが左側の要素であるか右側の要素であるかを決定することは、当該レベルのインデックスがインデックスのモジュロ２に基づいて偶数であるか奇数であるかを決定することに基づく、請求項１～１０のいずれか一項に記載の方法。
12. 前記順序付けられたハッシュのセットは、重複したハッシュ値を含む代わりに、重複したハッシュをシグナリングする構文要素を含む、請求項１～１１のいずれか一項に記載の方法。
13. コンピューティング装置であって、
    １つ以上のプロセッサと、
    メモリと、
    前記メモリに格納されたコンピュータ実行可能命令であって、前記１つ以上のプロセッサにより実行されると、前記プロセッサに請求項１～１２のいずれか一項に記載の方法を実行させる、コンピュータ実行可能命令と、
    を含むコンピューティング装置。
14. プロセッサ実行可能命令を格納しているコンピュータ可読媒体であって、前記プロセッサ実行可能命令は、１つ以上のプロセッサにより実行されると、前記プロセッサに請求項１～１２のいずれか一項に記載の方法を実行させる命令を含む、コンピュータ可読媒体。