(57)【要約】  本発明は、高水準ソースコードを該ソースコード内に表された機能を表現する算術回路に変換するシステム及び方法を提供する。本発明は、この変換を実行する翻訳／解釈コンポーネントを含む。好適な一実施形態において、ソースコードは、ブロックチェーンプラットフォームに関連して使用されるようなスマートコントラクトである。本発明は、例えば、ビットコインネットワークに関連して使用されてもよい。一実施形態による方法が、高水準ソースコード（例えば、スマートコントラクト）の部分を処理して算術回路を生成するステップを含む。算術回路は、ソースコード内に表された機能のうち少なくとも一部を表現するように構成された１つ以上の算術ゲートを含む。処理するステップは、ソースコード内に提供された１つ以上の定数を評価して、ブール及び／又は算術演算子を含む１つ以上の式を生じるステップを含む。算術回路は、算術ゲートに接続されたｎビットワイヤを含み、ハードウェア及び／又はソフトウェア回路を提供するために使用できる。算術回路は、プロセッサ上で実行可能な二次プログラムを生成するために使用できる。
2021502636.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータにより実現される方法であって、
算術回路を生成するソースコードの部分を処理するステップであり、
前記ソースコードは高水準プログラミング言語で書かれ、
前記算術回路は、前記ソースコード内に表された機能の一部又は全部を表現するように構成された１つ以上の算術ゲートを含む、ステップ、
を含む方法。
【請求項２】
ｉ）前記算術回路は前記ソースコードのマシン実行可能バージョンであり、結果を計算するように構成され、かつ／あるいは
ｉｉ）前記ソースコードはスマートコントラクトである、
請求項１に記載の方法。
【請求項３】
前記処理するステップは、
前記ソースコード内に提供された１つ以上の定数を評価して、ブール及び／又は算術演算子を含む１つ以上の式を提供するステップ
を含む、請求項１又は２に記載の方法。
【請求項４】
前記算術回路を使用してハードウェア及び／又はソフトウェア回路を提供するステップ、
をさらに含む請求項１乃至３のうちいずれか１項に記載の方法。
【請求項５】
前記算術回路は、算術ゲートに接続されたｎビットワイヤを含む、
請求項１乃至４のうちいずれか１項に記載の方法。
【請求項６】
前記算術回路はアーキテクチャ非依存である、請求項１乃至５のうちいずれか１項に記載の方法。
【請求項７】
当該方法は、前記ソースコードを前処理して１つ以上の定数を決定するステップをさらに含み、前記前処理するステップは、
コメントを除去するステップと、
ヘッダファイルからソースファイルにヘッダ宣言をインポートするステップと、
複数のソースファイルをマージするステップと、
ディレクティブ及びマクロを解決し、あるいは評価するステップと、
のうち１つ以上を含む、請求項１乃至６のうちいずれか１項に記載の方法。
【請求項８】
当該方法は、前記ソースコード内に宣言された全てのグローバル変数を検出するステップをさらに含み、グローバル変数は、関数、構造体若しくはクラス、定数、及び／又は実行のエントリポイントに関する、請求項１乃至７のうちいずれか１項に記載の方法。
【請求項９】
当該方法は、
シンボルのテーブルを生成して、前記ソースコード内に提供された各シンボル（すなわち、識別子）を前記ソースコード内に提供された宣言情報に関連づけるステップであり、前記テーブル内のシンボルはグローバル及び／又はローカルシンボルである、ステップ
をさらに含む、請求項１乃至８のうちいずれか１項に記載の方法。
【請求項１０】
当該方法は、１つ以上の入力変数に適用される論理及び／又は算術演算の組み合わせとして１つ以上のアウト変数を表す算術及び／又は論理式をもたらす前記ソースコードの行ごとの評価を実行するステップをさらに含む、請求項１乃至９のうちいずれか１項に記載の方法。
【請求項１１】
前記行ごとの評価は、
型を復号するサブステップ、
式を復号するサブステップ、
式を評価するサブステップ、及び／又は
前記機能により必要とされるデータ構造のためのメモリを割り振るサブステップ
を含む、請求項１０に記載の方法。
【請求項１２】
前記式の前記算術及び／又は論理演算を算術ゲートにマッピングするステップ、
をさらに含む請求項１０又は１１に記載の方法。
【請求項１３】
前記マッピングするステップは、
ワイヤ拡張を実行するサブステップ、及び／又は
ワイヤ圧縮を実行するサブステップ
を含む、請求項１２に記載の方法。
【請求項１４】
前記算術回路を使用して、前記回路の記述を提供する多項式のセットを含む二次プログラムを生成するステップ、
をさらに含む請求項１乃至１３のうちいずれか１項に記載の方法。
【請求項１５】
１つ以上の入力を使用する前記二次プログラムの実行のために前記二次プログラムをエンティティに提供するステップ、
をさらに含む請求項１４に記載の方法。
【請求項１６】
請求項１乃至１５のうちいずれか１項に記載のステップを実行するように構成された、コンピュータにより実現されるシステムであって、好ましくは当該システムは、前記ソースコードの処理を実行するように構成されたインタプリタを含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、高水準ソースコードを別の形式に変換するツール、手法、及びシステム、例えばインタプリタの分野に一般に関する。本発明は、ブロックチェーン技術にさらに関し、特に、ブロックチェーンにより実現されるソリューションを構築するツールに関する。本発明は、例えばブロックチェーン上で実行するように構成されたスマートコントラクトなどの、マシン実行可能技術の改善された生成にさらに関する。
【背景技術】
【０００２】
本文献において、用語「ブロックチェーン」は、電子的なコンピュータベースの分散台帳のいくつかのタイプのうち任意のものを指す。これらには、コンセンサスベースのブロックチェーン及びトランザクションチェーン技術、許可あり（permissioned）及び許可なし（un-permissioned）台帳、共有台帳、及びこれらの変形が含まれる。それは、プライベート及びパブリックブロックチェーンをさらに含む。
【０００３】
ブロックチェーン技術の最も広く知られている適用はビットコイン（登録商標）台帳であるが、他のブロックチェーン実装が提案され、開発されている。本開示では、簡便さ及び例示の目的でビットコインの例が参照されることがあるが、本発明は、ビットコインブロックチェーン又は関連プロトコルのいかなる特定の実装又は変形での使用にも限定されず、代替的なブロックチェーンの実装及びプロトコルが本発明の範囲内に入ることに留意されたい。
【０００４】
ブロックチェーンはピアツーピアの電子台帳であり、これは、ブロックから構成されるコンピュータベースの非中央集権的なシステムとして実現され、同様に、ブロックはトランザクションから構成される。各トランザクションは、ブロックチェーンシステム内の参加者間のデジタル資産の制御の移転を符号化するデータ構造であり、少なくとも１つの入力及び少なくとも１つの出力を含む。各ブロックは前のブロックのハッシュを含み、それにより、ブロックが一緒にチェーン化されて、ブロックチェーンの開始以降にそれに書き込まれた全てのトランザクションの永続的で改変不可能なレコードを作成する。
【０００５】
スクリプト（Script）として知られるビットコインブロックチェーンのスクリプト言語はスタックベースである。アイテムがスタックの上部へプッシュされ、あるいは上部からポップされることが可能である。例えば、ＯＰ＿ＥＱＵＡＬ演算は、スタックから上部２つのアイテムをポップし、それらを比較し、結果（例えば、等しい場合に１、等しくない場合に０）をスタックの上部にプッシュする。本実施形態のいくつかにより採用されるいくつかのスクリプト言語では、少なくとも２つのスタック、すなわちメインスタックと代替スタックが存在し得る。
【０００６】
トランザクションがブロックチェーンに書き込まれるためには、それは「立証され（validated）」なければならない。ネットワークノード（マイナー）が、ワークを実行して各トランザクションが有効であることを確保し、無効なトランザクションはネットワークから拒絶される。ノードは、他のノードとは異なる有効性の標準を有することができる。ブロックチェーンにおける有効性がコンセンサスベースであるため、トランザクションは、トランザクションが有効であるとノードの過半数が同意した場合、有効と考えられる。ノードにインストールされたソフトウェアクライアントは、部分的には未使用トランザクション（unspent  transaction、ＵＴＸＯ）ロック及びアンロックスクリプト（locking  and  unlocking  scripts）を実行することにより、ＵＴＸＯを参照するトランザクションに対してこの立証作業を実行する。ロック及びアンロックスクリプトの実行がＴＲＵＥの評価であり、適用可能な場合における他の立証条件が満たされる場合、トランザクションはノードにより立証される。立証されたトランザクションは他のネットワークノードに伝搬され、すると、マイナーノードは該トランザクションをブロックチェーンに含めることを選択することができる。
【０００７】
ゆえに、トランザクションがブロックチェーンに書き込まれるためには、それは、ｉ）トランザクションを受信した第１のノードにより立証され、トランザクションが立証された場合、ノードはそれをネットワーク内の他のノードに中継する、ｉｉ）マイナーにより構築された新しいブロックに追加される、ｉｉｉ）マイニングされる、すなわち過去のトランザクションの公開台帳に追加される、がなされなければならない。トランザクションは、十分な数のブロックがブロックチェーンに追加されてトランザクションを事実上不可逆にしたとき、確認されたと考えられる。
【０００８】
ブロックチェーン技術は、暗号通貨実装の使用に対して最も広く知られているが、デジタル起業家は、新しいシステムを実現するために、ビットコインが基礎とする暗号セキュリティシステムとブロックチェーンに記憶できるデータとの双方の使用を探求し始めている。ブロックチェーンが暗号通貨の領域に限定されない自動化されたタスク及び処理に使用できる場合、かなり有利であろう。このようなソリューションは、その適用においてより多目的であると同時に、ブロックチェーンの利点（例えば、イベントの永続的な改ざん防止のレコード、分散処理等）を利用することができる。
【０００９】
現在の研究の１つの分野は、「スマートコントラクト」の実装のためのブロックチェーンの使用である。これらは、マシン読取可能な契約又は同意の条件の履行を自動化するように設計されたコンピュータプログラムである。自然言語で書かれる従来の契約と異なり、スマートコントラクトは、入力を処理して結果を生成することができるルールを含むマシン実行可能プログラムであり、これは次いで、これら結果に依存してアクションを実行させることができる。
【００１０】
実施形態において、スマートコントラクトは、作成者又は何らかの他の特定のエンティティがスマートコントラクトの強制及び／又は実行に必要とされないという意味で「スマート」である。実行又は強制に人間の対話は必要とされない。すなわち、特定のエンティティとの対話はスマートコントラクト内の特定のステップで符号化できるが、スマートコントラクトはその他の方法で自動的に実行及び自己強制可能である。それは、マシン読取可能及び実行可能である。いくつかの例において、自動実行は、任意のエンティティがＵＴＸＯを消費でき、そのようにするインセンティブ（例えば、報酬）を有することを指す。このような例において、ＵＴＸＯを消費できる「任意のエンティティ」は、何らかの秘密の知識を証明するよう求められることなくアンロックスクリプトを作成することができるエンティティを指すことに留意する。換言すれば、消費トランザクションは、データのソースが暗号秘密（例えば、秘密非対称鍵、対称鍵等）へのアクセスを有することを検証することなく、立証可能である。さらに、このような例において、自己強制は、ブロックチェーンネットワークの立証ノードが制約に従って消費トランザクションを強制させられることを指す。いくつかの例において、ＵＴＸＯの「消費（spending）」は、ＵＴＸＯを参照して有効として実行する消費トランザクションを作成することを指す。
【００１１】
したがって、単なる暗号通貨支払いの手段を越え、ブロックチェーン技術が使用可能な用途の周りには大きな関心がある。これには、ＩｏＴデバイスの制御、Ａ．Ｉ．技術を組み込んだインテリジェントシステムなどが含まれる。
【００１２】
しかしながら、Ｃ、Ｃ＋＋、Ｊａｖａ（登録商標）等の高水準言語を使用するプログラミングの分野には多くの熟練者が存在するが、ブロックチェーンのアプリケーションを作成することができる人は数が比較的少ない。これは部分的には、ブロックチェーンについて比較的低水準で、メイン及びａｌｔスタックを操作するｏｐ＿ｃｏｄｅを使用してコード化する現在の必要性のためである。特に、ブロックチェーンの実装のためのスマートコントラクトのプログラミングは、Delmolino,  K.ら（2015）のStep  by  Step  Towards  Creating  a  Safe  Smart  Contract:  Lessons  and  Insights  from  a  Cryptocurrency  Lab、及びJuels,  A.ら（2013）のThe  Ring  of  Gyges:  Using  Smart  Contracts  for  Crimeで調査されているように、困難でエラーを起こしやすいことが知られている。
【００１３】
ブロックチェーンと共に使用できるソリューション及びアプリケーションの作成を可能にすることにより、改善されたブロックチェーン及び関連プラットフォームが提供される。算術ゲートの算出のソリューションがさらに提供される。算術回路は、プレディケート（predicate）としての又はプレディケートの実行のために構成され得る。本発明は、（従来技術開示により検証又は証明を単に提供するのと対照的に）実行可能プログラムの作成及び符号化を可能にする。
【発明の概要】
【００１４】
したがって、１つ以上の態様においてブロックチェーン及び分散コンピューティング技術を改善する方法及びシステムを提供することが望ましい。このような改善されたソリューションが次に考案されている。ゆえに、本発明によれば、別記の特許請求の範囲に定義される方法及びシステムが提供される。
【００１５】
本発明は、非中央集権的なシステムにおいてプログラマビリティを提供し、容易にするように配置されたシステム及び方法を含み得る。それは、例えば、暗号通貨システム、ブロックチェーンにより実現されるシステム、及び／又は分散計算システムでもよい。１つの観点からは、それは、エラー、時間、労力、コスト、及びプログラミング処理の間に必要とされるリソースを低減する。ゆえに、それは、技術的な問題に対する技術的なソリューションを提供する。別の観点からは、それは、エラー及びバグの低減のため、強化されたブロックチェーンソリューションを提供する。それは、ソフトウェアの完全性も保持する。
【００１６】
有利には、既知のインタプリタ及びコンパイラとは異なり、本発明は、アーキテクチャ非依存のソリューションを提供する。さらに、それは、実行を可能にするために仮想マシン（ＶＭ）の使用を必要としない。
【００１７】
本発明は、ソースコードを入力として取り込んで算術回路ｃを生成する、コンピュータにより実現されるシステム及び方法を提供し得る。結果として生じる回路Ｃは、（検証のためのプルーフとは対照的に）ＨＬＬソースコードの機能の表現であり得る。実行されると、算術回路Ｃは計算の結果を提供し、これは次いで検証され（verified）得る。回路Ｃはマシン実行可能でもよく、あるいはマシン上で実行のために処理されてもよい。ソースコードは、計算を表し又は表現し得る。
【００１８】
この回路は、体（field）
【数１】
2021502636.tif 000003
からの値を搬送して加算及び乗算ゲートに接続する「ワイヤ（wires）」から構成されてもよい。算術回路は、ソフトウェア、及び／又はワイヤ及び論理ゲートを有する物理回路において具現化されてもよい。ソースコードは、ＨＬＬ又はＧＰＬで書かれた機能性又は計算Ｐの一部又は全部を含み、あるいは表現し得る。本発明は、その計算を算術回路Ｃに変換するインタプリタとして記述されてもよい。算術回路Ｃ及び何らかの入力ｘが、実行のためにエンティティに供給されてもよい。
【００１９】
本発明は、ソースコード内に表された計算を、（マシン／プロセッサにより）実行可能なプレディケートに変換し、あるいは翻訳し得る。（ＨＬＬ／ＧＰＬ）ソースコードは、予めコンパイルされ、あるいは前処理されてもよい。
１つ以上の実施形態において、公開評価鍵（evaluation  key、ＥＫ）及び公開検証鍵（verification  key、ＶＫ）が、秘密値ｓを使用して導出され得る。本方法は、ＥＫ及びＶＫを使用して特定の入力ｘに対する計算を評価するステップを含んでもよい。出力ｙ、１つ以上の回路ワイヤの値、及びＥＫが使用されて、プルーフオブコレクトネス（proof-of-correctness）πを生成することができる。プルーフπはブロックチェーンに記憶され得る。それはブロックチェーントランザクションに記憶されてもよい。本方法は、ブロックチェーントランザクションにプルーフを提供するステップを含み得る。それは、トランザクションをブロックチェーンにサブミットするステップ、及び／又はそれをブロックチェーンに記憶するステップを含んでもよい。
【００２０】
本方法は、ブロックチェーンに記憶されたプルーフを検証するステップを含み得る。それは、１つ以上のパーティ（parties）により検証されてもよい。有利には、それは、証明者（prover）にパーティの各々と別個に対話するよう求めることなく複数のパーティにより検証され得る。これは、従来技術と比較してより効率的及び迅速なソリューションを提供する。
【００２１】
ブロックチェーンネットワーク（例、ビットコイン）内のノードの全部又は一部がトランザクションを検証し得る。検証は、公開検証鍵ＶＫ及びプルーフπを使用してスマートコントラクトを検証するために実行されてもよい。
【００２２】
本発明の一利点は、マイナーが既知の従来のブロックチェーンプロトコルに従ってトランザクションを検証することである。検証処理は、ネットワーク内でのマイナーの役割の一部である。したがって、本発明は、検証が必要な既存の動作の一部として実行されるため、技術的利点に対してノードによりなされる労力を使用することができる。これは、従来技術と比較して効率的な配置を提供する。
【００２３】
いくつかの実施形態において、本発明は、図１に示すように、ＤＳＬで符号化されたスマートコントラクトから二次算術プログラム（quadratic  arithmetic  program、ＱＡＰ）へのワークフローの一部を形成し得る。
【００２４】
図２に示すように、ドメイン固有言語（Domain  Specific  Language、ＤＳＬ）スマートコントラクトは、高水準言語コントラクトに変換され得る。ＤＳＬスマートコントラクトは、正確なセマンティクスを有するフォーマルな言語で書かれてもよい。ＤＳＬスマートコントラクトは、条件のセットを含み得る。ＤＳＬスマートコントラクトの結果は、条件のセットの履行に依存してもよい。
【００２５】
ＨＬＬプリコンパイラ（プリプロセッサとも呼ばれ得る）は、ＨＬＬコントラクトにより参照される外部ライブラリを組み込んで、ＨＬＬ前処理（HLL  pre-processed）コントラクトを生成し得る。ＨＬＬプリコンパイラは、図２ではＣプリコンパイラとして参照され得る。ＨＬＬコントラクトは、図２ではＣ言語コントラクトとして参照され得る。
【００２６】
次いで、ＨＬＬ前処理コントラクト（すなわち、ソースコード）は、本発明の一実施形態により算術回路に変形され得る。この算術回路は、ＱＡＰ多項式が導出される縮小算術回路を生成するように最適化されてもよい。
【００２７】
前処理変換は、ソフトウェアプログラム（図２ではＣプリコンパイラと呼ばれるプログラム）により実行されてもよく、これは、実行の結果として、ＤＳＬで書かれたＤＳＬスマートコントラクトなどの条件のセットを受信し、ＤＳＬコードをＨＬＬコントラクトなどのＨＬＬソースコードに翻訳する。これは、図２では「Ｃ言語前処理コントラクト」として参照され得る。それは、本明細書では単に「ソースコード」と呼ばれることもある。ＨＬＬコントラクトは、ＤＳＬスマートコントラクトで定義されたコントラクトを含むＣ＋＋プログラムなどのＨＬＬプログラムでもよい。ＨＬＬプリコンパイラは、ＨＬＬコントラクト及び必要な外部ライブラリを処理してスタンドアロンのＨＬＬ前処理コントラクト（すなわち、ソースコード）を生成するコンピュータ実行可能プログラムでもよい。
【００２８】
外部ライブラリは、呼び出しによりＨＬＬコントラクトにより利用される予め書かれたサブルーチン、関数、クラス、コンテナ、値、及び／又は変数型の集合でもよい。例えば、外部ライブラリを呼び出すことにより、ＨＬＬコントラクトは、そのライブラリの機能を、該機能自体を実装する必要なく得る。ＨＬＬ前処理コントラクトは、式及び演算子のセットを含んでもよい。演算子は、算術演算子（例えば、加算（＋）、乗算（＊）等）、比較演算子（例えば、未満（＜）、等値（＝＝）、以上（＞＝）等）、条件ステートメント（例えば、ｉｆ‐ｔｈｅｎ（？，：））、又は論理演算子（例えば、ＡＮＤ（＆＆）、ＯＲ（｜｜）、ＮＯＴ（！）、ＸＯＲ
【数２】
2021502636.tif 000004
等）を含んでもよい。いくつかの実施形態において、メイン関数（エントリポイント）は、予め定義された名前及びフォーマットを有する。
【００２９】
算術回路は、変数のセットにわたる有向非巡回グラフ（directed  acyclic  graph）ＤＡＧでもよい。ゼロの入次数（indegree）を有するＤＡＧのあらゆるノードは、変数（例えば、ｘｉ）を表現する入力ゲートでもよく、ＤＡＧのあらゆる他のノードは、合計ゲート（＋）又は積ゲート（×）でもよい。あらゆるゲート（ノード）は１の出次数（outdegree）を有し得るため、その基礎をなすグラフは有向ツリーであり得る。算術回路は、複雑さの２つの尺度、すなわちサイズと深さを有し得る。いくつかの例において、算術回路の「サイズ」は、算術回路内のゲート数に基づいてもよい。いくつかの例において、算術回路の「深さ」は、算術回路内の最長有向パスの長さに基づいてもよい。
算術回路が生成された後、それは縮小され得る。
【００３０】
本発明による、コンピュータにより実現される方法は、ソースコードの部分を処理して（実行可能な）算術回路を生成するステップを含み得る。ソースコードは、高水準プログラミング言語で書かれてもよく、算術回路は、ソースコード内に表されたいくつかの機能又は計算を表現するように構成された１つ以上の算術ゲートを含んでもよい。
これは、ＨＬＬソースコードを算術回路に変換しない従来技術で知られるコンパイラ及び解釈とは対照的である。
算術回路は、プロセッサ上で実行されてもよい。この回路は、ブロックチェーントランザクションに提供されてもよい。
【００３１】
これは、計算又は論理回路の検証を教示し、かつ／あるいは（ゼロ知識）証明の出力に至る従来技術の開示とは対照的である。例えば、Pinocchioシステムは、一般的な計算を検証するゼロ知識証明を生成する。「Communications  of  the  ACM」、Vol.59、No.2、2016  Parno  Bらの「Pinocchio:  Nearly  Practical  Verifiable  Computations」、103-112（Parno）。ゆえに、Pinocchioなどの従来技術のいずれかの検証システムが検証の目的で本発明と共に使用でき、本発明は、従来技術を超える機能性及び結果を提供する。
【００３２】
したがって、本発明は、計算を表現及び／又は提供するマシン実行可能出力を提供する。これは、次いで検証され得る。これは、例えば、検証スクリプトをコンパイルして計算を実行するように構成された（別個の）プログラムを立証する、ゆえに２パートの処理を含むPinocchioシステムとは対照的である。代わりに、本発明は、１パートのアプローチ、すなわち算術回路への高水準計算それ自体のコンパイルを使用する。ゆえに、本発明は、上記従来技術とはかなり異なるアプローチを使用して異なる技術的問題を解決する。
【００３３】
好ましくは、ソースコードはスマートコントラクトである。ソースコードは、上記のように前処理されてもよい。
【００３４】
好ましくは、処理するステップは、ソースコード内に提供される１つ以上の定数を評価するサブステップを含む。これは、ブール及び／又は算術演算子を含む１つ以上の式を提供し得る。
本方法は、算術回路を使用してハードウェア及び／又はソフトウェア回路を提供するステップをさらに含んでもよい。算術回路は、算術ゲートに接続されたｎビットワイヤを含んでもよい。算術回路は、アーキテクチャ非依存である。すなわち、それは、特定のハードウェア又はソフトウェアのアーキテクチャ又はプラットフォームでの動作又は使用に対して配置されない。それは、仮想マシンの使用を必要としない。これは、アーキテクチャ特有であるか又はＶＭの使用を必要とする従来技術のコンパイラ及びインタプリタとは対照的である。
【００３５】
本方法は、ソースコードを前処理して１つ以上の定数を決定するステップをさらに含んでもよい。前処理するステップは、
コメントを削除するステップ、
ヘッダファイルからソースファイルにヘッダ宣言をインポートするステップ、
複数のソースファイルをマージするステップ、
ディレクティブ及びマクロを解決し、あるいは評価するステップ
のうち１つ以上を含んでもよい。
【００３６】
本方法は、ソースコード内に宣言された全てのグローバル変数を検出するステップをさらに含んでもよく、グローバル変数は、関数、構造体若しくはクラス、定数、及び／又は実行のエントリポイントに関する。
本方法は、シンボル（識別子）のテーブルを生成して、ソースコード内に提供される各シンボル（すなわち、識別子）をソースコード内に提供される宣言情報に関連づけるステップをさらに含んでもよい。テーブル内のシンボルは、グローバル及び／又はローカルシンボルであり得る。
【００３７】
本方法は、１つ以上の入力変数に適用される論理及び／又は算術演算の組み合わせとして１つ以上のアウト変数を表す算術及び／又は論理式を結果としてもたらすソースコードの行ごとの（line-by-line）評価を実行するステップをさらに含んでもよい。
これは、型を復号するステップ、式を復号するステップ、式を評価するステップ、及び／又は上記機能により必要とされるデータ構造のためのメモリを割り振るステップをさらに含んでもよい。
【００３８】
本方法は、式の算術及び／又は論理演算を算術ゲートにマッピングするステップをさらに含んでもよい。マッピングするステップは、ワイヤ拡張を実行するサブステップ、及び／又はワイヤ圧縮を実行するサブステップを含んでもよい。
本方法は、算術回路を使用して、回路の記述を提供する多項式のセットを含む二次プログラムを生成するステップをさらに含んでもよい。この方法は、１つ以上の入力を使用する２次プログラムの実行のために２次プログラムをエンティティに提供するステップをさらに含んでもよい。
【００３９】
本発明は、上述の方法ステップのいずれかを実現又は実行するように配置されたシステムをさらに提供し得る。システムは、ソースコードの処理を実行するように配置された翻訳又は変換コンポーネント（すなわち、インタプリタ／コンパイラ）を含み得る。（ゼロ知識）証明の生成のためのコンパイラが当該分野において知られているが（例えば、上述の「Pinocchio:  Nearly  Practical  Verifiable  Computations」（Parno）を参照する）、これらは本発明のように算術回路へコンパイルしない。本発明は、回答のプルーフ又は検証でなく回答を生成する。
【００４０】
コンピュータにより実現されるシステムが、
プロセッサと、
プロセッサによる実行の結果として、当該システムに本願で記載又は請求される発明／方法の１つ以上の実施形態のうち任意の実施形態のコンピュータにより実現される方法を実行させる実行可能命令を含むメモリと、を含む。該命令は、ソースコードの処理を実行するように構成された翻訳又は変換コンポーネント（すなわち、インタプリタ／コンパイラ）を提供する命令を含み得る。
【００４１】
非一時的コンピュータ読取可能記憶媒体が、コンピュータシステムのプロセッサにより実行された結果としてコンピュータシステムに本願で記載又は請求される発明／方法の１つ以上の実施形態を少なくとも実行させる実行可能命令を記憶する。
【図面の簡単な説明】
【００４２】
本発明のこれら及び他の態様が、本明細書に記載した実施形態から明らかであり、それらを参照して明らかにされるであろう。次に、本発明の一実施形態が、単なる例として、添付の図面を参照して説明される。
【図１】本発明の例示的な使用及び実施形態に関与する検証可能な計算及びアクタのプロトコルを示す。これらのアクタは、クライアント、ワーカ（「証明者」としても知られる）、及び検証者である。
【図２】本発明の一実施形態によるＤＳＬコントラクトから二次算術プログラム（ＱＡＰ）への翻訳処理を示す。
【図３】本発明の一実施形態による算術回路の一例を示す。
【図４】本発明の一実施形態による回路表現を含むパケット（ヘッダ＋ボディ）の高水準記述を示す。
【図５】以下で説明される例のとおり「Check  if  variable  <a>  is  even」のステートメントを表現する４ビットワイヤエキスパンダの一実装を示す。
【図６】本発明の一例示的な実装によるビルディングブロックを示し、このビルディングブロックは条件ステートメントを実現する。
【図７】本発明の一実施形態による、定数生成器モジュールが算術回路により使用される定数の作成をどのように担うかを示す。使用される例では、３つの定数（Ｃ１、Ｃ２、及びＣ３）に加えてデフォルトのイチ（１）及びゼロ（０）の値が生成される。
【図８】種々の実施形態が実現され得るコンピューティング環境を示す概略図である。
【発明を実施するための形態】
【００４３】
［概要］
次に、一実施形態により、本発明がどのように動作実現され得るかの例示を提供する。この例では、高水準言語コントラクト（例えば、Ｃ／Ｃ＋＋言語）を算術ゲートを含む回路に変換するように構成されたインタプリタの可能な実装について説明する。しかしながら、本発明は、他のＨＬＬ言語を翻訳するように構成されてもよい。この変換を容易にするために、特定の構造又はビルディングブロック（building  blocks）が使用可能である。１つ以上の実施形態において、この表現は、分散された検証可能な計算を提供することができる包括的なパイプラインの構築の最初のステップとみなすことができる。
【００４４】
この例で提示されるビルディングブロックは、本発明の実施形態により取り扱われる全ての可能な高水準言語構造の網羅的なリストであることは意図されない。さらに、提示される例の代替的な実装が提供され得る。これらは当業者のスコープの範囲内に入る。
【００４５】
次に、本発明の一例示的な実施形態を提供する。ただし、これは、本発明が使用され得る適用の一例であることに留意することが重要である。当業者は、本発明が他の文脈及び適用において有利に使用され得ることを理解するであろう。本発明は、スマートコントラクト又は金融商品に関する使用に限定されない。
【００４６】
［本発明の例示的な実施形態及び例示的なユースケース］
例えば、ユーザがドメイン固有言語（ＤＳＬ）を使用して金融商品のコントラクトを生成することを可能にするプロトコルを考える。ひとたびコントラクトが生成されると、その実行は信頼されていないパーティ（「ワーカ（workers）」又は「証明者」と呼ばれる）にアウトソーシングでき、その正しさはパブリックに検証できる。プロトコルは、
・完全性、すなわち、正当な検証者（honest  verifier）はプロトコルが正しく守られる場合に出力の有効性を確信する
・健全性、すなわち、不正な（cheating）証明者は出力の真正性（authenticity）について正当な検証者に確信させることができない
・ゼロ知識性、すなわち、不正な検証者は出力の有効性以外何も習得しない
を確保する暗号プリミティブを利用する。
【００４７】
プロトコルの主な利点は以下のとおりである。
・参加者間の通信が要求されないため、中間者攻撃が防止される
・ブロックチェーン技術の使用に起因して、悪意のあるノードがデータを改ざんすることが困難になる。
・信頼されたハードウェアデバイスなどの信頼されたサードパーティが回避される。
・コントラクトの立証がコードの再実行を意味しない。計算は、ネットワーク内のあらゆるノードにより複製されるわけではない。代わりに、正当な実行のプルーフがパブリックブロックチェーンに記憶され、立証目的にのみ使用される。
【００４８】
このようなシステムは、種々のタイプのタスク及び製品に対応する種々のタイプのスマートコントラクトを処理することができ、金融の適用又は使用に限定されない。その非中央集権的及び分散された性質に起因して、（ビットコイン）ブロックチェーンは、２つ以上のパーティ間の合意を解決するのに十分適した環境を提供する。
【００４９】
このようなシステムは、非中央集権的な暗号通貨システムにおいてプログラマビリティを提供し、容易にする必要がある。しかしながら、当技術分野では、スマートコントラクトプログラミングはエラーを起こしやすい処理であることが認識されている。Delmolino,  K.ら（2015）のStep  by  Step  Towards  Creating  a  Safe  Smart  Contract:  Lessons  and  Insights  from  a  Cryptocurrency  Lab、及びJuels,  A.ら（2013）のThe  Ring  of  Gyges:  Using  Smart  Contracts  for  Crimeを参照する。
【００５０】
したがって、スマートコントラクトをプログラマにより書き込む及び読み取ることをより容易にするＤＳＬを使用することができ、それによりエラーを低減させ、プログラミング処理の間の時間、労力、コスト、及びリソースを低減させることは有利であろう。理想的には、専門家でないプログラマが、いかなる暗号も実装する必要なくコントラクトを書くことができるであろう。代わりに、コンパイラ／インタプリタが、ソースコードをユーザとブロックチェーンとの間の暗号プロトコルに自動的にコンパイルする。これらは、本発明により解決される技術的問題の内にある。このような利点は、プルーフの検証及び生成に関する従来技術の手法では提供されない。
【００５１】
このフレームワークは、最先端の暗号的に検証可能な計算を使用し（Gennaro,  R.ら（2013）のQuadratic  Span  Programs  and  Succint  NIZKs  without  PCPsを参照する）、正しい関数評価を確保する。すなわち、機密情報を取得した敵対者は、検証可能な計算の使用のおかげで結果を操作することができない。このモデルは、ブロックチェーン技術を使用してプルーフオブコレクトネスを記憶し、「構築による正しさ（correct-by-construction）」の暗号アプローチをスマートコントラクトと組み合わせる。
【００５２】
この例では、高水準言語コントラクト（例えば、Ｃ／Ｃ＋＋言語）を算術ゲートを含む回路に変換できる翻訳コンポーネントの実装に焦点を合わせる。結果として生じる回路は、（検証目的のプルーフとは対照的に）ＨＬＬソースコードのマシン実行可能表現である。この変換を容易にするために、特定の構造又はビルディングブロックが使用される。例において、本発明が使用されて、分散された検証可能な計算システムを実現するように構成されたパイプラインの構築の最初のステップを提供することができる。しかしながら、本発明はこのユースケースに限定されず、より広い範囲の適用及び文脈で実施するために使用できることを再度指摘することに留意する。
【００５３】
例示的な実装を説明するために、検証可能な計算のためのフレームワークの概要を提供し、続いて、本発明によるスマートコントラクトの回路表現の導入を提供する。
【００５４】
［例示的な使用：検証可能な計算：フレームワーク］
問題文。クライアントは、計算Ｐ及び入力ｘの仕様を信頼されていない証明者（ワーカ）に送信する。ワーカは出力ｙを計算し、それをクライアントに返す。ｙ＝Ｐ（ｘ）の場合、正しい証明者は正しさの証明書を生成し、ｙの正しさを（クライアントだけでなく）誰にでも確信させることができるべきである。そうでない場合、検証者は高い確率でｙを拒絶するべきである。
【００５５】
プロトコルは、検証者にとってローカルでＰ（ｘ）を実行するより安価であるべきであり、あるいはプロトコルは、検証者が自身で実行できない計算Ｐを取り扱うべきである。さらに、ワーカの挙動の正しさについての仮定は必要とされない。
【００５６】
データアクセス。システムに、２つの区別可能な非中央集権的なデータベースが存在する。（ｉ）ＤＨＴ  ‐  オフチェーンデータがＤＨＴに記憶される。データはノードにわたり十分にランダム化され、高い可用性を確保するように複製される。（ｉｉ）公開台帳  ‐  正しい実行のプルーフがブロックチェーンに記憶され、監査されることが可能である。
【００５７】
プロトコル。プロトコルにより必要とされるステップを図１に示す。計算Ｐは回路Ｃにより表現される。クライアントが入力ｘを供給し、ワーカが入力ｘに対して回路を実行し、出力がｙであると主張する。証明者は、｛Ｃ，ｘ，ｙ｝に対する有効なトランスクリプトを取得することが期待される。｛Ｃ，ｘ，ｙ｝に対する有効なトランスクリプトは、以下のような回路ワイヤへの値の割り当てである。
・入力ワイヤに割り当てられる値はｘのものである
・中間値はＣにおける各ゲートの正しいオペレーションに対応する
・出力ワイヤに割り当てられる値はｙである
主張された出力が正しくない、すなわちｙ≠Ｐ（ｘ）の場合、｛Ｃ，ｘ，ｙ｝に対する有効なトランスクリプトは存在しない。
【００５８】
セットアップフェーズは、正確なセマンティクスを有するフォーマルな言語でコントラクトを書くことを含む。本発明によれば、インタプリタは、入力としてソースコードを取り込み、体
【数３】
2021502636.tif 000005
からの値を搬送して加算及び乗算ゲートに接続するワイヤを含む算術回路Ｃを生成する。いくつかの実施形態において、英国特許出願第1718505.9号に記載されているような算術回路最適化手法が利用されて、スマートコントラクトの結果の決定の間に必要な必要とされるリソースを低減させてもよい。
【００５９】
回路Ｃから、システムは２次プログラムＱを生成し、すなわち、Ｑは、元の回路Ｃの完全な記述を提供する多項式のセットを含む。次いで、全ての証明者及び検証者により使用されるパブリックパラメータが生成される。
【００６０】
公開評価鍵ＥＫ及び公開検証鍵ＶＫが、クライアントにより選択された秘密値ｓを使用して導出される。ワーカは、これらの公開情報を使用して、特定の入力ｘに対する計算を評価する。出力ｙ、内部回路ワイヤの値、及びＥＫが使用されて、プルーフオブコレクトネスπを生成する。プルーフπはブロックチェーンに記憶され、証明者にこれらのエンティティの各々と別個に対話するよう求めることなく複数のパーティにより検証されることが可能である。
【００６１】
全てのビットコインノードは、公開検証鍵ＶＫ及びプルーフπを使用して支払トランザクションを立証し、ゆえにコントラクトを立証することができる。
【００６２】
［スマートコントラクト及び回路表現］
ドメイン固有言語（ＤＳＬ）がスマートコントラクトを実現するために必要とされ、例えばアクタラスモデリング言語（Actulus  Modeling  Language、ＡＭＬ）、デジタル資産モデリング言語（Digital  Asset  Modeling  Language、ＤＡＭＬ）、金融商品マークアップ言語（Financial  Products  Markup  Language、ＦｐＭＬ）などであるが、例示の簡潔さのため、本明細書では、高水準言語（High  Level  Language、ＨＬＬ）、Ｃなどの、より大きい範囲の型、演算子、及び構造を提供することができるより一般的な言語の使用について説明する。しかしながら、本発明は、専用ツールを使用して異なるＤＳＬ言語をＣ（又は別のＨＬＬ）に変換するように構成可能である。
【００６３】
本明細書で使用される例において、インタプリタは、Ｃで書かれたソースコードを処理する。本発明は、他の高水準言語（「汎用言語」（ＧＰＬ）とも呼ばれ得る）と共に動作するように適合可能である。汎用プログラミング言語の例には、Ａｄａ、ＡＬＧＯＬ、アセンブリ言語、ＢＡＳＩＣ、Ｂｏｏ、Ｃ、Ｃ＋＋、Ｃ＃、Ｃｌｏｊｕｒｅ、ＣＯＢＯＬ、Ｃｒｙｓｔａｌ、Ｄ、Ｄａｒｔ、Ｅｌｉｘｉｒ、Ｅｒｌａｎｇ、Ｆ＃、Ｆｏｒｔｒａｎ、Ｇｏ、Ｈａｒｂｏｕｒ、Ｈａｓｋｅｌｌ、Ｉｄｒｉｓ、Ｊａｖａ、ＪａｖａＳｃｒｉｐｔ（登録商標）、Ｊｕｌｉａ、Ｌｉｓｐ、Ｌｕａ、Ｍｏｄｕｌａ‐２、ＮＰＬ、Ｏｂｅｒｏｎ、Ｏｂｊｅｃｔｉｖｅ‐Ｃ、Ｐａｓｃａｌ、Ｐｅｒｌ、ＰＨＰ、Ｐｉｋｅ、ＰＬ／Ｉ、Ｐｙｔｈｏｎ、Ｒｉｎｇ、ＲＰＧ、Ｒｕｂｙ、Ｒｕｓｔ、Ｓｃａｌａ、Ｓｉｍｕｌａ、Ｓｗｉｆｔ、及びＴｃｌが含まれる。
【００６４】
高水準言語の論理回路への翻訳のための包括的なパイプラインを図２に示す。本発明に従い、図２の点線ボックスで強調されたモジュールに焦点を合わせる。
・コントラクト及び必要な外部ライブラリを含む高水準Ｃプログラムが一緒にリンクされ、スタンドアロンの前処理コントラクトを作成する。この段階では、Ｃプリコンパイラが、全ての必要なリソースが利用可能であることのチェックを担う。プリプロセッサディレクティブがさらに評価される。
・定数式が評価され、全てのシンボルが登録される。結果は、加算（＋）、乗算（＊）、比較（＜）、等値（＝＝）、条件ステートメント（？，：）、論理演算子（ａｎｄ、ｏｒ、ｎｏｔ、ｘｏｒ）などのＣライクな演算子の式のセットである。予め定義された名前及びフォーマットを有するメイン関数が必要とされる。算術回路（図３参照）は、基本算術ゲート、例えば加算及び乗算に接続されたｎビットのワイヤを有するシンボルを表現することにより構築される。
・二次算術プログラム（ＱＡＰ）における多項式は、Gennaro,  R.ら（2013）のQuadratic  Span  Programs  and  Succinct  NIZKs  Without  PCPsで紹介されているように、算術回路のルートにおけるその評価の観点で定義される。
【００６５】
図３は算術回路の一例を示す。各ワイヤは体Ｆからのものであり、全ての演算は体Ｆ上で実行される。この回路は、ｙ＝ｘ１＋ｘ２・ｘ３・（ｘ３＋ｘ４）を計算する。回路の最終出力は合計であるため、さらなる乗算ゲート（定数イチを乗算する）が必要とされる。
【００６６】
［Ｃ言語インタプリタ］
本発明の一例示的な実施形態に従い、次に、プリプロセッサディレクティブ、条件文、算術及びビット単位ブール演算子、グローバル関数を含むＣプログラミング言語に対して定義された命令のサブセットを認識することができるインタプリタについて説明する。当業者に容易に理解されるように、配列及び構造体のサポートが付加的な論理なしにさらに提供され得る。
【００６７】
インタプリタは、以下の「算術プリミティブの生成」と題されたセクションで提示される乗算、加算、及び特定のビルディングブロックを使用して、式を算術ゲート言語へ強化する。各ワイヤは、指定されたビット幅を有する。１ビット幅の場合、ワイヤは二値変数を表現する。
【００６８】
［ブロックチェーンでの実装のためのＣライクなプログラムの算術的強化］
次に、Ｃソースコードで表された機能を表現する算術回路の構築の処理について詳述する。処理の各段階で、予期されない挙動（例えば、欠落したシンボル、誤ったシンタックス、又は未知の演算子）は、適切なコードエラーと共にプログラム実行の即時終了を結果としてもたらす。
【００６９】
［前処理］
図２に示すように、スマートコントラクトは複数のファイル及びライブラリから構成され得る。プロトコルの最初のステップは、コントラクトを実現するために必要とされる命令のフルセットを含む単一のソースファイルの作成を含む。個々のサブステップが以下のように列挙され得る。
・全てのコメントが除去される。
・ヘッダ宣言がヘッダファイルからソースファイルにインポートされる。
・全てのソースファイルがマージされる。
・プリプロセッサＣディレクティブ及びマクロが解決され、あるいは評価される。これらは、#defineディレクティブ及び条件付き#ifdefディレクティブを含む。
【００７０】
このステップの終わりに、全てのプリプロセッサ定数の実際の値が分からなければならない。ソースコードで使用される変数の値は、コントラクトの入力の値のみに依存しなければならない。さらに、ソースコード中のエントリポイントの宣言は、以下のシンタックスを有さなければならない。
【表１】
2021502636.tif 000006
【００７１】
型inputType及びoutputTypeは、ユーザにより定義される。以下のソースコードボックスは、２つの符号なし整数入力間の単一の合計演算を含むスマートコントラクトの簡素な例を示す。
【表２】
2021502636.tif 000007
【００７２】
出力は、特定のコントラクトに依存して異なる型の変数で表現できる。上記の場合、単一の出力が、算術演算の結果に単に接続される。
【００７３】
［整数及び実数］
この例示的な実施形態において、簡潔さのため、（符号付き又は符号なし）整数間の演算のみが利用可能であると仮定する。この仮定が除去される場合、回路ビルディングブロック（「算術プリミティブの生成」のセクションを参照）は拡大されなければならない。したがって、実数間の演算は、整数間の演算に変換されなければならない。以下のコントラクトの部分について考える。
「従業員の平均給与が３２．５Ｋドルより高いかをチェックする」
【００７４】
このステートメントは、平均値を計算するために（Ｎ人の従業員による）除算を必要とする。しかしながら、このステートメントは、以下の整数間の式に変換できる。
【数４】
2021502636.tif 000008
ここで、ｓｉは第ｉの従業員の給与を表現する。
【００７５】
［シンボルのグローバルテーブルの作成］
コンピュータ科学において、シンボルのテーブルは、ソースコード中の各識別子（シンボル）をその宣言に関する情報に関連づけるためにコンパイラ／インタプリタにより使用されるデータ構造である。この第２のステップでは、インタプリタは、ソースファイル内に宣言された全てのグローバルシンボルを検出する。
・関数
・構造体（又はクラス）
注：クラス（Ｃ＋＋などのＯＯＰ言語）の使用は、public、protected、及びprivateセクションのスコープをチェックするためのさらなる論理を要する。
・定数
（グローバル変数も許可されるが、推奨されない。contract（．．．）関数のスコープは、独立したブラックボックスとして扱われるべきである。その挙動は、外部変数に依存すべきではない。）
【００７６】
これらのシンボルの各々に対して、それらの識別子の内部宣言を表現するローカルシンボルの階層が構築される。この段階の終わりに、テーブル内の各グローバルシンボル（名前、型、及び値）は、さらなる処理のために直接アドレス指定されてもよい。
【００７７】
［コントラクトのエントリポイントの検出］
グローバルシンボルの１つは、コントラクト（「前処理」セクションのContract関数）のエントリポイントでなければならない。そのパラメータの名前、数、及び型は、予期されたシンタックスに対してチェックされる。全ての入力構造がコントラクト内で使用され、全ての出力構造がコントラクトのいくつかの部分にリンクされることをチェックするのに、さらなる論理が存在してもよい。
【００７８】
［行ごとの評価］
各コード行は独立して分析される。識別子の内部宣言を表現するローカルシンボルは、シンボルのグローバルテーブルの階層に含まれる。より詳細には、この段階は以下のタスクを担う。
・構造体及び配列、基本型（ブール、整数等）及びポインタの宣言を含む、型の復号。
・式の復号、例えば、単項又は二項演算、定数、識別子、データ構造、及び関数呼び出し。
・式の評価、すなわち、入力値に依存しない（数値）式の評価。
・メモリ割り振り、すなわち、コントラクト機能により必要とされるデータ構造のための一時的なストレージ割り振り。
【００７９】
この段階は、空間的（すなわち、使用されるメモリ）及び時間的（すなわち、演算子の優先順位）の観点から算術式の全てのステートメントをリンクする。したがって、各出力変数は、入力変数に適用される論理及び算術演算の組み合わせとして表される。
【００８０】
［陽的演算式の作成］
「行ごと」セクションで定義されたデータ構造を使用し、一般的な算術／論理式ｅは、以下のシンタックスに従って陽的（explicit）形式で表現されるように折り畳まれる。
ＯＰＮ（ＯＰＮ−１（．．．（ＯＰ１（ＯＰ０））．．．））
【００８１】
このシンタックスに従い、任意の演算子ＯＰｉ＋１が演算子ＯＰｉの後にｅに適用される。
【００８２】
例えば、次のコードを所与として、
【表３】
2021502636.tif 000009
陽的な式ｅは以下のとおり表現できる。
ｏｕｔ０＝（？（＜１５（ＡＤＤ（ＡＤＤ（ＡＤＤ  ｉｎ０  ｉｎ１）ｉｎ０）ｉｎ１））５０（ＭＵＬ（ＭＵＬ  ｉｎ０  ｉｎ１）ｉｎ１））
【００８３】
「算術プリミティブの生成」のセクションで説明されるように、式ｅは、コントラクト機能を表現するために必要な算術プリミティブを作成することに使用される。
【００８４】
［算術プリミティブの生成］
この段階で、インタプリタは、式ｅを生成するために使用される演算と、回路上でこれらの機能性を実現するために必要とされる構造との間の、１対１のマッピングを行う準備ができている。
【００８５】
回路を作成するために必要な重要なパラメータは、ビット幅ｎｂｉｔ、すなわち、符号付き（又は符号なし）整数を表現するために使用されるビット数である。異なるコンピュータアーキテクチャは、異なるｎｂｉｔ値により特徴づけられる。クライアントがワーカの好適なビット幅値を知らない場合、その値は任意に選択され、図４に示されるように、さらなる情報と共に回路のヘッダに指定される。（コンパイルが特定のターゲットアーキテクチャに対して実行されるのと同様に、ビット幅値を知ることは、回路のより効率的な実装及び実行を結果としてもたらし得る。）
【００８６】
バージョンフィールドは、回路内の特定のビルディングブロックを作成するために使用される特定のアルゴリズムに関する重要な情報を与える。例示的な実装では、符号付き整数の２の補数２進表現が選択された。
【００８７】
［加算及び乗算演算］
加算及び乗算演算は、回路内の加算及び乗算ゲートに１対１でマッピングされる。２つのｎビットワイヤ入力を所与として、加算ワイヤ出力はｎ＋１ビットを必要とし、乗算ワイヤ出力は２ｎビットを必要とする。例えば、２つのｎｂｉｔワイヤａ及びｂ間の乗算は以下のように表現できる。
ＭＵＬ［ｉｄａ  ｉｄｂ］ＴＯ［ｉｄｃ］
【００８８】
（回路内のあらゆる算術又はブールワイヤｘが、値ｉｄｘにより一義的に識別可能である。二値変数については、値ゼロからカウントを開始する。）結果ｃは、２ｎｂｉｔビットで自動的に表現される。
【００８９】
［ブール演算］
ブールゲートのフルセットは、算術ゲートを使用して計算できる。２つのブール値ａ及びｂを所与として、以下の等価が有効である。
・ＡＮＤ（ａ，ｂ）＝ａｂ
・ＮＡＮＤ（ａ，ｂ）＝１−ａｂ
・ＯＲ（ａ，ｂ）＝１−（１−ａ）（１−ｂ）
・ＮＯＲ（ａ，ｂ）＝（１−ａ）（１−ｂ）
・ＸＯＲ（ａ，ｂ）＝（１−ａ）ｂ＋（１−ｂ）ａ
【００９０】
ＸＯＲ演算子以外、各ブールゲートは１つの乗算しか必要としない。全ての算術演算が１ビット幅ワイヤで実行される。
【００９１】
ｎビット幅入力に対するビット単位ブール演算は、ｎ個の１ビット乗算（ＡＮＤに対して）又は加算（ＯＲに対して）を必要とする。最下位（least  significative）出力ビットから始めて、次いで各要素が２を乗算され、次の要素に加算されて、結果として生じるｎビット整数値を構築する（「ワイヤ圧縮」のセクションを参照）。
【００９２】
［ワイヤ拡張］
ワイヤ拡張は、通常、算術ワイヤａをｎａビット出力ワイヤに翻訳するために使用され、ｎａは、ａで表すことができる最大値の２を底とする対数である。例えば、以下のコントラクトの部分について考える。
「Check  if  variable  <a>  is  even」
【００９３】
ｎａ＝４の場合、このステートメントは、図５に示すようにワイヤ拡張を使用して実現される。ａ０がａの最下位ビットを表現すると仮定すると、ステートメントの出力はａ０自体に等しい。この回路ビルディングブロックは以下のように表現できる。
ＥＸＰＡＮＤ［ｉｄａ］ＴＯ［ｉｄａ３  ｉｄａ２  ｉｄａ１  ｉｄａ０］
【００９４】
回路をより詳細に見ると、ａの１ビットのみがさらなる処理に必要とされ、残りの１ビットワイヤは除去できることが明らかである。インタプリタは、コントラクトの残りで使用される個々の１ビットワイヤのみを生成してもよい。図５は、「Check  if  variable  <a>  is  even」のステートメントを表現する４ビットワイヤエキスパンダの一実装を示す。
【００９５】
インタプリタは、最適化されたワイヤエキスパンダに特定のシンタックスを適用する。
ＥＸＰＡＮＤ［ｉｄａ］ＴＯ［０−＞ｉｄａ０］
【００９６】
すなわち、最下位１ビットワイヤ（すなわち、識別子番号ゼロ）のみが取り込まれ、それに識別子ｉｄａ０が割り当てられる。ｎａが大きいほど、最適化はより効果的であり得る。（この文脈では、最適化は、算術回路を表現するために使用される低水準ディレクティブを記憶又は伝送するための空間を節減する可能性として定義される。）
【００９７】
［ワイヤ圧縮］
ワイヤ圧縮は、１ビットワイヤａｉをｎａビット出力ワイヤに結合して戻すために使用される。
【数５】
2021502636.tif 000010
【００９８】
このビルディングブロックは定数による加算と乗算で構成され、したがってＱＡＰ多項式のサイズは影響を受けない（Genaro  R.ら（2013）のQuadratic  Span  Programs  and  Succinct  NIZKs  With  PCPsを参照）。ｎａ＝２５６であり、範囲［ｉｄａ０，ｉｄａ２５５］の識別子が連続していると仮定すると、このビルディングブロックを表現するための最適化された方法は以下のとおりである。
ＣＯＭＰＲＥＳＳ［ｉｄａ０：ｉｄａ２５５］ＴＯ［ｉｄａ］
【００９９】
次いで、結果として生じるワイヤａはｉｄａにより識別される。
【０１００】
［否定演算］
否定演算は２つの変数を比較するために必要であり、なぜならば、それらの差が値ゼロと比較できるためである。ｎビットワイヤの否定は、定数−１による乗算として実現できる。この定数は、以下のように表現されなければならない。
【数６】
2021502636.tif 000011
【０１０１】
［ゼロ相当演算（Equal  To  Zero  Operation）］
ｎｂｉｔビットワイヤａに対するこのビルディングブロックは、以下のように実現できる。
・ｎｂｉｔビットに対するワイヤ拡張（ａ０，  ．．．，ａｎｂｉｔ−１）
・各１ビットワイヤを否定する（ａｉ→ｂｉ）
・結果として生じるｂｉワイヤを乗算する、すなわち、
【数７】
2021502636.tif 000012
【０１０２】
したがって、ａ＝０の場合及びその場合に限り、１ビット変数ｃ＝１である。
【０１０３】
［ゼロ比較演算（Compare  To  Zero  Operation）］
「より大きい」演算は、簡素な等式ルールを使用して「より小さい」演算に変形できる。２の補数表現において、この演算は、２つの符号付き整数間の差が正か又は負か（あるいは、「以下」演算の場合にはゼロに等しいか）をチェックすることに対応する。差ｃ＝ａ−ｂの符号の判別は、２進表現における最上位（most  significative）ビットｘにより与えられる。負の数はｘ＝１により特徴づけられ、正の数はｘ＝０により特徴づけられる。
ＥＸＰＡＮＤ［ｉｄｃ］ＴＯ［ｎｂｉｔ−１  −＞  ｘ］
【０１０４】
比較のタイプ（正対負）に依存して、２進値ｘは否定される必要がある。
【０１０５】
［条件ステートメント］
高水準言語の条件ステートメントは、次の形式で表すことができる。
ＩＦ（Ｓｃ）  Ｓａ  ＥＬＳＥ  Ｓｂ
【０１０６】
ステートメントＳｃはコントラクトの入力に依存するため、分岐Ｓａ及びＳｂの双方が回路に実装されなければならない。論理フローを図６に示す。ステートメントＳｃの（二値）出力に依存して、ステートメントＳａ又はステートメントＳｂが実行される。２進演算ｘ＋１は、ｘを否定するために使用される。
【０１０７】
［定数の生成］
定数値は回路の入力ワイヤに依存しない。mul-by-const-c形式の専用の単項乗算ゲートを使用し、以下のさらなる回路を提供して、コントラクトにより必要とされる定数値を生成する。
・定数ゼロは、入力ワイヤに０を乗算することにより計算される。
（コントラクトは少なくとも１つの入力を有さなければならない。したがって、識別子１の入力（例えば、図７のｉｎ１）が使用されて定数ゼロを生成することができる。）
・定数イチは、定数ゼロに１を加算することにより計算される。
・任意のさらなる定数ｃｉが、定数イチに対してmul-by-const-ciを使用することにより計算される。
【０１０８】
定数ゼロ及びイチは常に回路に追加されるため、ｋ個の任意の定数の実装はｋ＋２個のゲートを必要とする。この処理を図７に示す。本発明の一実施形態により提供される定数生成器（generator）モジュールは、算術回路により使用される定数の作成を担う。この例において、３つの定数（Ｃ１、Ｃ２、及びＣ３）に加えてデフォルトのイチ（１）及びゼロ（０）の値が生成される。
【０１０９】
定数は、２の補数の標準で規定される既知のビット幅を有する。
【０１１０】
次に、図８を参照し、本開示の少なくとも１つの実施形態を実施するために使用され得るコンピューティングデバイス２６００の例示的な簡略ブロック図が提供される。種々の実施形態において、コンピューティングデバイス２６００は、上で例示及び説明されたシステムのうち任意のものを実現するために使用されてもよい。例えば、コンピューティングデバイス２６００は、データサーバ、ウェブサーバ、ポータブルコンピューティングデバイス、パーソナルコンピュータ、又は任意の電子コンピューティングデバイスとしての使用に対して構成されてもよい。図８に示すように、コンピューティングデバイス２６００は、１つ以上のレベルのキャッシュメモリ及びメモリコントローラを有する１つ以上のプロセッサ（集合的に２６０２とラベル付けされている）を含み得、該プロセッサは、メインメモリ２６０８及び永続ストレージ２６１０を含むストレージサブシステム２６０６と通信するように構成され得る。メインメモリ２６０８は、図示のように、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）２６１８及び読取専用メモリ（ＲＯＭ）２６２０を含むことができる。ストレージサブシステム２６０６及びキャッシュメモリ２６０２は、本開示に記載されるトランザクション及びブロックに関連づけられた詳細などの情報の記憶のために使用され得る。プロセッサ２６０２は、本開示に記載される任意の実施形態のステップ又は機能を提供するために利用され得る。
【０１１１】
プロセッサ２６０２は、１つ以上のユーザインターフェース入力デバイス２６１２、１つ以上のユーザインターフェース出力デバイス２６１４、及びネットワークインターフェースサブシステム２６１６と通信することもできる。
【０１１２】
バスサブシステム２６０４は、コンピューティングデバイス２６００の種々のコンポーネント及びサブシステムが意図されたとおり互いに通信することを可能にする機構を提供し得る。バスサブシステム２６０４は単一のバスとして概略的に示されているが、バスサブシステムの代替的な実施形態が複数のバスを利用してもよい。
【０１１３】
ネットワークインターフェースサブシステム２６１６は、他のコンピューティングデバイス及びネットワークへのインターフェースを提供し得る。ネットワークインターフェースサブシステム２６１６は、他のシステムからデータを受信し、コンピューティングデバイス２６００から他のシステムにデータを送信するためのインターフェースとして機能してもよい。例えば、ネットワークインターフェースサブシステム２６１６は、データ技術者がデバイスをネットワークに接続することを可能にし得、それにより、データ技術者は、データセンタなどの遠隔地にいる間にデバイスにデータを送信し、デバイスからデータを受信することができ得る。
【０１１４】
ユーザインターフェース入力デバイス２６１２は、キーボードなどの１つ以上のユーザ入力デバイス；一体型マウス、トラックボール、タッチパッド、又はグラフィックスタブレットなどのポインティングデバイス；スキャナ；バーコードスキャナ；ディスプレイに組み込まれたタッチスクリーン；音声認識システム、マイクロフォンなどのオーディオ入力デバイス；及び他タイプの入力デバイスを含んでもよい。一般に、用語「入力デバイス」の使用は、情報をコンピューティングデバイス２６００に入力する全ての可能なタイプのデバイス及び機構を含むことが意図される。
【０１１５】
１つ以上のユーザインターフェース出力デバイス２６１４は、表示サブシステム、プリンタ、又はオーディオ出力デバイスなどの非視覚的ディスプレイ等を含んでもよい。表示サブシステムは、陰極線管（ＣＲＴ）、液晶ディスプレイ（ＬＣＤ）、発光ダイオード（ＬＥＤ）ディスプレイなどのフラットパネルデバイス、又は投影若しくは他の表示装置でもよい。一般に、用語「出力デバイス」の使用は、コンピューティングデバイス２６００から情報を出力する全ての可能なタイプのデバイス及び機構を含むことが意図される。１つ以上のユーザインターフェース出力デバイス２６１４が使用されて、例えば、ユーザインターフェースを提示し、説明された処理及びその変形を実行するアプリケーションとのユーザ対話を、そのような対話が適切であり得るときに容易にしてもよい。
【０１１６】
ストレージサブシステム２６０６は、本開示の少なくとも１つの実施形態の機能を提供し得る基本プログラミング及びデータ構造を記憶するコンピュータ読取可能記憶媒体を提供し得る。アプリケーション（プログラム、コードモジュール、命令）は、１つ以上のプロセッサにより実行されたとき、本開示の１つ以上の実施形態の機能を提供してもよく、ストレージサブシステム２６０６に記憶されてもよい。これらのアプリケーションモジュール又は命令は、１つ以上のプロセッサ２６０２により実行されてもよい。ストレージサブシステム２６０６は、本開示に従って使用されるデータを記憶するリポジトリをさらに提供してもよい。例えば、メインメモリ２６０８及びキャッシュメモリ２６０２は、プログラム及びデータの揮発性ストレージを提供することができる。永続ストレージ２６１０は、プログラム及びデータの永続的（不揮発性）ストレージを提供することができ、フラッシュメモリ、１つ以上のソリッドステートドライブ、１つ以上の磁気ハードディスクドライブ、関連するリムーバブルメディアを備えた１つ以上のフロッピーディスクドライブ、関連するリムーバブルメディアを備えた１つ以上の光学ドライブ（例えば、ＣＤ‐ＲＯＭ又はＤＶＤ又はＢｌｕｅ‐Ｒａｙ）ドライブ、及び他の同様の記憶媒体を含んでもよい。このようなプログラム及びデータには、本開示に記載される１つ以上の実施形態のステップを実行するプログラムと、本開示に記載されるトランザクション及びブロックに関連づけられたデータを含むことができる。
【０１１７】
コンピューティングデバイス２６００は、ポータブルコンピュータデバイス、タブレットコンピュータ、ワークステーション、又は以下に記載される任意の他のデバイスを含む種々のタイプのものでもよい。さらに、コンピューティングデバイス２６００は、１つ以上のポート（例えば、ＵＳＢ、ヘッドフォンジャック、ライトニングコネクタ等）を通じてコンピューティングデバイス２６００に接続され得る別のデバイスを含んでもよい。コンピューティングデバイス２６００に接続され得るデバイスは、光ファイバコネクタを受け入れるように構成された複数のポートを含んでもよい。したがって、このデバイスは、光信号を、処理のために、デバイスをコンピューティングデバイス２６００に接続するポートを通じて伝送され得る電気信号に変換するように構成されてもよい。コンピュータ及びネットワークの絶えず変化する性質に起因して、図８に示されるコンピューティングデバイス２６００の説明は、デバイスの好適な実施形態を例示する目的で特定の例としてのみ意図される。図８に示すシステムより多くの又は少ないコンポーネントを有する多くの他の構成が可能である。
【０１１８】
上述の実施形態は、発明を限定するのでなく例示しており、当業者は、別記の特許請求の範囲により定義される発明の範囲から逸脱することなく多くの代替的な実施形態を設計可能であることに留意されたい。特許請求の範囲においては、括弧内に付されたいかなる参照符号も、特許請求の範囲を限定するものと解釈されてはならない。語「含んでいる」及び「含む」などは、任意の請求項又は明細書全体に列挙されたもの以外の要素又はステップの存在を除外しない。本明細書において、「含む」は、「含める、又は、から構成される」ことを意味し、「含んでいる」は、「含めている、又は、から構成されている」ことを意味する。要素の単数の参照は、そのような要素の複数の参照を除外するものではなく、その逆もまた同様である。発明は、いくつかの区別可能な要素を含むハードウェアを用いて、及び適切にプログラムされたコンピュータを用いて実現されてもよい。いくつかの手段を列挙するデバイスクレームにおいては、これらの手段のうちいくつかは、１つの同じアイテムのハードウェアにより具現化されてもよい。特定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これらの手段の組み合わせが利するように使用できないことを示すものではない。
【０１１９】
本明細書で引用される刊行物、特許出願、及び特許を含む全ての参照文献は、各参照文献が参照により援用されるよう個々及び具体的に示され、かつその全体を本明細書に明示されているのと同程度、本明細書で参照により援用される。これには、英国特許出願番号第GB1719998.5号、第GB1718505.9号、第GB1720768.9号が含まれる。
【図１】
2021502636.tif 000013
【図２】
2021502636.tif 000014
【図３】
2021502636.tif 000015
【図４】
2021502636.tif 000016
【図５】
2021502636.tif 000017
【図６】
2021502636.tif 000018
【図７】
2021502636.tif 000019
【図８】
2021502636.tif 000020
【国際調査報告】
2021502636.tif 000021
2021502636.tif 000022