Closed paco0x closed 2 years ago
Hi @zhangchiqing. Thanks for your great article and repo for explaining MPT of Ethereum.
I found a bug when trying to put on an extension node with matched == len(nibbles). The program will panic with the following case:
matched == len(nibbles)
func TestPutExtensionAllMatched(t *testing.T) { trie := NewTrie() trie.Put([]byte{1, 2, 3, 4}, []byte("hello1")) trie.Put([]byte{1, 2, 3, 5 << 4}, []byte("hello2")) trie.Put([]byte{1, 2, 3}, []byte("world")) leaf1 := NewLeafNodeFromNibbles([]Nibble{4}, []byte("hello1")) leaf2 := NewLeafNodeFromNibbles([]Nibble{0}, []byte("hello2")) branch := NewBranchNode() branch.SetBranch(Nibble(0), leaf1) branch.SetBranch(Nibble(5), leaf2) branch.SetValue([]byte("world")) ext := NewExtensionNode([]Nibble{0, 1, 0, 2, 0, 3}, branch) require.Equal(t, ext.Hash(), trie.Hash()) }
panic output:
❯ go test -v . -run TestPutExtension === RUN TestPutExtensionShorterAllMatched --- FAIL: TestPutExtensionShorterAllMatched (0.00s) panic: runtime error: slice bounds out of range [7:6] [recovered] panic: runtime error: slice bounds out of range [7:6] goroutine 21 [running]: testing.tRunner.func1.2({0x105348100, 0x140000b42a0}) /opt/homebrew/Cellar/go/1.19/libexec/src/testing/testing.go:1396 +0x1c8 testing.tRunner.func1() /opt/homebrew/Cellar/go/1.19/libexec/src/testing/testing.go:1399 +0x378 panic({0x105348100, 0x140000b42a0}) /opt/homebrew/Cellar/go/1.19/libexec/src/runtime/panic.go:884 +0x204 merkle-patrica-trie.(*Trie).Put(0x140000496f8, {0x14000049681, 0x3, 0x1050671fc?}, {0x140000a7060, 0x5, 0x5}) /Users/paco/Projects/ethereum/merkle-patricia-trie/trie.go:169 +0xce0 merkle-patrica-trie.TestPutExtensionShorterAllMatched(0x0?) /Users/paco/Projects/ethereum/merkle-patricia-trie/trie_test.go:165 +0x168 testing.tRunner(0x1400013a1a0, 0x105366af0) /opt/homebrew/Cellar/go/1.19/libexec/src/testing/testing.go:1446 +0x10c created by testing.(*T).Run /opt/homebrew/Cellar/go/1.19/libexec/src/testing/testing.go:1493 +0x300 FAIL merkle-patrica-trie 0.719s FAIL
This PR is trying to fix the above case and also add more test cases to cover put on the extension node.
Trie before put:
┌───────────────────────────┐ │ │ │ Extension Node │ │ │ │ Path: [0, 1, 0, 2, 0, 3] │ │ │ └────────────┬──────────────┘ │ │ │ │ ┌──────────────────────────┴─────────────────────────────────┐ │ Branch Node │ │ │ │ [0] ... [5] │ └────┼────────────────────────────────┼──────────────────────┘ │ │ │ │ │ │ │ │ ┌───────┴──────────┐ ┌─────────┴─────────┐ │ Leaf Node │ │ Leaf Node │ │ │ │ │ │ Path: [4] │ │ Path: [0] │ │ │ │ │ │ Value: "hello1" │ │ Value: "hello2"│ │ │ │ │ └──────────────────┘ └───────────────────┘
After put([]byte{[1, 2, 3]}, "world"):
put([]byte{[1, 2, 3]}, "world")
┌───────────────────────────┐ │ │ │ Extension Node │ │ │ │ Path: [0, 1, 0, 2, 0, 3] │ │ │ └────────────┬──────────────┘ │ │ │ │ ┌──────────────────────────┴─────────────────────────────────┐ │ Branch Node │ │ │ │ [0] ... [5] value: "world" │ └────┼────────────────────────────────┼──────────────────────┘ │ │ │ │ │ │ │ │ ┌───────┴──────────┐ ┌─────────┴─────────┐ │ Leaf Node │ │ Leaf Node │ │ │ │ │ │ Path: [4] │ │ Path: [0] │ │ │ │ │ │ Value: "hello1" │ │ Value: "hello2"│ │ │ │ │ └──────────────────┘ └───────────────────┘
Done @zhangchiqing
Hi @zhangchiqing. Thanks for your great article and repo for explaining MPT of Ethereum.
I found a bug when trying to put on an extension node with
matched == len(nibbles)
. The program will panic with the following case:panic output:
This PR is trying to fix the above case and also add more test cases to cover put on the extension node.
Trie before put:
After
put([]byte{[1, 2, 3]}, "world")
: