JP7361706B2 - ゼロ知識証明を可能にするためのコンピュータ実装されたシステム及び方法 - Google Patents

Description

この明細書は、概して、例えばブロックチェーンネットワークのノードなどのコンピュータプロセッサ又は一群のそのようなプロセッサにおける実装に適した、コンピュータ実装された方法及びシステムに関する。ステートメントの効率的なゼロ知識検証を可能にするプルーフを生成する改良された方法が提供される。当該方法は、双線形ペアリングフレンドリー楕円曲線の使用を必要としない既存の回路充足可能性のための離散対数ベースゼロ知識プルーフプロトコルに組み込むのに好適である。本発明は、以下に限られないが、特に、プルーフを作成するために証明者によって実行される方法、及びプルーフを検証するために検証者によって実行される、及び２人以上の参加者間の共同作業に適している。参加者間の安全なトラストレスでのやり取りを実現するために、当事者のうちの１つが、キー又はステートメントの知識を、そのステートメントを明らかにすることなく証明することができる。

本文書おいて、用語‘ブロックチェーン’は、全ての形態の電子的な、コンピュータベースの、分散型台帳を含む。これらは、合意に基づく（コンセンサスベースの）ブロックチェーン及びトランザクションチェーンの技術、許可された及び許可されていない台帳、共有台帳、並びにこれらの変形を含む。ブロックチェーン技術の最も広く知られている用途はビットコイン台帳であるが、他のブロックチェーン実装も提案及び開発されている。

ここでは、便宜及び説明のために、ビットコインを参照することがあるが、留意されたいことには、本発明は、ビットコインブロックチェーンとの使用に限定されず、それに代わるブロックチェーン実装及びプロトコルも本発明の範囲内にある。用語“ユーザ”は、ここでは、人間又はプロセッサベースのリソースを指す。ブロックチェーンは、トランザクションからなる複数のブロックで構成されるコンピュータベースの非中央集権的な分散システムとして実装されるピア・ツー・ピアの電子台帳である。

各トランザクションは、ブロックチェーンシステムにおける参加者間でのデジタル資産の管理の移転を符号化するデータ構造であり、少なくとも１つのインプットと少なくとも１つのアウトプットとを含む。各ブロックが、そのブロックが一緒にチェーン化される先行ブロックのハッシュを含むことで、その開始以前にそのブロックチェーンに書き込まれた全てのトランザクションの恒久的で変更不可能な記録を作り出す。トランザクションは、それらのインプット及びアウトプットに埋め込まれるスクリプトとして知られた小プログラムを含み、それらが、トランザクションのアウトプットが誰によってどのようにアクセスされ得るかを指定する。ビットコインプラットフォーム上では、これらのスクリプトは、スタックベースのスクリプト言語を使用して書かれる。

さらに、この文書では、算術回路を使用する既知のゼロ知識プルーフプロトコル及びシステムの構造を参照する。ブロックチェーンは、第三者仲裁又は第三者預託を必要とせずに２つの相互に信頼のない２つの当事者間で公正なやり取りすることの問題に対するソリューションを可能にする非中央集権化された許可なしでのグローバル機構を提供した。金銭的報のための又は例えばデジタルグッズなどの情報との交換での、データ又は情報の公正な交換は、ＺＫＣＰ（Zero-Knowledge Contingent Payments）（非特許文献２）として知られるトランザクションプロトコルにて具体化されている。ＺＫＣＰでは、支払が確認された場合にのみ、指定されたデータが売り手から買い手に転送され、買い手から売り手への支払は、この指定されたデータが売却の条件に従って有効である場合にのみ完了される。このようなプロトコルの詳細は知られている（非特許文献１）が、それは基本的に、ハッシュ時間ロック契約（hash-time-locked contract；ＨＴＬＣ）とゼロ知識プルーフとの組み合わせに基づいており、これは、暗号化された情報（‘デジタルグッズ’）が有効／正確であることと、この情報を解読する‘パスワード’が支払いを請求するためにブロックチェーン上で明らかにされなければならないデータであることとを同時に検証するものである。

ＺＫＣＰプロトコルの中心コンポーネントは、データ／情報の妥当性又は正確性、キーの妥当性、及び対応するハッシュ値に関する一連の従属ステートメントに対するゼロ知識プルーフである。このような複雑な複合ステートメントは、全般的な計算のために効率的なゼロ知識プルーフシステムを必要とし、突き詰めると、これは、１つの当事者が、秘密の入力を用いて任意のプログラムを走らせ、そして、秘密の入力又はプログラムの実行に関する情報を何ら明らかにすることなく、他の当事者に対し、プログラムが入力を有効であると認めて正しく実行されたことを証明することを可能にする。既知のＺＫＣＰの例では、採用された汎用ゼロ知識プルーフシステムは、Ｐｉｎｏｃｃｈｉｏプロトコル（非特許文献３）及びＣ＋＋ ｌｉｂｓｎａｒｋライブラリ（非特許文献４）で実装されるような、知識の簡潔な非対話型論証（succinct non-interactive arguments of knowledge；ＳＮＡＲＫ）フレームワークに基づいてきた。

ゼロ知識ＳＮＡＲＫ（ｚｋＳＮＡＲＫ）は、算術回路として表現可能な任意の計算の妥当性をゼロ知識で証明する方法を提供する。ｚｋＳＮＡＲＫの２つの主な特徴的性質は、それらが非対話的である（証明者が検証者に一手（１ムーブ）でプルーフを送る）こと及び簡潔である（プルーフが小さくて検証容易である）ことである。しかしながら、それらはかなりの制限を持つ：
－ プルーフ生成が、極めて計算的要求が大きいものである。
－ 証明キーが非常に大きく、回路サイズに比例する。
－ それらは、強力でテストされていない暗号仮定（すなわち、エクスポーネント仮定及びペアリングベース仮定の知識）に依存する。
－ 所与のプログラム（回路）に対して、それらは、設定パラメータを削除するために信頼されなければならない第三者によって共通参照文字列（common reference string；CRS）が計算されることを必要とする。設定パラメータの知識を持つ者が、偽のプルーフを作成する能力を持つ。

任意の暗号化楕円曲線キー操作を伴うステートメントを証明するｚｋＳＮＡＲＫの構築は、今日まで試みられていないが、仮説的に、何十万又は何百万ものゲートを備える算術回路で構成されることになり、結果として、プルーフ生成時間が数分かかることになるとともに、証明キーが数百メガバイトのサイズになるであろう。

技術的背景
対話型ゼロ知識プルーフのための基本システムは、証明者と検証者との間での何度かの通信ステップを伴うΣ（シグマ）プロトコルを使用することができる。通常、Σプロトコルは三手（３ムーブ）を必要とし、すなわち、証明者が最初のコミットメント（ａ）を検証者に送り、次いで、検証者がランダムチャレンジ（ｘ）で応答し、最後に証明者が最終応答すなわち‘ｏｐｅｎｉｎｇ’（ｚ）で応答する。そして、検証者が、トランスクリプト（ａ，ｘ，ｚ）に基づくステートメントを受け入れる又は拒絶する。

Σプロトコルは、証明者のみに知られている証拠（ｗ）の知識又は該証拠（ｗ）についてのステートメントを証明するために使用されることができる。コミットメントが、証拠に関するステートメントが真実であるという事実を除いて、証拠に関する情報すなわち秘密を検証者に明らかにしない場合、このプロトコルはゼロ知識である（非特許文献５）。

多くの対話型ゼロ知識プロトコルの中心は、算術回路の充足可能性に関して使用されるものであるコミットメント方式である。コミットメントによって、証明者が前もって秘密値にコミットし、その後、検証可能に秘密値を明らかにする（開く）ことが可能にされる。コミットメントスキームは、２つの主な性質を持つ。第一に、それは隠れていて、コミットメントが値を秘密のままにする。第二に、それは結びついていて、コミットメントは、元のコミットされた値に対してのみ開かれることができる。Ｐｅｄｅｒｓｅｎコミットメント（非特許文献５）スキームは、全ての当事者に知られた素数位数ｐの群Ｇの中のＧ及びＦという、２つの楕円曲線生成点を含む。コミットする者（コミッタ）が、素な整数Ｚ_ｐのフィールドでセキュアな乱数ｒを生成し、秘密値ｓへのコミットメント：
Ｃｏｍ（ｓ，ｒ）＝ｓ×Ｇ＋ｒ×Ｆ
を（楕円曲線加算／乗算によって）計算し、ここで、×は楕円曲線点乗算を表す。

コミッタは、後の段階で、値ｓ及びｒを提供することによって、コミットメントを完全に開くことができる（すなわち、それが検証されることができる）。コミッタはまた、秘密ｓ又は乱数ｒを明らかにすることなく、Σプロトコルの一部として特定のチャレンジ値に応答してコミットメントを開くことができる。

Ｐｅｄｅｒｓｅｎコミットメントは相加的に同形（ホモモルフィック）であり、すなわち、（楕円曲線上で）２つのコミットメントを加えることが、コミットされた値の和に対するコミットメントをもたらし、すなわち：
（ｓ_１×Ｇ＋ｒ_１×Ｆ）＋（ｓ_２×Ｇ＋ｒ_２×Ｆ）＝（ｓ_１＋ｓ_２）×Ｇ＋（ｒ_１＋ｒ_２）×Ｆ
である。

算術回路充足可能性の証明は‘ゼロ知識’で達成されることができる。（フィールドＺ_ｐ上の）算術回路は、ワイヤによって接続され（有向非循環グラフを形成する）算術ゲートの仮想構成であり、これは、任意の複雑な計算を実行することが可能であり、計算は整数演算に限定され、データ依存ループ又は可変状態を持たないものでなければならない。

各ゲートが、２つの入力ワイヤ及び１つの出力ワイヤを持ち、入力に対して乗算（×）又は加算（＋）演算を実行する。図１（ａ）は、左（ｗ_Ｌ）及び右（ｗ_Ｒ）のワイヤ入力と１つのワイヤ出力（ｗ_Ｏ）を有する乗算ゲートの概略図を示し、図１（ｂ）は、３つのゲート、３つの入力ワイヤ（ｗ_１，ｗ_２，ｗ_３）、１つの出力ワイヤ（ｗ_６）、及び２つの内部ワイヤ（ｗ_４，ｗ_５）を有する単純な算術回路の概略図を示している。

実際には、完全な回路は、外部（回路）入出力値を定めるフリー入力ワイヤ及びフリー出力ワイヤを持つ。合法的割り当て（リーガルアサインメント）は、ワイヤの値を、回路を満たすものとして定めるものであり、すなわち、各ワイヤが値を割り当てられ、各ゲートの出力が入力の積又は和に正確に対応する（すなわち、そのゲートは一貫性がある）。

所与の算術回路について、証明者は、まず（Ｐｅｄｅｒｓｅｎコミットメントを用いて）合法的割り当てにて各ワイヤ値にコミットし、次いで、ワイヤ値を証拠として、（並列に実行されることができる）回路内の各ゲートに対して検証者を持つ特別なΣプロトコルを、実行することによって、ワイヤ値を明らかにすることなく、回路に対する合法的割り当てを知っていることを検証者に対して証明することができる。これらのΣプロトコルは、後述するように、Ｐｅｄｅｒｓｅｎコミットメントの同形性を活用する。

（回路が満たされることの）プルーフを生成するために、最初に証明者は回路内の各ワイヤｗ_ｉ（ワイヤ数をｎとして、ｉ＝１，…，ｎ）に対するコミットメント：
Ｗ_ｉ＝Ｃｏｍ（ｗ_ｉ，ｒ_ｉ）
を生成し、これらを検証者に送る。

