# Verkle Trees 図解

[Verkle trees](https://vitalik.ca/general/2021/06/18/verkle.html)

**目標** トライ木において, その commitment (例えば Merkle root hash) と, 指定された leaf node にどんな値が格納されているかを検証可能にするための proof (例えば Merkle proof) を作成する. その上で proof はできる限り短くしたい.

**結果** 各 internal node に対応する値は, その子 node たちの vector commitment とし, vector commitment の inclusion proof を root までの path に沿って列挙したものを proof とする.

## 概説


注: 「1 の d 重根」(root of unity) は必ずしも複素数の話をしようとしているわけではない.

注: 今回は $f(\omega^i) = A_i$ としているが, 単に $f(i) = A_i$ のようにしてもよい. その場合, 有限体の位数には制限がなくなるが, 計算量はおそらく増える.

**例(i)** まずは, 1 層のトライ木について考える.


**例(ii)** 2 層のトライ木に関する inclusion proof について考える.

<!-- | key | value |
| ------ | ----- |
| `0x00` | `0x5` |
| `0x01` | `0x7` |
| `0x02` | `0x3` |
| `0x13` | `0x2` |
| `0x2e` | `0x6` | -->


B_0 の子 A_0 A_1, A_2 は leaf node. B_0 のcommitment $\mathrm{Com}(B_0)$ と A_0 が B_0 の子であるという proof $\pi_{A_0}$ が生成できる.


B_0 が internal node なので, 対応する値として $\mathrm{Com}(B_0)$ を用いる. B_1, B_2 は leaf node. C の commitment $\mathrm{Com}(C)$ と B_0 が C の子であるという proof $\pi_{B_0}$ が生成できる.


最終的に, A_0 が C の孫であるという proof は, 各階層での inclusion proof を path に沿って並べていくことで完成し, 他の sibling については気にしなくて良い. この性質は分岐の数を増やすほど有利に働く. ただし, 分岐を増やしすぎると Verkle tree の構成に時間がかかる.


具体的に今回の Verkle proof $\langle \pi_{A_0}, \pi_{B_0} \rangle$ の検証には,

$$\langle \mathrm{Com}(C), k_0, [(v_0, \pi_{A_0}), (\mathrm{Com}(B_0), \pi_{B_0})] \rangle$$

という 6 つの値が必要になる. ただし, $k_0$ は leaf の位置を指定するための path, $v_0$ はその位置に格納された値とする (今回は $k_0 =$ `0x00`, $v_0 =$ `0x5`). ここで, 複数の vector commitment の proof をまとめる inner product argument (IPA) という手法を用いて, $\pi_{A_0}, \pi_{B_0}$ を $\pi$ にまとめて

$$\langle \mathrm{Com}(C), k_0, [v_0, \mathrm{Com}(B_0)], \pi \rangle$$

という 5 つの値にすることができる. n, k に関する proof サイズのオーダーが減るわけではないが, Verkle tree が深いときには約半分になる. IPA（内積証明）については下記の Proof という章で解説されている.

[PCS multiproofs using random evaluation](https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html)

## What's next?

- [検証コスト](https://hackmd.io/@totorozk/B1d5w31KY)
- [仕様](https://hackmd.io/@totorozk/BkArU9fKt)
- [実装詳細](https://hackmd.io/@totorozk/HyUg8OnFt)