Comment by Kuszmaul | Hacker News Reader

Comment by Kuszmaul | Hacker News Reader

Author of the 2019 paper introducing Verkle Trees here [1]. Super exciting to see this on the front page of Hacker News! As the post explains very nicely, Verkle Trees basically let you save space (typically bandwidth, which can be expensive) by replacing a secure hash with a vector commitment scheme, making the tree shorter and fatter with some branching factor $k > 2$. This saved bandwidth comes at the cost of some extra computation required to generate the Verkle tree and verify proofs of leaf nodes.

As an aside, the Verkle either stands for V(ector Commitment Mer)kle Tree or the more tongue-in-cheek V(ery Short Mer)kle Tree.

A huge thanks to Alin Tomescu, who provided me with this project when I was an MIT PRIMES student in high school. He came up with the ingenious idea of combining a vector commitment scheme with a Merkle Tree. He also has a brilliant blog post on his website explaining Merkle Trees if you'd like more background info [3].

[1] Paper: https://math.mit.edu/research/highschool/primes/materials/20...

[2] Slides: https://math.mit.edu/research/highschool/primes/materials/20...

[3] Alin's Website: https://alinush.github.io/

[4] My website: https://sites.google.com/view/johnkuszmaul

> We present Verkle Trees, which are constructed similarly to Merkle Trees, but using Vector Commitments rather than cryptographic hash functions. In a Merkle Tree, a parent node is the hash of its children. In a Verkle Tree, a parent node is the Vector Commitment of its children. A Verkle Tree with branching factor k achieves O(kn) construction time and O(logk n) membership proof-size. This means that the branching factor, k, offers a tradeoff between computational power and bandwidth. The bandwidth reduction is independent of the depth of the tree; it depends only on the branching factor. We find experimentally that with a branching factor of k = 1024, which provides a factor of 10 reduction in bandwidth, it takes 110.1 milliseconds on average per leaf to construct a Verkle Tree with 214 leaves. A branching factor of k = 32, which provides a bandwidth reduction factor of 5, yields a construction time of 8.4 milliseconds on average per leaf for a tree with 214 leaves.

Thanks for posting the abstract. It's $2^{14}$ leaves in the original LaTeX rather than 214, just in case anyone is confused. (It's also $O(\log_k n)$ = O(log n / log k).)

Thanks! I actually wasn't aware of the intellectual history. I added a link to your paper at the start of my post.

Vitalik should really give you proper attribution.

Yeah :/. I was sent the Vitalik article by someone, and (despite other people liking it) found it somewhat poorly written (as did another friend of mine in the same group chat, who was left with similar questions) and then searched around trying to find more information and came across the original paper--the abstract for which was way way better than Vitalik's article :D--that hadn't been linked anywhere in the various internal cluster of references and documentation by any of the Ethereum people, near far as I could tell :(.

How did you get so proficient at math/CS while only in high school?

Reply on news.ycombinator.com