回路内の各‘加算’ゲート（図１（ｂ）に１つ示される）に対してΣ_ｚｅｒｏプロトコルが実行され、これは、ｗ_Ｌ＋ｗ_Ｒ－ｗ_Ｏ＝０であること（すなわち、入力ワイヤｗ_Ｌ及びｗ_Ｒが出力ワイヤｗ_Ｏに等しくて、加算ゲートが満たされること）を（ゼロ知識で）証明することを伴う。これは、以下のステップを含み、すなわち：
１． 証明者が、ゼロに対するコミットメント：Ｂ＝Ｃｏｍ（０，ｒ_Ｂ）を生成して検証者に送る。
２． 検証者が、ランダムチャレンジ値：ｘ←Ｚ_ｐで応答する。
３． 次いで、証明者が、開ける値（オープニング値）：ｚ＝ｘ（ｒ_Ｌ＋ｒ_Ｒ－ｒ_Ｏ）＋ｒ_Ｂを計算し、それを検証者に送る。
４． 検証者が、がｗ_Ｌ＋ｗ_Ｒ－ｗ_Ｏ＝０であることのプルーフとして、Ｃｏｍ（０，ｚ）＝ｘ×（Ｗ_Ｌ＋Ｗ_Ｒ－Ｗ_Ｏ）＋Ｂを証明する。
Ｂは、公開鍵と同様の曲線点を表す；Ｂ＝ｒ×Ｆ＋０×Ｇ
ｒ_Ｂは、対応するペアの秘密鍵を表す。

各‘乗算’ゲート（図１（ａ）に示される）に対してΣ_ｐｒｏｄプロトコルが実行され、これは、各乗算ゲートに対してｗ_Ｌ・ｗ_Ｒ＝ｗ_Ｏであること（すなわち、乗算ゲートが満たされること）を（ゼロ知識で）証明することを伴う。
１． 証明者が、５つのランダムバインディング値：ｔ_１，ｔ_２，ｔ_３，ｔ_４，ｔ_５←Ｚ_ｐを生成する。
２． 証明者が、Ｃ_１＝Ｃｏｍ（ｔ_１，ｔ_３）、Ｃ_２＝Ｃｏｍ（ｔ_２，ｔ_５）、Ｃ_３＝ｔ_１×Ｗ_Ｒ＋ｔ_４×Ｆを計算し、これらを検証者に送る。
３． 検証者が、ランダムチャレンジ値：ｘ←Ｚ_ｐで応答する。
４． 証明者が、開ける値：
ｅ_１＝ｗ_Ｌｘ＋ｔ_１
ｅ_２＝ｗ_Rｘ＋ｔ_２
ｚ_１＝ｒ_Ｌｘ＋ｔ_３
ｚ_２＝ｒ_Ｒｘ＋ｔ_５
ｚ_３＝（ｒ_Ｏ－ｗ_Ｌｒ_Ｒ）ｘ＋ｔ_４
を計算し、これらを検証者に送る。
５． そして、検証者が、ｗ_Ｌ・ｗ_Ｒ＝ｗ_Ｏであることの証明として、次式：
Ｃｏｍ（ｅ_１，ｚ_１）＝ｘ×Ｗ_Ｌ＋Ｃ_１
Ｃｏｍ（ｅ_２，ｚ_２）＝ｘ×Ｗ_Ｒ＋Ｃ_２
ｅ_１×Ｗ_Ｒ＋ｚ_３×Ｆ＝ｘ×Ｗ_Ｏ＋Ｃ_３
を検査する。

Σ_ｚｅｒｏプロトコル及びΣ_ｐｒｏｄプロトコルは、回路内の各ゲートの検証のために並列に動作されることができ、全てのゲートに対して同じ検証チャレンジ値（ｘ）を使用することができる。

一例として、図１（ｂ）の回路を考えると、合法的割り当て（すなわち、回路を満たすワイヤ値）を知っていることを証明者が検証者に対してゼロ知識で証明するために、証明者は、最初に、各ゲートに対するワイヤコミットメント（Ｗ_１，…，Ｗ_６）及びΣプロトコルコミットメント（すなわち、各加算ゲートに対して１つの追加コミットメント、各乗算ゲートに対して５つの追加コミットメント）を検証者に送る。

次いで、検証者がランダムチャレンジｘ←Ｚ_ｐで応答し、証明者が各ゲートの開ける値（各加算に１つ、各乗算に５つ）を計算して検証者に送り返す。そして、検証者が、Σプロトコルチェックを実行して、
ｗ_１・ｗ_２＝ｗ_４
ｗ_４・ｗ_５＝ｗ_６
ｗ_２＋ｗ_３＝ｗ_５
であり、故に、従って、コミットメントＷ_１，…，Ｗ_６がワイヤ値ｗ_１，…，ｗ_６を満たすことに対応する、ことを検証する。

証明者が、回路を満たすことに加えて、特定のワイヤが特定の値を持つことを示すことを望む場合、それらは、関連するワイヤに対するコミットメントを完全に開くことができる。この例では、検証者は更に、ｗ_６が特定の合法的な割り当てからの実際の出力であることを示すために、値ｗ_６及びｒ_６を検証者に送ることができる（そして、検証者は、Ｗ_６＝Ｃｏｍ（ｗ_６，ｒ_６）であることを検証することができる）。

図１（ｂ）の例は、簡単な回路である。実際には、有用な回路はもっと多くのゲートで構成される。特に関心があるのは、ＳＨＡ－２５６ハッシュ関数に関する算術回路であり、この回路は、証明者が、特定の（出力）値にハッシュするＳＨＡ－２５６関数へのプリイメージ（入力）を知っていることを、プリイメージを明らかにすることなく示すことを可能にする。ＳＨＡ－２５６アルゴリズムに関する回路の最も効率的な実装の１つは、２７，９０４個の算術ゲートからなる（Ｚｃａｓｈ２０１６）。すると、ＳＨＡ－２５６プリイメージの知識を証明することは、上のプロトコルの最初のコミットメント及びオープニングラウンドの両方で約５ＭＢのデータを送信することを必要とすることになり、証明者と検証者の両方に対して約２００，０００回の楕円曲線演算を必要とする（各々が数秒のプロセッサ時間を要する）。

算術回路充足可能性を証明するためについての並列Σプロトコルアプローチの性能を有意に改善するために開発された方法が幾つか存在する。既知のアプローチ（非特許文献５、非特許文献６）は、証明者から検証者に送られなければならないデータのサイズを実質的に減らす（すなわち、通信の複雑さを減らす）ために、回路ワイヤ値へのコミットメントをバッチにすることを伴う。これらの方法は、通信複雑性がＯ（ｎ）からＯ（√ｎ）又はＯ（ｌｏｇ（ｎ））に低減される証明システムを可能にする。

これまた、同じＳＨＡ回路の充足可能性を証明することについての比較として、そのプロトコル（非特許文献５）は、ほんの５ＫＢの証明キーサイズ及び１８０ｍｓの鍵生成時間を持つ。プルーフサイズは２４ＫＢであり、生成するのに約４秒かかり、そのプルーフはまた、検証するのにも約４秒かかる。

これらの方法については、採用されているメインベクトルバッチングプロトコルを以下のステップで説明することを除いて、ここで完全に説明することはしない。これは、通常のＰｅｄｅｒｓｅｎコミットメントと同じ性質に従うが、ｎ個の要素（ｍ＝ｍ_１，…，ｍ_ｎ）へのコミットメントが、単一のグループ要素を送信することを要するのみであり：
１． 証明者及び検証者が、グループ要素Ｆ←Ｇについて合意する。
２． 証明者が、ｎ個の乱数ｘ_１，…，ｘ_ｎ←Ｚ_ｐを生成する。
３． 証明者が、点Ｋ_ｉ＝ｘ_ｉ×Ｆ（ｆｏｒ ｉ＝１，…，ｎ）を計算する。これらの値は、検証者に送られる証明キーＰｒＫを形成する。
４． 証明者が、乱数：ｒ←Ｚ_ｐを生成する。
５． 証明者が、コミットメント：

を計算し、それを検証者に送信する。

Campanelli, Matteo, et al. "Zero-knowledge contingent payments revisited: Attacks and payments for services." Commun. ACM (2017). https://github.com/zcash-hackworks/pay-to-sudoku Parno, Bryan, et al. "Pinocchio: Nearly practical verifiable computation." Security and Privacy (SP), 2013 IEEE Symposium on. IEEE, 2013. https://github.com/scipr-lab/libsnark Bootle, Jonathan, et al. "Efficient zero-knowledge proof systems." Foundations of Security Analysis and Design VIII. Springer, Cham, 2015. 1-31. Groth, Jens. "Linear Algebra with Sub-linear Zero-Knowledge Arguments." CRYPTO. Vol. 5677. 2009. https://bitcointalk.org/index.php?topic=81865.msg901491#msg901491 Bootle, Jonathan, et al. "Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Berlin, Heidelberg, 2016. Standards for Efficient Cryptography (SEC) (Certicom Research, http://www.secg.org/sec2-v2.pd Bitcoin Developer Reference (http://bitcoin.org/en/developer-reference)

全体として、本発明は、ステートメントのゼロ知識証明又は検証を可能にするためのコンピュータ実装された方法にある。証明者は、ここでの方法を用いて、ステートメントに対する証拠を秘密にしながら、ステートメントが真であることを検証者に対して証明することができる。これらのステートメントは、算術回路充足可能性と公開鍵の妥当性に関する従属ステートメント（キーステートメントプルーフ）の両方を同時に必要とする複合ステートメントである。

ここでの方法は、例えば既存の離散対数ベースのゼロ知識プルーフプロトコルなどの、回路充足可能性に関する既知のプロトコルにおいて使用されることができる。当該方法は特に、双線形ペアリングフレンドリー楕円曲線の使用を必要としないプロトコルに適している。

当該方法においては、証明者が検証者に、所与の関数回路出力及び楕円曲線点に関するものであるステートメントを含む一組のデータを送信することを含み、関数回路入力は、対応する楕円曲線点乗数（ｓ）に等しい。該データは、ステートメントの回路についての個々のワイヤコミットメント及び／又はバッチにされたコミットメント、入力、及び出力を含む。証明者は、ステートメントで使用される楕円曲線又は各楕円曲線の仕様を、データに含めることができ、又は予め共有していることができる。そして、証明者は、検証者からのチャレンジに応答してオープニングを送信する。あるいは、証明者は更に証明キーを含める。

証明者から受信したデータを用いて、検証者は、回路が満たされると判定して、ステートメントを検証すること、故に、証明者がステートメントに対する証拠を保持していると決定することができる。楕円曲線点も計算されることができる。データを受信すると、検証者は、計算を通じて、データがステートメントに適合することを決定する。本発明は特に、ハッシュプリイメージ及び楕円曲線秘密鍵の等価性のゼロ知識証明に適する。

従って、本発明によれば、添付の特許請求の範囲に規定される方法及びシステムが提供される。

故に、証明者が、検証者に対して、ステートメントが真であることを、該ステートメントに対する証拠（Ｗ）を秘密にしたまま証明するものである、ステートメント（Ｓ）のゼロ知識証明又は検証を可能にするためのコンピュータ実装された方法を提供することが望ましい。この証明は、明示的な証明とすることができる。

証明者が、検証者に対して、ステートメントが真であることを、該ステートメントに対する証拠（ｗ）を秘密にしたまま証明するものである、ステートメント（Ｓ）のゼロ知識証明又は検証を可能にするためのコンピュータ実装された方法を提供することができ、当該方法は、
証明者が検証者に：
関数回路を実装して、所与の関数回路出力（ｈ）及び楕円曲線点（Ｐ）に対して、関数回路のワイヤへの関数回路入力（ｓ）が対応する楕円曲線点乗数（ｓ）に等しいかを判定する、ように構成されたｍ個のゲート及びｎ個のワイヤを有する算術回路によって表されるステートメント（Ｓ）と、
回路のワイヤについての個々のワイヤコミットメント及び／又はバッチにされたコミットメントと、
関数回路出力（ｈ）と、
証明キー（ＰｒＫ）と、
を送信することを含み、
これにより、検証者が、回路が満たされることを決定し、楕円曲線点（Ｐ）を計算して、ステートメントを検証すること、故に、証明者がステートメントに対する証拠（ｗ）を保持していると決定することを可能にする。

