notary/internal/note: signed note formats, keys, and operations

This is part of a design sketch for a Go module notary.
Eventually the code will live outside golang.org/x/exp.

Everything here is subject to change! Don't depend on it!

This CL implements a simple text format for the notary's
signed tree hashes.

Change-Id: I0d08e0943b3e2b83eace7baa059d4a05c5a330a5
Reviewed-on: https://go-review.googlesource.com/c/exp/+/156324
Run-TryBot: Russ Cox <rsc@golang.org>
Reviewed-by: Filippo Valsorda <filippo@golang.org>
diff --git a/notary/go.mod b/notary/go.mod
new file mode 100644
index 0000000..4b4d966
--- /dev/null
+++ b/notary/go.mod
@@ -0,0 +1,5 @@
+module golang.org/x/exp/notary
+
+go 1.13
+
+require golang.org/x/crypto v0.0.0-20190313024323-a1f597ede03a
diff --git a/notary/go.sum b/notary/go.sum
new file mode 100644
index 0000000..6dea69e
--- /dev/null
+++ b/notary/go.sum
@@ -0,0 +1,3 @@
+golang.org/x/crypto v0.0.0-20190313024323-a1f597ede03a h1:YX8ljsm6wXlHZO+aRz9Exqr0evNhKRNe5K/gi+zKh4U=
+golang.org/x/crypto v0.0.0-20190313024323-a1f597ede03a/go.mod h1:djNgcEr1/C05ACkg1iLfiJU5Ep61QUkGW8qpdssI0+w=
+golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
diff --git a/notary/internal/note/example_test.go b/notary/internal/note/example_test.go
new file mode 100644
index 0000000..d715ea4
--- /dev/null
+++ b/notary/internal/note/example_test.go
@@ -0,0 +1,128 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package note_test
+
+import (
+	"fmt"
+	"io"
+	"os"
+
+	"golang.org/x/exp/notary/internal/note"
+)
+
+func ExampleSign() {
+	skey := "PRIVATE+KEY+PeterNeumann+c74f20a3+AYEKFALVFGyNhPJEMzD1QIDr+Y7hfZx09iUvxdXHKDFz"
+	text := "If you think cryptography is the answer to your problem,\n" +
+		"then you don't know what your problem is.\n"
+
+	signer, err := note.NewSigner(skey)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+
+	msg, err := note.Sign(&note.Note{Text: text}, signer)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+	os.Stdout.Write(msg)
+
+	// Output:
+	// If you think cryptography is the answer to your problem,
+	// then you don't know what your problem is.
+	//
+	// — PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=
+}
+
+func ExampleOpen() {
+	vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+	msg := []byte("If you think cryptography is the answer to your problem,\n" +
+		"then you don't know what your problem is.\n" +
+		"\n" +
+		"— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n")
+
+	verifier, err := note.NewVerifier(vkey)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+	notaries := note.NotaryList(verifier)
+
+	n, err := note.Open(msg, notaries)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+	fmt.Printf("%s (%08x):\n%s", n.Sigs[0].Name, n.Sigs[0].Hash, n.Text)
+
+	// Output:
+	// PeterNeumann (c74f20a3):
+	// If you think cryptography is the answer to your problem,
+	// then you don't know what your problem is.
+}
+
+var rand = struct {
+	Reader io.Reader
+}{
+	zeroReader{},
+}
+
+type zeroReader struct{}
+
+func (zeroReader) Read(buf []byte) (int, error) {
+	for i := range buf {
+		buf[i] = 0
+	}
+	return len(buf), nil
+}
+
+func ExampleSign_add_signatures() {
+	vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+	msg := []byte("If you think cryptography is the answer to your problem,\n" +
+		"then you don't know what your problem is.\n" +
+		"\n" +
+		"— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n")
+
+	verifier, err := note.NewVerifier(vkey)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+	notaries := note.NotaryList(verifier)
+
+	n, err := note.Open([]byte(msg), notaries)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+
+	skey, vkey, err := note.GenerateKey(rand.Reader, "EnochRoot")
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+	_ = vkey // give to verifiers
+
+	me, err := note.NewSigner(skey)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+
+	msg, err = note.Sign(n, me)
+	if err != nil {
+		fmt.Println(err)
+		return
+	}
+	os.Stdout.Write(msg)
+
+	// Output:
+	// If you think cryptography is the answer to your problem,
+	// then you don't know what your problem is.
+	//
+	// — PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=
+	// — EnochRoot rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ=
+}
diff --git a/notary/internal/note/note.go b/notary/internal/note/note.go
new file mode 100644
index 0000000..d4b14cf
--- /dev/null
+++ b/notary/internal/note/note.go
@@ -0,0 +1,664 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// Package note defines the notes signed by the Go module notary.
+//
+// This package is part of a DRAFT of what the Go module notary will look like.
+// Do not assume the details here are final!
+//
+// A note is text signed by one or more notary keys.
+// The text should be ignored unless the note is signed by
+// a trusted notary key and the signature has been verified.
+//
+// A notary key is identified by a name, typically the "host[/path]"
+// giving the base URL of the notary's transparency log.
+// The syntactic restrictions on a name are that it be non-empty,
+// well-formed UTF-8 containing neither Unicode spaces nor plus (U+002B).
+//
+// A notary signs texts using public key cryptography.
+// A given notary may have multiple public keys, each
+// identified by the first 32 bits of the SHA-256 hash of
+// the concatenation of the notary name, a newline, and
+// the encoded public key.
+//
+// Verifying Notes
+//
+// A Verifier allows verification of signatures by one notary public key.
+// It can report the name of the notary and the uint32 hash of the key,
+// and it can verify a purported signature by that key.
+//
+// The standard implementation of a Verifier is constructed
+// by NewVerifier starting from a verifier key, which is a
+// plain text string of the form "<name>+<hash>+<keydata>".
+//
+// A Notaries allows looking up a Verifier by the combination
+// of notary name and key hash.
+//
+// The standard implementation of a Notaries is constructed
+// by NotaryList from a list of known verifiers.
+//
+// A Note represents a text with one or more signatures.
+// An implementation can reject a note with too many signatures
+// (for example, more than 100 signatures).
+//
+// A Signature represents a signature on a note, verified or not.
+//
+// The Open function takes as input a signed message
+// and a set of known notaries. It decodes and verifies
+// the message signatures and returns a Note structure
+// containing the message text and (verified or unverified) signatures.
+//
+// Signing Notes
+//
+// A Signer allows signing a text with a given key.
+// It can report the name of the notary and the hash of the key
+// and can sign a raw text using that key.
+//
+// The standard implementation of a Signer is constructed
+// by NewSigner starting from an encoded signer key, which is a
+// plain text string of the form "PRIVATE+KEY+<name>+<hash>+<keydata>".
+// Anyone with an encoded signer key can sign messages using that key,
+// so it must be kept secret. The encoding begins with the literal text
+// "PRIVATE+KEY" to avoid confusion with the public verifier key.
+//
+// The Sign function takes as input a Note and a list of Signers
+// and returns an encoded, signed message.
+//
+// Signed Note Format
+//
+// A signed note consists of a text ending in newline (U+000A),
+// followed by a blank line (only a newline),
+// followed by one or more signature lines of this form:
+// em dash (U+2014), space (U+0020),
+// notary name, space, base64-encoded signature, newline.
+//
+// Signed notes must be valid UTF-8 and must not contain any
+// ASCII control characters (those below U+0020) other than newline.
+//
+// A signature is a base64 encoding of 4+n bytes.
+//
+// The first four bytes in the signature are the uint32 key hash
+// stored in big-endian order, which is to say they are the first
+// four bytes of the truncated SHA-256 used to derive the key hash
+// in the first place.
+//
+// The remaining n bytes are the result of using the specified key
+// to sign the note text (including the final newline but not the
+// separating blank line).
+//
+// Generating Keys
+//
+// There is only one key type, Ed25519 with algorithm identifier 1.
+// New key types may be introduced in the future as needed,
+// although doing so will require deploying the new algorithms to all clients
+// before starting to depend on them for signatures.
+//
+// The GenerateKey function generates and returns a new signer
+// and corresponding verifier.
+//
+// Example
+//
+// Here is a well-formed signed note:
+//
+//	If you think cryptography is the answer to your problem,
+//	then you don't know what your problem is.
+//
+//	— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=
+//
+// It can be constructed and displayed using:
+//
+//	skey := "PRIVATE+KEY+PeterNeumann+c74f20a3+AYEKFALVFGyNhPJEMzD1QIDr+Y7hfZx09iUvxdXHKDFz"
+//	text := "If you think cryptography is the answer to your problem,\n" +
+//		"then you don't know what your problem is.\n"
+//
+//	signer, err := note.NewSigner(skey)
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//
+//	msg, err := note.Sign(&note.Note{Text: text}, signer)
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//	os.Stdout.Write(msg)
+//
+// The note's text is two lines, including the final newline,
+// and the text is purportedly signed by a notary named
+// "PeterNeumann". (Although notary names are canonically
+// base URLs, the only syntactic requirement is that they
+// not contain spaces or newlines).
+//
+// If Open is given access to a Notaries including the
+// Verifier for this key, then it will succeed at verifiying
+// the encoded message and returning the parsed Note:
+//
+//	vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+//	msg := []byte("If you think cryptography is the answer to your problem,\n" +
+//		"then you don't know what your problem is.\n" +
+//		"\n" +
+//		"— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n")
+//
+//	verifier, err := note.NewVerifier(vkey)
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//	notaries := note.NotaryList(verifier)
+//
+//	n, err := note.Open([]byte(msg), notaries)
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//	fmt.Printf("%s (%08x):\n%s", n.Sigs[0].Name, n.Sigs[0].Hash, n.Text)
+//
+// You can add your own signature to this message by re-signing the note:
+//
+//	skey, vkey, err := note.GenerateKey(rand.Reader, "EnochRoot")
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//	_ = vkey // give to verifiers
+//
+//	me, err := note.NewSigner(skey)
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//
+//	msg, err := note.Sign(n, me)
+//	if err != nil {
+//		log.Fatal(err)
+//	}
+//	os.Stdout.Write(msg)
+//
+// This will print a doubly-signed message, like:
+//
+//	If you think cryptography is the answer to your problem,
+//	then you don't know what your problem is.
+//
+//	— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=
+//	— EnochRoot rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ=
+//
+package note
+
+import (
+	"bytes"
+	"crypto/sha256"
+	"encoding/base64"
+	"encoding/binary"
+	"errors"
+	"fmt"
+	"io"
+	"strconv"
+	"strings"
+	"unicode"
+	"unicode/utf8"
+
+	"golang.org/x/crypto/ed25519"
+)
+
+// A Verifier verifies messages signed with a specific notary key.
+type Verifier interface {
+	// Name returns the name of the notary.
+	Name() string
+
+	// KeyHash returns the notary key hash.
+	KeyHash() uint32
+
+	// Verify reports whether sig is a valid signature of msg.
+	Verify(msg, sig []byte) bool
+}
+
+// A Signer signs messages using a specific notary key.
+type Signer interface {
+	// Name returns the name of the notary.
+	Name() string
+
+	// KeyHash returns the notary key hash.
+	KeyHash() uint32
+
+	// Sign returns a signature for the given message.
+	Sign(msg []byte) ([]byte, error)
+}
+
+// keyHash computes the key hash for the given notary name and encoded public key.
+func keyHash(name string, key []byte) uint32 {
+	h := sha256.New()
+	h.Write([]byte(name))
+	h.Write([]byte("\n"))
+	h.Write(key)
+	sum := h.Sum(nil)
+	return binary.BigEndian.Uint32(sum)
+}
+
+var (
+	errVerifierID   = errors.New("malformed verifier id")
+	errVerifierAlg  = errors.New("unknown verifier algorithm")
+	errVerifierHash = errors.New("invalid verifier hash")
+)
+
+const (
+	algEd25519 = 1
+)
+
+// isValidName reports whether name is valid.
+// It must be non-empty and not have any Unicode spaces or pluses.
+func isValidName(name string) bool {
+	return name != "" && utf8.ValidString(name) && strings.IndexFunc(name, unicode.IsSpace) < 0 && !strings.Contains(name, "+")
+}
+
+// NewVerifier construct a new Verifier from an encoded verifier key.
+func NewVerifier(vkey string) (Verifier, error) {
+	name, vkey := chop(vkey, "+")
+	hash16, key64 := chop(vkey, "+")
+	hash, err1 := strconv.ParseUint(hash16, 16, 32)
+	key, err2 := base64.StdEncoding.DecodeString(key64)
+	if len(hash16) != 8 || err1 != nil || err2 != nil || !isValidName(name) || len(key) == 0 {
+		return nil, errVerifierID
+	}
+	if uint32(hash) != keyHash(name, key) {
+		return nil, errVerifierHash
+	}
+
+	v := &verifier{
+		name: name,
+		hash: uint32(hash),
+	}
+
+	alg, key := key[0], key[1:]
+	switch alg {
+	default:
+		return nil, errVerifierAlg
+
+	case algEd25519:
+		if len(key) != 32 {
+			return nil, errVerifierID
+		}
+		v.verify = func(msg, sig []byte) bool {
+			return ed25519.Verify(key, msg, sig)
+		}
+	}
+
+	return v, nil
+}
+
+// chop chops s at the first instance of sep, if any,
+// and returns the text before and after sep.
+// If sep is not present, chop returns before is s and after is empty.
+func chop(s, sep string) (before, after string) {
+	i := strings.Index(s, sep)
+	if i < 0 {
+		return s, ""
+	}
+	return s[:i], s[i+len(sep):]
+}
+
+// verifier is a trivial Verifier implementation.
+type verifier struct {
+	name   string
+	hash   uint32
+	verify func([]byte, []byte) bool
+}
+
+func (v *verifier) Name() string                { return v.name }
+func (v *verifier) KeyHash() uint32             { return v.hash }
+func (v *verifier) Verify(msg, sig []byte) bool { return v.verify(msg, sig) }
+
+// NewSigner constructs a new Signer from an encoded signer key.
+func NewSigner(skey string) (Signer, error) {
+	priv1, skey := chop(skey, "+")
+	priv2, skey := chop(skey, "+")
+	name, skey := chop(skey, "+")
+	hash16, key64 := chop(skey, "+")
+	hash, err1 := strconv.ParseUint(hash16, 16, 32)
+	key, err2 := base64.StdEncoding.DecodeString(key64)
+	if priv1 != "PRIVATE" || priv2 != "KEY" || len(hash16) != 8 || err1 != nil || err2 != nil || !isValidName(name) || len(key) == 0 {
+		return nil, errSignerID
+	}
+
+	// Note: hash is the hash of the public key and we have the private key.
+	// Must verify hash after deriving public key.
+
+	s := &signer{
+		name: name,
+		hash: uint32(hash),
+	}
+
+	var pubkey []byte
+
+	alg, key := key[0], key[1:]
+	switch alg {
+	default:
+		return nil, errSignerAlg
+
+	case algEd25519:
+		if len(key) != 32 {
+			return nil, errSignerID
+		}
+		key = ed25519.NewKeyFromSeed(key)
+		pubkey = append([]byte{algEd25519}, key[32:]...)
+		s.sign = func(msg []byte) ([]byte, error) {
+			return ed25519.Sign(key, msg), nil
+		}
+	}
+
+	if uint32(hash) != keyHash(name, pubkey) {
+		return nil, errSignerHash
+	}
+
+	return s, nil
+}
+
+var (
+	errSignerID   = errors.New("malformed verifier id")
+	errSignerAlg  = errors.New("unknown verifier algorithm")
+	errSignerHash = errors.New("invalid verifier hash")
+)
+
+// signer is a trivial Signer implementation.
+type signer struct {
+	name string
+	hash uint32
+	sign func([]byte) ([]byte, error)
+}
+
+func (s *signer) Name() string                    { return s.name }
+func (s *signer) KeyHash() uint32                 { return s.hash }
+func (s *signer) Sign(msg []byte) ([]byte, error) { return s.sign(msg) }
+
+// GenerateKey generates a signer and verifier key pair for a named notary.
+// The signer key skey is private and must be kept secret.
+func GenerateKey(rand io.Reader, name string) (skey, vkey string, err error) {
+	pub, priv, err := ed25519.GenerateKey(rand)
+	if err != nil {
+		return "", "", err
+	}
+	pubkey := append([]byte{algEd25519}, pub...)
+	privkey := append([]byte{algEd25519}, priv.Seed()...)
+	h := keyHash(name, pubkey)
+
+	skey = fmt.Sprintf("PRIVATE+KEY+%s+%08x+%s", name, h, base64.StdEncoding.EncodeToString(privkey))
+	vkey = fmt.Sprintf("%s+%08x+%s", name, h, base64.StdEncoding.EncodeToString(pubkey))
+	return skey, vkey, nil
+}
+
+// A Notaries is a collection of known notary keys.
+type Notaries interface {
+	// Verifier returns the Verifier associated with the notary key
+	// identified by the name and hash.
+	// If the name, hash pair is unknown, Verifier should return
+	// an UnknownNotaryError.
+	Verifier(name string, hash uint32) (Verifier, error)
+}
+
+// An UnknownNotaryError indicates that the given notary key is not known.
+// The Open function records signatures for unknown notaries as
+// unverified signatures.
+type UnknownNotaryError struct {
+	Name    string
+	KeyHash uint32
+}
+
+func (e *UnknownNotaryError) Error() string {
+	return fmt.Sprintf("unknown notary key %s+%08x", e.Name, e.KeyHash)
+}
+
+// An ambiguousNotaryError indicates that the given name and hash
+// match multiple notary keys passed to NotaryList.
+// (If this happens, some malicious actor has taken control of the
+// verifier list, at which point we may as well give up entirely,
+// but we diagnose the problem instead.)
+type ambiguousNotaryError struct {
+	name string
+	hash uint32
+}
+
+func (e *ambiguousNotaryError) Error() string {
+	return fmt.Sprintf("ambiguous notary key %s+%08x", e.name, e.hash)
+}
+
+// NotaryList returns a Notaries implementation that uses the given list of verifiers.
+func NotaryList(list ...Verifier) Notaries {
+	m := make(notaryMap)
+	for _, v := range list {
+		k := nameHash{v.Name(), v.KeyHash()}
+		m[k] = append(m[k], v)
+	}
+	return m
+}
+
+type nameHash struct {
+	name string
+	hash uint32
+}
+
+type notaryMap map[nameHash][]Verifier
+
+func (m notaryMap) Verifier(name string, hash uint32) (Verifier, error) {
+	v, ok := m[nameHash{name, hash}]
+	if !ok {
+		return nil, &UnknownNotaryError{name, hash}
+	}
+	if len(v) > 1 {
+		return nil, &ambiguousNotaryError{name, hash}
+	}
+	return v[0], nil
+}
+
+// A Note is a text and signatures.
+type Note struct {
+	Text           string      // text of note
+	Sigs           []Signature // verified signatures
+	UnverifiedSigs []Signature // unverified signatures
+}
+
+// A Signature is a single signature found in a note.
+type Signature struct {
+	// Name and Hash give the name and key hash
+	// for the notary key that generated the signature.
+	Name string
+	Hash uint32
+
+	// Base64 records the base64-encoded signature bytes.
+	Base64 string
+}
+
+// An UnverifiedNoteError indicates that the note
+// successfully parsed but had no verifiable signatures.
+type UnverifiedNoteError struct {
+	Note *Note
+}
+
+func (e *UnverifiedNoteError) Error() string {
+	return "note has no verifiable signatures"
+}
+
+// An InvalidSignatureError indicates that the given notary key was known
+// and the associated Verifier rejected the signature.
+type InvalidSignatureError struct {
+	Name string
+	Hash uint32
+}
+
+func (e *InvalidSignatureError) Error() string {
+	return fmt.Sprintf("invalid signature for notary key %s+%08x", e.Name, e.Hash)
+}
+
+var (
+	errMalformedNote = errors.New("malformed note")
+	errInvalidSigner = errors.New("invalid signer")
+
+	sigSplit  = []byte("\n\n")
+	sigPrefix = []byte("— ")
+)
+
+// Open opens and parses the message msg, checking signatures of the known notaries.
+//
+// For each signature in the message, Open calls known.Verifier to find a verifier.
+// If known.Verifier returns a verifier and the verifier accepts the signature,
+// Open records the signature in the returned note's Sigs field.
+// If known.Verifier returns a verifier but the verifier rejects the signature,
+// Open returns an InvalidSignatureError.
+// If known.Verifier returns an UnknownNotaryError,
+// Open records the signature in the returned note's UnverifiedSigs field.
+// If known.Verifier returns any other error, Open returns that error.
+//
+// If no known verifier has signed an otherwise valid note,
+// Open returns an UnverifiedNoteError.
+// In this case, the unverified note can be fetched from inside the error.
+func Open(msg []byte, known Notaries) (*Note, error) {
+	// Must have valid UTF-8 with no non-newline ASCII control characters.
+	for i := 0; i < len(msg); {
+		r, size := utf8.DecodeRune(msg[i:])
+		if r < 0x20 && r != '\n' || r == utf8.RuneError && size == 1 {
+			return nil, errMalformedNote
+		}
+		i += size
+	}
+
+	// Must end with signature block preceded by blank line.
+	split := bytes.LastIndex(msg, sigSplit)
+	if split < 0 {
+		return nil, errMalformedNote
+	}
+	text, sigs := msg[:split+1], msg[split+2:]
+	if len(sigs) == 0 || sigs[len(sigs)-1] != '\n' {
+		return nil, errMalformedNote
+	}
+
+	n := &Note{
+		Text: string(text),
+	}
+
+	var buf bytes.Buffer
+	buf.Write(text)
+
+	// Parse and verify signatures.
+	// Ignore duplicate signatures.
+	seen := make(map[nameHash]bool)
+	seenUnverified := make(map[string]bool)
+	numSig := 0
+	for len(sigs) > 0 {
+		// Pull out next signature line.
+		// We know sigs[len(sigs)-1] == '\n', so IndexByte always finds one.
+		i := bytes.IndexByte(sigs, '\n')
+		line := sigs[:i]
+		sigs = sigs[i+1:]
+
+		if !bytes.HasPrefix(line, sigPrefix) {
+			return nil, errMalformedNote
+		}
+		line = line[len(sigPrefix):]
+		name, b64 := chop(string(line), " ")
+		sig, err := base64.StdEncoding.DecodeString(b64)
+		if err != nil || !isValidName(name) || b64 == "" || len(sig) < 5 {
+			return nil, errMalformedNote
+		}
+		hash := binary.BigEndian.Uint32(sig[0:4])
+		sig = sig[4:]
+
+		if numSig++; numSig > 100 {
+			// Avoid spending forever parsing a note with many signatures.
+			return nil, errMalformedNote
+		}
+
+		v, err := known.Verifier(name, hash)
+		if _, ok := err.(*UnknownNotaryError); ok {
+			// Drop repeated identical unverified signatures.
+			if seenUnverified[string(line)] {
+				continue
+			}
+			seenUnverified[string(line)] = true
+			n.UnverifiedSigs = append(n.UnverifiedSigs, Signature{Name: name, Hash: hash, Base64: b64})
+			continue
+		}
+		if err != nil {
+			return nil, err
+		}
+
+		// Drop repeated signatures by a single verifier.
+		if seen[nameHash{name, hash}] {
+			continue
+		}
+		seen[nameHash{name, hash}] = true
+
+		ok := v.Verify(text, sig)
+		if !ok {
+			return nil, &InvalidSignatureError{name, hash}
+		}
+
+		n.Sigs = append(n.Sigs, Signature{Name: name, Hash: hash, Base64: b64})
+	}
+
+	// Parsed and verified all the signatures.
+	if len(n.Sigs) == 0 {
+		return nil, &UnverifiedNoteError{n}
+	}
+	return n, nil
+}
+
+// Sign signs the note with the given signers and returns the encoded message.
+// The new signatures from signers are listed in the encoded message after
+// the existing signatures already present in n.Sigs.
+// If any signer uses the same notary key as an existing signature,
+// the existing signature is elided from the output.
+func Sign(n *Note, signers ...Signer) ([]byte, error) {
+	var buf bytes.Buffer
+	if !strings.HasSuffix(n.Text, "\n") {
+		return nil, errMalformedNote
+	}
+	buf.WriteString(n.Text)
+
+	// Prepare signatures.
+	var sigs bytes.Buffer
+	have := make(map[nameHash]bool)
+	for _, s := range signers {
+		name := s.Name()
+		hash := s.KeyHash()
+		have[nameHash{name, hash}] = true
+		if !isValidName(name) {
+			return nil, errInvalidSigner
+		}
+
+		sig, err := s.Sign(buf.Bytes()) // buf holds n.Text
+		if err != nil {
+			return nil, err
+		}
+
+		var hbuf [4]byte
+		binary.BigEndian.PutUint32(hbuf[:], hash)
+		b64 := base64.StdEncoding.EncodeToString(append(hbuf[:], sig...))
+		sigs.WriteString("— ")
+		sigs.WriteString(name)
+		sigs.WriteString(" ")
+		sigs.WriteString(b64)
+		sigs.WriteString("\n")
+	}
+
+	buf.WriteString("\n")
+
+	// Emit existing signatures not replaced by new ones.
+	for _, list := range [][]Signature{n.Sigs, n.UnverifiedSigs} {
+		for _, sig := range list {
+			name, hash := sig.Name, sig.Hash
+			if !isValidName(name) {
+				return nil, errMalformedNote
+			}
+			if have[nameHash{name, hash}] {
+				continue
+			}
+			// Double-check hash against base64.
+			raw, err := base64.StdEncoding.DecodeString(sig.Base64)
+			if err != nil || len(raw) < 4 || binary.BigEndian.Uint32(raw) != hash {
+				return nil, errMalformedNote
+			}
+			buf.WriteString("— ")
+			buf.WriteString(sig.Name)
+			buf.WriteString(" ")
+			buf.WriteString(sig.Base64)
+			buf.WriteString("\n")
+		}
+	}
+	buf.Write(sigs.Bytes())
+
+	return buf.Bytes(), nil
+}
diff --git a/notary/internal/note/note_test.go b/notary/internal/note/note_test.go
new file mode 100644
index 0000000..3c46ca6
--- /dev/null
+++ b/notary/internal/note/note_test.go
@@ -0,0 +1,415 @@
+// Copyright 2019 The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package note
+
+import (
+	"crypto/rand"
+	"errors"
+	"fmt"
+	"strings"
+	"testing"
+	"testing/iotest"
+)
+
+func TestNewVerifier(t *testing.T) {
+	vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+	_, err := NewVerifier(vkey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// Check various manglings are not accepted.
+	badKey := func(k string) {
+		_, err := NewVerifier(k)
+		if err == nil {
+			t.Errorf("NewVerifier(%q) succeeded, should have failed", k)
+		}
+	}
+
+	b := []byte(vkey)
+	for i := 0; i <= len(b); i++ {
+		for j := i + 1; j <= len(b); j++ {
+			if i != 0 || j != len(b) {
+				badKey(string(b[i:j]))
+			}
+		}
+	}
+	for i := 0; i < len(b); i++ {
+		b[i]++
+		badKey(string(b))
+		b[i]--
+	}
+
+	badKey("PeterNeumann+cc469956+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TWBADKEY==") // wrong length key, with adjusted key hash
+	badKey("PeterNeumann+173116ae+ZRpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW")         // unknown algorithm, with adjusted key hash
+}
+
+func TestNewSigner(t *testing.T) {
+	skey := "PRIVATE+KEY+PeterNeumann+c74f20a3+AYEKFALVFGyNhPJEMzD1QIDr+Y7hfZx09iUvxdXHKDFz"
+	_, err := NewSigner(skey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// Check various manglings are not accepted.
+	b := []byte(skey)
+	for i := 0; i <= len(b); i++ {
+		for j := i + 1; j <= len(b); j++ {
+			if i == 0 && j == len(b) {
+				continue
+			}
+			_, err := NewSigner(string(b[i:j]))
+			if err == nil {
+				t.Errorf("NewSigner(%q) succeeded, should have failed", b[i:j])
+			}
+		}
+	}
+	for i := 0; i < len(b); i++ {
+		b[i]++
+		_, err := NewSigner(string(b))
+		if err == nil {
+			t.Errorf("NewSigner(%q) succeeded, should have failed", b)
+		}
+		b[i]--
+	}
+}
+
+func TestGenerateKey(t *testing.T) {
+	// Generate key pair, make sure it is all self-consistent.
+	const Name = "EnochRoot"
+	skey, vkey, err := GenerateKey(rand.Reader, Name)
+	if err != nil {
+		t.Fatalf("GenerateKey: %v", err)
+	}
+	signer, err := NewSigner(skey)
+	if err != nil {
+		t.Fatalf("NewSigner: %v", err)
+	}
+	verifier, err := NewVerifier(vkey)
+	if err != nil {
+		t.Fatalf("NewVerifier: %v", err)
+	}
+
+	if name := signer.Name(); name != Name {
+		t.Errorf("signer.Name() = %q, want %q", name, Name)
+	}
+	if name := verifier.Name(); name != Name {
+		t.Errorf("verifier.Name() = %q, want %q", name, Name)
+	}
+	shash := signer.KeyHash()
+	vhash := verifier.KeyHash()
+	if shash != vhash {
+		t.Errorf("signer.KeyHash() = %#08x != verifier.KeyHash() = %#08x", shash, vhash)
+	}
+
+	msg := []byte("hi")
+	sig, err := signer.Sign(msg)
+	if err != nil {
+		t.Fatalf("signer.Sign: %v", err)
+	}
+	if !verifier.Verify(msg, sig) {
+		t.Fatalf("verifier.Verify failed on signature returned by signer.Sign")
+	}
+	sig[0]++
+	if verifier.Verify(msg, sig) {
+		t.Fatalf("verifier.Verify succceeded on corrupt signature")
+	}
+
+	// Check that GenerateKey returns error from rand reader.
+	_, _, err = GenerateKey(iotest.TimeoutReader(iotest.OneByteReader(rand.Reader)), Name)
+	if err == nil {
+		t.Fatalf("GenerateKey succeeded with error-returning rand reader")
+	}
+}
+
+func TestSign(t *testing.T) {
+	skey := "PRIVATE+KEY+PeterNeumann+c74f20a3+AYEKFALVFGyNhPJEMzD1QIDr+Y7hfZx09iUvxdXHKDFz"
+	text := "If you think cryptography is the answer to your problem,\n" +
+		"then you don't know what your problem is.\n"
+
+	signer, err := NewSigner(skey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	msg, err := Sign(&Note{Text: text}, signer)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	want := `If you think cryptography is the answer to your problem,
+then you don't know what your problem is.
+
+— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=
+`
+	if string(msg) != want {
+		t.Errorf("Sign: wrong output\nhave:\n%s\nwant:\n%s", msg, want)
+	}
+
+	// Check that existing signature is replaced by new one.
+	msg, err = Sign(&Note{Text: text, Sigs: []Signature{{Name: "PeterNeumann", Hash: 0xc74f20a3, Base64: "BADSIGN="}}}, signer)
+	if err != nil {
+		t.Fatal(err)
+	}
+	if string(msg) != want {
+		t.Errorf("Sign replacing signature: wrong output\nhave:\n%s\nwant:\n%s", msg, want)
+	}
+
+	// Check various bad inputs.
+	_, err = Sign(&Note{Text: "abc"}, signer)
+	if err == nil || err.Error() != "malformed note" {
+		t.Fatalf("Sign with short text: %v, want malformed note error", err)
+	}
+
+	_, err = Sign(&Note{Text: text, Sigs: []Signature{{Name: "a+b", Base64: "ABCD"}}})
+	if err == nil || err.Error() != "malformed note" {
+		t.Fatalf("Sign with bad name: %v, want malformed note error", err)
+	}
+
+	_, err = Sign(&Note{Text: text, Sigs: []Signature{{Name: "PeterNeumann", Hash: 0xc74f20a3, Base64: "BADHASH="}}})
+	if err == nil || err.Error() != "malformed note" {
+		t.Fatalf("Sign with bad pre-filled signature: %v, want malformed note error", err)
+	}
+
+	_, err = Sign(&Note{Text: text}, &badSigner{signer})
+	if err == nil || err.Error() != "invalid signer" {
+		t.Fatalf("Sign with bad signer: %v, want invalid signer error", err)
+	}
+
+	_, err = Sign(&Note{Text: text}, &errSigner{signer})
+	if err != errSurprise {
+		t.Fatalf("Sign with failing signer: %v, want errSurprise", err)
+	}
+}
+
+func TestNotaryList(t *testing.T) {
+	peterKey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+	peterVerifier, err := NewVerifier(peterKey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	enochKey := "EnochRoot+af0cfe78+ATtqJ7zOtqQtYqOo0CpvDXNlMhV3HeJDpjrASKGLWdop"
+	enochVerifier, err := NewVerifier(enochKey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	list := NotaryList(peterVerifier, enochVerifier, enochVerifier)
+	v, err := list.Verifier("PeterNeumann", 0xc74f20a3)
+	if v != peterVerifier || err != nil {
+		t.Fatalf("list.Verifier(peter) = %v, %v, want %v, nil", v, err, peterVerifier)
+	}
+	v, err = list.Verifier("PeterNeumann", 0xc74f20a4)
+	if v != nil || err == nil || err.Error() != "unknown notary key PeterNeumann+c74f20a4" {
+		t.Fatalf("list.Verifier(peter bad hash) = %v, %v, want nil, unknown notary key error", v, err)
+	}
+
+	v, err = list.Verifier("PeterNeuman", 0xc74f20a3)
+	if v != nil || err == nil || err.Error() != "unknown notary key PeterNeuman+c74f20a3" {
+		t.Fatalf("list.Verifier(peter bad name) = %v, %v, want nil, unknown notary key error", v, err)
+	}
+	v, err = list.Verifier("EnochRoot", 0xaf0cfe78)
+	if v != nil || err == nil || err.Error() != "ambiguous notary key EnochRoot+af0cfe78" {
+		t.Fatalf("list.Verifier(enoch) = %v, %v, want nil, ambiguous notary key error", v, err)
+	}
+}
+
+type badSigner struct {
+	Signer
+}
+
+func (b *badSigner) Name() string {
+	return "bad name"
+}
+
+var errSurprise = errors.New("surprise!")
+
+type errSigner struct {
+	Signer
+}
+
+func (e *errSigner) Sign([]byte) ([]byte, error) {
+	return nil, errSurprise
+}
+
+func fmtSig(s Signature) string {
+	return fmt.Sprintf("{%q %#08x %s}", s.Name, s.Hash, s.Base64)
+}
+
+func TestOpen(t *testing.T) {
+	peterKey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+	peterVerifier, err := NewVerifier(peterKey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	enochKey := "EnochRoot+af0cfe78+ATtqJ7zOtqQtYqOo0CpvDXNlMhV3HeJDpjrASKGLWdop"
+	enochVerifier, err := NewVerifier(enochKey)
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	text := `If you think cryptography is the answer to your problem,
+then you don't know what your problem is.
+`
+	peterSig := "— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n"
+	enochSig := "— EnochRoot rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ=\n"
+
+	peter := Signature{"PeterNeumann", 0xc74f20a3, "x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM="}
+	enoch := Signature{"EnochRoot", 0xaf0cfe78, "rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ="}
+
+	// Check one signature verified, one not.
+	n, err := Open([]byte(text+"\n"+peterSig+enochSig), NotaryList(peterVerifier))
+	if err != nil {
+		t.Fatal(err)
+	}
+	if n.Text != text {
+		t.Errorf("n.Text = %q, want %q", n.Text, text)
+	}
+	if len(n.Sigs) != 1 || n.Sigs[0] != peter {
+		t.Errorf("n.Sigs:\nhave %v\nwant %v", n.Sigs, []Signature{peter})
+	}
+	if len(n.UnverifiedSigs) != 1 || n.UnverifiedSigs[0] != enoch {
+		t.Errorf("n.UnverifiedSigs:\nhave %v\nwant %v", n.Sigs, []Signature{peter})
+	}
+
+	// Check both verified.
+	n, err = Open([]byte(text+"\n"+peterSig+enochSig), NotaryList(peterVerifier, enochVerifier))
+	if err != nil {
+		t.Fatal(err)
+	}
+	if len(n.Sigs) != 2 || n.Sigs[0] != peter || n.Sigs[1] != enoch {
+		t.Errorf("n.Sigs:\nhave %v\nwant %v", n.Sigs, []Signature{peter, enoch})
+	}
+	if len(n.UnverifiedSigs) != 0 {
+		t.Errorf("n.UnverifiedSigs:\nhave %v\nwant %v", n.Sigs, []Signature{})
+	}
+
+	// Check both unverified.
+	n, err = Open([]byte(text+"\n"+peterSig+enochSig), NotaryList())
+	if n != nil || err == nil {
+		t.Fatalf("Open unverified = %v, %v, want nil, error", n, err)
+	}
+	e, ok := err.(*UnverifiedNoteError)
+	if !ok {
+		t.Fatalf("Open unverified: err is %T, want *UnverifiedNoteError", err)
+	}
+	if err.Error() != "note has no verifiable signatures" {
+		t.Fatalf("Open unverified: err.Error() = %q, want %q", err.Error(), "note has no verifiable signatures")
+	}
+
+	n = e.Note
+	if n == nil {
+		t.Fatalf("Open unverified: missing note in UnverifiedNoteError")
+	}
+	if len(n.Sigs) != 0 {
+		t.Errorf("n.Sigs:\nhave %v\nwant %v", n.Sigs, []Signature{})
+	}
+	if len(n.UnverifiedSigs) != 2 || n.UnverifiedSigs[0] != peter || n.UnverifiedSigs[1] != enoch {
+		t.Errorf("n.UnverifiedSigs:\nhave %v\nwant %v", n.Sigs, []Signature{peter, enoch})
+	}
+
+	// Check duplicated verifier.
+	_, err = Open([]byte(text+"\n"+enochSig), NotaryList(enochVerifier, peterVerifier, enochVerifier))
+	if err == nil || err.Error() != "ambiguous notary key EnochRoot+af0cfe78" {
+		t.Fatalf("Open with duplicated verifier: err=%v, want ambiguous notary key", err)
+	}
+
+	// Check unused duplicated verifier.
+	_, err = Open([]byte(text+"\n"+peterSig), NotaryList(enochVerifier, peterVerifier, enochVerifier))
+	if err != nil {
+		t.Fatal(err)
+	}
+
+	// Check too many signatures.
+	n, err = Open([]byte(text+"\n"+strings.Repeat(peterSig, 101)), NotaryList(peterVerifier))
+	if n != nil || err == nil || err.Error() != "malformed note" {
+		t.Fatalf("Open too many verified signatures = %v, %v, want nil, malformed note error", n, err)
+	}
+	n, err = Open([]byte(text+"\n"+strings.Repeat(peterSig, 101)), NotaryList())
+	if n != nil || err == nil || err.Error() != "malformed note" {
+		t.Fatalf("Open too many verified signatures = %v, %v, want nil, malformed note error", n, err)
+	}
+
+	// Invalid signature.
+	n, err = Open([]byte(text+"\n"+peterSig[:60]+"ABCD"+peterSig[60:]), NotaryList(peterVerifier))
+	if n != nil || err == nil || err.Error() != "invalid signature for notary key PeterNeumann+c74f20a3" {
+		t.Fatalf("Open too many verified signatures = %v, %v, want nil, invalid signature error", n, err)
+	}
+
+	// Duplicated verified and unverified signatures.
+	enochABCD := Signature{"EnochRoot", 0xaf0cfe78, "rwz+eBzmZa0SO3NbfRGzPCpDckykFXSdeX+MNtCOXm2/5n" + "ABCD" + "2tiOHp+vAF1aGrQ5ovTG01oOTGwnWLox33WWd1RvMc+QQ="}
+	n, err = Open([]byte(text+"\n"+peterSig+peterSig+enochSig+enochSig+enochSig[:60]+"ABCD"+enochSig[60:]), NotaryList(peterVerifier))
+	if err != nil {
+		t.Fatal(err)
+	}
+	if len(n.Sigs) != 1 || n.Sigs[0] != peter {
+		t.Errorf("n.Sigs:\nhave %v\nwant %v", n.Sigs, []Signature{peter})
+	}
+	if len(n.UnverifiedSigs) != 2 || n.UnverifiedSigs[0] != enoch || n.UnverifiedSigs[1] != enochABCD {
+		t.Errorf("n.UnverifiedSigs:\nhave %v\nwant %v", n.UnverifiedSigs, []Signature{enoch, enochABCD})
+	}
+
+	// Invalid encoded message syntax.
+	badMsgs := []string{
+		text,
+		text + "\n",
+		text + "\n" + peterSig[:len(peterSig)-1],
+		"\x01" + text + "\n" + peterSig,
+		"\xff" + text + "\n" + peterSig,
+		text + "\n" + "— Bad Name x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=",
+		text + "\n" + peterSig + "Unexpected line.\n",
+	}
+	for _, msg := range badMsgs {
+		n, err := Open([]byte(msg), NotaryList(peterVerifier))
+		if n != nil || err == nil || err.Error() != "malformed note" {
+			t.Fatalf("Open bad msg = %v, %v, want nil, malformed note error\nmsg:\n%s", n, err, msg)
+		}
+	}
+}
+
+func BenchmarkOpen(b *testing.B) {
+	vkey := "PeterNeumann+c74f20a3+ARpc2QcUPDhMQegwxbzhKqiBfsVkmqq/LDE4izWy10TW"
+	msg := []byte("If you think cryptography is the answer to your problem,\n" +
+		"then you don't know what your problem is.\n" +
+		"\n" +
+		"— PeterNeumann x08go/ZJkuBS9UG/SffcvIAQxVBtiFupLLr8pAcElZInNIuGUgYN1FFYC2pZSNXgKvqfqdngotpRZb6KE6RyyBwJnAM=\n")
+
+	verifier, err := NewVerifier(vkey)
+	if err != nil {
+		b.Fatal(err)
+	}
+	notaries := NotaryList(verifier)
+	notaries0 := NotaryList()
+
+	// Try with 0 signatures and 1 signature so we can tell how much each signature adds.
+
+	b.Run("Sig0", func(b *testing.B) {
+		for i := 0; i < b.N; i++ {
+			_, err := Open(msg, notaries0)
+			e, ok := err.(*UnverifiedNoteError)
+			if !ok {
+				b.Fatal("expected UnverifiedNoteError")
+			}
+			n := e.Note
+			if len(n.Sigs) != 0 || len(n.UnverifiedSigs) != 1 {
+				b.Fatal("wrong signature count")
+			}
+		}
+	})
+
+	b.Run("Sig1", func(b *testing.B) {
+		for i := 0; i < b.N; i++ {
+			n, err := Open(msg, notaries)
+			if err != nil {
+				b.Fatal(err)
+			}
+			if len(n.Sigs) != 1 || len(n.UnverifiedSigs) != 0 {
+				b.Fatal("wrong signature count")
+			}
+		}
+	})
+}