7 ms·

Verkle Trees

263 points by felixbraun 5y ago

dvaun 5y ago
Another paper on this structure was from a highschool student in the MIT PRIMES program[0] back in 2018. I couldn't find much else besides other Ethereum-related sites [0]: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf https://math.mit.edu/research/highschool/primes/materials/20...
losvedir 5y ago
I always enjoy reading Vitalik's posts. I remember many years ago back when Bitcoin was fun. I traded it back and forth with friends for pizza and such. I even used it once at a hip restaurant in town. Some Bitcoin forum (the name of which escapes me atm) had a bitcoin drip, which would give you a free Bitcoin every once in a while. But then Bitcoin's value exploded, it's not very useful anymore since transaction fees are so high and its value is so volatile, no one can mine it on their home machines, and its ecological disaster. But it used to be just a cool, kind of hacker niche, and was fun to think about the underlying technology and possibilities. Vitalik's explorations with Ethereum have kind of a similar vibe to me. It's neat to think about the tech and how it works, and to try to come up with attacks and such. And if it ever moves to Proof of Stake, I won't have that guilty conscience playing with it. Of course, all of this on top of a $100 billion valuation is kind of frightening and weird. I hate to say it, but I'm not sure I'd mind a crazy crypto crash, just to explore this technology some more without the crazy monetary incentives.
- saurik 5y ago
  (There exist systems that are already proof of stake, such as Avalanche.)
  - randomhodler84 5y ago
    Love your work saurik but PoS is a PoS. Ideologically we should be opposed — No oligopolys. No income without capital expenditure. No entrenching inequality into consensus. BTC never was unfun. It’s more fun today than ever. OP is sad they sold.
    - X6S1x6Okd1st 5y ago
      I've had btc since 2012 not super early, but early enough that I briefly used mygox. Bitcoin has become toxic, the block size wars were interesting, but they yielded two communities that were less than what they were before the split. Bitcoin has stagnated technologically and Bitcoin cash believes that it will win based off of the principals that governed the split. Bitcoin will be on top for a good while longer, but I'm not interested in it anymore.
      - randomhodler84 5y ago
        The Bitcoin community got more focused on the fundamentals, long term thinking and actual value preservation. That is not true that it has stagnated technologically — MAST, taproot, Schnorr sigs. Lightning. Getting adopted as an official currency… Bitcoin is as cutting edge as ever. People got used to the slapdash lose a few hundred million in an eth smart contract world, and expect lambos in weeks. Which we see in the short term with frothy exuberance. The perceived toxicity is skepticism, because we have seen it all before. Same scams different year. Bcash is not to be taken seriously. There is and always will be Bitcoin.
        hanniabu 5y ago
        > Bitcoin is as cutting edge as ever. Everything you listed is years old, not cutting edge
        randomhodler84 5y ago
        Please name a “cutting edge” feature that exists in a coin today.
        hanniabu 5y ago
        Ethereum's zk rollups and upcoming sharding
        5y ago
- PretzelPirate 5y ago
  You’ll never be able to avoid the monetary incentives anymore outside of using a testnet. Ethereum testnets have real Dapps on them that you can use. You can also use layer 2 networks on top of Ethereum to avoid high transaction costs.
- X6S1x6Okd1st 5y ago
  Another cool piece of crypto tech is mina, there's really interesting bits of math & engineering being done as well as all the shilling, scams and speculation
  - randomhodler84 5y ago
    Mina, Grin, Beam are all interesting constructions. I’ve played with them but I felt quite nervous. They throw away too much information to be secure. Maybe totally unsuitable for value storage? The lack of audibility means your savings might be invalidated one day. All it takes is a single mistake and the Mina chain become useless, taking out all the embedded txs.
- rogueSkib 5y ago
  Re: "ecological disaster" I believe this is misinformation, because it assumes that the energy usage is not being well spent - that Bitcoin is a waste - but that assumption could not be further from the truth. Bitcoin's value lies in its absolute scarcity and immutable monetary policy - it preserves your time spent working in a money that cannot be debased by anyone, ever. There will only ever be 21 million bitcoin. If your savings is constantly at risk of being debased, not only do you lose purchasing power over time, but you're also incentivized to spend it and invest it as quickly as possible, rather than waiting thoughtfully for the best purchase or investment. You're being forced to have an extra job, as an investor, to even remotely come close to making a good investment. This is assuming that's even an option and that you have access to financial institutions in your country. Technology is advancing exponentially - it should bring abundance and higher quality of life to everyone in the world. People will get more for less money, i.e. it is exponentially deflationary. With an inflationary monetary policy, where markets and assets prices are supported by the printing of money and will immediately crash if the printing stops, many nations will be forced to print exponentially to fight the deflation caused by technology. In other words, technology should be saving everyone time and energy as it raises productivity, but inflation forces everyone to work harder to keep up. How can a finite planet support an economic system that demands infinite growth? A money with absolute scarcity solves this by allowing for deflation in prices as technology drives abundance. Fiat and inflationary monetary policy is the root problem driving climate change, and likely many other complex negative externalities. In addition, I would point out that energy usage is not intrinsically bad. Higher per capita energy usage leads to higher quality of life. The climate issue energy poses is within how the energy is produced, and the majority of that problem lies in the emissions from coal power. The good news on the energy production side is that a monetary network using Proof-of-Work incentivizes competition between miners globally. As cheaper (or even free, stranded) energy is made available to miners anywhere in the world, miners anywhere else who pay more for energy are pushed out of profitability and have to shut down shop. The difficulty adjustment in Bitcoin mining means that as more miners compete, those paying the most for energy are forced out of the market. This creates a clear incentive for miners to find the cheapest possible energy, which is predominately green and renewable and drives innovation in the space. Cheaper energy is great for humanity. Check out the recent work by ARK / Square exploring this. Overall, these developments have made me hopeful and optimistic about the future again :)
