# Verkle Tree (Trie)

###### tags: `Ethereum` `Math` `Polynomial Commitment` `Verkle Tree`

[TOC]

## Overview
> Describe data structure of Merkle Tree, Verkle Tree, Merkle Trie, Verkle Trie.

Verkle 이라는 단어는 **V**ector와 M**erkle**의 합성어?입니다.

Vector는 Verkle Tree가 proof of membership에 Vector Commitment Scheme를 사용하는 것을 의미합니다.

Merkle은 Verkle Tree의 트리 구조가 Merkle Tree와 동일함을 의미합니다.

Here we describe what the 'Verkle' things are.
'Verkle' means 'Vector (commitment)' and 'Merkle'. It means that 1) the tree(trie) uses a "vector commitment scheme" for proof of membership -- not just hashing the node and siblings and 2) the tree(trie) structure is the same as Merkle Tree(Trie).

As vector stuffs are a little bit more complex than merkle stufs, first we just get to the tree structure.





Commitment from child nodes to parent node with k proofs

KZG commitment scheme: inner node - child nodes 간의 proof size를 k가 아니라 1로 줄일 수 있음


1. Merkle Tree vs Verkle Tree
- data structure
- proof scheme
- proof size
2. Merkle Trie vs Verkle Trie (k-ary)
- data structure
- proof scheme
- proof size

### Top-down Approach

3. What is the proof of Verkle Trie(Tree)
4. How to reduce the proof size
- KGZ polynomial scheme

### Bottom-up Approach

## PCS Multiproof

## References
- https://vitalik.ca/general/2019/09/22/plonk.html
- https://vitalik.ca/general/2021/01/26/snarks.html
- https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf
- https://vitalik.ca/general/2021/06/18/verkle.html
- https://crypto.stanford.edu/pbc/notes/elliptic/movattack.html
- https://people.cs.nctu.edu.tw/~rjchen/ECC2012S/Elliptic%20Curves%20Number%20Theory%20And%20Cryptography%202n.pdf
- https://www.math.ru.nl/~bosma/Students/MScThesis_DennisMeffert.pdf
- https://en.wikipedia.org/wiki/Fundamental_theorem_of_algebra
- https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
- https://en.wikipedia.org/wiki/Fermat's_little_theorem
- https://en.wikipedia.org/wiki/Decisional_Diffie%E2%80%93Hellman_assumption
- https://en.wikipedia.org/wiki/Discrete_logarithm
- https://vitalik.ca/general/2017/01/14/exploring_ecp.html
- https://dankradfeist.de/ethereum/2020/06/16/kate-polynomial-commitments.html
- https://dankradfeist.de/ethereum/2021/06/18/verkle-trie-for-eth1.html
- https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html

Inner Product Augments
- https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
- https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
- https://hackmd.io/@tazAymRSQCGXTUKkbh1BAg/Sk27liTW9: multi-scalar multiplication (MSM)