merkle.js

import Timestamp from './timestamp';

function getKeys(trie) {
  return Object.keys(trie).filter(x => x !== 'hash');
}

function keyToTimestamp(key) {
  // 16 is the length of the base 3 value of the current time in
  // minutes. Ensure it's padded to create the full value
  let fullkey = key + '0'.repeat(16 - key.length);

  // Parse the base 3 representation
  return parseInt(fullkey, 3) * 1000 * 60;
}

export function insert(trie, timestamp) {
  let hash = timestamp.hash();
  let key = Number((timestamp.millis() / 1000 / 60) | 0).toString(3);

  trie = Object.assign({}, trie, { hash: trie.hash ^ hash });
  return insertKey(trie, key, hash);
}

function insertKey(trie, key, hash) {
  if (key.length === 0) {
    return trie;
  }
  const c = key[0];
  const n = trie[c] || {};
  return Object.assign({}, trie, {
    [c]: Object.assign({}, n, insertKey(n, key.slice(1), hash), {
      hash: n.hash ^ hash
    })
  });
}

export function build(timestamps) {
  let trie = {};
  for (let timestamp of timestamps) {
    insert(trie, timestamp);
  }
  return trie;
}

export function diff(trie1, trie2) {
  if (trie1.hash === trie2.hash) {
    return null;
  }

  let node1 = trie1;
  let node2 = trie2;
  let k = '';

  while (1) {
    let keyset = new Set([...getKeys(node1), ...getKeys(node2)]);
    let keys = [...keyset.values()];
    keys.sort();

    let diffkey = keys.find(key => {
      let next1 = node1[key] || {};
      let next2 = node2[key] || {};
      return next1.hash !== next2.hash;
    });
    if (!diffkey) {
      return keyToTimestamp(k);
    }

    k += diffkey;
    node1 = node1[diffkey] || {};
    node2 = node2[diffkey] || {};
  }
}

export function prune(trie, n = 2) {
  // Do nothing if empty
  if (!trie.hash) {
    return trie;
  }

  let keys = getKeys(trie);
  keys.sort();

  let next = { hash: trie.hash };
  keys = keys.slice(-n).map(k => (next[k] = prune(trie[k], n)));

  return next;
}

export function debug(trie, k = '', indent = 0) {
  const str =
    ' '.repeat(indent) +
    (k !== '' ? `k: ${k} ` : '') +
    `hash: ${trie.hash || '(empty)'}\n`;
  return (
    str +
    getKeys(trie)
      .map(key => {
        return debug(trie[key], key, indent + 2);
      })
      .join('')
  );
}

merkle.test.js

import * as merkle from './merkle';
import Timestamp from './timestamp';

function pretty(n) {
  if (n < 60) {
    console.log(`${n} (${n} min)`);
  } else if (n < 24 * 60) {
    console.log(`${n} (${n / 60} hours)`);
  } else {
    console.log(`${n} (${n / (24 * 60)} days)`);
  }
}

function printBase3Buckets() {
  for (let i = 0; i < 14; i++) {
    let left = '0000000000000'.slice(0, i);
    let rightLow = '0000000000000'.slice(0, 13 - i);
    let rightHigh = '2222222222222'.slice(0, 13 - i);
    const min = left + '2' + rightLow;
    const max = left + '2' + rightHigh;

    pretty(parseInt(max, 3) - parseInt(min, 3));
  }
}

function message(timestamp, hash) {
  timestamp = Timestamp.parse(timestamp);
  timestamp.hash = () => hash;
  return { timestamp };
}

