Repository: celestiaorg/nmt
Pull request #91 (2023-01-03 13:00:35)

feat!: implementing `hash.Hash` interface
<!--
Please read and fill out this form before submitting your PR.

Please make sure you have reviewed our contributors guide before submitting your
first PR.
-->

## Overview

Resolves a TODO from celestia-node:
https://github.com/celestiaorg/celestia-node/blob/8f13efab8aa314d52708dea8873eea70027745cb/share/ipld/namespace_hasher.go#L21-L33

Motivation: Instead of only providing utilities that require knowing if a value is an inner node or a leaf to hash, implement the `hash.Hash` interface so that `Write`/`Sum` can be used generally over both node types.

This PR is breaking as it changes the `Hasher` constructor to include share size.

To be discussed:
- [ ] Is this even desired? We want it in node but hasn't been discussed elsewhere AFAIK
- [ ] This PR introduces testify a dep, I can rewrite the tests to exclude this if unwanted
- [ ] Why is NamespaceLen exported, and has a getter in addition? Should `shareSize` also be exported then?

<!-- 
Please provide an explanation of the PR, including the appropriate context,
background, goal, and rationale. If there is an issue with this information,
please provide a tl;dr and link the issue. 
-->

## Checklist

<!-- 
Please complete the checklist to ensure that the PR is ready to be reviewed.

IMPORTANT:
PRs should be left in Draft until the below checklist is completed.
-->

- [X] New and updated code has appropriate documentation
- [X] New and updated code has new and/or updated testing
- [ ] Required CI checks are passing


