chadtmiller.com/pds.js

Switch repository

Loading…

// @pdsjs/spaces/lthash - homomorphic set hash for permissioned repo commits.

import { blake3 } from './blake3.js';

const LANES = 1024;
// Cannot change without reworking the Uint16Array impl. `new Uint16Array(buffer)`
// reads/writes in host byte order, which is little-endian on every platform
// pds.js targets (Node, Deno, browsers, Cloudflare Workers) and matches the
// little-endian lanes described above and by the spec; digests would only
// diverge from the reference on a big-endian host.
const LANE_BYTES = 2;
export const LTHASH_STATE_BYTES = LANES * LANE_BYTES; // 2048

/**
 * A homomorphic set hash. Each element expands to 1024 little-endian u16 lanes
 * summed into the state mod 2^16. Addition and subtraction commute, so the state
 * depends only on the current set, not on insertion order.
 */
export class LtHash {
  /** @param {Uint8Array|null} [state] */
  constructor(state) {
    if (state && state.length !== LTHASH_STATE_BYTES) {
      throw new Error(
        `LtHash state must be ${LTHASH_STATE_BYTES} bytes, got ${state.length}`,
      );
    }
    const buffer = new ArrayBuffer(LTHASH_STATE_BYTES);
    this.bytes = new Uint8Array(buffer);
    this.lanes = new Uint16Array(buffer);
    if (state) this.bytes.set(state);
  }

  /** @param {string} element @returns {this} */
  add(element) {
    const lanes = expand(element);
    for (let i = 0; i < LANES; i++) this.lanes[i] += lanes[i];
    return this;
  }

  /** @param {string} element @returns {this} */
  remove(element) {
    const lanes = expand(element);
    for (let i = 0; i < LANES; i++) this.lanes[i] -= lanes[i];
    return this;
  }

  /** @returns {Uint8Array} the full state, for persistence */
  state() {
    return new Uint8Array(this.bytes);
  }

  /** @returns {Promise<Uint8Array>} */
  async digest() {
    const hash = await crypto.subtle.digest('SHA-256', this.bytes);
    return new Uint8Array(hash);
  }

  /** @returns {boolean} */
  isEmpty() {
    for (let i = 0; i < LANES; i++) if (this.lanes[i] !== 0) return false;
    return true;
  }

  /** @param {LtHash} other @returns {boolean} */
  equals(other) {
    for (let i = 0; i < LANES; i++) {
      if (this.lanes[i] !== other.lanes[i]) return false;
    }
    return true;
  }
}

/**
 * Expand an element to 1024 little-endian u16 lanes with BLAKE3 in XOF mode.
 * @param {string} element
 * @returns {Uint16Array}
 */
function expand(element) {
  const expanded = blake3(
    new TextEncoder().encode(element),
    LTHASH_STATE_BYTES,
  );
  const buffer = new ArrayBuffer(LTHASH_STATE_BYTES);
  new Uint8Array(buffer).set(expanded);
  return new Uint16Array(buffer);
}