Limits on Revocable Proof Systems with Miranda Christ | a16z crypto research

TL;DR

It is impossible to have a stateless blockchain where users never have to update their proofs, and roll-up solutions cannot provide persistent account balances.

Transcript

very happy to have one of our own back in the house Miranda Christ who's one of our some research interns Last Summer and she'll be talking about an FC paper that she has with Joe Benoit that got some of like the best paper reviews that I've ever seen so I think this could wind up being a quite fundamental result looking forward to hearing the deta... Read More

Key Insights

• 😫 Stateless blockchains require users to submit proofs instead of the full set of valid coins to reduce the storage burden on validators.
• 💗 The size of the state in a blockchain can become a scalability issue when the number of transactions and unspent coins grows.
• 👤 Users in a stateless blockchain need to update their proofs when other users make transactions, leading to a constant fraction of users having to update their proofs regularly.
• 🗞️ Roll-ups, which aim to provide scalability through off-chain computations and proofs, cannot solve the proof update problem or provide persistent account balances.

Questions & Answers

Q: Why is the double spending problem important in blockchains?

The double spending problem undermines the integrity and trust of blockchain systems, as it allows users to spend the same coin multiple times. Ensuring that a user cannot double spend is crucial for maintaining the security and reliability of the blockchain.

Q: Can the size of the state in a blockchain be a limiting factor for scalability?

Yes, as the number of transactions and unspent coins increases, the size of the state in a blockchain can become a bottleneck. If the state becomes too large, it can pose challenges for validators to maintain and store the entire set of valid coins efficiently.

Q: Is there a way to minimize the storage burden on validators in a stateless blockchain?

While there are techniques to compress the storage requirements, such as using efficient data structures like accumulators or vector commitments, the impossibility result suggests that there is no way to completely eliminate the need for updating proofs in a stateless blockchain setting.

Summary & Key Takeaways

• A stateless blockchain involves users submitting transactions and validators verifying their validity.

• The double spending problem, where a user spends the same coin twice, is a key concern in blockchains.

• Stateless blockchains aim to reduce the storage burden on validators by having users submit proofs instead of the full set of valid coins.