FlatMerkle: Compact Inclusion Proofs with Linear Hashing
A new paper by Fairgate's Sergio Lerner introduces FlatMerkle, a construction that enables logarithmic-size inclusion proofs and verification over a single linear hash stream, without requiring a traditional Merkle tree structure. The paper explores applications to Bitcoin transaction commitments, data availability, and optimistic rollups.
eprint.iacr.org
🔗
FlatMerkle: Logarithmic-Space Inclusion Proofs over a Single Linear Hash Stream
Merkle trees are the standard way to obtain logarithmic-size, logarithmic-time inclusion proofs over a large dataset, but they require a tree-shaped hash structure distinct from the ordinary, linear (Merkle–Damgård) hashing that most deployed systems — including Bitcoin's own transaction and witness hashing — actually perform. We present FlatMerkle, a construction that achieves the same asymptotic guarantees, O(log N) proof size and O(log N) verification time, over a single ordinary linear hash stream, by periodically re-injecting the hash function's own past internal states (“checkpoints”) back into the stream as ordinary message content.