# Nukez Merkle V1 — Attestation & Verification Spec

**Status**: Normative. This is the canonical specification third parties should cite when independently verifying Nukez on-chain attestations.

**Spec name**: `nukez-merkle-v1`
**Schema version**: `1.0`
**Machine-readable form**: [/specs/nukez-merkle-v1.json](/specs/nukez-merkle-v1.json)

---

## 1. Spec identity

| Field | Value |
|---|---|
| `name` | `nukez-merkle-v1` |
| `schema_version` | `1.0` |
| `hash` | SHA-256 |
| `encoding` | UTF-8 |
| `digest_format` | lowercase hex |

---

## 2. File entry schema

Every file participating in a Merkle tree is described by:

```json
{
  "filename": "string",
  "size_bytes": "integer >= 0",
  "content_hash": "sha256:<64 hex>  OR  <64 hex>"
}
```

`content_hash` MAY appear with or without the `sha256:` prefix on the wire. All algorithms below normalize to the bare 64-character lowercase hex form before hashing.

---

## 3. Content hash normalization

```
If content_hash starts with "sha256:", strip that prefix before Merkle leaf hashing.
For byte-level file verification, SHA-256 the raw downloaded bytes and compare to
content_hash after normalizing both sides to the same prefix format.
```

---

## 4. Leaf formula

```python
content_hash = content_hash.removeprefix("sha256:")
leaf_material = f"{filename}:{size_bytes}:{content_hash}"
leaf_hash = sha256(leaf_material.encode("utf-8")).hexdigest()
```

`leaf_hash` is a bare 64-character lowercase hex string.

---

## 5. Ordering

```
Sort file entries lexicographically by filename before computing leaves.
```

Sorting is by raw Unicode codepoint order over UTF-8 strings.

---

## 6. Parent formula

```python
parent_hash = sha256((left_hex + right_hex).encode("utf-8")).hexdigest()
```

Concatenation is over the **hex strings** (not raw bytes), then the UTF-8 encoding of that concatenation is fed to SHA-256.

---

## 7. Tree construction

```
Build bottom-up.
Pair nodes left-to-right.
If a level has an odd number of nodes, duplicate the final node.
Repeat until one root remains.

A single-file tree root is that file's leaf hash.
Empty file lists are INVALID for Nukez attestations.
```

The duplication rule is intentional and matches the on-chain anchor implementation. Verifiers MUST implement it identically.

---

## 8. Root format

```
Published roots are represented as "sha256:<64 lowercase hex>".
Internal tree math uses bare 64-character lowercase hex strings.
```

Conversions:
- Bare → published: prepend `sha256:`
- Published → bare: strip `sha256:` prefix

---

## 9. Attestation object

```json
{
  "receipt_id": "string",
  "locker_id": "string",
  "result_hash": "sha256:<64 hex>",
  "merkle_root": "sha256:<64 hex>",
  "manifest_signature": "string",
  "file_count": "integer",
  "total_bytes": "integer",
  "files": ["sorted file entries"],
  "attestation_status": "pending | computed | complete",
  "attested_at": "ISO-8601 UTC timestamp",
  "schema_version": "1.0",
  "switchboard_slot": "integer | null",
  "switchboard_tx": "string | null",
  "switchboard_feed": "string | null"
}
```

The authoritative cryptographic values are `result_hash`, `merkle_root`, `files`, and the on-chain anchors.

### 9.1 manifest_signature

`manifest_signature` is the gateway's own attestation that it computed the `merkle_root`. It complements the on-chain anchor: the anchor proves the root exists on Solana, the signature proves Nukez produced it. It is tamper-evidence at the gateway boundary, verifiable independently of the chain.

