MACGUARD · DOCUMENTATION
Español

Merkle trees

How `rules_root` and the log root are computed, with an example you can recompute.

Rules: rules_root

Files are sorted by path (UTF-8 bytes). The leaf of each file is SHA-256(0x00 || path || 0x00 || sha256_hex) and internal nodes are SHA-256(0x01 || left || right). A tree of n leaves is split at the largest power of two below n (RFC 6962 / RFC 9162). The root is stored in the signed manifest.

Diagram: Merkle tree of the rule files

Drawing the diagram…

Diagram description

Rule files are sorted by path. Each leaf is SHA-256 of the byte 0x00 followed by path, a zero byte and the file SHA-256 in hex. With five leaves the tree splits at the largest power of two below five: four leaves on the left and one on the right. Internal nodes are SHA-256 of 0x01, left and right. The top hash is rules_root, stored in the signed manifest.

Mermaid code
flowchart BT
  L0["leaf 0<br/>H(00 || path0 0 sha0)"]:::sec
  L1["leaf 1"]:::sec
  L2["leaf 2"]:::sec
  L3["leaf 3"]:::sec
  L4["leaf 4"]:::sec
  N01["node<br/>H(01 || leaf0 || leaf1)"]:::val
  N23["node<br/>H(01 || leaf2 || leaf3)"]:::val
  N03["node<br/>H(01 || N01 || N23)"]:::val
  R["rules_root<br/>H(01 || N03 || leaf4)"]:::gate
  M["manifest.json<br/>signed with Sigstore"]:::pub
  L0 --> N01
  L1 --> N01
  L2 --> N23
  L3 --> N23
  N01 --> N03
  N23 --> N03
  N03 --> R
  L4 --> R
  R --> M
  classDef src fill:#cfe3ff,stroke:#2f6df0,color:#0b1b33
  classDef val fill:#ffe9b8,stroke:#b8860b,color:#2b1d00
  classDef sec fill:#cdeedd,stroke:#1b6e3c,color:#08210f
  classDef pub fill:#e4d7ff,stroke:#6a3fd1,color:#1b0b3b
  classDef qua fill:#ffd4cc,stroke:#c0392b,color:#33100b
  classDef gate fill:#ffffff,stroke:#111111,stroke-width:3px,color:#111111

Recompute it yourself with the release manifest.json (Python standard library only). It must print True:

import hashlib, json
m = json.load(open('manifest.json'))
H = hashlib.sha256
leaf = lambda b: H(b'\x00' + b).digest()
node = lambda l, r: H(b'\x01' + l + r).digest()
def mth(xs):
    if len(xs) == 1: return xs[0]
    k = 1
    while k * 2 < len(xs): k *= 2
    return node(mth(xs[:k]), mth(xs[k:]))
files = sorted(m['files'], key=lambda f: f['path'].encode())
root = mth([leaf(f"{f['path']}\0{f['sha256']}".encode()) for f in files]).hex()
print(root, root == m['rules_root'])

Practical effect: adding, removing or changing a single byte of one file, or adding an extra file to the package, changes rules_root and verification fails.

Log: log root

Every line of logs/log.jsonl is a leaf: SHA-256(0x00 || exact bytes of the line). They are combined with the same rule. The root and the number of entries form the checkpoint (see Log and checkpoints).

Diagram: Merkle tree of the transparency log

Drawing the diagram…

Diagram description

Every line of logs/log.jsonl is a leaf: SHA-256 of 0x00 followed by the exact bytes of the line. Leaves are combined with 0x01-prefixed node hashes into a root. The root and the number of entries are written to a checkpoint, and the checkpoint is signed. An inclusion proof for entry 4 is the sibling hashes along its path.

Mermaid code
flowchart BT
  E0["entry 0<br/>log.jsonl line"]:::src
  E1["entry 1"]:::src
  E2["entry 2"]:::src
  E3["entry 3"]:::src
  E4["entry 4<br/>the release entry"]:::pub
  E5["entry 5"]:::src
  A["node A = H(01 || L0 || L1)"]:::val
  B["node B = H(01 || L2 || L3)"]:::val
  C["node C = H(01 || L4 || L5)"]:::val
  AB["node AB"]:::val
  ROOT["log root"]:::gate
  CP["checkpoint<br/>origin, size, root"]:::sec
  E0 -->|leaf hash| A
  E1 --> A
  E2 --> B
  E3 --> B
  E4 -->|leaf hash| C
  E5 --> C
  A --> AB
  B --> AB
  AB --> ROOT
  C --> ROOT
  ROOT --> CP
  classDef src fill:#cfe3ff,stroke:#2f6df0,color:#0b1b33
  classDef val fill:#ffe9b8,stroke:#b8860b,color:#2b1d00
  classDef sec fill:#cdeedd,stroke:#1b6e3c,color:#08210f
  classDef pub fill:#e4d7ff,stroke:#6a3fd1,color:#1b0b3b
  classDef qua fill:#ffd4cc,stroke:#c0392b,color:#33100b
  classDef gate fill:#ffffff,stroke:#111111,stroke-width:3px,color:#111111

Proofs

LIMIT The web pages recompute these sums in the browser but do not verify Sigstore signatures. Use cosign, the public verifier or the app for that.