▲ 263 points
back
47 comments
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?
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.
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.
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.
(There exist systems that are already proof of stake, such as Avalanche.)
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.
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.
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.
I totally agree Bitcoin is oriented towards fundamentals and value preservation.
I don't find that interesting and I think the dominate force in the 21st century will be change and innovation.
It's great that bitcoin locked in taproot & that LN is functioning, those are small technical accomplishments compared to what Etherum, mina, zksync and many others have accomplished in that time (in terms of technical achievements).
Obviously bitcoin continues to dominate in terms of value, it's just not something that I find interesting anymore.
I've found the community get increasingly toxic. I don't believe it's skepticism because I've held bitcoin through much greater skepticism than what is happening now. I've held it through mtgox, before the IRS made any statement about it, through the split, through china banning it countless times, through 4 major crashes, through the 2013 unintended fork.
I followed bitcoin during the blocksize wars (I immediately sold all of my bch).
It's just not a community interested in growth, it seems like it's only interested in increased adoption & the idea of bitcoin as a global reserve currency.
> It's just not a community interested in growth, it seems like it's only interested in increased adoption & the idea of bitcoin as a global reserve currency.
If they're aspiring to build a global reserve currency, then why shouldn't their first priority be increased adoption? Distribution matters more than tech if the tech is already good enough.
Also, you seem to have contradicted yourself -- increased adoption begets growth.
> Bitcoin is as cutting edge as ever.
Everything you listed is years old, not cutting edge
Please name a “cutting edge” feature that exists in a coin today.
> MAST, taproot, Schnorr sigs. Lightning
I don’t mean to shit on the work to integrate this stuff, but a lot of it is either something that other chains already had (better versions of), or that other chains don’t need (eg: lightning)
“Better”? Features like? There is this narrative that bitcoin is old and not innovating.
It’s like TCP/IP. It is, just as tcp/ip innovates in a careful way.
If you think any chain doesn’t need a layer 2 overlay, which ultimately is the only way to scale tx’s. Anything else is kicking the can down the road.
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
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.
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 :)
Small, fairly predictable amounts of inflation don't matter too much in the long term because long-term savings is typically not saved as cash, but in a productive asset. That's a feature, not a bug. Why should we reward people if they don't invest their money in something useful?
And this is why it would be better to figure out how not to reward people for buying cryptocurrency. It's not a productive investment, it's just holding.
> Higher per capita energy usage leads to higher quality of life.
If that energy is spent on, you know, improving quality of life.
With bitcoin all energy is wasted on producing virtual tokens and a rate of transactions that a Raspberry Pi could run 10 times over.
Not sure why this is being downvoted.
BTC is not an ecological disaster - just like video games aren't ecological disasters.
Both use lots of energy and GPUs. One is decentralized hard money, the other is a source of entertainment.
> BTC is not an ecological disaster - just like video games aren't ecological disasters.
False equivalence.
How so? Videogames are no less useful than Bitcoin. Like, if all videogames disappeared tomorrow, humanity would fundamentally be all right.
> Videogames are no less useful than Bitcoin. Like, if all videogames disappeared tomorrow, humanity would fundamentally be all right.
1. What you said, when we normalize logic, is: videogames are just as useless as bitcoin. If videogames disappeared, humanity would be allright. Same goes for bitcoin.
I wonder if that is exactly waht you were going for.
2. Videogames are not useless. You could start with the fundamental need of humanity for games in general. Yes, if videogames disappeared, we would find other things to replace them with. I wonder if someone would then pop up and say something inane like "BTC is not an ecological disaster - just like Gaelic football [1] is not an ecological disaster."
Secondly, videogames are increasingly found to reduce stress. They are used to treat various patients [2]. They broach the subjects such as "games as new medium" and "games as art". They create vast online communities.
Bitcoin (and blockchains in general) laboriously appends entries to an append-only log using the power-equivalent of several countries at a speed of a paraplegic snail [3]. And in ten years it hasn't found a single niche where the same operations can't be done faster and more efficiently (and are usually already done faster and more efficiently).
[1] I jest, but this is a thing of beauty. Watch the entire video https://www.youtube.com/watch?v=TEAbWrdB9XU
[2] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4688462/
[3] All-time high for bitcoin was 450k transactions per day: https://www.blockchain.com/charts/n-transactions To do this, it requires more power than most countries in the world: https://www.visualcapitalist.com/visualizing-the-power-consu...
Since we're speaking about videogames, in 2006 Eve Online had 150 million DB transactions per day. To do that, Eve Online needs something like 6 database servers: https://www.eveonline.com/news/view/tranquility-tech-3
Bitcoin would need the heat death of the universe to handle a comparable load.
> I wonder if that is exactly waht (sic) you were going for.
Yes, it was. If you agree that Bitcoin is just as useless as videogames, and agree that videogames are not useless, you must also agree that Bitcoin is not useless.
I personally have no use for videogames, but I don't deny that many people do. I do, however, have use for an extremely resilient distributed timestampping service that takes several countries' energy to disrupt (which is what Bitcoin's blockchain is -- a public timestampping service). Turns out many people do, since running it is profitable.
This is why I don't like it when people call it a waste or meaningless. In my opinion, it's not a waste, but it is "excessively energy-consumptive". Sure, a lot of value is generated, but is that value commensurate with the cost? In the limit, what's the cap on this? Will Bitcoin mining consume 5% of the entire world's electricity in a decade? Is that really the best way to create a secure cryptocurrency? In addition to the potential environmental impact, what's the opportunity cost of that usage?
If Ethereum 2.0 rolls out and runs a PoS network without any issues for a year, 2 years, 3 years, what then? (Rather than debating the probability of that happening, for the sake of argument let's just hypothetically assume the transition does succeed and things run soothly for years.)
I suspect the community and devs won't even consider itas a topic for debate, though, which makes me think the cryptocurrency wars are going to get much more heated over the next 5 years. The cryptocurrencies you choose to use will be much more of a philosophical and ideological identity statement than it already is. Bitcoin-only vs. Ethereum-only vs. never-coiners. I'm genuinely pretty concerned it might reach the level of pro-life vs. pro-choice (vs. anti-natalist, I guess).
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/20...
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.
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.
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
It’s not necessarily; you can use a polynomial commitment based on postquantum assumptions, like lattices
In case people are interested, here are some of my recent notes on Verkle trees: https://www.notion.so/norswap/Stage-0-Discovery-dcbb7318ba66...