当該方法は、証明者が一組のデータ（データのセット）を検証者に送信することを含む。データのセットは、関数回路を実装し、所与の関数回路出力（ｈ）及び楕円曲線点（Ｐ）に対して、関数回路への又は関数回路内のワイヤへの関数回路入力（ｓ）が対応する楕円曲線点乗数（ｓ）に等しいかを判定する、ように構成されたｍ個のゲート及びｎ個のワイヤを有する算術回路を持つステートメントを含む。関数回路は、ハッシュ関数の機能を実装する回路とし得る。ハッシュ関数回路に対する又は関数回路内のワイヤに対するプリイメージは、対応する楕円曲線点乗数に等しいことができる。

データはまた、個々のワイヤコミットメント及び／又はバッチにされたコミットメントを含む。該コミットメント又は各コミットメントは、回路のゲートに関するワイヤ入力及び出力（これらは暗号化される）とし得る。データはまた、入力を含む。入力は、算術回路［楕円曲線点（Ｐ）］のワイヤに対するキーオープニングとしての働きをする。証明者又は検証者のいずれかがワイヤに名前を付け得る。入力又はキーオープニングは、回路内の最初のワイヤに対するものとし得る。データはまた、関数回路出力を含む。ステートメント内で使用される楕円曲線又は各楕円曲線の仕様をデータに含めることができる。

データを送信した後、証明者は、検証者からチャレンジ値を受信し、オープニングで応答する。オープニングは、Σ（シグマ）プロトコルに従った値ステートメントとし得る。オープニング値は、検証者が、ステートメントが真であると判定して楕円曲線点を計算することを可能にする回路の各ゲートに対するものとし得る。

チャレンジを待つことの代わりとして、証明者は更に証明キーを検証者に送信し得る。証明キーは、プルーフの一部であるデータから生成され得る。証明キーは、プルーフに使用される乱数のうちの１つ以上の乱数のハッシュとし得る。

検証者に送信されるデータは、検証者が、回路が満たされることを決定し、楕円曲線点を計算し、ステートメントを検証すること、故に、証明者がステートメントに対する証拠を保持していると決定することを可能にする。

検証者に送信されるデータのセット、及び／又は検証者に送信されるチャレンジへのオープニングは、検証者とは無関係に作成されるキーのように機能することができる。検証者からのチャレンジは、証明者の身元及びキーの完全性を決定することに類似している。

入力又はキーオープニングは、算術回路内の最初のワイヤに対するものとし得る。しかしながら、中間ワイヤの知識を証明することは、最初のワイヤの知識を証明することよりも困難であるため、ランダムなワイヤが選択されることが好ましい。さらに、最初のワイヤ以外のランダムなワイヤを選択することは、よりロバストであり、悪意ある第三者によるプルーフ又は証拠の発見を阻止する。

検証者が、証明者から受信したデータを分析することによって、ステートメントに対する証拠（ｗ）を知ることなく、ステートメントが真であることを検証するものであるステートメントのゼロ知識証明又は検証を可能にするための相補的なコンピュータ実装された方法を提供することが等しく望ましい。明確にしておくに、本発明の方法は、プラグソケット式に検証者によってとられる逆のアクションにまで及ぶ。本発明は、証明者と検証者との間の完全な共同作業にまで及ぶ。

証明者は、チャレンジ値を待つことに加えて、あるいは代えて、検証者が、ステートメントが真であると判定して楕円曲線点を計算することを可能にするランダム値を検証者に送信し得る。証明者からのデータの受信を受けて、検証者は代わりに、検証者が、ステートメントが真であると判定して楕円曲線点を計算することを可能にするランダム値を受信し得る。ランダム値は、少なくとも１つのコミットメントの関数とし得る。この関数は、ハッシュ関数とすることができる。

ランダム値又はチャレンジは、プロセスの利便性及び効率を向上させるために置き換えられ得る。また、証拠に関する情報を抽出しようという試みにおいて検証者が非ランダムなチャレンジを生成することに伴うリスクも存在する。さらに、チャレンジ値を、証明者によって提供されるランダム値で置き換えることは、この方法を対話型のものから非対話型のものに変換する。証明者は、独立的且つ公開的に検証されることが可能なプルーフをオフラインで生成することができる。ランダム値は、ハッシュ関数からの出力とし得る。ランダム値（ｘ）の代わりに、１つ以上のコミットメントのハッシュからの出力を用いることは、フィアット－シャミア（Fiat-Shamir）原理を利用する。

ランダム値は、証明者によって生成されて検証者に送信された全てのコミットメントの連結をハッシュすることによって計算され得る。

コミットメントは、Ｗ_ｉ＝Ｃｏｍ（ｗ_ｉ，ｒ_ｉ）とすることができ、
Ｃｏｍは関数回路へのコミットメントであり、
ｗ_ｉはワイヤ値であり、
ｒ_ｉは乱数であり、すなわち、これはワイヤコミットメントごとに異なり、
ｉはワイヤ種類であり、
Ｃｏｍ（ｗ，ｒ）＝ｗ×Ｇ＋ｒ×Ｆとされ、
Ｆ及びＧは楕円曲線点である。

算術回路内のワイヤｌに対する入力は、ｋｏ＝ｒ_ｌ×Ｆとすることができ、
ｋｏはキーオープニング入力であり、
ｒ_ｌは乱数であり、
Ｆは楕円曲線上の点である。

ワイヤは、回路内の最初のワイヤとし得る。

検証者は、回路が満たされることを確認することができ、楕円曲線点減算：
ｐｋ_ｌ＝Ｃｏｍ（ｗ_ｌ，ｒ_ｌ）－ｋｏ_ｌ
を介してワイヤｌに対する公開鍵を計算することができる。

証明者は、ワイヤコミットメントのバッチを送信し得るとともに、各ワイヤについて楕円曲線点を計算するための乱数を生成して、証明キーを形成し得る。

証拠に関するバッチにされたコミットメントは、

とすることができ、
ｒは、証明者によって生成された乱数であり、
証明者は、ワイヤ値ｗ_ｉ（ｆｏｒ ｉ＝１，…，ｎ）のベクトルｗへのコミットメントを計算し、
ｗ_ｎは、キーオープンされるものであり、
Ｋ_ｉは、計算された楕円曲線点であり、
ｗ_ｉはワイヤ値であり、
Ｆは楕円曲線上の点である。

算術回路内のワイヤｎに対する入力は、

であり、
ｋｏ_ｎはキーオープニング入力であり、
ｒは乱数であり、
Ｆは楕円曲線上の点である。

入力は、最初のワイヤに対するものとし得る。

検証者は、楕円曲線演算：

を介して、キーステートメントワイヤの公開鍵オープニングを計算し得る。

証明者は更に、完全にオープンにされたコミットメントを少なくとも１つのワイヤに送り得る。当該方法はＰｅｄｅｒｓｅｎコミットメントを使用し得る。ステートメントは、関数回路に対して１つの算術回路のみを使用し得る。関数回路は、好ましくはＳＨＡ－２５６ハッシュ関数であるハッシュ関数を実装し得る。

当該方法は、証明者によって、暗号鍵などのデータに対するゼロ知識付帯トランザクション（これは、ゼロ知識付帯トランザクションとし得る）を可能にするために使用されることができ、証明者は、提供されるデータ（これは、バニティアドレスとし得る）及び受信されるデータ（該データは、ＵＴＸＯの形態の支払とし得る）を確認するために検証者と連携し、検証者との通信チャンネル（該チャネルはオープンとし得る）を確立し、証明者は、検証者から、安全なランダム秘密鍵ｓｋＢから検証者が生成した楕円曲線公開鍵ｐｋ_Ｂを受信し、ｐｋ_Ｖ＝ｓｋ_Ｖ×Ｇであり、Ｇは楕円曲線点であり、
証明者は、データ＝ｐｋ_Ｖ＋ｉ×Ｇであるように、提供されるデータをロック値ｉで保護する。

証明者は、ｉを変えることによって得られたＢａｓｅ５８符号化アドレスにおける必要パターンの検索を実行しているとし得る。証明者は、ｐｋ_Ｐ＝ｉ×Ｇであるそれらの公開鍵と、関数回路入力（例えば、プリイメージ）がロック値ｉである関数回路からの出力ｆ（ｉ）と、を検証者に送信する。

証明者は、関数回路への入力が、ｐｋ_Ｐに対応する秘密鍵であることを検証者に証明するステートメントプルーフを検証者に送信することができ、故に、検証者がプルーフを検証し、ｐｋ＝ｐｋ_Ｖ＋ｐｋ_Ｐに対応するアドレスが合意されたパターンと一致することを確認することで、ロック値ｉを知ることが、データに関する完全な秘密鍵の導出を可能にすることと、ロック値ｉが関数回路への関数回路入力であることと、を特定することを可能にし得る。

証明者は、証明者からの署名と関数回路入力とによってアクセスされることが可能な、受信されるデータを含む出力を含んだトランザクションＴｘ_１を受信し得る。該トランザクションは、ハッシュ時間ロック関数とし得る。受信されるデータが、ＵＴＸＯへのアクセスを提供し得る。

証明者は、該トランザクションに署名して該トランザクションをブロックチェーン上でブロードキャストすることができ、それがブロックへとマイニングされて、該トランザクションをアンロックするための署名及び値ｉを供給する第２のトランザクションＴｘ_２を提供することによって、トランザクションＴｘ_１の出力からデータに証明者がアクセスすることを可能にし、そして、該トランザクションは、ブロックチェーン上で明らかにされ、斯くして、検証者が、ロック値ｉを特定して、証明者によって提供されたデータにアクセスすることを可能にし、
ｓｋ＝ｓｋ_Ｂ＋ｉであり、
ｐｋ＝ｓｋ×Ｇである。

証明者によって提供されるデータはバニティアドレスを含み得る。検証者から受信されるデータは暗号通貨支払（例えば、ＵＴＸＯ）を含み得る。

トランザクションは、完全にアトミックでトラストレスとすることができ、買い手は有効な値ｉを提供した場合にのみ支払いを受け、値ｉはブロックチェーン上で公然に明かされる。秘密鍵の分割により、ブロックチェーン上で露わにされる値は、他の誰にも役に立たず、完全な秘密鍵のセキュリティを損なわない。

あるコンピュータ実装された方法は、証明者が検証者との（第三者による集中化された交換を用いない）トラストレスでの公正なデータ交換を実行することを伴い得る。これは、クロスチェーン・アトミック・スワップ又はアトミックトレードとして記述されることができる。何故なら、この文脈では、両者がトランザクションを完了するか両者とも完了しないかのいずれかであるという公正な交換性を参照するからである。このスワップは、ハッシュされた時間ロックされた契約を可能にするスクリプト機能をサポートするブロックチェーン間で実行されることができる。

証明者は、第１のブロックチェーン上の例えば１ビットコインのＵＴＸＯなどの第１のデータへのアクセスを持ち、検証者は、第２のブロックチェーン上にある例えば１００ＬＴＣなどの第２のデータへのアクセスを持ち、証明者及び検証者は、データを交換することに合意する。当該方法は、証明者が、第２のブロックチェーンに対する鍵ペアを生成し、公開鍵を検証者に送信し、秘密鍵を保持することと、証明者が、第１のブロックチェーンに対する検証者公開鍵を受信し、検証者は、第１のブロックチェーンに対する鍵ペアを生成して秘密鍵（ｓ_Ｂ）を保持していることと、証明者が、ステートメントと、１つ以上のコミットメントと、入力若しくはキーオープニング及び関数回路出力（ｈ）と、楕円曲線仕様とを送信することと、を含む。

