func ImportKeypairFromKID(k keybase1.KID) (key GenericKey, err error) {
	kid := k.ToBytes()
	l := len(kid)
	if l < 3 {
		err = BadKeyError{"KID was way too short"}
		return
	}
	if kid[0] != byte(KeybaseKIDV1) || kid[l-1] != byte(IDSuffixKID) {
		err = BadKeyError{"bad header or trailer found"}
		return
	}
	raw := kid[2:(l - 1)]
	switch kid[1] {
	case byte(KIDNaclEddsa):
		if len(raw) != ed25519.PublicKeySize {
			err = BadKeyError{"Bad EdDSA key size"}
		} else {
			tmp := NaclSigningKeyPair{}
			copy(tmp.Public[:], raw)
			key = tmp
		}
	case byte(KIDNaclDH):
		if len(raw) != NaclDHKeysize {
			err = BadKeyError{"Bad DH key size"}
		} else {
			tmp := NaclDHKeyPair{}
			copy(tmp.Public[:], raw)
			key = tmp
		}
	default:
		err = BadKeyError{fmt.Sprintf("Bad key prefix: %d", kid[1])}
	}
	return
}

func PostDeviceLKS(sr SessionReader, deviceID keybase1.DeviceID, deviceType string, serverHalf []byte,
	ppGen PassphraseGeneration,
	clientHalfRecovery string, clientHalfRecoveryKID keybase1.KID) error {
	if len(serverHalf) == 0 {
		return fmt.Errorf("PostDeviceLKS: called with empty serverHalf")
	}
	if ppGen < 1 {
		G.Log.Warning("PostDeviceLKS: ppGen < 1 (%d)", ppGen)
		debug.PrintStack()
	}
	arg := APIArg{
		Endpoint:    "device/update",
		NeedSession: true,
		Args: HTTPArgs{
			"device_id":       S{Val: deviceID.String()},
			"type":            S{Val: deviceType},
			"lks_server_half": S{Val: hex.EncodeToString(serverHalf)},
			"ppgen":           I{Val: int(ppGen)},
			"lks_client_half": S{Val: clientHalfRecovery},
			"kid":             S{Val: clientHalfRecoveryKID.String()},
		},
		SessionR: sr,
	}
	_, err := G.API.Post(arg)
	return err
}

// To add a device key as the eldest key, signer and eldestKID
// should be nil.
func (d *Locksmith) addDeviceKeyWithSigner(ctx *Context, signer libkb.GenericKey, eldestKID keybase1.KID) error {
	devname, err := d.deviceName(ctx)
	if err != nil {
		return err
	}
	pps, err := d.ppStream(ctx)
	if err != nil {
		return err
	}
	d.lks = libkb.NewLKSec(pps, d.arg.User.GetUID(), d.G())
	args := &DeviceWrapArgs{
		Me:         d.arg.User,
		DeviceName: devname,
		DeviceType: libkb.DeviceTypeDesktop,
		Lks:        d.lks,
		IsEldest:   false,
		Signer:     signer,
		EldestKID:  eldestKID,
	}
	if signer == nil && eldestKID.IsNil() {
		args.IsEldest = true
	}
	eng := NewDeviceWrap(args, d.G())
	if err := RunEngine(eng, ctx); err != nil {
		return err
	}

	d.signingKey = eng.SigningKey()
	return nil
}

// Delegate marks the given ComputedKeyInfos object that the given kid is now
// delegated, as of time tm, in sigid, as signed by signingKid, etc.
func (cki *ComputedKeyInfos) Delegate(kid keybase1.KID, tm *KeybaseTime, sigid keybase1.SigID, signingKid, parentKID keybase1.KID, pgpHash string, isSibkey bool, ctime, etime time.Time) (err error) {
	G.Log.Debug("ComputeKeyInfos::Delegate To %s with %s at sig %s", kid.String(), signingKid, sigid.ToDisplayString(true))
	info, found := cki.Infos[kid]
	if !found {
		newInfo := NewComputedKeyInfo(false, false, KeyUncancelled, ctime.Unix(), etime.Unix(), pgpHash)
		newInfo.DelegatedAt = tm
		info = &newInfo
		cki.Infos[kid] = info
	} else {
		info.Status = KeyUncancelled
		info.CTime = ctime.Unix()
		info.ETime = etime.Unix()
	}
	info.Delegations[sigid] = signingKid
	info.Sibkey = isSibkey
	cki.Sigs[sigid] = info

	// If it's a subkey, make a pointer from it to its parent,
	// and also from its parent to it.
	if parentKID.Exists() {
		info.Parent = parentKID
		if parent, found := cki.Infos[parentKID]; found {
			parent.Subkey = kid
		}
	}

	return
}

