lthash

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

1. 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.
2. 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
• type HomoHash
  • func New16() HomoHash
  • func New32() HomoHash

Constants

const Size = 2048

Size is a length of a checksum.

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.

func New16

func New16() HomoHash

New16 returns lthash which works with 16-bit numbers.

func New32

func New32() HomoHash

New32 returns lthash which works with 32-bit numbers.