Open data

Consistency proofs

Prove that today's log contains yesterday's log, unchanged. This is what makes rewriting history detectable.

A consistency proof shows that a tree of size m is a prefix of a tree of size n: every block that was in the old log is still there, in the same place, with the same hash. If any block had been altered, removed or reordered, no valid proof could exist.

Checking that history was not rewritten

  1. 1

    Keep a checkpoint

    At some point, save a checkpoint's size and root. Any block's height + 1 and logRoot also work.

  2. 2

    Ask for a proof

    GET /proof/consistency?from=<saved size> returns a proof to the current size.

  3. 3

    Verify with your root

    Run the verification below with your saved root as the old root and the current signed checkpoint's root as the new root. Do not use the oldRoot from the response: the point is to check against what you saw before.

Verification

consistency.mjs
import { sha256 } from '@noble/hashes/sha2.js';

const hex = (s) => Uint8Array.from(s.match(/../g).map((b) => parseInt(b, 16)));
const toHex = (u) => [...u].map((b) => b.toString(16).padStart(2, '0')).join('');
const cat = (...a) => { const o = new Uint8Array(a.reduce((n, x) => n + x.length, 0)); let i = 0; for (const x of a) { o.set(x, i); i += x.length; } return o; };
const nodeHash = (l, r) => sha256(cat(new Uint8Array([1]), l, r));

// RFC 9162, section 2.1.4.2
export function verifyConsistency(first, second, firstRoot, secondRoot, path) {
  if (first === second) return path.length === 0 && firstRoot === secondRoot;
  if (first === 0 || first > second) return false;
  let p = path.map(hex);
  if ((first & (first - 1)) === 0) p = [hex(firstRoot), ...p];
  let fn = first - 1, sn = second - 1;
  while (fn & 1) { fn >>= 1; sn >>= 1; }
  let fr = p[0], sr = p[0];
  for (const c of p.slice(1)) {
    if (sn === 0) return false;
    if (fn & 1 || fn === sn) {
      fr = nodeHash(c, fr); sr = nodeHash(c, sr);
      if (!(fn & 1)) while (!(fn & 1) && fn !== 0) { fn >>= 1; sn >>= 1; }
    } else sr = nodeHash(sr, c);
    fn >>= 1; sn >>= 1;
  }
  return sn === 0 && toHex(fr) === firstRoot && toHex(sr) === secondRoot;
}

Who should run this

Anyone who depends on USD Network's history: exchanges, auditors, partners and, at mainnet, the independent witnesses that cosign checkpoints. Running it on a schedule against saved checkpoints is cheap and turns "we promise not to rewrite history" into something you check every few minutes.