証明者は、第１のデータを共通の公開鍵アドレスに送信する第１のブロックチェーントランザクションＴｘ_Ａを作成することができ、そして、該トランザクションを第１のブロックチェーンネットワーク上でブロードキャストし、該アドレスは、入力と検証者公開鍵との和によって定められる。このデータは、２４時間以内にスワップが実行されなかった後に、証明者によってアクセスされることができる。

証明者は、第２のブロックチェーントランザクションＴｘ_Ｂを検証することができ、該トランザクションは、第１のブロックチェーンに第１のブロックチェーントランザクションＴｘ_Ａが含まれることを確認した後に、検証者によって作成されて第２のブロックチェーンネットワーク上でブロードキャストされ、該トランザクションは、１００ＬＴＣの形態の第２のデータを証明者公開鍵アドレスに送り、該証明者公開鍵アドレスは、該証明者公開鍵アドレスに関する有効な署名、及び関数回路出力を決定する関数回路入力である値、を用いて証明者によってアクセス可能である。このデータは、２４時間以内にスワップが実行されなかった後に、検証者によってアクセスされることができる。

証明者は、第２のブロックチェーントランザクションＴｘ_Ｂが第２のブロックチェーン上に含まれることを確認し、署名と、関数回路出力の関数回路入力である上記値と、を提供することによって第２のデータにアクセスし、斯くして、検証者が、関数回路出力を決定する関数回路入力である上記値を観測し、（楕円曲線点乗算の同形性からｓ_Ｂ＋ｓであるＰ_Ｃの）秘密鍵を用いて署名を提供することによって第１のデータにアクセスすることを可能にする。

交換されるデータは暗号通貨とすることができ、第１のデータは、好ましくはビットコイン（Bitcoin）である第１の暗号通貨の量に対応し、第２のデータは、好ましくはライトコイン（Litecoin）である第２の暗号通貨の量に対応する。

上述のように、証明者による全てのアクションは、プルーフを検証するための検証者による逆のアクションを必要とする。本発明は、検証者によって実行される方法又はアクションにまで及ぶ。従って、証明者が、検証者に対して、ステートメントが真であることを、該ステートメントに対する証拠を秘密にしたまま、好ましくは明示的に、証明するものである、ステートメントのゼロ知識証明又は検証を可能にするためのコンピュータ実装された方法が提供され、当該方法は、検証者が証明者から：好ましくはハッシュ関数である関数回路を実装して、所与の関数回路の、そして好ましくは指定された関数回路の出力及び楕円曲線点に対して、関数回路への関数回路入力又はプリイメージが楕円曲線点乗数に等しいかを判定する、ように構成されたｍ個のゲート及びｎ個のワイヤを有する算術回路を持つステートメント、を受信することを含む。検証者はまた、回路のワイヤについての、暗号化されたワイヤ入力及び出力である個々のワイヤコミットメント及び／又はバッチにされたコミットメントと、算術回路内のワイヤ（好ましくは、最初のワイヤ以外のワイヤ）に対する入力又はキーオープニングと、関数回路出力（ｈ）と、を受信する。検証者はまた、ステートメントで使用される楕円曲線又は各楕円曲線の仕様を受信し得る。検証者は、証明者にチャレンジ値を送信することができ、その後、オープニングを受信する。オープニングは、Σプロトコルに従うものとすることができ、検証者が、ステートメントが真であると判定して楕円曲線点を計算する、ことを可能にする回路の各ゲートについての値を含むことができる。加えて、あるいは代わりに、検証者は、証明者から証明キーを受信し得る。

そして、検証者は、回路が満たされると判定し、楕円曲線点（Ｐ）を計算し、故に、証明者がステートメントに対する証拠（ｗ）を保持していると判定する。

これは、ステートメント回路の各ゲートについての値を証明者が知っていることを、証明が対話型である場合にはシグマプロトコルを用いて、あるいは、フィアット－シャミアヒューリスティックが使用される場合には証明キーを用いて、ゼロ知識で証明することによって達成され得る。検証者は、証明者から各ゲートに対するΣ＿ｚｅｒｏ及びΣ＿ｐｒｏｄコミットメントを受信し、チャレンジ値で応答し、証明者からオープニング値を受信し、そして、コミットメントと照合することができる。検証者は、楕円曲線点減算を介してワイヤｌに対する公開鍵を計算することによって、回路が満たされることを確認し得る。検証者は、各ワイヤについての各公開鍵が、ステートメントで指定された（１つ以上の）鍵と一致することを確認し得る。検証者は、完全にオープンにされたワイヤが、ステートメント内の指定可能な値と一致すると判定して、検証を完了することができる。

コンピュータ実行可能命令を有したコンピュータ読み取り可能記憶媒体を提供することも望ましく、該コンピュータ実行可能命令は、実行されるときに、証明者によって、検証者によって、又は証明者と検証者とが協働することによって実行される方法を実行するようにプロセッサを構成する。

インタフェース装置と、該インタフェース装置に結合された１つ以上のプロセッサと、該１つ以上のプロセッサに結合されたメモリとを有するエレクトロニクス装置を提供することも望ましく、メモリはコンピュータ実行可能命令を格納しており、該コンピュータ実行可能命令は、実行されるときに、ここに特許請求される方法を実行するように上記１つ以上のプロセッサを構成する。特許請求される方法を実行するように構成された、ブロックチェーンネットワークのノードを提供することも望ましい。そのようなノードを有するブロックチェーンネットワークを提供することも望ましい。

本発明の態様が、ここに記載される実施形態を参照して解明されて明らかになる。以下、本発明の実施形態が、単なる例として、以下を含む添付の図面を参照して説明される。
図１（ａ）及び（ｂ）は、技術的背景のセクションで対話型ゼロ知識証明に関する基本システムを上述した際に使用した図であり、図１（ａ）、左及び右のワイヤ入力と１つのワイヤ出力とを有する乗算ゲートの概略図であり、図１（ｂ）は、３つのゲート、３つの入力ワイヤ、１つの出力ワイヤ、及び２つの内部ワイヤを有する算術回路の概略図である。 ハッシュ関数及び楕円曲線乗算のための算術回路を含む、ステートメントに関する複合回路の概略図である。 １つの算術回路のみが必要とされる、図１の複合ステートメントに関する算術回路の代替概略図である。 ４つのゲートと５つのワイヤを持つ算術回路の概略図であり、ワイヤは、その公開鍵を有し、その公開鍵は、キーオープニング値でワイヤコミットメントから明らかにされる又はオープンにされる自身の公開鍵を持つ。 回路記述を有し且つ最初のワイヤが対応する公開鍵を持つステートメントＳの証明のために証明者と検証者との間で交換されるデータの概略表現である。 証明者と検証者との間で交換されるデータの他の概略表現である。 図４の回路が満たされること、入力ワイヤが必要な公開鍵を持つこと、及び出力ワイヤのハッシュが必要な値を持つことを検証するために検証者によって実行されるチェックの概略図である。

概説
本発明は、算術回路充足可能性と公開鍵の妥当性に関する従属ステートメント（キーステートメントプルーフ）の両方を同時に必要とする複合ステートメントの効率的なゼロ知識検証を可能にする。公開鍵楕円曲線仕様が、回路充足可能性を証明するために、同形コミットメント関数内で採用される。これは、効率的なやり方で回路入力及び／又は出力として使用される秘密鍵に対応する公開鍵ステートメントの証明を可能にする。

回路充足可能性及び楕円曲線キーペアの両方を含むステートメントに関するプルーフを生成することのプルーフサイズ及び計算費用を大きく低減することができる。ここでの方法は、双線形ペアリングフレンドリー楕円曲線の使用を必要としないものである回路充足可能性に関する既存の離散対数ベースのゼロ知識プルーフプロトコルに容易に組み込むことができる。当該方法は、ビットコインｓｅｃｐ２５６ｋ１標準に完全に適合する。

例えばビットコインブロックチェーンなどのブロックチェーン上の２者間の公正な交換トランザクションに関係する２つの用途が記述される。１つ目は、アウトソーシングされたバニティアドレスのトラストレス販売に関するゼロ知識付帯支払いを含み、これは、ＳＨＡ２５６ハッシュプリイメージと楕円曲線（例えば、ビットコイン）秘密鍵とが等しいことのゼロ知識証明を必要とする。２つ目は、クロスチェーン・アトミック・スワップのセキュリティを向上させることを含み、これは、ＳＨＡ２５６ハッシュプリイメージが、未知の秘密鍵（提供された公開鍵を有する）に、提供されたナンスを乗じたものに等しいことの証明を必要とする。

全般的ソリューション
この発明は、（楕円曲線点乗算に基づく）楕円曲線公開／秘密鍵ペアとの関係を含む特定のクラスの複合ステートメントの証明を可能にする方法に関する。

任意の暗号楕円曲線キー操作を含むステートメントを証明するためにｚｋＳＮＡＲＫを用いることは非現実的と考えられ、従って、当該方法は、一般的な回路充足可能性に関するプルーフの構築に使用される“同形隠蔽（homomorphic hiding）”（又はコミットメントスキーム）から直接抽出される楕円曲線公開鍵に関する情報を使用する。当該方法のステートメントに関与する特定タイプの楕円曲線は、回路コミットメントスキームで使用されるものと同じである。

しかしながら、ＳＮＡＲＫ法はペアリング操作を必要とし、それ故に、特別な双線形ペアリングフレンドリー楕円曲線を必要とする。このことは、一部のブロックチェーン上で使用される楕円曲線は双線形ペアリングフレンドリー楕円曲線と互換性がないので、ｚｋ－ＳＮＡＲＫの使用を不可能にする。

例として、ビットコイン公開鍵に関係するステートメントは、互換性のないものであるビットコインｓｅｃｐ２５６ｋ１曲線を使用している。

従って、本発明の方法は、ペアリングに頼らずにいっそう少ない暗号仮定を有した、算術回路充足可能性を証明するための他のプロトコルに適合する。全体的に、本発明の方法はｚｋＳＮＡＲＫＳよりも効率的である。何故なら、より少ない計算しか必要とされず、トラストレス交換用途でのプルーフサイズが小さくなるからである。

例として、後述の“ステートメント１”に関する複合回路を表すものである図２の概略図は、ハッシュ関数と楕円曲線乗算の両方のサブ回路を含む。図２において、その概略図は、秘密鍵‘ｓ’並びにそれが有する対応する対を為す公開鍵‘Ｐ’及び値‘ｈ’（これは秘密鍵‘ｓ’のハッシュである値）という、３つの入力（Input）を持っている。この概略図は２つの算術回路を含んでおり、１つ目は、秘密鍵に対するハッシュ（Hash）を実行し、２つ目は、秘密鍵に対する楕円曲線乗算（EC mult）を実行する。これらの回路の出力（Out）が入力と比較される。

なお、これら内部ゲートは単に例示目的でのものである。この回路は、ハッシュの出力が楕円曲線（ＥＣ）公開鍵に等しいことを検査する。入力‘ｈ’、‘Ｐ’、及び出力のみが検証者に対して完全に明らかにされる。そのたの値は全て暗号化される。

ステートメント１
“ハッシュ関数（Ｈ）の出力ｈと楕円曲線点Ｐ（公開鍵）を所与として、ハッシュｓ（すなわち、ｈ＝Ｈ（ｓ））のプリイメージが、楕円曲線点乗数（秘密鍵、すなわち、Ｐ＝ｓ×Ｇ、ただし、Ｇは楕円曲線生成点）に等しい”。

当該方法は、証明者がこの特定のステートメントをゼロ知識で証明することを可能にする。このような方法からの恩恵を受ける用途の例が、トラストレスでのデータ交換（例えば、アウトソーシングされたビットコインバニティアドレスの販売）、及び匿名化されたセキュアなクロスチェーン・アトミック・スワップに関して後述される。

