celestiaorg / smt

A Go library that implements a Sparse Merkle tree for a key-value map.
https://godoc.org/github.com/celestiaorg/smt
MIT License
138 stars 53 forks source link

Set proof's NonMembershipLeafData to nil for membership proofs #17

Closed adlerjohn closed 3 years ago

adlerjohn commented 3 years ago

Currently, the proof's NonMembershipLeafData field is always set to the leaf data, even if the proof ends up being a membership proof. Correct this and update documentation to make it clear that membership proofs have nil value for this field.

musalbas commented 3 years ago

LGTM but I would fold the two if statements into a single if statement for better readability. You could include parseLeaf in the if statement itself. https://golang.org/doc/effective_go#if

Parsing a leaf is a neglible computation.

adlerjohn commented 3 years ago

I might be missing something, but I don't think that works immediately:

  1. parseLeaf assumes its input leafData is non-nil, but if leafHash is placeholder then leafData is nil
  2. Compounding with the above, parseLeaf returns 2 values, so it can't be used within an if statement (except for in the initialization part). But because parseLeaf assumes its input is non-nil, we can't call it without first checking if leafData is nil (or equivalently, that leafHash is placeholder, which is already the check in place).

Current code (which enforces that leafData is non-nil before calling parseLeaf):

if !bytes.Equal(leafHash, smt.th.placeholder()) {
    actualPath, _ := smt.th.parseLeaf(leafData)
    if !bytes.Equal(actualPath, path) {
        // This is a non-membership proof that involves showing a different leaf.
        // Add the leaf data to the proof.
        nonMembershipLeafData = leafData
    }
}

In one if statement, which errors:

if actualPath, _ := smt.th.parseLeaf(leafData); !bytes.Equal(leafHash, smt.th.placeholder()) &&
    !bytes.Equal(actualPath, path) {
    // This is a non-membership proof that involves showing a different leaf.
    // Add the leaf data to the proof.
    nonMembershipLeafData = leafData
}
musalbas commented 3 years ago

Ah OK, that makes sense.