Add MerkleTree::gen_nth_proof and Proof::index.

[afck]

Also fixes Clippy warnings in the test code, and runs Clippy with --tests --all-features in Travis.

Fixes #31

[afck]

Have you already decided how to proceed with rustfmt? I'm happy to update the PR either way.

[psivesely]

I've been dealing with other stuff and I know @romac is quite busy as a grad student, so apologies for the late response. Since this is something you could use, it seems like we just shouldn't worry about rustfmt for now and figure out a strategy later.

[afck]

Thank you, it would be great to get this merged! And I'm happy with any of the above (possibly temporary) solutions: I can keep or revert that Rust nightly line, and/or apply the latest rustfmt and/or upgrade Clippy — anything that doesn't break CI.

[afck]

I merged the value getter and lemma generation to traverse the tree only once. Not sure whether it's cleaner, but it's shorter and probably a bit more efficient. The >> 1 is also gone.

I added two test cases where None is expected.

you could also change the way the inclusion proof generation code works

You mean: first find the value's index, then call Lemma::new_by_index? That might be faster than the current code, yes. But regarding efficiency, I wonder whether a much bigger change like https://github.com/SpinResearch/merkle.rs/issues/4 should be reconsidered.

[psivesely]

If a tree is well-formed you know exactly how it's going to be structured. I think this code should assume the tree is well structured and act accordingly. Then there's no need to traverse all the way down the left side until we hit a leaf, realize count != 1, go back up one node and check the other leaf, see that still count != 1, go back up two nodes, etc.. I don't think there's even a need for match at all. We should be able to determine the exact sequences of left and right steps down the tree to get to a given index when given the leaf count of a tree, navigating directly to our index/value and creating the inclusion proof along the way.

[afck]

Isn't that pretty much what Lemma::new_by_index already does? It never backtracks and checks other leaves: the path it takes depends only on the index and count. Just when it hits a leaf, I added the sanity check that count is indeed 1 now: If it isn't, the tree isn't structured correctly. Note that count isn't the size of the whole tree, but the expected size of the subtree at the current node.

(For the existing by-value proof constructor, we still have to check all the leaves sequentially, of course, since we don't know the index of that value.)

[psivesely]

Maybe I read the wrong code. Will check later.

El 11/06/2018, a la(s) 10:13, Andreas Fackler notifications@github.com escribió:

Isn't that pretty much what Lemma::new_by_index already does? It never backtracks and checks other leaves: the path it takes depends only on the index and count. Just when it hits a leaf, I added the sanity check that count is indeed 1 now: If it isn't, the tree isn't structured correctly. Note that count isn't the size of the whole tree, but the expected size of the subtree at the current node.

(For the existing by-value proof constructor, we still have to check all the leaves sequentially, of course, since we don't know the index of that value.)

— You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[psivesely]

Isn't that pretty much what Lemma::new_by_index already does? It never backtracks and checks other leaves: the path it takes depends only on the index and count.

It is now because of how you branch using this predicate. But if you look at the code before you combined value getter and inclusion proof generation code into a single traversing function, you'll see here that you were traversing sequentially as I described before. At least I think I have this all right :sweat_smile:.

Just having skimmed it--looks good--but I'll take a closer look and give a proper follow-up review tomorrow.

[afck]

I see what you mean. But also the old code would never backtrack more than one step: It's just that it would do the index vs. count check inside the new_by_index call, and immediately return if it needs to take the other branch. I agree that wasn't a good way to do it. (But it was still O(log n) and not sequential.)

[psivesely]

I see what you mean. But also the old code would never backtrack more than one step: It's just that it would do the index vs. count check inside the new_by_index call, and immediately return if it needs to take the other branch. I agree that wasn't a good way to do it.

Ah, you're right. When I first read this if statement I mentally wrote it off as only being significant the first time new_by_index was called (by gen_nth_proof)--an initial check--and not an essential part of traversal logic that works in tandem with new_tree_proof_by_index. Still, it is more efficient as you pointed out by a linear factor now, and as another plus to the new version, I think it's easier to follow.

[psivesely]

Okay, so just that last small change, and then I think this is good to merge.

Now I just got to learn about this whole BFT business. Looks important!

[afck]

BFT business. Looks important!

It's certainly fun and interesting. :slightly_smiling_face:

[psivesely]

Blocked by #40.

[psivesely]

Update: blocked by #44, not #40 anymore.

[afck]

I merged it with latest master.

I was also meaning to add --tests to the Clippy call in .travis.yml, but either I'm hallucinating (I blame the hot weather!) or I ran into a false positive.

[romac]

@afck Can you please rebase it on top of master, so that I can merge it?

[afck]

Done. (I think — there were plenty of conflicts.)

[romac]

Sweet, thanks :) Expect a v1.9.0 release sometime this week.