# `aborist.merkle`

Pure Merkle tree + proof primitives. Python port of
`proxy.unturf.com/pkg/verified/merkle.go` — convention-identical.
Used everywhere a content-addressable handle is needed: per-chunk
leaves, document_root, evidence_map_root, run_dag_root, snapshots.

## Conventions (do not silently change)

These match the Go reference & are load-bearing for cross-language
verification (Go peer ↔ Python peer compute bit-identical roots):

- **Leaf hash:** `sha256(0x00 || canonical_chunk_bytes)`. The `0x00`
  prefix domain-separates leaves from internal nodes.
- **Internal hash:** `sha256(0x03 || left || right)`. The `0x03`
  prefix is the **non-commutative** combine — `H(L,R) ≠ H(R,L)`.
  Order matters.
- **Odd-element rule:** when a level has an odd count, the last
  leaf is **self-duplicated** before pairing. NOT zero-padded.
- **Proof path:** each step carries an explicit `is_left: bool`
  alongside the sibling hash so a verifier knows which side to put
  the sibling on. Never sort siblings lexically — the order tells
  the verifier the tree topology.

## API surface

```python
from aborist.merkle import MerkleTree, MerkleProof

tree = MerkleTree.build([b"chunk_0_bytes", b"chunk_1_bytes", ...])
tree.root            # bytes(32) — sha256 of the whole tree
tree.leaves          # list[bytes(32)] — leaf hashes in input order

proof = tree.proof_for(leaf_index=2)
proof.siblings       # list[(sibling_hash, is_left)]
proof.verify(leaf_hash=tree.leaves[2], root=tree.root)  # bool
```

## When to read the source

- Adding a new content-addressable artifact (cores, evidence maps,
  snapshots, run-DAGs all touch this).
- Cross-language verification debugging (Go peer says one root,
  Python peer says another — the difference is always in canonical
  encoding, ordering, or one of the three prefix bytes above).
- Performance work — the Python build is ~3× slower than the Go
  reference; if it ever shows up in profiling, that's the file.

## Diagrams

The module graph shows what depends on `merkle.py` (a lot — it's
substrate):

![module graph](../diagrams/aborist-modules.svg)

The ingest pipeline shows where leaf & root hashes get computed:

![ingest pipeline](../diagrams/ingest-pipeline.svg)

## Source

[`aborist/merkle.py`](../../aborist/merkle.py) ·
Reference: [`proxy.unturf.com/pkg/verified/merkle.go`](https://git.unturf.com/engineering/unturf/proxy.unturf.com/-/blob/main/pkg/verified/merkle.go)
