Trie Proofs Not Working as Expected

[notbdu]

Describe the bug

Inserting two unique keys with a mismatching final character results in non functioning proofs.

Expected Behavior

Expect the following to run successfully:

package main

import (
	"io/ioutil"
	"log"
	"os"

	"github.com/ChainSafe/chaindb"
	"github.com/ChainSafe/gossamer/lib/trie"
)

var (
	value = []byte("somevalue")
	key1  = []byte("worlda")
	key2  = []byte("worldb")
)

func main() {
	tmp, err := ioutil.TempDir("", "trietest")
	if err != nil {
		log.Fatal(err)
	}
	defer func() {
		if err := os.RemoveAll(tmp); err != nil {
			log.Fatal(err)
		}
	}()
	memdb, err := chaindb.NewBadgerDB(&chaindb.Config{
		InMemory: true,
		DataDir:  tmp,
	})
	if err != nil {
		log.Fatal(err)
	}

	t := trie.NewEmptyTrie()
	t.Put(key1, value)
	t.Put(key2, value)

	err = t.Store(memdb)
	if err != nil {
		log.Fatal(err)
	}

	hash, err := t.Hash()
	if err != nil {
		log.Fatal(err)
	}

	proof, err := trie.GenerateProof(hash.ToBytes(), [][]byte{key1, key2}, memdb)
	if err != nil {
		log.Fatal(err)
	}

	pairs := []trie.Pair{
		{Key: key1, Value: value},
		{Key: key2, Value: value},
	}
	v, err := trie.VerifyProof(proof, hash.ToBytes(), pairs)
	if err != nil {
		log.Fatal(err)
	}
	log.Println("verified proof:", v)
}

Current Behavior

Instead, we are seeing the following error on trie.VerifyProof():
expected key not found in the trie

Possible Solution

To Reproduce

Steps to reproduce the behaviour:

1. Run the provided example.
2. Confirm the results.

Log output

2022/01/26 21:09:47 expected key not found in the trie       
exit status 1                                                

Specification

• go version: 1.16.4
• gossamer version: development
• gossamer commit tag: NA
• gossamer commit hash: 0f78be36386db424669267c40b5146bf5962d651
• operating system: 5.13.0-7620-generic #20~1634827117~21.04~874b071-Ubuntu SMP
• additional links: NA

[EclesioMeloJunior]

Thanks for reporting, as soon as possible we will start the investigations!!

[notbdu]

One of the issues is an off by one in the following I think:

gossamer/lib/trie/trie.go

Lines 336 to 349 in 6fb057e

	value.SetKey(key[length+1:])
	if length == len(p.Key) {
	// if leaf's key is covered by this branch, then make the leaf's
	// value the value at this branch
	br.Value = p.Value
	br.Children[key[length]] = value
	} else {
	// otherwise, make the leaf a child of the branch and update its partial key
	p.Key = p.Key[length+1:]
	p.SetDirty(true)
	br.Children[parentKey[length]] = p
	br.Children[key[length]] = value
	}

For example, with the two keys worlda and worldb the length of the common prefix is 11 (in nibbles) where the total length is 12.

Usage of length+1 here for curr value and parent keys is off by 1 and ends up slicing key[11 + 1:] or key[12:] which is an empty slice.

[noot]

@notbdu that code is actually correct, the 12th nibble is actually still in the key, it's just the index of the leaf node in the above branch. when the trie is traversed, that nibble is still checked as part of the key.

[notbdu]

That is true, the 12th nibble should be in the key. The branch node should contain the matching prefix and the leaf nodes should contain the trailing mismatching prefixes on the split.

However, slices are 0 indexed so when you do key[12:] you get an empty slice. I extracted the following lines from the current impl for clarity.

// key == "worlda" in nibbles
// p.Key == "worldb" in nibbles

length := lenCommonPrefix(key, p.Key) // this is 11, total length is 12 (12th nibble is a mismatch)
 
br := node.NewBranch(key[:length], newBranchValue, newBranchDirty, t.generation) // this is correct, branch key length is 11

value.SetKey(key[length+1:]) // this is incorrect, we overindex and get an empty slice length 0

