Problem:
Merkle proofs are used ubiquitously throughout the modular stack. Their size can be quite large, threatening to make light clients not so light.
Where to find them:
Merkle proofs can be found in many places, all of which could benefit from witness compression.
- Celestia light nodes authenticating their samples
- Rollup light nodes making trust-minimized state queries
- SORU light nodes receiving fraud proofs
- Blob Inclusion Proof
- PFB Inlcusion Proof
- Share Inclusion Proofs for Single Round Fraud Proofs
- Aggregation of multiple Blob Inclusion proofs for partial nodes
- PFB Inclusion Fraud Proofs.
Approaches:
- All 3 of the use-cases above utilize sha256 merkle proofs.
- DA layer samples could be authenticated with much smaller proofs if the merkle tree was replaced with KZG commitments.
- proof-based witness compression schemes could benefit from changing the hash from sha256 to a proof-friendly hash function, e.g poseidon.
- State proofs (and fraud proof witnesses) could be squashed significantly by switching to Verkle trees.
- Recent breakthroughs in proof systems have made sha256 compression proofs much more feasible.
- FRI-based proof systems are blazing fast, but often come with larger proof sizes. It’s worth it when and if the size of the merkle proofs exceeds the FRI proof size.
- KZG-based proof systems have the smallest proof size and thus the best compression gains. Although they are slower, you can compensate by aggregating instances in parallel (similar to folding schemes) and deferring the proving step to the aggregate instance.
- See nova-sha256 which proves a sha256 in seconds, even on a laptop, even before optimizations.
- ZKVMs could be used, but there’s a concern that they have large proof sizes and slow proving times compared with more-optimized approaches.
Promising Work:
-
starky enables STARKs with the same backend as Plonky2, but with much cheaper proofs for incrementally-verifiable computations, such as the sha256 hash function.
- Proving time is a function of the number of rows (iiuc)
- Proof size and verification time is a function of the number of columns (iiuc)
- Size of merkle proof (and number of merkle proofs) should only affect the row count (iiuc)
- Moonshot idea: can we adapt the stark system to use KZGs, and thus achieve compression gains while enabling aggregation of instances in parallel?
- Nova SHA256 with KZGs shows promise for balancing compression factor and proving time, thanks to opportunities for prover-side parallelism.
- Axiom fork of HALO 2