5 files changed, 1007 insertions, 0 deletions
diff --git a/src/metadata/drop.rs b/src/metadata/drop.rs
new file mode 100644
index 0000000..d231712
--- /dev/null
+++ b/src/metadata/drop.rs
@@ -0,0 +1,274 @@
+// Copyright © 2022 Kim Altintop <kim@eagain.io>
+// SPDX-License-Identifier: GPL-2.0-only WITH openvpn-openssl-exception
+
+use std::{
+    borrow::Cow,
+    collections::{
+        BTreeMap,
+        BTreeSet,
+        HashMap,
+    },
+    io,
+    num::NonZeroUsize,
+};
+
+use log::warn;
+use sha2::{
+    Digest,
+    Sha512,
+};
+use signature::Verifier;
+
+use super::{
+    error,
+    Alternates,
+    ContentHash,
+    Custom,
+    DateTime,
+    IdentityId,
+    KeyId,
+    KeySet,
+    Metadata,
+    Mirrors,
+    Signature,
+    Signed,
+    SpecVersion,
+};
+use crate::{
+    git::Refname,
+    json::canonical,
+    str::Varchar,
+};
+
+#[derive(Clone, serde::Serialize, serde::Deserialize)]
+pub struct Roles {
+    pub root: Role,
+    pub snapshot: Role,
+    pub mirrors: Role,
+    pub branches: HashMap<Refname, Annotated>,
+}
+
+impl Roles {
+    pub(crate) fn ids(&self) -> BTreeSet<IdentityId> {
+        let Self {
+            root: Role { ids: root, .. },
+            snapshot: Role { ids: snapshot, .. },
+            mirrors: Role { ids: mirrors, .. },
+            branches,
+        } = self;
+
+        let mut ids = BTreeSet::new();
+        ids.extend(root);
+        ids.extend(snapshot);
+        ids.extend(mirrors);
+        ids.extend(branches.values().flat_map(|a| &a.role.ids));
+        ids
+    }
+}
+
+#[derive(Clone, serde::Serialize, serde::Deserialize)]
+pub struct Role {
+    pub ids: BTreeSet<IdentityId>,
+    pub threshold: NonZeroUsize,
+}
+
+pub type Description = Varchar<String, 128>;
+
+#[derive(Clone, serde::Serialize, serde::Deserialize)]
+pub struct Annotated {
+    #[serde(flatten)]
+    pub role: Role,
+    pub description: Description,
+}
+
+pub type Verified = super::Verified<Drop>;
+
+#[derive(Clone, serde::Serialize, serde::Deserialize)]
+pub struct Drop {
+    pub spec_version: SpecVersion,
+    #[serde(default = "Description::new")]
+    pub description: Description,
+    pub prev: Option<ContentHash>,
+    pub roles: Roles,
+    #[serde(default)]
+    pub custom: Custom,
+}
+
+impl Drop {
+    pub fn verified<'a, F, G>(
+        self,
+        signatures: &BTreeMap<KeyId, Signature>,
+        find_prev: F,
+        find_signer: G,
+    ) -> Result<Verified, error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+        G: FnMut(&IdentityId) -> io::Result<KeySet<'a>>,
+    {
+        self.verify(signatures, find_prev, find_signer)?;
+        Ok(super::Verified(self))
+    }
+
+    pub fn verify<'a, F, G>(
+        &self,
+        signatures: &BTreeMap<KeyId, Signature>,
+        mut find_prev: F,
+        mut find_signer: G,
+    ) -> Result<(), error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+        G: FnMut(&IdentityId) -> io::Result<KeySet<'a>>,
+    {
+        use error::Verification::*;
+
+        if !crate::SPEC_VERSION.is_compatible(&self.spec_version) {
+            return Err(IncompatibleSpecVersion);
+        }
+
+        let canonical = self.canonicalise()?;
+        let payload = Sha512::digest(&canonical);
+        verify::AuthorisedSigners::from_ids(&self.roles.root.ids, &mut find_signer)?
+            .verify_signatures(&payload, self.roles.root.threshold, signatures)?;
+        if let Some(prev) = self.prev.as_ref().map(&mut find_prev).transpose()? {
+            verify::AuthorisedSigners::from_ids(&prev.signed.roles.root.ids, &mut find_signer)?
+                .verify_signatures(&payload, prev.signed.roles.root.threshold, signatures)?;
+            return prev.signed.verify(&prev.signatures, find_prev, find_signer);
+        }
+
+        Ok(())
+    }
+
+    pub fn verify_mirrors<'a, F>(
+        &self,
+        mirrors: &Signed<Mirrors>,
+        find_signer: F,
+    ) -> Result<(), error::Verification>
+    where
+        F: FnMut(&IdentityId) -> io::Result<KeySet<'a>>,
+    {
+        use error::Verification::*;
+
+        if let Some(deadline) = &mirrors.signed.expires {
+            if deadline < &DateTime::now() {
+                return Err(Expired);
+            }
+        }
+        if !crate::SPEC_VERSION.is_compatible(&mirrors.signed.spec_version) {
+            return Err(IncompatibleSpecVersion);
+        }
+
+        let payload = Sha512::digest(mirrors.signed.canonicalise()?);
+        verify::AuthorisedSigners::from_ids(&self.roles.mirrors.ids, find_signer)?
+            .verify_signatures(&payload, self.roles.mirrors.threshold, &mirrors.signatures)
+    }
+
+    pub fn verify_alternates<'a, F>(
+        &self,
+        alt: &Signed<Alternates>,
+        find_signer: F,
+    ) -> Result<(), error::Verification>
+    where
+        F: FnMut(&IdentityId) -> io::Result<KeySet<'a>>,
+    {
+        use error::Verification::*;
+
+        if let Some(deadline) = &alt.signed.expires {
+            if deadline < &DateTime::now() {
+                return Err(Expired);
+            }
+        }
+        if !crate::SPEC_VERSION.is_compatible(&alt.signed.spec_version) {
+            return Err(IncompatibleSpecVersion);
+        }
+
+        let payload = Sha512::digest(alt.signed.canonicalise()?);
+        verify::AuthorisedSigners::from_ids(&self.roles.mirrors.ids, find_signer)?
+            .verify_signatures(&payload, self.roles.mirrors.threshold, &alt.signatures)
+    }
+
+    pub fn canonicalise(&self) -> Result<Vec<u8>, canonical::error::Canonicalise> {
+        canonical::to_vec(Metadata::drop(self))
+    }
+}
+
+impl From<Drop> for Cow<'static, Drop> {
+    fn from(d: Drop) -> Self {
+        Self::Owned(d)
+    }
+}
+
+impl<'a> From<&'a Drop> for Cow<'a, Drop> {
+    fn from(d: &'a Drop) -> Self {
+        Self::Borrowed(d)
+    }
+}
+
+mod verify {
+    use super::*;
+
+    pub struct AuthorisedSigners<'a, 'b>(BTreeMap<&'a IdentityId, KeySet<'b>>);
+
+    impl<'a, 'b> AuthorisedSigners<'a, 'b> {
+        pub fn from_ids<F>(
+            ids: &'a BTreeSet<IdentityId>,
+            mut find_signer: F,
+        ) -> Result<AuthorisedSigners<'a, 'b>, error::Verification>
+        where
+            F: FnMut(&IdentityId) -> io::Result<KeySet<'b>>,
+        {
+            let mut signers = BTreeMap::new();
+            for id in ids {
+                signers.insert(id, find_signer(id)?);
+            }
+            signers
+                .values()
+                .try_fold(BTreeSet::new(), |mut all_keys, keys| {
+                    for key in keys.keys() {
+                        if !all_keys.insert(key) {
+                            return Err(error::Verification::DuplicateKey(*key));
+                        }
+                    }
+
+                    Ok(all_keys)
+                })?;
+
+            Ok(Self(signers))
+        }
+
+        pub fn verify_signatures<'c, S>(
+            &mut self,
+            payload: &[u8],
+            threshold: NonZeroUsize,
+            signatures: S,
+        ) -> Result<(), error::Verification>
+        where
+            S: IntoIterator<Item = (&'c KeyId, &'c Signature)>,
+        {
+            use error::Verification::SignatureThreshold;
+
+            let mut need_signatures = threshold.get();
+            for (key_id, signature) in signatures {
+                if let Some(sig_id) = self.0.iter().find_map(|(id, keys)| {
+                    #[allow(clippy::unnecessary_lazy_evaluations)]
+                    keys.contains_key(key_id).then(|| *id)
+                }) {
+                    let key = self.0.remove(sig_id).unwrap().remove(key_id).unwrap();
+                    if key.verify(payload, signature).is_ok() {
+                        need_signatures -= 1;
+                    } else {
+                        warn!("Bad signature by {key_id}");
+                    }
+
+                    if need_signatures == 0 {
+                        break;
+                    }
+                }
+            }
+            if need_signatures > 0 {
+                return Err(SignatureThreshold);
+            }
+
+            Ok(())
+        }
+    }
+}
diff --git a/src/metadata/error.rs b/src/metadata/error.rs
new file mode 100644
index 0000000..66173f9
--- /dev/null
+++ b/src/metadata/error.rs
@@ -0,0 +1,40 @@
+// Copyright © 2022 Kim Altintop <kim@eagain.io>
+// SPDX-License-Identifier: GPL-2.0-only WITH openvpn-openssl-exception
+
+use std::io;
+
+use thiserror::Error;
+
+use super::KeyId;
+use crate::json::canonical::error::Canonicalise;
+
+#[derive(Debug, Error)]
+pub enum SigId {
+    #[error("payload not at root revision")]
+    NotRoot,
+
+    #[error("invalid payload: canonicalisation failed")]
+    Canonical(#[from] Canonicalise),
+}
+
+#[derive(Debug, Error)]
+#[non_exhaustive]
+pub enum Verification {
+    #[error("incompatible spec version")]
+    IncompatibleSpecVersion,
+
+    #[error("canonicalisation failed")]
+    Canonicalise(#[from] Canonicalise),
+
+    #[error("required signature threshold not met")]
+    SignatureThreshold,
+
+    #[error("metadata past its expiry date")]
+    Expired,
+
+    #[error("duplicate key: key {0} appears in more than one identity")]
+    DuplicateKey(KeyId),
+
+    #[error(transparent)]
+    Io(#[from] io::Error),
+}
diff --git a/src/metadata/git.rs b/src/metadata/git.rs
new file mode 100644
index 0000000..1dde3da
--- /dev/null
+++ b/src/metadata/git.rs
@@ -0,0 +1,232 @@
+// Copyright © 2022 Kim Altintop <kim@eagain.io>
+// SPDX-License-Identifier: GPL-2.0-only WITH openvpn-openssl-exception
+
+use std::{
+    borrow::Cow,
+    io,
+};
+
+use anyhow::anyhow;
+
+use super::{
+    drop,
+    identity,
+    Alternates,
+    ContentHash,
+    Drop,
+    Identity,
+    IdentityId,
+    KeySet,
+    Metadata,
+    Mirrors,
+    Signed,
+};
+use crate::{
+    cmd,
+    git::if_not_found_none,
+    json,
+};
+
+pub const META_FILE_ALTERNATES: &str = "alternates.json";
+pub const META_FILE_DROP: &str = "drop.json";
+pub const META_FILE_ID: &str = "id.json";
+pub const META_FILE_MIRRORS: &str = "mirrors.json";
+
+pub mod error {
+    use thiserror::Error;
+
+    #[derive(Debug, Error)]
+    #[error("unexpected metadata type")]
+    pub struct TypeMismatch;
+
+    #[derive(Debug, Error)]
+    #[error("{file} not found in tree")]
+    pub struct FileNotFound {
+        pub file: &'static str,
+    }
+}
+
+pub struct GitMeta<T> {
+    pub hash: ContentHash,
+    pub signed: Signed<T>,
+}
+
+pub type GitIdentity = GitMeta<Identity>;
+pub type GitDrop = GitMeta<Drop>;
+pub type GitMirrors = GitMeta<Mirrors>;
+pub type GitAlternates = GitMeta<Alternates>;
+
+impl GitMeta<Drop> {
+    pub fn verified<'a, F, G>(
+        self,
+        find_prev: F,
+        find_signer: G,
+    ) -> Result<drop::Verified, super::error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Drop>>,
+        G: FnMut(&IdentityId) -> io::Result<KeySet<'a>>,
+    {
+        self.signed.verified(find_prev, find_signer)
+    }
+}
+
+impl GitMeta<Identity> {
+    pub fn verified<F>(self, find_prev: F) -> Result<identity::Verified, super::error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Identity>>,
+    {
+        self.signed.verified(find_prev)
+    }
+}
+
+pub struct FromSearchPath<'a, T> {
+    /// The repository (from the search path) the object was found in
+    pub repo: &'a git2::Repository,
+    pub meta: GitMeta<T>,
+}
+
+pub trait FromGit: Sized + Clone
+where
+    for<'a> Cow<'a, Self>: TryFrom<Metadata<'a>>,
+{
+    const METADATA_JSON: &'static str;
+
+    fn from_blob(blob: &git2::Blob) -> crate::Result<GitMeta<Self>> {
+        let hash = ContentHash::from(blob);
+        let signed = json::from_blob::<Signed<Metadata>>(blob)?
+            .fmap(Cow::<Self>::try_from)
+            .transpose()
+            .map_err(|_| error::TypeMismatch)?
+            .fmap(Cow::into_owned);
+
+        Ok(GitMeta { hash, signed })
+    }
+
+    fn from_tip<R: AsRef<str>>(
+        repo: &git2::Repository,
+        refname: R,
+    ) -> crate::Result<GitMeta<Self>> {
+        Self::from_reference(repo, &repo.find_reference(refname.as_ref())?)
+    }
+
+    fn from_reference(
+        repo: &git2::Repository,
+        reference: &git2::Reference,
+    ) -> crate::Result<GitMeta<Self>> {
+        Self::from_commit(repo, &reference.peel_to_commit()?)
+    }
+
+    fn from_commit(repo: &git2::Repository, commit: &git2::Commit) -> crate::Result<GitMeta<Self>> {
+        Self::from_tree(repo, &commit.tree()?)
+    }
+
+    fn from_tree(repo: &git2::Repository, tree: &git2::Tree) -> crate::Result<GitMeta<Self>> {
+        let entry = tree
+            .get_name(Self::METADATA_JSON)
+            .ok_or(error::FileNotFound {
+                file: Self::METADATA_JSON,
+            })?;
+        let blob = entry.to_object(repo)?.peel_to_blob()?;
+
+        Self::from_blob(&blob)
+    }
+
+    fn from_content_hash(
+        repo: &git2::Repository,
+        hash: &ContentHash,
+    ) -> crate::Result<GitMeta<Self>> {
+        let blob = repo.find_blob(hash.into())?;
+        Self::from_blob(&blob)
+    }
+
+    fn from_search_path<R: AsRef<str>>(
+        search_path: &[git2::Repository],
+        refname: R,
+    ) -> crate::Result<FromSearchPath<Self>> {
+        let (repo, reference) = find_ref_in_path(search_path, refname.as_ref())?
+            .ok_or_else(|| anyhow!("{} not found in search path", refname.as_ref()))?;
+        Self::from_reference(repo, &reference).map(|meta| FromSearchPath { repo, meta })
+    }
+}
+
+impl FromGit for Identity {
+    const METADATA_JSON: &'static str = META_FILE_ID;
+}
+
+impl FromGit for Drop {
+    const METADATA_JSON: &'static str = META_FILE_DROP;
+}
+
+impl FromGit for Mirrors {
+    const METADATA_JSON: &'static str = META_FILE_MIRRORS;
+}
+
+impl FromGit for Alternates {
+    const METADATA_JSON: &'static str = META_FILE_ALTERNATES;
+}
+
+pub fn find_parent<T>(
+    repo: &git2::Repository,
+) -> impl Fn(&ContentHash) -> io::Result<Signed<T>> + '_
+where
+    T: FromGit,
+    for<'a> Cow<'a, T>: TryFrom<Metadata<'a>>,
+{
+    |hash| {
+        T::from_content_hash(repo, hash)
+            .map_err(as_io)
+            .map(|meta| meta.signed)
+    }
+}
+
+pub fn find_parent_in_tree<'a, T>(
+    repo: &'a git2::Repository,
+    tree: &'a git2::Tree<'a>,
+) -> impl Fn(&ContentHash) -> io::Result<Signed<T>> + 'a
+where
+    T: FromGit,
+    for<'b> Cow<'b, T>: TryFrom<Metadata<'b>>,
+{
+    fn go<T>(
+        repo: &git2::Repository,
+        tree: &git2::Tree,
+        hash: &ContentHash,
+    ) -> crate::Result<Signed<T>>
+    where
+        T: FromGit,
+        for<'b> Cow<'b, T>: TryFrom<Metadata<'b>>,
+    {
+        let oid = git2::Oid::from(hash);
+        let blob = tree
+            .get_id(oid)
+            .ok_or_else(|| anyhow!("parent {} not found in tree {}", oid, tree.id()))?
+            .to_object(repo)?
+            .into_blob()
+            .map_err(|_| anyhow!("parent {} is not a file", oid))?;
+
+        T::from_blob(&blob).map(|meta| meta.signed)
+    }
+
+    move |hash| go(repo, tree, hash).map_err(as_io)
+}
+
+pub fn find_ref_in_path<'a>(
+    search_path: &'a [git2::Repository],
+    name: &str,
+) -> cmd::Result<Option<(&'a git2::Repository, git2::Reference<'a>)>> {
+    for repo in search_path {
+        let have_ref = if_not_found_none(repo.resolve_reference_from_short_name(name))?;
+        if let Some(r) = have_ref {
+            return Ok(Some((repo, r)));
+        }
+    }
+
+    Ok(None)
+}
+
+fn as_io<E>(e: E) -> io::Error
+where
+    E: Into<Box<dyn std::error::Error + Send + Sync>>,
+{
+    io::Error::new(io::ErrorKind::Other, e)
+}
diff --git a/src/metadata/identity.rs b/src/metadata/identity.rs
new file mode 100644
index 0000000..8071e84
--- /dev/null
+++ b/src/metadata/identity.rs
@@ -0,0 +1,366 @@
+// Copyright © 2022 Kim Altintop <kim@eagain.io>
+// SPDX-License-Identifier: GPL-2.0-only WITH openvpn-openssl-exception
+
+use std::{
+    borrow::Cow,
+    collections::{
+        BTreeMap,
+        BTreeSet,
+    },
+    fmt,
+    io,
+    marker::PhantomData,
+    num::NonZeroUsize,
+    path::PathBuf,
+    str::FromStr,
+};
+
+use anyhow::{
+    anyhow,
+    ensure,
+};
+use hex::FromHex;
+use log::warn;
+use sha2::{
+    Digest,
+    Sha256,
+    Sha512,
+};
+use signature::Verifier;
+use url::Url;
+
+use super::{
+    error,
+    git::{
+        find_parent_in_tree,
+        FromGit,
+        META_FILE_ID,
+    },
+    Ancestors,
+    ContentHash,
+    Custom,
+    DateTime,
+    Key,
+    KeyId,
+    KeySet,
+    Metadata,
+    Signature,
+    Signed,
+    SpecVersion,
+};
+use crate::{
+    json::{
+        self,
+        canonical,
+    },
+    metadata::git::find_parent,
+};
+
+#[derive(
+    Clone, Copy, Eq, Ord, PartialEq, PartialOrd, Hash, serde::Serialize, serde::Deserialize,
+)]
+pub struct IdentityId(#[serde(with = "hex::serde")] [u8; 32]);
+
+impl TryFrom<&Identity> for IdentityId {
+    type Error = error::SigId;
+
+    fn try_from(id: &Identity) -> Result<Self, Self::Error> {
+        if id.prev.is_some() {
+            return Err(error::SigId::NotRoot);
+        }
+        let digest = Sha256::digest(id.canonicalise()?);
+        Ok(Self(digest.into()))
+    }
+}
+
+impl fmt::Display for IdentityId {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.write_str(&hex::encode(self.0))
+    }
+}
+
+impl fmt::Debug for IdentityId {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        f.write_str(&self.to_string())
+    }
+}
+
+impl FromStr for IdentityId {
+    type Err = hex::FromHexError;
+
+    fn from_str(s: &str) -> Result<Self, Self::Err> {
+        FromHex::from_hex(s).map(Self)
+    }
+}
+
+impl TryFrom<String> for IdentityId {
+    type Error = hex::FromHexError;
+
+    fn try_from(value: String) -> Result<Self, Self::Error> {
+        FromHex::from_hex(value).map(Self)
+    }
+}
+
+pub struct Verified {
+    id: IdentityId,
+    cur: Identity,
+}
+
+impl Verified {
+    pub fn id(&self) -> &IdentityId {
+        &self.id
+    }
+
+    pub fn identity(&self) -> &Identity {
+        &self.cur
+    }
+
+    pub fn into_parts(self) -> (IdentityId, Identity) {
+        (self.id, self.cur)
+    }
+
+    /// `true` if signature is valid over message for any of the signer's
+    /// _current_ set of keys
+    pub fn did_sign<T: AsRef<[u8]>>(&self, msg: T, sig: &Signature) -> bool {
+        self.cur
+            .keys
+            .values()
+            .any(|key| key.verify(msg.as_ref(), sig).is_ok())
+    }
+}
+
+impl AsRef<Identity> for Verified {
+    fn as_ref(&self) -> &Identity {
+        self.identity()
+    }
+}
+
+#[derive(Clone, serde::Serialize, serde::Deserialize)]
+pub struct Identity {
+    pub spec_version: SpecVersion,
+    pub prev: Option<ContentHash>,
+    pub keys: KeySet<'static>,
+    pub threshold: NonZeroUsize,
+    pub mirrors: BTreeSet<Url>,
+    pub expires: Option<DateTime>,
+    #[serde(default)]
+    pub custom: Custom,
+}
+
+impl Identity {
+    pub fn verified<F>(
+        self,
+        signatures: &BTreeMap<KeyId, Signature>,
+        find_prev: F,
+    ) -> Result<Verified, error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+    {
+        let id = self.verify(signatures, find_prev)?;
+        Ok(Verified { id, cur: self })
+    }
+
+    pub fn verify<F>(
+        &self,
+        signatures: &BTreeMap<KeyId, Signature>,
+        find_prev: F,
+    ) -> Result<IdentityId, error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+    {
+        use error::Verification::Expired;
+
+        if let Some(deadline) = &self.expires {
+            if deadline < &DateTime::now() {
+                return Err(Expired);
+            }
+        }
+        self.verify_tail(Cow::Borrowed(signatures), find_prev)
+    }
+
+    fn verify_tail<F>(
+        &self,
+        signatures: Cow<BTreeMap<KeyId, Signature>>,
+        mut find_prev: F,
+    ) -> Result<IdentityId, error::Verification>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+    {
+        use error::Verification::IncompatibleSpecVersion;
+
+        if !crate::SPEC_VERSION.is_compatible(&self.spec_version) {
+            return Err(IncompatibleSpecVersion);
+        }
+
+        let canonical = self.canonicalise()?;
+        let signed = Sha512::digest(&canonical);
+        verify_signatures(&signed, self.threshold, signatures.iter(), &self.keys)?;
+        if let Some(prev) = self.prev.as_ref().map(&mut find_prev).transpose()? {
+            verify_signatures(
+                &signed,
+                prev.signed.threshold,
+                signatures.iter(),
+                &prev.signed.keys,
+            )?;
+            return prev
+                .signed
+                .verify_tail(Cow::Owned(prev.signatures), find_prev);
+        }
+
+        Ok(IdentityId(Sha256::digest(canonical).into()))
+    }
+
+    pub fn canonicalise(&self) -> Result<Vec<u8>, canonical::error::Canonicalise> {
+        canonical::to_vec(Metadata::identity(self))
+    }
+
+    pub fn ancestors<F>(&self, find_prev: F) -> impl Iterator<Item = io::Result<Signed<Self>>>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+    {
+        Ancestors {
+            prev: self.prev.clone(),
+            find_prev,
+            _marker: PhantomData,
+        }
+    }
+
+    pub fn has_ancestor<F>(&self, ancestor: &ContentHash, find_prev: F) -> io::Result<bool>
+    where
+        F: FnMut(&ContentHash) -> io::Result<Signed<Self>>,
+    {
+        match &self.prev {
+            None => Ok(false),
+            Some(parent) if parent == ancestor => Ok(true),
+            Some(_) => {
+                for prev in self.ancestors(find_prev) {
+                    match &prev?.signed.prev {
+                        None => return Ok(false),
+                        Some(parent) if parent == ancestor => return Ok(true),
+                        _ => continue,
+                    }
+                }
+
+                Ok(false)
+            },
+        }
+    }
+}
+
+impl From<Identity> for Cow<'static, Identity> {
+    fn from(s: Identity) -> Self {
+        Self::Owned(s)
+    }
+}
+
+impl<'a> From<&'a Identity> for Cow<'a, Identity> {
+    fn from(s: &'a Identity) -> Self {
+        Self::Borrowed(s)
+    }
+}
+
+fn verify_signatures<'a, S>(
+    payload: &[u8],
+    threshold: NonZeroUsize,
+    signatures: S,
+    keys: &BTreeMap<KeyId, Key>,
+) -> Result<(), error::Verification>
+where
+    S: IntoIterator<Item = (&'a KeyId, &'a Signature)>,
+{
+    use error::Verification::SignatureThreshold;
+
+    let mut need_signatures = threshold.get();
+    for (key_id, signature) in signatures {
+        if let Some(key) = keys.get(key_id) {
+            if key.verify(payload, signature).is_ok() {
+                need_signatures -= 1;
+            } else {
+                warn!("Bad signature by {key_id}");
+            }
+
+            if need_signatures == 0 {
+                break;
+            }
+        }
+    }
+    if need_signatures > 0 {
+        return Err(SignatureThreshold);
+    }
+
+    Ok(())
+}
+
+const FOLDED_HISTORY: &str = ".history";
+
+pub fn fold_to_tree<'a>(
+    repo: &'a git2::Repository,
+    tree: &mut git2::TreeBuilder<'a>,
+    Signed { signed, signatures }: Signed<Identity>,
+) -> crate::Result<()> {
+    use git2::FileMode::{
+        Blob,
+        Tree,
+    };
+
+    let meta = Signed {
+        signed: Metadata::from(&signed),
+        signatures,
+    };
+    tree.insert(META_FILE_ID, json::to_blob(repo, &meta)?, Blob.into())?;
+
+    let mut history = {
+        let existing = tree
+            .get(FOLDED_HISTORY)?
+            .map(|t| t.to_object(repo))
+            .transpose()?;
+        repo.treebuilder(existing.as_ref().and_then(git2::Object::as_tree))?
+    };
+    let mut parents = Vec::new();
+    for parent in signed.ancestors(find_parent(repo)) {
+        let meta = parent?.fmap(Metadata::from);
+        let blob = json::to_blob(repo, &meta)?;
+        parents.push(blob);
+    }
+    for (n, oid) in parents.into_iter().rev().enumerate() {
+        history.insert(&format!("{n}.json"), oid, Blob.into())?;
+    }
+    tree.insert(FOLDED_HISTORY, history.write()?, Tree.into())?;
+
+    Ok(())
+}
+
+pub fn find_in_tree(
+    repo: &git2::Repository,
+    root: &git2::Tree,
+    id: &IdentityId,
+) -> crate::Result<Verified> {
+    let (id_path, hist_path) = {
+        let base = PathBuf::from(id.to_string());
+        (base.join(META_FILE_ID), base.join(FOLDED_HISTORY))
+    };
+
+    let blob = root
+        .get_path(&id_path)?
+        .to_object(repo)?
+        .into_blob()
+        .map_err(|_| anyhow!("{} is not a file", id_path.display()))?;
+    let meta = Identity::from_blob(&blob)?.signed;
+    let hist = root
+        .get_path(&hist_path)?
+        .to_object(repo)?
+        .into_tree()
+        .map_err(|_| anyhow!("{} is not a directory", hist_path.display()))?;
+
+    let verified = meta
+        .signed
+        .verified(&meta.signatures, find_parent_in_tree(repo, &hist))?;
+    ensure!(
+        verified.id() == id,
+        "ids don't match after verification: expected {} found {}",
+        id,
+        verified.id()
+    );
+
+    Ok(verified)
+}
diff --git a/src/metadata/mirrors.rs b/src/metadata/mirrors.rs
new file mode 100644
index 0000000..9124dd3
--- /dev/null
+++ b/src/metadata/mirrors.rs
@@ -0,0 +1,95 @@
+// Copyright © 2022 Kim Altintop <kim@eagain.io>
+// SPDX-License-Identifier: GPL-2.0-only WITH openvpn-openssl-exception
+
+use std::{
+    borrow::Cow,
+    collections::BTreeSet,
+};
+
+use url::Url;
+
+use super::{
+    Custom,
+    DateTime,
+    Metadata,
+    SpecVersion,
+};
+use crate::{
+    json::canonical,
+    str::Varchar,
+};
+
+#[derive(Clone, serde::Serialize, serde::Deserialize)]
+pub struct Mirror {
+    pub url: Url,
+    #[serde(default)]
+    pub kind: Kind,
+    #[serde(default)]
+    pub custom: Custom,
+}
+
+#[derive(Clone, Default, serde::Serialize, serde::Deserialize)]
+#[serde(rename_all = "lowercase")]
+pub enum Kind {
+    /// Can fetch bundles
+    Bundled,
+    /// Can fetch packs via git-protocol
+    #[default]
+    Packed,
+    /// Not serving bundles at all
+    Sparse,
+    /// Unknown kind
+    Unknown(Varchar<String, 16>),
+}
+
+#[derive(Clone, Default, serde::Serialize, serde::Deserialize)]
+pub struct Mirrors {
+    pub spec_version: SpecVersion,
+    pub mirrors: Vec<Mirror>,
+    pub expires: Option<DateTime>,
+}
+
+impl Mirrors {
+    pub fn canonicalise(&self) -> Result<Vec<u8>, canonical::error::Canonicalise> {
+        canonical::to_vec(Metadata::mirrors(self))
+    }
+}
+
+impl From<Mirrors> for Cow<'static, Mirrors> {
+    fn from(m: Mirrors) -> Self {
+        Self::Owned(m)
+    }
+}
+
+impl<'a> From<&'a Mirrors> for Cow<'a, Mirrors> {
+    fn from(m: &'a Mirrors) -> Self {
+        Self::Borrowed(m)
+    }
+}
+
+#[derive(Clone, Default, serde::Serialize, serde::Deserialize)]
+pub struct Alternates {
+    pub spec_version: SpecVersion,
+    pub alternates: BTreeSet<Url>,
+    #[serde(default)]
+    pub custom: Custom,
+    pub expires: Option<DateTime>,
+}
+
+impl Alternates {
+    pub fn canonicalise(&self) -> Result<Vec<u8>, canonical::error::Canonicalise> {
+        canonical::to_vec(Metadata::alternates(self))
+    }
+}
+
+impl From<Alternates> for Cow<'static, Alternates> {
+    fn from(a: Alternates) -> Self {
+        Self::Owned(a)
+    }
+}
+
+impl<'a> From<&'a Alternates> for Cow<'a, Alternates> {
+    fn from(a: &'a Alternates) -> Self {
+        Self::Borrowed(a)
+    }
+}