~ knotless Search/
↑↓ move↵ open⇧↵ all results

johnandersen777.bsky.social/atlibs-identlink

ident.link agent-of walk with grants over CAR-verified sync.getRecord: Rust crate identlink, wasm, JS

1 collaborator
0
0
main
306 lines · 9.8 KB Raw History
#![forbid(unsafe_code)]

use std::collections::{HashMap, HashSet, VecDeque};

use chrono::{DateTime, Utc};
use futures::future::{join, join_all};
use serde::{Deserialize, Serialize};
use serde_json::Value;

mod car;
pub mod market;
#[cfg(feature = "native")]
mod http;
#[cfg(feature = "wasm")]
mod wasm;

pub use car::{record_cid, verify_record};
pub use market::market_contract_held;
#[cfg(feature = "native")]
pub use http::{ContractHeldFn, HttpIo};

pub const ENDORSEMENT_NSID: &str = "link.ident.endorsement";
pub const ASSOCIATION_NSID: &str = "com.publicdomainrelay.temp.market.association";
pub const AGENT_OF_PREFIX: &str = "https://ident.link/agent-of/";
pub const MAX_DEPTH: usize = 100;
pub const BUDGET: usize = 256;

pub type Error = Box<dyn std::error::Error + Send + Sync>;

#[derive(Clone, Debug, Default, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct DidDoc {
    #[serde(default)]
    pub id: String,
    #[serde(default)]
    pub also_known_as: Vec<String>,
    #[serde(default)]
    pub verification_method: Vec<VerificationMethod>,
    #[serde(default)]
    pub service: Vec<Service>,
}

#[derive(Clone, Debug, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct VerificationMethod {
    pub id: String,
    #[serde(default)]
    pub public_key_multibase: Option<String>,
}

#[derive(Clone, Debug, Deserialize)]
#[serde(rename_all = "camelCase")]
pub struct Service {
    pub id: String,
    #[serde(rename = "type", default)]
    pub kind: String,
    #[serde(default)]
    pub service_endpoint: Value,
}

impl DidDoc {
    pub fn signing_key(&self) -> Option<&str> {
        self.verification_method
            .iter()
            .find(|m| self.is_fragment(&m.id, "#atproto"))?
            .public_key_multibase
            .as_deref()
    }

    pub fn pds(&self) -> Option<&str> {
        self.service
            .iter()
            .find(|s| self.is_fragment(&s.id, "#atproto_pds") && s.kind == "AtprotoPersonalDataServer")?
            .service_endpoint
            .as_str()
    }

    fn is_fragment(&self, id: &str, fragment: &str) -> bool {
        id == fragment || id.strip_prefix(self.id.as_str()) == Some(fragment)
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Hash, Deserialize, Serialize)]
pub struct StrongRef {
    pub uri: String,
    pub cid: String,
}

#[derive(Clone, Copy, Debug, Deserialize)]
#[serde(rename_all = "camelCase", default)]
pub struct Options {
    pub max_depth: usize,
    pub budget: usize,
}

impl Default for Options {
    fn default() -> Self {
        Self { max_depth: MAX_DEPTH, budget: BUDGET }
    }
}

#[derive(Clone, Debug, PartialEq, Eq, Deserialize, Serialize)]
#[serde(rename_all = "camelCase")]
pub struct Ancestor {
    pub did: String,
    pub depth: usize,
    #[serde(default, skip_serializing_if = "Option::is_none")]
    pub expires_at: Option<DateTime<Utc>>,
}

#[derive(Clone, Debug, PartialEq, Eq, Serialize)]
#[serde(rename_all = "camelCase")]
pub struct Walk {
    pub agent: String,
    pub ancestors: Vec<Ancestor>,
    pub roots: Vec<String>,
    #[serde(skip_serializing_if = "Option::is_none")]
    pub expires_at: Option<DateTime<Utc>>,
    pub truncated: bool,
    pub errors: Vec<String>,
}

#[allow(async_fn_in_trait)]
pub trait Io {
    async fn resolve_did(&self, did: &str) -> Result<Option<DidDoc>, Error>;
    async fn get_record(&self, repo: &str, collection: &str, rkey: &str) -> Result<Option<Value>, Error>;
    async fn contract_held(&self, contract: &StrongRef, authorities: &[String]) -> Result<bool, Error>;
    fn now(&self) -> DateTime<Utc>;
}

pub fn is_did(s: &str) -> bool {
    let Some((method, id)) = s.strip_prefix("did:").and_then(|r| r.split_once(':')) else {
        return false;
    };
    s.len() <= 2048
        && !method.is_empty()
        && method.bytes().all(|b| b.is_ascii_lowercase())
        && !id.is_empty()
        && id.bytes().all(|b| b.is_ascii_alphanumeric() || b"._:%-".contains(&b))
        && !id.ends_with([':', '%'])
}

pub fn agent_of(also_known_as: &[String]) -> Vec<String> {
    let mut out: Vec<String> = Vec::new();
    for p in also_known_as.iter().filter_map(|e| e.strip_prefix(AGENT_OF_PREFIX)) {
        if is_did(p) && !out.iter().any(|o| o == p) {
            out.push(p.to_string());
        }
    }
    out
}

struct Edge {
    from: String,
    to: String,
    expires_at: Option<DateTime<Utc>>,
    contract: Option<StrongRef>,
    alive: bool,
}

struct Grant {
    expires_at: Option<DateTime<Utc>>,
    contract: Option<StrongRef>,
}

