3 ms·

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, Verkl

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/2018/Kuszmaul.pdf https://math.mit.edu/research/highschool/primes/materials/20... [2] Slides: https://math.mit.edu/research/highschool/primes/materials/2018/conf/CS/1-2-Kuszmaul.pdf https://math.mit.edu/research/highschool/primes/materials/20... [3] Alin's Website: https://alinush.github.io/ https://alinush.github.io/ [4] My website: https://sites.google.com/view/johnkuszmaul https://sites.google.com/view/johnkuszmaul

gritzko 5y ago
> 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.
- Kuszmaul 5y ago
  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).)
jude- 5y ago
Vitalik should really give you proper attribution.
- saurik 5y ago
  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 :(.
- deleted 5y ago
  [deleted]
sydthrowaway 5y ago
How did you get so proficient at math/CS while only in high school?
vbuterin 5y ago
Thanks! I actually wasn't aware of the intellectual history. I added a link to your paper at the start of my post.

gritzko 5y ago

> 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.

Kuszmaul 5y ago
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).)

jude- 5y ago

Vitalik should really give you proper attribution.

saurik 5y ago
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 :(.
deleted 5y ago
[deleted]

sydthrowaway 5y ago

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

vbuterin 5y ago

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