[joelg]

The merkle tree is persisted, and updating it is only log(n). You only have to "hash 2n elements" once, and then incrementally maintain it. It's negligible overhead for free log(n) diffing.