例示的なシステムの概観
図1は、ブロックチェーン150を実装するための例示的なシステム100を示す。システム100は、典型的にはインターネットのような広域インターネットワークであるパケット交換ネットワーク101を含む。パケット交換ネットワーク101は、パケット交換ネットワーク101内にピアツーピア(P2P)オーバーレイ・ネットワーク106を形成するように構成された複数のノード104を含む。各ノード104はピアのコンピュータ装置を含み、ノード104のうちの異なるものは異なるピアに属する。各ノード104は、一つまたは複数のプロセッサ、たとえば、一つまたは複数の中央処理装置(CPU)、アクセラレータ・プロセッサ、特定用途向けプロセッサ、および/またはフィールド・プログラマブル・ゲート・アレイ(FPGA)を含む処理装置を含む。各ノードはまた、メモリ、すなわち、非一時的なコンピュータ読み取り可能媒体またはメディアの形のコンピュータ読み取り可能な記憶を備える。メモリは、一つまたは複数のメモリ媒体、たとえば、ハードディスクなどの磁気媒体、固体ドライブ(SSD)、フラッシュメモリまたはEEPROMなどの電子媒体、および/または光ディスク・ドライブなどの光媒体を使用する一つまたは複数のメモリユニットを含んでいてもよい。
ブロックチェーン150は、データ151のブロックのチェーンを含み、ブロックチェーン150のそれぞれのコピーは、P2Pネットワーク160内の複数のノードのそれぞれに維持される。チェーン内の各ブロック151は、一つまたは複数のトランザクション152を含み、ここで、この文脈におけるトランザクションは、一種のデータ構造をいう。データ構造の性質は、トランザクション・モデルまたはスキームの一部として使用されるトランザクション・プロトコルのタイプに依存する。所与のブロックチェーンは、典型的には、全体を通して、1つの特定のトランザクション・プロトコルを使用する。1つの一般的なタイプのトランザクション・プロトコルでは、各トランザクション152のデータ構造は、少なくとも1つの入力および少なくとも1つの出力を含む。各出力は、該出力が暗号学的にロックされている(ロックを解除し、それによって償還または使用するために、そのユーザーの署名を必要とする)ユーザー103に属するデジタル資産の量を表す量を指定する。各入力は、先行するトランザクション152の出力をポイントし、それにより、諸トランザクションをリンクする。
ノード104の少なくともいくつかは、トランザクション152を転送し、それにより伝搬させる転送ノード104Fの役割を引き受ける。ノード104の少なくともいくつかは、ブロック151をマイニングするマイナー104Mの役割を引き受ける。ノード104の少なくともいくつかは、格納ノード104S(時に「フルコピー」ノードとも呼ばれる)の役割を引き受け、その各ノードは、それぞれのメモリに、同じブロックチェーン150のそれぞれのコピーを記憶する。各マイナー・ノード104Mはまた、ブロック151中にマイニングされるのを待っているトランザクション152のプール154を維持する。所与のノード104は、転送ノード104、マイナー104M、格納ノード104S、またはこれらの2つもしくは全部の任意の組み合わせでありうる。
所与の現在のトランザクション152jにおいて、入力(または各入力)は、トランザクションのシーケンスにおける先行するトランザクション152iの出力を参照するポインタを含み、この出力が現在のトランザクション152jにおいて償還されるか、または「使用される」ことを指定する。一般に、先行するトランザクションは、プール154または任意のブロック151内の任意のトランザクションとすることができる。先行するトランザクション152iは、必ずしも現在のトランザクション152jが作成される、またはネットワーク106に送信される時点において存在する必要はないが、先行するトランザクション152iは、現在のトランザクションが有効であるために、存在し、有効確認される必要がある。よって、本明細書における「先行」とは、ポインタによってリンクされた論理的なシーケンスで先行するものを指し、必ずしも時間的シーケンスにおける作成または送信の時刻を指すのではなく、よって、トランザクション152i、152jが順序外で作成または送信されることを必ずしも排除しない(孤立トランザクションに関する下記の議論を参照)。先行するトランザクション152iは、同様に、先行トランザクションまたは前のトランザクションと呼ばれることができる。
現在のトランザクション152jの入力は、先行するトランザクション152iの出力がロックされているユーザー103aの署名も含む。そして、現在のトランザクション152jの出力は、新しいユーザー103bに暗号学的にロックされることができる。よって、現在のトランザクション152jは、先行するトランザクション152iの入力において定義された量を、現在のトランザクション152jの出力において定義された新しいユーザー103bに移転することができる。いくつかの場合には、トランザクション152は、複数のユーザー間で入力量を分割するために複数の出力を有してもよい(おつりを与えるために、それらのユーザーのうちの1人はもとのユーザー103aであってもよい)。場合によっては、トランザクションが複数の入力をもち、一つまたは複数の先行トランザクションの複数の出力からの額を一緒に集め、現在のトランザクションの一つまたは複数の出力に再分配することもできる。
上記は、「出力ベース」トランザクション・プロトコルと呼ばれることがあり、時には未使用トランザクション出力(unspent transaction output、UTXO)タイプのプロトコルとも呼ばれることもある。ユーザーの合計残高は、ブロックチェーンに格納されるどの1つの数字においても定義されず、その代わり、ユーザーは、ブロックチェーン151内の多くの異なるトランザクション152に散在する、そのユーザーのすべてのUTXOの値を照合するために、特別な「ウォレット」アプリケーション105を必要とする。
代替的なタイプのトランザクション・プロトコルは、アカウント〔口座〕ベースのトランザクション・モデルの一部として、「アカウント・ベースの」プロトコルと呼ばれることがある。アカウント・ベースの場合、各トランザクションは、過去のトランザクションのシーケンスにおける先行するトランザクションのUTXOを遡って参照することによってではなく、絶対的なアカウント残高を参照することによって、移転される金額を定義する。すべてのアカウントの現在の状態は、ブロックチェーンとは別個にマイナーによって記憶され、常時更新される。そのようなシステムでは、トランザクションは、アカウントのランニング・トランザクション・タリー(running transaction tally)(「ポジション」とも呼ばれる)を使って順序付けられる。この値は、送信者によって、その暗号学的署名の一部として署名され、トランザクション参照計算の一部としてハッシュされる。さらに、任意的なデータ・フィールドも前記トランザクションが署名されてもよい。このデータ・フィールドは、たとえば前のトランザクションIDが該データ・フィールドに含まれている場合、先行するトランザクションをポイントしてもよい。
いずれのタイプのトランザクション・プロトコルでも、ユーザー103が新しいトランザクション152jを制定することを望む場合、ユーザーは、自分のコンピュータ端末102からP2Pネットワーク106のノード104の1つ(今日では、これは典型的にはサーバーまたはデータ・センターであるが、原理的には他のユーザー端末でもよい)に新しいトランザクションを送信する。このノード104は、各ノード104で適用されるノード・プロトコルに従って、そのトランザクションが有効であるかどうかをチェックする。ノード・プロトコルの詳細は、問題のブロックチェーン150において使用されているトランザクション・プロトコルのタイプに対応し、それらが一緒になって全体的なトランザクション・モデルをなす。ノード・プロトコルは、典型的には、新規トランザクション152jにおける暗号署名が、トランザクション152の順序付けされたシーケンスにおける先行するトランザクション152iに依存する期待される署名と一致することをチェックするために、ノード104を必要とする。出力ベースの場合、これは、新しいトランザクション152jの入力に含まれるユーザーの暗号署名が、新しいトランザクションが費やす先行トランザクション152iの出力において定義された条件にマッチすることをチェックすることを含んでいてもよく、この条件は、典型的には、新しいトランザクション152jの入力における暗号署名が、新しいトランザクションの入力がポイントする先行トランザクション152iの出力をロック解除することを少なくともチェックすることを含む。いくつかのトランザクション・プロトコルでは、条件は、少なくとも部分的には、入力および/または出力に含まれるカスタム・スクリプトによって定義されてもよい。あるいはまた、条件は、単にノード・プロトコルだけによって固定されてもよく、あるいは、これらの組み合わせによることもある。いずれにせよ、新しいトランザクション152jが有効であれば、現在のノードは、それをP2Pネットワーク106内のノード104のうちの一つまたは複数の他のノードに転送する。これらのノード104の少なくともいくつかは、転送ノード104Fとしても機能し、同じノード・プロトコルに従って同じテストを適用して、新しいトランザクション152jを一つまたは複数のさらなるノード104に転送する。このようにして、新しいトランザクションは、ノード104のネットワーク全体に伝搬させられる。
出力ベースのモデルでは、所与の出力(たとえば、UTXO)が消費されるかどうかの定義は、それがノード・プロトコルに従った別の、前進(onward)トランザクション152jの入力によってすでに有効に償還されているかどうかである。トランザクションが有効であるための別の条件は、それが消費または償還しようとする先行トランザクション152iの出力が、別の有効なトランザクションによってすでに使用/償還されていないことである。ここでもまた、有効でない場合、トランザクション152jは、ブロックチェーンにおいて伝搬または記録されない。これは、使用者が同じトランザクションの出力を複数回使おうとする二重使用に対する防護となる。他方、アカウント・ベースのモデルは、アカウント残高を維持することによって、二重使用に対して防護する。ここでもまた、トランザクションの定義された順序があるので、アカウント残高は任意の時点において単一の定義された状態をもつ。
有効確認に加えて、ノード104Mの少なくとも一部は、「作業証明」によって裏付けられる、マイニングとして知られるプロセスにおいて、トランザクションのブロックを最初に生成するために競争する。マイニング・ノード104Mでは、まだブロックに現れていない有効なトランザクションのプールに新規トランザクションが追加される。次いで、マイナーは、暗号学的パズルを解こうと試みることによって、トランザクションのプール154からトランザクション152の新しい有効なブロック151を組み立てるために競争する。典型的には、これは、ナンスがトランザクションのプール154と連結され、ハッシュされるときに、ハッシュの出力が所定の条件を満たすように、「ナンス」値を探すことを含む。たとえば、所定の条件は、ハッシュの出力が、あるあらかじめ定義された数の先頭ゼロを有するというものであってもよい。ハッシュ関数の特性は、入力に関して予測不可能な出力をもつことである。よって、この探索は、力づくによってのみ実行でき、よって、パズルを解こうとしている各ノード104Mにおいて相当な量の処理資源を消費する。
パズルを解いた第1のマイナー・ノード104Mは、これをネットワーク106に告知し、その解を証明として提供する。証明は、ネットワーク内の他のノード104によって容易にチェックすることができる(ひとたびハッシュに対する解が与えられたら、それによりハッシュの出力が条件に合致することをチェックすることは簡単である)。勝者がパズルを解いたトランザクションのプール154は、次いで、記憶ノード104Sとして機能するノード104の少なくとも一部によって、そのような各ノードにおいて勝者が発表した解をチェックしたことに基づいて、ブロックチェーン150内の新しいブロック151として記録される。チェーン内の先に生成されたブロック151n-1を遡ってポイントするブロック・ポインタ155も、新しいブロック151nに割り当てられる。作業証明は、二重使用のリスクを低減するのに役立つ。新しいブロック151を作成するためには多大な努力を要し、二重使用を含むブロックは他のノード104によって拒否される可能性が高いので、マイニング・ノード104Mにとって、自分のブロックに二重使用が含まれることを許容する動機がないのである。ひとたび生成されると、ブロック151は、P2Pネットワーク106内の記憶ノード104Sのそれぞれにおいて、同じプロトコルに従って認識され、維持されるので、修正できない。ブロック・ポインタ155はまた、ブロック151に逐次的な順序を課す。トランザクション152は、P2Pネットワーク106内の各記憶ノード104Sにおいて順序付けられたブロックに記録されるので、これは、トランザクションの変更不能な公開台帳を提供する。
任意の所与の時点においてパズルを解くために競争する異なるマイナー104Mが、いつ解を探し始めたかに応じて、任意の所与の時点における、マイニングされていないトランザクション・プール154の異なるスナップショットに基づいて、そうすることがありうることに留意されたい。誰であれ最初にそれぞれのパズルを解いた者が、どのトランザクション152が次の新しいブロック151nに含まれるかを定義し、マイニングされていないトランザクションの現在のプール154が更新される。マイナー104Mは、次いで、新たに定義された未決のプール154からブロックを生成するために競争を続ける。生じ得る「フォーク」を解決するためのプロトコルも存在する。フォークとは、2人のマイナー104Mが互いの非常に短い時間以内にパズルを解き、ブロックチェーンの矛盾したビューが伝播するというものである。要するに、フォークのどちらの支流が伸びても、最も長いほうが確定的なブロックチェーン150となる。
ほとんどのブロックチェーンでは、勝ったマイナー104Mは、自動的に、(あるユーザーから別のユーザーにある量のデジタル資産を移転する通常のトランザクションとは対照的に)新しい量のデジタル資産を無から創出する特別な種類の新しいトランザクションを用いて報酬を受ける。よって、勝ったノードは、ある量のデジタル資産を「採掘」したと言われる。この特殊なタイプのトランザクションは、「生成」トランザクションと呼ばれることもある。それは自動的に新しいブロック151nの一部を形成する。この報酬は、マイナー〔採掘者〕104Mが作業証明競争に参加するインセンティブを与える。通常の(非生成)トランザクション152は、しばしば、その出力の1つにおいて追加のトランザクション料をも指定し、そのトランザクションが含められたブロック151nを生成した勝ったマイナー104Mにさらに報酬を与える。
マイニング〔採掘〕に関わる計算資源のため、典型的には、少なくともマイナー・ノード104Mのそれぞれは、一つまたは複数の物理的サーバー・ユニットを含むサーバー、またはさらにはデータ・センター全体の形をとる。各転送ノード104Mおよび/または記憶ノード104Sも、サーバーまたはデータ・センターの形をとることができる。しかしながら、原則として、任意の所与のノード104は、ユーザー端末または互いにネットワーク接続されたユーザー端末のグループの形をとることができる。
各ノード104のメモリは、それぞれの役割(単数または複数)を実行し、ノード・プロトコルに従ってトランザクション152を処理するために、ノード104の処理装置上で動作するように構成されたソフトウェアを記憶する。本明細書においてノード104に帰されるいずれの動作も、それぞれのコンピュータ装置の処理装置上で実行されるソフトウェアによって実行されうることが理解されよう。ノード・ソフトウェアは、アプリケーション層で、一つまたは複数のアプリケーションにおいて実装されてもよく、あるいはオペレーティング・システム層またはプロトコル層のようなより下位の層で実装されてもよく、あるいはこれらの任意の組み合わせでもよい。また、本明細書で使用される用語「ブロックチェーン」は、当該種類の技術一般を指す一般的な用語であり、いかなる特定の固有のブロックチェーン、プロトコルまたはサービスにも限定しない。
ネットワーク101には、消費ユーザーの役割の複数の当事者103の各当事者のコンピュータ設備102も接続されている。これらは、トランザクションにおける支払人および払受人として行動するが、必ずしも他の当事者のための採掘または伝播トランザクションには参加しない。必ずしもマイニング・プロトコルを実行しない。2の当事者103およびそれぞれの設備102が例解目的のために示されている:第1の当事者103aおよびそのそれぞれのコンピュータ設備102a、ならびに第2の当事者103bおよびそのそれぞれのコンピュータ設備102bである。より多くのそのような当事者103およびそれらのそれぞれのコンピュータ設備102がシステムに存在し、参加することがありうるが、便宜上、それらは図示されていないことが理解されよう。各当事者103は、個人または組織でありうる。純粋に例示として、第1の当事者103aは、本明細書においてアリスと称され、第2の当事者103bは、ボブと称されるが、これは限定するものではなく、本明細書におけるアリスまたはボブという言及は、それぞれ「第1の当事者」および「第2の当事者」と置き換えることができることは理解されるであろう。
各当事者103のコンピュータ設備102は、一つまたは複数のプロセッサ、たとえば、一つまたは複数のCPU、GPU、他のアクセラレータ・プロセッサ、特定用途向けプロセッサ、および/またはFPGAを含むそれぞれの処理装置を備える。各当事者103のコンピュータ設備102は、さらに、メモリ、すなわち、非一時的なコンピュータ読み取り可能媒体またはメディアの形のコンピュータ読み取り可能記憶を備える。このメモリは、一つまたは複数のメモリ媒体、たとえばハードディスクなどの磁気媒体、SSD、フラッシュメモリまたはEEPROMなどの電子媒体、および/または光ディスク・ドライブなどの光媒体を使用する一つまたは複数のメモリユニットを含んでいてもよい。各当事者103のコンピュータ設備102上のメモリは、処理装置上で動作するように構成された少なくとも1つのクライアント・アプリケーション105のそれぞれのインスタンスを含むソフトウェアを記憶する。本明細書で所与の当事者103に帰されるいずれのアクションも、それぞれのコンピュータ設備102の処理装置上で実行されるソフトウェアを使用して実行されうることが理解されよう。各当事者103のコンピュータ設備102は、少なくとも1つのユーザー端末、たとえばデスクトップまたはラップトップコンピュータ、タブレット、スマートフォン、またはスマートウォッチのようなウェアラブルデバイスを含む。所与の当事者103のコンピュータ設備102は、ユーザー端末を介してアクセスされるクラウドコンピューティング資源のような、一つまたは複数の他のネットワーク化された資源を含んでいてもよい。
クライアント・アプリケーション105は、最初に、好適なコンピュータ読み取り可能な記憶媒体またはメディア上で任意の所与の当事者103のコンピュータ設備102に提供されてもよく、たとえばサーバーからダウンロードされ、あるいはリムーバブルSSD、フラッシュメモリ・キー、リムーバブルEEPROM、リムーバブル磁気ディスク・ドライブ、磁気フロッピー・ディスクまたはテープ、光ディスク、たとえばCDまたはDVD ROM、またはリムーバブル光学ドライブなどのリムーバブル記憶装置上で提供されてもよい。
クライアント・アプリケーション105は、少なくとも「ウォレット」機能を備える。これには主に2つの機能をもつ。これらのうちの一方は、それぞれのユーザー当事者103が、ノード104のネットワーク全体にわたって伝搬され、それによってブロックチェーン150に含まれるトランザクション152を作成し、署名し、送信することを可能にすることである。他方は、それぞれの当事者に、現在所有しているデジタル資産の量を報告することである。出力ベースのシステムでは、この第2の機能は、ブロックチェーン150全体に散在する、当該当事者に属するさまざまな152トランザクションの出力において定義される量を照合することを含む。
注:さまざまなクライアント機能は、所与のクライアント・アプリケーション105に統合されているものとして記載されることがあるが、これは必ずしも限定的なものではなく、むしろ、本明細書に記載されている任意のクライアント機能は、その代わりに、2つ以上の別個のアプリケーションのスイートにおいて実装されてもよい。該2つ以上のアプリケーションは、たとえばAPIを介してインターフェースする、または一方が他方へのプラグインである。より一般的には、クライアント機能は、アプリケーション層、またはオペレーティング・システムなどのより下位の層、またはこれらの任意の組み合わせで実装できる。以下は、クライアント・アプリケーション105に関して説明されるが、これは限定的ではないことが理解されるであろう。
各コンピュータ設備102上のクライアント・アプリケーションまたはソフトウェア105のインスタンスは、P2Pネットワーク106の転送ノード104Fの少なくとも1つに動作上結合される。これは、クライアント105のウォレット機能が、トランザクション152をネットワーク106に送信することを可能にする。クライアント105は、それぞれの当事者103が受領者である任意のトランザクションについてブロックチェーン150に照会するために(あるいは実は、諸実施形態においてブロックチェーン150は、部分的にはそれが公に見えることを通じてトランザクションの信用を提供する公共施設であるため、ブロックチェーン150内の他の当事者のトランザクションを検査するために)、記憶ノード104のうちの1つ、一部、または全部にコンタクトすることもできる。各コンピュータ設備102上のウォレット機能は、トランザクション・プロトコルに従ってトランザクション152を定式化し、送信するように構成される。各ノード104は、ノード・プロトコルに従ってトランザクション152を有効確認し、転送ノード104Fの場合は、ネットワーク106全体に伝播させるためにトランザクション152を転送するように構成されたソフトウェアを実行する。トランザクション・プロトコルとノード・プロトコルは互いに対応し、所与のトランザクション・プロトコルは所与のノード・プロトコルとともに、所与のトランザクション・モデルを実装する。同じトランザクション・プロトコルが、ブロックチェーン150内のすべてのトランザクション152について使用される(ただし、トランザクション・プロトコルは、その中でトランザクションの異なるサブタイプを許容してもよい)。同じノード・プロトコルが、ネットワーク106内のすべてのノード104によって使用される(ただし、トランザクションの異なるサブタイプを、そのサブタイプについて定義された規則に従って異なる仕方で扱ってもよく、また、異なるノードは異なる役割を担い、よって、プロトコルの異なる対応する側面を実装してもよい)。
上述したように、ブロックチェーン150はブロック151のチェーンを含み、各ブロック151は、上述したように、作業証明プロセスによって作成された一つまたは複数のトランザクション152の集合を含む。各ブロック151は、また、ブロック151への逐次的順序を規定するように、チェーン内の先に生成されたブロック151を遡ってポイントするブロック・ポインタ155を含む。ブロックチェーン150はまた、作業証明プロセスによって新しいブロックに含まれることを待つ有効なトランザクション154のプールを含む。各トランザクション152(生成トランザクション以外)は、トランザクションの諸シーケンスに対する順序を定義するよう、前のトランザクションを遡ってポイントするポインタを含む(トランザクション152の諸シーケンスは、分岐することが許容される)。ブロック151のチェーンは、チェーン内の第1のブロックであった生成ブロック(Gb)153まで遡る。チェーン150内の早期の一つまたは複数のオリジナル・トランザクション152は、先行トランザクションではなく創生ブロック(genesis block)153をポイントした。
所与の当事者103、たとえばアリスが、ブロックチェーン150に含められるよう、新しいトランザクション152jを送信することを望む場合、アリスは、関連するトランザクション・プロトコルに従って(アリスのクライアント・アプリケーション105においてウォレット機能を使用して)新しいトランザクションを定式化する。アリスは次いで、トランザクション152を、クライアント・アプリケーション105から、自分が接続されている一つまたは複数の転送ノード104Fの1つに送信する。たとえば、これは、アリスのコンピュータ102に最も近いか、または最も良好に接続されている転送ノード104Fでありうる。任意の所与のノード104は、新しいトランザクション152jを受信すると、それをノード・プロトコルおよびそのそれぞれの役割に従って処理する。これは、まず、新たに受信されたトランザクション152jが「有効」であるためのある種の条件を満たすかどうかをチェックすることを含む。その例については、手短に、より詳細に論じる。いくつかのトランザクション・プロトコルでは、有効確認のための条件は、トランザクション152に含まれるスクリプトによってトランザクションごとに構成設定可能でありうる。あるいはまた、条件は単に、ノード・プロトコルの組み込み特徴であってもよく、あるいはスクリプトとノード・プロトコルの組み合わせによって定義されてもよい。
新たに受信されたトランザクション152jが、有効であるとみなされるテストを通過するという条件で(すなわち、「有効確認される」という条件で)、トランザクション152jを受信する任意の記憶ノード104Sは、そのノード104Sにおいて維持されているブロックチェーン150のコピー内のプール154に、新たに有効確認されたトランザクション152を追加する。さらに、トランザクション152jを受信する任意の転送ノード104Fは、有効確認されたトランザクション152をP2Pネットワーク106内の一つまたは複数の他のノード104にさらに伝搬させる。各転送ノード104Fは同じプロトコルを適用するので、トランザクション152jが有効であると想定すると、これは、そのトランザクションがまもなくP2Pネットワーク106全体に伝搬させられることを意味する。
ひとたび一つまたは複数の記憶ノード104で維持されるブロックチェーン150のコピー内のプール154に受け入れられたら、マイナー・ノード104Mは、新しいトランザクション152を含むプール154の最新バージョンに関する作業証明パズルを解くために競争を開始する(他のマイナー104Mが依然としてプール154の古いビューに基づいてパズルを解こうとしていることがありうるが、誰であれ先に到達した者が、どこで次の新しいブロック151が終了し、新しいプール154が始まるかを定義し、最終的には、誰かが、アリスのトランザクション152jを含むプール154の一部についてのパズルを解くであろう)。ひとたび新しいトランザクション152jを含むプール154について作業証明が行われると、それは、変更不能な形で、ブロックチェーン150内のブロック151のうちの1つのブロックの一部となる。各トランザクション152は、以前のトランザクションへのポインタを含むので、トランザクションの順序も、変更不能な形で記録される。
異なるノード104は所与のトランザクションの異なるインスタンスを最初に受信し、よって、1つのインスタンスがブロック150中にマイニングされるまでは、どのインスタンスが「有効」かの対立する見解をもつことがある。マイニングされた時点で、すべてのノード104は、マイニングされたインスタンスが唯一の有効なインスタンスであると合意する。ノード104があるインスタンスを有効であると受け入れ、その後第2のインスタンスがブロックチェーン150に記録されていることを発見する場合は、そのノード104はこのことを受け入れなければならず、当初受け入れた、マイニングされていないインスタンスを破棄する(無効として扱う)ことになる。
1.2 UTXOベースのモデル
図2は、例示的なトランザクション・プロトコルを示す。これは、UTXOベースのプロトコルの例である。トランザクション152(「Tx」と略す)は、ブロックチェーン150の基本的なデータ構造である(各ブロック151は一つまたは複数のトランザクション152を含む)。以下は、出力ベースまたは「UTXO」ベースのプロトコルを参照して説明される。しかしながら、これは、すべての可能な実施形態に対して限定するものではない。
UTXOベースのモデルでは、各トランザクション(「Tx」)152は、一つまたは複数の入力202および一つまたは複数の出力203を含むデータ構造を含む。各出力203は、未使用のトランザクション出力(UTXO)を含んでいてもよく、これは、別の新しいトランザクションの入力202のためのソースとして使用できる(UTXOがまだ償還されていない場合)。UTXOは、デジタル資産(価値のストア)の量を指定する。UTXOは、他の情報の中でも、それが由来するところのトランザクションのトランザクションIDをも含んでいてもよい。トランザクション・データ構造はまた、入力フィールド(単数または複数)202および出力フィールド(単数または複数)203のサイズのインジケータを含んでいてもよいヘッダ201を含んでいてもよい。ヘッダ201はまた、トランザクションのIDを含んでいてもよい。諸実施形態において、トランザクションIDは、トランザクション・データ(トランザクションID自体を除く)のハッシュであり、マイナー104Mに提出された生のトランザクション152のヘッダ201に格納される。
アリス103aは、問題のデジタル資産の量をボブ103bに移転するトランザクション152jを作成したいとする。図2において、アリスの新しいトランザクション152jは、「Tx1」とラベル付けされている。これは、シーケンスにおいて先行するトランザクション152iの出力203においてアリスにロックされているデジタル資産のうちのある量を取り、その少なくとも一部をボブに移転する。先行するトランザクション152iは、図2において「Tx0」とラベル付けされている。Tx0およびTx1は、単に任意のラベルである。これらは、必ずしも、Tx0がブロックチェーン151における第1のトランザクションであること、または、Tx1がプール154におけるすぐ次のトランザクションであることを意味しない。Tx1は、アリスにロックされた未使用出力203を依然として有する、任意の先行する(すなわち先立つ)トランザクションを遡ってポイントすることができる。
先行するトランザクションTx0は、アリスがその新しいトランザクションTx1を作成する時点において、または少なくともアリスがそれをネットワーク106に送信する時点までに、すでに検証され、ブロックチェーン150に含められてもよい。それは、その時点ですでにブロック151のうちの1つに含まれてもよく、あるいは、プール154内でまだ待機していてもよく、その場合、まもなく新しいブロック151に含まれることになる。あるいはまた、Tx0およびTx1が一緒に生成されてネットワーク102に送信されることができ、あるいはさらには、ノード・プロトコルが「オーファン」トランザクションをバッファリングすることを許容する場合にはTx0がTx1の後に送信されることもできる。本明細書においてトランザクションのシーケンスの文脈で使用される「先行」および「後続」という用語は、トランザクション中に指定されたトランザクション・ポインタ(どのトランザクションがどの他のトランザクションをポイントするかなど)によって定義されるシーケンスにおけるトランザクションの順序のことをいう。それらの用語は、「先行者」および「後継者」または「先立つ」および「子孫」、「親」および「子」などに等しく置き換えることができる。これは、必ずしもそれらが作成される、ネットワーク106に送られる、または任意の所与のノード104に到達する順序を意味するわけではない。にもかかわらず、先行トランザクション(先立つトランザクションまたは「親」)をポイントする後続トランザクション(子孫トランザクションまたは「子」)は、親トランザクションが有効確認されない限り、有効確認されない。親より先にノード104に到着する子は、オーファンとみなされる。オーファンは、ノード・プロトコルおよび/またはマイナー挙動に依存して、破棄されてもよく、あるいは親を待つために、ある時間にわたってバッファリングされてもよい。
先行するトランザクションTx0の一つまたは複数の出力203のうちの1つは、本明細書でUTXO0とラベル付けされる特定のUTXOを含む。各UTXOは、UTXOによって表されるデジタル資産の量を指定する値と、ロック・スクリプトとを含む。ロック・スクリプトは、後続のトランザクションが有効確認されるため、よってUTXOが正常に償還されるために、後続のトランザクションの入力202においてロック解除スクリプトによって満たされなければならない条件を定義する。典型的には、ロック・スクリプトは、前記量を特定の当事者(それが含まれているトランザクションの受益者)にロックする。すなわち、ロック・スクリプトは、ロック解除条件を定義し、典型的には、後続のトランザクションの入力におけるロック解除スクリプトが、先行するトランザクションがロックされている当事者の暗号署名を含むという条件を含む。
ロック・スクリプト(別名scriptPubKey)は、ノード・プロトコルによって認識されるドメイン固有の言語で書かれたコードである。そのような言語の特定の例は、「Script」(大文字のS)と呼ばれる。ロック・スクリプトは、トランザクション出力203を使用するためにどんな情報が必要とされるか、たとえば、アリスの署名を要求することを指定する。トランザクションの出力には、ロック解除スクリプトが現れる。ロック解除スクリプト(別名scriptSig)は、ロック・スクリプト基準を満たすために必要とされる情報を提供する、ドメイン固有の言語で書かれたコードである。たとえば、ボブの署名を含んでいてもよい。ロック解除スクリプトは、トランザクションの入力202に現れる。
図示した例では、Tx0の出力203におけるUTXO0は、ロック・スクリプト[Checksig PA]を含み、これは、UTXO0が償還されるために(厳密には、UTXO0を償還しようとする後続のトランザクションが有効であるために)、アリスの署名Sig PAを要求する。[Checksig PA]は、アリスの公開鍵・秘密鍵のペアからの公開鍵PAを含む。Tx1の入力202は、Tx1を指す(たとえば、諸実施形態ではトランザクションTx0全体のハッシュであるそのトランザクションID、TxID0によって)ポインタを含む。Tx1の入力202は、Tx0の任意の他の可能な出力の中でそれを識別するために、Tx0内のUTXO0を識別するインデックスを含む。Tx1の入力202は、さらに、鍵ペアからのアリスの秘密鍵をデータの所定の部分(暗号学において時に「メッセージ」と呼ばれる)に適用することによって作成された、アリスの暗号署名を含むロック解除スクリプト<Sig PA>を含む。有効な署名を提供するためにアリスによって署名される必要があるデータ(または「メッセージ」)は、ロック・スクリプトによって、またはノード・プロトコルによって、またはこれらの組み合わせによって定義されうる。
新しいトランザクションTx1がノード104に到着すると、ノードはノード・プロトコルを適用する。これは、ロック解除スクリプトがロック・スクリプトにおいて定義されている条件を満たしているかどうかをチェックするために、ロック・スクリプトとロック解除スクリプトを一緒に実行する(この条件は一つまたは複数の基準を含みうる)。諸実施形態において、これは、2つのスクリプトを連結することを含む:
<Sig PA><PA>||[Checksig PA]
ここで、「||」は連結を表し、「<…>」は、データをスタック上に置くことを意味し、「[…]」はロック解除スクリプト(この例ではスタックベースの言語)に含まれる関数である。同じことだが、スクリプトを連結するのではなく、共通のスタックを用いてスクリプトが順次実行されてもよい。いずれにせよ、一緒に実行されたとき、それらのスクリプトは、Tx0の出力におけるロック・スクリプトに含まれるアリスの公開鍵PAを使用して、Tx1の入力におけるロック・スクリプトが、データの期待される部分に署名するアリスの署名を含むことを認証する。この認証を実行するためには、データの期待される部分自体(「メッセージ」)もTx0に含める必要がある。諸実施形態において、署名されたデータは、Tx0の全体を含む(よって、データの署名された部分がすでに内在的に存在するので、データの署名された部分を平文で指定する別個の要素が含まれる必要はない)。
公開‐秘密暗号による認証の詳細は、当業者にはおなじみであろう。基本的には、アリスが自分の秘密鍵を用いてメッセージを暗号化することによってメッセージに署名した場合、アリスの公開鍵と平文でのそのメッセージ(暗号化されていないメッセージ)を与えられると、ノード104のような別のエンティティは、そのメッセージの暗号化されたバージョンがアリスによって署名されたものであるはずであると認証することができる。署名することは、典型的には、メッセージをハッシュし、ハッシュに署名し、それを署名としてメッセージの平文バージョンにタグ付けし、それにより、公開鍵の任意の保持者が署名を認証することを可能にする。よって、本稿における、ある特定のデータまたはトランザクションの一部に署名することなどへの任意の言及は、諸実施形態においては、そのデータまたはトランザクションの一部のハッシュに署名することを意味することができる。
Tx1のロック解除スクリプトが、Tx0のロック・スクリプトにおいて指定された一つまたは複数の条件を満たす場合(示した例では、アリスの署名がTx1において提供され、認証された場合)、ノード104は、Tx1が有効であるとみなす。それがマイニング・ノード104Mである場合、このことは、それが作業証明を待つトランザクションのプール154にそれを追加することを意味する。それが転送ノード104Fである場合、それは、ネットワーク全体に伝搬されるよう、トランザクションTx1をネットワーク106内の一つまたは複数の他のノード104に転送する。ひとたびTx1が有効確認され、ブロックチェーン150に含められると、これは、Tx0からのUTXO0を使用済みとして定義する。Tx1は、未使用のトランザクション出力203を使用する場合にのみ有効でありうることに留意されたい。別のトランザクション152によってすでに使用された出力を使用しようとする場合、たとえ他のすべての条件が満たされていても、Tx1は無効となる。よって、ノード104は、先行するトランザクションTx0における参照されたUTXOがすでに使用されているかどうか(すでに別の有効なトランザクションへの有効な入力を形成しているかどうか)もチェックする必要がある。これが、ブロックチェーン150がトランザクション152に関する定義された順序を課すことが重要である理由の1つである。実際上は、所与のノード104は、トランザクション152が使用されたUTXO 203をマークする別個のデータベースを維持してもよいが、最終的には、UTXOが使用されたかどうかを定義するのは、ブロックチェーン150内の別の有効なトランザクションへの有効な入力をすでに形成しているかどうかである。
所与のトランザクション152のすべての出力203において指定された総量が、そのすべての入力202によってポイントされた総量よりも大きい場合、これは、ほとんどのトランザクション・モデルにおいて無効性の別の根拠である。したがって、そのようなトランザクションは、伝搬されたり、ブロック151中にマイニングされたりすることはない。
UTXOベースのトランザクション・モデルでは、所定のUTXOが全体として使用される必要があることに注意されたい。使用されるUTXOにおいて定義されている量のうち、別の量が使用される一方で一部を「残しておく」ことはできない。ただし、UTXOからの前記量は、次のトランザクションの複数の出力のあいだで分割できる。たとえば、Tx0におけるUTXO0において定義された量は、Tx1における複数のUTXOの間で分割できる。よって、アリスがボブにUTXO0で定義された量のすべてを与えることを望まない場合、残りを使って、Tx1の第2の出力において自分自身におつりを与えたり、あるいは別の当事者に支払ったりすることができる。
実際上は、アリスは通例、勝ったマイナーのための料金を含める必要もある。なぜなら、今日では、生成トランザクションの報酬だけでは、典型的には、採掘を動機づけるには十分ではないからである。アリスがマイナーのための手数料を含めない場合、Tx0は諸マイナー・ノード104Mによって拒否される可能性が高く、よって、技術的には有効であるが、それはまだ伝播され、ブロックチェーン150に含められることはない(マイナー・プロトコルは、マイナー104Mに望まない場合には、トランザクション152を受け入れるようマイナー104Mに強制しない)。いくつかのプロトコルでは、採掘料金は、独自の別個の出力203を必要としない(すなわち、別個のUTXOを必要としない)。その代わりに、所与のトランザクション152の入力(単数または複数)202によってポイントされる総量と出力(単数または複数)203において指定される総量との間の任意の差は、勝ったマイナー104に自動的に与えられる。たとえば、UTXO0へのポインタがTx1への唯一の入力であり、Tx1は1つの出力UTXO1しかもたないとする。UTXO0において指定されたデジタル資産の量がUTXO1において指定された量より多い場合、その差は自動的に勝ったマイナー104Mのものとなる。しかしながら、代替的または追加的に、トランザクション152のUTXO 203のうちの独自のものにおいてマイナー手数料が明示的に指定できることは必ずしも除外されない。
アリスおよびボブのデジタル資産は、ブロックチェーン150内の任意のところで任意のトランザクション152において、両者にロックされた未使用UTXOからなる。よって、典型的には、所与の当事者103の資産は、ブロックチェーン150を通じて、さまざまなトランザクション152のUTXO全体に分散される。ブロックチェーン150内のどこにも、所与の当事者103の総残高を定義する1つの数は記憶されていない。それぞれの当事者にロックされ、別の前進(onward)トランザクションにまだ使用されていないすべてのさまざまなUTXOの値を一緒に照合することは、クライアント・アプリケーション105におけるウォレット機能の役割である。これは、記憶ノード104Sのいずれか、たとえばそれぞれの当事者のコンピュータ設備102に最も近いか、または最も良好に接続されている記憶ノード104Sに記憶されているブロックチェーン150のコピーを問い合わせることによってできる。
スクリプト・コードは、概略的に表現されることが多い(すなわち、正確な言語ではない)ことに注意されたい。たとえば、[Checksig PA]と書いて、[Checksig PA]=OP_DUP OP_HASH160<H(PA)>OP_EQUALVERIFY OP_CHECKSIGを意味することができる。「OP_....」は、Script言語の特定のオペコードを指す。OP_CHECKSIG(「Checksig」とも呼ばれる)は、2つの入力(署名および公開鍵)を取り、楕円曲線デジタル署名アルゴリズム(ECDSA)を使用して署名の有効性を検証するScriptオペコードである。ランタイムでは、署名('sig')の発生はすべてスクリプトから除去されるが、ハッシュ・パズルなどの追加要件が、'sig'入力によって検証されるトランザクションに残る。別の例として、OP_RETURNは、トランザクション内にメタデータを格納し、それによりブロックチェーン150において変更不能な形でメタデータを記録することができるトランザクションの使用不能な(unspendable)出力を生成するためのScript言語のオペコードである。たとえば、メタデータは、ブロックチェーンに格納することが望まれる文書を含むことができる。
署名PAは、デジタル署名である。諸実施形態において、これは楕円曲線secp256k1を使用するECDSAに基づく。デジタル署名は、特定のデータに署名する。諸実施形態において、所与のトランザクションについて、署名は、トランザクション入力の一部、およびトランザクション出力の全部または一部に署名する。署名される出力の特定の部分はSIGHASHフラグに依存する。SIGHASHフラグは、署名の末尾に含まれる4バイトのコードであり、どの出力が署名されるか(よって、署名の時点において固定されるか)を選択する。
ロック・スクリプトは、それぞれのトランザクションがロックされる当事者の公開鍵を含んでいるという事実を指して、「scriptPubKey」と呼ばれることがある。ロック解除スクリプトは、対応する署名を供給するという事実を指して「scriptSig」と呼ばれることがある。しかしながら、より一般には、UTXOが償還されるための条件が署名を認証することを含むことは、ブロックチェーン150のすべてのアプリケーションにおいて必須ではない。より一般的には、スクリプト言語を使用して、一つまたは複数の条件を定義することができる。よって、より一般的な用語である「ロック・スクリプト」および「ロック解除スクリプト」が好まれることがある。
寄与者階層構造
図18Aは、本明細書において寄与者の「外部階層構造」(寄与者階層構造)と呼ばれるものの概略ブロック図を示す。階層構造内の各寄与者は、究極的に最終的な「作品」のベースとなる何らかの定義された寄与を行う人またはその他のエンティティである。
本開示の中核的な目的は、そのような階層構造を、変更不能な仕方でブロックチェーン150に記録されうるブロックチェーン・トランザクションの集合において表現することである。
「著者」(author)および「寄与者」(contributor)という用語は、この説明では交換可能に使用されていることに注意されたい。
図18Aの例示的な外部階層構造では、2つの異なる分枝が存在する。左側に示されている第1の分岐では、第1のグループの「下位著者」C-Aが階層構造におけるレベル4にあると言われる。第1グループの下位著者C-Aは、それぞれC-A0~C-A4の参照符号で示される5名の下位著者からなる。各人は、それぞれP-A0~P-A4と示される公開鍵によって一意的に識別される。各人は、データ・ブロックとして具現される、それぞれD-A0~D-A4と示される別個の個別の寄与をする。
用語「データ・ブロック」は、本願の文脈では、文書、ファイルまたは他のデータ・ブロックのような、個々の寄与者の寄与を捕捉するデータの集合または一部を指すために使用されることに留意されたい。これは、ブロックチェーン150のブロック151とは全く異なる。用語「データ・ブロック」および「データ・オブジェクト」は、本明細書において同義で使用される。
下位著者C-Aの第1のグループは、階層構造におけるレベル3にいる「上位著者」によって監督される。第1の下位著者グループC-Aを監督する上位著者は、第1のレベル3上位著者と呼ばれてもよく、参照符号C-C0で示される。彼(彼女/それを含む)は、公開鍵P-C0によって一意的に識別され、彼が監督する下位著者の寄与C-A0~C-A4に応答して寄与D-C0を行う。第1のレベル3の上位著者C-C0は、第1のレベル2の上位著者C-E0によって監督される。レベル2の上位著者C-E0は、公開鍵P-E0によって一意的に識別され、第1のレベル3の上位著者C-C0の寄与に応答して自らの寄与D-E0をする。
右側に示される階層構造の分枝では、下位著者C-Bの第2のグループ(この例では3人の下位著者C-B0~C-B2からなる)が、それぞれP-B0~P-B2の参照符号で示される一意的な公開鍵に関連付けられ、それぞれ個別の寄与D-B0~D-B2をする。
下位著者C-Bの第2のグループは、第2のレベル3の上位著者C-D0によって監督され、該上位著者は、公開鍵P-D0によって識別され、自分が監督する下位著者C-B0~C-B2の寄与D-B0~D-B2に応答して自分自身の寄与D-D0をする。
第2のレベル3の上位著者C-Dは、第2のレベル2の上位著者C-F0および第3のレベル2の上位著者C-F1と呼ばれる2人のレベル2の上位著者によって監督される。
第2および第3のレベル2の上位著者C-F0、C-F1は、それぞれ参照符号P-F0およびP-F1で示される公開鍵によって識別され、両名が合同して監督する第1のレベル3の上位著者C-D0の寄与D-D0に応答して、それぞれ参照符号D-F0およびD-F1で示される、自分自身の個別の寄与をする。
階層構造のレベル1の主任編集者C-G0は、参照符号Dで示される最終的な作品(彼の寄与)について最終的な責任を負い、レベル2の上位著者C-E0、C-F0、C-F1の3人すべてを監督する役割を担う。主任編集者は公開鍵P-G0によって識別される。
図示されていないが、階層構造の最上部(レベル0)には、最終的な作品Dが提出される著作権機関(copyright authority)がある。
図18Bは、さまざまな寄与者によってなされた個々の寄与だけでなく、寄与者自身の間の階層的関係のために生じるそれらの寄与の間の階層的関係の証拠を与えるために使用されうるデータ構造の例を示す。データ構造は、本明細書において「一般化ハッシュ・ツリー」1820と称されるものの形である。一般化ハッシュ・ツリーについては、以下でさらに詳しく説明する。当面は、一般化ハッシュ・ツリーは「古典的な」ハッシュ・ツリーと共通のいくつかの特性をもつが、より制約が少なく、古典的なハッシュ・ツリーでは可能でない仕方で階層的関係を表現するように構築されうると言えば十分である。一般化ハッシュ・ツリー1820は、ツリー内のそれぞれのレベルにある複数のノードと、それらのノードの間の方向性エッジとで形成され、ここで、各ノードは、下線の付いたデータ・ブロックのハッシュ(白丸として表されるリーフ・ノード)またはその「子ノード」の値の連結のハッシュ(黒丸として表される非リーフ・ノード)のいずれかである。手短に言うと、古典的なハッシュ・ツリーとは対照的に、各非リーフ・ノードは、任意の数の子をもつことができ、その結果、異なる非リーフ・ノードが異なる数の子を有することがあり、さらに、非リーフ・ノードが階層構造における任意のレベルで現れることができ、その結果、非リーフ・ノードは、リーフ・ノードと非リーフ・ノードの組み合わせである子を有する可能性がある。
以下でさらに詳細に議論される理由により、一般化ハッシュ・ツリーは、図18Aに示された種類の階層的関係を表現する新規かつ有用な方法を提供する。しかしながら、一般化ハッシュ・ツリーの基礎原理をより詳細に記述する前に、ブロックチェーン150上で図18Bに示された種類の一般化ハッシュ・ツリーを具現するために、ブロックチェーン・トランザクション152の集合1920(後述する図19Aおよび19Bに示される)が構築されうるプロトコルの概要が提供される。すなわち、ノードの値(参照符号H2-A0~RH)だけでなく、それらのノード間の階層的な関係を完全にエンコードするような仕方でブロックチェーン・トランザクションを構築するためのプロトコルである。本明細書では、このプロトコルを「協働的認証プロトコル(collaborative attestation protocol)」と呼ぶことがある。協働的認証プロトコルを支えるいくつかの一般的な原理および考察は、後述する。まず、プロトコルに従って実行される方法の具体的な例を、コンテキストを提供するために記述する。
ブロックチェーン・トランザクションの集合1920を記述する前に、一般化ハッシュ・ツリー1820の構造が、図18Aの寄与者階層構造に関連して記述される。図18Aの例に従うと、各寄与は、外部階層構造における寄与者のレベルに対応する、一般化ハッシュ・ツリー1820内のレベルにあるリーフ・ノードによって表される(すなわち、レベルnにおける任意の著者による寄与は、一般化ハッシュ・ツリー内のレベルnにおけるリーフ・ノードによって表される)。
よって、下位著者C-Aの第1のグループの寄与は、一般化ハッシュ・ツリー1820の階層構造におけるレベル4の5つのリーフ・ノードによって表される。それらのノードはそれぞれの値をもち、それぞれH2-A0からH2-A4の参照符号で表される。図18Bでは、過剰な混雑を避けるため、参照符号の一部を省略していることに注意されたい。この例では、各非リーフ・ノードの値は、それが対応する基礎となる寄与の二重ハッシュである。よって、たとえば、寄与D-A1に対応するリーフ・ノードの値H2-A1は、寄与D-A1の二重ハッシュであり、寄与D-A4を表すリーフ・ノードの値H2-A4は、その寄与D-A4の二重ハッシュである、などとなる。
同様に、下位著者の第2のグループC-Bについては、各寄与は、その寄与を二重ハッシュすることによって得られる値を有する、一般化ハッシュ・ツリー1820の階層構造内のレベル4のリーフ・ノードによって表される。たとえば、寄与D-B2に対応するノードの値H2-B2は、その寄与の二重ハッシュである。
一般化ハッシュ・ツリー1800のレベル3では、下位著者C-AおよびC-Bの各グループによる全体的な寄与は、それぞれの非リーフ・ノードIH-AおよびIH-Bによって表される。下位著者の第1のグループC-Aの全体的な寄与を表す非リーフIH-Aの値は、下位著者の第1のグループC-Aの寄与を表すリーフ・ノードすべての値の連結の単一ハッシュである、すなわち、下位著者の第1のグループC-Aによる個々の寄与を表すリーフ・ノード値H2-A0からH2-A4の連結の単一のハッシュである。同様に、下位著者の第2のグループC-Bの全体的な寄与を表す非リーフ・ノードの値IH-Bは、その個々の寄与D-B0からD-B2を表すリーフ・ノードの値H-B0からH-B2の連結の単一のハッシュである。
さらに、各レベル3の上位著者C-C0、C-D0の寄与は、それぞれH2-C0およびH2-D0の参照符号で示される、一般化ハッシュ・ツリー1820におけるレベル3のリーフ・ノードによって表され、そのそれぞれは、その上位著者の個々の寄与D-C0、D-D0の二重ハッシュである。
一般化ハッシュ・ツリー1820のレベル2では、下位著者の第1のグループC-Aの全体的な寄与が、そのグループを監督する第1のレベル2の上位著者C-C0の寄与と一緒に、値IH-Cをもつ単一の非リーフ・ノードによって表される。その値は、下位著者の第1のグループC-Aの全体的な寄与を表す値IH-Aと、第1のレベル3の上位著者C-C0の寄与を表すレベル2のリーフ・ノードの値H2-C0との連結である。
下位著者の第2のグループC-Bの全体的な寄与は、そのグループを監督する第2のレベル3の上位著者C-D0の寄与と一緒に、同様に計算された値IH-Dをもつ、レベル2の第2の非リーフ・ノードによって表される。
寄与者階層構造には、C-E0、C-F0、C-F1の3人のレベル2の上位著者があり、それぞれが個別の寄与D-E0、D-F0、D-F1をするため、一般化ハッシュ・ツリー1820は、それらの寄与D-E0、D-F0、D-F1のそれぞれを表すレベル2の3つのリーフ・ノードを含む。これらの各リーフ・ノードの値H2-E0、H2-F0およびH2-F1は、そのノードによって表される寄与の二重ハッシュとして計算される。
一般化ハッシュ・ツリーのレベル1では、それぞれ参照符号IH-EおよびIH-Fで示される値をもつ2つの非リーフ・ノードがある。値IH-Eをもつ非リーフ・ノードは、下位著者の第1のグループC-Aの全体的な寄与を、そのグループを監督する第1のレベル3の上位著者C-C0の寄与D-C0と、彼を監督する第1のレベル2の上位著者C-E0の寄与D-E0とともに、表す。ここでもまた、その値IH-Eは、値IH-C(下位著者の第1のグループC-Aの全体的な寄与に、その直接の監督者C-C0の寄与を加えたもの)と、第1のレベル2の上位著者C-E0の寄与D-E0を表すリーフ・ノードH2-E0の値との連結のハッシュとして計算される。
もう一方のレベル2の非リーフ・ノードは、該非リーフ・ノードの値IH-D(第2の下位著者グループC-Bと、それを直接監督する第2のレベル2の上位著者C-D0の寄与を表す)を、第2のレベル2の上位著者H2-D0を監督する第2および第3のレベル2の上位著者の寄与D-F0、D-F1を表す2つのリーフ・ノードの2つの値H2-F0、H2-F1と連結した連結として計算された値IH-Fをもつ。
レベル1のリーフ・ノードは、主任編集者の寄与C-G0を表す。これは、レベル2の上位著者の寄与D-E0、D-F0、D-F1に応答して主任編集者が作成した最終的な作品Dである。そのノードH2-G0の値は、最終的な作品Dの二重ハッシュとして計算される。
最後に、一般化ハッシュ・ツリーのレベル0において、ルート・ノードが、レベル1における非リーフ・ノードの値IH-E、IH-Fと、レベル1におけるリーフ・ノードの値H2-G0との連結の単一のハッシュとして計算される値RH(ルート・ハッシュ)を有する。
ここで、図19Aおよび図19Bを参照して、協働的認証プロトコルに従って実施される方法の一例を説明する。本方法は、図18Bの一般化ハッシュ・ツリー1820を具現するブロックチェーン・トランザクションの集合1920を作成する。
本方法(プロトコル)のステップは、図19Aおよび19Bにおいて、ページの上部の左から右に水平に走るフローチャートで示される。フローチャートの各ステップの下には、トランザクションの集合1920のうちの一つまたは複数のトランザクションの対応するサブセットが概略的に示されている。これは、そのステップで作成されたトランザクションである。最初のステップを除く各ステップで、前のステップで作成されたトランザクションと特定の使用関係(spending relationship)をもつ少なくとも1つの使用トランザクション(spending transaction)が作成される。図18Bの一般化ハッシュ・ツリー内のノード間の階層的関係を表すのは、これらの使用関係である。ノード自体の値は、さらに詳細に後述するように、トランザクション1920の出力においてエンコードされる。
図19Aから始めると、ステップ1900で、各下位著者グループC-A、C-Bの各下位著者は、自分の公開鍵にロックされた少なくとも1つの使用可能出力をもつ初期トランザクションを作成する。ステップ1900で、下位著者C-Aの第1のグループによって作成されたトランザクションは、それぞれTX-A0からTX-A4と表され、それぞれが、それを作成した下位著者の公開鍵P-A0、…、P-A4にロックされた少なくとも1つの使用可能な出力を有する(すなわち、各出力は、下位著者C-Aの第1のグループの異なる下位著者にロックされる)。あるいはまた、これらのトランザクションのうちの一つまたは複数は、他の任意の当事者によって作成されることも可能である。あるいはまた、これらのトランザクションすべての一部が単一のトランザクションに組み合わされることもできる。重要なのは、この方法の次のステップをセットアップするために、(少なくとも1つ、最大で5つのトランザクションにおける)5つの別々の使用可能な出力があり、そのそれぞれが、第1のグループC-Aの下位著者のうちの異なる下位著者の公開鍵にロックされているということである。たとえば、署名のために使用される鍵の順序が下位著者の順序を保存するマルチ署名(または、多くの署名をもつ類似のスクリプト)をセットアップすることによって、著者とそのコンテンツ間の関係の間の、1対1で識別できるマップを維持しながら、ツリーの構造を捕捉することができる。
下位著者の第2のグループC-Bによって作成されたトランザクションは、TX-B0からTX-B2の参照符号で示され、それぞれは、第2の下位著者グループC-Bのうちの異なる下位著者の公開鍵P-B0,…,P-B2にロックされた少なくとも1つの使用可能な出力をもつ。初期トランザクションを構築する代替的な方法に関する前段の説明は、等しく適用される。
ステップ1902では、各下位著者グループC-A、C-Bは、単一の使用トランザクション(すなわち、下位著者グループ当たり1つの使用トランザクション)を作成し、これは、ステップ1900で、そのグループの個々のメンバーによって作成された初期トランザクションのすべての出力を使用〔消費〕する。そのトランザクションは、第1のグループ・トランザクションTX-Aと呼ばれることもある。
よって、TX-A0からTX-A4の5つの初期トランザクションを自分たちの間で作成した下位著者の第1のグループC-Aの場合、ステップ1902では、そのグループC-Aが全体として、参照符号TX-Aで示される単一の使用トランザクションを作成する。このトランザクションは、前記5つの初期トランザクションTX-A0~TX-A4の使用可能な出力のうちの異なるものをそれぞれ使用する(すなわちポイントする)(少なくとも)5つの入力をもつ。
初期トランザクションTX-A0からTX-A4のそれぞれは、そのトランザクションの使用可能な出力が自分の公開鍵(それぞれP-A0からP-A4)にロックされているおかげで、第1のグループの下位著者G-Aのうちの異なる下位著者を識別することを思い出してほしい。初期トランザクションTX-A0からTX-A4の出力の5つすべてを使用する第1のグループ・トランザクションTX-Aは、その5人の下位著者が同じグループに属するという事実を捉える。本開示の用語を使用すると、それらの著者は「きょうだい」寄与者と称されてもよく、その寄与はきょうだい寄与と称されてもよい。第1のグループ使用トランザクションTX-Aは、少なくとも1つの使用可能出力をもつ。これは、下位著者の第1のグループC-Aを監督する、第1のレベル3の上位著者C-C0の公開鍵P-C0にロックされる。これは、ブロックチェーン・トランザクション1920の集合内で、その下位著者グループC-Aとその「直接の」監督者C-C0との間の階層的関係を捉える。
第1のグループ・トランザクションTX-Aは、各下位著者の寄与の証明のはたらきもする。その証明は、各下位著者からの「裁量署名」(discretionary signature)によって提供される。下位著者TX-A0~TX-A4の裁量署名は、それぞれDS-A0~DS-A4の参照符号で示されている。裁量署名は、以下にさらに詳細に記載される。当面は、裁量署名は、それが現れるトランザクションを有効確認する目的では無視される、すなわち、トランザクションを有効確認する目的ではマイナーは裁量署名を度外視し、裁量署名は、その著者の寄与の単一ハッシュと、その著者の公開鍵に対応する秘密鍵とに署名関数を適用することによって生成されると言えば十分である。よって、下位著者TX-A0の裁量署名DS-A0は、署名生成関数を、その著者の寄与D-A0の単一ハッシュと、その公開鍵P-A0の秘密鍵対応物に適用することによって計算される。これは、残りの下位著者にも同様に当てはまる。
第1のグループ・トランザクションTX-Aの使用可能な出力に戻ると、監督者C-C0の公開鍵P-C0にロックされるとともに、その出力のロック・スクリプトは、それぞれ、下位著者の寄与D-A0~D-A4の受領証明をも必要とする。今の例では、これは「二重ハッシュ・パズル」である、すなわち、ロック解除スクリプトは、各寄与の二重ハッシュを含み、寄与D-A0の二重ハッシュはH2-A0で表され、D-A1の寄与の二重ハッシュはH2-A1で表される、などとなる。このロック・スクリプトは、有効なトランザクション署名を含むロック・スクリプトによってのみ償還されることができ、ロック解除スクリプトはまた、各寄与についての二重ハッシュ・パズルを解くために、下位著者の寄与のそれぞれの単一ハッシュをも含まなければならない。
寄与D-A0の単一ハッシュはH-A0で示され、寄与D-A1の単一ハッシュはH-A1で示される、などとなる。これらは、第1の下位著者グループC-C0の直接の監督者(すなわち、第1のレベル3の上位著者C-C0)によって作成された第1の「レベル3」使用トランザクションTX-Cの入力に含まれることが示されている。
第1のレベル3使用トランザクションTX-Cは、ステップ1904で作成される。直接の監督者C-C0は、監督している下位著者C-Aから寄与D-A0~D-A4のすべてを受け取ってはじめて、単一ハッシュ値H-A0~H-A4を計算できるようになる(これを受け取ることによって、応答して自分自身の寄与D-C0を行うこともできるようになる)。よって、これらは、第1のレベル3使用トランザクションTX-Cにおいて、直接の監督者C-C0がそれらの寄与を受け取ったことの証明のはたらきをする。さらに、第1のレベル3使用トランザクションTX-Cの入力は、そのトランザクションTX-Cの出力(単数または出力)に署名する有効なトランザクション署名を含み、該署名は、(第1のグループ・トランザクションTX-Aの使用可能な出力において指定される)監督する著者C-C0の公開鍵P-C0の秘密鍵対応物を使用する。
第1のレベル3使用トランザクションTX-Cの出力に目を向けると、第1のレベル3の上位著者C-C0を監督する第1のレベル2の著者C-E0の公開鍵P-E0にロックされた少なくとも1つの使用可能な出力がある。使用可能な出力は、参照符号H2-C0で示される第1のレベル3の上位著者C-C0の寄与に関する二重ハッシュ・パズルをも含む。よって、その出力は、第1のレベル2の監督著者C-E0によってのみ、第1のレベル3の上位著者C-C0から後者の寄与D-C0を受け取った場合にのみ、使用されることができるので、前者はその寄与D-C0の単一のハッシュH-C0を、受領証明として提供することができる。加えて、第1のレベル3トランザクションTX-Cの一つまたは複数の出力は、図18Bにおいて、レベル3に示されている非リーフ・ノードのハッシュ値IH-Aを含み、これは第1のグループの下位著者C-Aすべての全体的な寄与を表す。これは以下で「要約ハッシュ」と呼ばれることがあり、トランザクションの集合におけるその非リーフ・ノードを明示的に(直接)エンコードする効果をもつ。
最後に、第1のレベル2トランザクションTX-Cは、第1のレベル3の上位著者自身の寄与D-C0の証明を、裁量署名DS-C0の形で含む。前記と同様に、これは、彼の寄与D-C0および公開鍵P-C0の秘密鍵対応物に署名関数を適用することによって生成される。
暫時ステップ1902に戻ると、第2の単一グループ使用トランザクションTX-Bが、類似の仕方で、第2の下位著者グループC-Bによって作成される。つまり、この場合、3つの初期トランザクションTX-B0からTX-B2を作成した3人の下位著者がおり、その結果、第2のグループ使用トランザクションTX-Bは、初期トランザクションのうちの異なるトランザクションをそれぞれ使用する3つの入力をもつ。
図19Aには明示的に示されていないが、第1のグループ・トランザクションTX-Aの5つの入力のそれぞれと、第2のグループ使用トランザクションTX-Bの3つの入力のそれぞれは、使用する初期トランザクションの出力において指定された公開鍵の秘密鍵対応物を使用して生成された有効なトランザクション署名を含む。よって、たとえば、第1のグループ使用トランザクションTX-Aの第1の入力は、初期トランザクションTX-A0の出力における公開鍵P-A0の秘密鍵対応物を使用して、そのトランザクションTX-Aの出力に署名するトランザクション署名を含む、などとなる。
第2のグループ使用トランザクションTX-Bは、同様に、第2のグループC-Bにおける各下位著者についての裁量署名(同じ方法で生成され、参照符号DS-B0~DS-B2で示される)と、第2のレベル3の上位著者C-D0、すなわち、第2のグループC-Bの下位著者の直接の監督者の公開鍵にロックされた少なくとも1つの使用可能な出力と、参照符号H2-B0~H2-B2で示される、第2の下位著者グループC-Bの寄与D-B0からD-B2のそれぞれに関する二重ハッシュ・パズルを含む。
ステップ1904に戻ると、第2の下位著者グループC-Bの直接の監督者C-D0は、第2のグループ・トランザクションTX-Bの使用可能な出力を使用する少なくとも1つの入力を有する第2のレベル3のトランザクションTX-Dを生成し、よって、第2のレベル2のトランザクションTX-Dの出力(単数または複数)に、第2のグループ・トランザクションTX-Bの使用可能な出力において指定された公開鍵P-D0の秘密鍵対応物を使用して署名することによって生成される有効なトランザクション署名を含み、さらに、それぞれ参照符号H-B0 H-B2で示される第2の下位著者グループC-Bの寄与D-B0,…,D-B2のそれぞれの単一ハッシュの形の二重ハッシュ・パズルの解を含む。
第1のレベル3使用トランザクションTX-Cとは対照的に、第2のレベル3使用トランザクションTX-Dは、少なくとも2つの使用可能出力を有する。これは、第2のレベル3上位著者C-D0が、1人ではなく2人の上位著者C-F0、C-F1によって監督されているという事実を反映している。これらの使用可能出力のうち第1のものは、第2のレベル2の監督著者C-F0の公開鍵P-F0にロックされ、第2の使用可能出力は、第3のレベル2の監督著者C-F1の公開鍵P-F1にロックされる。それらの使用可能な出力のそれぞれは、第2のレベル2の上位著者C-D0の寄与D-D0に関する二重ハッシュ・パズルH2-D0を含み、その出力をロック解除するためにはこれを解かなければならない。2つの使用可能出力をもつ代わりに、トランザクションTX-Dは、P-F0とP-F1の両方の公開鍵にロックされた単一の使用可能出力をもつことができる。これはたとえば、オペランドP-F0とP-F1をもつ2つのうち2つの(2-of-2)CHECKMULTISIGオペコードを、二重ハッシュ・パズルH2-D0と一緒に使用する。
最後に、第2のレベル3トランザクションTX-Dは、その一つまたは複数の出力において、図18Bの一般化ハッシュ・ツリー1820におけるレベル3にある非リーフ・ノードのハッシュ値IH-Bであって、第2の下位著者グループC-Bの全体的な寄与(上述の用語を使用した要約ハッシュ)を表すものと、また、上述のように生成された裁量署名DS-D0の形での第2のレベル3の上位著者の寄与の証明とを含む。
この方法の残りのステップは図19Bに示される。
これまでは、寄与者階層構造における2つの分枝を反映して、トランザクションの2つの別々の「分枝」があった。しかしながら、この方法の次のステップ、すなわちステップ1906では、レベル1の上位著者C-E0、C-F0、およびC-F1の3人すべてが同じ著者、すなわち主任編集者C-G0によって監督されるという事実を反映して、これらの2つの分枝は「マージ」される。すなわち、上述の用語を用いると、レベル1の上位著者3名はすべて階層構造における「きょうだい」であり、その「親」は主任編集者C-G0であるという事実を反映している。よって、ステップ1906では、単一のレベル2の使用トランザクションTX-EFが、これらの著者の3人全員によって作成される。この例では、レベル2の使用トランザクションTX-EFは、3つの入力をもつ。その1つは、第1のレベル3トランザクションTX-Cの使用可能な出力を使用し、残りの2つは、第2のレベル3の使用トランザクションTX-Dの2つの使用可能な出力を使用する。第1の入力は、第1のレベル2のトランザクションTX-Cの出力で指定された公開鍵P-E0の秘密鍵対応物を使用して生成された有効なトランザクション署名TS-E0と、さらに、第1のレベル2の著者C-C0の寄与D-C0の、該寄与D-C0の単一のハッシュH-C0の形での受領証明とを含む。第2および第3の入力は、それぞれ、公開鍵P-F0およびP-F1に対する秘密鍵対応物を使用してそれぞれ生成された有効なトランザクション署名TS-F0およびTS-F1を含み、それぞれ、第2のレベル3の著者の寄与D-D0の、その単一ハッシュH-D0の形での受領証明を含む。TX-Dが2つのうちの2つの(2-of-2)CHECKMULTISIGオペランドをもつ単一の使用可能出力をもつ場合、レベル2のトランザクションTX-EFは、第2および第3の入力の代わりに、2つの有効なトランザクション署名TS-F0とTS-F1と、受領証明H-D0とを含む単一の第2の入力をもつ。
レベル2のトランザクションTX-EFは、レベル1の主任編集者C-G0の公開鍵P-G0にロックされた少なくとも1つの使用可能な出力を含む一つまたは複数の出力を有しており、これは、さらに、3つのレベル2の上位著者の3つの寄与のそれぞれの、二重ハッシュ・パズルH2-E0、H2-F0、およびH2-F1の形の受領証明を必要とする。
さらに、一つまたは複数の出力は、図18Bの一般化ハッシュ・ツリーのレベル2における非リーフ・ノードのハッシュ値IH-CおよびIH-D(要約ハッシュ)と、レベル2の著者C-E0、C-F0およびC-F1のそれぞれについて、上記のように生成されたそれぞれの裁量署名DS-E0、DS-F0およびDS-F1の形でのその著者の寄与の証明とを含む。ステップ1908として、主任編集者C-G0は、レベル1トランザクションTX-Gを作成する。これは、レベル2トランザクションTX-EFの出力を有効に消費し、よって、有効なトランザクション署名TS-G0と、レベル2の著者の寄与D-E0、D-F0、およびD-F1の単一ハッシュ値H-E0、H-F0、およびH-F1の形での3つの受領証明とを含まなければならない。さらに、一つまたは複数の出力は、レベル3のリーフ・ノードIH-EおよびIH-Fのハッシュ値と、裁量署名DS-Dの形での主任編集者の寄与の証明とを含む。主任編集者の寄与は最終的な作品Dであり、これが裁量署名DS-Dが生成される対象となる寄与である。
レベル1トランザクションTX-Gは、参照符号P*で示される著作権機関の秘密鍵にロックされた使用可能な出力をもつ。
ステップ1910において、著作権機関は最終トランザクションTX*を作成する。これは、レベル1トランザクションTX-Gの使用可能な出力を消費する。よって、それは、レベル1トランザクションTX-Gで指定された公開鍵P*に対する秘密鍵対応物を使用して最終トランザクションTX*の出力に署名することによって生成された、有効なトランザクション署名TS*を含む。一例における著作権機関の役割のさらなる詳細は、のちに記載される。
各リーフ・ノードの二重ハッシュ値は、一般にH2-xxの形の参照符号で表され、関連する使用可能な出力における二重ハッシュ・パズルによってエンコードされ、その出力を消費するためにはこのパズルを解かなければならないことに注意されたい。さらに、この値は、後述するように、そのトランザクションの出力における他所で複製されてもよい。
上記では、トランザクション署名(transaction signature)(これは、本明細書では非裁量署名(non-discretionary signature)とも呼ばれる)を生成するために使用されるのと同じ秘密鍵が裁量署名を生成するために使用されるが、これは必須ではない。実際、裁量署名は、任意の秘密鍵を使用して、実際、トランザクション署名を生成するために使用される署名アルゴリズムと同じであってもなくてもよい任意の署名アルゴリズムを使用して、生成できる。たとえば、トランザクション署名はECDSAを使用して生成されてもよく、裁量署名はECDSAを使用して生成されてもされなくてもよい。
協働的認証プロトコルの例示的実装のさらなる詳細は後述される。この例示的実装は、本願で「一般化ハッシュ・ツリー」と呼ばれるものを利用する。一般化ハッシュ・ツリーの原理を、まず、関連する文脈を提供するために記述する。
2. ハッシュ・ツリー
データ構造としてのハッシュ・ツリーの概念は、1979年にRalph Merkleによって導入された。それ以来、ハッシュ・ツリーはブロックチェーンのブロック内のトランザクションの集合の表現や、Gitバージョン制御のようなバージョン管理システムにおける状態変化の記録を含む用途で広く使われてきた。
「ハッシュ・ツリー」および「マークル・ツリー」という用語は、一般に、同じタイプのデータ構造を指すために使用される。根底にあるデータ構造と選択された数学的定式化との間の区別をすることが有用であると考えられる場合、以下の説明では、根底にあるデータ構造を指すためにハッシュ・ツリーという用語を使い、ハッシュ・ツリーを指すためにマークル・ツリーという用語を、ハッシュ・ツリーのノードをインデックス付けするためのインデックス付けスキームと、そのインデックス付けシステムに従ってハッシュ・ツリーを構築するための一連のノードの式とを組み合わせて用いることがある。
マークル・ツリーは、一般に、ノードおよびエッジを含む二分木データ構造として扱われる。ノードはハッシュダイジェスト(ハッシュ値)として表現され、エッジは、連結されたノードのペアに一方向関数(一般的には暗号学的ハッシュ関数)を適用して親ノードを生成することによって生成される。このプロセスは、単一のルート・ハッシュ値(ルート・ノード)に到達するまで、再帰的に繰り返される。
マークル・ツリーは、二分木、三分木、またはより一般的にはk分木として実装されてきた。ここで、kは、ツリー全体で使用される共通の分岐因子である。分岐因子がマークル・ツリー全体で確かに一貫しているという事実は、そのようなツリーの広く受け入れられている特徴である。もう1つの一般的な特徴は、データ・ブロックがツリーの最下層(つまり、ルートから最も遠い層)でのみ挿入されることである。これらの制約条件を有するデータ構造は、本明細書では「古典的」ハッシュ(またはマークル)ツリーと呼ばれることがある。
しかしながら、本開示は、マークル・ツリーの構築において、これらの共通の特徴を用いて可能であるよりも大きな柔軟性を有することが有利である用途を認識した。よって、マークル・ツリーの高度に一般化された処置が提供され、その結果、本明細書で「一般化」ハッシュ・ツリーと呼ばれるものを構築し、操作するためのプロトコルがもたらされる。これらの一般化された構造は、古典的なマークル・ツリーの特性の多くを受け継ぐ一方で、一貫した分岐因子をもつことと、ベース層においてリーフ・ノードを挿入するだけであることの両方の制約条件を除去することによって、さらなる柔軟性を獲得する。
用語「スキーマ」は、ここでは、データ構造に課される制約条件の集合を指すために使用されうる。古典的なハッシュ・ツリーの場合、これらの制約条件は上に要約され、以下にさらに詳しく記載される。
本開示は、一般化ハッシュ・ツリーを構築するための新規スキーマを提供し、その詳細は以下に記載される。
本開示はまた、一般化ハッシュ・ツリーのノードにインデックスを割り当てるための新規のインデックス付けスキームを提供する。このインデックス付けスキームに従ってインデックス付けされたハッシュ・ツリーは、一般化マークル・ツリーと呼ばれうる。
本開示の実施形態は、以下に詳細に記載される。まず、記載される実施形態のコンテキストとして、古典的ハッシュ・ツリーのより詳細な説明を次に述べる。
2.1 古典的ハッシュ・ツリー
大量のデータを効率的で、かつそれほど資源集約的でない仕方で表現するための一般的な方法は、ハッシュ・ツリーとして知られる構造にそれを格納することである。ここで、ハッシュは、SHA-256のような一方向性の暗号学的ハッシュ関数のダイジェストを意味すると解釈される。
典型的なハッシュ関数は任意のサイズの入力をとり、一定の範囲の整数を生成する。たとえば、SHA-256ハッシュ関数は、その出力ハッシュダイジェスト(ハッシュ値)として256ビットの数を与える。
一般に、ハッシュ・ツリーは、一組の方向性エッジによって接続された「内部」ノードおよび「リーフ」ノードを含むツリー状のデータ構造である。各リーフ・ノードは、ツリーに「格納」されるデータの一部(データ・ブロック)の暗号学的ハッシュを表し、各ノードは、その「子」(子ノード)の連結をハッシュすることによって生成される。「親」ノードの子ノードは、方向性エッジによって親ノードに直接接続された任意のノードである。ハッシュ・ツリーのルート・ノードは、データの大きな集合をコンパクトに表現するために使用することができ、リーフ・ノードに対応するデータの前記部分のうちの任意のものが実際に集合の一部であることを証明するために使用することができる。ルート・ノードは、他のすべてのノードが直接的または間接的に接続される単一のノードである。
当該技術分野で使用される用語によれば、本開示は、ハッシュ・ツリーに「記憶されている」データを参照してもよい。しかしながら、ハッシュ関数の一方向性のため、データは、ハッシュ・ツリー自体から回復可能でないことが認められる(実際には、これはハッシュ・ツリーの利点の1つである)。むしろ、ハッシュ・ツリーは、以下に記載される仕方でデータ・ブロックを検証するために使用できる。よって、本開示が、データがハッシュ・ツリー等に格納されるまたは含まれることに言及する場合、それは、データが、以下に記載される仕方でハッシュ・ツリーにおいて表現されることを意味し、データがハッシュ・ツリーから回復可能であることを意味しないことが理解されるであろう。
多くのアプリケーションでは、各非リーフ・ノードがちょうど2つの子ノードをもち、リーフ・ノードがデータのブロックのハッシュである二分ハッシュ・ツリーが使用される。たとえば、ビットコイン・ブロックチェーンは、ブロックについてのすべてのトランザクションをコンパクトに記憶するために、二分ハッシュ・ツリー実装を使用する。ルート・ハッシュは、ブロックに含まれるフル・セット・トランザクションを表すために、ブロックヘッダに格納される。
図3は、単純な二分ハッシュ・ツリーを示しており、ここでは、リーフ・ノードは白丸で表され、非リーフ・ノードは黒丸で表され、エッジは、ノードのペア間の線分で表される。各ノードは、下記のように計算されるハッシュ値として具現される。
二分ハッシュ・ツリーの構造が図3に示される。ここで、矢印はハッシュ関数の適用を表し、白丸はリーフ・ノードを表し、黒丸は内部ノードとルートの両方に使用される。このハッシュ・ツリーは、各部分をハッシュし、結果として得られたダイジェストをペアごとにH(D1)||H(D2), …, H(D7)||H(D8)と連結することにより、データの8つの部分D1…D8の集合を格納する。ここで、「||」演算子は、データの2つのストリングの連結を表す。その後、連結された結果はハッシュされ、データセット全体の表現として、単一の256ビットのハッシュ・ダイジェストが残る(マークル・ルート)まで、このプロセスが繰り返される。
例として、参照番号300および301で示されるノードは、それぞれデータ・ブロックD3およびD4を表すリーフ・ノードである。よって、ノード301および302のハッシュ値は、それぞれH(D3)およびH(D4)である。ノード300および301は、参照番号302で示される共通の親ノードを有するので、「きょうだいノード」と呼ばれる。親ノード302のハッシュ値は、H(H(D3)||H(D4))である。次に、ノード302は、参照番号304で示されるノードのきょうだいノードであることが示される。なぜなら、これらのノードは共通の親ノード306を有し、その親ノード306は、その子ノード302、304のハッシュ値の連結のハッシュに等しいハッシュ値を有するからである。
2.2 マークル・ツリー
マークル・ツリーは、Ralph Merkleによって1979年に提案されたた、ハッシュ・ツリーの当初の実装である。
R.C. Merkle、Stanford University、(1979)、Secrecy, Authentication, and Public Key Systems(マークル論文).
マークル・ツリーは、典型的には、二分ハッシュ・ツリーとして解釈される。
マークル・ツリーにおいて、ツリーの各ノードにはインデックスのペア(i,j)が与えられ、N(i,j)として表される。インデックスi,jは、ツリー内の特定の位置に関連する単なる数値ラベルである。
マークル・ツリーの重要な特徴は、各ノードの構築が次式によって支配されることである(これらの式は、マークルの論文から改変され、単純化してある)。
ここで、k=(i+j-1)/2であり、Hは暗号学的ハッシュ関数である。
これらの式に基づいて構築された二分マークル・ツリーが図4に示される。i=jの場合はリーフ・ノードに対応し、リーフ・ノードは、単に、データDiの対応するi番目のブロックのハッシュであることがわかる。i≠jの場合は内部ノードまたはルート・ノードに対応し、該内部ノードまたはルート・ノードは、その特定のノードまたはルートに到達するまで、ツリー内の子ノードを再帰的にハッシュし連結することによって生成される。
たとえば、ノードN(1,4)は次のようにして4つのデータ・ブロックD
1,…,D
4から構築される。
各ノードは、そのノードが共通のルート・ノード、すなわち図4の例におけるノード(1,8)に接続されるときに介する方向性エッジの数に対応する、ツリーにおけるレベル(深さ)をもつ(ルート・ノード自体のレベルはゼロ)。ツリーは、ツリーにおける最低レベルとして定義される深さをもち、ノードの深さは、そのノードが存在するレベルである。たとえば、m
root=0であり、m
leaf=Mであり、図4ではM=3である。
二分木が例として示されているが、三分木、四分木、またはK分マークル・ツリーを構築することが
可能である。ここで、Kはツリーの分岐の次数であり、分岐因子とも呼ばれる。
一般に、すべてのマークル・ツリー実装に共通するコアとなる特性およびパラダイムは、次のように要約できる:
1.共通の分岐次数K-すべての非リーフ・ノードの分岐次数は共通である。二分マークル・ツリーの場合、すべての内部ノードとマークル・ルートは、ちょうど2つの子をもつ。
2.リーフ・ノードの位置-すべてのリーフ・ノードは、ツリーの底部に一様に配置される。これは、データ・ブロックは、同じベース層でのみツリーに注入可能であることを意味する。
これらの特性は、最適に効率的な仕方でデータ・ブロックのリストを格納するように設計されたマークル・ツリーのアーチファクトである。しかしながら、この設計は、たとえば、暗号署名スキームおよびブロックチェーン・トランザクションの記憶には非常によく役立つものの、他の用途のためには最適ではない制約条件を受ける。特性1の結果として、分岐因子Kをもつマークル・ツリーにN個のデータ・ブロックを格納するためには、ツリーはKM≧N個のリーフ・ノードをもたなければならない。これは、ツリーの深さが、総格納要件に対して対数的に増加するという点で有益である。しかしながら、これはまた、KM>Nであるすべての場合において、マークル・ツリーがヌルデータを含む追加のN'=KM-N個のリーフ・ノードで「パディング」されなければならないことも意味する。これは、マークル・ツリーは、ツリーのユーザーにとって関心のない余分なデータをしばしば含むことを意味する。
さらに、特性2は、そのベース以外のツリーのどのレベルでも、データ・ブロックを追加または注入することができないことを意味する。このため、マークル・ツリー自体の中にデータセットに関する階層や構造を反映することが非常に困難である。
マークル証明
ほとんどのアプリケーションにおけるマークル・ツリーの主な機能は、何らかのデータ・ブロックDiがN個のデータ・ブロックのリストまたは集合D∈{D1,…,DN}の要素であることの証明を容易にすることである。マークル・ルートと候補データ・ブロックDiが与えられるとき、これは集合内の前記ブロックの「存在証明」として扱うことができる。
そのような証明のための機構は、マークル証明として知られており、所与のデータ・ブロックDiとマークル・ルートRについて「マークル経路」として知られているハッシュの集合を得ることからなる。データ・ブロックについてのマークル経路は、単に、繰り返されるハッシュと連結によってルートRを再構築するために必要なハッシュの最小リストであり、データ・ブロックの「認証経路」と称されてもよい。
方法
マークル・ルートRと「検証」されるべきデータ・ブロックD1が与えられる場合――このコンテキストでの「検証される」とは、データ・ブロックD1がRによって表される集合D∈{D1,…,DN}(すなわち、ハッシュ・ツリーが構築されるもとになるデータ・ブロックの集合)に属することを証明することを意味する――、データ・ブロックD1は、以下のように検証される。データ・ブロックD1は、例として考えられている。この証明は、任意の所与のデータ・ブロックについて、それがハッシュ・ツリーを構築するために使用されたデータ・ブロックの1つに対応するか否かを決定するために、実行されることができる。
図5を参照すると、データ・ブロックD1を検証するために、マークル証明が以下のように実行される:
i)信頼されるソースからマークル・ルートRを取得する。
ii)ソースからマークル経路Γを取得する。この場合、Γはハッシュの集合:
Γ={N(2,2),N(3,4),N(5,8)}
である。
iii)以下のようにしてD1およびΓを使ってマークル証明を計算する:
a.データ・ブロックをハッシュして:
N(1,1)=H(D1) (「再構築されたリーフハッシュ」502)
を得る。
b.N(2,2)と連結し、ハッシュして:
N(1,2)=H(N(1,1)||N(2,2))
を得る。
c.N(3,4)と連結し、ハッシュして:
N(1,4)=H(N(1,2)||N(3,4))を得る。
d.N(5,8)と連結し、ハッシュして、ルートを再構築する:
N(1,8)=H(N(1,4)||N(5,8))を得て、
R'=N(1,8) (「再構築されたルート・ハッシュ」)
e.計算されたルートR'を(1)で得られたルートRと比較する:
I.R'=Rであれば、ツリー、したがってデータセットDにおけるD1の存在が確証される。
II.R'≠Rであれば、証明は失敗であり、D1はDの要素として確証されない。
これは、マークル・ツリーとそのルートによって表されるデータセットの一部としての、何らかのデータの存在証明を提供するための効率的な機構である。たとえば、データがブロックチェーン・トランザクションに対応し、ルートがブロックヘッダの一部として公に利用可能である場合、そのトランザクションがそのブロックに含まれていたことを迅速に証明することが可能である。
例示的なマークル・ツリーの一部として存在することを認証するプロセスが図5に示されている。これは、与えられたブロックとルートについてマークル証明を実行することが、事実上、必要なハッシュ値の最小限の数のみを使用して、マークル・ツリーが「上向き」にたどることであることを示す。
2.1.2 グラフ理論におけるツリー構造
ハッシュ・ツリーまたはマークル・ツリーは、グラフ理論の文脈で解釈されてもよい。ハッシュ・ツリーは、データの頂点またはノード(ハッシュ値)と、複数の連結された頂点のハッシュによって形成されたノードを接続するエッジとを含む。より具体的には、グラフ理論において、ハッシュ・ツリーは以下の重要な特性を有すると考えられる。
有向-ノード間のエッジは、一方向にしか実行できない一方向ハッシュ関数を計算することによって形成される。これは、ハッシュ・ツリーにおけるすべてのエッジが方向をもつことを意味し、ツリーがであることを意味する。
非環状-ハッシュ・ツリーの構造には循環経路はない。
グラフ-ハッシュ・ツリーは、頂点および頂点を接続するエッジを含むため、グラフとして分類できる。
これら3つの特性のすべての組み合せは、ハッシュ・ツリーまたはマークル・ツリーが有向非環状グラフ(DAG)の定義を満たすことを意味する。
有向グラフは、その有向エッジを無向エッジに置き換えることが連結グラフを形成する場合、弱く連結されていると呼ばれる。ハッシュ・ツリーはこの基準を満たすので、弱く連結されたDAGでもある。
「ルート付きツリー」は、1つの頂点またはノードがツリーのルートとして識別されるツリーとして定義され、ルート付きツリーが根底にある有向グラフをもつ場合は、有向ルート付きツリーと呼ばれる。さらに、有向ルート付きツリーでは、すべてのエッジは、指定されたルートから離れる向きであるか(樹枝状)、または指定されたルートに向かうか(反樹枝状)のいずれかである。
本開示は、ハッシュ・ツリーまたはマークル・ツリーを、後者の一例、すなわち、反樹枝状有向ルート付きツリーであると認識し、それによって、そのエッジのすべては、ルート「に向かって」頂点をハッシュしていくことによって構築される。
3. 一般化ハッシュ・ツリー・プロトコル
記載される実施形態は、以下の特性を有するように明示的に定義された一般化ハッシュ・ツリー・データ構造を提供する:
リーフ・ノードの階層的位置-リーフ・ノードが、ルート・ハッシュの下のツリーの任意のレベルに配置できる。これは、データの外部階層を反映するハッシュ・ツリーの異なるレベルにデータを注入することを許容する。任意の数の子-各ノードは任意の数の子(または「入次数(in-degree)」)をもつことができ、該子は、任意の数の内部子ノードおよび任意の数のリーフ子ノードを含みうる。
可変分岐因子-子の数(入次数)と親の数(出次数(out-degree))の比を与える、内部ノードについての分岐因子は、ツリー全体で共通である必要はない。
これらの特性の組み合わせは、ツリーのコアとなる機能、すなわち、上述したのと同じマークル証明原理を用いて所与のデータ・ブロックを効率的に検証する能力を維持しながら、その上にかぶさる第2層の階層をもつデータセットを表現できるハッシュ・ツリーの構築を許容する。これらのコアとなる機能は、ツリーが単一のハッシュ値、すなわちルートにおいてデータセット全体を表現できなければならないこと(すなわち、すべてのノードが共通のルート・ノードに直接的または間接的に接続されていなければならない)、および、階層構造内の位置に関わりなく、セット内のデータの任意の1つのブロックに対して、マークル存在証明を実行することが可能でなければならないことである。
一般化ハッシュ・ツリー構造の例が図6に示される。この例は、ハッシュ・ツリーにさまざまなレベルで挿入される14のデータ・ブロックD1~D14の階層構造を示している。これは、これらのデータ注入がすべてツリーの最下層で行われる伝統的なマークル・ツリー構造とは対照的である。
一般化ハッシュ・ツリーの規則
所望の特性を達成するハッシュ・ツリーは、以下の規則集合に従って構築できる。上記の用語を用いると、この規則集合は、任意の一般化ハッシュ・ツリーがそれに従って構築される「スキーマ」を構成する:
1.ノード-ノードは、高々1つの親と、任意の数の子をもつことができる。ノードは一般にリーフ・ノードまたは非リーフ・ノードのいずれかであるが、全体的には3つのカテゴリーに分けることができる:
a.ルート・ノードは、親をもたないことによって定義される。
b.中間ノードは、少なくとも1つの親と少なくとも1つの子をもつことによって定義される。
c.リーフ・ノードは子をもたないことによって定義される。
(a)と(b)はいずれも非リーフ・ノードの例であり、(c)はリーフ・ノードであることに注意。
2.エッジ-エッジは、特定の順序できょうだいと連結されたノードをハッシュすることによって作成される。親と子の間のエッジは、順に連結された親の子すべてをハッシュすることによって作成される。
親Pと4つの子C
1,C
2,C
3,C
4があれば、次のエッジを作成できる:
各エッジの数学的構築は同じであるため、親子間のエッジは、きょうだいの集合全体がわかって初めて作成されうることに注意されたい。
また、結果として得られるハッシュ値H(C
1||C
2||C
3||C
4)は親ノードのハッシュ値であることにも注意されたい。したがって、規則2は、「親ノードのハッシュ値は」指定された順序での「その子ノードのハッシュ値の連結のハッシュである」というように等価に定式化できる。
3.任意の数の子-任意の非リーフ・ノードがもちうる子の数に制限はない。リーフ・ノードは、定義により、子をもたない(規則1参照)。
4.リーフ・ノードの位置-ハッシュ・ツリー内でリーフ・ノードが配置されうる深さに制限はない。したがって、リーフ・ノードはツリーのどのレベルにも存在する可能性がある。
「第二原像攻撃」に対して追加の堅牢性を提供するために、追加の規則がスキーマに導入されてもよい。
5.リーフ・ノードと非リーフ・ノードは区別可能である-すべてのリーフ・ノードは明示的に非リーフ・ノードと区別可能である。これは、たとえば、各リーフ・ノードのハッシュ値の前に、所定のプレフィックス(たとえば、0x00)を付けることによって行うことができる。
第二原像攻撃は、ハッシュ値が計算されるもとになった元の原像を知らずに、攻撃者がハッシュ値の原像(すなわち、ハッシュするとその値になるようなデータ・ブロック)を発見することに成功する状況を指す。
上記の用語を適用すると、一般化マークル・ツリーは、インデックス付けとノードの式に関連する追加の規則をもち、それは以下のように定式化されうる:
6.インデックス付けシステム-すべてのノードは、共通のインデックス付けシステム(3.1.1参照)に従って、一意にラベル付けされなければならない。
7.黄金律-一組のきょうだいノードにラベル付けするとき、リーフきょうだいの前に、非リーフきょうだいがラベル付けされる(3.1.2参照)。
8.ノードの式-すべてのノードは、一般化ハッシュ・ツリーのノードの式に従わなければならない。これらの式は、インデックス付けシステムによって提供される構造に依存し、ツリー内のすべてのノードのハッシュ値が、その子から再帰的に構築されることを許容する(3.3参照)。
注:規則5~8は、一般化ハッシュ・ツリーに関しては任意的である。つまり、一般化ハッシュ・ツリーの基本的な特性を定義しているのは規則1~4のみである。規則5は、追加的なセキュリティを提供する任意的な実装機能であり、規則6~8は、一般化ハッシュ・ツリーを構築するための特に便利なノードの式のセットと、それらのノードの式で採用されるインデックス付けスキームを定義している(便利ではあるが、それでも他のインデックス付けスキームおよびノードの式の定式化が実行可能であることに注意)。
3.1.1 インデックス付けシステム
図7は、図6の一般化ハッシュ・ツリーを示しており、すべてのノードがアルファベットの参照符号A~Uを与えられている。
図5に示される例(3.2参照)のような一般化ハッシュ・ツリーを作成するために、上述のインデックス付けと表記のシステムは、各ノードが簡単に識別されることを許容し、ハッシュ・ツリー内のその位置を明確に示す。
一般化ハッシュ・ツリーにおけるノードを表すために使用される基本的な表記法は、
「インデックス・タプル」という用語は、ノード
のインデックス(i,i
0,…,i
m-2,j)を指してもよく、これらのインデックスは定義された順序をもつことを注意しておく。ツリーにおけるノードのレベルは、そのインデックス・タプルのインデックス数でエンコードされる。つまり、m+1個のインデックスを含むインデックス・タプルをもつノードはレベルmにある。この記述は、ルート・ハッシュがレベルm=0にあり、最も深いリーフ・ノードがレベルm=Mにあるという慣例を採用している。ここで、Mは、ツリーの深さと称される。その定義。
下付インデックスは、ルート・ノードから問題のノードへ、ツリーを下る経路をたどる。この経路は、3つのタイプの下付インデックスに分類できる。
ルート・インデックス-ヌルインデックス「0」が常に、最初の下付インデックスであり、ツリー内の各ノードが有限数のエッジによってルートに接続されることを意味する。ルート・ノードはN0とラベル付けされる。
中間インデックス-レベルmにあるノードは、常にm-2個の中間インデックスをもつ(m≦2であればヌル)をもつ。これらのインデックスは、ルートから問題のノードの親までのノードの経路を表す。これらのインデックスは、i0,…,im-2と書かれる。
きょうだいインデックス-ノードの最後の下付インデックスは、そのきょうだいに関するその位置を示す。
一般化ハッシュ・ツリー内の各ノードは、ちょうどm+1個のインデックスをもつ:1つのルート・インデックス(0)、m-2個の中間インデックス(i0,…,im-2)、1つのきょうだいインデックス(j)である。
また、すべてのインデックスは負でない整数であり、ゼロから始まり増加することに注意されたい。
説明を容易にするために、一般化ハッシュ・ツリー法のブロックチェーン・ベースの実装を議論するとき、内部ノードは「中間ノード」と称されることがある。よって、これら2つの用語は同等であり、交換可能とみなされる。
ルート・インデックスは常にゼロであるので、インデックスが計算されるとき、ルート・インデックスは明示的にエンコードされる必要はないことに注意されたい(すなわち、インデックス・タプルが計算されるとき、ルート・インデックスは、実際には値として保存されないという点で暗黙的であってもよい)。
黄金律
インデックスは、黄金律(GR)に従って上記のインデックス付けシステムに従って割り当てられる。この規則は次のように述べられる:
GR-n個のきょうだいノードについてのきょうだいインデックスjを決定するとき、値j=0,…,j=n-1が次のように割り当てられる:
1.左から右へ、かつ
2. 中間きょうだいが、リーフきょうだいの前に割り当てられるようにする。
ノードは、上から下へ、左から右に名前を付けられる。上から下へは、分岐経路を、よってノードの親を位置特定する。右から左は、前記親の子の位置を、そのきょうだいに対して示す。
ハッシング
ノードの式に示されるように、ハッシングのプロセスは、一般化ハッシュ・ツリーにおいて2つの意味をもつ。ツリーに含まれる任意のデータ・ブロックDは、どのレベルでも、リーフ・ノードを形成するためにH2(D)のように二重ハッシュされる(その値は「二重ハッシュ」値である)。しかしながら、複数のリーフおよび/または内部ノードが組み合わされてツリー内の新しい内部ノードを形成するときはいつでも、それらは連結され、1回だけハッシュされる、すなわちH(Leaf1||Leaf2)(「単一ハッシュ」値が得られる)。
二重ハッシュは、データ・ブロックそのものを明かさなくても、単一ハッシュ値(すなわち、データ・ブロックに対してハッシュ関数を1回だけ適用すること(単一ハッシングと称される)によって得られたもの)が、根底にあるデータ・ブロックの所有または受領の証明を提供するために公開されることができ、それは一般化ハッシュ・ツリーに関して検証できるという恩恵を提供する。これは、ハッシュ・ツリーが機微なデータを表現するために使用される場合に有益である。より一般的には、用語「多重ハッシュ」は、データ・ブロックを2回以上ハッシュする(すなわち、データ・ブロックをハッシュし、次に、少なくとも、同じまたは異なるハッシュ関数を用いてその結果をハッシュする)ことによって得られるハッシュ値をいう。
あるいはまた、機微でないデータの場合、単一ハッシュで十分であるかもしれない。すなわち、各リーフ・ノードのハッシュ値は、根底にあるデータ・ブロックの単一ハッシュであってもよい。一般化ハッシュ・ツリーと方法は、単一ハッシュ・アルゴリズムまたは関数に限定されるものではなく、単に、暗号学的に安全な一方関数が使われることを要求するものである。
一般化ハッシュ・ツリーのインデックス付け
図7は、図6の一般化ハッシュ・ツリー構造の例を示しており、インデックス付け慣例が採用されている:
ルート・ノード-ハッシュ・ツリーに1つのルート・ノードのみが存在し、この場合はAとラベル付けされている。
たとえば、AはN0とラベル付けされる。
中間ノード-ノードB、C、E、G、J、Lは、すべて中間ノードであり、その下のサブツリーのハッシュの要約のはたらきをする。
たとえば、BはN0,0とラベル付けされる、
たとえば、KはN0,0,0,1とラベル付けされる、
など。
リーフ・ノード-ノードD、F、H、I、K、M、N、O、P、Q、R、S、T、Uはすべてリーフ・ノードであり、データ・ブロックの二重ハッシュを含む。
たとえば、FはN0,0,1とラベル付けされる。
たとえば、PはN0,0,0,0,2とラベル付けされる。
たとえば、UはN0,1,0,0,2とラベル付けされる。
など。
図7のすべてのノードのラベルの完全なリストが表1に示される。
この表は、図6に示されるハッシュ・ツリーの完全な表現である。そのような表表現は、生成されたハッシュ・ツリー・データ構造を、たとえばオフチェーン・システム(下記参照)において実体的に具現するために使用されうる。
ノードの式
子の任意の数nをもちうるノードの記法
を想起されたい。この節全体を通して、記号+がデータ連結(通例は||と表される)を表すために使用され、山括弧(山括弧のペア内のデータをスタックにプッシュすることを表す)の使用は割愛される。つまり、x+yは、〈x〉||〈Y〉を意味するものと解釈される。
関数G
αは、すべての要素α、または少なくとも範囲0≦α≦n-1内のαに対応する要素にわたる連結和を計算するために、次のように定義されている(Σは、定義された範囲にわたる、和ではなく連結を表すことに注意):
一般化ハッシュ・ツリー・スキーマに従って、各ノードの値は、単に、(3.1.2の黄金律で指定されるように)順にそのすべての子の連結和のハッシュを取ったものとして定義できる。これは数学的に次のように書くことができる。
ノードの値に対するこの定義は、上からの連結和記法を使って表すことができる。ここで、各要素はノードのそれぞれの子となり、次のようになる:
これは、ノードが、上記のインデックス付けスキームに関連して定義された数学的操作を用いて、順にその子すべて連結のハッシュを取ったものであるという事実を捉えている。
値が計算されているノードはm+1個のインデックスをもっているので、その子は必然的にちょうどm+1個のインデックスをもつはずである。それにより、子の最初のm+1個のインデックスは親のインデックスと同じである。したがって、和のために使用されるダミー・インデックスαは、問題のノードのそれぞれの子の追加的なきょうだいインデックス(m+2番目のインデックス)を表す。
再帰
ノードのレベルが段階的に増加するたびに追加インデックスを加えるというこの原理は、ノードの値が、簡潔な再帰的表現を用いて表現されることを許容する。
ギリシャ文字(α,β,γ,…,ω)が、この再帰を表す「ダミー」(きょうだい)インデックスを表すのに使用される。計算されるべきノードのもとのm+1個のインデックスを表すために用いられるラテン文字(i,j)と混同しないためである。
この再帰が上記の公式でどのように機能するかを見るために、多くの世代にまたがる子孫をもつノード
を考える。子孫の第一世代のきょうだいインデックスはダミー・インデックスαによって表され、第二世代はβによって表され、などとなり、最後の(最も深い)世代はωによって表される。
すると、ノードの値についての公式は次のように書くことができる:
見て取れるように、問題のノードのそれぞれの第1の子孫は、その「子孫」(子および、該当する場合は孫、すなわち、一つまたは複数の他のノードを介して間接的にそれに接続されているノード)を用いて展開でき、これらのノードはさらにその子孫を用いて展開でき、となって、最下位の世代(ωによって示される)に到達するまで続く。
ここで、異なる子孫が異なる数の子孫をもつ可能性があるという事実を反映して、子孫世代ごとに和の上限が変化することに注意されたい。
たとえば、ダミー・インデックスαは、0≦α≦n-1の範囲であり、その値が計算されるべきノードがn個の子をもつことを示す。これらの子のそれぞれは、自分たち自身、異なる数の子(ノードに関する第二世代)をもつことがあるので、これを反映してダミー・インデックスβは0≦β≦n'-1の範囲である。
まとめると、ノードの値のための式は、ノードの値が、その子だけでなく、実際にはその子孫すべてからどのようにして構築されるかを表す再帰的な仕方で次のように書くことができる。
リーフ・ノードと非リーフ・ノード
セクション3.1で概説したように、一般化ハッシュ・ツリーは、リーフ・ノード(子をもたない)と非リーフ子ノード(少なくとも1つの子をもつ)を含みうる。
これら2つのクラスのノードは根本的に異なっている。リーフ・ノードは、特定のツリー分枝を終了する「端点」を、通例は何らかのデータDを表し、一方、非リーフ・ノードは分枝を終了せず、多くの子孫世代をもつ可能性がある。
この違いは、リーフ・ノードと非リーフ・ノードが異なる扱いをされることを確実にするために、ノードの式に反映されている。
n=0個の子をもつリーフ・ノード
の値は、そのノードによって表されるデータ・パケット
の二重ハッシュとして定義される。このことは、次のように書かれる。
非リーフ・ノードの値とリーフ・ノードの値の区別は、ノードの式の最終版を書くときに使用される。
和の分割
セクション3.1.2では、黄金律(GR)が、きょうだいノードの所与のセットについて、非リーフ・ノードがリーフ・ノードの前にラベル付けされることを確立した。
この理由は、ノードのための再帰的公式が、自分自身の子に展開されなければならない非リーフである子を、リーフである子よりも先に、一貫して合計することを保証するためである。
概念的には、GRのこの側面は、ノードの値の公式が、次のように、「和」(またはむしろ連結)を、異なる限界にわたる2つの「和」に分割することによって計算されることを許容する。
上記の分割された和は、合計n個の子をもつノードをε個の非リーフである子およびn-ε個のリーフである子にそれぞれ分割して考える。これは、一般化ハッシュ・ツリーでは、古典的なツリーとは対照的に、親ノードが、リーフ子ノードと非リーフ子ノードの両方をもつことができるという事実を反映している。
左側の和の上限は、非リーフの子すべての連結を表し、これは、右側の和がリーフである子すべてを連結する前に行われる。これは、以前に定式化されたGRの意図された結果である。
ノードの式
要約すると、一般化ハッシュ・ツリーにおける任意の所与のノードの値についての一対の簡潔な式は、次のように書くことができる:
これらの式は、リーフ・ノードと非リーフ・ノードとの区別を説明し、ノードの値をその諸子孫の頂点として再帰的に表現し、どのレベルでも非リーフとリーフの子に分離できる。これらの式は、連結和関数を使って次のように書き直すこともできる:
ノード・ハッシュ値の計算
図8は、一般化ハッシュ・ツリーの分枝を示し、ノード(レベルm)がその子孫からどのように計算されるかを示す。
値が計算される例示的なノード
の例が表示されている。ノードは任意のレベルmにあり、その上に複数の「祖先」をもちうる(点線で示す。祖先は、そのノードが直接的または間接的に接続されているノードである)。ただし、ハッシュ値を計算するために考慮する必要があるのは、その子孫のみである。
黒丸は非リーフ・ノードを表すために使用され、白丸はリーフ・ノードを表すために使用される。
以下に示される数段階において、再帰的なノードの式を用いて、ノードの値が計算される。
1. ノードを連結和を用いて書く:
2. 和を、そのノードのn個の子を用いて展開する。図では、これらはε個の非リーフ・ノードとn-ε個のリーフ・ノードに分割されて示されている。
3. 非リーフの子をそれ自身の子として再度展開する。この場合、
は非リーフであり、子孫をもつが、簡単のため、ノード
の展開のみが示されている。
4. 最終の非リーフの子孫をそれ自身の子をもちいて展開する。これにより、2つのリーフ・ノードの子が残り、よって、
の下にあるすべての枝はこれで終了している。
5. ステップ1の式を使用してノードのハッシュ値を計算するために、必要なハッシュ値をすべて下から上に組み込んでいく。
計算の最後の行が、リーフ・ノードのハッシュ値のみを用いていることに注意されたい。ハッシュ値は、これらのリーフ・ノードに対応するデータ・パケットDにのみ依存する。
一般化ハッシュ・ツリーの拡張
一般化ハッシュ・ツリーの鍵となる特性は、最初の作成後いつでもツリーに新しいデータを追加できることである。
たとえば、ある時点での文書の安定なバージョンを表現するために一般化ハッシュ・ツリーが使用されている場合、ツリー内の任意の点において新しいデータ・リーフH2(Dnew)を追加することにより、何らかの後の時点で、追加的な変更を行うことが簡単である。
例として、図9は、追加的なデータ・パケットDnewによって拡張された一般化ハッシュ・ツリーを示している。更新される必要があるオリジナルのツリーのノードは、それぞれ参照番号902および904によって示されるチェッカー状の円として示され、ノード904はルート・ノードである。
新しいデータがツリーにおいて、どこに、どのレベルで挿入されるかに依存して、ある種のノードは、その一意的なハッシュ値が変更されるであろうから、再計算されなければならない。これにより、変更が、ツリー内の任意の位置から上方に伝搬し、事後の変更の階層構造を反映することができる。
疑義を避けるために、ブロックチェーンの文脈では、ブロックチェーンにコミットされたハッシュ・ツリーの変更または修正への参照は、ブロックチェーン内の変更不能な仕方で記録されたデータのいかなる修正も意味しない。むしろ、たとえば、ブロックチェーンに格納されたハッシュ・ツリーの異なるバージョンを解釈するために、一組の規則が構築されることができる(たとえば、単純な規則は、最新のバージョンが、その一部の以前のバージョンを上書きするものとして解釈されるというものであってもよい)。たとえば、新しいトランザクションをブロックチェーンに書き込んで、このようにしてハッシュ・ツリーを拡張し、データの最新「バージョン」を、ブロックチェーン上に現れた際の新しさ(recency)に従って解釈することができる。バージョン化(versioning)は、ブロック間(すなわち、どのトランザクションが、マイニングされた最新のブロックにあったか)でも、ブロック内(すなわち、同じブロック内にある場合、どのトランザクションが「最高」/「最低」に現れたか)でも解決できる。
マークル存在証明の計算
一般化ハッシュ・ツリーの重要な利点は、マークル・ツリー証明(2.1.1参照)を用いて、古典的なマークル・ツリーに匹敵する効率レベルで、存在の証明が計算できるということである。
図10は、与えられた(任意の)データ・ブロックに対してマークル証明がどのように実行されるかを概略的に示している。図5と同様に、そのデータ・ブロックについての認証経路に属するノードは、点線で囲まれている。
再構成されたルート・ハッシュ1004は、(この場合)検証されるべきデータ・ブロックD3を二重ハッシュする(図5のルート・ハッシュ502に匹敵する)ことによって計算され、再構成されたルート・ハッシュ1004は、再構成されたルート・ハッシュ1004(図5のR'に匹敵する)を計算するために、ツリーのエッジ構造に従って、再構成されたルート・ハッシュ1002および認証経路のノードのハッシュ値に相続く連結およびハッシュ演算を適用することによって計算され、これは、データ・ブロックD3を検証するために、ルート・ノードのハッシュ値と比較されることができる。
図10は、一般化ハッシュ・ツリーについてのマークル証明を実行するために、古典的な二分または非二分のマークル・ツリーの場合と同じ原理が適用されるという事実を示す。マークル経路は、依然として、ルート・ノードに到達し、再構成されたルート・ハッシュ1004をその既知の値と比較するために必要とされるハッシュの最小限の集合のみである。
図10に示される例では、マークル証明(認証経路)は、ハッシュ(これは、前述したように、好ましくは、少なくとも機微なデータについては、ブロックD3の二重ハッシュである)値がノードPによって与えられるデータD3のブロックに対して計算される。このデータ・ブロックがツリーによって表されるデータセットの要素であることを確認するには、ノードN,O,Q,R,K,F,C,Dのハッシュ値が順に必要とされる。
ノードPについての再構成されたルート・ハッシュ102をそのきょうだいと連結してハッシュすることによって、ノードJについての再構成されたハッシュ値が計算される。このプロセスは、ルート・ノードAに到達するまで繰り返され、それは、期待されるマークル・ルート・ハッシュ値(すなわち、ルート・ノードのハッシュ値)に等しいべきである。
古典的なマークル・ツリーを使った証明と比較して、一般化ハッシュ・ツリーで使用されるマークル存在証明を調べるときに、いくつかの興味深い特性が現れる。
特性1:必要なハッシュ数
先のセクション2.1.1を参照し、N個のデータ・ブロックを表す、深さMのそのような二分古典ツリーを考える。これらのデータ・ブロックのいずれか1つに対してマークル存在証明を実行するためには、証明成功のためには常にM=log2N個のハッシュ値が必要になる。
しかしながら、提案された一般化ツリーでは、これは当てはまらない。存在証明を計算するために必要なハッシュ値の数は、(i)ノードの深さ、および(ii)ノードのきょうだいの数によって変化する。これは、マークル証明が古典的な二分木よりも多くのハッシュ値(そして可能性としては、より多くの計算)を必要とする場合がある一方で、マークル証明がより少ないハッシュ値(よって可能性としては、より少ない計算)を必要とする場合もあることを意味する。
たとえば、図10のハッシュ・ツリーを考える。このハッシュ・ツリーは14個のデータ・ブロックを格納しているので、その二分木対応物は、N=16個のリーフ・ノード(2つのヌルまたは重複値)をもち、データ・ブロックのうち任意のものに対するマークル存在証明は、ちょうど4つのハッシュ値を必要とする。
しかしながら、図10のハッシュ・ツリーは、ノードCおよびDの存在を証明することが、2つの値しか必要とせず(二分木より少ない)、ノードN,O,P,QまたはRについては8個を必要とするようなものである。
図11は、一般化されたマークル・ツリー構築と古典的なマークル・ツリー構築における、証明に必要とされる、変化するハッシュ数の比較を示す。これは、一般化されたマークル・ツリー構築と古典的なマークル・ツリー構築との間での、必要とされるハッシュ数の対照を実証している。
特性2:二重目的証明
古典的なマークル・ツリーでは、すべてのリーフ・ノードがツリーの最下層(m=M)に位置するため、すべてのマークル証明は同数のハッシュ計算を必要とする。
言い換えると、マークル証明の一部として「連結してハッシュ」演算が実行される回数は、各データ・リーフについて同じになる。深さm=Mのツリーについて、ルート・ノードがm=0にある場合、それぞれのマークル存在証明は、ちょうどM回のそのような演算を必要とする。
これらの演算は図11において矢印で表される。それぞれの矢印は、ノードをそのすべてのきょうだいと連結し、ハッシュして結果を得る操作を表している。
これらの演算(矢印)の数は、マークル存在証明が実行されているリーフ・ノードの深さのみの関数である。このため、古典的なマークル・ツリーでは、すべての証明はM回の操作を必要とする。つまり、すべてのリーフ・ノードがツリーの最下部にある。
しかしながら、一般化されたマークル・ツリーは、リーフ・ノードがツリー内の任意のレベルに存在しうるように指定されている。これは、マークル証明に関わる演算の数が、実際には、1から最大Mまでの範囲で変動することを意味する。
この違いは図11において明らかで、左側のツリー(古典的)でのすべてのマークル証明はちょうどm=M=4回の演算を必要とするが、右側のツリー(一般化)では演算数は、最下位レベルのデータ・パケットについての4から、データ・パケットD8についてのたった1まで変化する。
マークル証明のための演算の数が一般化ハッシュ・ツリーの場合には変化があるという事実自体が、これらのマークル証明が今では二重の目的であると考えられることを意味する:
目的1:データ・パケットが、より大きなデータセットの要素であることを、完全なデータセットを所有することなく、示すことを可能にするマークル証明存在。
目的2:データ・パケットが、セットに属するデータの階層構造における特定のレベルで存在することを示すことを可能にするマークル存在証明。
これらの目的のうち第1のものだけが、古典的なマークル・ツリーを用いて実装される標準的なマークル存在証明に適用できる。一方、一般化ハッシュ・ツリーに対して実行されるマークル証明に対しては、両方が適用される。
これは、一般化ハッシュ・ツリーについてのマークル証明が、古典的な場合と同じ集合メンバーシップの証明を達成するだけでなく、証明を実行する際に使用される演算の数が、データがハッシュ・ツリーに含まれる高さ(レベル)を明らかにするからである。
データ・リーフが階層構造を形成する場合、マークル証明は、データが所与のレベルmでツリーに挿入されたことを示すために使用されうる。すなわち、証明がちょうどm回の「連結してハッシュ」操作を含む場合である。よって、集合メンバーシップとその集合〔セット〕内の階層構造位置の両方である。
4.例示的なブロックチェーン・エンコード
図12Aは、一般化ハッシュ・ツリー(本明細書では同義に、一般化されたマークル・ツリーと呼ばれる)の形のデータ構造の概略的なブロック図を示す。一般化ハッシュ・ツリーは、参照番号1200によって示され、一般化ハッシュ・ツリー・スキーマによって与えられる追加的な柔軟性を利用する仕方で構築された複数のノードおよびエッジを含むように示されている。これは単に例解用の例であり、一般化ハッシュ・ツリーは、上記の要件を満たす任意の形をとることができることが理解されるであろう。
一般化ハッシュ・ツリー1200の各ノードは、円で表され、それを共通のルート・ノードN0に接続するエッジの数によって定義されるレベルを有する。すべての一般化ハッシュ・ツリーの場合と同様に、すべての他のノードが直接的または間接的に接続されている単一の共通のルート・ノードN0が存在する。ルート・ノードN0は、ゼロのレベルをもつ一般化ハッシュ・ツリーの唯一のノードである。
図12Aの例は、レベル1の3つのノードを示す。すなわち、そのノードからルート・ノードN0への単一の方向性エッジによってルート・ノードN0に直接接続される3つのノード。これら3つのレベル1ノードのうち、2つは非リーフ・ノードであると示されており、3つめはリーフ・ノードであると示されている(非リーフ・ノードは、少なくとも1つの他ノードが方向性エッジによってそれに直接接続されている任意のノードであり、該他のノードは、そのリーフ・ノードの子ノードと称される;非リーフ・ノードは、この意味での子ノードのない任意のノードである)。
親ノードに間接的に接続されたノード(すなわち、一つまたは複数の他のノードを介して、よって、2つ以上の方向性エッジによって、親ノードに接続されたノード)は、親ノードの孫ノードと呼ばれてもよい。そのような親ノードはそれぞれ、その子または孫の祖先と呼ばれてもよい。
以下の説明では、曖昧さ回避のために必要でない場合には、各インデックス・タプルからのコンマは省略される。よって、たとえば、N001という表記は、本稿の他の箇所のN0,0,1と等価である。
上述のインデックス付けシステムによれば、レベル1の2つの非リーフ・ノードはN00およびN01で示され、レベル1の非リーフ・ノードはN02で示される。
ノードN00は、N000とN001で示される2つの子ノードがある。本例では、これらの子ノードN000およびN001は両方とも、それら自身の子ノードをもたないリーフ・ノードとなっている。これらは、一般化ハッシュ・ツリーにおいてレベル2にあり、レベル1のノードN00(ノードN000とN001の両方の「親」ノード)を介し、それぞれ合計2つの方向性エッジ(そのノードから親ノードN00へのエッジと、親ノードN00からルート・ノードN0への方向性エッジ)を介して、ルート・ノードN0に接続される。
ノードN01は、レベル2において、N010、N011およびN012で示される3つの子ノードをもつことが示されている。これらの子ノードの1つは、それ自体が非リーフ・ノードであり、上記のインデックス付けスキームによれば、最も低いきょうだいインデックス0を有する(すなわち、該非リーフ子ノードはノードN010)。次に、このノードは、ハッシュ・ツリー1200においてレベル3に、N0100およびN0101で示される2つの子ノードをもつことが示され、これらのノードは、いずれも、本例ではリーフ・ノードとなっている。これらのレベル3の子ノードのそれぞれは、親ノードN010とそれ自身の親ノードN01を介して、合計3つの方向性エッジを介して、間接的にルート・ノードN0に接続される。
ノードN01の残りの子ノード、すなわちノードN011およびN012は、それ自身の子ノードをもたないリーフ・ノードである。
各リーフ・ノードは白丸で表され、ルート・ノードN0を含む各非リーフ・ノードは黒丸で表される。各リーフ・ノードのハッシュ値は、文書、ファイルなどのデータ・ブロックの二重ハッシュである。一般に、データ・ブロックは任意の形をとることができ、単に、リーフ・ノードのハッシュ値を得るために二重ハッシュされる原像を指す。各方向性エッジは、子ノードから親ノードへの実線矢印で示される。
表記Diは、ノードNiのハッシュ値を得るために二重ハッシュ化されたデータ・ブロックを示すために使用される。ここで、iは、その非リーフ・ノードのインデックス・タプルを示す。上記のスキーマによれば、インデックス・タプルの長さはノードのレベルとともに増加する。よって、たとえば、ノードN0100のハッシュ値を計算するためにハッシュされたデータ・ブロックはD0100で示され、リーフ・ノードN001のハッシュ値を得るためにハッシュされたデータ・ブロックはD001で示される、などとなる。そのようなデータ・ブロックのそれぞれは、図12Aでは、点線の輪郭をもつ円によって表され(注:これは、本明細書で使用される定義に従う一般化ハッシュ・ツリーのノードではない)、データ・ブロックと対応するリーフ・ノードとの間の関係を表すために点線矢印が使用される(注:これは、本明細書で使用される定義に従うデータ構造のエッジではない)。データ・ブロックと非リーフ・ノードの間の二重ハッシュ関係は、演算子H2によって示される。
上記のスキーマによれば、各非リーフ・ノードのハッシュ値は、原像の単一ハッシュであり、その原像は、そのすべての子ノードのハッシュ値を連結することによって形成される連結ストリングの形である。よって、例として、ノードN00のハッシュ値は、その子ノード、すなわちノードN000とN001のハッシュ値の連結のハッシュである。これは図12AではH(…||…)で示されており、連結が、任意の数ありうる子ノードすべてにわたることに注意しておく。
一般化ハッシュ・ツリー・スキーマは、単一の子ノードをもつ親ノードを認めるのに十分な柔軟性がある。その場合、親ノードのハッシュ値は、単一の子ノードのハッシュ値のハッシュである。
図12Aの例では、ノードN00の子ノードは両方とも、リーフ・ノードとなっている。しかしながら、一般化ハッシュ・ツリー・スキーマは、子ノードがリーフ・ノードと非リーフ・ノードの混合である非リーフ・ノードも認める。ノードN01はこのカテゴリーに入り、そのハッシュ値は、その非リーフ子ノードN010のハッシュ値と、そのリーフ子ノードN011およびN012のハッシュ値との連結のハッシュである。
非リーフ子ノードN010のハッシュ値は、その子ノードN0100およびN0101のハッシュ値の連結のハッシュであり(この例では、両方ともリーフ・ノードとなっており、よって、対応するデータ・ブロックD0100およびD0101の二重ハッシュとして導出される)、
所与のリーフまたは非リーフ・ノードNiの試験値は、ここではHiで示されてもよい。しかしながら、本開示の他所では、表記Eiはハッシュ値自体を表すために使用されることがあることに留意されたい。意味は文脈において明確であるはずである。
ノードN0100とN0101はノードN01とN01の孫である。ノードN000とN001は、ルート・ノードN0のみの孫である。
図12Bおよび図13は、図12Aの一般化ハッシュ・ツリー1200が、ブロックチェーン・トランザクションのシーケンスにおいてどのように具現されうるかを示す。
図12Bは、その構成要素ノードのレベルを示すためにマークされた、同じ一般化ハッシュ・ツリー1200を示している。データ・ブロックは、図12Bからは省略されている(いずれにせよ、上記したように、これらは、一般化ハッシュ・ツリー1200の一部をなすものではなく、データ・ブロック自体は、この例では、ブロックチェーンに格納されない)。
図13は、ブロックチェーン内の一般化ハッシュ・ツリー1200をエンコードおよび格納するために使用されうる一連のブロックチェーン・トランザクションを示す。この例示的なエンコードでは、トランザクションTx0(ルートトランザクション)はルート・ノードN0を表すために使用される。
ルート・トランザクションTx0に加えて、1つのトランザクションが、きょうだいノードの各セットを表すために使用される。すなわち、この例では、同じ親ノードをもつすべてのノードが、1つのトランザクションにおいて一緒にグループ化される。
よって、この例では、ルート・ノードN0の3つの子ノード、すなわち、N00、N01、およびN02は、レベル1トランザクションと呼ばれる単一トランザクションTx1においてエンコードされる(これらのノードがツリーにおいてレベル1にあるという事実を反映している)。
レベル2トランザクションは、参照符号Tx2aとTx2bでそれぞれ示される2つがある。第1のレベル2トランザクションTx2aは、レベル1のノードN00の子ノード、すなわちノードN000およびN001をエンコードする。同様に、第2のレベル2トランザクションTx2bは、ノードN01の3つの子ノード、すなわちノードN011、N010、およびN012をエンコードする。
単一のレベル3トランザクションTx3は、ノードN010の子、すなわちノードN0100およびN0101をエンコードする。
各トランザクションTx0~Tx3において、そのトランザクションによってエンコードされる一つまたは複数のノードのハッシュ値が、そのトランザクションの一つまたは複数の出力に含まれる。すなわち、各ノード・ハッシュ値は、そのトランザクションの出力に直接エンコードされ、複数のノードを表すトランザクションの場合、それらのノードのハッシュ値は、そのトランザクションの同じ出力または異なる出力に明示的に含まれてもよい。
ある実装では、ハッシュ値は、たとえばOP_DROPまたはOP_RETURNを使用して、トランザクションTx0ないしTx3の使用不能な出力に含まれる。
別の例として、ハッシュ値は、チェック・マルチ署名オペランド(CHECKMULTISIG)のダミー・オペランドとして含まれてもよい。
トランザクションTx0ないしTx3のそれぞれは、少なくとも1つの使用可能な出力(これは、任意のノード・ハッシュ値が含まれる前記出力であってもなくてもよい)をもつ。一般化ハッシュ・ツリー1200の方向性エッジは、トランザクション間の使用関係としてエンコードされる。
レベル3トランザクションTx3から始まり、このトランザクションは、第2のレベル2トランザクションTx2bによって費やされる使用可能な出力をもつ。すなわち、第2のレベル2トランザクションTx2bの入力は、参照符号P2bで示されるレベル3トランザクションTx3の出力へのポインタを含む。このポインタP2bは、第2のレベル2トランザクションTx2bとレベル3トランザクションTx3との間の使用〔消費〕関係をエンコードするだけでなく、レベル2の非リーフ・ノードN010(トランザクションTx2bにおいてエンコードされる)と、その2つの子ノードN0100とN0101(両方ともトランザクションTx3においてエンコードされる)からの2つの方向性エッジもエンコードする。
レベル1のトランザクションTx1は、少なくとも2つの入力を有し、そのうちの1つは、第1のレベル1のトランザクションTx2aの出力を使用し、もう1つは、第2のレベル2のトランザクションTx2bの消費可能な出力を使用する。これは、レベル1トランザクションTx1においてエンコードされたレベル1ノードと、レベル2トランザクションTx2aおよびTx2bにおいてエンコードされたレベル2ノードの間の関係を捉える。Tx2aは、レベル1のノードN00のすべての子ノードをエンコードし、第2のレベル2のトランザクションは、レベル1のノードN01のすべての子ノードをエンコードする。
最後に、ルート・トランザクションTx0は、ルート・ノードのハッシュ値をエンコードし、ルート・トランザクションTx0は、レベル1トランザクションTx1の使用可能な出力を使用する少なくとも1つの入力をもつ。
実装に依存して、暗号学的ハッシュ関数の数学的特性は、ある程度、ハッシュ・ツリーの構造をエンコードするために利用されうる。たとえば、複数の要約ハッシュを含むトランザクションについて、各要約ハッシュを、1レベル下のノードの既知の集合のサブセットに解決することは常に可能である。なぜなら、連結したハッシュが要約ハッシュに等しくなるノードのサブセットは一つしかないからである。よって、トランザクションが複数の要約ハッシュを含む場合でも、それらの要約ハッシュを下の、次のレベルの子ノードのそれぞれのサブセットに明示的にマッピングすることは本質的ではない。なぜなら、その情報は、それらの数学的特性の中にすでに捕捉されており、よって、データから曖昧さなく推論できるからである。ハッシュ値の数学的特性に依存するほうが、トランザクション内の冗長データの量を減らすので、メモリ効率がよい可能性がある。
しかしながら、代替として、ある程度の冗長データが導入されてもよく、これは、いくぶんメモリ効率が低くなるかもしれないが、他方では、ハッシュ・ツリーが、より少ない計算資源を使用して再構成/解釈されることを許容しうる(すなわち、計算効率がより高い)。たとえば、入力スクリプトは、各要約ハッシュに入るノードが適切な(任意の)マーカー(たとえば、OP_0または他の任意のマーカー、たとえば<data>プッシュ)によって分離され、ノードの分離された諸集合の順序(すなわち、それらが描かれているように左から右)が要約ハッシュの順序に対応するように、さらに修正されてもよい。
たとえば、要約ハッシュH
00およびH
01について、Tx*の入力アンロック・スクリプトは、次のように読まれてもよい。
これは、H
00はTx*の出力スクリプトにおける最初の要約ハッシュであるため、D
001が要約ハッシュH
00への欠けている入力であるという事実を伝えている。すなわち、トランザクションの入力と出力の間のデータの一貫した順序付けは、計算効率のよい仕方でトランザクション・データを解釈するのに有用である。
5. オンチェーン表現とオフチェーン表現
図13のトランザクションTx0~Tx3の集合は、トランザクションがブロックチェーン・トランザクションのノードに提出され、その後のある時点で一つまたは複数のブロック151にマイニングされうるという点で、「オンチェーン」エンコードである。
本例では、上記のインデックス付けスキームに従って計算されたインデックスは、ブロックチェーン・トランザクションTx0~Tx3において明示的にエンコードされず、むしろ、データ構造1200のノード間の階層的関係が、これらのトランザクション間の使用関係としてエンコードされる(これは次いで、これらのトランザクション間のポインタとして捕捉される)。データ構造1200をブロックチェーンにコミットする前に、またはコミットした後にそれをオフチェーンで再構築するために、インデックス付けスキームは、データ構造1200の初期のオフチェーン表現の一部として、オフチェーンで実装されてもよい。
図14は、オフチェーン・システム1400の電子記憶装置1404(オフチェーン記憶)へのアクセスを有する一つまたは複数のコンピュータ1402を備えることが示されている、オフチェーン・システム1400の高度に概略的なブロック図を示す。各コンピュータは、汎用プロセッサ(CPU、GPU/アクセラレータ・プロセッサなど)のような一つまたは複数のコンピュータ・プロセッサ、およびまたはオフチェーン・システム1400の記載された機能を実行するためのFPGA、ASICなどのようなプログラマブルまたは非プログラマブルな特殊目的プロセッサを含む。オフチェーン・システム1404は、一般化ハッシュ・ツリー・データ構造1200をブロックチェーン150にコミットするためにブロックチェーン150に記録するために、トランザクションTx0~Tx3のうちの一つまたは複数をブロックチェーン・ネットワーク101に提出すること、および、そこからオフチェーン記憶1404内で一般化ハッシュ・ツリー・データ構造1200を再構築するためにトランザクションTX0~Tx3のうちの一つまたは複数を取り出すことのうちの一方または両方を行うために、ブロックチェーン・ネットワーク101の少なくとも1つのノードと通信するように動作可能である。
いずれの場合においても、一般化ハッシュ・ツリー1200のバージョンは、少なくとも一時的に、オフチェーン記憶1404内に維持される。上記の動作を実装するため――ノードの式に従ってノードツリーを構築するか、またはマークル証明を使用して受信されたデータツリーを検証するかのいずれかのため――に、オフチェーン記憶1404内の一般化ハッシュ・ツリー1200の前記バージョンの各ノードは、上記のインデックス付けスキーム(上記の規則6~8)に従って計算されたインデックス・タプルを割り当てられてもよい。
図15では、オフチェーン記憶1400に格納された一般化ハッシュ・ツリー1200のバージョン(オフチェーン・バージョン)は、参照符号1200'によって示される。示されるように、その各ノードは、明示的に計算されたインデックス・タプル1402に関連付けられる。
代替的または追加的に、各インデックス・タプルは、ブロックチェーン・トランザクションTX0~TX3自身において明示的にエンコードされてもよい。これは決して本質的ではないが、トランザクション・データを解釈するのを支援する。たとえば、すべてのインデックスが明示的にエンコードされている場合、処理エンティティは、事前に「規則」を知ることなく、すべてのデータがツリー内でどのように収まっているかを割り出すことができうる。
協働的認証プロトコル
ここで、協働的認証プロトコルのさらなる詳細について述べる。
緒言
知的財産(IP)産業は、消費者製品の価値の約3分の1を占める無形資産の決定において重要な役割を果たしている。2017年だけでも、世界の特許、商標の出願件数はそれぞれ320万件、1,240万件であったと推定され、8年連続の増加となった。つまり、知的財産(IP)は個人や組織にとってきわめて価値の高い資産であることがあり、そのようなものとしてうまく管理されるべきである。
IP管理システムを作り出す際に考慮すべき主な事項は、おおまかに次のカテゴリーにはいる。
1.発明者および著作者への権利の割り当て;
2.発明の開示;
3.知的財産のライセンス供与。
著作者性の割り当て
伝統的に、新規の創造的な作品の著作者性(authorship)の割り当ては、複雑な手順でありうる。一般に、発明者に指名される権利は、新規なアイデアの原着想者に自動的に帰属する。しかしながら、この情報がどのように記録され、それがIPの最終的な所有権にどのように変換されるかは、はるかに不明瞭である。たとえば、大企業では、新技術・発明についての権利や著作者性の効果的な割り当ては、社内で、雇用契約に定められた条件に従って行われることが多い。すなわち、「職務著作物」である。特に、IP生産性が高い事業においては、「職務著作物」の知的財産権が使用者のみに帰属しうる場合であっても、このことは、指名された発明者の地位や、異なる寄与者による新規の作品の着想の時間順序をめぐる内部争いにつながることがある。
IPの発明者性の割り当ては、第三者の公証人が関与することもある。第三者の公証人は、署名と権限を認証・証明し、発明者や創作者が知的財産に関する権利や著作者性を主張できるようにする。業界で重要な機能を果たしているにもかかわらず、これらの公証人は、煩雑で高価な手続きを経て業務を行っている。
歴史的な解決策は、発明者が徹底的な「発明ノート」または同等の文書を採用することであろう。しかしながら、実施が不十分な場合、これらは紛争を悪化させることがあり、典型的には、危殆化された場合には、変更可能であり、改竄可能である。
著作者性および所有権を知的財産に割り当てるための、より効率的で、費用効果が高く、特徴的に論争の余地のないシステムを開発することが望ましい。特に、保護されるべき技術が複数の寄与著者による複合作品である場合にはなおさらである。
発明の開示
発明または他の形の知的財産が公に開示される時点は、それが知的財産法に基づいて保護されうるか否かに関係がある。ほとんどの法的管轄区において、競合する特許出願に関する場合、現在のパラダイムは、「最初に出願」した出願が、特許の付与を成功させるための優先権を主張するというものである。
これは、発明者が、その発明を十分に詳細に文書化し、できるだけ早い機会に特許出願を行うインセンティブを与えられることを意味する。このプロセスは、当然のことながら、新規なアイデアの最初の着想から特許出願としての出願までの間に遅延を生じさせる。
着想から出願までの中間期間は、発明者にとってのリスクをもたらす。競合者が、この期間に同等の発明を着想し、出願することができる可能性があるからである。よって、発明者にとって、最終出願日より前における自分の作品の存在証明を提供する機構を有することが有利である。
IP管理のための代替的なブロックチェーン・ベースの解決策は、主に、変更不能な存在証明を提供するという孤立した問題を解決することを目指す。しかしながら、これらの解決策は、一般に、IP自体の所有権と著作者性の階層構造をも確立し、反映するように行うことができない。
本願の実施形態は、保護される作品にインテリジェントな構造を提供することにより、これらの問題に同時に対処する、知的財産を管理するための新しいブロックチェーン・ベースの方法を提供する。
ブロックチェーンでの知的財産
本明細書における実施形態は、多様な保護される作品のために使用されうる、発明的プロセスにおける事象のIP登録簿およびタイムスタンプ台帳の両方として、公開ブロックチェーンを使用するための方法を提供する。ブロックチェーンの特性を利用することによって、上述の問題に対する技術的な解決策が提供される。
知的財産のアーティクルは、存在を証明する手段として、暗号化され、ハッシュ化され、ブロックチェーン上に格納される。格納機構はまた、その著作者性を反映し、発明者に権利を割り当てるハッシュ・ツリー実装を使用する。
予備的事項
協働的認証プロトコルは、原理を上述した一般化ハッシュ・ツリーを利用する。
加えて、以下の予備的事項は、記載される実施形態に関連する。
楕円曲線デジタル署名(Elliptic Curve Digital Signatures)
デジタル署名は、送信されるメッセージについて以下のことを提供する数学的スキームである:
・認証(Authentication)-メッセージは特定の当事者によって署名された
・否認防止(Non-repudiation)-署名者はメッセージに署名したことを否定できない
・完全性(Integrity)-メッセージは、伝送中に変更されていない。
楕円曲線デジタル署名アルゴリズム(Elliptic Curve Digital Signature Algorithm、ECDSA)は、資金が正当な所有者によってのみ使用できることを保証するために、ビットコイン(Bitcoin)によって使用される暗号デジタル署名方式である。
ECDSA署名に必要なパラメータは下記を含む:
E-楕円曲線関数
G-位数nの楕円曲線上の基点、ここで、n・G=O
n-大きな素数
鍵ペア生成アルゴリズム
公開鍵Pが生成されるもとになる秘密鍵x
0<x<nとなるように乱数xを選択する
P=x・G
署名アルゴリズム
メッセージm、乱数k、秘密鍵xが与えられた場合、ペア(r,s)を用いて署名を生成する
k-乱数0<k<nを選択する
r=k・Gを計算する
s=k-1(m+xr) mod nを計算する
ここで、k-1は、k mod nの乗法の逆元であり、k-1k≡1 mod nとなる。
検証アルゴリズム
署名(r,s)メッセージmと公開鍵yが与えられて、署名を検証する
s-1は、s mod qの乗法の逆元であり、s-1s≡1 mod nとなる
v=s-1m・G+s-1r・yを計算する
v=rであれば、署名は有効。
ブロックチェーン上のデータの格納
ブロックチェーン技術の採用が進むにつれて、これを支える規模拡大インフラとともに、ブロックチェーン上に大量のデータを挿入することへの関心が高まっている。ブロックチェーン・トランザクションのさまざまなフィールドの使用を通じて、データをブロックチェーンに格納することが、実際に可能である。ブロックチェーンへのデータの格納は、大まかには、使用不能なOP_RETURNオペコードを使用するか、OP_DROP文を使用するかの2つの方法のうち少なくとも1つでできる。
OP_RETURNの使用
OP_RETURNオペコードでマークされたトランザクション出力は、OP_RETURNがスクリプト実行を失敗させるので、使用不能であることが証明可能な〔証明可能的に使用不能な〕出力として知られている。したがって、次のタイプのロック・スクリプトにおいて、そのようなオペコードの後に任意のデータを格納することができる:
OP_RETURN <D>
OP_RETURNオペコードの後に続くスクリプトをマイナーや検証者が実行することは決して要求されない。つまり、このデータ格納方法は、通常、スクリプトの一部に格納されているデータに適用されるフォーマット要件を満たす必要がないという利点がある。
OP_DROPの使用
ブロックチェーン・トランザクションにデータを格納するために使用できるもう1つの方法は、OP_DROPオペコードを使用することである。これは、次の形のロックまたはアンロック・スクリプトにおいて使用できる。
OP_PUSHDATA OP_DROP
これは通常、OP_PUSHDATAオペコードを、スタックにプッシュされるデータ要素を山括弧で囲んだもので置き換えることによって、次のように、より簡単に表現される
<D> OP_DROP
しかしながら、そのようなスクリプトに格納されたデータは、スクリプト実行およびトランザクション有効確認によって組み込まれるスクリプトレベルのチェックの対象であることに注意されたい。
マルチ署名スクリプトの使用
ビットコインでは、m-of-n〔nのうちのm〕の特定の公開鍵に対応する任意のm-of-n署名を提供することにより、ロック解除できるトランザクション・ロック・スクリプトを構築することが可能である。そのようなマルチ署名トランザクションのためのロック・スクリプト条件は、次のように書かれる。
[CheckMultisig m-of-n]=OP_m <P1>…<Pn> OP_n OP_CHECKMULTISIG
このマルチ署名ロック・スクリプトは、公開鍵P1,…,Pnのサブセットを他のデータ(ここでは「ダミー・オペランド」と呼ばれる)で置き換えることによって、データを埋め込むために使用できる。マルチ署名ロック・スクリプトは、たとえば、1つの有効な公開鍵P(関数オペランド)のみで、n-1個のデータ要素を(ダミー・オペランドとして)埋め込むために使用できる。これは、概略的に次のように書かれる。
[CheckMultisig 1-of-n]=OP_1 <P><D1>…<Dn-1> OP_n OP_CHECKMULTISIG
この形式のロック・スクリプトは、トランザクション・ロック・スクリプト内に著者の寄与の二重ハッシュおよび裁量署名を提供する手段として、著作権割り当てハッシュ・ツリーのブロックチェーン・ベースの実装(または、より一般には、一般化ハッシュ・ツリー1820のような最終的な作品への階層的な寄与を表すハッシュ・ツリー)のいずれかにおいて使用されうる。
協働的認証プロトコル(Collaborative attestation protocol)
一般化ハッシュ・ツリーが、図19Aおよび19Bを参照して上述した例と同じまたは類似の原則に従って、協働的認証プロトコルを実装するために使用される。このプロトコルは、一般に、協働的作品またはプロセスの一部の文書化および認証に適用することができる。例として、ブロックチェーンに格納できる「著作権割り当て(copyright assignment)」ハッシュ・ツリーを作成する特定のアプリケーションを考える。本明細書は、協働的作品またはプロセスを表すハッシュ・ツリーの任意の形に等しく適用されることが理解されるであろう。最終目標は、著作権または他の形の作品を表す、変更不能な仕方で格納されたハッシュ・ツリーにおいて、知的財産権の割り当てに関与する階層構造を反映できることである。
目的
記述された実施形態の目的は、権利の階層構造がハッシュ・ツリー自体にも反映されるように、著作権作品と一般化ハッシュ・ツリー構造との間のマッピングを確立することである。すると、ブロックチェーン上に変更不能な仕方でハッシュ・ツリーを格納することは実装の問題である。これを実現するために、以下の特性が、記述されている著作権割り当てハッシュ・ツリーについて記載される:
1. 一般化ハッシュ・ツリーのすべての特性をもつ:
i. データは任意のレベルに存在できる。
ii. あるレベルで挿入されるデータ寄与の数は任意でありうる。
iii. データ・リーフは、単一の反樹枝状の有向ツリー構造を形成する。
iv. マークル証明は、挿入されたデータのどの部分に対しても実行できる。
2. 権限、所有権、または組織構造の階層構造を反映する。
3. すべての個々の構成要素を含む著作権作品の形成を追跡できる。
条件(2)と(3)は微妙に異なるが、これは、(2)は著作権のある作品に対する権利の権限チェーンをたどることが可能であることを確実にし、一方、(3)は作品そのものの形成をたどることを可能にすることを確実にするからである。
最終的な著作権作品に対するそれぞれの個々の寄与は、最終的な作品の別個の構成要素として見ることができるように記録される。これは、個々の寄与をツリー内のリーフ・ノードとして含めることによって達成される。
また、ツリー構造から、作品の構成要素部分がどのようにフィットするかを追跡することも可能である。たとえば、白書の2つのセクションが書かれ、リーフ・ノードとして含まれる場合、ツリーは、これらのセクションが後に最終的な文書を形成するためにどのように組み合わされるかのその後の記録を提供する。
これは2つの仕方で達成される。非リーフ/中間ノードは、著作権作品の構成要素の履歴を直接表現するために使用される。より高いレベルに現れるリーフ・ノードは、最終的な作品に対する編集上の変更を表すために使用される。
例
アリスとボブ(研究者など)という、別個だが等しいランクの2人の著者によって書かれた白書の2つのセクションD1,1およびD1,2を考える。それらは、それぞれH2(D0,0)、H2(D0,1)としてレベルm=5に含まれている。
m=4にあるそれらの親ノードは、値H(H2(D0,0)||H2(D0,1))をもつ仲介ノードとして単純な履歴を表す。ここで、演算子||は連結を示す。
しかしながら、ラインマネージャのキャロルからの編集上の変更も、同じレベルm=4に、値がH2(D0)であるリーフ・ノードとして含まれる。ここで、D0は、キャロルがアリスとボブのコンテンツに対して行った任意の変更E0,0、E0,1をエンコードする、組み合わされた作品の更新された状態と、著作権作品の新しい状態に対するキャロルからの任意のオリジナルな寄与O0とを表す。これは図20に示される。
図20は、データがどのようにハッシュ・ツリーに追加され、その関係が最終的な文書または著作権作品の組織上の階層構造および形成の両方を追跡するかを示している。
次に、ハッシュ・ツリーにおけるノードとして格納されるデータの意味に焦点を当てて、著作権割り当てツリーの具体的な例示的な形について説明する。
権限の階層構造(Hierarchy of Authority、HoA)
著作権作品の制作において、トリビアルでない階層構造が関わることが多い。関わる可能性のある役者(actor)のうちのほんの若干を挙げると、オリジナルのコンテンツを生み出す発明者、オリジナルのコンテンツを改変し、独自のコンテンツを提供することもある編集者、文書の特定の部分を承認する必要があるかもしれないアドバイザー、および典型的に作品に対する最終的な権利を有することになる所有者がありうる。そのような当事者はすべて、本明細書で使用される用語「寄与者」の例である。一般に、寄与者は、適当なコンピュータ装置を操作する人間(アリスおよびボブのような)であってもよく、または、寄与者は、コンピュータ生成される寄与の場合、コンピュータ、アプリケーション等であってもよい。
理想的には、最終的な作品へのすべての寄与者は、しばしば複雑になるであろう、権限の指示階層構造(indicative hierarchy of authority)において代表されるべきである。たとえば、階層構造の1つのレベルに複数の編集者がいることがある。それにより、前段階の作品を単に変更する編集者と、自分のオリジナルなコンテンツを追加する編集者とを区別する必要がある。一般化ハッシュ・ツリー構造は、これらのニーズに対応することができる。
一般に、寄与者は3つの異なるクラスの役者に分けられる:
下位著者(junior author)-オリジナル・コンテンツだけを提供できる寄与者。これらは典型的には発明者でありうる。図18Bでは、これらは第1および第2の下位著者グループC-A、C-Bのメンバーである。
上位著者(senior author)-下位著者の作品に基づいて構築される編集コンテンツおよび/またはオリジナルのコンテンツを提供する可能性のある寄与者である。これらは典型的には、編集者またはアドバイザーでありうる。図18Bの例では、これは、レベル3およびレベル2の両方の寄与者C-C0、C-D0、C-E0、C-F0、C-F1を包含する。
エグゼクティブ著者(executive author)(単数または複数)-これらは、下位著者、上位著者、またはその両方の作品に基づいて構築される編集コンテンツおよび/またはオリジナルのコンテンツを提供しうる寄与者である。また、典型的には、ルート著者が、著作権作品に対して最終的な承認権を有する。これらは、図18Bにおける主任編集者C-G0のような、エグゼクティブまたは所有者である。
同じ役者が複数のタイプの寄与者として組織権限階層構造(organisational hierarchy of authority)において関与している可能性はあるが、記載される実装では簡単のためそのようなシナリオを無視していることに注意されたい。しかしながら、一般化ハッシュ・ツリーは、これらのケースに対応するのに十分に柔軟な構造をもつ。たとえば、下位著者は、自分のオリジナル作品のその後のバージョンのための編集役割にも関与することがある。この場合、組織HoAとそれを表すハッシュ・ツリーの両方において、同じ役者が複数のレベルで現れることが想定される。
図18Bにおける一般化ハッシュ・ツリーのブロックチェーン・ベースの実装は、たとえば、新聞についての権利の階層構造を捉えるのに適しているであろう。新聞の組織階層構造は、図18Aに示されているものであろう。
この使用事例では、下位著者C-A、C-Bはジャーナリストであり、その全員が生のオリジナル・コンテンツD-A0、…、D-B2を寄与している。上位著者のC-C0、…、C-F-1は複数の編集層を含み、一部の編集者(レベル3の編集者のC-C0、C-D0)は、ジャーナリストに対して簡単な編集権限をもつことがあるが、より上のランクの上位編集者(レベル2の編集者C-E0、C-F0、C-F1)は追加のオリジナル・コンテンツを提供しうる。最後に、単一のエグゼクティブ著者C-G0が、新聞文書――最終的な作品D――を出版するために承認する最終的な権限をもつ主任編集者(editor-in-chief、EIC)を表す。すべての著者が自分に関連付けられたデータをもちうることに注意されたい。
上述したように、図18Aの各著者は一意的な公開鍵を有しており、それを用いてデジタル署名を作成し、ブロックチェーンを使用してトランザクションをすることができる。以下の説明では、表2に示される数学的表記が、図18に示される公開鍵を表すために使用され、これは、上に記載された一般化ハッシュ・ツリーのためのインデックス付けスキームと整合する。
表2:新聞の権限階層構造(HoA)(寄与者階層構造)の各役者に属するクラスと公開鍵
階層構造は、一般化ハッシュ・ツリー発明の有用性を説明するために、二分木ではないことに注意されたい。また、この例の代わりに、多くのもっと複雑な組織構造を用いることもできることに注意されたい。
著作権割り当てハッシュ・ツリー(copyright assignment hash tree)
著作権作品の形成に反映されるべき組織階層構造を確立したので、この目標を達成するためにハッシュ・ツリーが使用できる。
図21は、古典的な二分マークル・ツリーが新聞組織の階層構造を表すためにどのように使用されうるかを考察している。
図21は、新聞文書の構成要素(寄与)を格納するために使用される典型的な二分マークル・ツリーを示す。
このハッシュ・ツリー構造では、いくつかの問題が明らかになる。すべてのデータ・ブロックがツリーのいちばん下の同じ層に挿入されるという事実は、ツリーにエンコードされた権限、権利、または所有権の階層構造が存在しないことを意味し、せいぜい、このいちばん下の層の左から右に、権限に従ってブロックが順序付けられることができるくらいである。これは、ツリーの構造だけでは完全な階層構造を捉えることはできない。一般に、シーケンスの中の位置だけから階層構造内での寄与者の実際のレベルを特定することはできない。左から右に向かって進んで推測できることは、権限のレベルが一般的に増加していることだけである。
しかしながら、一般的なハッシュ・ツリー構築を呼び出すことによって、ツリーの構造内に階層構造を完全にエンコードすることが可能である。これは、ハッシュ・ツリーが作成できるため、新聞の、はるかに直感的な表現をも提供する。これは、図18Bのすでに述べた一般化ハッシュ・ツリー1820であり、これは、所望される権限の階層構造を反映している。
図22は、各ノードについてノード・インデックス{0,i0,i1,…,im-2,j}がラベル付けされており、一般化ハッシュ・ツリー1820が、どのように、一般的なハッシュ・ツリー構造に従うかを示す。すべてのインデックスは、値0から上に進む負でない整数であることを想起されたい。すなわち、図22は、ノード・インデックスに従ってラベル付けされた、新聞を表すハッシュ・ツリー1820のノードを示す。
伝統的なマークル・ツリーの手法で特定された問題は、ここでは、ハッシュ・ツリー内に権限の明確な階層構造が埋め込まれ、それにより、リーフ・ノードは、ツリー内で任意のレベルに存在することができるので、是正される。
前と同様に、白丸はリーフ・ノードを示し、黒丸は非リーフ・ノードを示している。これは、新聞の組織階層構造が反映されているリーフ・ノードが、今やみなが最下部に現れるのではなく、異なるレベルに現れることを示すのに役立つ。
新聞組織のHoAは、一般化ハッシュ・ツリー内で持続する。なぜなら、各リーフ・ノードは、別個の役者の寄与または効果を表すからである。
上記の一般化ハッシュ・ツリーは、上記のような規則を使用し、各ノードには、ノードの式を使って計算できる特定のハッシュ値が関連付けられる。特に、各リーフ・ノード(白)は、挿入される何らかのデータ・ブロックの二重ハッシュであり、各非リーフ・ノード(黒)は、単に、そのすべての子を連結したもののハッシュである。
このツリーは、完全インデックス付け規則に従い、各ノードは
の形の一意的なインデックス表記をもつ。
著者の役割
著作権割り当て階層構造におけるさまざまな役者は、著者の3つのカテゴリー、すなわち下位、上位、およびエグゼクティブのいずれかにされることが特定された。著者の各カテゴリーは、著作権作品の形成においてわずかに異なる役割を果たし、そのため、各カテゴリーは、ハッシュ・ツリーに異なるデータを提供することを受けもつ。
下位著者
下位著者は、権限の階層構造の「最下位」に位置する寄与者である。もっと厳密には、これは、組織構造の中に、下位著者の直下には役者はいないということである。
下位著者によって生成されたオリジナルのコンテンツは、一般に数学的表記Dで示されており(図中ではD-xxの形の参照符号によって示される)、今の目的のためにはファイル(より一般には、データ・ブロックという用語)と称することができる。このファイルは、他の著者のコンテンツを含まないため、異なる下位著者によってなされる寄与を区別することができる。たとえば、公開鍵P0,0,0をもつ著者が、オリジナルのコンテンツD0,0,0,jを生成する。ここで、jは、問題の下位著者を表すリーフ・ノードの、その著者の「きょうだい」に対する位置によって決定される。
下位著者の鍵となる特徴は、下位著者によって作成されたコンテンツが、直接の上位者に提出されるということである。このプロセスはオフブロック(オフチェーン)で行われることが理にかなっている。下位著者に関連する可能性のあるデータタイプを以下の表にまとめておく:
表3:下位著者に関連付けられるデータ
下位著者のコンテンツの二重ハッシュは、コンテンツのオンブロック表現として使用できる。これは、決定的なことに、コンテンツ自体を明かすことなく、上位著者が、オンブロックでオリジナル・コンテンツの受領証明を提供することを許容する。
単に単一ハッシュを使用し、コンテンツ・データをオンチェーン上で公開することは全く可能であるが、二重ハッシュを使用することは、著作権作品のためには有利である。なぜなら、たとえば特許出願前に、完全な公開を行うことなく、ハッシュをオンチェーンに載せることによって、何かがある時点で存在したことを証明することが望ましいからである。
オリジナル・コンテンツのハッシュの署名は、トランザクションの提出時に、下位著者が二重ハッシュの原像を知っていることの証明として、含まれる。
この署名は、ブロックチェーン・プロトコルの一部として使用されるものではないため、裁量的とみなされ、単に、下位著者が独自の作品を作成したことを証明していることを示していることに注意されたい。そのようなデジタル署名の例はECDSAであるが、本開示はこれに限定されない。なぜなら、それは裁量署名であり、裁量署名のためには任意の署名アルゴリズムが使用できるからである。
数学的表記σ(P,m)が、裁量署名を示し(一般に、図では、DS-xxの形の参照符号で示される)、Sig(P,m)は、公開鍵Pの所有者によるメッセージmに対する非裁量的な署名を示す(上記ではトランザクション署名と呼ばれ、一般に、S-xxの形の参照符号で示される)。非裁量的な署名は、UTXOを使用〔消費〕するために使われ、ブロックチェーン・プロトコルの一部としてマイナーによって検証される署名である。
ブロックチェーン・プロトコル、すなわち、P2Pネットワーク101の動作が従うプロトコルがECDSAの使用を指定する場合、トランザクション・システムはECDSAでなければならない。しかしながら、より一般には、各トランザクション署名は、何であれ適用されるブロックチェーン・プロトコル(ECDSAであってもなくてもよい)に従って計算される。上述のように、いずれにせよ、裁量署名を計算するためには、同じまたは異なる署名アルゴリズムが使用されうる。
上位著者
上位著者は、権限階層構造の「中」(中間)レベルの著者である。上位著者の鍵となる特徴は、組織構造のHoAにおいて、直下に少なくとも1人の役者がおり、直上に少なくとも1人の役者がいるということである。
先に述べたように、上位著者は編集、助言、管理責任などの複数の機能をもつことができる。それぞれの場合において、上位著者は、その下位者からコンテンツを受け取り、それを何らかの仕方で処理することが期待される。次いで、上位著者は、(a)受領したコンテンツを編集する、(b)自分自身の新しいオリジナル・コンテンツをその作品に追加する、または(c)その両方を行うことができる。
しかしながら、通常、上位著者は下位著者よりも多くの責任を負う。著作権作品の更新された状態は、その寄与内に反映され、チェーンを通して上に伝えられ、全寄与の二重ハッシュとその単一ハッシュの署名の両方を提供する。
上位著者の寄与は、上位著者に関連するデータの下記の表を用いて理解できる。ここで、nは、上位著者の直接の下位者の数を示し、εは、ハッシュ・ツリーにおける著者の直下にある非リーフハッシュの数である。
表4:上位著者に関連するデータ
n人の直接の下位者をもつ上位著者は、それぞれの下位者から受け取ったコンテンツD0,0,0,ε,…,D0,1,1,ε+(n-1)を受け、D0,0,0,ε,…,D0,1,1,ε+(n-1)と表される対応する編集文書(editorial document)を作成する。非リーフきょうだいの数εは、ハッシュ・ツリーがHoAと整合することを保証するために、和において使用されるデータを正しくオフセットするために使用される。
何らかの受け取ったコンテンツDに加えられた変更を表す編集文書Eが形成されることができ、上位著者が編集権を持たない、あるいは変更を望まない場合、これらの編集文書はヌル・フィールドであってもよい。
上位著者は、Oで示される自分のオリジナル・コンテンツを追加することもできる。編集文書が下位者の作品に基づいている場合、このオリジナル・コンテンツは、完全に、その上位著者の孤立した作品であり、著作権作品への彼ら自身の個人的な追加を証明するために、彼らが使用することができる。
上位著者の全寄与は、その編集文書とそのオリジナル・コンテンツの両方を考慮に入れ、それらが組み合わされて、上位者に伝えられるべき著作権作品の更新された状態を反映する。
ダミー演算子〔丸囲みの+〕およびその逆演算子〔丸囲みの-〕が定義され、著作権作品の変更状態またはバージョンは、次のように表現されうる。
仲介著者によって提出された著作権作品の更新バージョンは、次のように表現される。
ここで、受領されたコンテンツと対応する編集文書の諸ペアにわたる和が、上位著者の下位者全員を考慮に入れる。この文書の更新バージョンが、前述したその上位著者の「寄与」である(たとえば、レベル3の図18Aにおける寄与D-C0、D-D0、D-E0、D-F0、D-F1がこのカテゴリーにはいる)。
下位著者と同様に、上位著者の寄与の二重ハッシュが、単一ハッシュの署名とともに、オンブロック(オンチェーン)で文書の新しい状態を表現するために使用される。これにより、階層構造における次の上位者は、新しい文書バージョンの受領証明を実行し、必要に応じて変更を加えることができる。
上位著者は、その寄与を権限階層構造におけるその上位者に伝えることが期待されている。必ずしも必ずしも必要ではないかもしれないが、上位著者が各下位者のオリジナル・コンテンツをも上に伝えることを期待することは合理的である。それにより、階層構造における次の著者は、著作権作品が階層構造を正しく上って伝達されてきたことを独立して検証することができる。
仲介著者が提供すべき最終的なデータは、要約ハッシュである。これは、著作権作品の制作において仲介著者が自分の関与を含める点までの分枝の全履歴を提供するものである。要約ハッシュは、一般的なハッシュ・ツリー1820を参照することによって理解できる。
要約ハッシュ
すべての著者の寄与がハッシュ・ツリーのリーフ・ノードとして表現されていることを想起されたい。これは、著者が文書にコンテンツを追加するときはいつでも、その文書の履歴を反映する必要もあることを意味する。この履歴は、上位著者のきょうだいであるハッシュ・ツリーの内部ノード(単数または複数)に対応する。なお、下位著者は、定義により、文書履歴をもつことは期待されない。
簡単に言うと、ハッシュ・ツリーの中でリーフ・ノード(白丸)として表現された上位著者がいるところでは常に、少なくとも1つの非リーフ・ノード(黒丸)がきょうだいとしてもつことになる。これは、上位著者が一般化ハッシュ・ツリーにおけるその非リーフ・ノードきょうだいのそれぞれに対応するハッシュ値を提供すべきであることを意味する。
たとえば、ノードN
0,0,0,0およびN
0,0,0,1と、一般化ハッシュ・ツリー1820を考える。ここで、N
0,0,0,1は、上位著者を、ツリー内のリーフ・ノードとして表す。この著者は1つのきょうだいノード、すなわちN
0,0,0,0をもち、ハッシュ値は次のように与えられる:
したがって、上位著者は、著作権作品文書の形成への自分の関与を表すトランザクションに、このハッシュ値N
0,0,0,0を含めるべきである。
上位著者に関連する要約ハッシュを使用することで、上位著者は、ハッシュ・ツリーを上にたどるのに必要なすべての情報を提供することが保証される。これは、マークル存在証明を提供するために不可欠である。
単一の上位著者が多くの非リーフきょうだいノードをもつことがありうるので、ハッシュ・ツリーの複数の接続分岐に対応する複数の要約ハッシュを提供する必要があることがありうることに注意されたい。
エグゼクティブ著者
エグゼクティブ(ルート)著者は、権限階層構造の最上位にいる著者であり、つまり、直接の上位者をもたない(たとえば、EIC C-G0)。エグゼクティブ著者の鍵となる特徴は、下位者からコンテンツを受け取ること、既存のコンテンツを編集する権限をもつこと、オリジナル・コンテンツを追加し、出版前などに著作権作品を承認する最終的な権限をもつことである。
また、ルート著者が、著作権作品の最終バージョンを、著作権機関または知的財産を取り扱う同様の法的権威、たとえば弁理士や公証人に送信することを受け持つ可能性も高い。
エグゼクティブ著者は、少なくともその直接の下位者の寄与に対するアクセスをもつが、現実には、エグゼクティブ著者は、権限階層構造全体について、すべての下位著者および上位著者のオリジナル・コンテンツにアクセスできることが期待される。エグゼクティブ著者に関連するデータは、上位著者のものと同様であるが、エグゼクティブ著者は、未完成バージョンではなく、最終バージョンの著作権作品を提供し、署名する。
表5:エグゼクティブ著者に関連するデータ
新聞社のEIC C-G0がスポーツ・セクションと金融セクションの両方をまとめ、サインオフすることを受け持つのと同様に、ほとんどの場合、エグゼクティブ著者は接続分枝を結合することを受け持つ。このため、上の表に示されるように、エグゼクティブ著者は複数の要約ハッシュを提供しなければならない。
また、エグゼクティブ著者の寄与は、文書の最終バージョンであり、いずれも数学的な表記D0(図18B~図19Bの参照符号D)で示されることを注意しておくべきである。しかしながら、これはハッシュ・ツリーのルートではない。ハッシュ・ツリー自体のルートは、やはり、この最終的な文書の二重ハッシュを、m=1レベルのすべての要約ハッシュと連結することによって、得られる。
たとえば、著作権割り当てハッシュ・ツリー図12では、単にノードN
0のハッシュ値であるツリーのルート・ハッシュH
0は、ちょうど次のように与えられる。
ここで、文書D
0の最終バージョンは、ハッシュ・ツリー自体のインデックス付け規則に従って、D
0,2と書かれている。
最後に、上位著者の場合と同様に、所与の権限階層構造について、複数のエグゼクティブ著者(たとえば、EICではなく理事会)をもつことが可能であることに留意すべきである。この場合、すべてのエグゼクティブ著者が著作権作品の同じ最終バージョンを提供することにおいて一貫していることが合理的である。
技法
次のセクションは、図19Aおよび19Bを参照して、上述した一般化ハッシュ・ツリー構造1820を実装するための方法の説明を拡張する。この実装で利用される概念および技法は、ここでさらに詳しく述べる。
二重ハッシュ
前述したように、それぞれの寄与する著者についてのオリジナル・コンテンツ・データを二重ハッシュすることH2(D)が有利でありうる。これは、データの受領者、すなわち、著者の直接の上位者が、Dそのものを明かすことなく、H2(D)の原像であるその単一ハッシュH(D)を提供することによって、Dを受け取ったことを証明できるからである。
これは、ブロックチェーン上で最終的な著作権作品の構成要素を開示するときに特に望ましい。なぜなら、H2(D)の値は、後にDの存在を証明するためにトランザクションに入れられることができ、上位者は、値H(D)をトランザクションに含めることによって、その文書が自分の所まで上がってきたことを実証できるからである。どちらのトランザクションにおいても、機微な著作権素材は明かされない。
上位者によって明かされるハッシュ値H(D)(一般に、図中のH-xxの形の参照符号によって示される)は、本明細書では、受領証明と称される。
以下に説明するように、著作権作品の構成要素の二重ハッシュ値は、その構成要素のための事実上一意的な識別子として使用できる。これにより、著作権のある作品の構成要素がどのように配布され、ライセンスされるかにおける高い粒度が提供される。これは、化器の使用事例(デジタル・コンテンツのストリーミング)に示される。
ハッシュ・パズル・ロック・スクリプト
ハッシュ・パズルは、Scriptにおいてロック・スクリプトとして書くことができる。
[ハッシュ・パズルH(X)]=OP_HASH160 H(X) OP_EQUALVERIFY
これは、入力Xを与えられる場合にのみ、解くことができ、ロック解除されることができる。受領証明を実施するために、ハッシュ・パズルの修正は、ソルバーに、二重ハッシュの直前の原像を明かすことを強制する。受領証明は、Scriptにおいて次のように書くことができる。
[受領証明D1,…,Dn]=[ハッシュ・パズルH2(D1)]…[ハッシュ・パズルH2(Dn)]
=OP_HASH160 H2(D1) OP_EQUALVERIFY … OP_HASH160 H2(Dn) OP_EQUALVERIFY
これは、すべてのデータD1,…,Dnを提供することによってのみ解くことができる。このロック・スクリプト条件は、ブロックチェーン上に著作権割り当てハッシュ・ツリーを実装し、記録するときに使用できる。
理解されるように、OP_HASH160は、適切なハッシュ関数の一例に過ぎない。一般に、任意の暗号学的に安全なハッシュ関数が使用できる(別の例はOP_SHA256)。
裁量署名の使用
上記のように、裁量署名は、ブロックチェーン・コンセンサス・アルゴリズムによって使用されない署名である。UTXOモデルでは、スクリプトにおけるOP_CHECKSIG演算への入力として消費されるのは署名ではない。
裁量署名は、σ(P,m)として示され、OP_CHECKSIGによって消費される非裁量署名はSig(P,m)で示され、ここで、Pは署名者の公開鍵であり、mは署名されるメッセージ(トランザクションの一部)である。非裁量署名については、mは常にトランザクションであり、一方、裁量署名については、mは任意のメッセージでありうる。
裁量署名は、著者が自分の作品の使用に同意するための二次的な手段として使用できる。たとえば、著者は、上位者によるコンテンツの使用に同意するトランザクションの一部としての署名Sig(P,Tx)を与えることに加えて、自分の寄与をσ(P,H(D))として直接証明することができる。
裁量署名は、任意のデジタル署名タイプでありうるが、非裁量署名は(それがブロックチェーン・プロトコルによって義務付けられていると想定すると)必然的にECDSA署名でなければならないことに留意されたい。より一般には、非裁量署名は、どんなものにせよ適用されるブロックチェーン・プロトコルに従って、適用されなければならない。一方、裁量署名は、ブロックチェーン・プロトコルとは独立に適用することができる(唯一の要件は、トランザクションを無効にしない仕方で含められることである)。
通信チャネル
データの異なる構成要素の格納の仕方と転送の仕方の区別がある。区別は、トランザクションの一部としてオンブロックで転送されるデータと、何らかの他の通信チャネル、好ましくは安全な通信チャネル(A「サイドチャネル」)を介してオフブロックで転送されるデータとの間に引かれる。
これは、以下の事情のため、ブロックチェーン上に著作権割り当てハッシュ・ツリーを格納するために重要である。
非公開-もし、ハッシュ・ツリーが、発明を公けに詳述するのが望ましくなる前に、たとえば特許出願前に、生成される場合、生データ自体ではなく、データのハッシュ値のみを記憶することが賢明である。受領証明-生データはオフブロックで、たとえば上位者に送ることができ、データの二重ハッシュに関するハッシュ・パズルが、データが上位者によって受領されたことを証明するためにオンブロックで使用されることができる。オンブロックではデータの単一ハッシュしか明かさない(1参照)。
図23および図24は、オフブロックおよびオンブロックでデータを送信するプロセスが、企業フレームワークの権利の所望される階層構造または他の外部の階層構造内で、どのように並行して生起するかを示す。
ここで、オフブロックで保持される生データはD値で表され、そのハッシュと二重ハッシュがオンブロックに格納される。ここで示した他のオンブロック・データの意味は、先に説明した。
図23は、権限階層構造の分枝についての主要なデータフローを示す。ここで、P0はエグゼクティブ著者を表し、P0,0は上位著者であり、P0,0,0、P0,0,1はいずれも下位著者である。
図24は、別の権限階層構造分枝についての主要なデータフローを示す。ここで、P0はエグゼクティブ著者を表し、P0,1は上位著者であり、P0,1,0、P0,1,1はいずれも下位著者である。
ブロックチェーンを用いた実装
ブロックチェーン上で著作権割り当てハッシュ・ツリーを実装するために、ノード(ハッシュ値)は、HoAによって決定されるような、ハッシュ・ツリー自体の構造および著作権作品を作成するための操作の順序の両方を反映するようにトランザクション152に格納される。
ブロックチェーン150内のデジタル資産の所有権を支配する既存の公開鍵インフラストラクチャーは、権限チェーンを表すために使用され、トランザクションの構造は、ハッシュ・ツリーのノード間の接続(方向性エッジ)を表すために使用される。ブロックチェーン150の特性のため、これは、ハッシュ・ツリー内でエンコードされた操作の順序が、公開台帳上で変更不能な仕方でタイムスタンプ付けされることを許容する一般化ハッシュ・ツリーを具現する手段となる。
上述の実装では、トランザクション152がハッシュ・ツリーのエッジを表すために使用される。これは、トランザクションが、親ノードを生成するために、一組のきょうだいを連結してハッシュするプロセスを直接表すことを意味する。
ハッシュ・ツリー構造のトランザクションの集合{Tx*,Tx0,Tx0,0,Tx0,0,0,Tx0,1,Tx0,1,0}へのマッピングは、図25に概略的に示される。
図25は、ノード間のエッジを表すブロックチェーン・トランザクション1920の集合にマッピングされた著作権割り当てツリーを示す。これは、図19Aおよび19Bに示されているトランザクションの集合と同じであるが、図25は、トランザクションを表すために数学的表記を使用する(下記でも使用される)。この数学的表記は、図19Aおよび19Bで使用される参照符号に次のようにマップされる:
・Tx0,0,0-TX-A
・Tx0,1,0-TX-B
・Tx0,0-TX-C
・Tx0,1-TX-D
・Tx0,0-TX-EF
・Tx0-TX-G
・Tx*-TX*
各トランザクションは、2つの異なるツリー・レベルからのハッシュ・ツリー・ノードを含むことに注意されたい。任意の所与のトランザクションにおいて、図19Aおよび19Bの例で上述されたように、「低いほう」エッジはトランザクション入力の一部であり、「高いほう」のエッジは出力の一部である。
ハッシュ・ツリー・ノードのブロックチェーン・トランザクションへのマッピングは、トランザクション入力は著者からの非裁量署名を含み、出力は著者が作成したコンテンツの存在証明を表すという慣例を使用する。また、これらの出力は、著者の直接の上位者(単数または複数)のみがUTXOをロック解除し、ハッシュ・ツリーへの追加を続けることができるようにロックされる。
ここに示したトランザクションと新聞HoAとの関係を図26に示す。
図26は、権限の階層構造(HoA)と対応するトランザクションのチェーンとの間のマッピングを示す。
任意の所与のレベルの著者は、出力に、自らの裁量署名と、自分のコンテンツの二重ハッシュとを含める。こうして、効果的に、自らのオリジナルの作品を階層構造の上に伝え、上位者によるその利用に同意する。
ここでの意図は、ブロックチェーン150上で組織権限階層構造を表現し、著作権作品の各構成要素の表現を一意的なハッシュ値として記憶することである。
この実装のために、トランザクションは事実上、ハッシュ・ツリーの分枝の詳細を提供する。分枝は、類似のエッジの集合として定義される。4つの子をもつ親ノードがある場合、これら4つのエッジの集まりが分枝と呼ばれる。これらのエッジは、それぞれ4つの子をすべて連結し、その結果をハッシュすることで作成されるので、同様であると考えられることを想起されたい。
たとえば、トランザクションTx0,0,0を考える。このトランザクションは、分枝のドキュメンテーションであり、上位著者P0,0,0は出力の宛先(受信者)によって表され、下位著者P0,0,0,0,…,P0,0,0,4は入力署名によって表される。受信者の上位著者P0,0,0からの署名は、トランザクションTx0,0,0の出力を使用するために必要とされる。
このパラダイムは、最終的なトランザクションTx*、すなわち、エグゼクティブ著者と著作権機関との間のトランザクションを除いて、すべてのトランザクションに共通である。このトランザクションは、出力が、権利の階層構造にとって外部である著作権機関、たとえばIP登録簿または弁理士によってロック解除されることができるという点で異なる。
この最終トランザクションは、著作権作品の最終バージョンDとコンテンツ割り当てハッシュ・ツリーのルート・ハッシュH0の両方のハッシュされた表現を含んでいる。
著作権のある新聞の場合、ルート著者P0は1人だけである。新聞の最終版は、データD0,2によって与えられる。これが、ルート著者を表すリーフ・ノードN0,2に格納されているデータだからである(詳細は4.1.3を参照)。
エグゼクティブ著者に対応するノードN0,2のハッシュ値H0,2=H2(D0,2)と、ルート・ハッシュH0に対応するノードN0とを区別する必要があることを強調しておく。
トランザクションおよびデータ
ここで、ハッシュ・ツリー1820を具現するトランザクション1920の可能な形態について説明する。これらのトランザクションは、新聞の階層構造のための著作権割り当てハッシュ・ツリー1820を完全に表す。
ハッシュ・ツリーは、本明細書に記載される技法のいくつかを使用して実装される。これは単に、ブロックチェーン上に格納された知的財産の適用にこれらの技法がどのように役立つかを例証するものであるが、この方法はこれらの技法のみに限定されるものではないことに留意すべきである。
下位著者から上位著者
5人の下位著者(スポーツ・ジャーナリスト)から上位著者(スポーツ・エディター)へのトランザクションを考える。これを図12に示される。
このトランザクションは、以下のトランザクション1として示され、それぞれの下位著者からの署名を別々に提供するために1つずつある5つの入力と、2つの出力とを含む。
第1の出力は、(i)各リーフ著者の寄与の二重ハッシュと、(ii)各著者の寄与の単一ハッシュに対する裁量署名とを含む、使用不能なOP_RETURN出力である。この二重ハッシュは、トランザクションの支払い先である上位著者が、後に(根底にある寄与を明かすことなく、単一のハッシュの形で)受領証明を提供することを可能にする。
第2の出力は、2つのロック・スクリプト成分を含む、使用可能なUTXOである。第1のものは、単純な署名チェック・スクリプトであり、これは、上位著者に属する公開鍵からの署名が提供されたときに、ロック解除される。
第2の部分は、セクション4.1.4節に示されているような、受領証明スクリプトである。これは、各下位著者の寄与のハッシュが提供されたときに、ロック解除され、前記ハッシュは、関連する上位著者にオフブロックで渡される。
トランザクション1: OP_RETURNを使用した下位から上位へのトランザクションの例。これは図26からのTxID
0,0,0に対応する。
この同じトランザクションを、代わりにマルチ署名UTXOを使って作成することも可能である。ここで、OP_RETURN出力は、次のロック・スクリプト・コンポーネントに置き換えられる。
このロック・スクリプトは、使用不能なOP_RETURN出力ではなく、下位著者の寄与を格納するために使用される。このロック・スクリプトは、公開鍵P
0,0,0を使用して上位著者の署名を提供することによって解かれ、よって、前の図の署名チェックと同じように機能する。下位著者から上位著者へのトランザクションの代替形式が、下記でトランザクション2として示される。
トランザクション2: マルチ署名ロック・スクリプトを使用した下位から上位へのトランザクションの例。これは図16からのTxID
0,0,0に対応する。
OP_RETURNを使用することにより、「現在の」著者のハッシュ値が直接追加されることができる。マルチ署名を使用することで、ハッシュ値はスクリプト内に隠され、スクリプトはハッシュされ、よって、ツリーにおけるすぐ上の次のトランザクションにおいて、コンテンツ・データのコミット済みハッシュのみが明かされる。
以下の記述はこの実装における残りのトランザクションのためにマルチ署名形式を使い続けるが、それでもOP_RETURNは有効な方法である。より一般には、問題のデータは、トランザクションを無効にしない任意の仕方でトランザクションに含めることができる(好ましくは、署名された出力に含める)。
上位著者から上位著者
上位著者P0,0,0から、より高いランクの上位著者P0,0へのトランザクションTxID0,0を考える。どちらの役者も上位著者であり、どちらも著作権割り当てハッシュ・ツリー1820において、レベルは異なるが、リーフ・ノードによって表される。このトランザクションは、原則として、今述べた下位から上位へのトランザクションと同様である。ここでの主な違いは、5人の下位著者が1人の上位著者に支払った以前の状況ではなく、1人の役者が他の1人の役者へのトランザクションを作成することである。
この差は、入力の数(今やたった1つ)と出力スクリプトに格納されているデータ要素の数に反映される。トランザクション自体は、下記のトランザクション3として示される。
トランザクション3:マルチ署名ロック・スクリプトを使用した上位から上位へのトランザクションの例。これは、図prev 16からのTxID
0,0に対応する。
入力スクリプトは、より低いランクの上位著者P0,0,0に送られた前のTxID0,0,0のロック負担を満たしている。これは、受領証明使用条件を満たすために必要とされる5つのハッシュされたデータ要素と、マルチ署名ロック条件を満たすために必要とされる著者の署名Sig(P0,0,0,Tx)を含む。
出力スクリプトは、同じタイプのロック条件を含む;1つのマルチ署名スクリプトと、1つの受領証明スクリプトである。ここでの主な違いは、マルチ署名スクリプトは、この単独の寄与の二重ハッシュと、より低いランクの上位著者の裁量署名のみを含んでいることである。しかしながら、このロック・スクリプトは、要約ハッシュH
0,0,0,0も含む。これは、すべての下位編集者の以前の寄与の連結のハッシュである。このスクリプトは次のように書かれる:
このスクリプトは、P
0,0の所有者である、より高いランクの上位編集者からの署名を与えられたときにロック解除できる。また、受領証明は、より高いランクの上位著者に、より低いランクの著者の寄与のハッシュH(D
0,0,0,1)を提供するよう求めるだけであることに注意されたい。
上位著者からエグゼクティブ著者
上位スポーツ編集者P0,0と両方の上位金融編集者P0,1,P0,2から送られたトランザクションTxID0が主任編集者(EIC)P0に支払われることを考える。上位編集者はすべて上位著者であり、EICは唯一のエグゼクティブ著者であることを想起されたい。ここでもまた、これらの役者はすべて、著作権割り当てハッシュ・ツリーのリーフ・ノードによって表される。
このトランザクションは、下記でトランザクション4として示され、ハッシュ・ツリーには同じレベルにおいて上位著者が3人いるから3つの入力をもち、エグゼクティブ著者EICが1人しかないから1つの出力をもつ。
入力スクリプトは、先に示した上位から上位のトランザクションと同じ形式である。しかしながら、両方の金融エディターは同じ下位金融エディターをもつので、両方とも、下位エディターの寄与のハッシュ<H(D
3
0,2,1,2D
0,1,0,1)>をも入力として提供している。
トランザクション4:マルチ署名ロック・スクリプトを使用した上位からエグゼクティブへのトランザクションの例。これは図16からのTxID
0に対応する。
ここで使用される出力スクリプトは、EICによって提供される上位著者の寄与の受領証明と、P
0を使ったEICの署名を必要とする。下記に示されるマルチ署名スクリプトは、ツリーのこのレベルについての両方の要約ハッシュH
0,0,0およびH
0,1,0をも含む。
エグゼクティブ著者から著作権機関
EIC P0から著作権機関(copyright authority、CA)P*に送られるトランザクションTxID*を考える。このトランザクションは、エグゼクティブ著者によって作成され、下記を含むという特別な特性をもつ。
(i)著作権作品Dの最終バージョンまたは状態の一意的な表現H2(D)
(ii)著作権割り当てツリーについてのルート・ハッシュH0=N0。
下記でトランザクション5として示されるこのトランザクションは、また、権利の階層構造における最高権威者が、最終状態Dをオフブロックで送信することによりこれを第三者CAに開示することに同意することを示すために、エグゼクティブ著者(複数可)からの入力署名をも含む。
トランザクション5:エグゼクティブから著作権機関へのトランザクションの例。これは図16からのTxID
0に対応する。
このトランザクションは、1つの入力と1つの出力を含む。入力は、著作権作品に対する上位著者の寄与の単一ハッシュを受領証明として含み、また、EICの公開鍵P0からの必要な署名を含む。
このトランザクションの出力は、2つのロック成分をもつ。1つは単純なハッシュ・パズルであり、これは、著作権機関にH0の値(図19Bの参照符号H-RHで示される)を提供することを要求する。H0の値は、ハッシュ・ツリーのルートの単純な宣言と、著作権機関が最終的な著作権作品の正しい、期待されるバージョンと、その対応するハッシュ・ツリー表現とを受け取ったことの証明の両方として機能する。これは、次のように書かれる。
[ハッシュ・パズルH(H0)]=OP_HASH160 H2(H0) OP_EQUALVERIFY
OP_HASH160は例解用の例として使用されており、有望なハッシュ・パズルを構築するために使用されうる多くのハッシュ関数の1つに過ぎないことが強調される。ハッシュ・パズルという用語は、特定のハッシュ関数を含意するものではなく、ハッシュ・パズルを構築するためには、必要な暗号学的特性をもつ任意のハッシュ関数が使用できる。
第2の成分は、マルチ署名スクリプトであり、これは、EICの寄与、その寄与の署名、両方の関連する要約ハッシュを含み、次のように書ける。
その後のトランザクションにおいて著作権機関がこれらのロック条件を満たすと、ブロックチェーン上で著作権割り当てツリーを実装するプロセスは完了する。
まとめ
まとめると、上述の実施形態は、下記を提供する:
・著作権作品を格納することができ、一方では権利の所有を表す権限の階層構造をも反映する、一般化ハッシュ・ツリー;
・一般化ハッシュ・ツリーを公開ブロックチェーン上に格納するためのブロックチェーン・ベースの実装。
これらの2つの側面は、本稿の導入部で特定されたIPに対する権利の割り当ておよびその後の開示の問題に取り組むために連携して使用される。
上記のシステムは、コンテンツ管理システムをサポートする多様な、価値のある機能を生成するために、ブロックチェーンおよび関連する暗号学的プリミティブの特性を利用する。これは特に、コンテンツの共同制作における所有権と時系列を文書化することに関連するためである。WPにおいて概説されているシステムを通じて、以下が可能にされる。
一意的なコンテンツ識別子H2(D):
任意のコンテンツの一意的な識別子を生成する。この一意的な識別子は、H2(Content)である。コンテンツのこの識別子は、関心のあるコンテンツを取り出すまたは参照する必要のある外部システムにおいて利用できる。(例として、書籍について同様の機能を提供するISBN識別子を考えられたい)。
「作業証明(Proof of Work)」と「時の証明(Proof of When)」:
この文脈では、これは、役者〔アクター〕がペア
[H2(Content),σ(H(Content))]
を含むブロックチェーン上の既存のトランザクションを参照することによって、該役者が特定のコンテンツを作成したことを証明できることをいう。特定のブロック内の(変更不能な)ブロックチェーン上のこのトランザクションは、コンテンツ自体が少なくとも「特定の時刻」より作成されたことが証明可能であることを示す。二重ハッシュの原像の署名は、秘密鍵の所有者がその時点またはそれ以前にそのコンテンツを知っていたことを示す。
含有証明(Proof of Inclusion):
ハッシュ・ツリーへの概念的なマッピングと、ブロックチェーン・トランザクションでの適用可能なハッシュの格納とによるシステムの土台は、利害関係者が、コンテンツの最終バージョンにおいて特定のコンテンツの包含を証明できるようにする(H2(Content)によって表される)。これは、最終バージョンが複数の寄与コンテンツの機能であり、異なるコンテンツが複数の参加者によって作成されうる場合である。
コンテンツ、データ、およびプロセスを承認するために適切な参加者がデジタル署名を提供するによって実施される、ブロックチェーン上のこのハッシュ・ツリー・データの格納は、包含の証明を特に強力にし、ブロックチェーンの透明性および変更不能性を与え、反論に関連するのでデジタル署名の特性を与える。
移転の証明(Proof of Transfer):
エッジとしてのトランザクション(transaction-as-edge)の入力に署名することにより、これは、その親エンティティに、子が作成したコンテンツを編集または利用する許可を与えるエンティティ(子)のはたらきをする。トランザクション入力のこの署名は、子エンティティが、渡されているコンテンツ(その識別子H2(Content)によって表される)が正しいことに同意するという表現のはたらきもする。
受領証明(Proof of Receipt):
エンティティがエッジとしてのトランザクションの出力を消費する場合(これは、該エンティティが自分の署名と子の出力のハッシュを提供することを含む)、これは、そのエンティティがその子ノードから生のコンテンツを受け取ったこと、およびその生のコンテンツが、子ノードがその生のコンテンツがそうであるはずだと言っているものと整合する(完璧に一致する)ことを認証する(certify)。
時間順序の証明(Proof of Chronology):
エッジとしてのトランザクションに子ノードから親ノードへのコンテンツの移転を表現させることによる。これは、どの利害関係者も、リーフ・ノードから出発して階層構造を通じて最終的な(ルート・ノード)出力への漸進的な合成を追跡することができるため、参加者寄与の時間順序的な文書化を実施する。親ノードは、子ノードからのトランザクションの出力を消費することに留意されたい。これは、寄与のシーケンスを示す。
IPの開示:
IPの開示は、公開ブロックチェーン150を使用して達成される。公開ブロックチェーン150は、イベントを記録するための安全なタイムスタンプ・サーバーとして作用するので、著作権割り当てハッシュ・ツリーにおけるハッシュ値の公開は、所与のタイムスタンプにおける発明の、実施可能にしない表現(non-enabling representation)として作用する。公的な作業証明(PoW)ブロックチェーンの変更不能な特性は、ハッシュ関数の不可逆性と組み合わせて、著作権作品(またはその構成要素)のハッシュ値を置くことが、新規な作品の着想およびその後の発展の瞬間をタイムスタンプする安全な方法であることを意味する。後刻、完全な作品は、他の場所で公開されることができ(たとえば、特許を出願することによって)、そのハッシュが、タイムスタンプ付けされたオンチェーン値に対して検証されることができる。
よって、この方法は、発明の概念に対する優先権または資格に関する紛争の解決を許容し、IP紛争をめぐる法的手続においていくつかの仕方で使用できる。
さらに、第三者のサービスがこれらの方法を大規模に実装する場合、公開のブロックチェーンが、汎用のIP登録簿として使用されることができる。IP登録簿は、出願時やIP保護の付与時など、法的手続きにおけるタイムスタンプ付けされたイベントを含むことができる。
6. 使用事例:映画のストリーミング
著作権作品の創作を、操作の順序を変更不能な仕方でタイムスタンプ付けするためのブロックチェーンと組み合わされたものを表現するために一般化ハッシュ・ツリー構造を使用することは、多くの異なるタイプの作品の創作に関わるシナリオに適用されうる。そのような例の一つは、映画の創作であり、これは、典型的には、監督、プロデューサー、スクリーンライター、俳優、セットデザイナー、編集者などの多くの当時者が関与する。記述される例は、映画を考えているが、記述は、離散的なセグメントで構成されるデジタル・コンテンツの他の形式に等しく適用される。
映画のための一般化ハッシュ・ツリー
高度に複雑なハッシュ・ツリーを作成して、創作プロセスをその全体において表現することができ、最終的な映画の各要素がどのようにして創作されたかを詳述することができる。
しかしながら、この例については、簡略化されたシナリオが考えられる。映画製作プロセスは、等しい長さの3幕の創作に分割されるとする。各幕は等しい長さの5つのチャンクに分割され、映画全体が合計で15チャンクのビデオデータD1、…、D15を含み、それぞれが関連付けられた二重ハッシュ値H2(Di)をもつ。次に、図15に示されるように、映画は、単純な一般的ハッシュ・ツリーを使用して表現できる。
図15は、15個のデータ・セグメントに分割された、映画に適用される一般化ハッシュ・ツリー構造を示している。
下記のセクション6.3で論じられるように、フィルムの各チャンクに関連付けられた二重ハッシュ値は、一意的なパケットIDとして使用されることができ、各パケットは、フィルム全体についての一意的な識別子としてそのマークル・ルートRMを使用することによって、このハッシュ・ツリーの一部として迅速に検証することができる。この意味で、ルートRMは、製品についての一意的な識別子としてISBNまたはバーコードと同様に作用する。
しかしながら、ルートRMは、RM自身のための信頼されるソースがあれば、フィルムの個々のコンポーネントが簡単に検証されることをも可能にするため、従来のバーコードよりも、一意的な製品識別子としてはるかに価値がある。
さらに、フィルムの各セグメントD1、…、D15を別の、別個の一般化されたハッシュ・サブツリーのルートと関連付けることが可能である。このようにして、各セグメントの個々のコンポーネントは、セクション4で説明した著作権譲渡実装を使用して、ブロックチェーン上で追跡できる。
第1の映画セグメントD1についてのそのような一般化ハッシュ・サブツリーの例が図16に示される。図15と図16の両方において、D1についてのデータ・セグメントは、一貫性のために緑で示されているが、2つのツリー自体は著作権譲渡ハッシュ・ツリーの別々のインスタンスである。
図16は、第1の映画セグメントD1についての一般化ハッシュ・サブツリーを示す。最終的にセグメントD1を生成するために組み合わされるデータは小文字で示されている。
映画のストリーミング
図15に示される種類のハッシュ・ツリーによって表される映画の場合、実際的な用途の一例は、消費者(アリス)が、ストリーミング・サービス・プロバイダー(ボブ)から映画をストリーミングする際に、一般化ハッシュ・ツリーを、強力なデータ完全性チェックとして使用できるというシナリオである。
アリスが映画をストリーミングしたいときには、まずマークル・ルートR
Mを取り出すことができる。このマークル・ルートが、映画ファイルについての、公開の、一意的な識別子として使用される。これに加えて、アリスはまた、15の映画セグメントのそれぞれについて、一意的なパケットID H
2(D
1)、…、H
2(D
15)および関連するマークル経路Γ
1、…、Γ
15も取得するべきである。この情報はすべてブロックチェーン150(セクション4参照)で公に利用可能であり、英国のBBFC(British Board of Film Classification[英国映画等級指定委員会])のような標準団体によって認証されていると想定される[14]。アリスがストリーミングしたいデータ、およびアリスが前もって持っているデータは、以下のテーブル6に示される。
これは、アリスが、ストリーミング・サービス・プロバイダーとしてのボブによって送信されたデータ・パケットが正当なものであるかどうかを、アリス自身が見る必要なく、検証するのに十分な情報を手に入れたことを意味する。もしアリスが、二重ハッシュによって前記パケットIDまたは任意のパケットIDにならないパケットを受信した場合、アリスは、そのデータを誤りとして無視し、閲覧を打ち切ることができる。
秒毎の支払いフレームワークと組み合わされる場合、これはアリスに、ピアツーピア・ベースでコンテンツをストリーミングするきわめてリスクの低い方法を提供するだろう。
セグメント・サイズの粒度が適切であれば、アリスは、視聴やセグメントの前に一意的なパケットIDが常にチェックされることを強制できるので、アリスは、偶発的に見苦しいコンテンツや予期しないコンテンツを見ることがないように保護される。これは、パケットIDのフレーム毎の事前チェックと同じくらい厳密にできる。
映画のバージョン更新
固定された一意的な製品識別情報(マークル・ツリーのルート)をもてることは、しばしば複数の異なるバージョンをもつ映画の創作への応用のために特に有用である。たとえば、映画は、地域の規制に準拠するために、上映される国ごとに、少し修正されなければならないことが多い。
これらの小さな修正は、アリスのような人間のユーザーにとっては区別が難しいかもしれないが、暗号学的ハッシュ関数の高エントロピー特性のため、映画データのハッシュ・ダイジェストでは、常に容易に検出できる。
一意的なパケットIDをもつ15のセグメントを有する、上と同じ映画を考える。すべてのIDは、マークル・ツリー・ルートRMである、映画の一意的な製品識別情報と不可分に結びつけられている。
監督が数年後にこの映画を再検討し、この映画の特別な「ディレクターズカット」版のためのいくつかの軽微な編集上の変更をすることが現実的に可能である。この映画に対する監督の新しい変更の効果が、図17に示されている。
図17は、映画の新しい「ディレクターズカット」バージョンを表す、修正された一般化ハッシュ・ツリーを示している。オリジナルに対するディレクターの変更が、データ・セグメントD16に示されている(赤)。新しい一般化ハッシュ・ツリーは必然的に新しいルートR'M≠RMをもたなければならない。これは、ハッシュ・ツリーのルートを映画全体のための一意的な製品識別子として使用するという慣例を採用することによって、「ディレクターズカット」バージョンがもとのバージョンと容易に区別できることを意味する。
この新しい識別子によって、アリスは、1コマさえ見る前に、自分が映画の期待されるバージョンを見ているかどうかを検証することができる。アリスがディレクターズカットのためのデータ・パケットを受け取っているが、オリジナルの映画の製品IDに対して検証しようとしている場合、最初のセグメントでさえ失敗し、アリスは、代わりにオリジナルのバージョンをボブに求めることができる。
このチェックは、ピアツーピア・ストリーミング・サービスのユーザーが、自国で禁止されている映画のバージョンを不注意にストリーミングしないようにするためのツールとしても利用できる。
上記の実施形態は、単に例として記載されたものであることが理解されるであろう。
より一般的には、以下の陳述のうちの任意の一つまたは複数に従った方法、装置またはプログラムが提供されうる。
陳述1
定義された階層構造におけるそれぞれのレベルを有する寄与者による作品への寄与を、一つまたは複数のブロックチェーン・トランザクションにおいて記録するコンピュータ実装される方法であって、定義された階層構造において、一または複数のより低レベルの寄与者は、より高レベルの寄与者に対して、それぞれ一つまたは複数のより低レベルの寄与を提供し、前記より高レベルの寄与者は、前記一または複数のより低レベルの寄与に応答する、より高レベルの寄与を提供し、当該方法は:
前記より高レベルの寄与者のコンピュータ装置において、より高レベルの寄与者トランザクションを生成または修正して、前記より高レベルの寄与の証拠を与えるステップを含み、生成または修正されたより高レベルの寄与者トランザクションは:
一つまたは複数の入力を含み、該一つまたは複数の入力は:
一または複数のより低レベルの寄与者トランザクションの一つまたは複数の使用可能出力への一つまたは複数のポインタであって、前記一つまたは複数のより低レベルの寄与者トランザクションは前記一つまたは複数のより低レベルの寄与の証拠を与える一つまたは複数のより低レベルの寄与コミットメントを含む、ポインタと;
前記一つまたは複数の使用可能出力の一つまたは複数の署名チャレンジを満足する、前記より高レベルの寄与者の一つまたは複数のトランザクション署名とを含み、
前記より高レベルの寄与者トランザクションが、前記より高レベルの寄与から計算された、より高レベルの寄与コミットメントを含み、前記一つまたは複数のポインタと前記寄与コミットメントが、前記定義された階層構造内の前記より高レベルの寄与者と、前記一または複数のより低レベルの寄与者との間の関係を表し、前記一つまたは複数のトランザクション署名がその関係を証明する、
方法。
「第1および第2のより低レベルの寄与ハッシュを含む一つまたは複数のより低レベルの寄与者トランザクション」という表現は、第1および第2のより低レベルの寄与ハッシュが同じより低レベルの寄与者トランザクションに含まれる場合と、それらが異なるより低レベルの寄与者トランザクションに含まれる場合とを含む。
上述の例では、寄与コミットメントは、寄与ハッシュ(たとえば、それが証拠を与える寄与の単一または二重ハッシュ)の形をとる。より一般的には、寄与コミットメントはハッシュ・ベースであってもなくてもよく、たとえば、寄与コミットメントは、寄与の生データ(たとえば、寄与自体の全部または一部であってもよい)または寄与の証拠となるのに適した他の何らかの処理された形の該寄与のデータを含むことができる。
例示的実施形態が以下に記載される。
陳述2
前記一または複数のより低レベルの寄与者が第1および第2のより低レベルの寄与者を含み、前記一つまたは複数のより低レベルの寄与がそれぞれ前記第1および第2のより低レベルの寄与者の第1および第2のより低レベルの寄与を含み、前記一つまたは複数のより低レベルの寄与コミットメントがそれぞれ前記第1および第2のより低レベルの寄与を証明する第1および第2のより低レベルの寄与コミットメントを含む、陳述1に記載の方法。
陳述3
陳述1または2に記載の方法であって、前記より高レベルの寄与者トランザクションは、前記一つまたは複数のより低レベルの寄与の一つまたは複数の受領証明を含む、方法。
陳述4
前記一つまたは複数の受領証明が:前記第1のより低レベルの寄与の第1の受領証明、および前記第2のより低レベルの寄与の第2の受領証明を含む、陳述2および3に記載の方法。
陳述5
前記一つまたは複数の受領証明が前記一つまたは複数の入力に含まれており、それぞれ前記一つまたは複数のより低レベルの寄与者トランザクションの前記一つまたは複数の使用可能出力の第1および第2の受領証明チャレンジを満足させる、陳述3または4に記載の方法。
陳述6
前記より高レベル寄与者トランザクションが、前記より高レベルの寄与についての受領証明チャレンジを含む、陳述1ないし5のうちいずれか一項に記載の方法。
陳述7
前記高レベルの寄与者トランザクションが、受信側エンティティのためのトランザクション署名チャレンジを含む、陳述1ないし6のうちいずれか一項に記載の方法。
陳述8
前記受信側エンティティが、前記階層構造におけるさらに高レベルの寄与者であり、前記より高レベルの寄与者が、前記より低レベルの寄与者と前記さらに高レベルの寄与者との間の中間的な寄与者である、陳述7に記載の方法。
陳述9
前記より高レベルの寄与者トランザクションが、前記より高レベルの寄与者の秘密鍵と、前記より高レベルの寄与の証明とに署名機能を適用することによって生成された裁量署名を含み、前記より高レベルの寄与の証明は、前記より高レベルの寄与またはそのハッシュもしくは他の関数であり、前記より高レベルの寄与の証明は、前記より高レベルの寄与者トランザクションに含まれない、陳述1ないし8のうちいずれか一項に記載の方法。
陳述10
前記寄与コミットメントが寄与ハッシュである、陳述1ないし9のうちいずれか一項に記載の方法。
陳述11
前記より高レベルの寄与ハッシュが前記より高レベルの寄与の前記証明のハッシュである、陳述9および10に記載の方法。
陳述12
前記より高レベルの寄与の前記証明が、前記より高レベルの寄与であり、前記より高レベルの寄与ハッシュが、前記より高レベルの寄与の単一のハッシュである、または
前記より高レベルの寄与の前記証明が、前記より高レベルの寄与の単一ハッシュであり、前記より高レベルの寄与ハッシュが、前記より高レベルの寄与の二重のハッシュである、
陳述11に記載の方法。
「二重ハッシュ」という用語は、必ずしも同じハッシュ関数が2回適用されることを意味しない。一般に、何らかのデータの二重ハッシュは、数学的にH1(H2(D))のように表すことができる。ここで、H1およびH2は、同じハッシュ関数であってもよく(H1=H2)、または異なるハッシュ関数であってもよい(H1≠H2)。
陳述13
前記受領証明チャレンジ、前記受信側エンティティのための前記トランザクション署名チャレンジ、および/または前記裁量署名が、前記より高いレベルの寄与者トランザクションの一つまたは複数の出力に含まれる、陳述6ないし12のうちいずれか一項に記載の方法。
陳述14
陳述6、7および9を引用する場合の陳述13の方法であって、少なくとも前記受領証明チャレンジおよび前記トランザクション署名チャレンジは、前記裁量署名とは独立して消費可能な前記一つまたは複数の出力のうちのある出力に含まれている、方法。
陳述15
前記一つまたは複数の出力が:
前記第1のより低レベルの寄与の単一ハッシュまたは多重ハッシュと、前記第2のより低レベルの寄与の単一ハッシュまたは多重ハッシュとを含む連結したストリングをハッシュすることによって計算される要約ハッシュを含み、前記使用可能出力は、前記要約ハッシュとは独立して消費可能である、
陳述1ないし14のうちいずれか一項に記載の方法。
陳述16
定義された階層構造におけるそれぞれのレベルを有する寄与者による作品への寄与を、一つまたは複数のブロックチェーン・トランザクションにおいて記録するコンピュータ実装される方法であって、定義された階層構造において、第1および第2のより低レベルの寄与者は中間レベルの寄与者に対して、それぞれ第1および第2のより低レベルの寄与を提供し、前記中間レベルの寄与者は、前記第1および第2のより低レベルの寄与に応答する、中間レベルの寄与を、より高レベルの寄与者に対して提供し、当該方法は:
前記中間レベルの寄与者のコンピュータ装置において、ブロックチェーン・トランザクションを生成または修正するステップを含み、生成または修正されたブロックチェーン・トランザクションは:
前記第1のより低レベルの寄与の第1の受領証明、
前記第2のより低レベルの寄与の第2の受領証明、および
前記中間レベルの寄与者のトランザクション署名
を含む一つまたは複数の入力と;
前記中間レベルの寄与についての受領証明チャレンジ、
前記より高レベルの寄与者のためのトランザクション署名チャレンジ、および
裁量署名
を含む一つまたは複数の出力とを含み、
前記裁量署名は、前記中間レベルの寄与者の秘密鍵と、前記中間レベルの寄与またはそのハッシュとに署名関数を適用することによって生成され;
少なくとも、前記受領証明チャレンジおよび前記トランザクション署名チャレンジは、前記裁量署名とは独立して使用可能な前記一つまたは複数の出力のうちのある出力に含まれ、
方法。
陳述17
前記一つまたは複数の出力が:
前記第1のより低レベルの寄与の単一ハッシュまたは多重ハッシュと、前記第2のより低レベルの寄与の単一ハッシュまたは多重ハッシュとを含む連結されたストリングをハッシュすることによって計算される要約ハッシュを含み、前記使用可能な出力は、前記要約ハッシュとは独立して使用可能である、
陳述16に記載の方法。
陳述18
陳述16または17に記載の方法であって、第2の中間レベルの寄与者が第2の中間レベルの寄与を前記より高レベルの寄与者に提供し、
前記ブロックチェーン・トランザクションの前記一つまたは複数の入力は、さらに:
第3のより低レベルの寄与の第3の受領証明、
前記第2の中間レベルの寄与者のトランザクション署名を含み、
前記一つまたは複数の出力は、さらに:
前記第2の中間レベルの寄与についての受領証明チャレンジ、および
第2の裁量署名を含み、
少なくとも前記第2の中間レベルの寄与についての前記チャレンジは、前記一つまたは複数の出力のうちの前記使用可能な出力または前記一つまたは複数の出力のうちの別の使用可能な出力に含まれる;
前記第2の裁量署名は、署名関数を前記第2の中間レベルの寄与の単一ハッシュまたは多重ハッシュと、前記秘密鍵または前記中間レベルの寄与者の別の秘密鍵とに適用することによって生成される、
方法。
陳述19
前記一つまたは複数の出力が第2の要約ハッシュを含み、前記第2の要約ハッシュが原像をハッシュすることによって計算され、前記原像が前記第3のより低レベルの寄与の単一ハッシュまたは多重ハッシュを含む、陳述18に記載の方法。
陳述20
前記ブロックチェーン・トランザクションの前記一つまたは複数の入力がさらに:
第4のより低レベルの寄与の第4の受領証明を含み、
前記第2の要約ハッシュを計算するためにハッシュされた前記原像は、前記第3のより低レベルの寄与の前記単一ハッシュまたは多重ハッシュと、前記第4のより低レベルの寄与の単一ハッシュまたは多重ハッシュとを含む第2の連結されたストリングの形である、
陳述19に記載の方法。
陳述21
前記裁量署名は、前記ブロックチェーン・トランザクションの一つまたは複数の使用可能でない出力に含まれる、陳述1ないし20のうちいずれか一項に記載の方法。
陳述22
陳述17を引用する場合の陳述21に記載の方法であって、前記一つまたは複数の使用可能でない出力が前記要約ハッシュを含む、方法。
陳述23
前記一つまたは複数の使用可能でない出力が、前記第1のより低レベルの寄与の単一ハッシュまたは複数ハッシュ、および前記第2のより低レベルの寄与の単一ハッシュまたは多重ハッシュをも含む、陳述21または22に記載の方法。
陳述24
前記裁量署名は、前記使用可能出力に含まれ、前記トランザクション署名チャレンジは、マルチ署名チェック・オペコードの関数オペランドであり、前記裁量署名は、前記マルチ署名チェック・オペコードのダミー・オペランドである、陳述16ないし20のうちいずれか一項に記載の方法。
陳述25
陳述17を引用する場合の陳述24に記載の方法であって、前記要約ハッシュは、前記マルチ署名チェック・オペコードのダミー・オペランドとして前記使用可能出力に含まれる、方法。
陳述26
前記第1のより低レベルの寄与の単一ハッシュまたは多重ハッシュ、および前記第2のより低レベルの寄与の単一ハッシュまたは多重ハッシュも、前記マルチ署名チェック・オペコードのダミー・オペランドとして含まれる、陳述24または25に記載の方法。
陳述27
前記ブロックチェーン・トランザクションをブロックチェーン・ネットワークのノードに送信して、該ノードにおいて、ブロックチェーン内に記録するための処理がされるようにするステップを含む、陳述1ないし26のうちいずれかの一項に記載の方法。
陳述28
前記ブロックチェーン・トランザクションを処理のためにオフチェーン・システムに送信するステップを含む、陳述1ないし26のうちいずれか一項に記載の方法。
陳述29
前記より高レベルの寄与者が、前記使用可能出力を使用するために第2のブロックチェーン・トランザクションを生成し、前記第2のブロックチェーン・トランザクションが:
前記中間レベルの寄与の受領証明、
前記より高レベルの寄与者のトランザクション署名
を含む一つまたは複数の入力と;
前記より高レベルの寄与者のより高レベルの寄与についてのさらなる受領証明チャレンジ、
前記より高レベルの寄与の受信者のためのトランザクション署名チャレンジ、
さらなる裁量的署名
を含む一つまたは複数の出力とを含み、
前記さらなる裁量的署名は、前記より高レベルの寄与者の秘密鍵と、前記より高レベルの寄与の単一ハッシュまたは多重ハッシュと署名関数を適用することによって生成される、
陳述1ないし28のうちいずれか一項に記載の方法。
陳述30
前記第2のブロックチェーン・トランザクションの前記一つまたは複数の出力は、さらなる連結されたストリングをハッシュすることによって計算されるさらなる要約ハッシュを含み、前記さらなる連結されたストリングは、前記要約ハッシュと、前記より高レベルの寄与者の前記寄与の単一ハッシュまたは多重ハッシュとを含む、陳述29に記載の方法。
陳述31
陳述29または30に記載の方法であって、前記より高レベルの寄与は、前記階層構造内のすべての寄与者から受領されたすべての寄与に応答する最終的な作品の形であり、前記さらなる受領証明チャレンジは、前記最終的な作品の受領の証明によって満足される、方法。
陳述32
本願のさらなる側面は、一時的または非一時的媒体に具現されたブロックチェーン・トランザクションを提供し、前記ブロックチェーン・トランザクションは、定義された寄与階層構造におけるより高レベルの寄与者の寄与の証拠を与え、前記ブロックチェーン・トランザクションは:
第1のより低レベルの寄与の第1の受領証明、
第2のより低レベルの寄与の第2の受領証明、および
前記中間レベルの寄与者のトランザクション署名
を含む一つまたは複数の入力と;
中間レベルの寄与についての受領証明チャレンジ、
受信側エンティティのためのトランザクション署名チャレンジ、および
前記より高レベルの寄与者の秘密鍵と、前記中間レベルの寄与の証明とに基づいて検証可能な裁量署名であって、前記より高レベルの寄与の前記証明は、前記より高レベルの寄与またはそのハッシュであり、前記ブロックチェーン・トランザクションは、前記より高レベルの寄与の前記証明を含まない、裁量署名
を含む一つまたは複数の出力とを含み、
少なくとも前記受領証明チャレンジおよび前記トランザクション署名チャレンジは、前記裁量署名とは独立して使用可能な前記一つまたは複数の出力のうちのある出力に含まれる。
本明細書に開示される別の側面によれば、第一の当事者、第二の当事者、関与しうる任意の第三の当事者、および/またはノードのネットワークの任意の一つまたは複数のノードのアクションを含む方法が提供されてもよい。
本明細書に開示される別の側面によれば、第1の当事者のコンピュータ装置、第2の当事者のコンピュータ装置、もしあれば第3の当事者のコンピュータ装置、および/またはノードのネットワークの一つまたは複数のノードを有するシステムが提供されてもよい。
開示された技法の他の変形例または使用事例は、本明細書の開示を与えられれば、当業者に明らかになりうる。本開示の範囲は、記載された実施形態によって限定されるものではなく、添付の特許請求の範囲によってのみ限定される。