# Merkle proof verify

`merkle-proof-verify` · version 1.0.0 · Hashing & signatures · free, no key needed

Recompute a Merkle root (RFC 9162 or Bitcoin) from one leaf and its audit path, and compare it to a claimed root.

**Use when you need to: verify a merkle inclusion proof · check this leaf is really in the tree with this root · validate a ct log audit path.**

## Decide before calling

Read the [versioned contract](/v1/tools/merkle-proof-verify/versions/1.0.0) and the supported scope below. Reuse `merkle-proof-verify@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation.

## Explain the choice

"I can use `merkle-proof-verify@1.0.0` for verify a merkle inclusion proof. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured."

## Supported

- verify a merkle inclusion proof
- check this leaf is really in the tree with this root
- validate a ct log audit path
- bitcoin merkle branch verification
- spv proof check
- check a partial merkle branch from a merkleblock message

## Not supported

- building the audit path from a full leaf list (see merkle-root-compute)
- RFC 9162 consistency proofs between two tree sizes

## Behavior

- scheme 'rfc9162': leaf is raw leaf DATA as hex (the tool applies the 0x00 leaf-hash prefix itself). The verifier walks node=leaf_index, last_node=tree_size-1; while last_node>0: if node is odd, hash=H(0x01||next_path_entry||hash); else if node<last_node, hash=H(0x01||hash||next_path_entry); else (an even, rightmost node) consumes no path entry; then node//=2, last_node//=2. audit_path is consumed in that exact left-to-right order; reason 'path_length_wrong' (valid:false, computed_root null) when the path runs out early or has leftover entries.
- scheme 'bitcoin': leaf is a 64-hex-char txid in display order; audit_path is the Bitcoin merkle branch, sibling hashes bottom-up in display order. The verifier reverses leaf and each sibling to internal order, pairs (current, sibling) by leaf_index's bit at each level (even index -> current is left), double-SHA-256s, halves the index. audit_path.length must equal ceil(log2(tree_size)) exactly, else 'path_length_wrong'.
- leaf_index must be < tree_size in both schemes; otherwise the tool returns {valid: false, reason: 'index_out_of_range', computed_root: null} (RFC 9162 2.1.3.2: 'fail the proof verification'; well-typed input that does not verify is valid:false, not an error). A wrong audit_path length likewise returns {valid: false, reason: 'path_length_wrong', computed_root: null}. Order: every field is type- and shape-checked and every limit enforced first (invalid_input or limit_exceeded); then index_out_of_range, then path_length_wrong, then the root comparison. leaf_index and tree_size must be safe integers (at most 9007199254740991), else invalid_input.
- computed_root is the recomputed root whenever the audit path length is consistent (valid true, or valid false with reason 'root_mismatch'), and null exactly when reason is 'path_length_wrong' or 'index_out_of_range'.
- valid is true iff computed_root (canonical lowercase hex) equals root.
- Limits: audit_path has at most 53 entries (max_audit_path_entries) and leaf decodes to at most 65536 bytes (max_leaf_bytes, 131072 hex characters); both fail with limit_exceeded, checked before any hashing.

## Input

- `scheme` (one of "rfc9162", "bitcoin", required)
- `leaf` (string, required): max length 131072; pattern `^([0-9a-f]{2})*$`
- `leaf_index` (integer, required): min 0; max 9007199254740991
- `tree_size` (integer, required): min 1; max 9007199254740991
- `audit_path` (array of string, required): max items 53; each pattern `^[0-9a-f]{64}$`
- `root` (string, required): pattern `^[0-9a-f]{64}$`

## Output

- `valid` (boolean, required)
- `reason` (one of "root_mismatch", "path_length_wrong", "index_out_of_range", null, required)
- `computed_root` (string or null, required): pattern `^[0-9a-f]{64}$`

## Limits

- max audit path entries: 53
- max leaf bytes: 65536

## Example

Request input:

```json
{
  "scheme": "rfc9162",
  "leaf": "101112131415161718191a1b1c1d1e1f",
  "leaf_index": 0,
  "tree_size": 1,
  "audit_path": [],
  "root": "3bfb960453ebaebf33727da7a1f4db38acc051d381b6da20d6d4e88f0eabfd7a"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "computed_root": "3bfb960453ebaebf33727da7a1f4db38acc051d381b6da20d6d4e88f0eabfd7a"
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "merkle-proof-verify",
  "version": "1.0.0",
  "input": {
    "scheme": "rfc9162",
    "leaf": "101112131415161718191a1b1c1d1e1f",
    "leaf_index": 0,
    "tree_size": 1,
    "audit_path": [],
    "root": "3bfb960453ebaebf33727da7a1f4db38acc051d381b6da20d6d4e88f0eabfd7a"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/merkle-proof-verify/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"scheme":"rfc9162","leaf":"101112131415161718191a1b1c1d1e1f","leaf_index":0,"tree_size":1,"audit_path":[],"root":"3bfb960453ebaebf33727da7a1f4db38acc051d381b6da20d6d4e88f0eabfd7a"}'
```

The machine-readable contract is at [/v1/tools/merkle-proof-verify/versions/1.0.0](/v1/tools/merkle-proof-verify/versions/1.0.0).

### CLI

```sh
node cli.mjs run merkle-proof-verify 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Merkle root compute](/tools/merkle-root-compute): Compute a Merkle tree root (RFC 9162 or Bitcoin) from a leaf list, with an optional audit path.
- [Webhook slack verify](/tools/webhook-slack-verify): Verify a Slack request's X-Slack-Signature against its raw body and timestamp, with an absolute replay-window check.
- [Webhook stripe verify](/tools/webhook-stripe-verify): Verify a Stripe webhook's Stripe-Signature header against a raw payload, with secret-rotation and tolerance support.
- [Hash digest verify](/tools/hash-digest-verify): Recompute a fixed-length digest over encoded input bytes and compare it to an expected digest given in any encoding.
- [Webhook twilio verify](/tools/webhook-twilio-verify): Verify a Twilio X-Twilio-Signature against a URL and form params or a JSON body, trying Twilio's port-variant URLs.
- [Hmac verify](/tools/hmac-verify): Recompute an HMAC and compare it, constant-time, to a signature that may carry a literal prefix and be truncated.