func generateTrustCert(key libtrust.PublicKey, parentKey PrivateKey, parent *x509.Certificate) *x509.Certificate {
	cert := &x509.Certificate{
		SerialNumber: big.NewInt(0),
		Subject: pkix.Name{
			CommonName: "Trust Cert",
		},
		NotBefore:             time.Now().Add(-time.Second),
		NotAfter:              time.Now().Add(time.Hour),
		IsCA:                  true,
		KeyUsage:              x509.KeyUsageDigitalSignature,
		BasicConstraintsValid: true,
	}

	certDER, err := x509.CreateCertificate(
		rand.Reader, cert, parent,
		key.CryptoPublicKey(), parentKey.CryptoPrivateKey(),
	)
	if err != nil {
		panic(err)
	}

	cert, err = x509.ParseCertificate(certDER)
	if err != nil {
		panic(err)
	}

	return cert
}

func testVerified(t *testing.T, g TrustGraph, k libtrust.PublicKey, keyName, target string, permission uint16) {
	if ok, err := g.Verify(k, target, permission); err != nil {
		t.Fatalf("Unexpected error during verification: %s", err)
	} else if !ok {
		t.Errorf("key failed verification\n\tKey: %s(%s)\n\tNamespace: %s", keyName, k.KeyID(), target)
	}
}

func (g *memoryGraph) GetGrants(key libtrust.PublicKey, node string, permission uint16) ([][]*Grant, error) {
	grants := [][]*Grant{}
	collect := func(grant *Grant, chain []*Grant) bool {
		grantChain := make([]*Grant, len(chain)+1)
		copy(grantChain, chain)
		grantChain[len(grantChain)-1] = grant
		grants = append(grants, grantChain)
		return false
	}
	g.walkGrants(key.KeyID(), node, permission, collect, nil, nil, true)
	return grants, nil
}

// Verify verifies all the signatures and returns the list of
// public keys used to sign. Any x509 chains are not checked.
func (js *JSONSignature) Verify() ([]libtrust.PublicKey, error) {
	keys := make([]libtrust.PublicKey, len(js.signatures))
	for i, signature := range js.signatures {
		signBytes, err := js.signBytes(signature.Protected)
		if err != nil {
			return nil, err
		}
		var publicKey libtrust.PublicKey
		if len(signature.Header.Chain) > 0 {
			certBytes, err := base64.StdEncoding.DecodeString(signature.Header.Chain[0])
			if err != nil {
				return nil, err
			}
			cert, err := x509.ParseCertificate(certBytes)
			if err != nil {
				return nil, err
			}
			publicKey, err = FromCryptoPublicKey(cert.PublicKey)
			if err != nil {
				return nil, err
			}
		} else if signature.Header.JWK != nil {
			publicKey = signature.Header.JWK
		} else {
			return nil, errors.New("missing public key")
		}

		sigBytes, err := joseBase64UrlDecode(signature.Signature)
		if err != nil {
			return nil, err
		}

		err = publicKey.Verify(bytes.NewReader(signBytes), signature.Header.Algorithm, sigBytes)
		if err != nil {
			return nil, err
		}

		keys[i] = publicKey
	}
	return keys, nil
}

func promptUnknownKey(key libtrust.PublicKey, host string) bool {
	fmt.Printf("The authenticity of host %q can't be established.\nRemote key ID %s\n", host, key.KeyID())
	fmt.Printf("Are you sure you want to continue connecting (yes/no)? ")
	reader := bufio.NewReader(os.Stdin)
	line, _, err := reader.ReadLine()
	if err != nil {
		log.Fatalf("Error reading input: %s", err)
	}
	input := strings.TrimSpace(strings.ToLower(string(line)))
	return input == "yes" || input == "y"
}

func (g *memoryGraph) Verify(key libtrust.PublicKey, node string, permission uint16) (bool, error) {
	return g.walkGrants(key.KeyID(), node, permission, foundWalkFunc, nil, nil, false), nil
}

// VerifyChains verifies all the signatures and the chains associated
// with each signature and returns the list of verified chains.
// Signatures without an x509 chain are not checked.
func (js *JSONSignature) VerifyChains(ca *x509.CertPool) ([][]*x509.Certificate, error) {
	chains := make([][]*x509.Certificate, 0, len(js.signatures))
	for _, signature := range js.signatures {
		signBytes, err := js.signBytes(signature.Protected)
		if err != nil {
			return nil, err
		}
		var publicKey libtrust.PublicKey
		if len(signature.Header.Chain) > 0 {
			certBytes, err := base64.StdEncoding.DecodeString(signature.Header.Chain[0])
			if err != nil {
				return nil, err
			}
			cert, err := x509.ParseCertificate(certBytes)
			if err != nil {
				return nil, err
			}
			publicKey, err = FromCryptoPublicKey(cert.PublicKey)
			if err != nil {
				return nil, err
			}
			intermediates := x509.NewCertPool()
			if len(signature.Header.Chain) > 1 {
				intermediateChain := signature.Header.Chain[1:]
				for i := range intermediateChain {
					certBytes, err := base64.StdEncoding.DecodeString(intermediateChain[i])
					if err != nil {
						return nil, err
					}
					intermediate, err := x509.ParseCertificate(certBytes)
					if err != nil {
						return nil, err
					}
					intermediates.AddCert(intermediate)
				}
			}

			verifyOptions := x509.VerifyOptions{
				Intermediates: intermediates,
				Roots:         ca,
			}

			verifiedChains, err := cert.Verify(verifyOptions)
			if err != nil {
				return nil, err
			}
			chains = append(chains, verifiedChains...)

			sigBytes, err := joseBase64UrlDecode(signature.Signature)
			if err != nil {
				return nil, err
			}

			err = publicKey.Verify(bytes.NewReader(signBytes), signature.Header.Algorithm, sigBytes)
			if err != nil {
				return nil, err
			}
		}

	}
	return chains, nil
}