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 trustminimized 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 usecases above utilize sha256 merkle proofs.
 DA layer samples could be authenticated with much smaller proofs if the merkle tree was replaced with KZG commitments.
 proofbased witness compression schemes could benefit from changing the hash from sha256 to a prooffriendly 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.
 FRIbased 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.
 KZGbased 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 novasha256 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 moreoptimized approaches.
Promising Work:

starky enables STARKs with the same backend as Plonky2, but with much cheaper proofs for incrementallyverifiable 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 proverside parallelism.
 Axiom fork of HALO 2