検証可能暗号を使って論理回路を構成する離散対数OR演算子の解説

はじめに

本稿では¹で紹介されている 離散対数OR演算子というアイデアの解説をします。DLC/PTLC向けと書いてあるのですが、離散対数OR演算子自体は DLC/PTLCに関係なく使えるものになります。
また、¹は正式な論文ではなく、あくまでもアイデアの大枠であり、「証明」と本文中に書かれているものも厳密な意味での安全性の証明にはなっていないことに注意してください。

概要

「アリスが、楕円曲線上の点T_1, T_2, ..., T_nのいずれか(OR)の離散対数を知ったならば、それによって（全く無関係の）別の楕円曲線上の点Xの離散対数も知ることができる」という状況を暗号プロトコルにおいて作り出すことができるだろうか。

¹はこの問題に対して、肯定的な回答を出している。

そもそもなぜこんなことをしたいかという動機については、元々はDLCのオラクルが提供する情報を元に、それらを合成した情報によってアンロックされるビットコインのスクリプトを書きたかったからだと思われる。
しかし、この問題はDLCにとどまらず、以下の通り数多くの応用がある。

• DLCオラクルによって提供されるイベントの数値を合成し、数値間の関係に順序関係を作り出すこと
• 同上、DLCオラクルの数値を計算すること
• 単一のオラクルによらない、複数オラクルによるアンロックの実現
• ライトニングネットワークにおける複雑な支払い条件を設定すること
• エスクロー、非対話しきい値エスクロー、重み付きしきい値エスクローへの応用（これはよくわからない）
• 論理回路とブール関数の実現
• 非対話型t-of-nしきい値回路の実現
• 上記の応用の任意の組み合わせ。例えば、すべての支払条件は単一のアダプター点（後述）で表現可能になり、アダプター点同士を合成することで新しいアダプター点を作り出せる
• 理想的には、ビットコインスクリプトを一切使用しない仮想マシンを構成し、その内部でビットコインスクリプトを含めた任意の計算の実現。例えば、SPV検証や特定のビットコイントランザクションがブロックに含まれることのSPV包含証明など。

デメリットとしては、複雑なセットアップの場合、コストが非現実的なレベルで高くなること。また、このプロトコルは結局の所証明者が何を公開して何を公開しないか決定権を持つという点において、証明者を信頼しているといえる²。仮に、証明者をマルチパーティにしたとしても、証明者のマルチシグとトラストモデルとしては同じなので、このプロトコルが大きく発展することはなかったが、着想はその他多くのプロトコルに応用できる余地があると考える。

なお後にBitVM³という離散対数OR演算子よりも低コストなビットコイン上における任意スクリプトの実行プロトコルが発表された。

離散対数OR演算子の構成

以下、基本的なディフィーヘルマン（DH）鍵交換から始めて、どのように離散対数OR演算子が構成可能になるのか見てみる。

DH鍵交換

秘密情報aと公開鍵A=aGを持つアリス、秘密情報bと公開鍵B=bGを持つボブが鍵交換をして共有鍵Sを作りたいとする。

1. アリスがBを入手し、S = aB = a(bG)を計算する
2. ボブがAを入手し、S = bA = b(aG) = abG を計算する

エルガマル暗号

エルガマル暗号はDH鍵交換を使ってメッセージを暗号化する。

暗号化

ボブが公開鍵A=aGを持つアリスに対してメッセージMを暗号化する。

1. 乱数eを選択し、公開ナンスE=eGとする。
2. DH鍵交換によって共有乱数S=eAを計算する
3. 暗号文D = M + S を作成する

ボブは (D, E)をアリスに送る。

復号

アリスは(D, E)をアリスの秘密鍵aで復号したいとする。

1. 共有乱数S = aEを計算する
2. 平文M = D - S を計算する

DHタプルにおける乗法関係の証明

(G, xG, yG, xyG)という値の組(タプル)が与えられ、証明者がxを知っているときに、これらのタプルの離散対数が正しく乗法関係を満たすことを証明したいとする。検証者はxを知らず、証明者・検証者いずれもyを知らない。

証明

1. 乱数rを選ぶ
2. 公開ナンスR_1 = r GとR_2 = r(yG)をセットする
3. チャレンジ c = H(R_1 | R_2)を計算する
4. xの知識証明 s = r + cx を計算する

