Graftroot（個人的な解釈）

# Graftroot

Graftrootについて、なんとなく理解できたので解説します。
間違いなど指摘があれば、是非頂きたいです。

## Graftroot

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html

[bitcoin-dev](https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev)という、Bitcoin-coreのメーリングリストに、[Taproot](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html)を投稿したGregory Maxwellさんが
さらに***Graftroot***というものを投稿しました。
[Taproot](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015614.html)も相当革新的であったのですが、Graftrootはもっと革新的なものであると言われてました。
私も早速読んだのですが、最初は何を言っているか理解できませんでした。

同僚のBitcoin-coreの人に教えてもらい、なんとなく理解したので共有したいと思います。

## 重要な部分

```
With graftroot, the participants establish a threshold key, optionally
with a taproot alternative, just as they do with taproot.  At any
time, they can delegate their ability to sign to a surrogate script by
signing that script (and just the script) with their taproot key, and
sharing that delegation with whomever they choose.   Later, when it
comes time to spend the coin, if the signers aren't available and the
script must be used,  the redeeming party does whatever is required to
satisfy the script (e.g. provides their own signature and a timelock,
or whatnot)  and presents that information along with the signer's
signature of the script.
```

ここが重要らしい（和訳はできませぬ・・・）

要するに、Script自体に署名すればいいんじゃね？という事らしい・・・


## 解釈（妄想）

私なりに解釈してみます、メーリングリストには式などは皆無でしたので
ここからは、私の解釈（妄想に近いもの）になります。
Schnorr signatureの集約には、MuSigのような構造にしないとセキュリティ的に危ない事がわかりました。

楕円曲線（EC）を使います。
英字小文字は数値です、英字大文字は楕円曲線の点です。
```G```は、ジェネレータ（基準点）とします。

### 秘密鍵と公開鍵

```math
x_1,...,x_n\ \text{ :private keys}\\
X_i = x_iG\ (1 \le i \le n)\\
L=\{X_1,...,X_n\}\ \text{ :public keys}\\
```

### 必要なもの
引数の異なる２つのハッシュ関数

```math
H_0(\cdot)\ \text{ :hash function}\\
H_1(\cdot)\ \text{ :hash function}\\
```

### 署名

`<script>`毎に署名が必要です。
ただし、Transaction送信後でも`<script>`を追加する事が可能です。

```math
a_i = H_0(L,X_i)\ (1 \le i \le n)\\
\tilde{X} = a_1X_1+...+a_nX_n = \sum_{i=1}^{n} a_iX_i\\
r_1,...,r_n \text{ : } R_i = r_iG\ (1 \le i \le n)\ \text{ //random}\\
R = R_1+...+R_n = \sum_{i=1}^{n} R_i \\
\text{<script>}\ \text{ :script}\\
c=H_1(\tilde{X},R,\text{<script>})\\
s_i= r_i + ca_ix_i\ (1 \le i \le n)\\
s = s_1+...+s_n = \sum_{i=1}^{n} s_i\\
\sigma = (R,s)
```

### 検証

```math
a_i = H_0(L,X_i)\ (1 \le i \le n)\\
\tilde{X} = a_1X_1+...+a_nX_n = \sum_{i=1}^{n} a_iX_i\\
c=H_1(\tilde{X},R,\text{<script>})\\
sG \overset{?}{=} R + c\tilde{X}
```

### 証明

```math
s =\sum_{i=1}^{n} \{ r_i + ca_ix_i \}\\
sG =\sum_{i=1}^{n}  r_iG + c\sum_{i=1}^{n}a_ix_iG\\
sG =\sum_{i=1}^{n}  R_i + c\sum_{i=1}^{n}a_iX_i\\
sG = R + c\tilde{X}\\
```

### 提供方法
OPコードで提供されるならば、こんな感じかなぁ？

```math
\begin{align*}
& \bf\text{ pkscript}\\
& X_1\ ...\ X_n\ \text{<public keys num>}\ \text{OP_GRAFTROOTVERIFY}\\
& \ \\
& \bf\text{signature script}\\
& \text{<param 1>}\ ...\ \text{<param m>}\ s\ R\ \text{<script>}\\
\end{align*}
```

outputに設定するのは、公開鍵だけです。
inputで必要なのは、`<script>`とその署名です。
最初に`<script>`を確認して、OKの場合に`<script>`をスタックに積んで実行します。
`<script>`を解決する為に、`m`個のパラメータが必要です。

## さいごに

これが採用されると、`MAST`終了のお知らせにも見えます・・・

メリットとしては、`<script>`がTransaction送信後にも増やせてみたり
秘匿性が高かったりと非常に良いように見えます。

デメリットを挙げるならば、使うまでに`<script>`毎の証明書を保持しておく必要がありますので、
UTXO管理なんかも煩雑になったり、そちらのデータ管理（バックアップなどを含む）が重要になってくると思われます。

あと、重要な事なので、もう一度言っておきます。
私の個人的な解釈なので、実際のものとはかけ離れている可能性が大きいです。

## 関連リンク

元になったメーリングリストの投稿
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-February/015700.html

JimmySongの解説（私はあんまり理解できていない）
https://youtu.be/gOGQdfTdlMg

有名な方が先に投稿してました・・・
[Graftrootメモ](https://qiita.com/visvirial/items/173e9bdc615a94ae3e79)