pallet-mmr: batch proofs are sometimes broken

[acatangiu]

Is there an existing issue?

• I have searched the existing issues

Experiencing problems? Have you tried our Stack Exchange first?

• This is not a support question.

Description of bug

#10635 added support for generating and/or verifying proofs for multiple leaves at a time.

Single leaf proof generation/verification seems to always work, but multi-leaf (batch) proof generation/verification sometimes fails.

Steps to reproduce

Apply following patch to substrate:

diff --git a/frame/merkle-mountain-range/src/tests.rs b/frame/merkle-mountain-range/src/tests.rs
index d025910a9e..583d97a308 100644
--- a/frame/merkle-mountain-range/src/tests.rs
+++ b/frame/merkle-mountain-range/src/tests.rs
@@ -341,7 +341,8 @@ fn should_verify_batch_proof() {
        // Start off with chain initialisation and storing indexing data off-chain
        // (MMR Leafs)
        let mut ext = new_test_ext();
-       ext.execute_with(|| init_chain(7));     // <---- this works
+       // ext.execute_with(|| init_chain(12)); // <---- this works
+       ext.execute_with(|| init_chain(13));    // <---- this fails
        ext.persist_offchain_overlay();
 
        // Try to generate proof now. This requires the offchain extensions to be present
@@ -349,7 +350,7 @@ fn should_verify_batch_proof() {
        register_offchain_ext(&mut ext);
        let (leaves, proof) = ext.execute_with(|| {
                // when
-               crate::Pallet::<Test>::generate_batch_proof(vec![0, 4, 5]).unwrap()
+               crate::Pallet::<Test>::generate_batch_proof(vec![7, 11]).unwrap()
        });
 
        ext.execute_with(|| {

then run the test and it will incorrectly fail:

<workdir>/substrate$ cargo test -p pallet-mmr should_verify_batch_proof
    Finished test [unoptimized + debuginfo] target(s) in 0.35s
     Running unittests src/lib.rs (target/debug/deps/pallet_mmr-0ea839eef5152467)

running 2 tests
test tests::should_verify_batch_proof_statelessly ... ok
test tests::should_verify_batch_proof ... FAILED

failures:

---- tests::should_verify_batch_proof stdout ----
thread 'tests::should_verify_batch_proof' panicked at 'assertion failed: `(left == right)`
  left: `Err(Error::Verify)`,
 right: `Ok(())`', frame/merkle-mountain-range/src/tests.rs:358:9
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

As an interesting observation, generating+verifying [7, 11] on a 12-leaves MMR works, while for a 13-leaves MMR it fails.

[acatangiu]

ping @Wizdave97 as original PR author
ping @Lederstrumpf for ideas, looks more like a MMR library bug

[Wizdave97]

ping @Wizdave97 as original PR author ping @Lederstrumpf for ideas, looks more like a MMR library bug
@acatangiu
Seems this is the line causing the failure in that case is this line here https://github.com/paritytech/substrate/blob/master/frame/merkle-mountain-range/src/lib.rs#L293
proof.items.len() as u32 > mmr::utils::NodesUtils::new(proof.leaf_count).depth()

The depth is less than the proof items length by a difference of 1, so it fails at that point, If that check is commented out the test passes, seems the depth calculation might have a bug in that edge case.
Or is that check necessary? It's not there in the stateless verification

[Lederstrumpf]

It's more than an off-by-one error - discrepancy grows with decreasing overlap of copaths of leaves to be proven.

Within a merkle tree with n leaves, a proof for a single leaf to its peak requires $\log_2(n)$ proof items (where leaves are height 0).
For proving two leaves, as long their closest mutual ancestor is of height 3 or less, you need at most $\log_2(n) +1$ proof items. Else, the proof is larger. This holds the same for an mmr, just that the ancestor can be a range node, i.e. with differing distances to each of the leaves:

As an interesting observation, generating+verifying [7, 11] on a 12-leaves MMR works, while for a 13-leaves MMR it fails.

mmr::utils::NodesUtils::new(proof.leaf_count).depth() = $\lceil \log_2(n) \rceil + 1$, i.e. 5 for both n = 12 & n = 13.
For n=12, you do also need 5 proof items, but going to 13 leaves adds another peak to bag, hence you need one extra proof item:
issue proof length.pdf

Or is that check necessary? It's not there in the stateless verification

It's not necessary - I believe the only purpose is to fail early when the proof is clearly invalid, except in this case the bound is incorrect.

Aside from removing it entirely, one possible replacement for the check is (proof.items.len() + leaves.len()) as u64 > proof.leaf_count: in the worst case (wrt. proof item count) for a merkle tree, you're trying to prove half the leaves without any sibling overlaps, so all of your proof items are other leaves, and no nodes at all. This holds the same for an mmr.