# Verkle trees 仕様

現存する Verkle tree 実装のデータ構造に関する仕様をまとめたものである.

参考にしたのは下記の実装である (完全な Rust 実装は見つからなかった).

- [gballet/go-verkle](https://github.com/gballet/go-verkle)

その中で用いられている IPA (内積証明) では, 下記の実装に依存している.

- [crate-crypto/go-ipa](https://github.com/crate-crypto/go-ipa)

ドキュメントによると, 実際に Ethereum Mainnet の全アカウントの状態に関する Verkle tree を作ったらしい.

Verkle tree は $k$ 分木を考え, $d$ をその深さとする. すなわち, leaf の数は最大で $n := k^d$ である. 上の実装においては, $k = 256$, $d \leq 256$ となっている. 各 leaf には $\mathbb{F}_r$ の元が格納できる. $\lvert \mathbb{F}_r \rvert < 2^{256}$ なので, 32 bytes のデータはそのままでは格納できないことに注意してください. 解決策は [key-value 型 DB に対する Verkle tree](https://hackmd.io/@totorozk/S1L-b-YOF#key-value-%E5%9E%8B-DB-%E3%81%AB%E5%AF%BE%E3%81%99%E3%82%8B-Verkle-tree) を参考にしてください. このページでは, 実装のインターフェースとデータ構造に焦点を当てて説明します. [実装詳細](https://hackmd.io/@totorozk/HyUg8OnFt)や[検証コスト](https://hackmd.io/@totorozk/B1d5w31KY)などは別にまとめてあります.

## go-verkle のインターフェース

Verkle tree の構築や更新, commitment の作成などのプロトコルを担当する. 各 tree node の構築や更新を行うには, 少なくともその node の siblings の hash 値を知っている必要がある.

$\mathsf{Insert}$ は, 指定した node の新規挿入, あるいは値の更新を行う. この段階では commitment を計算しない.

$\mathsf{ComputeCommitment}$ は, 指定した node の commitment を計算する.

func MakeVerkleMultiProof(tree VerkleNode, keys [][]byte) (*Proof, []*Point, []byte, []*Fr) {
    return proof, cs, zs, ys;
}

func VerifyVerkleProof(proof *Proof, cs []*Point, zs []byte, ys []*Fr) bool {
    return isOk;
};

## go-ipa のインターフェース

与えられた Verkle tree の inclusion proof を生成, 検証するプロトコルを担当する. $\mathtt{zs} \in [0, k]^{d}$ は, inclusion proof を行いたい key の値を $k$ 進数表記した文字列とする.

$$
\mathsf{CreateMultiProof}: \mathbb{G}^{d} \times (\mathbb{F}_r^{k})^{d} \times [0, k]^{d} \to (\mathbb{G}^{\log_2 d} \times \mathbb{G}^{\log_2 d} \times \mathbb{F}_r \times \mathbb{G})
$$ は prover によって呼び出される. prover は Verkle tree の状態をすべて持っているとする. Verkle tree の key が指す node から root node までの path に沿った internal node たちの情報から, $\mathtt{ys}$, $\mathtt{fs}$, $\mathtt{commitments}$ を計算できる.
多項式 $f_i$ は, 深さ $i$ 番目の internal node の $z \in [0, k]$ 番目の child に値 $f_i(z) \in \mathbb{F}_r$ が格納されていることを意味する. 多項式 $f_i$ の Pedersen commitment を $C_i$ とする.
$\mathtt{zs} = (z_i)_{i \in [1, d]}$, $\mathtt{ys} = (y_i)_{i \in [1, d]}$, $\mathtt{fs} = (f_i)_{i \in [1, d]}$, $\mathtt{commitments} = (C_i)_{i \in [1, d]}$ とおく. ただし, 任意の $i \in [1, d]$ に対して, $f_i(z_i) = y_i$ を満たすとする. これらの情報をもとに prover は

multiProof = CreateMultiProof(commitments, fs, zs)

を計算する. 出力 $\mathtt{multiProof}$ は 4 つ組 $(L, R, A, D)$ で構成される.

$$\mathsf{CheckMultiProof}: (\mathbb{G}^{\log_2 d} \times \mathbb{G}^{\log_2 d} \times \mathbb{F}_r \times \mathbb{G}) \times \mathbb{G}^{d} \times \mathbb{F}_r^{d} \times [0, k]^{d} \to \{ 0, 1 \}
$$ は verifier によって呼び出される. Verkle tree の状態をすべて持っている verifier であれば, $\mathtt{zs}$ をもとに $\mathtt{commitments}$, $\mathtt{ys}$ は verifier 自身で計算できるが, そうでなければ prover が $\mathtt{multiProof}$ と一緒に渡してあげる必要がある. これらの情報をもとに verifier は

isOk = CheckMultiProof(multiProof, commitments, ys, zs) 

を計算し, $\mathtt{isOk} = 1$ であるときに限り, 与えられた `multiProof` を受理する.

## メモ