(*SparseMerkleTree).th.parseNode should check that data retrieved is within limits else panic

[odeke-em]

If we look at this code here

smt/treehasher.go

Lines 68 to 70 in a99c0f5

	func (th *treeHasher) parseNode(data []byte) ([]byte, []byte) {
	return data[len(nodePrefix) : th.pathSize()+len(nodePrefix)], data[len(nodePrefix)+th.pathSize():]
	}

we notice that the authors assumed that we'd always have data with a length of at least 33 bytes. However, this code unfortunately doesn't recall that to create a SparseMerkleTree, we need to pass in the nodes MapStore as well as the values MapStore. If we run this code, we'll get a panic:

func TestInvalidNodesValues(t *testing.T) {
        smn, smv := NewSimpleMap(), NewSimpleMap()
        smt := NewSparseMerkleTree(smn, smv, sha256.New())
        smn.Set([]byte("key"), []byte("v"))
        smn.Set([]byte("not my root"), []byte("v"))

        smt.UpdateForRoot([]byte("key"), []byte("values"), []byte("not my root"))
}  

go test -run=InvalidNodes
--- FAIL: TestInvalidNodesValues (0.00s)
panic: runtime error: slice bounds out of range [:33] with capacity 1 [recovered]
	panic: runtime error: slice bounds out of range [:33] with capacity 1

goroutine 18 [running]:
testing.tRunner.func1.2({0x11232a0, 0xc00010e000})
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/testing/testing.go:1209 +0x24e
testing.tRunner.func1()
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/testing/testing.go:1212 +0x226
panic({0x11232a0, 0xc00010e000})
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/runtime/panic.go:814 +0x214
github.com/celestiaorg/smt.(*treeHasher).parseNode(0xc0000a41e0, {0xc0000a80dc, 0x1, 0x1})
	/Users/emmanuelodeke/go/src/github.com/celestiaorg/smt/treehasher.go:69 +0x139
github.com/celestiaorg/smt.(*SparseMerkleTree).sideNodesForRoot(0xc0000a41e0, {0xc0000ea040, 0x20, 0x20}, {0xc0000a8100, 0x100c78b, 0xb}, 0x0)
	/Users/emmanuelodeke/go/src/github.com/celestiaorg/smt/smt.go:339 +0x485
github.com/celestiaorg/smt.(*SparseMerkleTree).UpdateForRoot(0xc0000a41e0, {0xc0000a80eb, 0x3, 0x3}, {0xc0000a80f0, 0x1220d00, 0x6}, {0xc0000a8100, 0xb, 0xb})
	/Users/emmanuelodeke/go/src/github.com/celestiaorg/smt/smt.go:119 +0xc5
github.com/celestiaorg/smt.TestInvalidNodesValues(0x0)
	/Users/emmanuelodeke/go/src/github.com/celestiaorg/smt/proofs_test.go:289 +0x305
testing.tRunner(0xc000083380, 0x11386a0)
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/testing/testing.go:1259 +0x102
created by testing.(*T).Run
	/Users/emmanuelodeke/go/src/go.googlesource.com/go/src/testing/testing.go:1306 +0x35f
exit status 2
FAIL	github.com/celestiaorg/smt	0.129s

Suggestion

Given this package is going to be general purpose, we need to also be defensive about code whose limits that we know we control, we should return errors and be defensive whenever we try to access data with blind bounds

/cc @cuonglm @adlerjohn @liamsi

[odeke-em]

I can also get here by invoking

        smn, smv := NewSimpleMap(), NewSimpleMap()
        smt := NewSparseMerkleTree(smn, smv, sha256.New())
        smn.Set([]byte("key"), []byte("v"))
        smn.Set([]byte("not my root"), []byte("v"))
        smt.ProveUpdatableForRoot([]byte("key"), []byte("not my root"))

[cuonglm]

@odeke-em This is interesting.

I guess it passes fuzzing (and also my eyes), because here you do the set via the MapStore interface, not directly to the tree using smt.Update.

[adlerjohn]

I don't see any issue with additional safety checks to be able to fail gracefully if the user passed in "invalid" input. Especially something like this, where the panic might not manifest for a while.

[universe2439]

Is this resolved?

[odeke-em]

Not yet!