describe('merkle trie', () => {
  test('adding an item works', () => {
    let trie = merkle.insert(
      {},
      Timestamp.parse('2018-11-12T13:21:40.122Z-0000-0123456789ABCDEF')
    );
    trie = merkle.insert(
      trie,
      Timestamp.parse('2018-11-13T13:21:40.122Z-0000-0123456789ABCDEF')
    );
    expect(trie).toMatchSnapshot();
  });

  test('diff returns the correct time difference', () => {
    let trie1 = {};
    let trie2 = {};

    const messages = [
      // First client messages
      message('2018-11-13T13:20:40.122Z-0000-0123456789ABCDEF', 1000),
      message('2018-11-14T13:05:35.122Z-0000-0123456789ABCDEF', 1100),
      message('2018-11-15T22:19:00.122Z-0000-0123456789ABCDEF', 1200),

      // Second client messages
      message('2018-11-20T13:19:40.122Z-0000-0123456789ABCDEF', 1300),
      message('2018-11-25T13:19:40.122Z-0000-0123456789ABCDEF', 1400)
    ];

    trie1 = merkle.insert(trie1, messages[0].timestamp);
    trie1 = merkle.insert(trie1, messages[1].timestamp);
    trie1 = merkle.insert(trie1, messages[2].timestamp);
    expect(trie1.hash).toBe(788);

    trie2 = merkle.insert(trie2, messages[3].timestamp);
    trie2 = merkle.insert(trie2, messages[4].timestamp);
    expect(trie2.hash).toBe(108);

    expect(new Date(merkle.diff(trie1, trie2)).toISOString()).toBe(
      '2018-11-13T13:20:00.000Z'
    );

    trie1 = merkle.insert(trie1, messages[3].timestamp);
    trie1 = merkle.insert(trie1, messages[4].timestamp);
    trie2 = merkle.insert(trie2, messages[0].timestamp);
    trie2 = merkle.insert(trie2, messages[1].timestamp);
    trie2 = merkle.insert(trie2, messages[2].timestamp);
    expect(trie1.hash).toBe(888);
    expect(trie1.hash).toBe(trie2.hash);
  });

  test('diffing works with empty tries', () => {
    // It's important to note that our trie only works with a range of
    // dates between the following:
    //
    // 1996-11-06T13:56:49.443Z
    // 2050-07-19T17:50:28.328Z
    //
    // This is because we assume the key represenation of the
    // timestamps are fixed length, but for dates outside that range
    // the length changes. Our range is small because we use a base 3
    // representation which will overflow quicker. If we are still
    // around in 2050, I think we'll have enough money to fix this.

    let trie1 = {};
    let trie2 = merkle.insert(
      {},
      Timestamp.parse('2009-01-02T10:17:37.789Z-0000-0000testinguuid1')
    );

    expect(merkle.diff(trie1, trie2)).toBe(1230891420000);
  });

  test('pruning works and keeps correct hashes', () => {
    let messages = [
      message('2018-11-01T01:00:00.000Z-0000-0123456789ABCDEF', 1000),
      message('2018-11-01T01:09:00.000Z-0000-0123456789ABCDEF', 1100),
      message('2018-11-01T01:18:00.000Z-0000-0123456789ABCDEF', 1200),
      message('2018-11-01T01:27:00.000Z-0000-0123456789ABCDEF', 1300),
      message('2018-11-01T01:36:00.000Z-0000-0123456789ABCDEF', 1400),
      message('2018-11-01T01:45:00.000Z-0000-0123456789ABCDEF', 1500),
      message('2018-11-01T01:54:00.000Z-0000-0123456789ABCDEF', 1600),
      message('2018-11-01T02:03:00.000Z-0000-0123456789ABCDEF', 1700),
      message('2018-11-01T02:10:00.000Z-0000-0123456789ABCDEF', 1800),
      message('2018-11-01T02:19:00.000Z-0000-0123456789ABCDEF', 1900),
      message('2018-11-01T02:28:00.000Z-0000-0123456789ABCDEF', 2000),
      message('2018-11-01T02:37:00.000Z-0000-0123456789ABCDEF', 2100)
    ];

    let trie = {};
    messages.forEach(msg => {
      trie = merkle.insert(trie, msg.timestamp);
    });
    expect(trie.hash).toBe(2496);
    expect(trie).toMatchSnapshot();

    let pruned = merkle.prune(trie);
    expect(pruned.hash).toBe(2496);
    expect(pruned).toMatchSnapshot();
  });
});