Node iterator starts before passed start path

[roysc]

System information

Geth version: v1.12.0

Expected behaviour

The documented behavior of a NodeIterator constructed with a start path:

// NodeIterator returns an iterator that returns nodes of the trie. Iteration starts at
// the key after the given start key.
func (t *Trie) NodeIterator(start []byte) NodeIterator {

Actual behaviour

When the trie contains a value node whose key is a prefix of the passed start path, this value node's key (with terminator) compares >= to the seeked path, so seek stops at it, although the actual path is lexicographically less than the start path.

Steps to reproduce the behaviour

Run the following:

package main

import (
	"fmt"
	"github.com/ethereum/go-ethereum/core/rawdb"
	"github.com/ethereum/go-ethereum/trie"
)

func main() {
	db := trie.NewDatabase(rawdb.NewMemoryDatabase())
	tree := trie.NewEmpty(db)

	tree.MustUpdate([]byte("foo"), []byte("bar"))
	tree.MustUpdate([]byte("food"), []byte("baz"))
	tree.MustUpdate([]byte("quux"), []byte("jar"))

	it := tree.NodeIterator([]byte("food"))
	for it.Next(true) {
		if it.Leaf() {
			key := string(it.LeafKey())
			if key == "foo" {
				panic(fmt.Sprintf("reached key %s", key))
			}
		}
	}
}

Note that this also panics if food is not added to the trie.

Proposed fix

I expect this issue rarely manifests because in practice, geth trie values are only inserted at 32-byte leaf nodes, so no leaf key will prefix a seeked start path. However it is not a consistent behavior, so it should be fixed or documented.

I propose a fix here: #27838

[roysc]

I see now that this is baked deeply into the design of the iterator. By occupying the last slot in a full node's children, the value node's path terminator also works as the index of its slot. This also means findChild and nextChild reach it last.
This effectively results in a pre-order traversal of nodes, but a post-order traversal of corresponding value nodes.

[rjl493456442]

Fixed by #27838