libiop
libiop copied to clipboard
Caphash optimization
Cap hashing was implemented for merkle trees. The algebraic and non-algebraic cap hashes were both implemented in hash_enum.tcc, as well as the dummy algebraic hash. See issue https://github.com/scipr-lab/libiop/issues/41.
A bug was fixed that merkle tree membership proof generation and verification didn't work when the input queries weren't sorted and unique. They now work when the tree is not zero knowledge, but when the tree is set to be zero knowledge, the code still fails.
The hash count method was updated to count each two-to-one hash as 2 units and the cap hash as 1 unit per input.
More tests were added, to test cap hashing, and to test large trees with randomly generated query leaves. The code no not test unsorted non-unique queries since that still fails for zero knowledge trees.
No snark protocols currently take advantage of the cap hash; they still have cap size set to 2.
~Changes are complete, but not ready to merge because I started working based off of PR #43, so that should preferably be merged first.~ Ready for review
I did a pass of the code, and most are smaller points. Let me know when you want me to reach out to the repo's owner to coordinate merging this PR.