perf(audit): optimize Merkle tree rebuilding to O(log n) per append

[andybons]

Background

Currently Store.rebuildMerkleRoot() (store.go:154) loads and rebuilds the entire Merkle tree on every append operation. This is O(n) complexity per write.

Problem

For runs with 10k+ log entries, this becomes a performance bottleneck. Each append requires loading all entries and recomputing the full tree.

Proposed Solution

Implement incremental Merkle tree updates:

• Track the tree structure in memory
• Only recompute affected branches when appending
• This reduces append cost from O(n) to O(log n)

Acceptance Criteria

• Incremental tree updates on append
• Maintain ability to rebuild full tree on store open
• No change to verification behavior
• Benchmark showing improvement for large entry counts

Priority

Low - Current implementation is acceptable for Phase 1. Only optimize if performance issues are observed with high-volume logging.

References

• PR feat(audit): add tamper-proof audit logging with cryptographic verification #3 review comment on Merkle tree performance