# Proofs

An inclusion proof shows a block is in the log, a consistency proof shows an older log is a prefix of a newer one, and both are checked with two SHA-256 rules from RFC 9162.

## The log

The transparency log is a Merkle tree over every block's hash, built exactly as [RFC 9162](https://www.rfc-editor.org/rfc/rfc9162#section-2.1) (Certificate Transparency v2) builds it (`lib/chain/tlog.ts`):

| | Hash |
|---|---|
| Leaf *i* (block at height *i*) | `SHA-256(0x00 ‖ block hash)`, the block hash as its 32 raw bytes |
| Inner node | `SHA-256(0x01 ‖ left ‖ right)` |
| Empty tree | `SHA-256()` of nothing |
| Shape | the left subtree holds the largest power of two of leaves smaller than the size |

The log of size *n* holds blocks 0 to *n* − 1, so leaf index = block height. Its root is the `root` of the [checkpoint](/integrity/checkpoints) of that size.

## Inclusion proofs

```endpoint try
GET /api/log/inclusion?height=397&size=398
```

The audit path of one block in the log of a given size.

| Parameter | Type | Notes |
|---|---|---|
| `height` | integer | The block height (the leaf index). |
| `size` | integer | Optional. The log size to prove against; default: the newest. Must be more than `height`. |

```json title="Response"
{
  "height": 397,
  "size": 398,
  "leaf": "5a5f3dfa85a21ca7fce7cc68182aaaf92e184ec51f1ea4b229a75ca76df0d2d6",
  "proof": [
    "19c183545e808d8606fea4750976da8887f51977b39e1d2a9162ef98e4e85d47",
    "5ebf642fca56b782717b638b205e1ef4c7aaa61ccf7a1d0fcfda6aa6aaf5d060",
    "5f9c1e51bc694fe2f5e6e1bef9ac21237c52073a1ea4ba1898d7c573ee8a39d1",
    "8f0ff0118236cf4120f00fb8562332e6110398c2d0884ae612585b80d35f3bc5",
    "0a72fdd21c0cf42e4bee2f4d8b3d933b591c6f99f48ab4e402075d9f136a9c04"
  ]
}
```

| Field | Type | Notes |
|---|---|---|
| `height`, `size` | integer | What was asked. |
| `leaf` | string | The leaf hash, `SHA-256(0x00 ‖ block hash)`. Recompute it from the block yourself rather than trusting it. |
| `proof` | array | The RFC 9162 audit path, hex hashes from the leaf up. |

Errors: `400` `height and size must be whole numbers`, `400` `Out of range` (a height not below `size`, or a size larger than the log).

## Consistency proofs

```endpoint try
GET /api/log/consistency?from=395&to=398
```

The proof that the log of size `from` is a prefix of the log of size `to`: no block in it was changed or removed.

| Parameter | Type | Notes |
|---|---|---|
| `from` | integer | The older size (the one you kept). |
| `to` | integer | The newer size, at most the log's current size. |

```json title="Response"
{
  "from": 395,
  "to": 398,
  "proof": [
    "7bdb6c150f9a0049ea23bb544dee08cafbe6f233d38883f7f90858259aff27ab",
    "ab6b2a943cb1b812272849f44b4c0de73a111d20b7a40b7e3f453eb48c566170",
    "f2c5d82d06bb7dc7872daacd1e0c09edc62e34fc2dd1ba69cf33151f2a848344",
    "3bb7fc5addd29bd75b67bcb251dc1c3f4a1da607551d91ca93941357ab407d3f",
    "5f9c1e51bc694fe2f5e6e1bef9ac21237c52073a1ea4ba1898d7c573ee8a39d1",
    "8f0ff0118236cf4120f00fb8562332e6110398c2d0884ae612585b80d35f3bc5",
    "0a72fdd21c0cf42e4bee2f4d8b3d933b591c6f99f48ab4e402075d9f136a9c04"
  ]
}
```

