# PAR-003: Tree Hash via clvm_utils::tree_hash()

> **Authoritative requirement:** [PAR-003](../NORMATIVE.md#PAR-003)
> **Verification:** [VERIFICATION.md](../VERIFICATION.md)
> **Tracking:** [TRACKING.yaml](../TRACKING.yaml)
> **Spec reference:** [SPEC.md](../../../../resources/SPEC.md) — Section 7

---

## Summary

Tree hash computation in `dig-clvm` must use `clvm_utils::tree_hash()`, producing results identical to Chia L1 as tested in [`test_curry_and_treehash.py`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/_tests/clvm/test_curry_and_treehash.py). The CLVM tree hash algorithm is the canonical content-addressing scheme for all Chia puzzles: a puzzle's identity is its tree hash, and puzzle hashes appear in every coin (as `puzzle_hash`) and in currying operations. Any deviation in tree hash computation would cause coins to have different IDs, puzzles to have different hashes, and validation to fail.

The tree hash algorithm is simple but must be implemented exactly: for an atom node, the hash is `sha256(0x01 || data)`; for a pair node, the hash is `sha256(0x02 || left_hash || right_hash)`. The `clvm_utils` crate (v0.26) provides `tree_hash(allocator, node)` which computes this recursively over a CLVM S-expression tree. It also provides standalone primitives `tree_hash_atom(bytes)` and `tree_hash_pair(left, right)` for computing hashes without an allocator, and `curry_tree_hash(program_hash, arg_hashes)` for computing the hash of a curried program without materializing it.

The `dig-clvm` crate must re-export `tree_hash`, `tree_hash_atom`, `tree_hash_pair`, `curry_tree_hash`, `TreeHash`, `CurriedProgram`, and `ToTreeHash` from `clvm_utils`. No custom tree hash implementation is permitted. This ensures that puzzle hashes computed by `dig-clvm` callers are identical to those computed by Chia L1 nodes, which is essential for cross-chain parity in the DIG network.

---

## Specification

### Algorithm Definition

```
tree_hash(atom)  = sha256(0x01 || atom_bytes)
tree_hash(pair)  = sha256(0x02 || tree_hash(left) || tree_hash(right))
```

Where:
- `0x01` is the single byte `\x01` (atom tag)
- `0x02` is the single byte `\x02` (pair tag)
- `||` is byte concatenation
- `sha256` is the SHA-256 cryptographic hash function
- The result is a 32-byte hash (`TreeHash` newtype)

### API Surface

```rust
use clvm_utils::{tree_hash, tree_hash_atom, tree_hash_pair, TreeHash};
use clvm_utils::{curry_tree_hash, CurriedProgram, ToTreeHash};

// Compute hash of a CLVM tree in an allocator
let hash: TreeHash = tree_hash(&allocator, node_ptr);

// Compute atom hash without allocator
let atom_hash: TreeHash = tree_hash_atom(&[1, 2, 3]);
// = sha256(0x01 || [1, 2, 3])

// Compute pair hash from two child hashes
let pair_hash: TreeHash = tree_hash_pair(left_hash, right_hash);
// = sha256(0x02 || left_hash.as_bytes() || right_hash.as_bytes())

// Compute curried puzzle hash without materializing
let curried_hash: TreeHash = curry_tree_hash(
    program_hash,           // TreeHash of the uncurried program
    &[arg1_hash, arg2_hash] // TreeHash of each curried argument
);
```

### Known Reference Values

From [`test_curry_and_treehash.py`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/_tests/clvm/test_curry_and_treehash.py):

```rust
// The empty atom (nil)
let nil_hash = tree_hash_atom(&[]);
// = sha256(0x01) = 4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a

// The atom "1" (single byte 0x01)
let one_hash = tree_hash_atom(&[1]);
// = sha256(0x01 || 0x01)

// A simple pair (1 . nil)
let pair_hash = tree_hash_pair(one_hash, nil_hash);
// = sha256(0x02 || one_hash || nil_hash)
```

### Prohibited Patterns

```rust
// PROHIBITED: Custom tree hash implementation
fn my_tree_hash(node: &ClvmNode) -> [u8; 32] {
    match node {
        Atom(data) => sha256(&[&[1u8], data].concat()),
        Pair(l, r) => sha256(&[&[2u8], &my_tree_hash(l), &my_tree_hash(r)].concat()),
    }
}

// PROHIBITED: Using a different hash function
fn tree_hash_blake(node: NodePtr) -> [u8; 32] { /* blake3 instead of sha256 */ }
```

### Re-exports

```rust
// In dig-clvm's lib.rs:
pub use clvm_utils::{tree_hash, curry_tree_hash, CurriedProgram, TreeHash, ToTreeHash};
```

---

## Acceptance Criteria

- [ ] `tree_hash()` is imported from `clvm_utils`, not custom-defined
- [ ] `grep -r "fn tree_hash" src/` returns zero matches (no custom implementation)
- [ ] Hash of the nil atom matches the known reference value `4bf5122f...`
- [ ] `curry_tree_hash()` produces the same result as computing `tree_hash()` on a materialized curried program
- [ ] `TreeHash`, `tree_hash`, `curry_tree_hash`, `CurriedProgram`, and `ToTreeHash` are re-exported from the crate root

---

## Implementation Notes

- `tree_hash()` requires a reference to the `Allocator` because it traverses the S-expression tree stored in the allocator's memory.
- `tree_hash_atom()` and `tree_hash_pair()` are allocator-free and can be used for computing hashes of values known at compile time or from external data.
- `curry_tree_hash()` is an optimization: it computes the hash of `(a (q . program) (c (q . arg1) (c (q . arg2) ... 1)))` without building the CLVM tree. This is used extensively for computing puzzle hashes from known components.
- The `ToTreeHash` trait allows types to compute their own tree hash, enabling composable hash computation.

---

## Verification

### Test Plan

1. **Nil atom hash**:
   ```rust
   use clvm_utils::tree_hash_atom;
   let hash = tree_hash_atom(&[]);
   assert_eq!(
       hex::encode(hash),
       "4bf5122f344554c53bde2ebb8cd2b7e3d1600ad631c385a5d7cce23c7785459a"
   );
   ```

2. **Known program hash**:
   - Load the `P2_DELEGATED_PUZZLE_OR_HIDDEN_PUZZLE` bytecode from `chia-puzzles`.
   - Deserialize into an `Allocator` and compute `tree_hash()`.
   - Assert the hash matches the known `P2_DELEGATED_PUZZLE_OR_HIDDEN_PUZZLE_HASH`.

3. **Curry round-trip**:
   - Compute `curry_tree_hash(program_hash, &[arg_hash])`.
   - Build the curried program in an allocator using `CurriedProgram`.
   - Compute `tree_hash()` on the materialized tree.
   - Assert both hashes are identical.

4. **Cross-validation with L1 reference values**:
   - Take test vectors from `test_curry_and_treehash.py`.
   - Compute tree hashes via `clvm_utils::tree_hash()`.
   - Assert exact match with L1 expected values.

5. **Code review -- no custom implementation**:
   - Run `grep -rn "fn tree_hash\|fn compute_hash\|fn puzzle_hash" src/`.
   - Verify no custom hash implementation exists.

6. **Re-export verification**:
   - In an integration test, import `dig_clvm::tree_hash` and `dig_clvm::TreeHash`.
   - Verify they compile and produce correct results.

### Expected Test Files

- `tests/parity_tests.rs` -- PAR-003 tree hash cross-validation tests

---

## Source Citations

- Chia L1 tree hash tests: [`test_curry_and_treehash.py`](https://github.com/Chia-Network/chia-blockchain/blob/main/chia/_tests/clvm/test_curry_and_treehash.py)
- `clvm_utils` API: [SPEC.md Section 2.3](../../../../resources/SPEC.md)
- Tree hash algorithm: `atom = sha256(0x01 || data)`, `pair = sha256(0x02 || left || right)`

---

## References

- [PAR-001](PAR-001.md) -- CLVM execution (tree hash operates on CLVM output trees)
- [PAR-008](PAR-008.md) -- Protocol types (Coin contains `puzzle_hash` which is a tree hash)
