Repository: celestiaorg/nmt (go)

Issue:
Change NMT Leaf Node to Hash the NID
Implementation for the Namespaced Merkle Tree (NMT) leaf node must be changed to hash the Namespace ID.  In the new implementation, leaf node 'node' of share data d should be structured as follows:

node.n_min = d.namespaceID
node.n_max = d.namespaceID
node.v = h(0x00, d.namespaceID, d.rawData)

See [PR #203](https://github.com/celestiaorg/celestia-specs/pull/203) opened for celestia-specs for the current structure of the NMT leaf node. 

Pull request description:
Adhere to specs and hash the nid in leaf
closes #45 
ref: https://github.com/celestiaorg/celestia-specs/pull/203

Patch:
diff --git a/hasher.go b/hasher.go
index 7091713..b770179 100644
--- a/hasher.go
+++ b/hasher.go
@@ -99,9 +99,10 @@ func (n *Hasher) HashLeaf(leaf []byte) []byte {
 	h.Reset()
 
 	nID := leaf[:n.NamespaceLen]
-	data := leaf[n.NamespaceLen:]
-	res := append(append(make([]byte, 0), nID...), nID...)
-	data = append([]byte{LeafPrefix}, data...)
+	resLen := int(2*n.NamespaceLen) + n.Hash.Size()
+	res := append(append(make([]byte, 0, resLen), nID...), nID...)
+	// h(0x00, d.namespaceID, d.rawData)
+	data := append(append(make([]byte, 0, len(leaf)+1), LeafPrefix), leaf...)
 	h.Write(data)
 	return h.Sum(res)
 }


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index f805314..d98f66c 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -18,8 +18,10 @@ func Test_namespacedTreeHasher_HashLeaf(t *testing.T) {
 	defaultRawData := []byte("a blockchain is a chain of blocks")
 
 	// Note: ensure we only hash in the raw data without the namespace prefixes
-	emptyHash := sum(crypto.SHA256, []byte{LeafPrefix}, []byte{})
-	defaultHash := sum(crypto.SHA256, []byte{LeafPrefix}, defaultRawData)
+	emptyHashZeroNID := sum(crypto.SHA256, []byte{LeafPrefix}, zeroNID, []byte{})
+	emptyHashOneNID := sum(crypto.SHA256, []byte{LeafPrefix}, oneNID, []byte{})
+	defaultHashOneNID := sum(crypto.SHA256, []byte{LeafPrefix}, oneNID, defaultRawData)
+	defaultHashLongNID := sum(crypto.SHA256, []byte{LeafPrefix}, longNID, defaultRawData)
 
 	oneNIDLeaf := append(oneNID, defaultRawData...)
 	longNIDLeaf := append(longNID, defaultRawData...)
@@ -30,11 +32,11 @@ func Test_namespacedTreeHasher_HashLeaf(t *testing.T) {
 		leaf  []byte
 		want  []byte
 	}{
-		{"1 byte namespaced empty leaf", 1, zeroNID, append(append(zeroNID, zeroNID...), emptyHash...)},
-		{"1 byte namespaced empty leaf", 1, oneNID, append(append(oneNID, oneNID...), emptyHash...)},
-		{"1 byte namespaced leaf with data", 1, oneNIDLeaf, append(append(oneNID, oneNID...), defaultHash...)},
-		{"namespaced empty leaf", 9, longNIDLeaf, append(append(longNID, longNID...), defaultHash...)},
-		{"namespaced leaf with data", 9, longNID, append(append(longNID, longNID...), emptyHash...)},
+		{"1 byte namespaced empty leaf", 1, zeroNID, append(append(zeroNID, zeroNID...), emptyHashZeroNID...)},
+		{"1 byte namespaced empty leaf", 1, oneNID, append(append(oneNID, oneNID...), emptyHashOneNID...)},
+		{"1 byte namespaced leaf with data", 1, oneNIDLeaf, append(append(oneNID, oneNID...), defaultHashOneNID...)},
+		{"namespaced leaf with data", 9, longNIDLeaf, append(append(longNID, longNID...), defaultHashLongNID...)},
+		{"namespaced empty leaf", 9, longNID, append(append(longNID, longNID...), sum(crypto.SHA256, []byte{LeafPrefix}, longNID, []byte{})...)},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {
diff --git a/nmt_test.go b/nmt_test.go
index 6763b35..f585b45 100644
--- a/nmt_test.go
+++ b/nmt_test.go
@@ -120,13 +120,13 @@ func TestNamespacedMerkleTree_Push(t *testing.T) {
 
 func TestNamespacedMerkleTreeRoot(t *testing.T) {
 	// does some sanity checks on root computation
-	// TODO: add in more realistic test-vectors
 	zeroNs := []byte{0, 0, 0}
 	onesNS := []byte{1, 1, 1}
-	leaf := []byte("leaf1")
-	leafHash := sum(crypto.SHA256, []byte{LeafPrefix}, leaf)
-	zeroFlaggedLeaf := append(append(zeroNs, zeroNs...), leafHash...)
-	oneFlaggedLeaf := append(append(onesNS, onesNS...), leafHash...)
+	leafData := []byte("leaf1")
+	zeroLeafHash := sum(crypto.SHA256, []byte{LeafPrefix}, zeroNs, leafData)
+	oneLeafHash := sum(crypto.SHA256, []byte{LeafPrefix}, onesNS, leafData)
+	zeroFlaggedLeaf := append(append(zeroNs, zeroNs...), zeroLeafHash...)
+	oneFlaggedLeaf := append(append(onesNS, onesNS...), oneLeafHash...)
 	twoZeroLeafsRoot := sum(crypto.SHA256, []byte{NodePrefix}, zeroFlaggedLeaf, zeroFlaggedLeaf)
 	diffNSLeafsRoot := sum(crypto.SHA256, []byte{NodePrefix}, zeroFlaggedLeaf, oneFlaggedLeaf)
 	emptyRoot := crypto.SHA256.New().Sum(nil)
@@ -142,9 +142,9 @@ func TestNamespacedMerkleTreeRoot(t *testing.T) {
 		// default empty root according to base case:
 		// https://github.com/celestiaorg/celestiaorg-specs/blob/master/specs/data_structures.md#namespace-merkle-tree
 		{"Empty", 3, nil, zeroNs, zeroNs, emptyRoot},
-		{"One leaf", 3, []namespaceDataPair{newNamespaceDataPair(zeroNs, leaf)}, zeroNs, zeroNs, leafHash},
-		{"Two leaves", 3, []namespaceDataPair{newNamespaceDataPair(zeroNs, leaf), newNamespaceDataPair(zeroNs, leaf)}, zeroNs, zeroNs, twoZeroLeafsRoot},
-		{"Two leaves diff namespaces", 3, []namespaceDataPair{newNamespaceDataPair(zeroNs, leaf), newNamespaceDataPair(onesNS, leaf)}, zeroNs, onesNS, diffNSLeafsRoot},
+		{"One leaf", 3, []namespaceDataPair{newNamespaceDataPair(zeroNs, leafData)}, zeroNs, zeroNs, sum(crypto.SHA256, []byte{LeafPrefix}, zeroNs, leafData)},
+		{"Two leaves", 3, []namespaceDataPair{newNamespaceDataPair(zeroNs, leafData), newNamespaceDataPair(zeroNs, leafData)}, zeroNs, zeroNs, twoZeroLeafsRoot},
+		{"Two leaves diff namespaces", 3, []namespaceDataPair{newNamespaceDataPair(zeroNs, leafData), newNamespaceDataPair(onesNS, leafData)}, zeroNs, onesNS, diffNSLeafsRoot},
 	}
 	for _, tt := range tests {
 		t.Run(tt.name, func(t *testing.T) {