The second preimage attack for Merkle Trees in Solidity

The second preimage attack in Merkle trees can happen when an intermediate node in a merkle tree is presented as a leaf.

The name of this attack is quite misleading because it implies hashes have a second preimage. Modern hash functions do not have multiple (computable) preimages.

A better name for this attack would be “node as leaf attack” or “shortened proof attack.”

Prerequisites

We assume the reader is familiar with Merkle trees and Merkle proofs.

Notation

We refer to h(x) to be the hash of x. h(x + y) is the hash of the concatenation of x and y. In this article, we’ll focus on keccak256 as our hash function; picking a specific function will help make some of the reasoning clearer later in the article. However, keep in mind that the ideas in this article will apply for any hash function. We refer to the leaves of a merkle tree with ℓ. The ith leaf is referred to with ℓᵢ.

An Example Attack

Suppose we wish to create a proof for leaf 2 (ℓ₂) in the tree below. The leaf will be ℓ₂, and the proof will be [h(ℓ₁), h(b), h(f)]. The values a, b, c, …, g are the concatenation of the child values. We accept the proof if h(g) equals the Merkle root.