MerkleProof should not include position or leaf value

[ggutoski]

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:

jellyfish/merkle_tree/src/internal.rs

Lines 139 to 150 in 92714a4

	pub struct MerkleProof<E, I, T, const ARITY: usize>
	where
	E: Element,
	I: Index,
	T: NodeValue,
	{
	/// Proof of inclusion for element at index `pos`
	#[serde(with = "canonical")]
	pub pos: I,
	/// Nodes of proof path, from root to leaf
	pub proof: MerklePath<E, I, T>,
	}

Digging into MerklePath we see

jellyfish/merkle_tree/src/internal.rs

Line 84 in 92714a4

pub type MerklePath<E, I, T> = Vec<MerkleNode<E, I, T>>;

where MerkleNode is an enum

jellyfish/merkle_tree/src/internal.rs

Line 25 in 92714a4

pub enum MerkleNode<E: Element, I: Index, T: NodeValue> {

with Leaf variant

jellyfish/merkle_tree/src/internal.rs

Lines 37 to 47 in 92714a4

	Leaf {
	/// Merkle hash value of this leaf
	#[serde(with = "canonical")]
	value: T,
	/// Index of this leaf
	#[serde(with = "canonical")]
	pos: I,
	/// Associated element of this leaf
	#[serde(with = "canonical")]
	elem: E,
	},

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>.

[mrain]

I tend to keep it in the original form. But this comment is valuable:

If the leaf value is large then the size of the merkle proof is unnecessarily large.

[ggutoski]

Forgot to mention: currently MerkleTree::verify takes a redundant arg pos. The current implementation merely checks pos against one of its copies inside MerkleProof:

jellyfish/merkle_tree/src/macros.rs

Lines 81 to 90 in 92714a4

	fn verify(
	root: impl Borrow<Self::NodeValue>,
	pos: impl Borrow<Self::Index>,
	proof: impl Borrow<Self::MembershipProof>,
	) -> Result<VerificationResult, MerkleTreeError> {
	if *pos.borrow() != proof.borrow().pos {
	return Ok(Err(())); // invalid proof for the given pos
	}
	proof.borrow().verify_membership_proof::<H>(root.borrow())
	}

Instead verify args should include both pos and elem or neither of these items. Seems strange to take only one but not the other. Naturally, my suggestion is to include both and then remove them from MerkleProof.

[mrain]

My opinion has changed. We should make these changes along with #642

[philippecamacho]

We will go with two kind of Merkle proof: with and without leaf.