Proof verification optimisation for pallet-beefy-mmr

[doubledup]

While looking into Ethereum gas optimisation for Snowbridge, we noticed one of OpenZeppelin's optimisations for proof verification. This amounts to sorting each pair of hashes before hashing them during proof creation, which removes the need to track & reproduce the order in which the hash function is applied during proof verification.

In our case, this makes it more efficient to verify proofs on Ethereum because we can perform a single comparison to determine the order when combining hashes.

This would be a breaking change to proof verification, so we'd need to communicate this to the relevant projects.

I've made this change in a fork and am working on updating the tests there. Are there any other considerations or knock-on effects I should deal with before opening a PR?

cc @acatangiu @Lederstrumpf

[acatangiu]

No knock-on effects I can think of.. feel free to move ahead with the PR.

[seunlanlege]

Unfortunately this optimization is not resistant to second-preimage attacks. Without this safegaurd it becomes possible for an attacker to shorten or lengthen the proofs (essentially describing an alternative tree) in order to fool the verifier that some non-existent items exist in the original tree.

For single proofs you are able to easily prevent this by asserting that the proof length is the same as the original tree height. This can be done by calculating the height of the tree using the number of leaves at the time the tree was created.

And while this vulnerability only affects the multiproof scheme, in order to truly optimize the gas verification costs for the beefy authority set it's necessary to use a merkle multiproof verifier.

Gas Performance

@openzeppelin/contracts

Number of hashes required for single-proof for 667 items in a 1000 leaf tree (kusama validators):

log2(1000) = 10;
667 (leaves) * 10 (tree height) + 667 (leaf hashes) = 7337

@polytope-labs/solidity-merkle-trees

Multiproofs allow for the re-use of intermediate hashes when re-calculating the root hash.

number of hashes in a multiproof of 667 leaves in a 1000-leaf tree = 672

Benchmarks

polytope-labs/solidity-merkle-trees

Recommendations

Based on this, we should revert: #12857

References

• Second Preimage Attacks
• Openzeppelin Audit Report

[vgeddes]

Just an update from the Snowfork side, we're mostly debating this issue on the Polkadot Bridges group on element: https://matrix.to/#/#bridges:web3.foundation.

[Lederstrumpf]

Given that keccak256 is (still™) collision resistant (else, Ethereum would have bigger fish to fry), a practical exploit of this attack is infeasible, lest an implementation issue such as https://eprint.iacr.org/2023/331 sneaks through. As such, an exploit seems, for the foreseeable future, theoretical in nature.

Nonetheless, @swasilyev pointed me towards a 2nd preimage attack against bitcoin light client SPV proofs, which reduces the brute force requirement from 256 to about 70 bits (modulo economic assumptions re. the attacker plausible at the time) for SPV clients without safety guards.
In this case, the bitcoin tx structure (i.e. the leaves in SPV proofs) was critical to the nature of the attack: since transactions can be 64 bytes in Bitcoin, the leaves themselves could be valid internal nodes. In our case where the MMR leaves are 232 bytes, it's only the leaf hashes that have the same length (32 bytes) as node hashes and entertain this ambiguity, so the frontier here's still collision resistance.

If there's another argument to be made that we should install safeguards against 2nd preimage attacks, here are the options to address/mitigate I've tallied up so far:

1. go ahead with polytope's 2d multiproofs, as proposed by @seunlanlege. What I like about the 2d multiproofs is that the proof verification's algorithm's logic is very transparent. Switching to 2d multiproofs is of independent consideration of 2nd preimage attacks if it benchmarks better than openzeppelin's multiproofs, but should also consider engineering & auditing effort for migrating the frame pallets to this scheme, given that they currently support batch proofs a la nervos already.

2. check the proof size |leaves| + |proof_items|. This is cheap (assuming one knows the mmr size) and can be done at different depths, depending on the desired mitigation level:

   1. upper bound log(mmr_size)
   2. upper bound worst case for |leaves|
   3. calculate exact proof size from positions of leaves (we don't supply these to proofs currently)

3. use distinct prefixes when hashing leaves & nodes, as suggested by @AlistairStewart

4. use distinct hash functions for leaves & nodes, as recommended by openzeppelin itself.
   The options we have are:

   1. ripemd-160 precompile
   2. implement blake2b around the blake2b compression precompile
   3. sha256 precompile
   4. double hash keccak256

   Of these alternatives, I'd go for 4.iii or 4.iv, and their gas cost is the same (for hashing a 32 byte input, sha256 would be 60 + 12 vs. keccak @ 2 * (30 + 6)).

5. check that leaves aren't ever 32 bytes to avoid ambiguity with nodes, also suggested by @AlistairStewart.
   MMR leaves are (currently) 232 bytes, so this is easily guaranteed.

As such, I'd keep #12857. If there's still concern that 2nd preimage attacks should be guarded against, we can deploy one of the above fixes.

[seunlanlege]

go ahead with polytope's 2d multiproofs, as proposed by @seunlanlege. What I like about the 2d multiproofs is that the proof verification's algorithm's logic is very transparent. Switching to 2d multiproofs is of independent consideration of 2nd preimage attacks if it benchmarks better than openzeppelin's multiproofs, but should also consider engineering & auditing effort for migrating the frame pallets to this scheme, given that they currently support batch proofs a la nervos already.

I want to add here that the 2d multiproof isn't a new scheme, the previous merkle tree scheme was simply a standard construction with no node sorting. The 2d multiproof is an approach to supporting multiproofs for standard merkle trees.

From the benchmarks i've posted here, the multiproof scheme is more efficient for larger sub sets than single proofs.

I'm still not fully onboard with openzeppelin's multi proofs. But would be interesting to see benchmarks against solidity-merkle-trees.

[vgeddes]

5. check that leaves aren't ever 32 bytes to avoid ambiguity with nodes, also suggested by @AlistairStewart.
MMR leaves are (currently) 232 bytes, so this is easily guaranteed.

Just a correction: Should check that leaves aren't ever 64 bytes to avoid ambiguity with nodes.

I can also confirm that @AlistairStewart's recommendations are backed by the OpenZeppelin team in this issue: OpenZeppelin/openzeppelin-contracts#3091, where they suggest the same methods for ensuring domain separation between internal nodes and leafs.

These mitigations are already in place in Polkadot/Substrate

For BEEFY validator root

Leaves are 20-byte ethereum addresses

1. substrate/frame/beefy-mmr/src/lib.rs

   Line 200 in e46d96c

   .map(T::BeefyAuthorityToMerkleLeaf::convert)

2. substrate/frame/beefy-mmr/src/lib.rs

   Line 78 in e46d96c

   .to_eth_address()

3. substrate/frame/support/src/crypto/ecdsa.rs

   Line 32 in e46d96c

   fn to_eth_address(&self) -> Result<[u8; 20], ()>;

For parachain heads root

Leaves are greater than 64 bytes. They are of the form:

(para_id: u32, head_data: Vec<u8>).encode()

And for all parachains in existence, head_data is always greater than 32 bytes. Think parent_head, block_number, state_root, etc. Of course this may change, as I think there is nothing in the protocol that prevents head_data from just containing a 32-byte parent hash, in which case such a leaf could be exploited.

I think a simple solution is to just filter out parachains/parathreads with such a property. The merkle tree construction already does this for parathreads.

https://github.com/paritytech/polkadot/blob/e9bf067c68e806cdb272e0ce8065faa543cc0b5a/runtime/rococo/src/lib.rs#L1292