atproto 0.0.1-preview.1

AT Protocol data model, repositories, identity, XRPC, OAuth and sessions

Readme Files Dependencies Versions

atproto#

Libraries for the AT Protocol in Zena: its data model, encodings, cryptography, identity resolution, and repositories.

Usage#

import {cidForValue, decodeCbor, encodeCbor} from 'atproto/cbor';
import {StringValue, newMap, stringField} from 'atproto/data';

let record = newMap([
  ('$type', new StringValue('app.bsky.feed.post')),
  ('text', new StringValue('Hello from Zena!')),
]);

let bytes = encodeCbor(record);
let cid = cidForValue(record);
let decoded = decodeCbor(bytes);

Libraries#

  • atproto/varint: multiformats unsigned varints.
  • atproto/multibase: multibase strings, and base58btc. The other base encodings are in zena:encoding.
  • atproto/cid: CIDs, their binary and string forms, and the CIDs atproto gives records and blobs.
  • atproto/data: the data model (Value and its cases), its JSON form, and blob references (BlobRef).
  • atproto/cbor: DAG-CBOR encoding and strict decoding, cidForValue, and sortedKeys, the order DAG-CBOR writes map keys in.
  • atproto/syntax: DIDs, handles, NSIDs, record keys, TIDs, datetimes, and CID strings.
  • atproto/car: CAR files and BlockMap, checking every block against its CID.
  • atproto/mst: the Merkle search tree: key heights, nodes, building a tree, and looking a key up through the nodes of a proof.
  • atproto/repo: commits, signing them, and verifying com.atproto.sync.getRecord proofs.
  • atproto/tid: timestamp identifiers, and a clock that hands out increasing ones.
  • atproto/didkey: public keys as multikeys, did:keys, and DID document verification methods, and checking atproto signatures with them.
  • atproto/did: what atproto reads from a DID document: the signing key, the PDS, and the claimed handle.
  • atproto/service-auth: service-auth JWTs, which an account's PDS signs so the account can call another service: creating them, checking them against the issuer's key, the audience, the method, and the time, and refusing a token presented twice (ReplayGuard).
  • atproto/session: signing in to an account's PDS with a password, refreshing and ending the session, and asking the PDS for service-auth tokens, with a password session or an OAuth one (AccountSession).
  • atproto/oauth: signing in with atproto OAuth as a public client, such as a command-line tool: finding the PDS's authorization server, the authorization request with PKCE and DPoP, trading the code for tokens, and a session that signs each request, follows the servers' nonces, refreshes and revokes its tokens.
  • atproto/dpop: DPoP keys and proofs: ES256 proofs for each request, checking them, and JWK thumbprints.
  • atproto/xrpc: an XRPC client, whose requests a RequestSigner can authorize one by one.
  • atproto/methods: the NSIDs of standard com.atproto methods, and xrpcPath, a method's path on a server.
  • atproto/plc: did:plc operations: building and signing them, the DID a genesis operation makes, and sending an operation to a PLC directory.
  • atproto/identity: resolving DIDs (did:plc, did:web) and handles (DNS over HTTPS, then HTTPS), checking handles in both directions.
  • atproto/sync: fetching a record and checking its proof against the DID document's key, fetching a blob and checking it against its CID, and listing a collection's records, which comes with no proof.

atproto/xrpc, atproto/identity, atproto/sync, atproto/session, atproto/oauth, and atproto/plc send requests with zena:fetch; atproto/oauth also reads the clock and draws random bytes. The other libraries have no imports from the host.

9.2 KiB Raw
/**
 * The Merkle search tree (MST) that holds an atproto repository's records
 * (https://atproto.com/specs/repository#mst-structure).
 *
 * Keys are `<collection>/<record key>` and values are the records' CIDs.
 * Each key has a height: the number of leading zero bits of its SHA-256
 * hash, divided by two and rounded down. A key sits in the node at the
 * layer equal to its height, and the keys of lower heights between two
 * keys of a node sit in a subtree between them. The root is at the layer
 * of the highest key. The tree for a set of keys is therefore unique, and
 * so is its root CID.
 *
 * A node is DAG-CBOR: `{l, e}`, where `l` is the subtree before the first
 * entry or null, and `e` lists the entries in key order. An entry is
 * `{p, k, v, t}`: the number of leading bytes its key shares with the
 * previous entry's key in the node, the rest of the key's bytes, the
 * value, and the subtree after it or null. A node may have no entries and
 * only a subtree, when a layer between two keys holds no key.
 */