fn grant(value: &Value, agent: &str, now: DateTime<Utc>) -> Option<Grant> {
    if value.get("agent")?.as_str()? != agent {
        return None;
    }
    let expires_at = match value.get("expiresAt") {
        None => None,
        Some(v) => Some(DateTime::parse_from_rfc3339(v.as_str()?).ok()?.with_timezone(&Utc)),
    };
    let contract = match value.get("contract") {
        None => None,
        Some(v) => Some(StrongRef::deserialize(v).ok()?),
    };
    if expires_at.is_some_and(|e| now >= e) || (contract.is_some() && expires_at.is_none()) {
        return None;
    }
    Some(Grant { expires_at, contract })
}

fn record(result: Result<Option<Value>, Error>, uri: String, errors: &mut Vec<String>) -> Option<Value> {
    result.unwrap_or_else(|e| {
        errors.push(format!("getRecord {uri}: {e}"));
        None
    })
}

fn up(edges: &[Edge], start: &str) -> Vec<Ancestor> {
    let mut out = Vec::new();
    let mut seen = HashSet::from([start]);
    let mut queue = VecDeque::from([(start, 0, None)]);
    while let Some((x, d, exp)) = queue.pop_front() {
        for e in edges.iter().filter(|e| e.alive && e.from == x) {
            if seen.insert(e.to.as_str()) {
                let exp = min(exp, e.expires_at);
                out.push(Ancestor { did: e.to.clone(), depth: d + 1, expires_at: exp });
                queue.push_back((&e.to, d + 1, exp));
            }
        }
    }
    out
}

fn min(a: Option<DateTime<Utc>>, b: Option<DateTime<Utc>>) -> Option<DateTime<Utc>> {
    match (a, b) {
        (Some(a), Some(b)) => Some(a.min(b)),
        (a, b) => a.or(b),
    }
}

pub async fn walk<I: Io>(io: &I, agent: &str, options: Options) -> Walk {
    let now = io.now();
    let mut errors = Vec::new();
    let mut edges: Vec<Edge> = Vec::new();
    let mut stuck: HashSet<String> = HashSet::new();
    let mut truncated = false;
    let mut seen = HashSet::from([agent.to_string()]);
    let mut queue = VecDeque::from([(agent.to_string(), 0, vec![agent.to_string()])]);
    let mut lookups = 0;
    while let Some((x, d, path)) = queue.pop_front() {
        let doc = match io.resolve_did(&x).await {
            Ok(Some(doc)) => doc,
            Ok(None) => continue,
            Err(e) => {
                errors.push(format!("resolveDid {x}: {e}"));
                continue;
            }
        };
        for p in agent_of(&doc.also_known_as) {
            if path.contains(&p) {
                stuck.insert(x.clone());
                continue;
            }
            if d < options.max_depth {
                lookups += 2;
            }
            if d + 1 > options.max_depth || lookups > options.budget {
                truncated = true;
                stuck.insert(x.clone());
                continue;
            }
            let (e, g) = join(
                io.get_record(&p, ENDORSEMENT_NSID, &x),
                io.get_record(&p, ASSOCIATION_NSID, &x),
            )
            .await;
            let e = record(e, format!("at://{p}/{ENDORSEMENT_NSID}/{x}"), &mut errors);
            let g = record(g, format!("at://{p}/{ASSOCIATION_NSID}/{x}"), &mut errors);
            let endorsed = e.is_some_and(|e| e.get("agent").and_then(Value::as_str) == Some(x.as_str()));
            let Some(g) = g.and_then(|g| grant(&g, &x, now)).filter(|_| endorsed) else {
                continue;
            };
            edges.push(Edge { from: x.clone(), to: p.clone(), expires_at: g.expires_at, contract: g.contract, alive: true });
            if seen.insert(p.clone()) {
                let mut path = path.clone();
                path.push(p.clone());
                queue.push_back((p, d + 1, path));
            }
        }
    }

    let mut held: HashMap<usize, Vec<String>> = HashMap::new();
    loop {
        let checks: Vec<(usize, Vec<String>)> = edges
            .iter()
            .enumerate()
            .filter(|(_, e)| e.alive && e.contract.is_some())
            .map(|(i, e)| (i, std::iter::once(e.to.clone()).chain(up(&edges, &e.to).into_iter().map(|a| a.did)).collect()))
            .filter(|(i, authorities)| held.get(i) != Some(authorities))
            .collect();
        if checks.is_empty() {
            break;
        }
        let results = join_all(checks.iter().map(|(i, a)| io.contract_held(edges[*i].contract.as_ref().unwrap(), a))).await;
        for ((i, authorities), result) in checks.into_iter().zip(results) {
            match result {
                Ok(true) => {
                    held.insert(i, authorities);
                }
                Ok(false) => edges[i].alive = false,
                Err(e) => {
                    errors.push(format!("contractHeld {}: {e}", edges[i].contract.as_ref().unwrap().uri));
                    edges[i].alive = false;
                }
            }
        }
    }

    let mut ancestors = up(&edges, agent);
    let reached = ancestors.len();
    ancestors.retain(|a| a.depth <= options.max_depth);
    truncated |= ancestors.len() < reached;
    let mut roots = Vec::new();
    let mut expires_at = None;
    let nodes = std::iter::once((agent, None)).chain(ancestors.iter().map(|a| (a.did.as_str(), a.expires_at)));
    for (n, exp) in nodes {
        if !stuck.contains(n) && !edges.iter().any(|e| e.alive && e.from == n) {
            roots.push(n.to_string());
            expires_at = min(expires_at, exp);
        }
    }
    Walk { agent: agent.to_string(), ancestors, roots, expires_at, truncated, errors }
}