# MPT branch 17th item

Merkle Patricia Trie [FullNode](https://github.com/ethereum/go-ethereum/blob/master/trie/node.go#L38) has an array with 17 elements:

FullNode struct {
    Children [17]Node
    flags    nodeFlag
}

It seems like the 17th element is never used. Is this true (needed for [MPT circuit](https://github.com/privacy-scaling-explorations/zkevm-circuits/pull/398))?

Why does it seem so?
The node is added to the trie using [insert function](https://github.com/ethereum/go-ethereum/blob/master/trie/trie.go#L311). This function always fills `Children` by using `key` nibble to specify the position of `Children` to be filled:

_, branch.Children[key[matchlen]], err = ...

But `key` contains nibbles (values from 0 to 15), so `Children[16]` is never set.

To be precise, `key` contains value 16 [as the last nibble](https://github.com/ethereum/go-ethereum/blob/master/trie/encoding.go#L104):

func keybytesToHex(str []byte) []byte {
	l := len(str)*2 + 1
	var nibbles = make([]byte, l)
	for i, b := range str {
		nibbles[i*2] = b / 16
		nibbles[i*2+1] = b % 16
	}
	nibbles[l-1] = 16
	return nibbles
}

But this seems to serve only as a flag to determine whether `ShortNode` is a leaf or an extension node (for example [here](https://github.com/ethereum/go-ethereum/blob/master/trie/node.go#L160)).

So it seems `Children[16]` always stays `nil` and MPT circuit is currently implemented assuming it is always `nil`.

## Tx / receipts stack trie

It seems for the transactions and receipts it is similar, except that the trie is [updated with index as key](https://github.com/ethereum/go-ethereum/blob/master/core/types/hashing.go#L100). The update methods in stacktrie.go: [Update](https://github.com/ethereum/go-ethereum/blob/master/trie/stacktrie.go#L207), [TryUpdate](https://github.com/ethereum/go-ethereum/blob/master/trie/stacktrie.go#L207).

We can see that TryUpdate calls [keybytesToHex](https://github.com/ethereum/go-ethereum/blob/bc90a882633e7a61fd5d18ec266a0c51bd71a888/trie/encoding.go#L97). That means the index is transformed into nibbles (values from 0 to 15) and there is again a flag (terminator) with value 16 at the end. The difference is that the key in stack trie can have different lengths (as opposed to having 64 nibbles in the storage trie), but this does not seem to affect how `Children` array is being filled. It seems `Children[16]` is always `nil`.

---

There is a way to build an MPT node using go-ethereum that contains a value in the 17th element
using the Trie. According to this test https://github.com/ethereum/go-ethereum/blob/b4ea2bf7dda9def5374ed3ab16a3dfd872eaa40a/trie/stacktrie_test.go#L275, the StackTrie is uncapable of doing that (it panics)

Basically this happens with this code:

    db := memorydb.New()
	nt := NewEmpty(NewDatabase(db))

    kvs := []struct {
        K string
        V string
    }{
        {"0x010203", "303030"},
        {"0x01020304", "313131"},
    }
    for _, kv := range kvs {
        nt.Update(common.FromHex(kv.K), common.FromHex(kv.V))
    }

    n := nt.NodeIterator(nil)
	for n.Next(true) {
		fmt.Printf("%v %v %v\n", n.Hash(), n.Path(), n.NodeBlob())
		if n.Leaf() {
			fmt.Printf("  %v %v\n", n.LeafKey(), n.LeafBlob())
			nodeBuf := n.LeafProof()[0]
			fmt.Printf("  %v\n", nodeBuf)
			n, _ := decodeNodeUnsafe(nil, nodeBuf)
			fmt.Printf("  n: %v\n", n)
		}
	}

And this creates the following node:

{000100020003: [
    0: {0410: 313131 } 1: <nil> 2: <nil> 3: <nil> 4: <nil> 5: <nil> 6: <nil> 7: <nil> 8: <nil> 9: <nil> a: <nil> b: <nil> c: <nil> d: <nil> e: <nil> f: <nil> [17]: 303030 
  ] }

So there must be some code path in `trie.go` that is capable of writting a value in the 17th element.
Nevertheless I believe this case never appears in:
1. State / Storage trie. Because all keys have same length
2. Tx / Receipt trie. Eventhough keys have different length, the RLP encoding forces that the keys of different lengths always have different prefixes
and to have an element in the 17th position, you need two keys, where one is shorter and a prefix of the other

Here https://github.com/ethereum/go-ethereum/blob/b4ea2bf7dda9def5374ed3ab16a3dfd872eaa40a/trie/trie.go#L333
When `n.Key` is a prefix of `key`, `matchlen` will point to the last element of `n.Key` which is 16

So in conclusion: the Trie implementation is capable of setting a value in the 17th element of a FullNode when a key is a prefix of another k
But in the Ethereum context, this case never happens because we never find a key that is the prefix of another key in any of the used Tries.