Compact Merkle Multiproofs
This addresses a memory optimization problem for systems using Merkle trees, such as blockchain or data verification, but is incremental as it builds on existing multiproof concepts.
The paper tackles the memory inefficiency of standard sparse Merkle multiproofs by introducing compact Merkle multiproofs, which reduce storage requirements from storing an index for every non-leaf hash to only k leaf indices, significantly cutting multiproof size, especially in larger trees.
The compact Merkle multiproof is a new and significantly more memory-efficient way to generate and verify sparse Merkle multiproofs. A standard sparse Merkle multiproof requires to store an index for every non-leaf hash in the multiproof. The compact Merkle multiproof on the other hand requires only $k$ leaf indices, where $k$ is the number of elements used for creating a multiproof. This significantly reduces the size of multirpoofs, especially for larger Merke trees.