// GetSibkeyForDevice gets the current per-device key for the given Device. Will
// return nil if one isn't found, and set err for a real error. The sibkey should
// be a signing key, not an encryption key of course.
func (ckf *ComputedKeyFamily) GetSibkeyForDevice(did keybase1.DeviceID) (key GenericKey, err error) {
	var kid keybase1.KID
	kid, err = ckf.getSibkeyKidForDevice(did)
	if kid.Exists() {
		key, _, err = ckf.FindActiveSibkey(kid)
	}
	return
}

func (k *KexProvisioner) verifyPleaseSign(jw *jsonw.Wrapper, newKID keybase1.KID) (err error) {
	jw.AssertEqAtPath("body.key.kid", k.sigKey.GetKID().ToJsonw(), &err)
	jw.AssertEqAtPath("body.key.uid", libkb.UIDWrapper(k.user.GetUID()), &err)
	jw.AssertEqAtPath("body.key.eldest_kid", k.user.GetEldestKID().ToJsonw(), &err)
	jw.AssertEqAtPath("body.key.username", jsonw.NewString(k.user.GetName()), &err)
	jw.AssertEqAtPath("body.device.kid", newKID.ToJsonw(), &err)
	jw.AssertEqAtPath("body.type", jsonw.NewString("sibkey"), &err)
	return err
}

// GetTLFCryptKeyServerHalfID implements the Crypto interface for CryptoCommon.
func (c *CryptoCommon) GetTLFCryptKeyServerHalfID(
	user keybase1.UID, deviceKID keybase1.KID,
	serverHalf TLFCryptKeyServerHalf) (TLFCryptKeyServerHalfID, error) {
	key := serverHalf.data[:]
	data := append(user.ToBytes(), deviceKID.ToBytes()...)
	hmac, err := DefaultHMAC(key, data)
	if err != nil {
		return TLFCryptKeyServerHalfID{}, err
	}
	return TLFCryptKeyServerHalfID{
		ID: hmac,
	}, nil
}

func LoadPGPKeyFromLocalDB(k keybase1.KID, g *GlobalContext) (*PGPKeyBundle, error) {
	dbobj, err := g.LocalDb.Get(DbKey{
		Typ: DBPGPKey,
		Key: k.String(),
	})
	if err != nil {
		return nil, err
	}
	if dbobj == nil {
		return nil, nil
	}
	return GetOneKey(dbobj)
}

func (sc *SigChain) VerifySigsAndComputeKeys(eldest keybase1.KID, ckf *ComputedKeyFamily) (cached bool, err error) {

	cached = false
	sc.G().Log.Debug("+ VerifySigsAndComputeKeys for user %s (eldest = %s)", sc.uid, eldest)
	defer func() {
		sc.G().Log.Debug("- VerifySigsAndComputeKeys for user %s -> %s", sc.uid, ErrToOk(err))
	}()

	if err = sc.VerifyChain(); err != nil {
		return
	}

	if sc.allKeys || sc.loadedFromLinkOne {
		if first := sc.getFirstSeqno(); first > Seqno(1) {
			err = ChainLinkWrongSeqnoError{fmt.Sprintf("Wanted a chain from seqno=1, but got seqno=%d", first)}
			return
		}
	}

	if ckf.kf == nil || eldest.IsNil() {
		sc.G().Log.Debug("| VerifyWithKey short-circuit, since no Key available")
		sc.localCki = NewComputedKeyInfos(sc.G())
		ckf.cki = sc.localCki
		return
	}
	links, err := sc.GetCurrentSubchain(eldest)
	if err != nil {
		return
	}

	if links == nil || len(links) == 0 {
		sc.G().Log.Debug("| Empty chain after we limited to eldest %s", eldest)
		eldestKey, _ := ckf.FindKeyWithKIDUnsafe(eldest)
		sc.localCki = NewComputedKeyInfos(sc.G())
		err = sc.localCki.InsertServerEldestKey(eldestKey, sc.username)
		ckf.cki = sc.localCki
		return
	}

	if cached, ckf.cki, err = sc.verifySubchain(*ckf.kf, links); err != nil {
		return
	}

	// We used to check for a self-signature of one's keybase username
	// here, but that doesn't make sense because we haven't accounted
	// for revocations.  We'll go it later, after reconstructing
	// the id_table.  See LoadUser in user.go and
	// https://github.com/keybase/go/issues/43

	return
}