ステートメント１が真であることの検証は、例として、入力‘ｈ’、‘Ｐ’、‘ｓ’をとって、ステートメントが真である場合に‘１’を出力し、それ以外の場合には‘０’を出力するものである以下の擬似コード関数を用いて決定可能である：
int verify(h,P,s)
{
if(h == H(s) && P == s x G) {
return 1
}
else {
return 0
}
}

‘ステートメント１’を、ゼロ知識で検証すること、すなわち、ｚｋＳＮＡＲＫシステムで証明者が‘ｓ’の値を検証者から秘密にしたままで検証することは、図２のように、ハッシュ関数と楕円曲線点乗算の両方について算術回路を必要とすることになる。

ＳＨＡ－２５６ハッシュ関数に関する算術回路は広く使用され、最適化されて、典型的に３０，０００未満の乗算ゲートを含むが、文献において、暗号楕円曲線点乗算実装に関する算術回路の例は知られていない。そのような回路が知られていたとしても、それらは、そのサイズ及び複雑さのために実用的でなく、より多くのゲートを含む。

当該方法は、図２に示すような、単一ハッシュ関数のための完全な算術回路で機能し、これは、キーステートメントプルーフと、ハッシュ関数用の１つの算術回路のみを使用する複合ステートメント１に関する算術回路の概略図を有している。この回路は、ハッシュの出力が正しいこと、及び公開鍵がＥＣの暗号化された入力（キーステートメントプルーフ）に等しいことを検査する。青色でハイライトされた値、すなわち、入力‘ｈ’、‘Ｐ’及び出力‘１’は検証者に対して明らかにされ、その他全ての値は暗号化される。

図３の回路を用いて、証明者は、回路充足可能性を介して、秘密鍵‘ｓ’のハッシュが‘ｈ’になること、及び、楕円曲線生成点をＧとして、鍵ペアの対応する公開鍵‘Ｐ’が‘ｓ×Ｇ’に等しいことを、明示的に証明することができる。秘密鍵‘ｓ’は、ハッシュのプリイメージ、又は関数への入力であり、ステートメントを証明するときに検証者には明らかにされない。

言うまでもなく、‘ｓ×Ｇ’が‘Ｐ’に等しいことを検証することは、プルーフプロトコルの一部としてコミットメントスキームにおいて必要な楕円曲線を使用することにより、無視できる追加の計算コストで回路プルーフから抽出されることができる。このような操作は‘キーステートメントプルーフ（key-statement proof）’と呼ばれており、‘キーオープニング（key-opening）’と呼ばれるコミットメントオープン手順を使用する。

技術的効果
既知のｚｋ‐ＳＮＡＲＫ（Zero-knowledge Succinct Non-interactive Arguments of Knowledge）は、算術回路充足可能性に関する汎用証明システムの一実装である。ＳＮＡＲＫフレームワークにおいて、算術回路としてエンコードされるステートメントは、多項式の集合から成る二次算術プログラム（Quadratic Arithmetic Program；ＱＡＰ）と呼ばれる構成へと変換される。そして、この式の集合の妥当性を単一の点で実証することによって、ステートメントを証明することができる。ＳＮＡＲＫ法の主な利点は、検証者が数少ない楕円曲線（ペアリング）演算（数ミリ秒を要する）を実行するだけでよく、プルーフが非常に小さく（２８８バイト）いとともに回路サイズに依存しないということである。

ＳＮＡＲＫ法によって達成される非常に小さいプルーフ及び検証時間は、トラストのあるセットアップ、標準的でない暗号仮定、及び証明者に課される遥かに重い計算負荷という犠牲のもとでもたらされる。ＳＮＡＲＫ法はまた、楕円曲線双線形ペアリングの使用を必要とする。しかしながら、計算的に実現可能な双線形ペアリングの使用は、特別な‘ペアリングフレンドリー’楕円曲線の使用を必要とする。これは、ビットコインｓｅｃｐ２５６ｋ１を含む、多くの標準的な暗号楕円曲線パラメータセットの使用を排する。すると、一般的な楕円曲線点乗算を含むステートメントは、明示的な回路（非常に大きくなり得る）を使用しなければならない。

前節で説明したＳＨＡ回路充足可能性を証明するためのΣプロトコルアプローチとの比較として、ＳＮＡＲＫ（ピノキオ）フレームワークを用いる場合、証明キーは生成するのに約１０秒を要し、約７ＭＢのサイズになり、プルーフも生成するのに約１０秒を要することになる。しかしながら、プルーフサイズは２８８Ｂとなり、検証するのに要するのは約５ｍｓのみである（非特許文献８）。

さらに、明示的な楕円曲線乗算（キーステートメント）を回路に組み込むことは、証明キーサイズ及びプルーフ生成時間の両方に、少なくとも１桁の大きさを乗じることになる。

本発明は、一般的な算術回路充足可能性と同時での、楕円曲線公開鍵－秘密鍵関係を含むステートメントのゼロ知識証明を可能にする。これは、算術回路充足可能性を証明することの域を超えて無視できる計算費用で達成され、証明の計算費用をかなり増加させるものである楕円曲線点乗算演算用の明示的算術回路を作成することを不要にする。

実装
以下、本発明の実装を、バッチ式及び非バッチ式の両方のコミットメントベースゼロ知識証明システムについて説明する。

これら例では、ゼロ知識証明プロトコルに、証明者（Ｐ）及び検証者（Ｖ）の二者が関与する。このプロトコルの目的は、証明者が、所与のステートメント（Ｓ）が真であることを、そのステートメントに対する証拠についての情報を秘密にしたまま、検証者に確信させることである。ステートメントは、ｍ個のゲート及びｎ個のワイヤを有する算術回路（Ｃ）と、回路ワイヤ値のうちの１つ（又はそれ以上）に対応する楕円曲線公開鍵：ｐｋ_ｌについての従属アサーションとで構成される。ここで、下付き文字のｌは、キーステートメントのワイヤインデックスである。さらに、ステートメントはまた、完全にオープンにされた（公開）ワイヤ値（すなわち、回路の公開入力／出力）についてのアサーションを含んでもよい。

ステートメントで指定される（１つ以上の）楕円曲線公開鍵は、ターゲット楕円曲線仕様（これは、楕円曲線パラメータの全集合：Ｔ＝（ｐ，ａ，ｂ，Ｇ，ｎ，ｈ）によって規定される）に対応する。

ビットコインスクリプトの場合、これらのパラメータはｓｅｃｐ２５６ｋ１（非特許文献９）の仕様によって規定される。この使用は、ベース生成点Ｇを含む。ベース点を指定することに加えて、ステートメントはまた、第２の点Ｆも指定しなければならない（ここで、Ｆ＝ｆ×Ｇであり、ｆはＺ_ｐの要素である）。証明者にｆの自由選択を許すことは証明者が偽のプルーフを生成することを可能にすることになり得るので、ｆの値は、証明的にランダムでなければならず（例えば、ビットコインジェネシスブロックハッシュ）、あるいは、例えばπのバイナリ表現の最初の２５６ビットなどの“奥の手以外の何物でもない（nothing up my sleeve）”数字でなければならない。

バッチにされたコミットメント及びバッチにされていないコミットメントを、４つのゲート及び５つのワイヤを有する代表的な算術回路である図４に関連して説明する。入力ワイヤ（ｗ_１）は、‘キーオープニング’値ｋｏ_１を有するワイヤコミットメントＷ_１から明らかにされる又はオープンにされるその公開鍵を持つ。

実装 － 個々のワイヤコミットメント
図４を一例として用いるに、‘キーオープニング’は、証明者によって作成されて検証者に送信される、回線内の各ワイヤに対する個々のコミットメントである。これらのキーオープニングは、算術回路充足可能性に関する既知のΣプロトコルに従う。図５は、証明者と検証者との間で交換されるデータを示している。

充足可能性は、以下のように、幾つかのステップを含めることによって達成される：
１． 回路の各ワイヤｉ（ｉ＝１，…，ｎ）に対して、Ｐｅｄｅｒｓｅｎコミットメントを用いてコミットされる：
Ｗ_ｉ＝Ｃｏｍ（ｗ_ｉ，ｒ_ｉ）
ここで、
Ｃｏｍ（ｗ，ｒ）＝ｗ×Ｇ＋ｒ×Ｆ
２． それが対応する公開鍵の照明（キーステートメントプルーフ）を必要とする回路ワイヤｌに対して、証明者はまた、キーオープニング：
ｋｏ_ｌ＝ｒ_ｌ×Ｆ
も送信する。
３． オプションで、回路ワイヤｊが公然に明らかにされていること（完全に公開されたワイヤ）を必要とする場合、証明者は完全なオープニングタプル：
（ｗ_ｊ，ｒ_ｊ）
を送信する。
４． 次いで、Σプロトコルを用いてゼロ知識で、回路の各ゲートが満たされることが証明され、これは、証明者が、各ゲートについてΣ_ｚｅｒｏ及びΣ_ｐｒｏｄコミットメント（すなわち、それぞれ、Ｂ、又はＣ_１，Ｃ_２，Ｃ_３）を計算して送信し、検証者がチャレンジ値（ｘ）で応答し、次いで証明者がオープニング値（ｚ及びｅ値）を送信し、そして、検証者がコミットメントと照合することを含む。
５． 回路が満たされることを検証者が確認すると、次いで、検証者が、楕円曲線点減算：
ｐｋ_ｌ＝Ｃｏｍ（ｗ_ｌ，ｒ_ｌ）－ｋｏ_ｌ
を介してワイヤｌに関する公開鍵を計算する。
６． そして、検証者が、各ｐｋ_ｌがステートメント中で指定された（１つ以上の）キーと一致すること（及び完全にオープンにされたワイヤが指定値と一致すること）を確認して、検証を完了する。

詳細な実装 － 個々のワイヤコミットメント
図４を続けて参照して、この例の個々のコミットメント及び検証を詳述する明示的な例を提供する。これは、ワイヤのうちの１つのキーステートメントプルーフ及び他の１つのワイヤの完全な開示の両方で、単純な算術回路の充足可能性を検証することを記述するものである。

図４に示す回路Ｃは、５つのワイヤｗ_ｉ（ｉ＝１，…，５）と４つのゲートｇ_ｊ（ｊ＝１，…，４）とを有している。ゲート１及び３は加算ゲートであり、ゲート２及び４は乗算ゲートである。

証明者及び検証者は、楕円曲線及びコミットメント仕様と共に、回路、ワイヤ５の値、及びワイヤ１の公開鍵を含むステートメントに同意する。それが真であることを証明者が検証者に対して証明することを望むステートメント（Ｓ）は：
“私は、回路Ｃへの充足割り当て（すなわち、全てのゲートを満たすワイヤ値｛ｗ_ｉ｝_ｉ＝１ ^５を知っており、ただし、ワイヤ１は公開鍵Ｐ（すなわち、Ｐ＝ｗ_１×Ｇ）を持っており、ワイヤ５は値ｈ（すなわち、ｗ_ｎ＝ｈ）を持っている”
である。