import {GrowableArray} from 'zena:collections';
import {Encoding, copyBytes, newByteArray} from 'zena:core';
import {sha256} from 'zena:crypto';
import {BlockMap} from './car.zena';
import {decodeCbor} from './cbor.zena';
import {Cid} from './cid.zena';
import {
  BytesValue,
  IntValue,
  LinkValue,
  ListValue,
  MapValue,
  NullValue,
  Value,
  field,
  newMap
} from './data.zena';

/** Fills arrays of entries before their elements are set. */
let NO_CID = new Cid(1, 0 as i64, 0 as i64, new FixedArray<u8>(0, 0 as u8));

/** A node that cannot be read, or a block a walk needed and did not have. */
export class MstError extends Error {
  new(message: String) : super(message);
}

/**
 * The height of `key`: half the number of leading zero bits of its
 * SHA-256 hash, rounded down.
 */
export function keyHeight(key: String): i32 {
  let hash = sha256(key.toBytes());
  var zeros = 0;
  for (var i = 0; i < hash.length; i += 1) {
    let b = hash[i] as i32;
    if (b == 0) {
      zeros += 8;
    } else {
      var mask = 0x80;
      while ((b & mask) == 0) {
        zeros += 1;
        mask = mask >> 1;
      }
      break;
    }
  }
  return zeros >> 1;
}

/** The number of leading bytes `a` and `b` share. */
export function commonPrefixLength(a: String, b: String): i32 {
  let limit = if (a.length < b.length) a.length else b.length;
  var i = 0;
  while (i < limit && a.getByteAt(i) == b.getByteAt(i)) {
    i += 1;
  }
  return i;
}

/** Negative when `a` sorts before `b` byte by byte. */
export function compareKeys(a: String, b: String): i32 {
  let shared = commonPrefixLength(a, b);
  if (shared < a.length && shared < b.length) {
    return a.getByteAt(shared) - b.getByteAt(shared);
  }
  return a.length - b.length;
}

/** An entry of a node, with its key in full. */
export final class MstEntry {
  key: String;
  value: Cid;
  var right: Cid | null;
  new(key: String, value: Cid, right: Cid | null) : key = key, value = value, right = right;
}

/** A decoded node. */
export final class MstNode {
  left: Cid | null;
  entries: FixedArray<MstEntry>;
  new(left: Cid | null, entries: FixedArray<MstEntry>) : left = left, entries = entries;
}

function optionalLink(value: Value | null, what: String): Cid | null {
  if (value == null || value is NullValue) {
    return null;
  }
  if (value is LinkValue) {
    return value.cid;
  }
  throw new MstError(`${what} is neither a CID nor null`);
}

/**
 * Reads a node, checking its shape, that each prefix length fits the
 * previous key, and that keys increase.
 */
export function decodeNode(bytes: FixedArray<u8>): MstNode {
  let value = decodeCbor(bytes);
  if (!(value is MapValue)) {
    throw new MstError('node is not a map');
  }
  let map = value;
  let list = field(map, 'e');
  if (!(list is ListValue)) {
    throw new MstError('node has no entry list');
  }
  let items = list.items;
  let entries = new FixedArray<MstEntry>(items.length, new MstEntry('', NO_CID, null));
  var previous = '';
  for (var i = 0; i < items.length; i += 1) {
    let item = items[i];
    if (!(item is MapValue)) {
      throw new MstError('entry is not a map');
    }
    let entry = item;
    let p = field(entry, 'p');
    let k = field(entry, 'k');
    let v = field(entry, 'v');
    if (!(p is IntValue) || !(k is BytesValue) || !(v is LinkValue)) {
      throw new MstError('entry lacks p, k or v');
    }
    let prefix = p.value;
    if (prefix < 0 || prefix > (previous.length as i64) || (i == 0 && prefix != 0)) {
      throw new MstError(`entry ${i} has prefix length ${prefix}`);
    }
    let key = joinKey(previous, prefix as i32, k.value);
    if (i > 0 && compareKeys(previous, key) >= 0) {
      throw new MstError(`keys out of order at '${key}'`);
    }
    entries[i] = new MstEntry(key, v.cid, optionalLink(field(entry, 't'), 'subtree'));
    previous = key;
  }
  return new MstNode(optionalLink(field(map, 'l'), 'left subtree'), entries);
}

/** The first `prefix` bytes of `previous` followed by `suffix`, as a key. */
function joinKey(previous: String, prefix: i32, suffix: FixedArray<u8>): String {
  let bytes = newByteArray(prefix + suffix.length);
  previous.copyBytesTo(bytes, 0, 0, prefix);
  copyBytes(bytes, prefix, suffix as ByteArray, 0, suffix.length);
  return String.fromByteArray(bytes, 0, bytes.length, Encoding.WTF8);
}