codecov[bot]: # [Codecov](https://codecov.io/gh/celestiaorg/nmt/pull/91?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) Report
> Merging [#91](https://codecov.io/gh/celestiaorg/nmt/pull/91?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (d8cc002) into [master](https://codecov.io/gh/celestiaorg/nmt/commit/7d31915d17e5019abef8bdea89a3182842331cba?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (7d31915) will **decrease** coverage by `1.39%`.
> The diff coverage is `83.72%`.

```diff
@@            Coverage Diff             @@
##           master      #91      +/-   ##
==========================================
- Coverage   96.75%   95.35%   -1.40%     
==========================================
  Files           6        6              
  Lines         400      431      +31     
==========================================
+ Hits          387      411      +24     
- Misses          7       14       +7     
  Partials        6        6              
```


| [Impacted Files](https://codecov.io/gh/celestiaorg/nmt/pull/91?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) | Coverage Δ | |
|---|---|---|
| [nmt.go](https://codecov.io/gh/celestiaorg/nmt/pull/91/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-bm10Lmdv) | `96.53% <50.00%> (-2.28%)` | :arrow_down: |
| [hasher.go](https://codecov.io/gh/celestiaorg/nmt/pull/91/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-aGFzaGVyLmdv) | `96.15% <90.90%> (-3.85%)` | :arrow_down: |
| [proof.go](https://codecov.io/gh/celestiaorg/nmt/pull/91/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-cHJvb2YuZ28=) | `96.59% <100.00%> (ø)` | |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg)

Wondertan: Doesn't diverge from implementation in celestia-node so LGTM
Wondertan: I lost my nmt approval perms😢

Patch:
diff --git a/go.mod b/go.mod
index 1b152c7..7e464d2 100644
--- a/go.mod
+++ b/go.mod
@@ -5,4 +5,11 @@ go 1.18
 require (
 	github.com/celestiaorg/merkletree v0.0.0-20210714075610-a84dc3ddbbe4
 	github.com/google/gofuzz v1.2.0
+	github.com/stretchr/testify v1.8.1
+)
+
+require (
+	github.com/davecgh/go-spew v1.1.1 // indirect
+	github.com/pmezard/go-difflib v1.0.0 // indirect
+	gopkg.in/yaml.v3 v3.0.1 // indirect
 )
diff --git a/go.sum b/go.sum
index bec8890..4c5d75c 100644
--- a/go.sum
+++ b/go.sum
@@ -1,7 +1,19 @@
 github.com/celestiaorg/merkletree v0.0.0-20210714075610-a84dc3ddbbe4 h1:CJdIpo8n5MFP2MwK0gSRcOVlDlFdQJO1p+FqdxYzmvc=
 github.com/celestiaorg/merkletree v0.0.0-20210714075610-a84dc3ddbbe4/go.mod h1:fzuHnhzj1pUygGz+1ZkB3uQbEUL4htqCGJ4Qs2LwMZA=
+github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
 github.com/google/gofuzz v1.2.0 h1:xRy4A+RhZaiKjJ1bPfwQ8sedCA+YS2YcCHW6ec7JMi0=
 github.com/google/gofuzz v1.2.0/go.mod h1:dBl0BpW6vV/+mYPU4Po3pmUjxk6FQPldtuIdl/M65Eg=
+github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
+github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
+github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
+github.com/stretchr/objx v0.4.0/go.mod h1:YvHI0jy2hoMjB+UWwv71VJQ9isScKT/TqJzVSSt89Yw=
+github.com/stretchr/objx v0.5.0/go.mod h1:Yh+to48EsGEfYuaHDzXPcE3xhTkx73EhmCGUpEOglKo=
+github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
+github.com/stretchr/testify v1.8.1 h1:w7B6lhMri9wdJUVmEZPGGhZzrYTPvgJArz7wNPgYKsk=
+github.com/stretchr/testify v1.8.1/go.mod h1:w2LPCIKwWwSfY2zedu0+kehJoqGctiVI29o6fzry7u4=
 gitlab.com/NebulousLabs/errors v0.0.0-20171229012116-7ead97ef90b8 h1:gZfMjx7Jr6N8b7iJO4eUjDsn6xJqoyXg8D+ogdoAfKY=
 gitlab.com/NebulousLabs/errors v0.0.0-20171229012116-7ead97ef90b8/go.mod h1:ZkMZ0dpQyWwlENaeZVBiQRjhMEZvk6VTXquzl3FOFP8=
 gitlab.com/NebulousLabs/fastrand v0.0.0-20181126182046-603482d69e40 h1:dizWJqTWjwyD8KGcMOwgrkqu1JIkofYgKkmDeNE7oAs=
@@ -14,3 +26,8 @@ golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5h
 golang.org/x/sys v0.0.0-20190412213103-97732733099d h1:+R4KGOnez64A81RvjARKc4UT5/tI9ujCIVX+P5KiHuI=
 golang.org/x/sys v0.0.0-20190412213103-97732733099d/go.mod h1:h1NjWce9XRLGQEsW7wpKNCjG9DtNlClVuFLEZdDNbEs=
 golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
+gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
+gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
+gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/hasher.go b/hasher.go
index d8b0bee..04b5358 100644
--- a/hasher.go
+++ b/hasher.go
@@ -11,10 +11,10 @@ import (
 const (
 	LeafPrefix = 0
 	NodePrefix = 1
-
-	DefaultNamespaceIDLen = 8
 )
 
+var _ hash.Hash = (*Hasher)(nil)
+
 // defaultHasher uses sha256 as a base-hasher, 8 bytes
 // for the namespace IDs and ignores the maximum possible namespace.
 var defaultHasher = NewNmtHasher(sha256.New(), DefaultNamespaceIDLen, true)
@@ -46,7 +46,7 @@ func Sha256Namespace8FlaggedLeaf(namespacedData []byte) []byte {
 // The output will also be of length 2*DefaultNamespaceIDLen+sha256.Size = 48 bytes.
 func Sha256Namespace8FlaggedInner(leftRight []byte) []byte {
 	const flagLen = DefaultNamespaceIDLen * 2
-	sha256Len := defaultHasher.Size()
+	sha256Len := defaultHasher.baseHasher.Size()
 	left := leftRight[:flagLen+sha256Len]
 	right := leftRight[flagLen+sha256Len:]
 
@@ -54,11 +54,14 @@ func Sha256Namespace8FlaggedInner(leftRight []byte) []byte {
 }
 
 type Hasher struct {
-	hash.Hash
+	baseHasher   hash.Hash
 	NamespaceLen namespace.IDSize
 
 	ignoreMaxNs      bool
 	precomputedMaxNs namespace.ID
+
+	tp   byte   // keeps type of NMT node to be hashed
+	data []byte // written data of the NMT node
 }
 
 func (n *Hasher) IsMaxNamespaceIDIgnored() bool {
@@ -71,16 +74,70 @@ func (n *Hasher) NamespaceSize() namespace.IDSize {
 
 func NewNmtHasher(baseHasher hash.Hash, nidLen namespace.IDSize, ignoreMaxNamespace bool) *Hasher {
 	return &Hasher{
-		Hash:             baseHasher,
+		baseHasher:       baseHasher,
 		NamespaceLen:     nidLen,
 		ignoreMaxNs:      ignoreMaxNamespace,
 		precomputedMaxNs: bytes.Repeat([]byte{0xFF}, int(nidLen)),
 	}
 }
 
+// Size returns the number of bytes Sum will return.
+func (n *Hasher) Size() int {
+	return n.baseHasher.Size() + int(n.NamespaceLen)*2
+}
+
+// Write writes the namespaced data to be hashed.
+//
+// Requires data of fixed size to match leaf or inner NMT nodes.
+// Only a single write is allowed.
+func (n *Hasher) Write(data []byte) (int, error) {
+	if n.data != nil {
+		panic("only a single Write is allowed")
+	}
+
+	ln := len(data)
+	switch ln {
+	// inner nodes are made up of the nmt hashes of the left and right children
+	case n.Size() * 2:
+		n.tp = NodePrefix
+	// leaf nodes contain the namespace length and a share
+	default:
+		n.tp = LeafPrefix
+	}
+
+	n.data = data
+	return ln, nil
+}
+
+// Sum computes the hash.
+// Does not append the given suffix, violating the interface.
+func (n *Hasher) Sum([]byte) []byte {
+	switch n.tp {
+	case LeafPrefix:
+		return n.HashLeaf(n.data)
+	case NodePrefix:
+		flagLen := int(n.NamespaceLen) * 2
+		sha256Len := n.Size()
+		return n.HashNode(n.data[:flagLen+sha256Len], n.data[flagLen+sha256Len:])
+	default:
+		panic("nmt node type wasn't set")
+	}
+}
+
+// Reset resets the Hash to its initial state.
+func (n *Hasher) Reset() {
+	n.tp, n.data = 255, nil // reset with an invalid node type, as zero value is a valid Leaf
+	n.baseHasher.Reset()
+}
+
+// BlockSize returns the hash's underlying block size.
+func (n *Hasher) BlockSize() int {
+	return n.baseHasher.BlockSize()
+}
+
 func (n *Hasher) EmptyRoot() []byte {
 	emptyNs := bytes.Repeat([]byte{0}, int(n.NamespaceLen))
-	h := n.Sum(nil)
+	h := n.baseHasher.Sum(nil)
 	digest := append(append(emptyNs, emptyNs...), h...)
 
 	return digest
@@ -96,11 +153,11 @@ func (n *Hasher) EmptyRoot() []byte {
 //
 //nolint:errcheck
 func (n *Hasher) HashLeaf(leaf []byte) []byte {
-	h := n.Hash
+	h := n.baseHasher
 	h.Reset()
 
 	nID := leaf[:n.NamespaceLen]
-	resLen := int(2*n.NamespaceLen) + n.Hash.Size()
+	resLen := int(2*n.NamespaceLen) + n.baseHasher.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...)
@@ -113,7 +170,7 @@ func (n *Hasher) HashLeaf(leaf []byte) []byte {
 // left and right child node bytes, including their respective min and max namespace IDs:
 // left = left.Min() || left.Max() || l.Hash().
 func (n *Hasher) HashNode(l, r []byte) []byte {
-	h := n.Hash
+	h := n.baseHasher
 	h.Reset()
 
 	// the actual hash result of the children got extended (or flagged) by their
diff --git a/nmt.go b/nmt.go
index c7f0122..0facc69 100644
--- a/nmt.go
+++ b/nmt.go
@@ -11,6 +11,11 @@ import (
 	"github.com/celestiaorg/nmt/namespace"
 )
 
+const (
+	DefaultNamespaceIDLen = 8
+	DefaultCapacity       = 128
+)
+
 var (
 	ErrInvalidRange            = errors.New("invalid proof range")
 	ErrMismatchedNamespaceSize = errors.New("mismatching namespace sizes")
@@ -94,8 +99,8 @@ type NamespacedMerkleTree struct {
 func New(h hash.Hash, setters ...Option) *NamespacedMerkleTree {
 	// default options:
 	opts := &Options{
-		InitialCapacity:    128,
-		NamespaceIDSize:    8,
+		InitialCapacity:    DefaultCapacity,
+		NamespaceIDSize:    DefaultNamespaceIDLen,
 		IgnoreMaxNamespace: true,
 		NodeVisitor:        noOp,
 	}


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index c7a5218..f46c0d1 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -7,9 +7,18 @@ import (
 	"reflect"
 	"testing"
 
+	"github.com/stretchr/testify/assert"
+	"github.com/stretchr/testify/require"
+
 	"github.com/celestiaorg/nmt/namespace"
 )
 
+const (
+	hashSize  = sha256.Size + (2 * DefaultNamespaceIDLen)
+	leafSize  = DefaultNamespaceIDLen + 512
+	innerSize = 2 * hashSize
+)
+
 func Test_namespacedTreeHasher_HashLeaf(t *testing.T) {
 	zeroNID := []byte{0}
 	oneNID := []byte{1}
@@ -165,3 +174,74 @@ func sum(hash crypto.Hash, data ...[]byte) []byte {
 
 	return h.Sum(nil)
 }
+
+func TestNamespaceHasherWrite(t *testing.T) {
+	tt := []struct {
+		name         string
+		expectedSize int
+		writtenSize  int
+	}{
+		{
+			"Leaf",
+			leafSize,
+			leafSize,
+		},
+		{
+			"Inner",
+			innerSize,
+			innerSize,
+		},
+	}
+
+	for _, ts := range tt {
+		t.Run("Success"+ts.name, func(t *testing.T) {
+			h := defaultHasher
+			h.Reset()
+			n, err := h.Write(make([]byte, ts.writtenSize))
+			assert.NoError(t, err)
+			assert.Equal(t, ts.expectedSize, n)
+			assert.Equal(t, ts.expectedSize, len(h.data))
+		})
+	}
+
+	t.Run("ErrorSecondWrite", func(t *testing.T) {
+		h := defaultHasher
+		h.Reset()
+		n, err := h.Write(make([]byte, leafSize))
+		assert.NoError(t, err)
+		assert.Equal(t, leafSize, n)
+
+		require.Panics(t, func() {
+			_, _ = h.Write(make([]byte, leafSize))
+		})
+	})
+}
+
+func TestNamespaceHasherSum(t *testing.T) {
+	tt := []struct {
+		name         string
+		expectedSize int
+		writtenSize  int
+	}{
+		{
+			"Leaf",
+			hashSize,
+			leafSize,
+		},
+		{
+			"Inner",
+			hashSize,
+			innerSize,
+		},
+	}
+
+	for _, ts := range tt {
+		t.Run("Success"+ts.name, func(t *testing.T) {
+			h := defaultHasher
+			h.Reset()
+			_, _ = h.Write(make([]byte, ts.writtenSize))
+			sum := h.Sum(nil)
+			assert.Equal(t, len(sum), ts.expectedSize)
+		})
+	}
+}