Merkle Epochs

[!WARNING] Prototype, not shipped This page describes PoC 2 from the xeprotocol/proof-of-uptime research repository — a standalone Node.js demo — together with the epoch chaining PoC 4 later added on top of it. No epoch or claim structure exists in an XE node. See the section overview for what is and is not implemented.

PoC 2 introduces merkle tree epochs -- a compression layer that groups heartbeats into fixed-size epochs, each summarised by a single 32-byte merkle root.

Concept

Instead of storing every heartbeat on-chain, heartbeats are grouped into epochs. Each epoch is a merkle tree of heartbeat hashes, yielding a compact root hash. Epochs themselves chain together, forming a verifiable timeline.

Epoch 0                    Epoch 1                    Epoch 2
┌──────────────────┐      ┌──────────────────┐      ┌──────────────────┐
│ H0  H1  ... H59  │      │ H60 H61 ... H119 │      │ H120 H121 ...    │
│       │          │      │       │          │      │       │          │
│   merkle tree    │      │   merkle tree    │      │   merkle tree    │
│       │          │      │       │          │      │       │          │
│   epoch root     │──────│   epoch root     │──────│   epoch root     │
└──────────────────┘      └──────────────────┘      └──────────────────┘
                   prevEpochHash           prevEpochHash

With 60 heartbeats per epoch (one per minute), each epoch covers 1 hour of uptime.

Merkle Tree Construction

Heartbeat hashes are arranged as leaves of a binary merkle tree. The tree is built bottom-up:

         Root
        /    \
      H01     H23
     /   \   /   \
    H0   H1 H2   H3

Each internal node is the SHA-256 hash of its two children concatenated:

parent = SHA-256(left || right)

[!NOTE] Odd leaf count If the number of leaves is odd, the last leaf is promoted unchanged to the next level (not duplicated). This avoids inflating the tree with redundant hashes.

[!WARNING] No domain separation in the prototype The prototype hashes children directly, with no prefix distinguishing a leaf from an internal node. That is a known gap, flagged in the threat analysis as a must-fix. XE's shipped merkle root over timekeeper attestations already domain-separates, prefixing leaves with 0x00 and internal nodes with 0x01; an uptime tree would need to do the same.

Selective Disclosure

The key property of merkle trees is selective disclosure: you can prove a specific heartbeat existed within an epoch without revealing any other heartbeats.

Example: Proving Heartbeat #37

To prove heartbeat #37 existed in an epoch of 60 heartbeats:

Provide heartbeat #37 (the leaf).
Provide the merkle proof path -- the sibling hashes needed to reconstruct the root.
The verifier hashes heartbeat #37, then combines with each sibling hash up the tree, arriving at the root.
If the computed root matches the published epoch root, the heartbeat is proven.

            Root ← verifier arrives here
           /    \
         ...    ...
        /          \
      ...          H_sibling  ← provided in proof
     /
   H_sibling       ← provided in proof
  /
H37 ← start here

The proof path contains O(log n) sibling hashes -- logarithmic in the number of heartbeats per epoch.

Proof Sizes

Heartbeats per Epoch

Tree Depth

Proof Hashes

Proof Size

60 (1 hour)

192 bytes

1,440 (1 day)

352 bytes

43,200 (30 days)

512 bytes

[!SUCCESS] Logarithmic scaling Doubling the number of heartbeats adds only one additional hash (32 bytes) to the proof. This is why merkle trees are the standard approach for compact membership proofs.

Epoch Structure

The PoC 4 prototype seals an epoch into a record; hashes and signatures are hex strings. (PoC 2's own epoch record has no prevEpochHash/epochHash — the chaining below is PoC 4's addition.)

{
  epochNumber,      // monotonic epoch counter
  merkleRoot,       // root of the heartbeat merkle tree
  heartbeatCount,   // heartbeats in this epoch
  firstSeq,         // first heartbeat sequence in this epoch
  lastSeq,          // last heartbeat sequence in this epoch
  firstTimestamp,   // unix millis of the first heartbeat
  lastTimestamp,    // unix millis of the last heartbeat
  prevEpochHash,    // epochHash of the previous epoch (64 zeros for the first)
  epochHash,        // SHA-256 over leaseId, epochNumber, merkleRoot,
                    //   heartbeatCount and prevEpochHash
  providerSig,      // provider signs the epoch hash
}

The merkle tree itself is kept locally by whoever needs to generate proofs; only the epoch root and the sealed record travel.

Epoch Chaining

Each epoch includes a prevEpochHash field -- the hash of the previous epoch. This creates a chain of epochs analogous to the heartbeat chain itself:

E0 ← E1 ← E2 ← E3 ← ... ← En

Properties

Ordering is immutable. You cannot reorder epochs without breaking the chain of prevEpochHash references.

Insertion is impossible. Inserting a new epoch between two existing ones would require recomputing the prevEpochHash of all subsequent epochs.

Deletion is detectable. Removing an epoch creates a gap: the next epoch's prevEpochHash will not match the preceding epoch's hash.

Verification

Verify Epoch Chain Integrity

for each epoch Ei where i > 0:
    assert Ei.prevEpochHash == Ei-1.epochHash
    assert Ei.firstSeq     == Ei-1.lastSeq + 1
    assert Ei.epochNumber  == Ei-1.epochNumber + 1

Verify Heartbeat Membership

1. Compute leaf = SHA-256(heartbeat)
2. Walk proof path: for each (sibling, direction) in proof:
     if direction == left:
         current = SHA-256(sibling || current)
     else:
         current = SHA-256(current || sibling)
3. Assert current == epoch.merkleRoot

Compression Ratio

For a 24-hour lease with 1-minute heartbeats, as measured in the PoC 4 demo run:

Layer

Data

Size

Raw heartbeats (JSON)

1,440 heartbeats

718.9 KB

Epoch roots

24 x 32 bytes

768 bytes

Single claim root

1 x 32 bytes

32 bytes

Collapsing 1,440 heartbeats to 24 32-byte roots is most of the win; the claim layer takes those 24 roots down to one. The demo reports 3,681x end to end (718.9 KB raw to a ~200-byte on-chain claim) — a figure from that specific run, not a protocol constant.

Heartbeat Chain -- the heartbeats that feed into merkle epochs
Production Design -- how epochs integrate into the three-layer architecture
Threat Analysis -- attacks against merkle proofs and mitigations