/** The data-model form of a node. */
export function encodeNode(node: MstNode): Value {
  let items = new FixedArray<Value>(node.entries.length, new NullValue());
  var previous = '';
  for (var i = 0; i < node.entries.length; i += 1) {
    let entry = node.entries[i];
    let prefix = commonPrefixLength(previous, entry.key);
    let suffix = entry.key.toBytes().slice(prefix, entry.key.length);
    let map = newMap();
    map.entries['p'] = new IntValue(prefix as i64);
    map.entries['k'] = new BytesValue(suffix);
    map.entries['v'] = new LinkValue(entry.value);
    map.entries['t'] = linkOrNull(entry.right);
    items[i] = map;
    previous = entry.key;
  }
  let map = newMap();
  map.entries['l'] = linkOrNull(node.left);
  map.entries['e'] = new ListValue(items);
  return map;
}

function linkOrNull(cid: Cid | null): Value {
  if (cid == null) {
    return new NullValue();
  }
  return new LinkValue(cid);
}

/**
 * Builds the tree for `keys`, which must be sorted byte by byte and
 * distinct, with `values[i]` the value of `keys[i]`. Stores every node in
 * `blocks` and returns the root's CID.
 */
export function buildMst(keys: FixedArray<String>, values: FixedArray<Cid>, blocks: BlockMap): Cid {
  let heights = new FixedArray<i32>(keys.length, 0);
  var top = 0;
  for (var i = 0; i < keys.length; i += 1) {
    if (i > 0 && compareKeys(keys[i - 1], keys[i]) >= 0) {
      throw new MstError(`keys not sorted and distinct at '${keys[i]}'`);
    }
    heights[i] = keyHeight(keys[i]);
    if (heights[i] > top) {
      top = heights[i];
    }
  }
  return buildNode(keys, values, heights, 0, keys.length, top, blocks);
}

/** Builds the node at `layer` holding `keys[start..end]`, and its subtrees. */
function buildNode(
  keys: FixedArray<String>,
  values: FixedArray<Cid>,
  heights: FixedArray<i32>,
  start: i32,
  end: i32,
  layer: i32,
  blocks: BlockMap
): Cid {
  var left: Cid | null = null;
  let entries = new GrowableArray<MstEntry>();
  var groupStart = start;
  for (var i = start; i <= end; i += 1) {
    if (i < end && heights[i] != layer) {
      continue;
    }
    let subtree = if (groupStart < i) {
      buildNode(keys, values, heights, groupStart, i, layer - 1, blocks)
    } else {
      null
    };
    if (entries.length == 0) {
      left = subtree;
    } else {
      entries[entries.length - 1].right = subtree;
    }
    if (i < end) {
      entries.push(new MstEntry(keys[i], values[i], null));
    }
    groupStart = i + 1;
  }
  let fixed = new FixedArray<MstEntry>(entries.length, new MstEntry('', NO_CID, null));
  for (var j = 0; j < entries.length; j += 1) {
    fixed[j] = entries[j];
  }
  return blocks.add(encodeNode(new MstNode(left, fixed)));
}

function loadNode(cid: Cid, blocks: BlockMap) {
  let bytes = blocks.get(cid);
  if (bytes == null) {
    throw new MstError(`missing node ${cid.toString()}`);
  }
  return decodeNode(bytes);
}

/**
 * The value of `key` in the tree at `root`, or null when the tree does not
 * have it. Reads only the nodes on the path to `key`, so `blocks` can be a
 * proof that holds just those; a node missing from it is an error.
 */
export function mstGet(root: Cid, key: String, blocks: BlockMap): Cid | null {
  var cid: Cid | null = root;
  while (cid != null) {
    let node = loadNode(cid, blocks);
    // The subtree before the first entry whose key is greater.
    var next = node.left;
    for (let entry in node.entries) {
      let order = compareKeys(key, entry.key);
      if (order == 0) {
        return entry.value;
      }
      if (order < 0) {
        break;
      }
      next = entry.right;
    }
    cid = next;
  }
  return null;
}

/** Calls `callback` with every key and value in the tree, in key order. */
export function mstWalk(root: Cid, blocks: BlockMap, callback: (key: String, value: Cid) => void): void {
  let node = loadNode(root, blocks);
  if (node.left != null) {
    mstWalk(node.left as Cid, blocks, callback);
  }
  for (let entry in node.entries) {
    callback(entry.key, entry.value);
    if (entry.right != null) {
      mstWalk(entry.right as Cid, blocks, callback);
    }
  }
}
none
VersionPublishedDependenciesApproved by
0.0.1-preview.1 2026-11-19 none