// Load takes a blessed KID and returns, if possible, the GenericKey
// associated with that KID, for signature verification. If the key isn't
// found in memory or on disk (in the case of PGP), then it will attempt
// to fetch the key from the keybase server.
func (sk *SpecialKeyRing) Load(kid keybase1.KID) (GenericKey, error) {

	sk.G().Log.Debug("+ SpecialKeyRing.Load(%s)", kid)

	if !sk.IsValidKID(kid) {
		err := UnknownSpecialKIDError{kid}
		return nil, err
	}

	if key, found := sk.keys[kid]; found {
		sk.G().Log.Debug("- SpecialKeyRing.Load(%s) -> hit inmem cache", kid)
		return key, nil
	}

	key, err := LoadPGPKeyFromLocalDB(kid, sk.G())

	if err != nil || key == nil {

		sk.G().Log.Debug("| Load(%s) going to network", kid)
		var res *APIRes
		res, err = sk.G().API.Get(APIArg{
			Endpoint:    "key/special",
			NeedSession: false,
			Args: HTTPArgs{
				"kid": S{kid.String()},
			},
			Contextified: NewContextified(sk.G()),
		})
		var w *Warnings
		if err == nil {
			key, w, err = GetOneKey(res.Body.AtKey("bundle"))
		}
		if err == nil {
			w.Warn(sk.G())

			if e2 := key.StoreToLocalDb(sk.G()); e2 != nil {
				sk.G().Log.Warning("Failed to store key: %s", e2)
			}
		}
	} else {
		sk.G().Log.Debug("| Load(%s) hit DB-backed cache", kid)
	}

	if err == nil && key != nil {
		sk.keys[kid] = key
	}

	sk.G().Log.Debug("- SpecialKeyRing.Load(%s)", kid)

	return key, err
}

// FindActiveEncryptionSubkey takes a given KID and finds the corresponding
// active encryption subkey in the current key family.  If for any reason it
// cannot find the key, it will return an error saying why.  Otherwise, it will
// return the key.  In this case either key is non-nil, or err is non-nil.
func (ckf ComputedKeyFamily) FindActiveEncryptionSubkey(kid keybase1.KID) (GenericKey, error) {
	ki, err := ckf.getCkiIfActiveNow(kid)
	if err != nil {
		return nil, err
	}
	if ki.Sibkey {
		return nil, BadKeyError{fmt.Sprintf("The key '%s' was delegated as a sibkey", kid.String())}
	}
	key, err := ckf.FindKeyWithKIDUnsafe(kid)
	if err != nil {
		return nil, err
	}
	if !CanEncrypt(key) {
		return nil, BadKeyError{fmt.Sprintf("The key '%s' cannot encrypt", kid.String())}
	}
	return key, nil
}

// GetEncryptionSubkeyForDevice gets the current encryption subkey for the given
// device.  Note that many devices might share an encryption public key but
// might have different secret keys.
func (ckf *ComputedKeyFamily) GetEncryptionSubkeyForDevice(did keybase1.DeviceID) (key GenericKey, err error) {
	var kid keybase1.KID
	if kid, err = ckf.getSibkeyKidForDevice(did); err != nil {
		return
	}
	if kid.IsNil() {
		return
	}
	if cki, found := ckf.cki.Infos[kid]; !found {
		return
	} else if !cki.Subkey.IsValid() {
		return
	} else {
		key, err = ckf.FindActiveEncryptionSubkey(cki.Subkey)
	}
	return
}

func makeKeyArgs(sigID keybase1.SigID, sig []byte, delType libkb.DelegationType, key libkb.GenericKey, eldestKID, signingKID keybase1.KID) (*libkb.HTTPArgs, error) {
	pub, err := key.Encode()
	if err != nil {
		return nil, err
	}
	args := libkb.HTTPArgs{
		"sig_id_base":     libkb.S{Val: sigID.ToString(false)},
		"sig_id_short":    libkb.S{Val: sigID.ToShortID()},
		"sig":             libkb.S{Val: string(sig)},
		"type":            libkb.S{Val: string(delType)},
		"is_remote_proof": libkb.B{Val: false},
		"public_key":      libkb.S{Val: pub},
		"eldest_kid":      libkb.S{Val: eldestKID.String()},
		"signing_kid":     libkb.S{Val: signingKID.String()},
	}
	return &args, nil
}

