4 ms·
The post offers a brief explanation of homomorphic hashing: > homomorphic hashing answers the question, “Given the hash of an input, along with a small update
by jawns 8y ago
The post offers a brief explanation of homomorphic hashing:
> homomorphic hashing answers the question, “Given the hash of an input, along with a small update to that input, how can we compute the hash of the new input (with the update applied) without having to recompute the entire hash from scratch?” We use LtHash, a specific homomorphic hashing algorithm based on lattice cryptography, to create an efficiently updatable checksum of a database.
Imagine adding and subtracting hashes!
> For any two disjoint sets S and T, LtHash(S) + LtHash(T) = LtHash(S ∪ T).
This is cool because now you don't have to recompute from scratch a hash representing a large array; you can just compute the hash of the parts you update and perform addition and subtraction.
- zzzcpan 8y agoYears ago I was trying to use Merkle trees for checksuming and synchronizing database replicas, since everyone was doing it this way. It was immediately obvious how impractical it was. So the first thing that came to mind was to use a fixed sized Merkle tree (half trees or whatever they are called). It was essentially an array of 64k hashes with each element storing a hash for a set of database keys. That, however, required rescanning multiple keys on updates and the number of keys depended on the database size. Of course this wasn't going to work well. Naturally the same idea of adding and subtracting hashes came to mind. Adding a hash of a key on update and subtracting on removal allowed to completely eliminate reads from disk. And rescanning a particular set of keys was only necessary during background synchronization and only when a key was missing on a replica, which was pretty rare. Although I don't use this approach anymore, it did work well and was trivial to implement.
- maximegarcia 8y agoSaving it. This is what I dreamt of for the ETag header of a list of items in a REST API (when caching each of the items separatly).