検証者に対して (R_1, R_2, s)を送信する。

検証

1. チャレンジc = H(R_1 | R_2)を計算する
2. s G = R_1 + c (xG)となることを検証する
3. s (yG) = R_2 + c (xyG)となることを検証する

※完全性は明らかだけど、健全性については不明。

(α)検証可能暗号の証明

ボブは(D,E)が「あるメッセージX = xGが公開鍵A=aGを持つアリスに対して暗号化されて送信された暗号文であること」を示したい。ボブはx, eを知っているが、検証者は知らない。
ボブは D = xG + eA であることと、E = eG であることを示したい。

証明

1. 乱数r_1, r_2を生成する。
2. 公開ナンスR_1 = r_1 G, R_2 = r_2 A, R_3 = r_2 G, R_4 = R_1 + R_2を設定する。
3. チャレンジ c = H(R_3 | R_4)を計算する
4. xの知識証明 s_1 = r_1 + cx を計算する
5. eの知識証明 s_2 = r_2 + ce を計算する

(R_3, R_4, s_1, s_2)を検証者に送る。

検証

1. チャレンジc = H(R_3 | R_4)を計算する
2. s_1 G + s_2 A = R_4 + c Dとなることを検証する
3. s_2 G = R_3 + c Eとなることを検証する

※完全性は明らかだけど、健全性については不明。

(β)検証可能暗号によって、証明者が平文となる点の離散対数を知っており、かつそれを暗号化していることの証明

ボブは上記の「検証可能暗号の証明」に X = xG の証明を追加する。

証明

1. 乱数r_1, r_2を生成する。
2. 公開ナンスR_1 = r_1 G, R_2 = r_2 A, R_3 = r_2 Gを設定する。
3. チャレンジ c = H(R_1 | R_2 | R_3)を計算する
4. xの知識証明 s_1 = r_1 + cx を計算する
5. eの知識証明 s_2 = r_2 + ce を計算する

(R_1, R_2, R_3, s_1, s_2)を検証者に送る。

検証

1. チャレンジc = H(R_1 | R_2 | R_3)を計算する
2. s_1 G = R_1 + c Xとなることを検証する
3. s_2 G = R_3 + c Eとなることを検証する
4. s_2 A = R_2 + c (D - X)となることを検証する

※完全性は明らかだけど、健全性については不明。検証時の2.において、エルガマル暗号では平文として扱われていたXを使っているが、離散対数OR演算子のプロトコルではXをそもそも検証者に公開するので問題ないということっぽい。

(γ)離散対数の検証可能暗号

離散対数として用いる値xを等しいサイズlビットの小さなセグメントに分割する。例えば、xを8ビットごとに分割する。

暗号化

1. すべてのセグメントx_kに対して、
   1. x_kを暗号化し、(D_k, E_k) = (x_k G + e_k A, e_k G)とする。
   2. Bulletproof ⁴による数値範囲の証明を行い、D_kが2^lより小さい値(x_k)を使ったピダーセンコミットメントである証明を作成する。
   3. 「(α)検証可能暗号の証明」によって、(D_k, E_k)の検証可能暗号の証明を作成する。
2. 「(β)検証可能暗号によって、証明者が平文となる点の離散対数を知っており、かつそれを暗号化していることの証明」によって、(\hat{\sum}{D_k}, \hat{\sum}{E_k})に対する証明を作成する。ここで \hat{\sum}は単純な和ではなく、セグメント分割したx_kの離散対数同士を足し合わせてxを復元するための重み付き和である。例えば最も単純なケースで、xを1ビットごとに分割する場合、 \hat{\sum} x_k = \sum x_k \times 2^{k-1}となる。これによって、証明者が離散対数xを知っており、かつそれを暗号化していることの証明が可能になる。

検証

1. すべての暗号化されたセグメント (D_k, E_k)に対して
   1. D_kのBulletproofを検証する。
   2. 「(α)検証可能暗号の証明」によって、(D_k, E_k)の検証可能暗号の証明を検証する。
