Bitcoinのアップデート「Taproot」は本当に安全なのか？

Table of Contents

はじめに

この記事ではTaprootの安全性の証明を述べます。まず、Taprootの歴史、記号の定義、アルゴリズムを述べます。
次に、安全性の証明におけるTaprootのアルゴリズムを定義し、定理を述べ最後にその証明を行います。

Taprootの歴史

Bitcoinのアウトプットに設定されるScriptのサイズを小さくし(効率化)、
不使用のScriptを公開しないよう(プライバシー)提案されたのがTaprootである。

2018年1月に、Bitcoin Core開発者かつBlockstream社の元CTOであるGregory Maxwellにより、Taprootは提案された。
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html

次に2018年4月に、今回扱うAndrew Poelstraによる安全性の証明が公開された。
https://github.com/apoelstra/taproot/blob/master/main.pdf

記号の定義

以上のようなマークルツリーを考えるときに、
$h=Hash(h_0\|h_1)\\h_0=Hash(h_00\|h_01)\\h_1=Hash(h_10\|h_11)$
と表す。
セキュリティパラメータを $\lambda$ として
離散対数をオーダー $p(\lambda)$ で解くことができるアルゴリズムが確率 $neg(\lambda)$ を除いて存在しない巡回群 $\mathscr{G}=\langle G \rangle$ と
アウトプットの長さが $q(\lambda)$ のランダムオラクルとしてモデリングされた２つのハッシュ関数 $H^{pk}$ , $H^m$ を定義する。

離散対数の定義は以下。
$b$ を $G$ の生成元とすれば、 $\forall g \in G$ は $k \in \mathbb{N} , g=b^k$ と表せる。
また $g$ を表現する２つの整数 $k_1,k_2$ は $n$ を法として合同だから、
$\\log_b:G\rightarrow \mathbb{N}/n\mathbb{N}$ なる関数を定義でき、 $b$ を底とする離散対数と定義する。

また、 $\beta=(KeyGen^\beta,Sign^\beta,Verify^\beta)$ を署名スキームとする。

またランダムオラクルの定義は以下。

$H:\{0,1\}^l\rightarrow \{0,1\}^k$ が以下を満たす時Hをランダムオラクルと呼ぶ。
1.過去に定めた $H(x)$ は一意に決定され
2. $H(x)$ が未定義のときには $\{0,1\}^k$ からランダムに値を決める。
("デジタル署名の証明可能安全性"より)

定理の証明では、攻撃者と挑戦者の間のゲームを想定する。

このゲームでは、「挑戦者が用意した署名値」を攻撃者が偽造しようとする。(暗号系の安全性検証)

Taprootのアルゴリズムにおける公開鍵

下図の $root$ の値を $t$ として公開鍵 $Q=P+tG$
ただし $hash_{tag}(m)=SHA256(SHA256(tag)\|SHA256(tag)\|m)$

出典：https://qiita.com/tnakagawa/items/0ca27450331183ea3509

安全性の証明におけるアルゴリズムの定義

$TR^\beta$ と記述される $\beta$ のTaprootを以下4つのアルゴリズムとして定義する。

1 鍵生成

$KeyGen(b)$ はbit- $b$ を入力して、keypair $(sk_0,sk_1,pk)$ を出力する。
まず、 $sk^\alpha\xleftarrow{\char36 }\mathbb{Z}/p(\lambda)\mathbb{Z}$ を選択し、
$pk^\alpha\xleftarrow{\char36 }sk^\alpha{G(\lambda)}$ を計算する。
もし $b=0$ ならば、アウトプットは $(sk^\alpha,\bot,pk^\alpha)$
もし $b=1$ ならば、 $(sk^\beta,pk^\beta)\leftarrow KeyGen^\beta$ で
$\varepsilon\leftarrow H^{pk}(pk^\beta\|pk^\alpha)$
このときアウトプット $sk_0\leftarrow sk^\alpha + \varepsilon\\sk_1=(sk^\beta,pk^\alpha,pk^\beta)\\pk\leftarrow pk^\alpha+\varepsilon G$

2 署名出力1

$Sign^1(sk_0,m)$ は秘密鍵 $sk_0$ ,メッセージ $m$ を入力しアウトプットである署名 $\sigma$ を以下のように出力する。
$k\xleftarrow{\char36 }\mathbb{Z}/p(\lambda)\mathbb{Z}\\R\leftarrow kG\\pk\leftarrow sk_0G\\e\leftarrow H^m(pk\|R\|m)$ を計算し $\sigma=(R,k+esk_0)$ を出力する。

3 署名出力2

$Sign^2(sk_1=(sk^\beta,pk^\alpha,pk^\beta),m)$ は秘密鍵 $sk_1$ ,メッセージ $m$ を入力し、署名 $\sigma$ を以下のように出力する。 $\sigma^\beta=Sign^\beta(sk^\beta,m)$ を計算し、 $\sigma=(pk^\alpha,pk^\beta,\sigma^\beta)$ を出力する。

4 検証

$Verify(pk,\sigma,m)$ は公開鍵 $pk$ ,署名 $\sigma$ ,メッセージ $m$ を入力しbit $b$ を以下のように出力する。
もし $\sigma=(R,s)$ ならば $e\leftarrow H^m(pk\|R\|m)$ を計算し、 $sG=R+epk$ のときに限り受諾する。もし $\sigma=(pk^\alpha,pk^\beta,\sigma^\beta)$ ならば、まず $pk=pk^\alpha+H^{pk}(pk^\beta\|pk^\alpha)G$ を確認し、もしそうならば、 $Verify^\beta(pk^\beta,\sigma^\beta,m)$ のときに限り受諾する。

定理

定理1

もし離散対数問題が $\mathscr{G}$ において困難かつ、 $\beta$ が偽造不可能ならば、 $TR^\beta$ は敵対者 $\mathscr{A}$ と挑戦者 $\mathscr{C}$ の間で以下のゲームにおいて偽造不可能である。

ゲーム

敵対者 $\mathscr{A}$ が bit $b$ を選び、挑戦者 $\mathscr{C}$ に送信する。 $\mathscr{C}$ は $KeyGen(b)$ により生成された公開鍵 $pk$ を返す。

$\mathscr{A}$ は、 $i\in \{1,2,...,q\},\lambda$ についての多項式で拘束される $q$ に対して定義される署名クエリ $(b_i,m_i)$ を送信する。 $\mathscr{C}$ は $Sign^b$ により生成される有効な署名 $\sigma_i$ を返す。

$\mathscr{A}$ は $Verify(pk,\sigma_*,m_*)$ が受諾されるような署名 $(\sigma_*,m_*)$ を再送する。
もし $\beta$ が存在的偽造不可能(existentially unforgeable)ならば全ての $i$ に対して $(\sigma_*,m_*)≠(\sigma_i,m_i)$ を得る。そうでなければ全ての $i$ に対して $m_*\neqm_i$ を得られる。

解説

要するに、攻撃者はTaprootの鍵パスとスクリプトパスそれぞれについて、セキュリティパラメータが許す限りいくらでも事前に任意のメッセージに対する有効な署名を入手できる。この得られた有効な署名の情報を使って新しい有効な署名を作り出すことができれば攻撃者が勝利する。
ただし、新しい有効な署名はこれまでに得られたメッセージと署名のペアをそのまま提出してはならない。また、存在的偽造不可能でない場合は、メッセージだけを改変して署名を偽造することもできないはずである。

証明

この定理の証明は２つの補題からなる。

安全性の証明では以下のような方法が使われることに注意せよ。

暗号方式が用いられるときに妥当な情報を入手できる攻撃者が、
攻撃に成功したときに矛盾が生じることを示すやり方が用いられる。
http://www.tj.chiba-u.jp/~wkishi/cryptography.htmlhttp://www.tj.chiba-u.jp/~wkishi/cryptography.html

補題1

敵対者 $\mathscr{A}$ が確率 $\varepsilon$ で $Sign^2$ の形で偽造をアウトプットするならば、確率 $\varepsilon - neg(\lambda,q)$ で $\beta$ の偽造を生成できる。

補題1の証明

$\beta$ -挑戦者にアクセスできる挑戦者 $\mathscr{C}$ 、敵対者 $\mathscr{A}$ の存在を仮定する。
まず $\mathscr{C}$ は全てのランダムオラクルクエリに一様に独立に返答する。

$\mathscr{C}$ は独立でランダムな鍵ペア $(sk^\alpha,pk^\alpha)$ を選択する。
・もし $b=0$ ならば、 $\mathscr{C}$ は $pk^\alpha$ を $\mathscr{A}$ に送信し $sk=sk^\alpha$ と保存する。
・もし $b=1$ ならば、 $\mathscr{C}$ は公開鍵 $pk^\beta$ を $\beta$ 挑戦者に要求し、 $pk=pk^\alpha +H^{pk}(pk^\beta\|pk^\alpha)G$ を計算し、 $\mathscr{A}$ に送信する。
$\mathscr{C}$ は $sk=sk^\alpha +H^{pk}(pk^\beta\|pk^\alpha)$ と保存する。

署名クエリ $(b_i,m_i)$ が与えられると、 $\mathscr{A}$ は以下のように振る舞う。
もし $b_i=0$ ならば $Sign^1(sk,m_i)$ を実行し $\sigma_i$ を返す。
もし $b_i=1$ かつ $b=0$ ならば $\bot$ を返す。
もし $b_i=1$ かつ $b=1$ ならば $\beta$ 挑戦者に $m_i$ の問い合わせをして $\sigma^\beta_I$ を獲得し、 $\sigma_i=(pk^\alpha,pk^\beta,\sigma^\beta)$ を返答する。

