2 ms·
Ah, thanks for the explanation. Some quick follow ups: Oh, so an incremental hash function is where you don't have to hash the entire thing again, but you can
by iamwil 3y ago
Ah, thanks for the explanation. Some quick follow ups:
Oh, so an incremental hash function is where you don't have to hash the entire thing again, but you can use the combiner (xor) to "remove" the old_child.hash and "add" the new_child.hash? And you use this to decrease the cost of hashing?
Huh, I didn't make up the term "unicit". I read it somewhere, presumably from Aaron Boodman, who invented the Prolly Tree.
- j-pb 3y agoExactly! The xor combiner is somewhat special in that it is self inverse, so a xor b xor a = b. This property doesn't hold for the other combiners, so for any other combiner ⊙ you would need to compute the inverse `old_child_hash^-1` for the removed hash so that `new_hash = old_hash ⊙ old_child_hash^-1 ⊙ new_child_hash`. Although I feel like I should re-iterate that the xor-combiner (in the paper termed XHASH) does not produce a cryptographic hash in any way and to quote the paper "Indeed, it is not even one-way". For my use case this means that you can only perform set operations in O(|common-prefix|) time with trusted peers and I actually don't expose the hash beyond the process itself. You can ofc ingest data from untrusted peers, that's why the randomization function (the function used for the keys/leafs) is keyed, with a key that is choosen randomly at library initalisation. In my case I'm storing hashes in the branch-nodes, but re-compute hashes for the leafs, so when performing set operations between two tries you often don't have to compute any hash. I didn't mean to imply that, I was just hoping to find a new root for research paper exploration, but even if you did it would be fine, it's a property that should have it's own name, I personally call them "deterministic"-trees :D.