Investigate failing MerkleTreeSimpleTest in zerocashTest.

[nathan-at-least]

Description here: Electric-Coin-Company/libzerocash#13 (comment)

[defuse]

Is this the same as #391?

[defuse]

I got the test to pass by fixing two bugs in the test:

• At the bottom, it's manually creating the witness for coin index 3, but comparing against the witness for coin index 1.
• It's using a depth-16 tree and changing it to a depth-3 tree makes it work.

But I don't exactly understand what the witnesses are supposed to be, so I'm not sure if it's the test that's wrong or if it's the merkle tree implementation that's wrong.

[defuse]

Another problem with the test is that the "christina" witness vector is too big, since it's re-used between the depth-64 and depth-16 tree, and so the getWitness() being tested only fills the first 16 elements of it.

Another clue is that the non-zero witness elements appear at the end of the generated witness, but the test at the bottom expect them to be at the front. So either A: The witness generator is doing the right thing, and the test at the bottom expected the tree to have depth 3 or B: The witness generator is mistakenly padding with zeroes on the front, instead of the back.

[defuse]

Yeah, zeroes should be up front, because there's a bunch of levels you want to ignore and then finally the subtree you want to check. So it's option B. This isn't the same as #391.

[defuse]

There's a pull request for this: Electric-Coin-Company/libzerocash#17

It uncovered the bug in #461.