(57)【要約】  本願明細書に記載の技術は、算術符号化のような圧縮技術を用いるビットストリームへの演算回路の無損失圧縮及びシリアル化のための方法及びシステムを実装するために利用されてよい。スマートコントラクトを表す演算回路は、算術符号化を用いてえ圧縮されてよく、それにより、その他の場合演算回路を格納するために必要なものより少ない計算リソース（例えば、データ記憶リソース）を用いてブロックチェーンネットワークに格納され又はブロードキャストできる圧縮演算回路を生成する。演算回路は、算術的演算子種類のようなデータ構造内の要素の頻度に基づきエントロピー符号化を用いて、効率的に圧縮できる。シリアル化解除及び圧縮解除のための命令も、ビットストリームに埋め込むことができ、（例えば、別のコンピュータシステムにより）元の回路を無損失に再構成するために使用できる。
2021518715.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実施される方法であって、
スマートコントラクトを表す演算回路に基づき、シンボルセットを取得するステップと、
前記演算回路を格納するために、少なくとも以下：
前記シンボルセットのサブセットを符号化値範囲にマッピングするステップと、
前記符号化値範囲の中の符号化値を選択するステップと、
圧縮演算回路の中で、前記符号化値を有する前記シンボルセットの第１サブセットを表すステップと、
により、データ量を削減するステップと、
前記圧縮演算回路を、ブロックチェーンネットワークのノードに格納させるステップと、
を含む方法。
【請求項２】
前記圧縮演算回路は、前記シンボルセットを異なる範囲の符号化値にマッピングするために使用可能なヘッダ符号化情報を含む、請求項１に記載の方法。
【請求項３】
前記符号化値は二進小数である、請求項１〜２のいずれか一項に記載の方法。
【請求項４】
前記符号化値は、前記符号化値が閾数のビットを用いて表すことができることに基づき、選択される、請求項１〜３のいずれか一項に記載の方法。
【請求項５】
前記符号化値を選択するステップは、
前記シンボルセットの異なるサブセットを前記符号化値範囲のサブ範囲にマッピングするステップと、
前記符号化値範囲の前記サブ範囲の中から前記符号化値を選択するステップと、
を含み、
シンボルの前記第１サブセットおよび前記第２サブセットは、前記圧縮演算回路の中で前記符号化値により表される、請求項１〜４のいずれか一項に記載の方法。
【請求項６】
前記スマートコントラクトを表す演算回路に基づき、シンボルセットを取得するステップと、
インプットファイルをシリアル化する要求を受信するステップであって、前記インプットファイルは、前記演算回路を表すコードの複数の行を含む、ステップと、
前記複数のうちの少なくとも一部をスキャンして、前記シンボルセットの中のシンボルをデータ構造に追加するステップと、
を更に含み、
前記シンボルセットは、前記データ構造から取得される、請求項１〜５のいずれか一項に記載の方法。
【請求項７】
前記シンボルセットの中のシンボルを前記シンボルと前記シンボルセットの別のシンボルとの間の差として符号化するステップ、を更に含む請求項１〜６のいずれか一項に記載の方法。
【請求項８】
前記演算回路は、演算子及び書き込み識別子を含み、前記シンボルセットは演算子であり、前記書き込み識別子は算術符号化方式に従い別個に符号化される、請求項１〜７のいずれか一項に記載の方法。
【請求項９】
前記演算回路を符号化するファイルをパースして、演算子セット及び前記演算子セットの少なくとも一部のパラメータセットを識別することにより、前記シンボルセットを取得するステップ、を更に含む請求項１〜８のいずれか一項に記載の方法。
【請求項１０】
前記符号化値範囲は、前記サブセットがパターン内に生じる確率に対応する、請求項１〜９のいずれか一項に記載の方法。
【請求項１１】
前記シンボルセットの前記サブセットは、１つのシンボルである、請求項１〜１０のいずれか一項に記載の方法。
【請求項１２】
前記圧縮演算回路は、前記演算回路の代わりに前記ブロックチェーンネットワークにブロードキャストされる、請求項１〜１１のいずれか一項に記載の方法。
【請求項１３】
前記圧縮演算回路を受信した前記ブロックチェーンネットワークのノードは、前記圧縮演算回路から前記演算回路を決定することができる、請求項１〜１２のいずれか一項に記載の方法。
【請求項１４】
システムであって、
プロセッサと、
前記プロセッサによる実行の結果として、前記システムに請求項１〜１３のいずれか一項に記載のコンピュータにより実施される方法を実行させる実行可能命令を含むメモリと、
を含むシステム。
【請求項１５】
実行可能命令を記憶した非一時的コンピュータ可読記憶媒体であって、前記実行可能命令は、コンピュータシステムのプロセッサにより実行された結果として、前記コンピュータシステムに、請求項１〜１３のいずれか一項に記載のコンピュータにより実施される方法を少なくとも実行させる、非一時的コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、（例えば、ディスク又はメモリに格納されるとき）演算回路により使用されるデータフットプリント（data  footprint）を削減する技術に関し、特に、圧縮技術、つまり本願明細書に記載の算術符号化技術を利用してシリアル化回路を生成する技術に関する。演算回路は、無損失方法で圧縮されて、後の時点で元の回路を完全に再生するために使用できるシリアル化回路を生成してよい。演算回路は、プログラムを生成するために使用されてよい。該プログラムの実行は、分散型コンピューティング環境の１つ以上のノードに委任できる。プログラムの正しい実行を保証するために、プロトコルが使用されてよい。ここで、第１コンピュータシステムは、プログラムの実行を第２コンピュータシステムに委任する。本発明は、特に、ブロックチェーンネットワークにおける使用に適するが、これに限定されない。
【背景技術】
【０００２】
本願明細書では、私たちは、全ての形式の電子的な、コンピュータに基づく、分散型台帳を包含するために用語「ブロックチェーン」を使用する。これらは、総意に基づくブロックチェーン及びトランザクションチェーン技術、許可及び未許可台帳、共有台帳、並びにこれらの変形を含む。他のブロックチェーン実装が提案され開発されているが、ブロックチェーン技術の最も広く知られているアプリケーションは、Ｂｉｔｃｏｉｎ台帳である。Ｂｉｔｃｏｉｎは、ここでは、便宜上及び説明の目的で参照されることがあるが、本発明はＢｉｔｃｏｉｎブロックチェーンと共に使用することに限定されず、代替のブロックチェーン実装及びプロトコルが本発明の範囲に包含されることに留意すべきである。用語「Ｂｉｔｃｏｉｎ」は、本願明細書では、Ｂｉｔｃｏｉｎプロトコルから派生した又はその変形である任意のプロトコルを含むと考えられる。
【０００３】
ブロックチェーンは、コンピュータに基づく非集中型の分散型システムとして実装されるピアツーピアの電子台帳であり、ブロックにより構成され、ブロックはまたトランザクションにより構成される。各トランザクションは、ブロックチェーンシステムの中の参加者間でデジタルアセットの制御の移転を符号化するデータ構造であり、少なくとも１つのインプット及び少なくとも１つのアウトプットを含む。各ブロックは前のブロックのハッシュを含み、これらのブロックは一緒に繋げられて、起源以来ブロックチェーンに書き込まれている全てのトランザクションの永久的な変更不可能な記録を生成する。トランザクションは、スクリプトとして知られている小さなプログラムを含む。スクリプトは、それらのインプット及びアウトプットを埋め込まれ、トランザクションのアウトプットがどのように及び誰によりアクセス可能であるかを指定する。Ｂｉｔｃｏｉｎプラットフォームでは、これらのスクリプトはスタックに基づくスクリプト言語を用いて記述される。
【０００４】
トランザクションがブロックチェーンに書き込まれるためには、検証されなければならない。ネットワークノード（マイナー）は、無効なトランザクションがネットワークから拒否され、各トランザクションが有効であることを保証するために作業を実行する。ノードにインストールされたソフトウェアクライアントは、未使用トランザクション（unspent  transaction,  UTXO）のロック及びアンロックスクリプトを実行することにより、UTXOに対してこの検証作業を実行する。ロック及びアンロックスクリプトの実行が真（TRUE）と評価する場合、トランザクションは有効であり、トランザクションはブロックチェーンに書き込まれる。したがって、トランザクションがブロックチェーンに書き込まれるためには、（ｉ）トランザクションを受信した第１ノードにより検証され、トランザクションが有効な場合には、ノードが該トランザクションをネットワーク内の他のノードに中継する、（ｉｉ）マイナーにより構築された新しいブロックに追加される、（ｉｉｉ）マイニングされる、つまり過去のトランザクションのパブリック台帳に追加される、ことが必要である。
【０００５】
ブロックチェーン技術は、暗号通貨の実装の使用のために最も広く知られているが、デジタル事業家が、Ｂｉｔｃｏｉｎの基づく暗号セキュリティシステム及び新しいシステムを実装するためにブロックチェーンに格納できるデータの両方の使用を開発し始めている。ブロックチェーンが、暗号通貨の分野に限定されない自動化タスク及びプロセスのために使用できれば、非常に有利になる。このようなソリューションは、ブロックチェーンの利益（例えば、永久性、イベントの記録の耐タンパ性、分散型処理、等）を利用しながら、それらの用途をより多様化し得る。
【０００６】
現在の研究の一分野は、「スマートコントラクト」の実装のためのブロックチェーンに基づくコンピュータプログラムの使用である。これらは、機械可読コントラクト又は合意の条項の実行を自動化するよう設計されたコンピュータプログラムである。自然言語で記述される伝統的なコントラクトと異なり、スマートコントラクトは、結果を生成するためにインプットを処理できるルールを含む機械実行可能プログラムであり、これは次に該結果に依存して動作を実行させる。
【発明の概要】
【０００７】
従って、クライアントコンピュータシステムが演算回路として表されるスマートコントラクトを生成し及び符号化技術、つまり算術符号化を使用して演算回路を圧縮し、それによりスマートコントラクトを格納する及び／又は実行する記憶空間要件を削減するために使用可能な圧縮演算回路を生成する（例えば、Ｂｉｔｃｏｉｎネットワークを用いて）検証可能な計算の枠組みを実装することが望ましい。一方で、圧縮演算回路は、ブロックチェーンネットワークへブロードキャストされ、非圧縮演算回路の代わりに（例えば、ブロックチェーンネットワークのノードに）格納できる。作業コンピュータシステムは、圧縮演算回路を取得し、（例えば、圧縮演算回路を伸長することにより）スマートコントラクトの実行可能バージョンを取得し、種々の検証可能な計算プロトコルに従いクライアントコンピュータシステムの代わりにスマートコントラクトを実行してよい。
【０００８】
このような改良されたソリューションがここで考案される。
【０００９】
したがって、本発明によると、添付の請求項において定められるシステム及び／又は方法が提供される。
【００１０】
本発明によると、ブロックチェーンネットワークのノードのためのコンピュータにより実施される方法であって、
スマートコントラクトを表す演算回路に基づき、シンボルセットを取得するステップと、
前記演算回路を格納するために、少なくとも以下：
前記シンボルセットのサブセットを符号化値範囲にマッピングするステップと、
前記符号化値範囲の中の符号化値を選択するステップと、
圧縮演算回路の中で、前記符号化値を有する前記シンボルセットの第１サブセットを表すステップと、
により、データ量を削減するステップと、
前記圧縮演算回路を、ブロックチェーンネットワークのノードに格納させるステップと、
を含む方法が提供され得る。
【００１１】
望ましくは、前記圧縮演算回路は、ヘッダを含み、前記ヘッダは、前記シンボルセットを異なる範囲の符号化値にマッピングするために使用可能な情報を符号化し、例えば第１シンボルは範囲［０−０．３）にマッピングし、第２シンボルは範囲［０．３、０．７）にマッピングし、第３シンボルは範囲［０．７，１）にマッピングする。前記異なる範囲は、重複しない範囲であってよく、その結果、特定の符号化値は正確に１つのシンボル又はシンボルセットに対応する。
【００１２】
望ましくは、前記符号化値は、０以上１未満の２進値のような２進数である。
【００１３】
前記符号化値は、前記符号化値が閾数のビットにより表されることに基づき選択されてよい。例えば、範囲内の２つの異なる２進値の間のように、より少ないビットで表すことのできる２進値が前記符号化値として選択されてよい。
【００１４】
前記符号化値を選択するステップは、
前記シンボルセットの異なるサブセットを前記符号化値範囲のサブ範囲にマッピングするステップと、
前記符号化値範囲の前記サブ範囲の中から前記符号化値を選択するステップと、
を含んでよく、
シンボルの前記第１サブセットおよび前記第２サブセットは、前記圧縮演算回路の中で前記符号化値により表される。
【００１５】
前記方法は、前記スマートコントラクトを表す演算回路に基づき、シンボルセットを取得するステップと、
インプットファイルをシリアル化する要求を受信するステップであって、前記インプットファイルは、前記演算回路を表すコードの複数の行を含む、ステップと、
前記複数のうちの少なくとも一部をスキャンして、前記シンボルセットの中のシンボルをデータ構造に追加するステップと、
を更に含んでよく、
前記シンボルセットは、前記データ構造から取得される。
【００１６】
前記方法は、前記シンボルセットの中のシンボルを前記シンボルと前記シンボルセットの別のシンボルとの間の差として符号化するステップ、を更に含んでよい。
【００１７】
望ましくは、前記演算回路は、演算子及び書き込み識別子を含み、前記シンボルセットは演算子であり、前記書き込み識別子は算術符号化方式に従い別個に符号化される。
【００１８】
前記方法は、前記演算回路を符号化するファイルをパースして、演算子セット及び前記演算子セットの少なくとも一部のパラメータセットを識別することにより、前記シンボルセットを取得するステップ、を更に含んでよい。
【００１９】
望ましくは、前記符号化値範囲は、前記サブセットがパターン内に生じる確率に対応する。例えば、２つのシンボルセットの間のように、より高い発生確率を有するシンボルセットは、比較的大きな対応する範囲の符号化値を有する。
【００２０】
望ましくは、前記シンボルセットの前記サブセットは、１つのシンボルである。
【００２１】
望ましくは、前記圧縮演算回路は、前記演算回路の代わりに前記ブロックチェーンネットワークにブロードキャストされる。
【００２２】
望ましくは、前記圧縮演算回路を受信した前記ブロックチェーンネットワークのノードは、前記圧縮演算回路から前記演算回路を決定することができる。
【００２３】
また、システムであって、プロセッサと、プロセッサによる実行の結果として、システムに請求項のいずれかに記載の方法を実行させる実行可能命令を含むメモリと、を含むシステムを提供することが望ましい。
【００２４】
また、実行可能命令を記憶した非一時的コンピュータ可読記憶媒体であって、コンピュータシステムの１つ以上のプロセッサによる実行の結果として、コンピュータシステムに請求項のいずれかに記載の方法を実行させる、非一時的コンピュータ可読記憶媒体を提供することが望ましい。
【図面の簡単な説明】
【００２５】
本発明の上述の及び他の態様は、本願明細書に記載の実施形態から明らかであり、及びそれを参照して教示される。本発明の実施形態は、単なる例を用いて及び添付の図面を参照して以下に説明される。
【図１】本開示の一実施形態における、演算回路のシリアル化及びシリアル化解除を示す。
【図２】本開示の一実施形態における、検証可能な計算及び関連するアクターのフロー図である。
【図３】本開示の一実施形態による、ドメイン固有言語（ＤＳＬ）符号から二次算術プログラム（ＱＡＰ）へのワークフローの一例を示す。
【図４】本開示の一実施形態による、シンボルシーケンスの算術符号化を視覚化する図を示す。
【図５】本開示の一実施形態による、算術符号化を用いて演算回路を圧縮する処理の説明図を示す。
【図６】一実施形態において、少なくとも一実施形態による、算術符号化の圧縮特性に基づき演算回路のシリアル化に対する種々の解が実装され得る図を示す。
【図７】一実施形態による、バッファを用いて演算回路のシリアル化を制御する処理の説明図を示す。
【図８】一実施形態による、演算回路に基づく辞書の特性を利用するシンボルシーケンスのマルチシンボル表現を視覚化する図を示す。
【図９】一実施形態による、マルチシンボル符号化の図を示す。
【図１０】更に圧縮可能なシリアル化回路の生成をもたらす、演算回路が識別子を集約することにより圧縮される図を示す。
【発明を実施するための形態】
【００２６】
以下は、本発明が一実施形態に従いどのように実施に動作し得るかの説明を提供する。本発明は、分散型コンピューティング環境の状況で実装されてよい。ここで、第１コンピューティングエンティティは、演算回路を利用して、実行が分散型コンピューティング環境のコンピューティングエンティティ（例えば、ブロックチェーンネットワークのノード）に委任できるプログラムを生成する。更に、プログラムの正しい実行は、計算上検証可能である。従って、演算回路に少なくとも部分的に基づき生成されたプログラムの実行を委任したクライアントコンピューティングエンティティは、プログラムが作業コンピューティングエンティティにより正しく実行されたことを検証できる。このように、分散型コンピューティング環境に対する種々の効率が実現されてよく、クライアントコンピューティングエンティティが別のエンティティの制御下でプログラムの実行をコンピュータシステムに委任し検証できるようにすることを含む。
【００２７】
以下により詳細に説明するように、算術符号化を用いて２進データストリームへと演算回路を圧縮し及びシリアル化するための可能な実装が説明される。２進データストリームは、無損失方法で、シリアル化解除され（de−serialised）及び伸長される。回路をシリアル化する種々の利点は、（例えば、演算回路の代わりにシリアル化回路を格納することにより）回路のデータ記憶フットプリント（footprint）の削減等を実現することである。例えば、ブロックチェーンネットワークのコンテキストでは、演算回路又は演算回路から導出されるプログラムは、ブロックチェーンネットワークの台帳に少なくとも部分的に符号化されてよい。本願明細書に記載の技術を用いて演算回路のデータ記憶フットプリントを削減することにより、ブロックチェーン台帳に格納されるデータ量を削減し得る。ブロックチェーン台帳は、ブロックチェーンネットワークの一部又は全部のノードにより複製され得るので、ブロックチェーンに格納されるデータのデータ記憶フットプリントの僅かな削減でも高く評価される。
【００２８】
特定の構造又はブロックの構築（building  blocks）は、この転換を助けるために使用できる。１つ以上の実施形態では、この表現は、分散型の検証可能な計算を提供できる包括的なパイプラインを構築する最初のステップと考えられる。本例で提示されるブロックの構築は、本発明の実施形態により扱われる全部の可能な高レベル言語構成の包括的リストであることを意図しない。更に、提示される例の代替実装が提供され得る。これらは、当業者の範囲内に包含される。
【００２９】
私たちは、本発明の説明のための実施形態を提供する。しかしながら、重要なことに、これは、本発明が使用され得るアプリケーションの一例である。当業者は、本発明が他のコンテキスト及びアプリケーションで有利に使用可能であることを理解する。
【００３０】
私たちの例では、ユーザがドメイン固有言語（Domain  Specific  Language  (DSL)）を用いてアプリケーションを生成することを可能にするプロトコルを考える。アプリケーションが生成されると、その実行は、信頼されないパーティ（「作業者（worker）」又は「証明者（prover）」と呼ばれる）に委託できると同時に、その正確さが公に検証できる。プロトコルは、以下を保証する暗号プリミティブを利用する：
・完全性（Completeness）。つまり、プロトコルが正しく遵守されれば、誠実な検証者は出力の有効性を確信する。
・健常性（Soundness）。つまり、不正な証明者が出力の信憑性について誠実な検証者を説得することはできない。
・ゼロ知識（Zero−knowledge）。つまり、不正な証明者は、出力の有効性以外に何も分からない。
【００３１】
プロトコルの幾つかの利点は以下を含み得る：
・参加者間の通信が必要ないので、中間者攻撃（Man−in−the−middle  attack）が防止される。
・ブロックチェーン技術の使用により、悪意あるノードがデータを改ざんすることを困難にする。
・信頼できるハードウェア装置のような信頼できる第三者が回避される。
・コントラクトの検証が、コードの再実行を意味しない。計算は、ネットワーク内の全てのノードにより複製されない。代わりに、正直な実行の証明が、公のブロックチェーンに格納され、検証目的でのみ使用される。
【００３２】
このようなシステムは、種々の種類のタスク及びプロダクトに対応する種々のアプリケーションを扱うことができる。この非集中化された分散型特性により、（Ｂｉｔｃｏｉｎ）ブロックチェーンは、２つ（以上の）パーティ間の合意を解決する良好に適する環境を提供する。
【００３３】
このようなシステムは、非集中化暗号通貨システムにおいてプログラム可能性を提供し促進することを必要とする。しかしながら、従来、スマートコントラクトプログラミングは誤りの生じやすい処理であると認識されている。以下を参照：Delmolino,  K.,  et  al.  (２０１５).  Step  by  Step  Towards  Creating  a  Safe  Smart  Contract:  Lessons  and  Insights  from  a  Cryptocurrency  Lab,  and  Juels,  A.,  et  al.  (２０１３)、The  Ring  of  Gyges:  Using  Smart  Contracts  for  Crime。
【００３４】
従って、アプリケーションの記述及び読み取りを容易にするＤＳＬがプログラマにより使用可能であること、従って、エラーを低減し、プログラミング処理中の時間、努力、コスト、及びリソースを削減することは有利である。理想的には、専門家でないプログラマが、暗号方法を実装する必要がなく、種々のアプリケーションを記述できる。代わりに、コンパイラ／インタープリタが、ユーザとブロックチェーンとの間で、ソースコードを暗号プロトコルに自動的にコンパイルする。これらは、特に本発明により解決される技術的問題である。
【００３５】
図１は、本開示により実装可能な一実施形態の説明図１００である。本願明細書に記載の技術は、コンピュータプログラムの実行において利用される演算回路をシリアル化し（serialise）及びシリアル化解除する（de−serialise）ために利用されてよい。演算回路は、一実施形態に従い、クライアント（例えば、鍵生成及び検証）及び証明者（例えば、計算及び証明（proof）生成）のための暗号法ルーチンのセットにコンパイルされる２次算術問題（Quadratic  Arithmetic  Problem  (QAP)）を構築するために利用されてよい。クライアント及び証明者は、プロトコルを利用して、証明者がプログラムを正しく実行することをクライアントが効率的に検証できる方法で、プログラムの実行を証明者に委任してよい。シリアル化（serialised）回路は、演算回路と関連して必要な計算リソース（例えば、ハードディスク空間）を削減することにより、コンピュータシステムの動作を向上するために利用されてよい。一実施形態では、演算回路は、コードセットを含むシリアル化回路を生成するために圧縮されるシンボルセット（例えば、算術ゲート及び値）として表現される情報を含む。ここで、シンボルセットは、無損失方法でコードセットから導出可能である。圧縮回路の送信は、より多くの回路を送信可能にすることにより、コンピュータシステムの効率的データ伝送帯域幅を向上し得る。例えば、圧縮回路が演算回路のサイズを５０％だけ削減した場合、効率的データ伝送帯域幅は２倍になってよい。これは、最大で２倍の圧縮演算回路が同じバイト数を用いて伝送できるからである（留意すべきことに、実際のデータ伝送帯域幅の向上は、圧縮されないパケットヘッダのようなデータオーバヘッドにより、２倍より少ないことがある）。演算回路のデータフットプリントの削減は、演算回路の使用に関連するコンピュータハードウェア要件を低減し得る。例えば、本願明細書に記載の回路を使用し、格納し又はその他の場合に相互作用するコンピュータシステムにより利用される短期メモリ（例えばＲＡＭ）データ記憶、及び／又はデータ帯域幅の量を低減する。圧縮回路の送信は、より多くの回路を送信可能にすることにより、コンピュータシステムの効率的データ伝送帯域幅を向上し得る。例えば、圧縮回路が演算回路のサイズを５０％だけ削減した場合、効率的データ伝送帯域幅は２倍になってよい。これは、最大で２倍の圧縮演算回路が同じバイト数を用いて伝送できるからである（留意すべきことに、実際のデータ伝送帯域幅の向上は、圧縮されないパケットヘッダのようなデータオーバヘッドにより、２倍より少ないことがある）。演算回路のデータフットプリントの削減は、演算回路の使用に関連するコンピュータハードウェア要件を低減し得る。例えば、本願明細書に記載の回路を使用し、格納し又はその他の場合に相互作用するコンピュータシステムにより利用される短期メモリ（例えばＲＡＭ）データ記憶、及び／又はデータ帯域幅の量を低減する。
【００３６】
概して、演算回路Ｃは、フィールドＦからの値を運び論理及び／又は演算ゲートを接続するワイヤを含む。一実施形態では、回路Ｃは、演算ゲート、入力ワイヤ、及び出力ワイヤを含むデータフィールドセットにより表すことができる。回路は、目標実行環境（例えば、プロセッサアーキテクチャ）に依存して実行の最適化を可能にする、バージョン番号、ワイヤの合計数、及びビット幅ｎｂｉｔのような情報を含むヘッダを更に含んでよい。演算回路の圧縮は、他のフィールドから決定可能なデータフィールドを除去すること、エントロピー符号化方式を適用すること、及びそれらの組み合わせにより、達成されてよい。種々の種類の簡略化ルールが、演算回路が符号化されるフォーマットに基づき圧縮ルーチンの一部として、使用されてよい。例えば、幾つかの情報は、要求されなくてよい。例えば、入力のためのワイヤ識別子、出力ゲートのワイヤ識別子、第１ゲートの第１入力、最終出力ワイヤ識別子は、圧縮されてよく（例えば、シリアル化回路の部分として明示的に符号化されなくてよい）、又はそれらの任意の組み合わせ。
【００３７】
種々の実施形態ではエントロピー符号化又は符号化方式は、（例えば、上述の簡略化ルールに基づき）演算回路又はその一部に適用される。エントロピー符号化は、ソースシンボルのシリアル化のための変数長コードテーブルを生成するために利用されてよい。ハフマン符号化は、コードテーブルを生成するために利用されてよい。コードテーブルでは、より高い頻度で生じるソースシンボルがより短いコードを用いて符号化され、より低い頻度で生じるソースシンボルがより長いコードを用いて符号化され、コードの長さは、ソースシンボル又はシーケンスの生じる頻度に反比例してよい。これらの技術を用いて、演算回路は、長期データ記憶媒体（例えば、ハードディスクドライブ）及び短期データ記憶媒体（例えば、ランダムアクセスメモリ）における記憶のために少ない計算リソースしか必要としないシリアル化回路へと圧縮できる。
【００３８】
上述のようにハフマン符号は、コードテーブルを生成するために利用されてよい。ハフマン符号は、無損失データ圧縮を達成するために使用できる特定種類の最適プレフィクスコードを表す。ハフマンアルゴリズムからの出力は、ソースシンボル、例えばファイル内の文字又はコマンドを符号化するための可変長コードテーブル（例えば、コードブック）であってよい。一実施形態では、アルゴリズムは、ソースシンボルからの可能な値毎に、推定された又は測定された発生確率又は頻度（重み）からテーブルを導出する。通常、より一般的なシンボルは、あまり一般的でないシンボルより少ないビットを用いて表される。一実施形態では、ハフマン符号化は、入力重みの数と線形な時間で、コードを見付けるよう効率的に実装できる。ここで、入力重みはソートされた順序である。この方針は、シンボルを別個に符号化する方法の中で最適であってよい。ハフマン符号化は、シンボル毎の表現を選択する特定の方法を用いてよく、結果としてプレフィクスコードを生じる。つまり、何らかの特定のシンボルを表すビット列は、任意の他のシンボルを表すビット列のプレフィクスには決してならない。
【００３９】
サイズｎを有するアルファベットＡからのシンボルセット｛ａ０，ａ１，．．．，ａｎ−１｝、及び通常、確率に比例するそれらの重み｛ｐ０，ｐ１，．．．，ｐｎ−１｝が与えられると、ルートからの最小重み経路長を有するツリーが要求される。出力コードＣ（Ｐ）＝｛ｃ０，ｃ１，．．．，ｃｎ−１｝は、最小重み経路長Ｌ（Ｃ）を有する２進コードワードのタプルである。
【００４０】
シャノンのソース符号化定理により定義されるように、ヌルでない確率を有する各シンボルａｉの情報コンテンツｈ（単位：ビット）は、ｈ（ａｉ）＝ｌｏｇ２（１／ｐｉ）である。エントロピーＨ（単位：ビット）は、各シンボルの情報コンテンツのゼロでない確率ｐｉを有する全部のシンボルａｉに渡る、加重和である：
【数１】
2021518715.tif 000003
【００４１】
エントロピーは、関連する重みを有する所与のアルファベットについて理論的に可能な最小コードワード長の指標である。通常、ハフマン符号は、ユニークである必要がない。所与の確率分布のハフマン符号のセットは、該確率分布のＬ（Ｃ）を最小化するコードの空でないサブセットである。
【００４２】
シリアル化回路は、無損失方法で拡張又は伸長ルーチンを用いて元の演算回路を導出するために使用できる。留意すべきことに、この文脈で「無損失（可逆、lossless）」は、圧縮データからソースデータが完全に導出可能である種類の圧縮アルゴリズムを表す。デジタル圧縮のコンテキストでは、無損失圧縮は、ソースビットストリームの各ビットがシンボルセットを含む圧縮データから導出可能であることを表してよい。反対に、損失圧縮（不可逆圧縮、lossy  compression）は、圧縮データが、圧縮データからソースビットストリームの各ビットを導出できない種類の圧縮アルゴリズムを表してよい。損失圧縮の一例は、ＭＰ３オーディオ符号化フォーマットである。
【００４３】
図２は、本開示の一実施形態に含まれる、検証可能な計算及び関連するアクターのフロー図２００の一例を示す図である。図２に示すように、検証可能な計算の図２００は、クライアントノード２４０、作業者（例えば、証明者）ノード２５０、及び検証者ノード２６０を含んでよく、これらは本開示の一実施形態における検証可能な計算プロトコルのステップを実行することに関連する。実施形態では、クライアントノード２４０、作業者ノード２５０、又は検証者ノード２６０のうちの１つ以上は、ブロックチェーンネットワーク内のノードである。
【００４４】
一実施形態では、設定段階は、ドメイン固有言語（domain−specific  language  (DSL)）でコントラクトを記述するステップを含む。インタープリタは、クライアントノード２４０であってよく、ソースコードを入力として取り入れ、フィールドＦからのデータを運び加算及び乗算ゲートに接続する「ワイヤ」で構成される演算回路Ｃを生成する。演算回路自体は、ハードウェア回路ではなく、有効非巡回グラフ（directed  acyclic  graph  (DAG)）であってよい。ワイヤは、ＤＡＧ内のエッジであってよい。しかしながら、演算回路は、ワイヤ及び論理ゲートを有する物理的回路で実装され得ることが考えられる。２０２で、クライアントノード２４０は、汎用言語（general−purpose  language  (GPL)）で記述された計算Ｐを、演算回路Ｃへとコンパイルする。実施形態では、クライアントノード２４０は、演算回路Ｃ及び入力ｘを作業者ノード２５０に供給する。
【００４５】
回路Ｃから、本開示の一実施形態は、元の回路Ｃの完全な記述を提供する多項式のセットを含む二次プログラムＱを生成できる次に、２次プログラムを実行し及び検証するとき作業者ノード２５０及び検証者ノード２６０により使用されるべき公開パラメータ（public  parameter）が生成されてよい。
【００４６】
２０４で、作業者ノード２５０は、入力ｘについて回路Ｃ又は２次プログラムＱを実行し、出力がｙであることを主張する。幾つかの実施形態では、作業者ノード２５０（つまり証明者）は、｛Ｃ，ｘ，ｙ｝について有効なトランスクリプトを取得することが期待される。従って、２０６で、作業者ノード２５０は、トランスクリプトを符号化する。幾つかの例では、有効なトランスクリプト｛Ｃ，ｘ，ｙ｝は、回路ワイヤへの値の割り当てである。その結果、入力ワイヤに割り当てられた値はｘのものであり、中間値はＣの中の各ゲートの正しい動作に対応し、出力ワイヤに割り当てられた値はｙである。主張された出力が正しくない場合（つまり、ｙ≠Ｐ（ｘ））、｛Ｃ，ｘ，ｙ｝の有効なトランスクリプトは存在しない。
【００４７】
２０８で、作業者ノード２５０は、クライアントノード２４０に出力ｙを提供する。実施形態では、公開評価鍵ＥＫ、及び公開検証鍵ＶＫは、ｊクライアントノード２４０により選択された又はクライアントノード２４０からのシークレット値ｓを用いて導出される。実施形態では、作業者ノード２５０は、これらの公開鍵を用いて、特定の入力ｘに対して計算を評価する。実施形態では、出力ｙ、内部回路ワイヤの値、及びＥＫは、正当性の証明（proof−of−correctness）πを生成するために使用される。証明πは、ブロックチェーンに格納され、複数のパーティ（例えば、検証者ノード２６０）により検証され、作業者ノード２５０は、複数のパーティと個別に相互作用する必要がない。この方法では、２１０で、検証者ノード２６０は、公開検証鍵ＶＫ及び証明πを用いて支払いトランザクションを検証でき、それによりコントラクトを有効にする。
【００４８】
検証可能な計算は、計算の証明の生成を可能にする技術である。一実施形態では、このような技術は、本願明細書では作業者と呼ばれる別の計算エンティティに入力ｘについて関数ｆの評価を委託するために、クライアントにより利用される。幾つかの例では、クライアントは計算上制限され、クライアントは関数の評価を実行できない（例えば、クライアントに利用可能な計算リソースを用いる計算の期待される実行時間が、最大許容閾値を超える）。しかしながら、このような必要はなく、クライアントは、通常、入力ｘについての関数ｆの評価を、計算実行時間、計算コスト（例えば、関数の評価を実行するための計算リソースを割り当てる経済的コスト）、等のような任意の適切な基準に基づき、言わば委任してよい。
【００４９】
一実施形態では、作業者は、本開示の他の場所でより詳細に記載されるようなブロックチェーンノードのような任意の適切な計算エンティティである。一実施形態では、作業者（例えば、ブロックチェーンノード）は、入力ｘについて関数ｆを評価し、出力ｙ、及び上述のクライアント及び／又はブロックチェーンネットワークの他のノードのような他の計算エンティティにより検証可能な、出力ｙの正しさの証明πを生成する。証明は、引数（argument）とも呼ばれてよく、上述の作業者により生成された出力の正しさを決定するために、入力ｘに対して関数ｆを再計算する代わりに、証明の正しさを検証することにより、実際の計算を行うより早く検証でき、従って、計算オーバヘッドが削減できる（例えば、パワーオーバヘッド、及び計算リソースへの電力供給及び運用に関連するコストを削減する）。ゼロ知識（zero−knowledge）の検証可能な計算では、作業者は、クライアントに、作業者が特定の特性を有する入力を知っていることのアテステーション（証明、attestation）を提供する。
【００５０】
知識のゼロ知識証明の効率的な変形は、ｚｋ−ＳＮＡＲＫ（Succinct  Non−interactive  ARgument  of  Knowledge）である。一実施形態では、ｚｋ−ＳＮＡＲＫに基づく全部のペアリングは、作業者が汎用グループ演算を用いて多数のグループ要素を計算し、検証者が多数のペアリング積の式を用いて証明をチェックする処理を含む。一実施形態では、線形対話証明は有限フィールドに対して機能し、作業者の及び検証者のメッセージは、フィールド要素のベクトルを含み、符号化し、参照し、又はその他の場合にはフィールド要素を決定するために使用可能な情報を含む。
【００５１】
一実施形態では、本願明細書に記載のシステム及び方法は、ブロックチェーンのマイナー（例えば、ノード）が計算（例えば、入力ｘについての関数ｆの評価）を１回実行し、出力の正しさを検証するために使用可能な証明を生成することを可能にする。ここで、証明の正しさを評価することは、関数を評価することより計算上安価である。この状況では、演算及びタスクのコスト（つまり、どれくらい高価か）は、演算又はタスクを実行する計算上の複雑さを表してよい。一実施形態では、計算上の複雑さは、ソートアルゴリズムを実行するときの、平均的な計算コスト又は最悪の計算コストを表す。例えば、ヒープソートアルゴリズム又はクイックソートアルゴリズムであって、両方とも平均的な計算コストＯ（ｎ  ｌｏｇ  ｎ）を有するが、クイックソートは最悪の計算コストＯ（ｎ２）を有し、ヒープソートは最悪の計算コストＯ（ｎ  ｌｏｇ  ｎ）を有する。一実施形態では、入力ｘについて関数ｆを評価するための平均的な計算コスト及び／又は最悪の計算コストは、証明の正しさを評価するものより悪い。従って、本願明細書に記載のシステム及び方法の使用は、非常に有利であり、例えば、更に計算上高価なコントラクトを実行可能にでき、例えば、コントラクトは、ブロックチェーンを検証するために必要な時間を比例的に増大しなくてよい。更なる利点は、検証者システムの電力消費の削減を含み得る。これにより、検証者コンピュータシステムの効率を向上し、証明の正しさを評価するときの検証者コンピュータシステムを運用することに関連するエネルギコストを削減する。
【００５２】
一実施形態では、検証鍵ＶＫ又はその部分は、ゼロ知識プロトコルの設定段階で生成された公開パラメータから抽出でき、証明π、及び入力／出力データと一緒に、作業者により提供された宣言された正しさの証明の計算を検証するために使用できる。例えば、以上及び以下に記載したように、ロックスクリプトが検証鍵ＶＫを変更からセキュアに守ることを可能にし、及び証明πの有効性をチェックするシステム及び方法は、トランザクション検証の間に、ブロックチェーン上でゼロ知識プロトコルの実行を可能にする。従って、本開示は、計算の検証で使用される要素を格納する（例えば、Ｂｉｔｃｏｉｎに基づくネットワークで）ブロックチェーンスクリプトを用いて検証段階を実行するシステム及び方法を提案する。
【００５３】
図３は、本開示の一実施形態による、ドメイン固有言語（ＤＳＬ）符号から二次算術プログラム（ＱＡＰ）へのワークフローの一例３００を示す。具体的に、図３は、変換器２０４によりＧＰＬコード３０６に変換されるＤＳＬコード３０２を示す。ＧＰＬプリコンパイラ３０８（プリプロセッサとしても知られる）は、ＧＰＬコード３０６により参照される外部ライブラリ３１０を組み入れて、ＧＰＬ前処理コード３１２を生成する。ＧＰＬ前処理コード３１２は、演算回路３１４へと変換される。演算回路３１４は、シリアル化回路３２０を生成するために圧縮された縮小演算回路３１６を生成するよう最適化される。シリアル化回路３２０から、ＱＡＰ多項式３１８が導出される。
【００５４】
一実施形態では、ドメイン固有言語（ＤＳＬ）コード３０２は、正確な意味論を有する公式言語で記述されたアプリケーションである。一実施形態では、コード３０２は条件セットを含み、ＤＳＬコード３０２の結果は、条件セットの充足に依存する。アプリケーションの一例（例えば、スマートコントラクト）は、入力として被保険者の保険料と保険会社による被保険者への可能な補償を取り入れる保険契約である。被保険者がスマートコントラクトの期間中に損失を受けた場合（例えば、第１条件の充足）、スマートコントラクトの実行は、保険会社に保険料を分配し、被保険者に損失の補償を分配する。他方で、被保険者がスマートコントラクトの期間中に損失を受けなかった場合、スマートコントラクトの実行は、保険会社に保険料を分配し、保険会社に可能な補償を分配する。
【００５５】
一実施形態では、変換器３０４は、ソフトウェアプログラムである。該ソフトウェアプログラムは、実行の結果として、ＤＳＬで記述されたＤＳＬコード３０２のような条件セットを受信し、ＤＳＬコードを、ＧＰＬコード３０６のようなＧＰＬソースコードに変換する。一実施形態では、ＧＰＬコード３０６は、Ｃ＋＋プログラムのようなＧＰＬプログラムであり、ＤＳＬコード３０２で定義されたコードを含む。幾つかの例では、汎用プログラミング言語又は汎用言語（general−purpose  language  (GPL)）は、ＤＳＬと対照的に、広く適用可能である。汎用プログラミング言語の例はAda,  ALGOL,  アセンブリ言語,BASIC,  Boo,  C,  C++,  C#,  Clojure,  COBOL,  Crystal,  D,  Dart,  Elixir,  Erlang,  F#,  Fortran,  Go,  Harbour,  Haskell,  Idris,  Java,  JavaScript,  Julia,  Lisp,  Lua,  Modula−２,  NPL,  Oberon,  Objective−C,  Pascal,  Perl,  PHP,  Pike,  PL/I,  Python,  Ring,  RPG,  Ruby,  Rust,  Scala,  Simula,  Swift,及びTcl.  C++を含み、本開示の実施形態で参照されることがあり、命令型、オブジェクト指向型の、汎用プログラミング機能を有するが、低レベルメモリ操作のための機能も提供する汎用プログラミング言語である。留意すべきことに、図３のコンテキストでは、代替として、「コード」は、記載されるコンテキストに基づき、実行可能コード（例えば、オブジェクトコード）、ソースコード、それらの両方、又はそれらの組み合わせを表してよい。
【００５６】
一実施形態では、ＧＰＬプリコンパイラ３０８は、ＧＰＬコード３０６及び必要な外部ライブラリ３１０を処理してスタンドアロン型ＧＰＬコード３０６前処理コード３１２を生成するコンピュータ実行可能プログラムである。実施形態では、ＧＰＬプリコンパイラ３０８は、ＧＰＬコード３０６内に見付かった定数表現及びレジスタシンボルを評価する。
【００５７】
一実施形態では、外部ライブラリ３１０は、呼び出しによりＧＰＬコード３０６により利用される、予め記述されたサブルーチン、関数、クラス、コンテナ、値、及び／又は可変型の集合である。例えば、外部ライブラリ３１０を呼び出すことにより、ＧＰＬコード３０６は、機能自体を実装する必要がなく、該ライブラリの機能を得る。
【００５８】
一実施形態では、ＧＰＬ前処理コード３１２は、式及び演算子のセットを含む。演算子は、算術演算子（例えば、加算（＋）、乗算（＊）、等）、比較演算子（例えば、未満（＜）、等しい（＝）、以上（≧）、等）、条件文（例えば、if−then（？，：））、又は論理演算（例えば、ＡＮＤ（＆＆）、ＯＲ（｜｜）、ＮＯＴ（！）、ＸＯＲ（○の中に＋）、等）を含んでよい。幾つかの実施形態では、メイン関数は、所定の名称及びフォーマットを有するよう生成される。
【００５９】
一実施形態では、演算回路３１４は、変数セットに対するＤＡＧである。一実施形態では、０の入次数（in−degree）ＤＡＧの全てのノードは、変数（例えば、ｘｉ）を表す入力ゲートであり、ＤＡＧの全ての他のノードは、和ゲート（＋）又は積ゲート（×）である。実施形態では、全てのゲート（ノード）は、１の出次数（out−degree）を有し、従って基本のグラフは有向木である。実施形態では、演算回路３１４は、複雑さの２つの指標：サイズ及び深さを有する。幾つかの例では、演算回路の「サイズ」は、演算回路３１４内のゲートの数に基づく。幾つかの例では、演算回路の「深さ」は、演算回路内の最長有向パスの長さに基づく。
【００６０】
一実施形態では、縮小演算回路３１６は、入力セットが与えられるとＤＳＬコード３０２の中で指定されるような、条件セットの結果を決定するために使用可能な縮小又は最小有向非巡回グラフ（directed  acyclical  graph  (DAG)）である。幾つかの実施形態では、縮小演算回路３１６は、最小化された（つまり、最小次数に縮小された）演算回路である。幾つかの実施形態では、最適演算回路は、必ずしも最小演算回路ではなくてよい（例えば、回路内の算術演算の数及び種類に依存して、特定のより大きな演算回路が、より大きな演算回路より速いと評価されてよい）。また、このような実施形態では、縮小演算回路３１６は、（例えば、最大速度、より少ないメモリ使用、最大効率プロセッサ利用率、等について）最適化されるが、必ずしも最小化された演算回路ではない。縮小演算回路３１６は、英国特許出願番号ＧＢ１７１８５０５．９号に記載された技術を用いて生成されてよい。
【００６１】
縮小演算回路３１６のような演算回路は、本願明細書に記載された技術に従い圧縮されて、シリアル化回路３２０を生成してよい。シリアル化回路３２０は、格納され読み出される必要のあるコードテンプレート又は標準アプリケーションの場合に使用されてよい。シリアル化回路３２０を利用することにより、パーティは、新しいアプリケーションが生成される度に、ＧＰＬから回路のインスタンスを生成する必要を除去できる。それにより、クライアント及び証明者がそのようなアプリケーションの特定のコードテンプレート又は部分を再利用するプロトコルの効率を向上する。シリアル化回路３２０は、算術的演算子種類のようなデータ構造内の要素の最頻出要素に対してエントロピー符号化を用いて生成されてよい。シリアル化解除及び伸長のための命令（例えば、シリアル化コードをソースシンボルにマッピングするコードブック）は、シリアル化回路の受信者がソース回路を再構成できるようにするシリアル化ビットストリームに埋め込まれてよい。
【００６２】
一実施形態では、ＱＡＰ多項式３１８は、元の演算回路（例えば、図３の演算回路３１４）の完全な記述を提供する数学的な式の中に表現された変数及び係数を有する１つ以上の式である。実施形態では、ＱＡＰ多項式のうちの多項式は、演算回路のルートにおけるそれらの評価の観点から定義される。例えば、Gennaro,  R.  et  al.,  Quadratic    Span    Programs  and  Succinct  NIZKs  without  PCPs  (２０１３)に記載されている。実施形態では、ＱＡＰ多項式は、スマートコントラクトの表現として、ブロックチェーントランザクションのロックスクリプト内に符号化される。実施形態では、ロックスクリプトは、実行されると、（例えば、ロックスクリプトの実行の結果として）パラメータ値のセットを受信する。パラメータ値のセットは、スマートコントラクトの結果を決定させるために、ＱＡＰ多項式に変数として入力される。
【００６３】
実施形態では、ＧＰＬ多項式３０８は、演算ゲートを有する演算回路であってよいＧＰＬ前処理コード３１２を生成する。しかしながら、複雑な演算回路も、条件及びフロー制御文により、論理サブモジュールを埋め込むことに留意する。
【００６４】
図４は、本開示の一実施形態による、シンボルシーケンスの算術符号化を視覚化する図４００を示す。一実施形態では、シンボルシーケンスのための算術符号化を生成する処理は、図４に示す図と結合して実行できる。算術符号化は、無損失データ圧縮で使用されるエントロピー符号化の一種である。シンボルセットは、通常、ＡＳＣＩＩコードのように、シンボル当たり固定数のビットを用いて表現され、頻繁に使用されるシンボルは、より少ないビットにより格納されてよい。ハフマン符号化と異なり、算術符号化は、メッセージ全体を０と１の間の範囲（０≦ｘ＜ｙ＜１）のような任意の精度範囲［ｘ，ｙ）へと符号化する。
【００６５】
例えば、図４は、任意の精度範囲内で使用して符号化され得るシンボルシーケンス｛ａ１，ａ２，ａ１｝の算術符号化を示す。一実施形態では、シンボルは、０と１との間の範囲（例えば、端点を含む及び／又は除く）で符号化される。一実施形態では、シンボルは、端点を含み及び／又は除いて０と２ｎとの間の範囲で符号化される。図４によると、一例は、シーケンス内の第１シンボルに対応する値範囲セットを含む。例えば、第１シンボルに対応する範囲［０，ｘ１）内の値はａ０であり、第１シンボルに対応する範囲［ｘ１，ｙ１）内の値はａ１であり、第１シンボルに対応する範囲［ｙ１，１）内の値はａ２である。一実施形態では、値範囲の各々は、シンボルシーケンス内の第２シンボルに対応するために、更に分割できる。例えば、及び図４に従い、ｘ１＜ｗ２＜ｘ２＜ｙ２＝ｙ１とする。次に、本例に従い、以下の２シンボルシーケンスが、以下の値範囲を用いて符号化できる。
【表１】
2021518715.tif 000004
【００６６】
種々の実施形態では、算術コーダは、確率ｐｉで、サイズｎを有するアルファベットＡから任意の所与のシンボルセットａｉに対して準最適出力を生成できる。ここで、最適値は−ｌｏｇ２ｐｉである。データモデルは、メッセージのシンボルの中にどんなパターンが見付かるかを予測することにより、定義できる。正確な予測は準最適解を保証する。一実施形態では、適応モデルは、前のシンボルに基づき、シンボルの現在の確率のそれらの推定を変化させる。一実施形態では、デコーダは、エンコーダと同じモデルを利用する。
【００６７】
シンボルの符号化及び復号は、以下に詳述する種々の技術を用いて実行できる。符号化処理の各ステップｊにおいて、新しいシンボルは、現在の間隔［ｘｊ，ｙｊ］（本願明細書の他の場所に記載されるように、端点を除く及び／又は含む実施形態は、本開示の範囲内にあると考えられる）及び現在の確率ｐｊを用いて符号化できる。種々の実施形態によると、ｐｊ（ａｉ）は、ステップｊにおいて、シンボル確率ａｉとして定義される。汎用表記ｐｉは、一実施形態では、適応モデルが使用されない場合及びその場合にのみ有効である。エンコーダは、現在の間隔をサブ間隔に分割し、各サブ間隔は、該シンボルの確率に比例する、現在の間隔の部分を表す。確率ｐｊ（ａｉ）を有する入力シンボルａｉのサブ間隔は、更新された間隔［ｘｊ＋１，ｙｊ＋１］になる：
【数２】
2021518715.tif 000005
【００６８】
シーケンスの全部のシンボルが符号化されると、結果として生じる間隔は、シンボルシーケンス全体に対応する（例えば、明確に識別する）。図４に示すように、間隔に包含される値は、「最終範囲」とマークされる（例えば、端点を含む及び／又は除く）。例えば、以下のテーブルは、一実施形態では、シンボルシーケンスを反映し、対応する範囲は前記のシーケンスを表す：
【表２】
2021518715.tif 000006
【００６９】
更に、留意すべきことに、図４に示された間隔又は値範囲は、必ずしも縮尺通りではなく、図４は特定の間隔が他の間隔に対して比例することを意味しない。一実施形態では、間隔は、シンボルの発生確率に（例えば、値を丸め込んだ結果として特定の精度閾値に）比例する又は実質的に比例する。一実施形態では、ステップｊ＋１におけるシンボルの確率は、ステップｊにおける先行するシンボルに依存する。一実施形態では、ステップｊにおけるシンボル発生確率は、無記憶性である確率を有する。ここで、ｊ＋１におけるシンボル発生分布は、任意の先行するシンボルの値に依存しない。
【００７０】
一実施形態では、シンボルシーケンスは、間隔（又は間隔内にある任意の部分）及び確率モデルを知ることにより再構成できる。ストリームが、例えば確率ｐＥＯＳを有するＥＯＳ（end  of  stream）シンボルａＥＯＳを用いて内部的に終了しない場合、復号処理を中断するために外部メカニズムが利用されてよい。幾つかの場合には、異なる等しく短い１０進分数が、同じ間隔を表すために使用できる。従って、少ないビットを有する２進表現は、一実施形態により、圧縮係数を最大化するために選択できる。例えば、範囲［０．６５，０．６７）の中の２つの分数は、大きく異なる数のビットにより表すことができる。それにより、シーケンスの圧縮係数に影響を与える：
【表３】
2021518715.tif 000007
従って、一実施形態では、シンボルシーケンスを符号化するために使用されるビットの数を削減する（又は最小化する）ために技術が利用される。整数個のビットが２進符号化で使用される実施形態では、算術エンコーダは、圧縮メッセージのサイズに渡り、１ビットの最大オーバヘッドを導入し得る。算術コーダは、デコーダが適合可能な精度ψの固定限度で動作し、その精度で、分数を最も近い等価値に丸め込んでよい。例えば、等しい確率ｐ＝１／３を有するこれらのシンボルは、［０，１）の中の３つの間隔を正しく表すために、無限の精度を要求する。一実施形態では、精度値が選択され、例えばψ＝８ビットであり、以下に示すように精度において２進範囲を計算するために使用できる：
【表４】
2021518715.tif 000008
一実施形態では、１つ以上の数字が現在符号化範囲の２つの限度の間で共有されるとき、これらの数字は、出力ストリームに付加され廃棄される。符号化範囲内の残りの数字は左にシフトされ、一方で、新しい数字が右に付加される。上限には１、下限には０である。従って、システムは、計算の精度にもやは貢献しないビットを追い払うことにより、ψビットの精度で動作し続ける。
【００７１】
圧縮の上限に関して、サイズＬ及びアルファベットＡについてシンボル頻度ｆ（ａｊ）のメッセージが与えられると、無限精度の符号化部分は、ＬＣ個のビットで表すことができる：
【数３】
2021518715.tif 000009
【００７２】
ＬＣをＬで割ると、メッセージの自己エントロピー（self−entropy）を得る。つまり、算術符号化は、エントロピーに漸近的に近い符号化を行う：
【数４】
2021518715.tif 000010
【００７３】
従って、算術符号化は、実質的に、シンボル確率が入力メッセージのものと同じである確率モデルのエントロピーに近い符号化が可能である。
【００７４】
留意すべきことに、算術符号化は、一度に１つのシンボルを圧縮するのではなく、従って、エントロピー限度に任意に近くなる。これに対して、ハフマン符号化は、全部のシンボル確率が２のべき乗でない限り、エントロピー限度に近づかない。以下の例を考える：低いエントロピー（ｐ０＝０．９５、ｐ１＝０．０５）を有する２つのシンボル｛０，１｝。ハフマン符号化は１ビットを各値に割り当て、結果として入力と同じ長さのコードを生じるが、算術符号化は、以下の最適圧縮比に近づく：
【数５】
2021518715.tif 000011
【００７５】
図５は、本開示の一実施形態による、算術符号化を用いて演算回路を圧縮する処理５００の説明のための例を示す。処理５００（又は本願明細書に記載の任意の他の処理、又はその変形及び／又は組み合わせ）の一部又は全部は、図４に関連して記載した技術に従い実行されてよい。処理５００は、算術符号化からシリアル化回路を生成するために実施できるステップの説明である。本願明細書に記載の算術符号化技術を用いて演算回路をシリアル化した結果として、演算回路の代わりに、演算回路の圧縮表現が格納できる。例えば、一実施形態では、シリアル化回路は、演算回路の代わりに、ブロックチェーンのノードへブロードキャストされる。それにより、ブロックチェーンネットワークのノード（例えば、ブロックチェーン台帳のコピーを保持するノード）のデータ記憶要件を低減する。
【００７６】
一実施形態では、システムは、演算回路（例えば、データファイルの中の行コードとして表される）を取得し、演算回路をパースして、演算子及び演算子の入力及び／又は出力であるワイヤ識別子を識別する。一実施形態では、演算子及び識別子は、異なるデータ構造にプッシュされ、その中に格納される。図５に示す処理５００は、上述のように異なる種類の回路データを符号化するのに適してよい。一実施形態では、処理５００は、演算子及び識別子（例えば、入力識別子）について別個に実行される。
【００７７】
一実施形態では、システムは、スマートコントラクトを表す演算回路の第１の１つ以上のシンボルを取得する（５０２）。幾つかの場合には、処理は、一度に１つのシンボルを選択し、個々のシンボルを範囲にマッピングするステップを含む。一方で、他の場合には、複数のシンボルが収集され、複数のシンボルは、特定の間隔範囲に集合的にマッピングされる。一実施形態では、シンボルは、全部、特定種類である（例えば、全部が演算子、全部が入力ワイヤ）。
【００７８】
一実施形態では、システムは、間隔範囲のサブ範囲へのシンボルのマッピングを取得する５０４。初期間隔範囲は、グローバル最小値からグローバル最大値までに及んでよい（例えば、全部の符号化シンボルがグローバルｍｉｎ／ｍａｘ値の範囲内に含まれる）。特に断りの無い限り、ここで以上及び以下に図５と関連して記載した端点は、含まれ及び／又は含まれなくてよい（例えば、範囲は、下限を含み、上限を除いてよい）。一実施形態では、グローバル最小値が０（含む）であり、グローバル最大値が１（除く）であり、従って、全体の値範囲は、１未満の値を有する２進小数により表される。マッピングは、初期間隔範囲を重複しないサブ範囲のセットに分割するマッピングテーブルを表す。従って、サブ範囲は、集合的に初期間隔範囲全体をカバーする。サブ範囲の各々は、一実施形態では、シンボル又はシンボルのセットにマッピングされる。一実施形態では、システムは、マッピング及び第１の１つ以上のシンボルに基づき、次の間隔範囲を決定する５０６。システムは、一実施形態では、第１の１つ以上のシンボルに対応するマッピングテーブルエントリを発見することにより、決定を行い、次の間隔範囲になるべき第１の１つ以上のシンボルに対応するサブ範囲を選択する。一実施形態では、マッピングが失敗した場合（例えば、第１の１つ以上のシンボルに対するマッピングテーブルエントリが存在しない）、処理はエラーにより早く終了する。例えば、グローバル範囲が［０，１）である場合、以下のマッピングテーブルが、シンボルセットについて存在してよい：
【表５】
2021518715.tif 000012
一実施形態では、システムは、第１の１つ以上のシンボルのサブ範囲を決定した後に、符号化すべき更なるシンボルが存在するか否かを決定する５０８。一実施形態では、（例えば、第１の１つ以上のシンボルがデータ構造からポップされた後に、）データ構造の中に追加シンボルが存在するか否かを決定することにより、決定が行われる。追加シンボルが存在する場合、システムは、一実施形態では、シンボルの、前に決定したサブ範囲のサブ範囲へのマッピングを取得する。一実施形態では、サブ範囲は、以下の場合のように、比例関係で前の範囲と同じである：
【表６】
2021518715.tif 000013
一実施形態では、システムは、この第２マッピングを使用して、１つ以上のシンボルの第２セットについて、これまで処理したシンボルに対応する間隔範囲を決定する。一実施形態では、これらのステップは、残されたシンボルがなくなる（シンボルを格納するデータ構造が空になる、ファイルの終わりに達する、等）まで、繰り返される。その結果、最後のサブ範囲が保持され、値を符号化するために使用される。例えば、前の例を続けると、シンボルセット全体がａ２ａ３である場合、最後の間隔範囲は［０．７，０．８）である。従って、本例では、０．７（含む）と０．８（除く）の間の任意の２つの（binary）１０進数がシンボルａ２ａ３を表すために使用できる。
【００７９】
最後の間隔範囲が取得されると、システムは、最後の間隔範囲の中の値を用いてシンボルを符号化する５１２。間隔範囲の中の任意の値は、シンボルを符号化するのに適する。例えば、前の例を続けると、ａ２ａ３を符号化するための有効な値の例は、０．７、０．７５、及び０．７９７９．．．を含む。ａ２ａ３を符号化するための無効な値の例は、０．６９６９．．．を含む。シンボルセットを符号化するための複数の適した値が存在し得るので、圧縮率を最大化するために、より少ないビットによる２進表現が選択できる。
【００８０】
一実施形態では、演算子及び／又はワイヤ識別子（又はそれらの部分）は、図５に従い説明されたようにシリアル化されてよい。結果として生じるシリアル化回路は、演算回路の代わりに、例えばブロックチェーン台帳に、格納される５１４。それにより、提示されたスマートコントラクトを符号化するための記憶要件を低減する。
【００８１】
図６は、一実施形態において、少なくとも一実施形態による、算術符号化の圧縮特性に基づき演算回路のシリアル化に対する種々の解が実装され得る図６００を示す。一実施形態では、シリアル化処理は、図６を参照して、ビットバッファとして、ビット毎の演算を提供するバッファにより管理される。一実施形態では、ビットバッファは、データがサポートされる永久記憶に転送される又はネットワークを介して送信される前に、データを一時的に格納する。図６に示すように、バッファは、（少なくとも）以下の方法：入力データｘをバッファに挿入するｐｕｔ（）関数、でアクセス可能である。一実施形態では、ｘはｎｂ個のビットを用いて格納され、ｓｅｎｄ（）関数は、バッファをフラッシュし、データを出力ストリームoutに転送する。
【００８２】
抽象レイヤとして機能する１つ以上のインタフェースが、型付けされた演算に提供されてよい。一実施形態では、低レベルメソッドｐｕｔ（）が、それぞれ整数、符号無し整数、及び文字列を（例えばバッファに）書き込むために利用できるｗｒｉｔｅＩｎｔ（）、ｗｒｉｔｅＵｎｉｔ（）、及びｗｒｉｔｅＳｔｒ（）のような異なる高レベルメソッドにより呼び出され得る。
【００８３】
一実施形態では、第３抽象レイヤが、入力（例えば、図６に示す入力ファイル６０２）から１行ずつデータを読み出し型付けされたデータを書き込む基礎にあるメソッドを呼び出すｓｃａｎ（）のような関数により提供される。一実施形態では、図６に示すｓｃａｎ（）関数は、呼び出されると、ファイル内の各コマンドが基礎にあるメソッドのうちの１つにマッピングできることをチェックするルーチンに対応する。一実施形態では、例えば認識されないコマンド、不正な署名フォーマット、不正な（例えば推奨されない）関数バージョンを検出した結果として生じる、マッピング内のエラーは、符号化処理全体の失敗を引き起こす。
【００８４】
一実施形態では、最高の抽象レイヤで、ｓｅｒｉａｌｉｓｅ（）関数は、回路情報を含む入力ファイルから読み出し、圧縮情報を出力ストリームに送信する。一実施形態では、出力ストリームは、ファイル又はネットワークリソースである。
【００８５】
一実施形態では、回路を含むファイルの行は、以下のフォーマットを有する。ここで、Ｐは演算子ＯＰのパラメータの数である。一実施形態では、演算子は特定数のパラメータを必要とする。一実施形態では、パラメータは、ｉｎ−ｐａｒａｍｅｔｅｒ（入力パラメータ）、ｏｕｔ−ｐａｒａｍｅｔｅｒ（出力パラメータ）、ｉｎｏｕｔ−ｐａｒａｍｅｔｅｒ（入力値を演算に提供し、演算の結果を格納するときに使用されるパラメータ）、等として分類できる。一実施形態では、別個のデータ構造が、演算子及びパラメータの圧縮のために使用される。一実施形態では、異なる圧縮技術が異なるデータ構造のために使用される。データ構造は、一実施形態では、キュー、スタック、ベクトル、等のような任意の適切なデータを使用して実装されてよい。一実施形態では、演算子キューの中の演算子は、固定数のパラメータ及び／又は固定サイズのパラメータを有する必要がある（例えば、可変長のデータｂｌｏｂはサポートされない）。例えば、データ構造に格納された「ＡＤＤ」演算は、正確に２つの入力パラメータと、１つの出力パラメータとを要求してよい。留意すべきことに、キューに格納された演算は、より上位の抽象レベルにおける演算と異なってよい。例えば、及び一般的には、加算演算は、任意の数の入力パラメータに対して実行できる（例えば、ａ＋ｂ＋ｃ＋．．．）．一実施形態では、データ構造は、異なる関数署名に対応する演算の複数の変形を有する。例えば、データ構造は、２つの入力と該２つの入力の和を表す１つの出力をサポートする「ＡＤＤ２」演算、３つの入力と該３つの入力の和についての出力パラメータをサポートする「ＡＤＤ３」演算、等をサポートしてよい。従って、一実施形態では、任意の数の入力の和は、固定数の入力を有する複数の加算演算を用いて一緒に繋げることができる。
【００８６】
一実施形態では、動的（例えば、可変）サイズを有するデータフィールドは、シリアル化パケットに埋め込むことができる。説明のための例として、同じサイズ（１６ビット）を有する圧縮データの４個のブロック［ｄａｔａ１，ｄａｔａ２，ｄａｔａ３，ｄａｔａ４］がシリアル化される場合を考える。一実施形態では、データブロックは、以下の符号化方式を用いて圧縮できる：固定サイズを有する第１フィールドは、ペイロード内のデータパケットの数のために予約されたフィールドのサイズ（例えば、単位：ビット）を含み、固定サイズ（例えば、第１フィールドと同じ又は異なるサイズ）を有する第２フィールドは、ペイロード内のデータパケットのために予約されたフィールドのサイズをビット単位で含み、第３フィールドはペイロード内のデータパケットの数を含み、残りのフィールドはデータパケットを含む。これは、動的なデータフィールドをどのように埋め込むかの単なる説明のための一例である。一実施形態では、第１データフィールドは、第１データフィールドに従う第１データ構造のサイズを符号化する。一方で、データ構造は、第２データフィールドに従う第２データ構造のサイズを符号化する第２データフィールドを含むことができる、等であり、ネストされた及び／又は順次パターンである。
【００８７】
一実施形態では、シリアル化回路のヘッダは、以下に詳細に記載されるような１つ以上の符号化フィールドを含む。一実施形態では、バージョンフィールドは、ヘッダの残りの部分をどのように解釈し及び／又は構築するか、及び固定サイズであるか（例えば、１バイト）に関する情報を提供する。一実施形態では、ヘッダは、演算のためのシンボルの数を示すパラメータＭを含む。一実施形態では、このパラメータは、シリアル化回路によりサポートされる演算の最大数に基づき決定される固定数のビットを用いて符号化される。一実施形態では、入力ワイヤの数（ＩＮ）、出力ワイヤの数（ＯＵＴ）、ワイヤ識別子の符号化サイズ（ｎｗ）、及びパラメータの符号化サイズ（ｎｐａｒａｍｓ）は、例えばハードコードされたビット数を用いて符号化される。一実施形態では、ワイヤの合計数Ｎは、符号化サイズｎｗを有する。留意すべきことに、ヘッダは、必ずしも、シリアル化データファイルの初めに又は先頭に位置する必要はない。一実施形態では、ヘッダは、ヘッダ情報の関連するデータの前の、シリアル化回路内の特定点に置かれるだけでよい。例えば、ヘッダがワイヤの合計数Ｎについてのパラメータを含む場合、一実施形態では、ヘッダ情報Ｎは、シリアル化回路内の任意の適切な点で符号化され、その結果、ワイヤ識別子を符号化するデータの前に読み出される。
【００８８】
一実施形態では、ヘッダは、埋め込み辞書を含む。一実施形態では、ハフマン符号化のシンボルの最大符号化サイズが先ず加算され、次に、各ペア（シンボルサイズ、シンボル）が、ペアの第１要素の最大符号化サイズを用いて加算される。一実施形態では、算術符号化が利用されない場合、ｎｐａｒａｍｓは、ヘッダの任意的パラメータである（例えば、省略できる）。一実施形態では、個々のシンボルの確率は、（符号化サイズｎｐｒｏｂを用いて）直接符号化できる。或いは、確率方式を提供でき、乗算係数がセット全体を表すために使用できる。例えば、４個のシンボルが以下の確率で使用される場合を考える：ｐ１＝０．１、ｐ２＝０．４、ｐ３＝０．１、ｐ４＝０．４。次に、乗算係数が、セット全体［１，４，１，４］を表すために使用できる。一実施形態では、これらの係数は、（例えば、符号化サイズｎｃｏｅｆｆを用いて）個々に符号化され、又は（符号化サイズｎｐｉｄを用いて）ユニークな識別子により方式テンプレートとして表される。一実施形態では、ヘッダは、ｎｐｒｏｂ及び／又はシンボルを識別子にマッピングするテーブルも符号化する。
【００８９】
一実施形態では、算術符号化は、値範囲を用いて、ヘッダ内に符号化された確率に従い、演算のシーケンスを表す。一実施形態では、符号化範囲の精度は、本開示の他の場所に記載されたように、例えば、図４に可憐する記載に関連して、計算できる。一実施形態では、このようにハフマン符号化を用いて、演算に対応する各圧縮シンボルは、ペイロードに順次追加される。
【００９０】
一実施形態では、ハフマン符号化が利用される場合のように、ワイヤ識別子は、それぞれペイロードに順次追加される。一実施形態では、算術符号化を用いてワイヤ識別子を符号化するために、異なる方針が利用できる。例えば、連続的符号化（例えば、ハフマン符号化による）、算術符号化（例えば、演算子による）、識別子の集約（例えば、図８に関連して以下に詳述される）、のうちの１つ以上である。
【００９１】
図７は、一実施形態による、バッファを用いて演算回路のシリアル化を制御する処理７００の説明図を示す。処理７００（又は本願明細書に記載の任意の他の処理、又はその変形及び／又は組み合わせ）の一部又は全部は、図５及び６に関連して記載した技術に従い実行されてよい。
【００９２】
一実施形態では、シリアル化処理７００は、異なる演算と演算の種類との間の抽象レイヤを提供するインタフェースのセットを用いて管理される。一実施形態では、第１抽象レイヤで、処理７００を実行するコンピュータシステムは、スマートコントラクトを表す演算回路をシリアル化するためのコマンドを受信する７０２。一実施形態では、コマンドは、シリアル化すべき演算回路を含むデータファイルへの参照を含むＡＰＩ（application  programming  interface）コマンドである。一実施形態では、データファイルは、未圧縮データファイルである（例えば、算術符号化技術を用いて圧縮されない）。一実施形態では、コマンドは、また、演算回路のシリアル化結果を格納する出力ストリームを識別する。
【００９３】
一実施形態では、スマートコントラクトは、正確な意味論を有するドメイン固有言語（ＤＳＬ）コードで記述される。スマートコントラクトは、一実施形態では、条件のセット及び１つ以上の結果を含み、該１つ以上の結果の充足が、１つ以上の入力に基づく条件のセットの評価に少なくとも部分的に依存する。一実施形態では、ＤＳＬコードは、汎用言語（ＧＰＬ）コードに変換される。汎用言語の非限定的な例は、Ada,  ALGOL,  アセンブリ言語,  BASIC,  Boo,  C,  C++,  C#,  Clojure,  COBOL,  Crystal,  D,  Dart,  Elixir,  Erlang,  F#,  Fortran,  Go,  Harbour,  Haskell,  Idris,  Java,  JavaScript,  Julia,  Lisp,  Lua,  Modula−２,  NPL,  Oberon,  Objective−C,  Pascal,  Perl,  PHP,  Pike,  PL/I,  Python,  Ring,  RPG,  Ruby,  Rust,  Scala,  Simula,  Swift,及びTclを含む。一実施形態では、ＧＰＬプリコンパイラは、外部ライブラリを用いてＧＰＬコードを処理して、スタンドアロン型ＧＰＬ前処理スマートコントラクトを生成する。一実施形態では、演算回路は、要素の演算ゲートに接続されるワイヤでシンボルを表現することにより構築される。
【００９４】
一実施形態では、システムは、演算回路を含む入力ファイルの第１行をスキャンする７０４。一実施形態では、読み出された入力ファイルの各行は、１つ以上の実行可能命令（例えば、アセンブリ命令）に対応し得るコマンドに対応する。一実施形態では、ファイルのスキャンは、ファイルの最初又は次の行からのコマンドの取得、及びコマンドの基礎にあるメソッドへのマッピングを含む。一実施形態では、システムは、コマンドに関連する型付けされた演算を決定することによりマッピングを決定する７０６。一実施形態では、サポートされる異なるデータ型は、整数、符号無し整数、文字列（例えば、ヌル終止符特別文字で終わる文字列）を含む。
【００９５】
一実施形態では、エンコーダの特定の設定に依存して、異なる種類の変数が、異なる数のビットを用いて符号化される７０８。符号化技術は、図５と関連して詳述される技術に従ってよい。例えば、ヘッダデータ、演算子データ、及びワイヤ識別子データの符号化は、それぞれ、データ符号化のための算術符号化技術のような異なる技術を利用できる。異なる符号化技術は、異なる種類の演算のために使用できる。一実施形態では、データが符号化されると、データはバッファに挿入される。一実施形態では、データをバッファに挿入するコマンド７１０は、データの特定数のビットを出力ストリームに書き込むコマンドである。システムは、次に、（例えば、ビットまたは文字の特定のｅｎｄ−ｏｆ−ｆｉｌｅシーケンスに達したか否かを検出することにより）ファイルの終わりに達したか否かを決定してよい７１２。一実施形態では、処理されるべきファイルの更なるコマンドがある場合、システムは、ファイルを通じて順にスキャンして、ファイルの第２、第３、第４、等の行を取得し、それらを上述のステップ７０４〜７１０に従い処理する。これらのステップは、ファイルの終わりが検出されるまで繰り返されてよい。ファイルの終わりで、システムは、バッファをフラッシュして、全部のデータを出力ストリーム又はファイルへ転送し、それによりシリアル化回路を生成する７１４。
【００９６】
図８は、演算回路に基づき辞書の特性を利用し及びコンピュータシステム又はＢｉｔｃｏｉｎネットワークのノードのようなコンピュータネットワークに格納される演算回路のサイズを削減するために本願明細書に記載の他の圧縮技術と関連して利用できるシンボルシーケンスのマルチシンボル表現を視覚化する図８００を示す。
【００９７】
一実施形態では、（例えば、利用可能な計算リソースにおける制約により）辞書のサイズは制限され、シンボルの発生は相関される（例えば、独立の確率特性がない）。従って、一実施形態では、圧縮のための算術範囲は、図８に示すような個々のプリミティブの機能を集約するシンボルを含む。
【００９８】
説明のための例として、以下の回路又は回路の部分（例えば、サブ回路）を考える。ここで、各演算の最初の２つのパラメータは入力識別子であり、最後のパラメータは出力識別子である。
ＡＤＤ  ４  ５  ６
ＡＤＤ  １  ６  ７
ＡＤＤ  １  ７  ８
【００９９】
上述の加算演算は、一実施形態では、以下の形式に圧縮できる：
ADD３  ４  ５  １  １  ８
【０１００】
一実施形態では、種々の因子が、データが圧縮可能な程度に影響を与える。例えば、辞書のサイズが制限されるか否か及び／又はどの程度制限されるか（確率範囲のフラグメント化は小数の２進表現の最適化を容易にしない）、プリミティブが個々に符号化されるか否か（確率範囲は集約されたシンボルに割り当てられる）、最小数の集約シンボルが提供される（あまり集約されないシンボルは、より効率的な確率範囲割り当てに相関される）。圧縮パラメータの推定は、一実施形態では、全ての算術演算が同じ数の入力（例えば、α）を有するという前提に基づき決定できる。一実施形態では、Ｎ個のプリミティブ演算子に基づき構築された集約シンボルＯＰＮは、対応するプリミティブ演算子より遅い平均レートＮ回で、圧縮出力ストリームのために新しいビットを生成する。さらに、Ｎ−１個の入力識別子が節約できる。演算及び識別子について初期の回路サイズがｓｉｚｅＯＰＳ＋ｓｉｚｅＩＤＳである場合、最適圧縮は以下により与えられる：
【数６】
2021518715.tif 000014
【０１０１】
集約シンボルの確率範囲は、固定、又は前のシンボルに依存して自動的に調整できる。固定確率の場合、シンボルシーケンス｛ｓ１，ｓ２，．．．，ｓβ｝について以下の集約確率Ｐ（ｓ１，ｓ２，．．．，ｓβ）を定義する：
【数７】
2021518715.tif 000015
【０１０２】
留意すべきことに、β！（つまり、βの階乗）個の、β個の連続するシンボルの異なる順列が利用可能である。シンボルシーケンスは、１つ以上のシンボルの繰り返しを含み得ることに留意する。乗算の可換特性により、各順列は、同じ集約シンボル確率により特徴付けられる。
【０１０３】
一実施形態では、シンボル深さβは、入力ストリームのコンテンツに従い符号化段階の間に動的に変更される。一実施形態では、放出されるシンボルの数Ｎ＊は、新しい範囲割り当てが実行されるとき、確立するために使用される。一実施形態では、Ｎ＊個の放出されたシンボルの２つの連続するウインドウに渡るマルチシンボル範囲は、異なり得る。更に、異なる集約シンボル深さβｉ（１≦ｉ≦ｎ＊）は、図９に示すように、現在ウインドウの中で定義されるｎ＊個のマルチシンボル範囲の各々について定義できる。一実施形態では、Ｎ＊は、定数であり、及び／又はシリアル化データのヘッダの中で定義される。
【０１０４】
図９００は、ストリーム[ａ，ａ，ａ]がマルチシンボルｓ１に変換され、ストリーム[ｂ，ｂ]がｓ２に変換され、シンボルｃがｓ３に変換される、マルチシンボル符号化の説明のための例を示す。本例では、集約シンボル深さはそれぞれβ１＝３、β２＝２、β３＝１であり、ｎ＊＝３である。
【０１０５】
所与の現在符号化ウインドウのβベクトルの設定は、一実施形態では、前の符号化ウインドウの設定に基づく。異なる重みｗが、前のウインドウに割り当てられる：
【数８】
2021518715.tif 000016
【０１０６】
従って、シンボルｓｉについてステップｊにおける集約シンボル深さ、つまりβｊ（ｓｉ）は、一実施形態では、前のステップβｊ−１（ｓｉ）と前のｊ−２個のステップの平均シンボル深さとの間の加重和として表される最も近い整数に近似できる。この式を用いて、コーダ及びデコーダの両方は、それらのシンボル確率範囲を同期できる。複数の重みも、以下のように定義できる：
【数９】
2021518715.tif 000017
【０１０７】
全部の重みが実数範囲［０，１］にあり、それらの和は１に等しくなければならない。
【０１０８】
一実施形態では、集約シンボル深さをどのように計算するか、及び所与の集約シンボルが何を表すかを確立する。図８の前の例では、ｓ１、シンボルの繰り返し［ａ］、ｓ２、シンボルの繰り返し［ｂ］、等を定義した。辞書が十分に小さい場合（例えば、１０個のシンボルより少ない）、組み合わせの完全な集合は予め構成できる。例えば、集約シンボル組み合わせのセットは、以下の方法で識別子にマッピングしてよい：
【表７】
2021518715.tif 000018
【０１０９】
図１０は、識別子を集約するために演算回路１００２が算術符号化技術を用いて圧縮され、結果として（例えば、識別子が集約されないシステムと比べて）更に圧縮可能なシリアル化回路１００４を生成する図１０００を示す。一実施形態では、演算子及び識別子は、別個の符号化され、例えば異なる技術を用いて符号化され、異なるデータ構造を用いて格納される（例えば、演算子のための第１キュー、及び識別子のための第２キュー）。図１０は、少なくとも一実施形態による、識別子の例示的なシリアル化を示す。一実施形態では、算術符号化技術を利用する圧縮処理は、演算回路１００２に適用されて、演算回路１００２よりサイズの小さい（例えば、より少ないビット数のデータを用いて格納される）シリアル化回路１００４を生成する。一実施形態では、シリアル化回路１００４は、平均的に（例えば、演算回路の全個体群（population）又は期待される回路動作／値に基づき決定される）、演算回路１００２よりサイズが小さい。一実施形態では、算術符号化は、演算回路１００２に適用された場合に、無損失伸長ルーチンを適用することにより演算回路１００２を完全に（例えば、ビット対ビットの精度で）再生成できる結果（つまりシリアル化回路１００４）を生成する一種の無損失圧縮である。
【０１１０】
一実施形態では、エントロピー方式が回路又は回路の部分を符号化するために利用されるか否か（例えば、識別子を符号化すべきか否か、演算子を符号化すべきか否か）は、データがどのように生成されるか、シンボルのサイズ、又はそれらの組み合わせに基づき決定される。例えば、幾つかの実施形態では、識別子は、それらの生成のランダムな特性及び／又はシンボルのサイズのために、エントロピー方式を用いて符号化されない。一般的に、より大きな回路はより多くの識別子を有し、シンボルのサイズを増大する。
【０１１１】
一実施形態では、識別子の集約は、圧縮方式の部分として、識別子の局所性を利用できる。これは、データの局所性に基づく使用に適してよい。つまり、回路の同じ部分で使用される識別子は、同様の値を有する傾向がある。留意すべきことに、これは全ての回路に該当せず、識別子の集約は、以下に更に詳述される集約技術を実行するか否かの決定（例えば、シリアル化の前の回路の分析）に基づき実行されてよい。
【０１１２】
集約技術の部分として、絶対値ではなく、２つの識別子の間の差が符号化される。一実施形態では、この方式は、入力識別子に適用され、出力識別子に適用されない。一実施形態では、出力識別子は、増分（incremental）であり、符号化処理中に必要なく、演算がシリアル化される順序に基づき除去され再構成できる。
【０１１３】
説明のための例として、以下の回路又は回路の部分を考える：
ＡＤＤ  ４  ５  ６
ＡＤＤ  １  ６  ７
ＡＤＤ  １  ７  ８
【０１１４】
識別子は、以下のように符号化できる：
ＡＤＤ  ４  １  ６
ＡＤＤ  −４  ５  ７
ＡＤＤ  −５  ６  ８
【０１１５】
最初の入力（４）は、通常通り符号化される。２番目の入力は、２番目の入力と前の入力との間の差として符号化される。言い換えると、５−４＝１である。次の識別子は、出力であり、集約目的で無視される。第２の加算演算を続けると、３番目の入力は３番目の入力と２番目の入力との間の差として符号化され：１−５＝−４、以下同様である。一実施形態では、この方式の利点のうちの１つは、多数の識別子を有する大規模回路の状況で、直ちに理解される（例えば、多数の識別子は、絶対的な識別子の値を符号化するために追加データビットを必要とする）。平均して、識別子を符号化するためにｎ個のビットが必要な場合、差を符号化するためにはｎ／２個より少ないビットしか必要ない。一実施形態では、入力ワイヤは、差の値を削減及び／又は最小化するために、再構成できる（例えば、無損失にかつ完全に再生成可能な方法でそれらを符号化するためには、少ないビットしか必要ない）。
ＡＤＤ  ４  １  ６
ＡＤＤ  −４  ０  ７
ＡＤＤ  ５  １  ８
【０１１６】
符号を表現するために追加ビットを考える。第１のソリューションは、５個の符号化入力識別子［１，−４，５，−５，６］を符号化するために１４個のビットを必要として。一方、第２のソリューションは、符号化識別子［１，−４，０，５，１］を符号化するために１０個のビットしか必要としない。各行の入力は、必要な合計ビットを最小化するために、回路生成の間に再構成できる。
【０１１７】
明細書及び図面は、したがって、限定的意味ではなく説明的であると考えられるべきである。しかしながら、これらへの種々の変更及び変化が、特許請求の範囲に記載された発明の範囲から逸脱することなく行われてよいことが明らかである。同様に、他の変形は、本開示の範囲内にある。したがって、開示の技術は種々の変更及び代替構成を受けるが、その特定の図示の実施形態が図示され、詳細に上述された。しかしながら、本発明を開示の１又は複数の特定の形式に限定する意図はなく、反対に、添付の特許請求の範囲に定められるように、本発明の範囲に包含される全ての変更、代替構成、均等物をカバーすることを意図する。
【０１１８】
開示の実施形態を記載する文脈における用語「a」及び「an」、「the」及び同様の参照は（特に以下の特許請求の範囲の文脈では）、文脈上特に示され又は明確に否定されない限り、単数及び複数の両方をカバーすることを意図する。用語「有する」、「含む」（comprising、having、including、containing）等は、特に断りのない限り、制限のない用語（つまり、「含むがそれに限定されない」を意味する）と考えられるべきである。用語「接続される（connected）」は、未修飾であり物理的接続を参照するとき、仲介物がない場合でも、部分的または全体的に含まれる、付加される、又は一緒に結合されると考えられるべきである。本開示における値の範囲の記載は、特に断りのない限り、単に、その範囲に含まれる各々の個別の値を個々に参照することの簡略表記法として機能し、各別個の値は個々に記載されたように本明細書に組み込まれると考えられるべきである。用語「セット又は集合」（例えば、「アイテムのセット」）又は「サブセット又は部分集合」の使用は、特に断りのない限り又は文脈上否定されない限り、１つ以上の構成要素を含む空ではない集合であると考えられるべきである。さらに、特に断りのない限り又は文脈上否定されない限り、対応するセットの用語「サブセット」は、必ずしも、対応するセットの真部分集合を示さず、サブセット及び対応するセットは等しくてもよい。
【０１１９】
結合的言語、例えば「A、B、及びCのうちの少なくとも１つ」又は「A、B及びCのうちの少なくとも１つ」は、特に断りのない限り又は文脈上特に明確に否定されない限り、通常、アイテム、用語、等が、A又はB又はCのいずれか、又はA及びB及びCのセットのうちの空でない任意のサブセットであり得ることを表すために使用されると文脈上理解される。例えば、３人のメンバを有するセットの説明のための例では、結合的フレーズ「A、B、及びCのうちの少なくとも１つ」又は「A、B及びCのうちの少なくとも１つ」は、以下のセット{A}、{B}、{C}、{A,B}、{A,C}、{B,C}、{A,B,C}のいずれかを表す。したがって、このような結合的言語は、通常、特定の実施形態が少なくとも１つのA、少なくとも１つのB、及び少なくとも１つのCがそれぞれ存在することを必要とすることを意味することを意図しない。さらに、特に断りの無い限り、又は文脈上特に明らかでない限り、語句「〜に基づく」は、「〜に少なくとも部分的に基づく」を意味し、「〜のみに基づく」を意味しない。
【０１２０】
記載のプロセスの動作は、特に断りのない限り又は文脈上明確に否定されない限り、任意の適切な順序で実行できる。記載のプロセス（又は変形及び／又はそれらの結合）は、実行可能命令により構成された１つ以上のコンピュータシステムの制御下で実行でき、ハードウェア又はその組み合わせにより１つ以上のプロセッサ上で連携して実行するコード（例えば、実行可能命令、１つ以上のコンピュータプログラム又は１つ以上のアプリケーション）として実装できる。幾つかの実施形態では、コードは、コンピュータ可読記憶媒体に、例えば１つ以上のプロセッサにより実行可能な複数の命令を有するコンピュータプログラムの形式で格納できる。幾つかの実施形態では、コンピュータ可読記憶媒体は、非一時的である。
【０１２１】
任意の及び全ての例の使用、又は提供された例示的な言語（例えば「のような（such  as）」）は、単に、本発明の実施形態をより良好に解明することを意図しており、特に断りのない限り本発明の範囲に限定を課すものではない。明細書中のいかなる言語も、任意の請求されない要素を本発明の実施に必須であることを示すと考えられるべきではない。
【０１２２】
本発明を実施するために発明者に知られたベストモードを含む本開示の実施形態が記載された。種々のこれらの実施形態は、前述の説明を読むことにより、当業者に明らかになる。発明者は、当業者がこのような変形を適切に利用することを期待し、発明者は、本開示の実施形態が特に記載されたものと異なる方法で実施されることを意図する。したがって、本開示の範囲は、適用される法により許容されるように、添付の特許請求の範囲に記載された主題の全ての変更及び均等物を含む。さらに、それらの全ての可能な変形における上述の要素の任意の組み合わせは、特に断りのない限り又は文脈上特に明確に否定されない限り、本開示の範囲により包含される。
【０１２３】
上述の実施形態は、本発明を限定するのではなく、説明すること、及び当業者は添付の特許請求の範囲により定められる本発明の範囲から逸脱することなく多くの代替的実施形態を考案できることに留意すべきである。特許請求の範囲において、括弧内の任意の参照符号は、請求項を限定することを意図しない。用語「有する」及び「含む」（comprising、comprises）等は、任意の請求項又は明細書全体に列挙されたもの以外の要素またはステップの存在を排除しない。本願明細書では、「有する」は「有する又は構成される」を意味し、「含む」は「含む又は構成される」を意味する。要素の単数の参照は、該要素の複数の参照を排除しない。逆も同様である。本発明は、幾つかの別個の要素を含むハードウェアにより、及び適切にプログラムされたコンピュータにより、実装できる。幾つかの手段を列挙する装置クレームでは、これらの手段のうちの幾つかは、１つの同じハードウェアアイテムにより具現化できる。単に特定の手段が相互に異なる従属請求項に記載されるという事実は、これらの手段の組み合わせが有利に使用されないことを示さない。
【図１】
2021518715.tif 000019
【図２】
2021518715.tif 000020
【図３】
2021518715.tif 000021
【図４】
2021518715.tif 000022
【図５】
2021518715.tif 000023
【図６】
2021518715.tif 000024
【図７】
2021518715.tif 000025
【図８】
2021518715.tif 000026
【図９】
2021518715.tif 000027
【図１０】
2021518715.tif 000028
【国際調査報告】
2021518715.tif 000029
2021518715.tif 000030