| Property | Value |
| --- | --- |
| Algorithm | Ed25519 |
| Signer | The gateway service key — the same key that signs `receipt_sig` |
| Signer public key | Published as `receipt_signer_pubkey` on `GET /v1/receipts/{receipt_id}` (64 lowercase hex chars) |
| Signed payload | The bare `merkle_root` with the `sha256:` prefix stripped, UTF-8 encoded — **not** the prefixed string and **not** the raw 32 bytes |
| Signature encoding | Lowercase hex, 128 chars (a 64-byte Ed25519 signature). Note: not base58, despite some older internal docs |
| Unsigned fallback | If the signing key is unavailable, the field is `unsigned:<first 32 hex of sha256(merkle_root)>`. Verifiers **MUST** reject any value starting with `unsigned:`. |

Verification:

```python
import binascii
from nacl.signing import VerifyKey

pub_hex = GET(f"/v1/receipts/{receipt_id}")["receipt_signer_pubkey"]
sig_hex = attestation["manifest_signature"]
assert not sig_hex.startswith("unsigned:"), "unsigned placeholder — reject"

payload = attestation["merkle_root"].removeprefix("sha256:").encode("utf-8")
VerifyKey(binascii.unhexlify(pub_hex)).verify(payload, binascii.unhexlify(sig_hex))
# raises nacl.exceptions.BadSignatureError if the signature does not verify
```

For full chain-of-custody, the same `merkle_root` should also appear in the SPL Memo of the on-chain anchor transaction (`switchboard_tx`), tying the gateway signature to the on-chain record.

### 9.2 file_count binding (odd-node ambiguity)

The odd-node duplication rule (§ on tree construction) means two distinct file lists can in principle produce the same `merkle_root` — the classic CVE-2012-2459 ambiguity inherited from Bitcoin-style trees. Nukez closes this by binding the file count.

A verifier **MUST** confirm that the number of leaves it used to reconstruct the `merkle_root` equals the attested `file_count` (present in the attestation object and written into the on-chain SPL Memo). If the leaf count does not equal `file_count`, the verification **MUST** be rejected even if the reconstructed root matches. This prevents a forged file list that exploits odd-node duplication from validating against a legitimate root.

