started replacing x509 with namespace

14 files changed, 334 insertions, 756 deletions

diff --git a/crypto.go b/crypto.go
index 34451cc..546fc0a 100644
--- a/crypto.go
+++ b/crypto.go
@@ -6,55 +6,8 @@ import (
 
 	"crypto"
 	"crypto/rand"
-	"crypto/tls"
-	"crypto/x509"
-
-	"github.com/system-transparency/stfe/x509util"
 )
 
-// buildChainFromDerList builds an X.509 certificate chain from a list of
-// DER-encoded certificates using the log's configured trust anchors, extended
-// key-usages, and maximum chain length (which includes the trust anchor).
-func (lp *LogParameters) buildChainFromDerList(derChain [][]byte) ([]*x509.Certificate, error) {
-	certificate, intermediatePool, err := x509util.ParseDerChain(derChain)
-	if err != nil {
-		return nil, err
-	}
-	opts := x509.VerifyOptions{
-		Roots:         lp.AnchorPool,
-		Intermediates: intermediatePool,
-		KeyUsages:     lp.KeyUsage, // no extended key usage passes by default
-	}
-
-	chains, err := certificate.Verify(opts)
-	if err != nil {
-		return nil, fmt.Errorf("chain verification failed: %v", err)
-	}
-	if len(chains) == 0 { // better safe than sorry
-		return nil, fmt.Errorf("chain verification failed: no path")
-	}
-
-	// there might be several valid chains
-	for _, chain := range chains {
-		if int64(len(chain)) <= lp.MaxChain {
-			return chain, nil // just pick the first valid chain
-		}
-	}
-	return nil, fmt.Errorf("bad certificate chain length: too large")
-}
-
-// verifySignature checks if signature is valid for some serialized data.  The
-// only supported signature scheme is ed25519(0x0807), see §4.2.3 in RFC 8446.
-func (lp *LogParameters) verifySignature(certificate *x509.Certificate, scheme tls.SignatureScheme, serialized, signature []byte) error {
-	if scheme != tls.Ed25519 {
-		return fmt.Errorf("unsupported signature scheme: %v", scheme)
-	}
-	if err := certificate.CheckSignature(x509.PureEd25519, serialized, signature); err != nil {
-		return fmt.Errorf("invalid signature: %v", err)
-	}
-	return nil
-}
-
 // genV1Sdi issues a new SignedDebugInfoV1 StItem from a serialized leaf value
 func (lp *LogParameters) genV1Sdi(serialized []byte) (*StItem, error) {
 	sig, err := lp.Signer.Sign(rand.Reader, serialized, crypto.Hash(0)) // ed25519
diff --git a/crypto_test.go b/crypto_test.go
index d304b93..cfbb0a8 100644
--- a/crypto_test.go
+++ b/crypto_test.go
@@ -6,170 +6,13 @@ import (
 	"fmt"
 	"testing"
 
-	"crypto/ed25519"
-	"crypto/tls"
-
 	cttestdata "github.com/google/certificate-transparency-go/trillian/testdata"
-	"github.com/system-transparency/stfe/x509util"
-	"github.com/system-transparency/stfe/x509util/testdata"
 )
 
 var (
 	testLeaf = make([]byte, 64)
 )
 
-func TestBuildChainFromDerList(t *testing.T) {
-	for _, table := range []struct {
-		description string
-		maxChain    int64    // including trust anchor
-		anchors     []byte   // pem block
-		chain       [][]byte // der list
-		wantErr     bool
-	}{
-		{
-			description: "bad chain: cannot be parsed because empty",
-			maxChain:    3,
-			anchors:     testdata.RootCertificate,
-			wantErr:     true,
-		},
-		{
-			description: "bad chain: no path from end-entity to intermediate",
-			maxChain:    3,
-			anchors:     testdata.RootCertificate2,
-			chain:       mustMakeDerList(t, testdata.ChainBadIntermediate)[:2],
-			wantErr:     true,
-		},
-		{
-			description: "bad chain: no path from intermediate to root",
-			maxChain:    3,
-			anchors:     testdata.RootCertificate2,
-			chain:       mustMakeDerList(t, testdata.IntermediateChain),
-			wantErr:     true,
-		},
-		{
-			description: "bad chain: end-entity certificate expired",
-			maxChain:    3,
-			anchors:     testdata.RootCertificate,
-			chain:       mustMakeDerList(t, testdata.ExpiredChain),
-			wantErr:     false,
-		},
-		{
-			description: "bad chain: too large",
-			maxChain:    2,
-			anchors:     testdata.RootCertificate,
-			chain:       mustMakeDerList(t, testdata.IntermediateChain),
-			wantErr:     true,
-		},
-		{
-			description: "ok chain: one explicit trust anchor",
-			maxChain:    3,
-			anchors:     testdata.RootCertificate,
-			chain:       mustMakeDerList(t, testdata.RootChain),
-		},
-		{
-			description: "ok chain: unnecessary certificates are ignored",
-			maxChain:    3,
-			anchors:     testdata.RootCertificate,
-			chain:       append(mustMakeDerList(t, testdata.IntermediateChain), mustMakeDerList(t, testdata.IntermediateChain2)...),
-		},
-		{
-			description: "ok chain: multiple anchors but one valid path",
-			maxChain:    3,
-			anchors:     testdata.TrustAnchors,
-			chain:       mustMakeDerList(t, testdata.IntermediateChain),
-		},
-		// Note that the underlying verify function also checks name constraints
-		// and extended key usages.  Not relied upon atm, so not tested.
-	} {
-		anchorList, err := x509util.NewCertificateList(table.anchors)
-		if err != nil {
-			t.Fatalf("must parse trust anchors: %v", err)
-		}
-		lp := &LogParameters{
-			LogId:      testLogId,
-			TreeId:     testTreeId,
-			Prefix:     testPrefix,
-			MaxRange:   testMaxRange,
-			MaxChain:   table.maxChain,
-			AnchorPool: x509util.NewCertPool(anchorList),
-			AnchorList: anchorList,
-			KeyUsage:   testExtKeyUsage,
-			Signer:     nil,
-			HashType:   testHashType,
-		}
-		_, err = lp.buildChainFromDerList(table.chain)
-		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 TestVerifySignature(t *testing.T) {
-	lp := makeTestLogParameters(t, nil)
-	for _, table := range []struct {
-		description string
-		certificate []byte // pem
-		key         []byte // pem
-		scheme      tls.SignatureScheme
-		wantErr     bool
-	}{
-		{
-			description: "invalid signature scheme",
-			certificate: testdata.EndEntityCertificate,
-			key:         testdata.EndEntityPrivateKey,
-			scheme:      tls.ECDSAWithP256AndSHA256,
-			wantErr:     true,
-		},
-		{
-			description: "invalid signature: certificate and key mismatch",
-			certificate: testdata.EndEntityCertificate,
-			key:         testdata.EndEntityPrivateKey2,
-			scheme:      tls.Ed25519,
-			wantErr:     true,
-		},
-		{
-			description: "valid signature",
-			certificate: testdata.EndEntityCertificate,
-			key:         testdata.EndEntityPrivateKey,
-			scheme:      tls.Ed25519,
-		},
-	} {
-		msg := []byte("msg")
-		key, err := x509util.NewEd25519PrivateKey(table.key)
-		if err != nil {
-			t.Fatalf("must make ed25519 signing key: %v", err)
-		}
-		list, err := x509util.NewCertificateList(table.certificate)
-		if err != nil {
-			t.Fatalf("must make certificate list: %v", err)
-		}
-		if len(list) != 1 {
-			t.Fatalf("must make one certificate: got %d", len(list))
-		}
-		certificate := list[0]
-		sig := ed25519.Sign(key, msg)
-
-		err = lp.verifySignature(certificate, table.scheme, msg, 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)
-		}
-		if err != nil {
-			continue
-		}
-
-		msg[0] += 1 // modify message
-		if err = lp.verifySignature(certificate, table.scheme, msg, sig); err == nil {
-			t.Errorf("got no error for modified msg in test %q", table.description)
-		}
-
-		msg[0] -= 1 // restore message
-		sig[0] += 1 // modify signature
-		if err = lp.verifySignature(certificate, table.scheme, msg, sig); err == nil {
-			t.Errorf("got no error for modified signature in test %q", table.description)
-		}
-	}
-}
-
 // TestGenV1Sdi tests that a signature failure works as expected, and that
 // the issued SDI (if any) is populated correctly.
 func TestGenV1Sdi(t *testing.T) {
@@ -280,17 +123,3 @@ func TestGenV1Sth(t *testing.T) {
 		}
 	}
 }
-
-// mustMakeDerList must parse a PEM-encoded list of certificates to DER
-func mustMakeDerList(t *testing.T, pem []byte) [][]byte {
-	certs, err := x509util.NewCertificateList(pem)
-	if err != nil {
-		t.Fatalf("must parse pem-encoded certificates: %v", err)
-	}
-
-	list := make([][]byte, 0, len(certs))
-	for _, cert := range certs {
-		list = append(list, cert.Raw)
-	}
-	return list
-}
diff --git a/handler.go b/handler.go
index 58771c8..93251f0 100644
--- a/handler.go
+++ b/handler.go
@@ -59,7 +59,7 @@ func (a Handler) sendHTTPError(w http.ResponseWriter, statusCode int, err error)
 
 func addEntry(ctx context.Context, i *Instance, w http.ResponseWriter, r *http.Request) (int, error) {
 	glog.V(3).Info("handling add-entry request")
-	leaf, appendix, err := i.LogParameters.newAddEntryRequest(r)
+	req, err := i.LogParameters.newAddEntryRequest(r)
 	if err != nil {
 		return http.StatusBadRequest, err
 	}
@@ -67,8 +67,8 @@ func addEntry(ctx context.Context, i *Instance, w http.ResponseWriter, r *http.R
 	trsp, err := i.Client.QueueLeaf(ctx, &trillian.QueueLeafRequest{
 		LogId: i.LogParameters.TreeId,
 		Leaf: &trillian.LogLeaf{
-			LeafValue: leaf,
-			ExtraData: appendix,
+			LeafValue: req.Item,
+			ExtraData: req.Signature,
 		},
 	})
 	if errInner := checkQueueLeaf(trsp, err); errInner != nil {
diff --git a/handler_test.go b/handler_test.go
index 40fd562..dd32c37 100644
--- a/handler_test.go
+++ b/handler_test.go
@@ -6,10 +6,9 @@ import (
 	"crypto"
 	"fmt"
 	"testing"
-	"time"
 
 	"crypto/ed25519"
-	"crypto/tls"
+	//"crypto/tls"
 	"encoding/base64"
 	"encoding/json"
 	"net/http"
@@ -19,12 +18,8 @@ import (
 	"github.com/google/certificate-transparency-go/trillian/mockclient"
 	cttestdata "github.com/google/certificate-transparency-go/trillian/testdata"
 	"github.com/google/trillian"
-	"github.com/system-transparency/stfe/x509util"
-	"github.com/system-transparency/stfe/x509util/testdata"
-)
 
-var (
-	testDeadline = time.Second * 10
+	"github.com/system-transparency/stfe/namespace/testdata"
 )
 
 type testHandler struct {
@@ -119,39 +114,39 @@ func TestPostHandlersRejectGet(t *testing.T) {
 	}
 }
 
-// TestGetAnchors checks for a valid number of decodable trust anchors
-func TestGetAnchors(t *testing.T) {
-	th := newTestHandler(t, nil)
-	defer th.mockCtrl.Finish()
-
-	url := EndpointGetAnchors.Path("http://example.com", th.instance.LogParameters.Prefix)
-	req, err := http.NewRequest("GET", url, nil)
-	if err != nil {
-		t.Fatalf("failed creating http request: %v", err)
-	}
-
-	w := httptest.NewRecorder()
-	th.getHandler(t, EndpointGetAnchors).ServeHTTP(w, req)
-	if w.Code != http.StatusOK {
-		t.Errorf("GET(%s)=%d, want http status code %d", url, w.Code, http.StatusOK)
-		return
-	}
-
-	var derAnchors [][]byte
-	if err := json.Unmarshal([]byte(w.Body.String()), &derAnchors); err != nil {
-		t.Errorf("failed unmarshaling trust anchors response: %v", err)
-		return
-	}
-	if got, want := len(derAnchors), len(th.instance.LogParameters.AnchorList); got != want {
-		t.Errorf("unexpected trust anchor count %d, want %d", got, want)
-	}
-	if _, err := x509util.ParseDerList(derAnchors); err != nil {
-		t.Errorf("failed decoding trust anchors: %v", err)
-	}
-}
+//// TestGetAnchors checks for a valid number of decodable trust anchors
+//func TestGetAnchors(t *testing.T) {
+//	// TODO: refactor with namespaces
+//	//th := newTestHandler(t, nil)
+//	//defer th.mockCtrl.Finish()
+//
+//	//url := EndpointGetAnchors.Path("http://example.com", th.instance.LogParameters.Prefix)
+//	//req, err := http.NewRequest("GET", url, nil)
+//	//if err != nil {
+//	//	t.Fatalf("failed creating http request: %v", err)
+//	//}
+//
+//	//w := httptest.NewRecorder()
+//	//th.getHandler(t, EndpointGetAnchors).ServeHTTP(w, req)
+//	//if w.Code != http.StatusOK {
+//	//	t.Errorf("GET(%s)=%d, want http status code %d", url, w.Code, http.StatusOK)
+//	//	return
+//	//}
+//
+//	//var derAnchors [][]byte
+//	//if err := json.Unmarshal([]byte(w.Body.String()), &derAnchors); err != nil {
+//	//	t.Errorf("failed unmarshaling trust anchors response: %v", err)
+//	//	return
+//	//}
+//	//if got, want := len(derAnchors), len(th.instance.LogParameters.); got != want {
+//	//	t.Errorf("unexpected trust anchor count %d, want %d", got, want)
+//	//}
+//	//if _, err := x509util.ParseDerList(derAnchors); err != nil {
+//	//	t.Errorf("failed decoding trust anchors: %v", err)
+//	//}
+//}
 
 func TestGetEntries(t *testing.T) {
-	chainLen := 3
 	for _, table := range []struct {
 		description string
 		breq        *GetEntriesRequest
@@ -179,23 +174,24 @@ func TestGetEntries(t *testing.T) {
 			wantCode:    http.StatusInternalServerError,
 			wantErrText: http.StatusText(http.StatusInternalServerError) + "\n",
 		},
-		{
-			description: "invalid get-entries response",
-			breq: &GetEntriesRequest{
-				Start: 0,
-				End:   1,
-			},
-			trsp:        makeTrillianGetLeavesByRangeResponse(t, 0, 1, []byte("foobar-1.2.3"), testdata.RootChain, testdata.EndEntityPrivateKey, false),
-			wantCode:    http.StatusInternalServerError,
-			wantErrText: http.StatusText(http.StatusInternalServerError) + "\n",
-		},
+		// TODO: make invalid get-entries response
+		//{
+		//	description: "invalid get-entries response",
+		//	breq: &GetEntriesRequest{
+		//		Start: 0,
+		//		End:   1,
+		//	},
+		//	trsp:        makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk),
+		//	wantCode:    http.StatusInternalServerError,
+		//	wantErrText: http.StatusText(http.StatusInternalServerError) + "\n",
+		//},
 		{
 			description: "valid get-entries response",
 			breq: &GetEntriesRequest{
 				Start: 0,
 				End:   1,
 			},
-			trsp:     makeTrillianGetLeavesByRangeResponse(t, 0, 1, []byte("foobar-1.2.3"), testdata.RootChain, testdata.EndEntityPrivateKey, true),
+			trsp:     makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk),
 			wantCode: http.StatusOK,
 		},
 	} {
@@ -206,7 +202,7 @@ func TestGetEntries(t *testing.T) {
 			url := EndpointGetEntries.Path("http://example.com", th.instance.LogParameters.Prefix)
 			req, err := http.NewRequest("GET", url, nil)
 			if err != nil {
-				t.Fatalf("failed creating http request: %v", err)
+				t.Fatalf("must create http request: %v", err)
 			}
 			q := req.URL.Query()
 			q.Add("start", fmt.Sprintf("%d", table.breq.Start))
@@ -244,30 +240,19 @@ func TestGetEntries(t *testing.T) {
 						t.Errorf("invalid StFormat: got %v, want %v", item.Format, StFormatChecksumV1)
 					}
 					checksum := item.ChecksumV1
-					if got, want := checksum.Package, []byte(fmt.Sprintf("%s_%d", "foobar-1.2.3", int64(i)+table.breq.Start)); !bytes.Equal(got, want) {
+					if got, want := checksum.Package, []byte(fmt.Sprintf("%s_%d", testPackage, int64(i)+table.breq.Start)); !bytes.Equal(got, want) {
 						t.Errorf("got package name %s, want %s", string(got), string(want))
 					}
 					if got, want := checksum.Checksum, make([]byte, 32); !bytes.Equal(got, want) {
 						t.Errorf("got package checksum %X, want %X", got, want)
 					}
+					// TODO: check namespace?
 				}
 
-				chain, err := x509util.ParseDerList(rsp.Chain)
-				if err != nil {
-					t.Errorf("failed parsing certificate chain: %v", err)
-				} else if got, want := len(chain), chainLen; got != want {
-					t.Errorf("got chain length %d, want %d", got, want)
-				} else {
-					if err := x509util.VerifyChain(chain); err != nil {
-						t.Errorf("invalid certificate chain: %v", err)
-					}
-				}
-				if got, want := tls.SignatureScheme(rsp.SignatureScheme), tls.Ed25519; got != want {
-					t.Errorf("got signature scheme %s, want %s", got, want)
-				}
-				if !ed25519.Verify(chain[0].PublicKey.(ed25519.PublicKey), rsp.Item, rsp.Signature) {
-					t.Errorf("invalid ed25519 signature")
-				}
+				// TODO: verify signaturew w/ namespace?
+				//if !ed25519.Verify(chain[0].PublicKey.(ed25519.PublicKey), rsp.Item, rsp.Signature) {
+				//	t.Errorf("invalid ed25519 signature")
+				//}
 			}
 		}()
 	}
@@ -285,29 +270,29 @@ func TestAddEntry(t *testing.T) {
 	}{
 		{
 			description: "empty trillian response",
-			breq:        makeTestLeafBuffer(t, []byte("foobar-1.2.3"), testdata.IntermediateChain, testdata.EndEntityPrivateKey, true),
+			breq:        mustMakeEd25519ChecksumV1Buffer(t, testPackage, testChecksum, testdata.Ed25519Vk, testdata.Ed25519Sk),
 			terr:        fmt.Errorf("back-end failure"),
 			wantCode:    http.StatusInternalServerError,
 			wantErrText: http.StatusText(http.StatusInternalServerError) + "\n",
 		},
 		{
-			description: "bad request parameters",
-			breq:        makeTestLeafBuffer(t, []byte("foobar-1.2.3"), testdata.IntermediateChain, testdata.EndEntityPrivateKey, false),
+			description: "bad request parameters: invalid signature",
+			breq:        mustMakeEd25519ChecksumV1Buffer(t, testPackage, testChecksum, make([]byte, 32), testdata.Ed25519Sk),
 			wantCode:    http.StatusBadRequest,
 			wantErrText: http.StatusText(http.StatusBadRequest) + "\n",
 		},
 		{
 			description: "log signature failure",
-			breq:        makeTestLeafBuffer(t, []byte("foobar-1.2.3"), testdata.IntermediateChain, testdata.EndEntityPrivateKey, true),
-			trsp:        makeTrillianQueueLeafResponse(t, []byte("foobar-1.2.3"), testdata.IntermediateChain, testdata.EndEntityPrivateKey, false),
+			breq:        mustMakeEd25519ChecksumV1Buffer(t, testPackage, testChecksum, testdata.Ed25519Vk, testdata.Ed25519Sk),
+			trsp:        makeTrillianQueueLeafResponse(t, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk, false),
 			wantCode:    http.StatusInternalServerError,
 			wantErrText: http.StatusText(http.StatusInternalServerError) + "\n",
 			signer:      cttestdata.NewSignerWithErr(nil, fmt.Errorf("signing failed")),
 		},
 		{
 			description: "valid add-entry request-response",
-			breq:        makeTestLeafBuffer(t, []byte("foobar-1.2.3"), testdata.IntermediateChain, testdata.EndEntityPrivateKey, true),
-			trsp:        makeTrillianQueueLeafResponse(t, []byte("foobar-1.2.3"), testdata.IntermediateChain, testdata.EndEntityPrivateKey, false),
+			breq:        mustMakeEd25519ChecksumV1Buffer(t, testPackage, testChecksum, testdata.Ed25519Vk, testdata.Ed25519Sk),
+			trsp:        makeTrillianQueueLeafResponse(t, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk, false),
 			wantCode:    http.StatusOK,
 			signer:      cttestdata.NewSignerWithFixedSig(nil, make([]byte, 32)),
 		},
@@ -686,54 +671,28 @@ func TestGetProofByHash(t *testing.T) {
 	}
 }
 
-// makeTestLeaf creates add-entry test data
-func makeTestLeaf(t *testing.T, name, pemChain, pemKey []byte) ([]byte, []byte) {
+// mustMakeEd25519ChecksumV1 creates an ed25519-signed ChecksumV1 leaf
+func mustMakeEd25519ChecksumV1(t *testing.T, id, checksum, vk, sk []byte) ([]byte, []byte) {
 	t.Helper()
-	key, err := x509util.NewEd25519PrivateKey(pemKey)
+	leaf, err := NewChecksumV1(id, checksum, mustNewNamespaceEd25519V1(t, vk)).Marshal()
 	if err != nil {
-		t.Fatalf("failed creating ed25519 signing key: %v", err)
+		t.Fatalf("must serialize checksum_v1: %v", err)
 	}
-	chain, err := x509util.NewCertificateList(pemChain)
-	if err != nil {
-		t.Fatalf("failed parsing x509 chain: %v", err)
-	}
-	leaf, err := NewChecksumV1(name, make([]byte, 32)).Marshal()
-	if err != nil {
-		t.Fatalf("failed creating serialized checksum_v1: %v", err)
-	}
-	appendix, err := NewAppendix(chain, ed25519.Sign(key, leaf), uint16(tls.Ed25519)).Marshal()
-	if err != nil {
-		t.Fatalf("failed creating serialized appendix: %v", err)
-	}
-	return leaf, appendix
+	return leaf, ed25519.Sign(ed25519.PrivateKey(sk), leaf)
 }
 
-// makeTestLeafBuffer creates an add-entry data buffer that can be posted.  If
-// valid is set to false an invalid signature will be used.
-func makeTestLeafBuffer(t *testing.T, name, pemChain, pemKey []byte, valid bool) *bytes.Buffer {
+// mustMakeEd25519ChecksumV1Buffer creates an add-entry data buffer with an
+// Ed25519 namespace that can be posted.
+func mustMakeEd25519ChecksumV1Buffer(t *testing.T, identifier, checksum, vk, sk []byte) *bytes.Buffer {
 	t.Helper()
-	leaf, appendix := makeTestLeaf(t, name, pemChain, pemKey)
-
-	var a Appendix
-	if err := a.Unmarshal(appendix); err != nil {
-		t.Fatalf("failed unmarshaling Appendix: %v", err)
-	}
-	chain := make([][]byte, 0, len(a.Chain))
-	for _, certificate := range a.Chain {
-		chain = append(chain, certificate.Data)
-	}
+	leaf, signature := mustMakeEd25519ChecksumV1(t, identifier, checksum, vk, sk)
 	req := AddEntryRequest{
-		Item:            leaf,
-		Signature:       a.Signature,
-		SignatureScheme: a.SignatureScheme,
-		Chain:           chain,
-	}
-	if !valid {
-		req.Signature = []byte{0, 1, 2, 3}
+		Item:      leaf,
+		Signature: signature,
 	}
 	data, err := json.Marshal(req)
 	if err != nil {
-		t.Fatalf("failed marshaling add-entry parameters: %v", err)
+		t.Fatalf("must marshal add-entry request: %v", err)
 	}
 	return bytes.NewBuffer(data)
 }
diff --git a/instance.go b/instance.go
index 122cb67..f013153 100644
--- a/instance.go
+++ b/instance.go
@@ -6,12 +6,10 @@ import (
 	"strings"
 	"time"
 
-	"crypto/sha256"
-	"crypto/x509"
 	"net/http"
 
 	"github.com/google/trillian"
-	"github.com/system-transparency/stfe/x509util"
+	"github.com/system-transparency/stfe/namespace"
 )
 
 // Instance is an instance of a particular log front-end
@@ -23,14 +21,12 @@ type Instance struct {
 
 // LogParameters is a collection of log parameters
 type LogParameters struct {
-	LogId      []byte              // used externally by everyone
-	TreeId     int64               // used internally by Trillian
-	Prefix     string              // e.g., "test" for <base>/test
-	MaxRange   int64               // max entries per get-entries request
-	MaxChain   int64               // max submitter certificate chain length
-	AnchorPool *x509.CertPool      // for chain verification
-	AnchorList []*x509.Certificate // for access to the raw certificates
-	KeyUsage   []x509.ExtKeyUsage  // which extended key usages are accepted
+	LogId      []byte                   // used externally by everyone
+	TreeId     int64                    // used internally by Trillian
+	Prefix     string                   // e.g., "test" for <base>/test
+	MaxRange   int64                    // max entries per get-entries request
+	MaxChain   int64                    // max submitter certificate chain length
+	Namespaces *namespace.NamespacePool // trust namespaces
 	Signer     crypto.Signer
 	HashType   crypto.Hash // hash function used by Trillian
 }
@@ -52,7 +48,7 @@ func (i Instance) String() string {
 }
 
 func (lp LogParameters) String() string {
-	return fmt.Sprintf("LogId(%s) TreeId(%d) Prefix(%s) MaxRange(%d) MaxChain(%d) NumAnchors(%d)", lp.id(), lp.TreeId, lp.Prefix, lp.MaxRange, lp.MaxChain, len(lp.AnchorList))
+	return fmt.Sprintf("LogId(%s) TreeId(%d) Prefix(%s) MaxRange(%d) MaxChain(%d) NumAnchors(%d)", lp.id(), lp.TreeId, lp.Prefix, lp.MaxRange, lp.MaxChain, len(lp.Namespaces.List()))
 }
 
 func (e Endpoint) String() string {
@@ -70,34 +66,26 @@ func NewInstance(lp *LogParameters, client trillian.TrillianLogClient, deadline
 
 // NewLogParameters creates new log parameters.  Note that the signer is
 // assumed to be an ed25519 signing key.  Could be fixed at some point.
-func NewLogParameters(treeId int64, prefix string, anchors []*x509.Certificate, signer crypto.Signer, maxRange, maxChain int64) (*LogParameters, error) {
+func NewLogParameters(signer crypto.Signer, logId *namespace.Namespace, treeId int64, prefix string, namespaces *namespace.NamespacePool, maxRange int64) (*LogParameters, error) {
 	if signer == nil {
 		return nil, fmt.Errorf("need a signer but got none")
 	}
-	if len(anchors) < 1 {
-		return nil, fmt.Errorf("need at least one trust anchor")
-	}
 	if maxRange < 1 {
 		return nil, fmt.Errorf("max range must be at least one")
 	}
-	if maxChain < 1 {
-		return nil, fmt.Errorf("max chain must be at least one")
+	if len(namespaces.List()) < 1 {
+		return nil, fmt.Errorf("need at least one trusted namespace")
 	}
-	pub, err := x509.MarshalPKIXPublicKey(signer.Public())
+	lid, err := logId.Marshal()
 	if err != nil {
-		return nil, fmt.Errorf("failed DER encoding SubjectPublicKeyInfo: %v", err)
+		return nil, fmt.Errorf("failed encoding log identifier: %v", err)
 	}
-	hasher := sha256.New()
-	hasher.Write(pub)
 	return &LogParameters{
-		LogId:      hasher.Sum(nil),
+		LogId:      lid,
 		TreeId:     treeId,
 		Prefix:     prefix,
 		MaxRange:   maxRange,
-		MaxChain:   maxChain,
-		AnchorPool: x509util.NewCertPool(anchors),
-		AnchorList: anchors,
-		KeyUsage:   []x509.ExtKeyUsage{}, // placeholder, must be tested if used
+		Namespaces: namespaces,
 		Signer:     signer,
 		HashType:   crypto.SHA256, // STFE assumes RFC 6962 hashing
 	}, nil
diff --git a/instance_test.go b/instance_test.go
index a9ed7ae..3e55b5b 100644
--- a/instance_test.go
+++ b/instance_test.go
@@ -3,121 +3,110 @@ package stfe
 import (
 	"bytes"
 	"testing"
+	"time"
 
 	"crypto"
-	"crypto/sha256"
-	"crypto/x509"
+	"crypto/ed25519"
 
-	cttestdata "github.com/google/certificate-transparency-go/trillian/testdata"
-	"github.com/system-transparency/stfe/x509util"
-	"github.com/system-transparency/stfe/x509util/testdata"
+	"github.com/system-transparency/stfe/namespace"
+	"github.com/system-transparency/stfe/namespace/testdata"
 )
 
 var (
-	testHashLen     = 31
-	testMaxRange    = int64(3)
-	testMaxChain    = int64(3)
-	testTreeId      = int64(0)
-	testPrefix      = "test"
-	testHashType    = crypto.SHA256
-	testExtKeyUsage = []x509.ExtKeyUsage{}
+	testLogId          = append([]byte{0x00, 0x01, 0x20}, testdata.Ed25519Vk3...)
+	testTreeId         = int64(0)
+	testMaxRange       = int64(3)
+	testPrefix         = "test"
+	testHashType       = crypto.SHA256
+	testSignature      = make([]byte, 32)
+	testNodeHash       = make([]byte, 32)
+	testMessage        = []byte("test message")
+	testPackage        = []byte("foobar")
+	testChecksum       = make([]byte, 32)
+	testTreeSize       = uint64(128)
+	testTreeSizeLarger = uint64(256)
+	testTimestamp      = uint64(0)
+	testProof          = [][]byte{
+		testNodeHash,
+		testNodeHash,
+	}
+	testIndex    = uint64(0)
+	testHashLen  = 31
+	testDeadline = time.Second * 10
 )
 
 func TestNewLogParameters(t *testing.T) {
-	anchors, err := x509util.NewCertificateList(testdata.TrustAnchors)
-	if err != nil {
-		t.Fatalf("must decode trust anchors: %v", err)
-	}
-	signer, err := x509util.NewEd25519PrivateKey(testdata.LogPrivateKey)
-	if err != nil {
-		t.Fatalf("must decode private key: %v", err)
-	}
-	pub, err := x509.MarshalPKIXPublicKey(signer.Public())
-	if err != nil {
-		t.Fatalf("must encode public key: %v", err)
-	}
-	hasher := sha256.New()
-	hasher.Write(pub)
-	logId := hasher.Sum(nil)
+	testLogId := mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk3)
+	namespaces := mustNewNamespacePool(t, []*namespace.Namespace{
+		mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk),
+	})
+	signer := ed25519.PrivateKey(testdata.Ed25519Sk)
 	for _, table := range []struct {
 		description string
-		treeId      int64
-		prefix      string
+		logId       *namespace.Namespace
 		maxRange    int64
-		maxChain    int64
-		anchors     []*x509.Certificate
+		namespaces  *namespace.NamespacePool
 		signer      crypto.Signer
 		wantErr     bool
 	}{
 		{
 			description: "invalid signer: nil",
-			treeId:      testTreeId,
-			prefix:      testPrefix,
-			maxRange:    0,
-			maxChain:    testMaxChain,
-			anchors:     anchors,
-			signer:      nil,
-			wantErr:     true,
-		},
-		{
-			description: "no trust anchors",
-			treeId:      testTreeId,
-			prefix:      testPrefix,
+			logId:       testLogId,
 			maxRange:    testMaxRange,
-			maxChain:    testMaxChain,
-			anchors:     []*x509.Certificate{},
-			signer:      signer,
+			namespaces:  namespaces,
+			signer:      nil,
 			wantErr:     true,
 		},
 		{
 			description: "invalid max range",
-			treeId:      testTreeId,
-			prefix:      testPrefix,
+			logId:       testLogId,
 			maxRange:    0,
-			maxChain:    testMaxChain,
-			anchors:     anchors,
+			namespaces:  namespaces,
 			signer:      signer,
 			wantErr:     true,
 		},
 		{
-			description: "invalid max chain",
-			treeId:      testTreeId,
-			prefix:      testPrefix,
+			description: "no namespaces",
+			logId:       testLogId,
 			maxRange:    testMaxRange,
-			maxChain:    0,
-			anchors:     anchors,
+			namespaces:  mustNewNamespacePool(t, []*namespace.Namespace{}),
 			signer:      signer,
 			wantErr:     true,
 		},
 		{
-			description: "public key marshal failure",
-			treeId:      testTreeId,
-			prefix:      testPrefix,
-			maxRange:    testMaxRange,
-			maxChain:    testMaxChain,
-			anchors:     anchors,
-			signer:      cttestdata.NewSignerWithFixedSig("no pub", testSignature),
-			wantErr:     true,
+			description: "invalid log identifier",
+			logId: &namespace.Namespace{
+				Format: namespace.NamespaceFormatEd25519V1,
+				NamespaceEd25519V1: &namespace.NamespaceEd25519V1{
+					Namespace: make([]byte, 31), // too short
+				},
+			},
+			maxRange:   testMaxRange,
+			namespaces: namespaces,
+			signer:     signer,
+			wantErr:    true,
 		},
 		{
 			description: "valid log parameters",
-			treeId:      testTreeId,
-			prefix:      testPrefix,
+			logId:       testLogId,
 			maxRange:    testMaxRange,
-			maxChain:    testMaxChain,
-			anchors:     anchors,
+			namespaces:  namespaces,
 			signer:      signer,
 		},
 	} {
-		lp, err := NewLogParameters(table.treeId, table.prefix, table.anchors, table.signer, table.maxRange, table.maxChain)
+		lp, err := NewLogParameters(table.signer, table.logId, testTreeId, testPrefix, table.namespaces, table.maxRange)
 		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
 		}
+		lid, err := table.logId.Marshal()
+		if err != nil {
+			t.Fatalf("must marshal log id: %v", err)
+		}
 
-		if got, want := lp.LogId, logId; !bytes.Equal(got, want) {
+		if got, want := lp.LogId, lid; !bytes.Equal(got, want) {
 			t.Errorf("got log id %X but wanted %X in test %q", got, want, table.description)
 		}
 		if got, want := lp.TreeId, testTreeId; got != want {
@@ -129,18 +118,9 @@ func TestNewLogParameters(t *testing.T) {
 		if got, want := lp.MaxRange, testMaxRange; got != want {
 			t.Errorf("got max range %d but wanted %d in test %q", got, want, table.description)
 		}
-		if got, want := lp.MaxChain, testMaxChain; got != want {
-			t.Errorf("got max chain %d but wanted %d in test %q", got, want, table.description)
-		}
-		if got, want := lp.MaxChain, testMaxChain; got != want {
-			t.Errorf("got max chain %d but wanted %d in test %q", got, want, table.description)
-		}
-		if got, want := len(lp.AnchorList), len(anchors); got != want {
+		if got, want := len(lp.Namespaces.List()), len(namespaces.List()); got != want {
 			t.Errorf("got %d anchors but wanted %d in test %q", got, want, table.description)
 		}
-		if got, want := len(lp.AnchorPool.Subjects()), len(anchors); got != want {
-			t.Errorf("got %d anchors in pool but wanted %d in test %q", got, want, table.description)
-		}
 	}
 }
 
@@ -209,24 +189,48 @@ func TestEndpointPath(t *testing.T) {
 	}
 }
 
-// makeTestLogParameters makes a collection of test log parameters that
-// correspond to testLogId, testTreeId, testPrefix, testMaxRange, testMaxChain,
-// the anchors in testdata.TrustAnchors, testHashType, and an optional signer.
-func makeTestLogParameters(t *testing.T, signer crypto.Signer) *LogParameters {
-	anchors, err := x509util.NewCertificateList(testdata.TrustAnchors)
+func mustNewLogId(t *testing.T, namespace *namespace.Namespace) []byte {
+	b, err := namespace.Marshal()
+	if err != nil {
+		t.Fatalf("must marshal log id: %v", err)
+	}
+	return b
+}
+
+func mustNewNamespaceEd25519V1(t *testing.T, vk []byte) *namespace.Namespace {
+	namespace, err := namespace.NewNamespaceEd25519V1(vk)
+	if err != nil {
+		t.Fatalf("must make ed25519 namespace: %v", err)
+	}
+	return namespace
+}
+
+func mustNewNamespacePool(t *testing.T, anchors []*namespace.Namespace) *namespace.NamespacePool {
+	namespaces, err := namespace.NewNamespacePool(anchors)
 	if err != nil {
-		t.Fatalf("must decode trust anchors: %v", err)
+		t.Fatalf("must make namespaces: %v", err)
 	}
+	return namespaces
+}
+
+// makeTestLogParameters makes a collection of test log parameters.
+//
+// The log's identity is based on testdata.Ed25519{Vk3,Sk3}.  The log's accepted
+// namespaces is based on testdata.Ed25519{Vk,Vk2}.  The remaining log
+// parameters are based on the global test* variables in this file.
+//
+// For convenience the passed signer is optional (i.e., it may be nil).
+func makeTestLogParameters(t *testing.T, signer crypto.Signer) *LogParameters {
 	return &LogParameters{
-		LogId:      testLogId,
-		TreeId:     testTreeId,
-		Prefix:     testPrefix,
-		MaxRange:   testMaxRange,
-		MaxChain:   testMaxChain,
-		AnchorPool: x509util.NewCertPool(anchors),
-		AnchorList: anchors,
-		KeyUsage:   testExtKeyUsage,
-		Signer:     signer,
-		HashType:   testHashType,
+		LogId:    mustNewLogId(t, mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk3)),
+		TreeId:   testTreeId,
+		Prefix:   testPrefix,
+		MaxRange: testMaxRange,
+		Namespaces: mustNewNamespacePool(t, []*namespace.Namespace{
+			mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk),
+			mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk2),
+		}),
+		Signer:   signer,
+		HashType: testHashType,
 	}
 }
diff --git a/namespace/namespace.go b/namespace/namespace.go
index a02de6d..f5c56cf 100644
--- a/namespace/namespace.go
+++ b/namespace/namespace.go
@@ -4,10 +4,10 @@
 //
 // For example, this is how a serialized Ed25519 namespace looks like:
 //
-// 0   2                      34 (byte index)
-// +---+----------------------+
-// | 1 +   Verification key   +
-// +---+----------------------+
+// 0    2    3                  35 (byte index)
+// +----+-----------------------+
+// | 1  + 32 + Verification key +
+// +----+-----------------------+
 package namespace
 
 import (
diff --git a/namespace/testdata/data.go b/namespace/testdata/data.go
index 2cf4b11..5f3f4df 100644
--- a/namespace/testdata/data.go
+++ b/namespace/testdata/data.go
@@ -7,6 +7,12 @@ import (
 var (
 	Ed25519Vk = mustDecodeB64("HOQFUkKNWpjYAhNKTyWCzahlI7RDtf5123kHD2LACj0=")
 	Ed25519Sk = mustDecodeB64("Zaajc50Xt1tNpTj6WYkljzcVjLXL2CcQcHFT/xZqYEcc5AVSQo1amNgCE0pPJYLNqGUjtEO1/nXbeQcPYsAKPQ==")
+
+	Ed25519Vk2 = mustDecodeB64("LqrWb9JwQUTk/SwTNDdMH8aRmy3mbmhwEepO5WSgb+A=")
+	Ed25519Sk2 = mustDecodeB64("fDkSq4cWvG72yMhUyHVcZ72QKerZ66msgyVqDvfufZQuqtZv0nBBROT9LBM0N0wfxpGbLeZuaHAR6k7lZKBv4A==")
+
+	Ed25519Vk3 = mustDecodeB64("Icd1U1oY0z+5iAwgCQZyGI+pycGs6GI2rQO8gAzT7Y0=")
+	Ed25519Sk3 = mustDecodeB64("Q6uNL7VKv9flaBIXBXy/NyhNOicLYKKmfuJ6tLReMvQhx3VTWhjTP7mIDCAJBnIYj6nJwazoYjatA7yADNPtjQ==")
 )
 
 func mustDecodeB64(s string) []byte {
diff --git a/reqres.go b/reqres.go
index 14729ea..9df94e3 100644
--- a/reqres.go
+++ b/reqres.go
@@ -4,7 +4,6 @@ import (
 	"fmt"
 	"strconv"
 
-	"crypto/tls"
 	"encoding/json"
 	"io/ioutil"
 	"net/http"
@@ -14,10 +13,8 @@ import (
 
 // AddEntryRequest is a collection of add-entry input parameters
 type AddEntryRequest struct {
-	Item            []byte   `json:"item"`             // tls-serialized StItem
-	Signature       []byte   `json:"signature"`        // serialized signature using the signature scheme below
-	SignatureScheme uint16   `json:"signature_scheme"` // rfc 8446, §4.2.3
-	Chain           [][]byte `json:"chain"`            // der-encoded X.509 certificates
+	Item      []byte `json:"item"`      // tls-serialized StItem
+	Signature []byte `json:"signature"` // serialized signature using the signature scheme below
 }
 
 // GetEntriesRequest is a collection of get-entry input parameters
@@ -44,40 +41,30 @@ type GetConsistencyProofRequest struct {
 type GetEntryResponse AddEntryRequest
 
 // newAddEntryRequest parses and sanitizes the JSON-encoded add-entry
-// parameters from an incoming HTTP post.  The serialized leaf value and
-// associated appendix is returned if the submitted data is valid: well-formed,
-// signed using a supported scheme, and chains back to a valid trust anchor.
-func (lp *LogParameters) newAddEntryRequest(r *http.Request) ([]byte, []byte, error) {
+// parameters from an incoming HTTP post.  The request is returned if it is
+// a checksumV1 entry that is signed by a valid namespace.
+func (lp *LogParameters) newAddEntryRequest(r *http.Request) (*AddEntryRequest, error) {
 	var entry AddEntryRequest
 	if err := unpackJsonPost(r, &entry); err != nil {
-		return nil, nil, err
+		return nil, err
 	}
 
 	// Try decoding as ChecksumV1 StItem
 	var item StItem
 	if err := item.Unmarshal(entry.Item); err != nil {
-		return nil, nil, fmt.Errorf("StItem(%s): %v", item.Format, err)
+		return nil, fmt.Errorf("StItem(%s): %v", item.Format, err)
 	}
 	if item.Format != StFormatChecksumV1 {
-		return nil, nil, fmt.Errorf("invalid StItem format: %s", item.Format)
-	}
-
-	// Check that there is a valid trust anchor
-	chain, err := lp.buildChainFromDerList(entry.Chain)
-	if err != nil {
-		return nil, nil, fmt.Errorf("invalid certificate chain: %v", err)
-	}
-
-	// Check that there is a valid signature
-	if err := lp.verifySignature(chain[0], tls.SignatureScheme(entry.SignatureScheme), entry.Item, entry.Signature); err != nil {
-		return nil, nil, fmt.Errorf("invalid signature: %v", err)
+		return nil, fmt.Errorf("invalid StItem format: %s", item.Format)
 	}
 
-	extra, err := NewAppendix(chain, entry.Signature, entry.SignatureScheme).Marshal()
-	if err != nil {
-		return nil, nil, fmt.Errorf("failed marshaling appendix: %v", err)
+	// Check that namespace is valid for item
+	if namespace, ok := lp.Namespaces.Find(&item.ChecksumV1.Namespace); !ok {
+		return nil, fmt.Errorf("unknown namespace: %s", item.ChecksumV1.Namespace.String())
+	} else if err := namespace.Verify(entry.Item, entry.Signature); err != nil {
+		return nil, fmt.Errorf("invalid namespace: %v", err)
 	}
-	return entry.Item, extra, nil
+	return &entry, nil
 }
 
 // newGetEntriesRequest parses and sanitizes the URL-encoded get-entries
@@ -149,15 +136,7 @@ func (lp *LogParameters) newGetConsistencyProofRequest(httpRequest *http.Request
 
 // newGetEntryResponse assembles a log entry and its appendix
 func (lp *LogParameters) newGetEntryResponse(leaf, appendix []byte) (*GetEntryResponse, error) {
-	var app Appendix
-	if err := app.Unmarshal(appendix); err != nil {
-		return nil, err
-	}
-	chain := make([][]byte, 0, len(app.Chain))
-	for _, c := range app.Chain {
-		chain = append(chain, c.Data)
-	}
-	return &GetEntryResponse{leaf, app.Signature, app.SignatureScheme, chain}, nil
+	return &GetEntryResponse{leaf, appendix}, nil // TODO: remove me
 }
 
 // newGetEntriesResponse assembles a get-entries response
@@ -175,11 +154,16 @@ func (lp *LogParameters) newGetEntriesResponse(leaves []*trillian.LogLeaf) ([]*G
 
 // newGetAnchorsResponse assembles a get-anchors response
 func (lp *LogParameters) newGetAnchorsResponse() [][]byte {
-	certificates := make([][]byte, 0, len(lp.AnchorList))
-	for _, certificate := range lp.AnchorList {
-		certificates = append(certificates, certificate.Raw)
+	namespaces := make([][]byte, 0, len(lp.Namespaces.List()))
+	for _, namespace := range lp.Namespaces.List() {
+		raw, err := namespace.Marshal()
+		if err != nil {
+			fmt.Printf("TODO: fix me and entire func\n")
+			continue
+		}
+		namespaces = append(namespaces, raw)
 	}
-	return certificates
+	return namespaces
 }
 
 // unpackJsonPost unpacks a json-encoded HTTP POST request into `unpack`
diff --git a/reqres_test.go b/reqres_test.go
index 3574750..fab0e29 100644
--- a/reqres_test.go
+++ b/reqres_test.go
@@ -6,11 +6,8 @@ import (
 	"strconv"
 	"testing"
 
-	"crypto/x509"
 	"net/http"
-
-	"github.com/google/trillian"
-	"github.com/system-transparency/stfe/x509util/testdata"
+	//	"github.com/google/trillian"
 )
 
 // TODO: TestNewAddEntryRequest
@@ -228,78 +225,81 @@ func TestNewGetConsistencyProofRequest(t *testing.T) {
 	}
 }
 
+// TODO: refactor TestNewGetEntryResponse
 func TestNewGetEntryResponse(t *testing.T) {
-	lp := makeTestLogParameters(t, nil)
+	//lp := makeTestLogParameters(t, nil)
 
-	var appendix Appendix
-	leaf, app := makeTestLeaf(t, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey)
-	if err := appendix.Unmarshal(app); err != nil {
-		t.Fatalf("must unmarshal appendix: %v", err)
-	}
-	if _, err := lp.newGetEntryResponse(leaf, app[1:]); err == nil {
-		t.Errorf("got no error invalid appendix")
-	}
+	//var appendix Appendix
+	//leaf, app := makeTestLeaf(t, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey)
+	//if err := appendix.Unmarshal(app); err != nil {
+	//	t.Fatalf("must unmarshal appendix: %v", err)
+	//}
+	//if _, err := lp.newGetEntryResponse(leaf, app[1:]); err == nil {
+	//	t.Errorf("got no error invalid appendix")
+	//}
 
-	// Valid response
-	rsp, err := lp.newGetEntryResponse(leaf, app)
-	if err != nil {
-		t.Errorf("got error %v but wanted none", err)
-		return
-	}
-	if got, want := rsp.Item, leaf; !bytes.Equal(got, want) {
-		t.Errorf("got leaf %X but wanted %X", got, want)
-	}
-	if got, want := rsp.Signature, appendix.Signature; !bytes.Equal(got, want) {
-		t.Errorf("got signature %X but wanted %X", got, want)
-	}
-	if got, want := rsp.SignatureScheme, appendix.SignatureScheme; got != want {
-		t.Errorf("got signature scheme %d but wanted %d", got, want)
-	}
-	if got, want := len(rsp.Chain), len(appendix.Chain); got != want {
-		t.Errorf("got chain length %d but wanted %d", got, want)
-	}
-	for i, n := 0, len(rsp.Chain); i < n; i++ {
-		if got, want := rsp.Chain[i], appendix.Chain[i].Data; !bytes.Equal(got, want) {
-			t.Errorf("got chain[%d]=%X but wanted %X", i, got, want)
-		}
-	}
+	//// Valid response
+	//rsp, err := lp.newGetEntryResponse(leaf, app)
+	//if err != nil {
+	//	t.Errorf("got error %v but wanted none", err)
+	//	return
+	//}
+	//if got, want := rsp.Item, leaf; !bytes.Equal(got, want) {
+	//	t.Errorf("got leaf %X but wanted %X", got, want)
+	//}
+	//if got, want := rsp.Signature, appendix.Signature; !bytes.Equal(got, want) {
+	//	t.Errorf("got signature %X but wanted %X", got, want)
+	//}
+	//if got, want := rsp.SignatureScheme, appendix.SignatureScheme; got != want {
+	//	t.Errorf("got signature scheme %d but wanted %d", got, want)
+	//}
+	//if got, want := len(rsp.Chain), len(appendix.Chain); got != want {
+	//	t.Errorf("got chain length %d but wanted %d", got, want)
+	//}
+	//for i, n := 0, len(rsp.Chain); i < n; i++ {
+	//	if got, want := rsp.Chain[i], appendix.Chain[i].Data; !bytes.Equal(got, want) {
+	//		t.Errorf("got chain[%d]=%X but wanted %X", i, got, want)
+	//	}
+	//}
 }
 
+// TODO: refactor TestNewGetEntriesResponse
 func TestNewGetEntriesResponse(t *testing.T) {
-	lp := makeTestLogParameters(t, nil)
+	//lp := makeTestLogParameters(t, nil)
 
-	// Invalid
-	leaf := makeTrillianQueueLeafResponse(t, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, false).QueuedLeaf.Leaf
-	leaf.ExtraData = leaf.ExtraData[1:]
-	if _, err := lp.newGetEntriesResponse([]*trillian.LogLeaf{leaf}); err == nil {
-		t.Errorf("got no error for invalid appendix")
-	}
+	//// Invalid
+	//leaf := makeTrillianQueueLeafResponse(t, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, false).QueuedLeaf.Leaf
+	//leaf.ExtraData = leaf.ExtraData[1:]
+	//if _, err := lp.newGetEntriesResponse([]*trillian.LogLeaf{leaf}); err == nil {
+	//	t.Errorf("got no error for invalid appendix")
+	//}
 
-	// Valid, including empty
-	for n, numEntries := 0, 5; n < numEntries; n++ {
-		leaves := make([]*trillian.LogLeaf, 0, n)
-		for i := 0; i < n; i++ {
-			leaves = append(leaves, makeTrillianQueueLeafResponse(t, []byte(fmt.Sprintf("%s-%d", testPackage, i)), testdata.RootChain, testdata.EndEntityPrivateKey, false).QueuedLeaf.Leaf)
-		}
-		if rsp, err := lp.newGetEntriesResponse(leaves); err != nil {
-			t.Errorf("got error for %d valid leaves: %v", n, err)
-		} else if got, want := len(rsp), n; got != want {
-			t.Errorf("got %d leaves but wanted %d", got, want)
-		}
-		// note that we tested actual leaf contents in TestNewGetEntryResponse
-	}
+	//// Valid, including empty
+	//for n, numEntries := 0, 5; n < numEntries; n++ {
+	//	leaves := make([]*trillian.LogLeaf, 0, n)
+	//	for i := 0; i < n; i++ {
+	//		leaves = append(leaves, makeTrillianQueueLeafResponse(t, []byte(fmt.Sprintf("%s-%d", testPackage, i)), testdata.RootChain, testdata.EndEntityPrivateKey, false).QueuedLeaf.Leaf)
+	//	}
+	//	if rsp, err := lp.newGetEntriesResponse(leaves); err != nil {
+	//		t.Errorf("got error for %d valid leaves: %v", n, err)
+	//	} else if got, want := len(rsp), n; got != want {
+	//		t.Errorf("got %d leaves but wanted %d", got, want)
+	//	}
+	//	// note that we tested actual leaf contents in TestNewGetEntryResponse
+	//}
 }
 
+// TODO: refactor TestNewGetAnchorsResponse
 func TestNewGetAnchorsResponse(t *testing.T) {
-	rawAnchors := makeTestLogParameters(t, nil).newGetAnchorsResponse()
-	if got, want := len(rawAnchors), testdata.NumTrustAnchors; got != want {
-		t.Errorf("got %d anchors but wanted %d", got, want)
-	}
-	for _, rawAnchor := range rawAnchors {
-		if _, err := x509.ParseCertificate(rawAnchor); err != nil {
-			t.Errorf("invalid trust anchor %X: %v", rawAnchor, err)
-		}
-	}
+	//rawAnchors := makeTestLogParameters(t, nil).newGetAnchorsResponse()
+	//if got, want := len(rawAnchors), testdata.NumTrustAnchors; got != want {
+	//	t.Errorf("got %d anchors but wanted %d", got, want)
+	//}
+	//for _, rawAnchor := range rawAnchors {
+	//	if _, err := x509.ParseCertificate(rawAnchor); err != nil {
+	//		t.Errorf("invalid trust anchor %X: %v", rawAnchor, err)
+	//	}
+	//}
 }
 
 func mustParseInt64(t *testing.T, num string) int64 {
diff --git a/trillian_test.go b/trillian_test.go
index 179d03c..b3c1653 100644
--- a/trillian_test.go
+++ b/trillian_test.go
@@ -6,10 +6,10 @@ import (
 
 	"github.com/google/trillian"
 	"github.com/google/trillian/types"
-	"github.com/system-transparency/stfe/x509util/testdata"
-
 	"google.golang.org/grpc/codes"
 	"google.golang.org/grpc/status"
+
+	"github.com/system-transparency/stfe/namespace/testdata"
 )
 
 func TestCheckQueueLeaf(t *testing.T) {
@@ -35,11 +35,11 @@ func TestCheckQueueLeaf(t *testing.T) {
 		},
 		{
 			description: "ok response: duplicate leaf",
-			rsp:         makeTrillianQueueLeafResponse(t, testPackage, testdata.IntermediateChain, testdata.EndEntityPrivateKey, true),
+			rsp:         makeTrillianQueueLeafResponse(t, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk, true),
 		},
 		{
 			description: "ok response: new leaf",
-			rsp:         makeTrillianQueueLeafResponse(t, testPackage, testdata.IntermediateChain, testdata.EndEntityPrivateKey, false),
+			rsp:         makeTrillianQueueLeafResponse(t, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk, false),
 		},
 	} {
 		if err := checkQueueLeaf(table.rsp, table.err); (err != nil) != table.wantErr {
@@ -73,7 +73,7 @@ func TestCheckGetLeavesByRange(t *testing.T) {
 			rsp: func(rsp *trillian.GetLeavesByRangeResponse) *trillian.GetLeavesByRangeResponse {
 				rsp.Leaves = nil
 				return rsp
-			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true)),
+			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk)),
 			wantErr: true,
 		},
 		{
@@ -82,7 +82,7 @@ func TestCheckGetLeavesByRange(t *testing.T) {
 			rsp: func(rsp *trillian.GetLeavesByRangeResponse) *trillian.GetLeavesByRangeResponse {
 				rsp.SignedLogRoot = nil
 				return rsp
-			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true)),
+			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk)),
 			wantErr: true,
 		},
 		{
@@ -91,7 +91,7 @@ func TestCheckGetLeavesByRange(t *testing.T) {
 			rsp: func(rsp *trillian.GetLeavesByRangeResponse) *trillian.GetLeavesByRangeResponse {
 				rsp.SignedLogRoot.LogRoot = nil
 				return rsp
-			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true)),
+			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk)),
 			wantErr: true,
 		},
 		{
@@ -100,13 +100,13 @@ func TestCheckGetLeavesByRange(t *testing.T) {
 			rsp: func(rsp *trillian.GetLeavesByRangeResponse) *trillian.GetLeavesByRangeResponse {
 				rsp.SignedLogRoot.LogRoot = rsp.SignedLogRoot.LogRoot[1:]
 				return rsp
-			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true)),
+			}(makeTrillianGetLeavesByRangeResponse(t, 0, 1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk)),
 			wantErr: true,
 		},
 		{
 			description: "bad response: too many leaves",
 			req:         &GetEntriesRequest{Start: 0, End: 1},
-			rsp:         makeTrillianGetLeavesByRangeResponse(t, 0, 2, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true),
+			rsp:         makeTrillianGetLeavesByRangeResponse(t, 0, 2, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk),
 			wantErr:     true,
 		},
 		{
@@ -115,13 +115,13 @@ func TestCheckGetLeavesByRange(t *testing.T) {
 			rsp: func(rsp *trillian.GetLeavesByRangeResponse) *trillian.GetLeavesByRangeResponse {
 				rsp.SignedLogRoot = makeLatestSignedLogRootResponse(t, 0, testTreeSize, testNodeHash).SignedLogRoot
 				return rsp
-			}(makeTrillianGetLeavesByRangeResponse(t, int64(testTreeSize)-1, int64(testTreeSize)-1, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true)),
+			}(makeTrillianGetLeavesByRangeResponse(t, int64(testTreeSize)-1, int64(testTreeSize)-1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk)),
 			wantErr: true,
 		},
 		{
 			description: "bad response: invalid leaf indices",
 			req:         &GetEntriesRequest{Start: 10, End: 11},
-			rsp:         makeTrillianGetLeavesByRangeResponse(t, 11, 12, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true),
+			rsp:         makeTrillianGetLeavesByRangeResponse(t, 11, 12, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk),
 			wantErr:     true,
 		},
 		{
@@ -130,12 +130,12 @@ func TestCheckGetLeavesByRange(t *testing.T) {
 			rsp: func(rsp *trillian.GetLeavesByRangeResponse) *trillian.GetLeavesByRangeResponse {
 				rsp.SignedLogRoot = makeLatestSignedLogRootResponse(t, 0, testTreeSize, testNodeHash).SignedLogRoot
 				return rsp
-			}(makeTrillianGetLeavesByRangeResponse(t, int64(testTreeSize)-1, int64(testTreeSize)-1, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true)),
+			}(makeTrillianGetLeavesByRangeResponse(t, int64(testTreeSize)-1, int64(testTreeSize)-1, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk)),
 		},
 		{
 			description: "ok response: a bunch of leaves",
 			req:         &GetEntriesRequest{Start: 10, End: 20},
-			rsp:         makeTrillianGetLeavesByRangeResponse(t, 10, 20, testPackage, testdata.RootChain, testdata.EndEntityPrivateKey, true),
+			rsp:         makeTrillianGetLeavesByRangeResponse(t, 10, 20, testPackage, testdata.Ed25519Vk, testdata.Ed25519Sk),
 		},
 	} {
 		if _, err := checkGetLeavesByRange(table.req, table.rsp, table.err); (err != nil) != table.wantErr {
@@ -284,13 +284,13 @@ func TestCheckGetLatestSignedLogRoot(t *testing.T) {
 }
 
 // makeTrillianQueueLeafResponse creates a valid trillian QueueLeafResponse
-// for a package `name` where the checksum is all zeros (32 bytes).  The pemKey
-// is a PEM-encoded ed25519 signing key, and pemChain its certificate chain.
+// for a package `name` where the checksum is all zeros (32 bytes).  Namespace
+// is based on vk and sk (ed25519).
 //
 // Note: MerkleLeafHash and LeafIdentityHash are unset (not used by stfe).
-func makeTrillianQueueLeafResponse(t *testing.T, name, pemChain, pemKey []byte, dupCode bool) *trillian.QueueLeafResponse {
+func makeTrillianQueueLeafResponse(t *testing.T, name, vk, sk []byte, dupCode bool) *trillian.QueueLeafResponse {
 	t.Helper()
-	leaf, appendix := makeTestLeaf(t, name, pemChain, pemKey)
+	leaf, signature := mustMakeEd25519ChecksumV1(t, name, make([]byte, 32), vk, sk)
 	s := status.New(codes.OK, "ok").Proto()
 	if dupCode {
 		s = status.New(codes.AlreadyExists, "duplicate").Proto()
@@ -300,7 +300,7 @@ func makeTrillianQueueLeafResponse(t *testing.T, name, pemChain, pemKey []byte,
 			Leaf: &trillian.LogLeaf{
 				MerkleLeafHash:   nil, // not used by stfe
 				LeafValue:        leaf,
-				ExtraData:        appendix,
+				ExtraData:        signature,
 				LeafIndex:        0,   // not applicable (log is not pre-ordered)
 				LeafIdentityHash: nil, // not used by stfe
 			},
@@ -343,22 +343,18 @@ func makeTrillianGetConsistencyProofResponse(t *testing.T, path [][]byte) *trill
 
 // makeTrillianGetLeavesByRangeResponse creates a range of leaves [start,end]
 // such that the package is `name`_<index> and the checksum is all zeros (32
-// bytes).  The pemKey is a PEM-encoded ed25519 signing key, and pemChain its
-// certificate chain.  Set `valid` to false to make an invalid Appendix.
+// bytes).  An Ed25519 namespace is used based on vk and sk.
 //
 // Note: MerkleLeafHash and LeafIdentityHash are unset (not used by stfe).
-func makeTrillianGetLeavesByRangeResponse(t *testing.T, start, end int64, name, pemChain, pemKey []byte, valid bool) *trillian.GetLeavesByRangeResponse {
+func makeTrillianGetLeavesByRangeResponse(t *testing.T, start, end int64, name, vk, sk []byte) *trillian.GetLeavesByRangeResponse {
 	t.Helper()
 	leaves := make([]*trillian.LogLeaf, 0, end-start+1)
 	for i, n := start, end+1; i < n; i++ {
-		leaf, appendix := makeTestLeaf(t, append(name, []byte(fmt.Sprintf("_%d", i))...), pemChain, pemKey)
-		if !valid {
-			appendix = []byte{0, 1, 2, 3}
-		}
+		leaf, signature := mustMakeEd25519ChecksumV1(t, append(name, []byte(fmt.Sprintf("_%d", i))...), make([]byte, 32), vk, sk)
 		leaves = append(leaves, &trillian.LogLeaf{
 			MerkleLeafHash:   nil,
 			LeafValue:        leaf,
-			ExtraData:        appendix,
+			ExtraData:        signature,
 			LeafIndex:        i,
 			LeafIdentityHash: nil,
 		})
diff --git a/type.go b/type.go
index 90dff85..18a613c 100644
--- a/type.go
+++ b/type.go
@@ -4,11 +4,11 @@ import (
 	"fmt"
 	"time"
 
-	"crypto/x509"
 	"encoding/base64"
 
 	"github.com/google/certificate-transparency-go/tls"
 	"github.com/google/trillian/types"
+	"github.com/system-transparency/stfe/namespace"
 )
 
 // StFormat defines a particular StItem type that is versioned
@@ -35,7 +35,7 @@ type StItem struct {
 
 // SignedTreeHeadV1 is a signed tree head as defined by RFC 6962/bis, §4.10
 type SignedTreeHeadV1 struct {
-	LogId     []byte `tls:"minlen:32,maxlen:32"`
+	LogId     []byte `tls:"minlen:35,maxlen:35"`
 	TreeHead  TreeHeadV1
 	Signature []byte `tls:"minlen:1,maxlen:65535"`
 }
@@ -43,14 +43,14 @@ type SignedTreeHeadV1 struct {
 // SignedDebugInfoV1 is a signed statement that we intend (but do not promise)
 // to insert an entry into the log as defined by markdown/api.md
 type SignedDebugInfoV1 struct {
-	LogId     []byte `tls:"minlen:32,maxlen:32"`
+	LogId     []byte `tls:"minlen:35,maxlen:35"`
 	Message   []byte `tls:"minlen:0,maxlen:65535"`
 	Signature []byte `tls:"minlen:1,maxlen:65535"`
 }
 
 // ConsistencyProofV1 is a consistency proof as defined by RFC 6962/bis, §4.11
 type ConsistencyProofV1 struct {
-	LogId           []byte `tls:"minlen:32,maxlen:32"`
+	LogId           []byte `tls:"minlen:35,maxlen:35"`
 	TreeSize1       uint64
 	TreeSize2       uint64
 	ConsistencyPath []NodeHash `tls:"minlen:0,maxlen:65535"`
@@ -58,7 +58,7 @@ type ConsistencyProofV1 struct {
 
 // InclusionProofV1 is an inclusion proof as defined by RFC 6962/bis, §4.12
 type InclusionProofV1 struct {
-	LogId         []byte `tls:"minlen:32,maxlen:32"`
+	LogId         []byte `tls:"minlen:35,maxlen:35"`
 	TreeSize      uint64
 	LeafIndex     uint64
 	InclusionPath []NodeHash `tls:"minlen:0,maxlen:65535"`
@@ -66,9 +66,9 @@ type InclusionProofV1 struct {
 
 // ChecksumV1 associates a leaf type as defined by markdown/api.md
 type ChecksumV1 struct {
-	// TODO: refactor package as `Namespace`, s.t., start is sha256(anchor pub)
-	Package  []byte `tls:"minlen:1,maxlen:255"`
-	Checksum []byte `tls:"minlen:1,maxlen:64"`
+	Package   []byte `tls:"minlen:1,maxlen:255"`
+	Checksum  []byte `tls:"minlen:1,maxlen:64"`
+	Namespace namespace.Namespace
 }
 
 // TreeHeadV1 is a tree head as defined by RFC 6962/bis, §4.10
@@ -89,13 +89,6 @@ type RawCertificate struct {
 	Data []byte `tls:"minlen:0,maxlen:65535"`
 }
 
-// Appendix is extra leaf data that is not stored in the log's Merkle tree
-type Appendix struct {
-	Signature       []byte `tls:"minlen:1,maxlen:16383"`
-	SignatureScheme uint16
-	Chain           []RawCertificate `tls:"minlen:1,maxlen:65535"`
-}
-
 func (f StFormat) String() string {
 	switch f {
 	case StFormatReserved:
@@ -149,7 +142,7 @@ func (i InclusionProofV1) String() string {
 }
 
 func (i ChecksumV1) String() string {
-	return fmt.Sprintf("Package(%s) Checksum(%s)", string(i.Package), b64(i.Checksum))
+	return fmt.Sprintf("Package(%s) Checksum(%s) Namespace(%s)", string(i.Package), string(i.Checksum), i.Namespace.String())
 }
 
 func (th TreeHeadV1) String() string {
@@ -194,26 +187,6 @@ func (i *StItem) UnmarshalB64(s string) error {
 	return i.Unmarshal(serialized)
 }
 
-// Marshal serializes an Appendix as defined by RFC 5246
-func (a *Appendix) Marshal() ([]byte, error) {
-	serialized, err := tls.Marshal(*a)
-	if err != nil {
-		return nil, fmt.Errorf("marshal failed for Appendix(%v): %v", a, err)
-	}
-	return serialized, nil
-}
-
-// Unmarshal unpacks a serialized Appendix
-func (a *Appendix) Unmarshal(serialized []byte) error {
-	extra, err := tls.Unmarshal(serialized, a)
-	if err != nil {
-		return fmt.Errorf("unmarshal failed for Appendix(%v): %v", a, err)
-	} else if len(extra) > 0 {
-		return fmt.Errorf("unmarshal found extra data for Appendix(%v): %v", a, extra)
-	}
-	return nil
-}
-
 // Marshal serializes a TreeHeadV1 as defined by RFC 5246
 func (th *TreeHeadV1) Marshal() ([]byte, error) {
 	serialized, err := tls.Marshal(*th)
@@ -273,10 +246,10 @@ func NewConsistencyProofV1(logId []byte, first, second uint64, proof [][]byte) *
 }
 
 // NewChecksumV1 creates a new StItem of type checksum_v1
-func NewChecksumV1(identifier []byte, checksum []byte) *StItem {
+func NewChecksumV1(identifier, checksum []byte, namespace *namespace.Namespace) *StItem {
 	return &StItem{
 		Format:     StFormatChecksumV1,
-		ChecksumV1: &ChecksumV1{identifier, checksum},
+		ChecksumV1: &ChecksumV1{identifier, checksum, *namespace},
 	}
 }
 
@@ -291,15 +264,6 @@ func NewTreeHeadV1(lr *types.LogRootV1) *TreeHeadV1 {
 	}
 }
 
-// NewAppendix creates a new leaf Appendix for an X.509 chain and signature
-func NewAppendix(x509Chain []*x509.Certificate, signature []byte, signatureScheme uint16) *Appendix {
-	chain := make([]RawCertificate, 0, len(x509Chain))
-	for _, c := range x509Chain {
-		chain = append(chain, RawCertificate{c.Raw})
-	}
-	return &Appendix{signature, signatureScheme, chain}
-}
-
 func b64(b []byte) string {
 	return base64.StdEncoding.EncodeToString(b)
 }
diff --git a/type_test.go b/type_test.go
index abfc280..2e0f4b6 100644
--- a/type_test.go
+++ b/type_test.go
@@ -3,28 +3,7 @@ package stfe
 import (
 	"testing"
 
-	"crypto/tls"
-
-	"github.com/system-transparency/stfe/x509util"
-	"github.com/system-transparency/stfe/x509util/testdata"
-)
-
-var (
-	testLogId          = make([]byte, 32)
-	testSignature      = make([]byte, 32)
-	testNodeHash       = make([]byte, 32)
-	testMessage        = []byte("test message")
-	testPackage        = []byte("foobar")
-	testChecksum       = make([]byte, 32)
-	testTreeSize       = uint64(128)
-	testTreeSizeLarger = uint64(256)
-	testTimestamp      = uint64(0)
-	testProof          = [][]byte{
-		testNodeHash,
-		testNodeHash,
-	}
-	testIndex           = uint64(0)
-	testSignatureScheme = tls.Ed25519
+	"github.com/system-transparency/stfe/namespace/testdata"
 )
 
 // TestEncDecStItem tests that valid StItems can be (un)marshaled, and that
@@ -33,7 +12,7 @@ var (
 // Note: max limits for inclusion and consistency proofs are not tested.
 // Note: TreeHeadV1 extensions are not tested (not used by stfe)
 func TestEncDecStItem(t *testing.T) {
-	logIdSize := 32
+	logIdSize := 35
 	signatureMin := 1
 	signatureMax := 65535
 	messageMax := 65535
@@ -218,39 +197,39 @@ func TestEncDecStItem(t *testing.T) {
 		// checksum_v1
 		{
 			description: "too short package",
-			item:        NewChecksumV1(make([]byte, packageMin-1), testChecksum),
+			item:        NewChecksumV1(make([]byte, packageMin-1), testChecksum, mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 			wantErr:     true,
 		},
 		{
 			description: "too large package",
-			item:        NewChecksumV1(make([]byte, packageMax+1), testChecksum),
+			item:        NewChecksumV1(make([]byte, packageMax+1), testChecksum, mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 			wantErr:     true,
 		},
 		{
 			description: "ok package: min",
-			item:        NewChecksumV1(make([]byte, packageMin), testChecksum),
+			item:        NewChecksumV1(make([]byte, packageMin), testChecksum, mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 		},
 		{
 			description: "ok package: max",
-			item:        NewChecksumV1(make([]byte, packageMax), testChecksum),
+			item:        NewChecksumV1(make([]byte, packageMax), testChecksum, mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 		},
 		{
 			description: "too short checksum",
-			item:        NewChecksumV1(testPackage, make([]byte, checksumMin-1)),
+			item:        NewChecksumV1(testPackage, make([]byte, checksumMin-1), mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 			wantErr:     true,
 		},
 		{
 			description: "too large checksum",
-			item:        NewChecksumV1(testPackage, make([]byte, checksumMax+1)),
+			item:        NewChecksumV1(testPackage, make([]byte, checksumMax+1), mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 			wantErr:     true,
-		},
+		}, // namespace (un)marshal is already tested in its own package (skip)
 		{
 			description: "ok checksum: min",
-			item:        NewChecksumV1(testPackage, make([]byte, checksumMin)),
+			item:        NewChecksumV1(testPackage, make([]byte, checksumMin), mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 		},
 		{
 			description: "ok checksum: max",
-			item:        NewChecksumV1(testPackage, make([]byte, checksumMax)),
+			item:        NewChecksumV1(testPackage, make([]byte, checksumMax), mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)),
 		},
 	} {
 		b, err := table.item.MarshalB64()
@@ -270,64 +249,6 @@ func TestEncDecStItem(t *testing.T) {
 	}
 }
 
-// TestEncDecAppendix tests that valid appendices can be (un)marshaled, and that
-// invalid ones in fact dail.
-//
-// Note: max limits for certificate chains are not tested.
-func TestEncDecAppendix(t *testing.T) {
-	chain, err := x509util.NewCertificateList(testdata.RootChain)
-	if err != nil {
-		t.Fatalf("must decode certificate chain: %v", err)
-	}
-
-	signatureMin := 1
-	signatureMax := 16383
-	for _, table := range []struct {
-		description string
-		appendix    *Appendix
-		wantErr     bool
-	}{
-		{
-			description: "too short signature",
-			appendix:    NewAppendix(chain, make([]byte, signatureMin-1), uint16(testSignatureScheme)),
-			wantErr:     true,
-		},
-		{
-			description: "too large signature",
-			appendix:    NewAppendix(chain, make([]byte, signatureMax+1), uint16(testSignatureScheme)),
-			wantErr:     true,
-		},
-		{
-			description: "ok signature: min",
-			appendix:    NewAppendix(chain, make([]byte, signatureMin), uint16(testSignatureScheme)),
-		},
-		{
-			description: "ok signature: max",
-			appendix:    NewAppendix(chain, make([]byte, signatureMax), uint16(testSignatureScheme)),
-		},
-		{
-			description: "too short chain",
-			appendix:    NewAppendix(nil, testSignature, uint16(testSignatureScheme)),
-			wantErr:     true,
-		},
-	} {
-		b, err := table.appendix.Marshal()
-		if err != nil && !table.wantErr {
-			t.Errorf("failed marshaling Appendix for %q: %v", table.description, err)
-		} else if err == nil && table.wantErr {
-			t.Errorf("succeeded marshaling Appendix but wanted error for %q", table.description)
-		}
-		if err != nil || table.wantErr {
-			continue // nothing to unmarshal
-		}
-
-		var appendix Appendix
-		if err := appendix.Unmarshal(b); err != nil {
-			t.Errorf("failed unmarshaling Appendix: %v", err)
-		}
-	}
-}
-
 // TestTreeHeadMarshal tests that valid tree heads can be marshaled and that
 // invalid ones cannot.
 //
@@ -369,7 +290,7 @@ func TestTreeHeadMarshal(t *testing.T) {
 
 // TestStItemUnmarshal tests that invalid ST items cannot be unmarshaled
 func TestStItemUnmarshalFailure(t *testing.T) {
-	b, err := NewChecksumV1(testPackage, testChecksum).Marshal()
+	b, err := NewChecksumV1(testPackage, testChecksum, mustNewNamespaceEd25519V1(t, testdata.Ed25519Vk)).Marshal()
 	if err != nil {
 		t.Errorf("must marshal ChecksumV1 StItem: %v", err)
 		return
@@ -395,31 +316,3 @@ func TestStItemUnmarshalFailure(t *testing.T) {
 		t.Errorf("succeded unmarshaling base64 but wanted error: bad byte")
 	}
 }
-
-// TestAppendixUnmarshal tests that invalid appendices cannot be unmarshaled
-func TestAppendixUnmarshalFailure(t *testing.T) {
-	chain, err := x509util.NewCertificateList(testdata.RootChain)
-	if err != nil {
-		t.Fatalf("must decode certificate chain: %v", err)
-	}
-	b, err := NewAppendix(chain, testSignature, uint16(testSignatureScheme)).Marshal()
-	if err != nil {
-		t.Fatalf("must marshal Appendix: %v", err)
-	}
-
-	var appendix Appendix
-	if err := appendix.Unmarshal(append(b[:], []byte{0}...)); err == nil {
-		t.Errorf("succeeded unmarshaling but wanted error: one extra byte")
-	}
-	if err := appendix.Unmarshal(append(b[:], b[:]...)); err == nil {
-		t.Errorf("succeeded unmarshaling but wanted error: one extra item")
-	}
-	if err := appendix.Unmarshal([]byte{0}); err == nil {
-		t.Errorf("succeeded unmarshaling but wanted error: just a single byte")
-	}
-
-	b[0] = byte(len(testSignature)) + 1 // will mess up the first length specifier
-	if err := appendix.Unmarshal(b); err == nil {
-		t.Errorf("succeeded unmarshaling but wanted error: bad length")
-	}
-}
diff --git a/x509util/README.md b/x509util/README.md
new file mode 100644
index 0000000..3eaecaa
--- /dev/null
+++ b/x509util/README.md
@@ -0,0 +1,2 @@
+# x509util
+TODO: remove package