func (l *SigChainLoader) LoadLinksFromStorage() (err error) {
	var curr LinkID
	var links []*ChainLink
	var mt *MerkleTriple
	goodKey := true

	uid := l.user.GetUID()

	l.G().Log.Debug("+ SigChainLoader.LoadFromStorage(%s)", uid)
	defer func() { l.G().Log.Debug("- SigChainLoader.LoadFromStorage(%s) -> %s", uid, ErrToOk(err)) }()

	if mt, err = l.LoadLastLinkIDFromStorage(); err != nil || mt == nil {
		l.G().Log.Debug("| Failed to load last link ID")
		if err == nil {
			l.G().Log.Debug("| no error loading last link ID from storage")
		}
		if mt == nil {
			l.G().Log.Debug("| mt (MerkleTriple) nil result from load last link ID from storage")
		}
		return err
	}

	// Load whatever the last fingerprint was in the chain if we're not loading
	// allKeys. We have to load something...  Note that we don't use l.fp
	// here (as we used to) since if the user used to have chainlinks, and then
	// removed their key, we still want to load their last chainlinks.
	var loadKID keybase1.KID

	curr = mt.LinkID
	var link *ChainLink

	suid := l.selfUID()

	for curr != nil && goodKey {
		l.G().VDL.Log(VLog1, "| loading link; curr=%s", curr)
		if link, err = ImportLinkFromStorage(curr, suid, l.G()); err != nil {
			return
		}
		kid2 := link.ToEldestKID()

		if loadKID.IsNil() {
			loadKID = kid2
			l.G().Log.Debug("| Setting loadKID=%s", kid2)
		} else if !l.allKeys && loadKID.Exists() && !loadKID.Equal(kid2) {
			goodKey = false
			l.G().Log.Debug("| Stop loading at KID=%s (!= KID=%s)", loadKID, kid2)
		}

		if goodKey {
			links = append(links, link)
			curr = link.GetPrev()
		}
	}

	reverse(links)
	l.G().Log.Debug("| Loaded %d links", len(links))

	l.links = links
	return
}

func (e *loginProvision) uidByKID(kid keybase1.KID) (keybase1.UID, error) {
	var nilUID keybase1.UID
	arg := libkb.APIArg{
		Endpoint:     "key/owner",
		NeedSession:  false,
		Contextified: libkb.NewContextified(e.G()),
		Args:         libkb.HTTPArgs{"kid": libkb.S{Val: kid.String()}},
	}
	res, err := e.G().API.Get(arg)
	if err != nil {
		return nilUID, err
	}
	suid, err := res.Body.AtPath("uid").GetString()
	if err != nil {
		return nilUID, err
	}
	return keybase1.UIDFromString(suid)
}

// UpdateDevices takes the Device object from the given ChainLink
// and updates keys to reflects any device changes encoded therein.
func (ckf *ComputedKeyFamily) UpdateDevices(tcl TypedChainLink) (err error) {

	G.Log.Debug("+ UpdateDevice")
	defer func() {
		G.Log.Debug("- UpdateDevice -> %s", ErrToOk(err))
	}()
	var dobj *Device
	if dobj = tcl.GetDevice(); dobj == nil {
		return
	}

	did := dobj.ID
	kid := dobj.Kid

	G.Log.Debug("| Device ID=%s; KID=%s", did, kid.String())

	var prevKid keybase1.KID
	if existing, found := ckf.cki.Devices[did]; found {
		G.Log.Debug("| merge with existing")
		prevKid = existing.Kid
		existing.Merge(dobj)
		dobj = existing
	} else {
		G.Log.Debug("| New insert")
		ckf.cki.Devices[did] = dobj
	}

	// Clear out the old Key that this device used to refer to.
	// We might wind up just clobbering it with the same thing, but
	// that's fine for now.
	if prevKid.IsValid() {
		G.Log.Debug("| Clear out old key")
		delete(ckf.cki.KIDToDeviceID, prevKid)
	}

	if kid.IsValid() {
		ckf.cki.KIDToDeviceID[kid] = did
	}

	return
}

// UpdateDevices takes the Device object from the given ChainLink
// and updates keys to reflects any device changes encoded therein.
func (ckf *ComputedKeyFamily) UpdateDevices(tcl TypedChainLink) (err error) {

	var dobj *Device
	if dobj = tcl.GetDevice(); dobj == nil {
		ckf.G().VDL.Log(VLog1, "Short-circuit of UpdateDevices(); not a device link")
		return
	}

	defer ckf.G().Trace("UpdateDevice", func() error { return err })()

	did := dobj.ID
	kid := dobj.Kid

	ckf.G().Log.Debug("| Device ID=%s; KID=%s", did, kid.String())

	var prevKid keybase1.KID
	if existing, found := ckf.cki.Devices[did]; found {
		ckf.G().Log.Debug("| merge with existing")
		prevKid = existing.Kid
		existing.Merge(dobj)
		dobj = existing
	} else {
		ckf.G().Log.Debug("| New insert")
		ckf.cki.Devices[did] = dobj
	}

	// Clear out the old Key that this device used to refer to.
	// We might wind up just clobbering it with the same thing, but
	// that's fine for now.
	if prevKid.IsValid() {
		ckf.G().Log.Debug("| Clear out old key")
		delete(ckf.cki.KIDToDeviceID, prevKid)
	}

	if kid.IsValid() {
		ckf.cki.KIDToDeviceID[kid] = did
	}

	return
}

