[themoonisachees]

Question:since doing this requires hashing your entire tree, what are the implications of doing this hashing operation on possibly millions of entries (which I'm estimating is the scale at which comparing linearly really start being noticably slow)?

I'm guessing you need to choose a hashing function correctly, but is hashing 2n elements then comparing in log(n) actually that much faster than comparing in n? Evidently, with the right settings yes, or we wouldn't be here, but I'm just wondering if the hashing step doesn't actually end up costing a lot more than we think by saying "oh we just hash it"

[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.