Our new paper Compactness of Hashing Modes and Efficiency beyond Merkle Tree was published at EUROCRYPT 2021.

Our first construction Augmented Binary Tree (ABR) mode is a (2ℓ+2ℓ−1−1)n-to-n-bit hash function making a total of (2ℓ−1) calls to 2n-to-n-bit compression functions for any ℓ≥2. Our construction is optimally compact with asymptotically (optimal) 2n/2−ϵ-query collision resistance in the ideal model. For a tree of height ℓ, in comparison with Merkle tree, the Augmented Binary Tree mode processes additional (2ℓ−1−1) data blocks making the same number of internal compression function calls.