# 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

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

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

### 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

```js title="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.
