added refactored types

5 files changed, 1207 insertions, 5 deletions

diff --git a/README.md b/README.md
index 66a9d43..24986ad 100644
--- a/README.md
+++ b/README.md
@@ -145,7 +145,7 @@ opaque NodeHash<32..2^8-1>;
 
 struct {
 	Namespace namespace;
-	opaque signature<0..2^16-1>;
+	opaque signature<1..2^16-1>;
 } SignatureV1;
 ```
 
@@ -174,7 +174,7 @@ namespace of type `ed25519_v1`.
 
 ```
 struct {
-	SignedTreeHeadV1 sth;
+	SignedTreeHeadV1 signed_tree_head;
 	SignatureV1 cosignatures<0..2^32-1>; // vector of cosignatures
 } CosignedTreeHeadV1;
 ```
@@ -189,7 +189,7 @@ and a consistency proof may be empty.
 
 ```
 struct {
-	Namespace namespace; // log identifier
+	Namespace log_id;
 	uint64 tree_size_1;
 	uint64 tree_size_2;
 	NodeHash consistency_path<0..2^16-1>;
@@ -205,7 +205,7 @@ There are two modifications: our log identifier is a namespace rather than an
 and an inclusion proof may be empty.
 ```
 struct {
-	Namespace namespace; // log identifier
+	Namespace log_id;
 	uint64 tree_size;
 	uint64 leaf_index;
 	NodeHash inclusion_path<0..2^16-1>;
@@ -222,7 +222,7 @@ update](https://wiki.mozilla.org/Security/Binary_Transparency).
 
 ```
 struct {
-	ChecksumDataV1 data;
+	ChecksumV1 data;
 	SignatureV1 signature;
 } SignedChecksumV1;
 
diff --git a/types/item.go b/types/item.go
new file mode 100644
index 0000000..5e8836e
--- /dev/null
+++ b/types/item.go
@@ -0,0 +1,140 @@
+package types
+
+import (
+	"fmt"
+
+	"github.com/google/certificate-transparency-go/tls"
+)
+
+// StFormat defines a particular StItem type that is versioned
+type StFormat tls.Enum
+
+const (
+	StFormatReserved           StFormat = 0
+	StFormatSignedTreeHeadV1   StFormat = 1
+	StFormatCosignedTreeHeadV1 StFormat = 2
+	StFormatConsistencyProofV1 StFormat = 3
+	StFormatInclusionProofV1   StFormat = 4
+	StFormatSignedChecksumV1   StFormat = 5
+)
+
+// StItem references a versioned item based on a given format specifier
+type StItem struct {
+	Format             StFormat            `tls:"maxval:65535"`
+	SignedTreeHeadV1   *SignedTreeHeadV1   `tls:"selector:Format,val:1"`
+	CosignedTreeHeadV1 *CosignedTreeHeadV1 `tls:"selector:Format,val:2"`
+	ConsistencyProofV1 *ConsistencyProofV1 `tls:"selector:Format,val:3"`
+	InclusionProofV1   *InclusionProofV1   `tls:"selector:Format,val:4"`
+	SignedChecksumV1   *SignedChecksumV1   `tls:"selector:Format,val:5"`
+}
+
+// TODO: StItemList
+
+type SignedTreeHeadV1 struct {
+	TreeHead  TreeHeadV1
+	Signature SignatureV1
+}
+
+type CosignedTreeHeadV1 struct {
+	SignedTreeHead SignedTreeHeadV1
+	Cosignatures   []SignatureV1 `tls:"minlen:0,maxlen:4294967295"`
+}
+
+type ConsistencyProofV1 struct {
+	LogId           Namespace
+	TreeSize1       uint64
+	TreeSize2       uint64
+	ConsistencyPath []NodeHash `tls:"minlen:0,maxlen:65535"`
+}
+
+type InclusionProofV1 struct {
+	LogId         Namespace
+	TreeSize      uint64
+	LeafIndex     uint64
+	InclusionPath []NodeHash `tls:"minlen:0,maxlen:65535"`
+}
+
+type SignedChecksumV1 struct {
+	Data      ChecksumV1
+	Signature SignatureV1
+}
+
+type ChecksumV1 struct {
+	Identifier []byte `tls:"minlen:1,maxlen:128"`
+	Checksum   []byte `tls:"minlen:1,maxlen:64"`
+}
+
+type TreeHeadV1 struct {
+	Timestamp uint64
+	TreeSize  uint64
+	RootHash  NodeHash
+	Extension []byte `tls:"minlen:0,maxlen:65535"`
+}
+
+type NodeHash struct {
+	Data []byte `tls:"minlen:32,maxlen:255"`
+}
+
+type SignatureV1 struct {
+	Namespace Namespace
+	Signature []byte `tls:"minlen:1,maxlen:65535"`
+}
+
+func (f StFormat) String() string {
+	switch f {
+	case StFormatReserved:
+		return "reserved"
+	case StFormatSignedTreeHeadV1:
+		return "signed_tree_head_v1"
+	case StFormatCosignedTreeHeadV1:
+		return "cosigned_tree_head_v1"
+	case StFormatConsistencyProofV1:
+		return "consistency_proof_v1"
+	case StFormatInclusionProofV1:
+		return "inclusion_proof_v1"
+	case StFormatSignedChecksumV1:
+		return "signed_checksum_v1"
+	default:
+		return fmt.Sprintf("unknown StFormat: %d", f)
+	}
+}
+
+func (i StItem) String() string {
+	switch i.Format {
+	case StFormatReserved:
+		return fmt.Sprintf("Format(%s)", i.Format)
+	case StFormatSignedTreeHeadV1:
+		return fmt.Sprintf("Format(%s): %+v", i.Format, i.SignedTreeHeadV1)
+	case StFormatCosignedTreeHeadV1:
+		return fmt.Sprintf("Format(%s): %+v", i.Format, i.CosignedTreeHeadV1)
+	case StFormatConsistencyProofV1:
+		return fmt.Sprintf("Format(%s): %+v", i.Format, i.ConsistencyProofV1)
+	case StFormatInclusionProofV1:
+		return fmt.Sprintf("Format(%s): %+v", i.Format, i.InclusionProofV1)
+	case StFormatSignedChecksumV1:
+		return fmt.Sprintf("Format(%s): %+v", i.Format, i.SignedChecksumV1)
+	default:
+		return fmt.Sprintf("unknown StItem: %v", i.Format)
+	}
+}
+
+// Marshal marshals a TLS-encodable item
+func Marshal(item interface{}) ([]byte, error) {
+	serialized, err := tls.Marshal(item)
+	if err != nil {
+		return nil, fmt.Errorf("tls.Marshal: %v", err)
+	}
+	return serialized, nil
+}
+
+// Unmarshal unmarshals a TLS-encoded item
+func Unmarshal(serialized []byte, out interface{}) error {
+	extra, err := tls.Unmarshal(serialized, out)
+	if err != nil {
+		return fmt.Errorf("tls.Unmarshal: %v", err)
+	}
+	if len(extra) > 0 {
+		return fmt.Errorf("tls.Unmarshal: extra data: %X", extra)
+	}
+	return nil
+}
diff --git a/types/item_test.go b/types/item_test.go
new file mode 100644
index 0000000..01c3376
--- /dev/null
+++ b/types/item_test.go
@@ -0,0 +1,626 @@
+package types
+
+import (
+	"bytes"
+	"strings"
+	"testing"
+)
+
+// testCaseType is a common test case used for ST log types
+type testCaseType struct {
+	description string
+	item        interface{}
+	wantErr     bool
+	wantBytes   []byte // only used if no error and not equal to nil
+}
+
+// TestMarshalUnmarshal tests that valid ST log structures can be marshalled and
+// then unmarshalled without error, and that invalid ST log structures cannot be
+// marshalled.  If wantBytes is non-nil the marshalled result must also match.
+func TestMarshalUnmarshal(t *testing.T) {
+	var tests []testCaseType
+	tests = append(tests, test_cases_stitem(t)...)
+	tests = append(tests, test_cases_sthv1(t)...)
+	tests = append(tests, test_cases_costhv1(t)...)
+	tests = append(tests, test_cases_cpv1(t)...)
+	tests = append(tests, test_cases_ipv1(t)...)
+	tests = append(tests, test_cases_signed_checksumv1(t)...)
+	tests = append(tests, test_cases_checksumv1(t)...)
+	tests = append(tests, test_cases_thv1(t)...)
+	tests = append(tests, test_cases_nh(t)...)
+	tests = append(tests, test_cases_sigv1(t)...)
+	tests = append(tests, test_cases_namespace(t)...)
+	tests = append(tests, test_cases_ed25519v1(t)...)
+	for _, table := range tests {
+		b, err := Marshal(table.item)
+		if got, want := err != nil, table.wantErr; got != want {
+			t.Errorf("got error %v but wanted %v in test %q: %v", got, want, table.description, err)
+		}
+		if err != nil {
+			continue // nothing to unmarshal
+		}
+		if got, want := b, table.wantBytes; want != nil && !bytes.Equal(got, want) {
+			t.Errorf("got bytes \n%v\n\tbut wanted\n%v\n\t in test %q: %v", got, want, table.description, err)
+		}
+
+		switch table.item.(type) {
+		case StItem:
+			var item StItem
+			err = Unmarshal(b, &item)
+		case SignedTreeHeadV1:
+			var item SignedTreeHeadV1
+			err = Unmarshal(b, &item)
+		case CosignedTreeHeadV1:
+			var item CosignedTreeHeadV1
+			err = Unmarshal(b, &item)
+		case ConsistencyProofV1:
+			var item ConsistencyProofV1
+			err = Unmarshal(b, &item)
+		case InclusionProofV1:
+			var item InclusionProofV1
+			err = Unmarshal(b, &item)
+		case SignedChecksumV1:
+			var item SignedChecksumV1
+			err = Unmarshal(b, &item)
+		case ChecksumV1:
+			var item ChecksumV1
+			err = Unmarshal(b, &item)
+		case TreeHeadV1:
+			var item TreeHeadV1
+			err = Unmarshal(b, &item)
+		case NodeHash:
+			var item NodeHash
+			err = Unmarshal(b, &item)
+		case SignatureV1:
+			var item SignatureV1
+			err = Unmarshal(b, &item)
+		case Namespace:
+			var item Namespace
+			err = Unmarshal(b, &item)
+		case Ed25519V1:
+			var item Ed25519V1
+			err = Unmarshal(b, &item)
+		default:
+			t.Errorf("unhandled type in test %q", table.description)
+		}
+		if err != nil {
+			t.Errorf("unmarshal failed but wanted success in test %q: %v", table.description, err)
+		}
+	}
+}
+
+// TestUnmarshalStItem tests that invalid StItems cannot be unmarshalled
+func TestUnmarshalStItem(t *testing.T) {
+	tests := test_cases_stitem(t)[1:] // skip reserved type
+	for _, table := range tests {
+		description := table.description[7:] // skip "valid: " prefix
+		b, err := Marshal(table.item)
+		if err != nil {
+			t.Fatalf("must marshal in test %q: %v", description, err)
+		}
+
+		var item StItem
+		if err := Unmarshal(append(b[:], []byte{0}...), &item); err == nil {
+			t.Errorf("unmarshal suceeded with one extra byte in test %q", description)
+		}
+		if err := Unmarshal(b[:len(b)-1], &item); err == nil {
+			t.Errorf("unmarshal suceeded with one byte short in test %q", description)
+		}
+		if err := Unmarshal(append(b[:], b[:]...), &item); err == nil {
+			t.Errorf("unmarshal succeeded with appended StItem in test %q", description)
+		}
+		if err := Unmarshal([]byte{0}, &item); err == nil {
+			t.Errorf("unmarshal succeeded with a single byte in test %q", description)
+		}
+	}
+}
+
+// TestStItemString checks that the String() function prints the right format,
+// and that following body is printed in a verbose mode without a nil-ptr panic.
+func TestStItemString(t *testing.T) {
+	wantPrefix := map[StFormat]string{
+		StFormatReserved:           "Format(reserved)",
+		StFormatSignedTreeHeadV1:   "Format(signed_tree_head_v1): &{TreeHead",
+		StFormatCosignedTreeHeadV1: "Format(cosigned_tree_head_v1): &{SignedTreeHead",
+		StFormatConsistencyProofV1: "Format(consistency_proof_v1): &{LogId",
+		StFormatInclusionProofV1:   "Format(inclusion_proof_v1): &{LogId",
+		StFormatSignedChecksumV1:   "Format(signed_checksum_v1): &{Data",
+		StFormat(1<<16 - 1):        "unknown StItem: unknown StFormat: 65535",
+	}
+	tests := append(test_cases_stitem(t), testCaseType{
+		description: "valid: unknown StItem",
+		item: StItem{
+			Format: StFormat(1<<16 - 1),
+		},
+	})
+	for _, table := range tests {
+		item, ok := table.item.(StItem)
+		if !ok {
+			t.Fatalf("must cast to StItem in test %q", table.description)
+		}
+
+		prefix, ok := wantPrefix[item.Format]
+		if !ok {
+			t.Fatalf("must have prefix for StFormat %v in test %q", item.Format, table.description)
+		}
+		if got, want := item.String(), prefix; !strings.HasPrefix(got, want) {
+			t.Errorf("got %q but wanted prefix %q in test %q", got, want, table.description)
+		}
+	}
+}
+
+var (
+	// StItem
+	testStItemReserved = StItem{
+		Format: StFormatReserved,
+	}
+
+	testStItemSignedTreeHeadV1 = StItem{
+		Format:           StFormatSignedTreeHeadV1,
+		SignedTreeHeadV1: &testSignedTreeHeadV1,
+	}
+	testStItemSignedTreeHeadV1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x01},        // format signed_tree_head_v1
+		testSignedTreeHeadV1Bytes, // SignedTreeHeadV1
+	}, nil)
+
+	testStItemCosignedTreeHeadV1 = StItem{
+		Format:             StFormatCosignedTreeHeadV1,
+		CosignedTreeHeadV1: &testCosignedTreeHeadV1,
+	}
+	testStItemCosignedTreeHeadV1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x02},          // format cosigned_tree_head_v1
+		testCosignedTreeHeadV1Bytes, // CosignedTreeHeadV1,
+	}, nil)
+
+	testStItemConsistencyProofV1 = StItem{
+		Format:             StFormatConsistencyProofV1,
+		ConsistencyProofV1: &testConsistencyProofV1,
+	}
+	testStItemConsistencyProofV1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x03},          // format consistency_proof_v1
+		testConsistencyProofV1Bytes, // ConsistencyProofV1
+	}, nil)
+
+	testStItemInclusionProofV1 = StItem{
+		Format:           StFormatInclusionProofV1,
+		InclusionProofV1: &testInclusionProofV1,
+	}
+	testStItemInclusionProofV1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x04},        // format inclusion_proof_v1
+		testInclusionProofV1Bytes, // InclusionProofV1
+	}, nil)
+
+	testStItemSignedChecksumV1 = StItem{
+		Format:           StFormatSignedChecksumV1,
+		SignedChecksumV1: &testSignedChecksumV1,
+	}
+	testStItemSignedChecksumV1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x05},        // format signed_checksum_v1
+		testSignedChecksumV1Bytes, // SignedChecksumV1
+	}, nil)
+
+	// Subtypes used by StItem
+	testSignedTreeHeadV1 = SignedTreeHeadV1{
+		TreeHead:  testTreeHeadV1,
+		Signature: testSignatureV1,
+	}
+	testSignedTreeHeadV1Bytes = bytes.Join([][]byte{
+		testTreeHeadV1Bytes,  // tree head
+		testSignatureV1Bytes, // signature
+	}, nil)
+
+	testCosignedTreeHeadV1 = CosignedTreeHeadV1{
+		SignedTreeHead: testSignedTreeHeadV1,
+		Cosignatures: []SignatureV1{
+			testSignatureV1,
+		},
+	}
+	testCosignedTreeHeadV1Bytes = bytes.Join([][]byte{
+		testSignedTreeHeadV1Bytes,                                 // signed tree head
+		[]byte{0x00, 0x00, 0x00, byte(len(testSignatureV1Bytes))}, // cosignature length specifier
+		testSignatureV1Bytes,                                      // the only cosignature in this list
+	}, nil)
+
+	testConsistencyProofV1 = ConsistencyProofV1{
+		LogId:     testNamespace,
+		TreeSize1: 16909060,
+		TreeSize2: 16909060,
+		ConsistencyPath: []NodeHash{
+			testNodeHash,
+		},
+	}
+	testConsistencyProofV1Bytes = bytes.Join([][]byte{
+		testNamespaceBytes, // log id
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04}, // tree size 1
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04}, // tree size 2
+		[]byte{0x00, byte(len(testNodeHashBytes))},             // consistency path length specifier
+		testNodeHashBytes, // the only node hash in this proof
+	}, nil)
+
+	testInclusionProofV1 = InclusionProofV1{
+		LogId:     testNamespace,
+		TreeSize:  16909060,
+		LeafIndex: 16909060,
+		InclusionPath: []NodeHash{
+			testNodeHash,
+		},
+	}
+	testInclusionProofV1Bytes = bytes.Join([][]byte{
+		testNamespaceBytes, // log id
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04}, // tree size
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04}, // leaf index
+		[]byte{0x00, byte(len(testNodeHashBytes))},             // inclusion path length specifier
+		testNodeHashBytes, // the only node hash in this proof
+	}, nil)
+
+	testSignedChecksumV1 = SignedChecksumV1{
+		Data:      testChecksumV1,
+		Signature: testSignatureV1,
+	}
+	testSignedChecksumV1Bytes = bytes.Join([][]byte{
+		testChecksumV1Bytes,  // data
+		testSignatureV1Bytes, // signature
+	}, nil)
+
+	// Additional subtypes
+	testChecksumV1 = ChecksumV1{
+		Identifier: []byte("foobar-1-2-3"),
+		Checksum:   make([]byte, 32),
+	}
+	testChecksumV1Bytes = bytes.Join([][]byte{
+		[]byte{12},             // identifier length specifier
+		[]byte("foobar-1-2-3"), // identifier
+		[]byte{32},             // checksum length specifier
+		make([]byte, 32),       // checksum
+	}, nil)
+
+	testTreeHeadV1 = TreeHeadV1{
+		Timestamp: 16909060,
+		TreeSize:  16909060,
+		RootHash:  testNodeHash,
+		Extension: make([]byte, 0),
+	}
+	testTreeHeadV1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04}, // timestamp
+		[]byte{0x00, 0x00, 0x00, 0x00, 0x01, 0x02, 0x03, 0x04}, // tree size
+		testNodeHashBytes,  // root hash
+		[]byte{0x00, 0x00}, // extension length specifier
+		// no extension
+	}, nil)
+
+	testNodeHash = NodeHash{
+		Data: make([]byte, 32),
+	}
+	testNodeHashBytes = bytes.Join([][]byte{
+		[]byte{32}, // node hash length specifier
+		make([]byte, 32),
+	}, nil)
+
+	testSignatureV1 = SignatureV1{
+		Namespace: testNamespace,
+		Signature: make([]byte, 64),
+	}
+	testSignatureV1Bytes = bytes.Join([][]byte{
+		testNamespaceBytes, // namespace field
+		[]byte{0, 64},      // signature length specifier
+		make([]byte, 64),   // signature
+	}, nil)
+)
+
+// test_cases_stitem returns test cases for the different StItem types
+func test_cases_stitem(t *testing.T) []testCaseType {
+	t.Helper()
+	return []testCaseType{
+		{
+			description: "invalid: StItem: reserved",
+			item:        testStItemReserved,
+			wantErr:     true,
+		},
+		{
+			description: "valid: StItem: signed_tree_head_v1",
+			item:        testStItemSignedTreeHeadV1,
+			wantBytes:   testStItemSignedTreeHeadV1Bytes,
+		},
+		{
+			description: "valid: StItem: cosigned_tree_head_v1",
+			item:        testStItemCosignedTreeHeadV1,
+			wantBytes:   testStItemCosignedTreeHeadV1Bytes,
+		},
+		{
+			description: "valid: StItem: consistency_proof_v1",
+			item:        testStItemConsistencyProofV1,
+			wantBytes:   testStItemConsistencyProofV1Bytes,
+		},
+		{
+			description: "valid: StItem: inclusion_proof_v1",
+			item:        testStItemInclusionProofV1,
+			wantBytes:   testStItemInclusionProofV1Bytes,
+		},
+		{
+			description: "valid: StItem: signed_checksum_v1",
+			item:        testStItemSignedChecksumV1,
+			wantBytes:   testStItemSignedChecksumV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_sthv1 returns test cases for the SignedTreeHeadV1 structure
+func test_cases_sthv1(t *testing.T) []testCaseType {
+	t.Helper()
+	return []testCaseType{
+		{
+			description: "valid: testSignedTreeHeadV1",
+			item:        testSignedTreeHeadV1,
+			wantBytes:   testSignedTreeHeadV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_costhv1 returns test cases for the CosignedTreeHeadV1 structure
+func test_cases_costhv1(t *testing.T) []testCaseType {
+	t.Helper()
+	return []testCaseType{
+		{
+			description: "test_cases_costhv1: valid: min",
+			item: CosignedTreeHeadV1{
+				SignedTreeHead: testSignedTreeHeadV1,
+				Cosignatures:   make([]SignatureV1, 0),
+			},
+		}, // skipping "valid: max" because it is huge
+		{
+			description: "test_cases_costhv1: testCosignedTreeHeadV1",
+			item:        testCosignedTreeHeadV1,
+			wantBytes:   testCosignedTreeHeadV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_cpv1 returns test cases for the ConsistencyProofV1 structure
+func test_cases_cpv1(t *testing.T) []testCaseType {
+	t.Helper()
+	max := 65535 // max consistency proof
+	return []testCaseType{
+		{
+			description: "test_cases_cpv1: invalid: >max",
+			item: ConsistencyProofV1{
+				LogId:     testNamespace,
+				TreeSize1: 0,
+				TreeSize2: 0,
+				ConsistencyPath: func() []NodeHash {
+					var path []NodeHash
+					for sum := 0; sum < max+1; sum += 1 + len(testNodeHash.Data) {
+						path = append(path, testNodeHash)
+					}
+					return path
+				}(),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_cpv1: valid: min",
+			item: ConsistencyProofV1{
+				LogId:           testNamespace,
+				TreeSize1:       0,
+				TreeSize2:       0,
+				ConsistencyPath: make([]NodeHash, 0),
+			},
+		},
+		{
+			description: "test_cases_cpv1: valid: testConsistencyProofV1",
+			item:        testConsistencyProofV1,
+			wantBytes:   testConsistencyProofV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_ipv1 returns test cases for the InclusionProofV1 structure
+func test_cases_ipv1(t *testing.T) []testCaseType {
+	t.Helper()
+	max := 65535 // max inclusion proof
+	return []testCaseType{
+		{
+			description: "test_cases_ipv1: invalid: >max",
+			item: InclusionProofV1{
+				LogId:     testNamespace,
+				TreeSize:  0,
+				LeafIndex: 0,
+				InclusionPath: func() []NodeHash {
+					var path []NodeHash
+					for sum := 0; sum < max+1; sum += 1 + len(testNodeHash.Data) {
+						path = append(path, testNodeHash)
+					}
+					return path
+				}(),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_ipv1: valid: min",
+			item: InclusionProofV1{
+				LogId:         testNamespace,
+				TreeSize:      0,
+				LeafIndex:     0,
+				InclusionPath: make([]NodeHash, 0),
+			},
+		},
+		{
+			description: "test_cases_ipv1: valid: testInclusionProofV1",
+			item:        testInclusionProofV1,
+			wantBytes:   testInclusionProofV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_signed_checksumv1 returns test cases for the SignedChecksumV1 structure
+func test_cases_signed_checksumv1(t *testing.T) []testCaseType {
+	t.Helper()
+	return []testCaseType{
+		{
+			description: "test_cases_signed_checksumv1: valid: testSignedChecksumV1",
+			item:        testSignedChecksumV1,
+			wantBytes:   testSignedChecksumV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_checksumv1 returns test cases for the ChecksumV1 structure
+func test_cases_checksumv1(t *testing.T) []testCaseType {
+	t.Helper()
+	minIdentifier, maxIdentifier, identifier := 1, 128, []byte("foobar-1-2-3")
+	minChecksum, maxChecksum, checksum := 1, 64, make([]byte, 32)
+	return []testCaseType{
+		{
+			description: "test_cases_checksumv1: invalid: identifier: min",
+			item: ChecksumV1{
+				Identifier: make([]byte, minIdentifier-1),
+				Checksum:   checksum,
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_checksumv1: invalid: identifier: max",
+			item: ChecksumV1{
+				Identifier: make([]byte, maxIdentifier+1),
+				Checksum:   checksum,
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_checksumv1: invalid: checksum: min",
+			item: ChecksumV1{
+				Identifier: identifier,
+				Checksum:   make([]byte, minChecksum-1),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_checksumv1: invalid: checksum: max",
+			item: ChecksumV1{
+				Identifier: identifier,
+				Checksum:   make([]byte, maxChecksum+1),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_checksumv1: valid: testChecksumV1",
+			item:        testChecksumV1,
+			wantBytes:   testChecksumV1Bytes,
+		},
+	}
+}
+
+// test_cases_thv1 returns test cases for the TreeHeadV1 structure
+func test_cases_thv1(t *testing.T) []testCaseType {
+	t.Helper()
+	min, max := 0, 1<<16-1 // extensions min and max
+	return []testCaseType{
+		{
+			description: "test_cases_thv1: invalid: max",
+			item: TreeHeadV1{
+				Timestamp: 0,
+				TreeSize:  0,
+				RootHash:  testNodeHash,
+				Extension: make([]byte, max+1),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_thv1: valid: min",
+			item: TreeHeadV1{
+				Timestamp: 0,
+				TreeSize:  0,
+				RootHash:  testNodeHash,
+				Extension: make([]byte, min),
+			},
+		},
+		{
+			description: "test_cases_thv1: valid: max",
+			item: TreeHeadV1{
+				Timestamp: 0,
+				TreeSize:  0,
+				RootHash:  testNodeHash,
+				Extension: make([]byte, max),
+			},
+		},
+		{
+			description: "test_cases_thv1: valid: testTreeHeadV1",
+			item:        testTreeHeadV1,
+			wantBytes:   testTreeHeadV1Bytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_nh returns test cases for the NodeHash structure
+func test_cases_nh(t *testing.T) []testCaseType {
+	t.Helper()
+	min, max := 32, 1<<8-1 // NodeHash min and max
+	return []testCaseType{
+		{
+			description: "test_cases_nh: invalid: min",
+			item:        NodeHash{make([]byte, min-1)},
+			wantErr:     true,
+		},
+		{
+			description: "test_cases_nh: invalid: max",
+			item:        NodeHash{make([]byte, max+1)},
+			wantErr:     true,
+		},
+		{
+			description: "test_cases_nh: valid: min",
+			item:        NodeHash{make([]byte, min)},
+		},
+		{
+			description: "test_cases_nh: valid: max",
+			item:        NodeHash{make([]byte, max)},
+		},
+		{
+			description: "test_cases_nh: valid: testNodeHash",
+			item:        testNodeHash,
+			wantBytes:   testNodeHashBytes,
+		}, // other invalid bounds are already tested in subtypes
+	}
+}
+
+// test_cases_sigv1 returns test cases for the SignatureV1 structure
+func test_cases_sigv1(t *testing.T) []testCaseType {
+	t.Helper()
+	min, max := 1, 1<<16-1 // signature min and max
+	return []testCaseType{
+		{
+			description: "test_cases_sigv1: invalid: min",
+			item: SignatureV1{
+				Namespace: testNamespace,
+				Signature: make([]byte, min-1),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_sigv1: invalid: max",
+			item: SignatureV1{
+				Namespace: testNamespace,
+				Signature: make([]byte, max+1),
+			},
+			wantErr: true,
+		},
+		{
+			description: "test_cases_sigv1: valid: min",
+			item: SignatureV1{
+				Namespace: testNamespace,
+				Signature: make([]byte, min),
+			},
+		},
+		{
+			description: "test_cases_sigv1: valid: max",
+			item: SignatureV1{
+				Namespace: testNamespace,
+				Signature: make([]byte, max),
+			},
+		},
+		{
+			description: "test_cases_sigV1: valid: testSignatureV1",
+			item:        testSignatureV1,
+			wantBytes:   testSignatureV1Bytes,
+		},
+	}
+}
diff --git a/types/namespace.go b/types/namespace.go
new file mode 100644
index 0000000..8a2ad17
--- /dev/null
+++ b/types/namespace.go
@@ -0,0 +1,135 @@
+package types
+
+import (
+	"fmt"
+
+	"crypto/ed25519"
+
+	"github.com/google/certificate-transparency-go/tls"
+)
+
+// NamespaceFormat defines a particular namespace type that is versioend
+type NamespaceFormat tls.Enum
+
+const (
+	NamespaceFormatReserved  NamespaceFormat = 0
+	NamespaceFormatEd25519V1 NamespaceFormat = 1
+)
+
+// Namespace references a versioned namespace based on a given format specifier
+type Namespace struct {
+	Format    NamespaceFormat `tls:"maxval:65535"`
+	Ed25519V1 *Ed25519V1      `tls:"selector:Format,val:1"`
+}
+
+// Ed25519V1 uses an Ed25519 verification key as namespace.  Encoding,
+// signing, and verification operations are defined by RFC 8032.
+type Ed25519V1 struct {
+	Namespace [32]byte
+}
+
+func (f NamespaceFormat) String() string {
+	switch f {
+	case NamespaceFormatReserved:
+		return "reserved"
+	case NamespaceFormatEd25519V1:
+		return "ed25519_v1"
+	default:
+		return fmt.Sprintf("unknown NamespaceFormat: %d", f)
+	}
+}
+
+func (n Namespace) String() string {
+	switch n.Format {
+	case NamespaceFormatReserved:
+		return fmt.Sprintf("Format(%s)", n.Format)
+	case NamespaceFormatEd25519V1:
+		return fmt.Sprintf("Format(%s): %+v", n.Format, n.Ed25519V1)
+	default:
+		return fmt.Sprintf("unknown Namespace: %v", n.Format)
+	}
+}
+
+// NewNamespaceEd25519V1 returns an new Ed25519V1 namespace based on a
+// verification key.
+func NewNamespaceEd25519V1(vk []byte) (*Namespace, error) {
+	if len(vk) != 32 {
+		return nil, fmt.Errorf("invalid verification key: must be 32 bytes")
+	}
+
+	var ed25519v1 Ed25519V1
+	copy(ed25519v1.Namespace[:], vk)
+	return &Namespace{
+		Format:    NamespaceFormatEd25519V1,
+		Ed25519V1: &ed25519v1,
+	}, nil
+}
+
+// Verify checks that signature is valid over message for this namespace
+func (ns *Namespace) Verify(message, signature []byte) error {
+	switch ns.Format {
+	case NamespaceFormatEd25519V1:
+		if !ed25519.Verify(ed25519.PublicKey(ns.Ed25519V1.Namespace[:]), message, signature) {
+			return fmt.Errorf("ed25519 signature verification failed")
+		}
+	default:
+		return fmt.Errorf("namespace not supported: %v", ns.Format)
+	}
+	return nil
+}
+
+// NamespacePool is a pool of namespaces that contain complete verification keys
+type NamespacePool struct {
+	pool map[string]*Namespace
+	list []*Namespace
+	// If we need to update this structure without a restart => add mutex.
+}
+
+// NewNameSpacePool creates a new namespace pool from a list of namespaces.  An
+// error is returned if there are duplicate namespaces or namespaces without a
+// complete verification key.  The latter is determined by namespaceWithKey().
+func NewNamespacePool(namespaces []*Namespace) (*NamespacePool, error) {
+	np := &NamespacePool{
+		pool: make(map[string]*Namespace),
+		list: make([]*Namespace, 0),
+	}
+	for _, namespace := range namespaces {
+		if !namespaceWithKey(namespace.Format) {
+			return nil, fmt.Errorf("need verification key in namespace pool: %v", namespace.Format)
+		}
+		if _, ok := np.pool[namespace.String()]; ok {
+			return nil, fmt.Errorf("duplicate namespace: %v", namespace.String())
+		}
+		np.pool[namespace.String()] = namespace
+		np.list = append(np.list, namespace)
+	}
+	return np, nil
+}
+
+// Find checks if namespace is a member of the namespace pool.
+func (np *NamespacePool) Find(namespace *Namespace) (*Namespace, bool) {
+	if _, ok := np.pool[namespace.String()]; !ok {
+		return nil, false
+	}
+	// If the passed namespace is a key fingerprint the actual key needs to be
+	// attached before returning.  Not applicable for Ed25519.  Docdoc later.
+	return namespace, true
+}
+
+// List returns a copied list of namespaces that is used by this pool.
+func (np *NamespacePool) List() []*Namespace {
+	namespaces := make([]*Namespace, len(np.list))
+	copy(namespaces, np.list)
+	return namespaces
+}
+
+// namespaceWithKey returns true if a namespace format contains a complete
+// verification key.  I.e., some formats might have a key fingerprint instead.
+func namespaceWithKey(format NamespaceFormat) bool {
+	switch format {
+	case NamespaceFormatEd25519V1:
+		return true
+	default:
+		return false
+	}
+}
diff --git a/types/namespace_test.go b/types/namespace_test.go
new file mode 100644
index 0000000..da18b13
--- /dev/null
+++ b/types/namespace_test.go
@@ -0,0 +1,301 @@
+package types
+
+import (
+	"bytes"
+	"reflect"
+	"strings"
+	"testing"
+
+	"crypto/ed25519"
+)
+
+var (
+	// Namespace
+	testNamespaceReserved = Namespace{
+		Format: NamespaceFormatReserved,
+	}
+
+	testNamespace          = testNamespaceEd25519V1
+	testNamespaceBytes     = testNamespaceEd25519V1Bytes
+	testNamespaceEd25519V1 = Namespace{
+		Format:    NamespaceFormatEd25519V1,
+		Ed25519V1: &testEd25519V1,
+	}
+	testNamespaceEd25519V1Bytes = bytes.Join([][]byte{
+		[]byte{0x00, 0x01}, // format ed25519_v1
+		testEd25519V1Bytes, // Ed25519V1
+	}, nil)
+
+	// Subtypes used by Namespace
+	testEd25519V1 = Ed25519V1{
+		Namespace: [32]byte{},
+	}
+	testEd25519V1Bytes = bytes.Join([][]byte{
+		make([]byte, 32), // namespace, no length specifier because fixed size
+	}, nil)
+)
+
+func TestNewNamespaceEd25519V1(t *testing.T) {
+	size := 32 // verification key size
+	for _, table := range []struct {
+		description string
+		vk          []byte
+		wantErr     bool
+	}{
+		{
+			description: "invalid",
+			vk:          make([]byte, size+1),
+			wantErr:     true,
+		},
+		{
+			description: "valid",
+			vk:          make([]byte, size),
+		},
+	} {
+		n, err := NewNamespaceEd25519V1(table.vk)
+		if got, want := err != nil, table.wantErr; got != want {
+			t.Errorf("got error %v but wanted %v in test %q: %v", got, want, table.description, err)
+		}
+		if err != nil {
+			continue
+		}
+		if got, want := n.Format, NamespaceFormatEd25519V1; got != want {
+			t.Errorf("got namespace format %v but wanted %v in test %q", got, want, table.description)
+			continue
+		}
+		if got, want := n.Ed25519V1.Namespace[:], table.vk; !bytes.Equal(got, want) {
+			t.Errorf("got namespace %X but wanted %X in test %q", got, want, table.description)
+		}
+	}
+}
+
+func TestNamespaceString(t *testing.T) {
+	wantPrefix := map[NamespaceFormat]string{
+		NamespaceFormatReserved:    "Format(reserved)",
+		NamespaceFormatEd25519V1:   "Format(ed25519_v1): &{Namespace",
+		NamespaceFormat(1<<16 - 1): "unknown Namespace: unknown NamespaceFormat: 65535",
+	}
+	tests := append(test_cases_namespace(t), testCaseType{
+		description: "valid: unknown Namespace",
+		item: Namespace{
+			Format: NamespaceFormat(1<<16 - 1),
+		},
+	})
+	for _, table := range tests {
+		namespace, ok := table.item.(Namespace)
+		if !ok {
+			t.Fatalf("must cast to Namespace in test %q", table.description)
+		}
+
+		prefix, ok := wantPrefix[namespace.Format]
+		if !ok {
+			t.Fatalf("must have prefix for StFormat %v in test %q", namespace.Format, table.description)
+		}
+		if got, want := namespace.String(), prefix; !strings.HasPrefix(got, want) {
+			t.Errorf("got %q but wanted prefix %q in test %q", got, want, table.description)
+		}
+	}
+}
+
+func TestVerify(t *testing.T) {
+	var tests []testCaseNamespace
+	tests = append(tests, test_cases_verify(t)...)
+	tests = append(tests, test_cases_verify_ed25519v1(t)...)
+	for _, table := range tests {
+		err := table.namespace.Verify(table.msg, table.sig)
+		if got, want := err != nil, table.wantErr; got != want {
+			t.Errorf("got error=%v but wanted %v in test %q: %v", got, want, table.description, err)
+		}
+	}
+}
+
+func TestNewNamespacePool(t *testing.T) {
+	ns1 := mustInitNamespaceEd25519V1(t, 0x00)
+	ns2 := mustInitNamespaceEd25519V1(t, 0xff)
+	nsr := &Namespace{Format: NamespaceFormatReserved}
+	for _, table := range []struct {
+		description string
+		namespaces  []*Namespace
+		wantErr     bool
+	}{
+		{
+			description: "invalid: duplicate namespace",
+			namespaces:  []*Namespace{ns1, ns1, ns2},
+			wantErr:     true,
+		},
+		{
+			description: "invalid: namespace without key",
+			namespaces:  []*Namespace{ns1, nsr, ns2},
+			wantErr:     true,
+		},
+		{
+			description: "valid: empty",
+			namespaces:  []*Namespace{},
+		},
+		{
+			description: "valid: one namespace",
+			namespaces:  []*Namespace{ns1},
+		},
+		{
+			description: "valid: two namespaces",
+			namespaces:  []*Namespace{ns1, ns2},
+		},
+	} {
+		_, err := NewNamespacePool(table.namespaces)
+		if got, want := err != nil, table.wantErr; got != want {
+			t.Errorf("got error %v but wanted %v in test %q: %v", got, want, table.description, err)
+		}
+	}
+}
+
+func TestFind(t *testing.T) {
+	ns1 := mustInitNamespaceEd25519V1(t, 0x00)
+	ns2 := mustInitNamespaceEd25519V1(t, 0xff)
+
+	// Empty pool
+	pool, err := NewNamespacePool(nil)
+	if err != nil {
+		t.Fatalf("must create new namespace pool: %v", err)
+	}
+	if _, ok := pool.Find(ns1); ok {
+		t.Errorf("found namespace in empty pool")
+	}
+
+	// Pool with one namespace
+	pool, err = NewNamespacePool([]*Namespace{ns1})
+	if err != nil {
+		t.Fatalf("must create new namespace pool: %v", err)
+	}
+	if ns, ok := pool.Find(ns1); !ok {
+		t.Errorf("could not find namespace that is a member of the pool")
+	} else if !reflect.DeepEqual(ns, ns1) {
+		t.Errorf("found namespace but it is wrong")
+	}
+	if _, ok := pool.Find(ns2); ok {
+		t.Errorf("found namespace although it is not a member of the pool")
+	}
+}
+
+func TestList(t *testing.T) {
+	ns1 := mustInitNamespaceEd25519V1(t, 0x00)
+	ns2 := mustInitNamespaceEd25519V1(t, 0xff)
+	namespaces := []*Namespace{ns1, ns2}
+	pool, err := NewNamespacePool(namespaces)
+	if err != nil {
+		t.Fatalf("must create new namespace pool: %v", err)
+	}
+	if got, want := len(pool.List()), len(namespaces); got != want {
+		t.Errorf("got len %v but wanted %v", got, want)
+	}
+	pool.List()[0] = ns2
+	if got, want := pool.List()[0].Ed25519V1.Namespace[:], ns1.Ed25519V1.Namespace[:]; !bytes.Equal(got, want) {
+		t.Errorf("returned list is not a copy")
+	}
+}
+
+// test_cases_namespace returns test cases for the different Namespace types.
+// It is used by TestMarshalUnmarshal(), see test_item.go.
+func test_cases_namespace(t *testing.T) []testCaseType {
+	return []testCaseType{
+		{
+			description: "invalid: Namespace: reserved",
+			item:        testNamespaceReserved,
+			wantErr:     true,
+		},
+		{
+			description: "valid: Namespace: ed25519_v1",
+			item:        testNamespaceEd25519V1,
+			wantBytes:   testNamespaceEd25519V1Bytes,
+		},
+	}
+}
+
+// test_cases_ed25519v1 returns test cases for the Ed25519V1 structure
+// It is used by TestMarshalUnmarshal(), see test_item.go.
+func test_cases_ed25519v1(t *testing.T) []testCaseType {
+	return []testCaseType{
+		{
+			description: "valid: testNamespaceEd25519V1",
+			item:        testEd25519V1,
+			wantBytes:   testEd25519V1Bytes,
+		},
+	}
+}
+
+// testCaseNamespace is a common test case used for Namespace.Verify() tests
+type testCaseNamespace struct {
+	description string
+	namespace   *Namespace
+	msg, sig    []byte
+	wantErr     bool
+}
+
+// test_cases_verify returns basic namespace.Verify() tests
+func test_cases_verify(t *testing.T) []testCaseNamespace {
+	return []testCaseNamespace{
+		{
+			description: "test_cases_verify: invalid: unsupported namespace",
+			namespace:   &Namespace{Format: NamespaceFormatReserved},
+			msg:         []byte("msg"),
+			sig:         []byte("sig"),
+			wantErr:     true,
+		},
+	}
+}
+
+// test_cases_verify_ed25519v1 returns ed25519_v1 Namespace.Verify() tests
+func test_cases_verify_ed25519v1(t *testing.T) []testCaseNamespace {
+	testEd25519Sk := [64]byte{230, 122, 195, 152, 194, 195, 147, 153, 80, 120, 153, 79, 102, 27, 52, 187, 136, 218, 150, 234, 107, 9, 167, 4, 92, 21, 11, 113, 42, 29, 129, 69, 75, 60, 249, 150, 229, 93, 75, 32, 103, 126, 244, 37, 53, 182, 68, 82, 249, 109, 49, 94, 10, 19, 146, 244, 58, 191, 169, 107, 78, 37, 45, 210}
+	testEd25519Vk := [32]byte{75, 60, 249, 150, 229, 93, 75, 32, 103, 126, 244, 37, 53, 182, 68, 82, 249, 109, 49, 94, 10, 19, 146, 244, 58, 191, 169, 107, 78,
+		37, 45, 210}
+	return []testCaseNamespace{
+		{
+			description: "test_cases_verify_ed25519v1: invalid: sk signed message, but vk is not for sk",
+			namespace: &Namespace{
+				Format: NamespaceFormatEd25519V1,
+				Ed25519V1: &Ed25519V1{
+					Namespace: [32]byte{},
+				},
+			},
+			msg:     []byte("message"),
+			sig:     ed25519.Sign(ed25519.PrivateKey(testEd25519Sk[:]), []byte("message")),
+			wantErr: true,
+		},
+		{
+			description: "test_cases_verify_ed25519v1: invalid: vk is for sk, but sk did not sign message",
+			namespace: &Namespace{
+				Format: NamespaceFormatEd25519V1,
+				Ed25519V1: &Ed25519V1{
+					Namespace: testEd25519Vk,
+				},
+			},
+			msg:     []byte("some message"),
+			sig:     ed25519.Sign(ed25519.PrivateKey(testEd25519Sk[:]), []byte("another message")),
+			wantErr: true,
+		},
+		{
+			description: "test_cases_verify_ed25519v1: valid",
+			namespace: &Namespace{
+				Format: NamespaceFormatEd25519V1,
+				Ed25519V1: &Ed25519V1{
+					Namespace: testEd25519Vk,
+				},
+			},
+			msg: []byte("message"),
+			sig: ed25519.Sign(ed25519.PrivateKey(testEd25519Sk[:]), []byte("message")),
+		},
+	}
+}
+
+func mustInitNamespaceEd25519V1(t *testing.T, initByte byte) *Namespace {
+	t.Helper()
+	buf := make([]byte, 32)
+	for i := 0; i < len(buf); i++ {
+		buf[i] = initByte
+	}
+	ns, err := NewNamespaceEd25519V1(buf)
+	if err != nil {
+		t.Fatalf("must make Ed25519v1 namespace: %v", err)
+	}
+	return ns
+}