use hashing from merkle package

8 files changed, 51 insertions, 57 deletions

diff --git a/pkg/types/crypto.go b/pkg/types/crypto.go
index df93108..8660c27 100644
--- a/pkg/types/crypto.go
+++ b/pkg/types/crypto.go
@@ -2,29 +2,14 @@ package types
 
 import (
 	"crypto/ed25519"
-	"crypto/sha256"
 )
 
 const (
-	HashSize      = sha256.Size
 	SignatureSize = ed25519.SignatureSize
 	PublicKeySize = ed25519.PublicKeySize
-
-	LeafNodePrefix     = byte(0x00)
-	InteriorNodePrefix = byte(0x01)
 )
 
 type (
-	Hash      [HashSize]byte
 	Signature [SignatureSize]byte
 	PublicKey [PublicKeySize]byte
 )
-
-func HashFn(buf []byte) *Hash {
-	var hash Hash = sha256.Sum256(buf)
-	return &hash
-}
-
-func LeafHash(buf []byte) *Hash {
-	return HashFn(append([]byte{LeafNodePrefix}, buf...))
-}
diff --git a/pkg/types/crypto_test.go b/pkg/types/crypto_test.go
index 181c8f0..491823a 100644
--- a/pkg/types/crypto_test.go
+++ b/pkg/types/crypto_test.go
@@ -5,6 +5,8 @@ import (
 	"crypto/ed25519"
 	"crypto/rand"
 	"testing"
+
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 func newKeyPair(t *testing.T) (crypto.Signer, PublicKey) {
@@ -18,10 +20,10 @@ func newKeyPair(t *testing.T) (crypto.Signer, PublicKey) {
 	return sk, pub
 }
 
-func newHashBufferInc(t *testing.T) *Hash {
+func newHashBufferInc(t *testing.T) *merkle.Hash {
 	t.Helper()
 
-	var buf Hash
+	var buf merkle.Hash
 	for i := 0; i < len(buf); i++ {
 		buf[i] = byte(i)
 	}
diff --git a/pkg/types/leaf.go b/pkg/types/leaf.go
index 2ba9299..9e8d445 100644
--- a/pkg/types/leaf.go
+++ b/pkg/types/leaf.go
@@ -8,24 +8,25 @@ import (
 	"io"
 
 	"git.sigsum.org/sigsum-go/pkg/ascii"
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 type Statement struct {
 	ShardHint uint64 `ascii:"shard_hint"`
-	Checksum  Hash   `ascii:"checksum"`
+	Checksum  merkle.Hash   `ascii:"checksum"`
 }
 
 type Leaf struct {
 	Statement
 	Signature Signature `ascii:"signature"`
-	KeyHash   Hash      `ascii:"key_hash"`
+	KeyHash   merkle.Hash      `ascii:"key_hash"`
 }
 
 type Leaves []Leaf
 
 func (s *Statement) ToBinary() []byte {
 	namespace := fmt.Sprintf("tree_leaf:v0:%d@sigsum.org", s.ShardHint)
-	b := make([]byte, 6+4+len(namespace)+4+0+4+6+4+HashSize)
+	b := make([]byte, 6+4+len(namespace)+4+0+4+6+4+merkle.HashSize)
 
 	copy(b[0:6], "SSHSIG")
 	i := 6
@@ -84,9 +85,9 @@ func (l *Leaf) FromASCII(r io.Reader) error {
 func (l *Leaves) FromASCII(r io.Reader) error {
 	leaves := &struct {
 		ShardHint []uint64    `ascii:"shard_hint"`
-		Checksum  []Hash      `ascii:"checksum"`
+		Checksum  []merkle.Hash      `ascii:"checksum"`
 		Signature []Signature `ascii:"signature"`
-		KeyHash   []Hash      `ascii:"key_hash"`
+		KeyHash   []merkle.Hash      `ascii:"key_hash"`
 	}{}
 
 	if err := ascii.StdEncoding.Deserialize(r, leaves); err != nil {
diff --git a/pkg/types/leaf_test.go b/pkg/types/leaf_test.go
index 9eae13c..7166fbc 100644
--- a/pkg/types/leaf_test.go
+++ b/pkg/types/leaf_test.go
@@ -10,6 +10,7 @@ import (
 	"testing"
 
 	"git.sigsum.org/sigsum-go/internal/mocks/signer"
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 func TestStatementToBinary(t *testing.T) {
@@ -225,7 +226,7 @@ func TestLeavesFromASCII(t *testing.T) {
 func validStatement(t *testing.T) *Statement {
 	return &Statement{
 		ShardHint: 72623859790382856,
-		Checksum:  *HashFn(newHashBufferInc(t)[:]),
+		Checksum:  *merkle.HashFn(newHashBufferInc(t)[:]),
 	}
 }
 
@@ -235,7 +236,7 @@ func validStatementBytes(t *testing.T) []byte {
 		[]byte{0, 0, 0, 41}, []byte("tree_leaf:v0:72623859790382856@sigsum.org"),
 		[]byte{0, 0, 0, 0},
 		[]byte{0, 0, 0, 6}, []byte("sha256"),
-		[]byte{0, 0, 0, 32}, HashFn(newHashBufferInc(t)[:])[:],
+		[]byte{0, 0, 0, 32}, merkle.HashFn(newHashBufferInc(t)[:])[:],
 	}, nil)
 }
 
@@ -243,7 +244,7 @@ func validLeaf(t *testing.T) *Leaf {
 	return &Leaf{
 		Statement: Statement{
 			ShardHint: 72623859790382856,
-			Checksum:  *HashFn(newHashBufferInc(t)[:]),
+			Checksum:  *merkle.HashFn(newHashBufferInc(t)[:]),
 		},
 		Signature: *newSigBufferInc(t),
 		KeyHash:   *newHashBufferInc(t),
@@ -253,7 +254,7 @@ func validLeaf(t *testing.T) *Leaf {
 func validLeafBytes(t *testing.T) []byte {
 	return bytes.Join([][]byte{
 		[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08},
-		HashFn(newHashBufferInc(t)[:])[:],
+		merkle.HashFn(newHashBufferInc(t)[:])[:],
 		newSigBufferInc(t)[:],
 		newHashBufferInc(t)[:],
 	}, nil)
@@ -262,7 +263,7 @@ func validLeafBytes(t *testing.T) []byte {
 func validLeafASCII(t *testing.T) string {
 	return fmt.Sprintf("%s=%d\n%s=%x\n%s=%x\n%s=%x\n",
 		"shard_hint", 72623859790382856,
-		"checksum", HashFn(newHashBufferInc(t)[:])[:],
+		"checksum", merkle.HashFn(newHashBufferInc(t)[:])[:],
 		"signature", newSigBufferInc(t)[:],
 		"key_hash", newHashBufferInc(t)[:],
 	)
@@ -277,9 +278,9 @@ func validLeavesASCII(t *testing.T) string {
 	t.Helper()
 	return validLeafASCII(t) + fmt.Sprintf("%s=%d\n%s=%x\n%s=%x\n%s=%x\n",
 		"shard_hint", 0,
-		"checksum", Hash{},
+		"checksum", merkle.Hash{},
 		"signature", Signature{},
-		"key_hash", Hash{},
+		"key_hash", merkle.Hash{},
 	)
 }
 
diff --git a/pkg/types/proof.go b/pkg/types/proof.go
index 8c1474e..f2df332 100644
--- a/pkg/types/proof.go
+++ b/pkg/types/proof.go
@@ -4,18 +4,19 @@ import (
 	"io"
 
 	"git.sigsum.org/sigsum-go/pkg/ascii"
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 type InclusionProof struct {
 	TreeSize  uint64
 	LeafIndex uint64 `ascii:"leaf_index"`
-	Path      []Hash `ascii:"inclusion_path"`
+	Path      []merkle.Hash `ascii:"inclusion_path"`
 }
 
 type ConsistencyProof struct {
 	NewSize uint64
 	OldSize uint64
-	Path    []Hash `ascii:"consistency_path"`
+	Path    []merkle.Hash `ascii:"consistency_path"`
 }
 
 func (p *InclusionProof) ToASCII(w io.Writer) error {
@@ -27,8 +28,8 @@ func (p *InclusionProof) FromASCII(r io.Reader, treeSize uint64) error {
 	return ascii.StdEncoding.Deserialize(r, p)
 }
 
-func (p *InclusionProof) Verify(treeSize uint64) bool {
-	return false // TODO: verify inclusion proof
+func (p *InclusionProof) Verify(leaf *merkle.Hash, root *merkle.Hash) error {
+	return merkle.VerifyInclusion(*leaf, p.LeafIndex, p.TreeSize, *root, p.Path)
 }
 
 func (p *ConsistencyProof) ToASCII(w io.Writer) error {
@@ -41,6 +42,6 @@ func (p *ConsistencyProof) FromASCII(r io.Reader, oldSize, newSize uint64) error
 	return ascii.StdEncoding.Deserialize(r, p)
 }
 
-func (p *ConsistencyProof) Verify(newRoot, oldRoot *Hash) bool {
-	return false // TODO: verify consistency proof
+func (p *ConsistencyProof) Verify(oldRoot, newRoot *merkle.Hash) error {
+	return merkle.VerifyConsistency(p.OldSize, p.NewSize, *oldRoot, *newRoot, p.Path)
 }
diff --git a/pkg/types/proof_test.go b/pkg/types/proof_test.go
index 8285b6e..ff3f177 100644
--- a/pkg/types/proof_test.go
+++ b/pkg/types/proof_test.go
@@ -6,6 +6,8 @@ import (
 	"io"
 	"reflect"
 	"testing"
+
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 func TestInclusionProofToASCII(t *testing.T) {
@@ -101,8 +103,8 @@ func validInclusionProof(t *testing.T) *InclusionProof {
 	return &InclusionProof{
 		LeafIndex: 1,
 		TreeSize:  4,
-		Path: []Hash{
-			Hash{},
+		Path: []merkle.Hash{
+			merkle.Hash{},
 			*newHashBufferInc(t),
 		},
 	}
@@ -112,7 +114,7 @@ func validInclusionProofASCII(t *testing.T) string {
 	t.Helper()
 	return fmt.Sprintf("%s=%d\n%s=%x\n%s=%x\n",
 		"leaf_index", 1,
-		"inclusion_path", Hash{},
+		"inclusion_path", merkle.Hash{},
 		"inclusion_path", newHashBufferInc(t)[:],
 	)
 }
@@ -122,8 +124,8 @@ func validConsistencyProof(t *testing.T) *ConsistencyProof {
 	return &ConsistencyProof{
 		NewSize: 1,
 		OldSize: 4,
-		Path: []Hash{
-			Hash{},
+		Path: []merkle.Hash{
+			merkle.Hash{},
 			*newHashBufferInc(t),
 		},
 	}
@@ -132,7 +134,7 @@ func validConsistencyProof(t *testing.T) *ConsistencyProof {
 func validConsistencyProofASCII(t *testing.T) string {
 	t.Helper()
 	return fmt.Sprintf("%s=%x\n%s=%x\n",
-		"consistency_path", Hash{},
+		"consistency_path", merkle.Hash{},
 		"consistency_path", newHashBufferInc(t)[:],
 	)
 }
diff --git a/pkg/types/tree_head.go b/pkg/types/tree_head.go
index de62526..04b3b10 100644
--- a/pkg/types/tree_head.go
+++ b/pkg/types/tree_head.go
@@ -9,12 +9,13 @@ import (
 
 	"git.sigsum.org/sigsum-go/pkg/ascii"
 	"git.sigsum.org/sigsum-go/pkg/hex"
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 type TreeHead struct {
 	Timestamp uint64 `ascii:"timestamp"`
 	TreeSize  uint64 `ascii:"tree_size"`
-	RootHash  Hash   `ascii:"root_hash"`
+	RootHash  merkle.Hash   `ascii:"root_hash"`
 }
 
 type SignedTreeHead struct {
@@ -25,7 +26,7 @@ type SignedTreeHead struct {
 type CosignedTreeHead struct {
 	SignedTreeHead
 	Cosignature []Signature `ascii:"cosignature"`
-	KeyHash     []Hash      `ascii:"key_hash"`
+	KeyHash     []merkle.Hash      `ascii:"key_hash"`
 }
 
 func (th *TreeHead) toBinary() []byte {
@@ -36,21 +37,21 @@ func (th *TreeHead) toBinary() []byte {
 	return b
 }
 
-func (th *TreeHead) ToBinary(keyHash *Hash) []byte {
+func (th *TreeHead) ToBinary(keyHash *merkle.Hash) []byte {
 	namespace := fmt.Sprintf("tree_head:v0:%s@sigsum.org", hex.Serialize(keyHash[:])) // length 88
-	b := make([]byte, 6+4+88+4+0+4+6+4+HashSize)
+	b := make([]byte, 6+4+88+4+0+4+6+4+merkle.HashSize)
 
 	copy(b[0:6], "SSHSIG")
 	i := 6
 	i += putSSHString(b[i:], namespace)
 	i += putSSHString(b[i:], "")
 	i += putSSHString(b[i:], "sha256")
-	i += putSSHString(b[i:], string((*HashFn(th.toBinary()))[:]))
+	i += putSSHString(b[i:], string((*merkle.HashFn(th.toBinary()))[:]))
 
 	return b
 }
 
-func (th *TreeHead) Sign(s crypto.Signer, kh *Hash) (*SignedTreeHead, error) {
+func (th *TreeHead) Sign(s crypto.Signer, kh *merkle.Hash) (*SignedTreeHead, error) {
 	sig, err := s.Sign(nil, th.ToBinary(kh), crypto.Hash(0))
 	if err != nil {
 		return nil, fmt.Errorf("types: failed signing tree head")
@@ -71,7 +72,7 @@ func (sth *SignedTreeHead) FromASCII(r io.Reader) error {
 	return ascii.StdEncoding.Deserialize(r, sth)
 }
 
-func (sth *SignedTreeHead) Verify(key *PublicKey, kh *Hash) bool {
+func (sth *SignedTreeHead) Verify(key *PublicKey, kh *merkle.Hash) bool {
 	return ed25519.Verify(ed25519.PublicKey(key[:]), sth.TreeHead.ToBinary(kh), sth.Signature[:])
 }
 
diff --git a/pkg/types/tree_head_test.go b/pkg/types/tree_head_test.go
index aa57a1c..e2e696c 100644
--- a/pkg/types/tree_head_test.go
+++ b/pkg/types/tree_head_test.go
@@ -10,11 +10,12 @@ import (
 
 	"git.sigsum.org/sigsum-go/internal/mocks/signer"
 	"git.sigsum.org/sigsum-go/pkg/hex"
+	"git.sigsum.org/sigsum-go/pkg/merkle"
 )
 
 func TestTreeHeadToBinary(t *testing.T) {
 	desc := "valid"
-	kh := Hash{}
+	kh := merkle.Hash{}
 	if got, want := validTreeHead(t).ToBinary(&kh), validTreeHeadBytes(t, &kh); !bytes.Equal(got, want) {
 		t.Errorf("got tree head\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
 	}
@@ -42,7 +43,7 @@ func TestTreeHeadSign(t *testing.T) {
 		},
 	} {
 		logKey := PublicKey{}
-		sth, err := table.th.Sign(table.signer, HashFn(logKey[:]))
+		sth, err := table.th.Sign(table.signer, merkle.HashFn(logKey[:]))
 		if got, want := err != nil, table.wantErr; got != want {
 			t.Errorf("got error %v but wanted %v in test %q: %v", got, want, table.desc, err)
 		}
@@ -109,7 +110,7 @@ func TestSignedTreeHeadFromASCII(t *testing.T) {
 func TestSignedTreeHeadVerify(t *testing.T) {
 	th := validTreeHead(t)
 	signer, pub := newKeyPair(t)
-	kh := HashFn(pub[:])
+	kh := merkle.HashFn(pub[:])
 
 	sth, err := th.Sign(signer, kh)
 	if err != nil {
@@ -156,7 +157,7 @@ func TestCosignedTreeHeadFromASCII(t *testing.T) {
 			desc: "invalid: not a cosigned tree head (not enough cosignatures)",
 			serialized: bytes.NewBuffer(append(
 				[]byte(validCosignedTreeHeadASCII(t)),
-				[]byte(fmt.Sprintf("key_hash=%x\n", Hash{}))...,
+				[]byte(fmt.Sprintf("key_hash=%x\n", merkle.Hash{}))...,
 			)),
 			wantErr: true,
 		},
@@ -188,7 +189,7 @@ func validTreeHead(t *testing.T) *TreeHead {
 	}
 }
 
-func validTreeHeadBytes(t *testing.T, keyHash *Hash) []byte {
+func validTreeHeadBytes(t *testing.T, keyHash *merkle.Hash) []byte {
 	ns := fmt.Sprintf("tree_head:v0:%s@sigsum.org", hex.Serialize(keyHash[:]))
 	th := bytes.Join([][]byte{
 		[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08},
@@ -200,7 +201,7 @@ func validTreeHeadBytes(t *testing.T, keyHash *Hash) []byte {
 		[]byte{0, 0, 0, 88}, []byte(ns),
 		[]byte{0, 0, 0, 0},
 		[]byte{0, 0, 0, 6}, []byte("sha256"),
-		[]byte{0, 0, 0, 32}, (*HashFn(th))[:],
+		[]byte{0, 0, 0, 32}, (*merkle.HashFn(th))[:],
 	}, nil)
 }
 
@@ -241,8 +242,8 @@ func validCosignedTreeHead(t *testing.T) *CosignedTreeHead {
 			Signature{},
 			*newSigBufferInc(t),
 		},
-		KeyHash: []Hash{
-			Hash{},
+		KeyHash: []merkle.Hash{
+			merkle.Hash{},
 			*newHashBufferInc(t),
 		},
 	}
@@ -257,7 +258,7 @@ func validCosignedTreeHeadASCII(t *testing.T) string {
 		"signature", newSigBufferInc(t)[:],
 		"cosignature", Signature{},
 		"cosignature", newSigBufferInc(t)[:],
-		"key_hash", Hash{},
+		"key_hash", merkle.Hash{},
 		"key_hash", newHashBufferInc(t)[:],
 	)
 }