PacSpace

Verification & Proofs

Merkle Specification

The exact specification for independently verifying proof hashes, including tree structure and reference implementations.

This document defines the exact algorithm PacSpace uses to compute proof hashes. Follow this specification to independently verify any proof hash you receive.

Tree Construction Rules

Rule 1: Leaf Hashes

Each item in a batch is hashed using keccak256 with a domain-separated prefix:

leafHash = keccak256("pacspace:item:v1:" + canonicalJSON)

The JSON is canonicalized — keys are sorted alphabetically at every nesting level, and no extra whitespace is included.

Rule 2: Internal Nodes

Each internal node is computed by concatenating two child hashes with a domain prefix:

nodeHash = keccak256("pacspace:node:v1:" + leftHash + rightHash)

Rule 3: Pair Order

Leaves are paired left-to-right in insertion order. The first two leaves form the first pair, the next two form the second pair, and so on up the tree.

Rule 4: Odd Number of Leaves

If a level has an odd number of nodes, the last node is duplicated to form a complete pair.

Rule 5: Empty Tree

An empty batch (zero items) produces a zero hash:

0x0000000000000000000000000000000000000000000000000000000000000000

Rule 6: Single Item

A batch with one item uses the item's leaf hash directly as the root — no tree is constructed.

root = leafHash(item)

Tree Structure

Here's how a four-item batch produces a proof hash:

                ┌──────────────┐
                │  Proof Hash  │
                │  (Root)      │
                └──────┬───────┘
                       │
              ┌────────┴────────┐
              │                 │
        ┌─────┴─────┐    ┌─────┴─────┐
        │  Node A   │    │  Node B   │
        └─────┬─────┘    └─────┬─────┘
              │                 │
         ┌────┴────┐      ┌────┴────┐
         │         │      │         │
      ┌──┴──┐  ┌──┴──┐ ┌──┴──┐  ┌──┴──┐
      │ L₀  │  │ L₁  │ │ L₂  │  │ L₃  │
      └─────┘  └─────┘ └─────┘  └─────┘
       Item 0   Item 1   Item 2   Item 3

Where:

  • L₀–L₃ = keccak256("pacspace:item:v1:" + canonicalJSON(item))
  • Node A = keccak256("pacspace:node:v1:" + L₀ + L₁)
  • Node B = keccak256("pacspace:node:v1:" + L₂ + L₃)
  • Root = keccak256("pacspace:node:v1:" + Node A + Node B)

For an odd number of items (e.g., three items), the last leaf is duplicated:

                ┌──────────────┐
                │  Proof Hash  │
                └──────┬───────┘
                       │
              ┌────────┴────────┐
              │                 │
        ┌─────┴─────┐    ┌─────┴─────┐
        │  Node A   │    │  Node B   │
        └─────┬─────┘    └─────┬─────┘
              │                 │
         ┌────┴────┐      ┌────┴────┐
         │         │      │         │
        L₀        L₁    L₂     L₂ (dup)

Reference Implementations

JavaScript

computeItemHash

Computes the leaf hash for a single item.

javascript
const { keccak256 } = require('@ethersproject/keccak256');
const { toUtf8Bytes } = require('@ethersproject/strings');

function canonicalize(obj) {
  if (obj === null || typeof obj !== 'object') return JSON.stringify(obj);
  if (Array.isArray(obj)) return '[' + obj.map(canonicalize).join(',') + ']';
  const sortedKeys = Object.keys(obj).sort();
  const pairs = sortedKeys.map(k => JSON.stringify(k) + ':' + canonicalize(obj[k]));
  return '{' + pairs.join(',') + '}';
}

function computeItemHash(item) {
  const canonical = canonicalize(item);
  const prefixed = 'pacspace:item:v1:' + canonical;
  return keccak256(toUtf8Bytes(prefixed));
}

computeMerkleRoot

Builds the tree and returns the root hash.

javascript
const ZERO_HASH = '0x' + '0'.repeat(64);

function computeMerkleRoot(itemHashes) {
  if (itemHashes.length === 0) return ZERO_HASH;
  if (itemHashes.length === 1) return itemHashes[0];

  let level = [...itemHashes];

  while (level.length > 1) {
    const nextLevel = [];

    // If odd number of nodes, duplicate the last one
    if (level.length % 2 !== 0) {
      level.push(level[level.length - 1]);
    }

    for (let i = 0; i < level.length; i += 2) {
      const left = level[i];
      const right = level[i + 1];
      const prefixed = 'pacspace:node:v1:' + left + right;
      nextLevel.push(keccak256(toUtf8Bytes(prefixed)));
    }

    level = nextLevel;
  }

  return level[0];
}

verifyReceipt

End-to-end verification of a webhook receipt.

javascript
function verifyReceipt(receipt) {
  const { contentHash, proofHash, itemHashes, previousProofHash } = receipt.proof;

  // 1. Verify content hash is in the batch
  if (!itemHashes.includes(contentHash)) {
    return { verified: false, reason: 'Content hash not found in itemHashes' };
  }

  // 2. Recompute the Merkle root from itemHashes
  const recomputedRoot = computeMerkleRoot(itemHashes);

  // 3. Compare against the proof hash
  if (recomputedRoot !== proofHash) {
    return { verified: false, reason: 'Recomputed root does not match proofHash' };
  }

  // 4. (Optional) Validate chain link if previous hash is available
  if (previousProofHash && receipt._storedPreviousHash) {
    if (previousProofHash !== receipt._storedPreviousHash) {
      return { verified: false, reason: 'Chain link broken — previousProofHash mismatch' };
    }
  }

  return { verified: true };
}

Usage Example

javascript
// From a delta.verified webhook payload
const receipt = {
  proof: {
    proofHash: '0x8f3a9b...',
    contentHash: '0x2d4e7f...',
    itemHashes: ['0x2d4e7f...', '0x9f1a3c...'],
    previousProofHash: '0x1c7b2e...'
  }
};

const result = verifyReceipt(receipt);
console.log(result); // { verified: true }

Hashing Notes

  • Algorithm: keccak256 (the same hash function used widely in cryptographic applications)
  • Encoding: All string inputs are UTF-8 encoded before hashing
  • Output: 32-byte hex string prefixed with 0x
  • Domain prefixes: Prevent hash collisions between leaf and internal nodes (pacspace:item:v1: vs pacspace:node:v1:)
Was this page helpful?

Last updated February 11, 2026

Previous

Proof Hashes

Next

Overview