# Verkle tree 実装詳細

## key-value 型 DB に対する Verkle tree

- [Verkle tree integration - HackMD](https://notes.ethereum.org/@vbuterin/verkle_tree_eip)
- [gballet/go-verkle](https://github.com/gballet/go-verkle)

key, value が 32 bytes ずつのテーブルの中身について inclusion proof したい. これができると stateless client の実装に役立つ.

Verkle tree の作成手順を図, 及び python コードで示した.

vector commitment では基本的に楕円曲線を用いるので, key, value が 32 bytes ずつのテーブル $d = \{(k_{\lambda}, v_{\lambda})\}_{\lambda \in \Lambda}$ に関する Verkle tree を作成したい場合に, 最下層を若干工夫する必要がある. この部分を extension (Verkle) tree として構成し, $d^{\prime} = \{(\mathrm{stem}, D^{(\mathrm{stem})})\}_{\mathrm{stem} \in \mathsf{Stems}}$ というテーブルに帰着させる. ただし $\mathsf{Stems}$ とは, 任意の $k_{\lambda} \ (\lambda \in \Lambda)$ を $256^{31}$ で割った余りを含み, かつそのようなもののみを含む集合とする.

$$\mathsf{Stems} := \{ p \in [0, 256^{31}) \mid k_{\lambda} = p + s \cdot 256^{31} \text{ for some } s \in [0, 256), \lambda \in \Lambda \}$$

extension Verkle tree と $d^{\prime}$ から構成した Verkle suffix tree とを合わせて, $d$ の Verkle tree が構成される. 深さの最大値は root node を含めなければ 33 (= 2 + 31) であるが, テーブルの key $k_{\lambda}$ たちが十分に散らばっているほど小さくなる. 理想的な例としては, $256^2$ 個のデータがあって, それらの key の suffix 2 bytes が全て異なれば, 深さ 4 の Verkle tree になる.

<!--
下記コード中の compute_vector_commitment 関数は単なる hash 関数として実装している. Merkle proof よりも短い proof を作成したいという目的のためには, より良い commitment scheme を選ぶ必要がある.

import hashlib
from typing import Dict, List

bytes32 = bytes
bytes31 = bytes
byte = bytes

VERKLE_NODE_WIDTH = 256
EXTENSION_MARKER = 1

def compute_vector_commitment(children: List[int]) -> int:
    # pseudo code
    digest = hashlib.sha3_256(b"".join([value.to_bytes(32, 'little')
                              for value in children])).hexdigest()
    return int(digest, 16)

def compute_extension_tree_root(stem: bytes31, values: Dict[byte, bytes32]) -> int:
    sub_leaves = [0] * 512
    for suffix, value in values.items():
        suffix_int = int.from_bytes(suffix, 'little')
        sub_leaves[2 * suffix_int] = \
            int(2**128) + int.from_bytes(value[:16], 'little')
        sub_leaves[2 * suffix_int + 1] = \
            int.from_bytes(value[16:], 'little')
    C0 = compute_vector_commitment(sub_leaves[:256])
    C1 = compute_vector_commitment(sub_leaves[256:])
    main_leaves = [
        int(EXTENSION_MARKER),
        int.from_bytes(stem, 'little'),
        C0,
        C1
    ] + [0] * 252
    return compute_vector_commitment(main_leaves)

def compute_main_tree_root(data: Dict[bytes32, int], prefix: bytes) -> int:
    if len(data) == 0:
        return 0
    elif len(data) == 1:
        return list(data.values())[0]
    else:
        sub_commitments = [
            compute_main_tree_root(
                {
                    key: value for key, value in
                    data.items() if key[:len(prefix) + 1] == prefix + bytes([i])
                },
                prefix + bytes([i])
            ) for i in range(VERKLE_NODE_WIDTH)
        ]
        return compute_vector_commitment(sub_commitments)

def compute_verkle_commitment(data: Dict[bytes32, bytes32]) -> int:
    stems = set(key[:-1] for key in data.keys())
    data_as_stems = dict()
    for stem in stems:
        commitment_data = dict()
        for i in range(VERKLE_NODE_WIDTH):
            key = stem + bytes([i])
            if key in data:
                commitment_data[bytes(i)] = data[key]
        data_as_stems[stem] = compute_extension_tree_root(
            stem, commitment_data)
    return compute_main_tree_root(data_as_stems, bytes([]))

if __name__ == '__main__':
    data = {0: 2, 1: 15, 2: 209, 256: 83}
    table = {}
    for key, value in data.items():
        table[key.to_bytes(32, 'little')] = value.to_bytes(32, 'little')
    root = hex(compute_verkle_commitment(table))
    assert root == '0x70dbdb60678021614a6d5455c5c6e4dfd69fdc8d2a53790947c60f5dea3d7dcd'

<!-- ## Verkle Proof の実装

proof の構築方法は下記などを参考にしたが, 実装の細部まで理解できたわけではない.

[research/verkle_trie.py](https://github.com/ethereum/research/blob/master/verkle_trie_eip/verkle_trie.py)

この実装では, vector commitment として pedersen commitment なるものを用いている.

そこでは bandersnatch という楕円曲線が用いられている.

[bandersnatch/bandersnatch](https://github.com/zhenfeizhang/bandersnatch/tree/65823a69d6c4c7612d2f2d3d21ce87f2b319fcf0/bandersnatch)

かなり複雑な実装に見えるが, セキュリティ要件の都合で必要になるのだろうか? -->

## コード

### CreateIPAProof


### CheckMultiProof


### Insert


### ComputeCommitment


## Non-inclusion proof

non-inclusion proof も行える Verkle SMT にしたいならば, $E^{(\mathrm{suffix})}$ が empty node のときに値 0 を結びつけるのではなく, $(0, \mathrm{stem}, 0, \ldots, 0)$ から構成した node $D^{(\mathrm{stem})}$ の commitment を結びつけるなどすれば良さそうである. さらに, extension tree の各 leaf にも non-inclusion flag を含めておく必要がある.