types: Add types and tests

9 files changed, 1039 insertions, 0 deletions

diff --git a/pkg/types/crypto.go b/pkg/types/crypto.go
new file mode 100644
index 0000000..72152bf
--- /dev/null
+++ b/pkg/types/crypto.go
@@ -0,0 +1,30 @@
+package types
+
+import (
+	"crypto/ed25519"
+	"crypto/sha256"
+)
+
+const (
+	HashSize      = sha256.Size
+	SignatureSize = ed25519.SignatureSize
+	PublicKeySize = ed25519.PublicKeySize
+
+	InteriorNodePrefix = byte(0x00)
+	LeafNodePrefix     = 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
new file mode 100644
index 0000000..d95d5fa
--- /dev/null
+++ b/pkg/types/crypto_test.go
@@ -0,0 +1,64 @@
+package types
+
+import (
+	"crypto"
+	"crypto/ed25519"
+	"crypto/rand"
+	"io"
+	"testing"
+)
+
+type testSigner struct {
+	PublicKey PublicKey
+	Signature Signature
+	Error     error
+}
+
+func (ts *testSigner) Public() crypto.PublicKey {
+	return ed25519.PublicKey(ts.PublicKey[:])
+}
+
+func (ts *testSigner) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
+	return ts.Signature[:], ts.Error
+}
+
+func newKeyPair(t *testing.T) (crypto.Signer, PublicKey) {
+	vk, sk, err := ed25519.GenerateKey(rand.Reader)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	var pub PublicKey
+	copy(pub[:], vk[:])
+	return sk, pub
+}
+
+func newHashBufferInc(t *testing.T) *Hash {
+	t.Helper()
+
+	var buf Hash
+	for i := 0; i < len(buf); i++ {
+		buf[i] = byte(i)
+	}
+	return &buf
+}
+
+func newSigBufferInc(t *testing.T) *Signature {
+	t.Helper()
+
+	var buf Signature
+	for i := 0; i < len(buf); i++ {
+		buf[i] = byte(i)
+	}
+	return &buf
+}
+
+func newPubBufferInc(t *testing.T) *PublicKey {
+	t.Helper()
+
+	var buf PublicKey
+	for i := 0; i < len(buf); i++ {
+		buf[i] = byte(i)
+	}
+	return &buf
+}
diff --git a/pkg/types/endpoint.go b/pkg/types/endpoint.go
new file mode 100644
index 0000000..0e4bab2
--- /dev/null
+++ b/pkg/types/endpoint.go
@@ -0,0 +1,22 @@
+package types
+
+import "strings"
+
+type Endpoint string
+
+const (
+	EndpointAddLeaf             = Endpoint("add-leaf")
+	EndpointAddCosignature      = Endpoint("add-cosignature")
+	EndpointGetTreeHeadLatest   = Endpoint("get-tree-head-latest")
+	EndpointGetTreeHeadToSign   = Endpoint("get-tree-head-to-sign")
+	EndpointGetTreeHeadCosigned = Endpoint("get-tree-head-cosigned")
+	EndpointGetInclusionProof   = Endpoint("get-inclusion-proof")
+	EndpointGetConsistencyProof = Endpoint("get-consistency-proof")
+	EndpointGetLeaves           = Endpoint("get-leaves")
+)
+
+// Path joins a number of components to form a full endpoint path.  For example,
+// EndpointAddLeaf.Path("example.com", "sigsum/v0") -> example.com/sigsum/v0/add-leaf.
+func (e Endpoint) Path(components ...string) string {
+	return strings.Join(append(components, string(e)), "/")
+}
diff --git a/pkg/types/leaf.go b/pkg/types/leaf.go
new file mode 100644
index 0000000..1476ead
--- /dev/null
+++ b/pkg/types/leaf.go
@@ -0,0 +1,111 @@
+package types
+
+import (
+	"crypto"
+	"crypto/ed25519"
+	"encoding/binary"
+	"fmt"
+	"io"
+
+	"git.sigsum.org/sigsum-lib-go/pkg/ascii"
+)
+
+type Statement struct {
+	ShardHint uint64 `ascii:"shard_hint"`
+	Checksum  Hash   `ascii:"checksum"`
+}
+
+type Leaf struct {
+	Statement
+	Signature Signature `ascii:"signature"`
+	KeyHash   Hash      `ascii:"key_hash"`
+}
+
+type Leaves []Leaf
+
+func (s *Statement) ToBinary() []byte {
+	b := make([]byte, 40)
+	binary.BigEndian.PutUint64(b[0:8], s.ShardHint)
+	copy(b[8:40], s.Checksum[:])
+	return b
+}
+
+func (s *Statement) Sign(signer crypto.Signer) (*Signature, error) {
+	sig, err := signer.Sign(nil, s.ToBinary(), crypto.Hash(0))
+	if err != nil {
+		return nil, fmt.Errorf("types: failed signing statement")
+	}
+
+	var signature Signature
+	copy(signature[:], sig)
+	return &signature, nil
+}
+
+func (s *Statement) Verify(key *PublicKey, sig *Signature) bool {
+	return ed25519.Verify(ed25519.PublicKey(key[:]), s.ToBinary(), sig[:])
+}
+
+func (l *Leaf) ToBinary() []byte {
+	b := make([]byte, 136)
+	binary.BigEndian.PutUint64(b[0:8], l.ShardHint)
+	copy(b[8:40], l.Checksum[:])
+	copy(b[40:104], l.Signature[:])
+	copy(b[104:136], l.KeyHash[:])
+	return b
+}
+
+func (l *Leaf) FromBinary(b []byte) error {
+	if len(b) != 136 {
+		return fmt.Errorf("types: invalid leaf size: %d", len(b))
+	}
+
+	l.ShardHint = binary.BigEndian.Uint64(b[0:8])
+	copy(l.Checksum[:], b[8:40])
+	copy(l.Signature[:], b[40:104])
+	copy(l.KeyHash[:], b[104:136])
+	return nil
+}
+
+func (l *Leaf) ToASCII(w io.Writer) error {
+	return ascii.StdEncoding.Serialize(w, l)
+}
+
+func (l *Leaf) FromASCII(r io.Reader) error {
+	return ascii.StdEncoding.Deserialize(r, l)
+}
+
+func (l *Leaves) FromASCII(r io.Reader) error {
+	leaves := &struct {
+		ShardHint []uint64    `ascii:"shard_hint"`
+		Checksum  []Hash      `ascii:"checksum"`
+		Signature []Signature `ascii:"signature"`
+		KeyHash   []Hash      `ascii:"key_hash"`
+	}{}
+
+	if err := ascii.StdEncoding.Deserialize(r, leaves); err != nil {
+		return err
+	}
+	n := len(leaves.ShardHint)
+	if n != len(leaves.Checksum) {
+		return fmt.Errorf("types: mismatched leaf field counts")
+	}
+	if n != len(leaves.Signature) {
+		return fmt.Errorf("types: mismatched leaf field counts")
+	}
+	if n != len(leaves.KeyHash) {
+		return fmt.Errorf("types: mismatched leaf field counts")
+	}
+
+	*l = make([]Leaf, 0, n)
+	for i := 0; i < n; i++ {
+		*l = append(*l, Leaf{
+			Statement: Statement{
+				ShardHint: leaves.ShardHint[i],
+				Checksum:  leaves.Checksum[i],
+			},
+			Signature: leaves.Signature[i],
+			KeyHash:   leaves.KeyHash[i],
+		})
+	}
+	return nil
+}
diff --git a/pkg/types/leaf_test.go b/pkg/types/leaf_test.go
new file mode 100644
index 0000000..0ae6431
--- /dev/null
+++ b/pkg/types/leaf_test.go
@@ -0,0 +1,299 @@
+package types
+
+import (
+	"bytes"
+	"crypto"
+	"fmt"
+	"io"
+	"reflect"
+	"strings"
+	"testing"
+)
+
+func TestStatementToBinary(t *testing.T) {
+	desc := "valid: shard hint 72623859790382856, checksum 0x00,0x01,..."
+	if got, want := validStatement(t).ToBinary(), validStatementBytes(t); !bytes.Equal(got, want) {
+		t.Errorf("got statement\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestStatementSign(t *testing.T) {
+	for _, table := range []struct {
+		desc    string
+		stm     *Statement
+		signer  crypto.Signer
+		wantSig *Signature
+		wantErr bool
+	}{
+		{
+			desc:    "invalid: signer error",
+			stm:     validStatement(t),
+			signer:  &testSigner{*newPubBufferInc(t), *newSigBufferInc(t), fmt.Errorf("signing error")},
+			wantErr: true,
+		},
+		{
+			desc:    "valid",
+			stm:     validStatement(t),
+			signer:  &testSigner{*newPubBufferInc(t), *newSigBufferInc(t), nil},
+			wantSig: newSigBufferInc(t),
+		},
+	} {
+		sig, err := table.stm.Sign(table.signer)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+
+		if got, want := sig[:], table.wantSig[:]; !bytes.Equal(got, want) {
+			t.Errorf("got signature\n\t%v\nbut wanted\n\t%v\nin test %q", got, want, table.desc)
+		}
+	}
+}
+
+func TestStatementVerify(t *testing.T) {
+	stm := validStatement(t)
+	signer, pub := newKeyPair(t)
+
+	sig, err := stm.Sign(signer)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if !stm.Verify(&pub, sig) {
+		t.Errorf("failed verifying a valid statement")
+	}
+
+	stm.ShardHint += 1
+	if stm.Verify(&pub, sig) {
+		t.Errorf("succeeded verifying an invalid statement")
+	}
+}
+
+func TestLeafToBinary(t *testing.T) {
+	desc := "valid: shard hint 72623859790382856, buffers 0x00,0x01,..."
+	if got, want := validLeaf(t).ToBinary(), validLeafBytes(t); !bytes.Equal(got, want) {
+		t.Errorf("got leaf\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestLeafFromBinary(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized []byte
+		wantErr    bool
+		want       *Leaf
+	}{
+		{
+			desc:       "invalid: not enough bytes",
+			serialized: make([]byte, 135),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: too many bytes",
+			serialized: make([]byte, 137),
+			wantErr:    true,
+		},
+		{
+			desc:       "valid: shard hint 72623859790382856, buffers 0x00,0x01,...",
+			serialized: validLeafBytes(t),
+			want:       validLeaf(t),
+		},
+	} {
+		var leaf Leaf
+		err := leaf.FromBinary(table.serialized)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &leaf, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got leaf\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func TestLeafToASCII(t *testing.T) {
+	desc := "valid: shard hint 72623859790382856, buffers 0x00,0x01,..."
+	buf := bytes.NewBuffer(nil)
+	if err := validLeaf(t).ToASCII(buf); err != nil {
+		t.Fatalf("got error true but wanted false in test %q: %v", desc, err)
+	}
+	if got, want := string(buf.Bytes()), validLeafASCII(t); got != want {
+		t.Errorf("got leaf\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestLeafFromASCII(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized io.Reader
+		wantErr    bool
+		want       *Leaf
+	}{
+		{
+			desc:       "invalid: not a tree leaf (too few key-value pairs)",
+			serialized: bytes.NewBuffer([]byte("shard_hint=0\n")),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: not a tree leaf (too many key-value pairs)",
+			serialized: bytes.NewBuffer(append(validLeafBytes(t)[:], []byte("key=value\n")...)),
+			wantErr:    true,
+		},
+		{
+			desc:       "valid: shard hint 72623859790382856, buffers 0x00,0x01,...",
+			serialized: bytes.NewBuffer([]byte(validLeafASCII(t))),
+			want:       validLeaf(t),
+		},
+	} {
+		var leaf Leaf
+		err := leaf.FromASCII(table.serialized)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &leaf, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got leaf\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func TestLeavesFromASCII(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized io.Reader
+		wantErr    bool
+		want       *Leaves
+	}{
+		{
+			desc:       "invalid: not a list of tree leaves (too few key-value pairs)",
+			serialized: bytes.NewBuffer([]byte("shard_hint=0\n")),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: not a list of tree leaves (too many key-value pairs)",
+			serialized: bytes.NewBuffer(append(validLeafBytes(t)[:], []byte("key=value\n")...)),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: not a list of tree leaves (too few shard hints))",
+			serialized: bytes.NewBuffer([]byte(invalidLeavesASCII(t, "shard_hint"))),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: not a list of tree leaves (too few checksums))",
+			serialized: bytes.NewBuffer([]byte(invalidLeavesASCII(t, "checksum"))),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: not a list of tree leaves (too few signatures))",
+			serialized: bytes.NewBuffer([]byte(invalidLeavesASCII(t, "signature"))),
+			wantErr:    true,
+		},
+		{
+			desc:       "invalid: not a list of tree leaves (too few key hashes))",
+			serialized: bytes.NewBuffer([]byte(invalidLeavesASCII(t, "key_hash"))),
+			wantErr:    true,
+		},
+		{
+			desc:       "valid leaves",
+			serialized: bytes.NewBuffer([]byte(validLeavesASCII(t))),
+			want:       validLeaves(t),
+		},
+	} {
+		var leaves Leaves
+		err := leaves.FromASCII(table.serialized)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &leaves, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got leaves\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func validStatement(t *testing.T) *Statement {
+	return &Statement{
+		ShardHint: 72623859790382856,
+		Checksum:  *newHashBufferInc(t),
+	}
+}
+
+func validStatementBytes(t *testing.T) []byte {
+	return bytes.Join([][]byte{
+		[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08},
+		newHashBufferInc(t)[:],
+	}, nil)
+}
+
+func validLeaf(t *testing.T) *Leaf {
+	return &Leaf{
+		Statement: Statement{
+			ShardHint: 72623859790382856,
+			Checksum:  *newHashBufferInc(t),
+		},
+		Signature: *newSigBufferInc(t),
+		KeyHash:   *newHashBufferInc(t),
+	}
+}
+
+func validLeafBytes(t *testing.T) []byte {
+	return bytes.Join([][]byte{
+		[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08},
+		newHashBufferInc(t)[:],
+		newSigBufferInc(t)[:],
+		newHashBufferInc(t)[:],
+	}, nil)
+}
+
+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", newHashBufferInc(t)[:],
+		"signature", newSigBufferInc(t)[:],
+		"key_hash", newHashBufferInc(t)[:],
+	)
+}
+
+func validLeaves(t *testing.T) *Leaves {
+	t.Helper()
+	return &Leaves{*validLeaf(t), Leaf{}}
+}
+
+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{},
+		"signature", Signature{},
+		"key_hash", Hash{},
+	)
+}
+
+func invalidLeavesASCII(t *testing.T, key string) string {
+	buf := validLeavesASCII(t)
+	lines := strings.Split(buf, "\n")
+
+	var ret string
+	switch key {
+	case "shard_hint":
+		ret = strings.Join(lines[1:], "\n")
+	case "checksum":
+		ret = strings.Join(append(lines[:1], lines[2:]...), "\n")
+	case "signature":
+		ret = strings.Join(append(lines[0:2], lines[3:]...), "\n")
+	case "key_hash":
+		ret = strings.Join(append(lines[0:3], lines[4:]...), "\n")
+	default:
+		t.Fatalf("must have a valid key to remove")
+	}
+	return ret
+}
diff --git a/pkg/types/proof.go b/pkg/types/proof.go
new file mode 100644
index 0000000..4311357
--- /dev/null
+++ b/pkg/types/proof.go
@@ -0,0 +1,46 @@
+package types
+
+import (
+	"io"
+
+	"git.sigsum.org/sigsum-lib-go/pkg/ascii"
+)
+
+type InclusionProof struct {
+	TreeSize  uint64
+	LeafIndex uint64 `ascii:"leaf_index"`
+	Path      []Hash `ascii:"inclusion_path"`
+}
+
+type ConsistencyProof struct {
+	NewSize uint64
+	OldSize uint64
+	Path    []Hash `ascii:"consistency_path"`
+}
+
+func (p *InclusionProof) ToASCII(w io.Writer) error {
+	return ascii.StdEncoding.Serialize(w, p)
+}
+
+func (p *InclusionProof) FromASCII(r io.Reader, treeSize uint64) error {
+	p.TreeSize = treeSize
+	return ascii.StdEncoding.Deserialize(r, p)
+}
+
+func (p *InclusionProof) Verify(treeSize uint64) bool {
+	return false // TODO: verify inclusion proof
+}
+
+func (p *ConsistencyProof) ToASCII(w io.Writer) error {
+	return ascii.StdEncoding.Serialize(w, p)
+}
+
+func (p *ConsistencyProof) FromASCII(r io.Reader, oldSize, newSize uint64) error {
+	p.OldSize = oldSize
+	p.NewSize = newSize
+	return ascii.StdEncoding.Deserialize(r, p)
+}
+
+func (p *ConsistencyProof) Verify(newRoot, oldRoot *Hash) bool {
+	return false // TODO: verify consistency proof
+}
diff --git a/pkg/types/proof_test.go b/pkg/types/proof_test.go
new file mode 100644
index 0000000..8285b6e
--- /dev/null
+++ b/pkg/types/proof_test.go
@@ -0,0 +1,138 @@
+package types
+
+import (
+	"bytes"
+	"fmt"
+	"io"
+	"reflect"
+	"testing"
+)
+
+func TestInclusionProofToASCII(t *testing.T) {
+	desc := "valid"
+	buf := bytes.NewBuffer(nil)
+	if err := validInclusionProof(t).ToASCII(buf); err != nil {
+		t.Fatalf("got error true but wanted false in test %q: %v", desc, err)
+	}
+	if got, want := string(buf.Bytes()), validInclusionProofASCII(t); got != want {
+		t.Errorf("got inclusion proof\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestInclusionProofFromASCII(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized io.Reader
+		wantErr    bool
+		want       *InclusionProof
+	}{
+		{
+			desc:       "invalid: not an inclusion proof (unexpected key-value pair)",
+			serialized: bytes.NewBuffer(append([]byte(validInclusionProofASCII(t)), []byte("tree_size=4")...)),
+			wantErr:    true,
+			want:       validInclusionProof(t), // to populate input to FromASCII
+		},
+		{
+			desc:       "valid",
+			serialized: bytes.NewBuffer([]byte(validInclusionProofASCII(t))),
+			want:       validInclusionProof(t),
+		},
+	} {
+		var proof InclusionProof
+		err := proof.FromASCII(table.serialized, table.want.TreeSize)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &proof, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got inclusion proof\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func TestConsistencyProofToASCII(t *testing.T) {
+	desc := "valid"
+	buf := bytes.NewBuffer(nil)
+	if err := validConsistencyProof(t).ToASCII(buf); err != nil {
+		t.Fatalf("got error true but wanted false in test %q: %v", desc, err)
+	}
+	if got, want := string(buf.Bytes()), validConsistencyProofASCII(t); got != want {
+		t.Errorf("got consistency proof\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestConsistencyProofFromASCII(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized io.Reader
+		wantErr    bool
+		want       *ConsistencyProof
+	}{
+		{
+			desc:       "invalid: not a consistency proof (unexpected key-value pair)",
+			serialized: bytes.NewBuffer(append([]byte(validConsistencyProofASCII(t)), []byte("start_size=1")...)),
+			wantErr:    true,
+			want:       validConsistencyProof(t), // to populate input to FromASCII
+		},
+		{
+			desc:       "valid",
+			serialized: bytes.NewBuffer([]byte(validConsistencyProofASCII(t))),
+			want:       validConsistencyProof(t),
+		},
+	} {
+		var proof ConsistencyProof
+		err := proof.FromASCII(table.serialized, table.want.OldSize, table.want.NewSize)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &proof, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got consistency proof\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func validInclusionProof(t *testing.T) *InclusionProof {
+	t.Helper()
+	return &InclusionProof{
+		LeafIndex: 1,
+		TreeSize:  4,
+		Path: []Hash{
+			Hash{},
+			*newHashBufferInc(t),
+		},
+	}
+}
+
+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", newHashBufferInc(t)[:],
+	)
+}
+
+func validConsistencyProof(t *testing.T) *ConsistencyProof {
+	t.Helper()
+	return &ConsistencyProof{
+		NewSize: 1,
+		OldSize: 4,
+		Path: []Hash{
+			Hash{},
+			*newHashBufferInc(t),
+		},
+	}
+}
+
+func validConsistencyProofASCII(t *testing.T) string {
+	t.Helper()
+	return fmt.Sprintf("%s=%x\n%s=%x\n",
+		"consistency_path", Hash{},
+		"consistency_path", newHashBufferInc(t)[:],
+	)
+}
diff --git a/pkg/types/tree_head.go b/pkg/types/tree_head.go
new file mode 100644
index 0000000..0f1efee
--- /dev/null
+++ b/pkg/types/tree_head.go
@@ -0,0 +1,76 @@
+package types
+
+import (
+	"crypto"
+	"crypto/ed25519"
+	"encoding/binary"
+	"fmt"
+	"io"
+
+	"git.sigsum.org/sigsum-lib-go/pkg/ascii"
+)
+
+type TreeHead struct {
+	Timestamp uint64 `ascii:"timestamp"`
+	TreeSize  uint64 `ascii:"tree_size"`
+	RootHash  Hash   `ascii:"root_hash"`
+}
+
+type SignedTreeHead struct {
+	TreeHead
+	Signature Signature `ascii:"signature"`
+}
+
+type CosignedTreeHead struct {
+	SignedTreeHead
+	Cosignature []Signature `ascii:"cosignature"`
+	KeyHash     []Hash      `ascii:"key_hash"`
+}
+
+func (th *TreeHead) ToBinary(keyHash *Hash) []byte {
+	b := make([]byte, 80)
+	binary.BigEndian.PutUint64(b[0:8], th.Timestamp)
+	binary.BigEndian.PutUint64(b[8:16], th.TreeSize)
+	copy(b[16:48], th.RootHash[:])
+	copy(b[48:80], keyHash[:])
+	return b
+}
+
+func (th *TreeHead) Sign(s crypto.Signer, ctx *Hash) (*SignedTreeHead, error) {
+	sig, err := s.Sign(nil, th.ToBinary(ctx), crypto.Hash(0))
+	if err != nil {
+		return nil, fmt.Errorf("types: failed signing tree head")
+	}
+
+	sth := &SignedTreeHead{
+		TreeHead: *th,
+	}
+	copy(sth.Signature[:], sig)
+	return sth, nil
+}
+
+func (sth *SignedTreeHead) ToASCII(w io.Writer) error {
+	return ascii.StdEncoding.Serialize(w, sth)
+}
+
+func (sth *SignedTreeHead) FromASCII(r io.Reader) error {
+	return ascii.StdEncoding.Deserialize(r, sth)
+}
+
+func (sth *SignedTreeHead) Verify(key *PublicKey, ctx *Hash) bool {
+	return ed25519.Verify(ed25519.PublicKey(key[:]), sth.TreeHead.ToBinary(ctx), sth.Signature[:])
+}
+
+func (cth *CosignedTreeHead) ToASCII(w io.Writer) error {
+	return ascii.StdEncoding.Serialize(w, cth)
+}
+
+func (cth *CosignedTreeHead) FromASCII(r io.Reader) error {
+	if err := ascii.StdEncoding.Deserialize(r, cth); err != nil {
+		return err
+	}
+	if len(cth.Cosignature) != len(cth.KeyHash) {
+		return fmt.Errorf("types: mismatched cosignature count")
+	}
+	return nil
+}
diff --git a/pkg/types/tree_head_test.go b/pkg/types/tree_head_test.go
new file mode 100644
index 0000000..03a52f5
--- /dev/null
+++ b/pkg/types/tree_head_test.go
@@ -0,0 +1,253 @@
+package types
+
+import (
+	"bytes"
+	"crypto"
+	"fmt"
+	"io"
+	"reflect"
+	"testing"
+)
+
+func TestTreeHeadToBinary(t *testing.T) {
+	desc := "valid"
+	kh := 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)
+	}
+}
+
+func TestTreeHeadSign(t *testing.T) {
+	for _, table := range []struct {
+		desc    string
+		th      *TreeHead
+		signer  crypto.Signer
+		wantSig *Signature
+		wantErr bool
+	}{
+		{
+			desc:    "invalid: signer error",
+			th:      validTreeHead(t),
+			signer:  &testSigner{*newPubBufferInc(t), *newSigBufferInc(t), fmt.Errorf("signing error")},
+			wantErr: true,
+		},
+		{
+			desc:    "valid",
+			th:      validTreeHead(t),
+			signer:  &testSigner{*newPubBufferInc(t), *newSigBufferInc(t), nil},
+			wantSig: newSigBufferInc(t),
+		},
+	} {
+		logKey := PublicKey{}
+		sth, err := table.th.Sign(table.signer, 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)
+		}
+		if err != nil {
+			continue
+		}
+
+		wantSTH := &SignedTreeHead{
+			TreeHead:  *table.th,
+			Signature: *table.wantSig,
+		}
+		if got, want := sth, wantSTH; !reflect.DeepEqual(got, want) {
+			t.Errorf("got sth\n\t%v\nbut wanted\n\t%v\nin test %q", got, want, table.desc)
+		}
+	}
+}
+
+func TestSignedTreeHeadToASCII(t *testing.T) {
+	desc := "valid"
+	buf := bytes.NewBuffer(nil)
+	if err := validSignedTreeHead(t).ToASCII(buf); err != nil {
+		t.Fatalf("got error true but wanted false in test %q: %v", desc, err)
+	}
+	if got, want := string(buf.Bytes()), validSignedTreeHeadASCII(t); got != want {
+		t.Errorf("got signed tree head\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestSignedTreeHeadFromASCII(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized io.Reader
+		wantErr    bool
+		want       *SignedTreeHead
+	}{
+		{
+			desc: "invalid: not a signed tree head (unexpected key-value pair)",
+			serialized: bytes.NewBuffer(append(
+				[]byte(validSignedTreeHeadASCII(t)),
+				[]byte("key=4")...),
+			),
+			wantErr: true,
+		},
+		{
+			desc:       "valid",
+			serialized: bytes.NewBuffer([]byte(validSignedTreeHeadASCII(t))),
+			want:       validSignedTreeHead(t),
+		},
+	} {
+		var sth SignedTreeHead
+		err := sth.FromASCII(table.serialized)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &sth, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got signed tree head\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func TestSignedTreeHeadVerify(t *testing.T) {
+	th := validTreeHead(t)
+	signer, pub := newKeyPair(t)
+	ctx := HashFn(pub[:])
+
+	sth, err := th.Sign(signer, ctx)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	if !sth.Verify(&pub, ctx) {
+		t.Errorf("failed verifying a valid signed tree head")
+	}
+
+	sth.TreeSize += 1
+	if sth.Verify(&pub, ctx) {
+		t.Errorf("succeeded verifying an invalid signed tree head")
+	}
+}
+
+func TestCosignedTreeHeadToASCII(t *testing.T) {
+	desc := "valid"
+	buf := bytes.NewBuffer(nil)
+	if err := validCosignedTreeHead(t).ToASCII(buf); err != nil {
+		t.Fatalf("got error true but wanted false in test %q: %v", desc, err)
+	}
+	if got, want := string(buf.Bytes()), validCosignedTreeHeadASCII(t); got != want {
+		t.Errorf("got cosigned tree head\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, desc)
+	}
+}
+
+func TestCosignedTreeHeadFromASCII(t *testing.T) {
+	for _, table := range []struct {
+		desc       string
+		serialized io.Reader
+		wantErr    bool
+		want       *CosignedTreeHead
+	}{
+		{
+			desc: "invalid: not a cosigned tree head (unexpected key-value pair)",
+			serialized: bytes.NewBuffer(append(
+				[]byte(validCosignedTreeHeadASCII(t)),
+				[]byte("key=4")...),
+			),
+			wantErr: true,
+		},
+		{
+			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{}))...,
+			)),
+			wantErr: true,
+		},
+		{
+			desc:       "valid",
+			serialized: bytes.NewBuffer([]byte(validCosignedTreeHeadASCII(t))),
+			want:       validCosignedTreeHead(t),
+		},
+	} {
+		var cth CosignedTreeHead
+		err := cth.FromASCII(table.serialized)
+		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)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := &cth, table.want; !reflect.DeepEqual(got, want) {
+			t.Errorf("got cosigned tree head\n\t%v\nbut wanted\n\t%v\nin test %q\n", got, want, table.desc)
+		}
+	}
+}
+
+func validTreeHead(t *testing.T) *TreeHead {
+	return &TreeHead{
+		Timestamp: 72623859790382856,
+		TreeSize:  257,
+		RootHash:  *newHashBufferInc(t),
+	}
+}
+
+func validTreeHeadBytes(t *testing.T, keyHash *Hash) []byte {
+	return bytes.Join([][]byte{
+		[]byte{0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08},
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x01},
+		newHashBufferInc(t)[:],
+		keyHash[:],
+	}, nil)
+}
+
+func validSignedTreeHead(t *testing.T) *SignedTreeHead {
+	t.Helper()
+	return &SignedTreeHead{
+		TreeHead: TreeHead{
+			Timestamp: 1,
+			TreeSize:  2,
+			RootHash:  *newHashBufferInc(t),
+		},
+		Signature: *newSigBufferInc(t),
+	}
+}
+
+func validSignedTreeHeadASCII(t *testing.T) string {
+	t.Helper()
+	return fmt.Sprintf("%s=%d\n%s=%d\n%s=%x\n%s=%x\n",
+		"timestamp", 1,
+		"tree_size", 2,
+		"root_hash", newHashBufferInc(t)[:],
+		"signature", newSigBufferInc(t)[:],
+	)
+}
+
+func validCosignedTreeHead(t *testing.T) *CosignedTreeHead {
+	t.Helper()
+	return &CosignedTreeHead{
+		SignedTreeHead: SignedTreeHead{
+			TreeHead: TreeHead{
+				Timestamp: 1,
+				TreeSize:  2,
+				RootHash:  *newHashBufferInc(t),
+			},
+			Signature: *newSigBufferInc(t),
+		},
+		Cosignature: []Signature{
+			Signature{},
+			*newSigBufferInc(t),
+		},
+		KeyHash: []Hash{
+			Hash{},
+			*newHashBufferInc(t),
+		},
+	}
+}
+
+func validCosignedTreeHeadASCII(t *testing.T) string {
+	t.Helper()
+	return fmt.Sprintf("%s=%d\n%s=%d\n%s=%x\n%s=%x\n%s=%x\n%s=%x\n%s=%x\n%s=%x\n",
+		"timestamp", 1,
+		"tree_size", 2,
+		"root_hash", newHashBufferInc(t)[:],
+		"signature", newSigBufferInc(t)[:],
+		"cosignature", Signature{},
+		"cosignature", newSigBufferInc(t)[:],
+		"key_hash", Hash{},
+		"key_hash", newHashBufferInc(t)[:],
+	)
+}