What makes an ideal state tree?

Current Merkle-Patricia tree

Property	Value
Single branch length	`128 * log(N)`
Cost of generating branch	`O(log(N))` database reads
K-branch length	`128 * k * log(N/k)` (approx)
Cost of editing 1 branch	`log(N) / 4` size-512 hashes + `O(log(N))` database writes

Problem: branches are too large (eg. 3840 bytes for size-1B state tree)

Property	Value (hexary tries)	Value (binary tries)
Single branch length	`128 * log(N)`	`32 * log(N)`
Cost of generating branch	`O(log(N))` database reads	`O(log(N))` database reads
K-branch length	`128 * k * log(N/k)` (approx)	`32 * k * log(N/k)` (approx)
Cost of editing 1 branch	`log(N) / 4` size-512 hashes + `O(log(N))` database writes	`log(N)` size-64 hashes + `O(log(N))` database writes

Problem: branches are still too large!

\(Q_i = [\frac{P(x) - P(x_i)}{X - x_i}]\)

Algebraic alternative to hash-based structures for committing to large amounts of data

Property	Value
Single branch length	`48`
Cost of generating branch	`O(N)` arithmetic ops + size-`N` EC linear combination
K-branch length	`48`
Cost of editing 1 branch	1 database write

Property	Value
Single branch length	`48`
Cost of generating branch	1 database read (as they're precomputed)
K-branch length	`48`
Cost of editing 1 branch	\(O(N * log(N))\) EC ops + \(O(N)\) database writes

Old state polynomial: polynomial reconstructed and witnesses saved every \(\sqrt(N)\) steps
Recent deltas: witnesses generated in real time

Property	Value
Single branch length	`48`
Cost of generating branch	\(O(\sqrt{N})\) arithmetic ops + size \(\sqrt{N}\) EC linear combination
K-branch length	`48`
Cost of editing 1 branch	\(\sqrt{N} * \log(N)\) EC ops + \(O(\sqrt{N})\) database writes (amortized)

Better, but unfortunately still not good enough.

Tree of polynomial commitments, each commitment having a large size (eg. 256 elements)
Proofs within each commitment are \(O(1)\) size

Property	Value
Single branch length	`12 * log(N)` (12 = 96 / 8)
Cost of generating branch	`O(log(N))` database reads + `log(N) / 8` size-256 EC linear combinations
K-branch length	`12 * k * log(N/k)` (approx)
Cost of editing 1 branch	`O(log(N))` database writes + `log(N) / 8` EC multiplications

Note also: because we now only need 1 proof, we can switch from Kate to bulletproofs

Property	Value (hexary tries)	Value (verkle tries)
Single branch length	`128 * log(N)`	`4 * log(N) + 200`
Cost of generating branch	`O(log(N))` database reads	`O(log(N))` database reads + `128 * log(N)` 256-bit arithmetic ops
K-branch length	`128 * k * log(N/k)` (approx)	`4 * k * log(N/k) + 200 + 64 * log(k)` (approx)
Cost of editing 1 branch	`O(log(N))` database writes + `log(N) / 4` size-512 hashes	`O(log(N))` database writes + `log(N) / 8` EC multiplications

Property	Value
Single branch length	`500` (approx)
Cost of generating branch	`O(log(N))` database reads + `400 * log(N)` prover constraints (approx)
K-branch length	`500` (approx)
Cost of editing 1 branch	`O(log(N))` database writes + hashes

Problem: need time to verify arithmetically-optimized hashes