`TestVerifySubtreeRootInclusion_recursionBug`

[rootulp]

Context

I'm trying to bump celestia-node to use celestia-app v2.0.0. It turns out the big test cases for TestProveCommitmentAllCombinations identified an issue in NMT.

https://github.com/celestiaorg/nmt/pull/260

Problem

Failing unit test to illustrate the issue. This results in a panic because computeRoot is called over and over with: start=19, end=20, k=0.

// TestVerifySubtreeRootInclusion_recursionBug is motivated by a failing test
// case in celestia-node
func TestVerifySubtreeRootInclusion_recursionBug(t *testing.T) {
    namespaceIds := bytes.Repeat([]byte{1}, 64)
    tree := exampleNMT(1, true, namespaceIds...)
    root, err := tree.Root()
    require.NoError(t, err)

    nmthasher := tree.treeHasher
    hasher := nmthasher.(*NmtHasher)
    subtreeRoot, err := tree.ComputeSubtreeRoot(0, 4)
    require.NoError(t, err)
    subtreeRoots := [][]byte{subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot, subtreeRoot}
    subtreeWidth := 8

    proof, err := tree.ProveRange(19, 64)
    require.NoError(t, err)

    require.NotPanics(t, func() {
        // This hits:
        // runtime: goroutine stack exceeds 1000000000-byte limit
        // runtime: sp=0x14020160480 stack=[0x14020160000, 0x14040160000]
        // fatal error: stack overflow
        _, err = proof.VerifySubtreeRootInclusion(hasher, subtreeRoots, subtreeWidth, root)
        require.NoError(t, err)
    })
}

Proposal

1. Fix the implementation in NMT so that it isn't possible to recurse indefinitely
2. Create a new NMT release
3. Bump to it in all downstream repos