jellyfish icon indicating copy to clipboard operation
jellyfish copied to clipboard

`MerkleProof` should not include position or leaf value

Open ggutoski opened this issue 6 months ago • 4 comments

This issue is an opinionated suggestion. Others may disagree.

MerkleProof struct contains:

  • 2 copies of index position
  • leaf value

These items should not be in the merkle proof. Instead, MerkleTree::verify should take them as separate args. If the leaf value is large then the size of the merkle proof is unnecessarily large.

First copy of index position is pos field in `MerkleProof struct: https://github.com/EspressoSystems/jellyfish/blob/92714a4cc509fac07b8e8fc321fc0271c5dbe6b6/merkle_tree/src/internal.rs#L139-L150

Digging into MerklePath we see

https://github.com/EspressoSystems/jellyfish/blob/92714a4cc509fac07b8e8fc321fc0271c5dbe6b6/merkle_tree/src/internal.rs#L84

where MerkleNode is an enum

https://github.com/EspressoSystems/jellyfish/blob/92714a4cc509fac07b8e8fc321fc0271c5dbe6b6/merkle_tree/src/internal.rs#L25

with Leaf variant

https://github.com/EspressoSystems/jellyfish/blob/92714a4cc509fac07b8e8fc321fc0271c5dbe6b6/merkle_tree/src/internal.rs#L37-L47

where we find a second copy of pos and the leaf value elem.

If, as I suggest, we remove these occurrences of pos then MerkleProof becomes just a wrapper for MerklePath. In that case we should eliminate the wrapper and just use MerklePath.

I suggest that MerklePath be an opaque struct. No need to expose the fact that it's a Vec<MerkleNode>.

ggutoski avatar Aug 16 '24 18:08 ggutoski