Description

The Merkle verification circuit is vulnerable to a second preimage attack. The circuit is defined as follows.

pub fn compute_merkle_root(
    leaf: Field,
    merkle_index: [u1; 32],
    merkle_path: [Field; 32],
) -> Field {

    let mut merkle_root = leaf;
    for i in 0..32 {
        let left = if merkle_index[i] == 0 { merkle_root } else { merkle_path[i] };
        let right = if merkle_index[i] == 1 { merkle_root } else { merkle_path[i] };

        let next_merkle_root = std::hash::mimc::mimc_bn254([left, right]);
        if merkle_path[i] != 0 { 
            merkle_root = next_merkle_root;
        }
    }
    merkle_root
}

Impact

The circuit allows variable length paths, and there is no domain separation for node hashes and leaf hashes. Therefore, an attacker can successfully prove an intermediate note as a leaf in a Merkle tree.

We did not discover a way to exploit this in practice.

Recommendations

There are generally two ways to mitigate a second preimage attack in Merkle root computation.

1. Make the verification path a fixed length.

2. Add domain separation for hashing leaves and hashing internal nodes.

The first solution is not a possibility for Singularity as the on-chain Merkle store allows variable depth leaves. We would recommend adding domain separation as per the second solution.

A straightforward way to implement domain separation would be to add different prefix elements to leaf and node hashes.

Remediation

This issue has been acknowledged by Singularity, and a fix was implemented in commit 064c573c↗.