README
¶
LtHash 
LtHash is a family of functions defined by Bellare and Micciancio in [1] and implemented by engineers from Facebook in [2, 3].
This algorithm calculates hash of a set. Homomorphic hashing means that hash of a whole set can be
calculated based on hashes of it's subsets, e.g. h({a,b}) = h({a})*h({b}).
In essense this algorithm calculates blake2b hash of every element and then adds vectors as if
they were a collection of uint16 (uint32) values. On the byte level LittleEndian representation is used.
Usage
h := lthash.New16()
// Add 3 objects
h.Add([]byte("John"))
h.Add([]byte("Maria"))
// remember the hash of the set {"John", "Maria"}
sum := h.Checksum()
// after we add Anna to our party, hash should change.
h.Add([]byte("Anna"))
// after removing an element we have a set {"John", "Maria"}
// once again so a hash should be the same.
h.Remove([]byte("Anna"))
if !bytes.Equal(sum, h.Checksum()) {
panic("unexpected")
}
Notes
- Actually this algorithm calculates hash of a multiset, not a set. This means that any element can be added multiple times and every time checksum will be changed.
- Technically there is nothing wrong in removing element which you have not previously added. You will get no error in this case, so be careful.
Benchmarks
TODO
Other implementations
- Facebook implementation
- Another golang implementation (it is slightly slower)
Documentation
¶
Index ¶
Constants ¶
View Source
const Size = 2048
Size is a length of a checksum.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type HomoHash ¶
type HomoHash interface {
// Add adds p to the multiset.
Add(p []byte)
// Remove removes p from the multiset.
Remove(p []byte)
// Sum appends the hash of the current multiset to b and returns the resulting slice.
// It does not change the underlying hash state.
Sum(b []byte) []byte
// SetState initializes current state with s.
SetState(s []byte)
}
HomoHash interface defines a set of operations for any homomorphic hash.
Source Files
Directories
Click to show internal directories.
Click to hide internal directories.