関数型暗号を用いてビットコインのコンセンサスを変更せずにコベナンツを実現する

Table of Contents

はじめに

この記事では、Jeremy Rubinによって提案された「関数型暗号を用いてビットコインのコンセンサスを変更せずに実現可能なコベナンツ(CTV)」¹について解説します。

このスキームは関数型暗号に依存していますが、現在実用的な範囲で利用できる関数型暗号は存在しないため、「もし関数型暗号が将来実現できたら、コンセンサス変更なしでもコベナンツ²も実現できる」ということを言っているだけであり、直ちに現在のビットコインネットワークでコベナンツが実現できるわけではありません。

関数型暗号とは

この記事や元のドキュメント¹で扱われている関数型暗号(FE)は、いわゆる IBE (Identity-Based Encryption: IDベース暗号), ABE (Attribute-Based Encryption: 属性ベース暗号), IPE (Inner-Product Encryption: 内積暗号)³とは別物です。

ここで言うFEは、関数型暗号について解説したサーベイ論文⁴によれば、任意の入出力を持つ関数の回路自体を暗号化・秘匿化し、その秘匿化した回路に対して、別のパーティが別の鍵で暗号化した入力を与えることで、復号された値が導出できるような暗号アルゴリズムです。FEはIBE, ABE, IPEを包含しており、FEが実現できるならばFEを使ってIBE, ABE, IPEをすべて実現できるような概念です。

具体的には以下のようなメソッドを持つアルゴリズムになります。

(I) $\text{KeyGen}() \rightarrow (k, K)$
(II) $\text{EncryptFunc}(k, F: A \rightarrow B) \rightarrow q$
(III) $\text{Encrypt}(K, A) \rightarrow c$
(IV) $\text{Decrypt}(q, c) \rightarrow B$

(I)は関数Fの暗号化用の鍵kと、関数入力値Aの暗号化用の鍵Kを生成します。
(II)は関数Fを鍵kを使って暗号化し、暗号化された関数qを出力します。
(III)は関数入力値Aを鍵Kで暗号化して暗号化された入力値cを出力します。
(IV)はqとcを使って、関数Fに入力Aを与えたときの出力Bを、FやAを知ることなく出力します。

さらに、このような関数を使い、カリー化(currying)によって、複数の入力値を持つ関数を構成することができます。

(V) $\text{EncryptFuncMultiArg}(k, F: (A_1, A_2) \rightarrow B) \rightarrow q$
すなわち、
$F_1(A_1) \rightarrow F_2, \text{EncryptFunc}(k, F_1) \rightarrow q_1$
$F_2(A_2) \rightarrow B, \text{EncryptFunc}(k, F_2) \rightarrow q_2$

であるとき、
$\text{EncryptFuncMultiArg}(k, F: (A_1, A_2) \rightarrow B) \rightarrow q := (q_1, q_2)$ と定義します。そして、DecryptMultiArgも以下のように定義すれば、復号ができます。

(VI) $\text{DecryptMultiArg}(q =(q_1, q_2), c_1, c_2) \rightarrow B := \text{Decrypt}(q_1, c_1)(\text{Decrypt}(q_2, c_2))$

なおIBE, ABE, IPEについてはすべて楕円曲線ペアリングもしくはLWE問題の困難性に依存しており、保守的な暗号学的仮定のみでの実現はできていないです。

CTV(BIP119)

CTV: Check Template Verify(BIP119)はコベナンツを実現するためのBIPで、特定のテンプレートにマッチするようなトランザクションによってのみ、utxoを消費することができるようにする提案です。

関数型暗号を使ったシンプルなCTVコベナンツ

セットアップ

まずFEの鍵を生成します。
$(m, M) \leftarrow \text{KeyGen}()$

次に楕円曲線暗号の秘密鍵・公開鍵ペアを生成します。
$(p, P) \leftarrow \text{Secp256k1KeyGen}()$

楕円曲線暗号の秘密鍵pを、FEの入力を暗号化する鍵Mを使って暗号化します。
$C_p \leftarrow \text{Encrypt}(M, p)$

CTV(BIP119)における、トランザクションテンプレートのハッシュ値を CTVHash(TX)とし、その値を楕円曲線暗号の秘密鍵pに加算することで、CTVの特定のTX専用の秘密鍵 UniqueSecKey(p, TX)を定義します。
すなわち、
$\text{UniqueSecKey}(p, \text{TX}) := \text{Add}(p, \text{CTVHash}(\text{TX}))$
また、同様にUniqueSecKey(p, TX)に対応した公開鍵 UniquePubKey(P, TX)も定義します。
$\text{UniquePubKey}(P, \text{TX}) := \text{TweakAdd}(P, \text{CTVHash}(\text{TX})) = P + \text{CTVHash}(\text{TX}) G$

FEで暗号化する対象の関数は、次のように、トランザクションに対して対応する秘密鍵で署名するような2変数関数として定義します。（なお、後述しますがトランザクションの構築において秘密鍵以外の情報がほしければ、それを引数として追加することも可能です）

$F(p, \text{TX}) := \text{ECDSASign}(\text{UniqueSecKey}(p, \text{TX}), \text{TX})$

そして、実際にこの関数Fを、暗号化鍵mで暗号化したものを $C_F$ とします。
$C_F = \text{EncryptFuncMultiArg}(m, F)$
この時点でm, pを削除して、誰もm, pにアクセスできないようにしておきます。
その後関数FにpとTXをそれぞれ暗号化したものを代入し、適用するとTXに対する署名値が得られます。もしm, pがすでに存在しないならば、 $C_F$ はCTVに従って署名する唯一の方法になります。

$\sigma = \text{DecryptMultiArg}( C_F, C_p, \text{Encrypt}(M, \text{TX}))$

複雑なCTV実現のための改良

暗号化対象の関数の内部におけるスクリプト実行検証

単純な内部での実行

関数Fの引数には秘密鍵とトランザクションだけではなく、署名条件I（特定のスクリプト実行環境上における、インスタンス化された条件）と、条件を満たすことを確認する引数Vを含めることができます。

すると以下のようにFを記述し直すことができます。

def F(p, I, TX, V)
    If E_I(TX, V):
        return Sign(Tweaked(p, E_I), TX)
    Else:
        return null

従来は、与えられた秘密鍵でトランザクションに署名していただけでしたが、条件を満たす場合のみ署名するように強制することができます。これによってコベナンツが実現されます。

ゼロ知識証明を使った実行条件の記述

上記では関数の内部に直接署名の実行条件を記述していましたが、以下のように、関数の中に入れるのは実行条件が満たされることのゼロ知識証明の検証だけにすることも可能です。

def F(p, I, TX, ZKP):
    If ZKPVerify(E_I)(TX, ZKP):
        return Sign(Tweaked(p, E_I), TX)
    Else:
        return null

その場合、実際に行う証明は外部で実行すればいいことになり、複雑な関数を都度暗号化する必要がなくなります。

def ZKProve(E, TX, V)
    # 証明は外部で実行

CTVの実現

コベナンツ入金

スクリプトの実行環境Eと公開鍵Pを選びます。
実行環境Eの中で、送金可能となる条件を決め、その条件をスクリプトで表現したインスタンスIを考えます。実際にバイト列として表現されるテンプレートを $E_I$ とします。
$\text{UniquePubKey}(P, E_I)$ を計算します。
3.で作成した公開鍵に対応したアドレスAに送金します。