OutOfRange error on node length 13

[artheus]

Hi,

Just got a runtime error (Index out of range) on the node length 13

I tried to use this on a node list of 208 separate content elements, it got stuck at trying to calculate a list of 13 nodes. I then tried adding a list of 13 nodes to the test case (copy-paste in the original tests) and got the same error.

~/workspace/go/src/github.com/cbergoon/merkletree [master] $ go test merkle_tree_test.go merkle_tree.go
--- FAIL: TestNewTree (0.00s)
panic: runtime error: index out of range [recovered]
    panic: runtime error: index out of range

goroutine 5 [running]:
testing.tRunner.func1(0xc42009a0f0)
    /usr/local/go/src/testing/testing.go:711 +0x2d2
panic(0x1119540, 0x11e5950)
    /usr/local/go/src/runtime/panic.go:491 +0x283
command-line-arguments.buildIntermediate(0xc420058740, 0x7, 0x8, 0x0)
    ~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:104 +0x50f
command-line-arguments.buildIntermediate(0xc42009c100, 0xe, 0x10, 0x20)
    ~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:118 +0x4e6
command-line-arguments.buildWithContent(0x11e9e20, 0xd, 0xd, 0xc4200864b0, 0xc42000a0c0, 0x4, 0x4, 0x0, 0x0)
    ~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:94 +0x2ff
command-line-arguments.NewTree(0x11e9e20, 0xd, 0xd, 0x11d5d20, 0x20, 0x20)
    ~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree.go:63 +0x4c
command-line-arguments.TestNewTree(0xc42009a0f0)
    ~/workspace/go/src/github.com/cbergoon/merkletree/merkle_tree_test.go:112 +0x86
testing.tRunner(0xc42009a0f0, 0x1146248)
    /usr/local/go/src/testing/testing.go:746 +0xd0
created by testing.(*T).Run
    /usr/local/go/src/testing/testing.go:789 +0x2de
FAIL    command-line-arguments  0.010s

Would be a good idea to check for this case.

[maxrobot]

I get a similar error when running the example.

I append an extra value to the list as such:

list = append(list, TestContent{x: "Hello"})
        list = append(list, TestContent{x: "Hi"})
        list = append(list, TestContent{x: "Hey"})
        list = append(list, TestContent{x: "Hey"})
        list = append(list, TestContent{x: "Hola"})

then when I run I see:

[{Hello} {Hi} {Hey} {Hey} {Hola}]
panic: runtime error: index out of range

goroutine 1 [running]:
github.com/cbergoon/merkletree.buildIntermediate(0xc42000a0c0, 0x3, 0x4, 0x2)
    /home/user97/go/src/github.com/cbergoon/merkletree/merkle_tree.go:104 +0x50f
github.com/cbergoon/merkletree.buildIntermediate(0xc4200520c0, 0x6, 0x8, 0x4)
    /home/user97/go/src/github.com/cbergoon/merkletree/merkle_tree.go:118 +0x4e6
github.com/cbergoon/merkletree.buildWithContent(0xc420076000, 0x5, 0x8, 0x0, 0xc420041da8, 0x485487, 0x5251c0, 0xc42000c018, 0xc420041f50)
    /home/user97/go/src/github.com/cbergoon/merkletree/merkle_tree.go:94 +0x2ff
github.com/cbergoon/merkletree.NewTree(0xc420076000, 0x5, 0x8, 0x22, 0x0, 0x0)
    /home/user97/go/src/github.com/cbergoon/merkletree/merkle_tree.go:63 +0x4c
main.main()
    /home/user97/go/src/go_scratch/main.go:41 +0x51d

I think allocating the slice differently should fix this.

[cbergoon]

The issue here has to do with the way a merkle tree handles an odd number of leaf nodes. When there is an odd number of entries the final entry is duplicated to make a 'full' tree.

This scenario was accounted for in buildWithContent(...) when there was an odd number of leaves. It was not accounted for in the intermediate levels of the tree (which are built in the buildIntermediate(...) function).

For example, if you have 5 leaf nodes the 5th is duplicated to make 6. When the 2nd layer of the tree is built there should be 3 nodes - to create the 3rd layer from the 2nd the nodes at position 1 and 2 are hashed together and and the node at position 3 should be hashed with itself. It was being hashed with the the 4th which does not exist hence the index out of range error you are seeing.

I will merge the fix shortly to fix it with a test to check for this. Thanks for finding this!

Cam

[swapnil-pandey]

@cbergoon Changes you can add the following changes in buildIntermediate function.

[cbergoon]

@swapnil-pandey make sure you have the latest code after the changes above were merged in. These changes should resolve the issue for you.

Its hard to tell for sure b/c it is out of context but I think the snippet you provided intends to build a tree that for an odd number of nodes makes the right node nil and builds the next node with only the existing hash from the left. This is fine and could be implemented this way but I think it would cause issues in other areas for this implementation. For example, verification of the tree b/c there is an assumption that both left and right are present. The structure that this implementation follows in this scenario is shown in this image: https://cdn-images-1.medium.com/max/640/0*nwrna5RNR0SNZej9.

[swapnil-pandey]

@cbergoon I was using your code for a project and the snippet I shared was what I did to make things work. Just shared to help. And of-course I had to make corresponding changes in the verification of the tree and calculateNodeHash. In the two functions I checked if the right parent is nil or not and proceeded accordingly.

Also, does the latest code takes care of the issue if at any intermediate level, the number of nodes are odd?

[cbergoon]

@swapnil-pandey cool thanks for sharing! You've probably already considered this but, because we are building the trees differently - the resulting roots in certain cases will be incompatible with each other.

And to answer your question, yes I believe it will work for any intermediate level. Feel free to make a pull request to improve tests/verifications or anything else you have improved.