はじめに（Introduction）
bitcoin-devのメーリングリストにTaproot proposalが、Pieter Wuilleより出ています。
中身を見ていこうと思いましたが、すでに詳しく解説されている方がいました。
ここでは、「Taprootとは」か「使い方」などについて記述していこうと思います。
※：需要があるかは不明（泣）、みんな早いなぁ（−３−）
※※※内容の不備などありましたら、指摘してくださるとありがたいです。※※※
Taprootとは
Bitcoinは、アウトプットにScriptを設定する事が出来ます。（P2SHとかP2WSH）
大きな問題として以下の２つが考えられます。
（※：他にもあると思いますが、ここでは以下の２つをあげます。）
- サイズが大きい（効率化）
- 不使用のScriptまで公開しなければならない（プライバシー）
スマートコントラクトを実装していく上で、複雑なScriptが必要となってきます。
コントラクトとしては、基本的にOR条件のScriptがいくつも連なっている場合が考えられます。
この場合、従来の方法だと全てScriptでつなげる必要があるので、サイズが大きくなります。
また、使用する時にOR条件の１つだけを使用するのに他の条件も全て記載しなければなりません。
そこで、Mark Friedenbach がMERKLEBRANCHVERIFY(bip-0116)、通称MASTを提案します。
マークルツリーのルートハッシュをアウトプットのScriptに組み込み、
使用するScriptとその他のリーフハッシュやブランチによってScriptがマークルツリーの一部である事を証明します。
証明されたScriptは通常のScriptととして処理されるという流れでこの問題を解決しようという提案です。
これは、Scriptのopcpdeとして提供されます。
Segwitが適用され、Schnorrなどが提案されてきている中、Gregory Maxwellが次の提案をします。
[bitcoin-dev] Taproot: Privacy preserving switchable scripting
ざっくりとですが、通常は公開鍵、通常でない場合はScriptにすれば良いという提案です。
要するに、<pubkey> OR <Script A> OR <Script B> OR ...の実現となります。
公開鍵もSchnorrを利用すれば、複数人の署名multisigも可能となります。
ちょっと長くなりましたがまとめると
仮想ORをマークルツリーで表現し、効率化とプライバシーを実現する技術です。
使い方
bip-taprootで提案されている使い方を見てみます。
アウトプット
BitcoinアウトプットのpkScriptにSegwitバージョン1で記述します。
51210102030405060708090a0102030405060708090a0102030405060708090a010203
51 - バージョンOP_1の0x51固定
21 - サイズ33バイトなので0x21固定
01 - EC(secp256k1)のy座標が、偶数の場合は0x00、奇数の場合は0x01
02... - EC(secp256k1)のx座標
要するに、公開鍵（Public Key）を設定します。
ただし、通常のEC（楕円曲線）で使われている、
先頭が0x020x03ではない事に気をつけてください。
次に、どのように公開鍵を作成するのか見てみます。
タグ付きハッシュ
タグ付きハッシュというものを使います。
tagは、文字列でUTF-8でエンコードした値です。
\text{hash}_\text{tag}(m)=\text{SHA256}(\text{SHA256}(\text{tag})||\text{SHA256}(\text{tag})||m) \\
使用するtagは、TapWeak、TapBranch、TapLeafの３つとなります。
TapWeakは以下のとおり。pubkeyは、0x02または0x03で始まる圧縮された形式です。
hashは、基本的にTapBranchで得られたハッシュ値となります。
\begin{align*}
& \text{hash}_\text{TapWeak}(\text{pubkey},\text{hash}) \\
& = \text{SHA256}(\text{SHA256}(\text{TapWeak})||\text{SHA256}(\text{TapWeak})||\text{pubkey}||\text{hash}) \\
\end{align*}
TapBranchは以下のとおり。hash1とhash2の大小比較をして値の小さい方を最初に連結します。
\begin{align*}
& \text{hash}_\text{TapBranch}(\text{hash1},\text{hash2}) \\
& \text{hash2がhash1より小さい場合} \\
& = \text{SHA256}(\text{SHA256}(\text{TapBranch})||\text{SHA256}(\text{TapBranch})||\text{hash2}||\text{hash1}) \\
& \text{それ以外の場合} \\
& = \text{SHA256}(\text{SHA256}(\text{TapBranch})||\text{SHA256}(\text{TapBranch})||\text{hash1}||\text{hash2}) \\
\end{align*}
TapLeafは以下のとおり。leaf_versionは0xc0固定です。
script_sizeは、scriptのバイト長です。
\begin{align*}
& \text{hash}_\text{TapLeaf}(\text{script}) \\
& = \text{SHA256}(\text{SHA256}(\text{TapLeaf})||\text{SHA256}(\text{TapLeaf})||\text{leaf_version}||\text{script_size}||\text{script}) \\
\end{align*}
Taprootの公開鍵
用意する物は、公開鍵といくつかのスクリプトです。
ここでは、pubkey、scriptA、scriptB、scriptCとします。
公開鍵pubkeyの点$P$は以下のとおりです。
$G$はジェネレーターで、$x$は秘密鍵です。
$$P=xG$$
それぞれのスクリプトに対するリーフハッシュを求めます。
\begin{align*}
& \text{leafA} = \text{hash}_\text{TapLeaf}(\text{scriptA}) \\
& \text{leafB} = \text{hash}_\text{TapLeaf}(\text{scriptB}) \\
& \text{leafC} = \text{hash}_\text{TapLeaf}(\text{scriptC}) \\
\end{align*}
マークルツリーを形成する為、ブランチを求めます。
\begin{align*}
& \text{branch1} = \text{hash}_\text{TapBranch}(\text{leafA},\text{leafB}) \\
& \text{branch2} = \text{hash}_\text{TapBranch}(\text{branch1},\text{leafC}) \\
\end{align*}
マークルツリーのルートを求めます。
\begin{align*}
& \text{root} = \text{hash}_\text{TapWeak}(\text{pubkey},\text{branch2}) \\
\end{align*}
ECの演算を行います、rootの値を$t$としたとき、求める公開鍵$Q$は以下のようになります。
$$Q=P+tG$$
これで、Taprootへ送信する事が出来るようになしました。
Scriptの検証ルール
次は、TaprootのUTXOを使用する方法です。
大きく２つあります。
※：ここでは、annexについては割愛しています。
witnessスタックが１つの場合とwitnessスタックが２つ以上の場合
witnessスタックが１つの場合
単純に、インプットに設定されている公開鍵$Q$の署名値（Schnorr）となります。
64byteか65byteの署名値となります。
署名するための値$d$は以下のとおりです。
要するに、「秘密鍵」＋「マークルツリーのルート」です。
$$d = x + t$$
hash typeが0x00の場合、省略可能で64byteになります。
それ以外のhash typeであれば、署名値の最後に付加するので65byteとなります。
Transaction digestの求め方は、segwitのもとのは異なるので注意が必要です。
署名方法は、以前に解説したbip-schnorrです。
ということは、単なるSchnorr使いたければ、$Q$に公開鍵設定すれば良い！？
witnessスタックが２つ以上の場合
こちらは、スクリプトを使う場合に使用されます。
スクリプトを解決する為のパラメータの後、最後２つがscriptとcontrol blockになります。
control blockは、33+32m byteとなります。（33byteとm個の32byte）
先頭の33byteは、公開鍵$P$とleaf_versionを表します。
この33byteをcとした時
最初の1byteを、c[0] & 0xfeしたものが、leaf_versionとなり。
((c[0]&1)+2) || c[1:33])としたものが、公開鍵$P$となります。
scriptの対するリーフハッシュを求めます。
$$\text{leaf} = \text{hash}_\text{TapLeaf}(\text{script})$$
m個の32byteからブランチを求めます。それぞれ、$e_1,\cdots,e_m$とします。
\begin{align*}
\text{branch} &= \text{hash}_\text{TapBranch}(\text{leaf},e_1) \\
\text{branch} &= \text{hash}_\text{TapBranch}(\text{branch},e_2) \\
& \vdots \\
\text{branch} &= \text{hash}_\text{TapBranch}(\text{branch},e_m) \\
\end{align*}
マークルツリーのルートを求めます。
\begin{align*}
& \text{root} = \text{hash}_\text{TapWeak}(P,\text{branch}) \\
\end{align*}
rootの値を$t$としたとき、求める公開鍵$Q$は以下のようになります。
$$Q=P+tG$$
これが、インプットに設定されている公開鍵と同じであるか判定します。
同じであれば、scriptを実行します。
scriptが正常に終了すればUTXOの使用が可能となります。
control block
先程のscriptA、scriptA、scriptAを使いたい場合、
どのようなcontrol blockを作れば良いのかを見てみます。
leaf_version付きの公開鍵を$P'$とします。
\begin{align*}
\text{scriptA} &= \{ P' || \text{leaf2} || \text{leaf3} \} \\
\text{scriptB} &= \{ P' || \text{leaf1} || \text{leaf3} \} \\
\text{scriptC} &= \{ P' || \text{branch1} \} \\
\end{align*}
拡張性
annex
witnessにannexを設定できます。
先頭が0x50で、最後に設定します。
未来の拡張用のスペースだそうです。
leaf_version
先頭2bitsと最後の1bit以外が空いています。
これも未来の拡張用スペースだそうです。
さいごに
まだまだ、論議中のbip-taprootですが、概ね以前から言われていたもとの同じように見えます。
単なる、Schnorrとしても使えそうなので、Bitcoinに採用される日が早くくると良いなと思いました。