# What makes an ideal state tree? --- ## Current Merkle-Patricia tree  --- ## Current Merkle-Patricia Tree: Properties <small> | 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) </small> --- ## Binary Patricia tree  --- <small> | 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! </small> --- ## Binary trees are already theoretically near-optimal as far as hash trees go. So what can we do? --- ## Idea: use polynomial commitments! $Q_i = [\frac{P(x) - P(x_i)}{X - x_i}]$ Algebraic alternative to hash-based structures for committing to large amounts of data --- ## Polynomial commitment: properties <small> | 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 | </small> ---  --- ## Polynomial commitment: precomputed witnesses <small> | 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 | </small> --- ### Problem: polynomial commitment schemes are not designed to deal with large polynomials that are constantly changing --- ### One last trick up our sleeve: "old state" polynomial and "recent deltas" polynomial [https://ethresear.ch/t/updating-and-generating-kate-witnesses-in-amortized-sqrt-n-time/7520](https://ethresear.ch/t/updating-and-generating-kate-witnesses-in-amortized-sqrt-n-time/7520) * Old state polynomial: polynomial reconstructed and witnesses saved every $\sqrt(N)$ steps * Recent deltas: witnesses generated in real time --- <small> | 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. </small> --- ## Verkle trees * Tree of polynomial commitments, each commitment having a large size (eg. 256 elements) * Proofs _within_ each commitment are $O(1)$ size --- ## Verkle tree proofs  --- <small> | 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 | </small> --- ## But we can do even better!  --- ## Merged proofs  <small> Note also: because we now only need 1 proof, we can switch from Kate to bulletproofs </small> --- <small> | 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 | </small> --- ## SNARKed Merkle proofs <small> | 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 </small>