Filenames cannot contain `:` (server-side validation rejects it, along with `\`, `..`, and a leading `.` outside the system-prefix allowance), so the `filename:size_bytes:content_hash` leaf material is unambiguous. A third-party verifier reconstructing leaves should reject any filename containing `:` rather than attempt to parse it.

---

## 10. Result hash

`result_hash` is a deterministic digest over the locker's canonicalized manifest summary.

```python
manifest_summary = {
  "locker_id": locker_id,
  "files": sorted(
    [
      {
        "filename": file.filename,
        "size_bytes": file.size_bytes,
        "content_hash": file.content_hash
      }
      for file in files
    ],
    key=lambda e: e["filename"]
  )
}

canonical_json = json.dumps(
  manifest_summary,
  separators=(",", ":"),
  sort_keys=True,
  ensure_ascii=False
)

result_hash = "sha256:" + sha256(canonical_json.encode("utf-8")).hexdigest()
```

Canonical JSON rules:
- Keys sorted alphabetically at every level
- No whitespace between elements
- Separators `,` and `:` without spaces
- `ensure_ascii=False` (UTF-8 preserved as-is)

---

## 11. att_code (display / oracle value — NOT a security primitive)

> **Important**: `att_code` is **derived from `result_hash`**, not directly from `merkle_root`.
> `att_code` is **not the security primitive**. It is a compact oracle/display value
> suitable for UIs and on-chain oracle feeds where a full 256-bit hash is impractical.
> The authoritative values for verification are `result_hash`, `merkle_root`, the
> file entries, and the on-chain anchors.

```python
def att_code_from_hash(h):
    h = h.removeprefix("sha256:")
    return int(h[:12], 16) % 1_000_000_000
```

---

## 12. Inclusion proof schema

```json
{
  "receipt_id": "string",
  "filename": "string",
  "leaf_hash": "<64 hex>",
  "leaf_index": "integer",
  "merkle_root": "sha256:<64 hex>",
  "proof": [
    {
      "hash": "<64 hex>",
      "position": "left | right"
    }
  ],
  "tree_depth": "integer",
  "file_count": "integer",
  "file_entry": {
    "filename": "string",
    "size_bytes": "integer",
    "content_hash": "string"
  },
  "schema_version": "1.0"
}
```

---

## 13. Proof verification

```python
current = leaf_hash

for step in proof:
    sibling = step["hash"].removeprefix("sha256:")
    if step["position"] == "left":
        current = sha256((sibling + current).encode("utf-8")).hexdigest()
    else:
        current = sha256((current + sibling).encode("utf-8")).hexdigest()

assert "sha256:" + current == merkle_root
```

`position` describes where the **sibling** sits relative to `current`:
- `left` → sibling is on the left, so `sibling || current`
- `right` → sibling is on the right, so `current || sibling`

---

## 14. Public endpoints

```
GET  /v1/storage/verification-bundle?receipt_id={receipt_id}
GET  /v1/storage/merkle-proof?receipt_id={receipt_id}&filename={filename}
GET  /v1/storage/verify?receipt_id={receipt_id}
POST /v1/storage/verify         body: {"receipt_id": "..."}
GET  /v1/attest-code?receipt_id={receipt_id}
GET  /v1/receipts/{receipt_id}
GET  /v1/receipts/{receipt_id}/verify
```

All are unauthenticated. `verification-bundle` returns a self-contained proof package suitable for offline verification.

---

## 15. On-chain anchors

### Solana / Switchboard

- **PullFeed** stores the oracle `att_code` (the compact display value, not authoritative).
- **SPL Memo** instruction stores the authoritative metadata:
  - `schema` (this spec name)
  - `receipt_id`
  - `merkle_root`
  - `file_count`
  - `attested_at`

The SPL Memo is the cryptographically meaningful anchor; PullFeed is a convenience for on-chain consumers that can only handle small numeric values.

### Monad

- `receiptId` on Monad is `bytes16(keccak256(receipt_id_string))`.
- `verifyMerkle(receiptId)` returns: `merkleRoot`, `solanaSlot`, `fileCount`, `attestedAt`.

---

## 16. Test vector

Verifiers MUST reproduce these exact values to be considered conformant.

### Input

```json
{
  "files": [
    {
      "filename": "a.txt",
      "size_bytes": 3,
      "content_hash": "sha256:aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
    },
    {
      "filename": "b.txt",
      "size_bytes": 5,
      "content_hash": "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb"
    },
    {
      "filename": "c.txt",
      "size_bytes": 7,
      "content_hash": "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc"
    }
  ]
}
```

### Expected merkle root

```
sha256:a80128f3298c7b6bf0b894576066d61a1e270d8bf4638d01ddd6d8e626f45528
```

### Inclusion proof for `b.txt`

```json
[
  {
    "hash": "91481cbebb6c2f6438ed263b130212193ef908a9864c2b9b77d511bd07072879",
    "position": "left"
  },
  {
    "hash": "539d42382ade0da0fe370b9f86b80739b31db6f06ac8a482ef1f7390251f6262",
    "position": "right"
  }
]
```

Verifying this proof against the leaf hash of `b.txt` MUST yield the expected merkle root above.

---

## 17. Conformance

An implementation is conformant if:
1. It produces the exact root from §16 for the test vector.
2. It produces the exact proof from §16 for `b.txt`.
3. It rejects empty file lists with a clear error.
4. It treats `att_code` as a display value, never as a security primitive.
5. It applies the leaf-duplication rule on odd-count tree levels.

---

## 18. References

- Machine-readable spec: [/specs/nukez-merkle-v1.json](/specs/nukez-merkle-v1.json)
- Discovery doc: [/.well-known/nukez.json](/.well-known/nukez.json)
- Endpoint reference: [/openapi.json](/openapi.json)
- Narrative walkthrough: [/docs/verify](/docs/verify) (frontend) and [/proof/verify](/proof/verify) (frontend, per-receipt)