bip-taproot

# はじめに（Introduction）

bitcoin-devのメーリングリストに[Taproot proposal](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html)が、Pieter Wuilleより出ています。

- [bip-taproot](https://github.com/sipa/bips/blob/bip-schnorr/bip-taproot.mediawiki)

<!--
- [bip-tapscript](https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki)
-->

中身を見ていこうと思いましたが、すでに詳しく解説されている方がいました。

- [BitcoinにTaprootを導入するBIPドラフトbip-taproot](https://techmedia-think.hatenablog.com/entry/2019/05/11/232625)

<!--
- [TaprootのアウトプットのスクリプトTapscriptに適用される新しいスクリプトルールを定義したBIPドラフトbip-tapscript](https://techmedia-think.hatenablog.com/entry/2019/05/13/133541)
-->

ここでは、「Taprootとは」か「使い方」などについて記述していこうと思います。
※：需要があるかは不明（泣）、みんな早いなぁ（−３−）

__<font color="red">※※※内容の不備などありましたら、指摘してくださるとありがたいです。※※※</font>__

# Taprootとは

Bitcoinは、アウトプットにScriptを設定する事が出来ます。（P2SHとかP2WSH）
大きな問題として以下の２つが考えられます。
（※：他にもあると思いますが、ここでは以下の２つをあげます。）

- サイズが大きい（効率化）
- 不使用のScriptまで公開しなければならない（プライバシー）

スマートコントラクトを実装していく上で、複雑なScriptが必要となってきます。
コントラクトとしては、基本的に`OR`条件のScriptがいくつも連なっている場合が考えられます。
この場合、従来の方法だと全てScriptでつなげる必要があるので、__サイズが大きく__なります。
また、使用する時に`OR`条件の１つだけを使用するのに__他の条件も全て記載__しなければなりません。

そこで、Mark Friedenbach が[MERKLEBRANCHVERIFY(bip-0116)](https://github.com/bitcoin/bips/blob/master/bip-0116.mediawiki)、通称MASTを提案します。
[マークルツリー](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%9C%A8)のルートハッシュをアウトプットのScriptに組み込み、
使用するScriptとその他のリーフハッシュやブランチによってScriptがマークルツリーの一部である事を証明します。
証明されたScriptは通常のScriptととして処理されるという流れでこの問題を解決しようという提案です。
これは、Scriptの`opcpde`として提供されます。

Segwitが適用され、Schnorrなどが提案されてきている中、Gregory Maxwellが次の提案をします。
[[bitcoin-dev] Taproot: Privacy preserving switchable scripting](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html)
ざっくりとですが、通常は公開鍵、通常でない場合はScriptにすれば良いという提案です。
要するに、`<pubkey> OR <Script A> OR <Script B> OR ...`の実現となります。
公開鍵もSchnorrを利用すれば、複数人の署名`multisig`も可能となります。

ちょっと長くなりましたがまとめると
`仮想OR`をマークルツリーで表現し、__効率化__と__プライバシー__を実現する技術です。

# 使い方

bip-taprootで提案されている使い方を見てみます。

## アウトプット

BitcoinアウトプットのpkScriptにSegwitバージョン1で記述します。

<font color="darkorange">51</font><font color="red">21</font><font color="blue">01</font><font color="green">02030405060708090a0102030405060708090a0102030405060708090a010203</font>

<font color="darkorange">51&nbsp;&nbsp;&nbsp;&nbsp; - バージョンOP_1の0x51固定</font>
<font color="red">21&nbsp;&nbsp;&nbsp;&nbsp; - サイズ33バイトなので0x21固定</font>
<font color="blue">01&nbsp;&nbsp;&nbsp;&nbsp; - EC(secp256k1)のy座標が、偶数の場合は0x00、奇数の場合は0x01</font>
<font color="green">02... - EC(secp256k1)のx座標</font>

要するに、公開鍵（Public Key）を設定します。
ただし、通常のEC（楕円曲線）で使われている、
先頭が`0x02``0x03`ではない事に気をつけてください。

次に、どのように公開鍵を作成するのか見てみます。

## タグ付きハッシュ

タグ付きハッシュというものを使います。
tagは、文字列でUTF-8でエンコードした値です。

```math
\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`で得られたハッシュ値となります。

```math
\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`の大小比較をして値の小さい方を最初に連結します。

```math
\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`のバイト長です。

```math
\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$$

それぞれのスクリプトに対するリーフハッシュを求めます。

```math
\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*}
```

マークルツリーを形成する為、ブランチを求めます。

```math
\begin{align*}
& \text{branch1} = \text{hash}_\text{TapBranch}(\text{leafA},\text{leafB}) \\
& \text{branch2} = \text{hash}_\text{TapBranch}(\text{branch1},\text{leafC}) \\
\end{align*}
```

マークルツリーのルートを求めます。

```math
\begin{align*}
& \text{root} = \text{hash}_\text{TapWeak}(\text{pubkey},\text{branch2}) \\
\end{align*}
```

![taproot.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/29914/c03f73e2-82e2-bcdc-85f1-cdd892638b2b.png)

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](https://qiita.com/tnakagawa/items/09cb30b84e5564aaad10)です。

> ということは、単なる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$とします。

```math
\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*}
```

マークルツリーのルートを求めます。

```math
\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'$とします。

```math
\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に採用される日が早くくると良いなと思いました。