# ROR-002: Find Common Ancestor

| Link | Path |
|------|------|
| **Normative** | [NORMATIVE.md](../NORMATIVE.md) |
| **Verification** | [VERIFICATION.md](../VERIFICATION.md) |
| **Tracking** | [TRACKING.yaml](../TRACKING.yaml) |
| **Spec** | [SPEC.md](../../../../resources/SPEC.md) Section 8.2 |

---

## Summary

`find_common_ancestor(&self, hash: &Bytes32, max_depth: u64) -> Result<Option<(Bytes32, u64)>>` MUST walk the parent_hash chain from the given hash, checking at each step whether the block is in the canonical chain. Returns the first canonical match as `(hash, height)`, or None if no ancestor is found within max_depth steps.

---

## Specification

### Function Signature

```rust
pub fn find_common_ancestor(
    &self,
    hash: &Bytes32,
    max_depth: u64,
) -> Result<Option<(Bytes32, u64)>>
```

### Algorithm

```
current = hash
for i in 0..max_depth:
    record = get_record(current)
    if record is None:
        return None  // chain broken, block not in store
    canonical_hash = get_hash_by_height(record.height)
    if canonical_hash == Some(current):
        return Some((current, record.height))  // found ancestor
    current = record.parent_hash
return None  // exceeded max_depth
```

### Implementation

```rust
pub fn find_common_ancestor(
    &self,
    hash: &Bytes32,
    max_depth: u64,
) -> Result<Option<(Bytes32, u64)>> {
    let mut current_hash = *hash;

    for _ in 0..max_depth {
        let record = match self.get_record(&current_hash)? {
            Some(r) => r,
            None => return Ok(None), // block not in store
        };

        // Check if this block is the canonical block at its height
        if let Some(canonical_hash) = self.get_hash_by_height(record.height)? {
            if canonical_hash == current_hash {
                return Ok(Some((current_hash, record.height)));
            }
        }

        // Walk backwards
        current_hash = record.parent_hash;
    }

    Ok(None) // no common ancestor within max_depth
}
```

### Use Cases

1. **Reorg detection**: When a new block arrives whose parent is not the current tip, call `find_common_ancestor` with the new block's parent hash to find the fork point.

2. **Fork analysis**: Walk a fork chain to determine how far back it diverges from the canonical chain.

### Edge Cases

| Scenario | Result |
|----------|--------|
| Hash is already canonical | Returns `Some((hash, height))` on first iteration |
| Hash not in store | Returns `None` immediately |
| Fork diverges deeper than max_depth | Returns `None` |
| Parent chain has a gap (missing block) | Returns `None` at the gap |
| max_depth = 0 | Returns `None` (loop body never executes) |

---

## Acceptance Criteria

- [ ] Returns the fork point when given a fork tip hash
- [ ] Returns the block itself if it is already canonical
- [ ] Returns None when hash is not in the store
- [ ] Returns None when the fork is deeper than max_depth
- [ ] Returns None when max_depth is 0
- [ ] Correctly walks the parent_hash chain backwards
- [ ] Stops at the first canonical ancestor (does not over-walk)
- [ ] Works with forks that branch at height 0 (genesis is the ancestor)

---

## Implementation Notes

- Performance: each iteration requires a `get_record` (cache hit ~100ns, miss ~5us) and a `get_hash_by_height` (mmap ~10ns). For typical reorgs (depth 1-6), this is sub-microsecond.
- The `max_depth` parameter prevents unbounded traversal in adversarial cases. A reasonable default for production use is 100-1000 blocks.
- This function is read-only and does not modify any state. It is safe to call concurrently.

---

## Test Plan

| Test Name | Type | Description |
|-----------|------|-------------|
| `test_find_ancestor_at_fork_point` | unit | Build canonical chain, add fork at height F, verify ancestor is at height F |
| `test_find_ancestor_already_canonical` | unit | Pass a canonical block hash, verify it returns itself |
| `test_find_ancestor_not_in_store` | unit | Pass an unknown hash, verify None |
| `test_find_ancestor_exceeds_depth` | unit | Set max_depth smaller than fork depth, verify None |
| `test_find_ancestor_zero_depth` | unit | Call with max_depth=0, verify None |
| `test_find_ancestor_at_genesis` | unit | Build a fork from genesis, verify ancestor is genesis (height 0) |
| `test_find_ancestor_broken_chain` | unit | Store fork blocks with a gap (missing parent), verify None at the gap |

---

## Expected Test Files

- `tests/ror_002_tests.rs`
