---
# System prepended metadata

title: Verkle Trees 図解

---

# 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 とする.

## 概説

![Figure 1](https://i.imgur.com/Sj3lH9q.jpg)

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

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

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

![Figure 2](https://i.imgur.com/dSiVyBC.jpg)

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

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

![Figure 3-1](https://i.imgur.com/67aSj6a.jpg)

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}$ が生成できる.

![Figure 3-2](https://i.imgur.com/emy4HvW.jpg)

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}$ が生成できる.

![Figure 3-3](https://i.imgur.com/u0zkkWO.jpg)

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

![Figure 4](https://i.imgur.com/SL7WbHC.jpg)

具体的に今回の 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)
