Merkle tree diff between replicas
Your task
Two replicas detect divergence by comparing Merkle trees over their key ranges. Each replica stores a sorted list of leaf hashes (one integer per fixed key bucket; both lists have the same length m, which is a power of two). A full binary Merkle tree is built over the leaves bottom-up: a parent hash is (left * 31 + right) & 0xFFFFFFFF. To diff, compare roots; if equal, the subtrees match. Otherwise recurse into both children, and at the leaf level record the index of any differing bucket. Return the sorted list of leaf-bucket indices (0-based) where the two replicas differ, visiting only the subtrees whose hashes mismatch (the whole point of the Merkle optimization).
Examples
merkle_diff(leaves_a: list[int], leaves_b: list[int]) -> list[int]Example 1
Input
merkle_diff([1, 2, 3, 4], [1, 2, 9, 4])Output
[2]