- rglullis 5y ago
  You do know that all these experiments happen on testnets, right? If playing with "real money" is what bothers you, just play around on Görli/Ropsten/Rinkeby.
deleted 5y ago
[deleted]
Kuszmaul 5y ago
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.
  - 5y ago
dandanua 5y ago
It's good that he noted that this scheme is insecure against quantum computers. Anyway, homomorphic cryptography is a fascinating field with many cool applications. I'm sure the ideas will remain useful even in the quantum era.
- Ar-Curunir 5y ago
  It’s not necessarily; you can use a polynomial commitment based on postquantum assumptions, like lattices
- mratsim 5y ago
  That's because it's polynomial commitment based on pairing-based cryptography (elliptic curves) but there are schemes based on hash functions (FRI) that are quantum secure. The main advantage of pairings is that you can have constant-size commitments. 28:47 - https://www.youtube.com/watch?v=bz16BURH_u8 https://www.youtube.com/watch?v=bz16BURH_u8
  - Ar-Curunir 5y ago
    If you’re using FRI then you have Merkle trees again :P There’s no space or computation savings when using FRI for the PC scheme here
norswap 5y ago
In case people are interested, here are some of my recent notes on Verkle trees: https://www.notion.so/norswap/Stage-0-Discovery-dcbb7318ba664687ba83adca727ff283#1323d81058d64e10944e47e48d1599b9 https://www.notion.so/norswap/Stage-0-Discovery-dcbb7318ba66...

263 points by felixbraun 5y ago

Another paper on this structure was from a highschool student in the MIT PRIMES program[0] back in 2018. I couldn't find much else besides other Ethereum-related sites [0]: https://math.mit.edu/research/highschool/primes/materials/2018/Kuszmaul.pdf https://math.mit.edu/research/highschool/primes/materials/20...

losvedir 5y ago

I always enjoy reading Vitalik's posts. I remember many years ago back when Bitcoin was fun. I traded it back and forth with friends for pizza and such. I even used it once at a hip restaurant in town. Some Bitcoin forum (the name of which escapes me atm) had a bitcoin drip, which would give you a free Bitcoin every once in a while. But then Bitcoin's value exploded, it's not very useful anymore since transaction fees are so high and its value is so volatile, no one can mine it on their home machines, and its ecological disaster. But it used to be just a cool, kind of hacker niche, and was fun to think about the underlying technology and possibilities. Vitalik's explorations with Ethereum have kind of a similar vibe to me. It's neat to think about the tech and how it works, and to try to come up with attacks and such. And if it ever moves to Proof of Stake, I won't have that guilty conscience playing with it. Of course, all of this on top of a $100 billion valuation is kind of frightening and weird. I hate to say it, but I'm not sure I'd mind a crazy crypto crash, just to explore this technology some more without the crazy monetary incentives.

saurik 5y ago
(There exist systems that are already proof of stake, such as Avalanche.)
- randomhodler84 5y ago
  Love your work saurik but PoS is a PoS. Ideologically we should be opposed — No oligopolys. No income without capital expenditure. No entrenching inequality into consensus. BTC never was unfun. It’s more fun today than ever. OP is sad they sold.
  - X6S1x6Okd1st 5y ago
    I've had btc since 2012 not super early, but early enough that I briefly used mygox. Bitcoin has become toxic, the block size wars were interesting, but they yielded two communities that were less than what they were before the split. Bitcoin has stagnated technologically and Bitcoin cash believes that it will win based off of the principals that governed the split. Bitcoin will be on top for a good while longer, but I'm not interested in it anymore.
    - randomhodler84 5y ago
      The Bitcoin community got more focused on the fundamentals, long term thinking and actual value preservation. That is not true that it has stagnated technologically — MAST, taproot, Schnorr sigs. Lightning. Getting adopted as an official currency… Bitcoin is as cutting edge as ever. People got used to the slapdash lose a few hundred million in an eth smart contract world, and expect lambos in weeks. Which we see in the short term with frothy exuberance. The perceived toxicity is skepticism, because we have seen it all before. Same scams different year. Bcash is not to be taken seriously. There is and always will be Bitcoin.
      - hanniabu 5y ago
        > Bitcoin is as cutting edge as ever. Everything you listed is years old, not cutting edge
        randomhodler84 5y ago
        Please name a “cutting edge” feature that exists in a coin today.
        hanniabu 5y ago
        Ethereum's zk rollups and upcoming sharding
        5y ago