ワイヤ１から４の値は明らかにされない。そして、図６に示すように、また以下に説明するように、証明者及び検証者がインタラクトする：
１． 証明者が、５つのランダムなブラインディング値（ｒ_１，…，ｒ_５）を生成し、次いで、５つのワイヤコミットメント（Ｗ_１，…，Ｗ_５）を計算し、それらを検証者に送信する。
２． 証明者が、ワイヤ１に対するキーオープニング：ｋｏ_１＝ｒ_１×Ｆを計算し、それを検証者に送信する。
３． 証明者が、ワイヤ５に関する完全なオープニング情報（ｗ_５，ｒ_５）を検証者に送信する。
４． 加算ゲート（ｇ_１及びｇ_３）について、証明者が、（ランダムなナンスｒ_Ｂ１及びｒ_Ｂ３を用いて）ゼロに対するコミットメント：Ｂ_１＝Ｃｏｍ（０，ｒ_Ｂ１）及びＢ_３＝Ｃｏｍ（０，ｒ_Ｂ３）を生成し、それらを検証者に送信する。
５． 乗算ゲート（ｇ_２及びｇ_４）について、証明者が、次のようにコミットメントを生成し、すなわち：
ゲート２について：
Ｃ_１２＝Ｃｏｍ（ｔ_１２，ｔ_３２）
Ｃ_２＝Ｃｏｍ（ｔ_２２，ｔ_５２） 及び
Ｃ_３＝ｔ_１２×Ｗ_１＋ｔ_４２×Ｆ
ゲート４について：
Ｃ_１４＝Ｃｏｍ（ｔ_１４，ｔ_３４）
Ｃ_２＝Ｃｏｍ（ｔ_２４，ｔ_５４） 及び
Ｃ_３＝ｔ_１４×Ｗ_３＋ｔ_４４×Ｆ
のようにコミットメントを生成し、ここで、ｔ_ｘｘ値は、ランダムなブラインディングナンスである。証明者は、これらのコミットメントを検証者に送信する。
６． 次いで、検証者が、ランダムチャレンジ値ｘを生成し、それを証明者に送信する。あるいは、検証者は、フィアット－シャミアヒューリスティックを用いて、全てのコミットメントの連結をハッシュすることによって、値ｘを生成してもよい。
７． 加算ゲート（ｇ_１及びｇ_３）について、証明者が、以下のオープニング：
ｚ_１＝ｘ（ｒ_１＋ｒ_１－ｒ_２）＋ｒ_Ｂ１
ｚ_３＝ｘ（ｒ_２＋ｒ_１－ｒ_４）＋ｒ_Ｂ３
を計算し、それらを検証者に送信する。
８． 乗算ゲート（ｇ_２及びｇ_４）について、証明者が、以下のオープニング：
ｅ_１２＝ｗ_１ｘ＋ｔ_１２
ｅ_２２＝ｗ_２ｘ＋ｔ_２２
ｚ_１２＝ｒ_１ｘ＋ｔ_３２
ｚ_２２＝ｒ_２ｘ＋ｔ_５２
ｚ_３２＝（ｒ_３－ｗ_１ｒ_２）ｘ＋ｔ_４２

ｅ_１４＝ｗ_３ｘ＋ｔ_１４
ｅ_２４＝ｗ_４ｘ＋ｔ_２４
ｚ_１４＝ｒ_３ｘ＋ｔ_３４
ｚ_２４＝ｒ_４ｘ＋ｔ_５４
ｚ_３４＝（ｒ_５－ｗ_３ｒ_４）ｘ＋ｔ_４４
を計算し、それらを検証者に送信する。
９． 最後に、検証者が、等価性を検査する。これらが合格すると、証明が検証される。

検証者によって実行される検証は、図７にまとめられており、内側のボックス内の検査が、回路が満たされること、及び、第１のワイヤが必要な公開鍵を有し、第５のワイヤが必要な値を有することを検証する。

図５及び図６のチャレンジ‘ｘ’は、対話的な証明を提供し、証明者と検証者との間で通信が往復する。

売り手と買い手が同時には応対できない、あるいはオンラインでないことがあり得るので、このインタラクションは、ゼロ知識付帯支払い（zero-knowledge contingent payment；ＺＫＣＰ）が行われるときに不便であり得る。また、買い手（検証者）が、プルーフが公開的に検証可能であることを望むことがあり、例えば、それがデジタルグッズの広告の一部であることがある。

さらに、証明が厳密にゼロ知識であるのは、完全特別正直検証者（perfect special-honest verifier）モデルにおいてのみであり、すなわち、検証者がチャレンジとして真の乱数を生成するのであって、証拠についての情報を試して取り出すためのチャレンジ値を選択したりはしないと仮定されるときのみである。

これらの問題を解決するために、フィアット－シャミアヒューリスティックが適用され、これは、ランダムチャレンジ値‘ｘ’を、証明者によって作成されたコミットメントのハッシュの出力で置き換える。ランダムオラクルモデル（暗号ハッシュ関数の出力が真にランダムとみなされる）では、証明者は不正を働くことができず、検証者は生成されたチャレンジ値を検査することができ。

従って、この例は、フィアット－シャミアヒューリスティックを使用して対話型証明システムを非対話型のものに変換することによって改善さることができ、また、証明者は、オフラインで独立して公開的に検証されることができるプルーフを生成することができる。

より具体的には、チャレンジ値（ｘ）が、証明者によって生成されたコミットメントの全て（すなわち、ワイヤコミットメントの全てと、和ゲート及び積ゲートそれぞれに対するＢ及びＣ_１，Ｃ_２，Ｃ_３コミットメントの全て）の連結を（例えば、ＳＨＡ－２５６で）ハッシュすることによって計算される値で置き換えられる。

実装 － バッチ化ベクトルコミットメント
ベクトルコミットメントのバッチ化を伴う回路充足可能性に関する圧縮証明システム（非特許文献８、非特許文献６）は、以下に記載される方法を使用し、当該方法は、バッチにされた回路ワイヤコミットメントからキーステートメントプルーフを抽出することを可能にする。

繰り返しを避けるため、完全なプロセスを記載することはせず、以下のステップは、バッチにされたワイヤコミットメントの生成と、それが指定された公開鍵を含むことを例証することとに焦点を当てている。以下のステップでは、ワイヤｌが、キーオープニングを与えられるものであり、ｎ個のワイヤがベクトルコミットメント内で共にバッチにされるとして、以下のように、バッチにされたコミットメントが生成される。
１． 証明者が、ｎ－１個の乱数ｘ_１，…，ｘ_ｎ－１←Ｚ_ｐを生成する。
２． 証明者が、楕円曲線点Ｋ_ｉ＝ｘ_ｉ×Ｇ（ｆｏｒ ｉ＝１，…，ｎ－１）を計算する。これらの値にＫ_ｎ＝Ｇを足したものが、検証者に送られる証明キーＰｒＫを形成する。
３． 証明者が、ランダム値：ｒ←Ｚ_ｐを生成する。
４． ｗ_ｎがキーオープンされるものであるとして、証明者が、ワイヤ値ｗ_ｉ（ｆｏｒ ｉ＝１，…，ｎ）のベクトルｗへのコミットメント：

を計算し、それを検証者に送信する。
５． 証明者がまた、ベクトルコミットのためのキーオープニング：

を送信する。
６． 検証者が、楕円曲線演算：

を介して、キーステートメントワイヤの公開鍵オープニングを計算する。

発明概要
ハッシュプリイメージ及び楕円曲線秘密鍵の等価性の証明は、数多くの用途で利用されることができる。以下、利用のためのキーステートメントゼロ知識プルーフの具体例の構築を概説するものである２つの用途について説明する。

以下のステートメントＳは、適用例の目的で、上述のステートメント１のより具体的なバージョンである：
Ｓ：
“公開出力ｈを有するＳＨＡ－２５６ハッシュ関数（Ｈ）及びｓｅｃｐ２５６ｋ１楕円曲線上の公開点Ｐが所与であり、ハッシュの秘密のプリイメージｓ（すなわち、ｈ＝Ｈ（ｓ））が、楕円曲線点乗数（すなわち、対応する秘密鍵、すなわち、Ｐ＝ｓ×Ｇ）に等しい”

提供される例において、このステートメントは、入力ワイヤ（ｗ１）が公開点Ｐの秘密鍵である、及び出力ワイヤ（ｗｎ）がｈに等しい、というアサーションとともに、ＳＨＡ－２５６ハッシュ関数Ｃ_{ＳＨＡ２５６}（ｎ個のワイヤｗ_ｉ（ｉ＝１，…，ｎ）及びｍ個のゲートを有する）に関する単一の算術回路で構成され、すなわち、

で構成される。

従って、このステートメントを完全に検証するために、証明者は、検証者に対して、ｓｅｃｐ２５６ｋ１ベースのコミットメントスキームを使用して、ＳＨＡ２５６回路への充足割り当てを知っていることを実証し、そして、ワイヤ１についてのキーオープニング（ｋｏ_１）及びワイヤｎについての完全オープニング（ｗ_ｎ，ｒ_ｎ）を単純に提供しなければならない。検証者は、入力ワイヤ（ｗ_１）の値を教わらず、すなわち、完全にオープンにされる出力ワイヤｗ_ｎを除く他のワイヤのいずれの値も教わらない。

用途Ｉ
上の実装セクションで説明した本発明の例は、支払い又はリソースへのアクセスのために交換されるデータを表すものである、アウトソーシングされたビットコインバニティアドレスに関するＺＫＣＰに適用されることができる。

ビットコインアドレスは、公開、コピー及び転記するのが容易なものとするために、人間読み取り可能な英数字フォーマット（Ｂａｓｅ５８エンコーディング）でエンコードされる。このフォーマットの使用は、所謂バニティアドレスの人気につながっており、例えば下に示すもの：
［外１］

などの、所望の（名前のような）文字列を含むアドレスを生じる秘密鍵を見つけるために、鍵空間がブルートフォース（総当たり）探索される。

有意なパターンを有するバニティアドレスを導出することは計算的に高くつくため（例えば、上に示したアドレスは、一致が見つかるまでにおよそ１０^１３個の異なる公開鍵の生成を必要とした）、検索をアウトソーシングすることが一般的であり、バニティアドレスが委託販売されているオンラインマーケットプレイスが幾つか存在している。これは、楕円曲線点乗算の同形性を用いて安全に行われることができる（非特許文献７）。

生成をアウトソーシングすることは安全であるが、バニティアドレスの販売は信用できない。売り手が支払いを受ける前に買い手が必要値を得たり、売り手が必要値を渡す前に支払いを受けたり、あるいは両者ともが第三者預託サービスを信頼しなければならなかったりする。本発明は、ＺＫＣＰを介したバニティアドレスのトラストレス販売を可能にするために使用されることができる。以下にて、買い手／検証者と売り手／証明者との間でとられるステップを説明する。
１． 買い手と売り手が、必要なバニティパターン（Ｓｔｒ）及び価格（ａビットコイン）について合意し、セキュアである必要のない通信チャンネルを確立する。
２． 買い手が、セキュアなランダム秘密鍵ｓｋＢ及び対応する楕円曲線公開鍵を生成し、公開鍵ｐｋ_Ｂ＝ｓｋ_Ｂ×Ｇである。
３． 買い手が売り手にｐｋ_Ｂを送信する。
４． 次いで、売り手が、ｉを変化させることによってｐｋ＝ｐｋ_Ｂ＋ｉ×Ｇから導出されるＢａｓｅ５８エンコードされたアドレスにおいて必要なパターンの探索を実行する。
５． 必要なパターンを持つアドレスが見つかった場合、売り手はｉを保存し、買い手にシグナリングして、ｐｋ_ｓ＝ｉ×Ｇ及びＳＨＡ２５６ハッシュＨ（ｉ）を送信する。
６． 売り手はまた、上の例で説明したように、Ｈ（ｉ）に対するプリイメージが、ｐｋ_ｓに対応する秘密鍵であることのプルーフを買い手に提供する。
７． 買い手が、プルーフを検証し、また、ｐｋ＝ｐｋ_Ｂ＋ｐｋ_ｓに対応するアドレスが合意したパターンに一致することを確認する。この時点で（プルーフによって）、買い手は、値ｉを教わることで、自身がバニティアドレスに関する完全な秘密鍵（ｓｋ_Ｂ＋ｉ）を導出することが可能になること、及び特定の値ｉがｈ＝Ｈ（ｉ）にハッシュすることを知る。
８． 次いで、買い手が、合意した手数料（ａ）を含むアウトプットを含んだ、ハッシュ時間ロック契約（ＨＴＬＣ）トランザクションＴｘ_１を構築する。この出力は、２通りのやり方でアンロックされることができ、すなわち：
ｉ． 任意の時に、売り手からの署名と、ハッシュプリイメージｉとを用いて、
ｉｉ． 例えば、指定された時間又はブロック高さまで出力が消費されることを防ぐために使用され得るものであるＣＨＥＣＫＬＯＣＫＴＩＭＥＶＥＲＩＦＹ （ＯＰ＿ＣＬＴＶ）スクリプトｏｐコードを使用して、指定された時間の後に買い手からの署名を用いて、
アンロックされることができる。
９． 次いで、買い手が、このトランザクションに署名してブロックチェーンにブロードキャストし、それがブロックへとマイニングされる。
１０． 確認されると、売り手は、自身の署名とハッシュロックを解除するための値ｉを供給するトランザクションＴｘ_２を提供することによって、Ｔｘ_１の出力における手数料を請求することができ、そして、値ｉはブロックチェーン上で明らかにされる。
１１． 買い手は、最終的なバニティアドレス秘密鍵ｓｋ＝ｓｋ_Ｂ＋ｉを計算することができ、ｐｋ＝ｓｋ×Ｇである。
１２． 買い手が指定のＯＰ＿ＣＬＴＶ時間の前に値ｉを供給しない場合、売り手は（非協力的な買い手によって手数料が失われることを防ぐために）署名を提供して手数料を再請求することができる。