p.Key = p.Key[length+1:] // this is incorrect, we overindex and get an empty slice length 0

The leaf nodes should contain the final nibble as the key. We're currently losing it completely.

[noot]

@notbdu a branch node can have up to 16 children, and the nibble that comes directly after the matching prefix that's in the branch is the index of the child within the branch. in your example, the key of the leaf is supposed to be empty - the leaf is stored at index key[11] of the parent branch. here the node is placed at the correct index (key[11]) https://github.com/ChainSafe/gossamer/blob/development/lib/trie/trie.go#L342 which allows for it to be found later.

when the trie is traversed, this is how it knows which child sub-trie to move to: https://github.com/ChainSafe/gossamer/blob/development/lib/trie/trie.go#L515

maybe this article (it has some diagrams) will help explain it better :)
https://medium.com/chainsafe-systems/gossamer-update-1-merkle-patricia-trie-6320588efedd

[notbdu]

Ah I see, so the last nibble is used in the child bitmap of the branch node and it is expected for the leaf nodes to have a 0 value? Thanks for the clarification!

Hmm, will continue to debug what the issue is on my end as well then 👍 .

[notbdu]

Same observation on my end w.r.t. to loadFromProof().

2022/01/28 12:43:07 recording node -> branch key=0x0707060f0702060c060406 childrenBitmap=110 value=0x dirty=false
2022/01/28 12:43:07 recording node -> leaf key=0x value=0x736f6d6576616c7565 dirty=false
2022/01/28 12:43:07 recording node -> branch key=0x0707060f0702060c060406 childrenBitmap=110 value=0x dirty=false
2022/01/28 12:43:07 recording node -> leaf key=0x value=0x736f6d6576616c7565 dirty=false
2022/01/28 12:43:07 proof -> [[139 7 118 247 38 198 70 6 0 44 64 36 115 111 109 101 118 97 108 117 101 44 64 36 115 111 109 101 118 97 108 117 101] [64 36 115 111 109 101 118 97 108 117 101]]
2022/01/28 12:43:07 decoded node -> branch key=0x0707060f0702060c060406 childrenBitmap=110 value=0x dirty=true
2022/01/28 12:43:07 decoded node -> leaf key=0x value=0x736f6d6576616c7565 dirty=true

Only one of the leaves is loaded.

Update: Woops, miswrote earlier - I'm only seeing a single leaf node decoded from the raw proof above in the logs.

// loadFromProof create a partial trie based on the proof slice, as it only contains nodes that are in the proof afaik.
func (t *Trie) loadFromProof(rawProof [][]byte, rootHash []byte) error {
        if len(rawProof) == 0 {
                return ErrEmptyProof
        }

        proofHashToNode := make(map[string]Node, len(rawProof))

        for i, rawNode := range rawProof {
                decodedNode, err := node.Decode(bytes.NewReader(rawNode))
                if err != nil {
                        return fmt.Errorf("%w: at index %d: 0x%x",
                                ErrDecodeNode, i, rawNode)
                }
                log.Println("decoded node ->", decodedNode)

[notbdu]

Ahhh so I think the issue now is that we're assuming that all child nodes are unique. But the edge case here is that we have two children indexed at different points in the parent branch with the same hash.

If we remove the deletion here, the loading of the proof and verification works correctly.
https://github.com/ChainSafe/gossamer/blob/development/lib/trie/database.go#L140

Will removing this uniqueness assumption cause any issues? I can't think of any off the top of my head right now but will defer to you guys.

[EclesioMeloJunior]

@notbdu the problem is: both leaf nodes have the same hash, so, the function loadProof load the first one and remove its hash from the map, and then the next branch child which points to a leaf with an equal hash cannot load its contents because that specific hash, both leaf nodes have, was deleted from the map.

This problem can occur with branches in different paths with the same hash. Lets's say we insert these keys, one at a time into our trie

keys := ["b", "d"]
keys := ["bxyz", "dxyz"]
keys := ["bxyzi", "dxyzi"]

now we have a trie with two different paths, however, the same hash in the inner branch and leaf nodes.

[EclesioMeloJunior]

@notbdu thanks for reporting the issue, the fix fbd13d2