最後に $\mathscr{A}$ は $Sign^2$ の形で $\sigma_*=(pk^\alpha_*,pk^\beta_*,\sigma^\beta_*)$ を満たす署名 $(\sigma_*,m_*)$ を返す。
更に、 $\sigma^\beta_*$ は鍵 $pk^\beta_*$ と $pk=pk^\alpha_* +H^{pk}(pk^\beta_*\|pk^\alpha_*)G$ と共に $m_*$ に有効な署名となる。
まず、 $H^{pk}$ がランダムオラクルとしてモデリングされ、 $\mathscr{A}$ は多項式回問い合わせすることより $(pk^\alpha_*,pk^\beta_*)=(pk^\alpha,pk^\beta)$ がごく僅かな確率を除いて成り立つ。
ゆえに、
$(\sigma,m_*)$ が $TR^\beta_*$ の偽造であるときに限り $(\sigma^\beta_*,m_*)$ が $\beta$ の偽造となるように、 $\sigma^\beta_*=\sigma^\beta_i$ のときに限り $\sigma_*=\sigma_i$ が成り立つ。

補題2

敵対者 $\mathscr{A}$ が確率 $\varepsilon$ で $Sign^1$ の形で偽造をアウトプットするならば、確率 $\varepsilon - neg(\lambda,q)$ で $(\mathscr{G},G,H^m)$ でのシュノア署名の偽造を生成できる。

補題2の証明

$\mathscr{C}$ は以下のように振る舞う。
まず、ランダムオラクル $H^S$ へのアクセスでき、 $s=R+eP,P=H^S(P\|R\|m)$ を満たす署名 $(s,R)$ を期待するシュノア署名への挑戦者 $\mathscr{S}$ にアクセスできる。
$\beta$ 挑戦者にアクセスできる敵対者 $\mathscr{A}$ の存在を仮定する。
まず $\mathscr{C}$ は全てのランダムオラクルクエリに一様に独立に返答する。
もし $b=0$ ならば $\mathscr{C}$ は $\mathscr{S}$ から $\mathscr{A}$ に公開鍵を転送し、全ての $b_i=1$ の署名に $\bot$ を返し、
それ以外の場合には、全ての署名を $\mathscr{S}$ に、 $H^m$ のクエリを $H^S$ に転送し、得られた偽造をシュノア偽造として提示する。

$Sign^1(sk,m_i)$ を実行し $\sigma_i$ を返す。
もし $b_i=1$ かつ $b=0$ ならば $\bot$ を返す。
このとき証明はすぐに得られるので、以下 $b=1$ の場合の証明を行う。

$\mathscr{C}$ は $\mathscr{S}$ から公開鍵 $pk^\alpha$ を得られ、 $(sk^\beta,pk^\beta)\leftarrow　KeyGen^\beta$ を選び、 $pk=pk^\alpha +H^{pk}(pk^\beta\|pk^\alpha)G$ を計算する。 $\mathscr{C}$ は $\mathscr{A}$ に $pk$ を送信する。

$\mathscr{C}$ は $H^{pk}$ クエリに一様にランダムに返答する。 $\mathscr{C}$ は $pk$ を $pk^\alpha$ に置き換えて $H^{m}$ クエリに返答する。その逆の場合は $H^{S}$ クエリに転送する。

$\mathscr{C}$ は署名クエリ $(b_i,m_i)$ に以下のように返答する。
もし $b_i=1$ ならば $\mathscr{C}$ は $Sign^2$ の形で $\sigma_i\leftarrow Sign^2 ((sk^\beta,pk^\alpha,pk^\beta),m_i)$ を得られ、返す。
もし $b_i=0$ ならば $\mathscr{C}$ は $\mathscr{S}$ から $m_i$ に関する署名 $(s_i,R_i)$ を要求する。
$e_i=H^S(pk^\alpha\|R\|m_i)$ として、 $\mathscr{C}$ は $e_iH^{pk}(pk^\beta\|pk^\alpha)$ を $s_i$ に加え $s_i^\prime$ を得られ、 $\sigma_i=(s_i^\prime,R_i)$ を返答する。
$s_i^\prime G=s_iG+e_iH^{pk}(pk^\beta\|pk^\alpha)G\\=R_i+e_i(pk^\alpha +H^{pk}(pk^\beta\|pk^\alpha)G)\\=R_i+e_ipk$
より、
$\sigma_i$ は有効な署名となる。
しかし $\mathscr{C}$ の $H^m$ への返答により、 $e_i=H^S(pk^\alpha\|R\|m_i)=H^m(pk\|R\|m_i)$ が保証され、これは $TR^\beta$ の検証式となる。

$\mathscr{A}$ は $Sign^1$ の形で $\forall i,(\sigma_*,m_*)≠(\sigma_i,m_i)$ を満たす偽造 $(\sigma_*,m_*)$ を返し、 $Verify(pk,\sigma_*,m_*)$ を受諾する。
$(s_*-e_*H^{pk}(pk^\beta\|pk^\alpha))G\\=R_*+e_*pk-H^{pk}(pk^\beta\|pk^\alpha)G\\=R_*+e_*pk^\alpha$ から $(s_*-e_*H^{pk}(pk^\beta\|pk^\alpha),R_*)$ が有効なシュノア署名で、 $\mathscr{S}$ に対する署名クエリの出力と等しくない。