すると、トランザクションは、完全にアトミックでトラストレスであり、買い手は有効な値ｉを提供した場合にのみ支払いを受け、値ｉはブロックチェーン上で公然に明かされる。秘密鍵の分割により、この値は、他の誰にも役に立たず、完全な秘密鍵のセキュリティを損なわない。

用途ＩＩ
上の実装セクションで説明した本発明の例は、各々がそれぞれの、異なるブロックチェーン上に記録された交換されるべきデータを持つ二者間での私的なデータ交換に適用されることができる。

より具体的には、本発明は、アトミックトレードとしても知られた、ブロックチェーントランザクション機構を活用するトラストレスでの公正な交換プロトコルであるプライバシーを保護するクロスチェーン・アトミック・スワップに適用されることができる。このプロトコルは、第三者集中型の交換を用いずに、２つの異なるブロックチェーン上で２つの異なる暗号通貨トークンを取引するために使用される。この文脈での単語‘アトミック’は、公正な交換の性質を指し、両者がトランザクションを完了するか、あるいは両者とも完了しないかのいずれかである。

既知の基本プロトコルの一例は、以下のステップに従って実行される。安全であるために、スワップで使用される暗号通貨の両方が、ハッシュされ且つ時間ロックされた契約を可能にするスクリプト機能を持たなければならない。このスワップには、アリスとボブの二者が関与する。この例では、アリスが１ビットコインを保有しており、それをボブの１００ライトコインと取引することに合意している。
１． アリスが、ボブに送信するライトコイン公開鍵Ｐ_Ａを生成する。
２． ボブが、アリスに送信するビットコイン公開鍵Ｐ_Ｂを生成する。
３． アリスが、セキュアな乱数ｘを生成する。
４． アリスが、ｘのＳＨＡ－２５６ハッシュ：ｈ＝Ｈ（ｘ）を計算する。
５． アリスが、以下であるビットコイントランザクションＴｘ_Ａ、すなわち、
ｉ． 有効な署名 ＡＮＤ ｈにハッシュする値を用いて、１ビットコインをＰ_Ｂに支払う、
ｉｉ． ＯＲ ２４時間後に１ビットコインをアリスに払い戻す、
ものであるビットコイントランザクションＴｘ_Ａを作成する。
６． アリスが、該トランザクションをビットコインネットワークにブロードキャストする。
７． ボブが、ビットコインブロックチェーン上でＴｘ_Ａが確認されたことを観測すると、以下であるライトコイントランザクションＴｘ_Ｂ、すなわち、
ｉ． 有効な署名 ＡＮＤ ｈにハッシュする値を用いて、１００ライトコインをＰ_Ａに支払う、
ｉｉ． ＯＲ ２４時間後に１００ライトコインをボブに払い戻す、
ものであるビットコイントランザクションＴｘ_Ｂを作成する。
８． ボブが、該トランザクションをライトコインネットワークにブロードキャストする。
９． トランザクションが確認されると、アリスは、自身の署名及び値ｘを提供することによって、ライトコイン出力を請求することができる。
１０． ボブは、ライトコインブロックチェーン上で値ｘを観測すると、自身の署名及び値ｘを提供することによって、ビットコイン出力を請求することができる。

この例は、両者ともコインを手に入れる又は両者とも手に入れないのいずれかであることを確実にする。アリスはハッシュ値を生成し、彼女のみがプリイメージを知っているが、彼女は、コインを請求するためにこのプリイメージを明らかにすることを要求され、そして、それが、ボブが彼のコインを請求することを可能にする。どちらかの者が完了に向けてプロトコルに従わない場合、それらの両者がロックアウト期間後に自身のコインを再請求することができる。

上述した既知のプロトコルの１つの重大な欠点は、両方のブロックチェーン上のトランザクションが自明にリンク付け可能なことであり、いったん確認されると、固有値ｘが、永久に、両方のブロックチェーン上で公然と見えてしまう。これは、コインの交換性及びトランザクションのプライバシーの両方に影響を及ぼす。

２つのトランザクションをリンク付けないためには、各チェーン上の出力に異なるキーが使用されなければならないが、プロトコルがセキュア且つトラストレスであるために、ボブは、アリスによって、彼女が彼女のハッシュプリイメージを明らかにするときに彼が彼のコインをアンロックするのに必要な情報を教わることになる、というプルーフを与えられなければならない。

上の例で説明したキーステートメントプルーフを採用することにより、第２のブロックチェーン上のハッシュロックされた出力を、通常のｐａｙ－ｔｏ－ｐｕｂｌｉｃ－ｋｅｙ－ｈａｓｈ（Ｐ２ＰＫＨ）出力に変換することができ、トランザクションの性質を隠すとともに如何なる可能なリンクも破ることができる。

アリスが１ビットコインを保有しており、それをボブの１００ライトコインと取引することに合意しているという上の例に適用して、改良プロセスは、以下のアクションを含むことになる：
２． アリスが、ボブに送信するライトコイン公開鍵Ｐ_Ａを（秘密鍵ｓ_Ａで）を生成する。
３． ボブが、アリスに送信するビットコイン公開鍵Ｐ_Ｂを（秘密鍵ｓ_Ｂで）生成する。
４． アリスが、セキュアな乱数ｘ←Ｚ_ｐを生成する。
５． アリスが、ｘのＳＨＡ－２５６ハッシュ：ｈ＝Ｈ（ｘ）と、ｘに対応する楕円曲線公開鍵：Ｐ_ｘ＝ｘ×Ｇとを計算する。
６． アリスが、ｈ及びＰ_ｘの両方をボブにセキュアに送信する。
７． アリスはまた、ｈのプリイメージがＰ_ｘを生成した秘密鍵に等しいことのキーステートメントプルーフをボブに送信する。
８． アリスが、以下であるビットコイントランザクションＴｘ_Ａ、すなわち、
ｉ． １ビットコインを公開鍵Ｐ_Ｃ＝Ｐ_Ｂ＋Ｐ_ｘに支払う、
ｉｉ． ＯＲ ２４時間後に１ビットコインをアリスに払い戻す、
ものであるビットコイントランザクションＴｘ_Ａを作成する。
９． アリスが、該トランザクションをビットコインネットワークにブロードキャストする。
１０． ボブが、ビットコインブロックチェーン上でＴｘ_Ａが確認されたことを観測すると、以下であるライトコイントランザクションＴｘ_Ｂ、すなわち、
ｉ． 有効な署名 ＡＮＤ ｈにＳＨＡ－２５６ハッシュする値を用いて、１００ライトコインをＰ_Ａに支払う、
ｉｉ． ＯＲ ２４時間後に１００ライトコインをボブに払い戻す、
ものであるビットコイントランザクションＴｘ_Ｂを作成する。
１１． ボブが、該トランザクションをライトコインネットワークにブロードキャストする。
１２． トランザクションが確認されると、アリスは、自身の署名及び値ｘを提供することによって、ライトコイン出力を請求することができる。
１３． ボブは、ライトコインブロックチェーン上で値ｘを観測すると、楕円曲線点乗算の同形性からｓ_Ｂ＋ｘであるＰ_Ｃの秘密鍵を用いて署名を提供することによってビットコイン出力を要求することができる。

用途全般
本発明は、証明者が、検証者に対して、ステートメントが真であることを、該ステートメントに対する証拠（ｗ）を秘密にしたまま証明するものである、ステートメント（Ｓ）のゼロ知識証明又は検証に適する。秘密は、例えばハッシュ関数などの関数によって処理されることができるが、例えば公開鍵に関するステートメントの妥当性といった、暗号楕円曲線キー操作を更に含むことができる。上の例において、本発明の方法は、バニティアドレスに関するトラストレスでのＺＫＣＰを可能にするために使用されている。これはまた、例えば、パスワードの導出、例えばパスポート又は身元証明書などの有効な機械読み取り可能文書の検証、又は他のそのような機密トランザクションにも適用されることができる。

なお、上述の実施形態は、本発明を限定するものではなく、例示するものであり、当業者は、添付の請求項によって規定される本発明の範囲から逸脱することなく、数多くの代わりの実施形態を設計することができる。

請求項において、括弧内に置かれた如何なる符号も、請求項を限定するものと解釈されるべきでない。用語“有している”及び“有する”並びにこれらに類するものは、いずれかの請求項又は明細書全体に列挙されたもの以外の要素又はステップの存在を除外するものではない。本明細書において、“有する”は“含む又はからなる”を意味し、“有している”は“含んでいる又はからなっている”を意味する。

単数形での要素の参照は、それらの要素の複数形での参照を除外するものではなく、その逆もまた然りである。本発明は、幾つかの別個の要素を有するハードウェアによって、また、適切にプログラムされたコンピュータによって実装され得る。

幾つかの手段を列挙するデバイスクレームにおいて、それらの手段のうちの幾つかが、同一のハードウェアアイテムによって具現化されてもよい。特定の複数の手段が相互に異なる従属請求項に記載されているという単なる事実は、それらの手段の組み合わせが有利に使用され得ないということを指し示すものではない。

Claims (27)

1. 証明者コンピュータが、検証者コンピュータに対して、ステートメントが真であることを、該ステートメントに対する証拠（ｗ）を秘密にしたまま証明するものである、ステートメント（Ｓ）のゼロ知識証明又は検証を可能にするためのコンピュータ実装された方法であって、当該方法は、
   証明者コンピュータが検証者コンピュータに：
   関数回路を実装して、所与の関数回路出力（ｈ）及び楕円曲線点（Ｐ）に対して、前記関数回路のワイヤへの関数回路入力（ｓ）が対応する楕円曲線点乗数（ｓ）に等しいかを判定する、ように構成されたｍ個のゲート及びｎ個のワイヤを有する算術回路によって表されるステートメント（Ｓ）と、
   前記回路のワイヤについての個々のワイヤコミットメント及び／又はバッチにされたコミットメントと、
   関数回路出力（ｈ）と、
   証明キー（ＰｒＫ）と、
   を送信することを含み、
   これにより、前記検証者コンピュータが、前記回路が満たされることを決定し、前記楕円曲線点（Ｐ）を計算して、前記ステートメントを検証すること、故に、前記証明者コンピュータが前記ステートメントに対する前記証拠（ｗ）を保持していると決定することを可能にする、
   コンピュータ実装された方法。