// UpdateDevices takes the Device object from the given ChainLink
// and updates keys to reflects any device changes encoded therein.
func (ckf *ComputedKeyFamily) UpdateDevices(tcl TypedChainLink) (err error) {

	var dobj *Device
	if dobj = tcl.GetDevice(); dobj == nil {
		ckf.G().VDL.Log(VLog1, "Short-circuit of UpdateDevices(); not a device link")
		return
	}

	defer ckf.G().Trace("UpdateDevice", func() error { return err })()

	did := dobj.ID
	kid := dobj.Kid

	ckf.G().Log.Debug("| Device ID=%s; KID=%s", did, kid.String())

	var prevKid keybase1.KID
	if existing, found := ckf.cki.Devices[did]; found {
		ckf.G().Log.Debug("| merge with existing")
		prevKid = existing.Kid
		existing.Merge(dobj)
		dobj = existing
	} else {
		ckf.G().Log.Debug("| New insert")
		ckf.cki.Devices[did] = dobj
	}

	// If a KID is specified, we should clear out any previous KID from the
	// KID->Device map. But if not, leave the map as it is. Later "device"
	// blobs in the sigchain aren't required to repeat the KID every time.
	if kid.IsValid() {
		if prevKid.IsValid() {
			ckf.G().Log.Debug("| Clear out old key")
			delete(ckf.cki.KIDToDeviceID, prevKid)
		}
		ckf.cki.KIDToDeviceID[kid] = did
	}

	return
}

func (e *LoginProvision) loadUserByKID(kid keybase1.KID) (*libkb.User, error) {
	arg := libkb.APIArg{
		Endpoint:     "key/owner",
		NeedSession:  false,
		Contextified: libkb.NewContextified(e.G()),
		Args:         libkb.HTTPArgs{"kid": libkb.S{Val: kid.String()}},
	}
	res, err := e.G().API.Get(arg)
	if err != nil {
		return nil, err
	}
	suid, err := res.Body.AtPath("uid").GetString()
	if err != nil {
		return nil, err
	}
	uid, err := keybase1.UIDFromString(suid)
	if err != nil {
		return nil, err
	}
	e.G().Log.Debug("key/owner result uid: %s", uid)
	loadArg := libkb.NewLoadUserArg(e.G())
	loadArg.UID = uid
	return libkb.LoadUser(loadArg)
}

func (k SKBKeyringFile) SearchWithComputedKeyFamily(ckf *ComputedKeyFamily, ska SecretKeyArg) []*SKB {
	var kid keybase1.KID
	G.Log.Debug("+ SKBKeyringFile.SearchWithComputedKeyFamily")
	defer func() {
		var res string
		if kid.Exists() {
			res = kid.String()
		} else {
			res = "<nil>"
		}
		G.Log.Debug("- SKBKeyringFile.SearchWithComputedKeyFamily -> %s\n", res)
	}()
	G.Log.Debug("| Searching %d possible blocks", len(k.Blocks))
	var blocks []*SKB
	for i := len(k.Blocks) - 1; i >= 0; i-- {
		G.Log.Debug("| trying key index# -> %d", i)
		if key, err := k.Blocks[i].GetPubKey(); err == nil && key != nil {
			kid = key.GetKID()
			active := ckf.GetKeyRole(kid)
			G.Log.Debug("| Checking KID: %s -> %d", kid, int(active))
			if !ska.KeyType.nonDeviceKeyMatches(key) {
				G.Log.Debug("| Skipped, doesn't match type=%s", ska.KeyType)
			} else if !KeyMatchesQuery(key, ska.KeyQuery, ska.ExactMatch) {
				G.Log.Debug("| Skipped, doesn't match query=%s", ska.KeyQuery)

			} else if active != DLGSibkey {
				G.Log.Debug("| Skipped, active=%d", int(active))
			} else {
				blocks = append(blocks, k.Blocks[i])
			}
		} else {
			G.Log.Debug("| failed --> %v", err)
		}
	}
	return blocks
}