The proof is empty when `from` is `0` or equals `to`. Errors: `400` `from and to must be whole numbers`, `400` `Sizes out of range` (`from` above `to`, or `to` above the log's size).

## Verify both in JavaScript

The two verification algorithms of RFC 9162 (§2.1.3.2 and §2.1.4.2), as `lib/chain/tlog.ts` implements them:

```js title="proofs.mjs"
import { sha256 } from "@noble/hashes/sha2";
import { bytesToHex, concatBytes, hexToBytes } from "@noble/hashes/utils";

const leafHash = (blockHashHex) => sha256(concatBytes(Uint8Array.of(0x00), hexToBytes(blockHashHex)));
const nodeHash = (left, right) => sha256(concatBytes(Uint8Array.of(0x01), left, right));
const same = (a, b) => bytesToHex(a) === bytesToHex(b);

// RFC 9162 §2.1.3.2: is `leaf` leaf m of the tree of size n with this root?
function verifyInclusion(leaf, m, n, proof, root) {
  if (m >= n) return false;
  let fn = m, sn = n - 1, r = leaf;
  for (const p of proof) {
    if (sn === 0) return false;
    if (fn % 2 === 1 || fn === sn) {
      r = nodeHash(p, r);
      if (fn % 2 === 0) do { fn >>= 1; sn >>= 1; } while (fn % 2 === 0 && fn !== 0);
    } else {
      r = nodeHash(r, p);
    }
    fn >>= 1;
    sn >>= 1;
  }
  return sn === 0 && same(r, root);
}

// RFC 9162 §2.1.4.2: is the tree (m, root1) a prefix of the tree (n, root2)?
function verifyConsistency(m, n, root1, root2, proof) {
  if (m > n) return false;
  if (m === n) return proof.length === 0 && same(root1, root2);
  if (m === 0) return proof.length === 0;
  const path = (m & (m - 1)) === 0 ? [root1, ...proof] : proof.slice();
  if (!path.length) return false;
  let fn = m - 1, sn = n - 1;
  while (fn % 2 === 1) { fn >>= 1; sn >>= 1; }
  let fr = path[0], sr = path[0];
  for (const c of path.slice(1)) {
    if (sn === 0) return false;
    if (fn % 2 === 1 || fn === sn) {
      fr = nodeHash(c, fr);
      sr = nodeHash(c, sr);
      if (fn % 2 === 0) do { fn >>= 1; sn >>= 1; } while (fn % 2 === 0 && fn !== 0);
    } else {
      sr = nodeHash(sr, c);
    }
    fn >>= 1;
    sn >>= 1;
  }
  return sn === 0 && same(fr, root1) && same(sr, root2);
}

const get = async (path) => (await fetch("https://mlx.app" + path)).json();

// The checkpoint to check against (verify its signature first: see Checkpoints).
const { checkpoint } = await get("/api/log");
const root = hexToBytes(checkpoint.root);

// 1. Block 397 is in the log.
const { block } = await get("/api/block/397");
const inc = await get(`/api/log/inclusion?height=397&size=${checkpoint.size}`);
console.log("leaf", bytesToHex(leafHash(block.hash)) === inc.leaf);
console.log("inclusion", verifyInclusion(leafHash(block.hash), 397, checkpoint.size, inc.proof.map(hexToBytes), root));

// 2. The log of size 395 you saw earlier is a prefix of today's log.
const old = { size: 395, root: "642006843df23efa33163dfb72cd8ba618945d94775da3fcaed27b60a339578a" };
const con = await get(`/api/log/consistency?from=${old.size}&to=${checkpoint.size}`);
console.log("consistency", verifyConsistency(old.size, checkpoint.size, hexToBytes(old.root), root, con.proof.map(hexToBytes)));
```

```text title="Output"
leaf true
inclusion true
consistency true
```

The old size and root here come from an earlier checkpoint (the state commitment at height 394 recorded it as `size` and `logRoot`). In practice use a checkpoint you verified and saved yourself, a witness's, or one carried by an [anchor](/integrity/anchors).

## From a transaction to the log

To show that a transaction is part of the history everyone sees:

1. `GET /api/tx/<hash>` gives its `height`.
2. `GET /api/block/<height>` gives the block. Check its `txs` holds the hash and that its `hash` follows from the header (see [Blocks](/network/blocks)).
3. Check the block's inclusion proof against a checkpoint you trust, as above.