2. (\hat{\sum}{D_k}, \hat{\sum}{E_k})を計算する。
3. 「(β)検証可能暗号によって、証明者が平文となる点の離散対数を知っており、かつそれを暗号化していることの証明」によって、(\hat{\sum}{D_k}, \hat{\sum}{E_k})に対する証明を検証する。

復号

アリスが復号する。

1. すべての暗号化されたセグメント (D_k, E_k)に対して
   1. x_k G = D_k - a E_kによって復号する
   2. x_k Gの離散対数 x_kをブルートフォースで導出する。
2. x = x_1 | x_2 | ... として xを求める。

離散対数OR演算子

上記から、離散対数OR演算子を構成する。

「アリスが、楕円曲線上の点T_1, T_2, ..., T_nのいずれか(OR)の離散対数を知ったならば、それによって（全く無関係の）別の楕円曲線上の点Xの離散対数も知ることができる」ということを表現したい。

アリスとボブは、「(γ)離散対数の検証可能暗号」によってこのようなXを構成できる。

1. ボブは、ランダムシークレットxを選択し、X=xGをアリスに送る。
2. それぞれのT_iに対して
   1. ボブは xをT_iを公開鍵として暗号化し、アリスに送る。
   2. ボブはさらに、その暗号文が「Xの離散対数を公開鍵T_iをターゲットとして暗号化したものであること」の証明を「(γ)離散対数の検証可能暗号」によって作成し、アリスに送る。
3. アリスはこれらの証明を検証し、もしT_iのいずれかの離散対数を知ったならば、xを復号することができることを確認する。

これによって、T_iの離散対数のいずれかの知識をXの離散対数の知識に置き換えることが可能になる。

ブール関数への応用

上記はOR演算子のみを扱ったが、いくつかの点の離散対数を選択的に公開することによって、最終的な点の知識を得るということが可能になるならば、それは論理回路・ブール関数として扱えることを意味する。

以下、この離散対数OR演算子を使ってNANDゲートを構成する例を見てみる。このようにして作られたNANDゲートを組み合わせることで、任意の論理回路を構成することが可能になる。

NANDゲートの構成

今、離散対数OR演算子のプロトコルにおいて、ボブが A_0 = a_0 G, A_1 = a_1 G , B_0 = b_0 G , B_1 = b_1 Gの4つの点の離散対数を持っているとする。ボブはa_0, a_1のうちいずれか一つ、またb_0, b_1のうちいずれか一つの離散対数をアリスに対して公開するとする。

アリスは 以下の通り、対応する点を計算する。

C_1 = A_0 + B_0: NAND(0, 0) = 1
C_2 = A_0 + B_1: NAND(0, 1) = 1
C_3 = A_1 + B_0: NAND(1, 0) = 1
C_4 = A_1 + B_1: NAND(1, 1) = 0

さらに、このC_1,...,C_4を使って、NAND関数の結果となる点(D_0, D_1)を以下のように作成できる。

D_0 = C_4
D_1 = C_1\ \text{or}\ C_2\ \text{or}\ C_3 (OR演算子による)

もし、ボブが(a_0, b_0)を公開したならばアリスはD_1の離散対数を知ることになる。また、ボブが(a_1, b_1)を公開したならばアリスはD_0の離散対数を知ることになる。

このようにして、自由に組み立て可能な変数の組を得ることができるので、論理回路が構成可能になる。

このようにして合成可能になる点のことをアダプター点と呼ぶことにする。
アダプター点を合成することで、回路全体を1として評価する入力が与えられた場合のみアンロック可能なスクリプトを用意することができるようになる。

マルチパーティOR演算子

証明者ボブが複数人(n人)であるようなケースを考える。ボブは離散対数OR演算子を作るときにXをX = \sum_{i=1}^n X_iとなるようにし、それぞれn人のボブがXの代わりにX_iをアリスに対して送信するような離散対数OR演算子を構成すればいい。

n人のボブが互いを信頼していなかったとしても、全員が協力して構成した場合のみ、結果的にアリスがXの離散対数を得ることができるようになる。

感想

楕円曲線上の点の合成だけですべてを表現しようとするのはシンプルで面白いです。分割して暗号化した後ブルートフォースするのはあまり従来の暗号プロトコルにない発想だと思いました。
証明者へのトラストモデルを少し改良することで発展する可能性はありそうです。

参考文献