Summary on A short note on PQ-Verkle

Overview

The post explores PQ-Verkle—a variant of Verkle trees potentially adapted for post-quantum (PQ) security—and its role in addressing Ethereum’s ever-growing state size. It frames the discussion by asking: What problems does Verkle solve, what are its key advantages, what do critics say, and can we “harden” it for a post-quantum world?

---

The Problem: Ethereum’s Growing State

• State Bloat and Hardware Demands:
  Ethereum’s state is continuously expanding, which increases storage and I/O requirements for nodes. This rise forces full-nodes to manage large witness sizes (proofs of state), making it costly in terms of disk access and bandwidth.

• Statelessness as a Goal:
  The ideal is to enable nodes to verify blocks without storing the entire state locally. Verkle trees aim to reduce the witness size dramatically, lowering the barrier for participation and improving network efficiency.

---

What Makes Verkle Trees Attractive?

• Efficient Storage Proofs:

  • Reduced Data Needs:
    Verkle trees use vector commitments (VCs) that compress proofs. Instead of including multiple sibling nodes (as in Merkle trees), only one commitment per tree level is needed.
  • Scaling with Arity:
    A higher arity leads to a shallower tree, resulting in fewer VC openings per proof. This efficiency becomes more pronounced as more leaves (state entries) are proven simultaneously.
  • Differential Updatability:
    The ability to update proofs by processing only the change (the “delta”) reduces the I/O overhead and simplifies updates.

• I/O Performance Benefits:
  Smaller trees and commitments mean less disk I/O, which is critical since database random reads are a major performance bottleneck in block execution.

---

The Quantum Question: Is Verkle Still Best Without PQ Concerns?

• Traditional Verkle Trees:
  In a non-PQ context, KZG-based Verkle trees are very efficient. Techniques like Inner Product Argument (IPA) allow for succinct proofs by aggregating many VC openings into one compact proof.

• Post-Quantum Challenges:
  The current Verkle approach leverages elliptic curves—which might be vulnerable to quantum attacks. Adapting Verkle trees for PQ security might require additional migrations or new cryptographic primitives that could complicate the overall design.

---

Criticisms and Concerns

• PQ-Resistance:

  • Migration Complexity:
    Transitioning to PQ-resistant trees could force Ethereum to undergo multiple state-tree migrations (e.g., from MPT to Verkle and then to a PQ alternative), a process that is inherently risky and time-consuming.
  • Dependence on Elliptic Curves:
    Many current ZKEVM implementations rely on elliptic curves for efficient arithmetization, but using them jeopardizes PQ security.

• Alternative Schemes:
  Binary trees, though simpler, tend to produce larger proofs and require more I/O, making them less attractive despite their simplicity.

• ZK-(Un)friendliness:
  Arithmetizing “foreign field arithmetic” in SNARKs is inherently challenging and often forces the use of inefficient workarounds (such as embedding elliptic curves) that further compound the issues of PQ resistance.

---

Can We Harden Verkle for a Post-Quantum World?

• Leveraging Lattice-Based Constructions:
  The post suggests that PQ-Verkle might be achievable by basing the design on lattice-based vector commitments. In such schemes, the underlying polynomial rings and associated primitives (with larger element sizes, e.g., ~64 bytes) might perform better in a PQ context.

• Recent Advances in PQ Vector Commitments:
  Several recent works are highlighted:

  • Older Lattice Schemes:
    Early proposals offered PQ security but often required a trusted setup or had poor asymptotic performance.
  • Promising Newer Schemes:
    A notable work (from 2022) shows significant improvements, offering logarithmic proof sizes for vectors of moderate size (around 1024 elements) and supporting stateless updatability—a key feature for Verkle trees.

• Proof Aggregation Techniques:
  A major research focus is on aggregating the many VC opening proofs into a single, compact proof. Options include:

  • Using lattice-based proving schemes (like LaBRADOR), which are complex but may offer sub-linear proof sizes.
  • Exploring hash-based proof systems (such as WHIR) to bypass some limitations of current VC aggregation methods.
  • Exploiting additive-homomorphic properties to compress proofs similarly to how BLS signature aggregation works in the Beacon chain.

• Differential Updatability:
  Maintaining differential updatability is crucial—it allows for efficient updates without the need to reprocess the entire tree, preserving I/O efficiency.

---

Conclusions and Future Directions

• PQ-Verkle’s Promise:
  PQ-Verkle trees could address Ethereum’s state size problem while being adapted to resist quantum attacks. Their efficiency in storage and I/O is a significant advantage.

• Open Research Questions:

  • How best to aggregate opening proofs to keep the final proof compact?
  • Can PQ vector commitment schemes be optimized to support differential updatability without significant trade-offs?
  • What is the overall performance impact when compared with current non-PQ solutions?

• Next Steps:
  The post calls for further research into evaluating and benchmarking these PQ schemes, particularly the promising approaches from recent literature. There is a need to understand the weakest points in the proposed solutions and compare them with other alternatives, as well as to integrate efficient proof aggregation techniques.

In short, while PQ-Verkle presents additional challenges, especially in terms of adapting to PQ security, it remains one of the most promising avenues for creating a scalable, efficient, and future-proof state structure for Ethereum. The community’s ongoing research and debate indicate that the right balance between performance, security, and complexity might soon be found.

---