PretzelPirate 5y ago
You’ll never be able to avoid the monetary incentives anymore outside of using a testnet. Ethereum testnets have real Dapps on them that you can use. You can also use layer 2 networks on top of Ethereum to avoid high transaction costs.
X6S1x6Okd1st 5y ago
Another cool piece of crypto tech is mina, there's really interesting bits of math & engineering being done as well as all the shilling, scams and speculation
- randomhodler84 5y ago
  Mina, Grin, Beam are all interesting constructions. I’ve played with them but I felt quite nervous. They throw away too much information to be secure. Maybe totally unsuitable for value storage? The lack of audibility means your savings might be invalidated one day. All it takes is a single mistake and the Mina chain become useless, taking out all the embedded txs.
rogueSkib 5y ago
Re: "ecological disaster" I believe this is misinformation, because it assumes that the energy usage is not being well spent - that Bitcoin is a waste - but that assumption could not be further from the truth. Bitcoin's value lies in its absolute scarcity and immutable monetary policy - it preserves your time spent working in a money that cannot be debased by anyone, ever. There will only ever be 21 million bitcoin. If your savings is constantly at risk of being debased, not only do you lose purchasing power over time, but you're also incentivized to spend it and invest it as quickly as possible, rather than waiting thoughtfully for the best purchase or investment. You're being forced to have an extra job, as an investor, to even remotely come close to making a good investment. This is assuming that's even an option and that you have access to financial institutions in your country. Technology is advancing exponentially - it should bring abundance and higher quality of life to everyone in the world. People will get more for less money, i.e. it is exponentially deflationary. With an inflationary monetary policy, where markets and assets prices are supported by the printing of money and will immediately crash if the printing stops, many nations will be forced to print exponentially to fight the deflation caused by technology. In other words, technology should be saving everyone time and energy as it raises productivity, but inflation forces everyone to work harder to keep up. How can a finite planet support an economic system that demands infinite growth? A money with absolute scarcity solves this by allowing for deflation in prices as technology drives abundance. Fiat and inflationary monetary policy is the root problem driving climate change, and likely many other complex negative externalities. In addition, I would point out that energy usage is not intrinsically bad. Higher per capita energy usage leads to higher quality of life. The climate issue energy poses is within how the energy is produced, and the majority of that problem lies in the emissions from coal power. The good news on the energy production side is that a monetary network using Proof-of-Work incentivizes competition between miners globally. As cheaper (or even free, stranded) energy is made available to miners anywhere in the world, miners anywhere else who pay more for energy are pushed out of profitability and have to shut down shop. The difficulty adjustment in Bitcoin mining means that as more miners compete, those paying the most for energy are forced out of the market. This creates a clear incentive for miners to find the cheapest possible energy, which is predominately green and renewable and drives innovation in the space. Cheaper energy is great for humanity. Check out the recent work by ARK / Square exploring this. Overall, these developments have made me hopeful and optimistic about the future again :)
rglullis 5y ago
You do know that all these experiments happen on testnets, right? If playing with "real money" is what bothers you, just play around on Görli/Ropsten/Rinkeby.

deleted 5y ago

[deleted]

Kuszmaul 5y ago

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

dandanua 5y ago

It's good that he noted that this scheme is insecure against quantum computers. Anyway, homomorphic cryptography is a fascinating field with many cool applications. I'm sure the ideas will remain useful even in the quantum era.

Ar-Curunir 5y ago
It’s not necessarily; you can use a polynomial commitment based on postquantum assumptions, like lattices
mratsim 5y ago
That's because it's polynomial commitment based on pairing-based cryptography (elliptic curves) but there are schemes based on hash functions (FRI) that are quantum secure. The main advantage of pairings is that you can have constant-size commitments. 28:47 - https://www.youtube.com/watch?v=bz16BURH_u8 https://www.youtube.com/watch?v=bz16BURH_u8
- Ar-Curunir 5y ago
  If you’re using FRI then you have Merkle trees again :P There’s no space or computation savings when using FRI for the PC scheme here

norswap 5y ago

In case people are interested, here are some of my recent notes on Verkle trees: https://www.notion.so/norswap/Stage-0-Discovery-dcbb7318ba664687ba83adca727ff283#1323d81058d64e10944e47e48d1599b9 https://www.notion.so/norswap/Stage-0-Discovery-dcbb7318ba66...