2. 前記証明者コンピュータは、前記証拠（ｗ）の知識を証明するために、個々のワイヤコミットメントを送信し、Σプロトコルを使用して前記検証者コンピュータと通信する、請求項１に記載のコンピュータ実装された方法。
3. 前記証明者コンピュータは、前記検証者コンピュータからチャレンジ値（ｘ）を受信し、オープニングで応答する、請求項１又は２に記載のコンピュータ実装された方法。
4. 前記証明者コンピュータは、前記検証者コンピュータが前記ステートメントが真であると判定して前記楕円曲線点（Ｐ）を計算することを可能にするランダム値（ｘ）を前記検証者コンピュータに送信する、請求項１又は２に記載のコンピュータ実装された方法。
5. 前記ランダム値（ｘ）は、少なくとも１つのコミットメントの関数である、請求項４に記載のコンピュータ実装された方法。
6. 前記ランダム値（ｘ）は、前記証明者コンピュータによって生成されて前記検証者コンピュータに送信された全ての前記コミットメントの連結をハッシュすることによって計算される、請求項４又は５に記載のコンピュータ実装された方法。
7. 前記コミットメントＷ_ｉは、Ｗ_ｉ＝Ｃｏｍ（ｗ_ｉ，ｒ_ｉ）であり、
   Ｃｏｍは前記関数回路へのコミットメントであり、
   ｗ_ｉはワイヤ値であり、
   ｒ_ｉは、ワイヤコミットメントごとに異なる乱数であり、
   ｉはワイヤ種類であり、
   Ｃｏｍ（ｗ，ｒ）＝ｗ×Ｇ＋ｒ×Ｆとされ、
   Ｆ及びＧは楕円曲線点である、
   請求項１乃至６のいずれか一項に記載のコンピュータ実装された方法。
8. 前記算術回路内のワイヤｌに対する入力が、ｋｏ＝ｒ_ｌ×Ｆであり、
   ｋｏはキーオープニング入力であり、
   ｒ_ｌは乱数であり、
   Ｆは楕円曲線上の点である、
   請求項７に記載のコンピュータ実装された方法。
9. 前記検証者コンピュータは、前記回路が満たされることを確認し、楕円曲線点減算：
   ｐｋ_ｌ＝Ｃｏｍ（ｗ_ｌ，ｒ_ｌ）－ｋｏ_ｌ
   を介してワイヤｌに対する公開鍵を計算することができる、請求項８に記載のコンピュータ実装された方法。
10. 前記証明者コンピュータは、ワイヤコミットメントのバッチを送信し、各ワイヤについて楕円曲線点を計算するための乱数を生成して、前記証明キー（ＰｒＫ）を形成する、請求項１に記載のコンピュータ実装された方法。
11. 前記証拠に関する前記バッチにされたコミットメントは、
    

    

    であり、
    ｒは、前記証明者コンピュータによって生成された乱数であり、
    前記証明者コンピュータは、ワイヤ値ｗ_ｉ（ｆｏｒ ｉ＝１，…，ｎ）のベクトルｗへのコミットメントを計算し、
    ｗ_ｎは、キーオープンされるものであり、
    Ｋ_ｉは、計算された楕円曲線点であり、
    ｗ_ｉはワイヤ値であり、
    Ｆは楕円曲線上の点である、
    請求項１０に記載のコンピュータ実装された方法。
12. 前記算術回路内のワイヤｎに対する入力は、
    

    

    であり、
    ｋｏ_ｎはキーオープニング入力であり、
    ｒは乱数であり、
    Ｆは楕円曲線上の点である、
    請求項１１に記載のコンピュータ実装された方法。
13. 前記検証者コンピュータは、楕円曲線演算：
    

    

    を介して、キーステートメントワイヤの公開鍵オープニングを計算する、請求項１２に記載のコンピュータ実装された方法。
14. 前記証明者コンピュータは更に、完全にオープンにされたコミットメントを少なくとも１つのワイヤに送る、請求項１乃至１３のいずれか一項に記載のコンピュータ実装された方法。
15. 当該方法はＰｅｄｅｒｓｅｎコミットメントを使用する、請求項１乃至１４のいずれか一項に記載のコンピュータ実装された方法。
16. 前記ステートメントは、前記関数回路に対して１つの算術回路のみを使用する、請求項１乃至１５のいずれか１項に記載のコンピュータ実装された方法。
17. 前記関数回路は、ＳＨＡ－２５６ハッシュ関数を実装する、請求項１乃至１６のいずれか一項に記載のコンピュータ実装された方法。
18. 当該方法は、前記証明者コンピュータによって、暗号鍵などのデータに対するゼロ知識付帯トランザクションを可能にするために使用され、
    前記証明者コンピュータは、提供されるデータ及び受信されるデータを確認するために検証者コンピュータと連携し、前記検証者コンピュータとの通信チャンネルを確立し、
    前記証明者コンピュータは、前記検証者コンピュータから、安全なランダム秘密鍵ｓｋＢから前記検証者コンピュータが生成した楕円曲線公開鍵ｐｋ_Ｂを受信し、ｐｋ_Ｖ＝ｓｋ_Ｖ×Ｇであり、Ｇは楕円曲線点であり、
    前記証明者コンピュータは、データ＝ｐｋ_Ｖ＋ｉ×Ｇであるように、前記提供されるデータをロック値ｉで保護し、
    前記証明者コンピュータは、ｐｋ_Ｐ＝ｉ×Ｇであるそれらの公開鍵と、関数回路入力が前記ロック値ｉである前記関数回路からの出力ｆ（ｉ）と、を検証者コンピュータに送信し、
    前記証明者コンピュータは、前記関数回路への入力が、ｐｋ_Ｐに対応する秘密鍵であることを前記検証者コンピュータに証明するステートメント（Ｓ）プルーフを前記検証者コンピュータに送信して、
    前記検証者コンピュータが前記プルーフを検証し、ｐｋ＝ｐｋ_Ｖ＋ｐｋ_Ｐに対応するアドレスが合意されたパターンと一致することを確認することで、前記ロック値ｉを知ることが、データ（ｓｋ_Ｂ＋ｉ）に関する完全な秘密鍵の導出を可能にすることと、前記ロック値ｉが前記関数回路への前記関数回路入力であることと、を特定することを可能にし、
    前記証明者コンピュータは、前記証明者コンピュータからの署名と前記関数回路入力とによってアクセスされることが可能な、前記受信されるデータを含む出力を含んだトランザクションＴｘ_１を前記検証者コンピュータから受信し、
    前記証明者コンピュータは、前記トランザクションに署名して前記トランザクションをブロックチェーン上でブロードキャストし、それがブロックへとマイニングされて、前記トランザクションをアンロックするための署名及び値ｉを供給する第２のトランザクションＴｘ_２を提供することによって、前記トランザクションＴｘ_１の出力から前記データに前記証明者コンピュータがアクセスすることを可能にし、そして、前記トランザクションは、前記ブロックチェーン上で明らかにされ、
    斯くして、前記検証者コンピュータが、前記ロック値ｉを特定して、前記証明者コンピュータによって提供された前記データにアクセスすることを可能にし、
    ｓｋ＝ｓｋ_Ｂ＋ｉであり、
    ｐｋ＝ｓｋ×Ｇである、
    請求項１乃至１７のいずれか一項に記載のコンピュータ実装された方法。
19. 前記証明者コンピュータによって提供される前記データはバニティアドレスを含む、請求項１８に記載のコンピュータ実装された方法。
20. 前記検証者コンピュータから受信される前記データは暗号通貨支払を含む、請求項１８に記載のコンピュータ実装された方法。
21. 証明者コンピュータは、検証者コンピュータとのトラストレスでの公正なデータ交換を行い、
    前記証明者コンピュータは、第１のブロックチェーン上の第１のデータへのアクセスを持ち、前記検証者コンピュータは、第２のブロックチェーン上にある第２のデータへのアクセスを持ち、当該方法は、
    前記証明者コンピュータが、前記第２のブロックチェーンに対する鍵ペアを生成し、公開鍵（Ｐ_Ａ）を前記検証者コンピュータに送信し、秘密鍵（ｓ_Ａ）を保持し、
    前記証明者コンピュータが、前記第１のブロックチェーンに対する検証者公開鍵（Ｐ_Ｂ）を受信し、前記検証者コンピュータは、前記第１のブロックチェーンに対する鍵ペアを生成して秘密鍵（ｓ_Ｂ）を保持しており、
    前記証明者コンピュータが、ステートメント（Ｓ）と、１つ以上のコミットメントと、入力（Ｐ_ｘ）及び関数回路出力（ｈ）と、楕円曲線仕様とを送信し、
    前記証明者コンピュータが、前記第１のデータを共通の公開鍵アドレス（Ｐ_ｃ）に送信する第１のブロックチェーントランザクションＴｘ_Ａを作成して、該トランザクションを第１のブロックチェーンネットワーク上でブロードキャストし、該アドレスは、前記入力（Ｐ_ｘ）と前記検証者公開鍵（Ｐ_ｃ）との和によって定められ、Ｐ_Ｃ＝Ｐ_Ｂ＋Ｐ_ｘであり、
    前記証明者コンピュータが、第２のブロックチェーントランザクションＴｘ_Ｂを検証し、該トランザクションは、前記第１のブロックチェーンに前記第１のブロックチェーントランザクションＴｘ_Ａが含まれることを確認した後に、前記検証者コンピュータによって作成されて前記第２のブロックチェーンネットワーク上でブロードキャストされ、該トランザクションは、前記第２のデータを証明者公開鍵アドレス（Ｐ_Ａ）に送り、該証明者公開鍵アドレス（Ｐ_Ａ）は、
    該証明者公開鍵アドレス（Ｐ_Ａ）に関する有効な署名、
    関数回路出力（ｈ）を決定する関数回路入力プリイメージである値、
    を用いて前記証明者コンピュータによってアクセス可能であり、
    前記証明者コンピュータが、前記第２のブロックチェーントランザクションＴｘ_Ｂが前記第２のブロックチェーン上に含まれることを確認し、署名と、前記関数回路出力（ｈ）の前記関数回路入力である前記値と、を提供することによって前記第２のデータにアクセスし、
    斯くして、前記検証者コンピュータが、前記関数回路出力（ｈ）を決定する前記関数回路入力である前記値を観測し、楕円曲線点乗算の同形性からｓ_Ｂ＋ｓであるＰ_Ｃの秘密鍵を用いて署名を提供することによって前記第１のデータにアクセスすることを可能にする、
    ことを含む、請求項１乃至１７のいずれか一項に記載のコンピュータ実装された方法。
22. 交換される前記データは暗号通貨であり、前記第１のデータは第１の暗号通貨の量に対応し、前記第２のデータは第２の暗号通貨の量に対応する、請求項２１に記載のコンピュータ実装された方法。
23. 前記第１の暗号通貨はビットコインであり、前記第２の暗号通貨はライトコインである、請求項２２に記載のコンピュータ実装された方法。
24. コンピュータ実行可能命令を有したコンピュータ読み取り可能記憶媒体であって、前記コンピュータ実行可能命令は、実行されるときに、請求項１乃至２３のいずれか一項に記載の方法を実行するようにプロセッサを構成する、コンピュータ読み取り可能記憶媒体。
25. インタフェース装置と、
    前記インタフェース装置に結合された１つ以上のプロセッサと、
    前記１つ以上のプロセッサに結合されたメモリであり、当該メモリはコンピュータ実行可能命令を格納しており、該コンピュータ実行可能命令は、実行されるときに、請求項１乃至２３のいずれか一項に記載の方法を実行するように前記１つ以上のプロセッサを構成する、メモリと、
    を有するエレクトロニクス装置。
26. ブロックチェーンネットワークのノードであって、請求項１乃至２３のいずれか一項に記載の方法を実行するように構成されたノード。
27. 請求項２６に記載のノードを有するブロックチェーンネットワーク。

Images